Cubic spectral conjecture for random geometric graph detection

Let $G_n^{\mathrm{geo}}$ be a random geometric graph generated by independent uniform points on a high-dimensional sphere, with connection function $K_n$ applied to endpoint inner products, and let $G_n^{\mathrm{ER}}$ be the Erdős–Rényi graph with the same edge density. If $\kappa_n$ is the centered and standardized spherical kernel operator, then the conjecture asserts that

n^3\left[\operatorname{tr}(\kappa_n^3)\right]^2\longrightarrow 0\quad\Longrightarrow\quad d_{\mathrm{TV}}\!\left(\mathcal{L}(G_n^{\mathrm{geo}}),\mathcal{L}(G_n^{\mathrm{ER}})\right)\longrightarrow 0.

Equivalently, for every sequence of tests distinguishing the two graph models, the sum of the two error probabilities has lower limit at least $1$ .

References

Primary source

arXiv

Additional references

Cubic spectral cancellation and random geometric graph detection: a quadratic-kernel counterexample — arXiv — Congyi Luo

Posted 3 weeks ago · edited 3 weeks ago

Progress summary

Refreshed 3 weeks ago

Claimed progress

A September 2026 preprint claims to refute the conjecture for unrestricted connection functions, while restricted versions remain open.

The conjecture proposes that detection is governed by the cubic spectral quantity $n^{3}\operatorname{tr}^{2}(\kappa^{3})$ , with detectability above and impossibility below the threshold. A February 2026 paper presented this as a conjecture, not a theorem.

Known results

For a fixed smooth kernel with $K'(0)\ne 0$ , the critical dimension is $d_{*}=n^{3/4}$ , and signed triangles detect below this threshold.
For a quadratic kernel, the reported test threshold is $d_{\sf test}^{*}=n^{3/8}$ .
For hard random geometric graphs, a July 2026 paper proves impossibility for $d\gg (nh(p))^{3}$ with $d\ge (1+\epsilon)n$ , covering the conjectured threshold when $h(p)\gtrsim n^{-2/3}$ ; the regime $d\le n$ remains open.

September 10, 2026 counterexample

Congyi Luo’s preprint claims that the cubic-trace condition fails for dimension-dependent, nonmonotone connection functions: cubic statistics can cancel while fourth-order statistics retain signal. The claim targets the formulation without monotonicity or a common-sign spectral condition and has not been independently verified.

Current status (as of September 2026): The unrestricted conjecture is claimed refuted by an unverified counterexample; versions with monotonicity or common-sign spectral assumptions, and the hard-kernel regime $d\le n$ , remain open.

Sources

No solutions have been posted yet.