Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE
Vipin Singh Sehrawat {[email protected]} · 2026
Read Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE by Vipin Singh Sehrawat {[email protected]} (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-11196.txt.
Introduction
Vipin Singh Sehrawat studies the limiting law of a shifted-prime quantity. It is the chance a random matrix over a finite field has a primitive-root determinant. He proves the limiting law has Hausdorff dimension zero. Yet it gives full mass to absolutely normal Liouville numbers. Sets of positive mass still carry substantial packing dimension. Effective Fourier decay bounds round out the results. So do sharp convergence rates in arithmetic progressions. So do concentration expansions. The list of unconditional results is long.
Catalog record
| CREATOR | Vipin Singh Sehrawat {[email protected]} |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 95719 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.11196
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE Thanks: The views expressed in this paper are solely those of the author and do not necessarily reflect those of Circle Internet or any other affiliated organizations. Vipin Singh Sehrawat {[email protected]} Abstract The prim-lwe problem, introduced by Sehrawat, Yeo, and Desmedt (Theoretical Computer Science, 886 (2021)), is a variant of the Learning with Errors problem in which the secret matrix is required to have a primitive-root determinant. The dimension-uniform reduction constant is c ( p ) = inf n ≥ 1 c n ( p ) c(p)=\inf_{n\geq 1}c_{n}(p) , where c n ( p ) c_{n}(p) is the exact density of n × n n\times n matrices over 𝔽 p \mathbb{F}_{p} with primitive-root determinant. Sehrawat, Yeo, and Desmedt asked whether inf p prime c ( p ) = 0 \inf_{p\text{ prime}}c(p)=0 , observing that an affirmative answer would follow from the conjectural infinitude of primorial primes. We resolve this question unconditionally using only Dirichlet’s theorem and Mertens’ product formula, bypassing the primorial-prime hypothesis. We further establish the sharp order min p ≤ x c ( p ) ≍ 1 log log x ( x → ∞ ) , \min_{p\leq x}c(p)\asymp\frac{1}{\log\log x}\qquad(x\to\infty), and show that the limiting distribution of c ( p ) c(p) over the primes has support exactly [ 0 , 1 / 2 ] [0,1/2] . This full-support property appears to be new. The law coincides with the classical shifted-prime distribution of φ ( p − 1 ) / ( p − 1 ) \varphi(p-1)/(p-1) via a transport lemma, is moreover continuous and purely singular, and the limiting measure has Hausdorff dimension 0 0 . The moments of the limiting distribution are given by convergent Euler products that uniquely determine it, and the associated Mellin transform extends analytically to the right half-plane. We also derive explicit lower bounds on c ( q ) c(q) for primes of cryptographic interest, parameterized solely by the number of distinct prime factors of q − 1 q-1 . As a simple conservative explicit bound, for any prime q > 2 30 q>2^{30} the dimension-uniform expected overhead 1 / c ( q ) 1/c(q) is at most 1.79 log q 1.79\log q . On the other hand, our results show that the worst-case overhead among primes p ≤ x p\leq x is of order Θ ( log log x ) \Theta(\log\log x) , and in particular 1 / c ( q ) = O ( log log q ) 1/c(q)=O(\log\log q) pointwise. 1 Introduction Let p be a prime and M_{n}(\mathbb{F}_{p}) denote the ring of n\times n matrices over \mathbb{F}_{p} . Following [ 1 ] , a matrix M\in M_{n}(\mathbb{F}_{p}) has primitive-root determinant if \det(M) generates \mathbb{F}_{p}^{*} . The fraction of such matrices is denoted c_{n}(p) ; since it is decreasing in n , the dimension-uniform constant governing the reduction from decision-LWE to decision- prim-lwe is c(p):=\inf_{n\geq 1}c_{n}(p)=\lim_{n\to\infty}c_{n}(p) . The precise formulas are recorded in Section 2 . Sehrawat, Yeo, and Desmedt [ 1 , Remark 3(ii)] asked whether \inf_{p}c(p)=0 can be proved unconditionally; see Section 2 for the precise statement. Main results We resolve this question and establish several natural refinements. 1. Unconditional vanishing (Theorem 3 ). We prove \inf_{p\text{ prime}}c(p)=0 using only Dirichlet’s theorem on primes in arithmetic progressions and Mertens’ third theorem, without assuming the primorial-prime hypothesis; see Section 3 . 2. Sharp order of the minimum (Proposition 1 , Corollary 8 ). By additionally invoking Linnik’s theorem on the least prime in an arithmetic progression, together with standard prime-number-theorem consequences for primorials, we establish \min_{p\leq x}c(p)\;\asymp\;\frac{1}{\log\log x}\qquad(x\to\infty). The matching lower bound follows from two observations: if p\leq x is an odd prime, then \omega(p-1)\leq m(x):=\max\{k:N_{k}\leq x\} , and Mertens’ theorem converts this into a 1/\!\log\log x lower bound for \varphi(p-1)/(p-1) ; the additional factor \prod_{j\geq 1}(1-p^{-j})\geq P_{3} is handled by Theorem 11 . Hence the decay to zero is quantified precisely. The implied constant is \approx 0.31 , so primes p whose predecessor p-1 is divisible by many small primes can still have c(p)<0.1 . The explicit bounds in Section 6 show that standard cryptographic moduli with controlled factorization incur only a small constant-factor overhead; see Remark 1 for effectivity. 3. Limiting distribution (Theorems 6 and 7 , Corollary 2 , Proposition 4 ). The quantity c(p) possesses a continuous limiting distribution over the primes whose support is exactly [0,\tfrac{1}{2}] ; the law is moreover purely singular, and Proposition 4 shows that the limiting measure has Hausdorff dimension 0 . If G denotes the distribution function, then 0<G(\tau)<1\qquad(0<\tau<1/2), the set of primes with c(p)\leq\tau has relative density G(\tau) , and G(\tau)\to 0 as \tau\downarrow 0 . The existence and continuity of G follow from the shifted-prime Erdős–Wintner framework for additive functions evaluated at p-1 [ 2 ] ; for the relevant classical background see Tenenbaum [ 3 ] and Deshouillers–Hassani [ 4 ] . Pure singularity is classical in the integer case (Erdős [ 5 ] ) and carries over to shifted primes by the same method, as noted by Tenenbaum [ 3 , p. 263] ; we include a self-contained proof for the reader’s convenience. Our new contribution on the distributional side is the full-support conclusion: the limiting law has support exactly [0,\tfrac{1}{2}] , established by combining the left non-differentiability result of [ 4 , Theorem 1.1] with the density of \{\varphi(m)/m:m\text{ even}\} in [0,1/2] (Lemma 4 ). Since the Euler product P(p)\to 1 , the prim-lwe density c(p)=\frac{\varphi(p-1)}{p-1}P(p) shares the same limiting distribution (Lemma 5 ). We also derive the moments of G as convergent Euler products (Theorem 8 ) and establish the analytic continuation of the Mellin transform \mathbb{E}[X^{s}] to the right half-plane (Theorem 10 ). At the right endpoint, 1-G(\tfrac{1}{2}-\varepsilon)\sim\kappa/\!\log(1/\varepsilon) as \varepsilon\downarrow 0 for an explicit constant \kappa (Proposition 7 ), so G is not Hölder of any positive order at 1/2 . 4. Explicit bounds for cryptographic moduli (Theorem 11 , Table 1 ). We give unconditional lower bounds on c(q) for primes q parameterized by \omega(q-1) , the number of distinct prime factors of q-1 , yielding concrete bounds for the NIST-standardized primes and other moduli whose predecessors have controlled factorization structure. The following consequence singles out the cryptographic implication: in the reduction from decision-LWE to decision- prim-lwe over \mathbb{F}_{q} , the dimension-uniform expected rejection-sampling overhead 1/c(q) admits an explicit upper bound depending only on \omega(q-1) . Corollary 1 (Cryptographic consequence) . Let P_{3}:=\prod_{j=1}^{\infty}\Bigl(1-\frac{1}{3^{j}}\Bigr)\approx 0.5601260779. Let q\geq 3 be a prime modulus with \omega(q-1)\leq K . Then \frac{1}{c(q)}\;\leq\;\frac{1}{P_{3}}\prod_{i=1}^{K}\frac{p_{i}}{p_{i}-1}. The general \omega(q-1) -based bound is immediate from Theorem 11 ; the sharper NIST figures use the exact factorizations recorded in Section 6 . Related work A related distribution problem was studied by Aivazidis and Sofos [ 6 ] , who considered the density of maximal-order elements in \mathrm{GL}_{n}(q) as q varies over prime powers and proved corresponding distribution laws. Their setting is different from ours: we work over prime fields and with the primitive-root determinant density arising in prim-lwe . On the distributional side, Deshouillers and Hassani [ 4 , Proposition 2.1