How small can the gaps in an infinite sum-free sequence be — is $a_{n+1}-a_n<n$ possible? (Erdős #876)
Statement
Let $A=\{a_1<a_2<\cdots\}\subset\mathbb{N}$ be an infinite sum-free set, in the strong sense that there are no solutions to $$a=b_1+\cdots+b_r$$ with $b_1<\cdots<b_r<a$ and $b_1,\ldots,b_r,a\in A$ — that is, no element of $A$ is a sum of distinct smaller elements of $A$. How small can the consecutive gaps $a_{n+1}-a_n$ be? Is it possible that $a_{n+1}-a_n<n$?
Acceptance. FULLY RESOLVES: a proof — machine-checkable (Lean/Coq) preferred, else a complete written proof with all steps — that either (a) constructs an infinite set $A$, sum-free in the stated strong sense, satisfying $a_{n+1}-a_n<n$ for all $n$ (or for all sufficiently large $n$, clearly flagged), or (b) shows that every such sum-free sequence must satisfy $a_{n+1}-a_n\geq n$ infinitely often. ADVANCES: a proof improving Graham's gap bound $a_{n+1}-a_n<n^{1+o(1)}$ to an explicit sharper function (e.g. $O(n(\log n)^C)$ with explicit $C$), strictly better than the best gap bound stated in the background; or a proof strictly improving either Łuczak–Schoen counting bound stated in the background; or a proof narrowing the maximum of $\sum_{n\in A}1/n$ strictly below Sullivan's bound of $4$ stated in the background (or a construction, with proof of sum-freeness, exceeding the best known lower value). Computations alone cannot close the problem — a finite prefix certifies nothing about an infinite sequence — though reproducible search code is welcome as supporting evidence for a proved construction. Deliver the proof file (and any construction/search code used).
Background
Posed by Erdős [Er75b], [Er77c], [Er98]; listed as open on erdosproblems.com/876 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics'), where the site notes it cannot be resolved by a finite computation. Erdős [Er62c] proved that every such sum-free set has density zero. In [Er98] Erdős reports that Graham proved there is a sum-free sequence with $a_{n+1}-a_n<n^{1+o(1)}$, with Melfi having a somewhat weaker result — so the question is precisely whether the exponent $1+o(1)$ can be brought down to gaps genuinely below $n$. Deshouillers, Erdős, and Melfi [DEM99] constructed a sum-free set growing like $a_n\sim n^{3+o(1)}$; the sharpest counting bounds are due to Łuczak and Schoen [LuSc00]: every such sum-free $A$ has $\lvert A\cap[1,N]\rvert\ll(N\log N)^{1/2}$ for all large $N$, while some sum-free $B$ achieves $\lvert B\cap[1,N]\rvert\gg N^{1/2}/(\log N)^{1/2+o(1)}$. The extremal growth is therefore $a_n=n^{2+o(1)}$, so average gaps are $n^{1+o(1)}$ and the question is delicately balanced: gaps below $n$ for all $n$ would force $\lvert A\cap[1,N]\rvert\gtrsim(2N)^{1/2}$, which the Łuczak–Schoen upper bound does not exclude. A companion question of Erdős [Er75b], [Er77c] asks for the maximum possible value of $\sum_{n\in A}1/n$ over such sets: Erdős proved it is $<100$, Sullivan improved this to $<4$ and conjectured the truth is slightly larger than $2$. Closely related is Erdős #790 (erdosproblems.com/790). The attacker's tool: design structured sum-free sequences (digit-restricted or Łuczak–Schoen-style block constructions) with provably slow gap growth — computer experiments on finite prefixes can guide the construction, but the deliverable is a proof of sum-freeness plus a gap bound.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #876 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #790 (related reciprocal-sum question for sum-free sets) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.