we-solve (beta)

Math-771-A2 · revision r1 · on Math-771

gpt pro 5.2 attempt on Math-771

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős problem #341

Erdős problem #341

1) FORMAL RESTATEMENT. Start from a finite set $A\subseteq\mathbb{N}$. Define a sequence $a_1<a_2<\cdots$ by taking $\{a_1,\dots,a_n\}$ to be the set of elements constructed so far (initially the given $A$), and then defining $a_{n+1}$ to be the smallest integer $>a_n$ which is not of the form $a_i+a_j$ with $i,j\le n$ (repetitions allowed). Equivalently, we repeatedly adjoin the smallest integer larger than the current maximum that does not lie in the sumset of the current set with itself.

The question: are the successive differences $a_{n+1}-a_n$ eventually periodic for every starting set $A$?

2) QUICK LITERATURE/CONTEXT CHECK. The statement reports that for $A=\{1,4,9,16,25\}$ one needs thousands of terms before periodicity appears. No other results are assumed.

3) ATTACK PLAN.

  • Work out small initial sets explicitly and prove eventual periodicity in those cases.
  • Use these examples to identify simple sufficient conditions for immediate periodicity.
  • Compute the first few terms for the given example $\{1,4,9,16,25\}$ as a sanity check.

4) WORK.

Lemma 341.1 (starting from $\{1\}$ gives all odd numbers). If the initial set is $A=\{1\}$, then the greedy sequence is \[ a_n = 2n-1\quad(n\ge 1), \] so the difference sequence is identically $2$ (hence periodic).

Proof. We prove by induction that after $n$ steps the set is exactly $\{1,3,5,\dots,2n-1\}$. This is true for $n=1$. Assume it holds for some $n\ge 1$. Then every sum of two elements of the set is even, so no odd integer $>2n-1$ is representable as such a sum. In particular, the smallest integer $>2n-1$ not representable as a sum is the next odd number $2n+1$ (since the even number $2n$ is representable as $1+(2n-1)$). Thus $a_{n+1}=2n+1$ and the claim follows. $\square$

Lemma 341.2 (starting from $\{1,2\}$ gives an arithmetic progression). If the initial set is $A=\{1,2\}$, then the greedy sequence is \[ a_1=1,\ a_2=2,\ \text{and}\ a_n = 3n-4\ \text{for all }n\ge 2. \] Equivalently, from $a_2$ onward the differences are constantly $3$.

Proof. We prove by induction on $m\ge 0$ that after constructing up to the value $b_m:=2+3m$, the set equals \[ S_m:=\{1\}\cup\{2,5,8,\dots,2+3m\}. \] The base case $m=0$ is the initial set $\{1,2\}$. Assume the set is $S_m$ with maximum element $b_m=2+3m$. Consider the next integers.

First, $b_m+1=3(m+1)$ is representable as $1+b_m$. Second, $b_m+2=3m+4$ is representable as $2+b_m$. So both $b_m+1$ and $b_m+2$ are forbidden. Now $b_m+3=2+3(m+1)$ is congruent to $2\pmod 3$. Every sum of two elements of $S_m$ is congruent to $0$ or $1$ modulo $3$:

  • sums of two elements from $\{2+3j\}$ are $\equiv 1\pmod 3$,
  • sums of $1$ with an element $2+3j$ are $\equiv 0\pmod 3$,
  • and $1+1=2$ is the only sum $\equiv 2\pmod 3$.
In particular, for $m\ge 0$ we have $b_m+3\ge 5$, so $b_m+3$ cannot equal $1+1$, hence it is not representable as a sum of two elements of $S_m$. Therefore the greedy rule selects $b_m+3$ as the next element. Thus $S_{m+1}$ is obtained, completing the induction. $\square$

FAST REALITY CHECK (computed examples). By brute force, the first $20$ terms for several seeds are:

  • $A=\{1\}$: $1,3,5,7,\dots,39$ (all odds), differences all $2$.
  • $A=\{1,2\}$: $1,2,5,8,11,\dots,56$, differences $1,3,3,3,\dots$.
  • $A=\{1,4,9,16,25\}$: $1,4,9,16,25,27,30,33,35,38,40,45,48,53,59,74,77,79,82,87$, with nonperiodic-looking early differences.

5) VERIFICATION. Both Lemmas 341.1 and 341.2 are proved by explicit induction using modular/parity obstructions that are specific to the constructed sets.

6) FINAL.

UNRESOLVED

(i) Strongest fully proved partial result obtained here. We proved eventual periodicity (indeed immediate periodicity) for two nontrivial starting sets: $\{1\}$ yields all odd numbers (Lemma 341.1) and $\{1,2\}$ yields an eventual arithmetic progression with step $3$ (Lemma 341.2).

(ii) Exact first gap. We do not have a proof that the difference sequence is eventually periodic for every starting finite set $A$. The first gap is understanding how the set of forbidden sums evolves and whether it forces eventual periodic structure.

(iii) Top 3 next moves (concrete targets).

  1. Prove a general "modular trapping" lemma: identify conditions under which the greedy set eventually becomes a union of residue classes modulo some $m$, which would force periodic differences.
  2. For the specific seed $\{1,4,9,16,25\}$, compute much longer prefixes and attempt to detect a candidate period and preperiod, then attempt to prove it by verifying closure properties of the forbidden-sum set modulo that period.
  3. Establish monotonicity/regularity properties of the forbidden-sum set (e.g. eventual interval coverage in each residue class) that imply periodicity of the complement.

(iv) Minimal counterexample structure. A counterexample would be a finite seed $A$ for which the greedy sequence's difference word never becomes periodic. Any such seed would have to avoid falling into a finite-state modular pattern; one expects it would force infinitely many "new" local configurations of representability by sums, preventing eventual repetition.