29.4. 29.4 Two-dimensional perfect arrays

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

As Fan, Fan and Siu proved in 1985, the conditions (2) and (3) are sufficient for the existence of (2,2,a,b)-perfect arrays. Paterson proved the same in 1994 [ 201 ] for -perfect arrays. Later Paterson [ 202 ], [ 203 ] supplied further sufficient conditions.

Hurlbert and Isaak in 1993 gave a construction for one and two dimensional growing arrays.

29.4.1. 29.4.1 Pseudocode of the algorithm Mesh

The following implementation of Mesh was proposed by Iványi and Tóth in 1988. The input of Mesh is the alphabet size and an even sequence w. The output is an -perfect array. It uses the following meshing function [ 134 ]:

Mesh( )

  1  
                     FOR
                   
                   
                  
                     TO
                   
                     2    
                     FOR
                   
                  
                  
                     TO
                   
                     3       
                     IF
                   
                   is even   4             5       
                     ELSE
                   
                     6  
                     RETURN
                   
                   
               

29.4.2. 29.4.2 Pseudocode of the algorithm Cellular

Algorithm Cellular is an extension and combination of the known algorithms Shift, Optimal-Martin, Even and Mesh .

Cellular results a cellular perfect array . Its input data are and , its output is an -perfect array, where and for . Cellular consists of six parts:

  1. Calculation (line 1 in the pseudocode): determines the new alphabet size using formula (29.2);

  2. Walking (lines 2–3): if , then construction of a perfect symmetric sequence using algorithm Optimal-Martin (walking in a De Bruijn graph);

  3. Meshing (lines 4–6): if is even and , then first construct an -ary even perfect sequence using Even, then construct an sized -ary square using meshing function (29.5);

  4. Shifting (lines 7–12): if and ( is odd or ), then use Martin once, then use Shift times, receiving a perfect array ;

  5. Combination (lines 13–16): if is even and , then construct an even sequence with Even , construct a perfect square by Mesh and finally use of Shift times, results a perfect array .

  6. Report (line 17): returns the output .

Cellular( )

  1     2  
                     IF
                   
                     3    
                     Optimal-Martin(
                     
                     )
                     4  
                     RETURN
                   
                     5  
                     IF
                   
                   and  and  is even   6    
                     Mesh(
                     
                     )
                     7    
                     RETURN
                   
                     8  
                     IF
                   
                   is odd or    9    
                     Optimal-Martin(
                     
                     )
                    10    
                     FOR
                   
                   
                  
                     TO
                   
                    11       
                     Shift(
                     
                     )
                    12         13    
                     RETURN
                   
                    14  
                     Mesh(
                     
                     )
                    15  
                     FOR
                   
                   
                  
                     TO
                   
                    16    
                     Shift(
                     
                     )
                    17    18  
                     RETURN
                   
                   
               

Exercises

29.4-1 Construct a -perfect array (a binary double square for window size .