{"id":"524ac0cf-3cb8-459a-acb4-f06fa8cb6516","arxiv_id":"2411.13229","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Introduces cospectral graphons and proves that equality of cycle densities, equality of spectra, and existence of a unitary intertwining operator are equivalent, plus a counterexample to cospectral approximation.","lead":"This paper defines when two graphons (limit objects for large graphs) have the same spectrum, showing three equivalent ways to check this. It also gives a pair of graphons with the same spectrum that no pair of ordinary graphs approaching them can share.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.2 is false: cycle densities are blind to the zero eigenvalue, so graphons with equal nonzero spectra but different kernels satisfy (i) but not (iv).","rationale":"The reader's weakest_assumption concerned the standard spectral theory of compact operators and concluded the proof was sound. The actual load-bearing flaw is a subtle but fatal gap within that spectral theory: the proof of (iii)⇒(iv) defines the claimed unitary only on the nonzero eigenspaces and never treats the kernel, even though a unitary intertwiner must map kernels isometrically. Because the cycle-density formulas (2.3) contain no contribution from eigenvalue 0, the equivalence (i)⇔(iv) cannot hold unless the zero eigenspaces of the two graphons are always unitarily equivalent whenever the nonzero spectra agree. The paper gives no argument for this, and it is false. I constructed an explicit pair of graphons with the same nonzero spectrum and hence the same cycle densities, but with kernels of different dimensions, so no unitary T can exist. This is not a matter of an exotic unbounded kernel or a missing epsilon; it is a counterexample within the class of bounded [0,1]-valued graphons. The main theorem, which is the central contribution of the note, is therefore incorrect as stated. A repaired version would need to either include the zero eigenvalue in the spectral data and weaken (i), or replace (iv) with a unitary between the orthogonal complements of the kernels; the current statement cannot stand. The secondary result, Theorem 4.2, appears correct and is independent of this flaw, but it does not salvage the central claim.","tokens_in":7372,"tokens_out":24752,"duration_ms":270423,"concrete_test":"Build the explicit counterexample: set λ_1 = 0.9, λ_n = 2^{-n-10} for n≥2, φ_1 = 1, φ_n = √2 sin(2π(n−1)x) for n≥2, and define U = λ_1 + Σ_{n≥2} λ_n φ_n(x)φ_n(y). Verify U is a graphon (0≤U≤1). Let W be the indicator of ∪(I_n×I_n), where I_n are disjoint intervals with |I_1|=0.9 and |I_n|=λ_n. Then check: (a) by (2.3), t(C_k,U) = 0.9^k + Σ_{n≥2} λ_n^k = t(C_k,W) for every k≥3; (b) ker T_U = {0} because the trigonometric basis is complete and all λ_n>0; (c) ker T_W contains all functions supported outside ∪I_n, so it is infinite-dimensional. Since equality in (iv) would force T(ker T_W) ⊆ ker T_U, a unitary T cannot exist. This directly contradicts Theorem 3.2.","verdict_should_be":"REJECT","load_bearing_attack":"Theorem 3.2 claims that equality of cycle densities is equivalent to existence of a unitary T with T·T_W = T_U·T. The proof of (iii)⇒(iv) defines T only on nonzero eigenspaces and ignores ker T_U and ker T_W. This is not a harmless omission: t(C_k,W) = Σ_{λ≠0} λ^k, so the cycle-density conditions (i) and (ii) are completely insensitive to the zero eigenspace. For finite graphs this subtlety is invisible because the number of vertices fixes the multiplicity of 0, but for graphons the kernel can have dimension 0, ℵ0, or any intermediate value independently of the nonzero spectrum. Hence (i) does not imply (iv). Concretely, fix positive λ_n with λ_1 > 2Σ_{n≥2}λ_n and take an orthonormal basis {φ_n} of L2([0,1]) with φ_1=1 and |φ_n|≤√2. Let U = λ_1 + Σ_{n≥2} λ_n φ_n(x)φ_n(y). Then U is a graphon with Spec(U) = {λ_n} and ker T_U = {0}. Let W be the block graphon 1_{∪(I_n×I_n)} where I_n are disjoint intervals with |I_1|=λ_1 and |I_n|=λ_n. Then Spec(W) = {λ_n} but ker T_W is infinite-dimensional. The two graphons have identical cycle densities, yet no unitary T can satisfy T·T_W = T_U·T, because a nonzero f ∈ ker T_W would be mapped into ker T_U = {0}, contradicting injectivity of T.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines two graphons U and W to be cospectral when t(C_k, U) = t(C_k, W) for all k ≥ 3. Theorem 3.2 claims this is equivalent to equality of the full spectra of the associated Hilbert-Schmidt operators and to the existence of a unitary operator T on L^2([0,1]) with T ∘ T_W = T_U ∘ T. The paper also proves (Theorem 4.2) that the graphon analogue of a previous approximability result for fractional isomorphism fails: the constant graphon 1/2 and the block graphon on [0,1/2]^2 are cospectral but cannot be limits of sequences of cospectral graphs. The proof uses an L1-norm obstruction.","tokens_in":7715,"tokens_out":19595,"duration_ms":200383,"significance":"Were Theorem 3.2 correct, it would provide a clean graphon counterpart to cospectrality of finite graphs, with cycle densities playing the role of the usual homomorphism counts. The proof strategy for the nonzero part of the spectrum is sensible, and the inapproximability result is elegant and appears correct. However, the main equivalence is false because cycle densities are blind to the zero eigenvalue, and the counterexample is simple and within the paper's own setup. The paper therefore needs substantial revision rather than minor polishing.","major_comments":[{"comment":"The equivalence (i)⇔(iii) and (i)⇔(iv) is false. Since t(C_k, W) = Σ_{λ∈Spec(W)} λ^k for k ≥ 3, these values depend only on the nonzero eigenvalues of T_W; the zero eigenvalue, with any multiplicity, contributes nothing. The proof of (ii)⇒(iii) selects a largest positive ν at which the spectra differ, but such a ν need not exist when the only spectral difference is in the zero eigenspace. Concretely, take λ_1 = 1/4 and λ_n = 2^{-n-3} for n ≥ 2, let (φ_n) be an orthonormal basis of L^2([0,1]) with φ_1 = 1 and |φ_n| ≤ √2, and set U(x,y) = λ_1 + Σ_{n≥2} λ_n φ_n(x)φ_n(y). Let W be the indicator of ∪_n (I_n × I_n), where the I_n are disjoint intervals with |I_n| = λ_n. Both are graphons with the same nonzero spectrum {λ_n : n ≥ 1}, so t(C_k, U) = t(C_k, W) for all k ≥ 3. But ker T_U = {0} while ker T_W is infinite-dimensional. No unitary T can satisfy T ∘ T_W = T_U ∘ T, because a nonzero f ∈ ker T_W would be mapped to an element of ker T_U = {0}, contradicting injectivity of T. Thus (i) does not imply (iv), and (i) does not imply (iii) when spectra are counted with multiplicities.","section":"Section 3, Theorem 3.2"},{"comment":"The construction of T relies on the spectra agreeing on all eigenspaces, including the zero eigenspace, because the direct sum decompositions include K_0 and L_0 and the isometries b_λ are chosen for every λ ∈ Spec(U) = Spec(W). If Spec is interpreted as the multiset of nonzero eigenvalues (a convention some graphon papers adopt), then (iii)⇒(iv) is false by the same counterexample above. If Spec includes zero with multiplicity, then (i)⇒(iii) is false. Thus under no interpretation of Spec are all four statements in Theorem 3.2 equivalent; the theorem needs to be restated, for example by separating the zero eigenspace and requiring a unitary or isometry between the orthogonal complements of the kernels.","section":"Section 3, proof of (iii)⇒(iv)"},{"comment":"The final inference \"By Parseval's Theorem (2.2) we conclude that U' and W' are not cospectral\" is not a direct consequence of Parseval alone. Parseval relates the L2 norm to the sum of squares of all eigenvalues, but cospectrality as defined in Definition 3.1 concerns cycle densities, which are sums of k-th powers for k ≥ 3. The needed implication is that different sums of squares of nonzero eigenvalues force different cycle densities for some k; this is true and can be proved by the argument in (ii)⇒(iii) restricted to the nonzero spectrum, but it should be stated explicitly rather than left as an immediate corollary of Parseval.","section":"Section 4, Proposition 4.3"}],"minor_comments":[{"comment":"The existence of the largest ν with different multiplicities is not explicitly justified. It follows because the nonzero eigenvalues of a compact self-adjoint operator have no accumulation point away from 0, but the proof should say this.","section":"Section 3, proof of (ii)⇒(iii)"},{"comment":"If α = 0, i.e., ν is the smallest positive eigenvalue modulus, then the strict inequalities in (3.1) cannot hold. The argument should treat this case separately, observing that the relevant sums in (T3) are empty for β < ν.","section":"Section 3, equation (3.1)"},{"comment":"References [9] and [10] are the same book (Lovász, Large networks and graph limits); one should be removed.","section":"References"},{"comment":"In the quoted statement of Theorem 4.1, \"Hn is Gn are fractionally isomorphic\" should read \"H_n and G_n are fractionally isomorphic.\"","section":"Section 4, Theorem 4.1"}],"recommendation":"major_revision","confidential_remarks":"The reader's report recommended acceptance, but the stress-test note identifies a genuine counterexample to Theorem 3.2. The zero-eigenvalue issue is not a minor oversight: it invalidates the paper's central equivalence. The inapproximability result (Theorem 4.2) appears salvageable, and the paper can likely be rewritten around a corrected statement that separates the nonzero-spectrum equivalence from the unitary-intertwiner condition. I would give the authors the opportunity to revise, but the current version should not be accepted as is."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The stress-test note is on target, and it kills the main theorem. The paper's contribution was to give three equivalent definitions of cospectral graphons—cycle densities, spectra, and unitary intertwining—but the equivalence between the first and the last fails exactly at the zero eigenvalue. For finite graphs the nullity is determined by the vertex count, so the cycle traces see it. For graphons the kernel can have different dimensions independently of the nonzero spectrum, and the paper's proof ignores that.\n\nConcretely, take any graphon with a complete orthonormal eigenbasis (trivial kernel) and match its nonzero eigenvalues with a block graphon supported on a proper subset, whose kernel is infinite-dimensional. Both have the same t(C_k, ·) for every k≥3, yet no unitary T can intertwine them because a unitary would have to map the infinite-dimensional kernel of one into the trivial kernel of the other. In the proof of (ii)⇒(iii), the chosen ν is the largest positive modulus with a multiplicity difference; if the only spectral difference is at 0, no such ν exists and the proof never starts. The proof of (iii)⇒(iv) constructs T only on the nonzero eigenspaces and never addresses the kernel.\n\nCredit where due: the inapproximability result (Theorem 4.2 and Proposition 4.3) is clean and correct, and it is a genuinely interesting counterpoint to the approximability result for fractional isomorphism. The writing is careful and the paper is easy to read. But the false theorem is not a minor gap; it is the central advertised result. A revision that adds a zero-eigenvalue condition to the definition, or establishes a corrected equivalence, could make the paper useful. As it stands, I would not cite the theorem, though the inapproximability part might be citable separately.\n\nRecommendation: send to peer review because the flaw is subtle and the inapproximability result deserves an audience, but the referee should require a corrected Theorem 3.2. This is a serious thinker's paper that just has a real bug.","headline":"The paper's main equivalence theorem is false: cycle densities can't see the zero eigenspace, so cospectral graphons need not be unitarily equivalent.","tokens_in":8214,"tokens_out":13439,"would_cite":false,"duration_ms":128359,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper defines cospectral graphons and proves that three natural definitions—equal cycle densities, equal spectra, and a unitary intertwining operator—are equivalent.","keywords":["graphons","cospectral graphons","cycle densities","graph spectra","unitary operators","cut distance","graph limits"],"falsifier":"Find a specific pair of bounded symmetric functions $U,W$ on $[0,1]^2$ with $t(C_k,U)=t(C_k,W)$ for all $k\\ge 3$ (or for infinitely many odd and infinitely many even $k$) but with different operator spectra, or exhibit any pair that violates one of the three equivalent criteria; such an example would disprove Theorem 3.2.","tokens_in":7208,"feed_emoji":"📊","tokens_out":8897,"duration_ms":80668,"temperature":0.7,"pith_summary":"Graphons are the standard limit objects of dense graph sequences, and many graph invariants extend naturally to them. This paper introduces a notion of cospectral graphons, paralleling cospectral finite graphs, and proves that three candidate definitions coincide: equal cycle densities at all lengths at least three, identical operator spectra, and the existence of a unitary operator intertwining the two graphon operators. Even equality of cycle densities for infinitely many odd and infinitely many even lengths is enough. The paper then shows a disanalogy with finite graphs: there are cospectral graphons that are limits of convergent graph sequences in which the approximating graphs are never cospectral, so cospectrality cannot always be lifted from limits to finite approximations. This matters because it delimits what spectral properties of large graphs can be read off from their limits.","feed_headline":"Graphon cospectrality: cycle densities equal spectra","feed_subtitle":"Equal cycle densities, equal spectra, and unitary conjugation all define the same relation on graph limits.","key_machinery":"The central object is the graphon viewed as an integral operator $T_W$ on $L^2([0,1])$, a symmetric Hilbert-Schmidt operator with discrete real spectrum whose eigenvalues are square-summable. Two facts carry the argument: Parseval's identity $\\|W\\|_2^2 = \\sum_{\\lambda \\in \\operatorname{Spec}(W)} \\lambda^2$ and the formula $t(C_k,W)=\\sum_{\\lambda \\in \\operatorname{Spec}(W)} \\lambda^k$ for $k\\ge 3$. The proof of Theorem 3.2 decomposes the eigenvalue sum into a top part at the farthest eigenvalue modulus $\\nu$ with a multiplicity mismatch, a middle part with $h$ terms bounded by $\\alpha^k$ for $\\alpha<\\nu$, and a tail whose $\\ell^2$-sum is small, then uses the parity of the multiplicity imbalance to show the $\\nu^k$ term does not cancel for one parity.","core_discovery":"The central claim, Theorem 3.2, is that for any two graphons $U$ and $W$ the following are equivalent: (i) $t(C_k,U)=t(C_k,W)$ for every $k\\ge 3$; (ii) the same equality holds for infinitely many odd and infinitely many even $k$; (iii) $\\operatorname{Spec}(U)=\\operatorname{Spec}(W)$, meaning the eigenvalues with multiplicities coincide; and (iv) there exists a unitary operator $T:L^2([0,1])\\to L^2([0,1])$ with $T\\circ T_W=T_U\\circ T$. The proof of (ii)$\\Rightarrow$(iii) chooses $\\nu$, the largest eigenvalue modulus at which multiplicities differ, splits each eigenvalue sum at $\\nu$ and at a small cutoff $\\beta$, and uses square-summability of the spectrum to control the tail by $(h+2)\\alpha^k$ with $\\alpha<\\nu$; the coefficient of $\\nu^k$ then has a nonzero value for one of the two parities, forcing infinitely many differences. The equivalence is a direct translation of the finite-graph fact that cycle homomorphism counts are traces of powers of the adjacency matrix.","pith_inferences":["A likely next step is a graphon analogue of quantum isomorphism, since the same framework—families of test graphs, a unitary or projection operator, and an approximation theorem—applies; the paper notes no such extension exists.","The non-approximability result suggests that spectral fingerprints of large networks are not continuous under the cut distance even when limits are cospectral, which would caution against inferring cospectrality of large graphs from convergence to the same limit.","One could test the open problem computationally by randomizing the half-square graphon while preserving its $L^1$-norm and checking numerically whether cycle densities remain equal; such experiments could guide a construction."],"forward_implications":["Cospectrality of graphon limits is robust: any two graphons with the same cycle densities are automatically intertwined by a unitary operator, so spectral equality in the limit is a purely measure-theoretic statement.","The threshold is low: matching cycle densities on infinitely many odd and infinitely many even lengths already forces cospectrality, so verifying the full family is unnecessary.","The example in Theorem 4.2, $U\\equiv \\frac12$ and $W$ the indicator of $[0,\\frac12]^2$, shows cospectral graphon limits can arise from sequences of graphs that are never cospectral, and the same holds for any two graphons with different $L^1$-norms.","The open Problem 4.4 asks whether equal-$L^1$ cospectral graphons can fail to be cospectrally approximable; if the answer is no, the obstruction in Theorem 4.2 is essentially the only one."],"supporting_citations":[{"why":"Supplies the spectral theory of graphon operators: $T_W$ is Hilbert-Schmidt with discrete real spectrum, Parseval's identity, and the formula $t(C_k,W)=\\sum\\lambda^k$.","marker":"[9]"},{"why":"Introduces graphons as limits of dense graph sequences and defines homomorphism densities $t(F,W)$.","marker":"[11]"},{"why":"Provides the cut distance and convergence framework used in the inapproximability theorem.","marker":"[2]"},{"why":"States the fractional-isomorphism approximation theorem that the negative approximation result for cospectral graphons is modeled on.","marker":"[6]"},{"why":"Gives the unitary-operator characterization of weak isomorphism, the model for the unitary criterion in Theorem 3.2.","marker":"[3]"}],"fun_headline_variants":["Cospectral graphons: three equivalent definitions","Graphon cospectrality: spectra, cycles, and unitaries","Cospectral graphons defy graph approximation","Cycle densities capture graphon spectra","When graphons share spectra and cycles"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The equivalence relies on graphon operators being compact, self-adjoint Hilbert-Schmidt operators with square-summable eigenvalues; if a graphon-like kernel lacked this spectral structure, equal cycle densities would no longer pin down the spectrum.","fun_headline_variants_meta":{"raw":{"variants":["Cospectral graphons: three equivalent definitions","Graphon cospectrality: spectra, cycles, and unitaries","Cospectral graphons defy graph approximation","Cycle densities capture graphon spectra","When graphons share spectra and cycles"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000572,"raw_usage":{"total_tokens":2649,"prompt_tokens":833,"completion_tokens":1816,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":449,"completion_tokens_details":{"reasoning_tokens":1749}},"tokens_in":449,"tokens_out":1816,"duration_ms":12563,"temperature":1.0,"reasoning_tokens":1749,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:42:57.407060+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a specific pair of bounded symmetric functions $U,W$ on $[0,1]^2$ with $t(C_k,U)=t(C_k,W)$ for all $k\\ge 3$ (or for infinitely many odd and infinitely many even $k$) but with different operator spectra, or exhibit any pair that violates one of the three equivalent criteria; such an example would disprove Theorem 3.2.","supporting_citations":[{"cited_title":"60, American Mathematical Society, Providence, RI, 2012","cited_arxiv_id":null,"evidence_quote":"Supplies the spectral theory of graphon operators: $T_W$ is Hilbert-Schmidt with discrete real spectrum, Parseval's identity, and the formula $t(C_k,W)=\\sum\\lambda^k$."},{"cited_title":"Lovász and B","cited_arxiv_id":null,"evidence_quote":"Introduces graphons as limits of dense graph sequences and defines homomorphism densities $t(F,W)$."},{"cited_title":"Borgs, J","cited_arxiv_id":null,"evidence_quote":"Provides the cut distance and convergence framework used in the inapproximability theorem."},{"cited_title":"Hladký and E","cited_arxiv_id":null,"evidence_quote":"States the fractional-isomorphism approximation theorem that the negative approximation result for cospectral graphons is modeled on."},{"cited_title":"Borgs, J","cited_arxiv_id":null,"evidence_quote":"Gives the unitary-operator characterization of weak isomorphism, the model for the unitary criterion in Theorem 3.2."}],"review_version":1}