Introduction

Take any set of positive integers. Add up the reciprocals of its elements: 1a1+1a2+1a3+…\frac{1}{a_1} + \frac{1}{a_2} + \frac{1}{a_3} + \dots. Sometimes that sum settles down to a finite number; sometimes it grows without bound — it diverges.

In 1936, Paul Erdős and Pál Turán noticed something suggestive: sets whose reciprocals diverge tend to be "spread out enough" that they can't avoid falling into an arithmetic progression — a run of numbers with constant spacing, like 3,7,11,153, 7, 11, 15.

Erdős later sharpened this into one of his most tantalizing conjectures: if the reciprocals of a set diverge, that set must contain arithmetic progressions of every possible length. It sounds almost too clean to be true — and nobody has been able to prove or disprove it in nearly 90 years.

Try It

Pick a set below and watch two things happen at once: the running sum of 1n\frac{1}{n} over the set, and a live search for 3-term arithmetic progressions hiding inside it — triples a,a+d,a+2da, a+d, a+2d all in the set.

<p class="hint">Every set below is a run of positive integers. Watch the running sum of reciprocals grow underneath it, and see which numbers (highlighted in red) belong to a 3-term arithmetic progression <b>a, a+d, a+2d</b> hiding inside the set.</p>
<div class="controls">
  <label for="setPicker">Set:</label>
  <select id="setPicker">
    <option value="powers2">Powers of two (1, 2, 4, 8, …) — sum converges</option>
    <option value="squares">Perfect squares (1, 4, 9, 16, …) — sum converges</option>
    <option value="primes">Primes (2, 3, 5, 7, …) — sum diverges</option>
    <option value="all" selected>All positive integers — sum diverges</option>
  </select>
  <button id="search" type="button">Search for progressions</button>
</div>
<div class="sumline" id="sumline">Pick a set to see its reciprocal sum.</div>
<div id="track" class="track"></div>
<div class="status" id="status">Click search to hunt for arithmetic progressions.</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; gap: .6rem; align-items: center; flex-wrap: wrap; margin-bottom: .6rem; }
.controls label { font-size: .85rem; font-weight: 600; color: #1d3557; }
select { font: 600 14px system-ui, sans-serif; padding: .4rem .6rem; border-radius: 8px; border: 1px solid #adb1b8; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
.sumline { font: 700 15px ui-monospace, monospace; color: #1d3557; margin: .3rem 0 .5rem; }
.track { display: flex; flex-wrap: wrap; gap: 6px; margin: .4rem 0; min-height: 46px; }
.num { width: 40px; height: 34px; display: flex; align-items: center; justify-content: center;
       font: 700 13px ui-monospace, monospace; border-radius: 6px; background: #e8eef3;
       color: #1d3557; border: 1px solid #cdd9e3; transition: all .15s; }
.num.ap { background: #e63946; border-color: #c92f3c; color: #fff; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.diverge { color: #0a7d33; }
.status.converge { color: #c92f3c; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// Four example sets — two with a convergent reciprocal sum, two with a divergent one.
const SETS = {
  // Sparse: reciprocals sum to < 2 no matter how far you extend it.
  powers2: [1,2,4,8,16,32,64,128,256,512],
  // Also sparse enough to converge (sum of 1/n^2 = pi^2/6 in the limit).
  squares: Array.from({length:12}, (_,i)=>(i+1)*(i+1)),
  // The sum of reciprocals of primes diverges (Euler, 1737), despite primes thinning out.
  primes: [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71],
  // The harmonic series 1 + 1/2 + 1/3 + ... diverges, famously slowly.
  all: Array.from({length:40}, (_,i)=>i+1),
};

// Whether each set's reciprocal sum diverges, for the status message.
const DIVERGES = { powers2: false, squares: false, primes: true, all: true };

let current = 'all';

// Brute-force scan: for every pair a < b in the set, check whether a + 2(b-a) is also in the set.
function findAPs(arr){
  const set = new Set(arr);
  const sorted = [...arr].sort((a,b)=>a-b);
  const found = [];
  for (let i=0;i<sorted.length;i++){
    for (let j=i+1;j<sorted.length;j++){
      const a = sorted[i], b = sorted[j], d = b-a;
      if (d<=0) continue;
      const c = b+d;
      if (set.has(c)) found.push([a,b,c]);
    }
  }
  return found;
}

function render(){
  const arr = SETS[current];
  const track = document.getElementById('track');
  track.innerHTML = '';
  let sum = 0;
  const sums = arr.map(n => { sum += 1/n; return sum; });
  const aps = findAPs(arr);
  const inAP = new Set();
  aps.forEach(([a,b,c]) => { inAP.add(a); inAP.add(b); inAP.add(c); });

  arr.forEach((n, idx) => {
    const d = document.createElement('div');
    d.className = 'num' + (inAP.has(n) ? ' ap' : '');
    d.textContent = n;
    d.title = i18nFmt('running sum so far: %s%', { s: sums[idx].toFixed(3) });
    track.appendChild(d);
  });

  const finalSum = sums[sums.length-1];
  document.getElementById('sumline').textContent =
    i18nFmt('Sum of 1/n over this set so far: %s%', { s: finalSum.toFixed(3) });

  setStatus(aps.length, DIVERGES[current]);
}

function setStatus(count, diverges){
  const s = document.getElementById('status');
  if (diverges) {
    s.textContent = i18nFmt('Reciprocals diverge — and sure enough, %n% number(s) sit inside a 3-term arithmetic progression.', { n: count });
    s.className = 'status diverge';
  } else {
    s.textContent = i18nFmt('Reciprocals converge — this set is nearly starved of arithmetic progressions (%n% number(s) involved).', { n: count });
    s.className = 'status converge';
  }
}

document.getElementById('setPicker').addEventListener('change', (e) => {
  current = e.target.value;
  render();
});
document.getElementById('search').addEventListener('click', render);

render();
Result
Console

Notice the pattern. A sparse set like the powers of two (1,2,4,8,16,…1, 2, 4, 8, 16, \dots) has a reciprocal sum that converges — and it turns out to have essentially no 3-term progressions at all. A dense set like all positive integers, or the primes, has a divergent sum — and progressions turn up everywhere, almost immediately.

The Real Complexity

Status: open. No proof, no counterexample — this is one of Erdős's largest bounties, commonly cited at $5,000, for whoever settles it either way.

Why is it so hard? Because it asks for a single unifying reason behind two very different-looking results that mathematicians only proved separately, decades apart:

  • Szemerédi's theorem (1975): any set of integers with positive density — roughly, a fixed fraction of all integers, like "every hundredth number" — contains arithmetic progressions of every length. This is a genuinely hard theorem, but it does not need divergence, just density.
  • The primes: the sum 12+13+15+17+…\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \dots over all primes diverges (Euler proved this back in 1737), even though the primes get sparser and sparser and have zero density. In 2004, Ben Green and Terence Tao proved the primes still contain arbitrarily long arithmetic progressions — a spectacular result that won Tao a Fields Medal in part for the surrounding work.

The Erdős–Turán conjecture would explain both results at once, from a single condition — divergence of reciprocals — that is weaker than positive density and doesn't care how a set thins out, only how much "weight" survives. Proving it would automatically reprove Szemerédi's theorem and the Green–Tao theorem as special cases. That is exactly why it stays out of reach: a proof would have to explain a huge zoo of examples with one clean argument, and every attempt so far only handles special cases.

Where It Matters

"How much of a set do you need before a pattern becomes unavoidable?" is a question that repeats across mathematics, and the Erdős conjecture is its purest form:

  • Additive combinatorics: the entire field grew out of exactly this density-versus-structure tension, with Szemerédi's theorem and the Green–Tao theorem as its two biggest landmarks.
  • Analytic number theory: reciprocal sums of primes, twin primes and other special sequences are a standard tool for measuring how "large" a set of numbers really is — see how the same idea plays out for gaps between twin primes.
  • Ramsey-type reasoning: the conjecture is a cousin of Ramsey theory — both ask how much size or structure is enough to force a pattern, no matter how you try to avoid it.
  • Open-problem culture: Erdős funded dozens of conjectures like this one out of his own pocket; the bounties turned mathematics into a game with real stakes, and many are still unclaimed.

Understand why this conjecture resists proof and you've grasped the central question of additive combinatorics: density can force structure, but turning that intuition into a universal theorem is often the hardest step in mathematics.

Conclusion

The Erdős–Turán conjecture asks for something almost embarrassingly simple: enough "weight" in a set of integers, measured only by whether its reciprocals diverge, should be enough to guarantee arithmetic progressions of every length. We already know this is true for dense sets (Szemerédi) and for the primes (Green–Tao) — yet the general statement, which would explain both at once, remains unproven.

It is a reminder that in mathematics, knowing many special cases of a pattern is not the same as knowing why the pattern must always hold. Somewhere between "the primes" and "all sets with divergent reciprocals" sits a gap nobody has closed — and a real bounty waiting for whoever closes it, the same way the P vs NP question waits for a proof either way.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/erdos-arithmetic-progressions/Content licensed under CC BY-NC 4.0.