29.7. 29.7 The existence theorem of perfect arrays

The main result of this chapter can be formulated as follows.

In the section—using the algorithms Cellular , Optimal-Martin , Even , Mesh , Shift , Colour [ 115 ], [ 126 ], [ 132 ], [ 134 ], [ 152 ]—we prove the following theorem and illustrate it by the construction of a hypercube.

Theorem 29.1 If , , , and satisfy (29.3) and

a) and , then there exists a -perfect array;

b) , then there exists a -perfect array,where and are suitable positive integers.

The proof is based on the algorithms Cellular , Optimal-Martin , Even , Mesh , Shift , Colour [ 115 ], [ 126 ], [ 132 ], [ 134 ], [ 152 ] and on the following two lemmas.

Lemma 29.2 (Cellular lemma, Horváth, Iványi [ 115 ], [ 132 ]) If and , then algorithm Cellular produces a cellular -perfect array , where is determined by formula (29.2), and .

Proof. It is known that algorithms Even + Mesh and Optimal-Martin + Shift result perfect outputs.

Since Mesh is used only for even alphabet size and for sized window, the sizes of the constructed array are even numbers and so the output array is cellular.

In the case of Shift we exploit that all prime divisors of divide the new alphabet size , and and .

Lemma 29.3 (Indexing lemma, Horváth, Iványi [ 115 ], [ 132 ]) If is a dimensional -cellular array with cells and each cell of contains the corresponding cellindex as an digit -ary number, then any two elements of having the same elementindex and different cellindex are heads of different patterns.

Proof. Let and be two such patterns and let us suppose they are identical. Let the head of in the cell have cellindex and head of in the cell have cellindex (both cells are in array ). Let .

We show that . For example in Fig. 29.2 let the head of be and the head of be . Then these heads are in cells with cellindex 0 and 2 so here .

In both cells, let us consider the position containing the values having local value 1 of some number (in our example they are the elements (3,2) and (3,6) of .) Since these elements are identical, . Then let us consider the positions with local values (in our example they are (3,1) and (3,5).) Since these elements are also identical so . We continue this way up to the elements having local value and get , implying .

This contradicts to the condition that the patterns are in different cells.

Lemma 29.4 (Colouring lemma) If , , is a cellular -perfect array, then algorithm Colour( ) produces a cellular -perfect array , where .

Proof. The input array is -ary, therefore is also -ary. The colouring array contains the elements of , so elements of are in .

The number of dimensions of equals to the number of dimensions of that is, .

Since is cellular and is a multiple of is cellular.

All that has to be shown is that the patterns in are different.

Let us consider two elements of as heads of two windows and their contents – patterns and . If these heads have different cellindex, then the considered patterns are different due to the periodicity of . E.g. in Figure 29.3 has cellindex 8, the pattern headed by has cellindex 2, therefore they are different (see parity of the elements).

If two heads have identical cellindex but different blockindex, then the indexing lemma can be applied.

Proof of the main theorem. Lemma 29.2 implies that the first call of Colour in line 10 of Growing results a doubly symmetric perfect output . In every iteration step (in lines 14–16 of Growing ) the zeroth block of is the same as , since the zeroth cell of the colouring array is filled up with zeros.

Thus is transformed into a doubly symmetric perfect output having the required prefixes .