# Fourier growth of structured $\mathbb{F}_{2}$-polynomials
and applications

Jarosław Błasiok
Columbia University
<EMAIL_ADDRESS>Peter Ivanov
Northeastern University
<EMAIL_ADDRESS>Yaonan Jin
Columbia University
<EMAIL_ADDRESS>Chin Ho Lee
Columbia University
<EMAIL_ADDRESS>Rocco A. Servedio
Columbia University
<EMAIL_ADDRESS>Emanuele Viola
Northeastern University
<EMAIL_ADDRESS>
###### Abstract

We analyze the _Fourier growth_ , i.e. the $L_{1}$ Fourier weight at level $k$
(denoted $L_{1,k}$), of various well-studied classes of “structured”
$\mathbbm{F}_{2}$-polynomials. This study is motivated by applications in
pseudorandomness, in particular recent results and conjectures due to [CHHL19,
CHLT19, CGL+20] which show that upper bounds on Fourier growth (even at level
$k=2$) give unconditional pseudorandom generators.

Our main structural results on Fourier growth are as follows:

  * •

We show that any symmetric degree-$d$ $\mathbbm{F}_{2}$-polynomial $p$ has
$L_{1,k}(p)\leq\mathop{\bf Pr\/}[p=1]\cdot O(d)^{k}$, and this is tight for
any constant $k$. This quadratically strengthens an earlier bound that was
implicit in [RSV13].

  * •

We show that any read-$\Delta$ degree-$d$ $\mathbbm{F}_{2}$-polynomial $p$ has
$L_{1,k}(p)\leq\mathop{\bf Pr\/}[p=1]\cdot(k\Delta d)^{O(k)}$.

  * •

We establish a composition theorem which gives $L_{1,k}$ bounds on disjoint
compositions of functions that are closed under restrictions and admit
$L_{1,k}$ bounds.

Finally, we apply the above structural results to obtain new unconditional
pseudorandom generators and new correlation bounds for various classes of
$\mathbbm{F}_{2}$-polynomials.

##  1 Introduction

###  1.1 Background: $L_{1}$ Fourier norms and Fourier growth

Over the past several decades, Fourier analysis of Boolean functions has
emerged as a fundamental tool of great utility across many different areas
within theoretical computer science and mathematics. Areas of application
include (but are not limited to) combinatorics, the theory of random graphs
and statistical physics, social choice theory, Gaussian geometry and the study
of metric spaces, cryptography, learning theory, property testing, and many
branches of computational complexity such as hardness of approximation,
circuit complexity, and pseudorandomness. The excellent book of O’Donnell
[O’D14] provides a broad introduction. In this paper we follow the notation of
[O’D14], and for a Boolean-valued function $f$ on $n$ Boolean variables and
$S\subseteq[n]$, we write $\widehat{f}(S)$ to denote the Fourier coefficient
of $f$ on $S$.

Given the wide range of different contexts within which the Fourier analysis
of Boolean functions has been pursued, it is not surprising that many
different quantitative parameters of Boolean functions have been analyzed in
the literature. In this work we are chiefly interested in the _$L_{1}$ Fourier
norm at level $k$_:

######  Definition 1 ($L_{1}$ Fourier norm at level $k$).

The _$L_{1}$ Fourier norm of a function $f\colon\\{-1,1\\}^{n}\to\\{0,1\\}$ at
level $k$_ is the quantity

$\displaystyle L_{1,k}(f):=\sum_{S\subseteq[n]:\lvert
S\rvert=k}\lvert\widehat{f}(S)\rvert.$

For a function class $\mathcal{F}$, we write $L_{1,k}(\mathcal{F})$ to denote
$\max_{f\in\mathcal{F}}L_{1,k}(f)$.

As we explain below, strong motivation for studying the $L_{1}$ Fourier norm
at level $k$ (even for specific small values of $k$ such as $k=2$) is given by
exciting recent results in unconditional _pseudorandomness_. More generally,
the notion of _Fourier growth_ is a convenient way of capturing the $L_{1}$
Fourier norm at level $k$ for every $k$:

######  Definition 2 (Fourier growth).

A function class $\mathcal{F}\subseteq\\{f\colon\\{-1,1\\}^{n}\to\\{0,1\\}\\}$
has _Fourier growth $L_{1}(a,b)$_ if there exist constants $a$ and $b$ such
that $L_{1,k}(\mathcal{F})\leq a\cdot b^{k}$ for every $k$.

The notion of Fourier growth was explicitly introduced by Reingold, Steinke,
and Vadhan in [RSV13] for the purpose of constructing pseudorandom generators
for space-bounded computation (though we note that the Fourier growth of DNF
formulas was already analyzed in [Man95], motivated by applications in
learning theory). In recent years there has been a surge of research interest
in understanding the Fourier growth of different types of functions [Tal17,
GSTW16, CHRT18, Lee19, GRZ20, Tal20, SSW20, GRT21]. One strand of motivation
for this study has come from the study of quantum computing; in particular,
bounds on the Fourier growth of $\mathsf{AC}^{0}$ [Tal17] were used in the
breakthrough result of Raz and Tal [RT19] which gave an oracle separation
between the classes $\mathsf{BQP}$ and $\mathsf{PH}$. More recently, in order
to achieve an optimal separation between quantum and randomized query
complexity, several researchers [Tal20, BS21, SSW20] have studied the Fourier
growth of decision trees, with the recent work of [SSW20] obtaining optimal
bounds. Analyzing the Fourier growth of other classes of functions has also
led to separations between quantum and classical computation in other settings
[GRT21, GRZ20, GTW21].

Our chief interest in the current paper arises from a different line of work
which has established powerful applications of Fourier growth bounds in
pseudorandomness. We describe the relevant background, which motivates a new
conjecture that we propose on Fourier growth, in the next subsection.

###  1.2 Motivation for this work: Fourier growth, pseudorandomness,
$\mathbbm{F}_{2}$-polynomials, and the [CHLT19] conjecture

##### Pseudorandom generators from Fourier growth bounds.

Constructing explicit, unconditional pseudorandom generators (PRGs) for
various classes of Boolean functions is an important goal in complexity
theory. In the recent work [CHHL19], Chattopadhyay, Hatami, Hosseini, and
Lovett introduced a novel framework for the design of such PRGs. Their
approach provides an explicit pseudorandom generator for any class of
functions that is closed under restrictions and has bounded Fourier growth:

######  Theorem 3 (PRGs from Fourier growth: Theorem 23 of [CHHL19]).

Let ${\cal F}$ be a family of $n$-variable Boolean functions that is closed
under restrictions and has Fourier growth $L_{1}(a,b)$. Then there is an
explicit pseudorandom generator that $\epsilon$-fools ${\cal F}$ with seed
length $O(b^{2}\log(n/\epsilon)(\log\log n+\log(a/\epsilon))).$

Building on Theorem 3, in [CHLT19] Chattopadhyay, Hatami, Lovett, and Tal
showed that in fact it suffices to have a bound just on $L_{1,2}({\cal F})$ in
order to obtain an efficient PRG for ${\cal F}$:

######  Theorem 4 (PRGs from $L_{1}$ Fourier norm bounds at level $k=2$:
Theorem 2.1 of [CHLT19]).

Let ${\cal F}$ be a family of $n$-variable Boolean functions that is closed
under restrictions and has $L_{1,2}({\cal F})\leq t$. Then there is an
explicit pseudorandom generator that $\epsilon$-fools ${\cal F}$ with seed
length $O((t/\epsilon)^{2+o(1)}\cdot\textnormal{polylog}(n)).$

Observe that while Theorem 4 requires a weaker structural result than Theorem
3 (a bound only on $L_{1,2}({\cal F})$ as opposed to $L_{1,k}({\cal F})$ for
all $k\geq 1$), the resulting pseudorandom generator is quantitatively weaker
since it has seed length polynomial rather than logarithmic in the error
parameter $1/\epsilon$. Even more recently, in [CGL+20] Chattopadhyay,
Gaitonde, Lee, Lovett, and Shetty further developed this framework by
interpolating between the two results described above. They showed that a
bound on $L_{1,k}$111In fact, they showed that a bound on the weaker quantity
$M_{1,k}(f):=\max_{x\in\\{-1,1\\}^{n}}\lvert\sum_{\lvert
S\rvert=k}\widehat{f}(S)x^{S}\rvert$ suffices. for any $k\geq 3$ suffices to
give a PRG, with a seed length whose $\epsilon$-dependence scales with $k$:

######  Theorem 5 (PRGs from $L_{1}$ Fourier norm bounds up to level $k$ for
any $k$: Theorem 4.3 of [CGL+20]).

Let ${\cal F}$ be a family of $n$-variable Boolean functions that is closed
under restrictions and has $L_{1,k}(\mathcal{F})\leq b^{k}$ for some $k\geq
3.$ Then there exists a pseudorandom generator that $\epsilon$-fools
$\mathcal{F}$ with seed length $O\left(\frac{b^{2+\frac{4}{k-2}}\cdot
k\cdot\textnormal{polylog}(\frac{n}{\epsilon})}{\epsilon^{\frac{2}{k-2}}}\right).$

#####  $\mathbbm{F}_{2}$-polynomials and the [CHLT19] conjecture.

The works [CHHL19] and [CHLT19] highlighted the challenge of proving $L_{1,k}$
bounds for the class of _bounded-degree $\mathbbm{F}_{2}$-polynomials_ as
being of special interest. Let

$\mathsf{Poly}_{n,d}:=\text{~{}the class of all $n$-variate
$\mathbbm{F}_{2}$-polynomials of degree $d$.}$

It follows from Theorem 4 that even proving

$L_{1,2}(\mathsf{Poly}_{n,\textnormal{polylog}(n)})\leq n^{0.49}$ (1)

would give nontrivial PRGs for $\mathbbm{F}_{2}$-polynomials of
$\textnormal{polylog}(n)$ degree, improving on [BV10, Lov09, Vio09b]. By the
classic connection (due to Razborov [Raz87]) between such polynomials and the
class $\mathsf{AC}^{0}[\oplus]$ of constant-depth circuits with parity gates,
this would also give nontrivial PRGs, of seed length $n^{1-c}$, for
$\mathsf{AC}^{0}[\oplus]$. This would be a breakthrough improvement on
existing results, which are poor either in terms of seed length [FSUV13] or in
terms of explicitness [CLW20].

The authors of [CHLT19] in fact conjectured the following bound, which is much
stronger than Equation 1:

######  Conjecture 6 ([CHLT19]).

For all $d\geq 1$, it holds that $L_{1,2}(\mathsf{Poly}_{n,d})=O(d^{2})$.

##### Extending the [CHLT19] conjecture.

Given 6, and in light of Theorem 5, it is natural to speculate that an even
stronger result than 6 might hold. We consider the following natural
generalization of the [CHLT19] conjecture, extending it from
$L_{1,2}(\mathsf{Poly}_{n,d})$ to $L_{1,k}(\mathsf{Poly}_{n,d})$:

######  Conjecture 7.

For all $d,k\geq 1$, it holds that $L_{1,k}(\mathsf{Poly}_{n,d})=O(d)^{k}$.

We note that if $p$ is the $\mathsf{AND}$ function on $d$ bits, then an easy
computation shows that $L_{1,k}(p)=\mathop{\bf Pr\/}[p=1]\cdot{d\choose k}$.
Moreover, in Appendix A we provide a reduction showing that this implies that
the upper bound $O(d)^{k}$ in 7 is best possible for any constant $k$.

For positive results, the work [CHLT19] proved that
$L_{1,1}(\mathsf{Poly}_{n,d})\leq 4d$, and already in [CHHL19] it was shown
that $L_{1,k}(\mathsf{Poly}_{n,d})\leq(2^{3d}\cdot k)^{k},$ but to the best of
our knowledge no other results towards 6 or 7 are known.

Given the apparent difficulty of resolving 6 and 7 in the general forms stated
above, it is natural to study $L_{1,2}$ and $L_{1,k}$ bounds for specific
subclasses of degree-$d$ $\mathbbm{F}_{2}$-polynomials. This study is the
subject of our main structural results, which we describe in the next
subsection.

###  1.3 Our results: Fourier bounds for structured
$\mathbbm{F}_{2}$-polynomials

Our main results show that $L_{1,2}$ and $L_{1,k}$ bounds of the flavor of 6
and 7 indeed hold for several well-studied classes of
$\mathbbm{F}_{2}$-polynomials, specifically _symmetric_
$\mathbbm{F}_{2}$-polynomials and _read- $\Delta$_
$\mathbbm{F}_{2}$-polynomials. We additionally prove a composition theorem
that allows us to combine such polynomials (or, more generally, any
polynomials that satisfy certain $L_{1,k}$ bounds) in a natural way and obtain
$L_{1,k}$ bounds on the resulting combined polynomials.

Before describing our results in detail, we pause to briefly explain why
(beyond the fact that they are natural mathematical objects) such “highly
structured” polynomials are attractive targets of study given known results.
It has been known for more than ten years [BHL12, Lemma 2] that for any degree
$d<(1-\epsilon)n$, a _random_ $\mathbbm{F}_{2}$-polynomial of degree $d$
(constructed by independently including each monomial of degree at most $d$
with probability $1/2$) is extremely unlikely to have bias larger than
$\exp(-n/d)$. It follows that as long as $d$ is not too large, a random
degree-$d$ polynomial $p$ is overwhelmingly likely to have
$L_{1,k}(p)=o_{n}(1)$, which is much smaller than $d^{k}$. (To verify this,
consider the polynomials $p_{S}$ obtained by XORing $p$ with the parity
function $\sum_{i\in S}x_{i}$. Note that the bias of $p_{S}$ is the Fourier
coefficient of $(-1)^{p}$ on $S$. Now apply [BHL12, Lemma 2] to each
polynomial $p_{S}$, and sum the terms.)

Since the conjectures hold true for random polynomials, it is natural to
investigate highly structured polynomials.

####  1.3.1 Symmetric $\mathbbm{F}_{2}$-polynomials

A _symmetric_ $\mathbbm{F}_{2}$-polynomial over $x_{1},\dots,x_{n}$ is one
whose output depends only on the Hamming weight of its input $x$. Such a
polynomial of degree $d$ can be written in the form

$p(x):=\sum_{k=0}^{d}c_{k}\sum_{\lvert S\rvert=k,S\subseteq[n]}\prod_{i\in
S}x_{i},$

where $c_{0},\ldots,c_{d}\in\\{0,1\\}$. While symmetric polynomials may seem
like simple objects, their study can sometimes lead to unexpected discoveries;
for example, a symmetric, low-degree $\mathbbm{F}_{2}$-polynomial provided a
counterexample to the “Inverse conjecture for the Gowers norm” [LMS11, GT09].

We prove the following upper and lower bounds on the $L_{1}$ Fourier norm at
level $k$ for any symmetric polynomial:

######  Theorem 8.

Let $p(x_{1},\dots,x_{n})$ be a symmetric $\mathbbm{F}_{2}$-polynomial of
degree $d$. Then $L_{1,k}(p)\leq\mathop{\bf Pr\/}[p=1]\cdot O(d)^{k}$ for
every $k$.

######  Theorem 9.

For every $k$, there is a symmetric $\mathbbm{F}_{2}$-polynomial
$p(x_{1},\ldots,x_{n})$ of degree $d=\Theta(\sqrt{kn})$ such that
$L_{1,k}(p)\geq(e^{-k}/2)\cdot\binom{n}{k}^{1/2}=\Omega_{k}(1)\cdot d^{k}$.

Theorem 8 verifies the [CHLT19] conjecture (6), and even the generalized
version 7, for the class of symmetric polynomials. Theorem 9 complements it by
showing that the upper bounds in Theorem 8 are tight for $k=O(1)$ when
$d=\Theta(\sqrt{n})$.

Theorem 8 also provides a quadratic sharpening of an earlier bound that was
implicit in [RSV13] (as well as providing the “correct” dependence on
$\mathop{\bf Pr\/}[p=1]$). In [RSV13] Reingold, Steinke and Vadhan showed that
any function $f$ computed by an oblivious, read-once, regular branching
program of width $w$ has $L_{1,k}(f)\leq(2w^{2})^{k}$. It follows directly
from a result of [BGL06] (Lemma 17 below) that any symmetric
$\mathbbm{F}_{2}$-polynomial $p$ of degree $d$ can be computed by an
oblivious, read-once, regular branching program of width at most $2d$, and
hence the [RSV13] result implies that $L_{1,k}(p)\leq 8^{k}d^{2k}.$

####  1.3.2 Read-$\Delta$ $\mathbbm{F}_{2}$-polynomials

For $\Delta\geq 1$, a _read- $\Delta$_ $\mathbbm{F}_{2}$-polynomial is one in
which each input variable appears in at most $\Delta$ monomials. The case
$\Delta=1$ corresponds to the class of _read-once polynomials_ , which are
simply sums of monomials over disjoint sets of variables; for example, the
polynomial $x_{1}x_{2}+x_{3}x_{4}$ is read-once whereas
$x_{1}x_{2}+x_{1}x_{4}$ is read-twice. Read-once polynomials have been studied
from the perspective of pseudorandomness [LV20, MRT19, Lee19, DHH20] as they
capture several difficulties in improving Nisan’s generators [Nis92] for
width-$4$ read-once branching programs.

We show that the $L_{1,k}$ Fourier norm of read-$\Delta$ polynomials is
polynomial in $d$ and $\Delta$:

######  Theorem 10.

Let $p(x_{1},\ldots,x_{n})$ be a read-$\Delta$ polynomial of degree $d$. Then
$L_{1,k}(p)\leq\mathop{\bf Pr\/}[p=1]\cdot O(k)^{k}\cdot(d\Delta)^{8k}$.

The work [Lee19] showed that read-once polynomials satisfy an $L_{1,k}$ bound
of $O(d)^{k}$ and this is tight for every $k$, but we are not aware of
previous bounds on even the $L_{1}$ Fourier norm at level $k=2$ for
read-$\Delta$ polynomials, even for $\Delta=2$.

As any monomial with degree $\Omega(\log n)$ vanishes under a random
restriction with high probability, we have the following corollary which
applies to polynomials of any degree.

######  Corollary 11.

Let $p(x_{1},\ldots,x_{n})$ be a read-$\Delta$ polynomial. Then
$L_{1,k}(p)\leq O(k)^{9k}\cdot(\Delta\log n)^{8k}$.

####  1.3.3 A composition theorem

The upper bounds of Theorem 8 and Theorem 10 both include a factor of
$\mathop{\bf Pr\/}[p=1]$. (We observe that negating $p$, i.e. adding 1 to it,
does not change its $L_{1,2}$ or $L_{1,k}$ and keeps $p$ symmetric
(respectively, read-$\Delta$) if it was originally symmetric (respectively,
read-$\Delta$), and hence in the context of those theorems we can assume that
this $\mathop{\bf Pr\/}[p=1]$ factor is at most $1/2.$) Level-$k$ bounds that
include this factor have appeared in earlier works for other classes of
functions [OS07, BTW15, CHRT18, Tal20, GTW21], and have been used to obtain
high-level bounds for other classes of functions [CHRT18, Tal20, GTW21] and to
extend level-$k$ bounds to more general classes of functions [Lee19]. Having
these $\mathop{\bf Pr\/}[p=1]$ factors in Theorem 8 and Theorem 10 is
important for us in the context of our composition theorem, which we now
describe. We begin by defining the notion of a _disjoint composition_ of
functions:

######  Definition 12.

Let $\mathcal{F}$ be a class of functions from $\\{-1,1\\}^{m}$ to
$\\{-1,1\\}$ and let $\mathcal{G}$ be a class of functions from
$\\{-1,1\\}^{\ell}$ to $\\{-1,1\\}$. Define the class
$\mathcal{H}=\mathcal{F}\circ\mathcal{G}$ of _disjoint compositions of
$\mathcal{F}$ and $\mathcal{G}$_ to be the class of all functions from
$\\{-1,1\\}^{m\ell}$ to $\\{-1,1\\}$ of the form

$h(x^{1},\ldots,x^{m})=f(g_{1}(x^{1}),\ldots,g_{m}(x^{m})),$

where $g_{1},\ldots,g_{m}\in\mathcal{G}$ are defined on $m$ disjoint sets of
variables and $f\in\mathcal{F}$.

As an example of this definition, the class of _block-symmetric_ polynomials
(i.e. polynomials whose variables are divided into blocks and are symmetric
within each block but not overall) are a special case of disjoint compositions
where ${\cal G}$ is taken to be the class of symmetric polynomials. We remark
that block-symmetric polynomials are known to correlate better with parities
than symmetric polynomials in certain settings [GKV17].

We prove a composition theorem for upper-bounding the $L_{1}$ Fourier norm at
level $k$ of the disjoint composition of any classes of functions that are
closed under restriction and admit a $L_{1,k}$ bound of the form $\mathop{\bf
Pr\/}[f=1]\cdot a\cdot b^{k}$:

######  Theorem 13.

Let $g_{1},\ldots,g_{m}\in\mathcal{G}$ and let $f\in\mathcal{F}$, where
$\mathcal{F}$ is closed under restrictions. Suppose that for every $1\leq
k\leq K$, we have

  1. 1.

$L_{1,k}(f)\leq\mathop{\bf Pr\/}[f=1]\cdot a_{\mathsf{out}}\cdot
b_{\mathsf{out}}^{k}$ for every $f\in\mathcal{F}$, and

  2. 2.

$L_{1,k}(g)\leq\mathop{\bf Pr\/}[g=1]\cdot a_{\mathsf{in}}\cdot
b_{\mathsf{in}}^{k}$ for every $g\in\mathcal{G}$.

Then for every $\pm 1$-valued function
$h\in\mathcal{H}=\mathcal{F}\circ\mathcal{G}$, we have that

$L_{1,K}(h)\leq\mathop{\bf Pr\/}[h=1]\cdot
a_{\mathsf{out}}\cdot(a_{\mathsf{in}}b_{\mathsf{in}}b_{\mathsf{out}})^{K}.$

See Theorem 31 for a slightly sharper bound. We remark that Theorem 13 does
not assume any $\mathbbm{F}_{2}$-polynomial structure for the functions in
${\cal F}$ or ${\cal G}$ and thus may be of broader utility.

###  1.4 Applications of our results

Our structural results imply new pseudorandom generators and correlation
bounds.

####  1.4.1 Pseudorandom generators

Combining our Fourier bounds with the polarizing framework, we obtain new PRGs
for read-few polynomials. The following theorem follows from applying Theorem
5 with some $k=\Theta(\log n)$ and the $L_{1,k}$ bound in Corollary 11.

######  Theorem 14.

There is an explicit pseudorandom generator that $\epsilon$-fools
read-$\Delta$ $\mathbbm{F}_{2}$-polynomials with seed length
$\textnormal{poly}(\Delta,\log n,\log(1/\epsilon))$.

For constant $\epsilon$, this improves on a PRG by Servedio and Tan [ST19a],
which has a seed length of $2^{O(\sqrt{\log(\Delta n)})}$. (Note that
read-$\Delta$ polynomials are also $(\Delta n)$-sparse.) We are not aware of
any previous PRG for read-2 polynomials with $\textnormal{polylog}(n)$ seed
length.

Note that the $\mathsf{OR}$ function has $L_{1}$ Fourier norm $O(1)$. By
expressing a DNF in the Fourier expansion of $\mathsf{OR}$ in its terms, it is
not hard to see that the same PRG also fools the class of read-$\Delta$ DNFs
(and read-$\Delta$ CNFs similarly) [ST19b].

####  1.4.2 Correlation bounds

Exhibiting explicit Boolean functions that do not _correlate_ with low-degree
polynomials is a fundamental challenge in complexity. Perhaps surprisingly,
this challenge stands in the way of progress on a striking variety of
frontiers in complexity, including circuits, rigidity, and multiparty
communication complexity. For a survey of correlation bounds and discussions
of these connections we refer the reader to [Vio09a, Vio17, Vio21].

For polynomials of degree larger than $\log_{2}n$, the state-of-the-art
remains the lower bound proved by Razborov and Smolensky in the 1980s’ [Raz87,
Smo87], showing that for any degree-$d$ polynomial $p$ and an explicit
function $h$ (in fact, majority) we have:

$\mathop{\bf Pr\/}[p(x)=h(x)]\leq 1/2+O(d/\sqrt{n}).$

Viola [Vio20] recently showed that upper bounds on $L_{1,k}(\mathcal{F})$
imply correlation bounds between $\mathcal{F}$ and an explicit function
$h_{k}$ that is related to majority and is defined as

$h_{k}(x):=\textnormal{sgn}\Biggl{(}\sum_{\lvert S\rvert=k}x^{S}\Biggr{)}.$

In particular, proving 6 or related conjectures implies new correlation bounds
beating Razborov–Smolensky. The formal statement of the connection is given by
the following theorem.

######  Theorem 15 (Theorem 1 in [Vio20]).

For every $k\in[n]$ and
$\mathcal{F}\subseteq\\{f\colon\\{0,1\\}^{n}\to\\{-1,1\\}\\}$, there is a
distribution $D_{k}$ on $\\{0,1\\}^{n}$ such that for any $f\in\mathcal{F}$,

$\mathop{\bf Pr\/}_{x\sim
D_{k}}\left[f(x)=h_{k}(x)\right]\leq\frac{1}{2}+\frac{e^{k}}{2\sqrt{\binom{n}{k}}}L_{1,k}(\mathcal{F}).$

For example, if $k=2$ and we assume that the answer to 6 is positive, then the
right-hand side above becomes $1/2+O(d^{2}/n)$, which is a quadratic
improvement over the bound by Razborov and Smolensky.

Therefore, Theorems 8 and 10 imply correlation bounds between these
polynomials and an explicit function that are better than $O(d/\sqrt{n})$
given in [Raz87, Smo87]. We note that via a connection in [Vio09b], existing
PRGs for these polynomials already imply strong correlation bounds between
these polynomials and the class of $\mathsf{NP}$. Our results apply to more
general classes via the composition theorem, where it is not clear if previous
techniques applied. For a concrete example, consider the composition of a
degree-$(n^{\alpha})$ symmetric polynomial with degree-$(n^{\alpha})$
read-$(n^{\alpha})$ polynomials. Theorem 13 shows that such polynomial has
$L_{1,2}\leq n^{O(\alpha)}$. For a sufficiently small $\alpha=\Omega(1)$, we
again obtain correlation bounds improving on Razborov–Smolensky.

###  1.5 Related work

We close this introduction by discussing a recent work of Girish, Tal and Wu
[GTW21] on parity decision trees that is related to our results.

Parity decision trees are a generalization of decision trees in which each
node queries a parity of some input bits rather than a single input bit. The
class of depth-$d$ parity decision trees is a subclass of $\mathbbm{F}_{2}$
degree-$d$ polynomials, as such a parity decision tree can be expressed as a
sum of products of sums over $\mathbbm{F}_{2}$, where each product corresponds
to a path in the tree (and hence gives rise to $\mathbbm{F}_{2}$-monomials of
degree at most $d$). The Fourier spectrum of parity decision trees was first
studied in [BTW15], which obtained a level-$1$ bound of $O(\sqrt{d})$. This
bound was recently extended to higher levels in [GTW21], showing that any
depth-$d$ parity decision tree $T$ over $n$ variables has $L_{1,k}(T)\leq
d^{k/2}\cdot O(k\log n)^{k}$.

##  2 Our techniques

We now briefly explain the approaches used to prove our results. We note that
each of these results is obtained using very different ingredients, and hence
the results can be read independently of each other.

###  2.1 Symmetric polynomials (Theorems 8 and 9, Section 4)

The starting point of our proof is a result from [BGL06], which says that
degree-$d$ symmetric $\mathbbm{F}_{2}$-polynomials only depend on the Hamming
weight of their input modulo $m$ for some $m$ (a power of two) which is
$\Theta(d)$, and the converse is also true. (See Lemma 17 for the exact
statement.) We now explain how to prove our upper and lower bounds given this.

For the upper bound (Theorem 8), since $p(x)$ takes the same value for all
strings $x$ with the same weights $\ell\bmod m$, to analyze $L_{1,k}(p)$ it
suffices to analyze $\mathop{\bf E\/}[(-1)^{x_{1}+\cdots+x_{k}}]$ conditioned
on $x$ having Hamming weight exactly $\ell\bmod m$.

We bound this conditional expectation by considering separately two cases
depending on whether or not $k\leq n/m^{2}$. For the case that $k\leq
n/m^{2}$, we use a (slight sharpening of a) result from [BHLV19], which gives
a bound of $m^{-k}e^{-\Omega(n/m^{2})}$. In the other case, that $k\geq
n/m^{2}$, in Lemma 19 we prove a bound of $O(km/n)^{k}$. This is established
via a careful argument that gives a new bound on the Kravchuk polynomial in
certain ranges (see Claim 22), extending and sharpening similar bounds that
were recently established in [CPT20] (the bounds of [CPT20] would not suffice
for our purposes).

In each of the above two cases, summing over all the $\binom{n}{k}$
coefficients gives the desired bound of $O(m)^{k}=O(d)^{k}$.

For the lower bound (Theorem 9), we first consider the symmetric function
$h_{k}(x):=\textnormal{sgn}(\sum_{\lvert S\rvert=k}(-1)^{\sum_{i\in
S}x_{i}})$. (Note that $h_{1}$ is the majority function.) As $h_{k}$ has
degree $k$, it follows from a consequence of the hypercontractive inequality
that $L_{1,k}(h_{k})\geq e^{-k}\binom{n}{k}^{1/2}$. We define our polynomial
$p$ so that on inputs $x$ whose Hamming weight $\lvert x\rvert$ is within
$m=\Theta(\sqrt{kn})$ from $n/2$, it agrees with $h_{k}$, and on other inputs
its value is defined such that $p$ only depends on $\lvert x\rvert\bmod 2m$.
By the converse of [BGL06], $p$ can be computed by a symmetric polynomial of
degree less than $2m$. Our lower bound then follows from
$L_{1,k}(f)\leq\binom{n}{k}^{1/2}$ for any Boolean function $f$, and that by
our choice of $m$, the two functions $p$ and $h_{k}$ disagree on
$e^{-\Omega(k)}$ fraction of the inputs.

###  2.2 Read-$\Delta$ polynomials (Theorem 10, Section 5)

Writing $f:=(-1)^{p}$ for an $\mathbbm{F}_{2}$-polynomial $p$, we observe that
the coefficient $\widehat{f}(S)$ is simply the bias of
$p_{S}(x):=p(x)+\sum_{i\in S}x_{i}$. Our high-level approach is to decompose
the read-few polynomial $p_{S}$ into many disjoint components, then show that
each component has small bias. Since the components are disjoint, the product
of these biases gives an upper bound on the bias of $p_{S}$.

In more detail, we first partition the variables according to the minimum
degree $t_{i}$ of the monomials containing each variable $x_{i}$. Then we
start decomposing $p_{S}$ by collecting all the monomials in $p$ containing
$x_{i}$ to form the polynomial $p_{i}$. We observe that the larger $t_{i}$ is,
the more likely $p_{i}$ is to vanish on a random input, and therefore the
closer $p_{i}+x_{i}$ is to being unbiased. For most $S$, we can pick many such
$p_{i}$’s ($i\in S$) from $p$ so that they are disjoint. For the remaining
polynomial $r$, because $\Delta$ and $d$ are small, we can further decompose
$r$ into many disjoint polynomials $r_{i}$. Finally, our upper bound on
$|\widehat{f}(S)|$ will be the magnitude of the product of the biases of the
$p_{i}$’s and $r_{i}$’s. We note that our decomposition of $p$ uses the
structure of $S$; and so the upper bound on $\widehat{f}(S)$ depends on $S$
(see Lemma 27). Summing over each $\lvert\widehat{f}(S)\rvert$ gives our upper
bound.

###  2.3 Composition theorem (Theorem 13, Section 6)

As a warmup, let us first consider directly computing a degree-1 Fourier
coefficient $\widehat{h}(\\{(i,j)\\})$ of the composition. Since the inner
functions $g_{i}$ depend on disjoint variables, by writing the outer function
$f$ in its Fourier expansion, it is not hard to see that

$\widehat{h}(\\{(i,j)\\})=\sum_{S\ni i}\widehat{f}(S)\prod_{\ell\in
S\setminus\\{i\\}}\mathop{\bf E\/}[g_{\ell}]\cdot\widehat{g}_{i}(\\{j\\}).$

When the $g_{i}$’s are balanced, i.e. $\mathop{\bf E\/}[g_{i}]=0$, we have
$\widehat{f}(\\{(i,j)\\})=\widehat{f}(\\{i\\})\widehat{g}_{i}(\\{j\\})$, and
it follows that $L_{1,1}(h)\leq L_{1,1}(\mathcal{F})L_{1,1}(\mathcal{G})$. To
handle the unbalanced case, we apply an idea from [CHHL19] that lets us relate
$\sum_{S\ni i}\widehat{f}(S)\prod_{\ell\in S\setminus\\{i\\}}\mathop{\bf
E\/}[g_{\ell}]$ to the average of $\widehat{f_{R}}(\\{i\\})$, for some
suitably chosen random restriction $R$ on $f$ (see Claim 33). As $\mathcal{F}$
is closed under restrictions, we can apply the $L_{1,1}(\mathcal{F})$ bound on
$f_{R}$, which in turns gives a bound on $\sum_{S\ni
i}\widehat{f}(S)\prod_{\ell\in S\setminus\\{i\\}}\mathop{\bf E\/}[g_{\ell}]$
in terms of $L_{1,1}(\mathcal{F})$ and $\mathop{\bf E\/}[g_{i}]$.

Bounding $L_{1,k}(h)$ for $k\geq 2$ is more complicated, as each
$\widehat{h}(S)$ involves $\widehat{f}(J)$ and $\widehat{g}_{i}(T)$’s, where
the sets $J$ and $T$ have different sizes. We provide more details in Section
6.

##  3 Preliminaries

Notation. For a string $x\in\\{0,1\\}^{n}$ we write $\lvert x\rvert$ to denote
its Hamming weight $\sum_{i=1}^{n}x_{i}$. We use $\mathcal{X}_{w}$ to denote
$\\{x:\lvert x\rvert=w\\}$, the set of $n$-bit strings with Hamming weight
$w$, and $\mathcal{X}_{\ell\bmod m}=\bigcup_{w:w\equiv\ell\bmod
m}\mathcal{X}_{w}=\\{x:\lvert x\rvert\equiv\ell\bmod m\\}$.

We recall that for an $n$-variable Boolean function $f$, the _level- $k$
Fourier $L_{1}$ norm of $f$_ is

$L_{1,k}(f)=\sum_{S\subset[n]:\lvert S\rvert=k}\lvert\widehat{f}(S)\rvert.$

We note that a function $f$ and its negation have the same $L_{1,k}$ for
$k\geq 1$. Hence we can often assume that $\mathop{\bf Pr\/}[f=1]\leq 1/2$, or
replace the occurrence of $\mathop{\bf Pr\/}[f=1]$ in a bound by
$\min\\{\mathop{\bf Pr\/}[f=1],\mathop{\bf Pr\/}[f=0]\\}$ for a
$\\{0,1\\}$-valued function $f$ (or by $\min\\{\mathop{\bf
Pr\/}[f=1],\mathop{\bf Pr\/}[f=-1]\\}$ for a $\\{-1,1\\}$-valued function). If
$f$ is a $\\{-1,1\\}$-valued function then $\frac{1-\lvert\mathop{\bf
E\/}[f]\rvert}{2}$ is equal to $\min\\{\mathop{\bf Pr\/}[f=1],\mathop{\bf
Pr\/}[f=-1]\\}$, and we will often write $\frac{1-\lvert\mathop{\bf
E\/}[f]\rvert}{2}$ for convenience.

Unless otherwise indicated, we will use the letters $p,q,r$, etc. to denote
$\mathbbm{F}_{2}$-polynomials (with inputs in $\\{0,1\\}^{n}$ and outputs in
$\\{0,1\\}$) and the letters $f,g,h,$ etc. to denote general Boolean functions
(where the inputs may be $\\{0,1\\}^{n}$ or $\\{-1,1\\}^{n}$ and the outputs
may be $\\{0,1\\}$ or $\\{-1,1\\}$ depending on convenience). We note that
changing from $\\{0,1\\}$ outputs to $\\{-1,1\\}$ outputs only changes
$L_{1,k}$ by a factor of $2$.

We use standard multilinear monomial notation as follows: given a vector
$\beta=(\beta_{1},\dots,\beta_{n})$ and a subset $T\subseteq[n]$, we write
$\beta^{T}$ to denote $\prod_{j\in T}\beta_{j}$.

##  4 $L_{1,k}$ bounds for symmetric polynomials

The main result of this section is Theorem 16, which gives an upper bound on
$L_{1,k}(p)$ for any symmetric $\mathbbm{F}_{2}$-polynomial $p$ of degree $d$,
covering the entire range of parameters $1\leq k,d\leq n$:

######  Theorem 16 (Restatement of Theorem 8).

Let $p\colon\\{0,1\\}^{n}\to\\{0,1\\}$ be a symmetric
$\mathbbm{F}_{2}$-polynomial of degree $d$. For every $1\leq k,d\leq n$,

$L_{1,k}(p):=\sum_{\lvert S\rvert=k}\lvert\widehat{p}(S)\rvert\leq\mathop{\bf
Pr\/}[p(x)=1]\cdot O(d)^{k}.$

##### Proof idea.

As the polynomial $p$ is symmetric, its Fourier coefficient $\widehat{p}(S)$
only depends on $|S|$, the size of $S$. Hence to bound $L_{1,k}$ it suffices
to analyze the coefficient $\widehat{p}(\\{1,\ldots,k\\})=\mathop{\bf
E\/}_{x\sim\\{0,1\\}^{n}}[p(x)(-1)^{x_{1}+\cdots+x_{k}}]$.

Our proof uses a result from [BGL06] (Lemma 17 below), which says that
degree-$d$ symmetric $\mathbbm{F}_{2}$-polynomials only depend on the Hamming
weight of their input modulo $m$ for some $m=O(d)$. Given this, since $p(x)$
takes the same value for strings $x$ with the same weights $\ell\bmod m$, we
can in turn bound each $\mathop{\bf E\/}[(-1)^{x_{1}+\cdots+x_{k}}]$
conditioned on $x$ having Hamming weight exactly $\ell\bmod m$, i.e.
$x\in\mathcal{X}_{\ell\bmod m}$. We consider two cases depending on whether or
not $k\leq n/m^{2}$. If $k\leq n/m^{2}$, we can apply a (slight sharpening of
a) result from [BHLV19], which gives a bound of $m^{-k}e^{-\Omega(n/m^{2})}$.
If $k\geq n/m^{2}$, in Lemma 19 we prove a bound of $O(km/n)^{k}$. In each
case, summing over all the $\binom{n}{k}$ coefficients gives the desired bound
of $O(m)^{k}=O(d)^{k}$.

We now give some intuition for Lemma 19, which upper bounds the magnitude of
the ratio

$\displaystyle\mathop{\bf E\/}_{x\sim\mathcal{X}_{\ell\bmod
m}}[(-1)^{x_{1}+\cdots+x_{k}}]=\frac{\sum_{x\in\mathcal{X}_{\ell\bmod
m}}(-1)^{x_{1}+\cdots+x_{k}}}{\lvert\mathcal{X}_{\ell\bmod m}\rvert}$ (2)

by $O(km/n)^{k}$. Let us first consider $k=1$ and $m=\Theta(\sqrt{n})$. As
most strings $x$ have Hamming weight within
$[n/2-\Theta(\sqrt{n}),n/2+\Theta(\sqrt{n})]$, it is natural to think about
the weight $\lvert x\rvert$ in the form of $n/2+m\mathbbm{Z}+\ell^{\prime}$.
It is easy to see that the denominator is at least $\Omega(2^{n}/\sqrt{n})$,
so we focus on bounding the numerator. Consider the quantity
$\sum_{x\in\mathcal{X}_{n/2+s}}\mathop{\bf E\/}[(-1)^{x_{1}}]$ for some $s$.
As we are summing over all strings of the same Hamming weight, we can instead
consider $\sum_{x\in\mathcal{X}_{n/2+s}}\mathop{\bf
E\/}_{i\sim[n]}[(-1)^{x_{i}}]$ (see Equation 5). For any string of weight
$n/2+s$, it is easy to see that

$\displaystyle\mathop{\bf
E\/}_{i\sim[n]}[(-1)^{x_{i}}]=(1/2-s/n)-(1/2+s/n)=-2s/n.$ (3)

Therefore, in the $k=1$ case we get that

$\bigg{\lvert}\mathop{\bf E\/}_{x\sim\mathcal{X}_{\ell\bmod
m}}[(-1)^{x_{1}+\cdots+x_{k}}]\bigg{\rvert}\leq
2\sum_{c}\binom{n}{n/2+cm+\ell^{\prime}}\frac{\lvert
cm+\ell^{\prime}\rvert}{n}.$

Using the fact that $\binom{n}{n/2+cm+\ell^{\prime}}$ is exponentially
decreasing in $\lvert c\rvert$, in Claim 20 we show that this is at most
$O(2^{n}/n)$. So the ratio in 2 is at most $O(1/\sqrt{n})$, as desired, when
$k=1.$

However, already for $k=2$, a direct (but tedious) calculation shows that

$\displaystyle\mathop{\bf
E\/}_{i<j}[(-1)^{x_{i}+x_{j}}]=\frac{4s^{2}-2ns+n}{n(n-1)},$ (4)

which no longer decreases in $s$ like in 3. Nevertheless, we observe that this
is bounded by $O(1/n+(\lvert s\rvert/n)^{2})$, which is sufficient for
bounding the ratio by $O(1/n)$. Building on this, for any $k$ we obtain a
bound of $2^{O(k)}((k/n)^{k/2}+(\lvert s\rvert/n))^{k}$ in Claim 22, and by a
more careful calculation we are able to obtain the desired bound of
$O(km/n)^{k}$ on Equation 2.

###  4.1 Proof of Theorem 16

We now prove the theorem. We will use the following result from [BGL06], which
says that degree-$d$ symmetric $\mathbbm{F}_{2}$-polynomials only depend on
their input’s Hamming weight modulo $O(d)$.

######  Lemma 17 (Corollaries 2.5 and 2.7 in [BGL06], $p=2$).

Let $p\colon\\{0,1\\}^{n}\to\\{0,1\\}$ be any function and $m$ be a power of
two. If $p$ is a symmetric $\mathbbm{F}_{2}$-polynomial of degree $d$, where
$m/2\leq d<m$, then $p(x)$ only depends on $\lvert x\rvert\bmod m$.
Conversely, if $p(x)$ only depends on $\lvert x\rvert\bmod m$, then it can be
computed by a symmetric $\mathbbm{F}_{2}$-polynomial of degree less than $m$.

We will also use two bounds on the biases of parities under the uniform
distribution over $\mathcal{X}_{\ell\bmod m}$, one holds for $k\leq
n/(2d)^{2}\leq n/m^{2}$ (Claim 18) and the other for $k\geq n/(2d)^{2}\geq
n/(4m^{2})$ (Lemma 19). Claim 18 is essentially taken from [BHLV19]. However,
the statement in [BHLV19] has a slightly worse bound, so below we explain the
changes required to give the bound of Claim 18. The proof of Lemma 19 involves
bounding the magnitude of Kravchuk polynomials. As it is somewhat technical we
defer its proof to Section 4.2.

######  Claim 18 (Lemma 10 in [BHLV19]).

For every $1\leq k\leq n/m^{2}$ and every integer $\ell$,

$2^{-n}\Big{\lvert}\sum_{x\in\mathcal{X}_{\ell\bmod
m}}(-1)^{x_{1}+\cdots+x_{k}}\Big{\rvert}\leq m^{-(k+1)}e^{-\Omega(n/m^{2})},$

while for $k=0$,

$\Big{\lvert}2^{-n}\lvert\mathcal{X}_{\ell\bmod m}\rvert-1/m\Big{\rvert}\leq
m^{-1}e^{-\Omega(n/m^{2})}.$

######  Lemma 19.

For $k\geq n/(4m^{2})$, we have

$\binom{n}{k}\cdot\max_{\ell}\left\lvert\frac{\sum_{x\in\mathcal{X}_{\ell\bmod
m}}(-1)^{x_{1}+\cdots+x_{k}}}{\lvert\mathcal{X}_{\ell\bmod
m}\rvert}\right\rvert\leq O(m)^{k}.$

We now use Claim 18 and Lemma 19 to prove Theorem 16.

###### Proof of Theorem 16.

As $p$ is symmetric, all the level-$k$ coefficients are the same, so it
suffices to give a bound on $\widehat{p}(\\{1,2,\ldots,k\\})$. Let
$\tilde{p}\colon\\{0,\ldots,n\\}\to\\{0,1\\}$ be the function defined by
$\tilde{p}(\lvert x\rvert):=p(x_{1},\ldots,x_{n})$. By Lemma 17, we have
$\tilde{p}(\ell)=\tilde{p}(\ell\bmod m)$ for some $d<m\leq 2d$ where $m$ is a
power of $2$. Using the definition of $\widehat{p}(\\{1,\ldots,k\\})$, we have

$\displaystyle\lvert\widehat{p}(\\{1,\ldots,k\\})\rvert$
$\displaystyle=\left\lvert\mathop{\bf
E\/}_{x\sim\\{0,1\\}^{n}}\bigl{[}p(x)(-1)^{x_{1}+\cdots+x_{k}}\bigr{]}\right\rvert$
$\displaystyle=\left\lvert\sum_{\ell=0}^{m-1}\tilde{p}(\ell)\frac{\lvert\mathcal{X}_{\ell\bmod
m}\rvert}{2^{n}}\cdot\frac{\sum_{x\in\mathcal{X}_{\ell\bmod
m}}(-1)^{x_{1}+\cdots+x_{k}}}{\lvert\mathcal{X}_{\ell\bmod
m}\rvert}\right\rvert$ $\displaystyle\leq\mathop{\bf
E\/}[p]\cdot\max_{0\leq\ell\leq
m-1}\left\lvert\frac{\sum_{x\in\mathcal{X}_{\ell\bmod
m}}(-1)^{x_{1}+\cdots+x_{k}}}{\lvert\mathcal{X}_{\ell\bmod
m}\rvert}\right\rvert,$

where we use the shorthand $\mathop{\bf E\/}[p]=\mathop{\bf
E\/}_{x\sim\\{0,1\\}^{n}}[p(x)]$ in the last step.

When $k\leq n/(2d)^{2}\leq n/m^{2}$, by Claim 18 (using the first bound for
the numerator and the second $k=0$ bound for the denominator) we have

$\max_{0\leq\ell\leq m-1}\left\lvert\frac{\sum_{x\in\mathcal{X}_{\ell\bmod
m}}(-1)^{x_{1}+\cdots+x_{k}}}{\lvert\mathcal{X}_{\ell\bmod
m}\rvert}\right\rvert\leq\frac{m^{-(k+1)}e^{-\Omega(n/m^{2})}}{m^{-1}(1-e^{-\Omega(n/m^{2})})}\\\
\leq O(1)\cdot m^{-k}e^{-\Omega(n/m^{2})},$

where the last inequality holds because $1\leq k\leq n/m^{2}$ and hence the
$(1-e^{-\Omega(n/m^{2})})$ factor in the denominator of the left-hand side is
$\Omega(1)$. Hence, summing over all the $\binom{n}{k}$ level-$k$
coefficients, we get that

$L_{1,k}(p)\leq\mathop{\bf E\/}[p]\cdot\binom{n}{k}\cdot O(1)\cdot
m^{-k}e^{-\Omega(n/m^{2})}\leq\mathop{\bf E\/}[p]\cdot O(1)\cdot
m^{k}\left(\frac{ne}{km^{2}}\right)^{k}e^{-\Omega(n/m^{2})}\leq\mathop{\bf
E\/}[p]\cdot O(m)^{k},$

where the last inequality is because for constant $c$, the function
$(x/k)^{k}e^{-cx}$ is maximized when $x=k/c$, and is $O(1)^{k}$.

When $k\geq n/(2d)^{2}\geq n/(4m^{2})$, by Lemma 19 we have

$L_{1,k}(p)\leq\mathop{\bf E\/}[p]\cdot\binom{n}{k}\max_{0\leq\ell\leq
m-1}\left\lvert\frac{\sum_{x\in\mathcal{X}_{\ell\bmod
m}}(-1)^{x_{1}+\cdots+x_{k}}}{\lvert\mathcal{X}_{\ell\bmod
m}\rvert}\right\rvert\leq\mathop{\bf E\/}[p]\cdot O(m)^{k}.\qed$

It remains to prove Claim 18 and Lemma 19.

###### Proof of Claim 18.

The second inequality (i.e. when $k=0$) is explicitly shown in [BHLV19, Lemma
10]. For the first inequality (i.e. when $k\geq 1$), following the proof of
[BHLV19, Lemma 10] but without using the last inequality in the proof of their
Claim 11, we have

$\left\lvert\sum_{x\in\mathcal{X}_{\ell\bmod
m}}(-1)^{x_{1}+\cdots+x_{k}}\right\rvert\leq\frac{2^{n}}{m}\sum_{j=0}^{m-1}\Big{\lvert}\cos\frac{j\pi}{m}\Big{\rvert}^{n-k}\Big{\lvert}\sin\frac{j\pi}{m}\Big{\rvert}^{k}.$

For $0<\theta<\pi/2$, we have $\cos\theta\leq e^{-\theta^{2}/2}$ and
$\sin\theta\leq\theta$. So

$\displaystyle\sum_{j=0}^{m-1}\Big{\lvert}\cos\frac{j\pi}{m}\Big{\rvert}^{n-k}\Big{\lvert}\sin\frac{j\pi}{m}\Big{\rvert}^{k}$
$\displaystyle=2\sum_{0<j<m/2}\Bigl{(}\cos\frac{j\pi}{m}\Bigr{)}^{n-k}\Bigl{(}\sin\frac{j\pi}{m}\Bigr{)}^{k}$
$\displaystyle\leq
2\sum_{0<j<m/2}e^{-\frac{n-k}{2}\bigl{(}\frac{j\pi}{m}\bigr{)}^{2}}\Bigl{(}\frac{j\pi}{m}\Bigr{)}^{k}.$

We now observe that each term in the above summation is at most half of the
previous one. This is because for every $j\geq 1$ we have

$\displaystyle\frac{\exp\Bigl{(}-\frac{(n-k)(j+1)^{2}\pi^{2}}{2m^{2}}\Bigr{)}\Bigl{(}\frac{(j+1)\pi}{m}\Bigr{)}^{k}}{\exp\Bigl{(}-\frac{(n-k)j^{2}\pi^{2}}{2m^{2}}\Bigr{)}\Bigl{(}\frac{j\pi}{m}\Bigr{)}^{k}}$
$\displaystyle\leq\exp\Bigl{(}-\frac{\pi^{2}(n-k)}{m^{2}}j\Bigr{)}\cdot\Bigl{(}1+\frac{1}{j}\Bigr{)}^{k}$
$\displaystyle\leq\exp\Bigl{(}-\frac{\pi^{2}(n-k)}{m^{2}}\Bigr{)}\cdot 2^{k}$
$\displaystyle\leq\exp\Bigl{(}-\frac{3\pi^{2}}{4}k\Bigr{)}\cdot 2^{k}$
$\displaystyle\leq\exp\Bigl{(}-\frac{3\pi^{2}}{4}\Bigr{)}\cdot 2$
$\displaystyle\leq\frac{1}{2},$

where the third step holds because w.l.o.g. $m\geq 2$ and $1\leq k\leq
n/m^{2}\leq n/4$, and hence $(n-k)/m^{2}\geq 3k/4$. For these reasons, we can
deduce that

$\sum_{j=0}^{m-1}\Big{\lvert}\cos\frac{j\pi}{m}\Big{\rvert}^{n-k}\Big{\lvert}\sin\frac{j\pi}{m}\Big{\rvert}^{k}\leq
2e^{-\frac{\pi^{2}(n-k)}{2m^{2}}}\Bigl{(}\frac{\pi}{m}\Bigr{)}^{k}\sum_{1\leq
j<m/2}2^{1-j}\leq m^{-k}\exp\bigl{(}-\Omega(n/m^{2})\bigr{)}.\qed$

###  4.2 Proof of Lemma 19

In this section, we prove Lemma 19. Let
$\mathcal{K}(n,k,w):=\sum_{x\in\mathcal{X}_{w}}(-1)^{x_{1}+\cdots+x_{k}}$ be
the _Kravchuk polynomial_. We recall the “symmetry relation” for this
polynomial (see e.g. [Wik21]):

$\displaystyle\binom{n}{k}\mathcal{K}(n,k,w)=\sum_{y\in\mathcal{X}_{k}}\sum_{x\in\mathcal{X}_{w}}(-1)^{\langle
y,x\rangle}=\sum_{x\in\mathcal{X}_{w}}\sum_{y\in\mathcal{X}_{k}}(-1)^{\langle
x,y\rangle}=\binom{n}{w}\mathcal{K}(n,w,k).$ (5)

Using Equation 5, we have

$\displaystyle\binom{n}{k}\max_{0\leq\ell\leq
m-1}\left\lvert\frac{\sum_{x\in\mathcal{X}_{\ell\bmod
m}}(-1)^{x_{1}+\cdots+x_{k}}}{\lvert\mathcal{X}_{\ell\bmod
m}\rvert}\right\rvert$
$\displaystyle=\max_{\ell}\frac{\lvert\sum_{w\equiv\ell\bmod
m}\binom{n}{k}\mathcal{K}(n,k,w)\rvert}{\sum_{w\equiv\ell\bmod
m}\binom{n}{w}}$ $\displaystyle=\max_{\ell}\frac{\lvert\sum_{w\equiv\ell\bmod
m}\binom{n}{w}\mathcal{K}(n,w,k)\rvert}{\sum_{w\equiv\ell\bmod
m}\binom{n}{w}}$ $\displaystyle\leq\max_{\ell}\frac{\sum_{c}\binom{n}{\lfloor
n/2\rfloor+cm+\ell}\lvert\mathcal{K}(n,\lfloor
n/2\rfloor+cm+\ell,k)\rvert}{\sum_{c}\binom{n}{\lfloor n/2\rfloor+cm+\ell}}$
$\displaystyle\leq 2\max_{\ell}\frac{\sum_{c\geq 0}\binom{n}{\lfloor
n/2\rfloor+cm+\ell}\lvert\mathcal{K}(n,\lfloor
n/2\rfloor+cm+\ell,k)\rvert}{\sum_{c\geq 0}\binom{n}{\lfloor
n/2\rfloor+cm+\ell}},$ (6)

where the indices of $c$ are integers that iterate over $\lfloor
n/2\rfloor+cm+\ell\in\\{0,\ldots,n\\}$, and the last line uses the symmetry of
${n\choose w}\mathcal{K}(n,w,k)$ around $w=n/2.$

Later in this section, we will prove (in Claim 22) that

$\lvert\mathcal{K}(n,\lfloor n/2\rfloor+s,k)\rvert\leq
2^{O(k)}\left(\left(\frac{n}{k}\right)^{\frac{k}{2}}+\left(\frac{\lvert
s\rvert}{k}\right)^{k}\right).$

Plugging this bound into Equation 6, we have

6 $\displaystyle\leq 2^{O(k)}\max_{\ell}\left(\frac{\sum_{c\geq
0}\binom{n}{\lfloor
n/2\rfloor+cm+\ell}\bigl{(}(n/k)^{k/2}+((cm+\ell)/k)^{k}\bigr{)}}{\sum_{c\geq
0}\binom{n}{\lfloor n/2\rfloor+cm+\ell}}\right)$
$\displaystyle=O(n/k)^{\frac{k}{2}}+\frac{2^{O(k)}}{k^{k}}\max_{\ell}\left(\frac{\sum_{c\geq
0}\binom{n}{\lfloor n/2\rfloor+cm+\ell}(cm+\ell)^{k}}{\sum_{c\geq
0}\binom{n}{\lfloor n/2\rfloor+cm+\ell}}\right).$ (7)

We will prove the following claim which bounds the ratio of the two
summations.

######  Claim 20.

For any $\ell\in\\{0,\ldots,m-1\\}$ and $k\geq n/(2m)^{2}$, we have

$\frac{\sum_{c\geq 0}\binom{n}{\lfloor
n/2\rfloor+cm+\ell}(cm+\ell)^{k}}{\sum_{c\geq 0}\binom{n}{\lfloor
n/2\rfloor+cm+\ell}}\leq O(mk)^{k}.$

Therefore, as $(n/k)^{1/2}\leq 2m$, we have

$\lx@cref{creftype~refnum}{eq:bias2}\leq
O(n/k)^{\frac{k}{2}}+\frac{2^{O(k)}}{k^{k}}\cdot O(mk)^{k}=O(m)^{k}.$

This completes the proof of Lemma 19. ∎

It remains to prove Claims 20 and 22. We begin with Claim 20.

###### Proof of Claim 20.

Fix any $\ell\in\\{0,\ldots,m-1\\}$, we first bound

$\frac{\sum_{c\geq 0}\binom{n}{\lfloor
n/2\rfloor+cm+\ell}(cm+\ell)^{k}}{\sum_{c\geq 0}\binom{n}{\lfloor
n/2\rfloor+cm+\ell}}$

with some quantity that does not depend on $\ell$. First, observe that the
denominator is at least $\binom{n}{\lfloor n/2\rfloor+\ell}$. Next, we have

$\displaystyle\frac{\binom{n}{\lfloor n/2\rfloor+\ell+cm}}{\binom{n}{\lfloor
n/2\rfloor+\ell}}$ $\displaystyle=\prod_{i=1}^{cm}\left(\frac{n-\lfloor
n/2\rfloor-\ell-cm+i}{\lfloor n/2\rfloor+\ell+i}\right)$
$\displaystyle=\prod_{i=1}^{cm}\left(1-\frac{2\ell+cm+\lfloor
n/2\rfloor-\lceil n/2\rceil}{\lfloor n/2\rfloor+\ell+i}\right)$
$\displaystyle\leq\left(1-\frac{2\ell+cm-1}{n}\right)^{cm}$
$\displaystyle\leq\exp\left(-\frac{cm(cm-1)}{n}\right)$ $\displaystyle\leq
e\cdot\exp(-(cm)^{2}/n)$ $\displaystyle(e^{cm/n}\leq e)$ $\displaystyle\leq
e\cdot\exp(-(c^{2}/4k))$ $\displaystyle(k\geq n/(2m)^{2}).$

Finally, we have $\ell\leq m$ and $(cm+\ell)\leq(c+1)m\leq 2cm$ for $c\geq 1$.
Therefore

$\displaystyle\frac{\sum_{c\geq 0}(cm+\ell)^{k}\binom{n}{\lfloor
n/2\rfloor+cm+\ell}}{\sum_{c\geq 0}\binom{n}{\lfloor n/2\rfloor+cm+\ell}}$
$\displaystyle\leq\frac{\sum_{c\geq 0}(cm+\ell)^{k}\binom{n}{\lfloor
n/2\rfloor+cm+\ell}}{\binom{n}{\lfloor n/2\rfloor+\ell}}$ $\displaystyle\leq
m^{k}+e\sum_{c\geq 1}(2cm)^{k}e^{-\frac{c^{2}}{4k}}$
$\displaystyle=m^{k}+e(2m)^{k}\sum_{c\geq 1}c^{k}e^{-\frac{c^{2}}{4k}}.$

In Claim 21 below we will show that the summation in the last line is bounded
by $O(k^{k})$. Applying this bound completes the proof. ∎

######  Claim 21.

$\sum_{c\geq 1}c^{k}e^{-\frac{c^{2}}{4k}}\leq O(k^{k})$ for any $k\geq 1$.

###### Proof.

Consider the function

$\lambda_{a}(x):=x^{k}\cdot e^{-ax^{2}},$

for some parameter $a>0$. Its derivative is
$\lambda_{a}^{\prime}(x)=(k-2ax^{2})x^{k-1}e^{-ax^{2}}$; so for $x\geq 0$,
$\lambda_{a}(x)$ is increasing when $x\leq\sqrt{k/(2a)}$, and is decreasing
when $x\geq\sqrt{k/(2a)}$. For such a (nonnegative) first-increasing-then-
decreasing function, it can be seen that

$\displaystyle\sum_{c\geq 1}\lambda_{a}(c)$
$\displaystyle\leq\underbrace{\vphantom{\int_{0}^{\infty}}\max\\{\lambda_{a}(x):x\geq
0\\}}_{\textup{A}}+\underbrace{\int_{0}^{\infty}\lambda_{a}(x)dx}_{\textup{B}}.$

The first term section 4.2 is exactly equal to

$\lx@cref{creftype~refnum}{term:T1}=\lambda_{a}\left(\sqrt{k/(2a)}\right)=\left(\frac{k}{2ea}\right)^{k/2}.$

Using the substitution $u=ax^{2}$, the second term section 4.2 is equal to

$\lx@cref{creftype~refnum}{term:T2}=\int_{0}^{\infty}x^{k}e^{-ax^{2}}dx=\frac{1}{2}a^{-\frac{k+1}{2}}\cdot\Gamma\left(\frac{k+1}{2}\right).$

where $\Gamma(k):=\int_{0}^{\infty}x^{k-1}e^{-x}dx$ is the Gamma function. It
is known (see, for example, [OLBC10, Equation (5.6.1)]) that
$\Gamma(\frac{k+1}{2})\leq\sqrt{2\pi}\cdot
e^{\frac{1}{12}}\cdot(\frac{k}{2e})^{k/2}$ for each integer $k\geq 1$.
Plugging this upper bound into the above formula gives

$\lx@cref{creftype~refnum}{term:T2}\leq
e^{\frac{1}{12}}\cdot\sqrt{\frac{\pi}{2a}}\cdot\left(\frac{k}{2ea}\right)^{k/2}\leq\frac{2}{\sqrt{a}}\cdot\left(\frac{k}{2ea}\right)^{k/2}.$

By setting $a=1/(4k)$, we deduce that

$\lx@cref{creftype~refnum}{term:T1}+\lx@cref{creftype~refnum}{term:T2}\leq\bigl{(}1+4\sqrt{k}\bigr{)}\cdot\left(2k^{2}/e\right)^{k/2}=\frac{1+4\sqrt{k}}{(e/2)^{k/2}}\cdot
k^{k}=O(1)\cdot k^{k},$

proving the claim. ∎

It remains to prove Claim 22, which gives a bound on
$\mathcal{K}(n,w,k):=\sum_{x\in\mathcal{X}_{k}}(-1)^{x_{1}+\cdots+x_{w}}$.

######  Claim 22.

$\lvert\mathcal{K}(n,\lfloor n/2\rfloor+s,k)\rvert\leq
2^{O(k)}((n/k)^{k/2}+(\lvert s\rvert/k)^{k})$ for any $k\geq 1.$

A similar claim was also made in [CPT20, Claim 4.10], but the bounds we obtain
here are more general and sharper for larger $\lvert s\rvert$, which is
crucial for our application. We start with a preliminary claim.

######  Claim 23.

For any positive integer $s$,

$\sum_{i=0}^{\lfloor
k/2\rfloor}\frac{n^{i}}{i!}\frac{s^{k-2i}}{(k-2i)!}\leq\begin{cases}(2e)^{k}\left(\frac{n}{k}\right)^{k/2}&\text{if
$s\leq\sqrt{nk}$}\\\ (2e)^{k}\left(\frac{s}{k}\right)^{k}&\text{if
$s\geq\sqrt{nk}$.}\end{cases}$

###### Proof.

Write $s=(cn)^{1/2}$ for some $c>0$. Then $n^{i}s^{k-2i}=(cn)^{k/2}/c^{i}$,
and

$\displaystyle\sum_{i=0}^{\lfloor
k/2\rfloor}\frac{n^{i}}{i!}\frac{s^{k-2i}}{(k-2i)!}=(cn)^{\frac{k}{2}}\sum_{i=0}^{\lfloor
k/2\rfloor}\frac{1}{c^{i}i!(k-2i)!}.$ (8)

We can write

$\frac{1}{i!(k-2i)!}=\frac{(2i)!}{k!i!}\frac{k!}{(2i)!(k-2i)!}=\frac{(2i)!}{k!i!}\binom{k}{2i}.$

So

8 $\displaystyle=\frac{(cn)^{\frac{k}{2}}}{k!}\sum_{i=0}^{\lfloor
k/2\rfloor}\frac{(2i)!}{c^{i}i!}\binom{k}{2i}$
$\displaystyle\leq\frac{(cn)^{\frac{k}{2}}}{k!}\max_{0\leq
i\leq\lfloor\frac{k}{2}\rfloor}\left(\frac{2i}{c}\right)^{i}\cdot\sum_{i=0}^{\lfloor
k/2\rfloor}\binom{k}{2i}$ $\displaystyle\leq
2^{k}\cdot\frac{(cn)^{\frac{k}{2}}}{k!}\max_{0\leq
i\leq\lfloor\frac{k}{2}\rfloor}\left(\frac{2i}{c}\right)^{i}.$

If $c\leq k$, then for $0\leq i\leq\lfloor k/2\rfloor$, we have $2i/c\leq k/c$
and thus $(2i/c)^{i}\leq(k/c)^{i}\leq(k/c)^{k/2}$ because $k/c\geq 1$. Hence,

$2^{k}\cdot\frac{(cn)^{\frac{k}{2}}}{k!}\max_{0\leq
i\leq\lfloor\frac{k}{2}\rfloor}\left(\frac{2i}{c}\right)^{i}\leq
2^{k}\frac{(cn)^{\frac{k}{2}}}{k!}\left(\frac{k}{c}\right)^{\frac{k}{2}}\leq(2e)^{k}\left(\frac{n}{k}\right)^{k/2}.$

If $c\geq k$, then for $0\leq i\leq\lfloor k/2\rfloor$, we have
$(2i/c)^{i}\leq 1$, and thus

$2^{k}\cdot\frac{(cn)^{\frac{k}{2}}}{k!}\max_{0\leq
i\leq\lfloor\frac{k}{2}\rfloor}\left(\frac{2i}{c}\right)^{i}\leq(2e)^{k}\left(\frac{cn}{k^{2}}\right)^{\frac{k}{2}}=(2e)^{k}\left(\frac{s}{k}\right)^{k}.\qed$

###### Proof of Claim 22.

Observe that

$(1-x)^{w}(1+x)^{n-w}=\sum_{k=0}^{n}\mathcal{K}(n,w,k)x^{k},$

Our goal is to bound above its $k$-th coefficient. We will assume $n$ is even,
otherwise we can apply the bound for $n+1$, which affects its magnitude by at
most a factor of $2$. By the symmetry of $\mathcal{K}(n,u,k)$ around $u=n/2$,
for Claim 22 we may take $w=n/2-s$, and for this choice of $w$ we have

$\displaystyle\sum_{k=0}^{n}\mathcal{K}(n,n/2-s,k)x^{k}=(1-x)^{\frac{n}{2}-s}(1+x)^{\frac{n}{2}+s}=(1-x^{2})^{\frac{n}{2}}\left(\frac{1+x}{1-x}\right)^{s}.$
(9)

We bound from above the coefficients of the power series expansion of the two
terms on the right hand side. The $i$-th coefficient of $(1-x^{2})^{n/2}$ is
$\binom{n/2}{i/2}$ if $i$ is even and is $0$ otherwise (because the function
is even). For $(\frac{1+x}{1-x})^{s}$, we will assume that $s$ is nonnegative
as this only affects the sign of its coefficients. Since
$\frac{1+x}{1-x}=1+\sum_{j\geq 1}2x^{j}$ and $\frac{1}{1-2x}=1+\sum_{j\geq
1}(2x)^{j}$ for $\lvert x\rvert<1/2$ in their power series expansion, the
$j$-th coefficient of $(\frac{1+x}{1-x})^{s}$ is at most the $j$-th
coefficient of $(1-2x)^{-s}$, which is

$2^{j}\cdot\frac{s\cdot(s+1)\cdots(s+j-1)}{1\cdot 2\cdots
j}=\binom{s+j-1}{j}2^{j}.$

Therefore, the magnitude of the $k$-th coefficient of Equation 9 is at most

$\displaystyle\sum_{i=0}^{\lfloor k/2\rfloor}\binom{n/2}{i}\binom{\lvert
s\rvert+k-2i-1}{k-2i}2^{k-2i}.$ (10)

Using $\binom{n}{k}\leq n^{k}/k!\,$, we have

$\displaystyle\lx@cref{creftype~refnum}{eq:kravchuk2}\leq\sum_{i=0}^{\lfloor
k/2\rfloor}\frac{n^{i}}{i!}\frac{(\lvert
s\rvert+k-2i-1)^{k-2i}}{(k-2i)!}2^{k-2i}.$

Note that $(s+t)^{j}\leq 2^{j}\max\\{s^{j},t^{j}\\}$ and so

$\frac{(\lvert s\rvert+k-2i-1)^{k-2i}}{(k-2i)!}\leq
2^{k-2i}\left(\frac{\max\\{\lvert
s\rvert^{k-2i},(k-2i-1)^{k-2i}\\}}{(k-2i)!}\right)\leq
2^{k-2i}\left(\frac{\max\\{\lvert
s\rvert^{k-2i},k^{k-2i}\\}}{(k-2i)!}\right).$

Therefore, 10 is bounded by

$2^{2k}\left(\sum_{i=0}^{\lfloor
k/2\rfloor}\frac{n^{i}}{i!}\frac{\max\\{\lvert
s\rvert^{k-2i},k^{k-2i}\\}}{(k-2i)!}\right).$

The claim then follows from Claim 23. ∎

###  4.3 Proof of Theorem 9

In this subsection, we give examples of symmetric polynomials $p$ with
$L_{1,k}(p)=\Omega_{k}(1)\cdot d^{k}$ for $d=\Theta(\sqrt{n})$, matching our
upper bound up to a constant factor when $k=O(1)$. We restate our theorem for
convenience.

######  Theorem 24 (Restatement of Theorem 9).

For every $k$, there is a symmetric $\mathbbm{F}_{2}$-polynomial
$p(x_{1},\ldots,x_{n})$ of degree $d=\Theta(\sqrt{kn})$ such that
$L_{1,k}(p)\geq(e^{-k}/2)\cdot\binom{n}{k}^{1/2}=\Omega_{k}(1)\cdot d^{k}$.

###### Proof.

Let $m:=C\sqrt{kn}$ for some constant $4\leq C\leq 8$ such that $m$ is a power
of two. Consider the function $h_{k}\colon\\{0,1\\}^{n}\to\\{-1,1\\}$ defined
by

$h_{k}(x)=\textnormal{sgn}\Bigg{(}\sum_{\lvert S\rvert=k}(-1)^{\sum_{i\in
S}x_{i}}\Bigg{)}.$

Let $\widetilde{h_{k}}\colon\\{0,\ldots,n\\}\to\\{-1,1\\}$ be the
symmetrization of $h_{k}$ so that $\widetilde{h_{k}}(\lvert
x\rvert):=h_{k}(x)$. Now consider the periodic function
$\widetilde{p}\colon\\{0,\ldots,n\\}\to\\{-1,1\\}$ that on input
$z\in\\{0,\ldots,n\\}$ such that

$z+2tm\in[n/2-m,n/2+m)\text{ for some $t\in\mathbbm{Z}$},$

evaluates to $\widetilde{p}(z):=\widetilde{h}_{k}(z+2tm)$. We define the
$\mathbbm{F}_{2}$-polynomial $p$ by $p(x_{1},\ldots,x_{n}):=\tilde{p}(\lvert
x\rvert)$. Since $p(x)$ depends only on $\lvert x\rvert\bmod 2m$, by Lemma 17,
it can be computed by a symmetric $\mathbbm{F}_{2}$-polynomial of degree
$d<2m$. Moreover, $p(x)$ agrees with $h_{k}(x)$ when $\lvert
x\rvert\in[n/2-m,n/2+m)$. Let $f=(-1)^{p}$. We have (note that from here on we
switch from $x\in\\{0,1\\}^{n}$ to $x\in\\{-1,1\\}^{n}$)

$\displaystyle L_{1,k}(f)\geq\Bigg{\lvert}\sum_{\lvert
S\rvert=k}\widehat{f}(S)\Bigg{\rvert}$
$\displaystyle=\Bigg{\lvert}\sum_{\lvert S\rvert=k}\mathop{\bf
E\/}_{x}\Bigl{[}f(x)x^{S}\Bigr{]}\Bigg{\rvert}$
$\displaystyle=\Bigg{\lvert}\sum_{\lvert S\rvert=k}\mathop{\bf
E\/}_{x}\Bigl{[}h_{k}(x)x^{S}\Bigr{]}+\mathop{\bf
E\/}_{x}\Bigl{[}\bigl{(}f(x)-h_{k}(x)\bigr{)}x^{S}\Bigr{]}\Bigg{\rvert}$
$\displaystyle=\Bigg{\lvert}\mathop{\bf E\/}_{x}\Biggl{[}h_{k}(x)\sum_{\lvert
S\rvert=k}x^{S}\Biggr{]}+\mathop{\bf
E\/}_{x}\Biggl{[}\bigl{(}f(x)-h_{k}(x)\bigr{)}\sum_{\lvert
S\rvert=k}x^{S}\Biggr{]}\Bigg{\rvert}$
$\displaystyle\geq\left|\Bigg{\lvert}\mathop{\bf
E\/}_{x}\Biggl{[}h_{k}(x)\sum_{\lvert
S\rvert=k}x^{S}\Biggr{]}\Bigg{\rvert}-\Bigg{\lvert}\mathop{\bf
E\/}_{x}\Biggl{[}\bigl{(}f(x)-h_{k}(x)\bigr{)}\sum_{\lvert
S\rvert=k}x^{S}\Biggr{]}\Bigg{\rvert}\right|.$

We proceed to lower bound the first term and upper bound the second term. For
the first term we use the same lower bound of $e^{-k}\binom{n}{k}^{1/2}$ in
the proof of [Vio20, Theorem 1]; for completeness we include the argument
here. One can verify that $\mathop{\bf E\/}_{x}[(\sum_{\lvert
S\rvert=k}x^{S})^{2}]=\binom{n}{k}$. Applying [O’D14, Theorem 9.22], which
states that $\mathop{\bf E\/}[\lvert h(x)\rvert]\geq e^{-k}\mathop{\bf
E\/}[h(x)^{2}]^{1/2}$ for any $h\colon\\{-1,1\\}^{n}\to\mathbbm{R}$ of degree
$k$, we get

$\displaystyle e^{-k}\binom{n}{k}^{1/2}=e^{-k}\mathop{\bf
E\/}_{x}\Biggl{[}\Biggl{(}\sum_{\lvert
S\rvert=k}x^{S}\Biggr{)}^{2}\Biggr{]}^{1/2}\leq\mathop{\bf
E\/}_{x}\Biggl{[}\Bigg{\lvert}\sum_{\lvert
S\rvert=k}x^{S}\Bigg{\rvert}\Biggr{]}\leq\mathop{\bf
E\/}_{x}\Biggl{[}\Biggl{(}\sum_{\lvert
S\rvert=k}x^{S}\Biggr{)}^{2}\Biggr{]}^{1/2}=\binom{n}{k}^{1/2}.$

So for the first term we have

$\mathop{\bf E\/}_{x}\Biggl{[}h_{k}(x)\sum_{\lvert
S\rvert=k}x^{S}\Biggr{]}=\mathop{\bf E\/}_{x}\left[\Bigg{\lvert}\sum_{\lvert
S\rvert=k}x^{S}\Bigg{\rvert}\right]\geq e^{-k}\binom{n}{k}^{1/2}.$

We now bound above the second term. As $\lvert f(x)-h_{k}(x)\rvert\leq 2$ for
every $x$, by the Cauchy–Schwarz inequality, we get

$\displaystyle\left|\mathop{\bf
E\/}_{x}\Biggl{[}\bigl{(}f(x)-h_{k}(x)\bigr{)}\sum_{\lvert
S\rvert=k}x^{S}\Biggr{]}\right|$ $\displaystyle\leq 2\cdot\mathop{\bf
Pr\/}_{x}\biggl{[}2\Big{\lvert}\sum_{i}x_{i}\Big{\rvert}\geq
m\biggr{]}\mathop{\bf E\/}_{x}\left[\Biggl{(}\sum_{\lvert
S\rvert=k}x^{S}\Biggr{)}^{2}\right]^{1/2}$ $\displaystyle=2\cdot\mathop{\bf
Pr\/}_{x}\biggl{[}2\Big{\lvert}\sum_{i}x_{i}\Big{\rvert}\geq
m\biggr{]}\binom{n}{k}^{1/2}$
$\displaystyle\leq(e^{-k}/2)\cdot\binom{n}{k}^{1/2},$

where the last inequality follows from the Chernoff bound recalling our choice
of $m=\Theta(\sqrt{kn})$. Therefore
$L_{1,k}(f)\geq(e^{-k}/2)\cdot\binom{n}{k}^{1/2}$, proving the theorem. ∎

##  5 $L_{1,k}$ bounds for read-$\Delta$ polynomials

In this section, we give our $L_{1,k}$ bounds on read-few polynomials, which
are restated below for convenience.

######  Theorem 25 (Restatement of Theorem 10).

Let $p(x_{1},\ldots,x_{n})$ be any read-$\Delta$ degree-$d$ polynomial. For
every $1\leq k\leq n$,

$L_{1,k}(p)\leq\mathop{\bf Pr\/}[p=1]\cdot O(k)^{k}\cdot(\Delta d)^{8k}.$

By observing that any degree-$\Omega(\log n)$ monomial vanishes under a random
restriction with high probability, we can use Theorem 25 to obtain an upper
bound for read-$\Delta$ polynomials that is independent of $d$:

######  Corollary 26 (Restatement of Corollary 11).

Let $p(x_{1},\ldots,x_{n})$ be a read-$\Delta$ polynomial. For any $1\leq
k\leq n$,

$L_{1,k}(p)\leq O(k)^{9k}\cdot(\Delta\log n)^{8k}.$

###### Proof.

Let $R$ be a $\rho$-random restriction that independently for each $x_{i}$
with probability $1-\rho$ sets $x_{i}$ to a uniform random bit and keeps
$x_{i}$ alive with the remaining $\rho$ probability. For any
$f\colon\\{-1,1\\}^{n}\to\\{-1,1\\}$, we have $\mathop{\bf
E\/}_{R}[\widehat{f_{R}}(S)]=\rho^{\lvert S\rvert}\widehat{f}(S)$. Thus,

$L_{1,k}(f)=\sum_{\lvert S\rvert=k}\lvert\widehat{f}(S)\rvert=\sum_{\lvert
S\rvert=k}\lvert\rho^{-k}\mathop{\bf
E\/}_{R}[\widehat{f_{R}}(S)]\rvert\leq\rho^{-k}\mathop{\bf
E\/}_{R}[L_{1,k}(f_{R})].$

Let $p(x_{1},\ldots,x_{n})$ be any read-$\Delta$ polynomial. Note that
$L_{1,k}(f)\leq n^{k/2}$ for any $f$. Hence, by Theorem 25, for any $d_{\max}$
and any $\rho$, we have

$L_{1,k}(p)\leq\rho^{-k}\cdot O(k)^{k}(\Delta
d_{\max})^{8k}+\rho^{-k}\cdot\mathop{\bf Pr\/}_{R}[\deg(p_{R})\geq
d_{\max}]\cdot n^{k/2}.$

We now upper bound $\mathop{\bf Pr\/}_{R}[\deg(p_{R})\geq d_{\max}]$. Each
monomial with degree greater than $d_{\max}$ survives $R$ with probability at
most $\rho^{d_{\max}}$, and there are at most $(\Delta n)/d_{\max}$ such
monomials in $p$. It follows by a union bound that $\mathop{\bf
Pr\/}_{R}[\deg(p_{R})\geq d_{\max}]\leq\rho^{d_{\max}}(\Delta n)/d_{\max}$. So
setting $\rho=1/2$ and $d_{\max}=2k\log n$, we have

$\displaystyle L_{1,k}(p)$ $\displaystyle\leq O(k)^{k}(\Delta\cdot
d_{\max})^{8k}+\frac{\rho^{d_{\max}}\Delta\cdot n^{1+k/2}}{\rho^{k}d_{\max}}$
$\displaystyle\leq O(k)^{9k}\cdot(\Delta\log n)^{8k}.\qed$

##### Proof idea.

We first observe that for $f=(-1)^{p}$, the Fourier coefficient
$\widehat{f}(S)$ is simply the bias of the $\mathbbm{F}_{2}$-polynomial
$p_{S}(x):=p(x)+\sum_{i\in S}x_{i}$. Assuming that $p_{S}$ depends on all $n$
variables, by a simple greedy argument we can collect
$n/\textnormal{poly}(\Delta,d)$ polynomials in $p_{S}$ so that each of them
depends on disjoint variables, and it is not hard to show that the product of
the biases of these polynomials upper bounds the bias of $p_{S}$. From this is
easy to see that any read-$\Delta$ degree-$d$ polynomial has bias
$\exp(2^{-d}n/\textnormal{poly}(\Delta,d))$. However, this quantity is too
large to sum over $\binom{n}{k}$ coefficients.

Our next idea (Lemma 27) is to give a more refined decomposition of the
polynomial $p$ by inspecting the variables $x_{i}:i\in S$ more closely.
Suppose the variables $x_{i}:i\in S$ are far apart in their dependency graph
(see the definition of $G_{p}$ below), as must indeed be the case for most of
the ${n\choose k}$ size-$k$ sets $S$. Then we can collect all the monomials
containing each $x_{i}$ to form a polynomial $p_{i}$, and these $p_{i}$’s will
depend on disjoint variables. Moreover, if every monomial in $p_{i}$ has high
degree (see the definition of $V_{t}(p)$ below), then $p_{i}=0$ with high
probability and therefore $p_{i}+x_{i}$ is almost unbiased. Therefore, we can
first collect these $p_{i}$ and $x_{i}$ from $p_{S}$; then, for the remaining
$m\geq\lvert S\rvert\cdot\textnormal{poly}(\Delta,d)$ monomials in $p_{S}$, as
before we collect $m/\textnormal{poly}(\Delta,d)$ polynomials $r_{i}$ so that
they depend on disjoint variables, but this time we collect these monomials
using the variables in $V_{t}(p)$, and give an upper bound in terms of the
size $\lvert V_{t}(p)\rvert$. Multiplying the biases of the $p_{i}+x_{i}$’s
and the bias of $r$ gives our refined upper bound on $\widehat{f}(S)$ in Lemma
27.

We now proceed to the actual proof. We first define some notions that will be
used throughout our arguments. For a read-$\Delta$ degree-$d$ polynomial $p$,
we define $V_{t}(p):t\in[d]$ and $G_{p}$ as follows.

For every $t\in[d]$, define

$V_{t}(p):=\\{i\in[n]:\text{the minimum degree of the monomials in $p$
containing $x_{i}$ is $t$}\\}.$

Note that the sets $V_{1}(p),\dots,V_{d}(p)$ form a partition of the input
variables $p$ depends on.

Define the undirected graph $G_{p}$ on $[n]$, where $i,j\in[n]$ are adjacent
if $x_{i}$ and $x_{j}$ both appear in the same monomial in $q$. Note that
$G_{p}$ has degree at most $\Delta d$. For $S\subseteq[n]$, we use $N_{=d}(S)$
to denote the indices that are at distance exactly $i$ to $S$ in $G_{p}$, and
use $N_{\leq d}(S)$ to denote $\bigcup_{j=0}^{d}N_{=j}(S)$.

We first state our key lemma, which gives a refined bound on each
$\widehat{f}(S)$ stronger than the naive bound sketched in the first paragraph
of the “Proof Idea” above, and use it to prove Theorem 25. We defer its proof
to the next section.

######  Lemma 27 (Main lemma for read-$\Delta$ polynomials).

Let $p(x_{1},\ldots,x_{n})$ be a read-$\Delta$ degree-$d$ polynomial. Let
$S\subseteq[n],\lvert S\rvert\geq\ell$ be a subset containing some $\ell$
indices $i_{1},\ldots,i_{\ell}\in S$ whose pairwise distances in $G_{p}$ are
at least $4$, and let $t_{1},\dots,t_{\ell}\in[d]$ be such that each $i_{j}\in
V_{t_{j}}(p)$. Let $f=(-1)^{p}$. Then

$\lvert\widehat{f}(S)\rvert\leq O(1)^{\lvert
S\rvert}\cdot\Delta^{\ell}\prod_{j\in[\ell]}\left(2^{-t_{j}}\exp\left(-\frac{2^{-{t_{j}}}\lvert
V_{t_{j}}(p)\rvert}{\ell\cdot(\Delta d)^{4}}\right)\right).$

###### Proof of Theorem 25.

Using a reduction given in the proof of [CMM+20, Lemma 2.2], it suffices to
prove the same bound without the acceptance probability factor, i.e. to prove
that for every $1\leq k\leq n$,

$L_{1,k}(p)\leq O(k)^{k}\cdot(\Delta d)^{8k}.$

As [CMM+20] did not provide an explicit statement of the reduction, for
completeness we provide a self-contained statement and proof in Lemma 36 in
Appendix A.

For every subset $S\subseteq[n]$ of size $k$, there exists an $\ell\leq k$ and
$i_{1},\ldots,i_{\ell}\in S$ such that their pairwise distances in $G_{p}$ are
at least $4$, each $i_{j}\in V_{t_{j}}(p)$ for some $t_{j}\in[d]$, and each of
the remaining $k-\ell$ indices in $S$ is within distance at most $3$ to some
$i_{j}$.

Fix any $i_{1},\ldots,i_{\ell}$, and let us bound the number of subsets
$S\subseteq[n]$ of size $k$ that can contain $i_{1},\ldots,i_{\ell}$. Because
$\lvert N_{\leq 3}(j)\rvert\leq(\Delta d)^{3}+(\Delta d)^{2}+\Delta d+1\leq
4(\Delta d)^{3}$ for every $j\in[n]$, the remaining $k-\ell$ indices of $S$
can appear in at most

$\displaystyle\sum_{j_{1}+\cdots+j_{\ell}=k-\ell}\prod_{b\in[\ell]}\binom{4(\Delta
d)^{3}}{j_{b}}$ $\displaystyle=\binom{4\ell(\Delta d)^{3}}{k-\ell}$
$\displaystyle\leq(4(\Delta d)^{3})^{k}\cdot
e^{k-\ell}\left(\frac{\ell}{k-\ell}\right)^{k-\ell}$
$\displaystyle\leq(e\Delta d)^{3k}$

different ways, where the equality uses the Vandermonde identity, the first
inequality uses $\binom{n}{k}\leq(en/k)^{k}$, and the last one uses
$(\frac{\ell}{k-\ell})^{k-\ell}\leq(1+\frac{\ell}{k-\ell})^{k-\ell}\leq
e^{\ell}$ and $4e<e^{3}$. Therefore, by Lemma 27,

$\displaystyle\sum_{S:\lvert S\rvert=k}\lvert\widehat{f}(S)\rvert$
$\displaystyle\leq\sum_{\ell=1}^{k}\sum_{t\subseteq[d]^{\ell}}\left[\Biggl{(}\prod_{j\in[\ell]}\lvert
V_{t_{j}}(p)\rvert\Biggr{)}\cdot(e\Delta d)^{3k}\cdot
O(1)^{k}\Delta^{\ell}\prod_{j^{\prime}\in[\ell]}\left(2^{-t_{j^{\prime}}}\exp\left(-\frac{2^{-{t_{j^{\prime}}}}\lvert
V_{t_{j^{\prime}}}(p)\rvert}{\ell(\Delta d)^{4}}\right)\right)\right]$
$\displaystyle\leq O(1)^{k}\cdot(\Delta
d)^{3k}\sum_{\ell=1}^{k}\Delta^{\ell}\sum_{t\subseteq[d]^{\ell}}\prod_{j\in[\ell]}\left(2^{-t_{j}}\lvert
V_{t_{j}}(p)\rvert\exp\left(-\frac{2^{-{t_{j}}}\lvert
V_{t_{j}}(p)\rvert}{\ell(\Delta d)^{4}}\right)\right)$ $\displaystyle\leq
O(1)^{k}\cdot(\Delta d)^{3k}\sum_{\ell=1}^{k}\Delta^{\ell}\cdot
d^{\ell}\cdot(\ell(\Delta d)^{4})^{\ell}$ $\displaystyle\leq
O(k)^{k}\cdot(\Delta d)^{3k}\cdot(\Delta d)^{5k}$
$\displaystyle=O(k)^{k}\cdot(\Delta d)^{8k},$

where the third inequality is because the function $x\mapsto xe^{-x/c}$ is
maximized when $x=c$. This completes the proof. ∎

###  5.1 Proof of Lemma 27

First we need a simple lemma that lower bounds the acceptance probability of a
sparse polynomial.

######  Lemma 28.

Let $r(x_{1},\ldots,x_{n})$ be a polynomial with at most $\Delta$ monomials,
each of which has degree at least $t$, and $r(0)=0$. Then $\mathop{\bf
Pr\/}[r(x)=0]\geq\max\\{\frac{1}{\Delta+1},1-2^{-t}\Delta\\}$.

###### Proof.

The lower bound of $1/(\Delta+1)$ follows from [KL93, Corollary 1]. For the
other bound, note that each monomial evaluates to $1$ with probability at most
$2^{-t}$; so by a union bound $\mathop{\bf Pr\/}[r(x)=1]\leq 2^{-t}\Delta$. ∎

We use $G_{p}$ to partition $[n]$ as follows. For each $j\in[\ell]$, let
$T_{j}:=N_{=1}(i_{j})$, the set of distance-1 neighbors of $i_{j}$. Let
$R:=[n]\setminus\bigcup_{j}(\\{i_{j}\\}\cup T_{j})$ be the remaining variables
(note that these are the variables whose distance from every $i_{j}$ is at
least two). As the $i_{j}$’s are at distance at least $4$ apart, then for
$j\neq j^{\prime}$ each index in $\\{i_{j}\\}\cup T_{j}$ has distance at least
$2$ to each index in $\\{i_{j^{\prime}}\\}\cup T_{j^{\prime}}$; so the
variables in $\\{i_{j}\\}\cup T_{j}$ appear in disjoint monomials from the
variables in $\\{i_{j^{\prime}}\\}\cup T_{j^{\prime}}$. We now partition the
monomials in $p$. For each $j\in[\ell]$, let $p_{j},q_{j}$ be two polynomials
such that $p_{j}$ is composed of all the monomials in $p$ that contain
$x_{i_{j}}$, and $q_{j}$ is composed of all monomials that contain some
variable in $x_{T_{j}}$ but not $x_{i_{j}}$. Let $r$ be the polynomial
composed of the remaining monomials in $p$. We can write $p$ as

$\sum_{j=1}^{\ell}\bigl{(}p_{j}(x_{i_{j}},x_{T_{j}})+q_{j}(x_{T_{j}},x_{R})\bigr{)}+r(x_{R}).$

Now, consider the polynomial

$\displaystyle p_{S}(x_{1},\ldots,x_{n})$
$\displaystyle:=p(x_{1},\ldots,x_{n})+\sum_{i\in S}x_{i}$
$\displaystyle\phantom{:}=\sum_{j=1}^{\ell}s_{j}(x_{i_{j}},x_{T_{j}},x_{R})+r^{\prime}(x_{R}),$
(11)

where

$\displaystyle s_{j}(x_{i_{j}},x_{T_{j}},x_{R})$
$\displaystyle:=p_{j}(x_{i_{j}},x_{T_{j}})+q_{j}(x_{T_{j}},x_{R})+x_{i_{j}}+\sum_{k\in
S\cap T_{j}}x_{k}$ (12) $\displaystyle r^{\prime}(x_{R})$
$\displaystyle:=r(x_{R})+\sum_{k\in S\cap R}x_{k}.$

The following claim gives an upper bound on the bias of $s_{j}$; we defer its
proof till later. (To interpret the claim it may be helpful to recall that
$i_{j}\in V_{t_{j}}(p)$, and hence the minimum degree of the monomials in $p$
containing $x_{i_{j}}$ is $t_{j}$.)

######  Claim 29.

For each possible outcome of $x_{R}$, we have $\lvert\mathop{\bf
E\/}_{x_{i_{j}},x_{T_{j}}}[(-1)^{s_{j}(x_{i_{j}},x_{T_{j}},x_{R})}]\rvert\leq\Delta
2^{-(t_{j}-1)}$ for every $j\in[\ell]$.

We have that

$\displaystyle\lvert\widehat{f}(S)\rvert$
$\displaystyle=\bigg{\lvert}\mathop{\bf
E\/}\Bigl{[}(-1)^{p_{S}(x)}\Bigr{]}\bigg{\rvert}$
$\displaystyle=\Bigg{\lvert}\mathop{\bf
E\/}_{x_{R}}\biggl{[}(-1)^{r^{\prime}(x_{R})}\cdot\prod_{j\in[\ell]}\mathop{\bf
E\/}_{x_{T_{j}},x_{i_{j}}}\Bigl{[}(-1)^{s_{j}(x_{i_{j}},x_{T_{j}},x_{R})}\Bigr{]}\biggr{]}\Bigg{\rvert}$
(13)
$\displaystyle\leq(2\Delta)^{\ell}\cdot\biggl{(}\prod_{j\in[\ell]}2^{-t_{j}}\biggr{)}\cdot\bigg{\lvert}\mathop{\bf
E\/}_{x_{R}}\Bigl{[}(-1)^{r^{\prime}(x_{R})}\Bigr{]}\bigg{\rvert},$ (14)

where Equation 13 is by independence of the different
$(x_{T_{j}},x_{i_{j}})$’s and Equation 14 is by Claim 29. We now claim that

$\lvert V_{t}(r^{\prime})\rvert\geq\lvert V_{t}(p)\rvert-\ell(\Delta
d)^{2}-\lvert S\rvert\quad\text{for every $t\in[d]$.}$ (15)

This is because a variable $x_{j}$ belongs to $V_{t}(p)\setminus
V_{t}(r^{\prime})$ only if it belongs to or is adjacent to the at most
$\ell\Delta d$ restricted variables $\\{x_{i_{j}},x_{T_{j}}:j\in[\ell]\\}$ in
$G_{p}$, or it is one of the $\\{x_{i}:i\in S\\}$. In Lemma 30 below we prove
that for every fixed assignment to $x_{i_{j}},x_{T_{j}}:j\in[\ell]$, and any
$t\in[d]$, we have that

$\bigg{\lvert}\mathop{\bf
E\/}_{x_{R}}\Bigl{[}(-1)^{r^{\prime}(x_{R})}\Bigr{]}\bigg{\rvert}\leq\exp\left(-\frac{2^{-t}\lvert
V_{t}(r^{\prime})\rvert}{(\Delta d)^{4}}\right).$ (16)

Continuing from above, combining Equations 14, LABEL:, 15 and 16, we have

$\displaystyle\lvert\widehat{f}(S)\rvert$
$\displaystyle\leq(2\Delta)^{\ell}\Biggl{(}\prod_{j\in[\ell]}2^{-t_{j}}\Biggr{)}\cdot\min\left\\{\exp\left(-\frac{2^{-t}(\lvert
V_{t}(p)\rvert-\ell(\Delta d)^{2}-\lvert S\rvert)}{(\Delta
d)^{4}}\right):t\in[d]\right\\}$ $\displaystyle\leq O(1)^{\lvert
S\rvert}\cdot(2\Delta)^{\ell}\Biggl{(}\prod_{j\in[\ell]}2^{-t_{j}}\Biggr{)}\cdot\min\left\\{\exp\left(-\frac{2^{-t}(\lvert
V_{t}(p)\rvert)}{(\Delta d)^{4}}\right):t\in[d]\right\\}$
$\displaystyle=O(1)^{\lvert
S\rvert}\cdot(2\Delta)^{\ell}\Biggl{(}\prod_{j\in[\ell]}2^{-t_{j}}\min\left\\{\exp\left(-\frac{2^{-t}(\lvert
V_{t}(p)\rvert)}{\ell\cdot(\Delta d)^{4}}\right):t\in[d]\right\\}\Biggr{)}$
$\displaystyle=O(1)^{\lvert
S\rvert}\cdot(2\Delta)^{\ell}\prod_{j\in[\ell]}\left(2^{-t_{j}}\exp\left(-\frac{2^{-{t_{j}}}\lvert
V_{t_{j}}(p)\rvert}{\ell\cdot(\Delta d)^{4}}\right)\right),$

where second inequality is because $\exp\left(\frac{\ell(\Delta d)^{2}+\lvert
S\rvert}{(\Delta d)^{4}}\right)\leq e^{\ell+\lvert S\rvert}\leq O(1)^{\lvert
S\rvert}$ because $\ell\leq\lvert S\rvert$. This proves the lemma. ∎

We now prove Claims 29 and 30.

###### Proof of Claim 29.

We may assume $t_{j}\geq 2$ as otherwise the conclusion is trivial. Since
${i_{j}}\in V_{t_{j}}(p)$, recalling Equations 11 and 12, every monomial in
$p_{j}$ containing $x_{i_{j}}$ has degree at least $t_{j}$, and by collecting
these monomials, we can write

$\displaystyle s_{j}(x_{i_{j}},x_{T_{j}},x_{R})$
$\displaystyle=x_{i_{j}}+p_{j}(x_{i_{j}},x_{T_{j}})+\sum_{k\in S\cap
T_{j}}x_{k}+q_{j}(x_{T_{j}},x_{R})$
$\displaystyle=x_{i_{j}}(1+u_{j}(x_{T_{j}}))+v_{j}(x_{T_{j}},x_{R})$

for some polynomials $u_{j}$ and $v_{j}$, where every monomial in
$u_{j}(x_{T_{j}})$ has degree at least $t_{j}-1\geq 1$, and thus $u_{j}(0)=0$.
Now, if an outcome of $x_{T_{j}}$ is such that $u_{j}(x_{T_{j}})=0$, then the
expectation of $(-1)^{s_{j}}$ is zero because $v_{j}$ does not depend on
$x_{i_{j}}$ and $\mathop{\bf E\/}[(-1)^{x_{i_{j}}}]=0$. Hence we have that for
every outcome of $x_{R}$,

$\bigg{\lvert}\mathop{\bf
E\/}_{x_{i_{j}},x_{T_{j}}}\Bigl{[}(-1)^{s_{j}(x_{i_{j}},x_{T_{j}},x_{R})}\Bigr{]}\bigg{\rvert}\leq\mathop{\bf
E\/}_{x_{T_{j}}}\bigg{\lvert}\mathop{\bf
E\/}_{x_{i_{j}}}\Bigl{[}(-1)^{s_{j}(x_{i_{j}},x_{T_{j}},x_{R})}\Bigr{]}\bigg{\rvert}\leq\mathop{\bf
Pr\/}[u_{j}(x_{T_{j}})=1]\leq\Delta 2^{-(t_{j}-1)},\qed$

where the final inequality is by Lemma 28.

######  Lemma 30.

Let $q(x_{1},\ldots,x_{n})$ be a read-$\Delta$ degree-$d$ polynomial. For
every $t\in[d]$ we have

$\Big{\lvert}\mathop{\bf
E\/}\bigl{[}(-1)^{q}\bigr{]}\Big{\rvert}\leq\exp\left(-\frac{2^{-t}\lvert
V_{t}(q)\rvert}{(\Delta d)^{4}}\right).$

###### Proof.

We partition $V_{t}(q)$ according to $G_{q}$ using the following greedy
procedure:

  1. 1.

Set $W_{1}=[n]$ and $i=1$.

  2. 2.

Pick a monomial $x^{S_{i}}$ of degree exactly $t$ containing some variable
$x_{j}:j\in W_{i}\cap V_{t}(q)$.

  3. 3.

Let $T_{i}:=N_{=1}(S_{i})$, and set $W_{i+1}=W_{i}\setminus N_{\leq
3}(S_{i})$.

  4. 4.

Repeat steps 2 and 3 until we cannot pick such an $S_{\ell+1}$. Let
$R=[n]\setminus\bigcup_{i\in[\ell]}(S_{i}\cup T_{i})$ be the remaining
variables.

By construction, the pairwise distances between the $(S_{i}\cup T_{i})$’s are
at least $2$, so the variables $x_{S_{i}\cup T_{i}}$’s must only appear in
disjoint monomials. Since each time we remove at most $t\cdot(\Delta d)^{3}$
elements from $V_{t}(q)$, we have $\ell\geq\lvert V_{t}(q)\rvert/(t(\Delta
d)^{3})$.

We now partition the monomials in $q$. For each $i\in[\ell]$, let
$p_{i},q_{i}$ be two polynomials such that $p_{i}$ is composed of all
monomials in $q$ that contain a variable in $x_{S_{i}}$, and $q_{i}$ is
composed of all monomials in $q$ that contain a variable in $x_{T_{i}}$ but
none in $x_{S_{i}}$. Let $r$ be the polynomial composed of the remaining
monomials in $q$. We can write $q(x)$ as

$\sum_{i=1}^{\ell}\bigl{(}p_{i}(x_{S_{i}},x_{T_{i}})+q_{i}(x_{T_{i}},x_{R})\bigr{)}+r(x_{R}).$

By collecting the monomials containing $x^{S_{i}}$, we can write

$p_{i}(x_{S_{i}},x_{T_{i}})+q_{i}(x_{T_{i}},x_{R})=x^{S_{i}}(1+u_{i}(x_{T_{i}}))+v_{i}(x_{S_{i}},x_{T_{i}},x_{R}).$

for some polynomials $u_{i}$ and $v_{i}$, where (1) $u_{i}$ consists of the at
most $\Delta-1$ monomials in $p_{i}$ that contain $x^{S_{i}}$, and
$u_{i}(0)=0$, and (2) $x^{S_{i}}$ does not appear in any monomial in $v_{i}$.
Let $\delta:=\mathop{\bf Pr\/}[u_{i}(x_{T_{i}})=0]$. By Lemma 28 we have
$\delta\geq 1/\Delta$. Therefore, for every assignment to $x_{R}$ and every
$i\in[\ell]$,

$\displaystyle\mathop{\bf E\/}_{x_{T_{i}}}\bigg{\lvert}\mathop{\bf
E\/}_{x_{S_{i}}}\Bigl{[}(-1)^{p_{i}(x_{S_{i}},x_{T_{i}})+q_{i}(x_{T_{i}},x_{R})}\Bigr{]}\bigg{\rvert}$
$\displaystyle=(1-\delta)\bigg{\lvert}\mathop{\bf
E\/}_{x_{S_{i}}}\Bigl{[}(-1)^{v_{i}(x_{S_{i}},x_{T_{i}},x_{R})}\Bigr{]}\bigg{\rvert}+\delta\mathop{\bf
E\/}_{x_{T_{i}}:u_{i}(x_{T_{i}})=0}\left[\bigg{\lvert}\mathop{\bf
E\/}_{x_{S_{i}}}\Bigl{[}(-1)^{x^{S_{i}}+v_{i}(x_{S_{i}},x_{T_{i}},x_{R})}\Bigr{]}\bigg{\rvert}\right]$
$\displaystyle\leq(1-\delta)+\delta(1-2^{-t})$ $\displaystyle\leq
1-2^{-t}/\Delta,$

where the first inequality is because for any choice of $x_{R}$ and
$x_{T_{i}}$, the polynomial $x^{S_{i}}+v_{i}(x_{S_{i}},x_{T_{i}},x_{R})$ has
degree exactly $t$, and therefore its bias is at most $1-2^{-t}$. Also, for
every fixed outcome of $x_{R}$, the restricted polynomials
$p_{i}(x_{S_{i}},x_{T_{i}})+q_{i}(x_{T_{i}},x_{R})$ depend on disjoint
variables. Therefore,

$\bigg{\lvert}\mathop{\bf
E\/}_{x_{T_{i}},x_{S_{i}}:i\in[\ell]}\Bigl{[}(-1)^{q(x)}\Bigr{]}\bigg{\rvert}\leq\left(1-\frac{2^{-t}}{\Delta}\right)^{\ell}\leq\exp\left(-\frac{\ell\cdot
2^{-t}}{\Delta}\right)\leq\exp\left(-\frac{2^{-t}\lvert
V_{t}(q)\rvert}{(\Delta d)^{4}}\right),$

because $\ell\geq\lvert V_{t}(q)\rvert/(t\Delta^{3}d^{3})\geq\lvert
V_{t}(q)\rvert/(\Delta^{3}d^{4})$. ∎

##  6 $L_{1,k}$ bounds for disjoint compositions

In this section we give $L_{1,k}$ bounds on _disjoint compositions_ of
functions, which we define below.

Let $\mathcal{F}$ and $\mathcal{G}$ be two families consisting of functions
mapping $\\{-1,1\\}^{m}$ and $\\{-1,1\\}^{\ell}$ to $\\{-1,1\\}$ respectively.
Let $f\in\mathcal{F}$ and $g_{1},\ldots,g_{m}\in\mathcal{G}$. We define
$h\colon\\{-1,1\\}^{m\ell}\to\\{-1,1\\}$, the _disjoint composition_ of $f$
and $g_{1},\ldots,g_{m}$, to be

$h(x_{1,1},\ldots,x_{1,\ell},\ldots,x_{m,1},\ldots,x_{m,\ell}):=f(g_{1}(x_{1,1},\ldots,x_{1,\ell}),\ldots,g_{m}(x_{m,1},\ldots,x_{m,\ell})).$

######  Theorem 31 (Sharper version of Theorem 13).

Let $g_{1},\ldots,g_{m}\in\mathcal{G}$, and $f\in\mathcal{F}$, where
$\mathcal{G},\mathcal{F}$ are as above and $\mathcal{F}$ is closed under
restrictions. Suppose for every $1\leq k\leq K$,

  1. 1.

$L_{1,k}(f)\leq\frac{1-\lvert\mathop{\bf E\/}[f]\rvert}{2}\cdot
a_{\mathsf{out}}\cdot b_{\mathsf{out}}^{k}$ for every $f\in\mathcal{F}$, and

  2. 2.

$L_{1,k}(g)\leq\frac{1-\lvert\mathop{\bf E\/}[g]\rvert}{2}\cdot
a_{\mathsf{in}}\cdot b_{\mathsf{in}}^{k}$ for every $g\in\mathcal{G}$.

Then

$L_{1,K}(h)\leq\frac{1-\lvert\mathop{\bf E\/}[h]\rvert}{2}\cdot
a_{\mathsf{out}}\cdot
b_{\mathsf{in}}^{K}\cdot\frac{a_{\mathsf{in}}b_{\mathsf{out}}}{2}\left(1+\frac{a_{\mathsf{in}}b_{\mathsf{out}}}{2}\right)^{K-1}.$

In particular, when $a_{\mathsf{in}}b_{\mathsf{out}}\geq 2$ or $K=1$ we have
$L_{1,K}[h]\leq\frac{1-\lvert\mathop{\bf E\/}[h]\rvert}{2}\cdot
a_{\mathsf{out}}\cdot\frac{(a_{\mathsf{in}}b_{\mathsf{in}}b_{\mathsf{out}})^{K}}{2}$.

##### Proof idea.

Before proving Theorem 31, we briefly describe the main ideas of the proof.
For a subset $J\subseteq[m]$, let $\partial_{J}f$ denote the _$J$ -th
derivative of $f$_, which can be expressed as

$\partial_{J}f(x_{1},\ldots,x_{m}):=\sum_{T\supseteq
J}\widehat{f}(T)x^{T\setminus J}.$

Note that $\widehat{f}(J)=\partial_{J}f(\vec{0})$.

Let us begin by considering the task of bounding
$L_{1,1}(h)=\sum_{(i,j)\in[m]\times[\ell]}\lvert\widehat{h}\\{(i,j)\\}\rvert$.
Let $\beta=(\beta_{1},\ldots,\beta_{m})$, where $\beta_{i}:=\mathop{\bf
E\/}[g_{i}]$. Using the Fourier expansion of $f$, we have

$\widehat{h}\\{(i,j)\\}=\sum_{S\subseteq[m]}\widehat{f}(S)\mathop{\bf
E\/}\left[\prod_{k\in S}g_{k}(x_{k})\cdot x_{i,j}\right].$

If $S\not\ni i$, then the expectation is zero, because $\prod_{k\in
S}g_{k}(x_{k})$ and $x_{i,j}$ are independent and $\mathop{\bf
E\/}[x_{i,j}]=0$. So, we have

$\widehat{h}\\{(i,j)\\}=\sum_{S\ni
i}\widehat{f}(S)\beta^{S\setminus\\{i\\}}\cdot\widehat{g}_{i}(\\{j\\})=\partial_{i}f(\beta)\cdot\widehat{g}_{i}(\\{j\\}).$

If the functions $g_{i}$ are balanced, i.e. $\mathop{\bf E\/}[g_{i}]=0$ for
all $i$, then we would have $\beta=\vec{0}$, and

$\widehat{h}\\{(i,j)\\}=\partial_{i}f(\vec{0})\cdot\widehat{g}_{i}(\\{j\\})=\widehat{f}(\\{i\\})\widehat{g}_{i}(\\{j\\}).$

So in this case we have

$L_{1,1}(h)=\sum_{i\in[m],j\in[\ell]}\big{\lvert}\widehat{h}(\\{(i,j)\\})\big{\rvert}=\sum_{i\in[m]}\sum_{j\in[\ell]}\lvert\widehat{f}(\\{i\\})\widehat{g}_{i}(\\{j\\})\rvert=\sum_{i\in[m]}\lvert\widehat{f}(\\{i\\})\rvert\sum_{j\in[\ell]}\lvert\widehat{g}_{i}(\\{j\\})\rvert$

and we can apply our bounds on $L_{1,1}(\mathcal{F})$ and
$L_{1,1}(\mathcal{G})$ to $\sum_{i\in[m]}\widehat{f}\\{i\\}$ and
$\sum_{j\in[\ell]}\widehat{g}_{i}\\{j\\}$ respectively. Specializing to the
case $g_{1}=\cdots=g_{m}$, we have

######  Claim 32.

Suppose $g_{1}=g_{2}=\cdots=g_{m}=:g$ and $\mathop{\bf E\/}[g]=0$. Then
$L_{1,1}(h)=L_{1,1}(f)L_{1,1}(g)$.

In general the $g_{i}$’s may not all be the same and may not be balanced, and
so it seems unclear how we can apply our $L_{1,1}(\mathcal{F})$ bound on
$\sum_{i\in[m]}\partial_{i}f(\beta_{1},\ldots,\beta_{m})$ when
$\beta\neq\vec{0}$. To deal with this, in Claim 33 below we apply a clever
idea introduced in [CHHL19] that lets us relate $f(\beta)$ at a nonzero point
$\beta$ to the average of $f_{R_{\beta}}(\vec{0})$, where $f_{R_{\beta}}$ is
$f$ with some of its inputs fixed by a random restriction $R_{\beta}$. As
$\mathcal{F}$ is closed under restrictions, we have that
$f_{R_{\beta}}\in\mathcal{F}$ and we can apply the $L_{1,1}(\mathcal{F})$
bound on $\sum_{i}\partial_{i}f_{R_{\beta}}(\vec{0})$, which in turn gives a
bound on $\sum_{i\in[m]}\partial_{i}f(\beta_{1},\ldots,\beta_{m})$.

Bounding $L_{1,K}(h)$ for $K\geq 2$ is more complicated, as now each
$\widehat{h}(S)$ involves many $\widehat{f}(J)$ and $\widehat{g}_{i}(T)$’s,
where the sets $J$ and $T$ have different sizes. So one has to group the
coefficients carefully.

###  6.1 Useful notation

For a set $S\subseteq[m]\times[\ell]$, let $S|_{f}:=\\{i\in[m]:(i,j)\in
S\text{ for some }j\in[\ell]\\}$ be the “set of first coordinates” that occur
in $S$, and let $S|_{i}:=\\{j\in[\ell]:(i,j)\in S\\}$. Note that if $(i,j)\in
S$, then $i\in S|_{f}$ and $j\in S|_{i}$. Let $\beta$ denote the vector
$(\beta_{1},\ldots,\beta_{m})$, where $\beta_{i}:=\mathop{\bf E\/}[g_{i}]$ for
each $i\in[m]$. For a set $J=\\{i_{1},\ldots,i_{\lvert
J\rvert}\\}\subseteq[m]$ and $f=f(y_{1},\dots,y_{m})$, we write
$\partial_{J}f$ to denote $\frac{\partial^{\lvert J\rvert}f}{\partial
y_{i_{1}}\cdots\partial y_{i_{\lvert J\rvert}}}$. Since
$\partial_{J}y^{T}=\mathbbm{1}(T\supseteq J)y^{T\setminus J}$, by the
multilinearity of $f$ we have that

$\displaystyle\partial_{J}f(\beta)=\sum_{T\supseteq
J}\widehat{f}(T)\beta^{\,T\setminus J}.$ (17)

###  6.2 The random restriction $R_{\beta}$

Given $\beta\in[-1,1]^{m}$, let $R_{\beta}$ be the random restriction which is
the randomized function from $\\{-1,1\\}^{m}$ to $\\{-1,1\\}^{m}$ whose $i$-th
coordinate is (independently) defined by

$R_{\beta}(y)_{i}:=\begin{cases}\textnormal{sgn}(\beta_{i})&\text{with
probability $\lvert\beta_{i}\rvert$}\\\ y_{i}&\text{with probability
$1-\lvert\beta_{i}\rvert$.}\end{cases}$

Note that we have

$\mathop{\bf E\/}_{R_{\beta},y}[R_{\beta}(y)_{i}]=\mathop{\bf
E\/}_{R_{\beta}}[R_{\beta}(\vec{0})_{i}]=\beta_{i}.$

Define $f_{R_{\beta}}(y)$ to be the (randomized) function $f(R_{\beta}(y))$.
By the multilinearity of $f$ and independence of the $R_{\beta}(y)_{i}$ we
have

$\mathop{\bf E\/}_{R_{\beta},y}[f_{R_{\beta}}(y)]=\mathop{\bf
E\/}_{R_{\beta}}[f_{R_{\beta}}(\vec{0})]=f(\beta).$

The following claim relates the two derivatives $\partial_{S}f(\beta)$ and
$\partial_{S}f_{R_{\beta}}(\vec{0})=\widehat{f_{R_{\beta}}}(S)$.

######  Claim 33.

$\partial_{S}f(\beta)=\prod_{i\in
S}\frac{1}{1-\lvert\beta_{i}\rvert}\cdot\mathop{\bf
E\/}_{R_{\beta}}[\partial_{S}f_{R_{\beta}}(\vec{0})]=\prod_{i\in
S}\frac{1}{1-\lvert\beta_{i}\rvert}\cdot\mathop{\bf
E\/}_{R_{\beta}}[\widehat{f_{R_{\beta}}}(S)].$

###### Proof.

The second equality follows from 17. To prove the first one, it suffices to
show

$\partial_{\\{i\\}}f(\beta)=\frac{1}{1-\lvert\beta_{i}\rvert}\mathop{\bf
E\/}_{R_{\beta}}[\partial_{\\{i\\}}f_{R_{\beta}}(\vec{0})].$

The rest follows by a straightforward induction. By definition of derivatives,
and noting $\mathop{\bf
E\/}_{R_{\beta}}[R_{\beta}(\frac{1}{1-\lvert\beta_{i}\rvert}z\cdot
e_{i})_{j}]$ equal $\beta_{i}+z\cdot e_{i}$ if $i=j$ and $\beta_{j}$
otherwise,

$\displaystyle\frac{\partial f}{\partial y_{i}}(\beta)$
$\displaystyle=\lim_{z\to 0}\frac{f(\beta+z\cdot e_{i})-f(\beta)}{z}$
$\displaystyle=\mathop{\bf E\/}_{R_{\beta}}\left[\lim_{z\to
0}\frac{f_{R_{\beta}}\bigl{(}\frac{1}{1-\lvert\beta_{i}\rvert}\cdot z\cdot
e_{i}\bigr{)}-f_{R_{\beta}}(\vec{0})}{z}\right]$
$\displaystyle=\frac{1}{1-\lvert\beta_{i}\rvert}\mathop{\bf
E\/}_{R_{\beta}}\left[\frac{\partial f_{R_{\beta}}}{\partial
y_{i}}(\vec{0})\right].\qed$

We now use Claim 33 to express each coefficient of $h$ in terms of the
coefficients of $f$ and $g_{i}$.

######  Lemma 34.

For $S\subseteq[m]\times[\ell]$, we have $\widehat{h}(S)=\prod_{i\in
S|_{f}}\widehat{g}_{i}(S|_{i})\cdot\prod_{i\in
S|_{f}}\frac{1}{1-\lvert\beta_{i}\rvert}\cdot\mathop{\bf
E\/}_{R_{\beta}}[\widehat{f_{R_{\beta}}}(S|_{f})]$.

###### Proof.

For $S\subseteq[m]\times[\ell]$ and $T\subseteq[m]$, decompose $T$ into
$(T\cap S|_{f})\,\cup\,(T\setminus S|_{f})$ and $S|_{f}$ into $(T\cap
S|_{f})\,\cup\,(S|_{f}\setminus T)$. Expanding $h$ using the Fourier expansion
of $f$, by the definitions of $S|_{f}$ and $S|_{i}$, we have

$\displaystyle\widehat{h}(S)$
$\displaystyle=\sum_{T\subseteq[m]}\widehat{f}(T)\mathop{\bf
E\/}_{x}\left[\prod_{i\in T}g_{i}(x)\cdot x^{S}\right]$
$\displaystyle=\sum_{T\subseteq[m]}\widehat{f}(T)\left(\Biggl{(}\prod_{i\in
S|_{f}\setminus T}\mathop{\bf E\/}\Bigl{[}\prod_{j\in
S|_{i}}x_{i,j}\Bigr{]}\Biggr{)}\cdot\Biggl{(}\prod_{i\in T\cap
S|_{f}}\mathop{\bf E\/}\Bigl{[}g_{i}(x)\prod_{j\in
S|_{i}}x_{i,j}\Bigr{]}\Biggr{)}\cdot\Biggl{(}\prod_{i\in T\setminus
S|_{f}}\mathop{\bf E\/}[g_{i}(x)]\Biggr{)}\right).$

When $S|_{f}\not\subseteq T$, we have $S|_{f}\setminus T\neq\varnothing$ and
thus $\prod_{i\in S|_{f}\setminus T}\prod_{j\in S|_{i}}\mathop{\bf
E\/}[x_{i,j}]=0$. Hence,

$\prod_{i\in S|_{f}\setminus T}\mathop{\bf E\/}\Bigl{[}\prod_{j\in
S|_{i}}x_{i,j}\Bigr{]}=\mathbbm{1}(S|_{f}\subseteq T).$

Note that $\mathop{\bf E\/}[g_{i}(x)\prod_{j\in S}x_{i,j}]=\widehat{g}_{i}(S)$
for every $S\subseteq[\ell]$. Using $\mathop{\bf E\/}[g_{i}(x)]=\beta_{i}$,
Equation 17 and Claim 33, we have

$\displaystyle\widehat{h}(S)$ $\displaystyle=\sum_{T\subseteq[m]:T\supseteq
S|_{f}}\widehat{f}(T)\prod_{i\in S|_{f}}\widehat{g}_{i}(S|_{i})\prod_{i\in
T\setminus S|_{f}}\mathop{\bf E\/}[g_{i}(x)]$ $\displaystyle=\prod_{i\in
S|_{f}}\widehat{g}_{i}(S|_{i})\cdot\Biggl{(}\sum_{T\subseteq[m]:T\supseteq
S|_{f}}\widehat{f}(T)\prod_{i\in T\setminus S|_{f}}\beta_{i}\Biggr{)}$
($\mathop{\bf E\/}[g_{i}(x)]=\beta_{i}$) $\displaystyle=\prod_{i\in
S|_{f}}\widehat{g}_{i}(S|_{i})\cdot\partial_{S|_{f}}f(\beta_{1},\ldots,\beta_{m})$
(Equation 17) $\displaystyle=\prod_{i\in
S|_{f}}\widehat{g}_{i}(S|_{i})\cdot\prod_{i\in
S|_{f}}\frac{1}{1-\lvert\beta_{i}\rvert}\cdot\mathop{\bf
E\/}_{R_{\beta}}\bigl{[}\widehat{f_{R_{\beta}}}(S|_{f})\bigr{]}.$
$\displaystyle\text{(\lx@cref{creftypecap~refnum}{claim:derivatives})}\qed$

###  6.3 Proof of Theorem 31

By Lemma 34, $L_{1,K}(h)$ is equal to

$\sum_{S\subseteq[m]\times[\ell]:\lvert
S\rvert=K}\lvert\widehat{h}(S)\rvert=\sum_{S\subseteq[m]\times[\ell]:\lvert
S\rvert=K}\biggl{|}\prod_{i\in S|_{f}}\widehat{g}_{i}(S|_{i})\cdot\prod_{i\in
S|_{f}}\frac{1}{1-\lvert\beta_{i}\rvert}\cdot\mathop{\bf
E\/}_{R_{\beta}}[\widehat{f_{R_{\beta}}}(S|_{f})]\biggr{|}.$

We enumerate all the subsets $S\subseteq[m]\times[\ell]$ of size $K$ in the
following order: For every $\lvert J\rvert=k\in[K]$ out of the $m$ blocks of
$\ell$ coordinates, we enumerate all possible combinations of the (disjoint)
nonempty subsets $\\{S_{i}:i\in J\\}$ in those $k$ blocks whose sizes sum to
$K$. Rewriting the summation above in this order, we obtain

$\displaystyle\sum_{S\subseteq[m]\times[\ell]:\lvert
S\rvert=K}\lvert\widehat{h}(S)\rvert$
$\displaystyle=\sum_{k=1}^{K}\sum_{\begin{subarray}{c}J\subseteq[m]\\\ \lvert
J\rvert=k\end{subarray}}\sum_{\begin{subarray}{c}w\subseteq[\ell]^{J}\\\
\sum_{i\in J}w_{i}=K\end{subarray}}\sum_{\begin{subarray}{c}\\{S_{i}\\}_{i\in
J}\subseteq[\ell]^{J}:\\\ \forall i\in J:\lvert
S_{i}\rvert=w_{i}\end{subarray}}\Bigg{\lvert}\prod_{i\in
J}\widehat{g}_{i}(S_{i})\prod_{i\in
J}\frac{1}{1-\lvert\beta_{i}\rvert}\mathop{\bf
E\/}_{R_{\beta}}\bigl{[}\widehat{f_{R_{\beta}}}(J)\bigr{]}\Bigg{\rvert}$
$\displaystyle\leq\sum_{k=1}^{K}\sum_{\begin{subarray}{c}J\subseteq[m]\\\
\lvert
J\rvert=k\end{subarray}}\sum_{\begin{subarray}{c}w\subseteq[\ell]^{J}\\\
\sum_{i\in J}w_{i}=K\end{subarray}}\sum_{\begin{subarray}{c}\\{S_{i}\\}_{i\in
J}\subseteq[\ell]^{J}:\\\ \forall i\in J:\lvert
S_{i}\rvert=w_{i}\end{subarray}}\prod_{i\in
J}\big{\lvert}\widehat{g}_{i}(S_{i})\big{\rvert}\prod_{i\in
J}\frac{1}{1-\lvert\beta_{i}\rvert}\Big{\lvert}\mathop{\bf
E\/}_{R_{\beta}}\bigl{[}\widehat{f_{R_{\beta}}}(J)\bigr{]}\Big{\rvert}.$ (18)

Since $L_{1,w_{i}}(g_{i})\leq\frac{1-\lvert\beta_{i}\rvert}{2}\cdot
a_{\mathsf{in}}\cdot b_{\mathsf{in}}^{w_{i}}$, for every $\\{w_{i}\\}_{i\in
J}$ such that $\sum_{i\in J}w_{i}=K$, we have

$\sum_{\begin{subarray}{c}\\{S_{i}\\}_{i\in J}\subseteq[\ell]^{J}:\\\ \forall
i\in J:\lvert S_{i}\rvert=w_{i}\end{subarray}}\prod_{i\in
J}\lvert\widehat{g}_{i}(S_{i})\rvert=\prod_{i\in
J}L_{1,w_{i}}(g_{i})\leq\prod_{i\in
J}\Bigl{(}\frac{1-\lvert\beta_{i}\rvert}{2}a_{\mathsf{in}}b_{\mathsf{in}}^{w_{i}}\Bigr{)}=b_{\mathsf{in}}^{K}a_{\mathsf{in}}^{\lvert
J\rvert}\prod_{i\in J}\frac{1-\lvert\beta_{i}\rvert}{2}.$

Plugging the above into 18, we get that

$\displaystyle\sum_{S\subseteq[m]\times[\ell]:\lvert
S\rvert=K}\lvert\widehat{h}(S)\rvert$ $\displaystyle\leq
b_{\mathsf{in}}^{K}\sum_{{k}=1}^{K}a_{\mathsf{in}}^{k}\sum_{\begin{subarray}{c}J\subseteq[m]\\\
\lvert
J\rvert={k}\end{subarray}}\sum_{\begin{subarray}{c}w\subseteq[\ell]^{J}\\\
\sum_{i\in J}w_{i}=K\end{subarray}}\prod_{i\in
J}\left(\frac{1-\lvert\beta_{i}\rvert}{2}\cdot\frac{1}{1-\lvert\beta_{i}\rvert}\cdot\Big{\lvert}\mathop{\bf
E\/}_{R_{\beta}}\bigl{[}\widehat{f_{R_{\beta}}}(J)\bigr{]}\Big{\rvert}\right)$
$\displaystyle=b_{\mathsf{in}}^{K}\sum_{{k}=1}^{K}\left(\frac{a_{\mathsf{in}}}{2}\right)^{k}\sum_{\begin{subarray}{c}J\subseteq[m]\\\
\lvert J\rvert={k}\end{subarray}}\Big{\lvert}\mathop{\bf
E\/}_{R_{\beta}}\bigl{[}\widehat{f_{R_{\beta}}}(J)\bigr{]}\Big{\rvert}\sum_{\begin{subarray}{c}w\subseteq[\ell]^{J}\\\
\sum_{i\in J}w_{i}=K\end{subarray}}1$ $\displaystyle\leq
b_{\mathsf{in}}^{K}\sum_{{k}=1}^{K}\left(\frac{a_{\mathsf{in}}}{2}\right)^{k}\binom{K-1}{k-1}\sum_{\begin{subarray}{c}J\subseteq[m]\\\
\lvert J\rvert={k}\end{subarray}}\Big{\lvert}\mathop{\bf
E\/}_{R_{\beta}}\bigl{[}\widehat{f_{R_{\beta}}}(J)\bigr{]}\Big{\rvert},$ (19)

where the last inequality is because for every subset $J\subseteq[m]$, the set
$\\{w\subseteq[\ell]^{J}:\sum_{i\in J}w_{i}=K\\}$ has size at most
$\binom{K-1}{\lvert J\rvert-1}$. We now bound $\lvert\mathop{\bf
E\/}_{R_{\beta}}[\widehat{f_{R_{\beta}}}(J)]\rvert$. Since for every
restriction $R_{\beta}$, we have $f_{R_{\beta}}\in\mathcal{F}$ (by the
assumption that $\mathcal{F}$ is closed under restrictions), it follows that

$L_{1,{k}}(f_{R_{\beta}})\leq\frac{1-\lvert\mathop{\bf
E\/}_{y}[f_{R_{\beta}}(y)]\rvert}{2}a_{\mathsf{out}}b_{\mathsf{out}}^{k}\leq\frac{1-\mathop{\bf
E\/}_{y}[f_{R_{\beta}}(y)]}{2}a_{\mathsf{out}}b_{\mathsf{out}}^{k}.$

So

$\displaystyle\sum_{J\subseteq[m],\lvert J\rvert={k}}\Big{\lvert}\mathop{\bf
E\/}_{R_{\beta}}\bigl{[}\widehat{f_{R_{\beta}}}(J)\bigr{]}\Big{\rvert}$
$\displaystyle\leq\mathop{\bf E\/}_{R_{\beta}}[L_{1,{k}}(f_{R_{\beta}})]$
$\displaystyle\leq\frac{1-\mathop{\bf
E\/}_{R_{\beta},y}[f_{R_{\beta}}(y)]}{2}a_{\mathsf{out}}b_{\mathsf{out}}^{k}$
$\displaystyle=\frac{1-\mathop{\bf
E\/}[h]}{2}a_{\mathsf{out}}b_{\mathsf{out}}^{k}.$

Continuing from 19, we get

$\displaystyle\sum_{S\subseteq[m]\times[\ell]:\lvert
S\rvert=K}\lvert\widehat{h}(S)\rvert$ $\displaystyle\leq\frac{1-\mathop{\bf
E\/}[h]}{2}\cdot
b_{\mathsf{in}}^{K}\cdot\sum_{k=1}^{K}\left(\frac{a_{\mathsf{in}}}{2}\right)^{k}\cdot\binom{K-1}{k-1}\cdot
a_{\mathsf{out}}b_{\mathsf{out}}^{k}$ $\displaystyle=\frac{1-\mathop{\bf
E\/}[h]}{2}\cdot a_{\mathsf{out}}\cdot
b_{\mathsf{in}}^{K}\cdot\frac{a_{\mathsf{in}}b_{\mathsf{out}}}{2}\left(1+\frac{a_{\mathsf{in}}b_{\mathsf{out}}}{2}\right)^{K-1}$

where the last step used the binomial theorem. Applying the same argument to
$-h$ lets us replace $\frac{1-\mathop{\bf E\/}[h]}{2}$ with
$\frac{1-\lvert\mathop{\bf E\/}[h]\rvert}{2}$, concluding the proof of Theorem
31. ∎

###  6.4 Bounding $L_{1,1}(p)$ for balanced polynomials

We give a quick application of Claim 32 to show that $L_{1,1}(p)\leq d$ for
balanced degree-$d$ polynomials. (Note that [CHLT19] showed that
$L_{1,1}(p)\leq 4d$ for general degree-$d$ polynomials.)

######  Claim 35.

For every degree-$d$ polynomial $p\colon\\{0,1\\}^{n}\to\\{0,1\\}$ with
$\mathop{\bf E\/}[p]=1/2$, we have $L_{1,1}(p)\leq d$.

###### Proof.

Suppose not, and suppose that there exists an $\epsilon>0$ such that
$L_{1,1}(p)=(1+\epsilon)d$ for some degree-$d$ balanced polynomial $p$ on $n$
variables. Consider the composition $p^{\prime}$ on disjoint sets of variables
with the inner functions $g_{1}=g_{2}=\dots g_{n}$ and the outer function all
equal to $p$. Note that $p^{\prime}$ is a balanced degree $d^{2}$ polynomial
with $L_{1,1}(p^{\prime})=(1+\epsilon)^{2}d^{2}$.

We can repeat this iteratively by replacing $p$ in $p^{\prime}$ in the
composition. After $k$ repetitions, we get a polynomial $q$ of degree
$d^{2^{k}}$ that has $L_{1,1}(q)=(1+\epsilon)^{2^{k}}d^{2^{k}}$. For large
enough $k$ this is greater than $4d^{2^{k}}$, but this contradicts the $4d$
upper bound of [CHLT19], a contradiction. ∎

### Acknowledgements

We thank Shivam Nadimpalli for stimulating discussions at the early stage of
the project. J.B. is supported by a Junior Fellowship from the Simons Society
of Fellows. P.I. is supported by NSF awards CCF-1813930 and CCF-2114116. Y.J.
is supported by NSF IIS-1838154, NSF CCF-1703925, NSF CCF-1814873 and NSF
CCF-1563155. C.H.L. is supported by the Croucher Foundation and the Simons
Collaboration on Algorithms and Geometry. R.A.S. is supported by NSF grants
CCF-1814873, IIS-1838154, CCF-1563155, and by the Simons Collaboration on
Algorithms and Geometry. E.V. is supported by NSF awards CCF-1813930 and
CCF-2114116.

## References

  * [BGL06] Nayantara Bhatnagar, Parikshit Gopalan, and Richard J. Lipton.  Symmetric polynomials over ${\mathbb{Z}}_{m}$ and simultaneous communication protocols.  J. Comput. System Sci., 72(2):252–285, 2006.
  * [BHL12] Ido Ben-Eliezer, Rani Hod, and Shachar Lovett.  Random low-degree polynomials are hard to approximate.  Comput. Complexity, 21(1):63–81, 2012.
  * [BHLV19] Ravi Boppana, Johan Håstad, Chin Ho Lee, and Emanuele Viola.  Bounded independence versus symmetric tests.  ACM Trans. Comput. Theory, 11(4):Art. 21, 27, 2019.
  * [BS21] Nikhil Bansal and Makrand Sinha.  K-forrelation optimally separates quantum and classical query complexity.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, New York, NY, USA, 2021.
  * [BTW15] Eric Blais, Li-Yang Tan, and Andrew Wan.  An inequality for the fourier spectrum of parity decision trees, 2015\.
  * [BV10] Andrej Bogdanov and Emanuele Viola.  Pseudorandom bits for polynomials.  SIAM J. Comput., 39(6):2464–2486, 2010.
  * [CGL+20] Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, and Abhishek Shetty.  Fractional Pseudorandom Generators from Any Fourier Level, 2020.
  * [CHHL19] Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett.  Pseudorandom generators from polarizing random walks.  Theory Comput., 15:Paper No. 10, 26, 2019.
  * [CHLT19] Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, and Avishay Tal.  Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates.  In 10th Innovations in Theoretical Computer Science, volume 124. 2019.
  * [CHRT18] Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, and Avishay Tal.  Improved pseudorandomness for unordered branching programs through local monotonicity.  In STOC’18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 363–375. ACM, New York, 2018.
  * [CLW20] Lijie Chen, Xin Lyu, and R. Ryan Williams.  Almost-everywhere circuit lower bounds from non-trivial derandomization.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1–12, 2020.
  * [CMM+20] Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, and Swagato Sanyal.  Tight chang’s-lemma-type bounds for boolean functions.  CoRR, abs/2012.02335, 2020.
  * [CPT20] Gil Cohen, Noam Peri, and Amnon Ta-Shma.  Expander random walks: A fourier-analytic approach.  Electron. Colloquium Comput. Complex., 27:163, 2020.
  * [DHH20] Dean Doron, Pooya Hatami, and William M. Hoza.  Log-seed pseudorandom generators via iterated restrictions.  In 35th Computational Complexity Conference, volume 169. 2020\.
  * [FSUV13] Bill Fefferman, Ronen Shaltiel, Christopher Umans, and Emanuele Viola.  On beating the hybrid argument.  Theory Comput., 9:809–843, 2013.
  * [GKV17] Frederic Green, Daniel Kreymer, and Emanuele Viola.  Block-symmetric polynomials correlate with parity better than symmetric.  Comput. Complexity, 26(2):323–364, 2017.
  * [GRT21] Uma Girish, Ran Raz, and Avishay Tal.  Quantum Versus Randomized Communication Complexity, with Efficient Players.  In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185, 2021.
  * [GRZ20] Uma Girish, Ran Raz, and Wei Zhan.  Lower bounds for XOR of forrelations, 2020.
  * [GSTW16] Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, and Avi Wigderson.  Degree and sensitivity: tails of two distributions.  Electron. Colloquium Comput. Complex., 23:69, 2016.
  * [GT09] Ben Green and Terence Tao.  The distribution of polynomials over finite fields, with applications to the Gowers norms.  Contrib. Discrete Math., 4(2):1–36, 2009.
  * [GTW21] Uma Girish, Avishay Tal, and Kewen Wu.  Fourier Growth of Parity Decision Trees.  In Valentine Kabanets, editor, 36th Computational Complexity Conference (CCC 2021), volume 200, 2021.
  * [KL93] Marek Karpinski and Michael Luby.  Approximating the number of zeroes of a GF[2] polynomial.  Journal of Algorithms, 14(2):280–287, 1993.
  * [Lee19] Chin Ho Lee.  Fourier bounds and pseudorandom generators for product tests.  In 34th Computational Complexity Conference, volume 137. 2019\.
  * [LMS11] Shachar Lovett, Roy Meshulam, and Alex Samorodnitsky.  Inverse conjecture for the Gowers norm is false.  Theory Comput., 7:131–145, 2011.
  * [Lov09] Shachar Lovett.  Unconditional pseudorandom generators for low-degree polynomials.  Theory Comput., 5:69–82, 2009.
  * [LV20] Chin Ho Lee and Emanuele Viola.  More on bounded independence plus noise: pseudorandom generators for read-once polynomials.  Theory Comput., 16:Paper No. 7, 50, 2020.
  * [Man95] Yishay Mansour.  An $O(n^{\log\log n})$ learning algorithm for DNF under the uniform distribution.  volume 50, pages 543–550. 1995.  Fifth Annual Workshop on Computational Learning Theory (COLT) (Pittsburgh, PA, 1992).
  * [MRT19] Raghu Meka, Omer Reingold, and Avishay Tal.  Pseudorandom generators for width-3 branching programs.  In STOC’19—Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 626–637. ACM, New York, 2019.
  * [Nis92] Noam Nisan.  Pseudorandom generators for space-bounded computation.  Combinatorica, 12(4):449–461, 1992.
  * [O’D14] Ryan O’Donnell.  Analysis of Boolean Functions.  Cambridge University Press, 2014.
  * [OLBC10] Frank WJ Olver, Daniel W Lozier, Ronald F Boisvert, and Charles W Clark.  NIST handbook of mathematical functions hardback and CD-ROM.  Cambridge university press, 2010.
  * [OS07] Ryan O’Donnell and Rocco A. Servedio.  Learning monotone decision trees in polynomial time.  SIAM J. Comput., 37(3):827–844, 2007.
  * [Raz87] Alexander A. Razborov.  Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function.  Mat. Zametki, 41(4):598–607, 623, 1987.
  * [RSV13] Omer Reingold, Thomas Steinke, and Salil P. Vadhan.  Pseudorandomness for regular branching programs via fourier analysis.  In RANDOM 2013, volume 8096 of Lecture Notes in Computer Science, pages 655–670, 2013.
  * [RT19] Ran Raz and Avishay Tal.  Oracle separation of BQP and PH.  In STOC’19—Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 13–23. ACM, New York, 2019.
  * [Smo87] Roman Smolensky.  Algebraic methods in the theory of lower bounds for boolean circuit complexity.  In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC ’87, page 77–82, New York, NY, USA, 1987. Association for Computing Machinery.
  * [SSW20] Alexander A. Sherstov, Andrey A. Storozhenko, and Pei Wu.  An Optimal Separation of Randomized and Quantum Query Complexity, 2020\.
  * [ST19a] Rocco A. Servedio and Li-Yang Tan.  Improved pseudorandom generators from pseudorandom multi-switching lemmas.  In Approximation, randomization, and combinatorial optimization. Algorithms and techniques, volume 145. 2019.
  * [ST19b] Rocco A. Servedio and Li-Yang Tan.  Pseudorandomness for read-$k$ DNF formulas.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 621–638. SIAM, Philadelphia, PA, 2019.
  * [Tal17] Avishay Tal.  Tight bounds on the Fourier spectrum of ${\bf{AC}}^{\bf 0}$.  In 32nd Computational Complexity Conference, volume 79. 2017\.
  * [Tal20] Avishay Tal.  Towards optimal separations between quantum and randomized query complexities.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 228–239, 2020.
  * [Vio09a] Emanuele Viola.  On the power of small-depth computation.  Foundations and Trends in Theoretical Computer Science, 5(1):1–72, 2009.
  * [Vio09b] Emanuele Viola.  The sum of $d$ small-bias generators fools polynomials of degree $d$.  Comput. Complexity, 18(2):209–217, 2009.
  * [Vio17] Emanuele Viola.  Challenges in computational lower bounds.  SIGACT News, Open Problems Column, 48(1), 2017.
  * [Vio20] Emanuele Viola.  Fourier conjectures, correlation bounds, and majority.  Electron. Colloquium Comput. Complex., 27:175, 2020.
  * [Vio21] Emanuele Viola.  New lower bounds for probabilistic degree and AC0 with parity gates.  Theory of Computing, 2021.  Available at http://www.ccs.neu.edu/home/viola/.
  * [Wik21] Wikipedia contributors.  Kravchuk polynomials.  https://en.wikipedia.org/wiki/Kravchuk_polynomials, accessed April 25, 2021.

##  Appendix A Reduction to bound without acceptance probability

In this section, we show that given any $L_{1,k}$ Fourier norm bound on a
class of functions that is closed under XOR on disjoint variables, such a
bound can be automatically “upgraded” to a refined bound that depends on the
acceptance probability:

######  Lemma 36.

Let $\mathcal{F}$ be a class of $\\{-1,1\\}$-valued functions such that for
every $f\in\mathcal{F}$, the XOR of disjoint copies of $f$ (over disjoint sets
of variables) also belongs to $\mathcal{F}$. If $L_{1,k}(\mathcal{F})\leq
b^{k}$, then for every $f\in\mathcal{F}$ it holds that $L_{1,k}(f)\leq
2e\cdot\frac{1-\lvert\mathop{\bf E\/}[f]\rvert}{2}\cdot b^{k}$.

###### Proof.

Suppose not, and let $f\in\mathcal{F}$ be such that
$L_{1,k}(f)>2e\cdot\frac{1-\lvert\mathop{\bf E\/}[f]\rvert}{2}\cdot b^{k}$. We
first observe that since $L_{1,k}(\mathcal{F})\leq b^{k}$, it must be the case
that $1-\lvert\mathop{\bf E\/}[f]\rvert\leq 1/e.$ Let
$\alpha:=\frac{1-\lvert\mathop{\bf E\/}[f]\rvert}{2}\in[0,\frac{1}{{2e}}]$ so
that $\lvert\mathop{\bf E\/}[f]\rvert=1-2\alpha\geq 1-1/e$. Let $f^{\oplus t}$
be the XOR of $t$ disjoint copies of $f$ on $tn$ variables, where the integer
$t$ is to be determined below. By our assumption, we have $f^{\oplus
t}\in\mathcal{F}$ and thus

$\displaystyle L_{1,k}(f^{\oplus t})$ $\displaystyle\geq\binom{t}{1}\cdot
L_{1,0}(f)^{t-1}\cdot L_{1,k}(f)$ (by disjointness)
$\displaystyle=t\cdot(1-2\alpha)^{t-1}\cdot L_{1,k}(f)$
($L_{1,0}(f)=\mathop{\bf E\/}[f]$) $\displaystyle>t\cdot(1-2\alpha)^{t-1}\cdot
2e\cdot\alpha\cdot b^{k}=:\Lambda(t).$

We note that if $\alpha=0$ then $\lvert\mathop{\bf E\/}[f]\rvert=1$, so all
the Fourier weight of $f$ is on the constant coefficient, and hence the
claimed inequality holds trivially. So we subsequently assume that
$0<\alpha\leq\frac{1}{2e}$. Let $t^{*}:=\frac{1}{-\ln(1-2\alpha)}>0$. It is
easy to verify that $\Lambda(t)$ is increasing when $t\leq t^{*}$, and is
decreasing when $t\geq t^{*}$.

We choose $t=\lceil t^{*}\rceil$. Since
$\alpha\leq\frac{1}{2e}<\frac{e-1}{2e}\approx 0.3161$, we have $t^{*}>1$ and
thus

$\displaystyle L_{1,k}(f^{\oplus t})>\Lambda(\lceil
t^{*}\rceil)\geq\Lambda(t^{*}+1)$
$\displaystyle=\left(\frac{1}{-\ln(1-2\alpha)}+1\right)\cdot(1-2\alpha)^{\frac{1}{-\ln(1-2\alpha)}}\cdot
2e\cdot\alpha\cdot b^{k}$
$\displaystyle=\left(\frac{2\alpha}{-\ln(1-2\alpha)}+2\alpha\right)\cdot
b^{k}\geq b^{k},$

where the last inequality holds for every $\alpha\in(0,\frac{e-1}{2e}]$ and
can be checked via elementary calculations. This contradicts
$L_{1,k}(\mathcal{F})\leq b^{k}$, and the lemma is proved. ∎