# Quasi-Random Influences of Boolean Functions

Fan Chung and Nicholas Sieger

###### Abstract

We examine a hierarchy of equivalence classes of quasi-random properties of
Boolean Functions. In particular, we prove an equivalence between a number of
properties including balanced influences, spectral discrepancy, local strong
regularity, homomorphism enumerations of colored or weighted graphs and
hypergraphs associated with Boolean functions as well as the $k$th-order
strict avalanche criterion amongst others. We further construct families of
quasi-random boolean functions which exhibit the properties of our equivalence
theorem and separate the levels of our hierarchy.

##  1 Introduction

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.

##  2 Preliminaries

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.

###  2.1 The influences of Boolean functions

The notion of “influences” is prominent in both analysis of boolean functions
and in cryptography.

######  Definition 2.1.

For $\gamma\in\mathbb{F}_{2}^{n}$, the $\gamma$-Influence of $f$ is

$\operatorname{I}_{\gamma}[f]\mathrel{\mathop{\ordinarycolon}}=\operatorname{\mathbb{P}}_{x\in\mathbb{F}_{2}^{n}}\left[f(x)\neq
f(x+\gamma)\right].$

Note that $\operatorname{I}_{0}[f]$ is always $0$. Furthermore, for
$\gamma\in\mathbb{F}_{2}^{n}$ with $\gamma_{i}=1$ and $\gamma_{j}=0$ for
$j\neq i$, $\operatorname{I}_{\gamma}[f]$ is precisely the influence of
coordinate $i$ as studied extensively in O’Donnell [20].

###  2.2 The spectral sampling of Boolean functions

Parseval’s Theorem states that for
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$

$\sum_{\gamma\in\mathbb{F}_{2}^{n}}\widehat{f}\left(\gamma\right)^{2}=\operatorname{\mathbb{E}}_{x\in\mathbb{F}_{2}^{n}}\left[f(x)^{2}\right]=1.$

Thus the Fourier coefficients of $f$ define a probability distribution on
$\mathbb{F}_{2}^{n}$ as follows:

######  Definition 2.2.

For a fixed boolean function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$, the
Spectral Sample $\mathcal{S}_{f}$ is the distribution on $\mathbb{F}_{2}^{n}$
where

$\operatorname{\mathbb{P}}_{\gamma\sim\mathcal{S}_{f}}\left[\gamma=\delta\right]=\widehat{f}\left(\delta\right)^{2}$

for a fixed $\delta\in\mathbb{F}_{2}^{n}$.

###  2.3 Subcubes and the counting of subcubes

Let $[n]$ denote the set $\\{1,\dots,n\\}$, and for $S\subseteq[n]$, let
$\overline{S}$ denote $[n]\setminus S$. Given a set $S\subseteq[n]$, and two
vectors $x\in\mathbb{F}_{2}^{S}$, $y\in\mathbb{F}_{2}^{\overline{S}}$, let
$x\underset{S}{\otimes}y$ denote the vector where

$(x\underset{S}{\otimes}y)_{i}=\begin{cases}x_{i}&i\in S\\\
y_{i}&i\in\overline{S}\end{cases}.$

The Subcube defined by a set $S\subseteq[n]$ and a vector
$z\in\mathbb{F}_{2}^{\overline{S}}$ is the set

$C(S,z)\mathrel{\mathop{\ordinarycolon}}=\\{x\underset{S}{\otimes}z\mathrel{\mathop{\ordinarycolon}}x\in\mathbb{F}_{2}^{S}\\}.$

We say that the dimension of a subcube $C(S,z)$ is $\mathinner{\\!\left\lvert
S\right\rvert}$. Note that $C([n],\eta)$ where $\eta$ is the empty string is
precisely the hypercube $Q_{n}$. In Figure 1, we have two examples of
subcubes. We are also concerned about boolean functions restricted to a
subcube:

######  Definition 2.3.

The restriction of
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ to the
subcube $C(S,z)$ is the boolean function
$f|_{S,z}\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{S}\to\\{1,-1\\}$
defined by

$f|_{S,z}(x)=f(x\underset{S}{\otimes}z)$

If $S=\emptyset$, then $f|_{S,z}(x)$ is the constant function $f(z)$, and if
$S=[n]$, then we recover $f$ itself.

$000$$001$$010$$100$$101$$011$$110$$111$ Figure 1: The blue dashed lines in
the figure indicate the $2$-dimensional subcube $C(\\{1,3\\},1)$, i.e. the set
of all length $3$ binary strings with a $1$ in the second coordinate. The red
dotted line indicates the $1$-dimensional subcube $C(\\{2\\},01)$.

###  2.4 Combinatorial aspects of Boolean functions

Here we give several useful combinatorial interpretations of Boolean functions
that are of interest of their own right. For two sets $A,B$, let
$A\hookrightarrow B$ denote the set of all injective functions from $A$ to
$B$. Let $A\sqcup B$ denote the disjoint union of the sets $A$ and $B$.

####  2.4.1 Bipartite Cayley Graphs

Given a bipartite graph $G=(U\sqcup V,E)$, we say $U$ is its left part,
denoted $L(G)$, and $V$ its right part, denoted $R(G)$. For $v\in V(G)$, let
$N_{G}(v)$ denote the neighborhood of $v$ in $G$.

######  Definition 2.4.

For a boolean function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$, the
bipartite Cayley graph of $f$, denoted $BC(f)$, is the bipartite graph on
vertex set $\mathbb{F}_{2}^{n}\sqcup\mathbb{F}_{2}^{n}$ where $u\sim v\iff
f(u+v)=-1$.

We observe that the number of edges in $BC(f)$ is exactly
$2^{2n}\operatorname{\mathbb{P}}_{x\in\mathbb{F}_{2}^{n}}[f(x)=-1]$. The
bipartite Cayley graph is associated to the Cayley graph with vertex set
$\mathbb{F}_{2}^{n}$ and edge set generated by
$\\{x\in\mathbb{F}_{2}^{n}\mathrel{\mathop{\ordinarycolon}}f(x)=-1\\}$. See
Figure 2 for a more explicit example of $BC(f)$.

$00$$01$$10$$11$$00$$10$$01$$11$ Figure 2: The bipartite Cayley graph,
$BC(g)$, of the function $g(z)=(-1)^{z_{1}+z_{2}}$ for
$z_{1},z_{2}\in\mathbb{F}_{2}$. $g$ encodes the XOR function on $2$ bits.

####  2.4.2 Embeddings and homomorphisms of bipartite subgraphs

We consider graph homomorphisms between bipartite graphs which preserve the
bipartition.

######  Definition 2.5.

A Bipartite Graph Homomorphism from $H=(U\sqcup V,F)$ to $G=(A\sqcup B,E)$ is
a pair of injective maps $(\psi,\phi)$ where
$\psi\mathrel{\mathop{\ordinarycolon}}U\to A$,
$\phi\mathrel{\mathop{\ordinarycolon}}V\to B$, and

$(u,v)\in F\implies(\psi(u),\phi(v))\in E.$

Note that we explicitly define our homomorphisms to be injective. The set of
all bipartite graph homomorphisms of a fixed bipartite graph $H$ into another
bipartite graph $G$ will be denoted by $BHOM(H,G)$. Let

$\operatorname{bhom}(H,G)\mathrel{\mathop{\ordinarycolon}}=\operatorname{\mathbb{E}}_{\psi\mathrel{\mathop{\ordinarycolon}}U\hookrightarrow
A}\operatorname{\mathbb{E}}_{\phi\mathrel{\mathop{\ordinarycolon}}V\hookrightarrow
B}\prod_{(u,v)\in F}[(\psi(u),\phi(v))\in E]$

denote the normalized size of $BHOM(H,G)$. We also consider bipartite graph
homomorphisms in which the left part is fixed by a particular injection
$\psi$. The set of all bipartite graph homomorphisms with a fixed left map
$\psi$ will be denoted by $BHOM_{\psi}(H,G)$. Let

$\operatorname{bhom}_{\psi}(H,G)\mathrel{\mathop{\ordinarycolon}}=\operatorname{\mathbb{E}}_{\phi\mathrel{\mathop{\ordinarycolon}}V\hookrightarrow
B}\prod_{(u,v)\in F}[(\phi(u),\psi(v))\in E]$

denote the normalized size of $BHOM_{\psi}(H,G)$. We say that an injection
$\psi$ has diameter at most $k$ if the image of $\psi$ is a set of diameter at
most $k$.

####  2.4.3 Colored multigraphs

The following definition is inspired by the work of Aharoni et al on rainbow
extremal problems [23].

######  Definition 2.6.

An edge-colored multigraph $M$ with color set $K$ is a multigraph with an
edge-coloring using colors in $K$ such that multiple edges between the
vertices $u$ and $v$ cannot have the same color.

We will typically think of the edges of an edge-colored multigraph as a subset
of $V\times V\times K$.

######  Definition 2.7.

For fixed $f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$,
$k\geq 1$, and $K\subseteq\mathbb{F}_{2}^{n}$, the rainbow Hamming graph
$RHG(k,f)$ is the colored multigraph on the vertex set $B_{k}(n,0)$ with color
set $K=\mathbb{F}_{2}^{n}$ and edge set defined as

$\\{(u,v,x)\in V\times V\times
K\mathrel{\mathop{\ordinarycolon}}f(u+x)=f(v+x)\\}.$

For an explicit example of a rainbow Hamming graph, see Figure 3.

$00$$01$$10$$00$$01$$10$$11$$11$$11$ Figure 3: The rainbow Hamming graph
$RHG(1,h)$ of the function $h(z)=(-1)^{1-z_{1}z_{2}}$ where
$z_{1},z_{2}\in\mathbb{F}_{2}$. Each edge is labeled by the string in
$\mathbb{F}_{2}^{2}$ which defines its color. Note that $h$ encodes the OR
function.

####  2.4.4 Rainbow embeddings

We consider graph homomorphisms into a colored multigraph which agree with the
coloring.

######  Definition 2.8.

Let $M$ be a colored multigraph with color set $K$ and let $G$ be a fixed
(simple) graph. A rainbow embedding of $G$ into $M$ is a injective coloring
$\chi\mathrel{\mathop{\ordinarycolon}}E(G)\to K$ and an injective map
$\phi\mathrel{\mathop{\ordinarycolon}}V(G)\to V(M)$ such that

$(u,v)\in E(G)\implies(\phi(u),\phi(v),\chi((u,v))\in E(M).$

These embeddings are also considered in the work of Alon and Marshall [24].

For a fixed graph $G$, a fixed colored multigraph $M$ with color set $K$, let

$\operatorname{em}(G,M)\mathrel{\mathop{\ordinarycolon}}=\operatorname{\mathbb{E}}_{\phi\mathrel{\mathop{\ordinarycolon}}V(G)\hookrightarrow
V(M)}\operatorname{\mathbb{E}}_{\chi\mathrel{\mathop{\ordinarycolon}}E(G)\hookrightarrow
K}\prod_{(u,v)\in E(G)}[(\phi(u),\phi(v),\chi((u,v)))\in E(M)]$

be the normalized count of rainbow embeddings of $G$ into $M$. If we
additionally fix the injection
$\phi\mathrel{\mathop{\ordinarycolon}}E(G)\hookrightarrow K$, let

$\operatorname{em}_{\phi}(G,M)\mathrel{\mathop{\ordinarycolon}}=\operatorname{\mathbb{E}}_{\chi\mathrel{\mathop{\ordinarycolon}}E(G)\hookrightarrow
K}\prod_{(u,v)\in E(G)}[(\phi(u),\phi(v),\chi((u,v)))\in E(M)]$

be the normalized count of rainbow embeddings with a fixed map $\phi$.

###  2.5 Bent Functions

We consider a specific class of boolean functions originally defined by
Rothaus [25].

######  Definition 2.9.

[25] For $n$ even, a boolean function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ is bent if

$\mathinner{\\!\left\lvert\widehat{f}\left(\gamma\right)\right\rvert}=2^{-n/2}$

for every $\gamma\in\mathbb{F}_{2}^{n}$.

Note that bent functions only exist for $n$ even.

We will need the following lemma:

######  Proposition 2.10.

[25] Let $g\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$
be bent. Then

$(g*g)(x)=[x=0].$

######  Example 2.11.

The Inner Product function
$IP\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{2m}\to\\{1,-1\\}$ is
defined by

$IP(z)\mathrel{\mathop{\ordinarycolon}}=(-1)^{\sum_{i=1}^{m}z_{i}z_{m+i}}=(-1)^{z_{1}\cdot
z_{2}}$

where $z_{1}$ is the first $m$ bits of $z$ and $z_{2}$ is the last $m$ bits of
$z$.

For the sake of completeness, we show that $IP$ is in fact a bent function. To
calculate its Fourier coefficients, fix $\gamma\in\mathbb{F}_{2}^{2m}$, and
let $\gamma_{1},\gamma_{2}\in\mathbb{F}_{2}^{m}$ denote the first $m$ bits of
$\gamma$ and the last $m$ bits respectively. For $x\in\mathbb{F}_{2}^{2m}$,
define $x_{1},x_{2}$ similarly. Then,

$\displaystyle\widehat{IP}\left(\gamma\right)$
$\displaystyle=\operatorname{\mathbb{E}}_{x\in\mathbb{F}_{2}^{2m}}IP(x)\chi_{\gamma}(x)$
$\displaystyle=\operatorname{\mathbb{E}}_{x_{1}\in\mathbb{F}_{2}^{m}}\operatorname{\mathbb{E}}_{x_{2}\in\mathbb{F}_{2}^{m}}(-1)^{x_{1}\cdot
x_{2}+\gamma_{1}\cdot x_{1}+\gamma_{2}\cdot x_{2}}$
$\displaystyle=\operatorname{\mathbb{E}}_{x_{1}\in\mathbb{F}_{2}^{m}}(-1)^{\gamma_{1}\cdot
x_{1}}\operatorname{\mathbb{E}}_{x_{2}\in\mathbb{F}_{2}^{m}}(-1)^{(x_{1}+\gamma_{2})\cdot
x_{2}}$
$\displaystyle=\operatorname{\mathbb{E}}_{x_{1}\in\mathbb{F}_{2}^{m}}(-1)^{\gamma_{1}\cdot
x_{1}}[x_{1}=\gamma_{2}]$ (1)
$\displaystyle=(-1)^{\gamma_{1}\cdot\gamma_{2}}2^{-m}$

where we use the fact that Fourier characters are orthogonal in line (1). Thus
$IP$ is a bent function.

##  3 Quasi-random Properties and the Main Results

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:

######  Property 1.

A boolean function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ with
$\mathinner{\\!\left\lvert\widehat{f}\left(0\right)\right\rvert}<\frac{1}{2}$
has the Balanced Influences Property $INF(k,\epsilon)$ if the
$\gamma$-Influence of $f$ is close to $\frac{1}{2}$ for every nonzero $\gamma$
in the Hamming ball of radius $k$ centered at $0$, i.e.

$\mathinner{\\!\left\lvert\operatorname{I}_{\gamma}[f]-\frac{1}{2}\right\rvert}<\epsilon$

for every $\gamma\neq\vec{0}$ in the Hamming ball of radius $k$ at $\vec{0}$.

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.

######  Property 2.

A boolean function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ with
$\mathinner{\\!\left\lvert\widehat{f}\left(0\right)\right\rvert}<\frac{1}{2}$
has the Spectral Discrepancy Property $SD(k,\epsilon)$ if the spectral sample
of $f$ has total weight close to $2^{l-n}$ on every subcube of dimension $l$
where $l\geq n-k$ i.e.

$\mathinner{\\!\left\lvert\operatorname{\mathbb{P}}_{z\sim\mathcal{S}_{f}}[z\in
H]-2^{\dim(C(S,z))-n}\right\rvert}<\epsilon$

for every subcube $H$ of dimension at least $n-k$.

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.

######  Property 3.

A boolean function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ with
$\mathinner{\\!\left\lvert\widehat{f}\left(0\right)\right\rvert}<\frac{1}{2}$
has the Restriction Fourier Property $RF(k,\epsilon)$ if the average
restriction of $f$ is nearly a bent function on any subcube of dimension at
most $k$, i.e.

$\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}\left[\widehat{f|_{S,z}}\left(\gamma\right)^{2}\right]-2^{-\dim(C(S,z))}\right\rvert}<\epsilon$

for every subcube $C(S,z)$ of dimension at most $k$ and every
$\gamma\in\mathbb{F}_{2}^{S}$.

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

######  Property 4.

A boolean function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ with
$\mathinner{\\!\left\lvert\widehat{f}\left(0\right)\right\rvert}<\frac{1}{2}$
has the Restriction Convolution Property $RC(k,\epsilon)$ if the average self-
convolution of restrictions of $f$ to subcubes of dimension at most $k$ is
close to the indicator function of the $0$ vector, i.e.

$\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}(f|_{S,z}*f|_{S,z})(x)-[x=\vec{0}]\right\rvert}<\epsilon$

for every set $S\subseteq[n]$ of size at most $k$.

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

######  Property 5.

A boolean function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ with
$\mathinner{\\!\left\lvert\widehat{f}\left(0\right)\right\rvert}<\frac{1}{2}$
has the Restriction Influences Property $RI(k,\epsilon)$ if the
$\gamma$-Influences of the average restriction to subcubes of dimension at
most $k$ are close to $\frac{1}{2}$.

$\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}\operatorname{I}_{\gamma}[f|_{S,z}]-\frac{1}{2}\right\rvert}<\epsilon$

for every set $S\subseteq[n]$ of size at most $k$ and every nonzero
$\gamma\in\mathbb{F}_{2}^{S}$.

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.

######  Property 6.

A boolean function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ with
$\mathinner{\\!\left\lvert\widehat{f}\left(0\right)\right\rvert}<\frac{1}{2}$
has the Local Strong Regularity Property $LSR(k,\epsilon)$ if the any pair of
vertices within distance $k$ of each other in the left part of the bipartite
Cayley graph of $f$ have approximately the same number of common neighbors,
i.e.

$\mathinner{\\!\left\lvert\frac{N_{BC(f)}(u)\cap
N_{BC(f)}(v)}{2^{n}}-\left(\frac{1}{4}-\frac{\widehat{f}\left(0\right)}{2}\right)\right\rvert}<\epsilon$

for every pair of vertices $x,y$ on the left side of $BC(f)$ such that
$\mathinner{\\!\left\lvert x-y\right\rvert}\leq k$.

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.

######  Property 7.

Define $p=\frac{1}{4}-\frac{\widehat{f}\left(0\right)}{2}$ and
$q=\frac{1}{2}-\frac{\widehat{f}\left(0\right)}{2}$. A boolean function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ with
$\mathinner{\\!\left\lvert\widehat{f}\left(0\right)\right\rvert}<\frac{1}{2}$
has the Degree $2$ Homomorphisms Property $DTH(k,\epsilon)$ if every bipartite
graph $G$ appears as a subgraph of $BC(f)$ as often as in a random bipartite
graph for any choice of left map for $G$ with diameter at most $k$, as long as
$G$ has maximum degree $2$ in its right part. More formally, the Degree-$2$
Homomorphisms Property holds if

$\mathinner{\\!\left\lvert\operatorname{bhom}_{\psi}(G,BC(f))-p^{r_{2}}q^{r_{1}}\right\rvert}<\epsilon
p^{r_{2}}q^{r_{1}}$

for every bipartite graph $G=(U\sqcup V,F)$ such that $V$ has maximum degree
$2$ in $G$ and $|V|\leq 2^{n/2}$, and every injection
$\psi\mathrel{\mathop{\ordinarycolon}}U\to\mathbb{F}_{2}^{n}$ of diameter at
most $k$ where $r_{2},r_{1}$ are the number of vertices in the right part of
$G$ with degree $2$ and $1$ respectively.

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

######  Property 8.

A boolean function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ with
$\mathinner{\\!\left\lvert\widehat{f}\left(0\right)\right\rvert}<\frac{1}{2}$
has the Rainbow Embeddings Property $RAIN(d,\epsilon)$ if for every fixed
simple graph $G$ and every choice of injection $\phi$ from $G$ to the rainbow
Hamming graph of $f$, there are close to $2^{-\mathinner{\\!\left\lvert
E(G)\right\rvert}}$ colorings of $G$ which become rainbow embeddings of $G$
under $\phi$. Namely, the Rainbow Embeddings Property holds if

$\mathinner{\\!\left\lvert\operatorname{em}_{\phi}(G,RHG(d,f))-2^{-\mathinner{\\!\left\lvert
E(G)\right\rvert}}\right\rvert}<\epsilon$

for every fixed graph $G$, and every
$\phi\mathrel{\mathop{\ordinarycolon}}V(G)\hookrightarrow V(RHG(d,f))$ of
diameter at most $d$.

######  Remark 3.1.

In Figure 3, consider the graph $K_{1,2}$ with the injection which sends the
left vertex to $00$ and the two right vertices to $01,10$. We note that there
are exactly $4$ possible edge-colorings of $K_{1,2}$ which become rainbow
embeddings under this injection. As there are $12$ possible colorings, it
follows that $OR$ does not satisfy the Rainbow Embeddings Property
$RAIN(d,\epsilon)$ for any $\epsilon<1/6$.

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:

######  Theorem 3.2.

For any fixed $d$ and $\epsilon$, the properties $INF(d,\epsilon)$(1),
$SD(d,\epsilon)$(2), $RF(d,\epsilon)$(3), $RC(d,\epsilon)$(4),
$RI(d,\epsilon)$(5), $LSR(d,\epsilon)$(6), $DTH(d,\epsilon)$(7), and
$RAIN(d,\epsilon)$(8) are equivalent.

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.

$INF(d,\epsilon)$$SD(d,\epsilon)$$RF(d,\epsilon)$$RC(d,\epsilon)$$RI(d,\epsilon)$$LSR(d,\epsilon)$$DTH(d,\epsilon)$$RAIN(d,\epsilon)$$\epsilon/2$Thm
(5.2)$\epsilon$Thm 5.4$\epsilon/2^{d}$Thm 5.5$\epsilon$Thm 5.6Thm
(5.7$\epsilon$$4\epsilon$Thm 5.8$4\epsilon$Thm 5.9$\epsilon
p/2e\mathinner{\\!\left\lvert D_{2}\right\rvert}$Thm
5.10$\epsilon\left(\frac{5}{2}+\widehat{f}\left(0\right)\right)^{-\mathinner{\\!\left\lvert
E(G)\right\rvert}}$Thm (5.12Thm 5.13$\epsilon/4$ Figure 4: The implications in
the main theorem (3.2). Each edge gives the loss in $\epsilon$ and the
reference to the theorem in which the implication is shown.

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$.

######  Theorem 3.3.

For each $d\geq 1$, there exists an explicit function
$f_{d}\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ with
$\mathinner{\\!\left\lvert\widehat{f}\left(0\right)\right\rvert}<\frac{1}{2}$
such that

  * •

$f_{d}$ satisfies the Balanced Influences Property of rank $d$ with error $0$.

  * •

$f_{d}$ does not satisfy the Balanced Influences Property of rank $d+1$ for
any bound $\epsilon<\frac{1}{2}$.

##  4 Relating Quasirandom Boolean Functions to Extant theories

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:

######  Definition 4.1.

The $k$-th Gowers Uniformity Norm, denoted $\|f\|_{U(k)}$, is defined as

$\|f\|_{U(k)}\mathrel{\mathop{\ordinarycolon}}=\left(\operatorname{\mathbb{E}}_{x\in\mathbb{F}_{2}^{n}}\operatorname{\mathbb{E}}_{v_{1},\dots,v_{k}\in\mathbb{F}_{2}^{n}}\prod_{\alpha_{1},\dots,\alpha_{k}\in\\{0,1\\}}f(x+\alpha_{1}v_{1}+\dots+\alpha_{k}v_{k})\right)^{2^{-k}}$

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:

######  Property 9.

A boolean function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ is
$(\epsilon,d)$ $\mathbb{F}_{2}$-Regular if

$\|f\|_{U(d+1)}<\epsilon$

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:

######  Theorem 4.2.

Let $f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ have
$(\epsilon,d)$-Balanced Influences. Then $f$ is $(\sqrt{2^{-d}+\epsilon},1)$
$\mathbb{F}_{2}$-Regular.

There is a function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ with
$(0,n)$-Balanced Influences, yet $f$ is not $(\epsilon,2)$
$\mathbb{F}_{2}$-Regular for any $\epsilon<1$.

For any $d\geq 2$, there is a function
$g\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ which is
$(\epsilon,d)$ $\mathbb{F}_{2}$-Regular and does not have the Balanced
Influences Property of any rank $k\geq 1$ for any error bound
$\epsilon<\frac{1}{2}$.

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:

######  Property 10.

A boolean function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ is
$(\epsilon,d)$ $\mathbb{R}$-Regular if

$\mathinner{\\!\left\lvert\widehat{f}\left(\gamma\right)\right\rvert}<\epsilon$

for every $\gamma\in\mathbb{F}_{2}^{n}$ with
$\mathinner{\\!\left\lvert\gamma\right\rvert}\leq d$.

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:

######  Theorem 4.3.

Let $f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ have
$(\epsilon,k)$ Balanced Influences. Then $f$ is $(\sqrt{2^{-k}+\epsilon},n)$
$\mathbb{R}$-regular.

Conversely, there is a function which is $(\epsilon,n)$ $\mathbb{R}$-regular
which does not have $(\epsilon,k)$ Balanced Influences for any rank $k\geq 1$
or error bound $\epsilon<\frac{1}{2}$.

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:

######  Property 11.

A boolean function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{Z}/2^{n}\mathbb{Z}\to\\{1,-1\\}$ is
$\mathbb{Z}/2^{n}\mathbb{Z}$-Regular with error bound $\epsilon$ if $f$ has
correlation at most $\epsilon$ with the all nonzero characters of
$\mathbb{Z}/2^{n}\mathbb{Z}$, i.e. for every nonzero
$j\in\mathbb{Z}/2^{n}\mathbb{Z}$,

$\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{z\in\mathbb{Z}/2^{n}\mathbb{Z}}f(z)\exp(2\pi
ijz/2^{n})\right\rvert}<\epsilon.$

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:

######  Theorem 4.4.

For any $\epsilon>0$ there is a function which is
$\mathbb{Z}/2^{n}\mathbb{Z}$-Regular with error bound $\epsilon$ but is not
$(\delta,n-k+1)$ $\mathbb{R}$-Regular for any $\delta<1$ where
$k=-C_{0}\ln(1/\epsilon)$ for some absolute constant $C_{0}$.

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

######  Definition 4.5.

For a coordinate $i$ and a parameter $\rho\in[0,1]$, the $\rho$-stable
influence of a boolean function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ is

$\operatorname{I}_{i}^{\rho}[f]\mathrel{\mathop{\ordinarycolon}}=\sum_{\begin{subarray}{c}\gamma\in\mathbb{F}_{2}^{n}\\\
\gamma_{i}=1\end{subarray}}\rho^{\mathinner{\\!\left\lvert\gamma\right\rvert}-1}\widehat{f}\left(\gamma\right)^{2}.$

The key pseudorandom property is:

######  Property 12.

A boolean function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ has
$(\epsilon,\rho)$ Small Stable Influences if

$\operatorname{I}_{i}^{\rho}[f]<\epsilon$

for every $i\in[n]$.

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:

######  Theorem 4.6.

Let $f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$
satisfy $SD(d,\epsilon e^{(d-1)((\delta/2)-\ln(2))})$. Then, $f$ has
$(\epsilon,\delta)$ small stable influences. Furthermore, $\chi_{\mathbf{1}}$
has $((1-\delta)^{n},\delta)$ small stable influences for any $\delta<1$ but
does not have $(\epsilon,k)$ Balanced Influences for any $k$ and any
$\epsilon<\frac{1}{2}$.

To summarize, we have figure 5 which includes the relationships between each
theory of quasirandomness and our results in Section §3.

$(\epsilon,d)$ $\mathbb{F}_{2}$-Regular, $d>1$$(\epsilon,1)$
$\mathbb{F}_{2}$-Regular$(\epsilon,\delta)$-Small Stable
Influences$\mathbb{Z}/2^{n}\mathbb{Z}$-Regularity$(\epsilon,k)$
$\mathbb{R}$-Regular, $k<n$$(\epsilon,d)$ Balanced Influences,
$d>0$BentTheorem 4.3Ex 6.5f [20]Theorem 4.6Ex 6.5d [20]Theorem 4.2Theorem
4.2Theorem 4.4 Figure 5: The relationships between different theories of
quasi-randomness. Each box is a distinct theory of quasi-randomness. Each
arrow is a strict implication. Beside each arrow we give a reference to the
proof of the implication. If the result follows by definition, we omit the
label for the sake of space. The results of this paper are in bold blue text
and blue arrows. Non-implications are red dotted lines with an $X$ in the
middle, with a citation for each result.

##  5 Proof of the Equivalences in Theorem 3.2

We now proceed to the proof of our main theorems. The following property of
the directional influence will be quite useful later.

######  Proposition 5.1.

If $\gamma\in\mathbb{F}_{2}^{n}$, then

$f*f(\gamma)=1-2\operatorname{I}_{\gamma}[f]$

###### Proof.

By definition of $\gamma$-influence,

$\displaystyle 1-2\operatorname{I}_{\gamma}[f]$
$\displaystyle=1-2\operatorname{\mathbb{P}}[f(x)\neq f(x+\gamma)]$
$\displaystyle=\operatorname{\mathbb{E}}_{x\in\mathbb{F}_{2}^{n}}\left(1-2[f(x)\neq
f(x+\gamma)]\right)$
$\displaystyle=\operatorname{\mathbb{E}}_{x\in\mathbb{F}_{2}^{n}}f(x)f(x+\gamma)$
$\displaystyle=f*f(\gamma)$

where we use the fact that $f(x)\in\\{1,-1\\}$ in the second and third
equalities. ∎

Our main Theorem 3.2 will be proved in a sequence of implications each of
which we state as a Theorem. The first Theorem in the proof of Theorem 3.2
relates the Balanced Influences Property to the Spectral Discrepancy Property.

######  Theorem 5.2.

For any fixed integer $d\geq 1$ and any $\epsilon>0$, the Balanced Influences
Property $INF(d,\epsilon/2)$ implies the Spectral Discrepancy Property
$SD(d,\epsilon)$.

###### Proof.

Fix a subcube $C(S,z_{0})$ where $\mathinner{\\!\left\lvert
S\right\rvert}=n-k$ where $k\leq d$. Let
$M\in\mathbb{F}_{2}^{\overline{S}\times[n]}$ be the projection matrix which
sends $z\in\mathbb{F}_{2}^{n}$ to $z|_{\overline{S}}$.

We observe that the indicator function $[\gamma\in C(S,z_{0})]$ can be written
as

$[\gamma\in
C(S,z_{0})]=\operatorname{\mathbb{E}}_{v\in\mathbb{F}_{2}^{\overline{S}}}(-1)^{v\cdot(M\gamma-
z_{0})}.$ (2)

Indeed, if $\gamma\in C(S,z_{0})$, then $M\gamma=z_{0}$, and
$\operatorname{\mathbb{E}}_{v\in\mathbb{F}_{2}^{\overline{S}}}(-1)^{v\cdot(M\gamma-
z_{0})}=\operatorname{\mathbb{E}}_{v\in\mathbb{F}_{2}^{\overline{S}}}1=1$. If
$\gamma\notin C(S,z_{0})$, then $\gamma_{j}\neq(z_{0})_{j}$ for some
$j\in\overline{S}$. Therefore,
$\operatorname{\mathbb{E}}_{v\in\mathbb{F}_{2}^{\overline{S}}}(-1)^{v\cdot(M\gamma-
z_{0})}=\operatorname{\mathbb{E}}_{v\in\mathbb{F}_{2}^{\overline{S}}}(-1)^{v\cdot
y}$ for some nonzero vector $y$. Hence,
$\operatorname{\mathbb{E}}_{v\in\mathbb{F}_{2}^{\overline{S}}}(-1)^{v\cdot(M\gamma-
z_{0})}=0$. Let $f$ be a function which satisfies the Balanced Influence
Property $INF(d,\epsilon/2)$. To use Equation (2), we expand the definition of
the spectral sample.

$\displaystyle\operatorname{\mathbb{P}}_{\gamma\sim\mathcal{S}_{f}}\left[\gamma\in
C(S,z_{0})\right]$ $\displaystyle=\sum_{\gamma\in
C(S,z_{0})}\widehat{f}\left(\gamma\right)^{2}$
$\displaystyle=\sum_{\gamma\in\mathbb{F}_{2}^{n}}\widehat{f}\left(\gamma\right)^{2}[\gamma\in
C(S,z_{0})]$
$\displaystyle=\sum_{\gamma\in\mathbb{F}_{2}^{n}}\widehat{f}\left(\gamma\right)^{2}\operatorname{\mathbb{E}}_{v\in\mathbb{F}_{2}^{\overline{S}}}(-1)^{v\cdot(M\gamma-
z_{0})}~{}~{}~{}~{}\text{By Equation (\ref{eqn indicator function as exp
sum})}$
$\displaystyle=\operatorname{\mathbb{E}}_{v\in\mathbb{F}_{2}^{\overline{S}}}(-1)^{v\cdot
z_{0}}\sum_{\gamma\in\mathbb{F}_{2}^{n}}\widehat{f}\left(\gamma\right)^{2}(-1)^{v\cdot
M\gamma}$
$\displaystyle=\operatorname{\mathbb{E}}_{v\in\mathbb{F}_{2}^{\overline{S}}}(-1)^{v\cdot
z_{0}}\sum_{\gamma\in\mathbb{F}_{2}^{n}}\widehat{f}\left(\gamma\right)^{2}(-1)^{M^{\top}v\cdot\gamma}$
$\displaystyle=\operatorname{\mathbb{E}}_{v\in\mathbb{F}_{2}^{\overline{S}}}(-1)^{v\cdot
z_{0}}\sum_{\gamma\in\mathbb{F}_{2}^{n}}\widehat{f}\left(\gamma\right)^{2}\chi_{\gamma}(M^{\top}v)~{}~{}~{}~{}~{}\text{By
definition of $\chi_{\gamma}$}$
$\displaystyle=\operatorname{\mathbb{E}}_{v\in\mathbb{F}_{2}^{k}}(-1)^{v\cdot
z_{0}}f*f(M^{\top}v)$

where we use the Fourier expansion of $f*f$ in the final line. Notice that
$f*f(M^{\top}0)=(f*f)(0)=1$, and that $x=0$ is the only solution to
$M^{\top}x=0$. Therefore, we can write

$\displaystyle\mathinner{\\!\left\lvert\operatorname{\mathbb{P}}_{\gamma\sim\mathcal{S}_{f}}\left[\gamma\in
C(S,z_{0})\right]-2^{-k}\right\rvert}$
$\displaystyle=\mathinner{\\!\left\lvert\sum_{v\in\mathbb{F}_{2}^{k}}(-1)^{v\cdot
z_{0}}\dfrac{f*f(M^{\top}v)}{2^{k}}-2^{-k}\right\rvert}$
$\displaystyle=\mathinner{\\!\left\lvert\sum_{v\in\mathbb{F}_{2}^{k}\setminus\\{\vec{0}\\}}(-1)^{v\cdot
z_{0}}\dfrac{f*f(M^{\top}v)}{2^{k}}\right\rvert}$
$\displaystyle\leq\frac{1}{2^{k}}\sum_{v\in\mathbb{F}_{2}^{k}\setminus\\{\vec{0}\\}}\mathinner{\\!\left\lvert
f*f(Mv)\right\rvert}$
$\displaystyle=\frac{1}{2^{k}}\sum_{v\in\mathbb{F}_{2}^{k}\setminus\\{\vec{0}\\}}\mathinner{\\!\left\lvert
1-2\operatorname{I}_{M^{\top}v}[f]\right\rvert}$

where we use Lemma 5.1 in the final line. As $k\leq d$, we have
$\mathinner{\\!\left\lvert
S\right\rvert}=n-\mathinner{\\!\left\lvert\overline{S}\right\rvert}=k\leq d$,
$\mathinner{\\!\left\lvert S\right\rvert}\leq d$. Thus,
$\mathinner{\\!\left\lvert v\right\rvert}\leq d$. Since $M$ is a projection
matrix, $\mathinner{\\!\left\lvert
M^{\top}v\right\rvert}=\mathinner{\\!\left\lvert v\right\rvert}\leq d$ . There
fore, we may apply $INF(d,\epsilon/2)$ to find

$\displaystyle\mathinner{\\!\left\lvert\operatorname{\mathbb{P}}_{\gamma\sim\mathcal{S}_{f}}\left[\gamma\in
C(S,z_{0})\right]-2^{-k}\right\rvert}$
$\displaystyle\leq\frac{1}{2^{k}}\sum_{v\in\mathbb{F}_{2}^{k}\setminus\\{\vec{0}\\}}\epsilon\leq\epsilon$

As $C(S,z_{0})$ is arbitrary, $f$ also satisfies the Spectral Discrepancy
Property $SD(d,\epsilon)$. ∎

For our next few implications, we will need the following result from
O’Donnell’s book [20], translated into our notation.

######  Lemma 5.3.

[[20] Proposition 3.21] If $C(S,z)$ is a fixed subcube and
$\gamma\in\mathbb{F}_{2}^{S}$, then

$\widehat{f|_{S,z}}\left(\gamma\right)=\sum_{\delta\in\mathbb{F}_{2}^{\overline{S}}}\widehat{f}\left(\delta\underset{S}{\otimes}\gamma\right)\chi_{\delta}(z)$

Now we can relate the spectral sample to the Fourier coefficients of
restricted functions.

######  Theorem 5.4.

For any fixed $d\geq 1$ and $\epsilon>0$ the Spectral Discrepancy Property
$SD(d,\epsilon)$ implies the Restriction Fourier Property $RF(d,\epsilon)$.

###### Proof.

This proof is essentially the proof of Corollary 3.22 in [20], which we
reproduce here in our notation for completeness. Suppose
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ satisfies
the Spectral Discrepancy Property $SD(d,\epsilon)$. Let $C(S,z)$ be an
arbitrary subcube of dimension $k$ where $k\leq d$. Then for a fixed
$\gamma\in\mathbb{F}_{2}^{S}$, Lemma 5.3 gives us

$\displaystyle\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}\widehat{f|_{S,z}}\left(\gamma\right)^{2}$
$\displaystyle=\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}\left(\sum_{\delta\in\mathbb{F}_{2}^{\overline{S}}}\widehat{f}\left(\delta\underset{S}{\otimes}\gamma\right)\chi_{\delta}(z)\right)^{2}$
$\displaystyle=\sum_{\delta_{1},\delta_{2}\in\mathbb{F}_{2}^{\overline{S}}}\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}\widehat{f}\left(\delta_{1}\underset{S}{\otimes}\gamma\right)\widehat{f}\left(\delta_{2}\underset{S}{\otimes}\gamma\right)\chi_{\delta_{1}}(z)\chi_{\delta_{2}}(z)$
$\displaystyle=\sum_{\delta_{1},\delta_{2}\in\mathbb{F}_{2}^{\overline{S}}}\widehat{f}\left(\delta_{1}\underset{S}{\otimes}\gamma\right)\widehat{f}\left(\delta_{2}\underset{S}{\otimes}\gamma\right)\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}\chi_{\delta_{1}}(z)\chi_{\delta_{2}}(z)$
$\displaystyle=\sum_{\delta\in\mathbb{F}_{2}^{\overline{S}}}\widehat{f}\left(\delta\underset{S}{\otimes}\gamma\right)^{2}$
(3)
$\displaystyle=\operatorname{\mathbb{P}}_{\eta\sim\mathcal{S}_{f}}\left[\eta\in
C(\overline{S},\gamma)\right]$ (4)

where we use the orthogonality of the Fourier characters in line (3) and the
definition of the spectral sample line (4). As $k\leq d$,
$\mathinner{\\!\left\lvert\overline{S}\right\rvert}=n-k\geq n-d$. Thus we can
apply Property $SD(d,\epsilon)$ to $C(\overline{S},z)$ to find that

$\mathinner{\\!\left\lvert\operatorname{\mathbb{P}}_{\eta\sim\mathcal{S}_{f}}\left[\eta\in
C(\overline{S},\gamma)\right]-2^{-k}\right\rvert}<\epsilon$

for every $\gamma\in\mathbb{F}_{2}^{S}$. Hence,

$\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}\widehat{f|_{S,z}}\left(\gamma\right)^{2}-2^{-k}\right\rvert}<\epsilon$

for every $\gamma\in\mathbb{F}_{2}^{S}$. As $C(S,z)$ is arbitrary, $f$ also
satisfies the Restriction Fourier Property $RF(d,\epsilon)$. ∎

With a bound on the Fourier coefficients of restricted functions, we can bound
the convolution of a restricted function with itself.

######  Theorem 5.5.

For any fixed $d\geq 1$ and $\epsilon>0$ the Restriction Fourier Property
$SD(d,\epsilon/2^{d})$ implies the Restriction Convolution Property
$RC(d,\epsilon)$

###### Proof.

Let $f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ have
the Restriction Fourier Property $RF(d,\epsilon/2^{d})$, and note that $f$
also satisfies $RF(k,\epsilon/2^{k})$ for every $k\leq d$. Fix
$k\in\mathbb{N}$ such that $k\leq d$ and a set $S\subseteq[n]$ where $|S|=k$.

We have

$\displaystyle\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}(f|_{S,z}*f|_{S,z})(x)$
$\displaystyle=\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}\sum_{\delta\in\mathbb{F}_{2}^{S}}\widehat{f|_{S,z}}\left(\delta\right)^{2}\chi_{\delta}(x)$
$\displaystyle=\sum_{\delta\in\mathbb{F}_{2}^{S}}\left(\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}\widehat{f|_{S,z}}\left(\delta\right)^{2}\right)\chi_{\delta}(x)$

Using the Fourier expansion of the indicator function $[x=0]$, we then have

$\displaystyle\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}(f|_{S,z}*f|_{Sz})(x)-[x=0]\right\rvert}$
$\displaystyle=\mathinner{\\!\left\lvert\sum_{\delta\in\mathbb{F}_{2}^{S}}\left(\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}\widehat{f|_{S,z}}\left(\delta\right)^{2}-\frac{1}{2^{k}}\right)\chi_{\delta}(x)\right\rvert}$
$\displaystyle\leq\sum_{\delta\in\mathbb{F}_{2}^{S}}\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}\widehat{f|_{S,z}}\left(\delta\right)^{2}-\frac{1}{2^{k}}\right\rvert}$
$\displaystyle\leq\sum_{\delta\in\mathbb{F}_{2}^{S}}\frac{\epsilon}{2^{k}}$
$\displaystyle\leq\epsilon$

where we use $RF(k,\epsilon/2^{k})$ in the penultimate line. Since $k$ and $S$
are arbitrary, we conclude that $f$ also satisfies the Restriction Convolution
Property $RC(d,\epsilon)$. ∎

Lemma (5.1) gives us a further property:

######  Theorem 5.6.

For any fixed $d\geq 1$ and $\epsilon>0$ the Restriction Convolution Property
$SD(d,2\epsilon)$ implies the Restriction Influences Property
$RF(d,\epsilon)$.

###### Proof.

Suppose $f$ satisfies the Restriction Convolution Property $RC(d,2\epsilon)$.
By Lemma (5.1) applied to $f|_{S,z}$, we have

$\operatorname{I}_{\gamma}[f|_{S,z}]=\frac{1-f|_{S,z}*f|_{S,z}(\gamma)}{2}$

for any fixed $S$ and $z$. Now fix $k\in\mathbb{N}$ such that $k\leq d$ and
$S\subseteq[n]$ where $|S|=k$. Then,

$\displaystyle\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}\operatorname{I}_{\gamma}[f|_{S,z}]-\frac{1}{2}\right\rvert}$
$\displaystyle=\mathinner{\\!\left\lvert\left(\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}\frac{1-f|_{S,z}*f|_{S,z}(\gamma)}{2}\right)-\frac{1}{2}\right\rvert}$
$\displaystyle=\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}\frac{f|_{S,z}*f|_{S,z}(\gamma)}{2}\right\rvert}$

As $\gamma\neq 0$, $RC(d,2\epsilon)$ implies that the above is at most
$\epsilon$. Hence, $f$ satisfies the Restriction Influences Property
$RI(d,\epsilon)$. ∎

As one might imagine, the influences of restricted functions relate nicely to
the influences of the original function.

######  Theorem 5.7.

For any fixed $d\geq 1$ and $\epsilon>0$, the Restriction Influences Property
$RI(d,\epsilon)$ implies the Balanced Influences Property $INF(d,\epsilon)$.

###### Proof.

Suppose $f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$
satisfies the Restriction Influences Property $RF(d,\epsilon)$. Fix
$S\subseteq[n]$ with $|S|\leq d$ and $\gamma\in\mathbb{F}_{2}^{S}$. Then,

$\displaystyle\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}\operatorname{I}_{\gamma}[f]$
$\displaystyle=\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}\operatorname{\mathbb{E}}_{x\in\mathbb{F}_{2}^{S}}[f|_{S,z}(x+\gamma)\neq
f|_{S,z}(x)]$
$\displaystyle=\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{\overline{S}}}\operatorname{\mathbb{E}}_{x\in\mathbb{F}_{2}^{S}}[f(x\underset{S}{\otimes}z+\gamma\underset{S}{\otimes}z))\neq
f(x\underset{S}{\otimes}z)]$

Let $y=x\underset{S}{\otimes}z$ and $\delta=\gamma\underset{S}{\otimes}0$.
Note that $\mathinner{\\!\left\lvert\delta\right\rvert}\leq d$ as
$\mathinner{\\!\left\lvert S\right\rvert}\leq d$.

$\displaystyle=\operatorname{\mathbb{E}}_{y\in\mathbb{F}_{2}^{n}}[f(y+\delta)\neq
f(y)]$ $\displaystyle=\operatorname{I}_{\delta}[f]$

Since any vector of Hamming weight at most $d$ can be represented as
$\gamma\underset{S}{\otimes}0$ for some set $S$ with
$\mathinner{\\!\left\lvert S\right\rvert}\leq d$ and
$\gamma\in\mathbb{F}_{2}^{S}$, the claim follows by $RI(d,\epsilon)$. Thus $f$
also satisfies the Balanced Influences Property $INF(d,\epsilon)$. ∎

Now we can cross over to more combinatorial properties.

######  Theorem 5.8.

For any fixed $d\geq 1$ and $\epsilon>0$, the Restriction Convolution Property
$RC(d,4\epsilon)$ implies that Local Strong Regularity Property
$LSR(d,\epsilon)$.

###### Proof.

Suppose $f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$
satisfies the Restriction Convolution Property $RC(d,4\epsilon)$. Fix $u\text{
and }v$ in the left part of the bipartite Cayley graph of $f$ such that
$0<\mathinner{\\!\left\lvert u-v\right\rvert}\leq d$. Let $S\subseteq[n]$ with
$\mathinner{\\!\left\lvert S\right\rvert}=d$ be a set which contains all the
indices on which $u$ and $v$ differ. Then,

$\displaystyle\mathinner{\\!\left\lvert\frac{\mathinner{\\!\left\lvert
N(u)\cap
N(v)\right\rvert}}{2^{n}}-\frac{1}{4}+\frac{\widehat{f}\left(0\right)}{2}\right\rvert}$
$\displaystyle=\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{c\in\mathbb{F}_{2}^{n}}\frac{(1-f(u+c))(1-f(v+c))}{4}-\frac{1}{4}+\frac{\widehat{f}\left(0\right)}{2}\right\rvert}$
$\displaystyle=\frac{1}{4}\mathinner{\\!\left\lvert
2\widehat{f}\left(0\right)-\left(\operatorname{\mathbb{E}}_{c\in\mathbb{F}_{2}^{n}}f(u+c)+f(c+v)\right)+\operatorname{\mathbb{E}}_{c\in\mathbb{F}_{2}^{n}}f(u+c)f(v+c)\right\rvert}$
$\displaystyle=\frac{1}{4}\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{c\in\mathbb{F}_{2}^{n}}f(u+c)f(v+c)\right\rvert}$

where we use the definition $\widehat{f}\left(0\right)$ in the final line. Now
write $u=x\underset{S}{\otimes}z$, $v=y\underset{S}{\otimes}z$, and
$c=w\underset{S}{\otimes}a$. We then have

$\displaystyle\mathinner{\\!\left\lvert\frac{\mathinner{\\!\left\lvert
N(u)\cap
N(v)\right\rvert}}{2^{n}}-\frac{1}{4}+\frac{\widehat{f}\left(0\right)}{2}\right\rvert}$
$\displaystyle=\frac{1}{4}\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{a\in\mathbb{F}_{2}^{\overline{S}}}\operatorname{\mathbb{E}}_{w\in\mathbb{F}_{2}^{S}}f(x\underset{S}{\otimes}z+w\underset{S}{\otimes}a)f(y\underset{S}{\otimes}z+w\underset{S}{\otimes}a)\right\rvert}$
$\displaystyle=\frac{1}{4}\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{w\in\mathbb{F}_{2}^{S}}\operatorname{\mathbb{E}}_{a\in\mathbb{F}_{2}^{\overline{S}}}f(9x+w)\underset{S}{\otimes}(z+a))f((y+w)\underset{S}{\otimes}(z+a))\right\rvert}$
Noting that $w+w=0$,
$\displaystyle=\frac{1}{4}\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{w\in\mathbb{F}_{2}^{S}}\operatorname{\mathbb{E}}_{a\in\mathbb{F}_{2}^{\overline{S}}}f|_{S,a+z}*f|_{S,a+z}(x+y)\right\rvert}$
$\displaystyle=\frac{1}{4}\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{a^{\prime}\in\mathbb{F}_{2}^{\overline{S}}}f|_{S,a^{\prime}}*f|_{S,a^{\prime}}(x+y)\right\rvert}$
$\displaystyle\leq\epsilon$

where we use $RC(d,4\epsilon)$ and the fact that $u\neq v$ in the final line.
Thus $f$ also satisfies the Local Strong Regularity Property
$LSR(d,\epsilon)$. ∎

######  Theorem 5.9.

For any fixed $d\geq 1$ and $\epsilon>0$, the Balanced Influences Property
$INF(d,4\epsilon)$ implies the Local Strong Regularity Property
$LSR(d,\epsilon)$.

###### Proof.

Suppose $f;\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ satisfies the Balanced Influences
Property $INF(d,4\epsilon)$. Fix $u,v$ in the left part of the bipartite
Cayley graph of $f$ such that $0<\mathinner{\\!\left\lvert
u-v\right\rvert}\leq d$. Then,

$\displaystyle\mathinner{\\!\left\lvert\frac{\mathinner{\\!\left\lvert
N(u)\cap
N(v)\right\rvert}}{2^{n}}-\frac{1}{4}+\frac{\widehat{f}\left(0\right)}{2}\right\rvert}$
$\displaystyle=\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{n}}\frac{(1-f(u+z))(1-f(v+z))}{4}-\frac{1}{4}+\frac{\widehat{f}\left(0\right)}{2}\right\rvert}$
$\displaystyle=\frac{1}{4}\left(2\widehat{f}\left(0\right)-\left(\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{n}}f(u+z)+f(z+z)\right)+\operatorname{\mathbb{E}}_{z\in\mathbb{F}_{2}^{n}}f(u+z)f(v+z)\right)$
$\displaystyle=\frac{1}{4}f*f(u+v)$ $\displaystyle\leq\epsilon$

where we use Lemma (5.1) in the third line and $INF(d,4\epsilon)$ in the final
line. It follows that $f$ also satisfies the Local Strong Regularity Property
$LSR(d,\epsilon)$. ∎

For $a,b\in\mathbb{N}$, let $(a)_{b}$ denote the Falling Factorial defined by
$(a)_{b}=a(a-1)\dots(a-b+1)$. Recall that $S\hookrightarrow T$ is the set of
injective functions from $S$ to $T$. For a graph $G$ two vertices $x\in V(G)$
and $y\in V(G)$, let $x\underset{G}{\sim}y$ denote the proposition that $x$ is
adjacent to $y$. If the graph is clear from context, we will simply write
$x\sim y$.

######  Theorem 5.10.

For any fixed $d\geq 1$ and $\epsilon>0$, the Local Strong Regularity Property
$LSR(d,\frac{\epsilon p}{2e\mathinner{\\!\left\lvert D_{2}\right\rvert}})$
implies the Degree-$2$ Homomorphisms Property $DTE(d,\epsilon)$ where $D_{2}$
is the set of vertices of degree $2$ in the right part of a bipartite graph
$G$..

###### Proof.

Fix a bipartite graph $G$ with $l$ vertices in its left part $L(G)$, $r$
vertices in its right part $R(G)$, and maximum degree $2$ in $R(G)$. Let
$D_{1},D_{2}$ denote sets of vertices in $R(G)$ of degree $1$ and $2$
respectively. Finally, for a vertex $r$ in $R(G)$, define
$p_{r}\mathrel{\mathop{\ordinarycolon}}=\begin{cases}q&\deg(r)=1\\\
p&\deg(r)=2\end{cases}$ where
$p=\frac{1}{4}-\frac{\widehat{f}\left(0\right)}{2}$ and
$q=\frac{1-\widehat{f}\left(0\right)}{2}$.

Suppose that
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ satisfies
the Local Strong Regularity Property $LSR(d,\frac{\epsilon
p}{2e\mathinner{\\!\left\lvert D_{2}\right\rvert}})$. We begin by expanding
the Degree-$2$ Homomorphisms Property (Property 7)

$\displaystyle\mathinner{\\!\left\lvert\operatorname{bhom}_{\psi}(G,BC(f))-p^{\mathinner{\\!\left\lvert
D_{2}\right\rvert}}q^{\mathinner{\\!\left\lvert
D_{1}\right\rvert}}\right\rvert}$
$\displaystyle=\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{\phi\mathrel{\mathop{\ordinarycolon}}R(G)\hookrightarrow\mathbb{F}_{2}^{n}}\prod_{(l,r)\in
E(G)}[\psi(l)\sim\phi(r)]-p^{\mathinner{\\!\left\lvert
D_{2}\right\rvert}}q^{\mathinner{\\!\left\lvert
D_{1}\right\rvert}}\right\rvert}$
$\displaystyle=\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{\phi\mathrel{\mathop{\ordinarycolon}}R(G)\hookrightarrow\mathbb{F}_{2}^{n}}\prod_{r\in
R(G)}\prod_{l\in N_{G}(r)}[\psi(l)\sim\phi(r)]-p^{\mathinner{\\!\left\lvert
D_{2}\right\rvert}}q^{\mathinner{\\!\left\lvert
D_{1}\right\rvert}}\right\rvert}$

where we use the fact that $G$ is bipartite in the second line. We can now add
$p_{r}-p_{r}$ to each term in the product and then telescope as follows:

$\displaystyle\mathinner{\\!\left\lvert\operatorname{bhom}_{\psi}(G,BC(f))-p^{\mathinner{\\!\left\lvert
D_{2}\right\rvert}}q^{\mathinner{\\!\left\lvert
D_{1}\right\rvert}}\right\rvert}$
$\displaystyle=\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{\phi\mathrel{\mathop{\ordinarycolon}}R(G)\hookrightarrow\mathbb{F}_{2}^{n}}\left(\prod_{r\in
R(G)}\left(\left(\prod_{l\in
N_{G}(r)}[\psi(l)\sim\phi(r)]\right)-p_{r}\right)+p_{r}\right)-p^{\mathinner{\\!\left\lvert
D_{2}\right\rvert}}q^{\mathinner{\\!\left\lvert
D_{1}\right\rvert}}\right\rvert}$
$\displaystyle=\mathinner{\\!\left\lvert\sum_{\emptyset\neq S\subseteq
R(G)}\operatorname{\mathbb{E}}_{\phi\mathrel{\mathop{\ordinarycolon}}R(G)\hookrightarrow\mathbb{F}_{2}^{n}}\left(\prod_{r\in
R(G)\setminus S}p_{r}\right)\left(\prod_{r\in S}\left(\left(\prod_{l\in
N_{G}(r)}[\psi(l)\sim\phi(r)]\right)-p_{r}\right)\right)\right\rvert}$
$\displaystyle\leq\sum_{\emptyset\neq S\subseteq R(G)}\left(\prod_{r\in
R(G)\setminus
S}p_{r}\right)\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{\phi\mathrel{\mathop{\ordinarycolon}}R(G)\hookrightarrow\mathbb{F}_{2}^{n}}\prod_{r\in
S}\left(\left(\prod_{l\in
N_{G}(r)}[\psi(l)\sim\phi(r)]\right)-p_{r}\right)\right\rvert}$

We now focus on an individual set $S\subseteq R(G)$ and its contribution to
the sum:

$X_{S}\mathrel{\mathop{\ordinarycolon}}=\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{\phi\mathrel{\mathop{\ordinarycolon}}R(G)\hookrightarrow\mathbb{F}_{2}^{n}}\prod_{r\in
S}\left(\left(\prod_{l\in
N_{G}(r)}[\psi(l)\sim\phi(r)]\right)-p_{r}\right)\right\rvert}$

We would like to exchange the expectation and the product over elements of
$S$. However, the expectation is over all injections not all functions. Thus
we proceed as follows.

$\displaystyle X_{S}$
$\displaystyle=\frac{1}{(2^{n})_{s}}\mathinner{\\!\left\lvert\sum_{\phi\mathrel{\mathop{\ordinarycolon}}R(G)\hookrightarrow\mathbb{F}_{2}^{n}}\prod_{r\in
S}\left(\left(\prod_{l\in
N_{G}(r)}[\psi(l)\sim\phi(r)]\right)-p_{r}\right)\right\rvert}$
$\displaystyle\leq\frac{1}{(2^{n})_{s}}\mathinner{\\!\left\lvert\sum_{\phi\mathrel{\mathop{\ordinarycolon}}R(G)\to\mathbb{F}_{2}^{n}}\prod_{r\in
S}\left(\left(\prod_{l\in
N_{G}(r)}[\psi(l)\sim\phi(r)]\right)-p_{r}\right)\right\rvert}$
$\displaystyle=\frac{2^{ns}}{(2^{n})_{s}}\prod_{i=1}^{s}\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{\phi(r_{i})\in\mathbb{F}_{2}^{n}}\left(\left(\prod_{l\in
N_{G}(r_{i})}[\psi(l)\sim\phi(r_{i})]\right)-p_{r}\right)\right\rvert}$

If $\deg(r_{i})=1$, then

$\displaystyle\operatorname{\mathbb{E}}_{\phi(r_{i})\in\mathbb{F}_{2}^{n}}\left(\left(\prod_{l\in
N_{G}(r_{i})}[\psi(l)\sim\phi(r_{i})]\right)-p_{r}\right)$
$\displaystyle=\operatorname{\mathbb{E}}_{\phi(r_{i})\in\mathbb{F}_{2}^{n}}[\psi(l)\sim\phi(r_{i})]-q$
$\displaystyle=\operatorname{\mathbb{E}}_{\phi(r_{i})\in\mathbb{F}_{2}^{n}}\dfrac{1-f(\psi(l)+\phi(r))}{2}-\frac{1-\widehat{f}\left(0\right)}{2}$
$\displaystyle=0$

Thus, $X_{S}$ is $0$ if $S$ contains any vertices of degree $1$. Assume then
that every $r_{i}\in S$ has exactly $2$ neighbors. Since the neighbors of
$\phi(r_{i})$ are fixed by $\psi$, we may apply $LSR(d,\frac{\epsilon
p}{2e\mathinner{\\!\left\lvert D_{2}\right\rvert}})$ to conclude that

$\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{\phi(r_{i})\in\mathbb{F}_{2}^{n}}\left(\left(\prod_{l\in
N_{G}(r_{i})}[\psi(l)\sim\phi(r_{i})]\right)-p_{r_{i}}\right)\right\rvert}<\frac{\epsilon
p}{2e\mathinner{\\!\left\lvert D_{2}\right\rvert}}.$

Thus, if $S$ only contains vertices of degree $2$,

$\displaystyle X_{S}$
$\displaystyle\leq\frac{2^{ns}}{(2^{n})_{s}}\left(\frac{\epsilon
p}{2e\mathinner{\\!\left\lvert
D_{2}\right\rvert}}\right)^{\mathinner{\\!\left\lvert S\right\rvert}}$

We then wish to bound the first term in the product:

$\displaystyle\frac{2^{ns}}{(2^{n})_{s}}$
$\displaystyle=\prod_{i=0}^{s-1}\frac{1}{1-\frac{i}{2^{n}}}$
$\displaystyle\leq\left(1-\frac{s}{2^{n}}\right)^{-s}$
$\displaystyle\leq\exp\left(\frac{s^{2}}{2^{n}}\right)$ $\displaystyle\leq e$

as $\mathinner{\\!\left\lvert S\right\rvert}\leq\mathinner{\\!\left\lvert
R\right\rvert}\leq 2^{n/2}$. Therefore,

$\displaystyle\mathinner{\\!\left\lvert\operatorname{bhom}_{\psi}(G,BC(f))-p^{\mathinner{\\!\left\lvert
D_{2}\right\rvert}}q^{\mathinner{\\!\left\lvert
D_{1}\right\rvert}}\right\rvert}$ $\displaystyle\leq\sum_{\emptyset\neq
S\subseteq R(G)}\left(\prod_{r\in R(G)\setminus S}p_{r}\right)X_{S}$
$\displaystyle\leq e\sum_{\emptyset\neq S\subseteq R(G)}\left(\prod_{r\in
R(G)\setminus S}p_{r}\right)[S\cap D_{1}=\emptyset]\left(\frac{\epsilon
p}{2e\mathinner{\\!\left\lvert
D_{2}\right\rvert}}\right)^{\mathinner{\\!\left\lvert S\right\rvert}}$
$\displaystyle=ep^{\mathinner{\\!\left\lvert
D_{2}\right\rvert}}q^{\mathinner{\\!\left\lvert
D_{1}\right\rvert}}\sum_{\emptyset\subsetneq S\subseteq
D_{2}}\left(\frac{\epsilon}{2e\mathinner{\\!\left\lvert
D_{2}\right\rvert}}\right)^{\mathinner{\\!\left\lvert S\right\rvert}}$
$\displaystyle=ep^{\mathinner{\\!\left\lvert
D_{2}\right\rvert}}q^{\mathinner{\\!\left\lvert
D_{1}\right\rvert}}\left(\left(1+\frac{\epsilon}{2e\mathinner{\\!\left\lvert
D_{2}\right\rvert}}\right)^{\mathinner{\\!\left\lvert
D_{2}\right\rvert}}-1\right)$ $\displaystyle\leq ep^{\mathinner{\\!\left\lvert
D_{2}\right\rvert}}q^{\mathinner{\\!\left\lvert
D_{1}\right\rvert}}\left(e^{\frac{\epsilon}{2e}}-1\right)$ (5)
$\displaystyle\leq p^{\mathinner{\\!\left\lvert
D_{2}\right\rvert}}q^{\mathinner{\\!\left\lvert D_{1}\right\rvert}}\epsilon$
(6)

where we use $1+x\leq e^{x}$ in line (5) and $e^{-x/2}\leq 1-x$ for
$x\leq\frac{1}{2}$ in line (6). Hence, $f$ also satisfies the Degree Two
Homomorphisms Property $DTH(d,\epsilon)$. ∎

To prove our next theorem, we need a few additional definitions. The
subdivision of a graph $G$, denoted $\operatorname{Sub}(G)$, is the bipartite
graph $(A\sqcup B,E)$ where $A=V(G)$,
$B=\\{r_{(u,v)}\mathrel{\mathop{\ordinarycolon}}(u,v)\in E(G)\\}$, and
$E=E_{1}\sqcup E_{2}$ where
$E_{1}=\\{(u,r_{(u,v)})\mathrel{\mathop{\ordinarycolon}}(u,v)\in
E(G)\\}$,$E_{2}=\\{(v,r_{(u,v)})\mathrel{\mathop{\ordinarycolon}}(u,v)\in
E(G)\\}$.

For two graphs $H$ and $G$, let $H\leq G$ denote the relation that $H$ is a
subgraph of $G$. For a subgraph $H\leq\operatorname{Sub}(G)$, let
$D_{2}(H)\subseteq R(H)$ denote the set of vertices in
$R(\operatorname{Sub}(G))$ of degree $2$ in $G$. Similarly, let
$D_{A}(H)\subseteq R(H)$ and $D_{B}(H)\subseteq R(H)$ denote the sets of
vertices of degree $1$ in $H$ whose incident edge is in $E_{1}$ and $E_{2}$
respectively.

We will need the following technical Lemma.

######  Lemma 5.11.

Then,

$\sum_{\begin{subarray}{c}H\\\
H\leq\operatorname{Sub}(G)\end{subarray}}x^{\mathinner{\\!\left\lvert
D_{2}(H)\right\rvert}}y^{\mathinner{\\!\left\lvert
D_{A}(H)\right\rvert}}z^{\mathinner{\\!\left\lvert
D_{B}(h)\right\rvert}}=(1+x+y+z)^{\mathinner{\\!\left\lvert
R(\operatorname{Sub}(G))\right\rvert}}$

###### Proof.

We expand the RHS by the multinomial theorem as

$(1+x+y+z)^{\mathinner{\\!\left\lvert
R(G^{\prime})\right\rvert}}=\sum_{\begin{subarray}{c}S,T,U,V\subseteq
R(G^{\prime})\\\ S\sqcup T\sqcup U\sqcup
V=E(G)\end{subarray}}x^{\mathinner{\\!\left\lvert
S\right\rvert}}y^{\mathinner{\\!\left\lvert
T\right\rvert}}z^{\mathinner{\\!\left\lvert U\right\rvert}}.$

We claim that each term in the sum defines a unique subgraph $H$ of
$G^{\prime}$. Indeed, for a fixed partition of $R(G^{\prime})$ into sets
$S,T,U,V$, let $S$ be the set of vertices in $R(H)$ of degree $2$, let $T$ to
be the set of vertices in $R(H)$ of degree $1$ incident to $A$, let $U$ to be
the set of vertices in $R(H)$ of degree $1$ incident to $B$, and let $V$ to
all remaining vertices. This mapping is bijective, and thus,

$\sum_{\begin{subarray}{c}S,T,U,V\subseteq R(G^{\prime})\\\ S\sqcup T\sqcup
U\sqcup V=E(G)\end{subarray}}x^{\mathinner{\\!\left\lvert
S\right\rvert}}y^{\mathinner{\\!\left\lvert
T\right\rvert}}z^{\mathinner{\\!\left\lvert U\right\rvert}}=\sum_{H\leq
G^{\prime}}x^{\mathinner{\\!\left\lvert
D_{2}(H)\right\rvert}}y^{\mathinner{\\!\left\lvert
D_{A}(H)\right\rvert}}z^{\mathinner{\\!\left\lvert D_{B}(H)\right\rvert}}.$

∎

######  Theorem 5.12.

For any fixed $d\geq 1$ and $\epsilon>0$, the Degree-$2$ Homomorphisms
Property
$DTH\left(d,\epsilon\left(\frac{5}{2}+\widehat{f}\left(0\right)\right)^{-\mathinner{\\!\left\lvert
E(G)\right\rvert}}\right)$ implies the Rainbow Embeddings Property
$RAIN(d,\epsilon)$.

###### Proof.

Let $G$ be a fixed graph. Suppose $f;\mathbb{F}_{2}^{n}\to\\{1,-1\\}$
satisfies the Degree-$2$ Homomorphisms Property
$DTH\left(d,\epsilon\left(\frac{5}{2}+\widehat{f}\left(0\right)\right)^{-\mathinner{\\!\left\lvert
E(G)\right\rvert}}\right)$. Let
$\phi\mathrel{\mathop{\ordinarycolon}}V(G)\hookrightarrow B_{d}(0)$ be an
injection of diameter at most $d$. Recalling the definition of a rainbow
embedding, we have

$\displaystyle\operatorname{em}_{\phi}(G,RHG(d,f))$
$\displaystyle=\operatorname{\mathbb{E}}_{\chi\mathrel{\mathop{\ordinarycolon}}E(G)\hookrightarrow\mathbb{F}_{2}^{n}}\prod_{(u,v)\in
E(G)}[(u,v,\chi((u,v)))\in E(RHG(d,f))]$
$\displaystyle=\operatorname{\mathbb{E}}_{\chi\mathrel{\mathop{\ordinarycolon}}E(G)\hookrightarrow\mathbb{F}_{2}^{n}}\prod_{(u,v)\in
E(G)}[f(\phi(u)+\chi((u,v)))=f(\phi(v)+\chi((u,v)))]$ Let $U^{+}(u,v)$ denote
the event that $f(\phi(u)+\chi((u,v)))=1$ and $U^{-}(u,v)$ denote the event
that $f(\phi(u)+\chi((u,v)))=-1$. Define $V^{+}(u,v)$ and $V^{-}(u,v)$
likewise. $\displaystyle\operatorname{em}_{\phi}(G,RHG(d,f))$
$\displaystyle=\operatorname{\mathbb{E}}_{\chi\mathrel{\mathop{\ordinarycolon}}E(G)\hookrightarrow\mathbb{F}_{2}^{n}}\prod_{(u,v)\in
E(G)}\bigg{(}[U^{+}(u,v)][V^{+}(u,v)]+[U^{-}(u,v)][V^{-}(u,v)]\bigg{)}$
$\displaystyle=\operatorname{\mathbb{E}}_{\chi\mathrel{\mathop{\ordinarycolon}}E(G)\hookrightarrow\mathbb{F}_{2}^{n}}\prod_{(u,v)\in
E(G)}\bigg{(}[U^{-}(u,v)][V^{-}(u,v)]+(1-[U^{-}(u,v)])(1-[V^{-}(u,v)])\bigg{)}$
$\displaystyle=\operatorname{\mathbb{E}}_{\chi\mathrel{\mathop{\ordinarycolon}}E(G)\hookrightarrow\mathbb{F}_{2}^{n}}\prod_{(u,v)\in
E(G)}\bigg{(}1-[U^{-}(u,v)]-[V^{-}(u,v)]+2[U^{-}(u,v)][V^{-}(u,v)]\bigg{)}$
(7)

We wish to lift the expression in line (7) to an equivalent expression in
terms of a bipartite graph homomorphism of $\operatorname{Sub}(G)$ into
$BC(f)$. Observe that $\phi$ is injective and its image has diameter at most
$k$, so $\phi$ is a valid choice of the map for the left part of a bipartite
graph homomorphism of $\operatorname{Sub}(G)$. Similarly, $\chi$ defines the
right part of a bipartite graph homomorphism. In consequence, the event
$U^{-}(u,v)$, which holds when $f(\phi(u)+\chi((u,v)))=-1$, is precisely the
condition that the edge $(u,r_{(u,v)})\in E(\operatorname{Sub}(G))$ is sent to
an edge $(\phi(u),\chi(u,v))\in E(BC(f))$. Similar statements hold for events
$U^{-}(u,v),V^{+}(u,v),V^{-}(u,v)$.

Therefore, the above expression (7) is precisely the following:

$\displaystyle\operatorname{em}_{\phi}(G,RHG(d,f))$
$\displaystyle=\operatorname{\mathbb{E}}_{\chi\mathrel{\mathop{\ordinarycolon}}E(G)\hookrightarrow\mathbb{F}_{2}^{n}}\prod_{r_{(u,v)}\in
R(\operatorname{Sub}(G))}\bigg{(}1-[U^{-}(u,v)]-[V^{-}(u,v)]+2[U^{-}(u,v)][V^{-}(u,v)]\bigg{)}$

as each edge in $G$ now corresponds to a unique right vertex in
$\operatorname{Sub}(G)$. By Lemma 5.11, we can expand the product as follows:

$\displaystyle\operatorname{em}_{\phi}(G,RHG(d,f))$
$\displaystyle=\operatorname{\mathbb{E}}_{\chi\mathrel{\mathop{\ordinarycolon}}E(G)\hookrightarrow\mathbb{F}_{2}^{n}}\sum_{H\mathrel{\mathop{\ordinarycolon}}H\leq\operatorname{Sub}(G)}2^{\mathinner{\\!\left\lvert
D_{2}(H)\right\rvert}}(-1)^{\mathinner{\\!\left\lvert
D_{1}(H)\right\rvert}}\prod_{(l,r)\in
H}[\phi(l)\underset{BC(f)}{\sim}\chi(r)]$
$\displaystyle=\sum_{H\mathrel{\mathop{\ordinarycolon}}H\leq\operatorname{Sub}(G)}2^{\mathinner{\\!\left\lvert
D_{2}(H)\right\rvert}}(-1)^{\mathinner{\\!\left\lvert
D_{1}(H)\right\rvert}}\operatorname{\mathbb{E}}_{\chi\mathrel{\mathop{\ordinarycolon}}E(G)\hookrightarrow\mathbb{F}_{2}^{n}}\prod_{(l,r)\in
H}[\phi(l)\underset{BC(f)}{\sim}\chi(r)]$ (8)

Define

$X=\mathinner{\\!\left\lvert\sum_{H\mathrel{\mathop{\ordinarycolon}}H\leq\operatorname{Sub}(G)}2^{\mathinner{\\!\left\lvert
D_{2}(H)\right\rvert}}(-1)^{\mathinner{\\!\left\lvert
D_{1}(H)\right\rvert}}\left(\left(\operatorname{\mathbb{E}}_{\chi\mathrel{\mathop{\ordinarycolon}}E(G)\hookrightarrow\mathbb{F}_{2}^{n}}\prod_{(l,r)\in
H}[\phi(l)\underset{BC(f)}{\sim}\chi(r)]\right)-p^{\mathinner{\\!\left\lvert
D_{2}(H)\right\rvert}}q^{\mathinner{\\!\left\lvert
D_{1}(H)\right\rvert}}\right)\right\rvert}$

Now will simplify $X$ in two ways. By Equation (8), we have

$\displaystyle X$
$\displaystyle=\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{\chi\mathrel{\mathop{\ordinarycolon}}E(G)\hookrightarrow\mathbb{F}_{2}^{n}}\sum_{H\mathrel{\mathop{\ordinarycolon}}H\leq\operatorname{Sub}(G)}2^{\mathinner{\\!\left\lvert
D_{2}(H)\right\rvert}}(-1)^{\mathinner{\\!\left\lvert
D_{1}(H)\right\rvert}}\left(\left(\prod_{(l,r)\in
H}[\phi(l)\underset{BC(f)}{\sim}\chi(r)]\right)-p^{\mathinner{\\!\left\lvert
D_{2}(H)\right\rvert}}q^{\mathinner{\\!\left\lvert
D_{1}(H)\right\rvert}}\right)\right\rvert}$
$\displaystyle=\mathinner{\\!\left\lvert\operatorname{em}_{\phi}(G,RHG(d,f))-\sum_{H\mathrel{\mathop{\ordinarycolon}}H\leq\operatorname{Sub}(G)}(2p)^{\mathinner{\\!\left\lvert
D_{2}(H)\right\rvert}}(-q)^{\mathinner{\\!\left\lvert
D_{1}(H)\right\rvert}}\right\rvert}$
$\displaystyle=\mathinner{\\!\left\lvert\operatorname{em}_{\phi}(G,RHG(d,f))-\sum_{H\mathrel{\mathop{\ordinarycolon}}H\leq\operatorname{Sub}(G)}\left(\frac{1}{2}-\widehat{f}\left(0\right)\right)^{\mathinner{\\!\left\lvert
D_{2}(H)\right\rvert}}\left(-\frac{1}{2}+\frac{\widehat{f}\left(0\right)}{2}\right)^{\mathinner{\\!\left\lvert
D_{1}(H)\right\rvert}}\right\rvert}$

We are now in a situation to apply Lemma 5.11 with
$x=\frac{1}{2}-\widehat{f}\left(0\right)$ and
$y=z=-\frac{1}{2}+\frac{\widehat{f}\left(0\right)}{2}$.

$\displaystyle=\mathinner{\\!\left\lvert\operatorname{em}_{\phi}(G,RHG(d,f))-\prod_{r_{(u,v)}\in
R(\operatorname{Sub}(G))}\left(1+2(-\frac{1}{2}+\frac{\widehat{f}\left(0\right)}{2})+\frac{1}{2}-\widehat{f}\left(0\right)\right)\right\rvert}$
$\displaystyle=\mathinner{\\!\left\lvert\operatorname{em}_{\phi}(G,RHG(d,f))-2^{-\mathinner{\\!\left\lvert
E(G)\right\rvert}}\right\rvert}$

where we use the fact that $\mathinner{\\!\left\lvert
R(\operatorname{Sub}(G))\right\rvert}=\mathinner{\\!\left\lvert
E(G)\right\rvert}$. On the other hand, the triangle inequality gives us that

$\displaystyle X$
$\displaystyle\leq\sum_{H\mathrel{\mathop{\ordinarycolon}}H\leq\operatorname{Sub}(G)}2^{\mathinner{\\!\left\lvert
D_{2}(H)\right\rvert}}\mathinner{\\!\left\lvert\left(\left(\operatorname{\mathbb{E}}_{\chi\mathrel{\mathop{\ordinarycolon}}E(G)\hookrightarrow\mathbb{F}_{2}^{n}}\prod_{(l,r)\in
H}[\phi(l)\underset{BC(f)}{\sim}\chi(r)]\right)-p^{\mathinner{\\!\left\lvert
D_{2}(H)\right\rvert}}q^{\mathinner{\\!\left\lvert
D_{1}(H)\right\rvert}}\right)\right\rvert}$
$\displaystyle\leq\epsilon(5/2+\widehat{f}\left(0\right))^{-\mathinner{\\!\left\lvert
E(G)\right\rvert}}\sum_{H\mathrel{\mathop{\ordinarycolon}}H\leq\operatorname{Sub}(G)}(2p)^{\mathinner{\\!\left\lvert
D_{2}(H)\right\rvert}}q^{\mathinner{\\!\left\lvert D_{1}(H)\right\rvert}}$ (9)
$\displaystyle=\epsilon(5/2+\widehat{f}\left(0\right))^{-\mathinner{\\!\left\lvert
E(G)\right\rvert}}\left(1+2q+2p\right)^{\mathinner{\\!\left\lvert
E(G)\right\rvert}}$ (10) $\displaystyle\leq\epsilon$

where we use the fact that $f$ satisfies the Degree-$2$-Homomorphisms Property
of rank $d$ with error bound
$\epsilon\left(\frac{5}{2}+\widehat{f}\left(0\right)\right)^{-\mathinner{\\!\left\lvert
E(G)\right\rvert}}$ in line (9) and Lemma 5.11 in line (10). Putting these two
expansions of $X$ together, we find that

$\mathinner{\\!\left\lvert\operatorname{em}_{\phi}(G,RHG(d,f))-2^{-\mathinner{\\!\left\lvert
E(G)\right\rvert}}\right\rvert}<\epsilon$

Thus $f$ also satisfies the Rainbow Embeddings Property $RAIN(d,\epsilon)$. ∎

######  Theorem 5.13.

For any fixed $d\geq 1$ and $\epsilon>0$, the Rainbow Embeddings Property
$RAIN(d,\epsilon)$ implies the Balanced Influences Property $INF(d,\epsilon)$.

###### Proof.

Suppose $f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$
satisfies the Rainbow Embeddings Property $RAIN(d,\epsilon)$. Fix $u\in
B_{d}(n,0)$, and let $\phi$ be an injection from $V(K_{2})$ to $\\{u,0\\}$. By
definition of rainbow embeddings, we have

$\displaystyle\operatorname{em}_{\phi}(K_{2},RHG(d,f))$
$\displaystyle=\operatorname{\mathbb{E}}_{\chi\mathrel{\mathop{\ordinarycolon}}E(K_{2})\to\mathbb{F}_{2}^{n}}[(u,0,\chi(e))\in
E(RHG(d,f))]$ Setting $x=\chi(e)$ and applying the definition of the edge set
of $RHG(f)$ $\displaystyle\operatorname{em}_{\phi}(K_{2},RHG(d,f))$
$\displaystyle=\operatorname{\mathbb{E}}_{x\in\mathbb{F}_{2}^{n}}[f(u+x)=f(x)]$
$\displaystyle=\operatorname{\mathbb{P}}_{x\in\mathbb{F}_{2}^{n}}\left[f(x+u)=f(x)\right]$
$\displaystyle=1-\operatorname{I}_{u}[f]$

By Property $RAIN(d,\epsilon)$, we have that
${\operatorname{em}_{\phi}(K_{2},RHG(d,f))-\frac{1}{2}}<\epsilon$. Hence, it
follows that
$\mathinner{\\!\left\lvert\operatorname{I}_{u}[f]-\frac{1}{2}\right\rvert}<\epsilon$
and $f$ also satisfies the Balanced Influences Property $INF(d,\epsilon)$. ∎

##  6 Constructions of Quasirandom Functions

In this section, we construct a large class of functions which separate the
Balanced Influences Property $INF(d+1,\epsilon)$ from
$INF(d,\epsilon^{\prime})$.

A $[n,k,d]$-binary linear code is a subspace
$\mathcal{C}\subseteq\mathbb{F}_{2}^{n}$ of dimension $k$ such that
$\min_{x\neq y}\mathinner{\\!\left\lvert x-y\right\rvert}=d$. An $[n,k,d]$
binary linear code may be specified by its parity check matrix
$M\in\mathbb{F}_{2}^{(n-k)\times n}$ which has the property that
$x\in\mathcal{C}\iff Mx=0$. Note that the parity check matrix has rank $n-k$.
We will need the following elementary fact regarding linear codes of distance
$d$.

######  Lemma 6.1.

[[28], Proposition 2.3.5] If $M$ is the parity check matrix of a code with
distance strictly greater than $d$, then any nonzero $x\in\ker(M)$ must have
$\mathinner{\\!\left\lvert x\right\rvert}>d$.

######  Example 6.2.

Let $\mathcal{C}$ be the $[7,4]$-Hamming code with parity check matrix $H$

$H=\begin{bmatrix}0&1&1&1&1&0&0&0\\\ 1&0&1&1&0&1&0&0\\\ 1&1&0&1&0&0&1&0\\\
1&1&1&0&0&0&0&1\end{bmatrix}$

One can check that no vector of Hamming weight $3$ or less can be an element
of the kernel, as every set of $3$ columns has at least one row with an odd
number of $1$’s

The goal of this section is to demonstrate that a bent function composed with
the parity check matrix of a distance $d$ linear code is a quasi-random of
rank $d$ with error $0$.

###### Proof of Theorem (3.3).

Let $\mathcal{C}$ be an $[n,k,d]$ binary linear code such that $n-k$ is even
and $n\geq k+2$. Let $H\in\mathbb{F}_{2}^{(n-k)\times n}$ be a parity check
matrix for $\mathcal{C}$. Let
$g\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n-k}\to\\{1,-1\\}$ be a
bent function, and
define$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ by

$f(x)\mathrel{\mathop{\ordinarycolon}}=g(Hx).$

We claim that

$\operatorname{I}_{\gamma}[f]=\begin{cases}\frac{1}{2}&\gamma\notin\ker(H)\\\
0&\gamma\in\ker(H)\end{cases}$

Indeed, by Lemma (5.1), we have

$\displaystyle\operatorname{I}_{\gamma}[f]$
$\displaystyle=\frac{1}{2}-\frac{1}{2}f*f(\gamma)$
$\displaystyle=\frac{1}{2}-\frac{1}{2}\operatorname{\mathbb{E}}_{\delta\in\mathbb{F}_{2}^{n}}g(H\delta)g(H(\delta+\gamma))$
$\displaystyle=\frac{1}{2}-\frac{1}{2}\frac{2^{\operatorname{rank}(H)}}{2^{n}}\operatorname{\mathbb{E}}_{\eta\in\operatorname{Range}(H)}2^{\dim(\ker(H))}g(\eta)g(\eta+H\gamma)$
$\displaystyle=\frac{1}{2}-\frac{1}{2}\operatorname{\mathbb{E}}_{\eta\in\operatorname{Range}(H)}g(\eta)g(\eta+H\gamma)$
(11)

where we use the Rank-Nullity Theorem in line (11). As the parity check matrix
is a surjective linear map from $\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}^{n-k}$,
we have

$\displaystyle\operatorname{I}_{\gamma}[f]$
$\displaystyle=\frac{1}{2}-\frac{1}{2}\operatorname{\mathbb{E}}_{\eta\in\mathbb{F}_{2}^{n-k}}g(\eta)g(\eta+H\gamma)$
$\displaystyle=\begin{cases}\frac{1}{2}&\gamma\notin\ker(H)\\\
0&\gamma\in\ker(H)\end{cases}$ (12)

where we use Lemma (2.10) in line (12). Now we can apply Lemma (6.1) to
conclude that if $\mathinner{\\!\left\lvert\gamma\right\rvert}\leq d$,
$\gamma\notin\ker(H)$. It follows that
$\operatorname{I}_{\gamma}[f]=\frac{1}{2}$ for every
$\gamma\in\mathbb{F}_{2}^{n}$ with
$0<\mathinner{\\!\left\lvert\gamma\right\rvert}\leq d$.

All that remains is to show that
$\mathinner{\\!\left\lvert\widehat{f}\left(0\right)\right\rvert}<\frac{1}{2}$.
To that end we observe

$\widehat{f}\left(0\right)=\operatorname{\mathbb{E}}_{x\in\mathbb{F}_{2}^{n}}g(Hx)=\frac{2^{\dim(\ker(H))}2^{n-k}}{2^{n}}\operatorname{\mathbb{E}}_{y\in\mathbb{F}_{2}^{n-k}}g(y)$

by the same reasoning as in line (11) above. Since $g$ is bent, it follows
that

$\mathinner{\\!\left\lvert\widehat{f}\left(0\right)\right\rvert}=\mathinner{\\!\left\lvert\widehat{g}\left(0\right)\right\rvert}=2^{-\frac{n-k}{2}}.$

As $n\geq k+2$, we conclude that
$\mathinner{\\!\left\lvert\widehat{f}\left(0\right)\right\rvert}\leq\frac{1}{2}$
and $INF(d,0)$ holds for $f$.

Similarly, as $\mathcal{C}$ has distance $d+1$, there is some
$\gamma^{\prime}\in\mathbb{F}_{2}^{n}$ with Hamming weight $d+1$ such that
$H\gamma^{\prime}=0$. Hence, $\operatorname{I}_{\gamma^{\prime}}[f]=0$ by
equation (12) above. Thus $INF(d+1,\epsilon)$ cannot hold for $f$ unless
$\epsilon\geq\frac{1}{2}$. ∎

######  Remark 6.3.

For $r$ even, let $\mathcal{C}$ be the Hamming code $[2^{r},2^{r}-r-1,3]$, and
let $H\in\mathbb{F}_{2}^{r\times 2^{r}-1}$ be its parity check matrix as in
Example 6.2. Let
$IP\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{r}\to\\{1,-1\\}$ be the
inner product function defined in Example (2.11) and define
$f(x)\mathrel{\mathop{\ordinarycolon}}=IP(Hx)$. Then, $f$ has the property
that $f*f(x)=\begin{cases}-1&x\in\mathcal{C}\\\
1&x\notin\mathcal{C}\end{cases}$

##  7 Proofs of relations among extant Quasirandomness Theories for Boolean
Functions

We will prove a series of lemmas which together separate and relate the
classes of quasirandom boolean functions defined in section §4.

######  Lemma 7.1.

If $f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ has the
Balanced Influences property $INF(d,\epsilon/2)$, then $f$ is
$(\sqrt{2^{-d}+\epsilon},n)$ $\mathbb{R}$-Regular.

###### Proof.

By Theorem 5.2, if $f$ has the Balanced Influences Property
$INF(d,\epsilon/2)$, then $f$ has the Spectral Discrepancy Property
$SD(d,\epsilon)$. Fix $\gamma\in\mathbb{F}_{2}^{n}$ and let $C(S,z)$ be a
subcube of dimension $n-d$ which contains $\gamma$. By $SD(d,\epsilon)$,

$\widehat{f}\left(\gamma\right)^{2}\leq\sum_{\delta\in
C(S,z)}\widehat{f}\left(\delta\right)^{2}\leq 2^{-d}+\epsilon.$

Therefore,
$\mathinner{\\!\left\lvert\widehat{f}\left(\gamma\right)\right\rvert}\leq\sqrt{2^{-d}+\epsilon}$
for every $\gamma\in\mathbb{F}_{2}^{n}$. ∎

######  Lemma 7.2.

For even $n$, there is a function
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ which has
$INF(d,0)$ for every $d\leq n$, but $\|f\|_{U(3)}=1$.

###### Proof.

Consider the Inner Product function
$IP(x)\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$
defined in Example 2.11. As shown in the example, $IP$ is a bent function and
therefore has the property $INF(d,2^{-n/2})$ for every $1\leq d\leq n$.
However, $IP$ has $\mathbb{F}_{2}$-Degree $2$. Since $\|g\|_{U(d+1)}=1$ if $g$
has $\mathbb{F}_{2}$-degree $d$ [27], we conclude that $\|IP\|_{U(3)}=1$. ∎

######  Lemma 7.3.

Let $g\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ be a
boolean function. Let $M\in\mathbb{F}_{2}^{(n+1)\times n}$ be the projection
matrix which sends $x\in\mathbb{F}_{2}^{n+1}$ to its first $n$ coordinates,
and let $w\in\mathbb{F}_{2}^{n+1}$ be the vector with a single $1$ in the
$n+1$st coordinate. Let
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n+1}\to\\{1,-1\\}$ be
defined by $f(x)=g(Mx)$. If $g$ is $(\epsilon,k)$ $\mathbb{F}_{2}$-Regular,
then

  * •

$f$ is $(\epsilon,k)$ $\mathbb{F}_{2}$-Regular

  * •

$\operatorname{I}_{w}[f]=0$.

###### Proof.

We first show that $f$ is $(\epsilon,k)$ $\mathbb{F}_{2}$-Regular. To that
end, we have

$\displaystyle\|f\|_{U(k)}$
$\displaystyle=\left(\operatorname{\mathbb{E}}_{x\in\mathbb{F}_{2}^{n}}\operatorname{\mathbb{E}}_{N\in\mathbb{F}_{2}^{n\times
k}}\prod_{v\in\mathbb{F}_{2}^{k}}f(x+Nv)\right)^{2^{-k}}$
$\displaystyle=\left(\operatorname{\mathbb{E}}_{x\in\mathbb{F}_{2}^{n}}\operatorname{\mathbb{E}}_{N\in\mathbb{F}_{2}^{n\times
k}}\prod_{v\in\mathbb{F}_{2}^{k}}g(M(x+Nv))\right)^{2^{-k}}$
$\displaystyle=\left(\operatorname{\mathbb{E}}_{x\in\mathbb{F}_{2}^{n}}\operatorname{\mathbb{E}}_{N\in\mathbb{F}_{2}^{n\times
k}}\prod_{v\in\mathbb{F}_{2}^{k}}g(Mx+MNv)\right)^{2^{-k}}$
$\displaystyle=\left(\frac{2^{k+1}2^{(n-1)(k+1)}}{2^{n(k+1)}}\operatorname{\mathbb{E}}_{y\in\mathbb{F}_{2}^{n-1}}\operatorname{\mathbb{E}}_{P\in\mathbb{F}_{2}^{n-1\times
k}}\prod_{v\in\mathbb{F}_{2}^{k}}g(y+Pv)\right)^{2^{-k}}$ (13)
$\displaystyle=\|g\|_{U(k)}$ (14) $\displaystyle\leq\epsilon$ (15)

where we use the fact that $M$ is a projection in line (13), and use our
assumption on $g$ in line (14). Thus $f$ is $(\epsilon,k)$
$\mathbb{F}_{2}$-Regular.

For the second claim, we observe that $f(x+w)=f(x)$ for every $x$. Therefore,
$\operatorname{I}_{w}[f]=0$. It follows that $f$ cannot have $INF(d,\epsilon)$
for any $d\geq 1$ and $\epsilon<\frac{1}{2}$. ∎

Now we can prove each of theorems relating our properties to extant theories.

###### Proof of Theorem (4.2).

We have three claims to prove. First, we consider the relationship between
$(\epsilon,n)$ Balanced Influences and $(\epsilon,1)$
$\mathbb{F}_{2}$-Regularity. Let
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ satisfy
$INF(d,\epsilon)$. By Lemma 7.3, $f$ is $(\sqrt{2^{-d}+\epsilon},n)$
$\mathbb{R}$-regular. By Proposition 6.7 in O’Donnell’s book [20],
$(\epsilon,1)$ $\mathbb{F}_{2}$-Regularity is equivalent to $(\epsilon,n)$
$\mathbb{R}$-Regularity. Thus, $f$ is $(\sqrt{2^{-d}+\epsilon},1)$
$\mathbb{F}_{2}$-Regular.

Now we show that $(\epsilon,k)$ Balanced Influences is comparable with
$(\epsilon,d)$ $\mathbb{F}_{2}$-Regularity for $d>1$ and any $k$. First we
show that Balanced Influences $INF(d,\epsilon)$ cannot imply $(\epsilon,2)$
$\mathbb{F}_{2}$-Regularity. Lemma 7.2 provides a bent function $f$ such that
$\|f\|_{U(3)}=1$. It follows that the class of bent functions is distinct from
$(\epsilon,d)$ $\mathbb{F}_{2}$-Regular functions for any $d\geq 2$ and
$\epsilon<1$. Since every Bent function satisfies $INF(k,0)$ for any
$k\in\mathbb{N}$ with $1\leq k\leq n$, it follows that $INF(d,\epsilon)$
cannot imply $(\epsilon,2)$ $\mathbb{F}_{2}$-Regularity.

Now we can show that $(\epsilon,d)$ $\mathbb{F}_{2}$-Regularity cannot imply
$(\epsilon,k)$ Balanced Influences for any $k\geq 1$. Let
$g\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ be
quadratic residue function considered in Example 4.12 of [21]. For any
$\epsilon>0$, there is $n$ sufficiently large such that $g$ is $(\epsilon,k)$
$\mathbb{F}_{2}$-Regular. By lemma 7.1 applied to $g$, we find an
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n+1}\to\\{1,-1\\}$ which is
$(\epsilon,k)$ $\mathbb{F}_{2}$-Regular yet there is a vector
$w\in\mathbb{F}_{2}^{n+1}$ such that $\operatorname{I}_{w}[f]=0$. Thus, $f$
cannot have the Balanced Influences Property $INF(k,\epsilon)$ for any $k\geq
1$ and $\epsilon<1$.

It follows that $(\epsilon,k)$ $\mathbb{F}_{2}$-Regularity and Quasirandomness
of rank $d$ with error $\epsilon$ are incomparable for $k\geq 2$ and $d\geq
1$. ∎

###### Proof of Theorem 4.3.

We have two claims to show. First, we prove that $(\delta,k)$ Balanced
Influences implies $(\epsilon,n)$ $\mathbb{R}$-Regularity. Lemma 7.1 implies
that if $f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$
has $INF(d,\epsilon)$, then $f$ is also $(\sqrt{2^{-d}+\epsilon},n)$
$\mathbb{R}$-Regular. Since $(\epsilon,k)$ $\mathbb{R}$-Regularity implies
$(\epsilon,k-1)$ $\mathbb{R}$-Regularity by definition, it follows that any
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ with
$(\epsilon,d)$ Balanced Influences also satisfies $(\epsilon,k)$
$\mathbb{R}$-Regularity for any $k\leq n$.

For the second claim, we must show that $(\epsilon,k)$ $\mathbb{R}$-Regularity
cannot imply $(\epsilon,d)$ Balanced Influences for any $k\leq n$, $d\geq 1$
or $\epsilon<1$. Consider the inner product function
$IP\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{2n}\to\\{1,-1\\}$ defined
in Example 1. By applying Lemma 7.3 to $IP$, we find an
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{2n+1}\to\\{1,-1\\}$ which
is $(2^{-n/2},n)$ $\mathbb{R}$-regular and yet does not have $INF(d,\epsilon)$
for any $d\geq 1$ and $\epsilon<\frac{1}{2}$. As $(\epsilon,n)$
$\mathbb{R}$-regularity implies $(\epsilon,k)$ $\mathbb{R}$-regularity for
$k<n$, it follows that $(\epsilon,k)$ $\mathbb{R}$-regularity does not imply
$INF(d,\epsilon)$ for any $k,d,\epsilon$. Thus $(\delta,k)$
$\mathbb{R}$-Regularity cannot imply $(\epsilon,d)$ Balanced Influences for
any $\delta>0$ or $k\leq n$. ∎

###### Proof of Theorem (4.6).

Assume $f$ satisfies $SD(d,\epsilon e^{(d-1)((\delta/2)-\ln(2))})$. We want
show that

$\operatorname{I}_{i}^{1-\delta}[f]=\sum_{\begin{subarray}{c}\gamma\in\mathbb{F}_{2}^{n}\\\
\gamma_{i}=1\end{subarray}}(1-\delta)^{\mathinner{\\!\left\lvert\gamma\right\rvert}-1}\widehat{f}\left(\gamma\right)^{2}$

is at most $\epsilon$. We observe that the set of
$\gamma\in\mathbb{F}_{2}^{n}$ with $\gamma_{i}=1$ is precisely the
$n-1$-dimensional subcubes $C(\\{i\\},1)$, and the same subcube may be divided
into $2^{d-1}$ subcubes of dimension $n-d$ follows. Pick a set $S$ of size $d$
such that $\\{i\\}\subset S\subset[n]$. Then,
$C(\overline{\\{i\\}},1)=\bigsqcup_{\begin{subarray}{c}z\in\mathbb{F}_{2}^{S}\\\
z_{i}=1\end{subarray}}C(S,z)$. Therefore,

$\displaystyle\operatorname{I}_{i}^{1-\delta}[f]$
$\displaystyle=\sum_{\begin{subarray}{c}\gamma\in\mathbb{F}_{2}^{n}\\\
\gamma_{i}=1\end{subarray}}(1-\delta)^{\mathinner{\\!\left\lvert\gamma\right\rvert}-1}\widehat{f}\left(\gamma\right)^{2}$
$\displaystyle=\sum_{\begin{subarray}{c}z\in\mathbb{F}_{2}^{S}\\\
z_{i}=1\end{subarray}}\sum_{\gamma\in
C(S,z)}(1-\delta)^{\mathinner{\\!\left\lvert\gamma\right\rvert}-1}\widehat{f}\left(\gamma\right)^{2}$
$\displaystyle\leq\sum_{\begin{subarray}{c}z\in\mathbb{F}_{2}^{S}\\\
z_{i}=1\end{subarray}}\left(\max_{\gamma\in
C(S,z)}(1-\delta)^{\mathinner{\\!\left\lvert\gamma\right\rvert}-1}\right)\sum_{\gamma\in
C(S,z)}\widehat{f}\left(\gamma\right)^{2}$ $\displaystyle\leq\epsilon
e^{(d-1)((\delta/2)-\ln(2))}\sum_{\begin{subarray}{c}z\in\mathbb{F}_{2}^{S}\\\
z_{i}=1\end{subarray}}\left(\max_{\gamma\in
C(S,z)}(1-\delta)^{\mathinner{\\!\left\lvert\gamma\right\rvert}-1}\right)$

where we use $SD(d,\epsilon e^{(d-1)((\delta/2)-\ln(2))})$ in the ultimate
line. Now we can simplify the result further:

$\displaystyle\operatorname{I}_{i}^{1-\delta}[f]$ $\displaystyle\leq\epsilon
e^{(d-1)((\delta/2)-\ln(2))}\sum_{\begin{subarray}{c}z\in\mathbb{F}_{2}^{S}\\\
z_{i}=1\end{subarray}}(1-\delta)^{\mathinner{\\!\left\lvert z\right\rvert}-1}$
$\displaystyle=\epsilon
e^{(d-1)((\delta/2)-\ln(2))}\left(\sum_{j=0}^{d-1}\binom{d-1}{j}(1-\delta)^{j}\right)$
$\displaystyle=\epsilon e^{(d-1)((\delta/2)-\ln(2))}(2-\delta)^{d-1}$
$\displaystyle=\epsilon
e^{(d-1)(\delta/2)}\left(1-\frac{\delta}{2}\right)^{d-1}$
$\displaystyle\leq\epsilon$

where we use $(1+x)\leq e^{x}$ in the final line. Thus $f$ has
$(\epsilon,\delta)$-Small Stable Influences.

Conversely, one can easily verify that $\chi_{\mathbf{1}}$ has
$((1-\delta)^{n},\delta)$-Small Stable Influences, but
$\operatorname{I}_{\gamma}[\chi_{\mathbf{1}}]=1$ for every
$\gamma\in\mathbb{F}_{2}^{n}$ with Hamming weight $1$. Thus
$\chi_{\mathbf{1}}$ does not have $INF(d,\epsilon)$ for any $d\geq 1$ unless
$\epsilon=\frac{1}{2}$. ∎

The relationship between $\mathbb{Z}/2^{n}\mathbb{Z}$ Regularity and the other
theories is more intricate than our other theories of quasi-randomness,
largely due to the algebraic differences between $\mathbb{Z}/2^{n}\mathbb{Z}$
and $\mathbb{F}_{2}^{n}$. As boolean functions in the sense of
$\mathbb{Z}/2^{n}\mathbb{Z}$-Regularity are not functions on
$\mathbb{F}_{2}^{n}$, we have the following definition to transfer results
between these two theories:

######  Definition 7.4.

Given $z\in\mathbb{Z}/2^{n}\mathbb{Z}$, let $z^{*}\in\mathbb{F}_{2}^{n}$
denote the vector such that

$z_{i}^{*}=a_{i}$

where $z=\sum_{i=1}^{n}a_{i}2^{i-1}$ is the binary expansion of $z$.

Chung and Graham [[5], Prop. 6.2] prove the following result, translated into
our notation:

######  Lemma 7.5.

[5] There is an absolute constant $C$ such that the function
$z\to\chi_{\mathbf{1}}(z^{*})$ is $\mathbb{Z}/2^{n}\mathbb{Z}$-Regular with
error bound $C\left(\dfrac{\sqrt{2+\sqrt{2}}}{2}\right)^{n}\approx 0.92^{n}$.

As $\chi_{\mathbf{1}}$ is a Fourier character, $\chi_{\mathbf{1}}$ cannot be
$(\epsilon,n)$ $\mathbb{R}$-Regular for any $\epsilon<1$. Thus for any
$\delta>0$, $\mathbb{Z}/2^{n}\mathbb{Z}$ Regularity with error bound $\delta$
does not imply $(\epsilon,n)$ $\mathbb{R}$-Regularity for any $\epsilon<1$.
Here we extend their result to show that $\mathbb{Z}/2^{n}\mathbb{Z}$
Regularity with error bound $\delta$ cannot even imply $(\epsilon,k)$
$\mathbb{R}$-Regularity for a wide range of $k<n$.

###### Proof of Theorem 4.4.

Set $k=\lceil-C_{0}\ln(\epsilon)\rceil$ for some absolute constant $C_{0}$ to
be defined later. Define $S=\\{1,\dots,n-k\\}$. Define
$\gamma\in\mathbb{F}_{2}^{n}$ by
$\gamma\mathrel{\mathop{\ordinarycolon}}=\mathbf{1}\underset{S}{\otimes}0$
where $\mathbf{1}\in\mathbb{F}_{2}^{S}$ is the all-ones vector and
$0\in\mathbb{F}_{2}^{\overline{S}}$ is the zero vector. We will show that
$\chi_{\gamma}$ is $\epsilon$ $\mathbb{Z}/2^{n}\mathbb{Z}$-Regular.

Define $\omega_{n}\mathrel{\mathop{\ordinarycolon}}=\exp\left(\dfrac{2\pi
i}{2^{n}}\right)$. Now let $c\in\mathbb{Z}/2^{n}\mathbb{Z}\setminus\\{0\\}$ be
arbitrary, and via the Euclidean algorithm, write $c=2^{k}a+b$ where $0\leq
b<2^{k}$. Then,

$\displaystyle\operatorname{\mathbb{E}}_{z\in\mathbb{Z}/2^{n}\mathbb{Z}}\chi_{\gamma}(z^{*})\omega_{n}^{-cz}$
$\displaystyle=\operatorname{\mathbb{E}}_{0\leq
y<2^{n-k}}\operatorname{\mathbb{E}}_{0\leq
x<2^{k}}\chi_{\gamma}(y^{*}\underset{S}{\otimes}x^{*})\omega_{n}^{-(2^{k}a+b)(2^{n-k}x+y)}$
We have
$\chi_{\gamma}(y^{*}\underset{S}{\otimes}x^{*})=\chi_{\mathbf{1}}(y^{*})\chi_{0}(x^{*})=\chi_{j}(y^{*})$
by definition of $\gamma$. Hence,
$\displaystyle=\operatorname{\mathbb{E}}_{0\leq
y<2^{n-k}}\operatorname{\mathbb{E}}_{0\leq
x<2^{k}}\chi_{\mathbf{1}}(y^{*})\omega_{n}^{-2^{n}ax-2^{n-k}xb-2^{k}ay-by}$
$\displaystyle=\operatorname{\mathbb{E}}_{0\leq
y<2^{n-k}}\operatorname{\mathbb{E}}_{0\leq
x<2^{k}}\chi_{\mathbf{1}}(y^{*})\omega_{n}^{-2^{n-k}xb-2^{k}ay-by}$
$\displaystyle=\operatorname{\mathbb{E}}_{0\leq
y<2^{n-k}}\chi_{\mathbf{1}}(y^{*})\omega_{n}^{-2^{k}ay-
by}\operatorname{\mathbb{E}}_{0\leq x<2^{k}}\omega_{n}^{-2^{n-k}xb}$
$\displaystyle=\operatorname{\mathbb{E}}_{0\leq
y<2^{n-k}}\chi_{\mathbf{1}}(y^{*})\omega_{n}^{-2^{k}ay-
by}\operatorname{\mathbb{E}}_{0\leq x<2^{k}}\omega_{k}^{-xb}$
$\displaystyle=\begin{cases}0&b\neq 0\\\ \operatorname{\mathbb{E}}_{0\leq
y<2^{n-k}}\chi_{\mathbf{1}}(y^{*})\omega_{n}^{-2^{k}ay}&b=0\end{cases}$
$\displaystyle=\begin{cases}0&b\neq 0\\\ \operatorname{\mathbb{E}}_{0\leq
y<2^{n-k}}\chi_{\mathbf{1}}(y^{*})\omega_{n-k}^{ay}&b=0\end{cases}$

We may now apply Lemma 7.5 so that

$\displaystyle\mathinner{\\!\left\lvert\operatorname{\mathbb{E}}_{z\in\mathbb{Z}/2^{n}\mathbb{Z}}\chi_{\gamma}^{*}(z)\omega_{n}^{-cz}\right\rvert}$
$\displaystyle\leq C\frac{\sqrt{2+\sqrt{2}}}{2}^{k}$ $\displaystyle\leq
C\left(\dfrac{\sqrt{2+\sqrt{2}}}{2}\right)^{-C_{0}\ln(\epsilon)}$
$\displaystyle=\epsilon$

where $C_{0}$ is a sufficiently large absolute constant. Thus
$z\to\chi_{\gamma}(z^{*})$ is $\epsilon$-$\mathbb{Z}/2^{n}\mathbb{Z}$ Regular.
However, $\mathinner{\\!\left\lvert\gamma\right\rvert}=n-k$, and so
$\chi_{\gamma}$ cannot be $(\epsilon,n-k+1)$ $\mathbb{R}$-Regular for any
$\epsilon<1$. Thus $\delta$-$\mathbb{Z}/2^{n}\mathbb{Z}$ Regularity does not
imply $(\epsilon,n-k)$ $\mathbb{R}$-Regularity for any $\epsilon<1$. ∎

##  8 Problems and remarks

Our proof of Theorem (3.3) provides a large class of examples of functions
which satisfy $INF(d,0)$ but not $INF(d+1,\epsilon)$ for $\epsilon$ small and
any $d\geq 1$. Furthermore, these functions have the property that $f*f(x)$ is
the indicator function for some binary linear code. Many questions remain,
some of which we include here.

######  Question 8.1.

Let $f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ be a
boolean function such that

$f*f(x)=[x\in\mathcal{C}]$

for some _nonlinear_ binary code $\mathcal{C}\subseteq\mathbb{F}_{2}^{n}$ of
distance $d$. Do such functions exist, and if so, is it true that $f$ has
$INF(d,0)$ but not $INF(d+1,\epsilon)$ for $\epsilon<\frac{1}{2}$?

######  Question 8.2.

Is there a classification of functions
$f\mathrel{\mathop{\ordinarycolon}}\mathbb{F}_{2}^{n}\to\\{1,-1\\}$ which
satisfy

$f*f(x)=[x\in\mathcal{C}]$

for some $[n,k,d]$ binary linear code
$\mathcal{C}\subseteq\mathbb{F}_{2}^{n}$?

We remark that any progress on this question will lead towards a solution of
the problem of enumerating bent functions.

There are several other interesting directions to consider.The relationship
between our work and $(\epsilon,d)$-$\mathbb{F}_{2}$-Regularity is summarized
in Figure 6.

$(\epsilon,1)$ $\mathbb{F}_{2}$-Regular$(\epsilon,2)$
$\mathbb{F}_{2}$-Regular$(\epsilon,d)$
$\mathbb{F}_{2}$-Regular$(\epsilon,1)$-Balanced
Influences$\vdots$$(\epsilon,n)$-Balanced InfluencesBent[21, 22][21, 22][21,
22]Theorem 4.2Def.Def.Def.Theorem 4.2Theorem 4.2Theorem 4.2 Figure 6: The
relationships between the properties in Theorem 3.2 and
$\mathbb{F}_{2}$-Regularity. Each arrow is a strict implication. Each arrow
which follows by definition has no label, and all other arrows have a label
with a reference to the proof of the implication. The results of this paper
are in bold blue text and dashed blue arrows. Incomparable properties are
linked by red dotted lines.

One can observe that our quasirandom theorem takes a new direction off
$(\epsilon,1)$-$\mathbb{F}_{2}$-Regularity in the quasirandom hierarchy
defined in [21]. One might ask if there is an analogue of these results for
the $i$th level of the same hierarchy. As the Balanced Influences Property
$INF(n,0)$ is equivalent to a function being bent, any analogue of our results
for higher levels may provide a “higher order” analogue of bent functions.
Such functions are likely to have very strong cryptographic properties and any
constructions of them would be interesting in their own right.

Finally, the relationship between quasirandomness over $\mathbb{F}_{2}^{n}$
and over $\mathbb{Z}/2^{n}\mathbb{Z}$ seems to be of particular interest. We
have the following conjecture, largely from numerical evidence:

######  Conjecture 8.3.

For any $\epsilon>0$, there is a $k=k(\epsilon)$ and a
$\delta=\delta(\epsilon)>0$ such that $(\delta,k)$-$\mathbb{R}$-regularity
implies $\epsilon$-$\mathbb{Z}/2^{n}\mathbb{Z}$-Regularity.

## References

  * [1] F. R. Chung, R. L. Graham, and R. M. Wilson, “Quasi-random graphs,” Combinatorica, vol. 9, pp. 345–362, 12 1989.
  * [2] S. Griffiths, “Quasi-Random Oriented Graphs,” Journal of Graph Theory, vol. 74, pp. 198–209, oct 2013.
  * [3] J. N. Cooper, “Quasirandom permutations,” Journal of Combinatorial Theory, Series A, vol. 106, pp. 123–143, 2004.
  * [4] F. R. Chung and R. L. Graham, “Quasi-random tournaments,” Journal of Graph Theory, vol. 15, pp. 173–198, 6 1991.
  * [5] F. R. Chung and R. L. Graham, “Quasi-random subsets of $\mathbb{Z}_{n}$,” Journal of Combinatorial Theory Series A, vol. 61, pp. 64–86, 9 1992.
  * [6] J. Friedman and A. Wigderson, On the second eigenvalue of hypergraphs.  Citeseer, 1989.
  * [7] Y. Kohayakawa, B. Nagle, V. Rödl, and M. Schacht, “Weak hypergraph regularity and linear hypergraphs,” Journal of Combinatorial Theory, Series B, vol. 100, pp. 151–160, 3 2010.
  * [8] J. Lenz and D. Mubayi, “Eigenvalues and linear quasirandom hypergraphs,” Forum of Mathematics, Sigma, vol. 3, p. 26, 1 2015.
  * [9] F. R. Chung and R. L. Graham, “Quasi‐random hypergraphs,” Random Structures and Algorithms, vol. 1, pp. 105–124, 1990.
  * [10] F. R. Chung, “Quasi-random classes of hypergraphs,” Random Structures and Algorithms, vol. 1, pp. 363–382, 12 1990.
  * [11] F. R. K. Chung and R. L. Graham, “Quasi-random set systems,” Journal of the American Mathematical Society, vol. 4, p. 151, 1 1991.
  * [12] F. R. K. Chung and R. L. Graham, “Cohomological aspects of hypergraphs,” 1992\.
  * [13] P. Frankl and V. Rödl, “The uniformity lemma for hypergraphs,” Graphs and Combinatorics, vol. 8, no. 4, pp. 309–312, 1992.
  * [14] V. Rödl and M. Schacht, “Regular partitions of hypergraphs: Counting lemmas,” Combinatorics Probability and Computing, vol. 16, pp. 887–901, 11 2007.
  * [15] V. Rödl and M. Schacht, “Regular partitions of hypergraphs: Regularity lemmas,” Combinatorics Probability and Computing, vol. 16, pp. 833–885, 11 2007.
  * [16] B. Nagle, V. Rödl, and M. Schacht, “The counting lemma for regular k-uniform hypergraphs,” Random Structures and Algorithms, vol. 28, pp. 113–179, 3 2006.
  * [17] Y. Kohayakawa and V. Rödl, “Szemerédi’s regularity lemma and quasi-randomness,” Recent Advances in Algorithms and Combinatorics, pp. 289–351, 2003.
  * [18] W. T. Gowers, “Quasirandomness, counting and regularity for 3-uniform hypergraphs,” Combinatorics Probability and Computing, vol. 15, pp. 143–184, 1 2006.
  * [19] W. T. Gowers, “Hypergraph regularity and the multidimensional szemerédi theorem,” Annals of Mathematics, vol. 166, pp. 897–946, 2007.
  * [20] R. O’Donnell, Analysis of Boolean Functions.  Cambridge University Press, 2014.
  * [21] D. Castro-Silva, “Quasirandomness in additive groups and hypergraphs,” 2021.
  * [22] F. R. Chung and P. Tetali, “Communication complexity and quasi randomness,” SIAM Journal on Discrete Mathematics, vol. 6, no. 1, pp. 110–123, 1993\.
  * [23] R. Aharoni, M. DeVos, S. G. H. de la Maza, A. Montejano, and R. Šámal, “A rainbow version of mantel’s theorem,” arXiv preprint arXiv:1812.11872, 2018.
  * [24] N. Alon and T. Marshall, “Homomorphisms of edge-colored graphs and coxeter groups,” 1998.
  * [25] O. S. Rothaus, “On “bent” functions,” Journal of Combinatorial Theory, Series A, vol. 20, pp. 300–305, may 1976.
  * [26] R. Forrié, “The strict avalanche criterion: Spectral properties of boolean functions and an extended definition,” in Advances in Cryptology — CRYPTO’ 88 (S. Goldwasser, ed.), (New York, NY), pp. 450–468, Springer New York, 1990.
  * [27] H. Hatami, P. Hatami, and S. Lovett, “Higher-order Fourier Analysis and Applications,” Foundations and Trends® in Theoretical Computer Science, vol. 13, no. 4, pp. 247–448, 2019.
  * [28] V. Guruswami, A. Rudra, and M. Sudan, Essential Coding Theory.  2019\.