gpt pro 5.2 attempt on Math-6014

Erdos Problem 954.

1) FORMAL RESTATEMENT. Define a strictly increasing sequence of integers $(a_k)_{k\ge 1}$ by $a_1:=1$ and, for each $k\ge 1$, \[ a_{k+1}:=\min\{n\in\mathbb{N}: S_k(n) < n-k\}, \] where \[ S_k(n):=\#\{(i,j):1\le i\le j\le k,\ a_i+a_j\le n\}. \] (Here solutions are counted with the convention $i\le j$.) Let \[ S(n):=\#\{(i,j):1\le i\le j,\ a_i+a_j\le n\}\qquad(n\in\mathbb{N}). \] The problem asks whether \[ S(x)=x+O\left(x^{1/4+o(1)}\right)\qquad(x\to\infty) \] (where $x$ may be restricted to integers).

2) QUICK LITERATURE/CONTEXT CHECK. The problem file states that the sequence was constructed by Rosen and that Erdős and Rosen could not prove whether $S(x)\le (1+o(1))x$. The file also states the conjectural error term $O(x^{1/4+o(1)})$.

3) ATTACK PLAN. (A) Extract identities forced by the greedy definition, especially at the special points $x=a_k$. (B) Convert the inequality defining $a_{k+1}$ into two-sided bounds for $S(x)-x$ in terms of $k$ and the counting function $k(x):=\max\{k: a_k\le x\}$. (C) Use computations for small $x$ to see the size and sign of $S(x)-x$.

4) WORK.

FAST REALITY CHECK (small $x$; exact computation). I generated the sequence by brute force from the defining recursion and computed $S(x)$ for several $x$. The first 20 terms are \[ 1,3,5,9,13,17,24,31,38,45,53,61,75,87,97,112,124,139,147,175. \] For selected $x$: \[ \begin{array}{c|c|c} x & S(x) & x-S(x)\\\hline 10 & 7 & 3\\ 20 & 15 & 5\\ 50 & 41 & 9\\ 100 & 88 & 12\\ 200 & 183 & 17\\ 500 & 474 & 26\\ 1000 & 951 & 49\\ 2000 & 1941 & 59\\ 5000 & 4902 & 98\\ 10000 & 9884 & 116\\ 20000 & 19801 & 199 \end{array} \] In particular, with the $i\le j$ convention, the remark in the problem file that $S(x)$ is always at least $x$ is false already at $x=2$ since $S(2)=1$. (What “at least $x$” means might depend on a different counting convention; I keep the convention $i\le j$ because it is used in the recursive definition.)

Lemma 954.1 (Lower bound below the next greedy jump; exact value at the jump). Fix $k\ge 1$ and set $m:=a_{k+1}$. Then:

(i) For every integer $n<m$ we have $S(n)=S_k(n)\ge n-k$.

(ii) One has the exact identities \[ S(m)=S_k(m)=m-k-1\qquad\text{and}\qquad S(m-1)=S_k(m-1)=m-k-1. \]

Proof. Because the sequence is increasing, if $n<m=a_{k+1}$ then $a_{k+1}>n$ and hence any pair $(i,j)$ with $j\ge k+1$ satisfies $a_i+a_j\ge a_1+a_{k+1}>n$, so it is not counted in $S(n)$. Thus $S(n)=S_k(n)$ for all $n<m$.

By definition, $m$ is the smallest integer such that $S_k(m)<m-k$. Therefore for every $n<m$ we must have $S_k(n)\ge n-k$. This proves (i).

For (ii), first note that $S_k(m)<m-k$ implies $S_k(m)\le m-k-1$ since $S_k(m)$ is an integer. Also, by (i) applied to $n=m-1$ we have $S_k(m-1)\ge (m-1)-k=m-k-1$. Monotonicity of $S_k(\cdot)$ in $n$ gives $S_k(m)\ge S_k(m-1)\ge m-k-1$. Combining this lower bound with the upper bound $S_k(m)\le m-k-1$ forces $S_k(m)=m-k-1$ and then also $S_k(m-1)=m-k-1$. Finally, $S(m)=S_k(m)$ because any pair using $a_{k+1}=m$ has sum at least $a_{k+1}+a_1=m+1>m$, so no such pair is counted at level $m$. This proves (ii). $\square$

Corollary 954.2. For every $n\ge 1$, \[ S(a_n)=a_n-n. \]

Proof. Apply Lemma 954.1(ii) with $k=n-1$ and $m=a_n$. $\square$

Lemma 954.3 (Quadratic upper bound on $a_{k}$). For every $k\ge 1$, \[ a_{k+1}\le \frac{k(k+3)}{2}+1. \]

Proof. For any integer $n$ we have the trivial bound $S_k(n)\le \binom{k+1}{2}=k(k+1)/2$ because there are only $\binom{k+1}{2}$ pairs $(i,j)$ with $1\le i\le j\le k$. If $n:=\frac{k(k+3)}{2}+1$, then \[ n-k=\frac{k(k+1)}{2}+1>\frac{k(k+1)}{2}\ge S_k(n), \] so $S_k(n)<n-k$. By minimality of $a_{k+1}$, we must have $a_{k+1}\le n$. $\square$

5) VERIFICATION. • Lemma 954.1: the only nontrivial points are (a) $S(n)=S_k(n)$ for $n<a_{k+1}$, which follows from monotonicity of $a_i$ and positivity of $a_1$, and (b) the squeeze $m-k-1\le S_k(m)\le m-k-1$. • Lemma 954.3: uses only the bound $S_k(n)\le \binom{k+1}{2}$. • Computations were cross-checked against the first terms given in the problem file.

6) FINAL. UNRESOLVED. (i) Strongest proved partial result: For all $n\ge 1$, $S(a_n)=a_n-n$; moreover, if $a_k\le x<a_{k+1}$ then $S(x)=S_k(x)\ge x-k$. (ii) First gap: obtain an upper bound of the form $S(x)\le x+O(x^{1/4+o(1)})$ (or even $S(x)\le (1+o(1))x$), i.e. control how often many pair-sums fall below $x$. (iii) Top 3 next moves: $1$ Prove an asymptotic for the counting function $k(x):=\max\{k: a_k\le x\}$ (even a bound $k(x)=O(x^{1/2-\varepsilon})$ would sharpen the lower bound $S(x)\ge x-k(x)$). $2$ Study the increment process $S(x+1)-S(x)$ and try to show it is typically $0$ or $1$ with controlled exceptions; Lemma 954.1(ii) shows $S$ does not jump at $x=a_{k+1}$. $3$ Compute $S(x)-x$ for much larger $x$ to guess whether the typical deficit is $\Theta(\sqrt{x})$, $\Theta(x^{1/4})$, or something else; then try to prove the corresponding bound. (iv) Minimal counterexample structure: an integer $x$ for which $|S(x)-x|\gg x^{1/4}$; by Lemma 954.1 this must be due to a large positive deviation (too many pairs) or a deficit much larger than $k(x)$.