{"id":"534e8264-0d37-46fe-9f5c-cf615d3483c9","arxiv_id":"2607.07308","paper_version":1,"verdict":"ACCEPT","confidence":"UNKNOWN","novelty_score":8.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"r-uniform Erdős-Rényi hypergraphs exhibit a spectral gap at m ≫ n^{r/2}, proved via an explicit selector process decomposition that also yields sparse tensor norm bounds and a tensor analogue of Seginer's theorem.","lead":"The paper proves that random hypergraphs develop a spectral gap exactly when they have more than n^{r/2} hyperedges, removing logarithmic factors that blocked prior work for 30 years. It also extends Seginer's classical matrix norm theorem to higher-order tensors.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified","rationale":"The reader's verdict of ACCEPT is well-supported. The reader correctly identified the witness set normalization and the covering argument (Lemmas 3.9–3.11) as the most load-bearing element of the proof. I scrutinized this element in detail and found the argument to be sound: the level-set decomposition, the partition into balanced/unbalanced indices, and the coefficient bounds all check out. The Chernoff-based union bounds and the combinatorial counting (Lemma A.1) are standard and correctly applied. The extensions to unbounded entries and the Seginer-type theorem are cleanly derived from the main result. The paper resolves a question open since 1995 (Friedman-Wigderson) and removes polylogarithmic factors that were a recognized barrier in multiple prior works. The proof technique—an explicit implementation of Talagrand's selector process decomposition—is both novel and well-executed. No circularity, no post-hoc fitting, no unstated assumptions were found. The confidence level of UNKNOWN in the reader's verdict is appropriate given that this is a theoretical result without machine-checked proofs or numerical verification, but the mathematical argument is complete and detailed.","tokens_in":21348,"tokens_out":848,"duration_ms":565239,"concrete_test":"Independently verify the coefficient bound in Lemma 3.11 for the first term: specifically, re-derive the inequality chain from the sum Σ_{k∈K₁} Π r^{-k_i} (Σ_{i=2}^r |A_{k,i}|) to the final bound <1/(2r), checking that the split into cases k_i≥k₁ vs k₁≥k_i correctly bounds the geometric series and that the factor (r/(r-1))^{r-1}≤3 is applied correctly. If any step in this chain fails, the solid convex hull inclusion for unbalanced witnesses breaks.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 1.3) follows from Theorem 3.1, whose proof decomposes the selector process into a Bernstein part (Lemma 3.6) and a positive part (Lemma 3.7). The positive part is controlled via a witness set W (Definition 3.8) with normalization φ(S)=√|S|/max(4r²,log²|S|). The reader correctly identifies this as the most fragile structural element. I examined the covering argument (Lemma 3.9) and the coefficient bounds (Lemmas 3.10–3.11) in detail. The level-set decomposition (7) partitions indices into K₀ (balanced) and K₁,...,K_r (unbalanced). For K₀, the total coefficient is bounded by a factorized sum yielding <1/2 (Lemma 3.10). For K_j, the coefficient splits into two terms: one controlled identically to K₀ giving <1/(4r), and the other bounded by splitting the double sum according to whether k_i≥k_1 or k_1≥k_i, yielding <1/(2r) (Lemma 3.11). The Chernoff-based union bounds (Lemmas 3.12–3.13) then control each witness class, with the combinatorial counting handled by Lemma A.1. The reduction from general [−1,1]-valued entries to Ber(Ln^{-1-ε}) (maximizing the tail) is standard. The extension to unbounded entries (Corollary 4.3) via truncation and combination with Boedihardjo's Theorem 4.1 is clean. The Seginer-type extension (Theorem 5.1) follows by combining the sparse bound with the dense bound, using a clipping threshold B that interpolates between regimes. I could not identify a step where the argument fails or relies on an unstated assumption. The normalization φ(S) is unconventional but the verification is complete and each inequality used (e.g., (5), (6), the sum-integral comparison) checks out.","agreement_with_reader":"agree"},"referee_report":{"model":"glm-5.2","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).","tokens_in":21765,"tokens_out":1000,"duration_ms":158898,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"The paper states (Section 1.6) that AI tools were used for literature research and typo scanning. This is transparent and appropriate.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper is a first submission with no self-citations, and the novelty is clearly articulated relative to prior work (Zhou–Zhu, Boedihardjo, Jain–Oh, etc.). The witness-set construction is the load-bearing element, and I verified the covering argument and coefficient bounds in detail. The normalization φ(S) is non-obvious but the proofs of Lemmas 3.10–3.11 check out. I see no reason this should not be accepted after minor revision."},"author_rebuttal":null,"desk_editor":{"model":"glm-5.2","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.","headline":"Solid paper resolving a 30-year-old question; the key technique is an explicit selector process decomposition that actually works","tokens_in":22140,"tokens_out":1573,"would_cite":true,"duration_ms":54794,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"Sparse random hypergraphs show spectral gap at n^{r/2} edges","keywords":[],"falsifier":"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.","tokens_in":21532,"feed_emoji":"📊","tokens_out":1378,"duration_ms":173188,"temperature":0.7,"pith_summary":"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.","feed_headline":"Sparse hypergraphs show spectral gap at n^{r/2} edges","feed_subtitle":"Sharp threshold for random hypergraph spectral gap, removing all logarithmic factors via explicit selector process decomposition","key_machinery":"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).","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Sharp spectral gap threshold for sparse random hypergraphs","Removing log factors from hypergraph spectral gap","Selector process decomposition yields tight hypergraph spectral gap","Improved norm bounds for sparse random tensors","Spectral gap for random hypergraphs without logarithmic slack"],"cache_read_input_tokens":0,"weakest_assumption_plain":"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","fun_headline_variants_meta":{"raw":{"variants":["Sharp spectral gap threshold for sparse random hypergraphs","Removing log factors from hypergraph spectral gap","Selector process decomposition yields tight hypergraph spectral gap","Improved norm bounds for sparse random tensors","Spectral gap for random hypergraphs without logarithmic slack"]},"model":"glm-5.2","effort":"low","cost_usd":0.0,"raw_usage":{"total_tokens":647,"prompt_tokens":578,"completion_tokens":69,"prompt_tokens_details":null},"tokens_in":578,"tokens_out":69,"duration_ms":37066,"temperature":1.0,"reasoning_tokens":null,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-09T14:28:41.518826+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"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.","supporting_citations":[],"review_version":1}