Estimate the Jacobsthal-type covering maximum $Y(x)$: is $Y(x)=o(x^2)$? (Erdős #687)
Statement
Let $Y(x)$ be the largest $y$ for which there exists a choice of congruence classes $a_p$, one for every prime $p\leq x$, such that every integer in $[1,y]$ is congruent to at least one of the $a_p\pmod p$. Give good estimates for $Y(x)$. In particular, prove that $Y(x)=o(x^2)$, or even $Y(x)\ll x^{1+o(1)}$.
Acceptance. FULLY RESOLVES (proof-shaped): a complete rigorous proof — a Lean/Coq formalisation preferred, otherwise a full written proof — of an asymptotic estimate for $Y(x)$; in particular either a proof that $Y(x)=o(x^2)$ or a determination of the true order of magnitude of $Y(x)$. ADVANCES: (a) improve the best known upper bound stated in the background (currently $Y(x)\ll x^2$, Iwaniec) with proof; (b) improve the best known lower bound stated in the background (currently $Y(x)\gg x\log x\log\log\log x/\log\log x$, Ford–Green–Konyagin–Maynard–Tao) with proof; or (c) compute $Y(x)$ exactly for a new record range of $x$ with a reproducible search program and a certificate of exhaustiveness, extending OEIS A048670/A058989. Deliver the proof, the improved-bound argument, or the search code plus attained values.
Background
Posed by Erdős [Er79d, Er80, Er96b] and listed as open on erdosproblems.com/687 (fetched 2026-07-21, status 'open'). The function $Y(x)$ is a close relative of the Jacobsthal function and is tightly bound up with the study of gaps between primes (see Erdős #4, erdosproblems.com/4). The best known upper bound is due to Iwaniec [Iw78], $Y(x)\ll x^2$. The best known lower bound is due to Ford, Green, Konyagin, Maynard, and Tao [FGKMT18], $Y(x)\gg x\,\frac{\log x\,\log\log\log x}{\log\log x}$, improving an earlier bound of Rankin [Ra38]. Maier and Pomerance conjectured that $Y(x)\ll x(\log x)^{2+o(1)}$. Erdős offered a prize of $1000 (and, in [Er80], writes that he would give half his total savings) for clearing up this problem; he also asked a weaker variant in which all but $o(y/\log y)$ of the integers in $[1,y]$ are covered. Related OEIS sequences: A048670, A058989. Attacker's tool: large-sieve / analytic bounds on the covering density in the spirit of the Ford–Green–Konyagin–Maynard–Tao prime-gap machinery, together with exhaustive computation of $Y(x)$ for small $x$ to extend A048670/A058989 and pin the true exponent.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #687 (T. F. Bloom) | website |
| REF-02 | OEIS A048670 — Jacobsthal function of primorials | website |
| REF-03 | OEIS A058989 | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.