with integer $0\leq c\leq 3$ and any constant $\eta>0$.

###### Proof.

By the Cauchy-Schwarz inequality,

$\operatorname*{\mathbb{E}}\left[\mathbbm{1}_{\\{\phi(Z_{j}+c)>\beta\\}}\exp\left\\{\varepsilon^{2}\theta\beta(2\phi(Z_{j}+c)-\beta)\right\\}\right]\leq\sqrt{\operatorname*{\mathbb{E}}[\mathbbm{1}_{\\{\phi(Z_{j}+c)>\beta\\}}]\operatorname*{\mathbb{E}}\left[\exp\left\\{\varepsilon^{2}\theta\beta(2\phi(Z_{j}+c)-\beta)\right\\}\right]}$

By Lemmas D.7 and D.9, this is $O\left(\Delta^{\eta}\right)$. ∎

###  D.2 General Lemmas

######  Lemma D.11.

For $Z_{j}\sim Poi(\lambda\nu_{j})$, and $\phi$ defined in (39)

$\displaystyle\operatorname*{\mathbb{E}}[\phi(Z_{j})^{2}]$
$\displaystyle=(\lambda\nu_{j})^{2}+\lambda\nu_{j}-2\lambda\nu_{j}\frac{n}{m}+\frac{n^{2}}{m^{2}}$
$\displaystyle\operatorname*{\mathbb{E}}[\phi(Z_{j})^{4}]$
$\displaystyle=(\lambda\nu_{j})^{4}+6(\lambda\nu_{j})^{3}+7(\lambda\nu_{j})^{2}+\lambda\nu_{j}-4\frac{n}{m}\left[(\lambda\nu_{j})^{3}+3(\lambda\nu_{j})^{2}+\lambda\nu_{j}\right]$
$\displaystyle+6\left(\frac{n}{m}\right)^{2}\left[(\lambda\nu_{j})^{2}+\lambda\nu_{j}\right]-4\left(\frac{n}{m}\right)^{3}\lambda\nu_{j}+\left(\frac{n}{m}\right)^{4}$

###### Proof.

$\operatorname*{\mathbb{E}}[\phi(Z_{j})^{2}]=\operatorname*{\mathbb{E}}\left[\left(Z_{j}-\frac{n}{m}\right)^{2}\right]=\operatorname*{\mathbb{E}}\left[Z_{j}^{2}-2Z_{j}\frac{n}{m}+\frac{n^{2}}{m^{2}}\right]$
$=(\lambda\nu_{j})^{2}+\lambda\nu_{j}-2\lambda\nu_{j}\frac{n}{m}+\frac{n^{2}}{m^{2}}$

$\displaystyle\operatorname*{\mathbb{E}}[\phi(Z_{j})^{4}]$
$\displaystyle=\operatorname*{\mathbb{E}}\left[\left(Z_{j}-\frac{n}{m}\right)^{4}\right]=\operatorname*{\mathbb{E}}\left[Z_{j}^{4}-4\frac{n}{m}Z_{j}^{3}+6\left(\frac{n}{m}\right)^{2}Z_{j}^{2}-4\left(\frac{n}{m}\right)^{3}Z_{j}+\left(\frac{n}{m}\right)^{4}\right]$
$\displaystyle=(\lambda\nu_{j})^{4}+6(\lambda\nu_{j})^{3}+7(\lambda\nu_{j})^{2}+\lambda\nu_{j}-4\frac{n}{m}\left[(\lambda\nu_{j})^{3}+3(\lambda\nu_{j})^{2}+\lambda\nu_{j}\right]$
$\displaystyle+6\left(\frac{n}{m}\right)^{2}\left[(\lambda\nu_{j})^{2}+\lambda\nu_{j}\right]-4\left(\frac{n}{m}\right)^{3}\lambda\nu_{j}+\left(\frac{n}{m}\right)^{4}$

∎

######  Lemma D.12.

For $Z_{j}\sim Poi(\lambda\nu_{j})$, and $\phi$ defined in (39)

$\displaystyle\operatorname*{\mathbb{E}}\left[\phi(Z_{j}+1)^{2}-\phi(Z_{j})^{2}\right]$
$\displaystyle=2\lambda\nu_{j}+1-\frac{2n}{m}$
$\displaystyle\operatorname*{\mathbb{E}}\left[\phi(Z_{j}+1)^{4}-\phi(Z_{j})^{4}\right]$
$\displaystyle=4(\lambda\nu_{j})^{3}+18(\lambda\nu_{j})^{2}+14(\lambda\nu_{j})+1$
$\displaystyle-\frac{4n}{m}(3(\lambda\nu_{j})^{2}+6\lambda\nu_{j}+1)+\frac{6n^{2}}{m^{2}}(2\lambda\nu_{j}+1)-\frac{4n^{3}}{m^{3}}$

###### Proof.

$\displaystyle\operatorname*{\mathbb{E}}[\phi(Z_{j}+1)^{2}-\phi(Z_{j})^{2}]=\operatorname*{\mathbb{E}}\left[2Z_{j}+1-\frac{2n}{m}\right]=2\lambda\nu_{j}+1-\frac{2n}{m}$

$\displaystyle\operatorname*{\mathbb{E}}[\phi(Z_{j}+1)^{4}-\phi(Z_{j})^{4}]$
$\displaystyle=\operatorname*{\mathbb{E}}\left[(4Z_{j}^{3}+6Z_{j}^{2}+4Z_{j}+1)-\frac{4n}{m}(3Z_{J}^{2}+3Z_{j}+1)+6\frac{n^{2}}{m^{2}}(2Z_{j}+1)-4\frac{n^{3}}{m^{3}}\right]$
$\displaystyle=4(\lambda\nu_{j})^{3}+18(\lambda\nu_{j})^{2}+14(\lambda\nu_{j})+1-\frac{4n}{m}(3(\lambda\nu_{j})^{2}+6\lambda\nu_{j}+1)+\frac{6n^{2}}{m^{2}}(2\lambda\nu_{j}+1)-\frac{4n^{3}}{m^{3}}$

∎

######  Lemma D.13.

The first four moments of the Poisson distribution are given by

$\operatorname*{\mathbb{E}}[X]=\lambda$
$\operatorname*{\mathbb{E}}[X^{2}]=\lambda^{2}+\lambda$
$\operatorname*{\mathbb{E}}[X^{3}]=\lambda^{3}+3\lambda^{2}+\lambda$
$\operatorname*{\mathbb{E}}[X^{4}]=\lambda^{4}+6\lambda^{3}+7\lambda^{2}+\lambda$

for $X\sim Poi(\lambda)$

###### Proof.

Computation of moments. ∎

######  Lemma D.14.

For any function $f$ and

$G(\psi)=-in\psi+\sum_{j=1}^{m}\log\left\\{\sum_{k=0}^{\infty}\left[\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}f(k)\right]\right\\}$

we have

$G^{\prime}(\psi)=-in+i\sum_{j=1}^{m}(\lambda_{0}\nu_{j}e^{i\psi})\frac{\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}f(k+1)}{\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}f(k)}$

so that $Re(G^{\prime}(0))=0$, and

$\displaystyle G^{\prime\prime}(\psi)=$
$\displaystyle\sum_{j=1}^{m}\left\\{\frac{1}{\left(\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}f(k)\right)^{2}}\left[(\lambda_{0}\nu_{j}e^{i\psi})^{2}\left\\{\left(\frac{\sum_{k=0}^{\infty}(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}f(k+1)\right)^{2}\right.\right.\right.$
$\displaystyle\left.\left.\left.-\left(\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}f(k)\right)\left(\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}f(k+2)\right)\right\\}\right.\right.$
$\displaystyle\left.\left.-(\lambda_{0}\nu_{j}e^{i\psi})\left(\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}f(k)\right)\left(\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}f(k+1)\right)\right]\right\\}$

###### Proof.

Follows from taking derivatives. ∎

##  Appendix E Lower bounds

###  E.1 The collisions tester is asymptotically bad when $n=\Theta(m)$ and
$\varepsilon=\omega\left(\frac{\log^{1/4}n}{n^{1/8}}\right)$

The following lower bound showing the collisions tester is asymptotically
suboptimal is based on a note of Peebles [31].

######  Theorem E.1.

When $n=\Theta(m)$ and
$\varepsilon=\omega\left(\frac{\log^{1/4}n}{n^{1/8}}\right)$, the collisions
tester has error probability
$\exp\left(-o\left(\frac{n^{2}\varepsilon^{4}}{m}\right)\right)$, and so,
takes $\omega(\sqrt{m\log(1/\delta)}/\varepsilon^{2})$ samples to distinguish
between the uniform distribution and an $\varepsilon$-far distribution with
error probability $\delta$.

######  Theorem E.1 (Due to Peebles.).

When $n=\Theta(m)$ and
$\varepsilon=\omega\left(\frac{\log^{1/4}n}{n^{1/8}}\right)$, the collisions
tester has error probability
$\exp\left(-o\left(\frac{n^{2}\varepsilon^{4}}{m}\right)\right)$, and so,
takes $\omega(\sqrt{m\log(1/\delta)}/\varepsilon^{2})$ samples to distinguish
between the uniform distribution and an $\varepsilon$-far distribution with
error probability $\delta$.

###### Proof.

First, let $X_{1},\dots,X_{n}$ be the elements sampled from our distribution.
Let $E_{i,j}$ be the event that $X_{i}=X_{j}$. Under the uniform distribution
$p$, we have that the probability that $X_{i}=X_{j}$ is

$\operatorname*{\mathbb{P}}_{p}[E_{i,j}]=\sum_{j=1}^{m}p_{j}^{2}=\frac{1}{m}$

Thus, the expected number of collisions under the uniform distribution is

$\operatorname*{\mathbb{E}}_{p}\left[\sum_{i<j}E_{i,j}\right]=\sum_{i<j}\operatorname*{\mathbb{E}}_{p}[E_{i,j}]=\binom{n}{2}/m$

Now, consider the $\varepsilon$-far distribution $q$ such that
$q_{j}=\frac{1}{m}+\frac{2\varepsilon}{m}$ for $j\leq m/2$ and
$q_{j}=\frac{1}{m}-\frac{2\varepsilon}{m}$ for $j>m/2$. We have that the
probability that $X_{i}=X_{j}$ under $q$ is

$\operatorname*{\mathbb{P}}_{q}[E_{i,j}]=\sum_{j=1}^{m}q_{j}^{2}=\frac{1}{m}+\sum_{j=1}^{m}\left(q_{j}-\frac{1}{m}\right)^{2}=\frac{1+4\varepsilon^{2}}{m}$

Thus, the expected number of collisions under $q$ is

$\operatorname*{\mathbb{E}}_{q}\left[\sum_{i<j}E_{i,j}\right]=\sum_{i<j}\operatorname*{\mathbb{E}}[E_{i,j}]=\binom{n}{2}\frac{1+4\varepsilon^{2}}{m}$

Now, under $p$, if we sample the first element at least $4n/\sqrt{m}$ times,
then we will have at least
$\binom{4n/\sqrt{m}}{2}>\binom{n}{2}\frac{1+4\varepsilon^{2}}{m}$ collisions
for large enough $n,m$. In this case, since the number of collisions under $p$
is more than the expected number of collisions under $q$, and our threshold
will be less than the expected number of collisions under $q$, we will output
$q$, and make a mistake. This happens with probability at least

$\frac{1}{n^{4n/\sqrt{m}}}=\exp\left(-\frac{4n}{\sqrt{m}}\log n\right)$

This is bigger than $\exp(-\Omega(\frac{n^{2}\varepsilon^{4}}{m}))$, the error
probability of the TV tester, as long as

$\frac{4n}{\sqrt{m}}\log n=o\left(\frac{n^{2}\varepsilon^{4}}{m}\right)$

Since $n=\Theta(m)$, this happens as long as

$\varepsilon=\omega\left(\frac{\log^{1/4}n}{n^{1/8}}\right)$

Thus, for error probability $\delta$, we require
$\omega(\sqrt{m\log(1/\delta)}/\varepsilon^{2})$ samples in the regime stated.
∎

###  E.2 Paninski tester is asymptotically bad when $n\geq\Theta(m\log m)$

######  Theorem E.2.

When $n\geq 48m\log m$, the Paninski tester fails to distinguish between the
uniform distribution on $m$ and an $\varepsilon$-far distribution with error
probability $\Omega(1)$ for $\varepsilon<1/3$.

###### Proof.

Recall that the Paninski tester counts the number of bins that see exactly one
sample. Let $E_{j}=\mathbbm{1}_{\\{Y_{j}=1\\}}$ be the event that the bin $j$
has exactly $1$ sample. Now, for $p$ the uniform distribution on $[m]$, the
expected number of samples that land in the $j^{th}$ bin is

$\operatorname*{\mathbb{E}}_{p}[Y_{j}]=\frac{n}{m}=48\log m$

Thus, by the Bernstein’s inequality,

$\operatorname*{\mathbb{P}}_{p}[Y_{j}\leq\log
m]=\operatorname*{\mathbb{P}}_{p}\left[Y_{j}\leq\left(1-\frac{47}{48}\right)\operatorname*{\mathbb{E}}_{p}[Y_{j}]\right]\leq
e^{-\left(\frac{47}{48}\right)^{2}\times 12\log m}=e^{-3\log
m}\leq\frac{1}{m^{3}}$

So, by union bound,

$\operatorname*{\mathbb{P}}_{p}[\exists j,Y_{j}\leq\log
m]\leq\sum_{j=1}^{m}\operatorname*{\mathbb{P}}_{p}\left[Y_{j}\leq\log
m\right]\leq\frac{1}{m^{2}}$

So, with probability $1-1/m^{2}$, every bin has at least $\log m$ balls, which
means that the Paninski statistic is $0$ with probability $1-1/m^{2}$.

Now, under $\varepsilon$-far distribution $q$ such that
$q_{j}=\frac{1}{m}+\frac{2\varepsilon}{m}$ for $j\leq m/2$ and
$q_{j}=\frac{1}{m}-\frac{2\varepsilon}{m}$ for $j>m/2$, we have, for $j\leq
m/2$

$\operatorname*{\mathbb{E}}_{q}[Y_{j}]=\frac{n}{m}=(1+2\varepsilon)48\log m$

and for $j>m/2$,

$\operatorname*{\mathbb{E}}_{q}[Y_{j}]=\frac{n}{m}=(1-2\varepsilon)48\log m$

Then, for $j\leq m/2$, since $\varepsilon>0$,

$\operatorname*{\mathbb{P}}_{q}[Y_{j}\leq\log
m]=\operatorname*{\mathbb{P}}_{q}\left[Y_{j}\leq\left(1-\frac{47+96\varepsilon}{48+96\varepsilon}\right)\operatorname*{\mathbb{E}}_{q}[Y_{j}]\right]\leq\operatorname*{\mathbb{P}}_{q}\left[Y_{j}\leq\left(1-\frac{47}{48}\right)\operatorname*{\mathbb{E}}_{q}[Y_{j}]\right]\leq\frac{1}{m^{3}}$

On the other hand, for $j>m/2$

$\operatorname*{\mathbb{P}}_{q}[Y_{j}\leq\log
m]=\operatorname*{\mathbb{P}}_{q}[Y_{j}\leq\left(1-\frac{47-96\varepsilon}{48(1-2\varepsilon)}\operatorname*{\mathbb{E}}_{q}[Y_{j}]\right)\leq
e^{-\left(\frac{47-96\varepsilon}{48(1-2\varepsilon)}\right)^{2}\times(1-2\varepsilon)12\log
m}$

Since $\varepsilon<1/3$, this is at most

$e^{-\frac{15^{2}\times 3}{48^{2}}\times 12\log m}\leq\frac{1}{m^{3}}$

Thus, we have that

$\operatorname*{\mathbb{P}}_{q}[\exists j,Y_{j}\leq\log
m]\leq\sum_{j=1}^{m}\operatorname*{\mathbb{P}}_{q}[Y_{j}\leq\log
m]\leq\frac{1}{m^{2}}$

So again, with probability $1-1/m^{2}$, every bin has at least $\log m$ balls
under $q$, so that the Paninski statistic is $0$ with $1-\frac{1}{m^{2}}$.
Putting the above together gives us that we will fail with probability
$\Omega(1)$.

∎

##  Appendix F TV Tester in the Superlinear Regime

######  Lemma F.1.

The TV tester can distinguish between the uniform distribution on $[m]$ and an
$\varepsilon$-far distribution with failure probability
$e^{-\frac{1}{2}\varepsilon^{2}n(1+o(1))}$ when $\varepsilon=o(1)$ and
$n=\omega(m/\varepsilon^{2})$.

###### Proof.

Let $Y$ be the empirical distribution when $n$ samples are drawn from the
distribution. The TV tester compares the empirical distribution $Y$ to the
uniform distribution and outputs uniform if and only if

$\|Y-p\|_{TV}<\frac{\varepsilon}{2}$

where $p$ is the uniform distribution on $[m]$.

Since by the definition of TV distance,

$\|Y-p\|_{TV}=\max_{S\subseteq[m]}\left|Y_{S}-p_{S}\right|$

we have that under the uniform distribution $p$, the probability of failure is

$\operatorname*{\mathbb{P}}_{p}[\|Y-p\|_{TV}\geq\tau^{*}]=\operatorname*{\mathbb{P}}_{p}\left[\max_{S\subseteq[m]}|Y_{S}-p_{S}|\geq\frac{\varepsilon}{2}\right]$

$\leq\sum_{S\subseteq[m]}\operatorname*{\mathbb{P}}_{p}[|Y_{S}-p_{S}|\geq\frac{\varepsilon}{2}]$

Note that the summand is the probability that the empirical mean of $n$
samples from a coin with probability of heads $\frac{|S|}{m}$ deviates from
its expectation by at least $\frac{\varepsilon}{2}$. By the Chernoff bound,
this is at most

$e^{-D\left(\frac{|S|}{m}+\frac{\varepsilon}{2}\|\frac{|S|}{m}\right)n}\leq
e^{-\frac{1}{2}\varepsilon^{2}n}$

since for any $r,\tau$, $D(r+\tau\|r)\geq 2\tau^{2}$.

Thus,

$\operatorname*{\mathbb{P}}_{p}\left[\|Y-p\|_{TV}\geq\frac{\varepsilon}{2}\right]\leq
2^{m}e^{-\frac{1}{2}\varepsilon^{2}n}=e^{-\frac{1}{2}\varepsilon^{2}n(1+o(1))}$

since $n=\omega(m/\varepsilon^{2})$.

Now, under $\varepsilon$-far distribution $q$, since
$\|p-q\|_{TV}\geq\varepsilon$, the set $S=\\{j|q_{j}>p_{j}\\}$ has
$|q_{S}-p_{S}|\geq\varepsilon$ so that $\sum_{j\in
S}q_{j}\geq\frac{|S|}{m}+\varepsilon$. Now, since
$\|Y-p\|_{TV}\geq|Y_{S}-p_{S}|$, we have

$\operatorname*{\mathbb{P}}_{q}\left[\|Y-p\|_{TV}\leq\frac{\varepsilon}{2}\right]\leq\operatorname*{\mathbb{P}}_{q}\left[|Y_{S}-p_{S}|\leq\frac{\varepsilon}{2}\right]$

Now, the RHS of the above is at most the probability that the empirical mean
of $n$ samples from a coin with probability of heads at least
$\frac{1}{2}+\varepsilon$ is less than $\frac{1}{2}+\frac{\varepsilon}{2}$. By
the Chernoff bound, this is at most

$e^{-D(\frac{1}{2}+\frac{\varepsilon}{2}\|\frac{1}{2}+\varepsilon)n}\leq
e^{-\frac{1}{2}n\varepsilon^{2}}$

Thus, the TV tester fails with probability at most
$e^{-\frac{1}{2}n\varepsilon^{2}(1+o(1))}$ as required. ∎

######  Lemma F.2.

When $n=\omega\left(\frac{m}{\varepsilon^{2}}\right)$ and $\varepsilon=o(1)$,
any tester that distinguishes between the uniform distribution on $[m]$ and an
$\varepsilon$-far distribution fails with probability at least
$e^{-\frac{1}{2}n\varepsilon^{2}(1+o(1))}$.

###### Proof.

Let $p$ be the uniform distribution on $[m]$, and let $q$ be the
$\varepsilon$-far distribution such that
$q_{j}=\frac{1}{m}+\frac{2\varepsilon}{m}$ for $j\leq m/2$ and
$q_{j}=\frac{1}{m}-\frac{2\varepsilon}{m}$ for $j>m/2$. Let $Y$ be the
empirical distribution from the samples drawn, and let
$B=\\{\sum_{j=1}^{m/2}Y_{j}\geq\frac{1}{2}+\frac{\varepsilon}{2}\\}$. Under
the uniform distribution, by Lemma F.4,

$\operatorname*{\mathbb{P}}_{p}[B]\geq
e^{-\frac{1}{2}\varepsilon^{2}n(1+o(1))}$ (61)

Now, the likelihood ratio of $Y\in B$ is given by

$\frac{q}{p}(Y)\geq(1+2\varepsilon)^{(\frac{1}{2}+\frac{\varepsilon}{2})n}(1-2\varepsilon)^{(\frac{1}{2}-\frac{\varepsilon}{2})n}$
$=e^{\left(\frac{1}{2}+\frac{\varepsilon}{2}\right)\log\left(1+2\varepsilon\right)n+\left(\frac{1}{2}-\frac{\varepsilon}{2}\right)\log\left(1-2\varepsilon\right)n}$

Now,

$\displaystyle\left(\frac{1}{2}+\frac{\varepsilon}{2}\right)\log\left(1+2\varepsilon\right)+\left(\frac{1}{2}-\frac{\varepsilon}{2}\right)\log\left(1-2\varepsilon\right)$
$\displaystyle=\left(\frac{1}{2}+\frac{\varepsilon}{2}\right)\left\\{\log\left(\frac{\frac{1}{2}+\frac{\varepsilon}{2}}{\frac{1}{2}}\right)-\log\left(\frac{\frac{1}{2}+\frac{\varepsilon}{2}}{\frac{1}{2}+\varepsilon}\right)\right\\}$
$\displaystyle\qquad+\left(\frac{1}{2}-\frac{\varepsilon}{2}\right)\left\\{\log\left(\frac{\frac{1}{2}-\frac{\varepsilon}{2}}{\frac{1}{2}}\right)-\log\left(\frac{\frac{1}{2}-\frac{\varepsilon}{2}}{\frac{1}{2}-\varepsilon}\right)\right\\}$
$\displaystyle=D\left(\frac{1}{2}+\frac{\varepsilon}{2}\|\frac{1}{2}\right)-D\left(\frac{1}{2}+\frac{\varepsilon}{2}\|\frac{1}{2}+\varepsilon\right)$
$\displaystyle=o(\varepsilon^{2})$

since
$D(\frac{1}{2}+\frac{\varepsilon}{2}\|\frac{1}{2})=\frac{\varepsilon^{2}}{2}(1+o(1))$
and
$D(\frac{1}{2}+\frac{\varepsilon}{2}\|\frac{1}{2}+\varepsilon)=\frac{\varepsilon^{2}}{2}(1+o(1))$.
Thus,

$\frac{q}{p}(X)\geq e^{o(\varepsilon^{2})}$ (62)

Now, suppose there is a test $\phi$ that uses $n$ samples and distinguishes
between the two cases with failure probability
$e^{-\left(\frac{1}{2}+\xi\right)n\varepsilon^{2}}$ for $\xi>0$, so that
$\phi=0$ denotes that the test outputs uniform, and $\phi=1$ denotes that the
test outputs far from uniform.

By assumption,

$\operatorname*{\mathbb{P}}_{p}[\phi=1]\leq
e^{-\left(\frac{1}{2}+\xi\right)n\varepsilon^{2}}$

Now,

$\operatorname*{\mathbb{P}}_{q}[\phi=0]\geq\operatorname*{\mathbb{P}}_{q}[\\{\phi=0\\}\cap
B]\geq\frac{q}{p}(\\{\phi=0\\}\cap
B)\operatorname*{\mathbb{P}}_{p}[\\{\phi=0\\}\cap B]$

But by (61) and our assumption,

$\operatorname*{\mathbb{P}}_{p}[\\{\phi=0\\}\cap
B]\geq\operatorname*{\mathbb{P}}_{p}[B]-\operatorname*{\mathbb{P}}_{p}[\phi=1]\geq
e^{-\frac{1}{2}\varepsilon^{2}n(1+o(1))}$

so that, using (62)

$\operatorname*{\mathbb{P}}_{q}[\phi=0]\geq
e^{-\frac{1}{2}\varepsilon^{2}n(1+o(1))}$

Thus, $\phi$ has error probability at least
$e^{-\frac{1}{2}\varepsilon^{2}n(1+o(1))}$, and we have a contradiction, so
that any test fails with probability at least
$e^{-\frac{1}{2}n\varepsilon^{2}(1+o(1))}$. ∎

See 1.3

###### Proof.

By Lemmas F.1 and F.2, the claim follows. ∎

###  F.1 Anticoncentration of a Binomial Variable

In this section we show that the Chernoff bound has sharp constants for
binomial random variables $B(n,\frac{1}{2})$.

We use the following lower bound on binomial coefficients, found in Lemma
4.7.1 of [1]:

######  Lemma F.3.

If $n$ and $np$ are integers, then

$\binom{n}{p}\geq\frac{1}{\sqrt{8np(1-p)}}2^{nh(p)}$

where $h(p):=-p\log_{2}p-(1-p)\log_{2}(1-p)$ is the binary entropy function.

######  Lemma F.4.

Let $X\sim B(n,1/2)$, and $\frac{1}{\sqrt{n}}\ll\varepsilon\ll 1$. Then

$\operatorname*{\mathbb{P}}[X>\frac{n}{2}+\varepsilon
n]=\exp(-2\varepsilon^{2}n(1+o(1)).$

###### Proof.

The upper bound is the standard Chernoff bound, so we focus on the lower
bound. For any $\varepsilon^{\prime}\in[\varepsilon,\varepsilon+3/\sqrt{n}]$
with $\frac{n}{2}+\varepsilon^{\prime}n$ integral we have by Lemma F.3 that

$\displaystyle\operatorname*{\mathbb{P}}[X=\frac{n}{2}+\varepsilon^{\prime}n]$
$\displaystyle=2^{-n}\binom{n}{(1/2+\varepsilon^{\prime})n}$
$\displaystyle\geq\frac{1}{\sqrt{2n(1+o(1))}}2^{-n(1-h(\frac{1}{2}+\varepsilon^{\prime}))}.$

Now, the binary entropy function has Taylor series

$\displaystyle h(\frac{1}{2}+\varepsilon^{\prime})$
$\displaystyle=1-\frac{2}{\ln
2}(\varepsilon^{\prime})^{2}+O((\varepsilon^{\prime})^{4}).$

Since $\varepsilon^{\prime}=\varepsilon(1+o(1))$ by construction, this means

$\operatorname*{\mathbb{P}}[X=\frac{n}{2}+\varepsilon^{\prime}n]\geq\frac{1}{\sqrt{2n(1+o(1))}}e^{-2n\varepsilon^{2}(1+o(1))}.$

Summing over the $3\sqrt{n}$ such $\varepsilon^{\prime}$, we have

$\operatorname*{\mathbb{P}}[X\geq\frac{n}{2}+\varepsilon n]\geq
e^{-2n\varepsilon^{2}(1+o(1))}$

as desired. ∎

##  Appendix G Squared Statistic in Sublinear Regime

Define a centering function

$\phi(k):=\left|k-\frac{n}{m}\right|$ (39)

We will analyze the squared statistic $S$ given by

$S=\sum_{j=1}^{m}\phi(Y_{j}^{n})^{2}$

where $Y_{j}^{n}=\sum_{i=1}^{n}1_{X_{i}=j}$ and $X_{1},\dots,X_{n}$ are the
$n$ samples drawn from distribution $\nu$ supported on $[m]$. Note that this
is equivalent to the collisions statistic, since it simply applies a
translation and scaling. We will set

$\beta:=\kappa\frac{n^{2}\varepsilon^{4}}{m}$ (63)

for constant $\kappa>0$ to be set later. We also define a parameter $\Delta$.

######  Assumption 4.

$1\lesssim n/m\ll\frac{1}{\varepsilon^{2}}$,
$\varepsilon\ll\frac{1}{n^{3/13}}$, $\frac{n^{2}}{m}\varepsilon^{4}\gg\log m$
and $m\geq C\log n$ for sufficiently large constant $C$. In addition, we have
the following constraints on $\beta$ and $\Delta$.

$\beta=\omega\left(\log\left(\frac{1}{\Delta}\right)+\sqrt{\frac{n}{m}\log\left(\frac{1}{\Delta}\right)}\right)$
(13) $\displaystyle\Delta=O\left(\frac{n\varepsilon^{2}}{m}\right)$ (14)
$(\beta^{2}\varepsilon^{2})^{3}=o\left(\Delta^{2}\right)$ (15)

We assume that Assumption 4 holds throughout this section. Observe that
Assumption 4 implies Assumption 2. Note that since $n=\Theta(m)$ and
$\frac{n^{2}\varepsilon^{4}}{m}=\omega(\log m)$, we have that

$\varepsilon=\omega\left(\frac{\log m}{n^{1/4}}\right)$ (64)

For ease of exposition, we will analyze

$\tilde{S}=\frac{m}{n^{2}\varepsilon^{2}}[S-n]$ (65)

We will study the log MGF of this statistic conditioned on all
$\phi(Y_{j}^{n})$’s at most $\beta$, given by

$\Lambda_{n,\nu}:=\log\left(\operatorname*{\mathbb{E}}_{\nu}\left[\exp(\theta\tilde{S})|\forall
j,\phi(Y_{j}^{n})\leq\beta\right]\right)$ (66)

We will compute an asymptotic expansion of the limiting log MGF conditioned on
all $\phi(Y_{j}^{n})$ at most $\beta$ given by

$\Lambda_{\nu}(\theta):=\lim_{n\to\infty}\frac{m}{n^{2}\varepsilon^{4}}\Lambda_{n,\nu}\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\right)$
(67)

###  G.1 Poissonization

Let $\tilde{S}_{Poi(\lambda)}$ be the Poissonized statistic. We compute the
conditional MGF of $\tilde{S}_{Poi(\lambda)}$ with MGF parameter
$\frac{n^{2}\varepsilon^{4}}{m}\theta$ conditioned on it being the case that
$\phi(Z_{j})\leq\beta$ for all $j$. That is,

$A_{\lambda}(\theta):=\exp(-\varepsilon^{2}\theta
n)\operatorname*{\mathbb{E}}\left[\mathbbm{1}_{\\{\forall
j,\phi(Z_{j})\leq\beta\\}}\exp\left(\varepsilon^{2}\theta\sum_{j=1}^{m}\phi(Z_{j})^{2}\right)\right]$
(68)

where $Z_{j}\sim Poi(\lambda\nu_{j})$ and are independent. Due to this
independence,

$A_{\lambda}(\theta)=\exp(-\varepsilon^{2}\theta
n)\prod_{j=1}^{m}\operatorname*{\mathbb{E}}\left[\mathbbm{1}_{\\{\phi(Z_{j})\leq\beta\\}}\exp\left(\varepsilon^{2}\theta\phi(Z_{j})^{2}\right)\right]$

######  Lemma G.1.

Suppose Assumption 4 holds. We have,

$\displaystyle\varepsilon^{2}\theta\operatorname*{\mathbb{E}}[\mathbbm{1}_{\\{\phi(Z_{j})\leq\beta\\}}\phi(Z_{j})^{2}]=\varepsilon^{2}\theta\operatorname*{\mathbb{E}}[\phi(Z_{j})^{2}]+o(\Delta^{2})$
$\displaystyle\frac{\varepsilon^{4}\theta^{2}}{2}\operatorname*{\mathbb{E}}\left[\mathbbm{1}_{\\{\phi(Z_{j})\leq\beta\\}}\phi(Z_{j})^{4}\right]=\frac{\varepsilon^{4}\theta^{2}}{2}\operatorname*{\mathbb{E}}[\phi(Z_{j})^{4}]+o(\Delta^{2})$
$\displaystyle\sum_{l=3}^{\infty}\frac{(\varepsilon^{2}\theta)^{l}}{l!}\operatorname*{\mathbb{E}}\left[\mathbbm{1}_{\\{\phi(Z_{j})\leq\beta\\}}\phi(Z_{j})^{2l}\right]=o(\Delta^{2})$

when $Z_{j}\sim Poi(\lambda\nu_{j})$ for $\lambda=n(1+O(\varepsilon^{2}))$ and
$\nu_{j}=1/m+O(\varepsilon/m)$ for all $j$.

###### Proof.

For the first claim,

$\varepsilon^{2}\theta\operatorname*{\mathbb{E}}[\mathbbm{1}_{\\{\phi(Z_{j})\leq\beta\\}}\phi(Z_{j})^{2}]=\varepsilon^{2}\theta\operatorname*{\mathbb{E}}[\phi(Z_{j})^{2}]-\varepsilon^{2}\theta\operatorname*{\mathbb{E}}[\mathbbm{1}_{\\{\phi(Z_{j})>\beta\\}}\phi(Z_{j})^{2}]$

By Lemma D.8, the second term is $o(\Delta^{2})$. Thus, we have the first
claim. The second claim can be proved in a similar way. The third claim
follows by Lemma D.5. ∎

###  G.2 Depoissonization

As before, we will first show that $A_{\lambda}(\theta)$ is analytic in
$\lambda$.

######  Lemma G.2.

$A_{\lambda}(\theta)$ is analytic in $\lambda$.

###### Proof.

We will show that
$\operatorname*{\mathbb{E}}[\mathbbm{1}_{\\{\phi(Z_{j})\leq\beta\\}}\exp(\varepsilon^{2}\theta\phi(Z_{j})^{2})]$
is analytic. We have that it can be written as

$\sum_{k:\phi(k)\leq\beta}\left[\frac{(\lambda\nu_{j})^{k}}{k!}e^{-\lambda\nu_{j}}\exp(\varepsilon^{2}\theta\phi(k)^{2})\right]$

which is a finite sum of analytic functions, and is thus analytic. The claim
follows. ∎

Note that for $A_{\lambda}(\theta)$ defined in (68), by Lemmas G.1 and G.2,
Assumption 3 holds for

$\xi(k)=\mathbbm{1}_{\\{\phi(k)\leq\beta\\}}\exp(\varepsilon^{2}\theta\phi(k)^{2})$

Then, we have the following

######  Lemma G.3.

We have that for uniform distribution $p$ such that $p_{j}=1/m$ for all $j$,

$\operatorname*{\mathbb{E}}_{p}\left[\exp\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\tilde{S}\right)|\forall
j,\phi(Y_{j}^{n})\leq\beta\right]=\exp(-\varepsilon^{2}\theta
n)\operatorname*{\mathbb{E}}_{p}\left[\exp\left(\varepsilon^{2}\theta\sum_{j=1}^{m}\mathbbm{1}_{\\{\phi(Y_{j}^{n})\leq\beta\\}}\phi(Y_{j}^{n})^{2}\right)\right]$
$=(1+O(1/n))\exp\left\\{\frac{n^{2}\varepsilon^{4}}{m}(\theta^{2}+o(1))\right\\}$

and for alternate distributions $q$ such that
$q_{j}=\frac{1}{m}+\frac{\varepsilon}{\gamma m}$ for $j\leq l$ and
$\nu_{j}=\frac{1}{m}-\frac{\varepsilon}{(1-\gamma)m}$ for $j>l$,

$\operatorname*{\mathbb{E}}_{q}\left[\exp\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\tilde{S}\right)|\forall
j,\phi(Y_{j}^{n})\leq\beta\right]=\exp(-\varepsilon^{2}\theta
n)\operatorname*{\mathbb{E}}_{q}\left[\exp\left(\varepsilon^{2}\theta\sum_{j=1}^{m}\mathbbm{1}_{\\{\phi(Y_{j}^{n})\leq\beta\\}}\phi(Y_{j}^{n})^{2}\right)\right]$

$=(1+O(1/n))\exp\left\\{\frac{n^{2}\varepsilon^{4}}{m}\left[\theta^{2}+\theta\frac{1}{\gamma(1-\gamma)}+o(1)\right]\right\\}$

###### Proof.

By Lemma C.4, the claim holds. ∎

###  G.3 Application of the Gärtner-Ellis Theorem

In this section, we apply the Gärtner-Ellis Theorem to obtain the probability
that our statistic crosses a threshold, under the uniform distribution, and
under one of the worst-case $\varepsilon$-far distributions.

######  Lemma G.4.

Under the uniform distribution $p$, we have that for $\tau>0$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{p}\left[\tilde{S}\geq\tau|\forall
j,\phi(Y_{j}^{n})\leq\beta\right]\right)=\frac{\tau^{2}}{4}$

Under an $\varepsilon$-far distribution $q$ of the form
$q_{j}=\frac{1}{m}+\frac{\varepsilon}{\gamma m}$ for $j\leq l$ and
$q_{j}=\frac{1}{m}-\frac{\varepsilon}{(1-\gamma)m}$ for $j>l$, and
$\gamma=\Theta(1)$, $1-\gamma=\Theta(1)$, for
$\tau<\frac{1}{\gamma(1-\gamma)}$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{q}\left[\tilde{S}\leq\tau|\forall
j,\phi(Y_{j}^{n})\leq\beta\right]\right)=\frac{\left(\tau\gamma(\gamma-1)+1\right)^{2}}{4\gamma^{2}(\gamma-1)^{2}}$

###### Proof.

Note that by Lemma G.3, the limiting logarithmic moment generating function
with respect to the uniform distribution $p$ is given by

$\Lambda_{p}(\theta)=\lim_{n\to\infty}\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{E}}_{p}\left[\exp\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\tilde{S}\right)|\forall
j,\phi(Y_{j}^{n})\leq\beta\right]\right)=\theta^{2}$

Thus, Assumption 1 holds for $\mathcal{D}_{\Lambda_{p}}=\mathbb{R}$.
Furthermore, the Fenchel-Legendre Transform (defined in equation 30) of
$\Lambda_{p}$ is given by

$\Lambda_{p}^{*}(\tau)=\sup_{\theta}\\{\theta\tau-\theta^{2}\\}=\frac{\tau^{2}}{4}$

This is a strongly convex function of $\tau$, so the set of exposed points of
$\Lambda_{p}^{*}$ whose exposing hyperplane belongs to
$\mathcal{D}_{\Lambda_{p}}^{o}$ is all of $\mathbb{R}$. Thus, by the Theorem
B.2 (Gärtner-Ellis), for $\tau>0$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{p}\left[\tilde{S}\geq\tau|\forall
j,\phi(Y_{j}^{n})\leq\beta\right]\right)=\inf_{x\geq\tau}\Lambda_{p}^{*}(x)=\frac{\tau^{2}}{4}$

Similarly, the limiting logarithmic moment generating function with respect to
an alternate distribution $q$ is given by

$\Lambda_{q}(\theta)=\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{E}}_{q}\left[\exp\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\tilde{S}\right)|\forall
j,\phi(Y_{j}^{n})\leq\beta\right]\right)=\theta^{2}+\frac{1}{\gamma(1-\gamma)}\theta$

The Fenchel-Legendre transform is given by

$\Lambda_{q}^{*}(\tau)=\sup_{\theta}\left\\{\theta\tau-\theta^{2}-\frac{1}{\gamma(1-\gamma)}\theta\right\\}=\frac{\left(\tau\gamma(\gamma-1)+1\right)^{2}}{4\gamma^{2}(\gamma-1)^{2}}$

Again, applying the Gärtner-Ellis Theorem gives, for
$\tau<\frac{1}{\gamma(1-\gamma)}$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{q}\left[\tilde{S}_{n}^{*}\leq\tau|\forall
j,\phi(Y_{j}^{n})\leq\beta\right]\right)=\inf_{x\leq\tau}\Lambda^{*}_{q}(x)=\frac{\left(\tau\gamma(\gamma-1)+1\right)^{2}}{4\gamma^{2}(\gamma-1)^{2}}$

∎

###  G.4 Removing the conditioning

So far, we have analyzed the probability that $\tilde{S}$ crosses a threshold
$\tau$ under the uniform distribution, and under a family of $\varepsilon$-far
distributions conditioned on the event that $\phi(Y_{j}^{n})\leq\beta$ for all
$j$. We will now remove this conditioning.

######  Lemma G.5.

Under the uniform distribution $p$, we have that for $\tau>0$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{p}\left[\tilde{S}\geq\tau\right]\right)=\frac{\tau^{2}}{4}$

Under an $\varepsilon$-far distribution $q$ for the form
$q_{j}=\frac{1}{m}+\frac{\varepsilon}{\gamma m}$ for $j\leq l$ and
$q_{j}=\frac{1}{m}-\frac{\varepsilon}{(1-\gamma)m}$ for $j>l$, and
$\gamma=\Theta(1)$, $1-\gamma=\Theta(1)$, for
$\tau<\frac{1}{\gamma(1-\gamma)}$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{q}\left[\tilde{S}\leq\tau\right]\right)=\frac{(\tau\gamma(\gamma-1)+1)^{2}}{4\gamma^{2}(\gamma-1)^{2}}$

###### Proof.

For the uniform distribution we will upper and lower bound
$\operatorname*{\mathbb{P}}_{p}[\tilde{S}\geq\tau]$ by

$e^{\frac{n^{2}\varepsilon^{4}}{m}\frac{\tau^{2}}{4}(1+o(1))}$

The claim for the uniform distribution will follow.

Under any distribution $\nu$,

$\operatorname*{\mathbb{P}}_{\nu}\left[\tilde{S}\geq\tau\right]=\operatorname*{\mathbb{P}}_{\nu}\left[\tilde{S}\geq\tau|\forall
j,\phi(Y_{j}^{n})\leq\beta\right]\operatorname*{\mathbb{P}}_{\nu}[\forall
j,\phi(Y_{j}^{n})\leq\beta]$
$+\operatorname*{\mathbb{P}}_{\nu}\left[\tilde{S}\geq\tau|\exists
j,\phi(Y_{j}^{n})>\beta\right]\operatorname*{\mathbb{P}}_{\nu}[\exists
j,\phi(Y_{j}^{n})>\beta]$

Now, by Bernstein’s inequality, since $n\varepsilon^{4}=\omega(1)$ by (64) and
$\beta=\kappa\frac{n^{2}\varepsilon^{4}}{m}$, we have, for the uniform
distribution $p$, for every $j$,

$\operatorname*{\mathbb{P}}_{p}[\phi(Y_{j}^{n})>\beta]\leq
2e^{-\frac{\kappa}{4}\frac{n^{2}\varepsilon^{4}}{m}}$

Thus, by union bound,

$\operatorname*{\mathbb{P}}_{p}\left[\exists
j,\phi(Y_{j}^{n})>\beta\right]\leq\sum_{j=1}^{m}\operatorname*{\mathbb{P}}_{p}[\phi(Y_{j}^{n})>\beta]\leq
2me^{-\frac{\kappa n^{2}\varepsilon^{4}}{4m}}=2e^{-\frac{\kappa
n^{2}\varepsilon^{4}}{4m}+\log m}=2e^{-\frac{\kappa
n^{2}\varepsilon^{4}}{4m}(1+o(1))}$

since $\frac{n^{2}\varepsilon^{4}}{m}=\omega(\log m)$. For
$\operatorname*{\mathbb{P}}_{p}[\forall j,\phi(Y_{j}^{n})\leq\beta]$ and
$\operatorname*{\mathbb{P}}_{p}[\tilde{S}\geq\tau|\exists
j,\phi(Y_{j}^{n})>\beta]$, we apply the trivial upper bound of $1$. So, for
$\kappa\geq 2\tau^{2}$, by Lemma G.4,

$\operatorname*{\mathbb{P}}_{p}[\tilde{S}\geq\tau]\leq
e^{-\frac{\tau^{2}}{4}\frac{n^{2}\varepsilon^{4}}{m}}+2e^{-\frac{\tau^{2}}{2}\frac{n^{2}\varepsilon^{4}}{m}(1+o(1))}=e^{-\frac{\tau^{2}}{4}\frac{n^{2}\varepsilon^{4}}{m}}(1+o(1))$

For the lower bound, note that

$\operatorname*{\mathbb{P}}_{p}[\forall j,\phi(Y_{j}^{n})\leq\beta]\geq
1-\sum_{j}\operatorname*{\mathbb{P}}_{p}[\phi(Y_{j}^{n})>\beta]\geq
1-2me^{-\frac{\kappa}{4}\frac{n^{2}\varepsilon^{4}}{m}}=1-2e^{-\frac{\kappa}{4}\frac{n^{2}\varepsilon^{4}}{m}(1+o(1))}$

For the second term, i.e.,
$\operatorname*{\mathbb{P}}_{p}\left[\tilde{S}\geq\tau|\exists
j,\phi(Y_{j}^{n})>\beta\right]\operatorname*{\mathbb{P}}_{p}[\exists
j,\phi(Y_{j}^{n})>\beta]$, we apply the trivial lower bound of $0$. Again,
setting $\kappa\geq 2\tau^{2}$, we get

$\operatorname*{\mathbb{P}}_{p}\left[\tilde{S}\geq\tau\right]\geq
e^{-\frac{n^{2}\varepsilon^{4}}{m}\frac{\tau^{2}}{4}(1+o(1))}$

So, we have the claim for the uniform distribution. We will upper and lower
bound the probability of crossing $\tau$ for $\varepsilon$-far distribution
$q$ in the same way. For ease, let

$c_{\tau}:=\frac{(\tau\gamma(\gamma-1)+1)^{2}}{4\gamma^{2}(\gamma-1)^{2}}$

By Bernstein’s inequality, we have that since $\gamma=\Theta(1)$ and
$1-\gamma=\Theta(1)$ so that $q_{j}=1/m+O(\varepsilon/m)$ for every $j$, and
since $n\varepsilon^{4}=\omega(1)$ by (64) and
$\beta=\kappa\frac{n^{2}\varepsilon^{4}}{m}$, for every $j$, under
$\varepsilon$-far distribution $q$,

$\operatorname*{\mathbb{P}}_{q}[\phi(Y_{j}^{n})>\beta]\leq
2e^{-\frac{\kappa}{4}\frac{n^{2}\varepsilon^{4}}{m}(1+o(1))}$

Then, setting $\kappa\geq 8c_{\tau}$, and repeating the same argument as in
the uniform case, we obtain the required upper and lower bounds on
$\operatorname*{\mathbb{P}}_{q}[\tilde{S}\leq\tau]$. The claim follows. ∎

###  G.5 Setting the threshold

We need to set our threshold $\tau$ so that the minimum of the error
probability under the uniform distribution $p$, and any $\varepsilon$-far
distribution $q$ is maximized. Note that, it is sufficient to consider a
threshold $\tau$ such that $0<\tau<\frac{1}{\gamma(1-\gamma)}$, since
otherwise, the error probability in one of the two cases is at least constant.
To set our threshold, we will first observe that for any $\tau$ in this range,
the “error exponent” under $\varepsilon$-far distributions is minimized for a
particular $\varepsilon$-far distribution. Then, we will set the threshold to
maximize the minimum of the error exponent under the uniform distribution, and
under this $\varepsilon$-far distribution.

######  Lemma G.6.

Setting the threshold $\tau=2$, we have for the uniform distribution $p$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{p}\left[\tilde{S}\geq\tau\right]\right)=1$

and for any $\varepsilon$-far distribution $q$ such that
$q_{j}=\frac{1}{m}+\frac{\varepsilon}{\gamma m}$ for $j\leq l$ and
$q_{j}=\frac{1}{m}-\frac{\varepsilon}{(1-\gamma)m}$ for $j>l$ and
$\gamma=\Theta(1),1-\gamma=\Theta(1)$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{q}\left[\tilde{S}\leq\tau\right]\right)\geq
1$

with equality for $q$ such that $q_{j}=1/m+2\varepsilon/m$ for $j\leq m/2$ and
$q_{j}=1/m-2\varepsilon/m$ for $j>m/2$.

###### Proof.

By Lemma G.5, for $0<\tau<\frac{1}{\gamma(1-\gamma)}$,

$\lim_{n\to\infty}\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{q}\left[\tilde{S}\leq\tau\right]\right)=\frac{\left(\tau\gamma(\gamma-1)+1\right)^{2}}{4\gamma^{2}(\gamma-1)^{2}}$

Now, the numerator of the right hand side is minimized when $\gamma=1/2$, and
the denominator is maximized when $\gamma=1/2$. Thus, the right hand side is
minimized when $\gamma=1/2$. So, we have that,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{q}\left[\tilde{S}\leq\tau\right]\right)\geq\frac{1}{4}(\tau-4)^{2}$

with equality for distribution $q$ such that $q_{j}=1/m+2\varepsilon/m$ for
$j\leq m/2$ and $q_{j}=1/m-2\varepsilon/m$ for $j>m/2$.

Then, the claim follows by substituting in $\tau=2$ in the expression for the
uniform distribution in Lemma C.13 and in the above expression. ∎

Recall that our target sample complexity is

$\displaystyle n=(1+o(1))\sqrt{m\log\frac{1}{\delta}}/\varepsilon^{2}$ (4)

We have our result for the squared/collisions tester. See 1.4

###### Proof.

We need to show that we can satisfy (14), (13) and (15) for the $\beta$ that
we chose in (63), and some $\Delta$. Set

$\Delta=\frac{n\varepsilon^{2}}{m}=\Theta(\varepsilon^{2})$

so that (14) is satisfied. Now,

$\beta=\kappa\frac{n^{2}\varepsilon^{4}}{m}=\omega(\log
m)=\omega\left(\log\left(\frac{1}{\Delta}\right)\right)$

and since $n=\Theta(m)$,

$\beta=\kappa\frac{n^{2}\varepsilon^{4}}{m}=\Theta\left(\sqrt{\frac{n}{m}}\frac{n^{2}\varepsilon^{4}}{m}\right)=\omega\left(\sqrt{\frac{n}{m}}\log
m\right)=\omega\left(\sqrt{\frac{n}{m}\log\left(\frac{1}{\Delta}\right)}\right)$

Thus, (13) is satisfied. For (15), note that

$\left(\beta^{2}\varepsilon^{2}\right)^{3}=\Theta\left(\left(\frac{n^{4}\varepsilon^{10}}{m^{2}}\right)^{3}\right)=\Theta\left(\frac{n^{12}\varepsilon^{30}}{m^{6}}\right)=\Theta\left(n^{6}\varepsilon^{30}\right)=o(\varepsilon^{4})=o(\Delta^{2})$

since $\varepsilon=o\left(\frac{1}{n^{3/13}}\right)$. So, the conditions are
satisfied.

By Lemma G.6, we have that $\bar{c}(\varepsilon,m,C)=1$ for every
$\varepsilon$ that satisfies our assumptions, and every $C>2$. In particular,
any $\varepsilon^{\prime}$ such that
$\left(1-\frac{1}{C^{\prime}}\right)\varepsilon(n)\leq\varepsilon^{\prime}(n)\leq\varepsilon(n)$
has $\bar{c}(\varepsilon^{\prime},m,C)=1$ for every $C>2$. Thus, by Lemma
B.10, we have that $c(\varepsilon,m)=1$ for every $\varepsilon$ that satisfies
our assumptions. The claim follows. ∎

##  Appendix H Empty bins statistic in Sublinear Regime

######  Assumption 5.

$n/m\lesssim 1$, $\varepsilon,\delta\ll 1$, $n\gg 1$.

We will assume that Assumption 5 holds throughout this section. Let our
statistic be

$S:=\sum_{j=1}^{m}\mathbbm{1}_{\\{Y_{j}^{n}=0\\}}$

where $Y_{j}^{n}=\sum_{i=1}^{n}\mathbbm{1}_{\\{X_{i}=j\\}}$, and
$X_{1},\dots,X_{n}$ are the $n$ samples drawn from the distribution $\nu$
supported on $[m]$. In other words, it is the number of empty bins. Note that
this has the same error probability as the total variation statistic when
$n\leq m$. For ease of exposition, we will analyze the statistic

$\tilde{S}=\frac{m}{n^{2}\varepsilon^{2}}[S-me^{-n/m}]$ (69)

Note that this has the same error probability as $S$. Consider the moment
generating function (MGF) of $\tilde{S}$ with respect to distribution $\nu$,
given by

$M_{\tilde{S},\nu}(\theta)=\operatorname*{\mathbb{E}}_{\nu}\left[\exp(\theta\tilde{S})\right]$

Note that the logarithmic moment generating function of this statistic is
given by

$\Lambda_{n,\nu}(\theta):=\log(\operatorname*{\mathbb{E}}_{\nu}[\exp(\theta\tilde{S})])$
(70)

We wish to study the error exponent [22] of this statistic with respect to
normalization $\frac{n^{2}\varepsilon^{4}}{m}$. To do this, we will compute
the asymptotic expansion of the limiting logarithmic moment generating
function of the statistic, given by

$\Lambda_{\nu}(\theta):=\lim_{n\to\infty}\frac{m}{n^{2}\varepsilon^{4}}\Lambda_{n,\nu}(\frac{n^{2}\varepsilon^{4}}{m}\theta)$
(71)

###  H.1 Poissonization

Define $\tilde{S}_{Poi(\lambda)}$ to be the Poissonized statistic, that is the
statistic $\tilde{S}$ when the number of samples is chosen according to the
Poisson distribution with mean $\lambda$. We begin by computing the MGF of
$\tilde{S}_{Poi(\lambda)}$ with MGF parameter
$\frac{n^{2}\varepsilon^{4}}{m}\theta$. Let this be

$A_{\lambda}(\theta):=\operatorname*{\mathbb{E}}\left[\exp\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\tilde{S}_{Poi(\lambda)}\right)\right]=\exp\left(-me^{-n/m}\varepsilon^{2}\theta\right)\operatorname*{\mathbb{E}}\left[\exp\left(\varepsilon^{2}\theta\sum_{j=1}^{m}\mathbbm{1}_{\\{Z_{j}=0\\}}\right)\right]$

where $Z_{j}\sim Poi(\lambda\nu_{j})$ are independent. Due to this
independence,

$A_{\lambda}(\theta)=\exp\left(-me^{-n/m}\varepsilon^{2}\theta\right)\prod_{j=1}^{m}\operatorname*{\mathbb{E}}\left[\exp\left(\varepsilon^{2}\theta\mathbbm{1}_{\\{Z_{j}=0\\}}\right)\right]$
(72)

Now, we have the following.

######  Lemma H.1.

$\operatorname*{\mathbb{E}}\left[\exp\left(\varepsilon^{2}\theta\mathbbm{1}_{\\{Z_{j}=0\\}}\right)\right]=e^{-\lambda\nu_{j}}e^{\varepsilon^{2}\theta}-e^{-\lambda\nu_{j}}+1$

when $Z_{j}\sim Poi(\lambda\nu_{j})$.

###### Proof.

$\displaystyle\operatorname*{\mathbb{E}}\left[\exp\left(\varepsilon^{2}\theta\mathbbm{1}_{\\{Z_{j}=0\\}}\right)\right]$
$\displaystyle=\exp(\varepsilon^{2}\theta)\operatorname*{\mathbb{P}}[Z_{j}=0]+\sum_{k=1}^{\infty}\operatorname*{\mathbb{P}}[Z_{j}=k]$
$\displaystyle=\exp(\varepsilon^{2}\theta)\operatorname*{\mathbb{P}}[Z_{j}=0]+1-\operatorname*{\mathbb{P}}[Z_{j}=0]=e^{-\lambda\nu_{j}}e^{\varepsilon^{2}\theta}-e^{-\lambda\nu_{j}}+1$

∎

###  H.2 Depoissonization

First, we will show that $A_{\lambda}(\theta)$ is analytic in $\lambda$.

######  Lemma H.2.

$A_{\lambda}(\theta)$ is analytic in $\lambda$.

###### Proof.

By Lemma H.1,
$\operatorname*{\mathbb{E}}[\exp(\varepsilon^{2}\theta\mathbbm{1}_{\\{Z_{j}=0\\}})]$
is analytic $\lambda$ since it is the finite sum of analytic functions. Then,
$A_{\lambda}(\theta)$ is the finite product of analytic functions, and is
hence analytic. The claim follows. ∎

######  Lemma H.3.

$M_{\tilde{S},\nu}\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\right)=\frac{n!}{2\pi
i}\oint\frac{e^{\lambda}}{\lambda^{n+1}}A_{\lambda}(\theta)d\lambda$ (73)

###### Proof.

Follows from Lemma C.5 since $A_{\lambda}(\theta)$ is analytic in $\lambda$. ∎

We will choose a contour passing through a particular $\lambda_{0}$, and this
will make it easy to evaluate the integral. We carry out the integration along
the contour given by $\lambda=\lambda_{0}e^{i\psi}$, where

$\lambda_{0}=n(1+e^{-n/m}\varepsilon^{2}\theta)$ (74)

We substitute $\lambda=\lambda_{0}e^{i\psi}$ and $A_{\lambda}(\theta)$ from
(72) into (73) to get that

$M_{\tilde{S},\nu}\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\right)=\exp\left(-me^{-n/m}\varepsilon^{2}\theta\right)\frac{n!}{2\pi}\lambda_{0}^{-n}Re\left[\int_{-\pi}^{\pi}g(\psi)d\psi\right]$
(75)

with

$g(\psi):=e^{-in\psi}e^{\lambda_{0}e^{i\psi}}\prod_{j=1}^{m}\left\\{e^{-\lambda_{0}\nu_{j}e^{i\psi}}e^{\varepsilon^{2}\theta}-e^{-\lambda_{0}\nu_{j}e^{i\psi}}+1\right\\}$
(76)

We will split this integral into $3$ parts. Let

$\begin{gathered}I_{1}=Re\left[\int_{-\pi/3}^{\pi/3}g(\psi)d\psi\right]\\\
I_{2}=Re\left[\int_{-\pi}^{-\pi/3}g(\psi)d\psi\right]\\\
I_{3}=Re\left[\int_{\pi/3}^{\pi}g(\psi)d\psi\right]\end{gathered}$ (77)

We will show that $I_{1}$ dominates. We show this by bounding $g(\psi)$ in the
region $\psi\in[-\pi,-\pi/3]\cup[\pi/3,\pi]$ as follows.

######  Lemma H.4.

For $\psi\in[-\pi,-\pi/3]\cup[\pi/3,\pi]$,

$|g(\psi)|\leq\exp\\{0.5n(1+O(\varepsilon^{2}))+0.5me^{-n/m}\varepsilon^{2}\theta(1+O(\varepsilon^{2}))\\}$

###### Proof.

By definition of $g$ from (76) and Lemma H.15, we have that for $Z_{j}\sim
Poi(\lambda_{0}\nu_{j})$,

$\displaystyle|g(\psi)|$
$\displaystyle=\left|e^{-in\psi}e^{\lambda_{0}e^{i\psi}}\prod_{j=1}^{m}\left\\{e^{-\lambda_{0}\nu_{j}e^{i\psi}}e^{\varepsilon^{2}\theta}-e^{-\lambda_{0}\nu_{j}e^{i\psi}}+1\right\\}\right|$
$\displaystyle=\Big{|}e^{-in\psi}e^{\lambda_{0}e^{i\psi}}\exp\left\\{me^{-\frac{n}{m}e^{i\psi}}\varepsilon^{2}\theta(1+O(\varepsilon^{2}))+O(n\varepsilon^{3})\right\\}\Big{|}$

Since $\lambda_{0}=n(1+O(\varepsilon^{2}))$, this is

$\Big{|}e^{-in\psi}\exp\\{ne^{i\psi}+me^{-\frac{n}{m}e^{i\psi}}\varepsilon^{2}\theta(1+O(\varepsilon^{2}))+O(n\varepsilon^{2})\\}\Big{|}$

The claim follows since $|e^{-in\psi}|=1$ and

$|\exp(e^{i\psi})|=|\exp(\cos(\psi)+i\sin(\psi))|=\exp(\cos(\psi))\leq\exp(0.5)$

for $\psi$ in the range stated. ∎

Note that this implies that for the integrals defined in (77) that

$I_{2}+I_{3}=O(e^{0.6n+0.6me^{-n/m}\varepsilon^{2}\theta})$ (78)

Now, we will compute $I_{1}$. Define $G(\psi):=\log(g(\psi))$. Then, by
definition of $g$ in (76),

$G(\psi)=-in\psi+\lambda_{0}e^{i\psi}+\sum_{j=1}^{m}\log\left\\{e^{-\lambda_{0}\nu_{j}e^{i\psi}}e^{\varepsilon^{2}\theta}-e^{-\lambda_{0}\nu_{j}e^{i\psi}}+1\right\\}$
(79)

Note that

$\text{Im}(G(0))=0$ (80)

Then, applying Lemma D.14,

$\text{Re}(G^{\prime}(0))=0$ (81)

Now, computing the asymptotic expansion of $G^{\prime\prime}(\psi)$ by Lemma
H.16, we have

$G^{\prime\prime}(\psi)=-ne^{i\psi}+O\left(n\varepsilon^{2}\right)$ (82)

Now, by Taylor’s theorem, for any $\psi\in[-\pi/3,\pi/3]$ there exists
$\tilde{\psi}\in(0,\psi)$ such that

$G(\psi)=G(0)+G^{\prime}(0)\psi+\frac{G^{\prime\prime}(\tilde{\psi})}{2}\psi^{2}$
(83)

But, by (82), $Re[G^{\prime\prime}(\psi)]\leq-0.4n$ for any
$\psi\in[-\pi/3,\pi/3]$. So, for $\psi\in[-\pi/3,\pi/3]$,

$Re(G(\psi))\leq G(0)-0.2n\psi^{2}$ (84)

Now, we have the following upper bound on $I_{1}$.

######  Lemma H.5.

$I_{1}\leq e^{G(0)}\frac{\sqrt{\pi}}{\sqrt{0.2n}}$

###### Proof.

$I_{1}=Re\left[\int_{-\pi/3}^{\pi/3}e^{G(\psi)}d\psi\right]\leq\int_{-\pi/3}^{\pi/3}e^{Re(G(\psi))}d\psi\leq
e^{G(0)}\int_{-\pi/3}^{\pi/3}e^{-0.2n\psi^{2}}d\psi$ (85)

∎

$\leq
e^{G(0)}\int_{-\infty}^{\infty}e^{-0.2n\psi^{2}}d\psi=e^{G(0)}\frac{\sqrt{\pi}}{\sqrt{0.2n}}$

The next lemma shows that $I_{1}$ is also lower bounded by the above quantity
(up to constants).

######  Lemma H.6.

$I_{1}\geq e^{G(0)}\frac{0.5\sqrt{\pi}}{\sqrt{1.1n}}(1+o(1))$

where $I_{1}$ is defined in (77)

###### Proof.

By (82),
$\text{Im}(G^{\prime\prime}(\psi))=-n\sin(\psi)+O\left(n\varepsilon^{2}\right)$.
So, for large enough $n$, since $|\sin(\psi)|\leq|\psi|$, for any
$\psi\in[-\pi/3,\pi/3]$, $|\text{Im}(G^{\prime\prime}(\psi))|\leq 1.1n|\psi|$.
So, by (83), (80) and (81), we have that for constant $c>0$ and
$\psi\in[-\pi/3,\pi/3]$,

$|\text{Im}(G(\psi))|\leq 1.1n|\psi|^{3}+cn\varepsilon^{2}\psi^{2}$

Also, $\text{Re}(G^{\prime\prime}(\psi))\geq-1.1n$ by a similar argument. So,
by (83) and (81), for $\psi\in[-\pi/3,\pi/3]$,

$\text{Re}(G(\psi))\geq G(0)-1.1n\psi^{2}$

Now, for $t_{n}=0.1\min\\{n^{-1/3},\frac{1}{\varepsilon\sqrt{cn}}\\}$, we have
that for $\psi\in[-t_{n},t_{n}]$, $\cos(\text{Im}(G(\psi)))\geq 0.5$ so that
$\text{Re}(e^{G(\psi)})\geq 0.5e^{\text{Re}(G(\psi)}$. We can split $I_{1}$
further into $3$ parts:

$I_{1}=\text{Re}\left[\int_{-\pi/3}^{-t_{n}}e^{G(\psi)}d\psi\right]+\text{Re}\left[\int_{t_{n}}^{\pi/3}e^{G(\psi)}d\psi\right]+\text{Re}\left[\int_{-t_{n}}^{t_{n}}e^{G(\psi)}d\psi\right]$

Now, by (84),

$\left|\int_{-\pi/3}^{-t_{n}}e^{G(\psi)}d\psi\right|\leq
e^{G(0)}\int_{-\infty}^{-t_{n}}e^{-0.2n\psi^{2}}d\psi=t_{n}e^{G(0)}\int_{-\infty}^{-1}e^{-0.2nt_{n}^{2}\bar{\psi}^{2}}d\bar{\psi}$
$\leq
t_{n}e^{G(0)}\int_{-\infty}^{-1}e^{-0.2nt_{n}^{2}|\bar{\psi}|}d\bar{\psi}=e^{G(0)}O\left(\frac{1}{nt_{n}}\right)=e^{G(0)}o\left(\frac{1}{\sqrt{n}}\right)$

In a similar way, we can bound the second term. For the third term, we have

$\text{Re}\left[\int_{-t_{n}}^{t_{n}}e^{G(\psi)}d\psi\right]\geq\int_{-t_{n}}^{t_{n}}0.5e^{\text{Re}(G(\psi))}d\psi\geq
0.5e^{G(0)}\int_{-t_{n}}^{t_{n}}e^{-1.1n\psi^{2}}d\psi$

$\geq
0.5e^{G(0)}\left[\int_{-\infty}^{\infty}e^{-1.1n\psi^{2}}d\psi-2\int_{-\infty}^{-t_{n}}e^{-1.1n\psi^{2}}d\psi\right]$
$\geq
0.5e^{G(0)}\left(\frac{\sqrt{\pi}}{\sqrt{1.1n}}+O\left(\frac{1}{nt_{n}}\right)\right)=0.5e^{H(0)}\frac{\sqrt{\pi}}{\sqrt{1.1n}}(1+o(1))$

Combining the bounds, we get that

$I_{1}\geq e^{G(0)}\frac{0.5\sqrt{\pi}}{\sqrt{1.1n}}(1+o(1))$

∎

Combining the upper bound on $I_{1}$ from Lemma H.5 and the lower bound from
Lemma H.6, we have

$I_{1}=e^{G(0)}\frac{1}{\sqrt{n}}e^{O(1)}$

So, by (75) and (78),

$M_{\tilde{S},\nu}\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\right)=\exp(-me^{-n/m}\varepsilon^{2}\theta)\frac{n!}{2\pi}\lambda_{0}^{-n}e^{G(0)}\frac{\sqrt{\pi}}{\sqrt{0.2n}}(1+o(1))$
(86)

So, it remains to compute $G(0)$.

######  Lemma H.7.

Under the uniform distribution given by $\nu_{j}=1/m$ for all $j$, and
$\lambda_{0}=n(1+e^{-n/m}\varepsilon^{2}\theta)$,

$G(0)=\lambda_{0}+me^{-n/m}\varepsilon^{2}\theta+\varepsilon^{4}\theta^{2}[-ne^{-2n/m}+m\frac{e^{-n/m}}{2}-m\frac{e^{-2n/m}}{2}]+O(m\varepsilon^{6})$

###### Proof.

By definition of $G(\psi)$ in equation (79) and Lemma H.1,

$G(0)=\lambda_{0}+\sum_{j=1}^{m}\log[1+e^{-\lambda_{0}\nu_{j}}(e^{\varepsilon^{2}\theta}-1)]$

Now, since
$e^{\varepsilon^{2}\theta}-1=\varepsilon^{2}\theta+\frac{\varepsilon^{4}\theta^{2}}{2}+O(\varepsilon^{6})$,
this is

$\lambda_{0}+\sum_{j=1}^{m}[e^{-\lambda_{0}\nu_{j}}(\varepsilon^{2}\theta+\frac{\varepsilon^{4}\theta^{2}}{2})-\frac{\varepsilon^{4}\theta^{2}}{2}e^{-2\lambda_{0}\nu_{j}}+O(\varepsilon^{6})]$

Substituting in $\lambda_{0}$ from (74), and $\nu_{j}=1/m$ for all $j$, this
is

$=\lambda_{0}+\sum_{j=1}^{m}[e^{-\frac{n}{m}}e^{-\frac{n}{m}e^{-\frac{n}{m}}\varepsilon^{2}\theta}(\varepsilon^{2}\theta+\frac{\varepsilon^{4}\theta^{2}}{2})-\frac{\varepsilon^{4}\theta^{2}}{2}e^{-2\frac{n}{m}(1+O(\varepsilon^{2}))})+O(\varepsilon^{6})]$
$=\lambda_{0}+\sum_{j=1}^{m}[e^{-\frac{n}{m}}(1-\frac{n}{m}e^{-\frac{n}{m}}\varepsilon^{2}\theta)(\varepsilon^{2}\theta+\frac{\varepsilon^{4}\theta^{2}}{2})-\frac{\varepsilon^{4}\theta^{2}}{2}e^{-2\frac{n}{m}}+O(\varepsilon^{6})]$
$=\lambda_{0}+\sum_{j=1}^{m}[e^{-\frac{n}{m}}\varepsilon^{2}\theta-\frac{n}{m}e^{-2\frac{n}{m}}\varepsilon^{4}\theta^{2}+\frac{e^{-\frac{n}{m}}}{2}\varepsilon^{4}\theta^{2}-\frac{\varepsilon^{4}\theta^{2}}{2}e^{-2\frac{n}{m}}+O(\varepsilon^{6})]$

$=\lambda_{0}+me^{-\frac{n}{m}}\varepsilon^{2}\theta+\varepsilon^{4}\theta^{2}[-ne^{-2\frac{n}{m}}+m\frac{e^{-\frac{n}{m}}}{2}-m\frac{e^{-2\frac{n}{m}}}{2}]+O(m\varepsilon^{6})$

∎

######  Lemma H.8.

Under distribution $\nu$ such that
$\nu_{j}=\frac{1}{m}+\frac{\varepsilon}{\gamma m}$ for $j\leq\gamma m$ and
$\nu_{j}=\frac{1}{m}-\frac{\varepsilon}{(1-\gamma)m}$ for $j>l$, for
$\gamma=\Theta(1)$, $(1-\gamma)=\Theta(1)$, and
$\lambda_{0}=n(1+e^{-n/m}\varepsilon^{2}\theta)$, we have

$G(0)=\lambda_{0}+me^{-\frac{n}{m}}\varepsilon^{2}\theta+\varepsilon^{4}\theta^{2}\left[-ne^{-2n/m}+m\frac{e^{-n/m}}{2}-m\frac{e^{-2n/m}}{2}\right]+\varepsilon^{4}\theta\frac{e^{-n/m}n^{2}}{2m\gamma(1-\gamma)}$

###### Proof.

By definition of $G(\psi)$ in equation (79) and Lemma H.1,

$G(0)=\lambda_{0}+\sum_{j=1}^{m}\log[1+e^{-\lambda_{0}\nu_{j}}(e^{\varepsilon^{2}\theta}-1)]$

Now, since
$e^{\varepsilon^{2}\theta}-1=\varepsilon^{2}\theta+\frac{\varepsilon^{4}\theta^{2}}{2}+O(\varepsilon^{6})$,
this is

$\lambda_{0}+\sum_{j=1}^{m}[e^{-\lambda_{0}\nu_{j}}(\varepsilon^{2}\theta+\frac{\varepsilon^{4}\theta^{2}}{2})-\frac{\varepsilon^{4}\theta^{2}}{2}e^{-2\lambda_{0}\nu_{j}}+O(\varepsilon^{6})]$

Substituting in $\lambda_{0}$ and $\nu$, this is

$=\lambda_{0}+me^{-\frac{n}{m}}\varepsilon^{2}\theta+\varepsilon^{4}\theta^{2}\left[-ne^{-2n/m}+m\frac{e^{-n/m}}{2}-m\frac{e^{-2n/m}}{2}\right]+\varepsilon^{4}\theta\frac{e^{-n/m}mn^{2}}{2m\gamma(1-\gamma)}$

∎

Finally, we compute the MGF.

######  Lemma H.9.

Under the uniform distribution $p$ over $[m]$,

$M_{\tilde{S},p}\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\right)=(1+O(1/n))\exp\left\\{\frac{n^{2}\varepsilon^{4}}{m}\theta^{2}\left[-\frac{m}{n}\frac{e^{-\frac{2n}{m}}}{2}+\frac{m^{2}}{n^{2}}\frac{e^{-n/m}}{2}-\frac{m^{2}}{n^{2}}\frac{e^{-\frac{2n}{m}}}{2}\right]\right\\}$

and over distribution $q$ such that
$q_{j}=\frac{1}{m}+\frac{\varepsilon}{\gamma m}$ for $j\leq\gamma m$ and
$\nu_{j}=\frac{1}{m}-\frac{\varepsilon}{(1-\gamma)m}$ for $j>\gamma m$, for
$\gamma=\Theta(1)$ and $1-\gamma=\Theta(1)$, we have

$\displaystyle
M_{\tilde{S},q}\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\right)=(1+O(1/n))\exp\left\\{\frac{n^{2}\varepsilon^{4}}{m}\theta^{2}\left[-\frac{m}{n}\frac{e^{-\frac{2n}{m}}}{2}+\frac{m^{2}}{n^{2}}\frac{e^{-n/m}}{2}-\frac{m^{2}}{n^{2}}\frac{e^{-\frac{2n}{m}}}{2}\right]+\varepsilon^{4}\theta\frac{e^{-n/m}n^{2}}{2m\gamma(1-\gamma)}\right\\}$

###### Proof.

For the uniform distribution $p$, by (86), substituting
$\lambda_{0}=n(1+e^{-n/m}\varepsilon^{2}\theta)$ and $G(0)$ from Lemma H.7, we
have

$\displaystyle
M_{\tilde{S},p}\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\right)=\exp(-me^{-n/m}\varepsilon^{2}\theta)\frac{e^{n}n!}{\sqrt{2\pi
n}}(n(1+e^{-n/m}\varepsilon^{2}\theta))^{-n}$
$\displaystyle\exp\left(ne^{-n/m}\varepsilon^{2}\theta+me^{-n/m}\varepsilon^{2}\theta+\varepsilon^{4}\theta^{2}\left[-ne^{-2\frac{n}{m}}+m\frac{e^{-\frac{n}{m}}}{2}-m\frac{e^{-2\frac{n}{m}}}{2}\right]+O(m\varepsilon^{6})\right)$
$\displaystyle=\frac{e^{n}n!}{\sqrt{2\pi n}}\exp(-n(\log
n+\log(1+e^{-n/m}\varepsilon^{2}\theta)))$
$\displaystyle\exp\left(ne^{-n/m}\varepsilon^{2}\theta+\varepsilon^{4}\theta^{2}\left[-ne^{-2n/m}+m\frac{e^{-n/m}}{2}-m\frac{e^{-2n/m}}{2}\right]+O(m\varepsilon^{6})\right)$
$\displaystyle=\frac{e^{n}n!}{n^{n}\sqrt{2\pi
n}}\exp\left\\{-n(e^{-n/m}\varepsilon^{2}\theta-\frac{e^{-2n/m}\varepsilon^{4}\theta^{2}}{2})\right\\}$
$\displaystyle\exp\left\\{ne^{-n/m}\varepsilon^{2}\theta+\varepsilon^{4}\theta^{2}\left[-ne^{-2n/m}+m\frac{e^{-n/m}}{2}-m\frac{e^{-2n/m}}{2}\right]+O(m\varepsilon^{6})\right\\}$
$\displaystyle=(1+O(1/n))\exp\left\\{\frac{n^{2}\varepsilon^{4}}{m}\theta^{2}\left[-\frac{m}{n}\frac{e^{-\frac{2n}{m}}}{2}+\frac{m^{2}}{n^{2}}\frac{e^{-n/m}}{2}-\frac{m^{2}}{n^{2}}\frac{e^{-\frac{2n}{m}}}{2}\right]\right\\}$

by Stirling’s approximation.

Similarly, for $q$ as stated, we have the claim. ∎

###  H.3 Application of the Gärtner-Ellis Theorem

In this section, we apply the Gärtner-Ellis Theorem to obtain the probability
that our statistic crosses a threshold, under the uniform distribution, and
under one of the worst-case $\varepsilon$-far distributions.

######  Lemma H.10.

When $n=\Theta(m)$, let $\alpha=n/m$. Then, under the uniform distribution
$p$, we have that for $\tau>0$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{p}\left[\tilde{S}\geq\tau\right]\right)=\frac{\tau^{2}\alpha^{2}e^{2\alpha}}{2e^{\alpha}-2-2\alpha}$

Under an $\varepsilon$-far distribution $q$ of the form
$q_{j}=\frac{1}{m}+\frac{\varepsilon}{\gamma m}$ for $j\leq\gamma m$ and
$q_{j}=\frac{1}{m}-\frac{\varepsilon}{(1-\gamma)m}$ for $j>\gamma m$, and
$\gamma=\Theta(1)$, $1-\gamma=\Theta(1)$, for
$\tau<\frac{e^{-\alpha}}{2\gamma(1-\gamma)}$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{q}\left[\tilde{S}\leq\tau\right]\right)=\frac{\alpha^{2}(2\tau
e^{\alpha}\gamma(\gamma-1)+1)^{2}}{8(-1-\alpha+e^{\alpha})\gamma^{2}(\gamma-1)^{2}}$

###### Proof.

Note that by Lemma H.9, the limiting logarithmic moment generating function
with respect to the uniform distribution $p$ is given by

$\Lambda_{p}(\theta)=\lim_{n\to\infty}\frac{m}{n^{2}\varepsilon^{4}}\log\left(M_{\tilde{S},p}\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\right)\right)=\theta^{2}\left[-\frac{e^{-2\alpha}}{2\alpha}+\frac{e^{-\alpha}}{2\alpha^{2}}-\frac{e^{-2\alpha}}{2\alpha^{2}}\right]$

Thus, Assumption 1 holds for $\mathcal{D}_{\Lambda_{p}}=\mathbb{R}$.
Furthermore, the Fenchel-Legendre Transform (defined in equation 30) of
$\Lambda_{p}$ is given by

$\Lambda_{p}^{*}(\tau)=\sup_{\theta}\left\\{\theta\tau-\theta^{2}\left[-\frac{e^{-2\alpha}}{2\alpha}+\frac{e^{-\alpha}}{2\alpha^{2}}-\frac{e^{-2\alpha}}{2\alpha^{2}}\right]\right\\}=\frac{\tau^{2}\alpha^{2}e^{2\alpha}}{2e^{\alpha}-2-2\alpha}$

This is a strongly convex function of $\tau$, so the set of exposed points of
$\Lambda_{p}^{*}$ whose exposing hyperplane belongs to
$\mathcal{D}_{\Lambda_{p}}^{o}$ is all of $\mathbb{R}$. Thus, by the Theorem
B.2 (Gärtner-Ellis), for $\tau>0$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{p}\left[\tilde{S}\geq\tau\right]\right)=\inf_{x\geq\tau}\Lambda_{p}^{*}(x)=\frac{\tau^{2}\alpha^{2}e^{2\alpha}}{2e^{\alpha}-2-2\alpha}$

Similarly, the limiting logarithmic moment generating function with respect to
an alternate distribution $q$ is given by

$\Lambda_{q}(\theta)=\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{E}}_{q}\left[\exp\left(\frac{n^{2}\varepsilon^{4}}{m}\theta\tilde{S}\right)\right]\right)=\theta^{2}\left[-\frac{e^{-2\alpha}}{2\alpha}+\frac{e^{-\alpha}}{2\alpha^{2}}-\frac{e^{-2\alpha}}{2\alpha^{2}}\right]+\theta\frac{e^{-\alpha}}{2\gamma(1-\gamma)}$

The Fenchel-Legendre transform is given by

$\Lambda_{q}^{*}(\tau)=\sup_{\theta}\left\\{\theta\tau-\theta^{2}\left[-\frac{e^{-2\alpha}}{2\alpha}+\frac{e^{-\alpha}}{2\alpha^{2}}-\frac{e^{-2\alpha}}{2\alpha^{2}}\right]-\theta\frac{e^{-\alpha}}{2\gamma(1-\gamma)}\right\\}=\frac{\alpha^{2}(2\tau
e^{\alpha}\gamma(\gamma-1)+1)^{2}}{8(-1-\alpha+e^{\alpha})\gamma^{2}(\gamma-1)^{2}}$

Again, applying the Gärtner-Ellis Theorem gives, for
$\tau<\frac{e^{-\alpha}}{2\gamma(1-\gamma)}$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{q}\left[\tilde{S}_{n}^{*}\leq\tau\right]\right)=\inf_{x\leq\tau}\Lambda^{*}_{q}(x)=\frac{\alpha^{2}(2\tau
e^{\alpha}\gamma(\gamma-1)+1)^{2}}{8(-1-\alpha+e^{\alpha})\gamma^{2}(\gamma-1)^{2}}$

∎

######  Lemma H.11.

When $n=o(m)$, under the uniform distribution $p$, we have for $\tau>0$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{p}\left[\tilde{S}\geq\tau\right]\right)=\tau^{2}$

and under an $\varepsilon$-far distribution $q$ such that
$q_{j}=\frac{1}{m}+\frac{\varepsilon}{\gamma m}$ for $j\leq\gamma m$ and
$q_{j}=\frac{1}{m}-\frac{\varepsilon}{(1-\gamma)m}$ for $j>\gamma m$, for
$\gamma=\Theta(1),1-\gamma=\Theta(1)$, and $\tau<\frac{1}{2\gamma(1-\gamma)}$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{q}\left[\tilde{S}\leq\tau\right]\right)=\frac{(2\tau\gamma(\gamma-1)+1)^{2}}{4\gamma^{2}(\gamma-1)^{2}}$

###### Proof.

Since $n=o(m)$, we have by Lemma H.9, Taylor expanding,

$M_{\tilde{S},p}\left(\frac{n^{2}\varepsilon^{4}}{m}\right)=\exp\left\\{\frac{n^{2}\varepsilon^{4}}{m}\theta^{2}\left[\frac{1}{4}+O(n/m)\right]\right\\}$

and similarly,

$M_{\tilde{S},q}\left(\frac{n^{2}\varepsilon^{4}}{m}\right)=\exp\left\\{\frac{n^{2}\varepsilon^{4}}{m}\theta\left[\frac{1}{4}\theta+\frac{1}{2\gamma(1-\gamma)}+O(n/m)\right]\right\\}$

Then, by a similar argument as in H.10, the claim follows. ∎

###  H.4 Setting the threshold

We need to set our threshold $\tau$ so that the minimum of the error
probability under the uniform distribution $p$, and any $\varepsilon$-far
distribution $q$ is maximized. Note that by Lemmas H.10 and H.11, it is
sufficient to consider a threshold $\tau$ such that
$0<\tau<\frac{e^{-\alpha}}{2\gamma(1-\gamma)}$ when $n=\Theta(m)$ and
$0<\tau<\frac{1}{2\gamma(1-\gamma)}$ when $n=o(m)$, since otherwise, the error
probability in one of the two cases is at least constant. To set our
threshold, we will first observe that for any $\tau$ in this range, the “error
exponent” under $\varepsilon$-far distributions is minimized for a particular
$\varepsilon$-far distribution. Then, we will set the threshold to maximize
the minimum of the error exponent under the uniform distribution, and under
this $\varepsilon$-far distribution.

######  Lemma H.12.

When $n=\Theta(m)$ so that $\alpha=n/m$, setting the threshold
$\tau=e^{-\alpha}$, we have for the uniform distribution $p$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{p}\left[\tilde{S}\geq\tau\right]\right)=\frac{\alpha^{2}}{2(-1-\alpha+e^{\alpha})}$

and for any $\varepsilon$-far distribution $q$ such that
$q_{j}=1/m+\frac{\varepsilon}{\gamma m}$ for $j\leq\gamma m$ and
$q_{j}=1/m-\frac{\varepsilon}{(1-\gamma)m}$ for $j>\gamma m$ and
$\gamma=\Theta(1),1-\gamma=\Theta(1)$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{q}\left[\tilde{S}\leq\tau\right]\right)\geq\frac{\alpha^{2}}{2(-1-\alpha+e^{\alpha})}$

with equality for $q$ such that $q_{j}=1/m+2\varepsilon/m$ for $j\leq m/2$ and
$q_{j}=1/m-2\varepsilon/m$ for $j>m/2$.

###### Proof.

By Lemma H.10, for $0<\tau<\frac{e^{-\alpha}}{2\gamma(1-\gamma)}$,

$\lim_{n\to\infty}\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{q}\left[\tilde{S}\leq\tau\right]\right)=\frac{\alpha^{2}(2\tau
e^{\alpha}\gamma(\gamma-1)+1)^{2}}{8(-1-\alpha+e^{\alpha})\gamma^{2}(\gamma-1)^{2}}$

Now, the numerator of the right hand side is minimized when $\gamma=1/2$, and
the denominator is maximized when $\gamma=1/2$. Thus, the right hand side is
minimized when $\gamma=1/2$. So, we have that,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{q}\left[\tilde{S}\leq\tau\right]\right)\geq\frac{2\alpha^{2}(1-\frac{1}{2}\tau
e^{\alpha})^{2}}{(-1-\alpha+e^{\alpha})}$

with equality for distribution $q$ such that $q_{j}=1/m+2\varepsilon/m$ for
$j\leq m/2$ and $q_{j}=1/m-2\varepsilon/m$ for $j>m/2$.

Then, the claim follows by substituting in $\tau=e^{-\alpha}$ in the
expression for the uniform distribution in Lemma H.10 and in the above
expression. ∎

######  Lemma H.13.

When $n=o(m)$, setting the threshold $\tau=1$, we have for the uniform
distribution $p$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{p}\left[\tilde{S}\geq\tau\right]\right)=1$

and for any $\varepsilon$-far distribution $q$ such that
$q_{j}=1/m+\frac{\varepsilon}{\gamma m}$ for $j\leq\gamma m$ and
$q_{j}=1/m-\frac{\varepsilon}{(1-\gamma)m}$ for $j>\gamma m$, and
$\gamma=\theta(1),1-\gamma=\Theta(1)$,

$\lim_{n\to\infty}-\frac{m}{n^{2}\varepsilon^{4}}\log\left(\operatorname*{\mathbb{P}}_{q}\left[\tilde{S}\leq\tau\right]\right)\geq
1$

with equality for distribution $q$ such that $q_{j}=1/m+2\varepsilon/m$ for
$j\leq m/2$ and $q_{j}=1/m-2\varepsilon/m$ for $j>m/2$.

###### Proof.

Follows from Lemma H.11 and using a similar argument as in Lemma H.12. ∎

Finally, we have our results.

See 1.5

###### Proof.

Recall that our statistic is equivalent to the TV tester when $n\leq m$. When
$n=\Theta(m)$, by Lemma H.12, we have that $\bar{c}(\varepsilon,m,C)=1$ for
every $\varepsilon$ that satisfies our assumptions, and every $C>2$. In
particular, any $\varepsilon^{\prime}$ such that
$\left(1-\frac{1}{C^{\prime}}\right)\varepsilon(n)\leq\varepsilon^{\prime}(n)\leq\varepsilon(n)$
has $\bar{c}(\varepsilon^{\prime},m,C)=1$ for every $C>2$. Thus, by Lemma
B.10, we have that $c(\varepsilon,m)=1$ for every $\varepsilon$ that satisfies
our assumptions.

So, we have shown that our tester fails with probability
$e^{-\frac{n^{2}\varepsilon^{4}}{m}(\xi+o(1))}$ for

$\xi=\frac{\alpha^{2}}{2(-1-\alpha+e^{\alpha})}$

where $\alpha=n/m$. This implies that the TV tester uses
$n=\frac{\sqrt{m\log(1/\delta)}}{\varepsilon^{2}}(c+o(1))$ samples for failure
probability $\delta$, where

$c=\frac{\sqrt{2(e^{\alpha}-1-\alpha)}}{\alpha}$

as required. Now, $c>1$ for $0\leq\alpha\leq 1$. The claim for the
$n=\Theta(m)$ case follows. By a similar argument using Lemma H.13, the claim
for the $n=o(m)$ case follows. ∎

###  H.5 Empty bins lemmas

We assume that Assumption 5 holds throughout this section.

######  Lemma H.14.

Suppose Assumption 5 holds.

$\sum_{k=0}^{\infty}\left\\{\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}e^{-\lambda_{0}\nu_{j}e^{i\psi}}\exp(\varepsilon^{2}\theta\mathbbm{1}_{\\{k=0\\}})\right\\}=1+O(\varepsilon^{2})$

for $\lambda_{0}=n(1+O(\varepsilon))$ and $\nu_{j}=1/m+O(\varepsilon/m)$ for
all $j$,

###### Proof.

By Lemma H.1,

$\displaystyle\sum_{k=0}^{\infty}\left\\{\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}e^{-\lambda_{0}\nu_{j}e^{i\psi}}\exp(\varepsilon^{2}\theta\mathbbm{1}_{\\{k=0\\}})\right\\}$
$\displaystyle=e^{-\lambda_{0}\nu_{j}e^{i\psi}}e^{\varepsilon^{2}\theta}-e^{-\lambda_{0}\nu_{j}e^{i\psi}}+1$
$\displaystyle=e^{-\lambda_{0}\nu_{j}e^{i\psi}}(\varepsilon^{2}\theta+O(\varepsilon^{4}))+1$

Substituting $\lambda_{0}$ and $\nu_{j}$, this is

$\displaystyle
1+e^{-\frac{n}{m}e^{i\psi}(1+O(\varepsilon))}(\varepsilon^{2}\theta+O(\varepsilon^{4}))$
$\displaystyle=1+O(\varepsilon^{2})$

∎

######  Lemma H.15.

Suppose Assumption 5 holds. For
$\lambda_{0}=n(1+e^{-n/m}\varepsilon^{2}\theta)$,
$\nu_{j}=\frac{1}{m}+O\left(\frac{\varepsilon}{m}\right)$ for all $j$,

$\prod_{j=1}^{m}\left\\{e^{-\lambda_{0}\nu_{j}e^{i\psi}}e^{\varepsilon^{2}\theta}-e^{-\lambda_{0}\nu_{j}e^{i\psi}}+1\right\\}=\exp\left\\{me^{-\frac{n}{m}e^{i\psi}}\varepsilon^{2}\theta(1+O(\varepsilon^{2}))+O(n\varepsilon^{3})\right\\}$

###### Proof.

By Lemma H.1,

$\displaystyle\prod_{j=1}^{m}\left\\{e^{-\lambda_{0}\nu_{j}e^{i\psi}}e^{\varepsilon^{2}\theta}-e^{-\lambda_{0}\nu_{j}e^{i\psi}}+1\right\\}$
$\displaystyle=\prod_{j=1}^{m}\left\\{e^{-\lambda_{0}\nu_{j}e^{i\psi}}(\varepsilon^{2}\theta+O(\varepsilon^{4}))+1\right\\}$
$\displaystyle=\exp\left\\{\sum_{j=1}^{m}\log\left[e^{-\lambda_{0}\nu_{j}e^{i\psi}}(\varepsilon^{2}\theta+O(\varepsilon^{4}))+1\right]\right\\}$

Substituting $\lambda_{0}=n(1+O(\varepsilon^{2}))$ and
$\nu_{j}=1/m+O(\varepsilon/m)$, since $n=O(m)$, this is

$\displaystyle=\exp\left\\{\sum_{j=1}^{m}\log\left[e^{-\frac{n}{m}e^{i\psi}(1+O(\varepsilon))}(\varepsilon^{2}\theta+O(\varepsilon^{4}))+1\right]\right\\}$
$\displaystyle=\exp\left\\{m\left[e^{-\frac{n}{m}e^{i\psi}(1+O(\varepsilon))}(\varepsilon^{2}\theta+O(\varepsilon^{4}))\right]\right\\}$
$\displaystyle=\exp\left\\{me^{-\frac{n}{m}e^{i\psi}}\varepsilon^{2}\theta(1+O(\varepsilon^{2}))+O(n\varepsilon^{3})\right\\}$

∎

######  Lemma H.16.

Suppose Assumption 5 holds. For
$\lambda_{0}=n(1+e^{-n/m}\varepsilon^{2}\theta)$,
$\nu_{j}=\frac{1}{m}+O(\frac{\varepsilon}{m})$, and

$f(k)=\exp(\varepsilon^{2}\theta\mathbbm{1}_{\\{k=0\\}})$

and

$G(\psi)=-in\psi+\lambda_{0}e^{i\psi}+\sum_{j=1}^{m}\log\left\\{e^{-\lambda_{0}\nu_{j}e^{i\psi}}e^{\varepsilon^{2}\theta}-e^{\lambda_{0}\nu_{j}e^{i\psi}}+1\right\\}$

we have

$G^{\prime\prime}(\psi)=-ne^{i\psi}+O(n\varepsilon^{2})$

###### Proof.

First, note that for $c>0$, since $\mathbbm{1}_{\\{k+c=0\\}}=0$ for every
$k\geq 0$, $f(k+c)=1$, for every $k\geq 0$. So,

$\sum_{k=0}^{\infty}\left\\{\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}e^{-\lambda_{0}\nu_{j}e^{i\psi}}f(k+c)\right\\}=1$

By Lemma H.14, we have that

$\sum_{k=0}^{\infty}\left\\{\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}e^{-\lambda_{0}\nu_{j}e^{i\psi}}f(k)\right\\}=1+O(\varepsilon^{2})$

So, we have

$\displaystyle\left(\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}e^{-\lambda_{0}\nu_{j}e^{i\psi}}f(k+1)\right)^{2}$
$\displaystyle-\left(\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}e^{-\lambda_{0}\nu_{j}e^{i\psi}}f(k)\right)\left(\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}e^{-\lambda_{0}\nu_{j}e^{i\psi}}f(k+2)\right)=O(\varepsilon^{2})$

and

$\left(\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}e^{-\lambda_{0}\nu_{j}e^{i\psi}}f(k)\right)\left(\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}e^{-\lambda_{0}\nu_{j}e^{i\psi}}f(k+2)\right)=1+O(\varepsilon^{2})$

and

$\left(\sum_{k=0}^{\infty}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{k}}{k!}e^{-\lambda_{0}\nu_{j}e^{i\psi}}f(k)\right)^{2}=1+O(\varepsilon^{2})$

So, by Lemma D.14, we have that

$G^{\prime\prime}(\psi)=\sum_{j=1}^{m}\frac{(\lambda_{0}\nu_{j}e^{i\psi})^{2}O(\varepsilon^{2})-(\lambda_{0}\nu_{j}e^{i\psi})(1+O(\varepsilon^{2}))}{1+O(\varepsilon^{2})}$
$=\sum_{j=1}^{m}\left\\{O(\frac{n^{2}\varepsilon^{2}}{m^{2}})-(\lambda_{0}\nu_{j}e^{i\psi})(1+O(\varepsilon^{2}))\right\\}(1+O(\varepsilon^{2}))$
$=-(\lambda_{0}e^{i\psi})(1+O(\varepsilon^{2}))+O\left(\frac{n^{2}\varepsilon^{2}}{m}\right)=-ne^{i\psi}+O(n\varepsilon^{2})$

since $n=O(m)$ and $\lambda_{0}=n(1+O(\varepsilon^{2}))$. ∎