{"id":"4b78a0d5-d3e9-4cac-a961-8f0be1423947","arxiv_id":"1908.03647","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Computational evidence supports a Boundary Conjecture that pairs of permutation matrices determine the boundary of the doubly stochastic eigenvalue region, and indicates that the Perfect-Mirsky region equals the full region for n=6 through 11, with a unique exception at n=5.","lead":"This paper studies which complex numbers can occur as an eigenvalue of a doubly stochastic matrix, a question that remains open for matrices larger than 4 by 4. It proposes that the boundary of this region is always produced by mixing at most two permutation matrices, and computer experiments support this and suggest the older Perfect-Mirsky region may be correct for sizes 6 through 11.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No bound connects the chosen mesh sizes (m=10000/1000/200) to the minimum gap between pair eigenpaths and ∂PM_n, so the n=6–11 evidence could miss a narrow excursion between sample points.","rationale":"The reader's weakest assumption — finite mesh sufficiency — is precisely the load-bearing concern. The paper provides honest computational evidence, but the n=6–11 conclusion requires that no eigenvalue excursion leaves PM_n between sample points. No analytical or numerical bound is given for this, and Section 5's own caveat admits that finer meshes may be needed for larger n. The A_4/A_5 counterexamples in Section 6 further show that the analogous pair-boundary property fails for closely related standard representations, so the pair-only reduction cannot be taken for granted. However, this is a limitation of evidence rather than an internal contradiction: the paper states its claims conditionally, includes code, and gives a detailed n=5 analysis. The proposed adaptive certification is a feasible, concrete check that would either validate the computational evidence or expose a missed excursion. Since the reader's CONDITIONAL verdict already reflects this uncertainty, no change to the verdict is needed.","tokens_in":11171,"tokens_out":20522,"duration_ms":242424,"concrete_test":"For n=10, take the inequivalent pairs from Algorithm 1 and replace the fixed m=1000 mesh with an adaptive, certification-oriented search: for each pair, track every eigenvalue branch t ↦ λ(t) of (1−t)P + tQ, and compute the signed distance of λ(t) to ∂PM_n to high precision, subdividing t-intervals wherever the distance decreases and using interval arithmetic or root-finding to determine whether any branch crosses ∂PM_n. If any branch leaves PM_n, Conjecture 7.1 is false for n=10; if every branch is certified to stay inside, the mesh concern is settled for that case. As a secondary check, repeat the same adaptive scan for a random sample of triples of permutations for n=7 to test whether eigenvalues outside the pair region appear, which would weaken the Boundary Conjecture premise.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central evidence for Conjecture 7.1 is a discrete scan: for each inequivalent pair of permutations, eigenvalues are computed at finitely many convex coefficients t, with m=10000 for n=6–9, m=1000 for n=10, and m=200 for n=11. Since DS_n is star-shaped from 0, it is enough to certify that no boundary point of DS_n lies outside PM_n. But no theorem bounds the required mesh size in terms of the minimal distance by which an exceptional eigenpath could leave PM_n. Section 5 explicitly acknowledges that 'finer mesh sizes to be necessary for larger n' are plausible because 'the absolute distance by which any exceptional curve leaves the region might be smaller.' For n=5 the exceptional curve leaves PM_5 over a coefficient interval of length roughly 0.0785, so a coarse mesh catches it; for n≥6 there is no analogous quantitative benchmark, and the plotted curves being 'quite far' from the boundary is not a certified margin. The Boundary Conjecture itself is a second unproved premise: if some boundary point of DS_n first appears only with triples or higher convex combinations, the pair-only scan would miss it. The paper's Section 6 supplies a concrete warning: for the standard representations of A_4 and A_5, pairs do not determine the boundary of the hull spectrum, and triples produce eigenvalues outside the pair region. The paper argues that adding odd permutations may restore the property for S_n, but the A_4/A_5 examples show the pair-boundary property is not automatic. The triple and quadruple computations for n≥6 are not exhaustive either. Thus Conjecture 7.1 rests on two unquantified sampling/search assumptions.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the set DS_n of complex numbers occurring as eigenvalues of n-by-n doubly stochastic matrices. It states the Boundary Conjecture (Conjecture 2.7) that every boundary point of DS_n is an eigenvalue of a convex combination of at most two permutation matrices, and it develops a computational method, based on group-theoretic reduction to inequivalent pairs of permutations, to search for eigenvalues outside the Perfect-Mirsky region PM_n. The paper reports that no counterexamples to the Perfect-Mirsky conjecture were found for n = 6 through 11, leading to Conjecture 7.1 that DS_n = PM_n for those n, and it analyzes the exceptional n = 5 case in detail, including the observation that only one inequivalent pair generates an eigenvalue outside PM_5. The authors also report that for the standard representations of A_4 and A_5, the analogous pair-boundary property fails, and they acknowledge the finite-mesh limitations of their evidence.","tokens_in":11506,"tokens_out":5793,"duration_ms":58071,"significance":"If the Boundary Conjecture is correct, the doubly stochastic single eigenvalue problem reduces on the boundary to one-parameter families of convex combinations of two permutation matrices, making numerical exploration tractable and potentially leading to a proof of Perfect-Mirsky for small n. The paper's rigorous lemmas (e.g., Lemma 2.3 and Corollary 2.4 on star-shapedness), the group-theoretic reduction to inequivalent pairs (Algorithm 1 and Table 1), and the reproducible code repository are genuine strengths. The explicit discussion of the A_4 and A_5 counterexamples to the pair-boundary property is honest and important. However, the central evidence for both Conjecture 2.7 and Conjecture 7.1 is finite sampling without certified error bounds, so the conjectures should be regarded as heuristic rather than established.","major_comments":[{"comment":"The evidence for DS_n = PM_n for n = 6,...,11 rests on finite mesh searches with m = 10000 for n = 6-9, m = 1000 for n = 10, and m = 200 for n = 11, and no bound is given that relates the mesh size to the minimum distance by which an eigenpath could leave PM_n between sample points. The paper itself notes in Section 5 that finer meshes may be necessary for larger n because exceptional excursions might be smaller. Without a certified numerical method (for example, interval arithmetic applied to the characteristic polynomials, or Lipschitz estimates for eigenvalues as functions of the convex parameter t), the computations cannot rule out a narrow excursion, and the statement of Conjecture 7.1 as unqualified is stronger than the evidence supports. The authors should either supply such a certificate or explicitly label the conjecture as heuristic and conditional on the mesh resolution.","section":"§5, Conjecture 7.1"},{"comment":"The pair-only search for counterexamples to the Perfect-Mirsky conjecture is justified by the Boundary Conjecture (Conjecture 2.7), but Section 6 shows that for the standard representations of A_4 and A_5, pairs do not determine the boundary of the hull spectrum and triples produce eigenvalues outside the pair region. Since these groups are closely related to S_4 and S_5, this is a concrete warning that the boundary of DS_n might require convex combinations of more than two permutations for some n. Consequently, the computational evidence for DS_n = PM_n is conditional on the very conjecture under test. The authors should either provide a direct certified search over triples (and, where feasible, higher combinations) for n = 6,...,11, or qualify Conjecture 7.1 as contingent on the Boundary Conjecture.","section":"§6, Figs. 7-8"}],"minor_comments":[{"comment":"The abstract states that PM_n = DS_n is known for n ≤ 4, while the introduction says 'for n < 4'; these statements should be made consistent (the cited result [12] proves the n = 4 case).","section":"Abstract / §1"},{"comment":"The text says the exceptional curve 'leaves PM 5 near the intersection of Π3 with Π4 and barely stays within PM 5 near the intersection of Π4 and Π5,' but the caption of Figure 2 says it 'leaves PM 5 above the intersection of Π3 and Π5'; the inconsistency should be resolved.","section":"§4, Fig. 2"},{"comment":"Observation 4.1 is stated as a definitive claim ('There is only one inequivalent pair ... that generates an eigenvalue outside PM 5'), but it is a computational observation. The authors should explicitly state the mesh size and numerical precision used for the eigenpath scan, and ideally indicate whether the claim is certified or merely supported by sampling.","section":"§4, Observation 4.1"},{"comment":"The phrase 'we have spent much CPU time (> 2 years) on searching' is informal; a quantitative description of the computational resources (e.g., core-hours) would be more appropriate for a formal paper.","section":"§7"}],"recommendation":"major_revision","confidential_remarks":"This is a computational and conjectural contribution rather than a theorem-based paper. The group-theoretic reduction and the honest presentation of the A_4/A_5 caveat are valuable, but the two central conjectures rest on finite sampling without certified bounds. If the journal is willing to publish computational evidence for conjectures, the paper could be acceptable after the authors either strengthen the numerical claims with certification or carefully weaken the statements to emphasize their heuristic status."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper is worth a serious look. The genuinely new pieces are the Boundary Conjecture, the double-coset reduction that makes inequivalent pair enumeration tractable up to n=13, and the exhaustive n=5 classification showing that only one inequivalent pair leaves PM5. The code is public, the n=5 analysis is careful, and the authors are unusually honest about what is and is not covered by their computations. For that I give them real credit.\n\nThe soft spots are real but not fatal, and the reader's stress test basically lands. The n=6–11 evidence for Conjecture 7.1 is an unquantified finite scan: no theorem connects the mesh size to the minimum distance by which an exceptional eigenpath could leave PM_n. The n=5 interval is wide enough that coarse meshes catch it, but there is no analogous benchmark for larger n, and the paper says as much in Section 5. The Boundary Conjecture itself is also doing load-bearing work: if boundary points first appear via triples or higher combinations, the pair-only scan misses them. The A4 and A5 examples show the pair-boundary property is not automatic for closely related representation-theoretic settings.\n\nWhat strikes me is that the paper does not overclaim. The conjectures are labeled conjectures, the mesh issue is openly acknowledged, and the triple/quadruple checks for n=5 and partial triple checks for n≥6 are presented as supporting evidence, not proof. The main weakness is that the headline claim \"DS_n = PM_n for n=6,...,11\" rests on two unproved premises, and the paper could have done more to quantify the required mesh size or at least flag more prominently that Conjecture 7.1 is a sampling conjecture.\n\nWho is this for? People working on the inverse eigenvalue problem for doubly stochastic matrices, and more broadly anyone interested in hull spectra of matrix groups. The double-coset reduction is a nice computational contribution in its own right. I would cite this paper for the n=5 result and the pair reduction. It deserves a serious referee: the computational claims are checkable, the exposition is clear, and the conjectures are positioned honestly. My recommendation is to send it to peer review with a request that the authors either bound the mesh error or soften the wording of Conjecture 7.1 to explicitly say \"computational evidence for\". I would not desk-reject this.","headline":"A genuinely useful computational paper with honest conjectures; the n=5 classification and pair-reduction are real contributions, but the n=6–11 Perfect-Mirsky evidence is finite sampling and should be framed as such.","tokens_in":12040,"tokens_out":1082,"would_cite":true,"duration_ms":12650,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15-04","15A18","15A29","15B51"],"pacs":[],"model":"deepseek-v4-flash","headline":"Pairing two permutation matrices may determine the whole boundary of the doubly stochastic eigenvalue region.","keywords":["doubly stochastic matrix","eigenvalue","permutation matrix","group representation","single eigenvalue problem","Perfect-Mirsky region","Boundary Conjecture","convex combination"],"falsifier":"For any n in {6,7,8,9,10,11}, run an adaptive search over all inequivalent pairs that refines the mesh near the boundary of PM_n and find a single eigenvalue outside PM_n; or find a convex combination of three permutation matrices with an eigenvalue outside the region generated by all pairs. Either observation would refute the paper's main conjectures.","tokens_in":10974,"feed_emoji":"🧮","tokens_out":5900,"duration_ms":56818,"temperature":0.7,"pith_summary":"The paper tries to establish the Boundary Conjecture: every complex number on the boundary of DS_n, the set of eigenvalues of n-by-n doubly stochastic matrices, is already an eigenvalue of a convex combination of at most two permutation matrices. If true, the hard task of characterizing all doubly stochastic eigenvalues reduces to studying line segments between pairs of permutation matrices. The authors support this conjecture with a computational method that cuts the number of permutation pairs to a tractable set and with searches for n up to 11. They further conjecture that DS_n equals the Perfect-Mirsky region PM_n for n = 6 through 11, and that the known n = 5 exception comes from a single inequivalent pair of permutations.","feed_headline":"Two permutations may draw the whole eigenvalue boundary","feed_subtitle":"Computations up to n=11 find no eigenvalues outside the Perfect-Mirsky region, supporting the pair-boundary conjecture.","key_machinery":"The machinery is the standard representation of the symmetric group: after conjugating by a fixed deflating matrix, each n-by-n permutation matrix becomes a block matrix whose lower right (n-1)-by-(n-1) block carries all eigenvalues except the common eigenvalue 1. The set of these blocks is an irreducible representation of S_n, and DS_n is the eigenvalue region of its convex hull. The computational reduction then uses double cosets of centralizers, via Mackey's formula, to pick one representative from each equivalence class of permutation pairs under uniform permutation similarity, cutting the number of pairs from O((n!)^2) to O(n!). Along each pair, eigenvalues are computed on a mesh of convex coefficients, and each point is tested against the polygons Π_k whose union is PM_n.","core_discovery":"The central claim is that pairs determine the boundary: for every boundary point z of DS_n there are permutation matrices P and Q, possibly equal, and a coefficient t in [0,1] such that z is an eigenvalue of tP + (1-t)Q. The paper does not prove this claim, but it provides the first systematic computational test of it. Using a deflation that removes the common eigenvalue 1 and a group-theoretic reduction to inequivalent pairs, the authors compute eigenpaths for all representative pairs for n up to 11 and find no counterexample to the Perfect-Mirsky conjecture for n = 6 through 11. For n = 5, they locate the known exceptional eigenpath and show it is the only one, up to uniform permutation similarity, among all pairs of that cycle-type pairing.","pith_inferences":["A natural testable extension is to replace fixed meshes with adaptive refinement near the boundary of PM_n for n = 6 and 7; if an excursion narrower than the 1/10000 mesh exists, it would surface there.","The authors' observation that the alternating groups A4 and A5 in the standard representation violate the analogous pair-boundary property suggests the Boundary Conjecture for S_n depends on the full symmetric group and its star-shaped convex hull, not on a general fact about matrix-group hull spectra.","If the Boundary Conjecture is correct, double-coset enumeration could serve as a general tool for finding extremal eigenpaths in other spectral sets defined by convex hulls of group orbits."],"forward_implications":["If the Boundary Conjecture holds, then because DS_n is star-shaped from the interval [0,1], every point of DS_n is an eigenvalue of a convex combination of at most three permutation matrices.","For n = 6 through 11, the pair computations combined with the Boundary Conjecture would settle the Perfect-Mirsky conjecture for those dimensions, giving DS_n = PM_n.","The pair-reduction method makes the doubly stochastic single eigenvalue problem computationally feasible to high precision for moderate n, since only O(n!) representative pairs need checking rather than all convex combinations.","The n = 5 exception would be understood as a single isolated phenomenon among inequivalent pairs, giving a clear target for future theoretical explanation."],"supporting_citations":[{"why":"Establishes Birkhoff's theorem that every doubly stochastic matrix is a convex combination of permutation matrices, the starting point for studying DS_n through permutation pairs.","marker":"[1]"},{"why":"Supplies Mackey's formula and G-set machinery used to reduce pairs of permutations to one representative per diagonal-conjugation orbit.","marker":"[2]"},{"why":"Provides the double-coset representation enumeration and centralizer computations used in the pair-reduction algorithm.","marker":"[4]"},{"why":"Gives prior hull-spectra results for other matrix groups where pairs often determine the boundary, motivating the Boundary Conjecture.","marker":"[7]"},{"why":"Shows the Karpelevich region for row-stochastic matrices has boundary determined by pairs, an analogy for the pair-boundary claim.","marker":"[9]"},{"why":"Proves DS_4 = PM_4, the largest dimension previously settled and the baseline the computations extend.","marker":"[12]"},{"why":"Supplies the explicit 5-by-5 doubly stochastic matrix with eigenvalues outside PM_5, the exceptional case analyzed in detail.","marker":"[14]"},{"why":"Defines PM_n, proves its containment in DS_n and the star-shapedness of DS_n, and frames the Perfect-Mirsky conjecture.","marker":"[16]"}],"fun_headline_variants":["Pair of permutations may trace eigenvalue boundary","Eigenvalue boundary from permutation pairs","Computing the doubly stochastic eigenvalue region","Permutation pairs: key to eigenvalue boundary","Boundary conjecture tested up to n=11"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The conclusion rests on the assumption that the finite mesh of convex coefficients used for each pair of permutations is fine enough to catch every interval where an eigenpath leaves PM_n; for n = 11 the mesh is 1/200, and no bound ties that spacing to the size of a possible excursion.","fun_headline_variants_meta":{"raw":{"variants":["Pair of permutations may trace eigenvalue boundary","Eigenvalue boundary from permutation pairs","Computing the doubly stochastic eigenvalue region","Permutation pairs: key to eigenvalue boundary","Boundary conjecture tested up to n=11"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000188,"raw_usage":{"total_tokens":1287,"prompt_tokens":853,"completion_tokens":434,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":469,"completion_tokens_details":{"reasoning_tokens":370}},"tokens_in":469,"tokens_out":434,"duration_ms":4352,"temperature":1.0,"reasoning_tokens":370,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:07:03.454033+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For any n in {6,7,8,9,10,11}, run an adaptive search over all inequivalent pairs that refines the mesh near the boundary of PM_n and find a single eigenvalue outside PM_n; or find a convex combination of three permutation matrices with an eigenvalue outside the region generated by all pairs. Either observation would refute the paper's main conjectures.","supporting_citations":[{"cited_title":"Birkhoff , Three Observations on Linear Algebra (Spanish) , Univ","cited_arxiv_id":null,"evidence_quote":"Establishes Birkhoff's theorem that every doubly stochastic matrix is a convex combination of permutation matrices, the starting point for studying DS_n through permutation pairs."},{"cited_title":"Bouc, Burnside rings , in Handbook of Algebra, vol","cited_arxiv_id":null,"evidence_quote":"Supplies Mackey's formula and G-set machinery used to reduce pairs of permutations to one representative per diagonal-conjugation orbit."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the double-coset representation enumeration and centralizer computations used in the pair-reduction algorithm."},{"cited_title":"Jankowski, C","cited_arxiv_id":null,"evidence_quote":"Gives prior hull-spectra results for other matrix groups where pairs often determine the boundary, motivating the Boundary Conjecture."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows the Karpelevich region for row-stochastic matrices has boundary determined by pairs, an analogy for the pair-boundary claim."},{"cited_title":"Levick, R","cited_arxiv_id":null,"evidence_quote":"Proves DS_4 = PM_4, the largest dimension previously settled and the baseline the computations extend."},{"cited_title":"Mashreghi and R","cited_arxiv_id":null,"evidence_quote":"Supplies the explicit 5-by-5 doubly stochastic matrix with eigenvalues outside PM_5, the exceptional case analyzed in detail."},{"cited_title":"Perfect and L","cited_arxiv_id":null,"evidence_quote":"Defines PM_n, proves its containment in DS_n and the star-shapedness of DS_n, and frames the Perfect-Mirsky conjecture."}],"review_version":1}