🔢 mathematics

On the problem of large gcd for disjoint residue classes

This paper establishes a lower bound on the maximum greatest common divisor of moduli for $k$ pairwise disjoint residue classes by employing a combination of graph coloring, structural lemmas, sieve theory, Möbius inversion, and the discrete Fourier transform.

Original authors: Jan Fornal, Yu-Chen Sun

Published 2026-07-28

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Jan Fornal, Yu-Chen Sun

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery about how numbers hide from each other. In the world of mathematics, specifically a branch called number theory, numbers often wear "masks" called residue classes. Think of a residue class as a specific seat at a round table where everyone has a number, but they only sit down if their number leaves the same "leftover" when divided by a specific size, called a modulus. For example, the "3 o'clock" seat at a table of 12 might be for everyone whose number is 3, 15, 27, and so on.

Now, imagine you have a group of these seats, but with a very strict rule: no two seats can ever overlap. If one seat is for numbers that are 1 more than a multiple of 5, and another is for numbers that are 2 more than a multiple of 7, they might accidentally share a number (like 22). If they do, they aren't "disjoint." The mathematicians in this story are asking a tricky question: If you force a bunch of these seats to be completely separate so they never share a single number, how much do the sizes of their tables (the moduli) have to have in common? Specifically, they want to know the size of the biggest "shared factor" (the Greatest Common Divisor, or GCD) between any two of these table sizes. It's like asking: if you have a bunch of puzzle pieces that refuse to fit together, how similar must their shapes be? This matters because understanding these hidden connections helps mathematicians solve bigger puzzles about how numbers are distributed, which is crucial for everything from cryptography to understanding the rhythm of prime numbers.

The Great GCD Mystery: When Numbers Refuse to Mix

In this paper, Jan Fornal and Yu-Chen Sun tackle a puzzle that has been nagging at mathematicians for a while. They are looking at a collection of $k$ different "residue classes" (our special seats) that are all pairwise disjoint, meaning no two of them share a single number. The big question is: If you have $k$ of these non-overlapping seats, how large must the shared factor (the GCD) be between the sizes of at least two of the tables?

For a long time, a mathematician named Sun made a bold guess (a conjecture). He thought that if you have $k$ disjoint seats, the biggest shared factor between any two table sizes must be at least $k$ . It's a neat, clean idea: if you have 100 seats that don't overlap, two of the tables must share a factor of at least 100. Sun proved this for small numbers of seats (up to 20), and others proved it for specific types of groups, but the general case for any number $k$ remained a mystery.

Fornal and Sun didn't prove Sun's exact guess of $k$ , but they came incredibly close. They proved that the largest shared factor is roughly $k$ divided by a very tiny, shrinking fraction. In their own words, they showed that the maximum GCD is at least:
$\exp\left( -(2 + o(1)) \sqrt{\frac{\log k}{\log \log k}} \right)$
Don't let the scary math symbols scare you. In plain English, this means the answer is $k$ to the power of something very close to 1. It's almost $k$ , just slightly smaller. So, while they didn't confirm the exact number $k$ , they confirmed that the shared factor grows almost as fast as the number of seats you have. This is a massive step forward, proving that Sun's intuition was essentially correct, just needing a tiny bit of wiggle room.

How They Solved It: The Colored Graph Game

To crack this code, the authors turned the problem into a game of connecting dots, or what mathematicians call a "graph." Imagine each of your $k$ disjoint seats is a dot (a vertex) on a piece of paper. Now, draw a line (an edge) between every pair of dots. But here's the twist: color each line based on the GCD of the two table sizes it connects. If two tables are both multiples of 6, the line between them is colored "6."

The authors realized that if you have too many dots (seats) and the lines (GCDs) are too small, the graph would have to look a certain way that simply isn't possible for disjoint seats. They used a clever trick called a "sieve" to group the table sizes into categories, kind of like sorting a deck of cards by suit and rank, but based on their prime factors.

Then, they introduced a "weight" system. Some dots are more important than others. They assigned weights to the dots based on how many groups they belonged to. The key insight came from a structural lemma (a fancy rule about the graph's shape). They found that if you have a dot connected to many other dots by lines of a "weird" color (a GCD that isn't the simple GCD of the two table sizes), that dot must either be in a tiny "exceptional" group, or it must have a very tiny weight.

By balancing these weights and using a tool called the "discrete Fourier transform" (which is like a way of listening to the hidden rhythms in the numbers), they were able to show that the total weight of the graph forces the GCDs to be large. If the GCDs were small, the math would break down, leading to a contradiction.

The Verdict

The paper proves that for any family of $k$ pairwise disjoint residue classes, the maximum GCD between any two moduli is at least:
$k^{1 - o(1)}$
This means that as $k$ gets huge, the shared factor gets closer and closer to $k$ itself.

They also applied this result to a related problem about "extremal families" of disjoint arithmetic progressions (sequences of numbers with a constant gap). They showed that in the largest possible families of these sequences, there must be two numbers that share a massive common factor, specifically around $x L(x)^{-1+o(1)}$ , where $L(x)$ is a specific function involving logarithms.

In short, Fornal and Sun didn't just guess; they built a rigorous mathematical bridge using graphs, sieves, and Fourier analysis to prove that disjoint numbers are forced to have a surprisingly strong connection. They didn't solve the problem perfectly (the exact $k$ is still a conjecture), but they proved that the connection is almost as strong as the conjecture predicted, closing the gap significantly.

Technical Summary: On the Problem of Large GCD for Disjoint Residue Classes

Problem Statement
The paper addresses a fundamental question regarding the arithmetic structure of pairwise disjoint residue classes. Let $a_1 \pmod{m_1}, \dots, a_k \pmod{m_k}$ be a family of $k$ pairwise disjoint residue classes. A necessary condition for disjointness is that for any distinct $i, j$ , $\gcd(m_i, m_j) > 1$ . The central problem is to determine how large the maximum greatest common divisor (GCD) among the moduli must be as a function of $k$ .

This problem relates to a conjecture by Sun, which posits that for any such family, $\max_{i<j} \gcd(m_i, m_j) \ge k$ . While this bound is best possible (as demonstrated by the $k$ distinct residue classes modulo $k$ ), it remains unproven for general $k$ . Previous results established the conjecture for small $k$ (e.g., $k \le 20$ by O'Bryant, $k=3,4$ for the group-theoretic version by Zhu) and specific cases.

Methodology
The authors employ a synthesis of combinatorial graph theory, sieve methods, and harmonic analysis to derive a lower bound for the maximum GCD. The core of the approach involves the following steps:

Colored Graph Construction: The residue classes are treated as vertices of a complete graph. The edge between two vertices is colored by the GCD of their corresponding moduli.
Weighted Partitioning: The authors introduce a partition of the integers $[d]$ (where $d = \max \gcd(m_i, m_j)$ ) into sets $K_n$ . Vertices are assigned weights based on their membership in these sets such that the total weight of each vertex is 1. This allows for a "double counting" argument where the sum of weights equals the number of classes $k$ .
Sieve-Theoretic Partition: A key technical component is the partition of the range $[d]$ into a small number of sets $C_i$ (Proposition 2.1). This partition is constructed using a multiscale decomposition of prime factors (separating very small primes and grouping primes into short intervals). This ensures that within each set $C_i$ , the divisor-sum parameter $T_i$ (related to the sum of GCDs of pairs in the set) is uniformly bounded.
Structural Lemma (Lemma 4.1): A dichotomy is established for edges between sets $K_m$ and $K_n$ where the edge color (GCD) differs from $\gcd(m, n)$ . The lemma states that either one endpoint belongs to a small "exceptional" set (size bounded by the number of prime factors), or the weight of a fixed endpoint is inversely proportional to the number of such incident edges. This controls the contribution of "non-standard" edges.
Fourier and Möbius Analysis: To derive a lower bound for the weighted GCD sum, the authors utilize Möbius inversion and the discrete Fourier transform. Specifically, Lemma 5.1 establishes the non-negativity of a specific quadratic form involving divisor sums and Fourier coefficients. This yields a quadratic lower bound ( $k_i^2$ ) for the contribution of each partition set.
Upper Bound via Disjointness: The upper bound is derived by exploiting the pairwise disjointness of the residue classes. Terms where the edge color equals $\gcd(m, n)$ correspond to the Chinese Remainder Theorem compatibility condition, which would imply intersection; thus, these terms are eliminated. The remaining terms are controlled using the structural lemma and the sieve partition.

Key Results
The main theorem establishes the following asymptotic lower bound for the maximum GCD:

$\max_{1 \le i < j \le k} \gcd(m_i, m_j) \gg_k \exp\left( -(2 + o(1)) \sqrt{\frac{\log k}{\log \log k}} \right)$

This implies that the maximum GCD is at least $k^{1-o(1)}$ , thereby proving Sun's conjecture up to a sub-polynomial factor $k^{o(1)}$ .

Additionally, the paper derives a corollary regarding the problem of distinct moduli bounded by $x$ . Combining their result with recent work on the maximum size $f(x)$ of a family of disjoint arithmetic progressions with moduli in $[1, x]$ (specifically $f(x) = x L(x)^{-1+o(1)}$ where $L(x) = \exp(\sqrt{\log x \log \log x})$ ), the authors show that any extremal family must contain two moduli sharing a common multiplicative core of size $x L(x)^{-1+o(1)}$ with comparatively small coprime tails.

Significance and Claims
The paper claims to provide the first general lower bound for the maximum GCD in a family of pairwise disjoint residue classes that depends on $k$ and approaches the conjectured linear bound. The authors note that their result bridges the gap between the known trivial lower bound ( $>1$ ) and Sun's conjectured bound ( $\ge k$ ).

The significance lies in the novel combination of techniques:

The use of a colored graph to visualize and analyze the GCD structure of moduli.
The application of a sieve-theoretic partition to control divisor sums in a way that minimizes the number of classes while maintaining uniformity.
The integration of Fourier orthogonality to convert the disjointness condition into a quantitative lower bound on GCD sums.

The authors do not claim to have resolved Sun's conjecture completely but assert that their estimate is the strongest known general result, reducing the problem to a factor of $k^{o(1)}$ . The work also connects the problem of disjoint residue classes to the broader context of GCD sums and the Duffin–Schaeffer conjecture, highlighting the utility of GCD graphs in number theory.

The Great GCD Mystery: When Numbers Refuse to Mix

How They Solved It: The Colored Graph Game

The Verdict

Technical Summary: On the Problem of Large GCD for Disjoint Residue Classes

More like this