REVIEW 4 major objections 4 minor 6 references
An $\mathcal{O}(n)$ Space Construction of Superpermutations
T0 review · 4 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash
Pith's one-line read The paper's central claim is a bead-by-bead generator that outputs a superpermutation in $O(n!)$ time using only $O(n)$ working memory, with the generated word's length equal to $\sum_{k=1}^{n} k!$.
desk verdict A new-looking O(n)-space superpermutation construction whose central coverage claim is unproven, and whose supplied Java code apparently fails for n=4. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the bead: a length-$(2n-1)$ tuple whose $n$ length-$n$ windows are pairwise distinct permutations, together with the mirror-shift operation $\mathrm{MS}_{n-k}$ that rewrites one bead into the next while keeping the maximum allowed overlap. Around beads, the paper builds a hierarchy of $k$-rings, ordered cycles of $(k-1)$-rings, so that the overlap between consecutive structures at level $k$ is known to be exactly $n-k-2$; this predictable overlap is what lets the algorithm print only the new letters and discard the rest, keeping memory to one current bead plus a small buffer. The mirror-shift identities in Theorem 6 express $\mathrm{MS}$ and $\mathrm{MU}$ as compositions of straight-shifts and straight-unshifts, which is what lets the generator move between rings without storing a leading bead.
What would settle it
Run the published program for $n=4$ or $n=5$, record every length-$n$ window of the output, and compare with the $n!$ permutations; a missing permutation disproves the claim. Also check the printed length: $33$ for $n=4$ and $153$ for $n=5$, matching $\sum_{k=1}^n k!$, since a length mismatch would show the overlap counts are wrong even before window inspection.
Extended reading notes
Core claim
On the paper's own terms, the discovery is a parametric family of transitions on beads. Starting from the seed bead $(x_1,\dots,x_n,x_1,\dots,x_{n-1})$, every next bead is obtained by applying mirror-shift $\mathrm{MS}_{n-k}$ at the appropriate index, and Theorem 7 asserts that the second half of the construction is the mirror of the first half, so the whole flattened word is a palindrome. The paper counts $(n-1)!$ beads, $(n-1)!-1$ intersections, and intersection lengths $\ell = n-k-2$ at ring order $k$, and from this derives the closed form $\ell(n) = (2n-1)(n-1)! - \sum_{i=1}^{n-2} i^2 i!$, which simplifies to $\sum_{k=1}^n k!$. The author presents this as a construction claim, not a minimal-length claim: the length match with the old minimal-superpermutation values is called coincidental.
Load-bearing premise
The construction assumes that the beads generated by the straight-shift and mirror-shift steps cover all $(n-1)!$ distinct beads exactly once, without repetition; if a bead is skipped or duplicated, the flattened output is not guaranteed to contain every permutation.
Editorial extensions
If this is right
- If the bead chain covers all $(n-1)!$ beads, a single streaming pass produces a complete superpermutation with no permutation set or earlier-stage sequence held in memory.
- The $O(n)$ space bound removes the factorial-memory bottleneck of recursive methods and avoids the NP-hard Hamiltonian-path search of graph methods, at the same $O(n!)$ output-time scale.
- Because the second half is the mirror of the first half, generation can stop halfway and emit the remainder by reflection, halving the number of shift computations.
- For every $n$, the construction gives a concrete word of length $\sum_{k=1}^n k!$, a number that agrees with the old minimal-conjecture values even though the paper does not claim minimality.
Reading between the lines
- Editorial inference: The whole argument comes down to one coverage question, whether repeated straight-shift and mirror-shift transitions enumerate every distinct bead exactly once; a direct enumeration check for $n=4$ or $5$ would settle it without any further theory.
- Editorial inference: The palindrome property suggests a symmetry shortcut for a correctness proof: verify that every bead in the first half is valid and that mirror-shift preserves validity, and the second half's coverage follows by mirror symmetry; the paper gestures at this but does not formalize it.
- Editorial inference: If coverage is confirmed, the same overlap-counting scheme might transfer to other window-encoding problems, since the length calculation uses only bead counts and pairwise intersection lengths rather than the specific alphabet.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a deterministic, streaming construction of superpermutations using 'beads' and recursively defined 'k-rings'. It defines straight-shift and mirror-shift operations, claims an O(n!) time and O(n) space algorithm, derives the length formula l(n) = (2n-1)(n-1)! - sum_{i=1}^{n-2} i^2 i! = sum_{k=1}^n k!, and provides Java code. The central assertion is that the assembled string W_n contains every n-permutation as a contiguous substring, but no theorem in the manuscript proves that coverage property.
Significance. If the construction were established, the paper would provide a simple streaming generator with O(n) working space, which would be a genuinely useful complement to recursive and graph-theoretic methods. The manuscript also supplies explicit definitions, a hierarchical decomposition, a candidate length formula matching the classical sum-of-factorials upper bound, and a runnable Java program; the explicit distinction in Remark 2 between this length and minimal superpermutation length is appropriate. However, the central coverage claim is never proved, the supporting intersection and tiling arguments contain logical gaps, and the Java code does not implement the paper's own mirror-shift definition. The paper therefore does not establish its main result.
major comments (4)
- [Section 2 and Section 4.1] The paper's central claim, stated in Section 2, is that the algorithm runs in O(n!) time using only O(n) space and constructs a superpermutation. Section 4.1 defines W_n as a concatenation of bead outputs, but no theorem states or proves that every n-permutation appears as a contiguous window of W_n. The proof sections (Theorems 1-9) concern bead counts, ring counts, and intersection lengths; they never show coverage. This is a load-bearing gap: without a coverage theorem, the object produced by the algorithm is not shown to be a superpermutation.
- [Section 5.1 and Theorem 1(ii)] The count of (n-1)! beads in Theorem 1(ii) divides n! by n, which presupposes that the beads generated by the algorithm partition the n! permutations exactly once, with no repetitions and no omissions. That disjoint-tiling property is never proved. The same unproven assumption enters Theorem 9 and the length calculation in Sections 5.1-5.3, so the final formula l(n) = (2n-1)(n-1)! - sum_{i=1}^{n-2} i^2 i! is conditional on the very property the paper needs to establish.
- [Theorem 2(i) and Theorem 1(iii)] The proof of Theorem 2(i) does not validly exclude an overlap of length n-1: comparing a suffix of b1 with a prefix of b2 cannot force x1=x2 unless the letters of b2 are known to carry the same labels as those of b1, and the text does not show that an arbitrary bead with that overlap must coincide with b1. Similarly, Theorem 1(iii) says that two distinct windows force x_m = x_{m-n}; distinctness alone does not imply equality at aligned positions, although the statement can be proved using the fact that each window is a permutation. These invalid arguments underlie the bead representation and the intersection-length hierarchy, so the derivation of intersection counts is not rigorously grounded.
- [Section 4.2] The Java method mirrorShift(int index) does not implement Definition 11. For n=4 and index=3 (k=1), the code transforms the stored bead 1234 to 2314, whereas Definition 11 yields MS_3(1234...) = 3214... . The submitted program is therefore not an implementation of the paper's algorithm, and its behavior cannot be used as evidence for the construction. A trace of the code for n=4 actually produces the standard length-33 superpermutation, so the code appears to implement a different but valid operation.
minor comments (4)
- [Theorem 1(i)] Theorem 1(i) is stated as 'the most space-efficient structure', but the proof only shows length-minimality for a string containing n distinct windows; longer strings can contain more permutations with a lower length-to-permutation ratio (e.g., n=3: 5/3 for a bead versus 9/6 for a superpermutation).
- [Theorem 4(iii)] In the induction hypothesis of Theorem 4(iii), the text says all j-rings with 0 <= j <= k intersect with length n-(k+2), but the length should depend on j as n-(j+2); this appears to be a typo.
- [Notation 5] The composition notation in Notation 5, especially the 'inverted ordering' with an upper and lower bound on the composition symbol, is nonstandard and likely to confuse readers; a concrete worked example would help.
- [Section 5.2 and Theorem 9] The phrase 'intersections of the same length' in Theorem 9 is not defined precisely in terms of the flattened string; the paper should specify how overlapping segments are merged when counting intersections between rings.
Circularity Check
The central length formula is derived from an assumed coverage property: the bead and intersection counts presuppose that the constructed sequence contains every n-permutation exactly once, so the 'derivation' of l(n) reduces to the target claim it is supposed to establish.
-
self definitional
[Section 3.1, Theorem 1(ii)]
"We require (n− 1)! distinct beads in a superpermutation for n. ... Each bead contains n distinct permutations. Since we require n! distinct permutations, the number of beads required is n!/n = (n− 1)!."
The bead count divides the target n! permutations by the n windows per bead. This is valid only if the beads' windows are pairwise disjoint across the whole construction and jointly cover every permutation, which is precisely the property that W_n is a superpermutation. No lemma proves that the flattened sequence produced by Definitions 5, 8, and 11 covers all permutations; Theorem 1 proves only intra-bead distinctness of the n windows. Section 5.1 uses this count as the basis of the length calculation, so (2n−1)(n−1)! is not an independent input count but a restatement of the unproven coverage assumption.
-
self definitional
[Section 5.2, Theorem 9 and Section 5.3]
"Firstly, we recall the nodes and edges argument from Theorem 2(ii). Using the same logic, we take the preliminary count of the number of intersections to be (n−(k+1))!−1."
This intersection recurrence inherits the bead and ring counts that were derived from the assumption that the construction partitions all n! permutations. Combined with Section 5.3, l(n) = (2n−1)(n−1)! − sum i^2·i! is presented as the length of the generated sequence. If the coverage assumption fails, the counts (n−1)! beads and each j·j! intersections are not the actual numbers for W_n, so the length formula reduces to the central claim rather than proving it.
full rationale
The paper's operation-count analysis (Theorem 8) is independent and correct as a count of recursive calls; it does not involve coverage and therefore is not circular. The length formula, however, is circular with respect to the main claim: Theorem 1(ii) obtains (n−1)! beads by dividing the required n! permutations by n windows per bead, without proving that the construction's beads are disjoint and exhaustive. Theorem 9's intersection counts and the final l(n) formula in Section 5.3 inherit that assumption. Thus the announced length 'prediction' is equivalent, by construction, to assuming that W_n is a superpermutation. This is a self-definitional reduction rather than a fitted-parameter or self-citation issue: the paper cites only external work, and no cited uniqueness theorem is doing load-bearing work. The submitted Java implementation also disagrees with the paper's own definitions and fails for n=4; that is a correctness risk, not itself circularity, but it underscores that the coverage claim has not been established independently of the length arithmetic. Score 6 reflects that the central derivation reduces to its target assumption, while the underlying idea might still be salvageable with a genuine coverage proof.
Assumptions & free parameters
assumptions (4)
- ad hoc to paper The bead set generated by the algorithm partitions the n! permutations exactly once.
- domain assumption Overlapping segments can be merged in the flattened representation without losing any contained permutation.
- domain assumption Printing a string of length m costs O(m) time and can be treated as streaming output.
- ad hoc to paper The straight-shift and mirror-shift functions map beads to beads.
invented entities (3)
-
bead (0-ring)
-
k-ring
-
straight-shift SS and mirror-shift MS operations
Cite this review
Pith. "Pith review of An $\mathcal{O}(n)$ Space Construction of Superpermutations." pith.science (2026). https://pith.science/paper/TBMGFHJU
@misc{pith2026250509628,
author = {Pith},
title = {Pith review of: An $\mathcalO(n)$ Space Construction of Superpermutations},
year = {2026},
howpublished = {\url{https://pith.science/paper/TBMGFHJU}},
note = {Machine review of arXiv:2505.09628}
}
abstract
A superpermutation is a sequence that contains every permutation of $n$ distinct symbols as a contiguous substring. For instance, a valid example for three symbols is a sequence that contains all six permutations. This paper introduces a new algorithm that constructs such sequences more efficiently than existing recursive and graph-theoretic methods. Unlike traditional techniques that suffer from scalability and factorial memory demands, the proposed approach builds superpermutations directly and compactly. This improves memory usage, enabling the construction of larger sequences previously considered impractical.
Reference graph
Works this paper leans on
-
[1]
: Tackling the Minimal Superpermutation Problem (2014)
botherref Houston , R. : Tackling the Minimal Superpermutation Problem (2014). https://arxiv.org/abs/1408.5108 botherref
arXiv 2014
-
[2]
: Non-uniqueness of minimal superpermutations
barticle Johnston , N. : Non-uniqueness of minimal superpermutations . Discrete Mathematics 313 ( 14 ), 1553 -- 1557 ( 2013 ) 10.1016/j.disc.2013.03.024 barticle
-
[3]
botherref Poster , A. , Houston , R. , Pantone , J. , Vatter , V. : A lower bound on the length of the shortest superpattern (2018). https://oeis.org/A180632/a180632.pdf botherref
work page 2018
-
[4]
: Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by Sigma and Tau (2017)
botherref Williams , A. : Hamiltonicity of the Cayley Digraph on the Symmetric Group Generated by Sigma and Tau (2017). https://arxiv.org/abs/1307.2549 botherref
arXiv 2017
-
[5]
: Linear Algebra Done Right (2024)
botherref Axler , S. : Linear Algebra Done Right (2024). https://linear.axler.net/LADR4e.pdf botherref
work page 2024
-
[6]
write newline
" write newline "" before.all 'output.state := FUNCTION string.to.integer 't := t text.length 'k := #1 'char.num := t char.num #1 substring 's := s is.num s "." = or char.num k = not and char.num #1 + 'char.num := while char.num #1 - 'char.num := t #1 char.num substring FUNCTION find.integer 't := #0 'int := int not t empty not and t #1 #1 substring 's :=...
Reviewed August 16, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.