On the number of elite primes
Ali Taheri, Amir Saleh
math.NT
Nov 14, 2026 · v1
TL;DR
All theorems on counting elite primes are formalized in Lean 4 with Mathlib, taking Brun–Titchmarsh and two GRH consequences as explicit hypotheses.
Abstract
A prime $p$ is elite if all sufficiently large Fermat numbers $F_n=2^{2^n}+1$ are quadratic nonresidues modulo $p$. Let $E(x)$ be the number of elite primes up to $x$. The best published bounds are $E(x)\ll x/(\log x)^{3/2}$ unconditionally and $E(x)\ll x^{5/6}$ under the Generalized Riemann Hypothesis (GRH), both due to Just. Just and Pollack remarked, without a written proof, that sorting primes by the exact power of $2$ dividing $p-1$ should give $x/(\log x)^{2-\varepsilon}$ and $x^{3/4+\varepsilon}$. We give complete proofs of slightly sharper statements: $E(x)\le(16+o(1))x\log\log x/(\log x)^2$ unconditionally, and $E(x)\ll x^{3/4}(\log x)^{1/2}$ under GRH. We also recall, with short proofs, known facts about the period of $(F_n\bmod p)$ that go back to Aigner: every elite prime $p$ satisfies the defining condition from the index $v_2(\operatorname{ord}_p 2)$ onwards, and the period is even unless $p\in\{3,5\}$. Finally, we show under GRH that, when the moduli involved are at most $x^{1/3}$, the set of primes bounded by the sieve argument has size $\asymp x\log\log x/(\log x)^2$. This indicates that the remaining factor $\log\log x$ cannot be removed by this method alone. All theorems of the paper have been formalized in the Lean 4 proof assistant, with the Brun–Titchmarsh inequality and two standard consequences of GRH as explicit hypotheses.
Problem
A prime is elite if all sufficiently large Fermat numbers are quadratic nonresidues modulo it. Just and Pollack stated, without proof, improved upper bounds for the counting function E(x) of elite primes up to x: x/(log x)^{2-ε} unconditionally and x^{3/4+ε} under GRH.
Approach
Primes are sorted by the exact power of 2 dividing p−1. The resulting residue-class conditions are counted with Jacobi-symbol characters of Fermat-number products. The counts are bounded using the Montgomery–Vaughan form of Brun–Titchmarsh unconditionally, and GRH character-sum bounds conditionally. All 110 theorems are formalized in Lean 4 on Mathlib, with the analytic inputs taken as hypotheses, and #print axioms confirms only the standard axioms are used.
Results
The paper proves E(x) ≤ (16+o(1)) x log log x/(log x)^2 unconditionally and E(x) ≪ x^{3/4}(log x)^{1/2} under GRH. It gives short proofs of Aigner-type periodicity facts, including that the period is even for elite p ∉ {3,5}. Under GRH it shows the sieve set has size ≍ x log log x/(log x)^2, so this method alone cannot remove the log log x factor.