Erdős Problem #876

Erdős Problem 876 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/876

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/876.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/876.tex.

FORMAL RESTATEMENT. Let $A=\{a_1<a_2<\cdots\}\subset\mathbb N$ be infinite. The problem defines $A$ to be sum-free if there are no solutions to \[ a=b_1+\cdots+b_r \] with $r\ge 2$ and $b_1<\cdots<b_r<a$ all in $A$. Equivalently: \[ \forall j\ge 2,\qquad a_j\notin \Big\{\sum_{i\in I} a_i: \emptyset\neq I\subset\{1,\dots,j-1\}\Big\}. \]

Question: how small can gaps $a_{n+1}-a_n$ be? In particular, does there exist such an infinite $A$ for which \[ a_{n+1}-a_n < n \] holds (presumably for all sufficiently large $n$; the statement in the problem text does not specify whether this is required for all $n$, eventually, or infinitely often).

QUICK LITERATURE/CONTEXT CHECK. The problem text itself states (without proofs) several results and constructions:

• Erdős proved every such sum-free set has density zero.
• Deshouillers--Erdős--Melfi constructed a sum-free set with $a_n\sim n^{3+o(1)}$.
• Erdős reports that Graham proved existence of a sequence with $a_{n+1}-a_n<n^{1+o(1)}$.
• Łuczak--Schoen proved $|A\cap[1,N]|\ll (N\log N)^{1/2}$ and constructed examples with $|B\cap[1,N]|\gg N^{1/2}/(\log N)^{1/2+o(1)}$.

I do not use any additional literature beyond what is explicitly in the problem text.

ATTACK PLAN.

1. Construction track: build explicit infinite sequences avoiding all subset-sum hits; try to tune growth to make gaps small.
2. Lower-bound track: show that many integers are forbidden once a prefix is chosen, forcing large gaps.
3. Reality check: compute greedy examples and brute-force short prefixes under gap constraints.

WORK.

Lemma 1 (superincreasing sequences are sum-free in this sense). Suppose $A=\{a_1<a_2<\cdots\}\subset\mathbb N$ satisfies \[ a_{m} > \sum_{i=1}^{m-1} a_i\qquad\text{for all }m\ge 2. \] Then $A$ is sum-free in the sense of the problem (no element is a sum of distinct smaller elements).

Proof. Fix $m\ge 2$ and consider any sum of distinct elements of $\{a_1,\dots,a_{m-1}\}$. Its value is at most $\sum_{i=1}^{m-1} a_i$, which is strictly less than $a_m$ by hypothesis. Therefore $a_m$ cannot be represented as such a sum. Since this holds for every $m$, no element of $A$ is a sum of distinct smaller elements, which is exactly the defining property. $\square$

Lemma 2 (the greedy algorithm from $1$ gives powers of $2$). Define a greedy sequence by $a_1=1$ and, for $m\ge 1$, let $a_{m+1}$ be the smallest integer $>a_m$ that is not representable as a sum of distinct elements from $\{a_1,\dots,a_m\}$. Then $a_m=2^{m-1}$ for all $m\ge 1$.

Proof. We prove by induction that after choosing $\{1,2,4,\dots,2^{m-1}\}$, the set of subset sums of these elements is exactly $\{0,1,2,\dots,2^{m}-1\}$.

Base $m=1$: subset sums of $\{1\}$ are $\{0,1\}$.

Inductive step: assume subset sums of $\{1,2,4,\dots,2^{m-1}\}$ equal $\{0,1,\dots,2^m-1\}$. Adding $2^m$ produces new sums of the form $2^m+s$ with $s\in\{0,1,\dots,2^m-1\}$, i.e. exactly $\{2^m,2^m+1,\dots,2^{m+1}-1\}$. Together with the old sums, this is $\{0,1,\dots,2^{m+1}-1\}$.

Therefore the smallest positive integer not representable after $m$ steps is $2^m$, so the greedy rule forces $a_{m+1}=2^m$. This proves $a_m=2^{m-1}$ for all $m$. $\square$

A tiny explicit obstruction to very small gaps (finite check). If a sum-free set contains $2,3,4$, then it cannot contain $5,6,$ or $7$, because \[ 5=2+3,\qquad 6=2+4,\qquad 7=3+4, \] and in each case the right-hand side uses distinct smaller elements. Hence the next element after $4$ must be at least $8$, forcing a gap $\ge 4$ at that point.

VERIFICATION (FAST REALITY CHECK). I computed a few canonical examples.

• Greedy from $1$ gives powers of $2$ (Lemma 2):

  1,2,4,8,16,32,64,128,...
  

  Gaps are $1,2,4,8,\dots$ (exponential), so certainly not $<n$.

• Greedy from $3$ (same greedy rule but starting at $3$) begins:

  3,4,5,6,16,17,49,50,148,149,445,446,...
  

  with gaps

  1,1,1,10,1,32,1,98,1,296,1,890,...
  

  so the inequality $a_{n+1}-a_n<n$ fails already at the fourth gap ($10>4$).

• Exhaustive backtracking for the gap condition $a_{i+1}-a_i<i$ for $i\ge 2$ shows:
  • starting with $a_1=2$, one cannot even construct a length-$4$ prefix satisfying both the sum-free condition and the gap condition (the only length-$3$ prefix is $2,3,4$, after which $5,6$ are forbidden as above);
  • starting with $a_1=3$, the longest possible prefix is $3,4,5,6$ (length $4$), since the next allowed element is $\ge 16$.
  These are finite sanity checks only; they do not resolve the asymptotic question.

FINAL. UNRESOLVED.

(i) Strongest proved partial result here. Lemma 1 gives a large explicit family of valid sequences (superincreasing), and Lemma 2 completely describes the greedy sequence starting from $1$. The small obstruction after $\{2,3,4\}$ shows why extremely small gaps are difficult.

(ii) First gap (crisp). Either construct an infinite sum-free sequence (in the problem's sense) with $a_{n+1}-a_n<n$ eventually, or prove that no such sequence exists.

(iii) Top 3 next moves (concrete).

1. Develop a quantitative "forbidden-sumset" lower bound: given a prefix $\{a_1,\dots,a_m\}$, lower bound the number of distinct subset sums (of size $\ge 2$) in an interval just above $a_m$, to force a lower bound on $a_{m+1}-a_m$.
2. Run a targeted computer search for long prefixes with constraints like $a_{n+1}-a_n\le n$ (or $\le n-1$) using branch-and-bound and memoization on subset-sum sets, to see whether the constraint survives to, say, $n=50$.
3. Attempt structured constructions (block constructions, base-$B$ digit restrictions, or "sparse + dense blocks") designed to create many collisions among subset sums while preventing any subset sum from landing back in $A$.

(iv) Minimal counterexample structure. A positive example for $a_{n+1}-a_n<n$ would need a mechanism that keeps each new $a_{m+1}$ outside the set of all subset sums of the prefix, while still allowing $a_{m+1}$ to lie within a window of length $\approx m$ above $a_m$. This suggests that the subset sums of the prefix must have exceptionally high collision density so that the forbidden set near $a_m$ is sparse.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

FORMAL RESTATEMENT. Let $A=\{a_1<a_2<\cdots\}\subset\mathbb N$ be infinite. The problem defines $A$ to be sum-free if there are no solutions to \[ a=b_1+\cdots+b_r \] with $r\ge 2$ and $b_1<\cdots<b_r<a$ all in $A$. Equivalently: \[ \forall j\ge 2,\qquad a_j\notin \Big\{\sum_{i\in I} a_i: \emptyset\neq I\subset\{1,\dots,j-1\}\Big\}. \]

Question: how small can gaps $a_{n+1}-a_n$ be? In particular, does there exist such an infinite $A$ for which \[ a_{n+1}-a_n < n \] holds (presumably for all sufficiently large $n$; the statement in the problem text does not specify whether this is required for all $n$, eventually, or infinitely often).

QUICK LITERATURE/CONTEXT CHECK. The problem text itself states (without proofs) several results and constructions:

• Erdős proved every such sum-free set has density zero.
• Deshouillers--Erdős--Melfi constructed a sum-free set with $a_n\sim n^{3+o(1)}$.
• Erdős reports that Graham proved existence of a sequence with $a_{n+1}-a_n<n^{1+o(1)}$.
• Łuczak--Schoen proved $|A\cap[1,N]|\ll (N\log N)^{1/2}$ and constructed examples with $|B\cap[1,N]|\gg N^{1/2}/(\log N)^{1/2+o(1)}$.

I do not use any additional literature beyond what is explicitly in the problem text.

ATTACK PLAN.

1. Construction track: build explicit infinite sequences avoiding all subset-sum hits; try to tune growth to make gaps small.
2. Lower-bound track: show that many integers are forbidden once a prefix is chosen, forcing large gaps.
3. Reality check: compute greedy examples and brute-force short prefixes under gap constraints.

WORK.

Lemma 1 (superincreasing sequences are sum-free in this sense). Suppose $A=\{a_1<a_2<\cdots\}\subset\mathbb N$ satisfies \[ a_{m} > \sum_{i=1}^{m-1} a_i\qquad\text{for all }m\ge 2. \] Then $A$ is sum-free in the sense of the problem (no element is a sum of distinct smaller elements).

Proof. Fix $m\ge 2$ and consider any sum of distinct elements of $\{a_1,\dots,a_{m-1}\}$. Its value is at most $\sum_{i=1}^{m-1} a_i$, which is strictly less than $a_m$ by hypothesis. Therefore $a_m$ cannot be represented as such a sum. Since this holds for every $m$, no element of $A$ is a sum of distinct smaller elements, which is exactly the defining property. $\square$

Lemma 2 (the greedy algorithm from $1$ gives powers of $2$). Define a greedy sequence by $a_1=1$ and, for $m\ge 1$, let $a_{m+1}$ be the smallest integer $>a_m$ that is not representable as a sum of distinct elements from $\{a_1,\dots,a_m\}$. Then $a_m=2^{m-1}$ for all $m\ge 1$.

Proof. We prove by induction that after choosing $\{1,2,4,\dots,2^{m-1}\}$, the set of subset sums of these elements is exactly $\{0,1,2,\dots,2^{m}-1\}$.

Base $m=1$: subset sums of $\{1\}$ are $\{0,1\}$.

Inductive step: assume subset sums of $\{1,2,4,\dots,2^{m-1}\}$ equal $\{0,1,\dots,2^m-1\}$. Adding $2^m$ produces new sums of the form $2^m+s$ with $s\in\{0,1,\dots,2^m-1\}$, i.e. exactly $\{2^m,2^m+1,\dots,2^{m+1}-1\}$. Together with the old sums, this is $\{0,1,\dots,2^{m+1}-1\}$.

Therefore the smallest positive integer not representable after $m$ steps is $2^m$, so the greedy rule forces $a_{m+1}=2^m$. This proves $a_m=2^{m-1}$ for all $m$. $\square$

A tiny explicit obstruction to very small gaps (finite check). If a sum-free set contains $2,3,4$, then it cannot contain $5,6,$ or $7$, because \[ 5=2+3,\qquad 6=2+4,\qquad 7=3+4, \] and in each case the right-hand side uses distinct smaller elements. Hence the next element after $4$ must be at least $8$, forcing a gap $\ge 4$ at that point.

VERIFICATION (FAST REALITY CHECK). I computed a few canonical examples.

• Greedy from $1$ gives powers of $2$ (Lemma 2):

  1,2,4,8,16,32,64,128,...
  

  Gaps are $1,2,4,8,\dots$ (exponential), so certainly not $<n$.

• Greedy from $3$ (same greedy rule but starting at $3$) begins:

  3,4,5,6,16,17,49,50,148,149,445,446,...
  

  with gaps

  1,1,1,10,1,32,1,98,1,296,1,890,...
  

  so the inequality $a_{n+1}-a_n<n$ fails already at the fourth gap ($10>4$).

• Exhaustive backtracking for the gap condition $a_{i+1}-a_i<i$ for $i\ge 2$ shows:
  • starting with $a_1=2$, one cannot even construct a length-$4$ prefix satisfying both the sum-free condition and the gap condition (the only length-$3$ prefix is $2,3,4$, after which $5,6$ are forbidden as above);
  • starting with $a_1=3$, the longest possible prefix is $3,4,5,6$ (length $4$), since the next allowed element is $\ge 16$.
  These are finite sanity checks only; they do not resolve the asymptotic question.

FINAL. UNRESOLVED.

(i) Strongest proved partial result here. Lemma 1 gives a large explicit family of valid sequences (superincreasing), and Lemma 2 completely describes the greedy sequence starting from $1$. The small obstruction after $\{2,3,4\}$ shows why extremely small gaps are difficult.

(ii) First gap (crisp). Either construct an infinite sum-free sequence (in the problem's sense) with $a_{n+1}-a_n<n$ eventually, or prove that no such sequence exists.

(iii) Top 3 next moves (concrete).

1. Develop a quantitative "forbidden-sumset" lower bound: given a prefix $\{a_1,\dots,a_m\}$, lower bound the number of distinct subset sums (of size $\ge 2$) in an interval just above $a_m$, to force a lower bound on $a_{m+1}-a_m$.
2. Run a targeted computer search for long prefixes with constraints like $a_{n+1}-a_n\le n$ (or $\le n-1$) using branch-and-bound and memoization on subset-sum sets, to see whether the constraint survives to, say, $n=50$.
3. Attempt structured constructions (block constructions, base-$B$ digit restrictions, or "sparse + dense blocks") designed to create many collisions among subset sums while preventing any subset sum from landing back in $A$.

(iv) Minimal counterexample structure. A positive example for $a_{n+1}-a_n<n$ would need a mechanism that keeps each new $a_{m+1}$ outside the set of all subset sums of the prefix, while still allowing $a_{m+1}$ to lie within a window of length $\approx m$ above $a_m$. This suggests that the subset sums of the prefix must have exceptionally high collision density so that the forbidden set near $a_m$ is sparse.