Erdoes #954 - working report - Erdős Problem a Day

Erdős problem #954 — wave 7w

Research and live-page access date: 2026-07-28 UTC.

Outcome: partial progress, not a solution. The mandatory live-page gate

passed. I prove an exact regulator/drawdown reformulation, give several

elementary identities and bounds, and exhaustively compute the sharp error on

every integer $1\le x\le 10^8$ using two independent exact counting paths.

Claim labels used below:

[a] elementary-rigorous — proved here from the definition;
[b] rigorous-modulo-named-theorem — conditional only on the explicitly

named theorem;

[c] plausible/structural-unverified;
[d] computational-only — finite, exhaustive, deterministic computation.

No finite computation is treated as evidence that an asymptotic statement is

proved or disproved.

0. Mandatory live-page gate

I used the Bright Data browser route, not datacenter curl, to read all three

live routes:

<https://www.erdosproblems.com/954>
<https://www.erdosproblems.com/latex/954>
<https://www.erdosproblems.com/forum/discuss/954>

The live findings were:

status: OPEN;
claimed proofs: 0;
“Currently working on this problem”: None;
“Interested in collaborating”: None;
“This problem looks difficult”: None;
“This problem looks tractable”: None;
both formalisation-worker markers: None;
last edited: 25 January 2026;
related OEIS sequence: A390642;
formalised statement: No.

Thus the required stop condition was not triggered.

Verbatim current statement

The following is copied verbatim from the live LaTeX-source route:

> Let $0=a_0<a_1<a_2<\cdots$ be the sequence of integers defined by $a_0=0$ and $a_1=1$, and $a_{k+1}$ is the smallest integer $n$ for which the number of solutions to $a_i+a_j \leq n$ (with $0\leq i\leq j\leq k$ and $j\geq 1$) is $<n$.

> Is the number of solutions to $a_i+a_j \leq x$ equal to $x+O(x^{1/4+o(1)})$?

Results listed on the live page

The page says:

1. Rosen constructed the sequence.

2. The number of solutions is always at least $x$ by construction.

3. Erdős and Rosen could not prove even an upper bound

$(1+o(1))x$.

4. The sequence starts

\[ 0,1,3,5,9,13,17,24,31,38,45,\ldots. \]

These are transcriptions of the live page, not claims that its literature list

is complete.

All three live comments

The page warns that comments are user-supplied and unverified.

1. Giorgos Kalogeropoulos, 14 November 2025. He reports submitting what

became OEIS A390642 and lists its first 30 positive terms.

2. Przemek Chojecki, 23 January 2026. Addressing the then-uncorrected

formulation without $a_0=0$, he derives

$F(a_m)=a_m-m$, hence an error of size $m\gg\sqrt{a_m}$, which would

falsify the displayed $x^{1/4+o(1)}$ conclusion for that old counting

convention. The thread is explicitly annotated “The site has been updated

to address this comment.”

3. Thomas Bloom, 25 January 2026. He explains that Erdős gave two

equivalent ways to construct the same positive sequence, but switching

definitions also changes which representations must be counted in the

conclusion. The live page now includes $a_0=0$.

None is marked as a proof claim for the corrected live statement. Section 2

below independently explains exactly why the correction removes the apparent

counterexample.

1. Literature audit

Primary source

I inspected the source PDF cited by the live page:

P. Erdős, “Problems and results on combinatorial number theory III,” in

Number Theory Day (New York, 1976), Lecture Notes in Mathematics 626,

Springer, 1977, pp. 43–72, especially p. 71:

<https://www.renyi.hu/~p_erdos/1977-27.pdf>.

The source identifies Kenneth Rosen, describes the two defining conventions,

states Rosen's hoped-for error at the $1/4$ exponent, and says that Erdős and

Rosen could not prove an $x+o(x)$ upper bound. This verifies that the live

problem is genuinely the Rosen construction and not merely a similar OEIS

sequence.

The source says the construction would make the Erdős–Fuchs theorem

essentially sharp. The named primary source is:

P. Erdős and W. H. J. Fuchs, “On a Problem of Additive Number Theory,”

Journal of the London Mathematical Society s1-31 (1956), 67–73,

<https://doi.org/10.1112/jlms/s1-31.1.67>.

That theorem rules out an error

\[ o\!\left(x^{1/4}(\log x)^{-1/2}\right) \]

for a linear cumulative representation function. It is a lower-obstruction

theorem, not an upper bound for this greedy sequence. [b: Erdős–Fuchs]

Current auxiliary data

The approved OEIS entry <https://oeis.org/A390642> gives 55 terms, a

Mathematica implementation, and the conjecture

\[ a_n\sim \frac{\pi}{8}n^2. \]

It cites only Erdős problem #954 for the question. The asymptotic is labelled

as a conjecture on OEIS and is used nowhere below as a theorem. [c]

I searched exact phrases from the 1977 source, the initial term string, the

identifier A390642, combinations of “Kenneth Rosen” with the defining

inequality, and arXiv-restricted versions of those queries. The only directly

relevant hits were the original Erdős paper, the live problem/thread, and

OEIS. I found no later primary paper studying this exact greedy construction.

This is an honest report of search misses, not a proof that no such paper

exists.

2. Corrected count and the old-comment issue

For integer $x\ge1$, define

\[ \begin{aligned} A(x)&=\#\{j\ge1:a_j\le x\},\\ B(x)&=\#\{(i,j):1\le i\le j,\ a_i+a_j\le x\},\\ R(x)&=\#\{(i,j):0\le i\le j,\ j\ge1,\ a_i+a_j\le x\}. \end{aligned} \]

Here the conclusion's phrase “number of solutions” carries the explicit index

convention from the defining sentence; this is also the convention used by

the live page's lower-bound remark and correction thread.

The corrected count therefore satisfies the exact identity

\[ \boxed{R(x)=A(x)+B(x)}. \tag{1} \]

The $A(x)$ summand consists precisely of the zero-pairs

$(a_0,a_j)$. [a]

For a finite prefix $a_0,\ldots,a_k$, write $R_k(x)$ for the analogous

finite count. Let $m=a_{k+1}$. Minimality, monotonicity, and integrality give

\[ R_k(m-1)\ge m-1,\qquad R_k(m)and hence

\[ \boxed{R_k(m)=m-1}. \tag{2} \]

At $x=m$, the only newly contributing pair involving $a_{k+1}$ is

$(a_0,a_{k+1})$; every positive pair involving it exceeds $m$. Therefore

\[ \boxed{R(a_n)=a_n\quad(n\ge1)}. \tag{3} \]

For \(a_k

minimality says $R(x)=R_k(x)\ge x$. Thus

\[ \boxed{D(x):=R(x)-x\ge0\ \text{for every integer }x\ge1,} \qquad \boxed{D(a_n)=0}. \tag{4} \]

All assertions (2)–(4) are [a].

Combining (1) and (3) yields

\[ \boxed{B(a_n)=a_n-n}. \tag{5} \]

This is exactly the identity in Chojecki's comment for the positive-only

count. The corrected statement adds the $n$ zero-pairs, turning

$a_n-n$ into $a_n$. Thus the old comment does not disprove the current

problem. [a]

3. Exact regulator/drawdown reduction

Set

\[ H(x)=x-B(x),\qquad H^*(x)=\max_{1\le t\le x}H(t). \]

Proposition

For every integer $x\ge1$,

\[ \boxed{A(x)=H^*(x)} \tag{6} \]

and

\[ \boxed{D(x)=H^*(x)-H(x)}. \tag{7} \]

Consequently, the positive sequence terms are exactly the strict record times

of $H$.

Proof

From $D(t)=A(t)+B(t)-t\ge0$, one has

\[ A(t)\ge t-B(t)=H(t). \]

Since $A$ is nondecreasing, $A(x)\ge H(t)$ for every $t\le x$, so

$A(x)\ge H^*(x)$.

Let $m=A(x)$, so \(a_m\le x \[ 0=D(a_m)=A(a_m)+B(a_m)-a_m, \]

and hence

\[ H(a_m)=a_m-B(a_m)=A(a_m)=m=A(x). \]

Thus $H^*(x)\ge A(x)$, proving (6). Substitution into

$D(x)=A(x)-H(x)$ proves (7).

Finally,

\[ H(x)-H(x-1)=1-\bigl(B(x)-B(x-1)\bigr)\le1. \]

The running maximum can therefore rise by at most one at a time. By (6), it

rises exactly when $A$ rises, i.e. exactly at $x=a_n$. ∎

This proposition is [a]. It gives a clean equivalent form of the open

question:

> Missing drawdown lemma. Prove

> \[ > \max_{t\le x}\bigl(t-B(t)\bigr)-\bigl(x-B(x)\bigr) > =O\!\left(x^{1/4+o(1)}\right) > \]

> for the self-consistent record set generated by (6).

This is not just a restatement in the original variables: it separates the

positive-positive convolution $B$ from the minimal monotone regulator $A$

and identifies the desired error as a one-sided drawdown rather than an

ordinary pointwise convolution error.

Two elementary corollaries

At $a_n$, no positive pair involving $a_n$ contributes, so (5) and the

$\binom n2$ available positive pairs among

$a_1,\ldots,a_{n-1}$ give

\[ a_n-n=B(a_n)\le\binom n2. \]

Therefore

\[ \boxed{a_n\le\frac{n(n+1)}2}. \tag{8} \]

Equivalently,

\[ \boxed{ A(x)\ge \left\lfloor\frac{\sqrt{8x+1}-1}{2}\right\rfloor. } \tag{9} \]

Also, immediately after $a_n$, the prefix has the new representation

$a_1+a_n=a_n+1$, so the next defining failure cannot occur there:

\[ \boxed{a_{n+1}\ge a_n+2}. \tag{10} \]

These bounds are all [a]. The verifier checks (8) and (10) on every

computed term.

4. Exact computation

The standalone verifier is

erdos954_wave7w_reverify.py.

It uses only Python's standard library and integer arithmetic.

First path: online event walk

Let

\[ r(x)=\#\{(i,j):0\le i\le j,\ j\ge1,\ a_i+a_j=x\}. \]

Then

\[ D(x)-D(x-1)=r(x)-1. \tag{11} \]

The program scans $x=1,2,\ldots,X$, storing exact future pair-sum

multiplicities. Whenever the finite-prefix walk would first become $-1$,

the program declares $x$ to be the next term, adds the zero-pair

$(0,x)$, which restores the global walk to zero, and schedules every new

positive pair $x+a_i$.

Second and third paths

The program separately:

1. constructs the first 55 positive terms literally from the defining

minimum by sorting every finite-prefix pair-sum multiset and scanning

every candidate $n$ from 1;

2. checks those terms against all 55 approved OEIS values;

3. discards the online event table;

4. rebuilds a fresh histogram by a nested loop over every pair in the

completed term list;

5. rescans every $x\le X$, rechecking nonnegativity, all term zeros,

(6)–(7), the strict-record characterization, every checkpoint, and the

total pair count.

Thus the large table is not trusted from a single generator. [d]

Sharp exhaustive table

Let

\[ M(X)=\max_{1\le x\le X}D(x). \]

“First/last maximizer” means the first and last integers at which the displayed

running maximum is attained.

| $X$ | $A(X)$ | last $a_n\le X$ | $D(X)$ | $M(X)$ | first maximizer | last maximizer |

|---:|---:|---:|---:|---:|---:|---:|

| $10$ | 4 | 9 | 1 | 1 | 6 | 10 |

| $10^2$ | 15 | 97 | 3 | 4 | 62 | 62 |

| $10^3$ | 49 | 1,000 | 0 | 11 | 498 | 938 |

| $10^4$ | 159 | 9,953 | 43 | 62 | 8,981 | 8,982 |

| $10^5$ | 504 | 98,969 | 91 | 273 | 96,513 | 96,520 |

| $10^6$ | 1,593 | 989,393 | 579 | 1,020 | 737,274 | 737,274 |

| $10^7$ | 5,039 | 9,987,363 | 1,805 | 6,093 | 9,720,575 | 9,720,575 |

| $10^8$ | 15,951 | 99,434,588 | 20,752 | 46,462 | 94,555,728 | 94,555,729 |

Every entry is [d]. In particular, the exact finite result is

\[ \boxed{0\le R(x)-x\le46\,462\qquad(1\le x\le10^8,\ x\in\mathbb Z),} \tag{12} \]

and the upper equality occurs exactly at

\[ \boxed{x=94\,555\,728,\ 94\,555\,729}. \tag{13} \]

This is sharp for the stated finite interval. It says nothing uniform as

$X\to\infty$.

At the final endpoint the two paths independently count

\[ R(10^8)=100\,020\,752, \]

of which $15\,951$ are zero-pairs. The comma-separated positive-term list

has SHA-256

07a12f9fab660653b9b52256219ddec6a4dd1807bf92ed407e596829370dcd70

All three assertions in this paragraph are [d].

5. Why the standard route stalls

If one assumes only the OEIS leading-order guess

\[ a_n\sim c n^2, \]

then an area calculation in the lattice wedge

$0\le i\le j$ suggests

\[ R(x)\sim \frac{\pi}{8c}x, \]

and hence $c=\pi/8$. This explains the OEIS constant. It is only a

leading-order heuristic for the actual greedy sequence. [c]

The desired exponent is much subtler. For an exactly quadratic model, the

remaining pair count resembles a lattice-point problem in a circular wedge;

the conjectural Gauss-circle scale in radius

$\sqrt{x}$ is $x^{1/4+o(1)}$. But the actual $a_n$ are neither known to

obey the leading asymptotic nor controlled to the much finer stability scale

needed to transfer a circle estimate. Straight-boundary terms and perturbations

of the individual $a_n$ can already create errors of order $\sqrt{x}$

unless they cancel. This analogy and cancellation requirement are [c],

not a proof route currently completed here.

The exact obstruction is therefore:

1. even $R(x)=(1+o(1))x$ is not known for this sequence (as the live page

records);

2. (6) controls only the running maximum of $H=x-B$, while the target needs

every drawdown from that maximum to be $x^{1/4+o(1)}$;

3. Erdős–Fuchs supplies a lower obstruction for all additive sets, not the

required upper control for this self-generated set;

4. no finite extension of (12) can establish the uniform asymptotic.

Thus the missing item is a genuinely uniform drawdown/stability lemma, not a

larger finite search.

6. Reproduction and cost

From the repository root:

python3 -m py_compile runs/erdos954_wave7w_reverify.py
python3 runs/erdos954_wave7w_reverify.py --limit 100000000

The $10^8$ run completed successfully with status: PASS. The measured

large run took 109.7 CPU-seconds and 409,696 KB peak resident memory before

the final extra drawdown assertions were added; those assertions were then

rerun through $10^6$ and passed. The generating and independent counting

paths themselves were unchanged. [d]

The algorithm takes $O(X+R(X))$ integer-event work and $O(X)$ memory. On

the observed range, a linear extrapolation to $10^9$ would require roughly

0.3–0.4 single-core hours and about 4 GB RAM; $10^{10}$ would be roughly

3–4 core-hours and 40 GB. These are engineering estimates [c], not

mathematical complexity bounds uniform over unknown future behavior. I did

not run either extension.

PARTIAL: proved the exact regulator/drawdown reduction and certified the sharp bound $0\le R(x)-x\le46{,}462$ for every integer $x\le10^8$; the unresolved step is a uniform $x^{1/4+o(1)}$ drawdown lemma.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger