Binomial Complexity of Multidimensional Arrays

Source abstract

Binomial coefficients for multidimensional arrays count occurrences of particular configurations. For the sake of presentation, the emphasis is put on column-binomial coefficients for two-dimensional finite arrays. In this article, we first show that these coefficients can be computed through some Magnus transform. To get structural and combinatorial information on arrays, we then define $(k,\ell)$-binomial equivalence for finite arrays and, from it, the $(k,\ell)$-binomial complexity function of an infinite array. Roughly, two finite arrays are $(k,\ell)$-binomially equivalent when they share the same number of subarrays of size at most $k\times \ell$. We obtain general results on the $(k,\ell)$-binomial complexity of infinite arrays coding direct products of infinite words. Our main theorem gives an exact formula for the $(k,\ell)$-binomial complexity of the two-dimensional Thue--Morse array. To that end, we closely examine the action of the bit-wise complement on the $k$-binomial equivalence classes of the factors of the Thue--Morse word.