The distribution of elements in automatic double sequences. (English) Zbl 1119.11021
This paper deals with double sequences \(A=(A(i,j))\), \(i,j\in\mathbb Z\) over \(\mathbb F_q\) satisfying a linear recurrence relation with at most finitely many nonzero entries on each row. Natural examples include Pascal’s triangle and rhombus modulo a prime. In earlier work [J. Number Theory 103, No. 1, 109–121 (2003; Zbl 1057.11008)] the author found a formula for the number of occurrences of a digit in the first \(q^k\) rows of the sequence. Here the result is generalized to \(q\)-automatic double sequences over a finite alphabet, and an explicit formula for the occurrence of specific digits in each row of \(A\) is found. For the \(n\)th row, this involves a product of matrices related to the digits of the \(q\)-ary expansion of \(n\). Asymptotic typical behaviour is thence related to the upper Lyapunov exponent of these square matrices. Examples are given where this may be computed explicitly, giving new proofs of several known results on Pascal’s triangle modulo a prime as special case, in particular a new and different proof of the result of R. Garfield and H. S. Wilf [J. Number Theory 41, No. 1, 1–5 (1992; Zbl 0765.11008)] is found.
Reviewer: Thomas Ward (Norwich)
Online Encyclopedia of Integer Sequences:
Sierpiński’s [Sierpinski’s] triangle (or gasket): triangle, read by rows, formed by reading Pascal’s triangle (A007318) mod 2.Triangle, read by rows, formed by reading Pascal’s triangle (A007318) mod 3.
Triangle read by rows: T(n,k) = A083093 with 1’s and 2’s interchanged.
References:
| [1] | Allouche, J.-P.; Berthé, V., Triangle de Pascal, complexité et automates, Bull. Belg. Math. Soc., 4, 1-23 (1997) · Zbl 0922.11012 |
| [2] | Allouche, J.-P.; Haeseler, F.v.; Peitgen, H.-O.; Petersen, A.; Skordev, G., Automaticity of double sequences generated by one-dimensional linear cellular automata, Theoret. Comput. Sci., 188, 195-209 (1997) · Zbl 0943.11020 |
| [3] | Allouche, J.-P.; Shallit, J., Automatic Sequences: Theory, Applications, Generalizations (2003), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1086.11015 |
| [4] | L. Arnold, V. Wihstutz, Lyapunov exponents: a survey, Lyapunov exponents (Bremen, 1984), pp. 1-26, Lecture Notes in Mathematics, vol. 1186, Springer, Berlin, 1986.; L. Arnold, V. Wihstutz, Lyapunov exponents: a survey, Lyapunov exponents (Bremen, 1984), pp. 1-26, Lecture Notes in Mathematics, vol. 1186, Springer, Berlin, 1986. · Zbl 0599.60061 |
| [5] | Barbolosi, D.; Grabner, P. J., Distribution des coefficients multinomiaux et \(q\)-binomiaux modulo \(p\), Indag. Math. (N.S.), 7, 129-135 (1996) · Zbl 0863.11009 |
| [6] | Berend, D.; Harmse, J. E., On some arithmetical properties of middle binomial coefficients, Acta Arith., 84, 31-41 (1998) · Zbl 0903.11004 |
| [7] | Bougerol, P.; Lacroix, J., Products of Random Matrices with Applications to Schrödinger Operators (1985), Birkhäuser: Birkhäuser Boston · Zbl 0572.60001 |
| [8] | Davis, K. S.; Webb, W. A., Pascal’s triangle modulo 4, Fibonacci Quart., 29, 79-83 (1991) · Zbl 0732.11009 |
| [9] | Fine, N. J., Binomial coefficients modulo a prime, Amer. Math. Monthly, 54, 589-592 (1947) · Zbl 0030.11102 |
| [10] | Furstenberg, H.; Kesten, H., Products of random matrices, Ann. Math. Statist., 31, 457-469 (1960) · Zbl 0137.35501 |
| [11] | Garfield, R.; Wilf, H. S., The distribution of the binomial coefficients modulo \(p\), J. Number Theory, 41, 1-5 (1992) · Zbl 0765.11008 |
| [12] | Glaisher, J. W.L., On the residue of a binomial-theorem coefficient with respect to a prime modulus, Quart. J. Math., 30, 150-156 (1899) · JFM 29.0152.03 |
| [13] | Goldwasser, J.; Klostermeyer, W.; Mays, M.; Trapp, G., The density of ones in Pascal’s rhombus, Discrete Math., 204, 231-236 (1999) · Zbl 0935.11009 |
| [14] | A. Granville, Arithmetic properties of binomial coefficients. I. Binomial coefficients modulo prime powers. Organic mathematics (Burnaby, BC, 1995) pp. 253-276, CMS Conference Proceedings, 20, American Mathematical Society, Providence, RI, 1997.; A. Granville, Arithmetic properties of binomial coefficients. I. Binomial coefficients modulo prime powers. Organic mathematics (Burnaby, BC, 1995) pp. 253-276, CMS Conference Proceedings, 20, American Mathematical Society, Providence, RI, 1997. · Zbl 0903.11005 |
| [15] | Hexel, E.; Sachs, H., Counting residues modulo a prime in Pascal’s triangle, Indian J. Math., 20, 91-105 (1978) · Zbl 0499.10005 |
| [16] | Huard, J. G.; Spearman, B. K.; Williams, K. S., Pascal’s triangle \((\operatorname{mod} 9)\), Acta Arith., 78, 331-349 (1997) · Zbl 0874.11024 |
| [17] | Huard, J. G.; Spearman, B. K.; Williams, K. S., Pascal’s triangle (mod 8), European J. Combin., 19, 45-62 (1998) · Zbl 0889.11007 |
| [18] | Kenyon, R.; Peres, Y., Intersecting random translates of invariant Cantor sets, Invent. Math., 104, 601-629 (1991) · Zbl 0745.28012 |
| [19] | N. Kriger, Arithmetical properties of some sequences of binomial coefficients, M. Sc. Thesis, Ben-Gurion University, 2001.; N. Kriger, Arithmetical properties of some sequences of binomial coefficients, M. Sc. Thesis, Ben-Gurion University, 2001. |
| [20] | Lima, R.; Rahibe, M., Exact Lyapunov exponent for infinite products of random matrices, J. Phys. A: Math. Gen., 27, 3427-3437 (1994) · Zbl 0830.15018 |
| [21] | Moshe, Y., The density of 0’s in recurrence double sequences, J. Number Theory, 103, 109-121 (2003) · Zbl 1057.11008 |
| [22] | A.H. Stein, Binomial coefficients not divisible by a prime, Number Theory (New York, 1985/1988), pp. 170-177, Lecture Notes in Mathematics, vol. 1383, Springer, Berlin, 1989.; A.H. Stein, Binomial coefficients not divisible by a prime, Number Theory (New York, 1985/1988), pp. 170-177, Lecture Notes in Mathematics, vol. 1383, Springer, Berlin, 1989. · Zbl 0692.10014 |
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.
