{"id":"317a7072-ceec-4134-97e9-525da367c454","arxiv_id":"2505.12446","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A signed bipartite graph with a squarefree half-discriminant and a plus or minus one constant or linear coefficient is determined by its generalized spectrum whenever it is controllable or almost controllable.","lead":"This paper proves a sufficient condition for a signed bipartite graph to be determined by its generalized spectrum: if a certain squarefree discriminant condition and a coefficient condition hold, and the graph is controllable or almost controllable, then it is determined by its generalized spectrum. The result extends a recent criterion for signed trees and answers an open question in spectral graph theory.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Theorem 2 depends on Proposition 2 of unpublished arXiv:2504.12932, cited without proof; the odd-prime case of the main argument fails if that p-adic divisibility lemma is unsound.","rationale":"I read the core argument as sound: the reduction to s = floor(n/2) is valid, Lemma 11 is correct, and Propositions 4 and 5, conditional on the cited lemmas, imply ℓ(Q) = 1. The p = 2 section is internally consistent; in Lemma 15 the case u ≠ 0 is handled because Eq. (9) and Eq. (8) give two spanning sets of ker φ(BBT), so verifying mixed orthogonality suffices for total isotropy. The odd-prime section is also coherent in both cases for x^2 − λ0. The remaining risk is external: Proposition 2 is a nontrivial p-adic divisibility lemma used exactly where the argument otherwise has no control over the level of Q. Since [9] is not peer-reviewed and is by the same authors, independent verification is needed before accepting Theorem 2 unconditionally. I therefore keep the reader's CONDITIONAL verdict and do not adjust it. The subsumption claim about irreducible signed trees is supported by standard cyclicity and is not a genuine concern.","tokens_in":12849,"tokens_out":24041,"duration_ms":239625,"concrete_test":"Obtain the proof of Proposition 2 from arXiv:2504.12932 and check it line by line against the hypotheses used in Section 3.2: controllable or almost controllable signed bipartite A, a rational regular orthogonal Q, and an odd prime p | ℓ(Q). Then run a randomized numerical verification: for 10^4 random controllable signed bipartite matrices A and random rational regular orthogonal Q with an odd prime p dividing ℓ(Q), compute the primary factor φ from Proposition 1 and verify p^(deg φ+1) | det φ(A); a single failure would invalidate the odd-prime case, while success would resolve the conditional concern.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.2 applies Proposition 2 of [9] at the two points where the proof forces p^2 | det(λ0 I − BBT): in Case 1 it yields p^3 | det(A^2 − λ0 I), and in Case 2 it yields p^2 | det(A − λ1 I) or p^2 | det(A + λ1 I). These are the only inputs that bridge the level of Q to the determinant of BBT; Lemma 7 then converts that divisibility into the final contradiction. Proposition 2 is a non-elementary assertion about the level of a rational regular orthogonal matrix and a primary factor of χ(A) over F_p, and it is imported verbatim from [9], an arXiv preprint by the same authors, without proof or an explicit statement of its hypotheses. Lemma 3 from [9], by contrast, is a short exercise following from Qhat^T Qhat ≡ 0 (mod p) and A Qhat = Qhat B, so the paper could supply that proof inline. The other reader-identified gap, that irreducible signed trees are controllable, is not load-bearing: if χ(A) is irreducible, e is a cyclic vector and W(Σ) has full rank. The decisive external dependency is therefore Proposition 2 of [9].","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the generalized spectral characterization (DGS) of signed bipartite graphs. Theorem 2 states that if an n-vertex controllable or almost controllable signed bipartite graph has the coefficient of the constant term (n even) or linear term (n odd) equal to ±1, and if 2^{-⌊n/2⌋}√Δ_Σ is squarefree, then the graph is DGS. The proof strategy is to show that every rational regular orthogonal matrix Q in Q(Σ) must have level 1. For the prime p=2 this is done through a totally isotropic subspace argument over F_2; for odd primes the contradiction is obtained by transferring a p-adic divisibility of det(A^2-λ0 I) or det(A±λ1 I) to det(BB^T-λ0 I), then invoking Lemma 7 and Lemma 8(iv). The paper also provides three Mathematica-verified examples illustrating reducible and almost controllable cases.","tokens_in":13112,"tokens_out":10340,"duration_ms":101481,"significance":"If correct, the result is a meaningful extension of the recent criterion of Ji, Wang, and Zhang for irreducible signed trees to a larger class of signed bipartite graphs, including reducible and almost controllable cases. The p=2 argument is detailed and the total-isotropy reasoning in Lemma 15 is coherent; Lemma 11 correctly reduces the discriminant condition to Δ_{BB^T} being squarefree; the examples are concrete and support the applicability of the theorem. The main reservation is that the odd-prime case depends essentially on Proposition 2, which is imported without proof from the authors' own unpublished arXiv preprint [9]; the central claim is therefore plausible but not yet fully self-contained.","major_comments":[{"comment":"Proposition 2 is stated without proof and is load-bearing in the proof of Proposition 5. In Case 1 it is used to conclude p^3 | det(A^2-λ0 I), and in Case 2 it is used to conclude p^2 | det(A-λ1 I) or p^2 | det(A+λ1 I). These are exactly the steps that bridge the level of Q to the determinant of BB^T, after which Lemma 7 closes the argument. Since Proposition 2 is a non-elementary assertion about the level of a rational regular orthogonal matrix and a primary factor of χ(A) over F_p, and since reference [9] is an unpublished arXiv preprint by the same authors, the manuscript should include a complete proof of Proposition 2, or at minimum a precise statement of all its hypotheses together with a proof. Without this, the odd-prime part of Proposition 5 is not verifiable from the paper itself.","section":"§2.1 and §3.2"},{"comment":"The transition from Proposition 1 to the applications of Proposition 2 needs to be made explicit. Proposition 1 only guarantees a multiple factor φ(x) of χ(A;x) over F_p with col(Qhat)∩ker φ(A) ≠ 0, while Proposition 2 is applied to the specific integer polynomials x^2-λ0 and x±λ1 in Cases 1 and 2. The paper should state how these integer polynomials represent the relevant factors over F_p and verify that all hypotheses of Proposition 2 (regularity of Q, rationality, and the stated condition on φ) are met in both cases.","section":"§3.2"}],"minor_comments":[{"comment":"In the proof of Proposition 3, the phrase 'by Lemma (ii)' should read 'by Lemma 8(ii)'; the reference is incomplete as printed.","section":"§2.2, Proposition 3"},{"comment":"The displayed expression for u(x) in the proof of Lemma 9 appears to contain a typo: it should be u(x)=u_{n-2}x^{n-2}+u_{n-3}x^{n-3}+...+u_0, not a repetition of u_0 in several terms.","section":"§2.2, Lemma 9"},{"comment":"The claim that Theorem 2 subsumes Theorem 1 relies on the fact that an irreducible signed tree is controllable. This is true because irreducibility of χ(A) makes e a cyclic vector, but the paper does not state this; a one-sentence explanation would remove an implicit step.","section":"§1"},{"comment":"The symbol φ is used both for the polynomial supplied by Lemma 6 and for the multiple factor appearing in Proposition 1/Proposition 2; the notation should be distinguished to avoid confusion in Cases 1 and 2.","section":"§3.2"}],"recommendation":"major_revision","confidential_remarks":"The decisive issue is the unproved import of Proposition 2 from the authors' own arXiv preprint [9]. I would ask the editor to require a complete proof or a peer-reviewed reference for that result before acceptance. If the authors can supply the proof, the paper is likely a solid contribution; the p=2 case and the discriminant reduction are carefully done, and the examples give useful evidence. I also note that the manuscript relies on several arXiv preprints [4] and [9], so a check of their publication status would be appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline result is a real extension: Theorem 2 removes the irreducibility and even-order restrictions from Ji-Wang-Zhang's signed-tree criterion and covers almost controllable signed bipartite graphs, answering a question they posed. The proof is largely sound, and the p=2 part—the total-isotropy argument in Section 3.1—is the most substantial new work. I checked the discriminant identity (Lemma 11), the walk-matrix rank calculations, and the examples; they are consistent, and the computed factorizations look reproducible.\n\nThe soft spot is structural. The odd-prime case in Section 3.2 depends on Proposition 2 of the authors' own arXiv:2504.12932, imported without proof. That proposition is what converts divisibility of the level of Q into divisibility of det(A^2 - λ0 I) and det(A ± λ1 I), and without it the contradiction in Proposition 5 does not go through. The stress-test note is right that this is the decisive external dependency. In a journal submission the authors should be required to either prove Proposition 2 in full or state it with hypotheses and a proof sketch; a paper whose main theorem hinges on an unproved claim in a preprint is not self-contained. The related Lemma 3 is easy and could be proven in two lines, so that one is a minor omission.\n\nA second, smaller gap: the paper says Theorem 2 subsumes Theorem 1 but doesn't justify that irreducible signed trees are controllable. It is true—if χ(A) is irreducible then e is cyclic, so W(Σ) has full rank—and it should be a one-sentence remark.\n\nOverall, I think the theorem is very likely true and the contribution is meaningful within the generalized spectral characterization niche. The dependency on Proposition 2 is a real but fixable weakness, not a sign of a broken argument. The paper deserves a serious referee, and I would send it to review, with the clear instruction that the authors supply the missing proof of Proposition 2 before acceptance.","headline":"A genuine extension of the signed-tree DGS criterion, with a proof that hinges on an unproved lemma from the authors' preprint.","tokens_in":13615,"tokens_out":2125,"would_cite":true,"duration_ms":20329,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"For controllable and almost controllable signed bipartite graphs, a squarefree scaled discriminant and a ±1 coefficient condition force determination by generalized spectrum.","keywords":["signed bipartite graph","generalized spectrum","discriminant","determined by spectrum","controllable graph","almost controllable","squarefree","regular orthogonal matrix"],"falsifier":"Take any controllable or almost controllable signed bipartite graph satisfying the coefficient condition and compute $2^{-\\lfloor n/2\\rfloor}\\sqrt{\\Delta_\\Sigma}$. If it is squarefree, the theorem predicts that every regular rational orthogonal matrix in $\\mathcal{Q}(\\Sigma)$ is a permutation matrix; a concrete falsifying observation would be a generalized cospectral partner $\\Gamma$ whose intertwining matrix has level greater than 1, or a direct computation in which an odd prime $p$ divides the level of $Q$ while $p^2\\nmid \\Delta_{BB^T}$. Since the proof depends on unproved lemmas from [9], a small example where those lemmas fail would also break the theorem.","tokens_in":12654,"feed_emoji":"🔢","tokens_out":11278,"duration_ms":94554,"temperature":0.7,"pith_summary":"The paper establishes a sufficient arithmetic condition for a signed bipartite graph to be determined by its generalized spectrum, meaning the pair of spectra (adjacency matrix and complement-style matrix $J-I-A$) pins the graph down up to isomorphism. The condition applies to graphs that are controllable or almost controllable, i.e. whose walk matrix has rank $n$ or $n-1$. If the characteristic polynomial has constant term $\\pm1$ (for even $n$) or linear coefficient $\\pm1$ (for odd $n$), and if the integer $2^{-\\lfloor n/2\\rfloor}\\sqrt{\\Delta_\\Sigma}$ built from the discriminant is squarefree, then the graph is determined by its generalized spectrum. This extends a recent criterion that worked only for signed trees with irreducible characteristic polynomials, and it covers odd-order and reducible cases that the earlier theorem could not reach. A reader should care because generalized spectral uniqueness is a strong form of \"the spectrum and complement spectrum tell you everything.\"","feed_headline":"Squarefree discriminant pins down signed bipartite graphs","feed_subtitle":"When a scaled discriminant is squarefree, generalized spectrum determines the signed bipartite graph up to isomorphism.","key_machinery":"The machinery is the block decomposition of a bipartite adjacency matrix $A = \\begin{pmatrix}0&B\\\\B^T&0\\end{pmatrix}$, joined to the discriminant identity $\\Delta_A = 4^{\\lfloor n/2\\rfloor}\\Delta_{BB^T}^2$. This identity converts the squarefree hypothesis into the statement that $\\Delta_{BB^T}$ is squarefree. The proof then establishes two exclusion results about the level $\\ell(Q)$ of any regular rational orthogonal matrix $Q$ intertwining $A$ with another signed graph, where the level is the smallest positive integer $k$ such that $kQ$ is an integer matrix: if $\\ell(Q)$ is even then $\\Delta_{BB^T}$ is even, and if an odd prime $p$ divides $\\ell(Q)$ then $p^2\\mid \\Delta_{BB^T}$. Squarefreeness of $\\Delta_{BB^T}$ therefore eliminates every prime divisor of $\\ell(Q)$, forcing $\\ell(Q)=1$; level-1 regular orthogonal matrices are exactly permutation matrices, and Lemma 1 turns that into the DGS conclusion.","core_discovery":"The central claim, Theorem 2, is: let $\\Sigma$ be an $n$-vertex signed bipartite graph that is controllable or almost controllable, and suppose the constant term ($n$ even) or linear coefficient ($n$ odd) of $\\chi(\\Sigma;x)$ is $\\pm1$. If $2^{-\\lfloor n/2\\rfloor}\\sqrt{\\Delta_\\Sigma}$ is squarefree, then $\\Sigma$ is determined by its generalized spectrum. The proof shows that any regular rational orthogonal matrix $Q$ with $Q^T A(\\Sigma)Q = A(\\Gamma)$ for a generalized cospectral partner $\\Gamma$ must have level 1, hence be a permutation matrix; then $\\Gamma$ is isomorphic to $\\Sigma$. In particular, the result subsumes the earlier signed-tree theorem and applies to reducible characteristic polynomials and to odd-order signed bipartite graphs.","pith_inferences":["The same squarefree-discriminant mechanism may extend to non-bipartite signed graphs if an analogue of the $\\Delta_A = 4^{\\lfloor n/2\\rfloor}\\Delta_{BB^T}^2$ identity can be found for a suitable principal submatrix; the bipartite block form is doing real work in the proof.","The squarefree condition is sufficient, not necessary; graphs with non-squarefree scaled discriminants may still be DGS by other routes, so the criterion likely underestimates the true family of DGS signed bipartite graphs.","Since the almost-controllable case needs a nontrivial automorphism, rigid almost-controllable signed bipartite graphs are unreachable by this argument; a separate mechanism would be required to settle their DGS status.","The proof's reliance on lemmas from an earlier preprint suggests that a formal verification or self-contained proof of the imported lemmas would be the most direct way to confirm the result before using it in applications."],"forward_implications":["Every signed tree covered by the earlier irreducible-tree theorem also satisfies the new criterion, and the new criterion additionally covers reducible signed trees and odd-order signed bipartite graphs.","For any signed bipartite graph meeting the two conditions, generalized cospectrality becomes isomorphism: the spectrum plus complement spectrum determines the graph exactly.","The condition is finitely checkable: compute the characteristic polynomial, its discriminant, the constant or linear coefficient, and test squarefreeness of the scaled integer.","In the almost controllable case, satisfying the theorem forces the graph to have a nontrivial automorphism, because only permutation matrices lie in $\\mathcal{Q}(\\Sigma)$.","The discriminant identity shows that $\\Delta_{BB^T}$ is the operative squarefree integer, so the DGS property is tied to the arithmetic of the half-size matrix $BB^T$ rather than to the full adjacency matrix."],"supporting_citations":[{"why":"Supplies the signed-tree theorem being extended and the discriminant identity $\\Delta_A = 4^{\\lfloor n/2\\rfloor}\\Delta_{BB^T}^2$ that anchors the squarefree hypothesis.","marker":"[7]"},{"why":"Supplies the primary-decomposition lemmas and Proposition 2 used without proof to rule out prime divisors of the orthogonal matrix's level.","marker":"[9]"},{"why":"Provides Lemmas 5-7 that connect squarefree discriminants to repeated factors modulo $p$ and to a Smith-normal-form criterion.","marker":"[4]"},{"why":"Establishes that generalized cospectrality is equivalent to the existence of a regular rational orthogonal matrix $Q$, with uniqueness and rationality in the controllable and almost controllable cases.","marker":"[2, 3, 11]"},{"why":"Supplies the mod-4 quadratic-form lemma used to handle the prime 2 in the level.","marker":"[6]"},{"why":"Supplies the standard fact that $p$ divides the discriminant exactly when the polynomial has a repeated factor over $\\mathbb{F}_p$.","marker":"[10]"}],"fun_headline_variants":["Squarefree discriminant nails signed bipartite graphs","Signed bipartite graphs settled by squarefree discriminant","One squarefree check decides signed bipartite graphs","Generalized spectrum wins for signed bipartite graphs","Squarefree scalar settles signed bipartite graph identity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the technical lemmas imported without proof from the authors' earlier preprint, in particular Proposition 2 and Lemma 3 of reference [9], correctly control which primes divide the level of an intertwining orthogonal matrix; the claim that Theorem 2 subsumes Theorem 1 also relies on the unstated premise that irreducible signed trees are controllable.","fun_headline_variants_meta":{"raw":{"variants":["Squarefree discriminant nails signed bipartite graphs","Signed bipartite graphs settled by squarefree discriminant","One squarefree check decides signed bipartite graphs","Generalized spectrum wins for signed bipartite graphs","Squarefree scalar settles signed bipartite graph identity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000264,"raw_usage":{"total_tokens":1558,"prompt_tokens":855,"completion_tokens":703,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":471,"completion_tokens_details":{"reasoning_tokens":633}},"tokens_in":471,"tokens_out":703,"duration_ms":7110,"temperature":1.0,"reasoning_tokens":633,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:34:51.252319+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take any controllable or almost controllable signed bipartite graph satisfying the coefficient condition and compute $2^{-\\lfloor n/2\\rfloor}\\sqrt{\\Delta_\\Sigma}$. If it is squarefree, the theorem predicts that every regular rational orthogonal matrix in $\\mathcal{Q}(\\Sigma)$ is a permutation matrix; a concrete falsifying observation would be a generalized cospectral partner $\\Gamma$ whose intertwining matrix has level greater than 1, or a direct computation in which an odd prime $p$ divides the level of $Q$ while $p^2\\nmid \\Delta_{BB^T}$. Since the proof depends on unproved lemmas from [9], a small example where those lemmas fail would also break the theorem.","supporting_citations":[{"cited_title":"Wang, Generalized spectral characterization revisited, Electron","cited_arxiv_id":null,"evidence_quote":"Supplies the signed-tree theorem being extended and the discriminant identity $\\Delta_A = 4^{\\lfloor n/2\\rfloor}\\Delta_{BB^T}^2$ that anchors the squarefree hypothesis."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the primary-decomposition lemmas and Proposition 2 used without proof to rule out prime divisors of the orthogonal matrix's level."},{"cited_title":"Wang, C.-X","cited_arxiv_id":null,"evidence_quote":"Provides Lemmas 5-7 that connect squarefree discriminants to repeated factors modulo $p$ and to a Smith-normal-form criterion."},{"cited_title":"Wang, A simple arithmetic criterion for graphs being determined by their generalized spectra, J","cited_arxiv_id":null,"evidence_quote":"Supplies the mod-4 quadratic-form lemma used to handle the prime 2 in the level."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the standard fact that $p$ divides the discriminant exactly when the polynomial has a repeated factor over $\\mathbb{F}_p$."}],"review_version":1}