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

6more comments