# Approximate primitive roots mod p

Artin conjectured that if $a$ is an integer which is not a square and not $-1$ then $a$ is a primitive root for infinitely many primes. This conjecture has not been resolved, but partial results are known: Heath-Brown showed that there are at most two prime numbers $a$ for which the conjecture fails.

I'd like to know if a different kind of partial result is known. Let $I(p)$ denote the index of the subgroup of $(\mathbf{Z}/p\mathbf{Z})^{\times}$ generated by 2. Thus $I(p)=1$ if and only if 2 is a primitive root mod $p$. Can one show that there is an infinite sequence of primes in which $I$ remains bounded?

• I'm assuming you don't want results conditional on GRH, since you classify Artin's conjecture as unresolved? Adam Felix has some nice results on the distribution of I(p) that amply imply your desired result, but the ones I know of are conditional on GRH. – Greg Martin Jul 18 '11 at 19:19
• Yes, I don't want to assume GRH. What I'm asking for follows from Artin's conjecture (since then you have an infinite sequence of primes on which I is 1), and thus from GRH. – Winnie Jul 21 '11 at 15:24

A result of Erdos and Murty asserts that if $\epsilon(p)$ is any decreasing function tending to zero, then $I(p) \leq p^{1/2-\epsilon(p)}$ for almost all primes $p$ (i.e., all but $o(\pi(x))$ primes $p \leq x$).

Kurlberg and Pomerance (see Lemma 20 in the paper mentioned below) show that for a positive proportion of primes $p$, one has the stronger bound $I(p) \leq p^{0.323}$. This follows from a result of Baker and Harman on shifted primes with large prime factors.

The Erdos--Murty paper is #77 at

http://www.mast.queensu.ca/~murty/index2.html

and the Kurlberg--Pomerance paper is

http://www.math.dartmouth.edu/~carlp/PDF/par13.pdf

See also Theorem 23 of this paper (which is conditional on GRH).

• Given that the Kurlberg--Pomerance paper is fairly recent, I'm assuming the result you mention from it is the best known, or at least close to it. That means the answer to my original question is "no," we can't prove the existence of an infinite sequence in which I is bounded. – Winnie Jul 21 '11 at 15:23
• I think that's right. The proof of Lemma 20 in that paper shows that you could improve $0.323$ to $\epsilon$ if you knew that there were infinitely many shifted primes $p-1$ with prime factors $> p^{1-\epsilon}$. Of course we think that $p-1$ is infinitely often twice a prime, which is much stronger and which would give the boundedness you originally asked for -- but this still seems hopeless. (However, progress towards this sort of conjecture plays a key role in the proof of the Heath--Brown proof you mentioned, and in the earlier work of Gupta and Murty.) – so-called friend Don Jul 21 '11 at 21:13

Here is something that is much weaker than what you are asking. The proof is elementary (but not entirely trivial). For every $\epsilon>0$, the series $$\sum_p \frac{I(p)^\epsilon}{p^{1+\epsilon}}$$ converges. For example, this implies that for every $N>0$, the set of primes $p$ satisfying $$I(p)>\frac{p}{(\log\log p)^N}$$ has (analytic) density zero.

• @Joe, That's a nice result. Please give a pointer to the proof. – Victor Miller Jul 19 '11 at 19:04
• @Victor: It's in Murty, Rosen, Silverman, Variations on a theme of Romanoff, Inter. J. Math. 7 (1996), 373--391. The results are phrased in terms of the order $f(p)$ of $a$ in $(\mathbb{Z}/p\mathbb{Z})^*$, instead of the index of the group generated by $a$, which gives the cleaner looking $\sum 1/pf_a(p)^\epsilon$. We handle more generally the image of finitely generated subgroups of a number field $K^*$ in the residue fields, and also the analog for fg subgroups of abelian varieties. – Joe Silverman Jul 19 '11 at 22:57