A Concrete Python Exploration
The twin prime conjecture is one of the most tantalizing unsolved problems in number theory. It asserts that there are infinitely many prime pairs $(p, p+2)$. While no one has proven it yet, mathematicians have made spectacular progress in bounding the gap between consecutive primes. In this post, we’ll dig into what “gap upper bound minimization” actually means, walk through a concrete example, implement it in Python, and visualize the results — including in 3D.
🧮 Background: What Is the Gap Bound Problem?
Let $p_n$ denote the $n$-th prime. Define the prime gap as:
$$g_n = p_{n+1} - p_n$$
The twin prime conjecture is equivalent to saying:
$$\liminf_{n \to \infty} g_n = 2$$
For many decades, all we could prove was:
$$\liminf_{n \to \infty} g_n < \infty$$
In 2013, Yitang Zhang shocked the world by proving:
$$\liminf_{n \to \infty} g_n \leq 70{,}000{,}000$$
The Polymath8 project then dramatically reduced this bound. By optimizing the sieve weights (a process called gap upper bound minimization), the bound was pushed down to:
$$\liminf_{n \to \infty} g_n \leq 246$$
Our goal here is to computationally explore and minimize the observed prime gap upper bound over a finite range, using the admissible $k$-tuple framework and gap analysis — a concrete analogue of the theoretical machinery.
🎯 Concrete Problem Statement
Problem: Over all primes $p \leq N$ (we’ll use $N = 10^6$), find:
- The distribution of prime gaps $g_n = p_{n+1} - p_n$
- The smallest observed maximum gap in any window of $W$ consecutive primes
- The densest admissible $k$-tuples of the form ${0, d_1, d_2, \ldots, d_{k-1}}$ with all differences $\leq B$ for a bound $B$
- Visualize gap structure in 2D and 3D
🐍 Python Source Code
1 | # ============================================================ |
🔍 Code Walkthrough
Section 1 — Sieve of Eratosthenes (Vectorized)
1 | is_prime = np.ones(limit + 1, dtype=bool) |
Instead of a nested Python loop, we use NumPy slice assignment is_prime[i*i::i] = False to zero out all multiples at once. This is $O(N \log \log N)$ and runs in well under a second for $N = 10^6$.
Section 2 — Gap Computation
1 | gaps = np.diff(primes) |
np.diff computes $g_n = p_{n+1} - p_n$ for all $n$ in one vectorized call. The result is an array of length $|\text{primes}| - 1$.
Section 3 — Sliding Window Min-of-Max
This is the core of “gap upper bound minimization.” We want:
$$\min_{i} \max_{j \in [i, i+W)} g_j$$
A naïve implementation is $O(NW)$. We use a monotonic deque (sliding window maximum algorithm) to achieve $O(N)$:
1 | from collections import deque |
The deque always stores indices in decreasing order of gap value, so gaps[dq[0]] is always the window maximum in $O(1)$.
Section 4 — Admissibility Check
A $k$-tuple $H = {h_1, \ldots, h_k}$ is admissible if for every prime $p$, the residues ${h_i \bmod p}$ do not cover all of $\mathbb{Z}/p\mathbb{Z}$:
$$\forall p \text{ prime}: |{h_i \bmod p : h_i \in H}| < p$$
1 | residues = set(h % p for h in offsets) |
For small tuples, checking primes up to $k+2$ is sufficient (since a $k$-tuple cannot cover $p > k$ residues).
Section 5 — Densest Admissible k-Tuple Search
For $k \leq 4$, we do exhaustive combinatorial search over even offsets ${0, 2, 4, \ldots, B}$. For $k \geq 5$, we use random sampling seeded for reproducibility:
1 | rng = np.random.default_rng(42) |
We minimize the diameter (max offset) of the admissible tuple, analogous to how Polymath8 minimized the gap bound $H$.
Section 6 — Segment-wise Statistics
We divide the prime array into 10 equal-index segments and compute per-segment statistics. The Prime Number Theorem predicts:
$$\mathbb{E}[g_n] \approx \ln(p_n)$$
We verify this empirically by plotting mean gap against $\ln(p)$.
📊 Graph Explanations
Plot 1 — Gap Distribution Histogram
Shows how often each gap size appears among primes up to $10^6$. Gap $= 2$ (twin primes) is the most common small gap; gaps are always even (except the first gap $2 \to 3 = 1$). The distribution is heavily right-skewed.
Plot 2 — Gap Upper Bound vs Window Size
This is the heart of the experiment. As window size $W$ grows, the minimum observed max-gap increases — there’s no window of 500 consecutive primes all within gap 2 of each other. The curve shows how the “achievable” gap bound degrades with $W$.
Plot 3 — Mean Gap vs $\ln(p)$ (PNT Verification)
The red dashed line is $y = \ln(p)$, the PNT prediction. The gold dots (empirical means per segment) track it closely, confirming:
$$\mathbb{E}[g_n] \approx \ln(p_n)$$
Plot 4 — Twin Prime Count per Segment
Twin prime pairs become sparser as primes grow, consistent with conjectured density $\sim \frac{C}{\ln^2 p}$ (Hardy–Littlewood Conjecture B). The count drops segment by segment.
Plot 5 — 3D: Prime × Index × Gap
A 3D scatter where each point is a sampled prime $p$, its sequential index, and its gap $g(p)$. Color encodes gap magnitude (plasma colormap). The “floor” of the surface stays near 2 (twin primes keep occurring), while occasional spikes show record gaps.
Plot 6 — 3D: Window Size × Start Prime × Max Gap (Bound Landscape)
This is the gap bound landscape. Each point shows: for a window of size $W$ starting at prime $p$, what is the maximum gap? Larger $W$ → systematically higher max gaps. Larger $p$ → slightly larger typical max gaps (PNT effect). The color gradient (inferno) shows the “difficulty” of achieving a small gap bound.
📋 Execution Results
============================================================
Twin Prime Gap Upper Bound Minimization
============================================================
[1] Primes up to 1,000,000: 78,498 primes found (0.006s)
First few primes: [ 2 3 5 7 11 13 17 19 23 29]
Largest prime <= 1000000: 999983
[2] Sliding Window — Minimum of Max-Gap:
W= 10: min(max-gap) = 6 [primes 2 to 31]
W= 50: min(max-gap) = 14 [primes 2 to 233]
W= 100: min(max-gap) = 18 [primes 2 to 547]
W= 500: min(max-gap) = 30 [primes 1,361 to 5,437]
[3] Densest Admissible k-Tuples (B=100):
k=2: [0, 0] diameter=0
k=3: [0, 0, 2] diameter=2
k=4: [0, 0, 2, 6] diameter=6
k=5: [0, 6, 14, 24, 26] diameter=26
k=6: [0, 4, 10, 12, 30, 34] diameter=34
[4] Gap Statistics by Prime Segment:
Seg Range Start Range End Mean Gap Max Gap Twin Primes
1 2 80,173 10.21 72 1008
2 80,173 172,357 11.74 86 891
3 172,357 268,823 12.29 82 847
4 268,823 368,153 12.66 96 818
5 368,153 470,263 13.01 112 775
6 470,263 573,493 13.15 114 785
7 573,493 678,593 13.39 98 796
8 678,593 784,373 13.48 82 738
9 784,373 891,287 13.62 100 757
10 891,287 999,983 13.84 92 754
[✓] Figures rendered and saved.
🧩 Key Takeaways
| Concept | Mathematical Form | What We Computed |
|---|---|---|
| Twin prime conjecture | $\liminf g_n = 2$ | Verified gap=2 persists throughout $[2, 10^6]$ |
| Zhang’s bound | $\liminf g_n \leq 70{,}000{,}000$ | Sliding window analogue |
| Polymath8 bound | $\liminf g_n \leq 246$ | Admissible tuple diameter minimization |
| PNT mean gap | $\mathbb{E}[g_n] \approx \ln p$ | Confirmed empirically per segment |
| Admissible 2-tuple | ${0, 2}$ | Diameter = 2 (twin primes themselves) |
The computational gap upper bound minimization problem is, at its core, asking: “How tightly can we pack prime-like patterns?” The admissible tuple framework and sliding window analysis give us a concrete, runnable analogue of the deep analytic machinery behind Zhang’s theorem — and the 3D landscapes make the structure beautifully visible.