DNF DNFs AC^0 TC^0 MAJ MUX NAE OR AND Tribes LocalCorrect sgn sparsity rank
span quasipoly Bias DTdepth DTsize PARITY Dict Corr avg smooth dist ETH

# Searching for Regularity in Bounded Functions

Siddharth Iyer
<EMAIL_ADDRESS>Research supported by NSF grant CCF-2131899 Michael
Whitmeyer
<EMAIL_ADDRESS>Research supported by NSF grant CCF-2006359.

###### Abstract

Given a function $f$ on $\mathbb{F}_{2}^{n}$, we study the following problem.
What is the largest affine subspace $\mathcal{U}$ such that when restricted to
$\mathcal{U}$, all the non-trivial Fourier coefficients of $f$ are very small?

For the natural class of bounded Fourier degree $d$ functions
$f:\mathbb{F}_{2}^{n}\to[-1,1]$, we show that there exists an affine subspace
of dimension at least $\widetilde{\Omega}(n^{1/d!}k^{-2})$, wherein all of
$f$’s nontrivial Fourier coefficients become smaller than $2^{-k}$. To
complement this result, we show the existence of degree $d$ functions with
coefficients larger than $2^{-d\log n}$ when restricted to any affine subspace
of dimension larger than $\Omega(dn^{1/(d-1)})$. In addition, we give explicit
examples of functions with analogous but weaker properties.

Along the way, we provide multiple characterizations of the Fourier
coefficients of functions restricted to subspaces of $\mathbb{F}_{2}^{n}$ that
may be useful in other contexts. Finally, we highlight applications and
connections of our results to parity kill number and affine dispersers.

##  1 Introduction

The search for structure within large objects is an old one that lies at the
heart of Ramsey theory. For example, a famous corollary of Ramsey’s theorem is
that any graph on $n$ vertices must contain a clique or an independent set of
size $\Omega(\log n)$. Another example is Roth’s111The related Hales-Jewett
theorem [HJ63] is also a classic result in Ramsey theory. theorem [Rot53] on
$3$-term arithmetic progressions, which essentially says that _every_ subset
of $\\{1,\ldots,n\\}$ of density $\delta>\Omega(1/\log\log n)$ must contain a
$3$-term arithmetic progression.222See also the recent quantitative
improvement due to Kelley and Meka [KM23] which gives the same result for all
subsets of density at least $\Omega(2^{-\log^{1/11}(n)})$

Szemerédi’s Regularity Lemma is also a well known example of this phenomenon.
Roughly speaking, it states that any graph $G$ can be partitioned into
$k:=M(\delta)$ parts $V_{1},\ldots,V_{k}$, wherein most pairs of parts
$(V_{i},V_{j})$ are $\delta$-regular. In this setting, the $\delta$-regularity
of $(V_{i},V_{j})$ roughly corresponds to saying that the bipartite graph
induced across $V_{i}$ and $V_{j}$ appears as though its edges were sampled
randomly. This powerful statement has found applications in both pure
mathematics (e.g., Szemerédi’s [Sze75] generalization of Roth’s result to
$k$-term arithmetic progressions) and theoretical computer science (to test
triangle-freeness in dense graphs [RS76, Alo+01, Sha06]).

Similar to the definition of regular partitions in Szemerédi’s Regularity
Lemma, one can also define a notion of regularity for functions. In
particular, for functions $f:\mathbb{F}_{2}^{n}\to\mathbb{R}$, we follow Green
[Gre05] and O’Donnell [ODo21] and define a function to be _$\delta$ -regular_
if all its nontrivial Fourier coefficients are at most $\delta$ in
magnitude.333For a formal definition, see Definition 2.6, and for more
background on Fourier analysis, see Section 2. This definition can be viewed
as a pseudorandomness condition; in particular, a randomly chosen Boolean
function $f:\mathbb{F}_{2}^{n}\to\\{\pm 1\\}$ is $\delta$-regular with very
high probability, even for $\delta=2^{-\Omega(n)}$.444See for example [ODo21],
Exercise 1.7 and Proposition 6.1.

The prior works surrounding graph regularity [Sze75, FK96, Sha06] and function
regularity [Gre05, Hos+16] have been concerned with obtaining $\delta$-regular
_partitions_ , which, roughly speaking, are partitions of the object at hand
into (mostly) pseudorandom parts. Often, these results have quite poor
dependencies on the parameter $\delta$ so as not to be practical for any
reasonably small value of $\delta$ (see Proposition 1.3 and Proposition 1.4
for detailed statements). Motivated by this, and by applications in
theoretical computer science, we relax our requirement and look to find just
_one_ $\delta$-regular part. Namely, we seek to understand the following
quantity:

$\mathsf{r}(f,\delta):=\min\\{\mathrm{codim}(\mathcal{U}):\mathcal{U}\text{ is
an affine subspace such that }f_{\mathcal{U}}\text{ is
}\delta\text{-regular}\\},$

where here and throughout this work $f_{\mathcal{U}}:\mathcal{U}\to\mathbb{R}$
denotes the restriction of $f$ to inputs coming from $\mathcal{U}$.

Before stating our main results as well as prior work, we make a few remarks
about the quantity $\mathsf{r}(f,\delta)$. In the special case when
$\delta=0$, the quantity $\mathsf{r}(f,0)$ has been previously studied in the
literature, under the name of _parity kill number_ [ODo+14]. This is the
smallest number of parities that need to be fixed in order to make $f$
constant. The value $\mathsf{r}(f,0)$ is also a measure associated with affine
dispersers, objects that have received significant attention in the study of
pseudorandomness, see e.g. [Sha11, Li16, CGL21, CT15, BK12]. An affine
disperser of dimension $k$ is a coloring of $\mathbb{F}_{2}^{n}$ such that no
affine subspace of dimension $k$ is monochromatic. If we view an affine
disperser as a function $f:\mathbb{F}_{2}^{n}\to\\{0,1,\ldots,C\\}$, then its
dimension is just $n-\mathsf{r}(f,0)+1$.

Now, we briefly discuss the bounds on $\mathsf{r}(f,\delta)$ most relevant to
our work. For a general function $f:\mathbb{F}_{2}^{n}\to[-1,1]$, it is known
that $\mathsf{r}(f,\delta)\leq 1/\delta$; this follows from a well-known
density-increment argument, see [Mes95] (for a short proof of this, see
Proposition 1.5). One might ask if $\mathsf{r}(f,\delta)$ is small when we
assume $f$ is structured, and a natural example of such functions is the class
of functions with low Fourier degree. For general degree $d$ functions
$f:\mathbb{F}_{2}^{n}\to[-1,1]$, the best bound on $\mathsf{r}(f,\delta)$
until this work was just the above mentioned bound of $1/\delta$. However, for
the class of degree $d$ Boolean functions, we know that
$\mathsf{r}(f,\delta)\leq\mathsf{r}(f,0)=O(d^{3})$; this follows from the
polynomial relationship between Fourier degree and decision tree depth, see
[Mid04], and [Ben17, Bd02] for surveys. We emphasize that this result relies
crucially on Booleanity (and is independent of $\delta$), and one can ask if
the more general class of degree $d$ functions bounded in the interval
$[-1,1]$ also have small $\mathsf{r}(f,\delta)$ values. Our main result
answers exactly this question, and provides an upper bound for
$\mathsf{r}(f,\delta)$ in this setting.

######  Theorem 1.1.

For any $\delta\in(0,1)$ and any degree $d$ function
$f:\mathbb{F}_{2}^{n}\to[-1,1]$, we have $\mathsf{r}(f,\delta)\leq
n-\Omega\left(n^{1/d!}(\log(n/\delta))^{-2}\right).$

Note that the general bound $\mathsf{r}(f,\delta)\leq 1/\delta$ that we
mentioned earlier, is only meaningful when $\delta>1/n$, however, our theorem
allows for $\delta$ to be much smaller. The regime of small $\delta$ is
particularly interesting from the perspective of pseudorandomness. Indeed, in
a qualitative sense, we see that by decreasing $\delta$, we are asking for
affine subspaces where the restricted function looks increasingly like a
random function. Using Theorem 1.1 together with our connection between
$\mathsf{r}(f,0)$ and the dimension of affine disperse, we obtain the
following corollary which says that low degree polynomials cannot serve as
good affine dispersers.

######  Corollary 1.2.

If $f:\mathbb{F}_{2}^{n}\to\\{0,\ldots,C\\}$ has Fourier degree $d$, then $f$
cannot be an affine disperser of dimension $k$ for any
$k\geq\Omega\left(n^{1/d!}(d+\log(nC))^{-2}\right)$.

##### Lower Bounds on $\mathsf{r}(f,\delta)$.

To complement Theorem 1.1, we present in Table 1 several examples of functions
(bounded as well as Boolean) for which $\mathsf{r}(f,\delta)$ is large. For
each row in the table, we exhibit a class of functions (whose degree and range
is as specified), such that for any $\delta^{\prime}\leq\delta$, _no_ affine
subspace of dimension larger than $n-\mathsf{r}(f,\delta)$ is
$\delta^{\prime}$-regular.

$\delta\leq$ | $\mathsf{r}(f,\delta)\geq$ | $\deg(f)$ | $\textrm{range}(f)$ | Ref.
---|---|---|---|---
$1/n$ | $n/2-1$ | 1 | $[-1,1]$ | Lemma 4.2
$\binom{n}{d}^{-1}$ | $n-2dn^{1/(d-1)}$ | $d$ | $[-1,1]$ | Lemma 4.3
$\Theta(n^{-1/2})$ | $\Theta(\sqrt{n})$ | $n$ | $\\{\pm 1\\}$ | Lemma 4.11
$\frac{1}{2}\cdot n^{-d}$ (for $d\leq\frac{\log n}{\log\log n+1}$) | $n-2dn^{1/(d-1)}$ | $\Omega(n)$ | $\\{\pm 1\\}$ | Corollary 4.7
$1/2^{2^{k}+1}$ (for integer $k$) | $\Omega\left((\log\frac{1}{\delta})^{\log_{2}(3)}\right)$ | $2^{k}$ | $\\{\pm 1\\}$ | Lemma 4.8
Table 1: Table of functions with large $\mathsf{r}(f,\delta)$ values.

Observe that Lemma 4.3 provides a somewhat of a converse to Theorem 1.1.
However there is a noticeable gap between the two results, and we conjecture
that Lemma 4.3 is closer to being tight, and that Theorem 1.1 could be
improved. We also note that Lemma 4.3 and Corollary 4.7 are not explicit – it
would be interesting to find more explicit examples.

###  1.1 Related Work

To the best of our knowledge, $\mathsf{r}(f,\delta)$ has not been explicitly
studied before. However, it is closely related to well-studied notions of
function regularity as well as the concepts of parity kill number and affine
dispersers. In this section, we give a detailed description of both these
connections.

##### Parity Kill Number and Affine Dispersers.

As we have already mentioned, $\mathsf{r}(f,0)$ has been studied under the
name of parity kill number, denoted $C_{\min}^{\oplus}[f]$ (see [ODo+14]).
Parity kill number can be considered as a further generalization of the
minimum certificate complexity of $f$, denoted $C_{\min}[f]$, which is the
minimum number of bits one must fix in order to make $f$ constant. In
particular, for any $\delta\geq 0$, we have
$\mathsf{r}(f,\delta)\leq\mathsf{r}(f,0)\leq C_{\min}[f]$. The minimum
certificate complexity is one of several natural complexity measures that have
been well studied for Boolean functions $f:\mathbb{F}_{2}^{n}\to\\{\pm 1\\}$
(see [Bd02, Ben17] for surveys).

As we have already alluded to, the quantity $\mathsf{r}(f,0)$ is also closely
related to efficacy of $f:\mathbb{F}_{2}^{n}\to\\{0,\ldots,C\\}$ as an affine
disperser. In the case of $C=1$, Cohen and Tal [CT15] rule out
$\mathbb{F}_{2}$-polynomials of degree $d$ as affine dispersers by showing
that any such function satisfies $\mathsf{r}(f,0)\leq n-\Omega(d\cdot
n^{1/(d-1)})$. This result resembles our Corollary 1.2; however, the two
results are incomparable for two reasons. First, degree $d$ functions over
$\mathbb{F}_{2}$ can have very large Fourier degree; moreover, the
corresponding result of [CT15] applies to functions whose range is
$\mathbb{F}_{2}$, while ours applies to functions that take values in the set
$\\{0,\ldots,C\\}$, which can have a much larger size. Furthermore, for
$f:\mathbb{F}_{2}^{n}\to\\{0,\ldots,C\\}$, a standard argument (analogous to
the one in [Mid04]) shows that $\mathsf{r}(f,0)\leq O(Cd^{3})$, where $d$ here
is the Fourier degree. However, this does not address the case where
$C=\Omega(n)$, which is when Corollary 1.2 becomes useful.

##### Pseudorandom Partitions.

As we have mentioned, much prior work on function regularity has been focused
on finding pseudorandom partitions of $\mathbb{F}_{2}^{n}$. To the best of our
knowledge, the earliest result in this direction is due to Green [Gre05];
below, the notation $\mathrm{twr}(x)$ refers to an exponential tower of 2’s
$2^{2^{\iddots}}$ of height $x$.

######  Proposition 1.3 (Theorem 2.1 in [Gre05]).

For any $f:\mathbb{F}_{2}^{n}\to\\{0,1\\}$ and $\delta>0$, there exists a
subspace $\mathcal{V}$ of co-dimension $M(\delta)\leq\mathrm{twr}(\lceil
1/\delta^{3}\rceil)$ such that for all but a $\delta$-fraction of the affine
subspaces $\mathcal{U}=\alpha+\mathcal{V}$, $f_{\mathcal{U}}$ is
$\delta$-regular.

In the same paper, Green showed that
$M(\delta)\geq\mathrm{twr}(\Omega(\log(1/\delta)))$ was necessary.
Subsequently, Hosseini et al. [Hos+16] exhibited a better counterexample
showing co-dimension $M(\delta)\geq\mathrm{twr}(\lceil 1/16\delta\rceil)$ is
required.

In the above upper and lower bound of [Gre05, Hos+16], the partition of
$\mathbb{F}_{2}^{n}$ is of a specific form – namely, it is every affine shift
of a given subspace. Given this observation, one can ask if there is a
partition of $\mathbb{F}_{2}^{n}$ into affine subspaces of smaller co-
dimension so that in most parts $f$ is $\delta$-regular. As the next
proposition, due to Girish et al. [Gir+21] shows, this is indeed the case.

######  Proposition 1.4 (Proposition A.1 in [Gir+21]).

For any $f:\mathbb{F}_{2}^{n}\to[0,1]$ and $\delta>0$, there exists a
partition $\Pi$ of $\mathbb{F}_{2}^{n}$, where every $\pi\in\Pi$ is an affine
subspace of co-dimension at most $\frac{1}{\delta^{3}}$ such that for all but
a $\delta$-fraction of the parts, $f_{\pi}$ is $\delta$-regular.

The proof of Proposition 1.4 is based on a simple algorithm that greedily
fixes the parities corresponding to the largest Fourier coefficients; it is
included in Appendix C for completeness.

Although, both these results partition $\mathbb{F}_{2}^{n}$ into several
affine subspaces where $f$ is $\delta$-regular, they are only meaningful when
$\delta$ is relatively large. Indeed, Proposition 1.3 is trivial when
$\delta<(\log^{*}(n))^{-1/3}$, and Proposition 1.4 when $\delta<n^{-1/3}$. As
we mentioned earlier, if we relax our requirement to finding just one affine
subspace, there is a simple upper bound on $\mathsf{r}(f,\delta)$ based on a
density-increment argument, which goes back to the works of Roth [Rot53] and
Meshulam [Mes95].

######  Proposition 1.5 (Folklore).

For any $f:\mathbb{F}_{2}^{n}\to[-1,1]$, we have
$\mathsf{r}(f,\delta)\leq\frac{1}{\delta}$.

We provide a proof of Proposition 1.5 in Appendix C for completeness.

###  1.2 Techniques

##### Upper bound on $\mathsf{r}(f,\delta)$.

We give a brief proof sketch of Theorem 1.1. The proof proceeds by induction
over the Fourier degree. The base case corresponds to degree one functions.
Our intuition is derived from the following fact. If we have any $k$ real
numbers $a_{1},\ldots,a_{k}$ such that the sum of any subset of them has
magnitude at most one, then by the pigeonhole principle, there is a non-empty
subset $S\subseteq[k]$, and a signing of the numbers in $S$ so that the signed
sum has magnitude at most $2^{-\Omega(k)}$. In the degree one case, we
partition $\\{1,\ldots,n\\}$ into consecutive disjoint intervals of size
$k=O(\log 1/\delta)$. We apply the above intuition to the $k$ Fourier
coefficients in each interval, to obtain signed sums that have small
magnitude. Then, by appropriately choosing an affine subspace, $\mathcal{U}$
of dimension $\Omega(n/\log(1/\delta))$, we show that these signed sums are
exactly the Fourier coefficients of the function restricted to $\mathcal{U}$
(see Proposition 2.8 for a more general statement). We give a more detailed
description of how this works in Section 3.

At a high level, we reduce the problem for degree $d$ functions to degree
$d-1$ by restricting to an affine subspace of dimension
$\widetilde{\Omega}\left(n^{1/d}\right)$, where the function is degree $d$ and
all Fourier coefficients at the $d$-th level are extremely small
$\ll\delta/n^{d}$. For a detailed statement, see Lemma 3.1. When we use the
inductive hypothesis for $d-1$, the last constraint ensures that the degree
$d$ coefficients cannot increase the new coefficients by more than
$O(\delta)$, even if they combine in the most constructive way possible.

Lemma 3.1 is also obtained by repeatedly applying the pigeonhole principle.
However, the key issue now is that several Fourier coefficients could be
affected when we apply a restriction, unlike the degree one case. To avoid
this, we apply restrictions iteratively so that each one preserves the small
Fourier coefficients from past iterations while still ensuring that _several_
new Fourier coefficients are also small. The cost of this procedure is that,
in each step, we must apply the pigeonhole principle over larger and larger
subsets of coordinates.

##### Lower Bounds.

Here, we give a very high level overview of our lower bounds on
$\mathsf{r}(f,\delta)$. The basic idea is to consider functions $f$ with the
property that their Fourier spectrum is concentrated on a small number of
Fourier coefficients. It turns out (see Proposition 2.8) that when we restrict
to an affine subspace, say $\mathcal{U}$, the Fourier coefficients of
$f_{\mathcal{U}}$ are simply signed sums of the Fourier coefficients of $f$.
By our choice of $f$, if the restricted function was $\delta$-regular, then
the large coefficients of $f$ involved in the signed sums somehow cancelled
each other out. We show that by choosing the vectors corresponding to the
large Fourier coefficients in $f$ appropriately, such a cancellation would
imply that the co-dimension of $\mathcal{U}$ must be large. For more detailed
sketches of the entries in Table 1, see Appendix A.

##  2 Preliminaries

##### Notation.

$\mathbbm{1}\\{\cdot\\}$ denotes an indicator function that takes the value 1
if the clause is satisfied and 0 otherwise. For a set $J\subseteq[n]$, we use
$\spn(J)$ to denote the subspace spanned by the standard basis vectors
corresponding to the elements in $J$. We refer to the $\text{L}_{1}$ norm of
$\gamma\in\mathbb{F}_{2}^{n}$ by $\|\gamma\|_{1}$. Given a subset
$S\subseteq\mathbb{F}_{2}^{n}$, we denote $S^{=t}:=S\cap\\{u:\|u\|_{1}=t\\}$.
Further, we define the degree of a function
$f:\mathbb{F}_{2}^{n}\rightarrow\mathbb{R}$ to be
$\max\\{\|\gamma\|_{1}:\widehat{f}(\gamma)\neq 0\\}$. We frequently interpret
a linear transformation $M:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}^{n}$ as a
matrix and refer to the linear map obtained by taking the transpose of the
matrix as $M^{\mathsf{T}}$. At several points, we consider the compositions of
functions with linear maps. For a function $f$ and a map
$M:\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2}^{n}$, we denote by $f\circ M$
the composition of the functions $f$ with $M$. In particular, $f\circ
M(x)=f(M(x))$.

##### Probability.

The following basic facts from probability theory are useful for us.

######  Fact 2.1 (Hoeffding, [Hoe63]).

Suppose $X_{1},\ldots,X_{n}$ are such that $a\leq X_{i}\leq b$ for all $i$.
Let $M=\frac{X_{1}+\ldots X_{n}}{n}$. Then,

$\mathop{\bf Pr\/}\Bigl{[}|M_{n}-\mathop{\bf E\/}M_{n}|\geq t\Bigr{]}\leq
2\exp\left(\frac{-2t^{2}n}{|b-a|}\right).$

######  Definition 2.2 (Statistical Distance).

Let $X$ and $Y$ be two random variables taking values in a set $\mathcal{S}$.
Then we define the statistical distance between $X$ and $Y$ as

$|X-Y|:=\max_{\mathcal{T}\subseteq\mathcal{S}}\Bigl{\lvert}\mathop{\bf
Pr\/}[X\in\mathcal{T}]-\mathop{\bf
Pr\/}[Y\in\mathcal{T}]\Bigr{\rvert}=\frac{1}{2}\sum_{s\in\mathcal{S}}\Bigl{\lvert}\mathop{\bf
Pr\/}[X=s]-\mathop{\bf Pr\/}[Y=s]\Bigr{\rvert}.$

##### Linear Algebra.

We recap two concepts from linear algebra, namely, orthogonal subspaces and
direct sum, since they become useful for studying the Fourier spectrum of
functions defined over subspaces of $\mathbb{F}_{2}^{n}$. For a subspace
$\mathcal{A}$ of $\mathbb{F}_{2}^{n}$, we denote the orthogonal subspace of
$\mathcal{A}$ as
$\mathcal{A}^{\perp}=\\{\gamma\in\mathbb{F}_{2}^{n}:\langle{\gamma,\gamma^{\prime}}\rangle=0,\>\forall\>\gamma^{\prime}\in\mathcal{A}\\}$.
We denote by $\dim(\mathcal{A})$, the dimension of $\mathcal{A}$ and
$\mathrm{codim}(\mathcal{A})=n-\dim(\mathcal{A})$.

We now define the notion of the direct sum of two subspaces.

######  Definition 2.3 (Independence, Direct Sum).

Two subspaces $\mathcal{A},\mathcal{B}$ are _independent_ if $a+b\neq 0$ for
any non-trivial choice of $a\in\mathcal{A}$ and $b\in\mathcal{B}$. In
addition, if $\\{a+b:a\in\mathcal{A}\text{ and
}b\in\mathcal{B}\\}=\mathbb{F}_{2}^{n}$, we say that $\mathbb{F}_{2}^{n}$ is a
_direct sum_ of $\mathcal{A}$ and $\mathcal{B}$, written as
$\mathcal{A}\oplus\mathcal{B}=\mathbb{F}_{2}^{n}$.555Such a subspace
$\mathcal{B}$ is sometimes called a complement of $\mathcal{A}$. However, this
term can be confused with the orthogonal subspace/complement, so we avoid
using this terminology.

If $\mathcal{A}\oplus\mathcal{B}=\mathbb{F}_{2}^{n}$, then
$\dim(\mathcal{A})+\dim(\mathcal{B})=n$. It is also well known that
$\dim(\mathcal{A}^{\perp})+\dim(\mathcal{A})=n$. Note, however, that
$\mathcal{A}^{\perp}$ and $\mathcal{A}$ need not be independent,666this might
be unexpected at first for those used to working over the reals, but it is
essentially because the inner product over $\mathbb{F}_{2}$ allows self-
orthogonal vectors in $\mathbb{F}_{2}^{n}$. and often in fact must not be.

######  Fact 2.4.

Let $\mathcal{A},\mathcal{B}$ be independent subspaces of
$\mathbb{F}_{2}^{n}$. Then for all distinct $b,b^{\prime}\in\mathcal{B}$, the
affine subspaces $b+\mathcal{A}$ and $b^{\prime}+\mathcal{A}$ are mutually
disjoint.

###### Proof.

If $b+a=b^{\prime}+a^{\prime}$, then a non-trivial sum of a vector from each
$\mathcal{A}$ and $\mathcal{B}$ equals zero, contradicting the fact that
$\mathcal{A}\oplus\mathcal{B}=\mathbb{F}_{2}^{n}$. ∎

##### Fourier Analysis.

For $f:\mathbb{F}_{2}^{n}\to\mathbb{R}$, we can write $f$ in the Fourier
representation as

$f(x)=\sum_{\gamma\in\mathbb{F}_{2}^{n}}\widehat{f}(\gamma)\chi_{\gamma}(x),$

where $\chi_{\gamma}(x):=(-1)^{\langle\gamma,x\rangle}$ and
$\widehat{f}(\gamma)=\mathop{\bf E\/}_{x}[f(x)\chi_{\gamma}(x)]$. We say $f$
has degree $d$ if $\max_{\gamma:\widehat{f}(\gamma)\neq 0}\|\gamma\|_{1}=d$,
and we refer to the degree $d$ part of $f$ by
$f^{=d}(x):=\sum_{\|\gamma\|_{1}=d}\widehat{f}(\gamma)\chi_{\gamma}(x)$. For
more on this topic, see [ODo21], which uses notation consistent with ours.

##### Restrictions.

We are ultimately concerned with understanding the Fourier coefficients of a
function when it is restricted to some affine subspace of
$\mathbb{F}_{2}^{n}$. In the special case where the coordinates in a set
$J\subseteq[n]$ are fixed using the vector $b\in\mathbb{F}_{2}^{J}$, we denote
the restriction of $f$ thus obtained as the function
${f}_{J\parbox{5.69046pt}{ \leavevmode\hbox to7.09pt{\vbox
to3.2pt{\pgfpicture\makeatletter\hbox{\hskip 1.19998pt\lower-1.59998pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{} {{}{}}{}{}{{
{\pgfsys@beginscope\pgfsys@setlinewidth{0.32pt}\pgfsys@setdash{}{0.0pt}\pgfsys@roundcap\pgfsys@roundjoin{}
{}{}{} {}{}{}
\pgfsys@moveto{-1.19998pt}{1.59998pt}\pgfsys@curveto{-1.09998pt}{0.99998pt}{0.0pt}{0.09999pt}{0.29999pt}{0.0pt}\pgfsys@curveto{0.0pt}{-0.09999pt}{-1.09998pt}{-0.99998pt}{-1.19998pt}{-1.59998pt}\pgfsys@stroke\pgfsys@endscope}}
}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b}:\spn(\overline{J})\rightarrow\mathbb{R}$,
which can be written as ${f}_{J\parbox{5.69046pt}{ \leavevmode\hbox
to6.09pt{\vbox to0.4pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b}(x)=f(x+b).$ Next,
we recall the formula of the Fourier coefficients of the restricted function.
Note that
$\\{\chi_{\gamma}(x):=(-1)^{\langle\gamma,x\rangle}:\gamma\in\spn(\overline{J})\\}$
is a Fourier basis of the restricted function.

######  Fact 2.5 (Fourier Coefficients of Restricted Functions (see [ODo21],
Proposition 3.21)).

For every $\gamma\in\spn(\overline{J})$ and $b\in\spn(J)$,

$\widehat{{f}_{J\parbox{5.69046pt}{ \leavevmode\hbox to6.09pt{\vbox
to0.4pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b}}(\gamma)=\sum_{\beta\in\spn(J)}\widehat{f}(\beta+\gamma)\chi_{\beta}(b).$

###  2.1 Fourier Analysis on Subspaces

We move to the general setting of restricting functions to arbitrary affine
subspaces.777For an arbitrary subspace $\mathcal{V}$, there is no canonical
mapping between vectors and characters when
$\mathcal{V}\neq\mathbb{F}_{2}^{n}$, and we cannot simply define the vectors
$\chi_{\gamma}$, for each $\gamma\in\mathcal{V}$, as we did in the case of
$\mathbb{F}_{2}^{n}$ to be the characters of $\mathcal{V}$. Let
$\mathcal{U}=\mathcal{V}+\alpha$ be an affine subspace of
$\mathbb{F}_{2}^{n}$. By the restriction of $f$ to $\mathcal{U}$, we mean the
function $f_{\mathcal{U}}:\mathcal{V}\rightarrow\mathbb{R}$ defined as
$f_{\mathcal{U}}(x)=f(x+\alpha).$

For the remainder of this section (and paper), let $\mathcal{W}$ be such that
$\mathcal{W}\oplus\mathcal{V}^{\perp}=\mathbb{F}_{2}^{n}$. For each element
$\gamma\in\mathcal{W}$, consider the function
$\chi_{\gamma}:\mathcal{V}\to\\{\pm 1\\}$ as
$\chi_{\gamma}(x)=(-1)^{\langle{\gamma,x}\rangle}$. It is easy to verify that
$\\{\chi_{\gamma}:\gamma\in\mathcal{W}\\}$ form an orthonormal basis of real-
valued functions defined over $\mathcal{V}$ under the inner product given by
$\langle{p,q}\rangle=\mathop{\bf E\/}_{x\in\mathcal{V}}[p(x)q(x)]$. We can
therefore uniquely associate each vector $\gamma\in\mathcal{W}$ with the
function $\chi_{\gamma}$, and for $\mathcal{U}=\alpha+\mathcal{V}$, we can
write

$\displaystyle
f_{\mathcal{U}}(x)=\sum_{\gamma\in\mathcal{W}}\widehat{f_{\mathcal{U}}}(\gamma)(-1)^{\langle{\gamma,x}\rangle}.$
(1)

We now state the formal definition of $\delta$-regularity.

######  Definition 2.6 ($\delta$-regularity).

Let $\mathcal{V}$ be a subspace of $\mathbb{F}_{2}^{n}$ and
$g:\mathcal{V}\to\mathbb{R}$. For $\delta\geq 0$, we say $g$ is
$\delta$-regular if $\max_{\gamma\neq
0}\left|\widehat{g}(\gamma)\right|\leq\delta$.

In this section, we present three separate formulas (2.7, Proposition 2.8 and
Proposition 2.11) for the Fourier coefficients of $f_{\mathcal{U}}$, each of
which is useful in different contexts.

First, using the above observations, we have the following simple formula for
the Fourier coefficients of $f_{\alpha+\mathcal{V}}$, which follows from the
orthogonality of the $\chi_{\gamma}$ we have defined.

######  Fact 2.7.

Let $\mathcal{V},\mathcal{W}$ be subspaces such that
$\mathcal{W}\oplus\mathcal{V}^{\perp}=\mathbb{F}_{2}^{n}$ and
$\mathcal{U}=\alpha+\mathcal{V}$. For any $\gamma\in\mathcal{W}$, we have that

$\widehat{f_{\mathcal{U}}}(\gamma)=\mathop{\bf
E\/}_{x\in\mathcal{V}}[f(x+\alpha)\cdot(-1)^{\langle{\gamma,x}\rangle}]=(-1)^{\langle{\gamma,\alpha}\rangle}\mathop{\bf
E\/}_{x\in\mathcal{U}}[f(x)\cdot(-1)^{\langle{\gamma,x}\rangle}].$

2.7 represents a simple and analogous formula for Fourier coefficients of
functions restricted to affine subspaces. It also highlights that the
magnitude of the Fourier coefficients of a restricted function are unaffected
by the choice for shift $\alpha$ as long it corresponds to the same affine
subspace.

Our next formula, which shows how the Fourier coefficients of
$f_{\mathcal{U}}$ can be written in terms of the Fourier coefficients of $f$,
is an easy consequence of 2.7.

######  Proposition 2.8.

Let $\mathcal{V},\mathcal{W}$ be subspaces such that
$\mathcal{W}\oplus\mathcal{V}^{\perp}=\mathbb{F}_{2}^{n}$ and
$\mathcal{U}=\alpha+\mathcal{V}$. For any $\gamma\in\mathcal{W}$, we have

$\widehat{f_{\mathcal{U}}}(\gamma)=\sum_{\beta\in\gamma+\mathcal{V}^{\perp}}\widehat{f}(\beta)\cdot(-1)^{\langle{\beta,\alpha}\rangle}.$

###### Proof.

Using 2.7, we can write

$\displaystyle\widehat{f_{\mathcal{U}}}(\gamma)=\mathop{\bf
E\/}_{x\in\mathcal{V}}[f(x+\alpha)\cdot(-1)^{\langle{\gamma,x}\rangle}]$
$\displaystyle=\mathop{\bf
E\/}_{x\in\mathcal{V}}\sum_{\beta}\widehat{f}(\beta)(-1)^{\langle{\beta,x+\alpha}\rangle}(-1)^{\langle{\gamma,x}\rangle}$
$\displaystyle=\sum_{\beta}\widehat{f}(\beta)(-1)^{\langle{\beta,\alpha}\rangle}\mathop{\bf
E\/}_{x\in\mathcal{V}}[(-1)^{\langle{\beta+\gamma,x}\rangle}]$
$\displaystyle=\sum_{\beta\in\gamma+\mathcal{V}^{\perp}}\widehat{f}(\beta)(-1)^{\langle{\beta,\alpha}\rangle},$

where the last equality follows by observing that $\mathop{\bf
E\/}_{x\in\mathcal{V}}\left[(-1)^{\langle{\gamma+\beta,x}\rangle}\right]=1$ if
$\beta\in\gamma+\mathcal{V}^{\perp}$, and zero otherwise. ∎

We note that Proposition 2.8 gives a formula analogous to 2.5 for restrictions
to general affine subspaces. This fact will be useful to construct functions
and argue that they never become $\delta$-regular when restricted to any
sufficiently large subspace. Before we give our final formula, we highlight
one particular choice of $\mathcal{W}$ such that
$\mathcal{W}\oplus\mathcal{V}^{\perp}=\mathbb{F}_{2}^{n}$.

######  Definition 2.9 ($M$ mapping $\mathcal{V}$ to $\spn(J)$).

Given a $k$-dimensional subspace $\mathcal{V}$, let
$B=\\{\beta_{1},\ldots,\beta_{n}\\}$ be a basis for $\mathbb{F}_{2}^{n}$ such
that $\mathcal{V}=\spn(\\{\beta_{1},\ldots,\beta_{k}\\}$. For any subset
$J\subseteq[n]$ of size $k$, let $M:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}^{n}$
be an invertible linear map such that $\\{M\beta_{i}:i\in[k]\\}=\\{e_{j}:j\in
J\\}$.

######  Proposition 2.10 (Choice of $\mathcal{W}$).

Let $\mathcal{V}$, $M$ and $J$ be defined as in Definition 2.9. The subspaces
$\mathcal{W}=\\{M^{\mathsf{T}}\gamma:\gamma\in\spn(J)\\}$ and
$\mathcal{V}^{\perp}$ are independent, and
$\mathcal{W}\oplus\mathcal{V}^{\perp}=\mathbb{F}_{2}^{n}$.

###### Proof.

We first show that $\mathcal{W}$ and $\mathcal{V}^{\perp}$ are independent.
Suppose that $M^{\mathsf{T}}\gamma+u=0$, where $\gamma\in\spn(J)$ and
$u\in\mathcal{V}^{\perp}$. For any $v\in\mathcal{V}$ such that $v\neq 0$, we
have

$0=\langle{v,M^{\mathsf{T}}\gamma+u}\rangle=\langle{v,M^{\mathsf{T}}\gamma}\rangle=\langle{Mv,\gamma}\rangle,$

which is impossible unless $\gamma=0$ since this implies
$Mv\in\spn(J)^{\perp}=\spn(\overline{J})$ and $Mv\neq 0$. This in turn implies
that $u=0$ and therefore that $\mathcal{W}$ and $\mathcal{V}^{\perp}$ are
independent. The claim follows by noting that
$\dim(\mathcal{W}\oplus\mathcal{V}^{\perp})=\dim(\mathcal{W})+\dim(\mathcal{V}^{\perp})=k+n-k=n$.
∎

Finally, we show that the Fourier coefficients of a function restricted to an
affine subspace are the same as the Fourier coefficients of the function
$f\circ M$ under a suitable (normal) restriction and for a particular choice
of $M$.

######  Proposition 2.11.

Let $\mathcal{V}$, $M$ and $J$ be defined as in Definition 2.9 and
$\mathcal{U}=\alpha+\mathcal{V}$. For any $\gamma\in\spn(J)$, we have
$\left|\widehat{f_{\mathcal{U}}}(M^{\mathsf{T}}\gamma)\right|=\left|\widehat{h_{\mathcal{U}^{\prime}}}(\gamma)\right|,$
where $h=f\circ M^{-1}$ and
$\mathcal{U}^{\prime}=\\{Mu:u\in\mathcal{U}\\}=M\alpha+\spn(J)$ is a standard
restriction.

###### Proof.

Repeatedly using 2.7, we have that

$\displaystyle\left|\widehat{f_{\mathcal{U}}}(M^{\mathsf{T}}\gamma)\right|=\Bigl{\lvert}\mathop{\bf
E\/}_{x\in\mathcal{U}}\left[f(x)(-1)^{\langle
M^{\mathsf{T}}\gamma,x\rangle}\right]\Bigr{\rvert}$
$\displaystyle=\Bigl{\lvert}\mathop{\bf
E\/}_{x\in\mathcal{U}}\left[f(x)(-1)^{\langle{\gamma,Mx}\rangle}\right]\Bigr{\rvert}$
$\displaystyle=\Bigl{\lvert}\mathop{\bf
E\/}_{z\in\mathcal{U}^{\prime}}\left[f(M^{-1}z)(-1)^{\langle{\gamma,z}\rangle}\right]\Bigr{\rvert}=\left|\widehat{g_{\mathcal{U}^{\prime}}}(\gamma)\right|.\qed$

Proposition 2.11 implies the following important corollary.

######  Corollary 2.12.

There exists an affine subspace $\mathcal{U}$ of dimension $k$ such that
$f_{\mathcal{U}}$ is $\delta$-regular if and only if there exists an
invertible linear map $M:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}^{n}$, a set
$J\subseteq[n]$ of size $k$, and a fixing of coordinates outside $J$ given by
$b\in\mathbb{F}_{2}^{\overline{J}}$ such that the function
${h}_{\overline{J}\parbox{5.69046pt}{ \leavevmode\hbox to6.09pt{\vbox
to0.4pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b}$ is
$\delta$-regular, where $h=f\circ M$.

We use Corollary 2.12 crucially in the proof of Theorem 1.1, wherein we
construct $M$ and $b$ such that ${f\circ M}_{\overline{[k]}\parbox{5.69046pt}{
\leavevmode\hbox to6.09pt{\vbox to0.4pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b}$ has small Fourier
coefficients. In the proof of this theorem we must understand the Fourier
coefficients of $f\circ M$ in terms of the Fourier coefficients of $f$. The
following fact gives an identity relating the Fourier coefficients of the two
functions.

######  Fact 2.13 ([ODo21], Exercise 3.1).

Let $M$ be an invertible linear transformation, and consider the function
$g=f\circ M^{-1}:\mathbb{F}_{2}^{n}\to\mathbb{R}$. Then we have that
$\widehat{g}(\gamma)=\widehat{f}(M^{\mathsf{T}}\gamma).$

###### Proof.

We have that

$\displaystyle\widehat{g}(\gamma)=\mathop{\bf E\/}_{x}[g(x)\chi_{\gamma}(x)]$
$\displaystyle=\mathop{\bf E\/}[f(Mx)\chi_{\gamma}(x)]$
$\displaystyle=\mathop{\bf E\/}_{y}[f(y)\chi_{\gamma}(M^{-1}y)]$
$\displaystyle=\mathop{\bf
E\/}_{y}[f(y)\chi_{M^{-\mathsf{T}}\gamma}(y)]=\widehat{f}(M^{-\mathsf{T}}\gamma),$

where we have used the fact that
$\chi_{\gamma}(M^{-1}y)=(-1)^{\langle{\gamma,M^{-1}y}\rangle}=(-1)^{\langle{M^{-\mathsf{T}}\gamma,y}\rangle}$.
∎

##  3 Upper Bound on $\mathsf{r}(f,\delta)$

Now we prove our main theorem, restated here for convenience. See 1.1

First, we gain some intuition from degree one functions.

##### Base Case/Toy Example.

Suppose $f$ is a Fourier degree one function. In this case our function has
the form

$f(x)=\widehat{f}(0)+\sum_{i}\widehat{f}({e_{i}})(-1)^{x_{i}}.$

For a parameter $t\geq 1$ and a subset $S\subseteq[t]$, consider the sum
$g_{S}=\widehat{f}(0)+\sum_{i\in S}\widehat{f}(e_{i})$. Note that
$g_{S}=\mathop{\bf E\/}[f(x)|x_{i}=0\>\>\forall i\in S]\in[-1,1]$. The
pigeonhole principle implies that for $t=\Omega(\log 1/\delta)$ there must
exist two distinct sets $S,S^{\prime}$ such that the difference
$|g_{S}-g_{S^{\prime}}|\leq\delta$. We can further write
$g_{S}-g_{S^{\prime}}=\sum_{i\in S\triangle
S^{\prime}}\widehat{f}(e_{i})(-1)^{|\\{i\\}\cap S^{\prime}|}$.

We now use the set $S\triangle S^{\prime}$ and the signs to construct an
affine subspace where at least one Fourier coefficient will have small
magnitude. Assume without loss of generality that $1\in S\setminus S^{\prime}$
and $S\triangle S^{\prime}=[t^{\prime}]$ for some $t^{\prime}\leq t$. Consider
restricting $f$ to the affine subspace $\mathcal{U}$ defined by the linear
equations $x_{1}+x_{i}=b_{i}$ for each $i\in\\{2,\ldots,t^{\prime}\\}$, where
$b_{i}=|\\{i\\}\cap S^{\prime}|$. We can reason about the Fourier spectrum of
$f_{\mathcal{U}}$ by plugging in $x_{i}=b_{i}+x_{1}$. Under this restriction,
we see that the Fourier coefficients of $e_{t^{\prime}+1},\ldots,e_{n}$ stay
the same, and the new Fourier coefficient of $e_{1}$ is exactly equal to

$\widehat{f}(e_{1})+\sum_{i=2}^{t^{\prime}}\widehat{f}({e_{i}})(-1)^{b_{i}}=g_{S}-g_{S^{\prime}},$

which we observed has magnitude at most $\delta$. Repeatedly applying this
argument roughly $n(\log(1/\delta))^{-1}$ times for the remaining standard
basis vectors and fixing remaining coordinates arbitrarily, we obtain an
affine subspace of dimension at least
$\Omega\left(\frac{n}{\log(1/\delta)}\right)$.

Theorem 1.1 is proved via induction using the following lemma.

######  Lemma 3.1.

For $\tau\in(0,1)$ and any degree $d$ function
$f:\mathbb{F}_{2}^{n}\to[-1,1]$, there exists an invertible linear map
$M:\mathbb{F}_{2}^{n}\rightarrow\mathbb{F}_{2}^{n}$, a set $J\subseteq[n]$
with size at least $\frac{d}{4e}\left(\frac{n}{\log 5/\tau}\right)^{1/d}$, and
$b\in\spn(\overline{J})$ such that $h=f\circ M$ satisfies

$\left|\widehat{{h}_{\overline{J}\parbox{5.69046pt}{ \leavevmode\hbox
to6.09pt{\vbox to0.4pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b}}(\gamma)\right|\leq\begin{cases}\tau\quad\text{
if }\|\gamma\|_{1}=d,\\\ 0\quad\text{ for all }\|\gamma\|_{1}>d.\end{cases}$

We now prove Theorem 1.1 using Lemma 3.1.

###### Proof.

The proof proceeds by induction over the degree. Our inductive hypothesis is
that for any $\delta>0$ and any degree $d$ function $f$, there exists an
invertible linear map $M$, a set $I\subseteq[n]$, and $b\in\spn(\overline{I})$
such that the following two items hold:

  1. 1.

${h}_{\bar{I}\parbox{5.69046pt}{ \leavevmode\hbox to6.09pt{\vbox
to0.4pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b}$ is
$\delta$-regular, where $h=f\circ M$, and

  2. 2.

for $C_{d}=\sum_{i=1}^{d}(i!)^{-1}$, we have

$|I|\geq\frac{n^{1/d!}}{(8e)^{C_{d-1}}\left(\log(n/\delta)\right)^{C_{d}}}.$

Note that $C_{d}\leq e-1<2$ for all $d\geq 1$. The existence of the desired
affine subspace is then given by Corollary 2.12, and its dimension is equal to
$|I|\geq\Omega\left(n^{1/d!}\left(\log(n/\delta)\right)^{-2}\right)$.

The base case corresponds to the degree being one. Let us apply Lemma 3.1 for
degree one with $\tau=\delta$ and denote $g=f\circ M$, where $M$ is the linear
map $M$ promised by the lemma. Additionally, we have a set $J$ of size at
least $\frac{n}{4e\log 5/\delta}\geq\Omega\left(\frac{n}{\log
n/\delta}\right)$, and $b\in\spn(\overline{J})$ such that

$\left|\widehat{{g}_{\overline{J}\parbox{5.69046pt}{ \leavevmode\hbox
to6.09pt{\vbox to0.4pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b}}(\gamma)\right|\leq\begin{cases}\tau\quad\text{
if }\|\gamma\|_{1}=1,\\\ 0\quad\text{ for all
}\|\gamma\|_{1}>1.\end{cases}\implies\left|\widehat{{g}_{\overline{J}\parbox{5.69046pt}{
\leavevmode\hbox to6.09pt{\vbox to0.4pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b}}(\gamma)\right|\leq\delta,\text{
for all }\gamma\neq 0.$

Assuming both items hold for some degree $d-1$, we show them for degree $d$.
Applying Lemma 3.1 with degree $d$ and $\tau=n^{-d}\delta/3$, we denote
$p:={(f\circ M)}_{\overline{J}\parbox{5.69046pt}{ \leavevmode\hbox
to6.09pt{\vbox to0.4pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b}$, where $M$, $J$
and $b$ are as promised by the lemma. Note that, by Lemma 3.1, $p$ has degree
at most $d$, and for any $\gamma$ with $\|\gamma\|_{1}=d$, we have,
$\left|\widehat{p}(\gamma)\right|\leq\delta/(3n^{d})$. Consider the functions
$p^{<d}$ and $p^{=d}$, which are the degree at most $d-1$ part of $p$ and the
degree $d$ part of $p$, respectively. We note that
$\frac{p^{<d}}{(1+\delta/3)}$ is bounded in the interval $[-1,1]$ because for
any $x$,

$\left|p^{<d}(x)\right|\leq\left|p(x)\right|+\left|p^{=d}(x)\right|\leq
1+\sum_{\gamma:\|\gamma\|_{1}=d}\left|\widehat{p}(\gamma)\right|\leq
1+\frac{\delta}{3}.$

Applying the inductive hypothesis888Technically,
$\frac{p^{<d}}{1+\delta/3}:\spn(J)\to[-1,1]$. However, we can abuse notation
slightly and consider it as a function from $\mathbb{F}_{2}^{J}$ to $[-1,1]$
in order to apply the inductive hypothesis. to $\frac{p^{<d}}{1+\delta/3}$ for
the choice of $\delta/3$, we get a linear map $M^{\prime}$, a set $I\subseteq
J$, and $b^{\prime}\in\spn(J\setminus I)$ such that
${\left(\frac{q}{1+\delta/3}\right)}_{J\setminus I\parbox{5.69046pt}{
\leavevmode\hbox to6.09pt{\vbox to0.4pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b^{\prime}}$ is
$\delta/3$-regular, where $q:=p^{<d}\circ M^{\prime}$. Therefore, for any
$\gamma\neq 0$, we have $\left|\widehat{{q}_{J\setminus I\parbox{5.69046pt}{
\leavevmode\hbox to6.09pt{\vbox to0.4pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b^{\prime}}}(\gamma)\right|\leq\left(1+\frac{\delta}{3}\right)\frac{\delta}{3}<\frac{2\delta}{3}$.
Denoting $p^{\prime}:=p\circ M^{\prime}$ and $r:=p^{=d}\circ M^{\prime}$, we
have for any $\gamma\neq 0$ that

$\displaystyle\Bigl{\lvert}\widehat{{p^{\prime}}_{J\setminus
I\parbox{5.69046pt}{ \leavevmode\hbox to6.09pt{\vbox
to0.4pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b^{\prime}}}(\gamma)\Bigr{\rvert}\leq\Bigl{\lvert}\widehat{{q}_{J\setminus
I\parbox{5.69046pt}{ \leavevmode\hbox to6.09pt{\vbox
to0.4pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b^{\prime}}}(\gamma)\Bigr{\rvert}+\Bigl{\lvert}\widehat{{r}_{J\setminus
I\parbox{5.69046pt}{ \leavevmode\hbox to6.09pt{\vbox
to0.4pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b^{\prime}}}(\gamma)\Bigr{\rvert}<2\delta/3+\sum_{\beta:\|\beta\|_{1}=d}\left|\widehat{g}(\beta)\right|\leq\delta.$

This shows that ${p^{\prime}}_{J\setminus I\parbox{5.69046pt}{
\leavevmode\hbox to6.09pt{\vbox to0.4pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b^{\prime}}$ is
$\delta$-regular. Moreover, if we extend $M^{\prime}$ to act as the identity
map on the coordinates in $\overline{J}$, we can write

$\displaystyle{p^{\prime}}_{J\setminus I\parbox{5.69046pt}{ \leavevmode\hbox
to6.09pt{\vbox to0.4pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b^{\prime}}(x)={(p\circ
M^{\prime})}_{J\setminus I\parbox{5.69046pt}{ \leavevmode\hbox to6.09pt{\vbox
to0.4pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b^{\prime}}(x)$
$\displaystyle=p(M^{\prime}(x+b^{\prime}))$ $\displaystyle={(f\circ
M)}_{J\parbox{5.69046pt}{ \leavevmode\hbox to6.09pt{\vbox
to0.4pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b}(M^{\prime}(x+b^{\prime}))=f(MM^{\prime}(x+b^{\prime}+b)),$

which implies that item 1 of the inductive hypothesis is satisfied by applying
the linear map $MM^{\prime}$ and restricting to the set $I$ by fixing the
coordinates outside according to $b+b^{\prime}$.

We now show that the size of $I$ satisfies item 2 above. Note that Lemma 3.1
promises that
$|J|\geq\frac{d}{4e}\left(\frac{n}{\log(15n^{d}/\delta)}\right)^{1/d}$.
Moreover, we have

$\log(15n^{d}/\delta)\leq d\log n/\delta+\log 15\leq 4d\log n/\delta,$

where the last inequality follows for sufficiently large $n$. Therefore,
$|J|\geq\frac{1}{8e}\left(\frac{n}{\log(n/\delta)}\right)^{1/d}$. Moreover, we
assume without loss of generality that $3|J|\leq n$ because, if not, we can
arbitrarily fix coordinates in $J$ until it is, which does not affect the
crucial property that all remaining degree $d$ Fourier coefficients have small
magnitude. Using the bounds on $|J|$ and applying item 2 of the inductive
hypothesis for degree $d-1$, we get

$\displaystyle|I|\geq\frac{|J|^{1/(d-1)!}}{(8e)^{C_{d-2}}\left(\log(3|J|/\delta)\right)^{C_{d-1}}}$
$\displaystyle\geq\frac{n^{1/d!}}{(8e)^{C_{d-1}}\log(n/\delta)^{1/d!}\left(\log(3|J|/\delta)\right)^{C_{d-1}}}$
$\displaystyle\geq\frac{n^{1/d!}}{(8e)^{C_{d-1}}\left(\log(n/\delta)\right)^{C_{d}}}.$

This shows item 2 of the inductive hypothesis as desired. ∎

To prove Lemma 3.1, we need the following claim, which ultimately lets us
bound Fourier coefficients in certain affine subspaces.

######  Claim 3.2 (Pigeonhole Principle).

Let $f:\mathbb{F}_{2}^{n}\to[-1,1]$ be degree $d$. For every $K\subseteq[n]$
of size $k$ such that $n-k\geq\binom{k}{d-1}\log(5/\tau)$, there exists
$S\subseteq[n]\setminus K$ and $z\in\\{\pm 1\\}^{S}$ such that

  1. 1.

$\forall\gamma\in\spn(K)$ with $\|\gamma\|_{1}=d-1$, we have
$\Bigl{\lvert}\sum_{j\in S}\widehat{f}(\gamma+e_{j})\cdot
z_{j}\Bigr{\rvert}\leq\tau$, and

  2. 2.

$1<|S|\leq\binom{k}{d-1}\log(5/\tau)$.

###### Proof.

Consider any subset of $T\subseteq\overline{K}$ of size
$\binom{k}{d-1}\log(5/\tau)$. For any $U\subseteq T$, consider the sum

$a_{U}(\gamma):=\widehat{f}(\gamma)+\sum_{j\in U}\widehat{f}(\gamma+e_{j}).$

We must have that $a_{U}(\gamma)\in[-1,1]$ since it is exactly equal to the
Fourier coefficient corresponding to $\gamma$ if we restricted everything in
$U$ to be one. This follows because $f$ is degree $d$.

Now, divide the interval $[-1,1]$ into $2/\tau$ intervals of length $\tau$.
For a fixed $U\subseteq T$ of even size, consider putting the values of
$a_{U}(\gamma)$ for all $\gamma\in\spn(K)^{=d-1}$ into a vector $v_{U}$ of
length $\binom{k}{d-1}$. First, note that the number of even subsets of $T$ is
at least $2^{\binom{k}{d-1}\log(5/\tau)-1}>(2/\tau)^{\binom{k}{d-1}}$.
Moreover, the number of possible interval vectors is at most
$(2/\tau)^{\binom{k}{d-1}}$. Therefore, by the pigeonhole principle, there
must be two distinct sets $U,U^{\prime}\subseteq T$ such that
$\|v_{U}-v_{U^{\prime}}\|_{\infty}\leq\tau$.

Thus, we have that

$\|v_{U}-v_{U^{\prime}}\|_{\infty}\leq\tau\Longleftrightarrow\sum_{i\in
U\triangle U^{\prime}}(-1)^{|\\{i\\}\cap
U^{\prime}|}\widehat{f}(\gamma+e_{i})\leq\tau\quad\forall\>\gamma\in\spn(K)^{=d-1}.$

Since $U,U^{\prime}$ have even size and are not equal, $U\triangle U^{\prime}$
has even size as well, so we can set our $S=U\triangle U^{\prime}\subseteq T$
and $z_{i}=(-1)^{|\\{i\\}\cap U^{\prime}|}$, and the claim follows. ∎

We can now prove Lemma 3.1.

###### Proof of Lemma 3.1.

We build the map $M$, the set $J$, and the vector $b$ iteratively. Throughout
the iterations, we seek to maintain a set $K$ of coordinates for which (under
a suitable linear transformation $M$) every Fourier coefficient corresponding
to a vector of weight $d$ in $\spn(K)$ has magnitude at most $\tau$. We build
$K$ one coordinate at a time by repeatedly invoking 3.2 and arguing that the
quantities guaranteed to be small by 3.2 are exactly the (new) Fourier
coefficients. When we can no longer add more coordinates to $K$, we fix any
remaining coordinates (outside of $K$ that are still alive), and we are left
with a function, over only the coordinates in $K$, that has the desired
property.

Note that we can start with $K$ being an arbitrary subset of size $d-1$
(w.l.o.g. let it be $[d-1]$) since any such subset has no Fourier coefficients
of degree $d$. Therefore, we can assume without loss of generality that
$\tau\geq 5\cdot 2^{-n/(4e)^{d}}$, since otherwise
$\frac{d}{4e}\left(\frac{n}{\log(5/\tau)}\right)^{1/d}<d$ and the lemma
becomes trivial. In each iteration, we maintain the following invariant for
$M$, $J$ and $b$. In iteration $i$, there exists some $K\subseteq J$ of size
$d+i-1$ such that the function $g={(f\circ
M)}_{\overline{J}\parbox{5.69046pt}{ \leavevmode\hbox to6.09pt{\vbox
to0.4pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b}$ satisfies

$\displaystyle|\widehat{g}(\gamma)|\leq\begin{cases}\tau\quad\text{ if
}\gamma\in\spn(K)\text{ and }\|\gamma\|_{1}=d,\\\ 0\quad\text{ for all
}\|\gamma\|_{1}>d.\end{cases}$

Assume without loss of generality that $J=[j]$ for some $j\leq n$ and
$K=[d+i-1]\subseteq J$. Since $g$ has degree $d$, we can apply 3.2 to $g$ and
obtain a subset $S\subseteq J\setminus K$ of size at most
$\binom{d+i-1}{d-1}(\log(5/\tau)$ and a sign vector $z\in\\{\pm 1\\}^{S}$ so
that

$\displaystyle~{}\Bigl{\lvert}\sum_{j\in S}\widehat{g}(\gamma+e_{j})\cdot
z_{j}\Bigr{\rvert}\leq\tau,\quad\text{ for all }\gamma\in\spn([d+i-1])\text{
such that }\|\gamma\|_{1}=d-1.$ (2)

We can also assume that $d+i\in S$ and $z_{d+i}=1$. Now consider the
invertible linear transformation
$M_{i}:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}^{n}$ that maps $e_{d+i}$ to
$\sum_{j\in S}e_{j}$ and behaves as the identity map on the remaining standard
basis vectors. Further, denote $J_{i}:=S\setminus\\{d+i\\}$ and let
$b_{i}\in\spn(J_{i})$, where $(b_{i})_{j}:=(1-z_{j})/2$ for each $j\in J_{i}$.
Intuitively, applying the linear transformation $M_{i}$ and then fixing the
coordinates in $J_{i}$ to $b_{i}$ corresponds to restricting the affine
subspace described by the equations $x_{j}+x_{d+i}=(1-z_{j})/2$ for all $j\in
J_{i}$.

After this iteration, we show that if we set $M^{\prime}\leftarrow MM_{i}$,
$J^{\prime}\leftarrow J\setminus J_{i}$ and $b^{\prime}\leftarrow b+b_{i}$,
the invariant holds with $K^{\prime}\leftarrow K\cup\\{d+i\\}$. For these
choices, we have

$\displaystyle{(f\circ M^{\prime})}_{\overline{J^{\prime}}\parbox{5.69046pt}{
\leavevmode\hbox to6.09pt{\vbox to0.4pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b^{\prime}}(x)=f\circ
M(M_{i}(x+b^{\prime}))$ $\displaystyle=f\circ M(M_{i}(x+b_{i}+b))$
$\displaystyle=f\circ M(M_{i}(x+b_{i})+b)$ $\displaystyle=g\circ
M_{i}(x+b_{i})={(g\circ M_{i})}_{J_{i}\parbox{5.69046pt}{ \leavevmode\hbox
to6.09pt{\vbox to0.4pt{\pgfpicture\makeatletter\hbox{\hskip
0.2pt\lower-0.2pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b_{i}}(x),$

and it therefore suffices to show that ${(g\circ
M_{i})}_{J_{i}\parbox{5.69046pt}{ \leavevmode\hbox to6.09pt{\vbox
to0.4pt{\pgfpicture\makeatletter\hbox{\hskip 0.2pt\lower-0.2pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{}}{}
{{}{}}{}{}{}{}{}{{}}\pgfsys@moveto{0.45999pt}{0.0pt}\pgfsys@lineto{5.69055pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
}{{}{{}}{}{}{{}}{{{}}{{{}}{\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{-1.0}{0.0}{0.0}{-1.0}{0.45999pt}{0.0pt}\pgfsys@invoke{
}\pgfsys@invoke{ \lxSVG@closescope }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope}}{{}}}} } \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}b_{i}}$ – denoted by
$h$ henceforth, for shorthand – is degree $d$ and
$\left|\widehat{h}(\gamma)\right|\leq\tau$ for all $\gamma\in\spn([d+i])$ with
$\|\gamma\|_{1}=d$. We start by analyzing the Fourier coefficients of $h$, for
which by 2.5 we have

$\displaystyle~{}\widehat{h}(\gamma)=\sum_{\beta\in\spn(J_{i})}\widehat{g\circ
M_{i}}(\gamma+\beta)(-1)^{\langle\beta,b_{i}\rangle}.$ (3)

Next, we observe the following relation between the Fourier coefficients of
$g\circ M_{i}$ and those of $g$, which we use to simplify Equation (3).
Denoting $v:=\sum_{j\in J_{i}}e_{j}$, we claim that, for any $\gamma$,

$\displaystyle~{}\widehat{g\circ
M_{i}}(\gamma)=\widehat{g}(\gamma+e_{d+i}\langle\gamma,v\rangle).$ (4)

Before proving Equation (4), we use it to prove that $h$ has the desired
properties. Note that since $g$ is degree $d$, Equation (4) implies that if
$\widehat{g\circ M_{i}}(\gamma)\neq 0$, then
$\|\gamma+e_{d+i}\langle\gamma,v\rangle\|_{1}\leq d$, which in turn implies
that $\|\gamma\|_{1}\leq d+1$. This immediately tells us that $g\circ M_{i}$
has degree at most $d+1$; therefore, $h$ also has degree at most $d+1$ since
the degree cannot increase under restrictions. Now, for any $\gamma$, Equation
(3) reduces to

$\displaystyle\widehat{h}(\gamma)$
$\displaystyle=\sum_{\begin{subarray}{c}\beta\in\spn(J_{i}),\\\
\|\beta\|_{1}\leq d+1-\|\gamma\|_{1}\end{subarray}}\widehat{g\circ
M_{i}}(\gamma+\beta)(-1)^{\langle\beta,b_{i}\rangle}$
$\displaystyle=\widehat{g\circ
M_{i}}(\gamma)+\sum_{\begin{subarray}{c}\beta\in\spn(J_{i}),\\\
0<\|\beta\|_{1}\leq d+1-\|\gamma\|_{1}\end{subarray}}\widehat{g\circ
M_{i}}(\gamma+\beta)(-1)^{\langle\beta,b_{i}\rangle}$
$\displaystyle=\widehat{g}(\gamma+e_{d+i}\langle\gamma,v\rangle)+\sum_{\begin{subarray}{c}\beta\in\spn(J_{i}),\\\
0<\|\beta\|_{1}\leq
d+1-\|\gamma\|_{1}\end{subarray}}\widehat{g}(\gamma+\beta+e_{d+i}\langle\gamma+\beta,v\rangle)(-1)^{\langle\beta,b_{i}\rangle},$
(5)

where, in the first equality, we used the fact that if
$\|\beta\|_{1}>d+1-\|\gamma\|_{1}$, then $\|\beta+\gamma\|_{1}>d+1$ and the
corresponding Fourier coefficient in $g\circ M_{i}$ is just zero, and in the
last equality, we used Equation (4). Moreover, for any
$\gamma\in\spn(J\setminus J_{i})$, we have $\langle\gamma,v\rangle=0$, which
means that
$\widehat{g}(\gamma+e_{d+i}\langle\gamma,v\rangle)=\widehat{g}(\gamma)$. We
can now conclude that $h$ has degree at most $d$. Indeed, if
$\|\gamma\|_{1}\geq d+1$, then Equation (5) implies that
$\widehat{h}(\gamma)=\widehat{g}(\gamma)=0$ since $g$ has degree at most $d$.

Next, we show that for any $\gamma\in\spn([d+i])$ with $\|\gamma\|_{1}=d$, it
must be that $|\widehat{h}(\gamma)|\leq\tau$. Applying Equation (5) for such
$\gamma$, we note that

$\displaystyle\widehat{h}(\gamma)$
$\displaystyle=\widehat{g}(\gamma)+\sum_{j\in
J_{i}}\widehat{g}(\gamma+e_{j}+e_{d+i}\langle\gamma+e_{j},v\rangle)(-1)^{\langle
e_{j},b_{i}\rangle}$ $\displaystyle=\widehat{g}(\gamma)+\sum_{j\in
J_{i}}\widehat{g}(\gamma+e_{j}+e_{d+i})z_{j}.$

We now consider two cases. First, when $\gamma_{d+i}=0$, the above equation
implies that $\widehat{h}(\gamma)=\widehat{g}(\gamma)$ since
$\|\gamma+e_{d+i}+e_{j}\|_{1}=d+2$ for every $j\in J_{i}$, and $g$ has degree
at most $d$. Therefore, in this case,
$\left|\widehat{h}(\gamma)\right|=\left|\widehat{g}(\gamma)\right|\leq\tau$ by
the inductive hypothesis. Otherwise, $\gamma_{d+i}=1$, and now using both
Equation (2) and the fact that
$\gamma+e_{d+i}\in\spn(\\{e_{1},\ldots,e_{d+i-1}\\})$, we conclude that
$\left|\widehat{h}(\gamma)\right|=\left|\sum_{j\in
S}\widehat{g}((\gamma+e_{d+i})+e_{j})z_{j}\right|\leq\tau$.

It remains to show Equation (4). We start by observing that
$M_{i}=M_{i}^{-1}$, which can be verified by noting that
$M_{i}^{-1}e_{d+i}=M_{i}^{-1}(e_{d+i}+v+v)=e_{d+i}+v$ and $M_{i}^{-1}$ acts as
the identity map on the remaining standard basis vectors. From 2.13, we know
that $\widehat{g\circ M_{i}}(\gamma)=\widehat{g\circ
M_{i}^{-1}}(\gamma)=\widehat{g}(M_{i}^{\mathsf{T}}\gamma)$. Since the rows of
$M_{i}^{\mathsf{T}}$ are the same as the columns of $M_{i}$, we have

$\displaystyle(M_{i}^{\mathsf{T}}\gamma)_{j}=\begin{cases}\langle
v+e_{d+i},\gamma\rangle\quad&\text{ if }j=d+i,\\\ \gamma_{j}\quad&\text{
otherwise.}\end{cases}$

Therefore, we can write $M_{i}^{\mathsf{T}}\gamma=\sum_{j\neq
d+i}\gamma_{j}e_{j}+e_{d+i}\langle
v+e_{d+i},\gamma\rangle=\gamma+e_{d+i}\langle v,\gamma\rangle$, as claimed.

We conclude the argument by calculating how many times we can repeat the above
procedure. Note that, in the $i$-th iteration, we fixed at most
$\binom{d+i-1}{d-1}\log 5/\tau-1$ coordinates and we added exactly one
coordinate to $K$. We can thus continue this process until iteration $t$ for
the largest value of $t$ such that

$\log(5/\tau)\cdot\left(\sum_{i=1}^{t}\binom{d+i-1}{d-1}\right)\leq n-d+1.$

Simplifying the binomial sum, we get

$\displaystyle\sum_{i=1}^{t}\binom{d+i-1}{d-1}=\sum_{i=1}^{t}\binom{d+i-1}{i}$
$\displaystyle=\sum_{i=1}^{t}\binom{d+i-1}{i}+\binom{d}{0}-1$
$\displaystyle=\binom{d+t}{t}-1<\left(\frac{e(d+t)}{d}\right)^{d},$

where the last equality follows by repeatedly using the identity
$\binom{a}{i}+\binom{a}{i-1}=\binom{a+1}{i}$. Thus, we can set
$t=\frac{d}{e}\left(\frac{n-d+1}{\log 5/\tau}\right)^{1/d}-d$. Adding in the
initial $d-1$ coordinates, at the end of the $t$ iterations, we can bound
$|K|$ as,

$\displaystyle|K|$ $\displaystyle=\frac{d}{e}\left(\frac{n-d+1}{\log
5/\tau}\right)^{1/d}-d+d-1$ $\displaystyle\geq\frac{d}{e}\left(\frac{n}{\log
5/\tau}\left(1-\frac{d-1}{n}\right)\right)^{1/d}-1$
$\displaystyle\geq\frac{d}{e}\left(\frac{n}{\log
5/\tau}\cdot\frac{1}{d}\right)^{1/d}-1$
$\displaystyle\geq\frac{d}{2e}\left(\frac{n}{\log 5/\tau}\right)^{1/d}-1$
($d^{1/d}\leq 2\quad\forall d\geq 1$)
$\displaystyle=\frac{d}{4e}\left(\frac{n}{\log
5/\tau}\right)^{1/d}+\frac{d}{4e}\left(\frac{n}{\log 5/\tau}\right)^{1/d}-1$
$\displaystyle\geq\frac{d}{4e}\left(\frac{n}{\log 5/\tau}\right)^{1/d}+d-1$
(since $\tau\geq 5\cdot 2^{-n/(4e)^{d}}$)
$\displaystyle\geq\frac{d}{4e}\left(\frac{n}{\log 5/\tau}\right)^{1/d}.$
($d\geq 1$)

At the end of $t$ iterations, we can fix any coordinates outside the set $K$
arbitrarily to ensure that the only non-zero Fourier coefficients with
$\text{L}_{1}$ norm $d$ in the resulting function must correspond to vectors
in $\spn(K)$, which do not change under the restriction. ∎

##  4 Lower Bounds on $\mathsf{r}(f,\delta)$

In this section, we prove lower bounds on $\mathsf{r}(f,\delta)$. We start
with lower bounds for functions $f$ that are bounded in the interval $[-1,1]$;
in the subsequent section, we give lower bounds for Boolean functions.

###  4.1 Bounded Functions

We begin with a simple bound on the number of standard basis vectors in low-
dimensional affine subspaces, which is crucial in the analysis of the lower
bounds.

######  Claim 4.1.

For any subspace $\mathcal{V}\subseteq\mathbb{F}_{2}^{n}$ of co-dimension $C$
and $\mathcal{W}$ such that
$\mathcal{W}\oplus\mathcal{V}^{\perp}=\mathbb{F}_{2}^{n}$, there exists a set
$S\subseteq\mathcal{W}$ of size at least $n-C$ such that for every $u\in S$,

$|\left(u+\mathcal{V}^{\perp}\right)^{=1}|\geq 1.$

Moreover, there exists a subset $S_{1}\subseteq S$ of size at least $n-2C$
whose corresponding shifts contain _exactly_ one standard basis vector.

###### Proof.

Let $S=\\{u:u\in\mathcal{W}\text{ and }|u+\mathcal{V}^{\perp}|^{=1}\geq 1\\}$.
Since every standard basis vector can be expressed as $u+v$ for some $u\in S$
and $v\in\mathcal{V}^{\perp}$, we have that
$\dim(\spn(S\cup\mathcal{V}^{\perp}))=n$. However, we also know that
$\dim(\spn(S\cup\mathcal{V}^{\perp}))\leq|S|+C$, and rearranging we get
$|S|\geq n-C$. Next, let $S_{1}=\\{u\in S:|u+\mathcal{V}^{\perp}|^{=1}=1\\}$.
By 2.4, for any $u,u^{\prime}\in S$, we have $u+\mathcal{V}^{\perp}\neq
u^{\prime}+\mathcal{V}^{\perp}$. Therefore,

$n\geq\sum_{u\in S}|(u+\mathcal{V}^{\perp})^{=1}|\geq\sum_{u\in
S_{1}}|(u+\mathcal{V}^{\perp})^{=1}|+\sum_{u\in S\setminus
S_{1}}|(u+\mathcal{V}^{\perp})^{=1}|\geq|S_{1}|+2(|S|-|S_{1}|),$

and rearranging, we get $|S_{1}|\geq 2|S|-n\geq n-2C$. ∎

######  Lemma 4.2.

There is a degree one function $f:\mathbb{F}_{2}^{n}\to[-1,1]$ for which
$\mathsf{r}(f,\delta)\geq n/2$, for all $\delta<1/n$.

###### Proof.

The counterexample is given by the function
$f(x)=\frac{1}{n}\cdot\sum_{i}(-1)^{e_{i}\cdot x}$. Let $\mathcal{V}$ be a
subspace of $\mathbb{F}_{2}^{n}$ of co-dimension $C$, and suppose we restrict
the function to the affine subspace $\mathcal{U}=\alpha+\mathcal{V}$. By 4.1,
if $C\leq n/2-1$, there exists at least two vectors
$\gamma,\gamma^{\prime}\in\mathcal{W}$ (where $\mathcal{W}$ is such that
$\mathcal{W}\oplus\mathcal{V}^{\perp}=\mathbb{F}_{2}^{n}$) such that
$|(\gamma+\mathcal{V}^{\perp})^{=1}|=|(\gamma^{\prime}+\mathcal{V}^{\perp})^{=1}|=1$.
Assume without loss of generality that $\gamma\neq 0$. Then, by Proposition
2.8, we have that

$|\widehat{f_{\mathcal{U}}}(\gamma)|=\Bigl{\lvert}\sum_{\eta\in
u+\mathcal{V}^{\perp}}\widehat{f}(\eta)(-1)^{\langle{\eta,\alpha}\rangle}\Bigr{\rvert}=\frac{1}{n}>\delta,$

which follows by observing that exactly one of the summands in the last sum
corresponds to a weight one vector and is non-zero. Therefore,
$\mathsf{r}(f,\delta)\geq n/2$. ∎

We next show how to generalize Lemma 4.2 to degree $d$ bounded functions.

######  Lemma 4.3.

For $d>2$ and $\delta<\binom{n}{d}^{-1}$, there exists a degree $d$ function
$f:\mathbb{F}_{2}^{n}\rightarrow[-1,1]$ for which $\mathsf{r}(f,\delta)\geq
n-2dn^{1/(d-1)}$.

###### Proof.

The counterexample is obtained using a probabilistic argument. We consider the
homogeneous degree $d$ polynomial with random signs
$f_{\mathbf{z}}:\mathbb{F}_{2}^{n}\to[-1,1]$, defined as

$f_{\mathbf{z}}(x)=\sum_{\gamma:\|\gamma\|_{1}=d}\frac{\mathbf{z}_{\gamma}\cdot(-1)^{\langle{\gamma,x}\rangle}}{\binom{n}{d}},$

where each $\mathbf{z}_{\gamma}\sim\\{\pm 1\\}$ is a uniformly random sign.

Let $\mathcal{V}$ be a subspace of $\mathbb{F}_{2}^{n}$ of co-dimension $C$,
and suppose we restrict $f_{\mathbf{z}}$ to an affine subspace
$\mathcal{U}=\alpha+\mathcal{V}$. By 4.1, we have a $S\subseteq\mathcal{W}$
(where $\mathcal{W}$ is such that
$\mathcal{W}\oplus\mathcal{V}^{\perp}=\mathbb{F}_{2}^{n}$) of size at least
$k:=n-C$ such that $|(u+\mathcal{V}^{\perp})^{=1}|\geq 1$ for each $u\in S$.
Moreover, by 2.4, for every $v,v^{\prime}\in\spn(S)$ we have that
$v+\mathcal{V}^{\perp}\ \neq v^{\prime}+\mathcal{V}^{\perp}$. Therefore, there
is a set $T\subseteq\mathcal{W}$ of size at least $\binom{k}{d}$ such that for
every $u\in T$, we have $|(u+\mathcal{V}^{\perp})^{=d}|\geq 1$. By Proposition
2.8, for each $u\in T$, we have

$|\widehat{f_{\mathcal{U}}}(u)|=\Bigl{\lvert}\sum_{\eta\in
u+\mathcal{V}^{\perp}}\widehat{f}(\eta)(-1)^{\langle{\eta,\alpha}\rangle}\Bigr{\rvert}.$

We now observe that if $(u+\mathcal{V}^{\perp})^{=d}$ has odd size, then
$\left|\widehat{f_{\mathcal{U}}}(u)\right|\geq\binom{n}{d}^{-1}$. Therefore,
if $f_{\mathcal{U}}$ was $\delta$-regular, then for each $u\in T$, it must be
that the set $(u+\mathcal{V}^{\perp})^{=d}$ has even size, and, in particular,
that $|(u+\mathcal{V}^{\perp})^{=d}|\geq 2$.

Let $\mathcal{V}$ be a subspace such that each non-trivial affine subspace of
$\mathcal{V}^{\perp}$ has an even number of weight $d$ vectors. For a given
affine subspace $\mathcal{U}=\alpha+\mathcal{V}$ and a random choice of the
signs $\mathbf{z}_{\gamma}$’s, the probability that $f_{\mathcal{U}}$ is
$\delta$-regular is therefore at most $2^{-\binom{k}{d}}$. Let $\mathcal{B}$
(for “$\mathcal{B}\text{ad}$”) be the event that there is an affine subspace
$\mathcal{U}$ where $f_{\mathcal{U}}$ is $\delta$-regular. We can simply union
bound over all possible affine subspaces of dimension at least $k$ to bound
the probability of $\mathcal{B}$. For any $k$, observe that the number of
affine subspaces of dimension $k$ is at most $2^{n(k+1)}$. Thus, we have

$\mathop{\bf Pr\/}[\mathcal{B}]\leq\sum_{j=k}^{n}2^{n(j+1)}\cdot
2^{-\binom{j}{d}}\leq\sum_{j=k}^{n}2^{n(j+1)-\left(\frac{j}{d}\right)^{d}}.$

Note that $h(x)=n(x+1)-\left(\frac{x}{d}\right)^{d}$ is concave in
$[0,\infty)$; moreover, a quick calculation shows that it is maximized when
$x=d\cdot n^{1/(d-1)}$. Setting $k=2dn^{\frac{1}{d-1}}$, our desired
probability is at most

$\displaystyle\mathop{\bf Pr\/}[\mathcal{B}]$ $\displaystyle\leq(n-k)\cdot
2^{n(2dn^{\frac{1}{d-1}}+1)-2^{d}\cdot n^{\frac{d}{d-1}}}$ (Every term is
smaller than the first.) $\displaystyle\leq(n-k)\cdot
2^{(2d+1-2^{d})n^{1+\frac{1}{d-1}}}$ $\displaystyle\leq o(1).$
($2d+1-2^{d}\leq-1\quad\forall d\geq 3$.)

Therefore, there exists a signing $\mathbf{z}_{\gamma}$ such that for any
affine subspace of dimension at least $2dn^{1/(d-1)}$, the restriction of
$f_{z}$ is not $\delta$-regular. ∎

######  Remark 4.4.

Note that Lemma 4.3 is trivial when $d=2$; it would be interesting to obtain a
tighter result in this case.

###  4.2 Boolean Functions

This section has two parts. The first gives non-explicit lower bounds on
$\mathsf{r}(f,\delta)$ for Boolean functions, and the second gives explicit
lower bounds.

####  4.2.1 Non-explicit Lower Bounds on $\mathsf{r}(f,\delta)$

We can turn our lower bounds on $\mathsf{r}(f,\delta)$ for bounded functions
into (non-explicit) lower bounds for Boolean functions. To do so, we use the
following simple but powerful lemma of [Hos+16], which states that given a
bounded function with a large $\mathsf{r}(f,\delta)$, there must exist some
Boolean function $g$ with similarly a large $\mathsf{r}(g,2\delta)$.

######  Lemma 4.5 ([Hos+16], Claim 1.2).

Let $\tau>0$ and $f:\mathbb{F}_{2}^{n}\to[-1,1]$. There exists a Boolean
function $g:\mathbb{F}_{2}^{n}\to\\{\pm 1\\}$ satisfying, for every affine
subspace $\mathcal{U}$ such that $|\mathcal{U}|\geq\frac{4n^{2}}{\tau^{2}}$
and any $\gamma\in\mathbb{F}_{2}^{n}$, that

$\Bigl{\lvert}\widehat{f}_{\mathcal{U}}(\gamma)-\widehat{g}_{\mathcal{U}}(\gamma)\Bigr{\rvert}\leq\tau.$

###### Proof.

Let $g(x)$ equal $1$ with probability $\frac{1+f(x)}{2}$, and $-1$ otherwise.
Let $\mathcal{U}=\alpha+\mathcal{V}$ for some subspace $\mathcal{V}$.

By 2.7 we can write

$\widehat{f_{\mathcal{U}}}(\gamma)=(-1)^{\langle{\gamma,\alpha}\rangle}\mathop{\bf
E\/}_{y\in\mathcal{U}}[f(y)\cdot(-1)^{\langle{\gamma,y}\rangle}].$

Consider the random variable

$\widehat{g}_{\mathcal{U}}(\gamma)=(-1)^{\langle{\gamma,\alpha}\rangle}\mathop{\bf
E\/}_{y\in\mathcal{U}}[g(y)\cdot(-1)^{\langle{\gamma,y}\rangle}].$

Observe that $\mathop{\bf
E\/}_{g}\widehat{g}_{\mathcal{U}}(\gamma)=\widehat{f}_{\mathcal{U}}(\gamma)$.
Moreover, every term in the summation is in $[-1,1]$, so by a Hoeffding bound
(see 2.1), the probability
$\left|\widehat{g}_{\mathcal{U}}(\gamma)-\widehat{f}_{\mathcal{U}}(\gamma)\right|\geq\tau$
is at most $2\exp\left(-\tau^{2}|\mathcal{U}|^{2}/2\right)\leq 2^{-2n^{2}+1}$.

On the other hand, there are at most $2^{n^{2}}$ affine subspaces of
$\mathbb{F}_{2}^{n}$, and at most $2^{n}$ choices for $\gamma$. Therefore, by
a union bound, the probability that $g$ has the property we desire is at least
$1-2^{n^{2}+n-2n^{2}+1}>0$, and the claim follows. ∎

Using Lemma 4.5, we have the following lemma.

######  Lemma 4.6.

For all $d\geq 3$ and $\delta<\frac{1}{2}\cdot\binom{n}{d}^{-1}$, there exists
a Boolean function $f$ with

$\mathsf{r}(f,\delta)\geq n-\max\left\\{2d\cdot
n^{1/(d-1)},\log\left(16n^{2}/\delta^{2}\right)\right\\}.$

###### Proof.

By Lemma 4.3, there exists a bounded $f$ that is not $\delta$-regular in any
affine subspace of dimension at least $2dn^{1/(d-1)}$ for all
$\delta<\binom{n}{d}^{-1}$. Lemma 4.5 tells us that there exists a Boolean
function $g$ whose Fourier coefficients agree up to an additive error
$\delta/2$ with the Fourier coefficients of $f$ on all affine subspaces of
dimension at least $\log\left(16n^{2}/\delta^{2}\right)$. Therefore, if $f$ is
not $\delta$-regular on all of these affine subspaces, then $g$ is also not
$\delta/2$-regular on any of these subspaces. ∎

We can plug some parameters into Lemma 4.6 and achieve the following more
parsable corollary.

######  Corollary 4.7.

For every $3\leq d\leq\frac{\log n}{\log\log n+1}$ and
$\delta=\frac{1}{2}\cdot n^{-d}$, there exists a Boolean function $f$ with
$\mathsf{r}(f,\delta)\geq n-2d\cdot n^{1/(d-1)}$.

###### Proof.

The function is the same as in Lemma 4.6. We argue that by our choice of
parameters, $k$ is always maximized by the first term. We first note that
$\frac{1}{2}\cdot\binom{n}{d}^{-1}>\frac{1}{2}\cdot n^{-d}=\delta$, so our
choice for $\delta$ is valid. Next, we have that

$\log(16n^{2}/\delta^{2})=5+2\log n+2d\log n\leq 3d\log n\leq
3\frac{\log^{2}n}{\log\log n},$

where we used the fact that $d\geq 3$ and $n$ is sufficiently large. On the
other hand, note that the function $h(x)=2xn^{1/(x-1)}$ is decreasing when
$x\leq\frac{\log n}{\log\log n+1}$. Therefore, we have that

$\displaystyle 2dn^{1/(d-1)}$ $\displaystyle\geq 2\cdot\frac{\log n}{\log\log
n}\cdot n^{\frac{\log\log n+1}{\log n}}=4\cdot\frac{\log^{2}n}{\log\log n}.$

Therefore, the first term is the larger term in Lemma 4.6, as desired. ∎

####  4.2.2 Explicit Lower Bounds on $\mathsf{r}(f,\delta)$

######  Lemma 4.8 (Related to Corollary 1.1 in [ODo+14]).

For each $\delta>0$, there exists an explicit Boolean function
$f:\mathbb{F}_{2}^{n}\to\\{0,1\\}$ with
$\mathsf{r}(f,\delta)=\Omega\left((\log\frac{1}{\delta})^{\log_{2}(3)}\right)$.

The proof of Lemma 4.8 is based on Theorem 4.9, which appeared in a slightly
weaker form in [ODo+14].

######  Theorem 4.9 ([ODo+14]).

Let $f:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}$, and
$g:\mathbb{F}_{2}^{m}\to\mathbb{F}_{2}$. We have that

$C_{\min}^{\oplus}[f\circ g]\geq C_{\min}^{\oplus}[f]+C_{\min}[f]\cdot B_{g},$

where $B_{g}=\max\\{\log C_{\min}^{\oplus}[g]-1,1\\}$.

In fact, in [ODo+14] Theorem 4.9 appeared as

$C_{\min}^{\oplus}[f\circ g]\geq C_{\min}^{\oplus}[f]+C_{\min}[f],$

but they assumed only that $C_{\min}^{\oplus}[g]\geq 2.$ Therefore, the above
result is strictly stronger for any $g$ such that $C_{\min}^{\oplus}[g]>4$. We
include a proof of this slightly stronger fact in Appendix B.

We require the following corollary of Theorem 4.9.

######  Corollary 4.10.

We have that

$C_{\min}^{\oplus}[f^{\circ k}]\geq
B_{g}\cdot\frac{C_{\min}[f]^{k}-C_{\min}[f]}{C_{\min}[f]-1}+C_{\min}^{\oplus}[f]\geq
B_{g}\cdot C_{\min}[f]^{k-1},$

where $B_{g}=\max\\{\log C_{\min}^{\oplus}[g]-1,1\\}$.

###### Proof that Theorem 4.9 implies Corollary 4.10.

Let $f=f^{\circ(k-1)}$ and $g=f$. We have by the theorem that

$\displaystyle C_{\min}^{\oplus}[f^{\circ k}]$ $\displaystyle\geq
C_{\min}^{\oplus}[f^{\circ(k-1)}]+C_{\min}[f^{\circ(k-1)}]\cdot B_{g}$
$\displaystyle\geq C_{\min}^{\oplus}[f^{\circ(k-1)}]+C_{\min}[f]^{k-1}\cdot
B_{g}$ (Supermultiplicativity of $C_{\min}$, see [Tal13]) $\displaystyle\geq
B_{g}\cdot\sum_{i=1}^{k-1}C_{\min}[f]^{i}+C_{\min}^{\oplus}[f]$
$\displaystyle=B_{g}\cdot\frac{C_{\min}[f]^{k}-C_{\min}[f]}{C_{\min}[f]-1}+C_{\min}^{\oplus}[f]\geq
B_{g}\cdot C_{\min}[f]^{k-1}.\qed$

For our application, we make the following crucial observation: if $f$ has
Fourier coefficients that are all of equal magnitude $\delta$, then any
restriction to an affine subspace results in Fourier coefficients of the
restricted function that are integer multiples of $\delta$. Hence, if $f$ is
$\delta^{\prime}$-regular, for any $\delta^{\prime}<\delta$, then $f$ is in
fact, constant. In this scenario, finding a subspace in which $f$ is
$\delta$-regular is equivalent to finding a subspace where it is constant.

###### Proof of Lemma 4.8.

Consider the following function $g:\mathbb{F}_{2}^{n}\to\\{\pm 1\\}$:

$g(x_{1},x_{2},x_{3},x_{4})=\frac{1}{2}(-1)^{x_{1}+x_{3}}+\frac{1}{2}(-1)^{x_{2}+x_{3}}+\frac{1}{2}(-1)^{x_{1}+x_{4}}-\frac{1}{2}(-1)^{x_{2}+x_{4}}.$

Define the function $f:=\frac{1-g}{2}$ so that
$f:\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}$. In other words, f is equal to
${x_{1}+x_{3}}$ if $x_{1}=x_{2}$ and $x_{1}+x_{4}+\mathbbm{1}\\{x_{1}=0\\}$
otherwise. Note that $f$ is a degree 2 function, where all non-zero Fourier
coefficients have the same magnitude. We also claim that
$C_{\min}^{\oplus}[f]=2$. Indeed, we can fix $x_{1}+x_{2}=0$ and
$x_{1}+x_{3}=0$, and we know $f$ equals 0. On the other hand, we have that
$C_{\min}[f]=3$.

We examine $f^{\circ k}=f(f_{1},f_{2},f_{3},f_{4})$, where the $f_{i}$’s are
copies of $f^{\circ(k-1)}$ over disjoint sets of inputs. We claim by induction
that $\deg(f^{\circ k})=2^{k}$. This is clearly true when $k=1$, and for the
inductive step we can write

$f(f_{1},f_{2},f_{3},f_{4})=\begin{cases}f_{1}+f_{3}&\text{ if }f_{1}=f_{2}\\\
f_{4}+f_{1}&\text{ if }f_{1}\neq f_{2}.\end{cases}$

Since $\mathbbm{1}\\{f_{1}=f_{2}\\}=f_{1}+f_{2}+1$, we can write

$f(f_{1},f_{2},f_{3},f_{4})=(f_{1}+f_{3})(f_{1}+f_{2}+1)+(f_{1}+f_{4})(f_{1}+f_{2}).$

Therefore, by the inductive hypothesis and the fact that the $f_{i}$’s are
supported over disjoint variables, we have that $\deg f^{\circ k}=2\cdot\deg
f^{\circ(k-1)}=2^{k}$. Therefore,999See [ODo21], Exercise 1.9 or 5.2. all the
Fourier coefficients are integer multiples of $1/2^{2^{k}}$. So, to make $f$
$\delta$-regular for $\delta<1/2^{2^{k}}$, it must be fixed to a constant.
Suppose we set $\delta=1/2^{2^{k}+1}$. By Corollary 4.10, we have that

$C_{\min}^{\oplus}[f^{\circ k}]\geq
C_{\min}[f]^{k-1}=3^{k-1}=\frac{1}{3}\cdot(2^{k})^{\log_{2}(3)}=\frac{1}{3}\cdot\frac{1}{2^{\log_{2}(3)}}\log(1/\delta)^{\log_{2}(3)}=\frac{1}{9}\cdot\log(1/\delta)^{\log_{2}(3)}.\qed$

We now show that the majority function, denoted by $\MAJ_{n}$, also has a
large $\mathsf{r}(f,\delta)$ value when $\delta=O(1/\sqrt{n})$.

######  Lemma 4.11.

There is an absolute constant $C>0$, such that for all sufficiently large $n$,
$\mathsf{r}(\MAJ_{n},\delta)\geq\Omega(n^{1/2})$ for any $\delta\leq
C/\sqrt{n}$.

We need the following three claims to prove this lemma.

######  Claim 4.12 (Fourier Spectrum of $\MAJ_{n}$, Corollary of Theorem 5.19
in [ODo21]).

Consider $f=\MAJ_{n}$. Each of the following hold.

  1. 1.

For each $t\in\mathbb{N}$ and $\gamma\in\mathbb{F}_{2}^{n}$ with
$\|\gamma\|_{1}=t$,

$\displaystyle\left|\widehat{f}(\gamma)\right|\leq\begin{cases}\left(\frac{t}{n}\right)^{\frac{t-1}{2}}\left|\widehat{f}(e_{1})\right|,&\text{
if $t$ is odd},\\\ 0&\text{ otherwise.}\end{cases}$

  2. 2.

For any $\gamma$ with $\|\gamma\|_{1}=1$,
$\left|\widehat{f}(\gamma)\right|\geq\sqrt{\frac{2}{\pi n}}$.

  3. 3.

For any $\gamma,\gamma^{\prime}$ such that
$\|\gamma\|_{1}+\|\gamma^{\prime}\|_{1}=n+1$, it holds that
$\Bigl{\lvert}\widehat{f}(\gamma)\Bigr{\rvert}=\Bigl{\lvert}\widehat{f}(\gamma^{\prime})\Bigr{\rvert}$.

######  Claim 4.13 ([htt]).

Let $\mathcal{U}=\alpha+\mathcal{W}$ be any affine subspace of
$\mathbb{F}_{2}^{n}$. For every $t\in[n]$, let $t^{*}:=\min\\{t,n-t\\}$. Then,
it holds that

$|\mathcal{U}^{=t}|\leq\binom{\dim(\mathcal{W})+1}{\leq t^{*}}.$

######  Lemma 4.14.

Let $\mathcal{V}$ be a subspace of $\mathbb{F}_{2}^{n}$ of co-dimension $C$
and $\mathcal{W}$ be such that
$\mathcal{W}\oplus\mathcal{V}^{\perp}=\mathbb{F}_{2}^{n}$. For each $\ell\leq
C+1$, there exists $S_{\ell}\subseteq\mathcal{W}$ such that $|S_{\ell}|\geq
n-C(\ell+1)$, and for each $\gamma\in S_{\ell}$ the following two hold:

  1. 1.

$|\left(\gamma+\mathcal{V}^{\perp}\right)^{=1}|=1$ and

  2. 2.

$|\left(\gamma+\mathcal{V}^{\perp}\right)^{=t}|\leq 2\cdot\binom{2C+1}{t-1}$,
for each $t\leq\ell$.

4.12 and 4.13 are powerful enough by themselves to achieve a weaker form of
Lemma 4.11: one can use them to show that $\MAJ_{n}$ is not
$\Omega(n^{-1/2})$-regular in any subspace of co-dimension
$O(n^{1/3})$.101010Following the proof sketch in Appendix A, the reason the
analysis breaks if we try to use only 4.13 and set $C=n^{1/3+\varepsilon}$ for
any $\varepsilon>0$ is as follows. By 4.13, there could be on the order of
$C^{3}=n^{1+3\varepsilon}$ weight three vectors in our signed sum
corresponding to the new Fourier coefficient. Since
$|\widehat{\MAJ_{n}}(\gamma)|=\Theta(n^{-3/2})$ when $\|\gamma\|_{1}=3$, these
coefficients could combine constructively to a magnitude of $\approx
n^{1+3\varepsilon}\cdot n^{-3/2}\gg n^{-1/2}$, thus potentially cancelling out
the (single) level one coefficient, which has magnitude
$|\widehat{\MAJ_{n}}(e_{1})|=\Theta(n^{-1/2})$.  We now use 4.12, 4.13, and
Lemma 4.14, the proofs of which are deferred to Appendix C, to prove Lemma
4.11.

###### Proof of Lemma 4.11.

Let $\mathcal{V}$ be a subspace of $\mathbb{F}_{2}^{n}$ of co-dimension
$C=\frac{\sqrt{n}}{10e}-1$, and suppose we restrict $\MAJ_{n}$ to the affine
subspace $\mathcal{U}=\alpha+\mathcal{V}$. Applying Lemma 4.14 with
$\ell=C+1$, we get a subset $S\subseteq\mathcal{W}$ (where $\mathcal{W}$ is
such that $\mathcal{W}\oplus\mathcal{V}^{\perp}=\mathbb{F}_{2}^{n}$) of size
at least $3$ such that each element $\gamma\in S$ satisfies both items in the
lemma. In particular, there must be $u\in S$ that satisfies both properties as
well as, $\mathbf{0}\not\in u+\mathcal{V}^{\perp}$ and $\mathbf{1}\notin
u+\mathcal{V}^{\perp}$.111111It is vital that $\mathbf{1}\not\in
M\alpha^{*}+\mathcal{V}^{\perp}$ since
$|\widehat{\MAJ_{n}}(\mathbf{1})|=|\widehat{\MAJ_{n}}(e_{i})|$, so they could
cancel each other out. For notational ease, let us denote
$E:=u+\mathcal{V}^{\perp}$. By Proposition 2.8, we have

$\displaystyle\left|\widehat{f_{\mathcal{U}}}(u)\right|=\Bigl{\lvert}\sum_{\eta\in
E}\widehat{f}(\eta)(-1)^{\eta,\alpha}\Bigr{\rvert}$
$\displaystyle\geq\left|\widehat{f}(e_{1})\right|-\sum_{t>1}^{n-1}|E^{=t}|\cdot\left|\widehat{f}\left(\sum_{i=1}^{t}e_{i}\right)\right|$
$\displaystyle=\left|\widehat{f}(e_{1})\right|-\sum_{t>1}^{\frac{n+1}{2}}\left(|E^{=t}|+|E^{=n-t+1}|\right)\cdot\left|\widehat{f}\left(\sum_{i=1}^{t}e_{i}\right)\right|.$
(6)

In the second to last step, we used the facts that majority is a symmetric
function and that $|E^{=1}|=1$ and $|E^{=n}|=0$. In the last step, we used
item 3 of 4.12. Next, we claim that

$\displaystyle|E^{=t}|+|E^{=n-t+1}|\leq\begin{cases}(t+1)\binom{2C+1}{t-1}&\text{
when }t\leq\ell,\\\ 2^{C+1}&\text{ otherwise}.\end{cases}~{}$ (7)

For the first case, when $t\leq\ell$, by item 2 of Lemma 4.14, we have
$|E^{=t}|\leq 2\binom{2C+1}{t-1}$. Furthermore, from 4.13, we have
$|E^{=n-t+1}|\leq\binom{C+1}{\leq t-1}\leq\binom{2C+1}{\leq
t-1}\leq(t-1)\cdot\binom{2C+1}{t-1}$ for all $1<t\leq\frac{\sqrt{n}}{10e}$.
When $t>\ell$, we note that both $|E^{=t}|$ and $|E^{=n-t+1}|$ are at most
$2^{C}$ since the dimension of $\mathcal{V}^{\perp}$ is $C$, and this is
tighter when $t>C+1$.

Using Equation 7 and 4.12, we can estimate the sum in Section 4.2.2 as

$\displaystyle\left|\widehat{f_{\mathcal{U}}}(u)\right|\leq\left|\widehat{f}(e_{1})\right|\left(1-\underbrace{\sum_{t=3}^{\ell}\binom{2C+1}{t-1}\left(\frac{t}{n}\right)^{\frac{t-1}{2}}(t+1)}_{A}-\underbrace{\sum_{t>\ell}^{\frac{n+1}{2}}2^{C+1}\left(\frac{t}{n}\right)^{\frac{t-1}{2}}}_{B}\right).$

We complete the argument by showing an upper bound on both the above sums.
Starting with $A$, and recalling that $C=\frac{\sqrt{n}}{10e}-1$, we see that

$\displaystyle A$
$\displaystyle\leq\sum_{t=3}^{\frac{\sqrt{n}}{10e}}\left(\frac{\sqrt{n}}{5(t-1)}\right)^{t-1}\left(\frac{t}{n}\right)^{\frac{t-1}{2}}\cdot(t+1)$
($\binom{n}{k}\leq\left(\frac{en}{k}\right)^{k}.$)
$\displaystyle\leq\sum_{t=3}^{\frac{\sqrt{n}}{10e}}\left(\frac{\sqrt{t}}{5(t-1)}\right)^{t-1}\cdot(t+1)$
$\displaystyle\leq\sum_{t=3}^{\frac{\sqrt{n}}{10e}}\left(\frac{(t+1)^{\frac{1}{2}}}{2(t+1)}\right)^{t-1}\cdot(t+1)$
($5(t-1)\geq 2(t+1)\quad\forall t\geq 3$.)
$\displaystyle=\sum_{t=3}^{\frac{\sqrt{n}}{10e}}\left(\frac{1}{2(t+1)^{1/2}}\right)^{t-1}\cdot(t+1)\leq\sum_{i=2}^{\infty}\left(\frac{1}{2}\right)^{i}\leq
1/2.$

In the penultimate inequality, we used the fact that for the first term, when
$t=3$, we have
$\left(\frac{1}{2(t+1)^{1/2}}\right)^{t-1}\cdot(t+1)=\left(\frac{1}{4}\right)^{2}\cdot
4=1/4$, and the ratio of the summands (for $t\geq 3$) is

$\frac{(2(t+1)^{1/2})^{t-1}}{(2(t+2)^{1/2})^{t}}\cdot\frac{t+2}{t+1}\leq\frac{1}{2(t+1)^{1/2}}\cdot
2\leq\frac{1}{(t+1)^{1/2}}\leq\frac{1}{2}.$

To bound $B$, we note that the function
$h(x)=\left(\frac{x}{n}\right)^{(x-1)/2}$ is strictly convex, which means its
maximum occurs either at $t=C$ or $t=\frac{n+1}{2}$. Again, setting
$C=\frac{\sqrt{n}}{10e}-1$, a quick calculation shows that the maximum is
achieved for the first term, and this term is at most

$\displaystyle
2^{\frac{\sqrt{n}}{10e}}\cdot\left(\frac{1}{10e\sqrt{n}}\right)^{\frac{\sqrt{n}}{20e}}$
$\displaystyle\leq 2^{\frac{\sqrt{n}}{10e}}\cdot 2^{-\log
n\cdot\frac{\sqrt{n}}{40e}}$ $\displaystyle\leq
2^{\frac{\sqrt{n}}{10e}-\left(\frac{\sqrt{n}}{10e}+2\log n\right)}$
($\frac{\sqrt{n}}{40e}\log n\geq\frac{\sqrt{n}}{10e}+2\log n$ for large enough
$n$.) $\displaystyle=2^{-2\log n}=\frac{1}{n^{2}}.$

This implies that $B\leq n\cdot\frac{1}{n^{2}}\leq o(1)$. Using item 2 of
4.12, we conclude that there is a non-trivial Fourier coefficient

$\left|\widehat{f_{\mathcal{U}}}(u)\right|\geq\left|\widehat{f}(e_{1})\right|\left(1-1/2-o(1)\right)=\Omega(n^{-1/2}).\qed$

##  5 Applications

We now present an application of Theorem 1.1 that shows a tradeoff between the
dimension of a disperser and its Fourier degree, and a connection to
extractors, as well. First, we introduce a definition that generalizes Boolean
functions and helps us reason about the Fourier spectrum of dispersers.

######  Definition 5.1.

We say a function $f:\mathbb{F}_{2}^{n}\rightarrow\mathbb{R}$ is $G$-granular
if for every $x\in\mathbb{F}_{2}^{n}$, we have that $f(x)$ is an integer
multiple of $G$.

######  Claim 5.2.

If a degree $d$ function $f:\mathbb{F}_{2}^{n}\rightarrow\mathbb{R}$ is
$G$-granular, then for every $\gamma\in\mathbb{F}_{2}^{n}$, we have that
$\widehat{f}(\gamma)$ is an integer multiple of $2^{-d}\cdot G$.

###### Proof.

Note that if we associate $\mathbb{F}_{2}$ with $\\{0,1\\}$, any
$f:\mathbb{F}_{2}^{n}\to\mathbb{R}$ has a real multilinear polynomial
representation $q:\\{0,1\\}^{n}\to\mathbb{R}$, where $q(x)=f(x)$ for all
$x\in\\{0,1\\}^{n}$ (see Exercise 1.9 in [ODo21]). In particular, we can write
$q$ as a sum of its indicators:

$q(x)=\sum_{a\in\\{0,1\\}^{n}}\mathbbm{1}\\{x=a\\}\cdot q(a).$

Noting that $\mathbbm{1}\\{x=a\\}=\prod_{i}(1-a_{i}-x_{i})(1-2a_{i})$, we see
that every coefficient of $q$ is an integer multiple of $G$.

However, we can also associate $f$ with a real multilinear polynomial,
$p:\\{\pm 1\\}^{n}\to\mathbb{R}$, such that $f(x)=p((-1)^{x})$ for all
$x\in\mathbb{F}_{2}^{n}$. Note then, that
$p(x)=q((1-x_{1})/2,\ldots,(1-x_{n})/2))$, so if $p$ has degree $d$, then all
its coefficients are integer multiples of $G\cdot 2^{-d}$. Finally, note that
$f$ and $p$ have the same Fourier coefficients (and therefore degree), which
implies the result. ∎

We now show that low degree granular functions cannot have a large parity kill
number. As a consequence, we get that low-degree affine dispersers cannot have
small dimension (Corollary 1.2).

######  Lemma 5.3.

Every degree $d$ function $f:\mathbb{F}_{2}^{n}\rightarrow[-1,1]$ that is
$G$-granular satisfies

$C_{\min}^{\oplus}[f]\leq n-\Omega\left(n^{1/d!}(d+\log n/G)^{-2}\right).$

###### Proof.

If $f$ is $G$-granular and degree $d$, then from 5.2 we know that all its
Fourier coefficients must be integer multiples of $2^{-d}\cdot G$. Moreover, a
Fourier coefficient of $f$ in any affine subspace is simply a signed sum of
the Fourier coefficients of $f$ and therefore it must also be an integer
multiple of $2^{-d}\cdot G$. This shows that if $f$ is $\delta$-regular in
some affine subspace $\mathcal{U}$ with $\delta<2^{-d}\cdot G$, then
$f_{\mathcal{U}}$ must be constant. The lemma follows by using Theorem 1.1 for
$\delta=2^{-d-1}\cdot G$. ∎

###### Proof of Corollary 1.2.

Using $f$, we can construct a degree $d$ function
$h:\mathbb{F}_{2}^{n}\to[-1,1]$ as $h(x)=1-\frac{2f(x)}{C}$. Noting that $h$
is $2/C$-granular and using the above lemma, it follows that

$C_{\min}^{\oplus}[f]=C_{\min}^{\oplus}[h]\leq
n-\Omega\left(n^{1/d!}(d+\log(nC))^{-2}\right),$

which shows that there is some affine subspace of dimension at least
$\Omega\left(n^{1/d!}(2d+\log(nC))^{-2}\right)$ where $f$ is constant. ∎

Last, we give a connection between the notion of $\delta$-regularity and
affine extractors. Formally, we define affine extractors as follows.

######  Definition 5.4 (Affine Extractor).

A function $f:\mathbb{F}_{2}^{n}\to\\{0,\ldots,C\\}$ is said to be a
$(k,\delta)$-_affine extractor_ if for all affine subspaces $\mathcal{U}$ of
dimension at least $k$, we have that

$|f_{\mathcal{U}}-\mathsf{Unif}_{C}|\leq\delta,$

where $\mathsf{Unif}_{C}$ is the uniform distribution over $\\{0,\ldots,C\\}$.

######  Claim 5.5.

If $f$ is a $(k,\delta)$-extractor, then $f$ becomes $2C\delta$-regular when
restricted to any affine subspace of dimension at least $k+1$.

###### Proof.

Note that if $f:\mathbb{F}_{2}^{n}\to\\{0,\ldots,C\\}$ is a
$(k,\delta)$-extractor then in any affine subspace $\mathcal{U}$, of dimension
at least $k$, we have,

$\Bigl{\lvert}\widehat{f_{\mathcal{U}}}(\chi_{\mathbf{0}})-\frac{C}{2}\Bigr{\rvert}=\Bigl{\lvert}\sum_{c}c\left(\mathop{\bf
Pr\/}_{x\in\mathcal{U}}[f(x)=c]-\frac{1}{C+1}\right)\Bigr{\rvert}\leq
C\sum_{c}\Bigl{\lvert}\mathop{\bf
Pr\/}_{x\in\mathcal{U}}[f(x)=c]-\frac{1}{C+1}\Bigr{\rvert}\leq 2C\delta.$

Suppose $f$ is a $(k,\delta)$-affine extractor. Let us assume to a
contradiction that $\mathcal{U}$ is an affine subspace of dimension at least
$k+1$, where $f_{\mathcal{U}}$ has a Fourier coefficient with magnitude larger
than $2C\delta$. By Corollary C.1, we can fix the parity corresponding to this
Fourier coefficient in such a way that the bias of the function increases by
$2C\delta$, which gives the desired contradiction. ∎

##  6 Future Directions

We highlight two open problems that offer particularly interesting research
directions. First, there is a tantalizing, and large, gap between our Theorem
1.1 and Lemma 4.3 for bounded degree $d$ functions. We suspect that Lemma 4.3
is closer to being tight and ask the following question.

######  Direction 6.1.

Can the upper bound on $\mathsf{r}(f,\delta)$ in Theorem 1.1 be improved?

Moreover, it would be interesting to find explicit Boolean and bounded
functions with large $r(f,\delta)$ values.

######  Direction 6.2.

Find (explicit) examples of functions $f:\mathbb{F}_{2}^{n}\to[-1,1]$ with
$r(f,\delta)$ values comparable to those obtained in Lemma 4.3. Similarly,
find (explicit) Boolean functions with similar $r(f,\delta)$ values.

##  7 Acknowledgements

We thank Anup Rao for posing the question that launched this project and for
his invaluable advice and feedback. We are also grateful Paul Beame for his
extremely helpful advice, discussions, and feedback. Finally, we thank Sandy
Kaplan for detailed feedback on this writeup.

## References

  * [Alo+01] Noga Alon, Eldar Fischer, Michael Krivelevich and Mario Szegedy  “Efficient Testing of Large Graphs”  In _Combinatorica_ 20, 2001  DOI: 10.1007/s004930070001
  * [Bd02] Harry Buhrman and Ronald de Wolf  “Complexity measures and decision tree complexity: a survey”  In _Theoretical Computer Science_ 288.1, 2002, pp. 21–43  DOI: https://doi.org/10.1016/S0304-3975(01)00144-X
  * [Ben17] Shalev Ben David  “Quantum speedups in query complexity”, 2017
  * [BK12] Eli Ben-Sasson and Swastik Kopparty  “Affine Dispersers from Subspace Polynomials”  In _SIAM J. Comput._ 41.4, 2012, pp. 880–914
  * [CGL21] Eshan Chattopadhyay, Jesse Goodman and Jyun-Jie Liao  “Affine Extractors for Almost Logarithmic Entropy”  In _FOCS_ IEEE, 2021, pp. 622–633
  * [CT15] Gil Cohen and Avishay Tal  “Two Structural Results for Low Degree Polynomials and Applications”  In _APPROX-RANDOM_ 40, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 680–709
  * [FK96] Alan M. Frieze and Ravi Kannan  “The Regularity Lemma and Approximation Schemes for Dense Problems”  In _FOCS_ IEEE Computer Society, 1996, pp. 12–20
  * [Gir+21] Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz and Wei Zhan  “Parallel Repetition for the GHZ Game: A Simpler Proof”  In _APPROX-RANDOM_ 207, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, pp. 62:1–62:19
  * [Gre05] Ben Green  “A Szemerédi-type regularity lemma in abelian groups”  In _Geometric and Functional Analysis_ 15, 2005, pp. 340–376  DOI: 10.1007/s00039-005-0509-8
  * [HJ63] A.. Hales and R.. Jewett  “Regularity and Positional Games”  In _Transactions of the American Mathematical Society_ 106.2 American Mathematical Society, 1963, pp. 222–229
  * [Hoe63] Wassily Hoeffding  “Probability Inequalities for Sums of Bounded Random Variables”  In _Journal of the American Statistical Association_ 58.301 [American Statistical Association, Taylor & Francis, Ltd.], 1963, pp. 13–30  URL: http://www.jstor.org/stable/2282952
  * [Hos+16] Kaave Hosseini, Shachar Lovett, Guy Moshkovitz and Asaf Shapira  “An improved lower bound for arithmetic regularity”  In _Mathematical Proceedings of the Cambridge Philosophical Society_ 161.2 Cambridge University Press, 2016, pp. 193–197  DOI: 10.1017/S030500411600013X
  * [htt] Fedor Petrov (https://mathoverflow.net/users/4312/fedor-petrov)  “Low-Hamming weight vectors in low-dimensional subspaces of $\mathbb{F}_{p}^{n}$”, MathOverflow  URL: https://mathoverflow.net/q/389026
  * [KM23] Zander Kelley and Raghu Meka  “Strong Bounds for 3-Progressions”, 2023  arXiv:2302.05537 [math.NT]
  * [Li16] Xin Li  “Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy”  In _FOCS_ IEEE Computer Society, 2016, pp. 168–177
  * [Mes95] Roy Meshulam  “On Subsets of Finite Abelian Groups with No 3-Term Arithmetic Progressions”  In _J. Comb. Theory Ser. A_ 71.1 USA: Academic Press, Inc., 1995, pp. 168–172  DOI: 10.1016/0097-3165(95)90024-1
  * [Mid04] Gatis Midrijanis  “Exact quantum query complexity for total Boolean functions”  arXiv, 2004  DOI: 10.48550/ARXIV.QUANT-PH/0403168
  * [ODo+14] Ryan O’Donnell, John Wright, Yu Zhao, Xiaorui Sun and Li-Yang Tan  “A Composition Theorem for Parity Kill Number”  In _Computational Complexity Conference_ IEEE Computer Society, 2014, pp. 144–154
  * [ODo21] Ryan O’Donnell  “Analysis of Boolean Functions”  In _CoRR_ abs/2105.10386, 2021
  * [Rot53] K.. Roth  “On Certain Sets of Integers”  In _Journal of the London Mathematical Society_ s1-28.1, 1953, pp. 104–109  DOI: https://doi.org/10.1112/jlms/s1-28.1.104
  * [RS76] I. Ruzsa and E. Szemerédi  “Triple systems with no six points carrying three triangles”  In _Combinatorica_ 18, 1976
  * [Sha06] Asaf Shapira  “Graph Property Testing and Related Problems”  University of Tel-Aviv, 2006
  * [Sha11] Ronen Shaltiel  “Dispersers for Affine Sources with Sub-polynomial Entropy”  In _2011 IEEE 52nd Annual Symposium on Foundations of Computer Science_ , 2011, pp. 247–256  DOI: 10.1109/FOCS.2011.37
  * [Sze75] Endre Szemerédi  “Regular partitions of graphs”, 1975
  * [Tal13] Avishay Tal  “Properties and applications of boolean function composition”  In _ITCS_ ACM, 2013, pp. 441–454

##  Appendix A Omitted Sketches

We give the main ideas behind the lower bounds in Table 1.

##### Sketch of Lemma 4.2.

The proof of this claim is based on the homogeneous degree-one function
$f(x)=\frac{1}{n}\sum_{i}(-1)^{x_{i}}$. Its key idea comes from 4.1, which we
use to show that if the dimension of $\mathrm{codim}(\mathcal{V})<n/2$, then
at least one shift of $\mathcal{V}^{\perp}$ must contain exactly one standard
basis vector. By the preceding discussion, this implies that
$f_{\alpha+\mathcal{V}}$ has a non-trivial Fourier coefficient with magnitude
exactly $1/n>\delta$.

We remark that Lemma 4.2 is tight. The function $f$ is symmetric, and for any
such function, we can fix $n/2$ parities to obtain an affine subspace where
every vector has weight $n/2$, which in turn fixes the function.

##### Sketch of Lemma 4.3 and Corollary 4.7.

To achieve Lemma 4.3, one might expect to extend the above argument to the
homogeneous degree $d$ function
$f(x)=\binom{n}{d}^{-1}\sum_{\gamma:\|\gamma\|_{1}=d}(-1)^{\langle{\gamma,x}\rangle}$.
Unfortunately, this function is symmetric, and we have $r(f,0)\leq n/2$. We
therefore consider a random homogeneous degree $d$ function
$f_{\mathbf{z}}(x)=\binom{n}{d}^{-1}\sum_{\gamma:\|\gamma\|_{1}=d}\mathbf{z}_{\gamma}\cdot(-1)^{\langle{\gamma,x}\rangle},$
where each $\mathbf{z}_{\gamma}$ is a random sign. A simple argument, again
utilizing 4.1, shows that there must be at least $\binom{k}{d}$ affine
subspaces of $\mathcal{V}^{\perp}$ with at least one vector of weight $d$. By
our earlier reasoning, each of those subspaces must in fact contain at least
two vectors of weight $d$ so that the restricted function would have a non-
trivial Fourier coefficient with magnitude $\binom{n}{d}^{-1}>\delta$.
Moreover, the probability (over the signs $\mathbf{z}_{\gamma}$’s) that each
of the $\binom{k}{d}$ signed sums cancels is at most $2^{-\binom{k}{d}}$, and
a union bound over all the possible affine subspaces of dimension
$k=\Theta(dn^{1/(d-1)})$ completes the argument.

If we restrict our attention to Boolean functions, we might hope to obtain
strong upper bounds for $\mathsf{r}(f,\delta)$; however, Corollary 4.7 rules
this out. The proof of this claim is based on a simple lemma of [Hos+16]
(Lemma 4.5), which uses the probabilistic method to convert a bounded function
that is not $\delta$-regular in large affine subspaces to a Boolean function
with the same property. Applying this lemma to the lower bound from Lemma 4.3
achieves the result.

##### Sketch of Lemma 4.11.

This lower bound is based on the majority function. Its key idea is that there
exists a non-trivial affine subspace of $\mathcal{V}^{\perp}$ containing
_exactly_ one weight-$1$ vector and relatively few vectors of higher weight
(see Lemma 4.14). Then, we use properties of the Fourier spectrum of the
majority function to show that the signed sum of the Fourier coefficients of
majority corresponding to vectors in this affine subspace, is on the order of
$\left|\widehat{f}(e_{1})\right|=\Omega(n^{-1/2})$. Specifically, we argue
that even if the coefficients coming from higher weight vectors in the
aforementioned sum combined in the most constructive way possible, they cannot
combine to more than $\Bigl{\lvert}\widehat{f}(e_{1})\Bigr{\rvert}/2$. We also
note that Lemma 4.11 is tight up to constant factors via Proposition 1.5.
Conversely, Lemma 4.11 implies that for $\delta\geq n^{-1/2}$, the majority
function on $O(1/\delta^{2})$ variables is an explicit Boolean function for
which $\mathsf{r}(f,\delta)\geq\Omega(1/\delta)$.

##### Rationale for Lemma 4.8.

The last entry in the table corresponds to Lemma 4.8 and is based on a simple
function $f$ on 4 inputs that is composed with itself $k$ times. We use key
properties of the composition of Boolean functions (from [Tal13, ODo+14]) to
achieve the bound. The function itself is the same one considered in [ODo+14],
and we use their main theorem crucially to obtain our lower bound. We present
a slightly generalized version of the main theorem of [ODo+14], so we include
a proof in Appendix B.

We make some final comments about the lower bounds from Corollary 4.7. The
Boolean functions that achieve the lower bounds share the property that the
magnitudes of their Fourier coefficients are extremely close to their bounded
counterparts in Lemma 4.3. However, even though the bounded functions
themselves have low degree, the Boolean functions are very far from being low-
degree functions; in fact, _almost all_ their Fourier mass comes from the
high-degree terms. Notably, these functions are also non-explicit affine
dispersers with small dimension, and it would be interesting to find explicit
Boolean functions with similar strong lower bounds on the
$\mathsf{r}(f,\delta)$.

##  Appendix B Short Proof of the Parity Kill Number Theorem ([ODo+14])

We present a more concise and slightly improved version of the main theorem of
[ODo+14], which appears as Theorem 4.9 above.

The following proposition suffices to prove the theorem.

######  Proposition B.1.

Let $f^{\prime}:\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}\to\mathbb{F}_{2}$ and
$g:\mathbb{F}_{2}^{k}\to\mathbb{F}_{2}$. We let
$f:\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{k}\to F_{2}$ be defined as

$f(x,y)=f^{\prime}(x,g(y)).$

Then for any affine subspace
$H\subseteq\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{k}$ on which $f$ is
constant, there exists some
$H^{\prime}\subseteq\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}$ on which
$f^{\prime}$ is constant such that either:

  1. 1.

$\mathrm{codim}(H^{\prime})\leq\mathrm{codim}(H)-B_{g}$, where
$B_{g}=\max\\{1,\log C_{\min}^{\oplus}[g]-1\\}$, as before.

  2. 2.

The $(n+1)$-st coordinate (so $g(y)$) is irrelevant in $H^{\prime}$ and
$\mathrm{codim}(H^{\prime})\leq\mathrm{codim}(H)$.

Furthermore, among the first $n$ coordinates, any coordinate that was
irrelevant in $H$ remains irrelevant in $H^{\prime}$.

Before proving Proposition B.1, let’s see how it implies Theorem 4.9. Note
that $f\circ g=f(g(x_{1}),...,g(x_{n}))$, so we will apply Proposition B.1 $n$
times. The crucial observation is that we must fall into the first case of
Proposition B.1 at least $C_{\min}[f]$ times. This is because if $f(x,y)$ is
constant on $H$, then $H$ must depend on at least $C_{\min}[f]$ coordinates.

Let then $H\subseteq\mathbb{F}_{2}^{n\cdot m}$ be a minimum co-dimension
subspace on which $f\circ g$ is constant, so that
$\mathrm{codim}(H)=C_{\min}^{\oplus}[f\circ g]$. Applying Proposition B.1 $n$
times, we derive $H^{\prime}$ on which $f$ is constant.

$\displaystyle C_{\min}^{\oplus}[f]$
$\displaystyle\leq\mathrm{codim}(H^{\prime})$
$\displaystyle\leq\mathrm{codim}(H)-B_{g}\cdot C_{\min}[f]$
$\displaystyle=C_{\min}^{\oplus}[f\circ g]-B_{g}\cdot C_{\min}[f].$

Rearranging gives the theorem.

Finally, before we prove Proposition B.1, we need the following lemma, the
proof of which is not complicated but we will omit and can be found in
[ODo+14].

######  Lemma B.2 ([ODo+14], Lemma 3.3).

Let $H\subseteq\mathbb{F}_{2}^{k}\times\mathbb{F}_{2}^{n}$ be an affine
subspace. Then there exists an invertible linear transformation $L$ on
$\mathbb{F}_{2}^{k}\times\mathbb{F}_{2}^{n}$ such that, after applying this
linear transformation, the constraints of $H$ can be partitioned into

  * •

$\mathcal{B}_{x,y}$, which contain constraints of the form
$x_{i}+y_{i}=\sigma_{i}$, for $1\leq i\leq t$.

  * •

$\mathcal{B}_{x}$, which contain constraints of the form $x_{j}=\sigma_{j}$,
for $t+1\leq j\leq t^{\prime}$.

  * •

$\mathcal{B}_{y}$, which contain constraints of the form $y_{k}=\sigma_{k}$,
for $t^{\prime}+1\leq k\leq t^{\prime\prime}$.

and $t+(t^{\prime}-t)+(t^{\prime\prime}-t^{\prime})=\mathrm{codim}(H)$.

The takeaway of the above lemma is that since parity kill number is invariant
under affine transformations, we can “canonize” any affine subspace in a way
that minimizes the interactions between coordinates.

###### Proof of Proposition B.1.

WLOG suppose that $H$ is of the form given in Lemma B.2.

  1. 1.

Easy Case: $|\mathcal{B}_{x,y}|=0$.

Let’s denote $C_{y}$ as the set of all $y$ that satisfy the constraints in
$\mathcal{B}_{y}$, and let $C_{x}$ (analogously) be the set of $x$ that
satisfy the constraints of $\mathcal{B}_{x}$.

    1. a)

Subcase 1: Suppose that $g(y)=b$ for all $y\in C_{y}$. Then we can let

$H^{\prime}=\left\\{(x,z)\left|\right.x\in C_{x},z=b\right\\}.$

$f^{\prime}$ is clearly constant on $H^{\prime}$. Note that

$\mathrm{codim}(H^{\prime})=|\mathcal{B}_{x}|+1=\mathrm{codim}(H)-|\mathcal{B}_{y}|+1\leq\mathrm{codim}(H)-C_{\min}^{\oplus}[g]+1\leq\mathrm{codim}(H)-B_{g},$

as desired for the first case of Proposition B.1.

    2. b)

Subcase 2: Suppose that $g$ is not constant on the inputs in $C_{y}$. In this
case, we claim that

$H^{\prime}=\left\\{(x,z)\left|\right.x\in C_{x}\right\\}$

makes $f^{\prime}$ constant. Indeed, suppose it doesn’t. Then there are two
inputs $(x,z)$ and $(x^{\prime},z^{\prime})$ such that $f^{\prime}(x,z)\neq
f^{\prime}(x^{\prime},z^{\prime})$. But then, we can pick $y,y^{\prime}\in
C_{y}$ such that $g(y)=z$ and $g(y^{\prime})=z^{\prime}$, and this results in
$(x,y),(x^{\prime},y^{\prime})\in H$ such that $f(x,y)\neq
f(x^{\prime},y^{\prime})$, a contradiction.

Finally, note that
$\mathrm{codim}(H^{\prime})=|\mathcal{B}_{x}|=\mathrm{codim}(H)-|\mathcal{B}_{y}|\leq\mathrm{codim}(H)-B_{g}$.
In fact, we don’t even need this to be true in order to fall into the second
case of the proposition (since $H^{\prime}$ does not depend on its last
coordinate), but it is nonetheless true.

  2. 2.

(Slightly) Harder Case: $|\mathcal{B}_{x,y}|\neq 0$.

    1. a)

Subcase 1: $g$ becomes a junta on $y_{1},...,y_{t}$ when restricted to
$C_{y}$. In this case, let $I=\\{i_{1},...,i_{s}\\}\subseteq[t]$ be the junta
variables, so that $g(y)=h(y_{i_{1}},...,y_{i_{s}})$ for all $y\in C_{y}$.
Then we claim that $f^{\prime}$ is constant on

$H^{\prime}=\left\\{(x,z)|x\in C_{x},x_{i}=0\>\forall i\in[t]\setminus
I,z=h(x_{i_{1}}\oplus\sigma_{i_{1}},...x_{i_{s}}\oplus\sigma_{i_{s}})\right\\}.$

Indeed, suppose it is not, so that $f^{\prime}(x,z)\neq
f^{\prime}(x^{\prime},z^{\prime})$. Take $y\in C_{y}$ such that
$y_{i}=\sigma_{i}\>\forall i\in[t]\setminus I$, and $y_{j}=\sigma_{j}\oplus
x_{j}\>\forall k\in I$. Then we have that $g(y)=h(y_{i_{1}},...,y_{i_{s}})=z$.
Similarly, we can find $y^{\prime}\in C_{y}$ such that
$g(y^{\prime})=z^{\prime}$. We end up at a contradiction though, since $(x,y)$
and $(x^{\prime},y^{\prime})$ are both in $H$, but are such that $f(x,y)\neq
f(x^{\prime},y^{\prime})$.

Finally, note that the codimension of $H^{\prime}$ is exactly
$|\mathcal{B}_{x}|+|\mathcal{B}_{x,y}|-s+1=\mathrm{codim}(H)-(|\mathcal{B}_{y}|+s)+1$.
Next, we claim that $|\mathcal{B}|+s\geq\log C_{\min}^{\oplus}[g]$. To see why
this is the case, note that we can fix $g$ by fixing at most
$|\mathcal{B}_{y}|+2^{s}$ parities/variables. This implies that
$|\mathcal{B}_{y}|+2^{s}\geq C_{\min}^{\oplus}[g]$ which implies that
$|\mathcal{B}_{y}|+s\geq\log C_{\min}^{\oplus}[g]$. Thus, we have that

$\mathrm{codim}(H^{\prime})\leq\mathrm{codim}(H)-B_{g},$

as desired.

    2. b)

Subcase 2: There exists some $b_{1},...,b_{t}$ such that $g(y)$ is _not_
constant on

$C_{y}^{\prime}:=\left\\{y\left|\begin{subarray}{c}y\in C_{y}\\\
y_{i}=b_{i}\>\>\forall\>1\leq i\leq t\end{subarray}\right.\right\\}.$

In this case, let

$H^{\prime}=\left\\{(x,z)\>|\>x\in
C_{x},\>\>x_{j}=b_{j}\oplus\sigma_{j}\>\>\forall\>1\leq j\leq t\right\\}.$

First, we claim that $f^{\prime}$ is constant on $H^{\prime}$. As before,
suppose it is not, so that $f^{\prime}(x,z)\neq
f^{\prime}(x^{\prime},z^{\prime})$. Then by definition, there exists
$y,y^{\prime}$ such that $y_{i}=y_{i}^{\prime}=b_{i}$ for all $i\in[t]$, such
that $g(y)=z$ and $g(y^{\prime})=z^{\prime}$. In this case, $(x,y)$ and
$(x^{\prime},y^{\prime})$ are both in $H$, but are such that $f(x,y)\neq
f(x^{\prime},y^{\prime})$, a contradiction.

Finally, note that $\mathrm{codim}(H^{\prime})\leq\mathrm{codim}(H)$, but that
$H^{\prime}$ is independent of its last coordinate $z$, so that we fall into
the second case of Proposition B.1.

∎

##  Appendix C Omitted Proofs

###  C.1 Proofs of Proposition 1.4 and Proposition 1.5

In this section we provide the proofs of Proposition 1.4 and Proposition 1.5.
We first begin with a corollary of Proposition 2.8 which will be useful in the
analysis of the claims.

######  Corollary C.1.

When $\mathcal{V}$ has dimension $n-1$, this corresponds to fixing a single
parity $\sum_{i:\gamma_{i}=1}x_{i}$ to $b\in\\{0,1\\}$. Then
$\mathcal{V}^{\perp}$ is simply $\spn(\\{\gamma\\})$ and $\alpha$ is any
vector such that $\langle{\gamma,\alpha}\rangle=b$.

Then for all $\gamma^{\prime}\neq\gamma$ we have by Proposition 2.8 that

$\widehat{f_{\alpha+\mathcal{V}}}(\chi_{\gamma^{\prime}})=(-1)^{\langle{\gamma^{\prime},\alpha}\rangle}\widehat{f}(\gamma^{\prime})+(-1)^{\langle{\gamma+\gamma^{\prime},\alpha}\rangle}=(-1)^{\langle{\gamma^{\prime},\alpha}\rangle}\left(\widehat{f}(\gamma^{\prime})+(-1)^{b}\cdot\widehat{f}(\gamma+\gamma^{\prime})\right).$

In particular, there exists a choice of $b$ such that

$\left|\widehat{f_{\alpha+\mathcal{V}}}(\chi_{\mathbf{0}})\right|=\left|\widehat{f}(\mathbf{0})+\widehat{f}(\gamma)\right|.$

###### Proof of Proposition 1.4.

Given some $f:\mathbb{F}_{2}^{n}\to[-1,1]$, consider the following simple
procedure:

  * •

While at least $\delta$ fraction of $\pi\in\Pi$ have some $\gamma_{\pi}$ such
that $|\widehat{f_{\pi}}(\gamma_{\pi})|>\delta$, further partition each $\pi$
into $\pi\cap\\{x:\langle{\gamma_{\pi},x}\rangle=0\\}$ and
$\pi\cap\\{x:\langle{\gamma_{\pi},x}\rangle=1\\}$.

We would like to show that we cannot perform the above partitioning action
more that $\frac{1}{\delta^{3}}$ times. Towards this end, define the potential
function $\Phi(\Pi):=\mathop{\bf
E\/}_{\pi\in\Pi}\widehat{f}_{\pi}(0)^{2}=\mathop{\bf
E\/}_{\pi\in\Pi}[(\mathop{\bf E\/}f_{\pi})^{2}]\in[0,1]$. Whenever we
partition further, by Corollary C.1 each $|\widehat{f}_{\pi}(0)|$ is updated
to either $|\widehat{f}_{\pi}(0)+\widehat{f}_{\pi}(\gamma_{\pi})|$ or
$|\widehat{f}_{\pi}(0)-\widehat{f}_{\pi}(\gamma_{\pi})|$. Therefore, the
contribution of $\pi$ to $\Phi$ in one step of the partitioning process is

$\frac{1}{2}\left((\widehat{f}_{\pi}(0)+\widehat{f}_{\pi}(\gamma_{\pi}))^{2}+(\widehat{f}_{\pi}(0)-\widehat{f}_{\pi}(\gamma_{\pi}))^{2}\right)-\widehat{f}_{\pi}(0)^{2}=\widehat{f}_{\pi}(\gamma_{\pi})^{2}.$

Since we assume at least $\delta$ fraction of $\pi\in\Pi$ had some
$\gamma_{\pi}$ such that $|\widehat{f_{\pi}}(\gamma_{\pi})|>\delta$, at each
step of the refinement $\Phi$ must increase by at least $\delta^{3}$,
completing the proof. ∎

###### Proof of Proposition 1.5.

Suppose without loss of generality, $\mathop{\bf E\/}f\geq 0$. Start with the
trivial subspace, $\pi_{0}=\mathbb{F}_{2}^{n}$. While there exists $\gamma$
such that $|\widehat{f}_{\pi_{t}}(\gamma)|>\delta$, by Corollary C.1 we can
fix the parity corresponding to $\gamma$ in such a way that ensures that
$|\widehat{f}_{\pi_{t+1}}(0)|=\left|\widehat{f}_{\pi_{t}}(0)+|\widehat{f}_{\pi_{t}}(\gamma)|\right|>\widehat{f_{\pi_{t}}}(\gamma)+\delta$.
Since $\widehat{f}_{\pi}(0)\leq 1$ for all $\pi$, this process can happen at
most $\frac{1}{\delta}$ times. ∎

###  C.2 4.12

###### Proof of 4.12.

Theorem 5.19 in [ODo21] gives the following formula for the Fourier
coefficients of the Majority function:

$\Bigl{\lvert}\widehat{\MAJ_{n}}(\gamma)\Bigr{\rvert}=\frac{\binom{\frac{n-1}{2}}{\frac{t-1}{2}}}{\binom{n-1}{t-1}}\cdot\frac{2}{2^{n}}\binom{n-1}{\frac{n-1}{2}},$

which holds for all $\gamma$ such that $\|\gamma\|_{1}=t$ is odd. Otherwise,
$\widehat{\MAJ_{n}}(\gamma)=0$. By the above equation, we have that

$\displaystyle\frac{\widehat{\MAJ_{n}}(\gamma)}{\widehat{\MAJ_{n}}(e_{1})}$
$\displaystyle=\frac{\binom{\frac{n-1}{2}}{\frac{t-1}{2}}}{\binom{n-1}{t-1}}$
$\displaystyle=\frac{\left(\frac{n-1}{2}\right)!\cdot(t-1)!\cdot(n-t)!}{\left(\frac{t-1}{2}\right)!\cdot\left(\frac{n-t}{2}\right)!\cdot(n-1)!}$
$\displaystyle=\frac{(t-2)!!\cdot(n-t-1)!!}{(n-2)!!}$
$\displaystyle=\frac{(t-2)\cdot(t-4)\cdots 1}{(n-2)\cdot(n-4)\cdots(n-t+1)}$
$\displaystyle\leq\left(\frac{t}{n}\right)^{\frac{t-1}{2}}.\qed$

###  C.3 4.13

###### Proof of 4.13.

First, consider

$\tilde{\mathcal{U}}=\begin{cases}\mathcal{U}&\text{ if }t\leq n/2\\\
\mathbf{1}+\mathcal{U}&\text{ if }t>n/2.\end{cases}$

Note that $\dim(\tilde{\mathcal{U}})\leq\dim(\mathcal{V})+1$. Moreover, note
that $|\mathcal{U}^{=t}|=|\tilde{\mathcal{U}}^{=t^{*}}|$. Using Gaussian
elimination, we can find a basis find a basis $b_{1},\ldots,b_{k}$ for
$\mathcal{U}$ such that $N(b_{1})<N(b_{2})<\ldots<N(b_{k})$, where
$k=\dim(\mathcal{U})$ and $N(b):=\min_{i}\\{i:b_{i}\neq 0\\}$. Moreover (again
via Gaussian elimination), we can ensure that $b_{i}$ is the only basis vector
with a $1$ in entry $N(b_{i})$. Therefore, any vector in $\mathcal{U}$
involving more than $t^{*}$ basis vectors must have more than $t^{*}$ nonzero
entries. Therefore, we have that

$|\mathcal{U}^{=t}|\leq|\mathcal{U}^{\leq t}|=|\tilde{\mathcal{U}}^{\leq
t^{*}}|\leq\sum_{i}^{t^{*}}\binom{\dim(\tilde{\mathcal{U}})}{i}\leq\binom{\dim(\mathcal{V})+1}{\leq
t^{*}}.\qed$

###  C.4 Lemma 4.14

###### Proof of Lemma 4.14.

We will prove the statement by induction on $\ell$. Setting $S_{1}$ to be
$\\{\gamma_{1},\ldots,\gamma_{n-2C}\\}$ guaranteed by 4.1 such that
$|(\gamma+\mathcal{V}^{\perp})^{=1}|=1$ for all $\gamma\in S_{1}$ proves the
base case when $\ell=1$.

Now suppose we have some $S_{\ell-1}$ that satisfies the conditions in the
lemma. We will pick $S_{\ell}\subseteq S_{\ell-1}$ that satisfies condition
(2) for $t=\ell$, and argue that the number that do not satisfy the condition
is at most $C$. Indeed, suppose towards a contradiction that
$|S_{\ell-1}\setminus S_{\ell}|\geq C+1$. Let $J\subseteq S_{\ell-1}\setminus
S_{\ell}$ be any subset of size $C+1$ and $H:=\bigcup_{\gamma\in
J}(\gamma+\mathcal{V}^{\perp})^{=\ell}$. Since $S_{\ell}\subseteq\mathcal{W}$,
we can say by 2.4 that the sets $(\gamma+\mathcal{V}^{\perp})_{\gamma\in
S_{\ell}}$ are all mutually disjoint and therefore,

$|H|=\sum_{\gamma\in
J}|(\gamma+\mathcal{V}^{\perp})^{=\ell}|>2(C+1)\binom{2C+1}{\ell-1}=\ell\binom{2C+2}{\ell}.$

However, $H\subseteq(\spn(\\{\gamma:\gamma\in J\\}\cup V^{\perp}))^{=\ell}$.
Since, $\dim(\spn(\\{\gamma:\gamma\in J\\}\cup V^{\perp}))\leq|J|+C=2C+1$, by
4.13 it must be that
$|H|\leq\binom{2C+2}{\leq\ell}\leq\ell\binom{2C+2}{\ell}$, where the
inequality holds for all $\ell\leq(2C+2)/2=C+1$. This is a contradiction, and
we conclude that $|S_{\ell-1}\setminus S_{\ell}|\leq C$. ∎