Quadratic Maps As Dynamical Systems On The P-Adic Numbers
Quadratic Maps As Dynamical Systems On The P-Adic Numbers
Quadratic Maps As Dynamical Systems On The P-Adic Numbers
Abstra
t. We des
ribe the traje
tories of the su
essive iterates of the square map and its perturbations
on the eld of p-adi
numbers. We show that the
y
les of the square map on Qp arise from
y
les of the
square map on Fp , and that all nonperiodi
traje
tories in the unit disk are dense in a
ompa
t open subset.
7! 7!
We nd that the perturbed maps x x2 + ", with " inside the unit
ir
le, have similar dynami
s to x x2 ,
but that ea
h fundamental
y
le arising from Fp
an further admit harmoni
y
les, for dierent
hoi
es of
p and ". In
ontrast, the
y
les of the maps x 7! x2 + ", with " on the boundary of the unit
ir
le, are no
longer tied to those of the square map itself. In all
ases we give an algorithm for
omputing the nitely
many periodi
points of the map.
1. Introdu tion
We are interested in dynami
s over the p-adi
elds Q p , for p a prime. Our starting point in this study |
inspired by the development of the
orresponding problem on the real and
omplex numbers over the past
30 years | is the analysis of the dynami
s of the algebrai
ally simplest of nonlinear systems, namely, the
family of quadrati
maps f" (x) = x2 + " for j"jp 1. In this paper, we give a
omplete global des
ription of
the traje
tories of elements x 2 Q p under the iterates of f" .
Denote the norm on Q p by j jp (
f. Se
tion 2) and write f"k = f" Æ Æ f" (k times) for the k th iterate
of f" . Our main result is the following (Theorems 3.4 and 4.4).
Theorem. Let f" : Q p ! Qp be given by f" (x) = x2 + ", with j"jp < 1 (in
luding " = 0). Then f" admits
exa
tly two xed points Æp;" and p;" , with jÆp;" jp = jp;" 1jp = j"jp . If x 2 Q p satises jxjp > 1, then the
traje
tory of f"k (x), k = 0; 1; 2; : : : , diverges to innity; whereas if jxjp < 1, the traje
tory
onverges to Æp;" .
If p = 2, then the traje
tory of every x on the unit
ir
le jxjp = 1
onverges to p;" . For any other prime p,
if jxjp = 1, then x is either a periodi
point, or its traje
tory is eventually quasiperiodi
. Further, there are
only nitely many periodi
points.
In parti
ular, one nds that the domains of attra
tion in Q p are easily dened. When " = 0, the xed
points are evidently Æp;0 = 0 and p;0 = 1.
We a
tually prove a far more pre
ise result about the stru
ture of the orbit spa
e, as en
apsulated in
Parts D and F of the proof of Theorem 4.4. In parti
ular, we prove that ea
h
y
le of the square map
x 7! x2 on the nite eld with p elements Fp gives rise to a so-
alled fundamental
y
le of f = f0 on Q p
of equal (primitive) period, and that these are the only nite orbits of the square map on Q p . When we
onsider instead the traje
tories of those maps f" on Q p with j"jp < 1 and " 6= 0, we nd, for all but some
\ex
eptional pairs" (p;
) (
f. Table 6.1),
orresponding fundamental
y
les; furthermore, when j"jp < 1,
fundamental
y
les may admit additional harmoni
s (as p and " vary). Here we dene a harmoni
y
le
to be a nite orbit H of f" whose period is a multiple of that of the
orresponding fundamental
y
le F
whose elements share leading
oeÆ
ients (in their p-adi
expansion) with elements of F . We apply a general
theorem of Pezda [Pezda1994℄ (see Theorem 4.1), to dedu
e the maximum possible length of a harmoni
y
le of f" . Finally, we use a generalization of a result of Thiran, Verstegen and Weyers in [TVW1989℄ to
identify maps f" and fundamental
y
les F whi
h admit no harmoni
s at all.
The paper is organized as follows. In Se
tion 2, we set our notation and summarize brie
y the needed
properties and tools of the p-adi
numbers for the
onvenien
e of the reader. Most of the results, with the
ex
eption of Corollary 2.3, are standard. In Se
tion 3 we analyse the dynami
s of the square map f (x) = x2 ,
with a view towards the general
ase. The analysis
ulminates, in Se
tion 4, with a des
ription of the
traje
tories of f" (x) = x2 + ", for j"jp < 1. The proof of Theorem 4.4 o
upies most of this se
tion. In
Se
tion 5, we give a brief summary of the possible dynami
s of the \boundary"
ase f" (x) = x2 + ", with
j"jp = 1, and des
ribe how the analysis of the proof of Theorem 4.4 may be applied to
ompute
y
les of
these maps. Finally, in Se
tion 6, we dis
uss some of the open questions raised by our analysis, in
luding the
dynami
s of f" on Q p for an ex
eptional prime p. We also dis
uss the existen
e of the nongeneri
ases of our
algorithm, whi
h rmly resist the appli
ation of either Hensel's lemma or the limiting result of [TVW1989℄.
There are a number of papers on related questions of dynami
s of polynomial maps, and quadrati
maps
in parti
ular. The paper [TVW1989℄ of Thiran, Verstegen and Weyers (and,
losely related, the earlier,
but unpublished paper [Ben-Menahem1988℄ of Ben-Menahem) provide signi
ant forays into the dynami
s
of quadrati
maps on Q p . In [TVW1989℄, they prove that fa , with jajp > 1, exhibits
haoti
behaviour,
and also
onsider some examples of the dynami
s of f" , j"jp 1. They prove a result (summarized here
in Theorem 4.2) about the la
k of
y
les in a neighbourhood of a xed point, and then dis
uss the the
quasiperiodi
ity of f" in general as well, using the argument in the appendix of [Ben-Menahem1988℄. In
the present paper, we apply a generalization of their theorem. In
ontrast to [TVW1989℄, however, we have
found a simpler proof of quasi-periodi
ity, and our results about the dynami
s of f" , j"jp 1 are proven in
omplete generality.
Other important papers whi
h
onsider quadrati
maps of the form x 7! x2 + a (over number elds as
well as p-adi
elds) in
lude [Morton1992℄, [MS1994℄, [Narkiewi
z1997℄, [Silverman1996℄, and [WR1994℄.
An analysis of te
hniques whi
h apply to a broad
lass of p-adi
analyti
maps is studied by Lubin in
[Lubin1994℄. In parti
ular, he denes notions of unipoten
y and instability whi
h bear
lose relation to the
nongeneri
ases of our algorithm. Also, he introdu
es the \Lie logarithm" as a linearization tool, and as
su
h it suggests that it might be possible to derive a far more general analysis of linearity near periodi
points
than that presented in [TVW1989℄. Lubin's student Hua-Chieh Li has made a number of generalizations
of Lubin's results, in
luding in parti
ular the paper [Li1996℄; however, these results do not apply to our
quadrati
maps. A number of papers by Khrennikov et al. dis
uss p-adi
dynami
s in general as well as
appli
ations (of the dynami
s of the square map) to neural nets and memory pro
esses (see, for example,
[DK1999, AKT1999, DGKS1999℄).
Another view of the study of p-adi
dynami
s | via the analysis of Julia sets, Fatou sets, and Sullivan's
theorem | has produ
ed a number of signi
ant and deep results. We would like to signal that some of
the key resear
hers in this area are Benedetto (see, for example, [Benedetto2000℄) and Hsia [Hsia1996℄. A
more number-theoreti
approa
h to bifur
ation theory over p-adi
elds
an be found in the work of Vivaldi
(see, for example, [Vivaldi1992℄ and [MV1995℄). These in
lude, in parti
ular, methods for understanding
the algebrai
extensions of the ground eld for whi
h
y
les of a given rational map will appear. It is from
this perspe
tive that one has the
learest pi
ture of the ex
eptional pairs (see Se
tion 4), but we have
hosen
not to present it here.
Last, but
ertainly not least, is a deep paper of Pezda [Pezda1994℄, in whi
h he proves an upper bound
for the possible periods of
y
les of polynomial maps with
oeÆ
ients in the unit
ir
le of Q p (or indeed in
the integer ring of any algebrai
number eld). We
ite his result in Theorem 4.1. Zieve has extended many
of Pezda's result in his (unpublished) thesis [Zieve1996℄. The results in this vein seem fundamental to the
generalization of our results to other polynomial mappings, or to algebrai
extensions of the elds Q p | a
topi
whi
h the authors hope to return to in a subsequent paper.
2. p-adi Numbers
The p-adi
numbers were dis
overed by Kurt Hensel in 1897 in the
ourse of his work on nding new
ompletions of the rational numbers. They
an be dened as follows.
DYNAMICS OF QUADRATIC MAPS ON Qp 3
Let p be a prime number. If n 2 Z is a nonzero integer, then its p-adi
valuation, denoted val(n), is the
largest integral power of p dividing n. Extend this valuation to all rational numbers m=n 2 Q by setting
val(m=n) = val(m) val(n) if m 6= 0, and set val(0) = 1. Then the p-adi
norm is dened by
jxjp = p x
val( )
for any x 2 Q . This norm is nonar
himedean, meaning that we have in pla
e of the triangle inequality the
stronger relation jx + y jp maxfjxjp ; jy jp g. Consequently (and in stark
ontrast to the eu
lidean norm),
the p-adi
norm does not permit the a
umulation of error, in the following sense. If ea
h of k elements
fx1 ; x2 ; : : : ; xk g have p-adi
norm at most , then jx1 + x2 + + xk jp as well. This property justies
the extensive use of modular arithmeti
(\p-adi
estimation") in p-adi
al
ulations, as in Se
tions 3 and 4.
Completing the eld of rational numbers with respe
t to this norm yields the eld of p-adi
numbers,
denoted Q p . A
on
rete realization of Q p is as the set of all formal Laurent series in p with
oeÆ
ients in
the set f0; 1; 2; : : : ; p 1g:
1
X
Q p = fx = an pn j N 2 ; an 2 f0; 1; 2; : : : ; p
Z 6 0g [ f0g = Q p [ f0g;
1g ; aN =
n=N
with addition and multipli
ation performed by starting at the lowest power of p, and \
arrying" su
essively
higher powers of p. (Thus, for example, 1 = (p 1) + (p 1)p + (p 1)p2 + , sin
e adding 1 gives the
zero series.) For x 2 Q p as above, jxjp = p N . Two p-adi
numbers are thus \
lose" with respe
t to the
norm if their
oeÆ
ients an agree for all n < M , for some \large" M . Thus the norm on Q p is equivalent
to that
onventionally used in symboli
dynami
s [Devaney1989℄, that is, maps on sequen
e spa
es (whi
h
arry no inherent algebrai
stru
ture). 1
The distinguished subring of Q p dened by Zp = fx 2 Q p j jxjp 1g is
alled the integer ring. It is an
integral domain. The set of invertible elements in Zp,
alled its group of units is Zp = fx 2 Q p j jxjp = 1g.
The ring Zp
ontains a unique maximal ideal pZp = fx 2 Zp j jxjp < 1g. The quotient of Zp by this
maximal ideal gives a eld, whi
h we identify with the nite eld of p elements F p = Z=pZ in the obvious
way. (Similarly, we
an identify the quotient rings Zp=pn Zp ' Z=pnZ for any positive integer n.) In this
ontext, we
all F p the residue eld (or residue
lass eld ) of Q p .
The eld Q p is unorderable, in essen
e due to the modular arithmeti
of F p . It has
hara
teristi
0 sin
e
it
ontains Q as a subeld. In fa
t, Q is a dense, proper subset of Q p : Q embeds into Q p as the set of
elements whose p-adi
oeÆ
ients are eventually periodi
(mu
h in the same way that Q embeds into R).
Topologi
ally, Q p is a Cantor set: totally dis
onne
ted but not dis
rete. The p-adi
s are also full of holes
in an algebrai
sense: there is no nite eld extension of Q p whi
h is algebrai
ally
losed. Not surprising,
therefore, is the sparseness of the set of periodi
points under f" in Q p .
Nevertheless, nding roots of polynomials in Q p is often quite simple, with the help of Hensel's Lemma.
Theorem 2.1 (Hensel's Lemma). Suppose g(x) is a polynomial with
oeÆ
ients in Zp. If a 2 Zp is an
approximate root of g in the sense that
g(a) 0 mod p2r+1 ; where r = val(g 0 (a));
then there is a unique root b of g near a in the sense that
g(b) = 0 and b a mod pr+1 :
Remark 2.2. In the spe
ial
ase where g0(a) has a
onstant leading term (so val(g0 (a)) = 0), Hensel's
Lemma implies that it suÆ
es to solve the polynomial equation in the residue eld F p in order to ensure the
existen
e of a solution in Zp. In
ontrast, the statement of the theorem is empty when a is a root of g 0 .
Hensel's Lemma is well-known and true in the more general setting of lo
al rings; see, for example,
[Eisenbud1995, Thm.7.3℄. We will make use of a slight extension of Hensel's Lemma, as follows:
1 Another algebrai
stru
ture on this set
an be imposed via
omponent-wise addition mod p (that is, identifying it with the
eld Fp ((t)) of formal Laurent series in an indeterminate t); this has been
onsidered in, for example, [SR1988℄ and [SR1991℄.
DYNAMICS OF QUADRATIC MAPS ON Qp 4
Corollary 2.3. Suppose g(x) is a polynomial with
oeÆ
ients in Zp, p 6= 2. If a 2 Zp is an approximate
root of g in the sense that
g(a) 0 mod p2r+1 ; where r val(g 0 (a));
then there is a unique root b of g near a in the sense that
g(b) = 0 and b a mod pR ;
where R = r + 1 if r = val(g 0 (a)) and R = 2r + 1 val(g 0 (a)) if r > val(g 0 (a)).
Proof. The existen
e and uniqueness of the root b of g is given by Hensel's Lemma; what remains in question
is the a
ura
y to whi
h the approximate root a estimates b, when r > val(g 0 (a)) = m. Write b = a + h, with
val(h) m + 1; we wish to show that val(h) 2r + 1 m. Consider Taylor's expansion of the polynomial
g at b:
1 1
g(b) = g(a + h) = g(a) + hg0 (a) + h2 g00 (a) + h3 g000 (a) + :
2 3!
By hypothesis, we have val(g (a)) 2r + 1 and val(hg 0 (a)) = val(h) + m. We
laim that all other terms of
the series have valuation not less than 2val(h).
Indeed, sin
e val(g 00 (a)) 0, and val(2) = 0 (sin
e p 6= 2), val( 21 h2 g 00 (a)) 2val(h). For the remaining
terms, note that val(n!) n=(p 1) [Neukir
h1986, III.1℄, so
1
1
val( hn g (n) (a)) nval(h) val(n!) n val(h) :
n! p 1
It follows that for all n 2 + 2(val(h)(p 1) 1) 1 , the
orresponding term of the Taylor series has
valuation not less than 2val(h). Thus g (b) g (a) + hg 0 (a) mod p2val(h) ; and sin
e the Taylor series for g at
b is identi
ally zero, we dedu
e that val(g(a)) = val(h) + m, or that val(h) 2r + 1 m as required.
We remark that the stated existen
e of an exa
t root b is not merely abstra
t | one
an expli
itly
ompute
b to any desired pre
ision. As a parti
ular and important example,
onsider the polynomial g(x) = xp 1 1.
Then g 0 (x) = (p 1)xp 2 , so jg 0 (x)jp = jp 1jp jxjpp 2 = jxjpp 2 . Thus, for any a 2 Zp, we have g 0 (a) 2 Zp.
It follows by Remark 2.2 that we should look for roots a of g in the residue eld F p . Sin
e, by Fermat's
Little Theorem, every a 2 f1; 2; 3; : : : ; p 1g satises the equation g (a) 0 mod p, we dedu
e by Hensel's
Lemma that ea
h a gives rise to a unique root a 2 Zp of g with
onstant term equal to a.
Example. Let p = 3, so that g (x) = x2 1. First let a = 1. As a2 = 1 in Z3, it is already a root; so 1 = 1.
Now let a = 2, whi
h is no longer an exa
t root. By Hensel's Lemma, we know that 2 takes the form
2 = 2 + b0 p + b00 p2 + and satises 22 = 1. We
ompute:
22 1 (2 + b0 p)2 1 mod p2
22 + 2(2)(b0 p) + (b0 p)2 1 mod p2
(1 + p) + (1 + p)(b0 p) + b02 p2 1 mod p2
(1 + b0 )p mod p2 :
Setting this last equal to 0 (modulo p2 ) yields b0 = 2. We
ontinue in this way and nd
2 = 2 + 2p + 2p2 + 2p3 + = 1;
as expe
ted.
The roots of the polynomial f (x) = xp 1 1 are
alled the Tei
hmuller representatives of f1; 2; : : : ; p 1g.
Together with 0, they give another
anoni
al
hoi
e of representatives in Zp of the
onjuga
y
lasses of pZp in
Zp. The advantage of this
hoi
e is that the elements f1 ; 2 ; : : : ; p 1 g form a group under multipli
ation
Another tool we would like to introdu
e now for use in Se
tion 3 is the p-adi
exponential map, as dened
by its Taylor series
x2 x3
exp(x) = 1 + x + + + :
2! 3!
DYNAMICS OF QUADRATIC MAPS ON Qp 5
Re
all that over the real numbers, exp is everywhere-
onvergent, and gives a bije
tion of R with R+ , the
positive real line. A moment's thought reveals that the exponential map
annot be nearly so well-behaved
in Q p : if x = p 1 , for example, then ea
h su
essive partial sum of exp(x) has stri
tly in
reasing norm and
hen
e the series
annot
onverge in Q p . Yet
onvergen
e in Q p is simple: a series
onverges exa
tly when
its sequen
e of terms
onverges to zero. A more
areful look at the proof of Lemma 2.3 yields the following
well-known theorem (proven, for example, in [Koblitz1984, IV.1.℄).
Theorem 2.4. The fun
tions exp and log(1 + x) = x x + 13 x2 give mutually inverse isomorphisms
1
(and homeomorphisms) between the multipli
ative group 1+ pn Zp and the additive group pn Zp, for any n 1
2
if p is odd, and n 2 if p = 2.
For more detail on the p-adi
numbers | their arithmeti
, their algebra, or their topology | see, for
example, [Serre1973℄ or [Koblitz1984℄.
In this se
tion we study the iterates of the square map f (x) = x2 on Q p (or Q p ). Let us rst treat the
spe
ial (and simple)
ase of p = 2 before pro
eeding to p > 2, whi
h analysis forms the bulk of this se
tion.
Suppose p = 2. Let C2 = f1g denote the multipli
ative
y
li
group of order 2. We
an
onstru
t a
group isomorphism
(3.1) : Z C2 22Z2 ! Q2
(n; ; x) 7 pn exp(x):
!
Giving Z and the nite group C2 the dis
rete topology, and 22 Z2 the topology it inherits as a subset of Z2,
be
omes a homeomorphism as well. Following the
ommutative diagram
f
!
x? x?
Q2 Q2
? ?
g1
g2
g3
Z C 2
2
2
! C 2
Z2 Z 2
2
Z2
where refers to the Tei
hmuller representatives in Zp. Following the
ommutative diagram
p f
!
x? x?p
Q Q
(3.3) ? ?
g1
g2
g3
Z p p
F p
Z ! p p p Z F Z
g : p p ! p p are given by multipli
ation by 2, and g is the square map g (x) = x on p . While the
3 Z Z 2 2
2
F
rst two maps are linear, and do not give rise to periodi
orbits, the map g2 does admit a
omplex orbit
stru
ture. Let us re
all the De
omposition Theorem of [Rogers1996℄.
Lemma 3.1. For ea
h odd divisor d of p 1, let ordd 2 denote the order of 2 modulo d, and '(d) the Euler
phi fun
tion at d. (So '(d) is the number of numbers less than d relatively prime to d.) Set ord1 2 = 1. For
ea
h distin
t su
h d, we obtain '(d)=ordd 2 distin
t
y
les of the square map g2 on F p of (primitive) period
(3.4)
= ordd 2:
Furthermore, for any x 2 F p whi
h is not itself a periodi
point of g2 , the iterate g2k (x) is periodi
, where k
is
hosen su
h that 2k is the largest even divisor of p 1.
Hen
e, passing ba
k to Q p via the isomorphism (3.2), we dedu
e that all periodi
orbits of f on Q p lie in
the nite subgroup of the Tei
hmuller representatives, and that further the orbit stru
ture of f admits an
expli
it des
ription for all p.
For the remainder of this se
tion, let us give a full a
ount of the quasiperiodi
nature of the square
map on Zp. Re
all that an element x is quasiperiodi
if for every neighbourhood U of x, there exists a
t > 0 su
h that f t(x) 2 U . We are motivated in part by pra
ti
al
onsiderations: in appli
ations, the
inevitable niteness of storage spa
e requires us to
onsider the \trun
ated" p-adi
s Q p modulo pn Zp, for
various degrees of pre
ision n. (As mentioned in Se
tion 2, no artifa
ts or errors are introdu
ed in doing
so.) Moreover, it is of interest to determine the randomness (or la
k thereof) of the set of ith
oeÆ
ients of
elements of a traje
tory under f .
To this end, let us rst
onsider the a
tion of g3 (x) = 2x on the strata of Q p , that is, on the open sets of
the form pr Zp (or, equally, their images in Q p modulo pn Zp for any n r).
Identify the spa
e pZp=p2 Zp with Fp , the nite eld with p elements. The element 0 is xed by multipli-
ation by 2. The orbit of the doubling map through an element a 2 F p is
O = fa; 2a; 2 a; 2 a; : : : 2n ag;
2 3 1
where n is the order of 2 modulo p. It follows that pZp=p2 Zp de
omposes under g3 into (p 1)=n
y
li
orbits of period n, and one xed point. Case-by-
ase
omputation for the odd primes p < 100 yields the
data in Table 3.1.
On strata pZp=ps+1 Zp ' Z=psZ, s > 1, we
ompute the number of
y
les of g3 as follows.
If n = ordp 2, and r = val(2n 1), then 2n = 1 + pr v , for some v 2 Zp. If s r, then the order of 2 in
s r
Z=p Z is simply n. If s > r , then an indu
tive argument, using the binomial expansion on 1 + p v , shows
that the order of 2 in Z=psZ is nps r . Moreover, whatever this order m, we have val(2m 1) = maxfr; sg.
Clearly, for p 6= 2, multipli
ation by 2 preserves valuation, so g3 preserves ea
h substratum pk Z=psZ '
Z=p
s kZ, for k s. The period of the
y
le of g through z 2 Z=psZ (val(z ) = k ) is determined by the
3
order of 2 in Z=ps kZ. Hen
e the periods of all the
y
les of g3 on Z=psZ are in the set
(3.5) f1; npk r j k = r; r + 1; : : : sg
where shorter periods arise for larger values of k , i.e. through elements of smaller p-adi
norm.
We may now lift this to a result for the square map f using the diagram 3.3.
DYNAMICS OF QUADRATIC MAPS ON Qp 7
Table 3.1. Primes p, the order of 2 modulo p, and the number of
y
les of the doubling
map on F p .
Proposition 3.2. Let p be an odd prime, let n be the order of 2 in Z=pZ and set r = val(2n 1). The
possible periods of
y
les of the square map f (x) = x2 on sets of the form Zp=ps+1 Zp (s 1) are:
f
; l
m(n,
)pk r j r k < s;
= 1 or
= ordd2 for some odd divisor d of p 1g;
where l
m(n;
) is the least
ommon integer multiple of n and
.
Proof. Any
y
le of the doubling map g3 on pk Zp=ps+1 Zp lifts, via the exponential map, to an isomorphi
y
le of the square map on 1 + pk Zp=ps+1 Zp, of period given by (3.4). We have already
omputed the
possible periods of
y
les of g2 on F p (3.4). Finally,
y
les of f (x) = x2 on Zp=ps+1 Zp arise as produ
ts of
y
les of g2 and g3 , with periods equal to the least
ommon multiple of the two.
In parti
ular, the ith
oeÆ
ients of elements of a traje
tory under f" are periodi
, with (predi
table)
period linearly in
reasing with i. This information
an be used to generate random sequen
es from these
ith
oeÆ
ients; see, for example, [WS1998℄.
Remark 3.3. Those primes p for whi
h the value of r in Proposition 3.2 is stri
tly greater than 1 are
alled
Wieferi
h primes. They have been studied in
onne
tion with Fermat's Last Theorem (see [Silverman1988℄
and [Granville1985℄, for example). To date, extensive sear
h (see [CDP1997℄, for example) has revealed only
two Wieferi
h primes | 1093 and 3511 | and ea
h of these gives only r = 2. Nevertheless, there is as
yet no indi
ation that these are the only su
h, and in fa
t it seems possible that there be innitely many
Wieferi
h primes.
Let us now pro
eed to give a \global pi
ture" of the orbit spa
e of the square map on Q p , for any p.
By this we mean an understanding of the behaviour of the traje
tory of any point x0 2 Q p under repeated
appli
ations of the square map. Use the notation x1 = x20 , x2 = x21 , : : : , and xt for the t-th iterate of x0
under f .
Theorem 3.4. The square map on Q p has two xed points, 0 and 1. If x0 satises jx0 jp > 1, then its
traje
tory diverges to innity; if jx0 jp < 1, its traje
tory
onverges to 0.
Let jx0 jp = 1; then jxt jp = 1 for all t. If p = 2, then this traje
tory
onverges to 1; for p > 2, 1 is not
an attra
tive xed point. If x0 lies in the subgroup of Tei
hmuller representatives, its traje
tory be
omes
periodi
in nite time. The traje
tory of any other x0 is eventually quasiperiodi
and dense in some
ompa
t
open subset of Q p .
Proof. It remains for us to prove that, for p > 2, 1 is non-attra
tive, and that any element x0 whi
h is on
the unit
ir
le but not a Tei
hmuller representative has a traje
tory under f whi
h is dense in a
ompa
t
open subset of Q p .
DYNAMICS OF QUADRATIC MAPS ON Qp 8
As before, set n = ordp 2 and r = val(2n 1). For any z 2 pZp, write m = val(z ), and dene
[
n [
n
V (z ) = z (2l + pr Zp) = (2l z + pm+r Zp);
l=1 l=1
a union of open sets
ontained in the stratum pm Zp.
Lemma 3.5. The traje
tory of z 2 pZp under the doubling map g3 is dense in V (z ).
Proof. V (z ) evidently
ontains the full traje
tory of z under the doubling map. Let M be any integer
(greater than m + r, say). To prove the lemma it suÆ
es to show that the traje
tory of z meets every
neighbourhood z 0 + pM Zp, where z 0 2 V (z ). Now V (z ) pm Zp; identify pm Zp=pM Zp ' Zp=pM m Zp. By
(3.5), the iterates 2l z take on npM m r distin
t values modulo pM m Zp. Yet this is pre
isely the number
of elements in V (z ) mod pM Zp: ea
h of the n distin
t open sets 2l z + pm+r Zp of V (z )
ontain pM m r
elements modulo pM Zp.
We are now ready to address the traje
tories of an element u 2 1 + pZp under the square map, using the
ommutative diagram:
z7!2z
pZp ! p
x? ?? p
Z
log? yexp
u7!u2
1 + pZp ! 1 + pZp;
where the verti
al arrows are isomorphisms and homeomorphisms.
First dene V (u) = exp(V (log(u))). The traje
tory of u under the square map lies in V (u), and further,
by Lemma 3.5, this traje
tory is dense. In parti
ular, 1
annot be an attra
tive xed point.
We now turn to the general
ase of jx0 jp = 1. Use the isomorphism (3.2) to write x0 = (0; a0 ; z ), with
a0 2 Fp and z 2 pZp. By Lemma 3.1, repla
ing x0 with some iterate xt if ne
essary, we may assume that
a0 is an element of a
y
le of the square map in Fp . Enumerate this
y
le as S 0 = fa0 ; a1 ; : : : ; aq 1 g Fp ,
where q is the order of 2 modulo d, for some odd divisor d of p 1 (Lemma 3.1). Then the traje
tory of x0
lies densely in some subset of the open set S 0 V (z ) F p pZp, sin
e the traje
tory of z is dense in V (z ),
and S 0 is nite.
More expli
itly, set b = g
d(q; n) to be the greatest
ommon divisor of the periods of the two
y
les
(squares of a0 and powers of 2 modulo p). Then S 0 V (z ) Fp pZp
an be partitioned into b open
subsets su
h that ea
h
ontains the dense traje
tory of any of its nonperiodi
elements. This
ompletes the
proof.
possible, he
onstru
ts from any given
y
le a series of determinants whose valuations must be multiples of
the period.
We next have the following theorem, summarized here from the text of [TVW1989℄.
Theorem 4.2. Let f" (x) = x2 + ", with j"jp 1, and let x~ 2 Zp be su
h that f" (~x) = x~ and jf"0 (~x)jp = 1.
Set ! = f"0 (~
x) = 2~x, t the least integer su
h that !t 1 mod p, and = val(!t 1). Let be the least
integer greater than =t. Then the map f" is topologi
ally
onjugate to the linear map L(Æ ) = !Æ on the
neighbourhood x~ + p Zp.
As suggested in [TVW1989℄, it is easy to generalize their result and prove it for any
y
le of the map f" .
Doing so gives us the following theorem.
Theorem 4.3. Let f" (x) = x2 + ", with j"jp 1. Suppose p > 2, and that f" admits a primitive
y
le
O = fz0; z1 ; : : : ; z
1g. Set ! = (f"
)0 (z0 ), and let t be the least positive integer su
h that !t 1 mod p.
Let = val(! t 1), and let be the least integer greater than =t. Then the only periodi
points in the
union of the
osets zi + p Zp, 0 i <
, are those of the
y
le O.
Let us now pro
eed to our main theorem, the proof of whi
h will o
upy the remainder of this se
tion.
Note rst that sin
e f" is not a homomorphism of multipli
ative groups, the isomorphims (3.1) and (3.2) are
of no help here. Nevertheless, we have the following theorem, whi
h shows that f" , j"jp < 1, should indeed
be dynami
ally interpreted as a perturbation of the original square map.
Theorem 4.4. There are two xed points of f" , Æp;" and p;" , with jÆp;" jp = jp;" 1jp = j"jp < 1. Let
x 2 Q p . If jxjp > 1, then its traje
tory under f" diverges to innity; whereas if jxjp < 1, its traje
tory
onverges to Æp;" .
If p = 2, then the traje
tory of every x su
h that jxjp = 1
onverges to p;" . For all other p, if jxjp = 1,
then x is either a periodi
point, or its traje
tory is eventually quasiperiodi
. In many
ases, one
an
algorithmi
ally determine the nitely many periodi
points, and
al
ulate them to any degree of pre
ision. In
the remaining, very spe
ial,
ases, the algorithm may fail to terminate, leaving only an approximate pi
ture
of the orbit spa
e.
More pre
isely, let n = ordp 2. Given a primitive
-
y
le O of the square map in F p , if n does not divide
, then there exists a unique
orresponding fundamental
-
y
le of f" with leading
oeÆ
ients in O. Any
other periodi
element of f" with leading
oeÆ
ient in O is a harmoni
y
le, and must have a period whi
h
is a multiple of both
and n.
Those pairs (p;
) for whi
h n divides
above are
alled ex
eptional pairs (see Table 6.1). Those quadru-
plets (p; ";
; x) to whi
h our algorithm and Theorem 4.3 apply are
alled generi
; we give examples of
non-generi
quadruplets in Se
tion 6.
Proof. Our proof pro
eeds in several parts. In Part A, we
ompute the xed points of f" , and in Part B, we
determine the traje
tories under f" of all points x 2= Zp. In Part C, we
onsider the spe
ial
ase of p = 2,
where we nd no periodi
points besides the attra
tive xed points.
The rest of the proof is devoted to
onstru
ting an algorithm for determining all periodi
points of f" on
Zp, for p odd.
In Part D, we
onsider
y
les of period
, where
is the period of a
y
le of the square map on the residue
eld. We
onsider the
-th iterate of f" , or rather, the fun
tion
g
;"(x) = f"
(x) x;
and des
ribe the nonex
eptional and generi
quadruplets (p; ";
; x), i.e. those for whi
h fundamental
y
les
exist and admit no harmoni
s.
In Parts E and F, we ta
kle those
ases not treated in Part D. Spe
i
ally, for r;" 0 to be determined,
hoose a0 2 Zp su
h that g;" (a0 ) 0 mod p2r;" +1 . Write a1 ; a2 ; a3 ; : : : for the iterates of a0 under f" .
Then by the
hain rule,
(4.2) 0 (a0 ) = f 0 (a0 )f 0 (a1 ) f 0 (a 1 ) 1 = 2 a0 a1 a
g;" 1:
" " " 1
DYNAMICS OF QUADRATIC MAPS ON Qp 10
To
on
lude by Hensel's Lemma that there is an exa
t root of g;" (generally, a -
y
le of f" ) near a0 , r;"
0 (a0 )). Predi
ting this value r;" is the obje
t of mu
h of Part E. In Part F, we
must satisfy r;" val(g;"
des
ribe an algorithm for
omputing all remaining
y
les, and explain the
ir
umstan
es under whi
h it may
fail to terminate.
Finally, in Part G, we prove that the nonperiodi
elements are in fa
t quasiperiodi
.
A. Existen
e of xed points: A xed point x = f" (x) must satisfy
p
1 1 4"
x= :
2
If p = 2, then val(4") = 2 + val(") 3, so we may apply Hensel's Lemma (to the fun
tion g (x) = x2 1 4")
to dedu
e the existen
e of this square root. It takes the form 1 2"u, for some u 2 Z2. If p 6= 2, then
val(4") 1. Thus the p square root of 1 4" exists in Q p by Hensel's Lemma, sin
e 1 has a square root in
F p . Here, one obtains 1 4" = (1 + "v ), for some v 2 ( 2) + pZp. Setting u = v=2 and simplifying,
we obtain that for any p, the two xed points are
Æp;" = "u and p;" = 1 "u:
for some u 2 1 + pZp.
B. Traje
tories for jxjp 6= 1: It is
lear that jxjp > 1 implies jf" (x)jp = jxj2p > jxjp ; hen
e the traje
tory
of su
h an x diverges to innity. Now suppose that jxjp < 1. It follows that
8 2
<= jxjp if jxj2p > j"jp ;
>
jf" (x)jp = jx + "jp > j"jp if jxj2p = j"jp ;
2
We show that from this point on, the traje
tory approximates Æp;" .
Let m = val(") 1. Then sin
e f"n+1 (x) = (f"n (x))2 + ", and val(f"n (x))2 = 2m, we have f"n+1 (x) "
mod p2m . This last equivalen
e holds also for the xed point x = Æp;" ; hen
e in fa
t f"n+1 (x) Æp;" mod p2m .
To dedu
e that f"n (x)
omes arbitrarily
lose to Æp;" as n ! 1, we have only to note the following. Given any
y 2 Q p su
h that y Æp;" mod pk (and thus y 0 mod pm ), it follows that y2 Æp;" 2
mod pk+m . Hen
e
f" (y) Æp;"
2
+ " mod pk+m ; but as Æp;" is a xed point of f" , we
on
lude that f" (y ) Æp;" mod pk+m .
Clearly then, Æp;" is an attra
tive xed point, with basin of attra
tion equal to pZp.
C. Determination of the orbit spa
e for p = 2: Let a0 2 Z2 satisfy f"
(a0 ) a0 mod 2 for some
> 0. From equation (4.2), we dedu
e val(g
0 (a0 )) = 0 for all
, and so we make take r = 1 in Hensel's
lemma (Theorem 2.1). Consequently, there exists a unique z 2 Z2 su
h that g
(z ) = 0 and z a0 1
mod 2. Sin
e z = 2;" ts this
riterion, we dedu
e that, for p = 2, there are no periodi
points of f" besides
the xed points. Let us prove that 2;" is also attra
tive.
Let x = 1+s, with s 2 2Z2, be an arbitrary element of Z2. If jsj2 > j"j2 , then f" (x) = 1+2s+s2 +" = 1+s0 ,
with js0 j2 < jsj2 . On the other hand, if jsj2 j"j2 , then the same
al
ulation yields js0 j2 = j"j2 . Hen
e,
repla
ing x with f"n (x) (n > 0) if ne
essary, we may assume that jsj2 = j"j2 , and thus that x 1 + "
mod 2m+1 (m = val(")). As a parti
ular
ase, we dedu
e that 2;" 1 + " mod 2m+1 . It thus suÆ
es
to prove that if x 2 Z2 satises x 2;" mod 2k for some k > 1, then f" (x) 2;" mod 2k+1 . Write
x 2;" = 2k u, for some u 2 Z2. Then (x 2;" )2 = 22k u2 , whi
h implies
x2 + 22;" = 22;" x + 22k u2 = 22;" (2;" + 2k u) + 22k u2 = 222;" + 2k+1 2;" u0
for some u0 2 Z2. Subtra
t 222;" to
on
lude that f" (x) 2;" 0 mod 2k+1 , as required.
D. Fundamental
y
les, p odd, nonex
eptional pairs: For the remainder, suppose that p 6= 2
and set n = ordp 2. Choose
as in Lemma 3.1 and a
orresponding (primitive)
-
y
le of the square map
through a0 ; a1 ; : : : ; a
1 in F p (identied with arbitary preimages in Zp under the quotient map). Then, sin
e
j"jp < 1, f"
(a0 ) f0
(a0 ) a0 mod p, so the ai must approximate a (primitive)
-
y
le of the perturbed
square map f" as well. To dedu
e the existen
e of a true
-
y
le of f" with these leading
oeÆ
ients, we
DYNAMICS OF QUADRATIC MAPS ON Qp 11
x0 2 Zp. Then
0 0
0 (z0 ) = 2 (z 2 1 + "x) 1 = (1 + pr u)(1 + "x + pr +1 x0 ) 1 pr u + "x mod pr +1 Zp:
0 0
(4.5) g;" 0
0 0
So val(g;" (z0 )) r unless a
an
ellation o
urs in this nal sum. The o
uren
e of su
h a
an
ellation
denes the nongeneri
ase of our algorithm. Note that it depends not only on p, and ", but also on the
hoi
e of representatives zi of the approximate
y
le.
F. Remaining
y
les, p odd:
We are left with the following undetermined
ases:
1. existen
e of a fundamental
y
le for an ex
eptional pair (p;
) (where 2
1 mod p);
2. existen
e of harmoni
y
les;
3. existen
e of harmoni
s of harmoni
s.
The short answer to (1) is that it depends on ". For example, for the ex
eptional pair (p;
) = (251; 100),
there is a fundamental
y
le when " = 0 (of
ourse) but there is none when " = p. See Se
tion 6 for further
dis
ussion.
A suÆ
ient
ondition for nonexisten
e of (2) is given by Theorem 4.3. By (4.2) and (4.3), we have that
t = ordp ((f"
)0 (z )) = ordp (2
) = l
m(n;
) > 1:
0 (z )) as a spe
ial
ase of Part E above (taking =
t). It follows that for a
We estimate = val(g
t;"
non-Wieferi
h prime p, and a generi
quadruplet (p; ";
t; z ), the value = 1 and hen
e = 1. So in these
ases, Theorem 4.3 implies that the given fundamental
-
y
les have no harmoni
-
y
les for any .
A suÆ
ient
ondition nonexisten
e of (3) is given by Theorem 4.1, whi
h gives an upper bound on the
possible values of for whi
h -
y
les
an exist. (In parti
ular, we may dedu
e that a fundamental
y
le
admits at most two harmoni
y
les.) Moreover, any su
h must admit a fa
torization of the form (4.1).
DYNAMICS OF QUADRATIC MAPS ON Qp 12
To address the remaining
ases, we need to look for
y
les of f" on a set of representatives Rr;" of
Z
0 (z0 )). Here, z0 should be an element of the desired
p=pr;" Zp, where this r;" is an estimate for val(g;"
y
le or, equivalently, a suÆ
iently pre
ise estimate thereof. One obvious and easy set to use is
(4.6) Rrg = fn 2 Z j 1 n p2r;"+1 ; p - ng:
This suggests the following re
ursive pro
ess:
1. obtain an estimate for r;" ;
2. nd a -
y
le fz0 ; z1 ; : : : z 1 g in Rr;" ;
0 = val(g;"
3. evaluate r;" 0 (z0 )) dire
tly, using (4.2);
0
4. if r;" > r;" , return to Step 1 with r;" 0 in pla
e of r;" ; otherwise, evaluate the
y
le using Hensel's
Lemma.
This pro
ess fails to terminate exa
tly on a
y
le
ontaining a root of both g;" and g;" 0 .
Of
ourse, Theorem 4.3 still applies, and tells us that any harmoni
y
le must dier from the
or-
responding fundamental
y
le in the rst
oeÆ
ients, where = r
;" + 1 for ex
eptional pairs and
r
t;" =l
m(n;
) + 1 otherwise. (Their
oeÆ
ients mod p must agree, of
ourse.)
G. Quasiperiodi
ity: Finally,
onsider the
ase where jxjp = 1 and x is not periodi
. Repla
ing x with
some iterate under f" if ne
essary (as in Lemma 3.1), we may assume that its
onstant term a0 is an element
of a
y
le in the nite eld; denote the elements of this
y
le by a0 ; a1 ; a
1 . We wish to show that x is
a quasiperiodi
point, i.e., that for every N > 0, there exists an M > 0 su
h that f"M (x) lies in the
oset
x + pN Zp.
Consider the traje
tories of f" on the set of all
osets of pN Zp whose representatives have
onstant term
among a0 ; a1 ; ; a
1 . By Hensel's Lemma, applied to the polynomial hy (x) = f" (x) y , the inverse map
f" 1 exists and is well-dened on this set, sin
e f" (x) f" (y) mod pN implies x2 y2 mod pN . The
onstant terms are nonzero and have by denition unique square roots among the a0 ; a1 ; a
1 , so we
dedu
e that x y mod pn . Hen
e, the traje
tories of f" on this
oset spa
e are
y
les, and in parti
ular
there is some M > 0 su
h that f"M (x) 2 x + pN Zp.
This
ompletes the proof of Theorem 4.4.
5. Iterates of f" (x) = x2 + ", j"jp = 1
The orbit spa
e of the maps f" (x) = x2 + ", j"jp = 1 are drasti
ally dierent from those of the pre
eding
two se
tions; nevertheless, mu
h of the analysis whi
h permitted us a global general pi
ture there
arries
over to this boundary
ase. Note that examples of this
ase were
onsidered in [TVW1989℄.
As noted in [TVW1989℄, if jxjp > 1, then the traje
tory of f" through x diverges to innity. Thus the
question redu
es again to a
onsideration of the traje
tories in Zp.
Consider rst the traje
tories of f" on the residue eld F p . As f" is not equivalent to the square map in
p known general, uniform des
ription of this orbit spa
e. For example, not all f" admit
this
ase, there is no
xed points, sin
e 1 4" may or may not exist in Q p . However, the niteness of Fp implies the existen
e
of some
y
les. Insofar as
on
erns us, they fall into two
ategories.
The rst kind of
y
le is one whi
h
ontains the element 0 2 F p . (This is
alled an attra
tive
y
le in
[TVW1989℄.) Denote the elements of this
y
le fa0 = 0; a1 ; : : : ; a
1 g and
onsider g
;" (x) = f"
(x) x.
From (4.2), we dedu
e that val(g
;"0 (a0 )) = 0, sin
e the produ
t a0 a1 a
1 is 0 modulo p. Hen
e there
exists a unique
-
y
le of f" with these leading
oeÆ
ients; even more, this uniqueness (together with the
exa
tness of approximation modulo p) implies that there are no other
y
les (of any period) with these
leading
oeÆ
ients. In the terminology of the pre
eding se
tions: this
ase gives rise to a single fundamental
y
le, with no harmoni
s.
The se
ond kind of
y
le is one whi
h lies entirely in Fp , and is similar to those en
ountered in the proof
of Theorem 4.4. For j"jp = 1, however, the produ
t a0 a1 a
1 is not ne
essarily equal to 1 modulo p, sin
e
the analysis of (4.3) does not apply. Hen
e the valuation of g
;" 0 (a0 ) depends on the entire term in (4.2).
0
We have no a priori estimate of val(g
;" (a0 )) in this
ase. Nevertheless, a
oarser version of the analysis of
Parts D through F of the proof
an be applied. If val(g
;" 0 (a0 )) = 0, then the
y
le gives rise, via Hensel's
Lemma, to a unique
-
y
le in Zp. The only other possible periods of
y
les with leading
oeÆ
ients in the
DYNAMICS OF QUADRATIC MAPS ON Qp 13
set fa0 ; a1 ; : : : ; a
1 g are
m, where m is a multiple of the order of 2
a0 a1 a
1 modulo p, and where, by
Pezda's Theorem 4.1,
m admits a fa
torization of the form (4.1). To nd a
y
le of period , we use the
re
ursive algorithm from Part F of the proof as before.
Note that the quasiperiodi
ity argument in Part G of the proof of Theorem 4.4 goes through un
hanged
for j"jp = 1 and hen
e that under f" , all points in Zp are either periodi
or eventually quasiperiodi
.
6. Open Questions
In Se
tions 3 and 4 we laid the foundations for the theory of fundamental
y
les. One is immediately
stru
k by some open number-theoreti
questions.
For one: is there an easy way to determine the order n of 2 in F p ? The distribution of these orders is
well-known, up to the Generalized Riemann Hypothesis; but determining the value of n in any given
ase
remains diÆ
ult. Using the Legendre symbol, one knows that 2 2 1 mod p if and only if p 1 mod 8
p 1
[Serre1973, Ch.1℄; but while this is helpful it is not enough to determine n ompletely.
For another: whereas a formula for the number and period of the orbits of the square map on F p is known,
several related questions remain open. For example, set
(p) equal to the number of
y
les of the square
map on F p . It is
onje
tured that for ea
h n 2, their are innitely many primes with
(p) = n. (The
ase
of
(p) = 2
orresponds to Artin primes p, see [Rogers1996℄.) On the other hand, one expe
ts only nitely
many p for whi
h
(p) = 1 (Fermat primes). What ee
t does it have to repla
e
(p) with the number of
y
les of f" , " 2 Z, as p varies? Or with the maximum number of
y
les over all "?
Related to this is the following more detailed question. For whi
h ex
eptional pairs (p;
) (see Table 6.1)
and whi
h " does there exist a
y
le of the square map on F p whi
h fails to indu
e a
orresponding funda-
mental
y
le of f" on Q p ? And when there fails to be a fundamental
-
y
le, will there be a -
y
le, for
some multiple of
(this time not ne
essarily divisible by n)?
The
onsideration of this
lass of (large, easily
hara
terized) primes is potentially of interest in its own
right. In the
ontext of this paper, we
on
lude that these primes are the ones for whi
h the dynami
s of
the square map x 7! x2 are unstable under perturbations. (See, for instan
e, the example in Part F of the
proof of Theorem 4.4.)
Another open question, whi
h seems more analyti
than number-theoreti
in nature, is the existen
e of
an nongeneri
quadruplet (p; ; "; z0 ). Two sets of
ir
umstan
es
an lead to an innite re
ursion, but both
arise from the existen
e of
y
les of f" on Q p , say through the elements fz0 ; z1 ; : : : z
1 g, for whi
h
(6.1) ((f"
)0 )t = (2
z0 z1 z
1 )t = 1
exa
tly for some t > 0. If t = 1, this means that z0 is an exa
t root of both g;" and its derivative, and that
Hensel's Lemma is powerless. If t > 1, it follows that r
;" = 0 and that a fundamental
-
y
le exists | but
one
annot a priori determine what harmoni
s, if any, it admits. We
an understand why this must o
ur,
as follows. Suppose p 6= 2 and write
1
f"
(z + h) = f"
(z ) + h(f
)0 (z ) + h2 (f
)00 (z ) +
2
for the Taylor expansion of the polynomial at z . As f"
(z ) = 0, and (f
)0 (z ) = t , a t-th root of unity, we
an rewrite this as f"
(z + h) z + ht mod h2 Zp. Now iterate this expression t times, using the relations
f
(f
(z + h)) f
(z + ht ) z + h2t mod h2 Zp. We
on
lude that for all h,
f"
t(z + h) z + h mod h2 Zp:
This holds for any h 2 Zp; in other words, f"
t behaves approximately as the identity map. However, as
f" has only nitely many periodi
points, a
hieving a topologi
al
onjuga
y between f"
and the identity
map (the key ingredient to the proof of Theorem 4.3) is not possible. Thus, the nongeneri
ases are
truly distinguished by a
ondition that is highly unstable under perturbations of z0 and " | justifying our
suggestive terminology.
DYNAMICS OF QUADRATIC MAPS ON Qp 14
Table 6.1. The ex
eptional pairs (p;
) up to 1 108,
al
ulated using ARIBAS [ARIBAS℄.
Here, d denotes an odd divisor of p 1 (not given).
Unfortunately, neither of these
ases
an easily be distinguished from one in whi
h the equation (6.1)
holds only modulo ps Zp, for some large s > 0, ex
ept in spe
ial
ases, as follows.
Example 1. Let p = 3 and
onsider the map f" , with " = 43 = 1+p p (thus j"jp < 1). The xed point
z = 3;" = 1 12 p satises (2z )2 = 1 exa
tly. Hen
e this is an example of an \nongeneri
"
ase.
Example 2. Let p = 7 and
onsider a 2-
y
le fz0 ; z1 g of f" with leading
oeÆ
ients in the set f2; 4g. Then
" = z02 z0 1 and z1 = z0 1. This quadruplet (7; "; 2; z0) is nongeneri
exa
tly when (22 z0z1 )t = 1
for some t; here one
an take t = 3. Applying Hensel's Lemma to the fun
tion g (x) = 64x3 ( x 1)3 1
with approximate root x = 2, we nd a unique solution z0 (and hen
e a unique nongeneri
quadruplet).
The eorts of the pre
eding examples may be dupli
ated for any 2-
y
le or xed point; but for higher-
order
y
les, it is more diÆ
ult to nd an exa
t relation between " and z0 , and thus to isolate the nongeneri
ases algebrai
ally.
We are left with many unanswered questions. In what sense does the behaviour of f" around z dier
from its behaviour in the generi
ase? Does every prime p admit some
hoi
e of " for whi
h there is a
y
le
satisfying (6.1)? How
an we nd su
h "? Do we dare imagine that they are in some sense boundary values,
su
h that the behaviour of the quadrati
maps fÆ
an be predi
ted by the relation of Æ to "?
Referen
es
[AKT1999℄ Sergio Albeverio, Andrei Khrennikov, Brunello Tirozzi, p-adi
dynami
al systems and neural networks, in: Math.
Models Methods Appl. S
i. 9 (1999), no. 9, 1417{1437.
[ARIBAS℄ ARIBAS, written and distributed by Otto Forster, 1996. See:
http://www.mathematik.uni-muen
hen.de/~forster/sw/aribas.html
[Ben-Menahem1988℄ S. Ben-Menahem, p-adi
Iterations, preprint Tel-Aviv UP (1988) 1627{88.
DYNAMICS OF QUADRATIC MAPS ON Qp 15
[Benedetto2000℄ R. Benedetto, p-adi
dynami
s and Sullivan's no wandering domain theorem, in: Compositio Mathemati
a,
122 (2000) 281{298.
[CDP1997℄ Ri
hard Crandall, Karl Di
hler and Carl Pomeran
e, A Sear
h for Wieferi
h and Wilson Primes, in: Mathemati
s
of Computation 66, No. 217 (1997), 433{449.
[DK1999℄ Stany De Smedt, Andrew Khrennikov, A p-adi
behaviour of dynami
al systems, in: Rev. Mat. Complut. 12 (1999),
no. 2, 301{323.
[Devaney1989℄ Robert L. Devaney, An Introdu
tion to Chaoti
Dynami
al Systems, 2nd ed., Addison-Wesley, 1989.
[DGKS1999℄ Daniel Dubis
har, Volker Gundla
h, Andrei Khrennikov, Oliver Steinkamp, Attra
tors of random dynami
al
systems over p-adi
numbers and a model of "noisy"
ognitive pro
esses, in: Phys. D 130 (1999), no. 1-2, 1{12.
[Eisenbud1995℄ David Eisenbud, Commutative Algebra with a View Toward Algebrai
Geometry. Springer-Verlag, New York,
1995.
[Granville1985℄ A.J. Granville, Rening the
onditions on the Fermat quotient, in: Math. Pro
. Cambridge Philos. So
. 98
(1985), no 1. 5{8.
[Koblitz1984℄ Neal Koblitz, p-adi
Numbers, p-adi
Analysis and Zeta-Fun
tions, Se
ond Edition. Springer-Verlag, New York,
1984.
[Hsia1996℄ L. Hsia, A weak Neron model with appli
ations to p-adi
dynami
al systems, in: Compos. Math., 100 (1996) 277{304.
[Li1996℄ Hua-Chieh Li, p-adi
periodi
points and Sen's theorem, in: J. Number Theory, 56 no. 2 (1996), 309{318.
[Lubin1994℄ Jonathan Lubin, Nonar
himedean dynami
al systems, in: Compositio Math., 94 no. 3 (1994), 321{346.
[Morton1992℄ Patri
k Morton, Arithmeti
properties of periodi
points of quadrati
maps, in: A
ta Arithmeti
a, LXII.4 (1992)
343{372.
[MS1994℄ Patri
k Morton and Joseph H. Silverman, Rational periodi
points of rational fun
tions, in: Internat. Math. Res.
Noti
es, 2 (1994) 97{110.
[MV1995℄ P. Morton and F. Vivaldi, Bifur
ations and dis
riminants for polynomials maps, in: Nonlinearity 8 (1995) 571{584.
[Narkiewi
z1997℄ W. Narkiewi
z, Arithmeti
s of Dynami
al Systems, A Survey, in: Tatra Mountains Math. Publ. 11 (1997)
69{75. 1998.
[Neukir
h1986℄ Jurgen Neukir
h, Class Field Theory, Grundlehren der mathematis
hen Wissens
haften 280, Springer-Verlag,
1986.
[Pezda1994℄ T. Pezda, Polynomial
y
les in
ertain lo
al domains, in: A
ta Arithmeti
a, LXVI.1 (1994) 11{22.
[Rogers1996℄ Thomas D. Rogers, The Graph of the Square Mapping on the Prime Fields, in: Dis
rete Mathemati
s 148 (1996)
317{324.
[Serre1973℄ Jean-Pierre Serre, A Course in Arithmeti
, Springer-Verlag, New York, 1973.
[Silverman1988℄ Joseph H. Silverman, Wieferi
h's
riterion and the ab
-
onje
ture, Journal of Number Theory 30 (1988) no
2, 226{237.
[Silverman1996℄ Joseph H. Silverman, Rational Fun
tions with a Polynomial Iterate, in: Journal of Algebra 180 (1996) 102{
110.
[SR1988℄ M. Shirvani and T.D.Rogers, Ergodi
Endomorphisms of Compa
t Abelian Groups, in: Commun. Math. Phys. 118
(1988) 401{410.
[SR1991℄ M. Shirvani and T.D.Rogers, On Ergodi
One-Dimensional Cellular Automata, in: Commun. Math. Phys. 136 (1991)
599{605.
[TVW1989℄ E. Thiran, D. Verstegen and J. Weyers, p-adi
Dynami
s, in: Journal of Statisti
al Physi
s, Vol. 54, Nos 3/4
(1989) 893{913.
[Verstegen1990℄ D. Verstegen, p-adi
Dynami
al Systems, in : Number Theory and Physi
s (J.-M. Lu
k, P.Moussa and M.
Walds
hmidt, eds.) Springer Pro
eedings in Physi
s, Springer (Berlin), Vol. 47 (1990) 235{242.
[Vivaldi1992℄ F. Vivaldi, Dynami
s over irredu
ible polynomials, in: Nonlinearity 5 (1992) 941{960.
[WR1994℄ Ralph Walde and Paula Russo, Rational Periodi
Points of the Quadrati
Fun
tion Q
(x) = x2 +
, in: Amer.
Math. Monthly, Vol 101 (1994) 318{331.
[WS1998℄ Christopher Wood
o
k and Nigel P. Smart, p-adi
Chaos and Random Number Generation, in: Experimental Math-
emati
s 7:4 (1998) 333{342.
[Zieve1996℄ M. Zieve, Nonar
himedean dynami
al systems and their appli
ations, Ph..D. thesis, UC Berkeley, 1996.
E-mail address : mnevinsalum.mit.edu, tdrogersgpu.srv.ualberta.
a
Department of Mathemati
s and Statisti
s, University of Ottawa, Ottawa, Canada K1N 6N5; and Department
of Mathemati
al S
ien
es, University of Alberta, Edmonton, Alberta, Canada T6G 2G1