{"id":"9d597f4f-4591-4f3f-aa99-680441226aa5","arxiv_id":"1908.04708","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Defines superpermutation matrices, reduces their row/column minimization to a universal word problem for quotient classes in S_n, and proves the ratio of the resulting upper and lower bounds tends to 2 as n grows.","lead":"Starting from superpermutations, this paper introduces 'superpermutation matrices': toric 0-1 grids that contain every permutation matrix as a block. It connects the minimal size of such grids to a new universal word problem and proves the ratio of its best upper and lower bounds approaches 2.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 7's proof of the key asymptotic bound contains a printed inequality that is false (e.g., d=2,n=8); the limit B(n)/(n-1)! -> 2 is not rigorously established as written.","rationale":"The paper's central construction and bounds are coherent: the transition-graph reduction is natural, the upper-bound Hamiltonian path is valid once the <= n-1 edge-weight claim is supplied (and that claim is true), and the lower-bound induction in Theorem 6 works for the n-2 version that the proof actually establishes. My stress-test therefore does not challenge the existence of the bounds or the truth of the asymptotic ratio. The load-bearing gap I find is in the written proof of Theorem 7, the step that makes the asymptotic limit rigorous. The displayed inequality controlling the proper-divisor sum v_n is false as printed; the numerical counterexample n=8, d=2 is easy to check. Since Theorem 8 depends on Lemma 7, which depends on Theorem 7, the central asymptotic claim is not established by the manuscript as written. This is not a rejection: the gap is localized, a corrected bound seems available, and computational checks of the formulas for small n are consistent. I agree with the reader's CONDITIONAL verdict, but not with the location of the weakest assumption: the edge-weight bound is a non-issue, whereas the Theorem 7 proof needs repair.","tokens_in":12281,"tokens_out":26537,"duration_ms":259551,"concrete_test":"Re-derive the inequality in Theorem 7 and evaluate it at n=8, d=2: the printed bound gives 1/(6!) * (2/8)^2 ~ 8.7e-5, while the term T_2 = phi(4) * 8^1 * 1! / (2^2 * 6!) = 1/180. Then install the corrected bound T_d <= n(n-1)/(d^2 (n-d)!) for all proper divisors d|n and recompute v_n; if the corrected sum still tends to 0 and L(n)/(n-2)! -> 1 (analytically, or numerically for n up to 200), the central claim stands with a repaired proof. If no correct bound can be found, the limit theorem is unproved.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The advertised asymptotic claim (Theorem 8) rests on Lemma 7, which in turn rests on Theorem 7's assertion that v_n = sum_{d|n, d= floor(n/2)! it still forces v_n -> 0. I do not see a counterexample to the theorem itself; for small n the table and direct computation via Lemma 6 agree. The edge-weight bound in Proposition 7, highlighted by the reader, is not the true soft spot: for distinct R2-classes one can choose representatives with matching last/first symbols, so an overlap of length at least 1 always exists and the transition costs at most n-1. The statement of Theorem 6 also has an off-by-one (the proof and table give n-2, not n-1), but that is a typo, not a threat to the corrected lower bound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper defines superpermutation matrices as toric 0-1 matrices containing every n by n permutation matrix as a block, and studies the minimal number of rows (or columns) of such a matrix. It shows this row and column minimization problem is equivalent by transposition (Proposition 4), and reduces it to a universal-word problem for the equivalence classes of S_n under cyclic row increments, denoted m(n). The main results are an upper bound B(n)=1+sum_{d|n}|cycles(1)(d)|(d+n-2) (Theorem 5), a lower bound C(n)=(n-1)!+n-2+sum_{d|n}|cycles(1)(d)| (Theorem 6, as proved), an explicit but slightly weaker upper bound B'(n) (Proposition 10), and the claim that B(n)/(n-1)! tends to 2 as n grows (Theorem 8). The counting of 1-cycles in the transition graph H_n is developed through the sets E(d,n), yielding the recursive formula in Proposition 8 and the closed form in Lemma 6.","tokens_in":12675,"tokens_out":17048,"duration_ms":153139,"significance":"This is a worthwhile contribution if the asymptotic claim can be properly supported. The paper introduces a clean matrix analogue of superpermutations, reduces the row and column minimization problems to universal words for equivalence classes, and obtains explicit, parameter-free bounds from first-principles counting of 1-cycles in the transition graph. The recursive enumeration of |cycles(1)(d)| via E(d,n) and the explicit Hamiltonian-path construction for the upper bound are concrete and checkable. The main advertised result, B(n)/(n-1)! tending to 2, is interesting and the ratio of upper to lower bound approaching 2 is a genuine quantitative statement. The weaknesses are localized proof gaps and typographical inconsistencies rather than a questionable research program.","major_comments":[{"comment":"The displayed estimate for a generic summand T_d = phi(n/d) n^{d-1}(d-1)!/(d^d (n-2)!) is false as printed. For n=8 and d=2, T_d = phi(4)*8^1*1!/(2^2*6!) = 16/2880 = 1/180, while the claimed upper bound 1/(n-d)! (d/n)^d equals 1/(720*16) = 1/11520. Since this estimate is the only mechanism used to show v_n -> 0, Lemma 7 and Theorem 8 are not established by the text. The gap appears localized and repairable: for example, using phi(n/d) <= n/d and an elementary product comparison gives T_d <= n(n-1)/(d^2 (n-d)!), and with d <= n/2 this suffices to force v_n -> 0. I request that the corrected argument be incorporated.","section":"Section 3.2, proof of Theorem 7"},{"comment":"The theorem statement gives the lower bound as C(n) = (n-1)! + n - 1 + sum_{d|n} |cycles(1)(d)|, but the induction proof in the same section and the numerical table in Figure 4 use (n-1)! + n - 2 + sum_{d|n} |cycles(1)(d)|. For n=3 the stated formula would give 6 rather than the table's value 5. The statement should be corrected to n-2; the proof itself is consistent with the corrected value.","section":"Section 3.1, Theorem 6"},{"comment":"The upper bound construction in Theorem 5 requires that every edge of H_n has weight at most n-1, but Proposition 7 only asserts this without proof. The assertion is true and easy to justify: for two distinct R2-classes, one can choose representatives A and B whose last and first columns coincide by shifting both row labels by suitable constants, so appending the remaining n-1 columns of B realizes the transition. Please add this argument, since as written it is a load-bearing unproved premise.","section":"Proposition 7 and proof of Theorem 5"}],"minor_comments":[{"comment":"When H_n is introduced for Problem 2, its vertices are described as equivalence classes for R1; they should be equivalence classes for R2.","section":"Section 2.3, definition of H_n"},{"comment":"The conditions denoted D(k) ∩ D(n) = {1} and k' ∧ p would be much clearer if written gcd(k,n)=1 and gcd(k',p)=1, respectively.","section":"Proofs of Lemma 5 and Lemma 6"},{"comment":"The displayed formulas are missing parentheses: the factor (n-2), respectively (n-2)/(n-1), should multiply the entire sum over divisors, not a single summand. Also, '1 - cycles(d)' in the proof of Proposition 10 should read 'cycles(1)(d)'.","section":"Proposition 10 and Theorem 7"},{"comment":"The table would be more informative if it included the ratio B(n)/C(n) or B(n)/(n-1)! for the displayed values, since the asymptotic claim is about the behavior of these ratios.","section":"Figure 4"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper introduces superpermutation matrices and connects their minimal size to a universal word problem for equivalence classes of S_n under cyclic row increments. That problem and the bounds m(n) are genuinely new, and the counting of 1-cycles via Euler's totient is a nice piece of work. The reduction from toric matrices to words (Propositions 5 and 6) is clean, and the explicit constructions for the upper bound are concrete enough to follow. Small-n values in the table match the formulas, which is a good sanity check.\n\nThe soft spots are real but localized. Theorem 6 states the lower bound as (n-1)! + n - 1 + sum, but the proof and table use n - 2. That is a typo, not a structural problem. The more serious issue is Theorem 7: the printed bound on the generic term is false, as the stress-test note shows for n=8,d=2. The derivation of v_n -> 0 is therefore not valid as written. However, the limit itself is true and can be recovered with a corrected bound, so the asymptotic claim survives but needs a rewrite of that proof. The reader's worry about Proposition 7's edge-weight bound is, I think, misplaced: for distinct R2-classes you can rotate representatives to get a matching first/last column, so a transition cost of at most n-1 always exists. The proof should say that in one sentence.\n\nOne more wording issue: the conclusion says both bounds are equivalent to 2I(n), but only the upper bound has that property; the lower bound is asymptotic to I(n). The intended statement is presumably that the ratio of upper to lower tends to 2.\n\nOverall, the core mathematics is sound and the new problem is worth knowing. The asymptotic result is probably correct, but the proof as printed is incomplete. This is exactly the kind of paper that peer review can fix: a referee should ask for a corrected Theorem 7 proof, the n-2 correction in Theorem 6, and a clearer conclusion. It deserves a serious referee, not a desk reject.","headline":"New matrix analogue of superpermutations with mostly sound bounds, but the asymptotic proof has a repairable gap and one off-by-one typo.","tokens_in":13218,"tokens_out":2741,"would_cite":false,"duration_ms":27960,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05A05","05C45","68R15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that the shortest word hitting every permutation class under cyclic increments lies between two explicit bounds whose ratio tends to 2.","keywords":["superpermutation matrices","universal words","symmetric group quotients","cyclic increments","transition graph","1-cycles","Hamiltonian paths","totient-function bounds"],"falsifier":"Compute the full transition graph $H_6$ and check whether every pair of cycles made of weight-1 edges has a connecting edge of weight at most 5; if any such edge has weight 6 or more, the upper bound $B(6)$ is not valid. Equivalently, an exhaustive search that finds a universal word of length below $C(6)=148$, or proves that no universal word of length at most $B(6)=217$ exists, would contradict the corresponding bound.","tokens_in":12043,"feed_emoji":"🧩","tokens_out":19191,"duration_ms":164058,"temperature":0.7,"pith_summary":"The paper introduces superpermutation matrices: toric (wrap-around) 0-1 matrices that contain every permutation matrix as a contiguous block, and shows that minimizing their width is equivalent to finding a shortest universal word for the equivalence classes of $S_n$ under cyclic increments of the entries, meaning a word that contains at least one member of each class as a contiguous factor. For the minimal length $m(n)$ of such a word, it proves a lower bound $C(n) = (n-1)! + n - 2 + \\sum_{d\\mid n} |\\mathrm{cycles}^{(1)}(d)|$ and an upper bound $B(n) = 1 + (n-1)! + (n-2) \\sum_{d\\mid n} |\\mathrm{cycles}^{(1)}(d)|$, where $|\\mathrm{cycles}^{(1)}(d)|$ counts cycles of weight-1 transitions of length $d$ in a transition graph. The paper further proves that $B(n)/(n-1)! \\to 2$ as $n \\to \\infty$, while the lower bound grows like $(n-1)!$, so the best proven upper and lower constructions differ asymptotically by exactly a factor of 2. This leaves the exact growth of $m(n)$ open but confines it to an explicitly computable interval, and the same graph construction yields explicit superpermutation matrices for small $n$.","feed_headline":"Word length for rotated permutation classes trapped in factor 2","feed_subtitle":"A matrix-to-word reduction gives explicit lower and upper bounds whose ratio tends to exactly 2.","key_machinery":"The central object is the transition graph $H_n$. Its vertices are the $(n-1)!$ equivalence classes of $S_n$ under cyclic increments, the relation $R_2$ where $\\pi \\sim \\sigma^i\\pi$ for $i \\in \\mathbb{Z}/n\\mathbb{Z}$, and the weight of an edge from the class of $\\pi$ to the class of $\\pi'$ is the minimal number of extra columns needed to move from a word representing one class to a word representing the other. Weight-1 edges form directed cycles, the 1-cycles; a key structural fact proved as Lemma 3 is that the length $d$ of any 1-cycle divides $n$, and the counts $|\\mathrm{cycles}^{(1)}(d)|$ are computed recursively from sets $E(d,n)$ using the totient function. These counts enter both bounds. Proposition 6 states that a path through all vertices of $H_n$ is exactly a universal word of length equal to the path weight plus $n$; the upper bound is a greedy Hamiltonian path visiting whole 1-cycles, and the lower bound is a counting inequality on the weight of any covering path.","core_discovery":"The central discovery is that the minimal width $m_1(n)=m_2(n)$ of a superpermutation matrix is controlled by a word problem on a quotient of the symmetric group: by transposition the row-minimal and column-minimal problems coincide, and both lie within $n-1$ of the minimal length $m(n)$ of a word over $\\{1,\\dots,n\\}$ that contains, for every permutation, at least one representative of its class under the relation $\\pi \\sim \\sigma^i \\pi$ (cyclic increment of all entries by $i$). The paper proves that $C(n) \\le m(n) \\le B(n)$. The lower bound follows from a path-covering argument: any path through all $(n-1)!$ classes has weight at least $(n-1)! + \\sum_{d\\mid n}|\\mathrm{cycles}^{(1)}(d)| - 2$, so any word has length at least $C(n)$. The upper bound is constructive: traverse each 1-cycle completely using weight-1 edges, jump between 1-cycles with edges of weight at most $n-1$, and add the initial $n$ letters, giving a universal word of length at most $B(n)$. Finally, using an auxiliary explicit bound $B'(n)$ built from the totient function, the paper proves $\\lim_{n\\to\\infty} B(n)/(n-1)! = 2$, so the asymptotic ratio of the best proven upper to lower bound is exactly 2.","pith_inferences":["Extension, not in the paper: the same 1-cycle counting should transfer to quotients of $S_n$ by other cyclic subgroups or by reversal symmetries; the only needed ingredient is a structural lemma pinning cycle lengths to divisors of the group order, which would give analogous constant-factor bounds for those variants.","Extension, not in the paper: the gap between $C(n)$ and the best found lengths suggests $m(n)$ may be strictly below $B(n)$ already at $n=5$; an exact computation of $m(5)$ or $m(6)$ by exhaustive search would test how much weight-2 edges can improve the upper bound.","Extension, not in the paper: if the monotonicity of $u_n = B(n)/(n-1)!$ (posed as an open question in the paper) can be proved, the limit 2 becomes uniform, yielding $m(n) \\le 2(n-1)!$ for all $n \\ge 6$."],"forward_implications":["For every $n$, the minimal universal-word length $m(n)$ lies between $C(n)$ and $B(n)$; numerically, $C(5)=35$, the best found word has length 39, and $B(5)=49$, with similar gaps for $n \\le 8$.","Because $B(n)/(n-1)! \\to 2$ while $C(n)/(n-1)! \\to 1$, every word covering all cyclic-increment classes has length asymptotic to some value between $(n-1)!$ and $2(n-1)!$, so no construction of this type can close the multiplicative gap further.","The upper-bound construction is explicit: a nearest-neighbour greedy traversal of the 1-cycles produces a universal word and hence a superpermutation matrix with at most $B(n)$ columns.","For prime $n$, the formulas specialize to $|\\mathrm{cycles}^{(1)}(1)| = n-1$ and $|\\mathrm{cycles}^{(1)}(n)| = ((n-1)!-(n-1))/n$, making the bounds fully explicit.","The auxiliary bound $B'(n)$ uses only the totient function and factorials, so it can be evaluated without the recursive cycle count, and it also satisfies $B'(n)/(n-1)! \\to 2$."],"supporting_citations":[{"why":"It supplies the lower-bound technique for superpermutation length via weight-1 and weight-2 cycles that the paper adapts to 1-cycles on the quotient graph.","marker":"[1]"},{"why":"It defines superpermutations and the recursive construction whose matrix analogue motivates the new problems.","marker":"[2]"},{"why":"It gives the best known superpermutation construction against which the new word bounds are compared.","marker":"[5]"},{"why":"It establishes the transition-graph and travelling-salesman viewpoint for superpermutation length that the quotient graph $H_n$ extends.","marker":"[7]"}],"fun_headline_variants":["Superpermutation matrix bounds reach asymptotic ratio 2","Rotated permutation words: proven bounds converge to factor 2","New matrix link pins universal word length ratio to 2","Matrix-to-word reduction yields tight 2 limit for superpermutations"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The upper bound assumes that between any two cycles made of weight-1 edges in the transition graph there is an edge of weight at most $n-1$; if some such transition required $n$ or more added columns, the construction behind $B(n)$ would fail.","fun_headline_variants_meta":{"raw":{"variants":["Superpermutation matrix bounds reach asymptotic ratio 2","Rotated permutation words: proven bounds converge to factor 2","New matrix link pins universal word length ratio to 2","Matrix-to-word reduction yields tight 2 limit for superpermutations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000254,"raw_usage":{"total_tokens":1556,"prompt_tokens":922,"completion_tokens":634,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":538,"completion_tokens_details":{"reasoning_tokens":565}},"tokens_in":538,"tokens_out":634,"duration_ms":6893,"temperature":1.0,"reasoning_tokens":565,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:35:46.759320+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the full transition graph $H_6$ and check whether every pair of cycles made of weight-1 edges has a connecting edge of weight at most 5; if any such edge has weight 6 or more, the upper bound $B(6)$ is not valid. Equivalently, an exhaustive search that finds a universal word of length below $C(6)=148$, or proves that no universal word of length at most $B(6)=217$ exists, would contradict the corresponding bound.","supporting_citations":[{"cited_title":"Houston, J","cited_arxiv_id":null,"evidence_quote":"It supplies the lower-bound technique for superpermutation length via weight-1 and weight-2 cycles that the paper adapts to 1-cycles on the quotient graph."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It defines superpermutations and the recursive construction whose matrix analogue motivates the new problems."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It gives the best known superpermutation construction against which the new word bounds are compared."},{"cited_title":"Tackling the Minimal Superpermutation Problem","cited_arxiv_id":"1408.5108","evidence_quote":"It establishes the transition-graph and travelling-salesman viewpoint for superpermutation length that the quotient graph $H_n$ extends."}],"review_version":1}