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

Statement

Let $n$ be sufficiently large. Is there some choice of congruence class $a_p\pmod p$ for every prime $2\leq p\leq n$ such that every integer in $[1,n]$ satisfies at least two of the congruences $\equiv a_p\pmod p$? (erdosproblems.com/689, direct fetch 2026-07-02.)

Erdős asked this as a strengthening of the ordinary covering-system question Erdős #687 — estimate the Jacobsthal covering function Y(x) (every integer covered by $\geq1$ class): "Are there residues $c_p$ for every prime $p$ with $2\le p\le n$ so that every positive integer $x\le n$ satisfies at least 2 (or at least $r$) of the congruences $x\equiv c_p\pmod p$?" — verbatim from [Er79d, p.79], quoted in the forum thread. The natural generalization replaces $2$ by any fixed $r\geq2$ (for $n$ sufficiently large depending on $r$); erdosproblems.com records this explicitly. Ben Green's "100 Open Problems" list states the $r=10$ case as Problem 45, with the remark: "Erdős remarks that he does not know how to answer it with $10$ replaced by $2$" (people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf, p.22, fetched and read in full) — i.e. even Erdős considered $r=2$, the case asked on this page, to be the hard core of the question, not an easy warm-up.

This page documents two different things under one slug, and the distinction is the whole point: 1. The exact all-integers analogue — replace "primes $p\le n$" by "all integers $n'\le n$" — is erdos/1205, and it is fully, elementarily SOLVED: $F(x)\sim\log x$, where $F(x)$ is the best simultaneous covering multiplicity achievable using one class per modulus $n'\le x$. This is short, unconditional, and is the direct technical ancestor of the attack on #689. 2. The primes-only case, #689 itself, remains OPEN on erdosproblems.com as of 2026-07-02 — but as of April–June 2026 it has two independent full-solution-claim write-ups (Przemek Chojecki and a user "MalekZ"), both explicitly built on a proof *sketch* developed in the comments mainly by Terence Tao and Mehtaab Sawhney (Oct 2025), using genuinely heavy modern machinery (Green–Tao–Ziegler linear equations in primes + Kahn's 1996 fractional-relaxation/hypergraph-nibble theorem). Neither write-up has been peer-reviewed or independently verified by an expert as of the last site edit; the site owner (Thomas Bloom) has explicitly paused further AI-assisted submissions on this thread pending human expert review or journal publication.

Facts

- No prize is listed for #689 on the site (unlike the sibling single-cover problem Erdős #687 — estimate the Jacobsthal covering function Y(x), which carries a \$1000 Erdős prize). - Origin: Erdős, "Some unconventional problems in number theory," Acta Math. Acad. Sci. Hungar. (1979) [Er79d, p.79]; restated in "A survey of problems in combinatorial number theory," Ann. Discrete Math. (1980) [Er80, p.108]. Immediately preceded in the same source paragraph by Erdős #688 — the ε_n covering variant: how few large primes can cover [1,n]? (the $\epsilon_n$-restricted-prime-range single-cover variant). - See also (erdosproblems.com's own cross-references, verified): Erdős #687 — estimate the Jacobsthal covering function Y(x) (single cover, estimate $Y(x)$, open, \$1000), Erdős #688 — the ε_n covering variant: how few large primes can cover [1,n]? ($\epsilon_n$-variant, open), erdos/1205 (all-moduli double(+)-cover analogue, SOLVED), erdos/1139 ($\limsup$ gap between integers with $\Omega\le2$ prime factors, open — linked by Tao, see below). - A hard upper bound on $r$ in general: pigeonhole via $\sum_{p\le n}n/p\sim n\log\log n$ shows the maximum simultaneous multiplicity achievable with one class per prime $p\le n$ is at most $(1+o(1))\log\log n$ (forum comment, msawhney, 31 Oct 2025) — so "$r$ fixed and $n\to\infty$" is the right regime; the question is genuinely about small constant $r$, not about how large $r$ can grow with $n$. - Boundary finding (unproved, but a serious informal claim by Tao): after working the sieve numerology for $r=3$, Tao wrote (30 Oct 2025): "I am now leaning towards the $r\geq3$ version of this claim actually being false," based on a surviving-semiprime count that the standard strategy cannot clear for $r\ge3$ (a related follow-up comment by msawhney partially formalizes this obstruction). This means $r=2$ (the case on this page) may be the unique nontrivial solvable instance of the whole family — a sharp threshold phenomenon, if the $r=2$ claimed proofs and the $r\ge3$ heuristic obstruction both hold up. - Why #689 matters beyond itself: Tao observed (27 Jan 2026, cross-posted to erdos/1139) that a genuine 2-fold cover using *every* prime $p\le n$ (not a subset), combined with CRT, produces an explicit length-$n$ run of integers $N+1,\dots,N+n$ each divisible by $\ge2$ distinct primes $\le n$ and hence each with $\Omega\ge3$ — a strong, explicit form of the "long gaps between $P_2$-numbers" phenomenon relevant to erdos/1139. So a full solution to #689 is not just of intrinsic interest — it would mechanically hand over strong quantitative input to a second, separately-famous open problem. - Verification state (load-bearing fact for confidence rating): Thomas Bloom's pinned comment (2 Jun 2026): "This problem has now had two full solution claims posted by Chojecki and MalekZ, both using an earlier sketch developed here in comments mainly due to Sawhney and Tao. ... Given the subtleties and technicalities involved, I will await either publication of a solution in a peer-reviewed journal, or a careful look from an expert human (e.g. Sawhney or Tao), before updating the site." Both write-ups explicitly disclose heavy AI assistance (Chojecki: "many back-and-forths with GPT-5.5 Pro"; MalekZ: "prepared with AI assistance ... specifically from Claude and codex"). A third party (Nat Sothanaphan) ran "a standard check" that found no issue but explicitly called this "at least a serious solution candidate," not a confirmed proof.

Solution

**The genuinely solved piece — erdos/1205 (all integers as moduli, not just primes) — first, since it is the load-bearing, fully rigorous, transferable technique.**

Statement of erdos/1205: let $F(x)$ be maximal such that there is a congruence class $a_{n'}\pmod{n'}$ for every $n'\le x$ with every $m\le x$ satisfying at least $F(x)$ of these congruences. Answer: $F(x)\sim\log x$ (erdosproblems.com/1205, status SOLVED — "resolved in some other way than a proof or disproof," i.e. by an elementary/folklore-style argument rather than a landmark paper).

Proof (fully elementary, three moves — the direct template for the harder primes-only attack): 1. Pigeonhole upper bound. Every $m\le x$ that satisfies the congruence $\equiv a_{n'}\pmod{n'}$ contributes to at most $\lceil x/n'\rceil$ total "hits" across all $m\le x$ for modulus $n'$; summing, the total number of (integer, satisfied-congruence) incidences is $\le\sum_{n'\le x}(x/n'+1)=x\log x+O(x)$, and dividing by $x$ integers gives the *average* multiplicity is $\le\log x+O(1)$ — so the guaranteed minimum $F(x)$ cannot exceed this average: $F(x)\le\log x+O(1)$. 2. Random construction + concentration (the reusable core move). Choose each class $a_{n'}$ for $n'\le x/2$ independently and uniformly at random. For any fixed target $m\le x/2$, the number of covering congruences is a sum of independent Bernoulli-type indicators with $\mathbb E[\text{count}]=\sum_{n'\le x/2}1/n'=\log x+O(1)$. A Chernoff-type concentration bound then shows $\Pr[\text{count}<\log x-O(\sqrt{\log x\log\log x})]\le1/(\log x)^2$ for each $m$ — small enough that, by a union bound over all $O(x)$ targets, all but $O(x/(\log x)^2)$ of them are covered at least $\log x-O(\sqrt{\log x\log\log x})$ times *simultaneously*, for a single realization of the random classes. 3. Greedy singleton cleanup with reserved large moduli. The $O(x/(\log x)^2)$ exceptional stragglers are cleaned up one-at-a-time using the *remaining* moduli $x/2<n'\le x$ (each such modulus can be freely pointed at one specific straggler, and there are $\gg x$ of them available against only $O(x/(\log x)^2)\ll x$ stragglers) — each straggler in fact receives $\gg(\log x)^2$ extra hits this way, far more than enough. Combining: $\log x-O(\sqrt{\log x\log\log x})\le F(x)\le\log x+O(1)$, i.e. $F(x)\sim\log x$. 4. Why this is the transferable template. The generic three-step shape — *(a) pigeonhole for the trivial matching upper bound on achievable multiplicity) $\Rightarrow$ (b) i.i.d. random assignment + concentration to get near-uniform coverage almost everywhere) $\Rightarrow$ (c) reserve a sparse tail of "big" moduli purely for deterministic mop-up of the rare exceptional set)* is the skeleton of essentially every known attack on this whole covering-multiplicity problem family, including the unverified attack on #689 itself below. It is also, transparently, the same skeleton used decades earlier by Erdős–Rankin-style constructions for large prime gaps (Erdős #4 — unbounded large gaps between primes (Rankin's constant removed)) and by the FGKMT hypergraph-covering proof of the same (Erdős #687 — estimate the Jacobsthal covering function Y(x)'s Related section) — random/greedy sieve first, then a much harder "clean-up the tail efficiently" step is where all the technical difficulty concentrates.

The claimed (UNVERIFIED as of 2026-07-02) escalation to #689 itself — primes only, so step (b) above is no longer free.

The obstruction that separates #689 from its easy sibling #1205: restricting the moduli to *primes* $p\le n$ removes the freedom to use *every* integer as a modulus, so the same random-assignment step no longer trivially concentrates — a fixed prime $p$ only "sees" $n/p$ targets, and for primes $p>n/z$ (a large chunk of the prime-counting mass) that is a genuinely small, sparse set, meaning naive concentration bounds are too weak and a prime can only ever be pointed at $O(1)$–$O(z)$ targets rather than acting like an unrestricted random hash. The claimed solution route, developed collaboratively in the forum (msawhney, Tao, Dogmachine, Chojecki, MalekZ, Oct 2025–Jun 2026), replaces step (b)'s naive randomness with:

1. Deterministic small-prime "debt" setup. Fix $a_2\equiv1\pmod2$, leave $3$ in its zero class, and switch a fixed finite set $S\subset\{7,11,13,\dots\}$ of small primes to nonzero residues, reducing the "still needs a second hit" targets to a structured residual set (roughly: even numbers $2^ku\,q$ with $u$ odd $S$-smooth, $q\notin S$ prime, up to fixed congruence exclusions) of the correct order $(1+o(1))n/\log n$ by the prime number theorem. 2. A "robust prime" cleanup layer. Reserve primes $P>n/5$; call $P$ "robust" if it already resolves all the residual double-hit obligations on its small multiples $P,2P,3P,4P\le n$ without creating fresh unresolved debt. The fraction of robust primes among $(n/5,\beta n]$ can be pushed above $\approx0.944$ by choosing $S$ large enough — this numerical margin is exactly what later funds the singleton mop-up (mirroring #1205's step (3), but now the "spare capacity" has to be earned rather than being free). 3. Reduce the remaining bulk problem to a 3-partite hypergraph fractional-matching problem. Build vertex classes $X,Y$ (finite coefficient "cores" of the two main residual arithmetic-progression families) and $Z$ (the robust primes in a suitable range), with an edge $(x,y,P)$ whenever $|y-x|=2P$; a near-perfect matching in this hypergraph assigns each robust prime to resolve one $(x,y)$ pair simultaneously, which is the double-covering analogue of #1205's random hash. 4. Statistical control over which edges exist: Green–Tao–Ziegler "linear equations in primes." Because the edge/vertex weights here are governed by simultaneous linear prime-pattern counts (not single primes), the construction needs averaged asymptotics for systems of affine-linear forms in primes — exactly the machinery of Green & Tao, "Linear equations in primes," Ann. of Math. 171 (2010), 1753–1850, applied (per the write-ups) via an auxiliary $W$-trick or fixed-modulus singular-series computation to get first- and second-moment estimates for the hypergraph's edge loads. This is the modern replacement for classical sieve theory precisely because classical sieves cannot beat the "each prime only touches $O(z/\log z)$ useful targets" bottleneck that blocked this approach for decades (the identical bottleneck that historically blocked Rankin-style large-gap constructions until FGKMT's 2018 hypergraph-covering breakthrough on the closely related Erdős #687 — estimate the Jacobsthal covering function Y(x)/Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) problem — msawhney's comment states this parallel explicitly). 5. Turn the fractional/averaged matching into a genuine integral one: Kahn's 1996 theorem. Jeff Kahn, "A linear programming perspective on the Frankl–Rödl–Pippenger theorem," Random Structures & Algorithms 8 (1996), 149–157 — a fractional-relaxation generalization of the Rödl-nibble hypergraph matching theorem: given a fractional matching of total weight $(1-o(1))|Z|$ with vanishing maximum edge weight and vanishing pairwise codegree weight, there exists an *actual integral matching* covering $(1-o(1))|Z|$ vertices. The write-ups verify the hypergraph here has bounded (in fact $\le2$) codegree, which is exactly the hypothesis Kahn's theorem needs. 6. Final singleton cleanup, symmetric to #1205's step (3): the residual mass left uncovered by the matching (coefficient-tail targets outside the finite cores, plus the small number of unmatched vertices) is mopped up one-at-a-time using leftover unused robust primes, funded by the strict surplus margin computed in step 2. 7. What is explicitly NOT yet nailed down (self-reported open interfaces in the claimed proofs, as of the last update): (a) whether Kahn's Theorem 1.5 conclusion, in its exact printed form, really delivers an integral matching of the needed size from the stated fractional hypotheses (the author reports being unable to access the printed 1996 paper and could only confirm the hypothesis, not the conclusion, from secondary sources); (b) whether the local-factor/singular-series disintegration of the second-moment Green–Tao–Ziegler systems is fully correct across all of systems (22)–(24) in the write-up — flagged by the author as the two places "independent eyes would matter most."

Bottom line for downstream use: the reusable, *load-bearing and fully verified* export from this problem-pair is the three-step covering-multiplicity template — (i) pigeonhole for the trivial upper bound, (ii) random-or-structured assignment for near-uniform bulk coverage, (iii) reserve a thin tail of large/robust moduli purely for deterministic singleton mop-up, funded by a provable surplus margin — demonstrated completely rigorously by erdos/1205. The claimed but unverified export, valuable to note for any open problem depending on it, is that this template appears to survive the much harsher "primes only" restriction *provided* one is willing to import Green–Tao–Ziegler linear-equations-in-primes machinery for step (ii) and Kahn's fractional-hypergraph-matching theorem for converting the resulting fractional cover into an honest one — i.e. #689, if the 2026 claims hold up, would be genuine new evidence that the GTZ + Kahn combination is powerful enough to crack a sieve-theoretic covering-multiplicity obstruction that classical sieve theory alone could not, in the same way FGKMT's Rödl-nibble hypergraph covering theorem cracked the large-prime-gaps obstruction that classical Rankin-type sieving alone could not (Erdős #687 — estimate the Jacobsthal covering function Y(x), Erdős #4 — unbounded large gaps between primes (Rankin's constant removed)). Any open problem wanting to borrow "the technique that (claims to) solve #689" should borrow exactly this GTZ-moments + Kahn-fractional-rounding combination, while flagging — as this page does — that as of 2026-07-02 it has not cleared peer review.

Related

- erdos/1205 — the all-moduli (not just primes) analogue; fully SOLVED, $F(x)\sim\log x$, elementary proof (pigeonhole + random/Chernoff + greedy cleanup) — the rigorous technical ancestor of the #689 attack, and the only fully verified "solved" content directly underlying this page. - Erdős #687 — estimate the Jacobsthal covering function Y(x) — the single-cover ($\geq1$ class) primes-only sibling, estimate $Y(x)$; open, \$1000 prize; same object, weaker covering requirement; shares the "classical sieve bottleneck, cracked historically only by Rödl-nibble/hypergraph-covering machinery" structural story with #689's claimed solution route. - Erdős #688 — the ε_n covering variant: how few large primes can cover [1,n]? — the $\epsilon_n$-restricted-prime-range single-cover variant; open; same original source paragraph [Er79d,p.79] as #689. - Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) — unbounded large prime gaps; PROVED by Ford–Green–Konyagin–Maynard–Tao via Rödl-nibble hypergraph covering (arXiv:1412.5029); the historical precedent for "linear-equations-in-primes + hypergraph-nibble machinery cracks a sieve-theoretic covering obstruction," which is exactly the claimed shape of the (unverified) #689 solution. - erdos/1139 — $\limsup$ of gaps between consecutive integers with $\le2$ prime factors; Tao's comment (27 Jan 2026) shows a full "strong form" solution to #689 (using *all* primes $\le n$) would mechanically imply strong quantitative progress here via CRT. - Covering systems of congruences — the general object (arithmetic progressions covering $\mathbb Z$ or an interval) instantiated by #689, #687, #688, #1205, and Erdős #2 — minimum modulus of a covering system cannot be arbitrarily large. - Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings — the semi-random hypergraph-matching method (Kahn 1996 is a fractional-relaxation generalization of this family) underlying both the FGKMT proof for Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) and the claimed #689 matching-rounding step. - concept/linear-equations-in-primes — Green–Tao–Ziegler machinery (Green & Tao, Ann. of Math. 2010) supplying the averaged simultaneous-prime-pattern moment estimates the claimed #689 proof needs in place of classical sieve theory. - concept/dyadic-harmonic-summation / Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the Chernoff-concentration step in #1205's proof is a first-moment/second-moment-flavored concentration argument in the same broad toolkit already catalogued elsewhere in this wiki (e.g. erdos/1.md, erdos/65.md).