t}}\mathcal{B}_{b}\cup\mathcal{B}_{x}$ generate all monomials,

$r(\mathsf{mAD}_{t,t^{\prime},p})=t\log t^{\prime}+\log t.$

  * •

Sparsity: By Equation (6.2.4), all monomials appearing in $T_{\mathbf{1}}$,
except for those purely in $x$-variables, contain at least one variable from
$y_{\mathbf{1}}$. Moreover, from Equation (48), no monomial appearing in
$T_{b}$ for $b\neq\mathbf{1}$ contains a variable from $y_{\mathbf{1}}$. Since
all Fourier coefficients of $\mathbb{I}_{\mathbf{1}}$ are non-zero by
Observation 4.18, Equation (6.2.4) yields that these monomials contribute

$t\left(\frac{t^{\prime}}{2}-1+\frac{t^{\prime}}{2}+(2^{p}-1)\frac{t^{\prime}}{2}\right)=t\left(\frac{t^{\prime}}{2}-1+2^{p-1}t^{\prime}\right)=\Theta(2^{p}tt^{\prime}).$
(49)

to the sparsity of $\mathsf{mAD}_{t,t^{\prime},p}$.

By Equation (48), all monomials all monomials appearing in $T_{b}$, for any
$b\neq\mathbf{1}$, except for those purely in $x$-variables, contain at least
one variable from $y_{b}$. Moreover, from Equations (6.2.4) and (48), no
monomial appearing in $T_{b}^{\prime}$ for $b^{\prime}\neq b$ contains a
variable from $y_{b}$. Since all Fourier coefficients of $\mathbb{I}_{b}$ are
non-zero by Observation 4.18, Equation (48) yields that these monomials
contribute at least (including contributions from each $T_{b}$ for
$b\neq\mathbf{1}$)

$(t-1)\cdot t\cdot(t^{\prime}-1)=\Omega(t^{2}t^{\prime})$ (50)

to the sparsity of $\mathsf{mAD}_{t,t^{\prime},p}$. By Equations (49) and
(50),

$k(\mathsf{mAD}_{t,t^{\prime},p})=\Omega(2^{p}tt^{\prime}+t^{2}t^{\prime}).$

By Equation (46),

$\displaystyle k(\mathsf{mAD}_{t,t^{\prime},p})$ $\displaystyle\leq
k(\mathbb{I}_{\mathbf{1}})k(\mathsf{mAND}_{t^{\prime},p})+\sum_{\mathbf{1}\neq
b\in\left\\{-1,1\right\\}^{\log t}}k(\mathbb{I}_{b})k(\mathsf{AND}_{\log
t^{\prime}})$ $\displaystyle\leq t\cdot
k(\mathsf{mAND}_{t^{\prime},p})+(t-1)t\cdot t^{\prime}$ by Observations 4.18
and 4.30 $\displaystyle=O(2^{p}tt^{\prime}+t^{2}t^{\prime}).$ since
$\mathsf{mAND}_{t^{\prime},p}$ is a function on $(\log t^{\prime}+p)$
variables

Thus,

$k(\mathsf{mAD}_{t,t^{\prime},p})=\Theta(2^{p}tt^{\prime}+t^{2}t^{\prime}).$

  * •

Max-rank-entropy: Recall from the argument for rank that
$\mathcal{B}=\bigcup_{b\in\left\\{-1,1\right\\}^{\log
t}}\mathcal{B}_{b}\cup\mathcal{B}_{x}\subseteq\mathrm{supp}(\mathsf{mAD}_{t,t^{\prime},p})$
generate all the monomials of $\mathsf{mAD}_{t,t^{\prime},p}$. Moreover the
absolute values of the coefficients of these monomials take values in the set
$\left\\{\frac{2}{tt^{\prime}},\left(1-\frac{2}{2^{p}}\right)\frac{2}{tt^{\prime}}\right\\}$.
Since $p\geq 2$, $1\geq 1-\frac{2}{2^{p}}\geq\frac{1}{2}$. Therefore

$k^{\prime\prime}(\mathsf{mAD}_{tt^{\prime}p})=O(tt^{\prime}).$ (51)

Recall that no monomial arising from the terms $T_{b}$ for $\mathbf{1}\neq
b\in\left\\{-1,1\right\\}^{\log t}$ (see Equation (48)) contain variables from
$y_{\mathbf{1}}$. Thus, monomials which contain the variable
$y_{\mathbf{1},1}$ only appear in Equation (6.2.4). Moreover, by Observation
4.18 we conclude that the absolute value of coefficient of any such monomial
takes values in the set
$\left\\{\frac{2}{tt^{\prime}}\left(1-\frac{2}{2^{p}}\right),\frac{4}{2^{p}tt^{\prime}}\right\\}$.

Recall from Definition 4.26 that
$k^{\prime\prime}(f)=\operatorname*{\arg\\!\min}_{\theta}\\{\dim(\mathcal{S}_{\theta})=r(f)\\}$,
where
$\mathcal{S}_{\theta}=\left\\{S:|\widehat{f}(S)|\geq\frac{1}{\theta}\right\\}$.
Therefore if $\theta<\frac{2}{tt^{\prime}}$, then $\mathcal{S}_{\theta}$ does
not include any monomial containing $y_{\mathbf{1},1}$. Therefore

$k^{\prime\prime}(\mathsf{mAD}_{t,t^{\prime},p})\geq\left(1-\frac{2}{2^{p}}\right)^{-1}\frac{tt^{\prime}}{2}\geq\frac{tt^{\prime}}{2}.$

Hence by Equation (51),

$k^{\prime\prime}(\mathsf{mAD}_{t,t^{\prime},p})=\Theta(tt^{\prime}).$

  * •

Weight: By Equation (46),

$\displaystyle\widehat{\mathsf{mAD}_{t,t^{\prime},p}}(\emptyset)$
$\displaystyle=\widehat{\mathbb{I}_{\mathbf{1}}}(\emptyset)\widehat{\mathsf{mAND}_{t^{\prime},p}}(\emptyset)+\sum_{\mathbf{1}\neq
b\in\left\\{-1,1\right\\}^{\log
t}}\widehat{\mathbb{I}_{b}}(\emptyset)\widehat{\mathsf{mAND}_{\log
t^{\prime}}}(\emptyset)$ by Observation 4.18 and Claim 6.14
$\displaystyle=\frac{1}{t}\left(1-\frac{2}{t^{\prime}}\right)+(t-1)\frac{1}{t}\left(1-\frac{2}{t^{\prime}}\right).$
$\displaystyle=1-\frac{2}{t^{\prime}}$

Thus by Observation 4.2,

$\delta(\mathsf{mAD}_{t,t^{\prime},p})=\frac{1-\widehat{\mathsf{mAD}_{t,t^{\prime},p}(\emptyset)}}{2}=\frac{1}{t^{\prime}}.$

∎

###  6.3 Setting parameters in our constructed functions

In this section we prove Theorems 1.5 and 1.7. Recall that these theorems
require us to exhibit functions which achieve certain bounds. Claims 6.15 and
6.16 correspond to the bounds in Theorem 1.5, and describe the required
functions. Claims 6.17 and 6.18 correspond to the bounds in Theorem 1.7, and
describe the required functions.

######  Claim 6.15.

For all $\rho,\kappa,\kappa^{\prime}\in\mathbb{N}$ such that $\kappa$ is
sufficiently large, for all $\epsilon>0$ such that
$\log\kappa\leq\rho\leq\kappa^{\frac{1}{2}-\epsilon}$ and
$\frac{\kappa\log\kappa}{\rho}\leq\kappa^{\prime}\leq\kappa$, for
$t=\frac{2\rho}{\log\kappa}$,
$t^{\prime}=\frac{\kappa\log^{2}\kappa}{\rho^{2}}$ and
$a=\frac{2\kappa^{\prime}\log\kappa}{\rho}$,

  * •

$\Omega(\epsilon\rho)=r(\mathsf{AD}_{t,t^{\prime},a})=O(\rho)$.

  * •

$k(\mathsf{AD}_{t,t^{\prime},a})=\Theta(\kappa)$.

  * •

$k^{\prime}(\mathsf{AD}_{t,t^{\prime},a})=\Theta(\kappa^{\prime})$.

  * •

$\delta(\mathsf{AD}_{t,t^{\prime},a})=\Theta\left(\frac{1}{\kappa}\left(\frac{\rho}{\log\kappa}\right)^{2}\right)$.

We prove Claim 6.15 in Section 6.3.1.

######  Claim 6.16.

For all $\rho,\kappa,\kappa^{\prime}\in\mathbb{N}$ such that $\kappa$ is
sufficiently large, for all constants $\epsilon>0$, such that
$\kappa^{1/2}\leq\kappa^{\prime}\leq(\kappa\log\kappa)/\rho$ and
$\log\kappa\leq\rho\leq\kappa^{\frac{1}{2}-\epsilon}$ for
$t=\frac{2\rho}{\log\kappa}$, $t^{\prime}=\frac{4\kappa^{\prime 2}}{\kappa}$
and $\ell=2\left(\frac{\kappa\log\kappa}{\kappa^{\prime}\rho}\right)^{2}$,

  * •

$\Omega(\epsilon\rho)=r(\mathsf{AAB}_{t,t^{\prime},\ell})=O(\rho)$.

  * •

$k(\mathsf{AAB}_{t,t^{\prime},\ell})=\Theta(\kappa)$.

  * •

$k^{\prime}(\mathsf{AAB}_{t,t^{\prime},\ell})=\Theta(\kappa^{\prime})$.

  * •

$\delta(f)=O\left(\frac{\kappa}{\kappa^{\prime 2}}\right)$.

We prove Claim 6.16 in Section 6.3.2.

######  Claim 6.17.

For all $\rho,\kappa,\kappa^{\prime\prime}\in\mathbb{N}$ such that $\kappa$ is
sufficiently large, for all constants $\epsilon>0$ such that
$\log\kappa\leq\rho\leq\kappa^{1/2-\epsilon}$,
$e\rho\leq\kappa^{\prime\prime}\leq\frac{\kappa\log\kappa}{\rho}$, for
$t=\frac{2\rho}{\log(\kappa^{\prime\prime}/\rho)},t^{\prime}=\frac{\kappa^{\prime\prime}}{\rho}\log\left(\kappa^{\prime\prime}/\rho\right)$,
$p=\log\left(\frac{4\kappa}{\kappa^{\prime\prime}}\right)$,

  * •

$r(\mathsf{mAD}_{t,t^{\prime},p})=\Theta(\rho)$.

  * •

$\Omega(\kappa)=k(\mathsf{mAD}_{t,t^{\prime},p})=O(\kappa/\epsilon)$.

  * •

$k^{\prime\prime}(\mathsf{mAD}_{t,t^{\prime},p})=\Theta(\kappa^{\prime\prime})$.

  * •

$\delta(\mathsf{mAD}_{t,t^{\prime},p})=\frac{\rho}{\kappa^{\prime\prime}\log(\kappa^{\prime\prime}/\rho)}$.

We prove Claim 6.17 in Section 6.3.3.

######  Claim 6.18.

For all $\rho,\kappa,\kappa^{\prime}\in\mathbb{N}$ such that $\kappa$ is
sufficiently large, for all $\epsilon>0$ such that
$\log\kappa\leq\rho\leq\kappa^{\frac{1}{2}-\epsilon}$ and
$\frac{\kappa\log\kappa}{\rho}\leq\kappa^{\prime\prime}\leq\kappa$, there
exists a constant $c\geq 1$ such that the following holds for
$t=\frac{2\rho}{\log\kappa}$,
$t^{\prime}=\frac{c\kappa\log^{2}\kappa}{\rho^{2}}$ and
$a=\frac{2c\kappa^{\prime\prime}\log\kappa}{\rho}$.

  * •

$\Omega(\epsilon\rho)=r(\mathsf{AD}_{t,t^{\prime},a})=O(\rho)$.

  * •

$k(\mathsf{AD}_{t,t^{\prime},a})=\Theta(\kappa)$.

  * •

$k^{\prime\prime}(\mathsf{AD}_{t,t^{\prime},a})=\Theta(\kappa^{\prime\prime})$.

  * •

$\delta(\mathsf{AD}_{t,t^{\prime},a})=\Theta\left(\frac{1}{\kappa}\left(\frac{\rho}{\log\kappa}\right)^{2}\right)$.

###### Proof.

It follows by Claim 6.15 and the fact that
$k^{\prime}(\mathsf{AD}_{t,t^{\prime},a})=k^{\prime\prime}(\mathsf{AD}_{t,t^{\prime},a})$
(Claim 6.12). ∎

####  6.3.1 Proof of Claim 6.15

In this section we prove Claim 6.15, which gives us Fourier-analytic
properties of $\mathsf{AD}_{t,t^{\prime},a}$ for particular settings of
$t,t^{\prime},a$.

###### Proof of Claim 6.15.

Given any $\rho,\kappa,\kappa^{\prime}$ as in the assumptions of the claim,
recall that we fix the following values.

$\displaystyle t$ $\displaystyle=\frac{2\rho}{\log\kappa},$ (52)
$\displaystyle t^{\prime}$
$\displaystyle=\kappa\left(\frac{\log\kappa}{\rho}\right)^{2},$ (53)
$\displaystyle a$ $\displaystyle=\frac{2\kappa^{\prime}\log\kappa}{\rho}.$
(54)

Since $\rho\geq\log\kappa$,

$t=\frac{2\rho}{\log\kappa}\geq 2.$

Since $\rho<\sqrt{\kappa}$ by assumption,

$t^{\prime}=\kappa\left(\frac{\log\kappa}{\rho}\right)^{2}\geq\log^{2}\kappa\geq
2,$

for large enough $\kappa$. Since
$\kappa^{\prime}\geq\frac{\kappa\log\kappa}{\rho}$,

$a=\frac{2\kappa^{\prime}\log\kappa}{\rho}\geq
2\kappa\left(\frac{\log\kappa}{\rho}\right)^{2}=2t^{\prime}.$ (55)

Hence the assumptions in Claim 6.12 are satisfied with these values of
$t,t^{\prime},a$. By Equations (52), (53) and (54), we obtain the following
bound which is of use to us later.

$\frac{at}{t^{\prime}}=\frac{2\kappa^{\prime}\log\kappa}{\rho}\cdot\frac{2\rho}{\log\kappa}\cdot\frac{\rho^{2}}{\kappa\log^{2}\kappa}=\frac{4\kappa^{\prime}}{\kappa}\left(\frac{\rho}{\log\kappa}\right)^{2}\leq\left(\frac{2\rho}{\log\kappa}\right)^{2}\leq
t^{2}.$ (56)

We have the following properties of $\mathsf{AD}_{t,t^{\prime},a}$.

  * •

Rank:

$\displaystyle r(\mathsf{AD}_{t,t^{\prime},a})$
$\displaystyle=(t-1)\log{t^{\prime}}+\log a+\log t$ by Claim 6.12
$\displaystyle=t\log t^{\prime}+\log\left(\frac{at}{t^{\prime}}\right)\leq
3t\log t^{\prime}$ by Equation (56)
$\displaystyle=\frac{6\rho}{\log\kappa}\left(\log(\kappa/\rho^{2})+2\log\log\kappa\right)$
by Equations (52) and (53)
$\displaystyle\leq\frac{6\rho}{\log\kappa}\left(\log\kappa+2\log\kappa\right)$
$\displaystyle=O(\rho).$

For our setting of parameters (Equations (52), (53) and (54)),
$at=4\kappa^{\prime}$. Since $\rho\geq\log\kappa$ and
$\kappa^{\prime}\geq\frac{\kappa\log\kappa}{\rho}$,

$\frac{at}{t^{\prime}}=\frac{4\kappa^{\prime}}{\kappa}\left(\frac{\rho}{\log{\kappa}}\right)^{2}\geq\frac{4\rho}{\log\kappa}>1.$
(57)

Thus,

$\displaystyle r(\mathsf{AD}_{t,t^{\prime},a})$
$\displaystyle=(t-1)\log{t^{\prime}}+\log a+\log t$ by Claim 6.12
$\displaystyle=t\log t^{\prime}+\log{\left(\frac{at}{t^{\prime}}\right)}\geq
t\log t^{\prime}$ by Equation (57)
$\displaystyle=\frac{2\rho}{\log\kappa}\left(\log(\kappa/\rho^{2})+2\log\log\kappa\right)$
by Equations (52) and (53)
$\displaystyle\geq\frac{2\rho}{\log\kappa}\left(\log(\kappa/\rho^{2})\right)\geq\frac{2\rho}{\log\kappa}\left(\log\kappa^{2\epsilon}\right)$
since $\rho\leq\kappa^{\frac{1}{2}-\epsilon}$
$\displaystyle=\frac{2\rho}{\log\kappa}(2\epsilon\log\kappa)$
$\displaystyle=\Omega(\epsilon\rho).$

  * •

Sparsity: By our choice of parameters (Equations (52), (53) and (54)), we have

$ta=4\kappa^{\prime}\leq 4\kappa=t^{2}t^{\prime}.$ (58)

Thus,

$\displaystyle k(f_{\rho,\kappa,\kappa^{\prime}})$
$\displaystyle=(t-1)(t^{\prime}-1)t+ta$ by Claim 6.12
$\displaystyle=\Theta(t^{2}t^{\prime})$ by Equation (58) and since
$t,t^{\prime}\geq 2$
$\displaystyle=\Theta\left(\left(\frac{2\rho}{\log\kappa}\right)^{2}\kappa\left(\frac{\log\kappa}{\rho}\right)^{2}\right)$
by Equations (52) and (53) $\displaystyle=\Theta(\kappa).$

  * •

Max-supp-entropy: Since $ta=4\kappa^{\prime}$ from Equation (58), we have by
Claim 6.12 that

$\displaystyle k^{\prime}(f_{\rho,\kappa,\kappa^{\prime}})$
$\displaystyle=\frac{ta}{2}=\Theta(\kappa^{\prime}).$

  * •

Weight:

$\displaystyle\delta(f_{\rho,\kappa,\kappa^{\prime}})$
$\displaystyle=\frac{1}{t^{\prime}}+\frac{1}{at}-\frac{1}{tt^{\prime}}$ by
Claim 6.12
$\displaystyle=\frac{1}{t^{\prime}}+\frac{1}{t}\left(\frac{1}{a}-\frac{1}{t^{\prime}}\right)$
$\displaystyle\in\left[\frac{1}{t^{\prime}}-\frac{1}{tt^{\prime}},\frac{1}{t^{\prime}}-\frac{1}{2tt^{\prime}}\right]$
since $2t^{\prime}\leq a$ by Equation (55)
$\displaystyle=\Theta\left(\frac{1}{t^{\prime}}\right)$ since $t\geq 2$
$\displaystyle=\Theta\left(\frac{1}{\kappa}\left(\frac{\rho}{\log\kappa}\right)^{2}\right).$
by Equation (53)

∎

####  6.3.2 Proof of Claim 6.16

In this section we prove Claim 6.16, which gives us Fourier-analytic
properties of $\mathsf{AAB}_{t,t^{\prime},\ell}$ for particular settings of
$t,t^{\prime},\ell$.

###### Proof of Claim 6.16.

Given any $\rho,\kappa,\kappa^{\prime}$ as in the assumptions of the claim,
recall that we fix the following values.

$\displaystyle t$ $\displaystyle=\frac{2\rho}{\log\kappa},$ (59)
$\displaystyle t^{\prime}$ $\displaystyle=\frac{4\kappa^{\prime 2}}{\kappa},$
(60) $\displaystyle\ell$
$\displaystyle=2\left(\frac{\kappa\log\kappa}{\kappa^{\prime}\rho}\right)^{2}.$
(61)

Since $\rho\geq\log\kappa$, we have $t=\frac{2\rho}{\log\kappa}\geq 2$. Since
$\kappa^{\prime}\geq\sqrt{\kappa}$, we have $t^{\prime}=\frac{4\kappa^{\prime
2}}{\kappa}\geq 4$. Finally since
$\kappa^{\prime}\leq(\kappa\log\kappa)/\rho$,
$\ell=2\left(\frac{\kappa\log\kappa}{\kappa^{\prime}\rho}\right)^{2}\geq 2$.
Hence the assumptions in Claim 6.11 are satisfied with these values of
$t,t^{\prime}$ and $\ell$.

By Equations (60) and (61), we obtain the following bound which is of use to
us later.

$\ell
t^{\prime}=2\left(\frac{\kappa\log\kappa}{\kappa^{\prime}\rho}\right)^{2}\cdot\frac{4\kappa^{\prime
2}}{\kappa}=8\kappa\left(\frac{\log\kappa}{\rho}\right)^{2}.$ (62)

We have the following properties of $\mathsf{AAB}_{t,t^{\prime},\ell}$.

  * •

Rank:

$\displaystyle r(\mathsf{AAB}_{t,t^{\prime},\ell})$ $\displaystyle=t(\log
t^{\prime}+\log\ell)+\log t$ by Claim 6.11 $\displaystyle=t\log(\ell
t^{\prime})+\log t\leq 2t\log(\ell t^{\prime})$ since $\ell\geq 2$ and
$t^{\prime}\geq 4$ $\displaystyle=\frac{4\rho}{\log\kappa}\left(\log
8+\log\left(\kappa/\rho^{2}\right)+2\log\log\kappa\right)$ by Equation (62)
$\displaystyle\leq\frac{4\rho}{\log\kappa}\left(\log\kappa+\log\kappa+2\log\kappa\right)$
since $\kappa$ is sufficiently large $\displaystyle=O(\rho).$

For the lower bound, we have

$\displaystyle r(\mathsf{AAB}_{t,t^{\prime},\ell})$ $\displaystyle=t(\log
t^{\prime}+\log\ell)+\log t$ by Claim 6.11 $\displaystyle\geq t\log(\ell
t^{\prime})$ since $t\geq 1$
$\displaystyle=\frac{2\rho}{\log\kappa}\cdot\left(\log
8+\log\left(\kappa/\rho^{2}\right)+2\log\log\kappa\right)$ by Equations (59)
and (62)
$\displaystyle\geq\frac{2\rho}{\log\kappa}\cdot\left(\log\left(\kappa/\rho^{2}\right)\right)\geq\frac{2\rho}{\log\kappa}\cdot\left(\log\kappa^{2\epsilon}\right)$
since $\rho\leq\kappa^{\frac{1}{2}-\epsilon}$
$\displaystyle=\frac{2\rho}{\log\kappa}\left(2\epsilon\log\kappa\right)$
$\displaystyle=\Omega(\epsilon\rho).$

  * •

Sparsity:

$\displaystyle k(\mathsf{AAB}_{t,t^{\prime},\ell})$
$\displaystyle=1+\frac{1}{2}t^{2}(\ell+1)t^{\prime}$ by Claim 6.11
$\displaystyle=\Theta(t^{2}\ell t^{\prime})$
$\displaystyle=\Theta\left(\left(\frac{2\rho}{\log\kappa}\right)^{2}\cdot
8\kappa\left(\frac{\log\kappa}{\rho}\right)^{2}\right)$ by Equations (59) and
(62) $\displaystyle=\Theta(\kappa).$

  * •

Max-supp-entropy:

$\displaystyle k^{\prime}(\mathsf{AAB}_{t,t^{\prime},\ell})$
$\displaystyle=\frac{tt^{\prime}\sqrt{\ell}}{2}$ by Claim 6.11
$\displaystyle=\frac{1}{2}\cdot\frac{2\rho}{\log\kappa}\cdot\frac{(2\kappa^{\prime})^{2}}{\kappa}\cdot\frac{\sqrt{2}\kappa\log\kappa}{\kappa^{\prime}\rho}$
by Equations (59), (60) and (61) $\displaystyle=\Theta(\kappa^{\prime}).$

  * •

Weight:

$\displaystyle\delta(\mathsf{AAB}_{t,t^{\prime},\ell})$
$\displaystyle=\frac{1}{t^{\prime}}$ by Claim 6.11
$\displaystyle=\Theta\left(\frac{\kappa}{\kappa^{\prime 2}}\right).$ by
Equation (60)

∎

####  6.3.3 Proof of Claim 6.17

In this section we prove Claim 6.17, which gives us Fourier-analytic
properties of $\mathsf{mAD}_{t,t^{\prime},p}$ for particular settings of
$t,t^{\prime},p$.

###### Proof of Claim 6.17.

Given $\rho,\kappa$ and $\kappa^{\prime\prime}$ choose:

$\displaystyle p$
$\displaystyle=\log\left(\frac{4\kappa}{\kappa^{\prime\prime}}\right)$ (63)
$\displaystyle t^{\prime}$
$\displaystyle=\frac{\kappa^{\prime\prime}}{\rho}\log\left(\frac{\kappa^{\prime\prime}}{\rho}\right)$
(64) $\displaystyle t$
$\displaystyle=\frac{2\rho}{\log(\kappa^{\prime\prime}/\rho)}$ (65)

Since $\rho\geq\log\kappa\geq\log(\kappa^{\prime\prime}/\rho)$, we have
$t=\frac{2\rho}{\log(\kappa^{\prime\prime}/\rho)}\geq 2$. Since
$\kappa^{\prime\prime}\geq 2\rho$, we have
$t^{\prime}=\frac{\kappa^{\prime\prime}}{\rho}\log\left(\frac{\kappa^{\prime\prime}}{\rho}\right)\geq\frac{\kappa^{\prime\prime}}{\rho}\geq
2$. Note that $p\geq 2$ since
$\log\left(\frac{4\kappa}{\kappa^{\prime\prime}}\right)\geq\log 4=2$.

Finally we show that $p\leq(t/2)\log t^{\prime}\leq(t-1)\log t^{\prime}$:

$\displaystyle(t-1)\log t^{\prime}$ $\displaystyle\geq(t/2)\log t^{\prime}$
$\displaystyle=\frac{\rho}{\log(\kappa^{\prime\prime}/\rho)}\log\left(\frac{\kappa^{\prime\prime}}{\rho}\log\left(\frac{\kappa^{\prime\prime}}{\rho}\right)\right)$
$\displaystyle=\rho+\rho\cdot\frac{\log\log(\kappa^{\prime\prime}/\rho)}{\log(\kappa^{\prime\prime}/\rho)}$
$\displaystyle\geq\rho$ since $\kappa^{\prime\prime}\geq 2\rho$
$\displaystyle\geq\log{\kappa}\geq\log\left(4\kappa/\kappa^{\prime\prime}\right)$
since $\kappa^{\prime\prime}\geq e\log\kappa\geq 4$ as $\kappa$ is
sufficiently large $\displaystyle=p.$

Hence the assumptions in Claim 6.13 are satisfied with these values of
$t,t^{\prime}$ and $p$.

We first state and prove some auxiliary claims which we require. The
derivative of $\frac{\log(\kappa^{\prime\prime}/\rho)}{\kappa^{\prime\prime}}$
with respect to $\kappa^{\prime\prime}$ equals

$\displaystyle\frac{1-\ln{(\kappa^{\prime\prime}/\rho)}}{\ln
2\cdot(\kappa^{\prime\prime})^{2}}.$

This value is negative since $\kappa^{\prime\prime}>e\cdot\rho$. Thus,
$\frac{\log(\kappa^{\prime\prime}/\rho)}{\kappa^{\prime\prime}}$ is a
decreasing function in $\kappa^{\prime\prime}$ for
$\kappa^{\prime\prime}>e\cdot\rho$. Consider the expression

$\displaystyle\frac{2^{p}}{t}$
$\displaystyle=\frac{4\kappa}{\kappa^{\prime\prime}}\frac{\log(\kappa^{\prime\prime}/\rho)}{2\rho}$
$\displaystyle\geq\frac{2\kappa\cdot\log{\left(\frac{\kappa\log\kappa}{\rho^{2}}\right)}}{\kappa\log\kappa}$
Since $\frac{\log(\kappa^{\prime\prime}/\rho)}{\kappa^{\prime\prime}}$ is a
monotone decreasing function in $\kappa^{\prime\prime}$ and
$\kappa^{\prime\prime}\leq\frac{\kappa\log\kappa}{\rho}$.
$\displaystyle=2\frac{\left(\log{\kappa/\rho^{2}}\right)+\log{\log\kappa}}{\log\kappa}$
$\displaystyle\geq 2\frac{\log\kappa^{2\epsilon}+\log\log\kappa}{\log\kappa}$
since $\rho\leq\kappa^{1/2-\epsilon}$ $\displaystyle\geq 4\epsilon.$

Therefore

$2^{p}\geq 4\epsilon t.$ (66)

Next, observe that

$tt^{\prime}=\frac{2\rho}{\log(\kappa^{\prime\prime}/\rho)}\left(\frac{\kappa^{\prime\prime}\log(\kappa^{\prime\prime}/\rho)}{\rho}\right)=2\kappa^{\prime\prime}.$
(67)

We have the following properties of $\mathsf{mAD}_{t,t^{\prime},p}$.

  * •

Rank:

$\displaystyle r(\mathsf{mAD}_{t,t^{\prime},p})$
$\displaystyle=\Theta\left(t\log t^{\prime}\right)$ by Claim 6.13
$\displaystyle=\Theta\left(\frac{\rho}{\log(\kappa^{\prime\prime}/\rho)}\left(\log\frac{\kappa^{\prime\prime}}{\rho}+\log\log\left(\frac{\kappa^{\prime\prime}}{\rho}\right)\right)\right)$
by Equations (65) and (64)
$\displaystyle=\Theta\left(\frac{\rho}{\log(\kappa^{\prime\prime}/\rho)}\left(\log\frac{\kappa^{\prime\prime}}{\rho}\right)\right)$
$\displaystyle=\Theta(\rho).$

  * •

Sparsity: For the upper bound, we have

$\displaystyle k(\mathsf{mAD}_{t,t^{\prime},p})$
$\displaystyle=O(2^{p}tt^{\prime}+t^{2}t^{\prime})$ by Claim 6.13
$\displaystyle=O\left(2^{p}tt^{\prime}+\frac{2^{p}tt^{\prime}}{4\epsilon}\right)$
by Equation (66) $\displaystyle=O\left(\frac{1}{\epsilon}\cdot
2^{p}tt^{\prime}\right)$ since $0<\epsilon<1/2$
$\displaystyle=O\left(\frac{1}{\epsilon}\cdot\frac{\kappa}{\kappa^{\prime\prime}}\cdot\kappa^{\prime\prime}\right)$
by Equations (67) and (63)
$\displaystyle=O\left(\frac{\kappa}{\epsilon}\right).$

For the lower bound, we have

$\displaystyle k(\mathsf{mAD}_{t,t^{\prime},p})$
$\displaystyle=\Omega(2^{p}tt^{\prime})$ by Claim 6.13
$\displaystyle=\Omega{\left(\frac{\kappa}{\kappa^{\prime\prime}}\cdot\kappa^{\prime\prime}\right)}$
by Equations (67) and (63) $\displaystyle=\Omega(\kappa).$

  * •

Max-rank-entropy:

$\displaystyle k^{\prime\prime}(\mathsf{mAD}_{t,t^{\prime},p})$
$\displaystyle=\Theta(tt^{\prime})$ by Claim 6.13
$\displaystyle=\Theta(\kappa^{\prime\prime}).$ by Equation (67)

  * •

Weight:

$\displaystyle\delta(\mathsf{mAD}_{t,t^{\prime},p})$
$\displaystyle=\frac{1}{t^{\prime}}$ by Claim 6.13
$\displaystyle=\frac{\rho}{\kappa^{\prime\prime}\log(\kappa^{\prime\prime}/\rho).}$
by Equation (64)

∎

##  7 Dominating Chang’s lemma for all thresholds

In this section, we show that there exists a function such that for any choice
of threshold, the lower bound on weight of that function that we obtain from
Theorems 1.4 and 1.6 are stronger than the lower bound obtained from Chang’s
lemma (Lemma 1.1).

######  Claim 7.1 (Beating Chang’s lemma for all thresholds for
$\mathsf{AD}_{t,t}$).

Consider any integer $t>4$ and define the function
$f=\mathsf{AD}_{t,t}:\left\\{-1,1\right\\}^{\log
t}\times\left\\{-1,1\right\\}^{t\log t}\to\left\\{-1,1\right\\}$ as in
Definition 6.1. Then,

  * •

$\delta(f)=\frac{1}{t}$.

  * •

For all real $x>0$ for which $\dim(\mathcal{S}_{x})>1$, we have

$\displaystyle\frac{\sqrt{\dim(\mathcal{S}_{x})}}{x\sqrt{\log(x^{2}/\dim(\mathcal{S}_{x}))}}=O\left(\frac{1}{t^{3/2}}\right).$

  * •

$\frac{1}{k(f)}\left(\frac{r(f)}{\log
k(f)}\right)^{2}=\Omega\left(\frac{1}{t}\right),\quad\frac{k(f)}{k^{\prime}(f)^{2}}=\Omega\left(\frac{1}{t}\right)\quad\text{and}\quad\frac{r(f)}{k^{\prime\prime}(f)\log
k(f)}=\Omega\left(\frac{1}{t}\right).$

In particular, Claim 7.1 shows that our bounds can be strictly stronger than
those given by Chang’s lemma, in the following sense.

  * •

All the lower bounds on $\delta(f)$ from Theorems 1.4 and 1.6 are tight, as
witnessed by $f=\mathsf{AD}_{t,t}$.

  * •

No matter what threshold $x$ is chosen in Lemma 1.1, the best possible lower
bound on $\delta(\mathsf{AD}_{t,t})$ that we get can get from Lemma 1.1 is
$\Omega\left(\frac{1}{t^{3/2}}\right)$, which is polynomially smaller than
$1/t$, the actual weight of $\mathsf{AD}_{t,t}$.

###### Proof of Claim 7.1.

From Claim 6.9, we have

$\displaystyle\delta(f)=\frac{1}{t}.$

Thus from Observation 4.2,

$\displaystyle\widehat{f}(\emptyset)=1-\frac{2}{t}.$ (68)

First, we show that except for the Fourier coefficient of the empty set, all
other Fourier coefficients of $f$ have magnitude equal to $\frac{2}{t^{2}}$.

Towards a contradiction assume that there exists $T\subseteq[\log t]\cup[t\log
t]$ such that ${\left|\widehat{f}(T)\right|}>\frac{2}{t^{2}}$. We have,

$\displaystyle 1$ $\displaystyle=\sum_{S\subseteq[\log t]\cup[t\log
t]}\widehat{f}^{2}(S)$
$\displaystyle=\left(1-\frac{2}{t}\right)^{2}+\sum_{S\subseteq[\log
t]\cup[t\log t],S\neq\emptyset}\widehat{f}^{2}(S)$
$\displaystyle=\left(1-\frac{2}{t}\right)^{2}+\widehat{f}^{2}(T)+\sum_{S\subseteq[\log
t]\cup[t\log t],S\neq\emptyset,S\neq T}\widehat{f}^{2}(S)$
$\displaystyle>\left(1-\frac{2}{t}\right)^{2}+\frac{4}{t^{4}}+\sum_{S\subseteq[\log
t]\cup[t\log t],S\neq\emptyset,S\neq T}\widehat{f}^{2}(S)$ (69)

From Claim 6.9, $k(f)=1+t^{2}(t-1)=t^{3}-t^{2}+1$ and $k^{\prime}(f)=t^{2}/2$.
Using these, along with the definition of $k^{\prime}(f)$ (Definition 4.26),
in Equation (69),

$\displaystyle 1$
$\displaystyle>\left(1-\frac{2}{t}\right)^{2}+\frac{4}{t^{4}}+\frac{4(k(f)-2)}{t^{4}}$
$\displaystyle=\left(1-\frac{2}{t}\right)^{2}+\frac{4}{t^{4}}+\frac{4(t^{3}-t^{2}+1-2)}{t^{4}}$
$\displaystyle=\left(1-\frac{2}{t}\right)^{2}+\frac{4}{t^{4}}+\frac{4(t^{3}-t^{2}-1)}{t^{4}}$
$\displaystyle=\left(1-\frac{2}{t}\right)^{2}+\frac{4}{t^{4}}+\left(\frac{4}{t}-\frac{4}{t^{2}}-\frac{4}{t^{4}}\right)$
$\displaystyle=\left(1+\frac{4}{t^{2}}-\frac{4}{t}\right)+\frac{4}{t^{4}}+\left(\frac{4}{t}-\frac{4}{t^{2}}-\frac{4}{t^{4}}\right)$
$\displaystyle=1.$

Thus,

${\left|\widehat{f}(S)\right|}=\frac{2}{t^{2}}\quad\text{for all non-
empty}~{}S\subseteq([\log t]\cup[t\log t]).$ (70)

We now prove the second part of the claim. If $x<\frac{t^{2}}{2}$ then
$\mathcal{S}_{x}=\left\\{\emptyset\right\\}$ and has dimension $0$. On the
other hand, for any $x\geq\frac{t^{2}}{2}$, we have
$\mathcal{S}_{x}=\mathrm{supp}(f)$ by Equation (70), and hence
$\dim(\mathcal{S}_{x})=r(f)=(t+1)(\log t)$ by Claim 6.9. Hence, in this case,

$\frac{\sqrt{\dim(\mathcal{S}_{x})}}{x\sqrt{\log(x^{2}/\dim(\mathcal{S}_{x}))}}=O\left(\frac{\sqrt{t\log
t}}{t^{2}\sqrt{\log t}}\right)=O\left(\frac{1}{t^{3/2}}\right),$

On the other hand, by Claim 6.9, $r(f)=\Theta(t\log t)$, $k(f)=\Theta(t^{3})$,
$k^{\prime}(f)=k^{\prime\prime}(f)=\Theta(t^{2})$. The third part of the claim
follows.

∎

##  8 Conclusions

In this paper, for Boolean functions $f$, we study the relationship between
weight and other Fourier-analytic measures namely rank, sparsity, max-supp-
entropy and max-rank-entropy. For a threshold $t>0$, Chang’s lemma gives a
lower bound on the weight of a Boolean function $f$ in terms of
$\dim\left(\left\\{S\subseteq[n]:|\widehat{f}(S)|\geq\frac{1}{t}\right\\}\right)$.
We consider three natural thresholds $t$ in Chang’s lemma, namely $k(f)$,
$k^{\prime}(f)$ and $k^{\prime\prime}(f)$, yielding three lower bounds on
weight in terms of these measures. We prove new lower bounds on weight in
Theorems 1.4 and 1.6, and our bounds dominate all the above-mentioned bounds
from Chang’s lemma for a wide range of parameters.

When $\log k(f)=\Theta(r(f))$, the function $f=\mathsf{AND}$ already shows
that all the above lower bounds are tight. To consider all other feasible
relationships between $k(f)$ and $r(f)$, we divide our investigation of these
lower bounds into two different parts. In the first part, we vary over all
feasible settings of $r(f)$, $k(f)$ and $k^{\prime}(f)$, and construct
functions that witness tightness of our lower bounds in Theorem 1.4 for nearly
all such feasible settings (Theorem 1.5). In the second part, we vary over all
feasible settings of $r(f)$, $k(f)$ and $k^{\prime\prime}(f)$, and construct
functions that witness near-tightness of our lower bounds in Theorem 1.6 for
nearly all such feasible settings (Theorem 1.7). These functions are
constructed by carefully composing the Addressing function with suitable inner
functions. We show a composition lemma (Lemma 6.8), which relates the
properties of the composed function with those of the inner functions; this
allows us to come up with functions that match our lower bounds.

We also construct functions for which our lower bounds are asymptotically
stronger than the lower bounds obtained from Chang’s lemma for all choices of
threshold (Claim 7.1). The functions that we construct in this work might be
of independent interest.

##### Open Problems.

Claim 6.15 shows tightness of our upper bound on rank in terms of sparsity and
weight (Theorem 1.3). Since our proof of Theorem 1.3 is a generalization of
the proof of the upper bound $r(f)=O(\sqrt{k(f)}\log k(f))$ due to Sanyal
[San19], it sheds light on the presence of the $\log k$ factor in Sanyal’s
upper bound. This still leaves the following question open: do there exist
Boolean functions $f$ for which $r(f)=\omega(\sqrt{k(f)})$?

There are some ranges of parameters where we were not able to construct
functions with upper bounds matching our lower bounds from Theorem 1.6. It
will be interesting to see if our techniques can be extended to cover these
ranges as well.

All thresholds $t$ considered for Chang’s lemma in this work satisfy
$\dim(\\{S\subseteq[n]:|\widehat{f}(S)|\geq\frac{1}{t}\\})=r(f)$. It is an
interesting problem to obtain Chang’s-lemma-type bounds for thresholds for
which this dimension is strictly less than $r(f)$.

Acknowledgements:  R.M. thanks DST (India) for grant
DST/INSPIRE/04/2014/001799. S.S. is supported by an ISIRD Grant from SRIC, IIT
Kharagpur. N.S.M. is supported by the NWO through QuantERA project QuantAlgo
680-91-034. T.M. would like to thank Prahladh Harsha and Ramprasad Saptharishi
for helpful discussions.

## References

  * [ACL+19] Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, and Ronald de Wolf.  Two new results about quantum exact learning.  In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, volume 132 of LIPIcs, pages 16:1–16:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [BC99] Anna Bernasconi and Bruno Codenotti.  Spectral analysis of Boolean functions as a graph eigenvalue problem.  IEEE Trans. Computers, 48(3):345–351, 1999.
  * [Blo16] Thomas F Bloom.  A quantitative improvement for Roth’s theorem on arithmetic progressions.  Journal of the London Mathematical Society, 93(3):643–663, 2016\.
  * [BRTW14] Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, and Julia Wolf.  Sampling-based proofs of almost-periodicity results and algorithmic applications.  In 41st International Colloquium on Automata, Languages, and Programming ICALP 2014, volume 8572 of Lecture Notes in Computer Science, pages 955–966. Springer, 2014.
  * [BS20] Thomas F Bloom and Olof Sisask.  Breaking the logarithmic barrier in Roth’s theorem on arithmetic progressions.  arXiv preprint arXiv:2007.03528, 2020.
  * [Cha02] Mei-Chu Chang.  A polynomial bound in Freiman’s theorem.  Duke mathematical journal, 113(3):399–419, 2002.
  * [CHLT19] Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, and Avishay Tal.  Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates.  In 10th Innovations in Theoretical Computer Science Conference, ITCS, pages 22:1–22:15, 2019.
  * [CLRS16] Siu On Chan, James R. Lee, Prasad Raghavendra, and David Steurer.  Approximate constraint satisfaction requires large LP relaxations.  J. ACM, 63(4):34:1–34:22, 2016.
  * [FKKK18] Ehud Friedgut, Jeff Kahn, Gil Kalai, and Nathan Keller.  Chvátal’s conjecture and correlation inequalities.  J. Comb. Theory, Ser. A, 156:22–43, 2018.
  * [GOS+11] Parikshit Gopalan, Ryan O’Donnell, Rocco A. Servedio, Amir Shpilka, and Karl Wimmer.  Testing Fourier dimensionality and sparsity.  SIAM J. Comput., 40(4):1075–1100, 2011.
  * [GR07] Ben Green and Imre Z. Ruzsa.  Freiman’s theorem in an arbitrary abelian group.  Journal of the London Mathematical Society, 75(1):163–175, 2007\.
  * [Gre02] Ben Green.  Arithmetic progressions in sumsets.  Geometric and Functional Analysis GAFA, 12(3):584–597, 2002.
  * [Gre03] Ben Green.  Some constructions in the inverse spectral theory of cyclic groups.  Combinatorics, Probability and Computing, 12(2):127–138, 2003.
  * [Gre04] Ben Green.  Spectral structure of sets of integers.  In Fourier analysis and convexity, pages 83–96. Springer, 2004\.
  * [GS08] Ben Green and Tom Sanders.  Boolean functions with small spectral norm.  Geometric and Functional Analysis GAFA, 18:144–162, 2008.
  * [GT13] Tom Gur and Omer Tamuz.  Testing Booleanity and the uncertainty principle.  Chic. J. Theor. Comput. Sci., 2013, 2013.
  * [HKP11] Pooya Hatami, Raghav Kulkarni, and Denis Pankratov.  Variations on the sensitivity conjecture.  Theory of Computing, 4:1–27, 2011.
  * [HLY19] Kaave Hosseini, Shachar Lovett, and Grigory Yaroslavtsev.  Optimality of linear sketching under modular updates.  In 34th Computational Complexity Conference, CCC 2019, volume 137 of LIPIcs, pages 13:1–13:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [IMR14] Russell Impagliazzo, Cristopher Moore, and Alexander Russell.  An entropic proof of Chang’s inequality.  SIAM J. Discret. Math., 28(1):173–176, 2014.
  * [Lov16] Shachar Lovett.  Communication is bounded by root of rank.  Journal of the ACM (JACM), 63(1):1–9, 2016.
  * [MO09] Ashley Montanaro and Tobias Osborne.  On the communication complexity of XOR functions.  CoRR, abs/0909.3392, 2009.
  * [San08] Tom Sanders.  Additive structures in sumsets.  Mathematical Proceedings of the Cambridge Philosophical Society, 144(2):289–316, 2008.
  * [San11] Tom Sanders.  On Roth’s theorem on progressions.  Annals of Mathematics, 174:619–636, 2011.
  * [San19] Swagato Sanyal.  Fourier sparsity and dimension.  Theory of Computing, 15(11):1–13, 2019.
  * [TWXZ13] Hing Yin Tsang, Chung Hoi Wong, Ning Xie, and Shengyu Zhang.  Fourier sparsity, spectral norm, and the log-rank conjecture.  In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 658–667, 2013.

##  Appendix A Equivalence of the two forms of Chang’s lemma

Recall that for any Boolean function
$f:\left\\{-1,1\right\\}^{n}\to\left\\{-1,1\right\\}$ and positive real number
$t$, we define
$\mathcal{S}_{t}:=\\{S\subseteq[n]:|\widehat{f}(S)|\geq\frac{1}{t}\\}$.
Chang’s lemma for the Boolean hypercube is usually stated in the literature as
an upper bound on the dimension of $\mathcal{S}_{t}$, as in Lemma A.1.

######  Lemma A.1 (Common form of Chang’s lemma).

Let $f:\left\\{-1,1\right\\}^{n}\to\left\\{-1,1\right\\}$ be a Boolean
function and $t$ be any positive real number. Let $d=\dim(\mathcal{S}_{t})>1$.
Then

$d=O(t^{2}\delta(f)^{2}\log(1/\delta(f))).$

In this section we show that Lemma A.1 and Lemma 1.1 can be easily derived
from each other. For convenience, we restate Lemma 1.1 below.

######  Lemma A.2 (Restatement of Lemma 1.1).

There exists a universal constant $c>0$ such that the following is true. Let
$f:\left\\{-1,1\right\\}^{n}\to\left\\{-1,1\right\\}$ be a Boolean function
and $t$ be any positive real number. Let $d=\dim(\mathcal{S}_{t})>1$. If
$\delta(f)<c$, then

$\delta(f)=\Omega\left(\frac{\sqrt{d}}{t\sqrt{\log\left(t^{2}/d\right)}}\right).$

We need the following claim.

######  Claim A.3.

Define a function $h:(0,1/e]\to\mathbb{R}$ by $h(\eta)=\eta\log(1/\eta)$. Then
$h$ is monotonically non-decreasing.

###### Proof.

Define $g(\eta):=\eta\ln(1/\eta)$, where $\ln$ denotes the natural logarithm
(i.e., logarithm with base $e$). Since, $h(\eta)=\log_{2}e\cdot g(\eta)$, it
is sufficient to show that $g$ is monotonically non-decreasing for
$\eta\in(0,1/e]$. Let $g^{\prime}(\cdot)$ denote the derivative of $g$ with
respect to $\eta$. We have that,

$g^{\prime}(\eta)=\ln(1/\eta)-1,$

which is non-negative for $\eta\in(0,1/e]$. The claim follows. ∎

###### Proof of equivalence of Lemma A.1 and Lemma A.2.

Lemma A.1 $\implies$ Lemma A.2.

Assume Lemma A.1 and let $f,t,\delta(f)$ and $d$ be as in the statement of
Lemma A.2. From Lemma A.1 we have that
$d=O(t^{2}\delta(f)^{2}\log(1/\delta(f)))$. Now,

$\displaystyle d=O(t^{2}\delta(f)^{2}\log\left(\frac{1}{\delta(f)}\right)$
(71) $\displaystyle\implies$
$\displaystyle\frac{t^{2}}{d}=\Omega\left(\frac{1}{\delta(f)^{2}\log\left(\frac{1}{\delta(f)}\right)}\right).$
(72)

Equation (72) implies that there exists a universal constant $c>0$ (that
depends on the constant hidden in the asymptotic notation) such that
$t^{2}/d>1$ whenever $\delta(f)<c$. Assuming $\delta(f)<c$ and taking
logarithm of both sides of Equation (72) we have that

$\displaystyle
0<\log\left(t^{2}/d\right)=\Omega\left(\log(1/\delta(f)^{2})-\log\log(1/\delta(f))\right)=\Omega\left(\log(1/\delta(f))\right).$
(73)

Equations (71) and (73) yield

$\displaystyle\frac{d}{t^{2}\log\left(t^{2}/d\right)}=O\left(\frac{t^{2}\delta(f)^{2}\log(1/\delta(f))}{t^{2}\log(1/\delta(f))}\right)=O(\delta(f)^{2})$
$\displaystyle\implies$
$\displaystyle\delta(f)=\Omega\left(\frac{\sqrt{d}}{t\sqrt{\log\left(t^{2}/d\right)}}\right).$

Lemma A.2 $\implies$ Lemma A.1.

Assume Lemma A.2. Let $f,t,\delta(f)$ and $d$ be as in the statement of Lemma
A.1 and $c$ be the universal constant in the statement of Lemma A.2. We assume
without loss of generality (by replacing $f$ by $-f$ if necessary) that
$\delta(f)\leq 1/2$. Now, we have that

$\frac{d}{t^{2}}\leq\frac{|\mathcal{S}_{t}|}{t^{2}}\leq\sum_{S\in\mathcal{S}_{t}}\widehat{f}(S)^{2}\leq
1,$

where the first inequality holds by the definition of $\mathcal{S}_{t}$ and
$d$, the second inequality holds from the definition of $\mathcal{S}_{t}$, and
the last inequality follows from Parseval’s identity (Theorem 4.6). We
conclude that

$\displaystyle d\leq t^{2}.$ (74)

We split the proof into two cases.

Case 1: $c\leq\delta(f)\leq 1/2$.99footnotemark: 9

By Claim A.3 and the observation that $c>0$ and $\delta(f)^{2}\leq 1/4<1/e$ we
have that

$\displaystyle\delta(f)^{2}\log(1/\delta(f)^{2})\geq c^{2}\log(1/c^{2}).$ (75)

By Equation (74) we have that

$d\leq
t^{2}=O(t^{2}c^{2}\log(1/c^{2}))=O(t^{2}\delta(f)^{2}\log(1/\delta(f)^{2}))=O(t^{2}\delta(f)^{2}\log(1/\delta(f))),$

where the third step follows from Equation (75).

Case 2: $0\leq\delta(f)<c$.

From Lemma A.2 we have that
$\delta(f)^{2}=\Omega\left(\frac{d}{t^{2}\log(t^{2}/d)}\right)>0$. Recall that
by our assumption, $\delta(f)\leq 1/2$ and hence
$\log\left(1/\delta(f)\right)\geq 1$. Now, if $t^{2}/d<2$, we have from Lemma
A.2 that
$d=O(\delta(f)^{2}t^{2}\log\left(t^{2}/d\right))=O(\delta(f)^{2}t^{2})=O(\delta(f)^{2}t^{2}\log\left(1/\delta(f)\right))$
and the proof is complete. Thus, assume henceforth that $t^{2}/d\geq 2$ and
hence $\log\left(t^{2}/d\right)\geq 1$. By Lemma A.2, Claim A.3 and the
observation that $\delta(f)^{2}\leq\frac{1}{4}<\frac{1}{e}$ we have that

$\displaystyle t^{2}\delta(f)^{2}\log(1/\delta(f)^{2})$
$\displaystyle=\Omega\left(t^{2}\left(\frac{d}{t^{2}\log\left(t^{2}/d\right)}\right)\cdot\log\left(\frac{t^{2}\log(t^{2}/d)}{d}\right)\right)$
$\displaystyle=\Omega\left(\left(\frac{d}{\log\left(t^{2}/d\right)}\right)\cdot\log\left(\frac{t^{2}\log(t^{2}/d)}{d}\right)\right)$
$\displaystyle=\Omega\left(\left(\frac{d}{\log\left(t^{2}/d\right)}\right)\cdot\log\left(t^{2}/d\right)\right)$
since $\log\left(t/d^{2}\right)\geq 1$ $\displaystyle=\Omega(d).$

This completes the proof.

∎