Growth-complexity spectrum of some discrete dynamical systems

We first study the iteration of birational mappings generated by the composition of the matrix inversion and of a permutation of the entries of 3 x 3 matrices, and consider the degree d(n) of the numerators (or denominators) of the corresponding successive rational expressions for the nth iterate. The growth of this degree is (generically) exponential with n: d(n) similar or equal to lambda(n).lambda is called the growth complexity. We introduce a semi-numerical analysis which enables to compute these growth complexities lambda for all the 9! possible birational transformations. These growth complexities correspond to a spectrum of eighteen algebraic values. We then drastically generalize these results, replacing permutations of the entries by homogeneous polynomial transformations of the entries possibly depending on many parameters. Again it is shown that the associated birational, or even rational, transformations yield algebraic values for their growth complexities. (C) 1999 Elsevier Science B.V. All rights reserved.