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

Erdős problem #687 — exact finite certification and the interval-sieve wall

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

Claim labels

[a] elementary-rigorous: proved directly from definitions or elementary

arithmetic in this report.

[b] rigorous-modulo-named-theorem: rigorous conditional on the cited

published theorem.

[c] plausible/structural-unverified: heuristic, search miss, projection,

or methodological diagnosis.

[d] computational-only: exactly reproduced in the stated finite range by

the standalone verifier, but not a uniform theorem.

0. Mandatory live-page gate

I loaded the rendered live page and then its discussion thread through the Bright Data browser path before doing any mathematics. The page was last edited 06 December 2025. It showed OPEN - $1000, 1 comment, 0 claimed proofs, “Currently working on this problem: None”, and “Interested in collaborating: None”. Thus neither mandatory stop condition applied. [d, live-page observation]

The remaining markers were: likes None; “looks difficult: None”; “looks tractable: None”; “results could be formalisable: None”; “working on formalising the results: None”; and “Formalised statement? No”. [d, live-page observation]

Live statement

The rendered statement begins verbatim:

Let $Y(x)$ be the maximal $y$ such that there exists a choice of congruence classes $a_p$ for all primes $p\le x$

The exact remaining mathematical condition is

[1,y]\cap\mathbb Z \subseteq \bigcup_{\substack{p\le x\\p\ {\rm prime}}} \{n\in\mathbb Z:n\equiv a_p\pmod p\}. \tag{0.1}

The page asks for good estimates for $Y(x)$, and specifically asks whether

Y(x)=o(x^2), \qquad\text{or even}\qquad Y(x)\ll x^{1+o(1)}. \tag{0.2}

Equations (0.1)–(0.2) are a meaning-preserving exact mathematical transcription of the rest of the rendered statement. [d for page transcription; a for the set-notation equivalence]

Everything else listed on the live page

The live page records the following current known results:

Y(x)\ll x^2 \quad\text{(Iwaniec [Iw78])}, \tag{0.3}

and

Y(x)\gg x\,\frac{\log x\,\log_3x}{\log_2x} \quad\text{(Ford--Green--Konyagin--Maynard--Tao [FGKMT18])}, \tag{0.4}

where $\log_j$ denotes the $j$-fold iterated logarithm. It says (0.4) improves Rankin's earlier bound and records the Maier--Pomerance conjecture

Y(x)\ll x(\log x)^{2+o(1)}. \tag{0.5}

[b for the named published results; c for the conjecture]

The page also records Erdős's weaker variant: allow all but $o(y/\log y)$ integers in $[1,y]$ to remain uncovered and ask whether the answer is very different. It links problems #688, #689, and #970 and OEIS sequences A048670 and A058989. [d, live-page observation]

The single comment is by Boris Alexeev, timestamped 04 December 2025. It identifies the formulation on p.106 of [Er80] using inverse functions $f(x)$ and $F(x)$, including the weaker almost-covering question, and highlights Erdős's prize. The thread says the site was updated to address that comment. It contains no claimed solution or worker declaration. [d, live-thread observation]

1. Primary-source and literature check

Henryk Iwaniec,

On the problem of Jacobsthal, Demonstratio Mathematica 11 (1978), 225–232, exists and studies the maximal length $C(r)$ of consecutive integers each divisible by one of $r$ chosen primes. Its bound $C(r)\ll r^2\log^2r$, with $r=\pi(x)$, gives (0.3). Banks--Ford--Tao also explicitly state that Iwaniec proved $J(w)\ll w^2$ with the linear sieve. [b]

Kevin Ford, Ben Green, Sergei Konyagin, James Maynard, and Terence Tao,

Long gaps between primes, J. Amer. Math. Soc. 31 (2018), 65–105, define this exact $Y(x)$ in Definition 1, prove (0.4) as equation (1.1), and prove $Y(x)=j(P(x))-1$ as equation (1.2). The paper also states the Iwaniec upper bound and the Maier--Pomerance conjecture. [b]

Thomas R. Hagedorn,

Computation of Jacobsthal's function $h(n)$ for $n<50$, Math. Comp. 78 (2009), 1073–1087, defines $h(k)=j(p_k\#)$ and gives exact values through $k=49$. Its Table 1 contains all finite values independently recomputed below. Therefore the finite table in this report is a from-scratch reproducibility result, not a new extension of the published table. [b for the paper; d for the comparison]

Mario Ziller and John F. Morack,

Algorithmic concepts for the computation of Jacobsthal's function, arXiv:1611.03310v2, report computations through $p_k=251$ and provide exhaustive ancillary lists of maximal sequences. This unrefereed computational report is not used as a certificate here. [d for the authors' reported computation]

William Banks, Kevin Ford, and Terence Tao,

Large prime gaps and probabilistic models, Invent. Math. 233 (2023), 1471–1518, give a current primary-source treatment of the extremal interval sieve. Their Section 2.3 still records Iwaniec's $J(w)\ll w^2$, and supplies the precise conditional route through the $x^2$ barrier used in Section 5 below. [b]

I searched the exact problem formulation, Jacobsthal function primorial, interval sieve, the Iwaniec title and citations, and 2020–2025 work using these terms. I found finite computations, variants, and the 2023 Banks--Ford--Tao analysis, but no primary source giving an unconditional improvement $Y(x)=o(x^2)$. This agrees with the live page but is only a reproducible search miss, not a proof of bibliographic completeness. [c]

2. Exact reduction to a primorial Jacobsthal function

Put

P(x):=\prod_{p\le x}p

and let $j(N)$ be the smallest positive integer $m$ such that every block of $m$ consecutive integers contains an integer coprime to $N$. Equivalently, $j(N)$ is the largest gap between consecutive integers coprime to $N$. [a, definitions and elementary equivalence]

For every real $x\ge2$,

\boxed{Y(x)=j(P(x))-1.} \tag{2.1}

To prove this from scratch, suppose classes $a_p\bmod p$ cover $[1,y]$. The Chinese remainder theorem supplies $B$ such that

B\equiv-a_p\pmod p\qquad(p\le x).

For every $1\le n\le y$, some $p\le x$ has $n\equiv a_p\pmod p$, hence $p\mid B+n$. Thus $B+1,\ldots,B+y$ is a run of $y$ integers none coprime to $P(x)$. Conversely, from such a run define $a_p\equiv-B\pmod p$; every offset is then covered by a prime divisor of its translated integer. The largest non-coprime run has length one less than the largest gap between consecutive coprimes, proving (2.1). [a]

If $p_k\le x<p_{k+1}$, then $P(x)=p_k\#$. Hence, with $h(k):=j(p_k\#)$,

Y(x)=h(k)-1. \tag{2.2}

In particular $Y$ is constant between consecutive primes. [a]

This reduction is exact but does not make the asymptotic problem easier: $p_k\#$ has exponential size in $p_k$, and determining its largest unit gap by scanning a complete period rapidly becomes infeasible. [a for the period size; c for the methodological diagnosis]

3. Exact finite result

The standalone verifier proves the following complete table. Here $P_k=p_k\#$, $h(k)=Y(p_k)+1$, $B$ is a CRT start for a run of $Y(p_k)$ non-units, and “states” is the number of memoized states used to prove that a run one unit longer is impossible. [d]

| $k$ | $p_k$ | $P_k$ | $h(k)$ | $Y(p_k)$ | CRT start $B$ | upper states | |---:|---:|---:|---:|---:|---:|---:| | 1 | 2 | 2 | 2 | 1 | 1 | 1 | | 2 | 3 | 6 | 4 | 3 | 1 | 1 | | 3 | 5 | 30 | 6 | 5 | 23 | 1 | | 4 | 7 | 210 | 10 | 9 | 199 | 1 | | 5 | 11 | 2,310 | 14 | 13 | 2,183 | 12 | | 6 | 13 | 30,030 | 22 | 21 | 20,569 | 32 | | 7 | 17 | 510,510 | 26 | 25 | 293,357 | 110 | | 8 | 19 | 9,699,690 | 34 | 33 | 60,043 | 416 | | 9 | 23 | 223,092,870 | 40 | 39 | 82,370,089 | 2,088 | | 10 | 29 | 6,469,693,230 | 46 | 45 | 6,052,606,537 | 10,714 | | 11 | 31 | 200,560,490,130 | 58 | 57 | 74,959,204,291 | 54,900 | | 12 | 37 | 7,420,738,134,810 | 66 | 65 | 1,873,765,918,163 | 313,992 | | 13 | 41 | 304,250,263,527,210 | 74 | 73 | 224,627,748,945,563 | 2,171,934 |

Consequently, for $1\le k\le13$ and $p_k\le x<p_{k+1}$, the exact value of $Y(x)$ is the fifth column. In particular,

\boxed{Y(x)=73\quad(41\le x<43),} \tag{3.1}

and the table determines every value for integer $2\le x\le42$. [d]

For the final row, one explicit covering assignment is

\begin{array}{c|rrrrrrrrrrrrr} p&2&3&5&7&11&13&17&19&23&29&31&37&41\\ \hline a_p&1&1&2&2&4&11&3&18&14&8&6&1&36. \end{array} \tag{3.2}

The CRT value $B=224627748945563$ satisfies

\gcd(B,P_{13})=\gcd(B+74,P_{13})=1, \qquad \gcd(B+n,P_{13})>1\quad(1\le n\le73). \tag{3.3}

The program checks every gcd in (3.3) directly. [d]

4. Why the finite upper certificates are exhaustive

For primes $p_1,\ldots,p_k$ and a proposed length $L$, let

C(p,r):=\{n\in[1,L]:n\equiv r\pmod p\}.

A search state consists of the set $U$ of uncovered positions and the set $R$ of unused primes. Select any $n\in U$. In every completion, some $p\in R$ must cover $n$, and its residue is forced to be $n\bmod p$. The recursion branches over every $p\in R$, replaces $U$ by $U\setminus C(p,n\bmod p)$, and deletes $p$ from $R$. This is an exhaustive partition of all possible completions. [a]

The only pruning inequality is

\sum_{p\in R}\max_{0\le r<p}|U\cap C(p,r)|<|U|. \tag{4.1}

If (4.1) holds, even the optimistic sum that ignores every overlap cannot cover $U$, so the state is impossible. Failed states are memoized by the exact pair $(U,R)$. Branch and position ordering affect runtime only, not completeness. [a]

For an even $L$, reflection $n\mapsto L+1-n$ switches the chosen residue modulo $2$. Thus a cover exists if and only if one exists with $a_2=0$, allowing the upper searches to fix that residue without loss. For each candidate $h(k)$, the program constructs and directly checks a cover of $h(k)-1$, then exhaustively rejects a cover of $h(k)$. A cover of any larger interval would restrict to one of length $h(k)$, so these two checks prove exactness. [a]

The exact-cover result is independently cross-checked for $k\le9$ by a second algorithm: allocate one complete period of length $P_k$, mark every multiple of every $p\le p_k$, and scan the surviving residues for the largest cyclic gap. This recomputes

\[ 2,4,6,10,14,22,26,34,40 \]

without using the exact-cover recursion or its witnesses. [d]

The delivered program uses only the Python standard library. It regenerates the first 13 primes by trial division, uses no random choices, SAT/MILP solver, floating-point prune, or imported certificate, and directly verifies all reported covers and CRT gaps. [a for program structure; d for the executed checks]

Run:

cd /home/exedev/MathDyad
python runs/erdos687_wavew009_reverify.py

The final clean run finished with PASS in 66.03 seconds and peak RSS 472,000 KB on this VM. The $k=13$ non-cover proof took 40.873 seconds and visited 2,171,934 states; the independent $P_9=223092870$ period scan took 17.466 seconds. The verifier's SHA-256 is a1db47497fde5548b3d888b49b41cf9157381939203c6bc5885f79e9fded0882. [d]

5. The precise $x^2$-barrier and a sufficient missing lemma

Banks--Ford--Tao define, for a choice of one residue $a_p\bmod p$ for each prime $p\le z$,

\mathcal S_z :=\mathbb Z\setminus\bigcup_{p\le z}(a_p\bmod p)

and the extremal interval-sieve quantity

W_y:= \min_{(a_p)} \left|[0,y]\cap \mathcal S_{\sqrt{y/\log y}}\right|. \tag{5.1}

They record the sharpest current bounds

(4+o(1))\frac{y\log_2y}{\log^2y} \le W_y \le \frac y{\log y} +O\!\left(\frac{y\log_2y}{\log^2y}\right). \tag{5.2}

[b, Banks--Ford--Tao equation (1.12)]

A concrete sufficient lemma for breaking the barrier is:

\boxed{\text{There exists a fixed }\alpha>0\text{ such that } W_y\ge\alpha\,\frac y{\log y} \text{ for all sufficiently large }y.} \tag{5.3}

Banks--Ford--Tao's Brun--Titchmarsh argument shows that (5.3) implies

j(P(w)) \ll w^{\,1+e^{-\alpha/2}+o(1)}. \tag{5.4}

Because $1+e^{-\alpha/2}<2$, equations (2.1) and (5.4) would prove the first requested improvement $Y(w)=o(w^2)$, in fact with a fixed power saving. [b for (5.4); a for the deduction]

The known lower bound in (5.2) is smaller than $y/\log y$ by a factor asymptotic to $4\log_2y/\log y\to0$; it therefore supplies no fixed $\alpha$ in (5.3). This pinpoints the missing uniform input in this standard route. [a]

The obstruction is not merely a loose numerical constant. Banks--Ford--Tao prove that if exceptional (Landau--Siegel) zeros exist, then

\liminf_{y\to\infty}\frac{W_y}{y/\log y}=0. \tag{5.5}

Consequently, (5.3) would rule out exceptional zeros, itself a famous open problem. This explains precisely why the usual linear-sieve machinery stalls at the exponent $2$: at the critical sieve level, its lower function vanishes, and a positive uniform survivor constant would have major consequences beyond this problem. [b for (5.5); a for the implication; c for the methodological diagnosis]

Even the conjecturally best value $\alpha=1$ allowed by the upper bound in (5.2) makes the exponent supplied by (5.4) only

1+e^{-1/2}=1.606530659713\ldots,

not $1+o(1)$. Thus this particular one-stage implication could settle $o(x^2)$ but cannot by itself reach the stronger target $x^{1+o(1)}$; that target needs a sharper treatment of the later prime classes or a different argument. [b for using (5.2)–(5.4); a for the numerical and logical deduction; c for the final methodological alternative]

6. What has and has not been achieved

The finite computation is exact, independently cross-checked in the largest range where a full primorial period is cheap, and comes with explicit CRT witnesses. It establishes (3.1) from scratch but reproduces already published finite values. [d]

The asymptotic question remains open. The cleanest concrete target found is (5.3): it would rigorously give a power saving over $x^2$, while (5.5) shows why proving it requires information unavailable to the standard unconditional sieve. No finite extension of the table can supply the uniformity in (5.3) or prove either asymptotic assertion in (0.2). [b for the conditional target and obstruction; a for the finite/uniform distinction]

PARTIAL: Independently certified $Y(x)=h(\pi(x))-1$ and the exact values through $x<43$ (in particular $Y=73$ on $41\le x<43$); a fixed positive interval-sieve survivor bound (5.3) would prove $Y=o(x^2)$, but it would also rule out exceptional zeros, and no such unconditional bound is known.

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