Erdős problem #688 — live check, exact reduction, upper bound, and finite certification
Date: 2026-07-27 (UTC)
Claim labels
- [a] elementary-rigorous: proved from elementary facts in this report.
- [b] rigorous-modulo-named-theorem: the theorem and a primary or authoritative source are named.
- [c] plausible/structural-unverified: a search miss, heuristic, comparison, or cost projection.
- [d] computational-only: exactly reproduced by the standalone verifier, but not a uniform theorem.
0. Mandatory live-page gate
I loaded the live problem page and its LaTeX endpoint through the Bright Data browser path on 2026-07-27, before doing any mathematics. The live page was last edited 07 April 2026. [d]
The live state was OPEN, with 0 comments, 0 claimed proofs, “Currently working on this problem: None”, and “Interested in collaborating: None”. The other markers were: liked by kxwz; “looks difficult: None”; “looks tractable: None”; “results could be formalisable: None”; and “working on formalising the results: None”. It records “Formalised statement? Yes”. Thus neither mandatory stop condition applied. [d]
Live statement
The live LaTeX source begins (verbatim):
> Define \(\epsilon_n\) to be maximal such that there exists some choice of congruence class \(a_p\) for all primes \(n^{\epsilon_n} The remainder says, exactly in mathematical notation,
\(\epsilon_n=o(1)\). This is a meaning-preserving formal transcription; the live LaTeX itself has a typographical blank left side in @@S19@@. The formal Lean link on the page uses the quantified integer \(m\), as do Erdős's originals. [d for the live transcription; a for the equivalence]
The only known result displayed on the live page is
\[ \epsilon_n\gg\frac{\log\log\log n}{\log\log n}. \]It cites [Er79d] and [Er80,p.106] and links problems #687, #689, and #1200. No prize is shown. [d]
1. Primary sources and literature check
The cited [Er79d] is P. Erdős, Some unconventional problems in number theory, Acta Math. Acad. Sci. Hungar. 33 (1979), 71–80, DOI 10.1007/BF01903382, with an author-archive PDF. On p.79 Erdős poses the same large-prime covering problem and states the same lower bound. That version says “smallest” exponent, which is inconsistent with the downward monotonicity in the exponent; the live page and the later source correct this to “largest”. [b for what the primary source says; a for the monotonicity observation]
The cited [Er80] is P. Erdős, A survey of problems in combinatorial number theory, Annals of Discrete Mathematics 6 (1980), 89–115, primary PDF. Section 6, p.106, explicitly defines the largest exponent, says “It is not difficult to prove” the displayed lower bound, but supplies no proof. The same page says that the Erdős–Ruzsa bounded-reciprocal covering conjecture would “very likely” imply a fixed positive lower bound for \(\epsilon_x\). [b for the source report; c for Erdős's “very likely” implication]
I searched exact fragments of the statement, both cited titles, combinations of “large primes”, “covering interval”, “residue classes”, and “Jacobsthal function”, and citations around the two originals. Gérald Tenenbaum's Some of Erdős' unconventional problems in number theory, thirty-four years later, also arXiv:1908.00488, exists and updates selected problems from the 1979 paper, but a full-text check found no treatment of this p.79 covering question. This is a search miss, not a proof that no later treatment exists. [c]
Filaseta–Ford–Konyagin–Pomerance–Yu, Sieving by large integers and covering systems of congruences, JAMS 20 (2007), 495–517, proves positive global-density results for moduli in \((N,KN]\). For the pairwise-coprime prime moduli here, the global survivor density is already exactly the CRT product \(\prod_p(1-1/p)>0\); this does not bound the largest finite gap and therefore does not settle #688. [b for their theorem; a for the comparison]
Ben Green's 100 Open Problems, most recently updated December 2025, gives useful current context. Problem 43 says that even controlling the union of arbitrary classes for primes in a narrow range around \(N^{0.51}\) is open, and explicitly identifies pairwise residue-class interaction as the obstacle. Problem 46 records the neighboring primorial Jacobsthal problem and Iwaniec's \(O(x^2)\) upper bound. Neither statement solves the primorial-quotient gap required here. [b for Green's recorded statements; a for the comparison]
No primary source found in these searches improves the lower bound or proves/disproves \(\epsilon_n=o(1)\). This is reported only as a reproducible literature-search miss. [c]
2. Exact reduction
For a prime \(q\le n\), define
\[ M(n,q):=\prod_{\substack{q\le p\le n\\p\ {\rm prime}}}p \]and let \(j(m)\) be the least \(\ell\) such that every block of \(\ell\) consecutive integers contains an integer coprime to \(m\). Define
\[ L(n):=\max\{q\le n:q\text{ prime and }j(M(n,q))>n\}, \tag{2.1} \]whenever the set is nonempty. [a: definitions]
There is a cover using the primes \(q\le p\le n\) if and only if \(j(M(n,q))>n\). Indeed, given classes \(a_p\bmod p\), the Chinese remainder theorem supplies \(A\) with
\[ A\equiv-a_p\pmod p\quad(q\le p\le n). \]Then \(x\equiv a_p\pmod p\) is equivalent to \(p\mid A+x\). Thus the classes cover \(1,\ldots,n\) exactly when the block \(A+1,\ldots,A+n\) contains no integer coprime to \(M(n,q)\). The converse sets \(a_p\equiv-A\pmod p\). [a]
For every \(n>1\) for which \(L(n)\) is defined, the supremum interpretation of the live quantity is exactly
\[ \boxed{\epsilon_n=\frac{\log L(n)}{\log n}}. \tag{2.2} \]If \(q=L(n)\), every exponent \(\eta<\log_nq\) includes all primes from \(q\) upward and hence permits the cover. At \(\eta=\log_nq\), the strict inequality \(n^\eta
The original asymptotic question is therefore equivalent to the following precise missing statement:
\[ \forall\alpha>0\ \exists n_0(\alpha)\ \forall n\ge n_0(\alpha): \qquad j\!\left(\prod_{n^\alpha3. A uniform upper bound and its exact finite version
A class modulo \(p\) contains at most \(\lceil n/p\rceil\) points of \([1,n]\). Consequently every cover using the prime suffix beginning at \(q\) must satisfy
\[ C_n(q):=\sum_{\substack{q\le p\le n\\p\ {\rm prime}}} \left\lceil\frac np\right\rceil\ge n. \tag{3.1} \]This is both a finite obstruction and the first pruning rule in the verifier. [a]
For fixed \(\alpha>0\), a cover using only \(n^\alpha
This does not answer the \(o(1)\) question, but it is a clean unconditional upper bound recovered directly from the statement. [b: Mertens and PNT; a for the deduction]
4. Exact finite computation
The standalone file erdos688_wave7g_reverify.py proves the complete table below. [d]
| \(n\) | exact \(L(n)\) | exact \(\epsilon_n\) |
|---:|---:|---:|
| \(11\)–\(42\) | \(2\) | \(\log_n2\) |
| \(43\)–\(44\) | \(3\) | \(\log_n3\) |
| \(45\)–\(46\) | \(2\) | \(\log_n2\) |
| \(47\)–\(49\) | \(3\) | \(\log_n3\) |
| \(50\)–\(60\) | \(2\) | \(\log_n2\) |
| \(61\)–\(65\) | \(3\) | \(\log_n3\) |
| \(66\) | \(2\) | \(\log_{66}2\) |
| \(67\)–\(70\) | \(3\) | \(\log_n3\) |
The nonmonotonic drops at \(45,50,66\) are real: increasing \(n\) without receiving a helpful new prime makes the target interval longer, while a new endpoint prime can make the value jump again. [d]
As one explicit construction, at \(n=67\) the following assignment covers every integer \(1,\ldots,67\):
\[ \begin{array}{c|rrrrrrrrrrrrrrrrrr} p&3&5&7&11&13&17&19&23&29&31&37&41&43&47&53&59&61&67\\ \hline a_p&2&3&4&9&1&2&11&11&16&6&24&10&12&7&52&21&15&22. \end{array} \tag{4.1} \]The verifier checks this fixed witness before starting its search. It then independently finds a cover with least prime \(3\) and proves that no cover with least prime at least \(5\) exists. [d]
Candidate covers were initially scouted with OR-Tools CP-SAT, but no solver status, objective, or hidden certificate is used in the reported result; the delivered standard-library program independently reconstructs witnesses and proves every upper suffix infeasible. [d]
Why the negative certificates are exact
The program descends through prime suffixes. Suffixes violating (3.1) are impossible. At the first remaining suffix, its smallest prime \(q\) must be used, since deleting it gives an already rejected suffix; the program enumerates every residue modulo \(q\). If that suffix is exhaustively rejected, the same induction forces the next smaller prime in the next trial. [a]
At any search node, let \(U\) be the uncovered points and let \(g_p\) be the largest number of them hit by one class modulo an unused prime \(p\). The prune
\(\sum g_p<|U|\) is safe even after optimistically ignoring all overlaps. If
\(\sum g_p-g_r<|U|\), prime \(r\) is mandatory and every residue of \(r\) with positive gain is enumerated. Otherwise, the program selects an uncovered \(x\); every completion must assign some unused \(p\) the forced residue \(x\bmod p\), so branching over all unused \(p\) is exhaustive. Failed states are memoized by (covered_mask, remaining_primes), which contains all information relevant to a completion. [a]
All incidence and coverage operations use integer bit masks. Primes are recomputed by trial division. There is no floating-point pruning, SAT/MILP solver, randomized step, or imported certificate. Decimals are printed only after the exact \(L(n)\) has been proved. [a+d]
The full run visited \(1{,}157{,}053\) nodes to reject the odd-prime suffix at \(n=66\), then found a modulus-\(2\) cover in 15 nodes. At \(n=67\), it rejected the suffix beginning at \(5\) in 6 nodes and found a suffix-\(3\) cover in 77 nodes. The final complete \(11\le n\le70\) run finished with PASS in 98.451 seconds on this VM. [d]
Run:
cd /home/exedev/MathDyad
python runs/erdos688_wave7g_reverify.py
The verifier's SHA-256 is
b67359f6ef7d887a356b4719dc9720e760a66b9249e3da2c706faca045d7fe13. [d]
5. Exact wall
For fixed \(\alpha\), the global density of integers coprime to
\(\prod_{n^\alpha
The union-capacity argument loses all force at \(\alpha\le e^{-1}\). The general primorial Jacobsthal bound recorded by Erdős and by Green is of order \(O(x^2)\) for primes up to \(x\); since \(\prod_{n^\alpha
Thus the exact missing lemma is (2.3): a uniform linear maximum-gap bound for primorial quotients, for every fixed lower exponent \(\alpha>0\). Equivalently, one needs an overlap/incidence theorem strong enough to show that arbitrary classes for all \(n^\alpha
The pure-Python search already needed about 49 seconds and \(1.16\times10^6\) nodes for the single \(n=66\) rejection; a separate \(n=100\) scout was stopped after roughly 75 seconds without a result. At the observed difficult-case rate of roughly \(2.3\times10^4\) nodes/second, \(10^8\) nodes would cost about 1.2 core-hours and \(10^9\) about 12 core-hours, before memory overhead. A larger finite project should use a compiled SAT solver emitting a checkable DRAT/LRAT proof, but no finite extension can supply the uniformity in (2.3). [d for observed runs; c for extrapolated cost and recommendation; a for the non-implication]
PARTIAL: Proved the exact Jacobsthal-quotient reduction, the unconditional bound \(\limsup\epsilon_n\le e^{-1}\), and a from-scratch exact table \(L(n)\) for every \(11\le n\le70\); the missing uniform linear gap bound (2.3) remains open.