Flt.html

Artin's conjecture (primitive roots).

First, recall the meaning of the term primitive root modulo p ( p prime):

a is said to be a primitive root modulo p if (mod p ), and (mod p ) for all , ... , ( ). In other words, a is a primitive root modulo p if .

Maple examples:

> restart;

> with(numtheory): # needed for 'order' and 'phi'

Warning, new definition for order

> p := nextprime(200);

> order(2, p);

> order(3, p);

> order(4, p); # not a surprise:

> order(5, p);

>

So, 2 and 3 are primitive roots modulo 211, 4 (for obvious reasons, known in advance) is not a primitive root mod 211, and 5 also is not a primitive root modulo 211.

Recall a classic theorem of Gauss that p has exactly primitive roots in the interval [1, ], and let us make a list of all those primitive roots - and count how many there are - for :

> L := []: count := 0:
for a to (p-1) do
if order(a, p) = p-1 then
L := [a, op(L)]; count := count+1;
fi od; sort(L); count;

>

To determine how many there are one can, trivially, resort to:

> nops(L);

> phi(p-1); # the Gauss result:

>

That's all very straightforward, and well known. But now let us look at the fascinating unknown:

Fix the value of a , and ask: for how many primes p is a a primitive root?

In other words, for how many primes p does one have:

(mod p ) ... (i)

but (mod p ), all r in [1, ] ... (ii)

Here one has the (famous) conjecture of Emil Artin. Let a be any integer ( , and not a square), then a is a primitive root mod p for infinitely many primes p . (In 1958 Schinzel and Sierpinski showed Artin's conjecture is a consequence of the prime tuples conjecture , and in 1986 Heath-Brown proved ( unconditionally ) Artin's conjecture for infinitely many a (but no single ' a ' is known for which the conjecture is true).)

A remarkable quantitative version (for such an a ) of this conjecture - by Artin - had been : Let be the number of primes less than or equal to x for which a is a primitive root, then:

is asymptotic to as

where A ( Artin's constant ) is defined by:

( = 0.3739558136... )

In other words:

tends to as

[I should point out to readers, perhaps not entirely familiar with Number Theory, that the ' ' is the main asymptotic term of the famous, classic Prime Number Theorem; it is, roughly, the number of primes up to x .]

Above I wrote " had been ", because computational work by the Lehmers (D.H. and E., 1962) revealed an error (an independence error in a probability argument), that error being set right by Tate and Lang (both of whom had been Artin's students) in their 1965 preface to Artin's Collected Papers (1965).

Hooley (1967) proved that the above quantitative result is true for squarefree a ( ) subject to the Generalised Riemann Hypothesis.

The truly extraordinary , corrected version (formulated by Heilbronn, as detailed in the Royal Society Mathematical Tables 9 Indices and Primitive Roots by A. E. Western and J. C. P. Miller) reads as follows (in Bach and Shallit):

Let , with squarefree, and let h be the largest integer for which a is a power. Let

where the first product is taken over primes q dividing h

and the second is taken over primes q not dividing h

then (conjecture) is asymptotic to as if (mod 4)

otherwise (conjecture) is asymptotic to as , where

where ' ' is the Mobius function (in Maple that's 'mobius')

the first product is taken over primes q dividing

and the second is taken over primes q dividing but not dividing h

(see page 222 of Bach and Shallit for many references)

Some Maple work:

> A := product(1 - 1/(ithprime(r)*(ithprime(r)-1)),r=1..infinity);

> evalf(A); # it is NO surprise that Maple cannot evaluate A:

Error, (in evalf/product1) cannot evaluate boolean

So, let's merely get an approximate value:

> A[20] := product(1 - 1/(ithprime(r)*(ithprime(r)-1)),r=1..20);

> evalf(A[20]);

>

In the following I calculate the number of times for which 2 (then 3, 5, 27) is a primitive for primes up to 'x' (for various x's: ; one may take higher values depending on the speed of computer available), and the relative frequency (i.e., relative to ). Here I have written a simple Maple procedure, which might not be familiar to all my readers, but it ought to be clear what is going on (and I spell it out just once):

> Artin := proc(a, x) local count, r;
count := 0:
for r while ithprime(r) <= x do
if order(a, ithprime(r)) = ithprime(r)-1 then
count := count+1
fi od; print(count, count/evalf(x/ln(x))); end:

> Artin(2, 10^2);