math0412262.tex
%\bibitem{ArtinPrimRoot}  
\documentclass[12pt]{article}
\usepackage{amssymb,latexsym,amsfonts}
\topmargin -0.5in
\textheight 22.3cm
\textwidth 13.5cm
\oddsidemargin 1.2cm
\parindent 1cm
\parskip 0cm

\newtheorem{theorem}{\noindent\bf Theorem}
\newtheorem{corollary}[theorem]{\noindent\bf Corollary}
\newtheorem{example}[theorem]{\noindent\bf Example}
\newtheorem{lemma}[theorem]{\noindent\bf Lemma}
\newenvironment{proof}{{\it Proof.\/}}{\bf $\Box$\\}
%\newcommand{\C}{\hbox{$\mathbb C$}}
\newcommand{\F}{\hbox{$\mathbb F$}}
\newcommand{\N}{\hbox{$\mathbb N$}}
\newcommand{\Q}{\hbox{$\mathbb Q$}}
%\newcommand{\R}{\hbox{$\mathbb R$}}
\newcommand{\Z}{\hbox{$\mathbb Z$}}
\newcommand{\ul}{\underline}
\newcommand{\mod}{{\rm mod}\,\,}
\newcommand{\backddots}{\mathinner{\mkern1mu\raise1pt\vbox
{\kern7pt\hbox{.}}\mkern2mu
\raise4pt\hbox{.}\mkern2mu\raise7pt\hbox{.}\mkern1mu}}

 
\begin{document}

\begin{center}
{\large\bf ARTIN'S PRIMITIVE ROOT CONJECTURE}\\
{\large\bf - a survey -}
\end{center}\vskip .5cm

\begin{center} PIETER MOREE \end{center}\vskip .5cm

\begin{minipage}[c]{12cm}
{\small {\sc Abstract}. This is an expanded version of
a write-up of a talk given 19-10-2000 at the DMV-seminar `The Riemann zeta function
and Random Matrix Theory' in Oberwolfach. A large part
of it was intended to be understandable by non-number theorists with
a mathematical background. The talk covered some of the history,
results and ideas connected with Artin's celebrated
primitive root conjecture dating from 1927. In the update several new results established after
2000 are also discussed.} 
\end{minipage}\vskip .5cm

\noindent Gauss considers
in articles 315-317 of his Disquisitiones Arithmeticae (1801)
the decimal expansion of numbers of the form $1\over p$ with $p$
prime.  For example, ${1\over 7}=0.{\underline{142857}}142857\ldots$, ${1\over
11}=0.{\underline{09}}0909\ldots$.  

These decimal expansions for $p\ne 2$ and $p\ne 5$ are purely periodic.  It
is easy to see that the period is equal to the smallest integer $k$ such
that $10^k\equiv 1(\mod p)$.  This integer $k$ is the {\it multiplicative
order} of 10 modulo $p$ and is denoted by ${\rm ord}_p(10)$.   The integer $k$
equals the order of the subgroup generated by $10$ in $(\Z/p\Z)^*$,
the multiplicative subgroup of residue classes modulo $p$.  By Lagrange's
theorem the order of a subgroup of a finite group is a divisor of the number
of elements in the group.  Since $(\Z/p\Z)^*$ has
$p-1$ elements, we conclude that ${\rm ord}_p(10)\mid p-1$.  If 
${\rm ord}_p(10)=p-1$,
we say that $10$ is a {\it primitive root} mod $p$.  The decimal expansion we have
given for $1\over 7$ shows that $7$ is a primitive root mod $10$.  Gauss'
table gives several other such examples and he must have asked himself
whether there are infinitely many such primes, that is, primes $p$ for which the
decimal period is $p-1$.  

Some light on this question can be shed on using the simple observation 
(due to Chebyshev) that if $q=4p+1$ is a prime with $p$ a prime
satisfying $p\equiv 2(\mod 5)$, then $10$ is a primitive root modulo $q$. 
To this end notice that, a priori, ${\rm ord}_q(10)=\{1,2,4,p,2p,4p\}$.  Now,
using the law of quadratic reciprocity, see e.g.
\cite{Lemmermeyer}, one deduces that
$$10^{2p}\equiv\left(10\over q\right)=\left(2\over q\right)
\left(5\over q\right)=(-1)^{q^2-1\over 8}\left(q\over 5\right)
=-\left(4\over 5\right) \equiv -1(\mod q).$$ Since no prime divisor of $10^4-1$
satisfies the requirements (and
hence ord$_q(10)\nmid 4$), one sees that ${\rm ord}_q(10)=4p=q-1$.  

The {\it logarithmic integral} ${\rm Li}(x)$ is defined
as $\int_2^x{dt/\log t}$.
The Prime Number Theorem in the form 
$\pi(x):=\# \{p\le x\}\sim {\rm Li}(x)$
as $x$ tends to infinity (i.e. the quotient of the r.h.s. and l.h.s. tends 
to 1 as $x$ tends to infinity), suggests that the `probability that
a number $n$ is prime' is $1/\log n$.  Thus for both $n$ and $4n+1$
to be prime and $n\equiv 2(\mod 5)$ we expect a probability of 
$1/({5\log^2n})$, assuming independence of these three events.  Since
they are not, we have to correct by some positive constant $c$ and hence expect
that up to $x$ there are at least $cx/{\log^2x}$ 
(note that $\sum_{n\le x}\log^{-2}n\sim x\log^{-2}x$) primes $p$ such that
$10$ is a primitive root mod $p$. Hence we expect that there are
infinitely many primes $p$ having $10$ as a primitive root mod $p$. This 
conjecture is commonly ascribed to Gauss, however, to the author's knowledge there
is no written evidence for it.

Emil Artin in 1927, led by a partial heuristic argument (sketched in \S 3), made the following
conjecture, where for a given $g\in \Q^*$ we define
${\mathcal{P}}(g)=\{p:{\rm ord}_p(g)=p-1\}$ and
${\mathcal{P}}(g)(x)=\#\{p\in{\mathcal{P}}(g):p\le x\}$.  (In general, if $S$
is a set, we define $S(x)=\#\{s\in S:s\le x\}$.)\\

\noindent\underline{Artin's primitive root conjecture (1927)}
Let $g\in \Q\backslash\{-1,0,1\}$.\\
{\it (Qualitative form)  The set ${\mathcal{P}}(g)$ is infinite 
if $g$ is not a square of a rational number.\\
(Quantitative form) Let $h$ be the largest integer such that
$g=g_0^h$ with $g_0\in\Q$. We have, as $x$ tends to infinity,   
\begin{equation}\label{P(g)(x)}
{\mathcal{P}}(g)(x)=\displaystyle\prod_{p\nmid
h}\left(1-{1\over{p(p-1)}}\right)
\displaystyle\prod_{p\mid h}\left(1-{1\over{p-1}}\right){x\over{\log x}}
+o\left(x\over{\log x}\right).
\end{equation}}
Denote the product appearing in (\ref{P(g)(x)}) by $A(h)$.
Note that $A(h)=0$ when $h$ is even. Then  ${\mathcal{P}}(g)$ is
finite and assertion (\ref{P(g)(x)})  is trivial. Thus the
condition that $g$ is not a square is necessary (and according to
Artin sufficient) for ${\mathcal{P}}(g)$ to be infinite.
For $h$ odd we have that $A(h)$ equals a
positive rational multiple of
$$A(1)=A=\displaystyle\prod_p\left(1-{1\over{p(p-1)}}\right)\approx 0.3739558136192\ldots,$$ the {\it Artin constant}. Thus the quantitative
form implies the qualitative form.\\
\indent The product defining the Artin constant does
not converge too quickly.  It turns out that for numerical approximations
it is possible and indeed much more efficient to write
$A=\prod_{k=2}^\infty\zeta(k)^{-e_k}$, with $e_k\in\N$ 
and $\zeta(s)=\sum_{n=1}^{\infty}n^{-s}$ the celebrated 
zetafunction of Riemann. This then allows one to determine $A$ without too much effort with
$1000$ decimal precision as zetavalues can be easily evaluated with high 
numerical precision, cf \cite{Monumi}.\\  
\indent Usually one
speaks about the Artin primitive root conjecture, rather than Artin's
conjecture since there are various unresolved conjectures due to Artin
(most notably the Artin holomorphy conjecture).\\
\vfil\eject
\noindent  The remainder of the
talk consists of the following 8 parts :

\begin{description}
\item[1)] Naive heuristic approach
\item[2)] Algebraic number theory
\item[3)] Artin's heuristic approach
\item[4)] Modified heuristic approach (\`a la Artin)
\item[5)] Hooley's work
\item[6)] Probabilistic model 
\item[7)] The indicator function
\item[8)] Some variations of Artin's problem
\end{description}

Our starting point in our analysis of Artin's primitive root
conjecture is the following observation : 
\begin{equation}
\label{uitgangspunt} 
p\in{\mathcal{P}}(g)\iff g^{p-1\over q}\not\equiv 1(\mod p) 
{\rm ~for~every~prime~}q{\rm~dividing~}p-1.
\end{equation}
\noindent "$\Longrightarrow$" Obvious.\\
"$\Longleftarrow$" Suppose $p\notin{\mathcal{P}}(g)$.  Then $g^{p-1\over
k}\equiv 1(\mod p)$ for some $k\mid(p-1)$, $k>1$.  But this implies that
$g^{p-1\over q_1}\equiv 1(\mod p)$ for some 
prime divisor $q_1$ of $k$. 
This is a contradiction.\\
\indent  Thus, associated with a prime $p$ we have
conditions for various $q$.  We are going to interchange the role of $p$ and
$q$, that is for a fixed $q$ we consider the set of primes $p$ such that 
$p\equiv 1(\mod q)$
and $g^{p-1\over q}\not\equiv 1(\mod p)$.\\
\indent I would like to point out, by the way, that there is more to decimal expansions
than meets the eye. 
For example, Girstmair \cite{Gi} proved that if a prime $p$ is such that its decimal expansion 
$1/p=0.x_1x_2\cdots x_{p-1}x_1\cdots$ has period $p-1$, then the difference between the sums of its even and odd places, 
namely $(x_2+x_4+\cdots +x_{p-1})-(x_1+x_3+\cdots+x_{p-2})$, is $11h_{\mathbb Q(\sqrt{-p})}$ if 
$p \equiv 3({\rm mod~}4)$ and is zero otherwise, where $h_{\mathbb Q(\sqrt{-p})}$ denotes the so-called class number
of the imaginary quadratic number field $\mathbb Q(\sqrt{-p})$ (I briefly 
discuss number fields in \S 2). Other examples are provided in \S 8.2, part 11 of \S 8.6 and Khare \cite{Khare}.\\

\noindent {\tt Warning}. This survey does not aim to be methodical and complete, rather it reflects the taste and likes of its 
author. Nevertheless, suggestions for inclusion of further material are appreciated as I intend to once in a while
update this work.
\vfil\eject 

\section{Naive heuristic approach}

Fix any prime $q$. We try to compute the density of primes $p$ such that 
both $p\equiv 1(\mod q)$ and
$g^{p-1\over q}\equiv 1(\mod p)$. 
By Dirichlet's theorem $p\equiv 1(\mod q)$ is true for primes $p$
with frequency $1/\varphi(q)={1/(q-1)}$.  Note that $g^{p-1\over
q}$ is a solution of $x^q\equiv 1(\mod p)$.  We expect there to be $q$
solutions and we want a solution to be $1$ modulo $q$.  Thus we expect to be
successful with probability $1\over q$, except when $q\mid h$.  Then
$g^{p-1\over q}=g_0^{h{p-1\over q}}\equiv 1(\mod p)$, trivially. If
we assume that these events are independent then the
probability that both events occur is $1\over q(q-1)$ 
if $q\nmid h$ and $1\over q-1$ otherwise.

By (\ref{uitgangspunt}) the above events should not occur for any
$q$ in order to ensure that $p\in{\mathcal{P}}(g)$.
This suggests a natural density of 
$$\displaystyle\prod_{q\nmid h}\left(1-{1\over q(q-1)}\right)
\displaystyle\prod_{q\mid h}\left(1-{1\over q-1}\right)=A(h)$$ for such primes. 
That is we expect (\ref{P(g)(x)}) to hold true.

\section{Algebraic number theory}

In order to understand Artin's approach to his conjecture we need some facts
about algebraic number theory.  We say $\alpha$ is {\it algebraic} over
$\Q$ if it satisfies an equation of the form $f(\alpha)=0$ with
$f(x)\in\Z[x]$.  We say $\alpha$ is an {\it algebraic} integer over
$\Q$ if it satisfies an equation of  the form $f(\alpha)=0$, where
$f(x)\in\Z[x]$ is monic.  A {\it number field} over $\Q$ is a
field obtained by adjoining finitely many algebraic numbers
$\alpha_1,\ldots,\alpha_s$ to $\Q$.  That is, $K=\Q(\alpha_1,\ldots,\alpha_s)$.  By $\Q(\alpha_1,\ldots,\alpha_s)$ we
denote the smallest field containing 
$\alpha_1,\ldots,\alpha_s$ and $\Q$. The
so called {\it theorem of the primitive element} asserts that for
a given number field $K$ there exists an algebraic integer $\alpha$ such
that $K=\Q(\alpha)$.  The element $\alpha$ is said to be a {\it primitive
element}.  For an algebraic integer $\alpha$ let $f_\alpha(x)$ be the
unique (as it turns out) monic polynomial $f_\alpha(x)$ of smallest degree
such that $f_\alpha(\alpha)=0$.
Then $K=\Q(\alpha)$ is isomorphic to $\Q[x]/(f_\alpha(x))$. 
The {\it degree} $[K:\Q]$ of $K$ is defined as deg$f_\alpha(x)$. The
{\it compositum} of two fields $K$ and $L$ is defined as the smallest
field containing both $K$ and $L$.\\

\noindent {\tt Example}. Let  $\alpha=i$.  Then $f_i(x)=x^2+1$. Note that  $\Q[x]$
contains elements of the form $\sum_{j=0}^ma_jx^j$. 
These elements correspond with an element in $\Q[x]/(x^2+1)$
obtained by replacing every $x^2$ by $-1$.  Thus, as a set,  
$\Q[x]/(x^2+1)\cong\{a+bx\mid a,b\in\Q\}$.  Similarly, as a
set, $\Q(i)=\{a+bi\mid a,b\in\Q\}$.  It is not difficult to
see that a field isomorphism between $\Q(i)$ and $\Q[x]/(x^2+1)$ is given by sending $x$ to $i$.\\
\indent For a general number field $K$, we have the following 
picture :
$$\begin{array}{rll}
\Q(\alpha)=K&\supset&{\mathcal{O}}_K\\
\cup&&\cup\\
\Q&\supset&\Z
\end{array}$$ 
Here ${\mathcal{O}}_K$ is the {\it ring of integers} of the field $K$.  It
plays a role analogous to that of $\Z$ in $\Q$ (in our example
 ${\mathcal{O}}_K$ is $\Z[i]=\{a+bi|a,b\in \Z\}$ the {\it ring of
Gaussian integers}). 
The {\it main
theorem of arithmetic} states that, up to the order of factors, factorisation
into primes in $\Z$ is unique.  One might hope for a ring inside $K$
with similar properties.  Let us consider the set of algebraic integers over
$\Q$ that are inside $K$.  This set is actually a ring, the ring of
integers, ${\mathcal{O}}_K$, of $K$.  It usually does not have unique factorization in
elements.  It, however, has unique factorization into terms of {\it prime
ideals} (up to order of factors).  The prime ideal $(p)$ in $\Z$ turns out to factor as
${\mathfrak P}_1^{e_1}\ldots {\mathfrak P}_g^{e_g}$ inside ${\mathcal{O}}_K$.  The equivalent statement
of $p=\# \Z/p\Z$ in $\Z$, reads in  ${\mathcal{O}}_K$:
$p^{f_i}=\# {\mathcal{O}}_K/{\mathfrak P}_i{\mathcal{O}}_K$.  Here $f_i$ is called
the {\it degree} of the prime ideal ${\mathfrak P}_i$.  We have the relationship
$\sum_{i=1}^ge_if_i=n$, with $n$ the degree of $K$.  
We say that a rational prime $p$ splits
completely in ${\mathcal{O}}_K$ if $e_i=f_i=1$ for $i=1,\ldots,g$.  Note that
in this case $g=n$.  If a prime $p$ splits completely in the ring of
integers ${\mathcal{O}}_K$, with $K\cong\Q[x]/(f(x))$, then over
$\Z/p\Z$, $f(x)$ splits into $n$ distinct linear factors.

\subsection{Analytic algebraic number theory}
Let $\mathfrak{O}$ run through the non-zero integral ideals of ${\mathcal{O}}_K$,
with $K$ a number field.  For $\Re(s)>1$, we define
$\zeta_K(s)=\sum_{\mathfrak{O}}N\mathfrak{O}^{-s}$ and
elsewhere by analytic continuation.  
Note that if $K=\Q$, then $\zeta_K(s)=\zeta(s)$, the usual zeta-function.
For $\Re(s)>1$ we have an Euler
product, 
$\zeta_K(s)=\prod_{\mathfrak P}(1-
N{\mathfrak P}^{-s})^{-1}$, where
the product runs over all prime ideals $\mathfrak P$ of  
${\mathcal{O}}_K$. 
In 1903, Landau proved the {\it Prime Ideal Theorem} to the effect that
$$\pi_K(x):
=\sum_{N{\mathfrak P}\leqq
x}1\sim{x\over\log x},~~ x\to\infty.$$  Assuming the {\it Riemann
Hypothesis} for the field $K$, that is, assuming that all the non-trivial
zeros of $\zeta_K(s)$ are on $\Re(s)={1\over 2}$, one obtains the much
sharper estimate
\begin{equation}\label{pik(x)}
\pi_K(x)={\rm Li}(x)+O_K(\sqrt{x}\log x),
~~x\to\infty,
\end{equation}
where the implied constant depends at most on $K$.\\
\indent  In the
analysis of Artin's primitive root conjecture an infinite family of fields
will play a role and we need an error term in (\ref{pik(x)}) that is
explicit in its dependency on
$K$.  Such a result was folklore and finally written down by Lang 
\cite{Lafolk}:
\begin{equation}
\label{langfolklore} 
\pi_K(x)={\rm Li}(x)+O(\sqrt{x}\log(x^{[K:{\mathbb Q}]}|D_K|)),
\end{equation} 
where $D_K$ 
denotes the
discriminant of the field $K$.\\
\indent The function $\pi_K(x)$ is heavily biased
towards prime ideals of degree one:
\begin{eqnarray*}
\pi_k(x)&=&\sum_{N{\mathfrak P}\leqq x\atop N{\mathfrak P}=p}1
+\sum_{N{\mathfrak P}\leqq x\atop N{\mathfrak P}=p^2}1+\ldots\\
&=&\sum_{N{\mathfrak P}\leqq x\atop N{\mathfrak P}=p}1
+O(\sum_{p^j\leqq x\atop j\geqq 2}1)
=\sum_{N{\mathfrak P}\leqq x\atop N{\mathfrak P}=p}1+O(\sqrt{x}).
\end{eqnarray*}

In Artin's problem one is specifically interested in so called {\it normal
fields}.  For such a field all prime ideals of degree one with at most
finitely many exceptions, come from rational primes $p$ that split
completely.  Throwing out these exceptions we have the following picture :
$$\begin{array}{c}
{\mathfrak P}_1{\mathfrak P}_2\dots{\mathfrak P}_n\\
\ddots\vdots\backddots\\
p_1
\end{array}\qquad
\begin{array}{c}
{\mathfrak P}'_1{\mathfrak P}'_2\dots{\mathfrak P}'_n\\
\ddots\vdots\backddots\\
p'_1
\end{array}$$
(A $[K:\Q]$-fold covering of the rational primes.)
Thus, for a normal field we have 
$$\pi_K(x)=[K:\Q]\sum_{p\leqq x\atop
p{\rm ~splits~completely~in~}K}1+O(\sqrt{x}\log x),$$ 
that is, by the Prime Ideal Theorem, 
\begin{equation}\label{sum{p leqq x}1}
\begin{array}{cll}
\displaystyle\sum_{p\leqq x\atop p{\rm ~splits~completely~in~}K}1
\sim{1\over[K:\Q]}{x\over\log x},~~x\to\infty.
\end{array}
\end{equation}
This is a particular case of a very important result called the 
{\it Chebotarev
density theorem}.  For a nice introductory account see Lenstra and
Stevenhagen \cite{LS}.\\ 

\noindent {\tt Example}. (Cyclotomic fields). A {\it
cyclotomic field} $K$ is a field of the form $K=\Q(\zeta_n)$ with
$\zeta_n=e^{2\pi i/n}$ and $n$ a natural number.  One can
show that $$f_{\zeta_n}(x)=\displaystyle\prod_{a=1\atop
(a,n)=1}^n(x-\zeta_n^a)=\Phi_n(x)\in\Z[x].$$  The polynomial
$\Phi_n(x)$ is the $n$th {\it cyclotomic polynomial}.  From this we deduce that
$[\Q(\zeta_n):\Q]={\rm deg~}\Phi_n(x)=\varphi(n)$.  The cyclotomic
fields are normal.  It can be shown that $p$ splits completely in $K\iff
p\equiv 1(\mod n)\iff x^n-1$ factors completely over $\Z/p\Z$.
 
On applying (\ref{sum{p leqq x}1}) we deduce that 
$$\displaystyle\pi(x,n,1):=\sum_{p\leqq x\atop p\equiv 1(\mod n)}1
\displaystyle\sim{1\over\varphi(n)}{x\over\log x},~~~x\to\infty,$$
a particular case of Dirichlet's theorem.  The same result can be deduced for the progressions $a(\mod n)$ with
$(a,n)=1$ on invoking Chebotarev's density theorem.

\section{Artin's heuristic approach} 
We have now the preliminaries available to follow the rest of the story on
the progress made on Artin's primitive root conjecture.  Remember that we
are interested in the set of all primes $p$ satisfying 
$$\left\{\begin{array}{rl}
p\equiv&1(\mod q)\\  
g^{p-1\over q}\equiv&1(\mod p),
\end{array}\right.
\hbox{}$$
where $q$ is any fixed prime.
By what we have learned about cyclotomic fields the primes $p\equiv
1(\mod q)$ are precisely those for which the equation $x^q\equiv 1(\mod p)$
has $q$ distinct solutions mod $p$.  I claim that if $g^{p-1\over
q}\equiv 1(\mod p)$, then $x^q\equiv g(\mod p)$ has a solution mod $p$.  To
see this, write $g=\gamma^a$ with $\gamma$ a primitive root mod $p$.  Then
$\gamma^{a{p-1\over q}}\equiv 1(\mod p)$.  A power of a primitive root can
only be congruent to $1(\mod p)$ if the exponent is a multiple of $p-1$,
hence $q\mid a$.  This says $a=bq$.  Then $(\gamma^b)^q\equiv g(\mod p)$ and
this proves the claim.  Let $\alpha_1,\ldots,\alpha_q$ be
the distinct mod $p$ solutions of $x^q\equiv 1(\mod p)$.  Then we see that
$\alpha_1\gamma^b,\ldots,\alpha_q\gamma^b$ are all distinct solutions of
$x^q\equiv g(\mod p)$. We conclude
that a prime that satisfies $p\equiv 1(\mod q)$
and $g^{p-1\over q}\equiv 1(\mod p)$ splits completely in the number field
\begin{equation}
\label{fielddefinition}
k_q:=\Q(\zeta_q,g^{1\over q}).
\end{equation}  
(Note that it does not make a difference
which $q$th root of $g$ we take, in that we always end up with the same
field.)  We leave it to the reader to show that if $p$ splits completely in
$k_q$, then $p\equiv 1(\mod q)$ and $g^{p-1\over q}\equiv 1(\mod p)$.  Thus
we have 
$$\left\{\begin{array}{rl}
p\equiv&1(\mod q)\\  
g^{p-1\over q}\equiv&1(\mod p)
\end{array}\right.
\hbox{$\iff p$ splits completely in $k_q$.}$$
Let us denote the degree of $k_q$ by $n(q)$.  It is not difficult to show
that $k_q$ is normal.  Hence we may apply (\ref{sum{p leqq x}1}) to deduce
that the number of primes $p\le x$ that do not split completely in $k_q$
equals $(1-1/n(q))x/\log x$, asymptotically.
So one expects $\prod_q(1-1/n(q))$ as the
density of primes $p$ for which $g$ is a primitive root mod $p$.\\
\indent  The latter
heuristic argument was believed until about 1960, when the Lehmers 
\cite{Lehmers} made some
numerical calculations that did not seem to always match with Artin's
heuristic.
Then, in 1968, Heilbronn realized that the events `$p$ does not
split completely in $k_q$' are not 
necessarily independent, as $p$ and $q$ range
through all primes and
published a corrected quantitative conjecture. Artin, however, made
this correction much earlier, namely in 1958 in a letter to the Lehmers
in a response to a letter of the Lehmers regarding his numerical work. 
Artin
did not publish his corrected conjecture, nor did the Lehmer's refer to
Artin in their paper \cite{Lehmers}, altough they give the correction
factor. 
As late as 1964 Hasse provides a correction factor in the 1964 edition
of his book \cite{Hasseboek} that is incorrect if $g\equiv 1({\rm mod~}4)$ is
{\it not} a prime.
For some excerpts of the correspondence between Artin and
the Lehmers see Stevenhagen \cite{Steven}.\\
\indent Take for example $g=5$, thus $h=1$.  Then
$k_2=\Q(\sqrt{5})\subseteqq k_5=\Q(\zeta_5,5^{1/5})$, i.e. $k_2$
is a subfield of $k_5$ (since
$\sqrt{5}=\zeta_5-\zeta_5^2-\zeta_5^3+\zeta_5^4$).
Now if $K\subseteqq L$ and $p$ splits completely in
$L$, then $p$ must split completely in $K$.  This means that the condition
`$p$ does not split completely in $k_2$' implies the condition `$p$ does
not split completely in $k_5$'.  So, assuming that
there are no further dependencies
between the various conditions on $q$, we expect that
$$
{\mathcal{P}}(5)(x)\sim
\displaystyle\prod_{p\ne 5}\left(1-{1\over{p(p-1)}}\right)
{x\over \log x },~~x\rightarrow\infty.
$$
Note that the constant involved equals $20A/19$.
This turns out to be more consistent with the numerical data than
Artin's prediction $A$.
\section{Modified heuristic approach (\`a la Artin)}
Recall that $k_q$ is defined in (\ref{fielddefinition}) for
prime $q$. Let $m$ be squarefree. We define $k_m$ to be the
compositum of the fields $k_q$ with $q|m$ and prime.  It can
be shown that $k_m=\Q(\zeta_m,g^{1/m})$. We are interested in the density of primes $p$ that do not
split completely in any $k_q$ (if
this exists).
We can try to compute it by inclusion-exclusion.  So
we start writing down $1-{1\over n(2)}-{1\over n(3)}\cdots$.  However, we
have counted double here the primes $p$ that split completely in both $k_2$
and $k_3$.  It can be shown that the primes that split completely in both
$k_n$ and $k_m$ are precisely the primes that split completely in
$k_{lcm(n,m)}$.  Thus we have to add ${1\over n(6)}$.  Continuing in
this fashion we arrive at the heuristic
\begin{equation}\label{P(g)(x)assymp}                                                                  
{\mathcal{P}}(g)(x)\sim\sum_{k=1}^\infty
{\mu(k)\over[\Q(\zeta_k,g^{1/k}):\Q]}{x\over\log x},~~x\rightarrow\infty.
\end{equation}
Here $\mu$ is the {\it M\"obius function}. It is defined by $\mu(1)=1$.
If $n>1$, then $\mu(n):=(-1)^s$, where $s$ denotes the number of distinct prime factors
of $n$ if $n$ is squarefree, and $\mu(n):=0$ otherwise.
If we are only interested in the primes $p$ that do not split completely in
any of $k_{q_1},\ldots,k_{q_s}$, with $s$ finite then there would be little
to prove (on invoking Chebotarev's theorem).  It is the 
{\it infinitely} many $q$ that makes the problem hard.

Artin's heuristic amounts to assuming that fields $k_{q_1}$ and $k_{q_2}$
are {\it linearly independent} over $\Q$ (i.e. 
$k_{q_1}\cap k_{q_2}=\mathbb Q$), for distinct primes $q_1$ and $q_2$.  
This has as a consequence that 
$[k_{q_1q_2}:\Q]=[k_{q_1}:\Q][k_{q_2}:\Q]$ and in
general, for squarefree $k$ that $n(k)={k\varphi(k)\over(k,h)}$.  Thus,
according to Artin we should have 
$$\sum_{k=1}^\infty{\mu(k)\over n(k)}
=\sum_{k=1}^\infty{\mu(k)(k,h)\over k\varphi(k)}
=\prod_{p\nmid h}\left(1-{1\over p(p-1)}\right)
\prod_{p\mid h}\left(1-{1\over p-1}\right)=A(h),$$ 
where in the derivation of the last equality we used the fact that if
$f(k)$ is a multiplicative function, then
$$\sum_{k=1}^\infty|f(k)|<\infty\Rightarrow
\sum_{k=1}^\infty f(k)=\prod_p(1+f(p)+f(p^2)+\cdots).$$
It can be shown that if $g\ne -1$ and $g$ not equal to a square, then
$$\displaystyle\sum_{k=1}^\infty{\mu(k)\over n(k)}=c_gA,$$ where $c_g>0$ is a
rational number depending on $g$.  It turns out that numerically the
heuristic (\ref{P(g)(x)assymp}) does not seem to be inconsistent with the
numerical data.  Let $g\ne -1$ or a square.  Hooley \cite{Hooley1} proved in 1967
that if the Riemann Hypothesis holds for the number fields
$\Q(\zeta_k,g^{1/k})$ with all squarefree $k$, then we have 
\begin{equation}
\label{classicalhooley} 
{\mathcal{P}}(g)(x)=\sum_{k=1}^\infty
{\mu(k)\over[\Q(\zeta_k,g^{1/k}):\Q]}{x\over\log x}
+O\left({x\log\log x\over \log^2x}\right)
\end{equation} 
and he explicitely evaluated the latter sum, say $\Sigma$, as 
\begin{equation}
\label{expli}
\Sigma=\left\{\begin{array}{rl}
A(h) & {\rm ~if~}d\not\equiv 1({\rm mod~}4);\\  
\left(1-\mu(|d|)\prod_{p|d\atop p|h}{1\over p-2}\prod_{p|d\atop p\nmid h}{1\over p^2-p-1}\right)A(h) & {\rm ~otherwise},
\end{array}\right.
\hbox{}
\end{equation}
with $d$ the discriminant of $\mathbb Q(\sqrt{g})$.
For convenience we denote
the assumption on the fields  $\Q(\zeta_k,g^{1/k})$ made by Hooley as
Hooley's Riemann Hypothesis (HRH) and the error term
${x\log\log x/\log^2x}$ as $R(x)$.

\section{Hooley's work}

For simplicity we assume $g=2$ and sketch Hooley's proof \cite{Hooley1}.
The restriction $g=2$ allows us to focus exclusively on the analytical
aspects, the algebraic aspects being discussed elsewhere in this survey.\\
\indent A large part of
his paper is devoted to proving an estimate for 
$$\hbox{$P(x,l)=\#\{p\leqq x: p$ splits completely in $k_l\}$},$$
for which the implied constant in the error term does not depend on $l$. 
His result on this is a special case of the result 
(\ref{langfolklore}) of Lang \cite{Lafolk} (proven a few
years later):
\begin{equation}
\label{hohoho}
P(x,l)={\rm Li}(x)+O(\sqrt{x}\log(lx)),
\end{equation}
where we assume the Riemann Hypothesis for $k_l$.  Another quantity needed
is 
$$\hbox{$N(x,\eta)=\#\{p\leqq x: p$ does not split completely in
$k_q,~q\leqq\eta\}$}.$$
By inclusion-exclusion we have $N(x,\eta)=\sum_{l'}\mu(l')P(x,l'),$
where $l'$ ranges over all divisors of $\prod_{q\leqq
\eta}q$.  Note that
$$\displaystyle\prod_{q\leqq\eta}q=e^{\sum_{q\leqq\eta}\log q}\leqq
e^{2\eta},$$
where we used that 
$\sum_{q\leqq\eta}\log q\sim\eta$ (which is equivalent with
the Prime Number Theorem).  
Note that
${\mathcal{P}}(2)(x)=N(x,x-1)$.  The problem in 
estimating $N(x,\eta)$ is that by using inclusion-exclusion and (\ref{hohoho})
is that we can only estimate $N(x,\eta)$ for rather small $\eta$, whereas
one would like to take $\eta=x-1$ and so we are forced to work with $N(x,\eta)$ for $\eta$
rather smaller than $x$.  We will actually choose $\eta={\log
x\over 6}$ and thus $l'<e^{2\eta}=x^{1/3}$. Let us
introduce a third quantity $M(x,\eta_1,\eta_2)=\#\{p\leqq x:p$ splits
completely in some $k_q,~\eta_1<q<\eta_2\}.$  It is easy to see that
$N(x,\xi_1)-M(x,\xi_1,\xi_2)-M(x,\xi_2,\xi_3)\leqq
{\mathcal{P}}(2)(x)\leqq N(x,\xi_1)$, that is, 
$${\mathcal{P}}(2)(x)=N(x,\xi_1)+O(M(x,\xi_1,\xi_2))
+O(M(x,\xi_2,\xi_3))+O(M(x,\xi_3,x-1)).$$  
We will choose $\xi_1={\log x\over 6}$,
$\xi_2={\sqrt{x}\over\log^2{x}}$ and $\xi_3={\sqrt{x}\log{x}}$.  Note
the small gap between $\xi_2$ and $\xi_3$.  This is the `hard region'
and unfortunately it is out of reach to close it and work say with 
$${\mathcal{P}}(2)(x)=N(x,\xi_1)+O(M(x,\xi_1,\xi_2))
+O(M(x,\xi_2,x-1)).$$  
Now using the estimate for $P(x,l)$ one easily arrives at   
\begin{eqnarray*}
N(x,\xi_1)&=&{\rm Li}(x)\sum_{l'\leqq x^{1\over 3}}{\mu(l')\over l'\varphi(l')}
+O\left({x\over\log^2{x}}\right)\\
&=&A {\rm Li}(x)+O\left({x\over\log^2{x}}\right)
\end{eqnarray*}
Again using the estimte for $P(x,q)$ we arrive at
$$M(x,\xi_1,\xi_2)\leqq\sum_{\xi_1\leqq q\leqq\xi_2}P(x,q)
=O\left({x\over\log^2{x}}\right).$$

In the region $(\xi_2,\xi_3)$ we use the fact that the primes $p$
counted by $P(x,q)$ certainly satisfy $p\equiv 1(\mod q)$.  Thus
$P(x,q)\leqq\pi(x,q,1)$.  Then using the Brun-Titchmarsh estimate 
$$\pi(x,q,1)<{2x\over \varphi(q)\log(x/q)},~~~1\leqq q<x,$$
we obtain
$$M(x,\xi_2,\xi_3)\leqq\sum_{\xi_2\leqq q\leqq\xi_3}P(x,q)\leqq 
\sum_{\xi_2\leqq q\leqq\xi_3}\pi(x,q,1)
=O(R(x)).$$
Finally, if a prime $p$ is counted by $M(x,\xi_3,x-1)$, then its order is
less than ${x\over \xi_3}={\sqrt{x}\over \log x}$ and thus it divides
$2^m-1$ for some $m<{\sqrt{x}/\log{x}}$.  Now
$$2^{M(x,\xi_3,x-1)}<
\prod_{p~{\rm counted~by~}M(x,\xi_3,x-1)}p
\leqq\displaystyle\prod_{m<{\sqrt{x}\over\log{x}}}(2^m-1).$$
Thus $$M(x,\xi_3,x-1)<\displaystyle\sum_{m<{\sqrt{x}\over\log{x}}}m
=O\left({x\over\log^2{x}}\right).$$  On gathering all terms we obtain
${\mathcal{P}}(2)(x)=A{\rm Li}(x)+O(R(x)).$\\
\indent Repeating this argument for arbitrary $g\ne -1$ or a square,
we arrive at (\ref{classicalhooley}) under HRH, which implies 
the truth of the
qualitative form of Artin's primivite root conjecture and a
modified form of the quantitative version.

\subsection{Unconditional results}
If one asks for unconditional results, the state of affairs is quite
appalling.  There is no known number $g$ for which ${\mathcal{P}}(g)$
is known to be infinite~!
In 1986, however, Heath-Brown \cite{HB} proved 
(improving on earlier fundamental work by Gupta and Ram Murty \cite{GM}) a result which implies 
that there are
at most two primes $q_1$ and $q_2$ for which ${\mathcal{P}}(q_1)$ and
${\mathcal{P}}(q_2)$ are finite and at most three squarefree numbers 
$s_1,s_2$ and $s_3$ for which ${\mathcal{P}}(s_1)$, ${\mathcal{P}}(s_2)$
and ${\mathcal{P}}(s_3)$ are finite.\\
\indent Remember the observation that if $q=4p+1$ and $p\equiv 2(\mod 5)$, then
$q\in {\mathcal{P}}(10)$.  Sieve theory cannot prove presently that there
are infinitely many such primes. 
However, the so called
lower bound sieve method combined with the Chen-Iwaniec switching method gave
rise to $\gg{x\over\log^2{x}}$ primes $p\leqq x$ such that either
$p-1=2^{e}q$ for some prime $q$ or $p-1=2^{e}q_1q_2$ with
$p^\alpha<q_1<p^\delta$ for some $\alpha>{1\over 4}$ and $\delta<{1\over
2}$.  This together with a rather elementary argument, is then enough to
establish Heath-Brown's result.\\
\indent Reznikov and Moree \cite{RM} established a variant of Heath-Brown's result
and used it to make considerable progress regarding a conjecture of Lubotzky and
Shalev to the extent that for all $d$ sufficiently large the number of subgroups
of index $d$ in the fundamental group $\pi_1(M)$ of a hyperbolic three manifold $M$ is at least 
$e^{dc(M)}$, for some positive constant $c(M)$ depending at most on $M$.

\section{Probabilistic model}
Let me consider the problem of finding a probabilistic model for a prime
$p$ to be such that $g$ is a primitive root mod $p$.  Herewith I mean
finding a simple function $f_g(p)$ (if it exists) such that
\begin{equation}
\label{model} 
\sum_{p\in S\atop p\leqq x}f_g(p)\sim
\sum_{p\in S,~p\leqq x\atop\hbox{
\scriptsize $g$ is a primitive root mod $p$}}1,
\end{equation} 
where $S$ has to be a set of primes having a natural density.\\
\indent  There are $\varphi(p-1)$
primitive roots mod $p$ and thus
one could try to take $f_g(p)={\varphi(p-1)/(p-1)}$ assuming
the primitive roots are
randomly distributed over
$1,\ldots,p-1$. 
Results of Elliott, Cobeli \& Zaharescu, Nongkynrih, Rudnick \& Zaharescu
indeed all suggest that the distribution
of the primitive roots over $1,\ldots,p-1$ is to a large extent governed by 
Poisson processes. Thus we would hope
to find something like 
\begin{equation}\label{sum(phi(p-1)over(p-1))}
\sum_{p\leqq x}{\varphi(p-1)\over p-1}\sim{\mathcal{P}}(g)(x),~~
x\rightarrow\infty.
\end{equation}
However, by Hooley's theorem there are, under HRH, $g_1$ and $g_2$ such that
${\mathcal{P}}(g_1)(x)\nsim{\mathcal{P}}(g_2)(x)$.  Thus
(\ref{sum(phi(p-1)over(p-1))}) cannot be true.  Let us not be scared by
this and try to evaluate $\sum_{p\leqq x}{\varphi(p-1)\over
p-1}$.  Note that ${\varphi(n)\over n}=\prod_{p\mid
n}(1-{1\over p})=\sum_{d\mid n}{\mu(d)\over d}.$ Thus 
$$
\sum_{p\leqq x}{\varphi(p-1)\over p-1}
=\sum_{p\leqq x}\sum_{d\mid (p-1)}{\mu(d)\over d}
=\sum_{d\leqq x}{\mu(d)\over d}\sum_{p\le x\atop p\equiv 1(d)}1
=\sum_{d\leqq x}{\mu(d)\over d}\pi(x,d,1).$$
Let $c_1$ be a fixed real number. Then the estimate
\begin{equation}
\label{siwa}
\pi(x,d,a):=\sum_{p\le x\atop p\equiv a({\rm mod~}d)}1
={{\rm Li}(x)\over \varphi(d)}
+O(xe^{-c_2\sqrt{\log x}})
\end{equation}
holds uniformly for all integers $a$ and $d$ such that
$(a,d)=1$ and $1\le d\le \log ^{c_1} x$, with $c_2$ some
positive constant. This is a well-known result due to Siegel
and Walfisz. On applying it we obtain
$$
\sum_{p\leqq x}{\varphi(p-1)\over p-1}
={\rm Li}(x)\sum_{d\leqq\log^{c_1} x}{\mu(d)\over d\varphi(d)}+
O\left({x\over \log^{c_1}x}\right)=A{\rm Li}(x)+
O\left({x\over \log^{c_1}x}\right).$$
\indent  Recall that Artin's heuristic answer was not always correct because he
failed to take into account quadratic interactions.  So let us try to
incorporate this into our model.  In order that $g$ is a primitive root mod
$p$ it is necessary that $(g/p)=-1$ and this is a quadratic
condition.  In particular if $g$ has to be a primitive root it must be a
non-square mod $p$.  There are ${p-1\over 2}$ of them and then
${2\varphi(p-1)/(p-1)}$ is the density.  Thus it makes sense to try to
evaluate the sum in the identity below, which yields, assuming HRH, 
by a computation a little more complicated than for the sum with
the condition $(g/p)=-1$ omitted: 
$$2\sum_{p\leqq x\atop\left(g\over p\right)=-1}{\varphi(p-1)\over p-1}
={\mathcal{P}}(g)(x)+O(R(x)).$$  

In case $h>1$ equality does not always hold.  The effect we have to take
into account there is that if $(p-1,h)>1$, then
$$g^{p-1\over(p-1,h)}\equiv
\left(g_0^{h\over(p-1,h)}\right)^{p-1}\equiv 1(\mod p)$$ and
thus $g$ cannot be a primitive root mod $p$.

Here is my proposal for $f_g(p)$.
\begin{equation}
\label{modelexplicit}
f_g(p)=\left\{
\begin{array}{cl}
{2{\varphi(p-1)\over p-1}} 
&\hbox{if $({q\over p})=-1$ and $(p-1,h)=1$;}\\
0 &\hbox{otherwise}
\end{array}\right.
\end{equation}
Then, it can be shown assuming HRH that
\begin{equation}
\label{mmodel}
\sum_{p\leqq x}f_g(p)={\mathcal{P}}(g)(x)
+O(R(x)).
\end{equation}  
To my amazement, this result appeared to be new.\\
\indent  The traditional approach
after the failure of the naive heuristic, is to show that it holds true on
average :
$${1\over N}\sum_{g\leqq N}{\mathcal{P}}(g)(x)
={1\over N}\sum_{p\leqq x}M_p(N),$$  
where $M_p(N)$ is the number of integers $g\leqq N$ which are primitive
roots modulo $p$.  Clearly $M_g(N)=\varphi(p-1)\{{N\over p}+O(1)\}$.  Thus
$${1\over N}\sum_{g\leqq N}{\mathcal{P}}(g)(x)
=\sum_{p\leqq x}{\varphi(p-1)\over p-1}
+O\left({x^2\over N\log x}\right)
+O\left({x\over \log^D x}\right),$$  
provided that $N>x^2\log^{D-1}{x}$.
Less trivial unconditional results in this direction were obtained by 
Goldfeld \cite{Goldfeld} and
Stephens \cite{Stephens}.

It turns out to be relatively easy to compute the first sum in
(\ref{model}) with $S=\{p:p\equiv a({\rm mod~}f)\}$ 
and one obtains a relatively complicated, but
completely explicit, Euler product.  The question is whether 
the true behaviour of ${\mathcal{P}}(g,f,a)(x):=\#\{p\leqq
x:p\in {\mathcal{P}}(g),~~p\equiv a(\mod f)\}$ matches up with this. 

Lenstra's work \cite{Lenstra}, which introduced Galois theory
into the subject, implies the following result on ${\mathcal{P}}(g,f,a)(x)$. 

\begin{theorem}
\label{lenstrarekenkundigerij}
Let $1\le a\le f,~(a,f)=1$. Let
$\sigma_a$ be the automorphism of $\mathbb Q(\zeta_f)$ determined by
$\sigma_a(\zeta_f)=\zeta_f^a$. Let $c_a(n)$ be $1$ if the restriction
of $\sigma_a$ to the field $\mathbb Q(\zeta_f)\cap \mathbb Q(\zeta_n,g^{1/n})$
is the identity and $c_a(n)=0$ otherwise. Put
$$\delta(a,f,g)=\sum_{n=1}^{\infty}{\mu(n)c_a(n)\over 
[\mathbb Q(\zeta_f,\zeta_n,g^{1/n}):\mathbb Q]}.$$
Then, assuming RH for all 
number fields $\Q(\zeta_f,\zeta_n,g^{1/n})$ with
$n$ squarefree,
$${\mathcal{P}}(g,f,a)(x)=\delta(a,f,g){x\over \log x}+
O(R(x)).$$
\end{theorem}
 

Inspired by the relatively easy Euler product coming from quadratic
heuristics, I set out to explicitely evaluate $\delta(a,f,g)$
and managed to find an Euler product for
it.  This is the same as the one found with quadratic heuristics ! 
As a consequence we have the following result \cite{MoreeAP}, which
generalizes (\ref{mmodel}):
\begin{theorem}\label{thm:sum(f_g(p))}
Assume RH for all number fields $\Q(\zeta_f,\zeta_n,g^{1/n})$ with $n$
squarefree. 
Then
$$\sum_{p\leqq x\atop p\equiv a(\mod f)}f_g(p)
={\mathcal{P}}(g,f,a)(x)+O(R(x)).$$
\end{theorem}
A rather
more insightful derivation of the Euler product
for $\delta(a,f,g)$ will appear in
\cite{LMS}, as a consequence of a more explicit approach 
involving quadratic characters in the line
of Lenstra's earlier work. This approach is the most powerful sofar
in finding explicit Euler products for primitive root densities. For a preview of this work
see Stevenhagen \cite{Steven}. The upshot is that the density for a whole
class of Artin type problems can be always written as
$$\delta=(1+\prod_p E_p)\prod_p A_p,$$\\
where the $E_p$ are (real)character averages and hence satisfy $-1\le E_p\le 1$. Only finitely
many of them are distinct from 1. The infinite product $\prod_p A_p$ can be regarded as the
`canonical' density of the problem at hand. In this formulation the situations where $\delta=0$
can be relatively easily computed (from the expression of the density
as an infinite sum this can be quite hard, cf. the formula for
$\delta(a,f,g)$ in Theorem \ref{lenstrarekenkundigerij}). For the original Artin problem a very easy computation
yields $\prod_p A_p=A(h)$ and $1+\prod_p E_p=E$ and one finds (\ref{expli}) again.\\
\indent The explicit formula for $\delta(a,f,g)$ allows one to determine the $f$
such that the primes in ${\mathcal{P}}(g)$ are equidistributed in the
various primitive residue classes mod $f$. This was done earlier by me
\cite{Moree3} using an Euler product for $\delta(1,f,g)$ (which
is easier to obtain) and some Galois theoretic arguments.
Basically $f$ must be a power of two, in case $h=1$.  Also $2^\alpha3^\beta$
can occur, the smallest integer instance being $g=21^7$. These results imply the falsity of
a conjecture of Rodier \cite{Rodier}, under the usual RH proviso.\\
\indent 
If $S$ is a union of arithmetic progressions, then
assuming a sufficiently strong generalisation of RH, it follows
by Theorem \ref{thm:sum(f_g(p))} that equality 
holds
with $f_g(p)$ chosen as in (\ref{modelexplicit}). 
This choice of $f_g(p)$ does not always work for arbitrary sets $S$ having
a natural density, for example when one chooses $S$ to be the 
set of primes that split
completely in $\Q(\zeta_3,g^{1/3})$, in case $g$ is not a cube.

\section{The indicator function}
\subsection{The indicator function and probabilistic models}
Let $G$ be a finite cyclic group and put $f(g)=1$ if
$G$ is generated by $g$ and $f(g)=0$ otherwise. It was already
observed by Landau that
\begin{equation}
\label{indicator}
f(g)={\varphi(n)\over n}\sum_{d|n}{\mu(d)\over \varphi(d)}
\sum_{{\rm ord}\chi=d}\chi(g),
\end{equation}
where the sum is over the characters $\chi$ of $G$ having order $d$.
Using this, one deduces that
$$
{\mathcal{P}}(g)(x)=\sum_{p\le x}{\varphi(p-1)\over p-1}\sum_{d|p-1}
{\mu(d)\over \varphi(d)}\sum_{{\rm ord}\chi=d}\chi(g).$$
Now write ${\mathcal{P}}(g)(x)=\sum_{d\le x}S_d(x)$.
Note that
$$S_1(x)=\sum_{p\le x}{\varphi(p-1)\over p-1}$$
and that
$$S_2(x)=-({g\over p})\sum_{p\le x}{\varphi(p-1)\over p-1}.$$
The term
$S_d(x)$ can be written as a linear combination of terms
$${1\over \pi(x)}
\sum_{p\le x,~p\equiv 1({\rm mod~}d)\atop p\equiv 1({\rm mod~}\delta)}
\left({g\over p}\right)_d,$$
where $({g\over p})_d$ denotes the $d$-th power residue symbol, cf.
\cite[p. 111]{Lemmermeyer}.
In case $g$ is squarefree these terms
disappear for every $d>2$ and $\delta$.
Hence we expect that
$${\mathcal{P}}(g)(x)\sim (S_1(x)+S_2(x))\sim 2\sum_{p\le x\atop 
({g\over p})=-1}
{\varphi(p-1)\over p-1},~~x\rightarrow\infty.$$
A slightly more complicated argument leads to the conjecture
$${\mathcal{P}}(g)(x)\sim 2\sum_{p\le x,~(p-1,h)=1\atop ({g\over p})=-1}
{\varphi(p-1)\over p-1},~~x\rightarrow\infty,$$
where $g$ is not required to be squarefree.
The problem in proving this (and hence a quantitative Artin's primitive
root conjecture) is that we have `too many error terms' and can only
achieve this if it can be established that there is sufficient cancellation,
which is out of reach presently.\\
\indent The analog of the latter conjecture for the general index $t$ case
(cf. \S \ref{sectionvaria}) is far from easy to infer 
by ad hoc methods (as we
managed to do for $t=1$ in the previous section), but can be
merely computed using the approach sketched here. Furthermore, under the
usual RH proviso this conjecture can then be shown to be true
\cite[Theorem 1]{MoreeNP}.\\
\indent The unconditional results on Artin's conjecture on average
in \cite{Goldfeld, Stephens} where obtained on using the indicator
function and estimates for character sums.
\subsection{The indicator function in the function field setting}
\indent We now give another application of the identity (\ref{indicator}).
Let $\F_q$ be the finite field with $q=p^n$ elements. 
Recall that its multiplicative group is cyclic.
Let $a(x)$ be 
a polynomial in the polynomial ring $\F_p[x]$. We are interested in the
number of irreducible polynomials $p(x)\in \F_p[x]$ such that
$a(x)$ generates $(\F_p[x]/(p(x))^*$. Recall that if deg$p(x)=n$ then
$\F_p[x]/(p(x))$ is isomorphic with
$\F_{p^n}$, where the isomorphism is given
explicitly as follows: for $h(x)\in \F_p[x]$, we write, using the
Euclidean algorithm,
$$h(x)=p(x)q(x)+r(x),~{\rm with~either~}r(x)=0{\rm ~or~}0\le {\rm deg}r
<{\rm deg}p=n.$$
Let $\rho\in \F_{p^n}$ be a root of $p(x)$. Then
$$h(\rho)=r(\rho)=a_0+a_1\rho+\cdots+a_{n-1}\rho^{n-1},~a_i\in \F_p$$
describes all the elements of $\F_{p^n}$. Thus, $a(x)$ generating
$(\F_p[x]/(p(x)))^*$ is equivalent to $a(\rho)$ generating
$\F^*_{p^n}$.\\
\indent Hence, to count the number of irreducible $p(x)$ of degree $n$ 
for which $a(x)$ is a generator is tantamount to counting the number
of $\rho$ of degree $n$ for which $a(\rho)$ generates $\F^*_{p^n}$.
Indeed, since each $p(x)$ has $n$ roots, we find that the number of
irreducible polynomials of degree $n$ in $\F_p[x]$ such that $a(x)$
generates $(\F_p[x]/(p(x)))^*$  is equal to the number of elements
$\rho\in \F_{p^n}$ of degree $n$ such that $a(\rho)$ generates
$\F^*_{p^n}$ divided by $n$. The latter number, is on using
(\ref{indicator}), equal to
$${1\over n}\sum_{\rho\in {\mathbb F}_{p^n}\atop {\rm deg}\rho=n}
{\varphi(p^n-1)\over p^n-1}\sum_{d|p^n-1}{\mu(d)\over \varphi(d)}
\sum_{{\rm ord}\chi=d}\chi(a(\rho)).$$
By inclusion-exclusion we find that the number of irreducible polynomials
of degree $n$ over $\F_q[x]$ equals
$${1\over n}\sum_{\rho\in {\mathbb F}_{p^n}\atop {\rm deg}\rho=n}1
={1\over n}\sum_{d|n}\mu(d)p^{n\over d}={p^n\over n}+
O\left({p^{n\over 2}\over n}\right).$$
(It is not difficult to show \cite[Lemma 3]{Monumi} that $\sum_{d|n}\mu(d)t^{n/d}>0$ for
every $t>1$ and hence that at least one irreducible polynomial of degree
$n$ over $\F_q[x]$ exists.)
Thus the contribution from the main term (the term with $d=1$) is
$${p^n+O(p^{n\over 2})\over n}{\varphi(p^n-1)\over p^n-1},$$
and the error term is
$${\varphi(p^n-1)\over n(p^n-1)}
\sum_{d|p^n-1\atop d>1}{\mu(d)\over \varphi(d)}
\sum_{{\rm ord}\chi=d}\sum_{\rho\in {\mathbb F}_{p^n}\atop {\rm deg}\rho=n}
\chi(a(\rho)).$$
On applying Weil's estimate for character sums and imposing
the appropriate conditions on $a(x)$, the truth of Artin's conjecture in this
situation is then established, cf. \cite{PS}.\\
\indent A little knowledge of the history of Weil's estimate makes clear
that we not always need to invoke this powerful and deep result. Weil,
in a period when he felt depressed, turned to the works of Gauss and 
started reading hapazardly. He soon found himself awestruck by
Gauss' approach in counting solutions mod $p$ of homogenous equations
of the form $x_0^m+\cdots+x_s^m$. This approach involves Gauss sums (and
Jacobi sums). Weil then started musing about generalisations of this
beautiful work and the rest is mathematical history.... 
Thus we would expect that in case 
$a(x)=x^m+c$ the required estimate for the error term can be obtained on
using only Gauss sums over finite fields.
This is indeed so, see \cite{Jensen}.\\
\indent The situation described here is a particular case of the
Artin primitive root conjecture for function fields. Hasse, who
was at the cradle of Artin's conjecture (Artin first formulated it in 
a discussion with Hasse), kept very interested in it throughout
his life and tried to stimulate people to work on it, cf.
\cite{Hasse}. One of
them was his PhD student Bilharz \cite{Bilharz},
 who in 1937 proved
Artin's conjecture for function fields  under the proviso that the RH for the zeta function
corresponding to the function field would hold true. Indeed, much
later this was proved by Weil and
hence Artin's primitive root conjecture is true for function fields !
Bilharz result has been subsequently generalized by 
Hsu \cite{Hsu} to Carlitz
modules (a particular case of 
Drinfeld modules of rank one). Rosen \cite{Rosen} in his well-written book  devotes
a whole chapter to Artin's primitive root conjecture in the function field setting.



\section{Some variations of Artin's problem}


\subsection{Elliptic Artin}

\noindent An excellent introduction to elliptic Artin can be found
in \cite{Murty} and we quote it here almost verbatim. For references
we refer to that paper.\\
\indent In 1976 Lang and Trotter \cite{LangTrotter} formulated elliptic 
analogues of the Artin
primitive root conjecture.  Suppose $E$ is an elliptic curve over $\Q$ with a rational point of infinite order.  A natural question is : How
often does the prescribed point generate $E(\F_p)$, the group of
points $(\mod p)$ ?

More precisely, let $a$ be a rational point of infinite order.  The problem
is to determine the density of primes $p$ for which $E(\F_p)$ is
generated by $\bar{a}$, the reduction of $a(\mod p)$.  (Here in addition to
primes of bad reduction, we may need to exclude primes dividing the
denominators of the coordintes of $a$.)  Such a point will be called a
primitive point for these primes.  Lang and Trotter conjectured that the
density of primes for which $a$ is a primitive point always exists.  This
is the elliptic analogue of Artin's primitive roots conjecture.

Of course, situations may (and do) arise when the density is zero.  In such a
case the set of primes for which $a$ is a primitive point is finite (and
often empty).  If this is the case, then it is so for obvious reasons.  So
the statement is that if it is not the case for obvious reasons that there
are only finitely many, then there are infinitely many and they have a
density.  

In considering the elliptic analogue, we see that two assertions are being
made about a prime $p$ for which $a$ is a primitive point :\\ 
1) $E(\F_p)$ is cyclic.\\
2) $\langle \bar a \rangle \cong E(\F_p)$,\\
where with $\langle \bar a \rangle$ we denote the subgroup in $E(\F_p)$ generated by
the reduction mod $p$ of the point $a$.
Is it even true that $E(\F_p)$ is cyclic infintely often ? It was Serre who pointed out the relevance of this question.  In a course
at Harvard in the fall of 1976, he proved that Hooley's method can be
adapted to show that the set of primes $p$ with $E(\F_p)$ cyclic
is $$\delta_E{x\over\log x}+O\left({x\over\log x}\right),{\rm ~where~}\delta_E=\sum_{k=1}^\infty{\mu(k)\over[\Q(E[k]):\Q]}.$$
Here $\Q(E[k])$ is the number field obtained by adjunction of the
coordinates of the $k$-division points of the elliptic curve $E$. It
is the analogue of the Kummerian extension $\Q(\zeta_k,g^{1/k})$.
As noted by Serre, $\delta_E>0$ if
and only if $E$ has an irrational 2-division
point.  That is, if $E$ has the Weierstrauss model, $y^2=x^3+cx+d$, we
require that $x^3+cx+d$ has an irrational root.  In the non-CM case, it is
still unknown if $E(\F_p)$ is cyclic for a positive density of
primes whenever $E$ has an irrational 2-division point.\\
\indent Some very recent work on the elliptic Artin conjecture is due to Alina Cojocaru. 

\subsection{Even order} 

\label{subsectioneven}
\noindent Let $g\ge 2$ be an integer. As we saw in the introduction the question whether ord$_p(g)=p-1$ for
a prime $p$, is equivalent with the period of the decimal expansion of
$1/p$ in base $g$ being maximal. Krishnamurty wondered how often the
period in these decimal expansions are even. This can be attacked
by algebraic methods similar to those sketched above.\\
\indent We say that a prime $p$ {\it divides a sequence} of integers, if it
divides at least one term of the sequence.
 Notice
that
$${\rm ord}_p(g)~{\rm is~even}\iff g^x\equiv -1({\rm mod~}p)
~{\rm has~a~solution}\iff p|\{g^k+1\}_{k=0}^{\infty}.$$
There is an unique $j\ge 1$ such that
$p\equiv 1+2^j ({\rm mod~}2^{j+1})$. Now ord$_g(p)$ is even
if and only if
$$g^{p-1\over 2^j}\not\equiv 1({\rm mod~}p).$$
It is more natural to consider the $g$ such that
ord$_g(p)$ is odd, that is the set
$\{p:2\nmid {\rm ord}_g(p)\}$. Let
$$P_j=\{p:p\equiv 1+2^j ({\rm mod~}2^{j+1}),~2\nmid {\rm ord}_g(p)
\}.$$
Note that
$$P_j=\{p:p\equiv 1+2^j ({\rm mod~}2^{j+1}),
~g^{p-1\over 2^j}\equiv 1({\rm mod~}p)\}.$$
Now $P_j$ consists of the primes $p$ that split completely
in $\mathbb Q(g^{1/2^j},\zeta_{2^j})$, but do not split completely
in $\mathbb Q(g^{1/2^j},\zeta_{2^{j+1}})$. Since
$\{p:~2\nmid {\rm ord}_g(p)\}=\cup_{j=1}^{\infty}P_j$, and
the $P_j$ are disjoint, one expects that the natural
density of the set
$\{p:~2\nmid {\rm ord}_g(p)\})$ equals $\sum_{j=1}^{\infty}
\delta(P_j)$, where $\delta(P_j)=\lim_{x\rightarrow \infty}
P_j(x)/\pi(x)$.
Now
$$\sum_{j=1}^{\infty}\delta(P_j)=\sum_{j=1}^{\infty}\left(
{1\over [\Q(g^{1/2^j},\zeta_{2^j}):\Q]}
-{1\over [\Q(a^{1/2^j},\zeta_{2^{j+1}}):\Q]}\right).$$
On taking $g=2$ one expects, on
computing the field degrees involved, that the density of prime divisors
of the sequence $\{2^k+1\}_{k=0}^{\infty}$ equals
$$\delta=({1\over 2}-{1\over 4})+({1\over 8}-{1\over 8})
+\sum_{j\ge 3}({4\over 4^j}-{2\over 4^j})={7\over 24}.$$
With natural density replaced by Dirichlet density, this
result was proved by Hasse in 1966.
The natural density of primitive divisors of sequences of the form $\{a^k+b^k\}_{k=1}^{\infty}$ with 
$a$ and
$b$ integers was computed independently along similar lines
by Ballot, Odoni and Wiertelak, see e.g. \cite{Ballot}.
For the  a sequence $\{a^k+b^k\}_{k=1}^{\infty}$ with $a$ and $b$ canonical, the density is
$2/3$. In particular, if $g=10$ one finds that the primes $p$ such that period of the decimal expansion of $1/p$ is
even have density $2/3$.\\
\indent Note that this result, unlike Hooley's, is unconditional.
Both involve infinite towers of field extensions, but the one appearing
in this problem is so sparse (in the sense that the degrees of the
fields quickly increase) that the profusion of error terms that
occurs in the Artin primitive root conjecture, does not arise and
one can afford working with the relatively large error terms 
in $\pi_K(x)$ that are conditionally known. A probabilistic model for ord$_p(g)$ to be
even was found by Moree \cite{Model}.\\
\indent Instead for asking when $2|{\rm ord}_p(g)$, one can ask
for $m|{\rm ord}_p(g)$ or for $(m,{\rm ord}_p(g))=1$ etc.. These
questions, with sharp error terms, are dealt with in various papers
of Wiertelak, see \cite{Modelerd} for references. Again it turns out the corresponding density exists and
is a rational number. Wiertelak gave a complicated expression for this
density in case of the `$m|{\rm ord}_p(g)$' problem, that was substantially simplified by 
Pappalardi \cite{Pappa}. Pappalardi's
expression was simplified by Moree \cite{Modelerd}, who based himself
on a simple to prove, apparently unknown before, identity for the associated counting
function (\cite[Proposition 1]{Modelerd}).

\subsection{Order in a prescribed arithmetic progression}
The problem of determining for how many primes $p\le x$ one has ord$_p(g)\equiv a({\rm mod~}d)$, with
$a$ and $d$ prescribed integers was first considered by Chinen and Murata \cite{CM} in case $d=4$.
In this generality the problem turns out to be much harder than the case where $d|a$.
Under an appropriate generalization of RH it turns out that $\delta_g(a,d)$, the density of primes $p\le x$ such
that  ord$_p(g)\equiv a({\rm mod~}d)$, exists \cite[Part II]{Moreejapi1}. Let $N_g(a,d)(x)$ be
the associated counting function.
The latter proof starts with noting the identity
$$N_g(a,d)(x)=\sum_{t=1}^{\infty}\#\{p\le x:r_g(p)=t,~p\equiv 1+ta({\rm mod~}dt)\},$$
where $r_g(p)=(p-1)/{\rm ord}_g(p)$ denotes the residual index. The individual terms
can be dealt with a variation of Hooley's method, where now one also needs to keep track
of the dependence on $t$. The more novel aspects of the work rest in making the
resulting formula for $\delta_g(a,d)$ more explicit, which requires algebraic number theory.\\
\indent The much simpler quantity 
$\delta(a,d)$, the average density of elements of order $\equiv a({\rm mod~}d)$ in a field of prime
characteristic also exists \cite{Mofield}. It turns out that under the latter RH variant for almost
all $g$ with $|g|\le x$ one has $\delta_g(a,d)=\delta(a,d)$. Moreover, if $\delta_g(a,d)\ne \delta(a,d)$, then
they tend to be close. Nevertheless, it is possible to find specific $g$ (usually appropriately chosen
high powers of a small basis number), for which $\delta_g(a,d)$ shows highly 
non-canonical behaviour. Despite
the subtle arithmetic behaviour of $\delta_g(a,d)$, there are some surprises. For example, if $g>0$ then
always $\delta_g(1,4)\le \delta_g(3,4)$. My experience that a rational density in an Artin type problem
indicates that the associated tower of field extension is rather sparse, seems to be invalid in this
context.\\
\indent The analogous problem of determining for how many primes $p\le x$ the residual index is in
a prescribed congruence class modulo $d$ was first studied by Pappalardi \cite{Pappa-1}. This turns
out to be a much easier problem and thus it is perhaps a bit surprising that the results obtained
have a rather similar format.
   

\subsection{Divisors of second order recurrences}

\noindent The sequences  $\{a^k+b^k\}_{k=1}^{\infty}$ are special cases of
sequences satisfying a second order linear recurrence and one can
wonder about prime divisors of such recurrences in general, cf. \cite{Ballot}. 
A general linear second
order recurrence has the form $u_{n+2}=cu_{n+1}+du_n$. Once the values
of $u_0$ and $u_1$ are given, it is uniquely determined. The
{\it characteristic polynomial} associated to the recurrence is
defined as $X^2-cX-d$. If this polynomial is reducible over $\Q$,
then the recurrence has the form $R=\{ca^k-db^k\}_{k=0}^{\infty}$, finding
the prime divisors amounts to finding the prime divisors of the sequence
with general term
$(a/b)^k-d/c=\alpha^k-\beta$. Now $p$ is a prime divisor of $R$, with
at most finitely many exceptions, if and only if
ord$_p(\beta)|{\rm ord}_p(\alpha)$. 
This can be phrased differently by saying that, with at most finitely
many exceptions, $p$ divides $R$ if and only if the subgroup mod $p$
generated by $\beta$, $\langle \beta \rangle$, is contained in the
subgroup $\langle \alpha \rangle$. One can then base a two variable
Artin conjecture on this, of which the qualitative form says that the
sequence $R$ should have infinitely many prime divisors. This form
is not too difficult to prove, as was done by P\'olya around 1920,
cf. \cite{MS}. To investigate the quantitative form, we put
$S(x)=\sum_{p\le x,~p|R}1$.
Then
$$S(x)=\sum_{p\le x}\sum_{w|p-1\atop
{\rm ord}_p(\beta)|{\rm ord}_p(\alpha)=(p-1)/w}1
=\sum_{w\le x-1}\sum_{{p\le x\atop p\equiv 1({\rm mod~}w)}
\atop {\rm ord}_p(\beta)|{\rm ord}_p(\alpha)=(p-1)/w}1.$$
Now $p\equiv 1({\rm mod~}w)$ and
ord$_p(\beta)|{\rm ord}_p(\alpha)=(p-1)/w$ if and only if 
$p$ splits completely in
$\mathbb Q(\alpha^{1/w},\beta^{1/w},\zeta_w)$
and $p$ does not split completely in any of the fields
$\mathbb Q(\alpha^{1/qw},\beta^{1/w},\zeta_{qw})$, with $q$ a prime.
Denote the degree of the latter field by $n(qw)$. Then,
as $x\rightarrow \infty$, the limit $S(x)/\pi(x)$ tends
to
\begin{equation}
\label{Stephensdouble}
\sum_{w=1}^{\infty}\sum_{k=1}^{\infty}
{\mu(k)\over n(kw)},
\end{equation}
provided a sufficiently
strong generalisation of RH is true. The sum 
(\ref{Stephensdouble}) equals a rational number times
the {\it Stephens constant}
$$S=\prod_p\left(1-{p\over p^3-1}\right)\approx 0.57595 99688 929\cdots $$
(The Stephens constant can also be evaluated with high numerical precision by
expressing in terms of zetavalues at integer arguments \cite{Monumi}.)
This result is due to Moree and Stevenhagen \cite{MS}
and improves on earlier work by Stephens \cite{Stephens3}. 
Stephens evaluation of (\ref{Stephensdouble})
(who restricted himself to the case where both $\alpha$ and $\beta$ are integers) is not always correct
and corrected in \cite{MS}.\\
\indent Note that the problem considered here
is a variant of Artin's primitive root conjecture that is more
complicated than the original one, whereas the variant discussed
in \S \ref{subsectioneven} is easier, although both deal with second order recurrences. 
Lagarias made a similiar experience: in \cite{Laga} he showed that the set of primes dividing some 
Lucas number $L_n$ (defined by $L_0 = 2$, $L_1 = 1$ and $L_{n+1} = L_n + L_{n-1}$) has natural density $2/3$, and 
remarked that his method does not work for the sequence $a_n$ defined by $a_0 = 3$, $a_1 = 1$ and $a_{n+1} = a_n + a_{n-1}$. 
Moree and Stevenhagen \cite{mos} showed that under an appropiate generalisation of
RH  this density equals 
$${1573727\over 1569610}S\approx 0.577470679956\ldots$$\\
\indent Much more material on recurrences can be found in the book \cite{recur}.

\subsection{Lenstra's work}
\noindent The
most far reaching generalisation of
the Artin primitive root conjecture was
considered by Lenstra \cite{Lenstra}, in the
context of his research on Euclidean number
fields : 
Let $K$ be a global field and $F$ a finite normal extension of $K$.  Let
$C$ be a subset of Gal$(F/K)$ which is stable under conjugation and let
$d$ be a positive integer (coprime to the characteristic of $K$ in the case
of a function field).  Consider a finitely generated subgroup $W$ of $K^*$
which has, modulo torsion, rank $r\geqq 1$, and let $M$ be the set of
prime ideals $\mathfrak P$ of $K$ satisfying
\begin{enumerate}
\item the Artin symbol $({\mathfrak P},F/K)\subseteq C$
\item the normalized exponential valuation attached to $\mathfrak P$ satisfies
ord$_{\mathfrak P}(w)=0$ for all $w\in W$.
\item if $\psi:W\to {\bar K}_{\mathfrak P}^*$ is the natural map, then
the index of $\psi(W)$ in ${\bar K}_{\mathfrak P}^*$ divides $d$.
\end{enumerate}
Here ${\bar K}_{\mathfrak P}^*$ denotes the multiplicative group of
${\bar K}_{\mathfrak P}$, the residue class field at $\mathfrak P$.
Lenstra conjectured that $M$ has a density.  He also obtained
necessary and sufficient conditions for this density to be nonzero, under
a sufficiently strong generalisation of RH. His main result implies
Theorem \ref{lenstrarekenkundigerij} for example. Lenstra applied it
to show, under the usual
RH proviso, that certain principal ideal rings are euclidean.

\subsection{Varia}
\label{sectionvaria}
\noindent We mention some other related results without delving deeply into the mathematics involved.\\
\noindent {\bf 1}) {\it How many primes $p$ are there are such that $p-1$ is squarefree ?}
There are two lines of attack.
One is \`a la Artin's primitive root conjecture.
In this approach one notes that $p-1$ is squarefree if and only if $p$
does not split completely in any of the
cyclotomic fields $\mathbb Q(\zeta_{q^2})$, where $q$ runs over all primes.
By inclusion-exclusion this gives then the conjectural
natural density
$\delta=\sum_{n=1}^{\infty}\mu(n)/[\mathbb Q(\zeta_{n^2}):\mathbb Q]$. The latter sum is easily seen to equal $A$.
An approach to this problem in this spirit was
made by H.-W. Knobloch \cite{knoflook, Hasse}, a student of Hasse. It turns out, however, that
a quite elementary proof is possible. It was found by Mirsky \cite{Mirsky}. This uses the trivial identity
$\sum_{d^2|n}\mu(d)=1$ if $n$ is not squarefree and zero otherwise.
Note that the number of primes $p\le x$ such
that $p-1$ is squarefree equals
$\sum_{p\le x}\sum_{a^2|p-1}\mu(a)$. Now swap the order of summation.
The inner sum is a prime counting sum and can be estimated by the
Siegel-Walfisz theorem (\ref{siwa}) for $a$ small enough. The contribution from all large $a$ we
can trivially estimate. Carrying out this procedure gives us the
same sum for the density $\delta$ as found in the earlier approach.  
(Mirsky gives the details of another proof and then for the relevant
 one for our purposes says it can be done similarly. This is worked
 out, however, in more detail in e.g. 
 Moree and Hommersom \cite[pp. 17--20]{Huib}.)
For more information see also the September 2004 entries of the NMBRTHRY archives.\\
{\bf 2}) Note that $g$ is a primitive root mod $p$ if the subgroup generated
by $\bar g$, the reduction of $g$ mod $p$, equals $(\Z/p\Z)^*$.
If $g_1,\cdots,g_r$ are rational numbers, one can wonder about
the density of primes $p\le x$ such that
$\langle {\bar g_1},\cdots,{\bar g_r} \rangle$ is the full multiplicative
group $(\Z/p\Z)^*$, see e.g. \cite{Cangelmi}, or about the density
such that each $g_i$, $1\le i\le r$, is a primitive root \cite{Matthews}.
In this direction Pappalari \cite{Paplepel} studied a conjecture of Brown
and Zassenhaus to the extent that if $p_1,\cdots,p_r$ denote the first $r$ primes, 
then for all but $o(\pi(x))$ primes $p\le x$, $\langle {\bar p_1},\cdots,{\bar p_r} \rangle$ 
is isomorphic to $(\Z/p\Z)^*$ if $r=[\log p]$. Pappalardi showed that under the usual
RH proviso the Brown-Zassenhaus conjecture holds true.\\
{\bf 3}) Fix an integer $t$. For the primes $p\equiv 1({\rm mod~}t)$ we
can ask for the subset of them such that $\langle \bar g \rangle$ generates a
subgroup of index $t$ in $(\Z/p\Z)^*$, see \cite{MoreeNP} and
the references given there.\\
{\bf 4}) The definition of primitive roots was extended by
Carmichael to
that of {\it primitive $\lambda$-roots} for composite moduli $n$, which
are integers with the maximal order modulo $n$. Let $N_g(x)$ be the
number of natural numbers up to $x$ for which $g$ is a primitive
$\lambda$-root. One might wonder then, in
analogy with Artin's conjecture, whether $N_g(x)\sim B(g)x$
for some positive constant $B(g)$ depending on $g$, perhaps with
some exceptional values of $g$. Li \cite{Li}
provides results suggesting that $N_g(x)/x$
does not typically tend to a limit, see also \cite{LiP, LiP2} for further results.\\
{\bf 5}) Pappalardi \cite{Pappa} studied the problem of determining how many primes
$p\le x$ there are such that ord$_p(g)$ is squarefree (and similarly ord$_m(g)$, where
$m$ ranges over the integers $\le x$ for which the latter order is defined).\\ 
{\bf 6}) Recall that $g$ is a primitive root mod $p$ if $p$ does not
split completely in any of the fields $k_q$. Goldstein considered
the more general problem where the fields $k_q$ are replaced by normal
number fields $L_q$ and made a conjecture which was
subsequently disproved by Weinberger. Goldstein then
proved a restrictive version of
his conjecture, which
result was improved upon by Ram Murty \cite{MurtyGoldstein}.\\
{\bf 7}) Brizolis conjectured that for every prime $p>3$ there exists an $x$ and a primitive root
 $g({\rm mod~}p)$ such that $x\equiv g^x({\rm mod~}p)$. Let $N(p)$ denote the number of $1\le x\le p-1$ such that $x$ is a 
 primitive root mod $p$ and $x$ and $p-1$ are coprime. It is easy to see that if $N(p)\ge 1$, then Brizolis' conjecture is 
 true for the prime $p$. Let $\omega(n)$ denote the number of distinct prime divisors of $n$ and 
 $d(n)$ the number of divisors of $n$. Cobeli and Zaharescu and, independently Wen Peng Zhang, using character sums and 
 the Weil bounds, proved that 
 $$N(p)={\varphi(p-1)^2\over p-1}+O(\sqrt{p}~ 4^{\omega(p-1)}\log p),$$ and used this to show that 
 Brizolis' conjecture is true for every prime $p>10^{50}$. Apparently the full Brizolis conjecture was recently
 settled by M. Campbell and C. Pomerance \cite{pommie}. Note that if $x\equiv g^x({\rm mod~}p)$, 
 then $x$ is 1-cycle under taking the discrete logarithm with respect to $g$. For small $k$, $k$-cycles of the
 discrete logarithm problem are studied in Holden and Moree \cite{HM1, HM2}.\\
{\bf 8}) Erd\H{o}s conjectured that there are infinitely many integers $n$ such that
$\Omega(n)=\Omega(n+1)$, where $\Omega(n)$ denotes the total number of prime divisors of $n$ and
a similar result for $\omega(n)$. The former conjecture was 
proved in 1984 by Heath-Brown, but the latter remains open. 
J. Kan \cite{Kan} proved the intriguing result that it cannot be true that both the latter
conjecture and the qualitative
form of Artin's primitive conjecture are false.\\
{\bf 9}) Over arbitrary number fields, there are two obvious ways in which Artin's conjecture can be generalized. Fix a number 
field $K$ with ring of integers ${\mathcal{O}}_K$, and a nonzero element $\alpha\in 
{\mathcal{O}}_K$, which is not a root of unity. 
We expect the following generalization to hold: the set of 
primes $\mathfrak p$ of $K$ for which $\alpha$ generates the cyclic group $(\mathcal{O}_K/\mathfrak{p}\mathcal{O}_K)^*$ has a density 
inside the set of all primes of $K$. Moreover, the situation is highly similar to the rational case, as the set of 
primes $\mathfrak p$ of $K$ for which $(\mathcal{O}_K/\mathfrak p\mathcal{O}_K)^*$ is isomorphic to 
$(\mathbb Z/p\mathbb Z)^*$ has density 1. In 1975 Cooke and Weinberger 
proved that this generalization of 
Artin's conjecture is indeed true and the density is given by the 
infinite sum in (\ref{classicalhooley}) with $\mathbb Q$ replaced by $K$, 
if an appropriate generalization of RH holds.\\
\indent Roskam \cite{Ros2} considers a generalization of Artin's conjecture in a "rational" direction: the set of rational 
primes $p$ for which the order of $\alpha$ in $(\mathcal{O}_K/\mathfrak p\mathcal{O}_K)^*$ is equal to the exponent of 
this group has a 
density inside the set of all rational primes. He proves that, assuming an appriopiate generalization of RH 
is true, this conjecture holds for quadratic fields $K$. A less general result in this direction he established
in \cite{Ros1} (but with a rather easier proof). Kitaoka and various of his pupils are very 
presently very actively working on Artin's conjecture for units (rather than
general elements) in number fields, cf. \cite{kit}.\\
{\bf 10}) Let $A$ be a hyperbolic matrix in SL$_2(\mathbb Z)$, that is a matrix with absolute trace greater 
than 2. We may define ord$_n(A)$ to be the order of $A$ in ${\rm SL}_{2}(\mathbb Z/n\mathbb Z)$. It can be shown
that for a hyperbolic matrix in SL$(2,\mathbb Z)$ there is a density-one sequence of integers $n$ such that
its order mod $n$ is slightly larger than $\sqrt{n}$. This is a crucial ingredient in an ergodicity theorem 
regarding eigenstates of quantized linear maps $A$ of the torus (`cat maps'), see Kurlberg and Rudnick 
\cite{KR}. Under an appropriate generalisation of RH it can be shown \cite{K1} that for almost all $n$ we have
ord$_n(A)\gg n^{1-\epsilon}$ for any $\epsilon>0$. Since the eigenvalues of $A$ are units in a quadratic number
field, this problem is closely related to that discussed under part IX.\\
{\bf 11)} R. Griffin (a mathematical amateur) thought in 1957 that the decimal expansions of $1/p$ should have
period length $p-1$ for all primes of the form $10X^2+7$. The first 16 primes $p$ of the form $10X^2+7$ have
indeed decimal period $p-1$, but this is not true for $p=7297$, the 17th such prime. D. Lehmer found in 1963 that
326 is a primitive root for the first 206 primes of the form $326X^2+3$. More impressive examples in the
same spirit can be given using recent results on prime producing quadratics. Y. Gallot holds the current
record in which 206 is being replaced by 31082. For more information on this topic see Moree \cite{Moreegriffin}.\\
{\bf 12}) Interest in prime divisors of binomial coefficients dates back at least
to Chebyshev. It is not difficult to see that unless $k$ is fairly close to one of the ends of the 
range $0\le k\le n$, then the coefficient ${n\choose k}$ contains many prime factors and many of these occur with 
high multiplicity. Erd\H{o}s made a number of conjectures quantifying these observations, one well-known conjecture being 
that the middle coefficient ${2n\choose n}$ is not squarefree for any $n>4$. Granville and Ramar\'e
proved this conjecture in 1996. The corresponding problem for
$q$-binomial and, more generally, $q$-multinomial  coefficients is much more complicated. Sander \cite{Sander} 
showed how Artin's primtive root conjecture implies the respective results.\\
{\bf 13)} Let $q$ be the order of a finite field. If $(n,q)=1$, then it can be shown that $X^n-1$ factors into
$$i_q(n)=\sum_{d|n}{\varphi(d)\over {\rm ord}_q(d)}$$
distinct irreducible factors over $\mathbb F_q$. The quantity $i_q(n)$ appears in various mathematical
settings, for example in Ulmer's study of elliptic curves with large rank over function
fields \cite{Ulmer} (see Moree and Sol\'e \cite{Moso} for further examples).
The study of $i_q(n)$ quickly leads into Artin primitive root
type problems \cite{Moso}.\\

\noindent {\bf Acknowledgement.} I'd like to thank 
 Zeev Rudnick for inviting me to give the talk
this manuscript is based on and
Jilyana Cazaran 
(Louisiana State University) for kindly typing
the initial version of these lecture notes from my handwritten ones.
My trip to Oberwolfach was paid for
from Prof. Opdam's NWO-PIONEER fund.

\vfil\eject

{\small
\begin{thebibliography}{99}

\bibitem{Ballot} C. Ballot, Density of prime divisors of linear 
recurrences, {\it Mem. Amer. Math.
Soc.} {\bf 115} (1995), no. 551, viii+102 pp..

\bibitem{Bilharz} H. Bilharz, Primdivisoren mit vorgegebener
Primitivwurzel, {\it Math. Ann.} {\bf 114} (1937), 476--492.

\bibitem{Cangelmi} L. Cangelmi and F. Pappalardi, On the $r$-rank Artin conjecture. II, {\it J.
Number Theory} {\bf 75} (1999), 120--132. 

\bibitem{CM} K. Chinen and L. Murata, On a distribution property of the residual order of $a({\rm mod~}p)$. I, II, 
{\it J. Number Theory}  {\bf 105}  (2004), 60--81; 82--100.

\bibitem{recur} G. Everest, Graham, A. van der Poorten, I. Shparlinski and T. Ward, 
{\it Recurrence sequences}, Mathematical Surveys and Monographs {\bf 104}, American Mathematical Society, 
Providence, RI, 2003. xiv+318 pp.. 

\bibitem{Gi} K. Girstmair, A "popular" class number formula, 
{\it Amer. Math. Monthly} {\bf 101} (1994), 997--1001.

\bibitem{Goldfeld} {M. Goldfeld}, Artin's conjecture on the
average,
{\it Mathematika} {\bf 15} (1968), 223--226.

\bibitem{GM} R. Gupta and M. Ram Murty, A remark on Artin's conjecture, 
{\it Invent. Math.}  {\bf 78}  (1984),  127--130. 

\bibitem{Hasse} H. Hasse, \"Uber die Artinsche Vermutung und verwandte Dichtefragen, {\it
Ann. Acad. Sci. Fennicae. Ser. A. I. Math.-Phys.} 1952, (1952). no. 116, 17 pp.

\bibitem{Hasseboek} H. Hasse, {\it Vorlesungen \"uber Zahlentheorie}, Akademie-Verlag, 1950.



\bibitem{HB} {D.R. Heath-Brown}, Artin's conjecture for
primitive roots,
{\it Quart. J. Math. Oxford} {\bf 37} (1986), 27--38.

\bibitem{HM1} J. Holden and P. Moree, {\it New conjectures and results for small cycles of the 
discrete logarithm}, High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams, 245--254,
Fields Inst. Commun. {\bf 41}, Amer. Math. Soc., Providence, RI, 2004. 

\bibitem{HM2} J. Holden and P. Moree, Some heuristics and results for small cycles of the discrete logarithm, 
arXiv:math.NT/0401013, to appear in Mathematics of Computation. 



\bibitem{Hooley1} {C. Hooley}, Artin's conjecture for primitive
 roots,
{\it J. Reine Angew. Math.} {\bf 225} (1967), 209--220.


\bibitem{Hsu} C.-N. Hsu, On Artin's conjecture for
the Carlitz module, {\it Compositio Math.} {\bf 106} (1997),
247--266.

\bibitem{Jensen} {E. Jensen and M.R. Murty}, Artin's conjecture for
polynomials over finite fields, Number theory, 167-181, Trends Math., Birkh�user, Basel, 2000.

\bibitem{Kan} J. Kan, A note on two conjectures, {\it Acta Arith.} {\bf 111} (2004), 1--3.

\bibitem{Khare} A. Khare, Divisibility tests and recurring decimals in Euclidean domains, 
arXiv:math.NT/0406025, submitted. 

\bibitem{kit} Y. Kitaoka, Distribution of units of a cubic field with negative discriminant, 
{\it J. Number Theory}  {\bf 91}  (2001),  318--355.

\bibitem{knoflook} H.-W. Knobloch, \"Uber Primzahlreihen nebst Anwendung auf ein elementares Dichteproblem, 
{\it Abh. Math. Sem. Univ. Hamburg} {\bf 19} (1954), 1--13. 

\bibitem{K1} P. Kurlberg, On the order of unimodular matrices modulo integers, 
{\it Acta Arith.}  {\bf 110}  (2003),  141--151.

\bibitem{KR} P. Kurlberg and Z. Rudnick, On quantum ergodicity for linear maps of the torus, 
{\it Comm. Math. Phys.}  {\bf 222}  (2001),  201--227.

\bibitem{Laga} J.C. Lagarias, The set of primes dividing the Lucas numbers has density $2/3$, 
{\it Pacific J. Math.}  {\bf 118}  (1985), 449--461; errata, ibid. {\bf 162}  (1994),  393--396. 


\bibitem{Lafolk} {S. Lang},
On the zeta function of number fields,
{\it Invent. Math.} {\bf 12} (1971), 337--345.


\bibitem{LangTrotter} S. Lang and H. Trotter, Primitive points on
elliptic curves, {\it Bull. Amer. Math. Soc.} {\bf 83}
(1977), 289-292.

\bibitem{Lehmers} {D.H. Lehmer and Emma Lehmer}, {\it Heuristics, anyone ?}, in
"Studies in Mathematical Analysis and Related Topics," pp. 202--210,
Stanford Univ. Press, Stanford, CA, 1962.

\bibitem{Lemmermeyer} F. Lemmermeyer, {\it Reciprocity laws. From Euler to Eisenstein}., Springer Monographs
in Mathematics, Springer-Verlag, Berlin, 2000. xx+487 pp..

\bibitem{Lenstra} {H.W. Lenstra, jr.}, On Artin's conjecture
and Euclid's
algorithm in global fields, {\it Invent. Math.} {\bf 42} (1977), 202--224.

\bibitem{LMS} H.W. Lenstra, jr., P. Moree and P. Stevenhagen, 
Character sums for primitive root densities, in preparation.

\bibitem{Li} S. Li, Artin's conjecture on average for composite
moduli, {\it J. Number Theory} {\bf 84} (2000), 93--118.

\bibitem{LiP} S. Li and C. Pomerance, {\it Primitive roots: a survey}, Number theoretic methods (Iizuka, 2001),  219--231, Dev. Math., 8, Kluwer Acad. Publ., 
Dordrecht, 2002. 

\bibitem{LiP2} S. Li and C. Pomerance, On generalizing Artin's conjecture on primitive roots to composite moduli, 
{\it J. Reine Angew. Math.}  {\bf 556}  (2003), 205--224. 

\bibitem{Matthews} K.R. Matthews, A generalisation of Artin's conjecture for primitive roots, {\it Acta Arith.} {\bf 29}
(1976), 113--146. 

\bibitem{Mirsky} L. Mirsky, The number of representations of an integer as the sum of a prime and a $k$-free 
integer,  {\it Amer. Math. Monthly}  {\bf 56} (1949), 17--19.


\bibitem{Moree3} {P. Moree}, Uniform distribution of primes having
a prescribed primitive root, {\it Acta Arith.}
{\bf 89} (1999), 9--21.

\bibitem{MoreeAP} {P. Moree}, Primes in arithmetic progression
having a prescribed primitive root, {\it J. Number Theory}
{\bf 78} (1999), 85--98.

\bibitem{MoreeNP} {P. Moree}, Asymptotically exact heuristics for (near)
primitive roots, {\it J. Number Theory} {\bf 83}
(2000), 155--181.

\bibitem {Monumi} {P. Moree}, Approximation of singular series and
automata, {\it Manuscripta Math.} {\bf 101} (2000), 385--399.

\bibitem{Mofield} {P. Moree}, On the average number of elements in a finite field with order or index in a 
prescribed residue class, {\it Finite Fields Appl.}  {\bf 10}  (2004), 438--463. 

\bibitem{Moreejapi1} {P. Moree}, On the distribution of the order and index of 
$g({\rm mod~}p)$ over residue classes I, to appear in the Journal of Number Theory, II, 
arXiv:math.NT/0404339, submitted, III, arXiv:math.NT/0405527, submitted.

\bibitem{Moreegriffin} {P. Moree}, Primitive root producing quadratics, arXiv:math.NT/0406033, submitted. 


\bibitem{Model} {P. Moree}, Asymptotically exact heuristics for prime divisors of $\{a^k+b^k\}_{k=1}^{\infty}$, 
arXiv:math.NT/0311483, submitted.

\bibitem{Modelerd} {P. Moree}, On primes $p$ for which $d$ divides ord$_p(g)$, arXiv:math.NT/040742, submitted.

\bibitem{Huib} P. Moree and H. Hommersom, Value distribution of Ramanujan sums and of 
cyclotomic polynomial coefficients, arXiv:math.NT/0307352 . 

\bibitem{Moso} {P. Moree and P. Sol\'e}, Around Pelik\'an's conjecture on very odd sequences, 
arXiv:math.NT/0407084, submitted. 

\bibitem{MS} P. Moree and P. Stevenhagen, A two-variable Artin
conjecture, {\it J. Number Theory}  {\bf 85}  (2000),  291--304.

\bibitem{mos} P. Moree and P. Stevenhagen, Prime divisors of the Lagarias sequence, 
{\it J. Th\'eor. Nombres Bordeaux}  {\bf 13}  (2001),  241--251.

\bibitem{MurtyGoldstein} M.R. Murty, An analogue of Artin's
conjecture for abelian extensions, {\it J. Number Theory}
{\bf 18} (1984), 241--248.

%\bibitem{Murty1} M.R. Murty, Artin's conjecture for
%primitive roots, {\it Math. Intelligencer}  {\bf 10} (1988),
%59-67.

\bibitem{Murty} M.R. Murty, {\it Artin's conjecture and elliptic analogues}, Sieve methods, exponential
sums, and their applications in number theory (Cardiff, 1995), 325--344, London Math. Soc. Lecture
Note Ser., 237, Cambridge Univ. Press, Cambridge, 1997. 

\bibitem{Pappa-1} F. Pappalardi, On Hooley's theorem with weights, 
{\it Rend. Sem. Mat. Univ. Politec. Torino} {\bf 53} (1995), 375--388.

\bibitem{Paplepel} F. Pappalardi, On the $r$-rank Artin conjecture, 
{\it Math. Comp.} {\bf 66} (1997), 853--868.

\bibitem{Pappa} F. Pappalardi, Square free values of the order function, 
{\it New York J. Math.} {\bf 9} (2003), 331--344 (electronic).

\bibitem{PS} F. Pappalardi and I. Shparlinski, On Artin's conjecture over function fields,
{\it Finite Fields Appl.} {\bf 1} (1995), 399--404. 

\bibitem{pommie} C. Pomerance, personal communication.

\bibitem{RM} A. Reznikov and P. Moree, Three-manifold subgroup growth, homology of coverings and simplicial 
volume, {\it Asian J. Math.} {\bf 1} (1997),  764--768.

\bibitem{Rodier} F. Rodier, Estimation asymptotique de la distance minimale du dual des codes BCH et polyn\^omes de 
Dickson, {\it Discrete Math.} {\bf 149} (1996), 205--221.

\bibitem{Rosen} M. Rosen, {\it Number theory in function fields}, Graduate Texts in Mathematics 
{\bf 210}, Springer-Verlag, New York, 2002. xii+358 pp. ISBN: 0-387-95335-3

\bibitem{Ros1} H. Roskam, A quadratic analogue of Artin's conjecture on primitive roots, 
{\it J. Number Theory} {\bf 81} (2000), 93--109.

\bibitem{Ros2} H. Roskam, Artin's primitive root conjecture for quadratic fields, 
{\it J. Th\'eor. Nombres Bordeaux}  {\bf 14}  (2002),  287--324.

\bibitem{Sander} J.W. Sander, Prime power divisors of multinomial coefficients and Artin's conjecture, 
{\it J. Number Theory} {\bf 46}  (1994),  372--384.


\bibitem{Stephens} {P.J. Stephens}, An average result for
Artin's conjecture, {\it Mathematika} {\bf 16} (1969), 178--188.

\bibitem{Stephens3} {P.J. Stephens}, Prime divisors of
second-order linear recurrences. I, II, {\it J. Number
Theory}  {\bf 8} (1976), 313--332; 333--345.

\bibitem{Steven} P. Stevenhagen, The correction factor in Artin's primitive root 
conjecture, {\it J. Th\'eor. Nombres Bordeaux} {\bf 15}  (2003),  383--391.

\bibitem{LS} P. Stevenhagen and H.W. Lenstra, jr., Chebotarev and his density theorem, {\it Math.
Intelligencer} {\bf 18} (1996), 26--37.  

\bibitem{Ulmer} D. Ulmer, Elliptic curves with large rank over function fields, 
{\it Ann. of Math.}  {\bf 155}  (2002),  295--315. 

%\bibitem{Weinberger} P.J. Weinberger, A counterexample to an
%analogue of Artin's conjecture, {\it Proc.
%Amer. Math. Soc.}  {\bf 35} (1972), 49--52.

\end{thebibliography}

%\nocite{*}
%\bibliography{ArtinPrimRoot}
%\bibliographystyle{amsplain}

\begin{center}\sc Pieter Moree\\
Max-Planck-Institut f\"ur Mathematik,\\ 
Vivatsgasse 7\\
D-53111 Bonn, Deutschland\\ 
{\em e-mail address:} \rm moree@mpim-bonn.mpg.de\\
\end{center}}



\end{document}

{\em homepage:} http://web.inter.nl.net/hcc/J.Moree/\\
\bibitem{Mojapi2} {P. Moree}, On the distribution of the order and index of 
$g({\rm mod~}p)$ over residue classes II, arXiv:math.NT/0404339, submitted.

\bibitem{Mojapi3} {P. Moree}, On the distribution of the order and index of 
$g({\rm mod~}p)$ over residue classes III, arXiv:math.NT/0405527, submitted.

Hecke, in the 1920's showed in a complicated work that
$\zeta_K(s)$ satisfies a functional equation, analogous to the
celebrated functional equation for the Riemann zeta-function.  Tate, in his famous thesis (written around 1950), using adeles and harmonic analysis, greatly
simplified Hecke's work.

\begin{theorem}\label{thm:Lenstra77}
(Lenstra, 1977) Let $\sigma_a$ be the action of $\Q(\zeta_f)$
determined by $\sigma_a(\zeta_f)=\zeta_f^a$.  Let 
$c_a(n)=\left\{
\begin{array}{ll}
1 &{\rm if~}\sigma_a\mid_{\Q(\zeta_f)\cap\Q(\zeta_n,g^{1\over n})}=id\\ 
0 &{\rm otherwise}
\end{array}
\right.$.  Put 
$\delta(a,f,g)=\displaystyle\sum_{n=1}^\infty{\mu(n)c_a(n)\over[\Q(\zeta_f,\zeta_n,g^{1\over n}):\Q]}$.  Then
${\mathcal{P}}(g,f,a)(x)=\delta(a,f,g){x\over\log x}
+O\left({x\log\log x\over\log^2 x}\right)$.
\end{theorem}

\noindent$\S5$ Goldstein's conjecture\\

Larry Goldstein formulated a conjecture in 1972 which implies Artin's
conjecture.  His conjecture is as follows : for each prime $q$, let $L_q$
be an algebraic number field, normal and of finite degree over $\Q$.  For each squarefree $k$, set $L_k=\displaystyle\prod_{q\mid k} L_q$,
whre $L_1$ is taken to be $\Q$.  Let $n(k)=[L_k:\Q]$.  Then the set
of rational primes which do not split completely in any $L_q$ has a natural
density $\delta$, where $\delta=\displaystyle\sum_{k=1}^\infty{\mu(k)\over
n(k)}$.  Artin's conjecture is recaptured by the special case 
$L_q=\Q(\zeta_q,g^{1\over q})$. 

Weinberger (1972), showed that Goldstein's conjecture is false, in
general.  His counterexample consisted of certain extensions $L_q$, abelian
over $\Q$, and satisfying $q\ll{\log|d(q)|\over n(q)}\ll q$.  ?? 
Goldstein then proved an adapted version of his theorem, on GRH.  An
unconditional version of this was proved by Ram Murty.  

\begin{theorem}\label{thm:L_q}
Suppose that for $q$ suficiently large, $L_q\mid_{\Q}$ is abelian
and that $\displaystyle\sum_{k=1}^\infty{\mu^2(k)\over n(k)}<\infty$.  If
\begin{enumerate}
\item ${\limsup\over{k\to\infty}}{\log|d_k|\over n(k)\log k}\ll\infty$ 
\item for some $0<\theta<{1\over 2c}$, $M(x,x^\theta)=o({x\over\log x})$,
\end{enumerate}
where $M(x,y)$ is the number of primes $\leqq x$ that split completely in
some $L_q$, $q>y$, then the set of primes which do not split completely in
any $L_q$ has a denstiy $\delta=\displaystyle\sum_{k=1}^\infty{\mu(k)\over
n(k)}$.
\end{theorem}

\bibitem{Hooley2} {C. Hooley} Applications of sieve methods
to the theory of numbers, {\it Cambridge Tracts
in Mathematics} {\bf 70}, Cambridge University Press,
Cambridge-New York-Melbourne, 1976. xiv+122
pp.

both $p\equiv 1({\rm mod~}q)$
and $g^{p-1\over q}\equiv 1({\rm mod~}p)$,
%$$\left\{\begin{array}{rl}
%p\equiv&1(\mod q)\\  
%g^{p-1\over q}\equiv&1(\mod p),
%\end{array}\right \hbox{}$$

math0412262.extracted_bib
\begin{thebibliography}{99}

\bibitem{Ballot} C. Ballot, Density of prime divisors of linear 
recurrences, {\it Mem. Amer. Math.
Soc.} {\bf 115} (1995), no. 551, viii+102 pp..

\bibitem{Bilharz} H. Bilharz, Primdivisoren mit vorgegebener
Primitivwurzel, {\it Math. Ann.} {\bf 114} (1937), 476--492.

\bibitem{Cangelmi} L. Cangelmi and F. Pappalardi, On the $r$-rank Artin conjecture. II, {\it J.
Number Theory} {\bf 75} (1999), 120--132. 

\bibitem{CM} K. Chinen and L. Murata, On a distribution property of the residual order of $a({\rm mod~}p)$. I, II, 
{\it J. Number Theory}  {\bf 105}  (2004), 60--81; 82--100.

\bibitem{recur} G. Everest, Graham, A. van der Poorten, I. Shparlinski and T. Ward, 
{\it Recurrence sequences}, Mathematical Surveys and Monographs {\bf 104}, American Mathematical Society, 
Providence, RI, 2003. xiv+318 pp.. 

\bibitem{Gi} K. Girstmair, A "popular" class number formula, 
{\it Amer. Math. Monthly} {\bf 101} (1994), 997--1001.

\bibitem{Goldfeld} {M. Goldfeld}, Artin's conjecture on the
average,
{\it Mathematika} {\bf 15} (1968), 223--226.

\bibitem{GM} R. Gupta and M. Ram Murty, A remark on Artin's conjecture, 
{\it Invent. Math.}  {\bf 78}  (1984),  127--130. 

\bibitem{Hasse} H. Hasse, \"Uber die Artinsche Vermutung und verwandte Dichtefragen, {\it
Ann. Acad. Sci. Fennicae. Ser. A. I. Math.-Phys.} 1952, (1952). no. 116, 17 pp.

\bibitem{Hasseboek} H. Hasse, {\it Vorlesungen \"uber Zahlentheorie}, Akademie-Verlag, 1950.



\bibitem{HB} {D.R. Heath-Brown}, Artin's conjecture for
primitive roots,
{\it Quart. J. Math. Oxford} {\bf 37} (1986), 27--38.

\bibitem{HM1} J. Holden and P. Moree, {\it New conjectures and results for small cycles of the 
discrete logarithm}, High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams, 245--254,
Fields Inst. Commun. {\bf 41}, Amer. Math. Soc., Providence, RI, 2004. 

\bibitem{HM2} J. Holden and P. Moree, Some heuristics and results for small cycles of the discrete logarithm, 
arXiv:math.NT/0401013, to appear in Mathematics of Computation. 



\bibitem{Hooley1} {C. Hooley}, Artin's conjecture for primitive
 roots,
{\it J. Reine Angew. Math.} {\bf 225} (1967), 209--220.


\bibitem{Hsu} C.-N. Hsu, On Artin's conjecture for
the Carlitz module, {\it Compositio Math.} {\bf 106} (1997),
247--266.

\bibitem{Jensen} {E. Jensen and M.R. Murty}, Artin's conjecture for
polynomials over finite fields, Number theory, 167-181, Trends Math., Birkh�user, Basel, 2000.

\bibitem{Kan} J. Kan, A note on two conjectures, {\it Acta Arith.} {\bf 111} (2004), 1--3.

\bibitem{Khare} A. Khare, Divisibility tests and recurring decimals in Euclidean domains, 
arXiv:math.NT/0406025, submitted. 

\bibitem{kit} Y. Kitaoka, Distribution of units of a cubic field with negative discriminant, 
{\it J. Number Theory}  {\bf 91}  (2001),  318--355.

\bibitem{knoflook} H.-W. Knobloch, \"Uber Primzahlreihen nebst Anwendung auf ein elementares Dichteproblem, 
{\it Abh. Math. Sem. Univ. Hamburg} {\bf 19} (1954), 1--13. 

\bibitem{K1} P. Kurlberg, On the order of unimodular matrices modulo integers, 
{\it Acta Arith.}  {\bf 110}  (2003),  141--151.

\bibitem{KR} P. Kurlberg and Z. Rudnick, On quantum ergodicity for linear maps of the torus, 
{\it Comm. Math. Phys.}  {\bf 222}  (2001),  201--227.

\bibitem{Laga} J.C. Lagarias, The set of primes dividing the Lucas numbers has density $2/3$, 
{\it Pacific J. Math.}  {\bf 118}  (1985), 449--461; errata, ibid. {\bf 162}  (1994),  393--396. 


\bibitem{Lafolk} {S. Lang},
On the zeta function of number fields,
{\it Invent. Math.} {\bf 12} (1971), 337--345.


\bibitem{LangTrotter} S. Lang and H. Trotter, Primitive points on
elliptic curves, {\it Bull. Amer. Math. Soc.} {\bf 83}
(1977), 289-292.

\bibitem{Lehmers} {D.H. Lehmer and Emma Lehmer}, {\it Heuristics, anyone ?}, in
"Studies in Mathematical Analysis and Related Topics," pp. 202--210,
Stanford Univ. Press, Stanford, CA, 1962.

\bibitem{Lemmermeyer} F. Lemmermeyer, {\it Reciprocity laws. From Euler to Eisenstein}., Springer Monographs
in Mathematics, Springer-Verlag, Berlin, 2000. xx+487 pp..

\bibitem{Lenstra} {H.W. Lenstra, jr.}, On Artin's conjecture
and Euclid's
algorithm in global fields, {\it Invent. Math.} {\bf 42} (1977), 202--224.

\bibitem{LMS} H.W. Lenstra, jr., P. Moree and P. Stevenhagen, 
Character sums for primitive root densities, in preparation.

\bibitem{Li} S. Li, Artin's conjecture on average for composite
moduli, {\it J. Number Theory} {\bf 84} (2000), 93--118.

\bibitem{LiP} S. Li and C. Pomerance, {\it Primitive roots: a survey}, Number theoretic methods (Iizuka, 2001),  219--231, Dev. Math., 8, Kluwer Acad. Publ., 
Dordrecht, 2002. 

\bibitem{LiP2} S. Li and C. Pomerance, On generalizing Artin's conjecture on primitive roots to composite moduli, 
{\it J. Reine Angew. Math.}  {\bf 556}  (2003), 205--224. 

\bibitem{Matthews} K.R. Matthews, A generalisation of Artin's conjecture for primitive roots, {\it Acta Arith.} {\bf 29}
(1976), 113--146. 

\bibitem{Mirsky} L. Mirsky, The number of representations of an integer as the sum of a prime and a $k$-free 
integer,  {\it Amer. Math. Monthly}  {\bf 56} (1949), 17--19.


\bibitem{Moree3} {P. Moree}, Uniform distribution of primes having
a prescribed primitive root, {\it Acta Arith.}
{\bf 89} (1999), 9--21.

\bibitem{MoreeAP} {P. Moree}, Primes in arithmetic progression
having a prescribed primitive root, {\it J. Number Theory}
{\bf 78} (1999), 85--98.

\bibitem{MoreeNP} {P. Moree}, Asymptotically exact heuristics for (near)
primitive roots, {\it J. Number Theory} {\bf 83}
(2000), 155--181.

\bibitem {Monumi} {P. Moree}, Approximation of singular series and
automata, {\it Manuscripta Math.} {\bf 101} (2000), 385--399.

\bibitem{Mofield} {P. Moree}, On the average number of elements in a finite field with order or index in a 
prescribed residue class, {\it Finite Fields Appl.}  {\bf 10}  (2004), 438--463. 

\bibitem{Moreejapi1} {P. Moree}, On the distribution of the order and index of 
$g({\rm mod~}p)$ over residue classes I, to appear in the Journal of Number Theory, II, 
arXiv:math.NT/0404339, submitted, III, arXiv:math.NT/0405527, submitted.

\bibitem{Moreegriffin} {P. Moree}, Primitive root producing quadratics, arXiv:math.NT/0406033, submitted. 


\bibitem{Model} {P. Moree}, Asymptotically exact heuristics for prime divisors of $\{a^k+b^k\}_{k=1}^{\infty}$, 
arXiv:math.NT/0311483, submitted.

\bibitem{Modelerd} {P. Moree}, On primes $p$ for which $d$ divides ord$_p(g)$, arXiv:math.NT/040742, submitted.

\bibitem{Huib} P. Moree and H. Hommersom, Value distribution of Ramanujan sums and of 
cyclotomic polynomial coefficients, arXiv:math.NT/0307352 . 

\bibitem{Moso} {P. Moree and P. Sol\'e}, Around Pelik\'an's conjecture on very odd sequences, 
arXiv:math.NT/0407084, submitted. 

\bibitem{MS} P. Moree and P. Stevenhagen, A two-variable Artin
conjecture, {\it J. Number Theory}  {\bf 85}  (2000),  291--304.

\bibitem{mos} P. Moree and P. Stevenhagen, Prime divisors of the Lagarias sequence, 
{\it J. Th\'eor. Nombres Bordeaux}  {\bf 13}  (2001),  241--251.

\bibitem{MurtyGoldstein} M.R. Murty, An analogue of Artin's
conjecture for abelian extensions, {\it J. Number Theory}
{\bf 18} (1984), 241--248.

%\bibitem{Murty1} M.R. Murty, Artin's conjecture for
%primitive roots, {\it Math. Intelligencer}  {\bf 10} (1988),
%59-67.

\bibitem{Murty} M.R. Murty, {\it Artin's conjecture and elliptic analogues}, Sieve methods, exponential
sums, and their applications in number theory (Cardiff, 1995), 325--344, London Math. Soc. Lecture
Note Ser., 237, Cambridge Univ. Press, Cambridge, 1997. 

\bibitem{Pappa-1} F. Pappalardi, On Hooley's theorem with weights, 
{\it Rend. Sem. Mat. Univ. Politec. Torino} {\bf 53} (1995), 375--388.

\bibitem{Paplepel} F. Pappalardi, On the $r$-rank Artin conjecture, 
{\it Math. Comp.} {\bf 66} (1997), 853--868.

\bibitem{Pappa} F. Pappalardi, Square free values of the order function, 
{\it New York J. Math.} {\bf 9} (2003), 331--344 (electronic).

\bibitem{PS} F. Pappalardi and I. Shparlinski, On Artin's conjecture over function fields,
{\it Finite Fields Appl.} {\bf 1} (1995), 399--404. 

\bibitem{pommie} C. Pomerance, personal communication.

\bibitem{RM} A. Reznikov and P. Moree, Three-manifold subgroup growth, homology of coverings and simplicial 
volume, {\it Asian J. Math.} {\bf 1} (1997),  764--768.

\bibitem{Rodier} F. Rodier, Estimation asymptotique de la distance minimale du dual des codes BCH et polyn\^omes de 
Dickson, {\it Discrete Math.} {\bf 149} (1996), 205--221.

\bibitem{Rosen} M. Rosen, {\it Number theory in function fields}, Graduate Texts in Mathematics 
{\bf 210}, Springer-Verlag, New York, 2002. xii+358 pp. ISBN: 0-387-95335-3

\bibitem{Ros1} H. Roskam, A quadratic analogue of Artin's conjecture on primitive roots, 
{\it J. Number Theory} {\bf 81} (2000), 93--109.

\bibitem{Ros2} H. Roskam, Artin's primitive root conjecture for quadratic fields, 
{\it J. Th\'eor. Nombres Bordeaux}  {\bf 14}  (2002),  287--324.

\bibitem{Sander} J.W. Sander, Prime power divisors of multinomial coefficients and Artin's conjecture, 
{\it J. Number Theory} {\bf 46}  (1994),  372--384.


\bibitem{Stephens} {P.J. Stephens}, An average result for
Artin's conjecture, {\it Mathematika} {\bf 16} (1969), 178--188.

\bibitem{Stephens3} {P.J. Stephens}, Prime divisors of
second-order linear recurrences. I, II, {\it J. Number
Theory}  {\bf 8} (1976), 313--332; 333--345.

\bibitem{Steven} P. Stevenhagen, The correction factor in Artin's primitive root 
conjecture, {\it J. Th\'eor. Nombres Bordeaux} {\bf 15}  (2003),  383--391.

\bibitem{LS} P. Stevenhagen and H.W. Lenstra, jr., Chebotarev and his density theorem, {\it Math.
Intelligencer} {\bf 18} (1996), 26--37.  

\bibitem{Ulmer} D. Ulmer, Elliptic curves with large rank over function fields, 
{\it Ann. of Math.}  {\bf 155}  (2002),  295--315. 

%\bibitem{Weinberger} P.J. Weinberger, A counterexample to an
%analogue of Artin's conjecture, {\it Proc.
%Amer. Math. Soc.}  {\bf 35} (1972), 49--52.

\end{thebibliography}