Duffin–Schaeffer conjecture / metric Diophantine approximation (Koukoulopoulos–Maynard theorem)

Statement

The Koukoulopoulos–Maynard theorem (formerly the Duffin–Schaeffer conjecture, Duffin & Schaeffer 1941, "Khintchine's problem in metric diophantine approximation," *Duke Math. J.* 8: 243–255): let $\psi:\mathbb N\to\mathbb R_{\ge0}$ be an arbitrary function. Call $\alpha\in\mathbb R$ $\psi$-approximable (by reduced fractions) if $$\left|\alpha-\frac{a}{q}\right| \;<\; \frac{\psi(q)}{q}$$ holds for infinitely many *reduced* fractions $a/q$ (i.e. $\gcd(a,q)=1$, $q>0$). Let $\mathcal A(\psi)$ be the set of such $\alpha$. Then, for almost every real $\alpha$ (Lebesgue measure), $\alpha\in\mathcal A(\psi)$ if and only if $$\sum_{q=1}^{\infty} \frac{\varphi(q)\,\psi(q)}{q} \;=\; \infty,$$ where $\varphi$ is Euler's totient (en.wikipedia.org/wiki/Duffin–Schaeffer_conjecture; abstract of arXiv:1907.04593). Equivalently: $\mathcal A(\psi)$ has full Lebesgue measure in every bounded interval if the sum diverges, and Lebesgue measure zero if it converges — a genuine zero-one law, with the $\varphi(q)/q$ weight (density of reduced residues mod $q$) as the exact arithmetic correction needed once one restricts to *reduced* fractions.

The "only if" direction (convergence $\Rightarrow$ measure zero) is elementary — a direct Borel–Cantelli / covering argument, essentially already understood by Duffin–Schaeffer in 1941. The "if" direction (divergence $\Rightarrow$ full measure) is the hard, formerly-conjectural part; it was open from 1941 until proved by Dimitris Koukoulopoulos and James Maynard in 2019 (arXiv:1907.04593, published *Annals of Mathematics* 192(1), 2020, 251–307).

Contrast with Khintchine's theorem (1926): for *monotonic* (non-increasing) $\psi$, almost every $\alpha$ is $\psi$-approximable (by *any*, not necessarily reduced, $a/q$) iff $\sum_q \psi(q)$ diverges — no $\varphi(q)/q$ correction needed (en.wikipedia.org/wiki/Diophantine_approximation). Duffin–Schaeffer's 1941 contribution was to observe that once $\psi$ is allowed to be non-monotonic, Khintchine's criterion can simply fail — there exist $\psi$ with $\sum\psi(q)=\infty$ for which almost every $\alpha$ has only finitely many *reduced*-fraction solutions — because Khintchine's proof secretly double-counts approximations that are non-reduced multiples of each other. Restricting to reduced $a/q$ and correcting by $\varphi(q)/q$ is the fix, and pinning down whether that fixed criterion is *itself* always correct (for arbitrary $\psi$, not just monotonic ones) is exactly the 80-year conjecture (quantamagazine.org/new-proof-settles-how-to-approximate-numbers-like-pi-20190814).

Facts

- Dirichlet's theorem (1837) is the $\psi(q)=1$ baseline: every irrational $\alpha$ has infinitely many reduced $a/q$ with $|\alpha-a/q|<1/q^2$ — Duffin–Schaeffer generalizes this to arbitrary denominator-dependent error/weight functions and asks for the *typical* (a.e.) rather than *universal* (every $\alpha$) answer. - Erdős (1970) proved the special case $\psi(q)\in\{0,\,c/q\}$ for a fixed constant $c$; Vaaler (1978) extended this to $\psi(q)=O(1/q)$ using sieve methods (jointly sometimes cited as the "Erdős–Vaaler" bounded-$q\psi(q)$ regime) — these cover the case where the approximation quality never gets *too* good relative to Dirichlet's baseline. - Pollington & Vaughan (1990), "The $k$ dimensional Duffin–Schaeffer conjecture" (*Mathematika* 37(2): 190–200): proved the natural simultaneous-approximation analogue in dimension $k\ge2$ unconditionally — the higher-dimensional problem turned out to be strictly easier than the $k=1$ case, which is why the 1-dimensional conjecture remained the outstanding open case for another three decades. - Beresnevich & Velani (2006), "A mass transference principle and the Duffin–Schaeffer conjecture for Hausdorff measures" (*Ann. of Math.* 164(3): 971–992): proved that a Hausdorff-measure-refined version of the conjecture is equivalent to the original Lebesgue-measure statement — so Koukoulopoulos–Maynard's 2019 proof automatically also settles the finer Hausdorff-measure/dimension question for full-dimensional $\psi$-approximable sets, via their mass transference principle. - Haynes, Pollington & Velani (2012) (*Math. Ann.* 353(2): 259–273) and Aistleitner (2014), "A note on the Duffin–Schaeffer conjecture with slow divergence" (*Bull. LMS*, doi:10.1112/blms/bdt085), and arXiv:1803.05703 ("The Duffin–Schaeffer conjecture with extra divergence"): a sequence of partial results proving the conjecture whenever the divergence of $\sum\varphi(q)\psi(q)/q$ is "fast enough" or survives an extra $\varepsilon$-log-power thinning — narrowing the gap right up to the borderline (barely-divergent) case that Koukoulopoulos–Maynard finally closed unconditionally. - Koukoulopoulos & Maynard (2019/2020), arXiv:1907.04593, *Annals of Mathematics* 192(1): 251–307 — the full unconditional resolution, via a new technique they call GCD graphs (see Technique below). - Follow-up / quantitative refinements: Koukoulopoulos–Maynard–Yang proved an almost-sharp *quantitative* (effective rate, not just zero-one) version using GCD graphs; arXiv:2404.15123 ("Proving the Duffin–Schaeffer conjecture without GCD graphs," 2024) and arXiv:2409.10386 ("Almost-sharp quantitative Duffin–Schaeffer without GCD graphs," 2024) give alternative proofs of comparable strength that avoid the delicate GCD-graph "quality" estimates entirely, replacing them with more direct sieve/overlap arguments. - Open extensions: the multiplicative Duffin–Schaeffer conjecture (simultaneous approximation with a *product* of distances $\prod_i\|q\alpha_i\|$ rather than a sum/max, closely tied to the still-open Littlewood conjecture) remains open beyond partial results — see arXiv:2403.11257, "The Duffin–Schaeffer Conjecture for multiplicative Diophantine approximation" (2024). - Direct reuse in this wiki's problem corpus: Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity? documents Koukoulopoulos–Lamzouri–Lichtman (arXiv:2502.09539, Feb 2025) transplanting the GCD-graph machinery verbatim from this proof to resolve an unrelated question about primitive/integer-dilation sets — concrete evidence that GCD graphs are reusable derivation fuel, not a one-off trick.

HOW it is used to prove things (recombination steps)

1. Recognize the shape: a problem is a Duffin–Schaeffer-type question whenever it asks "for almost every real $\alpha$ (or point in a measure space), does a naturally-indexed sequence of shrinking target sets $A_q$ hit $\alpha$ infinitely often?", where $A_q$ is built from reduced-fraction / coprimality-constrained data indexed by an integer $q$, and the natural first-moment guess is $\sum_q |A_q|$ (Borel–Cantelli heuristic). 2. Easy half via Borel–Cantelli: if $\sum_q|A_q|<\infty$, almost every point lies in only finitely many $A_q$ — this direction is always cheap and was never the obstruction. 3. Hard half needs quasi-independence, not full independence: to upgrade $\sum_q|A_q|=\infty$ to "almost every point lies in infinitely many $A_q$" one cannot use full Borel–Cantelli-converse (that needs true independence); instead one needs a second-moment / Erdős–Rényi–Kochen-Stone-type criterion controlling *pairwise overlaps* $|A_q\cap A_r|$ on average, so that the variance of $\sum_{q\le Q}\mathbf 1_{A_q}$ stays comparable to its mean. In the Duffin–Schaeffer setting the overlap $|A_q\cap A_r|$ is governed by $\gcd(q,r)$: fractions $a/q,\,b/r$ with a large common factor between $q,r$ can coincide or nearly coincide, breaking naive independence — this gcd-driven correlation is exactly the 80-year obstruction, because it can be arbitrarily bad for adversarially chosen non-monotonic $\psi$. 4. Encode the obstruction as a graph (Koukoulopoulos–Maynard's move): build a GCD graph on the finite vertex set $\{q\le Q:\psi(q)>0\}$, joining $q,r$ by an edge (or weighting an edge) when they share a large enough common factor *relative to* $\psi(q),\psi(r)$ that the pair contributes non-negligibly to the "bad" overlap sum $\sum_{q\ne r}\gcd(q,r)\cdot(\text{quality terms})$. The graph is literally a visual/combinatorial encoding of which denominators can interfere with which — "the graph's configuration precisely captures the measure-theoretic relationships determining convergence or divergence" (quantamagazine.org). 5. Bound the graph, not the analysis directly: reduce the required overlap estimate to a purely combinatorial statement about this graph (edge density / clustering), then discharge that combinatorial statement using number-theoretic input on the "anatomy of integers" — refined sieve-theoretic overlap estimates and results on the typical distribution of divisors of integers in dyadic ranges (the same family of tools behind Ford's work on the multiplication-table problem, $H(x,y,z)$). This separates "hard combinatorics of a specific $\psi$" from "universal facts about how integers factor," and it is the latter that Koukoulopoulos–Maynard could prove unconditionally. 6. Conclude via the zero-one law: once quasi-independence is established for the divergent case, a Cassels/Gallagher-type 0-1 law (the limsup set $\mathcal A(\psi)$ always has measure $0$ or full measure in any interval, independent of the exact divergence criterion) finishes the proof — divergence of $\sum\varphi(q)\psi(q)/q$ forces full measure. 7. Transplant elsewhere: because steps 3–5 are really "controlling gcd-correlated overlaps among an integer-indexed family of measure-$O(1/q)$ sets/quantities," the same GCD-graph + anatomy-of-integers machinery transplants directly to *other* problems with the same correlation structure — e.g. Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity?'s integer-dilation/primitive-set question (arXiv:2502.09539), which is not a Diophantine-approximation problem at all but has the identical gcd-overlap obstruction.

WHEN it applies: any metric ("almost every point") question reducible to a divergence/convergence criterion for a sum $\sum_q w(q)$ over integers, where the events/sets being unioned are indexed by $q$ and their pairwise overlaps are controlled by $\gcd(q,r)$ — classically: Diophantine approximation by reduced fractions with arbitrary (non-monotonic) approximation functions, simultaneous/multiplicative approximation variants, Hausdorff-measure refinements of approximation-type sets (via Beresnevich–Velani mass transference once the Lebesgue case is known). More broadly, any 0-1-law/Borel–Cantelli-converse argument that stalls specifically because of gcd-driven double-counting between terms of an integer-indexed family is a candidate for the GCD-graph treatment.

WHY it works (the mechanism): the classical approach (Khintchine, Erdős, Vaaler, Pollington–Vaughan) tried to bound the overlap sum $\sum_{q,r\le Q}|A_q\cap A_r|$ directly via analytic/sieve estimates, which only closed for *monotonic* or *slowly-varying* $\psi$ because adversarial non-monotonic $\psi$ can concentrate mass on integers with unusually rich common-divisor structure, defeating naive bounds. Recasting the same sum as a weighted graph turns "bound an analytic double sum for *every* admissible $\psi$" into "bound the edge-density/expansion of a graph built from the *support* of $\psi$," which can be attacked with combinatorial tools (independent of the fine values of $\psi$) plus a universal number-theoretic fact about how integers' divisors are distributed (anatomy of integers) — decoupling the arithmetic worst-case from the graph worst-case is what finally closed the 80-year gap.

Related

- GCD graphs (Koukoulopoulos–Maynard graph-theoretic sieve) — the graph-theoretic device itself (vertices = denominators/integers, edges = shared-common-factor overlap), invented for this proof and independently reused verbatim by Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity?'s resolution (arXiv:2502.09539). - Sieve theory: Eratosthenes–Legendre, Brun, Selberg, Turán, and the large sieve — the "anatomy of integers" / refined overlap estimates that discharge the combinatorial GCD-graph bound are sieve-theoretic in flavor (large-sieve-style divisor-distribution control), the same toolkit family documented on that page. - Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity? — Erdős's integer-dilation/primitive-set approximation problem; the GCD-graph machinery from this exact theorem is transplanted wholesale by Koukoulopoulos–Lamzouri–Lichtman (arXiv:2502.09539) to prove the $o(\log n)$ sub-question unconditionally, the clearest documented instance in this wiki of this concept as reusable derivation fuel.