Zaremba’s Conjecture (A=5): Proof Framework

Statement

Zaremba’s Conjecture (1972). For every integer $d \geq 1$, there exists $a$ with $\gcd(a,d) = 1$ such that $a/d = [0; a_1, \ldots, a_k]$ has all $a_i \leq 5$.

Status

• Certified computation: $R(d) \geq 1$ for all $d \leq 10^6$ from the hardened v6.1 kernel with an explicit no-overflow certificate.
• Large-scale evidence: the original v6 B200 run reports $R(d) \geq 1$ for all $d \leq 2.1 \times 10^{11}$, but this is strong computational evidence, not a certified result, because the kernel could silently clip frontiers.
• Conditional analytic framework: the Magee-Oh-Winter congruence-counting route suggests a threshold $D_0 \approx 3.4 \times 10^{10}$, but this depends on unresolved operator truncation, theorem-matching, and constant-propagation gaps.
• Rigor level: finite-matrix arithmetic is partially certified with arb/MPFR, but the transport from finite Galerkin matrices to the infinite-dimensional transfer operators is not yet proved. Paper is a proof framework, not a complete proof.

Full paper: PDF · LaTeX source · Verification manifest

Proof Architecture

The framework combines three ingredients (see paper PDF for full details):

1. Brute-Force Verification ($d \leq 2.1 \times 10^{11}$)

GPU matrix enumeration (v6 multi-pass kernel) reports every integer from 1 to 210 billion as marked. Zero uncovered. Runtime: 6,962.2 seconds (116 minutes) on 8× NVIDIA B200 (Blackwell, 183 GB each, CUDA 13.0, driver 580.126.09). Chunk configuration: 256 rounds × 8 GPUs, 119,210 seeds per chunk.

Exact invocation: ./matrix_v6 210000000000 (compiled with nvcc -O3 -arch=sm_100a scripts/experiments/zaremba-effective-bound/matrix_enum_multipass.cu -lpthread). Input: single argument $N = 2.1 \times 10^{11}$. Output: log reports zero uncovered integers. SHA256 checksums of the source and log are recorded in the verification manifest. The original run did not produce a per-level no-overflow certificate.

Certification status. The original v6 kernel increments out_count for every expansion but only writes the matrix if pos < max_out, then clips the next frontier to min(h_out, BUF_SLOTS) rather than aborting on overflow. The manifest records Uncovered: 0, but the kernel did not emit a machine-checkable no-overflow certificate.

Empirical update (2026-04-22). Local v6.1 probe runs on a single RTX 5090 at the exact 210B chunk size (119,210 seeds per chunk) measure:

• max_d = 10⁸: true unclipped Phase B peak frontier $= 1.91 \times 10^9$ (no overflow; 95.5% of the B200 $2 \times 10^9$ BUF_SLOTS)
• max_d = 10⁹: $17.5 \times 10^{12}$ (17.5 trillion) overflow events at local BUF_SLOTS $= 4 \times 10^8$, confirming the true per-level frontier repeatedly exceeded $4 \times 10^8$ — but the exact true peak cannot be recovered from a clipped probe

Because per-chunk peak is monotonically non-decreasing in max_d under fixed chunk size, the true peak at $\max_d = 2.1 \times 10^{11}$ is at least $1.91 \times 10^9$ and very likely larger. Whether the excess is small (keeping it under B200’s $2 \times 10^9$) or large (past $2 \times 10^9$) cannot be determined by our local probes — that requires a B200 v6.1 re-run.

What this does not say. Clipping does not directly invalidate Uncovered = 0. The bitset atomicOr mark fires before the pos < max_out check, so a clipped matrix still marks its denominator in the bitset; what is lost is its descendants. Because the 244 million Phase A seeds produce massively redundant CF coverage, denominators whose CF paths were clipped are almost always marked by other, unclipped paths. It is entirely consistent that Uncovered = 0 is correct even with significant clipping. The problem is that the v6 kernel does not prove this — it emits no machine-checkable certificate. This is a software-audit gap, not a mathematical one.

Path to certification. A hardened replacement, matrix_enum_multipass_v6_1.cu, adds a hard overflow abort and a final no-overflow certificate block. Re-running the 210B configuration with v6.1 on 8× B200 (or equivalent ≥ 1.5 TB aggregate GPU memory) and checking that the certificate reports All peaks < BUF_SLOTS: YES and No-overflow abort fired: NO upgrades the claim to certified status. If that run aborts with No-overflow abort fired: YES, the correct response is to increase num_rounds (e.g. to 512 or 1024) to reduce per-chunk seeds until the chunk size is safe, and record the new configuration as canonical. See paper/CERTIFICATE.md for the full probe log trail and audit procedure.

2. Spectral Gap Computation (11 primes, FP64)

For each prime $p \in \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31\}$, the spectral gap $\sigma_p$ of the congruence transfer operator $L_{\delta,p}$ is computed at FP64 precision ($N = 40$ Chebyshev collocation, cuBLAS power iteration). All gaps $\geq 0.530$. Note: 256-bit MPFR arithmetic controls round-off, but a rigorous bound on the truncation error between the $N = 40$ discretization and the infinite-dimensional operator (e.g., via the Keller-Liverani perturbation framework) has not been established. The “certification” applies to the finite Galerkin matrix, not rigorously to the full operator.

$p$	$\sigma_p$	Error bound $(1-\sigma)/\sigma$
2	0.845	0.183
3	0.745	0.342
5	0.956	0.046
7	0.978	0.022
11	0.886	0.129
13	0.530	0.887
17	0.912	0.097
19	0.957	0.045
23	0.861	0.161
29	0.616	0.623
31	0.780	0.282

3. Covering Argument (Frolenkov-Kan Sieve)

Sieve Bound. For $d$ coprime to prime $p$ with spectral gap $\sigma_p$, the Frolenkov-Kan sieve gives:

$R(d) \geq c \cdot d^{2\delta - 1} - \frac{1 - \sigma_p}{\sigma_p}$

where $c_1 = 1/|P'(\delta)| = 0.6046$ (from the Lalley renewal theorem, Appendix A of the paper) and $\delta = 0.8368$. For $d \geq 2$ and any covering prime with $\sigma_p \geq 0.530$: the main term $c \cdot d^{0.674} \geq 1.27$ exceeds the error $(1-\sigma)/\sigma \leq 0.887$. So $R(d) \geq 1$ for all $d \geq 2$ coprime to $p$.

Layered Covering. The covering proceeds in layers. For any integer $d \geq 2$, exactly one of the following holds:

• Layer 1: $d$ is coprime to some prime $p \in \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31\}$. The sieve at $p$ gives $R(d) \geq 1$. This covers all $d < \prod_{p \leq 31} p = 200{,}560{,}490{,}130$ (since such $d$ cannot be divisible by all 11 primes), PLUS all larger $d$ that happen to miss at least one of these primes.

• Layer 2: $d$ is divisible by every prime $\leq 31$ but coprime to some prime $p \in \{37, 41, \ldots, 97\}$ (all verified at FP64 with $\sigma_p \geq 0.530$). The sieve at $p$ gives $R(d) \geq 1$. This covers all $d < \prod_{p \leq 97} p \approx 2.3 \times 10^{36}$ that weren’t covered by Layer 1.

• Layer 3: $d$ is divisible by every prime $\leq 97$ but coprime to some prime $p \in \{101, \ldots, 3499\}$ (489 primes verified at FP64). The sieve at $p$ gives $R(d) \geq 1$. This covers all $d < \prod_{p \leq 3499} p \approx 10^{1500}$ not covered by previous layers.

• Layer 4 (non-constructive tail): $d$ is divisible by every prime $\leq 3499$. Then $d \geq \prod_{p \leq 3499} p \approx 10^{1500}$. By Bourgain-Gamburd (2008), property ($\tau$) holds: there exists $c > 0$ with $\sigma_p \geq c$ for all primes $p$. Since $d$ has finitely many prime factors, there exists a prime $p > 3499$ with $p \nmid d$. The F-K sieve at this $p$ gives $R(d) \geq 1$ for $d$ sufficiently large (depending on the non-effective constant $c$).

Critical note on Layer 4: This layer uses the non-constructive Bourgain-Gamburd property ($\tau$), making it non-effective. However, no integer smaller than $\approx 10^{1500}$ can reach this layer, and the brute-force verification to $2.1 \times 10^{11}$ provides a massive additional safety margin for Layers 1-3.

Note: The layered covering above is the supplementary BK/sieve perspective (Appendix B of the paper). The main proof of Theorem 2 uses the MOW framework instead, which avoids the non-constructive Layer 4 entirely — see “The Magee-Oh-Winter Framework” section below.

Mathematical Setup

The Semigroup

For each digit $a \in \{1,\ldots,5\}$, define $g_a = \begin{pmatrix} a & 1 \\ 1 & 0 \end{pmatrix}$. The continued fraction $[0; a_1, \ldots, a_k]$ has numerator and denominator given by the matrix product $g_{a_1} \cdots g_{a_k}$. The representation count is $R(d) = \#\{(a_1, \ldots, a_k) : a_i \in \{1,\ldots,5\},\ q_k = d\}$. Zaremba’s Conjecture is equivalent to $R(d) \geq 1$ for all $d \geq 1$.

The Transfer Operator

The Ruelle transfer operator at parameter $s > 0$:

$(\mathcal{L}_s f)(x) = \sum_{a=1}^{5} (a+x)^{-2s} f\!\left(\frac{1}{a+x}\right)$

The Hausdorff dimension $\delta = 0.836829443681208$ is the unique $s$ where $\rho(\mathcal{L}_s) = 1$. The leading eigenfunction $h$ (Patterson-Sullivan density) satisfies $\mathcal{L}_\delta h = h$ with $h(0) = 1.3776$.

Computed Constants

Quantity	Value	Method
Hausdorff dimension $\delta$	$0.836829443681208$	Chebyshev N=40, bisection
Eigenfunction $h(0)$	$1.377561602272515$	Power iteration, 1000 steps
Pressure derivative $P'(\delta)$	$-1.6539$	Hellmann-Feynman formula
Renewal constant $c_1 = 1/\|P'(\delta)\|$	$0.6046$	Lalley renewal theorem
Untwisted spectral gap $\sigma_0$	$0.7174$	Deflated power iteration
Dolgopyat bound $\rho_\eta$	$\leq 0.771$	Numerical (arb ball arithmetic on N=80 Galerkin matrix, not a computer-assisted Dolgopyat proof; no a-posteriori bound transporting to the full operator)
Power savings $\varepsilon$	$0.157$	$-\log(\rho_\eta)/

Transitivity (Algebraic Proof)

Theorem. The semigroup $\Gamma_{\{1,\ldots,5\}}$ acts transitively on $\mathbb{P}^1(\mathbb{F}_p)$ for every prime $p$.

Proof. Let $H = \langle g_1^2, g_1 g_2 \rangle \leq \text{SL}_2(\mathbb{F}_p)$. By Dickson’s classification:

1. Not Borel: $g_1^2$ has $(2,1)$-entry $= 1 \neq 0$ for all primes.
2. Not Cartan normalizer: $h_1 = g_1^2$ and $h_2 = g_1 g_2$ have characteristic polynomials $\lambda^2 - 3\lambda + 1$ and $\lambda^2 - 4\lambda + 1$. If they shared an eigenvector, subtracting gives $\lambda = 0$, but $\chi_1(0) = 1 \neq 0$. Contradiction.
3. Not exceptional for $p \geq 13$: $|H| \geq p^2 - 1 \geq 168 > 60 = |A_5|$.
4. Small primes $p \in \{2,3,5,7,11\}$: verified by exhaustive BFS.

Therefore $H = \text{SL}_2(\mathbb{F}_p)$, and every integer $d$ is admissible (no local obstructions). $\square$

The Magee-Oh-Winter Framework (Theorem 2)

The key upgrade from previous approaches: the Magee-Oh-Winter uniform congruence counting theorem (Crelle 2019) gives a pointwise power-saving error for the continued fractions semigroup, avoiding the circle-method minor-arc barrier entirely.

MOW Theorem: For the continued fractions semigroup $\Gamma_{\{1,\ldots,5\}}$:

$\#(\Gamma(q) \cap B_R) = \frac{c_\Gamma \cdot R^{2\delta}}{\#\text{SL}_2(\mathbb{Z}/q\mathbb{Z})} + O(q^C \cdot R^{2\delta - \varepsilon})$

with $\varepsilon > 0$ and $C > 0$ independent of $q$. This uses Dolgopyat-type transfer operator estimates, not the circle method.

From norm balls to denominators (Tauberian):

$R(d) = N(d) - N(d-1) \sim 2\delta \cdot c_\Gamma \cdot d^{2\delta - 1} + O(d^{2\delta - 1 - \varepsilon})$

For $R(d) \geq 1$: need $d^\varepsilon > C'/c_\Gamma$, giving threshold $D_0 = (C'/c_\Gamma)^{1/\varepsilon}$.

The Calderón-Magee explicit spectral gap (JEMS 2025) applies to Schottky subgroups with $\delta > 4/5$ (our $\delta = 0.837$ qualifies), making $\varepsilon$ computable in principle.

Result: $C_{\text{err}} \approx 536$, $\varepsilon' = 0.14$, $D_0 \approx 3.4 \times 10^{10} \leq 2.1 \times 10^{11}$. Margin: $6\times$.

Important caveats (DISPUTED — not yet rigorous):

1. The original MOW paper does not supply all constants explicitly; our constant extraction is a plausible numerical estimate, not a theorem.
2. The Calderón-Magee result gives an explicit gap only for untwisted operators; extending to twisted operators at all $q$ requires additional argument.
3. No detailed constant-tracking appendix (Sage or arb notebook) reproducing every numeric inequality is available. Until such a notebook is produced and independently verified, $D_0 \approx 3.4 \times 10^{10}$ is an estimate, not a rigorous bound.
4. The claim that “all load-bearing spectral data” are arb-certified applies only to the finite Galerkin matrices, not to the full infinite-dimensional operators.

Representation Growth

From our GPU computation (5.3 seconds, one B200):

$R(d) \sim d^{0.654} \quad \text{(empirical, } d \leq 10^6\text{)}$

Theoretical prediction: $R(d) \sim d^{2\delta - 1} = d^{0.674}$. The slight undercount (0.654 vs 0.674) is expected from finite-depth effects. Minimum $R(d) = 6$ at $d = 1$. Zero exceptions in $[1, 10^6]$. Full dataset: 1M rows CSV.

Reproduction

git clone https://github.com/cahlen/idontknow
cd idontknow

# Step 1: Brute force (requires 8× NVIDIA B200 or similar for 210B).
# Use v6.1 to get a no-overflow certificate in the final output.
nvcc -O3 -arch=sm_100a -o matrix_v6_1 \
    scripts/experiments/zaremba-effective-bound/matrix_enum_multipass_v6_1.cu -lpthread
./matrix_v6_1 210000000000

# Step 2: Spectral gaps (requires cuBLAS)
nvcc -O3 -arch=sm_100a -o extract_ef \
    scripts/experiments/zaremba-effective-bound/extract_eigenfunction.cu -lcublas -lm
./extract_ef  # outputs h(0) and gaps for primes ≤ 97

New Computations (2026-03-29)

MPFR-Certified Spectral Gaps

All 11 covering primes certified at 256-bit MPFR precision (77 decimal digits) with guaranteed rounding. All gaps $\sigma_p \geq 0.650$. This upgrades FP64 measurements to rigorous bounds.

Dolgopyat Spectral Profile (Exact Eigendecomposition)

We computed the spectral radius $\rho(t)$ of $L_{\delta+it}$ via exact eigendecomposition (LAPACK ZGEEV on the full 80×80 complex matrix) for 100,000 $t$-values.

Critical finding: Power iteration is unreliable for the twisted transfer operator — at certain $t$ values, multiple eigenvalues of similar magnitude with different phases cause oscillation instead of convergence. Full eigendecomposition is required.

• $\rho_\eta = \sup_{t \geq 1} \rho(t) \leq 0.771$ (arb-certified on $[1, 1000]$, MOW kernel decay for tail). Note: this bound applies to the $N = 80$ Chebyshev discretization of the transfer operator, not the full infinite-dimensional operator. A rigorous a-posteriori truncation error bound (e.g., via Keller-Liverani framework) transporting this result to the true operator has not been established.
• At $t = 1.0$: $\|L^{256}\|^{1/256} = 0.75796126 \pm 6.5 \times 10^{-70}$ (70 certified digits)
• For all $t \geq 2$: $\rho(t) < 0.68$ uniformly
• $\varepsilon_{\max} = -\log(\rho_\eta)/|P'(\delta)| = 0.157$

Renewal Constant

$c_1 = 1/|P'(\delta)| = 0.6046$ from the Lalley renewal theorem, computed via the Hellmann-Feynman formula using the left eigenmeasure $\nu$ and right eigenfunction $h$ of $\mathcal{L}_\delta$.

D₀ Calculation

With the corrected Dolgopyat bound, the MOW constant extraction gives:

• Optimal contour shift: $\varepsilon' = 0.145$
• $C_{\text{err}} = \kappa_1 + \kappa_2 \approx 200$
• $D_0 \approx 3.4 \times 10^{10}$ — a factor of 6× below the brute-force frontier of $2.1 \times 10^{11}$
• $C_\eta = 15$ (conservative above Naud bound $\leq 13$), all constants arb/MPFR-certified except $C_1$ (mpmath, 10% margin)

Relation to Shkredov (2026)

Independently and two weeks prior, Ilya Shkredov (arXiv:2603.14116, March 14, 2026) proved that for sufficiently large primes $q$, there exists $a$ coprime to $q$ with all partial quotients of $a/q$ bounded by $O(\sqrt{\log q})$. This is a major theoretical advance but does not resolve Zaremba’s Conjecture as originally stated:

	Shkredov (2026)	This work
Bound on partial quotients	$O(\sqrt{\log q})$ (growing)	$\leq 5$ (constant)
Denominators	Sufficiently large primes	All integers $d \geq 1$
Method	Analytic number theory	GPU computation + F-K sieve
Computational component	None	8× NVIDIA B200, ~2 hours
Status	Partial (asymptotic)	Conditional framework (computational)

The two results are independent and complementary. Shkredov’s purely analytic approach validates the spectral/semigroup framework from a theoretical direction. Our computation provides, to our knowledge, the largest brute-force verification and the most explicit spectral data computed for this problem.

References

• Zaremba, S.K. (1972). “La méthode des ‘bons treillis’ pour le calcul des intégrales multiples.” Applications of Number Theory to Numerical Analysis, pp. 39–119.
• Shkredov, I.D. (2026). “On some results of Korobov and Larcher and Zaremba’s conjecture.” arXiv:2603.14116.
• Frolenkov, D.A. and Kan, I.D. (2014). “A strengthening of a theorem of Bourgain-Kontorovich II.” Moscow Journal of Combinatorics and Number Theory, 4(1), pp. 24–117.
• Bourgain, J. and Kontorovich, A. (2014). “On Zaremba’s conjecture.” Annals of Mathematics, 180(1), pp. 137–196.
• Bourgain, J. and Gamburd, A. (2008). “Uniform expansion bounds for Cayley graphs of $\text{SL}_2(\mathbb{F}_p)$.” Annals of Mathematics, 167(2), pp. 625–642.
• Dickson, L.E. (1901). Linear Groups with an Exposition of the Galois Field Theory. B.G. Teubner, Leipzig.
• Huang, ShinnYih (2015). “An improvement to Zaremba’s conjecture.” Geometric and Functional Analysis, 25(3), pp. 860–914.
• Magee, M., Oh, H., and Winter, D. (2019). “Uniform congruence counting for Schottky semigroups in SL₂(Z).” J. reine angew. Math. (Crelle), 753, pp. 89–135.
• Calderón, I. and Magee, M. (2025). “Explicit spectral gap for Schottky subgroups of SL(2,Z).” J. Eur. Math. Soc.
• Lalley, S.P. (1989). “Renewal theorems in symbolic dynamics.” Acta Math., 163, pp. 1–55.

---

Computed 2026-03-29 on 8× NVIDIA B200 (1.43 TB VRAM) + RTX 5090. This work was produced through human–AI collaboration: the proof strategy, CUDA kernels, interval arithmetic, and documentation were developed jointly by Cahlen Humphreys and AI agents (Claude). The mathematical arguments have not been independently peer-reviewed. All code and data are open for verification at github.com/cahlen/idontknow. Published at bigcompute.science.