Marchenko-Pastur law for a random tensor model.

Pavel Yaskov111Steklov Mathematical Institute of RAS, Moscow, Russia
e-mail<EMAIL_ADDRESS>
This work is supported by the Russian Science Foundation under grant
18-71-10097.

###### Abstract

We study the limiting spectral distribution of large-dimensional sample
covariance matrices associated with symmetric random tensors formed by
$\binom{n}{d}$ different products of $d$ variables chosen from $n$ independent
standardized random variables. We find optimal sufficient conditions for this
distribution to be the Marchenko-Pastur law in the case $d=d(n)$ and
$n\to\infty$. Our conditions reduce to $d^{2}=o(n)$ when the variables have
uniformly bounded fourth moments. The proofs are based on a new concentration
inequality for quadratic forms in symmetric random tensors and a law of large
numbers for elementary symmetric random polynomials.

Keywords: random matrices; random tensors; sample covariance matrices.

##  1 Introduction

The paper studies the limiting behaviour of empirical spectral distributions
of large-dimensional sample covariance matrices associated with the random
tensor model investigated in [5]. Namely, we consider sample covariance
matrices of the form

$\widehat{\Sigma}_{N}=\frac{1}{N}\sum_{k=1}^{N}\mathbf{x}_{pk}\mathbf{x}_{pk}^{\top},$
(1)

where $\\{\mathbf{x}_{pk}\\}_{k=1}^{N}$ are i.i.d. copies of a random vector
$\mathbf{x}_{p}$ in ${\mathbb{R}}^{p}$ following the model below.

######  Definition 1.1.

A random vector $\mathbf{x}_{p}$ in ${\mathbb{R}}^{p}$ follows the random
tensor model with parameters $d,n\in{\mathbb{N}},$ $d\leqslant n,$ if
$p={{n}\choose{d}}$ and the following holds. There exists a random vector
$X=(X_{\alpha})_{\alpha=1}^{n}$ in ${\mathbb{R}}^{n}$ such that
$\\{X_{\alpha}\\}_{\alpha=1}^{n}$ are independent, have zero mean and unit
variance and $\mathbf{x}_{p}$ could be obtained by vectorizing the symmetric
tensor $X^{\otimes d}$, i.e. the entries of $\mathbf{x}_{p}$ could be indexed
by $d$-element subsets $i\subseteq\\{1,\ldots,n\\}$ and defined as products
$\prod_{\alpha\in i}X_{\alpha}.$

Bryson, Vershynin, and Zhao [5] show that the limiting spectral distribution
of $\widehat{\Sigma}_{N}$ is the Marchenko-Pastur (MP) law if $N\to\infty$,
$\binom{n}{d}/N$ tends to a positive constant, the fourth moments of
$X_{\alpha}=X_{\alpha}(d,n)$ are uniformly bounded, and $d^{3}=o(n).$ However,
they conjecture that the optimal condition is $d^{2}=o(n)$. We prove this
conjecture in our paper. The proof is based on a general version of the MP
theorem and a new concentration inequality for quadratic forms in symmetric
random tensors.

Concentration properties of quadratic forms provide a powerful tool to study
the asymptotic behaviour of empirical spectral distributions of sample
covariance and related random matrices (see [3], [4], [6], [10], [12], [15]
[23], [28], [31]). In particular, [30] gives necessary and sufficient
conditions for the MP theorem in terms of concentration of certain quadratic
forms. For various models of data, the concentration properties are
established in [4], [5], [20], [23], [29], [31], [32], among others.

Lytova [20] obtains concentration inequalities for quadratic forms in non-
symmetric random tensors $X^{(1)}\otimes\ldots\otimes X^{(d)}$ generated by
$d$ independent copies of an isotropic random vector $X$ in
${\mathbb{R}}^{n}$, quadratic forms in which concentrate around their means.
In the simplest $L_{2}$ case, the results of [20] are derived from the Efron-
Stein inequality for the variance of a function in $\\{X^{(k)}\\}_{k=1}^{d}$.
When all $X=X(n)$, $n\in{\mathbb{N}},$ have independent entries with uniformly
bounded fourth moments, Theorem 1.2 and Remark 4.1 in [20] give a version of
the MP theorem for the non-symmetric random tensor model under the assumption
$d=o(n)$ (that seems to be optimal). Recently, Vershynin [27] proves
corresponding exponential concentration inequalities, assuming that $X$ has
independent subgaussian entries.

In this paper, we derive $L_{2}$ concentration inequalities for quadratic
forms in symmetric random tensors with optimal dependence on $d$ (at least,
when $d=O(n)$). Our results improve those of [5] and have some relevance to
random chaoses. However, as noted in [5], known concentration inequalities for
random chaoses [1], [2], [11], [16], [17], [18] exhibit an unspecified
(possibly exponential) dependence on the degree $d$, which is too bad for our
problem. Also, comparing to the non-symmetric case, the strong dependence
structure of the symmetric random tensor model highly complicates its
analysis. In particular, for the quadratic form given by the squared $l_{2}$
norm, $\|X^{(1)}\otimes\ldots\otimes X^{(d)}\|^{2}$ is the product
$\prod_{k=1}^{d}\|X^{(k)}\|^{2}$ of independent random variables and
$\|X^{\otimes d}\|^{2}$ is the elementary symmetric polynomial of order $d$ in
the squared entries of $X$. The latter plays a key role in the context of the
MP theorem for the symmetric random tensor model, as the necessary condition
for the theorem is given by $\binom{n}{d}^{-1}\|X^{\otimes d}\|^{2}\to 1$ in
probability when $X=X(n)$, $d=d(n)$, and $n\to\infty$ (see Section 2). This
condition could be viewed as a law of large numbers for elementary symmetric
polynomials in independent nonnegative random variables. The asymptotic
behaviour of such polynomials is thoroughly studied in [7], [14], [21], [26].
Using the saddle-point approximation method of [14], we find necessary and
sufficient conditions (in terms of $d$ and $n$) for the above law of large
numbers in the i.i.d. case.

The paper is structured as follows. Section 2 contains main results. The
proofs are deferred to Section 3. Auxiliary results are proved in the
Supplementary Material.

##  2 Main results

Let us introduce some notation. For all $p\geqslant 1$, let $\mathbf{x}_{p}$
be a random vector in ${\mathbb{R}}^{p}$ and let ${\mathbb{R}}^{p\times p}$ be
the set of all real $p\times p$ matrices. For $A\in{\mathbb{R}}^{p\times p}$,
denote its spectral norm by $\|A\|$ and, for symmetric $A$, let $\mu_{A}$ be
its empirical spectral distribution defined by
$\mu_{A}:=p^{-1}\sum_{i=1}^{p}\delta_{\lambda_{i}},$ where
$\\{\lambda_{i}\\}_{i=1}^{p}$ is the set of eigenvalues of $A$ (here we allow
$\lambda_{i}=\lambda_{j}$ for $i\neq j$) and $\delta_{\lambda}$ stands for a
Dirac measure with mass at $\lambda\in{\mathbb{R}}$. Also, put
${\mathbb{C}}_{+}:=\\{z\in{\mathbb{C}}:{\rm\,Im}(z)>0\\}$. Denote further by
${\mathcal{B}}({\mathbb{R}}_{+})$ the Borel $\sigma$-algebra of
${\mathbb{R}}_{+}$, by $|S|$ the cardinality of a set $S$, by $\mathbf{1}(S)$
the indicator function of $S$, and by $[n]_{d}$ the set
$\\{i\subseteq\\{1,\ldots,n\\}:|i|=d\\}$. For a set of random variables
$X_{n}$, write $X_{n}=o_{\mathbb{P}}(1)$ if $X_{n}$ tends to 0 in probability
as $n\to\infty$, and $X_{n}=O_{\mathbb{P}}(1)$ if the set of variables $X_{n}$
is stochastically bounded. All random elements below will be defined on the
same probability space.

Recall the definition of the Marchenko-Pastur law $\mu_{\rho}$ ($\rho>0$),
i.e.

$d\mu_{\rho}=\max\\{1-1/\rho,0\\}\,d\delta_{0}+\frac{\sqrt{(a_{+}-x)(x-a_{-})}}{2\pi
x\rho}{\mathbf{1}}\big{(}a_{-}\leqslant x\leqslant a_{+}\big{)}\,dx\,\text{
for }\,a_{\pm}=(1\pm\sqrt{\rho})^{2},$

and a version of the Marchenko-Pastur theorem (going back to [22]) under the
following general assumption222For independent but not identically distributed
$\\{\mathbf{x}_{pk}\\}_{k=1}^{N}$ given in the definition of
$\widehat{\Sigma}_{N}$, one can replace (A) by its averaged version as in
Section 2 of [28], when stating the Marchenko-Pastur theorem. However, to
simplify the presentation, we consider only the i.i.d. case in this paper.
that quadratic forms in $\mathbf{x}_{p}$ weakly concentrate around some
values:

(A)
$(\mathbf{x}_{p}^{\top}A_{p}\mathbf{x}_{p}-{\mathrm{tr}}(A_{p}))/p\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}0$
as $p\to\infty$ for all sequences of symmetric positive semidefinite
$A_{p}\in{\mathbb{R}}^{p\times p}$ with $\|A_{p}\|\leqslant 1$.

######  Theorem 2.1.

Let $p=p(N)\in{\mathbb{N}}$ satisfy $p/N\to\rho>0$ as $N\to\infty$. Let also
$\mathbf{x}_{p}$ be a random vector in ${\mathbb{R}}^{p}$ for every $p$. If
$\rm(A)$ holds, then

${\mathbb{P}}(\mu_{\widehat{\Sigma}_{N}}\to\mu_{\rho}\text{ weakly,
}N\to\infty)=1.$ (2)

Furthermore, if (2) holds and
${\mathbb{E}}\mathbf{x}_{p}\mathbf{x}_{p}^{\top}=I_{p}$ for all $p$, then
$\mathbf{x}_{p}^{\top}\mathbf{x}_{p}/p\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}1$
as $p=p(N)\to\infty$.

The first part of the theorem follows from Theorem 2 in [31] (where we take
$\Sigma_{T}=I_{T}$) and the classical Marchenko-Pastur theorem for
$\mathbf{x}_{p}$ having i.i.d. Gaussian entries. The second part of the
theorem follows from Theorem 1.1 in [30].

To apply Theorem 2.1, one has to check (A). For the random tensor model, this
could be done via the following concentration inequality, which is our first
main result (for its proof, see Section 3).

######  Theorem 2.2.

Let $d,n\in{\mathbb{N}}$, $n\geqslant 16d,$ and $p=\binom{n}{d}$. If
$\mathbf{x}_{p}$ is a random vector in ${\mathbb{R}}^{p}$ following the random
tensor model and $A_{p}\in{\mathbb{R}}^{p\times p}$, then

${\rm Var}(\mathbf{x}_{p}^{\top}A_{p}\mathbf{x}_{p})\leqslant
p\,{\mathrm{tr}}(A_{p}A_{p}^{\top})\begin{cases}(1+K_{n}d/n)^{d}-1&\text{if
}A_{p}\text{ is diagonal},\\\ (1+2K_{n}d/n)^{d}(16d/n)(d\wedge 8)&\text{if
}A_{p}\text{ is zero-diagonal},\\\ 64K_{n}d^{2}/n&\text{if }A_{p}\text{ is
arbitrary, }2K_{n}d^{2}\leqslant n,\end{cases}$

where $K_{n}=\max\\{{\mathbb{E}}X_{\alpha}^{4}:1\leqslant\alpha\leqslant n\\}$
with $X_{\alpha}$ constituting $\mathbf{x}_{p}$ according to Definition 1.1.

Theorem 2.2 improves the corresponding upper bound in Theorem 1.9 in [5] by a
factor of $n^{-1/3}$ (up to some constants). The latter follows from

$\frac{K_{n}d^{2}}{n}=\frac{(K_{n}^{1/2}d/n^{1/3})^{2}}{n^{1/3}}\quad\text{and}\quad{\mathrm{tr}}(A_{p}A_{p}^{\top})\leqslant\|A_{p}A_{p}^{\top}\|{\mathrm{tr}}(I_{p})=p\|A_{p}\|^{2}.$

Note also that if $X_{\alpha}$ are i.i.d. over $\alpha$, then ${\rm
Var}(\mathbf{x}_{p}^{\top}\mathbf{x}_{p})\geqslant p^{2}(K_{n}-1)d^{2}/n$ by
Theorem 5.2 of Hoeffding [13]. This shows the sharpness of our bound.

Theorem 2.2 guarantees that (A) holds for any sequence of random vectors
$\mathbf{x}_{p}$ following the random tensor model with $p=\binom{n}{d}$ and
$X_{\alpha}=X_{\alpha}(d,n)$, when $K_{n}d^{2}=o(n)$ and $n\to\infty$ (here
$d,n$ may depend on some parameter $N$ that goes to infinity). This along with
Theorem 2.1 gives a version of the Marchenko-Pastur theorem for the random
tensor model under the fourth moment condition, extending Theorem 1.5 of [5],
where it is assumed that $d^{3}=o(n)$ and $K_{n}=O(1)$. We can state a more
general result, assuming only that the second moments are finite.

######  Theorem 2.3.

Let $d=d(N),n=n(N)\in{\mathbb{N}}$, $N\in{\mathbb{N}}$, satisfy $d\leqslant n$
and $\binom{n}{d}/N\to\rho>0$, whereinafter all limits are with respect to
$N\to\infty$. Assume also that, for each $p=\binom{n}{d}$, $\mathbf{x}_{p}$ is
a random vector in ${\mathbb{R}}^{p}$ that follows the random tensor model
with parameters $d,n$ and $X_{\alpha}=X_{\alpha}(d,n),$ $\alpha=1,\ldots,n$.
Then (2) follows from (3), where

$d{\mathbb{E}}X_{\alpha}^{2}\mathbf{1}(dX_{\alpha}^{2}>n)\to 0\text{ and
}\dfrac{d^{2}}{n}{\mathbb{E}}X_{\alpha}^{4}\mathbf{1}(dX_{\alpha}^{2}\leqslant
n)\to 0\text{ uniformly in $\alpha\in\\{1,\ldots,n\\}$.}$ (3)

Conversely, (2) implies (3) if, for all $d,n$,
$\\{X_{\alpha}\\}_{\alpha=1}^{n}$ are independent copies of a random variable
$X$ not depending on $d,n$ and such that ${\mathbb{E}}X=0,$
${\mathbb{E}}X^{2}=1>{\mathbb{P}}(X^{2}=1)$.

Theorem 2.3 is proved in Section 3. The sufficiency part of the theorem
follows from Theorem 2.1 and 2.2. The necessity part follows from Theorem 2.1
and the following law of large numbers (LLN) for elementary symmetric
polynomials of the form

$S_{n}^{(d)}:=\sum_{1\leqslant i_{1}<\ldots<i_{d}\leqslant n}Z_{i_{1}}\cdots
Z_{i_{d}},\quad d,n\in{\mathbb{N}}.$

######  Theorem 2.4.

Let $Z,Z_{1},Z_{2},\ldots$ be i.i.d. nonnegative nondegenerate random
variables. If ${\mathbb{E}}Z=1$ and $d=d(n)\in\\{1,\ldots,n\\}$ for
$n\in{\mathbb{N}},$ then the following are equivalent as $n\to\infty$:

(i)
$S_{n}^{(d)}/\binom{n}{d}\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}1$,

(ii) $d(S_{n}/n-1)\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}0$ for
$S_{n}=S_{n}^{(1)}$,

(iii) $d{\mathbb{E}}Z\mathbf{1}(dZ>n)\to 0$ and
$d^{2}{\mathbb{E}}Z^{2}\mathbf{1}(dZ\leqslant n)=o(n)$.

Theorem 2.4 is proved in Section 3. It gives necessary conditions for LLN for
the $U$-statistic $U_{n}^{(d)}:=S_{n}^{(d)}/\binom{n}{d}$. The asymptotic
distribution of this $U$-statistic is thoroughly studied in [7], [14], [21],
[26] for various asymptotic regimes. In particular, as is shown in [7], under
linear norming, the distribution may differ significantly for the cases
$d^{2}=o(n)$, $d^{2}\sim cn$, and $d^{2}/n\to\infty$. However, to the best of
our knowledge, there is no result in the literature, which gives
(i)$\Rightarrow$(ii) under no assumptions on $d,n$, and higher-order moments
of $Z$.333If $U_{n}^{(d)}\to 1$ in $L_{2}$, one can prove (ii) by using the
following fact from the theory of $U$-statistics: $d(S_{n}/n-1)$ is the Hájek
projection of $U_{n}^{(d)}-1$ in $L_{2}$, i.e. the projection on the set of
sums $\sum_{k=1}^{n}f_{k}(Z_{k})$, in particular,
${\mathbb{E}}|d(S_{n}/n-1)|^{2}\leqslant{\mathbb{E}}|U_{n}^{(d)}-1|^{2}$.
However, this argument works well only for $L_{2}$ convergence. To prove
(i)$\Rightarrow$(ii), we first show that (i) implies $d^{2}=o(n)$ and then use
the asymptotic representation for $S_{n}^{(d)}$ from Lemma 2.5 below. In the
case of positive $Z$, the lemma follows from formula (8) in [26], but the
latter is stated without the proof. For completeness, we prove Lemma 2.5 in
the Supplementary Material.

######  Lemma 2.5.

Under the conditions of Theorem 2.3, let $d^{2}=o(n)$ and $d\to\infty$. Then

$\ln\frac{S_{n}^{(d)}}{\binom{n}{d}}=\sum_{k=1}^{n}\ln(Z_{k}/\rho+1)-d+d\ln(\rho
d/n)+o_{\mathbb{P}}(1),\quad n\to\infty,$ (4)

where $\rho=\rho(n,Z_{1},\ldots,Z_{n})$ is the unique solution of the equation
$\sum_{k=1}^{n}\rho/(Z_{k}+\rho)=n-d$ if such solution exists and $\rho=1$
otherwise.

##  3 Proofs

###### Proof of Theorem 2.1..

For brevity, we will write $\mathbf{x}$, $A$, $K$ instead of $\mathbf{x}_{p},$
$A_{p}$, $K_{n}$. Let further $\mathbf{x}=(x_{i})$, $A=(a_{ij})$, where $i,j$
run all elements of $[n]_{d}$($=\\{i\subseteq\\{1,\ldots,n\\}:|i|=d\\}$).
Assume w.l.o.g. that $A$ is non-zero (the result is trivial otherwise). First,
consider the case of diagonal $A$. We have ${\rm
Var}(\mathbf{x}^{\top}A\mathbf{x})=\sum
a_{ii}a_{jj}\mathrm{Cov}(x_{i}^{2},x_{j}^{2}),$ where the sum is over all
$i,j\in[n]_{d}$. Note that $\mathrm{Cov}(x_{i}^{2},x_{j}^{2})=0$ if $i\cap
j=\varnothing$ and

$|\mathrm{Cov}(x_{i}^{2},x_{j}^{2})|\leqslant{\mathbb{E}}x_{i}^{2}x_{j}^{2}=\prod_{\alpha\in
i\Delta j}{\mathbb{E}}X_{\alpha}^{2}\prod_{\beta\in i\cap
j}{\mathbb{E}}X_{\beta}^{4}\leqslant K^{|i\cap j|}\text{ for any $i,j.$}$

The latter along with the Cauchy inequality yields

${\rm Var}(\mathbf{x}^{\top}A\mathbf{x})\leqslant\frac{1}{2}\sum_{i,j:i\cap
j\not=\varnothing}(a_{ii}^{2}+a_{jj}^{2})K^{|i\cap j|}=\sum_{i,j:i\cap
j\not=\varnothing}a_{ii}^{2}K^{|i\cap
j|}=\sum_{t=1}^{d}K^{t}\sum_{i}a_{ii}^{2}\sum_{j:|i\cap j|=t}1.$

If $|i\cap j|=t(\leqslant d)$ is fixed, then there are ${{d}\choose{t}}$
choices for choosing $i\cap j$ for any given $i$ and $\binom{n-d}{d-t}$
choices for choosing $j\setminus i$ for any given $i$ and $i\cap j$.
Therefore, the very last sum is equal to $\binom{d}{t}\binom{n-d}{d-t}$. As
$d\leqslant n,$ we see that

$\frac{\binom{n-d}{d-t}}{\binom{n}{d}}=\frac{d!/(d-t)!}{n!/(n-t)!}\frac{(n-d)!/(n-d-(d-t))!}{(n-t)!/(n-d)!}\leqslant\prod_{s=0}^{t-1}\frac{d-s}{n-s}\prod_{r=0}^{d-t-1}\frac{n-d-r}{n-t-r}\leqslant\bigg{(}\frac{d}{n}\bigg{)}^{t}1^{d-t}.$

Combining the above bounds and recalling that $p=\binom{n}{d}$, we derive that

${\rm Var}(\mathbf{x}^{\top}A\mathbf{x})\leqslant
p\,{\mathrm{tr}}(AA^{\top})\sum_{t=1}^{d}\binom{d}{t}(Kd/n)^{t}=p\,{\mathrm{tr}}(AA^{\top})((1+Kd/n)^{d}-1).$

Consider the case of zero-diagonal $A$. Let $\Delta_{t}:=\sum
a_{ij}x_{i}x_{j}\mathbf{1}(|i\cap j|=t)$, $t\in[0,d)\cap{\mathbb{Z}}_{+}$,
where the sum is over $i,j\in[n]_{d}$. By the triangle inequality for the norm
$\|\cdot\|_{2}=\sqrt{{\mathbb{E}}|\cdot|^{2}}$,

$\sqrt{{\rm
Var}(\mathbf{x}^{\top}A\mathbf{x})}=\sqrt{{\mathbb{E}}|\mathbf{x}^{\top}A\mathbf{x}|^{2}}=\Big{\|}\sum_{t=0}^{d-1}\Delta_{t}\Big{\|}_{2}\leqslant\sum_{t=0}^{d-1}\|\Delta_{t}\|_{2}=\sum_{t=0}^{d-1}\sqrt{{\mathbb{E}}|\Delta_{t}|^{2}}.$

Let us estimate ${\mathbb{E}}|\Delta_{t}|^{2}$ for any fixed $t$. By
definition,

${\mathbb{E}}|\Delta_{t}|^{2}=\sum_{\begin{subarray}{c}i,j,k,l:|i\cap
j|=|k\cap l|=t\end{subarray}}a_{ij}a_{kl}{\mathbb{E}}x_{i}x_{j}x_{k}x_{l}.$

The product $x_{i}x_{j}x_{k}x_{l}$ is equal to

$\prod_{\alpha\in\Lambda_{1}}X_{\alpha}\prod_{\beta\in\Lambda_{2}}X_{\beta}^{2}\prod_{\gamma\in\Lambda_{3}}X_{\gamma}^{3}\prod_{\delta\in\Lambda_{4}}X_{\delta}^{4},$

where $\Lambda_{c}=\Lambda_{c}(i,j,k,l),$ $c=1,\ldots,4,$ contains all
$\alpha\in i\cup j\cup k\cup l$ that are covered by exactly $c$ sets among
$i,j,k,l$. If $|\Lambda_{1}|\neq 0$, then
${\mathbb{E}}x_{i}x_{j}x_{k}x_{l}=0$. When $|\Lambda_{1}|=0$, it follows from
the independence of $\\{X_{\alpha}\\}_{\alpha=1}^{n}$ and the Cauchy–Schwarz
inequality that

$|{\mathbb{E}}x_{i}x_{j}x_{k}x_{l}|=\prod_{\gamma\in\Lambda_{3}}|{\mathbb{E}}X_{\gamma}^{3}|\prod_{\delta\in\Lambda_{4}}{\mathbb{E}}X_{\delta}^{4}\leqslant
K^{|\Lambda_{4}|}\prod_{\gamma\in\Lambda_{3}}\sqrt{{\mathbb{E}}X_{\gamma}^{4}{\mathbb{E}}X_{\gamma}^{2}}\leqslant
K^{s},$

where $s:=|\Lambda_{3}|/2+|\Lambda_{4}|\in{\mathbb{Z}}_{+}$ if
$|\Lambda_{1}|=0$ by
$|\Lambda_{1}|+2|\Lambda_{2}|+3|\Lambda_{3}|+4|\Lambda_{4}|=4d$. We get that

${\mathbb{E}}|\Delta_{t}|^{2}\leqslant\sum_{s\in{\mathbb{Z}}_{+}}K^{s}\sum_{(i,j,k,l)\in\Gamma(s,t)}|a_{ij}a_{kl}|$

for $\Gamma(s,t):=\\{(i,j,k,l):|i\cap j|=|k\cap
l|=t,|\Lambda_{1}|=0,|\Lambda_{3}|/2+|\Lambda_{4}|=s\\}$ and
$\Lambda_{c}=\Lambda_{c}(i,j,k,l)$, $c=1,3,4$.

By symmetry, for all given $i,j$ with $|i\cap j|=t$, the sets
$\\{(k,l):(i,j,k,l)\in\Gamma(s,t)\\}$ have the same cardinality. Let us denote
this cardinality by $\gamma(s,t)$. By the Cauchy inequality,

$\sum_{(i,j,k,l)\in\Gamma(s,t)}|a_{ij}a_{kl}|\leqslant\frac{1}{2}\sum_{(i,j,k,l)\in\Gamma(s,t)}(a_{ij}^{2}+a_{kl}^{2})=\sum_{(i,j,k,l)\in\Gamma(s,t)}a_{ij}^{2}=\gamma(s,t)\sum_{i,j:|i\cap
j|=t}a_{ij}^{2}.$

Combining the above bounds (for all $t$) along with the Cauchy-Schwartz
inequality gives

$\sqrt{{\rm
Var}(\mathbf{x}^{\top}A\mathbf{x})}\leqslant\sum_{t=0}^{d-1}\sqrt{\sum_{i,j:|i\cap
j|=t}a_{ij}^{2}}\sqrt{\sum_{s\in{\mathbb{Z}}_{+}}K^{s}\gamma(s,t)}\leqslant\sqrt{{\mathrm{tr}}(AA^{\top})}\sqrt{\sum_{t=0}^{d-1}\sum_{s\in{\mathbb{Z}}_{+}}K^{s}\gamma(s,t)}.$

######  Lemma 3.1.

Under the above notations, for all $t\in[0,d)\cap{\mathbb{Z}}_{+}$ and
$s\in{\mathbb{Z}}_{+},$ we have

$\gamma(s,t)\leqslant
2^{4(d-t)}\binom{n}{d}\binom{t}{s}2^{s}(d/n)^{d-(t-s)}{\bf 1}(s\leqslant t).$

Lemma 3.1 is proved in the Supplementary Material. For $p=\binom{n}{d}$, it
implies that

$\frac{{\rm
Var}(\mathbf{x}^{\top}A\mathbf{x})}{p\,{\mathrm{tr}}(AA^{\top})}\leqslant\sum_{t=0}^{d-1}\bigg{(}\frac{2^{4}d}{n}\bigg{)}^{d-t}\sum_{s=0}^{t}\binom{t}{s}\bigg{(}\frac{2Kd}{n}\bigg{)}^{s}=\sum_{t=0}^{d-1}\bigg{(}\frac{16d}{n}\bigg{)}^{d-t}\bigg{(}1+\frac{2Kd}{n}\bigg{)}^{t}.$

If $S$ is the last sum, then $S\leqslant(16d^{2}/n)(1+2Kd/n)^{d}$. Also, as
$n\geqslant 16d$ and $K\geqslant({\mathbb{E}}X_{1}^{2})^{2}=1$,

$S=\frac{16d}{n}\frac{(1+2Kd/n)^{d}-(16d/n)^{d}}{1+2Kd/n-16d/n}\leqslant\frac{16d}{n}\frac{(1+2Kd/n)^{d}}{1-14d/n}\leqslant\frac{2^{7}d}{n}(1+2Kd/n)^{d}.$

This proves the desired bound for zero-diagonal $A$. The variance bound for an
arbitrary matrix $A$ follows from the corresponding bounds for
$A_{0}=(a_{ij}\mathbf{1}(i=j))_{i,j\in[n]_{d}}$ and $A_{1}=A-A_{0}$ along with
the inequalities $\sqrt{{\rm
Var}(\mathbf{x}^{\top}A\mathbf{x})}\leqslant\sqrt{{\rm
Var}(\mathbf{x}^{\top}A_{0}\mathbf{x})}+\sqrt{{\rm
Var}(\mathbf{x}^{\top}A_{1}\mathbf{x})}$, $K\geqslant 1,$ $(1+x)^{d}\leqslant
e^{dx}$ and $(1+x)^{d}-1\leqslant dxe^{dx}$, $x\geqslant 0$.

∎

###### Proof of Theorem 2.3.

Suppose (ii) holds. To apply Theorem 2.1, we will verify (A). For each
$p=\binom{n}{d}$, let $A_{p}\in{\mathbb{R}}^{p\times p}$ be a positive
semidefinite symmetric matrix with $\|A_{p}\|\leqslant 1$. Consider a random
vector $\mathbf{y}_{p}$ defined as $\mathbf{x}_{p}$ in Definition 1.1 with
$X_{\alpha}$ replaced by
$Y_{\alpha}:=X_{\alpha}\mathbf{1}(dX_{\alpha}^{2}\leqslant n)$. As
$\\{\mathbf{x}_{p}^{\top}A_{p}\mathbf{x}_{p}\neq\mathbf{y}_{p}^{\top}A_{p}\mathbf{y}_{p}\\}\subseteq\bigcup_{\alpha=1}^{n}\\{dX_{\alpha}^{2}>n\\}$,
(3) yields that

${\mathbb{P}}(\mathbf{x}_{p}^{\top}A_{p}\mathbf{x}_{p}\neq\mathbf{y}_{p}^{\top}A_{p}\mathbf{y}_{p})\leqslant\sum_{\alpha=1}^{n}{\mathbb{P}}(dX_{\alpha}^{2}>n)\leqslant
n\max_{1\leqslant\alpha\leqslant
n}{\mathbb{E}}(dX_{\alpha}^{2}/n)\mathbf{1}(dX_{\alpha}^{2}>n)=:L_{n,d}\to 0.$

Thus, it sufficient to check (A) for $\mathbf{x}_{p}$ replaced by
$\mathbf{y}_{p}$. We will do it by showing that for $\mathbf{z}_{p}$ defined
as $\mathbf{x}_{p}$ in Definition 1.1 with $X_{\alpha}$ replaced by
$Z_{\alpha}:=Y_{\alpha}-{\mathbb{E}}Y_{\alpha}$, the following holds:

(a)
$(\mathbf{z}_{p}^{\top}A_{p}\mathbf{z}_{p}-\mathbf{y}_{p}^{\top}A_{p}\mathbf{y}_{p})/p\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}0$,

(b)
$(\mathbf{z}_{p}^{\top}A_{p}\mathbf{z}_{p}-{\mathbb{E}}\mathbf{z}_{p}^{\top}A_{p}\mathbf{z}_{p})/p\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}0$,

(c)
$({\mathbb{E}}\mathbf{z}_{p}^{\top}A_{p}\mathbf{z}_{p}-{\mathrm{tr}}(A_{p}))/p\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}0$.

Let us prove (a). Set $\mathbf{z}_{p,0}:=\mathbf{y}_{p}$ and define
$\mathbf{z}_{p,k}$, $k=1,\ldots,n,$ as $\mathbf{y}_{p}$ above with
$Y_{\alpha}$ replaced by $Z_{\alpha}$ for $\alpha=1,\ldots,k$. We have

${\mathbb{E}}|\mathbf{z}_{p}^{\top}A_{p}\mathbf{z}_{p}-\mathbf{y}_{p}^{\top}A_{p}\mathbf{y}_{p}|\leqslant{\mathbb{E}}|\mathbf{z}_{p,n}^{\top}A_{p}\mathbf{z}_{p,n}-\mathbf{z}_{p,0}^{\top}A_{p}\mathbf{z}_{p,0}|\leqslant\sum_{k=1}^{n}{\mathbb{E}}\Delta_{p,k},$

where
$\Delta_{p,k}:=|\mathbf{z}_{p,k}^{\top}A_{p}\mathbf{z}_{p,k}-\mathbf{z}_{p,k-1}^{\top}A_{p}\mathbf{z}_{p,k-1}|=|\|A_{p}^{1/2}\mathbf{z}_{p,k}\|^{2}-\|A_{p}^{1/2}\mathbf{z}_{p,k-1}\|^{2}|$.
To estimate ${\mathbb{E}}\Delta_{p,k}$ for any given $k$, we will use the
inequality

${\mathbb{E}}|\xi_{0}^{2}-\xi_{1}^{2}|\leqslant\sqrt{{\mathbb{E}}(\xi_{0}-\xi_{1})^{2}}\sqrt{{\mathbb{E}}(\xi_{0}+\xi_{1})^{2}}\leqslant
2\max_{q=0,1}\sqrt{{\mathbb{E}}\xi_{q}^{2}}\sqrt{{\mathbb{E}}(\xi_{0}-\xi_{1})^{2}}$

valid for any $\xi_{0},$ $\xi_{1}$ in $L_{2}$. Taking
$\xi_{q}=\|A_{p}^{1/2}\mathbf{z}_{p,k-q}\|$ and using that
$\|A_{p}^{1/2}\|=\sqrt{\|A_{p}\|}\leqslant 1$, we get
$|\xi_{0}-\xi_{1}|\leqslant\|A_{p}^{1/2}(\mathbf{z}_{p,k}-\mathbf{z}_{p,k-1})\|\leqslant\|\mathbf{z}_{p,k}-\mathbf{z}_{p,k-1}\|$
and
${\mathbb{E}}\xi_{q}^{2}\leqslant{\mathbb{E}}\|\mathbf{z}_{p,k-q}\|^{2}\leqslant
p$ as

${\mathbb{E}}Z_{\alpha}^{2}={\rm
Var}(Y_{\alpha})\leqslant{\mathbb{E}}Y_{\alpha}^{2}={\mathbb{E}}X_{\alpha}^{2}\mathbf{1}(dX_{\alpha}^{2}\leqslant
n)\leqslant{\mathbb{E}}X_{\alpha}^{2}=1.$ (5)

Thus, ${\mathbb{E}}\Delta_{p,k}\leqslant
2\sqrt{p}\sqrt{{\mathbb{E}}\|\mathbf{z}_{p,k}-\mathbf{z}_{p,k-1}\|^{2}}$. The
entries $\mathbf{z}_{p,k}-\mathbf{z}_{p,k-1}$ have the form

$\mathbf{1}(k\in i)\prod_{\alpha:\,\alpha\in
i,\,1\leqslant\alpha<k}Z_{\alpha}\cdot{\mathbb{E}}Y_{k}\cdot\prod_{\alpha:\,\alpha\in
i,\,k<\alpha\leqslant n}Y_{\alpha}$

for $i\in[n]_{d}$($=\\{j\subseteq\\{1,\ldots,n\\}:|i|=d\\}$), here
$\prod_{i\in\varnothing}=1$. By (5),

${\mathbb{E}}\|\mathbf{z}_{p,k}-\mathbf{z}_{p,k-1}\|^{2}\leqslant({\mathbb{E}}Y_{k})^{2}\sum_{i\in[n]_{d}:k\in
i}\mathbf{1}(k\in i)=({\mathbb{E}}Y_{k})^{2}\binom{n-1}{d-1}=$
$=({\mathbb{E}}Y_{k})^{2}\binom{n}{d}\frac{d}{n}=\frac{pd}{n}({\mathbb{E}}X_{k}\mathbf{1}(dX_{k}^{2}\leqslant
n))^{2}.$

It follows from ${\mathbb{E}}X_{k}=0$, that
${\mathbb{E}}X_{k}\mathbf{1}(dX_{k}^{2}\leqslant
n)=-{\mathbb{E}}X_{k}\mathbf{1}(dX_{k}^{2}>n)$ and

$|{\mathbb{E}}X_{k}\mathbf{1}(dX_{k}^{2}\leqslant
n)|\leqslant{\mathbb{E}}|X_{k}|\mathbf{1}(dX_{k}^{2}>n)\leqslant\sqrt{d/n}\,{\mathbb{E}}X_{k}^{2}\mathbf{1}(dX_{k}^{2}>n)$
(6)

Combining the above estimates yields

${\mathbb{E}}|\mathbf{z}_{p}^{\top}A_{p}\mathbf{z}_{p}-\mathbf{y}_{p}^{\top}A_{p}\mathbf{y}_{p}|\leqslant\sum_{k=1}^{n}{\mathbb{E}}\Delta_{p,k}\leqslant\frac{2pd}{n}\sum_{k=1}^{n}{\mathbb{E}}X_{k}^{2}\mathbf{1}(dX_{k}^{2}>n)\leqslant
2pL_{n,d}=o(p).$

This implies (a).

Let us prove (b). Applying Theorem 2.2 to $\bar{\mathbf{z}}_{p}$ defined as
$\mathbf{x}_{p}$ in Definition 1.1 with $X_{\alpha}$ replaced by
$Z_{\alpha}/\sqrt{{\mathbb{E}}Z_{\alpha}^{2}}$, we get

${\rm Var}(\mathbf{z}_{p}^{\top}A_{p}\mathbf{z}_{p})={\rm
Var}(\bar{\mathbf{z}}_{p}^{\top}D_{p}^{1/2}A_{p}D_{p}^{1/2}\bar{\mathbf{z}}_{p})\leqslant\frac{64K_{n}pd^{2}}{n}{\mathrm{tr}}((D_{p}^{1/2}A_{p}D_{p}^{1/2})^{2})\text{
if }2K_{n}d^{2}\leqslant n,$

where
$D_{p}:={\mathbb{E}}\mathbf{z}_{p}\mathbf{z}_{p}^{\top}\in{\mathbb{R}}^{p\times
p}$ is diagonal with diagonal entries $\prod_{\alpha\in
i}{\mathbb{E}}Z_{\alpha}^{2}$, $i\in[n]_{d}$, and

$K_{n}:=\max_{1\leqslant\alpha\leqslant
n}\frac{{\mathbb{E}}Z_{\alpha}^{4}}{({\mathbb{E}}Z_{\alpha}^{2})^{2}}\leqslant\frac{16\max\limits_{1\leqslant\alpha\leqslant
n}{\mathbb{E}}X_{\alpha}^{4}\mathbf{1}(dX_{\alpha}^{2}\leqslant
n)}{\min\limits_{1\leqslant\alpha\leqslant
n}({\mathbb{E}}Z_{\alpha}^{2})^{2}},$

here we have used that
${\mathbb{E}}Z_{\alpha}^{4}={\mathbb{E}}(Y_{\alpha}-{\mathbb{E}}Y_{\alpha})^{4}\leqslant
8({\mathbb{E}}Y_{\alpha}^{4}+({\mathbb{E}}Y_{\alpha})^{4})\leqslant
16{\mathbb{E}}Y_{\alpha}^{4}$. By (6) and $L_{n,d}=o(1)$, we have uniformly in
$\alpha$,

${\mathbb{E}}Y_{\alpha}={\mathbb{E}}X_{\alpha}\mathbf{1}(dX_{\alpha}^{2}\leqslant
n)=o((dn)^{-1/2}),$
${\mathbb{E}}Z_{\alpha}^{2}={\mathbb{E}}Y_{\alpha}^{2}-({\mathbb{E}}Y_{\alpha})^{2}=1-{\mathbb{E}}X_{\alpha}^{2}\mathbf{1}(dX_{\alpha}^{2}>n)+o((dn)^{-1/2})=1+o(d^{-1})$
(7)

As a result, by (3), $d^{2}K_{n}/n=o(1)/(1+o(d^{-1}))=o(1)$. In addition,

${\mathrm{tr}}((D_{p}^{1/2}A_{p}D_{p}^{1/2})^{2})\leqslant
p\|(D_{p}^{1/2}A_{p}D_{p}^{1/2})^{2}\|\leqslant
p\|A_{p}\|^{2}\|D_{p}^{1/2}\|^{4}\leqslant p\|D_{p}^{1/2}\|^{4}=$
$=p\max\limits_{i\in[n]_{d}}\Big{(}\prod_{\alpha\in
i}{\mathbb{E}}Z_{\alpha}^{2}\Big{)}^{2}\leqslant
p\Big{(}\max\limits_{1\leqslant\alpha\leqslant
n}{\mathbb{E}}Z_{\alpha}^{2}\Big{)}^{2d}=p(1+o(d^{-1}))^{4d}=p(1+o(1)).$

Finally, we conclude that $K_{n}d^{2}=o(n)$ and ${\rm
Var}(\mathbf{z}_{p}^{\top}A_{p}\mathbf{z}_{p})\leqslant p^{2}o(1)$, which
implies (b).

The relation (c) follows from the fact that

${\mathbb{E}}\mathbf{z}_{p}^{\top}A_{p}\mathbf{z}_{p}={\mathrm{tr}}(A_{p}D_{p})={\mathrm{tr}}(A_{p})+{\mathrm{tr}}(A_{p}(D_{p}-I_{p}))$

and ${\mathrm{tr}}(A_{p}(D_{p}-I_{p}))=o(p)$. Here the last equality could be
derived from Von Neumann’s trace inequality and (7) as follows,

$p^{-1}|{\mathrm{tr}}(A_{p}(D_{p}-I_{p}))|\leqslant\|A_{p}\|\|D_{p}-I_{p}\|\leqslant\|D_{p}-I_{p}\|=\max\limits_{i\in[n]_{d}}\Big{|}\prod_{\alpha\in
i}{\mathbb{E}}Z_{\alpha}^{2}-1\Big{|}\leqslant$
$\leqslant|\max\limits_{1\leqslant\alpha\leqslant
n}({\mathbb{E}}Z_{\alpha}^{2})^{d}-1|+|\min\limits_{1\leqslant\alpha\leqslant
n}({\mathbb{E}}Z_{\alpha}^{2})^{d}-1|=|(1+o(d^{-1}))^{d}-1|+|(1+o(d^{-1}))^{d}-1|=o(1).$

We have verified the sufficiency part of the theorem.

Let us prove the necessity part, i.e. (2)$\Rightarrow$(3). Let (2) holds and,
for each $d,n$, $X_{\alpha}=X_{\alpha}(d,n)$ are independent copies of $X$
with ${\mathbb{E}}X=0,$ ${\mathbb{E}}X^{2}=1>{\mathbb{P}}(X^{2}=1)$. So, by
Theorem 2.1, $\mathbf{x}_{p}^{\top}\mathbf{x}_{p}/p\to 1$ in probability.
Taking $Z=X^{2}$ in Theorem 2.3, we see that

$\mathbf{x}_{p}^{\top}\mathbf{x}_{p}/p$ and $S_{n}^{(d)}/\binom{n}{d}$ from
Theorem 2.3 have the same distribution.

As convergence in distribution to a constant implies convergence in
probability to the same constant, (i) in Theorem 2.3 holds. By
(i)$\Rightarrow$(iii) in Theorem 2.3, (3) holds. ∎

###### Proof of Theorem 2.4..

First, we will show that any of the conditions (i), (ii), (iii) implies that
$d^{2}=o(n)$. Indeed, if (iii) holds, then
${\mathbb{E}}Z\mathbf{1}(dZ\leqslant
n)=1-{\mathbb{E}}Z\mathbf{1}(dZ>n)=1-o(d^{-1})$ and
$d^{2}(1-o(1))=d^{2}({\mathbb{E}}Z\mathbf{1}(dZ\leqslant n))^{2}\leqslant
d^{2}{\mathbb{E}}Z^{2}\mathbf{1}(dZ\leqslant n)=o(n),$ hereinafter all limits
are with respect to $n\to\infty$. To prove that both (i) and (ii) imply
$d^{2}=o(n)$, we introduce one more condition:

(iv) ${\mathbb{P}}(d(S_{n}/n-1)<-\varepsilon)\to 0$ for all $\varepsilon>0$.
Obviously, (ii) $\Rightarrow$ (iv). Also, (i) $\Rightarrow$ (iv). Indeed, if
(i) holds, then

$d(S_{n}/n-1)\geqslant
d\ln\frac{S_{n}}{n}\geqslant\ln\frac{S_{n}^{(d)}}{\binom{n}{d}}=o_{\mathbb{P}}(1),$
(8)

where we have used Maclaurin’s inequality
$S_{n}/n\geqslant\big{(}S_{n}^{(d)}/\binom{n}{d}\big{)}^{1/d}$ (see (12.3) in
[25]).

Let us prove that (iv) $\Rightarrow$ $d^{2}=o(n)$. By Theorem 1 in [8] (or
Theorem 1.1 in [9]), ${\mathbb{P}}(S_{n}-n\leqslant 1)\geqslant 1/13$ for all
$n$. By standard inequalities for concentration functions (see Theorem 2.22 in
[24]), there exists $C>0$ such that ${\mathbb{P}}(1-\lambda\leqslant
S_{n}-n\leqslant 1)\leqslant C(\lambda+1)/\sqrt{n}$ for all $\lambda\geqslant
0$ and $n$. Taking $\lambda=\gamma\sqrt{n}+1$ for small enough $\gamma>0$, we
will guarantee that ${\mathbb{P}}(-\gamma\sqrt{n}\leqslant S_{n}-n\leqslant
1)\leqslant 1/26$ for all large enough $n$. As a result, we will get that
${\mathbb{P}}(S_{n}-n\leqslant-\gamma\sqrt{n})\geqslant 1/26+o(1)$. If (iv)
holds, then ${\mathbb{P}}(S_{n}-n\leqslant-\varepsilon n/d)\to 0$ for any
$\varepsilon>0$. The latter is possible only if, for any fixed
$\varepsilon>0$, $\varepsilon n/d>\gamma\sqrt{n}$ for all large enough $n$,
i.e. $n\geqslant n_{0}(\varepsilon)$. The latter means that $\sqrt{n}=o(n/d)$
or, equivalently, $d^{2}=o(n).$

Assume further that $d^{2}=o(n)$. Letting $b_{n}:=n/d$, we see that
$b_{n}\to\infty$ and $nb_{n}^{-2}\to 0$. By classical weak laws of large
numbers (see Theorem 2 in [13] with a discussion above it and page 317 in
[19]), $(S_{n}-n)/b_{n}=o_{\mathbb{P}}(1)$ if and only if

$n{\mathbb{P}}(|Z-1|>b_{n})+nb_{n}^{-2}{\mathbb{E}}(Z-1)^{2}\mathbf{1}(|Z-1|\leqslant
b_{n})+nb_{n}^{-1}|{\mathbb{E}}(Z-1)\mathbf{1}(|Z-1|\leqslant b_{n})|\to 0.$

The last condition could simplified as follows. As $Z\geqslant 0$ a.s. and
$b_{n}\to\infty$, then $Z>1$ when $|Z-1|>b_{n}$ for any large enough $n$. This
and ${\mathbb{E}}Z=1$ imply that (for large $n$)

$n{\mathbb{P}}(|Z-1|>b_{n})=n{\mathbb{P}}(Z-1>b_{n})\leqslant
nb_{n}^{-1}{\mathbb{E}}(Z-1)\mathbf{1}((Z-1)>b_{n})=$
$=-nb_{n}^{-1}{\mathbb{E}}(Z-1)\mathbf{1}((Z-1)\leqslant b_{n}).$

We also have that $nb_{n}^{-2}{\mathbb{E}}(Z-1)^{2}\mathbf{1}(|Z-1|\leqslant
b_{n},Z-1<0)\leqslant nb_{n}^{-2}=o(1).$ Therefore, the above results yield
that (ii) $\Leftrightarrow$ $n{\mathbb{E}}\phi((Z-1)/b_{n})\to 0$, where

$\phi(x)=\frac{x^{2}}{2}\mathbf{1}(x\in[0,1])+\Big{(}x-\frac{1}{2}\Big{)}\mathbf{1}(x>1),\quad
x\in{\mathbb{R}}.$

Using that $\phi$ is non-decreasing and convex, we derive

$0\leqslant{\mathbb{E}}\phi(Z/b_{n})-{\mathbb{E}}\phi((Z-1)/b_{n})\leqslant{\mathbb{E}}\phi^{\prime}(Z/b_{n})/b_{n}=$
$=b_{n}^{-2}{\mathbb{E}}Z\mathbf{1}(Z\leqslant
b_{n})+b_{n}^{-1}{\mathbb{P}}(Z>b_{n})\leqslant
2b_{n}^{-2}{\mathbb{E}}Z=2b_{n}^{-2}=o(n^{-1}).$

In addition, $\kappa(x)/2\leqslant\phi(x)\leqslant\kappa(x)$ for
$\kappa(x)=x^{2}\mathbf{1}(x\in[0,1])+x\mathbf{1}(x>1)$ and all
$x\in{\mathbb{R}}$. Thus, (ii) $\Leftrightarrow$
$n{\mathbb{E}}\phi((Z-1)/b_{n})\to 0$ $\Leftrightarrow$
$n{\mathbb{E}}\phi(Z/b_{n})\to 0\Leftrightarrow$ (iii).

Let us now show that (i) $\Leftrightarrow$ (ii). By the above arguments, we
could assume that $d^{2}=o(n).$ Also, suppose for a moment that $d\to\infty$.
Then, by Lemma 2.5, we have the representation (4). Denote further by
$\bar{\mathbb{E}}f(Z)$ the empirical mean $n^{-1}\sum_{k=1}^{n}f(Z_{k})$ for
any function $f$. Also, let
$\epsilon_{n},\varepsilon_{n},\delta_{n},\gamma_{n}$ be random sequences
tending to 0 in probability, not necessarily the same at each occurrence. As
shown in the proof of Lemma 2.5, $\rho
d/n\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}1.$ Using the well-known
inequalities $\ln(x)\leqslant x-1$ and $x\leqslant(x+1)\ln(x+1)\leqslant
x(2+x)/2$ valid for every $x\geqslant 0$, we see that by the definition of
$\rho$,

$\frac{d}{n}=\bar{\mathbb{E}}\frac{Z/\rho}{Z/\rho+1}\leqslant\bar{\mathbb{E}}\ln\Big{(}\frac{Z}{\rho}+1\Big{)}\leqslant\bar{\mathbb{E}}\frac{(Z/\rho)(2+Z/\rho)}{2(Z/\rho+1)}=\frac{d}{n}+\bar{\mathbb{E}}\frac{Z^{2}/(2\rho)}{Z+\rho}=\frac{d}{n}+\Big{(}\frac{1}{2}+\gamma_{n}\Big{)}\bar{\mathbb{E}}\frac{dZ^{2}}{Z+\rho}$

and

$d\ln\frac{\rho d}{n}=(1+\varepsilon_{n})d\Big{(}\frac{\rho
d}{n}-1\Big{)}=(1+\varepsilon_{n})\Big{(}d\bar{\mathbb{E}}\frac{Z\rho}{Z+\rho}-d\Big{)}=(1+\varepsilon_{n})\Big{(}d\Big{(}\frac{S_{n}}{n}-1\Big{)}-d\,\bar{\mathbb{E}}\frac{Z^{2}}{Z+\rho}\Big{)}.$

As a result, when $d\to\infty$, we get from Lemma 2.5 that for $n\geqslant 1,$

$(1+\varepsilon_{n})\Big{(}d(S_{n}/n-1)-d\bar{\mathbb{E}}\frac{Z^{2}}{Z+\rho}\Big{)}+\delta_{n}\leqslant\ln\frac{S_{n}^{(d)}}{\binom{n}{d}},$
(9)
$\ln\frac{S_{n}^{(d)}}{\binom{n}{d}}\leqslant(1+\varepsilon_{n})d(S_{n}/n-1)-(1/2+\epsilon_{n})d\bar{\mathbb{E}}\frac{Z^{2}}{Z+\rho}+\delta_{n}.$
(10)

Suppose (ii) holds and $d\to\infty$. Then (iii) holds and, by $\rho
d/n\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}1,$

$d\bar{\mathbb{E}}\frac{Z^{2}}{Z+\rho}\leqslant
d\bar{\mathbb{E}}ZI(dZ>n)+\frac{1}{\rho
d/n}\frac{d^{2}}{n}\bar{\mathbb{E}}Z^{2}I(dZ\leqslant
n)\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}0.$

Therefore, in view of (9) and (10), (i) holds.

Suppose (ii) holds and $d\not\to\infty$. We need the following elementary
fact:

if $\xi_{n}\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}0$, then there
exist (nonrandom) $\alpha_{n}\in{\mathbb{N}}$, $n\geqslant 1$, such that
$\alpha_{n}\to\infty$ and
$\alpha_{n}\xi_{n}\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}0$.

Therefore, by (ii), there exists $d_{*}=d_{*}(n)\in{\mathbb{N}}$ such that
$d(n)\leqslant d_{*}(n)$ for all $n$, $d=o(d_{*})$ (in particular,
$d_{*}\to\infty$), and (ii) holds for $d$ replaced by $d_{*}$. As shown above,
the latter implies that (i) holds for $d$ replaced by $d_{*}$. By Maclaurin’s
inequality (see (12.3) in [25]),

$\frac{S_{n}}{n}-1\geqslant\ln\frac{S_{n}}{n}\geqslant\frac{1}{d}\ln\frac{S_{n}^{(d)}}{\binom{n}{d}}\geqslant\frac{1}{d_{*}}\ln\frac{S_{n}^{(d_{*})}}{\binom{n}{d_{*}}},$

where $\ln 0=-\infty$. Combining the above relations yields (i) (for
$d=d(n)$).

Suppose (i) holds and $d\to\infty$. Then, noting that $(z+n/d)/(z+\rho)$
always lies between $1$ and $n/(\rho d)=1+o_{\mathbb{P}}(1)$ for $z\geqslant
0$, we get from (10) that

$d(S_{n}/n-1)-(1/2+\varepsilon_{n})\bar{\mathbb{E}}\frac{dZ^{2}}{Z+n/d}\geqslant\delta_{n}.$
(11)

It follows from (11) and
$\bar{\mathbb{E}}Z^{2}/(Z+n/d)\geqslant\bar{\mathbb{E}}ZI(dZ>n)/2+\bar{\mathbb{E}}Z^{2}I(dZ\leqslant
n)/(2n/d)$ that

$d(S_{n}/n-1)=d(\bar{\mathbb{E}}Z-{\mathbb{E}}Z)\geqslant(1/4+\epsilon_{n})\Big{(}d\bar{\mathbb{E}}Z\mathbf{1}(dZ>n)+\frac{d^{2}}{n}\,\bar{\mathbb{E}}Z^{2}\mathbf{1}(dZ\leqslant
n)\Big{)}+\delta_{n}.$ (12)

As ${\rm Var}((d^{2}/n)\bar{\mathbb{E}}Z^{2}\mathbf{1}(dZ\leqslant
n))\leqslant d^{2}(d/n)^{2}{\mathbb{E}}Z^{4}\mathbf{1}(dZ\leqslant
n)/n\leqslant(d^{2}/n){\mathbb{E}}Z^{2}\mathbf{1}(dZ\leqslant n)$, the
Chebyshev inequality yields

$d(S_{n}/n-1)\geqslant(1/4+\epsilon_{n})\frac{d^{2}}{n}\,{\mathbb{E}}Z^{2}\mathbf{1}(dZ\leqslant
n)+O_{\mathbb{P}}(1)\sqrt{\frac{d^{2}}{n}\,{\mathbb{E}}Z^{2}\mathbf{1}(dZ\leqslant
n)}+\delta_{n}.$

Let us show that $d^{2}{\mathbb{E}}Z^{2}\mathbf{1}(dZ\leqslant n)=O(n)$.
Suppose the contrary: for some $n_{k}\to\infty$ (as $k\to\infty$) and
$d_{k}=d(n_{k})$,
$(d_{k}^{2}/n_{k}){\mathbb{E}}Z^{2}\mathbf{1}(d_{k}Z\leqslant
n_{k})\to\infty$. If so, the right-hand side of the last inequality (with
$n_{k},d_{k}$ replacing $n,d$) goes to infinity in probability. But this is
impossible, because by Theorem 1 in [8],
${\mathbb{P}}(d_{k}(S_{n_{k}}/n_{k}-1)\leqslant
d_{k}/n_{k})={\mathbb{P}}(S_{n_{k}}\leqslant n_{k}+1)\geqslant 1/13$ for all
$k$. Thus, $d^{2}{\mathbb{E}}Z^{2}\mathbf{1}(dZ\leqslant n)=O(n)$.

The variables $d(\bar{\mathbb{E}}Z\mathbf{1}(dZ\leqslant
n)-{\mathbb{E}}Z\mathbf{1}(dZ\leqslant n))$ have uniformly bounded second
moments not exceeding $(d^{2}/n){\mathbb{E}}Z^{2}\mathbf{1}(dZ\leqslant n)$
and, hence, are bounded in probability. Therefore, (12) yields that

$(3/4-\epsilon_{n})d(\bar{\mathbb{E}}Z\mathbf{1}(dZ>n)-{\mathbb{E}}Z\mathbf{1}(dZ>n))\geqslant(1/4+\epsilon_{n})d{\mathbb{E}}Z\mathbf{1}(dZ>n)+O_{\mathbb{P}}(1).$
(13)

The latter proves that $d{\mathbb{E}}Z\mathbf{1}(dZ>n)=O(1)$. Indeed, suppose
the contrary: for some $n_{k}\to\infty$ and $d_{k}=d(n_{k})$,
$d_{k}{\mathbb{E}}Z\mathbf{1}(d_{k}Z>n_{k})\to\infty$. If so, the right-hand
side of (13) goes to infinity in probability. But this is impossible, as by
Theorem 1 in [8],
${\mathbb{P}}(d(\bar{\mathbb{E}}Z\mathbf{1}(dZ>n)-{\mathbb{E}}Z\mathbf{1}(dZ>n)))\leqslant(d/n){\mathbb{E}}Z\mathbf{1}(dZ>n))\geqslant
1/13$ and ${\mathbb{E}}Z\mathbf{1}(dZ>n)\leqslant{\mathbb{E}}Z=1$.

Let $\xi_{n}:=d(S_{n}/n-1)$,
$\eta_{n}:=d(\bar{\mathbb{E}}Z\mathbf{1}(dZ\leqslant
n)-{\mathbb{E}}Z\mathbf{1}(dZ\leqslant n))$, and
$\zeta_{n}:=d\bar{\mathbb{E}}Z\mathbf{1}(dZ>n)$. Obviously,
${\mathbb{E}}\xi_{n}={\mathbb{E}}\eta_{n}=0$,
$\xi_{n}=\eta_{n}+\zeta_{n}-{\mathbb{E}}\zeta_{n}$, and $\zeta_{n}\geqslant 0$
a.s. As we have argued above, ${\mathbb{P}}(\xi_{n}<-\varepsilon)\to 0$ for
all $\varepsilon>0$ and ${\mathbb{E}}\eta_{n}^{2},{\mathbb{E}}\zeta_{n}$ are
bounded by some constant $K>0.$ To prove (ii), we only need to show that
${\mathbb{P}}(\xi_{n}>\varepsilon)\to 0$ for all $\varepsilon>0$. The well-
known formula for the expectation
${\mathbb{E}}\xi_{n}=\int_{{\mathbb{R}}_{+}}{\mathbb{P}}(\xi_{n}>x)dx-\int_{{\mathbb{R}}_{+}}{\mathbb{P}}(\xi_{n}<-x)dx$
gives

$\int_{0}^{\infty}{\mathbb{P}}(\xi_{n}>x)dx=\int_{0}^{\infty}{\mathbb{P}}(\xi_{n}<-x)dx\leqslant\varepsilon+(M-\varepsilon){\mathbb{P}}(\xi_{n}<-\varepsilon)+\int_{M}^{\infty}{\mathbb{P}}(\xi_{n}<-x)dx$

for all $\varepsilon>0$ and $M\geqslant\varepsilon$. When $x>2K$, we have
${\mathbb{E}}\zeta_{n}-x/2<0$ and $\zeta_{n}-{\mathbb{E}}\zeta_{n}>-x/2$ a.s.,
therefore, for such $x$, $\xi_{n}<-x$ implies $\eta_{n}<-x/2$ and
${\mathbb{P}}(\xi_{n}<-x)\leqslant{\mathbb{P}}(\eta_{n}<-x/2)$. As a result,
taking $M=\max\\{2K,\varepsilon,4K/\varepsilon\\}$ and applying Chebyshev’s
inequality, we get

$\int_{0}^{\infty}{\mathbb{P}}(\xi_{n}>x)dx\leqslant\varepsilon+(M-\varepsilon){\mathbb{P}}(\xi_{n}<-\varepsilon)+\int_{M}^{\infty}\frac{4Kdx}{x^{2}}\leqslant
2\varepsilon+M{\mathbb{P}}(\xi_{n}<-\varepsilon).$

Therefore, for all $\varepsilon>0$,

$\varlimsup_{n\to\infty}\int_{0}^{\infty}{\mathbb{P}}(\xi_{n}>x)dx\leqslant
2\varepsilon.$

This is possible only if $\int_{0}^{\infty}{\mathbb{P}}(\xi_{n}>x)dx\to 0$.
Thus,
${\mathbb{P}}(\xi_{n}>\varepsilon)\leqslant\varepsilon^{-1}\int_{0}^{\infty}{\mathbb{P}}(\xi_{n}>x)dx\to
0$ for all $\varepsilon>0$. We have shown that (i)$\Rightarrow$(ii) when
$d\to\infty$.

Assume that (i) holds and $d\not\to\infty$. To prove (ii), suppose the
contrary: (ii) does not hold, i.e. there are $\varepsilon,\delta>0$ and
$(n_{k})_{k=1}^{\infty}$ such that
${\mathbb{P}}(|d_{k}(S_{n_{k}}/n_{k}-1)|>\varepsilon)\geqslant\delta$ for all
$k$ (here $d_{k}=d(n_{k})$) and $n_{k}\to\infty$ as $k\to\infty$. Such $d_{k}$
are unbounded over $k$ (if not, $d_{k}(S_{n_{k}}/n_{k}-1)\to 0$ a.s. and in
probability by the strong law of large numbers). As a result, there is a
subsequence $(n_{k_{l}})_{l=1}^{\infty}$ such that $d_{k_{l}}\to\infty$ and
$d_{k_{l}}(S_{n_{k_{l}}}/n_{k_{l}}-1)\not\to 0$ in probability as
$l\to\infty$. However, it is shown above that (i) and $d\to\infty$ imply (ii).
The same argument shows that the latter holds for the subsequence
$(n_{k_{l}})_{l=1}^{\infty}$ and $d_{k_{l}}=d(n_{k_{l}})$. We get the
contradiction. Thus, (i)$\Rightarrow$(ii). This finishes the proof of the
theorem. ∎

## Supplementary material

###### Proof of Lemma 2.5..

We will follow the proof of Theorem in [14]. For any $\rho>0$, we have

$2\pi S_{n}^{(d)}=\int_{-\pi}^{\pi}\sum_{k=0}^{n}S_{n}^{(k)}\frac{(\rho
e^{i\theta})^{n-k}}{(\rho
e^{i\theta})^{n-d}}d\theta=\int_{-\pi}^{\pi}\prod_{k=1}^{n}(Z_{k}+\rho
e^{i\theta})\frac{d\theta}{(\rho
e^{i\theta})^{n-d}}=\int_{-\pi}^{\pi}e^{u(\theta)}d\theta,$

where $S_{n}^{(0)}:=1$,
$u(\theta)=u(\theta,n,\rho,Z_{1},\ldots,Z_{n}):=n\bar{\mathbb{E}}\ln(Z+\rho
e^{i\theta})-(n-d)(\ln\rho+i\theta)$, and $\bar{\mathbb{E}}f(Z)$ denotes the
empirical mean $n^{-1}\sum_{k=1}^{n}f(Z_{k})$ for any function $f$. For such
$u$,

$u^{\prime}(0)=in\bar{\mathbb{E}}\frac{\rho}{Z+\rho}-i(n-d),\quad
u^{\prime\prime}(0)=-n\bar{\mathbb{E}}\frac{\rho}{Z+\rho}+n\bar{\mathbb{E}}\frac{\rho^{2}}{(Z+\rho)^{2}}=-n\bar{\mathbb{E}}\frac{\rho
Z}{(Z+\rho)^{2}},$
$|u^{\prime\prime\prime}(\theta)|=\Big{|}n\bar{\mathbb{E}}\frac{\rho Z(\rho
e^{i\theta}-Z)}{(Z+\rho e^{i\theta})^{3}}\Big{|}\leqslant
n\bar{\mathbb{E}}\frac{\rho Z}{(\rho\cos\theta+Z)^{2}}\leqslant
n\bar{\mathbb{E}}\frac{\rho Z}{(\rho/\sqrt{2}+Z)^{2}}\leqslant
2|u^{\prime\prime}(0)|$

for every $|\theta|\leqslant\pi/4$, where we have also used that $|\rho
e^{i\theta}-Z_{k}|\leqslant|\rho e^{i\theta}+Z_{k}|$ for such $\theta$.

Let $\rho=\rho(n,d,Z_{1},\ldots,Z_{n})>0$ solve $u^{\prime}(0)=0$, i.e.

$\bar{\mathbb{E}}\frac{\rho}{Z+\rho}=1-\frac{d}{n}\quad\text{or,
equivalently,}\quad\bar{\mathbb{E}}\frac{Z}{Z+\rho}=\frac{d}{n},$ (14)

if such solution exists and $\rho=1$ otherwise. By the weak law of large
numbers,

$\inf_{r>0}\bar{\mathbb{E}}\frac{r}{Z+r}=\bar{\mathbb{E}}\mathbf{1}(Z=0)\leqslant{\mathbb{P}}(Z=0)+\varepsilon<1-\frac{d}{n}<1=\sup_{r>0}\bar{\mathbb{E}}\frac{r}{Z+r}$

with probability $1-o(1)$ as $n\to\infty$, where
$\varepsilon={\mathbb{P}}(Z\neq 0)/2$. So, ${\mathbb{P}}(\rho\text{ satisfies
\eqref{eq:16}})\to 1$. We have ${\mathbb{P}}(\rho>c)\to 1$ for every $c>0,$
since with probability $1-o(1)$,

$\bar{\mathbb{E}}\frac{c}{Z+c}\leqslant{\mathbb{E}}\frac{c}{Z+c}+\varepsilon<1-\frac{d}{n}=\bar{\mathbb{E}}\frac{\rho}{Z+\rho}$

for $\varepsilon=(1-{\mathbb{E}}c/(Z+c))/2$. Moreover, $\rho
d/n\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}1$, as for all $c>0$ with
probability $1-o(1)$,

${\mathbb{E}}\frac{Zc}{Z+c}+o_{\mathbb{P}}(1)=\bar{\mathbb{E}}\frac{Zc}{Z+c}\leqslant\frac{\rho
d}{n}=\bar{\mathbb{E}}\frac{Z\rho}{Z+\rho}\leqslant\bar{\mathbb{E}}Z=1+o_{\mathbb{P}}(1)$

and, by the dominated convergence theorem, ${\mathbb{E}}(Zc)/(Z+c)\to 1$ as
$c\to\infty.$

As ${\mathbb{P}}(Z_{k}\geqslant 0)=1$ and the function $|Z_{k}+\rho
e^{i\theta}|=(\rho^{2}+Z^{2}+2\rho Z\cos\theta)^{1/2}$ is decreasing in
$|\theta|\in[0,\pi]$ for all $k$, then $|e^{u(\theta)}|$ is decreasing in
$|\theta|$ and

$\frac{1}{2\pi}\int_{\delta<|\theta|\leqslant\pi}|e^{u(\theta)}|d\theta\leqslant|e^{u(\delta)}|\quad\text{for
any $\delta>0$}.$

Assume further that $u^{\prime}(0)=0$ (this happens with probability $1-o(1)$,
as is shown above). By Taylor’s formula with the reminder in the integral form
for all $\delta\in[0,\pi/4]$,

$\big{|}e^{u(\delta)-(u(0)+u^{\prime\prime}(0)\delta^{2}/2)}\big{|}=\big{|}e^{v(\delta)\delta^{3}}\big{|}\leqslant
e^{|v(\delta)\delta^{3}|}\leqslant e^{-u^{\prime\prime}(0)\delta^{3}},$

where $v(\delta):=\int_{0}^{1}u^{\prime\prime\prime}(t\delta)(1-t)^{2}dt/2$
satisfies $|v(\delta)|\leqslant-u^{\prime\prime}(0)/2.$ Fix arbitrary
$\delta\in(0,\pi/4]$. We have
$|S_{n}^{(d)}-(2\pi)^{-1}\int_{-\delta}^{\delta}e^{u(\theta)}d\theta|\leqslant
e^{u(0)+u^{\prime\prime}(0)(\delta^{2}/2-\delta^{3})}$. Also, by Taylor’s
formula,

$\int_{-\delta}^{\delta}e^{u(\theta)}d\theta=e^{u(0)}\int_{-\delta}^{\delta}e^{u^{\prime\prime}(0)\theta^{2}/2+v(\theta)\theta^{3}}d\theta=\frac{e^{u(0)}}{U}\int_{-\delta
U}^{\delta U}e^{-z^{2}(1+r(z))/2}dz,$

where $U:=\sqrt{-u^{\prime\prime}(0)}$ and $r(z):=-2v(z/U)z/U^{3}$ satisfies
$|r(z)|\leqslant\delta$ for $z\in[-\delta U,\delta U]$.

Suppose for a moment that
$U\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}\infty$. Taking
$\delta=U^{-1/2}\wedge(1/2)$, we get that $|r(z)|<1/2$ and
$|e^{-z^{2}(1+r(z))/2}|=e^{-z^{2}/2}|e^{-z^{2}r(z)/2}|\leqslant
e^{-z^{2}/2}e^{|z^{2}r(z)|/2}\leqslant e^{-z^{2}/4}$ when $|z|\leqslant\delta
U$. Thus,

$\Big{|}\int_{|z|>\delta
U}e^{-z^{2}(1+r(z))/2}dz\Big{|}\leqslant\int_{|z|>\delta
U}e^{-z^{2}/4}dz=o(1)$

(here $\delta U\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}\infty$ by
the choice of $\delta$). In addition, using the inequality
$|e^{z}-1|\leqslant|z|e^{|z|},$ $z\in{\mathbb{C}}$, that follows from the
series expansion of $e^{z}$, we conclude that

$\Big{|}\int_{{\mathbb{R}}}(e^{-z^{2}(1+r(z))/2}-e^{-z^{2}/2})dz\Big{|}\leqslant\int_{{\mathbb{R}}}z^{2}|r(z)|e^{z^{2}(-1+|r(z)|)/2}dz\leqslant\delta\int_{{\mathbb{R}}}z^{2}e^{-z^{2}/4}dz\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}0$

because
$\delta=U^{-1/2}\wedge(1/2)\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}0$.
Combining the above bounds along with
$e^{-U^{2}(\delta^{2}/2-\delta^{3})}=o_{\mathbb{P}}(1)/U$, we see that if
$-u^{\prime\prime}(0)=U^{2}\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}\infty$,
then

$S_{n}^{(d)}=\frac{e^{u(0)}}{2\pi\sqrt{-u^{\prime\prime}(0)}}\int_{\mathbb{R}}e^{-z^{2}}dz(1+o_{\mathbb{P}}(1))=\frac{e^{u(0)}}{\sqrt{-2\pi
u^{\prime\prime}(0)}}(1+o_{\mathbb{P}}(1)).$

In addition, when $d^{2}=o(n)$, we have
$\binom{n}{d}=(1+o(1))n^{d}/d!=(1+o(1))(2\pi d)^{-1/2}(en)^{d}/d^{d}$ by the
Stirling formula. Thus, assuming
$-u^{\prime\prime}(0)\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}\infty,$
then we get the asymptotic formula

$\ln\frac{S_{n}^{(d)}}{\binom{n}{d}}-(u(0)-(\ln(-u^{\prime\prime}(0)/d))/2-d-d\ln(n/d))\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}0.$

To finish the proof, we will check that
$-u^{\prime\prime}(0)/d\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}1$
and, in particular,
$-u^{\prime\prime}(0)\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}\infty$.
Using Chebyshev’s sum inequality
$n\sum_{k=1}^{n}a_{k}b_{k}\leqslant\sum_{k=1}^{n}a_{k}\sum_{k=1}^{n}b_{k}$
that holds for every $a_{1}\leqslant\ldots\leqslant a_{n}$ and
$b_{1}\geqslant\ldots\geqslant b_{n}$, we conclude that with probability
$1-o(1)$,

$-u^{\prime\prime}(0)=n\bar{\mathbb{E}}\frac{Z}{Z+\rho}\frac{\rho}{Z+\rho}\leqslant
n\bar{\mathbb{E}}\frac{Z}{Z+\rho}\bar{\mathbb{E}}\frac{\rho}{Z+\rho}=n(d/n)(1-d/n)=d(1+o(1)).$

In addition, by the Cauchy-Schwartz inequality, with probability $1-o(1)$,

$-u^{\prime\prime}(0)=n\rho\bar{\mathbb{E}}\frac{Z}{(Z+\rho)^{2}}\geqslant\frac{n\rho}{\bar{\mathbb{E}}Z}\Big{(}\bar{\mathbb{E}}\frac{Z}{Z+\rho}\Big{)}^{2}=\frac{n(\rho
d/n)d/n}{{\mathbb{E}}Z+o_{\mathbb{P}}(1)}=d(1+o_{\mathbb{P}}(1))\to\infty$

(recall that ${\mathbb{E}}Z=1$ and $\rho
d/n\stackrel{{\scriptstyle\mathbb{P}}}{{\rightarrow}}1$). This finishes the
proof of the lemma. ∎

###### Proof of Lemma 3.1.

Setting $[n]_{d}:=\\{i\subseteq\\{1,\ldots,n\\}:|i|=d\\}$, fix arbitrary
$i_{0},j_{0}\subseteq[n]_{d}$ with $|i_{0}\cap j_{0}|=t$. By definition,
$\gamma(s,t)$ is the number of pairs $(k_{0},l_{0})$ such that
$k_{0},l_{0}\subseteq[n]_{d}$, $|k_{0}\cap l_{0}|=t$,
$|\Lambda_{3}(i_{0},j_{0},k_{0},l_{0})|/2+|\Lambda_{4}(i_{0},j_{0},k_{0},l_{0})|=s,$
and $|\Lambda_{1}(i_{0},j_{0},k_{0},l_{0})|=0$. Let us count such pairs.

Set further $(i,j,k,l,u,v)=(i_{0}\setminus j_{0},j_{0}\setminus
i_{0},k_{0}\setminus l_{0},l_{0}\setminus k_{0},i_{0}\cap j_{0},k_{0}\cap
l_{0})$. By definition,

$i,j,u$ are pairwise disjoint, $|i|=|j|=d-t$, and $|u|=t$ (the same for
$k,l,v$). (15)

Recall that $\Lambda_{c}(i_{0},j_{0},k_{0},l_{0}),$ $c=1,\ldots,4,$ contains
all $\alpha\in i_{0}\cup j_{0}\cup k_{0}\cup l_{0}$ that are covered by
exactly $c$ sets among $i_{0},j_{0},k_{0},l_{0}$. Therefore,

$|\Lambda_{1}|=0\quad\text{iff}\quad i\cup j\subseteq k\cup l\cup
v\quad\text{and}\quad k\cup l\subseteq i\cup j\cup u,$ $|\Lambda_{3}|=|((i\cup
j)\cap v)\cup(u\cap(k\cup l))|=|(i\cup j)\cap v|+|u\cap(k\cup
l)|,\quad|\Lambda_{4}|=|u\cap v|.$

Put $q:=|(i\cup j)\cap v|$ and $r:=|u\cap v|$. Let us show that it follows
from $|\Lambda_{1}|=0$ and $|i\cup j|=|k\cup l|$ that $|(i\cup j)\cap
v|=|u\cap(k\cup l)|=q$. The relation $i\cup j\subseteq k\cup l\cup v$ implies
that

$(i\cup j)\setminus v=(i\cup j)\setminus(u\cup v)\subseteq(k\cup l\cup
v)\setminus(u\cup v)=(k\cup l)\setminus u.$

Similarly, $k\cup l\subseteq i\cup j\cup u$ implies that $(k\cup l)\setminus
u\subseteq(i\cup j)\setminus v$. This proves that

$q=|(i\cup j)\cap v|=|i\cup j|-|(i\cup j)\setminus v|=|k\cup l|-|(k\cup
l)\setminus u|=|(k\cup l)\cap u|.$

Combining the above relations gives $|\Lambda_{3}|=2q$ and $s=q+r=|(i\cup
j)\cap v|+|u\cap v|=|(i\cup j\cup u)\cap v|\leqslant|v|=t.$ In particular,
this proves that $\gamma(s,t)=0$ when $s>t$.

Suppose $s\in\\{0,\ldots,t\\}$. For given $(i,j,u)$ satisfying (15) and
$r\leqslant s$, let us compute the number of triples $(k,l,v)$ satisfying (15)
and such that $|\Lambda_{1}|=0,$ $|\Lambda_{3}|=2(s-r)$, and
$|\Lambda_{4}|=|u\cap v|=r$, where $\Lambda_{c}=\Lambda_{c}(i\cup u,j\cup
u,k\cup v,l\cup v)$ for $c=1,3,4.$

The number of possible choices of $v\cap u$ is $\binom{t}{r},$ as $|u|=t$ and
$|u\cap v|=r$.

Given $v\cap u,$ the number of possible choices of $v\cap(i\cup j)$ is
$\binom{2(d-t)}{s-r},$ as $(i\cup j)\cap u=\varnothing$, $|i\cup j|=2(d-t),$
and $|v\cap(i\cup j)|=s-r$.

Given $v\cap(i\cup j\cup u),$ the number of possible choices of
$v\setminus(i\cup j\cup u)$ is $\binom{n-(2d-t)}{t-s},$ as $|i\cup j\cup
u|=2d-t$ and $|v\setminus(i\cup j\cup u)|=t-s$.

Given $v,$ the number of possible choices of $(k\cup l)\cap u$ is
$\binom{t-r}{s-r},$ as $(k\cup l)\cap u=(k\cup l)\cap(u\setminus v)$,
$|u\setminus v|=t-r$, and $|(k\cup l)\cap u|=s-r$.

Given $v$ and $(k\cup l)\cap u$, the number of possible choices of $(k,l)$ is
$\binom{2(d-t)}{d-t},$ as $k\cap l=\varnothing$ and, because of
$|\Lambda_{1}|=0$, $k$ and $l$ could be only composed from the elements of the
set $((i\cup j)\setminus v)\cup((k\cup l)\cap u)$, which has $2(d-t)$ elements
in total.

Combining the above bounds and varying $r$, we deduce that

$\gamma(s,t)=\sum_{r=0}^{s}\binom{t}{r}\binom{2(d-t)}{s-r}\binom{t-r}{s-r}\binom{n-2d+t}{t-s}\binom{2(d-t)}{d-t}\mathbf{1}(s\leqslant
t).$

As is well known, $\binom{2(d-t)}{m}\leqslant 2^{2(d-t)}$ for any $m.$ Also,
it follows from $s\leqslant t<d\leqslant n$ that

$\frac{\binom{n-2d+t}{t-s}}{\binom{n}{d}}=\frac{\frac{(n-2d+t)!}{(n-2d+s)!}}{\frac{(n-d+(t-s))!}{(n-d)!}}\frac{\frac{d!}{(t-s)!}}{\frac{n!}{(n-d+(t-s))!}}=\prod_{z=1}^{t-s}\frac{n-2d+s+z}{n-d+z}\prod_{m=0}^{d-(t-s)-1}\frac{d-m}{n-m}\leqslant$
$\leqslant\prod_{m=0}^{d-(t-s)-1}\frac{d-m}{n-m}=\Big{(}\frac{d}{n}\Big{)}^{d-(t-s)}\prod_{m=0}^{d-(t-s)-1}\frac{1-m/d}{1-m/n}\leqslant\Big{(}\frac{d}{n}\Big{)}^{d-(t-s)},$

where $\prod_{z=1}^{t-s}$ is equal to one if $t=s$. As a result, denoting
$2^{4(d-t)}\binom{n}{d}(d/n)^{d-(t-s)}\mathbf{1}(s\leqslant t)$ by $M$, we get
the desired bound

$\gamma(s,t)\leqslant
M\sum_{r=0}^{s}\binom{t}{r}\binom{t-r}{s-r}=M\binom{t}{s}\sum_{r=0}^{s}\binom{s}{r}=2^{s}\binom{t}{s}M.$

∎

## References

  * [1] Adamczak, R.: Logarithmic Sobolev inequalities and concentration of measure for convex functions and polynomial chaoses, _Bull. Pol. Acad. Sci. Math._ 53, (2005), 221–238. MR: 2163396
  * [2] Adamczak, R., and Latala, R.: Tail and moment estimates for chaoses generated by symmetric random variables with logarithmically concave tails, _Ann. Inst. Henri Poincaré Probab. Stat._ 48, (2012) 1103–1136. MR: 3052405
  * [3] Adamczak, R.: Some remarks on the Dozier–Silverstein theorem for random matrices with dependent entries. _Random Matrices: Theory and Applications_ 2, (2013), 1250017. MR: 3077829
  * [4] Bai, Z., and Zhou, W.: Large sample covariance matrices without independence structures in columns. _Stat. Sinica_ 18, (2008), 425-–442. MR: 2411613
  * [5] Bryson, J., Vershynin, R., and Zhao, H.: Marchenko–Pastur law with relaxed independence conditions. _Random Matrices: Theory and Applications_ , (2021), DOI: 10.1142/S2010326321500404.
  * [6] Dembczak-Kołodziejczyk, A., and Lytova, A.: On the empirical spectral distribution for certain models related to sample covariance matrices with different correlations. arXiv preprint, (2021), arXiv:2103.03204.
  * [7] van Es, A. J., and Helmers, R.: Elementary symmetric polynomials of increasing order. _Probab. Theory Related Fields_ 80, (1988), 21–35. MR: 0970469
  * [8] Feige, U.: On sums of independent random variables with unbounded variance and estimating the average degree in a graph. _SIAM Journal on Computing_ 35, (2006), 964–984. MR: 2203734
  * [9] Garnett, B.: Small deviations of sums of independent random variables. _J. Comb. Theory Ser. A._ 169, (2020), 105119. MR: 3981219
  * [10] Girko, V., and Gupta, A.K.: Asymptotic behavior of spectral function of empirical covariance matrices. _Random Oper. and Stoch. Eqs._ 2, (1994), 44–60. MR: 1276248
  * [11] Götze, F., Sambale, H., and Sinulis, A.: Concentration inequalities for polynomials in $\alpha$-sub-exponential random variables. _Electronic Journal of Probability_ 26, 1–22. MR: 4247973
  * [12] Guédon, O., Lytova, A., Pajor, A., and Pastur, L.: The central limit theorem for linear eigenvalue statistics of the sum of independent random matrices of rank one. _Spectral Theory and Differential Equations. Amer. Math. Soc. Transl. Ser_ 2, (2014), 145–164. MR: 3307778
  * [13] Hall, P.: On the rate of convergence in the weak law of large numbers. _Ann. Probab._ 10, (1982), 374–381. MR: 0647510
  * [14] Halász, G., and Szekely, G.J.: On the elementary symmetric polynomials of independent random variables. _Acta Math. Acad. Sci. H._ 28, (1976), 397–400. MR: 0423491
  * [15] El Karoui, N.: Concentration of measure and spectra of random matrices: Applications to correlation matrices, elliptical distributions and beyond. _Annals of Applied Probability_ 19, (2009), 2362–2405. MR: 2588248
  * [16] Latala, R.: Estimates of moments and tails of Gaussian chaoses. _Ann. Probab._ 34, (2006), 2315–2331. MR: 2294983
  * [17] Latala, R., and Lochowski, R.: Moment and tail estimates for multidimensional chaos generated by positive random variables with logarithmically concave tails. _Progress in Probability_ 56, (2003), 77–92. MR: 2073428
  * [18] Lehec J.: Moments of the Gaussian chaos. In _Seminaire de Probabilites XLIII_ , Springer, Berlin, (2011), 327–340. MR: 2790379
  * [19] Loeve, M.: Probability Theory. 3rd ed. Van Nostrand, Princeton, (1963). MR: 0203748
  * [20] Lytova, A.: Central limit theorem for linear eigenvalue statistics for a tensor product version of sample covariance matrices. _J. Theor. Probab._ 31, (2018), 1024–1057. MR: 3803923
  * [21] Major, P.: The limit behavior of elementary symmetric polynomials of i.i.d. random variables when their order tends to infinity. _Ann. Probab._ 27, (1999), 1980-2010. MR: 1742897
  * [22] Marcenko, V.A., and Pastur, L.A.: Distribution of eigenvalues in certain sets of random matrices. _Mat. Sb. (N.S.)_ 72, (1967), 507–536. MR: 0208649
  * [23] Pajor, A., and Pastur L.: On the limiting empirical measure of eigenvalues of the sum of rank one matrices with log-concave distribution. _Studia Math._ 195, (2009), 11–29. MR: 2539559
  * [24] Petrov, V.V.: _Limit theorems of probability theory._ Clarendon Press, Oxford, (1995). MR: 1353441
  * [25] Steele, J.M.: _The Cauchy-Schwarz master class. An introduction to the art of mathematical inequalities._ Cambridge University Press, Cambridge, (2004). MR: 2062704
  * [26] Szekely, G.J.: A limit theorem for elementary symmetric polynomials of independent random variables. _Z. Wahrsch. Verw. Gebiete_ 59, (1982), 355–359. MR: 0721631
  * [27] Vershynin, R.: Concentration inequalities for random tensors. Bernoulli, 26(4), (2020), 3139–3162. MR: 4140540
  * [28] Yaskov, P.: The universality principle for spectral distributions of sample covariance matrices, (2015), arXiv:1410.5190.
  * [29] Yaskov, P.: Variance inequalities for quadratic forms with applications. _Math. Methods Statist._ 24, (2015), 309–319. MR: 3437388
  * [30] Yaskov, P.: Necessary and sufficient conditions for the Marchenko-Pastur theorem. _Electron. Commun. Probab._ 21, Article no. 73, (2016), 1–8. MR: 3568347
  * [31] Yaskov, P.: LLN for quadratic forms of long memory time series and its applications in random matrix theory. _J. Theor. Probab._ 31, (2018), 2032–2055. MR: 3866606
  * [32] Yaskov, P.: Limiting spectral distribution for large sample covariance matrices with graph-dependent elements. arXiv preprint, (2021), arXiv:2105.09625.