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

  • $\begingroup$ 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. $\endgroup$ Nov 16 '12 at 17:28
  • $\begingroup$ 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 $\endgroup$ Nov 16 '12 at 17:34
  • $\begingroup$ @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. $\endgroup$
    – Joël
    Nov 16 '12 at 17:50
  • 1
    $\begingroup$ @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... $\endgroup$
    – Joël
    Nov 16 '12 at 17:54
  • 1
    $\begingroup$ @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... $\endgroup$
    – 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 "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$.

  • 2
    $\begingroup$ 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? $\endgroup$
    – GH from MO
    Nov 16 '12 at 18:13
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Anonymous
    Nov 16 '12 at 18:43
  • $\begingroup$ 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)$. $\endgroup$
    – Joël
    Nov 16 '12 at 18:57
  • 6
    $\begingroup$ 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! $\endgroup$ Nov 16 '12 at 20:04
  • 2
    $\begingroup$ Actually, since here the modulus $p$ is prime, one can do better than 5.2: Meng has published an argument giving the constant 4.5, and a recent manuscript of Junsoo Ha gives the constant 3.1 or so. $\endgroup$ Nov 20 '12 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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