§6.2: ${\mathbb F}_2$-polynomials

We began our study of boolean functions in Chapter 1.2 by considering their polynomial representations over the real field. In this section we take a brief look at their polynomial representations over the field ${\mathbb F}_2$, with $\mathsf{False}$, $\mathsf{True}$ being represented by $0, 1 \in {\mathbb F}_2$ as usual. Note that in the field ${\mathbb F}_2$, the arithmetic operations $+$ and $\cdot$ correspond to logical XOR and logical AND, respectively.

Example 17 Consider the logical parity (XOR) function on $n$ bits, $\chi_{[n]}$. To represent it over the reals (as we have done so far) we encode $\mathsf{False}, \mathsf{True}$ by $\pm 1 \in {\mathbb R}$; then $\chi_{[n]} : \{-1,1\}^n \to \{-1,1\}$ has the polynomial representation $\chi_{[n]}(x) = x_1 x_2 \cdots x_n$. Suppose instead we encode $\mathsf{False}, \mathsf{True}$ by $0, 1 \in {\mathbb F}_2$; then $\chi_{[n]} : {\mathbb F}_2^n \to {\mathbb F}_2$ has the polynomial representation $\chi_{[n]}(x) = x_1 + x_2 + \cdots + x_n$. Notice this polynomial has degree $1$, whereas the representation over the reals has degree $n$.

In general, let $f : {\mathbb F}_2^n \to {\mathbb F}_2$ be any boolean function. Just as in Chapter 1.2 we can find a (multilinear) polynomial representation for it by interpolation. The indicator function $1_{\{a\}} : {\mathbb F}_2^n \to {\mathbb F}_2$ for $a \in {\mathbb F}_2^n$ can be written as \begin{equation} \label{eqn:interp-f2-a} 1_{\{a\}}(x) = \prod_{i : a_i = 1} x_i \prod_{i : a_i = 0}(1-x_i), \end{equation} a degree-$n$ multilinear polynomial. (We could have written $1+x_i$ rather than $1-x_i$ since these are the same in ${\mathbb F}_2$.) Hence $f$ has the multilinear polynomial expression \begin{equation} \label{eqn:interp-f2-b} f(x) = \sum_{a \in {\mathbb F}_2^n} f(a)1_{\{a\}}(x). \end{equation} After simplification, this may be put in the form \begin{equation} \label{eqn:f2-poly-rep} f(x) = \sum_{S \subseteq [n]} c_S x^S, \end{equation} where $x^S = \prod_{i \in S} x_i$ as usual, and each coefficient $c_S$ is in ${\mathbb F}_2$. We call \eqref{eqn:f2-poly-rep} the ${\mathbb F}_2$-polynomial representation of $f$. As an example, if $f = \chi_{}$ is the parity function on $3$ bits, its interpolation is \begin{align} \chi_{}(x) &= (1-x_1)(1-x_2)x_3 + (1-x_1)x_2(1-x_3) + x_1(1-x_2)(1-x_3) + x_1x_2x_3 \nonumber\\ &= x_1 + x_2 + x_3 -2(x_1x_2 + x_1 x_3 + x_2 x_3) + 4x_1x_2x_3 \label{eqn:chi3Z}\\ &= x_1 + x_2 + x_3 \nonumber \end{align} as expected. We also have uniqueness of the ${\mathbb F}_2$-polynomial representation; the quickest way to see this is to note that there are $2^{2^n}$ functions ${\mathbb F}_2^n \to {\mathbb F}_2$ and also $2^{2^n}$ possible choices for the coefficients $c_S$. Summarizing:

Proposition 18 Every $f : {\mathbb F}_2^n \to {\mathbb F}_2$ has a unique ${\mathbb F}_2$-polynomial representation as in \eqref{eqn:f2-poly-rep}.

Examples 19 The logical AND function $\mathrm{AND}_n : {\mathbb F}_2^n \to {\mathbb F}_2$ has the simple expansion $\mathrm{AND}_n(x) = x_1 x_2 \cdots x_n$. The inner product mod $2$ function has the degree-$2$ expansion $\mathrm{IP}_{2n}(x_1, \dots, x_n, y_1, \dots, y_n) = x_1y_1 + x_2y_2 + \cdots + x_ny_n$.

Since the ${\mathbb F}_2$-polynomial representation is unique we may define ${\mathbb F}_2$-degree:

Definition 20 The ${\mathbb F}_2$-degree of a boolean function $f : \{\mathsf{False}, \mathsf{True}\}^n \to \{\mathsf{False}, \mathsf{True}\}$, denoted $\deg_{{\mathbb F}_2}(f)$, is the degree of its ${\mathbb F}_2$-polynomial representation. We reserve the notation $\deg(f)$ for the degree of $f$’s Fourier expansion.

We can also give a formula for the coefficients of the ${\mathbb F}_2$-polynomial representation:

Proposition 21 Suppose $f : {\mathbb F}_2^n \to {\mathbb F}_2$ has ${\mathbb F}_2$-polynomial representation $f(x) = \sum_{S \subseteq [n]} c_S x^S$. Then $c_S = \sum_{\mathrm{supp}(x) \subseteq S} f(x)$.

Corollary 22 Let $f : \{\mathsf{False}, \mathsf{True}\}^n \to \{\mathsf{False}, \mathsf{True}\}$. Then $\deg_{{\mathbb F}_2}(f) = n$ if and only if $f(x) = \mathsf{True}$ for an odd number of inputs $x$.

The proof of Proposition 21 is left for the exercises; Corollary 22 is just the case $S = [n]$. You can also directly see that $c_{[n]} = \sum_x f(x)$ by observing what happens with the monomial $x_1x_2 \cdots x_n$ in the interpolation \eqref{eqn:interp-f2-a},\eqref{eqn:interp-f2-b}.

Given a generic boolean function $f : \{\mathsf{False}, \mathsf{True}\}^n \to \{\mathsf{False}, \mathsf{True}\}$ it’s natural to ask about the relationship between its Fourier expansion (i.e., polynomial representation over ${\mathbb R}$) and its ${\mathbb F}_2$-polynomial representation. In fact you can easily derive the ${\mathbb F}_2$-representation from the ${\mathbb R}$-representation. Suppose $p(x)$ is the Fourier expansion of $f$; i.e., $f$’s ${\mathbb R}$-multilinear representation when we interpret $\mathsf{False}$, $\mathsf{True}$ as $\pm 1 \in {\mathbb R}$. From Exercise 1.10, $q(x) = \tfrac{1}{2} – \tfrac{1}{2} p(1-2x_1, \dots, 1-2x_n)$ is the unique ${\mathbb R}$-multilinear representation for $f$ when we interpret $\mathsf{False}$, $\mathsf{True}$ as $0, 1\in {\mathbb R}$. But we can also obtain $q(x)$ by carrying out the interpolation in \eqref{eqn:interp-f2-a}, \eqref{eqn:interp-f2-b} over ${\mathbb Z}$. Thus the ${\mathbb F}_2$ representation of $f$ is obtained simply by reducing $q(x)$’s (integer) coefficients modulo $2$.

We saw an example of this derivation above with $\chi_{}$. The $\pm 1$-representation is $x_1x_2x_3$. The representation over $\{0,1\} \in {\mathbb Z} \subseteq {\mathbb R}$ is $\tfrac{1}{2} – \tfrac{1}{2} (1-2x_1)(1-2x_2)(1-2x_3)$, which when expanded equals \eqref{eqn:chi3Z} and has integer coefficients. Finally, we obtain the ${\mathbb F}_2$ representation $x_1+x_2+x_3$ by reducing the coefficients of \eqref{eqn:chi3Z} modulo $2$.

One thing to note about this transformation from Fourier expansion to ${\mathbb F}_2$-representation is that it can only decrease degree. As noted in Exercise 1.12, the first step, forming $q(x) = \tfrac{1}{2} – \tfrac{1}{2} p(1-2x_1, \dots, 1-2x_n)$, does not change the degree at all (except if $p(x) \equiv 1$, $q(x) \equiv 0$). And the second step, reducing $q$’s coefficients modulo $2$, cannot increase the degree. We conclude:

Proposition 23 Let $f : \{-1,1\}^n \to \{-1,1\}$. Then $\deg_{{\mathbb F}_2}(f) \leq \deg(f)$.

Here is an interesting consequence of this proposition. Suppose $f : \{-1,1\}^n \to \{-1,1\}$ is $k$-resilient; i.e., $\widehat{f}(S) = 0$ for all $|S| \leq k < n$. Let $g = \chi_{[n]} \cdot f$; thus $\widehat{g}(S) = \widehat{f}([n] \setminus S)$ and hence $\deg(g) \leq n-k-1$. From Proposition 23 we deduce $\deg_{{\mathbb F}_2}(g) \leq n-k-1$. But if we interpret $f, g : {\mathbb F}_2^n \to {\mathbb F}_2$ then $g = x_1 + \cdots + x_n + f$ and hence $\deg_{{\mathbb F}_2}(g) = \deg_{{\mathbb F}_2}(f)$ (unless $f$ is parity or its negation). Thus:

Proposition 24 Let $f : \{-1,1\}^n \to \{-1,1\}$ be $k$-resilient, $k < n-1$. Then $\deg_{{\mathbb F}_2}(f) \leq n-k-1$.

This proposition was shown by Siegenthaler, a cryptographer who was studying stream ciphers; his motivation is discussed further at the end of this chapter. More generally, Siegenthaler proved the following result (the proof does not require Fourier analysis):

Siegenthaler’s Theorem Proposition 24 holds. Further, if $f$ is merely $k$th-order correlation immune then we still have $\deg_{{\mathbb F}_2}(f) \leq n-k$ (for $k < n$).

Proof: Pick a monomial $x^J$ of maximal degree $d = \deg_{{\mathbb F}_2}(f)$ in $f$’s ${\mathbb F}_2$-polynomial representation; we may assume $d > 1$ else we are done. Make an arbitrary restriction to the $n-d$ coordinates outside of $J$, forming function $g : {\mathbb F}_2^J \to {\mathbb F}_2$. The monomial $x^J$ still appears in $g$’s ${\mathbb F}_2$-polynomial representation; thus by Corollary 22, $g$ is $1$ for an odd number of inputs.

Let us first show Proposition 24. Assuming $f$ is $k$-resilient, it is unbiased. But $g$ is $1$ for an odd number of inputs so it cannot be unbiased (since $2^{d-1}$ is even for $d > 1$). Thus the restriction changed $f$’s bias and we must have $n-d > k$, hence $d \leq n-k-1$.

Suppose now $f$ is merely $k$th-order correlation immune. Pick an arbitrary input coordinate for $g$ and suppose its two possible restrictions give subfunctions $g_0$ and $g_1$. Since $g$ has an odd number of $1$’s, one of $g_0$ has an odd number of $1$’s and the other has an even number. In particular, $g_0$ and $g_1$ have different biases. One of these biases must differ from $f$’s. Thus $n-d+1 > k$, hence $d \leq n-k$. $\Box$

We end this section by mentioning another bound related to correlation immunity:

Theorem 25 Suppose $f : \{-1,1\}^n \to \{-1,1\}$ is $k$th-order correlation immune but not $k$-resilient (i.e., $\mathop{\bf E}[f] \neq 0$). Then $k +1 \leq \frac{2}{3}n$.

The proof of this theorem (left to the exercises) uses the Fourier expansion rather than the ${\mathbb F}_2$-representation. The bounds in both Siegenthaler’s Theorem and Theorem 25 can be sharp in many cases; this is also explored in the exercises.

4 comments to §6.2: ${\mathbb F}_2$-polynomials

• Karl Wimmer

Corollary 22: “if and if” -> “if and only if”

• Ryan O'Donnell

Thanks Karl!

• Sivakanth Gopi

In equation (2), I think it should be f(a) inside the summation.

• Ryan O'Donnell

Of course, yep. Thanks!