A Boolean Function with Small Degree and Many Variables

Recently, while working on a research project, I got on a tangent. From this tangent, I got on another tangent and that is what I want to write about today: a very nice Boolean function. This example got rediscovered several times for different reasons and, as I try to emphasize from time, I believe that things that are getting rediscovered many times must be of particular importance.

So let us define our Boolean function. I will give three very similar definitions throughout this post, but I will start with only one. Put $ {\ell(d) := 3 \cdot 2^{d-1} – 2}$. Our Boolean function $ {F_d: \{ 0, 1\}^{\ell(d)} \rightarrow \{ 0, 1\}}$ is defined as follows: Put $ {F_1(x) = x}$ (as $ {\ell(1)=1}$). For $ {d > 1}$, write $ {x \in \{ 0, 1\}^{\ell(d)}}$ as $ {x=(s,t,y,z)}$ with $ {s,t \in \{ 0,1 \}}$ and $ {y, z \in \{ 0, 1\}^{\ell(d-1)}}$. Then use this rule:

• If $ {s=t=1}$, then $ {F_d(1,1,y,z) = F_{d-1}(y)}$.
• If $ {s \neq t=0}$, then $ {F_d(1,0,y,z) = F_{d-1}(z)}$.
• If $ {s= t = 0}$, then $ {F_d(0,0,y,z) = 1-F_{d-1}(y)}$.
• If $ {s \neq t = 1}$, then $ {F_d(0,1,y,z) = 1-F_{d-1}(z)}$.

In the following, we list some properties of this function. Many of the concepts here are also discussed in an earlier post of mine.

1. Equitable Bipartitions

One of my favorite hats to wear is that of a spectral graph theorist, so let us begin here. The hypercube $ {\{0,1\}^n}$ is often identified with the graph with $ {\{0,1\}^n}$ as vertices, two vertices adjacent when they have Hamming distance 1. As we will use this in a minute, let me mention that the eigenvalues of the hypercube (ignoring multiplicities) are $ {n, n-2, n-4, \ldots, -(n-4), -(n-2), -n}$. We start counting by $ {0}$, so $ {n, n-2, -n}$ are the $ {0}$th, $ {1}$st, and $ {n}$th eigenvalue.

For a $ {k}$-regular graph we say that a subset of vertices $ {Y}$ is an equitable bipartition (or regular set or perfect $ {2}$-coloring or intriguing set or one of many other words) if there exist constants $ {a,b}$ such that each vertex in $ {Y}$ has precisely $ {a}$ neighbors in $ {Y}$ and each vertex not in $ {Y}$ has precisely $ {b}$ neighbors in $ {Y}$. The quotient matrix of this structure is

$ \displaystyle \begin{pmatrix} a & k-a \\ b & k-b \end{pmatrix}. $

Its two eigenvalues are $ {k}$ and some other eigenvalue $ {\lambda}$ of the (real) adjacency matrix of $ {\Gamma}$. The characteristic function of $ {Y}$ lies in the subspace spanned by the eigenvectors with eigenvalue $ {k}$ and eigenvalue $ {\lambda}$.

Why do I write all of this? Because $ {F_d}$ is an example for this. Let $ {Y}$ denote the set of all $ {x \in \{ 0, 1 \}^{\ell(d)}}$ with $ {F_d(x)=1}$. Then its quotient matrix turns out to be

$ \displaystyle \begin{pmatrix} \ell(d)-d & d \\ d & \ell(d)-d \end{pmatrix}. $

Clearly, the eigenvalues of this matrix are $ {n = \ell(d)}$ and $ {n – 2d}$. Hence, $ {F_d}$ (seen as a real vector) lies in the subspace spanned by the eigenvectors belonging to the eigenvalues $ {n}$ and $ {n-2d}$, so the $ {0}$th and $ {d}$th eigenvalue in our ordering above (recall: we start counting with $ {0}$).

This observation goes back to Tarannikov (more on that below), but was phrased and defined slightly differently. Fon-der-Flaass was aware of the fact that $ {F_d}$ is an equitable bipartition of the hypercube in 2007 as he mentions it on page 742, lines 10–11, here.

2. Boolean Function Analysis

Now we pretend to be a theoretical computer scientist who works on the analysis of Boolean functions: Let us consider Boolean functions on $ {\{0,1\}^n}$ as polynomials over the real numbers and let us measure their degree as such. Later we also consider degrees over $ {\mathbb{F}_2}$, so let us denote the degree of a function $ {F}$ over the reals by $ {\deg(F)}$ and the degree over the binary field by $ {\deg_2(F)}$.

In a famous paper, Nisan and Szegedy showed that a Boolean function $ {F}$ with $ {\deg(F) = d}$ has at most $ {d \cdot 2^{d-1}}$ relevant variables. They also constructed an example with $ {2^d-1}$ relevant variables. In a breakthrough result in 2020, Chiarelli, Hatami and Saks improved the upper bound to $ {6.614 \cdot 2^d}$ and later Wellens improved it further to $ {4.416 \cdot 2^d}$. But what is important for us here is that Chiarelli, Hatami and Saks also improved the lower bound to $ {3 \cdot 2^{d-1}-2}$ (they also mention that Shinkar and Tal found the same).

Now this number looks familiar. And indeed, it is the same construction as above. But why does it have degree $ {d}$ and depends on all variables? Instead of using the Boolean set $ {\{ 0, 1\}}$, let us use $ {\{-1, 1\}}$ for a moment. Define $ {G_d: \{ -1, 1\}^{\ell(d)} \rightarrow \{ -1, 1\}}$ as follows: Put $ {G_1(x) = x}$. Clearly, $ {G_1}$ has degree $ {1}$. Further (using the same notation as before), put

$ \displaystyle G_d(s,t,y,z) = \frac{s+t}{2} G_{d-1}(y) + \frac{s-t}2 G_{d-1}(z). $

It is easy to see that $ {F_d}$ and $ {G_d}$ are actually the same (up to our change in the underlying Boolean set). Clearly, $ {G_d}$ depends on all its $ {\ell(d)}$ variables. As $ {G_{d-1}}$ has degree $ {d-1}$, $ {G_d}$ will have degree $ {d}$. But that we already knew that: the function $ {F_d}$ lies in the subspace spanned by the first $ {d}$ eigenspaces of the hypercube which is the same as being of degree $ {d}$. See also here.

3. Cryptographic Boolean Functions

Lastly, let us take the point of view of someone in the theory of cryptography. Here we consider Boolean functions on $ {\{0,1\}^n}$ as polynomials over the field with two elements $ {\mathbb{F}_2}$ (or, maybe easier: all our calculations are modulo 2). To make things (hopefully) slightly less confusing, I will write $ {\oplus}$ for addition in $ {\mathbb{F}_2}$.

In this paper by Carlet and Tarannikov from 2002, a certain type of Boolean functions is studied. In their introduction, they explain 4 different properties that a Boolean function $ {F}$ used in cryptography should have:

• Balancedness: The function $ {F}$ should take values $ {0}$ and $ {1}$ equally often. Otherwise an attacker can simply guess $ {F(x)}$ with a chance larger than $ {0.5}$.
• Correlation-immunity/Resiliency: There are already many places on the internet that explain this far better than I could. For the sake of self-containment: We say that $ {F}$ is $ {k}$th order correlation-immune if $ {F(x) \oplus G(x)}$ is balanced for all non-constant affine functions $ {G}$ with at most $ {k}$ relevant variables. If $ {F}$ is also balanced, then $ {F}$ is called $ {k}$-resilient.
• Nonlinearity: $ {F}$ must be at large Hamming distance from all affine functions.
• Algebraic Degree: $ {\deg_2(F)}$ must be large. Otherwise, it is easy to guess $ {F}$ as there not many Boolean functions of small degree.

Carlet and Tarannikov study a certain class of functions which are (usually) balanced and resilient, but can also satisfy the other criteria: $ {d}$-regular functions. As I do not want to reproduce large parts of their paper here, I will not explain any of that. Instead, let me paraphrase their Theorem 12:

Theorem 12 (paraphrased) There exists a $ {d}$-regular nondegenerate Boolean function $ {H_d}$ on $ {\mathbb{F}_2^{\ell(d)}}$ with highest possible nonlinearity and $ {\deg_2(H_d) = d}$.

How do they define their function? (I took the liberty to relabel some indices, so that it is more similar to $ {F_d}$ and $ {G_d}$.) Start with

$ \displaystyle H_2(x_1, x_2, x_3, x_4) = x_1 \oplus x_2 \oplus (x_1 \oplus x_3)(x_2 \oplus x_4). $

Also $ {H_2}$ and $ {F_2}$ are not exactly the same, but there are simply many ways for starting such a recursive definition.

Continue with

$ \displaystyle H_d(s,t,y,z) = s \oplus (s \oplus t \oplus 1) H_{d-1}(y) \oplus (s \oplus t) H_{d-1}(z). $

Our recursive rule is slightly off compared to $ {F_d}$ or $ {G_d}$: For instance, $ {H_d(1,1,y,z) = 1 \oplus H_{d-1}(y)}$, but $ {F_d(1,1,y,z) = F_{d-1}(y)}$. But we could amend this by adding $ {1}$ in the recursive rule:

$ \displaystyle H_d(s,t,y,z) = 1 \oplus s \oplus (s \oplus t \oplus 1) H_{d-1}(y) \oplus (s \oplus t) H_{d-1}(z). $

Let me end with some terminology. Claude Carlet calls the a Boolean function $ {F}$ written as a polynomial over $ {\mathbb{F}_2}$ as the Algebraic Normal Form (ANF), while he denotes it written as a polynomial over the real numbers as Numerical Normal Form (NNF). Clearly, in general $ {\deg_2(F) \leq \deg(F)}$. The fact that $ {\deg_2(F_d) = d = \deg(F_d)}$ is in general not true. Update 06/10/2022: But it is true for the special case which we care about here. For instance, this follows from the remark after Proposition 6.23 in Ryan O’Donnell’s book.

4. More Occurrences?

Does this function appear in more contexts? Was it discovered by others? I am curious. Please let me know in the comments!

Acknowledgements I thank Yuval Filmus, Alexander L. Gavrilyuk, Yuriy Tarannikov, and, most importantly, Konstantin Vorob’ev for facilitating my literature study on this topic.

Update, 06 October 2022: Yuriy Tarannikov investigated the matter further and informed me (already some time ago) about it. Maybe there are two things to be pointed out. Firstly, he reproved the Nisan-Szegedy bound of $ d\cdot 2^{d-1}$ in 2001 here together with Peter Korolov and Anton Botev. Secondly, the precise bound for $ d=2$ is 4 and all examples can be found in this article by Camion, Carlet, Charpin and Sendrier. The precise bound for $ d=3$ is 10 as was shown Yuriy’s students, for instance in Alexander Zverev, On the Structure of the Spectrum Support of Boolean Functions, Boolean Functions in Cryptology and Information Security, NATO Science for Peace and Security Series D Information and Communication Security, Volume 18, 2007.