In the 1960s Vladimir Arnold described the effect of a certain transformation of the torus into itself. He used a picture of a cat as the starting image. This page uses a picture of Polly, a tabby cat to illustrate the same mapping. It can also be seen that changing the size of the image changes the period of the transformation. Here is a section of the table giving image size and period for the descrete catmap. Adding a single pixel border can drastically change the period. Click on the image specification to see the catmap.

- 148 114
- 149 74
- 150 300 Long Period
- 151 25
- 152 18 Short Period
- 153 36
- 154 120 Intermediate Period
- 155 30

The Discrete catmap is a mapping f from the set NxN to NxN where N is the set of numbers 0,1,2...,n-1 for a given modulus n. The mapping moves an X,Y point to another point given by

X <-2X+Y (mod n)Y <-X+Y (mod n)

This can be written in matrix vector form as (X,Y)-> M(X,Y) where M is the 2x2 matrix

(2 1)(1 1)

The discrete catmap f:T[N^{2}]->T[N^{2}] has a period d such that
f^{d} = 1. This period d(N) is a function of N and the wikipedia page
gives a reference to a proof by Freeman Dyson and Harold Falk that
states that d(n) < 3n. Brute force computation of d(n) shows that
that d(mn) = LCM (d(n), d(m)) where m and n are
relatively prime. Here LCM(x,y) is the least common multiple of x and
y. With the help of a computer you can make a
table of valuesof the orbit
length for given values of image size. The table
shows several interesting features, Let the order of M (mod n) be h(n).
h(n) is the least integer d so that M^{d} = 1 (mod n). The table shows
the number n, the function h(n), and the number of roots for the
equation x^{2}=5 (mod n). An aristerisk denotes that the number n is
prime. If m,n are relatively prime the first few values seem to show
that f(mn) = f(m)f(n). A function from non zero integers to
a subset of the complex numbers is called a multicative function
if f(mn)=f(m)f(n) holds for all relatively prime m,n. The function
h(n) is not quite multiplicative because h(9)=12, h(2)=3 but h(18)=12.
In fact h(mn)=LCM(h(m),h(n) whereLCM(x,y) is the least common multiple
of x and y. Next it is seen then when n has the values 2 4 8 16 32 the
values of h(n) are 3 3 6 12 24 and the values for n = 3 9 27 81 are
4 12 36 108.
More generally h(p^{n+1})=p*h(p^{n}) where p is prime and n is an exponent.
Next it is seen that if p is an odd prime, excepting 5 then either
h(p) divides p-1 or h(p) divides p+1. The choice of p-1 or p+1 depends
on whether x^{2}=5 (mod p) has a root.

Freeman Dyson and Harold Falk wrote an article showing that h(n)<3n. Examining the worst cases in the table shows that h(n)=3n for n=10. Back at the time of the French Revolution, Langrange found out that the Fibonacci sequence (mod 10) started to repeat itself after 60 terms. The number five (5) is special in this problem.

The ideas used to provide a proof can be found in a couple of books written by Carl Sabbagh and Simon Singh. Both books give a discussion of prime numbers and series. Simon Singh describes the proof of Fermat's Last Theorem (FLT), while Karl Sabbagh's book, Dr Riemann's Zeros describes an intractable problem in number theory and complex analysis. Niether Karl Sabbagh nor Simon Singh are professional mathematicians, but they defied publishing conventions by putting plenty of equations into their books. Currently Simon Singh is defending himself from lawyers set on him like mad dogs by an organisation representing those that oversell alternative medicine. Carl Sabbagh defends the rights of his fellow Palestinians whenever he can.

Popular books by professional mathematicians often have a lower equation count. This is a shame really, because many post graduate maths texts are so dense, and they assume so much prior knowledge that it is hard to get past the first three pages following the introduction. The catmap (X,Y)->(2X+Y, X+Y) is a member of a special group called SL(2, Z) or the special linear group over Z. This is the set of all 2x2 integer matrices with elements a,b,c,d with ad-bc=1. SL(2,Z) is kid's stuff. Any child learning matrix algebra will start off with 2x2 matrices, and if the teacher is gentle, then the first few matrices will have a determinent (ad-bc) of exactly 1 just to avoid messy division. Despite the simplicity of this group whole books have been written about it. For the catmap problem we are looking at the powers of one particular matrix, (mod N) where N>1. Books about SL(2,Z) will describe algebraic varieties and modular functions. They normally assume the reader is thoroughly familiar with Groups, Rings, Modules, Fields, and Vector spaces. Analytic functions are usually mentioned along with Riemann Surfaces. Applied scientists are interested in all of these things nowadays. Much of chemistry and materials science depends on the properties of a group called SO(3,R).

Karl Sabbagh mentions Freeman Dyson's interest in number theory. Karl Sabbagh also gives several appendices in his book on Dr Reimann's Zeros. One of these is about eigenvectors and eigen values. This is just what is required to prove that h(n) <= 3n for all n, and indeed that h(n)< 2n for most n.

The eigenvalues of the 2x2 matrix M with elements a,b,c,d are the roots of the equation det (M-tI) = 0 where the determinant of a 2x2 matrix (a,b,c,d) is the difference ad-bc and I is the 2x2 matrix with 1's on the diagonal, and zero elsewhere. This equation is called the characteristic equation and its form is

(a-t)(d-t)-bc = t Notice that we can make the last simplification whenever
the matrix is in SL(2,Z). Next we can use the Cayley Hamilton
theorem that says that every matrix satisfies it's own characteristic
equation. For the catmap, the equation is X^{2}-3X+1=0. It is now
possible to find the roots by completing the square.

add (3/2)^2 = 9/4 to each side: X

Write the left side as a square: (X-3/2)^2 = 5/4

Take sqare root of each side: X-3/2 = + or - sqrt(5)/2.

This gives two solutions s=3/2-sqrt(5)/2 and t= 3/2+sqrt(5)/2. Notice that st=1.

Consider the powers of M when M is reduced modulo N for some number
N. The elements of M and its powers M,M^{2},M^{3},M^{4} etc are all numbers
between 0 and N-1. There are at most N^{4} such quadruples a,b,c,d.
This means that two matrices in the sequence M,M^{2},M^{3} .... M^{k} must
be equal when k > N^{4}. We have some equation M^{j} = M^{k}. We also
know that any matrix in SL(2,Z) has an inverse since the transformation
(X,Y)->(2X+Y,X+Y) may be back solved to give the inverse transform
(X,Y)->(X-Y,-X+2Y). write Inv(M) for the inverse of M. If M^{j}=M^{k}
then multiply both sides by (Inv(M))^{j} to get 1=M^{k-j}. This means that
M^{d}=1 for some d. We also have Inv(M)=M^{d-1}. This is true whether
or not N is prime. The matrix inverse of M is sometimes written M^{-1}.

When p is an odd prime the formula for the roots of the characteristic equation which contains the quantities 3/2 and 1/2 can easily be reduced (mod p). the number k=(p+1)/2 is an inverse for 2 (mod p) with 2k=1 (mod p) so 1/2 is k and 3/2 is 3k (mod p). For example 2*4=8 so 2*4=1 (mod 7) and 4=(7+1)/2 is a multiplicative inverse of 2 (mod 7). Just as Simon Singh described in the proof of Fermat's Last Theorem there are 'good' and 'bad' primes for the catmap problem. The 'bad' primes are 2 and 5.

Before dealing with 'good' and 'bad' primes there is a useful
recurrence formula which may be proved by induction. This relates
h(p^{n+1}) to h(p^{n}) where p is prime.

The proof is by induction. If we know that M^{d} = 1 (mod p^{n}) then
M^{pd} = 1 mod p^{n+1}. Working in SL(2,Z) we write the first part of
the assertion as M^{d} = 1 (mod p^{n}) as M^{d}=1+(p^{n})*A. A is an integer
2x2 matrix, and the number p^{n} is taken as a scalar multiplier.
It is now possible to use the Binomial Theorem to raise 1+(p^{n})A to
the p-th power. The binomial expansion looks like this:

M

This yields M^{pd} = 1 (mod p^{n+1}) as required. This proof works despite
the fact that SL(2,Z) is not commutative and AB is not necessarily the
same as BA. The reason is that the identity matrix along with powers of
a single matrix does form a commutative ring. A^i times A^j is always
A^i+j and the order of multiplication is unimportant. Getting the
result M^{pd} = 1 mod (p^{n+1}) shows that h(p^{n+1}) always divides p*h(p^{n}).
This means h(p^{n+1}) <= p*h(p^{n}). Since I only want to prove h(n) <= 3*n
it is not necessary to prove equality, and indeed the non existant jump from
h(2) to h(2^2)=h(4) = 3 shows that equality is not always the case.

It is also possible to use this method to prove that when x is prime
then x^{p} = x (mod p). Use the binomial expansion:-

(x+y)

The middle terms cancel out because the binomial coefficients p(p-1)...(p-k+1)/k! are all divisible by p. p divides the numerator, but not the denominator, because p has no factors less than p. Substitute x=y=1 in the expression to get

2Now use 3=1+2 to get 3

It is possible to use (x+y)^{p} = x^{p}+y^{p} as a basis for a proof
by induction that x^{p}=x for all x : 1<=x<=p-1. This is also called
Fermat's Theorem. Since x is non zero we can divide once by x to
get:-

To prove h(p) < 3p for odd p it is easiest to turn to Galois Theory.
Simon Singh's book on FLT gives a decent account on the life and work
of Jean Evariste Galois. Galois worked on Groups and Fields, and linked
the two concepts with a theory of equations. A field is a set of numbers
with addition multiplication and division. The set of numbers modulo p
is a field called Zp, or GF(p), the Galois prime field of order p.
It is possible to add and multiply numbers, and then take the remainder
modulo p. The non-zero elements of Zp may be multiplied together. If
1 <=a <=p-1 then the set of numbers ax with 1<=x<=p-1 is also a subset
of non-zero elements (mod p). The mapping x->ax is a one to one mapping
since ax=ay implies a(x-y)=0 mod p. This means p must divide x-y so
x=y (mod p). The ability to cancel a from the equation a(x-y) follows
from the fact that p is prime, and a is non zero modulo p. a(x-y)=0
(mod p) is the same as saying a(x-y)=kp and p divides either a or x-y.
p must therefore divide x-y. The set of numbers { ax } therefore
includes all non zero elements of Zp, including 1. This means that
there is an x with ax=1 (mod p). This number can be written for 1/a
in fractions. Write Zp* for the non zero elements (mod p). Zp is a
set with multiplication, a unit element 1 such that a*1 =1*a=a and
for each a an inverse element 1/a with a*1/a = 1. This means Zp*
is a group, with p-1 elements. Given any a non zero mod p the
set of elements 1,a,a^{2}, ... a^{d-1} where a^{d}=1 is a subgroup of Zp.
An old theorem going back to Lagrange says that the size of a
subgroup H of a group G divides the size of G. This is often
written |G| = |H| (G:H) where the number G:H is the index of H in
G.

We know that M satisfies a quadratic equation.
This means that M^{2}=aM+b for some a and b in Zp. The same goes for
other powers of M powers of M satisfy the recurrence relation
M^{n+1} = a M^{n} + b M^{n-1}. M and its powers are 2x2 matrices, with
elements m[00][n] m[01][n] m[10][n] and m[11][n]. Each entry satisfies
the recurrence relation X[n+1]-3X[n]+X[n-1]=0. In a finite field such
a recurrence relationship must give rise to a sequence which repeats
itself. Such reurrence relations were known hundreds of years ago.
The simplest is the Fibonacci sequence 1 1 2 3 5 8 13 21 .... where
each term is the sum of the two previous terms.

Rearranging gives: F[n+1]-F[n]-F[n-1] = 0

There is a formula for general term of such a sequence. To solve the recurrence relation X[n+1]-a X[n] + X[n-1] you first solve the quadratic equation

X
getting roots s and t. The general term is A s^{n} +B t^{n} where
A and B are determined by the initial conditions

n=1: As + Bt = X[1]

If s=t things get nasty but a general solution may still be found.
This is X[n] = (A+Bn) t^{n}.

The powers of the matrix 1, M, M^{2}, M^{3} ... start to repeat when
the recurrence relation satisfied by the matrix entries repeats.
The recurrence relation has a period d where d is the number such that
s^{d} = 1 and t^{d} = 1 (mod p). The values of s and t for the catmap
matrix are s= 3/2-1/2 sqrt (5) and t = 3/2 + 1/2 sqrt(5). We know
that st=1 or s=1/t so s^{d}=1 implies t^{d}=1 and vice versa. If s and t
are in Zp = GF(p) we know that s and t have a period d which divides
p-1.

The case where sqrt(5) is not in GF(p) is harder. Galois theory gives a method of adjoining the roots of an equation to a smaller field and then analysing the symmetries of the larger field. These symmetries are called the Galois Group.

In the case of a quadratic extension (add roots of a quadratic equation)
there is only one symmetry transformation which consists of swapping
the roots. R: a + bs -> a + bt. Notice that R^{2}=1, the identity
transformation. Here a and b are elements of GF(p) and
the new field is GF(p^{2}). GF(p^{2}) is obtained from GF(p) by adjoining
the roots of any quadratic equation. It has a Galois Group {1,R} with
R^{2}=1. This is the same as the group Z2 where 1+1=0.

GF(p^{2}) has p^{2}-1 non zero elements, so all non zero elements
satisfy x^(p^{2}-1)=1 or x^(p^{2})=x. Consider the mapping F: x -> x^{p}.
This is called the Frobenius endomorphism. The result x^(p^{2})=x shows
that F(F(x))=(x^{p})^p=x(p^{2})=x so F^2=1. The group {1,F} is isomorphic
to the Galois Group {1,R}, and so F must also swap the elements s,t.
Notice that the relation st=1 shows that R(s)=1/s. The same goes for
F(s) so we have

This implies s

The last result shows that the order of s and t is at most p+1.
This means h(p) <= p+1 when 5 is not a square in Zp. It is also
possible to prove that s^{p} = 1/s using the theory of Quadratic residues
invented by Gauss. It makes a better story to refer to Galois Theory
because while Gauss is noted for his reticence in publishing his results
it can be said that the efforts of Galois to find a publisher were truly
catastrophic. His failed efforts were followed by a period of reckless
behaviour which resulted in his death in a duel at the age of 20.
Galois Theory is now quite a popular subject in university maths courses.

To summarize the main steps in the proof that the catmap transformation has order h(n) with h(n)<=3n use the following results.

When m,n are relatively prime then h(mn) <= LCM(h(m), h(n))h(p

Compute a few bad cases h(2),h(4),h(5).

Show h(p) divides p-1 when p is prime and x

Show h(p) divides p+1 when p is prime and x

It may appear that if n is a product of many primes where h(p)=p+1 then h(n) could become much larger than n. This is not the case because p+1 and q+1 have the common factor 2 for any pair of such primes. This means h(pq) <= (p+1) (q+1) / 2.

back to the top