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

In the section—using the algorithms *
Cellular
*,

`Optimal-Martin`

`Even`

`Mesh`

`Shift`

`Colour`

**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`

**Lemma 29.2 **(Cellular lemma, Horváth, Iványi [
115
], [
132
]) *If and , then algorithm *
*
Cellular
*

**Proof. **It is known that algorithms *
Even
* +

`Mesh`

`Optimal-Martin`

`Shift`

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`

`Growing`

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