A Spectral Proof of the Hypergraph Moore Bound

Alexander Schmidhuber; Matthew B. Hastings

REVIEW 3 major objections 6 minor 1 cited by

This paper proves the exact density–girth tradeoff conjectured in 2008 for uniform hypergraphs: every k-uniform hypergraph that is dense enough must contain a short even cover, with constants independent of k.

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 00:52 UTC pith:SLVS6ZBC

load-bearing objection Exact hypergraph Moore bound proved by a genuinely new spectral trace-counting argument; odd-uniformity section is compressed but the proof appears sound. the 3 major comments →

arxiv 2607.26028 v1 pith:SLVS6ZBC submitted 2026-07-28 math.CO cs.DMquant-ph

A Spectral Proof of the Hypergraph Moore Bound

Alexander Schmidhuber , Matthew B. Hastings This is my paper

classification math.CO cs.DMquant-ph MSC 05C6505C3515A42

keywords even coverhypergraph girthextremal hypergraph theoryspectral normtrace methodlifted walkslinear dependenciesdensity thresholds

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.

An even cover in a k-uniform hypergraph is a nonempty collection of edges in which every vertex appears an even number of times; for ordinary graphs it is a union of cycles, so the smallest even cover is the hypergraph analogue of girth. The paper settles a 2008 conjecture in full: for every k ≥ 3 and every 1 ≤ ℓ ≤ n, a k-uniform hypergraph on n vertices either has an even cover of size O(ℓ log(en/ℓ)) or has at most O(n^{k/2}/ℓ^{k/2-1}) edges, with absolute constants that do not depend on k. This is the exact hypergraph form of the Moore bound, with no polylogarithmic losses and a slightly sharper cover size than the conjectured O(ℓ log n). A sympathetic reader should care because the result is a sharp extremal statement about sparse binary vectors: any sufficiently large family of weight-k vectors contains a small nonempty subfamily XORing to zero, which is the certificate that underpins low-density parity-check codes and refutation algorithms for random constraint satisfaction problems.

Core claim

The central claim is Theorem 1.1: there exist absolute constants A,C > 0 such that for every k ≥ 3, every 1 ≤ ℓ ≤ n, and every k-uniform hypergraph H on [n], either g_ev(H) ≤ A ℓ log(en/ℓ) or |H| ≤ C n^{k/2}/ℓ^{k/2-1}, where g_ev(H) is the size of the smallest even cover. The proof works by building a graph whose vertices are the ℓ-subsets of [n], joining two vertices when they differ by a hyperedge, and examining a degree-normalized adjacency operator. A universal lower bound gives its norm at least 1/2. Under the assumption that no even cover of size about ℓ log(en/ℓ) exists, the trace method turns the 2s-th moment of the operator into a count of closed walks, and these walks are lifted to

What carries the argument

The central object is the reweighted adjacency operator K = Γ^{-1/2} A_G Γ^{-1/2}, where A_G is the adjacency matrix of the ℓ-slice graph, D is the diagonal degree matrix, and Γ = D + d̄ I with d̄ the average degree. A universal lower bound ∥K∥ ≥ 1/2 comes from testing on Γ^{1/2}1. The upper bound is obtained by the trace method: for integer s, ∥K∥^{2s} ≤ Tr K^{2s}, and the trace counts closed walks of length 2s. The paper lifts the graph to states (S,M), where S is a row and M is the set of hyperedges used an odd number of times so far; the lifted walk operator is L. A key lemma states that if the lifted edges are oriented so that every state has incoming weight at most κ, then ∥L∥ ≤ 2√(κ/d

Load-bearing premise

Everything rests on being able to direct every memory-augmented transition so that no augmented state receives more than about 2ℓ total weight; this is the step where the theorem's whole weight is carried, and the paper proves it with a distinct-representatives condition inside small windows.

What would settle it

Build a k-uniform hypergraph on n vertices with roughly C n^{k/2}/ℓ^{k/2-1} edges and no even cover smaller than Aℓ log(en/ℓ), for some k=3 or 4 and ℓ just below n/2; a computer search over random or adversarial edge sets for the actual constants A,C would either exhibit a counterexample or confirm the theorem in that window.

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

If this is right

For every k ≥ 3, any k-uniform hypergraph with more than C n^{k/2}/ℓ^{k/2-1} edges contains an even cover of size at most A ℓ log(en/ℓ); the previous polylogarithmic slack in the density threshold is gone.
The constants A and C do not depend on k or ℓ, so the statement holds uniformly across uniformities and hierarchy levels.
Because an even cover is a nonempty subfamily XORing to zero, the theorem says any family of more than C n^{k/2}/ℓ^{k/2-1} binary vectors of weight k has a linear dependence involving at most A ℓ log(en/ℓ) vectors.
The cover-size bound O(ℓ log(en/ℓ)) is slightly stronger than the conjectured O(ℓ log n), automatically improving the even-cover length at intermediate densities.
The construction of a low-in-weight orientation of lifted transitions gives a finite, explicit certificate for the density threshold, not just an existence proof.

Where Pith is reading between the lines

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

A reader might infer that the exact orientation lemma is a transferable tool: any graph or operator whose edges can be oriented with bounded incoming weight under a girth-like constraint will inherit the same ∥L∥ ≤ 2√(κ/d̄) bound, opening similar Moore-type results for other slice hierarchies.
The pairing-plus-contention trick for odd uniformity suggests a general recipe for converting even-slice spectral proofs to odd order by treating pairs of labels as steps and charging contention per port; this may apply to other spectral slice hierarchies beyond uniform hypergraphs.
If the absolute constants A,C are made explicit, the proof could yield finite-length bounds for low-density parity-check codes: the smallest even cover is the stopping distance, and the theorem would give a guaranteed stopping distance for sufficiently dense parity-check matrices.
One testable extension: run the same trace/orientation argument on weighted hypergraphs or hypergraphs with variable uniformity; the weighted analogue of the norm lemma suggests the same threshold should hold with edge weights replacing edge counts.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

Exact hypergraph Moore bound proved by a genuinely new spectral trace-counting argument; odd-uniformity section is compressed but the proof appears sound.

read the letter

You should know this paper is the real thing: it proves Feige's 2008 conjecture exactly, with k-independent constants and no polylog losses. The method is new — a parity lift on Kikuchi graphs with memory states, plus a Hall-based orientation that caps incoming weight. The even-k part is clean and I traced it through; the conversion from hyperedge density to average degree and the spectral lower bound both check out. The orientation lemma (2.7) is load-bearing, and the witness-counting argument is sound. The trace identity with the memory truncation works because the girth hypothesis forces every closed walk to return to empty memory.

The odd-k section is much denser. It builds spread bundles, weights moves by contention, and then runs a paired trace estimate with a more complicated orientation. I read the key lemmas (3.5, 3.6, Prop 3.7) and they are consistent: the capacity bound (3.6) and the Cauchy–Schwarz lower bound on total weight are legitimate. The residual risk is that this part is not machine-checked and has many moving parts, so a small counting error would be easy to hide. I did not find one, and the stress-test note agrees. Section 4's crossed-halves trick for k > 400ℓ is plausible; the half-injectivity and the density bound (4.2) hold up.

If I have a complaint, it's the same one I'd have for any dense combinatorics paper at this level: the odd case is hard to verify, and the authors could have done more to separate the core idea from the bookkeeping. That is a presentation issue, not a correctness issue. The citation pattern is honest; the concurrent work [14] is acknowledged, and the independence claim seems credible rather than defensive. The companion paper [1] is cited for applications, not as a crutch.

This paper deserves a serious referee. The even case alone is significant, and the odd case is likely correct. I would send it to review without hesitation. If I were refereeing, I'd ask for a slightly expanded proof of Prop 3.7, mainly for the benefit of the community, and a clearer statement of which constants are tracked where.

Who gets value: researchers in combinatorics, coding theory, and spectral graph theory; anyone working on even covers, LDPC codes, or random CSP refutation. I'd cite it and would bring it to reading group.

Recommendation: send to peer review; the math appears sound and the result settles a conjecture.

Referee Report

3 major / 6 minor

Summary. The paper proves Feige's 2008 hypergraph Moore bound conjecture: for every k ≥ 3 and 1 ≤ ℓ ≤ n, any k-uniform hypergraph on n vertices either contains an even cover of size O(ℓ log(en/ℓ)) or has at most O(n^{k/2}/ℓ^{k/2-1}) edges, with absolute constants independent of k. The proof works through Kikuchi matrices and a trace-method counting of closed walks, introducing a parity-lift that records hyperedges used an odd number of times, then orienting the lifted graph so that every state has small incoming weight. The even-k case (Section 2) is built on a sharp orientation argument using Hall's theorem and systems of distinct representatives; the odd-k case (Section 3) uses spread bundles, balanced transitions, and contention weights; the remaining regimes are handled in Section 4 via a syndrome-counting argument and a crossed-halves construction. The paper also develops spectral bounds for Kikuchi matrices that may be of independent interest.

Significance. If correct, this settles a conjecture that has been open since 2008 and improves prior work by removing all polylogarithmic losses and giving constants independent of k. The trace-lift and orientation techniques are novel and potentially reusable, and the spectral bounds for Kikuchi matrices are likely to find further applications. The paper includes explicit, checkable lemmas with detailed proofs, and the overall structure is clear. The companion-paper application to planted k-XOR refutation is a plausible further pay-off. The main residual risk is the compression of the odd-k and crossed-halves arguments, which are intricate but internally consistent on inspection.

major comments (3)

[§3.1–§3.2 (Definition 3.2, Lemma 3.4, Lemma 3.5)] The spread-bundle packing and the contention-weight calculation are the heart of the odd-k proof, but the exposition is dense and several steps are compressed. For example, the proof of Lemma 3.5 asserts that 'an instance e′ ≠ e with (S,F) ∈ P(e′) has a label pair {F,J′} with J′ ∈ B(F)' — this is true only if the set of instances has been defined without multiplicity, which is not stated. Please clarify whether instances are identified with their row/label quadruples or counted with multiplicity, and whether the bound (3.8) is in the latter case robust. This does not appear to break the proof, but it is load-bearing for the incoming-weight capacity (3.6) and should be made precise.
[§3.3, Proposition 3.7, tagged representatives] The tagged-vector independence argument introduces formal coordinates τ_B with one coordinate per bundle. The claim that a minimal dependency C meets every bundle evenly because of the tag coordinates is valid, but the subsequent inequality p − 1 ≤ |W| + β requires that the union of the residuals of C is contained in W, which is stated only implicitly. Also, the final bound p ≤ 2|W| + 2 depends on β ≤ p/2 and needs to be spelled out; as written, the chain 'p−1 ≤ |W|+β, whence p≤2|W|+2' is not immediate. Please expand this argument.
[§4.2, crossed halves] The reduction in the crossed-halves argument is the most delicate part of the paper. The proof of the density bound (4.2) is correct, but the claim that 'the proof of Proposition 3.7 now applies verbatim' requires checking that the port-capacity and in-weight arguments go through with rows of size two or one and with moving sets replaced by signed halves. The text gives a brief justification, but the linear map 1_{(D,±)} ↦ 1_D used in the trace-comparison step may not preserve the structure of the lifted walk if the two halves of a residual have different signs. I traced the argument and believe it works, but the manuscript should state the formal correspondence between the lifted walks in the signed-half graph and those in the original odd-k graph more explicitly.

minor comments (6)

[§1, Eq. (1.1)] The chain of inequalities (1.1) is central, but the notation N is introduced only later in Eq. (2.2) and used in (1.1) without definition. Please define N = binom(n,ℓ) before or at (1.1).
[§2.2, Lemma 2.4] The phrase 'memory never exceeds s' in the proof of Lemma 2.4 is justified by the sentence before it, but the argument that a hyperedge in memory must be used again before closure is only stated for the even case. In the odd case (Prop. 3.7) the analogous statement holds with 2s; please make the parallel explicit.
[§3.2, Eq. (3.4)] The factor 1/2 in the lower bound μ_q ≥ (1/8) m_q h_q B_q^2 binom(n−2q,ℓ−q) is justified by 'each instance arises from at most two such choices', but the preceding sentence says a fixed pair creates at least (1/2)B_q^2 binom(...) instances. Please reconcile the two factors: one half comes from double-counting the S choices and the other from the pair being unordered? This is likely correct but should be written unambiguously.
[§4.1, Lemma 4.1] The proof of Lemma 4.1 uses the injectivity of the map T ↦ Σ_{F∈T} 1_F. This is only valid if two subfamilies with the same image differ by an even cover, which is true because the symmetric difference of the two subfamilies is an even cover of size at most 2t. The manuscript states this, but the injectivity claim is not explicitly labeled; consider adding a sentence.
[References] Reference [14] is cited as 'arXiv:2607.14068, version 2, 2026' but the arXiv identifier appears to be in a different numbering range from the present paper. Please update the citation if the number is incorrect, and add the title/authors' affiliation if available.
[Global] The paper uses 'A' and 'C' for absolute constants throughout, with A fixed in Theorem 3.1 to 165 but not given a numeric value in Theorem 2.1. It would help the reader if the text stated whether these constants are the same in all theorems or can be taken as the maxima of the constants appearing in the proofs.

Circularity Check

0 steps flagged

No significant circularity; the proof is a self-contained contrapositive spectral argument.

full rationale

The derivation chain is self-contained and the target bound appears only as the statement to be proved. The main contradiction combines a universal lower bound on the reweighted Kikuchi operator (test vector argument) with an upper bound derived from the high-girth hypothesis via the lifted walk operator. The load-bearing steps are structural: the trace comparison in Lemma 2.4/Proposition 3.7, the orientation in-weight caps in Lemma 2.7 and Proposition 3.7, the Hall/SDR independence lemmas (Lemma 2.6 and the tagged-representative argument), and the port-capacity inequality (3.6). None of these steps uses the Moore bound itself or any fitted quantity. The constants A and C are absolute, not tuned to data, and the proof gives explicit density bounds. The only self-citations are to the companion paper [1] and, for physical interpretation, [11]; these are contextual and not load-bearing for any theorem in the paper. No parameter is fitted and then called a prediction, no uniqueness theorem from the authors' prior work is invoked, and no known result is merely renamed. Thus there is no circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 5 axioms · 4 invented entities

The proof introduces several technical constructions—parity lift, spread bundles, contention weights, bundle tags—but all are definitions within the proof, not physical postulates. No parameters are fitted; the absolute constants A and C are chosen and not optimized. External inputs are standard theorems (Hall, trace inequality, Cauchy-Schwarz/AM-GM, Stirling).

axioms (5)

standard math Hall's marriage theorem (system of distinct representatives)
Invoked in Lemmas 2.6, 2.7, and 3.7 to build the orientation's witness properties from F2-independence.
standard math Trace inequality for real symmetric matrices: ||M||^{2s} ≤ Tr M^{2s}
Used in eq. (1.1) and (2.5) to turn a spectral norm upper bound into a closed-walk count.
standard math Cauchy-Schwarz and AM-GM inequalities
Used in Lemma 2.5 (AM-GM) and eq. (3.7) (Cauchy-Schwarz on contention weights).
standard math Stirling-type binomial estimates
Used in Lemmas 2.2, 2.3, 3.6, and 4.2 to keep constants k-independent.
domain assumption Simple k-uniform hypergraph model with even cover = F2 linear dependence
The entire framing treats hyperedges as incidence vectors over F2 and an even cover as a nonempty dependency; all hypergraphs are simple sets.

invented entities (4)

Parity-lift memory state (S,M) no independent evidence
purpose: Tracks hyperedges used an odd number of times so that closed lifts correspond to walks avoiding short even covers.
Mathematical proof device, not a physical postulate; no empirical handle outside the proof.
Spread bundles no independent evidence
purpose: Decomposes odd-uniformity hypergraphs into bundles of residual-disjoint pairs so the even-k machinery applies two-at-a-time.
Construction used only inside the proof.
Contention weights w_e = 1/δ_e no independent evidence
purpose: Assigns capacities to row-hyperedge ports so heavily shared ports do not break the in-weight bound.
Auxiliary weighting; no independent evidence needed.
Formal bundle tags τ_B no independent evidence
purpose: Adds one coordinate per bundle to make residual vectors independent, restoring centers in the no-even-cover argument.
Proof device.

pith-pipeline@v1.3.0-alltime-deepseek · 15061 in / 44296 out tokens · 395750 ms · 2026-08-01T00:52:14.351461+00:00 · methodology

0 comments

read the original abstract

A nonempty subfamily of a $k$-uniform hypergraph is an \emph{even cover} if every vertex lies in an even number of its hyperedges; for $k=2$ these are edge-disjoint unions of cycles, so the minimum size of an even cover is the natural hypergraph analogue of girth. We prove Feige's 2008 conjecture on the hypergraph Moore bound: there are absolute constants $A$ and $C$ (independent of $k$) such that for every $k\ge3$ and every $1\le\ell\le n$, any $k$-uniform hypergraph on $n$ vertices with more than $C\,n^{k/2}/\ell^{k/2-1}$ hyperedges contains an even cover of size at most $A\,\ell\log(en/\ell)$. Our proof is based on sharp spectral bounds for Kikuchi matrices, which we expect to be of independent interest; we apply them to the refutation of random constraint satisfaction problems in a companion paper.

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

The Kikuchi Hierarchy is Sharp for $k$XOR
cs.DS 2026-07 conditional novelty 8.0

Normalized Kikuchi matrices achieve the sharp m ~ rho^{-2} n^{k/2} / ell^{k/2-1} trade-off with no logarithmic loss for detection, recovery, and two-sided refutation in kXOR, with matching low-degree lower bounds.

Reference graph

Works this paper leans on

14 extracted references · 1 linked inside Pith · cited by 1 Pith paper

[1]

Schmidhuber and M

A. Schmidhuber and M. B. Hastings. Sharp Spectral Algorithms and Lower Bounds for Planted kXOR. Companion paper
[2]

N. Alon, S. Hoory, and N. Linial. The Moore bound for irregular graphs.Graphs and Combinatorics, 18:53–57, 2002

2002
[3]

U. Feige. Small linear dependencies for binary vectors of low weight. InBuilding Bridges: Between Mathematics and Computer Science, pages 283–307. Springer, 2008

2008
[4]

Naor and J

A. Naor and J. Verstra¨ ete. Parity check matrices and product representations of squares.Combinatorica, 28:163–185, 2008

2008
[5]

Feige, J

U. Feige, J. H. Kim, and E. Ofek. Witnesses for non-satisfiability of dense random 3CNF formulas. In Proceedings of FOCS, pages 497–508, 2006

2006
[6]

Guruswami, P

V. Guruswami, P. K. Kothari, and P. Manohar. Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. InProceedings of STOC, pages 678–689, 2022

2022
[7]

Hsieh, P

J.-T. Hsieh, P. K. Kothari, and S. Mohanty. A simple and sharper proof of the hypergraph Moore bound. InProceedings of SODA, pages 2324–2344, 2023

2023
[8]

A. S. Wein, A. El Alaoui, and C. Moore. The Kikuchi hierarchy and tensor PCA. InProceedings of FOCS, pages 1446–1468, 2019

2019
[9]

M. B. Hastings,Classical and Quantum Algorithms for Tensor Principal Component Analysis, Quantum4, 237 (2020)

2020
[10]

Hsieh, P

J.-T. Hsieh, P. K. Kothari, S. Mohanty, D. Munh´ a Correia, and B. Sudakov. Small even covers, locally decodable codes and restricted subgraphs of edge-colored Kikuchi graphs.International Mathematics Research Notices, 2025(5), 2025

2025
[11]

Schmidhuber, R

A. Schmidhuber, R. O’Donnell, R. Kothari, and R. Babbush,Quartic quantum speedups for planted inference, Phys. Rev. X15, 021077 (2025)

2025
[12]

F¨ uredi and J

Z. F¨ uredi and J. Koml´ os. The eigenvalues of random symmetric matrices.Combinatorica, 1:233–241, 1981

1981
[13]

R. Kikuchi. A theory of cooperative phenomena.Physical Review, 81(6):988–1003, 1951

1951
[14]

A. S. Bandeira, D. Kunisky, P. Nizi´ c-Nikolac, L. Pesenti, and R. Wang. The hypergraph Moore bound. arXiv:2607.14068, version 2, 2026. 14

Pith/arXiv arXiv 2026

[1] [1]

Schmidhuber and M

A. Schmidhuber and M. B. Hastings. Sharp Spectral Algorithms and Lower Bounds for Planted kXOR. Companion paper

[2] [2]

N. Alon, S. Hoory, and N. Linial. The Moore bound for irregular graphs.Graphs and Combinatorics, 18:53–57, 2002

2002

[3] [3]

U. Feige. Small linear dependencies for binary vectors of low weight. InBuilding Bridges: Between Mathematics and Computer Science, pages 283–307. Springer, 2008

2008

[4] [4]

Naor and J

A. Naor and J. Verstra¨ ete. Parity check matrices and product representations of squares.Combinatorica, 28:163–185, 2008

2008

[5] [5]

Feige, J

U. Feige, J. H. Kim, and E. Ofek. Witnesses for non-satisfiability of dense random 3CNF formulas. In Proceedings of FOCS, pages 497–508, 2006

2006

[6] [6]

Guruswami, P

V. Guruswami, P. K. Kothari, and P. Manohar. Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. InProceedings of STOC, pages 678–689, 2022

2022

[7] [7]

Hsieh, P

J.-T. Hsieh, P. K. Kothari, and S. Mohanty. A simple and sharper proof of the hypergraph Moore bound. InProceedings of SODA, pages 2324–2344, 2023

2023

[8] [8]

A. S. Wein, A. El Alaoui, and C. Moore. The Kikuchi hierarchy and tensor PCA. InProceedings of FOCS, pages 1446–1468, 2019

2019

[9] [9]

M. B. Hastings,Classical and Quantum Algorithms for Tensor Principal Component Analysis, Quantum4, 237 (2020)

2020

[10] [10]

Hsieh, P

J.-T. Hsieh, P. K. Kothari, S. Mohanty, D. Munh´ a Correia, and B. Sudakov. Small even covers, locally decodable codes and restricted subgraphs of edge-colored Kikuchi graphs.International Mathematics Research Notices, 2025(5), 2025

2025

[11] [11]

Schmidhuber, R

A. Schmidhuber, R. O’Donnell, R. Kothari, and R. Babbush,Quartic quantum speedups for planted inference, Phys. Rev. X15, 021077 (2025)

2025

[12] [12]

F¨ uredi and J

Z. F¨ uredi and J. Koml´ os. The eigenvalues of random symmetric matrices.Combinatorica, 1:233–241, 1981

1981

[13] [13]

R. Kikuchi. A theory of cooperative phenomena.Physical Review, 81(6):988–1003, 1951

1951

[14] [14]

A. S. Bandeira, D. Kunisky, P. Nizi´ c-Nikolac, L. Pesenti, and R. Wang. The hypergraph Moore bound. arXiv:2607.14068, version 2, 2026. 14

Pith/arXiv arXiv 2026