29.2. 29.2 Necessary condition and earlier results

Since in the period of a perfect array each element is the head of a pattern, the volume of equals the number of the possible patterns. Since each pattern—among others the pattern containing only zeros—can appear only once, any size of is greater then the corresponding size of the window. So we have the following necessary condition due to Cock, further Hurlbert and Isaak: If is an -perfect array, then

and

Different construction algorithms and other results concerning one and two dimensional perfect arrays can be found in the fourth volume of The Art of Computer Programming written by D. E. Knuth [ 152 ]. E.g. a (2,1,5,32)-perfect array [ 152 ][page 22], a 36-length even sequence whose 4-length and 16-length prefixes are also even sequences [ 152 ][page 62], a (2,2,2,4)-perfect array [ 152 ][page 38] and a (4,2,2,16)-perfect array [ 152 ][page 63].

It is known [ 42 ], [ 152 ] that in the one-dimensional case the necessary condition (29.3) is sufficient too. There are many construction algorithms, like the ones of Cock [ 56 ], Fan, Fan, Ma and Siu [ 72 ], Martin [ 172 ] or any algorithm for constructing of directed Euler cycles [ 166 ].

Chung, Diaconis and Graham [ 55 ] posed the problem to give a necessary and sufficient condition of the existence of -perfect arrays.

The conditions (29.3) and (29.4) are sufficient for the existence of (2,2,a,b)-perfect arrays [ 72 ] and (n,2,a,b)-perfect arrays [ 201 ]. Later Paterson in [ 202 ], [ 203 ] supplied further sufficient conditions.

Hurlbert and Isaak [ 119 ] gave a construction for one- and two-dimensional growing arrays.