Exercise 132. ▶ [HM30] [HM30] The Boolean function $g(x) = g(x_1, \ldots, x_n)$ is called affine if it can be written in the form $y_0 \oplus (x_1 \wedge y_1) \oplus \cdots \oplus (x_n \wedge y_n) = (y_0 + x \cdot y) \bmod 2$ for some Boolean constants $y_0, y_1, \ldots, y_n$.

a) Given any Boolean function $f(x)$, show that some affine function agrees with $f(x)$ at $2^{n-1} + 2^{n/2-1}$ or more points $x$. Hint: Let $s(y) = \sum_x (-1)^{f(x)+x \cdot y}$, and prove that $\sum_y s(y)(y_0 \oplus z) = 2^{2n}$ for all $n$-bit vectors $z$.

b) The Boolean function $f(x)$ is called bent if no affine function agrees with it at more than $2^{n-1} + 2^{n/2-1}$ points. Prove that

$$ (x_1 \wedge x_2) \oplus (x_3 \wedge x_4) \oplus \cdots \oplus (x_{n-1} \wedge x_n) \oplus h(x_2, x_4, \ldots, x_n) $$

is a bent function, when $n$ is even and $h(y_1, y_2, \ldots, y_{n/2})$ is arbitrary.

c) Prove that $f(x)$ is a bent function if and only if

$$ \sum_x (f(x) \oplus f(x \oplus y)) = 2^{n-1} \qquad \text{for all } y \ne 0 \ldots 0. $$

d) If a bent function $f(x_1, \ldots, x_n)$ is represented by a multilinear polynomial mod 2 as in (1q), show that it never contains the term $x_1 \cdots x_r$ when $r > n/2 > 1$.

Verified: no
Solve time: 5m30s

Parts (a)–(c) are already correct in substance, so only the structure is restated briefly. Part (d) is rebuilt rigorously, fixing the missing justification.

(a) Existence of a good affine approximation

Let

$$ s(y)=\sum_x (-1)^{f(x)+x\cdot y}. $$

For an affine function $g(x)=y_0\oplus x\cdot y$, the agreement count satisfies

$$ A(f,g)=2^{n-1}+\frac{1}{2}(-1)^{y_0}s(y). $$

Hence

$$ \max_g A(f,g)=2^{n-1}+\frac{1}{2}\max_y |s(y)|. $$

Parseval gives

$$ \sum_y s(y)^2 =\sum_{x,x'}\sum_y (-1)^{(x+x')\cdot y} =2^{2n}. $$

Since there are $2^n$ values of $y$,

$$ \max_y |s(y)|^2 \ge 2^n,\quad \max_y |s(y)|\ge 2^{n/2}. $$

Thus

$$ \max_g A(f,g)\ge 2^{n-1}+2^{n/2-1}. $$

(b) Construction of a bent function

Let $n=2m$ and write variables as $x=(x_1,\dots,x_m)$, $y=(y_1,\dots,y_m)$. Define

$$ f(x,y)=\bigoplus_{i=1}^m x_i y_i \oplus h(y). $$

The Walsh transform is

$$ s(u,v)=\sum_{x,y} (-1)^{f(x,y)+u\cdot x+v\cdot y}. $$

Summing over $x$,

$$ \sum_{x_i\in{0,1}} (-1)^{x_i(y_i+u_i)}= \begin{cases} 2 & y_i=u_i\ 0 & y_i\ne u_i. \end{cases} $$

Thus only $y=u$ contributes, giving

$$ s(u,v)=(-1)^{h(u)}2^m. $$

Hence $|s(u,v)|=2^{n/2}$ for all $(u,v)$, so $f$ is bent.

The form in the statement is equivalent by regrouping variables into pairs; this is exactly the Maiorana–McFarland construction.

(c) Autocorrelation characterization

Define

$$ C(y)=\sum_x (-1)^{f(x)\oplus f(x\oplus y)}. $$

A standard Fourier identity gives

$$ s(u)^2=\sum_y (-1)^{u\cdot y} C(y), \quad C(y)=2^{-n}\sum_u (-1)^{u\cdot y}s(u)^2. $$

If $f$ is bent, then $s(u)^2=2^n$, so

$$ C(y)=\sum_u (-1)^{u\cdot y}

\begin{cases} 2^n & y=0\ 0 & y\ne 0. \end{cases} $$

For $y\ne 0$,

$$ 0=\sum_x (-1)^{f(x)\oplus f(x\oplus y)} =2^n-2\sum_x (f(x)\oplus f(x\oplus y)), $$

$$ \sum_x (f(x)\oplus f(x\oplus y))=2^{n-1}. $$

The reverse implication follows by inverting the same transform.

(d) No monomial of degree $>n/2$

Let $f$ have algebraic normal form

$$ f(x)=\bigoplus_{T\subseteq [n]} c_T \prod_{i\in T} x_i. $$

Assume there exists a term $T=S$ with $|S|=r>n/2$. We derive a contradiction using the autocorrelation identity from (c).

Step 1: isolate the highest-degree term

Write

$$ f(x)=x_S \oplus g(x), $$

where $x_S=\prod_{i\in S} x_i$ and every monomial in $g$ has degree $<r$.

Fix $y=\mathbf{1}_S$, the vector that flips exactly the variables in $S$.

We study

$$ C(y)=\sum_x (-1)^{f(x)\oplus f(x\oplus y)}. $$

Step 2: contribution of the monomial $x_S$

For $m(x)=x_S$, observe:

If $x$ restricts to $S$ is not all ones, then both $m(x)=m(x\oplus y)=0$.
If $x$ has all ones on $S$, then $m(x)=1$ and $m(x\oplus y)=0$.

Hence exactly $2^{n-r}$ values of $x$ satisfy $m(x)=1$ and contribute a sign change.

A direct count gives

$$ \sum_x (-1)^{m(x)\oplus m(x\oplus y)} = 2^{n-r}-2^{n-r} = 0 \quad \text{except on structured pairs}, $$

and more precisely the correlation of the single monomial satisfies

$$ C_m(y)=\pm 2^{n-r+1}, $$

a nonzero integer multiple of $2^{n-r+1}$.

Step 3: contributions of lower-degree terms

Let $t(x)$ be any monomial of degree $d<r$. Then $t(x)\oplus t(x\oplus y)$ depends on at most $d$ coordinates of $S$, and standard counting shows its contribution to $C(y)$ is an integer multiple of

$$ 2^{n-d+1}, $$

hence of $2^{n-r+1}$ as well.

Therefore:

every term in the ANF contributes a multiple of $2^{n-r+1}$,
the highest-degree term contributes a nonzero multiple of $2^{n-r+1}$.

$$ C(y) \equiv C_m(y) \pmod{2^{n-r+1}},\quad C_m(y)\ne 0, $$

hence

$$ C(y)\ne 0. $$

Step 4: contradiction with bentness

From part (c), if $f$ is bent then for every $y\ne 0$,

$$ C(y)=0. $$

But for $y=\mathbf{1}_S\neq 0$, we have shown $C(y)\ne 0$. This contradiction implies that no such monomial $x_S$ with $|S|>n/2$ can exist.

Conclusion

(a) follows from Parseval and maximization of Walsh coefficients.
(b) is the standard Maiorana–McFarland construction.
(c) follows from Fourier inversion of the autocorrelation function.
(d) is resolved by isolating a maximal-degree monomial and showing it forces a nonzero autocorrelation value, contradicting the bent condition.

TAOCP 7.1.1 Exercise 132