The ghosts of the cat

Ehrhard Behrends

Abstract

Let A ∈ SL(2, ZZ) be given and n ∈ N I . A induces a map A_{n} on ZZ_{n}^{2} by (x, y) ⟼ (a_{11}x + a_{12}y, a_{21}x + a_{22}y) mod n. A_{n} can be thought of as a discrete approximation of the similarly defined map on the unit square. It is known that the A_{n} have a surprisingly small period: there always is an r ≤ 3n such that A_{n}^{r} is the identity on ZZ_{n}^{2}.

One can visualize the properties of the iterates of A_{n} by considering the sets P, A_{n}P, A_{n}^{2}P, … for a fixed subset P of ZZ_{n}^{2}. (Here the cat comes into play: P has often been chosen to be the digitalized picture of a cat, in particular when treating the special case of the Anosov map A = \binom{21}{11}.) It turns out that in the sequence (A_{n}^{k}P)_{k} mostly “chaotic” pictures occur as one would expect. But also there can be observed some kind of regular behaviour for certain powers A_{n}^{k} before the end of the period.

It is the aim of the present paper to describe these phenomena and to explain why and how they occur. In order to quantify the chaotic behaviour of the maps on ZZ_{n}^{2} under consideration we introduce suitable functions.

Our methods are elementary. Only basic results from the geometry of numbers will be used.

1. Introduction

The Anosov map (x, y) ⟼ (2x + y, x + y) mod 1, defined on the unit square, plays an important rôle in the theory of dynamical systems. The discrete variant (x, y) ⟼ (2x + y, x + y) mod n on ZZ_{n}^{2} can be thought of as an approximation; it corresponds to the restriction of the Anosov map to the subset of pairs of rational numbers with denominator n. It was observed in [3] that in the discrete case the periods are surprisingly small which is in marked contract to the fact that on the square the map is ergodic. A new proof of this fact as well as the discussion of the corresponding case for arbitrary matrices in SL(m, ZZ) can be found in [1]. The reader who is interested in more detailed information on the Anosov map and some literature concerning the importance of its discrete approximation to quantum chaos is referred to this paper.

Here we are interested in what happens before the end of the period. To illustrate the phenomena we are going to describe we will sketch the images of certain digitalized pictures with respect to the iterations of the map under consideration (all these sketches can be found in the appendix). We will restrict ourselves to three pictures:

1) A “square” Sqr_{n} (the set of (i, j) ∈ ZZ_{n}^{2} such that 3 ≤ i, j ≤ [\frac{n}{2}].

2) A “cat” Cat_{n} (a sketch in a 16 × 18–rectangle)

3) A cross Cro_{n} consisting of the (i, j) in ZZ_{n}^{2} such that either i = j or i + j = (n − 1) mod n .

These can be found in fig. 1 of the appendix for the case n = 30.

In fig. 2 we sketch the P, A_{n}P, A_{n}^{2}P, … for the case of the Anosov map, n = 29, and P = Cat_{29}. The choice n = 29 is motivated by the fact that the period here is very small. One might expect that what can be seen in this case is typical in that the iterates produce patterns which tend to be more and more “chaotic” until, after the middle of the period, they in turn become more and more “regular” leading finally to the original pattern. But this is far from being true. Investigating various other examples one finds that before the end of the period pictures occur which are by no means chaotic. It turns out that one has to distinguish two cases.

Patterns of type I: One starts with a picture like Sqr_{n} or Cat_{n} built up essentially form “blocks” {(i, j) | i_{0} ≤ i ≤ i_{0} + r, j_{0} ≤ j ≤ j_{0} + r}, where the numbers r are not too small compared with n.

Patterns of type II: The relevant information is given by certain lines as in Cro_{n}.

(For simplicity we will not consider mixtures of these two cases.)

And here are the phenomena we are going to investigate.

Phenomena in case I: We will concentrate on the following.

I.1 The clusters: Consider e.g. the fifth iteration of Sqr_{28} with respect to the Anosov map which we will denote by A_{28}^{5}(Sqr_{28}) (fig. 3). It is not “chaotic” but consists of a number of clusters. There are 29 of them (here and in similar cases one has to take into account that we are calculating mod n so that, e.g., (i, 0) is adjacent to (i, n − 1)). A_{28}^{5} (Cat_{28}) looks quite similar (fig. 4): the same number of clusters, and whereas the individual ones look differently the pattern is the same. Thus it is apparent that the phenomenon is caused essentially by the particular from of the map and that the initial picture is of less importance. Note however that A_{28}^{5} (Cro_{28}) shows no similar behaviour (fig. 5) which indicates that the distinction between case I and case II is reasonable. The relevant map here is induced by the matrix \binom{21}{11}^{5} mod 28 = \binom{5 27}{27 6} =: A_{28,5}, acting on ZZ_{28}^{2}. We will explain in section 2 why and how the particular entries of A_{28,5} give rise to precisely the clusters observed.

I.2 The ghosts: This is a little bit more spectacular. As an example we have chosen the 12th iterate in the case n = 45. Fig. 6 provides A_{45}^{12}(Sqr_{45}), A_{45}^{12}(Cat_{45}), and A_{45}^{12}(Cro_{45}), respectively. Whereas the first two undoubtedly are some kind of “ghosts” of the original pattern nothing similar can be said of the third. Therefore as in I.1 it only seems to be of importance whether case I applies or not. The number of the ghosts (5 in this example) and how they are placed is seemingly an invariant only depending on the entries of A_{45,12} = \binom{21}{11}^{12} mod 45 = \binom{10 18}{18 37}.

See Section 3 for a discussion.

Phenomena in case II Also in this case very different degrees of chaotic behaviour are apparent. As an example consider A_{31}^{8}(Cro_{31}) and A_{31}^{10}(Cro_{31}) in fig. 7. How this phenomenon can be concluded from the matrices A_{31,8} = \binom{16 26}{26 21} and A_{31,10} = \binom{3 7}{7 27} will be discussed in section 4.

Clusters, ghosts and lines showing different degrees of chaotic behaviour were first observed in the course of computer simulations. These experiments also gave rise to various observations which now – having understood how the different patterns arise – can be explained. Here is a sample:

• If one starts with a fixed pattern P, then it is likely that in the sequence P, AP, … clusters (or ghosts) can be observed in a number of consecutive steps; i.e. if A^{k}P shows clusters then A^{k+1}P often does also.

• The number of clusters, if there are any, is always ±1 mod n.

• It is much more likely to observe ghosts in the case of composed numbers n than in the case of prime numbers.

Whereas our illustrations always use the Anosov matrix \binom{21}{11} our results apply to arbitrary A ∈ SL(2, ZZ). The sections 2, 3, 4 contain, as already mentioned, mainly the necessary facts to explain the phenomena Ia, Ib and II and the discussion of some consequences. Also in section 5, we introduce two functions in order to have a measure of how “chaotic” the mappings under consideration are.

2. Clusters

To begin with we remind the reader to an elementary fact concerning lattices in ZZ^{2}. Let x_{1} = \binom{x_{11}}{x_{12}}, x_{2} = \binom{x_{21}}{x_{22}} ∈ ZZ^{2} be linearly independent and L := \{ax_{1} + bx_{2} | a, b ∈ ZZ\}. L is called the lattice generated by x_{1} and x_{2}. Crucial for that what follows will be that the quotient ZZ^{2}/L has precisely | det (x_{1}, x_{2})| = |x_{11}x_{22} − x_{21}x_{12}| elements. This is proved, e.g., in [2] or [7].

Now let B = \binom{b_{11} b_{12}}{b_{21} b_{22}} ∈ SL(2, ZZ) be arbitrary and suppose that there is given a pattern P in ZZ^{2} of type I. Suppose further that x_{1} := B^{−1}\binom{1}{0}, x_{2} := B^{−1}\binom{0}{1} are small compared with P.

If x_{0} and x_{0} + x_{1} are in P then, since Bx_{1} = \binom{1}{0}, these points are mapped by B to adjacent points. The same happens with x_{0} and x_{0} + x_{2}, with x_{0} + x_{1} and x_{0} + x_{1} + x_{2}, and so on. With other words, P ∩(x_{0}+L) is mapped under B to a set which is a cluster as observed in I.1. It is easy but here not necessary to give this fact a more rigorous form, the necessary definitions (e.g. connectedness) for subsets of ZZ^{2} are provided by a theory called digital topology (see [4] or [6]).

If x_{0} and x̂_{0} are such that x_{0} +L and x̂_{0} +L are disjoint then B might map P ∩(x_{0} +L) and P ∩(x̂_{0}+L) so sets which are not adjacent. By the result mentioned at the beginning of this section the maximal number of points x_{0} one can choose such that the associated sets x_{0} + L are pairwise disjoint is precisely | det (x_{0}, x̂_{0})|. Therefore this is the number of clusters in B(P).

Let’s now turn from ZZ^{2} to ZZ_{n}^{2}. The idea is to apply a local version of what has been done before to the new situation. To be more precise, let x_{0} = \binom{x_{01}}{x_{02}} ∈ ZZ_{n}^{2} be given such that 0 < x_{01}, x_{02} < n − 1. Further suppose that there are vectors x_{1} = \binom{x_{11}}{x_{12}}, x_{2} ∈ \binom{x_{21}}{x_{22}} ∈ ZZ^{2} such that Bx_{1} = \binom{1}{0} mod n, Bx_{2} = \binom{0}{1} mod n and such that the |x_{ij}|, i, j = 1, 2 are small compared with n. Then what has been done before can now be repeated for {x_{0} + ax_{1} + bx_{2} | a, b ∈ ZZ, 0 ≤ x_{0i} + ax_{1i} + bx_{2i} ≤ n − 1 for i = 1, 2}. x_{1} and x_{2}, being the inverse images under B of the unit vectors, have as components precisely the entries of the matrix B^{−1}. Since B has determinant 1 this means that, modulo n, x_{1} = \binom{b_{22}}{−b_{21}}, x_{2} = \binom{−b_{12}}{b_{11}}.

But for us it is important whether in the equivalence classes of x_{1} and x_{2} are representatives of absolute value small relative to n. Therefore we introduce the following notation: For n ∈ N I fixed and x ∈ ZZ let x^{∗} be that number in x + nZZ which has the smallest possible absolute value. To put it otherwise, x^{∗} ist the unique number in C_{n} such that x = x^{∗} mod n; here C_{n} := −\frac{n−1}{2} +\{0,…, n−1\} (resp. −\frac{n−2}{2} +\{0,…, n−1\}) is n is odd (resp. even). (The definition depends on n, but no confusion should arise since we never will consider different n at the same time. Examples for n = 30: 5^{∗} = 5, 28^{∗} = −2, 15^{∗} = −15)

Summing up we arrive at the following

Proposition 1: Let B = \binom{b_{11} b_{12}}{b_{21} b_{22}} ∈ SL(2, ZZ) and n ∈ N I be given. Then the map x ⟼ Bx mod n on ZZ_{n}^{2} maps patterns of type I to clusters if and only if the absolute values of the numbers (b_{ij})^{∗}, i, j = 1, 2, are small compared with n. In this case there are precisely |b_{22}^{∗}b_{11}^{∗} − b_{21}^{∗}b_{12}^{∗}| clusters.

Example: Let n = 28 and B = \binom{21}{11}^{5}. Modulo n this is the matrix \binom{5 27}{27 6} which we met in section 1. We have 5^{∗} = 5, 6^{∗} = 6, 27^{∗} = −1 so that |6 · 5 − (−1)(−1)| = 29 should be the number of clusters, and this is precisely what has been observed in the computer simulation.

Even more can be said. In order to describe where the clusters are located it suffices to consider vectors y_{1},…, y_{r} ∈ ZZ^{2} such that any x ∈ ZZ^{2} is equivalent mod L to some y_{ρ}; then the clusters will be close to the points By_{1},…, By_{r}. It is convenient to choose the y’s such that they are of the form (a, b) with a, b nonnegative and small compared with n. It follows that the “centers” of the clusters are just the a\binom{b_{11}}{b_{21}} + b\binom{b_{21}}{b_{22}} for these a, b. But the b_{ij}^{∗} are small in the case under consideration. And this means that the a\binom{b_{11}}{b_{21}} + b\binom{b_{21}}{b_{22}} in ZZ_{n}^{2} generate the same pattern as the a\binom{b_{11}^{∗}}{b_{21}^{∗}} + b\binom{b_{21}^{∗}}{b_{22}^{∗}} in ZZ^{2}. This explains, e.g., that in the above example (fig. 3, 4) the clusters are lined up in such a way that the respective slopes are −1/5 and −6.

With our proposition at hand we are also able to explain the observations described in section 1. Since b_{ij}^{∗} = b_{ij} mod n for every n and det B = 1 we have b_{11}^{∗}b_{22}^{∗} − b_{21}^{∗}b_{12}^{∗} = 1 mod n and hence |b_{11}^{∗}b_{22}^{∗} − b_{21}^{∗}b_{12}^{∗}|, the number of clusters, necessarily is +1 or −1 mod n.

Also, if iterations A_{n}, A_{n}^{2}, … are under consideration and B = A_{n}^{k} produces clusters for a particular k, then (a_{ij}^{k})^{∗} are small compared with n for i, j = 1, 2 ((a_{ij}^{k}) = the components of A^{k}). Suppose now that the components of A are small, as it is e.g. the case for the Anosov map. Then the (a_{ij}^{k+1})^{∗} necessarily are not much larger than the (a_{ij}^{k})^{∗} and, since det A = 1, the determinants of the ((a_{ij}^{k})^{∗})_{ij} and the ((a_{ij}^{k+1})^{∗})_{ij} coincide. This explains why in the course of the iterations of a pattern clusters usually do not occur only once between more chaotic sections and why the number of clusters at these occasions remains the same. Note, however, that the clusters associated with A^{k+1} might be more “distorted” than those for A^{k}, and after further iterations these “very distorted” clusters provide a chaotic picture.

3. Ghosts

Again we fix B ∈ SL(2, ZZ) and n ∈ N I , and as in the previous section we at first study the map induced by B in ZZ^{2}. Given any pattern P, suppose that there exist linearly independent x_{1}, x_{2} ∈ ZZ^{2} such that x_{1}, x_{2}, Bx_{1}, Bx_{2} all are small with respect of the size of P. Let L be the lattice generated by x_{1}, x_{2}. Then, for any x_{0} ∈ P, the intersection of P with x_{0} + L is some kind of coarse version of P. Under B this is mapped to a similar pattern, the distortion solely depends on how x_{1}, x_{2} transform to Bx_{1}, Bx_{2}. As in the previous sections there are | det (x_{1}, x_{2})| many sets of the form x_{0} + L, and therefore B produces precisely this number of ghosts. The step from ZZ^{2} to ZZ_{n}^{2} is as in the previous section, we only state the final result:

Proposition 2: Let B and n be as above. Then x ⟼ Bx mod n can produce ghosts if and only if there are linearly independent x_{1} = \binom{x_{11}}{x_{12}} and x_{2} = \binom{x_{21}}{x_{22}} in ZZ^{2} such that the |x_{ij}^{∗}| (i, j = 1, 2) as well as the |(b_{11}x_{i1} + b_{12}x_{i2})^{∗}|, |(b_{21}x_{i1} + b_{22}x_{i2})^{∗}| (i = 1, 2) are small compared with n. In this case the number of ghosts is |x_{11}^{∗}x_{22}^{∗} − x_{12}^{∗}x_{21}^{∗}|.

Note: One might have difficulties to regard the B(P ∩ (x_{0} + L)) as ghosts in the special case when the Bx_{1}, Bx_{2} are modulo n vectors of the form \binom{ε}{δ}, |ε|, |δ| ≤ 1; if e.g. Bx_{1}, Bx_{2} modulo n are the vectors \binom{1}{0} and \binom{0}{1}, respectively, then this corresponds to the clusters of section 2. In order not to complicate the formulation of our result we prefer to think of the clusters as a degenerate case of ghosts.

Example: Consider B = \binom{2 1}{1 1}^{12} and n = 45 as in the introduction. We have B mod 45 = \binom{10 18}{18 37}. We investigate, for a, b ∈ ZZ with |a|, |b| small, in what cases \binom{a}{b} is mapped to a vector for which the ∗–version of the components is small. One finds that the best choice is as follows: \binom{1}{2} and \binom{2}{−1} are mapped under B to itself. Therefore we choose x_{1} = \binom{1}{2}, x_{2} = \binom{2}{−1}, and it follows that there are |2 · 2 − 1(−1)| = 5 ghosts as observed.

The further discussion mainly parallels that of the case of clusters. We only summarize the results:

– The “pixels” by which the ghosts are sketched sit on (a translate of) the lattice generated by Bx_{1}, Bx_{2}; in the example they lie on lines with slope 2 and −1/2 (cf. fig. 6).

– The fact that B mod n has two fixed points with small coordinates as in the example has as a consequence that the ghosts are very similar to the original. We note that this can happen (unless B is, mod n, the identity) only if n is a composed number. For prime numbers the ghosts necessarily are a “distorted” version of the original pattern. To illustrate this, consider as a further example the 12th iterate of the Anosov map in the case n = 73; A_{73}^{12}( Cat_{73}) can be found in fig. 8. We have A^{12} mod 73 = \binom{54 13}{13 41}, and a similar calculation as before this time leads to the choice x_{1} = \binom{2}{3} and x_{2} = \binom{3}{−1} which are mapped to \binom{1}{3} and \binom{3}{−2}, respectively.

– Let B be of the form A_{n}^{k} for a matrix A with small entries like e.g. in the Anosov case and suppose that there are x_{1}, x_{2} for B as in prop. 2. Then x_{1}, x_{2} and A_{n}^{k+1} also satisfy the assumptions of prop. 2. This means that there should be the same numbers of ghosts, but those associated with A_{n}^{k+1} can be more distorted than those produced by A_{n}^{k}.

4. Lines

Let n be fixed and x ∈ ZZ_{n}^{2}, x ≠ 0. By the line generated by x be mean the subset L_{x} := {mx | m ∈ ZZ_{n}} ⊂ ZZ_{n}^{2}. The collection of all L_{x} will be denoted by L I . If n is prime, then every L_{x} will have n elements, and for simplicity we will restrict our discussion to this case

The L_{x} look quite different. Some are discrete approximations of ordinary lines in R I ^{2}, others are more or less regular patterns rather than lines. In order to quantify this behaviour we introduce the following definition: γ(L_{x}) is the norm of the smallest y which generates L_{x}, i.e. min\{\sqrt{y_{1}^{∗2} + y_{2}^{∗2}} | y = (y_{1}, y_{2}) ∈ ZZ_{n}^{2}, L_{x} = L_{y}\}. Then L_{x} looks like a line which can be used in a discrete picture, say, only if γ(L_{x}) is small.

Now let B = \binom{b_{11} b_{12}}{b_{21} b_{22}} be a matrix with b_{ij} ∈ ZZ_{n} and det B = 1. As usual B induces a linear map on ZZ_{n}^{2} and thus on L I . Further, let P ⊂ ZZ_{n}^{2} be a pattern of type II. Since P is built up from (translates of) lines L_{x} with small γ(L_{x}) the image B(P) will be a pattern of type II again only if the γ(B(L_{x})) also are small. It is thus natural to count the L_{x} ∈ L I with small γ(L_{x}) for which γ(B(L_{x})) is small, too, to measure how regular or chaotic B treats type II patterns. To make this more rigorous we define for r ≤ n, χ_{B}(r) to be the cardinality of \{L_{x} | L_{x} ∈ L I , γ(L_{x}) ≤ \sqrt{r}, γ(B(L_{x})) ≤ \sqrt{r}\}.

And now we are able to understand the phenomena in case II: Chaotic pictures B(P) correspond to the case where for B := A_{n}^{k} the function χ_{B} is slowly increasing (and even zero for small r) whereas more or less regular ones occur if χ_{B} increases faster. To illustrate this, consider the χ_{B}–functions for the patterns of fig. 7:

• n = 31, B = A_{31,8} = \binom{16 26}{26 21} : (χ_{B}(r))_{r} = (0, 0, 0, 0, 4, 4, 4, 4, 4, 8, 8, 8, 8, 8, 8, 8,…)

• n = 31, B = A_{31,10} = \binom{3 7}{7 27} : (χ_{B}(r))_{r} = (0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 2, 2, 8, 8, 8, 8,…)

5. Measures of chaotic behaviour for a map on ZZ_{n}^{2}

In view of the discussion of the previous sections the following problems arise:

1. Let n ∈ N I and a matrix B = \binom{b_{11} b_{12}}{b_{21} b_{22}} with b_{ij} ∈ ZZ_{n} and det B = 1 be given. What properties of the b_{ij} are responsible for a “chaotic” behaviour of the mapping induced by B on ZZ_{n}^{2}, i.e. under what circumstances are the B(P) “chaotic” for “regular” pictures P ⊂ ZZ_{n}^{2}?

2. If n ∈ N I and A ∈ SL(2, ZZ) are given, how can one deduce from the entries of A whether in the sequence A_{n}, A_{n}^{2}, A_{n}^{3},… there will be “chaotic” matrices (where “chaotic” is measured with respect to a suitable definition according to “1.”)?

We have no idea how to treat “2.”, here we will propose only some definitions concerning “1.”. One possibility has been mentioned already in section 4: the function χ_{B}. Whereas it describes the observations properly the calculation of its values is rather cumbersome and an explicit description in terms of the b_{ij} would be useful.

Our second definition has patterns of type I as a starting point. We can regard B as more or less “chaotic” if for such patterns P the image B(P) fails to have or has little recognizable structure. Since the only observed “structures” are the ghosts (and, in the degenerate case, the clusters) we can quantify the chaotic behaviour of B by calculating to what extent the assumptions of proposition 2 in section 3 are satisfied. To this end we first introduce the ∗–norm ∥x_{0}∥_{∗} of a vector x_{0} ∈ ZZ_{n}^{2}. This number is defined as ∥(x, y)∥_{∗} := \sqrt{|x^{∗}|^{2} + |y^{∗}|^{2}}, i.e. it is the ℓ^{2}–Norm of the smallest vector y_{0} in ZZ^{2} such that x_{0} = y_{0} mod n. In order to observe ghosts one should find linearly independent x_{1}, x_{2} with small ∥x_{1}∥_{∗}, ∥x_{2}∥_{∗}, ∥Bx_{1}∥_{∗}, ∥Bx_{2}∥_{∗}. This will not happen, if for all x_{0} such that ∥x_{0}∥_{∗} ≤ r (r ∈ N I , r small compared with n) the vector Bx_{0} has a large ∗–norm. This motivates the following definition: For r ∈ N I , let φ_{B}(r) := min{∥B(x_{0})∥_{∗} | 0 < ∥x_{0}∥_{∗} ≤ r}. Clearly φ_{B} is a decreasing function, and the chaotic behaviour of B can be seen from φ_{B} as follows: B will be chaotic iff φ_{B} attains small values only for fairly large values of r. As an example, consider the 6th, 8th and 12th iteration of the cat in the case n = 35 in fig. 9 which show a chaotic behaviour, ghosts and clusters respectively.

The corresponding φ_{B}–functions are as follows:

B = \binom{1 2}{1 1}^{6}, n = 35; (φ_{B}(r)) = = (15.03, 5.39, 5.39, 5.39, 5.39, 2.00, 2.00, 2.00, 2.00, 2.00, 2.00, 2.00, …)

B = \binom{1 2}{1 1}^{8}, n = 35; (φ_{B}(r)) = (14.76, 14.32, 2.24, 2.24, 2.24, 2.24, 2.24, 2.24, 2.24, 2.24, 2.24, 2.24, …)

B = \binom{1 2}{1 1}^{11}, n = 35; φ_{B}(r) = (8.06, 8.06, 8.06, 4.12, 4.00, 4.00, 4.00, 4.00, 1.00, 1.00, 1.00, 6.00, …).

As one would expect, in the case of ghosts (resp. clusters) φ_{B}(r) attains small values (resp. even the value one) for small r.

In contrast to χ_{B} the function φ_{B} is easy to calculate. The x_{0} with 0 ≤ ∥x_{0}∥_{∗} ≤ r can be represented as the x_{0} = (a, b) with a, b ∈ ZZ, 0 < \sqrt{|a|^{2} + |b|^{2}} ≤ r. Thus φ_{B}(r) = min\{\sqrt{|(ab_{11} + bb_{12})^{∗}|^{2} + |(ab_{21} + bb_{22})^{∗}|^{2}} | 0 < \sqrt{|a|^{2} + |b|^{2}} < r\}.

It should be stressed that these definitions are only the very first steps towards an understanding of the chaotic behaviour of matrices B ∈ SL(2, ZZ) mod n (or, more generally, B ∈ SL(m, ZZ) mod n). Quantifications should be functions as in our examples or – even better – numbers which describe what is seen when treating concrete patterns P. And then it would be very interesting to derive techniques to find – given n – matrices B in SL(2, ZZ) such that B behaves “as chaotic as possible” on ZZ_{n}^{2}. Applications could be e.g. the cryptography of discrete pictures or the simple generation of uniformly distributed pseudorandom numbers in the unit square, i.e. sequences with a small discrepancy (in the sense of [5]) which are important for fast numerical integration.

References

[1] E. Behrends, B. Fiedler: Periods of the discretized linear Anosov maps. Preprint 1995.

[2] J.W. Cassels: An introduction to the geometry of numbers. Springer Verlag, 1971.

[3] F.J. Dyson, H. Talk: Period of a discrete cat mapping. Am. Math. Monthly 99, 603–614, 1992.

[4] T.Y. Kong, R. Kopperman, P.R. Meyer: A topological approach to digital topology. Am. Math. Monthly 98, 1991 , 901–917.

[5] L. Kuipers, H. Niederreiter: Uniform distribution of sequences. John Wiley & Sons, 1974.

[6] A. Rosenfeld, R.A. Melter: Digital Geometry. The Math. Intelligencer 11 (3), 1989, 69–72.

[7] K.L. Siegel: Lectures on the geometry of numbers. Springer Verlag, 1989.

Ehrhard Behrends

I. Mathematisches Institut Arnimallee 2 – 6 D – 14195 Berlin