Duffin–Schaeffer conjecture (1941) — the divergence criterion for metric Diophantine approximation by reduced fractions

Statement

Fix $\psi:\mathbb N\to\mathbb R_{\ge0}$, an arbitrary function ("approximation function"). For $\alpha\in[0,1]$, say $\alpha$ is $\psi$-approximable by reduced fractions if $$\left|\alpha-\frac{a}{q}\right|\le\frac{\psi(q)}{q}$$ holds for infinitely many pairs of coprime integers $a,q$ ($\gcd(a,q)=1$). Let $$A_q:=[0,1]\cap\bigcup_{\substack{1\le a\le q\\ \gcd(a,q)=1}}\Big[\tfrac{a-\psi(q)}{q},\tfrac{a+\psi(q)}{q}\Big],\qquad A:=\limsup_{q\to\infty}A_q$$ be the set of such $\alpha$ (Koukoulopoulos–Maynard, arXiv:1907.04593, (1.3)–(1.4), read verbatim). The "easy" Borel–Cantelli direction always gives $$\sum_{q=1}^\infty \frac{\phi(q)\psi(q)}{q}<\infty \implies \lambda(A)=0.$$

Duffin–Schaeffer conjecture (R. J. Duffin, A. C. Schaeffer, 1941; Problem 46 in Montgomery's lectures): the converse also holds — $$\sum_{q=1}^\infty \frac{\phi(q)\psi(q)}{q}=\infty \implies \lambda(A)=1.$$

Here $\phi$ is Euler's totient function; its appearance (rather than $\psi(q)$ alone, as in Khinchin's earlier theorem) is exactly what accounts for restricting to *reduced* fractions and is the crux of why the problem is hard — Khinchin's 1924 theorem proves the same dichotomy for $K_q=[0,1]\cap\bigcup_{0\le a\le q}[a/q\mp\psi(q)/q]$ (all fractions, not just reduced) under the extra hypothesis that $q\psi(q)$ is decreasing; Duffin and Schaeffer showed that hypothesis is not necessary and that the totient-weighted reduced-fraction sum is the fully general correct criterion.

Facts

- Origin: R. J. Duffin, A. C. Schaeffer, "Khintchine's problem in metric Diophantine approximation," *Duke Math. J.* 8 (1941), 243–255. They proved their own conjecture under a regularity condition ($\limsup_{Q\to\infty}\frac{\sum_{q\le Q}\psi(q)\phi(q)/q}{\sum_{q\le Q}\psi(q)}>0$), which forced $\phi(q)/q$ to behave like a constant on average. - Special-case progress before 2019 (all read directly from arXiv:1907.04593 §1's history paragraph): Walfisz (predating the conjecture) showed Khinchin's theorem implies Duffin–Schaeffer whenever $q\psi(q)$ is decreasing; Erdős (1970) and then Vaaler (1978) proved the conjecture for $\psi(q)=O(1/q)$; Pollington–Vaughan (1990) proved the $d$-dimensional analogue for every $d\ge2$ (the extra dimensions give enough independence that the 1-D obstruction disappears); Haynes–Pollington–Velani (2006), Beresnevich–Harman–Haynes–Velani (2013), and Aistleitner–Lachmann–Munsch–Technau–Zafeiropoulos proved versions with a slightly *stronger* divergence hypothesis (e.g. $\sum\phi(q)\psi(q)/(q(\log q)^\varepsilon)=\infty$), progressively weakening the extra log-power loss. - Equivalences established before the full proof: Beresnevich–Velani (*Annals of Math.*, 2006) proved a Hausdorff-measure refinement is *equivalent* to the Duffin–Schaeffer conjecture itself — so proving the Lebesgue-measure statement automatically pins down $\dim_H(A)$ for every $\psi$ (Corollary 3 of arXiv:1907.04593, stated with $s=\inf\{\beta: \sum\phi(q)(\psi(q)/q)^\beta<\infty\}$, $\dim_H(A)=\min(s,1)$). - Full conjecture proved: Dimitris Koukoulopoulos and James Maynard, "On the Duffin-Schaeffer conjecture," arXiv:1907.04593 (announced July 2019 at the Second Symposium on Analytic Number Theory, Cetraro; final version *Annals of Mathematics* 192 (2020), 251–307). As a corollary they also prove Catlin's conjecture on the analogous problem for *non-reduced* fractions, refining Khinchin's theorem to arbitrary (non-monotone) $\psi$. - Why the direct/naive approach fails: by Gallagher's 0-1 law (Lemma 5.1, cited to Gallagher 1961), $\lambda(A)\in\{0,1\}$ always, so it suffices to show $\lambda(A)>0$; a standard second-moment/Cauchy–Schwarz argument (§5) reduces this to bounding the *pairwise correlation* $\lambda(A_q\cap A_r)/(\lambda(A_q)\lambda(A_r))$ for $q\ne r$ (Lemma 5.3, citing Pollington–Vaughan's correlation estimate), which is controlled by $\prod_{p\mid qr/\gcd(q,r)^2,\ p>M(q,r)/\gcd(q,r)}(1+1/p)$ — this product blows up exactly when $q,r$ share many small prime factors relative to their size, i.e. the sets $A_q$, $A_r$ overlap far more than independence would predict. Quantifying this excess overlap — for *all* possible fine divisor structures of a set of $q$'s, not just special families — is precisely the 80-year obstruction (Quanta, quantamagazine.org/new-proof-settles-how-to-approximate-numbers-like-pi-20190814, fetched). - The Model Problem that isolates the hard core (arXiv:1907.04593 §3, read verbatim): given $S\subseteq[x,2x]$ with $\#S\asymp x^c$ such that $\#S^2/100$ pairs have $\gcd(a_1,a_2)>x^{1-c}$, must some fixed $d\gg x^{1-c}$ divide $\gg\#S$ elements of $S$? The literal answer is no (a counterexample is discussed in the paper's §15, connected to the Catlin-conjecture counterexample), but a technical bipartite variant sufficient for the proof does hold. - Journal/venue: *Annals of Mathematics* 192 (2020), 251–307; announced 2019. Simplified/alternative reproofs of the (near-sharp quantitative) result that avoid GCD graphs entirely were later given by Hauke, Vazquez Saez, and Walker, arXiv:2404.15123 and arXiv:2409.10386 (2024), "motivated by the ideas of Koukoulopoulos–Maynard's breakthrough" but restructuring the argument to sidestep the explicit graph "quality" bookkeeping. - Downstream reuse of the exact technique: Koukoulopoulos, Lamzouri, Lichtman, "Erdős's integer dilation approximation problem and GCD graphs," arXiv:2502.09539 (Feb 2025), transplant the GCD-graph machinery of this paper, essentially verbatim, from Diophantine approximation to a primitive-set/integer-dilation sparsity problem — see Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity? in this wiki, already documented as a live downstream consumer of this exact technique.

Solution

Answer: the conjecture is TRUE. For every $\psi:\mathbb N\to\mathbb R_{\ge0}$, $\sum_q \phi(q)\psi(q)/q=\infty \implies \lambda(A)=1$ (Koukoulopoulos & Maynard, 2019/2020).

**The transferable technique — turn an intractable "bound the average pairwise correlation over *all* divisor structures" sum into a graph-compression argument that isolates the one bad structure (a fixed common divisor) and pays for it with an Erdős–Vaaler-type small-prime tail bound:**

1. Reduce measure to a second-moment/correlation sum. Gallagher's 0-1 law collapses "prove $\lambda(A)=1$" to "prove $\lambda(A)>0$," and Cauchy–Schwarz on the counting function $Q(\alpha)=\#\{q\in[X,Y]:\alpha\in A_q\}$ turns that into bounding $\sum_{q,r}\lambda(A_q\cap A_r)$ from above by a constant multiple of $\big(\sum_q\lambda(A_q)\big)^2$ (Proposition 5.4, the "Second Moment Bound"). This is a completely standard move — every one of the pre-2019 partial results uses it too. What differs is what comes next.

2. Isolate the sole obstruction: pairs $(q,r)$ with an unusually large $\gcd$. The correlation bound $\lambda(A_q\cap A_r)/(\lambda(A_q)\lambda(A_r))$ is controlled by an Euler product over primes dividing $qr/\gcd(q,r)^2$ that exceed a threshold $M(q,r)/\gcd(q,r)$ — this product is $O(1)$ (i.e. near-independence holds) *unless* $q,r$ share many small prime factors relative to $\gcd(q,r)$'s size. So the entire proof reduces to bounding $\sum_{q,r:\ \gcd(q,r)\ge x^{1-c}/t}\phi(q)\phi(r)/(qr)$ — a purely combinatorial/number-theoretic sum over pairs with abnormally large common divisors, stripped of all measure theory.

3. Bipartite compression: iteratively force a single common divisor structure. Set $V_0=W_0=S$ (the bad set of denominators) and repeatedly pick a prime $p_{j+1}$ dividing $\gcd(v,w)$ for some surviving edge $(v,w)$, then split $V_j,W_j$ into the sub-collection divisible by $p_{j+1}$ vs. coprime to it, keeping whichever side is consistent with a growing "quality" potential (this is the paper's GCD graph: vertices are denominators, edges join pairs with anomalously large $\gcd$ — a graph-theoretic encoding of exactly the divisor overlap that the direct sum couldn't handle). This compression is explicitly modeled on the Erdős–Ko–Rado shifting technique and Dyson's transposition method — genealogically the same family of "iteratively simplify by forcing structure while controlling a monovariant" arguments as Roth-type density increment, but tuned differently. 4. The monovariant that actually works. A naive density increment ($\delta_j=$ edge-density of the surviving bipartite graph) loses control of the set sizes; a naive size-product ($\#V_j\cdot\#W_j\cdot a_jb_j/\gcd(a_j,b_j)^2$, weighting by the fixed divisors forced so far) isn't monotone either. The quantity that is provably non-decreasing under the right choice of splits is the hybrid $\delta_j^{10}\cdot\#V_j\#W_j\cdot a_jb_j/\gcd(a_j,b_j)^2$ — the tenth power of the density times the size-product term. Iterating until the graph terminates in a state where every edge $(v,w)$ satisfies $\gcd(v,w)=\gcd(a,b)$ *exactly*, for fixed $a\mid$ all of $V$, $b\mid$ all of $W$, converts the arbitrary divisor sum into a single, explicitly computable geometric-style bound. 5. Close the last gap with an inherited exponential tail estimate. After compression, the residual factor of $t^{12}$ (from the threshold parameter $t$) is won back using the Erdős (1970)/Vaaler (1978) small-prime tail bound $\#\{n<x:\sum_{p\mid n,\ p\ge t}1/p\ge1\}\ll e^{-t}x$ — literally the same estimate that let Erdős and Vaaler settle the $\psi(q)=O(1/q)$ special case fifty years earlier. The technique's real innovation is not a new elementary estimate but a new way to reduce the fully general problem to the exact situation where the old elementary estimate already applies — the compression argument manufactures, out of an arbitrary bad divisor structure, precisely the "one fixed common divisor + few small shared primes" configuration the 1970s tools were built for. 6. Portable takeaway. Whenever a second-moment/correlation argument in analytic or additive number theory stalls because pairwise correlations depend on an intractably rich family of divisor/GCD configurations, look for a compression/shifting procedure (in the Erdős–Ko–Rado / Dyson lineage) that iteratively forces a *single* worst-case structure while tracking a carefully chosen non-monotone-looking hybrid potential (here, density$^{k}\times$size — not the "obvious" density-increment or size-increment alone). Once compressed to the single bad structure, older, narrower elementary estimates (here, the Erdős–Vaaler tail bound) can finish the job. This exact machine (the "GCD graph") has already been re-deployed verbatim on a structurally different Erdős problem — see Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity? / arXiv:2502.09539 — confirming it is a genuinely reusable unit, not a one-off trick.

Related

- Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity? — Erdős's integer dilation approximation problem; the still partially-open primitive-set/sparsity question whose $o(\log n)$ bound (Koukoulopoulos–Lamzouri–Lichtman, arXiv:2502.09539) was proved by reusing this page's GCD-graph machinery verbatim, transplanted from Diophantine approximation to a dilation-separation setting — the clearest existing example in this wiki of the technique being reused downstream. - GCD graphs (Koukoulopoulos–Maynard graph-theoretic sieve) — the graph-theoretic object (vertices = integers/denominators, edges = pairs with anomalously large $\gcd$ relative to size) introduced in this proof; the compression/"quality" iteration described above is this concept's founding worked example. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs / concept/borel-cantelli-lemma — the standard reduction (Gallagher's 0-1 law + Cauchy–Schwarz on a counting function) that every attack on this conjecture, solved or partial, shares; the *novelty* of Koukoulopoulos–Maynard lies entirely downstream of this step. - concept/compression-arguments — the Erdős–Ko–Rado shifting / Dyson transposition lineage that the bipartite iteration procedure is explicitly modeled on; a reusable pattern for "iteratively force worst-case structure while tracking a monovariant." - concept/khinchin-theorem — the 1924 predecessor result for *all* fractions (not just reduced) under a monotonicity hypothesis on $q\psi(q)$; Duffin–Schaeffer's 1941 conjecture is exactly the removal of that monotonicity hypothesis via the totient-weighted reduced-fraction reformulation. - concept/hausdorff-dimension-diophantine-approximation — Beresnevich–Velani's equivalence between the Duffin–Schaeffer conjecture and its Hausdorff-measure refinement, giving $\dim_H(A)=\min(s,1)$ as an immediate corollary of the theorem proved here.