2026/03/11 by Vipin Singh Sehrawat
Computer Science · Mathematics · #cs.CR #math.NT
c(p): limiting fraction of n× n matrices over \mathbb Fp with primitive-root determinant; 1/c(p): rejection-sampling loss in PQ VSS; c(p)=\tfracφ(p-1)p-1∏j≥1(1-p-j). Over primes, c(p) follows φ(p-1)/(p-1): continuous on [0,1/2], X=\tfrac12∏ℓ≥3,prime(1-1/ℓ)Bℓ, Bℓ independent, Pr(Bℓ=1)=1/(ℓ-1). Hence infp c(p)=0, minp≤ xc(p)\asymp1/loglog x, \limsupp 1/(c(p)loglog p)=eγ on a primorial progression. μG is singular with dimHμG=0, sharpening Erdős (1939) for φ(n)/n. 1-G(\tfrac12-ε)∼\mathfrak S2e-γ/log(1/ε), \mathfrak S2 twin-prime singular series (infinitude unneeded); μf=logμG is Rajchman, with an explicit unconditional Fourier-decay rate from an effective bound for Graham-Kolesnik exponent-pair constants. \mathbb E[X-1]≈2.83 vs. worst case (1+o(1))eγloglog p; deterministic poly(log p)-time, factoring-free two-sided certificate for 1/c(p) of gap 1+o(1); Las Vegas generator of NTT-friendly primes q≡1\pmod2N; 1/c(p)>2 for all p, 1/c(p)≤(eγ+o(1))log y on y-friable shifts. Micciancio-Regev smoothing ηε(Λ) has kissing floor F=√(ln(K/ε)/π)/λ1(Λ^*) (K dual kissing number): at ε=2-cn every lattice has F≤ηε≤√(π/(min(c,1)ln2)),F; at fixed ε the ratio ηε/F can diverge as √(log n). For cyclotomic \mathbb Q(ζm) ((Ring-)LWE), an exact three-case law gives dual shell gap gm∈√(3/2),√2,√3, infimum √(3/2) on m:ωodd(m)≥2, discharging gap hypothesis unconditionally; at ε=2-cφ(m), c>2log2(1+√6) pins ηε(Λm) to the floor within 1+O(1/(cφ(m))).