29.10. 29.10 Finite two-dimensional arrays with maximal complexity

The section starts with definitions, then bounds and several further properties of the complexity functions are given.

29.10.1. 29.10.1 Definitions

Let be a positive integer and an alphabet. Let denote the set of -ary arrays (, positive integers), and the set of finite -ary two-dimensional arrays.

Definition 29.44 Let and be positive integers with and . A -ary array is a subarray of the -ary array if there exist indices such that , and .

According to this definition only nonempty arrays can be -subarrays.

We remark that we are dealing with aperiodic -ary arrays (written on a planar surface, with all the subarrays situated completely within the borders of the array). Another point of view is to consider the given array wrapped round on itself (written on a torus), hence a periodic array. Existence results for periodic and aperiodic arrays which contain every rectangular subarray of given sizes precisely once are given by Paterson [ 201 ], respectively Mitchell [ 180 ].

Notions of complexity similar to those for words can be introduced for arrays.

Definition 29.45 Let be a -ary array and , positive integers with and . Let denote the set of different subarrays of . The subarray complexity function, or, simply, the complexity function of is

and the total complexity function of is

The one-dimensional complexity and total complexity functions were introduced by M. Heinz [ 110 ] in 1977, and studied later by many authors (see e.g. recent papers [ 4 ], [ 6 ], [ 30 ], [ 7 ], [ 44 ], [ 74 ], [ 62 ], [ 251 ]).

Example 29.2 Let be an alphabet and

Then , and .

Definition 29.46 The -ary array is -extremal if

Definition 29.47 The -ary array is -perfect if it contains each of the possible -ary arrays as a subarray exactly once.

Definition 29.48 The arrays consisting of identical letters are called homogeneous arrays, the arrays consisting of different letters are called rainbow arrays.

We mention that a -ary rainbow array exists if and only if . It is obvious that -extremal arrays always exist in for arbitrary values of , , while -perfect arrays can exist only for , satisfying .

Definition 29.49 The function given by

is called maximal complexity function.

Definition 29.50 The -ary array is -maximal if

it is maximal if (29.54) holds for all , .

29.10.2. 29.10.2 Bounds of complexity functions

We present the natural bounds of the complexity function for -ary arrays , as well as those of the total complexity function.

Claim 29.51 (Anisiu, Iványi [ 8 ]) For each -ary array we have

The lower bound is sharp for homogeneous arrays and the upper bound is sharp for rainbow arrays. The total complexity of satisfies the inequality

Proof. From the definition of the subarray it follows that , ; for a homogeneous array the equality holds.

It is obvious that the complexity cannot exceed the total number of subarrays over , that is ; it also cannot exceed the total number of subarrays of dimension of the given array (possible not all different), namely . It follows that . For a rainbow array we have .

By summing up the inequalities (29.55) we obtain (29.56).

Remark 29.52 In terms of the maximal complexity functions, inequality (29.55) may be reformulated as

It follows that every -perfect array, as well as any rainbow array, is -maximal.

The values of the complexity and total complexity for homogeneous and rainbow arrays can be easily computed.

Claim 29.53 (Anisiu, Iványi [ 8 ]) If is a homogeneous array and is an rainbow array, then

and

Proof. The complexity functions and were given in the proof of Proposition 29.51. Easy calculations give the formulas for and .

The shape of the complexity function for words was proved in [ 62 ], [ 160 ], [ 135 ], [ 7 ] to be trapezoidal, i. e. it has an ascending part, possibly a horizontal one, and the last part is a descending line . The main feature is that after becoming constant, the complexity function of an arbitrary word cannot increase again. The question for arrays is: for a fixed , is still trapezoidal? For , the answer is positive, as a consequence of the mentioned result for words; nevertheless, this is not true for all the values . The array in the following example has the property that increases again after becoming a constant.

Example 29.3 For the array given by

one has , and .

29.10.3. 29.10.3 Properties of the maximal complexity function

We shall describe some properties of the function related to the shape of its graph, namely its monotonicity and its maximum.

For (or ) the arrays are in fact finite sequences (words). It was shown in [ 6 ], [ 7 ], [ 62 ] that for a given we have

where is the only natural number for which . The maximum of is equal to and is attained at the unique point for , and at both and for , hence is trapezoidal.

In the remaining part of this section we shall consider proper arrays (with ).

Remark 29.54 If both sizes of the array are smaller than the cardinal of the alphabet , we have

hence

The maximum will be given by

and will be attained at one of the points , or . If , we have ; if , .

In what follows we shall consider .

Claim 29.55 (Anisiu, Iványi [ 8 ]) Let be fixed; the function is trapezoidal, the horizontal part containing at most two points; the last part is a descending line and the maximum of is attained at the first point situated on the descending line, or on .

Proof. The values of are given by the minimum of the values of an increasing exponential and of a descending line. At the beginning, if , will be situated on the exponential, and surely it will end on the descending line. Therefore will have a trapezoidal shape, with a horizontal part with at most two points.

There will be a point which is the least value of for which is on the descending line, i.e. if

The maximal value of will be given by

The maximum of over will be then .

Remark 29.56 The maximum of can be attained at a unique point (for example ) or at several points ().

29.10.4. 29.10.4 On the existence of maximal arrays

In [ 7 ] it was proved, using the results in [ 42 ], [ 58 ], [ 172 ], [ 251 ] that there exist finite words with maximal complexity, of any given length; it follows that there are and maximal arrays for all positive integers and . More than that, in [ 6 ] the number of the words with maximal complexity is presented. Nevertheless, if both and are , the situation differs, as the following proposition shows.

Claim 29.57 (Anisiu, Iványi [ 8 ]) There are sizes , for which there are no arrays with maximal complexity.

Proof. For calculations show that the total complexity of any array is , while . It follows that for each array there exists at least one pair () for which .

Open question Find the pairs for which there exist maximal arrays in .

The result in Proposition 29.57 prevents us from obtaining a -ary array with maximal complexity for any and . A further question is: given , and , , is there an array which is -maximal?

A partial answer is given in [ 180 ]: in the binary case, if , there exists a array which is ()-maximal (in fact it is ()-perfect).

Exercises

29.10-1 Design arrays with maximal complexity for different parameters.

  Problems  

29-1 Comparison of the Martin-type algorithms

Write a program and compare the real running times of Martin (describen in the chapter on the complexity of words), Quick-Martin and Optimal-Martin .

29-2 Characterization of the solutions of equation (29.3)

Characterize the solutions of (29.3) for and .

  Chapter Notes  

Cyclic sequences in which every possible sequence of a fixed length occurs exactly once have been studied for more than a hundred years. The first proof of the existence of -perfect sequences was published by Flye-Sainte [ 76 ] in 1894. The problem was extended to arrays by Fan, Fan, Ma, and Siu in 1985 [ 72 ].

One dimensional perfect arrays are often called de Bruijn or Good sequences, since the papers of De Bruijn [ 42 ] and Good [ 94 ] make these sequences popular. Two dimensional perfect arrays were called perfect maps by Reed and Stewart in 1962 [ 232 ] and by Paterson in 1996 [ 202 ], or de Bruijn tori by Hurlbert and Isaak and Mitchell in 1993 and later [ 118 ], [ 119 ], [ 120 ].

A good and recent review on the one-dimensional results is given in Chapter Complexity of words of this volume.

The even De Bruijn sequences were introduced by A. Iványi and Z. Tóth in 1988 [ 134 ], [ 152 ]. They proposed an algorithm constructing even sequences for arbitrary alphabet size. Later Hurlbert and Isaak [ 119 ] provided an universal algorithm which constructs an infinite sequence whose prefixes are even for the corresponding alphabet size.

The concept of growing sequences was introduced by G. Hurlbert and G. Isaak [ 119 ].

The necessary conditions (29.3) and (29.4) were formulated at first in papers of Cock in 1988 [ 56 ], and in 1994 of Hurlbert and Isaak [ 119 ].

The first growing cubes were constructed by Horváth and Iványi [ 115 ], while the first hypercube by Iványi and Madarász [ 132 ].

The most general existence theorem of double symmetric perfect arrays can be found in [ 132 ].

-complexity was introduced in [ 124 ] and extended by Zoltán Kása in [ 141 ], [ 143 ], [ 142 ].

Interesting properties of De Bruijn graphs are reviewed by James Bond and Antal Iványi in [ 32 ].

Carla Savage [ 248 ] analysed De Bruijn sequences as special Gray codes.

The European Union and the European Social Fund under the grant agreement no. TÁMOP 4.2.1/B-09/1/KMR-2010-0003.