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

1. 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.

1. 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.”

1. 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

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

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

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

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

and hence

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

For \(a_k<x<a_{k+1}\), no later term can contribute and the defining minimality says \(R(x)=R_k(x)\ge x\). Thus

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

Combining (1) and (3) yields

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

Proposition

For every integer \(x\ge1\),

and

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

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<a_{m+1}\). At \(t=a_m\), (3) gives

and hence

Thus \(H^*(x)\ge A(x)\), proving (6). Substitution into \(D(x)=A(x)-H(x)\) proves (7).

Finally,

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

Therefore

Equivalently,

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:

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

Then

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;

1. checks those terms against all 55 approved OEIS values;
2. discards the online event table;
3. rebuilds a fresh histogram by a nested loop over every pair in the

completed term list;

1. 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

“First/last maximizer” means the first and last integers at which the displayed running maximum is attained.

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

and the upper equality occurs exactly at

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

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

then an area calculation in the lattice wedge \(0\le i\le j\) suggests

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);

1. (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)}\);

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

required upper control for this self-generated set;

1. 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.