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 . Our Boolean function is defined as follows: Put (as ). For , write as with and . Then use this rule:
- If , then .
- If , then .
- If , then .
- If , then .
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 is often identified with the graph with 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 . We start counting by , so are the th, st, and th eigenvalue.
For a -regular graph we say that a subset of vertices is an equitable bipartition (or regular set or perfect -coloring or intriguing set or one of many other words) if there exist constants such that each vertex in has precisely neighbors in and each vertex not in has precisely neighbors in . The quotient matrix of this structure is
Its two eigenvalues are and some other eigenvalue of the (real) adjacency matrix of . The characteristic function of lies in the subspace spanned by the eigenvectors with eigenvalue and eigenvalue .
Why do I write all of this? Because is an example for this. Let denote the set of all with . Then its quotient matrix turns out to be
Clearly, the eigenvalues of this matrix are and . Hence, (seen as a real vector) lies in the subspace spanned by the eigenvectors belonging to the eigenvalues and , so the th and th eigenvalue in our ordering above (recall: we start counting with ).
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 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 as polynomials over the real numbers and let us measure their degree as such. Later we also consider degrees over , so let us denote the degree of a function over the reals by and the degree over the binary field by .
In a famous paper, Nisan and Szegedy showed that a Boolean function with has at most relevant variables. They also constructed an example with relevant variables. In a breakthrough result in 2020, Chiarelli, Hatami and Saks improved the upper bound to and later Wellens improved it further to . But what is important for us here is that Chiarelli, Hatami and Saks also improved the lower bound to (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 and depends on all variables? Instead of using the Boolean set , let us use for a moment. Define as follows: Put . Clearly, has degree . Further (using the same notation as before), put
It is easy to see that and are actually the same (up to our change in the underlying Boolean set). Clearly, depends on all its variables. As has degree , will have degree . But that we already knew that: the function lies in the subspace spanned by the first eigenspaces of the hypercube which is the same as being of degree . 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 as polynomials over the field with two elements (or, maybe easier: all our calculations are modulo 2). To make things (hopefully) slightly less confusing, I will write for addition in .
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 used in cryptography should have:
- Balancedness: The function should take values and equally often. Otherwise an attacker can simply guess with a chance larger than .
- 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 is th order correlation-immune if is balanced for all non-constant affine functions with at most relevant variables. If is also balanced, then is called -resilient.
- Nonlinearity: must be at large Hamming distance from all affine functions.
- Algebraic Degree: must be large. Otherwise, it is easy to guess 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: -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 -regular nondegenerate Boolean function on with highest possible nonlinearity and .
How do they define their function? (I took the liberty to relabel some indices, so that it is more similar to and .) Start with
Also and are not exactly the same, but there are simply many ways for starting such a recursive definition.
Our recursive rule is slightly off compared to or : For instance, , but . But we could amend this by adding in the recursive rule:
Let me end with some terminology. Claude Carlet calls the a Boolean function written as a polynomial over 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 . The fact that 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 in 2001 here together with Peter Korolov and Anton Botev. Secondly, the precise bound for is 4 and all examples can be found in this article by Camion, Carlet, Charpin and Sendrier. The precise bound for 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.