3.1. Coupling the two models

As noted in Remark 1, the SRGG and the GRGG give the same random graph measure for the special case $p = 1/2.$ While the two models differ for $p \neq 1/2$ , there is a natural way to couple the two models using the same set of Gaussian vectors and the observation that when $\tilde{X} \sim \mathcal{N}(0,I_d)$ , the projection of $\tilde{X}$ onto $\mathbb{S}^{d-1}$ , $X = \tilde{X} / \lVert{\tilde{X}}\rVert$ , is distributed uniformly on $\mathbb{S}^{d-1}.$ Although this coupling is standard, most existing works focus on either the Gaussian model or the spherical model, choosing the one that is easier to deal with for the specific problem. For example, [Reference Devroye, György, Lugosi and Udina11] works with the Gaussian model, where the independence of the Gaussian coordinates is more helpful, while [Reference Li and Schramm18] works with the spherical model, where the arguments rely on properties of the spherical harmonics, an orthonormal basis for functions on the sphere. Similarly to the proofs in [Reference Bangachev and Bresler4], we use this coupling in both directions, leveraging the Gaussian model for some arguments, and turning to the spherical model for others. In this section, we derive results that relate the probabilities of observing a clique in the two models, and similar results for the probability of having an atypically large number of edges. As a consequence, it will suffice to obtain lower and upper bounds for only one of the two models, combined with the results of this section, to complete the proofs of our theorems. The following lemma captures the asymptotic behavior of the thresholds $t_{p}$ and $\tilde t_{p}$ as the dimension d goes to infinity.

Lemma 1. For fixed $p\in(0,1)$ , we have

\begin{align*} \tilde t_{p}=(\bar \Phi^{-1}\left(p\right)+o(1))\sqrt d \quad {and} \quad t_{p}=(\bar \Phi^{-1}\left(p\right)+o(1))/\sqrt d, \end{align*}

where $\bar \Phi\left(\cdot\right)$ is the tail of the standard Gaussian distribution.

Proof. Recall that $\tilde t_{p}$ is defined via $\mathbb{P}(\langle \tilde{X}_1,\tilde{X}_2 \rangle \ge \tilde t_{p}) = p,$ where $\tilde{X}_1$ and $\tilde{X}_2$ are two independent $\mathcal{N}(0,I_d)$ random variables. Then we have

\begin{align*} \left\langle \tilde{X}_1,\tilde{X}_2 \right\rangle = \sum_{j=1}^d \tilde{X}_1^{(j)} \tilde{X}_2^{(j)}, \end{align*}

where $\tilde{X}_i^{(j)}$ , the jth coordinate of $\tilde{X}_i$ , is a standard one-dimensional Gaussian random variable. Note that the collection $\{ \tilde{X}_{i}^{(j)} \,:\, i \in \{1,2\}, 1 \leq j \leq d \}$ is independent. Further, $(\tilde{X}_1^{(j)} \tilde{X}_2^{(j)}, 1\leq j \leq d )$ are independent, and $\mathbb{E}[\tilde{X}_1^{(j)} \tilde{X}_2^{(j)}] = 0$ and $\mathrm{Var}(\tilde{X}_1^{(j)} \tilde{X}_2^{(j)}) = 1$ for all $1 \le j \le d$ . So $\mathrm{Var} (\langle \tilde{X}_1,\tilde{X}_2 \rangle) = d$ . Using the central limit theorem, we get

(3.1) \begin{align} \frac{\left\langle \tilde{X}_1,\tilde{X}_2 \right\rangle}{\sqrt{d}} \Rightarrow \mathcal{N}(0,1) \end{align}

as $d \rightarrow \infty.$ Thus

\begin{align*} p = \mathbb{P}\left(\left\langle \tilde{X}_1,\tilde{X}_2 \right\rangle \ge \tilde t_{p}\right) = \mathbb{P}\left(\frac{\left\langle \tilde{X}_1,\tilde{X}_2 \right\rangle}{\sqrt{d}} \ge \frac{\tilde t_{p}}{\sqrt{d}} \right) \rightarrow \mathbb{P}\left(\mathcal{N}(0,1) \ge \frac{\tilde t_{p}}{\sqrt{d}}\right) = \bar \Phi\left(\frac{\tilde t_{p}}{\sqrt{d}}\right), \end{align*}

which proves the first claim. To see the second part, we use the coupling representation and observe that

\begin{align*}\ \left\langle X_1,X_2 \right\rangle = \frac{\left\langle \tilde{X}_1,\tilde{X}_2 \right\rangle}{\lVert{\tilde{X}_1}\rVert_2 \lVert{\tilde{X}_2}\rVert_2}. \end{align*}

By the law of large numbers, $d^{-1/2}\lVert{\tilde{X}_i}\rVert_2 \xrightarrow{\mathrm{P}} 1$ for $i = 1,2.$ Combining with the central limit theorem in (3.1) and using Slutsky’s lemma, we get

(3.2) \begin{align} \sqrt{d} \left\langle X_1,X_2 \right\rangle \Rightarrow \mathcal{N}(0,1) \end{align}

as $d \rightarrow \infty.$ The second claim then follows from a similar argument.

Denote by $\mathbb{P}_{n,d}$ the law of n independent d-dimensional standard Gaussian vectors. Let $\tilde{\mathbf{X}} = (\tilde{X}_1,\ldots,\tilde{X}_n ) \sim \mathbb{P}_{n,d}$ , and recall that $X_i \, :\!= \, \tilde{X}_i / \lVert{\tilde{X}_i}\rVert$ is distributed uniformly on $\mathbb{S}^{d-1}$ . For any $1 \leq m \leq n$ , define the events

\begin{align*} \tilde{\mathcal{E}}(m,d,p) &= \bigcap_{1 \le i\neq j\le m} \left\{ \left\langle \tilde{X}_i,\tilde{X}_j \right\rangle \ge \tilde t_{p} \right\}\!,\\[3pt] \mathcal{E}(m,d,p) &= \bigcap_{1 \le i\neq j\le m} \left\{ \left\langle X_i,X_j \right\rangle \ge t_{p} \right\}\!,\end{align*}

where $\tilde t_{p}$ and $t_{p}$ are as defined earlier. The following lemma establishes a relationship between the probabilities of the two events $\tilde{\mathcal{E}}$ and $\mathcal{E}$ using the coupling described above.

Lemma 2. For fixed $p < 1/2$ and any small $\delta>0$ , there exist constants $c_{\delta}$ and $\Delta_{\delta}$ , where $c_{\delta}$ and $\Delta_{\delta}$ both go to 0 as $\delta$ goes to 0, and $p < q < p+ \Delta_{\delta}$ such that the following inequalities hold:

(3.3) \begin{align} \mathbb{P}_{n,d}(\tilde{\mathcal{E}}(n,d,p))\le \exp({-}c_{\delta} dn)+2^n\mathbb{P}_{n,d}(\mathcal{E}((1-\delta)n,d,q)), \\[-10pt] \nonumber \end{align}

(3.4) \begin{align} \mathbb{P}_{n,d}(\mathcal{E}(n,d,p))\le \exp({-}c_{\delta} dn)+2^n\mathbb{P}_{n,d}(\tilde{\mathcal{E}}((1-\delta)n,d,q)). \\[10pt] \nonumber \end{align}

Proof. The proofs of (3.3) and (3.4) follow from similar arguments, and we present the details for only (3.3). Note that we can write

\begin{align*} \tilde{\mathcal{E}}(n,d,p) &= \bigcap_{1 \le i\neq j\le n} \left\{ \left\langle \tilde{X}_i,\tilde{X}_j \right\rangle \ge \tilde t_{p} \right\}\\[3pt] &= \bigcap_{1 \le i\neq j\le n} \left\{ \left\langle \frac{\tilde{X}_i}{\lVert{\tilde{X}_i}\rVert},\frac{\tilde{X}_j}{\lVert{\tilde{X}_j}\rVert} \right\rangle \ge \frac{\tilde t_{p}}{\lVert{\tilde{X}_i}\rVert\lVert{\tilde{X}_j}\rVert} \right\}\\[3pt] &= \bigcap_{1 \le i\neq j\le n} \left\{ \left\langle X_i,X_j \right\rangle \ge t_{p}\cdot\frac{\tilde t_{p}}{t_{p}}\cdot \frac{1}{\lVert{\tilde{X}_i}\rVert\lVert{\tilde{X}_j}\rVert} \right\}. \end{align*}

By Lemma 1, $\tilde t_{p}/t_{p}\sim d$ . Now, suppose for some subset $V \subseteq [n]$ that we have $\lVert{\tilde{X}_i}\rVert \ge (1+\delta)\sqrt{d}$ for all $i \in V$ . Assuming without loss of generality that $V = [m]$ , where $m = |V|$ , if the event

\begin{align*} \bigcap_{1 \le i\neq j\le n} \left\{ \left\langle \tilde{X}_i,\tilde{X}_j \right\rangle \ge \tilde t_{p} \right\} \cap \bigcap_{1 \le i\le m} \big\{ \lVert{\tilde{X}_i}\rVert \ge (1+\delta)\sqrt{d} \big\} \end{align*}

holds, then we also have

\begin{align*} \bigcap_{1 \le i\neq j\le m} \left\{ \left\langle X_i,X_j \right\rangle \ge t_q \right\} \end{align*}

holds for a new threshold $t_q = (1+\delta)^{-2} t_p(1 + o(1))$ , where $p < q < p+\Delta_{\delta}$ , which implies that

\begin{align*} \mathbb{P}_{n,d} \bigg( \tilde{\mathcal{E}}(n,d,p) \cap \bigcap_{1 \le i\le m} \big\{ \lVert{\tilde{X}_i}\rVert \ge (1+\delta)\sqrt{d} \big\} \bigg) \le \mathbb{P}_{n,d}\left(\mathcal{E}(m,d,q) \right). \end{align*}

Thus, to obtain (3.3), it suffices to show that we can take the subset V above to be of size $\delta n$ . To see that, first note that for a Gaussian vector $\tilde{X}$ , its length $\lVert{\tilde{X}}\rVert$ satisfies

\begin{align*}\lVert{\lVert{\tilde{X}}\rVert -\sqrt d}\rVert_{\psi_2}\le C, \end{align*}

where $\lVert{\cdot}\rVert_{\psi_2}$ is the sub-Gaussian norm (see Theorem 3.1.1 in [Reference Vershynin25]). Thus, for a single Gaussian vector $\tilde{X}$ and any $\delta > 0$ , we have $\mathbb{P}(\lVert{\tilde{X}}\rVert>(1+\delta)\sqrt d)\le \exp({-}Cd)$ for some constant C that depends only on $\delta$ . A simple binomial concentration gives that the probability of the event $\mathcal{B}_{n,\delta} \, :\!= \, \{ \#\{i\,:\,\lVert{\tilde{X}_i}\rVert\ge(1+\delta)\sqrt d\}\ge\delta n\}$ is upper-bounded by

\begin{align*}\mathbb{P}(\mathcal{B}_{n,\delta})\le \exp({-}Cd\delta n) = \exp({-}cdn), \end{align*}

where $c >0$ is again a constant that depends only on $\delta.$ Let $\mathcal J$ denote all the subsets of [n] with size $\lfloor (1-\delta)n \rfloor$ . A union bound gives

\begin{align*} \mathbb{P}_{n,d}(\tilde{\mathcal{E}}(n,d,p)) &\le \mathbb{P}_{n,d} ( \tilde{\mathcal{E}}(n,d,p) \cap \mathcal{B}_{n,\delta} ) + \mathbb{P}_{n,d}\big(\tilde{\mathcal{E}}(n,d,p) \cap \mathcal{B}_{n,\delta}^c \big)\\[3pt] &\le \exp({-}cd n)+\sum_{I\in\mathcal J}\mathbb{P}_{n,d}\bigg(\tilde{\mathcal{E}}(n,d,p) \cap \bigcap_{i\in I} \big\{ \lVert{\tilde{X}_i}\rVert \ge (1+\delta)\sqrt{d} \big\}\bigg)\\ &\le \exp({-}cdn)+2^n\cdot\mathbb{P}\bigg(\tilde{\mathcal{E}}(n,d,p) \cap \bigcap_{i \leq \lfloor (1-\delta)n \rfloor} \big\{ \lVert{\tilde{X}_i}\rVert \ge (1+\delta)\sqrt{d} \big\}\bigg)\\[3pt] &\le \exp({-}cdn)+2^n\cdot\mathbb{P}_{n,d}(\mathcal{E}((1-\delta)n,d,q) ) \end{align*}

as required.

Similarly, we obtain the following lemma, which uses the coupling to obtain a relationship between the probabilities of the edge-deviation events in the two models. For any $1\le m\le n$ , define the events

\begin{align*} \tilde{\mathcal{I}}_{\varepsilon}(m,d,p)=\left\{\left\langle \tilde{X}_i,\tilde{X}_j \right\rangle\ge\tilde t_{p}, \text{ for at least } (1+\varepsilon)p\binom{m}{2} \text{ pairs of } 1\le i < j\le m\right\}\!,\\[3pt] \mathcal{I}_{\varepsilon}(m,d,p)=\left\{\left\langle X_i,X_j \right\rangle\ge t_{p}, \text{ for at least } (1+\varepsilon)p\binom{m}{2} \text{ pairs of } 1\le i < j\le m\right\}\!.\end{align*}

Lemma 3. For fixed $p< 1/2$ , $\varepsilon>0$ , and any small $\delta > 0$ , there exist constants $c_{\delta}$ and $\Delta_{\delta}$ , where $c_{\delta}$ and $\Delta_{\delta}$ both go to 0 as $\delta$ goes to 0, $p < q < p + \Delta_{\delta}$ and $0 < \varepsilon' < \varepsilon$ such that the following inequalities hold:

(3.5) \begin{align} \mathbb{P}(\tilde{\mathcal{I}}_{\varepsilon}(n,d,p))<\exp({-}c_{\delta} dn)+2^n\mathbb{P}(\mathcal{I}_{\varepsilon'}((1-\delta)n,d,q)), \\[-32pt] \nonumber \end{align}

(3.6) \begin{align} \mathbb{P}(\mathcal{I}_{\varepsilon}(n,d,p)) <\exp({-}c_{\delta} dn)+2^n\mathbb{P}(\tilde{\mathcal{I}}_{\varepsilon'}((1-\delta)n,d,q)). \end{align}

The proof of this lemma is identical to that for Lemma 2, and we omit the details. Although Lemmas 2 and 3 are not tight, they allow us to estimate $\mathbb{P}(\mathcal{E})$ and $\mathbb{P}(\tilde{\mathcal{E}})$ (and similarly $\mathbb{P}(\mathcal{I}_{\varepsilon})$ and $\mathbb{P}(\tilde{\mathcal{I}}_{\varepsilon})$ ) together, since the additive error term $\exp({-}cdn)$ and the multiplicative factor $2^n$ are not comparable to the leading-order terms for the clique probabilities.

3.2. Geometric tools

In this section, we introduce symmetric rearrangement, the core geometric tool used to establish the upper bounds in our theorems. While the definitions are borrowed from [Reference Draghici12] (see also [Reference Baernstein3] for a comprehensive treatment), we restate them here for the sake of completeness. The main idea is to use measure-preserving transformations to transform arbitrary, measurable subsets of the sphere into spherical caps, defined below.

Spherical caps. For a point $\boldsymbol{v} \in \mathbb{S}^{d-1}$ and $a \in [0,1]$ , a spherical cap centered at $\boldsymbol{v}$ with measure a, denoted by $\mathcal{A}_{\boldsymbol{v}}^a$ , is the subset of $\mathbb{S}^{d-1}$ given by

\begin{align*} \mathcal{A}_{\boldsymbol{v}}^{a} = \big\{\boldsymbol{w} \in \mathbb{S}^{d-1} \,:\, \langle \boldsymbol{w},\boldsymbol{v} \rangle \geq h(a) \big\}, \end{align*}

where the altitude of the spherical cap, $h(a) \in [{-}1,1]$ , is chosen such that $\mu(\mathcal{A}_{\boldsymbol{v}}^a) = a$ (see Figure 1) Recall that $\mu = \mu_{\mathrm{S}}^{d-1}$ is the uniform probability measure on $\mathbb{S}^{d-1}$ . By definition, the cap centered at $\boldsymbol{v}$ with measure p is the neighborhood of a vertex located at $\boldsymbol{v}$ in the SRGG $\mathcal{G}_{\mathrm{S}}(n,p)$ . With this notation, there is an edge between two vertices i and j if and only if $X_i$ lies in $\mathcal{A}^p_{X_j}$ and vice versa.

Figure 1.

A spherical cap centered at $\boldsymbol{v}$ with measure a and height h(a).

Let $f_d(x)$ be the density function of a one-dimensional marginal of $\mu_{\mathrm{S}}^{d-1}$ , given by

\begin{align*}f_d(x) = \frac{\Gamma(d/2)}{\Gamma((d-1)/2)\sqrt{\pi}} (1 - x^2)^{(d-3)/2}, \end{align*}

and define $\Psi_{d}\left(u\right) \, :\!= \,\int_{u}^{1}f_d(x)\,\mathrm{d}x$ to be the corresponding tail distribution function. Then $h(a)=\Psi_{d}^{-1}\left(a\right)$ and $t_{p,d}=\Psi_{d}^{-1}\left(p\right)$ . If the dimension is clear from the context, we drop d from the notation and write $\Psi\left(p\right)$ and $\Psi^{-1}\left(p\right)$ .

Symmetric rearrangement of a subset. We associate with $\mathbb{S}^{d-1}$ a canonical center $\mathbf{e} = (1,0,\ldots,0)$ . Given a measurable subset $R \subset \mathbb{S}^{d-1}$ , the symmetric rearrangement of R, denoted by $R^\bullet$ , is a spherical cap centered at $\mathbf{e}$ that has the same measure as R does, i.e. $R^\bullet = \mathcal{A}_{\mathbf{e}}^{\mu(R)}$ .

Symmetric rearrangement of a function. Let $f \,:\, \mathbb{S}^{d-1} \rightarrow \mathbb{R}_+$ be a non-negative real-valued measurable function. The symmetric rearrangement (also called symmetric decreasing rearrangement in the references in this section) of f is defined to be a function $f^\bullet\,:\, \mathbb{S}^{d-1} \rightarrow \mathbb{R}_+$ satisfying

\begin{align*}\mu\big(\big\{\boldsymbol{x} \in \mathbb{S}^{d-1}\,:\, f^\bullet(x) \ge t \big\}\big)=\mu\big(\big\{\boldsymbol{x} \in \mathbb{S}^{d-1}\,:\, f(x) \ge t \big\}\big) \end{align*}

for each $t > 0$ . Further, it is constant on each slice $\{ \boldsymbol{x} \in \mathbb{S}^{d-1} \,:\, \left\langle \boldsymbol{x},\mathbf{e} \right\rangle = h\}$ , $-1 \le h \le 1$ , and is non-decreasing in h. For a rigorous definition of $f^\bullet$ , see Subsections 1.6 and 7.1 in [Reference Baernstein3]. It is easy to see that for any measurable subset $R \subseteq \mathbb{S}^{d-1}$ , the symmetric rearrangement of its indicator function is equivalent to the indicator of $R^\bullet$ .

In this section, we prove two propositions (Propositions 1 and 2) that are immediate corollaries of Theorem 2.2 in [Reference Draghici12], restated below. Intuitively, it says that certain functionals of functions are maximized by their symmetric rearrangements. To state it formally, let $AL_2(\mathbb{R}_{+}^2)$ be the set of continuous functions $\psi\,:\, \mathbb{R}_{+}^2\to\mathbb{R}_{+}$ satisfying that for every $x_1<x_2$ and $y_1 < y_2$ ,

(3.7) \begin{equation}\psi(x_1,y_2)+\psi(x_2,y_1)\leq\psi(x_1,y_1)+\psi(x_2,y_2),\end{equation}

and $\psi$ vanishes on the boundary, i.e. $\left.\psi\right|_{x_i=0}=0$ for $i=1,2$ . A continuous function $\psi\,:\,\mathbb{R}_{+}^{n}\to\mathbb{R}_{+}$ is said to be in $AL_2(\mathbb{R}_{+}^n)$ if after any $n-2$ coordinates are fixed, $\psi$ is in $AL_2(\mathbb{R}_{+}^2)$ in the remaining two coordinates. Note that for any $\psi\in C^2(\mathbb{R}_{+}^n)$ , we have that $\psi$ satisfies (3.7) if and only if $\partial_i\partial_j\psi\ge 0$ for every $i\neq j$ .

Theorem 5. ([Reference Draghici12], Theorem 2.2.) Let $M=\mathbb{S}^{d-1}$ , $f_i\,:\,M\to\mathbb{R}_+$ be n non-negative functions, $\psi$ be a continuous function in $AL_2(\mathbb{R}_{+}^n)$ , and $K_{i,j}\,:\,\mathbb{R}_+\to\mathbb{R}_+,1 \le i < j \le n,$ be increasing functions. Let

\begin{align*}I[f_1,\ldots,f_n] \, :\!= \,\int_{M^n}\psi(f_1(X_1),\ldots,f_n(X_n))\prod_{i < j}K_{i,j}(\langle X_i,X_j \rangle) \,\mathrm{d}\mu(X_1)\ldots \,\mathrm{d}\mu(X_n), \end{align*}

where $\mathrm{d}\mu$ is the uniform measure on M. Then we have

\begin{align*}I[f_1,\ldots, f_n]\le I[f_1^\bullet,\ldots, f_n^\bullet]. \end{align*}

Using this theorem, we establish two results for SRGGs. Recall that for two edge-weighted graphs $H_1$ and $H_2$ on the same node set, we write $H_1 \leq H_2$ if and only if $w^{H_1}_{i j} \leq w^{H_2}_{i j}$ for all $i\neq j$ . The following proposition states that for any fixed edge-weighted graph $H_0$ and an edge-weighted RGG H, the probability of the event $\{H\ge H_0\}$ under constraints $X_i\in A_i$ is optimized when the $A_i$ ’s are spherical caps centered at the same point.

Proposition 1. Let $A_i \subset \mathbb{S}^{d-1}$ , $i \in [n]$ , be measurable, and let $A_i^\bullet$ be their symmetric rearrangements. Let $H \sim \mathcal{H}_{\mathrm{S}}(n)$ . Then for any edge-weighted graph $H_0$ on the same node set [n],

(3.8) \begin{equation} \mathbb{P}\Bigg(\{ H \geq H_0 \} \cap\bigcap_{i=1}^n\{X_i\in A_i\}\Bigg)\le\mathbb{P}\Bigg(\{ H \geq H_0 \} \cap\bigcap_{i=1}^n\{X_i\in A_i^\bullet\}\Bigg) . \end{equation}

Proposition 2. Let f be a non-negative function on $\mathbb{S}^{d-1}$ , and let $X_1,\ldots,X_n$ be i.i.d. uniformly on $\mathbb{S}^{d-1}$ . Then for any $0\le p\le 1$ and $\theta\ge 0$ , we have

\begin{align*}\mathbb{E}\ {\exp}{\bigg({\theta}{\bigg({\sum_{i=1}}^{n}f(X_i)+{\sum_{i < j}}\mathrm{1}{\left\{\left\langle X_i,X_j \right\rangle\ge t_{p}\right\}}\bigg)}\bigg)}\le\mathbb{E} \ {\exp}{\bigg({\theta}{\bigg({\sum_{i=1}}^{n}f^\bullet(X_i)+{\sum_{i < j}}\mathrm{1}{\left\{\left\langle X_i,X_j \right\rangle\ge t_{p}\right\}}\bigg)}\bigg)}. \\[-12pt] \end{align*}

3.3. Proof outline

The estimation of the probability of the RGGs being a complete graph and of the edge deviation events follows a similar approach. Instead of individually proving Theorems 1 and 2 (respectively Theorems 3 and 4), we use the coupling lemmas established in Subsection 3.1 to reduce the analysis to only one of the two models. For some bounds, the spherical model turns out to be simpler to handle, whereas for others, we work with the Gaussian model.

The lower bounds for the probability of observing a complete graph are proved in Subsection 4.1. We first obtain an Erdős–Rényi-type lower bound, $p^{\binom{n}{2}}$ , for the spherical model using a purely geometric argument. Note that this lower bound does not depend on the dimension d. The remaining bounds in (2.2) and $(2.5)$ are proved by considering the Gaussian model, which is easier to handle with our method. To obtain these bounds, we consider the ‘bias’ event that the first coordinates of all the vectors $\tilde{X}_1, \ldots,\tilde{X}_n$ are larger than $c\sqrt[4]{d\log n}$ for some constant $c > 0$ . Conditioned on this event, we show that the GRGG is a clique with a probability bounded away from 0. We apply a similar idea to establish a lower bound on the edge deviation probability (see Subsection 5.1).

The upper bounds are proved in Subsection 4.2 and are more involved. We observe that conditioned on the GRGG being a complete graph, the statistic $S=\sum_{i\neq j}\langle \tilde{X}_i,\tilde{X}_j \rangle$ is atypically large. This statistic is easier to handle since it is the sum of products of independent standard Gaussian random variables, and we use a Bayesian argument to get one upper bound. We obtain another upper bound by considering the SRGG on n vertices to be obtained by a graph process, where the vertices are added one at a time. This gives us a corresponding subset-valued random process $(A_k)_{k \ge 0}$ starting from $A_0 = \mathbb{S}^{d-1}$ , and conditioned on $X_{1},\ldots,X_{k}$ , $A_k$ is the subset of $\mathbb{S}^{d-1}$ where $X_{k+1}$ can be in so that the SRGG on the first $k+1$ vertices is still a complete graph. By construction, $A_{k+1} = A_k \cap \mathcal{A}^p_{X_{k+1}}$ . We use symmetric rearrangements of subsets to transform the process $(A_k)_{k \ge 0}$ to a spherical-cap-valued random process. This reduced process is more tractable, and we prove one of the bounds in Theorems 1 and 2 by analyzing how the caps shrink with the arrival of each new vertex.

For the edge deviation event $\mathcal{I}_{\varepsilon}$ , we first obtain a bound on the moment-generating function (MGF) of the number of edges in the RGG. Defining

\begin{align*}f_k(\! \cdot \!) = \sum_{i=1}^{k} \mathrm{1}_{\mathcal{A}^p_{X_i}}(\! \cdot \!), \end{align*}

we can write the number of edges in the SRGG as $|E(G)| = \sum_{i=1}^n f_{i-1}(X_i)$ . To get an upper bound on the MGF of $|E(G)|$ , we use symmetric rearrangement of functions to transform $f_k$ into a more tractable process, and then bound the MGF of $\lvert E(G) \rvert$ by the MGF of this reduced process. Use of the exponential Markov’s inequality then completes the proofs.

4.1. Lower bounds

In this section, we obtain the lower bounds in Theorems 1 and 2. The three different bounds in the exponent are derived via different techniques. First, we prove a lower bound that does not depend on the dimension d. As a consequence, we see that the clique probability for the SRGG is at least as large as that for the Erdős–Rényi graph, which matches the intuition that the RGGs are more clustered than the Erdős–Rényi graph.

Proposition 3 For all $n,d \ge 2$ and $0\le p\le\frac{1}{2}$ ,

\begin{align*}\mathbb{P}(\mathcal{E})\ge p^{\binom{n}{2}}\ge\exp({-}cn^2). \end{align*}

We prove the above proposition by using the following result for the spherical model. We drop the subscript and superscript from $\mu_{\mathrm{S}}^{d-1}$ for simplicity.

Lemma 4. Let $\mu$ denote the uniform probability measure on $\mathbb{S}^{d-1}$ . Suppose $A\subset \mathbb{S}^{d-1}$ is convex, and $\boldsymbol{x} \in A$ . Then

\begin{align*}\mu\big(A\cap\mathcal{A}_{\boldsymbol{x}}^p\big) \ge p\cdot\mu(A).\end{align*}

Proof. Recall that $\Psi\left(x\right)=\mathbb{P}(X_1^{(1)}>x)$ is the tail distribution function of a one-dimensional marginal of $\mu$ . We construct a contraction mapping $\varphi=\varphi_{p,x} \,:\,\mathbb{S}^{d-1} \setminus \{-x\}\to\mathcal{A}_{\boldsymbol{x}}^p$ as follows. For every $y\in\mathbb{S}^{d-1} \setminus \{-x\}$ , set $\varphi_{p,x}(y)$ to be the unique point z on the geodesic segment connecting x and y such that $\left\langle x,z \right\rangle=\Psi^{-1}\left(p\cdot \Psi\left(\left\langle x,y \right\rangle\right)\right)$ . Then $\mu \circ \varphi=p\cdot\mu$ , and since A is convex with $x \in A$ , $\varphi(A)\subset A$ . So we immediately conclude that

\begin{align*}\mu\big(A\cap\mathcal{A}_{\boldsymbol{x}}^p\big)\ge\mu(\varphi(A))=p\cdot\mu(A). \end{align*}

Proof of Proposition 3. Define the sets $A_k = \bigcap_{i=1}^k \mathcal{A}_{X_i}^p$ , and consider the events

\begin{align*}\mathcal{E}_k = \bigcap_{1 \leq i \neq j \leq k}\{\left\langle X_i,X_j \right\rangle\ge t_{p} \}, \ 1 \leq k \leq n. \end{align*}

Note that $\mathcal{E}_n = \mathcal{E}$ , and

\begin{align*}\mathbb{P}(\mathcal{E}) = \prod_{i=1}^{n-1} \mathbb{P}(\mathcal{E}_{i+1}|\mathcal{E}_{i}). \end{align*}

Further, observe that $\mathbb P(\mathcal E_{k+1}|\mathcal E_k)=\mathbb E[X_{k+1} \in A_k |\mathcal E_k] =\mathbb E[\mu(A_{k})|\mathcal E_k]$ . Using Lemma 4 recursively, we obtain $\mathbb E[\mu(A_{k})|\mathcal E_k] \ge p^k$ , which we plug into the previous equation to conclude that

\begin{align*}\mathbb{P}(\mathcal{E}) \ge p^{\binom{n}{2}} \ge p^{n^2}. \end{align*}

Note that the result above does not depend on d. But for k large enough, a typical $A_k$ is too ‘small’, in the sense that $A_{k+1}$ has nearly the same measure as $A_k$ instead of $p \mu(A_k)$ . We obtain a dimension-dependent bound in this regime by introducing a biasing argument, where we condition on the event that all the points have a slightly large first coordinate. The technique can be used in both the spherical case and the Gaussian case. We choose the Gaussian case for simplicity.

Proposition 4. There exists a constant $C>0$ such that for all $n,d\ge 2$ and $\log n < d$ ,

\begin{align*}\mathbb{P}(\tilde{\mathcal{E}})\ge \frac{1}{2}\exp({-}C n \sqrt{d\log n}). \end{align*}

Proof. Suppose $\tilde{X}_i=(\tilde{X}_i^{(1)},\ldots,\tilde{X}_i^{(d)})$ , where the $\tilde{X}_i^{(k)}$ ’s are i.i.d. standard Gaussian random variables. For any constant $C > 0$ , define the biased event

\begin{align*}\mathcal B_C \, :\!= \,\bigcap_{i=1}^n\big\{\tilde{X}_i^{(1)}\ge (\tilde t_{p}+C\sqrt{d\log n})^{1/2}\big\}. \end{align*}

Recall that the tail of the standard Gaussian distribution satisfies $\bar \Phi\left(x\right)\ge ({1}/{10x})\mathrm{e}^{-x^2/2} \text{for all }$ $x \geq 2$ (see Proposition 2.1.2 in [Reference Vershynin25]), the $\tilde{X}_i^{(1)}$ ’s are independent, and $\tilde t_{p} = (\bar \Phi^{-1}\left(p\right)+o(1))\sqrt d$ , so we have

\begin{align*}\mathbb P(\mathcal B_C)=\bar \Phi\big(\big(\tilde t_{p}+C\sqrt{d\log n}\big)^{1/2}\big)^n\ge\exp({-}Cn\sqrt{d\log n}). \\[-25pt] \end{align*}

Conditionally on $\mathcal B_C$ happening, $\tilde{\mathcal{E}}$ fails only if

\begin{align*}\sum_{\ell=2}^{d}\tilde X_i^{(\ell)}\tilde X_j^{(\ell)}<\tilde t_{p}-\tilde X_i^{(1)}\tilde X_j^{(1)}\le -C\sqrt{d\log n} \end{align*}

for some $i,j\in[n]$ . Since $(\tilde{X}_i^{(\ell)}\tilde{X}_j^{(\ell)})_{2\le \ell \le d}$ are independent, mean zero, subexponential random variables, we can apply Bernstein’s inequality (see Theorem 2.8.1 in [Reference Vershynin25]) to get

\begin{align*}\mathbb P\left(\left|\sum_{\ell=2}^{d}\tilde X_i^{(\ell)}\tilde X_j^{(\ell)}\right|\ge C\sqrt{d\log n} \right)\le 2\exp\big[{-}c\min(C^2\log n,C\sqrt{d\log n})\big]. \end{align*}

For $\log n < d$ and appropriately chosen constant C, the right-hand side above is bounded by $2n^{-3}$ . Then, by a union bound on all possible pairs (i, j), we have

\begin{align*}\mathbb{P}(\tilde{\mathcal{E}}|\mathcal B_C)\ge 1-\binom{n}{2}2n^{-3}\ge \frac{1}{2}. \end{align*}

Combining the above two inequalities, we get

\begin{align*}\mathbb{P}(\tilde{\mathcal{E}}) = \mathbb{P}(\tilde{\mathcal{E}} | \mathcal B_C)\mathbb{P}(\mathcal B_C) \ge \frac{1}{2}\exp({-}C n \sqrt{d\log n}), \end{align*}

which completes the proof.

If n is exponentially large in d, then the union bound used in the proof above will be redundant, and we can establish a better bound by adding a small bias to all coordinates.

Proposition 5. There exists a constant $C>0$ such that for all $n,d\ge 2$ ,

\begin{align*}\mathbb{P}(\tilde{\mathcal{E}})\ge\exp({-}C nd). \end{align*}

Proof. Consider a different event

\begin{align*}\mathcal E_0' \, :\!= \,\bigcap_{\substack{1 \le i\le n\\[3pt] 1 \le \ell \le d}} \big\{\tilde{X}_i^{(\ell)}\ge \big(\tilde t_{p}/d\big)^{1/2}\big\}, \end{align*}

which immediately implies $\tilde{\mathcal{E}}$ . Recall that $\tilde t_{p}/d=O(d^{-1/2})$ , so we have

\begin{align*}\mathbb{P}(\tilde{\mathcal{E}})\ge\bar \Phi\big(\big(\tilde t_{p}/d\big)^{1/2}\big)^{nd}\ge 2^{-(1+o(1))nd}\ge \exp({-}Cnd). \end{align*}

Combining the results of Propositions 3, 4, and 5 via the coupling result (Lemma 2) gives us the desired lower bounds in Theorems 1 and 2.

4.2. Upper bounds

We can infer from the proof of Proposition 4 that in some regimes (e.g. $d\gtrsim \sqrt n$ ) the event $\tilde{\mathcal{E}}$ happens if there is a small bias for a majority of the Gaussian vectors. To capture a similar phenomenon from a macroscopic perspective, we introduce a statistic $S \, :\!= \,\sum_{1\le i\neq j\le n}\left\langle \tilde{X}_i,\tilde{X}_j \right\rangle$ . The following lemmas cover some properties of this statistic.

Lemma 5. There exists a constant $c_1=c_p>0$ such that for all $n,d\ge 2$ ,

\begin{align*}\mathbb E[S|\tilde{\mathcal{E}}]\ge c_1n^2\sqrt d. \end{align*}

Proof. If $p < 1/2$ , we can deduce from Lemma 1 that

\begin{align*}\mathbb{E}[S|\tilde{\mathcal{E}}]\ge (n^2-n)\tilde t_{p}\ge c_1n^2\sqrt d. \end{align*}

For the case $p=1/2$ , $\tilde t_{p} = 0$ , and we use a geometric argument to obtain the result. Note that in this case, the two RGG models coincide. So we first consider the spherical model and prove that $\mathbb{P}(\mathcal{E}|\left\langle X_1,X_2 \right\rangle=x)$ is monotonically increasing in x. For $0\le x < x' \le 1$ , fix $X_1,X_2$ so that $\left\langle X_1,X_2 \right\rangle=x$ , and choose $X_2'$ to lie on the geodesic connecting $X_1$ and $X_2$ such that $\langle X_1,X_2' \rangle=x'$ . By construction, $X_2'$ is a convex combination of $X_1$ and $X_2$ , so if $X_3,\ldots,X_n$ are sampled uniformly at random on $\mathbb{S}^{d-1}$ , independently of $X_1$ , $X_2$ , and $X_2'$ , the event that $(X_1,X_2,X_3,\ldots,X_n)$ forms a clique implies that $(X_1,X_2',X_3,\ldots,X_n)$ also forms a clique. Then we get

\begin{align*}\mathbb{P}(\mathcal{E}|\left\langle X_1,X_2 \right\rangle=x')\ge \mathbb{P}(\mathcal{E}|\left\langle X_1,X_2 \right\rangle=x). \end{align*}

Recalling that we denote by $f_d$ the density of $\left\langle X_1,X_2 \right\rangle$ , we find that Bayes’s formula gives

\begin{align*} \mathbb{E}[\langle X_1,X_2 \rangle|\mathcal{E}]&=\mathbb{P}(\mathcal{E})^{-1}\int_0^1\mathbb{P}(\mathcal{E}|\left\langle X_1,X_2 \right\rangle=x)xf_d(x)\,\mathrm{d}x\\[3pt] &\ge\mathbb{P}(\mathcal{E})^{-1}\bigg(\int_0^1\mathbb{P}(\mathcal{E}|\left\langle X_1,X_2 \right\rangle=x)f_d(x)\,\mathrm{d}x\bigg)\bigg(\int_0^1xf_d(x)\,\mathrm{d}x\bigg)\bigg(\int_0^1f_d(x)\,\mathrm{d}x\bigg)^{-1}\\[3pt] &=\mathbb{E}[\langle X_1,X_2 \rangle|\langle X_1,X_2 \rangle\ge 0]. \end{align*}

The inequality in the second line follows from Chebyshev’s integral inequality (see Chapter 9 in [Reference Mitrinović, Pečarić and Fink21]). Further, the first two terms in the second line cancel out, and the remaining two terms are equal to the conditional expectation in the final line. Finally, recall that when $p=1/2$ , $t_{p}=\tilde t_{p}=0$ . Hence, under the coupling $X_i=\tilde{X}_i/\lVert{\tilde{X}_i}\rVert$ , the event $\tilde{\mathcal{E}}$ coincides exactly with $\mathcal{E}$ . Moreover, since $\lVert{\tilde{X}_1}\rVert$ and $\lVert{\tilde{X}_2}\rVert$ are independent of $X_1,\dots,X_n$ , we obtain

\begin{align*} \mathbb{E}[\langle \tilde{X}_1,\tilde{X}_2 \rangle|\tilde{\mathcal{E}}]&=\mathbb{E}[\lVert{\tilde{X}_1}\rVert\cdot\lVert{\tilde{X}_2}\rVert\cdot\left\langle X_1,X_2 \right\rangle|\mathcal{E}]=\mathbb{E}\lVert{\tilde{X}_1}\rVert\cdot\mathbb{E}\lVert{\tilde{X}_2}\rVert\cdot\mathbb{E}[\langle X_1,X_2 \rangle|\mathcal{E}]\\[3pt] &\ge\mathbb{E}\lVert{\tilde{X}_1}\rVert\cdot\mathbb{E}\lVert{\tilde{X}_2}\rVert\cdot\mathbb{E}[\langle X_1,X_2 \rangle|\langle X_1,X_2 \rangle\ge 0]= \mathbb{E}[\langle \tilde{X}_1,\tilde{X}_2 \rangle|\langle \tilde{X}_1,\tilde{X}_2 \rangle\ge 0]. \end{align*}

Since $\langle \tilde{X}_1,\tilde{X}_2 \rangle$ has asymptotic distribution $\mathcal N(0,d)$ , the term on the right is bounded below by $c_1\sqrt d$ for some $c_1>0$ . Replacing $(\tilde{X}_1,\tilde{X}_2)$ by any pair $(\tilde{X}_i,\tilde{X}_j)$ , $i \neq j$ , we obtain the same bound. Summing up over all i, j gives $\mathbb{E}[S|\tilde{\mathcal{E}}]\ge c_1n^2\sqrt d$ .

Since S is the sum of i.i.d. subexponential random variables, it concentrates around its mean, and we have the following estimate using Bernstein’s inequality.

Lemma 6. There exists a constant $c_2>0$ such that for all $n,d\ge 2$ and $t>0$ ,

\begin{align*}\mathbb{P}(|S|\ge t)\le 2\exp\left({-}c_2\min\left(\frac{t^2}{n^2d},\frac{t}{n}\right)\right). \end{align*}

Proof. Note that we can decompose the sum as

\begin{align*}S=\sum_{k=1}^{d}\bigg(\sum_{1\le i\neq j\le n}\tilde{X}_i^{(k)}\tilde{X}_j^{(k)}\bigg)\,=\!:\,\sum_{k=1}^{d}Y^{(k)}, \end{align*}

where $Y^{(k)}$ are i.i.d. mean zero random variables with the same distribution as $Y \, :\!= \,(\!\sum_{i=1}^n Y_i)^2-\sum_{i=1}^{n}Y_i^2$ , in which the $Y_i$ ’s are i.i.d. standard normal variables. For every positive integer q, the following moment estimate on Y holds:

\begin{align*}\lVert{Y}\rVert_{L_q}\le\left\|\left(\sum_{i=1}^n Y_i\right)^2\right\|_{L_q}+\sum_{i=1}^{n}\|Y_i^2\|_{L_q}\le 6nq. \end{align*}

This coincides with property (b) in Proposition 2.7.1 in [Reference Vershynin25]. It follows that Y is a subexponential variable with $\lVert{Y}\rVert_{\psi_1}\lesssim n$ , where $\lVert{\cdot}\rVert_{\psi_1}$ is the subexponential norm (see Subsection 2.7 in [Reference Vershynin25]). Then Lemma 6 follows from Bernstein’s inequality.

Lemmas 5 and 6 together give the following upper bound.

Proposition 6. There exists a constant $c>0$ such that for all $n,d\ge 2$ ,

\begin{align*}\mathbb{P}(\tilde{\mathcal{E}})\le \exp({-}c\min(n^2,n\sqrt{d})). \end{align*}

Proof. We use the following extension of Markov’s inequality for the tail of positive random variables. Suppose A is measurable and $\xi$ is a real-valued random variable such that $a =\mathbb{E} [\xi | A]$ is finite. Then for any $b < a$ ,

(4.1) \begin{align} (a - b) \mathbb{P} (A) =\mathbb{E} [(\xi - b) 1_A] \leq \mathbb{E} (\xi-b)^+ \Rightarrow \mathbb{P} (A) \leq \frac{1}{a - b} \mathbb{E} (\xi-b)^+, \end{align}

where $(x)^+ = \max(x,0)$ . Take $A = \tilde{\mathcal{E}}$ , $\xi = S$ , and $b = {a}/{2}$ . By Lemma 5, since $a = \mathbb{E}[S|\tilde{\mathcal{E}}]$ , $b \ge c_1n^2\sqrt d/2$ . With use of Lemma 6 in the first line below, the right-hand side of (4.1) can be bounded by

\begin{align*} \mathbb{E}(S-b)_+&\le\int_{b}^{+\infty}\big(2\exp({-}c_2t/n)+2\exp\big({-}c_2t^2/n^2d\big)\big) \,\mathrm{d}t\\[3pt] &\le\frac{2n}{c_2}\exp({-}c_2b/n)+\frac{n^2d}{cb}\exp\big({-}c_2b^2/n^2d\big)\\[3pt] &\le C(n+\sqrt d)\,{\exp}\big({-}c\min\big(n^2,n\sqrt{d}\big)\big) \end{align*}

for some $c > 0$ . Therefore

\begin{align*}\mathbb{P}(\tilde{\mathcal{E}})\le \frac{1}{a-b}\mathbb{E}[(S-b)_{+}] \le \exp \big({-}(c+o(1))\min\big(n^2,n\sqrt{d}\big) \big). \end{align*}

Another way of dealing with the upper bound is to analyze the convex set-valued random process $A_k$ , defined in the proof of Proposition 3. If we define $H_k$ to be the induced subgraph of $\mathcal{G}_{\mathrm{S}}(n,p)$ on the last k vertices $n-k+1,\ldots,n$ , then we have the inequality

\begin{align*} \mathbb{P}(\mathcal{E})\le\mathbb{P}\bigg(\{H_{n-k}\ge t_{p,d}{\mathbf{1}}_{n-k}\}\cap\bigcap_{i=k+1}^n\{X_i\in A_k\}\bigg).\end{align*}

This reduces analyzing $\mathcal{E}$ to the study of the random process $A_k$ , which is still quite complicated. The following proposition allows us to compare $A_k$ with its symmetric rearrangement $A_k^\bullet$ , which is easier to analyze. Define $\mathcal{C}_0=\mathbb{S}^{d-1}$ , and iteratively define $\mathcal{C}_{k+1} \, :\!= \,(\mathcal{C}_k\cap\mathcal{A}_{X_{k+1}}^p)^\bullet$ . It is a sequence of spherical caps all centered at $\mathbf{e}$ .

Proposition 7. For any $0\le k\le n$ , we have

(4.2) \begin{equation} \mathbb{P}(\mathcal{E})\le\mathbb{P}\Bigg(\{H_{n-k}\ge t_{p,d}{\mathbf{1}}_{n-k}\}\cap\bigcap_{i=k+1}^{n}\{X_i\in\mathcal{C}_k\}\Bigg). \end{equation}

Proof. When $k=0$ , $H_n\ge t_{p,d}{\mathbf{1}}_{n}$ is exactly the event $\mathcal{E}$ , and $\mathcal{C}_0=\mathbb{S}^{d-1}$ , so the two sides of (4.2) are equal. To prove the statement, we show that the right-hand side of (4.2) is non-decreasing in k. Note that for any $0\le k\le n-1$ ,

\begin{align*} &\mathbb{P}\Bigg(\{H_{n-k}\ge t_{p,d}{\mathbf{1}}_{n-k}\}\cap\bigcap_{i=k+1}^{n}\{X_i\in\mathcal{C}_{k}\}\Bigg)\\[3pt] ={}&\mathbb{P}\Bigg(\{H_{n-k-1}\ge t_{p,d}{\mathbf{1}}_{n-k-1}\}\cap\bigcap_{i=k+1}^{n}\big\{X_i\in\big(\mathcal{C}_{k}\cap\mathcal{A}^p_{X_{k+1}}\big)\big\}\Bigg)\\[3pt] \le{}&\mathbb{P}\Bigg(\{H_{n-k-1}\ge t_{p,d}{\mathbf{1}}_{n-k-1}\}\cap\bigcap_{i=k+2}^{n}\big\{X_i\in\big(\mathcal{C}_{k}\cap\mathcal{A}^p_{X_{k+1}}\big)\big\}\Bigg)\\[3pt] \le{}&\mathbb{P}\Bigg(\{H_{n-k-1}\ge t_{p,d}{\mathbf{1}}_{n-k-1}\}\cap\bigcap_{i=k+2}^{n}\{X_i\in\mathcal{C}_{k+1}\}\Bigg). \end{align*}

Here, in the first inequality we drop $Bigg\{X_{k+1}\in(\mathcal{C}_{k}\cap\mathcal{A}^p_{X_{k+1}})\}$ , and in the second inequality, we apply Proposition 1, which completes the proof.

Defining $\eta_k \, :\!= \,\mu(\mathcal{C}_k)$ , and dropping the event $\{H_{n-k}\ge t_{p,d}{\mathbf{1}}_{n-k}\}$ on the right-hand side of (4.2), we get

\begin{equation*} \mathbb{P}(\mathcal{E})\le\mathbb{E}\big(\eta_k^{n-k}\big). \end{equation*}

$(\eta_k)_{k \ge 0}$ is a random, decreasing process, and the following lemma quantifies the difference $\eta_k - \eta_{k+1}$ . Recall that $h(\eta)$ is the altitude of a spherical cap with measure $\eta.$

Lemma 7. For any $\eta \ge 0$ , let $\eta' = \mu_{\mathrm{S}}^{d-1}(\mathcal{A}^\eta_{\mathbf{e}} \cap \mathcal{A}^p_Y)$ , where Y is uniformly distributed on $\mathbb{S}^{d-1}$ . Then there exist $c,c_0>0$ such that for any $\delta\in(0,c)$ and $\eta\in[{\exp}({-}c_0d\delta^2/2),1/2]$ ,

\begin{align*}\mathbb{P}\left(\eta-\eta'\ge c\delta\exp\left({-}\frac{d}{2}(1+3\delta^2)h(\eta)^2\right)\right)\ge 1- \exp({-}d\delta^2/2). \end{align*}

Recall that $\Psi\left(\cdot\right)$ is the tail distribution function of a one-dimensional marginal of $\mu_{\mathrm{S}}^{d-1}$ , i.e. $\Psi(t)=\mathbb{P}(X_1^{(1)}>t)$ , where $X_1^{(1)}$ is the first coordinate of $X_1$ . To prove Lemma 7 we use the following distributional approximation result obtained by Sodin [Reference Sodin24].

Lemma 8. There exist constants $C,C_1,C_2>0$ and a sequence $\varepsilon_d\searrow 0$ such that for all $t \in [0,C]$ ,

\begin{align*}(1-\varepsilon_d)\bar \Phi(\sqrt d t)\,{\exp}\big({-}C_1dt^4\big)\le\Psi(t)\le(1+\varepsilon_d)\bar \Phi(\sqrt dt)\, {\exp}\big({-}C_2dt^4\big). \end{align*}

Proof of Lemma 7. Note that $\eta'$ depends only on $Y^{(1)}$ , the first coordinate of Y. Recall the density of $Y^{(1)}$ is given by

\begin{align*}f_d(x) = \frac{\Gamma(d/2)}{\Gamma((d-1)/2)\sqrt{\pi}} (1 - x^2)^{(d-3)/2}. \end{align*}

From Lemma 8, we know that $\mathbb{P}(Y^{(1)}>\delta)\le \exp({-}d\delta^2/2)$ . Next we show that if $Y^{(1)} \le\delta$ then $\eta-\eta'\ge c\delta\exp({-}({d}/{2})(1+3\delta^2)h(\eta)^2)$ . Since $\eta'$ is monotonically increasing in $Y^{(1)}$ , it suffices to consider $Y=(\delta, -\sqrt{1-\delta^2},0,\ldots,0)$ . Note that $\{(x,y,\ldots)\in\mathbb S^{d-1}\,:\,x>h(\eta),$ $y >\delta x /\sqrt{1-\delta^2}\} \subseteq \mathcal{A}^\eta_{\mathbf{e}} \setminus \mathcal{A}^p_{Y}$ . Further, the two-dimensional marginal of $\mu_{\mathrm{S}}^{d-1}$ on the first two coordinates has density function

\begin{align*}f_d(x,y)=\frac{d-2}{2\pi}(1-x^2-y^2)^{(d-4)/2}. \end{align*}

By direct computation, when $Y^{(1)}\le\delta$ we have

\begin{align*} \mu\big(\mathcal{A}^\eta_{\mathbf{e}}\setminus\mathcal{A}^p_{Y^{(1)}}\big)&\ge\int_{x^2+y^2\le1}\mathrm 1_{\{x>h(\eta), y>\delta/\sqrt{1-\delta^2}x\}}f_d(x,y)\,\mathrm{d}x\,\mathrm{d}y\\[3pt] &\ge cd\int_{h(\eta)}^{1/2}\Bigg(\int_{\delta x/\sqrt(1-\delta^2)}^{\sqrt{1-x^2}}(1-x^2-y^2)^{(d-4)/2}dy\Bigg)\,\mathrm{d}x\\[3pt] &=cd\int_{h(\eta)}^{1/2}(1-x^2)^{(d-3)/2}\left(\int_{\delta x/\sqrt{(1-\delta^2)(1-x^2)}}^1(1-t^2)^{(d-4)/2}\,\mathrm{d}t\right)\,\mathrm{d}x\\[3pt] &\ge cd\int_{h(\eta)}^{1/2}(1-x^2)^{d/2}\delta x(1-2\delta^2x^2)^{d/2}\,\mathrm{d}x\\[3pt] &\ge c\delta(1-(1+2\delta^2)h(\eta)^2)^{d/2}\\[3pt] &\ge c\delta\exp\left({-}\frac{d}{2}(1+3\delta^2)h(\eta)^2\right).\end{align*}

For the last two inequalities to hold, we need $h(\eta)<c'\delta$ for some constant c ^′ small enough. This can be achieved by taking $c_0$ to be sufficiently small in the assumption, which completes the proof.

Using Lemma 7, we obtain the following two rates of decay of the sequence $(\eta_n)_{n \ge 1}$ as n goes to infinity, for different regimes of d.

Proposition 8. For a sufficiently small constant $c>0$ and $\log n \lesssim d \lesssim n^{4/3}$ ,

\begin{align*}\mathbb{P}\left(\eta_n\ge\exp\left({-}c\sqrt{d}\cdot\frac{\log n-\log d^{3/4}}{\sqrt{\log n}}\right)\right) \le \exp ({-}cn\sqrt{d\log n}). \end{align*}

Proof. We first select a constant $0 < c \ll 1$ and $\delta=c\sqrt[4]{\log n/d}$ . Let $I\subset[n]$ contain all indices i such that the first coordinate of $X_i$ is smaller than $\delta$ . Since I is a Bernoulli process with success parameter $p_0 \ge 1- \exp({-}d\delta^2/2)\ge 1- \exp({-}c\sqrt{d\log n})$ ,

\begin{align*}\mathbb{P}(|I|\le n/2)\le\sum_{i=0}^{n/2}p_0^i(1-p_0)^{n-i}\binom{n}{i}\le 2^n(1-p_0)^{n/2}\le \exp({-}cn\sqrt{d\log n}). \end{align*}

Let $N=(\log n-\log d^{3/4})/\sqrt{\log n}$ . On the event $|I|\ge n/2$ we prove $\eta_n<\exp({-}c\sqrt dN)$ . Since $\eta_1=p\le 1/2$ , we may assume $\eta_i\in[{\exp}({-}c\sqrt{d\log n}),1/2]$ for any $1\le i\le n$ . From the proof of Lemma 7, we deduce that for $i\in I$ , $\eta_i-\eta_{i+1}>c\delta\exp({-}({d}/{2})(1+3\delta^2)h(\eta_i)^2).$ Denote $I_k=I\cap\{i\,:\,\eta_i\in(e^{-k-1},e^{-k}]\}$ for any integer $1\le k\le \sqrt{d\log n}$ . Using Lemma 8, we get that for any $i\in I_k$ ,

(4.3) \begin{equation}\mathrm{e}^{-k-1}\le C\exp\left({-}\frac{d}{2}h(\eta_i)^2\right).\end{equation}

Then

\begin{align*}\eta_{i}-\eta_{i+1}\ge c\delta \mathrm{e}^{-(1+3\delta^2)k}, \end{align*}

and therefore

(4.4) \begin{equation}|I_k|\le\left\lceil\frac{\mathrm{e}^{-k}}{c\delta \mathrm{e}^{-(1+3\delta^2)k}}\right\rceil\le 1+\frac{1}{c\delta}\mathrm{e}^{3\delta^2k}.\end{equation}

Summing the above inequality for $0\le k\le c\sqrt{d}N$ gives

\begin{equation*}\sum_{k=0}^{c\sqrt dN}|I_k|\le c\sqrt dN+1+\frac{\mathrm{e}^{3c\delta^2\sqrt dN}}{c\delta(\mathrm{e}^{3\delta^2}-1)}\le \frac{n}{2}. \end{equation*}

The last inequality holds for sufficiently small $c>0$ . Therefore $\eta_n<\exp({-}c\sqrt d N)$ when $\lvert I \rvert\ge n/2$ .

Proposition 9. For sufficiently small constant $c>0$ , and $d \lesssim \log n$ ,

\begin{align*}\mathbb{P}(\eta_n\ge\exp({-}cd) ) \le \exp ({-}cnd). \end{align*}

Proof. The proof is similar to that of Proposition 8. We select a small constant $\delta \ll 1$ , and define I and $I_k$ for $1\le k\le d$ as before. In this regime, I is again a Bernoulli process, but with parameter $p_0\ge1- \exp({-}cd)$ . Therefore $\mathbb{P}(\lvert I \rvert\le n/2)\le \exp({-}cnd)$ . The inequalities (4.3) and (4.4) still hold, and we can sum over k to get that

\begin{align*}\sum_{k=0}^{cd}\lvert I_k \rvert\le 1+cd+\frac{\mathrm{e}^{3c\delta^2d}}{c\delta(\mathrm{e}^{3\delta^2}-1)}\le \frac{n}{2} \end{align*}

holds for a small enough constant c. Thus $\eta_n\le \mathrm{e}^{-cd}$ if $\lvert I \rvert\ge n/2$ .

Finally, we complete the proof of the upper bounds in Theorems 1 and 2. Substituting Proposition 8 into (4.2), when $\log n \lesssim d \lesssim n^{4/3}$ , we obtain

\begin{align*} \mathbb{P}(\mathcal{E})&\le\mathbb{E} \big(\eta_{n/2}^{n/2}\big)\le \mathbb{P}\left(\eta_n\ge\exp\left({-}c\sqrt{d}\cdot\frac{\log n-\log d^{3/4}}{\sqrt{\log n}}\right)\right)\\[3pt]& \quad +\exp\left({-}c\sqrt{d}\cdot\frac{\log n-\log d^{3/4}}{\sqrt{\log n}}\cdot\frac{n}{2}\right) \le \exp\left({-}cn\sqrt{d\log\frac{n^{1-o(1)}}{d^{3/4}}}\right). \end{align*}

Similarly, in the regime $d \lesssim \log n$ , we use Proposition 9 to get

\begin{align*} \mathbb{P}(\mathcal{E})\le\mathbb{E} \big(\eta_{n/2}^{n/2}\big)\le \mathbb{P}\left(\eta_n\ge\exp\left({-}cd\right)\right)+\exp\left({-}cd\cdot\frac{n}{2}\right)\le \exp({-}cnd). \end{align*}

The results above, along with Proposition 6 and Lemma 2, complete the proof of the upper bounds in Theorems 1 and 2.

5.1. Lower bounds

The first lower bound is a corollary of Proposition 3, the Erdős–Rényi-type lower bound for the clique probability. It follows from noting that conditioned on the existence of a large enough clique, the event $\mathcal{I}_{\varepsilon}$ happens with a probability bounded away from zero.

Proposition 10. For all n and $d\ge 2$ ,

\begin{align*}\mathbb{P}(\mathcal{I}_{\varepsilon})\ge \exp\left[{-}\left(\frac{p\log\frac{1}{p}}{2(1-p)}\varepsilon+o(1)\right)n^2\right]. \end{align*}

Proof. Let $\alpha=\sqrt{p\varepsilon/(1-p)}$ , and let $\mathcal{E}_{\left\lceil \alpha n+1 \right\rceil}$ be as defined in the proof of Proposition 4.1. We can infer from the proof that

(5.1) \begin{equation} \mathbb{P}(\mathcal{E}_{\left\lceil \alpha n+1 \right\rceil})\ge p^{\binom{\left\lceil \alpha n+1 \right\rceil}{2}}\ge\exp\left({-}\frac{p\log\frac{1}{p}}{2(1-p)}\varepsilon n^2-n\right). \end{equation}

Note that conditioned on $\mathcal{E}_{\left\lceil \alpha n+1 \right\rceil}$ happening, the connection probability of edges not included in this small clique remains equal to p. That implies if $G \sim \mathcal{G}_{\mathrm{S}}(n,p)$ ,

\begin{align*}\mathbb{E}[\lvert E(G) \rvert|\mathcal{E}_{\lceil \alpha n+1 \rceil}]\ge \binom{\left\lceil \alpha n+1 \right\rceil}{2}+p\left[\binom{n}{2}-\binom{\left\lceil \alpha n+1 \right\rceil}{2}\right]\ge p(1+\varepsilon)\binom{n}{2}+1. \end{align*}

Hence

\begin{align*}\mathbb{P}\left(\lvert E(G) \rvert\ge p(1+\varepsilon)\binom{n}{2}\Big|\mathcal{E}_{\left\lceil \alpha n+1 \right\rceil}\right)\ge\frac{1}{\binom{n}{2}}\left[\mathbb{E}[\lvert E(G) \rvert|\mathcal{E}_{\lceil \alpha n+1 \rceil}]-p(1+\varepsilon)\binom{n}{2}\right]\ge\frac{1}{n^2}. \end{align*}

Combining with (5.1) completes the proof.

For the second lower bound, we apply the biasing argument as we did in the proof of Proposition 4. Again, we prove the result for the Gaussian model and use Lemma 3 to obtain the result for the spherical model.

Proposition 11. For all n and $d\ge 2$ ,

\begin{align*}\mathbb{P}(\tilde{\mathcal{I}}_{\varepsilon})\ge\exp\left[{-}\left(\frac{\bar \Phi^{-1}\left(p\right)-\bar \Phi^{-1}\left(p(1+\varepsilon)\right)}{2}+o(1)\right)n\sqrt d\right]. \end{align*}

Proof. Suppose $\tilde{X}_i=(\tilde{X}_i^{(1)},\ldots,\tilde{X}_i^{(d)})$ . Let $C \, :\!= \,C_{n,d,p,\varepsilon}=\sqrt{\tilde t_{p,d}-\tilde t_{p(1+\varepsilon)+1/n,d-1}}$ , and define the biased event

\begin{align*}\mathcal B_C \, :\!= \,\bigcap_{1 \le i\le n}\big\{\tilde{X}_i^{(1)}>C\big\}. \end{align*}

Then for all $1\le i < j\le n$ we have

\begin{align*}\mathbb{P}(\langle \tilde{X}_i,\tilde{X}_j \rangle\ge \tilde t_{p,d}|\mathcal B_C)\ge \mathbb{P}\left(\sum_{k=2}^{d}\tilde{X}_i^{(k)}\tilde{X}_j^{(k)}\ge\tilde t_{p,d}-C^2\right)=\left(p(1+\varepsilon)+1/n\right) \wedge 1. \end{align*}

Let $G \sim \mathcal{G}_{\mathrm{G}}(n,p)$ . By summing over all i, j, we obtain

\begin{align*}\mathbb{E}[\lvert E(G) \rvert|\mathcal B_C]\ge p(1+\varepsilon)\binom{n}{2}+1. \end{align*}

Similarly to in the proof of Proposition 10, we get

(5.2) \begin{equation} \mathbb{P}\left(\lvert E(G) \rvert\ge p(1+\varepsilon)\binom{n}{2}\Big|\mathcal B_C\right)\ge \frac{1}{n^2}. \end{equation}

Since $1/n \rightarrow 0$ as $n \rightarrow \infty$ , we can deduce from Lemma 1 that

(5.3) \begin{equation} C^2=\tilde t_{p,d}-\tilde t_{p(1+\varepsilon)+1/n,d-1}=\big[\bar \Phi^{-1}(p)-\bar \Phi^{-1}\left(p(1+\varepsilon)\right)+o(1)\big]\sqrt d. \end{equation}

Using the standard estimation for Gaussian tails, we obtain

(5.4) \begin{equation} \mathbb{P}(\mathcal B_C)=\bar \Phi(C)^n\ge\exp\big[{-}(1+o(1))C^2n/2\big]. \end{equation}

Combining (5.2), (5.3), and (5.4) concludes the proof.

Combining Propositions 10 and 11 together with Lemma 3 gives the lower bounds in Theorems 3 and 4.

5.2. Upper bounds

We consider the number of edges $\lvert E(G) \rvert$ as the final term of the following stochastic process. Denote by $\lvert E_k(G) \rvert$ the number of edges between $X_1,\ldots,X_k$ , and define $f_k(x)=\sum_{1\le i\le k}\mathrm 1_{\mathcal{A}^p_{X_i}}(x)$ . Then $f_{k-1}(X_{k})$ counts the number of edges from $X_{k}$ to $X_1,\ldots,X_{k-1}$ , and

\begin{align*}\lvert E_{k}(G) \rvert-\lvert E_{k-1}(G) \rvert=f_{k-1}(X_{k}). \end{align*}

Similarly to the idea in Subsection 4.2, we will use Proposition 2 here to obtain a bound on the MGF of $\lvert E(G) \rvert=\sum_{k=1}^nf_{k-1}(X_k)$ by a sequence of symmetric rearrangements. We start by defining another sequence of functions $(g_k)_{k \ge 0}$ by setting $g_0 \equiv 0$ on $\mathbb{S}^{d-1}$ , and iteratively defining

\begin{equation*}g_{k} \, :\!= \, \big(g_{k-1}+\mathrm 1_{\mathcal{A}^p_{X_k}}\big)^\bullet,\quad 1\le k\le n-1.\end{equation*}

Using these functions, we define an interpolating process

(5.5) \begin{equation}m_k \, :\!= \, \sum_{i=1}^{k}g_{i-1}(X_i)+\sum_{i=k+1}^{n}g_k(X_i)+\sum_{k+1\le i < j\le n}\mathrm{1}\{\langle X_i,X_j \rangle\ge t_{p}\}, \quad 1 \le k \le n. \end{equation}

By definition, we have $m_0 = |E(G)|$ and $m_n = \sum_{k=1}^ng_{k-1}(X_k).$ For each k, the first term in (5.5) corresponds to the symmetric rearrangement of the edges between $X_1, \ldots, X_k$ , the second term corresponds to the symmetric rearrangement of the edges between $X_1,\ldots,X_k$ and $X_{k+1}, \ldots, X_{n}$ , and the final term counts the true edges between $X_{k+1},\ldots,X_{n}$ in G.

Proposition 12. The MGFs of $m_k$ are non-decreasing in k, i.e. for any $\theta\ge 0$ , we have

\begin{align*}\mathbb{E} \exp(\theta\lvert E(G) \rvert)=\mathbb{E} \mathrm{e}^{\theta m_0}\le\mathbb{E} \mathrm{e}^{\theta m_1}\le\cdots\le\mathbb{E} \mathrm{e}^{\theta m_n}. \end{align*}

Proof. It suffices to show that $\mathbb{E} \mathrm{e}^{\theta m_{k-1}}\le\mathbb{E} \mathrm{e}^{\theta m_k}$ for any $1\le k\le n$ . Fix k. Then by first conditioning on $X_1,\ldots,X_k$ , we get

\begin{align*} &\mathbb{E}[\mathrm{e}^{\theta m_{k-1}}|X_1,\ldots,X_k]\\[3pt] &=\exp\left(\theta\sum_{i=1}^{k}g_{i-1}(X_i)\right)\mathbb{E}_{X_{k+1},\ldots,X_{n}}\exp\left(\theta\left(\sum_{i=k+1}^{n}g_{k-1}(X_i)+\sum_{k\le i < j\le n}\mathrm{1}\left\{\left\langle X_i,X_j \right\rangle\ge t_{p}\right\}\right)\right). \end{align*}

Here $\mathbb{E}_{X_{k+1},\ldots,X_{n}}$ means taking expectation over randomness of $X_{k+1},\ldots,X_{n}$ , and we drop the subscript and simply write $\mathbb{E}$ to simplify the notation. Let $f(X)=g_{k-1}(X)+\mathrm{1}_{\mathcal{A}^p_{X_k}}(X)$ , and note that $f^\bullet=g_k$ . By applying Proposition 2, we obtain

\begin{align*} & \ \ \ \ \mathbb{E}\exp\Bigg(\theta\Bigg(\sum_{i=k+1}^{n}g_{k-1}(X_i)+\sum_{k\le i < j\le n}\mathrm 1\{\langle X_i,X_j \rangle\ge t_{p}\}\Bigg)\Bigg)\\[3pt] &=\mathbb{E}\exp\Bigg(\theta\Bigg(\sum_{i=k+1}^{n}f(X_i)+\sum_{k+1\le i < j\le n}\mathrm 1\{\langle X_i,X_j \rangle\ge t_{p}\}\Bigg)\Bigg)\\[3pt] &\le \mathbb{E}\exp\Bigg(\theta\Bigg(\sum_{i=k+1}^{n}f^\bullet(X_i)+\sum_{k+1\le i < j\le n}\mathrm 1\{\langle X_i,X_j \rangle\ge t_{p}\}\Bigg)\Bigg)\\[3pt] & =\mathbb{E}\exp\Bigg(\theta\Bigg(\sum_{i=k+1}^{n}g_{k}(X_i)+\sum_{k+1\le i < j\le n}\mathrm 1\{\langle X_i,X_j \rangle\ge t_{p}\}\Bigg)\Bigg). \end{align*}

Thus

\begin{align*}\mathbb{E}[\mathrm{e}^{\theta m_{k-1}}|X_1,\ldots,X_k]\le\mathbb{E}[\mathrm{e}^{\theta m_{k}}|X_1,\ldots,X_k]. \end{align*}

Taking the expectation over $X_1,\ldots,X_k$ completes the proof.

We complete the proof of Theorems 3 and 4 using the following upper bound on $m_n$ .

Proposition 13. Let $m_n$ be defined as in (5.5). Then

(5.6) \begin{equation} m_n \leq \left(p + p\varepsilon/2\right) \binom{n}{2} \end{equation}

holds with probability at least

\begin{align*} 1-\,{\exp}({-}\min ( c_1(p,\varepsilon)n^2, c_2(p,\varepsilon)n\sqrt{d} )) . \end{align*}

Here $c_1(p,\varepsilon)$ and $c_2(p,\varepsilon)$ are positive constants that depend only on p and $\varepsilon$ .

We first prove Theorem 3 assuming Proposition 13, using the following general lemma on stochastic order. The proof of Proposition 13 is delayed to the end of this section.

Lemma 9. Suppose Y and Y^′ are random variables satisfying $Y,Y'\le 1$ , and for all $\theta\ge 0$ ,

(5.7) \begin{equation} \mathbb{E} \mathrm{e}^{\theta Y}\le\mathbb{E} \mathrm{e}^{\theta Y'}. \end{equation}

Then for all $\delta\ge0$ ,

(5.8) \begin{equation} \log\mathbb{P}(Y\ge\delta)\le\frac{\delta}{2}\log\mathbb{P}\left(Y'\ge\frac{\delta}{2}\right)+\log 2. \end{equation}

Proof. Note that for all $\theta\ge0$ ,

\begin{align*}\mathbb{E} \mathrm{e}^{\theta Y'}=\mathbb{E}\left[\mathrm{e}^{\theta Y'}\mathrm{1}\left\{Y'\ge\frac{\delta}{2}\right\}\right]+\mathbb{E}\left[\mathrm{e}^{\theta Y'}\mathrm{1}\left\{Y'<\frac{\delta}{2}\right\}\right]\le \mathrm{e}^\theta\mathbb{P}\left(Y'\ge\frac{\delta}{2}\right)+\mathrm{e}^{\theta({\delta}/{2})}. \end{align*}

Applying Markov’s inequality, we obtain

\begin{align*} \log\mathbb{P}(Y\ge\delta)&\le\log(\mathrm{e}^{-\theta\delta}\mathbb{E} \mathrm{e}^{\theta Y})\le-\theta\delta+\log\mathbb{E} \mathrm{e}^{\theta Y'}\le -\frac{\theta\delta}{2}+\log\left.\left(1+\mathbb{P}\left(Y'\ge\frac{\delta}{2}\right)\mathrm{e}^{\theta-\frac{\theta\delta}{2}}\right)\right). \end{align*}

We get (5.8) by taking $\theta=-\log\mathbb{P}(Y'\ge {\delta}/{2})\ge 0$ , since

\begin{align*}\log\left.\left(1+\mathbb{P}\left(Y'\ge\frac{\delta}{2}\right)\mathrm{e}^{\theta-({\theta\delta}/{2})}\right)\right)=\log(1+\mathrm{e}^{-({\theta\delta}/{2})})\le\log 2. \end{align*}

Proof of Theorem 3. Let

\begin{align*}Y=\frac{\lvert E(G) \rvert}{\binom{n}{2}}-p, Y'=\frac{m_n}{\binom{n}{2}}-p. \end{align*}

It is clear that $Y,Y'\le 1$ , and they satisfy (5.7) due to Proposition 12. Combining with Proposition 13, we get

\begin{align*}\log\mathbb{P}(Y\ge\varepsilon)\le\frac{\varepsilon}{2}\log\mathbb{P}\left(Y'\ge\frac{\varepsilon}{2}\right)+\log 2\le-\frac{\varepsilon}{2}\min ( c_1(p,\varepsilon)n^2, c_2(p,\varepsilon)n\sqrt{d} )+\log 2. \end{align*}

Note that event $\mathcal{I}_{\varepsilon}$ is exactly $Y\ge\varepsilon$ , so the proof is complete.

For the proof of Proposition 13, it is sufficient to bound each $g_{k-1}(X_{k})$ individually, and then sum over k. We are going to bound an analogue of the MGF and then apply Markov’s inequality. Given a measurable function $g\,:\,\mathbb{S}^{d-1}\to\mathbb{R}$ , a subset $V\subset\mathbb{S}^{d-1}$ , and $\lambda\in\mathbb{R}$ , define

\begin{align*}\mathcal{M}[g;\,V](\lambda) \, :\!= \,\int_{V}\exp(\lambda g(X))\,\mathrm{d}\mu(X). \end{align*}

Let $q=p+p\varepsilon/32$ , and select a constant $a>0$ that satisfies

(5.9) \begin{equation} t_{p,d}-\frac{a^2}{\sqrt d}>\max\left(t_{q,d-1},\left(1-\frac{a^2}{\sqrt d}\right)t_{q,d-1}\right)\end{equation}

for all d sufficiently large. Such an a exists since Lemma 1 indicates a gap of order $\Omega(d^{-1/2})$ between $t_{p,d}$ and $t_{q,d-1}$ . Consider the strip $L_{t}$ , and the complement of a cap $V_{t}$ , defined as

\begin{align*} L_{t} \, :\!= \,\left\{\boldsymbol{w} \in \mathbb{S}^{d-1} \,:\, |\left\langle \boldsymbol{w},\boldsymbol{e} \right\rangle| \le \frac{t}{\sqrt[4]{d}}\right\},\\[3pt] V_{t} \, :\!= \,\left\{\boldsymbol{w} \in \mathbb{S}^{d-1} \,:\, \left\langle \boldsymbol{w},\boldsymbol{e} \right\rangle \le \frac{t}{\sqrt[4]{d}} \right\}.\end{align*}

The key observation is the following lemma.

Lemma 10. Suppose $\lambda\ge 0$ . Then for any function g such that $g=g^\bullet$ almost everywhere, and vector $Y\in L_{a}$ ,

\begin{align*}\mathcal{M}\big[g+\mathrm{1}_{\mathcal{A}^p_Y};\,V_{a}\big](\lambda)\le\big(1-q+q\mathrm{e}^\lambda+2\mathrm{e}^{-a^2\sqrt d/2+O(1)+\lambda}\big)\mathcal{M}[g;\,V_{a}](\lambda). \end{align*}

Proof. Let $S_t=\{X\in\mathbb{S}^{d-1}\,:\,\left\langle X,\boldsymbol{e} \right\rangle=t\}$ be a $(d-2)$ -dimensional slice at t and let $\mu_t$ denote the uniform measure on $S_t$ . We first prove that for all $|t|\le a/\sqrt[4]{d}$ ,

(5.10) \begin{equation} \int_{S_t}\exp\big[\lambda\cdot\mathrm{1}_{\mathcal{A}^p_{Y}}(X)\big]\,\mathrm{d}\mu_t(X)\le1-q+q\mathrm{e}^\lambda. \end{equation}

This is equivalent to showing $\mu_t(S_t\cap\mathcal{A}_Y^p)\le q$ , which can be computed directly. Suppose $Y=(y,\sqrt{1-y^2},0,\ldots,0)$ . Then

\begin{align*}S_t\cap\mathcal{A}_Y^p=\big\{X=(t,u,\ldots)\,:\,ty+u\sqrt{1-y^2}\ge t_{p,d}\big\}. \end{align*}

After scaling by $1/\sqrt{1-t^2}$ , $S_t\cap\mathcal{A}_Y^p$ is a spherical cap on $\mathbb{S}^{d-2}$ with altitude $(t_{p,d}-ty)/\sqrt{(1-y^2)(1-t^2)}$ , and so

\begin{align*} \mu_t\big(S_t\cap\mathcal{A}_Y^p\big)=\Psi_{d-1}\left(\frac{t_{p,d}-ty}{\sqrt{(1-y^2)(1-t^2)}}\right). \end{align*}

Recall that $|t|,|y|\le a/\sqrt[4]{d}$ , and a satisfies (5.9). This is upper-bounded by $\Psi_{d-1}(t_{q,d-1})=q$ , which proves (5.10).

Next we show that the integral on $V_{a}-L_{a}$ is small. For those $t<-a/\sqrt[4]{d}$ , the integral on $V_{a}-L_{a}$ can be bounded by that on $L_{a}$ since g is non-decreasing in the direction $\mathbf{e}$ as

\begin{align*} &\mathcal{M}\big[g+\mathrm{1}_{\mathcal{A}^p_Y};\,V_{a}-L_{a}\big](\lambda) \le \mathrm{e}^\lambda\mathcal{M}[g;\,V_{a}-L_{a}](\lambda)\\[3pt] \le& \mathrm{e}^\lambda \frac{\mu(V_{a}-L_{a})}{\mu(V_{a})}\mathcal{M}[g;\,V_{a}](\lambda)\le 2e^{-a^2\sqrt d/2+O(1)+\lambda}\mathcal{M}[g;\,V_{a}](\lambda). \end{align*}

Here in the last inequality we apply Lemma 8 on $\mu(V_{a}-L_{a})$ . Multiplying (5.10) by the value of g on $S_t$ and integrating over $|t|\le a/\sqrt[4]{d}$ gives

\begin{align*} \mathcal{M}\big[g+\mathrm{1}_{\mathcal{A}^p_Y};\,V_{a}\big](\lambda)&=\mathcal{M}\big[g+\mathrm{1}_{\mathcal{A}^p_Y};\,L_{a}\big](\lambda)+\mathcal{M}\big[g+\mathrm{1}_{\mathcal{A}^p_Y};\,V_{a}-L_{a}\big](\lambda)\\[3pt] &\le\big(1-q+q\mathrm{e}^\lambda+2\mathrm{e}^{-a^2\sqrt d/2+O(1)+\lambda}\big)\mathcal{M}[g;\,V_{a}](\lambda). \end{align*}

Finally, we derive an upper bound on $g_{k-1}(X_{k})$ from Lemma 10, and complete the proof of Proposition 13.

Proof of Proposition 13. Let $\lambda$ and $c_0$ be constants to be determined later, and define

\begin{align*}h\, :\!= \, \min\left(\frac{c_0\sqrt n}{\sqrt[4]{d}},\frac{a}{2}\right). \end{align*}

Define the index set

\begin{align*}I \, :\!= \,\{1\le k\le n\,:\,X_k\notin L_{h}\}. \end{align*}

These vectors $\{X_k\}_{k\in I}$ are atypical and have large contributions to $\mathcal{M}[g_k;\,V_{a}](\lambda)$ . Consider the bad event $\mathcal B \, :\!= \,\{\lvert I \rvert\ge p\varepsilon n/16\}$ of having too many atypical vectors. Its probability can be controlled as follows. By Lemma 8, for a single k,

\begin{align*}\mathbb{P}(X_k\notin L_{h})=2\Psi(h/\sqrt[4]{d})\le \exp({-}\sqrt{d}h^2/2+O(1)). \end{align*}

A union bound gives

\begin{align*}\mathbb{P}(\mathcal B)\le 2^n\cdot\mathbb{P}\left(X_k\notin L_{h} \mbox{ for all } 1\le k\le \frac{p\varepsilon n}{16}\right) &\le2^n\exp\left(\frac{p\varepsilon n}{16}\big({-}\sqrt{d}h^2/2+O(1)\big)\right) \\[3pt] &\le \exp({-}p\varepsilon n\sqrt{d}h^2/64). \end{align*}

Since $g_k = (g_{k-1}+\mathrm{1}_{\mathcal{A}^p_{X_k}})^\bullet$ , we can use Lemma 10 to bound $\mathcal{M}[g_k;\,V_{a}](\lambda)$ as

\begin{equation*} \mathcal{M}[g_k;\,V_{a}](\lambda)\le\mathcal{M}\big[g_{k-1}+\mathrm{1}_{\mathcal{A}^p_{X_k}};\,V_{a}\big](\lambda)\le \begin{cases} (1-q+q\mathrm{e}^\lambda+o(1))\mathcal{M}[g_{k-1};\,V_{a}](\lambda),\qquad k\notin I,\\[3pt] \mathrm{e}^\lambda\mathcal{M}[g_{k-1};\,V_{a}](\lambda),\qquad k\in I.\\[3pt] \end{cases} \end{equation*}

Note that $\mathcal{M}[g_0;\,V_{a}](\lambda)=\mu(V_{a})\le 1$ . We can deduce from above that for all $1\le k\le n$ ,

\begin{align*} \mathcal{M}[g_k;\,V_{a}](\lambda)\le(1-q+q\mathrm{e}^\lambda+o(1))^k\exp\left(\lambda\lvert I\cap\{1,\ldots,k\} \rvert\right). \end{align*}

In particular, on $\mathcal B^c$ , $\lvert I\cap\{1,\ldots,k\} \rvert\le p\varepsilon n/16$ , and thus for all $1\le k\le n$ ,

\begin{align*}\log \mathcal{M}[g_k;\,V_{a}](\lambda)\le k\log(1-q+q\mathrm{e}^\lambda+o(1))+\lambda p\varepsilon n/16. \end{align*}

From here we derive a bound on $g_{k-1}(X_k)$ by using Markov’s inequality. Since $h \leq a/2 = O(1)$ , we have

\begin{align*}\mu(V_{a}-V_{h})\asymp \mu\big(V_{h}^c\big)=\exp({-}\sqrt{d}h^2/2+O(1)). \end{align*}

Then for all $k\notin I$ , $X_k\in L_{h}$ and

\begin{align*}\mathcal{M}[g_{k-1};\,V_{a}](\lambda)\ge \mathcal{M}[g_{k-1};\,V_{a}-V_{h}](\lambda)\ge\mu(V_{a}-V_{h})\mathrm{e}^{\lambda g_{k-1}(X_k)}, \end{align*}

which implies

\begin{align*} g_{k-1}(X_k)&\le\frac{1}{\lambda}\log\mathcal{M}[g_{k-1};\,V_{a}](\lambda)-\frac{1}{\lambda}\log\mu(V_{a}-V_{h}) \\[3pt] &\le\frac{\log(1-q+q\mathrm{e}^\lambda+o(1))}{\lambda} (k-1)+p\varepsilon n/16+\frac{\sqrt{d}h^2}{2\lambda}+O(1). \end{align*}

For $k\in I$ , $X_k\notin L_{h}$ , and $g_{k-1}(X_k)\le n$ is trivially true. Finally, we upper-bound $m_n$ . Summing over k, we get that on $\mathcal B^c$ ,

\begin{align*} m_n&=\sum_{k\notin I}g_{k-1}(X_k)+\sum_{k\in I}g_{k-1}(X_k)\\[3pt] &\le \frac{\log(1-q+q\mathrm{e}^\lambda+o(1))}{\lambda}\binom{n}{2}+p\varepsilon n^2/16+\frac{n\sqrt{d}h^2}{2\lambda}+O(n)+p\varepsilon n^2/16. \end{align*}

Choose $\lambda$ such that $({1}/{\lambda})\log(1-q+q\mathrm{e}^\lambda)\le p+p\varepsilon/16$ , and $c_0\le\sqrt{p\varepsilon\lambda}/10$ . Such a $\lambda$ exists since

\begin{align*}\underset{\lambda\to 0^+}{\lim}\frac{\log(1-q+q\mathrm{e}^\lambda)}{\lambda}=q < p+p\varepsilon/16. \end{align*}

Then $m_n$ is bounded by

\begin{align*}(p+p\varepsilon/16)\binom{n}{2}+p\varepsilon n^2/16+p\varepsilon n^2/16+O\left(\frac{n}{\lambda}\right)+p\varepsilon n^2/16\le \left(p+p\varepsilon/2\right)\binom{n}{2}. \end{align*}

So we can conclude that (5.6) holds on $\mathcal B^c$ . The proof of Proposition 13 is completed by noting that

\begin{align*}\mathbb{P}(\mathcal B)\le \exp({-}p\varepsilon n\sqrt{d}h^2/64)\le \exp\big({-}\min\big(c_1(p,\varepsilon)n^2, c_2(p,\varepsilon)n\sqrt d\big)\big), \end{align*}

where $c_1(p,\varepsilon)=p\varepsilon c_0^2/64$ and $c_2(p,\varepsilon)=p\varepsilon a^2/64$ are constants.

Remark 7. We can determine the dependence of the constants in Theorem 4 (and also Theorem 3) on p and $\varepsilon$ by estimating the constants used in the proof of Proposition 13 Take $\lambda=\varepsilon/100$ and $c_0=\sqrt{p}\varepsilon/100$ . Note that $\bar \Phi^{-1}\left(p\right)\sim\sqrt{\log 1/p}$ , so we may take

\begin{align*}a^2=\frac{\bar \Phi^{-1}\left(p\right)-\bar \Phi^{-1}\left(p+p\varepsilon/32\right)}{2}=\Omega\left(\frac{\varepsilon}{\sqrt{\log(1/p)}}\right). \end{align*}

Then the corresponding constants satisfy $c_1(p,\varepsilon)=\Omega(p^2\varepsilon^3)$ and $c_2(p,\varepsilon)=\Omega(p\varepsilon^2/\sqrt{\log 1/p})$ . This gives

\begin{align*}\mathbb{P}(\mathcal{I}_{\varepsilon})\le\exp\left({-}\min\left(\Omega(p^2\varepsilon^4)n^2,\Omega\left(\frac{p\varepsilon^3}{\sqrt{\log 1/p}}\right)n\sqrt{d}\right)\right). \end{align*}