\documentstyle{article}
\title{\Large Chaos, Elliptic Curves and All That} 
\author{Matthew Fletcher
\thanks{The work of the first author was supported
by the SERC}\\
\and
Geoff C. Smith\\
School of Mathematical Sciences, University of Bath, Bath BA2 7AY, England
}
\date{}
\renewcommand{\baselinestretch}{1.5}
\begin{document}
\maketitle

\parskip=2ex
\parindent=0pt
\newcommand{\bs}{\vskip 2ex \noindent}
\newcommand{\ms}{\vskip 1ex \noindent}
\newcommand{\zn}{\mbox{${\bf Z}^n_2$} \/}
\newcommand{\znm}{\mbox{${\bf Z}^{n-1}_2$}}
\newcommand{\azn}{\mbox{${\bf Z}^n_2 \rightarrow {\bf Z}_2$}}
\newcommand{\aznm}{\mbox{$\znm \rightarrow {\bf Z}_2$}}
\newcommand{\ux}{\mbox{$\underline{x}$}}
\newcommand{\uci}{\mbox{$\underline{c}_{i}$}}
\newcommand{\xzn}{\mbox{$\underline{x} \in \zn $}}
\newcommand{\dfdx}{\mbox{$\displaystyle \frac {\partial f}{\partial x_{i} }$}} 
\newcommand{\dgdx}{\mbox{$\displaystyle \frac {\partial g}{\partial x_{i} }$}} 
\newcommand{\fai}{\mbox{$\forall i:1 \leq i \leq n$}}
\newcommand{\vn}{\mbox{${\bf V}_n$}}
\newcommand{\vi}{\mbox{$\vert$ I $\vert$}}
\newcommand{\sip}{\mbox{$\displaystyle \sum_{i \in \hbox{I}'} x_i$}}
\newcommand{\twon}{\mbox{$\displaystyle 2^{-2^{n-1}}{2^{n-1}\choose2^{n-2}} $}}
\newcommand{\zp}{\mbox{${\bf Z}_p^{\ast}$} \/}
\begin{center} {\underline {\bf 1. \quad Introduction}} \end{center}

The iteration of simple functions can rapidly produce chaotic 
behaviour in the fields of real and complex numbers.
In this paper we examine polynomial iteration in the integers modulo $N$
and examine the resulting structures. 
For each point $c$ in the complex plane the map $f_c : {\cal C} \rightarrow
{\cal C}$ is defined by $f_c(z) = z^2 + c$. The Mandelbrot Set is defined
to be those points $c \in {\cal C}$ for which the sequence $c, f_c(c), 
f_c(f_c(c)), \ldots$ does not diverge. See [1] for further details. 
By considering similar sequences in
the integers modulo $N$, and amending the concept of divergence, we obtain
finite analogues of the Mandelbrot Set when $N$ is the product
of certain primes. Curiously enough, we are immediately drawn to the
application of results concerning elliptic curves defined over finite
fields. So far we have only dealt with quadratic iteration. Iteration by
higher degree polynomial functions remains an open area, the arithmetic
of higher genus curves being much more complex.

\begin{center} {\underline {\bf 2. \quad Definitions}} \end{center}

Let ${\bf Z}_N$ be the ring of integers modulo $N$. 
For fixed $N > 0$, define $f_c : {\bf Z}_N \rightarrow {\bf Z}_N$ by
$$f_c (x) = x^2 + c \bmod N \qquad \mbox{for } 0 \leq c < N . $$
Define $s_c$ to be the infinite sequence $ < f_c(c) , f_c(f_c(c)) , \ldots , 
f_c^n(c) , \ldots > $ , where $f_c^n$ denotes $n$ applications of $f_c$.
After at most $N$ iterations, the iterated map must repeat a previously
encountered value, and the sequence will enter a recurring loop. We
define $k$ to be the smallest $k$ such that $f_c^k(c) = f_c^l(c) \quad
k > l \geq 1$. Then we can write $$ s_c= < f_c(c) , f_c^2(c) , \ldots , 
f_c^{l-1} > \frown < f_c^l(c), \ldots , f_c^{k-1}(c) >^{\infty} $$
where $\frown$ denotes sequence concatenation, and $< \ldots >^{\infty}$ 
denotes
the sequence repeated {\em ad infinitum}.
If $l=1$ then we can write $s_c=<f_c(c), \ldots , f_c^{k-1}(c) >^{\infty}$ and
say that $s_c$ is {\em cyclic}, with fundamental period $(k-1)$.
If $s_c$ is cyclic for all $0 \le c \le N$ then we say that $N$ is
{\em perfectly cyclic}.

\begin{center} {\underline {\bf 3. \quad Preliminary Results}} \end{center}

{\it Lemma 1:} \hspace{3mm} 
If $N$ is perfectly cyclic and $M$ divides $N$, then $M$ is perfectly cyclic.

{\it Proof:} \hspace{3mm}
For all $c$, $0 \le c < N$, there exists $k_c$ such that $f_c^{k_c}(c)=
f_c(c) \bmod N$. Therefore, $f_c^{k_c}(c) = f_c(c) \bmod M$, since $M$
divides $N$. $f_c(c)$ must be the first repeated value, for if some other
value was first repeated, then the loop could not contain $f_c(c) \bmod M$
-- a contradiction. 

{\it Lemma 2:} \hspace{3mm}
2, 3, and 5 are perfectly cyclic.

{\it Proof:} \hspace{3mm} by direct calculation.
 
\begin{center} {\underline {\bf 4. Quadratic Residues and Non--Residues}}
\end{center}

For a full treatment see [2].
We write ${\bf Z}_p^{\ast}$ for the group of units of the integers modulo $p$.
An element $x \in {\bf Z}_p^{\ast}$ is
a quadratic residue if $x=y^2 \bmod p$ for some $y \in {\bf Z}_p^{\ast}$,
otherwise $x$ is a quadratic non--residue. The quadratic residues form
a normal subgroup of index 2 in the multiplicative group ${\bf Z}_p^{\ast}$,
and so we have the following rules of multiplication:

Two quadratic residues multiplied together give a 
quadratic residue. \\ Two quadratic non--residues multiplied together give
a quadratic residue. \\ A quadratic residue and a non--residue multiplied
together give a quadratic non--residue.

The Legendre symbol of $x \bmod p$, 
written $(x \,\vert \, p)$, is defined for $p$ odd
as 
$$ (x \,\vert \, p) = \left\{ \begin{array}{ll}
	1 & \mbox{if x is a quadratic residue} \\
	-1 & \mbox{if x is a quadratic non--residue}
\end{array} \right. $$
for $p$ prime, and $x \in {\bf Z}_p^{\ast}$.

For $p$ odd, precisely half of the numbers in ${\bf Z}_p^{\ast}$ are quadratic residues,
namely $1^2 \bmod p, 2^2 \bmod p, \ldots ,$ $((p-1)/2)^2 \bmod p$. 

\begin{center} {\underline {\bf 5. \quad Determination of perfectly cyclic numbers}} \end{center}

{\it Lemma 3:} \hspace{3mm}
Let $p$ be an odd prime. If there exists $c \, (0 < c < p)$ such that 
$-c$ and $-2c$ are both quadratic non-residues $\bmod \, p$ then
$s_c$ is not cyclic, and hence $p$ is not perfectly cyclic.

{\it Proof:} \hspace{3mm}
Consider the repeating loop in $s_c$. Each value, $v$, in the loop
must have a predecessor, $pre(v)$, such that $(pre(v)^2+c) \bmod p=v$.
For $s_c$ to be cyclic, $f_c(c)=(c^2+c) \bmod p$ must be present.
There are only two possibilities for $pre(c^2+c)$, namely $+c$ and $-c$.
If $pre(c^2+c)=+c$, then $pre(+c)=0$ and $pre(0)=\pm \, \root \of{-c}$.
If $pre(c^2+c)=-c$, then $pre(-c)=\pm \, \root \of{-2c}$. So if $-c$ and $-2c$
are both quadratic non-residues, the loop cannot contain $f_c(c)$. Hence,
$s_c$ could not be cyclic.

{\it Lemma 4:} \hspace{3mm}
Let $p$ be an odd prime. If $2$ is a quadratic residue $\bmod \, p$, then
$p$ is not perfectly cyclic.

{\it Proof:} \hspace{3mm}
Consider the $(p-1)$ ordered pairs $(1,2), (2,4), \ldots, (p-1,2p-2)$.
Since precisely half the numbers in ${\bf Z}_p^{\ast}$ are quadratic residues,
the average number of quadratic residues per pair is precisely 1. Now
take any quadratic residue $\bmod \, p$, $x$ say, and consider the pair
$(x,2x)$. Since $x$ and $2$ are both quadratic residues, so is $2x$, and
the pair contains $2$ quadratic residues. Therefore there must exist at
least one pair $(y,2y)$ such that $y$ and $2y$ are both quadratic
non-residues, otherwise the average number of quadratic residues per pair
could not be $1$. Take $c=-y$ and apply Lemma 3.

We can determine for which odd primes $2$ is a quadratic residue by applying
the well known result (see, for example, [2]),
$$ (2 \,\vert \, p) = (-1)^{(p^2-1)/8} $$
Let $p=8q+r$, where $r \in \{1,3,5,7\}$, then $(2 \,\vert \, p)=1$ if and only if,
$r=1$ or $r=7$. 

So we have proved
that no primes of the form $8q+1, 8q+7$ can be perfectly cyclic. Now we wish
to prove that no primes of the form $8q+3, 8q+5$ can be perfectly cyclic --
except, of course, for $3$ and $5$.

{\it Lemma 5:} \hspace{3mm}
Let $p$ be an odd prime such that $2$ is a quadratic non--residue $\bmod \, p$.
If there exists a $y \in {\bf Z}_p^{\ast}$ such that $y^2-y$ and $y^2+y$ are
both quadratic non-residues then $p$ is not perfectly cyclic.

{\it Proof:} \hspace{3mm}
Assume, for contradiction, that the hypotheses are satisfied but that
$s_c$ is perfectly cyclic. Let $c= -y^2 \bmod p$. From Lemma 3, we
know that at least one of $-c$ and $-2c$ must be a quadratic residue
for $s_c$ to be cyclic. As $2$ is a quadratic non-residue, only one
of them can be a quadratic residue, and it is clearly $-c$. 
Therefore, $pre(0)= \pm \, \root \of
{-c}= \pm y$. Notice that $pre(+y)= \pm \, \root \of {+y -c}= \pm \, \root \of {y^2+y}$,
and $pre(-y)= \pm \, \root \of {-y -c} = \pm \, \root \of {y^2-y}$. We
know that $y^2-y$ and $y^2+y$ are both quadratic non-residues, therefore
the loop cannot continue back any further and so $s_c$ cannot be cyclic.
We have a contradiction so the proof is complete. 

{\it Lemma 6:} \hspace{3mm}
Let $p$ be a prime greater than $5$ such that $2$ is a quadratic
non--residue $\bmod \, p$. The prime $p$ is not perfectly cyclic.

{\it Proof:} \hspace{3mm}
It will suffice to prove there exists a $y$ such that $y^2-y$ and $y^2+y$ are
both quadratic non-residues $\bmod \, p$, and then apply Lemma 5.
Suppose, for a contradiction,  that no such $y$ exists. That is, for
every $y \in {\bf Z}_p^{\ast}$ at least one of $y^2-y$ and $y^2+y$ is a 
quadratic residue.
$$
\begin{array}{ccc}
y & y^2-y & y^2+y \\
2 & 2 & 6 \\
3 & 6 & 12 \\
4 & 12 & 20 \\
5 & 20 & 30 \\
9 & 72 & 90
\end{array} $$
Recall that $2$ is a quadratic non--residue, therefore, from $y=2$, it
follows that $6$ is a 
quadratic residue. Now $12=2\times 6$ so $12$ is a quadratic non--residue.
Therefore, 
from the case $y=4$, we see that $20$ is a
quadratic residue. However, $20=2^2\times 5$, so $5$ is a quadratic residue.
Now $72=6^2\times 2$,
so $72$ is a quadratic non--residue. Therefore, from the case $y=9$, 
we deduce that $90$ is a 
quadratic residue. Notice that $90=3^2\times 10$, so $10$ is a quadratic residue, but
$10=2\times 5$, therefore $5$ is a quadratic non--residue. Thus we have deduced
the contradiction that $5$ is both a quadratic reside and non--residue,
therefore the assumption that no such $y$ exists must be false. Apply
Lemma 5 to complete the proof. Note that this proof has assumed that
$2,6,12,20,30,72,90 \in {\bf Z}_p^{\ast}$, and so does not apply to the primes
$p=3$ and $p=5$.

Combining Lemmas 2, 4 and 6 we obtain

{\it Theorem 1: } \hspace{3mm} 
The numbers 2, 3 and 5 are the only perfectly cyclic primes.

We know that only numbers which have prime factors 2, 3, and 5
can be perfectly cyclic, from Lemma 1. 
If we can find a power of 2, 3, or 5, which is not
perfectly cyclic, then no perfectly cyclic number can have this power, or
any higher power as a factor. By direct calculation we find that 
$8$ is
perfectly cyclic, but $16$ is not; $9$ is perfectly cyclic, but $27$ is not;
and $25$ is perfectly cyclic, but $125$ is not. These results prove:

{\it Lemma 7:} \hspace{3mm}
Only numbers of the form $2^a \times 3^b \times 5^c$ where $ 0 \le a \le 3, 
0 \le b \le 2, 0 \le c \le 2$ can be perfectly cyclic.

We can verify that $2^3 \times 3^2 \times 5^2 = 1800$ 
is, in fact, perfectly cyclic and therefore, by Lemma 1, all its divisors are.
Theorem 3, below, also shows that $1800$ is perfectly cyclic.
Thus we have a complete determination of perfectly cyclic numbers.

{\it Theorem 2:} \hspace{3mm}
The set of perfectly cyclic numbers is precisely  $$ \{ 2^a \times 3^b \times
5^c \mbox{ such that } 0 \le a \le 3, 0 \le b, c \le 2 \} $$ 
$$ = \{ 1, 2, 3, 4, 6, 8, 9, 10, 12, 15, 18, 20, 24, 25, 30, 36, 40, 45, 50, $$
$$ 60, 72, 75, 90, 100, 
120, 150, 180, 200, 225, 300, 360, 450, 600, 900, 1800 \} .$$ 

\begin{center} {\underline {\bf 6. \quad General quadratic polynomials}}
\end{center}

Having determined the perfectly cyclic numbers for the maps $x \rightarrow
x^2+c$, we would like to generalise to quadratic maps of the
form $x \rightarrow ax^2+bx+c$, where $a, b$ are integers, $a \neq 0$.
Let us call
such perfectly cyclic numbers: \lq perfectly cyclic with respect to $ax^2+bx$
\rq. So the original perfectly cyclic numbers become perfectly cyclic with
respect to $x^2$. 

When $a=0 \bmod p$, the map $f_c(x)=ax^2+bx+c \bmod p$ becomes linear, and therefore always 
invertible, so for a given $ax^2+bx$ all primes which divide $a$ are 
automatically perfectly cyclic with respect to $ax^2+bx$. We intend to
show that apart from $2$, $3$, $5$, $7$ (under certain conditions),
and primes which divide $a$, 
there are no perfectly cyclic primes with respect to $ax^2+bx$.
    
Let $f_c:x \rightarrow ax^2+bx+c \, \bmod \, M, \, 0 \leq c < M$,
$g_c:x \rightarrow ax^2+bx+c \, \bmod \, N, \, 0 \leq c < M$,
and $h_c:x \rightarrow ax^2+bx+c \, \bmod \, MN, \, 0 \leq c < MN$.

{\it Lemma 8:} \hspace{3mm}
$h_c^i(c) \bmod M = f_{c \bmod M}^i(c \bmod M) \quad \mbox{
for all positive $i$.}$

{\it Proof:} \hspace{3mm}
Let $c'=c \bmod M$, and $c''=c \bmod N$.
$h_c(y) \bmod M = (ay^2 + by +c \bmod MN) \bmod M =
(a(y \bmod M)^2 + b(y \bmod M) +c) \bmod M $
$= f_{c'}(y \bmod M) $ for all $0 \leq y < MN$.
Now we can prove the lemma by induction on $i$. 

{\it Base Case:} $(i=1)$ 
$$ h_c(c) \bmod M = f_{c'}(c') \qquad \mbox{from above, with }c=y$$

{\it Inductive Step:} \hspace{3mm}
Suppose Lemma is true for some $I$, $I > 0$, then
$$ h_c^I(c) \bmod M = f_{c'}^I(c'), $$
$$h_c^{I+1}(c) \bmod M = h_c(h_c^I(c)) \bmod M = f_{c'}(
h_c^I(c) \bmod M)$$
$$= f_{c'}(f_{c'}^I(c')) = f_{c'}^{I+1}(c').$$
Hence, by induction, we are done.

Similarly,
$$h_c^i(c) \bmod N = g_{c''}^i(c'') 
\quad \mbox{for all } i, i \geq 1.$$

{\it Lemma 9:} \hspace{3mm}
If $M$ and $N$ are coprime, perfectly cyclic numbers with respect to 
$ax^2+bx$, then $MN$ is perfectly cyclic with respect to $ax^2+bx$.

{\it Proof:} \hspace{3mm}
With $f,g,h,c',c''$ defined as above, pick an arbitrary $c, 0 \le c < MN$,
and let $k$ and $l$ be the smallest $k,l > 1$ such that $f^k_{c'}(c')=c'$
and $g^l_{c''}(c'')=c''$, and consider 
$$h_c^{\lambda (k-1)(l-1) +1} \qquad \mbox{$\lambda$ an integer}$$
 $$h_c^{\lambda (k-1)(l-1) +1} \bmod M = f_{c'}^{\lambda (k-1)(l-1)+1}(c')
=f_{c'}(c')$$
 $$h_c^{\lambda (k-1)(l-1) +1} \bmod N= g_{c''}^{\lambda (k-1)(l-1)+1}(c'')
=g_{c''}(c'')$$
but $h_c(c) \bmod M = f_{c'}(c')$ and $h_c(c) \bmod N=g_{c''}(c'')$, so
by the Chinese Remainder Theorem, $$h_c(c)^{\lambda (k-1)(l-1)+1}=h_c(c),$$
since the two equations have a unique solution modulo $MN$. So the sequence
produced by iteration returns to $h_c(c)$ at least every $(k-1)(l-1)$
values, therefore $MN$ is perfectly cyclic. In fact the fundamental period will
be the lowest common multiple of $(k-1)$ and $(l-1)$.
This trivially generalises to

{\it Lemma 10:} \hspace{3mm}
If $ N_1, \ldots, N_t $ are pairwise relatively prime and are all
perfectly cyclic
numbers with respect to $ax^2+bx$, then $\prod^t_1 N_i$ is perfectly cyclic
with respect to $ax^2+bx$.

{\it Theorem 3:} \hspace{3mm}
If $p_1, \ldots, p_t$ are the only perfectly cyclic primes with respect
to $ax^2+bx$, and $r_1, \ldots, r_t$ are such that $p_i^{r_i}$ is perfectly
cyclic, but $p_i^{r_i+1}$ is not,
for each $i$, then the perfectly cyclic numbers
with respect to $ax^2+bx$ are precisely the factors of $\prod_1^t p_i^{r_i}$.

{\it Proof:} \hspace{3mm} 
Apply Lemma 10 to the perfectly cyclic primes, with Lemma 1 guaranteeing that
no other numbers could be perfectly cyclic.
 
For a given prime p, and $0 < d < p$, define 
$$Q_d = \{ x^2 \,\vert \, x^2+d=y^2 \bmod p, x,y \in {\bf Z}_p^{\ast} \}. $$

{\it Lemma 11:} \hspace{3mm}
If $p$ is of the form $4k+3$, then $\#Q_d={{p-3} \over 4}$ for all $d$.
If $p$ is of the form $4k+1$, then $\#Q_d={{p-5} \over 4}$ if $d$ is
a square, and $\#Q_d={{p-1} \over 4}$ if $d$ is a non-square.

{\it Proof:} \hspace{3mm}
Let $x \in Q_d$, then $x^2+d=y^2$ for some $y$. Let $y=x+l$, then
$$ x= \left[ {{d-l^2} \over 2l} \right], 
 x^2=\left[ {{d-l^2} \over 2l} \right]^2 .$$
As $l$ ranges from $1$ to $p-1$, $x^2$ will always be an element of
$Q_d$ unless $x^2=0$ or $x^2=-d$, since both $x^2$ and $y^2$ must be
non-zero. Now we must determine when two different values for the
parameter $l$ give rise to the same value of $x^2$. We have
$$ \left[ {{d -l^2} \over 2l} \right]^2 =
   \left[ {{d -m^2} \over 2m} \right]^2  \Longrightarrow
{{d-l^2} \over 2l}= \pm {{d-m^2} \over 2m} . $$
Therefore, $l=m$ or $lm= -d$ or $l= -m$ or $lm = d$. So, in general,
four
different values for $l$ of the form $l, -l, d/l, -d/l$ give rise to
the same element of $Q_d$, so we would expect $\#Q_d$ to be
approximately ${{p-1} \over 4}$. These four values are distinct unless
$l^2= \pm d$, when they coalesce to just two values. But,
$$ l^2= \pm d \Longrightarrow  x^2 = {{[d \mp d]^2} \over {\pm 4d}}
= 0, -d $$ 
so the cases $l^2= \pm d$ do not give valid solutions for $x^2$.

If $p=4k+3$, then $(-1 \,\vert \, p)=(-1)^{2k+1}= -1$. Therefore, $(-1)$ is
a non-square modulo $p$, and precisely one of $d$ and $-d$ will be
a square, so precisely two values of $l$ do not give a valid solution.
The remaining $p-3$ values split into groups of four giving the same
value for $x^2$, so $\#Q_d={{p-3} \over 4}$. 

If $p=4k+1$, then $(-1)$ is a square modulo $p$, and so either $l^2=d$
and $l^2=-d$ are both possible, or neither is possible. If $d$ is
a square, then both are, so four values for $l$ will be eliminated
giving $\#Q_d={{p-5} \over 4}$. If $d$ is a non-square, then
$\#Q_d={{p-1} \over 4}$.

{\it Corollary:} \hspace{3mm} 
Symmetrically we can define $N_d$ as the set of all non-squares $x$ for
which $x+d$ is also a non-square. By precisely the same argument as above
we can deduce that if $p=4k+3$ then $\#N_d={{p-3} \over 4}$,
and if $p=4k+1$ then $\#N_d={{p-5} \over 4}$ if $d$ is a non-square,
and $\#N_d={{p-1} \over 4}$ if $d$ is a square. Therefore, for
all $p$ and $d$, $\#Q_d+\#N_d={{p-3} \over 2}$.

\begin{center} {\underline {\bf 7. \quad Calculation of square 
distribution using Elliptic Curves}} \end{center}

Now we wish to consider $\# (Q_d \cap Q_e)$, 

{\it Theorem 4:} \hspace{3mm}
${{p-15} \over 8} - {\sqrt{p} \over 2}
\leq \#(Q_d \cap Q_e), \#(N_d \cap N_e) \leq {p \over 8} + {\sqrt{p} \over 2}$
provided that $d \neq e$.

{\it Proof:} \hspace{3mm}

First we introduce some new notation. Let $S, N, \star $ stand for a
square in \zp, a non-square in \zp and any element of \zp respectively. 
For given $d$ and $e$ with $d \neq e, de \neq 0$ we can use the
alphabet $\{ S, N, \star \}$ to write a three letter codeword representing
the number of triples $(x, x+d, x+e)$ where the first, second and third
symbols state the restrictions placed on $x, x+d$ and $x+e$ respectively.
For example, we write $SN\star $ for the number of triples $(x, x+d, x+e)$
where $x$ is a square in \zp, $x+d$ a non-square in \zp, and $x+e$ any
element of \zp. 

From the definitions of the symbols we immediately obtain the following
rewriting rules for expressions involving $\star $
\begin{equation} SS\star =SSS+SSN \end{equation}
\begin{equation} S\star S=SSS+SNS \end{equation}
\begin{equation} \star SS=SSS+NSS \end{equation}
\begin{equation} NN\star =NNS+NNN \end{equation}
\begin{equation} N\star N=NSN+NNN \end{equation}
\begin{equation} \star NN=SNN+NNN. \end{equation}

In this new notation $\#(Q_d \cap Q_e)$ becomes $SSS$ and
$\#(N_d \cap N_e)$ becomes $NNN$. Recall that $SS\star $ is the number
of triples $(x, x+d, x+e)$ where $x$ and $x+d$ must be squares but
$x+e$ can be any element of \zp. This will be equal to $\#Q_d$ unless
$(-e)$ and $(-e+d)$ are both squares when $(-e) \in Q_d$ but 
$(-e, -e+d, 0)$ is not a valid triple since $0 \not \in \zp$. This could be
avoided by amending the definition of $\star $ to be any element of
${\bf Z}_p$, but then the rewriting rules involving $\star $ would no
longer hold.

Therefore, 
\begin{equation}   SS\star = \left \{ \begin{array}{ll}
\#Q_d -1 & \mbox{if $(-e) \in Q_d$} \\
\#Q_d & \mbox{otherwise. }
\end{array} \right .   \end{equation}
Similarly, 
\begin{equation} NN\star = \left \{ \begin{array}{ll}
\#N_d -1 & \mbox{if $(-e) \in N_d$} \\
\#N_d & \mbox{otherwise. }
\end{array} \right .   \end{equation}
Combining (7) and (8) and noting that $(-e) \not \in Q_d \cap Q_e$, we
deduce that
\begin{equation}
\#Q_d + \#N_d -1 \leq SS\star + NN\star \leq \#Q_d + \#N_d.
\end{equation}
From the Corollary to Lemma 11 we know that $\#Q_d+\#N_d={{p-3} \over 2}$, 
giving us
\begin{equation} {{p-3} \over 2}-1 \leq SS\star + NN\star \leq {{p-3} \over 2}.
\end{equation}
In the same way we can show that $S\star S+N\star N$ and $\star SS + \star NN$
lie in the same range.

Now we can use an elliptic curve argument to estimate $SSS$ and $NNN$. 
For a full treatment of elliptic curves see [3] and [4]. 
To find $SSS$ we must count the number of $x \in \zp$ for 
which $x, x+d, x+e$ are all
non-zero squares. Consider the elliptic curve $y^2=x(x+d)(x+e)$ over
${\bf Z}_p$. By Hasse's theorem, the number, $U$, of points on the
curve satisfies $\vert U - (p+1) \vert \leq 2 \sqrt{p}$. Let $U'$ be
the number of distinct non-zero $x$-co-ordinates of points on the curve, 
then $U'= {{U-4} \over 2}$, since we are not counting the
\lq point at infinity \rq, or the three points with $y$-co-ordinate
$0$,
and the remaining points are of the form $(x, \pm y)$. 
Using the possible range for $U$ given by Hasse's Theorem we deduce that
\begin{equation} {{p-3} \over 2} - \sqrt{p} \leq U' \leq {{p-3} \over 2}
+ \sqrt{p}. \end{equation}
 
$U'$ counts those points for which $x, x+d, x+e$ are all
squares and those for which precisely one of
the three terms is a square. In our new notation this means that
\begin{equation} U'=SSS + SNN + NSN + NNS. \end{equation}
Now we use equations (6)-(8) and (11) to rewrite (12) as
\begin{equation} {{p-3} \over 2} - \sqrt{p} \leq
SSS + (\star NN + N\star N + NN\star) - 3NNN
\leq {{p-3} \over 2} + \sqrt{p}. \end{equation}

$U'$ is the number of values of $x \in {\bf Z}_p - \{ 0, -d, -e \}$
for which $x(x+d)(x+e)$ is a square. It is clear that the number of
values of $x \in {\bf Z}_p - \{ 0, -d, -e \}$ for which
$x(x+d)(x+e)$ is a non-square, 
$U''$ say, also lies in the range ${{p-3} \over 2}
\pm \sqrt{p}$ since obviously $U'+U''=p-3$. Thus we obtain the
symmetrical counterpart of (13):
\begin{equation} {{p-3} \over 2} - \sqrt{p} \leq
NNN + (\star SS + S\star S + SS\star) - 3SSS 
\leq {{p-3} \over 2} + \sqrt{p}. \end{equation}

Solving (13) and (14) simultaneously and using (7)-(9) to
evaluate the terms involving $\star$, we deduce that
\begin{equation} 
{{p-15} \over 8} - {\sqrt{p} \over 2} \leq SSS , NNN \leq
{p \over 8} + {\sqrt{p} \over 2}. \end{equation}

Substituting  (7),(8),(13) and (14) into (1)-(6) we obtain a
complete determination of all our three letter codes:
\begin{equation}
{{p-18} \over 8} -{\sqrt{p} \over 2} \leq SSN, SNS, NSS, NNS, NSN, SNN \leq
{{P+10} \over 8} + {\sqrt{p} \over 2}. \end{equation}

We can now use this result about the distribution of the squares
and non-squares in \zp to prove that perfectly cyclic primes
with respect to $ax^2+bx$ cannot exist for certain values of 
$a$ and $b$. 

{\it Lemma 12:} \hspace{3mm}
For a given $a$ and $b$, if $c$ can be found such that $b^2-4ac, b^2-4ac-4b, 
b^2-8ac-4b$ are all non-squares modulo prime $p$, then $p$ is not
perfectly cyclic with respect to $ax^2+bx$. 

{\it Proof:} \hspace{3mm}
As in the proof of Lemma 3, consider the backwards chain of predecessors
of $ac^2+bc+c$:
$pre(ac^2+bc+c)=c, -{b \over a}-c$ and then $pre(c)=0, -{b \over a}$ and
$pre(-{b \over a}-c)={ {{-b \pm \sqrt{b^2-8ac-4b}} \over 2a}}$. 
Finally $pre(0)=
{ {{-b \pm \sqrt{b^2-4ac}} \over 2a}}$ and $pre(-{b \over a})=
{ {{-b \pm \sqrt{b^2-4ac-4b}} \over 2a}}$. 
If there exists an instance of $c$, such
that $b^2-4ac$, $b^2-4ac-4b$, and $b^2-8ac-4b$ are all non-squares, then
the chain of predecessors cannot be followed back to $ac^2+bc+c$, and
so $p$ is not perfectly cyclic with respect to $ax^2+bx$.

We will now show that for sufficiently large $p$, it is always possible to
find such a $c$, unless $b= \pm 4$ or $b=0$. 
Let $\Delta = b^2-4ac$. We must find $\Delta, \Delta-4b, 
2\Delta -4b -b^2$ all non-squares. There are values of $c$ for which
these three quantities are not all different namely $c=0$ and $c=-{b \over a}$.
However, the case $c=0$ would force $\Delta$ to be a square, and 
$c=-{b \over a}$ forces $\Delta -4b$ to be a square, so neither special
value of $c$ could be included when counting up instances of 
$\Delta, \Delta-4b, 2\Delta -4b -b^2$ all being non-squares. 
Consider the elliptic curve $y^2=2x(x-4b)(x-{(b^2+4b)\over 2})$ 
over ${\bf Z}_p$. Let $V$ be the number of values of
$\Delta \in \zp$ for which $\Delta, \Delta-4b, 2\Delta -4b -4b^2$ are
all non-squares. The presence of an extra factor of 2 makes a slight
difference. If 2 is a square then $V=NNN$ whereas if 2 is a
non-square then $V=NNS$. From (14) and (15) we see that there is no
real difference between $NNN$ and $NNS$, only slightly more uncertainty
in the value of $NNS$. Taking $d=-4b, e=-{(b^2+4b) \over 2}$ and
applying Theorem 4,
\begin{equation} {{p-18} \over 8} -{\sqrt{p} \over 2} \leq V \leq
{{p+10} \over 8} + {\sqrt{p} \over 2}. \end{equation}

This assumes that $d, e \neq 0$ and that $d \neq e$. The only
cases for which these conditions do not hold are
$b=0$ and $b=\pm 4.$

Now $V$ is the number of suitable values of $\Delta$ for which
$\Delta, \Delta-4b \mbox{ and } 2\Delta-4b-b^2$ are all non-squares, so
when $ {{p-18} \over 8} > {{\sqrt{p} \over 2}} $, 
$V > 0$, and we can always choose $c$ so that $\Delta$ is one of the
values counted by $V$. The condition that $ {{p-18} \over 8} > 
{{\sqrt{p} \over 2}}$ simplifies to $p > (2 + \sqrt{22})^2 \approx 45.7. $ 

There are still a couple of loose ends to be tied up. The proof of Lemma 12
does not apply to the cases $b=0$ and $b=\pm 4$. This corresponds to
the fact that if 2 is a non-square in \zp then it is not possible to
ever find $-4ac, -4ac, -8ac$ all non-squares when $b=0$ since
precisely one of $-4ac$ and $-8ac$ must be a square, and similarly we
can never find $16-4ac, -4ac, -8ac$ all non-squares when $b=4$, or
$16-4ac, -4ac, 32-8ac$ all non-squares when $b=-4$. We are as yet unable to 
deal with the case $b = \pm 4.$ 

We can deal with the case $b=0$. The 
initial value
for each cycle is $ac^2+c$. As in the proof of Lemma 3, $pre(ac^2+c)=\pm c$,
$pre(+c)=0$, $pre(-c)= \pm \sqrt{-{2c \over a}}$ and $pre(0)= \pm
\sqrt{-{c \over a}}$. 

When 2 is a square mod $p$ then we choose $c$ so that 
$-c$ and $-2c$ are both squares if $a$ is a non-square, or both non-squares
if $a$ is a square. The proof of Lemma 4 guarantees that we can always find
such a $c$. Now both $-{c \over a}$ and $-{2c \over a}$ are non-squares
and so we cannot continue taking predecessors back any further. Therefore
we can never return to $ac^2+c$ and no prime $p$ for which 2 is a square
mod $p$ can be perfectly cyclic with respect to $ax^2$. 

When $2$ is a non-square mod $p$ we can always find a $y$ such
that $y^2+y$ and $y^2-y$ are both non-squares as in the proof of Lemma 6.
Let $c=- {y^2 \over a}$. Only one of $-{c \over a}$ and $-{2c \over a}$
can be a square and in this case it is clearly $-{c \over a}={y^2 \over a^2}$.
Now $pre(\pm \sqrt{-{c \over a}})=\pm \sqrt{ {\pm \sqrt{-{c \over a}} -c} 
\over a} = \pm \sqrt{ {\pm {y \over a} + {y^2 \over a}} \over a} =
\pm {{\sqrt{\pm y + y^2}} \over a}$. We already know that $y^2 +y$ and
$y^2-y$ are both non-squares, therefore we cannot continue taking
predecessors back any further. Therefore we can never return to $ac^2+c$ 
and no prime $p$ for which 2 is a non-square can be perfectly cyclic with
respect to $ac^2+c$, except possibly 3 and 5. [Recall that the proof of Lemma 6
applies to all primes $p$ for which 2 is a non-square mod $p$, except
for $p=3$ and $p=5$.] By direct calculation it is easily verified that
2, 3 and 5 are perfectly cyclic with respect to $ax^2$.

We have proved that when $b=0$ the only perfectly cyclic primes with
respect to $ax^2+bx$ are 2, 3, 5, and any prime which divides a.

Summarising the above results we have

{\it Theorem 5:} \hspace{3mm}
For prime $p \geq 47$, and non-zero $b \neq \pm 4,$
we can always choose $c$ so
that $\Delta, \Delta-4b, 2\Delta-4b-b^2$ are all non-squares, and therefore
by Lemma 12, $p$ is not perfectly cyclic with respect to $ax^2+bx$.
Furthermore, when $b=0$, then $p$ is only perfectly cyclic with respect 
to $ax^2$ if $p=2, 3, 5$ or $p$ divides $a.$ 

When $b= \pm 4$ then $p$ is apparently only perfectly cyclic with respect to 
$ax^2+bx$ if $p=2, 3, 5$ or $p$ divides $a$. This is not a theorem, but
merely an observation bordering on a conjecture.

\bs
Finally we deal with the remaining primes less than 47. 
For a fixed prime, $p$, we can determine the values of $a$ and $b$,
for which $p$ will be perfectly cyclic. Simply compute the sequences 
$<f_c(c), f_c^2(c), \ldots, >$ for each combination of values for
$a \bmod p$ and $b \bmod p$, and test for perfect cyclicity. This means
we can test the primes up to 43 individually, then invoke Theorem 5 to
dispose of the rest. Calculation shows that 2, 3, 5 are always perfectly
cyclic; 7 is perfectly cyclic if and only if, $b= \pm 2 \bmod 7$; and no
other prime $p$ is perfectly cyclic with respect to any $ax^2+bx$ unless
$a \bmod p=0$.

\begin{center} {\underline {\bf 8. \quad Conclusion}} \end{center}

For a given polynomial $ax^2+bx$  (where $b \neq \pm 4$)
the primes which are perfectly cyclic
with respect to $ax^2+bx$ are: 2, 3, 5, 7 if and only if, $b= \pm 2
\bmod 7$, and any primes which divide $a$.

\begin{center} {\underline {\bf Acknowledgements}} \end{center}
The authors would like to thank D. Coppersmith and
J. W. S. Cassels for their comments on elliptic curves in
private correspondence.

\begin{center} {\underline {\bf References}} \end{center}

1. \quad B. Branner. ``The Mandelbrot Set'', in Robert L. Devaney and Linda
Keen (eds.), {\it Chaos and Fractals: The
mathematics behind the computer graphics} vol. 39 Proceedings of Symposia in
Applied Mathematics, AMS (1989), 75--105.

2. \quad E. Kranakis. {\it ``Primality and Cryptography''}. Wiley-Teubner
(1986).

3. \quad J. W. S. Cassels. {\it ``Lectures on Elliptic Curves.''} CUP (1991).

4. \quad S. Lang. {\it ``Elliptic Curves and Diophantine Analysis.''}
Springer-Verlag (1978).

\end{document}
