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

Erdős problem 32 — live-page audit, exact finite covers, and the cross-scale barrier

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, verified theorem.
(c) plausible/structural-unverified: heuristic, conjectural, or a qualified search miss.
(d) computational-only: an exact finite calculation, not an asymptotic theorem.

0. Mandatory live-page gate

I fetched the rendered live page through the Bright Data browser path, then separately fetched its LaTeX rendering, dynamically loaded bibliography entries, and discussion thread. I did not infer the statement or status from the stale tracker metadata.

Verbatim current statement

The following is copied verbatim from the live page's “View the LaTeX source” rendering:

Is there a set $A\subset\mathbb{N}$ such that\[\lvert A\cap\{1,\ldots,N\}\rvert = o((\log N)^2)\]and such that every large integer can be written as $p+a$ for some prime $p$ and $a\in A$?
Can the bound $O(\log N)$ be achieved? Must such an $A$ satisfy\[\liminf \frac{\lvert A\cap\{1,\ldots,N\}\rvert}{\log N}> 1?\]

Status, known results, comments, and participation markers

The live page at erdosproblems.com/32 showed:

status: OPEN — $50 (so the stale “no prize” metadata is not authoritative);
claimed proofs: 0;
interested in collaborating: None;
currently working on this problem: None;
formalised statement: Yes;
last page edit: 23 January 2026.

Thus no mandatory stop condition applied.

The page gives the following results as ground truth.

(b) Erdős [Er54] constructed a full additive complement with

$A(N)\ll(\log N)^2$, improving Lorentz's $\ll(\log N)^3$.

(b) For almost all target integers, Wolke obtained

$(\log N)^{1+o(1)}$, Kolountzakis obtained $O(\log N\log\log N)$, and Ruzsa obtained $O(\omega(N)\log N)$ for every $\omega(N)\to\infty$.

(b) Ruzsa proved that every full complement satisfies

\[ \liminf_{N\to\infty}\frac{A(N)}{\log N}\ge e^\gamma =1.7810724179\ldots . \]

The separate discussion thread contained one comment, by msellke on 13 October

It records the Kolountzakis and Ruzsa almost-all refinements, notes Ruzsa's

conjectures about lower bounds in the almost-all setting, and says the site was updated to incorporate the comment. The thread itself warns that comments are unverified. There was no claim of a proof or current worker hidden in the thread.

1. Primary-source literature audit

I checked the primary papers rather than treating search snippets as theorems.

Full coverage

Paul Erdős, Some results on additive number theory, Proc. Amer. Math. Soc. 5 (1954), 847–853: author archive PDF.

(b) Theorem 1 states exactly that there is a sequence $B$ with

$B(x)<C(\log x)^2$ for which every sufficiently large integer is $p+b$.

Its proof selects $C(\log n)^2$ shifts in a block, uses the

Hoheisel–Ingham short-interval prime theorem to give each target many candidate shifts, and takes a union bound over all targets. This is the original appearance of the logarithmic union-bound cost discussed below.

Almost-all coverage and the lower bound

Mihail N. Kolountzakis, On the additive complements of the primes and sets of similar growth, Acta Arith. 77 (1996), 1–8, DOI 10.4064/aa-77-1-1-8.

(b) Theorem 1 constructs an almost complement of size

$O(\log x\log\log x)$.

The same paper stresses that Erdős's general growth-only method cannot be improved

for arbitrary “prime-like” sets; genuine arithmetic information about the primes is required.

Imre Z. Ruzsa, On the additive completion of primes, Acta Arith. 86 (1998), 269–275, DOI 10.4064/aa-86-3-269-275.

(b) Theorem 1(a) gives $B(x)=O(\log x)$ while covering lower density

$>1-\varepsilon$; Theorem 1(b) gives $B(x)=O(\omega(x)\log x)$ and density $1$.

(b) Theorem 2 gives the stronger form behind the live-page lower bound: if the

exceptional count is at most $x^{1-\log\log\log x/\log\log x}$, in particular if it is finite, then $\liminf B(x)/\log x\ge e^\gamma$.

(c) Ruzsa's Conjecture 2 says that a full complement should actually satisfy

$B(x)/\log x\to\infty$. This is a conjecture, not a known negative answer to the live page's $O(\log x)$ question.

Later related results do not solve the one-shift question

V. H. Vu, High Order Complementary Bases of Primes, Integers 2 (2002), A12:

(b) Vu constructs $X(x)=O(\log x)$ such that every sufficiently large

integer is $p+x_1+x_2$. This is a two-elements-of-$X$ theorem, not $p+x$.

Li-Xia Dai and Hao Pan, The additive complements of primes and Goldbach's problem, Acta Arith. 162 (2014), 209–221, DOI 10.4064/aa162-3-1; preprint arXiv:1101.1653.

The paper explicitly says the existence of a one-shift complement

$A(x)=O(\log x)$ is unknown.

(b) Its Theorem 1.1 instead gives a sparse prime set $A$ with

$A(x)=O(\log x)$ such that every sufficiently large odd integer is $a_1+a_2+p$; Theorem 1.2 is an almost-all $b+p$ result.

Exact-title searches, topic searches, and forward-citation checks for the Ruzsa, Kolountzakis, and Dai–Pan papers found no later primary source claiming a full one-shift improvement. The 2025 paper by Patil and Mohan that cites this literature studies complements constrained to lie outside the original set, not a thinner complement to the primes. (c) This is an honest search miss, not proof that no unindexed result exists. It agrees with the live page's open status as of the access date.

Downloaded primary-source SHA-256 checksums:

d694181393589ab735574099f1538d2dbb66d9cb9c9f564eca07e39ab41ff5c7  Erdős 1954
856492d3719a6b5537d055e0e61f6035a505e046b742ebf2f6ae7e80357dd842  Kolountzakis 1996
56d1671c747c7f125fce460544174f5c35685c6c6da0c9b854ce7d3a07feffac  Ruzsa 1998
d9e289d697eedc3e0074534c235566d14589b561e9343b03c443f71eee174877  Vu 2002
9ee5e72efda60b0d9f63ce953f3b82eb6ab19820d646250c08337203e2be6e2a  Dai–Pan 2014
e74307644b97ff69d6cd0e6a294153bdd62e572343271afd31ba8b25f7ad90f6  arXiv:1101.1653 PDF

2. An exact finite model

For $N\ge3$, define

F(N)=\min\left\{|C|: C\subseteq\{0,\ldots,\lfloor(N-1)/2\rfloor\},\ \forall\,1\le m\le N\ \exists c\in C\text{ with }m+c\in\mathbb P \right\}.

This is not silently being promoted to the original asymptotic problem. It is the exact finite optimization problem for a particularly natural “fresh shell” construction.

Exact equivalence to a prime-plus-shift block

(a) Put

B_N=\{N-c:c\in C\}\subset(N/2,N].

For $n=N+m$, $1\le m\le N$, and $b=N-c$,

\[ n-b=(N+m)-(N-c)=m+c. \]

Consequently,

\{N+1,\ldots,2N\}\subseteq\mathbb P+B_N \quad\Longleftrightarrow\quad \forall m\le N\ \exists c\in C:\ m+c\text{ is prime}.

Exact table

(d) The following equalities are exact. The displayed $C$ proves the upper bound, and the from-scratch exhaustive search rules out every $C$ with one fewer element. The last column $g$ is the smallest size of a consecutive offset set $\{0,\ldots,g-1\}$ that covers; nonconsecutive offsets substantially improve it at $N=128$.

$N$	exact $F(N)$	one optimal offset set $C$	consecutive $g$
4	2	$\{0,1\}$	2
8	3	$\{0,1,3\}$	4
12	4	$\{2,3,4,5\}$	4
16	4	$\{2,3,4,5\}$	4
20	4	$\{0,1,2,3\}$	4
24	5	$\{0,2,3,5,7\}$	6
32	6	$\{1,2,3,4,5,6\}$	6
40	6	$\{13,14,15,16,17,18\}$	6
48	6	$\{15,17,18,19,20,22\}$	6
64	6	$\{1,2,3,4,5,6\}$	6
80	6	$\{2,3,4,5,6,7\}$	6
96	8	$\{2,4,5,6,7,8,9,11\}$	8
128	8	$\{2,4,13,20,29,36,45,47\}$	14

The corresponding explicit additive shifts are always $B_N=\{N-c:c\in C\}$. For example, the final row gives

B_{128}=\{81,83,92,99,108,115,124,126\},

and the checker directly exhibits at least one prime-plus-$b$ representation for each $129\le n\le256$.

Why the lower-bound computation is a proof

(a) Each offset $c$ is stored as the bit set

R_c=\{m\in[1,N]:m+c\text{ is prime}\}.

At any search node, choose an uncovered $m$. Every possible completion must select one of the $R_c$ containing $m$, so branching over those sets is exhaustive. A branch is discarded only if:

its remaining coverage is contained in another unit-cost choice's remaining

coverage; or

even the sum of the $k$ largest remaining coverage cardinalities is smaller than

the number of uncovered points.

Both prunes preserve completeness. Memoisation only caches already-proved impossible states. The standard-library checker also independently sieves the primes, verifies each witness in both $(m,c)$ and $(n,p,b)$ coordinates, and computes the consecutive-offset bound. As an implementation cross-check, I separately formulated all 13 cases as Boolean covering models; OR-Tools CP-SAT returned the same optima. The report does not rely on CP-SAT.

Reproduction:

python3 runs/erdos32_wave7a_verify.py

The complete run took about 8 seconds on this VM. The largest lower-bound search, $F(128)>7$, visited 331,050 nodes. Its witness-table checksum is

9b7a518ba20b831e9c951317cdcb5df33372c53cd806d300e5bcb84984c87fd9

A simple prime-gap construction

Let $q(m)$ be the least prime at least $m$, and put

g(N)=1+\max_{1\le m\le N}(q(m)-m).

(a) If $g(N)\le\lceil N/2\rceil$, then $C=\{0,\ldots,g(N)-1\}$ is admissible: $q(m)=m+c$ for $0\le c<g(N)$. This explains the last column. It is only an upper bound; the nonconsecutive $N=128$ cover has size $8$, versus $g(128)=14$.

3. A rigorous barrier to independent fresh-shell constructions

The finite calculation is accompanied by an asymptotic diagnosis; this is the part that says exactly why a natural attack does not scale.

Every fresh shell costs asymptotically at least $\log N$

For a fixed offset $c$,

|R_c|=\pi(N+c)-\pi(c),\qquad 0\le c<N/2.

(b), modulo the prime number theorem,

\max_{0\le c<N/2}|R_c|=(1+o(1))\frac{N}{\log N}.

Here is the uniformity argument. For $c\le\delta N$,

|R_c|\le\pi((1+\delta)N) \le(1+\delta+o(1))\frac{N}{\log N}.

For $\delta N\le c\le N/2$, the prime number theorem is uniform on the compact scaled interval $[\delta N,3N/2]$, and

\pi(N+c)-\pi(c) =\int_c^{N+c}\frac{dt}{\log t}+o(N/\log N) =(1+o_\delta(1))\frac{N}{\log N}.

Let $\delta\to0$; the reverse bound follows already from $c=0$ and $\pi(N)\sim N/\log N$.

Since $N$ points must be covered and each selected $R_c$ covers at most the displayed maximum,

\boxed{F(N)\ge(1-o(1))\log N.}

Consequence for dyadic concatenation

For $N=2^j$, every $B_N$ lies in the disjoint shell $(2^{j-1},2^j]$ and covers the next block $(2^j,2^{j+1}]$. If one builds $A$ by asking each fresh shell to cover its next block by itself, then (b)

A(2^J) =\sum_{j\le J}|B_{2^j}| \ge(1-o(1))\sum_{j\le J}\log(2^j) =\left(\frac{1}{2\log2}+o(1)\right)(\log 2^J)^2.

Thus even optimal fresh-shell covers cannot yield $o((\log x)^2)$. This does not prove the original problem impossible: it proves that an improvement must make old and new shifts cooperate across scales, rather than paying for an independent cover at every scale.

4. Why the scale-free independent random model also stalls

There is a second precise version of the same wall. Fix $\kappa>0$, and independently select every positive integer $a$ with probability

q_a=\min(1/2,\kappa/a).

Then

\mathbb E|A\cap[1,N]|=\kappa\log N+O_\kappa(1).

For a target $n$, let

\mu_n=\sum_{\substack{a\le n-2\\n-a\ {\rm prime}}}q_a

be its expected number of representations.

(b), modulo the prime number theorem,

\frac1N\sum_{n\le N}\mu_n=\kappa+o(1).

Indeed, changing the finitely many truncated $q_a$'s contributes $o(1)$, while interchanging the sums gives

\frac{\kappa}{N}\sum_{a\le N-2}\frac{\pi(N-a)}a.

The inner sum is $N(1+o(1))$: the range $a\le N/\log N$ contributes $N(1+o(1))$ by the prime number theorem; the ranges $N/\log N<a\le N/2$ and $a>N/2$ are $o(N)$ by the standard $\pi(x)\ll x/\log x$ consequence.

Markov's inequality therefore leaves at least $(1/2-o(1))N$ targets with $\mu_n\le2\kappa+o(1)$. Since $q_a\le1/2$ and $\log(1-t)\ge-2t$ on $[0,1/2]$, each such target has

\Pr(n\notin\mathbb P+A) =\prod_{n-a\ {\rm prime}}(1-q_a) \ge \exp(-2\mu_n) \ge e^{-4\kappa-o(1)}.

Consequently,

\boxed{\mathbb E\,|\{n\le N:n\notin\mathbb P+A\}| \ge(1/2-o(1))e^{-4\kappa}N.}

This is a lower bound on the expectation, not a proof that an exceptionally lucky sample cannot cover everything. (b) It rigorously shows why the basic independent first-moment argument with fixed $\kappa$—the one giving expected size $O(\log N)$—still expects linearly many misses and cannot close the problem. (c) Letting $\kappa$ grow slowly is exactly the scale suggested by Ruzsa's $\omega(N)\log N$ almost-all theorem; making a naive union bound handle every target pushes the size back toward $\log^2 N$.

As a numerical check, the verifier recomputes

\frac1N\sum_{a\le N-2}\frac{\pi(N-a)}a =1.1090347825,\ 1.0905839515,\ 1.0699894289

at $N=10^3,10^4,10^5$, respectively. (d) These values are sanity checks only; the asymptotic claim rests on the prime number theorem argument above.

5. What exactly remains

Write the unknown set in dyadic shells

D_j=A\cap(2^{j-1},2^j].

A full solution must choose these shells compatibly so that all previous choices help cover every later target block. The required new ingredient can be stated precisely:

for the first live-page question, construct compatible $D_j$ with

$\sum_{i\le J}|D_i|=o(J^2)$ and $(2^J,2^{J+1}]\subseteq\mathbb P+\bigcup_{i\le J+1}D_i$ for every large $J$;

for the $O(\log N)$ question, strengthen the cumulative bound to $O(J)$.

The finite fresh-shell lemma cannot supply this, because it provably charges $\Omega(j)$ new shifts at stage $j$. The independent scale-free model cannot supply it either, because its expected exceptional set has positive density for every fixed sampling constant. What is missing is a correlated, cross-scale prime-translate covering lemma that reuses roughly logarithmically many total shifts while eliminating the last exceptional integers, and that still respects Ruzsa's $e^\gamma$ lower bound.

The pure verifier's cost also shows why merely extending the finite table is not that lemma. The $N=128$ lower proof took about 7 seconds; an exploratory $N=160$, 9-offset exclusion passed 920,000 nodes in 20 seconds without finishing in the same unoptimised checker. Larger certified tables are feasible with dedicated exact-cover software, but they would remain finite evidence and would not provide the required uniform compatibility. I therefore did not spend the box's CPU budget on them.

No construction here solves or falsifies the live problem, and no computation is presented as asymptotic evidence strong enough to do so.

PARTIAL: Exact fresh-shell minima were certified at 13 values through N=128, and two natural independent-scale approaches were rigorously shown to retain the log-squared barrier; the missing step is a correlated cross-scale covering lemma.

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

\(N\)	exact \(F(N)\)	one optimal offset set \(C\)	consecutive \(g\)
4	2	\(\{0,1\}\)	2
8	3	\(\{0,1,3\}\)	4
12	4	\(\{2,3,4,5\}\)	4
16	4	\(\{2,3,4,5\}\)	4
20	4	\(\{0,1,2,3\}\)	4
24	5	\(\{0,2,3,5,7\}\)	6
32	6	\(\{1,2,3,4,5,6\}\)	6
40	6	\(\{13,14,15,16,17,18\}\)	6
48	6	\(\{15,17,18,19,20,22\}\)	6
64	6	\(\{1,2,3,4,5,6\}\)	6
80	6	\(\{2,3,4,5,6,7\}\)	6
96	8	\(\{2,4,5,6,7,8,9,11\}\)	8
128	8	\(\{2,4,13,20,29,36,45,47\}\)	14