Pith. sign in

REVIEW 3 major objections 4 minor 9 references

Superpermutation matrices

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that the shortest word hitting every permutation class under cyclic increments lies between two explicit bounds whose ratio tends to 2.

desk verdict New matrix analogue of superpermutations with mostly sound bounds, but the asymptotic proof has a repairable gap and one off-by-one typo. read the letter →

arxiv 1908.04708 v1 pith:5H5ECS42 submitted 2019-08-13 math.CO

Guillaume Dumas This is my paper · ORCID
classification math.CO MSC 05A0505C4568R15
keywords superpermutationmatricesuniversalwordssymmetricgroupquotientscyclicincrementstransitiongraph1-cyclesHamiltonianpathstotient-functionbounds
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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$.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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$.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [Section 3.2, proof of Theorem 7] 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.
  2. [Section 3.1, Theorem 6] 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.
  3. [Proposition 7 and proof of Theorem 5] 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.
minor comments (4)
  1. [Section 2.3, definition of H_n] When H_n is introduced for Problem 2, its vertices are described as equivalence classes for R1; they should be equivalence classes for R2.
  2. [Proofs of Lemma 5 and Lemma 6] 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.
  3. [Proposition 10 and Theorem 7] 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)'.
  4. [Figure 4] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the bounds and asymptotic ratio are derived from independent structural facts about the transition graph.

full rationale

The derivation is self-contained. The lower bound is obtained from an induction on path weights (Theorem 6) with p(C)=(n-1)! and c(C)=sum_d |cycles(1)(d)|; the upper bound is an explicit Hamiltonian-path construction over 1-cycles (Theorem 5), and the asymptotic ratio is derived by bounding an auxiliary sum with elementary estimates (Theorem 7, Lemma 7, Theorem 8). No parameter is fitted to the quantity being predicted, and no central claim is imported from the author's prior work; the only external citations are background on ordinary superpermutations and universal cycles. The paper itself flags the one unproved monotonicity conjecture (“Unfortunately, I could not prove this result”), which is a limitation of the method, not a circular step. The edge-weight bound in Proposition 7 is asserted without proof but is a structural fact about H_n — any two distinct R2-classes admit representatives with at least one matching boundary symbol — and it is not a restatement of m(n). The reviewer's concern that a displayed inequality in Theorem 7 is numerically false is a correctness gap in a proof step, not a circular reduction; even if the proof were not repairable as written, the theorem is not assumed from its conclusion. Hence no circular step is present.

Assumptions & free parameters 0 free parameters · 2 assumptions · 2 invented entities

The paper introduces new definitions but no free parameters or fitted constants. The load-bearing premises are the faithful representation of S_n by permutation matrices and the unproved n-1 upper bound on edge weights. The invented entities are mathematical definitions, for which independent empirical evidence is not applicable.

assumptions (2)
  • standard math Permutation matrices provide a faithful representation of S_n (Proposition 2).
    Used throughout to turn permutation words into 0-1 matrix blocks and back; standard linear algebra.
  • domain assumption Every edge weight in the transition graph H_n lies between 1 and n-1 (Proposition 7).
    Stated as a bullet without proof; the upper bound B(n) in Theorem 5 relies on the worst-case cost n-1 to jump between 1-cycles.
invented entities (2)
  • Superpermutation matrix (toric 0-1 matrix containing S_n as blocks)
    purpose: Matrix analogue of a superpermutation word; the row/column minimization problems m1(n), m2(n), m3(n).
    New mathematical definition; no external falsifiable handle, but none is needed for a definition. Its usefulness is internal and demonstrated by the proven bounds.
  • Equivalence relation R2 (cyclic increment of row labels) and the universal word problem m(n)
    purpose: Reduces the matrix problem to a word problem over (n-1)! quotient classes.
    Defined by the paper in Section 2.2, Definition 4 and Problem 4; the reduction is proved, not empirically supported.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Superpermutation matrices." pith.science (2026). https://pith.science/paper/5H5ECS42

@misc{pith2026190804708,
  author       = {Pith},
  title        = {Pith review of: Superpermutation matrices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5H5ECS42}},
  note         = {Machine review of arXiv:1908.04708}
}
abstract

Superpermutations are words over a finite alphabet containing every permutation as a factor. Finding the minimal length of a superpermutation is still an open problem. In this article, we introduce superpermutations matrices. We establish a link between the minimal size of such a matrix and the minimal length of a universal word for the quotient of the symmetric group $S_n$ by an equivalence relation. We will then give non-trivial bounds on the minimal length of such a word and prove that the limit of their ratio when $n$ approaches infinity is 2.

Figures

Figures reproduced from arXiv: 1908.04708 by the authors.

Figure 1
Figure 1. Blocks in the 3×4 matrix corresponding to the six permutations of S3. 2.2 Definitions and equivalences between the problems We start by formally stating the problems we are going to focus on. Problem 1. Find the smallest integer m1(n)such that ∃T ∈ Mm1(n),n({0, 1}) with Sn ⊂ T Problem 2. Find the smallest integer m2(n)such that ∃T ∈ Mn,m2(n)({0, 1}) with Sn ⊂ T Remark 1. In a m × p matrix, there are mp distinct bloc… view at source ↗
Figure 2
Figure 2. A path going through every vertex in H4. It corresponds to the superpermu￾tation matrix with 12 columns given in Section 2.3. The universal word correspond￾ing to this path will be 123421342143. We are now going to look for better bounds. We define a 1-cycle as a cycle in Hn using only weight-1 edges. We note cycles(1)(k) = {C | C is a 1-cycle going through k vertices} and D(n) = {k ∈ N|k|n}. Lemma 3. Let d be an in… view at source ↗
Figure 3
Figure 3. 1-cycles in H4. We have one 1-cycle of length 4 and two 1-cycles of length 1. We are going to determine |cycles(1)(d)| for d ∈ D(n). Let us begin with d=1. Below, arithmetic is done modulo n. Lemma 4. For all n, the number of 1-cycles of length 1 is given by |cycles(1)(1)| = |{π|∃k,∀i,π(i +1) = π(i)+k and π(1) = 1}| ≤ n −1 Proof. cycles(1)(1) = {inc(π) ∈ Sn| 6 ∃y,w(inc(π), y) = 1} = {inc(π)|inc(π) = inc(πσ)} = {inc(… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Table of the values of the bounds for n ≤ 8. ”Best found“ is the minimal size found numerically for m(n). It is optimal at least for n ≤ 4. We saw in Proposition 7 that the ratio between trivial upper and lower bounds was equivalent to n. In order to show that we impro…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

  1. [1]

    Houston, J

    Anonymous 4chan user, R. Houston, J. Pantone, and V . Vatter. A lower bound on the length of the shortest superpattern.https://oeis.org/A180632/a180632. pdf, 2018

    work page 2018

  2. [2]

    D. A. Ashlock and J. Tillotson. Construction of small superpermutations and min- imal injective superstrings. Congressus Numerentium, 93:91–98, 1993

    work page 1993

  3. [3]

    Chung, P

    F . Chung, P . Diaconis, and R. Graham. Universal cycles for combinatorial prob- lems. Discrete Mathematics, 110:43–59, 1992

    work page 1992

  4. [4]

    N. G. De Bruijn. A combinatorial problem. Proceedings of the Section of Sci- ences of the Koninklijke Nederlandse Akademie van Wetenschappen te Amster- dam, 49:758–764, 1946

    work page 1946

  5. [5]

    G. Egan. Superpermutations. http://www.gregegan.net/SCIENCE/ Superpermutations/Superpermutations.html, 2018

    work page 2018

  6. [6]

    Containing all permutations

    M. Engen and V . Vatter. Containing all permutations. arXiv e-prints , page arXiv:1810.08252, Oct 2018

    work page Pith review arXiv 2018

  7. [7]

    R. Houston. Tackling the Minimal Superpermutation Problem. arXiv e-prints, page arXiv:1408.5108, Aug 2014

    work page Pith review arXiv 2014

  8. [8]

    J. R. Johnson. Universal cycles for permutations. arXiv e-prints , page arXiv:0710.5611, Oct 2007

    work page Pith review arXiv 2007

Show all 9 references
  1. [9]

    Williams

    A. Williams. Hamiltonicity of the Cayley Digraph on the Symmetric Group Gen- erated by sigma = (1 2 ... n) and tau = (1 2). arXiv e-prints, page arXiv:1307.2549, Jul 2013. 18

    2013 arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.