pith. machine review for the scientific record. sign in

arxiv: 2603.11196 · v5 · submitted 2026-03-11 · 💻 cs.CR · math.NT

Recognition: 2 theorem links

· Lean Theorem

Primitive-Root Ratio over Prime Fields: A Shifted-Prime Distribution of Hausdorff Dimension Zero and Implications for PRIM-LWE

Vipin Singh Sehrawat
Authors on Pith no claims yet

Pith reviewed 2026-05-15 12:50 UTC · model grok-4.3

classification 💻 cs.CR math.NT
keywords primitive rootsfinite fieldsHausdorff dimensionsingular distributionsPRIM-LWELWE reductiontotient ratioErdős–Wintner
0
0 comments X

The pith

The primitive-root ratio c(p) for matrices over F_p drops to zero with min values of order 1 over log log x and its limiting measure has Hausdorff dimension zero.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines c(p) as the limiting fraction of n by n matrices over the finite field F_p whose determinant is a primitive root modulo p. This quantity is a multiplicative deformation of the totient ratio phi(p-1)/(p-1) and the paper shows it becomes arbitrarily small over the primes. Specifically, the smallest value among primes up to x is asymptotically comparable to 1 over log log x, while the reciprocal satisfies a limsup of e to the gamma times log log p. The associated limiting distribution is proved to be purely singular with Hausdorff dimension zero, yet it has full topological support on the closed interval from 0 to 1/2 and admits an explicit Bernoulli-product representation indexed by odd primes. The results supply concrete bounds on the expected rejection-sampling overhead when reducing ordinary learning-with-errors instances to their primitive-root variants in lattice-based cryptography.

Core claim

For a prime p, c(p) denotes the limiting fraction of n by n matrices over F_p whose determinant is a primitive root modulo p. Unconditionally inf over all primes p of c(p) equals zero and the sharp order satisfies min of c(p) for p up to x is asymptotically 1 over log log x. The reciprocal obeys limsup over primes p of 1 over (c(p) log log p) equals e to the gamma with no smaller constant possible. The limiting measure mu_G is purely singular and satisfies dim_H(mu_G) equals zero; it has full support on [0, 1/2], a Bernoulli-product representation over the odd primes, moments given by convergent Euler products, and a Mellin transform that extends to an entire function non-vanishing on the Re

What carries the argument

The primitive-root ratio c(p), the limiting probability that a uniform random matrix over F_p has determinant equal to a primitive root modulo p, obtained as a multiplicative deformation of the classical totient ratio phi(p-1)/(p-1).

If this is right

  • The dimension-uniform expected rejection-sampling overhead when reducing LWE to PRIM-LWE equals exactly 1 over c(p) for each prime modulus.
  • Explicit numerical overhead estimates follow for every prime that appears in current NIST post-quantum standards and in representative NTT-friendly moduli.
  • The tail probability satisfies 1 minus G of (1/2 minus epsilon) is asymptotic to kappa over log of 1 over epsilon for an explicit constant kappa near the right endpoint.
  • The entire Mellin transform and convergent Euler-product moments permit analytic control of all moments and tail estimates for cryptographic parameter selection.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • For very large primes one may need to avoid certain residue classes or choose smaller matrix sizes to keep the rejection overhead from growing like log log p.
  • The zero Hausdorff dimension implies that the realized values of c(p) are concentrated on an extremely thin set of limit points inside [0, 1/2].
  • Analogous singularity and dimension-zero phenomena are likely to appear in other natural multiplicative deformations of the totient function taken over shifted primes.

Load-bearing premise

The shifted-prime Erdős–Wintner–Hildebrand framework supplies a continuous limiting distribution for the values of c(p) as p runs over the primes.

What would settle it

An explicit sequence of primes p_k tending to infinity such that c(p_k) stays bounded away from zero by a fixed positive constant, or a numerical check showing that the limsup of 1 over (c(p) log log p) is strictly smaller than e to the gamma.

Figures

Figures reproduced from arXiv: 2603.11196 by Vipin Singh Sehrawat.

Figure 1
Figure 1. Figure 1: Empirical CDF of c(p) over the 78,497 primes 3 ≤ p ≤ 106 , overlaid with the theoretical limiting distribution function G of Theorem 5, estimated by 107 Monte Carlo samples of the infinite convolution of Lemma 10 truncated at the 10,000th odd prime. The empirical values of c(p) were computed via the truncated Euler product of Proposition 8 with J = 20 terms, contributing error below 10−9 for every prime p … view at source ↗
Figure 2
Figure 2. Figure 2: Empirical bin masses of c(p) over the 78,497 primes 3 ≤ p ≤ 106 , computed via Proposition 8 with truncation depth J = 20, using 100 equal-width bins covering [0, 0.5]. The dashed bars mark selected anchor values φ(m)/m for small even squarefree m. The concentration of mass near these arithmetic anchors reflects the dependence of c(p) on the small prime divisors of p − 1 and illustrates the clustering pred… view at source ↗
Figure 3
Figure 3. Figure 3: Squared modulus |µcf (τ )| 2 computed via the Euler product of Proposition 5 using all primes ℓ ≤ 107 . The top panel uses a linear scale and the bottom panel a log-log scale. The function oscillates but its local averages decrease across successive decades of τ [PITH_FULL_IMAGE:figures/full_fig_p024_3.png] view at source ↗
read the original abstract

For a prime $p$, let $c(p)$ denote the limiting fraction of $n\times n$ matrices over $\mathbb{F}_p$ whose determinant is a primitive root modulo $p$. The quantity $c(p)$ is a natural multiplicative deformation of the totient ratio $\varphi(p-1)/(p-1)$ and inherits its distributional behaviour over the primes. Existence and continuity of the limiting law follow from the shifted-prime Erd\H{o}s--Wintner--Hildebrand framework. We prove the following new results: unconditionally, $\inf_p c(p)=0$ and the sharp order is $\min_{p\le x}c(p)\asymp 1/\log\log x$; the reciprocal satisfies $\limsup_{p\to\infty, \, p\text{ prime}} 1/(c(p)\log\log p)=e^{\gamma}$, and no smaller constant suffices. We give a complete proof, combining an adaptation of Erd\H{o}s's argument with the Jessen--Wintner pure-type dichotomy, that the limiting distribution is purely singular, and strengthen this to $\dim_H(\mu_G)=0$, i.e. the limiting measure is carried by a Borel set of Hausdorff dimension zero. The distribution has full topological support $[0,\tfrac12]$ and admits a Bernoulli-product representation indexed by the odd primes. The moments are given by convergent Euler products, and the Mellin transform $\mathbb{E}[X^s]$ extends to an entire function of $s$, non-vanishing on $\operatorname{Re}(s)>0$. Near the right endpoint, $1-G(\tfrac12-\varepsilon)\sim\kappa/\log(1/\varepsilon)$ with an explicit constant $\kappa$. The quantity $1/c(p)$ equals the dimension-uniform expected rejection-sampling overhead in the reduction from learning with errors (LWE) to PRIM-LWE in lattice-based cryptography. The explicit bounds yield concrete overhead estimates for all primes appearing in current NIST post-quantum standards and representative NTT-friendly moduli.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 4 minor

Summary. The manuscript defines c(p) as the limiting fraction (as n→∞) of n×n matrices over F_p whose determinant is a primitive root modulo p. It shows that c(p) is a multiplicative deformation of φ(p−1)/(p−1) that inherits the distributional behavior of the shifted-prime Erdős–Wintner–Hildebrand framework. The paper proves unconditionally that inf_p c(p)=0 with sharp order min_{p≤x} c(p) ≍ 1/log log x, that limsup_{p prime} 1/(c(p) log log p)=e^γ with no smaller constant, that the limiting measure μ_G is purely singular with Hausdorff dimension zero, has full topological support on [0,1/2], admits a Bernoulli-product representation indexed by odd primes, has moments given by convergent Euler products, and that its Mellin transform extends to an entire function non-vanishing on Re(s)>0. Near the right endpoint it gives the asymptotic 1−G(1/2−ε)∼κ/log(1/ε). The quantity 1/c(p) is interpreted as the dimension-uniform expected rejection-sampling overhead in the LWE-to-PRIM-LWE reduction, with explicit bounds supplied for NIST post-quantum standards.

Significance. If the derivations hold, the work supplies a sharp analytic description of the primitive-root ratio distribution, strengthening classical singularity theorems to Hausdorff dimension zero while furnishing concrete, usable overhead estimates for lattice-based cryptography. The unconditional nature of the infimum and limsup results, the explicit Euler-product moments, the entire Mellin transform, and the direct cryptographic interpretation constitute genuine strengths. The adaptation of Erdős’s argument together with the Jessen–Wintner dichotomy is carried out in a standard framework and yields falsifiable predictions for the order of c(p).

minor comments (4)
  1. §3 (or wherever the Bernoulli-product representation is introduced): the indexing by odd primes is stated but the precise probability weights for each factor should be written explicitly to avoid any ambiguity in the product measure construction.
  2. The explicit constant κ in the near-endpoint asymptotic 1−G(1/2−ε)∼κ/log(1/ε) is announced but its closed-form expression is not displayed in the abstract or introduction; adding it would improve readability.
  3. Table of NIST moduli (presumably in the final section): include the precise numerical values of 1/c(p) alongside the overhead estimates so that readers can verify the concrete bounds without recomputing the Euler products.
  4. Notation: the limiting measure is denoted μ_G in the abstract but appears as μ or ν in some later statements; a single consistent symbol should be fixed throughout.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and encouraging report, which correctly identifies the main contributions of the paper: the unconditional sharp order of inf c(p), the strengthening to Hausdorff dimension zero, the Bernoulli-product structure, the entire Mellin transform, and the concrete overhead bounds for NIST moduli. The recommendation for minor revision is noted with appreciation. No major comments appear in the report, so we have no specific points to address.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper derives its main results on inf_p c(p)=0 with sharp order 1/log log x, the limsup 1/(c(p) log log p)=e^γ, and dim_H(μ_G)=0 by adapting external classical results (Erdős argument, Jessen–Wintner pure-type dichotomy, shifted-prime Erdős–Wintner–Hildebrand framework) to the deformed ratio c(p). The limiting law's existence and continuity are invoked from that framework; the Bernoulli-product representation and singularity follow directly from the dichotomy without internal fitting or self-referential definitions. No step reduces a claimed prediction or uniqueness to a parameter fitted inside the paper, nor does any load-bearing premise collapse to a self-citation chain. The cryptographic overhead claim is purely definitional. The derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claims rest on the shifted-prime version of the Erdős–Wintner–Hildebrand theorem for existence and continuity of the limiting law, plus the Jessen–Wintner dichotomy for singularity; no free parameters are introduced and no new entities are postulated.

axioms (2)
  • domain assumption shifted-prime Erdős–Wintner–Hildebrand framework supplies existence and continuity of the limiting law
    Invoked in the abstract for the distributional behaviour of c(p)
  • domain assumption Jessen–Wintner pure-type dichotomy applies to conclude the limiting measure is purely singular
    Used to strengthen singularity to Hausdorff dimension zero

pith-pipeline@v0.9.0 · 5685 in / 1515 out tokens · 42428 ms · 2026-05-15T12:50:39.895980+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages

  1. [1]

    Aivazidis and E

    S. Aivazidis and E. Sofos. On the distribution of the density of maximal order elements in general linear groups.Ramanujan J., 38(1):35–59, 2015

    work page 2015

  2. [2]

    Alkim, L

    E. Alkim, L. Ducas, T. Pöppelmann, and P. Schwabe. Post-quantum key exchange—a new hope. In 25th USENIX Security Symposium, pages 327–343. USENIX Association, 2016

    work page 2016

  3. [3]

    large sieve

    M. B. Barban. The “large sieve” method and its applications in the theory of numbers.Uspekhi Mat. Nauk, 21(1):51–102, 1966. English translation:Russian Mathematical Surveys, 21(1):49–103, 1966

    work page 1966

  4. [4]

    Bombieri

    E. Bombieri. On the large sieve.Mathematika, 12:201–225, 1965

    work page 1965

  5. [5]

    Brakerski

    Z. Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. In CRYPTO 2012, volume 7417 ofLNCS, pages 868–886. Springer, 2012

    work page 2012

  6. [6]

    Brakerski, C

    Z. Brakerski, C. Gentry, and V. Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping.ACM Trans. Comput. Theory, 6(3):13:1–13:36, 2014

    work page 2014

  7. [7]

    C. K. Caldwell and Y. Gallot. On the primality ofn!±1and2 ×3×5···×p±1.Math. Comp., 71(237):441–448, 2002

    work page 2002

  8. [8]

    J. B. Conway.Functions of One Complex Variable. Graduate Texts in Mathematics 11, Springer, 2nd edition, 1978

    work page 1978

  9. [9]

    Deshouillers and M

    J.-M. Deshouillers and M. Hassani. A note on the distribution function ofφ(p−1)/(p−1).J. Aust. Math. Soc., 93(1–2):77–83, 2012

    work page 2012

  10. [10]

    P. G. L. Dirichlet. Beweis des Satzes, dass jede unbegrenzte arithmetische Progression, deren erstes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Factor sind, unendlich viele Primzahlen enthält.Abh. Königl. Preuß. Akad. Wiss. Berlin, pages 45–81, 1837

    work page

  11. [11]

    Ducas, A

    L. Ducas, A. Durmus, T. Lepoint, and V. Lyubashevsky. Lattice signatures and bimodal Gaussians. In CRYPTO 2013, volume 8042 ofLNCS, pages 40–56. Springer, 2013

    work page 2013

  12. [12]

    P. Dusart. Explicit estimates of some functions over primes.Ramanujan J., 45(1):227–251, 2018

    work page 2018

  13. [13]

    P. D. T. A. Elliott.Probabilistic Number Theory II: Central Limit Theorems. Springer, Grundlehren der mathematischen Wissenschaften, vol. 240, 1980

    work page 1980

  14. [14]

    P. Erdős. On the smoothness of the asymptotic distribution of additive arithmetical functions.Amer. J. Math., 61(3):722–725, 1939

    work page 1939

  15. [15]

    Erdős and M

    P. Erdős and M. Kac. The Gaussian law of errors in the theory of additive number theoretic functions. Amer. J. Math., 62:738–742, 1940

    work page 1940

  16. [16]

    Erdős and A

    P. Erdős and A. Wintner. Additive arithmetical functions and statistical independence.Amer. J. Math., 61(3):713–721, 1939

    work page 1939

  17. [17]

    Falconer.Fractal Geometry: Mathematical Foundations and Applications

    K. Falconer.Fractal Geometry: Mathematical Foundations and Applications. John Wiley & Sons, second edition, 2003. 34 Vipin Singh Sehrawat

    work page 2003

  18. [18]

    Fan and F

    J. Fan and F. Vercauteren. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Paper 2012/144, 2012.https://eprint.iacr.org/2012/144

    work page 2012

  19. [19]

    Fouque, J

    P.-A. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Prest, T. Ricosset, G. Seiler, W. Whyte, and Z. Zhang. Falcon: Fast-Fourier lattice-based compact signatures over NTRU. Spec- ification v1.2, submission to the NIST Post-Quantum Cryptography Standardization Project, 2020. https://falcon-sign.info/falcon.pdf

    work page 2020

  20. [20]

    Halberstam

    H. Halberstam. On the distribution of additive number-theoretic functions (III).J. Lond. Math. Soc., s1-31(1):14–27, 1956

    work page 1956

  21. [21]

    M. Hamburg. Ed448-Goldilocks, a new elliptic curve. Cryptology ePrint Archive, Paper 2015/625, 2015. https://eprint.iacr.org/2015/625

    work page 2015

  22. [22]

    G. H. Hardy and J. E. Littlewood. Some problems of ‘Partitio Numerorum’; III: On the expression of a number as a sum of primes.Acta Math., 44(1):1–70, 1923

    work page 1923

  23. [23]

    Hildebrand

    A. Hildebrand. Additive and multiplicative functions on shifted primes.Proc. London Math. Soc. (3), 59(2):209–232, 1989

    work page 1989

  24. [24]

    Jessen and A

    B. Jessen and A. Wintner. Distribution functions and the Riemann zeta function.Trans. Amer. Math. Soc., 38(1):48–88, 1935

    work page 1935

  25. [25]

    I. Kátai. On distribution of arithmetical functions on the set prime plus one.Compos. Math., 19(4):278– 289, 1968

    work page 1968

  26. [26]

    Yu. V. Linnik. On the least prime in an arithmetic progression. I. The basic theorem.Rec. Math. [Mat. Sbornik] N.S., 15(57):139–178, 1944

    work page 1944

  27. [27]

    Lyubashevsky and G

    V. Lyubashevsky and G. Seiler. NTTRU: Truly fast NTRU using NTT.IACR Trans. Cryptogr. Hardw. Embed. Syst., 2019(3):180–201, 2019

    work page 2019

  28. [28]

    F. Mertens. Ein Beitrag zur analytischen Zahlentheorie.J. Reine Angew. Math., 78:46–62, 1874

    work page

  29. [29]

    H. L. Montgomery and R. C. Vaughan.Multiplicative Number Theory I: Classical Theory. Cambridge Studies in Advanced Mathematics, vol. 97. Cambridge University Press, 2006

    work page 2006

  30. [30]

    G. L. Mullen and D. Panario.Handbook of Finite Fields. Discrete Mathematics and Its Applications. CRC Press, 2013

    work page 2013

  31. [31]

    Federal Information Processing Standards Publication 203, 2024

    National Institute of Standards and Technology.Module-Lattice-Based Key-Encapsulation Mechanism Standard. Federal Information Processing Standards Publication 203, 2024

    work page 2024

  32. [32]

    Federal Information Processing Standards Publication 204, 2024

    National Institute of Standards and Technology.Module-Lattice-Based Digital Signature Standard. Federal Information Processing Standards Publication 204, 2024

    work page 2024

  33. [33]

    O. Regev. On lattices, learning with errors, random linear codes, and cryptography. InSTOC’05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 84–93. ACM, New York, 2005. Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE 35

    work page 2005

  34. [34]

    J. B. Rosser and L. Schoenfeld. Approximate formulas for some functions of prime numbers.Illinois J. Math., 6(1):64–94, 1962

    work page 1962

  35. [35]

    I. J. Schoenberg. Über die asymptotische Verteilung reeller Zahlen mod 1.Math. Z., 28:171–199, 1928

    work page 1928

  36. [36]

    V. S. Sehrawat, F. Y. Yeo, and Y. Desmedt. Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification.Theoret. Comput. Sci., 886:106–138, 2021

    work page 2021

  37. [37]

    Szepieniec and F

    A. Szepieniec and F. Vercauteren. Lattice-Based Cryptography in Miden VM.IACR Cryptology ePrint Archive, Paper 2022/1041, 2022

    work page 2022

  38. [38]

    Tenenbaum

    G. Tenenbaum. A note on the distribution of some additive functions.Proc. Steklov Inst. Math., 276:262–265, 2012

    work page 2012

  39. [39]

    Tenenbaum.Introduction to Analytic and Probabilistic Number Theory

    G. Tenenbaum.Introduction to Analytic and Probabilistic Number Theory. Graduate Studies in Mathematics, vol. 163. American Mathematical Society, Providence, RI, third edition, 2015

    work page 2015

  40. [40]

    Tenenbaum and J

    G. Tenenbaum and J. Wu.Exercices corrigés de théorie analytique et probabiliste des nombres. Cours Spécialisés, no. 2. Société Mathématique de France, Paris, 1996

    work page 1996

  41. [41]

    Xylouris

    T. Xylouris. On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions.Acta Arith., 150(1):65–91, 2011

    work page 2011