Norm Bounds for Sparse Random Tensors and Spectral Gap of Random Hypergraphs

Kevin Lucca; Lucas Pesenti

Norm Bounds for Sparse Random Tensors and Spectral Gap of Random Hypergraphs

T0 review · 0 major / 6 minor · reviewed 2026-07-09 · glm-5.2

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

Pith's one-line read Sparse random hypergraphs show spectral gap at n^{r/2} edges

desk verdict Solid paper resolving a 30-year-old question; the key technique is an explicit selector process decomposition that actually works read the letter →

arxiv 2607.07308 v1 pith:5YYBB42L submitted 2026-07-08 math.PR cs.DMmath.CO

Kevin Lucca , Lucas Pesenti This is my paper · ORCID

classification math.PRcs.DMmath.CO

keywords randomhypergraphstensorsboundsdecompositioneigenvalueentriesfactors

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper pins down the exact sparsity threshold at which Erdős–Rényi random hypergraphs develop a spectral gap. For r-uniform hypergraphs on n vertices, the gap emerges as soon as the expected number of hyperedges m satisfies m ≫ n^{r/2}, matching the information-theoretic lower bound with no extra logarithmic factors. All prior methods—based on flattening the adjacency tensor into a matrix—inherently lost at least a polylog(n) factor and could not detect this phase transition. The authors remove that loss by decomposing the supremum of a selector process into two parts: a 'Bernstein part' controlled by standard concentration, and a 'positive part' controlled by an explicit witness set of normalized indicator tensors. The key structural innovation is the normalization φ(S) = √|S| / max(4r², log²|S|) for indicator vectors, which allows arbitrary test vectors to be dominated by the solid convex hull of these witnesses. A union bound over the witnesses then yields the sharp bound. As consequences, the paper gives improved injective norm bounds for sparse random tensors with independent entries—replacing exponential dependence on the tensor order r with polynomial dependence—and extends Seginer's classical matrix norm theorem to tensors under an L^{2+ε}–L² moment equivalence assumption.

What carries the argument

The selector process decomposition (equation 4): clip tensor entries at threshold τ = 1/(n log n) to separate the Bernstein part from the positive part. For the positive part, construct a witness set W of normalized indicator tensors with φ(S) = √|S|/max(4r², log²|S|), prove that XP ⊆ solid(Conv(W)) via a level-set decomposition of test vectors (Lemmas 3.9–3.11), and apply a Chernoff-bound union bound over W (Lemmas 3.12–3.13).

What would settle it

A counterexample would be a sequence of test vectors (unit-norm rank-1 tensors) for which the level-set decomposition in equation (7) produces index sets A_{k,i} that cannot be assigned to any K_j partition while maintaining the coefficient bounds in Lemmas 3.10–3.11. Concretely, if there exist unit vectors x₁,...,x_r such that the sum of coefficients r^{-k_i}φ(A_{k,i}) over the relevant K_0 or K_j exceeds the 1/2 or 1/(2r) budget, the solid convex hull containment (Lemma 3.9) fails and the union bound cannot control the positive part.

Watch

Extended reading notes

Core claim

The injective norm of the centered adjacency tensor of a sparse Erdős–Rényi r-uniform hypergraph is bounded by O(1) (up to polynomial factors in r and 1/ε) whenever each entry is nonzero with probability at most n^{-1-ε}. Setting ε so that the expected number of hyperedges satisfies m ≫ n^{r/2} yields the spectral gap ∥T∥_inj − ∥T − ET∥_inj = (1−o(1))pn^{r/2}. The bound is achieved by an explicit decomposition of the selector process into a Bernstein part (entries clipped at threshold 1/(n log n), controlled by Bernstein's inequality and a net argument) and a positive part (large entries, controlled by a union bound over a witness set of normalized {0,1}-valued pure tensors). The witness set

Load-bearing premise

The entire argument hinges on the specific normalization φ(S) = √|S|/max(4r², log²|S|) for indicator vectors being exactly the right choice to ensure that arbitrary test vectors can be covered by the solid convex hull of the witness set. If this normalization is too aggressive, some test vectors escape coverage; if too conservative, the union bound over witnesses picks up extra logarithmic factors and the sharp threshold is lost. The authors identify this as 'the main step of

Editorial extensions

If this is right

The second eigenvalue of sparse random hypergraphs could serve as an efficient certificate of unsatisfiability for random r-SAT formulas with O(n^{r/2}) constraints, potentially providing a simpler spectral alternative to non-backtracking-walk certificates for odd r.
The improved expander mixing lemma for sparse hypergraphs (Example 3.3) tightens discrepancy bounds for counting hyperedges across vertex subsets, with direct applications to tensor completion and multilayer community detection where prior analyses lost polylog factors.
The polynomial-in-r dependence of the sparse tensor norm bound opens the door to analyzing constant-order tensors with r growing (slowly) with n, a regime inaccessible to prior exponential-in-r estimates.
Conjecture 1.8—a full Seginer-type characterization of the injective norm for arbitrary i.i.d. tensor entries without moment assumptions—is now precisely formulated and shown equivalent to the proven Theorem 1.7 under moment equivalence, isolating exactly what remains open.
The explicit witness-set construction provides a template for systematizing ad hoc union-bound arguments in other high-dimensional extremal problems, potentially replacing case-by-case discretization analyses.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The decomposition strategy may extend to other structured random tensor models (e.g., stochastic block model tensors, spiked tensor models) where sparsity interacts with low-rank structure, potentially yielding sharp thresholds currently obscured by flattening-based analyses.
If the witness-set normalization φ(S) can be computed or approximated efficiently, it might lead to polynomial-time algorithms for approximating the injective norm of sparse random tensors, partially addressing the algorithmic question raised in Section 1.2 about whether the second eigenvalue can be computed efficiently in the sparse regime.
The gap between the proven polynomial dependence on r and the likely optimal dependence—given recent sharp constants for Gaussian tensors—suggests that the witness-set approach may be refinable, and that the true dependence on r could be linear or sublinear.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

The main thing to know: this paper proves that r-uniform Erdős-Rényi hypergraphs have a spectral gap (in the Friedman-Wigderson sense) exactly when m ≫ n^{r/2}, with no logarithmic factors. That threshold is information-theoretically tight and was previously known only up to polylog factors — the log loss was inherent to flattening approaches, as the paper explains clearly. Removing it is the real contribution here, and the technique they use to do it is genuinely new. The authors take Talagrand's abstract, non-constructive selector process decomposition theorem and implement it explicitly for the injective norm problem. The key step is identifying a normalization φ(S) = √|S|/max(4r², log²|S|) for indicator witnesses that makes the covering argument work. They acknowledge this as the main substantive step, and the verification in Lemmas 3.9–3.11 is complete — each inequality (the sum-integral comparison, the splitting by k_i vs k_1) checks out. The proof decomposes cleanly: Bernstein part via a standard net argument (Lemma 3.6), positive part via Chernoff union bound over the witness set (Lemmas 3.12–3.13). The Seginer-type extension (Theorem 5.1) is a natural combination of their sparse bound with Boedihardjo's dense bound, using a clipping threshold that interpolates between regimes. It's clean. The soft spots are minor and the paper is upfront about them. Theorem 3.1 requires r ≤ ε log n / (5 log log n), so the main result is for fixed r; the extension to arbitrary r via Boedihardjo has worse r-dependence. The polynomial dependence on r and ε in Theorem 1.4 is stated as non-optimal. Conjecture 1.8 (full Seginer without moment equivalence) is left open. Algorithmic aspects are deferred. None of these undermine the central result. I agree with the reader's assessment. The stress-test found no load-bearing flaw, and I checked the fragile points — the normalization and covering argument — independently. The reduction to Ber(Ln^{-1-ε}) for the worst case is standard stochastic domination. The handling of tensor symmetry via partitioning into r! independent tensors is correct. This is for probabilists and combinatorics people working on random tensors, spectral graph theory, or CSP refutation. It deserves a serious referee.

Referee Report

0 major / 6 minor

Summary. This paper studies the injective norm of sparse random tensors and applies the results to establish the spectral gap of Erdős–Rényi hypergraphs. The main result (Theorem 1.3) shows that for fixed r ≥ 3, r-uniform Erdős–Rényi hypergraphs on n vertices exhibit a spectral gap as soon as the expected number of hyperedges m satisfies m ≫ n^{r/2}, removing the polylogarithmic factors present in all prior work. The proof proceeds via an explicit decomposition of the associated selector process into a Bernstein part (Lemma 3.6) and a positive part (Lemma 3.7), inspired by Talagrand's generic decomposition theorem for selector processes. The positive part is controlled by an explicitly constructed witness set (Definition 3.8) with a carefully chosen normalization. As further consequences, the authors obtain improved norm bounds for sparse random tensors with independent entries (Theorem 1.4) and a Seginer-type theorem for tensors with i.i.d. entries under an L^{2+ε}–L^2 moment equivalence assumption (Theorem 1.7).

Significance. The spectral gap threshold n^{r/2} for Erdős–Rényi hypergraphs is a natural and long-standing target, and removing the polylogarithmic factors inherent to flattening-based approaches is a genuine technical contribution. The explicit witness-set decomposition is the central innovation: rather than invoking Talagrand's decomposition theorem as a black box, the authors construct the decomposition concretely, identifying the normalization φ(S) = √|S|/max(4r², log²|S|) as the key structural ingredient. The covering argument (Lemmas 3.9–3.11) is verified with explicit coefficient bounds, and the Chernoff-based union bounds (Lemmas 3.12–3.13) are clean. The Seginer-type extension (Theorem 5.1) is a natural and useful generalization, and the conjecture (Conjecture 1.8) is clearly stated. The applications to tensor completion (Example 3.4) and multilayer community detection (Example 3.5) demonstrate concrete improvements over prior bounds.

minor comments (6)

Section 1.4, equation (1): The notation δ(X) is introduced for the expected supremum of the selector process, but the symbol δ is not used elsewhere in the paper after this point. Consider clarifying that this is motivational notation from Talagrand's framework, or removing it to avoid confusion.
Definition 3.8: The witness set W_j for j ∈ [r] uses the normalization 1/(24r⁴ Σ|A_i| + (1/4r)log⁴n · Πϕ(A_i)²). The origin of the constants 24 and 4 is not immediately transparent. A brief remark on how these constants arise from the coefficient bounds in Lemma 3.11 would aid the reader.
Proof of Lemma 3.11: The bound uses (r/(r-1))^{r-1} ≤ 3, which holds for r ≥ 2 but is stated without justification. A parenthetical reference would suffice.
Theorem 5.1: The lower bound involves E[clip_M(Z)²] where M := 2E∥T∥_∞. The dependence on ε in the lower bound is noted to be necessarily exponential (Example 5.2), but the upper bound's dependence r⁵ log²(r/ε)/ε⁶ · K · M is polynomial in 1/ε. It would help to state explicitly whether this polynomial dependence is expected to be tight or whether there is room for improvement.
Remark 3.2: The claim that the conclusion holds for the model with exactly m hyperedges selected uniformly at random follows by conditioning, with the event having probability at least Ω(m^{-1/2}). A reference for this standard fact would be helpful for completeness.
The paper states (Section 1.6) that AI tools were used for literature research and typo scanning. This is transparent and appropriate.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity found

full rationale

The paper is a first submission with no self-citations. The central result (Theorem 1.3) is derived from Theorem 3.1, whose proof decomposes the selector process into a Bernstein part (Lemma 3.6, via Bernstein's inequality and a net argument) and a positive part (Lemma 3.7, via an explicitly constructed witness set W in Definition 3.8 and a Chernoff-based union bound). The decomposition is inspired by but does not black-box Talagrand's decomposition theorem; the witness set and covering argument (Lemmas 3.9–3.11) are constructed explicitly. External results used as black boxes—Boedihardjo's Theorem 4.1 for the dense/unbounded regime, Seginer's theorem as a target for extension, and standard concentration inequalities (Bernstein, Chernoff)—are all independent of the present paper. The Seginer-type extension (Theorem 5.1) combines the sparse bound (Corollary 4.3) with the dense bound (Theorem 4.1) via a clipping threshold B, which is a genuine interpolation rather than a circular reduction. No step in the derivation chain reduces to its own inputs by construction, and no 'prediction' is a renamed fit. The normalization φ(S) = √|S|/max(4r², log²|S|) is a substantive design choice verified by detailed coefficient bounds, not a fitted parameter presented as a prediction. The derivation is self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters or invented entities. The paper is pure probability theory with explicit constants.

assumptions (4)

standard math Talagrand's generic decomposition theorem for selector processes [Tal21, Theorem 11.12.1] provides the conceptual framework; the paper constructs the decomposition explicitly rather than invoking the theorem as a black box.
Invoked in Section 1.4 as inspiration. The actual decomposition (equation 4) and witness set (Definition 3.8) are constructed from first principles.
domain assumption Boedihardjo's bound on injective norm of random tensors with independent entries [Boe24, Corollary 1.4], stated as Theorem 4.1.
Used in Corollary 4.2 to handle the regime r > ε log n / (5 log log n) and in Theorem 5.1 for the dense (clipped) part. This is a recent external result.
standard math Bernstein's inequality and the multiplicative Chernoff bound (Lemmas 2.2–2.3).
Standard concentration inequalities used throughout the proof.
domain assumption Stochastic domination: among distributions on [0,1] with Pr(X≠0) ≤ p, Ber(p) maximizes the tail of sup_{X∈XP} ⟨T,X⟩.
Used without explicit proof in the proof of Theorem 3.1. This is a standard coupling argument but is stated as a fact.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Norm Bounds for Sparse Random Tensors and Spectral Gap of Random Hypergraphs." pith.science (2026). https://pith.science/paper/5YYBB42L

@misc{pith2026260707308,
  author       = {Pith},
  title        = {Pith review of: Norm Bounds for Sparse Random Tensors and Spectral Gap of Random Hypergraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5YYBB42L}},
  note         = {Machine review of arXiv:2607.07308}
}

abstract

Friedman and Wigderson (1995) introduced a notion of second eigenvalue for hypergraphs that generalizes the second eigenvalue of the adjacency matrix of a graph. We show that $r$-uniform Erd\H{o}s-R\'enyi hypergraphs on $n$ vertices exhibit a spectral gap as soon as their expected number of hyperedges $m$ satisfies $m \gg n^{r/2}$. Prior work identified this scale only up to logarithmic factors; removing these factors is the main technical challenge. Our proof overcomes this obstacle through an explicit decomposition of an associated selector process, inspired by a generic decomposition theorem of Talagrand (2021). As a consequence of our techniques, we obtain improved norm bounds for sparse random tensors with independent entries. Finally, under a mild moment equivalence assumption, we extend to tensors a seminal result of Seginer (2000) for random matrices with i.i.d. entries.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

[1]

Symposium on Theory of Computing (STOC) , pages =

Joel Friedman and Jeff Kahn and Endre Szemer. Symposium on Theory of Computing (STOC) , pages =

work page
[2]

Seginer, Yoav , journal =

work page
[3]

Combinatorica , volume = 15, number = 1, pages =

On the Second Eigenvalue of Hypergraphs , author =. Combinatorica , volume = 15, number = 1, pages =

work page
[4]

Combinatorica , year = 2006, volume = 26, pages =

Yonatan Bilu and Nathan Linial , title =. Combinatorica , year = 2006, volume = 26, pages =

work page 2006
[5]

Computational Complexity Conference (CCC) , volume =

Tommaso d'Orsi and Luca Trevisan , title =. Computational Complexity Conference (CCC) , volume =

work page
[6]

Luca Trevisan , howpublished =

work page
[7]

Allen and Ryan O'Donnell and David Witmer , title =

Sarah R. Allen and Ryan O'Donnell and David Witmer , title =. Symposium on Foundations of Computer Science (FOCS) , pages =

work page
[8]

Symposium on Theory of Computing (STOC) , pages =

Uriel Feige , title =. Symposium on Theory of Computing (STOC) , pages =

work page

Show all 33 references

[9]

Bandeira and Sivakanth Gopi and Haotian Jiang and Kevin Lucca and Thomas Rothvoss , title =

Afonso S. Bandeira and Sivakanth Gopi and Haotian Jiang and Kevin Lucca and Thomas Rothvoss , title =. Symposium on Theory of Computing (STOC) , pages =
[10]

Michel Talagrand , publisher =
[11]

Roman Vershynin , publisher =
[12]

Latała, Rafał , journal =
[13]

Random Structures & Algorithms , volume = 27, number = 2, pages =

Spectral techniques applied to sparse random graphs , author =. Random Structures & Algorithms , volume = 27, number = 2, pages =
[14]

and Shi, Jonathan and Steurer, David , booktitle =

Hopkins, Samuel B. and Shi, Jonathan and Steurer, David , booktitle =. 2015 , volume =

2015
[15]

Advances in Neural Information Processing Systems (NeurIPS) , year = 2022, volume = 35, pages =

Aaron Potechin and Goutham Rajendran , title =. Advances in Neural Information Processing Systems (NeurIPS) , year = 2022, volume = 35, pages =

2022
[16]

Friedman, Joel and Goerdt, Andreas and Krivilevich, Michael , journal =
[17]

Annals of Mathematics , volume = 180, year = 2014, number = 3, pages =

Bednorz, Witold and Lata. Annals of Mathematics , volume = 180, year = 2014, number = 3, pages =

2014
[18]

Symposium on Theory of Computing (STOC) , pages =

Lee,. Symposium on Theory of Computing (STOC) , pages =
[19]

van Handel, Ramon , journal =
[20]

Zhou, Zhixin and Zhu, Yizhe , year = 2021, volume = 15, journal =

2021
[21]

2008 , publisher =

The Probabilistic Method , author =. 2008 , publisher =

2008
[22]

Vershynin, Roman , publisher =
[23]

Dartois, Stephane and McKenna, Benjamin. 2024

2024
[24]

Preprint arXiv:2507.06522 , year=

Balanced multi-species spin glasses , author=. Preprint arXiv:2507.06522 , year=

arXiv
[25]

Journal of Functional Analysis , volume=

Lata. Journal of Functional Analysis , volume=. 2025 , publisher=

2025
[26]

Preprint arXiv:2603.01342 , year=

A moment-based approach to the injective norm of random tensors , author=. Preprint arXiv:2603.01342 , year=
[27]

Preprint arXiv:2503.10580 , year=

arXiv
[28]

Information and Inference: A Journal of the IMA , volume=

Sharp concentration of simple random tensors , author=. Information and Inference: A Journal of the IMA , volume=
[29]

Jain, Prateek and Oh, Sewoong , booktitle =
[30]

Biometrika , year = 2020, pages =

Lei, Jing and Chen, Kehui and Lynch, Brian , title =. Biometrika , year = 2020, pages =

2020
[31]

Hoffmann, Christopher and Kahle, Matthew and Paquette, Elliot , journal =
[32]

Mathematische Zeitschrift , volume = 27, pages =
[33]

2024 , publisher=

Park, Jinyoung and Pham, Huy Tuan , journal=. 2024 , publisher=

2024

Pith tools

Reviewed July 9, 2026 · model on record in the stance chip above.

[1] [1]

Symposium on Theory of Computing (STOC) , pages =

Joel Friedman and Jeff Kahn and Endre Szemer. Symposium on Theory of Computing (STOC) , pages =

work page

[2] [2]

Seginer, Yoav , journal =

work page

[3] [3]

Combinatorica , volume = 15, number = 1, pages =

On the Second Eigenvalue of Hypergraphs , author =. Combinatorica , volume = 15, number = 1, pages =

work page

[4] [4]

Combinatorica , year = 2006, volume = 26, pages =

Yonatan Bilu and Nathan Linial , title =. Combinatorica , year = 2006, volume = 26, pages =

work page 2006

[5] [5]

Computational Complexity Conference (CCC) , volume =

Tommaso d'Orsi and Luca Trevisan , title =. Computational Complexity Conference (CCC) , volume =

work page

[6] [6]

Luca Trevisan , howpublished =

work page

[7] [7]

Allen and Ryan O'Donnell and David Witmer , title =

Sarah R. Allen and Ryan O'Donnell and David Witmer , title =. Symposium on Foundations of Computer Science (FOCS) , pages =

work page

[8] [8]

Symposium on Theory of Computing (STOC) , pages =

Uriel Feige , title =. Symposium on Theory of Computing (STOC) , pages =

work page