×

Random matrix products and applications to cellular automata. (English) Zbl 1154.37020

The paper under review deals with Lyapunov exponents of products of i.i.d. random matrices which take their values in a finite set of \(m\times m\) matrices with complex coefficients, generating a monoid that contains a matrix of rank 1. It provides an explicit formula for the top exponent in terms of a convergent series. A generalization is considered in which the i.i.d. sequence is replaced by a Markov chain. The result on the Lyapunov exponent allows an asymptotic rate estimate for the nonzero coefficients of \(n\)th powers of polynomials with integer coefficients as \(n\to\infty.\)

MSC:

37H15 Random dynamical systems aspects of multiplicative ergodic theory, Lyapunov exponents
37B15 Dynamical aspects of cellular automata
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
82C20 Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J.-P. Allouche and V. Berthé,Triangle de Pascal, complexité et automates, Bull. Belg. Math. Soc.4 (1997), 1–23.
[2] J.-P. Allouche, M. Courbage and G. Skordev,Notes on cellular automata, Cubo Mat. Educ.3 (2001), 213–244. · Zbl 1103.68648
[3] J.-P. Allouche, F. von Haeseler, H.-O. Peitgen, A. Petersen and G. Skordev,Automaticity of double sequences generated by one-dimensional linear cellular automata, Theoret. Comput. Sci.188 (1997), 195–209. · Zbl 0943.11020 · doi:10.1016/S0304-3975(96)00298-8
[4] G. Benettin,Power-law behavior of Lyapunov exponents in some conservative dynamical systems, Phys. D13 (1984), 211–220. · Zbl 0578.70024 · doi:10.1016/0167-2789(84)90278-1
[5] D. Berend and N. Kriger,On some questions of Razpet regarding binomial coefficients, Discrete Math.260 (2003), 177–182. · Zbl 1015.05003 · doi:10.1016/S0012-365X(02)00760-4
[6] V. Berthé,Complexité et automates cellulaires linéaires, Theor. Inform. Appl.34 (2000), 403–423. · Zbl 0988.68116 · doi:10.1051/ita:2000124
[7] V. D. Blondel and J.N. Tsitsiklis,The Lyapunov exponent and joint spectral radius of pairs of matrices are hard–when not impossible–to compute and to approximate, Math. Control Signals Systems10 (1997), 31–40. · Zbl 0888.65044 · doi:10.1007/BF01219774
[8] J. Cohen and C. Newman,The stability of large random matrices and their products, Ann. Probab.12 (1984), 283–310. · Zbl 0543.60098 · doi:10.1214/aop/1176993291
[9] B. Derrida and E. Gardner,Lyapounov exponent of the one-dimensional Anderson model: weak disorder expansions, J. Physique45 (1984), 1283–1295. · doi:10.1051/jphys:019840045080128300
[10] N. J. Fine,Binomial coefficients modulo a prime, Amer. Math. Monthly54 (1947), 589–592. · Zbl 0030.11102 · doi:10.2307/2304500
[11] H. Furstenberg,Recurrence in Ergodic Theory and Combinatorial Number Theory, Princeton University Press, Princeton, N.J. 1981. · Zbl 0459.28023
[12] H. Furstenberg and H. Kesten,Products of random matrices, Ann. Math. Statist.31 (1960), 457–469. · Zbl 0137.35501 · doi:10.1214/aoms/1177705909
[13] M. Goldstein and W. Schlag,Hölder continuity of the integrated density of states for quasi-periodic Schrödinger equations and averages of shifts of subharmonic functions, Ann. of Math. (2)154 (2001), 155–203. · Zbl 0990.39014 · doi:10.2307/3062114
[14] A. Granville,Arithmetic properties of binomial coefficients. I. Binomial coefficients modulo prime powers, Organic mathematics, (Burnaby, BC, 1995), Amer. Math. Soc., Providence, RI, 1997, pp. 253–276. · Zbl 0903.11005
[15] F. Haeseler, H.-O. Peitgen and G. Skordev,Self-similar structure of rescaled evolution sets of cellular automata, Internat. J. Bifur. Chaos Appl. Sci. Engrg.11 (2001), 927–941. · Zbl 1090.37505 · doi:10.1142/S0218127401002511
[16] J. G. Huard, B. K. Spearman and K. S. Williams,Pascal’s triangle (mod 9), European J. Combin.19 (1998), 45–62. · Zbl 0889.11007 · doi:10.1006/eujc.1997.0146
[17] J. G. Huard, B. K. Spearman and K. S. Williams,Pascal’s triangle (mod 9), Acta Arith.78 (1997), 331–349. · Zbl 0874.11024
[18] J. Kari,Linear cellular automata with multiple state variables, Lecture Notes in Comput. Sci.1770 (2000), 110–121. · Zbl 0959.68085 · doi:10.1007/3-540-46541-3_9
[19] R. Kenyon and Y. Peres,Intersecting random translates of invariant Cantor sets, Invent. Math.104 (1991), 601–629. · Zbl 0745.28012 · doi:10.1007/BF01245092
[20] E. Kummer,Über die Ergänzungssätze zu den allgemainen Reciprocitätsgesetzen, J. Reine Angew. Math.44 (1852), 93–146. · ERAM 044.1198cj · doi:10.1515/crll.1852.44.93
[21] F. Ledrappier,Examples of applications of Oseledec’s theorem, Contemp. Math.50, Amer. Math. Soc., Providence, RI, 1986, pp. 55–64. · Zbl 0588.60023
[22] R. Lima and M. Rahibe,Exact Lyapunov exponent for infinite products of random matrices, J. Phys. A27 (1994), 3427–3437. · Zbl 0830.15018 · doi:10.1088/0305-4470/27/10/019
[23] Y. Moshe,The density of 0’s in recurrence double sequences, J. Number Theory103 (2003), 109–121. · Zbl 1057.11008 · doi:10.1016/S0022-314X(03)00103-3
[24] Y. Moshe,The distribution of elements in automatic double sequences, Discrete Math.297 (2005), 91–103. · Zbl 1119.11021 · doi:10.1016/j.disc.2005.03.022
[25] V. I. Oseledec,A multiplicative ergodic theorem, Trans. Moscow Math. Soc.19 (1968), 179–231.
[26] Y. Peres,Domains of analytic continuation for the top Lyapunov exponent, Ann. Inst. H. Poincaré Probab. Statist.28 (1992), 131–148. · Zbl 0794.58023
[27] S. Pincus,Strong laws of large numbers for products of random matrices, Trans. Amer. Math. Soc.287 (1985), 65–89. · Zbl 0558.60028 · doi:10.1090/S0002-9947-1985-0766207-5
[28] A. Robison,Fast computation of additive cellular automata, Complex Systems1 (1987), 211–216. · Zbl 0655.68064
[29] D. Singmaster,Notes on binomial coefficients. III. Any integer divides almost all binomial coefficients, J. London Math. Soc. (2)8 (1974), 555–560. · Zbl 0293.05007 · doi:10.1112/jlms/s2-8.3.555
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.