10.1,

(11.31) $\displaystyle\mathbb{E}\big{[}\mathbf{1}_{\Gamma}$ $\displaystyle
d_{K}\big{(}Z-Y,\mathcal{N}(0,\sigma_{1}^{2})\big{)}\big{]}\leqslant\mathbb{E}\big{[}\mathbf{1}_{\Gamma}d_{K}\big{(}Z-Y,\mathcal{N}(0,\sigma_{\omega}^{2})\big{)}\big{]}+\mathbb{E}\Big{[}\mathbf{1}_{\Gamma}\,\frac{|\sigma_{1}-\sigma_{\omega}|}{\max\\{\sigma_{1},\sigma_{\omega}\\}}\Big{]}$
$\displaystyle\leqslant\mathbb{E}\big{[}\mathbf{1}_{\Gamma}d_{K}\big{(}Z-Y,\mathcal{N}(0,\sigma_{\omega}^{2})\big{)}\big{]}+\frac{1}{\sigma_{1}^{2}}\,\mathbb{E}\big{[}|\sigma_{1}^{2}-\sigma_{\omega}^{2}|\big{]}$
$\displaystyle\stackrel{{\scriptstyle\eqref{e11.1},\eqref{e11.18}}}{{\leqslant}}\mathbb{E}\big{[}\mathbf{1}_{\Gamma}d_{K}\big{(}Z-Y,\mathcal{N}(0,\sigma_{\omega}^{2})\big{)}\big{]}+\frac{1}{\delta_{1}}\Big{(}\mathrm{osc}(\bm{X})+B+\frac{\kappa}{n}\Big{)}$
$\displaystyle\hskip
32.72049pt\stackrel{{\scriptstyle\eqref{e1.11}}}{{\leqslant}}\mathbb{E}\big{[}\mathbf{1}_{\Gamma}d_{K}\big{(}Z-Y,\mathcal{N}(0,\sigma_{\omega}^{2})\big{)}\big{]}+\mathrm{osc}(\bm{X})^{1-\alpha}+B^{1-\alpha}+\Big{(}\frac{\kappa}{n}\Big{)}^{1-\alpha}.$

By (11.24), Claims 11.2–11.4 and the Cauchy–Schwarz inequality,

(11.32)
$\displaystyle\mathbb{E}\big{[}\mathbf{1}_{\Gamma}d_{K}\big{(}Z-Y,\mathcal{N}(0,\sigma_{\omega}^{2})\big{)}$
$\displaystyle\big{]}\leqslant\frac{2^{22}C_{1}d^{3}K}{\sigma_{1}^{3}}\Big{(}\sum_{j=1}^{n}\Big{|}\Big{(}\\!\sum_{\begin{subarray}{c}i\in[n]^{d}\\\
i(1)=j\end{subarray}}\\!\\!\theta_{i}\Big{)}-\frac{\bm{\theta}_{+}}{n}\Big{|}^{3}\Big{)}\,+$
$\displaystyle\hskip
14.22636pt+\frac{2\sqrt{2}C_{d}}{\sigma_{1}}\sum_{s=2}^{d}\binom{d}{s}\sqrt{\Sigma_{s}+\frac{8d^{2}2^{d}}{n}}\,{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{H}\big{[}\mathcal{S}_{[s]}[\bm{\theta}]\big{]}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{s}^{2}.$

The desired estimate (11.2) follows by combining (11.30), (11.20), (11.31) and
(11.32), and invoking the definition of
$E^{\prime}_{1},E^{\prime}_{2},E^{\prime}_{3}$. The proof of Proposition 11.1
is completed. ∎

####  11.3. Completion of the proof

We are finally in a position to complete the proof of Theorem 1.4. To this
end, we first observe that we may assume that $n\geqslant\kappa$ and
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{0}\leqslant\sqrt{n}/2$.
(Otherwise, (1.12) is straightforward.) By (11.1), the last assumption
implies, in particular, that

(11.33) $\sigma_{1}^{2}\geqslant\frac{3d^{2}\delta_{1}}{4}.$

Next observe that, by the triangle inequality for the Kolmogorov distance,
Lemma 10.1, (11.33) and Proposition 1.2, we have

(11.34) $\displaystyle d_{K}\big{(}\mathcal{N}(0,\sigma_{1}^{2}),\,$
$\displaystyle\mathcal{N}(0,\sigma^{2})\big{)}\leqslant
d_{K}\big{(}\mathcal{N}(0,d^{2}\delta_{1}),\mathcal{N}(0,\sigma^{2})\big{)}+\frac{{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{0}^{2}}{n}$
$\displaystyle\leqslant\Big{|}\frac{\delta_{0}\,({\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{0}^{2}-1)}{d^{2}\delta_{1}}\Big{|}+\frac{1}{d^{2}\delta_{1}}\,\sum_{s=2}^{d}\binom{d}{s}^{2}\,s!\,|\Sigma_{s}|\cdot{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{s}^{2}+\frac{{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{0}^{2}}{n}.$

(Recall that $\sigma^{2}$ denotes the variance of
$\langle\bm{\theta},\bm{X}\rangle$.) On the other hand, by ($\mathcal{A}$1),
($\mathcal{A}$2), (1.7), Fact 10.6 and the definition of $B$, we have

(11.35)
$B=\frac{1}{n^{2d}}\sum_{i,j\in[n]^{d}}\mathbb{E}[X_{i}X_{j}]\leqslant|\delta_{0}|+\frac{4d^{2}}{n}.$

Moreover, by Hölder’s inequality,

(11.36)
$\sum_{j=1}^{n}\Big{|}\Big{(}\\!\sum_{\begin{subarray}{c}i\in[n]^{d}\\\
i(1)=j\end{subarray}}\\!\\!\theta_{i}\Big{)}-\frac{\bm{\theta}_{+}}{n}\Big{|}^{3}\leqslant
2^{4}\sum_{j=1}^{n}\Big{|}\\!\sum_{\begin{subarray}{c}i\in[n]^{d}\\\
i(1)=j\end{subarray}}\theta_{i}\Big{|}^{3}$

Finally, by the Cauchy–Schwarz inequality, for every $s\in\\{2,\dots,d\\}$ we
have

(11.37)
$\displaystyle{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\mathcal{H}\big{[}\mathcal{S}_{[s]}[\bm{\theta}]\big{]}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{s}^{2}$
$\displaystyle\
\,=\sum_{i\in[n]^{s}}\mathcal{H}\big{[}\mathcal{S}_{[s]}[\bm{\theta}]\big{]}(i)^{2}=n^{2d-2s}\sum_{i\in[n]^{s}}\mathcal{H}\big{[}\mathcal{A}_{[s]}[\bm{\theta}]\big{]}(i)^{2}$
$\displaystyle\stackrel{{\scriptstyle\eqref{e9.2}}}{{=}}n^{2d-2s}\sum_{i\in[n]^{s}}\Big{(}\sum_{F\subseteq[s]}(-1)^{s-|F|}\mathcal{A}_{F}[\bm{\theta}](i\upharpoonright
F)\Big{)}^{2}$ $\displaystyle\ \leqslant
n^{2d-2s}\,2^{s}\sum_{F\subseteq[s]}\sum_{i\in[n]^{s}}\mathcal{A}_{F}[\bm{\theta}](i\upharpoonright
F)^{2}$ $\displaystyle\ \leqslant
n^{2d-2s}\,2^{s}\sum_{F\subseteq[s]}\sum_{i\in[n]^{s}}\Big{(}\frac{1}{n^{s-|F|}}\sum_{i\upharpoonright
F\sqsubseteq j\in[n]^{s}}\mathcal{A}_{[s]}[\bm{\theta}](j)^{2}\Big{)}$
$\displaystyle\
=n^{2d-2s}\,2^{s}\sum_{F\subseteq[s]}\sum_{j\in[n]^{s}}\mathcal{A}_{[s]}[\bm{\theta}](j)^{2}\stackrel{{\scriptstyle\eqref{e1.5}}}{{=}}2^{2s}{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{s}^{2}\leqslant
12s!\,{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{s}^{2}$

where in the last inequality we have used the fact that $2^{2s}\leqslant 12s!$
for every integer $s\geqslant 2$.

Inequality (1.12) now follows from (11.2), (11.33)–(11.37), Fact 1.3 and the
estimate $C_{1}\leqslant 451$ obtained in [CF15]. The proof of Theorem 1.4 is
completed.

###  12\. Proofs of applications

####  12.1. Exchangeable random vectors

We start by giving the proof of Corollary 3.1.

###### Proof of Corollary _3.1_.

First observe that we may assume that $\mathrm{osc}(\bm{X})\leqslant 1$ and
$n\geqslant\kappa_{1}$. (Otherwise, (3.2) is straightforward.) Therefore, by
(3.1), the non-degenericity condition (1.11) is satisfied for every
$\alpha\in(0,1)$. Taking into account this remark, the result follows by
Theorem 1.4 albeit with a different absolute constant. The fact that in (3.2)
we can select the constant $\kappa_{1}=4320$ follows after noticing that, for
the one-dimensional case, in the proof of Proposition 11.1 it suffices to
apply (2.4) with $C_{1}=451$. ∎

######  Remark 12.1.

It is instructive to compare Corollary 3.1 with the classical work of Diaconis
and Freedman [DF80] which estimates the total variation distance between the
marginals of the law of an exchangeable random vector, and the corresponding
marginals of a mixture of product measures. The results in [DF80] are very
informative, but unfortunately they become quantitatively less useful for
exchangeable random vectors whose entries are not finite-valued. On the other
hand, by considering a statistically less rigid quantity, Corollary 3.1
provides estimates of equal quantitative strength for all permissible
distributions.

We proceed to estimate the oscillation of exchangeable random vectors. We
first treat the case of random vectors whose entries have finite fourth
moment.

######  Fact 12.2.

Let $\bm{X}$ be an exchangeable random vector in $\mathbb{R}^{n}$ $(n\geqslant
2)$ whose entries have zero mean, unit variance and finite fourth moment. Then
we have

(12.1)
$\mathrm{osc}(\bm{X})\leqslant\sqrt{\big{|}\mathbb{E}[X_{1}^{2}X_{2}^{2}]-1\big{|}}+\frac{\mathbb{E}[X_{1}^{4}]^{1/2}}{\sqrt{n}}.$

###### Proof.

By the Cauchy–Schwarz inequality and our assumptions, we have

(12.2)
$\displaystyle\mathrm{osc}(\bm{X})\stackrel{{\scriptstyle\eqref{e1.10}}}{{=}}\Big{\|}\frac{1}{n}\sum_{i=1}^{n}X_{i}^{2}-1\Big{\|}_{L_{1}}\leqslant\Big{\|}\frac{1}{n}\sum_{i=1}^{n}X_{i}^{2}-1\Big{\|}_{L_{2}}$
$\displaystyle=$ $\displaystyle\
\Big{(}\frac{1}{n^{2}}\sum_{i,j=1}^{n}\mathbb{E}[X_{i}^{2}X_{j}^{2}]+1-\frac{2}{n}\sum_{i=1}^{n}\mathbb{E}[X_{i}^{2}]\Big{)}^{1/2}$
$\displaystyle=$ $\displaystyle\
\Big{(}\frac{\mathbb{E}[X_{1}^{4}]-\mathbb{E}[X_{1}^{2}X_{2}^{2}]}{n}+\mathbb{E}[X_{1}^{2}X_{2}^{2}]-1\Big{)}^{1/2}\leqslant\sqrt{\big{|}\mathbb{E}[X_{1}^{2}X_{2}^{2}]-1\big{|}}+\frac{\mathbb{E}[X_{1}^{4}]^{1/2}}{\sqrt{n}}.\qed$

The following proposition supplements Fact 12.2, and it estimates the
oscillation of exchangeable random vectors whose entries have finite third
moment.

######  Proposition 12.3.

Let $\bm{X}$ be an exchangeable random vector in $\mathbb{R}^{n}$ $(n\geqslant
2)$ whose entries have zero mean, unit variance and finite third moment. Then
we have

(12.3)
$\mathrm{osc}(\bm{X})\leqslant\sqrt{\big{|}\mathbb{E}[X_{1}^{2}X_{2}^{2}]-1\big{|}}+\frac{4\mathbb{E}\big{[}|X_{1}|^{3}\big{]}}{\sqrt[4]{n}}.$

###### Proof.

We will use a standard truncation argument. Specifically, set
$K\coloneqq\mathbb{E}\big{[}|X_{1}|^{3}\big{]}$, and let $\lambda>0$ be a cut-
off parameter to be specified later. Moreover, for every $i\in[n]$ set
$G_{i}\coloneqq X_{i}^{2}\,\mathbf{1}_{[|X_{i}|\leqslant\lambda]}$ and
$B_{i}\coloneqq X_{i}^{2}\,\mathbf{1}_{[|X_{i}|>\lambda]}$, and notice that

(12.4)
$\mathbb{E}[G_{i}^{2}]=\mathbb{E}[X_{i}^{3}X_{i}\,\mathbf{1}_{[|X_{i}|\leqslant\lambda]}]\leqslant\lambda
K;$

on the other hand, by Hölder’s inequality and Markov’s inequality,

(12.5)
$\|B_{i}\|_{L_{1}}\leqslant\mathbb{E}\big{[}|X_{i}|^{3}\big{]}^{\frac{2}{3}}\,\mathbb{P}\big{(}|X_{i}|>\lambda\big{)}^{\frac{1}{3}}\leqslant\frac{K}{\lambda}.$

Since the random vectors $(G_{1},\dots,G_{n})$ and $(B_{1},\dots,B_{n})$ are
exchangeable, we obtain that

(12.6) $\displaystyle\mathrm{osc}(\bm{X})$
$\displaystyle\stackrel{{\scriptstyle\eqref{e1.10}}}{{=}}\Big{\|}\frac{1}{n}\sum_{i=1}^{n}X_{i}^{2}-1\Big{\|}_{L_{1}}\leqslant\Big{\|}\frac{1}{n}\sum_{i=1}^{n}G_{i}-1\Big{\|}_{L_{1}}+\|B_{1}\|_{L_{1}}$
$\displaystyle\stackrel{{\scriptstyle\eqref{e12.5}}}{{\leqslant}}\Big{\|}\frac{1}{n}\sum_{i=1}^{n}G_{i}-1\Big{\|}_{L_{1}}+\frac{K}{\lambda}\leqslant\Big{\|}\frac{1}{n}\sum_{i=1}^{n}G_{i}-1\Big{\|}_{L_{2}}+\frac{K}{\lambda}$
$\displaystyle\ \
=\Big{(}\frac{\mathbb{E}[G_{1}^{2}]-\mathbb{E}[G_{1}G_{2}]}{n}+\mathbb{E}[G_{1}G_{2}]-1+2\mathbb{E}[B_{1}]\Big{)}^{1/2}+\frac{K}{\lambda}$
$\displaystyle\ \
\leqslant\Big{(}\frac{\mathbb{E}[G_{1}^{2}]}{n}+\mathbb{E}[X_{1}^{2}X_{2}^{2}]-1+2\mathbb{E}[B_{1}]\Big{)}^{1/2}+\frac{K}{\lambda}$
$\displaystyle\,\stackrel{{\scriptstyle\eqref{e12.4},\eqref{e12.5}}}{{\leqslant}}\frac{\sqrt{\lambda
K}}{\sqrt{n}}+\sqrt{\big{|}\mathbb{E}[X_{1}^{2}X_{2}^{2}]-1\big{|}}+\sqrt{2}\frac{\sqrt{K}}{\sqrt{\lambda}}+\frac{K}{\lambda}$

where we have used the Cauchy–Schwarz inequality, and that
$0\leqslant\mathbb{E}[G_{1}G_{2}]\leqslant\mathbb{E}[G_{1}^{2}]$ and
$\mathbb{E}[G_{1}G_{2}]\leqslant\mathbb{E}[X_{1}^{2}X_{2}^{2}]$. The result
follows by applying (12.6) for $\lambda=\sqrt[4]{n}$. ∎

#####  12.1.1. Optimality

It follows from (3.2) that if $\bm{X}$ is an exchangeable and isotropic random
vector in $\mathbb{R}^{n}$ which satisfies

(12.7) $\mathbb{E}\big{[}|X_{1}|^{3}]=O(1),$

then for every positive integer $k\leqslant n$ we have

(12.8)
$d_{K}\Big{(}\frac{X_{1}+\dots+X_{k}}{\sqrt{k}},\mathcal{N}(0,1)\Big{)}=O\Big{(}\mathrm{osc}(\bm{X})+\frac{k}{n}+\frac{1}{\sqrt{k}}\Big{)}.$

Our goal in this subsection is to show that this estimate is optimal, in the
sense that each of the three error terms that appear in the right-hand-side of
(12.8) can be dominated by the Kolmogorov distance in (12.8) for an
appropriately selected exchangeable and isotropic random vector which
satisfies (12.7).

The necessity of the error term $O(1/\sqrt{k})$ is a classical observation,
and it can be attained by considering a random vector with independent
Rademacher entries. The necessity of the first error term—the oscillation—is
shown in the next example.

######  Example 12.4.

Let $n\geqslant 2$ be an arbitrary integer. Fix $0<\varepsilon\leqslant 1/2$,
and let $\bm{X}$ be a random vector in $\mathbb{R}^{n}$ whose distribution
satisfies

(12.9) $\mathbb{P}(\bm{X}\in A)=\varepsilon\,\mathbb{P}(\bm{Z}\in
A)+(1-\varepsilon)\,\mathbb{P}\Big{(}\frac{\bm{R}}{\sqrt{1-\varepsilon}}\in
A\Big{)}$

for every Borel subset $A$ of $\mathbb{R}^{n}$, where $\bm{Z}$ is a random
vector in $\mathbb{R}^{n}$ with constant zero entries and $\bm{R}$ is a random
vector in $\mathbb{R}^{n}$ with independent Rademacher entries. Notice that
$\bm{X}$ is exchangeable, isotropic and bounded; in particular, it satisfies
(12.7). Moreover,

(12.10) $\mathrm{osc}(\bm{X})=2\varepsilon.$

Finally, for every positive integer $k\leqslant n$ we have

(12.11)
$d_{K}\Big{(}\frac{X_{1}+\dots+X_{k}}{\sqrt{k}},\mathcal{N}(0,1)\Big{)}\geqslant\frac{1}{2}\,\mathbb{P}\Big{(}\frac{X_{1}+\dots+X_{k}}{\sqrt{k}}=0\Big{)}\geqslant\frac{\varepsilon}{2}\stackrel{{\scriptstyle\eqref{e12.10}}}{{\geqslant}}\frac{\mathrm{osc}(\bm{X})}{4}.$

The necessity of the error term $O(k/n)$ is the content of the following
example.

######  Example 12.5.

It is a slight modification of the results of Diaconis and Freedman in [DF80,
Section 4]. (See also [DF87] for closely related results.)

Specifically, let $n$ be a sufficiently large positive even integer, and let
$\bm{\xi}=(\xi_{1},\dots,\xi_{n})$ be a random vector which is uniformly
distributed on the set of all $x\in\\{-1,1\\}^{n}$ whose coordinates sum-up to
$0$. Notice that $\bm{\xi}$ is exchangeable. Using a non-asymptotic version of
Stirling’s approximation—see [Ro55]—and elementary computations, it is easy to
verify that for every integer $k\in\\{16,\dots,\frac{n}{14}\\}$ and every
integer $a\in\big{[}-\frac{\sqrt{k}}{2},\frac{\sqrt{k}}{2}\big{]}$ we have

(12.12)
$\mathbb{P}(S_{k}=a)\geqslant\mathbb{P}(R_{k}=a)\cdot\Big{(}1+\frac{1}{32}\,\frac{k}{n}\Big{)}$

where $S_{k}\coloneqq\xi_{1}+\dots+\xi_{k}$ and $R_{k}\coloneqq
r_{1}+\dots+r_{k}$ with $r_{1},\dots,r_{k}$ independent Rademacher random
variables. This estimate and the classical Berry–Esseen theorem in turn imply
that for every171717Here, given two positive quantities $a$ and $b$, we write
$a\gtrsim b$ to denote the fact that $a\geqslant Cb$ for some positive
universal constant $C$. $n\gtrsim k\gtrsim n^{2/3}$ we have

(12.13)
$d_{K}\Big{(}\frac{\xi_{1}+\dots+\xi_{k}}{\sqrt{k}},\mathcal{N}(0,1)\Big{)}\gtrsim\frac{k}{n};$

on the other hand, by anticoncentration considerations, if $k=O(n^{2/3})$,
then we have

(12.14)
$d_{K}\Big{(}\frac{\xi_{1}+\dots+\xi_{k}}{\sqrt{k}},\mathcal{N}(0,1)\Big{)}\gtrsim\frac{1}{\sqrt{k}}\gtrsim\frac{k}{n}.$

In other words, we have the desired lower bound in the regime $k=O(n)$.
Notice, however, that the random vector $\bm{\xi}$ is not isotropic, but this
is not a serious problem and it can be easily fixed by appropriately
perturbing $\bm{\xi}$.

Specifically, let $A_{0},A_{1},\dots,A_{n}$ be pairwise disjoint events which
are independent of $\bm{\xi}$ and satisfy $\mathbb{P}(A_{0})=\frac{1}{n-1}$
and $\mathbb{P}(A_{1})=\dots=\mathbb{P}(A_{n})=\frac{n-2}{n(n-1)}$. For every
$i\in[n]$ set

(12.15) $E_{i}\coloneqq\mathbf{1}_{A_{0}}-\frac{n}{n-2}\mathbf{1}_{A_{i}}\ \
\text{ and }\ \ X_{i}\coloneqq\frac{1}{\sigma}(\xi_{i}+E_{i})$

where
$\sigma^{2}\coloneqq\mathbb{E}\big{[}(\xi_{i}+E_{i})^{2}\big{]}=1+\frac{2}{n-2}$.
Using the fact that $\mathbb{E}[\xi_{1}\xi_{2}]=-\frac{1}{n-1}$, it is
straightforward to check that the random vector $\bm{X}=(X_{1},\dots,X_{n})$
is exchangeable, isotropic and bounded—hence, it satisfies (12.7)—and,
moreover,

(12.16) $\mathrm{osc}(\bm{X})=O\Big{(}\frac{1}{n}\Big{)}\ \ \text{ and }\ \
\big{|}\mathbb{E}[X_{1}^{2}X_{2}^{2}]-1\big{|}=O\Big{(}\frac{1}{n}\Big{)}.$

Next let $k\leqslant n$ be a positive integer. Note that the random variable
$\frac{1}{\sqrt{k}}(E_{1}+\dots+E_{k})$ is independent of
$\frac{1}{\sqrt{k}}(\xi_{1}+\dots+\xi_{k})$ and it is highly concentrated
around zero: it takes the value $\sqrt{k}$ with probability $\frac{1}{n-1}$,
the value $-\frac{1}{\sqrt{k}}\cdot\frac{n}{n-2}$ with probability
$\frac{k(n-2)}{n(n-1)}$ and the value $0$ everywhere else. Taking into account
these remarks and using (12.12) and the classical Berry–Esseen theorem, we
obtain that for every $n\gtrsim k\gtrsim n^{2/3}$,

(12.17)
$d_{K}\Big{(}\frac{X_{1}+\dots+X_{k}}{\sqrt{k}},\mathcal{N}(0,1)\Big{)}\gtrsim\frac{k}{n}.$

After observing that the analogue of (12.14) for the random vector $\bm{X}$ is
also valid if $k=O(n^{2/3})$, we see that for every $k=O(n)$,

(12.18)
$d_{K}\Big{(}\frac{X_{1}+\dots+X_{k}}{\sqrt{k}},\mathcal{N}(0,1)\Big{)}\gtrsim\frac{k}{n}.$

Finally, by replacing $\bm{X}$ with a subvector of appropriate
length181818More precisely, of length $cn$ where $c>0$ is a sufficiently small
constant. if necessary, we conclude that (12.18) holds true for every positive
integer $k\leqslant n$; in particular, by (12.8), (12.16) and (12.18), it
follows that the Berry–Esseen bound

(12.19)
$d_{K}\Big{(}\frac{X_{1}+\dots+X_{k}}{\sqrt{k}},\mathcal{N}(0,1)\Big{)}=O\Big{(}\frac{1}{\sqrt{k}}\Big{)}$

is satisfied only in the regime $k=O(n^{2/3})$.

####  12.2. High-dimensional examples

Our goal in this subsection is twofold: to estimate the oscillation of high-
dimensional exchangeable random tensors, and to present related applications.
We first deal with random tensors whose entries have finite fourth moment.
Specifically, we have the following analogue of Fact 12.2. (The proof is left
to the reader.)

######  Fact 12.6.

Let $\bm{X}$ which satisfy _( $\mathcal{A}$1)_ and _( $\mathcal{A}$2)_. Assume
that the entries of $\bm{X}$ have finite fourth moment. Then we have

(12.20)
$\mathrm{osc}(\bm{X})\leqslant\sqrt{\mathrm{pc}(\bm{X})}+\frac{5d}{\sqrt{n}}\big{(}|\delta_{1}|+\mathbb{E}[X_{(1,\dots,d)}^{4}]\big{)}^{1/2}.$

The following proposition estimates the oscillation of dissociated,
exchangeable and symmetric random tensors, as well as the oscillation of their
mixtures.

######  Proposition 12.7.

Let $n,d$ be positive integers with $n\geqslant 4d$, and let $\bm{X}=\langle
X_{i}:i\in[n]^{d}\rangle$ be an exchangeable and symmetric random tensor whose
entries have finite third moment.

  1. (1)

If $\bm{X}$ is dissociated, then

(12.21)
$\mathrm{osc}(\bm{X})\leqslant\frac{16d\,\big{(}\mathbb{E}\big{[}|X_{(1,\dots,d)}|^{3}\big{]}+1\big{)}}{\sqrt[4]{n}}.$

  2. (2)

If $\bm{X}$ is a mixture of dissociated, exchangeable and symmetric random
tensors, then

(12.22)
$\mathrm{osc}(\bm{X})\leqslant\sqrt{\mathrm{pc}(\bm{X})}+\frac{16d\,\big{(}\mathbb{E}\big{[}|X_{(1,\dots,d)}|^{3}\big{]}+1\big{)}}{\sqrt[4]{n}}.$

###### Proof.

We start with the proof of part (1). Set
$K\coloneqq\mathbb{E}\big{[}|X_{(1,\dots,d)}|^{3}\big{]}$. By Hölder’s
inequality, we have $\mathbb{E}\big{[}|X_{i}X_{p}|\big{]}\leqslant K^{2/3}$
for every $i,p\in[n]^{d}$; in particular, $\delta_{1}\leqslant K^{2/3}$.

As in the proof of Proposition 12.3, we will use a truncation argument. Let
$\lambda>0$ be a cut-off parameter which will be specified later. For every
$i\in[n]^{d}$ set

(12.23) $G_{i}\coloneqq X_{i}\,\mathbf{1}_{[|X_{i}|\leqslant\lambda]}\ \ \
\text{ and }\ \ \ B_{i}\coloneqq X_{i}\,\mathbf{1}_{[|X_{i}|>\lambda]}$

and observe that

(12.24) $\|B_{i}\|_{L_{1}}\leqslant\frac{K}{\lambda^{2}}\ \ \ \text{ and }\ \
\ \|B_{i}\|_{L_{2}}\leqslant\sqrt{\frac{K}{\lambda}}.$

Moreover, for every $j\in[n]$ set

(12.25)
$Y_{j}\coloneqq\frac{1}{n^{d-1}}\sum_{\begin{subarray}{c}i\in[n]^{d}\\\
i(1)=j\end{subarray}}X_{i}\ \ \ \text{ and }\ \ \
Z_{j}\coloneqq\frac{1}{n^{d-1}}\sum_{\begin{subarray}{c}i\in[n]^{d}\\\
i(1)=j\end{subarray}}G_{i}.$

By (12.24) and the Cauchy–Schwarz inequality, we have

(12.26)
$\mathbb{E}\big{[}|Y_{j}^{2}-Z^{2}_{j}|\big{]}\leqslant\frac{1}{n^{2d-2}}\\!\\!\\!\sum_{\begin{subarray}{c}i,p\in[n]^{d}\\\
i(1)=p(1)=j\end{subarray}}\\!\\!\\!\big{(}\mathbb{E}\big{[}|G_{i}B_{p}|\big{]}+\mathbb{E}\big{[}|B_{i}G_{p}|\big{]}+\mathbb{E}\big{[}|B_{i}B_{p}|\big{]}\Big{)}\leqslant\frac{3K}{\lambda}$

which yields that

(12.27)
$\displaystyle\mathrm{osc}(\bm{X})\stackrel{{\scriptstyle\eqref{e1.10}}}{{=}}\Big{\|}\frac{1}{n}\sum_{j=1}^{n}Y_{j}^{2}-\delta_{1}\Big{\|}_{L_{1}}\leqslant\Big{\|}\frac{1}{n}\sum_{j=1}^{n}Z_{j}^{2}-\delta_{1}\Big{\|}_{L_{1}}+\frac{3K}{\lambda}\leqslant$
$\displaystyle\leqslant\ \Big{\|}\frac{1}{n}$
$\displaystyle\sum_{j=1}^{n}Z_{j}^{2}-\delta_{1}\Big{\|}_{L_{2}}+\frac{3K}{\lambda}=\Big{(}\frac{1}{n^{2}}\sum_{j_{1},j_{2}=1}^{n}Z^{2}_{j_{1}}Z^{2}_{j_{2}}+\delta_{1}^{2}-2\delta_{1}\frac{1}{n}\sum_{j=1}^{n}Z_{j}^{2}\Big{)}^{1/2}+\frac{3K}{\lambda}.$

Using (12.24) and Hölder’s inequality, it is easy to see that for every
$j\in[n]$,

(12.28)
$\big{|}\mathbb{E}[Z_{j}^{2}]-\delta_{1}\big{|}\leqslant\frac{3K}{\lambda}+\frac{4d^{2}K^{2/3}}{n}\
\ \ \ \text{ and }\ \ \ \ \mathbb{E}[Z_{j}^{4}]\leqslant K\lambda.$

Next, set $i_{1}\coloneqq(1,2,\dots,d)$, $i_{2}\coloneqq(1,d+1,\dots,2d-1)$,
$i_{3}\coloneqq(2d,2d+1,\dots,3d-1)$ and $i_{4}\coloneqq(2d,3d,\dots,4d-2)$ if
$d\geqslant 2$; otherwise, set $i_{1}=i_{2}=1$ and $i_{3}=i_{4}=2$. By the
exchangeability of $\bm{X}$ and Hölder’s inequality, for every
$j_{1},j_{2}\in[n]$ with $j_{1}\neq j_{2}$ we have

(12.29)
$\big{|}\mathbb{E}[Z^{2}_{j_{1}}Z^{2}_{j_{2}}]-\delta_{1}^{2}\big{|}\leqslant\big{|}\mathbb{E}[G_{i_{1}}G_{i_{2}}G_{i_{3}}G_{i_{4}}]-\delta_{1}^{2}\big{|}+\frac{8d^{2}K^{4/3}}{n}+K\lambda\,\frac{8d^{2}}{n};$

on the other hand, by the dissociativity and exchangeability of $\bm{X}$,

(12.30)
$\mathbb{E}[G_{i_{1}}G_{i_{2}}G_{i_{3}}G_{i_{4}}]=\mathbb{E}[G_{i_{1}}G_{i_{2}}]\cdot\mathbb{E}[G_{i_{3}}G_{i_{4}}]=\mathbb{E}[G_{i_{1}}G_{i_{2}}]^{2}.$

Since
$X_{i_{1}}X_{i_{2}}=G_{i_{1}}G_{i_{2}}+G_{i_{1}}B_{i_{2}}+B_{i_{1}}G_{i_{2}}+B_{i_{1}}B_{i_{2}}$
and $\mathbb{E}[X_{i_{1}}X_{i_{2}}]=\delta_{1}$, by (12.24) and Hölder’s
inequality, we obtain that

(12.31)
$\big{|}\mathbb{E}[G_{i_{1}}G_{i_{2}}G_{i_{3}}G_{i_{4}}]-\delta_{1}^{2}\big{|}\leqslant\frac{6K^{5/3}}{\lambda}.$

By (12.27)–(12.31) and setting $\lambda=\sqrt{n}$, we conclude that (12.21) is
satisfied.

We proceed to the proof of part (2). Let $(\Omega,\mathcal{F},\mathbf{P})$ be
a probability space, and assume that $\bm{X}$ is the mixture with respect to
$(\Omega,\mathcal{F},\mathbf{P})$ of the dissociated, exchangeable and
symmetric random tensors191919Here, we assume that this process is
sufficiently measurable. $\langle\bm{X}_{\omega}:\omega\in\Omega\rangle$, that
is,

(12.32) $\mathbb{P}(\bm{X}\in
A)=\mathbf{E}\big{[}\mathbb{P}(\bm{X}_{\omega}\in A)\big{]}$

for every Borel subset $A$ of $\mathbb{R}^{[n]^{d}}$, where $\mathbf{E}$
denotes expectation with respect to $\mathbf{P}$. Since the entries of
$\bm{X}$ have finite third moment, the entries of $\bm{X}_{\omega}$ also have
finite third moment $\mathbf{P}$-almost surely. For every $i\in[n]^{d}$ let
$\bm{X}_{\omega}(i)$ denote the $i$-entry of $\bm{X}_{\omega}$. Set

(12.33)
$Z_{\omega}\coloneqq\frac{1}{n}\sum_{j=1}^{n}\Big{(}\frac{1}{n^{d-1}}\sum_{\begin{subarray}{c}i\in[n]^{d}\\\
i(1)=j\end{subarray}}\bm{X}_{\omega}(i)\Big{)}^{2}$

and observe that

(12.34)
$\mathrm{osc}(\bm{X})=\mathbf{E}\big{[}\|Z_{\omega}-\delta_{1}\|_{L_{1}}\big{]}.$

If $\delta_{1,\omega}\coloneqq\delta_{1}(\bm{X}_{\omega})$ is the parameter in
(1.6) associated with the random tensor $\bm{X}_{\omega}$ and $K_{\omega}$
denotes the absolute third moment of its entries, then, by (12.34), the
triangle inequality for the $L_{1}$-norm and the Cauchy–Schwarz inequality,

(12.35) $\displaystyle\mathrm{osc}(\bm{X})$
$\displaystyle\leqslant\mathbf{E}\big{[}\|Z_{\omega}-\delta_{1,\omega}\|_{L_{1}}\big{]}+\mathbf{E}\big{[}|\delta_{1,\omega}-\delta_{1}|\big{]}$
$\displaystyle=\mathbf{E}\big{[}\mathrm{osc}(\bm{X}_{\omega})\big{]}+\mathbf{E}\big{[}|\delta_{1,\omega}-\delta_{1}|\big{]}\stackrel{{\scriptstyle\eqref{e12.21}}}{{\leqslant}}\mathbf{E}\big{[}|\delta_{1,\omega}-\delta_{1}|\big{]}+\frac{16d\,\big{(}\mathbf{E}[K_{\omega}]+1\big{)}}{\sqrt[4]{n}}$
$\displaystyle\leqslant\sqrt{\big{|}\mathbf{E}[\delta_{1,\omega}^{2}]-\delta_{1}^{2}\big{|}}+\frac{16d\,\big{(}\mathbb{E}\big{[}|X_{(1,\dots,d)}|^{3}\big{]}+1\big{)}}{\sqrt[4]{n}}.$

Finally, since the random tensors
$\langle\bm{X}_{\omega}:\omega\in\Omega\rangle$ are exchangeable and
dissociated, we have

(12.36)
$\mathrm{pc}(\bm{X})=\big{|}\mathbf{E}[\delta_{1,\omega}^{2}]-\delta_{1}^{2}\big{|}.$

Combining (12.35) and (12.36) the result follows. ∎

######  Remark 12.8.

Note that the proof of Proposition 12.7 actually yields the validity of
(12.21) under the slightly weaker hypothesis that the subtensor
$\bm{X}_{[4d-2]}=\langle X_{i}:i\in[4d-2]^{d}\rangle$ of $\bm{X}$ is
dissociated.

#####  12.2.1. Infinitely extendible random tensors

Recall that an exchangeable random tensor $\bm{X}=\langle
X_{i}:i\in[n]^{d}\rangle$ is called infinitely extendible if there exists an
exchangeable (infinite) random tensor $\bm{Y}=\langle
Y_{i}:i\in\mathbb{N}^{d}\rangle$ such that $\bm{Y}_{n}\coloneqq\langle
Y_{i}:i\in[n]^{d}\rangle$ and $\bm{X}$ have the same distribution. It is a
classical observation that exchangeable random tensors might fail to be
infinitely extendible. Nevertheless, many exchangeable random tensors that
appear in practice are infinitely extendible; e.g., all exchangeable random
tensors whose entries are functions of i.i.d. random variables are infinitely
extendible.

Arguably, infinitely extendible exchangeable random tensors are better-
behaved; for instance, it is easy to see that if $\bm{X}$ satisfies
($\mathcal{A}$1) and ($\mathcal{A}$2) and it is infinitely extendible, then
the parameters

$\delta_{0}(\bm{X}),\dots,\delta_{d}(\bm{X})\ \ \ \text{ and }\ \ \
\Sigma_{0}(\bm{X}),\dots,\Sigma_{d}(\bm{X})$

associated with $\bm{X}$ via (1.6), (1.7) and (1.9), are all nonnegative. That
said, we have the following version of Theorem 1.4 for this class of random
tensors.

######  Corollary 12.9.

Let $\bm{X},\bm{\theta}$ which satisfy _( $\mathcal{A}$1)_, _(
$\mathcal{A}$2)_, _( $\mathcal{A}$3)_ with $n\geqslant 4d$, and assume that
$\bm{X}$ is infinitely extendible. Assume, moreover, that
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{1}=1$,
and let $\alpha\in(0,1)$ such that the following non-degenericity condition
holds true

(12.37)
$\delta_{1}>\max\big{\\{}\mathrm{pc}(\bm{X})^{\frac{\alpha}{2}},\delta_{0}^{\alpha}\big{\\}}$

where $\mathrm{pc}(\bm{X})$ is as in (3.7). Then, setting
$\sigma^{2}\coloneqq\mathrm{Var}\big{(}\langle\bm{\theta},\bm{X}\rangle\big{)}$,
we have

(12.38)
$d_{K}\big{(}\langle\bm{\theta},\bm{X}\rangle,\mathcal{N}(0,\sigma^{2})\big{)}\leqslant
E^{\prime\prime}_{1}+E^{\prime\prime}_{2}+E^{\prime\prime}_{3}$

where

(12.39) $\displaystyle E^{\prime\prime}_{1}$ $\displaystyle\coloneqq
5\mathrm{pc}(\bm{X})^{\frac{1-\alpha}{2}}+5\delta_{0}^{1-\alpha}+\frac{\delta_{0}}{d^{2}\delta_{1}}\,\big{|}{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}^{2}_{0}-1\big{|}$
(12.40) $\displaystyle E^{\prime\prime}_{2}$ $\displaystyle\coloneqq
2^{36}\,\frac{\mathbb{E}\big{[}|X_{(1,\dots,d)}|^{3}\big{]}}{\delta_{1}^{3/2}}\Big{(}\sum_{j=1}^{n}\Big{|}\\!\sum_{\begin{subarray}{c}i\in[n]^{d}\\\
i(1)=j\end{subarray}}\theta_{i}\Big{|}^{3}\Big{)}$ (12.41) $\displaystyle
E^{\prime\prime}_{3}$ $\displaystyle\coloneqq
3\kappa\,\frac{1}{d\sqrt{\delta_{1}}}\,\sum_{s=2}^{d}\binom{d}{s}\sqrt{s!}\,\sqrt{\Sigma_{s}}\,{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{s}.$

Here, $\kappa=20d^{3}18^{d}(2d)!$ is as in Theorem _1.4_.

The asymptotic behavior of the normalized averages
$\frac{1}{n^{d-1/2}}\sum_{i\in[n]^{d}_{\mathrm{Inj}}}X_{i}$ which correspond
to a random tensor $\bm{X}=\langle X_{i}:i\in[n]^{d}\rangle$ as in Corollary
12.9, is well-studied in the literature; see, e.g., [BCRT58, DDG21, EW78,
Si76]. For this particular case, Corollary 12.9 yields Berry–Esseen bounds
under the conditions

(12.42) $\delta_{0}=0,\ \ \ \ \mathrm{pc}(\bm{X})=0\ \ \ \text{ and }\ \ \
\delta_{1}>0.$

These conditions also cover the case of several popular statistics (e.g., non-
degenerate, possibly weighted, U-statistics).

###### Proof of Corollary _12.9_.

Let $\bm{Y}=\langle Y_{i}:i\in\mathbb{N}^{d}\rangle$ be an exchangeable
(infinite) random tensor such that $\bm{X}$ and $\bm{Y}_{n}$ have the same
distribution, where for every integer $N\geqslant d$ by $\bm{Y}_{N}$ we denote
the subtensor $\langle Y_{i}:i\in[N]^{d}\rangle$ of $\bm{Y}$. By
($\mathcal{A}$2), we see that $\bm{Y}$ is also symmetric and its diagonal
terms vanish. Therefore, by the Aldous–Hoover theorem [Ald81, Hoo79], $\bm{Y}$
is a mixture of exchangeable, dissociated and symmetric infinite random
tensors whose diagonal terms vanish. This property is inherited, of course, to
the subtensors of $\bm{Y}$. In particular, for every integer $N\geqslant n$
the finite tensor $\bm{Y}_{N}$ is a mixture of exchangeable, dissociated and
symmetric random tensors and, consequently, part (2) of Proposition 12.7 can
be applied to $\bm{Y}_{N}$; also notice that

  1. —

the entries of $\bm{Y}_{N}$ and $\bm{X}$ have the same absolute third moment,

  2. —

$\delta_{s}(\bm{X})=\delta_{s}(\bm{Y}_{N})$ and
$\Sigma_{s}(\bm{X})=\Sigma_{s}(\bm{Y}_{N})$ for every $s\in\\{0,\dots,d\\}$,
and

  3. —

$\mathrm{pc}(\bm{X})=\mathrm{pc}(\bm{Y}_{N})$.

Next fix a real tensor $\bm{\theta}=\langle\theta_{i}:i\in[n]^{d}\rangle$
which satisfies ($\mathcal{A}$3) and with
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{1}=1$.
Let $N\geqslant n$ be an arbitrary integer. We extend $\bm{\theta}$ to a real
tensor $\bm{\theta}_{N}=\langle\theta_{i}:i\in[N]^{d}\rangle$ by setting
$\theta_{i}=0$ if $i\notin[n]^{d}$; clearly we have
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{s}={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}_{N}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{s}$
for every $s\in\\{0,\dots,d\\}$. Moreover, the random variables
$\langle\bm{\theta},\bm{X}\rangle$ and
$\langle\bm{\theta}_{N},\bm{Y}_{N}\rangle$ have the same distribution. By the
previous observations and (12.22), we have

(12.43)
$\mathrm{osc}(\bm{Y}_{N})\leqslant\sqrt{\mathrm{pc}(\bm{X})}+\frac{16d\,\big{(}\mathbb{E}\big{[}|X_{(1,\dots,d)}|^{3}\big{]}+1\big{)}}{\sqrt[4]{N}}$

while, by (11.35),

(12.44)
$B_{N}=\Big{\|}\frac{1}{N^{d}}\sum_{i\in[N]^{d}}Y_{i}\Big{\|}_{L_{2}}^{2}\leqslant\delta_{0}+\frac{4d^{2}}{N}.$

By (12.43), (12.44) and (12.37), we see that the non-degenericity condition
(1.11) for the random tensor $\bm{Y}_{N}$ is satisfied for every sufficiently
large positive integer $N$. The result follows by applying Theorem 1.4 to
$\bm{Y}_{N},\bm{\theta}_{N}$ and using (12.43), and then taking the limit as
$N$ goes to infinity. ∎

####  12.3. Anticoncentration of polynomials: proof of Theorem 3.2

Let $n,d,\kappa,k$ and $\bm{\xi}=(\xi_{1},\dots,\xi_{n})$ be as in the
statement of the theorem, and fix a polynomial $f$ as in (3.13). We define a
random tensor $\bm{X}=\langle X_{i}:i\in[n]^{d}\rangle$ and a real tensor
$\bm{\theta}=\langle\theta_{i}:i\in[n]^{d}\rangle$ by setting
$X_{i}=\theta_{i}=0$ if $i\notin[n]^{d}_{\mathrm{Inj}}$, and

(12.45)
$X_{i}\coloneqq\prod_{r=1}^{d}\xi_{i_{r}}-\mathbb{E}\Big{[}\prod_{r=1}^{d}\xi_{i_{r}}\Big{]}\
\ \ \ \text{ and }\ \ \ \
\theta_{i}\coloneqq\frac{a_{\\{i_{1},\dots,i_{d}\\}}}{d!}$

for every $i=(i_{1},\dots,i_{d})\in[n]^{d}_{\mathrm{Inj}}$, where
$\bm{\alpha}=\langle a_{F}:F\in\binom{[n]}{d}\rangle$ are the coefficients of
$f$. It is clear that with these choices we have
$\langle\bm{\theta},\bm{X}\rangle=f(\bm{\xi})-\mathbb{E}\big{[}f(\bm{\xi})\big{]}$
and, consequently,

  1. —

$\mathrm{Var}\big{(}\langle\bm{\theta},\bm{X}\rangle\big{)}=\mathrm{Var}\big{(}f(\bm{\xi})\big{)}$,
and

  2. —

$\mathcal{L}_{\langle\bm{\theta},\bm{X}\rangle}(\varepsilon)=\mathcal{L}_{f(\bm{\xi})}(\varepsilon)$
for every $\varepsilon>0$.

Also notice that $\bm{X}$ and $\bm{\theta}$ satisfy the basic assumptions
($\mathcal{A}$1), ($\mathcal{A}$2) and ($\mathcal{A}$3). Moreover, by a
tedious but fairly straightforward computation, it is not hard to see that

(12.46) $\displaystyle\big{|}\delta_{s}-p^{2d-s}(1-p^{s})\big{|}\leqslant
p^{2d-s}\,\frac{12d^{2}}{k}\ \ \text{ for every }s\in\\{0,\dots,d\\}$ (12.47)
$\displaystyle\big{|}\Sigma_{s}-p^{2d-s}(1-p)^{s}\big{|}\leqslant
p^{2d-s}(1+p)^{s}\,\frac{12d^{2}}{k}\ \ \text{ for every }s\in\\{1,\dots,d\\}$
(12.48) $\displaystyle\mathrm{osc}(\bm{X})\leqslant
p^{2d-1}\,\frac{15d^{2}}{k}$ (12.49) $\displaystyle
B=\Big{\|}\frac{1}{n^{d}}\sum_{i\in[n]^{d}}X_{i}\Big{\|}_{L_{2}}^{2}=0$

where $p=k/n$. By (3.15), (12.46), (12.48) and (12.49), it follows that the
non-degenericity condition (1.11) is satisfied with $\alpha=1/2$. Therefore,
after appropriately normalizing, by Theorem 1.4 we obtain that

(12.50) $\displaystyle
d_{K}\big{(}\langle\bm{\theta},\bm{X}\rangle,\mathcal{N}(0,\sigma^{2})$
$\displaystyle\big{)}\leqslant\frac{8\kappa}{\sqrt{p}}\cdot\frac{1}{\sqrt{n}}+\frac{6}{(1-p){\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}^{2}_{1}}\cdot\frac{{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}^{2}_{0}}{n}\,+$
$\displaystyle+\frac{2^{38}p^{3/2}}{p^{3d}(1-p)^{3/2}{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}^{3}_{1}}\Big{(}\sum_{j=1}^{n}\Big{|}\\!\sum_{\begin{subarray}{c}i\in[n]^{d}\\\
i(1)=j\end{subarray}}\theta_{i}\Big{|}^{3}\Big{)}\,+$
$\displaystyle+\frac{8\kappa
p^{1/2}}{dp^{d}(1-p)^{1/2}{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{1}}\,\sum_{s=2}^{d}\binom{d}{s}\sqrt{s!}\,\sqrt{p^{2d-s}(1-p)^{s}}\,{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{s}$

where we have used (3.15) and (12.46)–(12.49). Next observe that for every
$\varepsilon>0$,

(12.51)
$\displaystyle\mathcal{L}_{\langle\bm{\theta},\bm{X}\rangle}(\varepsilon)$
$\displaystyle\leqslant\mathcal{L}_{\mathcal{N}(0,\sigma^{2})}(\varepsilon)+2d_{K}\big{(}\langle\bm{\theta},\bm{X}\rangle,\mathcal{N}(0,\sigma^{2})\big{)}$
$\displaystyle\hskip
42.67912pt\leqslant\frac{\varepsilon}{\sqrt{2\pi}\,\sigma}+2d_{K}\big{(}\langle\bm{\theta},\bm{X}\rangle,\mathcal{N}(0,\sigma^{2})\big{)}.$

On the other hand, by the choice of the random tensor $\bm{\theta}$ in (12.45)
and the definitions of the relevant seminorms in (1.5) and (3.14), for every
$s\in\\{0,\dots,d\\}$ we have

(12.52)
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{s}=\frac{(d-s)!}{d!}\,\sqrt{s!}\,{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\alpha}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{s}.$

Combining (12.50), (12.51) and (12.52), we see that (3.17) is satisfied.

Finally, in order to verify the estimate for the variance $\sigma^{2}$ of
$f(\bm{\xi})$ observe that

(12.53)
$\sigma^{2}=\mathrm{Var}\big{(}\langle\bm{\theta},\bm{X}\rangle\big{)}\stackrel{{\scriptstyle\eqref{e1.8},\eqref{e1.9}}}{{=}}\sum_{s=0}^{d}\binom{d}{s}^{2}\,s!\,\Sigma_{s}\,{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\theta}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{s}^{2}\stackrel{{\scriptstyle\eqref{e12.52}}}{{=}}\sum_{s=0}^{d}\Sigma_{s}\,{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\bm{\alpha}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{s}^{2}.$

Thus, (3.16) follows from (12.53) together with (12.46), (12.47) and (3.15).

###  Appendix A Proof of Lemma 7.3

The argument is an interesting and nontrivial instance of the Stein/Chen
method of normal approximation via concentration (see, e.g., [BC14, Section
6]).

####  A.1.

Recall that $n,d$ are positive integers with $d\geqslant 2$ and $n\geqslant
4d^{2}$. We start by setting

(A.1) $\delta\coloneqq 16\,\frac{\Lambda}{n}\ \ \ \text{ and }\ \ \
\eta_{\delta}\coloneqq\frac{n}{4}\,\mathbb{E}\big{[}|\Xi_{1}-\Xi_{1}^{\prime}|\cdot\min\\{|\Xi_{1}-\Xi_{1}^{\prime}|,\delta\\}\,|\,\pi_{1}\big{]}.$

Notice that, by (7.6), we have

(A.2)
$\delta\geqslant\frac{n}{4}\,\mathbb{E}\big{[}|\Xi_{1}-\Xi_{1}^{\prime}|^{3}\big{]}.$

Using (7.5), (7.6), (A.2) and the fact that
$\min(\alpha,\beta)\geqslant\alpha-\frac{\alpha^{2}}{4\beta}$ for every
$\alpha\geqslant 0$ and $\beta>0$, we obtain that

(A.3) $\displaystyle\mathbb{E}[\eta_{\delta}]$
$\displaystyle=\frac{n}{4}\,\mathbb{E}\big{[}|\Xi_{1}-\Xi_{1}^{\prime}|\cdot\min\\{|\Xi_{1}-\Xi_{1}^{\prime}|,\delta\\}\big{]}$
$\displaystyle\geqslant\frac{n}{4}\,\mathbb{E}\big{[}(\Xi_{1}-\Xi_{1}^{\prime})^{2}\big{]}-\frac{n}{16\delta}\,\mathbb{E}\big{[}|\Xi_{1}-\Xi_{1}^{\prime}|^{3}\big{]}=1-\frac{n^{2}}{16^{2}\Lambda}\,\mathbb{E}\big{[}|\Xi_{1}-\Xi_{1}^{\prime}|^{3}\big{]}\geqslant\frac{3}{4}.$

######  Sublemma A.1.

We have

(A.4) $\mathrm{Var}(\eta_{\delta})\leqslant 2^{9}\delta^{2}.$

We postpone the proof of Sublemma A.1 to the end of this appendix.

####  A.2.

Now let $z\in\mathbb{R}$ be arbitrary. We will show that the probabilities
$\mathbb{P}(z-|\Theta|\leqslant\Xi_{1}\leqslant z)$ and
$\mathbb{P}\big{(}z\leqslant\Xi_{1}\leqslant z+|\Theta|\big{)}$ are both
upper-bounded by the quantity appearing in the right-hand-side of (7.20);
clearly, this is enough to complete the proof. The argument is symmetric, and
so we shall focus on bounding the probability
$\mathbb{P}\big{(}z\leqslant\Xi_{1}\leqslant z+|\Theta|\big{)}$.

Let $f_{\Theta}\colon\mathbb{R}\to\mathbb{R}$ be defined by

(A.5)
$f_{\Theta}(x)\coloneqq\begin{cases}-\big{(}\frac{1}{2}|\Theta|+\delta\big{)}&\text{if
}x\leqslant z-\delta,\\\ -\frac{1}{2}|\Theta|+x-z&\text{if
}z-\delta<x<z+|\Theta|+\delta,\\\ \frac{1}{2}|\Theta|+\delta&\text{if
}x\geqslant z+|\Theta|+\delta.\end{cases}$

By ($\mathcal{E}$4), the pair $(\pi_{1},\pi_{2})$ is exchangeable. Hence, by
(7.1) and (7.19), we have

(A.6)
$\mathbb{E}\big{[}(\Xi_{1}^{\prime}-\Xi_{1})\big{(}f_{\Theta}(\Xi_{1}^{\prime})+f_{\Theta^{\prime}}(\Xi_{1})\big{)}\big{]}=0$

which in turn implies, after adding
$2\,\mathbb{E}\big{[}(\Xi_{1}-\Xi_{1}^{\prime})f_{\Theta}(\Xi_{1})\big{]}$ and
multiplying by $\frac{n}{4}$, that

(A.7) $\displaystyle\frac{n}{2}\,$
$\displaystyle\mathbb{E}\big{[}(\Xi_{1}-\Xi^{\prime}_{1})f_{\Theta}(\Xi_{1})\big{]}=$
$\displaystyle=\frac{n}{4}\,\mathbb{E}\big{[}(\Xi_{1}^{\prime}-\Xi_{1})\big{(}f_{\Theta^{\prime}}(\Xi_{1})-f_{\Theta}(\Xi_{1})\big{)}\big{]}+\frac{n}{4}\,\mathbb{E}\big{[}(\Xi_{1}^{\prime}-\Xi_{1})\big{(}f_{\Theta}(\Xi_{1}^{\prime})-f_{\Theta}(\Xi_{1})\big{)}\big{]}.$

Moreover, by (7.4), we have

(A.8)
$\frac{n}{2}\,\mathbb{E}\big{[}(\Xi_{1}^{\prime}-\Xi_{1})f_{\Theta}(\Xi_{1})\big{]}=\frac{n}{2}\,\mathbb{E}\big{[}f_{\Theta}(\Xi_{1})\,\mathbb{E}[\Xi_{1}^{\prime}-\Xi_{1}\,|\,\pi_{1}]\big{]}=\mathbb{E}\big{[}f_{\Theta}(\Xi_{1})\Xi_{1}\big{]}$

and so, by (7.3), the Cauchy–Schwarz inequality and the fact that
$\|f_{\Theta}\|_{L_{\infty}}\leqslant\delta+\frac{1}{2}|\Theta|$,

(A.9)
$\Big{|}\frac{n}{2}\,\mathbb{E}\big{[}(\Xi_{1}^{\prime}-\Xi_{1})f_{\Theta}(\Xi_{1})\big{]}\Big{|}\leqslant\delta\,\mathbb{E}\big{[}|\Xi_{1}|\big{]}+\frac{1}{2}\,\mathbb{E}\big{[}|\Xi_{1}\Theta|\big{]}\leqslant\delta+\frac{1}{2}\,\|\Theta\|_{L_{2}}.$

By the definition of $\Theta$ in (7.19), the triangle inequality and (7.7), we
thus have

(A.10)
$\Big{|}\frac{n}{2}\,\mathbb{E}\big{[}(\Xi_{1}^{\prime}-\Xi_{1})f_{\Theta}(\Xi_{1})\big{]}\Big{|}\leqslant\delta+e^{d}(2d)!\,\sum_{s=2}^{d}\sqrt{\frac{\beta_{s}}{n^{s}}}.$

Next observe that
$\|f_{\Theta}-f_{\Theta^{\prime}}\|_{L_{\infty}}\leqslant\frac{1}{2}\,\big{|}|\Theta|-|\Theta^{\prime}|\big{|}\leqslant\frac{1}{2}\,|\Theta-\Theta^{\prime}|$.
Hence,

(A.11)
$\displaystyle\Big{|}\frac{n}{4}\,\mathbb{E}\big{[}(\Xi_{1}^{\prime}-\Xi_{1})(f_{\Theta^{\prime}}(\Xi_{1})-f_{\Theta}(\Xi_{1}))\big{]}\Big{|}\leqslant\Big{|}\frac{n}{8}\,\mathbb{E}\big{[}|\Xi_{1}^{\prime}-\Xi_{1}|\cdot|\Theta-\Theta^{\prime}|\big{]}\Big{|}$
$\displaystyle\leqslant\frac{n}{8}\,$
$\displaystyle\|\Xi_{1}^{\prime}-\Xi_{1}\|_{L_{2}}\|\Theta-\Theta^{\prime}\|_{L_{2}}\stackrel{{\scriptstyle\eqref{e7.5},\eqref{e7.19}}}{{\leqslant}}\,\frac{\sqrt{n}}{4}\sum_{s=2}^{d}\|\Xi_{s}-\Xi_{s}^{\prime}\|_{L_{2}}\leqslant
2\,d^{2}e^{d}(2d)!\,\sum_{s=2}^{d}\sqrt{\frac{\beta_{s}}{n^{s}}}$

where we have used the Cauchy–Schwarz inequality, the triangle inequality and
(7.8).

From this point on, the proof proceeds exactly as in [BC05, Lemma 2.2]. More
precisely, in order to estimate the second term of the right-hand-side of
(A.7), by the fundamental theorem of calculus, we have

(A.12) $\displaystyle A$
$\displaystyle\coloneqq\frac{n}{4}\,\mathbb{E}\big{[}(\Xi_{1}^{\prime}-\Xi_{1})\big{(}f_{\Theta}(\Xi_{1}^{\prime})-f_{\Theta}(\Xi_{1})\big{)}\big{]}=\frac{n}{4}\,\mathbb{E}\Big{[}(\Xi_{1}^{\prime}-\Xi_{1})\int_{0}^{\Xi_{1}^{\prime}-\Xi_{1}}\\!\\!f^{\prime}_{\Theta}(\Xi_{1}+t)\,dt\Big{]}$
$\displaystyle\,=\frac{n}{4}\,\mathbb{E}\Big{[}(\Xi_{1}^{\prime}-\Xi_{1})\int_{-\infty}^{+\infty}f^{\prime}_{\Theta}(\Xi_{1}+t)\,\big{(}\mathbf{1}_{[0,\Xi_{1}^{\prime}-\Xi_{1}]}(t)-\mathbf{1}_{[\Xi_{1}^{\prime}-\Xi_{1},0]}(t)\big{)}\,dt\Big{]}$

with the convention that $\mathbf{1}_{[\beta,\alpha]}$ is constantly $0$ if
$\alpha<\beta$. Also observe that, by (A.5), we have
$f^{\prime}_{\Theta}=\mathbf{1}_{[z-\delta,z+\delta+|\Theta|]}$ which implies
that for every $t\in\mathbb{R}$,

  1. $\bullet$

$(\Xi_{1}^{\prime}-\Xi_{1})\,f^{\prime}_{\Theta}(\Xi_{1}+t)\,\big{(}\mathbf{1}_{[0,\Xi_{1}^{\prime}-\Xi_{1}]}(t)-\mathbf{1}_{[\Xi_{1}^{\prime}-\Xi_{1},0]}(t)\big{)}\geqslant
0$.

Therefore,

(A.13)
$A\geqslant\frac{n}{4}\,\mathbb{E}\Big{[}\int_{|t|\leqslant\delta}(\Xi_{1}^{\prime}-\Xi_{1})\,\mathbf{1}_{[z-\delta,z+\delta+|\Theta|]}(\Xi_{1}+t)\,\big{(}\mathbf{1}_{[0,\Xi_{1}^{\prime}-\Xi_{1}]}(t)-\mathbf{1}_{[\Xi_{1}^{\prime}-\Xi_{1},0]}(t)\big{)}\,dt\Big{]}.$

Moreover, for every $|t|\leqslant\delta$ we have

  1. $\bullet$

$(\Xi_{1}^{\prime}-\Xi_{1})\,\big{(}\mathbf{1}_{[0,\Xi_{1}^{\prime}-\Xi_{1}]}(t)-\mathbf{1}_{[\Xi_{1}^{\prime}-\Xi_{1},0]}(t)\big{)}\geqslant
0$ and

  2. $\bullet$

$\mathbf{1}_{[z-\delta,z+\delta+|\Theta|]}(\Xi_{1}+t)\geqslant\mathbf{1}_{[z,z+|\Theta|]}(\Xi_{1})$,

and so, by (A.13),

(A.14) $\displaystyle
A\geqslant\frac{n}{4}\,\mathbb{E}\Big{[}\mathbf{1}_{[z,z+|\Theta|]}(\Xi_{1})\,(\Xi_{1}^{\prime}-\Xi_{1})\int_{|t|\leqslant\delta}\big{(}\mathbf{1}_{[0,\Xi_{1}^{\prime}-\Xi_{1}]}(t)-\mathbf{1}_{[\Xi_{1}^{\prime}-\Xi_{1},0]}(t)\big{)}\,dt\Big{]}$
$\displaystyle=\ \,$
$\displaystyle\frac{n}{4}\,\mathbb{E}\big{[}\mathbf{1}_{[z,z+|\Theta|]}(\Xi_{1})\,|\Xi_{1}^{\prime}-\Xi_{1}|\cdot\min\big{\\{}\delta,|\Xi_{1}^{\prime}-\Xi_{1}|\big{\\}}\big{]}$
$\displaystyle\stackrel{{\scriptstyle\eqref{ea.1}}}{{=}}$
$\displaystyle\mathbb{E}\big{[}\mathbf{1}_{[z,z+|\Theta|]}(\Xi_{1})\,\eta_{\delta}\big{]}\geqslant\mathbb{E}\big{[}\mathbf{1}_{[z,z+|\Theta|]}(\Xi_{1})\big{]}\,\mathbb{E}[\eta_{\delta}]-\big{|}\mathbb{E}\big{[}\mathbf{1}_{[z,z+|\Theta|]}(\Xi_{1})\big{(}\eta_{\delta}-\mathbb{E}[\eta_{\delta}]\big{)}\big{]}\big{|}$
$\displaystyle\stackrel{{\scriptstyle\eqref{ea.3}}}{{\geqslant}}$
$\displaystyle\frac{3}{4}\,\mathbb{P}\big{(}z\leqslant\Xi_{1}\leqslant
z+|\Theta|\big{)}-\big{|}\mathbb{E}\big{[}\mathbf{1}_{[z,z+|\Theta|]}(\Xi_{1})\big{(}\eta_{\delta}-\mathbb{E}[\eta_{\delta}]\big{)}\big{]}\big{|}.$

On the other hand, by Sublemma A.1 and inequality
$\alpha\beta\leqslant\frac{1}{2}\,(\alpha^{2}+\beta^{2})$ applied for
“$\alpha=\frac{1}{\sqrt{2}}\,\mathbf{1}_{[z,z+|\Theta|]}(\Xi_{1})$” and
“$\beta=\sqrt{2}\,(\eta_{\delta}-\mathbb{E}[\eta_{\delta}])$”, we see that

(A.15)
$\displaystyle\mathbb{E}\big{[}\mathbf{1}_{[z,z+|\Theta|]}(\Xi_{1})\big{(}\eta_{\delta}-\mathbb{E}[\eta_{\delta}]\big{)}\big{]}$
$\displaystyle\leqslant\frac{1}{2}\,\Big{(}\frac{1}{2}\,\mathbb{P}\big{(}z\leqslant\Xi_{1}\leqslant
z+|\Theta|\big{)}+2\mathrm{Var}(\eta_{\delta})\Big{)}$
$\displaystyle\leqslant\frac{1}{4}\,\mathbb{P}\big{(}z\leqslant\Xi_{1}\leqslant
z+|\Theta|\big{)}+2^{9}\delta^{2}.$

Thus, by (A.14) and (A.15), we have

(A.16) $A\geqslant\frac{1}{2}\,\mathbb{P}\big{(}z\leqslant\Xi_{1}\leqslant
z+|\Theta|\big{)}-2^{9}\delta^{2}.$

Invoking the choice of $\delta$ in (A.1) and the choice of $A$ in (A.12) and
combining (A.7), (A.10), (A.11) and (A.16), we conclude that

(A.17) $\mathbb{P}\big{(}z\leqslant\Xi_{1}\leqslant z+|\Theta|\big{)}\leqslant
2^{5}\frac{\Lambda}{n}+2^{17}\frac{\Lambda^{2}}{n^{2}}+5d^{2}e^{d}(2d)!\sum_{s=2}^{d}\sqrt{\frac{\beta_{s}}{n^{s}}}.$

####  A.3. Proof of Sublemma A.1

Let $\bm{\zeta}\colon[n]^{2}\times[n]^{2}\to\mathbb{R}$ be defined by setting

(A.18) $\displaystyle\bm{\zeta}(i,j,p,q)$
$\displaystyle\coloneqq|\bm{\xi}_{1}(i,p)+\bm{\xi}_{1}(j,q)-\bm{\xi}_{1}(i,q)-\bm{\xi}_{1}(j,p)|\
\times$ $\displaystyle\hskip
56.9055pt\times\min\big{\\{}|\bm{\xi}_{1}(i,p)+\bm{\xi}_{1}(j,q)-\bm{\xi}_{1}(i,q)-\bm{\xi}_{1}(j,p)|,\delta\big{\\}}$

for every $i,j,p,q\in[n]$ with $i\neq j$ and $p\neq q$; otherwise, set
$\bm{\zeta}(i,j,p,q)=0$. Then observe that, by the choice of $\eta_{\delta}$
in (A.1), we have

(A.19)
$\eta_{\delta}=\frac{n}{4}\,\mathbb{E}\big{[}|\Xi_{1}-\Xi_{1}^{\prime}|\cdot\min\big{\\{}|\Xi_{1}-\Xi_{1}^{\prime}|,\delta\big{\\}}\,|\,\pi_{1}\big{]}=\frac{1}{4n}\,\sum_{\begin{subarray}{c}i,j\in[n]\\\
i\neq j\end{subarray}}\bm{\zeta}\big{(}i,j,\pi_{1}(i),\pi_{1}(j)\big{)}.$

Also recall that, by ($\mathcal{E}$3), $\pi_{1}$ is uniformly distributed on
$\mathbb{S}_{n}$. Thus, (A.19) asserts the random variable $\eta_{\delta}$ can
be expressed as the $Z$-statistic of order two associated with the tensor
$\bm{\zeta}$ which has a rather special form.

The proof is based on a specific decomposition of this $Z$-statistic. This
decomposition, also introduced by Barbour/Chen [BC05], is less symmetric than
the decomposition described in Section 9 (yet it has enough symmetries in
order to be computationally useful), but it has the advantage that its non-
constant components are mean zero random variables. Of course, this property
is very useful for computing the variance. For the convenience of the reader
we shall briefly recall this decomposition; for more information we refer to
[BC05].

Specifically, for every $i,j,p,q\in[n]$ set

$\bm{\zeta}(i,j,\cdot,q)\coloneqq\frac{1}{n-1}\sum_{\begin{subarray}{c}r\in[n]\\\
r\neq q\end{subarray}}\bm{\zeta}(i,j,r,q),\ \ \
\bm{\zeta}(i,j,p,\cdot)\coloneqq\frac{1}{n-1}\sum_{\begin{subarray}{c}r\in[n]\\\
r\neq p\end{subarray}}\bm{\zeta}(i,j,p,r),$ $\hskip
4.26773pt\bm{\zeta}(i,j,\cdot,\cdot)\coloneqq\frac{1}{n(n-1)}\sum_{\begin{subarray}{c}r,s\in[n]\\\
r\neq s\end{subarray}}\bm{\zeta}(i,j,r,s),\ \ \
\bm{\zeta}(i,\cdot,p,\cdot)\coloneqq\frac{1}{(n-1)^{2}}\sum_{\begin{subarray}{c}r,s\in[n]\\\
r\neq i,s\neq p\end{subarray}}\bm{\zeta}(i,r,p,s),$
$\\!\bm{\zeta}(i,\cdot,\cdot,\cdot)\coloneqq\frac{1}{n(n-1)^{2}}\sum_{\begin{subarray}{c}r,s,\ell\in[n]\\\
\ell\neq i,r\neq s\end{subarray}}\\!\bm{\zeta}(i,\ell,r,s),\ \ \
\bm{\zeta}(\cdot,j,\cdot,q)\coloneqq\frac{1}{(n-1)^{2}}\sum_{\begin{subarray}{c}r,s\in[n]\\\
r\neq j,s\neq q\end{subarray}}\\!\bm{\zeta}(r,j,s,q),$ $\hskip
8.5359pt\bm{\zeta}(\cdot,j,\cdot,\cdot)\coloneqq\frac{1}{n(n-1)^{2}}\sum_{\begin{subarray}{c}r,s,\ell\in[n]\\\
\ell\neq j,r\neq s\end{subarray}}\\!\bm{\zeta}(\ell,j,r,s),\ \ \
\bm{\zeta}(\cdot,\cdot,\cdot,\cdot)\coloneqq\frac{1}{n^{2}(n-1)^{2}}\sum_{\begin{subarray}{c}r,s,k,\ell\in[n]\\\
r\neq s,k\neq\ell\end{subarray}}\\!\bm{\zeta}(r,s,k,\ell).$

Then, for every $i,j,p,q\in[n]$ we define

(A.20) $\displaystyle\bm{\zeta}_{D}(i,j,p,q)$
$\displaystyle\coloneqq\bm{\zeta}(i,j,p,q)-\bm{\zeta}(i,j,\cdot,q)-\bm{\zeta}(i,j,p,\cdot)+\bm{\zeta}(i,j,\cdot,\cdot)$
(A.21) $\displaystyle\bm{\zeta}_{D}(i,\cdot,p,\cdot)$
$\displaystyle\coloneqq\bm{\zeta}(i,\cdot,p,\cdot)-\bm{\zeta}(i,\cdot,\cdot,\cdot)$
(A.22) $\displaystyle\bm{\zeta}_{D}(\cdot,j,\cdot,q)$
$\displaystyle\coloneqq\bm{\zeta}(\cdot,j,\cdot,q)-\bm{\zeta}(\cdot,j,\cdot,\cdot).$

Notice that for every $i,p,q\in[n]$ we have $\bm{\zeta}_{D}(i,i,p,q)=0$;
moreover, for every $i,j\in[n]$,

(A.23) $\sum_{\begin{subarray}{c}p,q\in[n]\\\ p\neq
q\end{subarray}}\bm{\zeta}_{D}(i,j,p,q)=0,\ \ \ \
\sum_{p=1}^{n}\bm{\zeta}_{D}(i,\cdot,p,\cdot)=0\ \ \text{ and }\ \
\sum_{p=1}^{n}\bm{\zeta}_{D}(\cdot,i,\cdot,p)=0.$

By (A.19) and the previous definitions, we may decompose $\eta_{\delta}$ as

(A.24) $\displaystyle\eta_{\delta}$
$\displaystyle=\frac{1}{4n}\sum_{\begin{subarray}{c}i,j\in[n]\\\ i\neq
j\end{subarray}}\bm{\zeta}_{D}\big{(}i,j,\pi_{1}(i),\pi_{1}(j)\big{)}+\frac{n-1}{4n}\sum_{i=1}^{n}\bm{\zeta}_{D}\big{(}\cdot,i,\cdot,\pi_{1}(i)\big{)}\
+$ $\displaystyle\hskip
85.35826pt+\frac{n-1}{4n}\sum_{i=1}^{n}\bm{\zeta}_{D}\big{(}i,\cdot,\pi_{1}(i),\cdot\big{)}+\frac{n-1}{4}\bm{\zeta}(\cdot,\cdot,\cdot,\cdot).$

Invoking (A.23) and the fact that $\pi_{1}$ is uniformly distributed on
$\mathbb{S}_{n}$ we see, in particular, that
$\mathbb{E}[\eta_{\delta}]=\frac{n-1}{4}\bm{\zeta}(\cdot,\cdot,\cdot,\cdot)$.
Therefore,

(A.25) $\displaystyle\mathrm{Var}(\eta_{\delta})$
$\displaystyle\leqslant\frac{3}{2^{4}n^{2}}\,\mathbb{E}\Big{[}\Big{(}\sum_{\begin{subarray}{c}i,j\in[n]\\\
i\neq
j\end{subarray}}\bm{\zeta}_{D}\big{(}i,j,\pi_{1}(i),\pi_{1}(j)\big{)}\Big{)}^{2}\Big{]}\,+$
$\displaystyle\hskip
28.45274pt+\frac{3}{2^{4}}\,\mathbb{E}\Big{[}\Big{(}\sum_{i=1}^{n}\bm{\zeta}_{D}\big{(}\cdot,i,\cdot,\pi_{1}(i)\big{)}\Big{)}^{2}\Big{]}+\frac{3}{2^{4}}\,\mathbb{E}\Big{[}\Big{(}\sum_{i=1}^{n}\bm{\zeta}_{D}\big{(}i,\cdot,\pi_{1}(i),\cdot\big{)}\Big{)}^{2}\Big{]}$
$\displaystyle\coloneqq E_{1}+E_{2}+E_{3}.$

Finally, using the Cauchy–Schwarz inequality, (A.23) and arguing202020The
argument in this context is actually simpler. as in Subsection 5.6, it is not
hard to verify that

(A.26) $E_{1}\leqslant\Big{(}\frac{2^{6}3}{n}+2^{6}3\Big{)}\delta^{2},\ \ \ \
E_{2}\leqslant 2^{3}3\delta^{2}\ \ \text{ and }\ \ E_{3}\leqslant
2^{3}3\delta^{2}.$

By (A.25), (A.26) and the fact that $n\geqslant 3$, we conclude that (A.4) is
satisfied.

### References

  * [Ald81] D. J. Aldous, Representations for partially exchangeable arrays of random variables, J. Multivariate Anal. 11 (1981), 581–597.
  * [Ald83] D. J. Aldous, Exchangeability and Related Topics, in “École d’été de Probabilités de Saint-Flour XIII”, Lecture Notes in Mathematics, Vol. 1117, Springer, 1983, 1–198.
  * [BC05] A. D. Barbour and L. H. Y. Chen, The permutation distribution of matrix correlation statistics, in “Stein’s Method and Applications”, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, Vol. 5, Singapore University Press, 2005, 223–245.
  * [BC14] A. D. Barbour and L. H. Y. Chen, Stein’s (magic) method, preprint (2014), available at https://arxiv.org/pdf/1411.1179.pdf.
  * [BE86] A. D. Barbour and G. K. Eagleson, Random association of symmetric arrays, Stoch. Anal. Appl. 4 (1986), 239–281.
  * [BCRT58] J. R. Blum, H. Chernoff, H. Rosenblatt and H. Teicher, Central limit theorems for interchangeable processes, Canada J. Math. 10 (1958), 222–229.
  * [Bob04] S. G. Bobkov, Concentration of normalized sums and a central limit theorem for noncorrelated random variables, Ann. Probab. 32 (2004), 2884–2908.
  * [BCG18] S. G. Bobkov, G. P. Chistyakov and F. Götze, Berry–Esseen bounds for typical weighted sums, Electron. J. Probab. 23 (2018), 1–22.
  * [Bo84] E. Bolthausen, An estimate of the remainder in a combinatorial central limit theorem, Z. Wahrsch. Verw. Gebiete 66 (1984), 379–386.
  * [BG93] E. Bolthausen and F. Götze, The rate of convergence for multivariate sampling statistics, Ann. Statist. 21 (1993), 1692–1710.
  * [BoG01] M. Bloznelis and F. Götze, Orthogonal decomposition of finite population statistics and its distributional asymptotics, Ann. Statist. 29 (2001), 899–917.
  * [BoG02] M. Bloznelis and F. Götze, An Edgeworth expansion for symmetric finite population statistics, Ann. Probab. 30 (2002), 1238–1265.
  * [CW01] A. Carbery and J. Wright, Distributional and $L^{q}$ norm inequalities for polynomials over convex bodies in $\mathbb{R}^{n}$, Math. Res. Lett. 8 (2001), 233–248.
  * [Ch14] S. Chatterjee, A short survey of Stein’s method, in “Proceedings of the International Congress of Mathematicians” Vol. IV, 13–21, Seoul, Korea, 2014.
  * [CF15] L. H. Y. Chen and X. Fang, On the error bound in a combinatorial central limit theorem, Bernoulli 21 (2015), 335–359.
  * [CGS11] L. H. Y. Chen, L. Goldstein and Q. M. Shao, Normal Approximation by Stein’s Method, Probability and Its Applications. Springer, 2011.
  * [CS07] L. H. Y. Chen and Q. M. Shao, Normal approximation for nonlinear statistics using a concentration inequality approach, Bernoulli, 13 (2007), 581–599.
  * [CTV06] K. P. Costello, T. Tao and V. Vu, Random symmetric matrices are almost surely nonsingular, Duke Math. J. 135 (2006), 395–413.
  * [Da44] H. E. Daniels, The relation between measures of correlation in the universe of sample permutations, Biometrika 33 (1944), 129–135.
  * [DDG21] L. Davezies, X. D’Haultfœuille and Y. Guyonvarch, Empirical process results for exchangeable arrays, Ann. Stat. 49 (2021), 845–862.
  * [DF80] P. Diaconis and D. Freedman, Finite exchangeable sequences, Ann. Probab. 8 (1980), 745–764.
  * [DF87] P. Diaconis and D. Freedman, A dozen de Finetti-style results in search of a theory, Ann. Inst. Henri Poincaré Probab. Stat. 23 (1987), 397–423.
  * [DKP22] Ch. Döbler, M. Kasprzak and G. Peccati, The multivariate functional de Jong CLT, Probab. Theory Related Fields 184 (2022), 367–399.
  * [EW78] G. K. Eagleson and N. C. Weber, Limit theorems for weakly exchangeable arrays, Math. Proc. Camb. Philos. Soc. 84 (1978), 123–130.
  * [Erd45] P. Erdős, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898–902.
  * [FKMW18] Y. Filmus, G. Kindler, E. Mossel and K. Wimmer, Invariance principle on the slice, ACM Trans. Comput. Theory 10 (2018), Article No. 11, 37 p.
  * [FM19] Y. Filmus and E. Mossel, Harmonicity and invariance on slices of the Boolean cube, Probab. Theory Related Fields 175 (2019), 721–782.
  * [GKP94] R. L. Graham, D. E. Knuth and O. Patashnik, Concrete mathematics: a foundation for computer science, 2nd ed., Addison-Wesley Publishing Group, 1994.
  * [Ho48] W. Hoeffding, A class of statistics with asymptotically normal distribution, Ann. Math. Statist. 19 (1948), 293–325.
  * [Ho51] W. Hoeffding, A combinatorial central limit theorem, Ann. Math. Statist. 22 (1951), 558–566.
  * [Hoo79] D. N. Hoover, Relations on probability spaces and arrays of random variables, preprint (1979), available at https://www.stat.berkeley.edu/~aldous/Research/hoover.pdf.
  * [deJ90] P. de Jong, A central limit theorem for generalized multilinear forms, J. Multivariate Anal. 34 (1990), 275–289.
  * [Kal05] O. Kallenberg, Probabilistic Symmetries and Invariance Principles, Probability and its Applications (New York), Springer, 2005.
  * [KST19] M. Kwan, B. Sudakov and T. Tran, Anticoncentration for subgraph statistics, J. Lond. Math. Soc. 99 (2019), 757–777.
  * [LO43] J. E. Littlewood and A. C. Offord, On the number of real roots of a random algebraic equation. III, Rec. Math. (Mat. Sbornik), Nouvelle Série 12 (1943), 277–286.
  * [LLTTY17] A. E. Litvak, A. Lytova, K. Tikhomirov, N. Tomczak-Jaegermann and P. Youssef, Adjacency matrices of random digraphs: singularity and anti-concentration, J. Math. Anal. Appl. 445 (2017), 1447–1491.
  * [Lo96] W. L. Loh, On Latin hypercube sampling, Ann. Statist. 24 (1996), 2058–2080.
  * [MNV16] R. Meka, O. Nguyen and V. Vu, Anti-concentration for polynomials of independent random variables, Theory Comput. 12 (2016), Paper No. 11, 16 pages.
  * [MOO10] E. Mossel, R. O’Donnell and K. Oleszkiewicz, Noise stability of functions with low influences: invariance and optimality, Ann. Math. 171 (2010), 295–341.
  * [NV13] H. H. Nguyen and V. Vu, Small ball probability, inverse theorems, and applications, in “Erdős centennial”, Bolyai Society Mathematical Studies, Vol. 25, Springer, 2013, 409–463.
  * [NP12] I. Nourdin and G. Peccati, Normal Approximations with Malliavin Calculus. From Stein’s Method to Universality, Cambridge Tracts in Mathematics, Vol. 192, Cambridge University Press, 2012.
  * [P04] G. Peccati, Hoeffding–ANOVA decompositions for symmetric statistics of exchangeable observations, Ann. Probab. 32 (2004), 1796–1829.
  * [PP11] G. Peccati and J.-R. Pycke, Hoeffding spaces and Specht modules, ESAIM Probab. Stat. 15 (2011), S58–S68.
  * [RV13] A. Razborov and E. Viola, Real advantage, ACM Trans. Comput. Theory 5 (2013), Article No. 17, 1–8.
  * [Ro55] H. Robbins, A remark on Stirling’s formula, Amer. Math. Monthly 62 (1955), 26–29.
  * [RS96] J. Rosiński and G. Samorodnitsky, Symmetrization and concentration inequalities for multilinear forms with applications to zero-one laws for Lévy chaos, Ann. Probab. 24 (1996), 422–437.
  * [Se80] R. J. Serfling, Approximation theorems of mathematical statistics, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, 1980.
  * [Si76] B. W. Silverman, Limit theorems for dissociated random variables, Adv. Appl. Probab. 8 (1976), 806–819.
  * [St82] C. Stein, A bound for the error in the normal approximation to the distribution of a sum of dependent random variables, in “Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, Vol. II: Probability Theory”, Univ. California Press, 1982, 583–602.
  * [St86] C. Stein, Approximate Computation of Expectations, Institute of Mathematical Statistics Lecture Notes – Monograph Series, Vol. 7, Hayward, CA, 1986.
  * [Vu14] V. Vu, Concentration and anti-concentration, available at https://www.ima.umn.edu/2014-2015/W9.8-12.14/21252.
  * [WW44] A. Wald and J. Wolfowitz, Statistical tests based on permutation of the observations, Ann. Math. Statist. 15 (1944), 358–372.
  * [ZC90] L. Zhao and X. Chen, Normal approximation for finite-population U-statistics, Acta Math. Appl. Sinica 6 (1990), 263–272.
  * [ZBCL97] L. Zhao, Z. Bai, C.-C. Chao and W.-Q. Liang, Error bound in a central limit theorem of double-indexed permutation statistics, Ann. Statist. 25 (1997), 2210–2227.