The main result of this chapter can be formulated as follows.
In the section—using the algorithms
]—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.
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
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.
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.
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
in line 10 of
results a doubly symmetric perfect output . In every iteration step (in lines 14–16 of
) 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 .