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

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

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

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

| 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:

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

coverage; or

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

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(b), modulo the prime number theorem,

\[ \max_{0\le cHere 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 NN/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