{"id":"32c779f7-a9ad-4c48-93a0-a8080fed7be2","arxiv_id":"2607.18031","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Every connected graph G on n vertices satisfies min{s+(G), s−(G)} ≥ n−1, confirming the Elphick–Farber–Goldberg–Wocjan conjecture.","lead":"The paper proves a long-open spectral graph theory conjecture: in every connected graph, the smaller of the two sums of squared positive and negative adjacency eigenvalues is at least n−1. It does so through a short induction on a new inequality for doubly nonnegative matrices, and the result resolves several related conjectures.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the inductive proof of Theorem 2.1 and its application in Section 3 are internally consistent.","rationale":"The reader identified the no-cut-vertex counting identities as the most delicate step. I agree that this is the point most worth scrutinizing, but I find the identities correct after independent re-derivation: each diagonal entry of M survives in n−1 submatrices, each edge entry survives in n−2 submatrices, and the algebra for sum_v q(G−v) is exact. The cut-vertex and base cases present no hidden difficulties, and the application of Theorem 2.1 to A±∘A± is sound. The central theorem therefore stands. The only caveat is that the claimed Lean formalization cannot be checked from the preprint, but this does not weaken the written proof. Hence the reader's ACCEPT verdict should remain unchanged.","tokens_in":10673,"tokens_out":18643,"duration_ms":172591,"concrete_test":"As a corroborating check, independently recompute the two no-cut-vertex identities, sum_v q(G−v) = (n−2)(q−1) and sum_v T(M−v) = (n−2)T(M)+d0, and verify equation (6) numerically on a random 2-connected graph with a random doubly nonnegative matrix M supported on edges. If both identities and the resulting inequality match, the most delicate averaging step is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I find no load-bearing flaw in the central argument. The proof of Theorem 2.1 is a complete induction. The folding step preserves both the edge sum and 1^T M 1 while restoring zero non-edge entries. In the cut-vertex case, the Gram-vector splitting is valid: non-edges across the two sides make the spans orthogonal, the constructed Gram matrices M1,M2 are doubly nonnegative, and both the edge sum and the total mass split exactly as claimed. In the no-cut-vertex case, I re-checked the two delicate counting identities: sum_v q(G−v) = (n−2)(q−1) and sum_v T(M−v) = (n−2)T(M)+d0. Both are correct. The subsequent Cauchy–Schwarz averaging to (6) and the two-case finishing argument also check out. The reduction in Section 3 from Theorem 2.1 to s±(G) ≤ q(G) uses Hadamard squares A±∘A±, which are doubly nonnegative, and the identities sum_edges (A±)_{uv} = ±(1/2)s±(G) are correct. No hidden assumption or circular step surfaced. The claimed Lean formalization is not independently verifiable from the preprint, but that is a reproducibility limitation, not a correctness defect.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves Conjecture 1.1 of Elphick, Farber, Goldberg, and Wocjan: every connected graph G on n vertices satisfies min{s+(G), s−(G)} ≥ n−1. The proof is built on a new inequality (Theorem 2.1) for doubly nonnegative matrices indexed by the vertices of a connected graph: 4(∑_{uv∈E(G)} √M_uv)^2 ≤ q(G) 1^T M 1, where q(G)=2|E|−|V|+1. The theorem is proved by induction with three steps: folding non-edge entries onto the diagonal, splitting at a cut vertex using a Gram-vector argument, and handling the no-cut-vertex case by averaging the induction hypothesis over vertex deletions. Section 3 applies the inequality to the Hadamard squares A+∘A+ and A−∘A− to obtain s±(G) ≤ q(G), which, together with s+(G)+s−(G)=2m, yields the conjectured lower bound. Section 4 derives consequences for disconnected graphs, squared spread, adjacency inertia, positive and negative p-energies, and graph complements. The paper also claims a Lean 4 formalization of the main theorem.","tokens_in":10956,"tokens_out":16914,"duration_ms":158114,"significance":"If the proof is correct, as my checking suggests, this settles a conjecture that has been open since 2016 and that has attracted substantial partial progress. The doubly nonnegative relaxation introduced in Theorem 2.1 is a genuinely new framework for square-energy estimates and is likely to have further applications; the companion paper on a Turán-type strengthening is evidence of its reach. The proof is self-contained, has no fitted parameters or ad hoc axioms, and the formal-verification claim, if reproducible, would make the result machine-checked. The consequences in Section 4, including previously conjectured bounds on p-energies and adjacency inertia, follow cleanly from the main theorem. This is a significant contribution to spectral graph theory.","major_comments":[],"minor_comments":[{"comment":"The claim that minimizing Φ_G over correlation matrices is a semidefinite program is stated without details; the objective involves nonlinear terms 1/(1−C_uv). Since this subsection is explicitly motivational, please add a remark that the reformulation is only sketched, or give a reference for the SDP representability of the epigraph.","section":"§1.2, 'Bounding the optimum by duality'"},{"comment":"The manuscript states that Theorem 1.2 has been formally verified in Lean 4 but gives no commit hash or list of verified statements in the arXiv text. As a reproducibility matter, please include a specific version identifier and a brief description of what the formalization covers.","section":"§1.3, 'Formal verification'"},{"comment":"The averaging step is compressed. In particular, the nonnegativity of q(G−v), which is needed for the Cauchy–Schwarz inequality over v, is not stated; it follows because G−v is connected on n−1 vertices. A one-sentence clarification would improve readability.","section":"§2, no-cut-vertex case"},{"comment":"For 0<p≤2, the inequality ∑ x_i^p ≥ (∑ x_i^2)^{p/2} is used without comment. It follows from ℓ_p/ℓ_2 norm monotonicity; adding a parenthetical would help readers not familiar with this fact.","section":"§4.4, proof of Corollary 4.4"}],"recommendation":"minor_revision","confidential_remarks":"I found no load-bearing errors in the proof. The induction in Theorem 2.1 is correct, including the delicate counting identities; the reduction in Section 3 is direct; and the consequences in Section 4 are valid. The minor comments concern presentation and the verifiability of the Lean claim. I recommend acceptance after minor revisions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is the real proof of Conjecture 1.1. The main work is Theorem 2.1, a doubly nonnegative matrix inequality, and the induction is self-contained. I went through the cut-vertex splitting and the averaging step in the 2-connected case; the algebra is right, including the two counting identities that carry the argument. The deduction to s±(G) ≤ 2m − n + 1 is direct, and the consequences in Section 4 follow honestly.\n\nWhat is actually new: the inequality itself and the relaxation trick—taking the Hadamard squares A±∘A± and dropping from the PSD cone to the full doubly nonnegative cone. The framework clearly grows out of the Ando–Lin / Coutinho–Spier / Zhang line, but the proof does not lean on those results; they are cited only as context. No fitted parameters, no post-hoc exclusions, no circular step.\n\nSoft spots, in proportion. The claimed Lean 4 formalization is not independently checkable from the arXiv file: there is no commit hash or artifact digest, just a GitHub URL. That is a reproducibility caveat, not a correctness defect—the written proof stands on its own. The one place I would tell a referee to linger is the no-cut-vertex case: the sums over vertex deletions are the most delicate part, and a miscount there would break the averaged bound. I checked them; they are correct. Section 1.2's informal origin story is somewhat long and could be trimmed, but it is clearly labeled as motivation and not used in the proof. The exposition elsewhere is dense but clear.\n\nFor whom: spectral graph theorists, and anyone working on graph energy or semidefinite relaxations in combinatorics. The result resolves a conjecture that had accumulated several partial bounds, and the proof technique is likely to be reused. This deserves a serious referee, not a desk rejection. I would send it out and ask the authors to provide a verifiable artifact reference for the formalization, but I would expect the mathematical content to survive review.","headline":"This paper genuinely proves the 2016 square-energy conjecture with a self-contained inductive argument, and the delicate averaging step checks out.","tokens_in":11459,"tokens_out":4519,"would_cite":true,"duration_ms":45527,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","15A18","15A42"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that every connected graph on n vertices satisfies min{s+(G), s−(G)} ≥ n−1, confirming the 2016 square-energy conjecture and several related spectral bounds.","keywords":["positive square energy","negative square energy","adjacency eigenvalues","doubly nonnegative matrix","spectral graph theory","semidefinite programming","p-energy","Nordhaus–Gaddum bounds"],"falsifier":"Compute min{s+(G),s−(G)} exactly for every connected graph on up to n=10 vertices; any graph with value below n−1 would refute Theorem 1.2. Independently, solve the optimization over doubly nonnegative M: if for some connected graph the ratio 4(Σ_{edges}√M_uv)^2/(1^TM1) exceeds 2|E|−n+1, Theorem 2.1—the paper's main engine—is false, even if the spectral conjecture itself might survive.","tokens_in":10557,"feed_emoji":"🧮","tokens_out":6927,"duration_ms":64588,"temperature":0.7,"pith_summary":"The paper proves a conjecture that has remained open since 2016: in any connected graph on n vertices, the smaller of the sums of squares of the positive and negative adjacency eigenvalues is at least n−1. The proof is built around a new inequality that holds for every doubly nonnegative matrix M attached to a connected graph: four times the square of the sum of square roots of edge entries is at most (2|E|−n+1) times the total mass of M. Applying the inequality to the entrywise squares of the positive and negative spectral parts of the adjacency matrix yields s±(G) ≤ 2|E|−n+1, which combined with s+ + s− = 2|E| forces the lower bound. The same result settles the disconnected version, the squared-spread bound, the adjacency-inertia conjecture, positive and negative p-energy conjectures, and a Nordhaus–Gaddum-type complement inequality.","feed_headline":"Every connected graph has square energy at least n−1","feed_subtitle":"A doubly nonnegative matrix inequality settles the 2016 spectral conjecture and related energy bounds.","key_machinery":"The load-bearing object is Theorem 2.1, a doubly-nonnegative inequality: 4(Σ_{edges} √M_uv)^2 ≤ q(G)·1^TM1, where q(G)=2|E|−n+1. It works by relaxing the exact spectral objects—Hadamard squares A±∘A±, which are positive semidefinite and entrywise nonnegative—to the full cone of doubly nonnegative matrices, a larger and more flexible class. The proof drives the inequality by induction: the cut-vertex case uses a Gram-vector decomposition so both the edge sum and the total mass split along the cut; the no-cut-vertex case averages the induction hypothesis over all one-vertex deletions, where the identities Σ_v q(G−v)=(n−2)(q−1) and Σ_v T(M−v)=(n−2)T(M)+d0 transfer mass from edges and diagonal a","core_discovery":"The central claim is Theorem 1.2: every connected graph G on n vertices satisfies min{s+(G), s−(G)} ≥ n−1, sharp for trees and for the negative square energy of K_n. The spectral statement is deduced from a standalone matrix inequality: for any connected graph G and any doubly nonnegative matrix M, 4(Σ_{uv∈E} √M_uv)^2 ≤ (2|E|−n+1)·1^TM1. This works because the Hadamard squares of the positive and negative spectral parts of the adjacency matrix are doubly nonnegative, and the sum of their edge entries dominates half the corresponding square energy. The matrix inequality is proved by induction on n: non-edge entries of M are folded onto the diagonal, cut vertices split the Gram representation","pith_inferences":["Editorial inference: because Theorem 2.1 is stated for all doubly nonnegative M, not just spectral Hadamard squares, it is a continuous inequality that can be tested or optimized by semidefinite programming independently of eigenvalues; any violation for a non-spectral M would signal a flaw in the proof's engine, even if the final theorem still held.","Editorial inference: the induction suggests a transferable scheme—if a quadratic graph functional satisfies a cut-vertex split and a controlled vertex-deletion average, it holds for all connected graphs; this may apply to other graph invariants such as Laplacian energies or degree-based functionals.","Editorial inference: the equality cases (trees, disjoint edges, complete graph) hint that the slack of the conjecture is governed by the cyclomatic number; one testable strengthening is min{s+,s−}−(n−κ) ≥ f(c(G)) for an explicit positive f.","Editorial inference: the same inequality might be applied to matrices that are positive semidefinite and nonnegative but unrelated to adjacency spectra, such as covariance or similarity matrices on a connected graph, yielding lower bounds on the sum over edges of their square roots."],"forward_implications":["For connected G, s±(G) ≤ 2|E|−n+1, strengthening the classical spectral-radius bound λ1^2 ≤ 2|E|−n+1.","For a graph with κ components, min{s+, s−} ≥ n−κ, proving the disconnected version of the conjecture.","The squared spread satisfies |s+−s−| ≤ 2(|E|−n+κ); in particular it is at most (n−1)(n−2), with equality only for K_n.","The adjacency inertia bound min{s+,s−} ≥ n0 − ι + max{n+, n−} holds for every graph.","Positive and negative p-energies satisfy Eσ_p ≥ (n−κ)^{p/2} for 0<p≤2 and Eσ_p ≥ n−κ for p≥2, and the complement inequality sσ(G)+sσ(G̅) ≤ (n−1)^2 holds."],"fun_headline_variants":["Square energy conjecture proved for connected graphs","Graph conjecture settled: min square energy at least n−1","New proof: every connected graph meets square energy floor","Spectral proof: min positive/negative square energy ≥ n−1","Hadamard squares yield graph energy conjecture proof"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The induction's no-cut-vertex case hinges on two exact deletion counts—each edge mass survives in all but two of the vertex-deleted submatrices and each diagonal entry in all but one—so a single miscount would break the averaged estimate and with it the proof of the main theorem.","fun_headline_variants_meta":{"raw":{"variants":["Square energy conjecture proved for connected graphs","Graph conjecture settled: min square energy at least n−1","New proof: every connected graph meets square energy floor","Spectral proof: min positive/negative square energy ≥ n−1","Hadamard squares yield graph energy conjecture proof"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000183,"raw_usage":{"total_tokens":1099,"prompt_tokens":639,"completion_tokens":460,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":383,"completion_tokens_details":{"reasoning_tokens":382}},"tokens_in":383,"tokens_out":460,"duration_ms":5108,"temperature":1.0,"reasoning_tokens":382,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T16:17:50.910729+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute min{s+(G),s−(G)} exactly for every connected graph on up to n=10 vertices; any graph with value below n−1 would refute Theorem 1.2. Independently, solve the optimization over doubly nonnegative M: if for some connected graph the ratio 4(Σ_{edges}√M_uv)^2/(1^TM1) exceeds 2|E|−n+1, Theorem 2.1—the paper's main engine—is false, even if the spectral conjecture itself might survive.","supporting_citations":[],"review_version":1}