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

Erdős problem 33 — live audit, an exact finite table through 101, and the uniformity wall

Access and computation date: 2026-07-27 (UTC).

Claim labels used throughout:

(a) elementary-rigorous: proved here from elementary facts.
(b) rigorous-modulo-named-theorem: rigorous assuming the cited theorem.
(c) plausible/structural-unverified: heuristic, conjectural, or a qualified

literature-search miss.

(d) computational-only: an exact finite result proved by exhaustive computation,

not an asymptotic theorem.

0. Mandatory live-page gate

I fetched the rendered live page, its “View the

LaTeX source” page, and its separate five-comment discussion thread through the Bright

Data browser path. I did this before attempting any mathematics and did not use the

tracker YAML as a statement.

Verbatim current statement

The following is copied verbatim from the live page's LaTeX rendering:

> Let $A\subset\mathbb{N}$ be such that every large integer can be written as $n^2+a$ for some $a\in A$ and $n\geq 0$. What is the smallest possible value of\[\limsup \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}?\]Is\[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{N^{1/2}}>1?\]

Status, results, comments, and participation markers

The live page showed:

status: OPEN;
claimed proofs: 0;
currently working on this problem: None;
interested in collaborating: Woett;
formalised statement: Yes;
last page edit: 27 December 2025.

“Interested in collaborating” is not the site's “currently working” marker, which

explicitly said None. Thus no mandatory stop condition applied.

The page records the following known results.

Such an $A$ is an additive complement of the squares.
(b) Erdős observed that a complement with finite limsup exists.
(b) Moser proved the second question affirmatively, initially with the explicit

lower bound $1.06$.

(b) Cilleruelo, Habsieger, and Balasubramanian–Ramana independently obtained the

current page's best lower bound

\[ \liminf_{N\to\infty}\frac{A(N)}{\sqrt N}\ge \frac4\pi =1.273239544735\ldots . \]

(b) Wouter van Doorn's linked construction has, for every $N$,

\[ \frac{A(N)}{\sqrt N}<2\phi^{5/2} =6.660381353571\ldots , \qquad \phi=\frac{1+\sqrt5}{2}. \]

The five comments were also checked:

1. Woett (12 August 2025) linked the $2\phi^{5/2}$ construction.

2. Woett (3 October 2025) said the construction was marginally sharpened to a strict

all-$N$ inequality without changing its limsup.

3. Thomas Bloom (3 October 2025) said the liminf literature had been added and that

he had not found comparable work on the limsup.

4. Sayan Dutta (6 March 2026) posted a proposed $k$-th-power generalisation with

constant $C_k(r)$, explicitly qualified by “assuming my calculations were

correct.” It is a comment, not a verified theorem or claimed proof.

5. surya161969 (25 December 2025) pointed out the typo “Ramama”; the page was

updated.

The discussion page itself warns that comments are unverified. None contains a claim

to solve problem 33, and the claimed-proof page has count zero.

1. Primary-source literature audit

The original problem and its finite companion

Erdős, [*Problems and results in additive number

theory*](https://combinatorica.hu/~p_erdos/1956-17.pdf), Colloque sur la Théorie des

Nombres, Bruxelles (1956), pp. 127–137, states the square-complement question on

p. 134. Immediately afterward he also asks for the smallest finite $t$ allowing all

integers up to $x$ to be represented by a square plus one of $t$ offsets. The exact

finite calculation below is for the natural finite truncation of the live convention,

which explicitly permits $0^2$.

The $4/\pi$ lower bound

Javier Cilleruelo,

[*The additive completion of $k$-th

powers*](https://matematicas.uam.es/~franciscojavier.cilleruelo/Papers/cuad.pdf),

J. Number Theory 44 (1993), 237–243,

DOI 10.1006/jnth.1993.1049, studies the

finite completion problem and proves

\[ |A_N|\ge \left( \frac{1}{\Gamma(2-1/k)\Gamma(1+1/k)}+o(1) \right)N^{1-1/k}. \]

For $k=2$, the gamma reflection formula gives $4/\pi$.

Laurent Habsieger,

[*On the additive completion of polynomial

sets*](https://doi.org/10.1006/jnth.1995.1039),

J. Number Theory 51 (1995), 130–135, proves the corresponding polynomial-set

bound; its displayed general constant also specialises to $4/\pi$ for squares.

The third independent source listed by the live page is R. Balasubramanian and

D. S. Ramana, Additive complements of the squares, C. R. Math. Acad. Sci. Soc.

R. Can. 23 (2001), 6–11. I verified the journal metadata and its statement through

Ramana's 2002 survey and later primary papers, but did not locate an openly accessible

author PDF of the six-page article. I therefore do not pretend to have independently

checked that proof line by line.

These are lower-bound papers. They do not supply a limsup-minimising construction.

The current upper construction

I downloaded and read van Doorn's linked note,

[*The smallest set such that every positive integer is the sum of a square and an

element from this

set*](https://github.com/Woett/Mathematical-shorts/blob/main/The%20smallest%20set%20such%20that%20every%20positive%20integer%20is%20the%20sum%20of%20a%20square%20and%20an%20element%20from%20this%20set.pdf).

It defines

\[ A=\left\{a\in\mathbb N: \phi^{2j}\le a<\phi^{2j}+2\phi^{j+1/2}-1 \text{ for some }j\ge0\right\}. \]

For $\phi^{2j}\le k<\phi^{2j+2}$, put

\[ n=\left\lfloor\sqrt{k-\phi^{2j}}\right\rfloor . \]

The note checks directly that $k-n^2$ lies in the displayed $j$-th interval.

Summing the interval lengths gives $A(x)<2\phi^{5/2}\sqrt x$.

Section 3 below rederives the constant in a form that exposes the remaining finite

subproblem.

Later representation-count work, including a post-page revision

The following primary sources concern excess representations or the possibility of

growth exactly at $4/\pi$, not a better fixed limsup constant:

Yong-Gao Chen and Jin-Hui Fang,

[*Additive complements of the

squares*](https://doi.org/10.1016/j.jnt.2017.04.016),

J. Number Theory 180 (2017), 410–422.

Yuchen Ding,

[*Green's problem on additive complements of the

squares*](https://doi.org/10.5802/crmath.107),

C. R. Math. 358 (2020), 897–900.

Yuchen Ding, Yu-Chen Sun, Li-Yuan Wang, and Yutong Xia,

[*A note on additive complements of the

squares*](https://arxiv.org/abs/2211.16810),

Discrete Math. 349 (2026), paper 114763,

DOI 10.1016/j.disc.2025.114763.

Yuchen Ding, Ben Krause, Csaba Sándor, Yu-Chen Sun, and Zihan Zhang,

[*Cross representations of additive complements of $r$-th

powers*](https://arxiv.org/abs/2512.15407), arXiv:2512.15407v6

(9 July 2026).

The last item postdates the live page's last edit. Its current Theorem 2 says that if

\[ f(n)=\#\{(a,m^2):n=a+m^2,\ a\in A,\ m\ge1\} \]

and $T(N)=\max_{h\le N}\tau(h)$, then

\[ \sum_{n\le N}f(n)-N\gg_A \frac{N^{3/4}}{\sqrt{T(N)}} =N^{3/4-o(1)}. \]

Its introduction explicitly mentions Erdős problem 33 and the same

$2\phi^{5/2}$ upper construction, but gives no new constant for the live limsup

question.

There is an important version trap here. Version 1 of arXiv:2512.15407 was titled

No exact on average additive complements of squares and claimed a linear excess

$c_A N$ infinitely often. The current v6 has a different title, five authors, and the

sublinear theorem above. The arXiv version history verifies six revisions between

17 December 2025 and 9 July 2026. I use only v6. Search-engine and ResearchGate

snippets still repeating the v1 abstract are stale and must not be used as a current

theorem.

Exact-title searches, topic searches, and the reference chains in the 2017, 2020,

2026, and current v6 papers found no primary source with a smaller fixed limsup upper

constant or a uniform improvement on $4/\pi$. (c) This is a qualified search miss,

not a proof that no unindexed result exists. It agrees with both the live OPEN status

and the current v6 paper's description.

PDF SHA-256 values for the exact files inspected:

11983cae67b4e2c95ba4adeaa82576edb9726890b8e268b1971a843dd2fe1798  Erdős 1956
d65f2212d19ffc5a3b0aa1863ab71510cadf4ba0f3354120ba5d319ff19bd236  Cilleruelo 1993
056d55f16583b6ac05e73c5f26aa9fa6a15e20188b203035147cc652e9e1ffd1  van Doorn note
33dcdf37d20c696120d3d2e1dc714880af288fa94eecf5b64c2b353e489ae5d1  arXiv:2512.15407v6

2. Exact finite computation through 101

Let

\[ \mathcal S_0=\{0^2,1^2,2^2,\ldots\} \]

and define the normalized finite completion number

\[ q(N)=\min\left\{|D|: D\subseteq\{0,\ldots,N\},\ \{0,\ldots,N\}\subseteq D+\mathcal S_0\right\}. \]

Equivalently, for the positive-integer convention

\[ t(X)=\min\left\{|B|: B\subseteq\{1,\ldots,X\},\ \{1,\ldots,X\}\subseteq B+\mathcal S_0\right\}, \]

translation by one gives the exact identity

\[ t(X)=q(X-1). \tag{2.1} \]

Indeed, $u=d+m^2$ if and only if $u+1=(d+1)+m^2$.

Complete exact table

(d) The following intervals give every value through the stated cutoff:

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

| $0$–$1$ | 1 | $1$–$2$ | 1 |

| $2$–$4$ | 2 | $3$–$5$ | 2 |

| $5$–$6$ | 3 | $6$–$7$ | 3 |

| $7$–$11$ | 4 | $8$–$12$ | 4 |

| $12$–$14$ | 5 | $13$–$15$ | 5 |

| $15$–$20$ | 6 | $16$–$21$ | 6 |

| $21$–$25$ | 7 | $22$–$26$ | 7 |

| $26$–$33$ | 8 | $27$–$34$ | 8 |

| $34$–$40$ | 9 | $35$–$41$ | 9 |

| $41$–$46$ | 10 | $42$–$47$ | 10 |

| $47$–$55$ | 11 | $48$–$56$ | 11 |

| $56$–$61$ | 12 | $57$–$62$ | 12 |

| $62$–$70$ | 13 | $63$–$71$ | 13 |

| $71$–$78$ | 14 | $72$–$79$ | 14 |

| $79$–$90$ | 15 | $80$–$91$ | 15 |

| $91$–$98$ | 16 | $92$–$99$ | 16 |

| $99$–$100$ | 17 | $100$–$101$ | 17 |

For completeness, here is one endpoint witness for every row. A witness at an

endpoint covers every earlier $N$ in its row, and its largest offset is no larger

than the row's first $N$.

| $k$ | largest $N$ coverable by $k$ offsets (through the cutoff) | witness $D$ |

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

| 1 | 1 | $\{0\}$ |

| 2 | 4 | $\{0,2\}$ |

| 3 | 6 | $\{0,2,5\}$ |

| 4 | 11 | $\{0,1,2,7\}$ |

| 5 | 14 | $\{0,2,3,4,10\}$ |

| 6 | 20 | $\{0,1,2,3,4,14\}$ |

| 7 | 25 | $\{0,2,4,5,6,8,19\}$ |

| 8 | 33 | $\{0,2,3,4,6,14,17,23\}$ |

| 9 | 40 | $\{0,2,4,6,7,8,10,12,30\}$ |

| 10 | 46 | $\{0,2,5,6,8,9,10,19,28,39\}$ |

| 11 | 55 | $\{0,1,2,4,6,10,12,23,25,29,43\}$ |

| 12 | 61 | $\{0,2,4,7,8,10,12,14,18,22,41,51\}$ |

| 13 | 70 | $\{0,2,4,6,8,10,11,12,14,16,18,20,58\}$ |

| 14 | 78 | $\{0,2,4,5,6,7,8,9,10,11,12,14,51,61\}$ |

| 15 | 90 | $\{0,2,4,6,7,8,12,14,18,26,37,43,44,49,68\}$ |

| 16 | 98 | $\{0,2,5,6,8,9,10,14,16,28,31,39,60,62,68,78\}$ |

| 17 | at least 100 | $\{0,2,5,6,8,10,12,13,14,16,18,20,24,26,43,49,71\}$ |

For example, the last row says that the positive set

\[ B=\{1,3,6,7,9,11,13,14,15,17,19,21,25,27,44,50,72\} \]

represents every integer $1\le x\le101$ as $b+m^2$. The exhaustive lower

bound at $N=99$ proves that no 16-element set can do so through $x=100$.

Why the lower bounds are exact

For a target $u$, its possible offsets are precisely

\[ H_u=\{u-j^2:0\le j\le\sqrt u\}. \]

At every search node the checker selects an uncovered $u$. Every completion must

choose some $d\in H_u$, so branching over all such $d$ is exhaustive.

The checker prunes only in the following elementary-rigorous ways.

1. Cardinality bound. If every remaining offset covers at most $g$ uncovered

targets, $r$ remaining offsets cover at most $rg$.

2. Packing bound. If selected uncovered targets have pairwise-disjoint candidate

sets $H_u$, each needs a different future offset.

3. Unit-cost dominance. If, among choices all covering the branch target, one

choice's remaining cover is contained in another's, replacing the former by the

latter never hurts.

Memoisation stores only states already proved impossible. Thus a negative answer is

an exhaustive finite proof, not a solver status trusted on faith. Witnesses are checked

separately by integer square roots in both $u=d+m^2$ and

$(u+1)=(d+1)+m^2$ coordinates.

Reproduction uses only the Python standard library:

python3 runs/erdos33_wave7b_verify.py

On this VM the complete rerun took 53.657 seconds. The hardest boundary,

$q(99)>16$, visited 1,520,017 search nodes. The witness-table checksum is

53c218ccb30ab7dd67415e2286ed823d24affa19093f0d1ce20450c924ad44cd

OR-Tools CP-SAT was used separately during candidate discovery and agreed at the

sampled optima, but neither the table nor its proof depends on OR-Tools.

3. A clean reduction to the missing asymptotic finite lemma

The finite calculation is locally sharp but does not by itself give an infinite

construction. This section identifies exactly what would make it scale.

Define

\[ c_{\rm fin}=\limsup_{N\to\infty}\frac{q(N)}{\sqrt N} \]

and let

\[ L=\inf_A\limsup_{N\to\infty}\frac{A(N)}{\sqrt N}, \]

where the infimum is over all additive complements in the live statement. Calling

$L$ an infimum avoids silently assuming that an extremiser exists.

The finite problem is a necessary local shadow

(a) For any infinite complement $A$, add the finitely many targets below its

coverage threshold to $A$. Then $A\cap[0,N]$ covers $[0,N]$, because every

representing offset is nonnegative and hence at most the target. Therefore

\[ q(N)\le A(N)+O_A(1), \]

and consequently

\[ c_{\rm fin}\le L. \tag{3.1} \]

Geometric block gluing

(a) Conversely, take integer block anchors $B_j$ with

$B_{j+1}/B_j\to R>1$, put $M_j=B_{j+1}-B_j$, and choose an optimal finite

completion $D_j$ for $[0,M_j]$. Then

\[ \mathcal A=\bigcup_j(B_j+D_j) \]

covers every block $[B_j,B_{j+1}]$. For \(B_j\le x \[ \mathcal A(x)\le\sum_{i\le j}q(M_i). \]

Writing $t=\sqrt R$, the definition of $c_{\rm fin}$ and a geometric sum give

\[ \limsup_{x\to\infty}\frac{\mathcal A(x)}{\sqrt x} \le c_{\rm fin}\, \frac{\sqrt{R(R-1)}}{\sqrt R-1} =c_{\rm fin}\,t\sqrt{\frac{t+1}{t-1}}. \tag{3.2} \]

Integer roundoff contributes only $o(1)$.

The logarithmic derivative of the last factor is

\[ \frac1t-\frac1{t^2-1} =\frac{t^2-t-1}{t(t^2-1)}. \]

It is minimised at $t=\phi$, and the factor there is $\phi^{5/2}$. Hence

\[ \boxed{c_{\rm fin}\le L\le\phi^{5/2}c_{\rm fin}.} \tag{3.3} \]

The elementary completion

\[ D_N=\{u-\lfloor\sqrt u\rfloor^2:0\le u\le N\} \]

has at most $2\sqrt N+O(1)$ distinct offsets, so $c_{\rm fin}\le2$.

Substitution in (3.3) recovers van Doorn's $2\phi^{5/2}$.

This supplies a precise upper-bound target:

> A proof that $q(N)\le(c+o(1))\sqrt N$ uniformly for some $c<2$ would

> immediately improve the live limsup upper bound to $c\phi^{5/2}$.

The exact values through $100$ are below $2\sqrt N$, but a finite prefix proves

nothing about this uniform asymptotic assertion. There is no usable dilation identity

for square translates: scaling a representation

$u=d+m^2$ does not cover all residue classes at the next scale without adding many

offsets. That is the precise obstruction to iterating the $N=100$ witness.

4. What the newest representation theorem forces — and what it does not

There is a short, rigorous-modulo-v6 consequence that quantifies the present

lower-bound wall.

Put

\[ E_A(N)=\max_{0\le x\le N} \left(A(x)-\frac4\pi\sqrt x\right). \]

The representation-count identity and a decreasing-function Riemann sum give

\[ \begin{aligned} \sum_{n\le N}f(n) &=\sum_{m\le\sqrt N}A(N-m^2)\\ &\le \frac4\pi\sum_{m\le\sqrt N}\sqrt{N-m^2} +\sqrt N\,E_A(N)\\ &\le \frac4\pi\int_0^{\sqrt N}\sqrt{N-y^2}\,dy +\sqrt N\,E_A(N)\\ &=N+\sqrt N\,E_A(N). \end{aligned} \tag{4.1} \]

Combining (4.1) with Theorem 2 of arXiv:2512.15407v6 yields

\[ E_A(N)\gg_A\frac{N^{1/4}}{\sqrt{T(N)}}=N^{1/4-o(1)}. \tag{4.2} \]

Thus for every large $N$ there is some $x\le N$ with

\[ \frac{A(x)}{\sqrt x} \ge\frac4\pi+N^{-1/4-o(1)}. \tag{4.3} \]

This is genuine growing absolute overshoot, but the normalised gap in (4.3) tends

to zero. It does not prove

$\limsup A(x)/\sqrt x>4/\pi$, much less a uniform improvement on $4/\pi$

after taking the infimum over all $A$.

Equation (4.1) also names the exact missing lower-bound input. A uniform linear

excess

\[ \sum_{n\le N}f(n)-N\ge\varepsilon N \]

for infinitely many $N$, with an absolute $\varepsilon>0$, would force

$L\ge4/\pi+\varepsilon$. The current v6 theorem is smaller by

$N^{1/4+o(1)}$. The withdrawn-as-current v1 abstract claimed a linear bound with

a complement-dependent constant, not the absolute uniform constant needed to raise

the infimum; in any event, that claim is absent from v6.

5. Verified outcome and honest wall

(d) Exact finite progress: the full table $q(0),\ldots,q(100)$, equivalently

$t(1),\ldots,t(101)$, is proved by explicit witnesses and exhaustive lower-bound

certificates.

(a) Structural progress: the finite asymptotic constant satisfies the clean

reduction $c_{\rm fin}\le L\le\phi^{5/2}c_{\rm fin}$.

(b) The newest primary preprint forces the absolute overshoot

$E_A(N)=N^{1/4-o(1)}$, but only a vanishing normalised gain.

(c) No searched primary source currently supplies either missing uniform

lemma. The live problem therefore remains open; no construction or theorem here

closes the uniform asymptotic step.

PARTIAL: exact finite square-completion numbers are verified through target 101, with a rigorous block reduction isolating the missing uniform $q(N)<(2-o(1))\sqrt N$ lemma; the live limsup constant remains open.

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