Some general properties of modified bent functions through addition of indicator functions

Abstract

Properties of a secondary bent function construction that adds the indicator of an affine subspace of arbitrary dimension to a given bent function in n variables are obtained. Some results regarding normal and weakly normal bent functions are generalized. An upper bound for the number of generated bent functions is proven. This bound is attained if and only if the given bent function is quadratic. In certain cases, the addition of the indicator of an m-dimensional subspace, for different m, will not generate bent functions. Such examples are presented for any even n ≥ 10. It is proven that there exists an infinite family of Maiorana–McFarland bent functions such that the numbers of generated bent functions differ for the bent function and its dual function.

1 Introduction

A bent function is a Boolean function in even number of variables that is at the maximal possible Hamming distance from the set of all affine Boolean functions. In other words, it has the best nonlinearity. Bent functions were introduced by O. Rothaus [26]. Since 1960, they have been actively researched. As extreme objects, they have many applications in various fields: algebra, coding theory, combinatorics, communication theory, cryptography. Boolean functions with high nonlinearity are especially interesting for symmetric cryptography, since they help to resist linear cryptanalysis [23]. Useful information regarding bent functions can be found in reviews, dissertations and monographs [6, 7, 9,10,11, 14, 21, 25, 28].

This work is dedicated to the following secondary construction of bent functions. Let f be a given bent function in n variables and L be an affine subspace of ${\mathbb {F}_{2}^{n}}$. We consider all bent functions of the form f ⊕Ind_L, where Ind_L is the indicator function of L. For the first time it was mentioned by J. Dillon [11] for n/2-dimensional subspaces. Later, C. Carlet [4] proved a criterion of “bentness” of f ⊕Ind_L, where L is of arbitrary dimension. The most popular and well studied case is $\dim L = n/2$. In this case, the criterion transforms to the affinity of f on L. Also, the construction generates exactly all bent functions at the Hamming distance 2^n/2 from the given one, which is the minimal possible distance between two distinct bent functions (see [17]). This connects the construction properties with the metric properties of the set of all bent functions (see, for instance, [16]). Note that this case was studied in terms of (weakly) normal bent functions, which means that a function is constant (resp. affine) on some n/2-dimensional affine subspace (see [3, 8, 13, 20]). It should be emphasized that the affinity on an affine subspace is an interesting property for cryptography by itself. Subspaces of large dimension deserve attention too. For instance, A. Canteaut and P. Charpin considered the case of (n − 2)-dimensional subspaces in the function decomposition context [2]. Note that it is rather difficult to find a suitable affine subspace L such that f ⊕Ind_L is a bent function. Also, it is hard to determine which of bent function subclasses contain f ⊕Ind_L and which do not. Nevertheless, some results related to these problems have been obtained [3, 4, 22, 27].

In this work, we investigate the properties of the construction f ⊕Ind_L, where L is an affine subspace of arbitrary dimension m. On the one hand, they are similar to the case of m = n/2. The construction properties are closely connected with the affinity of the dual function on affine subspaces. Some known results for m = n/2 are generalized for the case of arbitrary dimensions, for instance, an upper bound for the number of constructed bent functions [16], the use of the simplest iterative construction f(x) ⊕ y₁y₂ of bent functions [3, 8]. In certain cases, the addition of the indicator of an m-dimensional subspace, for different m, will not generate bent functions. Such examples are presented for any even n ≥ 10. On the other hand, the numbers of generated bent functions may differ for some bent function f and its dual function $\widetilde {f}$, which is opposite to the case of m = n/2. Examples of such bent functions for any even n ≥ 8 and m = n − 2 are provided. Interestingly, these examples are Maiorana–McFarland bent functions [24].

The article is organized as follows. Section 2 contains basic definitions. In Section 3, the notion of a balanced representation of a bent function f by a linear subspace L is introduced. It means that f is either constant or balanced on each coset of L. This notion is directly connected with the criterion proven in [4]. Also, properties of such representations (Theorem 2) are considered. Note that bent functions [5, 24, 29] obtained by the concatenation of affine functions always have a balanced representation by some nontrivial linear subspace. In Section 4, we assume that f ⊕Ind_L is a bent function for some given bent function f and an affine subspace L and consider how to find affine subspaces $L^{\prime }$ and $L^{\prime \prime }$, where $L^{\prime } \subset L \subset L^{\prime \prime }$, such that $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L^{\prime }}$ and $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L^{\prime \prime }}$ are bent functions. Note that the conditions related to the existence of $L^{\prime }$ and $L^{\prime \prime }$ are, in general, not trivial. There is one simple case: we can always find an n/2-dimensional $L^{\prime }$ by an (n/2 + 1)-dimensional L. The case of $\dim L = n/2 + 1$ similarly to the case of $\dim L = n/2$ guarantees that the construction is symmetric for the bent function f and its dual function $\widetilde {f}$: $\sup (\widetilde {f} \oplus (\widetilde {f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L}}))$ is an affine subspace too (Theorem 3). In other words, the dual functions of f and f ⊕Ind_L differ exactly on an affine subspace of dimension $\dim L$. Actually, the case of $\dim L = n/2 + 1$ is equivalent to applying the construction twice for some n/2-dimensional $L^{\prime } \subset L$ and its shift $L \setminus L^{\prime }$: $(f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L^{\prime }}) \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L \setminus L^{\prime }} = f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L}, \text { where } f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L^{\prime }} \text { is bent}.$ Hence, these two cases are practically similar. Let us denote by BS_m(f) the set of all bent functions of the form f ⊕Ind_L, where L is m-dimensional. In Section 5, an upper bound for # BS_m(f) is proven. This bound is attained for a nontrivial dimension if and only if the given bent function f is quadratic (Theorem 4). Also, it is shown how to choose a bent function f in n variables such that # BS_m(f) = 0, where m = n − 2,n − 1,…,k. In light of A. Gorodilova’s results [15], k ≤ n/2 + 4 for the dual function of a suitable Kasami [12, 19] bent function (Theorem 6). Thus, 0 is a tight lower bound for # BS_m(f). Section 6 focuses on the simplest iterative construction f_+ 2(x,y) = f(x) ⊕ y₁y₂ of bent functions. It is proven (Theorem 8) that “bentness” of f_+ 2 ⊕Ind_L for an m-dimensional affine subspace L implies “bentness” of $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L^{\prime }}$ for some affine subspace $L^{\prime }$ of dimension m − 1 or m − 2. This fact generalizes the properties of normal bent functions [3]. It allows us to construct a bent function f such that # BS_m(f) = 0, where m = n/2,n/2 + 1,n/2 + 2,n/2 + 3 (the number of dimensions depends on the initial function; such example is based on the bent function found in [20]). Note that these dimensions complement the ones from Theorem 6. In addition, # BS_n(f_+ 2) is calculated by constant derivatives (Theorem 9) and it is shown that it is impossible to find # BS_n(f_+ 2) by # BS_n− 2(f). The counterexample is found in the Maiorana–McFarland class. Section 7 demonstrates an infinite family of Maiorana–McFarland bent functions f_n in n variables such that $\#{\mathrm {B}\mathrm {S}_{n - 2}(f_{n})} \neq \#{\mathrm {B}\mathrm {S}_{n - 2}(\widetilde {f_{n}})}$, i. e. f and its dual $\widetilde {f}$ structurally differ. This can make it more difficult to determine the class containing $\widetilde {f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L}}$ even if f is a Maiorana–McFarland bent function.

2 Preliminaries

Let us denote the finite field with two elements by ${\mathbb {F}_2^{}}$. A Boolean function in n variables is a mapping from ${\mathbb {F}_{2}^{n}}$ to ${\mathbb {F}_2^{}}$. Let 〈x,y〉 = x₁y₁ ⊕… ⊕ x_ny_n, where $x, y \in \mathbb {F}_{2}^{n}$. Let us denote the characteristic Boolean function of a set $S \subseteq \mathbb {F}_{2}^{n}$ by Ind_S and the derivative of f in the direction α by D_αf, D_αf(x) = f(x) ⊕ f(x ⊕ α). Let $D_{L} f(x) = \bigoplus _{a \in L} f(x \oplus a)$, i. e. the derivative $D_{L} f = D_{a_{1}}D_{a_{2}}{\ldots } D_{a_{k}} f$, where a₁,…,a_k is a basis of L and L is a k-dimensional linear subspace of ${\mathbb {F}_{2}^{n}}$. We denote the cardinality of the set S by #S, the set {x ⊕ s | s ∈ S} by x ⊕ S and the set $\{ x \in {\mathbb {F}_{2}^{n}} \ | \ f(x) = 1\}$ by $\sup (f)$. The Hamming distance between two Boolean functions in n variables is the number of arguments on which these functions differ. A function f is balanced on a set S if $\# (\sup (f) \cap S) = \frac {1}{2}\# S$.

The degree of f ($\deg f$) is the degree of its algebraic normal form that is a representation of f as a polynomial over ${\mathbb {F}_2^{}}$:

$$ f(x_{1}, \ldots, x_{n}) = \underset{a \in {\mathbb{F}_{2}^{n}}}{\bigoplus} c_{a} x_{1}^{a_{1}}{\ldots} x_{n}^{a_{n}}, \ c_{a} \in {\mathbb{F}_2^{}}, \text{ where } $$

$x_{i}^{a_{i}} \equiv x_{i} \text { for } a_{i} = 1 \text { and } x_{i}^{a_{i}} \equiv 1 \text { for } a_{i} = 0$. A function is called affine if its degree is at most 1 and quadratic if its degree equals to 2. A function f is affine on an affine subspace L if f(x) ⊕〈a,x〉 is constant on L for some $a \in {\mathbb {F}_{2}^{n}}$.

The Walsh–Hadamard transform of f is the mapping $W_{f} :{\mathbb {F}_{2}^{n}} \to \mathbb {Z}$ such that

$$ W_{f}(y) = \underset{x \in {\mathbb{F}_{2}^{n}}}{\sum}(-1)^{f(x) \oplus {\langle y, x \rangle}}. $$

The numbers W_f(y) are called the Walsh–Hadamard coefficients. A Boolean function f in n variables, n is even, is a bent function if |W_f(y)| = 2^n/2 for all $y \in {\mathbb {F}_{2}^{n}}$. We denote by ${{\mathscr{B}}_{n}}$ the set of all bent functions in n variables. The dual function $\widetilde {f}$ is defined in the following way:

$$ (-1)^{\widetilde{f}(y)} = 2^{-n/2} W_{f}(y), y \in {\mathbb{F}_{2}^{n}}. $$

The function $\widetilde {f}$ is a bent function too, and $\widetilde {\widetilde {f}} = f$ (see, for instance, [26]).

Two Boolean functions f,g in n variables are called extended affinely equivalent (EA-equivalent) if there exist an invertible n-by-n binary matrix A, a vector $b \in {\mathbb {F}_{2}^{n}}$ and an affine function ℓ in n variables such that

$$ f(x)=g(x A \oplus b) \oplus \ell(x) \text{ for all } x \in {\mathbb{F}_{2}^{n}}. $$

Hereinafter, we suppose that n is even. In this work, we consider properties of a bent function construction f ⊕Ind_U, where f is a given bent function in n variables and U is an affine subspace of arbitrary dimension. For $f \in {{\mathscr{B}}_{n}}$ and 0 ≤ m ≤ n, we define

$$ {\mathrm{B}\mathrm{S}_{m}(f)} = \{ f \oplus \mathrm{I}\mathrm{n}\mathrm{d}_{U} \ | \ U \text{ is an } m\text{-dimensional affine subspace of } {\mathbb{F}_{2}^{n}} \} \cap {\mathcal{B}_{n}}. $$

Note that for $f, g \in {{\mathscr{B}}_{n}}$ that are EA-equivalent # BS_m(f) = # BS_m(g) holds.

Necessary and sufficient conditions for f ⊕Ind_U to be a bent function were proven by C. Carlet [4].

Theorem 1 (C. Carlet, 1994)

Let $f \in {\mathscr{B}}_{n}$, $L \subseteq {\mathbb {F}_{2}^{n}}$ be a linear subspace and $a \in {\mathbb {F}_{2}^{n}}$. Then f ⊕Ind_a⊕L is a bent function if and only if any of the following equivalent conditions hold:

• 1. D_αf is balanced on a ⊕ L for all $\alpha \in {\mathbb {F}_{2}^{n}} \setminus L$;

• 2. $\widetilde {f}(x) \oplus {\langle a, x \rangle }$ is either constant or balanced on each coset of L^⊥.

In the next section, additional details for the second condition of the criterion will be provided. They will be often used in the proofs.

Note that trivial subspace dimensions for $f \in {{\mathscr{B}}_{n}}$ are n − 1 and n. In these cases we just add an affine function to the bent function, i. e. the result is always a bent function too. It is also well known that f ⊕Ind_L is not a bent function if $\dim L < n/2$ (see [4]). Thus, we will focus on dimensions n/2,n/2 + 1,…,n − 2.

3 A balanced representation

Let us introduce the following notion.

Definition 1

A Boolean function f in n variables has a balanced representation by a linear subspace $L \subseteq {\mathbb {F}_{2}^{n}}$ if f is either constant or balanced on each coset of L.

Note that any function has a balanced representation by the 0-dimensional linear subspace. The same situation holds for a 1-dimensional linear subspace.

First of all, there are some additional details regarding balanced representations of bent functions. These statements mostly follow from Theorem 1 and [16].

Theorem 2

Let $f \in {{\mathscr{B}}_{n}}$ and L be a linear subspace of ${\mathbb {F}_{2}^{n}}$, $\dim L \leq n/2$. Then the following holds.

• 1. Let f be constant on each of a₁ ⊕ L,…,a_m ⊕ L, where $a_{1}, \ldots , a_{m} \in {\mathbb {F}_{2}^{n}}$, $m \in \mathbb {N}$, and be balanced on each other a ⊕ L, where $a \in {\mathbb {F}_{2}^{n}} \setminus U$, U = (a₁ ⊕ L) ∪… ∪ (a_m ⊕ L). Then $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U} \in {\mathscr{B}}_{n}$ and $\widetilde {f} \oplus \widetilde {f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U}} = \mathrm {I}\mathrm {n}\mathrm {d}_{L^{\bot }}$.

• 2. f has a balanced representation by L if and only if f is constant on each of $2^{n - 2 \dim L}$ distinct cosets of L.

• 3. f cannot be constant on more than $2^{n - 2 \dim L}$ distinct cosets of L.

Proof

Starting with the first point, let us consider W_f(x) and $W_{f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U}}(x)$:

$$ \begin{array}{@{}rcl@{}} W_{f \oplus \mathrm{I}\mathrm{n}\mathrm{d}_{U}}(x) = \underset{y \notin U}{\sum}{(-1)^{f(y) \oplus {\langle x, y \rangle}}} + \underset{y \in U}{\sum}{(-1)^{f(y) \oplus {\langle x, y \rangle} \oplus 1}} = \\ W_{f}(x) - 2 \underset{y \in U}{\sum}(-1)^{f(y) \oplus {\langle x, y \rangle}} = W_{f}(x) - 2 \sum\limits_{i = 1}^{m}\underset{y \in a_{i} \oplus L}{\sum}{(-1)^{f(a_{i}) \oplus {\langle x, y \rangle}}}. \end{array} $$

Since the function y↦〈x,y〉 (here x is a fixed parameter) is balanced on any a_i ⊕ L if x∉L^⊥, it holds that $W_{f}(x) = W_{f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U}}(x)$ for x∉L^⊥.

Next, let x ∈ L^⊥. In this case, we use the following:

$$ W_{f \oplus \mathrm{I}\mathrm{n}\mathrm{d}_{U}}(x) = W_{f}(x) - 2 \underset{y \in U}{\sum}(-1)^{f(y) \oplus {\langle x, y \rangle}}. $$

It can be seen that ${\sum }_{y \in U}(-1)^{f(y) \oplus {\langle x, y \rangle }} = W_{f}(x)$. Indeed, 〈x,z〉≡const on z ∈ y ⊕ L, y∉U, and, therefore, f(z) ⊕〈x,z〉 is balanced on y ⊕ L. Thus, ${\sum }_{y \notin U}(-1)^{f(y) \oplus {\langle x, y \rangle }} = 0$ and $W_{f}(x) = {\sum }_{y \in U}(-1)^{f(y) \oplus {\langle x, y \rangle }}$, i. e. $W_{f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U}}(x) = -W_{f}(x)$. At the same time, W_f(x) = ± 2^n/2. Consequently, f ⊕Ind_U is a bent function. Also, $W_{f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U}}(x) = W_{f}(x)$ if and only if x∉L^⊥. The first point is proven.

We can see that the first point implies that $m = 2^{n - 2\dim L}$, since $\# L^{\bot } = 2^{n - \dim L}$ and it is well known that the duality mapping preserves the Hamming distance between bent functions (see, for instance, [4]). Some results related to this mapping can be found in [18]. This proves the first half of the second point. To complete the second point and to prove the third point, we refer to [16, Lemma 8]. □

Corollary 1

Let $f, f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{a \oplus L} \in {{\mathscr{B}}_{n}}$, where L is a linear subspace of ${\mathbb {F}_{2}^{n}}$ and $a \in {\mathbb {F}_{2}^{n}}$. Then $\sup (\widetilde {f} \oplus (\widetilde {f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L}})) = (a_{1} \oplus L^{\bot }) \cup {\ldots } \cup (a_{2^{n - 2 \dim L^{\bot }}} \oplus L^{\bot }),$ where f(x) ⊕〈a,x〉 is constant on each of a_i ⊕ L^⊥ (each two of them are distinct). Note that this does not guarantee that $\sup (\widetilde {f} \oplus (\widetilde {f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L}}))$ is an affine subspace.

The case of $\dim L = n / 2$ is especially interesting for bent functions. A large class of normal bent functions for this representation was introduced by H. Dobbertin [13]. Also, any bent function represented by the concatenation of affine functions in k variables [5, 24, 29] has a balanced representation by some k-dimensional linear subspace.

Note that the algorithm described in [3] can find all balanced representations of bent functions f(x) ⊕〈a,x〉 for all $a \in {\mathbb {F}_{2}^{n}}$, i. e. all elements of ${\mathrm {B}\mathrm {S}_{m}(\widetilde {f})}$. Such algorithms have many applications (see, for instance, [1]).

4 Subspaces and superspaces of U where $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U} \in {{\mathscr{B}}_{n}}$

In this section, we consider a possibility to increase and decrease the dimension of a subspace by 1 which is suitable for the construction. Let us start with balanced representations.

Proposition 1

Suppose that $f \in {{\mathscr{B}}_{n}}$ has a balanced representation by a linear subspace $L \subseteq {\mathbb {F}_{2}^{n}}$. Then

• 1. f has a balanced representation by L ∪ (a ⊕ L), where $a \in {\mathbb {F}_{2}^{n}} \setminus L$, if and only if a ⊕ U = U, where U is the union of all cosets of L such that f is constant on each of them.

• 2. f has a balanced representation by L_w = {x ∈ L | 〈w,x〉 = 0}, where $w \in \mathbb {F}_{2}^{n} L^{\bot }$, if and only if f(x) ⊕〈w,x〉 has a balanced representation by L.

Proof

To prove the first point, it is enough to note that f is either constant or balanced on L ∪ (a ⊕ L) if and only if there are no cases when f is constant on x ⊕ L and balanced on a ⊕ x ⊕ L. It is equivalent to a ⊕ U = U.

Let us consider the second point. Since w∉L^⊥, L = L_w ∪ (s ⊕ L_w) for some s ∈ L such that 〈w,s〉 = 1. First of all, let b ∈ U. Then f is constant on b ⊕ L_w and b ⊕ s ⊕ L_w, i. e. U consists of $2 \cdot 2^{n - 2\dim L}$ cosets of L_w. At the same time, f(x) ⊕〈w,x〉 is not constant on b ⊕ L since 〈w,b〉≠〈w,b ⊕ s〉.

Let b∉U. Therefore, f is balanced on b ⊕ L. As a consequence, f is constant on b ⊕ L_w if and only if f is constant on b ⊕ s ⊕ L_w = (b ⊕ L) ∖ (b ⊕ L_w). Note that f(x) ⊕〈w,x〉 = f(x) ⊕〈w,b〉 for x ∈ b ⊕ L_w and f(x) ⊕〈w,x〉 = f(x) ⊕〈w,b〉⊕ 1 for x ∈ b ⊕ s ⊕ L_w. It implies that f(x) ⊕〈w,x〉 is constant on b ⊕ L if and only if f is constant on b ⊕ L_w and b ⊕ s ⊕ L_w.

Hence, f is constant on $2^{n - 2\dim L_{w}} = 2 \cdot 2^{n - 2\dim L} + 2 \cdot 2^{n - 2\dim L}$ distinct cosets of L_w if and only if f(x) ⊕〈w,x〉 is constant on $2^{n - 2\dim L}$ distinct cosets of L. Theorem 2 completes the proof. □

The following property follows from the previous proposition. Theorem 1 and bent function distance properties can also provide it.

Proposition 2

Let $f \in {{\mathscr{B}}_{n}}$ and $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L} \in {{\mathscr{B}}_{n}}$, where L is an affine subspace of ${\mathbb {F}_{2}^{n}}$. Let $a \in \mathbb {F}_{2}^{n}$. Then $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L \cup (a \oplus L)} \in {{\mathscr{B}}_{n}}$ if and only if $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{a \oplus L} \in {{\mathscr{B}}_{n}}$.

Proof

Without loss of generality, we assume that L is a linear subspace. Otherwise, we can consider f(x ⊕ b) instead of f, where b ∈ L. If a ∈ L, the statement is obvious. Let a∉L. First of all, Theorem 1 provides that $\widetilde {f}$ has a balanced representation by L^⊥. Next, (L ∪ (a ⊕ L))^⊥ = {x ∈ L^⊥ | 〈a,x〉 = 0} = (L^⊥)_a, where (L^⊥)_a is defined in the second point of Proposition 1. According to this point, $\widetilde {f}$ has a balanced representation by (L^⊥)_a if and only if $\widetilde {f}(x) \oplus {\langle a, x \rangle }$ has a balanced representation by L^⊥. Theorem 1 completes the proof. □

Let us rewrite the first point of Proposition 1 in terms of the construction.

Proposition 3

Let $f \in {{\mathscr{B}}_{n}}$ and $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L} \in {{\mathscr{B}}_{n}}$, where L is an affine subspace of ${\mathbb {F}_{2}^{n}}$. Let $a \in {\mathbb {F}_{2}^{n}}$ and L_a = {x ∈ L | 〈a,x〉 = 0}. Then $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L_{a}} \in {{\mathscr{B}}_{n}}$ if and only if $D_{a} \widetilde {f} \equiv D_{a} (\widetilde {f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L}})$.

Proof

It is easy to see that $D_{a} \widetilde {f} \equiv D_{a} (\widetilde {f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L}})$ is equivalent to a ⊕ U = U, where $U = \sup (\widetilde {f} \oplus (\widetilde {f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L}}))$. Without loss of generality, we can assume that L is a linear subspace, similarly to Proposition 2. Let $L^{\prime } = \{ x \in L \ | \ \langle a, x \rangle = 0\}$. If $L^{\prime } = L$, the statement is obvious: it means that a ∈ L^⊥ and we know that U is the union of cosets of L^⊥. In other cases, either $L_{a} = L^{\prime }$ or $L_{a} = L \setminus L^{\prime }$, where $\dim L^{\prime } = \dim L - 1$. According to Proposition 1, $\widetilde {f}$ has a balanced representation by $L^{\prime \bot } = L^{\bot } \cup (a \oplus L^{\bot })$ if and only if a ⊕ U = U. Thus, $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L^{\prime }} \in {{\mathscr{B}}_{n}}$ if and only if a ⊕ U = U. In light of Proposition 2, it does not matter whether $L_{a} = L^{\prime }$ or $L_{a} = L \setminus L^{\prime }$. □

Note that Propositions 1, 2 and 3 give nontrivial conditions to increase and decrease the dimension of a subspace. It looks like it is rather hard to construct a subspace or a superspace of the given one. In other words, nonempty BS_m(f), in general, does not guarantee that BS_m+ 1(f) and BS_m− 1(f) are nonempty too. It is confirmed by the computational experiments and by the results obtained in Sections 5.1 and 6.2 that are dedicated to bent functions with empty BS_m(f).

It is known [4] that the set $\sup (\widetilde {f} \oplus (\widetilde {f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U}}))$ is always an affine subspace for $f, f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U} \in {{\mathscr{B}}_{n}}$ and an n/2-dimensional U. Next, we prove that the same is true for an (n/2 + 1)-dimensional subspace.

Theorem 3

Let $f \in {{\mathscr{B}}_{n}}$ and $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U} \in {{\mathscr{B}}_{n}}$, where U is an affine subspace of ${\mathbb {F}_{2}^{n}}$ of dimension at most n/2 + 1. Then $\sup (\widetilde {f} \oplus (\widetilde {f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U}}))$ is an affine subspace too.

Proof

The case of $\dim U = n/2$ is obvious. Suppose that $\dim U = n/2 + 1$. By Theorem 1, let us move to a balanced representation by L^⊥ for $g(x) = \widetilde {f}(x) \oplus {\langle a, x \rangle }$, where a ⊕ L = U, L is a linear subspace. According to Corollary 1, we have $2^{n - 2 \dim L^{\bot }} = 2^{2} = 4$ “constant” cosets C₁,C₂,C₃,C₄ of L^⊥, i. e. $C_{1} \cup C_{2} \cup C_{3} \cup C_{4} = \sup (\widetilde {f} \oplus (\widetilde {f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U}}))$. Without loss of generality, we can suppose that $g|_{C_{1}} \equiv g|_{C_{2}}$. By Theorem 2, the function g has a balanced representation by the affine subspace C₁ ∪ C₂ of dimension n/2. But Proposition 1 provides that there exists a∉L^⊥ such that a ⊕ (C₁ ∪ C₂ ∪ C₃ ∪ C₄) = C₁ ∪ C₂ ∪ C₃ ∪ C₄. Since a∉L^⊥, it holds $a \oplus C_{i_{1}} = C_{i_{2}}$ and $a \oplus C_{i_{3}} = C_{i_{4}}$ for some {i₁,i₂,i₃,i₄} = {1,2,3,4}. It means that $a \oplus (C_{i_{1}} \cup C_{i_{3}}) = C_{i_{2}} \cup C_{i_{4}}$. Since $C_{i_{1}} \cup C_{i_{3}}$ is an affine subspace, $(C_{i_{1}} \cup C_{i_{3}}) \cup (C_{i_{2}} \cup C_{i_{4}}) = C_{1} \cup C_{2} \cup C_{3} \cup C_{4}$ is an affine subspace too. □

An important corollary of the theorem is the following proposition.

Proposition 4

Let $f \in {{\mathscr{B}}_{n}}$ and $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L} \in {{\mathscr{B}}_{n}}$, where L is an (n/2 + 1)-dimensional affine subspace of $\mathbb {F}_{2}^{n}$. Then there exists an n/2-dimensional affine subspace $L^{\prime } \subset L$ such that $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L^{\prime }} \in {{\mathscr{B}}_{n}}$.

Proof

Due to Theorem 3, let $U = \sup (\widetilde {f} \oplus (\widetilde {f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L}}))$ be a coset of a linear subspace $U^{\prime }$. Since $L^{\bot } \subset U^{\prime }$, Proposition 3 gives us that $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L_{a}} \in {{\mathscr{B}}_{n}}$, where $a \in U^{\prime }$ and a∉L^⊥. In this case $\dim L_{a} = n/2$. □

Proposition 4 claims that the case of (n/2 + 1)-dimensional L is equivalent to applying the construction twice for some n/2-dimensional $L^{\prime } \subset L$ (that always exists by the proposition) and its shift $L \setminus L^{\prime }$, i. e.

$$ (f \oplus \mathrm{I}\mathrm{n}\mathrm{d}_{L^{\prime}}) \oplus \mathrm{I}\mathrm{n}\mathrm{d}_{L \setminus L^{\prime}} = f \oplus \mathrm{I}\mathrm{n}\mathrm{d}_{L}, \text{ where } f \oplus \mathrm{I}\mathrm{n}\mathrm{d}_{L^{\prime}} \in {\mathcal{B}_{n}}. $$

5 Bounds for # BS_m(f)

The following theorem estimates # BS_m(f). It generalizes the upper bound from [16] that works for m = n/2.

Theorem 4

For $f \in {{\mathscr{B}}_{n}}$ and m ≥ n/2, it holds

$$ \#{\mathrm{B}\mathrm{S}_{m}(f)} \leq 2^{n - m}\prod\limits_{i = 1}^{n - m}\frac{2^{2m - n + 2i} - 1}{2^{i} - 1}. $$

Moreover, for m ≤ n − 2, the bound is attained if and only if f is quadratic.

Proof

To prove the bound, we refer to [16, Theorem 2]. In the first part of that theorem, the following was shown:

$$ \#D^{s}(g) \leq 2^{n} \prod\limits_{t = 0}^{s - 1}\frac{2^{n - 2t} - 1}{2 \cdot (2^{t + 1} - 1)} = \#D^{s}(h), $$

where $g, h \in {{\mathscr{B}}_{n}}$, h is quadratic, D^s(g) is the set of all s-dimensional affine subspaces such that g is affine on each of them.

Let U ∈ D^s(g), i. e. g(x) ⊕〈a,x〉 is constant on U for some $a \in {\mathbb {F}_{2}^{n}}$. Next, we define ${\text {nc}_{g}(U)} = \# \{ b \oplus U \ | \ g(x) \oplus {\langle a, x \rangle }\text { is constant on } b \oplus U, b \in {\mathbb {F}_{2}^{n}}\}$.

Theorem 1 gives us that $\#{\mathrm {B}\mathrm {S}_{n - s}(\widetilde {g})} = \#P^{s}(g)$, where

$$ \begin{array}{@{}rcl@{}}P^{s}(g) = \{ a \oplus L^{\bot} \ | \ a \in {\mathbb{F}_{2}^{n}}, L \text{ is a linear subspace of dimension } s\\ \text{ and the function } g(x) \oplus {\langle a, x \rangle} \text{ has a balanced representation by } L\}.\end{array} $$

Note that a ⊕ L^⊥ = b ⊕ L^⊥ if and only if 〈a,x〉⊕〈b,x〉 is constant on u ⊕ L, $a, b, u \in {\mathbb {F}_{2}^{n}}$. In other words, if g(x) ⊕〈a,x〉 is constant on u ⊕ L, then g(x) ⊕〈b,x〉 is constant on u ⊕ L if and only if a ⊕ L^⊥ = b ⊕ L^⊥. In light of Theorem 2, it implies that $\#P^{s}(g) = 2^{2s - n} \# \{ U \in D^{s}(g) \ | \ {\text {nc}_{g}(U)} = 2^{n - 2s}\}$. Therefore, $\#{\mathrm {B}\mathrm {S}_{n - s}(\widetilde {g})} = \#P^{s}(g) \leq 2^{2s - n} \#D^{s}(g)$. According to [16, Proposition 4], ${\text {nc}_{h}(U)} = 2^{n - 2 \dim U}$ for any U ∈ D^s(h), i. e. $\#{\mathrm {B}\mathrm {S}_{n - s}(\widetilde {h})} = 2^{2s - n} \#D^{s}(h)$. As a result,

$$ \begin{array}{@{}rcl@{}} \#{\mathrm{B}\mathrm{S}_{m}(\widetilde{g})} \leq 2^{2(n - m) - n} \#D^{n - m}(g) \leq 2^{2(n - m) - n} 2^{n} \prod\limits_{t = 0}^{n - m - 1}\frac{2^{n - 2t} - 1}{2 \cdot (2^{t + 1} - 1)} =\\ 2^{n - m}\prod\limits_{i = 1}^{n-m}\frac{2^{n - 2i + 2} - 1}{2^{i} - 1} = 2^{n - m}\prod\limits_{i = 1}^{n-m}\frac{2^{n - 2(n - m - i + 1) + 2} - 1}{2^{i} - 1} = \#{\mathrm{B}\mathrm{S}_{m}(\widetilde{h})}. \end{array} $$

It is more difficult to prove that the bound is attained only by quadratic functions for any m ≤ n − 2. The second part of the proof of [16, Theorem 2] gives us that #D^s(g) < #D^s(h) if there exists U ∈ D²(g) such that nc_g(U) < 2^n− 2⋅2, where s > 2. Let us prove the existence of such U by contradiction. Note that we exclude the case of #D²(g) = 0 since it is straightforward.

Let g be not quadratic. Suppose that nc_g(U) = 2^n− 2⋅2 for any U ∈ D²(g). We consider any U ∈ D²(g), U = u ⊕ L, where L is a linear subspace, $u \in {\mathbb {F}_{2}^{n}}$. Since nc_g(u ⊕ L) = 2^n− 2⋅2, Theorem 2 provides that g_a(x) = g(x) ⊕〈a,x〉 for some $a \in {\mathbb {F}_{2}^{n}}$ has a balanced representation by L, i. e. g_a is either constant or balanced on each coset of L. But any function balanced on 2-dimensional subspace is affine on it (see, for instance, [16, Proposition 2]). Thus, g_a is affine on each coset of L. As a consequence, g(x) = g_a(x) ⊕〈a,x〉 is affine on each coset of L as well. Hence, g is completely affinely decomposable of order 2.

Recall that g is completely affinely decomposable of order 2 if 1) g is affine on at least one 2-dimensional affine subspace; 2) if g is affine on a 2-dimensional affine subspace, then g is affine on any its coset as well. It is known [16, Theorem 1] that only affine and quadratic functions can satisfy these conditions, which contradicts the choice of g.

Thus, there exists U ∈ D²(g) such that nc_g(U) < 2^n− 2⋅2. In other words, #D^s(g) < #D^s(h) for any s > 2. It implies that $\#\mathrm {B}\mathrm {S}_{m}({\widetilde {g}}) < \#{\mathrm {B}\mathrm {S}_{m}(\widetilde {h})}$ for any m < n − 2. Let us consider s = 2. Since nc_g(U) < 2^n− 2⋅2, it can be seen that $\#{\mathrm {B}\mathrm {S}_{n - 2}(\widetilde {g})} = \#P^{2}(g) < 2^{2 \cdot 2 - n} \#D^{2}(g) \leq 2^{2 \cdot 2 - n} \#D^{2}(h) = \#{\mathrm {B}\mathrm {S}_{n - 2}(\widetilde {h})}$. Finally, we choose $\widetilde {f}$ as g since f is quadratic if and only if $\widetilde {f}$ is quadratic. The same is true for h. □

5.1 Bent functions with # BS_m(f) = 0

Let us show that # BS_m(f) = 0 for some $f \in {{\mathscr{B}}_{n}}$ and some m. First of all, the following necessary condition for derivatives holds.

Lemma 1

Let $f \in {{\mathscr{B}}_{n}}$ and the function f(x) ⊕〈w,x〉, $w \in {\mathbb {F}_{2}^{n}}$, have a balanced representation by a linear subspace L, $\dim L \geq 2$. Then D_Lf ≡ 0.

Proof

First of all, D_L〈w,x〉≡ 0 since $\dim L \geq 2$. Next, let us recall that $D_{L} f(x) = \bigoplus _{a \in L} f(x \oplus a).$ Since f is either constant or balanced on a fixed x ⊕ L, the number of ones among f(x ⊕ a), a ∈ L, is either 0 or $2^{\dim L - 1}$ or $2^{\dim L}$, i. e. it is always even. Therefore, D_Lf(x) = 0 for any $x \in {\mathbb {F}_{2}^{n}}$. □

This subsection focuses on the Kasami bent functions. It was proven [12, 19] that the functions of the form $f(x) = \text {tr}(\alpha x^{2^{2k} - 2^{k} + 1})$ are bent, where

• $\alpha , x \in \mathbb {F}_{2^{n}}$, $\mathbb {F}_{2^{n}}$ is the field with 2ⁿ elements and n is even;

• $\text {tr}(y) = y^{2^{0}} + y^{2^{1}} + {\ldots } + y^{2^{n - 1}}, y \in \mathbb {F}_{2^{n}}$, tr(y) always belongs to ${\mathbb {F}_2^{}}$;

• 0 < k < n and $\gcd (k, n) = 1$;

• $\alpha \notin \{ y^{3} \ | \ y \in \mathbb {F}_{2^{n}}\}$. Note that $\{ y^{3} \ | \ y \in \mathbb {F}_{2^{n}}\} \neq \mathbb {F}_{2^{n}}$ if n is even.

These functions are called the Kasami bent functions. Though they map $\mathbb {F}_{2^{n}}$ to ${\mathbb {F}_2^{}}$, we can fix a basis of $\mathbb {F}_{2^{n}}$ (since it is a vector space over ${\mathbb {F}_2^{}}$) and consider them as Boolean functions. It is well known that $\deg f = k + 1$ for 0 < k < n/2 and $\deg f = n - k + 1$ for n/2 < k < n.

In A. Gorodilova’s work [15] the properties of D_Lf of the Kasami functions were studied. We note the following result.

Theorem 5 (A. Gorodilova, 2013)

Let f be a Kasami bent function in n variables of degree t, n ≥ 8 is even. Then D_Lf≢0 for any k-dimensional linear subspace L, where

$$ k \leq \begin{cases} t - 2, & \text{ if } 4 \leq t \leq (n + 3)/3;\\ t - 3, & \text{ if } (n+3)/3 < t \leq n / 2. \end{cases} $$

These derivatives for 2-dimensional L were also studied in [27]: using the derivatives, D. Sharma et al. proved that a nonquadratic Kasami bent function does not belong to the Maiorana–McFarland class.

In light of these results, it is not difficult to prove that

Theorem 6

There exists a Kasami bent function f in n variables such that $\#{\mathrm {B}\mathrm {S}_{m}(\widetilde {f})} = 0$, where

$$ n - 2 \geq m \geq \begin{cases} n/2 + 3, & \text{ if } 4 \ | \ n \text{ or } n = 10;\\ n/2 + 4, & \text{ otherwise}. \end{cases} $$

Proof

Recall that there exists a Kasami bent function in n variables of degree n/2 if 4 | n and of degree n/2 − 1 for other even n. In the first case, $\gcd (n, n/2 - 1) = 1$ allows us to construct a Kasami bent function f of degree n/2. In the second case, $\gcd (n, n/2 - 2) = 1$ and, similarly, there exists a Kasami function f of degree n/2 − 1. According to Lemma 1 and Theorem 5, these Kasami functions (even if we add an affine function) cannot have a nontrivial balanced representation by a subspace of dimension at most n/2 − 3 and n/2 − 4 respectively. The case of n = 10 satisfies 4 ≤ t ≤ (10 + 3)/3 case of Theorem 5 and can be considered as the first case. Thus, Theorem 1 provides that $\#{\mathrm {B}\mathrm {S}_{m}(\widetilde {f})} = 0$, where n − 2 ≥ m ≥ n − (n/2 − 3) for the first case and n − 2 ≥ m ≥ n − (n/2 − 4) for the second case. □

Let us note that in Section 6.2 we consider bent functions $f \in {{\mathscr{B}}_{n}}$ such that # BS_m (f) = 0 for m ≤ n/2 + 3. In some sense, these examples complement Theorem 6: in this section we focus on m = n − 2,n − 3,…, in Section 6.2 we focus on m = n/2,n/2 + 1,…. Unfortunately, at the moment there is no example of a bent function $f \in {{\mathscr{B}}_{n}}$, where n is arbitrary, such that # BS_m(f) = 0 for any m ≤ n − 2.

6 BS_m(f _+ 2) for the iteratively constructed bent function f _+ 2

Let us consider the simplest iterative construction of a bent function f_+ 2 by $f \in {{\mathscr{B}}_{n}}$:

$$ f_{+2}(x_{1}, \ldots, x_{n+2}) = f(x_{1}, \ldots, x_{n}) \oplus x_{n + 1}x_{n+2}. $$

Recall that $f_{+2} \in {{\mathscr{B}}_{n + 2}}$ if and only if $f \in {{\mathscr{B}}_{n}}$. Also, it holds

$$ \widetilde{f_{+2}}(x_{1}, \ldots, x_{n+2}) = \widetilde{f}(x_{1}, \ldots, x_{n}) \oplus x_{n + 1}x_{n + 2}. $$

Since f and f_+ 2 have different number of variables, let us define

$$ {\text{pj}_{n}(x)} = (x_{1}, \ldots, x_{n}) \text{ and } {\text{pj}_{n}(S)} = \{{\text{pj}_{n}(x)} \ | \ x \in S\}, $$

where $x \in {\mathbb {F}_2^{n + 2}}$ and $S \subseteq {\mathbb {F}_2^{n + 2}}$. Also, ${{\mathbb {F}_{2}^{n}}(S)} = \{x \in {\mathbb {F}_{2}^{n}} \ | \ (x, 0, 0) \in S \}$.

In this section, we establish the connection between BS_m− 1(f), BS_m− 2(f) and BS_m(f_+ 2).

6.1 Balanced representations of iteratively constructed functions

Recall that $f \in {{\mathscr{B}}_{n}}$ is normal if it has a balanced representation by some n/2-dimensional L. Hence, the result of this subsection (Theorem 7 and the bellow proposition) is a generalization of the normal bent function property “f is normal if and only if f_+ 2 is normal” which was proven in [3] (see also [8]).

Proposition 5

Let $f \in {\mathscr{B}}_{n}$ have a balanced representation by a linear subspace $L \subseteq \mathbb {F}_{2}^{n}$. Then the bent function f_+ 2 has balanced representations by

• 1. L₀ = {(x,0,0) | x ∈ L}, i. e. $\dim L_{0} = \dim L$;

• 2. $L_{1} = \{(x, y, 0) \ | \ x \in L, y \in {\mathbb {F}_2^{}}\}$, i. e. $\dim L_{1} = \dim L + 1$.

Let us establish which balanced representations of f exist if we have some balanced representation of f_+ 2.

Theorem 7

Let $f \in {{\mathscr{B}}_{n}}$ and suppose that f_+ 2 has a balanced representation by a linear subspace $L \subseteq {\mathbb {F}_2^{n + 2}}$. Then there exists a linear subspace $L^{\prime } \subseteq {\mathbb {F}_{2}^{n}}$, where $\dim L - 1 \leq \dim L^{\prime } \leq \dim L,$ such that f has a balanced representation by $L^{\prime }$. Moreover, ${{\mathbb {F}_{2}^{n}}(L)} \subseteq L^{\prime } \subseteq {\text {pj}_{n}(L)}$ holds.

Proof

Let $x = (x_{1}, \ldots , x_{n + 2}) \in {\mathbb {F}_2^{n + 2}}$. For convenience, we rename the variables of both functions, that is, consider f(x₃,…,x_n+ 2) and f_+ 2(x) = x₁x₂ ⊕ f(x₃,…,x_n+ 2), where the function f is defined on the set

$$ {{\varGamma}} = \{\widetilde{x} \ | \ x \in {\mathbb{F}_2^{n + 2}}\} \subseteq {\mathbb{F}_2^{n + 2}}, \ \widetilde{x} = (0, 0, x_{3}, \ldots, x_{n + 2}). $$

We work with ${{\mathbb {F}_{2}^{n}}(L)}$ and pj_n(L) taking into account the new notation, i. e. $\text {pj}_{n}({x}) = \widetilde {x} \in {{\varGamma }}$ and $\mathbb {F}^{n}_{2}({L}) = L \cap {{\varGamma }}$.

Suppose that f_+ 2 has a balanced representation by a (t + 1)-dimensional subspace $L \subseteq {\mathbb {F}_2^{n + 2}}$. By Theorem 2, it is constant on each of s¹ ⊕ L,…,s^m ⊕ L which are distinct, $s^{1}, \ldots , s^{m} \in {\mathbb {F}_2^{n+2}}$ and m = 2^n− 2t. Let $L^{\prime } = L \cap {{\varGamma }}$. Since $\dim {{\varGamma }} = n$, then $\dim L^{\prime } \in \{t + 1, t, t - 1\}$.

Case 1

$\dim L^{\prime } = t + 1$. Therefore, $L = L^{\prime } \subseteq {{\varGamma }}$, i. e. any coset of $L^{\prime }$ either belongs to Γ or does not intersect with Γ. Since $f(a \oplus x) = f_{+2}(a \oplus x) \text { for all } x \in L^{\prime }, a \in {{\varGamma }},$ the function f is either constant or balanced on each coset of $L^{\prime }$ which belongs to Γ. Hence, it has balanced representation by $L^{\prime } = L$. Moreover, $L^{\prime } = {{\mathbb {F}_{2}^{n}}(L)}$ holds.

Case 2

$\dim L^{\prime } = t$. Then for some fixed $\alpha \in L \setminus L^{\prime }$ we can represent any x ∈ L as $x = x^{\prime } \oplus y \alpha , \text { where } x^{\prime } \in L^{\prime }, y \in {\mathbb {F}_2^{}}.$ Fixing some $s \in {\mathbb {F}_2^{n + 2}}$, it holds

$$ \begin{array}{@{}rcl@{}} f_{+2}(s \oplus y \alpha \oplus x^{\prime}) &=& f(\widetilde{s} \oplus y \widetilde{\alpha} \oplus x^{\prime}) \oplus (s_{1} \oplus y \alpha_{1})(s_{2} \oplus y \alpha_{2}) = f(\widetilde{s} \oplus y \widetilde{\alpha} \oplus x^{\prime}) \\ \oplus (\alpha_{1} s_{2} &\oplus& \alpha_{2} s_{1} \oplus \alpha_{1} \alpha_{2}) y \oplus s_{1} s_{2} \text{ for all } x^{\prime} \in L^{\prime} \text{ and } y \in {\mathbb{F}_2^{}}. \end{array} $$

(1)

Let us consider S = (s¹ ⊕ L) ∪… ∪ (s^m ⊕ L). It is obvious that #S = m2^t+ 1. Note that if f_+ 2 is constant on s ⊕ L, s ∈ S, then f_+ 2 is constant on a ⊕ s ⊕ L for $a = (\alpha _{1}, \alpha _{2}, 0, \ldots , 0) \in {\mathbb {F}_2^{n + 2}}$ too. Indeed, (α₁s₂ ⊕ α₂s₁ ⊕ α₁α₂)y = (α₁(s₂ ⊕ α₂) ⊕ α₂(s₁ ⊕ α₁) ⊕ α₁α₂)y for any $y \in {\mathbb {F}_2^{}}$, that is why (1) gives us

$$ \begin{array}{@{}rcl@{}} f_{+2}(s \oplus a \oplus y \alpha \oplus x^{\prime}) = f_{+2}(s \oplus y \alpha \oplus x^{\prime}) \oplus \\ \alpha_{1} s_{2} \oplus \alpha_{2} s_{1} \oplus \alpha_{1} \alpha_{2} \text{ for all } x^{\prime} \in L^{\prime} \text{ and } y \in {\mathbb{F}_2^{}}. \end{array} $$

At the same time, Theorem 2 claims that the bent function f_+ 2 cannot be constant on more than m distinct cosets. Therefore, a ⊕ S = S. Since $a \in L \setminus L^{\prime }$, it holds (α₁,α₂)≠(0,0). Let us consider two subcases.

Case 2.1

a ∈ L. In this case we can suppose that α = a. Then, fixing some s ∈ S, equality (1) transforms to

$$ \begin{array}{@{}rcl@{}} f_{+2}(s) = f_{+2}(s \oplus y \alpha \oplus x^{\prime}) = f(\widetilde{s} \oplus x^{\prime}) \oplus (\alpha_{1} s_{2} \oplus \alpha_{2} s_{1} \oplus \alpha_{1} \alpha_{2}) y \\ \oplus s_{1} s_{2} \text{ for all } x^{\prime} \in L^{\prime} \text{ and } y \in {\mathbb{F}_2^{}}. \end{array} $$

(2)

On the one hand, f is constant on each $u \oplus L^{\prime }$, where $u \in \widetilde {S} = \{ \widetilde {s} \ | \ s \in S\}$. On the other hand, $f(\widetilde {s} \oplus x^{\prime })$ does not depend on y. It means that α₁s₂ ⊕ α₂s₁ ⊕ α₁α₂ = 0 for all s ∈ S. Thus, for two elements of ${\mathbb {F}_2^{2}}$ given as (s₁,s₂), the equality does not hold. Therefore, $\#\widetilde {S} \geq \#S/2 = m 2^{t}$. But in this case we have at least $m = m 2^{t} / 2^{\dim L^{\prime }}$ distinct cosets of $L^{\prime }$ such that f is constant on each of them. By Theorem 2, f has a balanced representation by t-dimensional $L^{\prime }$. Note that ${{\mathbb {F}_{2}^{n}}(L)} = L^{\prime } = {\text {pj}_{n}(L)}$ holds.

Case 2.2

a∉L. Let us consider $L^{\prime \prime } = L \cup (a \oplus L)$, $\dim L^{\prime \prime } = t + 2$. Since a ⊕ S = S, the first point of Proposition 1 provides that f_+ 2 has a balanced representation by $L^{\prime \prime }$. To conclude the case, it is enough to note that any element $x \in L^{\prime \prime }$ can be represented as $x = x^{\prime } \oplus \alpha y \oplus a z = x^{\prime } \oplus y (\alpha \oplus a) \oplus (z \oplus y) a = x^{\prime } \oplus y \beta \oplus z^{\prime } a,$ where $\beta = \alpha \oplus a \in {{\varGamma }}, x^{\prime } \in L^{\prime }, \ y, z^{\prime } \in {\mathbb {F}_2^{}}$. Hence, we obtain that f_+ 2 has a balanced representation by (t + 2)-dimensional $L^{\prime \prime }$. At the same time, $\dim L^{\prime \prime } \cap {{\varGamma }} = t + 1$ and $a \in L^{\prime \prime }$. It means that we can apply the case 2.1 to the subspace $L^{\prime \prime }$ and the element a. As a result, the function f has a balanced representation by (t + 2 − 1)-dimensional $L^{\prime } \cup (\beta \oplus L^{\prime }) = U$. Also, ${{\mathbb {F}_{2}^{n}}(L)} \subset U \subseteq {\text {pj}_{n}(L)}$ holds.

Case 3

$\dim L^{\prime } = t - 1$. In this case there exist $\alpha , \beta \in L \setminus L^{\prime }$ such that (α₁,α₂) = (1,0) and (β₁,β₂) = (0,1). Any element x ∈ sⁱ ⊕ L, i ∈{1,…,m}, can be represented as $x = s^{i} \oplus x^{\prime } \oplus y \alpha \oplus z \beta , \text { where } x^{\prime } \in L^{\prime }, y, z \in {\mathbb {F}_2^{}}.$ Without loss of generality, let us suppose that sⁱ ∈Γ (otherwise, we can consider sⁱ ⊕ α, sⁱ ⊕ β or sⁱ ⊕ α ⊕ β instead of sⁱ). Next, for any fixed i ∈{1,…,m} it holds

$$ \begin{array}{@{}rcl@{}} f(s^{i}) = f_{+2}(s^{i}) = f_{+2}(s^{i} \oplus x) = f_{+2}(s^{i} \oplus x^{\prime} \oplus y \alpha \oplus z \beta) = \\ f(s^{i} \oplus x^{\prime} \oplus y \widetilde{\alpha} \oplus z \widetilde{\beta}) \oplus yz \text{ for all } x^{\prime} \in L^{\prime} \text{ and } y,z \in {\mathbb{F}_2^{}}. \end{array} $$

(3)

Thus, f is constant on each of $s^{i} \oplus L^{\prime }$, $s^{i} \oplus \widetilde {\alpha } \oplus L^{\prime }$, $s^{i} \oplus \widetilde {\beta } \oplus L^{\prime }$ and $s^{i} \oplus \widetilde {\alpha } \oplus \widetilde {\beta } \oplus L^{\prime }$.

We consider the subspace $L^{\prime \prime } = L^{\prime } \cup (\widetilde {\alpha } \oplus \widetilde {\beta } \oplus L^{\prime })$. Let us show that $\dim L^{\prime \prime } = t$. It is equivalent to $\widetilde {\alpha } \oplus \widetilde {\beta } \notin L^{\prime }$. Indeed, fixing $x^{\prime } = 0$, (3) provides that

$$ f(s^{i}) = f_{+2}(s^{i}) = f_{+2}(s^{i} \oplus \alpha \oplus \beta) = f(s^{i} \oplus \widetilde{\alpha} \oplus \widetilde{\beta}) \oplus 1, $$

but f is constant on $s^{i} \oplus L^{\prime }$. It means that $\widetilde {\alpha } \oplus \widetilde {\beta } \notin L^{\prime }$.

Next, we prove that f is constant on each of $s^{i} \oplus \widetilde {\alpha } \oplus L^{\prime \prime }$. Note that $s^{i} \oplus \widetilde {\alpha } \oplus L^{\prime \prime } = (s^{i} \oplus \widetilde {\alpha } \oplus L^{\prime }) \cup (s^{i} \oplus \widetilde {\beta } \oplus L^{\prime })$. According to (3),

$$ f(s^{i} \oplus \widetilde{\alpha}) = f_{+2}(s^{i} \oplus \alpha) = f_{+2}(s^{i} \oplus \beta) = f(s^{i} \oplus \widetilde{\beta}). $$

At the same time, f is constant on both $s^{i} \oplus \widetilde {\alpha } \oplus L^{\prime }$ and $s^{i} \oplus \widetilde {\beta } \oplus L^{\prime }$, i. e. it is constant on their union.

The rest of the case is to prove that all $s^{i} \oplus \widetilde {\alpha } \oplus L^{\prime \prime }$ are distinct. Suppose that $s^{i} \oplus \widetilde {\alpha } \oplus s^{j} \oplus \widetilde {\alpha } = s^{i} \oplus s^{j} \in L^{\prime \prime }$ for i≠j, where i,j ∈{1,…,m}. But $s^{i} \oplus s^{j} \notin L^{\prime } \subseteq L$ by the choice. Therefore, $s^{i} \oplus s^{j} \in \widetilde {\alpha } \oplus \widetilde {\beta } \oplus L^{\prime }$. In other words, $s^{i} = s^{j} \oplus \widetilde {\alpha } \oplus \widetilde {\beta } \oplus x^{\prime }, x^{\prime } \in L^{\prime }$. By (3) and the definition of f_+ 2, we obtain that

$$ \begin{array}{@{}rcl@{}} f_{+2}(s^{i}) = f_{+2}(s^{i} \oplus y \alpha \oplus z \beta) = f(s^{i} \oplus y \widetilde{\alpha} \oplus z \widetilde{\beta}) \oplus yz = \\ f(s^{j} \oplus (y \oplus 1) \widetilde{\alpha} \oplus (z \oplus 1)\widetilde{\beta} \oplus x^{\prime}) \oplus (y \oplus 1)(z \oplus 1) \oplus y \oplus z \oplus 1 = \\ f_{+2}(s^{j} \oplus (y \oplus 1) \alpha \oplus (z \oplus 1) \beta \oplus x^{\prime}) \oplus y \oplus z \oplus 1 \text{ for all } y, z \in {\mathbb{F}_2^{}}. \end{array} $$

But $f_{+2}(s^{j} \oplus (y \oplus 1) \alpha \oplus (z \oplus 1) \beta \oplus x^{\prime }) = f_{+2}(s^{j})$. Hence, f_+ 2(sⁱ) = f_+ 2(s^j) ⊕ y ⊕ z ⊕ 1 for all $y, z \in {\mathbb {F}_2^{}}$, which is a contradiction. As a result, any two of $s^{i} \oplus \widetilde {\alpha } \oplus L^{\prime \prime }$ are distinct and f is constant on each of them. By Theorem 2, f has a balanced representation by $L^{\prime \prime }$. Note that ${{\mathbb {F}_{2}^{n}}(L)} \subset L^{\prime \prime } \subset {\text {pj}_{n}(L)}$ holds. □

6.2 The connection between BS_m− 1(f), BS_m− 2(f) and BS_m(f _+ 2)

Recall that Theorem 1 gives us the connection between an affine subspace U, for which f ⊕Ind_U is a bent function, and the balanced representation of the bent function $\widetilde {f}$. It means that the results obtained in Section 6.1 can help us to establish the connection between the sets BS_m(f) and BS_k(f_+ 2).

Proposition 6

Let $f \in {\mathscr{B}}_{n}$ and $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U} \in {{\mathscr{B}}_{n}}$, where U is an affine subspace of ${\mathbb {F}_{2}^{n}}$. Then both $f_{+2} \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U_{1}}$ and $f_{+2} \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U_{2}}$ are bent functions, where

• 1. $U_{1} = \{(x, y, 0) \ | \ x \in U, y \in {\mathbb {F}_2^{}}\}$, i. e. $\dim U_{1} = \dim U + 1$;

• 2. $U_{2} = \{(x, y, z) \ | \ x \in U, y,z \in {\mathbb {F}_2^{}}\}$, i. e. $\dim U_{2} = \dim U + 2$.

Theorem 8

Let $f_{+2} \in {{\mathscr{B}}_{n + 2}}$ and $f_{+2} \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{a \oplus L} \in {{\mathscr{B}}_{n + 2}}$, where $L \subseteq {\mathbb {F}_2^{n + 2}}$ is a linear subspace, $a \in {\mathbb {F}_2^{n + 2}}$. Then there exists a linear subspace $L^{\prime } \subseteq {\mathbb {F}_{2}^{n}}$, where $\dim L - 2 \leq \dim L^{\prime } \leq \dim L - 1$, such that $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{{\text {pj}_{n}(a)} \oplus L^{\prime }} \in {{\mathscr{B}}_{n}}$. Moreover, ${{\mathbb {F}_{2}^{n}}(L)} \subseteq L^{\prime } \subseteq {\text {pj}_{n}(L)}$ holds.

Proof

By Theorem 1, $f_{+2} \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{a \oplus L} \in {{\mathscr{B}}_{n + 2}}$ if and only if $\widetilde {f}(x) \oplus {\langle a, x \rangle }$ has a balanced representation by L^⊥. Let us consider f_+ 2(x ⊕ a) instead of f_+ 2:

$$ f_{+2}(x \oplus a) = f({\text{pj}_{n}(x)} \oplus {\text{pj}_{n}(a)}) \oplus (x_{n+1} \oplus a_{n + 1})(x_{n+2} \oplus a_{n + 2}). $$

Since (x_n+ 1 ⊕ a_n+ 1)(x_n+ 2 ⊕ a_n+ 2) = x_n+ 1x_n+ 2 ⊕ a_n+ 2x_n+ 1 ⊕ a_n+ 1x_n+ 2 ⊕ a_n+ 1a_n+ 2, we can exclude ℓ(x) = a_n+ 2x_n+ 1 ⊕ a_n+ 1x_n+ 2 ⊕ a_n+ 1a_n+ 2 from f_+ 2(x ⊕ a): indeed, $g \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U} \in {\mathscr{B}}_{n + 2}$ if and only if $g \oplus \ell \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U} \in {{\mathscr{B}}_{n + 2}}$.

It means that $\widetilde {f({\text {pj}_{n}(x)} \oplus {\text {pj}_{n}(a)}}) \oplus x_{n+1}x_{n+2}$ has a balanced representation by L^⊥. According to Theorem 7, $\widetilde {f({\text {pj}_{n}(x)} \oplus {\text {pj}_{n}(a)})}$ has a balanced representation by $L^{\prime }$, where ${{\mathbb {F}_{2}^{n}}(L^{\bot })} \subseteq L^{\prime } \subseteq {\text {pj}_{n}(L^{\bot })}$. Again, it implies that $f({\text {pj}_{n}(x)} \oplus {\text {pj}_{n}(a)}) \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{L^{\prime \bot }}(x)$ is a bent function. Consequently, $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{{\text {pj}_{n}(a)} \oplus L^{\prime \bot }}$ is a bent function too, where $({\text {pj}_{n}(L^{\bot })})^{\bot } \subseteq L^{\prime \bot } \subseteq ({{\mathbb {F}_{2}^{n}}(L^{\bot })})^{\bot }$.

To complete the proof, it is necessary to check the bounds for $L^{\prime \bot }$. The dimensions obviously satisfy the conditions. Next,

$$ \begin{array}{@{}rcl@{}} ({\text{pj}_{n}(L^{\bot})})^{\bot} = \{x \in {\mathbb{F}_{2}^{n}} \ | \ {\langle x, y \rangle} = 0 \text{ for any } y \in {\text{pj}_{n}(L^{\bot})}\} = \\ \{x \in {\mathbb{F}_{2}^{n}} \ | \ {\langle (x, 0,0), y \rangle} = 0 \text{ for any } y \in L^{\bot}\} = \\ (L^{\bot})^{\bot} \cap \{ (x, 0,0) \ | \ x \in {\mathbb{F}_{2}^{n}}\} = {{\mathbb{F}_{2}^{n}}(L)}. \end{array} $$

We obtain that $({\text {pj}_{n}(L)})^{\bot } = ({\text {pj}_{n}((L^{\bot })^{\bot })})^{\bot } = {{\mathbb {F}_{2}^{n}}(L^{\bot })}$ from the above equality, i. e. $({{\mathbb {F}_{2}^{n}}(L^{\bot })})^{\bot } = {\text {pj}_{n}(L)}$. As a result, ${{\mathbb {F}_{2}^{n}}(L)} \subseteq L^{\prime \bot } \subseteq {\text {pj}_{n}(L)}$ holds. □

Theorem 8 allows us to preserve k zero values starting with n/2: if

$$ \#{\mathrm{B}\mathrm{S}_{n/2}(f)} = \#{\mathrm{B}\mathrm{S}_{n/2 + 1}(f)} = {\ldots} = \#{\mathrm{B}\mathrm{S}_{n/2 + k - 1}(f)} = 0, \text{ then} $$

$$ \#{\mathrm{B}\mathrm{S}_{n/2 + 1}(f_{+2})} = \#{\mathrm{B}\mathrm{S}_{n/2 + 2}(f_{+2})} = {\ldots} = \#{\mathrm{B}\mathrm{S}_{n/2 + k}(f_{+2})} = 0. $$

Computational experiments show that for the non-weakly normal bent function $f_{10} \in {{\mathscr{B}}_{10}}$ found in [20, Fact 14] the following holds.

Fact 1

For an affine subspace $U \subseteq {\mathbb {F}_2^{10}}$, $\dim U \leq 8$, $f_{10} \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U} \notin {{\mathscr{B}}_{10}}$ holds.

Together with Theorem 8, it implies the following:

Corollary 2

For any n ≥ 10, there exists a bent function $f \in {{\mathscr{B}}_{n}}$ such that $f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U} \notin {\mathscr{B}}_{n}$ for any affine subspace $U \subseteq {\mathbb {F}_{2}^{n}}$ of dimension at most n/2 + 3.

Remark 1

We do not consider the more general iterative construction h(x,y) = f(x) ⊕ g(y), where $x \in {\mathbb {F}_{2}^{n}}$ and $y \in {\mathbb {F}_2^{t}}$, for which we have the same “normal” property [8]: if g is normal, then h is normal if and only if f is normal. It is more difficult and D_(a,0)D_(0,b)h ≡ 0 for any $a \in {\mathbb {F}_{2}^{n}}$, $b \in {\mathbb {F}_2^{t}}$. According to Proposition 7 (see Section 6.3), ${\mathrm {B}\mathrm {S}_{n + t - 2}(\widetilde {h})}$ is always nonempty.

6.3 Exact number of functions in BS_n(f _+ 2)

Despite the bounds from Theorem 8, it seems impossible to obtain # BS_m(f_+ 2) by # BS_m− 1(f) and # BS_m− 2(f). Theorem 9 and computational experiments will clearly show this. The next proposition follows from [2, Theorem 8]. It can be proven directly by the second point of Theorem 1.

Proposition 7 (A. Canteaut, P. Charpin, 2003)

Let $f \in {{\mathscr{B}}_{n}}$, L be an (n − 2)-dimensional linear subspace of $\mathbb {F}_{2}^{n}$ and $a \in {\mathbb {F}_{2}^{n}}$. Then f ⊕Ind_a⊕L is a bent function if and only if $D_{L^{\bot }} \widetilde {f} \equiv 0$.

Let us introduce

$$ K_{c}(f) = \#\{2\text{-dimensional linear subspace } L \ | \ D_{L} f \equiv c\}, \ c \in {\mathbb{F}_2^{}}. $$

Proposition 7 implies that $\#{\mathrm {B}\mathrm {S}_{n-2}(\widetilde {f})} = 4 K_{0}(f)$.

Theorem 9

For any $f \in {{\mathscr{B}}_{n}}$ it holds

$$ \begin{array}{@{}rcl@{}} K_{0}(f_{+2}) &=& 10 K_{0}(f) + 6 K_{1}(f) + 3 \cdot 2^{n} - 3,\\ K_{1}(f_{+2}) &=& 6 K_{0}(f) + 10 K_{1}(f) + 3 \cdot 2^{n} - 2. \end{array} $$

Proof

Let us work with a Gauss–Jordan basis (GJB) of a 2-dimensional linear subspace of ${\mathbb {F}_2^{n + 2}}$ (see, for instance, [3]). We need to define lead(a) = i such that a_i = 1 and a_j = 0 for all j < i, where i,j ∈{1,…,n + 2}. A pair of nonzero $a, b \in {\mathbb {F}_2^{n + 2}}$ is a GJB of the linear subspace {0,a,b,a ⊕ b} if lead(a) > lead(b) and b_lead(a) = 0. For any linear subspace there exists a unique GJB.

Let $a = (a^{\prime }, \alpha ), b = (b^{\prime }, \beta ) \in {\mathbb {F}_2^{n + 2}}$, where $a^{\prime }, b^{\prime } \in {\mathbb {F}_{2}^{n}}$, $\alpha , \beta \in {\mathbb {F}_2^{2}}$. We note the following examples of GJBs:

In the first example, lead(a) = 4, lead(b) = 2. Also, $a^{\prime }, b^{\prime }$ are linearly independent, α,β are linearly dependent. In the second example, lead(a) = 6, lead(b) = 2. Also, $a^{\prime }, b^{\prime }$ are linearly dependent, α,β are linearly independent.

Let us count the number of GJBs a,b that correspond to D_Lf ≡ c, $c \in {\mathbb {F}_2^{}}$. Firstly, it is easy to see that $D_{L} f_{+2}(x) = D_{a^{\prime }} D_{b^{\prime }} f(x_{1}, \ldots , x_{n}) \oplus D_{\alpha } D_{\beta } x_{n+1}x_{n+2}.$ Note that D_αD_βx_n+ 1x_n+ 2 ≡ d, where $d \in {\mathbb {F}_2^{}}$. It means that D_Lf_+ 2 ≡ c if and only if $D_{a^{\prime }} D_{b^{\prime }} f \equiv c \oplus d$. Also, the following holds:

• 1. D_αD_βx_n+ 1x_n+ 2 ≡ 1 if and only if α,β are linearly independent;

• 2. $D_{a^{\prime }} D_{b^{\prime }} f \equiv 0$ for linearly dependent $a^{\prime }, b^{\prime }$.

Next, we calculate K₀(f_+ 2). All the desired subspaces satisfy one of the independent cases:

Case 1

$a^{\prime }$ and $b^{\prime }$ are linearly independent. There are two subcases here:

Case 1.1

$D_{a^{\prime }} D_{b^{\prime }} f \equiv 0$ and D_αD_βx_n+ 1x_n+ 2 ≡ 0. There are K₀(f) possibilities to choose a GJB $a^{\prime }, b^{\prime }$. According to point 1, any linearly dependent α,β can be chosen, there are exactly 10 such pairs. We obtain 10K₀(f) GJBs.

Case 1.2

$D_{a^{\prime }} D_{b^{\prime }} f \equiv 1$ and D_αD_βx_n+ 1x_n+ 2 ≡ 1. Similarly to the previous case, there are 6K₁(f) distinct GJBs, since α,β are linearly independent; there are exactly 6 such pairs (α,β).

Case 2

$a^{\prime }$ and $b^{\prime }$ are linearly dependent (it holds $D_{a^{\prime }} D_{b^{\prime }} f \equiv 0$ by point 2) and D_αD_βx_n+ 1x_n+ 2 ≡ 0. To form a GJB (a,b) by linearly dependent $a^{\prime }, b^{\prime }$, $a^{\prime } = 0$ is necessary. Any nonzero vector can be chosen as $b^{\prime }$ (we do not consider $b^{\prime } = 0$ since α,β are linearly dependent too). Next, any of 3 nonzero elements can be chosen as α: (1,0),(0,1) or (1,1). But β_lead(α) = 0≠α_lead(α), it means that the only way is β = (0,0). Finally, we have 3(2ⁿ − 1) distinct GJBs. It means that K₀(f_+ 2) = 10K₀(f) + 6K₁(f) + 3 ⋅ 2ⁿ − 3.

We calculate K₁(f_+ 2) in the same way:

Case 1

$a^{\prime }$ and $b^{\prime }$ are linearly independent. Thus, there are two subcases:

Case 1.1

$D_{a^{\prime }} D_{b^{\prime }} f \equiv 0$ and D_αD_βx_n+ 1x_n+ 2 ≡ 1, there are 6K₀(f) GJBs.

Case 1.2

$D_{a^{\prime }} D_{b^{\prime }} f \equiv 1$ and D_αD_βx_n+ 1x_n+ 2 ≡ 0, there are 10K₁(f) GJBs.

Case 2

$a^{\prime }$ and $b^{\prime }$ are linearly dependent and D_αD_βx_n+ 1x_n+ 2 ≡ 1, i. e. α,β are linearly independent by point 1. Similarly to K₀(f_+ 2), $a^{\prime } = 0$ is necessary. If $b^{\prime } = 0$, the only way to choose (a,b) is α = (1,0) and β = (0,1). Also, any $b^{\prime } \neq 0$ can be chosen. In this case there are 3 possibilities for α: (1,0),(0,1) or (1,1). Since β_lead(α) = 0, the only way to choose linearly independent α,β is to set the rest non-leading coordinate of β to 1. Finally, we have 3(2ⁿ − 1) + 1 distinct GJBs.

As a result, K₁(f_+ 2) = 6K₀(f) + 10K₁(f) + 3 ⋅ 2ⁿ − 2. □

It can be seen that K₀(f_+ 2) and, as a result, $\#{\mathrm {B}\mathrm {S}_{n}(\widetilde {f}_{+2})}$, depend on K₀(f) and K₁(f). Also, bounds from Theorem 8 bind ${\mathrm {B}\mathrm {S}_{n}(\widetilde {f}_{+2})}$ only with ${\mathrm {B}\mathrm {S}_{n-2}(\widetilde {f})}$: we do not consider ${\mathrm {B}\mathrm {S}_{n-1}(\widetilde {f})}$ since it is trivial and has the same structure for any bent function f. Unfortunately, it looks like K₁(f) has no direct connection to $\#{\mathrm {B}\mathrm {S}_{n-2}(\widetilde {f})}$. Computational experiments for Maiorana–McFarland bent functions confirm this:

Fact 2

Let ${f_{8}^{i}}(x, y) = {\langle x, \pi _{i}(y) \rangle }$, $x, y \in {\mathbb {F}_2^{4}}$, i ∈{1,2}, and π_i be defined by

$$\begin{array}{lllllllllllllllll} y & 0000 & 0001 & 0010 & 0011 & 0100 & 0101 & 0110 & 0111 & 1000 & 1001 & 1010 & 1011 & 1100 & 1101 & 1110 & 1111\\ \pi_{1}(y) & 0100 & 1001 & 1010 & 0011 & 0101 & 0111 & 1011 & 1101 & 1100 & 1110 & 0010 & 1111 & 0001 & 0110 & 1000 & 0000\\ \pi_{2}(y) & 0100 & 1001 & 1010 & 0011 & 1011 & 0111 & 0101 & 1100 & 1110 & 1101 & 0010 & 1111 & 0001 & 1000 & 0000 & 0110 \end{array}. $$

Then $\#{\mathrm {B}\mathrm {S}_{6}(\widetilde {{f_{8}^{1}}})} = \#{\mathrm {B}\mathrm {S}_{6}(\widetilde {{f_{8}^{2}}})}$, but $\#{\mathrm {B}\mathrm {S}_{8}(\widetilde {{f_{8}^{1}}}_{+2})} \neq \#{\mathrm {B}\mathrm {S}_{8}(\widetilde {{f_{8}^{2}}}_{+2})}$:

Thus, it is not sufficient to know # BS_n− 2(f) to calculate # BS_n(f_+ 2). Nevertheless, Theorem 9 allows us to construct an infinite family of bent functions with $\#{\mathrm {B}\mathrm {S}_{n-2}(f)} \neq \#{\mathrm {B}\mathrm {S}_{n-2}(\widetilde {f})}$.

7 BS_m(f) and ${\mathrm {B}\mathrm {S}_{m}(\widetilde {f})}$

In this section, we construct bent functions such that $\#{\mathrm {B}\mathrm {S}_{m}(f)} \neq \#{\mathrm {B}\mathrm {S}_{m}(\widetilde {f})}$.

Theorem 3 shows that the case of m = n/2 + 1 is very similar to the case of m = n/2: $\#{\mathrm {B}\mathrm {S}_{m}(f)} = \#{\mathrm {B}\mathrm {S}_{m}(\widetilde {f})}$ for m ≤ n/2 + 1. As a consequence, we have $\#{\mathrm {B}\mathrm {S}_{m}(f)} = \#{\mathrm {B}\mathrm {S}_{m}(\widetilde {f})}$ for any $f \in {{\mathscr{B}}_{2}} \cup {{\mathscr{B}}_{4}} \cup {{\mathscr{B}}_{6}}$ and any m. It seems that the simplest example of f such that $\#{\mathrm {B}\mathrm {S}_{m}(f)} \neq \#{\mathrm {B}\mathrm {S}_{m}(\widetilde {f})}$ can be found in ${{\mathscr{B}}_{8}}$ for m = 6. Computational experiments show that the following fact holds.

Fact 3

Let ξ₈(x,y) = 〈x,π(y)〉, where $x, y \in {\mathbb {F}_2^{4}}$, and π be defined by

$$ \begin{array}{lllllllllllllllll} y & 0000 & 0001 & 0010 & 0011 & 0100 & 0101 & 0110 & 0111 & 1000 & 1001 & 1010 & 1011 & 1100 & 1101 & 1110 & 1111\\ \pi(y) & 1001 & 1010 & 0100 & 0011 & 0101 & 0111 & 1011 & 1101 & 1100 & 1110 & 0010 & 1111 & 0001 & 0110 & 1000 & 0000 \end{array}. $$

Then $\#{\mathrm {B}\mathrm {S}_{6}(\xi _{8})} \neq \#{\mathrm {B}\mathrm {S}_{6}(\widetilde {\xi _{8}})}$. More precisely, ξ₈ and $\widetilde {\xi _{8}}$ have

Now, Fact 3 and Theorem 9 allow us to construct an infinite family of Maiorana–McFarland functions f_2k such that $\#{\mathrm {B}\mathrm {S}_{2k-2}(f_{2k})} \neq \#{\mathrm {B}\mathrm {S}_{2k-2}(\widetilde {f_{2k}})}$. Also, it implies that f_2k and $\widetilde {f_{2k}}$ are not EA-equivalent.

Corollary 3

$\#{\mathrm {B}\mathrm {S}_{2k-2}(f_{2k})} < \#{\mathrm {B}\mathrm {S}_{2k-2}(\widetilde {f_{2k}})}$ holds, where the function $f_{2k} \in {{\mathscr{B}}_{2k}}$, k ≥ 4, is defined by

$$ f_{2k}(x) = \xi_{8}(x_{1}, \ldots, x_{8}) \oplus x_{9}x_{10} \oplus x_{11} x_{12} \oplus {\ldots} \oplus x_{2k - 1} x_{2k}, \ x \in {\mathbb{F}_2^{2k}}. $$

Proof

It is easy to show by induction that $K_{0}(\widetilde {f_{2k}}) < K_{0}(f_{2k})$ and $K_{1}(\widetilde {f_{2k}}) < K_{1}(f_{2k})$. The base of the induction is the function f₈ = ξ₈, the induction step is provided by Theorem 9. It means that $\#{\mathrm {B}\mathrm {S}_{2k-2}(f_{2k})} = 4K_{0}(\widetilde {f_{2k}}) < 4K_{0}(f_{2k}) = \#{\mathrm {B}\mathrm {S}_{2k-2}(\widetilde {f_{2k}})}$. □

Thus, unlike m ≤ n/2 + 1, we obtain that # BS_m(f) and $\#{\mathrm {B}\mathrm {S}_{m}(\widetilde {f})}$ may not be equal. As a consequence, $\sup (\widetilde {f} \oplus (\widetilde {f \oplus \mathrm {I}\mathrm {n}\mathrm {d}_{U}}))$ may not be an affine subspace.

8 Conclusion

We have considered several properties of the bent function secondary construction f ⊕Ind_L, where f is a bent function in n variables and L is an affine subspace of arbitrary dimension. In particular, # BS_m(f), where BS_m(f) is the set of all bent functions of the form f ⊕Ind_L for an m-dimensional L, has been estimated. A relationship between considered subspaces in the simplest iterative construction has been established. Examples of the “most difficult” bent functions that have empty BS_m(f), for different m, have been provided. It has been found that the construction properties for arbitrary subspaces are quite similar to the case of n/2-dimensional subspaces, thus, we have generalized some known facts. At the same time, arbitrary dimensions have some specific properties that make the construction interesting.

Note that we have not provided an example of a bent function f in n variables, where n is arbitrary, such that BS_m(f) is empty for any m ≤ n − 2. It is a topic for future research.