Quasi-Random Influences of Boolean Functions

We consider Boolean Functions that map binary strings of length $n$ to $\{\textit{True},\textit{False}\}$. As boolean functions can encode a wide variety of mathematical and computational objects, such as decision problems, error-correcting codes, communication and cryptographic protocols, voting rules, propositional formulas, and arbitrary subsets of the set of binary strings, these functions are extremely well-studied in computer science, coding theory, cryptography, and data sciences to name a few areas of applications. For each application, many researchers have developed tools and perspectives unique to each area to study these boolean functions and have isolated key properties of boolean functions, for instance as the sensitivity of the function to changes in each coordinate, the size of its Fourier coefficients, or the distance of its support viewed as a binary code.

The goal of this paper is to organize some of these properties of boolean functions into a hierarchy of quasi-random equivalence classes in the same style as the quasi-random equivalence for graphs proven by Chung, Graham, and Wilson in [1] (for details, see section §3). In our main theorem, we show how a number of known analytic properties of boolean functions, such as the $k$-th order strict avalanche criterion, restrictions of the function having small Fourier coefficients, and discrepancy of the Fourier coefficients, can be either strengthened or weakened so as to become equivalent to one another in the same sense as in [1]. Motivated by the enumeration of “sub-patterns” within a larger object, we further show that several combinatorial properties of graphs built from our boolean function are equivalent to these analytic properties. These combinatorial properties include counts of rainbow embeddings of graphs and a co-degree condition on graphs defined from the boolean function. Finally, we give an explicit construction of a family of boolean functions which exhibits the properties in our main theorem. As it turns out, our construction depends crucially on the existence of good binary codes.

Our work continues the study of quasi-randomness of graphs and hypergraphs in the work of Chung, Graham, and Wilson [1]. Quasi-randomness theorems exist for other combinatorial objects, including Griffiths’ results on oriented graphs [2], Cooper’s work on permutations [3], Chung and Graham’s work on tournaments [4] and subsets of $\mathbb{Z}/N\mathbb{Z}$ [5], $k$-uniform linear Hypergraphs in works of Freidman and Widgerson [6] along with Rödl, Schacht, and Kohawakaya [7] and finally Lenz and Mubayi [8], and $k$-uniform general hypergraphs in papers of Chung and Graham [9, 10, 11, 12], Frankl, Rödl, Schacht, Kohawakaya, and Nagle in [13, 14, 15, 16, 17], surveyed in the papers of Gowers [18, 19]. There are also several extant theories of quasi-randomness for boolean functions, implicitly in Chung and Graham’s work on subsets of $\mathbb{Z}/N\mathbb{Z}$ [5] and explicitly in O’Donnell’s textbook [20], Castro-Silva’s monograph [21], and Chung and Tetali’s work on communication complexity [22]. We shall later prove that our theory of quasi-random boolean functions is distinct from each of these theories and is stronger than several of these theories and incomparable with the others.

Our paper is organized as follows. In section §2, we give the necessary preliminaries to state our quasi-random properties. Then we define the quasi-random properties and present our main results in section §3. We define the properties in extant theories of quasi-randomness for boolean functions in section §4. The main results of this paper are summarized in two flowcharts as seen in Figures 4 and 5. The proof of our main equivalence theorem appears in section §5, followed by the construction of our quasi-random functions in section §6. We then prove our comparison theorems which place our theory of quasi-randomness relative to several extant theories in section §7. Finally, we conclude with some remarks and open problems in section §8.

We refer the reader to O’Donnell’s book [20] for any undefined terminology. We identify the set of binary strings $\{0,1\}^{n}$ with elements of $\mathbb{F}_{2}^{n}$ via a choice of basis for $\mathbb{F}_{2}^{n}$, and then define a boolean function to be a map $f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\{1,-1\}$. We then equip the space of all maps $g\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\mathbb{C}$ with the following inner product:

$$\langle f,g\rangle\mathrel{\mathop{\ordinarycolon}}=\operatorname{\mathbb{E}}_{x\in\mathbb{F}_{2}^{n}}f(x)\overline{g(x)}=\frac{1}{2^{n}}\sum_{x\in\mathbb{F}_{2}^{n}}f(x)\overline{g(x)}$$

where $\overline{z}$ denotes complex conjugation of $z\in\mathbb{C}$. For each $\gamma\in\mathbb{F}_{2}^{n}$, the Fourier character $\chi_{\gamma}\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\{1,-1\}$ is

$$\chi_{\gamma}(x)\mathrel{\mathop{\ordinarycolon}}=(-1)^{\gamma\cdot x}$$

where $\gamma\cdot x\mathrel{\mathop{\ordinarycolon}}=\sum_{i=1}^{n}\gamma_{i}x_{i}$ is the usual dot product. The Fourier characters are an orthonormal basis for the space of all maps $g\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\mathbb{C}$ with the inner product as defined above. Therefore, every function $g\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\mathbb{C}$ has unique Fourier coefficients $\widehat{g}\left(\gamma\right)$ where $\widehat{f}\left(\gamma\right)=\langle g,\chi_{\gamma}\rangle$. The convolution of two functions $g\text{ and }h\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\mathbb{C}$ is

$$(g*h)(x)\mathrel{\mathop{\ordinarycolon}}=\operatorname{\mathbb{E}}_{y\in\mathbb{F}_{2}^{n}}f(x+y)\overline{g(y)}.$$

Note that $\widehat{g*h}\left(\gamma\right)=\widehat{g}\left(\gamma\right)\widehat{h}\left(\gamma\right)$.

We will also need to track the size of individual vectors in $\mathbb{F}_{2}^{n}$. For a vector $x\in\mathbb{F}_{2}^{n}$, its Hamming weight, denoted $|x|$, is $\mathinner{\!\left\lvert\{i\in[n]\mathrel{\mathop{\ordinarycolon}}x_{i}=1\}\right\rvert}$. Similarly, the Hamming distance between two vectors $x\text{ and }y\in\mathbb{F}_{2}^{n}$ is $\mathinner{\!\left\lvert x-y\right\rvert}$. For a subset $S\subseteq\mathbb{F}_{2}^{n}$, its diameter is $\operatorname{diam}(S)\mathrel{\mathop{\ordinarycolon}}=\max_{x,y\in S}\mathinner{\!\left\lvert x-y\right\rvert}$. The Hamming ball of radius $d$ in $\mathbb{F}_{2}^{n}$ and centered at the vector $x\in\mathbb{F}_{2}^{n}$, denoted by $B_{d}(n,x)$, is $\{y\in\mathbb{F}_{2}^{n}\mathrel{\mathop{\ordinarycolon}}\mathinner{\!\left\lvert x-y\right\rvert}\leq d\}$.

For a proposition $P(x)$, let $[P(x)]\mathrel{\mathop{\ordinarycolon}}=\begin{cases}1&P(x)\\ 0&\neg P(x)\end{cases}$ denote the indicator function for $P(x)$. We will write $0$ for the zero vector in $\mathbb{F}_{2}^{n}$ throughout, and write $\mathbf{1}\in\mathbb{F}_{2}^{n}$ for the all-ones vector. If $\mathcal{S}$ is a distribution on a set $S$, and $P(x)$ is a proposition on the variable $x\in S$, then

$$\operatorname{\mathbb{P}}_{x\sim\mathcal{S}}\left[P(x)\right]$$

will denote the probability that $P(x)$ holds where $x$ is drawn from the distribution $\mathcal{S}$. Whenever we write the expectation or probability over a set, such as $\operatorname{\mathbb{E}}_{x\in\mathbb{F}_{2}^{n}}$, the expectation or probability is taken with respect to the uniform distribution.

Here we state the definitions concerning various aspects of Boolean functions that will be used later.

We describe a number of quasi-random properties of boolean functions. The properties involve two parameters, denoted by $d$ and $\epsilon$, where $\epsilon$ indicates the error bound and $d$ is often related to the rank or dimension of patterns or objects in the property. The proof of the equivalence of these properties is given in section §5.

If $f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\{1,-1\}$ is chosen uniformly at random, we expect that the $\gamma$-influence (see Definition 2.1) should be close to $\frac{1}{2}$. Our first quasirandom property formalizes that notion:

We remark that $INF(k,0)$ is also known as the $k$th-Order Avalanche Criterion as studied in cryptography [26].

For $f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\{1,-1\}$ drawn uniformly from all boolean functions, the expected spectral sample (see Definition 2.2) is $\frac{1}{2^{n}}$ on each vector in $\mathbb{F}_{2}^{n}$. In particular, the total weight of the uniform distribution on a subcube of dimension $n-k$ is exactly $2^{k-n}$. Our next quasi-random property states that $\mathcal{S}_{f}$ is not far from the uniform distribution on on subcubes.

One can think of this property as a form of “discrepancy” for the spectral sample.

Next, we have a counting property on subcubes via the notion of restricted functions (see Definition 2.3). As $f|_{S,z}$ is a map $\mathbb{F}^{d}\to\{1,-1\}$ for $\mathinner{\!\left\lvert S\right\rvert}=d$, we can consider its Fourier coefficients. The next quasi-random property states that these Fourier coefficients are quite small on average.

The next property states that we can control certain patterns in the restrictions of $f$.

Convolutions are closely related to influences, so we have an additional influences property pertaining to an average restricted function:

The next combinatorial property states that many pairs of vertices on one side of the bipartite Cayley graph $BC(f)$ of $f$ (see Definition 2.4) have the same number of shared neighbors.

Note that every bipartite Cayley graph has a symmetry which reverses its left and right parts, so we only need to consider the left part in the quasirandom property. We remark that the assumption that $\mathinner{\!\left\lvert\widehat{f}\left(0\right)\right\rvert}<\frac{1}{2}$ is required for Property 6 and the other combinatorial properties.

Our next property concerns the bipartite graph homomorphisms of a fixed bipartite graph with a fixed left map.

Our next combinatorial property considers embeddings into a the rainbow Hamming graph as defined in definitions 2.6 and 2.8.

For properties $P(d,\epsilon)$ and $Q(d,\epsilon)$, we say $P$ implies $Q$ with error bound $\delta$, denoted $P(d,\epsilon)\overset{\delta}{\implies}Q(d,\epsilon)$, if for every $d\geq 1$, every $\epsilon>0$, and every boolean function $f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\{1,-1\}$, there is a $\delta>0$ such that

$$P(d,\delta)\implies Q(d,\epsilon)\hskip 28.45274pt$$

where $\delta$ depends on $d$ and $\epsilon$ but not on the size of the domain of $f$. If

$$P(d,\epsilon)\overset{\delta_{1}}{\implies}Q(d,\epsilon)~{}~{}\text{and}~{}~{}Q(d,\epsilon)\overset{\delta_{2}}{\implies}P(d,\epsilon)$$

for some error bounds $\delta_{1}$ and $\delta_{2}$, we say that $P$ and $Q$ are equivalent. Our main result is as follows:

If a boolean function $f$ satisfies any one of these properties for some $d$ and $\epsilon$, we say that $f$ is quasi-random of rank $d$ with error bound $\epsilon$.

We can summarize the proof of our main result in figure 4, where each arrow is labeled with the relevant theorem and error bound.

One can easily observe that $P(d+1,\epsilon)\implies P(d,\epsilon)$ for each property $P$ and every $d$ and $\epsilon$. Our second main result shows that these inclusions are strict, i.e. that there are functions which are quasi-random of rank $d$ but not quasi-random of rank $d+1$.

There are various other quasi-randomness theorems for boolean functions implicitly or explicitly considered in several related ranging from hypergraphs to analysis of boolean functions. Here we compare the properties defined in Section §3 to an incomplete list of these extant theories.

We first consider Chung and Tetali’s work on the relationship between $k$-uniform hypergraphs and boolean functions in [22]. Their ideas also appear implicitly in the works of Gowers [18] on hypergraph regularity lemmas and Szemeredi’s Theorem, and in a survey paper by Casto-Silva [21]. These works convert a boolean function to a $k$-uniform hypergraph via the following construction. Given a boolean function $f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\{1,-1\}$, its Cayley Hypergraph $H$ has the vertex set $\mathbb{F}_{2}^{n}$ and choosing hyper-edges $\{x_{1},\dots,x_{k}\}\in E(H)\iff f(x_{1}+\dots+x_{k})=-1$. Via the Cayley hypergraph, these authors transfer the theory of quasi-randomness for uniform hypergraphs to boolean functions.

The central definition in these works is the following, which we state is a slightly non-traditional fashion:

We will typically use the following equivalent formula (see [27]):

$$\|f\|_{U(k)}=\left(\operatorname{\mathbb{E}}_{x\in\mathbb{F}_{2}^{n},M\in\mathbb{F}_{2}^{n\times k}}\prod_{v\in\mathbb{F}_{2}^{k}}f(x+Mv)\right)^{2^{-k}}.$$

The Gowers norms are a direct translation of the properties in [11, 22] which count even and odd octahedra in $k$-Uniform hypergraphs. For these theories, the key pseudorandom property is the following:

As shown in Castro-Silva’s monograph [21], $(\epsilon,k+1)$ $\mathbb{F}_{2}$-Regularity implies $(\epsilon,k)$ $\mathbb{F}_{2}$-Regularity, and the implication is strict. Hence, just as we have a hierarchy of quasirandom properties in our Theorem 3.3, we can view $(\epsilon,k)$ $\mathbb{F}_{2}$-Regularity as a similar hierarchy indexed by $k$. Furthermore, the $k+1$-st Gowers norm controls correlation of $f$ with functions of $\mathbb{F}_{2}$-degree at most $k$ as shown in [27]. Hence, we can say that the hierarchy is indexed by $\mathbb{F}_{2}$-degree.

We show the following Theorem whose proof is found in section §7:

O’Donnell presents several pseudorandom properties in [20] which center on the Fourier expansion defined in Section §2. The first pseudorandom property he mentions is the following:

One can easily verify that $(\epsilon,d+1)$ $\mathbb{R}$-regularity implies $(\epsilon,d)$ $\mathbb{R}$-regularity, and a Fourier character of $\chi_{\gamma}$ where $\mathinner{\!\left\lvert\gamma\right\rvert}=d+1$ shows that the implication is strict. Hence, just as we have a hierarchy of quasirandom properties in our Theorem 3.3, $(\epsilon,k)$ $\mathbb{R}$-Regularity can be viewed as having an increasing hierarchy of pseudorandom properties indexed by $k$. Furthermore, $(\epsilon,n)$ $\mathbb{R}$-regularity is equivalent to $(\epsilon,1)$ $\mathbb{F}_{2}$-regularity as is shown in Proposition 6.7 of [20].

We show the following Theorem whose proof can be found in section §7:

Another collection of pseudorandom properties of Boolean functions appears implicitly in Chung and Graham’s work on quasirandom subsets of $\mathbb{Z}/N\mathbb{Z}$ [5]. To apply their work to boolean functions, we can identify the set of binary strings with elements of $\mathbb{Z}/2^{n}\mathbb{Z}$. Then a boolean function can be identified with the set of elements of $\mathbb{Z}/2^{n}\mathbb{Z}$ on which it takes the value $-1$. Their key pseudorandom property is the following:

As shown by Chung and Graham [5], $\mathbb{Z}/2^{n}\mathbb{Z}$-Regularity controls the correlations of a function $f$ with a shifted copy of itself much like our Balanced Influences Property (see 1). However, the arithmetic operations considered in $\mathbb{Z}/2^{n}\mathbb{Z}$-Regularity are carried out over $\mathbb{Z}/2^{n}\mathbb{Z}$ rather than $\mathbb{F}_{2}^{n}$ as in the Balanced Influences Property.

We prove the following Theorem whose proof is found in section §7:

O’Donnell [20] defines an additional pseudo-random property which uses a different generalization of influences as follows.

The key pseudorandom property is:

As shown by O’Donnell[20], $\rho$-Stable-Influences measure the expected change in the function if the input bits are changed via a particular noise model. Thus, $(\epsilon,\rho)$ Small Stable Influences implies a form of noise stability.

We show the following Theorem whose proof is found in section §7: