{"id":"2c396969-93e7-4408-b495-19e11fab64ef","arxiv_id":"2607.18044","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every n-vertex graph with clique number ω has √s⁺(G) ≤ (1−1/ω)n, where s⁺(G) is the sum of squared positive adjacency eigenvalues.","lead":"The paper proves that every n-vertex graph with clique number ω satisfies √s⁺(G) ≤ (1−1/ω)n, where s⁺(G) is the sum of squared positive adjacency eigenvalues, resolving a conjecture of Elphick and Wocjan. The proof passes through a weighted Turán inequality for doubly nonnegative matrices, established with a random greedy partition, and is claimed to be verified in Lean 4.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.3/ Eq (3.3) contain a reciprocal-constant typo; the proof yields 2ω/((ω−1)n²), which is essential for Lemma 1.4.","rationale":"The reader's primary concern was Lemma 1.6, the local inverse-probability estimate. I examined that induction proof closely and found it sound: the recurrences (2.1)–(2.2) are correct, the matrix construction in Theorem 2.3 satisfies the hypotheses of Lemma 2.2, and the algebra leading to the desired bound checks out. Lemma 1.6 is indeed load-bearing, but I see no flaw in it. The actual concrete gap in the written proof is the reciprocal-constant error in Theorem 1.3 and Eq (3.3). This is a transcription error—it does not affect the proof of Theorem 1.3 itself, which establishes the stronger correct constant, but it breaks the derivation of Lemma 1.4 as written. Because the error is localized and easily fixable, the appropriate verdict remains CONDITIONAL (the reader's original verdict). Thus I recommend UNCHANGED. I partially agree with the reader because they also flagged the constant error, though their weakest_assumption emphasized Lemma 1.6 more; I found Lemma 1.6 correct and the constant error to be the decisive load-bearing issue.","tokens_in":9970,"tokens_out":30737,"duration_ms":265329,"concrete_test":"Recompute the constant in the proof of Theorem 1.3: from (Σ√a_e)² ≤ (Σ a_e q_e)(Σ 1/q_e) and Σ 1/q_e ≤ (1/2)(1−1/ω)n², derive E W_P(a) ≥ 2/((1−1/ω)n²)(Σ√a_e)². Substitute this corrected value into Eq (3.3) and verify that Lemma 1.4's bound (1.3) follows. If the printed constant is used, the bound is too weak to imply Lemma 1.4, confirming the typo and the required correction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1.3 and Eq (3.3) state the lower bound 2(1−1/ω)/n² on expected separated mass. The proof of Theorem 1.3 actually derives (Σ√a_e)² ≤ (1/2)(1−1/ω)n² · E W_P(a), which rearranges to E W_P(a) ≥ 2/((1−1/ω)n²)·(Σ√a_e)² = 2ω/((ω−1)n²)·(Σ√a_e)². The printed constant is the reciprocal of the proven one, off by a factor (ω/(ω−1))². With the printed constant, the combination with (3.2) in the proof of Lemma 1.4 gives only (Σ√M_uv)² ≤ n² 1ᵀM1/4, which does not imply the claimed (1−1/ω)² n² 1ᵀM1/4. The corrected constant is load-bearing: it supplies the Turán factor (1−1/ω)². This is a localized transcription error—the proof of Theorem 1.3 itself proves the corrected version—but the step from Theorem 1.3 to Lemma 1.4 fails as written. After this fix, the rest of the chain (Lemma 1.6, the DNN/Motzkin–Straus relaxation, the spectral argument for Theorem 1.2) appears internally consistent.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that for every graph G on n vertices with clique number ω, √s⁺(G) ≤ (1−1/ω)n, where s⁺(G) is the sum of squared positive adjacency eigenvalues. This resolves Conjecture 1.1 of Elphick and Wocjan and strengthens Wilf's spectral Turán theorem. The proof proceeds by a chain of reductions: from a local inverse-probability estimate for the Caro–Wei random greedy partition (Lemma 1.6 / Theorem 2.3), to a weighted Turán-type lower bound on expected separated mass (Theorem 1.3), to a doubly nonnegative Motzkin–Straus inequality (Lemma 1.4), and finally to the spectral square-energy bound via the Schur product theorem applied to the positive part A₊ of the adjacency matrix. The paper also states that the proof of Theorem 1.2 has been formally verified in Lean 4. The central issue is that the displayed constant in Theorem 1.3 and Eq. (3.3) is weaker than the constant actually proved, and as printed it is insufficient for the proof of Lemma 1.4. The proof itself supplies the stronger constant needed; this is a correctable but load-bearing transcription error.","tokens_in":10324,"tokens_out":12204,"duration_ms":109883,"significance":"If the constant issue is corrected, this is a substantial result: it settles a named conjecture in spectral graph theory, strengthens Wilf's theorem, and introduces a remarkably clean local estimate for the Caro–Wei process. The doubly nonnegative relaxation and the use of the Schur product theorem provide a coherent and largely self-contained proof strategy. The claimed Lean formalization is an important reproducibility asset, although it needs to be matched to the corrected statements. The local harmonic inequality (1.5), with equality for complete multipartite graphs, is a striking contribution in its own right and is likely to find further applications.","major_comments":[{"comment":"The displayed lower bound is too weak by a factor ω²/(ω−1)². The proof of Theorem 1.3 actually derives (Σ√a_e)² ≤ (1/2)(1−1/ω)n² · E W_P(a), which rearranges to E W_P(a) ≥ 2ω/((ω−1)n²)·(Σ√a_e)². The printed statement has 2(1−1/ω)/n² instead. This is load-bearing: in the proof of Lemma 1.4, combining (3.2) with the printed (3.3) gives only (Σ√M_uv)² ≤ n² 1ᵀM1/4, missing the factor (1−1/ω)², so the proof of Lemma 1.4 fails as written. The subsequent remark that a_e≡1 yields an ω-partite subgraph with at least 2m²/((1−1/ω)n²) edges already uses the corrected constant. Please update the statement of Theorem 1.3, Eq. (3.3), and the overview to the stronger constant proved in the argument.","section":"Theorem 1.3 and Eq. (3.3)"}],"minor_comments":[{"comment":"The notation q_{x,u} is currently ambiguous: it should be defined explicitly as q_{G_x}(vu), while q_{u,x} is q_{G_u}(vx), so that the direction of the edge pair is unambiguous in the row-sum matrix R.","section":"Section 2, proof of Theorem 2.3"},{"comment":"The statement that the proof has been formally verified in Lean 4 needs to be reconciled with the corrected constant in Theorem 1.3. Please state explicitly which displayed statements are certified and update the repository documentation to match the corrected bound; otherwise the formal-verification claim cannot be independently audited.","section":"Section 1.2, Formal verification"},{"comment":"After the constant is corrected, the sentence 'Combining (3.2) and (3.3) and rearranging' is valid, but it may be worth displaying the intermediate line (Σ√M_uv)² ≤ (1−1/ω)² n² 1ᵀM1/4 to make the role of the corrected constant transparent.","section":"Section 3, proof of Lemma 1.4"}],"recommendation":"major_revision","confidential_remarks":"This is a genuine resolution of a known conjecture, and the proof chain is convincing once the constant in Theorem 1.3 / Eq. (3.3) is corrected. The error is localized and the paper's own proof supplies the stronger constant, so I would not recommend rejection. I would, however, require the authors to fix the constant in all displayed statements and to verify that the Lean formalization certifies the corrected theorem. If the repository certifies only a weaker statement, the formal-verification claim should be adjusted accordingly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a real proof of a real conjecture, and the main new machinery is worth reading. But Theorem 1.3 and Eq. (3.3) have a load-bearing constant typo. As printed, Lemma 1.4 does not follow; the proof of Theorem 1.3 itself proves the corrected constant, so it is a transcription error, not a conceptual one.\n\nWhat is new: the paper proves sqrt(s+(G)) ≤ (1-1/ω)n for all graphs, resolving Conjecture 1.1. The proof goes through a DNN Motzkin–Straus inequality (Lemma 1.4), which is a genuinely useful weighted strengthening of Turán, and the key engine is the local inverse-probability estimate for the Caro–Wei greedy partition (Lemma 1.6). That estimate is clever: the recurrence pair (2.1)-(2.2) plus the reciprocal-row-sum lemma is a nice argument. The derived weighted Turán stability statement (Theorem 1.3) is a reasonable byproduct, though its main role here is as a step.\n\nWhat is sound: the reduction from the spectral problem to the DNN inequality is standard (Schur product + trace), and once the constant is corrected the chain Lemma 1.6 → Theorem 1.3 → Lemma 1.4 → Theorem 1.2 is coherent. I did not find a circular dependency: the companion-paper relaxation is fully restated and proved here. The claimed Lean formalization is positive evidence, but there is no commit hash or artifact description in the paper, so I cannot independently verify it; I treat it as a promise.\n\nSoft spots: the constant typo is the main one. It sits at a central node: with the printed constant, combining (3.2) and (3.3) gives (Σ√M_uv)² ≤ n² 1ᵀM1/4, which lacks the Turán factor. The corrected constant 2ω/((ω-1)n²) is what actually appears in the algebra, and with it (1-1/ω)² appears and Lemma 1.4 goes through. This is a trivial fix for the authors, but it should be fixed before publication. Minor notes: the comparison with Füredi in the intro is a little loose (\"up to an additive rounding error\"), and the paragraph on Kelly–Postle does not directly connect to the theorem. Neither affects the main claim.\n\nFor whom: spectral extremal graph theorists and anyone working on Motzkin–Straus-type inequalities. It is a solid contribution, not a revolution.\n\nRecommendation: accept for peer review. The referee should require the constant fix and a small Lean artifact pointer (commit hash or build log). After that, this should be accepted.","headline":"The paper resolves Elphick–Wocjan with a genuinely new Caro–Wei/Motzkin–Straus argument, but Theorem 1.3 as printed contains a reciprocal-constant typo that blocks the chain until fixed.","tokens_in":10808,"tokens_out":3840,"would_cite":true,"duration_ms":36916,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C35","15A42"],"pacs":[],"model":"deepseek-v4-flash","headline":"For every graph on n vertices with clique number ω, the square root of the sum of squared positive adjacency eigenvalues is at most (1 − 1/ω)n, settling a conjecture stated in 2018.","keywords":["positive square energy","clique number","spectral Turán theorem","doubly nonnegative matrices","Motzkin–Straus inequality","Caro–Wei greedy process","random partition","machine-verified proof"],"falsifier":"Search, for all graphs on at most nine vertices, for a vertex v with 1/p(v) + Σ_{u∈N(v)} 1/q(vu) > n; finding one would falsify the key lemma and thus the theorem as proved.","tokens_in":9876,"feed_emoji":"📐","tokens_out":13405,"duration_ms":117697,"temperature":0.7,"pith_summary":"The paper establishes a sharp spectral analogue of Turán's theorem: for every n-vertex graph with clique number ω, the sum s⁺ of squares of the positive adjacency eigenvalues satisfies √s⁺ ≤ (1 − 1/ω)n. This confirms a conjecture that had been open since 2018 and strengthens Wilf's classical bound on the largest eigenvalue. The proof reduces the spectral statement through a chain of increasingly combinatorial inequalities, ending at a local probabilistic estimate for the random greedy Caro–Wei partition. Along the way it yields a weighted Turán stability theorem with an explicit random partition, and the full proof has been machine-checked.","feed_headline":"Clique number caps the square root of spectral energy","feed_subtitle":"Proof confirms a 2018 conjecture and strengthens the classic spectral Turán theorem.","key_machinery":"The proof is carried by the Caro–Wei random greedy process on the complement graph, which yields a random partition of the vertex set into at most ω parts because the chosen pivots form a clique. The load-bearing estimate is the local inverse-probability inequality (Lemma 1.6 / Theorem 2.3): for every vertex v, 1/p_G(v) + Σ_{u∈N_G(v)} 1/q_G(vu) ≤ n, where p_G(v) is the probability that v is chosen as a pivot and q_G(vu) is the probability that the edge uv lies between two different parts. The lemma is proved by induction via first-pivot recurrences together with an AM–GM inequality on reciprocal row sums. Summing this local estimate yields a harmonic bound on the edges, which implies a weigh","core_discovery":"The central discovery is Theorem 1.2: for every graph on n≥1 vertices with clique number ω, the quantity √s⁺(G) is bounded by (1−1/ω)n, where s⁺(G) is the sum of the squares of the positive eigenvalues of the adjacency matrix. This is equivalent to the ratio n/(n−√s⁺(G)) being at most ω, the form originally conjectured. The bound is tight: when ω divides n, the complete ω-partite Turán graph has exactly one positive eigenvalue equal to (1−1/ω)n, so equality holds.","pith_inferences":["Because the local harmonic inequality holds with equality for all complete multipartite graphs, a natural next step is a stability version: are complete multipartite graphs the only extremal cases, and if so, how much can a graph deviate before the bound becomes strict?","The Caro–Wei partition is exactly the clustering produced by the random-pivot correlation-clustering algorithm, so the harmonic estimate could translate into approximation guarantees for correlation clustering on dense graphs.","The doubly-nonnegative relaxation is flexible: replacing the entrywise square by entrywise p-th powers (for suitable p) might yield analogous spectral bounds for p-energies, provided the resulting matrix remains doubly nonnegative.","One could test computationally, on all graphs up to a modest size, whether equality in the local estimate forces complete multipartiteness; a counterexample would refine the extremal analysis of the theorem."],"forward_implications":["Resolves the square-energy conjecture posed in 2018: n/(n−√s⁺(G)) ≤ ω(G) for every graph.","Strengthens Wilf's spectral Turán theorem, since √s⁺(G) ≥ λ₁(G).","Gives a weighted Turán stability statement (Theorem 1.3): an explicit random ω-partition with a guaranteed lower bound on separated mass for arbitrary nonnegative edge weights, valid for all graphs and computable in polynomial time.","Provides a constructive, probability-based path from spectral data to clique number, potentially useful for algorithms that estimate clique number from eigenvalues.","The entire theorem is formally machine-verified, so the combinatorial and spectral reasoning is checkable step by step."],"fun_headline_variants":["Clique number caps square-root of spectral energy","New theorem: √s⁺ ≤ (1−1/ω)n, proven","Spectral energy squared, bounded by clique number","Resolved conjecture: clique number limits spectral energy","Tight bound: √s⁺ ≤ (1−1/ω)n for graphs"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The whole proof rests on the local inverse-probability estimate (Lemma 1.6) that for every vertex 1/p(v) + Σ_{u∈N(v)} 1/q(vu) ≤ n, so if any graph violates this inequality the weighted Turán bound, the doubly nonnegative Motzkin–Straus lemma, and the spectral theorem all collapse; separately, as printed, Theorem 1.3 and (3.3) need the constant corrected from 2(1−1/ω)/n² to 2ω/((ω−1)n²) for Lemma 1.4's proof to work as written.","fun_headline_variants_meta":{"raw":{"variants":["Clique number caps square-root of spectral energy","New theorem: √s⁺ ≤ (1−1/ω)n, proven","Spectral energy squared, bounded by clique number","Resolved conjecture: clique number limits spectral energy","Tight bound: √s⁺ ≤ (1−1/ω)n for graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000329,"raw_usage":{"total_tokens":1612,"prompt_tokens":624,"completion_tokens":988,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":368,"completion_tokens_details":{"reasoning_tokens":900}},"tokens_in":368,"tokens_out":988,"duration_ms":9458,"temperature":1.0,"reasoning_tokens":900,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T16:15:53.479485+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search, for all graphs on at most nine vertices, for a vertex v with 1/p(v) + Σ_{u∈N(v)} 1/q(vu) > n; finding one would falsify the key lemma and thus the theorem as proved.","supporting_citations":[],"review_version":1}