Specifically, the $\lambda_{i}$ are supported almost entirely on pairwise
disjoint sets of inputs of Hamming weight $k$ and are pairwise
indistinguishable by low-degree polynomials.

######  Theorem 4.4.

Let $0<\beta<1$ be given. Let $n,n^{\prime},m,k,r$ be positive integers with
$n\geqslant n^{\prime}\geqslant m>k$. Let
$\gamma\colon\binom{[n^{\prime}]}{k}\to[r]$ be a given
$(\frac{\beta}{16rm^{2}},\frac{\beta}{16r^{2}m^{2}},m)$-balanced coloring.
Then there are $($explicitly given$)$ probability distributions
$\lambda_{1},\lambda_{2},\ldots,\lambda_{r}$ on $\\{0,1\\}^{n}$ such that

$\displaystyle\operatorname{supp}\lambda_{i}\subseteq\\{x\in\\{0,1\\}^{n}:|x|=k\text{
or }|x|\geqslant m\\},$ $\displaystyle i\in[r],$ (4.21)
$\displaystyle\\{0,1\\}^{n}|_{k}\cap\operatorname{supp}\lambda_{i}=\\{\mathbf{1}_{S}:S\in\gamma^{-1}(i)\\},$
$\displaystyle i\in[r],$ (4.22)
$\displaystyle\lambda_{i}(\\{0,1\\}^{n}|_{k})\geqslant 1-\beta,$
$\displaystyle i\in[r],$ (4.23)
$\displaystyle\lambda_{i}(\\{0,1\\}^{n}|_{\ell})\leqslant\frac{\exp(-c(\ell-k)/\sqrt{n^{\prime}m})}{c(\ell-k+1)^{2}},$
$\displaystyle i\in[r],\;\ell\geqslant k,$ (4.24)
$\displaystyle\operatorname{orth}(\lambda_{i}-\lambda_{j})\geqslant
c\sqrt{\frac{n^{\prime}}{m},}$ $\displaystyle i,j\in[r],$ (4.25)

where $c\in(0,1)$ is an absolute constant, independent of
$n,n^{\prime},m,k,r,\beta.$

###### Proof.

By hypothesis, $\gamma$ is $(\epsilon,\delta,m)$-balanced with

$\displaystyle\epsilon=\frac{\beta}{16rm^{2}},$
$\displaystyle\delta=\frac{\beta}{16r^{2}m^{2}}.$

Applying Theorem 4.1 with these parameters gives functions
$\phi_{1},\phi_{2},\ldots,\phi_{r}\colon\\{0,1\\}^{n^{\prime}}\to\mathbb{R}$
that obey

$\displaystyle\operatorname{supp}\phi_{i}\subseteq\\{x\in\\{0,1\\}^{n^{\prime}}:|x|=k\text{
or }|x|\geqslant m\\},$ (4.26)
$\displaystyle\\{0,1\\}^{n^{\prime}}|_{k}\cap\operatorname{supp}\phi_{i}=\\{\mathbf{1}_{S}:S\in\gamma^{-1}(i)\\},$
(4.27) $\displaystyle\phi_{i}\geqslant 0\quad\text{on
}\\{0,1\\}^{n^{\prime}}|_{k},$ (4.28)
$\displaystyle\sum_{x:|x|=k}\phi_{i}(x)=1,$ (4.29)
$\displaystyle\sum_{x:|x|\neq k}|\phi_{i}(x)|\leqslant\frac{\beta}{r},$ (4.30)
$\displaystyle\sum_{x:|x|=\ell}|\phi_{i}(x)|\leqslant\frac{\beta}{rc^{\prime}\ell^{2}}\cdot\exp\left(-\frac{c^{\prime}(\ell-k)}{\sqrt{n^{\prime}m}}\right),\qquad\ell>k,$
(4.31) $\displaystyle\operatorname{orth}(\phi_{i}-\phi_{j})\geqslant
c^{\prime\prime}\sqrt{\frac{n^{\prime}}{m}}\qquad\text{for all }i,j\in[r],$
(4.32)

where $c^{\prime},c^{\prime\prime}\in(0,1)$ are the absolute constants defined
in Theorem 4.1. For $i\in[r],$ define
$\tilde{\phi}_{i}\colon\\{0,1\\}^{n^{\prime}}\to\mathbb{R}$ by

$\tilde{\phi}_{i}(x)=\phi_{i}(x)-\mathbf{I}[|x|>k]\min_{j\in[r]}\phi_{j}(x).$
(4.33)

Equation (4.26) shows that $\tilde{\phi}_{i}$ is a linear combination of
functions whose support is contained in
$\\{x\in\\{0,1\\}^{n^{\prime}}:|x|=k\text{ or }|x|\geqslant m\\}.$ As a
result,

$\displaystyle\operatorname{supp}\tilde{\phi}_{i}\subseteq\\{x\in\\{0,1\\}^{n^{\prime}}:|x|=k\text{
or }|x|\geqslant m\\}.$ (4.34)

Since $\tilde{\phi}_{i}=\phi_{i}$ on $\\{0,1\\}^{n^{\prime}}|_{k},$ we obtain
from (4.27) and (4.29) that

$\displaystyle\\{0,1\\}^{n^{\prime}}|_{k}\cap\operatorname{supp}\tilde{\phi}_{i}=\\{\mathbf{1}_{S}:S\in\gamma^{-1}(i)\\},$
(4.35) $\displaystyle\sum_{x:|x|=k}\tilde{\phi}_{i}(x)=1.$ (4.36)

In particular,

$\|\tilde{\phi}_{i}\|_{1}\geqslant 1.$ (4.37)

We further claim that

$\displaystyle\tilde{\phi}_{i}(x)$ $\displaystyle\geqslant 0,$ $\displaystyle
x\in\\{0,1\\}^{n^{\prime}}.$ (4.38)

Indeed, the nonnegativity of $\tilde{\phi}_{i}(x)$ for
$x\in\\{0,1\\}^{n^{\prime}}|_{k}$ follows from
$\tilde{\phi}_{i}(x)=\phi_{i}(x)$ and (4.28), whereas the nonnegativity of
$\tilde{\phi}_{i}(x)$ for $x\in\\{0,1\\}^{n^{\prime}}|_{>k}$ follows from
(4.33) via
$\tilde{\phi}_{i}(x)=\phi_{i}(x)-\min_{j\in[r]}\phi_{j}(x)\geqslant\phi_{i}(x)-\phi_{i}(x)\geqslant
0.$

On $\\{0,1\\}^{n^{\prime}}|_{>k},$ we have

$\displaystyle\tilde{\phi}_{i}$
$\displaystyle=\phi_{i}-\min_{j\in[r]}\phi_{j}=\max_{j\in[r]}\\{\phi_{i}-\phi_{j}\\}\leqslant\max_{j\in[r]}|\phi_{i}-\phi_{j}|\leqslant\sum_{j=1}^{r}|\phi_{j}|.$

This conclusion is also valid on $\\{0,1\\}^{n^{\prime}}|_{<k}$ due to (4.34).
Thus,

$\displaystyle\tilde{\phi}_{i}(x)$
$\displaystyle\leqslant\sum_{j=1}^{r}|\phi_{j}(x)|,$ $\displaystyle|x|\neq k.$
(4.39)

Summing over $x$ gives

$\displaystyle\sum_{x:|x|\neq k}\tilde{\phi}_{i}(x)$
$\displaystyle\leqslant\sum_{x:|x|\neq k}\sum_{j=1}^{r}|\phi_{j}(x)|$
$\displaystyle=\sum_{j=1}^{r}\sum_{x:|x|\neq k}|\phi_{j}(x)|$
$\displaystyle\leqslant\beta,$ (4.40)

where the third step applies (4.30).

For all $i\in[r]$ and $\ell\in\\{m,m+1,\ldots,n^{\prime}\\}$, we have the
graded bound

$\displaystyle\sum_{x:|x|=\ell}\tilde{\phi}_{i}(x)$
$\displaystyle\leqslant\sum_{j=1}^{r}\sum_{x:|x|=\ell}|\phi_{j}(x)|$
$\displaystyle\leqslant\frac{1}{c^{\prime}\ell^{2}}\cdot\exp\left(-\frac{c^{\prime}(\ell-k)}{\sqrt{n^{\prime}m}}\right),$
(4.41)

where the first step uses (4.39), and the second step uses (4.31). Finally,
for $i,j\in[r],$ we have

$\displaystyle\operatorname{orth}(\tilde{\phi}_{i}-\tilde{\phi}_{j})$
$\displaystyle=\operatorname{orth}(\phi_{i}-\phi_{j})$ $\displaystyle\geqslant
c^{\prime\prime}\sqrt{\frac{n^{\prime}}{m}},$ (4.42)

where the first step uses the definition (4.33), and the second step uses
(4.32).

Define $c=\min\\{c^{\prime},c^{\prime\prime}\\}.$ Equations (4.36) and (4.38)
show that each $\tilde{\phi}_{i}$ is a nonnegative function and is not
identically zero, making it possible to define a probability distribution
$\lambda_{i}$ on $\\{0,1\\}^{n}$ by

$\displaystyle\lambda_{i}(x)$
$\displaystyle=\frac{1}{\|\tilde{\phi}_{i}\|_{1}}\tilde{\phi}_{i}(x_{1}x_{2}\ldots
x_{n^{\prime}})\prod_{j=n^{\prime}+1}^{n}(1-x_{j}).$

In other words, $\lambda_{i}$ is nonzero only on inputs $x$ with
$x_{n^{\prime}+1}=x_{n^{\prime}+2}=\cdots=x_{n}=0,$ and on such inputs
$\lambda_{i}(x)$ is the properly normalized version of the nonnegative
function $\tilde{\phi}_{i}(x_{1}x_{2}\ldots x_{n^{\prime}})$. Then properties
(4.21) and (4.22) are immediate from (4.34) and (4.35), respectively. Property
(4.23) follows from

$\displaystyle\lambda_{i}(\\{0,1\\}^{n}|_{k})$
$\displaystyle=\frac{1}{\|\tilde{\phi}_{i}\|_{1}}\sum_{x\in\\{0,1\\}^{n}|_{k}}\tilde{\phi}_{i}(x_{1}x_{2}\ldots
x_{n^{\prime}})\prod_{j=n^{\prime}+1}^{n}(1-x_{j})$
$\displaystyle=\frac{1}{\|\tilde{\phi}_{i}\|_{1}}\sum_{x\in\\{0,1\\}^{n^{\prime}}|_{k}}\tilde{\phi}_{i}(x_{1}x_{2}\ldots
x_{n^{\prime}})$ $\displaystyle=\frac{1}{\|\tilde{\phi}_{i}\|_{1}}$
$\displaystyle\geqslant\frac{1}{1+\beta}$ $\displaystyle\geqslant 1-\beta,$

where the third step uses (4.36), and the fourth step uses (4.36) and (4.40).
Property (4.24) is trivial for $\ell=k$ and follows for $\ell>k$ from

$\displaystyle\lambda_{i}(\\{0,1\\}^{n}|_{\ell})$
$\displaystyle=\frac{1}{\|\tilde{\phi}_{i}\|_{1}}\sum_{x\in\\{0,1\\}^{n}|_{\ell}}\tilde{\phi}_{i}(x_{1}x_{2}\ldots
x_{n^{\prime}})\prod_{j=n^{\prime}+1}^{n}(1-x_{j})$
$\displaystyle=\frac{1}{\|\tilde{\phi}_{i}\|_{1}}\sum_{x\in\\{0,1\\}^{n^{\prime}}|_{\ell}}\tilde{\phi}_{i}(x_{1}x_{2}\ldots
x_{n^{\prime}})$
$\displaystyle\leqslant\frac{1}{\|\tilde{\phi}_{i}\|_{1}}\cdot\frac{\exp(-c^{\prime}(\ell-k)/\sqrt{n^{\prime}m})}{c^{\prime}\ell^{2}}$
$\displaystyle\leqslant\frac{\exp(-c(\ell-k)/\sqrt{n^{\prime}m})}{c\ell^{2}},$

where the third step uses (4.41), and the fourth step uses (4.37) and
$c=\min\\{c^{\prime},c^{\prime\prime}\\}.$

It remains to verify (4.25). For this, fix $i,j\in[r]$ arbitrarily. Then
$\|\tilde{\phi}_{i}\|_{1}-\|\tilde{\phi}_{j}\|_{1}=\langle\tilde{\phi}_{i},1\rangle-\langle\tilde{\phi}_{j},1\rangle=\langle\tilde{\phi}_{i}-\tilde{\phi}_{j},1\rangle=0,$
where the first step uses (4.38), and the third step uses (4.42). We thus see
that

$\|\tilde{\phi}_{i}\|_{1}=\|\tilde{\phi}_{j}\|_{1}.$ (4.43)

Next, observe that $\lambda_{i}$ can be written as the product of two
functions on disjoint sets of variables, and likewise for $\lambda_{j}.$
Namely,

$\displaystyle\lambda_{i}$
$\displaystyle=\frac{1}{\|\tilde{\phi}_{i}\|_{1}}\;\tilde{\phi}_{i}\otimes\text{\rm
NOR}_{n-n^{\prime}},$ $\displaystyle\lambda_{j}$
$\displaystyle=\frac{1}{\|\tilde{\phi}_{j}\|_{1}}\;\tilde{\phi}_{j}\otimes\text{\rm
NOR}_{n-n^{\prime}}.$

Now

$\displaystyle\operatorname{orth}(\lambda_{i}-\lambda_{j})$
$\displaystyle=\operatorname{orth}\left(\left(\frac{\tilde{\phi}_{i}}{\|\tilde{\phi}_{i}\|_{1}}-\frac{\tilde{\phi}_{j}}{\|\tilde{\phi}_{j}\|_{1}}\right)\otimes\text{\rm
NOR}_{n-n^{\prime}}\right)$
$\displaystyle\geqslant\operatorname{orth}\left(\frac{\tilde{\phi}_{i}}{\|\tilde{\phi}_{i}\|_{1}}-\frac{\tilde{\phi}_{j}}{\|\tilde{\phi}_{j}\|_{1}}\right)$
$\displaystyle=\operatorname{orth}\left(\frac{\tilde{\phi}_{i}-\tilde{\phi}_{j}}{\|\tilde{\phi}_{i}\|_{1}}\right)$
$\displaystyle=\operatorname{orth}(\tilde{\phi}_{i}-\tilde{\phi}_{j})$
$\displaystyle\geqslant c^{\prime\prime}\sqrt{\frac{n^{\prime}}{m}},$

where the second step uses Proposition 2.6(ii), the third step applies (4.43),
and the last step is justified by (4.42). In view of
$c=\min\\{c^{\prime},c^{\prime\prime}\\},$ this settles (4.25) and completes
the proof. ∎

###  4.3. Hardness amplification for approximate degree

We have reached the crux of our proof, a hardness amplification theorem for
approximate degree. Unlike previous work, our hardness amplification is
directly applicable to Boolean functions with sparse input and does not use
componentwise composition or input compression. The theorem statement below
has a large number of parameters, for maximum generality and black-box
integration with the auxiliary results of previous sections. We will later
derive a succinct and easy-to-apply corollary that will suffice for our
hardness amplification purposes.

######  Theorem 4.5.

Let $C^{*}\geqslant 1$ and $c\in(0,1)$ be the absolute constants from Theorems
_3.6_ and  _4.4,_ respectively. Fix a real number $0<\beta<1$ and positive
integers $n,m,k,N,\theta,D,T$ such that

$\displaystyle n/2\geqslant m>k,$ (4.44) $\displaystyle
4(N+1)^{2}k\exp\left(-\frac{\sqrt{m}}{16k}\right)+(N+1)\left(\frac{3C^{*}\log^{2}(n+N+1)}{m^{1/4}}\right)^{k}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\leqslant\frac{\beta}{16(N+1)^{2}m^{2}},$
(4.45) $\displaystyle
T\geqslant\frac{8\mathrm{e}}{c}\cdot\theta(1+\ln\theta)+\theta k,$ (4.46)
$\displaystyle T\geqslant D.$ (4.47)

Define

$\Delta=\left(1+2^{D}\binom{n\theta}{D}\right)\exp\left(-\frac{c(T-\theta
k)}{2\sqrt{nm}}\right).$ (4.48)

Then there is an $($explicitly given$)$ mapping
$H\colon(\\{0,1\\}^{n})^{\theta}\to\\{0,1\\}^{N}$ such that:

  1. (i)

each output bit of $H$ is computable by a monotone $(k+1)$-DNF formula;

  2. (ii)

for every $\epsilon\in[0,1]$ and every $f\colon\\{0,1\\}^{N}\to\\{0,1\\},$ one
has

$\deg_{\epsilon-\beta\theta-2\Delta}((f\circ H)|_{\leqslant
T})\geqslant\min\left\\{c\deg_{\epsilon}(f|_{\leqslant\theta})\sqrt{\frac{n}{2m}},D\right\\}.$

###### Proof.

We may assume that

$\epsilon-\beta\theta-2\Delta\geqslant 0$ (4.49)

since otherwise the left-hand side in the approximate degree lower bound of
(ii) is by definition $+\infty$. Define $V\subseteq\mathbb{R}^{N}$ by
$V=\\{0^{N},e_{1},e_{2},\ldots,e_{N}\\}$ and set $r=N+1.$ In view of (4.44)
and (4.45), Corollary 3.10 gives an explicit integer $n^{\prime}\in(n/2,n]$
and an explicit
$(\frac{\beta}{16r^{2}m^{2}},\frac{\beta}{16r^{2}m^{2}},m)$-balanced coloring
$\gamma\colon\binom{[n^{\prime}]}{k}\to[r]$. Alternatively, if one is not
concerned about explicitness, the existence of $\gamma$ can be deduced from
the much simpler Corollary 3.3. Specifically, (4.45) forces $\sqrt{m}\geqslant
k$ and in particular $n\geqslant m\geqslant k^{2}\geqslant 1.$ Moreover,
(4.45) implies that
$3r\sqrt{k\ln(n+1)}/m^{k/4}\leqslant\frac{\beta}{16r^{2}m^{2}}.$ Now Corollary
3.3 guarantees the existence of a
$(\frac{\beta}{16r^{2}m^{2}},\frac{\beta}{16r^{2}m^{2}},m)$-balanced coloring
$\gamma\colon\binom{[n]}{k}\to[r]$.

Since $n^{\prime}\geqslant m>k,$ Theorem 4.4 gives explicit distributions
$\lambda_{0^{N}},\lambda_{e_{1}},\lambda_{e_{2}},\ldots,\lambda_{e_{N}}$ on
$\\{0,1\\}^{n}$ such that

$\displaystyle\operatorname{supp}\lambda_{v}\subseteq\\{x\in\\{0,1\\}^{n}:|x|=k\text{
or }|x|\geqslant m\\},$ $\displaystyle v\in V,$ (4.50)
$\displaystyle\\{0,1\\}^{n}|_{k}\cap\operatorname{supp}\lambda_{e_{i}}=\\{\mathbf{1}_{S}:S\in\gamma^{-1}(i)\\},$
$\displaystyle i\in[N],$ (4.51)
$\displaystyle\\{0,1\\}^{n}|_{k}\cap\operatorname{supp}\lambda_{0^{N}}=\\{\mathbf{1}_{S}:S\in\gamma^{-1}(N+1)\\},$
(4.52) $\displaystyle\lambda_{v}(\\{0,1\\}^{n}|_{k})\geqslant 1-\beta,$
$\displaystyle v\in V,$ (4.53)
$\displaystyle\lambda_{v}(\\{0,1\\}^{n}|_{t})\leqslant\frac{\exp(-c(t-k)/\sqrt{nm})}{c(t-k+1)^{2}},$
$\displaystyle v\in V,\;t\geqslant k,$ (4.54)
$\displaystyle\operatorname{orth}(\lambda_{v}-\lambda_{u})\geqslant
c\sqrt{\frac{n}{2m},}$ $\displaystyle v,u\in V.$ (4.55)

Properties (4.51) and (4.52) imply that

$\displaystyle\\{0,1\\}^{n}|_{k}\cap\operatorname{supp}\lambda_{u}\cap\operatorname{supp}\lambda_{v}$
$\displaystyle=\varnothing,$ $\displaystyle u,v\in V,\;u\neq v.$ (4.56)

For $\mathbf{v}=(\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{\theta})\in
V^{\theta}$, define

$\Lambda_{\mathbf{v}}=\bigotimes_{i=1}^{\theta}\lambda_{\mathbf{v}_{i}}.$
(4.57)

######  Claim 4.6.

For each $\mathbf{v}\in V^{\theta},$ there is a function
$\widetilde{\Lambda_{\mathbf{v}}}\colon(\\{0,1\\}^{n})^{\theta}\to\mathbb{R}$
such that

$\displaystyle\operatorname{supp}\widetilde{\Lambda_{\mathbf{v}}}\subseteq(\\{0,1\\}^{n})^{\theta}|_{\leqslant
T},$ (4.58)
$\displaystyle\operatorname{orth}(\Lambda_{\mathbf{v}}-\widetilde{\Lambda_{\mathbf{v}}})>D,$
(4.59)
$\displaystyle\|\Lambda_{\mathbf{v}}-\widetilde{\Lambda_{\mathbf{v}}}\|_{1}\leqslant\Delta.$
(4.60)

We will settle Claim 4.6, and all other claims, after the proof of the
theorem.

We now turn to the construction of the monotone mapping $H$ in the theorem
statement. Define $h\colon\\{0,1\\}^{n}\to\\{0,1\\}^{N}$ by

$\displaystyle(h(z))_{j}$
$\displaystyle=\bigvee_{S\in\binom{[n]}{k+1}\cup\gamma^{-1}(j)}\;\bigwedge_{s\in
S}z_{s},$ $\displaystyle j=1,2,\ldots,N.$ (4.61)

Clearly, this is a monotone DNF formula of width $k+1$. Define
$H\colon(\\{0,1\\}^{n})^{\theta}\to\\{0,1\\}^{N}$ by

$\displaystyle H(x_{1},x_{2},\ldots,x_{\theta})$
$\displaystyle=\bigvee_{i=1}^{\theta}h(x_{i}),$ $\displaystyle
x_{1},x_{2},\ldots,x_{\theta}\in\\{0,1\\}^{n},$ (4.62)

where the right-hand side is the componentwise disjunction of the Boolean
vectors $h(x_{1}),h(x_{2}),\ldots,h(x_{\theta}).$ Observe that both $h$ and
$H$ are monotone and are given explicitly in closed form in terms of the
coloring $\gamma$ constructed at the beginning of the proof. This settles (i).

For (ii), fix an arbitrary function $f\colon\\{0,1\\}^{N}\to\\{0,1\\}$ and
abbreviate

$d=\deg_{\epsilon}(f|_{\leqslant\theta}).$

By the dual characterization of approximate degree (Fact 2.8), there is a
function $\psi\colon\\{0,1\\}^{N}|_{\leqslant\theta}\to\mathbb{R}$ such that

$\displaystyle\|\psi\|_{1}=1,$ (4.63) $\displaystyle\langle
f,\psi\rangle>\epsilon,$ (4.64) $\displaystyle\operatorname{orth}\psi\geqslant
d.$ (4.65)

Define $\Psi\colon(\\{0,1\\}^{n})^{\theta}\to\mathbb{R}$ by

$\Psi=\sum_{u\in\\{0,1\\}^{N}|_{\leqslant\theta}}\psi(u)\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\mathbf{v}\in
V^{\theta}:\\\
\mathbf{v}_{1}+\mathbf{v}_{2}+\cdots+\mathbf{v}_{\theta}=u\end{subarray}}\widetilde{\Lambda_{\mathbf{v}}}.$
(4.66)

We will now use (4.44)–(4.66) to prove a sequence of claims.

######  Claim 4.7.

One has

$\displaystyle\operatorname{supp}\Psi\subseteq(\\{0,1\\}^{n})^{\theta}|_{\leqslant
T},$ (4.67) $\displaystyle\|\Psi\|_{1}\leqslant 1+\Delta,$ (4.68)
$\displaystyle\operatorname{orth}\Psi\geqslant\min\left\\{cd\sqrt{\frac{n}{2m}},D\right\\}.$
(4.69)

######  Claim 4.8.

Let $v\in V$ be given. Then for all
$z\in\\{0,1\\}^{n}|_{k}\cap\operatorname{supp}\lambda_{v},$ one has $h(z)=v.$

######  Claim 4.9.

Let $u\in\\{0,1\\}^{N}|_{\leqslant\theta}$ and
$\mathbf{v}=(\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{\theta})\in
V^{\theta}$ be given such that
$\mathbf{v}_{1}+\mathbf{v}_{2}+\cdots+\mathbf{v}_{\theta}=u.$ Then

$|f(u)-\langle\widetilde{\Lambda_{\mathbf{v}}},f\circ
H\rangle|\leqslant\beta\theta+\Delta.$ (4.70)

######  Claim 4.10.

One has

$\langle f\circ H,\Psi\rangle>(\epsilon-\beta\theta-2\Delta)\|\Psi\|_{1}.$
(4.71)

Note from (4.67) that $\Psi$ is supported on inputs of Hamming weight at most
$T$ and can therefore be regarded as a function on
$(\\{0,1\\}^{n})^{\theta}|_{\leqslant T}$. Now the claimed bound in (ii)
follows by Fact 2.8 in view of (4.69) and (4.71). The proof of the theorem is
complete. ∎

###### Proof of Claim  _4.6_..

Equations (4.46), (4.50), and (4.54) ensure that Lemma 2.5 is applicable to
the distributions
$\lambda_{\mathbf{v}_{1}},\lambda_{\mathbf{v}_{2}},\ldots,\lambda_{\mathbf{v}_{\theta}}$
with parameters $\ell=\theta,$ $B=n,$ $C=1/c$, and
$\alpha=\exp(-c/\sqrt{nm})$, whence

$\displaystyle\Lambda_{\mathbf{v}}((\\{0,1\\}^{n})^{\theta}|_{>T})$
$\displaystyle\leqslant\exp\left(-\frac{c(T-\theta k)}{2\sqrt{nm}}\right),$
$\displaystyle\mathbf{v}\in V^{\theta}.$

In view of (4.47), we can now invoke Lemma 2.13 with parameter $B=n\theta$ to
obtain a function
$\widetilde{\Lambda_{\mathbf{v}}}\colon(\\{0,1\\}^{n})^{\theta}\to\mathbb{R}$
that satisfies (4.58)–(4.60). ∎

###### Proof of Claim  _4.7_..

Observe from (4.58) that $\Psi$ is a linear combination of functions supported
on inputs of Hamming weight at most $T.$ This settles the support property
(4.67). Property (4.68) can be verified as follows:

$\displaystyle\|\Psi\|_{1}$
$\displaystyle\leqslant\sum_{u\in\\{0,1\\}^{N}|_{\leqslant\theta}}|\psi(u)|\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\mathbf{v}\in
V^{\theta}:\\\
\mathbf{v}_{1}+\mathbf{v}_{2}+\cdots+\mathbf{v}_{\theta}=u\end{subarray}}\|\widetilde{\Lambda{}_{\mathbf{v}}}\|_{1}$
$\displaystyle\leqslant\left(\sum_{u\in\\{0,1\\}^{N}|_{\leqslant\theta}}|\psi(u)|\right)\max_{\mathbf{v}\in
V^{\theta}}\|\widetilde{\Lambda_{\mathbf{v}}}\|_{1}$
$\displaystyle=\|\psi\|_{1}\max_{\mathbf{v}\in
V^{\theta}}\|\widetilde{\Lambda_{\mathbf{v}}}\|_{1}$
$\displaystyle\leqslant\|\psi\|_{1}\max_{\mathbf{v}\in
V^{\theta}}\\{\|\Lambda_{\mathbf{v}}\|_{1}+\|\widetilde{\Lambda_{\mathbf{v}}}-\Lambda_{\mathbf{v}}\|_{1}\\}$
$\displaystyle\leqslant 1+\Delta,$

where the first and fourth steps apply the triangle inequality, and the last
step uses (4.60) and (4.63).

To settle (4.69), consider an arbitrary polynomial
$P\colon(\\{0,1\\}^{n})^{\theta}\to\mathbb{R}$ of degree less than
$\min\\{cd\sqrt{n/(2m)},D\\}.$ Then

$\displaystyle\langle\Psi,P\rangle$
$\displaystyle=\sum_{u\in\\{0,1\\}^{N}|_{\leqslant\theta}}\psi(u)\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\mathbf{v}\in
V^{\theta}:\\\
\mathbf{v}_{1}+\mathbf{v}_{2}+\cdots+\mathbf{v}_{\theta}=u\end{subarray}}\langle\widetilde{\Lambda_{\mathbf{v}}},P\rangle$
$\displaystyle=\sum_{u\in\\{0,1\\}^{N}|_{\leqslant\theta}}\psi(u)\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\mathbf{v}\in
V^{\theta}:\\\
\mathbf{v}_{1}+\mathbf{v}_{2}+\cdots+\mathbf{v}_{\theta}=u\end{subarray}}[\langle\Lambda_{\mathbf{v}},P\rangle+\langle\widetilde{\Lambda_{\mathbf{v}}}-\Lambda_{\mathbf{v}},P\rangle]$
$\displaystyle=\sum_{u\in\\{0,1\\}^{N}|_{\leqslant\theta}}\psi(u)\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\mathbf{v}\in
V^{\theta}:\\\
\mathbf{v}_{1}+\mathbf{v}_{2}+\cdots+\mathbf{v}_{\theta}=u\end{subarray}}\langle\Lambda_{\mathbf{v}},P\rangle,$
(4.72)

where the first and second steps use the linearity of inner product, and the
third step is valid by (4.59). Equation (4.55) allows us to invoke Proposition
2.7 with $\ell=\theta$ and $\phi_{v}=\lambda_{v}$ to infer that the inner
product $\langle\Lambda_{\mathbf{v}},P\rangle$ is a polynomial in $\mathbf{v}$
of degree less than $d.$ As a result, Fact 2.15 implies that the expected
value in (4.72) is a polynomial in $u$ of degree less than $d.$ In summary,
(4.72) is the inner product of $\psi$ with a polynomial of degree less than
$d$ and is therefore zero by (4.65). The proof of (4.69) is complete. ∎

###### Proof of Claim  _4.8_..

Consider an arbitrary string $z\in\\{0,1\\}^{n}|_{k}$. Then

$(h(z))_{j}=\bigvee_{S\in\gamma^{-1}(j)}\;\bigwedge_{s\in
S}z_{s}=\mathbf{I}[z\in\operatorname{supp}\lambda_{e_{j}}],$

where the first step uses the defining equation (4.61) together with $|z|=k,$
and the second step applies (4.51) along with $|z|=k.$ Thus, $h(z)$ can be
written out explicitly as

$h(z)=(\mathbf{I}[z\in\operatorname{supp}\lambda_{e_{1}}],\mathbf{I}[z\in\operatorname{supp}\lambda_{e_{2}}],\ldots,\mathbf{I}[z\in\operatorname{supp}\lambda_{e_{N}}]).$
(4.73)

Now recall from (4.56) that a string $z$ of Hamming weight $k$ can belong to
at most one of the sets
$\operatorname{supp}\lambda_{0^{N}},\operatorname{supp}\lambda_{e_{1}},\operatorname{supp}\lambda_{e_{2}},\ldots,\operatorname{supp}\lambda_{e_{N}}.$
As a result, if $z\in\operatorname{supp}\lambda_{e_{i}}$ then
$z\notin\operatorname{supp}\lambda_{e_{j}}$ for all $j\neq i$ and consequently
$h(z)=e_{i}$ by (4.73). Analogously, if
$z\in\operatorname{supp}\lambda_{0^{N}}$ then
$z\notin\operatorname{supp}\lambda_{e_{j}}$ for all $j$ and consequently
$h(z)=0^{N}$ by (4.73). This settles the claim for all $v\in V.$ ∎

###### Proof of Claim  _4.9_..

Since $u$ is a Boolean vector, the equality
$\mathbf{v}_{1}+\mathbf{v}_{2}+\cdots+\mathbf{v}_{\theta}=u$ forces

$\mathbf{v}_{1}\vee\mathbf{v}_{2}\vee\cdots\vee\mathbf{v}_{\theta}=u,$ (4.74)

where the disjunction is applied componentwise. For any input
$(x_{1},x_{2},\ldots,x_{\theta})$ where
$x_{i}\in\\{0,1\\}^{n}|_{k}\cap\operatorname{supp}\lambda_{\mathbf{v}_{i}},$
we have

$(f\circ
H)(x_{1},x_{2},\ldots,x_{\theta})=f\left(\bigvee_{i=1}^{\theta}h(x_{i})\right)=f\left(\bigvee_{i=1}^{\theta}\mathbf{v}_{i}\right)=f(u),$

where the second and third steps use Claim 4.8 and (4.74), respectively. Since
$\operatorname{supp}\Lambda_{\mathbf{v}}=\prod_{i=1}^{\theta}\operatorname{supp}\lambda_{\mathbf{v}_{i}},$
we have shown that

$f\circ H\equiv f(u)\qquad\qquad\text{on
}\;\;(\\{0,1\\}^{n}|_{k})^{\theta}\cap\operatorname{supp}\Lambda_{\mathbf{v}}.$
(4.75)

Furthermore,

$\Lambda_{\mathbf{v}}((\\{0,1\\}^{n}|_{k})^{\theta})=\prod_{i=1}^{\theta}\lambda_{\mathbf{v}_{i}}(\\{0,1\\}^{n}|_{k})\geqslant(1-\beta)^{\theta}\geqslant
1-\beta\theta,$ (4.76)

where the second step uses (4.53). Now

$\displaystyle|f(u)-$
$\displaystyle\langle\widetilde{\Lambda_{\mathbf{v}}},f\circ H\rangle|$
$\displaystyle\leqslant|f(u)-\langle\Lambda_{\mathbf{v}},f\circ
H\rangle|+|\langle\Lambda_{\mathbf{v}}-\widetilde{\Lambda_{\mathbf{v}}},f\circ
H\rangle|$ $\displaystyle\leqslant|f(u)-\langle\Lambda_{\mathbf{v}},f\circ
H\rangle|+\|\Lambda_{\mathbf{v}}-\widetilde{\Lambda_{\mathbf{v}}}\|_{1}$
$\displaystyle=\left|f(u)-\operatorname*{\mathbf{E}}_{\Lambda_{\mathbf{v}}}f\circ
H\right|+\|\Lambda_{\mathbf{v}}-\widetilde{\Lambda_{\mathbf{v}}}\|_{1}$
$\displaystyle\leqslant\operatorname*{\mathbf{E}}_{\Lambda_{\mathbf{v}}}|f(u)-f\circ
H|+\|\Lambda_{\mathbf{v}}-\widetilde{\Lambda_{\mathbf{v}}}\|_{1}$
$\displaystyle\leqslant
0\cdot\Lambda_{\mathbf{v}}((\\{0,1\\}^{n}|_{k})^{\theta})+1\cdot\Lambda_{\mathbf{v}}(\overline{(\\{0,1\\}^{n}|_{k})^{\theta}})+\|\Lambda_{\mathbf{v}}-\widetilde{\Lambda_{\mathbf{v}}}\|_{1}$
$\displaystyle\leqslant\beta\theta+\|\Lambda_{\mathbf{v}}-\widetilde{\Lambda_{\mathbf{v}}}\|_{1}$
$\displaystyle\leqslant\beta\theta+\Delta,$

where the last three steps use (4.75), (4.76), and (4.60), respectively. ∎

###### Proof of Claim  _4.10_..

To begin with,

$\displaystyle\langle f,\psi\rangle-\langle f\circ H,\Psi\rangle$
$\displaystyle=\sum_{u\in\\{0,1\\}^{N}|_{\leqslant\theta}}\psi(u)f(u)$
$\displaystyle\qquad\qquad-\sum_{u\in\\{0,1\\}^{N}|_{\leqslant\theta}}\psi(u)\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\mathbf{v}\in
V^{\theta}:\\\
\mathbf{v}_{1}+\mathbf{v}_{2}+\cdots+\mathbf{v}_{\theta}=u\end{subarray}}\langle\widetilde{\Lambda_{\mathbf{v}}},f\circ
H\rangle$
$\displaystyle=\sum_{u\in\\{0,1\\}^{N}|_{\leqslant\theta}}\psi(u)\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\mathbf{v}\in
V^{\theta}:\\\
\mathbf{v}_{1}+\mathbf{v}_{2}+\cdots+\mathbf{v}_{\theta}=u\end{subarray}}[f(u)-\langle\widetilde{\Lambda_{\mathbf{v}}},f\circ
H\rangle]$
$\displaystyle\leqslant\sum_{u\in\\{0,1\\}^{N}|_{\leqslant\theta}}|\psi(u)|\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\mathbf{v}\in
V^{\theta}:\\\
\mathbf{v}_{1}+\mathbf{v}_{2}+\cdots+\mathbf{v}_{\theta}=u\end{subarray}}|f(u)-\langle\widetilde{\Lambda_{\mathbf{v}}},f\circ
H\rangle|$
$\displaystyle\leqslant\|\psi\|_{1}\max_{u\in\\{0,1\\}^{N}|_{\leqslant\theta}}\max_{\begin{subarray}{c}\mathbf{v}\in
V^{\theta}:\\\
\mathbf{v}_{1}+\mathbf{v}_{2}+\cdots+\mathbf{v}_{\theta}=u\end{subarray}}|f(u)-\langle\widetilde{\Lambda_{\mathbf{v}}},f\circ
H\rangle|$ $\displaystyle\leqslant\|\psi\|_{1}(\beta\theta+\Delta)$
$\displaystyle=\beta\theta+\Delta,$ (4.77)

where the last two steps use Claim 4.9 and (4.63), respectively. Then

$\displaystyle\langle f\circ H,\Psi\rangle$
$\displaystyle>\epsilon-\beta\theta-\Delta$
$\displaystyle\geqslant\frac{\epsilon-\beta\theta-\Delta}{1+\Delta}\cdot\|\Psi\|_{1}$
$\displaystyle\geqslant(\epsilon-\beta\theta-2\Delta)\|\Psi\|_{1},$

where the first step uses (4.64) and (4.77), the second step is justified by
(4.49) and (4.68), and the third step is legitimate since $a/(1+b)\geqslant
a-b$ for all $a\in[0,1]$ and $b\geqslant 0$. This completes the proof of
(4.71). ∎

###  4.4. Hardness amplification for one-sided approximate degree

In this section, we will prove that the construction of Theorem 4.5 amplifies
not only approximate degree but also its one-sided variant. We start with a
technical lemma.

######  Lemma 4.11.

Let $n,m,k,\theta,D,T$ be positive integers with

$\displaystyle T$ $\displaystyle\geqslant n+D,$ (4.78) $\displaystyle T$
$\displaystyle\geqslant\theta k.$ (4.79)

Let $y\in(\\{0,1\\}^{n})^{\theta}|_{>T}$ be given. Then there exists
$\zeta_{y}\colon(\\{0,1\\}^{n})^{\theta}\to\mathbb{R}$ such that

$\displaystyle\operatorname{supp}\zeta_{y}\subseteq(\\{0,1\\}^{n})^{\theta}|_{\leqslant
T}\cup\\{y\\},$ (4.80) $\displaystyle\zeta_{y}(y)=1,$ (4.81)
$\displaystyle\operatorname{orth}\zeta_{y}>D,$ (4.82)
$\displaystyle\|\zeta_{y}\|_{1}\leqslant 1+2^{D}\binom{n(\theta-1)}{D},$
(4.83) $\displaystyle\zeta_{y}=0\quad\text{ on
}\quad(\\{0,1\\}^{n}|_{\leqslant k})^{\theta}.$ (4.84)

###### Proof.

It follows from (4.79) that $y=(y_{1},y_{2},\ldots,y_{\theta})$ has a
coordinate with Hamming weight greater than $k.$ By symmetry, we may assume
that

$|y_{1}|>k.$ (4.85)

We have $|y_{2}y_{3}\ldots y_{\theta}|=|y|-|y_{1}|>T-n\geqslant D,$ where the
second step uses the hypothesis $|y|>T$ along with the trivial bound
$|y_{1}|\leqslant n,$ whereas the third step is legitimate by (4.78). Thanks
to the newly obtained inequality $|y_{2}y_{3}\ldots y_{\theta}|>D,$ Lemma 2.12
is applicable with $B=n(\theta-1)$ and gives a function
$\zeta\colon(\\{0,1\\}^{n})^{\theta-1}\to\mathbb{R}$ such that

$\displaystyle\operatorname{supp}\zeta\subseteq(\\{0,1\\}^{n})^{\theta-1}|_{\leqslant
D}\cup\\{y_{2}y_{3}\ldots y_{\theta}\\},$ (4.86)
$\displaystyle\zeta(y_{2}y_{3}\ldots y_{\theta})=1,$ (4.87)
$\displaystyle\|\zeta\|_{1}\leqslant 1+2^{D}\binom{n(\theta-1)}{D},$ (4.88)
$\displaystyle\operatorname{orth}\zeta>D.$ (4.89)

We will prove that the claimed properties (4.80)–(4.84) are enjoyed by the
function

$\zeta_{y}(x)=\delta_{x_{1},y_{1}}\zeta(x_{2}x_{3}\ldots x_{\theta}).$

To verify the support property (4.80), fix any $x$ with $\zeta_{y}(x)\neq 0.$
Then necessarily $\delta_{x_{1},y_{1}}=1,$ forcing $x_{1}=y_{1}.$ Now (4.86)
implies that $x$ either equals $y$ or has Hamming weight at most $|y_{1}|+D.$
Since $|y_{1}|+D\leqslant n+D\leqslant T$ by (4.78), this completes the proof
of (4.80).

The remaining properties are straightforward. Property (4.81) follows from the
corresponding property (4.87) of $\zeta$. Likewise, property (4.82) follows
from (4.89) in light of Proposition 2.6 (ii). Property (4.83) is immediate
from (4.88). Finally, (4.84) is a consequence of (4.85). ∎

We are now ready to state and prove our hardness amplification result, which
is a far-reaching generalization of Theorem 4.5.

######  Theorem 4.12.

Let $C^{*}\geqslant 1$ and $c\in(0,1)$ be the absolute constants from Theorems
_3.6_ and  _4.4,_ respectively. Fix a real number $0<\beta<1$ and positive
integers $n,m,k,N,\theta,D,T$ such that

$\displaystyle n/2\geqslant m>k,$ (4.90) $\displaystyle
4(N+1)^{2}k\exp\left(-\frac{\sqrt{m}}{16k}\right)+(N+1)\left(\frac{3C^{*}\log^{2}(n+N+1)}{m^{1/4}}\right)^{k}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\leqslant\frac{\beta}{16(N+1)^{2}m^{2}},$
(4.91) $\displaystyle
T\geqslant\frac{8\mathrm{e}}{c}\cdot\theta(1+\ln\theta)+\theta k,$ (4.92)
$\displaystyle T\geqslant D+n.$ (4.93)

Define

$\Delta=\left(1+2^{D}\binom{n\theta}{D}\right)\exp\left(-\frac{c(T-\theta
k)}{2\sqrt{nm}}\right).$ (4.94)

Then there is an $($explicitly given$)$ mapping
$H\colon(\\{0,1\\}^{n})^{\theta}\to\\{0,1\\}^{N}$ such that:

  1. (i)

each output bit of $H$ is computable by a monotone $(k+1)$-DNF formula;

  2. (ii)

for every $\epsilon\in[0,1]$ and every $f\colon\\{0,1\\}^{N}\to\\{0,1\\},$ one
has

$\deg_{\epsilon-\beta\theta-2\Delta}((f\circ H)|_{\leqslant
T})\geqslant\min\left\\{c\deg_{\epsilon}(f|_{\leqslant\theta})\sqrt{\frac{n}{2m}},D\right\\};$

  3. (iii)

for every $\epsilon\in[0,1]$ and every $f\colon\\{0,1\\}^{N}\to\\{0,1\\}$ with
$f(1^{N})=0,$ one has

$\deg^{+}_{\epsilon-\beta\theta-2\Delta}((f\circ H)|_{\leqslant
T})\geqslant\min\left\\{c\deg^{+}_{\epsilon}(f|_{\leqslant\theta})\sqrt{\frac{n}{2m}},D\right\\}.$

###### Proof.

As in the proof of Theorem 4.5, we may assume that

$\epsilon-\beta\theta-2\Delta\geqslant 0$ (4.95)

since otherwise the left-hand side in the lower bounds of (ii) and (iii) is by
definition $+\infty$. Define $V\subseteq\mathbb{R}^{N}$ by
$V=\\{0^{N},e_{1},e_{2},\ldots,e_{N}\\}$ and set $r=N+1.$ Arguing as in the
proof of Theorem 4.5, we obtain an explicit integer $n^{\prime}\in(n/2,n]$ and
an explicit
$(\frac{\beta}{16r^{2}m^{2}},\frac{\beta}{16r^{2}m^{2}},m)$-balanced coloring
$\gamma\colon\binom{[n^{\prime}]}{k}\to[r]$, which in turn results in explicit
distributions
$\lambda_{0^{N}},\lambda_{e_{1}},\lambda_{e_{2}},\ldots,\lambda_{e_{N}}$ on
$\\{0,1\\}^{n}$ such that

$\displaystyle\operatorname{supp}\lambda_{v}\subseteq\\{x\in\\{0,1\\}^{n}:|x|=k\text{
or }|x|\geqslant m\\},$ $\displaystyle v\in V,$ (4.96)
$\displaystyle\\{0,1\\}^{n}|_{k}\cap\operatorname{supp}\lambda_{e_{i}}=\\{\mathbf{1}_{S}:S\in\gamma^{-1}(i)\\},$
$\displaystyle i\in[N],$ (4.97)
$\displaystyle\\{0,1\\}^{n}|_{k}\cap\operatorname{supp}\lambda_{0^{N}}=\\{\mathbf{1}_{S}:S\in\gamma^{-1}(N+1)\\},$
(4.98) $\displaystyle\lambda_{v}(\\{0,1\\}^{n}|_{k})\geqslant 1-\beta,$
$\displaystyle v\in V,$ (4.99)
$\displaystyle\lambda_{v}(\\{0,1\\}^{n}|_{t})\leqslant\frac{\exp(-c(t-k)/\sqrt{nm})}{c(t-k+1)^{2}},$
$\displaystyle v\in V,\;t\geqslant k,$ (4.100)
$\displaystyle\operatorname{orth}(\lambda_{v}-\lambda_{u})\geqslant
c\sqrt{\frac{n}{2m},}$ $\displaystyle v,u\in V.$ (4.101)

Properties (4.97) and (4.98) imply that

$\displaystyle\\{0,1\\}^{n}|_{k}\cap\operatorname{supp}\lambda_{u}\cap\operatorname{supp}\lambda_{v}$
$\displaystyle=\varnothing,$ $\displaystyle u,v\in V,\;u\neq v.$ (4.102)

For $\mathbf{v}=(\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{\theta})\in
V^{\theta}$, define

$\Lambda_{\mathbf{v}}=\bigotimes_{i=1}^{\theta}\lambda_{\mathbf{v}_{i}}.$
(4.103)

######  Claim 4.13.

For each $\mathbf{v}\in V^{\theta},$ there is a function
$\widetilde{\Lambda_{\mathbf{v}}}\colon(\\{0,1\\}^{n})^{\theta}\to\mathbb{R}$
such that

$\displaystyle\operatorname{supp}\widetilde{\Lambda_{\mathbf{v}}}\subseteq(\\{0,1\\}^{n})^{\theta}|_{\leqslant
T},$ (4.104)
$\displaystyle\operatorname{orth}(\Lambda_{\mathbf{v}}-\widetilde{\Lambda_{\mathbf{v}}})>D,$
(4.105)
$\displaystyle\|\Lambda_{\mathbf{v}}-\widetilde{\Lambda_{\mathbf{v}}}\|_{1}\leqslant\Delta,$
(4.106)
$\displaystyle\widetilde{\Lambda_{\mathbf{v}}}=\Lambda_{\mathbf{v}}\qquad\text{on
}(\\{0,1\\}^{n}|_{\leqslant k})^{\theta}.$ (4.107)

We will settle Claim 4.13 after the proof of the theorem. We now define the
monotone mapping $H$ exactly the same way as in the proof of Theorem 4.5.
Specifically, define $h\colon\\{0,1\\}^{n}\to\\{0,1\\}^{N}$ by

$\displaystyle(h(z))_{j}$
$\displaystyle=\bigvee_{S\in\binom{[n]}{k+1}\cup\gamma^{-1}(j)}\;\bigwedge_{s\in
S}z_{s},$ $\displaystyle j=1,2,\ldots,N.$ (4.108)

Define $H\colon(\\{0,1\\}^{n})^{\theta}\to\\{0,1\\}^{N}$ by

$\displaystyle H(x_{1},x_{2},\ldots,x_{\theta})$
$\displaystyle=\bigvee_{i=1}^{\theta}h(x_{i}),$ $\displaystyle
x_{1},x_{2},\ldots,x_{\theta}\in\\{0,1\\}^{n},$ (4.109)

where the right-hand side is the componentwise disjunction of the Boolean
vectors $h(x_{1}),h(x_{2}),\ldots,h(x_{\theta}).$ With these definitions,
items (i) and (ii) are immediate because they are restatements of Theorem 4.5
(i), (ii). To prove the remaining item (iii), fix an arbitrary function
$f\colon\\{0,1\\}^{N}\to\\{0,1\\}$ with

$f(1^{N})=0,$ (4.110)

and abbreviate

$d=\deg^{+}_{\epsilon}(f|_{\leqslant\theta}).$

By the dual characterization of one-sided approximate degree (Fact 2.9), there
is a function $\psi\colon\\{0,1\\}^{N}|_{\leqslant\theta}\to\mathbb{R}$ such
that

$\displaystyle\|\psi\|_{1}=1,$ (4.111) $\displaystyle\langle
f,\psi\rangle>\epsilon,$ (4.112)
$\displaystyle\operatorname{orth}\psi\geqslant d,$ (4.113)
$\displaystyle\psi(x)\geqslant 0\quad\text{whenever}\quad f(x)=1.$ (4.114)

Define $\Psi\colon(\\{0,1\\}^{n})^{\theta}\to\mathbb{R}$ by

$\Psi=\sum_{u\in\\{0,1\\}^{N}|_{\leqslant\theta}}\psi(u)\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\mathbf{v}\in
V^{\theta}:\\\
\mathbf{v}_{1}+\mathbf{v}_{2}+\cdots+\mathbf{v}_{\theta}=u\end{subarray}}\widetilde{\Lambda_{\mathbf{v}}}.$
(4.115)

Equations (4.90)–(4.115) subsume the corresponding equations (4.44)–(4.66) in
the proof of Theorem 4.5. Recall that from (4.44)–(4.66), we deduced Claims
4.7–4.10. As a result, Claims 4.7–4.10 remain valid here as well. In
particular, we have

$\displaystyle\operatorname{supp}\Psi\subseteq(\\{0,1\\}^{n})^{\theta}|_{\leqslant
T},$ (4.116)
$\displaystyle\operatorname{orth}\Psi\geqslant\min\left\\{cd\sqrt{\frac{n}{2m}},D\right\\},$
(4.117) $\displaystyle h\equiv v\quad\text{on
}\\{0,1\\}^{n}|_{k}\cap\operatorname{supp}\lambda_{v}$ $\displaystyle(v\in
V),$ (4.118) $\displaystyle\langle f\circ
H,\Psi\rangle>(\epsilon-\beta\theta-2\Delta)\|\Psi\|_{1}.$ (4.119)

Moreover, we will shortly prove the following new claim.

######  Claim 4.14.

$\Psi(x)\geqslant 0$ whenever $(f\circ H)(x)=1.$

The lower bound on the one-sided approximate degree in (iii) now follows from
the dual characterization of one-sided approximate degree (Fact 2.9) in view
of (4.116)–(4.119) and Claim 4.14. This completes the proof of Theorem 4.12. ∎

###### Proof of Claim  _4.13._.

Fix $\mathbf{v}\in V^{\theta}$ arbitrarily for the remainder of the proof.
Equations (4.92), (4.96), and (4.100) ensure that Lemma 2.5 is applicable to
the distributions
$\lambda_{\mathbf{v}_{1}},\lambda_{\mathbf{v}_{2}},\ldots,\lambda_{\mathbf{v}_{\theta}}$
with parameters $\ell=\theta,$ $B=n,$ $C=1/c$, and
$\alpha=\exp(-c/\sqrt{nm})$, whence

$\displaystyle\Lambda_{\mathbf{v}}((\\{0,1\\}^{n})^{\theta}|_{>T})$
$\displaystyle\leqslant\exp\left(-\frac{c(T-\theta k)}{2\sqrt{nm}}\right).$
(4.120)

Recall from (4.92) and (4.93) that $T\geqslant D+n$ and $T\geqslant\theta k,$
which makes Lemma 4.11 applicable. Define
$\widetilde{\Lambda_{\mathbf{v}}}\colon(\\{0,1\\}^{n})^{\theta}\to\mathbb{R}$
by

$\widetilde{\Lambda_{\mathbf{v}}}=\Lambda_{\mathbf{v}}-\sum_{y\in(\\{0,1\\}^{n})^{\theta}|_{>T}}\Lambda_{\mathbf{v}}(y)\zeta_{y},$
(4.121)

where $\zeta_{y}$ is as given by Lemma 4.11. To verify the support property
(4.104), fix any input $x$ of Hamming weight $|x|>T.$ For all $y$ in the
summation with $y\neq x$, we have $\zeta_{y}(x)=0$ in view of (4.80). As a
result, (4.121) simplifies to
$\widetilde{\Lambda_{\mathbf{v}}}(x)=\Lambda_{\mathbf{v}}(x)-\Lambda_{\mathbf{v}}(x)\zeta_{x}(x).$
In view of (4.81), we conclude that $\widetilde{\Lambda_{\mathbf{v}}}(x)=0$.

The orthogonality property (4.105) follows from

$\operatorname{orth}(\Lambda_{\mathbf{v}}-\widetilde{\Lambda_{\mathbf{v}}})\geqslant\min_{y\in(\\{0,1\\}^{n})^{\theta}|_{>T}}\operatorname{orth}\zeta_{y}>D,$

where the first step uses the defining equation (4.121) and Proposition 2.6
(i), and the second step is legitimate by (4.82).

Property (4.106) can be verified as follows:

$\displaystyle\|\Lambda_{\mathbf{v}}-\widetilde{\Lambda_{\mathbf{v}}}\|_{1}$
$\displaystyle\leqslant\sum_{y\in(\\{0,1\\}^{n})^{\theta}|_{>T}}\Lambda_{\mathbf{v}}(y)\|\zeta_{y}\|_{1}$
$\displaystyle\leqslant\left(1+2^{D}\binom{n(\theta-1)}{D}\right)\sum_{y\in(\\{0,1\\}^{n})^{\theta}|_{>T}}\Lambda_{\mathbf{v}}(y)$
$\displaystyle\leqslant\left(1+2^{D}\binom{n(\theta-1)}{D}\right)\exp\left(-\frac{c(T-\theta
k)}{2\sqrt{nm}}\right)$ $\displaystyle\leqslant\Delta,$

where the first step uses the triangle inequality along with the defining
equation (4.121), the second step applies (4.83), the third step is valid by
(4.120), and the fourth step uses the definition (4.94).

Finally, (4.107) follows from the definition (4.121) in view of (4.84). ∎

###### Proof of Claim  _4.14._.

We will prove the claim in contrapositive form. Specifically, fix an arbitrary
string $x=(x_{1},x_{2},\ldots,x_{\theta})\in(\\{0,1\\}^{n})^{\theta}$ with
$\Psi(x)<0$. Our objective is to deduce that $(f\circ H)(x)=0.$

There are two cases to consider. If $|x_{i}|>k$ for some $i,$ then the
defining equation (4.108) implies that $h(x_{i})=1^{N}$. As a result,

$(f\circ
H)(x)=f(H(x))=f\left(\bigvee_{i=1}^{\theta}h(x_{i})\right)=f(1^{N})=0,$

where the last step uses (4.110).

We now treat the complementary case $x\in(\\{0,1\\}^{n}|_{\leqslant
k})^{\theta}.$ By (4.107) and (4.115),

$\displaystyle\Psi(x)$
$\displaystyle=\sum_{u\in\\{0,1\\}^{N}|_{\leqslant\theta}}\psi(u)\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\mathbf{v}\in
V^{\theta}:\\\
\mathbf{v}_{1}+\mathbf{v}_{2}+\cdots+\mathbf{v}_{\theta}=u\end{subarray}}\Lambda_{\mathbf{v}}(x)$
$\displaystyle=\sum_{u\in\\{0,1\\}^{N}|_{\leqslant\theta}}\psi(u)\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\mathbf{v}\in
V^{\theta}:\\\
\mathbf{v}_{1}+\mathbf{v}_{2}+\cdots+\mathbf{v}_{\theta}=u\end{subarray}}\;\prod_{i=1}^{\theta}\lambda_{\mathbf{v}_{i}}(x_{i}).$
(4.122)

It follows from $\Psi(x)<0$ that the summation in (4.122) contains at least
one negative term, corresponding to a string
$u\in\\{0,1\\}^{N}|_{\leqslant\theta}$. This forces

$\psi(u)<0$ (4.123)

and additionally implies the existence of
$\mathbf{v}_{1},\mathbf{v}_{2},\ldots,\mathbf{v}_{\theta}\in V$ with

$\displaystyle x_{i}\in\operatorname{supp}\lambda_{\mathbf{v}_{i}},$
$\displaystyle i=1,2,\ldots,\theta,$ (4.124)
$\displaystyle\sum_{i=1}^{\theta}\mathbf{v}_{i}=u.$ (4.125)

Since $x\in(\\{0,1\\}^{n}|_{\leqslant k})^{\theta}$ in the case under
consideration, it follows from (4.96) and (4.124) that $|x_{i}|=k$ for all
$i.$ Now (4.118) ensures that $h(x_{i})=\mathbf{v}_{i}$ for all $i,$ which in
turn makes it possible to rewrite (4.125) as $\sum_{i=1}^{\theta}h(x_{i})=u.$
Since $u,h(x_{1}),h(x_{2}),\ldots,h(x_{\theta})\in\\{0,1\\}^{N},$ we conclude
that $\bigvee_{i=1}^{\theta}h(x_{i})=u.$ As a result,

$(f\circ H)(x)=f\left(\bigvee_{i=1}^{\theta}h(x_{i})\right)=f(u)=0,$

where the last step is immediate from (4.114) and (4.123). ∎

###  4.5. Specializing the parameters

Theorems 4.5 and 4.12 have a large number of parameters that one can adjust to
produce various hardness amplification theorems. We do so in this section. For
any constants $\alpha\in(0,1]$ and $C\geqslant 1,$ we show how to transform a
function $f$ on $\theta^{C}$ bits with approximate degree

$\deg_{\epsilon}(f|_{\leqslant\theta})\geqslant\theta^{1-\alpha}$ (4.126)

into a function $F$ on $T^{1+\alpha}$ bits with approximate degree

$\deg_{\epsilon-\frac{1}{T}}(F|_{\leqslant T})\geqslant
T^{1-\frac{2}{3}\alpha}.$ (4.127)

Comparing the exponents in (4.126) and (4.127), we see that $F$ is harder to
approximate than $f$ relative to the Hamming weight of the inputs for $F$ and
$f$, respectively. Moreover, we show that $F$ is expressible as $F=f\circ H$
for some mapping $H$ whose output bits are computable by monotone DNF formulas
of constant width. In particular, if $f$ is a monotone DNF formula of constant
width, then so is $F.$ The formal statement follows.

######  Corollary 4.15.

Fix reals $\alpha\in(0,1],$ $A\geqslant 1,$ and $C\geqslant 1$ arbitrarily.
Then for all large enough integers $\theta,$ there is an $($explicitly
given$)$ mapping $H\colon\\{0,1\\}^{\lfloor
T^{1+\alpha}\rfloor}\to\\{0,1\\}^{\lfloor\theta^{C}\rfloor}$ with
$T=\lfloor\theta\log^{2}\theta\rfloor$ such that the output bits of $H$ are
computable by monotone $\lceil 50(A+C)/\alpha\rceil$-DNF formulas and

$\deg_{\epsilon-\frac{1}{T^{A}}}((f\circ H)|_{\leqslant T})\geqslant
T^{1-\frac{2}{3}\alpha}$ (4.128)

for every $\epsilon\in[0,1]$ and every function
$f\colon\\{0,1\\}^{\lfloor\theta^{C}\rfloor}\to\\{0,1\\}$ with
$\deg_{\epsilon}(f|_{\leqslant\theta})\geqslant\theta^{1-\alpha}$.

###### Proof.

Invoke Theorem 4.5 with parameters

$\displaystyle\beta$
$\displaystyle=\frac{1}{2\theta\lfloor\theta\log^{2}\theta\rfloor^{A}},$
(4.129) $\displaystyle N$ $\displaystyle=\lfloor\theta^{C}\rfloor,$ (4.130)
$\displaystyle n$ $\displaystyle=\lfloor\theta^{\alpha}\rfloor,$ (4.131)
$\displaystyle m$ $\displaystyle=\lfloor\theta^{\alpha/4}\rfloor,$ (4.132)
$\displaystyle k$
$\displaystyle=\left\lceil\frac{50(A+C)}{\alpha}\right\rceil-1,$ (4.133)
$\displaystyle D$ $\displaystyle=\lceil\theta^{1-\frac{5}{8}\alpha}\rceil,$
(4.134) $\displaystyle T$ $\displaystyle=\lfloor\theta\log^{2}\theta\rfloor.$
(4.135)

Provided that $\theta$ is large enough, these parameter settings satisfy the
theorem hypotheses (4.44)–(4.47), whereas (4.48) gives

$\Delta\leqslant\frac{1}{4T^{A}}.$ (4.136)

As a result, Theorem 4.5 guarantees that

$\deg_{\epsilon-\frac{1}{T^{A}}}((f\circ H)|_{\leqslant
T})\geqslant\frac{c}{2}\cdot\theta^{1-\frac{5}{8}\alpha},$ (4.137)

where $c\in(0,1)$ is the absolute constant from Theorem 4.4 and
$H\colon\\{0,1\\}^{\lfloor
T^{1+\alpha}\rfloor}\to\\{0,1\\}^{\lfloor\theta^{C}\rfloor}$ is an explicit
mapping whose output bits are computable by monotone $\lceil
50(A+C)/\alpha\rceil$-DNF formulas. (In fact, $H$ uses only
$n\theta\approx(T/\log^{2}T)^{1+\alpha}$ input bits, but this improvement is
not relevant for our purposes.) Provided that $\theta$ is large enough
relative to the absolute constant $c,$ we infer (4.128) immediately from
(4.137). ∎

Analogously, we have the following hardness amplification result for _one-
sided_ approximate degree.

######  Corollary 4.16.

Fix reals $\alpha\in(0,1],$ $A\geqslant 1,$ and $C\geqslant 1$ arbitrarily.
Then for all large enough integers $\theta,$ there is an $($explicitly
given$)$ mapping $H\colon\\{0,1\\}^{\lfloor
T^{1+\alpha}\rfloor}\to\\{0,1\\}^{\lfloor\theta^{C}\rfloor}$ with
$T=\lfloor\theta\log^{2}\theta\rfloor$ such that the output bits of $H$ are
computable by monotone $\lceil 50(A+C)/\alpha\rceil$-DNF formulas and

$\deg_{\epsilon-\frac{1}{T^{A}}}^{+}((f\circ H)|_{\leqslant T})\geqslant
T^{1-\frac{2}{3}\alpha}$ (4.138)

for every $\epsilon\in[0,1]$ and every function
$f\colon\\{0,1\\}^{\lfloor\theta^{C}\rfloor}\to\\{0,1\\}$ such that
$\deg_{\epsilon}^{+}(f|_{\leqslant\theta})\geqslant\theta^{1-\alpha}$ and
$f(1^{\lfloor\theta^{C}\rfloor})=0.$

###### Proof.

The proof is the same, mutatis mutandis, as that of Corollary 4.15.
Specifically, invoke Theorem 4.12 with parameters (4.129)–(4.135). Provided
that $\theta$ is large enough, these parameter settings satisfy the theorem
hypotheses (4.90)–(4.93), whereas (4.94) gives (4.136). As a result, Theorem
4.12 guarantees that

$\deg_{\epsilon-\frac{1}{T^{A}}}^{+}((f\circ H)|_{\leqslant
T})\geqslant\frac{c}{2}\cdot\theta^{1-\frac{5}{8}\alpha},$ (4.139)

where $c\in(0,1)$ is the absolute constant from Theorem 4.4 and
$H\colon\\{0,1\\}^{\lfloor
T^{1+\alpha}\rfloor}\to\\{0,1\\}^{\lfloor\theta^{C}\rfloor}$ is an explicit
mapping whose output bits are computable by monotone $\lceil
50(A+C)/\alpha\rceil$-DNF formulas. Provided that $\theta$ is large enough
relative to the absolute constant $c,$ this settles (4.138). ∎

##  5\. Main results

In this section, we will settle our main results on approximate degree and
present their applications to communication complexity.

###  5.1. Approximate degree of DNF and CNF formulas

We will start with the two-sided case. Our proof here amounts to taking the
trivial one-variable formula $x_{1}$ and iteratively applying the hardness
amplification of Corollary 4.15.

######  Theorem 5.1.

For every $\delta\in(0,1]$ and $\Delta\geqslant 1,$ there is a constant
$c\geqslant 1$ and an $($explicitly given$)$ family
$\\{f_{n}\\}_{n=1}^{\infty}$ of functions
$f_{n}\colon\\{0,1\\}^{n}\to\\{0,1\\}$ such that each $f_{n}$ is computable by
a monotone $c$-DNF formula and satisfies

$\displaystyle\deg_{\frac{1}{2}-\frac{1}{n^{\Delta}}}(f_{n})$
$\displaystyle\geqslant\frac{1}{c}\cdot n^{1-\delta},$ $\displaystyle
n=1,2,3,\ldots.$ (5.1)

###### Proof.

Let $K\geqslant 1$ be the smallest integer such that

$\displaystyle\frac{1-(2/3)^{K}}{1+(2/3)^{K-1}}>1-\delta.$ (5.2)

Define

$A=2\Delta+3.$ (5.3)

Now, let $n\geqslant 1$ be any large enough integer. Define
$T_{0},T_{1},T_{2},\ldots,T_{K}$ recursively by $T_{0}=\lfloor
n/\log^{2K}n\rfloor$ and $T_{i}=\lfloor T_{i-1}\log^{2}T_{i-1}\rfloor$ for
$i\geqslant 1.$ Thus,

$\displaystyle T_{i}$ $\displaystyle\leqslant\frac{n}{\log^{2(K-i)}n},$
$\displaystyle i=0,1,2,\ldots,K,$ (5.4) $\displaystyle T_{i}$
$\displaystyle\sim\frac{n}{\log^{2(K-i)}n},$ $\displaystyle i=0,1,2,\ldots,K,$
(5.5)

where $\sim$ denotes equality up to lower-order terms. Provided that $n$ is
larger than a certain constant, inductive application of Corollary 4.15 gives
functions

$\displaystyle g_{n,i}\colon\\{0,1\\}^{\lfloor T_{i}^{1+(2/3)^{i-1}}\rfloor}$
$\displaystyle\to\\{0,1\\},$ $\displaystyle i=0,1,2,\ldots,K,$ (5.6)

such that

$\displaystyle\deg_{\frac{1}{2}-\frac{1}{T_{0}^{A}}-\frac{1}{T_{1}^{A}}-\cdots-\frac{1}{T_{i}^{A}}}(g_{n,i}|_{\leqslant
T_{i}})$ $\displaystyle\geqslant T_{i}^{1-(2/3)^{i}},$ $\displaystyle
i=0,1,2,\ldots,K,$ (5.7)

and each $g_{n,i}$ is an explicitly constructed monotone $c_{i}$-DNF formula
for some constant $c_{i}$ independent of $n.$ In more detail, the requirement
(5.7) for $i=0$ is equivalent to
$\deg_{\frac{1}{2}-\frac{1}{T_{0}^{A}}}(g_{n,0}|_{\leqslant T_{0}})>0$ and is
trivially satisfied by the “dictator” function $g_{n,0}(x)=x_{1}$, whereas for
$i\geqslant 1$ the function $g_{n,i}$ is obtained constructively from
$g_{n,i-1}$ by invoking Corollary 4.15 with

$\displaystyle\alpha$ $\displaystyle=\left(\frac{2}{3}\right)^{i-1},$
$\displaystyle C$ $\displaystyle=1+\left(\frac{2}{3}\right)^{i-2},$
$\displaystyle\theta$ $\displaystyle=T_{i-1},$ $\displaystyle f$
$\displaystyle=g_{n,i-1},$ $\displaystyle\epsilon$
$\displaystyle=\frac{1}{2}-\frac{1}{T_{0}^{A}}-\frac{1}{T_{1}^{A}}-\cdots-\frac{1}{T_{i-1}^{A}}.$

Specializing (5.4)–(5.7) to $i=K$, the function $g_{n,K}$ is a monotone
$c_{K}$-DNF formula for some constant $c_{K}$ independent of $n,$ takes at
most $N:=n^{1+(2/3)^{K-1}}$ input variables, and has approximate degree

$\displaystyle\deg_{\frac{1}{2}-\frac{1}{N^{\Delta+1}}}(g_{n,K})$
$\displaystyle\geqslant\deg_{\frac{1}{2}-\frac{1}{T_{0}^{A}}-\frac{1}{T_{1}^{A}}-\cdots-\frac{1}{T_{K}^{A}}}(g_{n,K})$
$\displaystyle\geqslant\deg_{\frac{1}{2}-\frac{1}{T_{0}^{A}}-\frac{1}{T_{1}^{A}}-\cdots-\frac{1}{T_{K}^{A}}}(g_{n,K}|_{\leqslant
T_{K}})$ $\displaystyle=\Omega(n^{1-(2/3)^{K}})$
$\displaystyle=\omega(N^{1-\delta}),$

where the first and last steps hold for all large enough $n$ due to (5.3) and
(5.2), respectively. The desired function family $\\{f_{n}\\}_{n=1}^{\infty}$
can then be defined by setting

$f_{n}=g_{\lfloor n^{1/(1+(2/3)^{K-1})}\rfloor,K}$

for all $n$ larger than a certain constant $n_{0},$ and taking the remaining
functions $f_{1},f_{2},\ldots,f_{n_{0}}$ to be the dictator function $x\mapsto
x_{1}.$ ∎

Theorem 5.1 immediately implies Theorems 1.1 and 1.2 from the introduction. We
now move on to the one-sided case.

######  Theorem 5.2.

For every $\delta\in(0,1]$ and $\Delta\geqslant 1,$ there is a constant
$c\geqslant 1$ and an $($explicitly given$)$ family
$\\{f_{n}\\}_{n=1}^{\infty}$ of functions
$f_{n}\colon\\{0,1\\}^{n}\to\\{0,1\\}$ such that each $f_{n}$ is computable by
a monotone $c$-DNF formula and satisfies

$\displaystyle\deg_{\frac{1}{2}-\frac{1}{n^{\Delta}}}^{+}(\neg f_{n})$
$\displaystyle\geqslant\frac{1}{c}\cdot n^{1-\delta},$ $\displaystyle
n=1,2,3,\ldots.$ (5.8)

This result subsumes Theorem 5.1 and settles Theorem 1.4 in the introduction.
The proof below makes repeated use of the following observation: if one
applies Corollary 4.16 to a function $f$ that is the _negation_ of a constant-
width monotone DNF formula, then the resulting composition $f\circ H$ is again
the _negation_ of a constant-width monotone DNF formula. This is easy to see
by writing $\neg(f\circ H)=(\neg f)\circ H$ and noting that both $\neg f$ and
$H$ are computable by constant-width monotone DNF formulas.

###### Proof of Theorem  _5.2_..

Much of the proof is identical to that of Theorem 5.1. As before, let
$K\geqslant 1$ be the smallest integer such that

$\displaystyle\frac{1-(2/3)^{K}}{1+(2/3)^{K-1}}>1-\delta.$ (5.9)

Define

$A=2\Delta+3.$ (5.10)

Now, let $n\geqslant 1$ be any large enough integer. Define
$T_{0},T_{1},T_{2},\ldots,T_{K}$ recursively by $T_{0}=\lfloor
n/\log^{2K}n\rfloor$ and $T_{i}=\lfloor T_{i-1}\log^{2}T_{i-1}\rfloor$ for
$i\geqslant 1.$ Thus,

$\displaystyle T_{i}$ $\displaystyle\leqslant\frac{n}{\log^{2(K-i)}n},$
$\displaystyle i=0,1,2,\ldots,K,$ (5.11) $\displaystyle T_{i}$
$\displaystyle\sim\frac{n}{\log^{2(K-i)}n},$ $\displaystyle i=0,1,2,\ldots,K,$
(5.12)

where $\sim$ denotes equality up to lower-order terms. Provided that $n$ is
larger than a certain constant, inductive application of Corollary 4.16 gives
functions

$\displaystyle g_{n,i}\colon\\{0,1\\}^{\lfloor T_{i}^{1+(2/3)^{i-1}}\rfloor}$
$\displaystyle\to\\{0,1\\},$ $\displaystyle i=0,1,2,\ldots,K,$ (5.13)

such that

$\displaystyle\deg_{\frac{1}{2}-\frac{1}{T_{0}^{A}}-\frac{1}{T_{1}^{A}}-\cdots-\frac{1}{T_{i}^{A}}}^{+}(\neg
g_{n,i}|_{\leqslant T_{i}})$ $\displaystyle\geqslant T_{i}^{1-(2/3)^{i}},$
$\displaystyle i=0,1,2,\ldots,K,$ (5.14)

and each $g_{n,i}$ is an explicitly constructed monotone $c_{i}$-DNF formula
for some constant $c_{i}$ independent of $n.$ In more detail, the requirement
(5.14) for $i=0$ is equivalent to
$\deg_{\frac{1}{2}-\frac{1}{T_{0}^{A}}}^{+}(\neg g_{n,0}|_{\leqslant
T_{0}})>0$ and is trivially satisfied by the “dictator” function
$g_{n,0}(x)=x_{1}$. For $i\geqslant 1$, we obtain $g_{n,i}$ from $g_{n,i-1}$
by applying Corollary 4.16 with

$\displaystyle\alpha$ $\displaystyle=\left(\frac{2}{3}\right)^{i-1},$
$\displaystyle C$ $\displaystyle=1+\left(\frac{2}{3}\right)^{i-2},$
$\displaystyle\theta$ $\displaystyle=T_{i-1},$ $\displaystyle f$
$\displaystyle=\neg g_{n,i-1},$ $\displaystyle\epsilon$
$\displaystyle=\frac{1}{2}-\frac{1}{T_{0}^{A}}-\frac{1}{T_{1}^{A}}-\cdots-\frac{1}{T_{i-1}^{A}}.$

This appeal to Corollary 4.16 is legitimate because $g_{n,i-1}$ is a monotone
DNF formula and therefore its negation $f=\neg g_{n,i-1}$ evaluates to $0$ on
the all-ones input.

Specializing (5.11)–(5.14) to $i=K$, the function $g_{n,K}$ is a monotone
$c_{K}$-DNF formula for some constant $c_{K}$ independent of $n,$ takes at
most $N:=n^{1+(2/3)^{K-1}}$ input variables, and has one-sided approximate
degree

$\displaystyle\deg_{\frac{1}{2}-\frac{1}{N^{\Delta+1}}}^{+}(\neg g_{n,K})$
$\displaystyle\geqslant\deg_{\frac{1}{2}-\frac{1}{T_{0}^{A}}-\frac{1}{T_{1}^{A}}-\cdots-\frac{1}{T_{K}^{A}}}^{+}(\neg
g_{n,K})$
$\displaystyle\geqslant\deg_{\frac{1}{2}-\frac{1}{T_{0}^{A}}-\frac{1}{T_{1}^{A}}-\cdots-\frac{1}{T_{K}^{A}}}^{+}(\neg
g_{n,K}|_{\leqslant T_{K}})$ $\displaystyle=\Omega(n^{1-(2/3)^{K}})$
$\displaystyle=\omega(N^{1-\delta}),$

where the first and last steps hold for all large enough $n$ due to (5.10) and
(5.9), respectively. The desired function family $\\{f_{n}\\}_{n=1}^{\infty}$
can then be defined by setting

$f_{n}=g_{\lfloor n^{1/(1+(2/3)^{K-1})}\rfloor,K}$

for all $n$ larger than a certain constant $n_{0},$ and taking the remaining
functions $f_{1},f_{2},\ldots,f_{n_{0}}$ to be the dictator function $x\mapsto
x_{1}.$ ∎

###  5.2. Quantum communication complexity

Using the pattern matrix method, we will “lift” our approximate degree results
to a near-optimal lower bound on the communication complexity of DNF formulas
in the two-party quantum model. Before we can apply the pattern matrix method,
there is a technicality to address with regard to the representation of
Boolean values as real numbers. In this paper, we have followed the standard
convention of representing “true” and “false” as $1$ and $0,$ respectively.
There is another common encoding, inspired by Fourier analysis and used in the
pattern matrix method [38, 43], whereby “true” and “false” are represented as
$-1$ and $1,$ respectively. To switch back and forth between these
representations, we will use the following proposition.

######  Proposition 5.3.

For any function $f\colon X\to\mathbb{R}$ on a finite subset $X$ of Euclidean
space, and any reals $\epsilon\geqslant 0$ and $c\neq 0,$

$\displaystyle\deg_{\epsilon}(f+c)=\deg_{\epsilon}(f),$
$\displaystyle\deg_{|c|\epsilon}(cf)=\deg_{\epsilon}(f).$

###### Proof.

For any polynomial $p,$ we have the following equivalences:

$\displaystyle\|f-p\|_{\infty}\leqslant\epsilon\qquad\Leftrightarrow\qquad\|(f+c)-(p+c)\|_{\infty}\leqslant\epsilon,$
$\displaystyle\|f-p\|_{\infty}\leqslant\epsilon\qquad\Leftrightarrow\qquad\|cf-
cp\|_{\infty}\leqslant|c|\epsilon,$

where the second line uses $c\neq 0.$ ∎

As a corollary, we can relate in a precise way the approximate degree of a
Boolean function $f\colon X\to\\{0,1\\}$ and the approximate degree of the
associated $\pm 1$-valued function $f^{\prime}\colon X\to\\{-1,+1\\}$ given by
$f^{\prime}=$$(-1)^{f}.$

######  Corollary 5.4.

For any Boolean function $f\colon X\to\\{0,1\\}$ and any $\epsilon\geqslant
0,$

$\deg_{\epsilon}((-1)^{f})=\deg_{\epsilon/2}(f).$

###### Proof.

Since $f$ is Boolean-valued, we have the equality of functions
$(-1)^{f}=1-2f.$ Now
$\deg_{\epsilon}((-1)^{f})=\deg_{\epsilon}(1-2f)=\deg_{\epsilon}(-2f)=\deg_{2\cdot\epsilon/2}(-2f)=\deg_{\epsilon/2}(f),$
where the second and fourth steps apply Proposition 5.3. ∎

Corollary 5.4 makes it easy to convert approximate degree results between the
$0,1$ representation and $\pm 1$ representation. For communication complexity,
no conversion is necessary in the first place:

$\displaystyle Q_{\epsilon}^{*}(F)=Q_{\epsilon}^{*}((-1)^{F}),$ $\displaystyle
F\colon X\times Y\to\\{0,1\\},$ (5.15)

where $Q_{\epsilon}^{*}$ denotes $\epsilon$-error quantum communication
complexity with arbitrary prior entanglement. This equality holds because the
representation of “true” and “false” in a communication protocol is a purely
syntactic matter, and one can relabel the output values $0,1$ as $1,-1$,
respectively, without affecting the protocol’s correctness or communication
cost. We note that (5.15) and Corollary 5.4 pertain to the encoding of the
_output_ of a Boolean function $f$. How “true” and “false” bits are
represented in the _input_ to $f$ is immaterial both for communication
complexity and approximate degree because the bijection
$(0,1)\leftrightarrow(1,-1)$ is a linear map.

We are now in a position to prove the promised communication lower bounds. The
pattern matrix method for two-party quantum communication is given by the
following theorem [38, Theorem 1.1].

######  Theorem 5.5 (Sherstov).

Let $f\colon\\{0,1\\}^{t}\to\\{0,1\\}$ be given. Define
$F\colon\\{0,1\\}^{4t}\times\\{0,1\\}^{4t}\to\\{0,1\\}$ by

$F(x,y)=f\left(\bigvee_{i=1}^{4}(x_{1,i}\wedge
y_{1,i}),\ldots,\bigvee_{i=1}^{4}(x_{t,i}\wedge y_{t,i})\right).$

Then for all $\alpha\in[0,1)$ and $\beta<\alpha/2,$

$Q_{\beta}^{*}(F)\geqslant\frac{1}{4}\deg_{\alpha/2}(f)-\frac{1}{2}\log\left(\frac{3}{\alpha-2\beta}\right).$

The original statement in [38, Theorem 1.1] uses the $\pm 1$ representation
for the range of $f$ and $F.$ We translated it to the $0,1$ representation, as
stated in Theorem 5.5, by applying (5.15) to $F$ and Corollary 5.4 to $f.$ By
combining Theorems 5.1 and 5.5, we obtain our main result on the quantum
communication complexity of DNF formulas:

######  Theorem 5.6.

For all $\delta\in(0,1]$ and $A\geqslant 1,$ there is a constant $c\geqslant
1$ and an $($explicitly given$)$ family $\\{F_{n}\\}_{n=1}^{\infty}$ of two-
party communication problems
$F_{n}\colon\\{0,1\\}^{n}\times\\{0,1\\}^{n}\to\\{0,1\\}$ such that each
$F_{n}$ is computable by a monotone $c$-DNF formula and satisfies

$\displaystyle Q_{\frac{1}{2}-\frac{1}{n^{A}}}^{*}(F_{n})$
$\displaystyle=\Omega(n^{1-\delta}).$ (5.16)

###### Proof.

Theorem 5.1 gives a constant $c^{\prime}\geqslant 1$ and an explicit family
$\\{f_{n}\\}_{n=1}^{\infty}$ of functions
$f_{n}\colon\\{0,1\\}^{n}\to\\{0,1\\}$ such that each $f_{n}$ is computable by
a monotone $c^{\prime}$-DNF formula and satisfies

$\displaystyle\deg_{\frac{1}{2}-\frac{1}{n^{2A}}}(f_{n})$
$\displaystyle\geqslant\frac{1}{c^{\prime}}\cdot n^{1-\delta},$ $\displaystyle
n=1,2,3,\ldots.$ (5.17)

For $n\geqslant 4,$ define
$F_{n}\colon\\{0,1\\}^{n}\times\\{0,1\\}^{n}\to\\{0,1\\}$ by

$F_{n}(x,y)=f_{\lfloor n/4\rfloor}\left(\bigvee_{i=1}^{4}(x_{1,i}\wedge
y_{1,i}),\ldots,\bigvee_{i=1}^{4}(x_{\lfloor n/4\rfloor,i}\wedge y_{\lfloor
n/4\rfloor,i})\right),$

where we index the strings $x$ and $y$ as arrays of $\lfloor n/4\rfloor\times
4$ bits. Clearly, $F_{n}$ is computable by a monotone $2c^{\prime}$-DNF
formula. We now invoke the pattern matrix method for quantum communication
(Theorem 5.5) with parameters

$\displaystyle\alpha$ $\displaystyle=1-\frac{2}{\lfloor n/4\rfloor^{2A}},$
$\displaystyle\beta$ $\displaystyle=\frac{1}{2}-\frac{1}{n^{A}},$
$\displaystyle f$ $\displaystyle=f_{\lfloor n/4\rfloor},$

which satisfy $\beta<\alpha/2$ for all $n\geqslant 24.$ As a result,

$\displaystyle Q_{\frac{1}{2}-\frac{1}{n^{A}}}^{*}(F_{n})$
$\displaystyle\geqslant\frac{1}{4}\cdot\deg_{\frac{1}{2}-\frac{1}{\lfloor
n/4\rfloor^{2A}}}(f_{\lfloor
n/4\rfloor})-\frac{1}{2}\log\left(\frac{3}{\frac{2}{n^{A}}-\frac{2}{\lfloor
n/4\rfloor^{2A}}}\right)$
$\displaystyle\geqslant\frac{1}{4}\cdot\frac{1}{c^{\prime}}\cdot\left\lfloor\frac{n}{4}\right\rfloor^{1-\delta}-\frac{1}{2}\log\left(\frac{3}{\frac{2}{n^{A}}-\frac{2}{\lfloor
n/4\rfloor^{2A}}}\right)$

for all $n\geqslant 24,$ where the first inequality applies the pattern matrix
method, and the second inequality uses (5.17). Now (5.16) follows since
$A,c^{\prime},\delta$ are constants. ∎

Theorem 5.6 settles Theorem 1.9 from the introduction.

###  5.3. Randomized multiparty communication

We now turn to communication lower bounds for DNF formulas in the $k$-party
number-on-the-forehead model. Analogous to (5.15), we have

$\displaystyle R_{\epsilon}(F)=R_{\epsilon}((-1)^{F}),$ $\displaystyle F\colon
X_{1}\times X_{2}\times\cdots\times X_{k}\to\\{0,1\\},$ (5.18)

where $R_{\epsilon}$ denotes $\epsilon$-error number-on-the-forehead
randomized communication complexity. The _$k$ -party set disjointness problem_
$\text{\rm DISJ}_{n,k}\colon(\\{0,1\\}^{n})^{k}\to\\{0,1\\}$ is given by

$\text{\rm
DISJ}_{n,k}(x_{1},x_{2},\ldots,x_{k})=\bigwedge_{j=1}^{n}\bigvee_{i=1}^{k}\overline{x_{i,j}}.$

In other words, the problem asks whether there is a coordinate $j$ in which
each of the Boolean vectors $x_{1},x_{2},\ldots,x_{k}$ has a $1.$ If one views
$x_{1},x_{2},\ldots,x_{k}$ as the characteristic vectors of corresponding sets
$S_{1},S_{2},\ldots,S_{k}$, then the set disjointness function evaluates to
true if and only if $S_{1}\cap S_{2}\cap\cdots\cap S_{k}=\varnothing.$ For a
communication problem $g\colon X_{1}\times X_{2}\times\cdots\times
X_{k}\to\\{0,1\\}$ and a function $f\colon\\{0,1\\}^{n}\to\\{0,1\\},$ we view
the componentwise composition $f\circ g$ as a $k$-party communication problem
on $X_{1}^{n}\times X_{2}^{n}\times\cdots\times X_{k}^{n}.$ The multiparty
pattern matrix method [43, Theorem 5.1] gives a lower bound on the
communication complexity of $f\circ\text{\rm DISJ}_{m,k}$ in terms of the
approximate degree of $f$:

######  Theorem 5.7 (Sherstov).

Let $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ be given. Consider the $k$-party
communication problem $F$ defined by $F=f\circ\text{\rm DISJ}_{m,k}.$ Then for
all $\alpha,\beta\geqslant 0$ with $\beta<\alpha/2,$ one has

$R_{\beta}(F)\geqslant\frac{\deg_{\alpha/2}(f)}{2}\cdot\log\left(\frac{\sqrt{m}}{C2^{k}k}\right)-\log\frac{1}{\alpha-2\beta},$

where $C>0$ is an absolute constant.

The actual statement of the pattern matrix method in [43, Theorem 5.1] is for
functions $f$ and $F$ with range $\\{-1,+1\\}$. Theorem 5.7 above, stated for
functions with range $\\{0,1\\}$, is immediate from [43, Theorem 5.1] by
applying (5.18) to $F$ and Corollary 5.4 to $f$. We are now ready for our main
result on the randomized multiparty communication complexity of DNF formulas.

######  Theorem 5.8.

Fix arbitrary constants $\delta\in(0,1]$ and $A\geqslant 1$. Then for all
integers $n,k\geqslant 2,$ there is an $($explicitly given$)$ $k$-party
communication problem $F_{n,k}\colon(\\{0,1\\}^{n})^{k}\to\\{0,1\\}$ with

$\displaystyle
R_{1/3}(F_{n,k})\geqslant\left(\frac{n}{c4^{k}k^{2}}\right)^{1-\delta},$
(5.19) $\displaystyle
R_{\frac{1}{2}-\frac{1}{n^{A}}}(F_{n,k})\geqslant\frac{n^{1-\delta}}{c4^{k}},$
(5.20)

where $c\geqslant 1$ is a constant independent of $n$ and $k.$ Moreover, each
$F_{n,k}$ is computable by a monotone DNF formula of width $ck$ and size
$n^{c}$.

It will be helpful to keep in mind that the conclusion of Theorem 5.8 is
“monotone” in $c,$ in the sense that proving Theorem 5.8 for a given constant
$c$ proves it for all larger constants as well.

###### Proof.

Theorem 5.1 gives a constant $c^{\prime}\geqslant 1$ and an explicit family
$\\{f_{n}\\}_{n=1}^{\infty}$ of functions
$f_{n}\colon\\{0,1\\}^{n}\to\\{0,1\\}$ such that each $f_{n}$ is computable by
a monotone DNF formula of width $c^{\prime}$ and satisfies

$\displaystyle\deg_{\frac{1}{2}-\frac{1}{n^{2A/\delta}}}(f_{n})$
$\displaystyle\geqslant\frac{1}{c^{\prime}}\cdot n^{1-\frac{\delta}{2}},$
$\displaystyle n=1,2,3,\ldots.$ (5.21)

Let $C>0$ be the absolute constant from Theorem 5.7. For arbitrary integers
$n,k\geqslant 2,$ define

$F_{n,k}=\begin{cases}\text{\rm AND}_{k}&\text{if }n<\lceil
C2^{k+1}k\rceil^{2},\\\ f_{\lfloor n/\lceil
C2^{k+1}k\rceil^{2}\rfloor}\circ\neg\text{\rm DISJ}_{\lceil
C2^{k+1}k\rceil^{2},k}&\text{otherwise.}\end{cases}$

We first analyze the cost of representing $F_{n,k}$ as a DNF formula. If
$n<\lceil C2^{k+1}k\rceil^{2},$ then by definition $F_{n,k}$ is a monotone DNF
formula of width $k$ and size $1.$ In the complementary case, $f_{\lfloor
n/\lceil C2^{k+1}k\rceil^{2}\rfloor}$ is by construction a monotone DNF
formula of width $c^{\prime}$ and hence of size at most $n^{c^{\prime}},$
whereas $\neg\text{\rm DISJ}_{\lceil C2^{k+1}k\rceil^{2},k}$ is by definition
a monotone DNF formula of width $k$ and size at most $\lceil
C2^{k+1}k\rceil^{2}\leqslant n.$ As a result, the composed function $F_{n,k}$
is a monotone DNF formula of width $c^{\prime}k$ and size at most
$n^{c^{\prime}}\cdot n^{c^{\prime}}=n^{2c^{\prime}}.$ In particular, the claim
in the theorem statement regarding the width and size of $F_{n,k}$ as a
monotone DNF formula is valid for any constant $c\geqslant 2c^{\prime}.$

We now turn to the communication complexity of $F_{n,k}.$ Since $F_{n,k}$ is
nonconstant, we have the trivial bound

$\displaystyle R_{\epsilon}(F_{n,k})$ $\displaystyle\geqslant 1,$
$\displaystyle 0\leqslant\epsilon<\frac{1}{2}.$ (5.22)

We further claim that

$R_{\epsilon}(F_{n,k})\geqslant\frac{1}{2c^{\prime}}\cdot\left\lfloor\frac{n}{\lceil
C2^{k+1}k\rceil^{2}}\right\rfloor^{1-\frac{\delta}{2}}\\\
+\log\left(1-\frac{2}{\lfloor n/\lceil
C2^{k+1}k\rceil^{2}\rfloor^{2A/\delta}}-2\epsilon\right)\qquad$ (5.23)

whenever the logarithmic term is well-defined. For $n<\lceil
C2^{k+1}k\rceil^{2},$ this claim is vacuous. In the complementary case
$n\geqslant\lceil C2^{k+1}k\rceil^{2},$ consider the family
$\\{g_{n}\\}_{n=1}^{\infty}$ of functions
$g_{n}\colon\\{0,1\\}^{n}\to\\{0,1\\}$ given by
$g_{n}(x_{1},x_{2},\ldots,x_{n})=f_{n}(\neg x_{1},\neg x_{2},\ldots,\neg
x_{n})$. For each $n,$ it is clear that $g_{n}$ and $f_{n}$ have the same
approximate degree. Since $F_{n,k}=g_{\lfloor n/\lceil
C2^{k+1}k\rceil^{2}\rfloor}\circ\text{\rm DISJ}_{\lceil
C2^{k+1}k\rceil^{2},k},$ one now obtains (5.23) directly from (5.21) and the
multiparty pattern matrix method (Theorem 5.7).

For a sufficiently large constant $c\geqslant 1$, the communication lower
bound (5.19) follows from (5.23) for $n\geqslant c4^{k}k^{2}$ and follows from
(5.22) for $n<c4^{k}k^{2}$.

The proof of (5.20) is more tedious. Take the constant $c\geqslant 1$ large
enough that the following relations hold:

$\displaystyle\left\lfloor\frac{n^{\delta}}{\lceil
2C\rceil^{2}\log^{2}n}\right\rfloor\geqslant 2n^{\delta/2}$
$\displaystyle\text{for all }n\geqslant c,$ (5.24) $\displaystyle
n^{\delta^{2}/4}\geqslant 1+A\log n$ $\displaystyle\text{for all }n\geqslant
c,$ (5.25) $\displaystyle c\geqslant 2c^{\prime}.$ (5.26)

If $n^{1-\delta}<c4^{k},$ then (5.20) holds due to (5.22). In what follows, we
treat the complementary case when

$\frac{n^{1-\delta}}{c4^{k}}\geqslant 1$ (5.27)

and in particular

$\displaystyle n$ $\displaystyle\geqslant c,$ (5.28) $\displaystyle k$
$\displaystyle\leqslant\log n.$ (5.29)

Then

$\displaystyle\left\lfloor\frac{n}{\lceil
C2^{k+1}k\rceil^{2}}\right\rfloor^{1-\frac{\delta}{2}}$
$\displaystyle\geqslant\left\lfloor\frac{n}{\lceil
2C\rceil^{2}4^{k}k^{2}}\right\rfloor^{1-\frac{\delta}{2}}$
$\displaystyle\geqslant\left\lfloor\frac{n^{1-\delta}}{4^{k}}\cdot\frac{n^{\delta}}{\lceil
2C\rceil^{2}\log^{2}n}\right\rfloor^{1-\frac{\delta}{2}}$
$\displaystyle\geqslant\left\lfloor\frac{n^{1-\delta}}{4^{k}}\cdot
2n^{\delta/2}\right\rfloor^{1-\frac{\delta}{2}}$
$\displaystyle\geqslant\left(\frac{n^{1-\delta}}{4^{k}}\cdot
n^{\delta/2}\right)^{1-\frac{\delta}{2}}$
$\displaystyle\geqslant\frac{n^{1-\delta}}{4^{k}}\cdot n^{\delta^{2}/4}$
$\displaystyle\geqslant\frac{n^{1-\delta}}{4^{k}}\cdot(1+A\log n),$ (5.30)

where the second step uses (5.29), the third step uses (5.24) and (5.28), the
fourth step is valid by (5.27), and the last step uses (5.25) and (5.28).
Continuing,

$\displaystyle\log\left(1-\frac{2}{\lfloor n/\lceil
C2^{k+1}k\rceil^{2}\rfloor^{2A/\delta}}-2\left(\frac{1}{2}-\frac{1}{n^{A}}\right)\right)$
$\displaystyle\hskip 56.9055pt=\log\left(\frac{2}{n^{A}}-\frac{2}{\lfloor
n/\lceil C2^{k+1}k\rceil^{2}\rfloor^{2A/\delta}}\right)$ $\displaystyle\hskip
56.9055pt\geqslant\log\left(\frac{2}{n^{A}}-\frac{2}{\lfloor n/(\lceil
2C\rceil^{2}4^{k}k^{2})\rfloor^{2A/\delta}}\right)$ $\displaystyle\hskip
56.9055pt\geqslant\log\left(\frac{2}{n^{A}}-\frac{2}{\lfloor n/(\lceil
2C\rceil^{2}n^{1-\delta}\log^{2}n)\rfloor^{2A/\delta}}\right)$
$\displaystyle\hskip
56.9055pt\geqslant\log\left(\frac{2}{n^{A}}-\frac{2}{(2n^{\delta/2})^{2A/\delta}}\right)$
$\displaystyle\hskip
56.9055pt\geqslant\log\left(\frac{2}{n^{A}}-\frac{1}{n^{A}}\right)$
$\displaystyle\hskip 56.9055pt=-A\log n,$ (5.31)

where the third step uses (5.27) and (5.29), and the fourth step uses (5.24)
and (5.28). Now

$\displaystyle R_{\frac{1}{2}-\frac{1}{n^{A}}}(F_{n,k})$
$\displaystyle\geqslant\frac{1}{2c^{\prime}}\cdot\frac{n^{1-\delta}}{4^{k}}\cdot(1+A\log
n)-A\log n$ $\displaystyle\geqslant\frac{n^{1-\delta}}{c4^{k}}\cdot(1+A\log
n)-A\log n$ $\displaystyle\geqslant\frac{n^{1-\delta}}{c4^{k}},$

where the first step substitutes the bounds (5.30) and (5.31) into (5.23), the
second step uses (5.26), and the third step is valid by (5.27). This completes
the proof of (5.20). ∎

Theorem 5.8 settles Theorem 1.6 from the introduction.

######  Remark 5.9.

In this section, we considered $k$-party number-on-the-forehead bounded-error
communication complexity with _classical_ players. The model naturally extends
to _quantum_ players, and our lower bound in Theorem 5.8 implies an
$\Omega(n^{1-\delta}/4^{k}k)$ communication lower bound in this quantum
$k$-party number-on-the-forehead model for computing an explicit DNF formula
$F\colon(\\{0,1\\}^{n})^{k}\to\\{0,1\\}$ of size $n^{O(1)}$ and width $O(k)$
with error probability $\frac{1}{2}-\frac{1}{n^{A}},$ where the constants
$\delta>0$ and $A\geqslant 1$ can be set arbitrarily. In more detail, the
multiparty pattern matrix method actually gives a bound on the _generalized
discrepancy_ of the composed communication problem $F$. By the results of
[27], generalized discrepancy leads in turn to a lower bound on the
communication complexity of $F$ in the quantum $k$-party number-on-the-
forehead model. Quantitatively, the authors of [27] show that any classical
communication lower bound obtained via generalized discrepancy carries over to
the quantum model with only a factor of $\Theta(k)$ loss.

###  5.4. Nondeterministic and Merlin–Arthur multiparty communication

To obtain our results on nondeterminism and Merlin–Arthur communication, we
will now develop a general technique for transforming lower bounds on one-
sided approximate degree into lower bounds in these communication models. The
technique in question is implicit in the papers [23, 43] but has not been
previously formalized in our sought generality.

Consider a $k$-party communication problem $F\colon X_{1}\times
X_{2}\times\cdots\times X_{k}\to\\{0,1\\},$ for some finite sets
$X_{1},X_{2},\ldots,X_{k}$. A fundamental notion in the study of multiparty
communication is that of a _cylinder intersection_[6]_,_ defined as any
function $\chi:X_{1}\times X_{2}\times\cdots\times X_{k}\to\\{0,1\\}$ of the
form

$\chi(x_{1},\dots,x_{k})=\prod_{i=1}^{k}\phi_{i}(x_{1},\dots,x_{i-1},x_{i+1},\dots,x_{k})$

for some $\phi_{i}:X_{1}\times\cdots X_{i-1}\times X_{i+1}\times\cdots
X_{k}\to\\{0,1\\},$ $i=1,2,\dots,k.$ In other words, a cylinder intersection
is the product of $k$ Boolean functions, where the $i$-th function does not
depend on the $i$-th coordinate. For a probability distribution $\mu$ on the
domain of $F,$ the _discrepancy of $F$ with respect to $\mu$_ is denoted
$\operatorname{disc}_{\mu}(F)$ and defined as

$\displaystyle\operatorname{disc}_{\mu}(F)=\max_{\chi}\left|\operatorname*{\mathbf{E}}_{(x_{1},\ldots,x_{k})\sim\mu}(-1)^{F(x_{1},\ldots,x_{k})}\chi(x_{1},\dots,x_{k})\right|,$

where the maximum is taken over all cylinder intersections $\chi.$ This notion
of discrepancy was defined by Babai, Nisan, and Szegedy [6] and is unrelated
to the one that we encountered in Section 3.2. It is of interest to us because
of the following theorem [23, Theorem 4.1], which gives a lower bound on
nondeterministic and Merlin–Arthur communication complexity in terms of
discrepancy.

######  Theorem 5.10 (Gavinsky and Sherstov).

Let $F:X\to\\{0,1\\}$ be a given $k$-party communication problem, where
$X=X_{1}\times\cdots\times X_{k}.$ Fix a function $H:X\to\\{0,1\\}$ and a
probability distribution $\Pi$ on $X.$ Put

$\displaystyle\alpha$ $\displaystyle=\Pi(F^{-1}(1)\cap H^{-1}(1)),$
$\displaystyle\beta$ $\displaystyle=\Pi(F^{-1}(1)\cap H^{-1}(0)),$
$\displaystyle Q$
$\displaystyle=\log\frac{\alpha}{\beta+\operatorname{disc}_{\Pi}(H)}.$

Then

$\displaystyle N(F)\geqslant Q,$ (5.32) $\displaystyle\text{\it
MA}_{1/3}(F)^{2}\geqslant\min\left\\{\Omega(Q),\;\Omega\left(\frac{Q}{\log\\{2/\alpha\\}}\right)^{2}\right\\}$
(5.33) $\displaystyle\phantom{\text{\it
MA}_{1/3}(F)^{2}}\geqslant\Omega(Q)-\left(\log\frac{2}{\alpha}\right)^{2}.$
(5.34)

We note that the original statement in [23] is for functions with range
$\\{-1,+1\\}.$ The above version for $\\{0,1\\}$ follows immediately because
the output values of a communication protocol serve as textual labels that can
be changed at will. Equation (5.34), which is also not part of the statement
in [23], follows from (5.33) in view of the inequality $(q/a)^{2}\geqslant
2q-a^{2}$ for all reals $q,a$ with $a\neq 0.$ (Start with
$(q/a-a)^{2}\geqslant 0$ and multiply out the left-hand side.)

We will need yet another notion of discrepancy, introduced in [43] and called
“repeated discrepancy.” Let $G$ be a $k$-party communication problem on
$X=X_{1}\times X_{2}\times\cdots\times X_{k}$. A probability distribution
$\pi$ on the domain of $G$ is called _balanced_ if
$\pi(G^{-1}(0))=\pi(G^{-1}(1))=1/2.$ For such $\pi$, the _repeated discrepancy
of $G$ with respect to $\pi$ _is given by

$\operatorname{rdisc}_{\pi}(G)\,=\,\sup_{d,r\in\mathbb{Z}^{+}}\;\,\max_{\chi}\left|\operatorname*{\mathbf{E}}_{\ldots,x_{i,j},\ldots}\left[\chi(\dots,x_{i,j},\ldots)\prod_{i=1}^{d}(-1)^{G(x_{i,1})}\right]\right|^{1/d},$

where the maximum is over $k$-dimensional cylinder intersections $\chi$ on
$X^{dr}=X_{1}^{dr}\times X_{2}^{dr}\times\cdots\times X_{k}^{dr},$ and the
arguments $x_{i,j}$ $(i=1,2,\dots,d;\;j=1,2,\dots,r)$ are chosen independently
according to $\pi$ conditioned on $G(x_{i,1})=G(x_{i,2})=\cdots=G(x_{i,r})$
for each $i$. The repeated discrepancy of a communication problem is much
harder to bound from above than standard discrepancy. The following result
from [43, Theorem 4.27] bounds the repeated discrepancy of set disjointness.

######  Theorem 5.11 (Sherstov).

Let $m$ and $k$ be positive integers. Then there is a balanced probability
distribution $\pi$ on the domain of $\text{\rm DISJ}_{m,k}$ such that

$\operatorname{rdisc}_{\pi}(\text{\rm
DISJ}_{m,k})\leqslant\left(\frac{ck2^{k}}{\sqrt{m}}\right)^{1/2},$

where $c>0$ is an absolute constant independent of $m,k,\pi.$

It was shown in [43] that repeated discrepancy gives a highly efficient way to
transform multiparty communication protocols into polynomials. For a
nonnegative integer $d$ and a function $f$ on a finite subset of Euclidean
space, define

$E(f,d)=\min_{p}\\{\|f-p\|_{\infty}:\deg p\leqslant d\\},$

where the minimum is taken over polynomials of degree at most $d.$ In other
words, $E(f,d)$ stands for the minimum error in an $\ell_{\infty}$-norm
approximation of $f$ by a polynomial of degree at most $d.$ The following
result was proved in [43, Theorem 4.2].

######  Theorem 5.12 (Sherstov).

Let $G\colon X\to\\{0,1\\}$ be a $k$-party communication problem, where
$X=X_{1}\times X_{2}\times\cdots\times X_{k}$. For an integer $n\geqslant 1$
and a balanced probability distribution $\pi$ on the domain of $G$, consider
the linear operator
$L_{\pi,n}\colon\mathbb{R}^{X^{n}}\to\mathbb{R}^{\\{0,1\\}^{n}}$ given by

$\displaystyle(L_{\pi,n}\chi)(z)$
$\displaystyle=\operatorname*{\mathbf{E}}_{x_{1}\sim\pi_{z_{1}}}\cdots\operatorname*{\mathbf{E}}_{x_{n}\sim\pi_{z_{n}}}\chi(x_{1},\dots,x_{n}),$
$\displaystyle z\in\\{0,1\\}^{n},$ (5.35)

where $\pi_{0}$ and $\pi_{1}$ are the probability distributions induced by
$\pi$ on $G^{-1}(0)$ and $G^{-1}(1),$ respectively. Then for some absolute
constant $c>0$ and every $k$-dimensional cylinder intersection $\chi$ on
$X^{n}=X_{1}^{n}\times X_{2}^{n}\times\cdots\times X_{k}^{n},$

$\displaystyle E(L_{\pi,n}\chi,d-1)$
$\displaystyle\leqslant(c\operatorname{rdisc}_{\pi}(G))^{d},$ $\displaystyle
d=1,2,\dots,n.$

We are now in a position to derive the promised lower bound on
nondeterministic and Merlin–Arthur communication complexity in terms of one-
sided approximate degree. Our proof combines Theorems 5.10–5.12 in a way
closely analogous to the proof of [43, Theorem 6.9].

######  Theorem 5.13.

Let $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ be given. Let $m$ and $k$ be positive
integers, and put $F=f\circ\text{\rm DISJ}_{m,k}$. Then for all
$\epsilon\in(0,1/2],$

$\displaystyle N(F)$
$\displaystyle\geqslant\frac{\deg^{+}_{\epsilon}(f)}{2}\log\left(\frac{\sqrt{m}}{Ck2^{k}}\right)-\log\frac{1}{\epsilon},$
(5.36) $\displaystyle\text{\it MA}_{1/3}(F)^{2}$
$\displaystyle\geqslant\frac{\deg^{+}_{\epsilon}(f)}{C}\log\left(\frac{\sqrt{m}}{Ck2^{k}}\right)-\left(\log\frac{2}{\epsilon}\right)^{2},$
(5.37)

where $C\geqslant 1$ is an absolute constant, independent of
$f,n,m,k,\epsilon.$

###### Proof.

Abbreviate $d=\deg^{+}_{\epsilon}(f)$. Let $X=(\\{0,1\\}^{m})^{k}$ denote the
domain of $\text{\rm DISJ}_{m,k}$. By Theorem 5.11, there is a probability
distribution $\pi$ on $X$ such that

$\displaystyle\pi(\text{\rm DISJ}_{m,k}^{-1}(0))=\pi(\text{\rm
DISJ}_{m,k}^{-1}(1))=\frac{1}{2},$ (5.38)
$\displaystyle\operatorname{rdisc}_{\pi}(\text{\rm
DISJ}_{m,k})\leqslant\left(\frac{c^{\prime}k2^{k}}{\sqrt{m}}\right)^{1/2},$
(5.39)

where $c^{\prime}>0$ is an absolute constant independent of $m$ and $k.$ By
the dual characterization of one-sided approximate degree (Fact 2.9), there
exists a function $\psi\colon\\{0,1\\}^{n}\to\mathbb{R}$ such that

$\displaystyle\langle f,\psi\rangle>\epsilon,$ (5.40)
$\displaystyle\|\psi\|_{1}=1,$ (5.41)
$\displaystyle\operatorname{orth}\psi\geqslant d,$ (5.42)
$\displaystyle\psi\geqslant 0\;\text{ on }f^{-1}(1).$ (5.43)

Define $\Psi\colon X^{n}\to\mathbb{R}$ by

$\Psi(x)=2^{n}\psi(\text{\rm DISJ}_{m,k}(x_{1}),\ldots,\text{\rm
DISJ}_{m,k}(x_{n}))\prod_{i=1}^{n}\pi(x_{i}).$ (5.44)

######  Claim 5.14.

$\Psi$ satisfies

$\displaystyle\langle F,\Psi\rangle>\epsilon,$ (5.45)
$\displaystyle\|\Psi\|_{1}=1,$ (5.46) $\displaystyle\Psi\geqslant 0\quad\text{
on }F^{-1}(1).$ (5.47)

We will carry on with the theorem proof and settle the claims later. Equation
(5.46) allows us to write

$\Psi(x)=\Pi(x)\cdot(-1)^{1-H(x)}$ (5.48)

for some Boolean function $H\colon X^{n}\to\\{0,1\\}$ and a probability
distribution $\Pi$ on $X^{n}.$ Indeed, one can explicitly define
$\Pi(x)=|\Psi(x)|$ and $H(x)=\mathbf{I}[\Psi(x)\geqslant 0].$

######  Claim 5.15.

One has

$\displaystyle\Pi(F^{-1}(1)\cap H^{-1}(0))=0,$ (5.49)
$\displaystyle\Pi(F^{-1}(1)\cap H^{-1}(1))>\epsilon.$ (5.50)

######  Claim 5.16.

There is an absolute constant $c>0$ such that

$\operatorname{disc}_{\Pi}(H)\leqslant\left(\frac{ck2^{k}}{\sqrt{m}}\right)^{d/2}.$

The sought communication bounds (5.36) and (5.37) follow from Theorem 5.10 in
view of Claims 5.15 and 5.16. ∎

We now settle the claims used in the proof of Theorem 5.13.

###### Proof of Claim  _5.14._.

We have

$\displaystyle\langle F,\Psi\rangle$
$\displaystyle=2^{n}\operatorname*{\mathbf{E}}_{x_{1},\ldots,x_{n}\sim\pi}f(\ldots,\text{\rm
DISJ}_{m,k}(x_{i}),\ldots)\psi(\ldots,\text{\rm DISJ}_{m,k}(x_{i}),\ldots)$
$\displaystyle=2^{n}\operatorname*{\mathbf{E}}_{z\in\\{0,1\\}^{n}}f(z)\psi(z)$
$\displaystyle=\langle f,\psi\rangle$ $\displaystyle>\epsilon,$

where the second step uses (5.38), and the third step is legitimate by (5.40).
Analogously,

$\displaystyle\|\Psi\|_{1}$
$\displaystyle=2^{n}\operatorname*{\mathbf{E}}_{x_{1},\ldots,x_{n}\sim\pi}|\psi(\text{\rm
DISJ}_{m,k}(x_{1}),\ldots,\text{\rm DISJ}_{m,k}(x_{n}))|$
$\displaystyle=2^{n}\operatorname*{\mathbf{E}}_{z\in\\{0,1\\}^{n}}|\psi(z)|$
$\displaystyle=1,$

where the last two steps are valid by (5.38) and (5.41), respectively. The
final property (5.47) can be seen from the following chain of implications:

$\displaystyle x\in F^{-1}(1)$ $\displaystyle\Rightarrow(\text{\rm
DISJ}_{m,k}(x_{1}),\ldots,\text{\rm DISJ}_{m,k}(x_{n}))\in f^{-1}(1)$
$\displaystyle\Rightarrow\psi(\text{\rm DISJ}_{m,k}(x_{1}),\ldots,\text{\rm
DISJ}_{m,k}(x_{n}))\geqslant 0$ $\displaystyle\Rightarrow\Psi(x)\geqslant 0,$

where the first and third steps use the definitions of $F$ and $\Psi,$
respectively, and the second step is valid by (5.43). ∎

###### Proof of Claim  _5.15._.

Fix any point $x\in F^{-1}(1)\cap H^{-1}(0).$ Then (5.47) implies that
$\Psi(x)\geqslant 0,$ or equivalently $\Pi(x)\cdot(-1)^{1-H(x)}\geqslant 0.$
This forces $\Pi(x)\leqslant 0$ due to $H(x)=0$. Since $\Pi$ is a probability
distribution, we conclude that $\Pi(x)=0$. The proof of (5.49) is complete.
The remaining relation (5.50) can be seen as follows:

$\displaystyle\Pi(F^{-1}(1)\cap H^{-1}(1))$ $\displaystyle=\Pi(F^{-1}(1)\cap
H^{-1}(1))-\Pi(F^{-1}(1)\cap H^{-1}(0))$
$\displaystyle=\sum_{X^{n}}\Pi(x)F(x)(-1)^{1-H(x)}$
$\displaystyle=\langle\Psi,F\rangle$ $\displaystyle>\epsilon,$

where the first step exploits (5.49), and the last step applies (5.45). ∎

###### Proof of Claim  _5.16._.

Let $\pi_{0}$ and $\pi_{1}$ be the probability distributions induced by $\pi$
on $\text{\rm DISJ}_{m,k}^{-1}(0)$ and $\text{\rm DISJ}_{m,k}^{-1}(1),$
respectively, and let
$L_{\pi,n}\colon\mathbb{R}^{X^{n}}\to\mathbb{R}^{\\{0,1\\}^{n}}$ be the linear
operator given by (5.35). Then for any cylinder intersection $\chi\colon
X^{n}\to\\{0,1\\}$, we have

$\displaystyle\left|\operatorname*{\mathbf{E}}_{x\sim\Pi}(-1)^{H(x)}\chi(x)\right|$
$\displaystyle=\left|\sum_{X^{n}}\Pi(x)(-1)^{H(x)}\chi(x)\right|$
$\displaystyle=\left|\sum_{X^{n}}\Psi(x)\chi(x)\right|$
$\displaystyle=\left|2^{n}\operatorname*{\mathbf{E}}_{x_{1},\ldots,x_{n}\sim\pi}\psi(\ldots,\text{\rm
DISJ}_{m,k}(x_{i}),\ldots)\chi(x)\right|$
$\displaystyle=\left|\sum_{z\in\\{0,1\\}^{n}}\psi(z)\operatorname*{\mathbf{E}}_{x_{1}\sim\pi_{z_{1}}}\ldots\operatorname*{\mathbf{E}}_{x_{n}\sim\pi_{z_{n}}}\chi(x)\right|$
$\displaystyle=|\langle\psi,L_{\pi,n}\chi\rangle|,$ (5.51)

where the second step uses (5.48), the third step invokes the definition
(5.44), the fourth step is justified by (5.38), and the last step is valid by
the definition of $L_{\pi,n}$.

For every polynomial $p\colon\\{0,1\\}^{n}\to\mathbb{R}$ of degree less than
$d$, we have

$\displaystyle|\langle\psi,L_{\pi,n}\chi\rangle|$
$\displaystyle=|\langle\psi,L_{\pi,n}\chi-p\rangle+\langle\psi,p\rangle|$
$\displaystyle=|\langle\psi,L_{\pi,n}\chi-p\rangle|$
$\displaystyle\leqslant\|\psi\|_{1}\,\|L_{\pi,n}\chi-p\|_{\infty}$
$\displaystyle=\|L_{\pi,n}\chi-p\|_{\infty},$ (5.52)

where the second step uses (5.42), the third step applies Hölder’s inequality,
and the fourth step substitutes (5.41). Taking the infimum in (5.52) over all
polynomials $p$ of degree less than $d,$ we arrive at

$|\langle\psi,L_{\pi,n}\chi\rangle|\leqslant E(L_{\pi,n}\chi,d-1).$ (5.53)

Now

$\displaystyle\operatorname{disc}_{\Pi}(H)$
$\displaystyle=\max_{\chi}\left|\operatorname*{\mathbf{E}}_{x\sim\Pi}(-1)^{H(x)}\chi(x)\right|$
$\displaystyle\leqslant\max_{\chi}E(L_{\pi,n}\chi,d-1)$
$\displaystyle\leqslant(c^{\prime\prime}\operatorname{rdisc}_{\pi}(\text{\rm
DISJ}_{m,k}))^{d}$
$\displaystyle\leqslant\left(c^{\prime\prime}\left(\frac{c^{\prime}k2^{k}}{\sqrt{m}}\right)^{1/2}\right)^{d},$

where the first step maximizes over all cylinder intersections $\chi,$ the
second step combines (5.51) and (5.53), the third step is valid for some
absolute constant $c^{\prime\prime}>0$ by Theorem 5.12, and the fourth step
holds by (5.39). ∎

This completes the proof of Theorem 5.13. By combining it with our main result
on one-sided approximate degree, we now obtain our sought lower bounds for
nondeterministic and Merlin–Arthur multiparty communication.

######  Theorem 5.17.

Let $\delta>0$ be arbitrary. Then for all integers $n,k\geqslant 2,$ there is
an $($explicitly given$)$ $k$-party communication problem
$F_{n,k}\colon(\\{0,1\\}^{n})^{k}\to\\{0,1\\}$ with

$\displaystyle N(F_{n,k})\leqslant c\log n,$ (5.54) $\displaystyle N(\neg
F_{n,k})\geqslant\left(\frac{n}{c4^{k}k^{2}}\right)^{1-\delta},$ (5.55)
$\displaystyle R_{1/3}(\neg
F_{n,k})\geqslant\left(\frac{n}{c4^{k}k^{2}}\right)^{1-\delta},$ (5.56)
$\displaystyle\text{\it MA}_{1/3}(\neg
F_{n,k})\geqslant\left(\frac{n}{c4^{k}k^{2}}\right)^{\frac{1-\delta}{2}},$
(5.57)

where $c\geqslant 1$ is a constant independent of $n$ and $k.$ Moreover, each
$F_{n,k}$ is computable by a monotone DNF formula of width $ck$ and size
$n^{c}$.

###### Proof.

Theorem 5.2 gives a constant $c^{\prime}\geqslant 1$ and an explicit family
$\\{f_{n}\\}_{n=1}^{\infty}$ of functions
$f_{n}\colon\\{0,1\\}^{n}\to\\{0,1\\}$ such that each $f_{n}$ is computable by
a monotone DNF formula of width $c^{\prime}$ and satisfies

$\displaystyle\deg_{3/8}^{+}(\neg f_{n})$
$\displaystyle\geqslant\frac{1}{c^{\prime}}\cdot n^{1-\delta},$ $\displaystyle
n=1,2,3,\ldots.$ (5.58)

In particular,

$\displaystyle\deg_{3/8}(\neg f_{n})$
$\displaystyle\geqslant\frac{1}{c^{\prime}}\cdot n^{1-\delta},$ $\displaystyle
n=1,2,3,\ldots.$ (5.59)

Let $C\geqslant 1$ be the maximum of the absolute constants from Theorems 5.7
and 5.13. For arbitrary integers $n,k\geqslant 2,$ define

$F_{n,k}=\begin{cases}\text{\rm AND}_{k}&\text{if }n<\lceil
C2^{k+1}k\rceil^{2},\\\ f_{\lfloor n/\lceil
C2^{k+1}k\rceil^{2}\rfloor}\circ\neg\text{\rm DISJ}_{\lceil
C2^{k+1}k\rceil^{2},k}&\text{otherwise.}\end{cases}$

We first analyze the cost of representing $F_{n,k}$ as a DNF formula. If
$n<\lceil C2^{k+1}k\rceil^{2},$ then by definition $F_{n,k}$ is a monotone DNF
formula of width $k$ and size $1.$ In the complementary case, $f_{\lfloor
n/\lceil C2^{k+1}k\rceil^{2}\rfloor}$ is by construction a monotone DNF
formula of width $c^{\prime}$ and hence of size at most $n^{c^{\prime}},$
whereas $\neg\text{\rm DISJ}_{\lceil C2^{k+1}k\rceil^{2},k}$ is by definition
a monotone DNF formula of width $k$ and size at most $\lceil
C2^{k+1}k\rceil^{2}\leqslant n.$ As a result, the composed function $F_{n,k}$
is a monotone DNF formula of width $c^{\prime}k$ and size at most
$n^{c^{\prime}}\cdot n^{c^{\prime}}=n^{2c^{\prime}}.$ In particular, the claim
in the theorem statement regarding the width and size of $F_{n,k}$ as a
monotone DNF formula is valid for any large enough $c.$ This in turn implies
the upper bound in (5.54): consider the nondeterministic protocol in which the
parties “guess” one of the terms of the DNF formula for $F_{n,k}$ (for a cost
of $\lceil\log n^{2c^{\prime}}\rceil$ bits), evaluate it (using another $2$
bits of communication), and output the result.

We now turn to the communication lower bounds. Since $F_{n,k}$ is nonconstant,
we have the trivial bounds

$\displaystyle N(\neg F_{n,k})\geqslant 1,$ (5.60) $\displaystyle R_{1/3}(\neg
F_{n,k})\geqslant 1,$ (5.61) $\displaystyle\text{\it MA}_{1/3}(\neg
F_{n,k})\geqslant 1.$ (5.62)

We further claim that

$\displaystyle N(\neg
F_{n,k})\geqslant\frac{1}{2c^{\prime}}\cdot\left\lfloor\frac{n}{\lceil
C2^{k+1}k\rceil^{2}}\right\rfloor^{1-\delta}-\log\frac{8}{3},$ (5.63)
$\displaystyle R_{1/3}(\neg
F_{n,k})\geqslant\frac{1}{2c^{\prime}}\cdot\left\lfloor\frac{n}{\lceil
C2^{k+1}k\rceil^{2}}\right\rfloor^{1-\delta}-\log 12,$ (5.64)
$\displaystyle\text{\it MA}_{1/3}(\neg
F_{n,k})^{2}\geqslant\frac{1}{Cc^{\prime}}\cdot\left\lfloor\frac{n}{\lceil
C2^{k+1}k\rceil^{2}}\right\rfloor^{1-\delta}-\left(\log\frac{16}{3}\right)^{2}.$
(5.65)

For $n<\lceil C2^{k+1}k\rceil^{2},$ these claims are trivial since
communication complexity is nonnegative. In the complementary case
$n\geqslant\lceil C2^{k+1}k\rceil^{2},$ consider the family
$\\{g_{n}\\}_{n=1}^{\infty}$ of functions
$g_{n}\colon\\{0,1\\}^{n}\to\\{0,1\\}$ given by
$g_{n}(x_{1},x_{2},\ldots,x_{n})=\neg f_{n}(\neg x_{1},\neg x_{2},\ldots,\neg
x_{n})$. For each $n,$ it is clear that $g_{n}$ and $\neg f_{n}$ have the same
one-sided approximate degree. Since $\neg F_{n,k}=g_{\lfloor n/\lceil
C2^{k+1}k\rceil^{2}\rfloor}\circ\text{\rm DISJ}_{\lceil
C2^{k+1}k\rceil^{2},k},$ one now obtains (5.63) and (5.65) directly from
(5.58) and Theorem 5.13. Analogously, $g_{n}$ and $\neg f_{n}$ have the same
two-sided approximate degree for each $n$, and one obtains (5.64) from (5.59)
and Theorem 5.7.

For a large enough constant $c\geqslant 1$, the communication lower bounds
(5.55)–(5.57) follow from (5.63)–(5.65) for $n\geqslant c4^{k}k^{2}$, and from
(5.60)–(5.62) for $n<c4^{k}k^{2}$. ∎

Theorem 5.17 settles Theorem 1.7 from the introduction.

## Acknowledgments

The author is thankful to Justin Thaler and Mark Bun for useful comments on an
earlier version of this paper.

## References

  * [1] S. Aaronson and Y. Shi, Quantum lower bounds for the collision and the element distinctness problems, J. ACM, 51 (2004), pp. 595–605, doi:10.1145/1008731.1008735.
  * [2] M. Ajtai, H. Iwaniec, J. Komlós, J. Pintz, and E. Szemerédi, Construction of a thin set with small Fourier coefficients, Bulletin of the London Mathematical Society, 22 (1990), pp. 583–590, doi:10.1112/blms/22.6.583.
  * [3] L. Babai, Trading group theory for randomness, in Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing (STOC), 1985, pp. 421–429, doi:10.1145/22145.22192.
  * [4] L. Babai, P. Frankl, and J. Simon, Complexity classes in communication complexity theory, in Proceedings of the Twenty-Seventh Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1986, pp. 337–347, doi:10.1109/SFCS.1986.15.
  * [5] L. Babai and S. Moran, Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes, J. Comput. Syst. Sci., 36 (1988), pp. 254–276, doi:10.1016/0022-0000(88)90028-1.
  * [6] L. Babai, N. Nisan, and M. Szegedy, Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs, J. Comput. Syst. Sci., 45 (1992), pp. 204–232, doi:10.1016/0022-0000(92)90047-M.
  * [7] Z. Bar-Yossef, T. S. Jayram, R. Kumar, and D. Sivakumar, An information statistics approach to data stream and communication complexity, J. Comput. Syst. Sci., 68 (2004), pp. 702–732, doi:10.1016/j.jcss.2003.11.006.
  * [8] R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf, Quantum lower bounds by polynomials, J. ACM, 48 (2001), pp. 778–797, doi:10.1145/502090.502097.
  * [9] P. Beame, M. David, T. Pitassi, and P. Woelfel, Separating deterministic from nondeterministic NOF multiparty communication complexity, in Proceedings of the Thirty-Fourth International Colloquium on Automata, Languages and Programming (ICALP), 2007, pp. 134–145, doi:10.1007/978-3-540-73420-8_14.
  * [10] P. Beame, M. David, T. Pitassi, and P. Woelfel, Separating deterministic from randomized multiparty communication complexity, Theory of Computing, 6 (2010), pp. 201–225, doi:10.4086/toc.2010.v006a009.
  * [11] P. Beame and T. Huynh, Multiparty communication complexity and threshold circuit size of $\mathsf{AC}^{0}$, SIAM J. Comput., 41 (2012), pp. 484–518, doi:10.1137/100792779.
  * [12] P. Beame, T. Pitassi, N. Segerlind, and A. Wigderson, A strong direct product theorem for corruption and the multiparty communication complexity of disjointness, Computational Complexity, 15 (2006), pp. 391–432, doi:10.1007/s00037-007-0220-2.
  * [13] H. Buhrman and R. de Wolf, Communication complexity lower bounds by polynomials, in Proceedings of the Sixteenth Annual IEEE Conference on Computational Complexity (CCC), 2001, pp. 120–130, doi:10.1109/CCC.2001.933879.
  * [14] M. Bun, R. Kothari, and J. Thaler, The polynomial method strikes back: Tight quantum query bounds via dual polynomials, Theory Comput., 16 (2020), pp. 1–71, doi:10.4086/toc.2020.v016a010.
  * [15] M. Bun and J. Thaler, Dual lower bounds for approximate degree and Markov–Bernstein inequalities, Inf. Comput., 243 (2015), pp. 2–25, doi:10.1016/j.ic.2014.12.003.
  * [16] M. Bun and J. Thaler, Hardness amplification and the approximate degree of constant-depth circuits, in Proceedings of the Forty-Second International Colloquium on Automata, Languages and Programming (ICALP), 2015, pp. 268–280, doi:10.1007/978-3-662-47672-7_22.
  * [17] M. Bun and J. Thaler, A nearly optimal lower bound on the approximate degree of $\mathsf{AC}^{0}$, SIAM J. Comput., 49 (2020), doi:10.1137/17M1161737.
  * [18] M. Bun and J. Thaler, The large-error approximate degree of $\operatorname{\mathsf{AC}}^{0}$, Theory of Computing, 17 (2021), pp. 1–46, doi:10.4086/toc.2021.v017a007.
  * [19] A. K. Chandra, M. L. Furst, and R. J. Lipton, Multi-party protocols, in Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC), 1983, pp. 94–99, doi:10.1145/800061.808737.
  * [20] A. Chattopadhyay and A. Ada, Multiparty communication complexity of disjointness, in Electronic Colloquium on Computational Complexity (ECCC), January 2008.  Report TR08-002.
  * [21] H. Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statist., 23 (1952), pp. 493–507.
  * [22] M. David, T. Pitassi, and E. Viola, Improved separations between nondeterministic and randomized multiparty communication, ACM Transactions on Computation Theory (TOCT), 1 (2009), doi:10.1145/1595391.1595392.
  * [23] D. Gavinsky and A. A. Sherstov, A separation of $\mathsf{NP}$ and $\mathsf{coNP}$ in multiparty communication complexity, Theory of Computing, 6 (2010), pp. 227–245, doi:10.4086/toc.2010.v006a010.
  * [24] W. Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association, 58 (1963), pp. 13–30, doi:10.1080/01621459.1963.10500830.
  * [25] B. Kalyanasundaram and G. Schnitger, The probabilistic communication complexity of set intersection, SIAM J. Discrete Math., 5 (1992), pp. 545–557, doi:10.1137/0405044.
  * [26] T. Lee, A note on the sign degree of formulas, 2009.  Available at http://arxiv.org/abs/0909.4607.
  * [27] T. Lee, G. Schechtman, and A. Shraibman, Lower bounds on quantum multiparty communication complexity, in Proceedings of the Twenty-Fourth Annual IEEE Conference on Computational Complexity (CCC), 2009, pp. 254–262, doi:10.1109/CCC.2009.24.
  * [28] T. Lee and A. Shraibman, Disjointness is hard in the multiparty number-on-the-forehead model, Computational Complexity, 18 (2009), pp. 309–336, doi:10.1007/s00037-009-0276-2.
  * [29] N. S. Mande, J. Thaler, and S. Zhu, Improved approximate degree bounds for $k$-distinctness, in Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), vol. 158, 2020, pp. 2:1–2:22, doi:10.4230/LIPIcs.TQC.2020.2.
  * [30] M. L. Minsky and S. A. Papert, Perceptrons: An Introduction to Computational Geometry, MIT Press, Cambridge, Mass., 1969.
  * [31] N. Nisan and M. Szegedy, On the degree of Boolean functions as real polynomials, Computational Complexity, 4 (1994), pp. 301–313, doi:10.1007/BF01263419.
  * [32] A. A. Razborov, On the distributional complexity of disjointness, Theor. Comput. Sci., 106 (1992), pp. 385–390, doi:10.1016/0304-3975(92)90260-M.
  * [33] A. A. Razborov, Quantum communication complexity of symmetric predicates, Izvestiya of the Russian Academy of Sciences, Mathematics, 67 (2002), pp. 145–159.
  * [34] A. A. Razborov and A. A. Sherstov, The sign-rank of $\mathsf{AC}^{0}$, SIAM J. Comput., 39 (2010), pp. 1833–1855, doi:10.1137/080744037.
  * [35] B. Rosser, Explicit bounds for some functions of prime numbers, American Journal of Mathematics, 63 (1941), pp. 211–232.
  * [36] A. A. Sherstov, Communication lower bounds using dual polynomials, Bulletin of the EATCS, 95 (2008), pp. 59–93.
  * [37] A. A. Sherstov, Separating $\mathsf{AC}^{0}$ from depth-$2$ majority circuits, SIAM J. Comput., 38 (2009), pp. 2113–2129, doi:10.1137/08071421X.
  * [38] A. A. Sherstov, The pattern matrix method, SIAM J. Comput., 40 (2011), pp. 1969–2000, doi:10.1137/080733644.
  * [39] A. A. Sherstov, Strong direct product theorems for quantum communication and query complexity, SIAM J. Comput., 41 (2012), pp. 1122–1165, doi:10.1137/110842661.
  * [40] A. A. Sherstov, Approximating the AND-OR tree, Theory of Computing, 9 (2013), pp. 653–663, doi:10.4086/toc.2013.v009a020.
  * [41] A. A. Sherstov, The intersection of two halfspaces has high threshold degree, SIAM J. Comput., 42 (2013), pp. 2329–2374, doi:10.1137/100785260.
  * [42] A. A. Sherstov, Making polynomials robust to noise, Theory of Computing, 9 (2013), pp. 593–615, doi:10.4086/toc.2013.v009a018.
  * [43] A. A. Sherstov, Communication lower bounds using directional derivatives, J. ACM, 61 (2014), pp. 1–71, doi:10.1145/2629334.
  * [44] A. A. Sherstov, The multiparty communication complexity of set disjointness, SIAM J. Comput., 45 (2016), pp. 1450–1489, doi:10.1137/120891587.
  * [45] A. A. Sherstov, Breaking the Minsky–Papert barrier for constant-depth circuits, SIAM J. Comput., 47 (2018), pp. 1809–1857, doi:10.1137/15M1015704.
  * [46] A. A. Sherstov, The power of asymmetry in constant-depth circuits, SIAM J. Comput., 47 (2018), pp. 2362–2434, doi:10.1137/16M1064477.
  * [47] A. A. Sherstov, Algorithmic polynomials, SIAM J. Comput., 49 (2020), pp. 1173–1231, doi:10.1137/19M1278831.
  * [48] A. A. Sherstov, The hardest halfspace, Comput. Complex., 30 (2021), pp. 1–85, doi:10.1007/s00037-021-00211-4.
  * [49] A. A. Sherstov and P. Wu, Near-optimal lower bounds on the threshold degree and sign-rank of $\mathsf{AC}^{0}$, in Proceedings of the Fifty-First Annual ACM Symposium on Theory of Computing (STOC), 2019, pp. 401–412, doi:10.1145/3313276.3316408.
  * [50] R. Špalek, A dual polynomial for OR.  Available at http://arxiv.org/abs/0803.4516, 2008.
  * [51] R. de Wolf, Quantum Computing and Communication Complexity, PhD thesis, University of Amsterdam, 2001.

##  Appendix A Constructing low-discrepancy integer sets

The purpose of this appendix is to provide a detailed and self-contained proof
of Theorem 3.5, restated below.

######  Theorem.

Fix an integer $R\geqslant 1$ and reals $P\geqslant 2$ and $\Delta\geqslant
1$. Let $m$ be an integer with

$m\geqslant P^{2}(R+1).$

Fix a set $S_{p}\subseteq\\{1,2,\ldots,p-1\\}$ for each prime $p\in(P/2,P]$
with $p\nmid m$. Suppose further that the cardinalities of any two sets from
among the $S_{p}$ differ by a factor of at most $\Delta.$ Consider the
multiset

$S=\\{(r+s\cdot(p^{-1})_{m})\bmod m:\\\ \qquad r=1,\ldots,R;\quad
p\in(P/2,P]\text{ prime with }p\nmid m;\quad s\in S_{p}\\}.$

Then the elements of $S$ are pairwise distinct and nonzero. Moreover, if
$S\neq\varnothing$ then

$\operatorname{disc}_{m}(S)\leqslant\frac{c}{\sqrt{R}}+\frac{c\log m}{\log\log
m}\cdot\frac{\log
P}{P}\cdot\Delta+\max_{p}\\{\operatorname{disc}_{p}(S_{p})\\}$ (A.1)

for some $($explicitly given$)$ constant $c\geqslant 1$ independent of
$P,R,m,\Delta.$

The special case $\Delta=1$ in this result was proved in [48, Theorem 3.6],
and that proof applies with cosmetic changes to any $\Delta\geqslant 1.$ As a
service to the reader, we provide the complete derivation below; the treatment
here is the same word for word as in [48] except for one minor point of
departure to handle arbitrary $\Delta\geqslant 1$. We use the same notation as
in [48] and in particular denote the modulus by lowercase $m,$ as opposed to
the uppercase $M$ in the main body of our paper (Theorem 3.5). Analogous to
[48], the presentation is broken down into five key milestones, corresponding
to Sections A.1–A.5 below.

###  A.1. Exponential notation

In the remainder of this manuscript, we adopt the shorthand

$e(x)=\exp(2\pi x\mathbf{i}),$

where $\mathbf{i}$ is the imaginary unit. We will need the following bounds
[48, Section 6.1]:

$\displaystyle|1-e(x)|$ $\displaystyle\leqslant 2\pi x,$ $\displaystyle
0\leqslant x\leqslant 1,$ (A.2) $\displaystyle|1-e(x)|$
$\displaystyle\geqslant 4\min(x,1-x),$ $\displaystyle 0\leqslant x\leqslant
1.$ (A.3)

Let $\mathcal{P}$ denote the set of prime numbers $p\in(P/2,P]$ with $p\nmid
m.$ In this notation, the multiset $S$ is given by

$S=\\{(r+s\cdot(p^{-1})_{m})\bmod m:p\in\mathcal{P},\;s\in
S_{p},\;r=1,2,\ldots,R\\}.$

There are precisely $\pi(P)-\pi(P/2)$ primes in $(P/2,P],$ of which at most
$\nu(m)$ are prime divisors of $m.$ Therefore,

$|\mathcal{P}|\geqslant\pi(P)-\pi\left(\frac{P}{2}\right)-\nu(m).$ (A.4)

###  A.2. Elements of _S_ are nonzero and distinct

As our first step, we verify that the elements of $S$ are nonzero and distinct
modulo $m$. This part of the argument is reproduced word for word from [48,
Section 6.2].

Specifically, consider any $r\in\\{1,2,\ldots,R\\}$, any prime $p\in(P/2,P]$
with $p\nmid m,$ and any $s\in S_{p}.$ Then $pr+s\in[1,PR+P-1]\subseteq[1,m).$
This means that $pr+s\not\equiv 0\pmod{m},$ which in turn implies that
$r+s\cdot(p^{-1})_{m}\not\equiv 0\pmod{m}$.

We now show that the multiset $S$ contains no repeated elements. For this,
consider any $r,r^{\prime}\in\\{1,2,\ldots,R\\},$ any primes
$p,p^{\prime}\in\mathcal{P},$ and any $s\in S_{p}$ and $s^{\prime}\in
S_{p^{\prime}}$ such that

$r+s\cdot(p^{-1})_{m}\equiv
r^{\prime}+s^{\prime}\cdot(p^{\prime-1})_{m}\pmod{m}.$ (A.5)

Our goal is to show that $p=p^{\prime},r=r^{\prime},s=s^{\prime}.$ To this
end, multiply (A.5) through by $pp^{\prime}$ to obtain

$r\cdot pp^{\prime}+s\cdot p^{\prime}\equiv r^{\prime}\cdot
pp^{\prime}+s^{\prime}\cdot p\pmod{m}.$ (A.6)

The left-hand side and right-hand side of (A.6) are integers in
$[1,RP^{2}+(P-1)P]\subseteq[1,m),$ whence

$r\cdot pp^{\prime}+s\cdot p^{\prime}=r^{\prime}\cdot
pp^{\prime}+s^{\prime}\cdot p.$ (A.7)

This implies that $p\mid s\cdot p^{\prime},$ which in view of $s<p$ and the
primality of $p$ and $p^{\prime}$ forces $p=p^{\prime}.$ Now (A.7) simplifies
to

$r\cdot p+s=r^{\prime}\cdot p+s^{\prime},$ (A.8)

which in turn yields $s\equiv s^{\prime}\pmod{p}$. Recalling that
$s,s^{\prime}\in\\{1,2,\ldots,p-1\\},$ we arrive at $s=s^{\prime}.$ Finally,
substituting $s=s^{\prime}$ in (A.8) gives $r=r^{\prime}.$

###  A.3. Correlation for _k_ small

So far, we have shown that the elements of $S$ are distinct and nonzero. To
bound the $m$-discrepancy of this set, we must bound the exponential sum

$\left|\sum_{s\in S}e\left(\frac{k}{m}\cdot s\right)\right|$ (A.9)

for all $k=1,2,\ldots,m-1.$ This subsection and the next provide two
complementary bounds on (A.9). The first bound, presented below, is preferable
when $k$ is close to zero modulo $m.$

######  Claim A.1.

Let $k\in\\{1,2,\ldots,m-1\\}$ be given. Then

$\left|\sum_{s\in S}e\left(\frac{k}{m}\cdot s\right)\right|\\\
\leqslant\left(\frac{2\pi\min(k,m-k)}{m}+\max_{p\in\mathcal{P}}\\{\operatorname{disc}_{p}(S_{p})\\}+\frac{\nu(k)+\nu(m-k)}{|\mathcal{P}|}\cdot\Delta\right)|S|.$

This claim generalizes the analogous statement in [48, Claim 6.10], where the
special case $\Delta=1$ was considered.

###### Proof.

Let $\mathcal{P}^{\prime}$ be the set of those primes in $\mathcal{P}$ that
divide neither $k$ nor $m-k.$ Then clearly

$|\mathcal{P}\setminus\mathcal{P}^{\prime}|\leqslant\nu(k)+\nu(m-k).$ (A.10)

Exactly as in [48], we have

$\displaystyle\left|\sum_{s\in S}e\left(\frac{k}{m}\cdot s\right)\right|$
$\displaystyle\qquad=\left|\sum_{r=1}^{R}\sum_{p\in\mathcal{P}}\sum_{s\in
S_{p}}e\left(\frac{k}{m}\cdot(r+s\cdot(p^{-1})_{m})\right)\right|$
$\displaystyle\qquad\leqslant\sum_{r=1}^{R}\sum_{p\in\mathcal{P}}\left|\sum_{s\in
S_{p}}e\left(\frac{k}{m}\cdot(r+s\cdot(p^{-1})_{m})\right)\right|$
$\displaystyle\qquad=R\sum_{p\in\mathcal{P}}\left|\sum_{s\in
S_{p}}e\left(\frac{ks\cdot(p^{-1})_{m}}{m}\right)\right|$
$\displaystyle\qquad\leqslant R\sum_{p\in\mathcal{P}^{\prime}}\left|\sum_{s\in
S_{p}}e\left(\frac{ks\cdot(p^{-1})_{m}}{m}\right)\right|+R\sum_{p\in\mathcal{P}\setminus\mathcal{P}^{\prime}}\left|\sum_{s\in
S_{p}}e\left(\frac{ks\cdot(p^{-1})_{m}}{m}\right)\right|$
$\displaystyle\qquad\leqslant R\sum_{p\in\mathcal{P}^{\prime}}\left|\sum_{s\in
S_{p}}e\left(\frac{ks\cdot(p^{-1})_{m}}{m}\right)\right|+R\sum_{p\in\mathcal{P}\setminus\mathcal{P}^{\prime}}|S_{p}|.$
(A.11)

We proceed to bound the two summations in (A.11). Bounding the second
summation is straightforward:

$\displaystyle R\sum_{p\in\mathcal{P}\setminus\mathcal{P}^{\prime}}|S_{p}|$
$\displaystyle\leqslant
R\cdot\frac{|\mathcal{P}\setminus\mathcal{P}^{\prime}|}{|\mathcal{P}|}\sum_{p\in\mathcal{P}}\Delta|S_{p}|$
$\displaystyle=\frac{|\mathcal{P}\setminus\mathcal{P}^{\prime}|}{|\mathcal{P}|}\cdot\Delta|S|$
$\displaystyle\leqslant\frac{\nu(k)+\nu(m-k)}{|\mathcal{P}|}\cdot\Delta|S|,$
(A.12)

where the first step is valid because the cardinalities of any two sets
$S_{p}$ differ by a factor of at most $\Delta,$ and the last step uses (A.10).
This three-line derivation is our only point of departure from the treatment
in [48].

The other summation in (A.11) is analyzed exactly as in [48]. For
$p\in\mathcal{P}^{\prime}$ and $K\in\\{k,k-m\\},$ we have

$\displaystyle\left|\sum_{s\in
S_{p}}e\left(\frac{ks\cdot(p^{-1})_{m}}{m}\right)\right|$
$\displaystyle=\left|\sum_{s\in
S_{p}}e\left(\frac{Ks\cdot(p^{-1})_{m}}{m}\right)\right|$
$\displaystyle=\left|\sum_{s\in
S_{p}}e\left(-\frac{Ks\cdot(m^{-1})_{p}}{p}\right)e\left(\frac{Ks}{pm}\right)\right|$
$\displaystyle\leqslant\left|\sum_{s\in
S_{p}}e\left(-\frac{Ks\cdot(m^{-1})_{p}}{p}\right)\left(e\left(\frac{Ks}{pm}\right)-1\right)\right|+\left|\sum_{s\in
S_{p}}e\left(-\frac{Ks\cdot(m^{-1})_{p}}{p}\right)\right|$
$\displaystyle\leqslant\left|\sum_{s\in
S_{p}}e\left(-\frac{Ks\cdot(m^{-1})_{p}}{p}\right)\left(e\left(\frac{Ks}{pm}\right)-1\right)\right|+\operatorname{disc}_{p}(S_{p})\cdot|S_{p}|$
$\displaystyle\leqslant\sum_{s\in
S_{p}}\left|e\left(\frac{Ks}{pm}\right)-1\right|+\operatorname{disc}_{p}(S_{p})\cdot|S_{p}|$
$\displaystyle=\sum_{s\in
S_{p}}\left|e\left(\frac{|K|s}{pm}\right)-1\right|+\operatorname{disc}_{p}(S_{p})\cdot|S_{p}|$
$\displaystyle\leqslant|S_{p}|\cdot\frac{2\pi|K|}{m}+\operatorname{disc}_{p}(S_{p})\cdot|S_{p}|,$

where the second step uses Fact 2.16 and the relative primality of $p$ and
$m$; the third step applies the triangle inequality; the fourth step follows
from $p\nmid|K|$, and the last step is valid by (A.2) and $s<p$. We have shown
that

$\displaystyle\left|\sum_{s\in
S_{p}}e\left(\frac{ks\cdot(p^{-1})_{m}}{m}\right)\right|$
$\displaystyle\leqslant\frac{2\pi\min(k,m-k)}{m}\cdot|S_{p}|+\operatorname{disc}_{p}(S_{p})\cdot|S_{p}|$

for $p\in\mathcal{P}^{\prime}.$ Summing over $\mathcal{P}^{\prime},$

$\displaystyle R\sum_{p\in\mathcal{P}^{\prime}}$
$\displaystyle\left|\sum_{s\in
S_{p}}e\left(\frac{ks\cdot(p^{-1})_{m}}{m}\right)\right|$
$\displaystyle\qquad\leqslant
R\sum_{p\in\mathcal{P}^{\prime}}\left(\frac{2\pi\min(k,m-k)}{m}\cdot|S_{p}|+\operatorname{disc}_{p}(S_{p})\cdot|S_{p}|\right)$
$\displaystyle\qquad\leqslant
R\sum_{p\in\mathcal{P}}\left(\frac{2\pi\min(k,m-k)}{m}\cdot|S_{p}|+\operatorname{disc}_{p}(S_{p})\cdot|S_{p}|\right)$
$\displaystyle\qquad\leqslant\left(\frac{2\pi\min(k,m-k)}{m}+\max_{p\in\mathcal{P}}\\{\operatorname{disc}_{p}(S_{p})\\}\right)R\sum_{p\in\mathcal{P}}|S_{p}|$
$\displaystyle\qquad=\left(\frac{2\pi\min(k,m-k)}{m}+\max_{p\in\mathcal{P}}\\{\operatorname{disc}_{p}(S_{p})\\}\right)|S|.$
(A.13)

By (A.11)–(A.13), the proof of the claim is complete. ∎

###  A.4. Correlation for $k$ large

We now present an alternative bound on the exponential sum (A.9), which is
preferable to the bound of Claim A.1 when $k$ is far from zero modulo $m.$
This part of the proof is reproduced verbatim from [48, Section 6.4].

######  Claim A.2.

Let $k\in\\{1,2,\ldots,m-1\\}$ be given. Then

$\left|\sum_{s\in S}e\left(\frac{k}{m}\cdot
s\right)\right|\leqslant\frac{m}{2R\min(k,m-k)}\cdot|S|.$

###### Proof:.

$\displaystyle\left|\sum_{s\in S}e\left(\frac{k}{m}\cdot s\right)\right|$
$\displaystyle=\left|\sum_{p\in\mathcal{P}}\sum_{s\in
S_{p}}\sum_{r=1}^{R}e\left(\frac{k}{m}\cdot(r+s\cdot(p^{-1})_{m})\right)\right|$
$\displaystyle\leqslant\sum_{p\in\mathcal{P}}\sum_{s\in
S_{p}}\left|\sum_{r=1}^{R}e\left(\frac{k}{m}\cdot(r+s\cdot(p^{-1})_{m})\right)\right|$
$\displaystyle=\sum_{p\in\mathcal{P}}\sum_{s\in
S_{p}}\left|\sum_{r=1}^{R}e\left(\frac{kr}{m}\right)\right|$
$\displaystyle=\sum_{p\in\mathcal{P}}\sum_{s\in
S_{p}}\frac{|1-e(kR/m)|}{|1-e(k/m)|}$
$\displaystyle\leqslant\sum_{p\in\mathcal{P}}\sum_{s\in
S_{p}}\frac{2}{|1-e(k/m)|}$
$\displaystyle\leqslant\sum_{p\in\mathcal{P}}\sum_{s\in
S_{p}}\frac{m}{2\min(k,m-k)}$ $\displaystyle=\frac{m}{2R\min(k,m-k)}\cdot|S|,$

where the last two steps use (A.3) and $|S|=R\sum_{p\in\mathcal{P}}|S_{p}|$,
respectively. ∎

###  A.5. Finishing the proof

The remainder of the proof is reproduced without changes from [48, Section
6.5], except for the use of the updated bound in Claim A.1 for arbitrary
$\Delta\geqslant 1.$

Specifically, Facts 2.17 and 2.18 imply that

$\displaystyle\pi(P)-\pi\left(\frac{P}{2}\right)$
$\displaystyle\geqslant\frac{P}{C\log P}\qquad\qquad(P\geqslant C),$ (A.14)
$\displaystyle\max_{k=1,2,\ldots,m}\nu(k)$ $\displaystyle\leqslant\frac{C\log
m}{\log\log m},$ (A.15)

where $C\geqslant 1$ is a constant independent of $R,P,m,\Delta.$ Moreover,
$C$ can be easily calculated from the explicit bounds in Facts 2.17 and 2.18.
We will show that the theorem conclusion (A.1) holds with $c=4C^{2}.$ We may
assume that

$\displaystyle P\geqslant C,$ (A.16) $\displaystyle\frac{C\log m}{\log\log
m}\leqslant\frac{P}{2C\log P},$ (A.17)

since otherwise the right-hand side of (A.1) exceeds $1$ and the theorem is
trivially true. By (A.4) and (A.14)–(A.17), we obtain

$|\mathcal{P}|\geqslant\frac{P}{2C\log P},$

which along with (A.15) gives

$\displaystyle\max_{k=1,2,\ldots,m-1}\frac{\nu(k)+\nu(m-k)}{|\mathcal{P}|}$
$\displaystyle\leqslant\frac{2C\log m}{\log\log m}\cdot\frac{2C\log P}{P}$
$\displaystyle=\frac{c\log m}{\log\log m}\cdot\frac{\log P}{P}.$ (A.18)

Claims A.1 and A.2 ensure that for every $k=1,2,\ldots,m-1,$

$\displaystyle\left|\sum_{s\in S}e\left(\frac{k}{m}\cdot s\right)\right|$
$\displaystyle\leqslant\left(\min\left(\frac{2\pi\min(k,m-k)}{m},\frac{m}{2R\min(k,m-k)}\right)\right.$
$\displaystyle\qquad\qquad\left.+\max_{p\in\mathcal{P}}\\{\operatorname{disc}_{p}(S_{p})\\}+\frac{\nu(k)+\nu(m-k)}{|\mathcal{P}|}\cdot\Delta\right)|S|$
$\displaystyle\leqslant\left(\sqrt{\frac{\pi}{R}}+\max_{p\in\mathcal{P}}\\{\operatorname{disc}_{p}(S_{p})\\}+\frac{\nu(k)+\nu(m-k)}{|\mathcal{P}|}\cdot\Delta\right)|S|$
$\displaystyle\leqslant\left(\frac{c}{\sqrt{R}}+\max_{p\in\mathcal{P}}\\{\operatorname{disc}_{p}(S_{p})\\}+\frac{\nu(k)+\nu(m-k)}{|\mathcal{P}|}\cdot\Delta\right)|S|;$

here we are using the updated bound from Claim A.1 in this paper for general
$\Delta$. Substituting the estimate from (A.18), we conclude that

$\max_{k=1,2,\ldots,m-1}\left|\sum_{s\in S}e\left(\frac{k}{m}\cdot
s\right)\right|\\\
\leqslant\left(\frac{c}{\sqrt{R}}+\max_{p\in\mathcal{P}}\\{\operatorname{disc}_{p}(S_{p})\\}+\frac{c\log
m}{\log\log m}\cdot\frac{\log P}{P}\cdot\Delta\right)|S|.\qquad\qquad$

This conclusion is equivalent to (A.1). The proof of Theorem 3.5 is complete.