\input amstex
\documentstyle{amsppt}
\loadeusm
\topmatter
\title
There are Infinitely Many Perrin Pseudoprimes
\endtitle
\date December 23, 1997
\enddate
\email grantham\@super.org
\endemail
\author Jon Grantham \endauthor
\subjclass{11Y11 (11N13 11N25)}
\endsubjclass
\address Institute for Defense Analyses, Center for Computing Sciences,
17100 Science Drive, Bowie, MD 20715 
\endaddress
\abstract
This paper proves the existence of infinitely many Perrin pseudoprimes,
as conjectured by Adams and Shanks in 1982.  The theorem proven covers a 
general class of pseudoprimes based on recurrence sequences.  The
proof uses ingredients of the recent proof that are are infinitely
many Carmichael numbers, along with zero-density estimates for Hecke
L-functions.
\endabstract
\NoBlackBoxes
\def\as{1}
\def\agp{2}
\def\dav{3}
\def\fogels{4}
\def\gord{5}
\def\gordpom{6}
\def\meone{7}
\def\gurak{8}
\def\hilone{9}
\def\hiltwo{10}
\def\lmo{11}
\def\lo{12}
\def\len{13}
\def\lenpom{14}
\def\mojones{15}
\def\sze{16}
\def\gcmd{\operatorname{gcmd}}
\def\disc{\operatorname{disc}}
\endtopmatter
\document


\head{\S 1 Background}
\endhead
In a 1982 paper \cite{\as}, Adams and Shanks introduced a
pseudoprimality test based on third order recurrence sequences
and asked if there are infinitely many composites which pass it --- Perrin
pseudoprimes, as they have become known.

They answered the question,
``Almost certainly yes, but we cannot prove it.  Almost certainly, there
are infinitely many [Carmichael numbers which are Perrin pseudoprimes],
and yet it has never been
proved that there are infinitely many Carmichael numbers.''

In 1994, Alford, Granville and Pomerance \cite{\agp} proved that there are
infinitely many Carmichael numbers.
A simple modification of that proof shows that there are infinitely
many Lucas and Lehmer pseudoprimes.  (If the characteristic
polynomial is $f(x)$, require all prime divisors $p$ of the Carmichael
numbers to have $p\equiv 1 \bmod 4\disc(f)$).

In this paper, the techniques of that proof
are combined with results about Hecke L-functions to
show that there are infinitely many Perrin pseudoprimes.

In fact, a more general result can be proven.

\proclaim{Theorem 1.1}
Let $f(x)\in\Bbb{Z}[x]$
be a monic, squarefree polynomial with splitting field $K$.  There are
infinitely many Frobenius pseudoprimes with respect to $f(x)$.
In fact, there are $\gg N^c$ Carmichael-Frobenius numbers with respect
to $K$ which are less than $N$, for
some $c=c(K)>0$.
\endproclaim

We know from Corollary 3.7 and Theorem 3.10 of \cite{\meone} that this theorem
shows that there are infinitely many Perrin pseudoprimes,
if we take $f(x)=x^3-x-1$.  (Note that all pseudoprimes constructed
here have S-signatures and the quadratic forms portion of Adams and
Shanks' test does not apply.)
From Theorems 3.11 and 3.12 of \cite{\meone}, we also have that there are
infinitely many pseudoprimes in the senses of Gurak \cite{\gurak}
and Szekeres \cite{\sze}.

By Proposition 5.1 of \cite{\meone}, in order to prove Theorem 1.1,
it suffices to show that there are infinitely many
Carmichael numbers $n$, such that for all $p|n$, $f(x)$ splits completely mod $p$.
The proof will involve
modifying the
construction in \cite{\agp} to ensure that each of the prime factors
of the Carmichael numbers constructed has this property.
 
The main result that will be used in this proof is a version 
of the ``prime ideal theorem for arithmetic progressions'' that gives a
uniform error term, except for a possible exceptional
progression.
This corresponds to Theorem 2.1 of \cite{\agp}.

\head{\S 2 Distribution of Primes}
\endhead
Theorems about the distribution of primes in arithmetic progressions
are traditionally proved using Dirichlet characters, homomorphisms from the
integers mod $q$ to the complex roots of unity.  (The map is
defined to be zero on integers not coprime to $q$.)
Since we want to prove a theorem about primes in a particular
arithmetic progression which split completely, we
employ a slightly different sort of Dirichlet character.

We recall the definitions of \cite{\lenpom}.

\proclaim{Definitions}
Let $K$ be an algebraic number field and $\frak{O}_K$ its ring of
integers.  A {\bf  cycle} of $K$ is a formal product $\frak{m}=\prod
\frak{p}^{m(\frak{p})}$ extending over all of the primes of $K$, where
the $m(\frak p)$ are nonnegative integers, almost all $0$,
$m(\frak{p})=0$ for complex $\frak{p}$ and $m(\frak{p})\le 1$ for real
$\frak{p}$.  Let $\eusm{I}$ be the group of fractional ideals of
$\frak{O}_K$.  Let $\eusm{I}(\frak{m})$ be the subgroup of $\eusm{I}$
generated by the finite primes $\frak{p}$ for which $m(\frak{p})=0$.
Let $P_{\frak{m}}$ be the subgroup of $\eusm{I}(\frak{m})$ generated
by the nonzero ideals of the form $\frak{O}_K\alpha$, where
$\alpha\in\frak{O}_K$ is such that $\alpha\equiv 1 \bmod
\frak{p}^{m(\frak{p})}$ for each finite prime $\frak p$, and
$\alpha>0$ under each embedding of $K$ in the field of real numbers
corresponding to a real prime $\frak{p}$ with $m(\frak{p})=1$.  The
{\bf norm} of a cycle $\frak{m}=\prod\frak{p}^{m(\frak{p})}$ is the
number $N(\frak{m})=\prod N(\frak{p})^{m(\frak{p})}$, where $\frak{p}$
in the second product ranges over only the finite primes, and
$N(\frak{p})$ is the norm of $\frak{p}$ in $K$.

A {\bf Dirichlet character of $K$} is a pair consisting of a cycle
$\frak{m}$ of $K$ and a group homomorphism
$\chi:\eusm{I}(\frak{m})\mapsto\Bbb{C}^*$ such that $P_{\frak{m}}$
is contained in the kernel.  We call $\frak{m}$ the {\bf modulus} of
$\chi$.

Given two Dirichlet characters $\chi$ and $\chi'$ with moduli $\frak{m}$ 
and $\frak{m}'$, we say that $\chi$ is {\bf induced} by $\chi'$ 
if $\frak{m}'(\frak{p})\le\frak{m}(\frak{p})$ for all $\frak{p}$ and $\chi$ 
is the composition of the inclusion 
$\eusm{I}(\frak{m})\subset\eusm{I}(\frak{m}')$ with $\chi'$.  A Dirichlet 
character is {\bf primitive} if it is not induced by any character other than 
itself.  The modulus of the unique primitive character inducing a 
Dirichlet character $\chi$ is called the {\bf conductor} of $\chi$.

For a Dirichlet character $\chi$ of $K$, $L(s,\chi)$ is defined to be $\sum
\chi(\frak{i})N(\frak{i})^{-s}$, where the sum is over the nonzero
ideals of the ring of integers of $K$ and $\operatorname{Re} s>1$.  This sum
is absolutely convergent, and $L(s,\chi')$ can be extended to a
meromorphic function on the complex plane.  It has a simple pole at
$s=1$ if $\chi'$ is principal and is holomorphic otherwise.

\endproclaim

Let $K$ be the splitting field of $f$, $n=[K:\Bbb{Q}]$, and
$d=\disc(K)$.
Let $\chi$ be a Dirichlet character mod $q$ (in the traditional sense).  We associate to it a
Dirichlet character of $K$ in the
following way.

Given an ideal $\frak{i}\subset\frak{O}_K$, 
let $\chi'(\frak{i})=\chi(N(\frak{i}))$.
Then $\chi'$ is an example of a
Dirichlet character of $K$ with conductor dividing $N(q)$.

Let $\Psi(x,\chi')=\sum_{N(\frak{i})<x}\chi'(\frak{i})\Lambda(\frak{i})$,
where $\Lambda(\frak{i})=\log N(\frak{p})$
if $\frak{i}=\frak{p}^k$ for some prime ideal $\frak{p}$, and $0$
otherwise.
Then $$\frac 1{\phi(q)}\sum_{\chi\bmod q} \bar\chi(a)\Psi(x,\chi')=\sum\Sb
N(\frak{i})<x\\N(\frak{i})\equiv a\bmod q\endSb \Lambda(\frak{i}).$$

We will prove some results about $L(s,\chi')$ that enable us to get
results about $\Psi(x,\chi')$, and thus about the distribution of
primes that split completely in $K$ and lie in a particular residue
class.

\proclaim{Lemma 2.1}
Fix a number field $K$.
Let $\chi$ be a real Dirichlet character of $K \bmod \frak{m}$.  Let $M=N(\frak{m})$.
Let $s$ be a real number in the range $2>s>1$.
If $\chi$ is principal, then
$$\frac {L'}L(s,\chi) > -\frac 1{s-1}-c_1\log 2M,$$
for some $c_1>0$, depending on $K$.
If $\chi$ is non-principal, and if $L(s,\chi)$ has some real zero $\rho>0$,
$$\frac {L'}L(s,\chi) > \frac 1{s-\rho}-c_1\log 2M,$$
and 
$$\frac {L'}L(s,\chi)>-c_1\log 2M)$$ if it doesn't have a real zero.
(The `$2M$' is necessary so $\log 2M>0$ for $M=1$).
\endproclaim
\demo{Proof}
Assume $\chi$ is non-principal.  From equation (5.9) of \cite{\lo},
$$\frac {L'}L(s,\chi)=B(\chi)+
\sum_{\rho}\left(\frac 1{s-\rho}+\frac 1\rho\right)
-\frac 12\log A(\chi)-\frac{\gamma'_\chi}{\gamma_\chi}(s),$$
where the sum is over all the non-trivial zeroes of $L(s,\chi)$,
$A(\chi)=dM$, $d=\disc(K)$, and $\gamma_\chi(s)=
\left[\pi^{-\frac{s+1}2}\Gamma\left(\frac{s+1}2\right)\right]^b
\left[\pi^{-\frac s2}\Gamma\left(\frac s2\right)\right]^a$ for
nonnegative integers $a$ and $b$ depending on $\chi$ such that $a+b=n$.
The exact dependence, described in \cite{\lo}, is irrelevant here.

The $\log A(\chi)$ term can be bounded because $A(\chi)<dM<d2M)$.

$B(\chi)$ is defined implicitly in \cite{\lo}.
By Lemma 5.1 of that paper, we have
$$B(\chi)=-\text{Re}\sum_{\rho}\frac 1{\rho}.$$

We have from Lemma 5.3 of \cite{\lo} that
$$|\frac{\gamma'_\chi}{\gamma_\chi}(s)|\ll n\log(s+2),$$
where the implied constant is absolute.


Thus $\frac{L'}L(s,\chi)>\sum_{\rho}\text{Re}\frac
1{s-\rho}-c_1\log 2M$, for some $c_1>0$.
We have that $\text{Re}\frac 1{s-\rho}=\frac {s-\text{Re}\rho}
{|s-\rho|^2}>0$, so we 
can omit any part of the sum.  We omit anything but one possible real zero.

Thus
$$\frac{L'}L(s,\chi)>\frac 1{s-\rho}-c_1\log 2M,$$
if $L(s,\chi)$ has a real zero $\rho$, and
$$\frac{L'}L(s,\chi)>-c_1\log 2M,$$
independent of the existence of real zeros.

Now assume $\chi$ is principal.
From (5.9) of \cite{\lo}
$$\frac {L'}L(s,\chi)=\sum_{\rho}\left(\frac 1{s-\rho}+\frac 1\rho\right)
-\frac 1s-\frac 1{s-1}-\frac
12\log
A(\chi) +\frac{\gamma'_\chi}{\gamma_\chi}(s).$$
By the same arguments as in the non-principal case (and the fact that
$\frac 1s<1$), we have that
$$\frac{L'}L(s,\chi)>-\frac 1{s-1}-c_1\log 2M.$$
\enddemo

The following is a version of the Landau-Page Lemma for Dirichlet
$L$-functions over a number field.

\proclaim{Lemma 2.2}
Given a number field $K$,
there is a computable constant $c_2>0$, depending on $K$,
such that for all $T\ge 2$,
there is at most one primitive character $\chi_1$ with modulus $\frak{m}$, $1\le N(\frak{m})<
T$ for which $L(s,\chi_1)$ has a zero $\beta_1+i\gamma_1$ satisfying
$\beta_1\ge 1-c_2/\log T$ and $|\gamma_1|<T$.
\endproclaim
\demo{Proof}
We follow the proof in \cite{\dav, p. 94}.

Lemma 2.3 of \cite{\lmo} (which also appears as
Lemma 3.5 of \cite{\lenpom}) allows us
to consider only real zeros of real non-principal characters.

Let $\chi_1$ and $\chi_2$ be primitive characters mod $\frak{m}_1$ and $\frak{m}_2$,
respectively, where $N(\frak{m}_1)$ and $N(\frak{m}_2)$ are at most $T$.

Consider the expression
$$-\frac{L'}L(s,\chi_0)-\frac{L'}L(s,\chi_1)-\frac{L'}L(s,\chi_2)
-\frac{L'}L(s,\chi_1\chi_2),$$
where $\chi_0$ is the principal character modulo the $\gcd$ of $\frak{m}_1$
and $\frak{m}_2$.  (We define $\gcd(\prod\frak{p}^{m_1(\frak{p})},\prod\frak{p}^{m_2(\frak{p})})
=\prod\frak{p}^{\max(m_1(\frak{p}),m_2(\frak{p}))}$.)
This is equal to 
$$\sum \Lambda(\frak{i})(\chi_0(\frak{i})+\chi_1(\frak{i}))(\chi_0(\frak{i})+\chi_2(\frak{i}))N({\frak i})^{-s}>0,\tag1$$
for $\text{Re} s>1$.

Assume that $L(s,\chi_1)$ and $L(s,\chi_2)$ have real zeros, $\beta_1$ and
$\beta_2$ respectively.
Applying the previous lemma to \thetag{1} for real $s>1$,
$$-\frac{1}{s-\beta_1}-\frac{1}{s-\beta_2}+\frac
1{s-1}+c_3\log T>0,$$
for some $c_3>0$ depending on $K$, but not $T$.
Rearranging,
$$\frac 1{s-\beta_1}+\frac 1{s-\beta_2}<\frac
1{s-1}+c_3\log T.$$


Let $c_2=\frac 1{6c_3}$ and assume that each $\beta_i\ge 1-\frac{c_2}{\log T}$.

Taking $s=1+3c_2/\log T$ gives us
$\frac 1{s-\beta_i}\ge\frac{\log T}{4c_2}$ and $\frac 1{s-1}=
\frac{\log T}{3c_2}$.

We now have that
$$\frac{\log T}{2c_2}<\frac{\log T}{3c_2}+c_3\log T.$$
Simplifying,
$\frac 1{6c_2}<c_3$.  Substituting the value of $c_2$ gives the
desired contradiction.
\enddemo

The following is an analog of the proof in \cite{\agp}.

For each Dirichlet character $\chi$ of a field $K$ and real numbers
$\sigma$, $T$, in the ranges $\frac 12\le\sigma\le 1$, $T\ge 0$, let
$N(\sigma,T,\chi)$ be the number of zeros $s=\beta+i\gamma$ of the
Dirichlet L-function $L(s,\chi)$ inside the box $\sigma\le\beta\le 1$
and $|\gamma|\le T$.
Let $\eusm{A}$ be the set of real numbers $A>2$ for which there exists
a number $C_A\ge 1$, such that for all $\sigma\ge 1-\frac 1A$ and
$T\ge 1$,
$$N(\sigma,T,\frak{m}):=\sum_{\chi\bmod \frak{m}} N(\sigma,T,\chi)\le 
C_A(N(\frak{m})T^n)^{A(1-\sigma)},$$
for all moduli $\frak m$.

Hilano \cite{\hiltwo} has shown that every $A\ge 2890$ is in $\eusm{A}$.
The existence of such an $A$ was first shown by Fogels \cite{\fogels}.

\proclaim{Theorem 2.3}
Let $K$ be a number field.
For any given $\epsilon>0$, there exist
numbers $x_{\epsilon}$,
$\eta_{\epsilon}>0$, and an integer $q_\epsilon(x)$, all depending on
$K$,
 such that whenever $x\ge
x_{\epsilon}$ and $x^{1/2}<y<x$,
$$\left|\sum\Sb
N(\frak{i})<y\\N(\frak{i})\equiv a\bmod q\endSb \Lambda(\frak{i})-
\frac{y}{\phi(q)}\right|\le\epsilon\frac{y}{\phi(q)}$$
for all integers $q$ not divisible by $q_\epsilon(x)$,
with $(a,q)=1$ and $q$ in the range $1\le q\le x^{\eta_{\epsilon}}$.
Furthermore $q_\epsilon(x)>\log x$.
\endproclaim
\demo{Proof}
Let $\rho=3\log(36C_A/\epsilon)$.
Let $\eta_\epsilon=\min(\frac 1{3An},\frac{c_2}{n\rho})$.
We can require $x_\epsilon>\max(e^{4A\rho/\eta_\epsilon},
18(C_A/\epsilon)^{2/\eta_\epsilon})$.


We can deduce the following explicit formula from \cite{\lenpom},
proof of Theorem 3.1:
(equations 3.2, 3.3 and the equation following the ``Hence'' on p. 493).

$$\split&\sum\Sb
N(\frak{a})<y\\N(\frak{a})\equiv a\bmod q\endSb
\Lambda(\frak{a})=\frac{y}{\phi(q)}-\frac 1{\phi(q)}
\sum_{\chi\bmod q}\bar\chi(a)\sum\Sb{L(\beta+i\gamma,\chi)=0}\\\
\beta\ge 1/2, |\gamma|\le T\endSb \frac
{y^{\beta+i\gamma}}{\beta+i\gamma}+\\
&O\left(n\log y+
n\frac{y\log y(\log y+\log dq+\log T)}T+
n\log dq+ny^{\frac 12}\log y(\log q+\log y)\right).\endsplit\tag2$$

We have that $\eta_\epsilon<1/6$, so $\log q<\log y$ and $q<y^{1/3}$.
We take $T=x$, so $y<T<y^2$.


The error term in $\thetag{2}$ is
$$O\left(ny^{1/2}(\log^2 y+\log y\log d)+n\log d\right).$$
Since $d,n$ are fixed, the error is 
$O(y^{1/2}\log^2y)=O(\frac{y^{6/7}}q)$, which is less than
$\frac{\epsilon}3\frac y{\phi(q)}$ for $y$ sufficiently large.

The double sum may be bounded by noting that $|y^{\beta+i\gamma}|=y^\beta$,
and $\beta+i\gamma\ge\sqrt{1/4+\gamma^2}\ge (1+|\gamma|)/3$.

Thus
$$
\left|\sum\Sb
N(\frak{a})<y\\N(\frak{a})\equiv 1\bmod q\endSb
\Lambda(\frak{a})-\frac{y}{\phi(q)}\right|\le\frac 3{\phi(q)}
\sum_{\chi\bmod q}\sum\Sb{L(\beta+i\gamma,\chi)=0}\\\
\beta\ge 1/2, |\gamma|\le x\endSb\frac{y^\beta}{1+|\gamma|}
+\frac\epsilon 3\frac{y}{\phi(q)}.\tag3$$

Write $\sum_\sigma^{\alpha}$ for a sum over all zeros of
$\beta+i\gamma$ of $L(s,\chi)$ and over all characters $\chi \bmod q$
where $\sigma\le\beta<\alpha$ and $|\gamma|<x$.  (Each $\beta+i\gamma$
is counted with multiplicity equal to the number of those L-functions
for which it is a zero.)  To estimate the double sum in \thetag{3}
we use the upper bounds $y^\beta\le y^{1-1/(2An)}$ for $\beta\le
1-1/(2An)$, and $y^\beta\le y$ for $\tau\le\beta\le 1$, where $\tau=1-\rho/\log
x$.  In the range
$1-1/(2An)\le\beta\le\tau$, we use the identity $y^\beta=y^{1-1/(2An)}+\log y
\int_{1-1/(2An)}^\beta y^\sigma d\sigma$.

Therefore, the double sum in \thetag{3} is at most
$$\split&\sum_{1/2}^\tau \frac{y^{1-1/(2An)}}{1+|\gamma|}+\log y\sum_{1-1/(2An)}^\tau
\frac 1{1+|\gamma|}\int_{1-1/(2An)}^\beta y^{\sigma} d\sigma+y
\sum_\tau^1 \frac y{1+|\gamma|}\\
&\le y^{1-1/(2An)}\sum^1_{1/2}\frac 1{1+|\gamma|}+\log
y\int_{1-1/(2An)}^\tau y^\sigma\left(\sum_\sigma^1 \frac 1{1+|\gamma|}\right)d\sigma
+y\sum_\tau^1 \frac 1{1+|\gamma|}.\endsplit\tag4$$

For $\sigma\ge 1/2$, we have, by partial summation,
$$\sum_\sigma^1\frac 1{1+|\gamma|}\le N(\sigma,2,q)+\frac{N(\sigma,x,q)}x
+\int_2^{x}\frac{N(\sigma,t,q)}{t^2} dt.$$

By \cite{\hilone}, %I could use a better citation for this.
$N(1/2,t,q)<c_4nq^nt\log qt$.  For $t$ in the
range $2\le t\le x$, we have $N(1/2,t,q)/t\le c_4nq^n\log qx$.

Applying this,
$$\sum_{1/2}^1 \frac{y^{1-\frac1{2An}}}{1+|\gamma|}\le
2c_4nq^ny^{1-\frac1{2An}}\log qx\left(2+\int_2^x\frac{dt}t\right)\le
5c_4nq^ny^{1-\frac1{2An}}\log^2 qx.$$
Since we insist that $\eta_\epsilon<\frac 1{8An^2}$, the first term in
\thetag{4} is
$O(y^{1-1/(3An)})$, which is $<\frac{\epsilon}{18}y$ for $y$
sufficiently large.

If $\sigma\ge 1-1/(2An)$, then $An(1-\sigma)\le 1/2$, so that for any $t$ in
the range $1\le t\le x$, the estimate from \cite{\hiltwo} shows that
$N(\sigma,t,d)\le C_Aq^{An(1-\sigma)}t^{1/2}$.  We deduce that
$$\sum_\sigma^1\frac 1{1+|\gamma|} \le C_A q^{An(1-\sigma)}
\left(3+\int_2^{x}\frac{dt}{t^{3/2}}\right)\le 5C_Aq^{An(1-\sigma)}.$$

Using the bound above, the middle term in \thetag{4} is 
$$\split&\le 5C_Aq^{An}\log y\int_{1-1/(2An)}^\tau \left(\frac
y{q^{An}}\right)^\sigma d\sigma\\
&\le 5C_Aq^{An}\frac{\log y}{log(y/q^{An})}\frac y{q^{An}}
\left(\frac y{q^{An}}\right)^{-(1-\tau)}.\endsplit$$

We have that 
$q^{An}<x^{An\eta}<y^{1/3}$, so $\frac{\log y}{\log (y/q^{An})}< 3/2$.
Also, $\left(\frac y{q^{An}}\right)^{-(1-\tau)}=\left(\frac
y{q^{An}}\right)^{-\rho/\log x}<e^{-\frac 23\log y\rho/\log
x}<e^{\frac 13\rho}$.


Thus the middle term in \thetag{4} is
$$\le 4C_Aye^{-\frac 13\rho}.$$

And by the way we chose $\rho$, that is $\le\frac{\epsilon}9 y$.

We apply Lemma 2.2 with $T=x^{n\eta_\epsilon}$ and call
the exceptional modulus $q_\epsilon(x)$.  Then for all moduli
less than $x^{\eta_\epsilon}$ and not divisible by $q_\epsilon(x)$, the
$L$-function has no zeros $\beta+i\gamma$ with 
$\beta\ge 1-\rho/\log x$ and $|\gamma|<x^{n\eta_\epsilon}$.

So the third sum above is
$$y\sum^1_\tau \frac 1{1+|\gamma|}\le y\frac{N(\tau,x,q)}{x^{n\eta_\epsilon}}
\le C_Ay(q^nx^n)^{A(1-\tau)}/x^{n\eta_\epsilon} < C_Ayx^{2An\rho/\log x}/x^{n\eta_\epsilon}.$$
This is less than
$C_Ayx^{-\eta_\epsilon/2}$, by our choice of $x$.
Also by our choice of $x$, this is less  than
$C_Ay{(18C_A/\epsilon)^{2/\eta_\epsilon}}^{-\eta_\epsilon/2}=\epsilon y/9$.
Putting these bounds together, we get the desired theorem.
\enddemo

Theorem 2.1 of {\cite{\agp}} shows, essentially, that the number of primes in an
arithmetic progression less than $x$ cannot be too far away from what you expect.
Furthermore, it shows this for ``most'' moduli up to $x^{\frac 5{12}}$.
Our replacement is the following

\proclaim{Theorem 2.4} 
Let $f(t)\in\Bbb{Z}[t]$ be a monic polynomial with splitting field
$K$, $[K:\Bbb{Q}]=n$.
Then we have a real numbers $x_{1/3},\eta_{1/3}>0$
and an integer $q_{1/3}(x)>\log
x$, depending on $K$ as described in Theorem 2.3, such that the
following statement holds.
If $q\le x^{\eta_{1/3}}$, $\gcd(a,q)=1$, $q_{1/3}(x)\nmid q$, $x\ge
x_{1/3}$ and $x^{1/2}<y<x$, then the number of primes $p<y$
that are $a \bmod q$ and such that  $f(t)$ splits into linear factors
mod $p$
(equivalently, $p$ splits completely in $K$)
is at least $\frac{1}{2\phi(q)n}\pi(x)$.  
\endproclaim
\demo{Proof}
The previous theorem gives that
$$\sum\Sb
N(\frak{a})<y\\N(\frak{a})\equiv a\bmod q\endSb
\Lambda(\frak{a})\le
\frac{(2/3)y}{\phi(q)}.$$

The sum contains two types of things we don't want.  The first is
prime ideal powers.  Those can be dispensed of in the usual way.  The second
is primes that don't split completely.  For primes that do not split
completely, we have $N(p)=p^k$, for $k>1$, so they can be dealt with in the same way
as prime powers.
We pass to the estimate on the number of primes by standard techniques
(\cite{\dav}, p. 112).
\enddemo

Henceforth, let $\eta=\eta_{1/3}$ and $q(x)=q_{1/3}(x)$.

\head{\S 3 Prachar's Theorem Revisited Revisited}
\endhead
We use the following variant of Theorem 3.1 of \cite{\agp}.

\proclaim{Theorem 3.1}
If $L$ is a squarefree number not divisible
by any prime exceeding $x^{\frac{1-\eta}{2}}$ and for which
$\sum_{\text{prime}\ q|L}\frac 1q\le\frac{1-\eta}{32n}$, then there is a
positive integer $k\le x^{1-\eta}$ with $(k,L)=1$ such that

$$\#\{d|L:dk+1\le x, dk+1 \text{ is prime, splits fully in } K\}\ge \frac
{\#\{d|L: 1\le d\le x^{\eta}\}}{8n\log x}.$$
\endproclaim
\demo{Proof}
Let $\pi_K(x;q)$ denote the number of primes less than $x$
that are $1 \bmod q$ and split completely in $K$.

From Theorem 2.4, we see that for each divisor of $L$ with $1\le d\le
\smash{x^{\eta}}$ and $(d,q(x))=1$,
$$\pi_K(dx^{1-\eta};d)\ge \frac{\pi(dx^{1-\eta})}{2n\phi(d)}\ge
\frac{dx^{1-\eta}}{2n\phi(d)\log x}.$$


Since any prime factor $q$ of $L$ is at most $x^{\frac{1-\eta}2}$, we
can use Montgomery and Vaughan's explicit version of the
Brun-Titchmarsh theorem to get 
$$\pi_K(dx^{1-\eta};dq)\le\pi(dx^{1-\eta};dq,1)\le\frac 8{q(1-\eta)}
\frac{dx^{1-\eta}}{\phi(d)\log{x}}.$$

So the number of primes $p\le dx^{1-\eta}$ with $p\equiv 1\bmod d$
and $(\frac{p-1}d,L)=1$ that split completely is at least
$$\pi_K(dx^{1-\eta};d)-\sum_{\text{prime } q|L}\pi_K(dx^{1-\eta};dq)$$
$$\ge\left(\frac 1{2n}-\frac 8{1-\eta}\sum_{\text{prime }q|L}\frac 1q\right)
\frac{dx^{1-\eta}}{\phi(d)\log{x}}\ge\frac {x^{1-\eta}}{4n\log
x},$$ for any divisor not divisible by$q(x)$.  But at least half of the
divisors of $L$ will not be divisible by $q(x)$.

Thus we have at least
$$\frac{x^{1-\eta}}{8n\log x}\#\{d|L:1\le d\le x^{\eta}\}$$
pairs $(p,d)$ where $p\le d^{1-\eta}$ is prime, $p\equiv 1\bmod
d$, $p$ splits completely in $K$, $(\frac{p-1}d,L)=1$, $d|L$ and $1\le d\le
x^\eta$.  Each such pair $(p,d)$ corresponds to an integer $\frac
{p-1}d\le x^{1-\eta}$ this is coprime to $L$, and so there is at least
one integer $k\le x^{1-\eta}$ with $(k,L)=1$ such that $k$ has at least 
$$\frac 1{8n\log x}\#\{d|L: 1\le d\le x^\eta\}$$
representations as $\frac{p-1}d$ with $(p,d)$ as above. Thus for this integer $k$ we have
$\#\{d|L:dk+1\le x, dk+1\text{ prime, split completely in $K$}\}\ge \frac 1{8n\log x}\#\{d|L: 1\le d\le x^\eta\}$.
\enddemo

\head{\S 4 Infinitely Many Frobenius Pseudoprimes}
\endhead
The results from Section 1 of \cite{\agp} (dealing
with subsequence products in a group) can be used without
modification.

\proclaim{Theorem 1.1 of \cite{\agp}}
If $G$ is a finite abelian group and $m$ is the maximal order of an
element in $G$, then $n(G)<m(1+\log{(\frac{|G|}m)})$.  ($n(G)$ is the
length of the longest sequence of (not necessarily distinct) elements
of $G$ for which no non-empty subsequence has product the identity.)
\endproclaim

As reported in \cite{\agp}, this theorem is due to van Emde Boas and Kruyswijk,
and to Meshulam.

\proclaim{Proposition 1.2 of \cite{\agp}}
Let G be a finite abelian group, and let $r>t>n=n(G)$ be integers.
Then any sequence of $r$ elements of G contains at least
$\dfrac{{r\choose t}}{{r\choose n}}$ distinct
subsequences of length at most $t$ and at least $t-n$, whose product
is the identity.
\endproclaim


\proclaim{Theorem 4.1}
Let $K$ be a number field, and let $\eta$ be the positive real number
depending on $K$ defined above.
For any $\epsilon>0$,
the number of Carmichael-Frobenius numbers less than $x$,
with respect to a number field $K$,
is at least $x^{\eta/3-\epsilon}$, for
sufficiently large $x$, depending on $\epsilon$ and $K$.
\endproclaim
\demo{Proof}
Let $\eusm Q$ be the set of primes $q\in(\frac{y^3}{\log y},y^3]$ for
which $q-1$ is free of prime factors exceeding $y$.  As reported in
\cite{\agp}, Friedlander has proved
that there is a constant $C>0$  for which 
$$|\eusm Q|\ge C\frac{y^3}{\log{y}}$$ for all sufficiently large $y$.
Let $L$ be the product of the primes $q\in \eusm Q$; then
$$\log L\le|\eusm Q|\log{(y^3)}\le\pi(y^3)\log{(y^3)}\le 2y^3,$$ for
all large $y$.  Now $\lambda(L)$ is the least common multiple of the
number $q-1$ for those primes $q$ that divide $L$.  Since each such
$q-1$ is free of prime factors exceeding $y$, we know that if the
prime power $p^a$ divides $\lambda(L)$ then $p\le y$ and $p^a\le
y^3$.  We let
$p^{a_p}$ be the largest power of $p$ with $p^{a_p}\le y^3$, then
$$\lambda(L)\le \prod_{p\le y} p^{a_p}\le\prod_{p\le y} y^3 = 
y^{3\pi(y)}\le e^{6y}$$ for all large $y$.

Let $G$ be the group $(\Bbb{Z}/L\Bbb{Z})^*$.  From Theorem 1.1 and the
above equations,
$$n(G)<\lambda(L)\left(1+\log{\frac{\phi(L)}{\lambda(L)}}\right)\le
\lambda(L)(1+\log L)\le e^{9y}$$ for all large $y$.

We can force $y$ large enough so that $\sum \frac 1q\le
\frac{1-B}{32n}$ as needed to apply Theorem
3.1.  Let $\delta=\frac{3\epsilon}{8n\eta}$, and let
$x=e^{y^{1+\delta}}$.
Then, for $y$ large enough, there is an integer $k$ coprime to
$L$ for which the set $\eusm P$ of primes $p\le x$ with $p=dk+1$ for
some divisor $d$ of $L$, and that split in $K$, satisfies 
$$|\eusm P|\ge\frac{\#\{d|L:1\le d\le x^{\eta}\}}{8n\log x}.$$
The product of any 
$$u:=\left[\frac{\log\left(x^{\eta}\right)}{\log{y^3}}\right]=
\left[\frac{\eta\log x}{\theta\log y}\right]$$
distinct prime factors of $L$ is a divisor $d$ of $L$ with $d\le
x^\eta$.  We deduce from above that
$$\#\{d|L:1\le d\le x^\eta\}\ge{{\omega(L)}\choose u}\ge\left(\frac
{\omega(L)}{u}\right)^u$$
$$\ge\left(\frac{Cy^3}{\eta\log x}\right)^u=\left(\frac
C\eta y^{2-\delta}\right)^u.$$

We notice that $\frac{(2-\delta)\eta}3=\frac{2\eta}3-\frac\epsilon 4$.
So for all sufficiently large values of $y$,
$$|\eusm P|\ge\frac{\left(\frac C\eta y^{2-\delta}\right)^u}{8n\log x}\ge
x^{\frac{2\eta}3-\frac\epsilon 3}.$$

Take $\eusm P'=\eusm P\backslash\eusm Q$.  Since $|\eusm Q|\le y^3$,
we have that $|\eusm P'|\ge x^{\frac{2\eta}3-\frac\epsilon 2}$, for all
sufficiently large values of $y$.  

We may view $\eusm P'$ as a subset of the group
$G=(\Bbb{Z}/L\Bbb{Z})^*$ by considering the residue class of each
$p\in\eusm P' \bmod L$.  If $\eusm S$ is a subset of $\eusm P'$
that contains more than one element and if
$$\prod(\eusm S):=\prod_{p\in\eusm S}p\equiv 1\bmod L,$$
then $\prod(\eusm S)$ is a Carmichael number all of whose prime
factors split completely in $K$.  Thus it is a Frobenius pseudoprime.

Let $t=e^{y^{\frac{1+\delta}2}}$.  Then, by Proposition 1.2, we see
that the number of Frobenius pseudoprimes of the form $\prod(\eusm S)$,
where $\eusm S\subset\eusm P'$ and $|\eusm S|\le t$, is at least 
$$\frac{{{|\eusm P'|}\choose{[t]}}}{{{|\eusm P'|}\choose {n(G)}}} \ge
\frac{\left(\frac{|\eusm P'|}{[t]}\right)^{[t]}}{|\eusm P'|^{n(G)}} \ge
\left(x^{\frac{2\eta}3-\frac\epsilon 2}\right)^{[t]-n(G)}[t]^{-[t]} \ge
x^{t\left(\frac{2\eta}3-\epsilon\right)}$$ for all sufficiently large
values of $y$.  We note that we have formed each Frobenius
pseudoprime
$\prod(\eusm P)\le x^t$.  Thus for $X=x^t$ we have the number of
Frobenius pseudoprimes $\le x$ is at least
$X^{\frac{2\eta}3-\epsilon}$ for all sufficiently large values of $X$.
Since $y$ can be uniquely determined from $X$, 
we're done.
\enddemo

\newpage

\Refs
\ref\no\as
\by W. W. Adams and D. Shanks
\paper Strong primality tests that are not sufficient
\jour Math. Comp.
\vol 39
\yr 1982
\pages 255--300
\endref

\ref\no\agp
\by W. R. Alford, Andrew Granville and Carl Pomerance
\paper There are infinitely many Carmichael numbers
\jour Annals of Mathematics
\yr 1994
\vol 140
\pages 703--722
\endref

\ref\no\dav
\by Harold Davenport
\book Multiplicative Number Theory
\bookinfo Second Edition
\yr 1980
\publ Springer-Verlag
\publaddr New York
\endref

\ref\no\fogels
\by E. Fogels
\paper On the zeros of $L$-functions
\jour Acta Arith.
\vol 11
\yr 1965
\pages 67--96
\endref

\ref\no\meone
\by J. Grantham
\paper Frobenius Pseudoprimes
\endref

\ref\no\gurak
\by S. Gurak
\paper Pseudoprimes for higher-order linear recurrence sequences
\jour Math. Comp.
\yr 1990
\vol 55
\pages 783--813
\endref


\ref\no\hilone
\by Teluhiko Hilano
\paper On the zeros of Hecke's $L$-functions
\jour Sci. Papers College Gen. Ed. Univ. Tokyo
\vol 24
\yr 1974
\pages 8--24
\endref

\ref\no\hiltwo
\by Teluhiko Hilano
\paper On the zeros of Heck's {\rm [sic]} $L$-functions
\jour Proc. Japan Acad.
\vol 50
\yr 1974
\pages 23--28
\endref

\ref\no\lmo
\by J. C. Lagarias, H.L. Montgomery, and A.M. Odlyzko
\paper A bound for the least prime ideal in the Chebotarev density
theorem
\jour Invent. Math.
\vol 54
\yr 1979
\pages 271--296
\endref

\ref\no\lo
\by J.C. Lagarias and A.M. Odlyzko
\paper Effective versions of the Chebotarev density theorem
\inbook Algebraic Number Fields: $L$-functions and Galois Properties
\ed A. Fr\"olich
\publ Academic Press
\publaddr London
\yr 1977
\pages 409--464
\endref

\ref\no\lenpom
\by H.W. Lenstra, Jr. and Carl Pomerance
\paper A rigorous time bound for factoring numbers
\jour J. Amer. Math. Soc.
\vol 5
\yr 1992
\pages 483--516
\endref

\ref\no\sze
\by G. Szekeres
\paper Higher order pseudoprimes in primality testing
\inbook Combinatorics, Paul Erd\H os is eighty
\bookinfo Bolyai Soc. Math. Stud.
\publ J\'anos Bolyai Math Soc.
\publaddr Budapest
\yr 1996
\vol 2
\pages 451--458
\endref
\endRefs
\enddocument