Let A be a finite alphabet, and letS be a set of of 2-dimensional bounded prohibited patterns over A . We consider the set MA ,S of matrices over A that avoid the patterns from S , and attempt to derive (closed or linear recurrence) formulas for the numbers of m × n matrices in MA ,S . We argue that different sets of prohibited patterns require different types of formulas, with some formulas recurrent in just one of the parameters m, n, some satisfying a two-dimensional linear recurrence relation (depending of both m and n), and some satisfying neither of the two types. We consider characterization of classes that admit a twodimensional linear recurrence relation, as well as classes that do not allow for such relation. In addition, given A and S , we address the question of the existence of a constant a such that the number toof |mA×|anmmn.atrices in MA ,S is asymptotically equal We report on preliminary results for a specific class of boolean matrices with the prohibited set consisting of thirty-two 3 × 3 matrices for which computational results suggest the non-existence of a twodimensional linear recurrence relation.
1 Introduction and preliminaries Many classes of objects are defined via prohibiting specified sub-objects. In our paper, we deal with classes of matrices over finite alphabets that do not contain patterns from a finite set of local prohibited patterns. Such matrices can be viewed as matrices recognizable via a bounded window automaton with a finite memory that can only view a bounded area of the matrix at a time and cannot see (or remember) the matrix in its entirety (while it is allowed to slide through the entire matrix window by window, verifying each window separately). The motivation behind considering these classes of matrices lies in extending the theory of ‘one-dimensional’ languages of strings avoiding specified substrings to two dimensional arrays. One-dimensional languages that avoid (connected) substrings from a finite set of prohibited substrings have been studied for several decades and their enumeration is well-known to lead to homogeneous linear recurrence relations (see. e.g., [3, 4]), We show that a similar, although more complicated, situation holds in the case of twodimensional arrays. We stress that when talking of submatrices, we mean connected blocks.
Let A be a finite alphabet, and let S be a set of k × ` matrices over A , k, ` ≥ 1. Let MA ,S denote the set matrices over A that do not contain (avoid) sub-matrices from S , i.e., the set of matrices A =k ai, j km.n, ai, j ∈ A , for 1 ≤ i ≤ m, 1 ≤ j ≤ m, having the property that none of the k × ` submatrices of A belong to S (thus, k and ` are the dimensions of the viewing window of the automaton recognizing A; it accepts A if and only if it never finds a matrix fromS in its viewing window).
We illustrate this concept with a specific class of matrices with prohibited patterns that will be used throughout our paper.
Example 1. Let A = {0, 1}, and consider the set of boolean matrices over A not admitting 3 × 3 crosses of zeroes or ones, i.e., not admitting submatrices of the form ∗ 0 ∗ where the stars stand for arbitrary elements from A (to avoid using stars, one could think of the set of the 32 prohibited matrices obtained by making all the possible choices). We will call the matrices from this class noise matrices, and note that they are often considered to be examples of chaotic, structure-less matrices.
Given an alphabet A and a set S of prohibited k × ` submatrices over A , let NA ,S (m, n) denote the number of m × n matrices in MA ,S . Then clearly NA ,S (m, n) = |A |mn, for all 1 ≤ m ≤ k and 1 ≤ n ≤ `, with at least one parameter smaller than the upper bound, while 0 ≤ NA ,S (m, n) ≤ |A |mn in general.
In what follows, we are interested in deriving formulas for NA ,S (m, n) for various alphabets A and sets of prohibited sub-matrices S .
Example 2. Considering A = {0, 1} again, taking empty S1 yields MA ,S1 consisting of all boolean matrices and NA ,S1 (m, n) = 2mn, for all m and n. Taking S2 to consist of the single 1 × 1 matrix with a1,1 = 1 implies that MA ,S2 consists of just the m × n zero-matrices and NA ,S2 (m, n) = 1, for all m and n.
Finally, taking S3 to consist of the 2 × 2 all-ones matrix ai, j = 1, for 1 ≤ i, j ≤ 2, yields MA ,S3 consisting of all 1 × 1, 1 × 2, 2 × 1 matrices, and m × n matrices that do not contain a 2 × 2 sub-matrix of all ones, for m, n ≥ 2. Thus,
NA ,S3 (
NA ,S3 (
One of the main conjectures concerning the asymptotic behavior of the numbers NA ,S (m, n) states the following: Conjecture 1. Let A be a finite alphabet, and let S be a set of prohibited k × ` submatrices over A . Then there exists a constant 0 ≤ a ≤ 1 such that
lim m→∞,n→∞
NA ,S (m, n) |A |amn = 1.
If the a from the above conjecture exists for a specific pairA and S , we say that a is the critical exponent for the pair. The sets S1 and S2 defined in Example 2 constitute extremal cases with the critical exponents a1 = 1 and a2 = 0, respectively.
The paper [1] contains the following information about the asymptotic behavior of the enumeration function of the noise matrices.
Theorem 1 ([1]). Let A and S be those defined in Example 1. For every m ≥ 3, there exists a constant 0 ≤ am ≤ 1 such that lim n→∞ |A |ammn
While computer experimentation appears to support Conjecture 1, in principle, it cannot be used to prove the claim for any specific pairA and S . However, it usually fairly quickly provides for estimates for the value of a. In particular, finding the numbers NA ,S (m, n) for a large range of pairs m, n allows one to calculate log|A |(NmAn,S (m,n)) for each such pair. The actual values for large pairs often match for a considerable number of decimal places. For example, calculations concerning the enumeration of noise matrices reported in [6] yield that the corresponding a (if it exists!) lies in the range: Let A and S be a finite alphabet and a set ofk × ` prohibited matrices over A . In this section, we prove that for any given m ≥ k there exists a linear recurrence formula tying together the numbers NA ,S (m, n), n ≥ 1. We use a generalization of a technique used in [1] for noise matrices.
Example 3. To illustrate the basic idea of this approach, suppose we extend a 3 × n matrix ending in a specific triple of columns by adding a specific new column which results in a 3 × (n + 1) matrix ending in a new triple of columns (but sharing two columns with the original triple). We may encounter two different situations: When considering the noise matrices defined in Example 1, these two situations differ as follows. Any noise matrix ending in the first triple remains a noise matrix after adding the specified column, while the matrix formed from a noise matrix by adding the second specified column ceases being a noise matrix.
With regard to the above example, it is important to point out that the entire situation only depends of the last three columns, and the actual number of columns of the matrices is irrelevant with regard to the above claims.
In view of these observations, let A be a finite alphabet and S be a set of k × ` prohibited matrices over A , and let us fix the number m ≥ k of rows. Let {M1, M2, . . . , M|A |m` } be the set of all m × ` matrices over A (listed in an arbitrary but fixed order). For each n ≥ `, divide the m × n matrices in MA ,S with regard to their last ` columns, and let αin denote the number of m × n matrices in MA ,S ending in the matrix Mi, 1 ≤ i ≤ |A |m`. Denote α(n) = (α1n, α2n, . . . , αn
|A |m` ), and note that
α(n) · 1T =
|A |m`
∑ αin = NA ,S (m, n),
i=1
(
As observed above, if we expand an m × n matrix
ending in Mi by adding a column, we obtain an
m × (n + 1) matrix ending in M j having the
property that the first ` − 1 columns of M j match the
last ` − 1 columns of Mi. If this is the case, we
will say that M j is a successor of Mi. Moreover,
if n ≥ `, the question whether an m × n matrix in
MA ,S ending in Mi remains in MA ,S after a
column is added to it so that it ends in M j depends of
Mi and M j only and it is independent of the
number of columns n. Therefore, for 1 ≤ i, j ≤ |A |m`,
let ai, j = 1 if M j is a successor of Mi having the
property that if an m × n matrix ending in Mi
belongs to MA ,S then so does the m × (n + 1) matrix
ending in M j (constructed from the smaller matrix
by adding a column). Let ai, j = 0 otherwise, and
denote A =k ai, j k. Since every m × (n + 1) matrix
in MA ,S is obtained from a specificm × n matrix
in MA ,S , it follows that
α(n + 1) = α(n)A,
(
Suppose now that the square matrix A is a root of a monic polynomial p(x) = a0 + a1x + a2x2 + . . . + as−1xs−1 + xs in Z[x], i.e., a0I + a1A + a2A2 + . . . + as−1As−1 + As = O, where I stands for the identity matrix and O for the all-zeroes matrix. Thus,
As = −a0I − a1A − a2A2 − . . . − as−1As−1, (
. . . − as−1α(n)As−11T .
Applying equations (
NA ,S (m, n + s) =
−a0NA ,S (m, n) − . . . − as−1NA ,S (m, n + s − 1),
(
The above arguments allow us to prove the following generalization of Theorem 2 to all sets of matrices over finite alphabets with prohibited bounded patterns.
Theorem 2 ([1]). Let A be a finite alphabet and S be a set of k × ` prohibited matrices over A . For every m ≥ k, there exists a linear recurrence relation such that
NA ,S (m, n + s) = −a0NA ,S (m, n) − . . . − as−1NA ,S (m, n + s − 1), as well as a constant 0 ≤ cm ≤ 1 such that lim n→∞
NA ,S (m, n) |A |cmmn = 1.
Proof. Let A and S be as stated, and suppose that m ≥ k. The matrix A defined in the discussion preceding the statement of our theorem is an |A |m` × |A |m` boolean matrix which (by the Cayley-Hamilton theorem) is the root of its characteristic polynomial charA(x), which belongs to Z[x], and is either monic when |A |m` is even or can be made monic by multiplying by −1 when |A |m` is odd. This yields a linear recurrence relation of order |A |m` for the numbers NA ,S (m, n), n ≥ `. Since A is a boolean (i.e., non-negative) matrix, using the Perron-Frobenius theorem yields that its spectral radius ρ(A) is its eigenvalue of the largest modulus. Consequently, ρ(A) determines the magnitude of any sequence satisfying the recurrence relation determined by charA(x) [2, 5], therefore NA ,S (m, n) = θ (ρ(A)n), and the second claim of our theorem follows.
One-dimensional linear recurrence relations of smallest order Even though we have proved the existence of an one-dimensional linear recurrence relation for each A , S , and m ≥ k, the orders |A |m` of these relations are rather large. The key problem when using such relations lies in the need to find the first|A |m` elements of the corresponding sequence by brute force. Thus, in order to start using the above described recurrence relation for the numbers NA ,S (3, n) in the case of noise matrices (for which the prohibited matrices are of dimension 3 × 3), one first needs to find the numbers
NA ,S (
Similarly, calculating the numbers NA ,S (4, n) for 1 ≤ n ≤ 35000 determined the critical exponent for m = 4 equal to 0.959452; the numbers NA ,S (5, n) for 1 ≤ n ≤ 50000 determined the critical exponent for m = 5 equal to 0.952307; and finally calculating the numbers NA ,S (6, n) for 1 ≤ n ≤ 25000 determined the critical exponent for m = 6 equal to 0.9475645.
As for the recurrence relation of minimal degree, having the actual values of the corresponding sequence allows one to find the minimal degree experimentally. Specifically, let k ≥ 2, and suppose an equivalence relation of degree k exists. If that were the case, the solution a0, a1, a2, . . . , ak−1 of the k × k system of linear equations a0NA ,S (m, `) + . . . + ak−1NA ,S (m, ` + k − 1) a0NA ,S (m, ` + 1) + . . . + ak−1NA ,S (m, ` + k) = NA ,S (m, ` + k) a0NA ,S (m, ` + k − 1) + . . . + ak−1NA ,S (m, ` + 2k − 2) = NA ,S (m, ` + k + 1)
. . . = NA ,S (m, ` + 2k − 1) would have to satisfy all the ‘latter’ systems, i ≥ 1, a0NA ,S (m, ` + i) + . . . + ak−1NA ,S (m, ` + k − 1 + i) a0NA ,S (m, ` + 1 + i) + . . . + ak−1NA ,S (m, ` + k + i) = NA ,S (m, ` + k + i) = NA ,S (m, ` + k + 1 + i) . . . a0NA ,S (m, ` + k − 1 + i) + . . . + ak−1NA ,S (m, ` + 2k − 2 + i) = NA ,S (m, ` + 2k − 1 + i).
This can be experimentally tested starting from k = 2, and looking for the firstk that satisfies these requirements (which will necessary be the smallest degree of a linear recurrence relation for the considered sequence).
Relying on [6] again reveals the following. The minimal degree of a linear recurrence relation for NA ,S (3, n) is 2, the minimal degree of a linear recurrence relation for NA ,S (4, n) is 4, the minimal degree of a linear recurrence relation for NA ,S (5, n) is 8, and the minimal degree of a linear recurrence relation for NA ,S (6, n) is 20.
for all n ≥ 3.
NA ,S (3, n + 2) = 4NA ,S (3, n) + 7NA ,S (3, n + 1), 4
Two-dimensional linear recurrence relations The results obtained for the noise matrices mentioned in the previous section suggest that the degree of the minimal linear recurrence relation increases with increasing number of rows. This is, however, not a universal fact concerning all matrices with prohibited bounded patterns. For example, all the numbers NA ,S2 (m, n) for the matrices from Example 2 are equal to 1, and hence satisfy the recurrence relation NA ,S2 (m, n + 1) = NA ,S2 (m, n). Nevertheless, we feel that the following conjecture might turn out to be true. Conjecture 2. Let A be a finite alphabet and S be a set of k × ` prohibited matrices over A with k, ` ≥ 2. Then the minimal degree of a linear recurrence relation for the sequence NA ,S (m, n), NA ,S (m, n + 1), NA ,S (m, n + 2), . . . m ≥ k, increases with increasing m.
In view of Conjecture 2, instead of looking for onedimensional linear recurrence relations, we propose to search for two-dimensional recurrence relations.
Specifically, letrm,n be a two dimensional sequence of reals (i.e., a function from N × N to R). We say that a two-dimensional sequence rm,n satisfies a two-dimensional linear recurrence relation provided there exist coefficients ai, j, 0 ≤ i ≤ t, 0 ≤ j ≤ s, with at,s = 0, such that
Our preliminary results suggest the following two conjectures. . . . +
Conjecture 3. Let A be a finite alphabet and S be a set of k × ` prohibited matrices over A with at least one of the numbers k, ` equal to 1. Then the two-dimensional sequence NA ,S (m, n), m, n ≥ 1, satisfies a two-dimensional recurrence relation. Conjecture 4. Let A be a finite alphabet and S be a set of k × ` prohibited matrices over A with k, ` ≥ 2. Then the two-dimensional sequence NA ,S (m, n), m, n ≥ 1, does not satisfy a twodimensional recurrence relation.
The authors wish to thank the referees for several useful insights that helped to improve our paper. The first author acknowledges the support by the projects VEGA 1/0596/17, VEGA 1/0719/18, APVV-15-0220, by the Slovenian Research Agency (research projects N1-0038, N1-0062, J1-9108), and by NSFC 11371307.
The second author acknowledges the support by VEGA 1/0039/17 and VEGA 1/0719/18.