# Simplicity conditions for binary orthogonal arrays

Claude Carlet, Rebeka Kiss, Gábor Nagy

► To cite this version:

Claude Carlet, Rebeka Kiss, Gábor Nagy. Simplicity conditions for binary orthogonal arrays. Designs, Codes and Cryptography, 2022, 91 (1), pp.151-163. 10.1007/s10623-022-01105-4. hal-03960664

HAL Id: hal-03960664

https://hal.science/hal-03960664v1

Submitted on 17 Sep 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Simplicity conditions for binary orthogonal arrays

Claude Carlet<fnref n="1" />,<fnref n="2" /> · Rebeka Kiss<fnref n="3" /> · Gábor P. Nagy<fnref n="3" />,<fnref n="4" />

Received: 20 April 2022 / Revised: 6 August 2022 / Accepted: 11 August 2022 / Published online: 31 August 2022
© The Author(s) 2022

## Abstract

It is known that correlation-immune (CI) Boolean functions used in the framework of side channel attacks need to have low Hamming weights. The supports of CI functions are (equivalently) simple orthogonal arrays, when their elements are written as rows of an array. The minimum Hamming weight of a CI function is then the same as the minimum number of rows in a simple orthogonal array. In this paper, we use Rao’s Bound to give a sufficient condition on the number of rows, for a binary orthogonal array (OA) to be simple. We apply this result for determining the minimum number of rows in all simple binary orthogonal arrays of strengths 2 and 3; we show that this minimum is the same in such case as for all OA, and we extend this observation to some OA of strengths 4 and 5. This allows us to reply positively, in the case of strengths 2 and 3, to a question raised by the first author and X. Chen on the monotonicity of the minimum Hamming weight of 2-CI Boolean functions, and to partially reply positively to the same question in the case of strengths 4 and 5.

Communicated by L. Teirlinck.

The research of C. Carlet is partly supported by the Trond Mohn Foundation and Norwegian Research Council. For R. Kiss and G.P. Nagy, support has been provided from the National Research, Development and Innovation Fund of Hungary, financed under the 2018-1.2.1-NKP funding scheme, within the SETIT Project 2018-1.2.1-NKP-2018-00004. The research of G.P. Nagy is partly supported by NKFIH-OTKA Grant SNN 132625.

<figure><img src="image_2.png" /></figure>

Gábor P. Nagy
nagy.gabor.peter@tkk.bme.hu; nagyg@math.u-szeged.hu

Claude Carlet
claude.carlet@gmail.com

Rebeka Kiss
Kiss.Rebeka@stud.u-szeged.hu

<footnote n="1">¹ Dept of Math. Univ. Paris 8, 2 rue de la Liberté, Universities of Paris 8 and Paris 13, CNRS LAGA (UMR 7539), 93 526 Saint-Denis Cedex, France</footnote>

<footnote n="2">² Department of Informatics, University of Bergen, PB 7803, 5020 Bergen, Norway</footnote>

<footnote n="3">³ Bolyai Institute, University of Szeged, Aradi vértanúk tere 1, Szeged 6720, Hungary</footnote>

<footnote n="4">⁴ Department of Algebra, Budapest University of Technology and Economics, Műegyetem rkp 3,
Budapest 1111, Hungary</footnote>
**Keywords** Orthogonal array · Correlation-immune · Boolean function · Rao's bound · Linear programming bound

**Mathematics Subject Classification** 05B05

# 1 Introduction

In cryptography, correlation immune (CI) functions are those Boolean functions over $\mathbb{F}_2^k$ whose output distribution does not change when at most $t$ input bits are fixed, where $t \le k$ is the correlation immunity order, whatever is the choice of these input bits and whatever are the values to which they are fixed. As shown in [19], they are those $k$-variable Boolean functions whose Fourier transform $\hat{f}(a) = \sum_{x \in \mathbb{F}_2^k} f(x)(-1)^{a \cdot x}$ (where “.” is the usual inner product in $\mathbb{F}_2^k$) vanishes for all nonzero inputs $a \in \mathbb{F}_2^k$ of Hamming weight at most $t$. In other words, the supports of these functions are unrestricted (i.e., linear or nonlinear) binary codes of dual distance at least $t+1$. The correlation immunity of a function $f$ allows the resistance against the Siegenthaler correlation attack on the stream ciphers using $f$ as a combining function (see [4] for more details). CI functions can also be used for implementing the rotating S-box masking counter-measure against side channel attacks (see [4] as well). We can reduce the cost of this counter-measure by finding, for given $k$ and $t$, the minimum Hamming weight $w_{k,t}$ of $t$-th order CI-functions in $k$ variables, that is the minimal size of their supports, and then by using a CI function of such weight in the implementation. The first author and Guilley [5, 6] published a table containing the values of $w_{k,t}$ for small $k, t$. It is difficult to give these values even for small parameters, this is demonstrated by the facts that the table is limited to $k \le 13$ and even then, there are missing values in the table.

CI-functions are closely related to orthogonal arrays, introduced by C.R. Rao [16] in 1947. Let $N, t, k$ be positive integers, $t \le k$, and $S$ a finite set of cardinality $s$. An $N \times k$ array $A$ with entries from $S$ is said to be an orthogonal array with $s$ symbols, strength $t$, and index $\lambda$, if every $N \times t$ subarray of $A$ contains each $t$-tuple based on $S$ exactly $\lambda$ times as a row. We will denote such an array by $OA(N, k, s, t)$. We have $\lambda = N/s^t$. An orthogonal array is called simple if the rows are distinct. Supports of $t$-th order CI-functions give simple binary orthogonal arrays with strength $t$, if their elements are written as rows, and vice versa.

In the theory of orthogonal arrays, for both simple and general orthogonal arrays, the main question is to give—for given numbers $k$ of columns and $s$ of symbols, and for strength $t$—the minimum value of $N$ for which an orthogonal array $OA(N, k, s, t)$ exists with $N$ rows. We will denote this value by $F^*(k, s, t)$ for simple orthogonal arrays (we have then $w_{k,t} = F^*(k, 2, t)$) and by $F(k, s, t)$ for general orthogonal arrays. This problem is very hard even for the smallest parameters $s = t = 2$. In fact, a binary orthogonal array of strength 2 with $k$ columns and $k+1$ rows is equivalent to a Hadamard matrix of order $k+1$. A Hadamard matrix of order $n$ is an $n \times n$ matrix whose entries are either +1 or -1, and whose rows are mutually orthogonal. The famous Hadamard conjecture proposes that a Hadamard matrix of order $n$ exists if and only if $n$ is divisible by 4. Equivalently in our notation: $F(k, 2, 2) = k+1$ if and only if $k$ is congruent to 3 modulo 4.

For some lower bounds on the number $N$ of rows, it is known that if an $OA(N, k, s, t)$ attains this special bound, then it is simple. For example, this is true for the Friedman-Bierbrauer bound [1]

$$N \ge s^k \left( 1 - \frac{(s-1)k}{s(t+1)} \right).$$
Indeed, it is seen from the proof that any multiplicity greater than 1 makes the inequality strict. For binary orthogonal arrays of strength $t \ge (2k - 2)/3$, the bound $N \ge 2^{k-1}$ implies simplicity in the case of equality, see [13].

In [6], the first author and Guilley asked the following question:

**problem 1** (Carlet-Guilley) Is $F^*(k, 2, t)$ a monotone non-decreasing function when $k$ grows and $t$ remains fixed?

The same question for $F(k, s, t)$ is trivial, since an OA($N, k, s, t$) gives rise to an OA($N, k - 1, s, t$) by deleting one of the columns. Moreover, if $F(k, s, t) = F^*(k, s, t)$, then

$$F^*(k, s, t) \le F(k + 1, s, t) \le F^*(k + 1, s, t).$$

Hence, the solution of the following problem would imply an answer to the problem posed by the first author and Guilley:

**problem 2** Find all parameters $k, s, t$ such that $F(k, s, t) = F^*(k, s, t)$.

In this paper, we give a partial answer to Problem 2. Our main theoretical result is the following:

**Theorem 1** Let A be an OA($N, k, s, 2u$). Define the integer

$$M(k, s, 2u) = \sum_{j=0}^{u} \binom{k}{j} (s-1)^j.$$

(i) If A has a row of multiplicity $\rho$, then $N \ge \rho M(k, s, 2u)$.

(ii) If $N < 2 M(k, s, 2u)$, then A is simple. If $N < 3 M(k, s, 2u)$, then each row of A has multiplicity at most 2.

(iii) If $k \ge 5$, $s = 2$, $u = 2$ and

$$N = 2 M(k, 2, 4) = k^2 + k + 2,$$

then either A is simple, or $k = 5$ and A is obtained by the juxtaposition of two identical arrays OA(16, 5, 2, 4).

Part (ii) of Theorem 1 implies a sufficient condition for the parameters $k, s, t$ to fulfill Problem 2:

**Corollary 2** If $t$ is even and

$$F(k, s, t) < 2 M(k, s, t)$$

then

$$F^*(k, s, t) = F(k, s, t).\square$$

Notice that the integer $M(k, s, t)$ is the lower bound for the number of rows in an orthogonal array with $k$ columns, $s$ symbols and strength $t$, given in Rao's famous theorem [11, Theorem 2.1]:

$$F(k, s, t) \ge M(k, s, t) \quad \text{for all positive integers } k, s, t. \qquad (1)$$

For part (iii) of Theorem 1, we observe that $M(5, 2, 4) = 16$, and up to equivalence, there is a unique OA(16, 5, 2, 4). If we assume that such an array has an all-0 row, then all its rows have an even number of 1s.
<table><caption>**Table 1** Number of rows in minimal simple orthogonal arrays with given number of columns and given strength</caption><thead><tr><th>k\t</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th></tr></thead><tbody><tr><td>1</td><td>2</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>2</td><td>2</td><td>4</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>3</td><td>2</td><td>4</td><td>8</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>4</td><td>2</td><td>8</td><td>8</td><td>16</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>5</td><td>2</td><td>8</td><td>16</td><td>16</td><td>32</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>6</td><td>2</td><td>8</td><td>16</td><td>32</td><td>32</td><td>64</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>7</td><td>2</td><td>8</td><td>16</td><td>64</td><td>64</td><td>64</td><td>128</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>8</td><td>2</td><td>12</td><td>16</td><td>64</td><td>128</td><td>128</td><td>128</td><td>256</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>9</td><td>2</td><td>12</td><td>24</td><td>128</td><td>128</td><td>256</td><td>256</td><td>256</td><td>512</td><td></td><td></td><td></td><td></td></tr><tr><td>10</td><td>2</td><td>12</td><td>24</td><td>128</td><td>256</td><td>512</td><td>512</td><td>512</td><td>512</td><td>1024</td><td></td><td></td><td></td></tr><tr><td>11</td><td>2</td><td>12</td><td>24</td><td>A</td><td>A'</td><td>512</td><td>1024</td><td>1024</td><td>1024</td><td>1024</td><td>2048</td><td></td><td></td></tr><tr><td>12</td><td>2</td><td>16</td><td>24</td><td>A</td><td>A'</td><td>B</td><td>1024</td><td>2048</td><td>2048</td><td>2048</td><td>2048</td><td>4096</td><td></td></tr><tr><td>13</td><td>2</td><td>16</td><td>32</td><td>A</td><td>A'</td><td>C</td><td>B'</td><td>4096</td><td>4096</td><td>4096</td><td>4096</td><td>4096</td><td>8192</td></tr></tbody></table>

We conclude this section with Table 1, which shows the values of $F^*(k, 2, t)$ for $1 \le k, t \le 13$; it is a reproduction of the tables in [5, 6, 18]. Using old and new computational results, and Theorem 1, we were able to fill in new entries in Table 1, denoted by capital letters. For previously known entries we colored the cells; the meaning of the colors are explained below.

**gray** The light gray fields are trivial. The dark gray fields are consequences of the Fonder-Flaass Theorem [8].

**yellow** The yellow fields are related to the constructions of Hadamard matrices, to the famous Hadamard Conjecture, and to a recent conjecture by the first author and Chen, see Sect. 4 for details.

**green** The values equal to Delsarte's LP Bound, and the construction is given by a linear code of codimension 2, see [5, 6, 18].

**red** The first author and Guilley [6] contributed the values by using the Satisfiability Modulo Theory (SMT) tool z3 [7]. The upper bound follows from a well-known construction that is related to shortening of the non-linear binary Kerdock code of length 16, see [12].

**A, A'** $A = 128$ and $A' = 256$, see Proposition 12(A).

**B, B'** $B = 768$ and $B' = 1536$. The values equal to Delsarte's LP Bound. The existence and uniqueness of an OA(1536, 13, 2, 7) has been shown recently by Krotov [15]. See Proposition 12(B) for an independent construction.

**C** $C = 1024$, see Proposition 12(C) and [18].

## 2 Preliminary results

In this section, we collected some preliminary results and notation on the minimum number of rows of an orthogonal array with $k$ rows, $s$ symbols and strength $t$. Recall the definition
$$ 
\begin{aligned}
F(k, s, t) &= \min\{N \mid \exists OA(N, k, s, t)\}, \\
F^*(k, s, t) &= \min\{N \mid \exists \text{ simple } OA(N, k, s, t)\}.
\end{aligned}
$$

**Lemma 3**

$$ F(k, s, t) \le F^*(k, s, t), \qquad (2) $$

$$ F(k, s, t) \le F(k + 1, s, t), \qquad (3) $$

$$ 2F(k, 2, 2u) = F(k + 1, 2, 2u + 1), \qquad (4) $$

$$ 2 F^*(k, 2, 2u) = F^*(k + 1, 2, 2u + 1). \qquad (5) $$

**Proof** 2 and 3 are trivial. [11, Theorem 2.24] and [11, Corollary 2.25] imply 4. 5 holds by [5, Proposition 2.6]. □

**Remark 4** Equation (5) implies that it suffices to deal with orthogonal arrays of even strength $t = 2u$ when studying the Carlet–Guilley problem and Problem 2. This also shows that in the case of binary orthogonal arrays ($s = 2$), one can use Theorem 1 to investigate the simplicity of arrays of odd strength.

**Remark 5** For all integer $m$, duals of certain double-error-correcting BCH codes provide arrays OA$(2^{2m+1}, 2^m + 1, 2, 5)$, and OA$(2^{2m}, 2^m, 2, 4)$ by 5. (See [11, p. 103].) If $k$ is an integer with $2^{m-1} < k \le 2^m$, then

$$ F(k, 2, 4) \le F(2^m, 2, 4) \le 2^{2m} < 4k^2. $$

By Rao's Bound, $F(k, 2, 4) \ge (k^2 + k + 2)/2$. This shows that asymptotically, $F(k, 2, 4)$ and $F(k, 2, 5)$ are quadratic functions of $k$.

For tuples $u, v \in \{0, \dots, s-1\}^k$, $w_H(u)$ denotes the Hamming weight, and

$$ uv^T = \sum_{i=1}^{k} u_i v_i $$

denotes the usual inner product (sometimes also denoted by $u \cdot v$ or by $\langle u, v \rangle$). For a matrix $H$ with complex entries, $H^*$ is the conjugate transpose of $H$. In particular, for complex (row) vectors $u, v \in \mathbb{C}^n$,

$$ uv^* = \sum_{i=1}^{n} u_i \bar{v}_i. $$

The 2-norm of $u \in \mathbb{C}^n$ is

$$ \|u\| = \sqrt{u u^*}. $$

Fix a primitive $s$-th root of unity $\zeta$. Let $A$ denote an $N \times k$ array with entries from $\{0, \dots, s-1\}$. The $i$-th row of $A$ is denoted by $a_i$. For $1 \le i \le N$ and $v \in \{0, \dots, s-1\}^k$, we write:

$$ \alpha_{i,v} = \zeta^{a_i v^T}. \qquad (6) $$

Clearly, for the zero vector $v = 0$, we have $\alpha_{i,0} = 1$. For any $v, v'$, we have

$$ \alpha_{i,v} \alpha_{i,v'} = (\zeta^{a_i v^T})(\zeta^{a_i (v')^T}) = \zeta^{a_i (v+v')^T} = \alpha_{i,v+v'}. $$
and

$$ \bar{\alpha}_{i,v} = \zeta^{-a_i v^T} = \zeta^{a_i (-v)^T} = \alpha_{i,-v}. $$

**Lemma 6** The following statements are equivalent:

(i) The array A is an OA(N, k, s, t).

(ii) $\sum_{i=1}^{N} \alpha_{i,v} = 0$ for any $v \in \{0, \dots, s-1\}^k$ with $1 \le w_H(v) \le t$.

(iii) $\sum_{i=1}^{N} \alpha_{i,v} \bar{\alpha}_{i,v'} = 0$ for any $v, v' \in \{0, \dots, s-1\}^k$ with $w_H(v) + w_H(v') \le t$.

**Proof** The equivalence of (i) and (ii) is precisely [11, Theorem 3.30]. Setting $v' = 0$, we obtain (ii) from (iii). For any $v, v'$, we have $\alpha_{i,v} \bar{\alpha}_{i,v'} = \alpha_{i,v-v'}$. As $w_H(v-v') \le w_H(v) + w_H(v') \le t$, (ii) implies (iii). □

**Remark 7** For binary arrays ($s = 2$), Lemma 6(ii) is the Xiao-Massey characterization of $k$-variable $t$-CI Boolean functions, see [19] or [5, Theorem 2.2].

### 3 The proof of the main theorem

The proof of [11, Theorem 2.1] is based on the introduction of two matrices $H$ and $Q$. We shall see that the same matrices can be used for proving our result.

**Proof of Theorem 1** Without loss of generality, we assume that the entries of $A$ are from $\{0, \dots, s-1\}$. For any $0 \le j \le u$, we define the $N \times \binom{k}{j} (s-1)^j$ matrix $H_j$ in the following way. The columns of $H_j$ are indexed with the tuples $v \in \{0, \dots, s-1\}^k$ of Hamming weight $j$. For $1 \le i \le N$ and tuple $v$ with $w_H(v) = j$, the entry $(i, v)$ of $H_j$ is $\alpha_{i,v}$. The matrix:

$$ H = [H_0 H_1 \cdots H_u] $$

has $N$ rows and

$$ M = \sum_{j=0}^{u} \binom{k}{j} (s-1)^j = M(k, s, 2u) $$

columns. Any two columns of $H$ are orthogonal complex vectors by Lemma 6(iii). Moreover, if column $h$ of $H$ is indexed by the tuple $v$, then

$$ h^*h = \sum_{i=1}^{N} \bar{\alpha}_{i,v} \alpha_{i,v} = N. $$

This means that $H^*H = NI$, and the columns of $\frac{1}{\sqrt{N}}H$ form an orthonormal set of vectors in $\mathbb{C}^N$. This set can be extended into an orthonormal basis of $\mathbb{C}^N$. In other words, one can add columns to $\frac{1}{\sqrt{N}}H$ such that one obtains an $N \times N$ unitary matrix $Q$. Each row of $Q$ has the form $[u u']$, where $u$ is a vector of length $M$, with entries $\frac{\zeta^{a_i v^T}}{\sqrt{N}}$. In particular,

$$ \|u\| = \sqrt{M/N}, \quad \|u'\| = \sqrt{1 - M/N}. \qquad (7) $$

Let us assume that the rows $i_1, \dots, i_\rho$ of $A$ are equal. Then, the rows $i_1, \dots, i_\rho$ of $H$ are equal, and, the rows $i_1, \dots, i_\rho$ of $Q$ have the form

$$ [u u_{(r)}], \quad r = 1, \dots, \rho. $$
The rows of $Q$ form an orthonormal basis, thus for all $1 \le r \ne s \le \rho$,

$$0 = uu^* + u_{(r)}u_{(s)}^* \quad (8)$$

Assume that $N < \rho M$. Then 7 and 8 imply

$$u_{(r)}u_{(s)}^* < -\frac{1}{\rho} \quad (r \ne s). \quad (9)$$

We have

$$\begin{aligned} 0 &\le \left\| \sum_{r=1}^{\rho} u_{(r)} \right\|^2 \\ &= \sum_{s,r=1}^{\rho} u_{(r)}u_{(s)}^* \\ &= \rho \left(1 - \frac{M}{N}\right) + \sum_{r \ne s} u_{(r)}u_{(s)}^* \\ &< 1 - \frac{\rho M}{N}, \end{aligned}$$

using 9 in the last step. The assumption $N < \rho M$ makes the right hand side negative, a contradiction. This proves (i). Part (ii) is a straightforward consequence of (i).

For the rest of the proof, $A$ denotes a non-simple $OA(k^2 + k + 2, k, 2, 4)$ with $k \ge 5$. By reordering the rows of $A$, and adding a fixed row to all rows modulo 2, we may assume that the first two rows of $A$ are all 0s. We use the notation $H_i, i = 0, 1, 2, H$ and $Q$ from above. Recall that $H$ has $N$ rows and $N/2$ columns. As $\zeta = -1$, the entries of $H$ are $\pm 1$. The key observation is the following:

(*) In rows 3, ..., $N$, the number of 1s is either $\ell_1$ or $\ell_2$, where

$$\ell_{1,2} = \frac{k+1 \pm \sqrt{k-1}}{2}.$$

Let us prove this. As the first two rows of $A$ are all-zeros, the first two rows of $Q$ have the form $[u u']$ and $[u u'']$, where

$$u = \left[ \frac{1}{\sqrt{N}} \cdots \frac{1}{\sqrt{N}} \right].$$

Using the fact that $N = 2M(k, 2, 4)$, we show $u'' = -u'$ in the same way as above. Let $[v v']$ be row $i$ of $Q$ with $i \ge 3$. This is orthogonal to the first two rows, hence,

$$\begin{aligned} 0 &= uv^T + u'(v')^T, \\ 0 &= uv^T + u''(v')^T = uv^T - u'(v')^T. \end{aligned}$$

This implies $uv^T = 0$. This means that among the entries of $v$, $\frac{1}{\sqrt{N}}$ and $-\frac{1}{\sqrt{N}}$ occur equally often. In terms of $H$, this means that in this row, 1 occurs $N/4$ times.

Let $\ell$ denote the number of 1s in row $i$ of $A$. $H_0$ has one column, which consists of all 1s. In row $i$ of $H_1$, the number of 1s is $k - \ell$. In row $i$ of $H_2$, the number of 1s is

$$\binom{\ell}{2} + \binom{k-\ell}{2}.$$
Hence, for the number of 1s in row $i$ of $H$, we have

$$1 + k - \ell + \binom{\ell}{2} + \binom{k-\ell}{2} = \frac{k^2 + k + 2}{4}.$$

Hence, we have $\ell^2 - (k+1)\ell + (k^2+k+2)/4 = 0$, which implies (*).

Immediate consequences are that $\kappa = \sqrt{k-1}$ is an integer, $N = k^2+k+2$ can be written as $N = \kappa^4 + 3\kappa^2 + 4$, and $\ell_{1,2} = (\kappa^2 \pm \kappa + 2)/2$.

Let us construct the array $A'$ by selecting all rows of $A$ that start with three zeros. We get

$$A' = \begin{bmatrix} 0 & 0 & 0 & 0 & \cdots & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 \\ 0 & 0 & 0 & 0 & \cdots & B \\ 0 & 0 & 0 & 0 & \cdots & 0 \end{bmatrix}$$

where $B$ is a subarray with $N/8 - 2$ rows and $k-3$ columns. Since $A$ has strength 4, then according to Lemma 6, columns 4 to $k$ of $A'$ have a number of 1s equal to their number of 0s, that equals then $N/16$. Let $a$ denote the number of rows of weight $\ell_1$ in $B$. The total number of 1s in $B$ is

$$a\ell_1 + (N/8 - 2 - a)\ell_2 = N/16 \cdot (k-3). \quad (10)$$

We reorder to get:

$$a(\ell_1 - \ell_2) = N(k-3)/16 - (N-16)\ell_2/8. \quad (11)$$

Now, $\ell_1 - \ell_2 = \kappa = \sqrt{k-1}$. Also, the right hand side can be expanded into a polynomial of $\kappa$. This yields:

$$\begin{aligned} 16a\kappa &= (\kappa^4 + 3\kappa^2 + 4)(\kappa^2 - 2) - (\kappa^4 + 3\kappa^2 - 12)(\kappa^2 - \kappa + 2) \\ &= \kappa^5 - 4\kappa^4 + 3\kappa^3 + 4\kappa^2 - 12\kappa + 16. \end{aligned}$$

We obtain that $16 \equiv 0 \pmod{\kappa}$, that is $\kappa$ divides 16, and since by assumption, we have $k \ge 5$, that is, $\kappa \ge 2$, then we have $\kappa \in \{2, 4, 8, 16\}$. If $\kappa \in \{4, 8, 16\}$, then $-12\kappa + 16 \equiv 0 \pmod{64}$, that is, $3\kappa \equiv 4 \pmod{16}$. This implies $\kappa \equiv 12 \pmod{16}$ (since the inverse of 3 modulo 16 equals 11), a contradiction.

Let us then consider the case $\kappa = 2$. Then $k = 5$, $N = 32$, $\ell_1 = 4$ and $\ell_2 = 2$. Since $A$ has 30 non-zero rows, and $\binom{5}{2} + \binom{5}{4} = 15$, each nonzero row has multiplicity 2. In other words, $A$ is twice an $OA(16, 5, 2, 4)$. This finishes the proof of (iii). $\square$

## 4 Simple arrays of strength 2 and 4

In the special case of orthogonal arrays of strength 2, we solve Problem 2, and this allows us to give an affirmative answer to Problem 1.

**Proposition 8** For $k \ge 2$, we have $F^*(k, 2, 2) = F(k, 2, 2)$. In particular, the sequence $F^*(k, 2, 2)$ is non-decreasing.

*Proof* For any positive integer $h$, a classical Hadamard matrix $H_{2h}$ is the matrix of the Hadamard Fourier transform, equal to the Kronecker product $H_2 \otimes \cdots \otimes H_2$ of the matrix:

$$H_2 = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$$
with itself. This implies

$$F(2^h - 1, 2, 2) = 2^h. \tag{12}$$

Given a positive integer $k$, let $h$ be the positive integer such that $2^{h-1} \le k \le 2^h - 1$, then 3 and 12 imply:

$$F(k, 2, 2) \le F(2^h - 1, 2, 2) = 2^h \le 2k.$$

As $M(k, 2, 2) = k + 1$, we can apply Corollary 2 to obtain $F(k, 2, 2) = F^*(k, 2, 2)$. □

The solution of Problem 2 has an implication to a recent conjecture by the first author and Chen. In [5, Conjecture 2.8], the authors asked if

$$F^*(k, 2, 3) = 8 \left\lfloor \frac{k}{4} \right\rfloor. \tag{CC}$$

Wang proved in [18, Theorem 3.7] that CC and the Hadamard conjecture are equivalent. However, Wang's proof is incomplete, since no explanation is given for $w_{4\lambda+\varepsilon,3} \le w_{4\lambda+4,3}$, where $1 \le \varepsilon \le 3$ (and $w_{n,t} = F^*(n, 2, t)$). In fact, this follows from Proposition 8. In order to be self-contained, we present a complete proof of the two conjectures.

**Proposition 9** The Hadamard conjecture is equivalent with Conjecture CC.

*Proof* Recall that [11, Theorem 7.5] states that orthogonal arrays OA(4λ, 4λ−1, 2, 2) and/or OA(8λ, 4λ, 2, 3) exist (and then $F(4\lambda - 1, 2, 2) \le 4\lambda$) if and only if there exists a Hadamard matrix of order 4λ. According to Rao's Bound, we have $F(4\lambda - 1, 2, 2) \ge 4\lambda$. The Hadamard conjecture is then equivalent with:

$$F(4\lambda - 1, 2, 2) = 4\lambda \tag{Ha}$$

for all positive integer $\lambda$. By 5 and Proposition 8, CC is equivalent with

$$F(k - 1, 2, 2) = 4 \left\lfloor \frac{k}{4} \right\rfloor. \tag{CC'}$$

If $k = 4\lambda$, then Ha and CC' are clearly equivalent. It remains to show that Ha implies CC' for any integer $k = 4\lambda + \varepsilon$ with $1 \le \varepsilon \le 3$. Rao's Bound gives

$$4\lambda < k \le F(k - 1, 2, 2),$$

which implies

$$4\lambda + 4 \le F(k - 1, 2, 2) \le F(4\lambda + 3, 2, 2), \tag{13}$$

since 4 divides $F(k - 1, 2, 2)$, and $F(k, s, t)$ is non-decreasing in $k$. By Ha and 13,

$$F(k - 1, 2, 2) = 4\lambda + 4 = 4 \left\lfloor \frac{k}{4} \right\rfloor,$$

and the Carlet-Chen conjecture follows. □

We finish this section by a partial answer to Problem 2 for orthogonal arrays of strength 4.

**Proposition 10** Let $k, m$ be integers, $m \ge 4$ even, with

$$2^{m-1/2} \le k \le 2^m - 1.$$

Then $F^*(k, 2, 4) = F(k, 2, 4)$.
**Proof** For any even integer $m \ge 4$, Kerdock [12] constructed a binary, non-linear code of length $2^m$, cardinality $4^m$, minimum distance $2^{m-1} - 2^{(m-2)/2}$ and dual distance 6. This code can be interpreted as a simple OA$(4^m, 2^m, 2, 5)$, since we know that an unrestricted code has dual distance $d^\perp$ if and only if its indicator is a correlation immune function of order $d^\perp - 1$ (and not of order $d^\perp$), that is, if and only if the array obtained by writing all codewords as rows is a simple OA of strength $d^\perp - 1$. In the usual way, we take the rows that start with a 0, and delete the starting 0 to obtain a simple OA$(2^{2m-1}, 2^m - 1, 2, 4)$. This shows

$$F(2^m - 1, 2, 4) \le F^*(2^m - 1, 2, 4) \le 2^{2m-1} \quad \text{form} \ge 4\text{even.}$$

Assume $2^{m-1/2} \le k \le 2^m - 1$. Then

$$ 
\begin{aligned}
F(k, 2, 4) &\le F(2^m - 1, 2, 4) \\
&\le 2^{2m-1} \\
&< 2^{2m-1} + 2^{m-1/2} + 2 \\
&\le k^2 + k + 2 = 2M(k, 2, 4).
\end{aligned}
$$

Corollary 2 implies $F^*(k, 2, 4) = F(k, 2, 4)$. $\square$

<figure><img src="image_3.png" /></figure>

We can interpret the above result in such a way that the set of integers $k$ confirming the Carlet-Guilley problem has a positive density. For any integer $t$, we define the set $\mathcal{G}(t)$ of integers $k$ such that $F^*(k, 2, t) = F(k, 2, t)$. Let $4 \le \mu$ be an even integer. For $4 \le m \le \mu$ even, the set $\mathcal{G}(4)_{<2^\mu}$ contains disjoint intervals of length

$$2^m - 1 - 2^{m-1/2} = 2^m \left(1 - \frac{1}{\sqrt{2}}\right) - 1.$$

Summing this up, we obtain

$$ 
\begin{aligned}
|\mathcal{G}(4)_{<2^\mu}| &\ge \sum_m \ge 4\text{even}^\mu 2^m \left(1 - \frac{1}{\sqrt{2}}\right) - 1 \\
&= \sum_{\ell=0}^{\mu/2-2} 2^{2\ell+4} \left(1 - \frac{1}{\sqrt{2}}\right) - 1 \\
&= \frac{\mu}{2} - 1 + 2^4 \left(1 - \frac{1}{\sqrt{2}}\right) \frac{4^{\mu/2-1} - 1}{3}.
\end{aligned}
$$

Hence,

$$\lim_{\mu \to \infty} \frac{|\mathcal{G}(4)_{<2^\mu}|}{2^\mu} \ge \frac{4 - 2\sqrt{2}}{3} \approx 0.39.$$

**Remark 11** It is not known (but not excluded either) if the Kerdock code is optimal as an unrestricted code of dual distance 6, that is, if $F^*(2^m, 2, 5) = 4^m$ and $F^*(2^m - 1, 2, 4) = 2^{2m-1}$, for $m \ge 4$ even. It is more or less conjectured, but not yet proved explicitly, that the Preparata code of length $2^m$, with $m \ge 4$ even, is optimal as a code with size $2^{2m-2m}$ and dual distance $2^{m-1} - 2^{m/2-1}$, that is, $F^*(2^m, 2, 2^{m-1} - 2^{m/2-1} - 1) = 2^{2m-2m}$.
5 Applications and further constructions

**Proposition 12** *The missing entries of Table 1 are the following:*

$$
\begin{align*}
F^*(k, 2, 4) &= 128 \quad \text{for } 11 \le k \le 15, \\
F^*(k, 2, 5) &= 256 \quad \text{for } 11 \le k \le 16,
\end{align*}
\tag{A}
$$

$$
\begin{align*}
F^*(12, 2, 6) &= 768, \\
F^*(13, 2, 7) &= 1536,
\end{align*}
\tag{B}
$$

$$
F^*(13, 2, 6) = 1024. \tag{C}
$$

For all these parameters $k, t$, we have $F^*(k, 2, t) = F(k, 2, t)$.

*Proof* (A) For $u = 4$ and $k \le 15$, shortening the Kerdock code gives

$$
F(k, 2, 4) \le 128, \quad \text{and} \quad F(k + 1, 2, 5) \le 256.
$$

If $11 \le k \le 15$, then Corollary 2 implies

$$
F^*(k, 2, 4) = F(k, 2, 4). \tag{14}
$$

Assume $F(10, 2, 4) < 128$ and let $A$ denote an $\mathcal{O}A(n, 10, 2, 4)$ with $n < 128$. Then $n \le 112$ and $A$ is simple by Theorem 1. Hence, $F^*(10, 2, 4) \le 112$, which contradicts to the entry

$$
F^*(10, 2, 4) = 128. \tag{15}
$$

of Table 1. Hence, 14 holds for $k = 10$, as well. As $F(k, s, t)$ is non-decreasing in $k$, we
obtain (A).

(B) For $k = 12, t = 6$, Delsarte's LP Bound has value 768. We modified the ILP method of Bulutoglu and Margot [3] to construct an array $B = OA(768, 12, 2, 6)$ that has an automorphism

$$
(1, 2, 3, 4, 5)(6, 7, 8, 9, 10)
$$

of order 5. This gives rise to an array $B' = OA(1536, 13, 2, 7)$ with weight polynomial

$$
(x+1)^5 \cdot (x^8 - 5x^7 + 28x^6 - 35x^5 + 70x^4 - 35x^3 + 28x^2 - 5x + 1).
$$

As shown in [15], $B'$ is unique and it can be constructed from an equitable partition of the
13-cube.

(C) For $k = 13, t = 6$, Delsarte's LP Bound has value 1024. The generator matrix

$$
G = \begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\
1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\
1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1
\end{bmatrix}
$$

defines a binary linear [13, 3, 7]-code *C*. The dual of *C* is a linear *OA*(1*024*, 13, 2, 6). Notice
that this construction is given in a more general context in [18]. □

**Remark 13** (1) $F(10, 2, 4) \ge 128$ can be deduced from [3, Table 1], from [17, Table III], from [18, Appendix A], or from [2, Theorems 18 and 20].

(2) The values in (A) are given in [14], with a more computer-based proof.
15. Krotov D.S.: On the OA(1536; 13; 2; 7) and related orthogonal arrays. Discret. Math. 343, 111659 (2020). https://doi.org/10.1016/j.disc.2019.111659.

16. Rao C.R.: Factorial experiments derivable from combinatorial arrangements of arrays. Suppl. J. R. Stat. Soc. 9(1), 128–139 (1947).

17. Schoen E.D., Eendebak P.T., Nguyen M.V.M.: Complete enumeration of pure-level and mixed-level orthogonal arrays. J. Combin. Des. 18(2), 123–140 (2010). https://doi.org/10.1002/jcd.20236.

18. Wang Q.: Hadamard matrices, d-linearly independent sets and correlation-immune Boolean functions with minimum Hamming weights. Des. Codes Cryptogr. 87(10), 2321–2333 (2019). https://doi.org/10.1007/s10623-019-00620-1.

19. Xiao G.-Z., Massey J.: A spectral characterization of correlation-immune combining functions. IEEE Trans. Inf. Theory 34(3), 569–571 (1988). https://doi.org/10.1109/18.6037.

**Publisher's Note** Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.