GCD graphs (Koukoulopoulos–Maynard graph-theoretic sieve)

Statement

A (bipartite) GCD graph (Koukoulopoulos–Maynard, Definition 6.1 of arXiv:1907.04593) is a septuple $$ G=(\mu,\,V,\,W,\,E,\,P,\,f,\,g) $$ where:

- $\mu$ is a measure on $\mathbb N$ (extended to $\mathbb N^2$ by $\mu(N):=\sum_{(n_1,n_2)\in N}\mu(n_1)\mu(n_2)$) — in the Duffin–Schaeffer application, $\mu(n)=\phi(n)\psi(n)/n$; - $V,W$ are finite sets of positive integers (the two vertex classes); - $E\subseteq V\times W$ is the edge set, so $(V,W,E)$ is an ordinary bipartite graph; - $P$ is a set of "accounted-for" primes, and $f,g:P\to\mathbb Z_{\ge0}$ are exponent functions satisfying, for every $p\in P$: (i) $p^{f(p)}\mid v$ for all $v\in V$ and $p^{g(p)}\mid w$ for all $w\in W$; (ii) if $(v,w)\in E$ then $p^{\min\{f(p),g(p)\}}\Vert\gcd(v,w)$; (iii) if $f(p)\neq g(p)$, then $p^{f(p)}\Vert v$ for all $v\in V$ and $p^{g(p)}\Vert w$ for all $w\in W$.

So a GCD graph is an ordinary weighted bipartite graph on integer vertex sets, plus a *ledger* $(P,f,g)$ that records, prime by prime, exactly how much of $\gcd(v,w)$ for each edge is already "explained" by fixed divisibility of all of $V$ by $p^{f(p)}$ and all of $W$ by $p^{g(p)}$. $G$ is non-trivial if $\mu(E)>0$.

A GCD subgraph $G'\preceq G$ (Definition 6.4) shrinks $V,W,E$ and only ever *adds* primes to $P$ (never removes one), i.e. it is a restriction that knows *at least as much* about the divisor structure of its edges as $G$ did. The canonical way to build one (Definition 6.5) is to fix a new prime $p\notin P$ and a pair of valuations $(k,\ell)$, and pass to $$ G_{p^k,p^\ell} = \bigl(\mu,\ V_{p^k},\ W_{p^\ell},\ E\cap(V_{p^k}\times W_{p^\ell}),\ P\cup\{p\},\ f_{p^k},\ g_{p^\ell}\bigr), $$ where $V_{p^k}=\{v\in V: p^k\Vert v\}$ (or "coprime to $p$" if $k=0$) — i.e. slice both sides by exact $p$-adic valuation and keep only the corresponding edges.

Each GCD graph has an edge density $\delta(G):=\mu(E)/(\mu(V)\mu(W))$ and a quality $$ q(G) \;:=\; \delta^{10}\,\mu(V)\mu(W)\prod_{p\in P} \frac{p^{\,|f(p)-g(p)|}}{\bigl(1-\mathbb 1_{f(p)=g(p)\ge 1/p}\bigr)^{2}\,\bigl(1-p^{-31/30}\bigr)^{10}} $$ (Definition 6.6(d)) — a single scalar combining edge density, vertex mass, and the accumulated "spread" of the fixed valuations $f(p)-g(p)$ over the accounted primes $P$. $q(G)>0$ iff $G$ is non-trivial (Lemma 6.7(d)).

Master statement used to prove Duffin–Schaeffer (Proposition 7.1, "Existence of a good GCD subgraph"): given a non-trivial GCD graph $G=(\mu,V,W,E,\varnothing,f_\varnothing,g_\varnothing)$ with trivial prime set and edge density $\delta>0$, all of whose edges satisfy a fixed lower bound on a certain "large-common-prime-factor" statistic $L_t(v,w)\ge10$ for $t\ge10\delta^{-1/50}$, $t>10^{2000}$ — there exists a GCD subgraph $G'\preceq G$ such that (a) $R(G')=\varnothing$ (every prime dividing some edge's gcd is now accounted for in $P'$); (b),(c) $G'$ is *regular*: every vertex's neighbourhood has density $\ge(9\delta'/10)$ of the opposite side; and (d) either the quality has grown by a factor $\gtrsim\delta t^{50}$, or the quality is at least preserved ($q(G')\gg q(G)$) and the "stripped" vertices (with the $P'$-part of their factorization removed) satisfy a strictly stronger large-common-factor bound $L_t(v',w')\ge4$.

Facts

- Origin. Introduced by Dimitris Koukoulopoulos and James Maynard in "On the Duffin–Schaeffer conjecture," arXiv:1907.04593 (May 2019 / published Annals of Math. 192 (2020), 251–307) to prove: for $\psi:\mathbb N\to\mathbb R_{\ge0}$ with $\sum_q\psi(q)\phi(q)/q=\infty$, almost every real $\alpha$ has infinitely many coprime solutions $a/q$ to $|\alpha-a/q|\le\psi(q)/q$ — settling the 1941 Duffin–Schaeffer conjecture (Erdős's Problem 46 in Montgomery's list) and, as a corollary, Catlin's conjecture on non-reduced solutions (a refinement of Khinchin's 1924 theorem). - The problem it solves in the proof. A second-moment/Cauchy–Schwarz argument (Section 5) reduces Duffin–Schaeffer to bounding $\sum_{q,r}\lambda(A_q\cap A_r)\ll1$, and a sieve bound (Lemma 5.3) shows the "excess overlap" of $A_q,A_r$ is controlled by $\prod_{p\mid qr/\gcd(q,r)^2,\ p>M(q,r)/\gcd(q,r)}(1+1/p)$. The whole difficulty is bounding, on average, how often *many small primes divide exactly one of $q,r$* — i.e. understanding sets $S$ of integers where many pairs have an unexpectedly large $\gcd$. This is exactly the "Model Problem" that GCD graphs are built to attack (p.7 of the paper): if a positive fraction of pairs in $S\times S$ have $\gcd(a_1,a_2)>x^{1-c}$, is that forced by a single fixed common divisor $d$ shared by many elements? - Why plain "density increment" (à la Roth's theorem) fails here: iteratively maximizing the density $\delta_j=\#\{(v,w): \gcd(v,w)>x^{1-c}/t\}/(\#V_j\#W_j)$ loses control of the *sizes* $\#V_j,\#W_j$, which are exactly what's needed to bound the original sum. - Why plain "size" ($\#V_j\cdot\#W_j\cdot a_jb_j/\gcd(a_j,b_j)^2$, tracking the fixed common divisors $a_j,b_j$) also fails: this quantity is not guaranteed to increase at every step of the iteration. - The fix: quality $\delta^{10}\cdot\#V\cdot\#W\cdot ab/\gcd(a,b)^2$ (the prototype of Definition 6.6(d)'s formula, before the technical $\phi(q)/q$-related correction factors are added) is a *hybrid* of the density and the size statistics that the authors show can be forced to increase (or preserved alongside stronger regularity) at every step of the compression — "roughly inspired by" the compression/shifting arguments of Erdős–Ko–Rado and Dyson (paper's own words, Section 3, p.8), and structurally analogous to a density-increment argument but tracking a different invariant so that vertex-set size is never lost. - Superseded/simplified since. Hauke, Vázquez Saez & Walker, "Proving the Duffin–Schaeffer conjecture without GCD graphs" (arXiv:2404.15123, Compositio Math.), give a re-proof of the same theorem that avoids GCD graphs and the "quality" invariant entirely, replacing the iterative quality-tracking with two direct propositions about bounded prime-valuation structure — explicitly motivated by, and simplifying, the original GCD-graph argument. A quantitative/"almost-sharp" strengthening of Duffin–Schaeffer was proved first *with* GCD graphs (Koukoulopoulos–Maynard–Yang) and later *without* them (arXiv:2409.10386, "Almost-Sharp Quantitative Duffin-Schaeffer without GCD Graphs"). GCD graphs remain the historically foundational and still-citable version of the technique even where later work bypasses the explicit graph machinery. - Reused on a second, structurally different problem. Koukoulopoulos, Lamzouri & Lichtman, "Erdős's integer dilation approximation problem and GCD graphs," arXiv:2502.09539 (Feb 2025), transplant the GCD-graph machinery (unmodified in spirit, adapted from integer denominators $q$ to a general real-valued index set $A$) to prove, unconditionally, one of the two sub-questions of **Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity?** (Erdős's $500 integer-dilation problem): if $A\subset\mathbb R_{\ge1}$ has positive logarithmic density then infinitely many pairs $\alpha\ne\beta\in A$ satisfy $|n\alpha-\beta|<\varepsilon$ for some positive integer $n$ and every $\varepsilon>0$. This is direct evidence the technique is genuinely reusable, not a one-off trick tied to Diophantine approximation of rationals specifically.

Technique

WHY it works (the mechanism). The core number-theoretic obstruction in problems of this shape is: *"a set of integers (or reals) $S$ has an anomalously large number of pairs with large $\gcd$ — is this always explained by a single shared divisor?"* This is not simply an averaging/sieve question because a large $\gcd$ between $v$ and $w$ could in principle be caused by many *different* primes on different pairs, with no global structure. GCD graphs solve this via a compression (iterative subgraph) argument: repeatedly pass from $(V_j,W_j)$ to a sub-pair $(V_{j+1},W_{j+1})$ that is *homogeneous* in the valuation of one new prime $p_{j+1}$ (either "all divisible by $p_{j+1}$" or "all coprime to $p_{j+1}$" on each side), while tracking a carefully engineered scalar invariant — the quality — that is provably non-decreasing (up to controlled loss) at every step. Because quality bundles together edge density, vertex mass, *and* the accumulated fixed-divisor structure with the correct weight (the $\phi(p)/p$-shaped correction factors in Definition 6.6(d) are essential — see the paper's own remark after the definition), the process cannot "cheat" by improving one statistic while destroying another. The iteration terminates (finitely many primes can matter, controlled via anatomy-of-integers bounds — Lemma 7.3, on how few integers have many small prime factors) at a GCD subgraph where the divisor structure is *completely explained* by two fixed integers $a\mid V, b\mid W$ with $\gcd(v,w)=\gcd(a,b)$ for every remaining edge — at which point the original sum is bounded by an elementary divisor-counting estimate ($\#V\cdot\#W\cdot ab/\gcd(a,b)^2$, now controllable because $q(G)$ never decreased net).

HOW it is used to prove things (recombination steps)

1. Reduce an analytic/measure-theoretic sum to a bipartite-graph edge-density bound. Whenever a proof needs $\sum_{q,r\in S}(\text{weight})\cdot\mathbb 1[\text{some gcd-type condition on }q,r]\ll(\text{target})$, recast $S$ (or $S\times S$) as a bipartite graph $G=(V,W,E)$ with $V=W=S$, edge weight $\mu$ from the analytic weight, and $E$ = the pairs satisfying the gcd condition. This is exactly Duffin–Schaeffer's Proposition 6.3 step. 2. Define quality as $\delta^{10}\mu(V)\mu(W)\prod_p(\cdots)$ — a hybrid of edge density and vertex mass with correction factors tuned to the specific weight function $\mu$ in play (here $\mu(n)=\phi(n)\psi(n)/n$, and the $\phi/q$-shape is load-bearing). Reusing this technique on a new problem requires re-deriving the right correction factors for *that* problem's weight — this is the main non-mechanical step in a transplant (see arXiv:2502.09539 for a worked second instance). 3. Iterate: for each new "unaccounted" prime $p\in R(G)$ dividing some edge's $\gcd$, pass to the homogeneous subgraph $G_{p^k,p^\ell}$ that either increases quality substantially, or preserves it while strictly improving the regularity of the remaining edges (e.g. tightening a "large common factor" statistic $L_t$). This uses anatomy-of-integers input (few integers have unusually many small prime factors — Lemma 7.3, in the spirit of Erdős's and Vaaler's original partial results on Duffin–Schaeffer) to bound how many iterations/how much prime-mass can be problematic. 4. Terminate at a fully-explained ("good") subgraph where $R(G')=\varnothing$ and the divisor structure of every remaining edge is pinned to two fixed integers — then read off the bound via a trivial divisor-counting estimate, using that quality is now controllably large or the vertex sets are controllably not-too-shrunk. 5. Unwind the reduction chain back through the second-moment/Borel–Cantelli argument to the original measure-theoretic statement.

WHEN it applies. Look for: (i) a target estimate of the shape "a weighted double sum over pairs $(q,r)$ from an index set, restricted to pairs with an anomalously large $\gcd$ (or gcd-type quantity), is small on average"; (ii) the weight function has enough multiplicative structure (in Duffin–Schaeffer, $\phi(q)/q$) that the quality's correction factors can be engineered to be well-behaved; (iii) the index set can plausibly decompose, after finitely many prime-valuation splits, into a regime where all large gcds are explained by a bounded amount of shared structure — i.e. an "anatomy of integers" input bounding rare/pathological prime-factorization behavior is available or provable. This is a fairly specific but recurring signature in metric Diophantine approximation, primitive-set/dilation problems (erdos/143), and — per the authors' remark in Section 3 — potentially other combinatorial-number-theory settings with a compression/shifting flavor (Erdős–Ko–Rado, Dyson-style arguments are the stated inspiration). It is *not* needed (and the newer 2024 papers show it can be entirely bypassed) whenever a more direct structural lemma about bounded prime-valuations can be extracted without paying for the general iterative bookkeeping — a useful sanity check before importing the full GCD-graph machinery onto a new problem is to check whether Hauke–Vázquez Saez–Walker's leaner two-proposition approach (arXiv:2404.15123) already suffices.

Related

- Erdős #143 — integer dilations $|kx-y|\\geq1$ force sparsity? — Erdős's $500 integer-dilation approximation problem; the GCD-graph machinery is reused essentially verbatim by Koukoulopoulos–Lamzouri–Lichtman (arXiv:2502.09539) to prove one of its two sub-questions unconditionally, the clearest evidence this is genuinely reusable derivation fuel and not a one-off Duffin–Schaeffer trick. - Sieve theory: Eratosthenes–Legendre, Brun, Selberg, Turán, and the large sieve — GCD graphs are described by the authors themselves as arising from "a refined overlap estimate from sieve theory" (Lemma 5.3's bound on $\lambda(A_q\cap A_r)$); the graph-theoretic compression argument is the extra ingredient sieve theory alone did not supply. - Von Mangoldt-weighted Markov chains for primitive-set (Erdős) sums — a structurally different (Markov-chain, not compression-graph) technique used on the closely related primitive-set family (erdos/1196, erdos/1217, erdos/164) in the same "sum over a set of integers/reals with a multiplicative constraint" problem area; worth comparing as an alternative recombination target when GCD graphs don't directly fit. - The alteration (deletion) method — probabilistic existence proofs that build an almost-good random structure, then delete its blemishes; canonical instance: Erdős's 1959 high-girth/high-chromatic-number graphs and covering/compression-style arguments in this wiki (e.g. Covering systems of congruences's "distortion method") — GCD graphs' iterative subgraph-passing is in the same family of *staged-revelation / iterative-structure-extraction* proof techniques, distinguished by tracking a purpose-built scalar invariant (quality) rather than density alone. - Duffin–Schaeffer conjecture / Theorem 1 of arXiv:1907.04593 (no dedicated concept/duffin-schaeffer-conjecture page yet in this wiki as of 2026-07-02) — the originating theorem; GCD graphs are the graph-theoretic core of its proof (Sections 6-14 of the paper).