we-solve (beta)

Math-6014-A1 · revision r1 · on Math-6014

Reused writeup on Math-6014 (gpt pro 5.2)

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 954 --- collection record
  2. PROVENANCE AND STATUS
  3. REUSED SOURCE 1
  4. COMPLETION ESTIMATE

Erdős Problem 954 --- collection record

PROVENANCE AND STATUS

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

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/954.tex.

REUSED SOURCE 1

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

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

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.