Zaremba Transitivity: Computation and Provisional All-Prime Strategy

The Finding

The semigroup $\Gamma_{\{1,\ldots,5\}}$, generated by the continued fraction matrices

$g_a = \begin{pmatrix} a & 1 \\ 1 & 0 \end{pmatrix}, \qquad a = 1, 2, 3, 4, 5$

acts transitively on $(\mathbb{Z}/p\mathbb{Z})^2 \setminus \{0\}$ for every tested prime $p \leq 17{,}389$.

The intended all-prime argument applies Dickson’s classification (1901) to our specific generators, combined with direct BFS computation for small primes. Audit status: this remains a proof strategy, not a completed theorem. The full generator set has determinant $-1$, so an all-prime proof must be stated carefully in $\mathrm{GL}_2(\mathbb{F}_p)$ or after passing to even words in $\mathrm{SL}_2(\mathbb{F}_p)$.

Audit status (2026-04-23): The finite computation is the reliable claim. The all-prime algebraic argument below should be read as provisional until a group theorist independently verifies the Borel, split/nonsplit Cartan normalizer, and exceptional subgroup exclusions in the correct ambient group.

The Argument

Revised April 2026 to fix three errors identified in o3-pro review: a circular size estimate in the exceptional exclusion, a basis-dependent Borel check, and a shared-eigenvector fallacy. The corrected argument below uses invariant-subspace analysis throughout.

We work with the generators directly: $g_1 = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ and $g_2 = \begin{pmatrix} 2 & 1 \\ 1 & 0 \end{pmatrix}$, both in $\text{SL}_2(\mathbb{Z})$. Let $G_p = \langle g_1, g_2, g_3, g_4, g_5 \rangle \leq \text{SL}_2(\mathbb{F}_p)$.

By Dickson’s theorem (1901), every proper subgroup of $\text{SL}_2(\mathbb{F}_p)$ is contained in one of the following maximal subgroups:

• Borel: the stabilizer of a line in $\mathbb{F}_p^2$ (upper triangular in some basis)
• Normalizer of a split Cartan: preserves a pair of lines (diagonal $\cup$ antidiagonal in some basis)
• Normalizer of a nonsplit Cartan: preserves a quadratic extension structure
• Exceptional: isomorphic to $A_4$, $S_4$, or $A_5$ (only possible for small $p$)

We show $G_p$ is not contained in any of these for any prime $p$.

(1) Not in any Borel subgroup ($p \geq 7$)

A Borel subgroup of $\text{SL}_2(\mathbb{F}_p)$ is the stabilizer of some line $\ell \subset \mathbb{F}_p^2$. If $G_p$ stabilizes $\ell$, then every generator $g_a$ stabilizes $\ell$, meaning $\ell$ is an eigenvector for every $g_a$.

The eigenvalues of $g_1$ satisfy $\lambda^2 - \lambda - 1 = 0$ (discriminant 5), giving eigenvectors proportional to $(\varphi, 1)$ and $(\psi, 1)$ where $\varphi, \psi = (1 \pm \sqrt{5})/2$ in $\mathbb{F}_p$. These are well-defined when $5$ is a quadratic residue mod $p$; when it is not, $g_1$ has no eigenlines over $\mathbb{F}_p$ and cannot lie in any Borel subgroup at all.

The eigenvalues of $g_2$ satisfy $\lambda^2 - 2\lambda - 1 = 0$ (discriminant 8), giving eigenvectors proportional to $((2 \pm \sqrt{8})/2, 1) = (1 \pm \sqrt{2}, 1)$ in $\mathbb{F}_p$.

For $g_1$ and $g_2$ to share a common eigenline, some eigenvector of $g_1$ must equal some eigenvector of $g_2$ (up to scalar). This requires $(1 \pm \sqrt{5})/2 \equiv 1 \pm \sqrt{2} \pmod{p}$ for some choice of signs. Squaring to eliminate the square roots and simplifying, one can check that these equations have no solution for $p \geq 7$. Explicitly: if $(1+\sqrt{5})/2 = 1 + \sqrt{2}$, then $\sqrt{5} = 1 + 2\sqrt{2}$, so $5 = 1 + 4\sqrt{2} + 8$, giving $\sqrt{2} = -1$ and thus $2 = 1$, which fails for $p \geq 3$. The other sign combinations yield similar contradictions (the details reduce to checking that $p \nmid 2, 3, 5$, which holds for $p \geq 7$).

Therefore $g_1$ and $g_2$ share no common eigenline over $\mathbb{F}_p$ for $p \geq 7$, so $G_p$ cannot be contained in any Borel subgroup.

(2) Not in any Cartan normalizer ($p \geq 7$)

The normalizer of a split Cartan subgroup preserves (setwise) a pair of lines $\{\ell_1, \ell_2\}$ in $\mathbb{F}_p^2$. Every element either fixes both lines or swaps them. In particular, each generator must permute $\{\ell_1, \ell_2\}$, so each generator’s eigenlines (if they exist) must be contained in $\{\ell_1, \ell_2\}$.

From (1), $g_1$ has eigenlines $\{(\varphi, 1), (\psi, 1)\}$ and $g_2$ has eigenlines $\{(1+\sqrt{2}, 1), (1-\sqrt{2}, 1)\}$. These are four generically distinct lines. For both $g_1$ and $g_2$ to normalize the same split Cartan, their eigenline pairs must coincide: $\{\varphi, \psi\} = \{1+\sqrt{2}, 1-\sqrt{2}\}$ as unordered pairs in $\mathbb{F}_p$. This forces either $\varphi = 1+\sqrt{2}$ or $\varphi = 1-\sqrt{2}$ (and similarly for $\psi$), which reduces to the same equations shown impossible in (1).

For the nonsplit Cartan normalizer: the nonsplit Cartan is diagonalizable over $\mathbb{F}_{p^2}$ but not over $\mathbb{F}_p$. Its normalizer preserves the associated quadratic extension structure. If $g_1$ lies in such a normalizer and has eigenvalues over $\mathbb{F}_p$ (i.e., 5 is a QR mod $p$), then $g_1$ lies in the split Cartan inside the nonsplit normalizer, which is impossible since its eigenlines are defined over $\mathbb{F}_p$. If 5 is not a QR mod $p$, then $g_1$‘s eigenvalues lie in $\mathbb{F}_{p^2} \setminus \mathbb{F}_p$, and it could a priori lie in a nonsplit Cartan. But then $g_2$‘s eigenvalue field is $\mathbb{F}_p(\sqrt{2})$, and for both to lie in the same nonsplit Cartan requires $\mathbb{F}_p(\sqrt{5}) = \mathbb{F}_p(\sqrt{2})$, i.e., $5 \cdot 2 = 10$ is a perfect square mod $p$. Even when this holds, the specific eigenvector pair of $g_1$ in $\mathbb{F}_{p^2}^2$ must match that of $g_2$, which again reduces to the algebraic constraints shown impossible above.

(3) Not an exceptional subgroup ($p \geq 61$)

The exceptional subgroups $A_4$, $S_4$, $A_5$ have orders 12, 24, 60 respectively. The element $g_1 \in \text{SL}_2(\mathbb{F}_p)$ has characteristic polynomial $\lambda^2 - \lambda - 1$, so its order in $\text{SL}_2(\mathbb{F}_p)$ divides $p^2 - 1$ (by Cayley-Hamilton and the structure of $\text{GL}_2(\mathbb{F}_p)$). For $p \geq 61$, we show $\text{ord}(g_1) > 60$, which prevents $G_p$ from being contained in any exceptional subgroup.

The eigenvalues of $g_1$ are the roots of $\lambda^2 - \lambda - 1$ in $\overline{\mathbb{F}_p}$. The order of $g_1$ equals the multiplicative order of these eigenvalues. Since $\lambda^2 = \lambda + 1$, the eigenvalue $\varphi$ generates a subgroup of $\mathbb{F}_{p^2}^{\times}$ whose order divides $p^2 - 1$ but not $p - 1$ (generically). For the order to be $\leq 60$, the eigenvalue must be a root of unity of degree $\leq 60$, which constrains $p$ to divide a specific finite set of resultants. Concretely: $\text{ord}(g_1) \leq 60$ iff $x^2 - x - 1$ divides $x^k - 1$ over $\mathbb{F}_p$ for some $k \leq 60$, iff $p$ divides $\text{Res}(x^2 - x - 1,\, x^k - 1)$ for some $k \leq 60$. Each resultant is a fixed integer, so only finitely many primes can satisfy this. Computing these 60 resultants and collecting their prime factors yields the finite set $\{2, 3, 5, 11, 19, 29, 31, 41, 59\}$ — all less than 61. (For example, $g_1$ has order 5 mod 5, order 10 mod 11, and order 29 mod 59.) This is a finite, verifiable computation with no circularity: it depends only on the characteristic polynomial of $g_1$, not on the size of the group it generates.

(4) Small primes ($p < 61$) by direct computation

For all primes $p < 61$ (specifically $p = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59$): exhaustive BFS confirms the orbit of $(0, 1)$ under $\langle g_1, \ldots, g_5 \rangle$ has size $p^2 - 1$, i.e., the semigroup hits every nonzero vector. This covers all primes where the Borel/Cartan argument requires $p \geq 7$ and the exceptional argument requires $p \geq 61$.

Conclusion

For $p \geq 61$: steps (1)-(3) show $G_p$ is not contained in any maximal proper subgroup of $\text{SL}_2(\mathbb{F}_p)$, so $G_p = \text{SL}_2(\mathbb{F}_p)$.

For $7 \leq p < 61$: steps (1)-(2) exclude Borel and Cartan, while step (4) provides direct computational verification of transitivity.

For $p < 7$: step (4) provides direct computational verification.

If the Dickson exclusions above are completed in the correct ambient group, they would imply the desired all-prime transitivity statement. At present, the certified statement on this page is the finite computation: transitivity holds for the first 2,000 primes, up to $p=17{,}389$.

Note: This argument was constructed with AI assistance (Claude, revised after o3-pro review) and applies well-known classical results (Dickson 1901) to our specific generators. The eigenvector non-coincidence in steps (1)-(2) and the order bound in step (3) are elementary but have not been independently verified by a human number theorist. The computational cross-check below provides supporting evidence for all primes up to 17,389.

Why This Matters

No Local Obstructions

A local obstruction at prime $p$ would mean some residue class $d \bmod p$ is never hit by the semigroup, immediately giving infinitely many counterexamples to Zaremba’s Conjecture.

The provisional argument above, if completed, would show that the orbit hits every nonzero vector mod $p$ for every $p$. The current verified computation shows this for $p \leq 17{,}389$.

The all-prime argument applies classical theory (Dickson’s classification) and is supported by exhaustive BFS computation for all primes up to 17,389 — but it has not been peer-reviewed and should not be cited as a theorem yet.

Computational Cross-Check

We independently verified transitivity by exhaustive BFS for all 2,000 primes up to $p = 17{,}389$ ($\pi(17{,}389) = 2{,}000$). The computation uses a CUDA kernel (one thread per prime) for $p \leq 500$ and a single-threaded CPU fallback for $500 < p \leq 17{,}389$; total wall time is 133 seconds. Zero exceptions in all cases are consistent with the proposed all-prime strategy.

This is strong finite-range evidence against local obstructions. It does not by itself prove $S(d)>0$ for all $d$.

Combined with Other Results

Together with our other findings, this gives a comprehensive picture:

1. No local obstructions found through $p=17{,}389$ (all-prime argument provisional — this page, not yet peer-reviewed)
2. Uniform spectral gap (property ($\tau$) not claimed, but finite-level spectral gap $\sigma_m \geq 0.237$ observed for 1,214 square-free moduli — spectral gaps)
3. Brute-force verification (zero failures to $d = 2.1 \times 10^{11}$; strong computational evidence pending v6.1 certification — experiment page)
4. Cayley graph diameters ($\text{diam}(p) \leq 2 \log p$ for all 172 primes $\leq 1021$ — Cayley diameters)

The remaining gap: making the error terms in the Bourgain-Kontorovich circle method effective to obtain an explicit $Q_0$. The Cayley diameter bound $\text{diam}(p) \sim 1.45 \log p$ constrains the maximum CF length needed modulo any prime, which feeds directly into the minor arc estimates.

Method

For each prime $p$:

1. Initialize the orbit with the seed vector $(0, 1) \in (\mathbb{Z}/p\mathbb{Z})^2$
2. BFS: apply $g_a$ and $g_a^{-1}$ for $a = 1, \ldots, 5$ to every visited vector
3. Continue until no new vectors are discovered
4. Check: orbit size $= p^2 - 1$ (all nonzero vectors)?

The state space is $(\mathbb{Z}/p\mathbb{Z})^2$ with $p^2$ states. Each BFS visits at most $p^2$ states with 10 neighbors each (5 forward + 5 inverse), so the work per prime is $O(p^2)$.

Implementation: CUDA kernel with one thread per prime for $p \leq 500$ (local-memory BFS, up to 250,001-byte visited and queue arrays per thread); single-threaded CPU fallback for $500 < p \leq 17{,}389$ (malloc’d visited and queue arrays). Source: scripts/experiments/zaremba-transitivity/check_transitivity.cu.

Data

Every prime has exactly 2 orbits:

Range	Primes	Non-transitive	Orbit structure
$p \leq 100$	25	0	2 orbits ($\{(0,0)\}$ + rest)
$100 < p \leq 1{,}000$	143	0	2 orbits
$1{,}000 < p \leq 5{,}000$	535	0	2 orbits
$5{,}000 < p \leq 10{,}000$	526	0	2 orbits
$10{,}000 < p \leq 17{,}389$	771	0	2 orbits
Total	2,000	0	All transitive

Code

# Compile (requires CUDA toolkit; kernel used for p <= 500, CPU fallback for larger p)
nvcc -O3 -arch=sm_100a -o check_transitivity \
    scripts/experiments/zaremba-transitivity/check_transitivity.cu

# Run for all primes up to 17,389 (the reported range; ~133 s on one GPU + CPU)
./check_transitivity 17389

Source: scripts/experiments/zaremba-transitivity/check_transitivity.cu

References

1. 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.
2. Dickson, L.E. (1901). Linear Groups with an Exposition of the Galois Field Theory. B.G. Teubner, Leipzig.
3. Bourgain, J. and Kontorovich, A. (2014). “On Zaremba’s conjecture.” Annals of Mathematics, 180(1), pp. 137–196. arXiv:1107.3776
4. Bourgain, J. and Gamburd, A. (2008). “Uniform expansion bounds for Cayley graphs of SL_2(F_p).” Annals of Mathematics, 167(2), pp. 625–642.

---

Computed in 133 s on NVIDIA DGX B200 (CUDA kernel for $p \leq 500$; single-threaded CPU fallback on 2× Intel Xeon Platinum 8570 for $500 < p \leq 17{,}389$). Algebraic argument constructed with AI assistance (Claude). All code and data open for independent verification at github.com/cahlen/idontknow.