Zaremba Representation Counts Grow as $d^{0.674}$

Correction (2026-07-21). The 2026-07-21 audit found that the original version of this page was backed by a defective dataset and contained sample values traceable to no computation at all. Every number on this page has since been recomputed from scratch with a clean reference implementation and independently cross-validated; see the correction notice at the bottom for exactly what was wrong. The headline conclusion — growth exponent $\approx 0.674$ matching the transfer-operator prediction — survives the correction and is now, for the first time, actually supported by the committed data.

The Finding

Fix the digit set $\{1,\ldots,5\}$. For each denominator $d$ we count two precisely defined quantities:

• $R_{\text{words}}(d)$ — the number of continued fraction words $(a_1,\ldots,a_k)$, $a_i \in \{1,\ldots,5\}$, whose denominator continuant $K(a_1,\ldots,a_k)$ equals $d$. This is the quantity counted by the Bourgain–Kontorovich transfer-operator heuristic.
• $R_{\text{fracs}}(d)$ — the number of numerators $a$ with $\gcd(a,d)=1$ such that $a/d = [0;a_1,\ldots,a_k]$ with all $a_i \le 5$. Since every rational has exactly two CF expansions, $R_{\text{words}} \approx 2\,R_{\text{fracs}}$.

Both grow as

$R(d) \sim C \cdot d^{2\delta - 1} \approx C \cdot d^{0.674},$

matching the transfer-operator prediction ($2 \times 0.836829 - 1 = 0.673659$). OLS regression of $\log R(d)$ on $\log d$ for $10^3 \le d \le 10^6$ (999,001 points, avoiding small-$d$ transients) gives fitted slope $\hat\alpha = 0.6741 \pm 0.0008$ (95% CI) — identically for both counting conventions, as it must, since they differ by a bounded factor. Raw-point $R^2 = 0.72$ because individual $R(d)$ fluctuate strongly (coefficient of variation $\approx 0.54$ within each decade); binning into tenth-decade geometric means gives slope $0.6727$ with $R^2 = 0.99996$.

Crucially, the hardest cases are small $d$, not large $d$:

$d$	$R_{\text{words}}(d)$	$R_{\text{fracs}}(d)$	Notes
1	1	1	Global minimum
2	2	1
6	3	2
13	16	9
100	32	16
1,000	120	64
10,000	532	271
100,000	2,718	1,424
1,000,000	12,992	6,761

$R_{\text{words}}(d) \ge 1$ for every $d \le 10^6$ (zero uncovered denominators — consistent with the exhaustive $A=5$ Zaremba verification), and $R_{\text{fracs}}(d) = 1$ only for $d \in \{1, 2\}$.

The complete dataset ($d \le 10^6$, both columns) is representation_counts_v2_1000000.csv (SHA-256 67c2389e87a5e598c59bd179d726d31a0379b172239143ce38e7fc82fc0edafb).

Computation Details

• Generator: count_representations_v2.c — a single-threaded CPU depth-first search on the denominator continuant recurrence $q_{\text{new}} = a\,q + q_{\text{prev}}$ from $(q, q_{\text{prev}}) = (1, 0)$. No frontier buffers exist, so nothing can silently clip.
• Scale: 11,415,955,624 CF words enumerated (5,956,450,306 distinct fractions) in 24.7 s on one CPU core (Apple M-series); run log committed as run_count_reps_v2_1e6.log.
• Cross-validation 1: an independent Python DFS recomputed both columns for all $d \le 3000$ — 0 mismatches.
• Cross-validation 2: brute-force enumeration over every coprime rational $a/d$ with $d \le 300$ (expanding each CF directly and testing admissibility of either expansion) — 0 mismatches against $R_{\text{fracs}}$.

Why This Matters

A counterexample to Zaremba’s Conjecture at $A=5$ would require $R(d) = 0$ for some $d$. Our data shows $R(d)$ grows in expectation: the Cesàro mean $\frac{1}{N}\sum_{d \le N} R_{\text{words}}(d)$ rises from 108.8 at $N=10^3$ to 11,416.0 at $N=10^6$, tracking $N^{2\delta-1}$. Individual values fluctuate (CV $\approx 0.54$ per decade), so “increasing” refers to decade means, not pointwise monotonicity.

This growth rate is exactly what the transfer operator predicts: the semigroup ball of matrices with digit entries in $\{1,\ldots,5\}$ and denominator $\le N$ has $\sim N^{2\delta}$ elements (here $1.14\times 10^{10} \approx (10^6)^{1.674}$, directly confirming the ball-size exponent), spread over $N$ denominators — giving each $d \le N$ about $N^{2\delta-1}$ representations on average.

Correction Notice (2026-07-21)

The original version of this finding failed audit on three counts, documented in the review ledger and remediation records:

1. The committed dataset was wrong. The GPU kernel count_representations.cu counted the numerator continuant $K(a_2,\ldots,a_k)$ (matrix entry $m_{10}$) instead of the denominator $K(a_1,\ldots,a_k)$, pre-seeded the count at $d=1$ (producing $R(1)=6$), and silently clipped each BFS level at 200M matrices while the true tree contains $1.14 \times 10^{10}$ nodes. That file is preserved as representation_counts_1000000_DEPRECATED.csv and must not be used.
2. The published sample values were fabricated by error. $R(100)=15$, $R(1000)=287$, $R(10^4)=6{,}842$, $R(10^5)=163{,}511$ matched neither the committed CSV nor any correct counting convention — and internally imply a growth exponent of $\approx 1.38$, contradicting this finding’s own headline.
3. Provenance was self-contradictory: the page simultaneously claimed Tesla V100 / 5.1 h, B200 / 47 min, and B200 / 5.3 s for the same computation, plus a SHA-256 for a file that never existed in the repository.

All quantities above were regenerated by the CPU reference implementation and doubly cross-validated as described. The fitted exponent from honest data ($0.6741 \pm 0.0008$) agrees with the theoretical $2\delta - 1 = 0.6737$ more cleanly than the original claim did.

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.
• Bourgain, J. and Kontorovich, A. (2014). “On Zaremba’s conjecture.” Annals of Mathematics, 180(1), pp. 137–196.
• Hensley, D. (1992). “Continued fraction Cantor sets, Hausdorff dimension, and functional analysis.” Journal of Number Theory, 40(3), pp. 336–358.

---

Computed on CPU (single-threaded reference implementation). Code: count_representations_v2.c.

This work was produced through human–AI collaboration (Cahlen Humphreys + Claude). Not independently peer-reviewed. All code and data open for verification at github.com/cahlen/idontknow.