Erdős #687 — estimate the Jacobsthal covering function Y(x)

Statement

Let $Y(x)$ be the maximal $y$ such that there exists a choice of congruence classes $a_p$ for all primes $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, can one prove that $Y(x)=o(x^2)$ or even $Y(x)\ll x^{1+o(1)}$?

Facts

- Prize $1000; status open, and per the site's own tooltip "cannot be resolved with a finite computation" (erdosproblems.com/687, fetched directly). Falsifiability here means "not finite": no candidate finite construction/witness can *prove* the required upper bound, since the claim is an asymptotic statement about ALL sufficiently large $x$ and ALL choices of $a_p$. - Falsifiable in the weak sense that a large enough explicit covering construction could *refute* a proposed upper bound (as FGKMT's construction refutes any conjectured $Y(x) = O(x^{1-\epsilon})$), but the actual ask — proving $Y(x)=o(x^2)$ or $Y(x)\ll x^{1+o(1)}$ — is a genuine upper-bound theorem, not decidable by finite search. - Origin: Erdős, "Some unconventional problems in number theory," Acta Math. Acad. Sci. Hungar. (1979) [Er79d,p.79]; "A survey of problems in combinatorial number theory," Ann. Discrete Math. (1980) [Er80,p.106]; "Some problems I presented or planned to present in my short talk" (1996) [Er96b]. In [Er80] Erdős writes: "It is not clear who first formulated this problem — probably many of us did it independently. I offer the maximum of \$1000 dollars and $1/2$ my total savings for clearing up of this problem." (quoted verbatim on erdosproblems.com/687). - Known results / best bounds (both verified on erdosproblems.com/687): - Upper bound (unimproved since 1978): $Y(x) \ll x^2$, due to Iwaniec, "On the problem of Jacobsthal," Demonstratio Math. (1978) [Iw78]. No later paper found (2026-07-02 search) that improves this exponent — the central open gap of the problem is exactly here. - Lower bound (current best): $Y(x) \gg x\,\dfrac{\log x \log\log\log x}{\log\log x}$, due to Ford, Green, Konyagin, Maynard, Tao, "Long gaps between primes," J. Amer. Math. Soc. (2018) [FGKMT18] = arXiv:1412.5029 (arXiv abstract read directly). This improves an older bound of Rankin (1938) [Ra38]. The FGKMT construction is exactly a combinatorial covering-system construction of the $Y(x)$ type — the paper's headline result (a lower bound of $\gg \log X\log\log X\log\log\log\log X/\log\log\log X$ on the largest prime gap up to $X$, arXiv abstract) is *derived from* their $Y(x)$-type lower bound via the classical Erdős–Rankin translation "a covering of $[1,y]$ using primes $\le x$ $\Rightarrow$ a prime gap of size $\ge y$ near $\exp(x)$." - Conjectured truth: Maier and Pomerance conjecture $Y(x) \ll x(\log x)^{2+o(1)}$ (stated on erdosproblems.com/687, corroborated independently via web search) — far below both the $x^2$ upper bound proved and even below the $x^{1+o(1)}$ threshold Erdős explicitly asks about, i.e. Erdős's stated target ($x^{1+o(1)}$) is already stronger than what is believed true; $o(x^2)$ is the "easy ask," $x^{1+o(1)}$ is the "hard ask," and $x(\log x)^{2+o(1)}$ is the believed truth (intermediate, closer to the hard ask). - A weaker variant (allow $o(y/\log y)$ exceptions in $[1,y]$) is also posed by Erdős in [Er80]; erdosproblems.com/687 notes he asks whether the answer is "very different" there. - Related problems: Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) (unbounded prime gaps, resolved by literally the same FGKMT lower-bound construction — see Literature state), Erdős #688 — the ε_n covering variant: how few large primes can cover [1,n]? ($\epsilon_n$-variant: covering $[1,n]$ using only primes in $(n^{\epsilon_n}, n]$), Erdős #689 — double covering by prime residues: all-moduli case SOLVED (erdos/1205, F(x)~log x); primes-only case OPEN with two 2026 proof claims unverified (double-covering variant: every integer in $[1,n]$ hit by $\ge 2$ of the congruences $a_p\pmod p$), Jacobsthal's function h(k) — finiteness and near-matching two-sided bounds (Jacobsthal's function $h(k)$ itself: max gap between integers coprime to a squarefree $n$ with $k$ prime factors — the "coprimality" analogue of the "covering" function $Y$), Erdős #2 — minimum modulus of a covering system cannot be arbitrarily large (Erdős's *other* covering-systems problem — minimum modulus of a distinct-modulus covering system — same "covering system of congruences" object, unrelated construction, but resolved and a template for what a full resolution of a covering-systems question looks like).

Literature state

Not resolved — confirmed open as of 2026-07-02 (erdosproblems.com/687 direct fetch shows status OPEN, 1 forum comment with no claimed partial solution, "Comment activity not yet incorporated: None" widget). No paper found in this search improves Iwaniec's 1978 upper bound $Y(x)\ll x^2$; no evidence of AI/LLM contribution (github.com/teorth/erdosproblems wiki "AI contributions" page checked, no mention of #687).

What the literature *does* establish, precisely delimiting where the difficulty sits: 1. The lower-bound side is a solved-adjacent, actively-worked area. FGKMT's arXiv:1412.5029 ("Long gaps between primes," JAMS 2018) is the state of the art; its "main new ingredient is a generalization of a hypergraph covering theorem of Pippenger and Spencer, proven using the Rödl nibble method" (arXiv abstract). This exact machine is what pushed $Y(x)$'s lower bound up from Rankin's 1938 construction. Because $Y(x)$'s lower bound only needs to beat a comparatively weak target to resolve the *prime-gap* question, FGKMT's result was strong enough to fully settle the separate (and separately famous) Erdős problem Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) ("is the largest gap $\gg C\log p\log\log p\log\log\log\log p/(\log\log\log p)^2$ for every $C$?", confirmed PROVED on erdosproblems.com/4). That is a genuine, verified precedent: the identical covering-construction technology used for #687's lower bound *did* fully resolve a sibling Erdős problem — but it resolves the lower-bound-strength question, not the upper-bound question #687 actually asks for. 2. The upper-bound side (what #687 needs) has seen no progress since 1978. Iwaniec's elementary/sieve-counting bound $Y(x)\ll x^2$ stands unchallenged; the believed-true bound (Maier–Pomerance, $x(\log x)^{2+o(1)}$) would require ruling out coverings far more efficient than anything anyone has shown impossible. This is structurally an "impossibility of a combinatorial covering" result, i.e. the opposite direction from what Rödl-nibble/hypergraph-covering machinery is built to prove (those constructively *build* good coverings; #687 needs a proof that no cleverer covering than the known ones can exist). 2b. Terence Tao's blog post on Erdős #385 (terrytao.wordpress.com/2024/08/19, checked directly) independently confirms and uses the FGKMT lower bound on $Y(x)$/Jacobsthal's function (his eq. (1.2)) as a black box in unrelated sieve-theoretic work — this cross-use confirms the FGKMT bound is the field's accepted state of the art for the lower-bound side, five+ years after publication, with nothing superseding it. 3. A closely related but structurally distinct covering-systems problem, Erdős's minimum-modulus problem (Erdős #2 — minimum modulus of a covering system cannot be arbitrarily large, "can the smallest modulus of a covering system be arbitrarily large?"), was fully resolved (status DISPROVED, erdosproblems.com/2 confirmed) by Hough via arXiv:1307.0874 ("Solution of the minimum modulus problem for covering systems," showing min modulus $\le 10^{18}$), later sharpened to $\le 616{,}000$ by the distortion method of Balister–Bollobás–Morris–Sahasrabudhe(–Tiba) (arXiv:2211.01417, "Erdős covering systems," a gentle exposition of the method — abstract read directly). This is the single most relevant *fully solved* precedent for #687: it is a covering-systems-of-congruences problem, resolved by proving a strong structural/density *impossibility* result about how efficiently congruence classes can jointly cover $\mathbb{Z}$ — i.e. it is an "upper-bound-on-covering-efficiency" proof in the same broad family #687 needs, even though the specific combinatorial setup differs (arbitrary distinct moduli covering all of $\mathbb{Z}$, vs. one class per prime $\le x$ covering $[1,y]$).

Attack surface

- Mode: literature-resolution (primary) + derivation. This is explicitly not finite-search for the headline question — the target is an asymptotic upper-bound theorem across all $x$, which cannot be settled by any computation, only by proof. (A finite search *could* still be useful as a falsification/exploration tool for the lower-bound side, or to numerically test whether known constructions already threaten to violate the Maier–Pomerance conjecture at accessible $x$, but that would not touch the $1000 prize question.) - Concrete first experiment (derivation-oriented, not finite-search): (1) Read Iwaniec [Iw78] and reconstruct exactly which counting/double-counting argument yields $x^2$ — erdosproblems.com/687 gives no detail beyond citing it, and this page's search did not locate a digitized/open copy of the 1978 Demonstratio Math. paper (worth a targeted library/MathSciNet pull, MR 499895) — then check whether the same argument, pushed with modern large-sieve or Turán-sieve inequalities (as used in Hough's distortion method, arXiv:1307.0874, and its exposition arXiv:2211.01417), can be tightened toward $x^{2-\delta}$ for any $\delta>0$, which alone would answer the "$o(x^2)$" half of the question. (2) In parallel, study whether the distortion method's core inequality (a weighted-density/variance bound controlling how much overlap covering congruence systems must have) transfers from "arbitrary moduli covering $\mathbb Z$" to "one congruence per prime $\le x$ covering $[1,y]$" — the two settings are combinatorially close enough (both: a system of arithmetic-progression constraints, ask about maximal coverage/minimal escape) that a transfer attempt is a well-defined, scoped research task, not blue-sky. - Oracle: for the actual $1000 question there is no finite oracle — a claimed upper-bound proof must be checked by human/formal peer review (no formalization exists yet per erdosproblems.com/687: "Formalised statement? No"). A *lower-bound* construction, by contrast, is mechanically checkable: given explicit $a_p$ for $p\le x$, verifying "every integer in $[1,y]$ hits some $a_p\pmod p$" is a direct $O(y\cdot \pi(x))$ or sieve-based computation — useful for testing whether the FGKMT/Rödl-nibble construction can be explicitly instantiated and numerically checked against the conjectured $x(\log x)^{2+o(1)}$ ceiling at moderate $x$. - Feasibility: famous and hard for the actual prize — this is the reverse-direction sibling of a problem (large prime gaps, Erdős #4 — unbounded large gaps between primes (Rankin's constant removed)) that took from Rankin (1938) through Erdős–Rankin refinements, Maier–Pomerance, Pintz, and finally FGKMT's 2014/2018 hypergraph-covering breakthrough to resolve the *lower*-bound side, and the *upper*-bound side asked by #687 has had zero recorded progress in 47+ years (1978–2026). A first realistic non-full-resolution contribution: (a) a clean literature/derivation note pinning down exactly what Iwaniec's 1978 argument is and whether any modern large-sieve/distortion-method inequality reproduces or improves it (genuinely useful, unglamorous, and currently missing from any public source found); (b) a numerical exploration comparing the best known explicit FGKMT-style covering constructions against the Maier–Pomerance conjectured ceiling at feasible $x$, to build intuition for where the true growth rate likely sits.

Related

- Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) — unbounded large prime gaps; PROVED (erdosproblems.com/4) by the same FGKMT hypergraph-covering / Rödl-nibble construction that gives #687's current best lower bound — direct precedent that this machinery resolves the *lower*-bound side of this problem family, not the upper-bound side #687 needs. - Erdős #688 — the ε_n covering variant: how few large primes can cover [1,n]? — $\epsilon_n$-variant of the same covering setup, restricting to primes in $(n^{\epsilon_n}, n]$; same combinatorial object, tighter prime range. - Erdős #689 — double covering by prime residues: all-moduli case SOLVED (erdos/1205, F(x)~log x); primes-only case OPEN with two 2026 proof claims unverified — double-covering variant (each integer hit by $\ge 2$ residue classes); same object, stronger covering requirement. - Jacobsthal's function h(k) — finiteness and near-matching two-sided bounds — Jacobsthal's function $h(k)$ (max gap between integers coprime to a $k$-almost-prime-factor number); the "avoid all classes" dual of $Y(x)$'s "hit some class." - Erdős #2 — minimum modulus of a covering system cannot be arbitrarily large — Erdős's minimum-modulus covering-systems problem; DISPROVED by Hough (arXiv:1307.0874) and sharpened by the distortion method (arXiv:2211.01417) — the closest *fully solved* precedent for proving a covering-efficiency impossibility result, the exact shape of theorem #687 needs. - Erdős–Rankin construction (covering-congruences translation for large prime gaps) — the classical translation between "covering $[1,y]$ with primes $\le x$" and "prime gap of size $\ge y$"; the bridge linking #687 to #4. - Pippenger–Spencer hypergraph covering theorem (and the FGKMT generalization) — Pippenger–Spencer-style hypergraph covering, generalized by FGKMT (arXiv:1412.5029) to build the current-best $Y(x)$ lower bound. - Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings — semi-random greedy method (successive "nibbles" of near-disjoint edges) underlying the FGKMT construction. - Distortion method (Hough; Balister–Bollobás–Morris–Sahasrabudhe–Tiba) for covering-system impossibility bounds — Hough / Balister–Bollobás–Morris–Sahasrabudhe(–Tiba) technique (arXiv:1307.0874, arXiv:2211.01417) for proving covering-system *impossibility*/density bounds; the most plausible transferable machinery for #687's upper-bound side. - Covering systems of congruences — the general object (finite unions of arithmetic progressions covering $\mathbb Z$ or an interval) that both #687 and #2 instantiate. - Sieve theory: Eratosthenes–Legendre, Brun, Selberg, Turán, and the large sieve — Iwaniec's 1978 upper bound and any tightening of it sits in the large-sieve / Turán-sieve toolkit.