The density of 0's in recurrence double sequences. (Q1415370)

This paper studies the density of \(0\)'s in double linear recurrence sequences \(A=(A(i,j))_{i\geq 0, j \in {\mathbb Z}}\) over a finite field GF\((q)\) generated by a linear recurrence with constant coefficients with a finite initial condition: more precisely, if \(P_i(X)=\sum_{j =-\infty} ^{\infty} A(i,j) X ^j\) for \(i\geq 0\), then \(P_i=\sum _{k=1} ^d c_k (X) P_{i-k} (X)\) for \(i \geq d\). When \(d=1\) (the double recurrence is then said to be of first order), these double sequences are generated by linear cellular automata with finite initial condition; hence this class of double sequences includes Pascal's triangle reduced modulo a prime, and more generally Pascal's rhombus [\textit{W. F. Klostermeyer, M. E. Mays, L. Soltes} and \textit{G. Trapp}, Fibonacci Q. 35, 318--328 (1997; Zbl 0908.11005)]. The paper under review is mainly devoted to the following question: is the density of \(0\)'s in such a double linear recurrence equal to \(1\)? Observe that the double sequence \(A=(A(i,j))_{i\geq 0, j \in {\mathbb Z}}\) has at most finitely many nonzero elements in each row; hence the density of a letter is defined as the density in the triangle which corresponds to the nonzero terms, that is, to the limit of the frequency of occurrences in the first rows of the triangle as the number of rows increases. The paper under review shows that the density of \(0\)'s is equal to \(1\) when \(A\) is generated by a nontrivial first-order double linear recurrence. The results are based on an explicit formula for the number of entries in the first \(q^n\) rows. It is then possibe to decide algorithmically whether the density of any element is equal to \(0\) or not.