Pascal's triangle, complexity and automata (Q1280222)

The aim of this paper is to study the double sequence \( s_{n,m}= \binom {n}{m} \) mod \( d\). Actually it is mainly concerned with the number \( P_{d}(u,v) \) of distinct \( u\times v \) sized rectangular blocks contained in the infinite matrix \( (s_{n,m})\). Firstly \( P_{d}(u,v) \) is proved to be multiplicative : namely, for relatively prime integers \( d_{1} \) and \( d_{2} \) one has \( P_{d_{1}d_{2}}(u,v) =P_{d_{1}}(u,v) P_{d_{2}}(u,v)\). Then, for any prime number \( d\), rather explicit formulas are given for \( P_{d}(1,v) \) hence for \( P_{d}(u,v)\). For \( d=2 \) the result is particularly explicit and simple. In the general case, let \(\omega\) denote the number of distinct prime factors of \( d\), the main result of the paper is the existence of constants \( 0<A<B \) such that \( A \sup(u,v)^{2\omega}\leq P_{d}(u,v)\leq B \sup(u,v)^{2\omega}\). In particular one recovers that the sequence \( s_{n,m} \) is automatic if and only if \( \omega=1 \) (i.e. if \( d \) is a power of a prime number). Reading this article is pleasant : proofs are explicitly written and main results come with comments on connected topics.