Erdős #688 — the ε_n covering variant: how few large primes can cover [1,n]?

Statement

For each $n$, define $\epsilon_n$ to be the extremal value (Erdős's own 1979 wording: "the smallest number so that...") such that there is a choice of residue class $b_p$ for every prime $p$ with $n^{\epsilon_n} < p \le n$, so that every integer $x\in[1,n]$ satisfies at least one of the congruences $x\equiv b_p\pmod p$ — i.e. a covering of $[1,n]$ built using *only the large primes above* $n^{\epsilon_n}$, with every prime $\le n^{\epsilon_n}$ discarded. (erdosproblems.com's modern restatement phrases $\epsilon_n$ as the *maximal* $\epsilon$ for which such a covering still exists — the two phrasings describe the same threshold value, from opposite sides.)

Question

estimate $\epsilon_n$. In particular, is it true that $\epsilon_n = o(1)$ — i.e. does the fraction of "discardable small primes" needed shrink to nothing as $n\to\infty$, or is a positive-power range of primes below $n$ always structurally necessary?

Facts

- Status: OPEN. Confirmed by direct fetch of erdosproblems.com/688 (2026-07-02): "This is open, and cannot be resolved with a finite computation." Zero forum comments; no partial or complete solution claimed anywhere in the record. - Origin: Erdős, "Some unconventional problems in number theory," *Acta Math. Acad. Sci. Hungar.* 33 (1979) 71–80 [Er79d] — primary source fetched and read directly. It appears on p.79, immediately after Erdős discusses $B(n)$ (his notation for the object now called $Y(x)$, Erdős #687 — estimate the Jacobsthal covering function Y(x)) — Iwaniec's lower bound $B(n)>c\sqrt n$ and a Rankin-method upper bound $B(n) < cn(\log\log\log n)^2/(\log n\log\log n\log\log\log\log n)$. Erdős then writes: *"Recently, I considered the following modification of the above problem... I can prove that $\epsilon_n>c\log\log\log n/\log\log n$."* Restated in "A survey of problems in combinatorial number theory," Ann. Discrete Math. (1980) 89–115 [Er80, p.106]. - The one proven piece — a genuinely solved sub-result inside an open problem: $$\epsilon_n \gg \frac{\log\log\log n}{\log\log n}.$$ This lower bound is due to Erdős himself (1979/1980) and is the *only* rigorously established fact about $\epsilon_n$ found anywhere in the literature search (2026-07-02) — no improvement, no matching upper bound, and no resolution of the $o(1)$ question has been published in the 45+ years since. This is independently corroborated by the machine-formalized statement: google-deepmind/formal-conjectures/FormalConjectures/ErdosProblems/688.lean tags the *general* lower-bound, upper-bound, and $o(1)$-dichotomy sub-theorems all research open (each body is sorry), while carving out precisely this one bound as its own separate lemma erdos_688.variants.lglglg_over_lglg_is_big_o tagged research solved — an independent, structurally-forced confirmation that this specific inequality is the field's one settled fact about $\epsilon_n$. - Caveat on the word "solved": even this lemma's Lean *proof* is still sorry (unformalized) — "solved" here means mathematically established/published by Erdős, not yet machine-checked. - Erdős's 1979 paper states the bound with no proof or proof sketch (contrast with Theorem 1 earlier in the same paper, which he does prove in full in §4) — the technique is not recoverable from the primary source itself. - What remains genuinely open: any upper bound on $\epsilon_n$ (i.e. any argument ruling out an even more efficient covering that reaches further down in prime size), and the headline dichotomy question $\epsilon_n=o(1)$ vs. $\epsilon_n \gg 1$. The known lower bound $\gg\log\log\log n/\log\log n \to 0$ is consistent with *either* answer to that dichotomy — it constrains how fast $\epsilon_n$ can shrink but does not itself decide whether it shrinks to $0$ at all. - Direction of the bound (constructive, not an impossibility result): $\epsilon_n\ge V$ means "exhibit an actual covering of $[1,n]$ that only uses primes down to $n^{V}$" — i.e. proving a *lower* bound on $\epsilon_n$ is a *constructive/existence* task (build a covering), the same logical shape as the $Y(x)$ *lower* bound on Erdős #687 — estimate the Jacobsthal covering function Y(x) (built by FGKMT's hypergraph-covering machinery) and as Rankin's classical $B(n)$ *upper* bound quoted in the same paragraph of [Er79d]. The genuinely hard, still-open direction — an upper bound on $\epsilon_n$ / ruling out coverings that reach even further down — is structurally an *impossibility* proof, the same hard direction that has stalled $Y(x)$'s upper bound (Iwaniec 1978, unimproved) on the sibling problem Erdős #687 — estimate the Jacobsthal covering function Y(x). - Best-supported inference on technique (flagged, not confirmed from a primary proof text): Erdős states the Rankin-method construction for $B(n)$'s upper bound in the sentence immediately preceding his statement of the $\epsilon_n$ bound, in the same paragraph, with the identical $(\log\log\log n)$-vs-$(\log\log n)$ iterated-logarithm shape. This strongly suggests — but does not prove, since no proof is given — that Erdős's $\epsilon_n$ lower bound is obtained by the same Rankin-style explicit congruence-covering construction (see Erdős–Rankin construction (covering-congruences translation for large prime gaps)): choose a chain of primes with reciprocal sum controlled at dyadic/iterated-log scales via Mertens' theorem ($\sum_{n^\epsilon<p\le n}1/p \sim \log(1/\epsilon)$ by Mertens' second theorem), and use CRT to assign residues covering $[1,n]$ using only that restricted, large-prime range. No independent secondary source verifying this technique transfer was found. - Dependency structure — why this problem matters to other open problems: erdosproblems.com/1200 states explicitly that a related conjecture of Erdős and Ruzsa (that a bounded-reciprocal-sum family of primes always leaves a positive-density uncovered set, erdos/1200) would very likely follow if $\epsilon_n \gg 1$ is proved — "certainly proving $\epsilon_n\ge c$ would prove this conjecture (taking $P$ to be all primes in $[x^c,x]$)." So any future strengthening of the $\epsilon_n$ lower bound to a genuine constant (not just $\to 0$ slowly) would directly resolve erdos/1200 — the clearest concrete illustration of what "open problems depend on this" means for #688. - No AI/LLM contribution found for #688 as of this search (2026-07-02); the Lean scaffold exists (statement formalized) but every proof body is sorry.

Related

- Erdős #687 — estimate the Jacobsthal covering function Y(x) — the parent problem: $Y(x)$ (Erdős's $B(n)$ in the same 1979 paragraph), the *unrestricted* covering-function analogue (use *any* primes $\le x$, ask how large an interval $[1,y]$ can be covered). #688 restricts the tool-set to only the top primes $(n^{\epsilon_n},n]$ and asks how far down that restriction can be pushed while a covering still exists. Both share Iwaniec's and Rankin's techniques as the immediate historical starting point (same paragraph of [Er79d]). - 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 $\ge2$ of the congruences, using *all* primes $\le n$); explicitly cross-listed as "See also" on erdosproblems.com/688. - erdos/1200 — Erdős–Ruzsa conjecture (any bounded-$\sum 1/p_i$ prime/congruence family leaves a positive-density uncovered set); erdosproblems.com/1200 states directly that proving $\epsilon_n\ge c$ for #688 would prove this conjecture — the clearest documented instance of a problem that *depends on* #688's (still-open) headline question, though not on the one piece of #688 that is actually solved. - Erdős–Rankin construction (covering-congruences translation for large prime gaps) — the classical explicit-covering-construction method (chaining primes/moduli via CRT with reciprocal sums controlled at iterated-log scale via Mertens' theorem) that gives Rankin's $B(n)$ upper bound in the same paragraph of [Er79d], and is the best-supported (though unconfirmed) candidate technique behind Erdős's $\epsilon_n\gg\log\log\log n/\log\log n$ lower bound. - Covering systems of congruences — the general object (one congruence class per prime/modulus, covering an interval or all of $\mathbb Z$) that #687, #688, #689, and #1200 all instantiate. - concept/mertens-theorems — the prime-reciprocal-sum estimate $\sum_{n^\epsilon<p\le n}1/p\sim\log(1/\epsilon)$ underlying any construction or counting argument that restricts a covering to a shrinking upper range of primes. - Machine formalization of infinitary combinatorics proofs (Isabelle/HOL, Lean) — google-deepmind/formal-conjectures/FormalConjectures/ErdosProblems/688.lean formalizes all four sub-statements (two-sided rate estimate, the $o(1)$ dichotomy, and Erdős's proven bound as a separate lemma) with sorry proof bodies; the "research solved" vs. "research open" category split in that single file is itself independent evidence for exactly which one fact about $\epsilon_n$ is actually established.