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)$.
Best Answer
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 "The Least Prime Primitive Root and the Shifted Sieve" in Acta Arith. 80 (1997), no. 3, 277–288; also on arxiv.
Unconditionally, I believe it's not even known that $G(p)$ is less than $p$ for all large $p$.