# Sparse matrices:
convergence of the characteristic polynomial seen from infinity

Simon Coste

###### Abstract

We prove that the reverse characteristic polynomial $\det(I_{n}-zA_{n})$ of a
random $n\times n$ matrix $A_{n}$ with iid $\mathrm{Bernoulli}(d/n)$ entries
converges in distribution towards the random infinite product

$\prod_{\ell=1}^{\infty}(1-z^{\ell})^{Y_{\ell}}$

where $Y_{\ell}$ are independent $\mathrm{Poisson}(d^{\ell}/\ell)$ random
variables. We show that this random function is a Poisson analog of more
classical Gaussian objects such as the Gaussian holomorphic chaos. As a
byproduct, we obtain new simple proofs of previous results on the asymptotic
behaviour of extremal eigenvalues of sparse Erdős-Rényi digraphs: for every
$d>1$, the greatest eigenvalue of $A_{n}$ is close to $d$ and the second
greatest is smaller than $\sqrt{d}$, a Ramanujan-like property for irregular
digraphs. For $d<1$, the only non-zero eigenvalues of $A_{n}$ converge to a
Poisson multipoint process on the unit circle.

Our results also extend to the semi-sparse regime where $d$ is allowed to grow
to $\infty$ with $n$, slower than $n^{o(1)}$. We show that the reverse
characteristic polynomial converges towards a more classical object written in
terms of the exponential of a log-correlated real Gaussian field. In the semi-
sparse regime, the empirical spectral distribution of $A_{n}/\sqrt{d_{n}}$
converges to the circle distribution; as a consequence of our results, the
second eigenvalue sticks to the edge of the circle.

##  1 Introduction

Let $A_{n}$ be a square $n\times n$ matrix whose $n^{2}$ entries are
independent $\mathrm{Bernoulli}(d_{n}/n)$ random variables. This non-Hermitian
matrix arises, for example, as the adjacency matrix of a directed Erdős-Rényi
graph with mean in-degree and mean out-degree $d_{n}$. Its _empirical spectral
distribution_ is the atomic measure defined by

$\mu_{n}=\frac{1}{n}\sum_{i=1}^{n}\delta_{\lambda_{i}(A_{n})}$ (1.1)

where $|\lambda_{i}(A_{n})|\geqslant\dotsb\geqslant|\lambda_{n}(A_{n})|$ are
the complex eigenvalues of $A_{n}$ ordered by decreasing modulus. It is a
striking result that when $d_{n}\to\infty$, the random measure $\mu_{n}$
suitably rescaled converges towards the _circular law_ , a uniform
distribution on a disk ([BR+19, RT19]). This phenomenon cannot hold when
$d_{n}$ is bounded independently of $n$, because in this case, any potential
limit should have an atom at zero, as noted for example in [RT19]. In this
$d_{n}=O(1)$ regime called _sparse_ , the existence of a weak limit for (1.1)
is not known. If this limit exists, there are no conjectures on its shape.
This is in contrast with the same problem when $A_{n}$ is the adjacency matrix
of a random directed $d$-regular graph (when $d\geqslant 3$ is an integer);
there, the limiting distribution is conjectured to have a closed-form
expression, the oriented Kesten-McKay density. In the Erdős-Rényi model, there
are reasons to think that no closed-form expressions will exist; more
generally, the spectral behaviour of $A_{n}$ in the sparse regime is still
largely unknown and we refer to the physics-oriented survey [LMNR19] for
insights on spectra of sparse, non-Hermitian matrices. Recently, [BCN20]
showed that when $d_{n}=d$, all the eigenvalues of $A_{n}$ are asymptotically
close to the disk $D(0,\sqrt{d})$ except one which is close to $d$ — this is a
Ramanujan-like property for sparse digraphs. It notably implies the tightness
of the sequence of random measures $(\mu_{n})$, and the fact that all limit
points are supported in $D(0,\sqrt{d})$, but the existence of a _unique_ limit
point is not guaranteed.

In this paper, the main result is that when $d_{n}=d>0$, the sequence of
random polynomials

$q_{n}:z\mapsto\det(I_{n}-zA_{n})=\prod_{i=1}^{n}(1-z\lambda_{i}),$

restricted to the disk $D(0,d^{-1/2})$, weakly converges towards an explicit
random analytic function $F$. This is inspired by a recent advance in
[BCGZ20]. As a corollary, we draw a simple proof of the aforementioned result
from [BCN20]. The limiting function $F$ seems to be new; it is a Poisson
analog of the Gaussian holomorphic chaos [NPS20], and has connections with the
combinatorics of multiset-partitions. In this paper, we only sketch some of
its elementary properties, but a deeper study might be of independent
interest. Since this object arises as the limit of the polynomials $q_{n}$
which are themselves linked with the $\lambda_{i}$, a better understanding of
$F$ might be useful for understanding the asymptotic spectral properties of
$A_{n}$.

In the regime where $d_{n}\to\infty$ slower than $n^{o(1)}$, we prove a
similar result for the rescaled polynomials
$d_{n}^{-1/2}q_{n}(d_{n}^{-1/2}z)$. We show that when restricted to $D(0,1)$,
they converge towards $-z\sqrt{1-z^{2}}G(z)$, where $G$ is the exponential of
a log-correlated Gaussian field, and we draw consequences on the eigenvalues
of $A_{n}$ which show that the second eigenvalue of $A_{n}/\sqrt{d_{n}}$ is
close to $1$: it sticks to the edge of the circular law.

##  2 Results in the sparse regime

In all this section, we fix $d>0$ and we consider a random $n\times n$ matrix
$A_{n}$ whose $n^{2}$ entries are independent zero-one random variables with
$\mathrm{Bernoulli}(d/n)$ distribution.

###  2.1 Convergence of the secular polynomials and eigenvalue asymptotics

The main result of this paper is the convergence of the reverse characteristic
polynomial of $A_{n}$, which is defined as

$q_{n}(z)=\det(I-zA_{n}).$ (2.1)

This is a sequence of random polynomials. They can explicitly be written in
terms of the eigenvalues of $A_{n}$, namely
$q_{n}(z)=\prod_{i=1}^{n}(1-\lambda_{i}z)$, or alternatively they can be
expressed through their coefficients, that is:
$q_{n}(z)=1+\sum_{k=1}^{n}(-1)^{k}z^{k}\Delta_{k}(A)$, where

$\Delta_{k}(A)=\sum_{\begin{subarray}{c}I\subset[n]\\\
|I|=k\end{subarray}}\det((a_{i,j})_{i,j\in I}).$

These coefficients are known in the litterature under the name _secular
coefficients_ , see for instance [DG06] in the context of circular
$\beta$-ensembles, and sometimes we will refer to $q_{n}$ as the _secular
polynomials_. Since they are symmetric functions in the $\lambda_{i}$, they
can be expressed through Newton’s formulas as polynomials in the power sums
$\lambda_{1}^{k}+\dotsb+\lambda_{n}^{k}=\mathrm{tr}(A^{k})$: more precisely,
there is a polynomial $P_{k}$ with degree $k$ and real coefficients such that

$\Delta_{k}(A_{n})=(-1)^{k}\frac{P_{k}(\mathrm{tr}(A_{n}^{1}),\dotsc,\mathrm{tr}(A_{n}^{k}))}{k!},$

this will be recalled in Subsection 6.1. The traces of $A_{n}^{k}$ can be
studied using classical methods in combinatorics, and their limit is
identified by the following definition and the theorem after.

######  Definition 2.1.

Let $d>0$, and let $(Y_{\ell}:\ell\in\mathbb{N}^{*})$ be a family of
independent random variables, with $Y_{\ell}\sim\mathrm{Poi}(d^{\ell}/\ell)$.
We define a family of (non-independent) random variables by

$X_{k}:=\sum_{\ell|k}\ell Y_{\ell}\qquad\qquad(k\in\mathbb{N}^{*})$ (2.2)

where $a|b$ means that $b$ is a nonzero multiple of $a$.

######  Theorem 2.2 (trace asymptotics).

For every integer $k$, the following joint weak convergence holds:

$(\mathrm{tr}(A_{n}^{1}),\dotsc,\mathrm{tr}(A_{n}^{k}))\xrightarrow[n\to\infty]{\mathrm{law}}(X_{1},\dotsc,X_{k}).$
(2.3)

In particular, their joint convergence in distribution implies the convergence
in distribution of any polynomial in the $\mathrm{tr}(A_{n}^{k})$, and in
particular of the coefficients $\Delta_{k}(A_{n})$ towards
$(-1)^{k}P_{k}(X_{1},\dotsc,X_{k})/k!$, or equivalently, the finite-
dimensional convergence of $q_{n}$ towards the random analytic function

$F(z):=1+\sum_{k=1}^{\infty}(-1)^{k}P_{k}(X_{1},\dotsc,X_{k})\frac{z^{k}}{k!}.$
(2.4)

To upgrade this result to _functional_ weak convergence, we need to introduce
some tools. Let $\mathbb{H}_{r}$ the space of analytic functions on the open
disk $D(0,r)$, for $r>0$. This set is endowed with the topology of uniform
convergence on compact subsets, and with the corresponding Borel sigma-algebra
(all the technical details regarding random analytic functions will be
recalled in Section 5). The sum representation in (2.4) is not very
informative, and some effort will be deployed for getting more explicit
representations of $F$ in the next subsection, including infinite product
representations in terms of the $Y_{\ell}$. For the moment, we will only need
that

$\text{almost surely, }F\text{ is in }\mathbb{H}_{d^{-1/2}}.$ (2.5)

We can now state our main result, where for completeness all the definitions
are recalled.

######  Theorem 2.3 (weak convergence).

Let $d>0$ and let $A_{n}$ be a random $n\times n$ matrix whose $n^{2}$ entries
are independent Bernoulli random variables with parameter $d/n$, and let
$q_{n}(z)=\det(I_{n}-zA_{n})$. Then,

$q_{n}\xrightarrow[n\to\infty]{\mathrm{law}}F$ (2.6)

where the convergence is the weak convergence of probability measures on
$\mathbb{H}_{d^{-1/2}}$, and $F$ is the random element in
$\mathbb{H}_{d^{-1/2}}$ defined in (2.4).

Figure 1: An illustration of Theorem 2.3 when $d>1$. The color scheme used for
these domain colourings is depicted in the small inset of the right picture.
Left is the domain colouring of $z\mapsto\det(I-zA)$, where $A$ is an $n\times
n$ random matrix with independent entries equal to 1 with probability $d/n$
and 0 otherwise ($n=500$ and $d=2$). The inverse eigenvalues of $A$ are in
white and the two circles have radius $1/d$ and $1/\sqrt{d}$. Right is the
colouring of the random analytic function $F$ in (2.4). What we see inside
$D(0,1/\sqrt{d})$ in the left picture converges in distribution towards what
we see in the right picture.

###  2.2 Eigenvalue asymptotics

The zeros of analytic functions are continuous with respect to the uniform
convergence of compact sets (Hurwitz’s theorem). It is thus natural to study
the zeroes of $F$. We introduce a random multiset, or equivalently a Radon
measure with integer values. Let $\mathbb{U}_{\ell}$ be the set of $\ell$-th
roots of unity. If $A,B$ are two multisets, their multiset union is noted
$A\uplus B$; we note $A^{m}=A\uplus\dotsb\uplus A$ ($m$ times), which means
the multiset containing each element of $A$ exactly $m$ times.

######  Definition 2.4.

Let $(Y_{\ell}:\ell\geqslant 1)$ be the family of independent
$\mathrm{Poisson}(d^{\ell}/\ell)$ random variables in Definition 2.1. We set
$\mathcal{Z}_{d}(\ell)=\mathbb{U}_{\ell}^{Y_{\ell}}$, and

$\mathcal{Z}_{d}=\biguplus_{\ell\geqslant 1}\mathcal{Z}_{d}(\ell).$ (2.7)

In other words, each $\ell$-th root of unity is put in $\mathcal{Z}_{d}$ with
multiplicity $Y_{\ell}$. Note that the same root of unity can be added
multiple times: in fact, if $x=\mathrm{e}^{\frac{k2i\pi}{\ell}}$ with $k,\ell$
mutually primes, then $x$ is a primitive $\ell$-th root of unity, and the
total multiplicity of $x$ in $\mathcal{Z}_{d}$ will be

$M_{\ell}=\sum_{j=1}^{\infty}Y_{j\ell}.$

When $d<1$, this sum is almost surely finite, because
$\mathbf{E}[M_{\ell}]=\sum_{j=1}^{\infty}d^{j\ell}/(j\ell)<\infty$. When
$d=1$, we will see that this sum is also almost surely finite, even if
$\mathbf{E}[M_{\ell}]=\infty$. We can now describe the random multiset of
zeroes of $F$.

######  Proposition 2.5.

When $d>1$, the random analytic function $F$ has exactly one zero located at
$1/d$ and it is simple. When $d\leqslant 1$, the zeros of $F$ have the same
distribution as the random multiset described in Definition 2.4.

The proof is a straightforward consequence of the representations of $F$ given
in Theorem 2.7 below. Now, with this proposition and a simple probabilistic
analysis of the weak convergence on $\mathbb{H}_{d^{-1/2}}$ done in the
inspiring papers [BZ20, BCGZ20], we will almost effortlessly show the
following result which was already partially proved in [BCN20, CS21] using a
different, _ad hoc_ method.

######  Theorem 2.6.

Let $|\lambda_{1}|\geqslant\dotsb\geqslant|\lambda_{n}|$ be the eigenvalues of
the random matrix $A_{n}$ defined in the preceding theorem. If $d>1$, then for
any $\varepsilon>0$ the following holds:

$\displaystyle\lim_{n\to\infty}\mathbf{P}(|\lambda_{1}-d|>\varepsilon)=0$
$\displaystyle\lim_{n\to\infty}\mathbf{P}(|\lambda_{2}|>\sqrt{d}+\varepsilon)=0.$
(2.8)

If $d=1$, then

$\lim_{n\to\infty}\mathbf{P}(|\lambda_{1}|>1+\varepsilon)=0.$

Finally, if $d<1$, then the eigenvalues of $A_{n}$ are either zero or roots of
unity. The random multiset $\Phi_{n}$ of the non-zero eigenvalues of $A_{n}$
satisfies

$\Phi_{n}\xrightarrow[n\to\infty]{\mathrm{law}}\mathcal{Z}_{d}$ (2.9)

where $\mathcal{Z}_{d}$ is the random multiset of zeroes of $F$ and the
convergence is the vague convergence of Radon measures on $\mathbb{C}$.

In the case $d>1$, it is supposed that $|\lambda_{2}|$ actually converges in
probability towards $\sqrt{d}$, but to the knowledge of the author this has
not been proved yet; we refer to the related work section on this topic.

Figure 2: Complex eigenvalues of a realization $A_{n}$ for $n=2000$ and
different values of $d$. The circles have radii $\max\\{1,d\\}$.

Incidentally, when $d<1$ there is a positive probability that $A_{n}$ has no
non-zero eigenvalues, that is, $A_{n}$ is nilpotent. We will see in the proof
that this probability is asymptotically equal to $1-d$. As soon as $d\geqslant
1$, this is no longer the case and $A_{n}$ must have at least one non-zero
eigenvalue with probability going to $1$ as $n\to\infty$. Regarding the $d=1$
case, we could not extract further information from our proof, the only
conclusion we have is that all the eigenvalues asymptotically have modulus
smaller then $1+o_{\mathbf{P}}(1)$, but some numerical experiments tend to
show that there is a circle of eigenvalues with modulus _close_ to 1 (and not
_equal_ to $1$ as in the $d<1$ case), as well as other smaller non-zero
eigenvalues, see the middle picture in Figure 2.

###  2.3 The Poisson multiplicative function and its Secular Coefficients

We now study the random analytic function $F$. The results in this section
will notably imply (2.5) or Proposition 2.5, but they are also interesting on
their own.

The log-generating function of the random variables $X_{k}$ will play a
central role, as well as its centered version:

$\displaystyle f(z)=\sum_{k=1}^{\infty}X_{k}\frac{z^{k}}{k},$
$\displaystyle\mathscr{P}(z)=\sum_{n=1}^{\infty}(\tau_{k}-X_{k})\frac{z^{k}}{k}$
where $\displaystyle\tau_{k}=\mathbf{E}[X_{k}]=\sum_{\ell|k}d^{\ell}.$ (2.10)

######  Theorem 2.7 (limiting object).

Almost surely, for all $z$ inside the disk of convergence of $f$, we have

$F(z)=\mathrm{e}^{-f(z)}$ (2.11)

and

$\displaystyle F(z)=\prod_{\ell=1}^{\infty}(1-z^{\ell})^{Y_{\ell}}.$ (2.12)

We now turn to the radius of convergence of $f$ and $F$.

  1. (i)

If $d<1$, then the following alternative holds true. With probability $1-d$,
the function $f$ is identically zero. Or, with probability $d$, the radius of
convergence of $f$ is equal to 1. In both cases $F$ is a polynomial so its
radius of convergence is $\infty$.

  2. (ii)

If $d=1$, almost surely the radius of convergence of $f$ is 1 and $F$ is a
polynomial, so its radius of convergence is $\infty$.

  3. (iii)

If $d>1$, almost surely the radius of convergence of $f$ is $1/d$. The radius
of convergence of $\mathscr{P}$ is $d^{-1/2}$. For every $z\in D(0,d^{-1/2})$,

$F(z)=\mathrm{e}^{\mathscr{P}(z)}\times\prod_{\ell=1}^{\infty}(1-dz^{\ell})^{\frac{1}{\ell}}$
(2.13)

where the infinite product is uniformly convergent on compact subsets
$D(0,d^{-1/2})$, hence the radius of convergence of $F$ is $\geqslant
d^{-1/2}$.

There is not so much to say about $F$ when $d\leqslant 1$: the expression
(2.12) says that $F$ is a polynomial with roots located on the unit circle.
However, when $d>1$ the situation is richer. Let $c_{n}$ be the (random)
coefficients of $F=\mathrm{e}^{-f}$, so that
$F(z)=\sum_{n=0}^{\infty}c_{n}z^{n}$. The $c_{n}$ are also called the secular
coefficients of $F$; with the definition in (2.4) they are given by
$c_{n}=P_{k}(X_{1},\dotsc,X_{k})/k!$ but this expression will not be very
useful. The $c_{n}$ are random variables, and since $F$ is analytic inside
$D(0,1/\sqrt{d})$, Hadamard’s formula says that
$\limsup|c_{n}|^{1/n}\geqslant\sqrt{d}$ almost surely, and it is natural to
ask what happens at the border of this disk, a question similar to the
construction of the Gaussian Multiplicative Chaos on the circle, see [RV13]
for a survey (as a side note, we will also see that $f$ is itself a log-
correlated field).

######  Remark 2.8.

The preceding theorem does not prove that the radius of convergence of $F$ is
equal to $d^{-1/2}$, but only greater than $d^{-1/2}$. We strongly suppose
that it is indeed an equality.

Now, Cauchy’s formula says that for any $m\in\mathbb{Z}$ and $r<d^{-1/2}$,

$\frac{1}{2\pi}\int_{0}^{2\pi}F(r\mathrm{e}^{it})r^{-m}\mathrm{e}^{-imt}\mathrm{d}t=\begin{cases}c_{m}\text{
if }m\geqslant 0\\\ 0\text{ if }m<0.\end{cases}.$

Consequently, the limit

$\lim_{r\to
d^{-1/2}}\frac{1}{2\pi}\int_{0}^{2\pi}F(r\mathrm{e}^{it})\varphi(r\mathrm{e}^{it})\mathrm{d}t$

exists for every $\varphi(z)=\sum_{k=d_{1}}^{d_{2}}a_{k}z^{k}$ with
$d_{1},d_{2}\in\mathbb{Z}$, ie for trigonometric polynomial $\varphi$ on the
circle $\mathbb{T}_{d^{-1/2}}=\\{|z|=d^{-1/2}\\}$. This provides us with a
simple construction of $F$ extended to $\mathbb{T}_{d^{-1/2}}$: we see it as a
random distribution, that is, a continuous linear function on the set of
trigonometric polynomials on $\mathbb{T}_{d^{-1/2}}$.

######  Definition 2.9.

The Poisson Holomorphic Chaos of index $d>1$, noted $\mathrm{PHC}_{d}$, is the
random distribution on $\mathbb{T}_{d^{-1/2}}$ almost surely defined by

$(\mathrm{PHC}_{d},\varphi)=\lim_{r\to
d^{-1/2}}\frac{1}{2\pi}\int_{0}^{2\pi}F(r\mathrm{e}^{it})\varphi(r\mathrm{e}^{it})\mathrm{d}t.$
(2.14)

A distribution $D$ on $\mathbb{T}_{d^{-1/2}}$ is entirely characterized by its
Fourier coefficients $\hat{D}(m):=(D,e_{m})$ where
$e_{m}(t)=d^{-1/2}\mathrm{e}^{-imt}$. Consequently, we can define the
$s$-Sobolev norm ($s\in\mathbb{R}$) by

$\|D\|_{s}^{2}=\sum_{n\in\mathbb{Z}}(1+n^{2})^{s}|\hat{D}(n)|^{2}.$ (2.15)

A distribution is $s$-Sobolev when the sum above is finite. Since the Fourier
coefficients of the Poisson holomorphic chaos are given by
$\widehat{\mathrm{PHC}_{d}}(m)=d^{-m/2}c_{m}$ if $m\geqslant 0$ and $0$ if
$m<0$, the Sobolev norm is simply given by
$\sum_{m\in\mathbb{N}}(1+n^{2})^{s}d^{-n/2}|c_{n}|^{2}$.

######  Proposition 2.10.

Let $d>1$. Almost surely, the random distribution $\mathrm{PHC}_{d}$ is
$s$-Sobolev for every $s<-1/2$.

Future work will be devoted to a wider analysis of the Sobolev-regularity of
$F$. Studying the Sobolev norms of $F$ requires a good understanding of the
integrability properties of the secular coefficients $c_{n}$. We saw that
these coefficients are polynomials in the $X_{k}$ (hence of the $Y_{\ell}$),
but this expression is difficult to manipulate; however, we have access to
their moments by means of a combinatorial analysis. For every integer $k>0$,
we note $\mathrm{Odd}_{k}$ the set of nonempty subsets of
$[k]=\\{1,\dotsc,k\\}$ with an odd number of elements, and $\mathrm{Even}_{k}$
the set of nonempty subsets of $[k]=\\{1,\dotsc,k\\}$ with an even number of
elements.

######  Theorem 2.11.

For any $z_{1},\dotsc,z_{k}$, one one has

$\mathbf{E}[F(z_{1})\dotsb
F(z_{k})]=\frac{\prod_{S\in\mathrm{Odd}_{k}}(1-d\prod_{s\in
S}z_{s})}{\prod_{S\in{\mathrm{Even}}_{k}}(1-d\prod_{s\in S}z_{s})}.$ (2.16)

To give a few examples,

$\displaystyle\mathbf{E}[F(z)]=1-zd$
$\displaystyle\mathbf{E}[F(y)F(z)]=\frac{(1-dy)(1-dz)}{1-dyz}$
$\displaystyle\mathbf{E}[F(x)F(y)F(z)]=\frac{(1-dx)(1-dy)(1-dz)(1-dxyz)}{(1-dxy)(1-dxz)(1-dyz)}.$

In particular, we see the $c_{n}$ are centered random variables except $c_{0}$
and $c_{1}$, and the analytic series $(1-z)^{-1}=\sum z^{n}$ gives
$\mathbf{E}[|c_{n}|^{2}]=d^{n}(d+1)$ — in particular
$\mathbf{E}[|c_{n}|^{2}]=O(d^{n})$.

The formula given above is our analog of the generating-function formula for
the Gaussian Holomorphic Chaos in [NPS20]. Therein, the combinatorial
interpretation of the secular coefficients was easily linked with the
enumeration of magic squares. A similar simple interpretation of the
coefficients of (2.16) is not clear for the moment, but some thoughts are
gathered in Subsection 8.6 at page 8.6.

##  3 Results in the denser regime where $d_{n}\to\infty$

The primary interest of this paper was to study random zero-one matrices with
a constant mean degree $d_{n}=d>0$ not depending on $n$, a regime which is
more difficult than the ‘semi-sparse’ regime where $d_{n}$ is allowed to grow
to infinity. This is what we study now, and our results essentially have the
same flavour as [BCGZ20] in that the spectral limits of $A_{n}$ are Gaussian.
We emphasize that this method gives a unified point of view on the convergence
of the characteristic polynomial in _all regimes of $d$_, sparse or not. Our
results are stated and proved in the regime where $d$ goes to infinity but not
too fast; in fact, we will from now on suppose

$\displaystyle\lim_{n\to\infty}d_{n}=+\infty$ and
$\displaystyle\lim_{n\to\infty}\frac{\log(d_{n})}{\log(n)}=0.$ (H)

There is no doubt that the result will still hold for denser regimes such as
$d=n^{\alpha},\alpha<1$; we did not pursue this route further.

Our first result is on the identification of traces of $A_{n}/\sqrt{d_{n}}$
when $d_{n}\to\infty$; in the sparse regime, everything was essentially
Poisson; in this semi-sparse regime, everything is essentially Gaussian.

######  Theorem 3.1.

Let $(N_{k}:k\geqslant 1)$ be a family of iid standard real Gaussian random
variables. Then, under (H), for any $k$,

$\left(\frac{\mathrm{tr}(A)}{\sqrt{d_{n}}}-\sqrt{d_{n}},\dotsc,\frac{\mathrm{tr}(A^{k})}{\sqrt{d_{n}}^{k}}-\sqrt{d_{n}}^{k}\right)\xrightarrow[n\to\infty]{\mathrm{law}}(N_{1},\dotsc,\sqrt{k}N_{k})+(0,1,0,1,\dotsc,\mathbf{1}_{k\text{
is even}}).$ (3.1)

The proof is at Section 10. It is well known that if $Z_{\lambda}$ is a
$\mathrm{Poi}(\lambda)$ random variable, then
$\lambda^{-1/2}(Z_{\lambda}-\lambda)$ converges in distribution towards a
standard Gaussian. From this, it is almost immediate to see that if the
$X_{k}$ are the random variables arising in Definition 2.1 in the sparse
regime, then $d^{-1/2}(X_{1},\dotsc,X_{k})$ converges in distribution as
$d\to\infty$ to the RHS in (3.1).

We now define

$G(z)=\exp\left\\{\sum_{k=1}^{\infty}N_{k}\frac{z^{k}}{\sqrt{k}}\right\\}.$

It is easily seen that the analytic function inside the exponential, say
$g(z)$, almost surely has a radius of convergence equal to $1$, hence $G$ is
in $\mathbb{H}_{1}$ (analytic functions in $D(0,1)$). On a side note, it is
not difficult to check that if $g$ is a log-correlated Gaussian field, in that
$\mathrm{Cov}(g(z),g(w))=-\log(1-z\bar{w})$.

######  Theorem 3.2 (weak convergence).

Let $(d_{n})$ be a sequence satisfying (H) and let $A_{n}$ be a random
$n\times n$ matrix whose $n^{2}$ entries are independent Bernoulli random
variables with parameter $d_{n}/n$, and let
$q_{n}(z)=\det(I_{n}-zA_{n}/\sqrt{d_{n}})$. Then,

$\frac{q_{n}(z)}{\sqrt{d_{n}}}\xrightarrow[n\to\infty]{\mathrm{law}}-z\sqrt{1-z^{2}}G(z)$
(3.2)

weakly on $\mathbb{H}_{1}$.

We note that the limit in (3.2) is nearly the same as the one in [BCGZ20]. The
main difference is in the presence of this $z$ factor, and it is due to the
fact that the entries in our matrix are not centered. If we replaced $A$ with
$A-\mathbf{E}[A]$, this term would not be present.

We now give the analog of Theorem 2.6 in the $d_{n}\to\infty$ setting.

######  Theorem 3.3.

Let $|\lambda_{1}|\geqslant\dotsb\geqslant|\lambda_{n}|$ be the eigenvalues of
the random matrix $A_{n}$ defined in the preceding theorem, under hypothesis
(H). Then, $\lambda_{1}/\sqrt{d_{n}}\to\infty$ almost surely and for any
$\varepsilon>0$,

$\displaystyle\lim_{n\to\infty}\mathbf{P}(||\lambda_{2}/\sqrt{d_{n}}|-1|>\varepsilon)=0.$
(3.3)

In any regime where $d_{n}\to\infty$, the circle law was proved in [BR+19,
RT19]: the empirical spectral distribution of the $\lambda_{i}/\sqrt{d_{n}}$
converges weakly towards the uniform distribution on $D(0,1)$. The convergence
in (3.3) says that apart from the first eigenvalue, there are no outliers in
the spectrum, ie the second eigenvalue cannot wander away from the boundary of
the support $D(0,1)$ of the limiting distribution.

Since the circular distribution puts a strictly positive mass $c(\varepsilon)$
on any domain $\mathbb{C}\setminus D(0,1-\varepsilon)$, then by the
Portemanteau theorem, the fraction of eigenvalues of $A_{n}/\sqrt{d_{n}}$
which are bigger than $1-\varepsilon$ is asymptotically $\geqslant
c(\varepsilon)$, and in particular is strictly positive: not only is
$|\lambda_{2}/\sqrt{d_{n}}|$ greater than $1-\varepsilon$, but also a linearly
growing number of $|\lambda_{k}/\sqrt{d_{n}}|$.

Figure 3: Same plot as in Figure 1, but for $\det(I-zA/\sqrt{d_{n}})$; here we
took $n=2000$ and $d_{n}=100$. The function on the right is the phase portrait
of $z\mapsto-z\sqrt{1-z^{2}}G(z)$ as in Theorem 3.2.

### Plan of the paper

In Section 4, we give an overview of the origins of our method and various
related work. We mention a set of questions and possible extensions. Section 5
is a summary of classical notions on random analytic functions; the specific
properties of the Poisson multiplicative function which are stated in
Subsection 2.3 are proved in Section 8. The core results of the paper, namely
Theorem 2.3 and 2.6, are proved in Section 6 as consequences of Theorem 2.2,
which identifies the limits of the traces. This theorem is proved in Section
9. Section 10 deals with our results in the $d_{n}\to\infty$ regime.

##  4 Related work and comments

#### Convergence of the reverse characteristic polynomial.

Our work is inspired by the recent paper [BCGZ20]. There, the authors prove
the convergence of $\det(I_{n}-zX_{n}/\sqrt{n})$, where $X_{n}$ is a random
matrix whose entries are iid random variables, with mean 0 and variance 1, and
whose law does not depend on $n$; for instance, Ginibre matrices. The circular
law phenomenon holds for this model; that is, the empirical spectral
distribution of $X_{n}/\sqrt{n}$ converges weakly towards the uniform
distribution over $D(0,1)$. The goal of [BCGZ20] was to prove the ‘no outliers
phenomenon’: that the greatest eigenvalue of $X_{n}/\sqrt{n}$, noted
$\rho_{n}$, converges in probability towards 1, with no extra assumptions on
the moments of the entries of $X$. We refer to the introduction of [BCC+18]
and references therein for some history on this theorem. In our paper we
closely follow the method introduced in [BCGZ20]. This method is itself
inspired by [BZ20] and Appendix A therein. The crucial addition of [BCGZ20]
was a truncation procedure and the identification of a trace CLT, which
allowed to identify the limiting distribution. However, the model studied in
[BZ20] is completely different (perturbations of banded matrices).

#### Eigenvalue asymptotics for sparse matrices and trace methods.

Theorem 2.6 was already proved in [BCN20], following a long line of research
initiated in [Bor15, BLM15] and continued, for example, in [Cos21, BC19,
BDH20]. These papers reach results like (2.8) by using a very sophisticated
high-trace method, namely, they study the asymptotics of
$\mathrm{tr}(A^{k_{n}}_{n})$, with $k_{n}$ allowed to grow to $\infty$. This
technique dates back at least to [FK81]. In our method, (2.8) is a direct
consequence of Theorem 2.3, which is itself proved using the classical trace
method with $k$ fixed as in Theorem 2.2. It is considerably simpler. Trace
asymptotics are standard in random matrix theory, even for non-Hermitian
random matrices; however, we could not find Theorem 2.2 in the litterature and
to the knowledge of the authors, there are very few similar results for other
models of sparse matrices. The closest result can be seen in [DJPP13] (or in
its bipartite version [Zhu20]) for traces of non-backtracking matrices on
regular graphs: see the definition of $\mathrm{CNBW}^{\infty}_{k}$ at page 15
in [DJPP13].

#### Sparse models: extension to regular graphs.

Our paper only treats the case of Erdős-Rényi directed graphs, whose edges are
independent. The other main model for sparse non-Hermitian matrices is the
_random regular digraph model_ mentioned in the introduction. For an integer
$d\geqslant 3$, one samples $A$ uniformly from the set of adjacency matrices
of $d$-regular directed graphs. A statement similar to Theorem 2.6 for this
model was proven in [Cos21] using the high-trace method, but the method in our
paper should also provide a simpler proof. In fact, the limits of the traces
as in Theorem 2.2 is thought to be the same for random regular, with a similar
proof; but the main difficulty lies in the tension of the polynomials $q_{n}$,
where our method and Proposition 6.2 are not easily generalized.

Similarly, one can be interested in applying this model to random undirected
regular graphs. The asymptotics of the second eigenvalue, in this case, is
given by the Alon-Friedman theorem and the proofs relied on delicate subgraphs
asymptotics [Fri08], or the use of the non-backtracking matrix $B$, see
[Bor15]. The asymptotics of the traces of $B$ are known, see [DJPP13], but
here again the tension of the family of polynomials $\det(I-zB)$ on
$\mathbb{H}_{1/2\sqrt{d-1}}$ is not proved for the moment.

#### Sparse models: extensions to inhomogeneous graphs.

The inhomogeneous random digraph is defined as follows: instead of appearing
with probability $p=d/n$, an edge $(i,j)$ appears with probability $p_{i,j}$
depending on $i$ and $j$. When the mean matrix $P$ has low rank and has
delocalized entries, a theorem similar to Theorem 2.6 was proved in [CS21].
Since this model encompasses popular generative models in network science
(such as the directed Stochastic Block-Model, its weighted, labelled or
degree-corrected variants, or the rank-1 inhomogeneous random graph), our
method could provide an interesting alternative to [BLM15] and the high-trace
methods; however, as it is now our method cannot provide information on the
eigenvectors of $A_{n}$, and it could be interesting to see if any refinement
can achieve this.

#### Alon-Boppana for non-normal matrices.

In the theory of sparse non-Hermitian matrices, there is still a crucial lack
of lower bounds for the second eigenvalue. For instance, our result in Theorem
2.6 states that when $d>1$ the second eigenvalue of Erdős-Rényi graphs
satisfies $|\lambda_{2}|\leqslant\sqrt{d}+o_{\mathbf{P}}(1)$. However, the
matching lower bound, namely that
$|\lambda_{2}|\geqslant\sqrt{d}+o_{\mathbf{P}}(1)$, is only conjectured; in
fact, it is generally believed that for any fixed $k$,
$|\lambda_{k}|\geqslant\sqrt{d}+o_{\mathbf{P}}(1)$. We call this kind of upper
bounds ‘Alon-Boppana bounds’, in reference of the famous lower bound for
$\lambda_{2}$ in [Nil91] in the context of regular graphs. For Hermitian or
normal matrices, they are easily reachable thanks to the min-max
characterizations of eigenvalues, but this tool is not available for non-
normal matrices such as adjacency matrices of random digraphs. In many models
of sparse random matrices such as [CS21], Alon-Boppana bounds are conjectured,
but at the moment they are not proved.

One possible way to prove these bounds is to directly prove that the ESD of
$A$ converges towards a limiting measure supported in $D(0,\sqrt{d})$, but as
mentioned in the introduction this seems very difficult in sparse settings.

The method developed in [BR+19, BCGZ20] and this paper suggests another
strategy. The limiting function $F$ is conjectured to have a radius of
convergence of $1/\sqrt{d}$. If we had $\limsup|\lambda_{2}|<c$ for some
$c<\sqrt{d}$ on an event with positive probability, then on this event all the
roots of $q_{n}$ except $1/\lambda_{1}$ would be outside the circle of radius
$1/c$. It seems reasonnable to say that this should imply that the radius of
convergence of $F$ would then be greater than $1/c$ on this event, a
contradiction. We could not formalize this idea.

#### The Poisson analog of the GHC.

Exponentials of Gaussian fields have a very rich history, see the survey
[RV13]. Of special interest is the Gaussian holomorphic chaos, ie

$\displaystyle
C(z)=\exp\left(\sum_{k=0}^{\infty}N_{k}\frac{z^{k}}{\sqrt{k}}\right)$ (4.1)

where the $N_{k}$ are iid standard complex Gaussian variables. This random
analytic function on $D(0,1)$ was proved to be the limit of the secular
polynomials in the circular $\beta$-ensemble for $\beta=2$ in [DS94], and then
for every $\beta>0$ in [JM15]. This link between characteristic polynomials
and Gaussian functions was also central in a series of conjectures in [FK14]
and subsequent work. The remarkable paper [NPS20] thoroughly studies more
refined properties of the GHC linked with the circular ensembles; therein, the
very clear combinatorial interpretation of the moments of the GHC already seen
in [DG06] is proven by elementary means ( [NPS20, Theorem 1.6]). For the
moment, we could not reach such an elegant description for our Poisson analog,
see Theorem 2.7.

Subsequent work should be devoted to a less shallow study of the Poisson
multiplicative function $F$ and its extension to the circle
$\mathbb{T}_{d^{-1/2}}$ as in Definition (2.1). The following questions arise.

  1. 1.

We strongly suppose that the radius of convergence of $F$ is $d^{-1/2}$, we
did only prove that is it $\geqslant d^{-1/2}$.

  2. 2.

Proposition 2.10 only gives a tiny information on the regularity of
$\mathrm{PHC}$. Can we fully characterize the Sobolev regularity of this
object? As noted in Subsection 8.4, the answer could depend on the limit of
$\int|F(r\mathrm{e}^{it})|^{2}\mathrm{d}t$ — the total mass of a putative
random measure on $\\{|z|=d^{-1/2}\\}$ defined by $\lim_{r\to
d^{-1/2}}\mathrm{e}^{2\mathrm{Re}(f(r\mathrm{e}^{it}))}\mathrm{d}t$.

  3. 3.

Is there a simple combinatorial interpretation of the generating functions for
the moments of $\mathrm{PHC}_{d}$ in (2.16)?

  4. 4.

What can be said about the convergence of the secular coefficients
$\Delta_{k}(A_{n})$ when $k$ is allowed to go to infinity with $n$?

##  5 General facts about random analytic functions

In this section, we recall some basic facts on random analytic functions.

Let $\mathbb{H}_{r}$ be the set of analytic functions on the open disk
$D(0,r)$. A textbook treatment of the properties of $\mathbb{H}_{r}$ is in
[S+15, vol. 2a, ch. 6]. A classical consequence of Cauchy’s formula is that
the elements in $\mathbb{H}_{r}$ can be represented as power series

$\sum_{k=0}^{\infty}a_{k}z^{k}$ (5.1)

with $\limsup|a_{k}|^{1/k}\leqslant 1/r$ (Hadamard’s formula). The space
$\mathbb{H}_{r}$ is endowed with the compact-convergence topology: we say that
a sequence $f_{n}$ converges to $f$ if, for every compact set $K\subset
D(0,r)$,

$\|f_{n}-f\|_{K}=\sup_{z\in K}|f_{n}(z)-f(z)|\to 0.$

Endowed with this topology, $\mathscr{H}(D)$ is _topolish_ — it is separable,
complete and there is a metric distance generating the topology.

We now turn to random variables in $\mathbb{H}_{r}$. We endow this space with
the Borel sigma-algebra. Random variables in $\mathbb{H}_{r}$ are random
analytic functions; equivalently, they are series as in (5.1), where the
$a_{i}$ are random variables satisfying Hadamard’s limsup condition. The laws
of two random functions $\sum a_{k}z^{k}$ and $\sum b_{k}z^{k}$ are equal if
and only if the finite-dimensional distributions of $(a_{i})$ and $(b_{i})$
agree, that is, if
$(a_{0},\dotsc,a_{k})\stackrel{{\scriptstyle\text{law}}}{{=}}(b_{0},\dotsc,b_{k})$
for every $k$. The classical text on random analytic functions is [Kah93],
especially Chapter 3.

We endow the space of probability distributions on $\mathbb{H}_{r}$ with the
topology of weak convergence of measures, that is: the law of $f_{n}$
converges weakly towards the law of $f$ if and only if
$\mathbf{E}[\Phi(f_{n})]\to\mathbf{E}[\Phi(f)]$ for every continuous bounded
function $\Phi:\mathbb{H}_{r}\to[0,\infty[$. With a common abuse of language,
when we say that random variables converge in law, we mean that their
distributions converge in law as described above. The following theorem
summarizes the results in [Shi12]. See also [BCGZ20, Lemma 3.2].

######  Theorem 5.1.

Let $f,f_{1},f_{2},\dotsc$ be random variables in $\mathbb{H}_{r}$. Then,
$f_{n}$ converges weakly towards $f$ if and only if

  1. (i)

The sequence of random variables $\|f_{n}\|_{K_{i}}$ is tight for every $i$,
where $K_{i}$ is a sequence of compacts exhausting $D(0,r)$.

  2. (ii)

The finite-dimensional laws of $f_{n}$ converge in law towards those of $f$.

Proving the tightness of $\|f_{n}\|_{K}$ when $f_{n}$ is a random sequence of
analytic function can be simplified by the following device, a statement close
to [Shi12], Lemma 2.6 and the remark just after.

######  Lemma 5.2 (Hardy-type criterion).

Let $f_{n}(z)=\sum a_{n,k}z^{k}$ be a sequence of random analytic functions on
$D(0,r)$. If there is a sequence $(a_{k})$ such that
$\sup_{n}\mathbf{E}[|a_{n,k}|^{2}]\leqslant a_{k}$ for every $k$ and such that
$\limsup|a_{k}|^{1/2k}\leqslant 1/r$, then $(f_{n})$ is tight in
$\mathbb{H}_{r}$.

###### Proof.

Let $K\subset D(0,r)$ be a compact set and let $s<r$ be the radius of a disk
containing it. By Cauchy’s formula,

$\displaystyle|f_{n}(z)|^{2}=\left|\frac{1}{2i\pi}\int_{|z|=s}\frac{f_{n}(w)}{w-z}\mathrm{d}w\right|^{2}$
$\displaystyle=\frac{1}{(2\pi)^{2}}\left|\int_{0}^{2\pi}\frac{f_{n}(s\mathrm{e}^{it})si\mathrm{e}^{it}}{s\mathrm{e}^{it}-z}\mathrm{d}t\right|^{2}$
$\displaystyle\leqslant\frac{s^{2}}{2\pi\delta^{2}}\int_{0}^{2\pi}|f_{n}(s\mathrm{e}^{it})|^{2}dt$

where we used Cauchy-Schwarz’s inequality and we set $\delta=s-\max_{x\in
K}|x|>0$. Using Parseval’s formula, we obtain

$|f_{n}(z)|^{2}\leqslant\frac{s^{2}}{\delta^{2}}\sum_{k=0}^{\infty}|a_{n,k}|^{2}s^{2k}$

and this is valid for all $z\in K$. The expectation of the RHS is by
hypothesis smaller than $(s^{2}/\delta^{2})\sum_{k}a_{k}s^{2k}$, a continuous
function in $s\in[0,r)$ because we supposed that
$\limsup|a_{k}|^{1/2k}\leqslant 1/r$. Consequently, $\mathbf{E}[\sup_{z\in
K}|f_{n}(z)|^{2}]\leqslant c_{K}$ for some constant $c_{K}$ depending on $K$.
It readily implies the tightness of the sequence. ∎

######  Remark 5.3.

The $2$-Hardy norm on a disk $D(0,s)$ is
$\left(\sum|a_{k}|^{2}s^{2k}\right)^{1/2}$. The preceding statement says that
if $(f_{n})$ has a uniformly bounded $2$-Hardy norm in every $D(0,s)$ for
$s<r$ then the sequence is tight. This is slightly more specific than the
criterion in [Shi12], in which one directly proves that
$\mathbf{E}[|f_{n}(z)|^{2}]$ is bounded by a continuous function. The reason
why we do this is the following: if we directly want to study
$\mathbf{E}[|f_{n}(z)|^{2}]$, we obtain

$\mathbf{E}[|f_{n}(z)|^{2}]=\sum_{k,\ell}z^{k}\bar{z}^{\ell}\mathbf{E}[a_{n,k}\overline{a_{n,\ell}}]$

and often, the random variables $a_{n,\ell}$ and $a_{n,k}$ are independent or
decorrelated for $k\neq\ell$, as in [BCGZ20]. This will not the case for us,
see the examples in Subsection 6.3.

##  6 Proof of Theorem 2.3

###  6.1 Proof of the finite-dimensional convergence

To prove Theorem 2.3, namely that $q_{n}$ converges weakly towards $F$, we use
Theorem 5.1. The key for the finite-dimensional convergence is the
identification of the distributional limits of the traces of $A^{k}$ in
Theorem 2.2. Given this theorem which will be proved in Section 9, we can
classically link the traces of $A^{k}$ with the secular coefficients, the
coefficients of $\det(I-zA)$.

To do this we introduce a family of polynomials $P_{k}$, each $P_{k}$ having
$k$ variables. We note $\mathfrak{S}_{k}$ the group of permutations of $[k]$;
each permutation $\sigma$ can be uniquely written as a composition of $\ell$
cycles with disjoint support, say $\sigma=c_{1}\circ\dotsb\circ c_{\ell}$; the
length of a cycle $c$ is noted $|c|$. Then, we define $P_{k}$ as

$P_{k}(z_{1},\dotsc,z_{k})=\sum_{\begin{subarray}{c}\sigma\in\mathfrak{S}_{k}\end{subarray}}(-1)^{\ell}z_{|c_{1}|}\dots
z_{|c_{\ell}|}.$ (6.1)

######  Proposition 6.1.

For any $f(z)=\sum a_{n}z^{n}$ analytic in some disk $D(0,r)$,

$\mathrm{e}^{-\sum_{k=1}^{\infty}a_{k}\frac{z^{k}}{k}}=1+\sum_{k=1}^{\infty}P_{k}(a_{1},\dotsc,a_{k})\frac{z^{k}}{k!}.$
(6.2)

Moreover, for any $n\times n$ matrix $B$, for any $z$,

$\det(I-zB)=1+\sum_{k=1}^{n}P_{k}(\mathrm{tr}(B),\dotsc,\mathrm{tr}(B^{k}))\frac{z^{k}}{k!}.$
(6.3)

###### Proof.

Part (6.2) can be found in [Aig07, Corollary 3.6]. For the second statement,
we note $C(z)$ the matrix logarithm of $I-zB$, which exists if $|z|<1/\|B\|$
and is defined by

$C(z)=-\sum_{k=1}^{\infty}\frac{B^{k}}{k}z^{k}.$

Then
$\det(I-zB)=\det(\mathrm{e}^{C(z)})=\mathrm{e}^{\mathrm{tr}(C(z))}=\mathrm{e}^{-\sum_{1}^{\infty}\frac{\mathrm{tr}(A^{k})}{k}z^{k}}$.
This proves (6.3) (we can truncate the sum at $n$ since it is a polynomial of
degree $n$) for $|z|<1/\|B\|$, and it extends analytically for all $z$. ∎

The coefficients of $q_{n}$ are
$\Delta_{k}(A_{n})=P_{k}(\mathrm{tr}(A),\dotsc,\mathrm{tr}(A^{k}))/k!$ and
polynomials are continuous with respect to weak convergence, so Theorem 2.2
implies that

$(\Delta_{1}(A_{n}),\dotsc,\Delta_{k}(A_{n}))\xrightarrow{\mathrm{law}}(P_{1}(X_{1}),\dotsc,P_{k}(X_{1},\dotsc,X_{k})/k!).$

Thanks to (6.2) and the definition of $F$ in (2.4), this is exactly the
finite-dimensional convergence of $q_{n}$ towards $F=\mathrm{e}^{-f}$, ie the
second point in Theorem 5.1. To complete the proof, we need to check the first
point of this theorem.

###  6.2 Proof of the tightness

We now have to prove the first point on Theorem 5.1, that is, the tightness of
$(q_{n})$, and to do this we use the Hardy-type criterion in Lemma 5.2. We
recall that $q_{n}(z)=\det(I-zA)=1+\sum_{k=1}^{n}(-1)^{k}z^{k}\Delta_{k}(A)$
where the $\Delta_{k}(A)$ are the secular coefficients; from now on, we’ll
simply note them $\Delta_{k}$, and they are given by

$\Delta_{k}=\sum_{\begin{subarray}{c}I\subset[n]\\\
|I|=k\end{subarray}}\det(A(I))$ (6.4)

with $A(I)=(a_{i,j})_{i,j\in I}$. Our goal for Lemma 5.2 is to give an upper
bound for

$\displaystyle\mathbf{E}[|\Delta_{k}|^{2}]=\sum_{\begin{subarray}{c}|I|=k\\\
|J|=k\end{subarray}}\mathbf{E}[\det(A(I))\det(A(J))]$ (6.5)

which does not depend on $n$. For any finite set $E$, we note
$\mathfrak{S}(E)$ the group of its bijections and
$\varepsilon:\mathscr{S}(E)\to\\{-1,+1\\}$ the signature (the unique
nonconstant group morphism). If $I,J$ are fixed, then

$\mathbf{E}[\det(A(I))\det(A(J))]=\sum_{\begin{subarray}{c}\sigma\in\mathfrak{S}(I)\\\
\tau\in\mathfrak{S}(J)\end{subarray}}\varepsilon(\sigma)\varepsilon(\tau)\mathbf{E}\left[\prod_{\begin{subarray}{c}i\in
I\\\ j\in J\end{subarray}}a_{i,\sigma(i)}a_{j,\tau(j)}\right]$ (6.6)

and when the entries $a_{i,j}$ are centered and have a common variance, the
former expression is easy to study: if $I\neq J$, the expectation is the sum
is always zero by independence, so the whole expression is nonzero iff $I=J$
and the only nonzero contribution in the sum comes from $\sigma=\tau$. This is
the situation studied in [BZ20] or [BCN20]. It is not the case for us since we
deal with non-centered entries. For instance, let us take $n=2$, $I=\\{1\\}$
and $J=\\{1,2\\}$, so that

$\mathbf{E}[\det(A(I))\det(A(J))]=\mathbf{E}[a_{1,1}^{2}a_{2,2}-a_{1,1}a_{1,2}a_{2,1}].$

If the $a_{i,j}$ are standard real Gaussian random variables, this is zero.
But if they are $\mathrm{Ber}(p)$, this is $p^{2}-p^{3}$. Fortunately, the
computations are accessible.

######  Proposition 6.2.

Set $p=d/n$. With the preceding notations,

$\mathbf{E}[|\Delta_{k}|^{2}]=(n)_{k}p^{k}(1-p)^{k-1}(1-kp-p+nkp-k^{2}p).$
(6.7)

The proof will be in Section 6.3. We did not succeed in finding a simpler
proof. Now, since $p\leqslant 1$ and $kp\leqslant d$ for all $k\leqslant n$,
we can bound $\mathbf{E}[|\Delta_{k}|^{2}]$ by $a_{k}:=d^{k}(2+d+kd)$, which
does not depend on $n$; we also have

$\limsup|a_{k}|^{1/2k}=\sqrt{d}.$

Lemma 5.2 applies and shows that $(q_{n})$ is a tight sequence in
$\mathbb{H}_{d^{-1/2}}$.

###  6.3 Proof of Proposition 6.2

For any two nonempty subsets $I,J\subset[n]$, we will note

$\delta(I,J)=\mathbf{E}[\det(A(I))\det(A(J))].$ (6.8)

Proposition 6.2 is a direct consequence of the following theorem which could
be of independent interest.

######  Theorem 6.3.

If $I$ has $k$ elements and $J$ has $h$ elements (wlog, $k\leqslant h$), then
the followings holds for any matrix $A$ with independent $\mathrm{Ber}(p)$
entries.

  1. (i)

If $J\setminus I$ or $I\setminus J$ has more than two elements, then
$\delta(I,J)=0$.

  2. (ii)

If $I=J$, then

$\delta(I,J)=k!p^{k}(1-p)^{k-1}(1-p+kp).$ (6.9)

  3. (iii)

If $I\subset J$ and $J\setminus I$ has only one element, then
$\delta(I,J)=(k-1)!p^{k}(1-p)^{k-1}$.

  4. (iv)

If $|I|=|J|$ and if $|I\cap J|=k-1$, then $\delta(I,J)=k!p^{k+1}(1-p)^{k-1}$.

We now prove Proposition 6.2, and we will only need the cases (i), (ii), (iv)
— case (iii) is only included for completeness. We have

$\mathbf{E}[|\Delta_{k}|^{2}]=\sum_{\begin{subarray}{c}|I|=|J|=k\end{subarray}}\delta(I,J)$

and in this sum, the only non-zero contributions come from couples $I=J$ and
couples $I,J$ with $|I\cap J|=k-1$, so

$\displaystyle\mathbf{E}[|\Delta_{k}|^{2}]$
$\displaystyle=\sum_{\begin{subarray}{c}|I|=|J|=k\\\
I=J\end{subarray}}\delta(I,J)+\sum_{\begin{subarray}{c}|I|=|J|=k\\\ |I\cap
J|=k-1\end{subarray}}\delta(I,J)$
$\displaystyle=\binom{n}{k}k!p^{k}(1-p)^{k-1}(1-p+kp)+\binom{n}{k+1}(k+1)kk!p^{k+1}(1-p)^{k-1}$
$\displaystyle=(n)_{k}p^{k}(1-p)^{k-1}(1-p+kp)+(n)_{k+1}kp^{k+1}(1-p)^{k-1}$
$\displaystyle=(n)_{k}p^{k}(1-p)^{k-1}(1-kp-p+nkp-k^{2}p).$

Before jumping to the proof of Theorem 6.3, let us illustrate the $3\times 3$
case for which computations can be checked by hand.

######  Example 6.4.

We study

$A=\begin{pmatrix}a_{1,1}&a_{1,2}&a_{1,3}\\\ a_{2,1}&a_{2,2}&a_{2,3}\\\
a_{3,1}&a_{3,2}&a_{3,3}\end{pmatrix}.$

Case (i): let us take for instance $I=\\{1\\}$ and $J=\\{1,2,3\\}$, so

$\displaystyle\delta(I,J)$ $\displaystyle=\mathbf{E}[a_{1,1}\det(A)]$
$\displaystyle=\mathbf{E}[a_{1,1}(a_{1,1}a_{2,2}a_{3,3}+a_{1,2}a_{2,3}a_{3,1}+a_{1,3}a_{2,1}a_{3,2}-a_{1,1}a_{2,3}a_{3,2}-a_{1,2}a_{2,1}a_{3,3}-a_{1,3}a_{2,2}a_{3,1})]$
$\displaystyle=\mathbf{E}[a_{1,1}a_{2,2}a_{3,3}+a_{1,1}a_{1,2}a_{2,3}a_{3,1}+a_{1,1}a_{1,3}a_{2,1}a_{3,2}-a_{1,1}a_{2,3}a_{3,2}-a_{1,1}a_{1,2}a_{2,1}a_{3,3}-a_{1,1}a_{1,3}a_{2,2}a_{3,1}]$
$\displaystyle=p^{3}+p^{4}+p^{4}-p^{3}-p^{4}-p^{4}$ $\displaystyle=0.$

For case (ii) let us take $I=J=\\{1,2\\}$, so that

$\displaystyle\delta(I,J)$
$\displaystyle=\mathbf{E}[(a_{1,1}a_{2,2}-a_{1,2}a_{2,1})^{2}]$
$\displaystyle=\mathbf{E}[a_{1,1}a_{2,2}+a_{1,2}a_{2,1}-2a_{1,1}a_{2,2}a_{1,2}a_{2,1}]$
$\displaystyle=2p^{2}-2p^{4}.$

For case (iii) we take $I=\\{1,2\\}$ and $J=\\{1,2,3\\}$, we obtain

$\delta(I,J)=\mathbf{E}[(a_{1,1}a_{2,2}-a_{1,2}a_{2,1})\times\\\
(a_{1,1}a_{2,2}a_{3,3}+a_{1,2}a_{2,3}a_{3,1}+a_{1,3}a_{2,1}a_{3,2}-a_{1,1}a_{2,3}a_{3,2}-a_{1,2}a_{2,1}a_{3,3}-a_{1,3}a_{2,2}a_{3,1})]$

and this is equal to $2p^{5}-4p^{4}+2p^{3}$.

Finally for case (iv) we take $I=\\{1,2\\}$ and $J=\\{2,3\\}$ and we obtain

$\displaystyle\delta(I,J)$
$\displaystyle=\mathbf{E}[(a_{1,1}a_{2,2}-a_{1,2}a_{2,1})(a_{2,2}a_{3,3}-a_{2,3}a_{3,2})]$
$\displaystyle=\mathbf{E}[a_{1,1}a_{2,2}a_{3,3}-a_{1,1}a_{2,2}a_{2,3}a_{3,2}-a_{1,2}a_{2,1}a_{2,2}a_{3,3}+a_{2,1}a_{1,2}a_{2,3}a_{3,2}]$
$\displaystyle=2p^{3}-2p^{4}$

For the proof, we will settle some notations. We will denote $I\cap J=:K$.
Remember that $I$ has less elements than $J$; we can choose some fixed one-to-
one mapping $\alpha:I\to J$, and we choose it such that if fixes $K$, ie
$\alpha(i)=i$ for every $i\in K$. For any discrete set $D\subset[n]$, the set
of permutations of $D$ is noted $\mathfrak{S}(D)$. If
$\sigma\in\mathfrak{S}(I)$ and $\tau\in\mathfrak{S}(J)$, we introduce

$\displaystyle\mathrm{cp}_{K}(\sigma,\tau)=\\{i\in K:\sigma(i)=\tau(i)\\}$
$\displaystyle\mathrm{fp}_{K}(\sigma)=\\{i\in K:\sigma(i)=i\\}$

the sets of (respectively) _common points_ of $\sigma,\tau$ in $K$, and _fixed
points_ of $\sigma$ in $K$. We will need the following observation.

######  Lemma 6.5.

$|\mathrm{fp}_{K}(\tau\circ\alpha\circ\sigma^{-1})|=|\mathrm{cp}_{K}(\sigma,\tau)|$.

###### Proof.

For any $i\in K$, we note that if $\tau(i)=\sigma(i)$ then
$\tau\circ\alpha\circ\sigma^{-1}\circ\sigma(i)=\sigma(i)$ and vice-versa, so
$\sigma(i)$ is a fixed point of $\tau\circ\alpha\circ\sigma^{-1}$ in $K$ if
and only if $i$ is a common point of $\tau$ and $\sigma$ in $K$. ∎

###### Proof of the theorem.

By the definition of the determinant,

$\delta(I,J)=\mathbf{E}\left[\det(A(I))\det(A(J))\right]=\sum_{\begin{subarray}{c}\sigma\in\mathfrak{S}(I)\\\
\tau\in\mathfrak{S}(J)\end{subarray}}\varepsilon(\sigma)\varepsilon(\tau)\mathbf{E}\left[\prod_{i\in
I}a_{i,\sigma(i)}\prod_{j\in J}a_{j,\sigma(j)}\right].$ (6.10)

In (6.10), we note that for fixed $\sigma,\tau$, the expectation inside the
sums is equal to $p^{k+h-|\mathrm{cp}_{K}(\sigma,\tau)|}$. Since
$\varepsilon(\tau\circ\alpha\circ\sigma^{-1})=\varepsilon(\tau)\varepsilon(\sigma^{-1})=\varepsilon(\tau)\varepsilon(\sigma)$
and $\tau\to\tau\circ\alpha\circ\sigma^{-1}$ is a bijection of
$\mathfrak{S}(J)$, we obtain

$\displaystyle\mathbf{E}\left[\det(A(I))\det(A(J))\right]$
$\displaystyle=p^{k+h}\sum_{\sigma\in\mathfrak{S}(I)}\sum_{\tau\in\mathfrak{S}(J)}\varepsilon(\sigma)\varepsilon(\tau)p^{-|\mathrm{fp}_{K}(\tau\circ\alpha\circ\sigma^{-1})|}$
$\displaystyle=p^{k+h}\sum_{\sigma\in\mathfrak{S}(I)}\sum_{\tau\in\mathfrak{S}(J)}\varepsilon(\tau\circ\alpha\circ\sigma^{-1})p^{-|\mathrm{fp}_{K}(\tau\circ\alpha\circ\sigma^{-1})|}$
$\displaystyle=p^{k+h}\sum_{\sigma\in\mathfrak{S}(I)}\sum_{\tau\in\mathfrak{S}(J)}\varepsilon(\tau)p^{-|\mathrm{fp}_{K}(\tau)|}$
$\displaystyle=p^{k+h}h!\sum_{\tau\in\mathfrak{S}(J)}\varepsilon(\tau)p^{-|\mathrm{fp}_{K}(\tau)|}.$

Let $M=M_{J,K}(p)$ be the matrix whose rows and columns are indexed by $J$,
and with all entries equal to $1$ except the diagonal entries $m_{i,i}$ with
$i\in K$, which are equal to $p^{-1}$. Then,

$\sum_{\tau\in\mathfrak{S}(J)}\varepsilon(\tau)p^{-|\mathrm{fp}_{K}(\tau)|}=\det
M_{J,K}(p).$ (6.11)

Thanks to this representation we can finish the proof of the theorem, case by
case.

Case (i). Here, we immediately see that if $J\setminus K=J\setminus I$ has
more than 2 elements, then the matrix $M$ has two identical columns and its
determinant is zero.

To treat the other cases, we introduce some final notations. We note
$E_{\ell}$ the $\ell\times\ell$ matrix with ones everywhere, and we denote by
$\chi_{\ell}$ its characteristic polynomial $\chi_{\ell}(z)=\det(E_{\ell}-z)$.
Since the eigenvalues of $E_{\ell}$ are $\ell$ and $\ell-1$ zeroes, we have
$\chi_{\ell}(z)=(\ell-z)(-z)^{\ell-1}$. Finally, we set $w=1-p^{-1}$.

Case (ii). Here $I=J=K$, and by definition, (6.11) is nothing but the
characteristic polynomial of $E_{k}$ evaluated at $w$, so

$\delta(I,J)=p^{2k}k!\chi_{k}(w)=p^{2k}k!(k-1+p^{-1})(p^{-1}-1)^{k-1}$

which simplifies to the expression in the theorem.

Cases (iii-iv). Otherwise, $J\setminus K$ only has one element, say $i$;
without loss of generality we can suppose that $i$ is the last element in $J$,
so that we can do the following manipulations:

$\displaystyle\det\begin{bmatrix}p^{-1}&1&\dots&\dots&1\\\
1&p^{-1}&\ddots&&\vdots\\\ \vdots&\ddots&\ddots&\ddots&\vdots\\\
\vdots&\dots&\ddots&p^{-1}&1\\\ 1&\dots&\dots&1&1\end{bmatrix}$
$\displaystyle=\det\begin{bmatrix}p^{-1}&1&\dots&\dots&1\\\
1&p^{-1}&\ddots&&\vdots\\\ \vdots&\ddots&\ddots&\ddots&\vdots\\\
\vdots&\dots&\ddots&p^{-1}&1\\\ 1&\dots&\dots&1&p^{-1}+w\\\ \end{bmatrix}$
$\displaystyle=\det\begin{bmatrix}p^{-1}&1&\dots&\dots&1\\\
1&p^{-1}&\ddots&&\vdots\\\ \vdots&\ddots&\ddots&\ddots&\vdots\\\
\vdots&\dots&\ddots&p^{-1}&1\\\ 1&\dots&\dots&1&p^{-1}\\\
\end{bmatrix}+\det\begin{bmatrix}p^{-1}&1&\dots&1&0\\\
1&p^{-1}&\ddots&\vdots&\vdots\\\ \vdots&\ddots&\ddots&1&\vdots\\\
\vdots&\dots&\ddots&p^{-1}&0\\\ 1&\dots&\dots&1&w\\\ \end{bmatrix}$
$\displaystyle=\det\begin{bmatrix}p^{-1}&1&\dots&\dots&1\\\
1&p^{-1}&\ddots&&\vdots\\\ \vdots&\ddots&\ddots&\ddots&\vdots\\\
\vdots&\dots&\ddots&p^{-1}&1\\\ 1&\dots&\dots&1&p^{-1}\\\
\end{bmatrix}+(-1)^{i+i}w\det\begin{bmatrix}p^{-1}&1&\dots&1\\\
1&p^{-1}&\ddots&\vdots\\\ \vdots&\ddots&\ddots&1\\\ 1&\dots&1&p^{-1}\\\
\end{bmatrix}$

and this is equal to $\chi_{k}(w)+w\chi_{k-1}(w)=(-1)^{k-1}w^{k-1}$. Overall,
we obtain that in case (iii) where $k=h$, $\delta(I,J)=k!p^{k+1}(1-p)^{k-1}$,
and in case (iv) where $k=h+1$, $\delta(I,J)=(k-1)!p^{k}(1-p)^{k-1}$. ∎

##  7 Proof of Theorem 2.6

We identify multisets with integer-valued Radon measures as in [Shi12] and
endow the space of multisets with the topology of vague convergence, and the
space of random multisets with the topology of weak convergence with respect
to the vague topology.

######  Proposition 7.1.

Let $f_{n}$ be a sequence of random elements in $\mathbb{H}_{r}$ converging in
law towards $f$ which is supposed to be nonzero, and let $\Phi_{n},\Phi$ be
the random multisets of the zeroes of $f_{n},f$. Then, $\Phi_{n}$ converges in
law towards $\Phi$. Additionnaly, if $\Phi$ is almost surely equal to
$\\{\rho\\}$ for some deterministic $\rho\in D(0,r)$, then when $n$ is large
enough, $f_{n}$ has a unique zero $\rho_{n}$ in $D(0,r-\varepsilon)$, it is
simple, and $|\rho_{n}-\rho|<\varepsilon$.

###### Proof.

The first statement is exactly [Shi12], Proposition 2.3. For the second
statement we detail the proof: by Skorokhod’s representation theorem, on a
possibly enlarged probability space, we can find random analytic functions
$g,g_{1},g_{2},\dotsc$ such that $g$ has the same law as $f$ and $g_{n}$ has
the same law as $f_{n}$ for every $n$, and such that $g_{n}\to g$ in
$\mathbb{H}_{r}$ _almost surely_ on an event $\Omega_{0}$ with probability 1.
On $\Omega_{0}$, we can apply Hurwitz’s continuity theorem as in [S+15],
Theorem 6.4.1, cases (b)-(c): for every $\omega\in\Omega_{0}$, for every
$\varepsilon>0$, there is an $N_{\omega}$ such that $\forall n>N_{\omega}$,
the function $g_{n}$ has exactly one zero in $D(\rho,\varepsilon)$, and has no
other zeroes in $D(0,r-\varepsilon)$. ∎

###### Proof of Theorem 2.6.

The statements in Theorem 2.6 about the largest eigenvalues are direct
consequences of Propositions 2.5 and 7.1. Now, for the $d<1$ case, we must
additionnally prove that all the eigenvalues of $A$ have modulus exactly $1$
or $0$, which will entirely close the proof of the theorem.

Let $G$ be the digraph associated with $A$. We say that a directed graph is
strongly connected if for any two vertices $i,j$, there is a directed path
from $i$ to $j$ and a directed path from $j$ to $i$. Let $g_{1},\dotsc,g_{r}$
be the maximal strongly connected subgraphs (MSCS) of $G$ — we also say that
vertices with either no out-going edge or no in-going edge or both are MSCS of
their own (they only have one vertex), and we call them _trivial_. It is
always possible to label the $n$ vertices of $G$ so that $A$ is a block matrix
with diagonal blocks given by the adjacency matrices of the $g_{i}$, and
lower-diagonal blocks are only filled with zeroes. Consequently, the
eigenvalues of $A$ are the eigenvalues of all the $g_{i}$. The eigenvalues of
trivial MSCS are zero, so non-zero eigenvalues in the spectrum of $A$ must be
eigenvalues of non-trivial MSCS.

######  Lemma 7.2.

If $d<1$, with high probability, $G$ does not contain any non-trivial strongly
connected subgraph other than cycles.

###### Proof of the lemma.

The argument is similar to the one for undirected graphs, see [JLR11, Theorem
5.5]. The only strongly connected subgraphs with exactly as many edges as
vertices are the directed cycles. Now, if a strongly connected subgraph
contains strictly more edges than vertices, then it must contain a subgraph
which is either a directed cycle with an extra inner directed path, or two
directed cycles joined by a directed path. Essentially, these subgraphs look
like one of the following ones:

Let $D_{k}$ be the number of such digraphs with $k$ vertices and let $X_{k}$
be the number of subgraphs of $D_{k}$ which are present in $G$. We have

$\mathbf{E}[X_{k}]=\frac{(n)_{k}}{k!}\\#(D_{k})\left(\frac{d}{n}\right)^{k+1}$

and it is easily seen that $\\#(D_{k})\leqslant c(k-1)!k^{2}$ for some
constant $c$, so we have $\mathbf{E}[X_{k}]\leqslant ck^{2}d^{k+1}/nk\leqslant
ckd^{k}/n$. Consequently, noting $X=\sum_{k\geqslant 4}X_{k}$ and using $d<1$,
we obtain that $\mathbf{E}[X]=O(1/n)$ and Markov’s inequality ensures that
with high probability, $G$ does not contain any strongly connected subgraph
other than cycles or trivial subgraphs. ∎

The eigenvalues of $A$ are thus $0$ and eigenvalues of directed cycles, which
are roots of unity. In particular, all the eigenvalues of $A$ have modulus
zero or $1$ with probability going to $1$ as $n\to\infty$, which closes the
proof of the $d<1$ case in Theorem 2.6.

∎

##  8 Properties of the Poisson multiplicative function

###  8.1 Radii of convergence of $f$ and $\mathscr{P}$

The radius of convergence $r_{g}$ of a series $g(z)=\sum a_{k}z^{k}$ is given
by Hadamard’s formula, $r_{g}=(\limsup|a_{k}|^{\frac{1}{k}})^{-1}$. For the
statements in Theorem 2.7 related to radii of convergence of $f$ and
$\mathscr{P}$, we thus need to study $\limsup|X_{k}/k|^{1/k}$ and
$\limsup|(X_{k}-\tau_{k})/k|^{1/k}$. Since $k^{1/k}\to 1$, it will be enough
to study $\limsup X_{k}^{1/k}$ and $\limsup|X_{k}-\tau_{k}|^{1/k}$. We begin
with two useful lemmas.

######  Lemma 8.1.

Almost surely, there is an integer $\ell_{0}$ such that for every
$\ell\geqslant\ell_{0}$,

$\left|Y_{\ell}-\frac{d^{\ell}}{\ell}\right|\leqslant
2\ln(\ell)\sqrt{\frac{d^{\ell}}{\ell}}.$ (8.1)

###### Proof.

The Chernoff bound for Poisson variables (see [BLM13] section 2.2) can be
written as follows: if $Z\sim\mathrm{Poi}(\lambda)$, then

$\mathbf{P}(|Z-\lambda|\geqslant t)\leqslant\exp\left\\{-\lambda
h\left(\frac{t}{\lambda}\right)\right\\}+\exp\left\\{-\lambda
h\left(-\frac{t}{\lambda}\right)\right\\}$ (8.2)

where $h(x)=(1+x)\ln(1+x)-x$. Let us apply this to our family of Poisson
random variables $Y_{\ell}\sim\mathrm{Poi}(\lambda_{\ell})$, where
$\lambda_{\ell}=d^{\ell}/\ell$. We set
$t_{\ell}=2\ln(\ell)\sqrt{\lambda_{\ell}}$; the right-hand side of (8.2) is
then $O(\ell^{-2})$, and in particular it is summable. The Borel-Cantelli
lemma ensures the result. ∎

######  Lemma 8.2.

If $d>1$, $\tau_{k}=d^{k}(1+o(1))$ and almost surely there is a constant $c$
such that for all $k$,

$\left|X_{k}-\tau_{k}\right|\leqslant ck^{2}d^{k/2}.$ (8.3)

###### Proof.

The statement on $\tau_{k}$ is trivial. For the other one, note that

$\left|X_{k}-\sum_{\ell|k}d^{\ell}\right|\leqslant\sum_{\ell=1}^{k}\ell\left|Y_{\ell}-\frac{d^{\ell}}{\ell}\right|.$

Statement (8.1) shows that almost surely, $|Y_{\ell}-d^{\ell}/\ell|$ is
smaller than $2\ln(\ell)\sqrt{d^{\ell}/\ell}$ for $\ell\geqslant\ell_{0}$, and
this is again smaller than $2\ln(k)\sqrt{d^{k}/k}$, so

$\left|X_{k}-\tau_{k}\right|\leqslant\sum_{\ell=1}^{\ell_{0}}\ell\left|Y_{\ell}-\frac{d^{\ell}}{\ell}\right|+2k^{2}\ln(k)\sqrt{\frac{d^{k}}{k}}.$
(8.4)

If we note $c^{\prime}$ the first term, the LHS is smaller than
$(c^{\prime}+1)\times 2k^{2}d^{k/2}$, a crude bound but which is largely
enough for our needs. ∎

From this, we can easily deal with the convergence properties of $f$ and
$\mathscr{P}$ stated in Theorem 2.7.

  * •

If $d<1$, the upper bound in (8.1) goes to $0$ with $\ell$, and in particular
if $\ell$ is large enough, it is strictly smaler than $1/2$. Since
$d^{\ell}/\ell$ is also smaller than $1/2$ when $\ell>1$, we see that the
integer $Y_{\ell}$ must be strictly smaller than 1, therefore it is zero:
almost surely, only a finite number of $Y_{\ell}$ can be nonzero. As a
consequence, the random variables $X_{k}$ are almost surely bounded, and
$\limsup X_{k}^{1/k}\leqslant 1$. If at least one of the $Y_{\ell}$ is
nonzero, then there is a subsequence $k_{j}$ such that $X_{k_{j}}\geqslant 1$,
and consequently $\limsup X_{k}^{1/k}=1$. But it is not always the case. In
fact, the probability that _all_ the $Y_{\ell}$ are equal to zero is precisely
$\prod_{\ell=1}^{\infty}\mathrm{e}^{-d^{\ell}/\ell}=\mathrm{e}^{\log(1-d)}=1-d$.

  * •

If $d=1$, similar arguments as before apply with the difference that the
probability of all the $Y_{\ell}$ are equal to zero is zero.

  * •

If $d>1$, we can apply Lemma 8.2 and we easily obtain that
$X_{k}=\tau_{k}(1+o(1))$, so clearly $\limsup X_{k}^{1/k}=d$. We also check
that the radius of convergence of $\mathscr{P}$ is greater than $1/\sqrt{d}$.
For this, we only need to prove that

$\limsup|X_{k}-\tau_{k}|^{1/k}\leqslant\sqrt{d}.$ (8.5)

But this is a straightforward consequence of the inequality
$|X_{k}-\tau^{k}|\leqslant 2ck^{2}\sqrt{d}^{k}$ from the lemma.

###  8.2 Infinite product representations

We now prove (2.11), (2.12) and (2.13). In all the sequel, $\log$ will refer
to the principal branch of the complex logarithm, the one defined on
$\mathbb{C}\setminus\mathbb{R}_{-}$. We first see that for every $z$ in the
disk of convergence of $f$, which in any case is contained in $D(0,1)$, so

$\displaystyle f(z)=\sum_{k,\ell=1}^{\infty}\ell
Y_{\ell}\frac{z^{k}}{k}\mathbf{1}_{\ell|k}$
$\displaystyle=\sum_{\ell=1}^{\infty}Y_{\ell}\sum_{j=1}^{\infty}\frac{(z^{\ell})^{j}}{j}$
$\displaystyle=-\sum_{\ell=1}^{\infty}Y_{\ell}\log(1-z^{\ell}).$

The series inversions performed in these equalities are justified by the
uniform convergence of $f$ on compact subsets of the disk of convergence of
$f$, but they do not necessarily hold outside. As a consequence,
$\mathrm{e}^{-f}$ is itself well-defined on this disk, analytic, and

$\mathrm{e}^{-f(z)}=\lim_{N\to\infty}e^{\sum_{\ell=1}^{N}Y_{\ell}\log(1-z^{\ell})}=\lim_{N\to\infty}\prod_{\ell=1}^{N}(1-z^{\ell})^{Y_{\ell}}=\eqref{def:F}.$

As a first consequence, we see that when $d\leqslant 1$, since only a finite
number of $Y_{\ell}$ are nonzero, then $F=\mathrm{e}^{-f}$ is actually a
polynomial. Now, we introduce $L(z)=\mathbf{E}[f(z)]$, which can be written as

$\sum_{k=1}^{\infty}\sum_{\ell|k}d^{\ell}\frac{z^{k}}{k}.$

This is almost a Lambert function, but the presence of a $k$ in the
denominator actually makes it closer to a ‘log-Lambert’ function. Since the
series above is uniformly convergent on compact subsets of $D(0,1/d)$, we can
reorder like we just did for $f$, but in a slightly different way:

$\displaystyle L(z)$
$\displaystyle=\sum_{\ell=1}^{\infty}\sum_{j=1}^{\infty}d^{\ell}\frac{z^{j\ell}}{j\ell}$
$\displaystyle=\sum_{\ell=1}^{\infty}\sum_{j=1}^{\infty}\frac{(dz^{j})^{\ell}}{j\ell}$
$\displaystyle=\sum_{j=1}^{\infty}\frac{1}{j}\sum_{\ell=1}^{\infty}\frac{(dz^{j})^{\ell}}{\ell}$
$\displaystyle=-\sum_{j=1}^{\infty}\frac{\log(1-dz^{j})}{j}.$ (8.6)

By definition, $-f(z)=\mathscr{P}(z)-L(z)$, so the formula (2.13) in Theorem
2.7 is a consequence of the following proposition, whose main point is to
extend the convergence of the preceding sum (minus the first term) to
$D(0,1/\sqrt{d})$.

######  Proposition 8.3.

If $d>1$, then for every $|z|<1/d$,

$\mathrm{e}^{-L(z)}=\prod_{\ell=1}^{\infty}\sqrt[\ell]{1-dz^{\ell}}$

and the infinite product is uniformly convergent on compact subsets of
$D(0,1/\sqrt{d})$.

###### Proof.

The fact that this identity holds for $|z|<1/d$ follows from (8.6), since

$\displaystyle\exp(-L(z))$
$\displaystyle=\exp\left(\lim_{J\to\infty}\sum_{j=1}^{J}j^{-1}\log(1-dz^{j})\right)$
$\displaystyle=\lim_{J\to\infty}\exp\left(\sum_{j=1}^{J}j^{-1}\log(1-dz^{j})\right)$
$\displaystyle=\lim_{J\to\infty}(1-dz)\sqrt[2]{1-dz^{2}}\sqrt[3]{1-dz^{3}}\dotsb\sqrt[J]{1-dz^{J}}$
$\displaystyle=\prod_{\ell=1}^{\infty}\sqrt[\ell]{1-dz^{\ell}}.$

To upgrade this convergence in $D(0,1/d)$ to uniform convergence on
$D(0,1/\sqrt{d})$, we note that

$\prod_{\ell=1}^{\infty}\sqrt[\ell]{1-dz^{\ell}}=(1-dz)\mathrm{e}^{\sum_{j=2}^{\infty}j^{-1}\log(1-dz^{j})}$

so it is sufficient to prove that the series of logs started at $j=2$ is
uniformly convergent on compact subsets of $D(0,1/\sqrt{d})$. This is done by
noting that if $K$ is a compact in $D(0,s)$ for some $s<1/\sqrt{d}$, then for
$z\in K$ one has $|dz^{j}|<ds^{2}<1$. Note $r=ds^{2}<1$. There is a constant
$c_{r}$ such that for every $|z|<r$ one has $|\log(1+z)|<c_{r}|z|$, and
consequently $\sum_{j=2}^{\infty}|j^{-1}\log(1-dz^{j})|\leqslant c_{r}d\sum
j^{-1}r^{j}$ so uniform convergence on $K$ follows. ∎

######  Remark 8.4.

By the same argument one can extend the uniform convergence of the infinite
product to the set of $z\in D(0,1)$ such that for every $j\geqslant 2$,
$dz^{j}\notin\mathbb{R}_{-}$ since we use the principal logarithm. This set
can be described as $D(0,1)$ deprived of every segment semi-infinite line
$\\{td^{-1/j}\theta_{j}:t\geqslant 1\\}$ where $\theta_{j}$ is a $j$-th root
of unity and $j$ spans $\\{2,3,\dotsc\\}$.

###  8.3 Secular moments and generating function

In the representation

$\displaystyle F(z)=\mathrm{e}^{-f(z)}$
$\displaystyle=\prod_{\ell=1}^{\infty}(1-z^{\ell})^{Y_{\ell}},$

the product is uniformly convergent on compact subsets of the disk of
convergence of $f$. We now seek the secular coefficients, ie the coefficient
of $z^{n}$ in this series, noted $c_{n}=[z^{n}]F(z)$. Clearly,
$c_{n_{1}}\dotsb c_{n_{r}}=[z_{1}^{n_{1}}\dotsb z_{r}^{n_{r}}]F(z_{1})\dotsb
F(z_{r})$. We note $F(\bm{z})=F(z_{1})\dotsb F(z_{r})$. Our goal is to express
this as simply as possible to extract the coefficients. We have

$F(\bm{z})=\prod_{\ell=1}^{\infty}\left(\prod_{s=1}^{r}(1-z_{s}^{\ell})\right)^{Y_{\ell}}.$

We recall that if $X\sim\mathrm{Poi}(\lambda)$, then
$\mathbf{E}[z^{X}]=\mathrm{e}^{\lambda(z-1)}$. By independence,

$\displaystyle\mathbf{E}[F(\bm{z})]$
$\displaystyle=\prod_{\ell=1}^{\infty}\mathbf{E}\left[\left(\prod_{s=1}^{r}(1-z_{s}^{\ell})\right)^{Y_{\ell}}\right]$
$\displaystyle=\prod_{\ell=1}^{\infty}\mathrm{e}^{\frac{d^{\ell}}{\ell}[\prod_{s=1}^{r}(1-z_{s}^{\ell})-1]}$
$\displaystyle=\exp\left\\{\sum_{\ell=1}^{\infty}\frac{d^{\ell}}{\ell}\left(\prod_{s=1}^{r}(1-z_{s}^{\ell})-1\right)\right\\}.$

With the convention that a product over an empty set is equal to $1$, we have

$\prod_{s=1}^{r}(1-z_{s}^{\ell})=\sum_{S\subset[r]}(-1)^{|S|}\prod_{s\in
S}z_{s}^{\ell}=\sum_{S\subset[r]}(-1)^{|S|}\left(\prod_{s\in
S}z_{s}\right)^{\ell}$

and consequently the sum inside the integral is equal to

$\displaystyle\sum_{\ell=1}^{\infty}\frac{d^{\ell}}{\ell}\left(\prod_{s=1}^{r}(1-z_{s}^{\ell})-1\right)$
$\displaystyle=\sum_{S\subset[r],S\neq\varnothing}(-1)^{|S|}\sum_{\ell=1}^{\infty}\frac{\left(d\prod_{s\in
S}z_{s}\right)^{\ell}}{\ell}$
$\displaystyle=\sum_{S\subset[r],S\neq\varnothing}(-1)^{|S|-1}\log\left(1-d\prod_{s\in
S}z_{s}\right)$
$\displaystyle=\sum_{S\in\mathrm{Odd}_{r}}\log\left(1-d\prod_{s\in
S}z_{s}\right)-\sum_{S\in\mathrm{Even}_{r}}\log\left(1-d\prod_{s\in
S}z_{s}\right)$

where $\mathrm{Odd}_{r},\mathrm{Even}_{r}$ denote the sets of nonempty subsets
of $[r]$ with an odd number of elements or with an even number of elements. We
obtain

$\mathbf{E}[f(\bm{z})]=\frac{\prod_{S\in\mathrm{Odd}_{r}}(1-d\prod_{s\in
S}z_{s})}{\prod_{S\in\mathrm{Even}_{r}}(1-d\prod_{s\in S}z_{s})}$ (8.7)

which is Theorem 2.16. We gather some remarks on the combinatorics of set-
partitions of multisets in Subsection 8.6.

When $r=1$, there is only one nonempty subset of $\\{1\\}$, so

$\mathbf{E}F(z)=1-zd.$ (8.8)

Equivalently, $\mathbf{E}[c_{0}]=1,\mathbf{E}[c_{1}]=-d$ and
$\mathbf{E}[c_{k}]=0$ for $k>1$. When $r=2$, the formula says that

$\mathbf{E}[F(z)F(w)]=\frac{(1-zd)(1-wd)}{(1-zwd)}.$ (8.9)

This is also equal to $\sum_{k=0}^{\infty}d^{k}z^{k}w^{k}(1-zd-wd+d^{2}zw)$,
so

$\mathbf{E}[c_{n}^{2}]=d^{n}+d^{n+1}.$ (8.10)

###  8.4 Sobolev regularity

Remember that the Sobolev norm was defined in (2.15) as

$\|F\|_{s}^{2}=\sum_{n\in\mathbb{Z}}(1+n^{2})^{s}\frac{|c_{n}|^{2}}{d^{n}}.$

Since $F$ is analytic, the sum only spans $n\geqslant 0$, and by the preceding
section, $\mathbf{E}[|c_{n}|^{2}]=d^{n}(d+1)$. As long as $s<-1/2$, we have
$\mathbf{E}[\|F\|_{s}^{2}]<\infty$ and consequently $\|F\|_{s}^{2}<\infty$
almost surely, as requested in Theorem 2.10.

One can ask if the $\mathrm{PHC}_{d}$ is _not_ $s$-Sobolev for $s>-1/2$. The
trick used in [NPS20], Section 6.1 can indeed be applied to our setting:
therein, it is proved by elementary means that for $s<0$, there is a constant
$c_{s}>0$ such that for $r<1$,

$\|F\|_{s}^{2}\geqslant\frac{c_{s}}{|\log
r|^{2s}}\sum_{n=0}^{\infty}r^{2n}|c_{n}|^{2}=\frac{c_{s}}{|\log
r|^{2s}}\frac{1}{2\pi}\int_{0}^{2\pi}|F(r\mathrm{e}^{it})|^{2}\mathrm{d}t=\frac{c_{s}}{|\log
r|^{2s}}\frac{1}{2\pi}\int_{0}^{2\pi}\mathrm{e}^{2\mathrm{Re}(f(z))}\mathrm{d}t$
(8.11)

where the middle equality is Parseval’s identity and the last one is the
definition of $F$. Now, when $f$ is a Gaussian analytic function, the limit of
this last integral with a suitable normalization term exists, and it is a real
random variable representing the total mass of the Gaussian Multiplicative
Chaos. The existence of a limit is not trivial, and the identification of the
distribution of the limit (the Fyodorov-Bouchaud-Lie formula) was proved
recently, see [R+20] and [NPS20]. Given these, [NPS20] saw that in the
Gaussian case, the right-hand side of (8.11) converges to a random number
times $|\log 0|$, hence $\|F\|^{2}_{s}=\infty$ and $F$ is not $s$-Sobolev for
$s\in[-1/2,0)$. In our case where $f$ is the Poisson function given by (2.10),
the existence of a limit when $r\to d^{-1/2}$ of

$\frac{1}{2\pi}\int_{0}^{2\pi}\mathrm{e}^{2\sum_{k=1}^{\infty}X_{k}\frac{r^{k}\cos(kt)}{k}}\mathrm{d}t$

is not known.

###  8.5 The correlation of the Poisson Field

We close this section by a small remark which strenghthens the analogy between
$F$ and the Gaussian holomorphic chaos.

######  Proposition 8.5.

$f$ is log-correlated in the following sense: for every $z,w$ in the disk of
convergence of $f$,

$\mathrm{Cov}(f(z),f(w))=\sum_{\alpha=1}^{\infty}\sum_{\beta=1}^{\infty}\log\left(\frac{1}{1-dz^{\alpha}\bar{w}^{\beta}}\right)\frac{1}{\alpha\beta}.$
(8.12)

###### Proof.

Let us note $Z_{\ell}=Y_{\ell}-d^{\ell}/\ell$. Since the $Y_{i}$ are
independent, so are the $Z_{i}$, and in particular $E[Z_{i}Z_{j}]=0$ if $i\neq
j$, and $\mathbf{E}[Z_{i}^{2}]=\mathrm{Var}(Y_{i})=d^{i}/i$, and so

$\displaystyle\mathbf{E}[\mathscr{P}(z)\overline{\mathscr{P}(w)}]$
$\displaystyle=\sum_{k,h=1}^{\infty}\frac{z^{k}\bar{w}^{h}}{kh}\mathbf{E}\left[\sum_{\begin{subarray}{c}i|k\\\
j|h\end{subarray}}ijZ_{i}Z_{j}\right]$
$\displaystyle=\sum_{k,h=1}^{\infty}\frac{z^{k}\bar{w}^{h}}{kh}\sum_{i\in\mathrm{div}(h,k)}i^{2}\mathbf{E}[Z_{i}^{2}]$
$\displaystyle=\sum_{k,h=1}^{\infty}\frac{z^{k}\bar{w}^{h}}{kh}\sum_{\ell\in\mathrm{div}(h,k)}\ell
d^{\ell}.$

where $\mathrm{div}(a,b)$ denotes the set of common divisors of $a$ and $b$.
We can reorder the sum, and we get

$\displaystyle\mathbf{E}[\mathscr{P}(z)\overline{\mathscr{P}(w)}]$
$\displaystyle=\sum_{\ell=1}\sum_{a,b=1}^{\infty}\frac{z^{a\ell}\bar{w}^{b\ell}}{a\ell\times
b\ell}\ell d^{\ell}$
$\displaystyle=\sum_{a,b=1}^{\infty}\frac{1}{ab}\sum_{\ell=1}\frac{z^{a\ell}\bar{w}^{b\ell}d^{\ell}}{\ell}$
$\displaystyle=-\sum_{a,b=1}^{\infty}\frac{\log(1-dz^{a}\bar{w}^{b})}{ab}.$

∎

###  8.6 Set-partitions of multisets

In this informal section, we give some remarks on the combinatorics of the
generating function (2.16). Let $r\geqslant 1$ be an integer. We follow the
terminology by Bender [Ben74]: given a multiset $\mathscr{M}$ on $r$ elements,
that is, $\mathscr{M}=\\{\\{1^{n_{1}},\dotsc,r^{n_{r}}\\}\\}$, a _set-
partition_ of $\mathscr{M}$ is a multiset $B=\\{\\{B_{1},\dotsc,B_{r}\\}\\}$
of nonempty indistinguishable sets $B_{1},\dotsc,B_{h}\subset[r]$, possibly
repeated, such that their multiset-union is $\mathscr{M}$. In other words, the
$B_{j}$ are subsets of $[r]$ such that for every $i\in[r]$,

$\sum_{j=0}^{h}\mathbf{1}_{i\in B_{j}}=n_{i}.$

The number of blocks in the multiset $B$ will be noted $|B|$.

######  Example 8.6.

If $\mathscr{M}=\\{1,\dotsc,r\\}$ is a set, then this corresponds to the
classical set-partitions of $[r]$, counted by the Bell numbers $B_{r}$. If
$\mathscr{M}=\\{1^{n}\\}$ ($1$ repeated $n$ times) then the only set-partition
of $\mathscr{M}$ is $\\{1\\},\\{1\\},\dotsc,\\{1\\}$. If
$\mathscr{M}=\\{\\{1^{4},2^{1},3^{2},4^{2}\\}\\}$, then a possible set-
partition of $\mathscr{M}$ is

$\\{1,2,3\\},\\{1,3,4\\},\\{1\\},\\{1\\},\\{3,4\\}$

and another one is

$\\{1,2,3,4\\},\\{1,3\\},\\{1,4\\},\\{1\\}.$

Now, let $z_{1},\dotsc,z_{r}$ be complex variables and $q\geqslant 1$ a
parameter. The multivariable function

$G(z_{1},\dotsc,z_{r})=\prod_{S\subset[r]}\frac{1}{1-q\prod_{s\in S}z_{s}}$

is the generating function of set-partitions of multisets in the following
sense; let us note

$\mathrm{par}(\mathscr{M},q)=\sum_{B\vdash\mathscr{M}}q^{|B|}$

where the $B\vdash\mathscr{M}$ means that the sum runs over all the set-
partitions of the multiset $\mathscr{M}$. Then,

$G(z)=\sum_{\\{\\{1^{n_{1}},\dots,r^{n_{r}}\\}\\}}\mathrm{par}(\\{\\{1^{n_{1}},\dots,r^{n_{r}}\\}\\},q)\times
z_{1}^{n_{1}}\dotsc z_{r}^{n_{r}}.$ (8.13)

For instance, the coefficient of $z_{1}\dots z_{r}$ in $G$, when $q=1$, is
nothing but the classical number of partitions of $[r]$, which is counted by
the Bell numbers. Then, the generating function (2.16) is a weighted sum of
set-partitions of multisets, such that the blocks with odd cardinality are all
distincts. The weight is $(-1)^{k}d^{|B|}$, where $k$ is the number of blocks
with odd cardinality.

######  Remark 8.7.

A celebrated formula in combinatorics states that $\prod_{i\geqslant
0}(1-z^{2i+1})=\sum(-1)^{n}p_{s}(n)z^{n}$, with $p_{s}(n)$ the number of self-
conjugate partitions of $n$, see for instance [Aig07, eqn. (11) page 127].
There is a chance that products like the
$\prod_{S\in\mathscr{V}^{\mathrm{odd}}_{r}}(1-dz_{S})$ appearing in (2.16)
have a similar simple interpretation, but for the moment it is not clear for
the author.

##  9 Proof of Theorem 2.2

The goal of this section is to prove Theorem 2.2. We chose to follow standard
methods in path-counting combinatorics, but an alternative proof could use the
Stein method to get a convergence speed.

###  9.1 Usual preliminaries

#### Notations.

When $a$ is a positive integer, $[a]$ is the set $\\{1,\dotsc,a\\}$. The
falling factorials of $a$ are
$(a)_{1}=a,(a)_{2}=a(a-1),\dotsc,(a)_{k}=a(a-1)\dotsc(a-k+1)$ and the binomial
numbers $\binom{a}{k}=(a)_{k}/k!$. When $\mathscr{E}$ is a set,
$\\#\mathscr{E}$ is the number of its elements. A $k$-tuple of elements in a
set $\mathscr{E}$ is a sequence $(i_{1},\dotsc,i_{k})$ where the $i_{t}$ are
elements of $\mathscr{E}$, while a $k$-set of elements in $\mathscr{E}$ is a
set of $k$ _distincts_ elements in $\mathscr{E}$. We note $\mathscr{E}_{k}$
the set of $k$-tuples of elements in $[n]=\\{1,\dotsc,n\\}$, that is:

$\mathscr{E}_{k}=\\{\mathbf{i}=(i_{1},\dotsc,i_{k}):i_{s}\in[n]\\}.$

We will never indicate the dependencies in $n$, the size of the matrix $A$.
However, every object encountered in the sequel depends on $n$, and every
limit is with respect to $n\to\infty$.

In general, we will adopt the following notational rules:

  1. (i)

Calligraphic letters are for sets.

  2. (ii)

Boldface letters are for tuples, for instance
$\mathbf{i}=(i_{1},\dotsc,i_{k})$.

#### Directed graphs.

The matrix $A$ is an $n\times n$ matrix with 0/1 entries. It represents the
adjacency matrix of a digraph, on the vertex set $V=[n]$. The edge set is
$E=\\{(i,j)\in[n]\times[n]:A_{i,j}=1\\}$. We insist on the fact that $G=(V,E)$
is directed and possibly has loops. We say that a digraph
$G^{\prime}=(V^{\prime},E^{\prime})$ is weakly connected if, for any pair of
distinct vertices $i,j$, there is a (weak) path from $i$ to $j$, ie a sequence
$i_{0}=i,i_{1},\dotsc,i_{k}=j$ such that for each $s$, $(i_{s-1},i_{s})\in
E^{\prime}$ or $(i_{s},i_{s-1})\in E^{\prime}$ or both. Naturally, if this is
the case one has $\\#E^{\prime}-\\#V^{\prime}\geqslant-1$, with equality if
ond only if $G^{\prime}$ has no cycle.

#### A-sub notation.

For any tuple $\mathbf{i}=(i_{1},\dotsc,i_{k})\in\mathscr{E}_{k}$, the
shorthand $A_{\mathbf{i}}$ stands for:

$A_{\mathbf{i}}:=A_{i_{1},i_{2}}\times\dotsb\times
A_{i_{k-1},i_{k}}A_{i_{k},i_{1}}.$ (9.1)

It is the indicator that the cycle induced by $\mathbf{i}$ is present in $G$.
With this notation,

$\mathrm{tr}(A^{k})=\sum_{\mathbf{i}\in\mathscr{E}_{k}}A_{\mathbf{i}}.$

###  9.2 Reduction to cycle count

For every $\mathbf{i}=(i_{1},\dotsc,i_{k})\in\mathscr{E}_{k}$, we note

$\displaystyle V(\mathbf{i})=\\{i_{1},\dotsc,i_{k}\\}$ $\displaystyle
v(\mathbf{i})=\\#V(\mathbf{i})$ (9.2) $\displaystyle
E(\mathbf{i})=\\{(i_{1},i_{2}),(i_{2},i_{3}),\dotsc,(i_{k-1},i_{k}),(i_{k},i_{1})\\}$
$\displaystyle e(\mathbf{i})=\\#E(\mathbf{i}).$ (9.3)

Here are simple examples with a graphical representations. If an edge $(i,j)$
is crossed twice or more in $\mathbf{i}$, we represent it as many times, but
it counts as one edge in $E(\mathbf{i})$, see the middle figure.

|  |  |  |
---|---|---|---|---
$\mathbf{i}=(3,5,7,7,8)$ |  | $\mathbf{j}=(1,9,1,9,3)$ |  | $\mathbf{k}=(1,2,3,4,3,2)$
$v(\mathbf{i})=4$ |  | $v(\mathbf{j})=3$ |  | $v(\mathbf{k})=4$
$e(\mathbf{i})=5$ |  | $e(\mathbf{j})=4$ |  | $e(\mathbf{k})=6$

One can interpret $v(\mathbf{i})$ as the number of ‘vertices’ of $[n]$ that
are visited by $\mathbf{i}$, and $e(\mathbf{i})$ as the number of distinct
‘edges’ of $\mathbf{i}$. The digraph $(V(\mathbf{i}),E(\mathbf{i}))$ contains
a loop, so necessarily $v(\mathbf{i})\leqslant e(\mathbf{i})$. On the other
hand, there can be no more edges than the length of $\mathbf{i}$, that is,
$e(\mathbf{i})\leqslant k$ when $\mathbf{i}\in\mathscr{E}_{k}$. Since the
entries of $A$ are independent 0/1 random variables, for every fixed
$\mathbf{i}$ we have

$\mathbf{E}[A_{\mathbf{i}}]=\left(\frac{d}{n}\right)^{e(\mathbf{i})}.$ (9.4)

For every $v\leqslant e\leqslant k$, we set
$\mathscr{E}_{k}(v,e)=\\{\mathbf{i}\in\mathscr{E}_{k},v(\mathbf{i})=v,e(\mathbf{i})=e\\}$,
and

$\displaystyle T_{k}=\sum_{\begin{subarray}{c}e\leqslant k\\\
v=e\end{subarray}}\sum_{\mathbf{i}\in\mathscr{E}_{k}(v,e)}A_{\mathbf{i}},$
$\displaystyle R_{k}=\sum_{\begin{subarray}{c}e\leqslant k\\\
v<e\end{subarray}}\sum_{\mathbf{i}\in\mathscr{E}_{k}(v,e)}A_{\mathbf{i}}$
(9.5)

so that naturally $\mathrm{tr}(A^{k})=T_{k}+R_{k}$. Before stating a few
technical lemmas, we recall the fact that $k$ is a fixed integer.

######  Lemma 9.1.

$\\#\mathscr{E}_{k}(v,e)\leqslant k^{k}n^{v}$.

###### Proof.

We first choose which $v$ vertices will be used, which gives
$\binom{n}{v}\leqslant n^{v}$. Then, we organize them in a $k$-tuple so that
exactly $e$ edges appear, but the number of ways to do this is certainly
smaller than $v^{k}\leqslant k^{k}$. ∎

######  Lemma 9.2.

$\mathbf{E}[R_{k}]\leqslant d^{k}k^{k+2}/n$. Consequently, $R_{k}\to 0$ in
probability and in distribution.

###### Proof.

We use (9.4):

$\mathbf{E}[R_{k}]=\sum_{v<e\leqslant
k}\\#\mathscr{E}_{k}(v,e)\times\left(\frac{d}{n}\right)^{e}.$

By the preceding lemma,
$\mathbf{E}[R_{k}]\leqslant\sum_{v<e}k^{k}d^{e}n^{v}/n^{e}$. It is crudely
bounded by $d^{k}k^{k+2}n^{-1}$. The rest follows from the Markov inequality.
∎

######  Lemma 9.3.

$\mathscr{E}_{k}(v,v)$ is empty if $v$ is not a divisor of $k$. Otherwise, if
$k=vq$, then the elements of $\mathscr{E}_{k}(v,v)$ are exactly the sequences

$(i_{1},i_{2},\dotsc,i_{v},i_{1},\dotsc,i_{v},\dotsc,i_{1},\dotsc,i_{v})$
(9.6)

where $i_{1},\dotsc,i_{v}$ are all distinct, and the subsequence
$\mathbf{i}^{\prime}=(i_{1},\dotsc,i_{v})$ is repeated $q$ times.

###### Proof.

Let $\mathbf{i}$ be in $\mathscr{E}_{k}(v,v)$. In the sequel, we will note
$s\in[k+1]$ the first time a vertex is revisited, that is:

$s=\min\\{t\in\\{2,\dotsc,k+1\\}:i_{t}\in\\{i_{1},\dotsc,i_{t-1}\\}\\}.$

If $s=k+1$, then each $i_{t}$ is present exactly once in $\mathbf{i}$, so
$\mathbf{i}$ is a cycle on $k$ distinct vertices and
$v(\mathbf{i})=e(\mathbf{i})=k$. Otherwise, $s\leqslant k$, and
$\mathbf{i}^{\prime}:=(i_{1},\dotsc,i_{s})$ has
$v(\mathbf{i}^{\prime})=e(\mathbf{i}^{\prime})=s$.

If $v(\mathbf{i})>v(\mathbf{i}^{\prime})$, then $\mathbf{i}$ visits a ‘new’
vertex $j\notin\mathbf{i}^{\prime}$ after $s$; but then, there will be a
second cycle in $\mathbf{i}$, and $(V(\mathbf{i}),E(\mathbf{i}))$ will have at
least two cycles; if this was true, then we should have
$e(\mathbf{i})\geqslant v(\mathbf{i})+1$, a contradiction.

No other vertices than the $s$ vertices of $\mathbf{i}^{\prime}$ will thus be
present in $\mathbf{i}$; but since
$e(\mathbf{i})=v(\mathbf{i})=v(\mathbf{i}^{\prime})=s$, it also means that no
other edge than $E(\mathbf{i}^{\prime})$ will be present in $E(\mathbf{i})$.
From this, it is easily seen that $\mathbf{i}$ consists in $q$ repetitions of
$\mathbf{i}^{\prime}$ for some $q$, and consequently that $qs=k$. ∎

We now make a crucial observation. Let us fix some integer $\ell$. Let
$k=q\ell$ be a multiple of $\ell$, and let
$\mathbf{i}\in\mathscr{E}_{k}(\ell,\ell)$; by the lemma above, $\mathbf{i}$ is
just some $\mathbf{i}^{\prime}=(i_{1},\dotsc,i_{\ell})$ repeated $q$ times.
But then, since $A$ has only zero/one entries,

$A_{\mathbf{i}}=(A_{i_{1},i_{2}}\times\dotsb\times
A_{i_{\ell},i_{1}})^{q}=A_{\mathbf{i}^{\prime}}.$

On the other hand, the lemma also shows that the elements in
$\mathscr{E}_{k}(\ell,\ell)$ are fully determined by their first $\ell$ terms,
and thus $\\#\mathscr{E}_{k}(\ell,\ell)=\\#\mathscr{E}_{\ell}(\ell,\ell)$.
Consequently, for every multiple $k$ of $\ell$,

$\sum_{\mathbf{i}\in\mathscr{E}_{k}(\ell,\ell)}A_{\mathbf{i}}=\sum_{\mathbf{j}\in\mathscr{E}_{\ell}(\ell,\ell)}A_{\mathbf{j}}.$
(9.7)

In other words, the preceding sum does not depend on $k$, but only on $\ell$.
But one can go further into simplifying this expression: the set
$\mathscr{E}_{\ell}(\ell,\ell)$ is nothing but the set of $\ell$-tuples of
distinct elements, say $(i_{1},\dotsc,i_{\ell})$; but if $\mathbf{j}$ is
another such tuple, obtained from $\mathbf{i}$ by a cyclic permutation, say
$\mathbf{j}=(i_{1+a},i_{2+a},\dotsc,i_{a})$, then
$A_{\mathbf{i}}=A_{\mathbf{j}}$. For each $\mathbf{i}$, there are exactly
$\ell$ cyclic permutations of $\mathbf{i}$; noting $\mathscr{C}_{\ell}$ the
set of ordered $\ell$-tuples of distinct elements of $[n]$ up to cyclic
permutation, it is now clear that for every $k$ multiple of $\ell$,

$\sum_{\mathbf{i}\in\mathscr{E}_{k}(\ell,\ell)}A_{\mathbf{i}}=\ell\sum_{\mathbf{i}\in\mathscr{C}_{\ell}}A_{\mathbf{i}}.$

This is why we introduce the $k$-free notation $S_{\ell}$:

$S_{\ell}:=\sum_{\mathbf{i}\in\mathscr{C}_{\ell}}A_{\mathbf{i}}.$ (9.8)

With this notation and the discussion above,

$T_{k}=\sum_{\ell|k}\ell S_{\ell}.$

We now show that the random variables $S_{\ell}$ are asymptotically Poisson
independent random variables with paremeters $d^{\ell}/\ell$, using the method
of falling factorial moments.

######  Proposition 9.4.

Let $m,\ell_{1},p_{1},\dotsc,\ell_{m},p_{m}$ be positive integers, with the
$\ell_{i}$ all distinct. Then,

$\lim_{n\to\infty}\mathbf{E}\left[(S_{\ell_{1}})_{p_{1}}\times\dotsb\times(S_{\ell_{m}})_{p_{m}}\right]=\left(\frac{d^{\ell_{1}}}{\ell_{1}}\right)^{p_{1}}\times\dotsb\times\left(\frac{d^{\ell_{m}}}{\ell_{m}}\right)^{p_{m}}.$
(9.9)

The proof of Proposition 9.4 will be the content of the next subsection;
before that, we show how it directly implies the main result in Theorem 2.2.
We recall from Definition 2.1 that $Y_{\ell}$ is a family if independent
Poisson random variables, with parameter $d^{\ell}/\ell$.

###### Proof of Theorem 2.2.

The Poisson distribution $Z\sim\mathrm{Poi}(\lambda)$ is the unique
probability distribution on nonnegative integers such that
$\mathbf{E}[(Z)_{k}]=\lambda^{k}$ for all $k\geqslant 0$. Consequently, the
RHS of (9.9) is nothing but

$\mathbf{E}[(Y_{\ell_{1}})_{p_{1}}\times\dotsb\times(Y_{\ell_{m}})_{p_{m}}].$

The joint convergence of the factorial moments described in (9.9) implies the
convergence

$(S_{\ell_{1}},\dotsc,S_{\ell_{m}})\xrightarrow{\mathrm{law}}(Y_{\ell_{1}},\dotsc,Y_{\ell_{m}})$

and in particular
$(S_{1},\dotsc,S_{k})\xrightarrow{\mathrm{law}}(Y_{1},\dotsc,Y_{k})$ for any
$k$. Since $T_{k}=\sum_{\ell|k}\ell S_{\ell}$, there is a fixed linear
function $g:\mathbb{R}^{k}\to\mathbb{R}^{k}$ such that
$(T_{1},\dotsc,T_{k})=g(S_{1},\dotsc,S_{k})$; more precisely,

$g(x_{1},\dotsc,x_{k})=\left(x_{1},x_{1}+2x_{2},x_{1}+3x_{3},x_{1}+2x_{2}+4x_{4},\dotsc,\sum_{i|k}ix_{i}\right).$

Since $\mathrm{tr}(A^{k})=T_{k}+R_{k}$, we obtain

$(\mathrm{tr}(A^{1},\dotsc,\mathrm{tr}(A^{k}))=g(S_{1},\dotsc,S_{k})+(R_{1},\dotsc,R_{k}).$

Lemma 9.2 says that $R_{i}\to 0$ in probability for every fixed $i$, so
$(R_{1},\dotsc,R_{k})\to(0,\dotsb,0)$ in probability for every fixed $k$.
Since $g$ is continuous, Slutsky’s lemma implies that

$(T_{1},\dotsc,T_{k})\xrightarrow{\mathrm{law}}g(Y_{1},\dotsc,Y_{k})=\left(X_{1},\dotsc,X_{k}\right)$

which is the claim in Theorem 2.2.

∎

###  9.3 Proof of Proposition 9.4

For all the proof, we definitely fix the integer $m\geqslant 1$, as well as
the lengths $\ell_{1},\dotsc,\ell_{m}$ and the powers $p_{1},\dotsc,p_{m}$;
all these numbers are assumed to be nonzero integers.

######  Definition 9.5.

Let $\ell,p$ be two integers. The $(\ell,p)$-loopsoup, noted
$\mathscr{S}_{\ell,p}$, is the collection of ordered $p$-tuples of distinct
cycles of length $\ell$, that is, elements in $\mathscr{C}_{\ell}$. The
$(\bm{\ell},\bm{p})$ loopsoup associated with
$\bm{\ell}=(\ell_{1},\dotsc,\ell_{m}),\bm{p}=(p_{1},\dotsc,p_{m})$ is the set
$\mathscr{S}_{\bm{\ell},\bm{p}}=\mathscr{S}_{\ell_{1},p_{1}}\times\dotsb\times\mathscr{S}_{\ell_{m},p_{m}}$,
whose elements are $m$-tuples $(\bm{c}_{1},\dotsc,\bm{c}_{m})$, with
$\bm{c}_{i}\in\mathscr{S}_{\ell_{i},p_{i}}$. The total number of cycles in a
loopsoup is $p_{1}+\dotsb+p_{m}$. The maximum number of $i\in[n]$ that appear
in an element of $\mathscr{S}_{\bm{\ell},\bm{p}}$ is

$M=M(\bm{\ell},\bm{p})=\ell_{1}p_{1}+\dotsb+\ell_{m}p_{m}.$ (9.10)

######  Example 9.6.

A typical element of $\mathscr{S}_{\bm{\ell},\bm{p}}$ is a tuple of tuples.
Let us take for instance $\bm{\ell}=(2,4)$ and $\bm{p}=(3,6)$. An element of
$\mathscr{S}_{\bm{\ell},\bm{p}}$ is $(\bm{c}_{1},\bm{c}_{2})$ where
$\bm{c}_{1}=(\mathbf{i}_{1},\mathbf{i}_{2},\mathbf{i}_{3})$ and
$\mathbf{i}_{s}$ are distinct $2$-cycles, and
$\bm{c}_{2}=(\mathbf{j}_{1},\mathbf{j}_{2},\mathbf{j}_{3},\mathbf{j}_{4},\mathbf{j}_{5},\mathbf{j}_{6})$
where the $\mathbf{j}_{s}$ are distinct $4$-cycles.

If $\bm{c}=(\bm{c}_{1},\dotsc,\bm{c}_{m})\in\mathscr{S}_{\bm{\ell},\bm{p}}$,
we refer to the $j$-th element of $\bm{c}_{i}$ as $\bm{c}_{i,j}$ and we note

$\displaystyle e(\bm{c})=\bigcup_{i\in[m]}E(\bm{c}_{i,j}:i\in[m],j\in[p_{i}])$
$\displaystyle e(\bm{c})=\\#E(\bm{c}).$

It is the set of ‘edges’ appearing in one of the $p_{1}+\dotsb+p_{m}$ cycles
appearing in $\bm{c}$. Since each $\bm{c}_{i,j}$ is a cycle and thus has the
same number of vertices and edges, we have $e(\bm{c})\leqslant M$.

######  Lemma 9.7.

For any $m\geqslant 1$ and
$\bm{\ell}=(\ell_{1},\dotsc,\ell_{m}),\bm{p}=(p_{1},\dotsc,p_{m})$, one has

$\mathbf{E}\left[\prod_{i=1}^{m}(S_{\ell_{i}})_{p_{i}}\right]=\sum_{\bm{c}\in\mathscr{S}_{\bm{\ell},\bm{p}}}\left(\frac{d}{n}\right)^{e(\bm{c})}.$
(9.11)

###### Proof.

$S_{k}$ is the number of $k$-cycles that appear in the graph induced by $A$,
so $(S_{k})_{h}$ is the number of ways to choose an $h$-tuple of $k$-cycles
that appear in the graph induced by $A$, that is:
$(S_{k})_{k}=\sum_{(\mathbf{i}_{1},\dotsc,\mathbf{i}_{h})\in\mathscr{S}_{k,h}}A_{\mathbf{i}_{1}}\dotsb
A_{\mathbf{i}_{h}}$. We develop the product and take the expectation:

$\mathbf{E}\left[\prod_{i=1}^{m}(S_{\ell_{i}})_{p_{i}}\right]=\sum_{\bm{c}\in\mathscr{S}_{\bm{\ell},\bm{p}}}\mathbf{E}\prod_{i=1}^{m}\prod_{j=1}^{p_{i}}A_{\mathbf{c}_{i,j}}=\sum_{\bm{c}\in\mathscr{S}_{\bm{\ell},\bm{p}}}\left(\frac{d}{n}\right)^{e(\bm{c})}.$

∎

In (9.11), we are going to split the sum according to the value of
$e(\bm{c})\in[M]$: for every $k\leqslant M$, we set
$\mathscr{S}_{\bm{\ell},\bm{c}}(k)=\\{\bm{c}\in\mathscr{S}_{\bm{\ell},\bm{p}},e(\bm{c})=k\\}$.
It is clear that when we sort the summands in (9.11) according to this value
of $e$, we obtain that it is equal to $Z_{1}+\dotsb+Z_{M}$, where

$\displaystyle
Z_{k}=\left(\frac{d}{n}\right)^{k}\\#(\mathscr{S}_{\bm{\ell},\bm{c}}(k)).$

As expected, the dominant term in (9.11) is $Z_{M}$. This is the content of
the following proposition, which, considering the above discussion, finishes
the proof of Theorem 9.4.

######  Proposition 9.8.

There is a constant $c=c(\bm{\ell},\bm{p},d)>0$ such that for any $n$ and
$k<M$,

$\\#(\mathscr{S}_{\bm{\ell},\bm{c}}(k))\leqslant cn^{k-1}.$ (9.12)

Moreover,

$\\#(\mathscr{S}_{\bm{\ell},\bm{c}}(M))=(1+o(1))\prod_{i=1}^{m}\left(\frac{n^{\ell_{i}}}{\ell_{i}}\right)^{p_{i}}.$
(9.13)

###### Proof of (9.13).

Let $\mathscr{S}^{\prime}$ be the subset of
$\mathscr{S}_{\bm{\ell},\bm{c}}(M)$ composed of those $\bm{c}$ which are
completely vertex-disjoint, ie $V(\bm{c}_{i,k})\cap
V(\bm{c}_{j,h})=\varnothing$ when $(i,h)\neq(j,k)$. By elementary counting,

$\\#\mathscr{S}^{\prime}=\frac{(n)_{M}}{\ell_{1}^{p_{1}}\times\dotsb\times\ell_{m}^{p_{m}}}.$

Since $M$ is fixed, this expression is equivalent to
$n^{M}/\prod\ell_{i}^{p_{i}}$ when $n\to\infty$. We shall now prove that the
number of elements in
$\mathscr{S}^{\prime\prime}=\mathscr{S}_{\bm{\ell},\bm{c}}(M)\setminus\mathscr{S}^{\prime}$
is $o(n^{M})$, which is well enough for our needs since
$\\#\mathscr{S}_{\bm{\ell},\bm{c}}(M)=\\#\mathscr{S}^{\prime}+\\#\mathscr{S}^{\prime\prime}$.
If $\bm{c}$ is in $\mathscr{S}^{\prime\prime}$, it means that two among the
$M$ distinct cycles of $\bm{c}$ visit one common vertex, and consequently that
$v(\bm{c})\leqslant M-1$. Since $\bm{\ell}$ and $\bm{c}$ are fixed, for every
set $V\subset[n]$, there is a constant $c$ such that there are less than $c$
elements $\bm{c}\in\mathscr{S}_{\bm{\ell},\bm{c}}$ such that $V(\bm{c})=V$
(one can take $c=M^{M}$ for instance), and so the number of elements in
$\mathscr{S}^{\prime\prime}$ is smaller than

$c+c\binom{n}{2}+\dotsb+c\binom{n}{M-1},$

an extremely crude bound, but still smaller than $cn^{M-1}$ upon adjusting the
constant $c$. ∎

###### Proof of (9.12).

Consider an element $\bm{c}\in\mathscr{S}_{\bm{\ell},\bm{c}}(k)$ for $k<M$. If
all of its cycles were vertex-disjoints, then $\bm{c}$ would have $M$ edges,
so at least two of its cycles share a common vertex, and consequently the
number of vertices $v(\bm{c})$ present in $\bm{c}$ cannot be greater than
$k-1$. But for any subset $V\subset[n]$ with $v(\bm{c})$ elements, there is a
constant $c$ such that there are no more than $c$ elements in
$\mathscr{S}_{\bm{\ell},\bm{c}}$ with $V(\bm{c})=V$. Consequently,

$\\#\mathscr{S}_{\bm{\ell},\bm{c}}(k)\leqslant
c+c\binom{n}{2}+\dotsb+c\binom{n}{k-1}.$

This is smaller than $cn^{k-1}$ for some (other) constant $c$, depending only
on $\bm{\ell}$ and $\bm{c}$. ∎

##  10 Proofs of our results when $d_{n}\to\infty$

###  10.1 Tightness and weak convergence: proof of Theorem 3.2

The proof strategy is the same as for the sparse case: the main difference is
in the identification of the distributional limits of the traces. We will
adopt the following notation:

$\hat{q}_{n}(z)=\frac{\det(I-zA_{n}/\sqrt{d_{n}})}{\sqrt{d_{n}}}.$ (10.1)

We first show that the sequence $(\hat{q}_{n})$ is tight on $D(0,1)$ and then
we identify that its limit is $-z\sqrt{1-z^{2}}G(z)$ by finding the
distributional limit of the traces of $A^{k}$.

######  Lemma 10.1.

The sequence of random polynomials $\hat{q}_{n}$ is tight in $\mathbb{H}_{1}$.

###### Proof.

We simply use our criterion from Lemma 5.2. First of all, we note that
$\hat{q}_{n}(z)=\sum(-1)^{k}z^{k}\hat{\Delta}_{k}$, where
$\hat{D}_{k}=\Delta_{k}d_{n}^{-(k+1)/2}$ and $\Delta_{k}$ is exactly (6.4).
Consequently, Proposition 6.2 shows that

$\mathbf{E}[|\hat{\Delta}_{k}|^{2}]=\frac{(n)_{k}}{d_{n}^{k+1}}\left(\frac{d_{n}}{n}\right)^{k}(1-np-p+nkp-k^{2}p)\leqslant\frac{1+d_{n}+2kd_{n}}{d_{n}}\leqslant
3k.$

Since $\limsup(3k)^{1/2k}=1$, Lemma 5.2 leads to the conclusion. ∎

We must now identify the finite-dimensional limits of $\hat{q}_{n}$. Using
(6.3), we have $\hat{q}_{n}(z)=\mathrm{e}^{-f_{n}(z)}/\sqrt{d_{n}}$, where

$f_{n}(z)=\sum_{k=1}^{\infty}\mathrm{tr}\left(\left(\frac{A}{\sqrt{d_{n}}}\right)^{k}\right)\frac{z^{k}}{k}.$

Consequently, for fixed $n$ and every $z<1/\sqrt{d_{n}}$, using the expansion
of the complex logarithm on $D(0,1)$ we get

$\hat{q}_{n}(z)=\frac{1-z\sqrt{d_{n}}}{\sqrt{d_{n}}}\frac{\mathrm{e}^{-f_{n}(z)}}{1-z\sqrt{d_{n}}}=\frac{1-z\sqrt{d_{n}}}{\sqrt{d_{n}}}\mathrm{e}^{-\sum_{k=1}^{\infty}\alpha_{k}\frac{z^{k}}{k}}$

with

$\alpha_{k}:=\frac{\mathrm{tr}(A^{k})}{\sqrt{d_{n}}^{k}}-\sqrt{d_{n}}^{k}$
(10.2)

and the log-exp formula (6.10) gives

$\hat{q}_{n}(z)=\frac{1-z\sqrt{d_{n}}}{\sqrt{d_{n}}}\left(1+\sum_{k=1}^{n}P_{k}(\alpha_{1},\dotsc,\alpha_{k})\frac{z^{k}}{k!}\right),$
(10.3)

an identity which is valid for $|z|<1/\sqrt{d_{n}}$, but which extends to
every $z$ by analyticity. Thanks to this identity, we see that proving the
finite-dimensional convergence of $\hat{q}_{n}$ only reduces to studying the
distributional limits of the $\alpha_{i}$ and this is done in Theorem 3.1 and
its proof thereafter. Given this theorem, we can finish the proof of Theorem
3.2 by a simple application of Theorem 5.1 which says that $\alpha_{k}$
converges in distribution towards $1+\sqrt{k}N_{k}$ if $k$ is even and
$\sqrt{k}N_{k}$ if $k$ is odd, where $N_{k}$ is a real standard Gaussian;
consequently,

$\mathrm{e}^{-\sum_{k=1}^{\infty}\alpha_{k}\frac{z^{k}}{k}}\xrightarrow[n\to\infty]{}\mathrm{e}^{-\sum_{k=}^{\infty}\frac{z^{2k}}{2k}-\sum_{k=1}^{\infty}\frac{N_{k}}{\sqrt{k}}z^{k}}=\mathrm{e}^{\frac{1}{2}\log(1-z^{2})-\sum_{k=1}^{\infty}\frac{N_{k}}{\sqrt{k}}z^{k}}=\sqrt{1-z^{2}}\times
G(z).$

The sequence of functions $z\mapsto(1-z\sqrt{d_{n}})/\sqrt{d_{n}}$ converges
uniformly on $\mathbb{C}$ towards $-z$, so by continuity

$\hat{q}_{n}(z)=\frac{1-z\sqrt{d_{n}}}{\sqrt{d_{n}}}\times\mathrm{e}^{-\sum_{k=1}^{\infty}\alpha_{k}\frac{z^{k}}{k}}\xrightarrow[n\to\infty]{\mathrm{law}}-z\times\sqrt{1-z^{2}}G(z).$

###  10.2 Proof of Theorem 3.3

It is the same proof as for Theorem 2.6 in Section 7. The limiting function is
$z\sqrt{1-z^{2}}G(z)$ and $G$ has no zeroes, hence $\hat{q}_{n}$ has exactly
one root which converges towards $0$, and all the other roots are with high
probability outside $D(0,1-\varepsilon)$. The result follows from the fact
that the roots of $\hat{q}_{n}$ are the inverse eigenvalues of
$A_{n}/\sqrt{d_{n}}$.

###  10.3 Proof of Theorem 3.1: trace asymptotics

We now prove the trace limits in Theorem 3.1. The proof globally follows the
same lines as for the sparse regimes and could possibly be simplified. We will
stick to the same notations as in Section 9, most of them being gathered at
Page 9.1. The starting point is the identity

$\mathrm{tr}(A^{k})=\sum_{\mathbf{i}\in\mathscr{E}_{k}}A_{\mathbf{i}}$

where $\mathscr{E}_{k}$ is the set of $k$-tuples of elements of $[n]$. If
$\mathbf{i}$ has $e(\mathbf{i})$ ‘edges’ as in (9.2), then by independence

$\mathbf{E}[A_{\mathbf{i}}]=\left(\frac{d_{n}}{n}\right)^{e(\mathbf{i})}.$

For every $v\leqslant e\leqslant k$, we set
$\mathscr{E}_{k}(v,e)=\\{\mathbf{i}\in\mathscr{E}_{k},v(\mathbf{i})=v,e(\mathbf{i})=e\\}$,
and

$\displaystyle T_{k}=\sum_{\begin{subarray}{c}e\leqslant k\\\
v=e\end{subarray}}\sum_{\mathbf{i}\in\mathscr{E}_{k}(v,e)}A_{\mathbf{i}},$
$\displaystyle R_{k}=\sum_{\begin{subarray}{c}e\leqslant k\\\
v<e\end{subarray}}\sum_{\mathbf{i}\in\mathscr{E}_{k}(v,e)}A_{\mathbf{i}}$

so that naturally $\mathrm{tr}(A^{k})=T_{k}+R_{k}$. We repeat Lemmas 9.2 and
surrounding results adapted to our regime.

######  Lemma 10.2.

$\mathbf{E}[R_{k}]\leqslant d_{n}^{k}k^{k+2}/n$. Consequently, $R_{k}\to 0$ in
probability and in distribution as long as $d_{n}=n^{o(1)}$.

######  Lemma 10.3.

$\mathscr{E}_{k}(v,v)$ is empty if $v$ is not a divisor of $k$. Otherwise, if
$k=vq$, then the elements of $\mathscr{E}_{k}(v,v)$ are exactly the sequences

$(i_{1},i_{2},\dotsc,i_{v},i_{1},\dotsc,i_{v},\dotsc,i_{1},\dotsc,i_{v})$

where $i_{1},\dotsc,i_{v}$ are all distinct, and the subsequence
$\mathbf{i}^{\prime}=(i_{1},\dotsc,i_{v})$ is repeated $q$ times.

We recall the notation $S_{\ell}$:

$S_{\ell}:=\sum_{\mathbf{i}\in\mathscr{C}_{\ell}}A_{\mathbf{i}}$

where $\mathscr{C}_{\ell}$ is the set of cycles of length $\ell$ on $[n]$.
With this notation, we saw that

$T_{k}=\sum_{\ell|k}\ell S_{\ell}.$

We now show that the random variables $S_{\ell}$ are asymptotically Gaussian
independent random variables with mean and variance $d_{n}^{\ell}/\ell$, using
the method of moments — this is where the proof drifts away from the
sparse/Poisson case. To do this, we define a normalized version of the
$S_{\ell_{i}}$: we set $B_{\mathbf{i}}=A_{\mathbf{i}}-d_{n}^{\ell}/n^{\ell}$,
so that $\mathbf{E}[B_{\mathbf{i}}]=0$, and

$W_{\ell}=\frac{\sum_{\mathbf{i}\in\mathscr{C}_{\ell}}B_{\mathbf{i}}}{\sqrt{d_{n}^{\ell}/\ell}}=\frac{S_{\ell}-\mathbf{E}[S_{\ell}]}{\sqrt{d_{n}^{\ell}/\ell}}.$

The core of the proof is the following result.

######  Proposition 10.4.

We suppose that $d_{n}$ satisfies (H). For any distinct nonzero integers
$\ell_{i}$ and any integers $p_{i}$,

$\lim_{n\to\infty}\mathbf{E}\left[\prod_{i=1}^{m}W_{\ell_{i}}^{p_{i}}\right]=\prod_{i=1}^{m}\frac{p_{i}!}{2^{p_{i}/2}(p_{i}/2)!}\mathbf{1}_{p_{i}\text{
is even.}}.$ (10.4)

###### Proof of Theorem 3.1.

Let $(N_{\ell}:\ell\geqslant 1)$ be a family of independent standard Gaussian
variables. The RHS of (10.4) is nothing but

$\mathbf{E}[N_{\ell_{1}}^{p_{1}}\times\dotsb\times N_{\ell_{m}}^{p_{m}}].$

The joint convergence of the moments in (10.4) implies
$(W_{1},\dotsc,W_{k})\xrightarrow{\mathrm{law}}(N_{1},\dotsc,\sqrt{k}N_{k})$
for any $k$. Now, we have

$\frac{\mathrm{tr}(A^{k})}{\sqrt{d_{n}}^{k}}=\frac{T_{k}}{\sqrt{d_{n}}^{k}}+\frac{R_{k}}{\sqrt{d_{n}}^{k}}$

and we saw that $R_{k}\to 0$. Since $T_{k}=\sum_{\ell|k}\ell S_{\ell}$ and
$S_{\ell}=\sqrt{d^{\ell}/\ell}W_{\ell}+d^{\ell}/\ell$,

$\displaystyle\frac{T_{k}}{\sqrt{d_{n}}^{k}}-\sqrt{d_{n}}^{k}$
$\displaystyle=-\sqrt{d_{n}}^{k}+\frac{1}{\sqrt{d_{n}}^{k}}\sum_{\ell|k}(d_{n}^{\ell}+\sqrt{\ell
d_{n}^{\ell}}W_{\ell})$
$\displaystyle=-\sqrt{d_{n}}^{k}+\sum_{\ell|k}d_{n}^{\ell-k/2}+\sum_{\ell|k}\sqrt{\ell
d_{n}^{\ell-k}}W_{\ell}$
$\displaystyle=\sum_{\ell|k,\ell<k}d_{n}^{\ell-k/2}+\sum_{\ell|k,\ell<k}\sqrt{\ell
d_{n}^{\ell-k}}W_{\ell}+\sqrt{k}W_{k}.$

If $\ell$ is a divisor of $k$, it is either $k,k/2$ or smaller than $k/2$, so
the first sum is equal to $1+O(1/d_{n})=1+o(1)$ if $k$ is even and $o(1)$ if
$k$ is odd. It is easily seen that the second term goes to zero in probability
as long as $d_{n}\to\infty$: in fact, by Proposition 10.4, we have
$\mathbf{E}[W_{\ell}^{2}]\leqslant c$ for some $c$, hence if $\ell<k$,

$\mathbf{E}[(\sqrt{\ell
d_{n}^{k-\ell}}W_{\ell})^{2}]\leqslant\frac{c^{\prime}}{d_{n}}\to 0$

and the whole sum in $\ell<k$ goes to zero in probability. We thus get

$\frac{\mathrm{tr}(A^{k})}{\sqrt{d_{n}}^{k}}-\sqrt{d_{n}}^{k}=o(1)+\frac{T_{k}}{\sqrt{d_{n}}^{k}}-\sqrt{d_{n}}^{k}=o_{\mathbf{P}}(1)+\mathbf{1}_{k\text{
even}}+\sqrt{k}W_{k},$

and the claim in Theorem 3.1 follows from the joint convergence of the
$W_{k}$.

∎

###  10.4 Proof of Proposition 10.4

For all the proof, we fix the integer $m\geqslant 1$, as well as the
$\ell_{1},\dotsc,\ell_{m}$ and the powers $p_{1},\dotsc,p_{m}$; these numbers
are assumed to be nonzero integers and the $\ell_{i}$ are distinct. We will
frequently use the shorthand $\bm{\ell}=(\ell_{1},\dotsc,\ell_{m})$ and
$\bm{p}=(p_{1},\dotsc,p_{m})$.

######  Definition 10.5.

Let $\mathscr{U}_{\bm{\ell},\bm{p}}$ be the cartesian product of $p_{i}$
copies of $\mathscr{C}_{\ell_{i}}$ for each $i=1,\dotsc,m$, in other words:

$\mathscr{U}_{\bm{\ell},\bm{p}}=\bigtimes_{i=1}^{m}\bigtimes_{j=1}^{p_{i}}\mathscr{C}_{\ell_{i}}.$

A typical element of $\mathscr{U}_{\bm{\ell},\bm{p}}$ is a
$(p_{1}+\dotsc+p_{m})$-tuple of cycles with $p_{i}$ of them of length
$\ell_{i}$. We will note $\bm{c}=(\bm{c}_{i,j})$ with $i\in[m]$, $j\in[p_{i}]$
and $\bm{c}_{i,j}\in\mathscr{C}_{\ell_{i}}$. We note $v(\bm{c})$ the total
number of vertices present in the cycles of $\bm{c}$, and

$\displaystyle E(\bm{c})=\bigcup_{i\in[m]}E(\bm{c}_{i,j}:i\in[m],j\in[p_{i}])$
$\displaystyle e(\bm{c})=\\#E(\bm{c}).$

It is the set of ‘edges’ appearing in one of the $p_{1}+\dotsb+p_{m}$ cycles
appearing in $\bm{c}$; in particular, if one edge appears in multiple cycles
$\bm{c}_{i,j}$, we only count it once. Since each $\bm{c}_{i,j}$ is a cycle
and thus has the same number of vertices and edges, we have
$e(\bm{c})\leqslant M$ where

$M=M(\bm{\ell},\bm{p})=\ell_{1}p_{1}+\dotsb+\ell_{m}p_{m}.$ (10.5)

We also recall that $B_{\mathbf{i}}=A_{\mathbf{i}}-(d/\ell)^{\ell}$, for any
$\mathbf{i}\in\mathscr{E}_{\ell}$, and that

$W_{\ell}=\frac{1}{\sigma_{\ell}}\sum_{\mathbf{i}\in\mathscr{C}_{\ell}}B_{\mathbf{i}}$
(10.6)

where $\sigma_{\ell}=\sqrt{d^{\ell}/\ell}$.

######  Lemma 10.6.

For any $m\geqslant 1$ and
$\bm{\ell}=(\ell_{1},\dotsc,\ell_{m}),\bm{p}=(p_{1},\dotsc,p_{m})$, one has

$\mathbf{E}\left[\prod_{i=1}^{m}W_{\ell_{i}}^{p_{i}}\right]=\sum_{\bm{c}\in\mathscr{U}_{\bm{\ell},\bm{p}}}\mathbf{E}\left[\prod_{i=1}^{m}\prod_{j=1}^{p_{i}}\frac{B_{\bm{c}_{i,j}}}{\sigma_{\ell_{i}}}\right].$
(10.7)

###### Proof.

One only has to expand the sum defining $W_{\ell}$. ∎

Since $\bm{c}$ is a collection of cycles, it is customary that
$v(\bm{c})\leqslant e(\bm{c})$, and clearly $e(\bm{c})\leqslant M$. We
decompose the sum in (10.7) as follows:

$\mathbf{E}\left[\prod_{i=1}^{m}W_{\ell_{i}}^{p_{i}}\right]=\sum_{\begin{subarray}{c}\bm{c}\in\mathscr{U}_{\bm{\ell},\bm{p}}\\\
v(\bm{c})<e(\bm{c})\end{subarray}}\mathbf{E}\left[\prod_{i=1}^{m}\prod_{j=1}^{p_{i}}\frac{B_{\bm{c}_{i,j}}}{\sigma_{\ell_{i}}}\right]+\sum_{k=1}^{M}\sum_{\begin{subarray}{c}\bm{c}\in\mathscr{U}_{\bm{\ell},\bm{p}}\\\
v(\bm{c})=e(\bm{c})=k\end{subarray}}\mathbf{E}\left[\prod_{i=1}^{m}\prod_{j=1}^{p_{i}}\frac{B_{\bm{c}_{i,j}}}{\sigma_{\ell_{i}}}\right].$
(10.8)

Our task will now consist in finding the dominant terms in this sum. We first
start with Lemma 10.7, a rough estimate on the expectations in the above sums
that will be used everywhere after. Then, in Lemma 10.8 we prove that the sum
over $v<e$ is negligible. In Lemma 10.9 we prove that in the second sum, all
the terms with $k<M/2$ are negligible and in Lemma 10.10 we show that the
terms with $k>M/2$ are also negligible. Finally, in Lemma 10.11 we study the
limit of the only remaining term, the one for $k=M/2$.

######  Lemma 10.7.

For any $\bm{c}\in\mathscr{U}_{\bm{\ell},\bm{p}}$,

$\mathbf{E}\left[\prod_{i=1}^{m}\prod_{j=1}^{p_{i}}\frac{B_{\bm{c}_{i,j}}}{\sigma_{\ell_{i}}}\right]\leqslant
c(\bm{\ell},\bm{p})\left(\frac{d}{n}\right)^{e(\bm{c})}\frac{1}{d^{\frac{M}{2}}}$
(10.9)

where $c(\bm{\ell},\bm{p})\leqslant 2^{M}(\max\bm{\ell})^{M/2}$.

The proof is in Appendix A.

######  Lemma 10.8.

Under (H),

$\lim_{n\to\infty}\sum_{\begin{subarray}{c}\bm{c}\in\mathscr{U}_{\bm{\ell},\bm{p}}\\\
v(\bm{c})<e(\bm{c})\end{subarray}}\mathbf{E}\left[\prod_{i=1}^{m}\prod_{j=1}^{p_{i}}\frac{B_{\bm{c}_{i,j}}}{\sigma_{\ell_{i}}}\right]=0.$
(10.10)

###### Proof.

By the preceding lemma, the sum is bounded by a constant times

$\sum_{h<k\leqslant
M}\\#\\{\bm{c}\in\mathscr{U}_{\bm{\ell},\bm{p}},v(\bm{c})=h,e(\bm{c})=k\\}\times
d^{k-M/2}n^{-k}.$

By counting arguments similar to those already used before, there are
constants $c$ (depending on $h,k,\bm{\ell},\bm{p}$) such that

$\\#\\{\bm{c}\in\mathscr{U}_{\bm{\ell},\bm{p}},v(\bm{c})=h,e(\bm{c})=k\\}\leqslant
cn^{h}.$

All things together yield a bound of order $\sum_{h<k\leqslant
M}d^{k-M/2}n^{h-k}=O(d^{k-M/2}/n)$, which is $o(1)$ when $d\leqslant
n^{o(1)}$. ∎

######  Lemma 10.9.

Under (H), if $k<M/2$, then

$\lim_{n\to\infty}\sum_{\begin{subarray}{c}\bm{c}\in\mathscr{U}_{\bm{\ell},\bm{p}}\\\
v(\bm{c})=e(\bm{c})=k\end{subarray}}\mathbf{E}\left[\prod_{i=1}^{m}\prod_{j=1}^{p_{i}}\frac{B_{\bm{c}_{i,j}}}{\sigma_{\ell_{i}}}\right]=0.$
(10.11)

###### Proof.

The same proof as the preceding lemma yields a bound of order
$d^{k-M/2}n^{k-k}=d^{k-M/2}$, which is $o(1)$ when $k<M/2$. ∎

######  Lemma 10.10.

Under (H), if $k>M/2$ then

$\lim_{n\to\infty}\sum_{\begin{subarray}{c}\bm{c}\in\mathscr{U}_{\bm{\ell},\bm{p}}\\\
v(\bm{c})=e(\bm{c})=k\end{subarray}}\mathbf{E}\left[\prod_{i=1}^{m}\prod_{j=1}^{p_{i}}\frac{B_{\bm{c}_{i,j}}}{\sigma_{\ell_{i}}}\right]=0.$
(10.12)

###### Proof.

Remember that elements in $\mathscr{U}_{\bm{\ell},\bm{p}}$ are collections of
cycles. Consequently, if $v(\bm{c})=e(\bm{c})$, then $\bm{c}$ can consist only
in cycles which are vertex-disjoint, but possibly repeated multiple times. If
$k>M/2$, then all those cycles cannot be repeated, because otherwise $\bm{c}$
would contain $2k>M$ cycles. So, at least one of them is not repeated, and
disjoint from all the others, say $\bm{c}_{i,j}$. But then, $B_{\bm{c}_{i,j}}$
is independent from all the others $B_{\bm{c}_{i^{\prime},j^{\prime}}}$: the
expectation inside the sum above splits, and since $B_{\bm{c}_{i,j}}$ is
centered, it is equal to zero. Consequently, the whole sum above is actually
zero. ∎

######  Lemma 10.11.

Under (H),

$\lim_{n\to\infty}\sum_{\begin{subarray}{c}\bm{c}\in\mathscr{U}_{\bm{\ell},\bm{p}}\\\
v(\bm{c})=e(\bm{c})=M/2\end{subarray}}\mathbf{E}\left[\prod_{i=1}^{m}\prod_{j=1}^{p_{i}}\frac{B_{\bm{c}_{i,j}}}{\sigma_{\ell_{i}}}\right]=\prod_{i=1}^{m}\frac{p_{i}!}{2^{p_{i}/2}(p_{i}/2)!}\mathbf{1}_{p_{i}\text{
is even}}.$ (10.13)

###### Proof.

The proof of the preceding lemma shows that the only elements contributing to
the sum above are precisely the $\bm{c}$ consisting in $M/2$ vertex-disjoint
cycles, each one being repeated at least once; but there are $M$ elements in
$\bm{c}$, each one is actually repeated exactly twice. First of all, this is
not possible if one of the $p_{i}$ is not even, so in this case the whole sum
is zero. Let us assume that all the $p_{i}$ are even. Let $\mathscr{V}$ be the
subset of $\mathscr{U}_{\bm{\ell},\bm{p}}$ matching these constraints; we will
write its elements $\bm{c}$ as multisets,

$\bm{c}=\\{\\{\bm{c}_{1,1},\bm{c}_{1,1},\dots,\bm{c}_{1,p_{1}/2},\bm{c}_{1,p_{1}/2},\bm{c}_{2,1},\bm{c}_{2,1},\dots\\}\\}$

and the $M/2$ distinct $\bm{c}_{i,j}$ are vertex-disjoint. The expectation
inside the sum is then equal to

$\mathbf{E}\left[\prod_{i=1}^{m}\prod_{j=1}^{p_{i}/2}\frac{B_{\bm{c}_{i,j}}^{2}}{\sigma_{\ell_{i}}^{2}}\right]=\prod_{i=1}^{m}\prod_{j=1}^{p_{i}/2}\mathbf{E}\left[\frac{B_{\bm{c}_{i,j}}^{2}}{\sigma_{\ell_{i}}^{2}}\right]=\prod_{i=1}^{m}\prod_{j=1}^{p_{i}/2}\frac{(d/n)^{\ell_{i}}(1-(d/n)^{\ell_{i}})}{\sigma_{\ell_{i}}^{2}}$

where we used that the $B_{\bm{c}_{i,j}}$ are independent
$\mathrm{Bernoulli}((d/n)^{\ell_{i}})$ random variables. Now, we recall that
$\sum p_{i}\ell_{i}=M$ and $\sigma_{\ell}=d^{\ell/2}\ell^{-1/2}$, so the last
expression is

$(1+o(1))\frac{(d/n)^{M/2}}{\prod_{i=1}^{m}\prod_{j=1}^{p_{i}/2}\sigma_{\ell_{i}}^{2}}=(1+o(1))\frac{\prod\ell_{i}^{p_{i}}}{n^{M/2}}.$

We now need to count the elements in $\mathscr{V}$. The choice of the $M/2$
cycles is exactly

$\frac{(n)_{M/2}}{\prod_{i=1}^{m}\ell_{i}^{p_{i}}}$

and they must be repeated twice in $\bm{c}$, which gives

$\prod_{i=1}^{m}\frac{p_{i}!}{2^{p_{i}/2}(p_{i}/2)!}$

possibilities for any choice of the $M/2$ cycles. Putting it all together, we
get that

$\\#\mathscr{V}=(1+o(1))n^{M/2}\times\prod_{i=1}^{m}\frac{p_{i}!}{2^{p_{i}/2}(p_{i}/2)!\ell_{i}^{p_{i}}}$

and (10.13) follows. ∎

## Acknowledgements

The author thanks the three authors of [BCGZ20] as well as Yizhe Zhu and
Ludovic Stephan for various discussions on this method and comments on the
paper. The author is supported by ERC NEMO, under the European Union’s Horizon
2020 research and innovation programme grant agreement number 788851.

## References

  * [Aig07] Martin Aigner.  A course in enumeration, volume 238.  Springer Science & Business Media, 2007.
  * [BC19] Charles Bordenave and Benoît Collins.  Eigenvalues of random lifts and polynomials of random permutation matrices.  Ann. of Math. (2), 190(3):811–875, 2019.
  * [BCC+18] Charles Bordenave, Pietro Caputo, Djalil Chafaï, Konstantin Tikhomirov, et al.  On the spectral radius of a random matrix: An upper bound without fourth moment.  Annals of Probability, 46(4):2268–2286, 2018.
  * [BCGZ20] Charles Bordenave, Djalil Chafaï, and David García-Zelada.  Convergence of the spectral radius of a random matrix through its characteristic polynomial, 2020.
  * [BCN20] Charles Bordenave, Simon Coste, and Raj Rao Nadakuditi.  Detection thresholds in very sparse matrix completion.  arXiv preprint arXiv:2005.06062, 2020.
  * [BDH20] Gerandy Brito, Ioana Dumitriu, and Kameron Decker Harris.  Spectral gap in random bipartite biregular graphs and applications, 2020\.
  * [Ben74] Edward A. Bender.  Partitions of multisets.  Discrete Mathematics, 9(4):301–311, 1974.
  * [BLM13] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart.  Concentration inequalities: A nonasymptotic theory of independence.  Oxford university press, 2013.
  * [BLM15] Charles Bordenave, Marc Lelarge, and Laurent Massoulié.  Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1347–1357. IEEE, 2015.
  * [Bor15] Charles Bordenave.  A new proof of friedman’s second eigenvalue theorem and its extension to random lifts.  arXiv preprint arXiv:1502.04482, 2015.
  * [BR+19] Anirban Basak, Mark Rudelson, et al.  The circular law for sparse non-hermitian matrices.  Annals of Probability, 47(4):2359–2416, 2019.
  * [BZ20] Anirban Basak and Ofer Zeitouni.  Outliers of random perturbations of toeplitz matrices with finite symbols.  Probability Theory and Related Fields, 178(3):771–826, 2020.
  * [Cos21] Simon Coste.  The spectral gap of sparse random digraphs.  In Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, volume 57, pages 644–684. Institut Henri Poincaré, 2021.
  * [CS21] Simon Coste and Ludovic Stephan.  A simpler spectral approach for clustering in directed networks, 2021\.
  * [DG06] Persi Diaconis and Alex Gamburd.  Random matrices, magic squares and matching polynomials.  Electron. J. Combin., 11(2):Research Paper 2, 26, 2004/06.
  * [DJPP13] Ioana Dumitriu, Tobias Johnson, Soumik Pal, and Elliot Paquette.  Functional limit theorems for random regular graphs.  Probability Theory and Related Fields, 156(3-4):921–975, 2013.
  * [DS94] Persi Diaconis and Mehrdad Shahshahani.  On the eigenvalues of random matrices.  volume 31A, pages 49–62. 1994.  Studies in applied probability.
  * [FK81] Z. Füredi and J. Komlós.  The eigenvalues of random symmetric matrices.  Combinatorica, 1(3):233–241, 1981.
  * [FK14] Yan V Fyodorov and Jonathan P Keating.  Freezing transitions and extreme values: random matrix theory, and disordered landscapes.  Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 372(2007):20120503, 2014.
  * [Fri08] Joel Friedman.  A proof of Alon’s second eigenvalue conjecture and related problems.  American Mathematical Soc., 2008.
  * [JLR11] Svante Janson, Tomasz Luczak, and Andrzej Rucinski.  Random graphs, volume 45.  John Wiley & Sons, 2011.
  * [JM15] Tiefeng Jiang and Sho Matsumoto.  Moments of traces of circular beta-ensembles.  The Annals of Probability, 43(6):3279 – 3336, 2015.
  * [Kah93] Jean-Pierre Kahane.  Some random series of functions, volume 5.  Cambridge University Press, 1993.
  * [LMNR19] Fernando Lucas Metz, Izaak Neri, and Tim Rogers.  Spectral theory of sparse non-hermitian random matrices.  Journal of Physics A: Mathematical and Theoretical, 52(43):434003, Oct 2019.
  * [Nil91] Alon Nilli.  On the second eigenvalue of a graph.  Discrete Mathematics, 91(2):207–210, 1991.
  * [NPS20] Joseph Najnudel, Elliot Paquette, and Nick Simm.  Secular coefficients and the holomorphic multiplicative chaos, 2020.
  * [R+20] Guillaume Remy et al.  The fyodorov–bouchaud formula and liouville conformal field theory.  Duke Mathematical Journal, 169(1):177–211, 2020.
  * [RT19] Mark Rudelson and Konstantin Tikhomirov.  The sparse circular law under minimal assumptions.  Geometric and Functional Analysis, 29(2):561–637, 2019.
  * [RV13] Rémi Rhodes and Vincent Vargas.  Gaussian multiplicative chaos and applications: a review, 2013.
  * [S+15] Barry Simon et al.  A comprehensive course in analysis.  American Mathematical Society Providence, Rhode Island, 2015.
  * [Shi12] Tomoyuki Shirai.  Limit theorems for random analytic functions and their zeros: Dedicated to the late professor yasunori okabe (functions in number theory and their probabilistic aspects).  RIMS Kokyuroku Bessatsu, 34:335–359, 2012.
  * [Zhu20] Yizhe Zhu.  On the second eigenvalue of random bipartite biregular graphs.  arXiv preprint arXiv:2005.08103, 2020.

##  Appendix A Proof of Lemma 10.7

The proof of Lemma 10.7 is a consequence of the following application of the
FKG inequality.

######  Lemma A.1.

Let $G$ be an Erdős-Rényi digraph (loops allowed) with connectivity $p$. Let
$\mathfrak{X}_{1},\dotsc,\mathfrak{X}_{r}$ be any number of graphs on $n$
vertices and let $X_{i}=\mathbf{1}_{\mathfrak{X}_{i}\in G}$. Then,

$\mathbf{E}\left[\prod_{i=1}^{r}(X_{i}-\mathbf{E}[X_{i}])\right]\leqslant
2^{r}p^{E}$ (A.1)

where $E$ is the total number of distinct edges in $\cup\mathfrak{X}_{i}$.

###### Proof.

Note $x_{i}=\mathbf{E}[X_{i}]$. We have

$\displaystyle\mathbf{E}\left[\prod(X_{i}-x_{i})\right]\leqslant\mathbf{E}\left[\prod(X_{i}+x_{i})\right]=\sum_{I\subset[r]}\mathbf{E}\left[\prod_{i\in
I}X_{i}\right]\prod_{i\notin I}x_{i}.$ (A.2)

The random variables $X_{i}$ are increasing with the addition of edges, as
well as any of their products. The FKG inequality (see [JLR11, Section 2.2])
then states that for any $I\subset[r]$ we have

$\prod_{i\in I}x_{i}\leqslant\mathbf{E}\left[\prod_{i\in I}X_{i}\right].$

The FKG inequality also ensures that

$\mathbf{E}\left[\prod_{i\in I}X_{i}\right]\mathbf{E}\left[\prod_{i\notin
I}X_{i}\right]\leqslant\mathbf{E}\left[\prod_{i\in[r]}X_{i}\right].$

Using these two inequalities for every $I\subset[r]$ in (A.2) ends the proof,
because $\prod_{i\in[r]}X_{i}$ is a product of $E$ independent
$\mathrm{Bernoulli}(p)$ random variables and there are $2^{r}$ subsets of
$[r]$. ∎

###### Proof of Lemma 10.7.

We apply the preceding theorem to the family of graphs
$\mathfrak{X}_{i,j}=\bm{c}_{i,j}$ and to the random Erdős-Rényi digraph $G$
induced by $A$. Since $A_{\bm{c}_{i,j}}=\mathbf{1}_{\mathfrak{X}_{i,j}\subset
G}$ and $B_{\bm{c}_{i,j}}=A_{\bm{c}_{i,j}}-\mathbf{E}[A_{\bm{c}_{i,j}}]$, so

$\prod_{i=1}^{m}\prod_{j=1}^{p_{i}}B_{\bm{c}_{i,j}}=\prod_{i=1}^{m}\prod_{j=1}^{p_{i}}(X_{i,j}-\mathbf{E}[X_{i,j}]).$

There are $M$ cycles in $\bm{c}$ and $e(\bm{c})$ is the total number of
distinct edges present in any of them, so the bound in the preceding lemma is
$2^{M}(d/n)^{e(\bm{c})}$. Finally,

$\prod_{i=1}^{m}\prod_{j=1}^{p_{i}}\frac{1}{\sigma_{\ell_{i}}}=\prod_{i=1}^{m}\prod_{j=1}^{p_{i}}\sqrt{\frac{\ell_{i}}{d^{\ell_{i}}}}\leqslant(\max\bm{\ell})^{M/2}d^{-M/2}.$

∎