Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For $p$ a prime number, let $G(p)$ be the least prime $q$ such that $q$ is a primitive root mod $p$, that is $q$ generates the multiplicative group $(\mathbb Z/p\mathbb Z$)* .

Is it known that $G(p)=O(p)$ ? I don't mind if the answer assumes GRH or any other standard conjecture.

I am interested in results true for all $p$, much less (though a little bit) on results which exclude a density $0$ or other smallish set of $p$. I note that it is easier to find bounds in the literature for $g(p)$, the least integer $n$ such that $n$ is a primitive root mod $p$. For example $g(p)=O(p^{1/2+\epsilon})$ was known unconditionally to Vonogradov in the 1930's (we have better unconditional results since), and with GRH we have result of type $g(p)=O(log^A p)$ with $A$ is some small constant. But what are the best results we have for $G(p)$? What are the best expected results ?

I am interested by $G(p)$ and not $g(p)$ because I use this problem as a testing ground of various effective forms of Chebotarev's there, and Chebotarev provides prime numbers. The best result I can prove this way is, under GRH, is $G(p)=O(p \log^{6+\epsilon} p)$ (edited: I made a mistake on the exponent of the $\log$), using Proposition 8.3 of the book of Ram Murty and Kumar Murty "Non-vanishing of $L$-functions and applications". With the GRH version of Lagarias-Odlyzko I get only $O(p^2 \log^2 p)$.

EDIT: Here is the proof of the estimate using Murty and Murty, as GH asked. Proposition 8.3 of Murty and Murty states that if $G$ is the Galois group of an extension $L$ of $\mathbb Q$, $D$ a union of conjugacy classes in $G$, and $M=\sum \log p$, the sum being on the primes ramified in $L$, then $$| \pi_D(x) - \frac{|D|}{|G|} Li\, x | < C |D|^{1/2} x^{1/2} \log(Mx),$$ where $C$ is an absolute constant, $\pi_D(x)$ the numbers of primes $p \leq x$ such that $Frob_p \in D$.

Let us apply this to $L=\mathbb Q(\mu_p)$, $D=$ set of primitive roots in $G=(\mathbb Z/p\mathbb Z)^\ast$. If for some real $x$, the principal term $\frac{|D|}{|G|} Li x = Li(x)/2$ is bigger than the error term $C |D|^{1/2} x^{1/2} \log(p x)$, then $\pi_D(x) > 0$ which means that $G(p)< x$.

So we write that inequality, and solve it for $x$, using $|D|=\phi(p-1)$, and replacing $Li(x)$ by $x/\log x$ which just changes the constant $C$. So we want: $$ x/(\log(x) x^{1/2}) > C \phi(p-1)^{1/2} (\log p + \log x).$$ Since $\log p \log x > \log p + \log x$ except for $x$ ridiculously small, it is enough to have $$ x/(\log(x) x^{1/2}) > C \phi(p-1)^{1/2} \log p \log x,$$ or, taking the square, $$x / \log^4(x) > C^2 \phi(p-1) \log^2 p$$ which is implied by $$x > C' \phi(p-1) \log^2 p \log^4(\phi(p-1) \log^2 p),$$ Hence $G(p)=O(\phi(p-1) \log^2 p \log^4(\phi(p-1) \log^2 p)) = O(p \log^{6+\epsilon} p)$.

share|cite|improve this question
According to… , a conjecture of Montgomery implies that, for EVERY residue class $a$ in $\mathbb{Z}/p^{\ast}$, there is a prime $q$ which is $O(p^{1+\epsilon})$ and represents $a$. I'm afraid I don't know more about this. – David Speyer Nov 16 '12 at 17:28
You may want to exclude successors of ( primorials and small multiples of primorials), as they may produce the hardest p to determine G(p). Or tackle them head on, as small values of phi(p-1) suggest potentially large values for G(p). Gerhard "But I May Be Wrong" Paseman, 2012.11.16 – Gerhard Paseman Nov 16 '12 at 17:34
@Gerhard: $\phi(p-1)$ is never too small, it is at least $C (p-1)/\log \log (p-1))$. A $\log \log$ term is not really important in those estimations. So I don't think it is "morally" necessary to excludes those primes. – Joël Nov 16 '12 at 17:50
@David: Yes. Actually a stronger form of this conjecture says that there is a prime $q$ that represents $a$ wiih $q=O(p \log(p)^2)$. And since (beware ! very bad heuristic follows...) it is much easier to find a prime which modulo $p$ falls in a set of $\phi(p-1)/2$ elements rather than on just one specific element, one could expect that $G(p) = O(p \log(p)^2 / (phi(p-1)/2)) = O(\log(p)^2 \log \log p)$ ! But very likely it's too naive... – Joël Nov 16 '12 at 17:54
@GH: I have wrote the answer -- and realized I made a mistake on my back of the envelope computation: the exponent of \log must be $6+\epsilon$, not $4$. Hope I haven't made an other mistake... – Joël Nov 16 '12 at 18:32

1 Answer 1

up vote 10 down vote accepted

For the expected behavior, see Paszkiewicz and Schinzel's paper "On the least prime primitive root modulo a prime" in Math. Comp. 71 (2002), no. 239, 1307–1321. There they examine a conjecture of Bach that $\limsup \frac{G(p)}{(\log p)(\log\log p)^2}=e^{\gamma}$.

It is known that almost always $G(p)$ is bounded by a fixed power of $\log{p}$, and the word `almost' can be removed if we assume GRH. (Under GRH, we in fact have $G(p) \ll (\log{p})^6$, and one can do better as long as $p-1$ doesn't have atypically many prime factors.) The best results I know in this direction are due to Greg Martin; see

Unconditionally, I believe it's not even known that $G(p)$ is less than $p$ for all large $p$.

share|cite|improve this answer
Greg Martin says $G(p) \ll (\log{p})^6$ under GRH is due to Shoup (1992). He says "Although both authors state their bounds only for primitive roots, the bounds actually hold for prime primitive roots as well." Can you explain why? – GH from MO Nov 16 '12 at 18:13
It looks from Wang's paper (which can be found by searching Google books for his collected works) that he actually shows the partial sums of $\Lambda(n) e^{-n/x}$, taken over primitive roots $n$ up to about $(log p)^{C}$, is positive. So this gives a prime small power $n$ which is a primitive root mod $p$. But then the prime which $n$ is a power of must also be a primitive root mod $p$. – Anonymous Nov 16 '12 at 18:43
Thank you very much! – GH from MO Nov 16 '12 at 18:51
Well, many thanks. I find striking how bad the effective chebotarev theorems (even those proved under GRH) are when we try to apply them in special situations, compared to what we can get directly in those situations. Here we have under GRH $O(\log^6 p)$ instead of $O(p \log^{6+\epsilon} p)$. Similarly, for the problem of the least prime in an arithmetic sequence, we expect $O(p \log^2 p)$ but with effective Chebotarev under GRH, we only get $O(p^2 \log^2 p)$. – Joël Nov 16 '12 at 18:57
Just wanted to confirm that Anonymous has said correctly almost everything I could say about unconditional results. Note that Linnik's theorem (with Xylouris's constant), applied to any one primitive-root residue class mod $p$, shows unconditionally that there exists a prime primitive root mod $p$ that is $\ll p^{5.2}$. As far as I know, this is the best unconditional, uniform result for prime primitive roots! – Greg Martin Nov 16 '12 at 20:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.