Proof. The proof combines the matrix Chernoff method of Tropp [60] with the dimension-free trace argument of [62]. We first project onto an arbitrary finite-dimensional subspace. Let \(\Pi\) be an orthogonal projection of finite rank and put \[Y_i=\Pi(\phi_i\otimes\phi_i)\Pi.\] Then \(0\preceq Y_i\preceq p\Pi\) and \[\mathbb{E}Y_i=\Pi\mathcal{C}\Pi=:\mathcal{C}_\Pi.\] For \(\theta>0\) and any \(0\le y\le p\), convexity of the exponential on \([0,p]\) gives \[e^{\theta y} \le 1+\frac{e^{\theta p}-1}{p}y.\] By the transfer rule for matrix functions [60], \[e^{\theta Y_i} \preceq \Pi+\frac{e^{\theta p}-1}{p}Y_i\] on \(\operatorname{range}(\Pi)\), and hence \[\mathbb{E}e^{\theta Y_i} \preceq \Pi+\frac{e^{\theta p}-1}{p}\mathcal{C}_\Pi \preceq \exp\left(\frac{e^{\theta p}-1}{p}\mathcal{C}_\Pi\right).\] Let \(S_\Pi=\sum_iY_i\). The matrix Laplace-transform method gives \[\mathbb{E}\operatorname{tr}e^{\theta S_\Pi} \le \operatorname{tr}\exp\left( \sum_{i=1}^n\log \mathbb{E}e^{\theta Y_i} \right) \le \operatorname{tr}\exp\left( n\frac{e^{\theta p}-1}{p}\mathcal{C}_\Pi \right).\] The last step uses operator monotonicity of the logarithm and trace monotonicity of the matrix exponential [60]. Because \(S_\Pi\ge0\), the event \(\lambda_{\max}(S_\Pi)\ge t\) implies \(\operatorname{tr}(e^{\theta S_\Pi}-\Pi)\ge e^{\theta t}-1\). Hence \[\mathbb{P}\{\lambda_{\max}(S_\Pi)\ge t\} \le \inf_{\theta>0} \frac{ \operatorname{tr}\!\left[ \exp\!\left( n\frac{e^{\theta p}-1}{p}\mathcal{C}_\Pi \right)-\Pi \right]}{e^{\theta t}-1}.\] The remaining trace is controlled by the effective mass \(\operatorname{tr}(\mathcal{C}_\Pi)\le p\). Set \(a_\theta=n(e^{\theta p}-1)/p\). Since \(\mathcal{C}_\Pi\preceq\kappa\Pi\), \[\begin{align} \operatorname{tr}(e^{a_\theta\mathcal{C}_\Pi}-\Pi) &= \sum_s(e^{a_\theta\lambda_s(\mathcal{C}_\Pi)}-1) \\ &\le a_\theta e^{a_\theta\kappa}\operatorname{tr}(\mathcal{C}_\Pi) \le a_\theta p\,e^{a_\theta\kappa}. \end{align}\]

Choose \(\theta=1/p\). Then \(a_\theta=(e-1)n/p\), and for all \(t\ge p\), \[\mathbb{P}\{\lambda_{\max}(S_\Pi)\ge t\} \le \exp\left( C+\log n+C\frac{n\kappa}{p}-\frac{t}{Cp} \right). \label{eq:hilbert-finite-rank-tail}\tag{16}\] Taking \[t=C_D(n\kappa+p\log n)\] with \(C_D\) large enough gives probability at most \(n^{-D}\), uniformly in \(\Pi\).

To remove the projection, choose a countable orthonormal basis \((e_m)_{m\ge1}\) of the separable space \(\mathcal{H}\), and let \(\Pi_m\) be the projection onto \(\operatorname{span}\{e_1,\ldots,e_m\}\). For \(S=\sum_{i=1}^n\phi_i\otimes\phi_i\succeq0\), the variational formula gives \[\|\Pi_mS\Pi_m\|_{\mathrm{op}}\uparrow\|S\|_{\mathrm{op}}.\] Therefore \[\{\|S\|_{\mathrm{op}}>t\} = \bigcup_{m\ge1}\{\|\Pi_mS\Pi_m\|_{\mathrm{op}}>t\}.\] Continuity from below and the finite-rank estimate 16 complete the proof. ◻

Proof. Apply 2 with tail exponent \(D+4\) to \(\phi_{U_i}=h(U_i,\cdot)\). The section and population covariance bounds are 19 and 20 . Since \(\Sigma_U\) and the operator in 18 have the same nonzero eigenvalues, the claimed bound follows from 2. ◻

Proof. By 21 , \(\mathbb{E}_U q_U\le n^{-2D-7}\). Markov’s inequality gives \[\mathbb{P}_U\{q_U>n^{-D-3}\} \le n^{D+3}\mathbb{E}_U q_U \le n^{-D-4}.\] ◻

Proof. Step 1: Truncation and the conditional mean.

Fix a realization of \(U\) satisfying the events in 4 3, and truncate each column at the deterministic level \(R=C_D\sqrt{np}\) required by matrix Chernoff. Namely, set \[\widetilde{g}(V):= g_U(V)\mathbf{1}_{\{\|g_U(V)\|_2\le R\}}.\] Let \(\widetilde{G}\) be the matrix with columns \(\widetilde{g}(V_1),\ldots,\widetilde{g}(V_n)\). Then \[\widetilde{G}\widetilde{G}^\top = \sum_{j=1}^n \widetilde{g}(V_j)\widetilde{g}(V_j)^\top.\] The summands \[Y_j:=\widetilde{g}(V_j)\widetilde{g}(V_j)^\top\] are conditionally independent positive-semidefinite matrices and satisfy \[0\preceq Y_j\preceq R^2I_n.\] Moreover, \[\sum_{j=1}^n\mathbb{E}[Y_j\mid U] \preceq n\mathbb{E}_V[g_U(V)g_U(V)^\top] = n\Sigma_U.\] On the good covariance event of 3, \[\mu_U:= \left\|\sum_{j=1}^n\mathbb{E}[Y_j\mid U]\right\|_{\mathrm{op}} \le n\|\Sigma_U\|_{\mathrm{op}} \le C_D(n^2\Lambda^2+np\log n). \label{eq:decoupled-mu-bound}\tag{22}\]

Step 2: Conditional matrix Chernoff.

Applying 1, conditionally on \(U\), to \(\widetilde{G}\widetilde{G}^\top\) with \(L=R^2\) and \(s=(D+3)\log n\), we obtain \[L(s+\log n)=R^2(D+4)\log n\le C_Dnp\log n.\] Combining 1 with 22 shows that, with conditional probability at least \(1-n^{-D-3}\), \[\|\widetilde{G}\widetilde{G}^\top\|_{\mathrm{op}} \le C_D(n^2\Lambda^2+np\log n).\] Taking square roots gives \[\|\widetilde{G}\|_{\mathrm{op}} \le C_D\left(n\Lambda+\sqrt{np\log n}\right).\]

Step 3: Removal of the truncation.

Finally, on the event \(\max_{1\le j\le n}\|g_U(V_j)\|_2\le R\), which has conditional probability at least \(1-nq_U\ge1-n^{-D-2}\) by 4, the original matrix satisfies \[G=\widetilde{G}.\] Combining this conditional probability with the events in 4 3 and then integrating over \(U\) proves the claim. ◻

Proof. This is the standard tail decoupling inequality for Banach-space-valued canonical U-statistics of order two; see de la Peña and Giné [61]. We apply that result in the Banach space of \(n\times n\) matrices equipped with the operator norm, to the matrix-valued kernel whose \((i,j)\) entry is \(k(U_i,U_j)\mathbf{1}_{i\ne j}\). Its decoupled version is exactly \(G^0\). ◻

Proof of 1. Let \(V_1,\ldots,V_n\) be the independent copy introduced in 17 , so that \(G=(h(U_i,V_j))_{i,j=1}^n\). Let \(C_0\ge1\) be the universal constant in 5. Apply 1 with tail parameter \(D+2+\log_2 C_0\). The resulting failure probability is \(n^{-D-3-\log_2 C_0}\), which is at most \(C_0^{-1}n^{-D-3}\) because \(n\ge2\). After relabeling the constant in the operator-norm threshold, we therefore obtain \[\mathbb{P}\left\{ \|G\|_{\mathrm{op}}> C_D\left(\sqrt{np\log n}+n\Lambda\right) \right\} \le C_0^{-1}n^{-D-3}. \label{eq:cap-full-decoupled-tail}\tag{23}\]

The decoupling inequality in 5 is stated for the zero-diagonal matrix \[G^0_{ij}=h(U_i,V_j)\mathbf{1}_{\{i\ne j\}}.\] If \[D_G:=\operatorname{diag}(h(U_1,V_1),\ldots,h(U_n,V_n)),\] then \(G^0=G-D_G\). The triangle inequality therefore gives \[\|G^0\|_{\mathrm{op}} \le \|G\|_{\mathrm{op}} +\|D_G\|_{\mathrm{op}}. \label{eq:cap-full-to-zero-diagonal}\tag{24}\] Since \[h(u,v)=\mathbf{1}_{\{\langle u,v\rangle\ge\tau\}}-p,\] we have \(|h(u,v)|\le1\) for every \(u,v\in\mathbb{S}^{d-1}\). Consequently, \[\|D_G\|_{\mathrm{op}} =\max_{i\in[n]}|h(U_i,V_i)| \le1.\] Under \(np\ge C_D\log n\), this additive constant is absorbed by \(\sqrt{np\log n}\) after increasing \(C_D\). Thus 23 and 24 imply \[\mathbb{P}\left\{ \|G^0\|_{\mathrm{op}}> C_D\left(\sqrt{np\log n}+n\Lambda\right) \right\} \le C_0^{-1}n^{-D-3}. \label{eq:cap-zero-diagonal-tail}\tag{25}\]

For the degree-one-subtracted spherical kernel used later, the corresponding diagonal maximum is estimated directly in 2; the independent inner-product tail makes it smaller than the stated sparse term. 4 instead works directly with the zero-diagonal decoupled Gaussian matrix.

Define \[M_{ij}=h(U_i,U_j)\mathbf{1}_{\{i\ne j\}}.\] For \(i\ne j\), the definitions of \(A\) and \(h\) give \(M_{ij}=A_{ij}-p\), while \(M_{ii}=0\). Since \(\mathbb{E}A=p(J-I_n)\), it follows entry by entry that \[M=A-\mathbb{E}A. \label{eq:cap-centered-matrix-identification}\tag{26}\]

Set \[t=C_0C_D\left(\sqrt{np\log n}+n\Lambda\right).\] Applying 5, followed by 25 , yields \[\begin{align} \mathbb{P}\left\{\|A-\mathbb{E}A\|_{\mathrm{op}}>t\right\} &=\mathbb{P}\left\{\|M\|_{\mathrm{op}}>t\right\}\\ &\le C_0\,\mathbb{P}\left\{\|G^0\|_{\mathrm{op}}>t/C_0\right\}\\ &\le n^{-D-3} \le n^{-D}, \end{align}\] where the first equality uses 26 . Absorbing \(C_0\) into \(C_D\), we have proved that, with probability at least \(1-n^{-D}\), \[\|A-\mathbb{E}A\|_{\mathrm{op}} \le C_D\left(\sqrt{np\log n}+n\Lambda\right). \label{eq:cap-preliminary-concentration}\tag{27}\]

By 5, \(\Lambda\le Cp\tau\). Hence \(n\Lambda\le Cnp\tau\), and substituting this bound into 27 gives 3 . ◻

Proof. The \(d\) nonzero eigenvalues of \(S\) are at least \(\gamma\), while all other eigenvalues vanish. Weyl’s inequality therefore leaves a gap of at least \(\gamma/2\) between the perturbed signal cluster and the remaining eigenvalues. The Frobenius form of the Davis–Kahan theorem [65], [66] gives \[\|\sin\Theta(\widehat Y,Y)\|_{\mathrm F} \le \frac{2\sqrt d\,\|E\|_{\mathrm{op}}}{\gamma}. \label{eq:frobenius-davis-kahan}\tag{28}\] For the orthogonal Procrustes alignment [53], \[\min_{O\in O(d)}\|\widehat YO-Y\|_{\mathrm F} \le \sqrt2\, \|\sin\Theta(\widehat Y,Y)\|_{\mathrm F}. \label{eq:frobenius-procrustes}\tag{29}\] Combining 28 and 29 proves the claim. ◻

Proof. Since \((PO)(PO)^\top=PP^\top\), write \[PP^\top-QQ^\top =(PO-Q)(PO)^\top+Q(PO-Q)^\top.\] The claim follows from \(\|MN^\top\|_{\mathrm F}\le\|M\|_{\mathrm F}\|N\|_{\mathrm{op}}\). ◻

Proof. Step 1: Section norm and conditional covariance.

The kernel \(h_\perp\) is symmetric and canonical, and its integral-operator norm is \(\Lambda_{\ge2}\). Its sections satisfy \[\begin{align} \int h_\perp(u,v)^2\,d\sigma(v) &\le 2\int h(u,v)^2\,d\sigma(v) +2d^2\lambda_1^2\int\langle u,v\rangle^2\,d\sigma(v)\\ &\le 2p+2d\lambda_1^2\le Cp. \end{align}\] Here \(d\lambda_1^2\le Cp^2L\le Cp\), where \(L=1+\log(1/p)\), by 15.

We now verify the two inputs to the decoupled argument. Let \(V_1,\ldots,V_n\) be an independent spherical sample. Applying 2 to the sections \(\phi_u=h_\perp(u,\cdot)\) gives, with probability at least \(1-n^{-D-4}\) over \(U=(U_1,\ldots,U_n)\), \[\left\|\sum_{i=1}^n\phi_{U_i}\otimes\phi_{U_i}\right\|_{\mathrm{op}} \le C_D\bigl(n\Lambda_{\ge2}^2+p\log n\bigr). \label{eq:higher-harmonic-covariance-event}\tag{31}\] Here the covariance operator is \(T_{h_\perp}^2\), whose norm is \(\Lambda_{\ge2}^2\).

Step 2: Uniform column bound.

For the uniform column bound, fix \(v\in\mathbb{S}^{d-1}\). Then \[\sum_{i=1}^n h_\perp(U_i,v)^2 \le 2\sum_{i=1}^n h(U_i,v)^2 +2d^2\lambda_1^2\sum_{i=1}^n\langle U_i,v\rangle^2.\] For fixed \(v\), the first sum is at most a constant times a \(\operatorname{Bin}(n,p)\) variable plus \(np^2\). Hence the binomial Chernoff bound [64] gives \[\mathbb{P}_{U,V}\left\{ \sum_{i=1}^nh(U_i,V)^2>C_Dnp \right\}\le n^{-2D-10}. \label{eq:higher-harmonic-column-tail}\tag{32}\] If \(q_U\) denotes the conditional probability of this event given \(U\), Markov’s inequality applied to 32 shows that \(q_U\le n^{-D-5}\) outside an event of probability \(n^{-D-5}\). Independently, the standard sample-covariance bound for the isotropic vectors \(\sqrt d\,U_i\) [64] gives \[\left\|\sum_{i=1}^nU_iU_i^\top\right\|_{\mathrm{op}} \le C\frac{n}{d} \label{eq:higher-harmonic-sample-covariance}\tag{33}\] with probability at least \(1-n^{-D-5}\). This uses \(d\le c_Dn\), which follows from the upper bound on \(d\) in 2. On 33 , uniformly in \(v\), \[2d^2\lambda_1^2\sum_{i=1}^n\langle U_i,v\rangle^2 \le Cnd\lambda_1^2 \le Cnp;\] the last inequality follows from \(d\lambda_1^2\le Cp^2L\) and \(pL\le C\). Consequently, conditional on a realization of \(U\) satisfying 33 and \(q_U\le n^{-D-5}\) as obtained from 32 , all \(n\) decoupled columns have squared norm at most \(C_Dnp\) except on an event of conditional probability at most \(nq_U\le n^{-D-4}\).

Step 3: Chernoff concentration and decoupling.

We may now repeat the positive-semidefinite Chernoff calculation in 1. The conditional mean is controlled by 31 , and the squared column bound is \(C_Dnp\). Thus the full decoupled matrix has norm at most \[C_D\left(\sqrt{np\log n}+n\Lambda_{\ge2}\right) \label{eq:higher-harmonic-decoupled-bound}\tag{34}\] with the required conditional probability. The decoupling inequality in 5 transfers 34 to the symmetric matrix, up to the diagonal introduced when the full decoupled matrix is used. To control that diagonal, put \[t_n=\min\left\{1,C_D\sqrt{\frac{\log n}{d}}\right\}.\] A spherical-coordinate subgaussian tail bound [64] and a union bound give \(\max_i|\langle U_i,V_i\rangle|\le t_n\) with probability at least \(1-n^{-D-3}\). On this event, \[\max_i|h_\perp(U_i,V_i)| \le 1+d\lambda_1t_n \le C_D\bigl(1+p\sqrt{L\log n}\bigr) \le C_D\sqrt{np\log n}.\] Thus the diagonal is absorbed into the sparse term, completing the proof. ◻

Proof of 2. Step 1: Sample covariance and signal decomposition.

Put \(L=1+\log(1/p)\) and \[M=\frac{d}{n}X^\top X.\] The standard covariance bound for independent isotropic subgaussian vectors [64] gives, with probability at least \(1-n^{-D-2}\), \[\|M-I_d\|_{\mathrm{op}} \le \delta_n:=C_D\sqrt{\frac{d+\log n}{n}}. \label{eq:spherical-frob-covariance}\tag{35}\] The upper bound on \(d\) in 2 implies \(d\le c_Dn\), so the constants can be chosen such that \(\delta_n\le1/2\). On this event \(M\) is positive definite, so \(X\) has full column rank. We may therefore define \[Y=X(X^\top X)^{-1/2} =\sqrt{\frac{d}{n}}\,XM^{-1/2}.\]

Let \[E_{ij}=h_\perp(U_i,U_j)\mathbf{1}_{\{i\ne j\}}.\] The degree-one decomposition is the exact identity \[B+d\lambda_1I_n=d\lambda_1XX^\top+E. \label{eq:spherical-frob-decomposition}\tag{36}\] By 2 16 15, \[\|E\|_{\mathrm{op}} \le C_D\left(\sqrt{np\log n}+np\frac{L}{d}\right), \qquad \lambda_1\asymp p\sqrt{\frac{L}{d}}.\] The nonzero eigenvalues of \(d\lambda_1XX^\top\) are the eigenvalues of \(n\lambda_1M\) and hence are at least \(n\lambda_1/2\). Moreover, \[\rho_n:=\frac{\|E\|_{\mathrm{op}}}{n\lambda_1} \le C_D\left( \sqrt{\frac{d\log n}{npL}}+\sqrt{\frac{L}{d}} \right). \label{eq:spherical-frob-ratio}\tag{37}\]

Step 2: Eigenspace perturbation.

The lower and upper bounds on \(d\) make the two terms on the right smaller than a sufficiently small absolute constant. Adding \(d\lambda_1I_n\) shifts every eigenvalue by the same amount, so it does not change the top \(d\) eigenspace. We may therefore apply 6 to 36 . It yields an \(O\in O(d)\) such that \[\|\widehat YO-Y\|_{\mathrm F} \le C_D\sqrt d\,\rho_n. \label{eq:spherical-eigenspace-bound}\tag{38}\] After multiplying by \(\sqrt{n/d}\) and dividing by \(\sqrt n\), \[\frac{1}{\sqrt n} \left\|\widehat UO-XM^{-1/2}\right\|_{\mathrm F} \le C_D\rho_n.\] Since \(\|X\|_{\mathrm F}=\sqrt n\) and 35 implies \(\|M^{-1/2}-I_d\|_{\mathrm{op}}\le C\delta_n\), \[\frac{1}{\sqrt n} \|XM^{-1/2}-X\|_{\mathrm F} \le C\delta_n.\] Under the assumptions of 2, this covariance error is already contained in the sparse perturbation term. Indeed, \(pL\le C\) and \(d\ge C_DL\) give \[\frac{d+\log n}{n} \le C_D\frac{d\log n}{npL}.\] The triangle inequality and 37 therefore prove the vector bound 4 .

Step 3: Gram matrix recovery.

On the covariance event 35 , \[\|\widehat U\|_{\mathrm{op}}=\sqrt{\frac{n}{d}}, \qquad \|X\|_{\mathrm{op}}\le C\sqrt{\frac{n}{d}}.\] Applying 7 with the alignment in 38 gives \[\frac{\sqrt d}{n}\|\widehat K-XX^\top\|_{\mathrm F} \le \frac{C}{\sqrt n}\|\widehat UO-X\|_{\mathrm F}.\] The vector bound 4 , together with a union bound over the covariance event 35 and the event in 2 proves 5 and completes the proof. ◻

Proof. Let \[f(s)=\overline{\Phi}(u/s),\qquad s_i=\frac{\|G_i\|}{\sqrt d}.\]

Conditioning on \(G\) in the definition of the threshold gives \(p=\mathbb{E}f(\|G\|/\sqrt d)\). Hence \[a(G_i)=f(s_i)-p = \bigl(f(s_i)-f(1)\bigr)-\eta, \qquad \eta:=\mathbb{E}\bigl[f(\|G\|/\sqrt d)-f(1)\bigr].\] Thus the size of \(a(G_i)\) is controlled by the radius fluctuation \(s_i-1\).

Let \[t_n=C_D\sqrt{\frac{\log n}{d}}, \qquad \mathcal{E}_{\rm rad}:=\{\max_i |s_i-1|\le t_n\}.\] By Gaussian norm concentration [64], \(\mathbb{P}(\mathcal{E}_{\rm rad})\ge1-n^{-D-2}\) after increasing \(C_D\). After increasing the constant in the lower bound on \(d\), the assumption \(d\ge C_D L^2\log n\) makes \(t_n\le c/L\). For every \(s\in[1-c/L,1+c/L]\), \[|f'(s)| = \frac{u}{s^2}\varphi(u/s) \le CpL\] by 17 and the Gaussian tail comparison [64]. In particular, \(f\) is \(CpL\)-Lipschitz on \([1-c/L,1+c/L]\).

We also use a quadratic, rather than a coordinatewise, radius bound. Since the Euclidean norm is one-Lipschitz and \(|\mathbb{E}\|G_i\|/\sqrt d-1|\le C/d\), Gaussian concentration [64] shows that \(\sqrt d(s_i-1)\) has uniformly bounded subgaussian norm. Consequently, \(d(s_i-1)^2\) has uniformly bounded subexponential norm [64]. Scalar Bernstein’s inequality [64] and \(n\ge C_D\log n\) therefore give \[\sum_{i=1}^n(s_i-1)^2\le C_D\frac{n}{d} \label{eq:raw-radius-quadratic-sum}\tag{42}\] with probability at least \(1-n^{-D-2}\). On the intersection of this event with \(\mathcal{E}_{\rm rad}\), \[\max_i |f(s_i)-f(1)| \le C_DpL\sqrt{\frac{\log n}{d}}, \qquad \left(\sum_i |f(s_i)-f(1)|^2\right)^{1/2} \le C_DpL\sqrt{\frac{n}{d}}. \label{eq:raw-first-projection-fluctuation}\tag{43}\]

The centering term satisfies \[|\eta| \le \mathbb{E}|f(\|G\|/\sqrt d)-f(1)| \le CpL\,\mathbb{E}\left|\frac{\|G\|}{\sqrt d}-1\right| + \mathbb{P}\left\{\left|\frac{\|G\|}{\sqrt d}-1\right|>\frac{c}{L}\right\} \le C\frac{pL}{\sqrt d}, \label{eq:raw-first-projection-centering}\tag{44}\] where the last step uses \(\mathbb{E}|\|G\|/\sqrt d-1|\le C/\sqrt d\) and the same Gaussian norm concentration; the tail term is absorbed under \(d\ge C_D L^2\log n\), after increasing \(C_D\). Combining 43 and 44 gives the stated \(\ell_2\) and \(\ell_\infty\) bounds on the intersection of the two events. A union bound completes the proof. ◻

Proof. For \(i\ne j\), \[A^{\rm G}_{ij}-p = r(G_i,G_j)+a(G_i)+a(G_j).\] This gives ?? . Multiplying on both sides by \(\Pi_n\) and using \(\Pi_n\mathbf{1}=0\) gives ?? . ◻

Proof. Step 1: Truncation and recentering.

We spell out the truncation because conditioning changes the canonical measure. Let \[\mathcal{T}=\left\{x: \left|\frac{\|x\|}{\sqrt d}-1\right|\le\frac{c}{L}\right\}, \qquad \varepsilon=\gamma_d(\mathcal{T}^c), \qquad \nu=\gamma_d(\,\cdot\mid\mathcal{T}).\] Gaussian norm concentration [64] and \(d\ge C_DL^2\log n\) give \(\varepsilon\le n^{-2D-20}\). For \(x\in\mathcal{T}\), define \[m(x)=\int k(x,y)\,d\nu(y), \qquad m_0=\int m(x)\,d\nu(x),\] and \[k_{\mathcal{T}}(x,y)=k(x,y)-m(x)-m(y)+m_0.\] Then \(k_{\mathcal{T}}\) is canonical under \(\nu\). Since \(k\) is canonical under \(\gamma_d\) and 17 bounds its squared section norm by \(Cp\) uniformly for \(x\in\mathcal{T}\), Cauchy–Schwarz gives \[\sup_{x\in\mathcal{T}}|m(x)|+|m_0|\le C\sqrt{p\varepsilon}.\] Moreover, if \(Q_\nu\) denotes projection orthogonal to constants in \(L^2(\nu)\), then \[T_{k_{\mathcal{T}},\nu} =Q_\nu T_{k,\nu}Q_\nu, \qquad \|T_{k_{\mathcal{T}},\nu}\|_{\mathrm{op}} \le\frac{\Lambda_k}{1-\varepsilon}.\] The last inequality follows by identifying \(L^2(\nu)\) with the subspace of \(L^2(\gamma_d)\) supported on \(\mathcal{T}\) and observing that restriction and renormalization multiply the operator norm by at most \((1-\varepsilon)^{-1}\).

Step 2: Conditional covariance and uniform column bound.

We now repeat the proof of 1 under \(\nu\), using the zero-diagonal decoupled matrix required by 5. The section bound in 17 gives \[\sup_{x\in\mathcal{T}} \int k_{\mathcal{T}}(x,y)^2\,d\nu(y)\le Cp.\] Consequently, 2 bounds the conditional covariance of the decoupled columns by \[C_D\bigl(n\Lambda_k^2+p\log n\bigr).\] If \(D_j=I-e_je_j^\top\) and \(\Sigma\) is the covariance of a full column, the zero-diagonal columns have covariances \(D_j\Sigma D_j\) and \[\sum_{j=1}^nD_j\Sigma D_j =(n-2)\Sigma+\operatorname{diag}(\Sigma) \preceq (n-1)\|\Sigma\|_{\mathrm{op}}I_n.\] Thus deleting the diagonal does not enlarge the Chernoff mean scale. For the column bound, fix a typical second endpoint \(y\). Under \(\nu\), the number of threshold indicators in that column is binomial with success probability at most \((1-\varepsilon)^{-1}\overline{\Phi}(u\sqrt d/\|y\|)\le Cp\). The binomial Chernoff and Markov argument of 4 therefore bounds all sampled threshold columns by \(C_Dnp\) with the required conditional probability. The first Hoeffding projections are \(O(p)\) on \(\mathcal{T}\) and contribute at most \(Cnp^2\). If \(k=r_\perp\), the additional linear column satisfies \[\sum_{i=1}^n\beta^2\langle G_i,y\rangle^2 \le C\beta^2 n\|y\|^2 \le Cnp^2L \le Cnp\] on the standard Gaussian sample-covariance event [64]; conditioning all sample points to lie in \(\mathcal{T}\) changes its failure probability by at most \((1-\varepsilon)^{-n}\). Here we used \(d\le cn\) and \(\beta^2\le Cp^2L/d\). Thus the squared column bound is \(C_Dnp\).

Step 3: Decoupling and removal of the truncation.

Applying 1 conditionally therefore gives \[\|G^0_{\mathcal{T}}\|_{\mathrm{op}} \le C_D\left(\sqrt{np\log n}+n\Lambda_k\right). \label{eq:raw-truncated-decoupled-bound}\tag{45}\] The decoupling inequality in 5 transfers 45 to the zero-diagonal matrix generated by \(k_{\mathcal{T}}\). On the event that all original sample points lie in \(\mathcal{T}\), the matrices generated by \(k\) and \(k_{\mathcal{T}}\) differ by the off-diagonal part of \(m\mathbf{1}^\top+\mathbf{1}m^\top-m_0J\). Its operator norm is at most \(Cn\sqrt{p\varepsilon}\), including the diagonal correction, and is smaller than \(n^{-D-2}\). Finally, \(\mathbb{P}\{\exists i:G_i\notin\mathcal{T}\}\le n\varepsilon\). Combining the events and relabeling \(D\) proves the proposition. ◻

Proof of 3. The condition \(np\ge C_D\log n\) implies \(L\le C\log n\), so \(d\ge C_DL^2\log n\) in particular implies the \(d\ge CL^3\) hypothesis of 17. Apply 4 to \(r\) with tail exponent \(D+2\) and use 17. This gives \[\|R\|_{\mathrm{op}} \le C_D\left( \sqrt{np\log n} +np\sqrt{\frac{L}{d}} +np\frac{L^2}{d} \right) \label{eq:raw-R-bound}\tag{46}\] with probability at least \(1-n^{-D-2}\). On the event from 8, also taken with tail exponent \(D+2\), the Hoeffding reduction 3 gives \[\|\Pi_n(A^{\rm G}-\mathbb{E}A^{\rm G})\Pi_n\|_{\mathrm{op}} \le \|R\|_{\mathrm{op}}+2\|a_G\|_\infty.\] The \(\|a_G\|_\infty\) term is absorbed by \(\sqrt{np\log n}\) because \(pL\) is bounded for \(0<p\le p_0\) and \(np\ge C_D\log n\). This proves 7 , since \(d\ge C_DL^2\log n\) and \(L\le C\log n\) imply \[\frac{L^2}{d}\le C\sqrt{\frac{L}{d}}.\]

For the full-matrix estimate, ?? gives \[\|a_G\mathbf{1}^\top+\mathbf{1}a_G^\top-2\operatorname{diag}(a_G)\|_{\mathrm{op}} \le 2\sqrt n\,\|a_G\|_2+2\|a_G\|_\infty,\] together with the bound 46 on \(\|R\|_{\mathrm{op}}\). By 8, \[2\sqrt n\,\|a_G\|_2 \le C_D\frac{npL}{\sqrt d},\] and the \(\|a_G\|_\infty\) term is again absorbed by the sparse term. The two geometric terms in \(\|R\|_{\mathrm{op}}\) are at most \(CnpL/\sqrt d\) because \(L\ge1\) and \(d\ge L^2\). A union bound over the events in 4 8 proves 7 8 with probability at least \(1-n^{-D}\). ◻

Proof. Let \(R_\perp\) be the zero-diagonal empirical matrix generated by \(r_\perp\), and write \[D_Z=\operatorname{diag}(\|Z_1\|_2^2,\ldots,\|Z_n\|_2^2), \qquad D_a=\operatorname{diag}(a_G).\] The Hoeffding decomposition and the removal of the degree-one Gaussian chaos give the exact identity \[E_{\rm G} = \Pi_nR_\perp\Pi_n -d\beta\Pi_n(D_Z-I_n)\Pi_n -2\Pi_nD_a\Pi_n. \label{eq:gaussian-frob-residual-decomposition}\tag{48}\] Indeed, the off-diagonal matrix generated by \(\beta\langle G_i,G_j\rangle\) is \(d\beta(ZZ^\top-D_Z)\), while \(\Pi_nZZ^\top\Pi_n=Z_cZ_c^\top\).

By 4 17, \[\|R_\perp\|_{\mathrm{op}} \le C_D\left(\sqrt{np\log n}+np\frac{L^2}{d}\right). \label{eq:gaussian-recovery-rperp-bound}\tag{49}\] Gaussian norm concentration [64] and a union bound give \[\max_i\bigl|\|Z_i\|_2^2-1\bigr| \le C_D\sqrt{\frac{\log n}{d}}, \label{eq:gaussian-recovery-norm-bound}\tag{50}\] where the smaller term \(\log n/d\) is absorbed because \(d\ge C_DL^2\log n\). Since \(d\beta\asymp p\sqrt{dL}\), \[d\beta\|D_Z-I_n\|_{\mathrm{op}} \le C_Dp\sqrt{L\log n}. \label{eq:gaussian-recovery-DZ-bound}\tag{51}\] Likewise, 8 gives \[\|D_a\|_{\mathrm{op}} \le C_DpL\sqrt{\frac{\log n}{d}}+n^{-D-2}. \label{eq:gaussian-recovery-Da-bound}\tag{52}\] Both diagonal terms are absorbed by \(\sqrt{np\log n}\) under \(np\ge C_D\log n\) and \(pL\le C\). Inserting 49 , 51 , and 52 into 48 proves the lemma. ◻

Proof of 4. Step 1: Sample covariance and signal eigengap.

Put \(L=1+\log(1/p)\) and \[M=\frac{d}{n} Z_c^\top Z_c.\] By orthogonal invariance, \(G^\top\Pi_nG\) has the same law as the Gram matrix of \(n-1\) independent \(N(0,I_d)\) vectors. The Wishart concentration bound [64] therefore gives, with probability at least \(1-n^{-D-2}\), \[\|M-I_d\|_{\mathrm{op}} \le \delta_n:=C_D\sqrt{\frac{d+\log n}{n}}. \label{eq:gaussian-frob-covariance}\tag{53}\] The upper bound on \(d\) in 4 implies \(d\le c_Dn\), and hence the constants may be chosen such that \(\delta_n\le1/2\). On this event \(M\) is positive definite, so \(Z_c\) has full column rank. We may therefore define \[Y^{\rm G} :=Z_c(Z_c^\top Z_c)^{-1/2} =\sqrt{\frac{d}{n}}\,Z_cM^{-1/2}. \label{eq:gaussian-population-orthonormalization}\tag{54}\]

The nonzero eigenvalues of the signal matrix \(d\beta Z_cZ_c^\top\) are the eigenvalues of \(n\beta M\) and therefore are at least \(n\beta/2\). By 9 17, \[\begin{align} \rho_{\rm G} &:= \frac{\|E_{\rm G}\|_{\mathrm{op}}}{n\beta}\\ &\le C_D\left( \sqrt{\frac{d\log n}{npL}} +\frac{L^{3/2}}{\sqrt d} \right). \end{align} \label{eq:gaussian-frob-ratio}\tag{55}\] The lower and upper dimension bounds, with the constants chosen sufficiently large and small respectively, give \(\rho_{\rm G}\le1/8\).

Step 2: Eigenspace and vector recovery.

The matrix \[\Pi_n(A^{\rm G}-\mathbb{E}A^{\rm G})\Pi_n+d\beta\Pi_n = d\beta Z_cZ_c^\top+E_{\rm G}\] preserves \(\mathbf{1}^\perp\). On that subspace, adding \(d\beta\Pi_n\) shifts every eigenvalue by the same amount. The signal matrix has its \(d\) nonzero eigenvalues in \([n\beta/2,3n\beta/2]\). Since \(\|E_{\rm G}\|_{\mathrm{op}}\le n\beta/8\), Weyl’s inequality places the smallest perturbed signal eigenvalue above \(3n\beta/8\) and every remaining eigenvalue of the shifted matrix below \(n\beta/8\). After the shift is removed, the signal eigenvalues are therefore at least \((3n/8-d)\beta\). The upper bound on \(d\) in 4 allows the constant \(c_D\) to be chosen so that \(d\le n/8\); hence these eigenvalues remain positive. Removing the shift preserves the ordering within \(\mathbf{1}^\perp\), whereas the eigenvalue on \(\operatorname{span}\{\mathbf{1}\}\) remains zero. Thus the top \(d\) eigenspace in 4 is precisely the signal cluster to which 6 applies. We obtain an \(O\in O(d)\) such that \[\|\widehat Y^{\rm G}O-Y^{\rm G}\|_{\mathrm F} \le C_D\sqrt d\,\rho_{\rm G}.\] Multiplying by \(\sqrt{n/d}\) and dividing by \(\sqrt n\) gives \[\frac{1}{\sqrt n} \left\|\widehat ZO-Z_cM^{-1/2}\right\|_{\mathrm F} \le C_D\rho_{\rm G}. \label{eq:gaussian-aligned-signal-bound}\tag{56}\] On the covariance event 53 , \(\|Z_c\|_{\mathrm F}\le C\sqrt n\) and \(\|M^{-1/2}-I_d\|_{\mathrm{op}}\le C\delta_n\). Consequently, \[\frac{1}{\sqrt n}\|Z_cM^{-1/2}-Z_c\|_{\mathrm F} \le C\delta_n. \label{eq:gaussian-covariance-centering-error}\tag{57}\] Finally, if \(\bar Z=n^{-1}\sum_iZ_i\), then \(Z-Z_c=\mathbf{1}\bar Z^\top\). Since \(\bar Z\sim N(0,(nd)^{-1}I_d)\), Gaussian norm concentration [64] gives \[\|\bar Z\|_2\le C_D/\sqrt n\le C_D\delta_n. \label{eq:gaussian-sample-mean-error}\tag{58}\] Combining 56 , 57 , and 58 with 55 proves 9 , because \(pL\le C\) and \(d\ge C_DL\) imply \[\delta_n^2= C_D^2\frac{d+\log n}{n} \le C_D\frac{d\log n}{npL}.\]

Step 3: Gram matrix recovery.

Standard Gaussian singular-value bounds [64] and \(d\le c_Dn\) give \[\|\widehat Z\|_{\mathrm{op}}=\sqrt{\frac{n}{d}}, \qquad \|Z\|_{\mathrm{op}}\le C\sqrt{\frac{n}{d}}.\] Thus 7, with the alignment in 56 , yields \[\frac{\sqrt d}{n}\|\widehat K^{\rm G}-ZZ^\top\|_{\mathrm F} \le \frac{C}{\sqrt n}\|\widehat ZO-Z\|_{\mathrm F}.\] The vector bound 9 , together with a union bound over the events in 53 , 9, and 58 proves 10 and completes the proof. ◻

Proof. For either model, let \(q_i\) be the edge probability conditional on the latent vector at vertex \(i\). Conditional on that vector, \(d_i\sim\operatorname{Bin}(n-1,q_i)\). Hence the scalar Bernstein bound [64] and \(np\ge C_D\log n\) imply \[\mathbb{P}\left\{ |d_i-(n-1)q_i|>K_D\sqrt{np\log n},\;q_i\le2p \right\} \le2n^{-D-2}. \label{eq:degree-common-binomial-bound}\tag{60}\] The estimate 60 is applied separately to each vertex and then union-bounded; no independence among the degrees is needed.

Spherical graph.

Rotational invariance gives, for every \(i\ne j\), \[\mathbb{P}\{\langle U_i,U_j\rangle\ge\tau\mid U_i\}=p.\] Thus \(q_i=p\), and 60 followed by a union bound proves part (i).

Gaussian vector graph.

Put \(L=1+\log(1/p)\) and define \[q_i :=\mathbb{P}\{\langle G_i,G\rangle/\sqrt d\ge u\mid G_i\} =\overline{\Phi}\!\left(\frac{u\sqrt d}{\|G_i\|}\right),\] where \(G\sim N(0,I_d)\) is independent of \(G_i\) and \(\overline{\Phi}(x)=\mathbb{P}\{N(0,1)\ge x\}\). Thus \(q_i-p=a(G_i)\) in the notation of 8. Apply 8 with tail exponent \(D+3\). With probability at least \(1-n^{-D-3}\), \[\max_i|q_i-p| \le K_DpL\sqrt{\frac{\log n}{d}}+n^{-D-5}. \label{eq:gaussian-degree-probability-shift}\tag{61}\] Choose the constant in the dimension assumption so that \(C_D\ge4K_D^2\). Then \(K_DL\sqrt{\log n/d}\le1/2\), so the first term is at most \(p/2\). The second is also at most \(p/2\) because \(p\ge C_D(\log n)/n\). Hence \(q_i\le2p\) for every \(i\) on this event.

Using 60 , a union bound, and 61 , we obtain \[\begin{align} \max_i|d_i(A^{\rm G})-(n-1)p| &\le \max_i|d_i(A^{\rm G})-(n-1)q_i|+(n-1)\max_i|q_i-p|\\ &\le C_D\left( \sqrt{np\log n} +npL\sqrt{\frac{\log n}{d}} \right). \end{align}\] This proves part (ii). ◻

Proof of 5. Choose a universal constant \(\delta_0\in(0,1/5)\) so small that \[\frac{32\delta_0(1+7\delta_0)}{(1-\delta_0)^2} \log\!\left(\frac{1+2\delta_0}{2\delta_0}\right)<1. \label{eq:fixed-synchronization-delta}\tag{62}\] Such a choice is possible because \(\delta\log(1/\delta)\to0\) as \(\delta\downarrow0\). We prove that the two operator-norm deviations in 10 are at most \(\delta_0np\).

Both models satisfy \(\mathbb{E}M=p(J-I_n)\). If \(\mathcal{D}_M=\operatorname{diag}(M\mathbf{1})\) and \(\mathcal{L}_M=\mathcal{D}_M-M\), then \[\begin{align} M-pJ&=(M-\mathbb{E}M)-pI_n,\\ \mathcal{L}_M+pJ-npI_n &=\mathcal{D}_M-(n-1)pI_n-(M-\mathbb{E}M). \end{align} \label{eq:common-sync-identities}\tag{63}\] We write \(\mathcal{L}_A\) and \(\mathcal{L}_{\rm G}\) for the two resulting Laplacians.

Spherical graph.

Apply 1 11 with tail exponent \(D+3\). Substituting \(M=A\) in 63 gives, simultaneously, \[\begin{align} \|A-pJ\|_{\mathrm{op}} &\le K_D\bigl(\sqrt{np\log n}+np\tau\bigr),\\ \|\mathcal{L}_A+pJ-npI_n\|_{\mathrm{op}} &\le K_D\bigl(\sqrt{np\log n}+np\tau\bigr). \end{align} \label{eq:spherical-sync-two-deviations}\tag{64}\] Here the harmless term \(pI_n\) is absorbed by \(\sqrt{np\log n}\).

Put again \(L=1+\log(1/p)\). By 16, the condition \(d\ge C_DL\) gives \(\tau\le C\sqrt{L/d}\). Dividing 64 by \(np\) therefore gives \[\max\left\{ \frac{\|A-pJ\|_{\mathrm{op}}}{np}, \frac{\|\mathcal{L}_A+pJ-npI_n\|_{\mathrm{op}}}{np} \right\} \le K_D\left( \sqrt{\frac{\log n}{np}}+\sqrt{\frac{L}{d}} \right). \label{eq:spherical-sync-normalized}\tag{65}\] By increasing the constants in the assumptions \(np\ge C_D\log n\) and \(d\ge C_DL\), the right-hand side of 65 is at most \(\delta_0\). The conclusion follows from 10 and 62 .

Gaussian vector graph.

Apply the full-matrix estimate 8 and 11, again with tail exponent \(D+3\). Using 63 with \(M=A^{\rm G}\) and \(L\ge1\), we obtain \[\begin{align} &\max\left\{ \frac{\|A^{\rm G}-pJ\|_{\mathrm{op}}}{np}, \frac{\|\mathcal{L}_{\rm G}+pJ-npI_n\|_{\mathrm{op}}}{np} \right\}\\ &\qquad\le K_D\left( \sqrt{\frac{\log n}{np}} +L\sqrt{\frac{\log n}{d}} \right). \end{align} \label{eq:gaussian-sync-normalized}\tag{66}\] The assumptions \(np\ge C_D\log n\) and \(d\ge C_DL^2\log n\), with constants chosen sufficiently large, make the right-hand side of 66 at most \(\delta_0\). Another application of 10 completes the Gaussian proof. A union bound over the events in 1 3 11 gives probability at least \(1-n^{-D}\) in both models. ◻

Proof. Step 1: Empirical Hoeffding decomposition.

We use the kernels \(h_\mu,a_\mu,r_\mu^{\rm lab}\) defined at the beginning of this section. By construction, \[\mathbb{E}_{Y'} r_\mu^{\rm lab}(Y,Y') = \mathbb{E}_Y r_\mu^{\rm lab}(Y,Y')=0,\] so \(r_\mu^{\rm lab}\) is canonical, and its integral-operator norm is \(\Lambda_\mu^{\rm lab}\).

We first relate this population decomposition to the zero-diagonal empirical matrix. Let \[R_{\mu,ij}^{\rm lab} = r_\mu^{\rm lab}(Y_i,Y_j)\mathbf{1}_{\{i\ne j\}}, \qquad a_i=a_\mu(Y_i).\] For \(i\ne j\), \[h_\mu(Y_i,Y_j) = r_\mu^{\rm lab}(Y_i,Y_j)+a_i+a_j.\] Thus the off-diagonal empirical matrix generated by \(h_\mu\) is \[R_\mu^{\rm lab} +a\mathbf{1}^\top+\mathbf{1}a^\top-2\operatorname{diag}(a).\] Since \(\Pi_n\mathbf{1}=0\), the definition of \(E_\mu^{\rm lab}\) gives the exact identity \[E_\mu^{\rm lab} = \Pi_n R_\mu^{\rm lab}\Pi_n -\Delta_\mu\Pi_n -2\Pi_n\operatorname{diag}(a)\Pi_n. \label{eq:gmbm-empirical-residual-decomposition}\tag{70}\] Both correction terms have operator norm \(O(1)\) and send \(\xi_c\) to a vector with \(\ell_\infty\) norm \(O(1)\), because \(|a_i|\le C\), \(|\Delta_\mu|\le1\), and \(\|\xi_c\|_\infty\le2\). Since \(np\ge C_D\log n\), these deterministic terms are absorbed into \(C_D\sqrt{np\log n}\) after increasing \(C_D\).

Step 2: Operator-norm concentration.

We next bound \(\|R_\mu^{\rm lab}\|_{\mathrm{op}}\).

Typical sections. Let \(m_\mu=\mu^2\sqrt d\), and let \(\mathcal{G}\) be the set of points \(Y=(\xi,G)\) satisfying \[\left|\frac{\|G\|}{\sqrt d}-1\right| \le C_D\sqrt{\frac{\log n}{d}}\le \frac{c}{L}, \qquad |G_1|\le C_D\sqrt{\log n}.\] Chi-square and Gaussian tails [64], together with the deterministic implications of 6, give \(\mathbb{P}\{Y\notin\mathcal{G}\}\le n^{-2D-12}\). Hence all points in the original sample, and all points on both sides of a decoupled sample, belong to \(\mathcal{G}\) with probability at least \(1-n^{-2D-10}\). Denote this event by \(\mathcal{E}_{\rm sec}\).

The assumptions of 6 also imply \(m_\mu\le c/\sqrt L\) and \(\mu|G_1|\le c/\sqrt L\) on \(\mathcal{G}\). For any \(y=(\xi,g)\in\mathcal{G}\), conditioning on \(Y=y\) makes the edge statistic a mixture of two Gaussians. Their common variance is \[\left\|\frac{g}{\sqrt d}+\mu\xi e_1\right\|_2^2 =1+O(L^{-1}),\] and their shifts have absolute value \(|\mu g_1+m_\mu\xi|=O(L^{-1/2})\). Since \(\tau\asymp\sqrt L\), Mills’ ratio [67] gives the uniform bound \[\mathbb{P}\{\sqrt d\,\langle Z(y),Z(Y')\rangle\ge\tau\}\le Cp.\] The elementary inequality \((\mathbf{1}_E-p)^2\le2\mathbf{1}_E+2p^2\), the bound \(|\Delta_\mu|\le Cp\), and conditional Jensen therefore imply \[\int r_\mu^{\rm lab}(y,y')^2\,d\mathbb{P}_Y(y')\le Cp \qquad\text{for every }y\in\mathcal{G}. \label{eq:gmbm-typical-section-bound}\tag{71}\]

Recentering after truncation. We also check explicitly that truncation does not destroy canonicality. Let \(\varepsilon=\mathbb{P}\{Y\notin\mathcal{G}\}\) and \(\nu=\mathbb{P}_Y(\,\cdot\mid\mathcal{G})\). For \(y\in\mathcal{G}\), set \[\begin{align} m_{\mathcal{G}}(y) &=\int r_\mu^{\rm lab}(y,y')\,d\nu(y'),\\ m_{\mathcal{G},0} &=\int m_{\mathcal{G}}(y)\,d\nu(y),\\ r_{\mu,\mathcal{G}}^{\rm lab}(y,y') &=r_\mu^{\rm lab}(y,y')-m_{\mathcal{G}}(y) -m_{\mathcal{G}}(y')+m_{\mathcal{G},0}. \end{align}\] The last kernel is canonical under \(\nu\). Since \(r_\mu^{\rm lab}\) is canonical under the original law and its sections on \(\mathcal{G}\) have squared \(L^2\) norm at most \(Cp\), Cauchy–Schwarz gives \[\sup_{y\in\mathcal{G}}|m_{\mathcal{G}}(y)| +|m_{\mathcal{G},0}| \le C\sqrt{p\varepsilon}. \label{eq:gmbm-truncation-centering-size}\tag{72}\] If \(Q_\nu\) is projection orthogonal to constants in \(L^2(\nu)\), then \[T_{r_{\mu,\mathcal{G}}^{\rm lab},\nu} =Q_\nu T_{r_\mu^{\rm lab},\nu}Q_\nu, \qquad \|T_{r_{\mu,\mathcal{G}}^{\rm lab},\nu}\|_{\mathrm{op}} \le\frac{\Lambda_\mu^{\rm lab}}{1-\varepsilon}.\] Indeed, extension by zero identifies \(L^2(\nu)\) with functions supported on \(\mathcal{G}\) in the original \(L^2\) space, and the change of normalization costs the factor \((1-\varepsilon)^{-1}\). The conditional covariance calculation in 3, applied to the recentered canonical kernel, is therefore bounded by \[C_D\bigl(n(\Lambda_\mu^{\rm lab})^2+p\log n\bigr). \label{eq:gmbm-truncated-covariance-bound}\tag{73}\]

Conditional matrix concentration. The recentered kernel is uniformly bounded, and its squared section norm is \(O(p)\). For each fixed second endpoint, scalar Bernstein therefore bounds the squared column norm by \(C_Dnp\). The conditional-probability and Markov argument of 4 makes the squared-column bound \(C_Dnp\) simultaneous for all sampled decoupled columns. The covariance estimate 73 , the matrix Chernoff inequality in 1, and the decoupling inequality in 5 now give \[\|R_{\mu,\mathcal{G}}^{\rm lab}\|_{\mathrm{op}} \le C_D\left(\sqrt{np\log n}+n\Lambda_\mu^{\rm lab}\right) \label{eq:gmbm-truncated-operator-bound}\tag{74}\] with probability at least \(1-n^{-D-1}\), where \(R_{\mu,\mathcal{G}}^{\rm lab}\) is the zero-diagonal empirical matrix of the recentered kernel. On \(\mathcal{E}_{\rm sec}\), the recentering correction satisfies \[\|R_\mu^{\rm lab}-R_{\mu,\mathcal{G}}^{\rm lab}\|_{\mathrm{op}} \le Cn\sqrt{p\varepsilon}=o(n^{-D-2}). \label{eq:gmbm-recentering-correction}\tag{75}\] Combining 74 with 75 gives the same bound for \(R_\mu^{\rm lab}\). By 18, this is at most \(C_D(\sqrt{np\log n}+np\mu\sqrt L+np\sqrt{L/d})\). Together with 70 , this proves 68 .

Step 3: Signed row sums.

The operator estimate 68 controls the spectrum, but the SDP dual certificate also requires coordinatewise control in the label direction. Since \(\xi_c=\xi-\bar\xi\mathbf{1}\), \[R_\mu^{\rm lab}\xi_c = R_\mu^{\rm lab}\xi-\bar\xi\,R_\mu^{\rm lab}\mathbf{1}.\] We control the two terms on the right separately. First fix \(i\) and condition on \(Y_i\). The variables \[X_{ij}=r_\mu^{\rm lab}(Y_i,Y_j)\xi_j,\qquad j\ne i,\] are independent, bounded by an absolute constant, and have conditional variance at most \(Cp\). The variance bound follows from the section estimate 71 : \[\sum_{j\ne i}\operatorname{Var}(X_{ij}\mid Y_i) \le \sum_{j\ne i}\mathbb{E}[X_{ij}^2\mid Y_i] \le Cnp. \label{eq:gmbm-signed-row-variance}\tag{76}\] Their conditional mean is \(T_{r_\mu^{\rm lab}}\xi(Y_i)\). The pointwise estimate 120 gives on \(\mathcal{E}_{\rm sec}\) \[\left| T_{r_\mu^{\rm lab}}\xi(Y_i) \right| \le C_Dp\mu\sqrt{L\log n}.\] Therefore \[\left| \sum_{j\ne i}\mathbb{E}[X_{ij}\mid Y_i] \right| \le C_Dnp\mu\sqrt{L\log n}.\] Scalar Bernstein’s inequality, conditional on \(Y_i\), gives \[\mathbb{P}\left\{ \left| \sum_{j\ne i}\bigl(X_{ij}-\mathbb{E}[X_{ij}\mid Y_i]\bigr) \right| > C_D\sqrt{np\log n} \,\middle|\,Y_i \right\} \le n^{-D-3},\] where the linear Bernstein term is absorbed because \(np\ge C_D\log n\). A union bound over \(i\) gives \[\max_i |(R_\mu^{\rm lab}\xi)_i| \le C_D\left(\sqrt{np\log n} +np\mu\sqrt{L\log n}\right) \label{eq:gmbm-row-xi-bound}\tag{77}\] with probability at least \(1-n^{-D-2}\). The same argument with \(X_{ij}=r_\mu^{\rm lab}(Y_i,Y_j)\) gives \[\max_i |(R_\mu^{\rm lab}\mathbf{1})_i| \le C_D\sqrt{np\log n}, \label{eq:gmbm-row-one-bound}\tag{78}\] with probability at least \(1-n^{-D-2}\), because \(r_\mu^{\rm lab}\) is canonical and hence \(T_{r_\mu^{\rm lab}}1=0\). Hoeffding’s inequality [68] for the Rademacher labels gives \(|\bar\xi|\le C_D\sqrt{\log n/n}\) with probability at least \(1-n^{-D-2}\). Since this factor is at most one, 77 and 78 imply \[\max_i \left| \sum_{j\ne i} r_\mu^{\rm lab}(Y_i,Y_j)(\xi_j-\bar\xi) \right| \le C_D\left(\sqrt{np\log n} +np\mu\sqrt{L\log n}\right). \label{eq:gmbm-row-centered-label-bound}\tag{79}\] The estimate 79 is the required row bound for \(R_\mu^{\rm lab}\xi_c\). The left multiplication by \(\Pi_n\) can only subtract the average of this vector, so it increases the \(\ell_\infty\) norm by at most a factor two. Adding the already controlled deterministic diagonal and \(-\Delta_\mu\Pi_n\) terms in 70 proves 69 . ◻

Proof of 6. Step 1: Conjugation by the true labels.

Let \(D_\xi=\operatorname{diag}(\xi_1,\ldots,\xi_n)\). For each feasible matrix \(X\) in 13 , set \(Y=D_\xi XD_\xi\). Since \(D_\xi^\top=D_\xi=D_\xi^{-1}\), the map \(X\mapsto Y\) is a bijection of the elliptope: \(X\succeq0\) and \(X_{ii}=1\) for every \(i\) if and only if \(Y\succeq0\) and \(Y_{ii}=1\) for every \(i\). Moreover, with \[C_\mu:=D_\xi B_\mu D_\xi,\] cyclicity of the trace gives \[\langle B_\mu,X\rangle =\langle D_\xi B_\mu D_\xi,Y\rangle =\langle C_\mu,Y\rangle.\] Thus the conjugated SDP is \[\max\left\{ \langle C_\mu,Y\rangle: Y\succeq0,\;Y_{ii}=1\;\text{for every }i \right\}. \label{eq:gmbm-conjugated-sdp}\tag{80}\] Finally, \(D_\xi(\xi\xi^\top)D_\xi=J\). Hence \(\xi\xi^\top\) is the unique optimizer of 13 if and only if \(J\) is the unique optimizer of 80 . We prove the latter assertion using 13. By 67 , \[B_\mu = \Delta_\mu\xi_c\xi_c^\top+E_\mu^{\rm lab}, \qquad \xi_c=\xi-\bar\xi\mathbf{1}, \qquad \bar\xi=\frac{1}{n}\sum_{i=1}^n\xi_i.\] Since \[D_\xi\xi_c = \mathbf{1}-\bar\xi\xi,\] we may write \[C_\mu = \Delta_\mu qq^\top+R_\mu, \qquad q=\mathbf{1}-\bar\xi\xi, \qquad R_\mu=D_\xi E_\mu^{\rm lab}D_\xi. \label{eq:gmbm-sdp-conjugated}\tag{81}\] Define the perturbation matrix \[H_\mu :=C_\mu-\Delta_\mu J =\Delta_\mu(qq^\top-J)+R_\mu.\] Thus \(C_\mu=\Delta_\mu J+H_\mu\), in the form required by 13. The reference matrix \(C_0=\Delta_\mu J\) has signed Laplacian \[S_{C_0}=n\Delta_\mu I_n-\Delta_\mu J.\] It vanishes on \(\mathbf{1}\) and equals \(n\Delta_\mu I_n\) on \(\mathbf{1}^\perp\).

Step 2: Perturbation of the population certificate.

We first control the label imbalance. Hoeffding’s inequality [68] gives \[|\bar\xi| \le C_D\sqrt{\frac{\log n}{n}} \label{eq:gmbm-sdp-label-balance}\tag{82}\] with probability at least \(1-n^{-D-2}\). The population part of \(H_\mu\) is \[\Delta_\mu(qq^\top-J) = -\Delta_\mu\bar\xi (\mathbf{1}\xi^\top+\xi\mathbf{1}^\top) +\Delta_\mu\bar\xi^2\xi\xi^\top.\] Also \(q^\top\mathbf{1}=n(1-\bar\xi^2)\). These two identities give directly \[\begin{align} &\|\Delta_\mu(qq^\top-J)\|_{\mathrm{op}} +\|\Delta_\mu(qq^\top-J)\mathbf{1}\|_\infty \le 4n\Delta_\mu\bigl(|\bar\xi|+\bar\xi^2\bigr). \end{align} \label{eq:gmbm-sdp-pop-size}\tag{83}\]

For the empirical part, conjugation preserves operator norm. Moreover, \(E_\mu^{\rm lab}\mathbf{1}=0\), and hence \[\|R_\mu\|_{\mathrm{op}}=\|E_\mu^{\rm lab}\|_{\mathrm{op}}, \qquad \|R_\mu\mathbf{1}\|_\infty=\|E_\mu^{\rm lab}\xi_c\|_\infty.\] The two estimates in 12 now give \[\begin{align} \|R_\mu\|_{\mathrm{op}}+\|R_\mu\mathbf{1}\|_\infty \le C_D\left( \sqrt{np\log n} +np\mu\sqrt{L\log n} +np\sqrt{\frac{L}{d}} \right) \label{eq:gmbm-sdp-random-size} \end{align}\tag{84}\] with probability at least \(1-n^{-D-1}\).

Step 3: Comparison with the label signal.

By 18, \(n\Delta_\mu\ge cnp\mu^2\sqrt{dL}\). Dividing the three terms in 84 by this signal scale gives \[\frac{\sqrt{\log n/(np)}}{\mu^2\sqrt{dL}}, \qquad \frac{\sqrt{\log n}}{\mu\sqrt d}, \qquad \frac{1}{\mu^2d}.\] The first is small by \(\mu^2\sqrt{dL}\ge C_D\sqrt{\log n/(np)}\), the second by \(\mu^2d\ge C_D\log n\), and the third by the same inequality. After increasing \(C_D\), we obtain \[\|R_\mu\|_{\mathrm{op}}+\|R_\mu\mathbf{1}\|_\infty \le \frac{1}{8} n\Delta_\mu. \label{eq:gmbm-sdp-random-small}\tag{85}\] Likewise, 82 and 83 imply, for all sufficiently large \(n\), \[\|\Delta_\mu(qq^\top-J)\|_{\mathrm{op}} +\|\Delta_\mu(qq^\top-J)\mathbf{1}\|_\infty \le\frac{1}{8} n\Delta_\mu. \label{eq:gmbm-sdp-pop-small}\tag{86}\] Combining 85 and 86 gives \[\|H_\mu\|_{\mathrm{op}}+\|H_\mu\mathbf{1}\|_\infty \le\frac{1}{4} n\Delta_\mu. \label{eq:gmbm-sdp-total-small}\tag{87}\]

Step 4: Apply the certificate.

By 87 , the decomposition \(C_\mu=\Delta_\mu J+H_\mu\) satisfies the strict perturbation condition in 13. Hence \(J\) is the unique optimizer of the conjugated SDP, and conjugating back gives \(\widehat X=\xi\xi^\top\). The label-balance and residual events hold simultaneously with probability at least \(1-n^{-D}\). ◻

Proof of 7. Let \[H_i=\xi_iG_{i1}, \qquad R_{ij}=\frac{\langle G_i,G_j\rangle}{\sqrt d}, \qquad m_\mu=\mu^2\sqrt d.\] The sign change in \(H_i\) absorbs the unknown label, so \(H_1,\ldots,H_n\) are again independent \(N(0,1)\) variables. The quantity \(m_\mu\) is the deterministic same-label shift, while \(R_{ij}\) contains the remaining Gaussian inner product. With this notation the label dependence is isolated in one sign \(\xi_i\xi_j\), and, for \(i\ne j\), \[\sqrt d\,\langle Z_i,Z_j\rangle =\xi_i\xi_j\bigl(m_\mu+\mu(H_i+H_j)\bigr)+R_{ij}. \label{eq:gmbm-large-separation-statistic}\tag{88}\] Since \(np\ge C\log n\), we have \(p\ge C\log n/n\) and hence \(L\le C\log n\) for all sufficiently large \(n\). The assumption \(\mu^2d\ge C\log n\) therefore gives \[\mu\sqrt d\ge C\sqrt{\log n}\ge C\sqrt L, \label{eq:gmbm-large-mu-d}\tag{89}\] after adjusting the absolute constant.

Step 1: Lower bound for the threshold.

Choose \(p_0<1/8\), and let \(u_p>0\) be determined by \[\mathbb{P}\{N(0,2)\ge u_p\}=4p.\] The classical Gaussian Mills bounds [67] state that, for \(x>0\), \[\frac{x}{1+x^2}\frac{e^{-x^2/2}}{\sqrt{2\pi}} \le \overline{\Phi}(x) \le \frac{1}{x}\frac{e^{-x^2/2}}{\sqrt{2\pi}}. \label{eq:gmbm-large-mills}\tag{90}\] After decreasing \(p_0\) if necessary, 90 implies \[c\sqrt L\le u_p\le C\sqrt L. \label{eq:gmbm-large-up}\tag{91}\]

We first record a tail bound for the residual inner product. For independent standard Gaussian vectors \(G_1,G_2\in\mathbb{R}^d\) and \(|\lambda|<\sqrt d\), \[\mathbb{E}\exp\left\{\lambda\frac{\langle G_1,G_2\rangle}{\sqrt d}\right\} =\left(1-\frac{\lambda^2}{d}\right)^{-d/2}.\] Indeed, conditioning on \(G_1\) gives \[\mathbb{E}\left[ \exp\left\{\frac{\lambda^2\|G_1\|_2^2}{2d}\right\} \right] =\left(1-\frac{\lambda^2}{d}\right)^{-d/2}.\] For \(|\lambda|\le\sqrt d/2\), the inequality \(-\log(1-\lambda^2/d)\le2\lambda^2/d\) bounds the moment generating function by \(e^{\lambda^2}\). Chernoff’s inequality [64], first with \(\lambda=t/4\) when \(t\le2\sqrt d\) and then with \(\lambda=\sqrt d/2\) when \(t>2\sqrt d\), yields \[\mathbb{P}\{|R_{12}|>t\} \le2\exp\{-c\min(t^2,t\sqrt d)\}, \qquad t\ge0. \label{eq:gmbm-product-tail}\tag{92}\]

Conditional on \(\xi_i\xi_j=1\), the statistic in 88 is \[m_\mu+\mu(H_i+H_j)+R_{ij}, \qquad H_i+H_j\sim N(0,2).\] Since the unconditional edge probability is \(p=(p_+(\mu)+p_-(\mu))/2\), we have \(p_+(\mu)\le2p\). Suppose, toward a contradiction, that \(\tau<m_\mu+\mu u_p/2\). Then \[\begin{align} p_+(\mu) &\ge \mathbb{P}\{H_i+H_j\ge u_p,\;R_{ij}\ge-\mu u_p/2 \mid \xi_i\xi_j=1\}\\ &\ge 4p-\mathbb{P}\{R_{ij}< -\mu u_p/2\}. \end{align} \label{eq:gmbm-pplus-contradiction}\tag{93}\] This is a union-bound estimate and does not require independence between \(H_i+H_j\) and \(R_{ij}\). By 91 , the lower bound on \(\mu\sqrt L\), and 89 , \[\min\{(\mu u_p)^2,\mu u_p\sqrt d\} \ge c\min\{\mu^2L,\mu\sqrt{dL}\} \ge C L.\] Thus 92 gives \(\mathbb{P}\{R_{ij}< -\mu u_p/2\}\le p\) after increasing \(C\). Substitution into 93 would imply \(p_+(\mu)\ge3p\), a contradiction. We conclude that \[\tau\ge m_\mu+\frac{1}{2}\mu u_p. \label{eq:gmbm-threshold-lower-large-mu}\tag{94}\]

Step 2: Extreme coordinates and residual inner products.

Hoeffding’s inequality [68] gives \[\mathbb{P}\left\{\frac{n}{3}\le |\{i:\xi_i=\sigma\}|\le\frac{2n}{3} \text{ for both }\sigma\in\{\pm1\}\right\}=1-o(1). \label{eq:gmbm-large-class-balance}\tag{95}\] On this event, choose \[i_\sigma\in\operatorname*{arg\,min}_{\{i:\xi_i=\sigma\}}H_i, \qquad M_\sigma=\max_{\{i:\xi_i=\sigma\}}H_i, \qquad \sigma\in\{\pm1\}.\] Conditional on the labels, the variables in either class are independent \(N(0,1)\). Set \(a_n=\sqrt{2\log n}\). The Mills bounds 90 imply, uniformly for \(n/3\le q\le2n/3\), \[\begin{align} q\,\overline{\Phi}\left(a_n+\frac{2\log\log n}{a_n}\right)&=o(1),\\ q\,\overline{\Phi}\left(a_n-\frac{2\log\log n}{a_n}\right)&\longrightarrow\infty. \end{align} \label{eq:gmbm-extreme-tail-relations}\tag{96}\] The first relation in 96 and a union bound control the maximum in each class. For the minimum, symmetry and \((1-x)^q\le e^{-qx}\) show that the probability that every observation exceeds \(-a_n+2\log\log n/a_n\) tends to zero. Hence, with probability \(1-o(1)\), simultaneously for \(\sigma\in\{\pm1\}\), \[M_\sigma\le a_n+\frac{2\log\log n}{a_n}, \qquad H_{i_\sigma}\le-a_n+\frac{2\log\log n}{a_n}.\] Since 91 bounds \(u_p\) below by a positive absolute constant, it follows that, for all sufficiently large \(n\), \[M_\sigma+H_{i_\sigma} \le\frac{4\log\log n}{a_n} \le\frac{1}{4}u_p, \qquad \sigma\in\{\pm1\}. \label{eq:gmbm-min-plus-max}\tag{97}\] A Gaussian tail bound [64] and a union bound also give, for an absolute constant \(K>0\), \[\max_{1\le i\le n}|H_i|\le K\sqrt{\log n} \label{eq:gmbm-all-h-small}\tag{98}\] with probability \(1-o(1)\).

It remains to control all residual inner products incident to the two selected vertices. Write \(G_i=(G_{i1},W_i)\) with \(W_i\in\mathbb{R}^{d-1}\), with the evident interpretation for \(d=1\). The indices \(i_+\) and \(i_-\) depend only on the labels and first coordinates, and hence are independent of \(W_1,\ldots,W_n\). Gaussian norm concentration [64] gives \[\max_{\sigma\in\{\pm1\}}\|W_{i_\sigma}\|_2 \le C(\sqrt d+\sqrt{\log n})\] with probability \(1-o(1)\). Conditional on a selected \(W_{i_\sigma}\), each \(\langle W_{i_\sigma},W_j\rangle/\sqrt d\) is centered Gaussian with variance \(\|W_{i_\sigma}\|_2^2/d\). The same conditioning applies to the inner product between the two selected vectors because their remaining coordinates are independent. A Gaussian tail bound [64] and a union bound over the two candidates and all \(j\) therefore give \[\max_{\sigma\in\{\pm1\}}\max_{j\ne i_\sigma} \frac{|\langle W_{i_\sigma},W_j\rangle|}{\sqrt d} \le K\left(\sqrt{\log n}+\frac{\log n}{\sqrt d}\right)\] with probability \(1-o(1)\). On the event 98 , the omitted first-coordinate product is at most \(K^2\log n/\sqrt d\). Increasing \(K\) and writing \[r_n:=\sqrt{\log n}+\frac{\log n}{\sqrt d},\] we obtain \[\max_{\sigma\in\{\pm1\}}\max_{j\ne i_\sigma}|R_{i_\sigma j}| \le Kr_n \label{eq:gmbm-candidate-r-small}\tag{99}\] with probability \(1-o(1)\).

We finally verify the scale comparisons needed in the next step. By 91 and the lower bound on \(\mu\sqrt L\), \[\mu u_p\ge8Kr_n \label{eq:gmbm-mu-u-large}\tag{100}\] after increasing \(C\). Moreover, \[m_\mu=\mu(\mu\sqrt d)\ge C\mu\sqrt{\log n}\] by 89 , while \[m_\mu =\frac{(\mu\sqrt d)(\mu\sqrt L)}{\sqrt L} \ge Cr_n.\] Increasing \(C\) once more gives \[m_\mu\ge4K\mu\sqrt{\log n}+4Kr_n. \label{eq:gmbm-m-large}\tag{101}\]

Step 3: Isolated vertices and posterior symmetry.

Fix \(\sigma\in\{\pm1\}\). We show that \(i_\sigma\) has no neighbors. If \(j\ne i_\sigma\) has label \(\sigma\), then 88 , 97 , and 99 give \[\sqrt d\,\langle Z_{i_\sigma},Z_j\rangle \le m_\mu+\frac{1}{4}\mu u_p+Kr_n <m_\mu+\frac{1}{2}\mu u_p \le\tau,\] where the strict inequality uses 100 , and the last inequality is 94 . If \(j\) has the opposite label, then 98 , 99 , and 101 imply \[\sqrt d\,\langle Z_{i_\sigma},Z_j\rangle \le -m_\mu+2K\mu\sqrt{\log n}+Kr_n <0<m_\mu+\frac{1}{2}\mu u_p\le\tau.\] Thus \(i_\sigma\) is isolated. Applying the argument to both labels and intersecting the events in 95 , 97 , 98 , and 99 proves \[\mathbb{P}\{A^\mu\text{ has an isolated vertex in each label class}\} \longrightarrow1.\]

It remains only to formalize the exchangeability argument. Fix an adjacency matrix \(a\) with \(\mathbb{P}\{A^\mu=a\}>0\), and let \(\mathcal{I}(a)\) be its isolated vertices. Every permutation \(\pi\) supported on \(\mathcal{I}(a)\) leaves \(a\) unchanged. Since the joint law of \((A^\mu,\xi)\) is vertex-exchangeable, \[\mathbb{P}\{\xi=x\mid A^\mu=a\} =\mathbb{P}\{\xi=\pi x\mid A^\mu=a\} \qquad\text{for every }x\in\{\pm1\}^n.\] Equivalently, conditional on \(A^\mu=a\), and after further conditioning on the labels outside \(\mathcal{I}(a)\) and the number of positive labels in \(\mathcal{I}(a)\), all assignments of those labels to the isolated vertices are equally likely.

Let \(\mathcal{E}\) be the event that both signs occur among the isolated vertices. On \(\mathcal{E}\), there are at least two such assignments. If at least one vertex is nonisolated, at most one of them can equal a fixed output up to a global sign, because the labels outside \(\mathcal{I}(a)\) are fixed. If every vertex is isolated, at most two assignments can equal that output up to sign, whereas there are at least \(n\ge4\) assignments for all sufficiently large \(n\). Thus, after also conditioning on the independent random seed of a possibly randomized estimator \(\widetilde{\xi}\), \[\mathbb{P}\{\widetilde{\xi}\in\{\xi,-\xi\}\mid A^\mu=a\} \le 1-\frac{1}{2}\mathbb{P}\{\mathcal{E}\mid A^\mu=a\}.\] Averaging over \(A^\mu\) and using \(\mathbb{P}(\mathcal{E})=1-o(1)\) yields, uniformly over all such estimators, \[\mathbb{P}\{\widetilde{\xi}\in\{\xi,-\xi\}\} \le\frac{1}{2}+o(1).\] This completes the proof. ◻

Proof. We first locate the cap threshold uniformly in \(d\). There are absolute constants \(a,q_0>0\) such that \[\mathbb{P}\{X_1\ge a/\sqrt d\}\ge q_0, \qquad X\sim\sigma,\quad d\ge3.\] Indeed, on \([a/\sqrt d,2a/\sqrt d]\) the density \(w_d\) is bounded below by \(c\sqrt d\) when \(a\) is sufficiently small; here we use \(c_d\asymp\sqrt d\). After choosing \(p_0<q_0\), the identity \(p=\mathbb{P}\{X_1\ge\tau\}\) therefore implies \(\tau\ge a/\sqrt d\). In particular, \[\frac{d\tau}{1+\tau}\ge c. \label{eq:spherical-mills-threshold-location}\tag{104}\]

Put \[\delta=\frac{c_0(1-\tau^2)}{d\tau},\] where \(c_0>0\) is a sufficiently small absolute constant. By 104 , \(\delta/(1-\tau)=c_0(1+\tau)/(d\tau)\le1\), so \([\tau,\tau+\delta]\subset[\tau,1]\). Moreover, for every point in this interval, \[\frac{t^2-\tau^2}{1-\tau^2} \le \frac{\delta(2\tau+\delta)}{1-\tau^2} \le \frac{Cc_0}{d}.\] Consequently, \[\left(\frac{1-t^2}{1-\tau^2}\right)^{(d-3)/2} \ge c, \qquad \tau\le t\le\tau+\delta.\] Integrating over this interval gives \[\int_\tau^1(1-t^2)^{(d-3)/2}\,dt \ge c\frac{(1-\tau^2)^{(d-1)/2}}{d\tau}.\] For the upper bound, use \(t\ge\tau\) on \([\tau,1]\): \[\begin{align} \int_\tau^1(1-t^2)^{(d-3)/2}\,dt &\le \frac{1}{\tau} \int_\tau^1 t(1-t^2)^{(d-3)/2}\,dt \\ &= \frac{(1-\tau^2)^{(d-1)/2}}{(d-1)\tau} \le C\frac{(1-\tau^2)^{(d-1)/2}}{d\tau}. \end{align}\] Multiplication by \(c_d\) proves the two-sided estimate. ◻

Proof. The differential equation 102 gives \[(1-t^2)y''(t)-(d-1)t\,y'(t)+\ell(\ell+d-2)y(t)=0,\] for \(y=P_\ell^{(d)}\). Multiplying by \((1-t^2)^{(d-3)/2}\) gives \[\frac{d}{dt} \left[ (1-t^2)^{(d-1)/2}(P_\ell^{(d)})'(t) \right] = -\ell(\ell+d-2)(1-t^2)^{(d-3)/2}P_\ell^{(d)}(t).\] Integrating from \(\tau\) to \(1\), the upper boundary term vanishes because \((1-t^2)^{(d-1)/2}=0\) at \(t=1\). Hence \[\lambda_\ell = \frac{c_d(1-\tau^2)^{(d-1)/2}}{\ell(\ell+d-2)} (P_\ell^{(d)})'(\tau). \label{eq:lambda-derivative-identity}\tag{105}\] The normalized derivative identity [69] and the addition formula give \[(P_\ell^{(d)})'(t) = \frac{\ell(\ell+d-2)}{d-1}P_{\ell-1}^{(d+2)}(t), \qquad |P_{\ell-1}^{(d+2)}(t)|\le1.\] Substitution into 105 yields \[|\lambda_\ell| \le \frac{c_d}{d-1}(1-\tau^2)^{(d-1)/2}.\] By 14, this implies \(|\lambda_\ell|\le Cp\tau\). ◻

Proof. The identity follows from \(P_1^{(d)}(t)=t\) and \[\int t(1-t^2)^{(d-3)/2}\,dt = -\frac{1}{d-1}(1-t^2)^{(d-1)/2}.\] The comparison 107 follows from the exact formula and 14. Finally, the degree-one reproducing kernel is \(K_1(u,v)=d\langle u,v\rangle\); see [69]. ◻

Proof. The two-sided estimate for \(\tau\) follows from 14. Indeed, using \(c_d\asymp\sqrt d\) and taking logarithms in \[p\asymp \frac{c_d}{d\tau}(1-\tau^2)^{(d-1)/2}\] gives \[L\asymp 1+d\tau^2,\] after increasing the constant in the assumption \(d\ge C L\) to absorb the polynomial prefactor. Hence \(\tau\asymp\sqrt{L/d}\).

After increasing \(C\), we may assume \(\tau\le c_0\) for a sufficiently small absolute constant \(c_0\). We use the refined ultraspherical derivative bound \[\sup_{\ell\ge2} \frac{|(P_\ell^{(d)})'(t)|}{\ell(\ell+d-2)} \le \frac{C}{d}\left(|t|+\frac{1}{d}\right), \qquad |t|\le c_0. \label{eq:refined-ultraspherical-derivative}\tag{108}\] Indeed, the normalized derivative identity gives \[(P_\ell^{(d)})'(t) = \frac{\ell(\ell+d-2)}{d-1}P_{\ell-1}^{(d+2)}(t).\] It remains to bound the normalized polynomial on the right uniformly in its degree. We use the Laplace integral representation; see [70]. If \(q\ge3\) and \(Z\) is the first coordinate of a uniform point on \(\mathbb{S}^{q-2}\), then \[P_m^{(q)}(t) =\mathbb{E}\left(t+i\sqrt{1-t^2}\,Z\right)^m.\] For \(m=1\), this equals \(t\). For \(m\ge2\), the modulus inside the expectation is at most one, and therefore \[\begin{align} |P_m^{(q)}(t)| &\le \mathbb{E}\left|t+i\sqrt{1-t^2}\,Z\right|^m \\ &\le \mathbb{E}\left|t+i\sqrt{1-t^2}\,Z\right|^2 =t^2+\frac{1-t^2}{q-1} \le C\left(|t|+\frac{1}{q}\right) \label{eq:normalized-zonal-central-bound} \end{align}\tag{109}\] for \(|t|\le c_0\). Applying 109 with \(q=d+2\) and \(m=\ell-1\) proves 108 .

Combining 105 with 108 at \(t=\tau\) gives, for every \(\ell\ge2\), \[|\lambda_\ell| \le \frac{C c_d}{d}(1-\tau^2)^{(d-1)/2} \left(\tau+\frac{1}{d}\right).\] By 14, the prefactor \(c_d d^{-1}(1-\tau^2)^{(d-1)/2}\) is at most \(C p\tau\). Hence \[|\lambda_\ell| \le C p\tau\left(\tau+\frac{1}{d}\right) \le C p\frac{L}{d},\] where the last step uses \(\tau^2\asymp L/d\) and \(L\ge1\). Taking the supremum over \(\ell\ge2\) proves the claim. ◻

Proof. Step 1: Threshold and degree-one coefficient.

Conditioning on \(G\) gives \[S\,\big|\,G \sim N\left(0,\frac{\|G\|^2}{d}\right).\] The chi-square concentration inequality [64] gives \(\mathbb{P}\{|\|G\|/\sqrt d-1|>t\}\le 2e^{-cdt^2}\) for \(0<t<1\). Combining this with the Gaussian tail bounds [64] gives a quantitative comparison. If \(R=\|G\|/\sqrt d\) and \(|R-1|\le c/L\), then, uniformly for \(t\asymp\sqrt L\), \[\overline{\Phi}(t/R)\asymp\overline{\Phi}(t). \label{eq:gaussian-tail-comparison}\tag{111}\] The exceptional probability is at most \(2e^{-cd/L^2}=o(p)\) because \(d\ge CL^3\). Since \(\mathbb{P}\{S\ge t\}=\mathbb{E}\overline{\Phi}(t/R)\), evaluating 111 at two sufficiently small and large constant multiples of \(\sqrt L\) brackets the upper \(p\)-quantile and proves \(u\asymp\sqrt L\).

The same conditioning gives \[\mathbb{E}\left[S\mathbf{1}_{\{S\ge u\}}\mid G\right] = \frac{\|G\|}{\sqrt d} \varphi\left(\frac{u\sqrt d}{\|G\|}\right),\] where \(\varphi\) is the standard Gaussian density. On \(|R-1|\le c/L\), the integrand is comparable to \(\varphi(u)\); the exceptional part is \(o(p\sqrt L)\). Mills’ ratio [67] gives \(\varphi(u)\asymp pu\asymp p\sqrt L\). Thus \(m_1\asymp p\sqrt L\), which, by 41 , proves the bounds on \(\beta\) in 17.

Step 2: Radial harmonic decomposition.

For \(G\sim\gamma_d\), write \[R:=\frac{\|G\|}{\sqrt d}, \qquad U:=\frac{G}{\|G\|}.\] Then \(G=\sqrt d\,RU\), where \(U\sim\sigma\) is independent of \(R\); let \(\nu_d\) be the law of \(R\). The spherical-harmonic decomposition from 8.1 gives \[L^2(\gamma_d) =\bigoplus_{\ell\ge0}L^2(\nu_d)\otimes\mathcal{H}_\ell^d.\] The operator preserves each summand and acts there through an integral operator on the radial factor.

With \(P_0^{(d)}\equiv1\), set, for \(\ell\ge0\), \[F_\ell(q) =\int_{u/(\sqrt d q)}^1P_\ell^{(d)}(t)w_d(t)\,dt,\] with the integral interpreted as zero if its lower endpoint exceeds one. The Funk–Hecke formula [69] shows that the radial kernel in degree \(\ell\) is \(K_\ell(r,s)=F_\ell(rs)\). If \(Qf=f-\int f\,d\nu_d\), then the degree-zero block of \(T_r\) is \(QK_0Q\); the positive-degree blocks are unchanged.

We record the derivative bounds needed below. Let \(\mathcal{I}=[1-c/L,1+c/L]\). Gaussian norm concentration [64] gives \[\mathbb{P}\{R\notin\mathcal{I}\}\le2e^{-cd/L^2}, \qquad \|R-1\|_{L^k(\nu_d)}\le \frac{C_k}{\sqrt d}, \quad 2\le k\le6. \label{eq:gaussian-radial-moments}\tag{112}\] For \(r,s\in\mathcal{I}\), the shifted threshold \(u/(rs)\) differs from \(u\) by \(O(L^{-1/2})\). To justify the derivative bounds below, put \(z_q=u/(\sqrt d q)\). Direct differentiation gives \[F_0'(q)=\frac{u}{\sqrt d\,q^2}w_d(z_q), \qquad \frac{w_d'(z)}{w_d(z)}=-\frac{(d-3)z}{1-z^2}.\] For \(q=rs\) with \(r,s\in\mathcal{I}\), we have \(dz_q/dq=-z_q/q\) and \(dz_q^2=O(L/d)\). It follows by two further differentiations that \(|F_0^{(j)}(q)|\le C_jpL^j\) for \(1\le j\le3\); the case \(j=0\) follows from the Gaussian tail comparison. Similarly, the explicit formula \[F_1(q)=\frac{c_d}{d-1} \left(1-\frac{u^2}{dq^2}\right)^{(d-1)/2},\] has logarithmic derivative \[\frac{F_1'(q)}{F_1(q)} =\frac{(d-1)z_q^2}{q(1-z_q^2)}=O(L).\] Differentiating this identity once more gives \(|F_1''(q)|\le C L^2|F_1(q)|\). Since Gaussian Mills bounds give \(F_1(q)\asymp p\sqrt{L/d}\) uniformly in this interval, we obtain \[\begin{align} |F_0^{(j)}(q)|&\le C_jpL^j, &&0\le j\le3,\tag{113}\\ |F_1^{(j)}(q)|&\le C_jp\sqrt{\frac{L}{d}}\,L^j, &&0\le j\le2,\tag{114} \end{align}\] whenever \(q=rs\) with \(r,s\in\mathcal{I}\). Uniformly on the same set, 16, applied at the shifted threshold, gives \[\sup_{\ell\ge2}|F_\ell(rs)|\le Cp\frac{L}{d}. \label{eq:gaussian-higher-radial-blocks}\tag{115}\] The complement of \(\mathcal{I}^2\) contributes at most \(Ce^{-cd/(2L^2)}\) in Hilbert–Schmidt norm. Since \(d\ge CL^3\), increasing \(C\) makes this quantity at most \(CpL/d\); thus it is absorbed in each of the block estimates below.

Step 3: Bounds for the radial blocks.

Put \(\delta_r=r-1\) and \(\delta_s=s-1\). Since \(rs-1=\delta_r+\delta_s+\delta_r\delta_s\), Taylor’s formula at \(1\) gives \[F_0(rs)=F_0(1)+F_0'(1)(rs-1) +\frac{1}{2}F_0''(1)(rs-1)^2+\mathcal{R}_3(r,s).\] Applying \(Q\) in both variables removes the constant and one-variable terms. The surviving part of the linear term is \(F_0'(1)Q\delta_r\,Q\delta_s\). Since \(Q\) is an orthogonal projection, \[\|Q_rQ_s[(rs-1)^2]\|_2 \le \|(rs-1)^2\|_2 =\|rs-1\|_4^2\le \frac{C}{d}.\] Here \(Q_r\) and \(Q_s\) mean that \(Q\) acts in the \(r\) and \(s\) variables, respectively. Thus the linear and quadratic contributions have respective norms at most \[|F_0'(1)|\|Q\delta_r\|_2\|Q\delta_s\|_2 \le \frac{CpL}{d}, \qquad \frac{1}{2}|F_0''(1)|\|Q_rQ_s[(rs-1)^2]\|_2 \le \frac{CpL^2}{d}.\] The integral remainder satisfies \[\|\mathcal{R}_3\|_2 \le CpL^3\|rs-1\|_6^3 \le Cp\frac{L^3}{d^{3/2}}.\] By 112 113 and \(d\ge CL^2\), these contributions sum to at most \(CpL^2/d\). Hence \[\|QK_0Q\|_{\mathrm{op}} \le\|QK_0Q\|_{\mathrm{HS}} \le Cp\frac{L^2}{d}. \label{eq:gaussian-radial-zero-block}\tag{116}\]

For degree one, 114 112 yield \[\|K_1-F_1(1)(\mathbf{1}\otimes\mathbf{1})\|_{\mathrm{HS}} \le Cp\frac{L^{3/2}}{d}.\] Write \(E=K_1-F_1(1)(\mathbf{1}\otimes\mathbf{1})\). Since \(\|r\|_2=\|\mathbf{1}\|_2=1\) and \(1-\langle r,\mathbf{1}\rangle^2=\operatorname{Var}(r)\le C/d\), \[\left|\beta-F_1(1)\right| \le \|E\|_{\mathrm{op}}+C\frac{|F_1(1)|}{d}.\] The normalized radial function \(r\mapsto r\) has \(L^2(\nu_d)\) norm one, and the coefficient of the Gaussian coordinate functions is \[\beta=\langle r,K_1r\rangle_{L^2(\nu_d)}.\] Moreover, \[\|r\otimes r-\mathbf{1}\otimes\mathbf{1}\|_{\mathrm{op}} \le \|(r-\mathbf{1})\otimes r\|_{\mathrm{op}} +\|\mathbf{1}\otimes(r-\mathbf{1})\|_{\mathrm{op}} \le \frac{C}{\sqrt d}.\] Combining the last three displays, using \(|F_1(1)|+|\beta|\le Cp\sqrt{L/d}\), gives \[\|K_1-\beta(r\otimes r)\|_{\mathrm{op}} \le Cp\frac{L^{3/2}}{d}. \label{eq:gaussian-radial-one-residual}\tag{117}\] Finally, apply the elementary Schur bound to the restriction of \(K_\ell\) to \(\mathcal{I}^2\) and add the Hilbert–Schmidt estimate for its complement from the paragraph following 115 . Since \(\nu_d\) is a probability measure, this gives \[\sup_{\ell\ge2}\|K_\ell\|_{\mathrm{op}} \le Cp\frac{L}{d}. \label{eq:gaussian-radial-higher-op}\tag{118}\] Taking the supremum over the mutually orthogonal blocks in 116 117 118 proves \[\|T_{r_\perp}\|_{\mathrm{op}}\le Cp\frac{L^2}{d}.\] Adding the rank-\(d\) first-chaos operator, whose norm is \(\beta\asymp p\sqrt{L/d}\), proves the bound for \(T_r\) in 110 .

Step 4: Section bounds.

If \(|\|x\|/\sqrt d-1|\le c/L\), then \(u\sqrt d/\|x\|=u+O(1/\sqrt L)\) and the Gaussian tail comparison in 111 gives \[\mathbb{P}\{\langle x,Y\rangle/\sqrt d\ge u\}\le Cp.\] The \(L^2\) section bounds now follow from \(q_{\rm G}^2\le 2\mathbf{1}_{\{\langle x,Y\rangle/\sqrt d\ge u\}}+2p^2\), and the definitions of \(r\) and \(r_\perp\). Indeed, conditional Jensen gives \(a(x)^2\le\mathbb{E}_Yq_{\rm G}(x,Y)^2\le Cp\) and \(\mathbb{E}a(Y)^2\le\mathbb{E}q_{\rm G}(G,Y)^2\le Cp\), while \[\beta^2\mathbb{E}\langle x,Y\rangle^2 =\beta^2\|x\|^2 \le Cp^2L\le Cp\] on the stated radial set. Expanding the two definitions and increasing the constant proves both claims. ◻

Proof. For independent \(G,G'\sim N(0,I_d)\), set \(U=(G+G')/\sqrt2\) and \(V=(G-G')/\sqrt2\). Then \(U,V\) are independent standard Gaussian vectors and \[\frac{\langle G,G'\rangle}{\sqrt d} =\frac{\|U\|^2-\|V\|^2}{2\sqrt d}.\] For equal labels, the remaining linear term is \(\sqrt2\mu U_1\), so the edge statistic has law \(m_\mu+T_\mu\). For opposite labels, swapping \(U\) and \(V\) shows that it has law \(-m_\mu-T_\mu\). This proves 122 . Since \(p=(p_+(\mu)+p_-(\mu))/2\), 122 also gives \[p=\frac{1}{2}\mathbb{P}\{T_\mu\ge\tau-m_\mu\} +\frac{1}{2}\mathbb{P}\{T_\mu\le-\tau-m_\mu\}. \label{eq:gmbm-threshold-mixture}\tag{126}\]

10.0.0.2 Local density estimates.

Write \[X_d=\frac{1}{2\sqrt d}\sum_{k=2}^d (U_k^2-V_k^2), \qquad Q_\mu=\frac{U_1^2-V_1^2}{2\sqrt d}+\sqrt2\,\mu U_1,\] so that \(T_\mu=X_d+Q_\mu\) and \(X_d\) is independent of \(Q_\mu\). By the orthogonal change of variables \((U_{2:d},V_{2:d})\mapsto ((U_{2:d}+V_{2:d})/\sqrt2,(U_{2:d}-V_{2:d})/\sqrt2)\), \(X_d\) has the same law as \(\langle G^{(1)},G^{(2)}\rangle/\sqrt d\) for independent \(G^{(1)},G^{(2)}\sim N(0,I_{d-1})\). Conditional on \(G^{(1)}\), its density is Gaussian. Consequently, with \(R=\|G^{(1)}\|/\sqrt d\), \[f_{X_d}(x)=\mathbb{E}\left[\frac{1}{R}\varphi\left(\frac{x}{R}\right)\right], \qquad \mathbb{P}\{X_d\ge x\}=\mathbb{E}\overline{\Phi}\left(\frac{x}{R}\right).\] Chi-square concentration [64] gives \(\mathbb{P}\{|R-1|>c/L\}\le 2\exp(-cd/L^2)\). Splitting the two expectations over this event and its complement first gives \[c e^{-Cx^2}\le \mathbb{P}\{X_d\ge x\}\le C e^{-cx^2}, \qquad 1\le x\le c\sqrt d. \label{eq:gmbm-X-tail}\tag{127}\] Together with 126 and the bounds on \(m_\mu\) and \(Q_\mu\), 127 implies \(\tau\asymp\sqrt L\). Using the Gaussian Mills bounds [67] then shows, uniformly for \(c\sqrt L\le x\le C\sqrt L\) and \(|s|\le c/\sqrt L\), that \[f_{X_d}(x+s)\asymp f_{X_d}(-x+s)\asymp \varphi(x), \qquad \mathbb{P}\{X_d\ge x+s\}\asymp\overline{\Phi}(x). \label{eq:gmbm-local-product-tail}\tag{128}\] Indeed, on \(|R-1|\le c/L\) the logarithm of each Gaussian density ratio is \(O(x^2|R-1|+|x s|)=O(1)\); the exceptional contribution is \(O(\exp(-cd/L^2))=O(n^{-D-4})\) after increasing \(C_D\).

The perturbation satisfies \(\mathbb{E}|Q_\mu|\le C(\mu+d^{-1/2})\). Moreover, Gaussian and chi-square tails give \[\mathbb{P}\{|Q_\mu|>c_0/\sqrt L\} \le \exp(-c/(\mu^2L))+\exp(-c\sqrt{d/L}) \label{eq:gmbm-Q-tail}\tag{129}\] and the right-hand side is \(O(n^{-D-4})\). Because \(m_\mu\le c_D/\sqrt L\) and \(Q_\mu\) is at most \(c_0/\sqrt L\) outside an event of probability \(O(n^{-D-4})=o(p)\), 128 and 126 prove 123 . Applying the density identity \(f_\mu(t)=\mathbb{E}f_{X_d}(t-Q_\mu)\) and splitting according to the same event for \(Q_\mu\) proves 124 , including the lower bound.

10.0.0.3 Comparison of the two tails.

On \(|Q_\mu|\le c_0/\sqrt L\), the interval between \(t\) and \(t-Q_\mu\) stays in the window where 128 and 123 give a density bound \(Cp\sqrt L\). Conditioning on \(Q_\mu\) therefore yields \[\left| \mathbb{P}\{X_d+Q_\mu\ge t\}-\mathbb{P}\{X_d\ge t\} \right| \le C p\sqrt L\,\mathbb{E}|Q_\mu| +\mathbb{P}\{|Q_\mu|>c_0/\sqrt L\}. \label{eq:gmbm-upper-tail-perturbation}\tag{130}\] The lower-tail analogue of 130 holds as well. We now compare the two terms in 129 directly with the target scale. Put \[a=\frac{1}{\mu^2L},\qquad q=\sqrt{\frac{d}{L}}.\] By 121 , \(a,q\ge C_D\log n\), while \(np\ge C_D\log n\) implies \(L\le C\log n\). After increasing \(C_D\), the elementary fact \(\log x=o(x)\) gives \[ca\ge L+\frac{1}{2}\log a+C, \qquad cq\ge L+\log q+C.\] Since \(e^{-L}=p/e\), it follows that \[e^{-ca}\le Cp\,a^{-1/2}=Cp\mu\sqrt L, \qquad e^{-cq}\le Cp\,q^{-1}=Cp\sqrt{\frac{L}{d}}. \label{eq:gmbm-Q-tail-absorption}\tag{131}\] Thus 129 is absorbed by \(p\sqrt L(\mu+d^{-1/2})\). Since \(X_d\) is symmetric, \(\mathbb{P}\{X_d\le -t\}=\mathbb{P}\{X_d\ge t\}\), and 125 follows. ◻

Proof. The tail estimates in 19 do not by themselves control the full population kernel. We compare that kernel with the zero-mean Gaussian model by interpolation. The parameter \(\alpha\) turns on the label-dependent linear Gaussian term, while \(b\) turns on the deterministic shift between same-label and opposite-label pairs. We follow the path \((0,0)\to(\mu,0)\to(\mu,m_\mu)\), keeping the mean, the label coefficient, and the one-variable Hoeffding components removed along the entire path. We will prove that the two paths are operator-norm Lipschitz and satisfy \[\begin{align} \sup_{0\le\alpha\le\mu} \|\partial_\alpha\mathcal{T}_{\alpha,0}\|_{\mathrm{op}} &\le Cp\sqrt L, \tag{133}\\ \sup_{|b|\le m_\mu} \|\partial_b\mathcal{T}_{\mu,b}\|_{\mathrm{op}} &\le Cp\left(\frac{L^{3/2}}{\sqrt d}+\mu L\right). \tag{134} \end{align}\] The derivatives may be interpreted weakly.

To make the effect of the subtractions precise, let \(\mathsf P\) denote the orthogonal projection in \(L^2(\mathbb{P}_Y\otimes\mathbb{P}_Y)\) onto the symmetric canonical kernels orthogonal to the label kernel \((Y,Y')\mapsto\xi\xi'\). The kernel of \(\mathcal{T}_{\alpha,b}\) is \(\mathsf P K_{\alpha,b}\). The projection \(\mathsf P\) is independent of \((\alpha,b)\), so, after smoothing the threshold, \[\partial_\alpha\mathcal{T}_{\alpha,b} =T_{\mathsf P(\partial_\alpha K_{\alpha,b})}, \qquad \partial_b\mathcal{T}_{\alpha,b} =T_{\mathsf P(\partial_b K_{\alpha,b})}.\] In particular, applying the mean, label, and one-variable subtractions cannot increase any Hilbert–Schmidt estimate below. This observation also justifies integrating the two weak derivatives at the end of the proof.

10.0.0.4 Harmonic block decomposition.

We include the decomposition that is needed to account for radial multiplicity. Write \(g=(x,r\omega)\) with \(x=g_1\sim N(0,1)\), \(r=\|g_{2:d}\|\), and \(\omega\in\mathbb{S}^{d-2}\), and let \(\nu_{d-1}\) denote the law of \(r\). The kernel is invariant under simultaneous rotations of \(\omega\) and \(\omega'\). Hence \[L^2(\mathbb{P}_Y) =L^2(\{\pm1\})\otimes \bigoplus_{\ell\ge0} L^2(\gamma_1\otimes\nu_{d-1})\otimes\mathcal{H}_\ell^{d-1},\] where \(L^2(\{\pm1\})\) carries the uniform measure. After decomposing this two-dimensional label factor, each label block is the orthogonal direct sum, over \(\ell\), of an integral operator on the \((x,r)\) variables. Thus its operator norm is the supremum of the norms of these radial blocks. In particular, the radial factor must be treated as an integral operator rather than as a scalar.

More explicitly, if \(t=\langle\omega,\omega'\rangle\), then the threshold statistic equals \[\frac{xx'}{\sqrt d}+\frac{rr'}{\sqrt d}t +\alpha(\xi x'+\xi'x)+b\xi\xi'.\] Except on the null set \(rr'=0\), the degree-\(\ell\) angular coefficient is therefore \[\int_{q_{\alpha,b}}^1P_\ell^{(d-1)}(t)w_{d-1}(t)\,dt, \qquad q_{\alpha,b} =\frac{\sqrt d\{\tau-\alpha(\xi x'+\xi'x)-b\xi\xi'\}-xx'}{rr'}. \label{eq:gmbm-explicit-radial-block}\tag{135}\] This formula is the starting point for every derivative estimate below. To make the boundary factors explicit, write \(A=\xi x'+\xi'x\) and let \(\mathcal{F}_\ell(\alpha,b)\) denote the coefficient in 135 , with all radial variables fixed. At points where \(|q_{\alpha,b}|<1\), \[\begin{align} \partial_\alpha\mathcal{F}_\ell(\alpha,b) &=\frac{\sqrt d}{rr'}A P_\ell^{(d-1)}(q_{\alpha,b})w_{d-1}(q_{\alpha,b}),\\ \partial_b\mathcal{F}_\ell(\alpha,b) &=\frac{\sqrt d}{rr'}\xi\xi' P_\ell^{(d-1)}(q_{\alpha,b})w_{d-1}(q_{\alpha,b}). \end{align}\]

We next record the finite-dimensional boundary-density estimate used in these formulas. Define \[\rho_d(z)=\frac{1}{\sqrt d}w_{d-1}\left(\frac{z}{\sqrt d}\right) =\frac{c_{d-1}}{\sqrt d} \left(1-\frac{z^2}{d}\right)^{(d-4)/2} \mathbf{1}_{\{|z|<\sqrt d\}}. \label{eq:gmbm-rho-def}\tag{136}\] If \(|z-\tau|\le C/\sqrt L\), then \(z\asymp\sqrt L\) by 19. Moreover, 121 and \(L\le C\log n\) imply \(d\ge CL^3\). Therefore, \[\log\rho_d(z) =\log\frac{c_{d-1}}{\sqrt d}-\frac{z^2}{2} +O\left(\frac{z^2+z^4}{d}\right),\] and hence \(\rho_d(z)\asymp\varphi(z)\asymp p\sqrt L\). If \(\ell_d=\log\rho_d\) on \((-\sqrt d,\sqrt d)\), then \[\ell_d'(z)=-\frac{(d-4)z}{d-z^2},\qquad \ell_d''(z)=-\frac{(d-4)(d+z^2)}{(d-z^2)^2},\qquad |\ell_d'''(z)|\le C\frac{\sqrt L}{d}\] throughout the same window. Differentiating \(\rho_d=e^{\ell_d}\) therefore gives the local bounds \[c p\sqrt L\le\rho_d(z)\le Cp\sqrt L, \qquad |\rho_d^{(j)}(z)|\le C_jpL^{(j+1)/2}, \quad 0\le j\le3. \label{eq:gmbm-rigorous-density-derivatives}\tag{137}\] In particular, on typical radii the factor \(\sqrt d/(rr')\) in the derivative formulas combines with \(w_{d-1}(q)=\sqrt d\,\rho_d(\sqrt d q)\) to give a boundary coefficient of order \(p\sqrt L\).

Approximate the threshold by a smooth monotone function and differentiate before taking the approximation limit. For the population calculation, use the parameter-adaptive set \[|x|,|x'|\le c_0\left(\frac{d}{L}\right)^{1/4}, \qquad \left|\frac{r}{\sqrt d}-1\right| +\left|\frac{r'}{\sqrt d}-1\right| \le \frac{c_0}{L}. \label{eq:gmbm-interpolation-typical-set}\tag{138}\] Gaussian and chi-square concentration bound the probability of its complement by \[C\exp\{-c\sqrt{d/L}\}+C\exp\{-cd/L^2\}.\] Let \(\mathcal{B}\) denote this exceptional set and put \(A=\xi x'+\xi'x\). Since \(w_{d-1}\le C\sqrt d\) and \(|P_\ell^{(d-1)}|\le1\), the absolute values of the differentiated coefficients are bounded by \[\frac{Cd|A|}{rr'} \quad\text{for the \alpha path}, \qquad \frac{Cd}{rr'} \quad\text{for the b path}.\] Here \(r^2\sim\chi^2_{d-1}\), so the gamma-function formula for inverse chi-square moments gives \[\mathbb{E}\left(\frac{\sqrt d}{r}\right)^8\le C.\] Together with the fixed Gaussian moments of \(A\), Cauchy–Schwarz yields, for either differentiated coefficient \(D\), \[\|D\mathbf{1}_{\mathcal{B}}\|_2 \le (\mathbb{E}|D|^4)^{1/4}\mathbb{P}(\mathcal{B})^{1/4} \le C\mathbb{P}(\mathcal{B})^{1/4}.\] After changing the absolute constant in the exponent, this is bounded by \(Ce^{-cq}+Ce^{-cq^2/L}\), where \(q=\sqrt{d/L}\). The derived conditions in 121 give \(q\ge C_D\log n\) and \(L\le C\log n\). Therefore, after increasing \(C_D\), \[e^{-cq}+e^{-cq^2/L} \le C e^{-L}\frac{L}{q} =Cp\frac{L}{q} =Cp\frac{L^{3/2}}{\sqrt d}. \label{eq:gmbm-interpolation-bad-set}\tag{139}\] This is the required error for the \(b\) path, and it is at most \(Cp\sqrt L\) for the \(\alpha\) path because \(q\ge\sqrt L\).

On 138 , the upper signal bound and \(|b|\le m_\mu\) give \[\alpha(|x|+|x'|)\le \frac{c}{\sqrt L},\qquad |b|\le\frac{c}{\sqrt L},\qquad \frac{|xx'|}{\sqrt d}\le\frac{c}{\sqrt L}.\] Together with \(\tau\asymp\sqrt L\) and the radial restriction, these bounds show from 135 that every boundary lies at \(t=\tau+O(L^{-1/2})\) on the normalized one-dimensional scale.

On a fixed harmonic block, the Funk–Hecke formula [69] therefore reduces each derivative to a boundary coefficient in this window, where 137 applies. The normalized radii satisfy \[\left\|\frac{r}{\sqrt d}-1\right\|_{L^k} +\left\|\frac{r'}{\sqrt d}-1\right\|_{L^k} \le \frac{C_k}{\sqrt d}, \qquad 2\le k\le6,\] as in 112 . Taylor expansion of every radial block in these normalized radii, followed by Cauchy–Schwarz in the two radial variables, therefore has the same bounds as the scalar coefficients in 137 . The degree-zero radial term is compressed by the Hoeffding projection, so its constant and one-variable Taylor terms vanish.

10.0.0.5 Interpolation in \(\alpha\).

We first vary \(\alpha\) along the path \((\alpha,0)\). Let \(\eta\) denote the joint law of \((\xi,x,r)\). On the typical set 138 , the product of \(\sqrt d/(rr')\) and \(w_{d-1}(q_{\alpha,0})\) is at most \(Cp\sqrt L\). Since \(|P_\ell^{(d-1)}|\le1\) and \(\mathbb{E}(\xi x'+\xi'x)^2=2\), the Hilbert–Schmidt norm of every differentiated radial block satisfies \[\begin{align} &\int\!\!\int \left| \frac{\sqrt d}{rr'}(\xi x'+\xi'x) P_\ell^{(d-1)}(q_{\alpha,0}) w_{d-1}(q_{\alpha,0}) \right|^2\,d\eta\,d\eta' \\ &\le C p^2L. \end{align}\] Thus the operator norm of each block is at most \(Cp\sqrt L\). The mean, label, and one-variable Hoeffding components lie in mutually orthogonal subspaces of \(L^2(\eta\otimes\eta)\), so removing them does not increase this Hilbert–Schmidt bound. Taking the supremum over the orthogonal harmonic blocks gives \[\|\partial_\alpha\mathcal{T}_{\alpha,0}\|_{\mathrm{op}} \le Cp\sqrt L.\] This proves 133 .

10.0.0.6 Interpolation in \(b\).

We next vary \(b\) along \((\mu,b)\). The constant Gaussian component in the label-odd block is exactly \(\partial_b\Delta(\mu,b)\) and is absent from \(\partial_b\mathcal{T}_{\mu,b}\). For every positive angular degree, the normalized zonal-polynomial estimate 109 gives, on the typical set, \[|P_\ell^{(d-1)}(q_{\mu,b})| \le C\left( \sqrt{\frac{L}{d}} +\frac{\mu(|x|+|x'|)}{\sqrt d} +\frac{|b|}{\sqrt d} +\frac{|xx'|+1}{d} \right),\qquad \ell\ge1.\] Multiplying by the \(O(p\sqrt L)\) boundary factor and taking the \(L^2\) norm in \((x,x')\) gives \[Cp\sqrt L\left( \sqrt{\frac{L}{d}}+\frac{\mu{\sqrt d}}{+}\frac{|b|}{\sqrt d}+\frac{1}{d} \right) \le \frac{CpL}{\sqrt d},\] where we used the bounded Gaussian moments of \(x,x'\), together with \(\mu\sqrt L\le c\), \(|b|\sqrt L\le c\), and \(d\ge L\). Consequently, \[\sup_{\ell\ge1} \|\partial_b\mathcal{T}_{\mu,b}^{(\ell)}\|_{\mathrm{op}} \le \frac{CpL}{\sqrt d}, \label{eq:gmbm-b-positive-degree}\tag{140}\] where \(\mathcal{T}_{\mu,b}^{(\ell)}\) denotes the degree-\(\ell\) harmonic block.

It remains to treat angular degree zero. Put \(\delta_r=r/\sqrt d-1\) and define \(\delta_{r'}\) similarly. On the typical set, the normalized boundary \(z_{\mu,b}=\sqrt d\,q_{\mu,b}\) satisfies \[\begin{align} z_{\mu,b} ={}&\tau-\mu(\xi x'+\xi'x)-b\xi\xi'-\frac{xx'}{\sqrt d} -\tau(\delta_r+\delta_{r'}) \\ &+O\!\left( \sqrt L(\delta_r+\delta_{r'})^2 +(\delta_r+\delta_{r'}) \left[\mu(|x|+|x'|)+|b|+\frac{|xx'|}{\sqrt d}\right] \right). \end{align} \label{eq:gmbm-normalized-boundary-expansion}\tag{141}\] Because \(rr'=d(1+\delta_r)(1+\delta_{r'})\), the differentiated degree-zero kernel is exactly \[\xi\xi'\frac{1}{(1+\delta_r)(1+\delta_{r'})} \rho_d(z_{\mu,b}).\] To track the Taylor terms, write \[U=\mu(\xi x'+\xi'x),\qquad V=b\xi\xi',\qquad W=\frac{xx'}{\sqrt d},\qquad R=\tau(\delta_r+\delta_{r'}).\] Then 141 reads \(z_{\mu,b}=\tau-U-V-W-R+E\), where \[|E|\le C\left[ \sqrt L(\delta_r+\delta_{r'})^2 +|\delta_r+\delta_{r'}|(|U|+|V|+|W|) \right].\] We expand \(\rho_d\) to second order at \(\tau\), with an integral third-order remainder, and expand \([(1+\delta_r)(1+\delta_{r'})]^{-1}\) to second order at \((0,0)\). The mean, label coefficient, and one-variable Hoeffding component in each argument are then removed. Every pure power of \(V\) becomes either a constant or a multiple of \(\xi\xi'\), while the term linear in \(U\) becomes a sum of one-variable kernels after multiplication by the outer factor \(\xi\xi'\). These terms therefore vanish under the corresponding projections.

We give the norm calculation for the terms that remain. By 112 , all fixed moments of \(x,x'\) are bounded and \[\|\delta_r\|_k+\|\delta_{r'}\|_k\le\frac{C_k}{\sqrt d}, \qquad 2\le k\le6.\] Together with 137 , the linear denominator and boundary terms, the \(W\) term, and the mixed \(UV\) term have joint \(L^2\) norm at most \[Cp\left( \frac{L^{3/2}}{\sqrt d}+\frac{L}{\sqrt d}+\mu L \right). \label{eq:gmbm-degree-zero-linear-terms}\tag{142}\] The first term comes from \(R\) and the radial denominator, the second from \(W\), and the last uses \(\mu|b|L^{3/2}\le C\mu L\). The terms of quadratic order are bounded by \[Cp\left( \frac{L^{3/2}}{\sqrt d} +\frac{\mu L^2}{\sqrt d} +\mu^2L^{3/2} +\mu|b|L^{3/2} \right). \label{eq:gmbm-degree-zero-quadratic-terms}\tag{143}\] The four contributions arise, respectively, from the second-order radial error \(E\), the products \(UR\) and \(UW\), the product \(U^2\), and the mixed product \(UV\). Finally, the third-order Taylor remainder has norm at most \[Cp\left( \frac{L^{3/2}}{\sqrt d} +\frac{\mu L^2}{\sqrt d} +\mu^2L^{3/2} +\mu|b|L^{3/2} +\mu^3L^2 \right). \label{eq:gmbm-degree-zero-cubic-terms}\tag{144}\] Indeed, the only new largest monomial is \(U^3\), whose coefficient is at most \(CpL^2\) by 137 ; terms containing \(W,R,E\), or a denominator remainder are bounded by the first four terms in 144 . This follows from Hölder’s inequality and the moment bounds in 112 . Since orthogonal projection is a contraction in \(L^2\), the same estimates hold after the required components are removed. The assumptions \(d\ge CL^3\), \(\mu\sqrt L\le c\), and \(|b|\sqrt L\le c\) imply \[\frac{\mu L^2}{\sqrt d}\le C\mu L,\qquad \mu^2L^{3/2}+\mu|b|L^{3/2}+\mu^3L^2\le C\mu L.\] Thus 142 143 144 are all at most \(Cp(L^{3/2}/\sqrt d+\mu L)\). Since operator norm is bounded by Hilbert–Schmidt norm on each radial block, the degree-zero block is therefore bounded by \[Cp\left(\frac{L^{3/2}}{\sqrt d}+\mu L\right).\] Together with the positive-degree estimate 140 , this proves 134 .

10.0.0.7 Integration of the two paths.

At \((0,0)\) the labels play no role. The proof of 17, applied at the fixed threshold \(\tau\) (whose tail is comparable to \(p\) by 123 ), gives \[\|\mathcal{T}_{0,0}\|_{\mathrm{op}} \le Cp\left(\sqrt{\frac{L}{d}}+\frac{L^2}{d}\right).\] Integrating 133 from \(0\) to \(\mu\) and then 134 from \(0\) to \(m_\mu\) proves 132 , because \(m_\mu L^{3/2}/\sqrt d=\mu^2L^{3/2}\) and \(m_\mu\mu L=\mu^3\sqrt d\,L\).

To remove the smoothing, integrate each first derivative in the Gaussian coordinate normal to the threshold boundary. The resulting formula contains the ordinary Gaussian density and is dominated by 133 134 . Dominated convergence yields the weak derivatives in 133 134 ; the uniform bounds make both paths operator-norm Lipschitz. ◻

Proof of 18. Size of the label signal. By 122 125 , \[\begin{align} p_+(\mu)-p_-(\mu) &= \int_{\tau-m_\mu}^{\tau+m_\mu}f_\mu(t)\,dt +O\!\left(p\sqrt L\left(\mu+\frac{1}{\sqrt d}\right)\right). \end{align}\] Moreover, \[\frac{\mu+d^{-1/2}}{m_\mu} =\frac{1}{\mu\sqrt d}+\frac{1}{\mu^2d} \le \frac{C}{\sqrt{\log n}}\] by \(\mu^2d\ge C_D\log n\). Thus the error is smaller than the integral after increasing \(C_D\), and 124 gives \[p_+(\mu)-p_-(\mu) \asymp m_\mu\,p\sqrt L = p\mu^2\sqrt{dL}.\] Since \(\Delta_\mu=(p_+(\mu)-p_-(\mu))/2\), this proves the first estimate in 119 .

The residual population operator. At \((\alpha,b)=(\mu,m_\mu)\), the operator \(\mathcal{T}_{\alpha,b}\) defined in 20 is exactly \(T_{r_\mu^{\rm lab}}\). Hence 132 gives \[\Lambda_\mu^{\rm lab} \le Cp\left( \sqrt{\frac{L}{d}}+\frac{L^2}{d} +\mu\sqrt L+\mu^2L^{3/2}+\mu^3\sqrt d\,L \right).\] The derived conditions 121 , together with \(m_\mu\sqrt L\le c_D\), imply \(\mu L\le C\) and \[\frac{L^2}{d}\le\sqrt{\frac{L}{d}},\qquad \mu^2L^{3/2}=\mu\sqrt L\,(\mu L)\le C\mu\sqrt L,\qquad \mu^3\sqrt d\,L =\mu\sqrt L\,(m_\mu\sqrt L)\le c_D\mu\sqrt L.\] This proves the second estimate in 119 .

The remaining pointwise estimate is 21 below. ◻

Proof. For \(y=(\xi,g)\), set \[s_y=\left\|\frac{g}{\sqrt d}+\mu\xi e_1\right\|_2, \qquad b_y=\mu g_1+m_\mu\xi,\] and \[\Psi(s,b)=\frac{1}{2}\left[ \overline{\Phi}\left(\frac{\tau-b}{s}\right) -\overline{\Phi}\left(\frac{\tau+b}{s}\right) \right].\] Conditioning on the second label and Gaussian vector gives \[\mathbb{E}_{Y'}\!\left[ \mathbf{1}_{\{\sqrt d\langle Z(y),Z(Y')\rangle\ge\tau\}}\xi' \right]=\Psi(s_y,b_y).\] The transformation \((\xi,g)\mapsto(-\xi,-g)\) preserves the law and changes the sign of \(\xi\) while leaving \(a_\mu(\xi,g)\) unchanged. Thus \(\mathbb{E}[a_\mu(Y)\xi]=0\). Moreover, \(\Delta_\mu=\mathbb{E}[\xi\Psi(s_Y,b_Y)]\), and therefore \[T_{r_\mu^{\rm lab}}\xi(y) =\Psi(s_y,b_y)-\Delta_\mu\xi. \label{eq:gmbm-label-action-identity}\tag{145}\]

The function \(\Psi(s,b)\) is odd in \(b\). We may therefore write \[\Psi(s,b)=bH(s,b^2),\] where \(H=H(s,z)\) is continuous at \(z=0\). Gaussian Mills bounds and direct differentiation show that, whenever \(|s-1|\le c/L\), \(|b|\le c/\sqrt L\), and \(z=b^2\), \[|H(s,z)|\le Cp\sqrt L, \qquad |\partial_sH(s,z)|+|\partial_zH(s,z)| \le CpL^{3/2}. \label{eq:gmbm-H-derivatives}\tag{146}\] Indeed, these derivatives are linear combinations of \(\varphi^{(j)}((\tau\pm b)/s)\), \(0\le j\le2\), multiplied by bounded powers of \(s^{-1}\). Since \((\tau\pm b)/s=\tau+O(L^{-1/2})\), Gaussian Mills bounds give \(|\varphi^{(j)}((\tau\pm b)/s)|\le C_jpL^{(j+1)/2}\), which proves 146 .

Write \(H_y=H(s_y,b_y^2)\) and recall that \(b_y=m_\mu\xi+\mu g_1\). Since \[\Delta_\mu =\mathbb{E}[\xi b_YH_Y] =m_\mu\mathbb{E}H_Y+\mu\mathbb{E}[\xi G_1H_Y],\] identity 145 becomes \[\begin{align} T_{r_\mu^{\rm lab}}\xi(y) ={}&m_\mu\xi(H_y-\mathbb{E}H_Y)\\ &+\mu\bigl(g_1H_y-\xi\mathbb{E}[\xi G_1H_Y]\bigr). \end{align} \label{eq:gmbm-H-centered-identity}\tag{147}\] The hypotheses on \(y\) and 121 imply \(|s_y-1|\le c/L\) and \(|b_y|\le c/\sqrt L\). The terms in the second line that involve this fixed \(y\), together with the typical part of the expectation, are therefore at most \(C_Dp\mu\sqrt{L\log n}\) by the first bound in 146 and Gaussian moments. Its atypical part is controlled below.

It remains to control the centered factor in the first line. On the same set, \[|s_y-1| \le C_D\left( \sqrt{\frac{\log n}{d}} +\frac{\mu\sqrt{\log n}}{\sqrt d}+\mu^2 \right), \qquad |b_y^2-m_\mu^2| \le C_D\left(m_\mu\mu\sqrt{\log n}+\mu^2\log n\right).\] The same bounds hold in expectation with no larger right-hand side. We make the contribution of atypical \(Y\) explicit. Use the one-point version of the adaptive set 138 , and call its complement \(\mathcal{B}\). The integral identity \[H(s,b^2)=\frac{1}{2b}\int_{-b}^{b} \frac{1}{s}\varphi\left(\frac{\tau-t}{s}\right)dt, \qquad b\ne0,\] with the continuous interpretation at \(b=0\), gives the global bound \(|H(s,b^2)|\le C/s\). If \(s_Y=\|G/\sqrt d+\mu\xi e_1\|\) and \(a=\mu\sqrt d\,\xi e_1\), then \[\frac{1}{\|G+a\|^2}=\int_0^\infty e^{-t\|G+a\|^2}\,dt\] and the Gaussian Laplace transform satisfies \[\mathbb{E}e^{-t\|G+a\|^2} =(1+2t)^{-d/2} \exp\left(-\frac{t\|a\|^2}{1+2t}\right) \le(1+2t)^{-d/2}.\] Consequently, \[\mathbb{E}s_Y^{-2} =d\mathbb{E}\|G+a\|^{-2} \le d\int_0^\infty(1+2t)^{-d/2}\,dt =\frac{d}{d-2}\le C. \label{eq:gmbm-negative-second-moment}\tag{148}\] The same calculation with the representation \(x^{-2}=\int_0^\infty t e^{-tx}\,dt\) shows that \[\mathbb{E}s_Y^{-4} \le d^2\int_0^\infty t(1+2t)^{-d/2}\,dt =\frac{d^2}{(d-2)(d-4)}\le C.\] Hence Cauchy–Schwarz, also using \(\mathbb{E}G_1^4=3\), gives \[\mathbb{E}[|H_Y|\mathbf{1}_{\mathcal{B}}] +\mathbb{E}[|G_1H_Y|\mathbf{1}_{\mathcal{B}}] \le C\mathbb{P}(\mathcal{B})^{1/2}.\] Gaussian and chi-square concentration, followed by the comparison in 139 with a changed absolute exponent, bounds the last display by \[Cp\frac{L}{q}, \qquad q=\sqrt{d/L}.\] For the first line of 147 , multiplication by \(m_\mu\) produces \[m_\mu p\frac{L}{q}=p\mu^2L^{3/2} \le Cp\mu\sqrt{L\log n},\] where the last inequality follows from \(\mu L/\sqrt{\log n}\le C\), a consequence of \(\mu^2L\log n\le c_D\) and \(L\le C\log n\). The atypical contribution to the second line is smaller by the same comparison.

Applying the Lipschitz estimate in 146 around \((1,m_\mu^2)\) gives \[\begin{align} m_\mu|H_y-\mathbb{E}H_Y| \le C_DpL^{3/2}m_\mu\biggl(& \sqrt{\frac{\log n}{d}} +\frac{\mu\sqrt{\log n}}{\sqrt d}+\mu^2\\ &+m_\mu\mu\sqrt{\log n}+\mu^2\log n \biggr). \end{align}\] After division by \(p\mu\sqrt{L\log n}\), the five terms on the right become \[\mu L,\qquad \mu^2L,\qquad \frac{m_\mu\mu L}{\sqrt{\log n}},\qquad m_\mu^2L,\qquad m_\mu\mu L\sqrt{\log n}.\] The third term is bounded by the fifth. The remaining terms are small because \[\mu L\le C m_\mu\sqrt L,\qquad m_\mu^2L=(m_\mu\sqrt L)^2,\qquad m_\mu\mu L\sqrt{\log n} =(m_\mu\sqrt L)(\mu\sqrt{L\log n}),\] while \(m_\mu\sqrt L\le c_D\) and \(\mu^2L\log n\le c_D\) by 121 . Here the first inequality also uses \(\mu^2d\ge C_D\log n\) and \(L\le C\log n\). Thus both lines of 147 are bounded by \(C_Dp\mu\sqrt{L\log n}\), proving 120 . ◻