$\displaystyle\mathbf{E}\left[\prod_{u=1}^{r}(Y_{i_{u}}-\mathbf{E}\left[Y_{i_{u}}\mid\mathcal{H}_{J}\right])^{e_{u}}(\overline{Y_{i_{u}}}-\mathbf{E}\left[\overline{Y_{i_{u}}}\mid\mathcal{H}_{J}\right])^{g_{u}}\right.$
$\displaystyle\hskip
72.26999pt\left.\prod_{v=1}^{s}(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}_{J}\right])^{e_{r+v}}\prod_{w=1}^{t}(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}_{J}\right])^{g_{r+w}}\mid\mathcal{H}_{J}\right]$
$\displaystyle=\mathbf{E}\left[\prod_{v\in
A}(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}_{J}\right])\prod_{w\in
B}(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}_{J}\right])\right.$
(45) $\displaystyle\hskip
28.90755pt\prod_{u=1}^{r}(Y_{i_{u}}-\mathbf{E}\left[Y_{i_{u}}\mid\mathcal{H}_{J}\right])^{e_{u}}(\overline{Y_{i_{u}}}-\mathbf{E}\left[\overline{Y_{i_{u}}}\mid\mathcal{H}_{J}\right])^{g_{u}}$
$\displaystyle\hskip 21.68121pt\left.\prod_{v\in[s]\setminus
A}(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}_{J}\right])^{e_{r+v}}\prod_{w\in[t]\setminus
B}(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}_{J}\right])^{g_{r+w}}\mid\mathcal{H}_{J}\right]$
$\displaystyle=$ $\displaystyle\sum_{a=0}^{\lvert A\rvert}\sum_{b=0}^{\lvert
B\rvert}\sum_{\begin{subarray}{c}S_{1}\subset A\\\ \lvert
S_{1}\rvert=a\end{subarray}}\sum_{\begin{subarray}{c}T_{1}\subset B\\\ \lvert
T_{1}\rvert=b\end{subarray}}\prod_{v\in A\setminus S_{1}}(-\lvert
x_{j_{v}}\rvert^{p}(1\pm\gamma))\prod_{w\in B\setminus T_{1}}(-\lvert
x_{k_{w}}\rvert^{p}(1\pm\gamma))$ $\displaystyle\hskip
72.26999pt\mathbf{E}\left[\prod_{v\in S_{1}}Y_{j_{v}}\prod_{w\in
T_{1}}\overline{Y_{k_{w}}}W_{A,B}\mid\mathcal{H}_{J}\right]\enspace.$ (46)

where,

$\displaystyle W_{A,B}$
$\displaystyle=\prod_{u=1}^{r}(Y_{i_{u}}-\mathbf{E}\left[Y_{i_{u}}\mid\mathcal{H}_{J}\right])^{e_{u}}(\overline{Y_{i_{u}}}-\mathbf{E}\left[\overline{Y_{i_{u}}}\mid\mathcal{H}_{J}\right])^{g_{u}}\prod_{v\in[s]\setminus
A}(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}_{J}\right])^{e_{r+v}}$
$\displaystyle\hskip 108.405pt\prod_{w\in[t]\setminus
B}(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}_{J}\right])^{g_{r+w}}\enspace.$

Consider the term inside the expectation in Eqn. ( ‣ A.4). For $v\in S_{1}$,
write
$Y_{j_{v}}=\sum_{l_{v}\text{ consist. w.
}j_{v}}2^{l_{v}}z_{j_{v}l_{v}}X_{j_{v}}^{p}$ and similarly for $Y_{k_{w}}$ for
$k\in T_{1}$. Therefore,

$\displaystyle\mathbf{E}\left[\prod_{v\in S_{1}}Y_{j_{v}}\prod_{w\in
T_{1}}\overline{Y_{k_{w}}}W_{A,B}\mid\mathcal{H}_{J}\right]=$
$\displaystyle\sum_{\begin{subarray}{c}l_{v}\textsf{~{}consist.
with~{}}~{}j_{v}\\\ l_{w}\textsf{~{}consist.
with~{}}~{}k_{w}\end{subarray}}2^{\sum_{v\in S_{1}}l_{v}+\sum_{w\in
T_{1}}}\mathbf{E}\left[\prod_{v\in S_{1}}X_{j_{v}}^{p}\prod_{w\in
T_{1}}\overline{X_{k_{w}}}^{p}W_{A,B}\prod_{v\in
S_{1}}z_{j_{v}l_{v}}\prod_{w\in
T_{1}}z_{k_{w}l_{w}}\mid\mathcal{H}_{J}\right]\enspace.$ (47)

Consider the term $\mathbf{E}\left[\prod_{v\in S_{1}}X_{j_{v}}^{p}\prod_{w\in
T_{1}}\overline{X_{k_{w}}}^{p}W_{A,B}\prod_{v\in
S_{1}}z_{j_{v}l_{v}}\prod_{w\in
T_{1}}z_{k_{w}l_{w}}\mid\mathcal{H}_{J}\right]$. Let $\mathcal{R}$ denote the
random bits used by the algorithm. Let $\omega$ denote the set of random bits
used to form the complex roots of unity sketches. Then,

$\displaystyle\mathbf{E}\left[\prod_{v\in S_{1}}X_{j_{v}}^{p}\prod_{w\in
T_{1}}\overline{X_{k_{w}}}^{p}W_{A,B}\prod_{v\in
S_{1}}z_{j_{v}l_{v}}\prod_{w\in
T_{1}}z_{k_{w}l_{w}}\mid\mathcal{H}_{J}\right]$
$\displaystyle=\mathbf{E}_{{\mathcal{R}\setminus\omega}}\left[{\mathbf{E}_{{\omega}}\left[{\prod_{v\in
S_{1}}X_{j_{v}}^{p}\prod_{w\in
T_{1}}\overline{X_{k_{w}}}^{p}W_{A,B}\prod_{v\in
S_{1}}z_{j_{v}l_{v}}\prod_{w\in
T_{1}}z_{k_{w}l_{w}}\mid\mathcal{H}_{J}}\right]}\right]\enspace.$ (48)

Now, $\mathcal{H}_{J}$ includes nocollision terms for each $i_{u},j_{v}$ and
$k_{w}$ as per the definition of the indices. Therefore, assuming $r+s+t$-wise
independence of the $\omega_{lr}(i)$ family across the $i$’s and independence
across $l\in[0,\ldots,L]$ and $r\in[2s]$, we have that

$\displaystyle\mathbf{E}_{{\omega}}\left[{\prod_{v\in
S_{1}}X_{j_{v}}^{p}\prod_{w\in
T_{1}}\overline{X_{k_{w}}}^{p}W_{A,B}\prod_{v\in
S_{1}}z_{j_{v}l_{v}}\prod_{w\in
T_{1}}z_{k_{w}l_{w}}\mid\mathcal{H}_{J}}\right]$ $\displaystyle=\prod_{v\in
S_{1}}\mathbf{E}_{{\omega}}\left[{X_{j_{v}}^{p}\mid\mathcal{H}_{J}}\right]\prod_{w\in
T_{1}}\mathbf{E}_{{\omega}}\left[{\overline{X_{k_{w}}}^{p}\mid\mathcal{H}_{J}}\right]\mathbf{E}_{{\omega}}\left[{W_{A,B}\mid\mathcal{H}_{J}}\right]$
$\displaystyle=\prod_{v\in S_{1}}\left(\lvert
x_{j_{v}}\rvert^{p}(1\pm\gamma)\right)\prod_{w\in T_{1}}\left(\lvert
x_{k_{w}}\rvert^{p}(1\pm\gamma)\right)\mathbf{E}_{{\omega}}\left[{W_{A,B}\mid\mathcal{H}_{J}}\right]\enspace.$

Substituting in Eqn. (A.4), we have,

$\displaystyle\mathbf{E}\left[\prod_{v\in S_{1}}X_{j_{v}}^{p}\prod_{w\in
T_{1}}\overline{X_{k_{w}}}^{p}W_{A,B}\prod_{v\in
S_{1}}z_{j_{v}l_{v}}\prod_{w\in
T_{1}}z_{k_{w}l_{w}}\mid\mathcal{H}_{J}\right]$ $\displaystyle=\prod_{v\in
S_{1}}\left(\lvert x_{j_{v}}\rvert^{p}(1\pm\gamma)\right)\prod_{w\in
T_{1}}\left(\lvert
x_{k_{w}}\rvert^{p}(1\pm\gamma)\right)\mathbf{E}\left[W_{A,B}\prod_{v\in
S_{1}}z_{j_{v}l_{v}}\prod_{w\in
T_{1}}z_{k_{w}l_{w}}\mid\mathcal{H}_{J}\right]\enspace.$ (49)

Substituting in Eqn. (A.4), we have,

$\displaystyle\mathbf{E}\left[\prod_{v\in S_{1}}Y_{j_{v}}\prod_{w\in
T_{1}}\overline{Y_{k_{w}}}W_{A,B}\mid H\right]=\prod_{v\in S_{1}}\left(\lvert
x_{j_{v}}\rvert^{p}(1\pm\gamma)\right)\prod_{w\in T_{1}}\left(\lvert
x_{k_{w}}\rvert^{p}(1\pm\gamma)\right)$ $\displaystyle\hskip
72.26999pt\sum_{\begin{subarray}{c}l_{v}\textsf{~{}consist.
with~{}}~{}j_{v}\\\ l_{w}\textsf{~{}consist.
with~{}}~{}k_{w}\end{subarray}}2^{\sum_{v\in S_{1}}l_{v}+\sum_{w\in
T_{1}}}\mathbf{E}\left[W_{A,B}\prod_{v\in S_{1}}z_{j_{v}l_{v}}\prod_{w\in
T_{1}}z_{k_{w}l_{w}}\mid\mathcal{H}_{J}\right]$ (50)

Consider the term

$\displaystyle\sum_{\begin{subarray}{c}l_{v}\textsf{~{}consist.
with~{}}~{}j_{v}\\\ l_{w}\textsf{~{}consist.
with~{}}~{}k_{w}\end{subarray}}2^{\sum_{v\in S_{1}}l_{v}+\sum_{w\in
T_{1}}}\mathbf{E}\left[W_{A,B}\prod_{v\in S_{1}}z_{j_{v}l_{v}}\prod_{w\in
T_{1}}z_{k_{w}l_{w}}\mid\mathcal{H}_{J}\right]$ (51)

Given the definition of the conditioning event $\mathcal{H}_{J}$, Lemma 27
essentially asserts that Eqn. (51) lies in

$\displaystyle\in\mathbf{E}\left[W_{A,B}\mid\mathcal{H}_{J}\right](1\pm(\lvert
S_{1}\rvert+\lvert T_{1}\rvert)\gamma)^{\lvert S_{1}\rvert+\lvert
T_{1}\rvert}$
$\displaystyle\in\mathbf{E}\left[W_{A,B}\mid\mathcal{H}_{J}\right](1\pm(\lvert
A\rvert+\lvert B\rvert)^{2}\gamma)$

where it is assumed that $\lvert A\rvert+\lvert B\rvert\leq n^{O(1)}$.

Substituting in Eqn. (A.4), we obtain that

$\mathbf{E}\left[\prod_{v\in S_{1}}Y_{j_{v}}\prod_{w\in
T_{1}}\overline{Y_{k_{w}}}W_{A,B}\mid\mathcal{H}_{J}\right]\\\
=(1\pm\gamma)^{(\lvert A\rvert+\lvert B\rvert)^{2}}(1\pm\gamma)^{\lvert
S_{1}\rvert+\lvert T_{1}\rvert}\prod_{v\in S_{1}}\lvert
x_{j_{v}}\rvert^{p}\prod_{w\in T_{1}}\lvert
x_{k_{w}}\rvert^{p}\mathbf{E}\left[W_{A,B}\mid\mathcal{H}_{J}\right]$ (52)

Substituting in Eqn. ( ‣ A.4), we have,

$\displaystyle\mathbf{E}\left[\prod_{u=1}^{r}(Y_{i_{u}}-\mathbf{E}\left[Y_{i_{u}}\mid\mathcal{H}_{J}\right])^{e_{u}}(\overline{Y_{i_{u}}}-\mathbf{E}\left[\overline{Y_{i_{u}}}\mid\mathcal{H}_{J}\right])^{g_{u}}\prod_{v=1}^{s}(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}_{J}\right])^{e_{r+v}}\right.$
$\displaystyle\hskip
36.135pt\left.\prod_{w=1}^{t}(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}_{J}\right])^{g_{r+w}}\mid\mathcal{H}_{J}\right]$
$\displaystyle=(1\pm\gamma)^{(\lvert A\rvert+\lvert
B\rvert)^{2}}\mathbf{E}\left[W_{A,B}\mid\mathcal{H}_{J}\right]$
$\displaystyle~{}~{}\sum_{a=0}^{\lvert A\rvert}\sum_{b=0}^{\lvert
B\rvert}\sum_{\begin{subarray}{c}S_{1}\subset A\\\ \lvert
S_{1}\rvert=a\end{subarray}}\sum_{\begin{subarray}{c}T_{1}\subset B\\\ \lvert
T_{1}\rvert=b\end{subarray}}\prod_{v\in A\setminus S_{1}}(-\lvert
x_{j_{v}}\rvert^{p}(1\pm\gamma))\prod_{w\in B\setminus T_{1}}(-\lvert
x_{k_{w}}\rvert^{p}(1\pm\gamma))\prod_{v\in S_{1}}\lvert
x_{j_{v}}\rvert^{p}\prod_{w\in T_{1}}\lvert x_{k_{w}}\rvert^{p}$
$\displaystyle=(1\pm\gamma)^{(\lvert A\rvert+\lvert
B\rvert)^{2}}\mathbf{E}\left[W_{A,B}\mid\mathcal{H}_{J}\right]\gamma^{\lvert
A\rvert+\lvert B\rvert}\prod_{v\in A}\lvert x_{j_{v}}\rvert^{p}\prod_{w\in
B}\lvert x_{k_{w}}\rvert^{p}$ (53)

###### Fact 34

Suppose $i\in\text{lmargin}(G_{0})\cup_{l^{\prime}=1}^{L}G_{l^{\prime}}$ and
suppose $l$ is consistent with $i$ and $\beta\geq 1$ is an integer. Then,

$\displaystyle\lvert x_{i}\rvert^{p\beta}2^{l\beta}$ $\displaystyle\leq
2^{l}\lvert
x_{i}\rvert^{p}\left(\frac{F_{2}}{B}\right)^{p(\beta-1)/2}2^{(1+p/2)(\beta-1)}$

  * Proof: [Proof of Fact 34.] By the definition of $\mathsf{level}(i)$, $\lvert x_{i}\rvert\leq\left(\frac{F_{2}}{(2\alpha)^{\mathsf{level}(i)-1}B}\right)^{1/2}$. Therefore,

$\displaystyle\lvert x_{i}\rvert^{p\beta}2^{l\beta}=2^{l}\cdot
2^{l(\beta-1)}\cdot\lvert x_{i}\rvert^{p}\cdot\lvert
x_{i}\rvert^{p(\beta-1)}\leq 2^{l}\lvert
x_{i}\rvert^{p}\left(\frac{F_{2}}{(2\alpha)^{\mathsf{level}(i)-1}B}\right)^{p(\beta-1)/2}2^{l(\beta-1)}$
(54)

Now $-1\leq l-\mathsf{level}(i)\leq 1$ and $2^{\ell}(2\alpha)^{-\ell
p/2}=2^{\ell(1-(p/2)\log_{2}(2\alpha))}$, for any $\ell$.

Since, $\alpha=1-(1-2/p)\nu$, where, $\nu=0.01$,
$\ln(\alpha)\geq-2(1-2/p)\nu$. Hence,

$\displaystyle 1-(p/2)\log_{2}(2\alpha)$
$\displaystyle=1-(p/2)(1+\log_{2}(\alpha))$
$\displaystyle=1-p/2-\frac{p/2}{\ln 2}\ln(\alpha)$
$\displaystyle\leq-(p/2-1)+\frac{(p/2)}{\ln 2}(1-2/p)(2\nu))$
$\displaystyle=-(p/2-1)+(p/2-1)\frac{(2\nu)}{\ln 2}$
$\displaystyle=-(p/2-1)(1-2\nu/\ln(2))$ $\displaystyle<0$

Hence, for any $\ell\geq 0$, $2^{\ell}(2\alpha)^{-\ell p/2}<1$. Therefore, for
any integer $\beta\geq 1$, we have,

$\displaystyle\lvert x_{i}\rvert^{p\beta}2^{l\beta}$ $\displaystyle\leq
2^{l}\lvert
x_{i}\rvert^{p}\left(\frac{F_{2}}{(2\alpha)^{\mathsf{level}(i)-1}B}\right)^{p(\beta-1)/2}2^{l(\beta-1)}$
$\displaystyle=2^{l}\lvert
x_{i}\rvert^{p}\left(\frac{F_{2}}{B}\right)^{p(\beta-1)/2}\left(\frac{2^{\mathsf{level}(i)}}{(2\alpha)^{(p/2)\mathsf{level}(i)}}\right)^{\beta-1}(2\alpha)^{(p/2)(\beta-1)}2^{(l-\mathsf{level}(i))(\beta-1)}$
$\displaystyle\leq 2^{l}\lvert
x_{i}\rvert^{p}\left(\frac{F_{2}}{B}\right)^{p(\beta-1)/2}2^{(1+p/2)(\beta-1)}$

###### Lemma 35

Suppose $e_{1},\ldots,e_{r},g_{1},\ldots,g_{r}\geq 1$ and
$e_{r+1},\ldots,e_{r+s^{\prime}}\geq 2$ and $g_{r+1},\ldots,g_{r+t}\geq 2$.
Let
$\\{i_{1},\ldots,i_{r}\\}\cup\\{j_{1},\ldots,j_{s^{\prime}}\\}\cup\\{k_{1},\ldots,k_{t}\\}\subset\text{lmargin}(G_{0})\cup_{l=1}^{L}G_{l}$.
Let $s\geq 2\max_{u=1}^{r}(e_{u},g_{u})$ and $B/C\leq 1/(72p^{2})$. Let
$J^{\prime}$ denote the set
$\\{i_{1},\ldots,i_{r},j_{1},\ldots,j_{s}^{\prime},k_{1},\ldots,k_{r}^{\prime}\\}$.
Let $\mathcal{H}_{J^{\prime}}$ denote
$\mathcal{G}\wedge\textsc{nocollision}(J^{\prime})\wedge\textsc{accuest}(J^{\prime})$.
Then,

$\displaystyle\mathbf{E}$
$\displaystyle\left[\prod_{u=1}^{r}Y_{i_{u}}^{e_{u}}\overline{Y_{i_{u}}}^{g_{u}}\prod_{v\in[s^{\prime}]}Y_{j_{v}}^{e_{r+v}}\prod_{w\in[t]}\overline{Y_{k_{w}}}^{g_{r+v}}\mid\mathcal{H}_{J^{\prime}}\right]$
$\displaystyle\hskip 72.26999pt\leq
2e^{\sum_{u\in[r]}(e_{u}+g_{u})/8}\prod_{u=1}^{r}\lvert
x_{i_{u}}\rvert^{p}\prod_{v=1}^{s}\lvert
x_{j_{v}}\rvert^{p}\prod_{w=1}^{t}\lvert x_{k_{w}}\rvert^{p}$
$\displaystyle\hskip
79.49744pt\cdot\left(\frac{4F_{2}}{B}\right)^{(p/2)\left(\sum_{u=1}^{r}(e_{u}+g_{u}-1)+\sum_{v\in[s]}(e_{r+v}-1)+\sum_{w\in[t]}(e_{r+w}-1)\right)}\enspace.$

  * Proof:  The expectations in this proof are conditioned on the conjunction of events $\mathcal{G}$, $\textsc{nocollision}(J)$ and $\textsc{goodest}(J)$. For brevity, let $\mathcal{H}_{J^{\prime}}=\mathcal{G}\wedge\textsc{nocollision}(J^{\prime})\wedge\textsc{goodest}(J^{\prime})$.

$\displaystyle\mathbf{E}\left[\left.\prod_{u=1}^{r}Y_{i_{u}}^{e_{u}}\overline{Y_{i_{u}}}^{g_{u}}\prod_{v\in[{s^{\prime}}]}Y_{j_{v}}^{e_{r+v}}\prod_{w\in[t]}\overline{Y_{k_{w}}}^{g_{r+w}}\right|\mathcal{H}_{J^{\prime}}\right]$
$\displaystyle=\mathbf{E}\left[\prod_{u=1}^{r}\left(\sum_{l_{u}\text{ consist.
w.
}i_{u}}2^{l_{u}}z_{i_{u}l_{u}}X_{i_{u}}^{p}\right)^{e_{u}}\left(\sum_{l_{u}\text{
consist. w.
}i_{u}}2^{l_{u}}z_{i_{u}l_{u}}\overline{X_{i_{u}}}^{p}\right)^{g_{u}}\right.$
$\displaystyle\left.\prod_{v\in[{s^{\prime}}]}\left(\sum_{l^{\prime}_{v}\text{
consist. w.
}j_{v}}2^{l^{\prime}_{v}}z_{j_{v}l^{\prime}_{v}}X_{j_{v}}^{p}\right)^{e_{r+v}}\left.\prod_{w\in[t]}\left(\sum_{\ell_{w}\text{
consist. w.
}k_{w}}2^{\ell_{w}}z_{k_{w}\ell_{w}}\overline{X_{k_{w}}}^{p}\right)^{g_{r+w}}\right|\mathcal{H}_{J^{\prime}}\right]$
(55)

Consider one of the power terms in Eqn. ( ‣ A.4), say,
$\left(\sum_{l_{u}\text{ consist. w.
}i_{u}}2^{l_{u}}z_{i_{u}l_{u}}X_{i_{u}}^{p}\right)^{e_{u}}$. Note that for
each $i_{u}\in\text{lmargin}(G_{0})\cup_{l=1}^{L}G_{l}$, $i_{u}$ is sampled
into at most one group $\bar{G}_{l}$, for $l\in[0,L]$. Since, $z_{i_{u},l}$ is
the indicator variable that is 1 iff $i_{u}$ is sampled into $\bar{G}_{l}$,
therefore, for $z_{i_{u},l}=1$ for at most one $l\in[0,L]$. Hence, for $l\neq
l^{\prime}$, $z_{i_{u},l}z_{i_{u},l^{\prime}}=0$. Now,

$\displaystyle\left(\sum_{l_{u}\text{ consist. w.
}i_{u}}2^{l_{u}}z_{i_{u}l_{u}}X_{i_{u}}^{p}\right)^{e_{u}}=\sum_{\begin{subarray}{c}\sum_{l~{}\textsf{~{}consist.
with~{}}~{}i_{u}}h_{l}=e_{u}\\\ h_{l}\text{'s}\geq
0\end{subarray}}~{}~{}\prod_{l~{}\textsf{~{}consist.
with~{}}~{}i_{u}}\left(2^{l}z_{i_{u},l}X_{i_{u}}^{p}\right)^{h_{l}}$

In the product term $\prod_{l~{}\textsf{~{}consist.
with~{}}~{}i_{u}}\left(2^{l}z_{i_{u},l}X_{i_{u}}^{p}\right)^{h_{l}}$, if
$h_{l}$ and $h_{l^{\prime}}$ are both non-zero for some $l\neq l^{\prime}$,
then,
$z_{i_{u},l}^{h_{l}}z_{i_{u},l^{\prime}}^{h_{l^{\prime}}}=z_{i_{u},l}z_{i_{u},l^{\prime}}=0$,
and therefore the product term is 0. Hence, the only contribution comes from
the diagonal terms, that is

$\displaystyle\left(\sum_{l_{u}\text{ consist. w.
}i_{u}}2^{l_{u}}z_{i_{u}l_{u}}X_{i_{u}}^{p}\right)^{e_{u}}$
$\displaystyle=\sum_{l_{u}~{}\textsf{~{}consist.
with~{}}~{}i_{u}}2^{l_{u}e_{u}}z_{i_{u}l_{u}}X_{i_{u}}^{pe_{u}}$
$\displaystyle=X_{i_{u}}^{pe_{u}}\sum_{l_{u}\textsf{~{}consist.
with~{}}~{}i_{u}}2^{l_{u}e_{u}}z_{i_{u}l_{u}}\enspace.$

Substituting in Eqn. ( ‣ A.4), we have,

$\displaystyle\mathbf{E}$
$\displaystyle\left[\prod_{u=1}^{r}\left(\sum_{l_{u}\text{ consist. w.
}i_{u}}2^{l_{u}}z_{i_{u}l_{u}}X_{i_{u}}^{p}\right)^{e_{u}}\left(\sum_{l_{u}\text{
consist. w.
}i_{u}}2^{l_{u}}z_{i_{u}l_{u}}\overline{X_{i_{u}}}^{p}\right)^{g_{u}}\right.$
$\displaystyle\left.\prod_{v\in[{s^{\prime}}]}\left(\sum_{l^{\prime}_{v}\text{
consist. w.
}j_{v}}2^{l^{\prime}_{v}}z_{j_{v}l^{\prime}_{v}}X_{j_{v}}^{p}\right)^{e_{r+v}}\left.\prod_{w\in[t]}\left(\sum_{\ell_{w}\text{
consist. w.
}k_{w}}2^{\ell_{w}}z_{k_{w}\ell_{w}}\overline{X_{k_{w}}}^{p}\right)^{g_{r+w}}\right|\mathcal{H}_{J^{\prime}}\right]$
$\displaystyle=\mathbf{E}\left[\prod_{u=1}^{r}X_{i_{u}}^{pe_{u}}\overline{X_{i_{u}}}^{pg_{u}}\prod_{v=1}^{s^{\prime}}X_{j_{v}}^{pe_{r+v}}\prod_{w\in[t]}\overline{X_{k_{w}}}^{pg_{r+w}}\prod_{u=1}^{r}\sum_{l_{u}\text{
consist. w. }i_{u}}2^{l_{u}(e_{u}+g_{u})}z_{i_{u}l_{u}}\right.$
$\displaystyle\hskip
36.135pt\left.\left.\prod_{v=1}^{s^{\prime}}\sum_{l^{\prime}_{v}\text{
consist. w.
}j_{v}}2^{l^{\prime}_{v}e_{r+v}}z_{j_{v}l^{\prime}_{v}}\prod_{w=1}^{t}\sum_{\ell_{w}\text{
consist. w.
}k_{w}}2^{\ell_{w}g_{r+w}}z_{k_{w}\ell_{w}}\right|\mathcal{H}_{J^{\prime}}\right]\enspace.$
(56)

For any $i$, conditional on $\mathcal{H}_{J^{\prime}}$, $X_{i}=\lvert
x_{i}\rvert+Z_{i}=\lvert x_{i}\rvert\left(1+\frac{Z_{i}}{\lvert
x_{i}\rvert}\right)$, where $Z_{i}$ is given by Eqns. (35) and (36). Then,
Eqn. ( ‣ A.4) equals

$\displaystyle=\prod_{u=1}^{r}\lvert
x_{i_{u}}\rvert^{p(e_{u}+g_{u})}\prod_{v=1}^{s^{\prime}}\lvert
x_{j_{v}}\rvert^{pe_{r+v}}\prod_{w=1}^{t}\lvert x_{k_{w}}\rvert^{pg_{r+t}}$
$\displaystyle\hskip 14.45377pt\sum_{\begin{subarray}{c}l_{u}\text{ consist.
w. }i_{u},u=1,\ldots,r\\\ l^{\prime}_{v}\text{ consist. w.
}j_{v},v\in[{s^{\prime}}]\\\ \ell_{w}\text{ con{s'}ist. w.
}k_{w},w\in[t]\end{subarray}}2^{\sum_{u=1}^{r}{l_{u}(e_{u}+g_{u})}+\sum_{v=1}^{s^{\prime}}l^{\prime}_{v}e_{r+v}+\sum_{w=1}^{t}\ell_{w}g_{r+w}}$
$\displaystyle\mathbf{E}\left[\prod_{u=1}^{r}\left(1+\frac{Z_{i_{u}}}{\lvert
x_{i_{u}}\rvert}\right)^{pe_{u}}\left(1+\frac{\overline{Z_{i_{u}}}}{\lvert
x_{i_{u}}\rvert}\right)^{pg_{u}}\prod_{v=1}^{s^{\prime}}\left(1+\frac{Z_{j_{v}}}{\lvert
x_{j_{v}}\rvert}\right)^{pe_{r+v}}\prod_{w=1}^{t}\left(1+\frac{Z_{k_{w}}}{\lvert
x_{k_{w}}\rvert}\right)^{pg_{r+w}}\right.$ $\displaystyle\left.\hskip
43.36243pt\left|\bigwedge_{u=1}^{r}z_{i_{u}l_{u}}=1\bigwedge_{v=1}^{t}z_{j_{v}l^{\prime}_{v}}=1\bigwedge_{w=1}^{t}z_{k_{w}\ell_{w}}=1,\mathcal{H}_{J^{\prime}}\right.\right]$
$\displaystyle\hskip
43.36243pt\cdot\text{Pr}\left[\bigwedge_{u=1}^{r}z_{i_{u}l_{u}}=1\bigwedge_{v=1}^{t}z_{j_{v}l^{\prime}_{v}}=1\bigwedge_{w=1}^{t}z_{k_{w}\ell_{w}}=1,\mathcal{H}_{J^{\prime}}\right]\enspace.$
(57)

We will denote the expression in the expectation as $P(I,J,K,e,g)$, where,
$I=\\{i_{1},\ldots,i_{r}\\},J=\\{j_{1},\ldots,j_{s^{\prime}}\\}$ and
$K=\\{k_{1},\ldots,k_{t}\\}$. $e$ denotes the vector
$(e_{1},\ldots,e_{r+{s^{\prime}}})$ and $g$ denotes the vector
$(g_{1},\ldots,g_{r+t})$, where, $e_{1},\ldots,e_{r}\geq 1$,
$g_{1},\ldots,g_{r}\geq 1$, and
$e_{r+1},\ldots,e_{r+{s^{\prime}}},g_{r+1},\ldots,g_{r+t}\geq 2$. Then, Eqn. (
‣ A.4) may be written as

$\displaystyle=\prod_{u=1}^{r}\lvert
x_{i_{u}}\rvert^{p(e_{u}+g_{u})}\prod_{v=1}^{s^{\prime}}\lvert
x_{j_{v}}\rvert^{pe_{r+v}}\prod_{w=1}^{t}\lvert x_{k_{w}}\rvert^{pg_{r+t}}$
$\displaystyle\sum_{\begin{subarray}{c}l_{u}\text{ consist. w.
}i_{u},u=1,\ldots,r\\\ l^{\prime}_{v}\text{ consist. w.
}j_{v},v\in[{s^{\prime}}]\\\ \ell_{w}\text{ con{s'}ist. w.
}k_{w},w\in[t]\end{subarray}}2^{\sum_{u=1}^{r}{l_{u}(e_{u}+g_{u})}+\sum_{v=1}^{s^{\prime}}l^{\prime}_{v}e_{r+v}+\sum_{w=1}^{t}\ell_{w}g_{r+w}}$
$\displaystyle\hskip
50.58878pt\mathbf{E}\left[P(I,J,K,e,g)\left|\bigwedge_{u=1}^{r}z_{i_{u}l_{u}}=1\bigwedge_{v=1}^{t}z_{j_{v}l^{\prime}_{v}}=1\bigwedge_{w=1}^{t}z_{k_{w}\ell_{w}}=1,\mathcal{H}_{J^{\prime}}\right.\right]$
$\displaystyle\hskip
72.26999pt\text{Pr}\left[\bigwedge_{u=1}^{r}z_{i_{u}l_{u}}=1\bigwedge_{v=1}^{t}z_{j_{v}l^{\prime}_{v}}=1\bigwedge_{w=1}^{t}z_{k_{w}\ell_{w}}=1,\mathcal{H}_{J^{\prime}}\right]\enspace.$

By $\textsc{nocollision}(J)$, we have

$\displaystyle\mathbf{E}\left[P(I,J,K,e,g)\mid\left|\bigwedge_{u=1}^{r}z_{i_{u}l_{u}}=1\bigwedge_{v=1}^{t}z_{j_{v}l^{\prime}_{v}}=1\bigwedge_{w=1}^{t}z_{k_{w}\ell_{w}}=1,\mathcal{H}_{J^{\prime}}\right.\right]$
$\displaystyle\mathbf{E}\left[\left.\prod_{u=1}^{r}\left(1+\frac{Z_{i_{u}}}{\lvert
x_{i_{u}}\rvert}\right)^{pe_{u}}\left(1+\frac{\overline{Z_{i_{u}}}}{\lvert
x_{i_{u}}\rvert}\right)^{pg_{u}}\prod_{v=1}^{s^{\prime}}\left(1+\frac{Z_{j_{v}}}{\lvert
x_{j_{v}}\rvert}\right)^{pe_{r+v}}\prod_{w=1}^{t}\left(1+\frac{Z_{k_{w}}}{\lvert
x_{k_{w}}\rvert}\right)^{pg_{r+w}}\right|\right.$ $\displaystyle\hskip
72.26999pt\left.\bigwedge_{u=1}^{r}z_{i_{u}l_{u}}=1\bigwedge_{v=1}^{t}z_{j_{v}l^{\prime}_{v}}=1\bigwedge_{w=1}^{t}z_{k_{w}\ell_{w}}=1,\mathcal{H}_{J^{\prime}}\right]$
$\displaystyle=\prod_{u=1}^{r}\mathbf{E}\left[\left.\left(1+\frac{Z_{i_{u}}}{\lvert
x_{i_{u}}\rvert}\right)^{pe_{u}}\left(1+\frac{\overline{Z_{i_{u}}}}{\lvert
x_{i_{u}}\rvert}\right)^{pg_{u}}\right\rvert
z_{i_{u},l_{u}}=1,\mathcal{H}_{J^{\prime}}\right]$ $\displaystyle\hskip
72.26999pt\cdot\prod_{v=1}^{s^{\prime}}\mathbf{E}\left[\left.\left(1+\frac{Z_{j_{v}}}{\lvert
x_{j_{v}}\rvert}\right)^{pe_{r+v}}\right|z_{j_{v},l^{\prime}_{v}}=1,\mathcal{H}_{J^{\prime}}\right]$
$\displaystyle\hskip
72.26999pt\cdot\prod_{w=1}^{t}\mathbf{E}\left[\left.\left(1+\frac{Z_{k_{w}}}{\lvert
x_{k_{w}}\rvert}\right)^{pg_{r+w}}\right|z_{k_{w},\ell_{w}}=1,\mathcal{H}_{J^{\prime}}\right]\left(1\pm
n^{-\Omega(1)}\right)\enspace.$ (58)

We now consider $\mathbf{E}\left[\left.\left(1+\frac{Z_{i_{u}}}{\lvert
x_{i_{u}}\rvert}\right)^{pe_{u}}\left(1+\frac{\overline{Z_{i_{u}}}}{\lvert
x_{i_{u}}\rvert}\right)^{pg_{u}}\right\rvert
z_{i_{u},l_{u}}=1,\mathcal{H}_{J^{\prime}}\right]$. Then, since,
$z_{i_{u},l_{u}}=1$, we have $\frac{\lvert Z_{i_{u}}\rvert}{\lvert
x_{i_{u}}\rvert}\leq(B/C)^{1/2}\leq 1/(8p)$ with probability
$1-n^{-\Omega(1)}$. Hence,

$\mathbf{E}\left[\left.\left(1+\frac{Z_{i_{u}}}{\lvert
x_{i_{u}}\rvert}\right)^{pe_{u}}\left(1+\frac{\overline{Z_{i_{u}}}}{\lvert
x_{i_{u}}\rvert}\right)^{pg_{u}}\right\rvert\mathcal{H}_{J^{\prime}}\right]\\\
\leq\left(1+\frac{\lvert Z_{i_{u}}\rvert}{\lvert
x_{i_{u}}\rvert}\right)^{pe_{u}}\left(1+\frac{\lvert Z_{i_{u}}\rvert}{\lvert
x_{i_{u}}\rvert}\right)^{pg_{u}}\leq\left(1+\frac{1}{8p}\right)^{p(e_{u}+g_{u})}\enspace.$

with probability $1-n^{-\Omega(1)}$.

Now consider $\mathbf{E}\left[\left.\left(1+\frac{Z_{j_{v}}}{\lvert
x_{j_{v}}\rvert}\right)^{pe_{r+v}}\right|z_{j_{v},l^{\prime}_{v}}=1,\mathcal{H}_{J^{\prime}}\right]$,
for a fixed $v\in[s^{\prime}]$. Let $c_{i}=\binom{pe_{r+v}}{i}$, for
$i=1,2,\ldots,k$. Since, $\frac{\lvert Z_{j_{v}}\rvert}{\lvert
x_{j_{v}}\rvert}\leq 1/8$ with probability $1-n^{-\Omega(1)}$, we have by the
Taylor’s series expansion of $\left(1+\frac{Z_{j_{v}}}{\lvert
x_{j_{v}}\rvert}\right)^{pe_{r+v}}$ up to $k$ terms (and using $k+1$-wise
independence of the family $\\{\omega_{lr}(i)\\}_{i\in[n]}$), that

$\displaystyle\left(1+\frac{Z_{j_{v}}}{\lvert
x_{j_{v}}\rvert}\right)^{pe_{r+v}}=\sum_{i=0}^{k-1}c_{i}\frac{Z_{j_{v}}^{i}}{\lvert
x_{j_{v}}\rvert^{i}}+c_{k}\frac{Z_{j_{v}}^{{}^{\prime}k}}{\lvert
x_{j_{v}}\rvert^{k}}$

where, $\lvert Z^{\prime}_{j_{v}}\rvert\leq\lvert Z_{j_{v}}\rvert$.

Taking expectation, and using the fact that
$\mathbf{E}\left[Z_{j_{v}}^{i}\right]=0$, for $r=1,2,\ldots,k-1$, and since,
$\lvert Z^{\prime}_{j_{v}}\rvert\leq\lvert Z_{j_{v}}\rvert\leq(1/(8p))\lvert
x_{j_{v}}\rvert$, with probability $1-n^{-\Omega(1)}$, given that
$z_{j_{v},l^{\prime}_{v}}=1$, we have,

$\displaystyle\mathbf{E}\left[\left(1+\frac{Z_{j_{v}}}{\lvert
x_{j_{v}}\rvert}\right)^{pe_{r+v}}\mid\mathcal{H}_{J^{\prime}}\right]$
$\displaystyle=\sum_{r=0}^{k-1}c_{r}\frac{\mathbf{E}\left[Z_{j_{v}}^{r}\mid
H\right]}{\lvert
x_{j_{v}}\rvert^{r}}+c_{k}\frac{\mathbf{E}\left[Z_{j_{v}}^{{}^{\prime}k}\mid\mathcal{H}_{J^{\prime}}\right]}{\lvert
x_{j_{v}}\rvert^{k}}=1+c_{k}\frac{\mathbf{E}\left[Z_{j_{v}}^{{}^{\prime}k}\mid\mathcal{H}_{J^{\prime}}\right]}{\lvert
x_{j_{v}}\rvert^{k}}$ $\displaystyle\leq 1+\lvert c_{k}\rvert\frac{\lvert
Z_{j_{v}}^{{}^{\prime}k}\rvert}{\lvert x_{j_{v}}\rvert^{k}}\leq 1+\lvert
c_{k}\rvert\frac{\lvert Z_{j_{v}}^{k}\rvert}{\lvert x_{j_{v}}\rvert^{k}}\leq
1+\lvert c_{k}\rvert(8p)^{-k}\leq 1+n^{-\Omega(1)}$

since,
$c_{k}=\bigl{\lvert}\binom{pe_{r+v}}{k}\bigr{\rvert}\leq\left(\frac{pe_{r+v}}{k}\right)^{\lceil
p\rceil}<1$, assuming $k\geq 2pe_{r+v}$.

Substituting in Eqn. (A.4) we have,

$\displaystyle\mathbf{E}\left[P(I,J,K,e,g)\mid\bigwedge_{u=1}^{r}z_{i_{u}l_{u}}=1\bigwedge_{v=1}^{t}z_{j_{v}l^{\prime}_{v}}=1\bigwedge_{w=1}^{t}z_{k_{w}\ell_{w}}=1,\mathcal{H}_{J^{\prime}}\right]$
$\displaystyle\leq\left(1+\frac{1}{8p}\right)^{p\sum_{u\in[r]}(e_{u}+g_{u})}\left(1+n^{-\Omega(1)}\right)^{s^{\prime}+t}$
$\displaystyle\leq
e^{\sum_{u\in[r]}(e_{u}+g_{u})/8}\left(1+n^{-\Omega(1)}\right)\enspace.$ (59)

Substituting Eqn. (A.4) in Eqn. ( ‣ A.4), we have,

$\displaystyle\mathbf{E}\left[\left.\prod_{u=1}^{r}Y_{i_{u}}^{e_{u}}\overline{Y_{i_{u}}}^{g_{u}}\prod_{v\in[s]}Y_{j_{v}}^{e_{r+v}}\prod_{w\in[t]}\overline{Y_{k_{w}}}^{g_{r+v}}\right\rvert\mathcal{H}_{J^{\prime}}\right]$
$\displaystyle=e^{\sum_{u\in[r]}(e_{u}+g_{u})/8}\left(1+n^{-\Omega(1)}\right)\sum_{\begin{subarray}{c}l_{u}\text{
consist. w. }i_{u},u=1,\ldots,r\\\ l^{\prime}_{v}\text{ consist. w.
}j_{v},v\in[s]\\\ \ell_{w}\text{ consist. w.
}k_{w},w\in[t]\end{subarray}}2^{\sum_{u=1}^{r}{l_{u}(e_{u}+g_{u})}+\sum_{v=1}^{s}l^{\prime}_{u}+\sum_{w=1}^{t}\ell_{w}}$
$\displaystyle\prod_{u=1}^{r}\lvert
x_{i_{u}}\rvert^{p(e_{u}+g_{u})}\prod_{v=1}^{s}\lvert
x_{j_{v}}\rvert^{pe_{r+v}}\prod_{w=1}^{t}\lvert x_{k_{w}}\rvert^{pg_{r+t}}$
$\displaystyle\hskip
72.26999pt\text{Pr}\left[\left.\bigwedge_{u=1}^{r}z_{i_{u}l_{u}}=1\bigwedge_{v=1}^{t}z_{j_{v}l^{\prime}_{v}}=1\bigwedge_{w=1}^{t}z_{k_{w}\ell_{w}}=1\right|\mathcal{H}_{J^{\prime}}\right]\enspace.$
(60)

By Fact 34, we have, for any $i\in\text{lmargin}(G_{0})\cup_{l=1}^{L}G_{l}$,
$l$ consistent with $i$ and $\beta\geq 1$,

$\lvert x_{i}\rvert^{p\beta}2^{\beta l}\leq 2^{l}\lvert
x_{i}\rvert^{p}\left(\frac{F_{2}}{B}\right)^{p(\beta-1)/2}2^{(p/2+1)(\beta-1)}=2^{l}\lvert
x_{i}\rvert^{p}\left(\frac{2^{1+2/p}F_{2}}{B}\right)^{(p/2)(\beta-1)}\enspace.$

Thus,

$\lvert x_{i_{u}}\rvert^{p(e_{u}+g_{u})}2^{(e_{u}+g_{u})l_{u}}\leq\lvert
x_{i_{u}}\rvert^{p}2^{l_{u}}\left(\frac{2^{1+2/p}F_{2}}{B}\right)^{(p/2)(e_{u}+g_{u}-1)}$

and

$\lvert x_{j_{v}}\rvert^{pe_{r+v}}2^{e_{r+v}l^{\prime}_{v}}\leq\lvert
x_{j_{v}}\rvert^{p}2^{l^{\prime}_{v}}\left(\frac{2^{1+2/p}F_{2}}{B}\right)^{(p/2)(e_{r+v}-1)}\enspace.$

Using this, Eqn. (A.4) is upper bounded as

$\displaystyle\mathbf{E}\left[\left.\prod_{u=1}^{r}Y_{i_{u}}^{e_{u}}\overline{Y_{i_{u}}}^{g_{u}}\prod_{v\in[s^{\prime}]}Y_{j_{v}}^{e_{r+v}}\prod_{w\in[t]}\overline{Y_{k_{w}}}^{g_{r+v}}\right\rvert\mathcal{H}_{J^{\prime}}\right]$
$\displaystyle\leq
e^{\sum_{u\in[r]}(e_{u}+g_{u})/8}\left(1+n^{-\Omega(1)}\right)\prod_{u=1}^{r}\lvert
x_{i_{u}}\rvert^{p}\prod_{v=1}^{s}\lvert
x_{j_{v}}\rvert^{p}\prod_{w=1}^{t}\lvert x_{k_{w}}\rvert^{p}$
$\displaystyle\hskip
36.135pt\left(\frac{2^{1+2/p}F_{2}}{B}\right)^{(p/2)\left(\sum_{u=1}^{r}(e_{u}+g_{u}-1)+\sum_{v\in[s]}(e_{r+v}-1)+\sum_{w\in[t]}(e_{r+w}-1)\right)}$
$\displaystyle\sum_{\begin{subarray}{c}l_{u}\text{ consist. w.
}i_{u},u=1,\ldots,r\\\ l^{\prime}_{v}\text{ consist. w. }j_{v},v\in[s]\\\
\ell_{w}\text{ consist. w.
}k_{w},w\in[t]\end{subarray}}2^{\sum_{u\in[r]}l_{u}+\sum_{v\in[s]}l_{v}+\sum_{w\in[t]}l_{w}}$
$\displaystyle\hskip
108.405pt\text{Pr}\left[\bigwedge_{u=1}^{r}z_{i_{u}l_{u}}=1\bigwedge_{v=1}^{t}z_{j_{v}l^{\prime}_{v}}=1\bigwedge_{w=1}^{t}z_{k_{w}\ell_{w}}=1\mid\mathcal{H}_{J^{\prime}}\right]$
(61)

Recall that for brevity purposes, in this proof, we have extended the event
$\mathcal{H}_{J^{\prime}}$ to also include $\textsc{nocollision}(J)$ and
$\textsc{goodest}(J)$. Then, by Lemma 7,

$\displaystyle\sum_{\begin{subarray}{c}l_{u}\text{ consist. w.
}i_{u},u=1,\ldots,r\\\ l^{\prime}_{v}\text{ consist. w. }j_{v},v\in[s]\\\
\ell_{w}\text{ consist. w.
}k_{w},w\in[t]\end{subarray}}2^{\sum_{u\in[r]}l_{u}+\sum_{v\in[s]}l_{v}+\sum_{w\in[t]}l_{w}}$
$\displaystyle\hskip
72.26999pt\cdot\text{Pr}\left[\bigwedge_{u=1}^{r}z_{i_{u}l_{u}}=1\bigwedge_{v=1}^{t}z_{j_{v}l^{\prime}_{v}}=1\bigwedge_{w=1}^{t}z_{k_{w}\ell_{w}}=1\mid\mathcal{H}_{J^{\prime}}\right]=1\pm
n^{-\Omega(1)}$

Substituting in Eqn. (A.4), we obtain

$\displaystyle\mathbf{E}\left[\left.\prod_{u=1}^{r}Y_{i_{u}}^{e_{u}}\overline{Y_{i_{u}}}^{g_{u}}\prod_{v\in[s^{\prime}]}Y_{j_{v}}^{e_{r+v}}\prod_{w\in[t]}\overline{Y_{k_{w}}}^{g_{r+v}}\right\rvert\mathcal{H}_{J^{\prime}}\right]$
$\displaystyle\leq
e^{\sum_{u\in[r]}(e_{u}+g_{u})/8}\left(1+n^{-\Omega(1)}\right)^{2}\prod_{u=1}^{r}\lvert
x_{i_{u}}\rvert^{p}\prod_{v=1}^{s}\lvert
x_{j_{v}}\rvert^{p}\prod_{w=1}^{t}\lvert x_{k_{w}}\rvert^{p}$
$\displaystyle\hskip
36.135pt\left(\frac{2^{1+2/p}F_{2}}{B}\right)^{(p/2)\left(\sum_{u=1}^{r}(e_{u}+g_{u}-1)+\sum_{v\in[s]}(e_{r+v}-1)+\sum_{w\in[t]}(e_{r+w}-1)\right)}$
$\displaystyle\leq 2e^{\sum_{u\in[r]}(e_{u}+g_{u})/8}\prod_{u=1}^{r}\lvert
x_{i_{u}}\rvert^{p}\prod_{v=1}^{s}\lvert
x_{j_{v}}\rvert^{p}\prod_{w=1}^{t}\lvert x_{k_{w}}\rvert^{p}$
$\displaystyle\hskip
36.135pt\left(\frac{4F_{2}}{B}\right)^{(p/2)\left(\sum_{u=1}^{r}(e_{u}+g_{u}-1)+\sum_{v\in[s]}(e_{r+v}-1)+\sum_{w\in[t]}(e_{r+w}-1)\right)}$

since, $p\geq 2$ and $2^{1+2/p}\leq 2^{2}=4$.

###### Lemma 36

Let $X$ be a non-negative real random variable with expectation
$\mathbf{E}\left[X\right]=\mu$. Then, for any integer $e\geq 2$,
$\mathbf{E}\left[(X-\mu)^{e}\right]\leq\mathbf{E}\left[X^{e}\right]+\mu^{e}\enspace.$

  * Proof:  Let $p_{x}=\text{Pr}\left[X=x\right]$. Then,

$\displaystyle\mathbf{E}\left[(X-\mu)^{e}\right]$
$\displaystyle=\sum_{x}p_{x}(x-\mu)^{e}$
$\displaystyle=\sum_{x\leq\mu}p_{x}(x-\mu)^{e}+\sum_{x>\mu}p_{x}(x-\mu)^{e}$
(62) $\displaystyle\leq\sum_{x\leq\mu}p_{x}(\mu-x)^{e}+\sum_{x>\mu}p_{x}x^{e}$
$\displaystyle\leq\sum_{x\leq\mu}p_{x}\mu^{e}+\mathbf{E}\left[X^{e}\right]$
$\displaystyle\leq\mu^{e}+\mathbf{E}\left[X^{e}\right]\enspace.$

Step 1 follows from the definition of expectation. Step 2 separates the
summation into the ranges $x\leq\mu$ and $x>\mu$. Step 3 uses the fact that in
the range $x\leq\mu$, $\mu-x\leq 0$ and therefore for any odd $e$,
$(\mu-x)^{e}\leq(x-\mu)^{e}$. For even $e$, the two powers $(\mu-x)^{e}$ and
$(x-\mu)^{e}$ are the same. Hence for all $e\geq 2$,
$(\mu-x)^{e}\leq(x-\mu)^{e}$. Further, for $x\geq\mu$, $(x-\mu)^{e}\leq
x^{e}$, since, $x\geq 0$ by virtue of $X$ being a non-negative random
variable. Step 3 follows from the facts that (i) in the range $x\leq\mu$,
$0\leq(\mu-x)\leq\mu$ and hence, $(\mu-x)^{e}\leq\mu^{e}$, and, (ii) by non-
negativity of $X$, $\sum_{x>\mu}p_{x}x^{e}\leq\sum_{x\geq
0}p_{x}x^{e}=\mathbf{E}\left[X^{e}\right]$. The final step follows since
$\sum_{x\leq\mu}p_{x}\mu^{e}=\mu^{e}\text{Pr}\left[X\leq\mu\right]\leq\mu^{e}$.

Recall that $G^{\prime}=\text{lmargin}(G_{0})\cup_{l=1}^{L}G_{l}$.

###### Lemma 37

Let $j\in G^{\prime}$. Then, the following expectation is real and is bounded
above as follows.

$\displaystyle\mathbf{E}\left[(Y_{j}-\mathbf{E}\left[Y_{j}\mid\mathcal{H}\right])^{e}_{j}\mid\mathcal{H}\right]\leq(1+\delta^{\prime\prime})(\mathbf{E}\left[Y_{j}^{e_{j}}\mid\mathcal{H}\right]+\lvert
x_{j}\rvert^{pe_{j}}(1+\delta^{\prime}))$

where,
$\delta^{\prime},\delta^{\prime\prime}\in\min(O(\delta),n^{-\Omega(1)})$.

  * Proof:  By definition, $Y_{j}=\sum_{l\textsf{~{}consist. with~{}}j}2^{l}z_{jl}X_{j}^{p}$, where, $z_{jl}=1$ iff $i\in\bar{G_{l}}$. Taking expectation of $Y_{j}$, $\mathbf{E}\left[Y_{j}\mid\mathcal{H}\right]=\sum_{l\textsf{~{}consist. with~{}}j}2^{l}\mathbf{E}\left[z_{jl}X_{j}^{p}\mid\mathcal{H}\right]$. Note that $\mathbf{E}_{{\omega}}\left[{X_{j}^{p}\mid\mathcal{H}}\right]=\lvert x_{j}\rvert^{p}$ as discussed earlier. This does not depend on the hash functions $g_{1},\ldots,g_{L}$ which determine $z_{jl}$. Therefore, $\mathbf{E}\left[z_{jl}X_{j}^{p}\mid\mathcal{H}\right]=\mathbf{E}\left[z_{jl}\mid\mathcal{H}\right]\lvert x_{j}\rvert^{p}$. Thus, we have,

$\mathbf{E}\left[Y_{j}\mid\mathcal{H}\right]=\lvert
x_{j}\rvert^{p}\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{l}z_{jl}\mid\mathcal{H}\right]=\lvert x_{j}\rvert^{p}(1\pm
2^{l}\min(O(\delta),n^{-\Omega(1)}))$

where, the last step follows from Lemma 24. In the following, we will refer to
$(1\pm 2^{l}\min(O(\delta),n^{-\Omega(1)}))$ as $1\pm\delta^{\prime}$, where,
$\delta^{\prime}=\min(O(\delta),n^{-\Omega(1)}))$.

Therefore, letting $c_{k}=\binom{e_{j}}{k}$,

$\displaystyle\mathbf{E}\left[(Y_{j}-\mathbf{E}\left[Y_{j}\mid\mathcal{H}\right])^{e_{j}}\mid\mathcal{H}\right]=\sum_{j=0}^{k}c_{k}\mathbf{E}\left[Y_{j}^{k}\mid\mathcal{H}\right](-1)^{e_{j}-k}\lvert
x_{j}\rvert^{p(e_{j}-k)}(1\pm\delta^{\prime})^{e_{j}-k}\enspace.$ (63)

Now, $\mathbf{E}\left[Y_{j}^{k}\mid\mathcal{H}\right]=1$, if $k=0$. Otherwise,
for $k\geq 1$, note that

$\left(\sum_{l\textsf{~{}consist.
with~{}}j}2^{l}z_{jl}X_{j}^{p}\right)^{k}=\sum_{l\textsf{~{}consist.
with~{}}j}2^{kl}z_{jl}X_{j}^{pk}\enspace.$

Taking expectations of both sides, and noting that
$\mathbf{E}_{{\omega}}\left[{X_{j}^{pk}}\right]=\lvert x_{j}\rvert^{pk}$ and
the expectation of the $z_{jl}$’s is independent of $\omega$, we have,

$\displaystyle\mathbf{E}\left[\left(\sum_{l\textsf{~{}consist.
with~{}}j}2^{l}z_{jl}X_{j}^{p}\right)^{k}\right]=\lvert
x_{j}\rvert^{pk}\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{kl}z_{jl}\right]\enspace.$

Substituting in Eqn. (63), we have,

$\displaystyle\mathbf{E}\left[(Y_{j}-\mathbf{E}\left[Y_{j}\mid\mathcal{H}\right])^{e_{j}}\mid\mathcal{H}\right]=\sum_{j=0}^{k}c_{k}\lvert
x_{j}\rvert^{pk}\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{kl}z_{jl}\right](-1)^{e_{j}-k}\lvert
x_{j}\rvert^{p(e_{j}-k)}(1\pm\delta^{\prime})^{e_{j}-k}\enspace.$

Define the random variable $W_{j}=\sum_{l\textsf{~{}consist.
with~{}}j}2^{l}z_{jl}$. Then, the above expectation can be written as follows.

$\displaystyle\mathbf{E}\left[((Y_{j}-\mathbf{E}\left[Y_{j}\mid\mathcal{H}\right])^{e_{j}}\mid\mathcal{H}\right]$
$\displaystyle=\sum_{j=0}^{k}c_{k}\lvert
x_{j}\rvert^{pe_{j}}\mathbf{E}\left[W_{j}^{k}\right](-1)^{e_{j}-k}\lvert
x_{j}\rvert^{p(e_{j}-k)}(1\pm\delta^{\prime})^{e_{j}-k}$
$\displaystyle=(1\pm\delta^{\prime\prime})\lvert
x_{j}\rvert^{pe_{j}}\mathbf{E}\left[(W_{j}-\mathbf{E}\left[W_{j}\mid\mathcal{H}\right])^{e_{j}}\mid\mathcal{H}\right],\text{
where, $0\leq\delta^{\prime\prime}\leq\min(O(\delta),n^{-\Omega(1)})$}$
$\displaystyle\leq(1+\delta^{\prime\prime})\lvert
x_{j}\rvert^{pe_{j}}(\mathbf{E}\left[W_{j}^{e_{j}}\mid\mathcal{H}\right]+\mathbf{E}\left[W_{j}\mid\mathcal{H}\right]^{e_{j}})$
(64)

Now, $\lvert
x_{j}\rvert^{pe_{j}}\mathbf{E}\left[W_{j}^{e_{j}}\mid\mathcal{H}\right]=\mathbf{E}\left[Y_{j}^{e_{j}}\mid\mathcal{H}\right]$,
by calculations as done above. Similarly,
$\lvert
x_{j}\rvert^{pe_{j}}(\mathbf{E}\left[W_{j}\mid\mathcal{H}\right])^{e_{j}}=\lvert
x_{j}\rvert^{pe_{j}}(1\pm\delta^{\prime})^{e_{j}}$. Substituting in Eqn. (63),
we have,

$\displaystyle\mathbf{E}\left[((Y_{j}-\mathbf{E}\left[Y_{j}\mid\mathcal{H}\right])^{e_{j}}\mid\mathcal{H}\right]\leq(1+\delta^{\prime\prime})(\mathbf{E}\left[Y_{j}^{e_{j}}\mid\mathcal{H}\right]+\lvert
x_{j}\rvert^{pe_{j}}(1+\delta^{\prime}))\enspace.$

Lemma 38 presents an approximation of the central moment
$\mathbf{E}\left[(Y_{j}-\mathbf{E}\left[Y_{j}\mid\mathcal{H}\right])^{e_{j}}\mid\mathcal{H}\right]$
in terms of the (non-central) moment
$\mathbf{E}\left[Y_{j}^{e_{j}}\mid\mathcal{H}\right]$.

###### Lemma 38

Let $j\in G^{\prime}$ and $e_{j}$ be an integer $\geq 0$. Then,

$\displaystyle\mathbf{E}\left[(Y_{j}-\mathbf{E}\left[Y_{j}\mid\mathcal{H}\right])^{e_{j}}\mid\mathcal{H}\right]\leq(2+\delta^{\prime})\mathbf{E}\left[Y_{j}^{e_{j}}\mid\mathcal{H}\right]$

where, $\delta^{\prime}\leq n^{-\Omega(1)}$.

  * Proof:  We begin with the statement of Lemma 37.

$\displaystyle\mathbf{E}\left[(Y_{j}-\mathbf{E}\left[Y_{j}\mid\mathcal{H}\right])^{e}_{j}\mid\mathcal{H}\right]\leq(1+\delta^{\prime\prime})(\mathbf{E}\left[Y_{j}^{e_{j}}\mid\mathcal{H}\right]+\lvert
x_{j}\rvert^{pe_{j}}(1+\delta^{\prime}))$ (65)

where, $\delta^{\prime},\delta^{\prime\prime}\leq n^{-\Omega(1)}$. We will now
attempt to lower bound the term
$\mathbf{E}\left[Y_{j}^{e_{j}}\mid\mathcal{H}\right]$ in terms of $\lvert
x_{j}\rvert^{pe_{j}}$. We will follow calculations similar to those in the
proof of Lemma 37. Firstly, if $e_{j}=0$, then,
$\mathbf{E}\left[Y_{j}^{e_{j}}\right]=1=\lvert x_{j}\rvert^{pe_{j}}$. So now
assume that $e_{j}\geq 1$ and integral.

$\displaystyle\mathbf{E}\left[Y_{j}^{e_{j}}\mid\mathcal{H}\right]$
$\displaystyle=\lvert
x_{j}\rvert^{pe_{j}}\mathbf{E}\left[\biggl{(}\sum_{l\textsf{~{}consist.
with~{}}j}2^{l}z_{jl}\biggr{)}^{e_{j}}\right]=\lvert
x_{j}\rvert^{pe_{j}}\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{le_{j}}z_{jl}\right]\enspace.$ (66)

We write $2^{le_{j}}z_{jl}=2^{le_{j}-l}\cdot 2^{l}z_{jl}$, for
$l\textsf{~{}consist. with~{}}j$. Let $l\textsf{~{}consist. with~{}}j$.

_Case 1:_ If $j\in\text{mid}(G_{r})$, then, the only value of $l$ consistent
with $j$ is $r$. In this case, $2^{le_{j}}z_{jl}=2^{r(e_{j}-1)}\cdot
2^{l}z_{jl}$.

_Case 2:_ If $j\in\text{rmargin}(G_{r})$, then, $2^{le_{j}}z_{jl}\geq
2^{(r-1)(e_{j}-1)}\cdot 2^{l}z_{jl}$.

_Case 3:_ If $j\in\text{lmargin}(G_{r})$, then, $2^{le_{j}}z_{jl}\geq
2^{r(e_{j}-1)}\cdot 2^{l}z_{jl}$.

Now $j\in\text{lmargin}(G_{0})\cup_{l=1}^{L}G_{l}$. If $j\in G_{r}$ and
$r\in[L]$, then, for any $l$ consistent with $j$, $2^{le_{j}}z_{jl}\geq
2^{(r-1)(e_{j}-1)}\cdot 2^{l}z_{jl}$. In this case,

$\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{le_{j}}z_{jl}\mid\mathcal{H}\right]\geq
2^{(r-1)(e_{j}-1)}\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{l}z_{jl}\mid\mathcal{H}\right]=2^{(r-1)(e_{j}-1)}(1\pm\delta^{\prime})\geq
1-\delta^{\prime}$

by Lemma 24, and since, $r\geq 1$ and $e_{j}\geq 1$.

If $j\in\text{lmargin}(G_{0})$, then, for any $l$ consistent with $j$,
$2^{le_{j}}z_{jl}\geq 2^{0(e_{j}-1)}\cdot 2^{l}z_{jl}=2^{l}z_{jl}$. In this
case, $\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{le_{j}}z_{jl}\mid\mathcal{H}\right]=1-\delta^{\prime}$, by Lemma
24. Therefore, in all cases, for
$j\in\text{lmargin}(G_{0})\cup_{l=1}^{L}G_{l}$, we have,

$\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{le_{j}}z_{jl}\mid\mathcal{H}\right]\geq
1-\delta^{\prime}\enspace.$

From Eqn. (66) for $e_{j}\geq 1$ we have,
$\displaystyle\mathbf{E}\left[Y_{j}^{e_{j}}\mid\mathcal{H}\right]\geq(1-\delta^{\prime})\lvert
x_{j}\rvert^{pe_{j}}\enspace.$

Substituting in Eqn. (65) we have,

$\displaystyle\mathbf{E}\left[(Y_{j}-\mathbf{E}\left[Y_{j}\mid\mathcal{H}\right])^{e}_{j}\mid\mathcal{H}\right]$
$\displaystyle\leq(1+\delta^{\prime\prime})(\mathbf{E}\left[Y_{j}^{e_{j}}\mid\mathcal{H}\right]+\lvert
x_{j}\rvert^{pe_{j}}(1+\delta^{\prime}))$
$\displaystyle\leq(1+\delta^{\prime\prime})(1+(1-\delta^{\prime})^{-1})\mathbf{E}\left[Y_{j}^{e_{j}}\mid\mathcal{H}\right]$
$\displaystyle=(2+\delta^{\prime\prime\prime})\mathbf{E}\left[Y_{j}^{e_{j}}\mid\mathcal{H}\right]$

where, $\delta^{\prime\prime\prime}\leq n^{-\Omega(1)})$.

Note that when $e_{j}=0$,
$\mathbf{E}\left[Y_{j}^{e_{j}}\mid\mathcal{H}\right]=1=\lvert
x_{j}\rvert^{pe_{j}}$, and the _RHS_ above becomes
$(1+\delta^{\prime\prime})(2+\delta^{\prime})=(2+\delta^{\prime\prime\prime})\mathbf{E}\left[Y_{j}^{e_{j}}\mid\mathcal{H}\right]$.

###### Lemma 39

Let $j\in\text{lmargin}(G_{0})\cup_{l=1}^{L}G_{l}$. Then, for any
$e_{j},g_{j}\geq 0$,

$\displaystyle\mathbf{E}\left[(Y_{j}-\mathbf{E}\left[Y_{j}\mid\mathcal{H}\right])^{e_{j}}(\overline{Y_{j}}-\mathbf{E}\left[\overline{Y_{j}}\mid\mathcal{H}\right])^{g_{j}}\mid\mathcal{H}\right]\leq\left(\frac{2(1+\delta^{\prime})}{1-\delta^{\prime}}\right)^{e_{j}+g_{j}}\mathbf{E}\left[Y_{j}^{e_{j}}\overline{Y_{j}}^{g_{j}}\right]$

where, $\delta^{\prime}=n^{-\Omega(1)}$.

  * Proof:  We have $Y_{j}=\sum_{l_{j}\textsf{~{}consist. with~{}}j}2^{l}z_{lj}X_{j}^{p}$. Further, $\mathbf{E}\left[Y_{j}\mid\mathcal{H}\right]=\lvert x_{j}\rvert^{p}(1\pm\delta^{\prime})$, where, $\delta^{\prime}\leq n^{-\Omega(1)}$. Let $c_{k}=\binom{e_{j}}{k}$ and $d_{k}=\binom{g_{j}}{k}$. Therefore,

$\displaystyle\mathbf{E}\left[(Y_{j}-\mathbf{E}\left[Y_{j}\mid\mathcal{H}\right])^{e_{j}}(\overline{Y_{j}}-\mathbf{E}\left[\overline{Y_{j}}\mid\mathcal{H}\right])^{g_{j}}\mid\mathcal{H}\right]$
$\displaystyle=\mathbf{E}\left[\left(\sum_{l\textsf{~{}consist.
with~{}}j}2^{l}z_{lj}X_{j}^{p}-\lvert
x_{j}\rvert^{p}(1\pm\delta^{\prime})\right)^{e_{j}}\left(\sum_{l\textsf{~{}consist.
with~{}}j}2^{l}z_{lj}X_{j}^{p}-\lvert
x_{j}\rvert^{p}(1\pm\delta^{\prime})\right)^{g_{j}}\right]$
$\displaystyle=\textbf{E}\left[\left(\sum_{k=0}^{e_{j}}c_{k}\left(\sum_{l\textsf{~{}consist.
with~{}}j}2^{l}z_{lj}X_{j}^{p}\right)^{k}(-1)^{e_{j}-k}\lvert
x_{j}\rvert^{p(e_{j}-k)}(1\pm\delta^{\prime})^{p(e_{j}-k)}\right)\right.$
$\displaystyle\hskip
36.135pt\left.\left(\sum_{k^{\prime}=0}^{g_{j}}d_{k}\left(\sum_{l\textsf{~{}consist.
with~{}}j}2^{l}z_{jl}X_{j}^{p}\right)^{k^{\prime}}(1-)^{g_{j}-k^{\prime}}\lvert
x_{j}\rvert^{p(g_{j}-k^{\prime})}(1\pm\delta^{\prime})^{p(e_{j}-k^{\prime})}\right)\right]$
$\displaystyle=\sum_{k,k^{\prime}=0,0}^{e_{j},g_{j}}c_{k}d_{k^{\prime}}\mathbf{E}\left[\left(\sum_{l\textsf{~{}consist.
with~{}}j}2^{l}z_{lj}X_{j}^{p}\right)^{k}\left(\sum_{l\textsf{~{}consist.
with~{}}j}2^{l}z_{jl}X_{j}^{p}\right)^{k^{\prime}}\right]$
$\displaystyle\hskip 72.26999pt(-1)^{e_{j}+g_{j}-k-k^{\prime}}\lvert
x_{j}\rvert^{p(e_{j}+g_{j}-k-k^{\prime})}(1\pm\delta^{\prime})^{e_{j}+g_{j}-k-k^{\prime}}\enspace.$
(67)

Since, $z_{lj}z_{l^{\prime}j}=0$, for any distinct $l,l^{\prime}$, we have for
any fixed $0\leq k\leq e_{j}$ and $0\leq k^{\prime}\leq g_{j}$ that,

$\displaystyle\mathbf{E}\left[\left(\sum_{l\textsf{~{}consist.
with~{}}j}2^{l}z_{lj}X_{j}^{p}\right)^{k}\left(\sum_{l\textsf{~{}consist.
with~{}}j}2^{l}z_{jl}X_{j}^{p}\right)^{k^{\prime}}\right]$
$\displaystyle=\mathbf{E}\left[\left(\sum_{l\textsf{~{}consist.
with~{}}j}2^{lk}z_{lj}^{k}X_{j}^{pk}\right)\left(\sum_{l\textsf{~{}consist.
with~{}}j}2^{lk^{\prime}}z_{jl}^{k^{\prime}}\overline{X_{j}}^{pk^{\prime}}\right)\right]$
$\displaystyle=\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{l(k+k^{\prime})}z_{lj}^{k+k^{\prime}}X_{j}^{pk}\overline{X_{j}}^{pk^{\prime}}\right]\enspace.$
(68)

Let $a^{pk}_{r}=\binom{pk}{r}$ and $b_{r^{\prime}}^{pk^{\prime}}$ denote
$\binom{pk^{\prime}}{r^{\prime}}$.

$\displaystyle\mathbf{E}_{{\omega}}\left[{X_{j}^{pk}\overline{X_{j}}^{pk^{\prime}}\mid\mathcal{H}}\right]$
$\displaystyle=\lvert
x_{j}\rvert^{p(k+k^{\prime})}\mathbf{E}_{{\omega}}\left[{\left(1+\frac{Z_{j}}{\lvert
x_{j}\rvert}\right)^{pk}\left(1+\frac{\overline{Z_{j}}}{\lvert
x_{j}\rvert}\right)^{pk^{\prime}}\mid\mathcal{H}}\right]$
$\displaystyle=\lvert
x_{j}\rvert^{p(k+k^{\prime})}\sum_{r,r^{\prime}=0}^{pk,pk^{\prime}}a^{pk}_{r}b^{pk^{\prime}}_{r^{\prime}}\mathbf{E}_{{\omega}}\left[{Z_{j}^{r}\overline{Z_{j}}^{r}}\right]\lvert
x_{j}\rvert^{-(r+r^{\prime})}\enspace.$ (69)

Note that the expression for $Z_{j}^{r}\overline{Z_{j}}^{r^{\prime}}$ has the
multiplicative term $\omega_{j}^{r}\overline{\omega_{j}}^{r^{\prime}}$. If
$r\neq r^{\prime}$, then, upon taking expectation with respect to all the
various $\omega_{i}$’s, in particular, we have,
$\mathbf{E}_{{\omega_{j}}}\left[{\omega_{j}^{r}\overline{\omega_{j}}^{r^{\prime}}}\right]=0$
and therefore that
$\mathbf{E}_{{|omega}}\left[{Z_{j}^{r}\overline{Z_{j}}^{r^{\prime}}}\right]=0$.
Thus, Eqn. ( ‣ A.4) is equivalent to the following expression where
$r=r^{\prime}$.

$\displaystyle\mathbf{E}_{{\omega}}\left[{X_{j}^{pk}\overline{X_{j}}^{pk^{\prime}}\mid\mathcal{H}}\right]=\lvert
x_{j}\rvert^{p(k+k^{\prime})}\sum_{r}a^{pk}_{r}b^{pk^{\prime}}_{r^{\prime}}\mathbf{E}_{{\omega}}\left[{\frac{\lvert
Z_{j}\rvert^{2r}}{\lvert x_{j}\rvert^{2r}}\mid\mathcal{H}}\right]\enspace.$
(70)

It follows that the expectation term in the above equation is real and non-
negative.

Let $\mathbf{E}_{{h}}\left[{\cdot}\right]$ denote the expectation with respect
to the hash functions and $\mathbf{E}_{{\omega}}\left[{\cdot}\right]$ denote
the expectation with respect to the complex roots of unity sketches (i.e., the
remaining random bits). Substituting Eqn (70) in Eqn. ( ‣ A.4), we have,

$\displaystyle\mathbf{E}_{{\omega}}\left[{X_{j}^{pk}\overline{X_{j}}^{pk^{\prime}}\mid\mathcal{H}}\right]$
$\displaystyle=\lvert
x_{j}\rvert^{p(k+k^{\prime})}\sum_{r=0}^{\min(pk,pk^{\prime})}a_{r}^{pk}b_{r}^{pk^{\prime}}\mathbf{E}_{{\omega}}\left[{\frac{\lvert
Z_{j}\rvert^{2r}}{\lvert x_{j}\rvert^{2r}}}\right]\enspace.$

Substituting the above equation in Eqn. ( ‣ A.4), we have,

$\displaystyle\mathbf{E}\left[\left(\sum_{l\textsf{~{}consist.
with~{}}j}2^{l}z_{lj}X_{j}^{p}\right)^{k}\left(\sum_{l\textsf{~{}consist.
with~{}}j}2^{l}z_{jl}X_{j}^{p}\right)^{k^{\prime}}\right]$
$\displaystyle=\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{l(k+k^{\prime})}z_{lj}^{k+k^{\prime}}X_{j}^{pk}\overline{X_{j}}^{pk^{\prime}}\right]$
$\displaystyle=\lvert
x_{j}\rvert^{p(k+k^{\prime})}\sum_{r=0}^{\min(pk,pk^{\prime})}a_{r}^{pk}b_{r}^{pk^{\prime}}\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{l(k+k^{\prime})}z_{lj}^{k+k^{\prime}}\frac{\lvert
Z_{j}\rvert^{2r}}{\lvert x_{j}\rvert^{2r}}\right]\enspace.$

Substituting this equation in Eqn. ( ‣ A.4), we have,

$\displaystyle\mathbf{E}\left[(Y_{j}-\mathbf{E}\left[Y_{j}\mid\mathcal{H}\right])^{e_{j}}(\overline{Y_{j}}-\mathbf{E}\left[\overline{Y_{j}}\mid\mathcal{H}\right])^{g_{j}}\mid\mathcal{H}\right]$
$\displaystyle=\sum_{k,k^{\prime}=0,0}^{e_{j},g_{j}}c_{k}d_{k^{\prime}}\mathbf{E}\left[\left(\sum_{l\textsf{~{}consist.
with~{}}j}2^{l}z_{lj}X_{j}^{p}\right)^{k}\left(\sum_{l\textsf{~{}consist.
with~{}}j}2^{l}z_{jl}X_{j}^{p}\right)^{k^{\prime}}\mid\mathcal{H}\right]$
$\displaystyle\hskip 72.26999pt(-1)^{e_{j}+g_{j}-k-k^{\prime}}\lvert
x_{j}\rvert^{p(e_{j}+g_{j}-k-k^{\prime})}(1\pm\delta^{\prime})^{e_{j}+g_{j}-k-k^{\prime}}\enspace.$
$\displaystyle=\sum_{k,k^{\prime}=0,0}^{e_{j},g_{j}}c_{k}d_{k^{\prime}}\lvert
x_{j}\rvert^{p(k+k^{\prime})}\sum_{r=0}^{\min(pk,pk^{\prime})}a_{r}^{pk}b_{r}^{pk^{\prime}}\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{l(k+k^{\prime})}z_{lj}^{k+k^{\prime}}\frac{\lvert
Z_{j}\rvert^{2r}}{\lvert x_{j}\rvert^{2r}}\mid\mathcal{H}\right]$
$\displaystyle\hskip 72.26999pt(-1)^{e_{j}+g_{j}-k-k^{\prime}}\lvert
x_{j}\rvert^{p(e_{j}+g_{j}-k-k^{\prime})}(1\pm\delta^{\prime})^{e_{j}+g_{j}-k-k^{\prime}}\enspace.$
$\displaystyle=\lvert
x_{j}\rvert^{p(e_{j}+g_{j})}\sum_{k,k^{\prime}=0,0}^{e_{j},g_{j}}c_{k}d_{k^{\prime}}\sum_{r=0}^{\min(pk,pk^{\prime})}a_{r}^{pk}b_{r}^{pk^{\prime}}\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{l(k+k^{\prime})}z_{lj}^{k+k^{\prime}}\frac{\lvert
Z_{j}\rvert^{2r}}{\lvert x_{j}\rvert^{2r}}\mid\mathcal{H}\right]$
$\displaystyle\hskip
72.26999pt(-1)^{e_{j}+g_{j}-k-k^{\prime}}(1\pm\delta^{\prime})^{e_{j}+g_{j}-k-k^{\prime}}\enspace.$
(71)

Noting that the term in the expectation is always non-negative, replacing the
powers of -1 by 1 cannot decrease the _RHS_. Therefore, the _RHS_ of Eqn. ( ‣
A.4) is bounded above by

$\displaystyle\leq$ $\displaystyle(1+\delta)^{e_{j}+g_{j}}\lvert
x_{j}\rvert^{p(e_{j}+g_{j})}\sum_{k,k^{\prime}=0,0}^{e_{j},g_{j}}c_{k}d_{k^{\prime}}\sum_{r=0}^{\min(pk,pk^{\prime})}a_{r}^{pk}b_{r}^{pk^{\prime}}\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{l(k+k^{\prime})}z_{lj}^{k+k^{\prime}}\frac{\lvert
Z_{j}\rvert^{2r}}{\lvert x_{j}\rvert^{2r}}\mid\mathcal{H}\right]$
$\displaystyle=(1+\delta)^{e_{j}+g_{j}}\lvert
x_{j}\rvert^{p(e_{j}+g_{j})}\sum_{k,k^{\prime}=0,0}^{e_{j},g_{j}}c_{k}d_{k^{\prime}}\tau(k,k^{\prime}),$
(72)

where,

$\displaystyle\tau(k,k^{\prime})=\sum_{r=0}^{\min(pk,pk^{\prime})}a_{r}^{pk}b_{r}^{pk^{\prime}}\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{l(k+k^{\prime})}z_{lj}^{k+k^{\prime}}\frac{\lvert
Z_{j}\rvert^{2r}}{\lvert x_{j}\rvert^{2r}}\mid\mathcal{H}\right]\enspace.$
(73)

Repeating similar calculations, we obtain,

$\displaystyle\mathbf{E}\left[Y_{j}^{e_{j}}\overline{Y_{j}}^{g_{j}}\mid\mathcal{H}\right]$
$\displaystyle\geq(1-\delta^{\prime})^{e_{j}+g_{j}}\lvert
x_{j}\rvert^{p(e_{j}+g_{j})}\sum_{r=0}^{\min(e_{j},g_{j})}a_{r}^{pe_{j}}b_{r}^{pg_{j}}$
$\displaystyle\hskip 36.135pt\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{l(e_{j}+g_{j})}z_{lj}^{e_{j}+g_{j}}\frac{\lvert
Z_{j}\rvert^{2r}}{\lvert x_{j}\rvert^{2r}}\mid\mathcal{H}\right]$
$\displaystyle=(1-\delta^{\prime})^{e_{j}+g_{j}}\lvert
x_{j}\rvert^{p(e_{j}+g_{j})}\tau(e_{j},g_{j})\enspace.$ (74)

We now consider the $\tau$ function. Note that by definition, $\tau$ is a
symmetric function, that is, $\tau(k,k^{\prime})=\tau(k^{\prime},k)$. We wish
to show that $\tau$ is monotonic, that is, if $0\leq k\leq e_{j}$ and $0\leq
k^{\prime}\leq g_{j}$, then, $\tau(k,k^{\prime})\leq\tau(e_{j},g_{j})$. Assume
that $0\leq k\leq e_{j}$ and $0\leq k^{\prime}\leq g_{j}$.

_Case 1._ Suppose $k+k^{\prime}=0$, or, equivalently, $k=0$ and
$k^{\prime}=0$. Then, $\tau(k,k^{\prime})=1$. Further,

$\displaystyle\tau(e_{j},g_{j})$
$\displaystyle=\sum_{r=0}^{\min(pe_{j},pg_{j}^{\prime})}a_{r}^{pe_{j}}b_{r}^{pg_{j}}\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{l(e_{j}+g_{j})}z_{lj}^{e_{j}+g_{j}}\frac{\lvert
Z_{j}\rvert^{2r}}{\lvert x_{j}\rvert^{2r}}\mid\mathcal{H}\right]$
$\displaystyle=1+\sum_{r=1}^{\min(pe_{j},pg_{j}^{\prime})}a_{r}^{pe_{j}}b_{r}^{pg_{j}}\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{l(e_{j}+g_{j})}z_{lj}^{e_{j}+g_{j}}\frac{\lvert
Z_{j}\rvert^{2r}}{\lvert x_{j}\rvert^{2r}}\mid\mathcal{H}\right]$
$\displaystyle\geq 1=\tau(k,k^{\prime})\enspace.$

_Case 2._ Now suppose $k+k^{\prime}\geq 1$. We note that the function
$a_{r}^{n}=\binom{n}{r}$ is monotonic in the first argument, that is,
$\binom{n+1}{r}\geq\binom{n}{r}$. This follows since, for $r=0$, these two
terms are obviously equal to 1, and for $r>0$,

$\displaystyle\binom{n+1}{r}=\prod_{j=0}^{r-1}\frac{n+1-j}{j}>\prod_{j=0}^{r-1}\frac{n-j}{j}=\binom{n}{r}\enspace.$

Therefore,

$\displaystyle\tau(k,k^{\prime})$
$\displaystyle=\sum_{r=0}^{\min(pk,pk^{\prime})}\binom{pk}{r}\binom{pk^{\prime}}{r}\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{l(k+k^{\prime})}z_{lj}^{k+k^{\prime}}\frac{\lvert
Z_{j}\rvert^{2r}}{\lvert x_{j}\rvert^{2r}}\mid\mathcal{H}\right]$
$\displaystyle\leq\sum_{r=0}^{\min(pe_{j},pg_{j})}\binom{pe_{j}}{r}\binom{pe_{j}}{r}\mathbf{E}\left[\sum_{l\textsf{~{}consist.
with~{}}j}2^{l(e_{j}+g_{j})}z_{lj}^{e_{j}+g_{j}}\frac{\lvert
Z_{j}\rvert^{2r}}{\lvert x_{j}\rvert^{2r}}\mid\mathcal{H}\right]$
$\displaystyle=\tau(e_{j},g_{j})\enspace.$

The last step is obtained essentially by replacing each term in the expansion
of $\tau(k,k^{\prime})$ by a corresponding term that is a function of $e_{j}$
and $g_{j}$ and which is no smaller. First, the summation is extended from
$\min(pk,pk^{\prime})$ to $\min(pe_{j},pg_{j})$. Since the summation inside
are all non-negative terms, the replacement cannot make it smaller. Secondly,
the terms $\binom{pk}{r}$ and $\binom{pk^{\prime}}{r}$ are replaced by
$\binom{pe_{j}}{r}$ and $\binom{pg_{j}}{r}$ respectively, which are each no
smaller than its corresponding term. The term $2^{l(k+k^{\prime})}\leq
2^{l(e_{j}+g_{j})}$. Now $z_{lj}$ is an indicator variable, and for
$k+k^{\prime}\geq 1$, $z_{lj}=z_{lj}^{k+k^{\prime}}=z_{lj}^{e_{j}+g_{j}}$.

Thus, in all cases, $\tau$ is a monotonic function, that is, for $0\leq k\leq
e_{j}$ and $\tau(k,k^{\prime})\leq\tau(e_{j},g_{j})$.

Continuing from Eqn. ( ‣ A.4), we have,

$\displaystyle\mathbf{E}\left[(Y_{j}-\mathbf{E}\left[Y_{j}\mid\mathcal{H}\right])^{e_{j}}(\overline{Y_{j}}-\mathbf{E}\left[\overline{Y_{j}}\mid\mathcal{H}\right])^{g_{j}}\mid\mathcal{H}\right]$
$\displaystyle\leq(1+\delta^{\prime})^{e_{j}+g_{j}}\lvert
x_{j}\rvert^{p(e_{j}+g_{j})}\sum_{k,k^{\prime}=0,0}^{e_{j},g_{j}}c_{k}d_{k^{\prime}}\tau(k,k^{\prime})$
$\displaystyle=(1+\delta^{\prime})^{e_{j}+g_{j}}\lvert
x_{j}\rvert^{p(e_{j}+g_{j})}\tau(e_{j},g_{j})\sum_{k,k^{\prime}=0}^{e_{j},g_{j}}c_{k}d_{k^{\prime}}$
$\displaystyle=(1+\delta^{\prime})^{e_{j}+g_{j}}\lvert
x_{j}\rvert^{p(e_{j}+g_{j})}\tau(e_{j},g_{j})2^{e_{j}+g_{j}}$
$\displaystyle\left(\frac{2(1+\delta^{\prime})}{1-\delta^{\prime}}\right)^{e_{j}+g_{j}}\mathbf{E}\left[Y_{j}^{e_{j}}\overline{Y_{j}}^{g_{j}}\mid\mathcal{H}\right]$

Let $G^{\prime}=\text{lmargin}(G_{0})\cup_{l=1}^{L}G_{l}$. Recall that
$\mathcal{H}=\mathcal{G}\wedge\textsc{nocollision}\wedge\textsc{accuest}$.
Although, for the next lemma, it would suffice to condition on the event
$\mathcal{H}^{\prime}=\mathcal{G}\wedge\textsc{nocollision}(G^{\prime})\wedge\textsc{accuest}(G^{\prime})$.

######  Lemma 40 (Re-statement of Lemma 11.)

Let $B\geq Ln^{1-2/p}\epsilon^{-4/p}\log^{2/p}(1/\delta))$ for a suitable
constant $L$. Then, for integral $0\leq
d_{1},d_{2}\leq\lceil\log(1/\delta)\rceil$, we have,

$\mathbf{E}\biggl{[}\left(\sum_{i\in
G^{\prime}}(Y_{i}-\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right])\right)^{d_{1}}\left(\sum_{i\in
G^{\prime}}(\overline{Y_{i}}-\overline{\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right]})\right)^{d_{2}}\bigg{|}\mathcal{H}\biggr{]}\leq\left(\frac{\epsilon
F_{p}}{20}\right)^{d_{1}+d_{2}}\enspace.$

  * Proof:  For $d_{1}+d_{2}=0$, that is, $d_{1}=0$ and $d_{2}=0$, the statement of the lemma is vacuously true. If $d_{1}+d_{2}=1$, then, say $d_{1}=1$, then,

$\displaystyle\mathbf{E}\left[\sum_{i\in
S}(Y_{i}-\mathbf{E}\left[Y_{i}\right])\right]=\sum_{i\in S}\lvert
x_{i}\rvert^{p}n^{-\Omega(1)}=F_{p}n^{-\Omega(1)}$

implying the statement of the Lemma.

We therefore assume that $d_{1}+d_{2}>1$. Using the notation that
$S_{1}=\\{i_{1},\ldots,i_{r}\\}$ and $S_{2}=\\{j_{1},\ldots,j_{t}\\}$, we can
rewrite the summation by using three subsets: $T_{1}=S_{1}\cap S_{2}$,
$T_{2}=S_{1}\setminus S_{2}$ and $T_{3}=S_{2}\setminus S_{1}$, where, $\lvert
T_{1}\rvert=r,\lvert T_{2}\rvert=s$ and $\lvert T_{3}\rvert=t$. Without loss
of generality, let $d_{1}\leq d_{2}$—the other case is symmetric.

Then, the summation may be written as

$\displaystyle\mathbf{E}\left[\left.\left(\sum_{i\in
S}(Y_{i}-\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right])\right)^{d_{1}}\left(\sum_{i\in
S}(\overline{Y_{i}}-\overline{\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right]})\right)^{d_{2}}\right|\mathcal{H}\right]$
$\displaystyle=\sum_{r=0}^{d_{1}}\sum_{s=\max(0,1-r)}^{d_{1}-r}\sum_{t=\max(0,1-r)}^{d_{2}-r}\sum_{a=0}^{s}\sum_{b=0}^{t}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{r+s}=d_{1}\\\
e_{1},\ldots,e_{r+s}\geq 1\\\
\bigl{\lvert}\\{j\in[s]:e_{r+j}=1\\}\bigr{\rvert}=a\\\
A=\\{j\in[s]:e_{r+j}=1\\}\end{subarray}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{r+t}=d_{2}\\\
\text{ $g_{j}^{\prime}s\geq 1$}\\\
\bigl{\lvert}\\{j:g_{r+j}=1\\}\bigr{\rvert}=b\\\
B=\\{k\in[t]:g_{r+k}=1\\}\end{subarray}}\binom{d_{1}}{e_{1},\ldots,e_{r+s}}$
$\displaystyle~{}~{}~{}\binom{d_{2}}{g_{1},\ldots,g_{r+t}}\sum_{\begin{subarray}{c}\\{i_{1},\ldots,i_{r},j_{1},\ldots,j_{s},k_{1},\ldots,k_{t}\\}\end{subarray}}\mathbf{E}\left[\prod_{v\in
A}(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}\right])\prod_{w\in
B}(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}\right])\right.$
$\displaystyle\hskip
108.405pt\prod_{u=1}^{r}(Y_{i_{u}}-\mathbf{E}\left[Y_{i_{u}}\mid\mathcal{H}\right])^{e_{u}}(\overline{Y_{i_{u}}}-\mathbf{E}\left[\overline{Y_{i_{u}}}\right])^{g_{u}}$
$\displaystyle\hskip 72.26999pt\left.\left.\prod_{v\in[s]\setminus
A}(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}\right])^{e_{r+v}}\prod_{w\in[t]\setminus
B}(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}\right])^{g_{r+w}}\right|\mathcal{H}\right]$

Let $\gamma=n^{-\Omega(1)}$. Using Lemma 33, we have,

$\displaystyle\mathbf{E}\left[\prod_{v\in
A}(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}\right])\prod_{w\in
B}(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}\right])\prod_{u=1}^{r}(Y_{i_{u}}-\mathbf{E}\left[Y_{i_{u}}\mid\mathcal{H}\right])^{e_{u}}(\overline{Y_{i_{u}}}-\mathbf{E}\left[\overline{Y_{i_{u}}}\mid\mathcal{H}\right])^{g_{u}}\right.$
$\displaystyle\left.\left.\prod_{v\in[s]\setminus
A}(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}\right])^{e_{r+v}}\prod_{w\in[t]\setminus
B}(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}\right])^{g_{r+w}}\right|\mathcal{H}\right]$
$\displaystyle\leq\gamma^{a+b}\prod_{v\in A}\lvert
x_{j_{v}}\rvert^{p}\prod_{w\in B}\lvert
x_{k_{w}}\rvert^{p}\mathbf{E}\left[\prod_{u=1}^{r}(Y_{i_{u}}-\mathbf{E}\left[Y_{i_{u}}\mid\mathcal{H}\right])^{e_{u}}(\overline{Y_{i_{u}}}-\mathbf{E}\left[\overline{Y_{i_{u}}}\mid\mathcal{H}\right])^{g_{u}}\right.$
$\displaystyle\hskip 36.135pt\left.\left.\prod_{v\in[s]\setminus
A}(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}\right])^{e_{r+v}}\prod_{w\in[t]\setminus
B}(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}\right])^{g_{r+w}}\right|\mathcal{H}\right]$
$\displaystyle=\gamma^{a+b}\prod_{v\in A}\lvert x_{j_{v}}\rvert^{p}\prod_{w\in
B}\lvert
x_{k_{w}}\rvert^{p}\prod_{u=1}^{r}\mathbf{E}\left[(Y_{i_{u}}-\mathbf{E}\left[Y_{i_{u}}\right])^{e_{u}}(\overline{Y_{i_{u}}}-\mathbf{E}\left[\overline{Y_{i_{u}}}\right])^{g_{u}}\mid\mathcal{H}\right]$
$\displaystyle\hskip 36.135pt\prod_{v\in[s]\setminus
A}\mathbf{E}\left[(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}\right])^{e_{r+v}}\mid\mathcal{H}\right]\prod_{w\in[t]\setminus
B}\mathbf{E}\left[(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}\right])^{g_{r+w}}\mid\mathcal{H}\right]\enspace.$
(76)

We will now use Lemma 39, which states that, for $e_{j},g_{j}\geq 0$,

$\mathbf{E}\left[(Y_{j}-\mathbf{E}\left[Y_{j}\mid\mathcal{H}\right])^{e_{j}}(\overline{Y_{j}}-\mathbf{E}\left[\overline{Y_{j}}\mid\mathcal{H}\right])^{g_{j}}\mid\mathcal{H}\right]\leq\left(2\left(\frac{1+\delta^{\prime}}{1-\delta^{\prime}}\right)\right)^{e_{j}+g_{j}}\mathbf{E}\left[Y_{j}^{e_{j}}\overline{Y_{j}}^{g_{j}}\right]$

where, $\delta^{\prime}=n^{-\Omega(1)}$.

Note that for $\delta^{\prime}=n^{-\Omega(1)}$, where, the constant term in
$\Omega(1)$ can be made as large as needed by choosing the parameter of width
of hash tables appropriately, and since, $e_{j}+g_{j}\leq\log(1/\delta)\leq
n^{2/p}$, it follows that
$\left(\frac{1+\delta^{\prime}}{1-\delta^{\prime}}\right)^{e_{j}+g_{j}}\leq
1+\delta^{\prime\prime}$, where, $\delta^{\prime\prime}=n^{-\Omega(1)}$ for a
different constant in $\Omega(1)$. Also,
$(1+\delta^{\prime\prime})^{\lceil\log(1/\delta)\rceil}\leq 2$, which we will
use below.

Substituting in Eqn. ( ‣ A.4), we have,

$\displaystyle\mathbf{E}\left[\prod_{v\in
A}(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}\right])\prod_{w\in
B}(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}\right])\prod_{u=1}^{r}(Y_{i_{u}}-\mathbf{E}\left[Y_{i_{u}}\mid\mathcal{H}\right])^{e_{u}}(\overline{Y_{i_{u}}}-\mathbf{E}\left[\overline{Y_{i_{u}}}\mid\mathcal{H}\right])^{g_{u}}\right.$
$\displaystyle\left.\left.\prod_{v\in[s]\setminus
A}(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}\right])^{e_{r+v}}\prod_{w\in[t]\setminus
B}(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}\right])^{g_{r+w}}\right|\mathcal{H}\right]$
$\displaystyle\leq\gamma^{a+b}\prod_{v\in A}\lvert
x_{j_{v}}\rvert^{p}\prod_{w\in B}\lvert x_{k_{w}}\rvert^{p}\cdot(2)\cdot
2^{\sum_{u=1}^{r}(e_{u}+g_{u})+\sum_{v\in[s]}e_{r+v}+\sum_{w\in[t]}g_{r+w}}$
$\displaystyle\hskip
36.135pt\prod_{u=1}^{r}\mathbf{E}\left[Y_{i_{u}}^{e_{u}}\overline{Y_{i_{u}}}^{g_{u}}\mid\mathcal{H}\right]\prod_{v\in[s]\setminus
A}\mathbf{E}\left[Y_{j_{v}}^{e_{r+v}}\mid\mathcal{H}\right]\prod_{w\in[t]\setminus
B}\mathbf{E}\left[\overline{Y_{k_{w}}}^{g_{r+w}}\mid\mathcal{H}\right]\enspace.$

Now, the sum of the exponents in the power of 2 in the above expression is
$d_{1}+d_{2}-a-b$. Thus, the above equation becomes,

$\displaystyle\mathbf{E}\left[\prod_{v\in
A}(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}\right])\prod_{w\in
B}(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}\right])\prod_{u=1}^{r}(Y_{i_{u}}-\mathbf{E}\left[Y_{i_{u}}\mid\mathcal{H}\right])^{e_{u}}(\overline{Y_{i_{u}}}-\mathbf{E}\left[\overline{Y_{i_{u}}}\mid\mathcal{H}\right])^{g_{u}}\right.$
$\displaystyle\left.\prod_{v\in[s]\setminus
A}(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}\right])^{e_{r+v}}\prod_{w\in[t]\setminus
B}(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}\right])^{g_{r+w}}|\mathcal{H}\right]$
$\displaystyle\leq\gamma^{a+b}2^{d_{1}+d_{2}-a-b+1}\prod_{v\in A}\lvert
x_{j_{v}}\rvert^{p}\prod_{w\in B}\lvert
x_{k_{w}}\rvert^{p}\prod_{u=1}^{r}\mathbf{E}\left[Y_{i_{u}}^{e_{u}}\overline{Y_{i_{u}}}^{g_{u}}\mid\mathcal{H}\right]\prod_{v\in[s]\setminus
A}\mathbf{E}\left[Y_{j_{v}}^{e_{r+v}}\mid\mathcal{H}\right]$
$\displaystyle\hskip 216.81pt\prod_{w\in[t]\setminus
B}\mathbf{E}\left[\overline{Y_{k_{w}}}^{g_{r+w}}\mid\mathcal{H}\right]$
$\displaystyle=\gamma^{a+b}2^{d_{1}+d_{2}-a-b+1}\prod_{v\in A}\lvert
x_{j_{v}}\rvert^{p}\prod_{w\in B}\lvert
x_{k_{w}}\rvert^{p}\mathbf{E}\left[\prod_{u=1}^{r}Y_{i_{u}}^{e_{u}}\overline{Y_{i_{u}}}^{g_{u}}\prod_{v\in[s]\setminus
A}Y_{j_{v}}^{e_{r+v}}\prod_{w\in[t]\setminus
B}\overline{Y_{k_{w}}}^{g_{r+w}}\mid\mathcal{H}\right],$ (77)

where we have used the fact that
$\sum_{u=1}^{r}(e_{u}+g_{u})+\sum_{v=1}^{s}e_{r+v}+\sum_{w=1}^{t}g_{r+w}=d_{1}+d_{2}$.

By Lemma 35, we have, for $e_{1},\ldots,e_{r},g_{1},\ldots,g_{r}\geq 1$ and
$e_{r+1},\ldots,e_{r+t}\geq 2$ and $g_{r+1},\ldots,g_{r+t}\geq 2$, that

$\displaystyle\mathbf{E}\left[\prod_{u=1}^{r}Y_{i_{u}}^{e_{u}}\overline{Y_{i_{u}}}^{g_{u}}\prod_{v\in[s]}Y_{j_{v}}^{e_{r+v}}\prod_{w\in[t]}\overline{Y_{k_{w}}}^{g_{r+v}}|\mathcal{H}\right]$
$\displaystyle\leq 2e^{\sum_{u\in[r]}(e_{u}+g_{u})/8}\prod_{u=1}^{r}\lvert
x_{i_{u}}\rvert^{p}\prod_{v=1}^{s}\lvert
x_{j_{v}}\rvert^{p}\prod_{w=1}^{t}\lvert x_{k_{w}}\rvert^{p}$
$\displaystyle\hskip
36.135pt\left(\frac{4F_{2}}{B}\right)^{(p/2)\left(\sum_{u=1}^{r}(e_{u}+g_{u}-1)+\sum_{v\in[s]}(e_{r+v}-1)+\sum_{w\in[t]}(e_{r+w}-1)\right)}$
$\displaystyle\leq 2e^{(d_{1}+d_{2})/8}\prod_{u=1}^{r}\lvert
x_{i_{u}}\rvert^{p}\prod_{v\in[s]}\lvert
x_{j_{v}}\rvert^{p}\prod_{w\in[t]}\lvert
x_{k_{w}}\rvert^{p}\left(\frac{4F_{2}}{B}\right)^{(p/2)(d_{1}+d_{2}-r-s-t-
a-b)}$ (78)

using the fact that
$\sum_{u=1}^{r}(e_{u}+g_{u})+\sum_{v=1}^{s}e_{r+v}+\sum_{w=1}^{t}g_{r+w}=d_{1}+d_{2}$.

Substituting Eqn ( ‣ A.4) in Eqn. ( ‣ A.4) we have,

$\displaystyle\mathbf{E}\left[\prod_{v\in
A}(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}\right])\prod_{w\in
B}(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}\right])\prod_{u=1}^{r}(Y_{i_{u}}-\mathbf{E}\left[Y_{i_{u}}\mid\mathcal{H}\right])^{e_{u}}(\overline{Y_{i_{u}}}-\mathbf{E}\left[\overline{Y_{i_{u}}}\mid\mathcal{H}\right])^{g_{u}}\right.$
$\displaystyle\left.\left.\prod_{v\in[s]\setminus
A}(Y_{j_{v}}-\mathbf{E}\left[Y_{j_{v}}\mid\mathcal{H}\right])^{e_{r+v}}\prod_{w\in[t]\setminus
B}(\overline{Y_{k_{w}}}-\mathbf{E}\left[\overline{Y_{k_{w}}}\mid\mathcal{H}\right])^{g_{r+w}}\right|\mathcal{H}\right]$
$\displaystyle\leq
4\gamma^{a+b}2^{d_{1}+d_{2}}e^{(d_{1}+d_{2})/8}\prod_{u=1}^{r}\lvert
x_{i_{u}}\rvert^{p}\prod_{v\in[s]}\lvert
x_{j_{v}}\rvert^{p}\prod_{w\in[t]}\lvert
x_{k_{w}}\rvert^{p}\left(\frac{4F_{2}}{B}\right)^{(p/2)(d_{1}+d_{2}-r-s-t-
a-b)}$ (79)

Substituting Eqn. ( ‣ A.4) in Eqn. (LABEL:eq:dmomc), we have,

$\displaystyle\mathbf{E}\left[\left.\left(\sum_{i\in
S}(Y_{i}-\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right])\right)^{d_{1}}\left(\sum_{i\in
S}(\overline{Y_{i}}-\overline{\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right]})\right)^{d_{2}}\right|\mathcal{H}\right]$
$\displaystyle\leq 4\cdot
2^{d_{1}+d_{2}}e^{(d_{1}+d_{2})/8}\sum_{r=0}^{d_{1}}\sum_{s=\max(0,1-r)}^{d_{1}-r}\sum_{t=\max(0,1-r)}^{d_{2}-r}\sum_{a=0}^{s}\sum_{b=0}^{t}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{r+s}=d_{1}\\\
e_{1},\ldots,e_{r+s}\geq 1\\\
\bigl{\lvert}\\{j\in[s]:e_{r+j}=1\\}\bigr{\rvert}=a\end{subarray}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{r+t}=d_{2}\\\
\text{ $g_{j}^{\prime}s\geq 1$}\\\
\bigl{\lvert}\\{j:g_{r+j}=1\\}\bigr{\rvert}=b\end{subarray}}$
$\displaystyle~{}~{}\binom{d_{1}}{e_{1},\ldots,e_{r+s}}\binom{d_{2}}{g_{1},\ldots,g_{r+t}}\sum_{\begin{subarray}{c}\\{i_{1},\ldots,i_{r},j_{1},\ldots
j_{s},k_{1},\ldots,k_{t}\\}\end{subarray}}\gamma^{a+b}\prod_{u=1}^{r}\lvert
x_{i_{u}}\rvert^{p}\prod_{v\in[s]}\lvert
x_{j_{v}}\rvert^{p}\prod_{w\in[t]}\lvert x_{k_{w}}\rvert^{p}$
$\displaystyle\hskip
72.26999pt\left(\frac{4F_{2}}{B}\right)^{(p/2)(d_{1}+d_{2}-r-s-t-a-b)}$
$\displaystyle\leq
2\left(\frac{8e^{1/(4p)}F_{2}}{B}\right)^{(p/2)(d_{1}+d_{2})}\sum_{r=0}^{d_{1}}\sum_{s=\max(0,1-r)}^{\lfloor(d_{1}-r)\rfloor}\sum_{t=\max(0,1-r)}^{\lfloor(d_{2}-r)\rfloor}\sum_{a=0}^{s}\sum_{b=0}^{t}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{r+s}=d_{1}\\\
e_{1},\ldots,e_{r+s}\geq 1\\\
\bigl{\lvert}\\{j\in[s]:e_{r+j}=1\\}\bigr{\rvert}=a\end{subarray}}$
$\displaystyle\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{r+t}=d_{2}\\\ \text{
$g_{j}^{\prime}s\geq 1$}\\\
\bigl{\lvert}\\{j:g_{r+j}=1\\}\bigr{\rvert}=b\end{subarray}}\binom{d_{1}}{e_{1},\ldots,e_{r+s}}\binom{d_{2}}{g_{1},\ldots,g_{r+t}}\frac{\gamma^{a+b}F_{p}^{r+s+t}}{(4F_{2}/B)^{(p/2)(r+s+t+a+b)}(r+s+t)!}$
$\displaystyle\leq
2\left(\frac{8e^{1/(4p)}F_{2}}{B}\right)^{(p/2)(d_{1}+d_{2})}\sum_{r=0}^{d_{1}}\sum_{s=\max(0,1-r)}^{d_{1}-r}\sum_{t=\max(0,1-r)}^{d_{2}-r}\frac{F_{p}^{r+s+t}}{(4F_{2}/B)^{(p/2)(r+s+t)}(r+s+t)!}$
$\displaystyle\sum_{a=0}^{s}\sum_{b=0}^{t}\frac{\gamma^{a+b}}{(4F_{2}/B)^{(p/2)(a+b)}}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{r+s}=d_{1}\\\
e_{1},\ldots,e_{r+s}\geq 1\\\
\bigl{\lvert}\\{j\in[s]:e_{r+j}=1\\}\bigr{\rvert}=a\end{subarray}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{r+t}=d_{2}\\\
\text{ $g_{j}^{\prime}s\geq 1$}\\\
\bigl{\lvert}\\{j:g_{r+j}=1\\}\bigr{\rvert}=b\end{subarray}}\binom{d_{1}}{e_{1},\ldots,e_{r+s}}\binom{d_{2}}{g_{1},\ldots,g_{r+t}}1$
(80)

Fix $r,s,t,a$ and $b$ as per the constraints, and consider the inner
summation. Given the vectors $e_{1},\ldots,e_{r+s}$ and
$g_{1},\ldots,g_{r+t}$, define the vectors
$e^{\prime}_{1},\ldots,e^{\prime}_{r+s}$ and
$g^{\prime}_{1},\ldots,g^{\prime}_{r+s}$ as follows. $e^{\prime}_{j}=e_{j}-1$,
for $j\in[r]$, $e^{\prime}_{r+j}=e_{r+j}-2$, for $j\in[t]$ and $e_{r+j}\neq
1$, and $e^{\prime}_{r+j}=0$, if $e_{r+j}=1$. Similarly, the $r+t$-dimensional
vector $g^{\prime}$ is defined. Therefore,

$\displaystyle\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{r+s}=d_{1}\\\
e_{1},\ldots,e_{r+s}\geq 1\\\
\bigl{\lvert}\\{j\in[s]:e_{r+j}=1\\}\bigr{\rvert}=a\end{subarray}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{r+t}=d_{2}\\\
\text{ $g_{j}^{\prime}s\geq 1$}\\\
\bigl{\lvert}\\{j:g_{r+j}=1\\}\bigr{\rvert}=b\end{subarray}}\binom{d_{1}}{e_{1},\ldots,e_{r+s}}\binom{d_{2}}{g_{1},\ldots,g_{r+t}}1$
$\displaystyle=\Biggl{(}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{r+s}=d_{1}\\\
e_{1},\ldots,e_{r+s}\geq 1\\\
\bigl{\lvert}\\{j\in[s]:e_{r+j}=1\\}\bigr{\rvert}=a\end{subarray}}\binom{d_{1}}{e_{1},\ldots,e_{r+s}}1\Biggr{)}\Biggl{(}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{r+t}=d_{1}\\\
\text{ $g_{j}^{\prime}s\geq 1$}\\\
\bigl{\lvert}\\{j:g_{r+j}=1\\}\bigr{\rvert}=b\end{subarray}}\binom{d_{2}}{g_{1},\ldots,g_{r+t}}1\Biggr{)}$
$\displaystyle\leq\Biggl{(}d_{1}^{r+a+2(s-a)}\sum_{\begin{subarray}{c}e^{\prime}_{1}+\ldots
e^{\prime}_{r+s}=d-(r+2s-a)\\\
\bigl{\lvert}\\{j:e^{\prime}_{r+j}=0\\}\bigr{\rvert}=a\end{subarray}}\binom{d_{1}-(r+2s-a)}{e^{\prime}_{1},\ldots,e^{\prime}_{r+s}}\Biggr{)}$
$\displaystyle\hskip
36.135pt\Biggl{(}d_{2}^{r+b+2(t-b)}\sum_{\begin{subarray}{c}g^{\prime}_{1}+\ldots
g^{\prime}_{r+t}=d_{2}-(r+2t-b)\\\
\bigl{\lvert}\\{j:g^{\prime}_{r+j}=0\\}\bigr{\rvert}=b\end{subarray}}\binom{d_{2}-(r+2t-b)}{g^{\prime}_{1},\ldots,g^{\prime}_{r+t}}\Biggr{)}$
(81)

Now,

$\displaystyle\sum_{\begin{subarray}{c}e^{\prime}_{1}+\ldots
e^{\prime}_{r+s}=d_{1}-(r+2s-a)\\\
\bigl{\lvert}\\{j:e^{\prime}_{r+j}=0\\}\bigr{\rvert}=a\end{subarray}}$
$\displaystyle\binom{d_{1}-(r+2s-a)}{e^{\prime}_{1},\ldots,e^{\prime}_{r+s}}$
$\displaystyle=\binom{r+s}{a}\sum_{\begin{subarray}{c}f_{1}+\ldots,f_{r+s-a}=d_{1}-(r+2s-a)\end{subarray}}\binom{d_{1}-(r+2s-a)}{f_{1},\ldots,f_{r+s-a}}$
$\displaystyle=\binom{r+s}{a}(r+s-a)^{d_{1}-(r+2s-a)}$
$\displaystyle\leq\frac{(r+s)^{d_{1}-(r+2s-a)+a}}{a!}$

Similarly,

$\displaystyle\sum_{\begin{subarray}{c}g^{\prime}_{1}+\ldots
g^{\prime}_{r+t}=d_{2}-(r+2t-b)\\\
\bigl{\lvert}\\{j:g^{\prime}_{r+j}=0\\}\bigr{\rvert}=b\end{subarray}}\binom{d_{2}-(r+2t-b)}{g^{\prime}_{1},\ldots,g^{\prime}_{r+t}}\leq\frac{(r+t)^{d_{2}-(r+2t-b)+b}}{b!}\enspace.$

Substituting in ( ‣ A.4), we have

$\displaystyle\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{r+s}=d_{1}\\\
e_{1},\ldots,e_{r+s}\geq 1\\\
\bigl{\lvert}\\{j\in[s]:e_{r+j}=1\\}\bigr{\rvert}=a\end{subarray}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{r+t}=d_{2}\\\
\text{ $g_{j}^{\prime}s\geq 1$}\\\
\bigl{\lvert}\\{j:g_{r+j}=1\\}\bigr{\rvert}=b\end{subarray}}\binom{d_{1}}{e_{1},\ldots,e_{r+s}}\binom{d_{2}}{g_{1},\ldots,g_{r+t}}1$
$\displaystyle\leq\left(\frac{1}{a!b!}\right)d_{1}^{r+2s-a}d_{2}^{r+2t-b}(r+s)^{d_{1}-r-2s+2a}(r+t)^{d_{2}-r-2t+2b}$

Therefore,

$\displaystyle\sum_{a=0}^{s}\sum_{b=0}^{t}\frac{\gamma^{a+b}}{(4F_{2}/B)^{(p/2)(a+b)}}$
$\displaystyle\hskip
21.68121pt\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{r+s}=d\\\
e_{1},\ldots,e_{r+s}\geq 1\\\
\bigl{\lvert}\\{j\in[s]:e_{r+j}=1\\}\bigr{\rvert}=a\end{subarray}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{r+t}=d\\\
\text{ $g_{j}^{\prime}s\geq 1$}\\\
\bigl{\lvert}\\{j:g_{r+j}=1\\}\bigr{\rvert}=b\end{subarray}}\binom{d}{e_{1},\ldots,e_{r+s}}\binom{d}{g_{1},\ldots,g_{r+t}}1$
$\displaystyle\leq
d_{1}^{r+2s}d_{2}^{r+2t}(r+s)^{d_{1}-r-2s}(r+t)^{d_{2}-r-2t}\sum_{a=0}^{s}\sum_{b=0}^{t}\left(\frac{\gamma}{(4F_{2}/B)^{p/2}}\right)^{a+b}$
$\displaystyle\hskip
108.405pt\left(\frac{(r+s)^{2a}(r+t)^{2b}}{d_{1}^{a}d_{2}^{b}}\right)$
$\displaystyle=d_{1}^{r+2s}d_{2}^{r+2t}(r+s)^{d_{1}-r-2s}(r+t)^{d_{2}-r-2t}\left(\sum_{a=0}^{s}\left(\frac{\gamma(r+s)^{2}}{d_{1}(4F_{2}/B)^{(p/2)}}\right)^{a}\right)$
$\displaystyle\hskip
108.405pt\left(\sum_{b=0}^{t}\left(\frac{\gamma(r+s)^{2}}{d_{2}(4F_{2}/B)^{p/2}}\right)^{b}\right)$
$\displaystyle\leq
d_{1}^{r+2s}d_{2}^{r+2t}(r+s)^{d_{1}-r-2s}(r+t)^{d_{2}-r-2t}\left(1+\gamma^{\prime}\right)\left(1+\gamma^{\prime}\right)$
(82) $\displaystyle\leq
2d_{1}^{r+2s}d_{2}^{r+2t}(r+s)^{d_{1}-r-2s}(r+t)^{d_{2}-r-2t}\enspace.$
$\displaystyle\leq 2d_{2}^{2r+2s+2t}(r+s+t)^{d_{1}+d_{2}-2r-2s-2t}$ (83)

Eqn. (82) is obtained from the previous step as follows. Let

$\gamma^{\prime}=2\max\left(\frac{\gamma(r+s)^{2}}{d_{1}(4F_{2}/B)^{p/2}},\frac{\gamma(r+s)^{2}}{d_{2}(4F_{2}/B)^{p/2}}\right)\enspace.$

Then, $\gamma^{\prime}=O(\gamma(d_{1}+d_{2})^{2})=n^{-\Omega(1)}$ and

$\sum_{a=0}^{s}\left(\frac{\gamma(r+s)^{2}}{d_{1}(4F_{2}/B)^{(p/2)}}\right)^{a}\leq
1+\gamma^{\prime},\text{ and
}\sum_{b=0}^{s}\left(\frac{\gamma(r+s)^{2}}{d_{2}(4F_{2}/B)^{(p/2)}}\right)^{b}\leq
1+\gamma^{\prime}\enspace.$

The last step, that is, Eqn. (83) is obtained from its previous equation as
follows. (1)
$\displaystyle(r+s)^{d_{1}-r-2s}(r+t)^{d_{2}-r-2s}\leq(r+s+t)^{d_{1}-r-2s}(r+s+t)^{d_{2}-r-2t}=(r+s+t)^{d_{1}+d_{2}-2r-2s-2t}$,
and (2) by assumption, $d_{1}\leq d_{2}$.

Substituting Eqn. (83) in Eqn. ( ‣ A.4), we have,

$\displaystyle\mathbf{E}\left[\left.\left(\sum_{i\in
S}(Y_{i}-\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right])\right)^{d_{1}}\left(\sum_{i\in
S}(\overline{Y_{i}}-\overline{\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right]})\right)^{d_{2}}\right|\mathcal{H}\right]$
$\displaystyle\leq
2^{d_{1}+d_{2}+2}e^{(d_{1}+d_{2})/8}\left(\frac{4F_{2}}{B}\right)^{(p/2)(d_{1}+d_{2})}\sum_{r=0}^{d_{1}}\sum_{s=\max(0,1-r)}^{d_{1}-r}\sum_{t=\max(0,1-r)}^{d_{2}-r}\frac{F_{p}^{r+s+t}}{(4F_{2}/B)^{(p/2)(r+s+t)}(r+s+t)!}$
$\displaystyle\hskip
14.22636pt\sum_{a=0}^{s}\sum_{b=0}^{t}\frac{\gamma^{a+b}}{(4F_{2}/B)^{(p/2)(a+b)}}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{r+s}=d_{1}\\\
e_{1},\ldots,e_{r+s}\geq 1\\\
\bigl{\lvert}\\{j\in[s]:e_{r+j}=1\\}\bigr{\rvert}=a\end{subarray}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{r+t}=d_{2}\\\
\text{ $g_{j}^{\prime}s\geq 1$}\\\
\bigl{\lvert}\\{j:g_{r+j}=1\\}\bigr{\rvert}=b\end{subarray}}\binom{d_{1}}{e_{1},\ldots,e_{r+s}}\binom{d_{2}}{g_{1},\ldots,g_{r+t}}1$
$\displaystyle\leq
2^{2}\left(\frac{8e^{1/(4p)}F_{2}}{B}\right)^{(p/2)(d_{1}+d_{2})}\sum_{r=0}^{d_{1}}\sum_{s=\max(0,1-r)}^{d_{1}-r}\sum_{t=\max(0,1-r)}^{d_{2}-r}\frac{F_{p}^{r+s+t}}{(4F_{2}/B)^{(p/2)(r+s+t)}(r+s+t)!}$
$\displaystyle\hskip
36.135ptd_{2}^{2r+2s+2t}(r+s+t)^{d_{1}+d_{2}-2r-2s-2t}\enspace.$ (84)

Letting $u=r+s+t$ in Eqn. (84), we obtain,

$\displaystyle\leq
2^{2}\left(\frac{8e^{1/(4p)}F_{2}}{B}\right)^{(p/2)(d_{1}+d_{2})}\sum_{u=1}^{\lfloor(d_{1}+d_{2})/2\rfloor}\left(\frac{F_{p}^{u}}{(4F_{2}/B)^{(p/2)u}u!}\right)d_{2}^{2u}u^{d_{1}+d_{2}-2u}$
(85)

since, $2r+2s+2t\leq d_{1}+d_{2}$ and therefore,
$u=r+s+t\leq\lfloor(d_{1}+d_{2})/2\rfloor$.

Taking ratio of the $u+1$st term to the $u$th term in the summation in Eqn.
(85), we have,

$\displaystyle\frac{F_{p}}{(4F_{2}/B)^{(p/2)}}\cdot\frac{d_{2}^{2}}{(u+1)^{3}}\cdot(1+1/u)^{d_{1}+d_{2}-2u}\geq\frac{F_{p}}{(4F_{2}/B)^{(p/2)}}\cdot\frac{d_{2}^{2}}{(u+1)^{3}}$

Since, $F_{2}\leq n^{1-2/p}F_{p}^{2/p}$ and $B\geq Kn^{1-2/p}d_{2}^{2/p}$, it
follows that

$\frac{F_{p}}{(4F_{2}/B)^{(p/2)}}\geq(K/4)^{p/2}d_{2}\enspace.$

Therefore, the ratio of $u+1$st term to the $u$th term is at least

$\displaystyle\frac{F_{p}}{(4F_{2}/B)^{(p/2)}}\cdot\frac{d_{2}^{2}}{(u+1)^{3}}\geq\frac{(K/4)^{p/2}d_{2}^{3}}{(u+1)^{3}}\geq
2$

for $K\geq 8$ since, $d_{2}\geq\lfloor d_{1}+d_{2}\rfloor/2\geq u+1$.

Therefore, the series
$\displaystyle\sum_{u=1}^{\lfloor(d_{1}+d_{2})/2\rfloor}\left(\frac{F_{p}^{u}}{(4F_{2}/B)^{u}u!}\right)d_{2}^{2u}u^{d_{1}+d_{2}-2u}$
is bounded above by twice the last term, that is,

$\displaystyle\sum_{u=1}^{\lfloor(d_{1}+d_{2})/2\rfloor}\left(\frac{F_{p}^{u}}{(4F_{2}/B)^{u}u!}\right)d_{2}^{2u}u^{d_{1}+d_{2}-2u}$
$\displaystyle\leq(2)\left(\frac{F_{p}^{\lfloor(d_{1}+d_{2})/2\rfloor}}{(4F_{2}/B)^{\lfloor(d_{1}+d_{2})/2\rfloor}(\lfloor(d_{1}+d_{2})/2\rfloor!)}\right)d_{2}^{2\lfloor(d_{1}+d_{2})/2\rfloor}$
$\displaystyle\hskip
108.405pt\left(\lfloor(d_{1}+d_{2})/2\rfloor\right)^{d_{1}+d_{2}-2\lfloor(d_{1}+d_{2})/2\rfloor}$
(86)

Substituting in Eqn. (85), we obtain

$\displaystyle\mathbf{E}\left[\left.\left(\sum_{i\in
S}(Y_{i}-\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right])\right)^{d_{1}}\left(\sum_{i\in
S}(\overline{Y_{i}}-\overline{\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right]})\right)^{d_{2}}\right|\mathcal{H}\right]$
$\displaystyle\leq
2^{3}e^{(d_{1}+d_{2})/8}\left(\frac{8F_{2}}{B}\right)^{(p/2)(d_{1}+d_{2})}\left(\frac{F_{p}^{\lfloor(d_{1}+d_{2})/2\rfloor}}{(4F_{2}/B)^{\lfloor(d_{1}+d_{2})/2\rfloor}(\lfloor(d_{1}+d_{2})/2\rfloor!)}\right)d_{2}^{2\lfloor(d_{1}+d_{2})/2\rfloor}$
$\displaystyle\hskip
72.26999pt\left(\lfloor(d_{1}+d_{2})/2\rfloor\right)^{d_{1}+d_{2}-2\lfloor(d_{1}+d_{2})/2\rfloor}$
$\displaystyle\leq
2^{3}e^{(d_{1}+d_{2})/8}\left(\frac{8F_{2}}{B}\right)^{(p/2)\left((d_{1}+d_{2})-\lfloor(d_{1}+d_{2})/2\rfloor\right)}F_{p}^{\lfloor(d_{1}+d_{2})/2\rfloor}$
$\displaystyle\hskip
36.135pt\frac{d_{2}^{2\lfloor(d_{1}+d_{2})/2\rfloor}}{\lfloor(d_{1}+d_{2})/2\rfloor!}\left(\lfloor(d_{1}+d_{2})/2\rfloor\right)^{d_{1}+d_{2}-2\lfloor(d_{1}+d_{2})/2\rfloor}$
(87)

By Stirling’s approximation, that is, $\displaystyle n!>(2\pi
n)^{1/2}\left(\frac{n}{e}\right)^{n}$, we have
$\displaystyle\lfloor(d_{1}+d_{2})/2\rfloor!>(2\pi\lfloor(d_{1}+d_{2})/2\rfloor))^{1/2}\left(\frac{\lfloor(d_{1}+d_{2})/2\rfloor}{e}\right)^{\lfloor(d_{1}+d_{2})/2\rfloor}$.

Since, $d_{1}+d_{2}>1$, and we have assumed that $d_{2}\geq d_{1}$, $d_{2}\leq
3\lfloor(d_{1}+d_{2})/2\rfloor$. Therefore,

$\displaystyle\frac{d_{2}^{2\lfloor(d_{1}+d_{2})/2\rfloor}}{\lfloor(d_{1}+d_{2})/2\rfloor!}$
$\displaystyle\leq(3\sqrt{e})^{d_{1}+d_{2}}\left(\frac{\left(\lfloor(d_{1}+d_{2})/2\rfloor\right)^{2\lfloor(d_{1}+d_{2})/2\rfloor}}{\sqrt{2\pi}\left(\lfloor(d_{1}+d_{2})/2\rfloor\right)^{\lfloor(d_{1}+d_{2})/2\rfloor+1/2}}\right)$
$\displaystyle=(2\pi)^{-1/2}(3\sqrt{e})^{d_{1}+d_{2}}\left(\lfloor(d_{1}+d_{2})/2\rfloor\right)^{\lfloor(d_{1}+d_{2})/2\rfloor-1/2}$
(88)

The term
$\left(\lfloor(d_{1}+d_{2})/2\rfloor\right)^{d_{1}+d_{2}-2\lfloor(d_{1}+d_{2})/2\rfloor}$
in Eqn. (A.4) is 1 if $d_{1}+d_{2}$ is odd and is
$\lfloor(d_{1}+d_{2})/2\rfloor$ if $d_{1}+d_{2}$ is even. We write this as the
indicator variable
$\displaystyle\lfloor(d_{1}+d_{2})/2\rfloor^{\textbf{1}_{d_{1}+d_{2}\text{ odd
}}}$.

Using this and substituting Eqn. (88) into Eqn. (A.4), we have,

$\displaystyle\mathbf{E}\left[\left.\left(\sum_{i\in
S}(Y_{i}-\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right])\right)^{d_{1}}\left(\sum_{i\in
S}(\overline{Y_{i}}-\overline{\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right]})\right)^{d_{2}}\right|\mathcal{H}\right]$
$\displaystyle\leq
2^{3}e^{(d_{1}+d_{2})/8}\left(\frac{8F_{2}}{B}\right)^{(p/2)\left((d_{1}+d_{2})-\lfloor(d_{1}+d_{2})/2\rfloor\right)}F_{p}^{\lfloor(d_{1}+d_{2})/2\rfloor}$
$\displaystyle\hskip
72.26999pt\frac{d_{2}^{2\lfloor(d_{1}+d_{2})/2\rfloor}}{\lfloor(d_{1}+d_{2})/2\rfloor!}\left(\lfloor(d_{1}+d_{2})/2\rfloor\right)^{d_{1}+d_{2}-2\lfloor(d_{1}+d_{2})/2\rfloor}$
$\displaystyle\leq
2^{3}e^{(d_{1}+d_{2})/8}(2\pi)^{-1/2}(3\sqrt{e})^{d_{1}+d_{2}}\left(\frac{8F_{2}}{B}\right)^{(p/2)\lceil(d_{1}+d_{2})/2\rceil}F_{p}^{\lfloor(d_{1}+d_{2})/2\rfloor}$
$\displaystyle\hskip
72.26999pt\left(\lfloor(d_{1}+d_{2})/2\rfloor\right)^{\lfloor(d_{1}+d_{2})/2\rfloor-1/2+\textbf{1}_{d_{1}+d_{2}\text{
odd}}}$ $\displaystyle\leq 2^{3}\left(3\cdot
e\right)^{d_{1}+d_{2}}\left(\frac{8F_{2}}{B}\right)^{(p/2)\lceil(d_{1}+d_{2})/2\rceil}F_{p}^{\lfloor(d_{1}+d_{2})/2\rfloor}\left(\lfloor(d_{1}+d_{2})/2\rfloor\right)^{(d_{1}+d_{2})/2}$
(89)

Now, $B\geq Ln^{1-2/p}\epsilon^{-4/p}\log^{2/p}(1/\delta)$, for an appropriate
constant $L\geq(2^{3})^{2/p}\cdot\left((8\cdot 20)(3e)\right)^{4/p}$. Using
$F_{2}\leq n^{1-2/p}F_{p}^{2/p}$, we have,

$\displaystyle\left(2^{6/p}(3e)^{2}\cdot\frac{8F_{2}}{B}\right)^{p/2}\leq\frac{\epsilon^{2}F_{p}}{400\lceil\log(1/\delta)\rceil}$

Therefore, assuming $d_{1}+d_{2}\geq 1$, Eqn. (89) is bounded above by

$\displaystyle
2^{3}\left(3e\right)^{d_{1}+d_{2}}\left(\frac{8F_{2}}{B}\right)^{(p/2)\lceil(d_{1}+d_{2})/2\rceil}F_{p}^{\lfloor(d_{1}+d_{2})/2\rfloor}\left(\lfloor(d_{1}+d_{2})/2\rfloor\right)^{(d_{1}+d_{2})/2}$
$\displaystyle\leq\left(\lfloor(d_{1}+d_{2})/2\rfloor\right)^{(d_{1}+d_{2})/2}\left(\frac{\epsilon^{2}F_{p}}{400\lceil\log(1/\delta)\rceil}\right)^{\lceil(d_{1}+d_{2})/2\rceil}F_{p}^{\lfloor(d_{1}+d_{2})/2\rfloor}$
$\displaystyle\leq\left(\frac{\epsilon
F_{p}}{20}\right)^{d_{1}+d_{2}}\enspace.$

Here, the last step uses that, (i)
$\lfloor(d_{1}+d_{2})/2\rfloor\leq\lceil\log(1/\delta)\rceil$, (ii)
$\epsilon^{2\lceil(d_{1}+d_{2})/2\rceil}\leq\epsilon^{d_{1}+d_{2}}$, and
(iii)
$F_{p}^{\lfloor(d_{1}+d_{2})/2\rfloor+\lceil(d_{1}+d_{2})/2\rceil}=F_{p}^{d_{1}+d_{2}}$.

###  A.5  Analysis of contribution to $d$th moment from items in
$\text{mid}(G_{0})$

Recall that $\mathcal{H}$ denotes the event
$\mathcal{G}\wedge\textsc{nocollision}\wedge\textsc{goodest}$.

######  Lemma 41 (Re-stated (expanded) version of Lemma 12.)

Let $1\leq e,g\leq\lceil\log(1/\delta)\rceil$ and $l\in\text{mid}(G_{0})$.
Assume $C\geq 72p^{2}B$ and $\lvert
x_{l}\rvert\geq\left(\frac{F_{2}^{\text{res}}\left({C}\right)}{B}\right)^{1/2}$.
Let the family $\\{\omega_{lr}(i)\\}_{i\in[n]}$ be $O(k)$-wise independent
where, $k\geq O(\log(1/\delta)+\log n)$. Then,
$\displaystyle\mathbf{E}\left[\left(\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{e}\left(\left(1+\frac{\overline{Z_{l}}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{g}\mid\mathcal{H}\right]$ is real and

$\displaystyle 0\leq\mathbf{E}\left[\left(\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{e}\left(\left(1+\frac{\overline{Z_{l}}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{g}\mid\mathcal{H}\right]\leq\left(\frac{7p^{2}(e+g)F_{2}^{\text{res}}\left({C}\right)}{\rho
C\lvert x_{l}\rvert^{2}}\right)^{(e+g)/2}\enspace.$

It follows that,

$\displaystyle\mathbf{E}\left[\left(Y_{l}-\mathbf{E}\left[Y_{l}\mid\mathcal{H}\right]\right)^{e}\left(\overline{Y_{l}}-\mathbf{E}\left[\overline{Y_{l}}\mid\mathcal{H}\right]\right)^{g}\mid\mathcal{H}\right]\leq\left(\frac{8p^{2}\lvert
x_{l}\rvert^{2p-2}F_{2}^{\text{res}}\left({C}\right)}{\rho
C}\right)^{(e+g)/2}\enspace.$

  * Proof:  Let $c_{r}=\binom{p}{r}$, for $r\geq 0$. Since, $\frac{\lvert Z_{l}\rvert}{\lvert x_{l}\rvert}\leq 1/8$, the binomial series expansion of $\left(1+\frac{Z_{l}}{\lvert x_{l}\rvert}\right)^{p}$ holds as the power series $\sum_{r\geq 0}c_{r}\left(\frac{Z_{l}}{\lvert x_{l}\rvert}\right)^{r}$. For the first part of the proof, we will assume full independence of the family $\\{\omega_{lr}(i)\\}_{i\in[n]}$, for $l=0$ and $r\in[2s]$ so that we can use the above binomial expansion.

$\displaystyle\mathbf{E}\left[\left(\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{e}\left(\left(1+\frac{\overline{Z_{l}}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{g}\mid\mathcal{H}\right]$
$\displaystyle=\mathbf{E}\left[\left(\sum_{r\geq
1}c_{r}\left(\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{r}\right)^{e}\left(\sum_{s\geq
1}c_{s}\left(\frac{\overline{Z_{l}}}{\lvert
x_{l}\rvert}\right)^{s}\right)^{g}\mid\mathcal{H}\right]$
$\displaystyle=\mathbf{E}\left[\left(\frac{c_{1}Z_{l}}{\lvert
x_{l}\rvert}\right)^{e}\left(\frac{c_{1}\overline{Z_{l}}}{\lvert
x_{l}\rvert}\right)^{g}\left(\sum_{r\geq
1}\frac{c_{r}}{c_{1}}\left(\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{r-1}\right)^{e}\left(\sum_{s\geq
1}\frac{c_{s}}{c_{1}}\left(\frac{\overline{Z_{l}}}{\lvert
x_{l}\rvert}\right)^{s-1}\right)^{g}\mid\mathcal{H}\right]$
$\displaystyle=\sum_{a_{1}+\ldots+a_{k}+\ldots=e}\sum_{b_{1}+\ldots+b_{k}+\ldots=g}c_{1}^{e+g}\prod_{r\geq
1}\left(\frac{c_{r}}{c_{1}}\right)^{a_{r}}\prod_{s\geq
1}\left(\frac{c_{s}}{c_{1}}\right)^{b_{s}}$ $\displaystyle\hskip
72.26999pt\mathbf{E}\left[\cfrac{Z_{l}^{e+\sum_{r\geq
1}(r-1)a_{r}}\overline{Z_{l}}^{g+\sum_{s\geq 1}(s-1)b_{s}}}{\lvert
x_{l}\rvert^{\sum_{r\geq 1}(r-1)a_{r}+\sum_{s\geq
1}(s-1)b_{r}}}\mid\mathcal{H}\right]$ (90)

Consider the term $\displaystyle\mathbf{E}\left[\frac{Z_{l}^{e+\sum_{r\geq
1}(r-1)a_{r}}\overline{Z_{l}}^{g+\sum_{s\geq 1}(s-1)b_{s}}}{\lvert
x_{l}\rvert^{\sum_{r\geq 1}(r-1)a_{r}+\sum_{s\geq
1}(s-1)b_{r}}}\mid\mathcal{H}\right]$. Subject to the constraint that
$a_{1}+\ldots+a_{k}+\ldots=e$ and $b_{1}+\ldots+b_{k}+\ldots=g$, we have,
$e+\sum_{r\geq 1}(r-1)a_{r}=\sum_{r\geq 1}ra_{r}$ and $g+\sum_{s\geq
1}(s-1)b_{s}=\sum_{s\geq 1}sb_{s}$. Hence,

$\displaystyle\mathbf{E}\left[Z_{l}^{e+\sum_{r\geq
1}(r-1)a_{r}}\overline{Z_{l}}^{g+\sum_{s\geq
1}(s-1)b_{s}}\mid\mathcal{H}\right]=\mathbf{E}\left[Z_{l}^{\sum_{r\geq
1}ra_{r}}\overline{Z_{l}}^{\sum_{s\geq 1}sb_{s}}\mid\mathcal{H}\right]$

This expectation is 0 if $\sum_{r\geq 1}ra_{r}\neq\sum_{s\geq 1}sb_{s}$.
Therefore,

$\displaystyle\mathbf{E}\left[\left(\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{e}\left(\left(1+\frac{\overline{Z_{l}}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{g}\mid\mathcal{H}\right]$
$\displaystyle=\sum_{a_{1}+\ldots+a_{k}+\ldots=e}\sum_{\begin{subarray}{c}b_{1}+\ldots+b_{k}+\ldots=g\\\
\sum_{r\geq 1}ra_{r}=\sum_{s\geq
1}sb_{s}\end{subarray}}c_{1}^{e+g}\prod_{r\geq
1}\left(\frac{c_{r}}{c_{1}}\right)^{a_{r}}\prod_{s\geq
1}\left(\frac{c_{s}}{c_{1}}\right)^{b_{s}}\frac{\mathbf{E}\left[(Z\overline{Z})^{\sum_{r\geq
1}ra_{r}}\mid\mathcal{H}\right]}{\lvert x_{l}\rvert^{2\sum_{r\geq 1}ra_{r}}}$
(91)

From Eqn. ( ‣ A.5), it follows that the _RHS_ is a real number, and therefore
the expectation in the _LHS_ is real.

For non-zero expectation, assuming $\sum_{r\geq 1}ra_{r}=\sum_{s\geq
1}sb_{s}$, we have,

$\displaystyle 0\leq\frac{\mathbf{E}\left[(Z_{l}\overline{Z_{l}})^{\sum_{r\geq
1}ra_{r}}\mid\mathcal{H}\right]}{\lvert x_{l}\rvert^{2\sum_{r\geq 1}ra_{r}}}$
$\displaystyle\leq\frac{\mathbf{E}\left[(Z_{l}\overline{Z_{l}})^{(e+g)/2}\mid\mathcal{H}\right]}{\lvert
x_{l}\rvert^{e+g}}\left(\frac{\lvert Z_{l}\rvert}{\lvert
x_{l}\rvert}\right)^{2(\sum_{r\geq 1}ra_{r})-(e+g)}$ $\displaystyle\leq\lvert
x_{l}\rvert^{-(e+g)}\left(\frac{(e+g)F_{2}^{\text{res}}\left({C}\right)}{2(\rho/9)C}\right)^{(e+g)/2}\varrho^{2(\sum_{r\geq
1}ra_{r})-(e+g)}$

where, $\varrho=(B/C)^{1/2}$. Note that conditional on goodest, $\lvert
Z_{l}\rvert/\lvert x_{l}\rvert\leq\rho$.

Substituting, and noting that $c_{1}=\binom{p}{1}=p$, the sum in Eqn. (90) is
bounded above as follows.

$\displaystyle\sum_{a_{1}+\ldots+a_{k}+\ldots=e}\sum_{b_{1}+\ldots+b_{k}+\ldots=g}c_{1}^{e+g}\prod_{r\geq
1}\left(\frac{c_{r}}{c_{1}}\right)^{a_{r}}\prod_{s\geq
1}\left(\frac{c_{s}}{c_{1}}\right)^{b_{s}}$ $\displaystyle\hskip
72.26999pt\mathbf{E}\left[\cfrac{Z_{l}^{e+\sum_{r\geq
1}(r-1)a_{r}}\overline{Z_{l}}^{g+\sum_{s\geq 1}(s-1)b_{s}}}{\lvert
x_{l}\rvert^{\sum_{r\geq 1}(r-1)a_{r}+\sum_{s\geq
1}(s-1)b_{r}}}\mid\mathcal{H}\right]$ $\displaystyle\leq\lvert
x_{l}\rvert^{-(e+g)}\left(\frac{c_{1}^{2}(e+g)F_{2}^{\text{res}}\left({C}\right)}{2(\rho/9)C}\right)^{(e+g)/2}$
$\displaystyle\hskip
14.22636pt\sum_{a_{1}+\ldots+a_{k}+\ldots=e}\sum_{\begin{subarray}{c}b_{1}+\ldots+b_{k}+\ldots=g\\\
\sum_{r\geq 1}ra_{r}=\sum_{s\geq 1}sb_{s}\end{subarray}}\prod_{r\geq
1}\left(\frac{\lvert c_{r}\rvert}{c_{1}}\right)^{a_{r}}\prod_{s\geq
1}\left(\frac{\lvert c_{s}\rvert}{c_{1}}\right)^{b_{s}}\varrho^{2(\sum_{r\geq
1}ra_{r})-(e+g)}$ $\displaystyle\leq\lvert
x_{l}\rvert^{-(e+g)}\left(\frac{c_{1}^{2}(e+g)F_{2}^{\text{res}}\left({C}\right)}{2(\rho/9)C}\right)^{(e+g)/2}$
$\displaystyle\hskip
14.22636pt\sum_{a_{1}+\ldots+a_{k}+\ldots=e}\sum_{\begin{subarray}{c}b_{1}+\ldots+b_{k}+\ldots=g\end{subarray}}\prod_{r\geq
1}\left(\frac{\lvert c_{r}\rvert}{c_{1}}\right)^{a_{r}}\prod_{s\geq
1}\left(\frac{\lvert
c_{s}\rvert}{c_{1}}\right)^{b_{s}}\varrho^{\left(\sum_{r\geq
1}ra_{r}+\sum_{s\geq 1}sb_{s}\right)-(e+g)}$ (92)

Using, $\sum_{r\geq 1}a_{r}=e$ and $\sum_{s\geq 1}b_{s}=g$, we have,
$\left(\sum_{r\geq 1}ra_{r}+\sum_{s\geq 1}sb_{s}\right)-(e+g)=\sum_{r\geq
1}(r-1)a_{r}+\sum_{s\geq 1}(s-1)b_{s}$. Therefore, Eqn. (92) equals

$\displaystyle\lvert
x_{l}\rvert^{-(e+g)}\left(\frac{c_{1}^{2}(e+g)F_{2}^{\text{res}}\left({C}\right)}{2(\rho/9)C}\right)^{(e+g)/2}\left(\sum_{r\geq
1}\frac{\lvert c_{r}\rvert}{c_{1}}\varrho^{r-1}\right)^{e}\left(\sum_{s\geq
1}\frac{\lvert c_{s}\rvert}{c_{1}}\varrho^{s-1}\right)^{g}$ (93)

The ratio of the $(r+1)$th term to the $r$th term in the summation
$\sum_{r\geq 1}\frac{\lvert c_{r}\rvert}{c_{1}}\varrho^{r-1}$ , for
$r=1,2,\ldots,k-1$ is

$\displaystyle\left\lvert\frac{c_{r+1}}{c_{r}}\right\rvert\varrho=\frac{\lvert
p-r\rvert\varrho}{r+1}\leq\frac{1}{8}$

since, $\varrho=(B/C)^{1/2}\leq 1/(8p)$. Therefore, $\sum_{r\geq
1}\frac{\lvert c_{r}\rvert}{c_{1}}\varrho^{r-1}\leq\sum_{r\geq
1}(1/8)^{r-1}\leq(9/8)$.

The summation in Eqn. (93) is therefore bounded above by (since, $c_{1}=p$)

$\displaystyle\mathbf{E}\left[\left(\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{e}\left(\left(1+\frac{\overline{Z_{l}}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{g}\mid\mathcal{H}\right]$
$\displaystyle\leq\lvert
x_{l}\rvert^{-(e+g)}\left(\frac{((9/8)p)^{2}(e+g)F_{2}^{\text{res}}\left({C}\right)}{2(\rho/9)C}\right)^{(e+g)/2}$
$\displaystyle\leq\left(\frac{6p^{2}(e+g)F_{2}^{\text{res}}\left({C}\right)}{\lvert
x_{l}\rvert^{2}\rho C}\right)^{(e+g)/2}\enspace.$ (94)

Proceeding similarly, we show that for any $k\geq 1$,
$\displaystyle\mathbf{E}\left[\left(\sum_{r=1}^{k}c_{r}\frac{Z_{l}^{r}}{\lvert
x_{l}\rvert^{r}}\right)^{e}\left(\sum_{s=1}^{k}c_{s}\frac{\overline{Z_{l}}^{s}}{\lvert
x_{l}\rvert^{r}}\right)^{g}\mid\mathcal{H}\right]$ is real and

$\displaystyle
0\leq\mathbf{E}\left[\left(\sum_{r=1}^{k}c_{r}\frac{Z_{l}^{r}}{\lvert
x_{l}\rvert^{r}}\right)^{e}\left(\sum_{s=1}^{k}c_{s}\frac{\overline{Z_{l}}^{s}}{\lvert
x_{l}\rvert^{r}}\right)^{g}\right]\leq\left(\frac{6p^{2}(e+g)F_{2}^{\text{res}}\left({C}\right)}{\lvert
x_{l}\rvert^{2}\rho C}\right)^{(e+g)/2}\enspace.$ (95)

_Using $k$-wise independence._ Let $k=\Omega(\log n)$ be a parameter to be
determined and assume that the family $\\{\omega_{lr}(i)\\}_{i\in[n]}$ is at
least $k$-wise independent. With probability $1-n^{-\Omega(1)}$, $\lvert
Z_{l}\rvert\leq\left(\frac{F_{2}^{\text{res}}\left({C}\right)}{C}\right)^{1/2}$.
Therefore, $\displaystyle\frac{\lvert
Z_{l}\rvert}{x_{l}}\leq\left(\frac{F_{2}^{\text{res}}\left({C}\right)}{\lvert
x_{l}\rvert^{2}C}\right)^{1/2}$. By Taylor’s series expansion up to $k$ terms,
we have, $\displaystyle\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}=\sum_{r=0}^{k-1}c_{r}\frac{Z_{l}^{r}}{\lvert
x_{l}\rvert^{r}}+\gamma_{k}$, where,
$\displaystyle\gamma_{k}=c_{k}\frac{Z_{l}^{{}^{\prime}k}}{\lvert
x_{l}\rvert^{k}}$ and $\lvert Z^{\prime}_{l}\rvert\leq\lvert Z_{l}\rvert$. By
the above discussion, we have,
$\displaystyle\lvert\gamma_{k}\rvert=\frac{\lvert
c_{k}Z_{l}^{{}^{\prime}k}\rvert}{\lvert
x_{l}\rvert^{k}}\leq\left\lvert\binom{p}{k}\right\rvert\left(\frac{F_{2}^{\text{res}}\left({C}\right)}{\lvert
x_{l}\rvert^{2}C}\right)^{k/2}=\zeta$ (say).

In the remainder of the proof, _all expectations are conditional on_
$\mathcal{H}$.

Let $\alpha_{k}$ denote the sum of the first $k-1$ terms in the Taylor series
expansion of $\left(1+\frac{Z_{l}}{\lvert x_{l}\rvert}\right)^{p}$ except for
the zeroth term, that is,

$\displaystyle\alpha_{k}=\sum_{r=1}^{k-1}c_{r}\frac{Z_{l}^{r}}{\lvert
x_{l}\rvert^{r}}\enspace.$

Hence, $\displaystyle\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}-1=\alpha_{k}+\gamma_{k}$. Let
$\beta_{k}=\overline{\alpha_{k}}$ and so that
$\displaystyle\left(1+\frac{\overline{Z_{l}}}{\lvert
x_{l}\rvert}\right)^{p}-1=\beta_{k}+\overline{\gamma_{k}}$. Therefore,

$\displaystyle\mathbf{E}\left[\left(\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{e}\left(\left(1+\frac{\overline{Z_{l}}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{g}\right]=\mathbf{E}\left[\left(\alpha_{k}+\gamma_{k}\right)^{e}\left(\beta_{k}+\overline{\gamma_{k}}\right)^{g}\right]\enspace.$

Let $d_{r}=\binom{e}{r}$, for $r=0,1,\ldots,e$ and $h_{s}=\binom{g}{s}$, for
$s=0,1,\ldots,g$. Therefore,

$\displaystyle\mathbf{E}\left[\left(\alpha_{k}+\gamma_{k}\right)^{e}\left(\beta_{k}+\overline{\gamma_{k}}\right)^{g}\right]$
$\displaystyle=\mathbf{E}\left[\left(\sum_{r=0}^{e}d_{r}\alpha_{k}^{e-r}\gamma_{k}^{r}\right)\left(\sum_{s=0}^{g}h_{s}\beta_{k}^{g-s}\overline{\gamma_{k}}^{s}\right)\right]$
$\displaystyle=\mathbf{E}\left[\alpha_{k}^{e}\beta_{k}^{g}\right]+\sum_{\begin{subarray}{c}r=0\ldots
e,s=0\ldots g\\\ r+s\geq
1\end{subarray}}d_{r}h_{s}\mathbf{E}\left[\alpha_{k}^{e-r}\beta_{k}^{g-s}\gamma_{k}^{r}\overline{\gamma_{k}}^{s}\right]\enspace.$
(96)

By Eqn. ( ‣ A.5), the _LHS_ of Eqn. (A.5) is non-negative and real.

By Eqn. (95),
$\displaystyle\mathbf{E}\left[\alpha_{k}^{e}\beta_{k}^{g}\right]$ is non-
negative, real and
$\displaystyle\mathbf{E}\left[\alpha_{k}^{e}\beta_{k}^{g}\right]\leq\left(\frac{6p^{2}(e+g)F_{2}^{\text{res}}\left({C}\right)}{\lvert
x_{l}\rvert^{2}\rho C}\right)^{(e+g)/2}$.

We now consider the term
$\mathbf{E}\left[\alpha_{k}^{e-r}\beta_{k}^{g-s}\gamma_{k}^{r}\overline{\gamma_{k}}^{s}\right]$.
Note that

$\displaystyle\lvert\alpha_{k}\rvert$ $\displaystyle\leq\sum_{r=1}^{k-1}\lvert
c_{r}\rvert\frac{\lvert Z_{l}\rvert^{r}}{\lvert
x_{l}\rvert^{r}}\leq\sum_{r=1}^{k-1}\bigl{\lvert}\binom{p}{r}\bigr{\rvert}\frac{1}{(8p)^{r}}\enspace.$

The ratio of the $r+1$st term to the $r$th term in the above summation is,
$\displaystyle\frac{\lvert p-r\rvert}{r+1}\cdot\frac{1}{8p}\leq 1/8$. Thus,
$\lvert\alpha_{k}\rvert\leq\displaystyle\sum_{r=1}^{k-1}\bigl{\lvert}\binom{p}{r}\bigr{\rvert}\frac{1}{(8p)^{r}}\leq\left(\frac{p}{8p}\right)\sum_{r=1}^{k-1}(1/8)^{r-1}=(1/7)$.
Hence,
$\lvert\beta_{k}\rvert=\lvert\overline{\alpha_{k}}\rvert=\lvert\alpha_{k}\rvert\leq
1/7$.

Substituting in Eqn. (A.5) and taking absolute values, we obtain,

$\displaystyle 0\leq$
$\displaystyle\mathbf{E}\left[\left(\alpha_{k}+\gamma_{k}\right)^{e}\left(\beta_{k}+\overline{\gamma_{k}}\right)^{g}\right]$
$\displaystyle\leq\mathbf{E}\left[\alpha_{k}^{e}\beta_{k}^{g}\right]+\sum_{\begin{subarray}{c}r=0\ldots
e,s=0\ldots g\\\ r+s\geq
1\end{subarray}}d_{r}h_{s}\lvert\alpha_{k}\rvert^{e-r}\lvert\beta_{k}\rvert^{g-s}\zeta_{k}^{r+s}$
$\displaystyle\leq\left(\frac{6p^{2}(e+g)F_{2}^{\text{res}}\left({C}\right)}{\lvert
x_{l}\rvert^{2}\rho C}\right)^{(e+g)/2}+\sum_{\begin{subarray}{c}r=0\ldots
e,s=0\ldots g\\\ r+s\geq
1\end{subarray}}d_{r}h_{s}(1/7)^{e+g-r-s}\zeta_{k}^{r+s}\enspace.$ (97)

We now consider the summation term in Eqn. (A.5). Then,

$\displaystyle\sum_{\begin{subarray}{c}r=0\ldots e,s=0\ldots g\\\ r+s\geq
1\end{subarray}}d_{r}h_{s}(1/7)^{e+g-r-s}\zeta_{k}^{r+s}$
$\displaystyle=(1/7)^{e+g}\sum_{s=1}^{g}h_{s}(7\zeta_{k})^{s}+(1/7)^{e+g}\sum_{r=1}^{e}d_{r}(7\zeta_{k})^{r}\sum_{s=0}^{g}h_{s}(7\zeta_{k})^{s}\enspace.$
(98)

Consider the summation $\sum_{s=1}^{g}h_{s}(7\zeta_{k})^{s}$. The ratio of the
$s+1$th term to the $s$th term, for $s=1,2,\ldots,g-1$, is
$\displaystyle\left(\frac{h_{s+1}}{h_{s}}\right)(7\zeta_{k})\leq
7g\zeta_{k}/2=n^{-\Omega(1)}$. Thus,

$\sum_{s=1}^{g}h_{s}(7\zeta_{k})^{s}\leq
h_{1}(7\zeta_{k})\sum_{s=1}^{g}(7g\zeta_{k}/2)^{s-1}=7g\zeta_{k}(1+O(g\zeta_{k}))\leq
8g\zeta_{k}\enspace.$

We now consider the second (double)-summation in Eqn. (A.5), namely,
$\displaystyle\sum_{r=1}^{e}d_{r}(7\zeta_{k})^{r}\sum_{s=0}^{g}h_{s}(7\zeta_{k})^{s}$.
Proceeding as in the previous paragraph, this is at most $8e\zeta_{k}$. The
second summation,
$\sum_{s=0}^{g}h_{s}(7\zeta_{k})^{s}=(1+7\zeta_{k})^{g}\leq\textrm{exp}\left\\{{7\zeta_{k}g}\right\\}\leq
1+8g\zeta_{k}$, since, $g=O(\log(1/\zeta))$ and $\zeta_{k}=n^{-\Omega(1)}$.
Therefore,
$\displaystyle\sum_{r=1}^{e}d_{r}(7\zeta_{k})^{r}\sum_{s=0}^{g}h_{s}(7\zeta_{k})^{s}\leq
8e\zeta_{k}(1+8g\zeta_{k})$.

Substituting in Eqn. (A.5), we have,

$\displaystyle(1/7)^{e+g}\sum_{s=1}^{g}h_{s}(7\zeta_{k})^{s}+(1/7)^{e+g}\sum_{r=1}^{e}d_{r}(7\zeta_{k})^{r}\sum_{s=0}^{g}h_{s}(7\zeta_{k})^{s}$
$\displaystyle\leq(1/7)^{e+g}(9)\zeta_{k}(e+g)$
$\displaystyle\leq(9)(e+g)(1/7)^{e+g}\left(\frac{F_{2}^{\text{res}}\left({C}\right)}{\lvert
x_{l}\rvert^{2}C}\right)^{k/2}\enspace.$ (99)

Substituting in Eqn. (A.5), we have,

$\displaystyle\mathbf{E}\left[\left(\alpha_{k}+\gamma_{k}\right)^{e}\left(\beta_{k}+\overline{\gamma_{k}}\right)^{g}\right]$
$\displaystyle\leq\left(\frac{6p^{2}(e+g)F_{2}^{\text{res}}\left({C}\right)}{\lvert
x_{l}\rvert^{2}\rho
C}\right)^{(e+g)/2}+(9)(e+g)(1/7)^{e+g}\left(\frac{F_{2}^{\text{res}}\left({C}\right)}{\lvert
x_{l}\rvert^{2}C}\right)^{k/2}$
$\displaystyle=\left(\frac{6p^{2}(e+g)F_{2}^{\text{res}}\left({C}\right)}{\lvert
x_{l}\rvert^{2}\rho C}\right)^{(e+g)/2}$ $\displaystyle\hskip
36.135pt\cdot\left(1+9(e+g)\left(\frac{\rho}{6(7p)^{2}(e+g)}\right)^{(e+g)/2}\left(\frac{F_{2}^{\text{res}}\left({C}\right)}{\lvert
x_{l}\rvert^{2}C}\right)^{(k-(e+g))/2}\right)\enspace.$ (100)

Let $d=2\lceil\log(1/\delta)\rceil$, so that $e+g\leq d$. Then,

$\displaystyle
9(e+g)\left(\frac{\rho}{6(7p)^{2}(e+g)}\right)^{(e+g)/2}=\textrm{exp}\left\\{{\ln(9(e+g))+\left(\frac{e+g}{2}\right)\ln\left(\frac{\rho}{6(7p)^{2}(e+g)}\right)}\right\\}\enspace.$
(101)

The function $x\ln\frac{\rho}{ax}$ attains a maximum at $x=\frac{\rho}{ea}$
and the maximum value is $\frac{\rho}{\textrm{exp}\left\\{{1}\right\\}a}$.
Thus, the _RHS_ in Eqn. (101) is bounded above by
$\displaystyle\textrm{exp}\left\\{{\ln(9d)+\frac{\rho}{\left(\textrm{exp}\left\\{{1}\right\\}\right)6(7p)^{2}}}\right\\}$.
Further,

$\displaystyle\left(\frac{F_{2}^{\text{res}}\left({C}\right)}{\lvert
x_{l}\rvert^{2}C}\right)^{(k-(e+g))/2}\leq\left(\frac{1}{8p}\right)^{(k-(e+g))/2}$
$\displaystyle=\textrm{exp}\left\\{{-(\ln(8p))(k-(e+g)/2)}\right\\}$
$\displaystyle\leq\textrm{exp}\left\\{{-2-\left(\ln(9d)+\frac{\rho}{\left(\textrm{exp}\left\\{{1}\right\\}\right)6(7p)^{2}}\right)}\right\\},$

provided, $\displaystyle k\geq
d+\left(\frac{1}{\ln(8p)}\right)\left(2+\left(\ln(9d)+\frac{\rho}{\left(\textrm{exp}\left\\{{1}\right\\}\right)6(7p)^{2}}\right)\right)=O(\log(1/\delta)+\log
n)$, since, $\rho=O(\log n)$.

Under this condition,

$\displaystyle
9(e+g)\left(\frac{\rho}{6(7p)^{2}(e+g)}\right)^{(e+g)/2}\left(\frac{F_{2}^{\text{res}}\left({C}\right)}{\lvert
x_{l}\rvert^{2}C}\right)^{(k-(e+g))/2}\leq e^{-2}\enspace.$

Substituting in Eqn. (A.5), we obtain

$\displaystyle\mathbf{E}\left[\left(\alpha_{k}+\gamma_{k}\right)^{e}\left(\beta_{k}+\overline{\gamma_{k}}\right)^{g}\right]$
$\displaystyle\leq\left(\frac{6p^{2}(e+g)F_{2}^{\text{res}}\left({C}\right)}{\lvert
x_{l}\rvert^{2}\rho C}\right)^{(e+g)/2}\left(1+e^{-2}\right)$
$\displaystyle\leq\left(\frac{7p^{2}(e+g)F_{2}^{\text{res}}\left({C}\right)}{\lvert
x_{l}\rvert^{2}\rho C}\right)^{(e+g)/2}$ (102)

This proves the first statement of the lemma.

For the second statement of the lemma, $Y_{l}=\lvert
x_{l}\rvert^{p}\left(1+\frac{Z_{l}}{\lvert x_{l}\rvert}\right)^{p}$. Using
$k$-wise independence of the $\omega_{lr}$’s family of random roots of unity,
and since, $\lvert Z_{i}\rvert/\lvert x_{i}\rvert\leq\varrho=(B/C)^{1/2}\leq
1/(8p)$, we have,

$\displaystyle\mathbf{E}\left[Y_{l}\right]$ $\displaystyle=\lvert
x_{l}\rvert^{p}\left(\sum_{r=0}^{k-1}c_{r}\frac{\mathbf{E}\left[Z_{l}^{r}\right]}{\lvert
x_{l}\rvert^{r}}+c_{k}\frac{\mathbf{E}\left[Z_{l}^{{}^{\prime}k}\right]}{\lvert
x_{l}\rvert^{k}}\right)=\lvert x_{l}\rvert^{p}\left(1\pm\gamma\right)$

since, $\mathbf{E}\left[Z_{l}^{r}\right]=0$, for $r\in[k-1]$ and where,
$\lvert\gamma\rvert\leq\lvert c_{k}\rvert(8p)^{-k}==\zeta$ (say), which is
$n^{-\Omega(1)}$ since $k=\Omega(\log n)$. That is, we have shown that
$\displaystyle\left\lvert\mathbf{E}\left[Y_{l}\right]-\lvert
x_{l}\rvert^{p}\right\rvert\leq\gamma\lvert x_{l}\rvert^{p}$.

By a similar argument, $\mathbf{E}\left[\overline{Y_{l}}\right]=\lvert
x_{l}\rvert^{p}(1\pm\gamma)$.

Since, $\displaystyle Y_{l}=(\lvert x_{l}\rvert+Z_{l})^{p}=\lvert
x_{l}\rvert^{p}\left(1+\frac{Z_{l}}{\lvert x_{i}\rvert}\right)^{p}$, we have,

$\displaystyle\mathbf{E}\left[\left(Y_{l}-\mathbf{E}\left[Y_{l}\right]\right)^{e}\left(\overline{Y_{l}}-\mathbf{E}\left[\overline{Y_{l}}\right]\right)^{g}\right]$
$\displaystyle=\mathbf{E}\left[\left(\lvert
x_{l}\rvert^{p}\left(1+\frac{Z_{l}}{\lvert x_{l}\rvert}\right)^{p}-\lvert
x_{l}\rvert^{p}(1+\gamma)\right)^{e}\left(\lvert
x_{l}\rvert^{p}\left(1+\frac{\overline{Z_{l}}}{\lvert
x_{l}\rvert}\right)^{p}-\lvert x_{l}\rvert^{p}(1\pm\gamma)\right)^{g}\right]$
$\displaystyle=\lvert x_{l}\rvert^{p(e+g)}(1+\zeta)^{e+g}$
$\displaystyle\hskip
36.135pt\mathbf{E}\left[\left((1+\gamma)^{-1}\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{e}\left((1+\overline{\gamma})^{-1}\left(1+\frac{\overline{Z_{l}}}{\lvert
x_{l}\rvert}\right)^{p}-(1\pm\gamma)\right)^{g}\right]$
$\displaystyle\leq\lvert
x_{l}\rvert^{p(e+g)}(1+\gamma)^{e+g}\mathbf{E}\left[\left(\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{e}\left(\left(1+\frac{\overline{Z_{l}}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{g}\right]$ $\displaystyle\leq\lvert
x_{l}\rvert^{p(e+g)}(1+\gamma)^{e+g}\left(\frac{7p^{2}(e+g)F_{2}^{\text{res}}\left({C}\right)}{\lvert
x_{l}\rvert^{2}\rho C}\right)^{(e+g)/2}$ $\displaystyle=\left(\frac{\lvert
x_{l}\rvert^{2p-2}a(e+g)F_{2}^{\text{res}}\left({C}\right)}{\rho
C}\right)^{(e+g)/2}$

where, $a=7p^{2}(1+\gamma)^{e+g}\leq(7p^{2})e^{(e+g)\gamma}\leq 9p^{2}$,
since, $e+g\leq O(\log(1/\delta)$ and
$\gamma=\textrm{exp}\left\\{{-(\ln(8p))k}\right\\}\leq O(1/(\log(1/\delta)))$,
if $k=O(\log\log(1/\delta))$. The second to last step follows from the first
statement of the lemma.

###### Lemma 42

Let $1\leq e\leq\lceil\log(1/\delta)\rceil$ and $l\in\text{mid}(G_{0})$.
Suppose the random roots of unity family $\\{\omega_{lr}\\}_{l,r}$ is
$O(\log(n)\log(1/\delta))$-wise independent. Then,

$\mathbf{E}\left[\left(\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{e}\mid\mathcal{H}\right]\leq
n^{-\Omega(1)}\enspace.$

Therefore,

$\mathbf{E}\left[\left(Y_{l}-\mathbf{E}\left[Y_{l}\right]\right)^{e}\mid\mathcal{H}\right]\leq\lvert
x_{l}\rvert^{pe}n^{-\Omega(1)}$

and

$\mathbf{E}\left[\left(\overline{Y_{l}}-\mathbf{E}\left[\overline{Y_{l}}\right]\right)^{e}\mid\mathcal{H}\right]\leq\lvert
x_{l}\rvert^{pe}n^{-\Omega(1)}\enspace.$

  * Proof:  All expectations in this proof are conditional on $\mathcal{H}$. Let $k$ be a parameter. Let $c_{r}=\binom{p}{r}$, for $r=0,1,\ldots,k$. Then,

$\displaystyle\mathbf{E}\left[\left(\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{e}\mid\mathcal{H}\right]=\mathbf{E}\left[\left(\left(\sum_{r=1}^{k-1}c_{r}\left(\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{r}\right)+c_{k}\left(\frac{Z^{\prime}_{i}}{\lvert
x_{i}\rvert}\right)^{k}\right)^{e}\mid\mathcal{H}\right]$ (103)

where, $\lvert Z^{\prime}_{i}\rvert\leq\lvert Z_{i}\rvert$.

Denote $\sum_{r=1}^{k-1}c_{r}\left(\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{r}$ by $\alpha$ and
$c_{k}\frac{Z_{i}^{{}^{\prime}k}}{\lvert x_{i}\rvert^{k}}$ by $\beta$. Let
$d_{r}=\binom{e}{r}$, for $r=0,1,\ldots,e$. We have,
$\lvert\alpha\rvert\leq\sum_{r=1}^{k-1}\lvert
c_{r}\rvert(8p)^{-1}\leq(1/8)\sum_{r=1}^{k-1}(1/8)^{r-1}=1/7$. Also,
$\lvert\beta\rvert\leq(8p)^{-k}$. Then, Eqn. (103) can be written as

$\displaystyle\mathbf{E}\left[\left(\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{e}\mid\mathcal{H}\right]$
$\displaystyle=\mathbf{E}\left[\left(\alpha+\beta\right)^{e}\mid\mathcal{H}\right]=\mathbf{E}\left[\alpha^{e}\mid\mathcal{H}\right]+\sum_{r=1}^{e}d_{r}\mathbf{E}\left[\alpha^{e-r}\beta^{r}\mid\mathcal{H}\right]\enspace.$
(104)

Now,

$\displaystyle\mathbf{E}\left[\alpha^{e}\mid\mathcal{H}\right]=\mathbf{E}\left[\left(\sum_{r=1}^{k-1}c_{r}\left(\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{r}\right)^{e}\mid\mathcal{H}\right]=\sum_{h_{1}+\ldots+h_{k-1}=e}\prod_{r=1}^{k-1}c_{r}^{h_{r}}\frac{\mathbf{E}\left[Z_{l}^{\sum_{r=1}^{k-1}r\cdot
h_{r}}\mid\mathcal{H}\right]}{\lvert x_{l}\rvert^{\sum_{r=1}^{k-1}r\cdot
h_{r}}}=0\enspace.$

Consider the sum
$\displaystyle\sum_{r=1}^{e}d_{r}\lvert\alpha\rvert^{e-r}\lvert\beta\rvert^{r}$.
The ratio of $r+1$th term to the $r$th term is
$\displaystyle\left(\frac{e-r}{r+1}\right)\cdot
7\beta\leq(7e\lvert\beta\rvert/2)$. Assuming $k=O(\log n)$,
$\lvert\beta\rvert\leq(8p)^{-k}=n^{-\Omega(1)}$. Therefore,
$\displaystyle\sum_{r=1}^{e}d_{r}\lvert\alpha\rvert^{e-r}\lvert\beta\rvert^{r}\leq
e(1/7)^{e-1}\lvert\beta\rvert(1+O(en^{-\Omega(1)}))\leq n^{-\Omega(1)}$.

Substituting these into Eqn. (104), we have,

$\displaystyle\mathbf{E}\left[\left(\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{e}\mid\mathcal{H}\right]=\mathbf{E}\left[\left(\alpha+\beta\right)^{e}\mid\mathcal{H}\right]$
$\displaystyle=0+\sum_{r=1}^{e}d_{r}\mathbf{E}\left[\alpha^{e-r}\beta^{r}\mid\mathcal{H}\right]\enspace.$

Taking absolute values, we have,

$\displaystyle\left\lvert\mathbf{E}\left[\left(\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{e}\mid\mathcal{H}\right]\right\rvert\leq\sum_{r=1}^{e}d_{r}\lvert\alpha\rvert^{e-r}\lvert\beta\rvert^{r}=n^{-\Omega(1)}\enspace.$

Now, $\displaystyle Y_{l}=\lvert x_{l}\rvert^{p}\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}$ and therefore,
$\displaystyle\left\lvert\frac{\mathbf{E}\left[Y_{l}\mid\mathcal{H}\right]}{\lvert
x_{l}\rvert^{p}}-1\right\rvert\leq n^{-\Omega(1)}$, using $k=O(\log n)$-wise
independence. Equivalently,
$\displaystyle\bigl{\lvert}\mathbf{E}\left[Y_{l}\mid\mathcal{H}\right]-\lvert
x_{l}\rvert^{p}\bigr{\rvert}\leq\lvert x_{l}\rvert^{p}n^{-\Omega(1)}$. So,
$\mathbf{E}\left[Y_{l}\mid\mathcal{H}\right]=\lvert
x_{l}\rvert^{p}(1+\gamma)$, where, $\lvert\gamma\rvert\leq n^{-\Omega(1)}$.
Therefore,

$\displaystyle\mathbf{E}\left[(Y_{l}-\mathbf{E}\left[Y_{l}\right])^{e}\mid\mathcal{H}\right]$
$\displaystyle=\lvert
x_{l}\rvert^{pe}\mathbf{E}\left[\left(\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}-(1+\gamma)\right)^{e}\right]\enspace.$

Taking absolute values,

$\displaystyle\left\lvert\mathbf{E}\left[(Y_{l}-\mathbf{E}\left[Y_{l}\right])^{e}\right]\right\rvert$
$\displaystyle=\lvert
x_{l}\rvert^{pe}\left\lvert\mathbf{E}\left[\left(\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}-(1+\gamma)\right)^{e}\mid\mathcal{H}\right]\right\rvert$
$\displaystyle\leq\lvert
x_{l}\rvert^{pe}(1+\lvert\gamma\rvert)^{e}\left\lvert\mathbf{E}\left[\left(\left(1+\frac{Z_{l}}{\lvert
x_{l}\rvert}\right)^{p}-1\right)^{e}\mid\mathcal{H}\right]\right\rvert$
$\displaystyle\leq\lvert x_{l}\rvert^{pe}(1+n^{-\Omega(1)})^{e}n^{-\Omega(1)}$
$\displaystyle\leq\lvert x_{l}\rvert^{pe}n^{-\Omega(1)}\enspace.$

since, $e\leq\lceil\log(1/\delta)\rceil\leq O(\log n)$.

###  A.6 A combinatorial lemma

In the calculation of the $d$th central moment for the contribution from the
items in $\text{mid}(G_{0})$, we will need to estimate an upper bound on the
following combinatorial sums defined in Eqns. (3.3) and (2) respectively.

$\displaystyle Q(S_{1},S_{2})$
$\displaystyle=\sum_{q=1}^{\min(S_{1},S_{2})}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{q}=S_{1}\\\
e_{j}^{\prime}s\geq
1\end{subarray}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{q}=S_{2}\\\
g_{j}^{\prime}s\geq
1\end{subarray}}\binom{S_{1}}{e_{1},\ldots,e_{q}}\binom{S_{2}}{g_{1},\ldots,g_{q}}$
$\displaystyle\hskip
5.69046pt\sum_{\\{i_{1},\ldots,i_{q}\\}}\prod_{r=1}^{q}\lvert
x_{i_{r}}\rvert^{(p-1)(e_{r}+g_{r})}\prod_{r=1}^{q}(e_{r}+g_{r})^{(e_{r}+g_{r})/2}\enspace.$
$\displaystyle R(S)$ $\displaystyle=\sum_{q=1}^{\lfloor
S/2\rfloor}\sum_{h_{1}+\ldots+h_{q}=S,h_{j}^{\prime}s\geq
2}\binom{S}{h_{1},\ldots,h_{q}}\sum_{\\{i_{1},\ldots,i_{q}\\}}\prod_{r\in[q]}\lvert
x_{i_{r}}\rvert^{(p-1)h_{r}}\prod_{r\in[q]}h_{r}^{h_{r}/2}\enspace.$

Define the sum

$\displaystyle P(S)$
$\displaystyle=\sum_{q=1}^{S}\sum_{i_{1},\ldots,i_{q}}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{q}=2S\\\
e_{1},\ldots e_{q}\geq
2\end{subarray}}\binom{S}{e_{1}/2,\ldots,e_{q}/2}\prod_{r\in[q]}\lvert
x_{i_{r}}\rvert^{(2p-2)(g_{r}/2)}\enspace.$ (105)

The expression in Eqn. (3.3) is upper bounded by

###### Lemma 43

[Re-statement of first part of Lemma 13.] $Q(S_{1},S_{2})\leq R(S_{1}+S_{2})$.

  * Proof:  Consider the multinomial expansion of $(a_{1}+\ldots+a_{q})^{S_{1}}$, for $a_{1},\ldots,a_{q}\geq 0$ together with the constraint that in each monomial of the form $\prod_{i\in[q]}{a_{i}}^{e_{i}}$, each $e_{i}\geq 1$. This equals $\sum_{e_{1}+\ldots+e_{q}=S_{1},e_{j}^{\prime}s\geq 1}\binom{S_{1}}{e_{1},\ldots,e_{q}}\prod_{i\in[q]}a_{i}^{e_{i}}$. The multinomial expansion of $(a_{1}+\ldots+a_{q})^{S_{2}}$ with the same constraint can be written as $\sum_{g_{1}+\ldots+g_{q}=S_{2},g_{j}^{\prime}s\geq 1}$ $\binom{S_{2}}{g_{1},\ldots,g_{q}}\prod_{i\in[q]}a_{i}^{g_{i}}$. Now consider the multinomial expansion of $(a_{1}+\ldots+a_{q})^{S_{1}+S_{2}}$ subject to the constraint that in each monomial of the form $\prod_{i\in[q]}{a_{i}}^{h_{i}}$, each $h_{i}\geq 2$. This equals $\sum_{h_{1}+\ldots+h_{q}=S_{1}+S_{2},h_{j}^{\prime}s\geq 2}$ $\binom{S_{1}+S_{2}}{h_{1},\ldots,h_{q}}\prod_{i\in[q]}a_{i}^{h_{i}}$. It therefore follows that

$\displaystyle\sum_{e_{1}+\ldots+e_{q}=S_{1},e_{j}^{\prime}s\geq
1}\binom{S_{1}}{e_{1},\ldots,e_{q}}\prod_{i\in[q]}a_{i}^{e_{i}}\sum_{g_{1}+\ldots+g_{q}=S_{2},g_{j}^{\prime}s\geq
1}\binom{S_{2}}{g_{1},\ldots,g_{q}}\prod_{i\in[q]}a_{i}^{g_{i}}$
$\displaystyle\hskip
72.26999pt\leq\sum_{h_{1}+\ldots+h_{q}=S_{1}+S_{2},h_{j}^{\prime}s\geq
2}\binom{S_{1}+S_{2}}{h_{1},\ldots,h_{q}}\prod_{i\in[q]}a_{i}^{h_{i}}$

Here the variables $h_{i}$ takes values (among other possibilities)
$e_{i}+g_{i}$, for $i\in[q]$, for each $q$-partition vector $e$ of $S_{1}$ and
$q$-partition $g$ of $S_{2}$. Therefore,

$\displaystyle\sum_{e_{1}+\ldots+e_{q}=S_{1},e_{j}^{\prime}s\geq
1}\binom{S_{1}}{e_{1},\ldots,e_{q}}\prod_{i\in[q]}a_{i}^{e_{i}}\sum_{g_{1}+\ldots+g_{q}=S_{2},g_{j}^{\prime}s\geq
1}\binom{S_{2}}{g_{1},\ldots,g_{q}}\prod_{i\in[q]}a_{i}^{g_{i}}$
$\displaystyle\hskip 72.26999pt\prod_{i\in[q]}(e_{i}+g_{i})^{(e_{i}+g_{i})/2}$
$\displaystyle\leq\sum_{h_{1}+\ldots+h_{q}=S_{1}+S_{2},h_{j}^{\prime}s\geq
2}\binom{S_{1}+S_{2}}{h_{1},\ldots,h_{q}}\prod_{i\in[q]}a_{i}^{h_{i}}\prod_{i\in[q]}h_{i}^{h_{i}/2}\enspace.$
(106)

It therefore follows that by letting $a_{i}=\lvert x_{i}\rvert^{p-1}$, for
$i\in[n]$, that

$\displaystyle Q(S_{1},S_{2})$ (107)
$\displaystyle=\sum_{q=1}^{\min(S_{1},S_{2})}\sum_{\\{i_{1},\ldots,i_{q}\\}\subset[n]}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{q}=S_{1}\\\
e_{j}^{\prime}s\geq
1\end{subarray}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{q}=S_{2}\\\
g_{j}^{\prime}s\geq
1\end{subarray}}\binom{S_{1}}{e_{1},\ldots,e_{q}}\binom{S_{2}}{g_{1},\ldots,g_{q}}$
$\displaystyle\hskip 72.26999pt\prod_{r=1}^{q}\lvert
x_{i_{r}}\rvert^{(p-1)(e_{r}+g_{r})}\prod_{r=1}^{q}(e_{r}+g_{r})^{(e_{r}+g_{r})/2}$
$\displaystyle\leq\sum_{q=1}^{\lfloor(S_{1}+S_{2})/2\rfloor}\sum_{\\{i_{1},\ldots,i_{q}\\}}\sum_{h_{1}+\ldots+h_{q}=S_{1}+S_{2},h_{j}^{\prime}s\geq
2}\binom{S_{1}+S_{2}}{h_{1},\ldots,h_{q}}\prod_{r\in[q]}\lvert
x_{i_{r}}\rvert^{(p-1)h_{r}}\prod_{r\in[q]}h_{r}^{h_{r}/2}$
$\displaystyle=R(S_{1}+S_{2})$ (108)

Suppose we generalize the factorial notation $x!$ to mean $\Gamma(x+1)$, when
$x$ is a fraction of the form $(n+1/2)$, for $n\geq 1$. Using this, generalize
the multinomial coefficient notation $\binom{S}{e_{1},\ldots,e_{q}}$ to denote
$\frac{S!}{e_{1}!\ldots e_{q}!}$, even when the $e_{j}$’s are fractional and
of the form $(n+1/2)$, for $n\geq 1$.

###### Lemma 44

$R^{2}(S)\leq R(2S)$.

  * Proof:

$\displaystyle R^{2}(S)$ $\displaystyle=\sum_{q_{1}=1}^{\lfloor
S/2\rfloor}\sum_{q_{2}=1}^{\lfloor
S/2\rfloor}\sum_{\\{i_{1},\ldots,i_{q_{1}}\\}}\sum_{j_{1},\ldots,j_{q_{2}}}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{q_{1}}=S\\\
e_{j}^{\prime}s\geq
2\end{subarray}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{q_{2}}=S\\\
g_{j}^{\prime}s\geq
2\end{subarray}}\binom{S}{e_{1},\ldots,e_{q_{1}}}\binom{S}{g_{1},\ldots,g_{q_{2}}}$
$\displaystyle\hskip 72.26999pt\prod_{r\in[q_{1}]}\lvert
x_{i_{r}}\rvert^{(p-1)e_{r}}\prod_{s\in[q_{2}]}\lvert
x_{j_{s}}\rvert^{(p-1)g_{s}}\prod_{r\in[q_{1}]}e_{r}^{e_{r}/2}\prod_{r\in[q_{2}]}g_{r}^{g_{r}/2}\enspace.$

Define

$\displaystyle a$ $\displaystyle=\bigl{\lvert}\\{i_{1},\ldots
i_{q_{1}}\\}\cap\\{j_{1},\ldots,j_{q_{2}}\\}\bigr{\rvert}$ $\displaystyle b$
$\displaystyle=\\{\bigl{\lvert}\\{i_{1},\ldots,i_{q_{1}}\\}\setminus\\{j_{1},\ldots,j_{q_{2}}\\}\bigr{\rvert}$
$\displaystyle c$
$\displaystyle=\\{\bigl{\lvert}\\{j_{1},\ldots,j_{q_{2}}\\}\setminus\\{i_{1},\ldots,i_{q_{1}}\\}\bigr{\rvert}$

Then, $R^{2}(S)$ can be written as

$\displaystyle R^{2}(S)$
$\displaystyle=\sum_{a=0}^{S}\sum_{b=\max(0,1-a)}^{S-a}\sum_{c=\max(0,1-a)}^{S-a}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{a+b}=S\\\
e_{j}^{\prime}s\geq
2\end{subarray}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{a+c}=S\\\
g_{j}^{\prime}s\geq
2\end{subarray}}\binom{S}{e_{1},\ldots,e_{a+b}}\binom{S}{g_{1},\ldots,g_{a+c}}$
$\displaystyle\sum_{\\{i_{1},\ldots,i_{a},j_{1},\ldots,j_{b},k_{1},\ldots,k_{c}\\}}\prod_{l=1}^{a}\lvert
x_{i_{l}}\rvert^{(p-1)(e_{l}+g_{l})}\prod_{m=1}^{b}\lvert
x_{j_{m}}\rvert^{(p-1)e_{l+m}}\prod_{n=1}^{c}\lvert
x_{k_{n}}\rvert^{(p-1)e_{l+n}}$ $\displaystyle\hskip
144.54pt\prod_{l=1}^{a}\left(e_{l}^{e_{l}/2}g_{l}^{g_{l}/2}\right)\prod_{m=1}^{b}e_{l+m}^{e_{l+m}/2}\prod_{n=1}^{x}g_{l+n}^{g_{l+n}/2}\enspace.$
(109)

By a similar argument as in Lemma 43, and using the fact that
$\left(e_{l}^{e_{l}/2}g_{l}^{g_{l}/2}\right)\leq(e_{l}+g_{l})^{(e_{l}+g_{l})/2}$,
for any $e_{l},g_{l}\geq 1$, we have that the sum in Eqn. (109), is bounded
above by the following sum (using $q=a+b+c$).

$\displaystyle\leq\sum_{q=1}^{S}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{q}=2S\\\
e_{j}^{\prime}s\geq
2\end{subarray}}\binom{2S}{e_{1},\ldots,e_{q}}\sum_{\\{i_{1},\ldots,i_{q}\\}}\prod_{l=1}^{q}\lvert
x_{i_{l}}\rvert^{(p-1)e_{j}}\prod_{l=1}^{q}e_{l}^{e_{l}/2}$ (110)
$\displaystyle=R(2S)\enspace.$

###### Lemma 45

$\displaystyle R(2S)$ $\displaystyle\leq(2eS)^{S}P(S)$
$\displaystyle=(2eS)^{S}\sum_{q=1}^{S}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{q}=2S\\\
e_{j}^{\prime}s\geq
2\end{subarray}}\binom{S}{e_{1}/2,\ldots,e_{q}/2}\sum_{\\{i_{1},\ldots
i_{q}\\}}\prod_{r\in[q]}\lvert x_{i_{r}}\rvert^{(2p-2)(e_{r}/2)}\enspace.$

  * Proof:  Consider Eqn. (110).

Fix $q$ and $\\{i_{1},\ldots,i_{q}\\}$. Then, using Stirling’s formula, we
have,

$\displaystyle\binom{2S}{e_{1},\ldots,e_{q}}\prod_{l=1}^{q}e_{l}^{e_{l}/2}$
$\displaystyle=\frac{(2S)!}{e_{1}!\ldots
e_{q}!}\prod_{l=1}^{q}e_{l}^{e_{l}/2}$
$\displaystyle\leq(2S)^{S}\left(\frac{S!e^{e_{1}+\ldots+e_{q}}}{\left(\prod_{r\in[q]}\sqrt{2\pi
e_{r}}\right)e_{1}^{e_{1}}\cdots
e_{q}^{e_{q}}}\right)\prod_{l=1}^{q}e_{l}^{e_{l}/2}$
$\displaystyle\leq(2eS)^{S}\left(\frac{S!}{(e_{1}/2)!\ldots(e_{q}/2)!}\right)$
$\displaystyle=(2eS)^{S}\binom{S}{e_{1}/2,\ldots,e_{q}/2}$

using the generalized factorial notation. The statement of the lemma now
follows.

We would now like to establish a bound on $R(2S)$ in terms of $F_{2p-2}^{S}$.
The two expressions are shown below.

$\displaystyle P(S)$ $\displaystyle\leq\sum_{q=1}^{S}\sum_{\\{i_{1},\ldots
i_{q}\\}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{q}=2S\\\ g_{j}^{\prime}s\geq
2\end{subarray}}\binom{S}{g_{1}/2,\ldots,g_{q}/2}\prod_{r\in[q]}\lvert
x_{i_{r}}\rvert^{(2p-2)(g_{r}/2)}\enspace.$ (111) $\displaystyle F_{2p-2}^{S}$
$\displaystyle=\sum_{q=1}^{S}\sum_{\\{i_{1},\ldots
i_{q}\\}}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{q}=S\\\ e_{j}^{\prime}s\geq
1\end{subarray}}\binom{S}{e_{1},\ldots,e_{q}}\prod_{r\in[q]}\lvert
x_{i_{r}}\rvert^{(2p-2)e_{r}}\enspace.$ (112)

###### Lemma 46

$P(S)\leq 4^{S}F_{2p-2}^{S}$.

###### Corollary 47

$R(2S)\leq(8eS)^{S}F_{2p-2}^{S}$ .

  * Proof:  [Proof of Corollary 47.] We have from Lemma 45 that $R(2S)\leq(2eS)^{S}P(S)$. By Lemma 46, we have $P(S)\leq 4^{S}F_{2p-2}^{S}$. Combining, we obtain the corollary.

  * Proof:  [Of Lemma 46.]

Fix $q$ and fix a choice of the index set
$\\{i_{1},\ldots,i_{q}\\}\subset[n]$.

For $q\in[S]$, define the sets
$U_{q}=\\{(g_{1},\ldots,g_{q}):g_{1}+\ldots+g_{q}=2S,g_{j}^{\prime}s\geq 2\\}$
and $V_{q}=\\{(e_{1},\ldots,e_{q}):e_{1}+\ldots+e_{q}=S,e_{j}^{\prime}s\geq
1\\}$. The sets $U_{q}$ and $V_{q}$ may be viewed as two partitions of bi-
partite graph $G_{q}=(U_{q},V_{q},E_{q})$, where the edge-set $E_{q}$ is
defined as follows. Let $(g_{1},\ldots,g_{q})\in U_{q}$. Let $h$ be the number
of indices $j$ such that $g_{j}$ is even and let these indices be
$k_{1}<\ldots<k_{h}$ in sequence. Thus, $g_{j}$ is odd for any
$j\not\in\\{k_{1},\ldots,k_{h}\\}$. Define,

$\displaystyle e_{k_{j}}=g_{k_{j}}/2,~{}~{}~{}j=1,2,\ldots,h\enspace.$ (113)

Note that $q-h$ is even. This is because $0=2S\mod 2=g_{1}+\ldots+g_{q}\mod
2=\left((g_{k_{1}}+\ldots+g_{k_{h}}\right)\mod
2+\sum_{j\not\in\\{k_{1},\ldots,k_{h}\\}}(g_{j}\mod 2)=q-h\mod 2$, since each
of $g_{k_{r}}$ is even, for $r\in[h]$ and each of $g_{j}$ is odd, for
$j\in[q]\setminus\\{k_{1},\ldots,k_{h}\\}$.

Let $l_{1}<l_{2}<\ldots<l_{q-h}$ be the sequence of all indices in $[q]$ such
that $g_{l_{j}}$ is odd, for $l\in[q-h]$. Note that $q-h$ is even. Let $t$ be
the permutation of $\\{l_{1},\ldots,l_{q-h}\\}$ such that $\lvert
x_{t_{1}}\rvert\leq\lvert x_{t_{2}}\rvert\leq\ldots\leq\lvert
x_{t_{q-h}}\rvert$. Define,

$\displaystyle e_{t_{j}}$ $\displaystyle=\begin{cases}\lfloor
g_{t_{j}}/2\rfloor&~{}~{}~{}j=1,2,\ldots,(q-h)/2\\\ \lceil
g_{t_{j}}/2\rceil&~{}~{}~{}j=(q-h)/2+1,\ldots,q-h\enspace.\end{cases}$ (114)

Denote this mapping as $\phi(g_{1},\ldots,g_{q})$, where,
$\phi:U_{q}\rightarrow V_{q}$.

We would now like to count $\lvert\phi^{-1}(e_{1},\ldots,e_{q})\rvert$. Fix
$(e_{1},\ldots,e_{q})$ and fix any $H\subset[q]$. We will let $H$ be the set
of indices such that $g_{i}$ is even and $g_{i}=2e_{i}$. Let $\lvert
H\rvert=h$. Let $l_{1}<l_{2}<\ldots<l_{q-h}$ be the sequence of indices in
$[q]\setminus H$. Let $t$ be the permutation of $\\{l_{1},\ldots,l_{q-h}\\}$
such that $\lvert x_{t_{1}}\rvert\leq\lvert
x_{t_{2}}\rvert\leq\ldots\leq\lvert x_{t_{q-h}}\rvert$. Define,

$\displaystyle g_{t_{j}}$ $\displaystyle=\begin{cases}2e_{t_{j}}-1&\text{ for
}j=(q-h)/2+1,\ldots,q-h\\\ 2e_{t_{j}}+1&\text{ for
}j=1,2,\ldots,(q-h)/2\enspace.\end{cases}$ (115)

For a fixed $H$, this function $\psi_{H}(e_{1},\ldots,e_{q})$ is a mapping
from $V_{q}$ to $U_{q}$. Further, if for a given $(g_{1},\ldots,g_{q})$,
$H=\\{i:g_{i}\text{ is even }\\}$, then,

$\psi_{H}(\phi(g_{1},\ldots,g_{q}))=(g_{1},\ldots,g_{q})\enspace.$

Hence,

$\displaystyle\lvert\phi^{-1}(e_{1},\ldots,e_{q})\rvert\leq\bigl{\lvert}\\{H:H\subset[q]\\}\bigr{\rvert}=2^{q}\enspace.$
(116)

Another important fact is that by construction, for any
$(g_{1},\ldots,g_{q})\in U_{q}$, if we let
$(e_{1},\ldots,e_{q})=\phi(g_{1},\ldots,g_{q})$, then,

$\prod_{r=1}^{q}\lvert x_{i_{r}}\rvert^{(p-1)g_{r}}\leq\prod_{r=1}^{q}\lvert
x_{i_{r}}\rvert^{(2p-2)e_{r}}\enspace.$

This can be seen as follows. Let $H=\\{i:g_{i}\text{ is even }\\}$ and let
$h=\lvert H\rvert$. Let $\bar{H}=[q]\setminus H$ and
$\bigl{\lvert}\bar{H}\bigr{\rvert}=q-h$. Then, $\prod_{r\in[q]}\lvert
x_{r}\rvert^{(p-1)g_{r}}=\prod_{r\in H}\lvert
x_{r}\rvert^{(2p-2)e_{r}}\prod_{r\in\bar{H}}\lvert x_{r}\rvert^{(p-1)g_{r})}$.
It suffices to show that $\prod_{r\in\bar{H}}\lvert
x_{r}\rvert^{g_{r}}\leq\prod_{r\in\bar{H}}\lvert x_{r}\rvert^{2e_{r}}$. This
is equivalent to show that $\sum_{r\in\bar{H}}g_{r}\ln\lvert
x_{r}\rvert\leq\sum_{r\in\bar{H}}2e_{r}\ln\lvert x_{r}\rvert$. Let
$\alpha_{r}=\ln\lvert x_{r}\rvert\geq 0$. Let $t$ be a permutation of the
indices of the elements of $\bar{H}$ such that $\lvert
x_{t_{1}}\rvert\leq\lvert x_{t_{2}}\rvert\leq\ldots\leq\lvert
x_{t_{q-h}}\rvert$. So it suffices to show that
$\sum_{r=1}^{q-h}g_{t_{r}}\alpha_{t_{r}}\leq\sum_{r=1}^{q-h}2e_{t_{r}}\alpha_{t_{r}}$.
The permutation orders the indices so that
$\alpha_{t_{1}}\leq\alpha_{t_{2}}\leq\ldots\leq\alpha_{t_{q-h}}$. The sum
$L(x)=\sum_{r=1}^{q-h}x_{r}\alpha_{t_{r}}$ is a linear function of
$g_{t_{r}}$. Consider the assignment for the $x_{r}$’s, where,
$x_{r}=g_{t_{r}}$, where, $g_{t_{r}}\geq 2$ is odd for each $r$. For any $j\in
1,\ldots,(q-h)/2$, let $x^{\prime}_{r}=g_{t_{r}}-1$ and
$x^{\prime}_{q-h-r}=g_{t_{q-h-r}}+1$ and let $x^{\prime}_{j}$ equal $x_{j}$
for all other indices $j\in[q-h]$. Then, $L(x)\leq L(x^{\prime})$, since,
$\alpha_{t_{j}}$’s are in non-descending order. Continuing this argument for
each $r\in[(q-h)/2]$, we obtain that $L(x)\leq L(x^{*})$, where,
$x^{*}_{r}=g_{t_{r}}-1=2e_{t_{r}}$, for $r=1,2,\ldots,(q-h)/2$ and
$x^{*}_{r}=g_{t_{r}}+1=2e_{t_{r}}$, for $r=1,2,\ldots,(q-h)/2$. This proves
the assertion.

Let $(e_{1},\ldots,e_{q})=\phi(g_{1},\ldots,g_{q})$, for some
$(g_{1},\ldots,g_{q})\in U_{q}$. We are now interested in an upper bound for
the following ratio
$\displaystyle\cfrac{\binom{S}{g_{1}/2,\ldots,g_{q}/2}}{\binom{S}{e_{1},\ldots,e_{q}}}$.
As before, let $H=\\{i\in[q]:g_{i}\text{ is even }\\}$ and let $E=\sum_{i\in
H}(g_{i}/2)$. Let the indices in $H$ be $k_{1}<k_{2}<\ldots<k_{h}$, where,
$h=\lvert H\rvert$. Let the remaining indices be
$l_{1}<l_{2}<\ldots,l_{h^{\prime}}$, where, $h^{\prime}=(q-h)$. Then,

$\displaystyle\binom{S}{g_{1}/2,\ldots,g_{q}/2}$
$\displaystyle=\frac{S!}{(g_{1}/2)!\cdots(g_{q}/2)!}$
$\displaystyle=\binom{S}{E}\binom{E}{(g_{k_{1}}/2),\ldots,(g_{k_{h}}/2)}\binom{S-E}{(g_{l_{1}}/2)\ldots,(g_{l_{h^{\prime}}}/2)}$
$\displaystyle=\binom{S}{E}\binom{E}{e_{k_{1}},\ldots,e_{k_{h}}}\binom{S-E}{(g_{l_{1}}/2)\ldots,(g_{l_{h^{\prime}}}/2)}$

since, $(e_{1},\ldots,e_{q})=\phi(g_{1},\ldots,g_{q})$. Similarly,

$\displaystyle\binom{S}{e_{1},\ldots,e_{q}}$
$\displaystyle=\binom{S}{E}\binom{E}{e_{k_{1}},\ldots,e_{k_{h}}}\binom{S-E}{e_{l_{1}}\ldots,e_{l_{h^{\prime}}}}$

Taking ratios, let $R$ denote the ratio
$\displaystyle\cfrac{\binom{S}{g_{1}/2,\ldots,g_{q}/2}}{\binom{S}{e_{1},\ldots,e_{q}}}$.

$\displaystyle R$
$\displaystyle=\cfrac{\binom{S}{g_{1}/2,\ldots,g_{q}/2}}{\binom{S}{e_{1},\ldots,e_{q}}}=\cfrac{\binom{S-E}{(g_{l_{1}}/2)\ldots,(g_{l_{h^{\prime}}}/2)}}{\binom{S-E}{e_{l_{1}}\ldots,e_{l_{h^{\prime}}}}}=\prod_{r=1}^{h^{\prime}/2}\left(\cfrac{e_{l_{r}}!}{g_{l_{r}}/2!}\right)\left(\cfrac{e_{l_{h^{\prime}-r+1}}!}{g_{l_{h^{\prime}-r+1}}/2!}\right)$
$\displaystyle=\prod_{r=1}^{h^{\prime}/2}\cfrac{e_{l_{r}}!}{(e_{l_{r}}+1/2)!}\prod_{r=h^{\prime}/2+1}^{h^{\prime}}\cfrac{e_{l_{r}}!}{(e_{l_{r}}-1/2)!}\leq\prod_{r=h^{\prime}/2+1}^{h^{\prime}}\cfrac{e_{l_{r}}!}{(e_{l_{r}}-1/2)!}$
$\displaystyle\leq\prod_{r=h^{\prime}/2+1}^{h^{\prime}}\cfrac{e_{l_{r}}!}{(e_{l_{r}}-1)!}\leq\prod_{r=h^{\prime}/2+1}^{h^{\prime}}e_{l_{r}}\leq\prod_{r=1}^{h^{\prime}}e_{l_{r}}\enspace.$
(117)

Further, $\sum_{r=1}^{h^{\prime}}e_{l_{r}}=S-E$ $=S^{\prime}$ (say). Hence,
$\prod_{l=1}^{h^{\prime}}e_{l_{r}}$ is maximized when the $e_{l_{r}}$’s equals
$S^{\prime}/h$. The product is then at most
$(S^{\prime}/h^{\prime})^{h^{\prime}}=\textrm{exp}\left\\{{h^{\prime}\ln(S^{\prime}/h^{\prime})}\right\\}$.
The function $g(x)=x\ln\frac{a}{x}$ attains its maximum in the range $1\leq
x\leq a$ at $x=a/e$. The corresponding maximum value is $g^{*}=a/e$.
Therefore,
$\displaystyle\textrm{exp}\left\\{{h^{\prime}\ln(S^{\prime}/h^{\prime})}\right\\}\leq\textrm{exp}\left\\{{S/e}\right\\}$.
Substituting in Eqn. (A.6), we have,

$\displaystyle
R=\cfrac{\binom{S}{g_{1}/2,\ldots,g_{q}/2}}{\binom{S}{e_{1},\ldots,e_{q}}}\leq
e^{(S-E)/e}\enspace.$ (118)

Fix $q\in[S]$ and index set $\\{i_{1},\ldots,i_{q}\\}\subset[n]$. We will now
try to relate the sub-summations from Eqn. (111) and Eqn. (112) respectively.

$\displaystyle\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{q}=2S\\\
g_{j}^{\prime}s\geq
2\end{subarray}}\binom{S}{g_{1}/2,\ldots,g_{q}/2}\prod_{r\in[q]}\lvert
x_{i_{r}}\rvert^{(2p-2)(g_{r}/2)}$
$\displaystyle=\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{q}=S\\\
e_{j}^{\prime}s\geq
1\end{subarray}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{q}=2S\\\
g_{j}^{\prime}s\geq 2\\\
\phi(g_{1},\ldots,g_{q})=(e_{1},\ldots,e_{q})\end{subarray}}\binom{S}{g_{1}/2,\ldots,g_{q}/2}\prod_{r\in[q]}\lvert
x_{i_{r}}\rvert^{(2p-2)(g_{r}/2)}$
$\displaystyle\leq\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{q}=S\\\
e_{j}^{\prime}s\geq
1\end{subarray}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{q}=2S\\\
g_{j}^{\prime}s\geq 2\\\
\phi(g_{1},\ldots,g_{q})=(e_{1},\ldots,e_{q})\end{subarray}}e^{S/e}\binom{S}{e_{1},\ldots,e_{q}/2}\prod_{r\in[q]}\lvert
x_{i_{r}}\rvert^{(2p-2)e_{r}}$
$\displaystyle=e^{S/e}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{q}=S\\\
e_{j}^{\prime}s\geq
1\end{subarray}}\binom{S}{e_{1},\ldots,e_{q}/2}\prod_{r\in[q]}\lvert
x_{i_{r}}\rvert^{(2p-2)e_{r}}\left\lvert\phi^{-1}(e_{1},\ldots,e_{q})\right\rvert$
$\displaystyle\leq(2e^{1/e})^{S}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{q}=S\\\
e_{j}^{\prime}s\geq
1\end{subarray}}\binom{S}{e_{1},\ldots,e_{q}/2}\prod_{r\in[q]}\lvert
x_{i_{r}}\rvert^{(2p-2)e_{r}}\enspace.$ (119)

Therefore, since, $q\leq S$,

$\displaystyle P(S)$ $\displaystyle\leq\sum_{q=1}^{S}\sum_{\\{i_{1},\ldots
i_{q}\\}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{q}=2S\\\ g_{j}^{\prime}s\geq
2\end{subarray}}\binom{S}{g_{1}/2,\ldots,g_{q}/2}\prod_{r\in[q]}\lvert
x_{i_{r}}\rvert^{(2p-2)(g_{r}/2)}$
$\displaystyle\leq(2e^{1/e})^{S}\sum_{q=1}^{S}\sum_{\\{i_{1},\ldots
i_{q}\\}}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{q}=S\\\ e_{j}^{\prime}s\geq
1\end{subarray}}\binom{S}{e_{1},\ldots,e_{q}/2}\prod_{r\in[q]}\lvert
x_{i_{r}}\rvert^{(2p-2)e_{r}}$ $\displaystyle\leq 4^{S}F_{2p-2}^{S}\enspace.$

###### Corollary 48

[Re-statement of second part of Lemma 13.]
$R(S)\leq\left(4e^{1+1/e}SF_{2p-2}\right)^{S/2}$.

  * Proof:  Follows from Lemma 47 and Lemma 44.

###  A.7 $d$th central moment calculations for $\text{mid}(G_{0})$ resumed

###### Lemma 49

Let $a\geq 9p^{2}$ be a constant and let
$C\geq(400)ae(n^{1-2/p}/\log(n))\epsilon^{-2}\log(1/\delta)$ . Then,

$\displaystyle\sum_{q=1}^{\min(S_{1},S_{2})}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{q}=S_{1}\\\
e_{j}\geq 1\end{subarray}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{q}=S_{2}\\\
g_{j}\geq
1\end{subarray}}\binom{S_{1}}{e_{1},\ldots,e_{q}}\binom{S_{2}}{g_{1},\ldots,g_{q}}$
$\displaystyle\hskip 36.135pt\sum_{\\{i_{1},\ldots
i_{q}\\}}\prod_{r=1}^{q}\lvert
x_{i_{r}}\rvert^{p(e_{r}+g_{r})-2((e_{r}+g_{r})/2)}\left(\frac{aF_{2}}{\rho
C}\right)^{\sum_{r=1}^{q}(e_{r}+g_{r})/2}\prod_{r=1}^{q}(e_{r}+g_{r})^{(e_{r}+g_{r})/2}$
$\displaystyle\leq\left(\frac{\epsilon
F_{p}}{20}\right)^{S_{1}+S_{2}}\enspace.$

  * Proof:

$\displaystyle\sum_{q=1}^{\min(S_{1},S_{2})}\sum_{\begin{subarray}{c}e_{1}+\ldots+e_{q}=S_{1}\\\
e_{j}\geq 1\end{subarray}}\sum_{\begin{subarray}{c}g_{1}+\ldots+g_{q}=S_{2}\\\
g_{j}\geq
1\end{subarray}}\binom{S_{1}}{e_{1},\ldots,e_{q}}\binom{S_{2}}{g_{1},\ldots,g_{q}}$
$\displaystyle\hskip 36.135pt\sum_{\\{i_{1},\ldots
i_{q}\\}}\prod_{r=1}^{q}\lvert
x_{i_{r}}\rvert^{p(e_{r}+g_{r})-2((e_{r}+g_{r})/2)}\left(\frac{aF_{2}}{\rho
C}\right)^{\sum_{r=1}^{q}(e_{r}+g_{r})/2}\prod_{r=1}^{q}(e_{r}+g_{r})^{(e_{r}+g_{r})/2}$
$\displaystyle=\left(\frac{aF_{2}}{\rho
C}\right)^{(S_{1}+S_{2})/2}Q(S_{1}+S_{2})$
$\displaystyle\leq\left(\frac{aF_{2}}{\rho
C}\right)^{(S_{1}+S_{2})/2}R(S_{1}+S_{2}),~{}~{}\text{ by
Lemma~{}\ref{lem:comb:1}}$ $\displaystyle\leq\left(\frac{aF_{2}}{\rho
C}\right)^{(S_{1}+S_{2})/2}\left(16e(S_{1}+S_{2})F_{2p-2}\right)^{(S_{1}+S_{2})/2},~{}~{}\text{
by Corollary~{}\ref{lem:comb:R2SF2p2}}$
$\displaystyle=\left(\frac{16ae(S_{1}+S_{2})F_{2}}{\rho
C}\right)^{(S_{1}+S_{2})/2}F_{p}^{(2-2/p)(S_{1}+S_{2})/2}$ (120)

For $p\geq 2$, $2p-2\geq p$ and so $F_{2p-2}\leq F_{p}^{2-2/p}$. Since,
$\rho\geq\log n$, $1\leq S_{1},S_{2}\leq\lceil\log(1/\delta)\rceil$ and
$C=K(n^{1-2/p}/\log(n))\epsilon^{-2}\log(1/\delta))$, we have, for
$K=(400)(16ae)$, that

$\displaystyle\frac{16ae(S_{1}+S_{2})aF_{2}}{(\log
n)K(n^{1-2/p}/\log(n))\epsilon^{-2}\log(1/\delta)}\leq\frac{\epsilon^{2}F_{p}^{2/p}}{400}\enspace.$

Substituting in Eqn. ( ‣ A.7), we have,

$\displaystyle\left(\frac{16ae(S_{1}+S_{2})F_{2}}{\rho
C}\right)^{(S_{1}+S_{2})/2}F_{p}^{(2-2/p)(S_{1}+S_{2})/2}$
$\displaystyle\leq\left(\frac{\epsilon
F_{p}}{20}\right)^{S_{1}+S_{2}}\enspace.$

Let $\mathcal{H}$ denote the event
$\mathcal{G}\wedge\textsc{nocollision}\wedge\textsc{goodest}$.

######  Lemma 50 (Re-statement of Lemma 14)

. Let $a\geq 9p^{2}$ be a constant and let $C\geq K(16ae)(n^{1-2/p}/\log(n))$
$\epsilon^{-2}\log(1/\delta)$, where, $K=400(16ae)$. Then, for $0\leq
d_{1},d_{2}\leq\log(1/\delta)$ and integral, the following holds.

$\mathbf{E}\left[\left(\sum_{i\in\text{mid}(G_{0})}(Y_{i}-\mathbf{E}\left[Y_{i}\mid\mathcal{H}\right])\right)^{d_{1}}\left(\sum_{i\in\text{mid}(G_{0})}(\overline{Y_{i}}-\mathbf{E}\left[\overline{Y_{i}}\mid\mathcal{H}\right])\right)^{d_{2}}\mid\mathcal{H}\right]\leq\left(\frac{\epsilon
F_{p}}{10}\right)^{d_{1}+d_{2}}\enspace.$

  * Proof:  Recall that $\mathcal{H}$ denote the event $\mathcal{G}\wedge\textsc{nocollision}(\text{mid}(G_{0}))\wedge\textsc{goodest}(\text{mid}(G_{0}))$.

Let $\alpha_{0}(q)=\max(0,1-q)$.

$\displaystyle\mathbf{E}\left[\left(\sum_{i\in\text{mid}(G_{0})}(Y_{i}-\mathbf{E}\left[Y_{i}\mid\mathcal{G}\right])\right)^{d_{1}}\left(\sum_{i\in\text{mid}(G_{0})}(\overline{Y_{i}}-\mathbf{E}\left[\overline{Y_{i}}\mid\mathcal{H}\right])\right)^{d_{2}}\right]$
$\displaystyle=\sum_{q=0}^{\min(d_{1},d_{2})}\sum_{s=\alpha_{0}(q)}^{d_{1}-q}\sum_{t=\alpha_{0}(q)}^{d_{2}-q}\sum_{e_{1}+\ldots+e_{q+s}=d_{1}}\binom{d_{1}}{e_{1},\ldots,e_{q+s}}\sum_{g_{1}+\ldots+g_{q+t}=d_{2}}\binom{d_{2}}{g_{1},\ldots,g_{q+s}}$
$\displaystyle\sum_{\\{i_{1},\ldots,i_{q},j_{1},\ldots,j_{s},k_{1},\ldots,k_{t}\\}}\mathbf{E}\left[\prod_{r=1}^{q}(Y_{i_{r}}-\mathbf{E}\left[Y_{i_{r}}\mid\mathcal{H}\right])^{e_{r}}(\overline{Y_{i_{r}}}-\mathbf{E}\left[\overline{Y_{i_{r}}}\mid\mathcal{H}\right])^{g_{r}}\right.$
$\displaystyle\hskip
108.405pt\left.\prod_{l=1}^{s}(Y_{j_{l}}-\mathbf{E}\left[Y_{j_{l}}\mid\mathcal{H}\right])^{e_{q+s}}\prod_{m=1}^{t}(Y_{k_{m}}-\mathbf{E}\left[Y_{k_{m}}\mid\mathcal{H}\right])^{g_{q+t}}\right]$
(121)

Note that for a given value of $q$, if $q=0$, then $s$ and $t$ are at least 1,
and otherwise, for $q>0$, $s$ and $t$ may be initialized from 0.

Consider the term in the expectation of Eqn. ( ‣ A.7). By nocollision and its
consequent property as explained earlier,

$\displaystyle\mathbf{E}\left[\prod_{r=1}^{q}(Y_{i_{r}}-\mathbf{E}\left[Y_{i_{r}}\mid\mathcal{H}\right])^{e_{r}}(\overline{Y_{i_{r}}}-\mathbf{E}\left[\overline{Y_{i_{r}}}\mid\mathcal{H}\right])^{g_{r}}\prod_{l=1}^{s}(Y_{j_{l}}-\mathbf{E}\left[Y_{j_{l}}\mid\mathcal{H}\right])^{e_{q+s}}\right.$
$\displaystyle\left.\hskip
72.26999pt\prod_{m=1}^{t}(Y_{k_{m}}-\mathbf{E}\left[Y_{k_{m}}\mid\mathcal{H}\right])^{g_{q+t}}\right]$
$\displaystyle=\prod_{r=1}^{q}\mathbf{E}\left[(Y_{i_{r}}-\mathbf{E}\left[Y_{i_{r}}\mid\mathcal{H}\right])^{e_{r}}(\overline{Y_{i_{r}}}-\mathbf{E}\left[\overline{Y_{i_{r}}}\mid\mathcal{H}\right])^{g_{r}}\prod_{l=1}^{s}\mathbf{E}\left[(Y_{j_{l}}-\mathbf{E}\left[Y_{j_{l}}\mid\mathcal{H}\right])^{e_{q+s}}\right]\right.$
$\displaystyle\hskip
54.2025pt\left.\prod_{m=1}^{t}\mathbf{E}\left[(Y_{k_{m}}-\mathbf{E}\left[Y_{k_{m}}\mid\mathcal{H}\right])^{g_{q+t}}\right]\right]$
$\displaystyle\leq\prod_{r=1}^{q}\left(\frac{\lvert
x_{i_{r}}\rvert^{2p-2}a(e_{r}+g_{r})F_{2}}{\rho