Introduction and problem statement

Perfect binary arrays (PBA) are an important class of algebraic constructions that have found numerous applications in the tasks of cryptographic information protection [1], the synthesis of error correction codes [2], construction of orthogonal and biorthogonal signal systems, antenna aperture synthesis, as well as in many other applications of science and technology [3]. Nevertheless, despite the numerous applications and a large number of publications devoted to the problems of the synthesis of PBA, in the general case, there are no methods for constructing their full classes for the derived value of the PBA order N . Moreover, today there is not even an accurate estimation of the cardinality of the full class of PBA of practically valuable orders 4 N  , in particular order 8 N  . Significant progress in solving the problem of synthesizing the full class of PBA of order 8 N  was obtained in [4], in particular, it was found that the cardinality of the PBA class of order 8 N  is not less than 8x8 688 128 J  , while 688 128 PBA were constructed using the original constructive method.

Another major class of perfect algebraic constructions is the class of the bentsequences (the truth tables of bent-functions), which was introduced in [5] and also found their numerous applications in cryptography and coding theory [6]. Methods for the synthesis of a full class of bent-sequences of length 16 n  (the truth tables of bent-functions of four variables) are described in [7], while constructive methods for the synthesis of a full class of bent-sequences of length 64 n  are proposed in [8,9]. Recent researches of the PBA class carried out in [7]

Basic definitions

We introduce the basic definitions:

Definition 1 [10]. A perfect binary array is a two-dimensional sequence (

1}

i j i j H N h i j N h     ,(1)

having an ideal two-dimensional periodic autocorrelation function (2DPACF), whose elements

   1 1 2 , ,0 0 , 0 ; ( , )

, 0, for any other and ,

N N i j i m j i j N for m R m PACF m h h m                 (2)

where , 0,1,.

N

Let us give as an example a perfect binary array of order 4 N  as well as its twodimensional periodic autocorrelation function 16 0 0 0 0 0 0 0 , 0 0 0 0 0 0 0 0

H R                                   ,(3)

where the symbol "+" denotes +1, and the symbol "-" denotes -1, respectively.

Definition 2 [11]. The Walsh-Hadamard transform (WHT) of a vector ( ) F n in matrix form is defined as

( ) ( ) ( ) f W w A n F n  ,(4)

where ( ) F n is the binary sequence of length n , ( ) A n is the Hadamard matrix of order n , which is constructed in accordance with the following recurrence relation

( / 2) ( / 2) ( ) , (1) [ ]. ( / 2) ( / 2) A n A n A n A A n A n          (5)

Definition 3 [7]. A binary sequence Let us consider the currently known methods of classification of PBA and bentsequences in order to establish the interrelation between these classes of perfect algebraic constructions. The modern approach to the classification of PBA involves the use of the following proposition: [3].

0 1 1 [ , , , , , ] i n B b b b b     of

In [7] it was shown that the full class of bent-sequences of length 16 n  includes the full class of PBA of order 4 N  in the case of their representation as vectors by successive concatenation of the rows (columns) of the corresponding PBA.

For example, we concatenate the rows of PBA (3), as a result of which we obtain the following sequence and its Walsh-Hadamard transform coefficients in accordance with (4)

B B W w A B                         (7)

It is easy to see that the sequence (7) really satisfies the condition of Definition 3 and is a bent-sequence of length 16 n  .

A modern approach to the classification of bent-sequences is based on the consideration of affine-equivalent classes. This classification is easiest to make on the basis of the representation of bent-sequences in algebraic normal form.

Definition 4 [11]. The algebraic normal form (ANF)

1 2 φ( , ,..., ) k x x x of a sequence T is a polynomial of 2 log k n  variables with coefficients {0,1} i a 

, where the AND operation is used as the multiplication, and the XOR operation is used as the addition operation

  1 1 2 0 φ , ,..., N s k i i i x x x a X     ,(8)

where s i X are the terms of the ANF polynomial of degree

  s wt X  ;

wt is the Hamming's weight. The coefficients

  0 1 1 , ,..., i N a a a a  

can be found by performing the Reed-Muller transform [11], i.e. by multiplying the original sequence by the Reed-Muller matrix

ν RM ν ν { } , { } i i a T RM T a RM     ,(9)

where the original sequence T is represented above the alphabet {0,1} using a bijective mapping 1 0, 1 1     , and the Reed-Muller matrix ν RM is determined using the following recurrent rule

  ν 1 0 ν ν 1 ν 1 ν1 0 1 0 1 , 1 1 RM RM RM RM RM RM                     , (10)

where  is the Kronecker product.

Definition 5 [11]. Terms of ANF of the degree   1 s wt X   are called as affine.

For example, for sequence length 16 n  there are the following possible affine terms:

0 1 2 3

1, , , , x x x x on the basis of which corresponding affine codewords can be formed.

For example, we can represent as the ANF obtained from the PBA bent-sequence (7)

1 3 4 1 2 B x x x x   . (11)

It is known [8] that the sum of a bent-sequence with an affine function (which is equivalent to adding one or several affine terms to the ANF coefficients sequence) leads to the formation of other bent-sequences. Thus, the full set of bent-sequences of cardinality 896 J  can be classified into 896 / 32 28  affine non-equivalent classes, in each of which it is possible to distinguish a bent-sequence that does not have affine terms.

In this paper, through numerous experiments, the following statement was established:

Proposition 2. Let 0

H to be PBA of order 4 N  , and 0

T to be the sequence obtained by concatenating its rows (columns). Then the sequences , ,..., k H H H   that are also PBA. Note that the Proposition 2 is valid only for PBA of order 4 N  , and fully corresponds to Proposition 1, in terms of structure. However, Proposition 2 makes it easy to establish the interconnection between the generating PBA represented as their ANF (which contain affine terms) and the corresponding generating bent-sequences. We present all 28 generating bent-sequences, among which 12 (in bold font) generates affine non-equivalent classes of PBA of cardinality 32 PBA in each one, corresponding to Proposition 2 In the general case, the problem of synthesizing a complete class of PBA of order 8 N  is computationally complex and has not been solved yet. Significant progress in the construction of PBA classes was made in [4], where a method for synthesizing the PBA class based on the classes of thinned matrices was proposed and the constructions for their reproduction and superposition were found.

b x x x x b x x x x x x b x x x x x x b x x x x x x x x b x x x x x x b x x x x x x x x b x x x x                       1 2 3 1 4 2 2 3 1 4 1 2 3 2 3 1 4 1 3 4 2 3 1 4 1 3 1 2 b = x x + x x b = x x + x x + x x b = x x + x x + x x b = x x + x x + x x +

b = x x + x x + x x b = x x + x x + x x + x x b = x x + x x + x x b = x x + x x + x x + x x b = x x + x x + x x b = x x + x x + x x + x x b = x x + x x b = x x + x x + x xx x x x b x x x x x x b x x x x x x x x b x x x x x x x x b x x x x x x x x b x x x x x x x x b x x x x x x x x b x x x x x x x x x x x x                              (12

The results of [4] are based on the following proposition:

Proposition 3 [3].

The PBA 0 ( ) H N of the arbitrary order N can always be represented as an interleaving (  ) of its thinned matrices 0 , , , , ,

0 0 0 0 ( ) ( / 2) ( / 2) ( / 2) ( / 2), i j i j i j i j i j H N h a b c d A N B N C N D N          (13)

where h vary within the limits , 0,1,...,

, 2, 2 i j i j a h  , , 2, 2 1 i j i j b h   , , 2 1 , 2 i j i j c h   , ,2 11 i j N   .

Each PBA can be represented as (13). In the general case, the set of various structures of thinned matrices obtained by thinning the full class of PBA, we denote as

i j A B C D A N B N C N D N i j              , (14)

where the parameters A  , B  , C  , D  are the number of different structures (degrees of freedom) of the corresponding thinned matrices , , , A B C D of order / 2 N . Different matrix structures from ( 14) can be obtained by using the cyclic shift operations in rows and columns, inversion, transposition, and mirroring of the set of generating matrices.

In [4], such a set of thinned matrices was obtained, the structures of which are presented in Table 1.

A                         

16 0 16 0 0 0 0 0 16 0 16 0 0 0 0 0

A R          B                         

16 0 16 0 0 0 0 0 16 0 16 0 0 0 0 0

B R            C                          16 0 16 0 0 0 0 0 16 0 16 0 0 0 0 0 C R            D                          16 0 16 0 0 0 0 0 16 0 16 0 0 0 0 0 D R            0 A                          0 16 16 16 16 0 0 0 0 0 0 0 0 0 0 0 0 A R          0 E                          0 16 16 16 16 0 0 0 0 0 0 0 0 0 0 0 0 E R            1 A                          1 16 0 0 0 16 0 0 0 16 0 0 0 16 0 0 0 A R          1 E                          1 16 0 0 0 16 0 0 0 16 0 0 0 16 0 0 0 E R            2 A                          2 16 0 0 0 0 16 0 0 0 0 16 0 0 0 0 16 A R          2 E                          2 16 0 0 0 0 16 0 0 0 0 16 0 0 0 0 16 E R            A                          3 16 0 0 0 0 0 0 16 0 0 16 0 0 16 0 0 A R          3 E                          3 16 0 0 0 0 0 0 16 0 0 16 0 0 16 0 0 E R            4 A                          4 16 0 16 0 0 0 0 0 0 16 0 16 0 0 0 0 A R          4 E                          4 16 0 16 0 0 0 0 0 0 16 0 16 0 0 0 0 E R            5 A                          5 16 0 0 0 0 0 16 0 16 0 0 0 0 0 16 0 A R          5 E                          5 16 0 0 0 0 0 16 0 16 0 0 0 0 0 16 0 E R           

As a result, the PBA class of cardinality 8 8 688 128 PBA J   was built, which increased the lower bound estimation of the cardinality of PBA class of order 8 N  in factor of 7 compared to the previous result obtained in [12].

It is known, that all the representatives of PBA class of the order 4 N  , when concatenating the PBA rows (columns) generates bent-sequences. The research carried out in this paper allowed us to establish that there are just 8 8, 98 304

PBA bent J   

representatives in the PBA class of order 8 N  (synthesized in [4]) that forms the bent-sequences of length 64 n  when concatenating their rows (columns). At the same time, the other 688 128 98 304 589 824   PBA (when concatenating rows or columns) have non-uniform Walsh-Hadamard transform coefficients (absolute values). In order to classify these spectral coefficients, it is most convenient to use the definition of the elementary structure of the Walsh-Hadamard transform coefficients [13].

Definition 6 [13]. The elementary structure of the vector ( ) W  of Walsh-Hadamard transform coefficients is the set of absolute values of its spectral components. It was established experimentally that all remaining 589 824 PBA, on the basis of which it is impossible to form bent-sequences by applying the operation of concatenation of their rows (columns), according to Definition 6, have an elementary structure {0(12), 8(48), 16(4)} .

This notation of the elementary structure should be understood as follows: the number in front of the parentheses characterizes the absolute value of the Walsh-Hadamard transform coefficient, whereas the number in parentheses indicates how many times it occurs in the vector of the Walsh-Hadamard transform coefficients.

Let us consider, for example, one of these PBA, as well as its 2DPACF 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 , 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

H R                                                                                                    . (15)

Applying the concatenation of the rows (columns) of PBA (15), we obtain a binary sequence and, according to Definition 2, corresponding to it vector of Walsh-Hadamard transform coefficients, which has an elementary structure {0(12), 8(48), 16(4 The research performed in this paper shows that establishing the interrelation between the class of PBA of order 8 N  and the class of bent-sequences of length 64 n  can significantly increase the lower bound of the number of PBA due to their new structures, that exist in the class of bent-sequences.

)} { }; { T T W                                                                   

Note that, in the general case, the problem of synthesizing bent-sequences of length 64 n  is a complex computational problem, coupled with the enumeration of a set of 64 2 18 446 744 073709551616 J   elements. Nevertheless, the theory of bentsquares that was proposed in [14], with the help of which it was possible to synthesize the full set of bent-sequences of length 64 n  which have the cardinality PBA bent J    PBA, that was constructed in [4].

As an example, we present one of the PBA and it's 2DPACF, that was found in the bent-sequences of the length 64 n  class and is not member of set of PBA synthesized in [4] 8

H                                                                                 

, 64 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

R                  . (17)

We concatenate the PBA (17) rows, as a result of which we obtain the following sequence and its Walsh-Hadamard transform coefficients in accordance with (4)

[ ]; [ B B W                                                                                      ],

             (18) which proves that (18) is indeed a bent-sequence.

Note that PBA (17) consists of thinned matrices presented in Table . 2. These structures of thinned matrices differ from the matrices presented in Table 1. This fact shows that there are exist other structures of thinned matrices that differ from those found in [4].

A                           16 0 16 0 8 0 8 0 0 0 0 0 8 0 8 0 A R           B                           16 0 16 0 8 0 8 0 0 0 0 0 8 0 8 0 B R               C                           16 0 16 0 0 8 0 8 0 0 0 0 0 8 0 8 C R              D                           16 0 16 0 0 8 0 8 0 0 0 0 0 8 0 8 D R             

Thus, the discovering of the interrelation between the class of PBA of order 8 N  and bent-sequences of length 64 n  allows us to improve the estimation of the lower bound of the cardinality of PBA class of order 8 N  . Summarizing, it was established that in [4], the PBA class that produces the bent-sequences has cardinality

J    ,(19)

which is larger by a factor of ~4.2 compared to the estimation in [4].

Conclusion

We note the main results obtained in the paper:

1. The lower bound estimation for the cardinality of the class of the PBA of order 8 N  is improved. In particular, it has been established that the cardinality of the PBA class of order 8 N  is not less than It should be noted that the search for new structures of thinned matrices, as well as the rules for their interleaving for formal enumeration of the PBA full class that generates bent-sequences, is an actual direction for further research. The number of PBA, which generate sequences with other (different from the bent-sequences) elementary structures of the Walsh-Hadamard transform vectors also remains unknown and can be the actual direction for further research.