Parity families and a kernel-averaged L-function for near-Ramanujan signings

Vaibhav Suvagiya

REVIEW 2 major objections 3 minor 13 references

Parity families and a kernel-averaged L-function for near-Ramanujan signings

T0 review · 2 major / 3 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read This paper proves ε-versions of the Bilu-Linial conjecture by averaging over a constrained parity family of signings, showing the spectral-radius bound reduces to counting non-backtracking walks.

desk verdict Real new machinery, but the headline ε-theorems overclaim: the final step evaluates n^{1/(2 log n)} as 1 instead of e^{1/2}. read the letter →

arxiv 2607.17343 v1 pith:NRI3OOHS submitted 2026-07-19 math.CO cs.DMmath.SP

Vaibhav Suvagiya This is my paper · ORCID

classification math.COcs.DMmath.SP MSC 05C5005C38

keywords signingBilu-LinialconjectureRamanujangraphsparityfamilyIharaL-functionnon-backtrackingwalkstracecertificatebicycle-free

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's central claim is an ε-version of the Bilu-Linial conjecture: every d-regular graph that is subcritical at scale log n, and every d-regular graph bicycle-free at radius C log log n / δ, has a signing whose spectral radius is at most 2√(d−1)(1+Cδ log(1/δ))(1+o(1)). The mechanism is to average not over all signings but over the affine F₂ family that makes every short even cycle unbalanced; a master identity then expresses the family-averaged trace as a parity-weighted count of walks confined to the span of the constraint cycles. Averaging the Ihara L-function over this family diagonalizes it: every prime whose parity escapes the span automatically contributes the Ramanujan rate √(d−1), so the whole deviation from Ramanujan is carried by confined primes. The paper proves matched upper and lower bounds on those confined walk counts, using a doubling injection from below and an ear-decomposition/fresh-run encoding from above, plus window and Moore-bound rank lemmas for bicycle-free graphs. If correct, this gives a route to the Bilu-Linial conjecture on locally cycle-rich graphs, while also showing uniform averaging provably cannot certify sub-Kesten signings.

What carries the argument

The master identity (Proposition 7): E_{σ∈F} tr(A_σ^ℓ) = Σ_{z∈W} (−1)^{π(z)} N_ℓ(z), where W is the span of the constraint cycles, π is the parity form, and N_ℓ(z) counts closed walks of parity z. The kernel-averaged L-function identity (Proposition 10) diagonalizes the family-averaged Ihara product, isolating parity-confined primes. The counting engine is the fresh-run/ear decomposition of a non-backtracking walk, whose number of maximal fresh runs equals the cycle rank of its support, plus a window lemma bounding paths in bicycle-free graphs and a Moore-bound rank lemma for irregular graphs.

What would settle it

Compute R_F(k) = (Σ_{z∈W} (−1)^{π(z)} N_{2k}(z))^{1/(2k)} at k=⌈log n⌉ for a d-regular graph that satisfies subcriticality at scale log n but has a small dense core reachable by walks of length log n; if R_F(k) exceeds 2√(d−1)(1+Cδ log(1/δ))·e^{1/2}, the proof's conversion step is invalid and the (1+o(1)) in Propositions 21 and 24 does not follow from the stated hypotheses.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes that for any d-regular graph satisfying either of two local sparsity hypotheses—subcriticality at scale log n, or bicycle-freeness at radius C log log n/δ—there exists a signing σ in the parity family (all short even cycles unbalanced) with ρ(A_σ) ≤ 2√(d−1)(1+Cδ log(1/δ))(1+o(1)). The proof runs through a trace certificate: at k = ⌈log n⌉, the family-averaged even trace is bounded by (2√(d−1)(1+η))^{2k} times a polynomial factor, and Corollary 8 converts this into a spectral-radius bound for some member of the family. The paper also proves structural results: on the hypercube every solution of the quadrilateral system satisfies A_σ² = nI, giving an exa

Load-bearing premise

The load-bearing premise is that the trace certificate is valid at walk length k ≫ log n, while the stated subcriticality/bicycle-free hypotheses are asserted only at scale log n; if they hold only at that shorter scale, the proof's (1+o(1)) factor fails and only an extra e^{1/2} constant is delivered.

Editorial extensions

If this is right

For every d-regular graph satisfying the stated subcriticality hypothesis, the parity family contains a signing with spectral radius within (1+δ log(1/δ))(1+o(1)) of the Ramanujan bound 2√(d−1).
The same conclusion holds for every d-regular graph bicycle-free at radius C log log n/δ, matching the hypothesis scale of the earlier random-signing result but with the conclusion guaranteed inside a constrained family.
Random 2-lift towers satisfy the dilute hypotheses with high probability, so the ε-Bilu-Linial conjecture holds along these sequences.
Uniform averaging over all signings provably cannot certify a spectral radius below the Kesten profile; only the parity-confined average can.
The two-sided interlacing approach via E_σ det(xI−A_σ²) cannot work in general: this polynomial is not real-rooted even for the 4-cycle.

Reading between the lines

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

The proof as written evaluates the trace certificate at k=⌈log n⌉ and uses (n(Ck)^c)^{1/(2k)} = 1+o(1); at k=log n, n^{1/(2k)} = e^{1/2} ≈ 1.649, so the (1+o(1)) factor appears to require the subcriticality/bicycle-free hypotheses to hold at scale (log n)^{1+ε} rather than scale log n as stated in the abstract. If the hypotheses hold only at the stated scale, the argument as written yields an extr
The same parity-averaging idea could be applied to other constraint systems (e.g. only a β_L-fraction of short cycles unbalanced) and would predict that the family's advantage over uniform signings grows with cycle density; this is directly testable on planted-quadrilateral random graphs.
The exact hypercube certificate suggests that graphs in which every 2-path is completed by exactly one 4-cycle admit an entire affine solution family with exact spectral bound; identifying further such two-eigenvalue signed covers would extend the exact regime beyond Q_n.

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

Colleague, here's my read.

The paper has real, new machinery. Proposition 7 (the master identity turning the sign problem into a parity-weighted walk sum over W), Proposition 10 (the kernel-averaged Ihara L-function diagonalization), the exact hypercube certificate (Prop 5), and the non-real-rootedness obstruction (Remark 6) all look correct and are genuinely new relative to the cited literature. The experimental section is unusually careful: matched budgets, conditioned-uniform controls, and honest disclosure of the variance-outlier artifact.

The soft spot is in the two ε-theorems, and it is not cosmetic. Both Prop 21 and Prop 24 conclude by evaluating (n(Ck)^c)^{1/(2k)} at k=⌈log n⌉ as 1+O(log log n/log n). That is false: n^{1/(2k)} = exp((log n)/(2⌈log n⌉)) → e^{1/2} ≈ 1.649. So the proofs as written give ρ ≤ 2√(d−1)·e^{1/2}·(1+δ)^{...}·(1+o(1)), not the stated (1+o(1)). To get the claimed bound you need k≫log n, which means the subcriticality/bicycle-free hypotheses must hold at scale (log n)^{1+ε} rather than “scale log n” as in the abstract. This is load-bearing: it is the step that converts the counting bounds into the headline inequality. I checked the actual line in the proof of Prop 24 — it says exactly what the stress-test flagged. The paper’s own Corollary 8 already shows the uniform average carries this n^{1/(2k)} obstruction, so the mistake is not isolated.

The error is localized and plausibly repairable — either restate the constant or strengthen the scale hypotheses. The heavy counting lemmas (Props 16, 19, 20, 22) I could not verify line-by-line, but they are plausible and the experimental evidence supports the general picture.

Who is this for? Researchers working on Bilu-Linial, signed spectra, and Ihara zeta functions. The core identities and the negative result (no two-sided interlacing via the expected polynomial) are worth engaging with. The ε-theorems as stated should not be cited without the e^{1/2} caveat.

Recommendation: send to peer review. The paper deserves a serious referee despite the flawed conclusion; the referee should insist on fixing the k-scaling argument before acceptance.

Referee Report

2 major / 3 minor

Summary. The paper studies affine F_2 families of signings of a d-regular graph that make every even cycle of length at most L unbalanced. It proves a master identity (Prop. 7) expressing the family-averaged even trace as a parity-weighted sum over the cycle-span W, and a kernel-averaged Ihara L-function identity (Prop. 10). It then develops counting bounds for totally even and parity-confined non-backtracking walks under two regimes: (r0,δ)-subcritical at scale ℓ and bicycle-free at radius R. These are assembled via Cor. 8 into ε-versions of the Bilu–Linial conjecture: Propositions 21 and 24 claim signings with ρ ≤ 2√(d−1)(1+Cδlog(1/δ))(1+o(1)) (bicycle-free) and ρ ≤ 2√(d−1)(1+δ)^{4(r0+2)}(1+O(log log n/log n)) (dilute). The paper also gives an exact hypercube certificate and a counterexample to real-rootedness of E_σ det(xI−A_σ²). The decisive quantitative step in both theorems is the estimate (n(Ck)^c)^{1/(2k)} = 1+O(log log n/log n) at k=⌈log n⌉, which is false: n^{1/(2k)}→e^{1/2}.

Significance. If the scaling issue is repaired, the paper's structural contributions are significant: a clean conversion of the sign problem to a counting problem, a mechanism showing that uniform averaging cannot certify sub-Kesten signings, a new route to near-Ramanujan signings on dilute/bicycle-free graphs within a constrained parity family, and a decisive obstruction to two-sided interlacing. The exact hypercube certificate, the matched counting bounds, and the extensive exact computational verification (with code provided) are concrete strengths. However, the headline (1+o(1)) consequences are not established at the stated hypothesis scales because of the asymptotic error detailed below.

major comments (2)

[Prop. 24, proof, final step] The proof sets k=⌈log n⌉ and concludes via (n(Ck)^c)^{1/(2k)} = 1+O(log log n/log n). With k=⌈log n⌉, n^{1/(2k)} = exp((log n)/(2⌈log n⌉)) → e^{1/2}, and (Ck)^{c/(2k)} → 1. Thus the factor is e^{1/2}(1+o(1)), not 1+o(1). Corollary 8 therefore yields ρ ≤ 2√(d−1)(1+δ)^{4(r0+2)} e^{1/2}(1+o(1)), not the stated display. This invalidates the (1+o(1)) claim in Prop. 24 and the abstract's dilute-regime consequence. The error is local and repairable: taking k=(log n)^{1+ε} (with corresponding strengthening of the subcriticality scale) or explicitly stating the constant e^{1/2} would fix it.
[Prop. 21, proof, final sentence] The same asymptotic error appears in the bicycle-free theorem. The constant K defined in Prop. 21 contains a factor n, so (C''K(Ck)^2)^{1/(2k)} includes n^{1/(2k)}→e^{1/2} when k=⌈log n⌉. The sentence "which is the claim" is therefore false: the proof delivers an extra constant e^{1/2} times the stated right-hand side. This is load-bearing because this step converts the counting bound into the abstract's headline inequality for the bicycle-free regime.

minor comments (3)

[Prop. 24, proof] The exponent c in (n(Ck)^c) is never defined; it should be the explicit exponent 3(r0+1)^2+2 appearing in the preceding display.
[Abstract and Prop. 24] The abstract says "subcritical at scale log n" while Proposition 24 states the hypothesis at ℓ=2⌈log n⌉. These should be aligned, and the base of logarithms should be specified; the erroneous e^{1/2} estimate is independent of the base, but clarity is needed.
[Prop. 16, proof] The fresh-run encoding says run ends are 'visible to a decoder who knows G and the visited set'; since the decoder does not know the visited set at the start, the encoding/decoding procedure should be described more explicitly.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: the trace/L-function reduction to counting is genuine; the only flagged item is a minor, non-load-bearing self-citation to the companion note. The k=ceil(log n) constant issue is a correctness concern, not circularity.

full rationale

The central derivation chain is self-contained. Corollary 8 is a valid moment inequality (min rho <= R_F(k)); Proposition 7 computes the family-averaged trace as a parity-weighted sum over W by elementary character orthogonality; Proposition 22 and Lemmas 19/20 are counting bounds under the stated subcritical/bicycle-free hypotheses; Proposition 24 assembles these with the non-backtracking transfer of Lemma 23. None of these steps assumes the target spectral bound, and no parameter is fitted to data. The paper also explicitly disclaims that the L-function identity by itself bounds min rho (Section 9: 'it does not by itself bound min_{sigma in F} rho'), so the identities are not disguised as predictions. The only self-citation is the unpublished companion note [4], used for exact circulant evaluations and side remarks in Section 7; it is not load-bearing for Propositions 21/24 or the master identities. The reader-identified arithmetic issue at k = ceil(log n) — where (n(Ck)^c)^{1/(2k)} is e^{1/2}+o(1), not 1+o(1) — would affect the stated (1+o(1)) constant, but it is a correctness/overclaim issue, not a circularity: it does not make any derived quantity equal to an input by construction. Score 2 is assigned only for the minor, non-load-bearing self-citation.

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

No free parameters are fitted to data: δ, r_0, Λ, L, R are quantified hypothesis constants and the constants C are asymptotic. No invented entities are postulated. The load-bearing assumptions are the local-growth hypotheses (subcriticality conditions (i)-(ii); bicycle-free radius) and consistency of the parity system (1), which the paper itself shows fails for K_4-containing graphs (Lemma 4). Note the hidden scale requirement identified in the weakest_assumption: the proofs silently need the hypotheses to hold at scale ≫ log n.

assumptions (8)

domain assumption Subcriticality at scale ℓ: every connected min-degree-2 subgraph H with ≤ ℓ edges has cycle rank ≤ r_0 (condition (i)) and closed NB-walk counts c_H(t) ≤ 2|E(H)|(t+1)^{3r_0}(1+δ)^t (condition (ii))
Section 10 definition; the entire counting argument of Props 16/22 runs through (ii); Remark 14 notes K_d violates (ii).
domain assumption Bicycle-free at radius R: every ball of radius R contains at most one cycle (window lemma, Lemmas 19-20, Prop 21)
Used to bound stale-path entropy in bicycle-free supports; the paper argues the radius C log log n/δ is sharp in form via tree-burst gadgets.
domain assumption Consistency of the parity system (1) (every even cycle of length ≤ L unbalanced)
Lemma 4: K_4 makes the full system inconsistent; the theorems consequently quantify over 'any consistent family' W, and for K_4-containing graphs the method is silent.
standard math Bass's Ihara-Bass determinant identity det(I−uB_σ) = ∏_p (1−σ(p)u^{|p|})
Cited [2]; input to the kernel-averaged L-function identity (Prop 10).
standard math Moore bound for irregular graphs (Alon-Hoory-Linial)
Cited [1]; used in Lemma 20's rank bound via n_i ≥ (d̄_i−1)^R.
standard math Equality case of Wielandt's theorem: ρ(B_{K_d,σ}) = ρ(B_{K_d}) iff σ is switching-equivalent to all-plus or all-minus
Prop 13 proof; load-bearing for the K_d trapping lower bound; no reference or derivation given.
standard math Strong connectivity of the non-backtracking digraph of a connected min-degree-2 non-cycle graph, with diameter ≤ 2s−1
Lemma 15; cited to Kotani-Sunada [10].
ad hoc to paper Exact spectral evaluations of signed circulants C_n(1,2) at 2√2 (companion note [4], 'in preparation')
Central empirical support in §7; referenced but unavailable; must be treated as unverified.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Parity families and a kernel-averaged L-function for near-Ramanujan signings." pith.science (2026). https://pith.science/paper/NRI3OOHS

@misc{pith2026260717343,
  author       = {Pith},
  title        = {Pith review of: Parity families and a kernel-averaged L-function for near-Ramanujan signings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NRI3OOHS}},
  note         = {Machine review of arXiv:2607.17343}
}

abstract

For a signing $\sigma$ of a $d$-regular graph, the spectrum of $A_\sigma$ depends only on the signs of cycles. We study the affine $\mathbb F_2$ family of signings making every short even cycle unbalanced, and show that averaging over it converts the sign problem of the Bilu-Linial conjecture into a counting problem: a master identity expresses the family-averaged trace as a parity-weighted sum over wrap classes confined to the span $W$ of the constraint cycles, and the family-averaged Ihara $L$-function diagonalizes so that every prime whose parity escapes $W$ contributes the Ramanujan rate $\sqrt{d-1}$ automatically. Uniform averaging over all signings, by contrast, provably cannot certify a spectral radius below the Kesten profile. We prove matched upper and lower bounds for the confined walk counts, a doubling injection from below, and from above an ear-decomposition encoding in which the number of fresh runs of a non-backtracking walk equals the cycle rank of its support, combined with a window lemma for bicycle-free graphs and a rank bound via the Moore bound for irregular graphs. Consequences include $\varepsilon$-versions of the Bilu-Linial conjecture: every $d$-regular graph that is subcritical at scale $\log n$, and every $d$-regular graph bicycle-free at radius $C\log\log n/\delta$, admits a signing in the parity family with $\rho(A_\sigma)\le2\sqrt{d-1}(1+C\delta\log(1/\delta))(1+o(1))$. We further identify the necessary hypotheses exactly ($K_d$-trapping; tree-burst gadgets), give an exact certificate on the hypercube, and record a decisive obstruction to two-sided interlacing: $\mathbb E_\sigma\det(xI-A_\sigma^2)$ is not real-rooted, already for the quadrilateral, where it equals $(x^2-4x+2)^2+4$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

13 extracted references · 2 linked inside Pith

[1]

N. Alon, S. Hoory, N. Linial,The Moore bound for irregular graphs, Graphs Combin. 18 (2002), 53-57

2002
[2]

Bass,The Ihara-Selberg zeta function of a tree lattice, Internat

H. Bass,The Ihara-Selberg zeta function of a tree lattice, Internat. J. Math. 3 (1992), 717-797

1992
[3]

Y. Bilu, N. Linial,Lifts, discrepancy and nearly optimal spectral gap, Combinatorica 26 (2006), 495-519

2006
[4]

Suvagiya,Signed circulants at the Ramanujan bound, in preparation, 2026

V. Suvagiya,Signed circulants at the Ramanujan bound, in preparation, 2026

2026
[5]

Bordenave,A new proof of Friedman ’s second eigenvalue theorem and its extension to random lifts, Ann

C. Bordenave,A new proof of Friedman ’s second eigenvalue theorem and its extension to random lifts, Ann. Sci. ´Ec. Norm. Sup´ er. 53 (2020), 1393-1439

2020
[6]

C. D. Godsil, I. Gutman,On the matching polynomial of a graph, in: Algebraic Methods in Graph Theory, 1981. 14

1981
[7]

H ˚ astad,Some optimal inapproximability results, J

J. H ˚ astad,Some optimal inapproximability results, J. ACM 48 (2001), 798-859

2001
[8]

O. J. Heilmann, E. H. Lieb,Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972), 190-232

1972

Show all 13 references

[9]

Huang,Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, Ann

H. Huang,Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, Ann. of Math. 190 (2019), 949-955

2019
[10]

Kotani, T

M. Kotani, T. Sunada,Zeta functions of finite graphs, J. Math. Sci. Univ. Tokyo 7 (2000), 7-25

2000
[11]

A. W. Marcus, D. A. Spielman, N. Srivastava,Interlacing families I: Bipartite Ramanujan graphs of all degrees, Ann. of Math. 182 (2015), 307-325

2015
[12]

Mohanty, R

S. Mohanty, R. O’Donnell, P. Paredes,Explicit near-Ramanujan graphs of every degree, STOC 2020; arXiv:1909.06988

2020 arXiv
[13]

Z. Xu, X. Zhang,An improved upper bound for the Bilu-Linial conjecture, arXiv:2606.28797 (2026). 15

2026 arXiv

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.

[1] [1]

N. Alon, S. Hoory, N. Linial,The Moore bound for irregular graphs, Graphs Combin. 18 (2002), 53-57

2002

[2] [2]

Bass,The Ihara-Selberg zeta function of a tree lattice, Internat

H. Bass,The Ihara-Selberg zeta function of a tree lattice, Internat. J. Math. 3 (1992), 717-797

1992

[3] [3]

Y. Bilu, N. Linial,Lifts, discrepancy and nearly optimal spectral gap, Combinatorica 26 (2006), 495-519

2006

[4] [4]

Suvagiya,Signed circulants at the Ramanujan bound, in preparation, 2026

V. Suvagiya,Signed circulants at the Ramanujan bound, in preparation, 2026

2026

[5] [5]

Bordenave,A new proof of Friedman ’s second eigenvalue theorem and its extension to random lifts, Ann

C. Bordenave,A new proof of Friedman ’s second eigenvalue theorem and its extension to random lifts, Ann. Sci. ´Ec. Norm. Sup´ er. 53 (2020), 1393-1439

2020

[6] [6]

C. D. Godsil, I. Gutman,On the matching polynomial of a graph, in: Algebraic Methods in Graph Theory, 1981. 14

1981

[7] [7]

H ˚ astad,Some optimal inapproximability results, J

J. H ˚ astad,Some optimal inapproximability results, J. ACM 48 (2001), 798-859

2001

[8] [8]

O. J. Heilmann, E. H. Lieb,Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972), 190-232

1972