Introduction and Main Results
The study of the complexity in the spin glass theory is concerned about the total numbers of critical or saddle points for the disordered Hamiltonians. By analyzing their asymptotic behavior, they help to understand the geometry of the high-dimensional energy landscapes. Earlier results were pioneered in the beautiful work of Auffinger-Ben Arous-Černý [5 ] in the spherical pure p p p -spin model, whose Hamiltonian is defined as
H N G ( σ ) = 1 N ( p − 1 ) / 2 ∑ I ∈ [ N ] p G I σ I H_N^G(\sigma)=\frac{1}{N^{(p-1)/2}}\sum_{I\in[N]^p}G_I\sigma_I H N G ( σ ) = N ( p − 1 ) /2 1 I ∈ [ N ] p ∑ G I σ I
for σ ∈ N S N − 1 = { σ ∈ R N : ∥ σ ∥ 2 2 = N } \sigma\in\sqrt{N}S^{N-1}=\{\sigma\in\mathbb{R}^N:\|\sigma\|_2^2=N\} σ ∈ N S N − 1 = { σ ∈ R N : ∥ σ ∥ 2 2 = N } , where σ I : = ∏ α = 1 p σ i α \sigma_I:=\prod_{\alpha=1}^{p}\sigma_{i_\alpha} σ I := ∏ α = 1 p σ i α for I = ( i 1 , … , i p ) I=(i_1,\ldots,i_p) I = ( i 1 , … , i p ) . Denote by ∇ S \nabla_S ∇ S and ∇ S 2 \nabla_S^2 ∇ S 2 the spherical gradient and Hessian, respectively. Let
Crt G ( ( − ∞ , u ) ) : = { σ ∈ N S N − 1 : ∇ S H N G ( σ ) = 0 , H N G ( σ ) < N u } . \operatorname{Crt}_G((-\infty,u)):=\{\sigma\in\sqrt{N}S^{N-1}:\nabla_SH_N^G(\sigma)=0,\ H_N^G(\sigma)<Nu\}. Crt G (( − ∞ , u )) := { σ ∈ N S N − 1 : ∇ S H N G ( σ ) = 0 , H N G ( σ ) < N u } .
be the collection of all critical points below the energy level u ∈ R u\in\mathbb{R} u ∈ R . In [5 Theorem 2.8] , it was established an explicit formula for the logarithmic asymptotics of the expected number of critical point, i.e.,
lim N → ∞ 1 N log E [ Crt G ( ( − ∞ , u ) ) ] = { 1 2 log ( p − 1 ) + 1 2 + Ω ( 2 u E ∞ ) − u 2 2 , u ≤ − E ∞ , 1 2 log ( p − 1 ) − p − 2 4 ( p − 1 ) u 2 , − E ∞ ≤ u ≤ 0 , 1 2 log ( p − 1 ) , u ≥ 0. (1) \lim_{N\to\infty}\frac{1}{N}\log\mathbb{E}\left[\operatorname{Crt}_G((-\infty,u))\right]=
\begin{cases}
\frac{1}{2}\log(p-1)+\frac{1}{2}+\Omega\left(\frac{2u}{E_\infty}\right)-\frac{u^2}{2}, & u\le-E_\infty,\\
\frac{1}{2}\log(p-1)-\frac{p-2}{4(p-1)}u^2, & -E_\infty\le u\le0,\\
\frac{1}{2}\log(p-1), & u\ge0.
\end{cases} \tag*{(1)} N → ∞ lim N 1 log E [ Crt G (( − ∞ , u )) ] = ⎩ ⎨ ⎧ 2 1 log ( p − 1 ) + 2 1 + Ω ( E ∞ 2 u ) − 2 u 2 , 2 1 log ( p − 1 ) − 4 ( p − 1 ) p − 2 u 2 , 2 1 log ( p − 1 ) , u ≤ − E ∞ , − E ∞ ≤ u ≤ 0 , u ≥ 0. (1)
where
E ∞ = 2 p − 1 p , μ s c ( d λ ) = 4 − λ 2 2 π 1 { ∣ λ ∣ ≤ 2 } d λ (2) E_{\infty}=2\sqrt{\frac{p-1}{p}},\qquad\mu_{\mathrm{sc}}(d\lambda)=\frac{\sqrt{4-\lambda^{2}}}{2\pi}\mathbf{1}_{\{|\lambda|\leq2\}}\,d\lambda \tag*{(2)} E ∞ = 2 p p − 1 , μ sc ( d λ ) = 2 π 4 − λ 2 1 { ∣ λ ∣ ≤ 2 } d λ (2)
and Ω ( x ) \Omega(x) Ω ( x ) is the log-potential of semicircular law given by
Ω ( x ) = ∫ R log ∣ λ − x ∣ μ s c ( d λ ) = { x 2 4 − 1 2 − ∣ x ∣ 4 x 2 − 4 + log ( ∣ x ∣ + x 2 − 4 2 ) , ∣ x ∣ ≥ 2 , x 2 4 − 1 2 , ∣ x ∣ ≤ 2. (3) \Omega(x)=\int_{\mathbb{R}}\log|\lambda-x|\,\mu_{\mathrm{sc}}(d\lambda)=
\begin{cases}
\frac{x^{2}}{4}-\frac{1}{2}-\frac{|x|}{4}\sqrt{x^{2}-4}+\log\left(\frac{|x|+\sqrt{x^{2}-4}}{2}\right), & |x|\geq2,\\
\frac{x^{2}}{4}-\frac{1}{2}, & |x|\leq2.
\end{cases} \tag*{(3)} Ω ( x ) = ∫ R log ∣ λ − x ∣ μ sc ( d λ ) = { 4 x 2 − 2 1 − 4 ∣ x ∣ x 2 − 4 + log ( 2 ∣ x ∣ + x 2 − 4 ) , 4 x 2 − 2 1 , ∣ x ∣ ≥ 2 , ∣ x ∣ ≤ 2. (3)
In addition to this, the annealed complexity of saddle points was obtained in the same work [5 ] and later generalized to the mixed p p p -spin model by Auffinger-Ben Arous [4 ] . Based on these, the study of complexity has received growing attention and many results have been made available. First, the second moment calculation of Crt G ( ( − ∞ , u ) ) \operatorname{Crt}_{G}((-\infty,u)) Crt G (( − ∞ , u )) was carried out in the pure p p p -spin model by Subag [20 ] , which concluded that the quenched and annealed complexities of the critical points indeed match with each other. More sophisticated formulas for the annealed complexity were also obtained in some Gaussian fields with isotropic increments by Auffinger-Zeng [6 ] as well as with non-rotationally invariant potential by Chen-Lu-Sen [12 ] .
While the aforementioned results heavily rely on the Gaussianity of the Hamiltonians, it is a natural question to ask if the annealed complexity (1) will remain the same or not when G I G_I G I 's are not Gaussian. Let { J I } I ∈ [ N ] p , N ∈ N \{J_I\}_{I\in[N]^p,N\in\mathbb{N}} { J I } I ∈ [ N ] p , N ∈ N be a collection of independent random variables independent of G I G_I G I 's. By switching G G G with J J J , let H N J H_N^J H N J be defined in the same manner as H N G H_N^G H N G . A reasonable setting to investigate the universality of the annealed complexity is to consider the pure p p p -spin Hamiltonian associated to the interpolated disorder between G I G_I G I and J I J_I J I ,
H t ( σ ) : = 1 N ( p − 1 ) / 2 ∑ I ∈ [ N ] p ( 1 − t G I + t J I ) σ I (4) H_t(\sigma):=\frac{1}{N^{(p-1)/2}}\sum_{I\in[N]^p}\left(\sqrt{1-t}G_I+\sqrt{t}J_I\right)\sigma_I \tag*{(4)} H t ( σ ) := N ( p − 1 ) /2 1 I ∈ [ N ] p ∑ ( 1 − t G I + t J I ) σ I (4)
for 0 ≤ t ≤ 1 0\leq t\leq1 0 ≤ t ≤ 1 and investigate the corresponding number of critical points,
Crt t ( B ) : = ∣ { σ ∈ N S N − 1 ∣ H t ( σ ) ∈ N B , ∇ S H t ( σ ) = 0 } ∣ (5) \operatorname{Crt}_t(B):=\left|\left\{\sigma\in\sqrt{N}\mathbb{S}^{N-1}\mid H_t(\sigma)\in NB,\nabla_{\mathbb{S}}H_t(\sigma)=0\right\}\right| \tag*{(5)} Crt t ( B ) := { σ ∈ N S N − 1 ∣ H t ( σ ) ∈ N B , ∇ S H t ( σ ) = 0 } (5)
for all Borel set B ⊆ R B\subseteq\mathbb{R} B ⊆ R . In this paper we show that the annealed complexity does exhibit universality for all 0 < t < 1 0<t<1 0 < t < 1 if J I J_I J I 's are strictly subgaussian. Here we recall that a random variable X X X (of unit variance) is κ S G 2 \kappa_{\mathrm{SG}}^{2} κ SG 2 -subgaussian if
E [ e λ X ] ≤ e κ S G 2 λ 2 / 2 , ∀ λ ∈ R . \mathbb{E}\left[e^{\lambda X}\right]\leq e^{\kappa_{\mathrm{SG}}^{2}\lambda^{2}/2},\qquad\forall\lambda\in\mathbb{R}. E [ e λ X ] ≤ e κ SG 2 λ 2 /2 , ∀ λ ∈ R .
It is strict subgaussian if
κ S G = 1. \kappa_{\mathrm{SG}}=1. κ SG = 1.
The following is our main result.
Theorem 1.1. Let p ≥ 3 p\geq3 p ≥ 3 . Let { J I } I ∈ [ N ] p , N ∈ N \{J_I\}_{I\in[N]^p,N\in\mathbb{N}} { J I } I ∈ [ N ] p , N ∈ N be independent with zero mean and unit variance. If they satisfy (SSG), then for any 0 ≤ t < 1 0\leq t<1 0 ≤ t < 1 .
lim N → ∞ 1 N log E [ Crt t ( ( − ∞ , u ) ) ] = lim N → ∞ 1 N log E [ Crt 0 ( ( − ∞ , u ) ) ] . (6) \lim_{N\to\infty}\frac{1}{N}\log\mathbb{E}\left[\operatorname{Crt}_t((-\infty,u))\right]=\lim_{N\to\infty}\frac{1}{N}\log\mathbb{E}\left[\operatorname{Crt}_0((-\infty,u))\right]. \tag*{(6)} N → ∞ lim N 1 log E [ Crt t (( − ∞ , u )) ] = N → ∞ lim N 1 log E [ Crt 0 (( − ∞ , u )) ] . (6)
Example 1.2. Assume that J I J_I J I 's are i.i.d. symmetric Racemacher, i.e., P ( J I = ± 1 ) = 1 / 2 \mathbb{P}(J_I=\pm1)=1/2 P ( J I = ± 1 ) = 1/2 . It is centered with unit variance. Moreover, its moment generating function satisfies (SSG) since E [ e λ J ] = cosh ( λ ) ≤ e λ 2 / 2 \mathbb{E}[e^{\lambda J}]=\cosh(\lambda)\leq e^{\lambda^{2}/2} E [ e λ J ] = cosh ( λ ) ≤ e λ 2 /2 . Then the conclusion of Theorem 1.1 holds.
Example 1.3. Assume that J I J_I J I ’s are i.i.d. sampled uniformly from ( − 3 , 3 ) (-\sqrt{3},\sqrt{3}) ( − 3 , 3 ) . It is centered with unit variance. Moreover, its moment generating function satisfies (SSG) since E [ e λ J ] = sinh ( 3 λ ) / ( 3 λ ) ≤ e λ 2 / 2 \mathbb{E}[e^{\lambda J}] = \sinh(\sqrt{3}\lambda)/(\sqrt{3}\lambda) \le e^{\lambda^2/2} E [ e λ J ] = sinh ( 3 λ ) / ( 3 λ ) ≤ e λ 2 /2 . Thus, (6) holds.
Our proof of Theorem 1.1 starts with the standard Kac-Rice formula for the annealed complexity. Note that even for smooth non-Gaussian disorder, conditioning on a vanishing gradient makes the conditional law of the Hessian and the density of the gradient difficult to analyze. By the virtue of the form of the disorder 1 − t G I + t J I \sqrt{1-t}G_I+\sqrt{t}J_I 1 − t G I + t J I , it allows us to avoid this obstruction by first conditioning on J J J and then applying Kac-Rice formula to the remaining Gaussian field, for which the conditional Hessian is a deterministic matrix plus an independent GOE perturbation. We then take average over J J J and control the remaining dependence through some concentration and large-deviation estimates.
While we utilize several known estimates and results from [8 , 17 ] to implement the above approach, the main key ingredient of this paper is played by the following joint large deviation principle (LDP), which holds under the strict subgaussianity assumption (SSG). Let B ( σ ) B(\sigma) B ( σ ) stand for a semi-orthogonal matrix representing the orthogonal projection from R N \mathbb{R}^N R N onto the tangent space of N S N − 1 \sqrt{N}S^{N-1} N S N − 1 at σ \sigma σ , i.e., B ( σ ) B(\sigma) B ( σ ) satisfies
B ( σ ) T B ( σ ) = I N − 1 (7) B(\sigma)^{\mathsf{T}}B(\sigma)=I_{N-1} \tag*{(7)} B ( σ ) T B ( σ ) = I N − 1 (7)
B ( σ ) B ( σ ) T = I N − σ σ T N = : P ( σ ) , (8) B(\sigma)B(\sigma)^{\mathsf{T}}=I_N-\frac{\sigma\sigma^{\mathsf{T}}}{N}=:P(\sigma), \tag*{(8)} B ( σ ) B ( σ ) T = I N − N σ σ T =: P ( σ ) , (8)
where I N − 1 I_{N-1} I N − 1 and I N I_N I N the ( N − 1 ) (N-1) ( N − 1 ) - and N N N -dimensional identity matrices, respectively.
Theorem 1.5. Let p ≥ 3 p\ge3 p ≥ 3 . Let { J I } I ∈ [ N ] p , N ∈ N \{J_I\}_{I\in[N]^p,N\in\mathbb{N}} { J I } I ∈ [ N ] p , N ∈ N be independent with zero mean and unit variance. Assume that they satisfy (SSG). Under the product measure P J ⊗ P σ \mathbb{P}_J\otimes\mathbb{P}_\sigma P J ⊗ P σ for σ ∼ P σ : = Unif ( N S N − 1 ) \sigma\sim\mathbb{P}_\sigma:=\operatorname{Unif}(\sqrt{N}S^{N-1}) σ ∼ P σ := Unif ( N S N − 1 ) , the pair
( H N J ( σ ) N ( N − 1 ) , ∥ B ( σ ) T ∇ H N J ( σ ) ∥ 2 2 N ) (9) \left(\frac{H_N^J(\sigma)}{\sqrt{N(N-1)}},\frac{\lVert B(\sigma)^{\mathsf{T}}\nabla H_N^J(\sigma)\rVert_2^2}{N}\right) \tag*{(9)} ( N ( N − 1 ) H N J ( σ ) , N ∥ B ( σ ) T ∇ H N J ( σ ) ∥ 2 2 ) (9)
satisfies the LDP at speed N N N with the good rate function
J 2 ( a , b ) = { a 2 2 + b − p 2 p + 1 2 log ( p b ) , a ∈ R , b > 0 , ∞ , a ∈ R , b ≤ 0. \mathcal{J}_2(a,b)=
\begin{cases}
\frac{a^2}{2}+\frac{b-p}{2p}+\frac{1}{2}\log\left(\frac{p}{b}\right), & a\in\mathbb{R},\ b>0,\\
\infty, & a\in\mathbb{R},\ b\leq0.
\end{cases} J 2 ( a , b ) = { 2 a 2 + 2 p b − p + 2 1 log ( b p ) , ∞ , a ∈ R , b > 0 , a ∈ R , b ≤ 0.
Remark 1.6. Theorem 1.5 is an LDP universality result under (SSG). Interestingly, the same strict subgaussianity assumption also appears in random matrix theory. In [15 ] , Guionnet and Husson showed that the largest eigenvalue of a Wigner matrix with entries satisfying (SSG) obeys an LDP at speed N N N with the same rate function as in the Gaussian case. On the contrary, Augeri, Guionnet, and Husson [7 ] showed that this LDP universality can fail when the entries are subgaussian but not strictly subgaussian. We anticipate an analogous failure of universality for the joint LDP of the pair in (9) if (SSG) is weakened to mere subgaussianity.
Remark 1.7. In this work, we only consider the pure p p p -spin model for the clarity of exposition. Indeed, following our argument, it can be shown that Theorems 1.1 and 1.5 hold also for the mixed p p p -spin model.
Remark 1.8. Before the completion of this paper, we learned of a concurrent work by Kivimae and McKenna [19 ] . They study the same interpolated model assuming that the non-Gaussian disorders have general subexponential tails. Their main result establishes the following lower bound:
lim inf N → ∞ 1 N log E [ Crt t ( ( − ∞ , u ) ) ] ≥ lim N → ∞ 1 N log E [ Crt 0 ( ( − ∞ , u ) ) ] \liminf_{N\to\infty}\frac{1}{N}\log\mathbb{E}\left[\operatorname{Crt}_t((-\infty,u))\right]\geq\lim_{N\to\infty}\frac{1}{N}\log\mathbb{E}\left[\operatorname{Crt}_0((-\infty,u))\right] N → ∞ lim inf N 1 log E [ Crt t (( − ∞ , u )) ] ≥ N → ∞ lim N 1 log E [ Crt 0 (( − ∞ , u )) ]
and it holds true also in the mixed p p p -spin models. As discussed in the preceding remark, this suggests a potentially interesting dichotomy, analogous to those observed in [7 , 13 , 15 ] : universality may hold under strict subgaussianity, but need not hold under subgaussianity alone.
The rest of the paper is organized as follows. Section 2 introduces some notation. In Section 3, we apply the Kac-Rice formula to derive the main integral representation for the expected complexity. This computation is standard and closely follows [5 ] . Section 5 is devoted to separating the determinant of the Hessian term in the Kac-Rice formula. It relies on the technical lemmas prepared in Section 4, where we establish superexponential concentration estimates and universality results for the empirical spectral measure of the Hessian matrix. In Section 6, we study the joint moment generating function for the pair (9) , where strict subgaussianity plays a crucial role. Based on this, Section 7 carries out the proofs of the large deviation principle in Theorem 1.5 as well as the asserted universality, Theorem 1.1 .
Acknowledgements. W.-K. Chen is partly supported by NSF grants DMS-2246715 and Simons Foundation MPS-TSM-00025876; T.-L. Lu is partly supported by NSF grants DMS-2246715; both thank the National Center for Theoretical Sciences in Taiwan for their hospitality during summer 2026, where part of this research was conducted. A. Sen is partly supported by Simons Foundation MP-TSM-00002716. All authors warmly thank E. Subag, P. Kivimae, and B. McKenna for the illuminating discussions. In the proof of the upper bound in Proposition 6.3 (i), the use of the Brascamp–Lieb inequality was suggested by ChatGPT (OpenAI).
Notation
We introduce some notation that will be used for the remainder of this paper.
For a real number x x x , denote by x + = max { x , 0 } x_+=\max\{x,0\} x + = max { x , 0 } .
Let ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ and ∥ ⋅ ∥ 2 \|\cdot\|_2 ∥ ⋅ ∥ 2 denote the standard inner product and Euclidean norm on R N \mathbb{R}^N R N , respectively.
For an real-valued N × N N \times N N × N matrix A A A , denote by ∥ A ∥ F = ( ∑ i , j = 1 N A i j 2 ) 1 / 2 \|A\|_{\mathrm{F}} = \left(\sum_{i,j=1}^{N} A_{ij}^{2}\right)^{1/2} ∥ A ∥ F = ( ∑ i , j = 1 N A ij 2 ) 1/2 the Frobenius norm of A A A . Let Spec ( A ) \operatorname{Spec}(A) Spec ( A ) denote its spectrum, with eigenvalues counted according to their algebraic multiplicities, and let ∥ A ∥ o p \|A\|_{\mathrm{op}} ∥ A ∥ op denote its operator norm. When A A A is symmetric, we order its eigenvalues as λ 1 ↑ ( A ) ≤ ⋯ ≤ λ N ↑ ( A ) \lambda_1^{\uparrow}(A) \le\cdots\le\lambda_N^{\uparrow}(A) λ 1 ↑ ( A ) ≤ ⋯ ≤ λ N ↑ ( A ) and define its empirical spectral measure by μ A = N − 1 ∑ j = 1 N δ ( λ j ↑ ( A ) ) \mu_A = N^{-1}\sum_{j=1}^{N} \delta(\lambda_j^{\uparrow}(A)) μ A = N − 1 ∑ j = 1 N δ ( λ j ↑ ( A )) , where δ ( x ) \delta(x) δ ( x ) denotes the Dirac measure at x x x .
For two probability measures μ , ν \mu,\nu μ , ν on R \mathbb{R} R with finite first moments, define the bounded Lipschitz distance by
d B L ( μ , ν ) = sup ∥ f ∥ L i p ≤ 1 , ∥ f ∥ ∞ ≤ 1 ∫ R f ( x ) ( μ − ν ) ( d x ) , d_{\mathrm{BL}}(\mu,\nu) = \sup_{\|f\|_{\mathrm{Lip}}\le1,\|f\|_{\infty}\le1} \int_{\mathbb{R}} f(x)\,(\mu-\nu)(dx), d BL ( μ , ν ) = ∥ f ∥ Lip ≤ 1 , ∥ f ∥ ∞ ≤ 1 sup ∫ R f ( x ) ( μ − ν ) ( d x ) ,
where ∥ f ∥ L i p \|f\|_{\mathrm{Lip}} ∥ f ∥ Lip and ∥ f ∥ ∞ \|f\|_{\infty} ∥ f ∥ ∞ denotes the Lipschitz seminorm and supremum norm of the function f : R → R f:\mathbb{R}\to\mathbb{R} f : R → R , respectively.
We write f ( N ) = O N ( g ( N ) ) f(N) = O_N(g(N)) f ( N ) = O N ( g ( N )) if there exists an absolute constant C > 0 C > 0 C > 0 such that ∣ f ( N ) ∣ ≤ C g ( N ) |f(N)| \le Cg(N) ∣ f ( N ) ∣ ≤ C g ( N ) for all sufficiently large N N N . Similarly, f ( N ) = o N ( g ( N ) ) f(N) = o_N(g(N)) f ( N ) = o N ( g ( N )) if ∣ f ( N ) / g ( N ) ∣ → 0 |f(N)/g(N)| \to0 ∣ f ( N ) / g ( N ) ∣ → 0 as N → ∞ N \to\infty N → ∞ .
First Moment of Complexity
Recall that B ( σ ) B(\sigma) B ( σ ) is a N × ( N − 1 ) N \times(N-1) N × ( N − 1 ) semi-orthogonal matrix representing the orthogonal projection from R N \mathbb{R}^N R N onto the tangent space of N S N − 1 \sqrt{N}\mathbb{S}^{N-1} N S N − 1 at σ \sigma σ . We can then represent the spherical gradient and Hessian at σ ∈ N S N − 1 \sigma\in\sqrt{N}\mathbb{S}^{N-1} σ ∈ N S N − 1 by
∇ S H t ( σ ) = B ( σ ) T ∇ H t ( σ ) , \nabla_S H_t(\sigma) = B(\sigma)^{\mathsf{T}}\nabla H_t(\sigma), ∇ S H t ( σ ) = B ( σ ) T ∇ H t ( σ ) ,
∇ S 2 H t ( σ ) = B ( σ ) T ( ∇ 2 H t ( σ ) − p H t ( σ ) N I N ) B ( σ ) . \nabla_S^2 H_t(\sigma) = B(\sigma)^{\mathsf{T}}\left(\nabla^2 H_t(\sigma) - \frac{pH_t(\sigma)}{N}I_N\right)B(\sigma). ∇ S 2 H t ( σ ) = B ( σ ) T ( ∇ 2 H t ( σ ) − N p H t ( σ ) I N ) B ( σ ) .
where ∇ \nabla ∇ and ∇ 2 \nabla^2 ∇ 2 denoted the ordinary Euclidean gradient and Hessian. Last, recall the Gaussian orthogonal ensemble (GOE) is the centered Gaussian matrix ( g i j ) 1 ≤ i , j ≤ N (g_{ij})_{1\le i,j\le N} ( g ij ) 1 ≤ i , j ≤ N with covariance structure
E [ g i j g k ℓ ] = δ i k δ j ℓ + δ i ℓ δ j k N . \mathbb{E}[g_{ij}g_{k\ell}] = \frac{\delta_{ik}\delta_{j\ell}+\delta_{i\ell}\delta_{jk}}{N}. E [ g ij g k ℓ ] = N δ ik δ j ℓ + δ i ℓ δ j k .
Covariance Structure
Proposition 3.1 (Covariance Profile for Spherical Derivative). For any fixed σ ∈ N S N − 1 \sigma\in\sqrt{N}\mathbb{S}^{N-1} σ ∈ N S N − 1 , conditioning on J I ′ J'_I J I ′ 's, ( H t ( σ ) , ∇ S H t ( σ ) , ∇ S 2 H t ( σ ) ) (H_t(\sigma),\nabla_S H_t(\sigma),\nabla_S^2 H_t(\sigma)) ( H t ( σ ) , ∇ S H t ( σ ) , ∇ S 2 H t ( σ )) is a Gaussian field with the following means and covariances:
(i) The Hamiltonian H t ( σ ) ∼ Normal ( t H N J ( σ ) , ( 1 − t ) N ) H_t(\sigma) \sim\operatorname{Normal}(\sqrt{t}H_N^{J}(\sigma),(1-t)N) H t ( σ ) ∼ Normal ( t H N J ( σ ) , ( 1 − t ) N ) .
(ii) The gradient ∇ S H t ( σ ) ∼ Normal ( t B ( σ ) T ∇ H N J ( σ ) , ( 1 − t ) p I N − 1 ) \nabla_S H_t(\sigma) \sim\operatorname{Normal}(\sqrt{t}B(\sigma)^{\mathsf{T}}\nabla H_N^{J}(\sigma),(1-t)pI_{N-1}) ∇ S H t ( σ ) ∼ Normal ( t B ( σ ) T ∇ H N J ( σ ) , ( 1 − t ) p I N − 1 ) .
(iii) The Hessian satisfies
E [ ∇ S 2 H t ( σ ) ] = t B ( σ ) T ( ∇ 2 H N J ( σ ) − p H N J ( σ ) N I N ) B ( σ ) . \mathbb{E}[\nabla_S^2 H_t(\sigma)] = \sqrt{t}B(\sigma)^{\mathsf{T}}\left(\nabla^2 H_N^{J}(\sigma) - \frac{pH_N^{J}(\sigma)}{N}I_N\right)B(\sigma). E [ ∇ S 2 H t ( σ )] = t B ( σ ) T ( ∇ 2 H N J ( σ ) − N p H N J ( σ ) I N ) B ( σ ) . Moreover, for all i , j , k , ℓ ∈ [ N − 1 ] i,j,k,\ell\in[N-1] i , j , k , ℓ ∈ [ N − 1 ] ,
Cov ( ∇ S 2 H t ( σ ) i j , ∇ S 2 H t ( σ ) k ℓ ) = ( 1 − t ) N − 1 [ p ( p − 1 ) ( δ i k δ j ℓ + δ i ℓ δ j k ) + p 2 δ i j δ k ℓ ] . \operatorname{Cov}(\nabla_S^2 H_t(\sigma)_{ij},\nabla_S^2 H_t(\sigma)_{k\ell}) = (1-t)N^{-1}\left[p(p-1)(\delta_{ik}\delta_{j\ell}+\delta_{i\ell}\delta_{jk})+p^2\delta_{ij}\delta_{k\ell}\right]. Cov ( ∇ S 2 H t ( σ ) ij , ∇ S 2 H t ( σ ) k ℓ ) = ( 1 − t ) N − 1 [ p ( p − 1 ) ( δ ik δ j ℓ + δ i ℓ δ j k ) + p 2 δ ij δ k ℓ ] .
(iv) For all i , j , k ∈ [ N − 1 ] i,j,k \in[N-1] i , j , k ∈ [ N − 1 ] ,
Cov ( H t ( σ ) , ∇ S H t ( σ ) ) = 0 , \operatorname{Cov}(H_t(\sigma),\nabla_S H_t(\sigma))=0, Cov ( H t ( σ ) , ∇ S H t ( σ )) = 0 ,
Cov ( H t ( σ ) , ∇ S 2 H t ( σ ) ) = − ( 1 − t ) p I N − 1 , \operatorname{Cov}(H_t(\sigma),\nabla_S^2 H_t(\sigma))=-(1-t)pI_{N-1}, Cov ( H t ( σ ) , ∇ S 2 H t ( σ )) = − ( 1 − t ) p I N − 1 ,
Cov ( ( ∇ S H t ( σ ) ) i , ( ∇ S 2 H t ( σ ) ) j k ) = 0. \operatorname{Cov}((\nabla_S H_t(\sigma))_i,(\nabla_S^2 H_t(\sigma))_{jk})=0. Cov (( ∇ S H t ( σ ) ) i , ( ∇ S 2 H t ( σ ) ) j k ) = 0.
Additionally, under the conditional measure P ( ⋅ ∣ ∇ S H t ( σ ) = 0 ) \mathbb{P}(\cdot\mid\nabla_S H_t(\sigma)=0) P ( ⋅ ∣ ∇ S H t ( σ ) = 0 ) , we have the joint law
H t ( σ ) = d N ( N − 1 ) ( p − 1 ) p x N J , Z ( σ ) H_t(\sigma)\mathrel{\stackrel{d}{=}}\sqrt{\frac{N(N-1)(p-1)}{p}}x_N^{J,Z}(\sigma) H t ( σ ) = d p N ( N − 1 ) ( p − 1 ) x N J , Z ( σ )
∇ S 2 H t ( σ ) = d ( N − 1 ) p ( p − 1 ) N ( M N − 1 J , G O E ( σ ) − x N J , Z ( σ ) I N − 1 ) \nabla_S^2H_t(\sigma)\mathrel{\stackrel{d}{=}}\sqrt{\frac{(N-1)p(p-1)}{N}}\left(M_{N-1}^{J,\mathrm{GOE}}(\sigma)-x_N^{J,Z}(\sigma)I_{N-1}\right) ∇ S 2 H t ( σ ) = d N ( N − 1 ) p ( p − 1 ) ( M N − 1 J , GOE ( σ ) − x N J , Z ( σ ) I N − 1 )
where
x N J , Z ( σ ) : = p p − 1 ( t H N J ( σ ) N ( N − 1 ) + 1 − t Z N − 1 ) , (10) x_N^{J,Z}(\sigma):=\sqrt{\frac{p}{p-1}}\left(\sqrt{t}\frac{H_N^J(\sigma)}{\sqrt{N(N-1)}}+\sqrt{1-t}\frac{Z}{\sqrt{N-1}}\right), \tag*{(10)} x N J , Z ( σ ) := p − 1 p ( t N ( N − 1 ) H N J ( σ ) + 1 − t N − 1 Z ) , (10)
M N − 1 J , G O E ( σ ) : = t N N − 1 B ( σ ) T ∇ 2 H N J ( σ ) B ( σ ) p ( p − 1 ) + 1 − t ⋅ G O E N − 1 , (11) M_{N-1}^{J,\mathrm{GOE}}(\sigma):=\sqrt{t}\sqrt{\frac{N}{N-1}}\frac{B(\sigma)^{\mathsf T}\nabla^2H_N^J(\sigma)B(\sigma)}{\sqrt{p(p-1)}}+\sqrt{1-t}\cdot\mathrm{GOE}_{N-1}, \tag*{(11)} M N − 1 J , GOE ( σ ) := t N − 1 N p ( p − 1 ) B ( σ ) T ∇ 2 H N J ( σ ) B ( σ ) + 1 − t ⋅ GOE N − 1 , (11)
and Z ∼ Normal ( 0 , 1 ) Z\sim\operatorname{Normal}(0,1) Z ∼ Normal ( 0 , 1 ) .
Proof. These are straightforward computations, see [5 Lemma 3.2] .
Kac-Rice Formula
Proposition 3.2. For every Borel set S ⊆ R S\subseteq\mathbb{R} S ⊆ R and every t ∈ [ 0 , 1 ) t\in[0,1) t ∈ [ 0 , 1 ) , we have
E J , G [ Cr t ( S ) ] = e N ( 1 2 log ( p − 1 ) − 1 2 log ( 1 − t ) + 1 2 ) + o N ( N ) E σ , J , Z , G O E [ e − N t 2 p ( 1 − t ) y N J ( σ ) ∣ det ( M N − 1 J , G O E ( σ ) − x N J , Z ( σ ) I N − 1 ) ∣ ⋅ 1 { x N J , Z ( σ ) ∈ N p ( N − 1 ) ( p − 1 ) S } ] (12) \mathbb{E}_{J,G}\left[\operatorname{Cr}_t(S)\right]
=e^{N\left(\frac{1}{2}\log(p-1)-\frac{1}{2}\log(1-t)+\frac{1}{2}\right)+o_N(N)}
\mathbb{E}_{\sigma,J,Z,\mathrm{GOE}}\left[
e^{-\frac{Nt}{2p(1-t)}y_N^J(\sigma)}
\left|\det\left(M_{N-1}^{J,\mathrm{GOE}}(\sigma)-x_N^{J,Z}(\sigma)I_{N-1}\right)\right|
\cdot\mathbf{1}_{\left\{x_N^{J,Z}(\sigma)\in\sqrt{\frac{Np}{(N-1)(p-1)}S}\right\}}
\right] \tag*{(12)} E J , G [ Cr t ( S ) ] = e N ( 2 1 l o g ( p − 1 ) − 2 1 l o g ( 1 − t ) + 2 1 ) + o N ( N ) E σ , J , Z , GOE [ e − 2 p ( 1 − t ) N t y N J ( σ ) det ( M N − 1 J , GOE ( σ ) − x N J , Z ( σ ) I N − 1 ) ⋅ 1 { x N J , Z ( σ ) ∈ ( N − 1 ) ( p − 1 ) N p S } ] (12)
where
y N J ( σ ) = N − 1 ∥ B ( σ ) T ∇ H N J ( σ ) ∥ 2 (13) y_N^J(\sigma)=N^{-1}\left\|B(\sigma)^{\mathsf T}\nabla H_N^J(\sigma)\right\|^2 \tag*{(13)} y N J ( σ ) = N − 1 B ( σ ) T ∇ H N J ( σ ) 2 (13)
and the random variables σ ∼ Unif ( N S N − 1 ) \sigma\sim\operatorname{Unif}(\sqrt{N}\mathbb{S}^{N-1}) σ ∼ Unif ( N S N − 1 ) , Z ∼ Normal ( 0 , 1 ) Z\sim\operatorname{Normal}(0,1) Z ∼ Normal ( 0 , 1 ) , and G O E N − 1 \mathrm{GOE}_{N-1} GOE N − 1 are mutually independent and independent of the disorder J J J .
Proof. We ought to count the critical points via the Kac-Rice formula (see [1 Theorem 11.2.1] ). The regularity conditions are automatically satisfied since we are only applying it to the Gaussian disorder. Let d σ d\sigma d σ denote the surface measure on N S N − 1 \sqrt{N}\mathbb{S}^{N-1} N S N − 1 . Then
E J , G [ Cr t ( S ) ] = E J [ E G [ Cr t ( S ) ] ] = E J [ ∫ N S N − 1 E G [ ∣ det ∇ S 2 H t ( σ ) ∣ ⋅ 1 { H t ( σ ) ∈ N S } ∣ ∇ S H t ( σ ) = 0 ] f ∇ S H t ( σ ) ∣ J ( 0 ) d σ ] , \begin{aligned}
\mathbb{E}_{J,G}\left[\operatorname{Cr}_t(S)\right]
=\mathbb{E}_J\left[\mathbb{E}_G\left[\operatorname{Cr}_t(S)\right]\right] \\
&=\mathbb{E}_J\left[
\int_{\sqrt{N}\mathbb{S}^{N-1}}
\mathbb{E}_G\left[
\left|\det\nabla_S^2H_t(\sigma)\right|
\cdot\mathbf{1}_{\{H_t(\sigma)\in NS\}}
\mid\nabla_S H_t(\sigma)=0
\right]
f_{\nabla_S H_t(\sigma)\mid J}(0)\,d\sigma
\right],
\end{aligned} E J , G [ Cr t ( S ) ] = E J [ E G [ Cr t ( S ) ] ] = E J [ ∫ N S N − 1 E G [ det ∇ S 2 H t ( σ ) ⋅ 1 { H t ( σ ) ∈ N S } ∣ ∇ S H t ( σ ) = 0 ] f ∇ S H t ( σ ) ∣ J ( 0 ) d σ ] ,
where f ∇ S H t ( σ ) ∣ J f_{\nabla_S H_t(\sigma)\mid J} f ∇ S H t ( σ ) ∣ J denotes the conditional density of ∇ S H t ( σ ) \nabla_S H_t(\sigma) ∇ S H t ( σ ) given J J J . From this, together with the (conditional) covariance profile illustrated in Proposition 3.1 , we can conclude (12) .
Properties of the Hessian Matrix
Throughout this subsection, assume N ≥ 2 N \ge2 N ≥ 2 . For convenience, let g = { g i j } 1 ≤ i ≤ j ≤ N − 1 g = \{g_{ij}\}_{1\le i\le j\le N-1} g = { g ij } 1 ≤ i ≤ j ≤ N − 1 be independent standard Gaussian random variables, independent of J J J , and realize GOE N − 1 \operatorname{GOE}_{N-1} GOE N − 1 by setting ( GOE N − 1 ) i j = g i j / N − 1 (\operatorname{GOE}_{N-1})_{ij} = g_{ij}/\sqrt{N-1} ( GOE N − 1 ) ij = g ij / N − 1 for 1 ≤ i < j ≤ N − 1 1 \le i < j \le N-1 1 ≤ i < j ≤ N − 1 , ( GOE N − 1 ) i i = 2 g i i / N − 1 (\operatorname{GOE}_{N-1})_{ii} = \sqrt{2}g_{ii}/\sqrt{N-1} ( GOE N − 1 ) ii = 2 g ii / N − 1 , and ( GOE N − 1 ) j i = ( GOE N − 1 ) i j (\operatorname{GOE}_{N-1})_{ji} = (\operatorname{GOE}_{N-1})_{ij} ( GOE N − 1 ) j i = ( GOE N − 1 ) ij . We use the notation
M N − 1 J , g ( σ ) : = M N − 1 J , GOE ( σ ) and μ N − 1 J , g , σ : = μ M N − 1 J , g ( σ ) . (14) M_{N-1}^{J,g}(\sigma) := M_{N-1}^{J,\operatorname{GOE}}(\sigma) \quad\text{and} \quad\mu_{N-1}^{J,g,\sigma} := \mu_{M_{N-1}^{J,g}(\sigma)}. \tag*{(14)} M N − 1 J , g ( σ ) := M N − 1 J , GOE ( σ ) and μ N − 1 J , g , σ := μ M N − 1 J , g ( σ ) . (14)
The main purpose of this subsection is to study the concentration and the universality (in J J J ) of the measure μ N − 1 J , g , σ \mu_{N-1}^{J,g,\sigma} μ N − 1 J , g , σ .
Concentration of the Hessian Matrix
Lemma 4.1. For any mapping f : R → R f:\mathbb{R}\to\mathbb{R} f : R → R and σ ∈ N S N − 1 \sigma\in\sqrt{N}\mathbb{S}^{N-1} σ ∈ N S N − 1 , we define F N σ : R N p × R N ( N − 1 ) / 2 → R F_N^\sigma:\mathbb{R}^{Np}\times\mathbb{R}^{N(N-1)/2}\to\mathbb{R} F N σ : R N p × R N ( N − 1 ) /2 → R by
F N σ ( J , g ) = ∫ R f ( λ ) μ N − 1 J , g , σ ( d λ ) = 1 N − 1 Tr ( f ( M N − 1 J , g ( σ ) ) ) . F_N^\sigma(J,g)=\int_{\mathbb{R}} f(\lambda)\,\mu_{N-1}^{J,g,\sigma}(d\lambda)=\frac{1}{N-1}\operatorname{Tr}\left(f\left(M_{N-1}^{J,g}(\sigma)\right)\right). F N σ ( J , g ) = ∫ R f ( λ ) μ N − 1 J , g , σ ( d λ ) = N − 1 1 Tr ( f ( M N − 1 J , g ( σ ) ) ) . Then there exists a constant c 1 = c 1 ( p ) > 0 c_1=c_1(p)>0 c 1 = c 1 ( p ) > 0 such that for all N ≥ 2 N\ge2 N ≥ 2 ,
sup σ ∈ N S N − 1 ∥ F N σ ∥ Lip ≤ c 1 ∥ f ∥ Lip N , (15) \sup_{\sigma\in\sqrt{N}\mathbb{S}^{N-1}}\left\|F_N^\sigma\right\|_{\operatorname{Lip}}\le\frac{c_1\left\|f\right\|_{\operatorname{Lip}}}{N}, \tag*{(15)} σ ∈ N S N − 1 sup ∥ F N σ ∥ Lip ≤ N c 1 ∥ f ∥ Lip , (15) where the supremum is over σ ∈ N S N − 1 \sigma\in\sqrt{N}\mathbb{S}^{N-1} σ ∈ N S N − 1 .
Proof. For all pairs ( J , g ) , ( J ′ , g ′ ) ∈ R N p × R N ( N − 1 ) / 2 (J,g),(J',g')\in\mathbb{R}^{Np}\times\mathbb{R}^{N(N-1)/2} ( J , g ) , ( J ′ , g ′ ) ∈ R N p × R N ( N − 1 ) /2 ,
∣ F N σ ( J , g ) − F N σ ( J ′ , g ′ ) ∣ = 1 N − 1 ∣ ∑ j = 1 N − 1 ( f ( λ j ↑ ( M N − 1 J , g ( σ ) ) ) − f ( λ j ↑ ( M N − 1 J ′ , g ′ ( σ ) ) ) ) ∣ ≤ ∥ f ∥ Lip N − 1 ∑ j = 1 N − 1 ∣ λ j ↑ ( M N − 1 J , g ( σ ) ) − λ j ↑ ( M N − 1 J ′ , g ′ ( σ ) ) ∣ ≤ ∥ f ∥ Lip N − 1 ∑ j = 1 N − 1 ∣ λ j ↑ ( M N − 1 J , g ( σ ) ) − λ j ↑ ( M N − 1 J ′ , g ′ ( σ ) ) ∣ 2 (16) \begin{aligned}
\left|F_N^\sigma(J,g)-F_N^\sigma(J',g')\right|
&=\frac{1}{N-1}\left|\sum_{j=1}^{N-1}\left(f\left(\lambda_j^\uparrow\left(M_{N-1}^{J,g}(\sigma)\right)\right)-f\left(\lambda_j^\uparrow\left(M_{N-1}^{J',g'}(\sigma)\right)\right)\right)\right| \\
&\le\frac{\left\|f\right\|_{\operatorname{Lip}}}{N-1}\sum_{j=1}^{N-1}\left|\lambda_j^\uparrow\left(M_{N-1}^{J,g}(\sigma)\right)-\lambda_j^\uparrow\left(M_{N-1}^{J',g'}(\sigma)\right)\right| \\
&\le\frac{\left\|f\right\|_{\operatorname{Lip}}}{\sqrt{N-1}}\sqrt{\sum_{j=1}^{N-1}\left|\lambda_j^\uparrow\left(M_{N-1}^{J,g}(\sigma)\right)-\lambda_j^\uparrow\left(M_{N-1}^{J',g'}(\sigma)\right)\right|^2} \tag*{(16)}
\end{aligned} ∣ F N σ ( J , g ) − F N σ ( J ′ , g ′ ) ∣ = N − 1 1 j = 1 ∑ N − 1 ( f ( λ j ↑ ( M N − 1 J , g ( σ ) ) ) − f ( λ j ↑ ( M N − 1 J ′ , g ′ ( σ ) ) ) ) ≤ N − 1 ∥ f ∥ Lip j = 1 ∑ N − 1 λ j ↑ ( M N − 1 J , g ( σ ) ) − λ j ↑ ( M N − 1 J ′ , g ′ ( σ ) ) ≤ N − 1 ∥ f ∥ Lip j = 1 ∑ N − 1 λ j ↑ ( M N − 1 J , g ( σ ) ) − λ j ↑ ( M N − 1 J ′ , g ′ ( σ ) ) 2 (16)
≤ ∥ f ∥ Lip N − 1 ∥ M N − 1 J , g ( σ ) − M N − 1 J ′ , g ′ ( σ ) ∥ F , (17) \le\frac{\left\|f\right\|_{\operatorname{Lip}}}{\sqrt{N-1}}\left\|M_{N-1}^{J,g}(\sigma)-M_{N-1}^{J',g'}(\sigma)\right\|_{\mathrm{F}}, \tag*{(17)} ≤ N − 1 ∥ f ∥ Lip M N − 1 J , g ( σ ) − M N − 1 J ′ , g ′ ( σ ) F , (17)
where (4.3) holds by the Cauchy-Schwarz inequality and (4.4) holds by the Hoffman-Wielandt inequality (see [3 Lemma 2.1.19] ). For the Hessian term in M N − 1 J , g ( σ ) M_{N-1}^{J,g}(\sigma) M N − 1 J , g ( σ ) , we have
∥ t N N − 1 B ( σ ) T ∇ 2 H N J ( σ ) B ( σ ) p ( p − 1 ) − t N N − 1 B ( σ ) T ∇ 2 H N J ′ ( σ ) B ( σ ) p ( p − 1 ) ∥ F 2 = t N p ( p − 1 ) ( N − 1 ) ∥ B ( σ ) T ( ∇ 2 H N J ( σ ) − ∇ 2 H N J ′ ( σ ) ) B ( σ ) ∥ F 2 ≤ N p ( p − 1 ) ( N − 1 ) ∥ ∇ 2 H N J ( σ ) − ∇ 2 H N J ′ ( σ ) ∥ F 2 ≤ 2 p ( p − 1 ) ∑ j , k = 1 N [ 1 N ( p − 1 ) / 2 ∑ I ∈ [ N ] p ( J I − J I ′ ) ∂ 2 σ I ∂ σ j ∂ σ k ] 2 ≤ 2 p ( p − 1 ) ∑ j , k = 1 N 1 N p − 1 [ ∑ I ∈ [ N ] p ( J I − J I ′ ) 2 1 { j , k ∈ I } ] [ ∑ I ∈ [ N ] p ( ∂ 2 σ I ∂ σ j ∂ σ k ) 2 ] (18) \begin{aligned}
\left\|\sqrt{t}\sqrt{\frac{N}{N-1}}\frac{B(\sigma)^{\mathsf{T}}\nabla^2H_N^J(\sigma)B(\sigma)}{\sqrt{p(p-1)}}-\sqrt{t}\sqrt{\frac{N}{N-1}}\frac{B(\sigma)^{\mathsf{T}}\nabla^2H_N^{J'}(\sigma)B(\sigma)}{\sqrt{p(p-1)}}\right\|_{\mathrm{F}}^2 \\
&=\frac{tN}{p(p-1)(N-1)}\left\|B(\sigma)^{\mathsf{T}}\left(\nabla^2H_N^J(\sigma)-\nabla^2H_N^{J'}(\sigma)\right)B(\sigma)\right\|_{\mathrm{F}}^2 \\
&\le\frac{N}{p(p-1)(N-1)}\left\|\nabla^2H_N^J(\sigma)-\nabla^2H_N^{J'}(\sigma)\right\|_{\mathrm{F}}^2 \\
&\le\frac{2}{p(p-1)}\sum_{j,k=1}^{N}\left[\frac{1}{N^{(p-1)/2}}\sum_{I\in[N]^p}(J_I-J'_I)\frac{\partial^2\sigma_I}{\partial\sigma_j\partial\sigma_k}\right]^2 \\
&\le\frac{2}{p(p-1)}\sum_{j,k=1}^{N}\frac{1}{N^{p-1}}\left[\sum_{I\in[N]^p}(J_I-J'_I)^2\mathbf{1}_{\{j,k\in I\}}\right]\left[\sum_{I\in[N]^p}\left(\frac{\partial^2\sigma_I}{\partial\sigma_j\partial\sigma_k}\right)^2\right] \tag*{(18)}
\end{aligned} t N − 1 N p ( p − 1 ) B ( σ ) T ∇ 2 H N J ( σ ) B ( σ ) − t N − 1 N p ( p − 1 ) B ( σ ) T ∇ 2 H N J ′ ( σ ) B ( σ ) F 2 = p ( p − 1 ) ( N − 1 ) tN B ( σ ) T ( ∇ 2 H N J ( σ ) − ∇ 2 H N J ′ ( σ ) ) B ( σ ) F 2 ≤ p ( p − 1 ) ( N − 1 ) N ∇ 2 H N J ( σ ) − ∇ 2 H N J ′ ( σ ) F 2 ≤ p ( p − 1 ) 2 j , k = 1 ∑ N N ( p − 1 ) /2 1 I ∈ [ N ] p ∑ ( J I − J I ′ ) ∂ σ j ∂ σ k ∂ 2 σ I 2 ≤ p ( p − 1 ) 2 j , k = 1 ∑ N N p − 1 1 I ∈ [ N ] p ∑ ( J I − J I ′ ) 2 1 { j , k ∈ I } I ∈ [ N ] p ∑ ( ∂ σ j ∂ σ k ∂ 2 σ I ) 2 (18)
≤ 2 p ( p − 1 ) ∑ j , k = 1 N 1 N p − 1 [ ∑ I ∈ [ N ] p ( J I − J I ′ ) 2 1 { j , k ∈ I } ] ( p 2 ( p − 1 ) 2 ∑ I ′ ∈ [ N ] p − 2 σ I ′ 2 ) (19) \le\frac{2}{p(p-1)}\sum_{j,k=1}^{N}\frac{1}{N^{p-1}}\left[\sum_{I\in[N]^p}(J_I-J'_I)^2\mathbf{1}_{\{j,k\in I\}}\right]\left(p^2(p-1)^2\sum_{I'\in[N]^{p-2}}\sigma_{I'}^2\right) \tag*{(19)} ≤ p ( p − 1 ) 2 j , k = 1 ∑ N N p − 1 1 I ∈ [ N ] p ∑ ( J I − J I ′ ) 2 1 { j , k ∈ I } p 2 ( p − 1 ) 2 I ′ ∈ [ N ] p − 2 ∑ σ I ′ 2 (19)
= 2 p ( p − 1 ) N ∑ I ∈ [ N ] p ( J I − J I ′ ) 2 ∑ j , k = 1 N 1 { j , k ∈ I } (20) = \frac{2p(p-1)}{N}\sum_{I\in[N]^p}(J_I-J'_I)^2\sum_{j,k=1}^{N}\mathbf{1}_{\{j,k\in I\}} \tag*{(20)} = N 2 p ( p − 1 ) I ∈ [ N ] p ∑ ( J I − J I ′ ) 2 j , k = 1 ∑ N 1 { j , k ∈ I } (20)
≤ 2 p 3 ( p − 1 ) N ∥ J − J ′ ∥ 2 2 , (21) \le\frac{2p^3(p-1)}{N}\lVert J-J'\rVert_2^2, \tag*{(21)} ≤ N 2 p 3 ( p − 1 ) ∥ J − J ′ ∥ 2 2 , (21)
where both (18) and (19) holds by the Cauchy–Schwarz inequality; and (20) holds since ∥ σ ∥ 2 2 = N \lVert\sigma\rVert_2^2=N ∥ σ ∥ 2 2 = N . For the GOE term in M N − 1 J , g ( σ ) M_{N-1}^{J,g}(\sigma) M N − 1 J , g ( σ ) , we have
∥ 1 − t GOE N − 1 − 1 − t GOE N − 1 ′ ∥ F ≤ 2 ( 1 − t ) N − 1 ∑ 1 ≤ i ≤ j ≤ N ( g i j − g i j ′ ) 2 ≤ 2 ∥ g − g ′ ∥ 2 N − 1 . (22) \left\lVert\sqrt{1-t}\operatorname{GOE}_{N-1}-\sqrt{1-t}\operatorname{GOE}'_{N-1}\right\rVert_{\mathrm{F}}
\le\sqrt{\frac{2(1-t)}{N-1}\sum_{1\le i\le j\le N}(g_{ij}-g'_{ij})^2}
\le\frac{2\lVert g-g'\rVert_2}{\sqrt{N-1}}. \tag*{(22)} 1 − t GOE N − 1 − 1 − t GOE N − 1 ′ F ≤ N − 1 2 ( 1 − t ) 1 ≤ i ≤ j ≤ N ∑ ( g ij − g ij ′ ) 2 ≤ N − 1 2 ∥ g − g ′ ∥ 2 . (22)
We see that (15) follows directly from (17) , (21) , and (22) .
For η > 0 \eta>0 η > 0 and K > 0 K>0 K > 0 , define the function
log η ( x ) = log ∣ x + i η ∣ = 1 2 log ( x 2 + η 2 ) and log η K ( x ) = min { log η ( x ) , log η ( K ) } . \log_\eta(x)=\log\lvert x+i\eta\rvert=\frac{1}{2}\log(x^2+\eta^2)
\quad\text{and}\quad
\log_\eta^K(x)=\min\{\log_\eta(x),\log_\eta(K)\}. log η ( x ) = log ∣ x + i η ∣ = 2 1 log ( x 2 + η 2 ) and log η K ( x ) = min { log η ( x ) , log η ( K )} .
Note that log η ( x ) ≥ log ∣ x ∣ \log_\eta(x)\ge\log\lvert x\rvert log η ( x ) ≥ log ∣ x ∣ and log η ( x ) ≥ log η K ( x ) \log_\eta(x)\ge\log_\eta^K(x) log η ( x ) ≥ log η K ( x ) for all x ∈ R x\in\mathbb{R} x ∈ R . Moreover, both functions log η ( ⋅ ) \log_\eta(\cdot) log η ( ⋅ ) and log η K ( ⋅ ) \log_\eta^K(\cdot) log η K ( ⋅ ) are ( 2 η ) − 1 (2\eta)^{-1} ( 2 η ) − 1 -Lipschitz. Additionally, for all x ∈ R x\in\mathbb{R} x ∈ R , consider the random variable
W η , N J , g ( σ , x ) = ∫ R log η ( λ − x ) μ N − 1 J , g , σ ( d λ ) = 1 N − 1 Tr [ log η ( M N − 1 J , g ( σ ) − x I N − 1 ) ] . W_{\eta,N}^{J,g}(\sigma,x)=\int_{\mathbb{R}}\log_\eta(\lambda-x)\,\mu_{N-1}^{J,g,\sigma}(d\lambda)=\frac{1}{N-1}\operatorname{Tr}\left[\log_\eta\left(M_{N-1}^{J,g}(\sigma)-xI_{N-1}\right)\right]. W η , N J , g ( σ , x ) = ∫ R log η ( λ − x ) μ N − 1 J , g , σ ( d λ ) = N − 1 1 Tr [ log η ( M N − 1 J , g ( σ ) − x I N − 1 ) ] .
Lemma 4.2. Suppose { J I } I ∈ [ N ] p , N ∈ N \{J_I\}_{I\in[N]^p,N\in\mathbb{N}} { J I } I ∈ [ N ] p , N ∈ N satisfies (SG) with uniform κ S G \kappa_{\mathrm{SG}} κ SG , then there exists a constant c 2 = c 2 ( κ S G , p ) > 0 c_2=c_2(\kappa_{\mathrm{SG}},p)>0 c 2 = c 2 ( κ SG , p ) > 0 such that for any h ≥ 0 h\ge0 h ≥ 0 ,
sup σ , x P J , g ( ∣ W η , N J , g ( σ , x ) − E J , g W η , N J , g ( σ , x ) ∣ ≥ h ) ≤ c 2 − 1 exp ( − c 2 η 2 N 2 h 2 log N ) (23) \sup_{\sigma,x}\mathbb{P}_{J,g}\left(\left\lvert W_{\eta,N}^{J,g}(\sigma,x)-\mathbb{E}_{J,g}W_{\eta,N}^{J,g}(\sigma,x)\right\rvert\ge h\right)\le c_2^{-1}\exp\left(-\frac{c_2\eta^2N^2h^2}{\log N}\right) \tag*{(23)} σ , x sup P J , g ( W η , N J , g ( σ , x ) − E J , g W η , N J , g ( σ , x ) ≥ h ) ≤ c 2 − 1 exp ( − log N c 2 η 2 N 2 h 2 ) (23)
and for any N ≥ 2 N\ge2 N ≥ 2 and λ > 0 \lambda>0 λ > 0 ,
sup σ , x E J , g [ exp ( λ ( W η , N J , g ( σ , x ) − E J , g W η , N J , g ( σ , x ) ) ) ] ≤ c 2 − 1 exp ( λ 2 log N c 2 η 2 N 2 ) , (24) \sup_{\sigma,x}\mathbb{E}_{J,g}\left[\exp\left(\lambda\left(W_{\eta,N}^{J,g}(\sigma,x)-\mathbb{E}_{J,g}W_{\eta,N}^{J,g}(\sigma,x)\right)\right)\right]\le c_2^{-1}\exp\left(\frac{\lambda^2\log N}{c_2\eta^2N^2}\right), \tag*{(24)} σ , x sup E J , g [ exp ( λ ( W η , N J , g ( σ , x ) − E J , g W η , N J , g ( σ , x ) ) ) ] ≤ c 2 − 1 exp ( c 2 η 2 N 2 λ 2 log N ) , (24)
where the supremum is over σ ∈ N S N − 1 \sigma\in\sqrt{N}S^{N-1} σ ∈ N S N − 1 and x ∈ R x\in\mathbb{R} x ∈ R .
Proof. (24) follows from (23) directly by enlarging the constant c 2 c_2 c 2 if necessary. We introduce the following auxiliary functions:
log η 1 ( λ ) = { − λ 2 η − 1 2 + log η ( η ) , λ ≤ − η , log η ( λ ) , − η ≤ λ ≤ η , λ 2 η − 1 2 + log η ( η ) , λ ≥ η . \log_\eta^1(\lambda)=
\begin{cases}
-\dfrac{\lambda}{2\eta}-\dfrac{1}{2}+\log_\eta(\eta), & \lambda\le-\eta,\\
\log_\eta(\lambda), & -\eta\le\lambda\le\eta,\\
\dfrac{\lambda}{2\eta}-\dfrac{1}{2}+\log_\eta(\eta), & \lambda\ge\eta.
\end{cases} log η 1 ( λ ) = ⎩ ⎨ ⎧ − 2 η λ − 2 1 + log η ( η ) , log η ( λ ) , 2 η λ − 2 1 + log η ( η ) , λ ≤ − η , − η ≤ λ ≤ η , λ ≥ η .
log η 2 ( λ ) = { log η ( λ ) + 1 2 − log η ( η ) , λ ≤ − η , − λ 2 η , λ ≥ − η , \log_{\eta}^{2}(\lambda)=
\begin{cases}
\log_{\eta}(\lambda)+\frac{1}{2}-\log_{\eta}(\eta), & \lambda\leq-\eta,\\
-\frac{\lambda}{2\eta}, & \lambda\geq-\eta,
\end{cases} log η 2 ( λ ) = { log η ( λ ) + 2 1 − log η ( η ) , − 2 η λ , λ ≤ − η , λ ≥ − η ,
log η 3 ( λ ) = { λ 2 η , λ ≤ η , log η ( λ ) + 1 2 − log η ( η ) , λ ≥ η . \log_{\eta}^{3}(\lambda)=
\begin{cases}
\frac{\lambda}{2\eta}, & \lambda\leq\eta,\\
\log_{\eta}(\lambda)+\frac{1}{2}-\log_{\eta}(\eta), & \lambda\geq\eta.
\end{cases} log η 3 ( λ ) = { 2 η λ , log η ( λ ) + 2 1 − log η ( η ) , λ ≤ η , λ ≥ η .
By definition, log η ( λ ) = log η 1 ( λ ) + log η 2 ( λ ) + log η 3 ( λ ) \log_{\eta}(\lambda)=\log_{\eta}^{1}(\lambda)+\log_{\eta}^{2}(\lambda)+\log_{\eta}^{3}(\lambda) log η ( λ ) = log η 1 ( λ ) + log η 2 ( λ ) + log η 3 ( λ ) for all λ ∈ R \lambda\in\mathbb{R} λ ∈ R and η > 0 \eta>0 η > 0 ; log η 1 ( λ ) \log_{\eta}^{1}(\lambda) log η 1 ( λ ) , − log η 2 ( λ ) -\log_{\eta}^{2}(\lambda) − log η 2 ( λ ) , and − log η 3 ( λ ) -\log_{\eta}^{3}(\lambda) − log η 3 ( λ ) are convex; and ∥ log η 1 ( ⋅ ) ∥ L i p \lVert\log_{\eta}^{1}(\cdot)\rVert_{\mathrm{Lip}} ∥ log η 1 ( ⋅ ) ∥ Lip , ∥ log η 2 ( ⋅ ) ∥ L i p \lVert\log_{\eta}^{2}(\cdot)\rVert_{\mathrm{Lip}} ∥ log η 2 ( ⋅ ) ∥ Lip , ∥ log η 3 ( ⋅ ) ∥ L i p ≤ ( 2 η ) − 1 \lVert\log_{\eta}^{3}(\cdot)\rVert_{\mathrm{Lip}}\leq(2\eta)^{-1} ∥ log η 3 ( ⋅ ) ∥ Lip ≤ ( 2 η ) − 1 . For i = 1 , 2 , 3 i=1,2,3 i = 1 , 2 , 3 , set
W i , η , N J , g ( σ , x ) = ( − 1 ) 1 { i ≠ 1 } ∫ R log η i ( λ − x ) μ N − 1 J , g , σ ( d λ ) . W_{i,\eta,N}^{J,g}(\sigma,x)=(-1)^{\mathbb{1}_{\{i\neq1\}}}\int_{\mathbb{R}}\log_{\eta}^{i}(\lambda-x)\,\mu_{N-1}^{J,g,\sigma}(\mathrm{d}\lambda). W i , η , N J , g ( σ , x ) = ( − 1 ) 1 { i = 1 } ∫ R log η i ( λ − x ) μ N − 1 J , g , σ ( d λ ) .
Since the mapping ( J , g ) ↦ M N − 1 J , g ( σ ) (J,g)\mapsto M_{N-1}^{J,g}(\sigma) ( J , g ) ↦ M N − 1 J , g ( σ ) is affine and λ ↦ ( − 1 ) 1 { i ≠ 1 } log η i ( λ − x ) \lambda\mapsto(-1)^{\mathbb{1}_{\{i\neq1\}}}\log_{\eta}^{i}(\lambda-x) λ ↦ ( − 1 ) 1 { i = 1 } log η i ( λ − x ) is convex with Lipschitz constant ≤ ( 2 η ) − 1 \leq(2\eta)^{-1} ≤ ( 2 η ) − 1 (for i = 1 , 2 , 3 i=1,2,3 i = 1 , 2 , 3 ), we have from Klein’s lemma [16 Lemma 1.2] and Lemma 4.1 that ( J , g ) ↦ W i , η , N J , g ( σ , x ) (J,g)\mapsto W_{i,\eta,N}^{J,g}(\sigma,x) ( J , g ) ↦ W i , η , N J , g ( σ , x ) is convex and ( c 1 / 2 η N ) (c_{1}/2\eta N) ( c 1 /2 η N ) -Lipschitz (uniformly over deterministic realization of g ∈ R N ( N − 1 ) / 2 g\in\mathbb{R}^{N(N-1)/2} g ∈ R N ( N − 1 ) /2 , σ ∈ N S N − 1 \sigma\in\sqrt{N}S^{N-1} σ ∈ N S N − 1 , and x ∈ R x\in\mathbb{R} x ∈ R ). Therefore, from [13 Proposition A.1] , there exists an absolute constant c > 0 c>0 c > 0 such that
P J , g ( ∣ W η , N J , g ( σ , x ) − E J , g [ W η , N J , g ( σ , x ) ] ∣ ≥ h ) ≤ ∑ i = 1 3 P J , g ( ∣ W i , η , N J , g ( σ , x ) − E J , g [ W i , η , N J , g ( σ , x ) ] ∣ ≥ h 3 ) \mathbb{P}_{J,g}\left(\left|W_{\eta,N}^{J,g}(\sigma,x)-\mathbb{E}_{J,g}[W_{\eta,N}^{J,g}(\sigma,x)]\right|\geq h\right)
\leq\sum_{i=1}^{3}\mathbb{P}_{J,g}\left(\left|W_{i,\eta,N}^{J,g}(\sigma,x)-\mathbb{E}_{J,g}[W_{i,\eta,N}^{J,g}(\sigma,x)]\right|\geq\frac{h}{3}\right) P J , g ( W η , N J , g ( σ , x ) − E J , g [ W η , N J , g ( σ , x )] ≥ h ) ≤ i = 1 ∑ 3 P J , g ( W i , η , N J , g ( σ , x ) − E J , g [ W i , η , N J , g ( σ , x )] ≥ 3 h )
≤ 6 exp ( − 4 c η 2 N 2 h 2 9 c 1 2 max { κ S G , 2 } log ( N p + N 2 ) ) . (25) \leq6\exp\left(-\frac{4c\eta^{2}N^{2}h^{2}}{9c_{1}^{2}\max\{\kappa_{\mathrm{SG}},2\}\log(N^{p}+N^{2})}\right). \tag*{(25)} ≤ 6 exp ( − 9 c 1 2 max { κ SG , 2 } log ( N p + N 2 ) 4 c η 2 N 2 h 2 ) . (25)
for all h ≥ 0 h\geq0 h ≥ 0 . The desired inequality (23) then follows by (25) .
Lemma 4.3. Suppose { J I } I ∈ [ N ] p , N ∈ N \{J_I\}_{I\in[N]^p,N\in\mathbb{N}} { J I } I ∈ [ N ] p , N ∈ N satisfies (SG) with uniform κ S G \kappa_{\mathrm{SG}} κ SG . Then, the following statements hold uniformly over σ ∈ N S N − 1 \sigma\in\sqrt{N}S^{N-1} σ ∈ N S N − 1 .
(i) Recall x N J , Z ( σ ) x_N^{J,Z}(\sigma) x N J , Z ( σ ) from (10) . There exists c 3 = c 3 ( κ S G , p ) > 0 c_3=c_3(\kappa_{\mathrm{SG}},p)>0 c 3 = c 3 ( κ SG , p ) > 0 such that
sup σ P J , Z ( ∣ x N J , Z ( σ ) ∣ ≥ h ) ≤ 2 e − c 3 N h 2 (26) \sup_{\sigma}\mathbb{P}_{J,Z}\left(\left|x_N^{J,Z}(\sigma)\right|\geq h\right)\leq2e^{-c_3Nh^2} \tag*{(26)} σ sup P J , Z ( x N J , Z ( σ ) ≥ h ) ≤ 2 e − c 3 N h 2 (26) for all h > 0 h>0 h > 0 .
(ii) Recall M N − 1 J , g ( σ ) M_{N-1}^{J,g}(\sigma) M N − 1 J , g ( σ ) from (11) . For all C > 0 C>0 C > 0 , there exists c 4 = c 4 ( κ S G , p , C ) > 0 c_4=c_4(\kappa_{\mathrm{SG}},p,C)>0 c 4 = c 4 ( κ SG , p , C ) > 0 such that
sup N ≥ 2 sup σ , k ≤ C N E J , g [ ∥ M N − 1 J , g ( σ ) ∥ o p k ] 1 / k ≤ c 4 . (27) \sup_{N\geq2}\sup_{\sigma,k\leq CN}\mathbb{E}_{J,g}\left[\left\|M_{N-1}^{J,g}(\sigma)\right\|_{\mathrm{op}}^{k}\right]^{1/k}\leq c_4. \tag*{(27)} N ≥ 2 sup σ , k ≤ C N sup E J , g [ M N − 1 J , g ( σ ) op k ] 1/ k ≤ c 4 . (27) (iii) There exists c 5 = c 5 ( κ S G , p ) > 0 c_5=c_5(\kappa_{\mathrm{SG}},p)>0 c 5 = c 5 ( κ SG , p ) > 0 such that
sup N ≥ 2 sup σ E J , g , Z [ ∣ det ( M N − 1 J , g ( σ ) − x N J , Z ( σ ) I N − 1 ) ∣ 2 ] 1 / 2 ≤ e c 5 N . (28) \sup_{N\geq2}\sup_{\sigma}\mathbb{E}_{J,g,Z}\left[\left|\det\left(M_{N-1}^{J,g}(\sigma)-x_N^{J,Z}(\sigma)I_{N-1}\right)\right|^{2}\right]^{1/2}\leq e^{c_5N}. \tag*{(28)} N ≥ 2 sup σ sup E J , g , Z [ det ( M N − 1 J , g ( σ ) − x N J , Z ( σ ) I N − 1 ) 2 ] 1/2 ≤ e c 5 N . (28)
Proof. (26) holds directly from Markov’s inequality and (SG):
P J , Z ( x N J , Z ( σ ) ≥ h ) ≤ e − λ h E J , Z [ e λ x N J , Z ( σ ) ] = e − λ h E J , Z [ exp ( λ p p − 1 ( t N ( N − 1 ) ∑ I ∈ [ N ] p σ I N ( p − 1 ) / 2 J I + 1 − t N − 1 Z ) ) ] ≤ exp [ − λ h + max { κ S G 2 , 1 } λ 2 p 2 ( p − 1 ) ( 1 N ( N − 1 ) ∑ I ∈ [ N ] p σ I 2 N p − 1 + 1 N − 1 ) ] = exp ( − λ h + max { κ S G 2 , 1 } λ 2 p ( p − 1 ) ( N − 1 ) ) \begin{aligned}
\mathbb{P}_{J,Z}\left(x_N^{J,Z}(\sigma)\geq h\right)\leq e^{-\lambda h}\mathbb{E}_{J,Z}\left[e^{\lambda x_N^{J,Z}(\sigma)}\right] \\
&=e^{-\lambda h}\mathbb{E}_{J,Z}\left[\exp\left(\lambda\sqrt{\frac{p}{p-1}}\left(\sqrt{\frac{t}{N(N-1)}}\sum_{I\in[N]^p}\frac{\sigma_I}{N^{(p-1)/2}}J_I+\sqrt{\frac{1-t}{N-1}}Z\right)\right)\right] \\
&\le\exp\left[-\lambda h+\frac{\max\{\kappa_{\mathrm{SG}}^2,1\}\lambda^2p}{2(p-1)}\left(\frac{1}{N(N-1)}\sum_{I\in[N]_p}\frac{\sigma_I^2}{N^{p-1}}+\frac{1}{N-1}\right)\right] \\
&=\exp\left(-\lambda h+\frac{\max\{\kappa_{\mathrm{SG}}^2,1\}\lambda^2p}{(p-1)(N-1)}\right)
\end{aligned} P J , Z ( x N J , Z ( σ ) ≥ h ) ≤ e − λh E J , Z [ e λ x N J , Z ( σ ) ] = e − λh E J , Z exp λ p − 1 p N ( N − 1 ) t I ∈ [ N ] p ∑ N ( p − 1 ) /2 σ I J I + N − 1 1 − t Z ≤ exp − λh + 2 ( p − 1 ) max { κ SG 2 , 1 } λ 2 p N ( N − 1 ) 1 I ∈ [ N ] p ∑ N p − 1 σ I 2 + N − 1 1 = exp ( − λh + ( p − 1 ) ( N − 1 ) max { κ SG 2 , 1 } λ 2 p )
Optimizing over λ ≥ 0 \lambda\ge0 λ ≥ 0 gives us a one-sided bound in the form (26) . By applying the same argument on − x N J , Z ( σ ) -x_N^{J,Z}(\sigma) − x N J , Z ( σ ) , we get the two-sided bound (26) .
In order to show (27) , we see by definition (11) and the tail probability estimate (A.3) that it suffices to prove E J [ ∥ ∇ 2 H N J ( σ ) ∥ o p k ] 1 / k \mathbb{E}_J[\|\nabla^2H_N^J(\sigma)\|_{\mathrm{op}}^k]^{1/k} E J [ ∥ ∇ 2 H N J ( σ ) ∥ op k ] 1/ k can be bounded uniformly as long as k ≤ C N k\le CN k ≤ C N . Observe that for all x ∈ S N − 1 x\in S^{N-1} x ∈ S N − 1 ,
⟨ ∇ 2 H N J ( σ ) x , x ⟩ = ∑ I ∈ [ N ] p ( 1 N ( p − 1 ) / 2 ∑ j , k = 1 N ∂ 2 σ I ∂ σ j ∂ σ k x j x k ) J I . \langle\nabla^2H_N^J(\sigma)x,x\rangle=\sum_{I\in[N]_p}\left(\frac{1}{N^{(p-1)/2}}\sum_{j,k=1}^N\frac{\partial^2\sigma_I}{\partial\sigma_j\partial\sigma_k}x_jx_k\right)J_I. ⟨ ∇ 2 H N J ( σ ) x , x ⟩ = I ∈ [ N ] p ∑ N ( p − 1 ) /2 1 j , k = 1 ∑ N ∂ σ j ∂ σ k ∂ 2 σ I x j x k J I .
Note that, as in the proof of Lemma 4.1, the 2-norm of the coefficients satisfies
∑ I ∈ [ N ] p ( 1 N ( p − 1 ) / 2 ∑ j , k = 1 N ∂ 2 σ I ∂ σ j ∂ σ k x j x k ) 2 ≤ p 2 ( p − 1 ) 2 N . \sum_{I\in[N]_p}\left(\frac{1}{N^{(p-1)/2}}\sum_{j,k=1}^N\frac{\partial^2\sigma_I}{\partial\sigma_j\partial\sigma_k}x_jx_k\right)^2\le\frac{p^2(p-1)^2}{N}. I ∈ [ N ] p ∑ N ( p − 1 ) /2 1 j , k = 1 ∑ N ∂ σ j ∂ σ k ∂ 2 σ I x j x k 2 ≤ N p 2 ( p − 1 ) 2 .
It follows that ⟨ ∇ 2 H N J ( σ ) x , x ⟩ \langle\nabla^2H_N^J(\sigma)x,x\rangle ⟨ ∇ 2 H N J ( σ ) x , x ⟩ is ( p 2 ( p − 1 ) 2 κ S G 2 / N ) (p^2(p-1)^2\kappa_{\mathrm{SG}}^2/N) ( p 2 ( p − 1 ) 2 κ SG 2 / N ) -subgaussian by [21 Proposition 2.6.1] .
Now, for 0 < δ < 1 / 2 0<\delta<1/2 0 < δ < 1/2 , let N δ \mathcal{N}_\delta N δ be a δ \delta δ -net of the unit sphere S N − 1 S^{N-1} S N − 1 . By [21 Proposition 4.2.12] , we may choose it so that ∣ N δ ∣ ≤ ( C 0 / δ ) N |\mathcal{N}_\delta|\le(C_0/\delta)^N ∣ N δ ∣ ≤ ( C 0 / δ ) N for an absolute constant C 0 > 0 C_0>0 C 0 > 0 . For every x ∈ S N − 1 x\in S^{N-1} x ∈ S N − 1 , there exists y ∈ N δ y\in\mathcal{N}_\delta y ∈ N δ such that ∥ x − y ∥ 2 ≤ δ \|x-y\|_2\le\delta ∥ x − y ∥ 2 ≤ δ . It follows that
∥ ∇ 2 H N J ( σ ) ∥ o p = max x ∈ S N − 1 ∣ ⟨ ∇ 2 H N J ( σ ) x , x ⟩ ∣ ≤ max y ∈ N δ ∣ ⟨ ∇ 2 H N J ( σ ) y , y ⟩ ∣ + 2 δ ∥ ∇ 2 H N J ( σ ) ∥ o p . (29) \|\nabla^2H_N^J(\sigma)\|_{\mathrm{op}}=\max_{x\in S^{N-1}}\left|\langle\nabla^2H_N^J(\sigma)x,x\rangle\right|
\le\max_{y\in\mathcal{N}_\delta}\left|\langle\nabla^2H_N^J(\sigma)y,y\rangle\right|+2\delta\|\nabla^2H_N^J(\sigma)\|_{\mathrm{op}}. \tag*{(29)} ∥ ∇ 2 H N J ( σ ) ∥ op = x ∈ S N − 1 max ⟨ ∇ 2 H N J ( σ ) x , x ⟩ ≤ y ∈ N δ max ⟨ ∇ 2 H N J ( σ ) y , y ⟩ + 2 δ ∥ ∇ 2 H N J ( σ ) ∥ op . (29)
Apply (A.2) to the 2 ∣ N δ ∣ 2|\mathcal{N}_\delta| 2∣ N δ ∣ random variables { ± ⟨ ∇ 2 H N J ( σ ) y , y ⟩ : y ∈ N δ } \{\pm\langle\nabla^2H_N^J(\sigma)y,y\rangle:y\in\mathcal{N}_\delta\} { ± ⟨ ∇ 2 H N J ( σ ) y , y ⟩ : y ∈ N δ } . Together with (29) , this yields
E J [ ∥ ∇ 2 H N J ( σ ) ∥ o p k ] 1 / k ≤ 1 1 − 2 δ E J [ ( max y ∈ N δ ⟨ ∇ 2 H N J ( σ ) y , y ⟩ ) k ] 1 / k ≤ c 16 1 − 2 δ p ( p − 1 ) κ S G N log ( 2 ∣ N δ ∣ ) + k = O N ( 1 ) \begin{aligned}
\mathbb{E}_J[\|\nabla^2H_N^J(\sigma)\|_{\mathrm{op}}^k]^{1/k}\le\frac{1}{1-2\delta}\mathbb{E}_J\left[\left(\max_{y\in\mathcal{N}_\delta}\langle\nabla^2H_N^J(\sigma)y,y\rangle\right)^k\right]^{1/k} \\
&\le\frac{c_{16}}{1-2\delta}\frac{p(p-1)\kappa_{\mathrm{SG}}}{\sqrt{N}}\sqrt{\log(2|\mathcal{N}_\delta|)+k}=O_N(1)
\end{aligned} E J [ ∥ ∇ 2 H N J ( σ ) ∥ op k ] 1/ k ≤ 1 − 2 δ 1 E J [ ( y ∈ N δ max ⟨ ∇ 2 H N J ( σ ) y , y ⟩ ) k ] 1/ k ≤ 1 − 2 δ c 16 N p ( p − 1 ) κ SG log ( 2∣ N δ ∣ ) + k = O N ( 1 )
for fixed δ \delta δ and k ≤ C N k\le CN k ≤ C N . This proves (27) .
Last, (28) follows from
E J , g , Z [ ∣ det ( M N − 1 J , g ( σ ) − x N J , Z ( σ ) I N − 1 ) ∣ 2 ] ≤ E J , g , Z [ ( ∥ M N − 1 J , g ( σ ) ∥ o p + ∣ x N J , Z ( σ ) ∣ ) 2 ( N − 1 ) ] , \mathbb{E}_{J,g,Z}\left[\left|\det\left(M_{N-1}^{J,g}(\sigma)-x_N^{J,Z}(\sigma)I_{N-1}\right)\right|^2\right]\le\mathbb{E}_{J,g,Z}\left[\left(\|M_{N-1}^{J,g}(\sigma)\|_{\mathrm{op}}+|x_N^{J,Z}(\sigma)|\right)^{2(N-1)}\right], E J , g , Z [ det ( M N − 1 J , g ( σ ) − x N J , Z ( σ ) I N − 1 ) 2 ] ≤ E J , g , Z [ ( ∥ M N − 1 J , g ( σ ) ∥ op + ∣ x N J , Z ( σ ) ∣ ) 2 ( N − 1 ) ] ,
the inequality (26) , and (27) with k = 2 ( N − 1 ) k=2(N-1) k = 2 ( N − 1 ) .
Corollary 4.4. If { J I } I ∈ [ N ] p , N ∈ N \{J_I\}_{I\in[N]_p,N\in\mathbb{N}} { J I } I ∈ [ N ] p , N ∈ N satisfies (SG) with uniform κ S G \kappa_{\mathrm{SG}} κ SG , then there exists a constant c 6 = c 6 ( κ S G , p ) > 0 c_6=c_6(\kappa_{\mathrm{SG}},p)>0 c 6 = c 6 ( κ SG , p ) > 0 such that for all M ≥ 1 M\ge1 M ≥ 1 , we have
sup N ≥ 2 sup σ , ∣ x ∣ ≤ M , η > 0 ∫ R ( log η ( λ − x ) − log η K ( λ − x ) ) E J , g [ μ N − 1 J , g , σ ( d λ ) ] ≤ c 6 M 2 K 2 , (30) \sup_{N\ge2}\sup_{\sigma,|x|\le M,\eta>0}\int_{\mathbb{R}}\left(\log_\eta(\lambda-x)-\log_\eta^K(\lambda-x)\right)\mathbb{E}_{J,g}\left[\mu_{N-1}^{J,g,\sigma}(d\lambda)\right]\le\frac{c_6M^2}{K^2}, \tag*{(30)} N ≥ 2 sup σ , ∣ x ∣ ≤ M , η > 0 sup ∫ R ( log η ( λ − x ) − log η K ( λ − x ) ) E J , g [ μ N − 1 J , g , σ ( d λ ) ] ≤ K 2 c 6 M 2 , (30)
where the supremum is over σ ∈ N S N − 1 \sigma\in\sqrt{N}S^{N-1} σ ∈ N S N − 1 .
Proof. By definition, rewrite
∫ R ( log η ( λ − x ) − log η K ( λ − x ) ) E J , g [ μ N − 1 J , g , σ ( d λ ) ] = 1 2 ∫ ∣ λ − x ∣ ≥ K log ( ( λ − x ) 2 + η 2 K 2 + η 2 ) E J , g [ μ N − 1 J , g , σ ( d λ ) ] = 1 2 ∫ K ∞ 2 y y 2 + η 2 E J , g [ μ N − 1 J , g , σ ( ∣ λ − x ∣ ≥ y ) ] d y ≤ ∫ R ∣ λ − x ∣ 2 E J , g [ μ N − 1 J , g , σ ( d λ ) ] ∫ K ∞ 2 y ( y 2 + η 2 ) d y , (31) \begin{aligned}
\int_{\mathbb{R}}\left(\log_{\eta}(\lambda-x)-\log_{\eta}^{K}(\lambda-x)\right)\mathbb{E}_{J,g}\left[\mu_{N-1}^{J,g,\sigma}(d\lambda)\right]
&=\frac{1}{2}\int_{\lvert\lambda-x\rvert\ge K}\log\left(\frac{(\lambda-x)^2+\eta^2}{K^2+\eta^2}\right)\mathbb{E}_{J,g}\left[\mu_{N-1}^{J,g,\sigma}(d\lambda)\right]\\
&=\frac{1}{2}\int_{K}^{\infty}\frac{2y}{y^2+\eta^2}\mathbb{E}_{J,g}\left[\mu_{N-1}^{J,g,\sigma}(\lvert\lambda-x\rvert\ge y)\right]\,dy\\
&\le\int_{\mathbb{R}}\lvert\lambda-x\rvert^2\mathbb{E}_{J,g}\left[\mu_{N-1}^{J,g,\sigma}(d\lambda)\right]\int_{K}^{\infty}\frac{2}{y(y^2+\eta^2)}\,dy, \tag*{(31)}
\end{aligned} ∫ R ( log η ( λ − x ) − log η K ( λ − x ) ) E J , g [ μ N − 1 J , g , σ ( d λ ) ] = 2 1 ∫ ∣ λ − x ∣ ≥ K log ( K 2 + η 2 ( λ − x ) 2 + η 2 ) E J , g [ μ N − 1 J , g , σ ( d λ ) ] = 2 1 ∫ K ∞ y 2 + η 2 2 y E J , g [ μ N − 1 J , g , σ (∣ λ − x ∣ ≥ y ) ] d y ≤ ∫ R ∣ λ − x ∣ 2 E J , g [ μ N − 1 J , g , σ ( d λ ) ] ∫ K ∞ y ( y 2 + η 2 ) 2 d y , (31)
where (31) holds by Markov’s inequality. By (27) , the first term in (31) satisfies
∫ R ∣ λ − x ∣ 2 E J , g [ μ N − 1 J , g , σ ( d λ ) ] ≤ E J , g [ ∥ M N − 1 J , g ( σ ) ∥ o p 2 + 2 ∣ x ∣ ∥ M N − 1 J , g ( σ ) ∥ o p + x 2 ] = M 2 O N ( 1 ) . \int_{\mathbb{R}}\lvert\lambda-x\rvert^2\mathbb{E}_{J,g}\left[\mu_{N-1}^{J,g,\sigma}(d\lambda)\right]\le\mathbb{E}_{J,g}\left[\left\lVert M_{N-1}^{J,g}(\sigma)\right\rVert_{\mathrm{op}}^2+2\lvert x\rvert\left\lVert M_{N-1}^{J,g}(\sigma)\right\rVert_{\mathrm{op}}+x^2\right]=M^2O_N(1). ∫ R ∣ λ − x ∣ 2 E J , g [ μ N − 1 J , g , σ ( d λ ) ] ≤ E J , g [ M N − 1 J , g ( σ ) op 2 + 2 ∣ x ∣ M N − 1 J , g ( σ ) op + x 2 ] = M 2 O N ( 1 ) .
Moreover, the second term in (31) is of order K − 2 K^{-2} K − 2 , uniformly over all η > 0 \eta>0 η > 0 . These two estimations give us the desired bound (30) .
Universality of the Hessian Matrix
Throughout this subsection, we assume that the disorder variables J I J_I J I ’s are independent and have zero mean and unit variance.
Definition 4.5 (Finite Moment). A collection of random variables { X α } α ∈ A \{X_\alpha\}_{\alpha\in A} { X α } α ∈ A is said to have uniformly bounded moments if for all k ∈ N k\in\mathbb{N} k ∈ N
sup α ∈ A E [ ∣ X α ∣ k ] < ∞ . (32) \sup_{\alpha\in A}\mathbb{E}\left[\lvert X_\alpha\rvert^k\right]<\infty. \tag*{(32)} α ∈ A sup E [ ∣ X α ∣ k ] < ∞. (32)
We note that condition (M) holds if the same collection of random variables satisfies (SG) with uniform κ S G \kappa_{\mathrm{SG}} κ SG .
Lemma 4.6. If { J I } I ∈ [ N ] p , N ∈ N \{J_I\}_{I\in[N]^p,N\in\mathbb{N}} { J I } I ∈ [ N ] p , N ∈ N satisfies (M), then
lim N → ∞ sup σ ∈ N S N − 1 d B L ( E J , g [ μ N − 1 J , g , σ ] , μ s c ) = 0 , (33) \lim_{N\to\infty}\sup_{\sigma\in\sqrt{N}\mathbb{S}^{N-1}}d_{\mathrm{BL}}\left(\mathbb{E}_{J,g}\left[\mu_{N-1}^{J,g,\sigma}\right],\mu_{\mathrm{sc}}\right)=0, \tag*{(33)} N → ∞ lim σ ∈ N S N − 1 sup d BL ( E J , g [ μ N − 1 J , g , σ ] , μ sc ) = 0 , (33)
where the supremum is over σ ∈ N S N − 1 \sigma\in\sqrt{N}\mathbb{S}^{N-1} σ ∈ N S N − 1 .
Proof. Conditioning on σ ∈ N S N − 1 \sigma\in\sqrt{N}\mathbb{S}^{N-1} σ ∈ N S N − 1 , μ N − 1 J , g , σ \mu_{N-1}^{J,g,\sigma} μ N − 1 J , g , σ is the empirical measure of the random matrix
M_{N-1}^{J,g}(\sigma)\mathrel{\mathop:}=\sqrt{\frac{N}{N-1}}\frac{B(\sigma)^{\mathsf{T}}\nabla^2H^{\sqrt{1-tG+\sqrt{t}J}(\sigma)B(\sigma)}{\sqrt{p(p-1)}}.}
Recall the rank ( N − 1 ) (N-1) ( N − 1 ) projection P ( σ ) P(\sigma) P ( σ ) from (8) and we set
\overline{M}_{N-1}^{J,g}(\sigma)=\frac{P(\sigma)^{\mathsf{T}}\nabla^2H^{\sqrt{1-tG+\sqrt{t}J}(\sigma)P(\sigma)}{\sqrt{p(p-1)}}.}
Then, the bounded Lipschitz distance satisfies
d B L ( E J , g [ μ N − 1 J , g , σ ] , μ s c ) ≤ d B L ( E J , g [ μ M N − 1 J , g ] , E J , g [ μ N − 1 N M N − 1 J , g ( σ ) ] ) . (34) d_{\mathrm{BL}}\left(\mathbb{E}_{J,g}\left[\mu_{N-1}^{J,g,\sigma}\right],\mu_{\mathrm{sc}}\right)\le d_{\mathrm{BL}}\left(\mathbb{E}_{J,g}\left[\mu_{M_{N-1}^{J,g}}\right],\mathbb{E}_{J,g}\left[\mu_{\sqrt{\frac{N-1}{N}}M_{N-1}^{J,g}(\sigma)}\right]\right). \tag*{(34)} d BL ( E J , g [ μ N − 1 J , g , σ ] , μ sc ) ≤ d BL ( E J , g [ μ M N − 1 J , g ] , E J , g [ μ N N − 1 M N − 1 J , g ( σ ) ] ) . (34)
+ d B L ( E J , g [ μ N − 1 N M N − 1 J , g ( σ ) ] , E J , g [ μ M N − 1 J , g ( σ ) ] ) (35) +d_{\mathrm{BL}}\left(\mathbb{E}_{J,g}\left[\mu_{\sqrt{\frac{N-1}{N}}M_{N-1}^{J,g}(\sigma)}\right],\mathbb{E}_{J,g}\left[\mu_{M_{N-1}^{J,g}(\sigma)}\right]\right) \tag*{(35)} + d BL ( E J , g [ μ N N − 1 M N − 1 J , g ( σ ) ] , E J , g [ μ M N − 1 J , g ( σ ) ] ) (35)
+ d B L ( E J , g [ μ M N − 1 J , g ( σ ) ] , μ s c ) . (36) +d_{\mathrm{BL}}\left(\mathbb{E}_{J,g}\left[\mu_{M_{N-1}^{J,g}(\sigma)}\right],\mu_{\mathrm{sc}}\right). \tag*{(36)} + d BL ( E J , g [ μ M N − 1 J , g ( σ ) ] , μ sc ) . (36)
By (27) , the first term (34) can be estimated by
d B L ( E J , g [ μ M N − 1 J , g ( σ ) ] , E J , g [ μ N − 1 N M N − 1 J , g ( σ ) ] ) ≤ [ ( N N − 1 ) 1 / 2 − 1 ] E J , g [ ∥ M N − 1 J , g ( σ ) ∥ o p ] = o N ( 1 ) , d_{\mathrm{BL}}\left(\mathbb{E}_{J,g}\left[\mu_{M_{N-1}^{J,g}(\sigma)}\right],\mathbb{E}_{J,g}\left[\mu_{\sqrt{\frac{N-1}{N}}M_{N-1}^{J,g}(\sigma)}\right]\right)\leq\left[\left(\frac{N}{N-1}\right)^{1/2}-1\right]\mathbb{E}_{J,g}\left[\left\|M_{N-1}^{J,g}(\sigma)\right\|_{\mathrm{op}}\right]=o_N(1), d BL ( E J , g [ μ M N − 1 J , g ( σ ) ] , E J , g [ μ N N − 1 M N − 1 J , g ( σ ) ] ) ≤ [ ( N − 1 N ) 1/2 − 1 ] E J , g [ M N − 1 J , g ( σ ) op ] = o N ( 1 ) ,
where the convergence is uniform over σ ∈ N S N − 1 \sigma\in\sqrt{N}\mathbb{S}^{N-1} σ ∈ N S N − 1 . By definition of B ( σ ) B(\sigma) B ( σ ) and P ( σ ) P(\sigma) P ( σ ) , the second term (35) can be estimated by
d B L ( E J , g [ μ N − 1 N M N − 1 J , g ( σ ) ] , E J , g [ μ M N − 1 J , g ( σ ) ] ) = d B L ( E J , g [ μ N − 1 N M N − 1 J , g ( σ ) ] , 1 N δ 0 + N − 1 N E J , g [ μ N − 1 N M N − 1 J , g ( σ ) ] ) ≤ 2 N . \begin{aligned}
d_{\mathrm{BL}}\left(\mathbb{E}_{J,g}\left[\mu_{\sqrt{\frac{N-1}{N}}M_{N-1}^{J,g}(\sigma)}\right],\mathbb{E}_{J,g}\left[\mu_{M_{N-1}^{J,g}(\sigma)}\right]\right) \\
&=d_{\mathrm{BL}}\left(\mathbb{E}_{J,g}\left[\mu_{\sqrt{\frac{N-1}{N}}M_{N-1}^{J,g}(\sigma)}\right],\frac{1}{N}\delta_0+\frac{N-1}{N}\mathbb{E}_{J,g}\left[\mu_{\sqrt{\frac{N-1}{N}}M_{N-1}^{J,g}(\sigma)}\right]\right)\leq\frac{2}{N}.
\end{aligned} d BL ( E J , g [ μ N N − 1 M N − 1 J , g ( σ ) ] , E J , g [ μ M N − 1 J , g ( σ ) ] ) = d BL ( E J , g [ μ N N − 1 M N − 1 J , g ( σ ) ] , N 1 δ 0 + N N − 1 E J , g [ μ N N − 1 M N − 1 J , g ( σ ) ] ) ≤ N 2 .
Last, note that the interpolated disorder 1 − t G I + t J I \sqrt{1-t}G_I+\sqrt{t}J_I 1 − t G I + t J I still satisfies (M). By [17 Proposition 3.1] , the term in (36) also converge uniformly to 0 as N → ∞ N\to\infty N → ∞ . This concludes the proof of the lemma.
Lemma 4.7. For all h > 0 h>0 h > 0 , there exists η = η ( h ) > 0 \eta=\eta(h)>0 η = η ( h ) > 0 such that
sup N , A N , x ∫ R ( log η ( λ − x ) − log ∣ λ − x ∣ ) E [ μ A N + G O E N ] ( d λ ) ≤ h , (37) \sup_{N,A_N,x}\int_{\mathbb{R}}\left(\log_{\eta}(\lambda-x)-\log\lvert\lambda-x\rvert\right)\mathbb{E}\left[\mu_{A_N+\mathrm{GOE}_N}\right](d\lambda)\leq h, \tag*{(37)} N , A N , x sup ∫ R ( log η ( λ − x ) − log ∣ λ − x ∣ ) E [ μ A N + GOE N ] ( d λ ) ≤ h , (37) where the supremum is over all N ∈ N N\in\mathbb{N} N ∈ N , deterministic symmetric matrices A N A_N A N , and x ∈ R x\in\mathbb{R} x ∈ R .
Proof. From [2 Theorem 1] , there exists an absolute constant c 7 > 0 c_7>0 c 7 > 0 such that, for every N ∈ N N\in\mathbb{N} N ∈ N , every deterministic symmetric N × N N\times N N × N matrix A N A_N A N , and every interval I ⊆ R I\subseteq\mathbb{R} I ⊆ R , we have
E ( ∣ Spec ( A N + G O E N ) ∩ I ∣ ) ≤ c 7 N ∣ I ∣ , (38) \mathbb{E}\left(\left|\operatorname{Spec}(A_N+\mathrm{GOE}_N)\cap I\right|\right)\leq c_7N|I|, \tag*{(38)} E ( ∣ Spec ( A N + GOE N ) ∩ I ∣ ) ≤ c 7 N ∣ I ∣ , (38)
where ∣ I ∣ |I| ∣ I ∣ is the Lebesgue measure of I I I . (38) implies that the empirical measure satisfies
E [ μ A N + G O E N ] ( I ) = 1 N E ( ∣ Spec ( A N + G O E N ) ∩ I ∣ ) ≤ c 7 ∣ I ∣ \mathbb{E}\left[\mu_{A_N+\mathrm{GOE}_N}\right](I)=\frac{1}{N}\mathbb{E}\left(\left|\operatorname{Spec}(A_N+\mathrm{GOE}_N)\cap I\right|\right)\leq c_7|I| E [ μ A N + GOE N ] ( I ) = N 1 E ( ∣ Spec ( A N + GOE N ) ∩ I ∣ ) ≤ c 7 ∣ I ∣
for every interval I I I . Therefore, E [ μ A N + G O E N ] \mathbb{E}\left[\mu_{A_N+\mathrm{GOE}_N}\right] E [ μ A N + GOE N ] is absolutely continuous with respect to the Lebesgue measure with density bounded by c 7 c_7 c 7 . Consequently,
∫ R ( log η ( λ − x ) − log ∣ λ − x ∣ ) E [ μ A N + G O E N ] ( d λ ) ≤ c 7 2 ∫ R log ( 1 + η 2 ( λ − x ) 2 ) d λ = c 7 π η . \int_{\mathbb{R}}\left(\log_{\eta}(\lambda-x)-\log\lvert\lambda-x\rvert\right)\mathbb{E}\left[\mu_{A_N+\mathrm{GOE}_N}\right](d\lambda)\leq\frac{c_7}{2}\int_{\mathbb{R}}\log\left(1+\frac{\eta^2}{(\lambda-x)^2}\right)d\lambda=c_7\pi\eta. ∫ R ( log η ( λ − x ) − log ∣ λ − x ∣ ) E [ μ A N + GOE N ] ( d λ ) ≤ 2 c 7 ∫ R log ( 1 + ( λ − x ) 2 η 2 ) d λ = c 7 π η .
We see then (37) holds directly.
Isolating the Determinant
Recall E ∞ = 2 ( p − 1 ) / p E_{\infty}=2\sqrt{(p-1)/p} E ∞ = 2 ( p − 1 ) / p from (2) . For all u ∈ R u\in\mathbb{R} u ∈ R , let
U N ( u ) : = N p ( N − 1 ) ( p − 1 ) ( − ∞ , u ) = ( − ∞ , N N − 1 2 u E ∞ ) . U_N(u):=\sqrt{\frac{Np}{(N-1)(p-1)}}(-\infty,u)=\left(-\infty,\sqrt{\frac{N}{N-1}}\frac{2u}{E_{\infty}}\right). U N ( u ) := ( N − 1 ) ( p − 1 ) N p ( − ∞ , u ) = ( − ∞ , N − 1 N E ∞ 2 u ) .
The main goal of this section is to isolate the determinant term in
L N ( u ) : = E σ , J , g , Z [ e − N t 2 p ( 1 − t ) y N J ( σ ) ∣ det ( M N − 1 J , g ( σ ) − x N J , Z ( σ ) I N − 1 ) ∣ ⋅ 1 { x N J , Z ∈ U N ( u ) } ] (39) \mathcal{L}_N(u) := \mathbb{E}_{\sigma,J,g,Z}\left[e^{-\frac{Nt}{2p(1-t)}y_N^J(\sigma)}\left|\det\left(M_{N-1}^{J,g}(\sigma)-x_N^{J,Z}(\sigma)I_{N-1}\right)\right|\cdot\mathbf{1}_{\{x_N^{J,Z}\in U_N(u)\}}\right] \tag*{(39)} L N ( u ) := E σ , J , g , Z [ e − 2 p ( 1 − t ) N t y N J ( σ ) det ( M N − 1 J , g ( σ ) − x N J , Z ( σ ) I N − 1 ) ⋅ 1 { x N J , Z ∈ U N ( u )} ] (39)
by using the concentration of the random matrix in the determinant. For all x ∈ R x\in\mathbb{R} x ∈ R and δ > 0 \delta>0 δ > 0 , we also introduce
ℓ N ( x , δ ) : = E σ , J , Z [ e − N t 2 p ( 1 − t ) y N J ( σ ) 1 { x N J , Z ( σ ) ∈ B ( x , δ ) } ] . (40) \ell_N(x,\delta):=\mathbb{E}_{\sigma,J,Z}\left[e^{-\frac{Nt}{2p(1-t)}y_N^J(\sigma)}\mathbf{1}_{\{x_N^{J,Z}(\sigma)\in B(x,\delta)\}}\right]. \tag*{(40)} ℓ N ( x , δ ) := E σ , J , Z [ e − 2 p ( 1 − t ) N t y N J ( σ ) 1 { x N J , Z ( σ ) ∈ B ( x , δ )} ] . (40)
Lemma 5.1. For K ≥ M + 2 K\ge M+2 K ≥ M + 2 and ∣ x ∣ ≤ M |x|\le M ∣ x ∣ ≤ M ,
0 ≤ ∫ R ( log η K ( λ − x ) − log ∣ λ − x ∣ ) μ s c ( d λ ) ≤ η . (41) 0\le\int_{\mathbb{R}}\left(\log_\eta^K(\lambda-x)-\log|\lambda-x|\right)\mu_{\mathrm{sc}}(d\lambda)\le\eta. \tag*{(41)} 0 ≤ ∫ R ( log η K ( λ − x ) − log ∣ λ − x ∣ ) μ sc ( d λ ) ≤ η . (41)
Proof. Since supp ( μ s c ) ⊆ [ − 2 , 2 ] \operatorname{supp}(\mu_{\mathrm{sc}})\subseteq[-2,2] supp ( μ sc ) ⊆ [ − 2 , 2 ] , we must have ∣ λ − x ∣ ≤ M + 2 |\lambda-x|\le M+2 ∣ λ − x ∣ ≤ M + 2 . Therefore,
∫ R ( log η K ( λ − x ) − log ∣ λ − x ∣ ) μ s c ( d λ ) = ∫ R ( log η ( λ − x ) − log ∣ λ − x ∣ ) μ s c ( d λ ) − ∫ ∣ λ − x ∣ ≥ K ( log η ( λ − x ) − log η K ( λ − x ) ) μ s c ( d λ ) (42) \begin{aligned}
\int_{\mathbb{R}}\left(\log_\eta^K(\lambda-x)-\log|\lambda-x|\right)\mu_{\mathrm{sc}}(d\lambda)
&=\int_{\mathbb{R}}\left(\log_\eta(\lambda-x)-\log|\lambda-x|\right)\mu_{\mathrm{sc}}(d\lambda)\\
&\quad-\int_{|\lambda-x|\ge K}\left(\log_\eta(\lambda-x)-\log_\eta^K(\lambda-x)\right)\mu_{\mathrm{sc}}(d\lambda) \tag*{(42)}
\end{aligned} ∫ R ( log η K ( λ − x ) − log ∣ λ − x ∣ ) μ sc ( d λ ) = ∫ R ( log η ( λ − x ) − log ∣ λ − x ∣ ) μ sc ( d λ ) − ∫ ∣ λ − x ∣ ≥ K ( log η ( λ − x ) − log η K ( λ − x ) ) μ sc ( d λ ) (42)
= 1 2 ∫ R log ( 1 + η 2 ( λ − x ) 2 ) μ s c ( d λ ) (43) =\frac{1}{2}\int_{\mathbb{R}}\log\left(1+\frac{\eta^2}{(\lambda-x)^2}\right)\mu_{\mathrm{sc}}(d\lambda) \tag*{(43)} = 2 1 ∫ R log ( 1 + ( λ − x ) 2 η 2 ) μ sc ( d λ ) (43)
≤ 1 2 π ∫ R log ( 1 + η 2 ( λ − x ) 2 ) d λ = η , (44) \le\frac{1}{2\pi}\int_{\mathbb{R}}\log\left(1+\frac{\eta^2}{(\lambda-x)^2}\right)d\lambda=\eta, \tag*{(44)} ≤ 2 π 1 ∫ R log ( 1 + ( λ − x ) 2 η 2 ) d λ = η , (44)
where (43) holds since the second integral in (5.4 vanishes and (44) by the density (2) . The lower bound in (41) is direct from the expression (43) . □ \square □
Upper Bound
Proposition 5.2. If { J I } I ∈ [ N ] p , N ∈ N \{J_I\}_{I\in[N]_p,N\in\mathbb{N}} { J I } I ∈ [ N ] p , N ∈ N satisfies (SG) with uniform κ S G \kappa_{\mathrm{SG}} κ SG , then, for u ∈ R u\in\mathbb{R} u ∈ R ,
lim sup N → ∞ 1 N log L N ( u ) ≤ lim δ → 0 sup x ≤ 2 u / E ∞ { Ω ( x ) + lim sup N → ∞ 1 N log ℓ N ( x , δ ) } . \limsup_{N\to\infty}\frac{1}{N}\log\mathcal{L}_N(u)\le\lim_{\delta\to0}\sup_{x\le2u/E_\infty}\left\{\Omega(x)+\limsup_{N\to\infty}\frac{1}{N}\log\ell_N(x,\delta)\right\}. N → ∞ lim sup N 1 log L N ( u ) ≤ δ → 0 lim x ≤ 2 u / E ∞ sup { Ω ( x ) + N → ∞ lim sup N 1 log ℓ N ( x , δ ) } .
Proof. Let δ , η , h > 0 \delta,\eta,h>0 δ , η , h > 0 and let M ≥ 2 + ∣ 2 u / E ∞ ∣ M\ge2+|2u/E_\infty| M ≥ 2 + ∣2 u / E ∞ ∣ , K = M 2 ≥ M + 2 K=M^2\ge M+2 K = M 2 ≥ M + 2 be parameters to be chosen sufficiently large. By compactness, there exists finitely many points x 1 , … , x n ∈ [ − M , 2 u / E ∞ ] x_1,\ldots,x_n\in[-M,2u/E_\infty] x 1 , … , x n ∈ [ − M , 2 u / E ∞ ] , including x n = 2 u / E ∞ x_n=2u/E_\infty x n = 2 u / E ∞ , such that [ − M , 2 u / E ∞ ] ⊆ ⋃ i = 1 n B ( x i , δ ) [-M,2u/E_\infty]\subseteq\bigcup_{i=1}^nB(x_i,\delta) [ − M , 2 u / E ∞ ] ⊆ ⋃ i = 1 n B ( x i , δ ) . Consequently, U N ( u ) ∩ [ − M , M ] ⊆ ⋃ i = 1 n B ( x i , δ ) U_N(u)\cap[-M,M]\subseteq\bigcup_{i=1}^nB(x_i,\delta) U N ( u ) ∩ [ − M , M ] ⊆ ⋃ i = 1 n B ( x i , δ ) for all sufficiently large N N N .
Therefore, for all sufficiently large N N N ,
E J , g , Z [ e − N t 2 p ( 1 − t ) y N J ( σ ) ∣ det ( M N − 1 J , g ( σ ) − x N J , Z ( σ ) I N − 1 ) ∣ ⋅ 1 { x N J , Z ( σ ) ∈ U N ( u ) } ] = E J , g , Z [ e − N t 2 p ( 1 − t ) y N J ( σ ) ⋅ e ( N − 1 ) ∫ R log ∣ λ − x N J , Z ( σ ) ∣ μ N − 1 J , g , σ ( d λ ) 1 { x N J , Z ( σ ) ∈ U N ( u ) } ] ≤ E J , g , Z [ e ( N − 1 ) ∫ R log ∣ λ − x N J , Z ( σ ) ∣ μ N − 1 J , g , σ ( d λ ) 1 { ∣ x N J , Z ( σ ) ∣ ≥ M } ] (45) \begin{aligned}
&\mathbb{E}_{J,g,Z}\left[e^{-\frac{Nt}{2p(1-t)}y_N^J(\sigma)}\left|\det\left(M_{N-1}^{J,g}(\sigma)-x_N^{J,Z}(\sigma)I_{N-1}\right)\right|\cdot\mathbf{1}_{\{x_N^{J,Z}(\sigma)\in U_N(u)\}}\right]\\
&=\mathbb{E}_{J,g,Z}\left[e^{-\frac{Nt}{2p(1-t)}y_N^J(\sigma)}\cdot e^{(N-1)\int_{\mathbb{R}}\log|\lambda-x_N^{J,Z}(\sigma)|\mu_{N-1}^{J,g,\sigma}(d\lambda)}\mathbf{1}_{\{x_N^{J,Z}(\sigma)\in U_N(u)\}}\right]\\
&\le\mathbb{E}_{J,g,Z}\left[e^{(N-1)\int_{\mathbb{R}}\log|\lambda-x_N^{J,Z}(\sigma)|\mu_{N-1}^{J,g,\sigma}(d\lambda)}\mathbf{1}_{\{|x_N^{J,Z}(\sigma)|\ge M\}}\right] \tag*{(45)}
\end{aligned} E J , g , Z [ e − 2 p ( 1 − t ) N t y N J ( σ ) det ( M N − 1 J , g ( σ ) − x N J , Z ( σ ) I N − 1 ) ⋅ 1 { x N J , Z ( σ ) ∈ U N ( u )} ] = E J , g , Z [ e − 2 p ( 1 − t ) N t y N J ( σ ) ⋅ e ( N − 1 ) ∫ R l o g ∣ λ − x N J , Z ( σ ) ∣ μ N − 1 J , g , σ ( d λ ) 1 { x N J , Z ( σ ) ∈ U N ( u )} ] ≤ E J , g , Z [ e ( N − 1 ) ∫ R l o g ∣ λ − x N J , Z ( σ ) ∣ μ N − 1 J , g , σ ( d λ ) 1 { ∣ x N J , Z ( σ ) ∣ ≥ M } ] (45)
+ ∑ i = 1 n E J , g , Z [ e − N t 2 p ( 1 − t ) y N J ( σ ) ⋅ e ( N − 1 ) ∫ R log ∣ λ − x N J , Z ( σ ) ∣ μ N − 1 J , g , σ ( d λ ) 1 { x N J , Z ( σ ) ∈ B ( x i , δ ) } ] . (46) +\sum_{i=1}^{n}\mathbb{E}_{J,g,Z}\left[e^{-\frac{Nt}{2p(1-t)}y_N^J(\sigma)}\cdot e^{(N-1)\int_{\mathbb{R}}\log|\lambda-x_N^{J,Z}(\sigma)|\mu_{N-1}^{J,g,\sigma}(d\lambda)}\mathbf{1}_{\{x_N^{J,Z}(\sigma)\in B(x_i,\delta)\}}\right]. \tag*{(46)} + i = 1 ∑ n E J , g , Z [ e − 2 p ( 1 − t ) N t y N J ( σ ) ⋅ e ( N − 1 ) ∫ R l o g ∣ λ − x N J , Z ( σ ) ∣ μ N − 1 J , g , σ ( d λ ) 1 { x N J , Z ( σ ) ∈ B ( x i , δ )} ] . (46)
For the first term (45) , we see that there exists a constant c 8 = c 8 ( κ S G , p ) > 0 c_8=c_8(\kappa_{\mathrm{SG}},p)>0 c 8 = c 8 ( κ SG , p ) > 0 such that
E J , g , Z [ e ( N − 1 ) ∫ R log ∣ λ − x N J , Z ( σ ) ∣ μ N − 1 J , g , σ ( d λ ) 1 { ∣ x N J , Z ( σ ) ∣ ≥ M } ] ≤ E J , g , Z [ e 2 ( N − 1 ) ∫ R log ∣ λ − x N J , Z ( σ ) ∣ μ N − 1 J , g , σ ( d λ ) ] 1 / 2 ⋅ P J , Z ( ∣ x N J , Z ( σ ) ∣ ≥ M ) 1 / 2 = E J , g , Z [ ∣ det ( M N − 1 J , g ( σ ) − x N J , Z ( σ ) I N − 1 ) ∣ 2 ] 1 / 2 ⋅ P J , Z ( ∣ x N J , Z ( σ ) ∣ ≥ M ) 1 / 2 ≤ e c 5 N ⋅ 2 e − c 3 N M 2 / 2 (47) \begin{aligned}
\mathbb{E}_{J,g,Z}\left[e^{(N-1)\int_{\mathbb{R}}\log|\lambda-x_N^{J,Z}(\sigma)|\mu_{N-1}^{J,g,\sigma}(d\lambda)}\mathbf{1}_{\{|x_N^{J,Z}(\sigma)|\ge M\}}\right] \\
&\le\mathbb{E}_{J,g,Z}\left[\mathrm{e}^{2(N-1)\int_{\mathbb{R}}\log\lvert\lambda-x_N^{J,Z}(\sigma)\rvert\,\mu_{N-1}^{J,g,\sigma}(\mathrm{d}\lambda)}\right]^{1/2}\cdot\mathbb{P}_{J,Z}\left(\lvert x_N^{J,Z}(\sigma)\rvert\ge M\right)^{1/2} \\
&= \mathbb{E}_{J,g,Z}\left[\left\lvert\det\left(M_{N-1}^{J,g}(\sigma)-x_N^{J,Z}(\sigma)I_{N-1}\right)\right\rvert^2\right]^{1/2}\cdot\mathbb{P}_{J,Z}\left(\lvert x_N^{J,Z}(\sigma)\rvert\ge M\right)^{1/2} \\
&\le\mathrm{e}^{c_5N}\cdot\sqrt{2}\mathrm{e}^{-c_3NM^2/2} \tag*{(47)}
\end{aligned} E J , g , Z [ e ( N − 1 ) ∫ R l o g ∣ λ − x N J , Z ( σ ) ∣ μ N − 1 J , g , σ ( d λ ) 1 { ∣ x N J , Z ( σ ) ∣ ≥ M } ] ≤ E J , g , Z [ e 2 ( N − 1 ) ∫ R l o g ∣ λ − x N J , Z ( σ )∣ μ N − 1 J , g , σ ( d λ ) ] 1/2 ⋅ P J , Z ( ∣ x N J , Z ( σ )∣ ≥ M ) 1/2 = E J , g , Z [ det ( M N − 1 J , g ( σ ) − x N J , Z ( σ ) I N − 1 ) 2 ] 1/2 ⋅ P J , Z ( ∣ x N J , Z ( σ )∣ ≥ M ) 1/2 ≤ e c 5 N ⋅ 2 e − c 3 N M 2 /2 (47)
≤ e − c 8 N M 2 , (48) \le\mathrm{e}^{-c_8NM^2}, \tag*{(48)} ≤ e − c 8 N M 2 , (48)
for sufficiently large M M M , where the (47) follows from (26) and (28) . Next, let
A i = ∫ R ( log η ( λ − x N J , Z ( σ ) ) − log η ( λ − x i ) ) μ N − 1 J , g , σ ( d λ ) , A_i=\int_{\mathbb{R}}\left(\log_\eta\left(\lambda-x_N^{J,Z}(\sigma)\right)-\log_\eta(\lambda-x_i)\right)\mu_{N-1}^{J,g,\sigma}(\mathrm{d}\lambda), A i = ∫ R ( log η ( λ − x N J , Z ( σ ) ) − log η ( λ − x i ) ) μ N − 1 J , g , σ ( d λ ) ,
B i = ∫ R log η ( λ − x i ) ( μ N − 1 J , g , σ − E J , g [ μ N − 1 J , g , σ ] ) ( d λ ) , B_i=\int_{\mathbb{R}}\log_\eta(\lambda-x_i)\left(\mu_{N-1}^{J,g,\sigma}-\mathbb{E}_{J,g}\left[\mu_{N-1}^{J,g,\sigma}\right]\right)(\mathrm{d}\lambda), B i = ∫ R log η ( λ − x i ) ( μ N − 1 J , g , σ − E J , g [ μ N − 1 J , g , σ ] ) ( d λ ) ,
C i = ∫ R ( log η ( λ − x i ) − log η K ( λ − x i ) ) E J , g [ μ N − 1 J , g , σ ] ( d λ ) , C_i=\int_{\mathbb{R}}\left(\log_\eta(\lambda-x_i)-\log_\eta^K(\lambda-x_i)\right)\mathbb{E}_{J,g}\left[\mu_{N-1}^{J,g,\sigma}\right](\mathrm{d}\lambda), C i = ∫ R ( log η ( λ − x i ) − log η K ( λ − x i ) ) E J , g [ μ N − 1 J , g , σ ] ( d λ ) ,
D i = ∫ R log η K ( λ − x i ) ( E J , g [ μ N − 1 J , g , σ ] − μ s c ) ( d λ ) D_i=\int_{\mathbb{R}}\log_\eta^K(\lambda-x_i)\left(\mathbb{E}_{J,g}\left[\mu_{N-1}^{J,g,\sigma}\right]-\mu_{\mathrm{sc}}\right)(\mathrm{d}\lambda) D i = ∫ R log η K ( λ − x i ) ( E J , g [ μ N − 1 J , g , σ ] − μ sc ) ( d λ )
E i = ∫ R ( log η K ( λ − x i ) − log ∣ λ − x i ∣ ) μ s c ( d λ ) . E_i=\int_{\mathbb{R}}\left(\log_\eta^K(\lambda-x_i)-\log\lvert\lambda-x_i\rvert\right)\mu_{\mathrm{sc}}(\mathrm{d}\lambda). E i = ∫ R ( log η K ( λ − x i ) − log ∣ λ − x i ∣ ) μ sc ( d λ ) .
Then
∫ R log ∣ λ − x N J , Z ( σ ) ∣ μ N − 1 J , g , σ ( d λ ) ≤ ∫ R log η ( λ − x N J , Z ( σ ) ) μ N − 1 J , g , σ ( d λ ) = A i + B i + C i + D i + E i + Ω ( x i ) . (49) \begin{aligned}
\int_{\mathbb{R}}\log\lvert\lambda-x_N^{J,Z}(\sigma)\rvert\,\mu_{N-1}^{J,g,\sigma}(\mathrm{d}\lambda)
\le\int_{\mathbb{R}}\log_\eta\left(\lambda-x_N^{J,Z}(\sigma)\right)\mu_{N-1}^{J,g,\sigma}(\mathrm{d}\lambda) \\
&= A_i+B_i+C_i+D_i+E_i+\Omega(x_i). \tag*{(49)}
\end{aligned} ∫ R log ∣ λ − x N J , Z ( σ )∣ μ N − 1 J , g , σ ( d λ ) ≤ ∫ R log η ( λ − x N J , Z ( σ ) ) μ N − 1 J , g , σ ( d λ ) = A i + B i + C i + D i + E i + Ω ( x i ) . (49)
From (45) , (46) , (48) , and (49) , it follows that
E J , g , Z [ e − N t 2 p ( 1 − t ) y N J ( σ ) ∣ det ( M N − 1 J , g ( σ ) − x N J , Z ( σ ) I N − 1 ) ∣ ⋅ 1 { x N J , Z ( σ ) ∈ U N ( u ) } ] ≤ e − c 8 N M 2 + ∑ i = 1 n E J , g , Z [ e − N t 2 p ( 1 − t ) y N J ( σ ) e ( N − 1 ) ( A i + B i + C i + D i + E i ) 1 { x N J , Z ( σ ) ∈ B ( x i , δ ) } ] e ( N − 1 ) Ω ( x i ) . (50) \begin{aligned}
\mathbb{E}_{J,g,Z}\left[\mathrm{e}^{-\frac{Nt}{2p(1-t)}y_N^J(\sigma)}\left\lvert\det\left(M_{N-1}^{J,g}(\sigma)-x_N^{J,Z}(\sigma)I_{N-1}\right)\right\rvert\cdot\mathbf{1}_{\{x_N^{J,Z}(\sigma)\in U_N(u)\}}\right] \\
&\le\mathrm{e}^{-c_8NM^2}+\sum_{i=1}^{n}\mathbb{E}_{J,g,Z}\left[\mathrm{e}^{-\frac{Nt}{2p(1-t)}y_N^J(\sigma)}\mathrm{e}^{(N-1)(A_i+B_i+C_i+D_i+E_i)}\mathbf{1}_{\{x_N^{J,Z}(\sigma)\in B(x_i,\delta)\}}\right]\mathrm{e}^{(N-1)\Omega(x_i)}. \tag*{(50)}
\end{aligned} E J , g , Z [ e − 2 p ( 1 − t ) N t y N J ( σ ) det ( M N − 1 J , g ( σ ) − x N J , Z ( σ ) I N − 1 ) ⋅ 1 { x N J , Z ( σ ) ∈ U N ( u )} ] ≤ e − c 8 N M 2 + i = 1 ∑ n E J , g , Z [ e − 2 p ( 1 − t ) N t y N J ( σ ) e ( N − 1 ) ( A i + B i + C i + D i + E i ) 1 { x N J , Z ( σ ) ∈ B ( x i , δ )} ] e ( N − 1 ) Ω ( x i ) . (50)
Now, we estimate the five terms in (49) individually.
1 ∘ 1^\circ 1 ∘ On the event { x N J , Z ( σ ) ∈ B ( x i , δ ) } \{x_N^{J,Z}(\sigma)\in B(x_i,\delta)\} { x N J , Z ( σ ) ∈ B ( x i , δ )} , since log η \log_\eta log η is ( 2 η ) − 1 (2\eta)^{-1} ( 2 η ) − 1 -Lipschitz, we have
A i ≤ δ 2 η . (51) A_i\le\frac{\delta}{2\eta}. \tag*{(51)} A i ≤ 2 η δ . (51)
2 ∘ 2^\circ 2 ∘ For C i C_i C i , we see from (30) that
C i ≤ sup σ , ∣ x ∣ ≤ M , η > 0 ∫ R ( log η ( λ − x ) − log η K ( λ − x ) ) E J , g [ μ N − 1 J , g , σ ] ( d λ ) ≤ c 6 M 2 K 2 = c 6 M 2 . (52) C_i\le\sup_{\sigma,\lvert x\rvert\le M,\eta>0}\int_{\mathbb{R}}\left(\log_\eta(\lambda-x)-\log_\eta^K(\lambda-x)\right)\mathbb{E}_{J,g}\left[\mu_{N-1}^{J,g,\sigma}\right](\mathrm{d}\lambda)\le\frac{c_6M^2}{K^2}=\frac{c_6}{M^2}. \tag*{(52)} C i ≤ σ , ∣ x ∣ ≤ M , η > 0 sup ∫ R ( log η ( λ − x ) − log η K ( λ − x ) ) E J , g [ μ N − 1 J , g , σ ] ( d λ ) ≤ K 2 c 6 M 2 = M 2 c 6 . (52)
3 ∘ 3^\circ 3 ∘ For D i D_i D i , we see from (33) that
D i ≤ log η ( K ) 2 η sup σ d B L ( E J , g [ μ N − 1 J , g , σ ] , μ s c ) = : r N ( η , K ) = o N ( 1 ) (53) D_i\le\frac{\log_\eta(K)}{2\eta}\sup_\sigma d_{\mathrm{BL}}\left(\mathbb{E}_{J,g}\left[\mu_{N-1}^{J,g,\sigma}\right],\mu_{\mathrm{sc}}\right)=:r_N(\eta,K)=o_N(1) \tag*{(53)} D i ≤ 2 η log η ( K ) σ sup d BL ( E J , g [ μ N − 1 J , g , σ ] , μ sc ) =: r N ( η , K ) = o N ( 1 ) (53)
for each fixed η > 0 \eta>0 η > 0 and K > 0 K>0 K > 0 .
4° From (41) , we see that since K ≥ M + 2 K \ge M + 2 K ≥ M + 2 and ∣ x i ∣ ≤ M |x_i| \le M ∣ x i ∣ ≤ M ,
E i ≤ η . (54) E_i \le\eta. \tag*{(54)} E i ≤ η . (54)
5° Let us consider the term B i = W η , N J , g ( σ , x i ) − E J , g [ W η , N J , g ( σ , x i ) ] B_i = W_{\eta,N}^{J,g}(\sigma,x_i)-\mathbb{E}_{J,g}[W_{\eta,N}^{J,g}(\sigma,x_i)] B i = W η , N J , g ( σ , x i ) − E J , g [ W η , N J , g ( σ , x i )] . From (23) and (24) it follows that there exists some c 9 = c 9 ( κ S G , p ) > 0 c_9=c_9(\kappa_{\mathrm{SG}},p)>0 c 9 = c 9 ( κ SG , p ) > 0 such that for sufficiently large N N N ,
E J , g , Z [ e − N t 2 p ( 1 − t ) y N J ( σ ) ⋅ e ( N − 1 ) B i 1 { x N J , Z ( σ ) ∈ B ( x i , δ ) } ] ≤ e ( N − 1 ) h ⋅ E J , Z [ e − N t 2 p ( 1 − t ) y N J ( σ ) 1 { x N J , Z ( σ ) ∈ B ( x i , δ ) } ] + E J , g , Z [ e ( N − 1 ) B i 1 { ∣ B i ∣ ≥ h } ] ≤ e ( N − 1 ) h ⋅ E J , Z [ e − N t 2 p ( 1 − t ) y N J ( σ ) 1 { x N J , Z ( σ ) ∈ B ( x i , δ ) } ] + ( c 2 − 1 e ( N − 1 ) 2 log N c 2 η 2 N 2 ⋅ c 2 − 1 e − c 2 η 2 N 2 h 2 log N ) 1 / 2 ≤ e ( N − 1 ) h E J , Z [ e − N t 2 p ( 1 − t ) y N J ( σ ) 1 { x N J , Z ( σ ) ∈ B ( x i , δ ) } ] + c 9 − 1 e − c 9 η 2 N 2 h 2 / log N . (55) \begin{aligned}
\mathbb{E}_{J,g,Z}\left[e^{-\frac{Nt}{2p(1-t)}y_N^J(\sigma)}\cdot e^{(N-1)B_i}\mathbf{1}_{\{x_N^{J,Z}(\sigma)\in B(x_i,\delta)\}}\right]
&\le e^{(N-1)h}\cdot\mathbb{E}_{J,Z}\left[e^{-\frac{Nt}{2p(1-t)}y_N^J(\sigma)}\mathbf{1}_{\{x_N^{J,Z}(\sigma)\in B(x_i,\delta)\}}\right]\\
&\quad+\mathbb{E}_{J,g,Z}\left[e^{(N-1)B_i}\mathbf{1}_{\{|B_i|\ge h\}}\right]\\
&\le e^{(N-1)h}\cdot\mathbb{E}_{J,Z}\left[e^{-\frac{Nt}{2p(1-t)}y_N^J(\sigma)}\mathbf{1}_{\{x_N^{J,Z}(\sigma)\in B(x_i,\delta)\}}\right]\\
&\quad+\left(c_2^{-1}e^{\frac{(N-1)^2\log N}{c_2\eta^2N^2}}\cdot c_2^{-1}e^{-\frac{c_2\eta^2N^2h^2}{\log N}}\right)^{1/2}\\
&\le e^{(N-1)h}\mathbb{E}_{J,Z}\left[e^{-\frac{Nt}{2p(1-t)}y_N^J(\sigma)}\mathbf{1}_{\{x_N^{J,Z}(\sigma)\in B(x_i,\delta)\}}\right]+c_9^{-1}e^{-c_9\eta^2N^2h^2/\log N}. \tag*{(55)}
\end{aligned} E J , g , Z [ e − 2 p ( 1 − t ) N t y N J ( σ ) ⋅ e ( N − 1 ) B i 1 { x N J , Z ( σ ) ∈ B ( x i , δ )} ] ≤ e ( N − 1 ) h ⋅ E J , Z [ e − 2 p ( 1 − t ) N t y N J ( σ ) 1 { x N J , Z ( σ ) ∈ B ( x i , δ )} ] + E J , g , Z [ e ( N − 1 ) B i 1 { ∣ B i ∣ ≥ h } ] ≤ e ( N − 1 ) h ⋅ E J , Z [ e − 2 p ( 1 − t ) N t y N J ( σ ) 1 { x N J , Z ( σ ) ∈ B ( x i , δ )} ] + ( c 2 − 1 e c 2 η 2 N 2 ( N − 1 ) 2 l o g N ⋅ c 2 − 1 e − l o g N c 2 η 2 N 2 h 2 ) 1/2 ≤ e ( N − 1 ) h E J , Z [ e − 2 p ( 1 − t ) N t y N J ( σ ) 1 { x N J , Z ( σ ) ∈ B ( x i , δ )} ] + c 9 − 1 e − c 9 η 2 N 2 h 2 / l o g N . (55)
Combining (50) , (51) , (52) , (53) , (54) , and (55) , and then averaging over σ \sigma σ , we obtain
L N ( u ) ≤ e − c 8 N M 2 + e ( N − 1 ) ( δ 2 η + η + c 6 M 2 + r N ( η , K ) ) ∑ i = 1 n e ( N − 1 ) Ω ( x i ) ( e ( N − 1 ) h ℓ N ( x i , δ ) + a N ) . (56) \mathcal{L}_N(u)\le e^{-c_8NM^2}+e^{(N-1)\left(\frac{\delta}{2\eta}+\eta+\frac{c_6}{M^2}+r_N(\eta,K)\right)}\sum_{i=1}^{n}e^{(N-1)\Omega(x_i)}\left(e^{(N-1)h}\ell_N(x_i,\delta)+a_N\right). \tag*{(56)} L N ( u ) ≤ e − c 8 N M 2 + e ( N − 1 ) ( 2 η δ + η + M 2 c 6 + r N ( η , K ) ) i = 1 ∑ n e ( N − 1 ) Ω ( x i ) ( e ( N − 1 ) h ℓ N ( x i , δ ) + a N ) . (56)
where a N = c 9 − 1 e − c 9 η 2 N 2 h 2 / log N a_N=c_9^{-1}e^{-c_9\eta^2N^2h^2/\log N} a N = c 9 − 1 e − c 9 η 2 N 2 h 2 / l o g N . From the formula (3) , we see that there exists an absolute constant c 10 > 0 c_{10}>0 c 10 > 0 such that Ω ( x ) ≤ c 10 x 2 \Omega(x)\le c_{10}x^2 Ω ( x ) ≤ c 10 x 2 for all x ∈ R x\in\mathbb{R} x ∈ R . Therefore,
a N ∑ i = 1 n e ( N − 1 ) Ω ( x i ) ≤ n e ( N − 1 ) c 10 M 2 − c 9 η 2 N 2 h 2 / log N (57) a_N\sum_{i=1}^{n}e^{(N-1)\Omega(x_i)}\le ne^{(N-1)c_{10}M^2-c_9\eta^2N^2h^2/\log N} \tag*{(57)} a N i = 1 ∑ n e ( N − 1 ) Ω ( x i ) ≤ n e ( N − 1 ) c 10 M 2 − c 9 η 2 N 2 h 2 / l o g N (57)
Since the cover is finite and independent of N N N , (56) , (57) , and r N ( η , K ) → 0 r_N(\eta,K)\to0 r N ( η , K ) → 0 imply that
lim sup N → ∞ 1 N log L N ( u ) ≤ max { − c 8 M 2 , δ 2 η + η + h + c 6 M 2 + sup − M ≤ x ≤ 2 u / E ∞ { Ω ( x ) + lim sup N → ∞ 1 N log ℓ N ( x , δ ) } } . (58) \begin{aligned}
\limsup_{N\to\infty}\frac{1}{N}\log\mathcal{L}_N(u)
\le\max\left\{-c_8M^2,\frac{\delta}{2\eta}+\eta+h+\frac{c_6}{M^2}
+\sup_{-M\le x\le2u/E_\infty}\left\{\Omega(x)+\limsup_{N\to\infty}\frac{1}{N}\log\ell_N(x,\delta)\right\}\right\}. \tag*{(58)}
\end{aligned} N → ∞ lim sup N 1 log L N ( u ) ≤ max { − c 8 M 2 , 2 η δ + η + h + M 2 c 6 + − M ≤ x ≤ 2 u / E ∞ sup { Ω ( x ) + N → ∞ lim sup N 1 log ℓ N ( x , δ ) } } . (58)
Here the term in (57) is superexponentially small for fixed M , η , h > 0 M,\eta,h>0 M , η , h > 0 . Letting M ↑ ∞ M\uparrow\infty M ↑ ∞ in (58) gives
lim sup N → ∞ 1 N log L N ( u ) ≤ δ 2 η + η + h + sup x ≤ 2 u / E ∞ { Ω ( x ) + lim sup N → ∞ 1 N log ℓ N ( x , δ ) } . \limsup_{N\to\infty}\frac{1}{N}\log\mathcal{L}_N(u)\le\frac{\delta}{2\eta}+\eta+h+\sup_{x\le2u/E_\infty}\left\{\Omega(x)+\limsup_{N\to\infty}\frac{1}{N}\log\ell_N(x,\delta)\right\}. N → ∞ lim sup N 1 log L N ( u ) ≤ 2 η δ + η + h + x ≤ 2 u / E ∞ sup { Ω ( x ) + N → ∞ lim sup N 1 log ℓ N ( x , δ ) } .
For fixed η , h > 0 \eta,h>0 η , h > 0 , let δ ↓ 0 \delta\downarrow0 δ ↓ 0 , and then let η , h ↓ 0 \eta,h\downarrow0 η , h ↓ 0 . The limit in δ \delta δ exists in [ − ∞ , ∞ ) [-\infty,\infty) [ − ∞ , ∞ ) because ℓ N ( x , δ ) \ell_N(x,\delta) ℓ N ( x , δ ) is nonincreasing in δ \delta δ . This proves the proposition.
Lower Bound
Proposition 5.3. If { J I } I ∈ [ N ] p , N ∈ N \{J_I\}_{I\in[N]^p,N\in\mathbb{N}} { J I } I ∈ [ N ] p , N ∈ N satisfies (SG) with uniform κ S G \kappa_{\mathrm{SG}} κ SG , then, for u ∈ R u\in\mathbb{R} u ∈ R ,
lim inf N → ∞ 1 N log L N ( u ) ≥ sup x < 2 u / E ∞ { Ω ( x ) + lim δ → 0 lim inf N → ∞ 1 N log ℓ N ( x , δ ) } . (59) \liminf_{N\to\infty}\frac{1}{N}\log\mathcal{L}_N(u)\ge\sup_{x<2u/E_\infty}\left\{\Omega(x)+\lim_{\delta\to0}\liminf_{N\to\infty}\frac{1}{N}\log\ell_N(x,\delta)\right\}. \tag*{(59)} N → ∞ lim inf N 1 log L N ( u ) ≥ x < 2 u / E ∞ sup { Ω ( x ) + δ → 0 lim N → ∞ lim inf N 1 log ℓ N ( x , δ ) } . (59)
Proof. Fix h > 0 h>0 h > 0 and let M ≥ 1 + ∣ 2 u / E ∞ ∣ M\geq1+\lvert2u/E_{\infty}\rvert M ≥ 1 + ∣ 2 u / E ∞ ∣ , K ≥ M + 2 K\geq M+2 K ≥ M + 2 be parameters to be chosen sufficiently large. Fix − M ≤ x < 2 u / E ∞ -M\leq x<2u/E_{\infty} − M ≤ x < 2 u / E ∞ . Choose ϵ > 0 \epsilon>0 ϵ > 0 such that x + ϵ < 2 u / E ∞ x+\epsilon<2u/E_{\infty} x + ϵ < 2 u / E ∞ and let 0 < δ < ϵ 0<\delta<\epsilon 0 < δ < ϵ . Then for sufficiently large N N N , B ( x , δ ) ⊆ U N ( u ) B(x,\delta)\subseteq U_N(u) B ( x , δ ) ⊆ U N ( u ) . Let η = η ( h , t ) > 0 \eta=\eta(h,t)>0 η = η ( h , t ) > 0 be chosen later.
We introduce the following notations
A = ∫ R ( log ∣ λ − x N J , Z ( σ ) ∣ − log η ( λ − x N J , Z ( σ ) ) ) μ N − 1 J , g , σ ( d λ ) . A=\int_{\mathbb{R}}\left(\log\lvert\lambda-x_N^{J,Z}(\sigma)\rvert-\log_{\eta}(\lambda-x_N^{J,Z}(\sigma))\right)\mu_{N-1}^{J,g,\sigma}(\mathrm{d}\lambda). A = ∫ R ( log ∣ λ − x N J , Z ( σ )∣ − log η ( λ − x N J , Z ( σ )) ) μ N − 1 J , g , σ ( d λ ) .
B = ∫ R ( log η ( λ − x N J , Z ( σ ) ) − log η ( λ − x ) ) μ N − 1 J , g , σ ( d λ ) . B=\int_{\mathbb{R}}\left(\log_{\eta}(\lambda-x_N^{J,Z}(\sigma))-\log_{\eta}(\lambda-x)\right)\mu_{N-1}^{J,g,\sigma}(\mathrm{d}\lambda). B = ∫ R ( log η ( λ − x N J , Z ( σ )) − log η ( λ − x ) ) μ N − 1 J , g , σ ( d λ ) .
C = ∫ R log η ( λ − x ) ( μ N − 1 J , g , σ − E g [ μ N − 1 J , g , σ ] ) ( d λ ) . C=\int_{\mathbb{R}}\log_{\eta}(\lambda-x)\left(\mu_{N-1}^{J,g,\sigma}-\mathbb{E}_{g}\left[\mu_{N-1}^{J,g,\sigma}\right]\right)(\mathrm{d}\lambda). C = ∫ R log η ( λ − x ) ( μ N − 1 J , g , σ − E g [ μ N − 1 J , g , σ ] ) ( d λ ) .
D = ∫ R log η ( λ − x ) ( E g [ μ N − 1 J , g , σ ] − E J , g [ μ N − 1 J , g , σ ] ) ( d λ ) . D=\int_{\mathbb{R}}\log_{\eta}(\lambda-x)\left(\mathbb{E}_{g}\left[\mu_{N-1}^{J,g,\sigma}\right]-\mathbb{E}_{J,g}\left[\mu_{N-1}^{J,g,\sigma}\right]\right)(\mathrm{d}\lambda). D = ∫ R log η ( λ − x ) ( E g [ μ N − 1 J , g , σ ] − E J , g [ μ N − 1 J , g , σ ] ) ( d λ ) .
E = ∫ R ( log η ( λ − x ) − log η K ( λ − x ) ) E J , g [ μ N − 1 J , g , σ ] ( d λ ) . E=\int_{\mathbb{R}}\left(\log_{\eta}(\lambda-x)-\log_{\eta}^{K}(\lambda-x)\right)\mathbb{E}_{J,g}\left[\mu_{N-1}^{J,g,\sigma}\right](\mathrm{d}\lambda). E = ∫ R ( log η ( λ − x ) − log η K ( λ − x ) ) E J , g [ μ N − 1 J , g , σ ] ( d λ ) .
F = ∫ R log η K ( λ − x ) ( E J , g [ μ N − 1 J , g , σ ] − μ s c ) ( d λ ) . F=\int_{\mathbb{R}}\log_{\eta}^{K}(\lambda-x)\left(\mathbb{E}_{J,g}\left[\mu_{N-1}^{J,g,\sigma}\right]-\mu_{\mathrm{sc}}\right)(\mathrm{d}\lambda). F = ∫ R log η K ( λ − x ) ( E J , g [ μ N − 1 J , g , σ ] − μ sc ) ( d λ ) .
Then
∫ R log ∣ λ − x N J , Z ( σ ) ∣ μ N − 1 J , g , σ ( d λ ) = A + B + C + D + E + ∫ R log η K ( λ − x ) μ s c ( d λ ) . (60) \int_{\mathbb{R}}\log\lvert\lambda-x_N^{J,Z}(\sigma)\rvert\mu_{N-1}^{J,g,\sigma}(\mathrm{d}\lambda)=A+B+C+D+E+\int_{\mathbb{R}}\log_{\eta}^{K}(\lambda-x)\mu_{\mathrm{sc}}(\mathrm{d}\lambda). \tag*{(60)} ∫ R log ∣ λ − x N J , Z ( σ )∣ μ N − 1 J , g , σ ( d λ ) = A + B + C + D + E + ∫ R log η K ( λ − x ) μ sc ( d λ ) . (60)
Conditioning on ( σ , J , Z ) (\sigma,J,Z) ( σ , J , Z ) , the terms D D D and E E E do not depend on g g g , while E g [ C ] = 0 \mathbb{E}_{g}[C]=0 E g [ C ] = 0 . Moreover, E ≥ 0 E\geq0 E ≥ 0 since log η ( λ − x ) − log η K ( λ − x ) ≥ 0 \log_{\eta}(\lambda-x)-\log_{\eta}^{K}(\lambda-x)\geq0 log η ( λ − x ) − log η K ( λ − x ) ≥ 0 . Hence, by Jensen’s inequality,
E g [ e ( N − 1 ) ( A + B + C + D + E + F ) ] ≥ exp ( ( N − 1 ) ( E g [ A + B ] + D + F ) ) . \mathbb{E}_{g}\left[e^{(N-1)(A+B+C+D+E+F)}\right]\geq\exp\left((N-1)\left(\mathbb{E}_{g}[A+B]+D+F\right)\right). E g [ e ( N − 1 ) ( A + B + C + D + E + F ) ] ≥ exp ( ( N − 1 ) ( E g [ A + B ] + D + F ) ) .
Moreover, since K ≥ M + 2 K\geq M+2 K ≥ M + 2 and ∣ x ∣ ≤ M \lvert x\rvert\leq M ∣ x ∣ ≤ M , we have by (41) that
∫ R log η K ( λ − x ) μ s c ( d λ ) ≥ ∫ R log ∣ λ − x ∣ μ s c ( d λ ) = Ω ( x ) . \int_{\mathbb{R}}\log_{\eta}^{K}(\lambda-x)\mu_{\mathrm{sc}}(\mathrm{d}\lambda)\geq\int_{\mathbb{R}}\log\lvert\lambda-x\rvert\mu_{\mathrm{sc}}(\mathrm{d}\lambda)=\Omega(x). ∫ R log η K ( λ − x ) μ sc ( d λ ) ≥ ∫ R log ∣ λ − x ∣ μ sc ( d λ ) = Ω ( x ) .
Therefore, for every fixed σ \sigma σ and for all sufficiently large N N N ,
E J , g , Z [ e − N t 2 p ( 1 − t ) y N J ( σ ) ∣ det ( M N − 1 J , g ( σ ) − x N J , Z ( σ ) I N − 1 ) ∣ ⋅ 1 { x N J , Z ( σ ) ∈ U N ( u ) } ] ≥ e ( N − 1 ) Ω ( x ) E J , Z [ e − N t 2 p ( 1 − t ) y N J ( σ ) ⋅ e ( N − 1 ) ( E g [ A + B ] + D + F ) ⋅ 1 { x N J , Z ( σ ) ∈ B ( x , δ ) } ] . (61) \begin{aligned}
\mathbb{E}_{J,g,Z}\left[e^{-\frac{Nt}{2p(1-t)}y_N^{J}(\sigma)}\left\lvert\det\left(M_{N-1}^{J,g}(\sigma)-x_N^{J,Z}(\sigma)I_{N-1}\right)\right\rvert\cdot\mathbf{1}_{\{x_N^{J,Z}(\sigma)\in U_N(u)\}}\right] \\
&\geq e^{(N-1)\Omega(x)}\mathbb{E}_{J,Z}\left[e^{-\frac{Nt}{2p(1-t)}y_N^{J}(\sigma)}\cdot e^{(N-1)(\mathbb{E}_{g}[A+B]+D+F)}\cdot\mathbf{1}_{\{x_N^{J,Z}(\sigma)\in B(x,\delta)\}}\right]. \tag*{(61)}
\end{aligned} E J , g , Z [ e − 2 p ( 1 − t ) N t y N J ( σ ) det ( M N − 1 J , g ( σ ) − x N J , Z ( σ ) I N − 1 ) ⋅ 1 { x N J , Z ( σ ) ∈ U N ( u )} ] ≥ e ( N − 1 ) Ω ( x ) E J , Z [ e − 2 p ( 1 − t ) N t y N J ( σ ) ⋅ e ( N − 1 ) ( E g [ A + B ] + D + F ) ⋅ 1 { x N J , Z ( σ ) ∈ B ( x , δ )} ] . (61)
Now, we estimate the four terms in (61) individually.
1 ∘ 1^\circ 1 ∘ For A A A , we see from Lemma 4.7 that uniform over deterministic realizations J ∈ R [ N ] p J\in\mathbb{R}^{[N]^{p}} J ∈ R [ N ] p , σ ∈ N S N − 1 \sigma\in\sqrt{N}\mathbb{S}^{N-1} σ ∈ N S N − 1 and x ∈ R x\in\mathbb{R} x ∈ R , there exists η = η ( h , t ) > 0 \eta=\eta(h,t)>0 η = η ( h , t ) > 0 so small so that
sup N ≥ 2 sup J , σ , x ∫ R ( log η ( λ − x ) − log ∣ λ − x ∣ ) E g [ μ N − 1 J , g , σ ] ( d λ ) ≤ h . (62) \sup_{N\geq2}\sup_{J,\sigma,x}\int_{\mathbb{R}}\left(\log_{\eta}(\lambda-x)-\log\lvert\lambda-x\rvert\right)\mathbb{E}_{g}\left[\mu_{N-1}^{J,g,\sigma}\right](\mathrm{d}\lambda)\leq h. \tag*{(62)} N ≥ 2 sup J , σ , x sup ∫ R ( log η ( λ − x ) − log ∣ λ − x ∣ ) E g [ μ N − 1 J , g , σ ] ( d λ ) ≤ h . (62)
Taking x = x N J , Z ( σ ) x=x_N^{J,Z}(\sigma) x = x N J , Z ( σ ) in (62) then gives
E g [ A ] = − ∫ R ( log η ( λ − x N J , Z ( σ ) ) − log ∣ λ − x N J , Z ( σ ) ∣ ) E g [ μ N − 1 J , g , σ ] ( d λ ) ≥ − h . (63) \mathbb{E}_{g}[A]=-\int_{\mathbb{R}}\left(\log_{\eta}(\lambda-x_N^{J,Z}(\sigma))-\log\lvert\lambda-x_N^{J,Z}(\sigma)\rvert\right)\mathbb{E}_{g}\left[\mu_{N-1}^{J,g,\sigma}\right](\mathrm{d}\lambda)\geq-h. \tag*{(63)} E g [ A ] = − ∫ R ( log η ( λ − x N J , Z ( σ )) − log ∣ λ − x N J , Z ( σ )∣ ) E g [ μ N − 1 J , g , σ ] ( d λ ) ≥ − h . (63)
2° On the event { x N J , Z ( σ ) ∈ B ( x , δ ) } \{x_N^{J,Z}(\sigma) \in B(x,\delta)\} { x N J , Z ( σ ) ∈ B ( x , δ )} , since log η \log_\eta log η is ( 2 η ) − 1 (2\eta)^{-1} ( 2 η ) − 1 -Lipschitz, we have
B ≥ − δ 2 η . (64) B \ge-\frac{\delta}{2\eta}. \tag*{(64)} B ≥ − 2 η δ . (64)
3° For F F F , we see from (33) that
F ≥ − log η ( K ) 2 η sup σ d B L ( E J , g [ μ N − 1 J , g , σ ] , μ s c ) = − r N ( η , K ) = o N ( 1 ) (65) F \ge-\frac{\log_\eta(K)}{2\eta}\sup_{\sigma}d_{\mathrm{BL}}\left(\mathbb{E}_{J,g}\left[\mu_{N-1}^{J,g,\sigma}\right],\mu_{\mathrm{sc}}\right)=-r_N(\eta,K)=o_N(1) \tag*{(65)} F ≥ − 2 η log η ( K ) σ sup d BL ( E J , g [ μ N − 1 J , g , σ ] , μ sc ) = − r N ( η , K ) = o N ( 1 ) (65)
for each fixed η > 0 \eta>0 η > 0 and K > 0 K>0 K > 0 .
4° Finally, we analyze the term D D D . Applying the same argument as in Lemma 4.2 to the mapping J ↦ E g [ W η , N J , g ( σ , x ) ] J\mapsto\mathbb{E}_g\left[W_{\eta,N}^{J,g}(\sigma,x)\right] J ↦ E g [ W η , N J , g ( σ , x ) ] , we obtain the same concentration estimate as in (23) . More precisely, for all h ≥ 0 h\ge0 h ≥ 0 ,
sup σ , x P J ( ∣ D ∣ ≥ h ) ≤ c 2 − 1 exp ( − c 2 η 2 N 2 h 2 log N ) . \sup_{\sigma,x}\mathbb{P}_J(|D|\ge h)\le c_2^{-1}\exp\left(-\frac{c_2\eta^2N^2h^2}{\log N}\right). σ , x sup P J ( ∣ D ∣ ≥ h ) ≤ c 2 − 1 exp ( − log N c 2 η 2 N 2 h 2 ) .
Therefore,
E J , Z [ e − N t 2 p ( 1 − t ) y N J ( σ ) ⋅ e ( N − 1 ) D ⋅ 1 { x N J , Z ( σ ) ∈ B ( x , δ ) } ] ≥ e − ( N − 1 ) h ⋅ E J , Z [ e − N t 2 p ( 1 − t ) y N J ( σ ) ⋅ 1 { x N J , Z ( σ ) ∈ B ( x , δ ) } ⋅ 1 { ∣ D ∣ ≤ h } ] ≥ e − ( N − 1 ) h ( E J , Z [ e − N t 2 p ( 1 − t ) y N J ( σ ) ⋅ 1 { x N J , Z ( σ ) ∈ B ( x , δ ) } ] − c 2 − 1 e − c 2 η 2 N 2 h 2 / log N ) . (66) \begin{aligned}
\mathbb{E}_{J,Z}\left[e^{-\frac{Nt}{2p(1-t)}y_N^J(\sigma)}\cdot e^{(N-1)D}\cdot\mathbf{1}_{\{x_N^{J,Z}(\sigma)\in B(x,\delta)\}}\right]
&\ge e^{-(N-1)h}\cdot\mathbb{E}_{J,Z}\left[e^{-\frac{Nt}{2p(1-t)}y_N^J(\sigma)}\cdot\mathbf{1}_{\{x_N^{J,Z}(\sigma)\in B(x,\delta)\}}\cdot\mathbf{1}_{\{|D|\le h\}}\right]\\
&\ge e^{-(N-1)h}\left(\mathbb{E}_{J,Z}\left[e^{-\frac{Nt}{2p(1-t)}y_N^J(\sigma)}\cdot\mathbf{1}_{\{x_N^{J,Z}(\sigma)\in B(x,\delta)\}}\right]-c_2^{-1}e^{-c_2\eta^2N^2h^2/\log N}\right). \tag*{(66)}
\end{aligned} E J , Z [ e − 2 p ( 1 − t ) N t y N J ( σ ) ⋅ e ( N − 1 ) D ⋅ 1 { x N J , Z ( σ ) ∈ B ( x , δ )} ] ≥ e − ( N − 1 ) h ⋅ E J , Z [ e − 2 p ( 1 − t ) N t y N J ( σ ) ⋅ 1 { x N J , Z ( σ ) ∈ B ( x , δ )} ⋅ 1 { ∣ D ∣ ≤ h } ] ≥ e − ( N − 1 ) h ( E J , Z [ e − 2 p ( 1 − t ) N t y N J ( σ ) ⋅ 1 { x N J , Z ( σ ) ∈ B ( x , δ )} ] − c 2 − 1 e − c 2 η 2 N 2 h 2 / l o g N ) . (66)
Combining (61) , (63) , (64) , (65) , and (66) , and then averaging over σ \sigma σ , gives
L N ( u ) ≥ exp [ ( N − 1 ) ( Ω ( x ) − 2 h − δ 2 η − r N ( η , K ) ) ] ( ℓ N ( x , δ ) − b N ) , (67) \mathcal{L}_N(u)\ge\exp\left[(N-1)\left(\Omega(x)-2h-\frac{\delta}{2\eta}-r_N(\eta,K)\right)\right]\left(\ell_N(x,\delta)-b_N\right), \tag*{(67)} L N ( u ) ≥ exp [ ( N − 1 ) ( Ω ( x ) − 2 h − 2 η δ − r N ( η , K ) ) ] ( ℓ N ( x , δ ) − b N ) , (67)
where b N = c 2 − 1 e − c 2 η 2 N 2 h 2 / log N b_N=c_2^{-1}e^{-c_2\eta^2N^2h^2/\log N} b N = c 2 − 1 e − c 2 η 2 N 2 h 2 / l o g N . Set
ℓ ( x , δ ) : = lim inf N → ∞ 1 N log ℓ N ( x , δ ) . \ell(x,\delta):=\liminf_{N\to\infty}\frac{1}{N}\log\ell_N(x,\delta). ℓ ( x , δ ) := N → ∞ lim inf N 1 log ℓ N ( x , δ ) .
We claim that
lim inf N → ∞ 1 N log L N ( u ) ≥ Ω ( x ) − 2 h − δ 2 η + ℓ ( x , δ ) . (68) \liminf_{N\to\infty}\frac{1}{N}\log\mathcal{L}_N(u)\ge\Omega(x)-2h-\frac{\delta}{2\eta}+\ell(x,\delta). \tag*{(68)} N → ∞ lim inf N 1 log L N ( u ) ≥ Ω ( x ) − 2 h − 2 η δ + ℓ ( x , δ ) . (68)
If ℓ ( x , δ ) = − ∞ \ell(x,\delta)=-\infty ℓ ( x , δ ) = − ∞ , the desired lower bound for this fixed x x x and δ \delta δ is automatic. Suppose instead that ℓ ( x , δ ) > − ∞ \ell(x,\delta)>-\infty ℓ ( x , δ ) > − ∞ . Then, for every ρ > 0 \rho>0 ρ > 0 and all sufficiently large N N N ,
ℓ N ( x , δ ) ≥ exp ( N ( ℓ ( x , δ ) − ρ ) ) . \ell_N(x,\delta)\ge\exp\left(N(\ell(x,\delta)-\rho)\right). ℓ N ( x , δ ) ≥ exp ( N ( ℓ ( x , δ ) − ρ ) ) .
Since b N b_N b N is superexponentially small, ℓ N ( x , δ ) − b N > 0 \ell_N(x,\delta)-b_N>0 ℓ N ( x , δ ) − b N > 0 for all sufficiently large N N N , and
lim inf N → ∞ 1 N log ( ℓ N ( x , δ ) − b N ) = lim inf N → ∞ 1 N log ℓ N ( x , δ ) = ℓ ( x , δ ) . \liminf_{N\to\infty}\frac{1}{N}\log\left(\ell_N(x,\delta)-b_N\right)=\liminf_{N\to\infty}\frac{1}{N}\log\ell_N(x,\delta)=\ell(x,\delta). N → ∞ lim inf N 1 log ( ℓ N ( x , δ ) − b N ) = N → ∞ lim inf N 1 log ℓ N ( x , δ ) = ℓ ( x , δ ) .
Hence, Claim (68) now follows from (67) . For the fixed h > 0 h>0 h > 0 and the corresponding fixed η = η ( h , t ) > 0 \eta=\eta(h,t)>0 η = η ( h , t ) > 0 , let δ ↓ 0 \delta\downarrow0 δ ↓ 0 in (68) . This yields
lim inf N → ∞ 1 N log L N ( u ) ≥ Ω ( x ) − 2 h + lim δ ↓ 0 ℓ ( x , δ ) . \liminf_{N\to\infty}\frac{1}{N}\log\mathcal{L}_N(u)\ge\Omega(x)-2h+\lim_{\delta\downarrow0}\ell(x,\delta). N → ∞ lim inf N 1 log L N ( u ) ≥ Ω ( x ) − 2 h + δ ↓ 0 lim ℓ ( x , δ ) .
Next let h ↓ 0 h\downarrow0 h ↓ 0 . Since x < 2 u / E ∞ x<2u/E_\infty x < 2 u / E ∞ was arbitrary, taking the supremum over such x x x proves the proposition.
Convergence of Joint Moment Generating Function
Set the random variable
X N J ( σ ) = H N J ( σ ) N ( N − 1 ) (69) X_N^J(\sigma)=\frac{H_N^J(\sigma)}{\sqrt{N(N-1)}} \tag*{(69)} X N J ( σ ) = N ( N − 1 ) H N J ( σ ) (69)
and recall y N J ( σ ) y_N^J(\sigma) y N J ( σ ) from (13) . Consider the joint moment generating function
Λ N ( α , β ) : = 1 N log E σ , J [ exp ( N ⟨ ( α , β ) , ( X N J ( σ ) , y N J ( σ ) ) ⟩ ) ] = 1 N log E σ , J [ exp ( α N N − 1 H N J ( σ ) + β ∥ B ( σ ) ⊤ ∇ H N J ( σ ) ∥ 2 2 ) ] . (70) \begin{aligned}
\Lambda_N(\alpha,\beta):=\frac{1}{N}\log\mathbb{E}_{\sigma,J}\left[\exp\left(N\left\langle(\alpha,\beta),(X_N^J(\sigma),y_N^J(\sigma))\right\rangle\right)\right] \\
&=\frac{1}{N}\log\mathbb{E}_{\sigma,J}\left[\exp\left(\alpha\sqrt{\frac{N}{N-1}}H_N^J(\sigma)+\beta\left\|B(\sigma)^\top\nabla H_N^J(\sigma)\right\|_2^2\right)\right]. \tag*{(70)}
\end{aligned} Λ N ( α , β ) := N 1 log E σ , J [ exp ( N ⟨ ( α , β ) , ( X N J ( σ ) , y N J ( σ )) ⟩ ) ] = N 1 log E σ , J [ exp ( α N − 1 N H N J ( σ ) + β B ( σ ) ⊤ ∇ H N J ( σ ) 2 2 ) ] . (70)
The main result of this section is the following convergence:
Theorem 6.1. If p ≥ 3 p\ge3 p ≥ 3 and { J I } I ∈ [ N ] p , N ∈ N \{J_I\}_{I\in[N]_p,N\in\mathbb{N}} { J I } I ∈ [ N ] p , N ∈ N satisfies (SSG), then
Λ ( α , β ) : = lim N → ∞ Λ N ( α , β ) = { α 2 2 − 1 2 log ( 1 − 2 β p ) , β < 1 2 p , ∞ , β ≥ 1 2 p . (71) \Lambda(\alpha,\beta):=\lim_{N\to\infty}\Lambda_N(\alpha,\beta)=
\begin{cases}
\frac{\alpha^2}{2}-\frac{1}{2}\log(1-2\beta p), & \beta<\frac{1}{2p},\\
\infty, & \beta\ge\frac{1}{2p}.
\end{cases} \tag*{(71)} Λ ( α , β ) := N → ∞ lim Λ N ( α , β ) = { 2 α 2 − 2 1 log ( 1 − 2 β p ) , ∞ , β < 2 p 1 , β ≥ 2 p 1 . (71)
Auxiliary Bounds
For a random variable X X X satisfying (SG), we define the complex moment generating function by
M X ( z ) = E [ e z X ] , ∀ z ∈ C . M_X(z)=\mathbb{E}\left[e^{zX}\right],\qquad\forall z\in\mathbb{C}. M X ( z ) = E [ e z X ] , ∀ z ∈ C .
Note that subgaussianity readily ensures that M X M_X M X is entire by the dominated convergence theorem.
Lemma 6.2. If X X X satisfies (SSG), then there exists absolute constant c 11 > 0 c_{11}>0 c 11 > 0 such that for all x , y ∈ R x,y\in\mathbb{R} x , y ∈ R ,
∣ M X ( x + i y ) ∣ ≤ exp ( x 2 − y 2 2 + c 11 x 4 + h ( y ) ) , (72) \left|M_X(x+iy)\right|\le\exp\left(\frac{x^2-y^2}{2}+c_{11}x^4+h(y)\right), \tag*{(72)} ∣ M X ( x + i y ) ∣ ≤ exp ( 2 x 2 − y 2 + c 11 x 4 + h ( y ) ) , (72) where h ( y ) = min { y 2 / 2 , c 11 y 4 } h(y)=\min\{y^2/2,c_{11}y^4\} h ( y ) = min { y 2 /2 , c 11 y 4 } .
Proof. Since M X ( 0 ) = 1 ≠ 0 M_X(0)=1\ne0 M X ( 0 ) = 1 = 0 , we can choose an analytic branch K X ( z ) = log M X ( z ) K_X(z)=\log M_X(z) K X ( z ) = log M X ( z ) for ∣ z ∣ |z| ∣ z ∣ sufficiently small. By condition (SSG), E [ X ] = E [ X 3 ] = 0 \mathbb{E}[X]=\mathbb{E}[X^3]=0 E [ X ] = E [ X 3 ] = 0 , and E [ X 2 ] = 1 \mathbb{E}[X^2]=1 E [ X 2 ] = 1 , there exists δ > 0 \delta>0 δ > 0 and C > 0 C>0 C > 0 so that
∣ K X ( z ) − z 2 2 ∣ ≤ C ∣ z ∣ 4 for all ∣ z ∣ < δ . \left|K_X(z)-\frac{z^2}{2}\right|\le C|z|^4\qquad\text{for all }|z|<\delta. K X ( z ) − 2 z 2 ≤ C ∣ z ∣ 4 for all ∣ z ∣ < δ .
We can enlarge C > 0 C>0 C > 0 and shrink δ > 0 \delta>0 δ > 0 if necessary so that
∣ M X ( x + i y ) ∣ ≤ exp ( x 2 − y 2 2 + C ( x 4 + y 4 ) ) for all ∣ x ∣ , ∣ y ∣ < δ . (73) \left|M_X(x+iy)\right|\le\exp\left(\frac{x^2-y^2}{2}+C(x^4+y^4)\right)\qquad\text{for all }|x|,|y|<\delta. \tag*{(73)} ∣ M X ( x + i y ) ∣ ≤ exp ( 2 x 2 − y 2 + C ( x 4 + y 4 ) ) for all ∣ x ∣ , ∣ y ∣ < δ . (73)
On the other hand, (SSG) also implies that for all x , y ∈ R x,y\in\mathbb{R} x , y ∈ R ,
∣ M X ( x + i y ) ∣ ≤ M X ( x ) ≤ exp ( x 2 2 ) ≤ exp ( x 2 − y 2 2 + y 2 2 ) . (74) \left|M_X(x+iy)\right|\le M_X(x)\le\exp\left(\frac{x^2}{2}\right)\le\exp\left(\frac{x^2-y^2}{2}+\frac{y^2}{2}\right). \tag*{(74)} ∣ M X ( x + i y ) ∣ ≤ M X ( x ) ≤ exp ( 2 x 2 ) ≤ exp ( 2 x 2 − y 2 + 2 y 2 ) . (74)
If we take c 11 = max { C , 1 / ( 2 δ 2 ) } c_{11}=\max\{C,1/(2\delta^2)\} c 11 = max { C , 1/ ( 2 δ 2 )} , then
∣ M X ( x + i y ) ∣ ≤ M X ( x ) ≤ exp ( x 2 − y 2 2 + δ 2 2 ) ≤ exp ( x 2 − y 2 2 + c 11 x 4 ) ; |M_X(x+iy)| \le M_X(x) \le\exp\left(\frac{x^2-y^2}{2}+\frac{\delta^2}{2}\right) \le\exp\left(\frac{x^2-y^2}{2}+c_{11}x^4\right); ∣ M X ( x + i y ) ∣ ≤ M X ( x ) ≤ exp ( 2 x 2 − y 2 + 2 δ 2 ) ≤ exp ( 2 x 2 − y 2 + c 11 x 4 ) ;
This concludes the proof of the lemma.
Proposition 6.3. For each N ∈ N N \in\mathbb{N} N ∈ N , let X 1 , … , X m N X_1,\ldots,X_{m_N} X 1 , … , X m N be independent random variables satisfying (SSG). Let { a j } j = 1 m N ⊆ R \{a_j\}_{j=1}^{m_N} \subseteq\mathbb{R} { a j } j = 1 m N ⊆ R and { b j } j = 1 m N ⊆ R d N \{b_j\}_{j=1}^{m_N} \subseteq\mathbb{R}^{d_N} { b j } j = 1 m N ⊆ R d N be deterministic coefficients satisfying
∑ j = 1 m N a j 2 = A N , ∑ j = 1 m N a j b j = 0 and ∑ j = 1 m N b j b j T = τ N 2 I d N . (75) \sum_{j=1}^{m_N} a_j^2=A_N,\qquad\sum_{j=1}^{m_N}a_jb_j=0\quad\text{and}\quad\sum_{j=1}^{m_N}b_jb_j^{\mathsf T}=\tau_N^2 I_{d_N}. \tag*{(75)} j = 1 ∑ m N a j 2 = A N , j = 1 ∑ m N a j b j = 0 and j = 1 ∑ m N b j b j T = τ N 2 I d N . (75) Moreover, there exists c 12 > 0 c_{12}>0 c 12 > 0 such that τ N 2 ≤ c 12 \tau_N^2\le c_{12} τ N 2 ≤ c 12 . Define for α ∈ R \alpha\in\mathbb{R} α ∈ R , γ > 0 \gamma>0 γ > 0 and v ∈ R d N v\in\mathbb{R}^{d_N} v ∈ R d N ,
R N ( α , γ , v ) = E [ exp ( α ∑ j = 1 m N a j X j − γ ∥ v + ∑ j = 1 m N b j X j ∥ 2 2 ) ] . R_N(\alpha,\gamma,v)=\mathbb{E}\left[\exp\left(\alpha\sum_{j=1}^{m_N}a_jX_j-\gamma\left\|v+\sum_{j=1}^{m_N}b_jX_j\right\|_2^2\right)\right]. R N ( α , γ , v ) = E exp α j = 1 ∑ m N a j X j − γ v + j = 1 ∑ m N b j X j 2 2 . Last, set
ρ N = max 1 ≤ j ≤ m N ( ∣ a j ∣ + ∥ b j ∥ 2 ) and Δ N = ∑ j = 1 m N ( a j 4 + ∥ b j ∥ 2 4 ) . \rho_N=\max_{1\le j\le m_N}\left(|a_j|+\|b_j\|_2\right)\quad\text{and}\quad\Delta_N=\sum_{j=1}^{m_N}\left(a_j^4+\|b_j\|_2^4\right). ρ N = 1 ≤ j ≤ m N max ( ∣ a j ∣ + ∥ b j ∥ 2 ) and Δ N = j = 1 ∑ m N ( a j 4 + ∥ b j ∥ 2 4 ) . (i) There exists c 13 = c 13 ( α , γ , c 12 ) > 0 c_{13}=c_{13}(\alpha,\gamma,c_{12})>0 c 13 = c 13 ( α , γ , c 12 ) > 0 such that
sup v ∈ R d N log R N ( α , γ , v ) ≤ α 2 A N 2 − d N 2 log ( 1 + 2 γ τ N 2 ) + c 13 Δ N (76) \sup_{v\in\mathbb{R}^{d_N}}\log R_N(\alpha,\gamma,v)\le\frac{\alpha^2A_N}{2}-\frac{d_N}{2}\log(1+2\gamma\tau_N^2)+c_{13}\Delta_N \tag*{(76)} v ∈ R d N sup log R N ( α , γ , v ) ≤ 2 α 2 A N − 2 d N log ( 1 + 2 γ τ N 2 ) + c 13 Δ N (76) (ii) If ρ N = o N ( 1 ) \rho_N=o_N(1) ρ N = o N ( 1 ) and Δ N = O N ( 1 ) \Delta_N=O_N(1) Δ N = O N ( 1 ) , then
log R N ( α , γ , 0 ) = α 2 A N 2 − d N 2 log ( 1 + 2 γ τ N 2 ) + o N ( N ) . (77) \log R_N(\alpha,\gamma,0)=\frac{\alpha^2A_N}{2}-\frac{d_N}{2}\log(1+2\gamma\tau_N^2)+o_N(N). \tag*{(77)} log R N ( α , γ , 0 ) = 2 α 2 A N − 2 d N log ( 1 + 2 γ τ N 2 ) + o N ( N ) . (77) Proof. Consider the random vector g ∼ Normal ( 0 , I d N ) g\sim\operatorname{Normal}(0,I_{d_N}) g ∼ Normal ( 0 , I d N ) ,
x j = α a j , y j = ⟨ b j , g ⟩ , and ξ N = 2 γ 1 + 2 γ τ N 2 . x_j=\alpha a_j,\qquad y_j=\langle b_j,g\rangle,\qquad\text{and}\qquad\xi_N=\sqrt{\frac{2\gamma}{1+2\gamma\tau_N^2}}. x j = α a j , y j = ⟨ b j , g ⟩ , and ξ N = 1 + 2 γ τ N 2 2 γ . Denote the function
F N ( g ) = exp ( − 1 2 ( α 2 A N + τ N 2 ∥ g ∥ 2 2 ) ) ∏ j = 1 m N M X j ( x j + i y j ) (78) F_N(g)=\exp\left(-\frac{1}{2}\left(\alpha^2A_N+\tau_N^2\|g\|_2^2\right)\right)\prod_{j=1}^{m_N}M_{X_j}(x_j+iy_j) \tag*{(78)} F N ( g ) = exp ( − 2 1 ( α 2 A N + τ N 2 ∥ g ∥ 2 2 ) ) j = 1 ∏ m N M X j ( x j + i y j ) (78) By linearizing the quadratic term in R N ( α , β , v ) R_N(\alpha,\beta,v) R N ( α , β , v ) with the identity e − ∥ v ∥ 2 2 / 2 = E g [ e i ⟨ v , g ⟩ ] e^{-\|v\|_2^2/2}=\mathbb{E}_g[e^{i\langle v,g\rangle}] e − ∥ v ∥ 2 2 /2 = E g [ e i ⟨ v , g ⟩ ] , we have
log R N ( α , β , v ) = log E g [ e i 2 γ ⟨ v , g ⟩ ∏ j = 1 m N M X j ( x j + i 2 γ y j ) ] \log R_N(\alpha,\beta,v)=\log\mathbb{E}_g\left[e^{i\sqrt{2\gamma}\langle v,g\rangle}\prod_{j=1}^{m_N}M_{X_j}(x_j+i\sqrt{2\gamma}y_j)\right] log R N ( α , β , v ) = log E g [ e i 2 γ ⟨ v , g ⟩ j = 1 ∏ m N M X j ( x j + i 2 γ y j ) ]
= α 2 A N 2 − d N 2 log ( 1 + 2 γ τ N 2 ) + log E g [ e i 2 γ ⟨ v , g ⟩ F N ( ξ N g ) ] , (79) = \frac{\alpha^{2}A_N}{2} - \frac{d_N}{2}\log(1+2\gamma\tau_N^{2})+\log\mathbb{E}_g\left[e^{i\sqrt{2\gamma}\langle v,g\rangle}F_N(\xi_N g)\right], \tag*{(79)} = 2 α 2 A N − 2 d N log ( 1 + 2 γ τ N 2 ) + log E g [ e i 2 γ ⟨ v , g ⟩ F N ( ξ N g ) ] , (79)
where (79) holds by the identities (75) .
First, we claim that there exists q > 1 q>1 q > 1 and C > 0 C>0 C > 0 such that
E [ ∣ F N ( ξ N g ) ∣ q ] ≤ e C Δ N (80) \mathbb{E}\left[\left|F_N(\xi_N g)\right|^q\right]\le e^{C\Delta_N} \tag*{(80)} E [ ∣ F N ( ξ N g ) ∣ q ] ≤ e C Δ N (80)
We see from the inequality (72) induced by strict subgaussianity that
log E g [ ∣ F N ( ξ N g ) ∣ q ] ≤ − q 2 ( α 2 A N + τ N 2 ∥ ξ N g ∥ 2 2 ) + E g [ exp ( q ∑ j = 1 m N x j 2 − ( ρ N y j ) 2 2 + c 11 x j 4 + h ( ξ N y j ) ) ] = c 11 q ∑ j = 1 m N x j 4 + log E g [ exp ( q ∑ j = 1 m N h ( ξ N y j ) ) ] , (81) \begin{aligned}
\log\mathbb{E}_g\left[\left|F_N(\xi_N g)\right|^q\right]
\le-\frac{q}{2}\left(\alpha^2 A_N+\tau_N^2\|\xi_N g\|_2^2\right)+\mathbb{E}_g\left[\exp\left(q\sum_{j=1}^{m_N}\frac{x_j^2-(\rho_N y_j)^2}{2}+c_{11}x_j^4+h(\xi_N y_j)\right)\right] \\
&= c_{11}q\sum_{j=1}^{m_N}x_j^4+\log\mathbb{E}_g\left[\exp\left(q\sum_{j=1}^{m_N}h(\xi_N y_j)\right)\right], \tag*{(81)}
\end{aligned} log E g [ ∣ F N ( ξ N g ) ∣ q ] ≤ − 2 q ( α 2 A N + τ N 2 ∥ ξ N g ∥ 2 2 ) + E g [ exp ( q j = 1 ∑ m N 2 x j 2 − ( ρ N y j ) 2 + c 11 x j 4 + h ( ξ N y j ) ) ] = c 11 q j = 1 ∑ m N x j 4 + log E g [ exp ( q j = 1 ∑ m N h ( ξ N y j ) ) ] , (81)
where (81) holds by the identities (75) . Next, we choose q > 1 q>1 q > 1 small enough so that
q ( γ c 12 1 + 2 γ c 12 ) < 1 2 . (82) q\left(\frac{\gamma c_{12}}{1+2\gamma c_{12}}\right)<\frac{1}{2}. \tag*{(82)} q ( 1 + 2 γ c 12 γ c 12 ) < 2 1 . (82)
For the last term in (81) , we shall apply the Gaussian Brascamp–Lieb inequality (A.1) with
m = m N , d = d N , u j = b j ∥ b j ∥ 2 , λ j = ∥ b j ∥ 2 2 τ N 2 , f j ( x ) = exp ( q h ( ξ N ∥ b j ∥ 2 x ) λ j ) , m=m_N,\qquad d=d_N,\qquad u_j=\frac{b_j}{\|b_j\|_2},\qquad\lambda_j=\frac{\|b_j\|_2^2}{\tau_N^2},\qquad f_j(x)=\exp\left(\frac{q h(\xi_N\|b_j\|_2x)}{\lambda_j}\right), m = m N , d = d N , u j = ∥ b j ∥ 2 b j , λ j = τ N 2 ∥ b j ∥ 2 2 , f j ( x ) = exp ( λ j q h ( ξ N ∥ b j ∥ 2 x ) ) ,
where we may assume without lose of generality that b j ≠ 0 b_j\ne0 b j = 0 . We see then
log E g [ exp ( ∑ j = 1 m N h ( ξ N y j ) ) ] = log E Z [ ∏ j = 1 m N f j ( ⟨ u j , g ⟩ ) λ j ] ≤ ∑ j = 1 m N λ j log E Z [ f j ( Z ) ] . (83) \log\mathbb{E}_g\left[\exp\left(\sum_{j=1}^{m_N}h(\xi_Ny_j)\right)\right]
=\log\mathbb{E}_Z\left[\prod_{j=1}^{m_N}f_j(\langle u_j,g\rangle)^{\lambda_j}\right]
\le\sum_{j=1}^{m_N}\lambda_j\log\mathbb{E}_Z[f_j(Z)]. \tag*{(83)} log E g [ exp ( j = 1 ∑ m N h ( ξ N y j ) ) ] = log E Z [ j = 1 ∏ m N f j (⟨ u j , g ⟩ ) λ j ] ≤ j = 1 ∑ m N λ j log E Z [ f j ( Z )] . (83)
Note that by the elementary inequalities log ( 1 + x ) ≤ x \log(1+x)\le x log ( 1 + x ) ≤ x , e x − 1 ≤ x e x e^x-1\le xe^x e x − 1 ≤ x e x , and the definition of the function h ( y ) = min { y 2 / 2 , c 11 y 4 } h(y)=\min\{y^2/2,c_{11}y^4\} h ( y ) = min { y 2 /2 , c 11 y 4 } , we see for our choice of q > 1 q>1 q > 1 in (82) ,
λ j log E Z [ f j ( Z ) ] ≤ λ j ( E Z [ f j ( Z ) ] − 1 ) ≤ E Z [ q h ( ξ N ∥ b j ∥ 2 Z ) exp ( q h ( ξ N ∥ b j ∥ 2 Z ) λ j ) ] ≤ E Z [ c 11 q ( ξ N ∥ b j ∥ 2 Z ) 4 exp ( q ξ N 2 ∥ b j ∥ 2 2 Z 2 2 λ j ) ] = c 11 q ξ N 4 E Z [ Z 4 exp ( q ( γ τ N 2 1 + 2 γ τ N 2 ) Z 2 ) ] ∥ b j ∥ 2 4 ≤ c 11 q ξ N 4 E Z [ Z 4 exp ( q ( γ c 12 1 + 2 γ c 12 ) Z 2 ) ] ∥ b j ∥ 2 4 . (84) \begin{aligned}
\lambda_j\log\mathbb{E}_Z[f_j(Z)]
\le\lambda_j\left(\mathbb{E}_Z[f_j(Z)]-1\right)
\le\mathbb{E}_Z\left[qh(\xi_N\|b_j\|_2Z)\exp\left(\frac{qh(\xi_N\|b_j\|_2Z)}{\lambda_j}\right)\right] \\
&\le\mathbb{E}_Z\left[c_{11}q(\xi_N\|b_j\|_2Z)^4\exp\left(\frac{q\xi_N^2\|b_j\|_2^2Z^2}{2\lambda_j}\right)\right] \\
&=c_{11}q\xi_N^4\mathbb{E}_Z\left[Z^4\exp\left(q\left(\frac{\gamma\tau_N^2}{1+2\gamma\tau_N^2}\right)Z^2\right)\right]\|b_j\|_2^4 \\
&\le c_{11}q\xi_N^4\mathbb{E}_Z\left[Z^4\exp\left(q\left(\frac{\gamma c_{12}}{1+2\gamma c_{12}}\right)Z^2\right)\right]\|b_j\|_2^4. \tag*{(84)}
\end{aligned} λ j log E Z [ f j ( Z )] ≤ λ j ( E Z [ f j ( Z )] − 1 ) ≤ E Z [ q h ( ξ N ∥ b j ∥ 2 Z ) exp ( λ j q h ( ξ N ∥ b j ∥ 2 Z ) ) ] ≤ E Z [ c 11 q ( ξ N ∥ b j ∥ 2 Z ) 4 exp ( 2 λ j q ξ N 2 ∥ b j ∥ 2 2 Z 2 ) ] = c 11 q ξ N 4 E Z [ Z 4 exp ( q ( 1 + 2 γ τ N 2 γ τ N 2 ) Z 2 ) ] ∥ b j ∥ 2 4 ≤ c 11 q ξ N 4 E Z [ Z 4 exp ( q ( 1 + 2 γ c 12 γ c 12 ) Z 2 ) ] ∥ b j ∥ 2 4 . (84)
The claim (80) follows directly by combining (81) , (83) , and (84) .
To show the upper bound, we see that (76) follows from combining (79) , the claim (80) with q = 1 q=1 q = 1 and
∣ E g [ e i 2 γ ⟨ v , g ⟩ F N ( ξ N g ) ] ∣ ≤ E g [ ∣ F N ( ξ N g ) ∣ ] . \left|\mathbb{E}_g\left[e^{i\sqrt{2\gamma}\langle v,g\rangle}F_N(\xi_Ng)\right]\right|
\le\mathbb{E}_g\left[\left|F_N(\xi_Ng)\right|\right]. E g [ e i 2 γ ⟨ v , g ⟩ F N ( ξ N g ) ] ≤ E g [ ∣ F N ( ξ N g ) ∣ ] .
For the second item, let κ j = ( log M X j ) ( 4 ) ( 0 ) \kappa_j = (\log M_{X_j})^{(4)}(0) κ j = ( log M X j ) ( 4 ) ( 0 ) be the fourth cumulant of X j X_j X j (which, say, are uniformly bounded by κ \kappa κ ). By (SSG), there exists δ , C > 0 \delta, C > 0 δ , C > 0 such that for all ∣ z ∣ < δ |z| < \delta ∣ z ∣ < δ
log M X j ( z ) = z 2 2 + κ j 24 z 4 + Q j ( z ) and sup N ∈ N sup 1 ≤ j ≤ m N ∣ Q j ( z ) ∣ ≤ C ∣ z ∣ 5 . \log M_{X_j}(z) = \frac{z^2}{2} + \frac{\kappa_j}{24}z^4 + Q_j(z) \quad\text{and} \quad\sup_{N \in\mathbb{N}}\sup_{1 \leq j \leq m_N}|Q_j(z)| \leq C|z|^5. log M X j ( z ) = 2 z 2 + 24 κ j z 4 + Q j ( z ) and N ∈ N sup 1 ≤ j ≤ m N sup ∣ Q j ( z ) ∣ ≤ C ∣ z ∣ 5 .
Define
D N ( g ) = 1 24 ∑ j = 1 m N κ j ( x j + i ξ N y j ) 4 and E N = { max 1 ≤ j ≤ m N ∣ x j + i ξ N y j ∣ < δ } . D_N(g) = \frac{1}{24}\sum_{j=1}^{m_N}\kappa_j(x_j+i\xi_Ny_j)^4 \quad\text{and} \quad\mathcal{E}_N = \left\{\max_{1 \leq j \leq m_N}|x_j+i\xi_Ny_j| < \delta\right\}. D N ( g ) = 24 1 j = 1 ∑ m N κ j ( x j + i ξ N y j ) 4 and E N = { 1 ≤ j ≤ m N max ∣ x j + i ξ N y j ∣ < δ } .
We claim that on the event E N \mathcal{E}_N E N ,
F N ( ξ N g ) → exp ( E g [ D N ( g ) ] ) in L q . (85) \mathcal{F}_N(\xi_Ng) \to\exp\left(\mathbb{E}_g[D_N(g)]\right) \quad\text{in } L^q. \tag*{(85)} F N ( ξ N g ) → exp ( E g [ D N ( g )] ) in L q . (85)
Note that on E N \mathcal{E}_N E N , one has from the definition (78) , the identities (75) , that
F N ( ξ N g ) = exp [ D N ( g ) + O ( ∑ j = 1 m N ∣ x j + i ξ N y j ∣ 5 ) ] . (86) \mathcal{F}_N(\xi_Ng) = \exp\left[D_N(g) + O\left(\sum_{j=1}^{m_N}|x_j+i\xi_Ny_j|^5\right)\right]. \tag*{(86)} F N ( ξ N g ) = exp [ D N ( g ) + O ( j = 1 ∑ m N ∣ x j + i ξ N y j ∣ 5 ) ] . (86)
By Gaussian moment bounds, there exists c 14 = c 14 ( α , γ , c 12 ) > 0 c_{14}=c_{14}(\alpha,\gamma,c_{12})>0 c 14 = c 14 ( α , γ , c 12 ) > 0 such that for k = 4 , 5 , 6 k=4,5,6 k = 4 , 5 , 6 ,
E g [ ∑ j = 1 m N ∣ x j + i ξ N y j ∣ k ] ≤ 2 k ∑ j = 1 m N ( ∣ α ∣ k ∣ a j ∣ k + ξ N k E g [ ∣ ⟨ b j , g ⟩ ∣ k ] ) ≤ c 14 ρ N k − 4 Δ N . (87) \mathbb{E}_g\left[\sum_{j=1}^{m_N}|x_j+i\xi_Ny_j|^k\right] \leq2^k\sum_{j=1}^{m_N}\left(|\alpha|^k|a_j|^k+\xi_N^k\mathbb{E}_g[|\langle b_j,g\rangle|^k]\right) \leq c_{14}\rho_N^{k-4}\Delta_N. \tag*{(87)} E g [ j = 1 ∑ m N ∣ x j + i ξ N y j ∣ k ] ≤ 2 k j = 1 ∑ m N ( ∣ α ∣ k ∣ a j ∣ k + ξ N k E g [ ∣ ⟨ b j , g ⟩ ∣ k ] ) ≤ c 14 ρ N k − 4 Δ N . (87)
In particular, P g ( E N ) → 1 \mathbb{P}_g(\mathcal{E}_N)\to1 P g ( E N ) → 1 by Markov’s inequality and the remainder term in (86) satisfies ∑ j = 1 m N ∣ x j + i ξ N y j ∣ 5 → 0 \sum_{j=1}^{m_N}|x_j+i\xi_Ny_j|^5\to0 ∑ j = 1 m N ∣ x j + i ξ N y j ∣ 5 → 0 in probability. Moreover, by Gaussian Poincaré inequality (see [10 Theorem 3.20] ), applied to the real and imaginary parts,
E g [ ∣ D N ( g ) − E g [ D N ( g ) ] ∣ 2 ] ≤ ξ N 2 E g [ ∥ ∇ D N ( g ) ∥ 2 2 ] = ξ N 2 E g [ ∥ 1 6 ∑ j = 1 m N κ j ( x j + i ξ N y j ) 3 ξ N b j ∥ 2 2 ] ≤ ξ N 4 κ 2 τ N 2 6 E g [ ∑ j = 1 m N ∣ x j + i ξ N y j ∣ 6 ] ≤ ξ N 4 κ 2 τ N 2 6 ⋅ c 14 ρ N 2 Δ N = o N ( 1 ) , (88) \begin{aligned}
\mathbb{E}_g\left[|D_N(g)-\mathbb{E}_g[D_N(g)]|^2\right] \leq\xi_N^2\mathbb{E}_g\left[\|\nabla D_N(g)\|_2^2\right] \\
&= \xi_N^2\mathbb{E}_g\left[\left\|\frac{1}{6}\sum_{j=1}^{m_N}\kappa_j(x_j+i\xi_Ny_j)^3\xi_Nb_j\right\|_2^2\right] \\
&\leq\frac{\xi_N^4\kappa^2\tau_N^2}{6}\mathbb{E}_g\left[\sum_{j=1}^{m_N}|x_j+i\xi_Ny_j|^6\right] \\
&\leq\frac{\xi_N^4\kappa^2\tau_N^2}{6}\cdot c_{14}\rho_N^2\Delta_N=o_N(1), \tag*{(88)}
\end{aligned} E g [ ∣ D N ( g ) − E g [ D N ( g )] ∣ 2 ] ≤ ξ N 2 E g [ ∥∇ D N ( g ) ∥ 2 2 ] = ξ N 2 E g 6 1 j = 1 ∑ m N κ j ( x j + i ξ N y j ) 3 ξ N b j 2 2 ≤ 6 ξ N 4 κ 2 τ N 2 E g [ j = 1 ∑ m N ∣ x j + i ξ N y j ∣ 6 ] ≤ 6 ξ N 4 κ 2 τ N 2 ⋅ c 14 ρ N 2 Δ N = o N ( 1 ) , (88)
where the last inequality holds by (87) with k = 6 k=6 k = 6 . Combining (86) and (88) , we see that F N ( ξ N g ) → exp ( E g [ D N ( g ) ] ) \mathcal{F}_N(\xi_Ng)\to\exp(\mathbb{E}_g[D_N(g)]) F N ( ξ N g ) → exp ( E g [ D N ( g )]) in probability. Since Δ N = O N ( 1 ) \Delta_N=O_N(1) Δ N = O N ( 1 ) , (80) further implies that the sequence F N ( ξ N g ) \mathcal{F}_N(\xi_Ng) F N ( ξ N g ) is L q L^q L q -bounded, thus concludes (85) . Moreover, the L q L^q L q -boundedness of F N ( ξ N g ) \mathcal{F}_N(\xi_Ng) F N ( ξ N g ) and boundedness of D N ( g ) D_N(g) D N ( g ) further implies
E g [ F N ( ξ N g ) ] = exp ( E g [ D N ( g ) ] ) ( 1 + o N ( 1 ) ) . \mathbb{E}_g[\mathcal{F}_N(\xi_Ng)] = \exp(\mathbb{E}_g[D_N(g)])(1+o_N(1)). E g [ F N ( ξ N g )] = exp ( E g [ D N ( g )]) ( 1 + o N ( 1 )) .
Plugging this in (79) and setting v = 0 v=0 v = 0 will then give us the desired asymptote (77) .
Upper Bound
Before applying Proposition 6.3 to establish the upper bound in (71) , we need to introduce some notation. First, we set
a I ( σ ) = N N − 1 σ I N ( p − 1 ) / 2 ∈ R and b I ( σ ) = B ( σ ) T ∇ σ I N ( p − 1 ) / 2 ∈ R N − 1 . a_I(\sigma)=\sqrt{\frac{N}{N-1}}\frac{\sigma_I}{N^{(p-1)/2}}\in\mathbb{R}\quad\text{and}\quad b_I(\sigma)=\frac{B(\sigma)^{\mathsf{T}}\nabla\sigma_I}{N^{(p-1)/2}}\in\mathbb{R}^{N-1}. a I ( σ ) = N − 1 N N ( p − 1 ) /2 σ I ∈ R and b I ( σ ) = N ( p − 1 ) /2 B ( σ ) T ∇ σ I ∈ R N − 1 .
For a configuration σ ∈ N S N − 1 \sigma\in\sqrt{N}S^{N-1} σ ∈ N S N − 1 , we define the set of delocalized and localized coordinate of σ \sigma σ by
L ( σ ) = { i ∈ [ N ] ∣ ∣ σ i ∣ ≥ log N } ⊆ [ N ] and D ( σ ) = [ N ] ∖ L ( σ ) , L(\sigma)=\{i\in[N]\mid|\sigma_i|\ge\log N\}\subseteq[N]\quad\text{and}\quad D(\sigma)=[N]\setminus L(\sigma), L ( σ ) = { i ∈ [ N ] ∣ ∣ σ i ∣ ≥ log N } ⊆ [ N ] and D ( σ ) = [ N ] ∖ L ( σ ) ,
where ∣ L ( σ ) ∣ ≤ r N : = ⌊ N / ( log N ) 2 ⌋ = o N ( N ) |L(\sigma)|\le r_N:=\lfloor N/(\log N)^2\rfloor=o_N(N) ∣ L ( σ ) ∣ ≤ r N := ⌊ N / ( log N ) 2 ⌋ = o N ( N ) . Additionally, consider the subspace
E D ( σ ) = { v ∈ R N : ⟨ v , σ ⟩ = 0 and v i = 0 for all i ∈ L ( σ ) } ⊂ { σ } ⊥ E_D(\sigma)=\{v\in\mathbb{R}^N:\langle v,\sigma\rangle=0\text{ and }v_i=0\text{ for all }i\in L(\sigma)\}\subset\{\sigma\}^{\perp} E D ( σ ) = { v ∈ R N : ⟨ v , σ ⟩ = 0 and v i = 0 for all i ∈ L ( σ )} ⊂ { σ } ⊥
of dimension N − ∣ L ( σ ) ∣ − 1 N-|L(\sigma)|-1 N − ∣ L ( σ ) ∣ − 1 . Let B D ( σ ) B_D(\sigma) B D ( σ ) be a N × ( N − ∣ L ( σ ) ∣ − 1 ) N\times(N-|L(\sigma)|-1) N × ( N − ∣ L ( σ ) ∣ − 1 ) semi-orthogonal matrix consisting of an orthonormal basis of E D ( σ ) E_D(\sigma) E D ( σ ) . Then,
∥ B ( σ ) T v ∥ 2 ≥ ∥ B D ( σ ) T v ∥ 2 , ∀ v ∈ R N (89) \|B(\sigma)^{\mathsf{T}}v\|_2\ge\|B_D(\sigma)^{\mathsf{T}}v\|_2,\quad\forall v\in\mathbb{R}^N \tag*{(89)} ∥ B ( σ ) T v ∥ 2 ≥ ∥ B D ( σ ) T v ∥ 2 , ∀ v ∈ R N (89)
Remark 6.4. The matrix B D ( σ ) B_D(\sigma) B D ( σ ) has two useful properties that will be essential in our proofs later. First, for any v ∈ R N v\in\mathbb{R}^N v ∈ R N vanishing on D ( σ ) D(\sigma) D ( σ ) , we have B D ( σ ) T v = 0 B_D(\sigma)^{\mathsf{T}}v=0 B D ( σ ) T v = 0 . Second, if v ∈ R N v\in\mathbb{R}^N v ∈ R N is supported on D ( σ ) D(\sigma) D ( σ ) with v i = σ i v_i=\sigma_i v i = σ i for i ∈ D ( σ ) i\in D(\sigma) i ∈ D ( σ ) , then B D ( σ ) T v = 0 B_D(\sigma)^{\mathsf{T}}v=0 B D ( σ ) T v = 0 . The former holds since any element in E D ( σ ) E_D(\sigma) E D ( σ ) is supported on D ( σ ) D(\sigma) D ( σ ) and this readily implies that v ∈ E D ( σ ) ⊥ v\in E_D(\sigma)^\perp v ∈ E D ( σ ) ⊥ so that B D ( σ ) T v = 0 B_D(\sigma)^{\mathsf{T}}v=0 B D ( σ ) T v = 0 . The latter holds true due to B D ( σ ) T σ = 0 B_D(\sigma)^{\mathsf{T}}\sigma=0 B D ( σ ) T σ = 0 .
Set [ N ] h i p [N]^p_{\mathrm{hi}} [ N ] hi p to be the collection of tensor index I I I that has at most 1 entries in D ( σ ) D(\sigma) D ( σ ) and [ N ] l o p = [ N ] p ∖ [ N ] h i p [N]^p_{\mathrm{lo}}=[N]^p\setminus[N]^p_{\mathrm{hi}} [ N ] lo p = [ N ] p ∖ [ N ] hi p . We split the Hamiltonian H N J ( σ ) = H N h i ( σ ) + H N l o ( σ ) H_N^J(\sigma)=H_N^{\mathrm{hi}}(\sigma)+H_N^{\mathrm{lo}}(\sigma) H N J ( σ ) = H N hi ( σ ) + H N lo ( σ ) into high- and low-influence parts, where each part only contains tensor indices that are in the corresponding subset. Set
c I ( σ ) = B D ( σ ) T ∇ σ I N ( p − 1 ) / 2 ∈ R N − ∣ L ( σ ) ∣ − 1 and η = η ( σ ) = 1 N ∑ i ∈ L ( σ ) σ i 2 ∈ [ 0 , 1 ] , c_I(\sigma)=\frac{B_D(\sigma)^{\mathsf{T}}\nabla\sigma_I}{N^{(p-1)/2}}\in\mathbb{R}^{N-|L(\sigma)|-1}\quad\text{and}\quad\eta=\eta(\sigma)=\frac{1}{N}\sum_{i\in L(\sigma)}\sigma_i^2\in[0,1], c I ( σ ) = N ( p − 1 ) /2 B D ( σ ) T ∇ σ I ∈ R N − ∣ L ( σ ) ∣ − 1 and η = η ( σ ) = N 1 i ∈ L ( σ ) ∑ σ i 2 ∈ [ 0 , 1 ] ,
Lemma 6.5. For all σ ∈ N S N − 1 \sigma\in\sqrt{N}S^{N-1} σ ∈ N S N − 1 , the following identities hold:
∑ I ∈ [ N ] p a I ( σ ) 2 = N 2 N − 1 , ∑ I ∈ [ N ] p a I ( σ ) b I ( σ ) = 0 , and ∑ I ∈ [ N ] p b I ( σ ) b I ( σ ) T = p I N − 1 , (90) \sum_{I\in[N]^p}a_I(\sigma)^2=\frac{N^2}{N-1},\quad\sum_{I\in[N]^p}a_I(\sigma)b_I(\sigma)=0,\quad\text{and}\quad\sum_{I\in[N]^p}b_I(\sigma)b_I(\sigma)^{\mathsf{T}}=pI_{N-1}, \tag*{(90)} I ∈ [ N ] p ∑ a I ( σ ) 2 = N − 1 N 2 , I ∈ [ N ] p ∑ a I ( σ ) b I ( σ ) = 0 , and I ∈ [ N ] p ∑ b I ( σ ) b I ( σ ) T = p I N − 1 , (90)
and also
∑ I ∈ [ N ] l o p a I ( σ ) 2 = N 2 s ( η ) N − 1 , ∑ I ∈ [ N ] l o p a I ( σ ) c I ( σ ) = 0 , ∑ I ∈ [ N ] l o p c I ( σ ) c I ( σ ) T = p ( 1 − η p − 1 ) I N − ∣ L ( σ ) ∣ − 1 , (91) \sum_{I\in[N]^p_{\mathrm{lo}}}a_I(\sigma)^2=\frac{N^2s(\eta)}{N-1},\quad\sum_{I\in[N]^p_{\mathrm{lo}}}a_I(\sigma)c_I(\sigma)=0,\quad\sum_{I\in[N]^p_{\mathrm{lo}}}c_I(\sigma)c_I(\sigma)^{\mathsf{T}}=p(1-\eta^{p-1})I_{N-|L(\sigma)|-1}, \tag*{(91)} I ∈ [ N ] lo p ∑ a I ( σ ) 2 = N − 1 N 2 s ( η ) , I ∈ [ N ] lo p ∑ a I ( σ ) c I ( σ ) = 0 , I ∈ [ N ] lo p ∑ c I ( σ ) c I ( σ ) T = p ( 1 − η p − 1 ) I N − ∣ L ( σ ) ∣ − 1 , (91)
where s ( η ) = 1 − η p − p η p − 1 ( 1 − η ) s(\eta)=1-\eta^p-p\eta^{p-1}(1-\eta) s ( η ) = 1 − η p − p η p − 1 ( 1 − η ) .
Proof. Both (90) and (91) can be proved by the same computation as in Proposition 3.1 . We only provide the details for (91) . Fix σ ∈ N S N − 1 \sigma\in\sqrt{N}S^{N-1} σ ∈ N S N − 1 . Set, for any x , y ∈ R N x,y\in\mathbb{R}^N x , y ∈ R N ,
C ( x , y ) = E [ H N l o ( x ) H N l o ( y ) ] = ∑ I ∈ [ N ] l o p x I y I N p − 1 = N ( R ( x , y ) p − R L ( x , y ) p − p R L ( x , y ) p − 1 R D ( x , y ) ) , \begin{aligned}
C(x,y)=\mathbb{E}\left[H_N^{\mathrm{lo}}(x)H_N^{\mathrm{lo}}(y)\right]=\sum_{I\in[N]^p_{\mathrm{lo}}}\frac{x_Iy_I}{N^{p-1}} \\
&= N\left(R(x,y)^p-R_L(x,y)^p-pR_L(x,y)^{p-1}R_D(x,y)\right),
\end{aligned} C ( x , y ) = E [ H N lo ( x ) H N lo ( y ) ] = I ∈ [ N ] lo p ∑ N p − 1 x I y I = N ( R ( x , y ) p − R L ( x , y ) p − p R L ( x , y ) p − 1 R D ( x , y ) ) ,
where
R ( x , y ) : = 1 N ∑ i = 1 N x i y i , R L ( x , y ) : = 1 N ∑ i ∈ L ( σ ) x i y i , and R D ( x , y ) : = R ( x , y ) − R L ( x , y ) . R(x,y):=\frac{1}{N}\sum_{i=1}^{N}x_i y_i,\quad R_L(x,y):=\frac{1}{N}\sum_{i\in L(\sigma)}x_i y_i,\quad\text{and}\quad R_D(x,y):=R(x,y)-R_L(x,y). R ( x , y ) := N 1 i = 1 ∑ N x i y i , R L ( x , y ) := N 1 i ∈ L ( σ ) ∑ x i y i , and R D ( x , y ) := R ( x , y ) − R L ( x , y ) .
By definition, (91) is obtained by
∑ I ∈ [ N ] 0 p a I ( σ ) 2 = N N − 1 C ( σ , σ ) = N 2 N − 1 ( 1 − η p − p η p − 1 ( 1 − η ) ) . \sum_{I\in[N]^p_0}a_I(\sigma)^2=\frac{N}{N-1}C(\sigma,\sigma)=\frac{N^2}{N-1}\left(1-\eta^p-p\eta^{p-1}(1-\eta)\right). I ∈ [ N ] 0 p ∑ a I ( σ ) 2 = N − 1 N C ( σ , σ ) = N − 1 N 2 ( 1 − η p − p η p − 1 ( 1 − η ) ) .
Next write
∑ I ∈ [ N ] 0 p a I ( σ ) c I ( σ ) = N N − 1 B D ( σ ) T ∇ y C ( σ , σ ) . \sum_{I\in[N]^p_0}a_I(\sigma)c_I(\sigma)=\sqrt{\frac{N}{N-1}}B_D(\sigma)^{\mathsf{T}}\nabla_y C(\sigma,\sigma). I ∈ [ N ] 0 p ∑ a I ( σ ) c I ( σ ) = N − 1 N B D ( σ ) T ∇ y C ( σ , σ ) .
Let v , v ′ ∈ R N v,v'\in\mathbb{R}^N v , v ′ ∈ R N be supported on D ( σ ) D(\sigma) D ( σ ) and L ( σ ) L(\sigma) L ( σ ) respectively with v i = σ i v_i=\sigma_i v i = σ i on D ( σ ) D(\sigma) D ( σ ) and v i ′ = σ i v'_i=\sigma_i v i ′ = σ i on L ( σ ) L(\sigma) L ( σ ) . A direct computation yields
∇ y C ( σ , σ ) = p ( 1 − R L ( σ , σ ) p − 1 ) v + p ( 1 − R L ( σ , σ ) p − 1 − ( p − 1 ) R L ( σ , σ ) p − 2 R D ( σ , σ ) ) v ′ . \nabla_y C(\sigma,\sigma)=p(1-R_L(\sigma,\sigma)^{p-1})v+p(1-R_L(\sigma,\sigma)^{p-1}-(p-1)R_L(\sigma,\sigma)^{p-2}R_D(\sigma,\sigma))v'. ∇ y C ( σ , σ ) = p ( 1 − R L ( σ , σ ) p − 1 ) v + p ( 1 − R L ( σ , σ ) p − 1 − ( p − 1 ) R L ( σ , σ ) p − 2 R D ( σ , σ )) v ′ .
From Remark 6.4, B D ( σ ) T v = 0 B_D(\sigma)^{\mathsf{T}}v=0 B D ( σ ) T v = 0 and B D ( σ ) T v ′ = 0 B_D(\sigma)^{\mathsf{T}}v'=0 B D ( σ ) T v ′ = 0 . These yield the second identity in (91) .
For the last identity in (91) , write
∑ I ∈ [ N ] 0 p c I ( σ ) c I ( σ ) T = B D ( σ ) T ( ∂ 2 C ( σ , σ ) ∂ x s ∂ y t ) s , t ∈ [ N ] B D ( σ ) . (92) \sum_{I\in[N]^p_0}c_I(\sigma)c_I(\sigma)^{\mathsf{T}}=B_D(\sigma)^{\mathsf{T}}\left(\frac{\partial^2C(\sigma,\sigma)}{\partial x_s\partial y_t}\right)_{s,t\in[N]}B_D(\sigma). \tag*{(92)} I ∈ [ N ] 0 p ∑ c I ( σ ) c I ( σ ) T = B D ( σ ) T ( ∂ x s ∂ y t ∂ 2 C ( σ , σ ) ) s , t ∈ [ N ] B D ( σ ) . (92)
From a direct computation, it can be seen that the D ( σ ) × L ( σ ) D(\sigma)\times L(\sigma) D ( σ ) × L ( σ ) , L ( σ ) × D ( σ ) L(\sigma)\times D(\sigma) L ( σ ) × D ( σ ) , and L ( σ ) × L ( σ ) L(\sigma)\times L(\sigma) L ( σ ) × L ( σ ) -block submatrices of ( ∂ x s ∂ y t C ( σ , σ ) ) s , t ∈ [ N ] \left(\partial_{x_s}\partial_{y_t}C(\sigma,\sigma)\right)_{s,t\in[N]} ( ∂ x s ∂ y t C ( σ , σ ) ) s , t ∈ [ N ] are of the form b D , L σ D σ L T b_{D,L}\sigma_D\sigma_L^{\mathsf{T}} b D , L σ D σ L T , b L , D σ L σ D T b_{L,D}\sigma_L\sigma_D^{\mathsf{T}} b L , D σ L σ D T , and d L , L I L + b L , L σ L σ L T d_{L,L}I_L+b_{L,L}\sigma_L\sigma_L^{\mathsf{T}} d L , L I L + b L , L σ L σ L T , where b D , L b_{D,L} b D , L , b L , D b_{L,D} b L , D , b L , L b_{L,L} b L , L , and d L , L d_{L,L} d L , L are scalars depending on σ \sigma σ and p p p and σ D \sigma_D σ D and σ L \sigma_L σ L are the restrictions of σ \sigma σ to D ( σ ) D(\sigma) D ( σ ) and L ( σ ) L(\sigma) L ( σ ) respectively. As a consequence of Remark 6.4, only the D ( σ ) × D ( σ ) D(\sigma)\times D(\sigma) D ( σ ) × D ( σ ) -block submatrix of ( ∂ x s ∂ y t C ( σ , σ ) ) s , t ∈ [ N ] \left(\partial_{x_s}\partial_{y_t}C(\sigma,\sigma)\right)_{s,t\in[N]} ( ∂ x s ∂ y t C ( σ , σ ) ) s , t ∈ [ N ] can contribute to the right-hand side of (92) . Since
( ∂ 2 C ( σ , σ ) ∂ x s ∂ y t ) s , t ∈ D ( σ ) = p ( 1 − η p − 1 ) I D ( σ ) + p ( p − 1 ) N σ D σ D T , \left(\frac{\partial^2C(\sigma,\sigma)}{\partial x_s\partial y_t}\right)_{s,t\in D(\sigma)}=p(1-\eta^{p-1})I_{D(\sigma)}+\frac{p(p-1)}{N}\sigma_D\sigma_D^{\mathsf{T}}, ( ∂ x s ∂ y t ∂ 2 C ( σ , σ ) ) s , t ∈ D ( σ ) = p ( 1 − η p − 1 ) I D ( σ ) + N p ( p − 1 ) σ D σ D T ,
by using the second vanishing property in Remark 6.4, the proof of the third identity in (91) follows.
Proposition 6.6. If { J I } I ∈ [ N ] p , N ∈ N \{J_I\}_{I\in[N]^p,N\in\mathbb{N}} { J I } I ∈ [ N ] p , N ∈ N satisfies (SSG), then for all β < 1 / 2 p \beta<1/2p β < 1/2 p ,
lim sup N → ∞ Λ N ( α , β ) ≤ α 2 2 − 1 2 log ( 1 − 2 β p ) . (93) \limsup_{N\to\infty}\Lambda_N(\alpha,\beta)\leq\frac{\alpha^2}{2}-\frac{1}{2}\log(1-2\beta p). \tag*{(93)} N → ∞ lim sup Λ N ( α , β ) ≤ 2 α 2 − 2 1 log ( 1 − 2 β p ) . (93)
Proof. For 0 ≤ β < 1 / 2 p 0\leq\beta<1/2p 0 ≤ β < 1/2 p , we linearize the quadratic term in the joint moment generating function by introducing g ∼ Normal ( 0 , I N − 1 ) g\sim\operatorname{Normal}(0,I_{N-1}) g ∼ Normal ( 0 , I N − 1 ) and get
Λ N ( α , β ) = 1 N log E σ , J [ exp ( α H N J ( σ ) + β ∥ B ( σ ) T ∇ H N J ( σ ) ∥ 2 2 ) ] = 1 N log E σ [ ∏ I ∈ [ N ] 0 p M J I ( α a I ( σ ) + 2 β ⟨ b I ( σ ) , g ⟩ ) ] . ≤ 1 N log E σ [ exp ( 1 2 ∑ I ∈ [ N ] p ( α a I ( σ ) + 2 β ⟨ b I ( σ ) , g ⟩ ) 2 ) ] = N α 2 2 ( N − 1 ) − N − 1 2 N log ( 1 − 2 β p ) . \begin{aligned}
\Lambda_N(\alpha,\beta)=\frac{1}{N}\log\mathbb{E}_{\sigma,J}\left[\exp\left(\alpha H_N^J(\sigma)+\beta\lVert B(\sigma)^{\mathsf{T}}\nabla H_N^J(\sigma)\rVert_2^2\right)\right] \\
&=\frac{1}{N}\log\mathbb{E}_{\sigma}\left[\prod_{I\in[N]^p_0}M_{J_I}\left(\alpha a_I(\sigma)+\sqrt{2\beta}\langle b_I(\sigma),g\rangle\right)\right]. \\
&\le\frac{1}{N}\log\mathbb{E}_{\sigma}\left[\exp\left(\frac{1}{2}\sum_{I\in[N]^{p}}\left(\alpha a_I(\sigma)+\sqrt{2\beta}\langle b_I(\sigma),g\rangle\right)^2\right)\right] \\
&= \frac{N\alpha^2}{2(N-1)}-\frac{N-1}{2N}\log(1-2\beta p).
\end{aligned} Λ N ( α , β ) = N 1 log E σ , J [ exp ( α H N J ( σ ) + β ∥ B ( σ ) T ∇ H N J ( σ ) ∥ 2 2 ) ] = N 1 log E σ I ∈ [ N ] 0 p ∏ M J I ( α a I ( σ ) + 2 β ⟨ b I ( σ ) , g ⟩ ) . ≤ N 1 log E σ exp 2 1 I ∈ [ N ] p ∑ ( α a I ( σ ) + 2 β ⟨ b I ( σ ) , g ⟩ ) 2 = 2 ( N − 1 ) N α 2 − 2 N N − 1 log ( 1 − 2 β p ) .
where the inequality follows from (SSG) and the sum can be evaluated via (90) . The asymptote (93) then follows by taking N → ∞ N\to\infty N → ∞ .
For β = − γ < 0 \beta=-\gamma<0 β = − γ < 0 , we see by (89) and the independence between H N h i ( σ ) H_N^{\mathrm{hi}}(\sigma) H N hi ( σ ) and H N l o ( σ ) H_N^{\mathrm{lo}}(\sigma) H N lo ( σ ) ,
E J [ exp ( α H N J ( σ ) − γ ∥ B ( σ ) T ∇ H N J ( σ ) ∥ 2 2 ) ] ≤ E J [ exp ( α H N J ( σ ) − γ ∥ B D ( σ ) T ∇ H N J ( σ ) ∥ 2 2 ) ] ≤ E J [ exp ( α H N h i ( σ ) ) ] sup v ∈ R N − ∣ L ( σ ) ∣ − 1 E J [ exp ( α H N l o ( σ ) − γ ∥ v + B D ( σ ) T ∇ H N l o ( σ ) ∥ 2 2 ) ] . (94) \begin{aligned}
\mathbb{E}_{J}\left[\exp\left(\alpha H_N^J(\sigma)-\gamma\left\|B(\sigma)^{\mathsf{T}}\nabla H_N^J(\sigma)\right\|_2^2\right)\right]
&\le\mathbb{E}_{J}\left[\exp\left(\alpha H_N^J(\sigma)-\gamma\left\|B_D(\sigma)^{\mathsf{T}}\nabla H_N^J(\sigma)\right\|_2^2\right)\right]\\
&\le\mathbb{E}_{J}\left[\exp\left(\alpha H_N^{\mathrm{hi}}(\sigma)\right)\right]\sup_{v\in\mathbb{R}^{N-|L(\sigma)|-1}}\mathbb{E}_{J}\left[\exp\left(\alpha H_N^{\mathrm{lo}}(\sigma)-\gamma\left\|v+B_D(\sigma)^{\mathsf{T}}\nabla H_N^{\mathrm{lo}}(\sigma)\right\|_2^2\right)\right]. \tag*{(94)}
\end{aligned} E J [ exp ( α H N J ( σ ) − γ B ( σ ) T ∇ H N J ( σ ) 2 2 ) ] ≤ E J [ exp ( α H N J ( σ ) − γ B D ( σ ) T ∇ H N J ( σ ) 2 2 ) ] ≤ E J [ exp ( α H N hi ( σ ) ) ] v ∈ R N − ∣ L ( σ ) ∣ − 1 sup E J [ exp ( α H N lo ( σ ) − γ v + B D ( σ ) T ∇ H N lo ( σ ) 2 2 ) ] . (94)
For the first term in (94) , we combine (SSG) and the covariance profile (91) to yield
E J [ exp ( α H N h i ( σ ) ) ] ≤ exp ( α 2 2 ∑ I ∈ [ N ] h i p a I ( σ ) 2 ) = exp ( α 2 N 2 ( 1 − s ( η ) ) 2 ( N − 1 ) ) . (95) \mathbb{E}_{J}\left[\exp\left(\alpha H_N^{\mathrm{hi}}(\sigma)\right)\right]\le\exp\left(\frac{\alpha^2}{2}\sum_{I\in[N]^p_{\mathrm{hi}}}a_I(\sigma)^2\right)=\exp\left(\frac{\alpha^2N^2(1-s(\eta))}{2(N-1)}\right). \tag*{(95)} E J [ exp ( α H N hi ( σ ) ) ] ≤ exp 2 α 2 I ∈ [ N ] hi p ∑ a I ( σ ) 2 = exp ( 2 ( N − 1 ) α 2 N 2 ( 1 − s ( η )) ) . (95)
For the second term in (94) , we apply the upper bound in Proposition 6.3 with the collection of deterministic coefficients { a I ( σ ) } I ∈ [ N ] l o p \{a_I(\sigma)\}_{I\in[N]^p_{\mathrm{lo}}} { a I ( σ ) } I ∈ [ N ] lo p and { c I ( σ ) } I ∈ [ N ] l o p \{c_I(\sigma)\}_{I\in[N]^p_{\mathrm{lo}}} { c I ( σ ) } I ∈ [ N ] lo p . By the covariance profile (91) , we have the parameters
d N = N − ∣ L ( σ ) ∣ − 1 , A N = N 2 N − 1 s ( η ) , τ N 2 = p ( 1 − η p − 1 ) ≤ p . d_N=N-|L(\sigma)|-1,\qquad A_N=\frac{N^2}{N-1}s(\eta),\qquad\tau_N^2=p(1-\eta^{p-1})\le p. d N = N − ∣ L ( σ ) ∣ − 1 , A N = N − 1 N 2 s ( η ) , τ N 2 = p ( 1 − η p − 1 ) ≤ p .
Therefore, (94) , (95) , and (76) together implies that
E J [ exp ( α H N J ( σ ) − γ ∥ B ( σ ) T ∇ H N J ( σ ) ∥ 2 2 ) ] ≤ exp ( α 2 N 2 ( 1 − s ( η ) ) 2 ( N − 1 ) + α 2 N 2 s ( η ) 2 ( N − 1 ) − d N 2 log ( 1 + 2 γ p ( 1 − η p − 1 ) ) + c 13 Δ N ) = exp ( N 2 α 2 2 ( N − 1 ) + c 13 Δ N ) ( 1 + 2 γ p ( 1 − η p − 1 ) ) − d N / 2 . (96) \begin{aligned}
\mathbb{E}_{J}\left[\exp\left(\alpha H_N^J(\sigma)-\gamma\left\|B(\sigma)^{\mathsf{T}}\nabla H_N^J(\sigma)\right\|_2^2\right)\right]
&\le\exp\left(\frac{\alpha^2N^2(1-s(\eta))}{2(N-1)}+\frac{\alpha^2N^2s(\eta)}{2(N-1)}-\frac{d_N}{2}\log\left(1+2\gamma p(1-\eta^{p-1})\right)+c_{13}\Delta_N\right)\\
&=\exp\left(\frac{N^2\alpha^2}{2(N-1)}+c_{13}\Delta_N\right)\left(1+2\gamma p(1-\eta^{p-1})\right)^{-d_N/2}. \tag*{(96)}
\end{aligned} E J [ exp ( α H N J ( σ ) − γ B ( σ ) T ∇ H N J ( σ ) 2 2 ) ] ≤ exp ( 2 ( N − 1 ) α 2 N 2 ( 1 − s ( η )) + 2 ( N − 1 ) α 2 N 2 s ( η ) − 2 d N log ( 1 + 2 γ p ( 1 − η p − 1 ) ) + c 13 Δ N ) = exp ( 2 ( N − 1 ) N 2 α 2 + c 13 Δ N ) ( 1 + 2 γ p ( 1 − η p − 1 ) ) − d N /2 . (96)
Next we claim that Δ N = o N ( N ) \Delta_N=o_N(N) Δ N = o N ( N ) . Note that for all I ∈ [ N ] l o p I\in[N]^p_{\mathrm{lo}} I ∈ [ N ] lo p ,
∣ a I ( σ ) ∣ 2 ≤ 2 N 1 − p ∣ σ I ∣ 2 ≤ 2 N 1 − p [ N p − 2 ( log N ) 2 ] 2 = 2 N − 1 ( log N ) 4 = o N ( 1 ) |a_I(\sigma)|^2\le2N^{1-p}|\sigma_I|^2\le2N^{1-p}\left[\sqrt{N^{p-2}}(\log N)^2\right]^2=2N^{-1}(\log N)^4=o_N(1) ∣ a I ( σ ) ∣ 2 ≤ 2 N 1 − p ∣ σ I ∣ 2 ≤ 2 N 1 − p [ N p − 2 ( log N ) 2 ] 2 = 2 N − 1 ( log N ) 4 = o N ( 1 )
and
∥ c I ( σ ) ∥ 2 2 ≤ ∥ ∇ σ I ∥ 2 2 N p − 1 = 1 N p − 1 ∥ ∑ ℓ = 1 p ( ∏ k ≠ ℓ σ i k ) e i ℓ ∥ 2 2 ≤ p N p − 1 ∑ ℓ = 1 p ( ∏ k ≠ ℓ σ i k ) 2 ∥ e i ℓ ∥ 2 2 ≤ p 2 ( log N ) 2 N = o N ( 1 ) . \begin{aligned}
\|c_I(\sigma)\|_2^2&\le\frac{\|\nabla\sigma_I\|_2^2}{N^{p-1}}=\frac{1}{N^{p-1}}\left\|\sum_{\ell=1}^{p}\left(\prod_{k\ne\ell}\sigma_{i_k}\right)e_{i_\ell}\right\|_2^2\\
&\le\frac{p}{N^{p-1}}\sum_{\ell=1}^{p}\left(\prod_{k\ne\ell}\sigma_{i_k}\right)^2\|e_{i_\ell}\|_2^2\le\frac{p^2(\log N)^2}{N}=o_N(1).
\end{aligned} ∥ c I ( σ ) ∥ 2 2 ≤ N p − 1 ∥∇ σ I ∥ 2 2 = N p − 1 1 ℓ = 1 ∑ p k = ℓ ∏ σ i k e i ℓ 2 2 ≤ N p − 1 p ℓ = 1 ∑ p k = ℓ ∏ σ i k 2 ∥ e i ℓ ∥ 2 2 ≤ N p 2 ( log N ) 2 = o N ( 1 ) .
Therefore,
Δ N = ∑ I ∈ [ N ] l o p ( a I ( σ ) 4 + ∥ c I ( σ ) ∥ 2 4 ) ≤ max I ∈ [ N ] l o p ( a I ( σ ) 2 + ∥ c I ( σ ) ∥ 2 2 ) ∑ I ∈ [ N ] l o p ( a I ( σ ) 2 + ∥ c I ( σ ) ∥ 2 2 ) = o N ( 1 ) ( N 2 ( N − 1 ) − 1 s ( η ) + p ( 1 − η p − 1 ) d N ( σ ) ) = o N ( N ) , (97) \begin{aligned}
\Delta_N=\sum_{I\in[N]^p_{\mathrm{lo}}}\left(a_I(\sigma)^4+\|c_I(\sigma)\|_2^4\right) \\
&\le\max_{I\in[N]^p_{\mathrm{lo}}}\left(a_I(\sigma)^2+\lVert c_I(\sigma)\rVert_2^2\right)\sum_{I\in[N]^p_{\mathrm{lo}}}\left(a_I(\sigma)^2+\lVert c_I(\sigma)\rVert_2^2\right) \\
&= o_N(1)\left(N^2(N-1)^{-1}s(\eta)+p(1-\eta^{p-1})d_N(\sigma)\right)=o_N(N), \tag*{(97)}
\end{aligned} Δ N = I ∈ [ N ] lo p ∑ ( a I ( σ ) 4 + ∥ c I ( σ ) ∥ 2 4 ) ≤ I ∈ [ N ] lo p max ( a I ( σ ) 2 + ∥ c I ( σ ) ∥ 2 2 ) I ∈ [ N ] lo p ∑ ( a I ( σ ) 2 + ∥ c I ( σ ) ∥ 2 2 ) = o N ( 1 ) ( N 2 ( N − 1 ) − 1 s ( η ) + p ( 1 − η p − 1 ) d N ( σ ) ) = o N ( N ) , (97)
where the convergence is uniform over σ ∈ N S N − 1 \sigma\in\sqrt{N}S^{N-1} σ ∈ N S N − 1 .
Finally, we control the last term in (96) . For convenience, set S ( x ) = 1 + 2 γ p ( 1 − x p − 1 ) S(x)=1+2\gamma p(1-x^{p-1}) S ( x ) = 1 + 2 γ p ( 1 − x p − 1 ) for x ∈ [ 0 , 1 ] x\in[0,1] x ∈ [ 0 , 1 ] . Observe that for any fixed subset L ⊆ [ N ] L\subseteq[N] L ⊆ [ N ] with size ∣ L ∣ ≥ 1 |L|\ge1 ∣ L ∣ ≥ 1 , η L ( σ ) : = N − 1 ∑ i ∈ L σ i 2 \eta_L(\sigma):=N^{-1}\sum_{i\in L}\sigma_i^2 η L ( σ ) := N − 1 ∑ i ∈ L σ i 2 obeys Beta ( ∣ L ∣ / 2 , ( N − ∣ L ∣ ) / 2 ) \operatorname{Beta}(|L|/2,(N-|L|)/2) Beta ( ∣ L ∣/2 , ( N − ∣ L ∣ ) /2 ) . Hence,
E σ [ ( 1 + 2 γ p ( 1 − η ( σ ) p − 1 ) ) − d N / 2 ] = ∑ ℓ = 0 r N ∑ L ⊆ [ N ] ∣ L ∣ = ℓ E σ [ 1 { L ( σ ) = L } S ( η L ( σ ) ) − ( N − ℓ − 1 ) / 2 ] ≤ ( 1 + 2 γ p ) − ( N − 1 ) / 2 + ∑ ℓ = 1 r N ( N ℓ ) E X ∼ Beta ( ℓ / 2 , ( N − ℓ ) / 2 ) [ S ( X ) − ( N − ℓ − 1 ) / 2 ] . (98) \begin{aligned}
\mathbb{E}_{\sigma}\left[(1+2\gamma p(1-\eta(\sigma)^{p-1}))^{-d_N/2}\right]
=\sum_{\ell=0}^{r_N}\sum_{\substack{L\subseteq[N]\\|L|=\ell}}\mathbb{E}_{\sigma}\left[\mathbf{1}_{\{L(\sigma)=L\}}S(\eta_L(\sigma))^{-(N-\ell-1)/2}\right] \\
&\le(1+2\gamma p)^{-(N-1)/2}+\sum_{\ell=1}^{r_N}\binom{N}{\ell}\mathbb{E}_{X\sim\operatorname{Beta}(\ell/2,(N-\ell)/2)}\left[S(X)^{-(N-\ell-1)/2}\right]. \tag*{(98)}
\end{aligned} E σ [ ( 1 + 2 γ p ( 1 − η ( σ ) p − 1 ) ) − d N /2 ] = ℓ = 0 ∑ r N L ⊆ [ N ] ∣ L ∣ = ℓ ∑ E σ [ 1 { L ( σ ) = L } S ( η L ( σ ) ) − ( N − ℓ − 1 ) /2 ] ≤ ( 1 + 2 γ p ) − ( N − 1 ) /2 + ℓ = 1 ∑ r N ( ℓ N ) E X ∼ Beta ( ℓ /2 , ( N − ℓ ) /2 ) [ S ( X ) − ( N − ℓ − 1 ) /2 ] . (98)
Here,
E X ∼ Beta ( ℓ / 2 , ( N − ℓ ) / 2 ) [ S ( X ) − ( N − ℓ − 1 ) / 2 ] = 1 B ( ℓ / 2 , ( N − ℓ ) / 2 ) ∫ 0 1 S ( x ) − ( N − ℓ − 1 ) / 2 x ℓ / 2 − 1 ( 1 − x ) ( N − ℓ ) / 2 − 1 d x = 1 B ( ℓ / 2 , ( N − ℓ ) / 2 ) ∫ 0 1 ( 1 − x S ( x ) ) ( N − ℓ − 1 ) / 2 x ℓ / 2 − 1 ( 1 − x ) − 1 / 2 d x ≤ ( 1 + 2 γ p ) − ( N − ℓ − 1 ) / 2 B ( ℓ / 2 , 1 / 2 ) B ( ℓ / 2 , ( N − ℓ ) / 2 ) . (99) \begin{aligned}
\mathbb{E}_{X\sim\operatorname{Beta}(\ell/2,(N-\ell)/2)}\left[S(X)^{-(N-\ell-1)/2}\right]
=\frac{1}{B(\ell/2,(N-\ell)/2)}\int_0^1S(x)^{-(N-\ell-1)/2}x^{\ell/2-1}(1-x)^{(N-\ell)/2-1}\,dx \\
&=\frac{1}{B(\ell/2,(N-\ell)/2)}\int_0^1\left(\frac{1-x}{S(x)}\right)^{(N-\ell-1)/2}x^{\ell/2-1}(1-x)^{-1/2}\,dx \\
&\le(1+2\gamma p)^{-(N-\ell-1)/2}\frac{B(\ell/2,1/2)}{B(\ell/2,(N-\ell)/2)}. \tag*{(99)}
\end{aligned} E X ∼ Beta ( ℓ /2 , ( N − ℓ ) /2 ) [ S ( X ) − ( N − ℓ − 1 ) /2 ] = B ( ℓ /2 , ( N − ℓ ) /2 ) 1 ∫ 0 1 S ( x ) − ( N − ℓ − 1 ) /2 x ℓ /2 − 1 ( 1 − x ) ( N − ℓ ) /2 − 1 d x = B ( ℓ /2 , ( N − ℓ ) /2 ) 1 ∫ 0 1 ( S ( x ) 1 − x ) ( N − ℓ − 1 ) /2 x ℓ /2 − 1 ( 1 − x ) − 1/2 d x ≤ ( 1 + 2 γ p ) − ( N − ℓ − 1 ) /2 B ( ℓ /2 , ( N − ℓ ) /2 ) B ( ℓ /2 , 1/2 ) . (99)
where the inequality holds since
S ( x ) − ( 1 + 2 γ p ) ( 1 − x ) = x ( 1 + 2 γ p − 2 γ p x p − 2 ) ≥ 0. S(x)-(1+2\gamma p)(1-x)=x(1+2\gamma p-2\gamma p x^{p-2})\ge0. S ( x ) − ( 1 + 2 γ p ) ( 1 − x ) = x ( 1 + 2 γ p − 2 γ p x p − 2 ) ≥ 0.
Plugging (99) back in (98) yields
E σ [ S ( η ( σ ) ) − d N / 2 ] ≤ ( 1 + 2 γ p ) − ( N − 1 ) / 2 [ 1 + ∑ ℓ = 1 r N ( N ℓ ) ( 1 + 2 γ p ) ℓ / 2 B ( ℓ / 2 , 1 / 2 ) B ( ℓ / 2 , ( N − ℓ ) / 2 ) ] . (100) \mathbb{E}_{\sigma}\left[S(\eta(\sigma))^{-d_N/2}\right]\le(1+2\gamma p)^{-(N-1)/2}\left[1+\sum_{\ell=1}^{r_N}\binom{N}{\ell}(1+2\gamma p)^{\ell/2}\frac{B(\ell/2,1/2)}{B(\ell/2,(N-\ell)/2)}\right]. \tag*{(100)} E σ [ S ( η ( σ ) ) − d N /2 ] ≤ ( 1 + 2 γ p ) − ( N − 1 ) /2 [ 1 + ℓ = 1 ∑ r N ( ℓ N ) ( 1 + 2 γ p ) ℓ /2 B ( ℓ /2 , ( N − ℓ ) /2 ) B ( ℓ /2 , 1/2 ) ] . (100)
Now, by Stirling’s formula, uniformly for 1 ≤ ℓ ≤ r N 1\le\ell\le r_N 1 ≤ ℓ ≤ r N ,
log ( N ℓ ) = O N ( ℓ log N ) and log ( B ( ℓ / 2 , 1 / 2 ) B ( ℓ / 2 , ( N − ℓ ) / 2 ) ) = O N ( ℓ log N + log N ) . \log\binom{N}{\ell}=O_N(\ell\log N)\quad\text{and}\quad\log\left(\frac{B(\ell/2,1/2)}{B(\ell/2,(N-\ell)/2)}\right)=O_N(\ell\log N+\log N). log ( ℓ N ) = O N ( ℓ log N ) and log ( B ( ℓ /2 , ( N − ℓ ) /2 ) B ( ℓ /2 , 1/2 ) ) = O N ( ℓ log N + log N ) .
Since r N log N = O N ( N / log N ) = o N ( N ) r_N\log N=O_N(N/\log N)=o_N(N) r N log N = O N ( N / log N ) = o N ( N ) , the square bracket in (100) is e o N ( N ) e^{o_N(N)} e o N ( N ) . Combining (96) , (97) , (98) , and (100) leads to the desired upper bound. □
Lower Bound
Proposition 6.7. If p ≥ 3 p\ge3 p ≥ 3 and { J I } I ∈ [ N ] p , N ∈ N \{J_I\}_{I\in[N]^p,N\in\mathbb{N}} { J I } I ∈ [ N ] p , N ∈ N satisfies (SSG), then
lim inf N → ∞ Λ N ( α , β ) ≥ { α 2 2 − 1 2 log ( 1 − 2 β p ) , β < 1 2 p , ∞ , β ≥ 1 2 p . (101) \liminf_{N\to\infty}\Lambda_N(\alpha,\beta)\ge
\begin{cases}
\frac{\alpha^2}{2}-\frac{1}{2}\log(1-2\beta p), & \beta<\frac{1}{2p},\\
\infty, & \beta\ge\frac{1}{2p}.
\end{cases} \tag*{(101)} N → ∞ lim inf Λ N ( α , β ) ≥ { 2 α 2 − 2 1 log ( 1 − 2 β p ) , ∞ , β < 2 p 1 , β ≥ 2 p 1 . (101)
Proof. Set the remainder R I ( z ) = log M J I ( z ) − z 2 / 2 R_I(z)=\log M_{J_I}(z)-z^2/2 R I ( z ) = log M J I ( z ) − z 2 /2 . Since E [ J I ] = 0 \mathbb{E}[J_I]=0 E [ J I ] = 0 , E [ J I 2 ] = 1 \mathbb{E}[J_I^2]=1 E [ J I 2 ] = 1 , there exists δ , C > 0 \delta,C>0 δ , C > 0 such that
sup N ∈ N sup I ∈ [ N ] p ∣ R I ( z ) ∣ ≤ C ∣ z ∣ 3 for all ∣ z ∣ ≤ δ . (102) \sup_{N\in\mathbb{N}}\sup_{I\in[N]^p}|R_I(z)|\le C|z|^3 \quad\text{for all } |z|\le\delta. \tag*{(102)} N ∈ N sup I ∈ [ N ] p sup ∣ R I ( z ) ∣ ≤ C ∣ z ∣ 3 for all ∣ z ∣ ≤ δ . (102)
First, we argue for β ≥ 0 \beta\ge0 β ≥ 0 . By introducing an independent random vector g ∼ Normal ( 0 , I N − 1 ) g\sim\operatorname{Normal}(0,I_{N-1}) g ∼ Normal ( 0 , I N − 1 ) and denoting z I ( σ ) = α a I ( σ ) + 2 β ⟨ b I ( σ ) , g ⟩ ∈ R z_I(\sigma)=\alpha a_I(\sigma)+\sqrt{2\beta}\langle b_I(\sigma),g\rangle\in\mathbb{R} z I ( σ ) = α a I ( σ ) + 2 β ⟨ b I ( σ ) , g ⟩ ∈ R , we again linearize the quadratic term in the joint moment generating function:
Λ N ( α , β ) = 1 N log E σ , g [ exp ( ∑ I ∈ [ N ] p log M J I ( z I ( σ ) ) ) ] = 1 N log E σ , g [ exp ( 1 2 ∑ I ∈ [ N ] p z I ( σ ) 2 + ∑ I ∈ [ N ] p R I ( z I ( σ ) ) ) ] = N α 2 2 ( N − 1 ) + 1 N log E σ , g [ exp ( β p ∥ g ∥ 2 2 + ∑ I ∈ [ N ] p R I ( z I ( σ ) ) ) ] . (103) \begin{aligned}
\Lambda_N(\alpha,\beta)=\frac{1}{N}\log\mathbb{E}_{\sigma,g}\left[\exp\left(\sum_{I\in[N]^p}\log M_{J_I}(z_I(\sigma))\right)\right] \\
&=\frac{1}{N}\log\mathbb{E}_{\sigma,g}\left[\exp\left(\frac{1}{2}\sum_{I\in[N]^p}z_I(\sigma)^2+\sum_{I\in[N]^p}R_I(z_I(\sigma))\right)\right] \\
&=\frac{N\alpha^2}{2(N-1)}+\frac{1}{N}\log\mathbb{E}_{\sigma,g}\left[\exp\left(\beta p\lVert g\rVert_2^2+\sum_{I\in[N]^p}R_I(z_I(\sigma))\right)\right]. \tag*{(103)}
\end{aligned} Λ N ( α , β ) = N 1 log E σ , g exp I ∈ [ N ] p ∑ log M J I ( z I ( σ )) = N 1 log E σ , g exp 2 1 I ∈ [ N ] p ∑ z I ( σ ) 2 + I ∈ [ N ] p ∑ R I ( z I ( σ )) = 2 ( N − 1 ) N α 2 + N 1 log E σ , g exp β p ∥ g ∥ 2 2 + I ∈ [ N ] p ∑ R I ( z I ( σ )) . (103)
where (103) holds by the covariance profile (90) . Consider for M ≥ 1 M\ge1 M ≥ 1 the events E N 1 = { σ ∈ N S N − 1 : ∥ σ ∥ ∞ ≤ log N } \mathcal{E}_N^1=\{\sigma\in\sqrt{N}S^{N-1}:\lVert\sigma\rVert_\infty\le\log N\} E N 1 = { σ ∈ N S N − 1 : ∥ σ ∥ ∞ ≤ log N } and E N 2 ( M ) = { g ∈ R N − 1 : ∥ g ∥ ∞ ≤ M } \mathcal{E}_N^2(M)=\{g\in\mathbb{R}^{N-1}:\lVert g\rVert_\infty\le M\} E N 2 ( M ) = { g ∈ R N − 1 : ∥ g ∥ ∞ ≤ M } .
Note that P σ ( E N 1 ) → 1 \mathbb{P}_{\sigma}(\mathcal{E}_N^1)\to1 P σ ( E N 1 ) → 1 as N → ∞ N\to\infty N → ∞ . We claim that the argument of the remainder ∣ z I ( σ ) ∣ = o N ( 1 ) |z_I(\sigma)|=o_N(1) ∣ z I ( σ ) ∣ = o N ( 1 ) on the event E N 1 ∩ E N 2 ( M ) \mathcal{E}_N^1\cap\mathcal{E}_N^2(M) E N 1 ∩ E N 2 ( M ) . Indeed, on E N 1 ∩ E N 2 ( M ) \mathcal{E}_N^1\cap\mathcal{E}_N^2(M) E N 1 ∩ E N 2 ( M ) ,
∣ α a I ( σ ) ∣ = ∣ α ∣ ∣ σ I ∣ N ( p − 1 ) / 2 ≤ ∣ α ∣ ∥ σ ∥ ∞ p N ( p − 1 ) / 2 ≤ ∣ α ∣ ( log N ) p N ( p − 1 ) / 2 = o N ( 1 ) |\alpha a_I(\sigma)|=\frac{|\alpha||\sigma_I|}{N^{(p-1)/2}}\le\frac{|\alpha|\lVert\sigma\rVert_\infty^p}{N^{(p-1)/2}}\le\frac{|\alpha|(\log N)^p}{N^{(p-1)/2}}=o_N(1) ∣ α a I ( σ ) ∣ = N ( p − 1 ) /2 ∣ α ∣∣ σ I ∣ ≤ N ( p − 1 ) /2 ∣ α ∣ ∥ σ ∥ ∞ p ≤ N ( p − 1 ) /2 ∣ α ∣ ( log N ) p = o N ( 1 )
and also
∣ 2 β ⟨ b I ( σ ) , g ⟩ ∣ ≤ 2 β N ( p − 1 ) / 2 ∣ ∑ j = 1 p σ I ∖ { i j } ( B ( σ ) g ) i j ∣ ≤ 2 β p ∥ σ ∥ ∞ p − 1 ∥ B ( σ ) g ∥ ∞ N ( p − 1 ) / 2 ≤ 2 β p ( log N ) p − 1 ∥ g ∥ 2 N ( p − 1 ) / 2 = O ( ( log N ) p − 1 N ( p − 2 ) / 2 ) = o N ( 1 ) , \begin{aligned}
\left|\sqrt{2\beta}\langle b_I(\sigma),g\rangle\right|
\le\frac{\sqrt{2\beta}}{N^{(p-1)/2}}\left|\sum_{j=1}^p\sigma_{I\setminus\{i_j\}}(B(\sigma)g)_{i_j}\right| \\
&\le\frac{\sqrt{2\beta}p\lVert\sigma\rVert_\infty^{p-1}\lVert B(\sigma)g\rVert_\infty}{N^{(p-1)/2}} \\
&\le\frac{\sqrt{2\beta}p(\log N)^{p-1}\lVert g\rVert_2}{N^{(p-1)/2}}
=O\left(\frac{(\log N)^{p-1}}{N^{(p-2)/2}}\right)=o_N(1),
\end{aligned} 2 β ⟨ b I ( σ ) , g ⟩ ≤ N ( p − 1 ) /2 2 β j = 1 ∑ p σ I ∖ { i j } ( B ( σ ) g ) i j ≤ N ( p − 1 ) /2 2 β p ∥ σ ∥ ∞ p − 1 ∥ B ( σ ) g ∥ ∞ ≤ N ( p − 1 ) /2 2 β p ( log N ) p − 1 ∥ g ∥ 2 = O ( N ( p − 2 ) /2 ( log N ) p − 1 ) = o N ( 1 ) ,
where we recall here that p ≥ 3 p\ge3 p ≥ 3 . Since ∣ z I ( σ ) ∣ = o N ( 1 ) |z_I(\sigma)|=o_N(1) ∣ z I ( σ ) ∣ = o N ( 1 ) , we have by (102) that for N N N large enough, there exists constant c 15 = c 15 ( α , β ) > 0 c_{15}=c_{15}(\alpha,\beta)>0 c 15 = c 15 ( α , β ) > 0 such that
∣ ∑ I ∈ [ N ] p R I ( α a I ( σ ) + 2 β ⟨ b I ( σ ) , g ⟩ ) ∣ ≤ c 15 ∑ I ∈ [ N ] p ( ∣ a I ( σ ) ∣ 3 + ∣ ⟨ b I ( σ ) , g ⟩ ∣ 3 ) ≤ c 15 max I ∈ [ N ] p ( ∣ a I ( σ ) ∣ + ∣ ⟨ b I ( σ ) , g ⟩ ∣ ) ∑ I ∈ [ N ] p ( ∣ a I ( σ ) ∣ 2 + ∣ ⟨ b I ( σ ) , g ⟩ ∣ 2 ) = o N ( 1 ) ( N 2 N − 1 + p ∥ g ∥ 2 2 ) = o N ( N ) . \begin{aligned}
\left|\sum_{I\in[N]^p}R_I\left(\alpha a_I(\sigma)+\sqrt{2\beta}\langle b_I(\sigma),g\rangle\right)\right| \\
&\le c_{15}\sum_{I\in[N]^p}\left(|a_I(\sigma)|^3+|\langle b_I(\sigma),g\rangle|^3\right) \\
&\le c_{15}\max_{I\in[N]^p}\left(|a_I(\sigma)|+|\langle b_I(\sigma),g\rangle|\right)\sum_{I\in[N]^p}\left(|a_I(\sigma)|^2+|\langle b_I(\sigma),g\rangle|^2\right) \\
&=o_N(1)\left(\frac{N^2}{N-1}+p\lVert g\rVert_2^2\right)=o_N(N).
\end{aligned} I ∈ [ N ] p ∑ R I ( α a I ( σ ) + 2 β ⟨ b I ( σ ) , g ⟩ ) ≤ c 15 I ∈ [ N ] p ∑ ( ∣ a I ( σ ) ∣ 3 + ∣ ⟨ b I ( σ ) , g ⟩ ∣ 3 ) ≤ c 15 I ∈ [ N ] p max ( ∣ a I ( σ ) ∣ + ∣ ⟨ b I ( σ ) , g ⟩ ∣ ) I ∈ [ N ] p ∑ ( ∣ a I ( σ ) ∣ 2 + ∣ ⟨ b I ( σ ) , g ⟩ ∣ 2 ) = o N ( 1 ) ( N − 1 N 2 + p ∥ g ∥ 2 2 ) = o N ( N ) .
where the last equality holds by the covariance profile (90) and all estimates are uniform on the event E N 1 ∩ E N 2 ( M ) \mathcal{E}_N^1 \cap\mathcal{E}_N^2(M) E N 1 ∩ E N 2 ( M ) . We then see from (103) that
lim inf N → ∞ Λ N ( α , β ) ≥ α 2 2 + lim inf N → ∞ 1 N log E σ , g [ e β p ∥ g ∥ 2 + o N ( N ) 1 E N 1 ∩ E N 2 ( M ) ] = α 2 2 + lim inf N → ∞ 1 N log ( 1 2 π ∫ − M M e ( β p − 1 2 ) x 2 d x ) N = α 2 2 + log ( 1 2 π ∫ − M M e ( β p − 1 2 ) x 2 d x ) . \begin{aligned}
\liminf_{N\to\infty}\Lambda_N(\alpha,\beta)&\geq\frac{\alpha^2}{2}+\liminf_{N\to\infty}\frac{1}{N}\log\mathbb{E}_{\sigma,g}\left[e^{\beta p\|g\|^2+o_N(N)}\mathbf{1}_{\mathcal{E}_N^1\cap\mathcal{E}_N^2(M)}\right]\\
&=\frac{\alpha^2}{2}+\liminf_{N\to\infty}\frac{1}{N}\log\left(\frac{1}{\sqrt{2\pi}}\int_{-M}^{M}e^{(\beta p-\frac{1}{2})x^2}\,dx\right)^N\\
&=\frac{\alpha^2}{2}+\log\left(\frac{1}{\sqrt{2\pi}}\int_{-M}^{M}e^{(\beta p-\frac{1}{2})x^2}\,dx\right).
\end{aligned} N → ∞ lim inf Λ N ( α , β ) ≥ 2 α 2 + N → ∞ lim inf N 1 log E σ , g [ e β p ∥ g ∥ 2 + o N ( N ) 1 E N 1 ∩ E N 2 ( M ) ] = 2 α 2 + N → ∞ lim inf N 1 log ( 2 π 1 ∫ − M M e ( β p − 2 1 ) x 2 d x ) N = 2 α 2 + log ( 2 π 1 ∫ − M M e ( β p − 2 1 ) x 2 d x ) .
and may deduce our desired lower bound (101) by taking M → ∞ M\to\infty M → ∞ .
For β = − γ < 0 \beta=-\gamma<0 β = − γ < 0 , we apply the lower bound in Proposition 6.3 with the collection of deterministic coefficients { a I ( σ ) } I ∈ [ N ] p \{a_I(\sigma)\}_{I\in[N]^p} { a I ( σ ) } I ∈ [ N ] p and { b I ( σ ) } I ∈ [ N ] p \{b_I(\sigma)\}_{I\in[N]^p} { b I ( σ ) } I ∈ [ N ] p . By the covariance profile (90) , we have the parameters
d N = N − 1 , A N = N 2 α 2 N − 1 , τ N 2 = p . d_N=N-1,\qquad A_N=\frac{N^2\alpha^2}{N-1},\qquad\tau_N^2=p. d N = N − 1 , A N = N − 1 N 2 α 2 , τ N 2 = p .
Moreover, on the event
E N = { σ ∈ N S N − 1 : ∥ σ ∥ ∞ ≤ log N } \mathcal{E}_N=\{\sigma\in\sqrt{N}\mathbb{S}^{N-1}:\|\sigma\|_\infty\leq\log N\} E N = { σ ∈ N S N − 1 : ∥ σ ∥ ∞ ≤ log N }
which satisfies P σ ( E N ) → 1 \mathbb{P}_{\sigma}(\mathcal{E}_N)\to1 P σ ( E N ) → 1 , we have, by a similar argument as in the case β ≥ 0 \beta\geq0 β ≥ 0 , the bound
ρ N = O N ( ( log N ) p N ( p − 1 ) / 2 ) = o N ( 1 ) and Δ N = O N ( ρ N 2 N ) = O N ( ( log N ) 2 p N p − 2 ) = o N ( 1 ) . \rho_N=O_N\left(\frac{(\log N)^p}{N^{(p-1)/2}}\right)=o_N(1)
\qquad\text{and}\qquad
\Delta_N=O_N(\rho_N^2N)=O_N\left(\frac{(\log N)^{2p}}{N^{p-2}}\right)=o_N(1). ρ N = O N ( N ( p − 1 ) /2 ( log N ) p ) = o N ( 1 ) and Δ N = O N ( ρ N 2 N ) = O N ( N p − 2 ( log N ) 2 p ) = o N ( 1 ) .
Therefore, (77) implies that
Λ N ( α , β ) ≥ 1 N log E σ [ 1 E N E g [ exp ( α ∑ I ∈ [ N ] p a I ( σ ) J I − γ ∥ ∑ I ∈ [ N ] p b I ( σ ) J I ∥ 2 2 ) ] ] = N α 2 2 ( N − 1 ) − N − 1 2 N log ( 1 + 2 γ p ) + 1 N log P σ ( E N ) + o N ( 1 ) . \begin{aligned}
\Lambda_N(\alpha,\beta)&\geq\frac{1}{N}\log\mathbb{E}_{\sigma}\left[\mathbf{1}_{\mathcal{E}_N}\mathbb{E}_g\left[\exp\left(\alpha\sum_{I\in[N]^p}a_I(\sigma)J_I-\gamma\left\|\sum_{I\in[N]^p}b_I(\sigma)J_I\right\|_2^2\right)\right]\right]\\
&=\frac{N\alpha^2}{2(N-1)}-\frac{N-1}{2N}\log(1+2\gamma p)+\frac{1}{N}\log\mathbb{P}_{\sigma}(\mathcal{E}_N)+o_N(1).
\end{aligned} Λ N ( α , β ) ≥ N 1 log E σ 1 E N E g exp α I ∈ [ N ] p ∑ a I ( σ ) J I − γ I ∈ [ N ] p ∑ b I ( σ ) J I 2 2 = 2 ( N − 1 ) N α 2 − 2 N N − 1 log ( 1 + 2 γ p ) + N 1 log P σ ( E N ) + o N ( 1 ) .
and this concludes the proof.
Proof of Main Results
Proof of Theorem 1.5. Recall from (69) and (13) the following notations:
X N J ( σ ) = H N J ( σ ) N ( N − 1 ) and y N J ( σ ) = ∥ B ( σ ) ⊤ ∇ H N J ( σ ) ∥ 2 2 N . X_N^J(\sigma)=\frac{H_N^J(\sigma)}{\sqrt{N(N-1)}}\qquad\text{and}\qquad y_N^J(\sigma)=\frac{\|B(\sigma)^\top\nabla H_N^J(\sigma)\|_2^2}{N}. X N J ( σ ) = N ( N − 1 ) H N J ( σ ) and y N J ( σ ) = N ∥ B ( σ ) ⊤ ∇ H N J ( σ ) ∥ 2 2 .
By (71) , the limiting logarithmic moment generating function of ( X N J ( σ ) , y N J ( σ ) ) (X_N^J(\sigma),y_N^J(\sigma)) ( X N J ( σ ) , y N J ( σ )) is
Λ ( α , β ) = lim N → ∞ Λ N ( α , β ) = { α 2 2 − 1 2 log ( 1 − 2 β p ) , β < 1 2 p , ∞ , β ≥ 1 2 p . \Lambda(\alpha,\beta)=\lim_{N\to\infty}\Lambda_N(\alpha,\beta)=
\begin{cases}
\frac{\alpha^2}{2}-\frac{1}{2}\log(1-2\beta p),&\beta<\frac{1}{2p},\\
\infty,&\beta\geq\frac{1}{2p}.
\end{cases} Λ ( α , β ) = N → ∞ lim Λ N ( α , β ) = { 2 α 2 − 2 1 log ( 1 − 2 β p ) , ∞ , β < 2 p 1 , β ≥ 2 p 1 .
Its effective domain is D Λ = R × ( − ∞ , 1 / ( 2 p ) ) D_\Lambda=\mathbb{R}\times(-\infty,1/(2p)) D Λ = R × ( − ∞ , 1/ ( 2 p )) . The function Λ \Lambda Λ is differentiable on D Λ D_\Lambda D Λ , lower semicontinuous on R 2 \mathbb{R}^2 R 2 , and
∥ ∇ Λ ( α , β ) ∥ 2 = ∥ ( α , p 1 − 2 p β ) ∥ 2 → ∞ as β ↑ 1 2 p . (104) \|\nabla\Lambda(\alpha,\beta)\|_2=\left\|\left(\alpha,\frac{p}{1-2p\beta}\right)\right\|_2\to\infty\quad\text{as}\quad\beta\uparrow\frac{1}{2p}. \tag*{(104)} ∥∇Λ ( α , β ) ∥ 2 = ( α , 1 − 2 pβ p ) 2 → ∞ as β ↑ 2 p 1 . (104)
so Λ \Lambda Λ is essentially smooth (see [14 Definition 2.3.5] ). Therefore, by Gärtner-Ellis theorem (see [14 Theorem 2.3.6] ), ( X N J ( σ ) , y N J ( σ ) ) (X_N^J(\sigma), y_N^J(\sigma)) ( X N J ( σ ) , y N J ( σ )) satisfies the LDP at speed N N N with the good rate function
Λ ∗ ( a , b ) = sup α ∈ R , β < 1 / ( 2 p ) [ ( α a + β b ) − ( α 2 2 − 1 2 log ( 1 − 2 β p ) ) ] . \Lambda^*(a,b)=\sup_{\alpha\in\mathbb{R},\beta<1/(2p)}\left[(\alpha a+\beta b)-\left(\frac{\alpha^2}{2}-\frac{1}{2}\log(1-2\beta p)\right)\right]. Λ ∗ ( a , b ) = α ∈ R , β < 1/ ( 2 p ) sup [ ( α a + β b ) − ( 2 α 2 − 2 1 log ( 1 − 2 β p ) ) ] .
For b > 0 b>0 b > 0 , the optimizers are α = a \alpha=a α = a and β = ( b − p ) / ( 2 p b ) \beta=(b-p)/(2pb) β = ( b − p ) / ( 2 p b ) , while for b ≤ 0 b\leq0 b ≤ 0 the supremum is infinite. Hence Λ ∗ = I 2 \Lambda^*=\mathcal{I}_2 Λ ∗ = I 2 , which proves Theorem 1.5 .
Proof of Theorem 1.1. Since Z N : = Z / N − 1 Z_N:=Z/\sqrt{N-1} Z N := Z / N − 1 is independent of ( X N J ( σ ) , y N J ( σ ) ) (X_N^J(\sigma),y_N^J(\sigma)) ( X N J ( σ ) , y N J ( σ )) and satisfies the LDP at speed N N N with the good rate function c 2 / 2 c^2/2 c 2 /2 , the sequence
( X N J ( σ ) , y N J ( σ ) , Z N ) ∈ D : = R × [ 0 , ∞ ) × R (105) (X_N^J(\sigma),y_N^J(\sigma),Z_N)\in\mathcal{D}:=\mathbb{R}\times[0,\infty)\times\mathbb{R} \tag*{(105)} ( X N J ( σ ) , y N J ( σ ) , Z N ) ∈ D := R × [ 0 , ∞ ) × R (105)
satisfies the LDP at speed N N N with the good rate function
I 3 ( a , b , c ) = I 2 ( a , b ) + c 2 2 = { a 2 2 + c 2 2 + b − p 2 p + 1 2 log ( p b ) , b > 0 , ∞ , b ≤ 0. \mathcal{I}_3(a,b,c)=\mathcal{I}_2(a,b)+\frac{c^2}{2}=
\begin{cases}
\frac{a^2}{2}+\frac{c^2}{2}+\frac{b-p}{2p}+\frac{1}{2}\log\left(\frac{p}{b}\right), & b>0,\\
\infty, & b\leq0.
\end{cases} I 3 ( a , b , c ) = I 2 ( a , b ) + 2 c 2 = { 2 a 2 + 2 c 2 + 2 p b − p + 2 1 log ( b p ) , ∞ , b > 0 , b ≤ 0.
Next, we compute the exponential rate of ℓ N ( x , δ ) \ell_N(x,\delta) ℓ N ( x , δ ) , as defined in (40) for a fixed x ∈ R x\in\mathbb{R} x ∈ R and δ > 0 \delta>0 δ > 0 . Set
T ( a , c ) = p p − 1 ( t a + 1 − t c ) . T(a,c)=\sqrt{\frac{p}{p-1}}\left(\sqrt{t}a+\sqrt{1-t}c\right). T ( a , c ) = p − 1 p ( t a + 1 − t c ) .
The set { ( a , b , c ) ∈ D : ∣ T ( a , c ) − x ∣ ≤ δ } \{(a,b,c)\in\mathcal{D}: |T(a,c)-x|\leq\delta\} {( a , b , c ) ∈ D : ∣ T ( a , c ) − x ∣ ≤ δ } is closed in D \mathcal{D} D , and the function ( a , b , c ) ↦ − ( t b ) / ( 2 p ( 1 − t ) ) (a,b,c)\mapsto-(tb)/(2p(1-t)) ( a , b , c ) ↦ − ( t b ) / ( 2 p ( 1 − t )) is continuous and bounded above on D \mathcal{D} D . Therefore, by Varadhan’s lemma, more precisely, see [14 Exercise 4.3.11] , we obtain
lim sup N → ∞ 1 N log ℓ N ( x , δ ) = lim sup N → ∞ 1 N log E σ , J , Z [ exp ( N ( − t y N J ( σ ) 2 p ( 1 − t ) ) ) 1 { ∣ T ( X N J ( σ ) , Z N ) − x ∣ ≤ δ } ] ≤ sup ∣ T ( a , c ) − x ∣ ≤ δ b > 0 { − t b 2 p ( 1 − t ) − I 3 ( a , b , c ) } = 1 2 log ( 1 − t ) − p − 1 2 p ( ∣ x ∣ − δ ) + 2 . (106) \begin{aligned}
\limsup_{N\to\infty}\frac{1}{N}\log\ell_N(x,\delta)
&=\limsup_{N\to\infty}\frac{1}{N}\log\mathbb{E}_{\sigma,J,Z}\left[\exp\left(N\left(-\frac{t y_N^J(\sigma)}{2p(1-t)}\right)\right)\mathbf{1}_{\{|T(X_N^J(\sigma),Z_N)-x|\leq\delta\}}\right]\\
&\leq\sup_{\substack{|T(a,c)-x|\leq\delta\\b>0}}\left\{-\frac{tb}{2p(1-t)}-\mathcal{I}_3(a,b,c)\right\}\\
&=\frac{1}{2}\log(1-t)-\frac{p-1}{2p}(|x|-\delta)_+^2. \tag*{(106)}
\end{aligned} N → ∞ lim sup N 1 log ℓ N ( x , δ ) = N → ∞ lim sup N 1 log E σ , J , Z [ exp ( N ( − 2 p ( 1 − t ) t y N J ( σ ) ) ) 1 { ∣ T ( X N J ( σ ) , Z N ) − x ∣ ≤ δ } ] ≤ ∣ T ( a , c ) − x ∣ ≤ δ b > 0 sup { − 2 p ( 1 − t ) t b − I 3 ( a , b , c ) } = 2 1 log ( 1 − t ) − 2 p p − 1 ( ∣ x ∣ − δ ) + 2 . (106)
Indeed, the optimization over b b b is attained at b = p ( 1 − t ) b=p(1-t) b = p ( 1 − t ) and has value log ( 1 − t ) / 2 \log(1-t)/2 log ( 1 − t ) /2 , while
inf ∣ T ( a , c ) − x ∣ ≤ δ a 2 + c 2 2 = p − 1 2 p ( ∣ x ∣ − δ ) + 2 . \inf_{|T(a,c)-x|\leq\delta}\frac{a^2+c^2}{2}=\frac{p-1}{2p}(|x|-\delta)_+^2. ∣ T ( a , c ) − x ∣ ≤ δ inf 2 a 2 + c 2 = 2 p p − 1 ( ∣ x ∣ − δ ) + 2 .
Similarly, applying Varadhan’s lemma to the open set { ( a , b , c ) ∈ D : ∣ T ( a , c ) − x ∣ < δ } \{(a,b,c)\in\mathcal{D}: |T(a,c)-x|<\delta\} {( a , b , c ) ∈ D : ∣ T ( a , c ) − x ∣ < δ } , we deduce
lim inf N → ∞ 1 N log ℓ N ( x , δ ) ≥ sup ∣ T ( a , c ) − x ∣ < δ b > 0 { − t b 2 p ( 1 − t ) − I 3 ( a , b , c ) } , \liminf_{N\to\infty}\frac{1}{N}\log\ell_N(x,\delta)\geq\sup_{\substack{|T(a,c)-x|<\delta\\b>0}}\left\{-\frac{tb}{2p(1-t)}-\mathcal{I}_3(a,b,c)\right\}, N → ∞ lim inf N 1 log ℓ N ( x , δ ) ≥ ∣ T ( a , c ) − x ∣ < δ b > 0 sup { − 2 p ( 1 − t ) t b − I 3 ( a , b , c ) } ,
which has the same optimal value as in (106) . Therefore,
lim N → ∞ 1 N log ℓ N ( x , δ ) = 1 2 log ( 1 − t ) − p − 1 2 p ( ∣ x ∣ − δ ) + 2 . (107) \lim_{N\to\infty}\frac{1}{N}\log\ell_N(x,\delta)=\frac{1}{2}\log(1-t)-\frac{p-1}{2p}(|x|-\delta)_+^2. \tag*{(107)} N → ∞ lim N 1 log ℓ N ( x , δ ) = 2 1 log ( 1 − t ) − 2 p p − 1 ( ∣ x ∣ − δ ) + 2 . (107)
Recall the quantity L N ( u ) \mathcal{L}_N(u) L N ( u ) from (39) . Combining Proposition 5.2 with (107) yields
lim sup N → ∞ 1 N log L N ( u ) ≤ 1 2 log ( 1 − t ) + sup x ≤ 2 u / E ∞ ( Ω ( x ) − p − 1 2 p x 2 ) . \limsup_{N\to\infty}\frac{1}{N}\log\mathcal{L}_N(u)\leq\frac{1}{2}\log(1-t)+\sup_{x\leq2u/E_\infty}\left(\Omega(x)-\frac{p-1}{2p}x^2\right). N → ∞ lim sup N 1 log L N ( u ) ≤ 2 1 log ( 1 − t ) + x ≤ 2 u / E ∞ sup ( Ω ( x ) − 2 p p − 1 x 2 ) .
Indeed, the functions
F δ ( x ) = Ω ( x ) − p − 1 2 p ( ∣ x ∣ − δ ) + 2 F_\delta(x)=\Omega(x)-\frac{p-1}{2p}(|x|-\delta)_+^2 F δ ( x ) = Ω ( x ) − 2 p p − 1 ( ∣ x ∣ − δ ) + 2
converge uniformly to F 0 ( x ) F_0(x) F 0 ( x ) on a compact set containing all their maximizers for 0 ≤ δ ≤ 1 0\leq\delta\leq1 0 ≤ δ ≤ 1 . Similarly, Proposition 5.3 and (107) give
lim inf N → ∞ 1 N log L N ( u ) ≥ 1 2 log ( 1 − t ) + sup x < 2 u / E ∞ ( Ω ( x ) − p − 1 2 p x 2 ) . \liminf_{N\to\infty}\frac{1}{N}\log\mathcal{L}_N(u)\geq\frac{1}{2}\log(1-t)+\sup_{x<2u/E_\infty}\left(\Omega(x)-\frac{p-1}{2p}x^2\right). N → ∞ lim inf N 1 log L N ( u ) ≥ 2 1 log ( 1 − t ) + x < 2 u / E ∞ sup ( Ω ( x ) − 2 p p − 1 x 2 ) .
Since F 0 ( x ) F_0(x) F 0 ( x ) is continuous, its suprema on x < 2 u / E ∞ x<2u/E_\infty x < 2 u / E ∞ and x ≤ 2 u / E ∞ x\leq2u/E_\infty x ≤ 2 u / E ∞ are the same. It follows
lim N → ∞ 1 N log L N ( u ) = 1 2 log ( 1 − t ) + sup x ≤ 2 u / E ∞ ( Ω ( x ) − p − 1 2 p x 2 ) . (108) \lim_{N\to\infty}\frac{1}{N}\log\mathcal{L}_N(u)=\frac{1}{2}\log(1-t)+\sup_{x\leq2u/E_\infty}\left(\Omega(x)-\frac{p-1}{2p}x^2\right). \tag*{(108)} N → ∞ lim N 1 log L N ( u ) = 2 1 log ( 1 − t ) + x ≤ 2 u / E ∞ sup ( Ω ( x ) − 2 p p − 1 x 2 ) . (108)
Combining (108) with the Kac-Rice formula (12) , we obtain
lim N → ∞ 1 N log E J , G [ Crt t ( ( − ∞ , u ) ) ] = 1 2 log ( p − 1 ) + 1 2 + sup x ≤ 2 u / E ∞ ( Ω ( x ) − p − 1 2 p x 2 ) . (109) \lim_{N\to\infty}\frac{1}{N}\log\mathbb{E}_{J,G}\left[\operatorname{Crt}_t((-\infty,u))\right]=\frac{1}{2}\log(p-1)+\frac{1}{2}+\sup_{x\leq2u/E_\infty}\left(\Omega(x)-\frac{p-1}{2p}x^2\right). \tag*{(109)} N → ∞ lim N 1 log E J , G [ Crt t (( − ∞ , u )) ] = 2 1 log ( p − 1 ) + 2 1 + x ≤ 2 u / E ∞ sup ( Ω ( x ) − 2 p p − 1 x 2 ) . (109)
The right-hand side of (109) does not depend on t t t , and therefore equals the corresponding expression at t = 0 t=0 t = 0 . This proves Theorem 1.1.
Useful Inequalities
Lemma A.1 (Gaussian Brascamp-Lieb inequality). Let u 1 , … , u m ∈ R d u_1,\ldots,u_m\in\mathbb{R}^d u 1 , … , u m ∈ R d be unit vectors and let λ 1 , … , λ m > 0 \lambda_1,\ldots,\lambda_m>0 λ 1 , … , λ m > 0 satisfy
∑ j = 1 m λ j u j u j T = I d . \sum_{j=1}^{m}\lambda_j u_j u_j^{\mathsf T}=I_d. j = 1 ∑ m λ j u j u j T = I d . If g ∼ Normal ( 0 , I d ) g\sim\operatorname{Normal}(0,I_d) g ∼ Normal ( 0 , I d ) and Z ∼ Normal ( 0 , 1 ) Z\sim\operatorname{Normal}(0,1) Z ∼ Normal ( 0 , 1 ) , then for any nonnegative measurable functions f j : R → [ 0 , ∞ ) f_j:\mathbb{R}\to[0,\infty) f j : R → [ 0 , ∞ ) with E [ f j ( Z ) ] < ∞ \mathbb{E}[f_j(Z)]<\infty E [ f j ( Z )] < ∞ ,
E [ ∏ j = 1 m f j ( ⟨ u j , g ⟩ ) λ j ] ≤ ∏ j = 1 m E [ f j ( Z ) ] λ j . (110) \mathbb{E}\left[\prod_{j=1}^{m}f_j(\langle u_j,g\rangle)^{\lambda_j}\right]\leq\prod_{j=1}^{m}\mathbb{E}[f_j(Z)]^{\lambda_j}. \tag*{(110)} E [ j = 1 ∏ m f j (⟨ u j , g ⟩ ) λ j ] ≤ j = 1 ∏ m E [ f j ( Z ) ] λ j . (110)
Proof. This is a rank-one specialization of [11 Theorem 4] .
Lemma A.2. If X 1 , … , X n X_1,\ldots,X_n X 1 , … , X n are (not necessarily independent) random variables satisfying (SG) with uniform κ S G \kappa_{\mathrm{SG}} κ SG , there exists an absolute constant c 16 > 0 c_{16}>0 c 16 > 0 such that for all k ∈ N k\in\mathbb{N} k ∈ N ,
E [ ( max 1 ≤ j ≤ n X j ) k ] 1 / k ≤ c 16 κ S G log n + k . (111) \mathbb{E}\left[\left(\max_{1\leq j\leq n}X_j\right)^k\right]^{1/k}\leq c_{16}\kappa_{\mathrm{SG}}\sqrt{\log n+k}. \tag*{(111)} E [ ( 1 ≤ j ≤ n max X j ) k ] 1/ k ≤ c 16 κ SG log n + k . (111)
Proof. By the condition (SG) and union bound, we have
P ( ∣ max 1 ≤ j ≤ n X j ∣ ≥ h ) ≤ 2 n e − h 2 / ( 2 κ S G 2 ) . \mathbb{P}\left(\left|\max_{1\leq j\leq n} X_j\right|\geq h\right)\leq2n e^{-h^2/(2\kappa_{\mathrm{SG}}^2)}. P ( 1 ≤ j ≤ n max X j ≥ h ) ≤ 2 n e − h 2 / ( 2 κ SG 2 ) .
Define a : = ( 2 κ S G 2 log ( 2 n ) ) 1 / 2 a := (2\kappa_{\mathrm{SG}}^2\log(2n))^{1/2} a := ( 2 κ SG 2 log ( 2 n ) ) 1/2 and Y = ( ∣ max 1 ≤ j ≤ n X j ∣ − a ) + Y=(|\max_{1\leq j\leq n}X_j|-a)_+ Y = ( ∣ max 1 ≤ j ≤ n X j ∣ − a ) + . Then,
E [ ∣ Y ∣ k ] = k ∫ 0 ∞ h k − 1 P ( ∣ Y ∣ ≥ h ) d h = k ∫ 0 ∞ h k − 1 P ( ∣ max 1 ≤ j ≤ n X j ∣ ≥ a + h ) d h \begin{aligned}
\mathbb{E}[|Y|^k]=k\int_0^\infty h^{k-1}\mathbb{P}(|Y|\geq h)\,dh \\
&=k\int_0^\infty h^{k-1}\mathbb{P}\left(\left|\max_{1\leq j\leq n}X_j\right|\geq a+h\right)\,dh
\end{aligned} E [ ∣ Y ∣ k ] = k ∫ 0 ∞ h k − 1 P ( ∣ Y ∣ ≥ h ) d h = k ∫ 0 ∞ h k − 1 P ( 1 ≤ j ≤ n max X j ≥ a + h ) d h
≤ 2 n k ∫ 0 ∞ h k − 1 e − ( a + h ) 2 / ( 2 κ S G 2 ) d h ≤ k ∫ 0 ∞ h k − 1 e − h 2 / ( 2 κ S G 2 ) d h = k ⋅ 2 k / 2 − 1 κ S G k Γ ( k 2 ) . \leq2nk\int_0^\infty h^{k-1}e^{-(a+h)^2/(2\kappa_{\mathrm{SG}}^2)}\,dh\leq k\int_0^\infty h^{k-1}e^{-h^2/(2\kappa_{\mathrm{SG}}^2)}\,dh=k\cdot2^{k/2-1}\kappa_{\mathrm{SG}}^k\Gamma\left(\frac{k}{2}\right). ≤ 2 nk ∫ 0 ∞ h k − 1 e − ( a + h ) 2 / ( 2 κ SG 2 ) d h ≤ k ∫ 0 ∞ h k − 1 e − h 2 / ( 2 κ SG 2 ) d h = k ⋅ 2 k /2 − 1 κ SG k Γ ( 2 k ) .
Since Γ ( k / 2 ) 1 / k = O k ( k ) \Gamma(k/2)^{1/k}=O_k(\sqrt{k}) Γ ( k /2 ) 1/ k = O k ( k ) as k → ∞ k\to\infty k → ∞ , we have
∥ max 1 ≤ j ≤ n X j ∥ L k ≤ a + ∥ Y ∥ L k = O ( κ S G log n + k ) . \left\|\max_{1\leq j\leq n}X_j\right\|_{L^k}\leq a+\|Y\|_{L^k}=O\left(\kappa_{\mathrm{SG}}\sqrt{\log n+k}\right). 1 ≤ j ≤ n max X j L k ≤ a + ∥ Y ∥ L k = O ( κ SG log n + k ) .
and this ends the proof for the lemma.
Lemma A.3 ([9 Lemma 6.3] ). For h ≥ 8 h\geq8 h ≥ 8 and all N ∈ N N\in\mathbb{N} N ∈ N ,
P ( ∥ G O E N ∥ o p ≥ h ) ≤ e − N h 2 / 9 . (112) \mathbb{P}(\|\mathrm{GOE}_N\|_{\mathrm{op}}\geq h)\leq e^{-Nh^2/9}. \tag*{(112)} P ( ∥ GOE N ∥ op ≥ h ) ≤ e − N h 2 /9 . (112)