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

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

The discrete catmap f:T[N²]->T[N²] 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²=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ⁿ⁺¹)=p*h(pⁿ) 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²=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

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²-3X+1=0. It is now possible to find the roots by completing the square.

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²,M³,M⁴ etc are all numbers between 0 and N-1. There are at most N⁴ such quadruples a,b,c,d. This means that two matrices in the sequence M,M²,M³ .... M^k must be equal when k > N⁴. 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ⁿ⁺¹) to h(pⁿ) where p is prime.

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

This yields M^pd = 1 (mod pⁿ⁺¹) 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ⁿ⁺¹) shows that h(pⁿ⁺¹) always divides p*h(pⁿ). This means h(pⁿ⁺¹) <= p*h(pⁿ). 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:-

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

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², ... 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²=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ⁿ⁺¹ = a Mⁿ + 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.

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

getting roots s and t. The general term is A sⁿ +B tⁿ where A and B are determined by the initial conditions

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

The powers of the matrix 1, M, M², M³ ... 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²=1, the identity transformation. Here a and b are elements of GF(p) and the new field is GF(p²). GF(p²) is obtained from GF(p) by adjoining the roots of any quadratic equation. It has a Galois Group {1,R} with R²=1. This is the same as the group Z2 where 1+1=0.

GF(p²) has p²-1 non zero elements, so all non zero elements satisfy x^(p²-1)=1 or x^(p²)=x. Consider the mapping F: x -> x^p. This is called the Frobenius endomorphism. The result x^(p²)=x shows that F(F(x))=(x^p)^p=x(p²)=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

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.

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.