Small Prime Primitive Roots in Arithmetic Progressions
summary
The gist
Let p > 1 be a large prime number, let q = O(log log p) and let 1 ≤ a < q be a pair of relatively prime integers.
In short
The paper proves that for a large prime p, there exists a prime primitive root u in a specific arithmetic progression modulo q, where q is small relative to p. It shows such a primitive root u is bounded by (log p)(log log p), implying that the number of primitive roots on this progression grows significantly faster than previously thought.
Key concepts
- Primitive Root
- A prime number u in the field Fp is a primitive root if its powers generate all non-zero elements of the multiplicative group. For Fp, this means u^k covers every element from 1 to p-1 when k ranges from 0 to p-2.
- Divisor Dependent Characteristic Function
- This function, Psi(u), is used to check if an element u is a primitive root by analyzing its order. It involves the ratio of Euler's totient function phi(p-1) and the order of u in the group, specifically checking if ord_p(u) equals p-1.
- Error Term Analysis
- The total error term E(x, q, a) in counting primitive roots is broken down into two parts: E0 and E1. The paper bounds these terms using estimates involving x = (log p)(log log p), showing that the main term dominates the error as p gets large.
- Main Term M(x, q, a)
- The main term M(x, q, a) is derived from the ratio phi(p-1)/p multiplied by x/phi(q). This term is shown to be larger than the error terms E0 and E1 when p is large, which allows the proof to conclude that a primitive root exists in the specified range.
Terminology used across episodes
This episode discusses
The paper
Small Prime Primitive Roots in Arithmetic Progressions · Read on arXiv
N. A. Carella
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "Small Prime Primitive Roots in Arithmetic Progressions".
Paper summary: Emmy: So we're wrapping up the discussion on "Small Prime Primitive Roots in Arithmetic Progressions." The authors, N. A. Carella, are proposing this specific result about finding a prime primitive root u that is both small and in a certain arithmetic progression >
Ada: Exactly. They show that for any large prime p and any relatively prime integers a and q where q grows slowly with p, you can find such a root u bounded by log p times log log p five > <ref:2509.19309#pg1>
Kolya: What does this actually change for someone just listening to the show? It means there's an effective way to find these specific types of roots in finite fields using this machinery, which is useful for things like cryptography or number theory applications >
Emmy: And the result itself points towards a polynomial time algorithm for determining primitive roots in the prime finite field Fp because they connect this existence proof to Section nine of their paper "Small Prime Primitive Roots in Arithmetic Progressions" <ref:2509.19309#pg2> <ref:2509.19309#pg2,a polynomial time algorithm for determining primitive>
Ada: That's the practical side. The paper doesn't just prove it exists, it shows how to actually compute it efficiently once you know the factorization of p minus one >
Kolya: I think the main thing here is that they found a way to beat those existing exponential bounds on least primitive roots by utilizing this new characteristic function and showing the main term dominates the error term in their counting function analysis >
Emmy: And as we saw, even after estimating all those error terms, like E0 plus E1, the main term M(x, q, a) still manages to dominate when x is log p times log log p >
Ada: So essentially they've shown that for large primes p there's always a prime primitive root in this specific range and class because the machinery they developed overcomes the expected error terms >
Conclusion: Ada: So we're wrapping up our look at this paper, "Small Prime Primitive Roots in Arithmetic Progressions." Basically, they proved that for any large prime p and certain numbers a and q, you can always find a prime primitive root u that is small—bounded by something like log p times log log p.
Emmy: Exactly. They did this using these specific characteristic functions, which are ways to check if an element is a primitive root or not in the field Fp. It’s like they built these special filters for finding the right kind of number.
Kolya: From my side, I'm interested in how they handled those error terms. They broke down the total error into two parts, E0 and E1, and showed that even after accounting for them, the main term still wins out when p gets really big. That means the count is definitely bigger than what you'd expect by pure chance.
Ada: Right. The main point they drive home is that this existence holds for all sufficiently large prime numbers p, which is a big deal because it contradicts some existing limits on how small these roots can be.
Emmy: It suggests there’s a systematic way to locate these specific roots within predictable bounds, which points toward finding an algorithm for them. If you can find them efficiently, that’s a practical implication for number theory applications.
Kolya: Yeah, and if this holds up as p gets huge, it means we're not just lucky; there's a structure to exploit when searching for these roots in arithmetic progressions. It opens the door to better bounds on things like discrete logarithms.
More episodes
- 2509.05860-Concentration Inequalities for Branching Random Walks
- 2509.21830-Noncollapsing for Curvature Flows with Inhomogeneous Speeds
- 2510.08346-Separability and Submetrizability in Locally Convex Spaces
- 2510.27290-Borel Combinatorics of Schreier Graphs of Z-actions
- 2511.13500-Sampling Density for Gabor Phase Retrieval
- 2511.19161-Linear dynamics of random products of weighted shifts
- 2511.21548-Metastability of diffusion processes in narrow tubes
- 2512.01536-Abelian approximations for bicrossed products
- 2601.02524-Lagrangian slice disks with symplectomorphic exteriors
- 2601.13805-On rough ideal convergence