🔢 mathematics

Explicit bounds for the graphicality of the prime gap sequence

This paper establishes the first explicit unconditional thresholds, specifically $n \geq \exp\exp(30.32)$ and $n \geq \exp\exp(34.33)$ , guaranteeing that the sequence of the first $n$ prime gaps is graphic and that its realizations satisfy DPG-graphic properties, respectively, by employing refined graphic criteria and explicit estimates derived from zero-free regions and zero-density estimates of the Riemann zeta function.

Original authors: Keshav Aggarwal, Robin Frot, Haozhe Gou, Hui Wang

Published 2026-08-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Keshav Aggarwal, Robin Frot, Haozhe Gou, Hui Wang

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

The Great Prime Puzzle

Imagine the number line as a long, endless highway. Scattered along this road are special rest stops called "prime numbers." These are numbers that can only be divided by themselves and one, like 2, 3, 5, or 7. If you drive from one prime stop to the next, the distance you travel is called a "prime gap." Sometimes the stops are right next to each other (like 2 and 3, a gap of 1), and sometimes they are miles apart.

For a long time, mathematicians have been fascinated by the pattern of these gaps. But recently, a group of researchers asked a weird, sideways question: Can we turn these gaps into a map? Specifically, if you take the first n gaps between prime numbers, can you arrange them as the "degrees" (the number of connections) of a network of dots and lines? In math-speak, this is asking if the sequence is "graphic." It's like asking if you have a specific set of instructions for how many hands each person at a party should shake, and whether it's actually possible to arrange the party so everyone shakes exactly that many hands without anyone getting confused or shaking the same hand twice.

Why does this matter? It sounds like a party game, but it connects two huge worlds of math: the chaotic, unpredictable nature of prime numbers and the rigid, logical rules of graph theory. If we can prove these gaps always form a valid network, it tells us something deep about how primes are distributed. It's like discovering that the seemingly random footsteps of a dancer actually follow a hidden, perfect choreography.

The Paper's Big Discovery

In this paper, Keshav Aggarwal, Robin Frot, Haozhe Gou, and Hui Wang act as the ultimate referees for this mathematical party game. They tackle a question that had been floating in the air for a while: Exactly how big does the party need to be before we can guarantee that the prime gap sequence forms a valid network?

Previous work by Erdős and others had shown that for very large numbers, the answer is "yes," and that it's true for every number if a famous, unproven guess called the Riemann Hypothesis is true. But the authors of this paper wanted to be more precise. They didn't just want to say "it works for big numbers"; they wanted to find the exact starting line. They wanted to say, "If you have at least this many primes, the network is guaranteed to work, no matter what."

The team successfully established the first explicit, unconditional threshold. They proved that for any number of primes $n$ greater than or equal to $\exp(\exp(30.32))$ , the sequence of the first $n$ prime gaps is definitely "graphic." To put that massive number in perspective, it is an astronomically large value, far beyond the number of atoms in the universe, but the key is that it is a specific, calculable number. Before this, we didn't have a concrete "stop here" sign; now we do.

But they didn't stop there. They also looked at a more complex version of the game called the "DPG-process." Imagine building a network one person at a time. You start with a small group, and every time you add a new person, you have to connect them to the existing group without changing how many hands the original people were already shaking. This is much harder than just checking if the final group works. The authors proved that for $n \ge \exp(\exp(34.33))$ , not only is the network valid, but you can also build it step-by-step using this specific "add-a-person" method without ever getting stuck.

How They Solved It

To find these exact numbers, the authors had to be incredibly precise with their tools. They used a refined version of a classic rule called the Erdős–Gallai criterion, which acts like a checklist to see if a party plan is possible. Instead of checking every single possibility, they found a smarter way to check only the critical moments where the plan might fail.

Then, they had to deal with the messy reality of prime numbers. Primes are tricky; they don't follow a simple rhythm. To predict how big the gaps could get, the authors had to dive deep into the "Riemann zeta function," a complex mathematical object that holds the secrets of prime distribution. They used the best-known "zero-free regions" (areas where the function doesn't have any zeros) and "zero-density estimates" (counting how many zeros are in a certain area) to create tight bounds on how large the gaps could possibly be.

By combining these sharp graph theory rules with these tight number theory estimates, they were able to calculate the exact point where the math guarantees the network works. They didn't just guess; they proved it. They showed that once you pass the threshold of $\exp(\exp(30.32))$ , the chaotic dance of prime gaps suddenly snaps into a perfect, solvable puzzle. And for the step-by-step construction, the threshold is $\exp(\exp(34.33))$ .

The Bottom Line

This paper doesn't just say "it probably works." It provides a hard, mathematical guarantee. It tells us that while the prime gaps might look random and wild, if you wait long enough—specifically, until you reach the unimaginably large number of $\exp(\exp(30.32))$ —they will always form a valid, connected network. It's a victory for precision, turning a vague "it works for big numbers" into a concrete "it works starting right here." The authors have drawn the line in the sand, proving that beyond that line, the universe of prime gaps is orderly enough to be mapped, one connection at a time.

Technical Summary: Explicit Bounds for the Graphicality of the Prime Gap Sequence

Problem Statement
The paper addresses the combinatorial properties of the sequence of prime gaps. Let $p_n$ denote the $n$ -th prime number (with $p_0=1$ ). The sequence of the first $n$ prime gaps is defined as $PD_n = (p_\ell - p_{\ell-1})_{\ell=1}^n$ . The central question is whether this sequence is graphic, meaning there exists a simple undirected graph with $n$ vertices whose degrees correspond exactly to the elements of $PD_n$ .

This inquiry is motivated by two conjectures proposed by Toroczkai (2016):

Existence Conjecture: For every $n \ge 2$ , a prime gap graph exists.
Structural Conjecture: Every prime gap graph on $n$ vertices contains $(p_{n+1} - p_n)/2$ independent edges.

While Erdős et al. [9] previously proved these conjectures hold for sufficiently large $n$ unconditionally, and for all $n$ assuming the Riemann Hypothesis (RH), their results were non-explicit. This paper aims to establish the first explicit unconditional threshold $n_0$ such that for all $n \ge n_0$ , the sequence $PD_n$ is graphic. Furthermore, it seeks to make the structural property (DPG-graphicity) explicit.

Methodology
The authors build upon the framework established by Erdős et al. [9], which combines tools from analytic number theory (to analyze prime gaps) and matching theory (to establish graph realizability). The proof strategy involves two primary refinements to achieve explicit bounds:

Refined Graphicality Criterion: Instead of verifying the Erdős–Gallai criterion for all $k \in \{1, \dots, n-1\}$ , the authors utilize a sharper criterion (Theorem 2.7, based on Zverovich and Zverovich [22] and Tripathi and Vijay [19]). This reduces the verification to specific values of $k$ where the degree sequence jumps, significantly simplifying the analysis for large $n$ .
Explicit Estimates for Prime Gaps: The core analytical work involves deriving explicit bounds for the first moment of large prime gaps. This relies on:
- Explicit Zero-Free Regions: Utilizing the best known explicit zero-free region for the Riemann zeta function $\zeta(s)$ , specifically the result by Yang [21] which improves the constant $c_0$ in the zero-free region $\beta \le 1 - c_0 (\log t)^{-2/3} (\log \log t)^{-1/3}$ to $c_0 = 1/51.34$ .
- Explicit Zero-Density Estimates: Employing explicit bounds for $N(\sigma, T)$ , the number of non-trivial zeros in the critical strip, derived from Kadiri, Lumley, and Ng [14].
- Explicit Chebyshev Function: Deriving an explicit formula for $\psi(x)$ with precise error terms (Lemma 2.5), which is used to bound the sum of large prime gaps.

The authors define the Degree-Preserving Network Growth (DPG) process, an algorithm that extends a graph $G_n$ to $G_{n+1}$ by inserting a new vertex and connecting it to endpoints of a matching of size $(p_{n+1}-p_n)/2$ . The existence of such a matching in any realization of $PD_n$ is the condition for the sequence to be DPG-graphic.

Key Contributions and Results
The paper provides the first explicit unconditional lower bounds for the graphicality of the prime gap sequence.

Theorem 1.3 (Existence): The authors establish that for all $n \ge \exp(\exp(30.32))$ , the sequence $PD_n$ is graphic. This confirms the Existence Conjecture for all $n$ beyond this explicit threshold without assuming the Riemann Hypothesis.
Theorem 1.4 (Structural/DPG-Graphicity): The authors prove that for all $n \ge \exp(\exp(34.33))$ , every realization $G_n$ of the prime gap sequence $PD_n$ satisfies the condition that the pair $(G_n, p_{n+1}-p_n)$ is DPG-graphic. This implies that the sequence of prime gap graphs constitutes a non-trivial, naturally arising infinite structure that can be iteratively extended via the DPG process.

Significance
The paper claims significance primarily in the transition from asymptotic existence to explicit, unconditional verification.

Explicitness: Unlike previous works that relied on the existence of "sufficiently large" $n$ or the assumption of RH, this work provides concrete numerical thresholds ( $n_0 \approx \exp(\exp(30.32))$ ).
Methodological Refinement: The work demonstrates how combining refined graph-theoretic criteria (reducing the number of Erdős–Gallai checks) with the most up-to-date explicit estimates in analytic number theory (specifically zero-density and zero-free regions) can yield concrete results in problems linking prime distribution and graph theory.
Unconditional Nature: The results hold unconditionally, relying only on the known properties of the Riemann zeta function up to the current state of the art (e.g., verified zeros up to $H_0 = 3 \times 10^{12}$ and explicit zero-free regions).

The authors note that the main bottleneck for improving these bounds is the known explicit zero-free region for the Riemann zeta function; any future improvements in this analytic number theory domain would directly translate to lower thresholds for $n_0$ . The paper does not propose new applications or experimental proposals but focuses strictly on establishing these rigorous mathematical bounds.

The Great Prime Puzzle

The Paper's Big Discovery

How They Solved It

The Bottom Line

More like this