The PRIM-LWE problem requires the secret matrix to have a determinant that is a primitive root modulo a prime p. The security reduction from standard LWE to PRIM-LWE depends on how often random matrices over the finite field satisfy this condition — the density c(p) of matrices with primitive-root determinant.
The open question: does the infimum of c(p) over all primes equal zero? If so, the security reduction degrades for some primes, and PRIM-LWE cannot uniformly match standard LWE hardness (arXiv:2603.11196).
The answer is yes, and it follows from Dirichlet's theorem and Mertens' product formula — no unproved conjectures needed. The original conjecture that primorial primes were required was unnecessary. The density c(p) drops to zero along primes whose predecessor p-1 has many distinct prime factors, because more prime factors mean a smaller fraction of the multiplicative group consists of primitive roots.
The sharp rate is min c(p) ~ 1/log log x as x grows. The density has a continuous but purely singular limiting distribution over the primes, supported on exactly [0, 1/2]. Every prime contributes; no prime achieves density above 1/2; and the distribution is continuous but concentrates on a set of measure zero.
For the NIST-standardized moduli q = 3329 and q = 8380417, the rejection-sampling overhead — the cost of resampling until a primitive-root determinant appears — is at most 2.17 and 3.42 respectively. The practical impact on deployed cryptographic systems is bounded and modest.
The answer to the foundational question (yes, density approaches zero) and the answer to the practical question (overhead is small for real parameters) point in opposite directions. The structure that makes PRIM-LWE theoretically weaker makes it practically adequate.