Erdős Conjecture on Arithmetic Progressions

Take any set of positive integers. Add up the reciprocals of its elements: $\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, 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.

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

<p class="hint">{{hint_para}}</p>
<div class="controls">
  <label for="setPicker">{{label_pick_set}}</label>
  <select id="setPicker">
    <option value="powers2">{{opt_powers2}}</option>
    <option value="squares">{{opt_squares}}</option>
    <option value="primes">{{opt_primes}}</option>
    <option value="all" selected>{{opt_all}}</option>
  </select>
  <button id="search" type="button">{{btn_search}}</button>
</div>
<div class="sumline" id="sumline">{{sum_hint}}</div>
<div id="track" class="track"></div>
<div class="status" id="status">{{status_hint}}</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; }

// Code not found

Notice the pattern. A sparse set like the powers of two ($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.

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 $\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.

"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.

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.