Pith. sign in

REVIEW 2 major objections 3 minor 44 references

This paper proves that the spherical random geometric graph G(n,d,p) and the binomial random graph G(n,p) are statistically indistinguishable whenever d ≫ n^3 p^3 (log 1/p)^3, for p down to n^{-1/5} polylog(n).

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 04:35 UTC pith:HTAL2OOU

load-bearing objection The pointwise probability estimate is a real contribution, but Theorem 1.2 is not proved in its claimed p-range and the threshold itself is already covered by the independent result the authors cite. the 2 major comments →

arxiv 2607.22480 v1 pith:HTAL2OOU submitted 2026-07-24 math.PR cs.DMmath.CO

Distinguishability threshold for random geometric graphs

Zach Hunter , Aleksa Milojevi\'c , Benny Sudakov This is my paper
classification math.PR cs.DMmath.CO MSC 05C8060D05
keywords random geometric graphsspherical random geometric graphbinomial random graphtotal variation distancesigned triangle countstatistical distinguishabilityhigh-dimensional probabilityvertex exposure
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes the long-standing distinguishability conjecture for spherical random geometric graphs in the sparse range 1/3 ≥ p ≥ n^{-1/5} polylog(n): once the sphere dimension d exceeds a constant times n^3 p^3 (log 1/p)^3, the total variation distance between G(n,d,p) and the binomial random graph G(n,p) tends to zero. The engine is a pointwise formula: for any mildly pseudorandom graph H, the probability that G(n,d,p) equals exactly H is at most (1+o(1)) times the corresponding G(n,p) probability, with the leading correction controlled by the signed triangle count of H divided by sqrt(d). If correct, this resolves the conjecture in a broad previously open regime and shows that the signed-triangle test is optimal in that range. It also provides local distributional information about the geometric model that goes beyond the testing question.

Core claim

The central claim is that geometry is undetectable exactly when d ≫ n^3 p^3 (log p^{-1})^3, for p in [n^{-1/5}(logn)^A, 1/3]. More precisely, for every ε>0 and d ≥ C_ε n^3 p^3 (log p^{-1})^3, TV(G(n,p), G(n,d,p)) ≤ ε. The proof achieves this via Proposition 3.1: for any pseudorandom graph H (with degrees, codegrees, and spectrum close to those of G(n,p)), the probability that G(n,d,p) equals H, intersected with a high-probability event on the latent vectors, is at most p^{e(H)}(1-p)^{N-e(H)} exp( κ_△ N_△(H)/√d + κ_□ N_□(H)/d + κ_◇ N_◇(H)/d + o(1) ), where N_△ is the signed triangle count. Since the signed triangle count is typically O(n^{3/2} p^{3/2}), the exponent is o(1) precisely when d ≫

What carries the argument

The signed triangle count N_△(H)=Σ_{i<j<k}(A_{ij}-p)(A_{jk}-p)(A_{ik}-p) is the leading correction: triangles are boosted and two-edge triples are suppressed by the geometry with opposite signs, so their net effect is captured by this centered count. The proof machinery is a one-vertex-at-a-time exposure using the Gram–Schmidt/Bartlett decomposition of the latent sphere vectors, which makes the coordinates of the remaining points conditionally independent. Truncated Gaussians approximate the spherical conditional laws, and the one-step contribution is controlled through a concentration inequality for subgaussian quadratic forms, culminating in the moment-generating-function estimate that yie

Load-bearing premise

Proposition 3.1 — the pointwise bound on P[G(n,d,p)=H] — is stated and proved only for p ≥ n^{-1/3}(logn)^A, but Theorem 1.2 applies it for p as small as n^{-1/5}(logn)^A; if that estimate cannot be extended down, the theorem's stated range is not established by the proof, and the supporting pseudorandomness lemma is proved only for p ≥ n^{-1/3}, with its main auxiliary stated for p ≥ n^{-1/2}.

What would settle it

Read Section 4 and Appendix A.2: Proposition 3.1 and Lemma 2.11 are each proved under hypotheses p ≥ n^{-1/3}(logn)^A (and Lemma A.1 for p ≥ n^{-1/2}), while Section 3.1 applies them for p as low as n^{-1/5}(logn)^A. Taking p = n^{-1/5} and d = C n^3 p^3 (log 1/p)^3, the error term n^{5/2}p^{1/2}/d is a constant (up to log factors), so the proof's stated error control only vanishes for p ≫ n^{-1/5}; if no remark or lemma closes the gap, the theorem is unsubstantiated in the claimed range.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • If the theorem is correct, the signed-triangle test is optimal up to constants: below the threshold d ≪ n^3 p^3 (log 1/p)^3 triangles distinguish the models, while above it no test can.
  • The pointwise bound gives local distributional control on G(n,d,p), including for graphs with unusually few triangles, which are exponentially less likely than in G(n,p).
  • Indistinguishability now holds for all p down to n^{-1/5} polylog(n), a wide range where the conjecture was previously open.
  • The proof shows the geometric correction factorizes, to first order, over triples of vertices, with higher-order corrections from four-cycles and diamonds entering at order 1/d.
  • Because the argument works below the threshold as well, it yields an approximate description of the geometric graph in lower dimensions, not just a test for distinguishing it.
  • The induction framework suggests the same type of pointwise estimate could be extended to other latent-space random graph models with a similar one-step conditional independence structure.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The formal proof of Proposition 3.1 is stated for p ≥ n^{-1/3}(logn)^A, while Theorem 1.2 invokes it for p as small as n^{-1/5}(logn)^A; if that pointwise estimate cannot be extended downward, the theorem's stated range is not established by the proof as written.
  • The dominant error term n^{5/2} p^{1/2}/d in the one-step estimate vanishes only when p ≫ n^{-1/5}, so the p ≥ n^{-1/5} boundary appears to be a genuine limitation of the current induction rather than an artifact.
  • A testable extension is to verify numerically on small graphs that log P[G(n,d,p)=H]/P[G(n,p)=H] is linear in N_△(H)/√d plus higher-order signed counts; this would confirm the factorized pattern interpretation.
  • The pseudorandomness event E, proved via a local-to-global lemma that is itself stated only for p ≥ n^{-1/2}, is likely the main obstacle to pushing the proof below p ~ n^{-1/3} without new ideas.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper studies the total-variation distance between the spherical random geometric graph G(n,d,p) and the Erdős–Rényi graph G(n,p). Theorem 1.2 claims indistinguishability for every ε>0 whenever 1/3 ≥ p ≥ n^{-1/5}(log n)^A and d ≥ C_ε n^3 p^3 (log p^{-1})^3. The engine of the proof is Proposition 3.1, a pointwise upper bound on P[G(n,d,p)=H ∧ F] in terms of the signed triangle count, signed four-cycle count, and signed diamond count of H, with an explicit error term. The proof uses a Gram–Schmidt coordinate system, an inductive vertex-exposure scheme, pseudorandomness events E and F, truncated-Gaussian approximations, and Hanson–Wright-type moment-generating-function estimates. The authors acknowledge a concurrent independent proof of the conjecture by Du–Mao–Sun–Wu–Xu [14] in the regime p ≫ n^{-2/3}/log n.

Significance. If the technical estimates are correct, Proposition 3.1 is a substantial new local-limit statement for high-dimensional spherical random geometric graphs: it gives a parameter-free, explicit upper bound for the probability of realizing an arbitrary pseudorandom graph, with signed triangle counts as the leading correction. This is likely to be useful beyond the indistinguishability problem. The proof is self-contained and does not fit parameters to data. However, as an indistinguishability result, Theorem 1.2 is weaker than the already-cited result [14], since n^{-1/5} ≫ n^{-2/3}; the genuinely new contribution is Proposition 3.1 itself, not the resolution of Conjecture 1.1 in a new range. The manuscript's abstract and introduction should be repositioned accordingly.

major comments (2)
  1. [Introduction / Theorem 1.2] The claimed range in Theorem 1.2, 1/3 ≥ p ≥ n^{-1/5}(log n)^A, is contained in the regime p ≫ n^{-2/3}/log n already proved by the concurrent work [14]. Indeed n^{-1/5} ≫ n^{-2/3}, so every p satisfying the paper's lower bound also satisfies [14]'s lower bound. The note added in proof acknowledges [14], but the abstract and introduction still state that the paper resolves the conjecture in a broad range. This overstates the novelty of Theorem 1.2. The authors should explicitly identify Proposition 3.1, not Theorem 1.2, as the new contribution, and describe Theorem 1.2 as an application that is subsumed by [14].
  2. [§3.1 / Proposition 3.1] The reader's concern that Theorem 1.2's range p ≥ n^{-1/5} is not covered by Proposition 3.1's hypothesis p ≥ n^{-1/3} does not land: since n^{-1/5} > n^{-1/3} for large n, the theorem's lower bound is stronger, not weaker, than the proposition's. Thus the invocation of Proposition 3.1 in the proof of Theorem 1.2 is legitimate. This should be stated explicitly so that the reported gap is not mistakenly attributed to the paper.
minor comments (3)
  1. [Section 3, Proposition 3.1] The displayed definition of R_{n,d,p} appears to have a typo: it reads n^3 p^2 + n^{5/2}/d^{3/2}, but the intended term is presumably n^3 p^2 / d^{3/2}, matching Lemma 6.4's error. The same typo appears in the error computation in the proof of Theorem 1.2. Please correct.
  2. [Abstract / Note added in proof] The sentence 'it was previously fully proved only in the constant-density case' is outdated in view of [14]. Since the paper itself cites [14], the abstract and introduction should be updated to say that during the preparation of this work an independent proof for p ≫ n^{-2/3}/log n appeared, and that the present paper's indistinguishability theorem is contained in that range.
  3. [Appendix A.2, proof of Lemma 2.11] The proof invokes Lemma A.1 as stated in the regime p ≥ n^{-1/2}. Since the standing hypothesis is p ≥ n^{-1/3}(log n)^A, which implies p ≥ n^{-1/2}, there is no logical gap; however, the dependence could be made explicit to avoid confusion.

Circularity Check

0 steps flagged

No circular derivation: Theorem 1.2 follows from an independently derived pointwise probability bound; the noted p-range mismatch is a proof gap, not circularity.

full rationale

I walked the derivation chain: Theorem 1.2 is derived from Proposition 3.1, which is a pointwise upper bound on P[G(n,d,p)=H ∧ F]. The bound's correction terms κ△N△/√d, κ□N□/d, κ◇N◇/d are computed from explicit Gaussian and spherical estimates (e.g., Proposition 5.1, Claim 5.2, Lemmas 6.4 and 7.6), not defined so as to force the target indistinguishability statement. The event D is used only to control the magnitude of these signed counts, and the threshold d ≥ Cε n^3 p^3 (log p^{-1})^3 emerges from bounding κ△N△/√d plus the error term nR_{n,d,p}, rather than being assumed inside Proposition 3.1 (which only requires d ≥ Cn^2 p (log n)^A). No parameter is fitted to data, and no prediction is the renamed value of a fitted input. The reference to the authors' earlier work [19] is motivational/technical background only; the load-bearing estimates are proved in this paper or cited to independent works ([4], [6], [23], [34]). The main concern in the manuscript is a rigor gap: Proposition 3.1 is stated and proved for p ≥ n^{-1/3}(log n)^A (§4: 'In particular, d ≥ Cn^2 p(log n)^A, p ≥ n^{-1/3}(log n)^A'), while Theorem 1.2 claims the range p ≥ n^{-1/5}(log n)^A. Similarly, Lemma 2.11's appendix proof invokes Lemma A.1, which is introduced for p ≥ n^{-1/2}. These are correctness issues about the stated range, not circularity: the theorem is not assumed in the proof of the bound, and the bound does not reduce by construction to the theorem. Therefore the circularity score is minimal.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

No free parameters are fitted; the proof uses standard probability tools and the structural domain assumption that the spherical RGG is well-approximated by Gaussians and that pseudorandomness events hold w.h.p. No new entities (particles, forces, dimensions) are introduced.

axioms (4)
  • standard math Standard Gaussian tail bounds, log-concavity of Φ, and properties of the Mills ratio λ (Lemmas 2.1, 2.2).
    Used throughout the proof for estimates on edge probabilities and truncated Gaussians.
  • domain assumption Spherical distribution is close to Gaussian after scaling (Lemma 2.4, 2.5, 2.6).
    This is the core analytic approximation used to replace spherical distributions by Gaussians in the vertex-exposure scheme.
  • standard math Hanson–Wright inequality and subgaussian concentration (Theorem 2.8, Proposition 7.3).
    Used to control quadratic forms in the moment generating function estimates.
  • domain assumption The pseudorandom events E (graph) and F (vectors) hold with probability 1-o(1) under the stated parameter ranges (Lemmas 2.11, 2.13).
    Required to apply the pointwise probability bound to most graphs; the paper provides proofs but with the parameter-range inconsistencies noted in the weaknesses.

pith-pipeline@v1.3.0-alltime-deepseek · 52968 in / 28117 out tokens · 227657 ms · 2026-08-01T04:35:48.852903+00:00 · methodology

0 comments
read the original abstract

The spherical random geometric graph $G(n,d,p)$ is obtained by sampling $n$ independent points uniformly on the unit sphere $\mathbb{S}^{d-1}\subseteq\mathbb{R}^d$ and joining pairs of points which are sufficiently close, where the threshold is chosen so that the edge probability is $p$. The central question related to this model, and to a broad class of other models, is the following: when does the underlying geometry affect the resulting graph in a way which makes it distinguishable from the Erd\H{o}s--R\'enyi random graph $G(n,p)$, as measured in total variation distance? The precise answer to this question was conjectured by Bubeck, Ding, Eldan, and R\'acz, who predicted that $G(n,d,p)$ and $G(n,p)$ are indistinguishable precisely when $d \gg n^3p^3(\log p^{-1})^3$, and provided a test for distinguishing these models in the low-dimensional regime. Although this conjecture attracted considerable attention from researchers in probability, theoretical computer science, and high-dimensional statistics, it was previously fully proved only in the constant-density case. In this paper, we resolve the distinguishability conjecture in the broad range $1/3 \geq p \geq n^{-1/5} \text{polylog}(n)$. The key ingredient of our proof is a stronger statement which gives a precise asymptotic formula for the probability that $G(n,d,p)$ realizes a prescribed graph $H$: above the conjectured threshold, this probability is at most $(1+o(1))$ times the corresponding probability for $G(n,p)$, with the signed triangle count of $H$ appearing as the leading correction term.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

44 extracted references · 7 linked inside Pith

  1. [1]

    Abdalla, A

    P. Abdalla, A. S. Bandeira, and C. Invernizzi.Guarantees for spontaneous synchronization on random geometric graphs. SIAM J. Appl. Dyn. Syst. 23(1) (2024), 779–790

    2024

  2. [2]

    Balogh, B

    J. Balogh, B. Bollob´ as, M. Krivelevich, T. M¨ uller, and M. Walters.Hamilton cycles in random geometric graphs.Ann. Appl. Probab. 21(3) (2011), 1053–1072

    2011

  3. [3]

    Bangachev and G

    K. Bangachev and G. Bresler.Detection ofL ∞ geometry in random geometric graphs: suboptimality of triangles and cluster expansion.InProceedings of Thirty Seventh Conference on Learning Theory, Proc. Mach. Learn. Res. 247, PMLR, 2024, 427–497

    2024

  4. [4]

    Bangachev and G

    K. Bangachev and G. Bresler.On the Fourier coefficients of high-dimensional random geometric graphs.InProceedings of the 56th Annual ACM Symposium on Theory of Computing, ACM, 2024, 549–560. arXiv:2402.12589

    Pith/arXiv arXiv 2024

  5. [5]

    Z. W. Birnbaum.An inequality for Mill’s ratio.Ann. Math. Statist. 13(2) (1942), 245–246

    1942

  6. [6]

    J. Bok, S. Li, and S. Yu.Detection of local geometry in random graphs: information-theoretic and computational limits. arXiv preprint arXiv:2603.24545 (2026)

    arXiv 2026

  7. [7]

    Brennan, G

    M. Brennan, G. Bresler, and B. Huang.Threshold for detecting high dimensional geometry in anisotropic random geometric graphs.Random Structures Algorithms 64(1) (2024), 125–137

    2024

  8. [8]

    Brennan, G

    M. Brennan, G. Bresler, and D. Nagaraj.Phase transitions for detecting latent geometry in random graphs.Probab. Theory Related Fields 178 (2020), 1215–1289

    2020

  9. [9]

    Bubeck, J

    S. Bubeck, J. Ding, R. Eldan, and M. Z. R´ acz.Testing for high-dimensional geometry in random graphs.Random Structures Algorithms 49(3) (2016), 503–532

    2016

  10. [10]

    Chatterjee.A generalization of the Lindeberg principle.Ann

    S. Chatterjee.A generalization of the Lindeberg principle.Ann. Probab. 34(6) (2006), 2061–2076

    2006

  11. [11]

    Cao and Y

    Y. Cao and Y. Zhu.Spectra of high-dimensional sparse random geometric graphs.arXiv preprint arXiv:2507.06556, 2025

    Pith/arXiv arXiv 2025

  12. [12]

    Duchemin and Y

    Q. Duchemin and Y. de Castro.Random geometric graph: some recent developments and perspectives.arXiv:2203.15351, 2022

    Pith/arXiv arXiv 2022

  13. [13]

    Devroye, A

    L. Devroye, A. Gy¨ orgy, G. Lugosi, and F. Udina.High-dimensional random geometric graphs and their clique number. Electron. J. Probab. 16 (2011), no. 90, 2481–2508

    2011

  14. [14]

    H. Du, C. Mao, N. Sun, Y. Wu, and J. Xu.Resolution of the detection threshold conjecture for random geometric graphs in thed > nregime.arXiv preprint arXiv:2607.02013, 2026

    Pith/arXiv arXiv 2026

  15. [15]

    Eldan and D

    R. Eldan and D. Mikulincer.Information and dimensionality of anisotropic random geometric graphs.InGeometric aspects of functional analysis, Lecture Notes in Math. 2256, Springer, 2020, 273–324

    2020

  16. [16]

    Erd˝ os and A

    P. Erd˝ os and A. R´ enyi.On random graphs. I.Publ. Math. Debrecen 6 (1959), 290–297

    1959

  17. [17]

    Erd˝ os.Some remarks on the theory of graphs.Bull

    P. Erd˝ os.Some remarks on the theory of graphs.Bull. Amer. Math. Soc. 53 (1947), 292–294

    1947

  18. [18]

    E. N. Gilbert.Random plane networks.J. Soc. Indust. Appl. Math. 9(4) (1961), 533–543

    1961

  19. [19]

    Hunter, A

    Z. Hunter, A. Milojevi´ c, and B. Sudakov.Gaussian random graphs and Ramsey numbers.arXiv preprint arXiv:2512.17718, 2025

    Pith/arXiv arXiv 2025

  20. [20]

    Janson, T

    S. Janson, T. Luczak, and A. Ruci´ nski.Random graphs.Wiley-Interscience, New York, 2000

    2000

  21. [21]

    Y. Kuramoto.Self-entrainment of a population of coupled non-linear oscillators.InInternational Symposium on Math- ematical Problems in Theoretical Physics(Kyoto, 1975), Lecture Notes in Phys. 39, Springer, 1975, 420–422

    1975

  22. [22]

    Laurent and P

    B. Laurent and P. Massart.Adaptive estimation of a quadratic functional by model selection.Ann. Statist. 28(5) (2000), 1302–1338. 30 ZACH HUNTER, ALEKSA MILOJEVI ´C, AND BENNY SUDAKOV

    2000

  23. [23]

    S. Liu, S. Mohanty, T. Schramm, and E. Yang.Testing thresholds for high-dimensional sparse random geometric graphs. SIAM J. Comput. (Special Section STOC 2022), 2024, STOC22-125–STOC22-181

    2022

  24. [24]

    S. Liu, S. Mohanty, T. Schramm, and E. Yang.Local and global expansion in random geometric graphs.InProceedings of the 55th Annual ACM Symposium on Theory of Computing, ACM, 2023, 817–825

    2023

  25. [25]

    Liu and M

    S. Liu and M. Z. R´ acz.Phase transition in noisy high-dimensional random geometric graphs.arXiv:2103.15249, 2021

    Pith/arXiv arXiv 2021

  26. [26]

    Liu and M

    S. Liu and M. Z. R´ acz.A probabilistic view of latent space graphs and phase transitions.Bernoulli 29(3) (2023), 2417– 2441

    2023

  27. [27]

    A. M. Mathai, S. B. Provost, and T. Hayakawa.Bilinear forms and zonal polynomials.Lecture Notes in Statistics 102, Springer-Verlag, New York, 1995

    1995

  28. [28]

    McDiarmid and T

    C. McDiarmid and T. M¨ uller.On the chromatic number of random geometric graphs.Combinatorica 31(4) (2011), 423–488

    2011

  29. [29]

    J. Ma, W. Shen, and S. Xie.An exponential improvement for Ramsey lower bounds.Invent. Math. (2026), to appear, doi:10.1007/s00222-026-01421-9

    doi:10.1007/s00222-026-01421-9 2026

  30. [30]

    M¨ uller.Two-point concentration in random geometric graphs.Combinatorica 28(5) (2008), 529–545

    T. M¨ uller.Two-point concentration in random geometric graphs.Combinatorica 28(5) (2008), 529–545

    2008

  31. [31]

    Paquette and E

    E. Paquette and E. Vander Werf.Random geometric graphs and the spherical Wishart matrix.arXiv preprint arXiv:2110.10785, 2021

    Pith/arXiv arXiv 2021

  32. [32]

    M. D. Penrose.Onk-connectivity for a geometric random graph.Random Structures Algorithms 15(2) (1999), 145–164

    1999

  33. [33]

    Penrose.Random geometric graphs.Oxford Studies in Probability 5, Oxford University Press, Oxford, 2003

    M. Penrose.Random geometric graphs.Oxford Studies in Probability 5, Oxford University Press, Oxford, 2003

    2003

  34. [34]

    Rudelson and R

    M. Rudelson and R. Vershynin.Hanson–Wright inequality and sub-gaussian concentration.Electron. Commun. Probab. 18 (2013), no. 82, 1–9

    2013

  35. [35]

    M. R. Sampford.Some inequalities on Mill’s ratio and related functions.Ann. Math. Statist. 24(1) (1953), 130–132

    1953

  36. [36]

    S. H. Strogatz.From Kuramoto to Crawford: exploring the onset of synchronization in populations of coupled oscillators. Physica D 143(1–4) (2000), 1–20

    2000

  37. [37]

    Vershynin.High-dimensional probability

    R. Vershynin.High-dimensional probability. An introduction with applications in data science.Second edition, Cambridge Series in Statistical and Probabilistic Mathematics 58, Cambridge University Press, Cambridge, 2026

    2026

  38. [38]

    ν(x)” to denote what is−λ(x) in our notation, and “λ(x) =ν ′(x)

    M. J. Wainwright.High-dimensional statistics. A non-asymptotic viewpoint.Cambridge Series in Statistical and Proba- bilistic Mathematics 48, Cambridge University Press, Cambridge, 2019. AppendixA.Proof of Preliminaries A.1.Deferred proofs from Section 2.1. Proof of Lemma 2.1.The logarithmic derivative of Φ is (log Φ) ′(t) = ϕ(t) Φ(t) =λ(t). Sinceλ ′(t)≤0 ...

    2019

  39. [39]

    Here, we give its simplified statement, in the regime wheremandℓare constant, and p≥n −1/2

    (Lemma 5.1). Here, we give its simplified statement, in the regime wheremandℓare constant, and p≥n −1/2. Lemma A.1.Letu 1, . . . ,um,w 1, . . . ,wℓ be sampled uniformly at random fromS d−1, and let L={x:⟨u i, x⟩ ≥cp,d/ √ dfor alli∈[m]and⟨w j, x⟩< cp,d/ √ dfor allj∈[ℓ]}. Ifµ=P[x∈L]is the probability that a uniformly sampled pointx∈S d−1 lands inL, then the...

  40. [40]

    Hence, the standard Gaussian tail estimate gives P |⟨πs(gi), πs(gj)⟩| ≥3 p 2nlogn gi ≤2 exp(−9(logn)/2)≤n −4

    In the above paragraph, we have shown that with high probability,∥π s(gi)∥2 2 ≤s+ 4 √nlogn≤2nfor alli, s. Hence, the standard Gaussian tail estimate gives P |⟨πs(gi), πs(gj)⟩| ≥3 p 2nlogn gi ≤2 exp(−9(logn)/2)≤n −4. A union bound over theO(n 3) triples (s, i, j) shows that with high probability, ⟨πs(gi), πs(gj)⟩ ≤ 5√nlognfor all 1≤s < i < j≤n. Combined wi...

  41. [41]

    Namely, they have shown that ifδ >0 is chosen such thatP[G(n, d, p) =△] =p 3(1 +δ), then Var[N △(G)]≤O(n 3p3(1 + δ) +p 5δ2n4 +p 6δn4)

    and [6, Equations (B.3)-(B.6)] (under the minimal assumptiond≫log(1/p) 4). Namely, they have shown that ifδ >0 is chosen such thatP[G(n, d, p) =△] =p 3(1 +δ), then Var[N △(G)]≤O(n 3p3(1 + δ) +p 5δ2n4 +p 6δn4). The precise asymptotics ofδcan be derived from the Theorem A.3. To do this, observe the random variablesA ij, Aik are pairwise independent whenj̸=k...

  42. [42]

    Ifδ 1 is sufficiently small, then E[eξT M ξ+aT ξ]−E[e gT M g+aT g] =O eO(δ2)δ1δ2 . DISTINGUISHABILITY THRESHOLD FOR RANDOM GEOMETRIC GRAPHS 39 Proof.Replacingξandgbyξ/σandg/σ, and replacingMandabyσ 2Mandσa, respectively, does not change either exponential in the conclusion or the values ofδ 1 andδ 2. Hence, we may assume without loss of generality thatσ= ...

  43. [43]

    Hence,E z(i)[e4aT z(i) ]≤e O(∥a∥2 2). Finally, the random variable 4(z (i))T Mz (i) is a quadratic form in independent centered subgaussians, and as such its expectation can be bounded bye O(∥M∥ 2 HS ), using the Hanson-Wright inequality (see Theorem 2.8). Hence, we have ∆i ≤O eO(∥M∥ 2 HS +∥a∥2 2) |ai|3 + mX j=1 M 2 ij 3/2 ≤e O(δ2)O δ1 |ai|2 + mX j=1 M 2 ...

  44. [44]

    On the other hand, using the Taylor series of the functionA7→log detA, we find that when∥M ′∥op is sufficiently small, then we have log det(I−2M ′) =− P∞ k=1 tr((2M ′)k)/k

    This is simple to see since |a′T (I−2M ′)−1a′ −a ′T a′|=|a ′T ((I−2M ′)−1 −I)a ′| ≤ ∥a∥2 2∥((I−2M ′)−1 −I)∥ op ≤O(∥M ′∥op∥a∥2 2), and recall that∥M ′∥op ≤ ∥M∥op ≤δ 1. On the other hand, using the Taylor series of the functionA7→log detA, we find that when∥M ′∥op is sufficiently small, then we have log det(I−2M ′) =− P∞ k=1 tr((2M ′)k)/k. The first term of...