Chaos, Elliptic Curves and All That

Matthew Fletcher ^{∗}

Geoff C. Smith

School of Mathematical Sciences, University of Bath, Bath BA2 7AY, England

1. Introduction

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} : C → C is defined by f_{c}(z) = z^{2} + c. The Mandelbrot Set is defined to be those points c ∈ C for which the sequence c, f_{c}(c), f_{c}(f_{c}(c)), … 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.

2. Definitions Let Z_{N} be the ring of integers modulo N. For fixed N > 0, define f_{c} : Z_{N} → Z_{N} by

∗The work of the first author was supported by the SERC

f_{c}(x) = x^{2} + c mod N for 0 ≤ c < N.

Define s_{c} to be the infinite sequence < f_{c}(c), f_{c}(f_{c}(c)), …, f_{c}^{n}(c), … > , 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) k > l ≥ 1. Then we can write

s_{c} =< f_{c}(c), f_{c}^{2}(c), …, f_{c}^{l−1} >⌢< f_{c}^{l}(c), …, f_{c}^{k−1}(c) >^{∞}

where ⌢ denotes sequence concatenation, and < … >^{∞} denotes the sequence repeated ad infinitum. If l = 1 then we can write s_{c} =< f_{c}(c), …, f_{c}^{k−1}(c) >^{∞} and say that s_{c} is cyclic, with fundamental period (k − 1). If s_{c} is cyclic for all 0 ≤ c ≤ N then we say that N is perfectly cyclic.

3. Preliminary Results

Lemma 1: If N is perfectly cyclic and M divides N, then M is perfectly cyclic.

Proof: For all c, 0 ≤ c < N, there exists k_{c} such that f_{c}^{k_{c}}(c) = f_{c}(c) mod N. Therefore, f_{c}^{k_{c}}(c) = f_{c}(c) mod 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) mod M – a contradiction.

Lemma 2: 2, 3, and 5 are perfectly cyclic.

Proof: by direct calculation.

4. Quadratic Residues and Non–Residues For a full treatment see [2]. We write Z_{p}^{∗} for the group of units of the integers modulo p. An element x ∈ Z_{p}^{∗} is a quadratic residue if x = y^{2} mod p for some y ∈ Z_{p}^{∗}, otherwise x is a quadratic non–residue. The quadratic residues form a normal subgroup of index 2 in the multiplicative group Z_{p}^{∗}, 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 mod p, written (x | p), is defined for p odd as

(x | p) = \{ \begin{matrix}1 & if x is a quadratic residue \\ −1 & if x is a quadratic non–residue \end{matrix}

for p prime, and x ∈ Z_{p}^{∗}.

For p odd, precisely half of the numbers in Z_{p}^{∗} are quadratic residues, namely 1^{2} mod p, 2^{2} mod p, …, ((p − 1)/2)^{2} mod p.

5. Determination of perfectly cyclic numbers

Lemma 3: Let p be an odd prime. If there exists c (0 < c < p) such that −c and −2c are both quadratic non-residues mod p then s_{c} is not cyclic, and hence p is not perfectly cyclic.

Proof: 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) mod p = v. For s_{c} to be cyclic, f_{c}(c) = (c^{2} + c) mod 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) = ±\sqrt{−c}. If pre(c^{2} + c) = −c, then pre(−c) = ±\sqrt{−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.

Lemma 4: Let p be an odd prime. If 2 is a quadratic residue mod p, then p is not perfectly cyclic.

Proof: Consider the (p−1) ordered pairs (1, 2), (2, 4), …, (p−1, 2p−2). Since precisely half the numbers in Z_{p}^{∗} are quadratic residues, the average number of quadratic residues per pair is precisely 1. Now take any quadratic residue mod 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 nonresidues, 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 | p) = (−1)^{(p^{2}−1)/8}

Let p = 8q + r, where r ∈ {1, 3, 5, 7}, then (2 | 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.

Lemma 5: Let p be an odd prime such that 2 is a quadratic non–residue mod p. If there exists a y ∈ Z_{p}^{∗} such that y^{2} − y and y^{2} + y are both quadratic non-residues then p is not perfectly cyclic.

Proof: Assume, for contradiction, that the hypotheses are satisfied but that s_{c} is perfectly cyclic. Let c = −y^{2} mod 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) = ±\sqrt{−c} = ±y. Notice that pre(+y) = ±\sqrt{+y − c} = ±\sqrt{y^{2} + y}, and pre(−y) = ±\sqrt{−y − c} = ±\sqrt{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.

Lemma 6: Let p be a prime greater than 5 such that 2 is a quadratic non– residue mod p. The prime p is not perfectly cyclic.

Proof: It will suffice to prove there exists a y such that y^{2} − y and y^{2} + y are both quadratic non-residues mod p, and then apply Lemma 5. Suppose, for a contradiction, that no such y exists. That is, for every y ∈ Z_{p}^{∗} at least one of y^{2} − y and y^{2} + y is a quadratic residue.

\begin{matrix}y & y^{2} − y & y^{2} + y \\ 2 & 2 & 6 \\ 3 & 6 & 12 \\ 4 & 12 & 20 \\ 5 & 20 & 30 \\ 9 & 72 & 90 \end{matrix}

Recall that 2 is a quadratic non–residue, therefore, from y = 2, it follows that 6 is a quadratic residue. Now 12 = 2 × 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} × 5, so 5 is a quadratic residue. Now 72 = 6^{2} × 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} × 10, so 10 is a quadratic residue, but 10 = 2 × 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 ∈ Z_{p}^{∗}, and so does not apply to the primes p = 3 and p = 5.

Combining Lemmas 2, 4 and 6 we obtain Theorem 1: 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:

Lemma 7: Only numbers of the form 2^{a} × 3^{b} × 5^{c} where 0 ≤ a ≤ 3, 0 ≤ b ≤ 2, 0 ≤ c ≤ 2 can be perfectly cyclic.

We can verify that 2^{3} × 3^{2} × 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.

Theorem 2: The set of perfectly cyclic numbers is precisely

{2^{a} × 3^{b} × 5^{c} such that 0 ≤ a ≤ 3, 0 ≤ b, c ≤ 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}.

6. General quadratic polynomials

Having determined the perfectly cyclic numbers for the maps x → x^{2} + c, we would like to generalise to quadratic maps of the form x → ax^{2} + bx + c, where a, b are integers, a ≠ 0. Let us call such perfectly cyclic numbers: ‘perfectly cyclic with respect to ax^{2}+bx ’. So the original perfectly cyclic numbers become perfectly cyclic with respect to x^{2}.

When a = 0 mod p, the map f_{c}(x) = ax^{2} + bx + c mod 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 → ax^{2}+bx+c mod M, 0 ≤ c < M, g_{c} : x → ax^{2}+bx+c mod N, 0 ≤ c < M, and h_{c} : x → ax^{2} + bx + c mod MN, 0 ≤ c < MN.

Lemma 8: h_{c}^{i}(c) mod M = f_{cmodM}^{i}(c mod M) for all positive i.

Proof: Let c′ = c mod M, and c′′ = c mod N. h_{c}(y) mod M = (ay^{2} + by + c mod MN) mod M = (a(y mod M)^{2} + b(y mod M) + c) mod M = f_{c′}(y mod M) for all 0 ≤ y < MN. Now we can prove the lemma by induction on i.

Base Case: (i = 1)

h_{c}(c) mod M = f_{c′}(c′) from above, with c = y

Inductive Step: Suppose Lemma is true for some I, I > 0, then

h_{c}^{I}(c) mod M = f_{c′}^{I}(c′),
h_{c}^{I+1}(c) mod M = h_{c}(h_{c}^{I}(c)) mod M = f_{c′}(h_{c}^{I}(c) mod M)
= f_{c′}(f_{c′}^{I}(c′)) = f_{c′}^{I+1}(c′).

Hence, by induction, we are done.

Similarly,

h_{c}^{i}(c) mod N = g_{c′′}^{i}(c′′) for all i, i ≥ 1.

Lemma 9: 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.

Proof: With f, g, h, c′, c′′ defined as above, pick an arbitrary c, 0 ≤ c < MN, and let k and l be the smallest k, l > 1 such that f_{c′}^{k}(c′) = c′ and g_{c′′}^{l}(c′′) = c′′, and consider

h_{c}^{λ(k−1)(l−1)+1} λ an integer
h_{c}^{λ(k−1)(l−1)+1} mod M = f_{c′}^{λ(k−1)(l−1)+1}(c′) = f_{c′}(c′)
h_{c}^{λ(k−1)(l−1)+1} mod N = g_{c′′}^{λ(k−1)(l−1)+1}(c′′) = g_{c′′}(c′′)

but h_{c}(c) mod M = f_{c′}(c′) and h_{c}(c) mod N = g_{c′′}(c′′), so by the Chinese Remainder Theorem,

h_{c}(c)^{λ(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

Lemma 10: If N_{1}, …, N_{t} are pairwise relatively prime and are all perfectly cyclic numbers with respect to ax^{2} + bx, then ∏_{1}^{t} N_{i} is perfectly cyclic with respect to ax^{2} + bx.

Theorem 3: If p_{1}, …, p_{t} are the only perfectly cyclic primes with respect to ax^{2} + bx, and r_{1}, …, 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 ∏_{1}^{t} p_{i}^{r_{i}}.

Proof: 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} | x^{2} + d = y^{2} mod p, x, y ∈ Z_{p}^{∗}}.

Lemma 11: If p is of the form 4k + 3, then #Q_{d} = \frac{p−3}{4} for all d. If p is of the form 4k + 1, then #Q_{d} = \frac{p−5}{4} if d is a square, and #Q_{d} = \frac{p−1}{4} if d is a non-square.

Proof: Let x ∈ Q_{d}, then x^{2} + d = y^{2} for some y. Let y = x + l, then

x = [\frac{d − l^{2}}{2l} ] , x^{2} = [\frac{d − l^{2}}{2l} ]^{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

[\frac{d − l^{2}}{2l} ]^{2} = [\frac{d − m^{2}}{2m} ]^{2} ⟹ \frac{d − l^{2}}{2l} = ±\frac{d − m^{2}}{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 \frac{p−1}{4}. These four values are distinct unless l^{2} = ±d, when they coalesce to just two values. But,

l^{2} = ±d ⟹ x^{2} = \frac{[d ∓ d]^{2}}{±4d} = 0, −d

so the cases l^{2} = ±d do not give valid solutions for x^{2}.

If p = 4k + 3, then (−1 | 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} = \frac{p−3}{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} = \frac{p−5}{4}. If d is a non-square, then #Q_{d} = \frac{p−1}{4}.

Corollary: 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} = \frac{p−3}{4}, and if p = 4k + 1 then #N_{d} = \frac{p−5}{4} if d is a non-square, and #N_{d} = \frac{p−1}{4} if d is a square. Therefore, for all p and d, #Q_{d} + #N_{d} = \frac{p−3}{2}.

7. Calculation of square distribution using Elliptic Curves

Now we wish to consider #(Q_{d} ∩ Q_{e}),

Theorem 4: \frac{p−15}{8} − \frac{\sqrt{p}}{2} ≤ #(Q_{d} ∩ Q_{e}), #(N_{d} ∩ N_{e}) ≤ \frac{p}{8} + \frac{\sqrt{p}}{2} provided that d ≠ e.

Proof:

First we introduce some new notation. Let S, N, ⋆ stand for a square in Z_{p}^{∗} , a non-square in Z_{p}^{∗} and any element of Z_{p}^{∗} respectively. For given d and e with d ≠ e, de ≠ 0 we can use the alphabet {S, N, ⋆} 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⋆ for the number of triples (x, x + d, x + e) where x is a square in Z_{p}^{∗} , x + d a non-square in Z_{p}^{∗} , and x + e any element of Z_{p}^{∗} .

From the definitions of the symbols we immediately obtain the following rewriting rules for expressions involving ⋆

SS⋆ = SSS + SSN  (1)
S ⋆ S = SSS + SNS  (2)
⋆SS = SSS + NSS  (3)
NN⋆ = NNS + NNN  (4)
N ⋆ N = NSN + NNN  (5)
⋆NN = SNN + NNN.  (6)

In this new notation #(Q_{d} ∩Q_{e}) becomes SSS and #(N_{d} ∩N_{e}) becomes NNN. Recall that SS⋆ 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 Z_{p}^{∗} . This will be equal to #Q_{d} unless (−e) and (−e + d) are both squares when (−e) ∈ Q_{d} but (−e, −e + d, 0) is not a valid triple since 0 ∉ Z_{p}^{∗}. This could be avoided by amending the definition of ⋆ to be any element of Z_{p}, but then the rewriting rules involving ⋆ would no longer hold.

Therefore,

SS⋆ = \{ \begin{matrix}#Q_{d} − 1 & if (−e) ∈ Q_{d} \\ #Q_{d} & otherwise. \end{matrix}  (7)

Similarly,

NN⋆ = \{ \begin{matrix}#N_{d} − 1 & if (−e) ∈ N_{d} \\ #N_{d} & otherwise. \end{matrix}  (8)

Combining (7) and (8) and noting that (−e) ∉ Q_{d} ∩ Q_{e}, we deduce that

#Q_{d} + #N_{d} − 1 ≤ SS ⋆ +NN⋆ ≤ #Q_{d} + #N_{d}.  (9)

From the Corollary to Lemma 11 we know that #Q_{d} + #N_{d} = \frac{p−3}{2}, giving us

\frac{p − 3}{2} − 1 ≤ SS ⋆ +NN⋆ ≤ \frac{p − 3}{2}.  (10)

In the same way we can show that S ⋆ S + N ⋆ N and ⋆SS + ⋆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 ∈ Z_{p}^{∗} for which x, x+d, x+e are all non-zero squares. Consider the elliptic curve y^{2} = x(x + d)(x + e) over Z_{p}. By Hasse’s theorem, the number, U, of points on the curve satisfies |U − (p + 1)| ≤ 2\sqrt{p}. Let U′ be the number of distinct non-zero x-co-ordinates of points on the curve, then U′ = \frac{U−4}{2}, since we are not counting the ‘point at infinity ’, or the three points with y-co-ordinate 0, and the remaining points are of the form (x, ±y). Using the possible range for U given by Hasse’s Theorem we deduce that

\frac{p − 3}{2} − \sqrt{p} ≤ U′ ≤ \frac{p − 3}{2} + \sqrt{p}.  (11)

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

U′ = SSS + SNN + NSN + NNS.  (12)

Now we use equations (6)-(8) and (11) to rewrite (12) as

\frac{p − 3}{2} − \sqrt{p} ≤ SSS + (⋆NN + N ⋆ N + NN⋆) − 3NNN ≤ \frac{p − 3}{2} + \sqrt{p}. (13)

U′ is the number of values of x ∈ 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 ∈ Z_{p} − {0, −d, −e} for which x(x + d)(x + e) is a non-square, U′′ say, also lies in the range \frac{p−3}{2} ± \sqrt{p} since obviously U′ + U′′ = p − 3. Thus we obtain the symmetrical counterpart of (13):

\frac{p − 3}{2} − \sqrt{p} ≤ NNN + (⋆SS + S ⋆ S + SS⋆) − 3SSS ≤ \frac{p − 3}{2} + \sqrt{p}. (14)

Solving (13) and (14) simultaneously and using (7)-(9) to evaluate the terms involving ⋆, we deduce that

\frac{p − 15}{8} − \frac{\sqrt{p}}{2} ≤ SSS, NNN ≤ \frac{p}{8} + \frac{\sqrt{p}}{2}.  (15)

Substituting (7),(8),(13) and (14) into (1)-(6) we obtain a complete determination of all our three letter codes:

\frac{p − 18}{8} − \frac{\sqrt{p}}{2} ≤ SSN, SNS, NSS, NNS, NSN, SNN ≤ \frac{P + 10}{8} + \frac{\sqrt{p}}{2}. (16)

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

Lemma 12: 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.

Proof: As in the proof of Lemma 3, consider the backwards chain of predecessors of ac^{2} +bc+c: pre(ac^{2} +bc+c) = c, −\frac{b}{a} −c and then pre(c) = 0, −\frac{b}{a} and pre(−\frac{b}{a} − c) = \frac{−b±\sqrt{b^{2}−8ac−4b}}{2a}. Finally pre(0) = \frac{−b±\sqrt{b^{2}−4ac}}{2a} and pre(−\frac{b}{a}) = \frac{−b±\sqrt{b^{2}−4ac−4b}}{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 = ±4 or b = 0. Let Δ = b^{2}−4ac. We must find Δ, Δ−4b, 2Δ−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 = −\frac{b}{a}. However, the case c = 0 would force Δ to be a square, and c = −\frac{b}{a} forces Δ − 4b to be a square, so neither special value of c could be included when counting up instances of Δ, Δ−4b, 2Δ−4b−b^{2} all being non-squares. Consider the elliptic curve y^{2} = 2x(x−4b)(x− \frac{(b^{2}+4b)}{2}) over Z_{p}. Let V be the number of values of Δ ∈ Z_{p}^{∗} for which Δ, Δ−4b, 2Δ−4b−4b^{2} are all nonsquares. 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 = −\frac{(b^{2}+4b)}{2} and applying Theorem 4,

\frac{p − 18}{8} − \frac{\sqrt{p}}{2} ≤ V ≤ \frac{p + 10}{8} + \frac{\sqrt{p}}{2}.  (17)

This assumes that d, e ≠ 0 and that d ≠ e. The only cases for which these conditions do not hold are b = 0 and b = ±4.

Now V is the number of suitable values of Δ for which Δ, Δ−4b and 2Δ−4b−b^{2} are all non-squares, so when \frac{p−18}{8} > \frac{\sqrt{p}}{2}, V > 0, and we can always choose c so that Δ is one of the values counted by V. The condition that \frac{p−18}{8} > \frac{\sqrt{p}}{2} simplifies to p > (2 + \sqrt{22})^{2} ≈ 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 = ±4. This corresponds to the fact that if 2 is a non-square in Z_{p}^{∗} 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 = ±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) = ±c, pre(+c) = 0, pre(−c) = ±\sqrt{−\frac{2c}{a}} and pre(0) = ±\sqrt{−\frac{c}{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 −\frac{c}{a} and −\frac{2c}{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 = −\frac{y^{2}}{a}. Only one of −\frac{c}{a} and −\frac{2c}{a} can be a square and in this case it is clearly −\frac{c}{a} = \frac{y^{2}}{a^{2}} . Now pre(±\sqrt{−\frac{c}{a}}) = ±\sqrt{\frac{±\sqrt{− \frac{c}{a}} −c}{a}} = ±\sqrt{\frac{± \frac{y}{a} + \frac{y^{2}}{a}}{a}} = ±^{\frac{\sqrt{±y+y^{2}}}{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

Theorem 5: For prime p ≥ 47, and non-zero b ≠ ±4, we can always choose c so that Δ, Δ − 4b, 2Δ − 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 = ±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.

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), …, > for each combination of values for a mod p and b mod 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 = ±2 mod 7; and no other prime p is perfectly cyclic with respect to any ax^{2} + bx unless a mod p = 0.

8. Conclusion

For a given polynomial ax^{2} + bx (where b ≠ ±4) the primes which are perfectly cyclic with respect to ax^{2} + bx are: 2, 3, 5, 7 if and only if, b = ±2 mod 7, and any primes which divide a.

Acknowledgements

The authors would like to thank D. Coppersmith and J. W. S. Cassels for their comments on elliptic curves in private correspondence.

\underline{References}

1. B. Branner. “The Mandelbrot Set”, in Robert L. Devaney and Linda Keen (eds.), Chaos and Fractals: The mathematics behind the computer graphics vol. 39 Proceedings of Symposia in Applied Mathematics, AMS (1989), 75–105.

2. E. Kranakis. “Primality and Cryptography”. Wiley-Teubner (1986).

3. J. W. S. Cassels. “Lectures on Elliptic Curves.” CUP (1991).

4. S. Lang. “Elliptic Curves and Diophantine Analysis.” Springer-Verlag (1978).