Srikanth Srinivasansrikanth@cs.au.dk[https://orcid.org/0000-0001-6491-124X]
Department of Computer Science, Aarhus University, Denmark Work done while at
the Department of Mathematics, Indian Institute of Technology Bombay, Mumbai,
India. Supported by MATRICS grant MTR/2017/000958 awarded by SERB, Government
of India. A preliminary version of this paper appeared at STOC 2020. 2023 5
Feb 28, 2022 Oct 21, 2022 Dec 20, 2022 Feb 24, 2023 Polynomial approximation,
Boolean functions, Probabilistic degree, Coin Problem 10.46298/theoretics.23.5
S. Srinivasan A Robust Version of Hegedűs’s Lemma

# A Robust Version of Hegedűs’s Lemma, with Applications

###### Abstract

Hegedűs’s lemma is the following combinatorial statement regarding polynomials
over finite fields. Over a field $\mathbb{F}$ of characteristic $p>0$ and for
$q$ a power of $p$, the lemma says that any multilinear polynomial
$P\in\mathbb{F}[x_{1},\ldots,x_{n}]$ of degree less than $q$ that vanishes at
all points in $\\{0,1\\}^{n}$ of some fixed Hamming weight $k\in[q,n-q]$ must
also vanish at all points in $\\{0,1\\}^{n}$ of weight $k+q$. This lemma was
used by Hegedűs (2009) to give a solution to _Galvin’s problem_ , an extremal
problem about set systems; by Alon, Kumar and Volk (2018) to improve the best-
known multilinear circuit lower bounds; and by Hrubeš, Ramamoorthy, Rao and
Yehudayoff (2019) to prove optimal lower bounds against depth-$2$ threshold
circuits for computing some symmetric functions.

In this paper, we formulate a robust version of Hegedűs’s lemma. Informally,
this version says that if a polynomial of degree $o(q)$ vanishes at most
points of weight $k$, then it vanishes at many points of weight $k+q$. We
prove this lemma and give the following three different applications.

  * •

Degree lower bounds for the coin problem: The _$\delta$ -Coin Problem_ is the
problem of distinguishing between a coin that is heads with probability
$((1/2)+\delta)$ and a coin that is heads with probability $1/2$. We show that
over a field of positive (fixed) characteristic, any polynomial that solves
the $\delta$-coin problem with error $\varepsilon$ must have degree
$\Omega(\frac{1}{\delta}\log(1/\varepsilon)),$ which is tight up to constant
factors.

  * •

Probabilistic degree lower bounds: The _Probabilistic degree_ of a Boolean
function is the minimum $d$ such that there is a random polynomial of degree
$d$ that agrees with the function at each point with high probability. We give
tight lower bounds on the probabilistic degree of _every_ symmetric Boolean
function over positive (fixed) characteristic. As far as we know, this was not
known even for some very simple functions such as unweighted Exact Threshold
functions, and constant error.

  * •

A robust version of the combinatorial result of Hegedűs (2009) mentioned
above.

##  1 Introduction

The Polynomial Method is a technique of great utility in both Theoretical
Computer Science and Combinatorics. The idea of associating polynomials with
various combinatorial objects and then using algebraic or geometric techniques
to analyze them has proven useful in many settings including, but not limited
to, Computational Complexity (Circuit lower bounds [38, 41, 8, 52],
Pseudorandom generators [11]), Algorithm design (Learning Algorithms [32, 28,
27], Satisfiability algorithms [52, 51], Combinatorial algorithms [49, 1, 4]),
and Extremal Combinatorics [21, 16, 18].

The engine that drives the proofs of many of these results is our
understanding of combinatorial and algebraic properties of polynomials. In
this paper, we investigate another such naturally stated property of
polynomials defined over the Boolean cube $\\{0,1\\}^{n}$ and strengthen known
results in this direction. We then apply this result to sharpen known results
in theoretical computer science and combinatorics.

The question we address is related to how well low-degree polynomials can
‘distinguish’ between different layers of the Boolean cube $\\{0,1\\}^{n}.$
For $m\in\\{0,\ldots,n\\}$, let $\\{0,1\\}^{n}_{m}$ be the elements of
$\\{0,1\\}^{n}$ of Hamming weight exactly $m$. As a first approximation, let
us say that a polynomial $P\in\mathbb{F}[x_{1},\ldots,x_{n}]$ (here
$\mathbb{F}$ is some field) distinguishes between level sets
$\\{0,1\\}^{n}_{k}$ and $\\{0,1\\}^{n}_{K}$ if it vanishes at all points in
the former set and at no point of the latter. Note that the ability of low-
degree polynomials to do this depends on the properties of the underlying
field $\mathbb{F}$: when $\mathbb{F}=\mathbb{Q}$ (or any field of
characteristic $0$), the simple polynomial
$\left(\sum_{i=1}^{n}x_{i}\right)-k$ does the job. However, if the field
$\mathbb{F}$ has positive characteristic $p$ and more specifically if $K-k$ is
divisible by $p$, then this simple polynomial no longer works and the answer
is not so clear.

In this setting, a classical theorem of Lucas tells us that if $q$ is the
largest power of $p$ dividing $K-k$, then there is a polynomial of degree $q$
that distinguishes between $\\{0,1\\}^{n}_{k}$ and $\\{0,1\\}^{n}_{K}.$ A very
interesting lemma of Hegedűs [23] shows that this is tight even if we only
require $P$ to be non-zero at _some_ point of $\\{0,1\\}^{n}_{K}.$ More
precisely, Hegedűs’s lemma shows the following.111The lemma is usually stated
[23, 5, 25] for a more restricted choice of parameters. However, the known
proofs extend to yield the stronger statement given here. A proof of a more
general statement can be found in [44, Theorem 1.5].

######  Lemma 1.1 (Hegedűs’s lemma).

Let $\mathbb{F}$ be a field of characteristic $p>0$. Fix any positive integers
$n,k,q$ such that $k\in[q,n-q],$ and $q$ a power of $p$. If
$P\in\mathbb{F}[x_{1},\ldots,x_{n}]$ is any polynomial that vanishes at _all_
$a\in\\{0,1\\}^{n}_{k}$ but does not vanish at _some_
$b\in\\{0,1\\}^{n}_{k+q}$, then $\deg(P)\geq q.$

This lemma was first proved in [23] using Gröbner basis techniques. An
elementary proof of this was recently given by the author and independently by
Alon (see [25]) using the Combinatorial Nullstellensatz.

Hegedűs’s lemma has been used to resolve various questions in both
combinatorics and theoretical computer science.

  * •

Hegedűs used this lemma to give an alternate solution to a problem of Galvin,
which is stated as follows. Given a positive integer $n$ divisible by $4$,
what is the smallest size $m=m(n)$ of a family $\mathcal{F}$ of $(n/2)$-sized
subsets of $[n]$ such that for any $S\subseteq[n]$ of size $n/2$, there is a
$T\in\mathcal{F}$ with $|T\cap S|=n/4$? It is easy to see that $m(n)\leq n/2$
for any $n$. A matching lower bound was given by Enomoto, Frankl, Ito and
Nomora [19] in the case that $t:=(n/4)$ is odd. Hegedűs used the above lemma
to give an alternate proof of a lower bound of $n$ in the case that $t$ is an
odd prime. His proof was subsequently strengthened to a linear lower bound for
all $t$ by Alon et al. [5] and more recently to a near-tight lower bound of
$(n/2)-o(n)$ for all $t$ by Hrubeš et al. [25]. Both these results used the
lemma above.

  * •

Alon et al. [5] also used Hegedűs’s lemma to prove bounds for generalizations
of Galvin’s problem. Using this, they were able to prove improved lower bounds
against _syntatically multilinear algebraic circuits._ These are algebraic
circuits that compute multilinear polynomials in a “transparently multilinear”
way (see e.g. [40] for more). Alon et al. used Hegedűs’s lemma to prove near-
quadratic lower bounds against syntactically multilinear algebraic circuits
computing certain explicitly defined multilinear polynomials, improving on an
earlier $\tilde{\Omega}(n^{4/3})$ lower bound of Raz, Shpilka and Yehudayoff
[37].

  * •

Hrubeš et al. [25] also used Hegedűs’s lemma to answer the following question
of Kulikov and Podolskii [30] on depth-$2$ threshold circuits. What is the
smallest $k=k(n)$ such that there is a depth-$2$ circuit made up of
Majority222The Majority function is the Boolean function $f$ which accepts
exactly those inputs that have more $1$s than $0$s. gates of fan-in at most
$k$ that computes the Majority function on $n$ bits? Using Hegedűs’s lemma,
Hrubeš et al. showed an asymptotically tight lower bound of $n/2-o(n)$ on
$k(n)$.

##### Main Result.

Our main result in this paper is a ‘robust’ strengthening of Hegedűs’s lemma.
Proving ‘robust’ or ‘stability’ versions of known results is standard research
direction in combinatorics. Such questions are usually drawn from the
following template. Given the fact that objects that satisfy a certain
property have some fixed structure, we ask if a similar structure is shared by
objects that ‘almost’ or ‘somewhat’ satisfy the property.

In our setting, we ask if we can recover the degree lower bound in Hegedűs’s
lemma even if we have a polynomial $P$ that ‘approximately’ distinguishes
between $\\{0,1\\}^{n}_{k}$ and $\\{0,1\\}^{n}_{k+q}$: this means that the
polynomial $P$ vanishes at ‘most’ points of weight $k$ but is non-zero at
‘many’ points of weight $k+q$. Our main lemma is that under suitable
definitions of ‘most’ and ‘many’, we can recover (up to constant factors) the
same degree lower bound as in Lemma 1.1 above.

######  Lemma 1.2 (Main Result (Informal)).

Assume that $\mathbb{F}$ is a field of characteristic $p$. Let $n$ be a
growing parameter and assume we have positive integer parameters $k,q$ such
that $100q<k<n-100q$ and $q$ is a power of $p$. For
$\varepsilon=\varepsilon(n,k,q),$ if $P\in\mathbb{F}[x_{1},\ldots,x_{n}]$ that
vanishes at a $(1-\varepsilon)$-fraction of points of $\\{0,1\\}^{n}_{k}$ but
does not vanish at an $\varepsilon^{0.0001}$ fraction of points of
$\\{0,1\\}^{n}_{k+q},$ then $\deg(P)=\Omega(q).$

######  Remark 1.3.

  1. 1.

To keep the exposition informal, we have not specified exactly what
$\varepsilon$ is in the above lemma. However, we note below that the
$\varepsilon$ chosen is nearly the best possible in the sense that if
$\varepsilon$ is appreciably increased, then there is a sampling-based
construction of a polynomial $P$ of degree $o(q)$ satisfying the hypothesis of
the above lemma (see Section 3.3).

  2. 2.

The reader might wonder why the lemma above is a strengthening of Hegedűs’s
lemma, given that we require the polynomial $P$ to be non-zero at many points
of weight $k+q$, which is a seemingly stronger condition than required in
Lemma 1.1. However, this is in fact a weaker condition. This is because of the
following simple algebraic fact: if there is a polynomial $P$ of degree at
most $d$ satisfying the hypothesis of Lemma 1.1 (i.e. vanishing at all points
of weight $k$ but not at some point of weight $k+q$), then there is also a
polynomial $Q$ of degree at most $d$ that vanishes at all points of weight $k$
but does not vanish at a _significant fraction_ (at least a $(1-1/p)$
fraction) of points of weight $k+q$. We give a short proof of this in Appendix
A. Hence, the above lemma is indeed a generalization of Lemma 1.1 (up to the
constant-factor losses in the degree lower bound).

##### Applications.

Our investigations into robust versions of Hegedűs’s lemma were motivated by
questions in computational complexity theory. Using our main result, we are
able to sharpen and strengthen known results in complexity as well as
combinatorics.

  1. 1.

Degree bounds for the Coin Problem: For a parameter $\delta\in[0,1/2],$ we
define the _$\delta$ -coin problem_ as follows. We are given $N$ independent
tosses of a coin, which is promised to either be of bias $1/2$ (i.e. unbiased)
or $(1/2)-\delta$, and we are required to guess which of these is the case
with a high degree of accuracy, say with error probability at most
$\varepsilon$. (See Definition 4.1 for the formal definition.)

The coin problem has been studied in a variety of settings in complexity
theory (see, e.g. [3, 46, 47, 39, 12, 15]) and for various reasons such as
understanding the power of randomness in bounded-depth circuits, the
limitations of blackbox hardness amplification, and devising pseudorandom
generators for bounded-width branching programs. More recently, Limaye et al.
[31] proved optimal lower bounds on the size of $\mathrm{AC}^{0}[\oplus]$
333Recall that these are bounded-depth circuits made up of AND, OR and
$\oplus$ gates. circuits solving the $\delta$-coin problem with constant
error, strengthening an earlier lower bound of Shaltiel and Viola [39]. This
led to the first class of explicit functions for which we have tight (up to
polynomial factors) $\mathrm{AC}^{0}[\oplus]$ lower bounds. These bounds were
in turn used by Golovnev, Ilango, Impagliazzo, Kabanets, Kolokolova and Tal
[20] to resolve a long-standing open problem regarding the complexity of MCSP
in the $\mathrm{AC}^{0}[\oplus]$ model, and by Potukuchi [36] to prove lower
bounds for Andreev’s problem.

A key result in the lower bound of Limaye et al. [31] was a tight lower bound
on the degree of any polynomial $P\in\mathbb{F}[x_{1},\ldots,x_{N}]$ that
solves the $\delta$-coin problem with constant error: they showed that any
such polynomial $P$ must have degree at least $\Omega(1/\delta).$ As noted by
Agrawal [2], this is essentially equivalent to a recent result of
Chattopadhyay, Hatami, Lovett and Tal [13] on the level-$1$ Fourier
coefficients of low-degree polynomials over finite fields, which in turn is
connected to an intriguing new approach [13] toward constructing pseudorandom
generators secure against $\mathrm{AC}^{0}[\oplus].$

Using the robust Hegedűs lemma, we are able to strengthen the degree lower
bound of [31] to a tight degree lower bound for _all errors_. Specifically, we
show that over any field $\mathbb{F}$ of fixed positive characteristic $p$,
any polynomial $P$ that solves the $\delta$-coin problem with error
$\varepsilon$ must have degree $\Omega(\frac{1}{\delta}\log(1/\varepsilon))$,
which is tight for all $\delta$ and $\varepsilon.$

  2. 2.

Probabilistic degrees of symmetric functions: In a landmark paper [38],
Razborov showed how to use polynomial approximations to prove lower bounds
against $\mathrm{AC}^{0}[\oplus]$. The notion of polynomial approximation
introduced (implicitly) in his result goes by the name of _probabilistic
polynomials,_ and is defined as follows. An $\varepsilon$-error probabilistic
polynomial of degree $d$ for a Boolean function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ is a random polynomial $\bm{P}$ of
degree at most $d$ that agrees with $f$ at each point with probability at
least $1-\varepsilon$. The $\varepsilon$-error probabilistic degree of $f$ is
the least $d$ for which this holds. (Roughly speaking, a low-degree
probabilistic polynomial for $f$ is an efficient randomized algorithm for $f$,
where we think of polynomials as algorithms and degree as a measure of
efficiency.)

Many applications of polynomial approximation in complexity theory [8] and
algorithm design [50] use probabilistic polynomials and specifically bounds on
the probabilistic degrees of various _symmetric_ Boolean functions.444Recall
that a Boolean function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ is said to be
symmetric if its output depends only on the Hamming weight of its input.
Motivated by this, in a recent result with Tripathi and Venkitesh [43], we
gave a near-tight characterization on the probabilistic degree of every
symmetric Boolean function. Unfortunately, however, our upper and lower bounds
were separated by logarithmic factors. This can be crucial: in certain
algorithmic applications (see, e.g., [4, Footnote, Page 138]), the appearance
or non-appearance of an additional logarithmic factor in the degree can be the
difference between (say) a truly subquadratic running time of
$N^{2-\varepsilon}$ and a running time of $N^{2-o(1)}$, which might be less
interesting.

In the case of characteristic $0$ (or growing with $n$), such gaps look hard
to close since we don’t even understand completely the probabilistic degree of
simple functions like the OR function [34, 22, 10]. However, in positive
(fixed) characteristic, there are no obvious barrriers. Yet, even in this
case, the probabilistic degree of very simple symmetric Boolean functions like
the _Exact Threshold functions_ (functions that accept inputs of exactly one
Hamming weight) remained unresolved until this paper.

In this paper, we resolve this question and more. We are able to give a tight
(up to constants) lower bound (matching the upper bounds in [43]) on the
probabilistic degree of _every_ symmetric function over fields of positive
(fixed) characteristic.

  3. 3.

Robust version of Galvin’s problem: Given that Hegedűs’s lemma was used to
solve Galvin’s problem, it is only natural that we consider the question of
using the robust version to solve a robust version of Galvin’s problem. More
precisely, we consider the minimum size $m=m(n,\varepsilon)$ to be the minimum
size of a family $\mathcal{F}$ of $(n/2)$-sized subsets of $[n]$ such that for
all but an $\varepsilon$-fraction of sets $S$ of size $n/2$, there is a set
$T\in\mathcal{F}$ such that $|S\cap T|=n/4.$

Following the proof of Galvin’s theorem from Hegedűs’s lemma, we can prove a
lower bound of $\Omega(\sqrt{n\log(1/\varepsilon}))$ for the above version of
Galvin’s problem for any $\varepsilon\in[2^{-n},1/2].$ Note that this
interpolates smoothly between a bound of $\Omega(\sqrt{n})$ for constant
$\varepsilon$ and $\Omega(n)$ for $\varepsilon=2^{-\Omega(n)}$, both of which
are tight. For general $\varepsilon$ in between these two extremes, we do not
know if our bounds are tight (we suspect they are). However, our bounds _are_
tight for every $\varepsilon$ for a natural generalization of the above
problem, where we allow intersections of any size (and not just $n/4$). We
refer the reader to Section 4.3 for details.

##### Proof Outline.

We observe that the main lemma (Lemma 1.2) is quite similar to classical
polynomial approximation results of Razborov [38] and Smolensky [41, 42] (see
also [45]). The main difference is that while these results hold for
polynomials approximating some function on the whole cube $\\{0,1\\}^{n}$, the
lemma deals with polynomial approximations that are more ‘local’ in that they
are restricted on just two layers of the cube. Nevertheless, we can show that
the basic proof strategy of Smolensky (or more specifically a variant as in
[6, 29]) can be used to prove our lemma as well.

The main point of difference from these standard proofs is the employment of a
result from discrete geometry due to Nie and Wang [35], that allows us to
bound the size of the _closure_ 555The _degree- $D$ closure_
$\mathrm{cl}_{D}(E)$ of a set $E$ is the set of points where any degree-$D$
polynomial $Q$ vanishing throughout $E$ is forced to vanish. of a small set of
points in the cube. This is a well-studied object in coding theory [48] and
combinatorics [14, 26, 35], and turns out to be a crucial ingredient in our
proof.

For the application to the coin problem, we show that if a polynomial $P$
solves the coin problem (see Definition 4.1 for the formal definition of
this), then it can be used to distinguish between Hamming weights $k$ and
$k+q$ for $k$ and $q$ as in Lemma 1.2. This reduction is done by a simple
sampling argument. The degree lower bound in Lemma 1.2 then implies the
desired degree lower bound on the degree of $P$.

In the other applications to probabilistic degree and the robust version of
Galvin’s problem, the idea is to follow the proofs of the previous best
results in this direction and apply the main lemma at suitable points. We
defer more details to the actual proofs.

##  2 Preliminaries

We use the notation $[a,b]$ to denote an interval in $\mathbb{R}$ as well as
an interval in $\mathbb{Z}$. The distinction will be clear from context.

##### Multilinear polynomials and Multilinearization.

Fix any field $\mathbb{F}$. Throughout, we work with functions
$f:\\{0,1\\}^{n}\rightarrow\mathbb{F}$ which are represented by multilinear
polynomials. Recall that each such function has a _unique_ multilinear
polynomial representation. Further, given a (possibly non-multlinear)
polynomial $P(x_{1},\ldots,x_{n})$ representing $f$ (i.e. $P(a)=f(a)$ for all
$a\in\\{0,1\\}^{n}$), we can obtain a multilinear representation $Q$ by simply
replacing each $x_{i}^{r}$ for $r>1$ by $x_{i}$ in the polynomial $P$. This
preserves the underlying function as $b^{r}=b$ for $b\in\\{0,1\\}$. Any
polynomial $P$ can be _multilinearized_ this way without increasing the
degree.

##### Bernstein’s inequality.

The following standard deviation bound can be found in, e.g., the book of
Dubhashi and Panconesi [17, Theorem 1.2].

######  Lemma 2.1 (Bernstein’s inequality).

Let $X_{1},\ldots,X_{m}$ be independent and identically distributed Bernoulli
random variables with mean $q$. Let $X=\sum_{i=1}^{m}X_{i}$. Then for any
$\theta>0$,

###  2.1 Symmetric Boolean functions

Let $n$ be a growing integer parameter which will always be the number of
input variables. We use $s\mathcal{B}_{n}$ to denote the set of all symmetric
Boolean functions on $n$ variables. Note that each symmetric Boolean function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ is uniquely specified by a string
$\mathrm{Spec}\,f:[0,n]\rightarrow\\{0,1\\}$, which we call the _Spectrum_ of
$f$, in the sense that for any $a\in\\{0,1\\}^{n}$, we have

$f(a)=\mathrm{Spec}\,f(|a|).$

Given a $f\in s\mathcal{B}_{n}$, we define the _period of $f$_, denoted
$\mathrm{per}(f),$ to be the smallest positive integer $b$ such that
$\mathrm{Spec}\,f(i)=\mathrm{Spec}\,f(i+b)$ for all $i\in[0,n-b]$. We say $f$
is _$k$ -bounded_ if $\mathrm{Spec}\,f$ is constant on the interval $[k,n-k]$;
let $B(f)$ denote the smallest $k$ such that $f$ is $k$-bounded.

###### Standard decomposition of a symmetric Boolean function [33].

Fix any $f\in s\mathcal{B}_{n}.$ Among all symmetric Boolean functions
$f^{\prime}\in s\mathcal{B}_{n}$ such that
$\mathrm{Spec}\,f^{\prime}(i)=\mathrm{Spec}\,f(i)$ for all $i\in[\lceil
n/3\rceil+1,\lfloor 2n/3\rfloor],$ we choose a function $g$ such that
$\mathrm{per}(g)$ is as small as possible. We call $g$ the _periodic part_ of
$f$. Define $h\in s\mathcal{B}_{n}$ by $h=f\oplus g.$ We call $h$ the _bounded
part_ of $f$.

We will refer to the pair $(g,h)$ as a _standard decomposition_ of the
function $f$. Note that we have $f=g\oplus h.$

Let $f\in s\mathcal{B}_{n}$ and let $(g,h)$ be a standard decomposition of
$f$. Then, $\mathrm{per}(g)\leq\lfloor n/3\rfloor$ and $B(h)\leq\lceil
n/3\rceil.$

###### Some symmetric Boolean functions.

Fix some positive $n\in\mathbb{N}$. The _Majority_ function $\mathrm{Maj}_{n}$
on $n$ Boolean variables accepts exactly the inputs of Hamming weight greater
than $n/2.$ For $t\in[0,n]$, the _Threshold_ function $\mathrm{Thr}^{t}_{n}$
accepts exactly the inputs of Hamming weight at least $t$; and similarly, the
_Exact Threshold_ function $\mathrm{EThr}^{t}_{n}$ accepts exactly the inputs
of Hamming weight exactly $t$. Finally, for $b\in[2,n]$ and $i\in[0,b-1]$, the
function $\mathrm{MOD}^{b,i}_{n}$ accepts exactly those inputs $a$ such that
$|a|\equiv i\pmod{b}.$ In the special case that $i=0$, we also use
$\mathrm{MOD}^{b}_{n}.$

###  2.2 Probabilistic polynomials

######  Definition 2.2 (Probabilistic polynomial and Probabilistic degree).

A _probabilistic polynomial_ is a random polynomial $\bm{P}$ (with some
distribution having finite support) over $\mathbb{F}[x_{1},\ldots,x_{n}].$ We
say that the degree of $\bm{P}$, denoted $\deg(\bm{P})$, is at most $d$ if the
probability distribution defining $\bm{P}$ is supported on polynomials of
degree at most $d$.

Given a Boolean function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ and an
$\varepsilon>0,$ an _$\varepsilon$ -error probabilistic polynomial_ for $f$ is
a probabilistic polynomial $\bm{P}$ such that for each $a\in\\{0,1\\}^{n}$,

We define the _$\varepsilon$ -error probabilistic degree_ of $f$, denoted
$\mathrm{pdeg}^{\mathbb{F}}_{\varepsilon}(f)$, to be the least $d$ such that
$f$ has an $\varepsilon$-error probabilistic polynomial of degree at most $d$.

When the field $\mathbb{F}$ is clear from context, we use
$\mathrm{pdeg}_{\varepsilon}(f)$ instead of
$\mathrm{pdeg}^{\mathbb{F}}_{\varepsilon}(f).$

######  Fact 3.

We have the following simple facts about probabilistic degrees of Boolean
functions. Let $\mathbb{F}$ be any field.

  1. 1.

(Error reduction [22]) For any $\delta<\varepsilon\leq 1/3$ and any Boolean
function $f$, if $\bm{P}$ is an $\varepsilon$-error probabilistic polynomial
for $f$, then $\bm{Q}=M(\bm{P}_{1},\ldots,\bm{P}_{\ell})$ is a $\delta$-error
probabilistic polynomial for $f$ where
$\ell=O(\log(1/\delta)/\log(1/\varepsilon)),$ $M$ is the exact multilinear
polynomial for $\mathrm{Maj}_{\ell},$ and $\bm{P}_{1},\ldots,\bm{P}_{\ell}$
are independent copies of $\bm{P}.$ In particular, we have
$\mathrm{pdeg}_{\delta}^{\mathbb{F}}(f)\leq\mathrm{pdeg}_{\varepsilon}^{\mathbb{F}}(f)\cdot
O(\log(1/\delta)/\log(1/\varepsilon)).$

  2. 2.

(Composition) For any Boolean function $f$ on $k$ variables and any Boolean
functions $g_{1},\ldots,g_{k}$ on a common set of $m$ variables, let $h$
denote the natural composed function $f(g_{1},\ldots,g_{k})$ on $m$ variables.
Then, for any $\varepsilon,\delta>0,$ we have
$\mathrm{pdeg}_{\varepsilon+k\delta}^{\mathbb{F}}(h)\leq\mathrm{pdeg}_{\varepsilon}^{\mathbb{F}}(f)\cdot\max_{i\in[k]}\mathrm{pdeg}_{\delta}^{\mathbb{F}}(g_{i}).$

  3. 3.

(Sum) Assume that $f,g_{1},\ldots,g_{k}$ are all Boolean functions on a common
set of $m$ variables such that the functions $g_{1},\ldots,g_{k}$ are mutually
exclusive and $f=\sum_{i\in[k]}g_{i}$. Then, for any $\delta>0,$ we have
$\mathrm{pdeg}_{k\delta}^{\mathbb{F}}(f)\leq\max_{i\in[k]}\mathrm{pdeg}_{\delta}^{\mathbb{F}}(g_{i}).$

The first item above is not entirely obvious, as the polynomial $\bm{P}$ is
not necessarily Boolean-valued at points when $\bm{P}(a)\neq f(a)$. Hence, it
is not clear that composing with a polynomial that computes the Boolean
Majority function achieves error-reduction. The second and third items above
are trivial.

Building on work of Alman and Williams [4] and Lu [33], Tripathi, Venkitesh
and the author [43] gave upper bounds on the probabilistic degree of any
symmetric function. We recall below the statement in the case of fixed
positive characteristic.

######  Theorem 2.3 (Known upper bounds on probabilistic degree of symmetric
functions [43]).

Let $\mathbb{F}$ be a field of constant characteristic $p>0$ and
$n\in\mathbb{N}$ be a growing parameter. Let $f\in s\mathcal{B}_{n}$ be
arbitrary and let $(g,h)$ be a standard decomposition of $f$. Then we have the
following for any $\varepsilon>0.$

  1. 1.

If $\mathrm{per}(g)=1,$ then $g$ is a constant and hence
$\mathrm{pdeg}_{\varepsilon}(g)=0.$

If $\mathrm{per}(g)$ is a power of $p$, then $g$ can be _exactly_
represented666While this is not part of the formal theorem statement from
[43], it follows readily from the proof. as a polynomial of degree at most
$\mathrm{per}(g)$, and hence
$\mathrm{pdeg}^{\mathbb{F}}_{\varepsilon}(g)\leq\mathrm{per}(g),$

  2. 2.

$\mathrm{pdeg}_{\varepsilon}(h)=O(\sqrt{B(h)\log(1/\varepsilon)}+\log(1/\varepsilon))$
if $B(h)\geq 1$ and $0$ otherwise, and

  3. 3.

$\mathrm{pdeg}_{\varepsilon}(f)=\left\\{\begin{array}[]{ll}O(\sqrt{n\log(1/\varepsilon)})&\text{if
$\mathrm{per}(g)>1$ and not a power of $p$},\\\
O(\min\\{\sqrt{n\log(1/\varepsilon)},\mathrm{per}(g)\\})&\text{if
$\mathrm{per}(g)$ a power of $p$ and $B(h)=0$,}\\\
O(\min\\{\sqrt{n\log(1/\varepsilon)},\mathrm{per}(g)+&\text{otherwise.}\\\ \ \
\sqrt{B(h)\log(1/\varepsilon)}+\log(1/\varepsilon)\\})&\end{array}\right.$

###  2.3 A string lemma

Given a function $w:I\rightarrow\\{0,1\\}$ where $I\subseteq\mathbb{N}$ is an
interval, we think of $w$ as a string from the set $\\{0,1\\}^{|I|}$ in the
natural way. For an interval $J\subseteq I,$ we denote by $w|_{J}$ the
substring of $w$ obtained by restriction to $J$.

The following simple lemma can be found, e.g. as a special case of [9, Theorem
3.1]. For completeness, we give a short proof in Appendix B.

######  Lemma 2.4.

Let $w\in\\{0,1\\}^{+}$ be any non-empty string777Recall that, for any
alphabet $\Sigma,$ the notation $\Sigma^{+}$ denotes the set of non-empty
strings over this alphabet. and $u,v\in\\{0,1\\}^{+}$ such that $w=uv=vu$.
Then there exists a string $z\in\\{0,1\\}^{+}$ such that $w$ is a power of $z$
(i.e. $w=z^{k}$ for some $k\geq 2$).

######  Corollary 2.5.

Let $g\in s\mathcal{B}_{n}$ be arbitrary with $\mathrm{per}(g)=b>1.$ Then for
all $i,j\in[0,n-b+1]$ such that $i\not\equiv j\pmod{b}$, we have
$\mathrm{Spec}\,g|_{[i,i+b-1]}\neq\mathrm{Spec}\,g|_{[j,j+b-1]}.$

######  Proof 2.6.

Suppose $\mathrm{Spec}\,g|_{[i,i+b-1]}=\mathrm{Spec}\,g|_{[j,j+b-1]}$ for some
$i\not\equiv j\pmod{b}.$ Assume without loss of generality that $i<j<i+b.$ Let
$u=\mathrm{Spec}\,g|_{[i,j-1]},v=\mathrm{Spec}\,g|_{[j,i+b-1]},w=\mathrm{Spec}\,g|_{[i+b,j+b-1]}$.
Then $u=w$ and the assumption $uv=vw$ implies $uv=vu$. By Lemma 2.4, there
exists a string $z$ such that $uv=z^{k}$ for $k\geq 2$ and therefore
$\mathrm{per}(g)<b$. This contradicts our assumption on $b$.

###  2.4 Lucas’s theorem

######  Theorem 2.7 (Lucas’s theorem).

Let $A,B$ be any non-negative integers and $p$ any prime. Then

$\binom{A}{B}=\prod_{i\geq 0}\binom{A_{i}}{B_{i}}\pmod{p}$

where $A_{i}$ (resp. $B_{i}$) is the $(i+1)$th least significant digit of $A$
(resp. $B$) in base $p$.

The following is a standard application of Lucas’s theorem, essentially
observed by Lu [33] and Hegedűs [23], showing that Hegedűs’s lemma is tight.

######  Corollary 2.8.

Fix any prime $p$ and positive integer $n$. Assume $i$ is a non-negative
integer and $q$ a positive integer such that $i+q\leq n.$ Let $p^{\ell}$ be
the largest power of $p$ dividing $q$. Then, there is a symmetric multilinear
polynomial $Q\in\mathbb{F}_{p}[x_{1},\ldots,x_{n}]$ of degree $p^{\ell}$ such
that $Q$ vanishes at all points of $\\{0,1\\}^{n}_{i}$ but at no point of
$\\{0,1\\}^{n}_{i+q}.$

######  Proof 2.9.

Assume $q=p^{\ell}s$ where $s$ is not divisible by $p$. Let
$a_{\ell},b_{\ell}\in\\{0,\ldots,p-1\\}$ be the $(\ell+1)$th least significant
digit of $i$ and $i+q$ respectively in base $p$. Note that
$b_{\ell}=a_{\ell}+s_{0}\pmod{p}$ where $s_{0}$ is the least significant digit
of $s$ in base $p$ ($s_{0}$ is non-zero as $s$ is not divisible by $p$).

Define the polynomial

$Q(x_{1},\ldots,x_{n})=\left(\sum_{S\subseteq[n]:|S|=p^{\ell}}\prod_{i\in
S}x_{i}\right)-a_{\ell},$

which we consider an element of $\mathbb{F}_{p}[x_{1},\ldots,x_{n}].$ Note
that at any input $c\in\\{0,1\\}^{n}$ of Hamming weight $w$, we have

$Q(c)=\binom{w}{p^{\ell}}-a_{\ell}$

where the right hand side is interpreted modulo $p$. Lucas’s theorem then
easily implies that $Q(c)=0$ if $w=i$ and $s_{0}$ if $w=i+q.$

##  3 The Main Lemma

In this section, we prove the main lemma, which is a robust version of Lemma
1.1.

######  Lemma 3.1 (A Robust Version of Hegedűs’s Lemma).

Assume that $\mathbb{F}$ is a field of characteristic $p$. Let $n$ be a
growing parameter and assume we have positive integer parameters $k,q$ such
that $100q<k<n-100q$ and $q$ is a power of $p$. Define
$\alpha=\min\\{k/n,1-(k/n)\\}$ and $\delta=q/n.$ Assume
$P\in\mathbb{F}[x_{1},\ldots,x_{n}]$ is a polynomial such that for some
$K\in\\{k+q,k-q\\}$,

$\displaystyle\leq\min\\{e^{-100\delta^{2}n/\alpha},1/1000\\}$ (1a)
$\displaystyle\geq e^{-\delta^{2}n/100\alpha}.$ (1b)

Then, $\deg(P)=\Omega(q),$ where the $\Omega(\cdot)$ hides an absolute
constant.

One can ask if the above lemma can be proved under weaker assumptions:
specifically, if the upper bound in (1a) can be relaxed. It turns out that it
cannot (up to changing the constant in the exponent) because for larger error
parameters, there is a sampling-based construction of a polynomial with
smaller degree that is zero on most of $\\{0,1\\}^{n}_{k}$ and non-zero on
most of $\\{0,1\\}^{n}_{K}.$ We discuss this construction in Section 3.3.

We first prove a special case of the lemma which corresponds to the case when
$K=k+q=\lfloor n/2\rfloor$ and $q$ sufficiently larger than $\sqrt{n}.$ This
case suffices for most of our applications. The general case is a
straightforward reduction to this special case.

###  3.1 A special case

######  Lemma 3.2 (A special case of Lemma 3.1).

Let $n$ be a growing parameter and assume
$\varepsilon\in[2^{-n/100},e^{-200}].$ Assume $t$ is an integer such that $t$
is a power of $p$ and furthermore, $t=\sqrt{n\ell}$ for some
$\ell\in\mathbb{R}$ such that
$100\leq\ell\leq\frac{1}{2}\cdot\ln(1/\varepsilon).$ Let
$P\in\mathbb{F}[x_{1},\ldots,x_{n}]$ be any polynomial such that

$\displaystyle\leq\varepsilon$ (2a) $\displaystyle\geq e^{-\ell/2}.$ (2b)

Then, $\deg(P)\geq t/25.$

######  Remark 3.3.

By negating inputs (i.e. replacing $x_{i}$ with $1-x_{i}$ for each $i$), the
above lemma also implies the analogous statements where $\lfloor n/2\rfloor-t$
and $\lfloor n/2\rfloor$ are replaced by $\lceil n/2\rceil+t$ and $\lceil
n/2\rceil$ respectively.

Before we prove this lemma, we need to collect some technical facts and
lemmas.

The following is standard. See, e.g., [29, Lemma 3.3] for a proof.

######  Fact 8.

Let $R\in\mathbb{F}[x_{1},\ldots,x_{n}]$ be a non-zero multilinear polynomial
of degree at most $d\leq n$. Then $R$ cannot vanish at all points in any
Hamming ball of radius $d$ in $\\{0,1\\}^{n}$.

######  Lemma 3.4.

Let $n,r,s$ be any non-negative integers with $r\leq s\leq n/4.$ Then we have

$e^{-8s(r-s)/n}\leq\frac{\binom{n}{\lfloor n/2\rfloor-s}}{\binom{n}{\lfloor
n/2\rfloor-r}}\leq e^{-2r(r-s)/n}.$

######  Proof 3.5.

Note that

$\frac{\binom{n}{\lfloor n/2\rfloor-s}}{\binom{n}{\lfloor
n/2\rfloor-r}}=\frac{(\lfloor n/2\rfloor-s+1)\cdots(\lfloor
n/2\rfloor-r)}{(\lceil n/2\rceil+s)\cdots(\lceil
n/2\rceil+r+1)}\leq\left(\frac{\lfloor n/2\rfloor-r}{\lceil
n/2\rceil+r}\right)^{r-s}\leq\left(1-\frac{2r}{n}\right)^{r-s}\leq
e^{-2r(r-s)/n},$

which implies the right inequality in the statement of the claim. We have used
the inequality $1-x\leq e^{x}$ to deduce the final inequality above.

For the left inequality, we similarly have

$\displaystyle\frac{\binom{n}{\lfloor n/2\rfloor-s}}{\binom{n}{\lfloor
n/2\rfloor-r}}\geq\left(\frac{\lceil n/2\rceil-s}{\lceil
n/2\rceil+s}\right)^{r-s}\geq\left(\left(1-\frac{2s}{n}\right)^{2}\right)^{r-s}\geq
e^{-8s(r-s)/n}.$

where the final inequality follows from the fact that $(1-x)\geq e^{-2x}$ for
$x\in[0,1/2]$.

Given a set $E\subseteq\\{0,1\\}^{n},$ and a parameter $D\leq n$, we define
$\mathcal{I}_{D}(E)$ to be the set of all multilinear polynomials $Q$ of
degree at most $D$ that vanish at all points of $E$. Further, we define the
_degree- $D$ closure of $E$_, denoted $\mathrm{cl}_{D}(E)$ as follows.

$\mathrm{cl}_{D}(E):=\\{a\in\\{0,1\\}^{n}\ |\ Q(a)=0\ \ \forall
Q\in\mathcal{I}_{D}(E)\\}.$

Note that $\mathrm{cl}_{D}(E)\supseteq E$ but could be much bigger than $E$.
The following result of Nie and Wang [35] gives a bound on
$|\mathrm{cl}_{D}(E)|$ in terms of $|E|.$ (This particular form is noted and
essentially proved in [35], and is explicitly stated and proved in [29,
Theorem A.1] for _all_ fields.)

######  Theorem 3.6.

For any $E\subseteq\\{0,1\\}^{n}$ and any $D\leq n$, we have

$\frac{\mathrm{cl}_{D}(E)}{2^{n}}\leq\frac{|E|}{N_{D}}$

where $N_{D}=\sum_{j=0}^{D}\binom{n}{j},$ the number of multilinear monomials
of degree at most $D$.

######  Remark 3.7.

It should be noted that the above lemma generalizes the standard linear-
algebraic fact that for any $E$ such that $|E|<N_{D}$, there is a non-zero
multilinear polynomial of degree $D$ that vanishes on $E$. Or equivalently,

$|E|<N_{D}\Longrightarrow\mathrm{cl}_{D}(E)<2^{n}.$

The inequality stated in the lemma is tight for certain sets $E$ of size
$N_{D}$ (a good example of such a set is any Hamming ball of radius $D$).
However, when $|E|$ is much smaller than $N_{D}$, the parameters can be
tightened. A tight form of this lemma, that gives the best possible parameters
depending on $|E|$, was proved in earlier work of Keevash and Sudakov [26]
(see also the works of Clements and Lindström [14], Wei [48], Heijnen and
Pellikaan [24], and Beelen and Dutta [7] that prove similar results). However,
we don’t need this general form of the lemma here.

We now begin the proof of the Lemma 3.2.

######  Proof 3.8 (Proof of Lemma 3.2).

Assume that $P$ is as given. Let $m=\lfloor n/2\rfloor$.

Let $E_{0},E_{1}$ be defined as follows. (Here, the notation “$E$” stands for
“error sets”.)

$\displaystyle E_{0}$ $\displaystyle=\\{a\in\\{0,1\\}^{n}_{m-t}\ |\ P(a)\neq
0\\}$ $\displaystyle E_{1}$ $\displaystyle=\\{a\in\\{0,1\\}^{n}_{m}\ |\
P(a)=0\\}$

We show that there are polynomials
$Q_{1},Q_{2}\in\mathbb{F}[x_{1},\ldots,x_{n}]$ such that the following
conditions hold.

(Q1.1) $Q_{1}(a)\neq 0$ if and only if $|a|\equiv m\pmod{t}.$

(Q2.1) $Q_{2}(a)=0$ for all $a\in E_{0}$.

(Q2.2) $Q_{2}(a)=0$ for all $a$ such that $|a|<m-t$ and $|a|\equiv m\pmod{t}.$

(Q2.3) $Q_{2}(a)\neq 0$ for some $a\in\\{0,1\\}^{n}_{m}\setminus E_{1}.$

Given polynomials $Q_{1},Q_{2}$ as above, we construct the polynomial $R$ to
be the multilinear polynomial obtained by computing the formal product $P\cdot
Q_{1}\cdot Q_{2}$ and replacing $x_{i}^{r}$ by $x_{i}$ for each $r>1$. Note
that $R(a)=P(a)Q_{1}(a)Q_{2}(a)$ for any $a\in\\{0,1\\}^{n}$.

We observe that $R(a)=0$ for all $|a|<m.$ This is based on a case analysis of
whether $|a|\equiv m\pmod{t}$ or not. In the latter case, we see that
$Q_{1}(a)=0$ and hence $R(a)=0.$ In the former case, we have either
$a\in\\{0,1\\}^{n}_{m-t}\setminus E_{0}$, in which case $P(a)=0$, or not, in
which case $Q_{2}(a)=0.$ Hence, $R(a)=0$ for all $|a|<m.$

On the other hand, we note that $R$ is a non-zero polynomial. This is because
by (Q2.3), we know that there is some $a^{\prime}\in\\{0,1\\}^{n}_{m}\setminus
E_{1}$ where $Q_{2}(a^{\prime})\neq 0.$ Further, $Q_{1}(a^{\prime})\neq 0$ and
$P(a^{\prime})\neq 0$ by (Q1.1) and the definition of $E_{1}$ respectively.
Hence, $R(a^{\prime})\neq 0,$ implying that $R$ is a non-zero multilinear
polynomial.

By Fact 8, we thus know that $R$ has degree at least $m$. In particular, we
obtain

$\deg(P)\geq\deg(R)-\deg(Q_{1})-\deg(Q_{2})\geq m-\deg(Q_{1})-\deg(Q_{2}).$

Hence, to finish the proof of the lemma, it suffices to prove the following
claims.

######  Claim 9.

There is a $Q_{1}$ of degree at most $t$ satisfying property (Q1.1).

######  Claim 10.

There is a $Q_{2}$ of degree at most $m-t-t_{1}$ satisfying properties
(Q2.1)-(Q2.3), where $t_{1}=\lceil t/25\rceil.$

We now prove the above claims.

[Proof of Claim 9] This follows immediately from the upper bound for periodic
functions in Theorem 2.3. Consider the $t$-periodic function that takes the
value $1$ at point $a\in\\{0,1\\}^{n}$ if and only if $|a|\equiv m\pmod{t}.$
Since this function is $t$-periodic, it can be represented exactly as a
polynomial of degree at most $t$. This yields the claim.

[Proof of Claim 10] Let $D$ denote $m-t-t_{1}.$ Let
$E=E_{0}\cup\bigcup_{j<m-t:j\equiv m\pmod{t}}\\{0,1\\}^{n}_{j}.$ We want to
show the existence of a polynomial $Q_{2}$ of degree at most $D$ such that
$Q_{2}$ vanishes at all points of $E$ but $Q_{2}$ does not vanish at some
point in ${E}_{1}^{\prime}:=\\{0,1\\}^{n}_{m}\setminus E_{1}$. Note that this
is equivalent to saying that $\mathrm{cl}_{D}(E)\nsupseteq{E}_{1}^{\prime}$.
To show this, it suffices to show that

$|\mathrm{cl}_{D}(E)|<e^{-\ell/2}\cdot\binom{n}{m}$ (3)

since by hypothesis we have $|{E}_{1}^{\prime}|\geq
e^{-\ell/2}\cdot\binom{n}{m}.$

To do this, we use Theorem 3.6. Note that we have

$\displaystyle|E|$ $\displaystyle\leq|E_{0}|+\sum_{j<m-t:j\equiv
m\pmod{t}}\binom{n}{j}$
$\displaystyle\leq\varepsilon\cdot\binom{n}{m-t}+\sum_{k\geq
1}\binom{n}{m-t-k\cdot t}$
$\displaystyle\leq\varepsilon\cdot\binom{n}{m-t}+\binom{n}{m-t}\cdot\left(e^{-2\ell}+e^{-4\ell}+\ldots\right)$
$\displaystyle\leq\binom{n}{m-t}\cdot(\varepsilon+2\cdot
e^{-2\ell})\leq\binom{n}{m-t}\cdot(3e^{-2\ell})$ (4)

where the third inequality is a consequence of Lemma 3.4 (with $r=t$ and
$s=(k+1)t$ for various $k$) and the final inequality uses $\varepsilon\leq
e^{-2\ell}.$

On the other hand, the parameter $N_{D}$ from the statement of Theorem 3.6 can
be lower bounded as follows.

$\displaystyle N_{D}$ $\displaystyle=\sum_{j=0}^{D}\binom{n}{D-j}\geq
t_{1}\binom{n}{m-t-2t_{1}}$ $\displaystyle\geq
t_{1}e^{-\ell}\cdot\binom{n}{m-t}>e^{-\ell}\cdot\frac{\sqrt{n}}{3}\cdot\binom{n}{m-t}$

where the second inequality follows from Lemma 3.4 (with $r=t$ and
$s=t+2t_{1}$) and the final inequality uses the fact that
$t_{1}>t/30=\sqrt{n\ell}/30\geq\sqrt{n}/3.$

Putting the above together with (4) immediately yields

$\frac{|E|}{N_{D}}<9e^{-\ell}\cdot\frac{\binom{n}{m-t}}{\sqrt{n}\cdot\binom{n}{m-t}}=9e^{-\ell}\cdot
n^{-1/2}.$

Using Theorem 3.6, we thus obtain

$\mathrm{cl}_{D}(E)<9e^{-\ell}\cdot\frac{2^{n}}{\sqrt{n}}\leq
e^{-\ell/2}\cdot\frac{2^{n}}{2\sqrt{n}}\leq e^{-\ell/2}\cdot\binom{n}{m}$

where the last inequality follows from Stirling’s approximation. Having shown
(3), the claim now follows.

###  3.2 The General Case

We start with some preliminaries.

We first show a simple ‘error-reduction’ procedure for polynomials. For any
polynomial $P\in\mathbb{F}[x_{1},\ldots,x_{n}]$ and any $m\in[0,n]$, let
$\mathrm{NZ}_{m}(P)$ denote the set of points of $\\{0,1\\}^{n}_{m}$ where $P$
does not vanish. Let $\psi_{m}(P)$ denote $|\mathrm{NZ}_{m}(P)|/\binom{n}{m}.$

######  Lemma 3.9.

For any $Q\in\mathbb{F}[x_{1},\ldots,x_{n}]$ and any $r\geq 1$, there is a
probabilistic polynomial $\bm{Q^{(r)}}$ of degree at most $r\cdot\deg(Q)$ such
that for all $m\in[0,n]$,
$\mathop{\textbf{E}}_{\bm{Q^{(r)}}}[\psi_{m}(\bm{Q^{(r)}})]=\psi_{m}(Q)^{r}.$

######  Proof 3.10.

For a permutation $\pi\in S_{n},$ and $a\in\\{0,1\\}^{n},$ define
$a^{\pi}=(a_{\pi(1)},\ldots,a_{\pi(n)}).$ Also, define
$Q^{\pi}(x_{1},\ldots,x_{n})=Q(x^{\pi})=Q(x_{\pi(1)},\ldots,x_{\pi(n)}).$

For a uniformly random $\bm{\pi}\in S_{n},$ and any $a\in\\{0,1\\}^{n}_{m}$,
the probabilistic polynomial $Q^{\bm{\pi}}$ satisfies

as $a^{\bm{\pi}}$ is uniformly distributed over $\\{0,1\\}^{n}_{m}.$

Choose $\bm{\pi_{1}},\ldots,\bm{\pi_{r}}$ i.u.a.r. from $S_{n},$ and define
$\bm{Q^{(r)}}=\prod_{i=1}^{r}Q^{\bm{\pi_{i}}}.$ For any
$a\in\\{0,1\\}^{n}_{m}$

In particular, the above holds for a uniformly random $\bm{a}$ chosen from
$\\{0,1\\}^{n}_{m}.$ Hence, we have

$\mathop{\textbf{E}}_{\bm{Q^{(r)}}}[\psi_{m}(\bm{Q^{(r)}})]=$

We are now ready to prove the main lemma in its full generality.

######  Proof 3.11 (Proof of Lemma 3.1).

W.l.o.g. we assume that $k\leq n/2$. (To prove the lemma for $k>n/2$, consider
the polynomial $Q(x)=P(1-x_{1},\ldots,1-x_{n})$ instead.)

We first reduce to the case where $K=n/2$.

More precisely, note that there exist non-negative integers $r\leq 2q$ and $s$
so that $2(K-r)=n-r-s.$ This can be seen by a simple case analysis. If
$K=k-q$, we can choose $r=0$, $s=n-2k+2q$; if $K=k+q$ and $n-2k\geq 2q$, we
can choose $r=0$ and $s=n-2k-2q$; and if $K=k+q$ and $n-2k<2q$, we can choose
$r=2q-(n-2k)$ and $s=0$.

Having chosen $r,s$ as above, we set $K^{\prime}=K-r$, $k^{\prime}=k-r$ and
$n^{\prime}=n-r-s$. Let $\bm{S}$ be a uniformly random subset of $[n]$ of size
$r+s$ and $\bm{y}$ a uniformly random point in $\\{0,1\\}^{r+s}_{r}$. We set
$P_{\bm{S},\bm{y}}(x_{i}:i\not\in S)$ to be the probabilistic polynomial
obtained by setting all the variables indexed by $\bm{S}$ according to
$\bm{y}$. Note that we have

$\mathop{\textbf{E}}_{\bm{S},\bm{y}}[\psi_{k^{\prime}}(P_{\bm{S},\bm{y}})]=\psi_{k}(P)=:\varepsilon_{0}\phantom{xxx}\text{
and
}\phantom{xxx}\mathop{\textbf{E}}_{\bm{S},\bm{y}}[\psi_{K^{\prime}}(P_{\bm{S},\bm{y}})]=\psi_{K}(P)=:\varepsilon_{1}.$

By Markov’s inequality, we have

Hence, with positive probability over the choice of $\bm{S}$ and $\bm{y},$ we
have both $\psi_{k^{\prime}}(P_{\bm{S},\bm{y}})\leq
2\varepsilon_{0}/{\varepsilon_{1}}$ and
$\psi_{K^{\prime}}(P_{\bm{S},\bm{y}})>{\varepsilon_{1}}/{2}.$ We fix such a
choice $S,y$ for $\bm{S},\bm{y}$ and let $P^{\prime}$ denote $P_{S,y}.$
Clearly, $\deg(P)\geq\deg(P^{\prime})$ and hence it suffices to lower bound
$\deg(P^{\prime}).$

We will now use Lemma 3.2 to obtain the desired lower bound on
$\deg(P^{\prime}).$ First of all, note that $\ell^{\prime}:=q^{2}/n^{\prime}$
satisfies

$\ell^{\prime}=\frac{q^{2}}{n^{\prime}}\leq\frac{k^{2}}{10000n^{\prime}}\leq\frac{n^{\prime}}{10000},$

by the bounds on $q$ in the statement of the lemma and the fact that $k\leq
2K=n^{\prime}$.

We consider now two cases.

##### Case 1:

Assume first that $\ell^{\prime}\geq 100.$ Using the bounds on
$\varepsilon_{0}$ and $\varepsilon_{1}$ that follow from the lemma statement
and the bounds above, $P^{\prime}$ is a polynomial in $n^{\prime}$ variables
satisfying

$\displaystyle\psi_{k^{\prime}}(P^{\prime})$
$\displaystyle\leq\frac{2\varepsilon_{0}}{\varepsilon_{1}}\leq
2\varepsilon_{0}^{0.99}\leq
2\exp(-99\delta^{2}n/\alpha)=2\exp(-99\delta^{2}n^{2}/(\alpha n))\leq
2\exp(-99q^{2}/n^{\prime}),\text{ and }$
$\displaystyle\psi_{K^{\prime}}(P^{\prime})$
$\displaystyle\geq\frac{\varepsilon_{1}}{2}\geq\frac{1}{2}\exp(-(1/100)\cdot\delta^{2}n/\alpha)=\frac{1}{2}\exp(-(1/100)\cdot\delta^{2}n^{2}/(\alpha
n))$ $\displaystyle\geq\frac{1}{2}\exp(-(1/25)\cdot q^{2}/n^{\prime}).$

where we have used the inequalities $n^{\prime}\geq 2(k-q)\geq\alpha n$ and
$n^{\prime}=2K^{\prime}\leq 2(k+q)\leq 4\alpha n.$

Define $\varepsilon=\exp(-2\ell^{\prime}).$ Note that we have
$\varepsilon\geq\exp(-n^{\prime}/5000)$ by the bound on $\ell^{\prime}$ above.
Further,

$\displaystyle\psi_{(n^{\prime}/2)-q}(P^{\prime})$
$\displaystyle=\psi_{k^{\prime}}(P^{\prime})\leq
2\exp(-99q^{2}/n^{\prime})=2\exp(-99\ell^{\prime})\leq\exp(-2\ell^{\prime})=\varepsilon,\text{
and }$ $\displaystyle\psi_{n^{\prime}/2}(P^{\prime})$
$\displaystyle=\psi_{K^{\prime}}(P^{\prime})\geq\frac{1}{2}\exp(-(1/25)\cdot
q^{2}/n^{\prime})\geq\exp(-\ell^{\prime}/2).$

Applying Lemma 3.2 to $P^{\prime}$ (see also Remark 3.3), we immediately
obtain $\deg(P^{\prime})\geq q/25$ and hence we are done in this case.

##### Case 2:

Now consider the case when $\ell^{\prime}<100$. In this case, the hypothesis
of the lemma assures us that $\varepsilon_{0}\leq 1/1000$ and
$\varepsilon_{1}\geq\exp(-q^{2}/100\alpha n)\geq\exp(-\ell^{\prime}/25)\geq
e^{-4}$ where the second inequality uses $n^{\prime}\leq 4\alpha n$ as argued
above. Then, we have

$\displaystyle\psi_{k^{\prime}}(P^{\prime})$
$\displaystyle\leq\frac{2\varepsilon_{0}}{\varepsilon_{1}}\leq
2\varepsilon_{0}^{0.99}\leq\frac{1}{400},$ (5a)
$\displaystyle\psi_{K^{\prime}}(P^{\prime})$
$\displaystyle\geq\frac{\varepsilon_{1}}{2}\geq\frac{\varepsilon_{0}^{0.01}}{2}\geq\frac{1}{2^{100/99}}\cdot\psi_{k^{\prime}}(P^{\prime})^{1/99}\geq\psi_{k^{\prime}}(P^{\prime})^{1/7},$
(5b) $\displaystyle\psi_{K^{\prime}}(P^{\prime})$
$\displaystyle\geq\frac{\varepsilon_{1}}{2}\geq e^{-5}.$ (5c)

where (5b) uses
$\varepsilon_{0}^{0.01}\geq(\psi_{k^{\prime}}(P^{\prime})/2)^{1/99}$ and
$\psi_{k^{\prime}}(P^{\prime})\leq 1/400$, both of which follow from (5a).

Let $r$ be a large constant that will be fixed below. By Lemma 3.9, we know
that there is a probabilistic polynomial $\bm{P^{\prime(r)}}$ of degree at
most $r\cdot\deg(P^{\prime})$ such that for each
$m\in\\{k^{\prime},K^{\prime}\\}$, we have
$\mathop{\textbf{E}}_{\bm{P^{\prime(r)}}}[\psi_{m}(\bm{P^{\prime(r)}})]=\psi_{m}(P^{\prime})^{r}.$

The proof will proceed by another restriction to $n^{\prime\prime}$ variables,
where $n^{\prime\prime}$ is defined to be the largest even integer such that
$100n^{\prime\prime}\leq q^{2}.$ We assume that $n^{\prime\prime}$ is greater
than a large enough absolute constant, since otherwise $q$ is upper bounded by
a fixed constant, in which case the degree bound to be proved is trivial. Note
that $\ell^{\prime\prime}:=q^{2}/n^{\prime\prime}\geq 100$ by definition. We
also have $n^{\prime\prime}=(q^{2}/100)-2,$ which implies that
$\ell^{\prime\prime}\leq 100+O(1)/q^{2}\leq 101$, as long as $q$ is greater
than a large enough absolute constant.

Relabel the variables so that $P^{\prime}$ is a polynomial in
$x_{1},\ldots,x_{n^{\prime}}.$ Let $\bm{T}$ be a uniformly random subset of
$[n^{\prime}]$ of size $n^{\prime}-n^{\prime\prime}$ and let $\bm{z}$ be a
uniformly random point in
$\\{0,1\\}^{n^{\prime}-n^{\prime\prime}}_{(n^{\prime}-n^{\prime\prime})/2}.$
Define the probabilistic polynomial $\bm{P^{\prime(r)}}_{\bm{T},\bm{z}}$
obtained by setting the variables indexed by $\bm{T}$ according to $\bm{z}$ in
the probabilistic polynomial $\bm{P^{\prime(r)}}.$ Let
$K^{\prime\prime}:=n^{\prime\prime}/2$ and
$k^{\prime\prime}:=k^{\prime}-(n^{\prime}-n^{\prime\prime})/2$. As above, we
have

$\mathop{\textbf{E}}_{\bm{P^{\prime(r)}},\bm{T},\bm{z}}[\psi_{k^{\prime\prime}}(\bm{P^{\prime(r)}}_{\bm{T},\bm{z}})]=\psi_{k^{\prime}}(P^{\prime})^{r}=:\varepsilon_{0}^{\prime}\phantom{xxx}\text{
and
}\phantom{xxx}\mathop{\textbf{E}}_{\bm{P^{\prime(r)}},\bm{T},\bm{z}}[\psi_{K^{\prime\prime}}(\bm{P^{\prime(r)}}_{\bm{T},\bm{z}})]=\psi_{K^{\prime}}(P^{\prime})^{r}=:\varepsilon_{1}^{\prime}.$

Let $r$ be the smallest positive integer so that
$\varepsilon_{0}^{\prime}=\psi_{k^{\prime}}(P^{\prime})^{r}\leq e^{-300}.$
Note that $r$ is upper bounded by an absolute constant, as
$\psi_{k^{\prime}}(P^{\prime})\leq 1/400$ by (5a). Further, we have
$\psi_{k^{\prime}}(P^{\prime})^{r-1}>e^{-300}$ and hence

$\varepsilon_{1}^{\prime}=\psi_{K^{\prime}}(P^{\prime})^{r}=\psi_{K^{\prime}}(P^{\prime})^{r-1}\cdot\psi_{K^{\prime}}(P^{\prime})\geq\left((\psi_{k^{\prime}}(P^{\prime}))^{r-1}\right)^{1/7}\cdot
e^{-5}>e^{-48}$

where the first inequality uses (5).

By Markov’s inequality as above, there is a fixed choice of
$\bm{P^{\prime(r)}},\bm{T},$ and $\bm{z}$ such that the corresponding
polynomial $P^{\prime\prime}$ is a polynomial on $n^{\prime\prime}$ variables
satisfying

$\psi_{k^{\prime\prime}}(P^{\prime\prime})\leq\frac{2\varepsilon_{0}^{\prime}}{\varepsilon_{1}^{\prime}}<e^{-210}<e^{-2\ell^{\prime\prime}}\phantom{xxx}\text{
and
}\phantom{xxx}\psi_{K^{\prime\prime}}(P^{\prime\prime})\geq\frac{\varepsilon_{1}^{\prime}}{2}>e^{-50}\geq
e^{-\ell^{\prime\prime}/2}.$

Applying Lemma 3.2 to $P^{\prime\prime}$ with error parameter
$\varepsilon=\frac{2\varepsilon_{0}^{\prime}}{\varepsilon_{1}^{\prime}}$
yields $\deg(P^{\prime\prime})\geq q/25.$ As $\deg(P^{\prime\prime})\leq
r\cdot\deg(P^{\prime}),$ we also get $\deg(P^{\prime})=\Omega(q)$, finishing
the proof in this case as well. (Note that the $\Omega(\cdot)$ hides an
absolute constant.)

###  3.3 Tightness of the Main Lemma (Lemma 3.1)

In this section, we discuss the near-optimality of Lemma 3.1 w.r.t. to the
various parameters. Fix $n,k,q,\alpha,\delta$ and $\mathbb{F}$ as in the
statement of Lemma 3.1. Assume that $K=k+q$ (the case when $K=k-q$ is similar)
and that $k\leq n/2$. Let $\varepsilon\in(0,1)$ be arbitrary.

First of all, we note that the degree lower bound obtained cannot be larger
than $q$, because by Corollary 2.8, it follows that there is a degree-$q$
polynomial that vanishes at all points of weight $k$ but no points of weight
$K$.

So, the statement of Lemma 3.1 proves a lower bound on the degree that nearly
(up to constant factors) matches this trivial upper bound, under the weaker
assumption that the polynomial is forced to be zero only on most (say a
$1-\varepsilon$ fraction) of $\\{0,1\\}^{n}_{k}$ and non-zero on most (say a
$1-\varepsilon$ fraction) of $\\{0,1\\}^{n}_{K}$. (Lemma 3.1 is a stronger
statement, but we will show that even this weaker statement is tight.)

In this section, we show that the value of $\varepsilon$ cannot be increased
beyond $\varepsilon=\exp(-O(\delta^{2}n/\alpha))$, if we want to prove a lower
bound of $\Omega(q)$ on the degree. More precisely, we show the following.

######  Theorem 3.12.

Assume that $\varepsilon=\exp(-o(\delta^{2}n/\alpha)).$ Then, there is a
polynomial $P$ of degree $o(q)$ such that

$\displaystyle\leq\varepsilon$ $\displaystyle\geq 1-\varepsilon.$

######  Proof 3.13.

To prove this theorem, we analyze a different polynomial construction to
achieve this based on sampling. We will need the following interpolation lemma
that can be found in a paper of Alman and Williams [4].888This lemma has a
trivial proof via univariate polynomial interpolation if we only want the
polynomial $Q$ to have rational coefficients. However, here it important that
$Q$ has integer coefficients.

######  Lemma 3.14.

Let $n$ be arbitrary and $I\subseteq[0,n]$ be any interval of integers. Given
any $f:I\rightarrow\\{0,1\\}$, there is a multilinear polynomial
$Q\in\mathbb{Z}[x_{1},\ldots,x_{n}]$ of degree at most $|I|-1$ such that
$Q(a)=f(|a|)$ for each $a\in\bigcup_{i\in I}\\{0,1\\}^{n}_{i}$.

Fix any positive integer $m$. By Lemma 3.14, it follows that there is a
multilinear polynomial $Q\in\mathbb{Z}[y_{1},\ldots,y_{m}]$ of degree
$O(\delta m)$ such that $Q(b)=0$ for each $b\in\\{0,1\\}^{m}$ such that
$|b|\in((\alpha-\delta/2)m,(\alpha+\delta/2)m)$ and $Q(b)=1$ for each
$b\in\\{0,1\\}^{m}$ such that
$|b|\in((\alpha+\delta/2)m,(\alpha+3\delta/2)m)$. Reducing the coefficients
modulo $p$, we obtain a polynomial
$\tilde{Q}\in\mathbb{F}[y_{1},\ldots,y_{m}]$ with the same property. Fix this
$\tilde{Q}.$

Consider the probabilistic polynomial $\bm{P}(x_{1},\ldots,x_{n})$ defined as
follows. Choose $\bm{i_{1}},\ldots,\bm{i_{m}}$ i.u.a.r. from $[n]$ where
$m=C\cdot(\alpha/\delta^{2})\log(1/\varepsilon)$ for a large enough constant
$C$ we will fix below. We define $\bm{P}(x_{1},\ldots,x_{n})$ to be the
polynomial $\tilde{Q}(x_{\bm{i_{1}}},\ldots,x_{\bm{i_{m}}})$. Note that

$\deg(\bm{P})\leq\deg(Q)=O(\delta
m)=O((\alpha/\delta)\log(1/\varepsilon))=o(\delta n)=o(q)$

where the second-last equality uses our assumption that
$\varepsilon=\exp(-o(\delta^{2}n/\alpha)).$

Let $a\in\\{0,1\\}^{n}_{k}$ be arbitrary. We analyze the random variable
$\bm{P}(a)$. Note that as long as the Hamming weight of
$\bm{b}=(a_{\bm{i_{1}}},\ldots,a_{\bm{i_{m}}})$ is in the interval
$((\alpha-\delta/2)m,(\alpha+\delta/2)m)$, we have $\bm{P}(a)=0.$ As each co-
ordinate of $\bm{b}$ is $1$ with probability $k/n=\alpha\in[0,1/2]$,
Bernstein’s inequality (Lemma 2.1) yields

$\displaystyle\leq$

as long as $C$ is a large enough constant. In a similar way, we also see that
for any $a\in\\{0,1\\}^{n}_{K}$, we have and hence, in particular, , as long
as $C$ is a large enough constant.

In particular, by Markov’s inequality and the union bound, we see that there
is a $P$ of degree at most $\deg(\bm{P})$ such that

$\psi_{k}(P)\leq\varepsilon\phantom{xxxx}\text{ and
}\phantom{xxxx}\psi_{K}(P)\geq 1-\varepsilon.$

Thus, we have a polynomial $P$ as claimed in Theorem 3.12.

###  3.4 An extension to the case when $q$ is not a power of $p$

An anonymous reviewer suggested the following extension of the main lemma
(Lemma 3.1). We prove this by a simple reduction to the main lemma. (This
leads to a worsening in the constants involved.)

######  Lemma 3.15 (An extension to the case when $q$ is not a power of $p$).

Assume that $\mathbb{F}$ is a field of characteristic $p$. Let $n$ be a
growing parameter and assume we have positive integer parameters $k,q$ such
that $200q<k<n-200q$. Let $q^{\prime}$ be the largest power of $p$ that
divides $q$ and assume $q=q^{\prime}s$. Define $\alpha=\min\\{k/n,1-(k/n)\\}$
and $\delta=q/n$. Assume that $Q\in\mathbb{F}[x_{1},\ldots,x_{n}]$ is a
polynomial such that for some $K\in\\{k+q,k-q\\}$,

$\displaystyle\leq\min\\{e^{-1000\delta^{2}n/s\alpha},1/2000\\}$ (6a)
$\displaystyle\geq e^{-\delta^{2}n/1000s\alpha}.$ (6b)

Then, $\deg(Q)=\Omega(q^{\prime}),$ where the $\Omega(\cdot)$ hides an
absolute constant.

######  Remark 3.16.

The ‘non-robust’ version of this lemma (when $Q$ vanishes everywhere on
$\\{0,1\\}^{n}_{k}$ but not on some point in $\\{0,1\\}^{n}_{K}$) yields a
degree lower bound of $q^{\prime}$, and can be proved using similar techniques
to those used in proving Hegedűs’s lemma. A proof can be found in [44].

######  Remark 3.17.

As in the case of the main lemma, the degree lower bound obtained above is
tight, using the same reasoning as in Section 3.3.

######  Proof 3.18.

W.l.o.g. assume $K=k+q$.

Let $k^{\prime}=\lfloor k/s\rfloor$ and $n^{\prime}=\lfloor n/s\rfloor-1$. Our
aim will be to show using the polynomial $Q$ that there is a polynomial $P$ on
$n^{\prime}$ variables that distinguishes between Hamming weights $k^{\prime}$
and $K^{\prime}:=k^{\prime}+q^{\prime}$. We will then appeal to Lemma 3.1 to
get the degree lower bound.

It is easy to check that $100q^{\prime}<k^{\prime}<n^{\prime}-100q^{\prime}$
as

$\displaystyle 100q^{\prime}s=100q$ $\displaystyle<k-q<(k^{\prime}+1)s-q\leq
k^{\prime}s$ $\displaystyle k^{\prime}s\leq k<n-102q$
$\displaystyle<(n^{\prime}+2)s-102q\leq
n^{\prime}s-100q=(n^{\prime}-100q^{\prime})s$

where we used the hypotheses that $200q<k<n-200q.$

We construct the polynomial $P$ as follows. Assume that $k=k^{\prime}s+r_{1}$
and $n=n^{\prime}s+s+r_{2}$ for $r_{1},r_{2}\in\\{0,\ldots,s-1\\}.$ On an
input $x\in\\{0,1\\}^{n^{\prime}}$, we consider the _random_ input
$\bm{y}\in\\{0,1\\}^{n}$ defined as follows.

  * •

Each co-ordinate of $x$ is repeated $s$ times to get an
$X\in\\{0,1\\}^{sn^{\prime}}$.

  * •

We concatenate $X$ with the string $1^{r_{1}}0^{s+r_{2}-r_{1}}$ to get a
string $Y\in\\{0,1\\}^{n}.$

  * •

A uniformly random permutation $\bm{\pi}$ is applied to the $n$ coordinates of
$Y$ to get $\bm{y}.$

Finally, we define the probabilistic polynomial $\bm{P}(x):=Q(\bm{y}).$ For a
fixed permutation $\bm{\pi}$, each coordinate of $\bm{y}$ is a polynomial of
degree at most $1$ in the variables $x_{1},\ldots,x_{n^{\prime}},$ and hence,
$\deg(\bm{P})\leq\deg(Q).$ We will show that there is some polynomial $P$ in
the support of $\bm{P}$ that has the desired properties.

Let $\varepsilon_{0}$ and $\varepsilon_{1}$ denote the right hand sides of
inequalities (6a) and (6b) respectively. Observe that when
$x\in\\{0,1\\}^{n^{\prime}}_{w}$, then the random $\bm{y}\in\\{0,1\\}^{n}$ is
uniformly distributed over $\\{0,1\\}^{n}_{ws+r_{1}}.$ In particular, setting
$w=k^{\prime}$ and $k^{\prime}+q^{\prime}$, we get the following.

$\displaystyle\leq\varepsilon_{0}$ $\displaystyle\geq\varepsilon_{1}.$

To find a suitable fixing of $\bm{P}$, we consider two cases.

  * •

Case 1: $e^{-\delta^{2}n/250s\alpha}\geq 1/2$: In this case, define two events
$\mathcal{E}_{0}$ and $\mathcal{E}_{1}$ (depending only on the probabilistic
polynomial $\bm{P}$) as follows.

$\mathcal{E}_{0}:=$

where $\zeta_{1}:=1-\varepsilon_{1}.$ Note that
$\varepsilon_{1}=e^{-\delta^{2}n/1000s\alpha}\geq 2^{-0.25}>0.8$ and hence
$\zeta_{1}<0.2.$

By Markov’s inequality, with positive probability over the choice of $\bm{P}$,
neither of the above events occurs. Fix such a polynomial $P$. Then, we have

$\displaystyle<2\varepsilon_{0}=\min\\{2e^{-1000\delta^{2}n/s\alpha},2/2000\\}$
$\displaystyle\leq\min\\{e^{-200\delta^{2}n/s\alpha},1/1000\\},$ (7)

where we used the simple fact that for any non-negative real number $\gamma$,
we have the inequality
$\min\\{2\gamma,1/1000\\}\leq\min\\{\gamma^{0.2},1/1000\\}$. We also have

(8)

where the second inequality uses the fact that $\zeta_{1}\leq 0.2$ for any
$\gamma\in[0,1],$ we have999This is a special case of the Boole-Bonferroni
inequalities, which are closely related to the Principle of Inclusion-
Exclusion. $(1-\gamma)^{5}\leq 1-5\gamma+10\gamma^{2}$.

  * •

Case 2: $e^{-\delta^{2}n/250s\alpha}<1/2$: In this case, we proceed
analogously, but define the ‘bad’ events as follows.

$\mathcal{E}_{0}^{\prime}:=$

By Markov’s inequality, there is again a fixing $P$ of $\bm{P}$ such that
neither of the above two events occurs. For such a polynomial $P$, we have

(9)

where the second inequality used our assumption that
$e^{-\delta^{2}n/250s\alpha}<1/2$. We also have

$\displaystyle<\frac{\varepsilon_{0}}{\varepsilon_{1}/2}\leq
e^{\delta^{2}n/200s\alpha}\cdot\varepsilon_{0}\leq
e^{-999\delta^{2}n/s\alpha}$ $\displaystyle\leq
e^{200\delta^{2}n/s\alpha}\leq\min\\{e^{-200\delta^{2}n/s\alpha},1/1000\\},$
(10)

where the second inequality used (9) above and the third and last inequalities
use the fact that $e^{-\delta^{2}n/250s\alpha}<1/2$ to deduce that
$e^{-1000\delta^{2}n/s\alpha}\leq 1/2000$ and
$e^{-200\delta^{2}n/s\alpha}<1/1000$ respectively.

Putting (7), (8), (10) and (9) together gives us that in both cases we have

$\displaystyle\leq\min\\{e^{-200\delta^{2}n/s\alpha},1/1000\\}$ (11a)
$\displaystyle\geq e^{-\delta^{2}n/200s\alpha}.$ (11b)

To apply Lemma 3.1 to $P$, we need to relate the above bounds to quantities
defined in terms of $\delta^{\prime}:=q^{\prime}/n^{\prime}$ and
$\alpha^{\prime}:=k^{\prime}/n^{\prime}.$ We claim that

$\frac{\delta^{2}n}{s\alpha}\leq\frac{(\delta^{\prime})^{2}n^{\prime}}{\alpha^{\prime}}\leq\frac{2\delta^{2}n}{s\alpha}.$
(12)

Assuming these inequalities, we observe that $P$ satisfies the hypotheses of
Lemma 3.1. Applying this lemma gives us

$\deg(Q)\geq\deg(\bm{P})\geq\deg(P)=\Omega(q^{\prime}),$

finishing the proof of Lemma 3.15.

It remains to prove (12), which is a simple calculation.

$\displaystyle\frac{(\delta^{\prime})^{2}n^{\prime}}{\alpha^{\prime}}$
$\displaystyle=\frac{(\delta^{\prime}n^{\prime})^{2}}{\alpha^{\prime}n^{\prime}}=\frac{(q^{\prime})^{2}}{k^{\prime}}=\frac{(q^{\prime}s)^{2}}{k^{\prime}s^{2}}\geq\frac{q^{2}}{sk}=\frac{\delta^{2}n}{s\alpha},$
$\displaystyle\frac{(\delta^{\prime})^{2}n^{\prime}}{\alpha^{\prime}}$
$\displaystyle=\frac{(q^{\prime})^{2}}{k^{\prime}}=\frac{(q^{\prime}s)^{2}}{k^{\prime}s^{2}}\leq\frac{q^{2}}{s(k-s)}=\frac{\delta^{2}n}{s\alpha}\cdot\left(1-\frac{s}{k}\right)^{-1}\leq\frac{2\delta^{2}n}{s\alpha}$

where the final inequality uses the fact that $\frac{s}{k}\leq\frac{q}{k}\leq
0.01.$

##  4 Applications

###  4.1 Tight Degree Lower Bounds for the Coin Problem

We start with a definition.

######  Definition 4.1 (The $\delta$-Coin Problem).

For any $\alpha\in[0,1]$ and integer $n\geq 1$, let $\mu_{\alpha}^{n}$ be the
product distribution over $\\{0,1\\}^{n}$ obtained by setting each bit to $1$
independently with probability $\alpha.$ Let $\delta\in(0,1)$ be a parameter.

Given a function $g:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, we say that _$g$
solves the $\delta$-coin problem with error $\varepsilon$_ if

(13)

(This definition is sometimes [31] stated in terms of the distributions
$\mu_{(1/2)-\delta}$ and $\mu_{(1/2)+\delta}$. This is essentially equivalent
to the definition above.)

Let $\mathbb{F}$ be a prime field of characteristic $p$, where $p$ is a fixed
constant. We consider here the minimum degree of a polynomial
$P\in\mathbb{F}[x_{1},\ldots,x_{n}]$ that solves the $\delta$-coin problem
with error $\varepsilon.$

By Lemma 3.14, for any $n\geq 1$, there is a polynomial
$P\in\mathbb{F}[x_{1},\ldots,x_{n}]$ of degree $O(\delta n)$ that outputs $0$
on all inputs of weight $w\in(n((1/2)-3\delta/2),n(1/2-\delta/2))$ and $1$ on
all inputs of weight $(n(1/2-\delta/2),n(1/2+\delta/2)).$ Using Lemma 2.1
(Bernstein’s inequality), it can be easily checked that $P$ solves the
$\delta$-coin problem with error $\varepsilon$ as long as $n\geq
C\frac{1}{\delta^{2}}\log(1/\varepsilon)$ for some large enough constant
$C>0$. This yields a polynomial $P$ of degree
$O(\frac{1}{\delta}\log(1/\varepsilon))$.

In earlier work [31], we showed that this was tight for constant
$\varepsilon.$ That is, we showed that any polynomial $P$ that solves the
$\delta$-coin problem with error at most $1/10$ (say) must have degree
$\Omega(1/\delta).$ This was also implied by an independent result of
Chattopadhyay, Hosseini, Lovett and Tal [13] (see [2]). Both proofs relied on
slight strengthenings of Smolensky’s [41] lower bound on polynomials
approximating the Majority function. It is not clear from these proofs,
however, if this continues to be true for subconstant $\varepsilon.$ The main
lemma (Lemma 3.1), or even its simpler version Lemma 3.2, shows that this is
indeed true.

######  Theorem 4.2 (Tight Degree Lower Bound for the $\delta$-coin problem
for all errors).

Assume $\mathbb{F}$ has characteristic $p$ and $\delta,\varepsilon$ are
parameters going to $0$. Let $N\geq 1$ be any positive integer. Any polynomial
$P\in\mathbb{F}[x_{1},\ldots,x_{N}]$ that solves the $\delta$-coin problem
with error $\varepsilon$ must have degree
$\Omega(\frac{1}{\delta}\log(1/\varepsilon)).$

######  Proof 4.3.

We assume that $\varepsilon$ is smaller than some small enough constant
$\varepsilon_{0}$ (for larger $\varepsilon$, we can just appeal to the lower
bound of [31]).

Assume for now that $\delta=1/k$ for some integer $k\geq 1$. Fix $n$ to be the
least even integer such that $n\geq\frac{C}{\delta^{2}}\log(1/\varepsilon)$
for a large constant $C$ and $q:=\delta n$ is a power of the characteristic
$p$. Note that $n\leq
O(p)\cdot\frac{C}{\delta^{2}}\log(1/\varepsilon)=O(\frac{1}{\delta^{2}}\log(1/\varepsilon))$
as $p$ is a constant. Define the probabilistic polynomial
$\bm{Q}\in\mathbb{F}[y_{1},\ldots,y_{n}]$ obtained from $P$ by randomly
replacing each variable of $P$ by a uniformly random variable among
$y_{1},\ldots,y_{n}$. For any $a\in\\{0,1\\}^{n}_{n/2}$, we have

and similarly for $a\in\\{0,1\\}^{n}_{(n/2)-q}$, we have . In particular, by
Markov’s inequality, there is a fixed polynomial $Q$ of degree at most
$\deg(P)$ that satisfies

Hence, by Lemma 3.2, we have $\deg(P)=\Omega(\delta
n)=\Omega(\frac{1}{\delta}\log(1/\varepsilon)).$

Now, if $\delta$ is not of the assumed form, we consider $k$ be the largest
integer such that $\delta\leq 1/k$ and set $\delta^{\prime}:=1/k$. Define
$\alpha\in(0,1)$ by $\alpha=\delta/\delta^{\prime}.$ Note that if
$\bm{a},\bm{b}\in\\{0,1\\}$ are sampled independently from the distributions
$\mu_{1/2-\delta^{\prime}}^{1}$ and $\mu_{1/2-(\alpha/2)}^{1}$ respectively,
then their parity $\bm{a}\oplus\bm{b}$ has the distribution
$\mu_{1/2-\delta}^{1}.$ Now, if we define the probabilistic polynomial
$\bm{R}(x_{1},\ldots,x_{n})$ by

$\bm{R}(x_{1},\ldots,x_{n})=P(x_{1}\oplus\bm{y}_{1},\ldots,x_{n}\oplus\bm{y}_{n})$

where $\bm{y}=(\bm{y}_{1},\ldots,\bm{y}_{n})$ is sampled from
$\mu_{1/2-(\alpha/2)}^{n},$ then $\bm{R}$ solves the $\delta^{\prime}$-coin
problem with error at most $\varepsilon.$ Note also that
$\deg(\bm{R})\leq\deg(P)$ as for each fixed $\bm{y},$ each
$x_{i}\oplus\bm{y}_{i}$ is a linear function of $x_{i}$.

Repeating the above argument with $\bm{R}$ instead of $P$ yields that
$\deg(\bm{R})=\Omega(\frac{1}{\delta^{\prime}}\log(1/\varepsilon))=\Omega(\frac{1}{\delta}\log(1/\varepsilon)).$
We thus get the same lower bound for $\deg(P).$

###  4.2 Tight Probabilistic Degree Lower bounds for Positive Characteristic

We start with some basic notation and definitions and then state our result.

Throughout this section, let $\mathbb{F}$ be a field of fixed (i.e.
independent of $n$) characteristic $p>0$. The main theorem of this section
characterizes (up to constant factors) the $\varepsilon$-error probabilistic
degree of every symmetric function and for almost all interesting values of
$\varepsilon$.

######  Theorem 4.4 (Probabilistic Degree lower bounds over positive
characteristic).

Let $n\in\mathbb{N}$ be a growing parameter. Let $f\in s\mathcal{B}_{n}$ be
arbitrary and let $(g,h)$ be a standard decomposition of $f$ (see Section 2
for the definition). Then for any $\varepsilon\in[1/2^{n},1/3]$, we have

$\mathrm{pdeg}_{\varepsilon}^{\mathbb{F}}(f)=\left\\{\begin{array}[]{ll}\Omega(\sqrt{n\log(1/\varepsilon)})&\text{if
$\mathrm{per}(g)>1$ and not a power of $p$,}\\\
\Omega(\min\\{\sqrt{n\log(1/\varepsilon)},\mathrm{per}(g)\\})&\text{if
$\mathrm{per}(g)$ a power of $p$ and $B(h)=0$,}\\\
\Omega(\min\\{\sqrt{n\log(1/\varepsilon)},\mathrm{per}(g)&\text{otherwise.}\\\
\ \ +\sqrt{B(h)\log(1/\varepsilon)}+\log(1/\varepsilon)\\})\end{array}\right.$

Here the $\Omega(\cdot)$ notation hides constants depending on the
characteristic $p$ of the field $\mathbb{F}.$

Note that this matches the upper bound construction from Theorem 2.3.

####  4.2.1 Some Preliminaries

######  Definition 4.5 (Restrictions).

Given functions $f\in s\mathcal{B}_{n}$ and $g\in s\mathcal{B}_{m}$ where
$m\leq n$, we say that $g$ is a restriction of $f$ if there is some
$a\in[0,n-m]$ such that the identity

$g(x)=f(x1^{a}0^{n-m-a})$

holds for every $x\in\\{0,1\\}^{n}$. Or equivalently, that $g$ can be obtained
from $f$ by setting some inputs to $0$ and $1$ respectively.101010Note that
exactly which inputs are set to $0$ or $1$ is not important, since we are
dealing with _symmetric_ Boolean functions.

We will use the following obvious fact freely. If $g$ is a restriction of $f$,
then for any $\delta>0$,
$\mathrm{pdeg}_{\delta}(g)\leq\mathrm{pdeg}_{\delta}(f).$

In earlier work with Tripathi and Venkitesh [43], we showed the following
near-optimal lower bound on the probabilistic degrees of Threshold functions.

######  Lemma 4.6 (Lemma 27 in [43]).

Assume $t\geq 1$. For any $\varepsilon\in[2^{-n},1/3],$

$\mathrm{pdeg}_{\varepsilon}(\mathrm{Thr}_{n}^{t})=\Omega(\sqrt{\min\\{t,n+1-t\\}\log(1/\varepsilon)}+\log(1/\varepsilon)).$

(The corresponding lemma in [43] is only stated for $t\leq n/2$. However, as
$\mathrm{Thr}^{n+1-t}_{n}(x)=1-\mathrm{Thr}^{t}_{n}(1-x_{1},\ldots,1-x_{n}),$
the above lower bound holds for $t>n/2$ also.)

The following classical results of Smolensky prove optimal lower bounds on the
probabilistic degrees of some interesting classes of symmetric functions.

######  Lemma 4.7 (Smolensky’s lower bound for Majority function [45, 42]).

For any field $\mathbb{F}$, any $\varepsilon\in(1/2^{n},1/5),$ we have

$\mathrm{pdeg}_{\varepsilon}^{\mathbb{F}}(\mathrm{Maj}_{n})=\Omega(\sqrt{n\log(1/\varepsilon)}).$

######  Lemma 4.8 (Smolensky’s lower bound for MOD functions [41]).

For $2\leq b\leq n/2$, any $\mathbb{F}$ such that $\text{char}(\mathbb{F})$ is
either zero or coprime to $b$, any $\varepsilon\in(1/2^{n},1/(3b))$, there
exists an $i\in[0,b-1]$ such that

$\mathrm{pdeg}_{\varepsilon}^{\mathbb{F}}(\mathrm{MOD}^{b,i}_{n})=\Omega(\sqrt{n\log(1/b\varepsilon)}).$

We now show how to use our robust version of Hegedűs’s lemma to prove Theorem
4.4. In fact, Lemma 3.2 will suffice for this application.

####  4.2.2 Strategy and two simple examples

The probabilistic degree lower bounds below will use the following corollary
of Lemma 3.2.

######  Corollary 4.9.

Let $n$ be a growing parameter and assume
$\varepsilon\in[2^{-n/100},e^{-200}].$ Assume $t$ is an integer such that $t$
is a power of $p$ and furthermore, $t=\sqrt{n\ell}$ for some
$\ell\in\mathbb{R}$ such that
$100\leq\ell\leq\frac{1}{2}\cdot\ln(1/\varepsilon).$ Let $h\in
s\mathcal{B}_{n}$ be any function such that $\mathrm{Spec}\,h(\lfloor
n/2\rfloor)\neq\mathrm{Spec}\,h(\lfloor n/2\rfloor-t)$. Then,
$\mathrm{pdeg}_{\varepsilon}(h)=\Omega(t).$

######  Proof 4.10.

By error reduction for probabilistic polynomials (Fact 3 item 1), it suffices
to prove an $\Omega(t)$ lower bound on $\mathrm{pdeg}_{\varepsilon/2}(h).$

Assume without loss of generality that $\mathrm{Spec}\,h(\lfloor
n/2\rfloor)=1$ and $\mathrm{Spec}\,h(\lfloor n/2\rfloor-t)=0.$ Let $\bm{P}$ be
an $(\varepsilon/2)$-error probabilistic polynomial for $h$. Then, we have

$\displaystyle\leq\varepsilon/2$ $\displaystyle\leq\varepsilon/2$

Thus, we have

$\mathop{\textbf{E}}_{\bm{P}}[$

and hence, by averaging, there is a polynomial $P$ in the support of the
distribution of $\bm{P}$ such that

Applying Lemma 3.2 to $P$ yields

$\deg(\bm{P})\geq\deg(P)=\Omega(t).$

To illustrate the usefulness of Corollary 4.9, we prove optimal lower bounds
on the probabilistic degrees for two interesting classes of functions (both of
which will be subsumed by Theorem 4.4).

######  Corollary 4.11.

Let $\varepsilon\in(0,1/3]$ be a constant. Let $q$ be any integer relatively
prime to $p$ such that $q\leq 0.99n.$ Then the $\varepsilon$-error
probabilistic degrees of $\mathrm{EThr}_{n}^{\lfloor n/2\rfloor}$ and
$\mathrm{MOD}_{n}^{q}$ are $\Omega(\sqrt{n}).$

Known lower bounds (Lemmas 4.7 and 4.8) can be used to prove similar lower
bounds to the one given above, but with additional log-factor losses (see
Lemma 4.8, which requires the error to be subconstant, and [43]). However, we
do not know how to prove the above tight (up to constants) lower bound without
appealing to Lemma 3.2. In particular, we do not know how to prove the above
in characteristic $0$.

######  Proof 4.12.

We use Corollary 4.9. We will use $\mathrm{EThr}_{n}^{\lfloor n/2\rfloor}$ and
$\mathrm{MOD}_{n}^{q}$ to construct functions that distinguish between weights
$\lfloor n/2\rfloor$ and $\lfloor n/2\rfloor-t$ for suitable
$t=\Omega(\sqrt{n}).$ Corollary 4.9 then implies the required lower bound.

For $h=\mathrm{EThr}_{n}^{\lfloor n/2\rfloor}$, note that
$\mathrm{Spec}\,h(\lfloor n/2\rfloor)\neq\mathrm{Spec}\,h(\lfloor
n/2\rfloor-t)$ for any $t<\lfloor n/2\rfloor$. In particular, setting $t$ to
be the smallest power of $p$ such that $t\geq\sqrt{100n}$ and
$\varepsilon_{0}=e^{-2t^{2}/n},$ we get by Corollary 4.9 that
$\mathrm{pdeg}_{\varepsilon_{0}}(h)=\Omega(t)=\Omega(\sqrt{n}).$ By error-
reduction for probabilistic polynomials (Fact 3 item 1), we also have the same
lower bound (up to constant factors) for any $\varepsilon\leq 1/3.$ This
proves the claim in the case that $h=\mathrm{EThr}_{n}^{\lfloor n/2\rfloor}.$

For $h=\mathrm{MOD}_{n}^{q}$, we make some minor modifications to the above
idea. Let $r\in[0,q-1]$ be such that $r+\lfloor(n-q)/2\rfloor\equiv
0\pmod{q}.$ Define $h^{\prime}\in s\mathcal{B}_{n-q}$ by

$h^{\prime}(x)=h(x1^{r}0^{q-r}).$

Set $t$ to be the smallest power of $p$ such that $t\geq\sqrt{100(n-q)}$ and
$\varepsilon_{0}=e^{-2t^{2}/(n-q)}.$ Note that
$\mathrm{Spec}\,h^{\prime}(\lfloor(n-q)/2\rfloor)=\mathrm{Spec}\,h(r+\lfloor(n-q)/2\rfloor)=1$
as $r+\lfloor(n-q)/2\rfloor\equiv 0\pmod{q}.$ On the other hand,
$r+\lfloor(n-q)/2\rfloor-t\not\equiv 0\pmod{q}$ as $t$ is a power of $p$ and
hence not divisible by $q$, which implies that
$\mathrm{Spec}\,h^{\prime}(\lfloor(n-q)/2\rfloor-t)=0$. Thus, by Corollary
4.9, we get
$\mathrm{pdeg}_{\varepsilon_{0}}(h^{\prime})=\Omega(t)=\Omega(\sqrt{n}).$

####  4.2.3 Proof of Theorem 4.4

The proof of this theorem closely follows our probabilistic degree lower
bounds in [43] with careful modifications to avoid the log-factor losses
therein.

Let $f\in s\mathcal{B}_{n}$ be arbitrary and let $(g,h)$ be a standard
decomposition of $f$.

We start with a lemma that proves lower bounds on
$\mathrm{pdeg}_{\varepsilon}(f)$ as long as $\mathrm{per}(g)$ is large.

######  Lemma 4.13.

Fix any $\varepsilon\in[2^{-n},1/3].$ Assume that $f$ is such that
$\mathrm{per}(g)>\sqrt{n\log(1/\varepsilon)}.$ Then

$\mathrm{pdeg}_{\varepsilon}(f)=\Omega(\sqrt{n\log(1/\varepsilon)}).$

######  Proof 4.14.

We first prove the lemma under the assumption that
$\varepsilon\in[2^{-n/1000},e^{-10000p^{2}}].$

Fix $m$ to be the largest power of $p$ upper bounded by
$\frac{1}{4}\sqrt{n\log(1/\varepsilon)}$.

Since $\mathrm{per}(g)>\sqrt{n\log(1/\varepsilon)}\geq m,$ there is no
function $g^{\prime}\in s\mathcal{B}_{n}$ that has period $m$ and agrees with
$f$ on the interval $I:=[\lceil n/3\rceil+1,\lfloor 2n/3\rfloor].$ Thus, there
exists some $r\in I$ such that $r+m\in I$ and
$\mathrm{Spec}\,f(r)\neq\mathrm{Spec}\,f(r+m).$

Let $k=\lceil n/2\rceil$. Note that $r\geq\lceil n/3\rceil\geq k/2$ and
$r+m\leq\lfloor 2n/3\rfloor.$ Define $F\in s\mathcal{B}_{k}$ by setting

$F(x)=f(x1^{a}0^{b})$

where $a=r+m-\lfloor k/2\rfloor$ and $b=n-k-a$ (it can be checked that $a,b$
are non-negative for parameters $r,m,k$ as above). Note that
$\mathrm{Spec}\,F(\lfloor k/2\rfloor)=\mathrm{Spec}\,f(\lfloor
k/2\rfloor+a)=\mathrm{Spec}\,f(r+m)$ and similarly that
$\mathrm{Spec}\,F(\lfloor k/2\rfloor-m)=\mathrm{Spec}\,f(r).$ We thus obtain
$\mathrm{Spec}\,F(\lfloor k/2\rfloor)\neq\mathrm{Spec}\,F(\lfloor
k/2\rfloor-m).$

Note that by the bounds on $\varepsilon$ assumed above

$m\geq\frac{1}{4p}\sqrt{n\log(1/\varepsilon)}\geq 20\sqrt{n}.$ (14)

Using Corollary 4.9, we hence get

$\mathrm{pdeg}_{\varepsilon}(f)\geq\mathrm{pdeg}_{\varepsilon/2}(F)=\Omega(m)=\Omega(\sqrt{n\log(1/\varepsilon)})$

which proves the lemma under the assumption on $\varepsilon$ above. (We use
the bounds on $\varepsilon$ to ensure that $2^{-k/200}\leq\varepsilon\leq
e^{-2m^{2}/k},$ which is part of the hypothesis of Corollary 4.9.)

If $\varepsilon\in[2^{-n},2^{-n/10000p^{2}}],$ then for
$\varepsilon_{0}=2^{-n/10000p^{2}},$ we have

$\mathrm{pdeg}_{\varepsilon}(f)\geq\mathrm{pdeg}_{\varepsilon_{0}}(f)=\Omega(\sqrt{n\log(1/\varepsilon_{0})})=\Omega(\sqrt{n\log(1/\varepsilon)})$

which implies the desired lower bound.111111Note that we assume that the
characteristic is a fixed positive constant and hence the $\Omega(\cdot)$ can
hide constants depending on $p$.

On the other hand, if $\varepsilon>e^{-10000p^{2}}$, we proceed as follows. We
construct $F$ as above, but we may no longer have $m\geq 20\sqrt{n}$ as
implied by (14). However, for $F^{\prime}\in s\mathcal{B}_{k^{\prime}}$
defined by

$F^{\prime}(x)=F(x0^{t}1^{t})$

for suitably chosen $t\leq k/2$, we can ensure that
$m\in[10\sqrt{k^{\prime}},20\sqrt{k^{\prime}}].$ Note that
$\mathrm{Spec}\,F^{\prime}(\lfloor
k^{\prime}/2\rfloor)=\mathrm{Spec}\,F(\lfloor k/2\rfloor)$ and
$\mathrm{Spec}\,F^{\prime}(\lfloor
k^{\prime}/2\rfloor-m)=\mathrm{Spec}\,F(\lfloor k/2\rfloor-m)$. Hence, for
$\varepsilon_{1}=e^{-10000}$, Corollary 4.9 implies

$\mathrm{pdeg}_{\varepsilon_{1}}(f)\geq\mathrm{pdeg}_{\varepsilon_{1}}(F^{\prime})=\Omega(m)=\Omega(\sqrt{n\log(1/\varepsilon_{1})}).$

By error reduction (Fact 3 item 1), the same lower bound holds for
$\mathrm{pdeg}_{\varepsilon}(f)$ as well.

The next lemma allows us to prove a weak lower bound on
$\mathrm{pdeg}_{\varepsilon}(f)$ depending only on its periodic part $g$.

######  Lemma 4.15.

For any $\varepsilon\in[2^{-n},1/3],$

$\mathrm{pdeg}_{\varepsilon}(f)\geq\begin{cases}\Omega(\sqrt{n\log(1/\varepsilon)}),&\text{if
}\mathrm{per}(g)\text{ is not a power of }p\\\
\Omega(\min\\{\mathrm{per}(g),\sqrt{n\log(1/\varepsilon)}\\}),&\text{if
}\mathrm{per}(g)\text{ is a power of }p.\end{cases}$

######  Proof 4.16.

By Fact 3 item 1 (error reduction), we know that
$\mathrm{pdeg}_{\varepsilon}(g)=\Theta(\mathrm{pdeg}_{\delta}(g))$ as long as
$\delta=\varepsilon^{\Theta(1)}.$ In particular, we may assume without loss of
generality that $\varepsilon\in[2^{-n/10000},e^{-10000p^{2}}].$

Let $b:=\mathrm{per}(g)$. If $\mathrm{per}(g)>\sqrt{n\log(1/\varepsilon)}$, we
are done by Lemma 4.13. So we assume that $b\leq\sqrt{n\log(1/\varepsilon)}.$
In particular, this implies that $b\leq n/100.$

We have two cases.

######  $b$ is not a power of $p$.

Let $n_{1}$ be the largest power of $p$ upper bounded by
$\frac{1}{4}\sqrt{n\log(1/\varepsilon)}.$ By the constraints on $\varepsilon$,
we have $10\sqrt{n}\leq n_{1}\leq n/100.$

Let $b_{1}\in[0,b-1]$ such that $b_{1}\equiv n_{1}\pmod{b}$; note that
$b_{1}\neq 0$ as $b$ is not a power of $p$. As $b_{1}$ is smaller than
$b=\mathrm{per}(g)$, there must exist $r\in[0,n-b_{1}]$ such that

$\mathrm{Spec}\,g(r)\neq\mathrm{Spec}\,g(r+b_{1}).$

Assume that we choose the smallest $r\geq n/2$ so that this condition holds.
Then we have $r\leq n/2+b\leq 51\cdot n/100.$ Fix this $r$. As
$\mathrm{Spec}\,g(r)\neq\mathrm{Spec}\,g(r+b_{1}),$ we also have
$\mathrm{Spec}\,g(r)\neq\mathrm{Spec}\,g(r+b_{1}+k\cdot b)$ for any integer
$k$ such that $0\leq r+b_{1}+kb\leq n.$ In particular, as $b_{1}\equiv
n_{1}\pmod{b},$ we note that
$\mathrm{Spec}\,g(r)\neq\mathrm{Spec}\,g(r+n_{1}).$ As $n_{1}\leq n/100,$ we
have

$n/2\leq r\leq r+n_{1}\leq n/2+n/50.$

As $\mathrm{Spec}\,g(i)=\mathrm{Spec}\,f(i)$ for all $i\in[\lceil
n/3\rceil+1,\lfloor 2n/3\rfloor]$, we have
$\mathrm{Spec}\,f(r)\neq\mathrm{Spec}\,f(r+n_{1}).$ Without loss of
generality, we assume that $\mathrm{Spec}\,f(r)=0$ and
$\mathrm{Spec}\,f(r+n_{1})=1.$

Let $m=\lceil n/2\rceil.$ We define $F\in s\mathcal{B}_{m}$ as follows.

$F(x)=f(x1^{a}0^{n-m-a})$

where $a$ is chosen so that $\mathrm{Spec}\,F(\lfloor
m/2\rfloor)=\mathrm{Spec}\,f(r+n_{1})=1$. This also has the consequence that
$\mathrm{Spec}\,F(\lfloor m/2\rfloor-n_{1})=\mathrm{Spec}\,f(r)=0.$ By
Corollary 4.9, we get
$\mathrm{pdeg}_{\varepsilon}(F)=\Omega(n_{1})=\Omega(\sqrt{n\log(1/\varepsilon)}),$
proving the lemma in this case.

######  $b$ is a power of $p$.

In this case, we first choose parameters $m,\delta$ with the following
properties.

  1. (P1)

$m\in[n]$ with $m\geq 20b$ and $m\equiv n\pmod{2}.$

  2. (P2)

$1/3\geq\delta\geq\max\\{\varepsilon,1/2^{m}\\}.$

  3. (P3)

$\sqrt{m\log(1/\delta)}<b.$

  4. (P4)

$\sqrt{m\log(1/\delta)}=\Omega(\min\\{b,\sqrt{n\log(1/\varepsilon)}\\})=\Omega(b).$
(Recall that $b\leq\sqrt{n\log(1/\varepsilon)}$.)

We will show below how to find $m,\delta$ satisfying these properties.
Assuming this for now, we first prove the lower bound on
$\mathrm{pdeg}_{\varepsilon}(f).$

Define $F\in s\mathcal{B}_{m}$ as follows.

$F(x)=f(x0^{t}1^{t})$

for $t=(n-m)/2$. We observe that if $(G,H)$ is a standard decomposition of
$F$, then $\mathrm{per}(G)\geq b.$ To see this, note that by Corollary 2.5, we
have

$\mathrm{Spec}\,g|_{[\lfloor n/2\rfloor,\lfloor
n/2\rfloor+b-1]}\neq\mathrm{Spec}\,g|_{[\lfloor n/2\rfloor+i,\lfloor
n/2\rfloor+i+b-1]}$

for any $i\in[b-1]$. As $f$ and $g$ agree on inputs of weight from $[\lfloor
n/3\rfloor+1,\lfloor 2n/3\rfloor],$ the same non-equality holds for
$\mathrm{Spec}\,f$ also. Further, as $\mathrm{Spec}\,F(\lfloor
m/2\rfloor+j)=\mathrm{Spec}\,f(\lfloor n/2\rfloor+j)$ for $j\leq m/2$, we also
get

$\mathrm{Spec}\,F|_{[\lfloor m/2\rfloor,\lfloor
m/2\rfloor+b-1]}\neq\mathrm{Spec}\,F|_{[\lfloor m/2\rfloor+i,\lfloor
m/2\rfloor+i+b-1]}.$

for any $i\in[b-1]$ (we have used here the fact that $m\geq 20b$ which holds
by (P1)). Finally, as $F$ and $G$ agree on inputs of weight from $[\lfloor
m/3\rfloor+1,\lfloor 2m/3\rfloor]\supseteq[\lfloor m/2\rfloor,\lfloor
m/2\rfloor+2b],$ the above non-equality holds for $G$ as well. This implies
that $G$ cannot have period smaller than $b$.

By (P3), we have $\mathrm{per}(G)>\sqrt{m\log(1/\delta)}.$ Lemma 4.13 above
and (P4) now imply that
$\mathrm{pdeg}_{\delta}(F)=\Omega(\min\\{b,\sqrt{n\log(1/\varepsilon)}\\}).$
However, as $\delta\geq\varepsilon$ (by (P2)) and $F$ is a restriction of $f$,
the same lower bound holds for $\mathrm{pdeg}_{\varepsilon}(f)$ as well. This
proves the lemma modulo the existence of $m,\delta$ as above. We justify this
now.

  1. 1.

If $b\leq 10\sqrt{n},$ we take $m$ to be the largest integer such that
$m\equiv n\pmod{2}$ and $m\leq b^{2}/100.$ The parameter $\delta$ is set to
$1/3.$

  2. 2.

If $10\sqrt{n}<b\leq n/100,$ then we take $m$ to be the largest integer such
that $m\equiv n\pmod{2}$ and $m\leq n/2.$ The parameter
$\delta=\max\\{\varepsilon,2^{-b^{2}/2m}\\}.$

Note that as observed above, we have $b\leq n/100,$ and hence, the above
analysis subsumes all cases.

In each case, the verification of properties (P1)-(P4) is a routine
computation. (We assume here that $b$ is greater than a suitably large
constant, since otherwise the statement of the lemma is trivial.) This
concludes the proof.

We now prove a lower bound on $\mathrm{pdeg}_{\varepsilon}(h).$

######  Lemma 4.17.

Assume $B(h)\geq 1$. Then, $\varepsilon\in[2^{-n},1/3],$

$\mathrm{pdeg}_{\varepsilon}(h)=\Omega(\sqrt{B(h)\log(1/\varepsilon)}+\log(1/\varepsilon)).$

######  Proof 4.18.

Similar to the proof of Lemma 4.15, we may assume without loss of generality
that $\varepsilon\in[2^{-n/10000},e^{-10000p^{2}}].$

Let $B(h)=b.$ Recall (Observation 2.1) that $B(h)\leq\lceil n/3\rceil.$
Further, by definition of $B(h),$ we have either $\mathrm{Spec}\,h(b-1)=1$ or
$\mathrm{Spec}\,h(n-b+1)=1.$ We assume that $\mathrm{Spec}\,h(n-b+1)=1$ (the
other case is similar).

The lemma is equivalent to showing that
$\mathrm{pdeg}_{\varepsilon}(h)=\Omega(\max\\{\sqrt{B(h)\log(1/\varepsilon)},\log(1/\varepsilon)\\})$.
We do this based on a case analysis based on the relative magnitudes of
$\log(1/\varepsilon)$ and $b.$

Assume for now that $\varepsilon\leq 2^{-b/1000}$. In this case, we show a
lower bound of $\Omega(\log(1/\varepsilon)).$ To see this, set $m=\lceil
n/4\rceil$ and consider the restriction $H\in s\mathcal{B}_{m}$ obtained as
follows.

$H(x)=h(x1^{n-b+1-m}0^{b-1}).$

Note that as $\mathrm{Spec}\,h$ is the constant $0$ function on the interval
$[b,n-b],$ the function $H$ is computing the AND function on $m$ inputs. By
Lemma 4.6, we immediately have
$\mathrm{pdeg}_{\varepsilon}(h)\geq\mathrm{pdeg}_{\varepsilon}(H)=\Omega(\log(1/\varepsilon))$
proving the lemma in this case.

Now assume that $\varepsilon>2^{-b/1000}.$ In this case, we need to show that
$\mathrm{pdeg}_{\varepsilon}(h)$ is lower bounded by
$\Omega(\sqrt{b\log(1/\varepsilon)}).$ To prove this, consider the restriction
$H\in s\mathcal{B}_{2b-2}$ defined by $H(x)=h(x1^{n-2b+2}).$ Since
$\mathrm{Spec}\,h$ is the constant $0$ function on the interval $[b,n-b]$ and
$\mathrm{Spec}\,h(n-b+1)=1,$ it follows that the periodic part of $H$ has
period $\Omega(b)$. It then follows from Lemma 4.13 that
$\mathrm{pdeg}_{\varepsilon}(h)=\Omega(\sqrt{b\log(1/\varepsilon)}).$ This
concludes the proof of the lemma.

Now, we are ready to prove Theorem 4.4.

######  Proof 4.19 (Proof of Theorem 4.4).

By Lemma 4.15, we already have the desired lower bound on
$\mathrm{pdeg}_{\varepsilon}(f)$ in any of the following scenarios.

  * •

$\mathrm{per}(g)$ is not a power of $p$, or

  * •

$\mathrm{per}(g)$ is a power of $p$ and
$\mathrm{per}(g)\geq\sqrt{n\log(1/\varepsilon)},$ or

  * •

$B(h)=0.$

So from now, we assume that $\mathrm{per}(g)$ is a power of $p$ upper-bounded
by $\sqrt{n\log(1/\varepsilon)}$ and that $B(h)\geq 1.$ In this case, Lemma
4.15 shows that $\mathrm{pdeg}(f)=\Omega(\mathrm{per}(g)).$ On the other hand,
since $B(h)\leq n$ and $\varepsilon\geq 2^{-n},$ the lower bound we need to
show is
$\Omega(\mathrm{per}(g)+\sqrt{B(h)\log(1/\varepsilon)}+\log(1/\varepsilon)).$
By Lemma 4.17, it suffices to show a lower bound of
$\Omega(\mathrm{per}(g)+\mathrm{pdeg}_{\varepsilon}(h)).$

The analysis splits into two simple cases.

Assume first that $\mathrm{pdeg}_{\varepsilon}(h)\leq 4\cdot\mathrm{per}(g)$.
In this case, we are trivially done, because we already have
$\mathrm{pdeg}(f)=\Omega(\mathrm{per}(g))$, which is
$\Omega(\mathrm{pdeg}(g)+\mathrm{pdeg}_{\varepsilon}(h))$ as a result of our
assumption.

Now assume that $\mathrm{pdeg}_{\varepsilon}(h)>4\cdot\mathrm{per}(g).$ We
know that $f=g\oplus h$ and hence $h=f\oplus g.$ Hence, we have

$\displaystyle\mathrm{pdeg}_{\varepsilon}(h)\leq
2(\mathrm{pdeg}_{\varepsilon/2}(f)+\mathrm{pdeg}_{\varepsilon/2}(g))\leq
O(\mathrm{pdeg}_{\varepsilon}(f))+2\mathrm{per}(g),$

where the first inequality is a consequence of Fact 3 item 2 and the second
follows from error-reduction and Theorem 2.3. The above yields

$\mathrm{pdeg}_{\varepsilon}(f)=\Omega((\mathrm{pdeg}_{\varepsilon}(h)-2\cdot\mathrm{per}(g)))=\Omega(\mathrm{pdeg}_{\varepsilon}(h))=\Omega(\mathrm{per}(g)+\mathrm{pdeg}_{\varepsilon}(h)).$

This finishes the proof.

###  4.3 A Robust Version of Galvin’s Problem

We recall here a combinatorial theorem of Hegedűs [23] regarding set systems.
The theorem (and also our robust generalization given below) is easier to
prove in the language of indicator vectors, so we state it in this language.

Given any vectors $u,v\in\mathbb{F}^{n}$ for any field $\mathbb{F},$ we define
$\langle u,v\rangle:=\sum_{j\in[n]}u_{j}v_{j}.$

######  Theorem 4.20.

Assume $n=4p$, for a large enough prime $p$. Let
$u^{(1)},\ldots,u^{(m)}\in\\{0,1\\}^{n}_{n/2}\subseteq\mathbb{Z}^{n}$ be such
that for each $v\in\\{0,1\\}^{n}_{n/2}$, there is an $i\in[m]$ such that
$\langle u^{(i)},v\rangle=p.$ Then $m\geq p.$

The above theorem is nearly tight as can be seen by taking the indicator
vectors of the sets $S_{i}=\\{i,(i+1),\ldots,i+(n/2)-1\\}$ for $i\in[n/2]$.
Improvements on the above theorem (some of them asymptotically tight) were
proved recently by Alon et al. [5] and Hrubeš et al. [25].

Using the robust version of Hegedűs’s lemma, we can prove tight robust
versions of the above statement.

######  Remark 4.21.

We can prove a robust generalization (stated below) in a slightly more general
setting where the $i$th inner product $\langle u^{(i)},v\rangle$ is supposed
to take a value $b_{i}$ (which is not necessarily $p$). Similar to Theorem
4.20 above, it is easy to note that our robust version is tight up to constant
factors.

However, if we consider the robust version of the original statement of
Theorem 4.20 (where all the inner products take value $p$), then while our
lower bound continues to hold, it is not clear whether it is tight (except in
the settings where $\varepsilon$ is either a constant or $2^{-\Omega(n)}$). We
conjecture that it is.

We now prove a robust version of Theorem 4.20.

######  Theorem 4.22.

Assume $n$ is a growing even integer parameter and
$\varepsilon\in[2^{-n},1/2].$. Let
$u^{(1)},\ldots,u^{(m)}\in\\{0,1\\}^{n}_{n/2}\subseteq\mathbb{Z}^{n}$ and
$b_{1},\ldots,b_{m}\leq n$ be such that

Then $m=\Omega(\sqrt{n\log(1/\varepsilon)}).$

The theorem can easily seen to be tight up to constant factors. For
$t=C\cdot\sqrt{n\log(1/\varepsilon)}$, set $m=2t+1$ and take
$u^{(1)}=u^{(2)}=\cdots=u^{(m)}=1^{n/2}0^{n/2}$ and
$b_{1}=(n/4)-t,b_{2}=(n/4)-t+1,\ldots,b_{m}=(n/4)+t.$ By standard Chernoff
bounds for the Hypergeometric distribution, we immediately get that this set
of hyperplanes satisfy the above condition for a large enough choice of the
constant $C$.

We need the following standard bound on binomial coefficients. For
completeness, we include the proof in Appendix C.

######  Claim 54.

Let $n$ be an even integer and $m$ a non-negative integer with $m\leq n/2$.
Then, for any $k,\ell\in\\{0,\ldots,\lfloor m/2\rfloor\\}$ with $\ell\leq k$,
we have

$\frac{\binom{n/2}{\lfloor m/2\rfloor-k}\binom{n/2}{\lceil
m/2\rceil+k}}{\binom{n/2}{\lfloor m/2\rfloor-\ell}\binom{n/2}{\lceil
m/2\rceil+\ell}}\leq\exp(-\Omega((k^{2}-\ell^{2})/m)).$

Given the above, we can prove Theorem 4.22 as follows.

######  Proof 4.23 (Proof of Theorem 4.22).

Recall that for any fixed $u\in\\{0,1\\}^{n}_{n/2}$ and any $b\in\mathbb{Z}$,
the probability that a uniformly random $v\in\\{0,1\\}^{n}$ satisfies $\langle
u,v\rangle=b$ is at most $O(1/\sqrt{n})$. In particular, we must have
$m=\Omega(\sqrt{n})$ for any $\varepsilon\leq 1/2.$ This proves the result for
$\varepsilon=\Omega(1).$

Hence, we may assume that $\varepsilon$ is smaller than any fixed constant. We
can also assume that $\varepsilon\geq 2^{-\delta n}$ for a small enough
constant $\delta$. Assume that $m\leq\sqrt{n\log(1/\varepsilon)}$.

We call $i\in[m]$ _balanced_ if $|b_{i}-\frac{n}{4}|\leq t$ where
$t:=C\sqrt{n\log(1/\varepsilon)}$ for a large enough constant $C$. If $i$ is
not balanced, then we have for a uniformly random
$\bm{v}\sim\\{0,1\\}^{n}_{n/2}$,

The second inequality above follows from Claim 54, and the third follows from
the Stirling approximation and using the fact that $C$ is a large enough
constant. In particular, if $B$ is the set of balanced $i$, we have

where we used the fact that $m\leq\sqrt{n\log(1/\varepsilon)}$. We can thus
consider only $\\{u^{(i)}\ |\ i\in B\\}$, which satisfy the hypothesis with
error probability $\varepsilon_{1}:=2\varepsilon.$

Now consider the polynomial

$P(x_{1},\ldots,x_{n})=\prod_{i\in B}(\langle u^{(i)},x\rangle-b_{i}).$

We know that $P$ vanishes at a random point of $\\{0,1\\}^{n}_{n/2}$ with
probability at least $1-\varepsilon_{1}.$ Now, fix any prime $p\in[10t,20t]$
(such a prime exists by standard number-theoretic results). We claim that for
any $i\in B$ and a uniformly random point $\bm{v}\in\\{0,1\\}^{n}_{n/2-p}$, we
have

(15)

for a large enough constant $C$. Informally speaking, the reason for this
inequality is as follows: the expected value of $\langle
u^{(i)},\bm{v}\rangle$ is $(n/4)-p/2$ and any number $b\equiv b_{i}\pmod{p}$
is far from this expectation. To prove this, let $s=n/2-p$. Note that
$s=\Omega(n)$ as long as $t$ is small enough in relation to $n$, which happens
if $\delta$ is assumed to be a small enough constant. Using the fact that $i$
is balanced, we note that

$\displaystyle\Delta_{i}:=b_{i}-\left\lceil\frac{s}{2}\right\rceil$
$\displaystyle\leq\frac{n}{4}+t-\left(\frac{n}{4}-\left\lceil\frac{p}{2}\right\rceil\right)\leq\frac{2p}{3}$
$\displaystyle\Delta_{i}$
$\displaystyle\geq\frac{n}{4}-t-\left(\frac{n}{4}-\left\lceil\frac{p}{2}\right\rceil\right)\geq\frac{p}{3}.$

We thus have

$\displaystyle=\sum_{j\geq 0}$ $\displaystyle=\sum_{j\geq 0}$
$\displaystyle=\sum_{j\geq
0}\frac{\binom{n/2}{\left\lceil\frac{s}{2}\right\rceil+\Delta_{i}+jp}\binom{n/2}{\left\lfloor\frac{s}{2}\right\rfloor-\Delta_{i}-jp}}{\binom{n}{s}}$
(by Claim 54)
$\displaystyle=\frac{\binom{n/2}{\left\lceil\frac{s}{2}\right\rceil}\binom{n/2}{\left\lfloor\frac{s}{2}\right\rfloor}}{\binom{n}{s}}\cdot\sum_{j\geq
0}\exp(-\Omega((\Delta_{i}+jp)^{2})/s))$ (Stirling approximation and
$s=\Omega(n)$ $\displaystyle\leq
O\left(\frac{1}{\sqrt{n}}\right)\cdot\sum_{j\geq
0}\exp(-\Omega(\Delta_{i}^{2}+jp^{2})/s)$ ($p^{2}/s\geq C^{2}$ )
$\displaystyle\leq
O\left(\frac{1}{\sqrt{n}}\right)\cdot\exp(-\Omega(\Delta_{i}^{2}/s))\cdot\sum_{j\geq
0}\exp(-\Omega(C^{2}j))$ (for large enough $C$ ) $\displaystyle\leq
O\left(\frac{1}{\sqrt{n}}\right)\cdot\exp(-\Omega(\Delta_{i}^{2}/s))\cdot 2$
$\displaystyle=O\left(\frac{1}{\sqrt{n}}\right)\cdot\exp(-\Omega(p^{2}/s)).$

In a similar way, we also get Overall, we thus obtain for any $i\in B$, as
long as $C$ is a large enough constant. Union bounding over the at most
$m\leq\sqrt{n\log(1/\varepsilon)}$ elements of $B$, we see that

From now on, we consider the polynomial $P$ as an element of
$\mathbb{F}_{p}[x_{1},\ldots,x_{n}].$ At this point, we would like to apply
Lemma 3.1 to the polynomial $P$ and finish the proof. Unfortunately, the error
parameter $\varepsilon_{1}$ above is not small enough to apply Lemma 3.1
directly (we need $\varepsilon_{1}\leq\exp(-200p^{2}/n)$). However, we can do
a simple error reduction as in Lemma 3.9 to ensure that Lemma 3.1 is
applicable. More precisely, choose $r$ to be a large enough absolute constant
so that $\varepsilon_{1}^{r}\leq\frac{1}{2}\exp(-200p^{2}/n).$ Now, by Lemma
3.9 there is a probabilistic polynomial $\bm{P^{(r)}}$ of degree at most
$r\cdot\deg(P)$ such that

$\displaystyle\leq\varepsilon_{1}^{2r}\leq\frac{1}{2}\exp(-200p^{2}/n),\text{
and }$ $\displaystyle\geq(1-\varepsilon)^{r}\geq
1-r\varepsilon\geq\frac{9}{10}$

where for the last inequality we used the fact that $\varepsilon$ is smaller
than some absolute constant.

By a simple union bound, there is a fixed polynomial
$P^{\prime}\in\mathbb{F}_{p}[x_{1},\ldots,x_{n}]$ of degree
$r\cdot\deg(P)=O(m)$ such that

$\displaystyle\leq\exp(-200p^{2}/n),\text{ and }$
$\displaystyle\geq\frac{1}{2}$

Hence, applying Lemma 3.1 to the polynomial $P^{\prime}$, we get
$\deg(P^{\prime})=\Omega(p)=\Omega(\sqrt{n\log(1/\varepsilon)}).$ This yields
the desired lower bound on $m.$

###### Acknowledgements.

The author is grateful to Mrinal Kumar, Nutan Limaye, Utkarsh Tripathi and S.
Venkitesh for useful discussions, feedback, and encouragement. The author
thanks Nutan Limaye for suggesting the robust version of Galvin’s problem as
an application. The author is also grateful to the anonymous referees of STOC
2020 and TheoretiCS for their corrections and suggestions. In particular, a
referee for the TheoretiCS submission pointed out an extension to the main
lemma (Lemma 3.15).

## References

  * [1] Amir Abboud, Richard Ryan Williams and Huacheng Yu  “More Applications of the Polynomial Method to Algorithm Design”  In _Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015_ , 2015, pp. 218–230  DOI: 10.1137/1.9781611973730.17
  * [2] Rohit Agrawal  “Coin Theorems and the Fourier Expansion”  In _Chic. J. Theor. Comput. Sci._ 2020, 2020  URL: http://cjtcs.cs.uchicago.edu/articles/2020/4/contents.html
  * [3] Miklós Ajtai and Michael Ben-Or  “A Theorem on Probabilistic Constant Depth Computations”  In _Proceedings of the 16th Annual ACM Symposium on Theory of Computing, STOC 1984, April 30 - May 2, 1984, Washington, DC, USA_ ACM, 1984, pp. 471–474  DOI: 10.1145/800057.808715
  * [4] Josh Alman and Ryan Williams  “Probabilistic Polynomials and Hamming Nearest Neighbors”  In _IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015_ IEEE Computer Society, 2015, pp. 136–150  DOI: 10.1109/FOCS.2015.18
  * [5] Noga Alon, Mrinal Kumar and Ben Lee Volk  “Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits”  In _33rd Computational Complexity Conference, CCC 2018, June 22-24, 2018, San Diego, CA, USA_ , 2018, pp. 11:1–11:16  DOI: 10.4230/LIPIcs.CCC.2018.11
  * [6] James Aspnes, Richard Beigel, Merrick L. Furst and Steven Rudich  “The Expressive Power of Voting Polynomials”  In _Combinatorica_ 14.2, 1994, pp. 135–148
  * [7] Peter Beelen and Mrinmoy Datta  “Generalized Hamming weights of affine Cartesian codes”  In _Finite Fields Appl._ 51, 2018, pp. 130–145  DOI: 10.1016/j.ffa.2018.01.006
  * [8] Richard Beigel  “The Polynomial Method in Circuit Complexity”  In _Proceedings of the Eigth Annual Structure in Complexity Theory Conference, CCC 1993, San Diego, CA, USA, May 18-21, 1993_ IEEE Computer Society, 1993, pp. 82–95  DOI: 10.1109/SCT.1993.336538
  * [9] Jean Berstel and Juhani Karhumäki  “Combinatorics on words: a tutorial”  In _Bulletin of the EATCS_ 79, 2003, pp. 178
  * [10] Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli and Srikanth Srinivasan  “On the Probabilistic Degree of OR over the Reals”  In _38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)_ 122, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018, pp. 5:1–5:12  DOI: 10.4230/LIPIcs.FSTTCS.2018.5
  * [11] Mark Braverman  “Polylogarithmic independence fools _AC_ ${}^{\mbox{0}}$ circuits”  In _J. ACM_ 57.5, 2010  DOI: 10.1145/1754399.1754401
  * [12] Joshua Brody and Elad Verbin  “The Coin Problem and Pseudorandomness for Branching Programs”  In _51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA_ IEEE Computer Society, 2010, pp. 30–39  DOI: 10.1109/FOCS.2010.10
  * [13] 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 Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA_ , 2019, pp. 22:1–22:15  DOI: 10.4230/LIPIcs.ITCS.2019.22
  * [14] G.F. Clements and B. Lindström  “A generalization of a combinatorial theorem of Macaulay”  In _Journal of Combinatorial Theory_ 7.3, 1969, pp. 230–238  DOI: https://doi.org/10.1016/S0021-9800(69)80016-5
  * [15] Gil Cohen, Anat Ganor and Ran Raz  “Two Sides of the Coin Problem”  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain_ 28, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014, pp. 618–629  DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.618
  * [16] Ernie Croot, Vsevolod F Lev and Péter Pál Pach  “Progression-free sets in are exponentially small”  In _Annals of Mathematics_ JSTOR, 2017, pp. 331–337
  * [17] Devdatt P Dubhashi and Alessandro Panconesi  “Concentration of measure for the analysis of randomized algorithms”  Cambridge University Press, 2009
  * [18] Jordan S Ellenberg and Dion Gijswijt  “On large subsets of with no three-term arithmetic progression”  In _Annals of Mathematics_ JSTOR, 2017, pp. 339–343
  * [19] Hikoe Enomoto, Peter Frankl, Noboru Ito and Kazumasa Nomura  “Codes with given distances”  In _Graphs and Combinatorics_ 3.1 Springer, 1987, pp. 25–38
  * [20] Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova and Avishay Tal  “$\mathrm{AC^{0}[p]}$ Lower Bounds Against MCSP via the Coin Problem”  In _46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece_ 132, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, pp. 66:1–66:15  DOI: 10.4230/LIPIcs.ICALP.2019.66
  * [21] Larry Guth  “Polynomial methods in combinatorics” 64, University Lecture Series  American Mathematical Society, Providence, RI, 2016, pp. ix+273  DOI: 10.1090/ulect/064
  * [22] Prahladh Harsha and Srikanth Srinivasan  “On polynomial approximations to AC”  In _Random Struct. Algorithms_ 54.2, 2019, pp. 289–303  DOI: 10.1002/rsa.20786
  * [23] Gábor Hegedűs  “Balancing sets of vectors”  In _Studia Scientiarum Mathematicarum Hungarica_ 47.3 Akadémiai Kiadó, 2009, pp. 333–349
  * [24] Petra Heijnen and Ruud Pellikaan  “Generalized Hamming weights of $q$-ary Reed-Muller codes”  In _IEEE Trans. Inform. Theory_ 44.1, 1998, pp. 181–196  DOI: 10.1109/18.651015
  * [25] Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao and Amir Yehudayoff  “Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits”  In _46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece_ 132, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, pp. 72:1–72:14  DOI: 10.4230/LIPIcs.ICALP.2019.72
  * [26] Peter. Keevash and Benny. Sudakov  “Set Systems with Restricted Cross-Intersections and the Minimum Rank ofInclusion Matrices”  In _SIAM Journal on Discrete Mathematics_ 18.4, 2005, pp. 713–727  DOI: 10.1137/S0895480103434634
  * [27] Adam R. Klivans, Ryan O’Donnell and Rocco A. Servedio  “Learning intersections and thresholds of halfspaces”  In _J. Comput. Syst. Sci._ 68.4, 2004, pp. 808–840  DOI: 10.1016/j.jcss.2003.11.002
  * [28] Adam R. Klivans and Rocco A. Servedio  “Learning DNF in time $2^{\tilde{O}(n^{1/3})}$”  In _J. Comput. Syst. Sci._ 68.2, 2004, pp. 303–318  DOI: 10.1016/j.jcss.2003.07.007
  * [29] Swastik Kopparty and Srikanth Srinivasan  “Certifying Polynomials for $\mathrm{AC}^{0}[\oplus]$ Circuits, with Applications to Lower Bounds and Circuit Compression”  In _Theory of Computing_ 14.1, 2018, pp. 1–24  DOI: 10.4086/toc.2018.v014a012
  * [30] Alexander S. Kulikov and Vladimir V. Podolskii  “Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates”  In _34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany_ , 2017, pp. 49:1–49:14  DOI: 10.4230/LIPIcs.STACS.2017.49
  * [31] Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi and S. Venkitesh  “A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^{0}[\oplus]$ via the Coin Problem”  In _SIAM J. Comput._ 50.4, 2021, pp. 1461–1499  DOI: 10.1137/19M1276467
  * [32] Nathan Linial, Yishay Mansour and Noam Nisan  “Constant Depth Circuits, Fourier Transform, and Learnability”  In _J. ACM_ 40.3, 1993, pp. 607–620  DOI: 10.1145/174130.174138
  * [33] Chi-Jen Lu  “An exact characterization of symmetric functions in $\mathrm{qAC^{0}[2]}$”  In _Theoretical Computer Science_ 261.2 Elsevier, 2001, pp. 297–303
  * [34] Raghu Meka, Oanh Nguyen and Van Vu  “Anti-concentration for Polynomials of Independent Random Variables”  In _Theory of Computing_ 12.1, 2016, pp. 1–17  DOI: 10.4086/toc.2016.v012a011
  * [35] Zipei Nie and Anthony Y. Wang  “Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry”  In _Journal of Combinatorial Theory, Series A_ 134, 2015, pp. 196–220  DOI: https://doi.org/10.1016/j.jcta.2015.03.011
  * [36] Aditya Potukuchi  “On the $\mathrm{AC^{0}[\oplus]}$ Complexity of Andreev’s Problem”  In _39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2019, December 11-13, 2019, Bombay, India_ 150, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, pp. 25:1–25:14  DOI: 10.4230/LIPIcs.FSTTCS.2019.25
  * [37] Ran Raz, Amir Shpilka and Amir Yehudayoff  “A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits”  In _SIAM J. Comput._ 38.4, 2008, pp. 1624–1647  DOI: 10.1137/070707932
  * [38] Alexander A. Razborov  “Lower bounds on the size of bounded depth circuits over a complete basis with logical addition” (English translation in Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333–338, 1987)  In _Mathematicheskie Zametki_ 41.4, 1987, pp. 598–607  DOI: 10.1007/BF01137685
  * [39] Ronen Shaltiel and Emanuele Viola  “Hardness Amplification Proofs Require Majority”  In _SIAM J. Comput._ 39.7, 2010, pp. 3122–3154  DOI: 10.1137/080735096
  * [40] Amir Shpilka and Amir Yehudayoff  “Arithmetic Circuits: A survey of recent results and open questions”  In _Foundations and Trends in Theoretical Computer Science_ 5.3-4, 2010, pp. 207–388  DOI: 10.1561/0400000039
  * [41] 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_ , 1987, pp. 77–82  ACM
  * [42] Roman Smolensky  “On representations by low-degree polynomials”  In _Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, FOCS 1993_ , 1993, pp. 130–138  IEEE
  * [43] Srikanth Srinivasan, Utkarsh Tripathi and S. Venkitesh  “On the Probabilistic Degrees of Symmetric Boolean Functions”  In _SIAM J. Discret. Math._ 35.3, 2021, pp. 2070–2092  DOI: 10.1137/19M1294162
  * [44] Srikanth Srinivasan and S. Venkitesh  “On Vanishing Properties of Polynomials on Symmetric Sets of the Boolean Cube, in Positive Characteristic” Available at https://arxiv.org/abs/2111.05445 arXiv, 2021  DOI: 10.48550/ARXIV.2111.05445
  * [45] M. Szegedy  “Algebraic Methods in Lower Bounds for Computational Models with Limited Communication.”  In _PhD thesis_ The University of Chicago, 1989
  * [46] Leslie G. Valiant  “Short Monotone Formulae for the Majority Function”  In _J. Algorithms_ 5.3, 1984, pp. 363–366  DOI: 10.1016/0196-6774(84)90016-6
  * [47] Emanuele Viola  “On Approximate Majority and Probabilistic Time”  In _Computational Complexity_ 18.3, 2009, pp. 337–375
  * [48] V.. Wei  “Generalized Hamming weights for linear codes”  In _IEEE Transactions on Information Theory_ 37.5, 1991, pp. 1412–1418  DOI: 10.1109/18.133259
  * [49] R. Williams  “Faster All-Pairs Shortest Paths via Circuit Complexity”  In _SIAM J. Comput._ 47.5, 2018, pp. 1965–1985  DOI: 10.1137/15M1024524
  * [50] Richard Ryan Williams  “The Polynomial Method in Circuit Complexity Applied to Algorithm Design (Invited Talk)”  In _34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014, December 15-17, 2014, New Delhi, India_ 29, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014, pp. 47–60  DOI: 10.4230/LIPIcs.FSTTCS.2014.47
  * [51] Ryan Williams  “New algorithms and lower bounds for circuits with linear threshold gates”  In _Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014_ ACM, 2014, pp. 194–202  DOI: 10.1145/2591796.2591858
  * [52] Ryan Williams  “Nonuniform ACC Circuit Lower Bounds”  In _J. ACM_ 61.1, 2014, pp. 2:1–2:32  DOI: 10.1145/2559903

##  Appendix A Lemma 1.1 is implied by Lemma 3.1 (up to constant factors)

The following claim shows that if there is a $P$ satisfying the hypotheses of
Lemma 1.1, then there is also a polynomial $Q$ of degree at most $\deg(P)$
satisfying a stronger property, namely, that of not vanishing at too many
points of $\\{0,1\\}^{n}_{k+q}.$

######  Claim 68.

Let $\mathbb{F}$ be a field of characteristic $p>0$. Fix any positive integers
$n,k,q$ such that $k\in[q,n-q],$ and $q$ a power of $p$. If there is a
polynomial $P\in\mathbb{F}[x_{1},\ldots,x_{n}]$ is any polynomial that
vanishes at _all_ $a\in\\{0,1\\}^{n}_{k}$ but does not vanish at _some_
$b\in\\{0,1\\}^{n}_{k+q}$, then there is a
$Q\in\mathbb{F}[x_{1},\ldots,x_{n}]$ of degree at most $\deg(P)$ such that $Q$
vanishes at all $a\in\\{0,1\\}^{n}_{k}$ but is non-zero at at least a
$(1-1/p)$ fraction of the points in $\\{0,1\\}^{n}_{k+q}.$

######  Proof A.1.

Let $d=\deg(P)$. Assume without loss of generality that $P(b)=1.$ Note that
$P$ is the solution to the system of linear equations defined by the following
constraints on polynomials of degree at most $d$.

$\displaystyle|a|=k$ $\displaystyle\Rightarrow P(a)=0$ $\displaystyle P(b)$
$\displaystyle=1.$

As the above linear system is over $\mathbb{F}_{p}\subseteq\mathbb{F},$ we
note that we may assume that $P\in\mathbb{F}_{p}[x_{1},\ldots,x_{n}].$ From
now on, we assume that $\mathbb{F}=\mathbb{F}_{p}.$

Consider the degree-$d$ closure $C=\mathrm{cl}_{d}(\\{0,1\\}^{n}_{k}).$ By the
existence of $P$, we see that $b\not\in C.$ However, by symmetry, this implies
that no point $b^{\prime}\in\\{0,1\\}^{n}_{k+q}$ lies in $C$.

Let $V_{d,k}$ denote the vector space of all multilinear polynomials of degree
at most $d$ that vanish at all points in $\\{0,1\\}^{n}_{k}.$ Let $\bm{Q}$ be
a uniformly random element of $V_{d,k}$. For any $c\in\\{0,1\\}^{n}\setminus
C$, standard linear algebra implies that $\bm{Q}(c)$ is a uniformly random
element of $\mathbb{F}=\mathbb{F}_{p}.$ In particular, for any
$b^{\prime}\in\\{0,1\\}^{n}_{k+q}$, we see that

In particular, there is a $Q\in V_{d,k}$ that is non-zero at at least a
$(1-1/p)$ fraction of points in $\\{0,1\\}^{n}_{k+q}.$ This yields the
statement of the claim.

##  Appendix B Proof of Lemma 2.4 (the string lemma)

We begin by recalling the statement of the lemma.

See 2.4

######  Proof B.1.

Assume that $|u|=\ell,|v|=m$ and $|w|=\ell+m=n.$ We will show in fact that
both $u$ and $v$ are powers of the same non-empty string $z$. This will
clearly imply the lemma.

The proof is by induction on the length of $w$. The base case of the induction
corresponds to $n=2$, which is obvious.

We now proceed with the inductive case. Assume w.l.o.g. that $\ell\leq m.$ As
$uv=vu$, we see that the first $\ell$ symbols in $v$ match those of $u$, and
hence we have $v=uv^{\prime}$ for some $v^{\prime}\in\\{0,1\\}^{m-\ell}.$ If
$\ell=m,$ this implies that $u=v$ and we are immediately done. Otherwise, we
see that $w=uv^{\prime}u=v^{\prime}uu$ for a non-empty string $v^{\prime}$.
Hence, we have $uv^{\prime}=v^{\prime}u$. By the induction hypothesis, we know
that both $u$ and $v^{\prime}$ are powers of some non-empty $z$. Hence, so is
$v$. This concludes the proof.

##  Appendix C Proof of Claim 54

We first restate the claim. See 54

######  Proof C.1.

It suffices to show that for each $k\in\\{0,\ldots,\lfloor m/2\rfloor-1\\}$,

$\frac{\binom{n/2}{\lfloor m/2\rfloor-k-1}\binom{n/2}{\lceil
m/2\rceil+k+1}}{\binom{n/2}{\lfloor m/2\rfloor-k}\binom{n/2}{\lceil
m/2\rceil+k}}\leq\exp(-\Omega(k/m)).$ (16)

The claim then follows by a simple induction on $k-\ell$.

To prove (16), we proceed as follows. By an expansion of binomial coefficients
in terms of factorials, we see that

$\displaystyle\frac{\binom{n/2}{\lfloor m/2\rfloor-k-1}\binom{n/2}{\lceil
m/2\rceil+k+1}}{\binom{n/2}{\lfloor m/2\rfloor-k}\binom{n/2}{\lceil
m/2\rceil+k}}$ $\displaystyle=\frac{(\lfloor m/2\rfloor-k)(n/2-(\lceil
m/2\rceil+k))}{(n/2-(\lfloor m/2\rfloor-k-1))(\lceil m/2\rceil+k+1)}$
$\displaystyle\leq\frac{\lfloor m/2\rfloor-k}{\lceil m/2\rceil+k+1}$
$\displaystyle\leq\frac{(m/2)-k}{(m/2)}\leq 1-2k/m\leq\exp(-2k/m).$