29.6. 29.6 Construction of growing arrays using colouring

In this section particular constructions are presented.

29.6.1. 29.6.1 Construction of growing sequences

As the first example let and . Cellular calculates and Martin produces the cellular (2,1,2,4)-perfect sequence .

Since is symmetric, . Now Growing chooses multiplication coefficient , extension vector and uses Colour to construct a 4-ary perfect sequence.

Colour arranges copies into a blocks sized array receiving

Colour receives the indexing scheme and the colouring matrix transforming the elements of into digit length -ary numbers: .

Finally we colour the matrix using – that is multiply the elements of by and add the -th block of to both cells of the -th copy in :

Since , we use Colour again with and get the (8,1,2,64)-perfect sequence repeating 4 times, using the same indexing array and colouring array .

Another example is and . To guarantee the cellular property now we need a new alphabet size . Martin produces a (6,1,2,36)-perfect sequence , then Colour results a (12,1,2,144)-perfect sequence .

29.6.2. 29.6.2 Construction of growing squares

As the first example let and . Then . We construct the even sequence using Even and the symmetric perfect array in Figure 29.1.a using the meshing function (29.5). Since is symmetric, it can be used as . Now the greatest common divisor of and is 2, therefore indeed .

Figure 29.1.  a) A (2,2,4,4)-square;           b) Indexing scheme a) A (2,2,4,4)-square;           b) Indexing scheme I of size 4\times4 of size a) A (2,2,4,4)-square;           b) Indexing scheme I of size 4\times4

a) A (2,2,4,4)-square;           b) Indexing scheme I of size 4\times4

Growing chooses and Colour returns the array repeating the array times.

Colour uses the indexing scheme containing indices in the same arrangement as it was used in . Figure 29.1.b shows .

Transformation of the elements of into 4-digit -ary form results the colouring matrix represented in Figure 29.2.

Figure 29.2.  Binary colouring matrix Binary colouring matrix C of size 8\times8 of size Binary colouring matrix C of size 8\times8

Binary colouring matrix C of size 8\times8

Colouring of array using the colouring array results the (4,2,2,16)-square represented in Figure 29.3.

In the next iteration Colour constructs an 8-ary square repeating times, using the same indexing scheme and colouring by . The result is , a -perfect square.

Figure 29.3.  A (4,2,2,16)-square generated by colouring

A (4,2,2,16)-square generated by colouring

29.6.3. 29.6.3 Construction of growing cubes

If , then the necessary condition (29.4) is for double cubes, implying is a cube number or is a multiple of 3. Therefore, either and then , or and so , that is, the smallest possible perfect double cube is the (8, 3, 2, 256)-cube.

As an example, let and . Cellular computes , Mesh constructs the -perfect square in Figure 29.1.a, then Shift uses Optimal-Martin with and to get the shift sizes for the layers of the -perfect output of Cellular , where . Shift uses as zeroth layer and the th layer is generated by cyclic shifting of the previous layer downwards by (div 4) and right by (mod 4), where . 16 layers of are shown in Figure 29.5.

Let be a sized perfect, rectangular matrix, whose 0th layer is the matrix represented in Figure 29.1, and the -perfect array in Figure 29.5, where and .

Growing uses Colour to retrieve a doubly symmetric cube. , thus and , that is we construct the matrix repeating times.

has the size and . Colour gets the colouring matrix by transforming the elements of into 8-digit -ary numbers – and arrange the elements into sized cubes in lexicographic order – that is in order (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1). Finally colouring results a double cube .

contains elements therefore it is presented only in electronic form (on the home page of the first author).

If we repeat the colouring again with , then we get a 64-ary sized double cube .

29.6.4. 29.6.4 Construction of a four-dimensional double hypercube

In 4 dimensions the smallest 's satisfying (29.3) are and . But we do not know algorithm which can construct -perfect or -perfect hypercube. The third chance is the -perfect hypercube. Let and . Cellular calculates , then calls Optimal-Martin receiving the cellular -perfect sequence . Then Cellular calls Mesh which constructs the cellular -perfect square shown in Figure 29.4.

Figure 29.4.  A (2,2,4,4)-square

A (2,2,4,4)-square

Now Shift calls Optimal-Martin with and to get the shift sizes for the layers of the -perfect output of Cellular , where . Shift uses as zeroth layer and the th layer is generated by cyclic shifting of the previous layer downwards by (div 4) and right by (mod 4), where . The layers of the -perfect array are shown in Figure 29.5.

Figure 29.5.  Sixteen layers of the Sixteen layers of the (2,3,2,16) -perfect output of Shift-perfect output of Shift

Sixteen layers of the (2,3,2,16) -perfect output of Shift

Up to this point the construction is the same as in [ 115 ], but now , therefore we use Shift again to get a -perfect prism, then we fill an empty cube with -sized prisms and finally colouring results the required 4-dimensional hypercube.

Exercises

29.6-1 Explain the construction of Figure 29.5.