# Least prime primitive root

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)$.

-
According to mathoverflow.net/questions/834/… , 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

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

arxiv.org/abs/math/9807104

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

-
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