{"id":"bcac169d-8ffe-4014-90ac-0618f2f217e5","arxiv_id":"2505.09628","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proposes an O(n)-space streaming construction of superpermutations but supplies no proof that its output contains every permutation.","lead":"This paper presents a bead-and-ring algorithm that claims to stream superpermutations, strings containing every ordering of n symbols, using only O(n) memory. The construction's correctness, the proof that every permutation appears, is never given, so the central claim rests on an unproven assumption.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No proof that every permutation is covered, and the supplied Java implementation fails for n=4: its output misses 1243, 1432, 2143, and 3241.","rationale":"The reader's weakest assumption was that the construction covers all n! permutations exactly once without proof. My trace confirms and sharpens that concern: the paper's own Java implementation fails coverage already at n=4, missing four permutations and producing a string longer than the paper's own length formula. This is load-bearing because the central claim is precisely that the algorithm constructs a superpermutation; if the submitted implementation does not, the claim as stated is false. The mathematical construction may be repairable, since a direct implementation of Definitions 5 and 11 for n=4 appears to produce a valid length-33 superpermutation, and the paper's length formula matches known superpermutation lengths. But the absence of a correctness proof for the general construction remains, and the presented artifact contradicts the central claim. The reader's REJECT verdict is therefore supported; no verdict change is needed.","tokens_in":17288,"tokens_out":21946,"duration_ms":209985,"concrete_test":"Execute the Section 4.2 Java program with n=4 and compare the set of length-4 substrings with all 24 permutations. My trace predicts the output 123412341423142431241342134241324243214, whose windows omit 1243, 1432, 2143, and 3241; if reproduced, the submitted algorithm is not a superpermutation construction. To separate an implementation typo from the mathematical construction, also recompute n=4 directly from Definitions 5 and 11: that version should have length 33 and contain all 24 permutations, which would isolate the failure to the code and the missing proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim in Section 2 requires the generated string to contain every n-permutation as a window. No theorem in the paper proves this coverage property. Theorem 1(ii) counts (n-1)! beads only under the assumption that each bead contributes n distinct, unrepeated permutations, and Theorem 9 counts intersections under the same assumption; neither shows that every permutation appears in the flattened W_n. Moreover, the operational Java implementation in Section 4.2 does not implement the paper's own operations. startBead prints the n stored letters twice, giving 2n characters instead of the 2n-1 of a bead, and mirrorShift(d) applies a left rotation (e.g., 1234 -> 2314 when d=3) rather than Definition 11's MS_{n-k}, which for d=3 gives 3214. Tracing the supplied code for n=4 yields length 39, not the 33 predicted by Section 5.3, and its 36 length-4 windows contain only 20 distinct permutations: 1243, 1432, 2143, and 3241 are absent. I am not claiming the underlying mathematical idea is false: a faithful implementation of Definitions 5 and 11 appears to give the standard length-33 superpermutation for n=4. But the paper does not prove coverage in general, and the submitted implementation fails even this small case.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17623,"tokens_out":17401,"duration_ms":165336,"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":[{"comment":"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":"Section 2 and Section 4.1"},{"comment":"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.","section":"Section 5.1 and Theorem 1(ii)"},{"comment":"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":"Theorem 2(i) and Theorem 1(iii)"},{"comment":"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.","section":"Section 4.2"}],"minor_comments":[{"comment":"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).","section":"Theorem 1(i)"},{"comment":"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.","section":"Theorem 4(iii)"},{"comment":"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":"Notation 5"},{"comment":"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.","section":"Section 5.2 and Theorem 9"}],"recommendation":"reject","confidential_remarks":"The main reason for rejection is not the code's output quality; my trace of the submitted Java code for n=4 gives a valid length-33 superpermutation, contrary to the claim that it omits 1243, 1432, 2143, and 3241. The reject recommendation rests on the absence of any proof that the mathematical construction covers all permutations and on the mismatch between the code and Definition 11. If the authors supply a rigorous coverage proof and align the implementation with the definitions, a resubmission could be considered."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dhruv's paper has a genuinely new framework for generating superpermutations incrementally in what is claimed to be O(n) working space, but as written it does not prove that the generated string is a superpermutation. The length and complexity analyses hang on an unproven coverage property, and the operational Java implementation appears not to match the paper's own definitions.\n\nWhat is actually new: the bead-ring-mirror-shift machinery. I haven't seen it in Houston, Johnston, Poster et al., or Williams, and the streaming O(n)-space claim is a distinct contribution if it can be made to work. The paper is also clear about notation and does not oversell the length: Remark 2 explicitly notes that matching sum k! is not a claim of optimality. The citation pattern is clean, with the relevant prior work cited.\n\nWhere the paper does well: the hierarchical ring structure is elaborate, and the operation-count recurrence in Theorem 8 is a clean combinatorial derivation. The definitions of beads, shifts, and intersections are mostly precise, and the flattened-sequence convention is workable.\n\nThe soft spots are serious. Nowhere does the paper state, let alone prove, a theorem that W_n contains all n! permutations as windows. Theorem 1(ii) counts (n-1)! beads by dividing n! by n, which assumes each bead contributes n distinct permutations with no repetition across beads. Theorem 9 counts j·j! intersections of length j under the same assumption. That coverage property is exactly what the paper needs to establish, so the length formula is conditional on the central claim. The proof of Theorem 1(iii) is also invalid as written: distinctness of the relevant windows does not by itself imply x_m = x_{m-n}, even though the statement happens to be true. And the stress-test trace of the Java code in Section 4.2 finds that for n=4 the program outputs length 39 rather than the predicted 33 and misses four permutations. I did not run the code myself, but it clearly does not implement Definition 11's mirror-shift as written, so this is a concrete red flag about the relationship between the math and the code.\n\nI want to be fair: the underlying idea may be salvageable. For n=4, a faithful implementation of the definitions seems to give the standard length-33 superpermutation, so the construction is not obviously false. But the paper needs a real proof of coverage and a corrected, verified implementation before the claims can be accepted.\n\nWho should read it: anyone interested in superpermutation constructions and in how easy it is for an elegant combinatorial scheme to hide an unproven covering assumption. It deserves a serious referee—the idea is new and sharp enough to warrant the time—but the referee should treat it as a construction in need of proof, not as a solved result.","headline":"A new-looking O(n)-space superpermutation construction whose central coverage claim is unproven, and whose supplied Java code apparently fails for n=4.","tokens_in":18085,"tokens_out":4749,"would_cite":false,"duration_ms":46253,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68R15","05A05","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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!$.","keywords":["superpermutation","permutation","algorithm","space complexity","mirror-shift","beads","combinatorial generation"],"falsifier":"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.","tokens_in":17109,"feed_emoji":"🔗","tokens_out":8407,"duration_ms":84354,"temperature":0.7,"pith_summary":"The paper's aim is a memory-lean way to build superpermutations: instead of first constructing all smaller cases or solving a Hamiltonian path over permutation nodes, it generates one bead after another and prints each bead as it goes. A bead is a string of length $2n-1$ whose $n$ overlapping windows are $n$ distinct permutations, and the author argues that beads can be chained by a straight-shift or mirror-shift operation with maximal overlap, organized into nested cycles called $k$-rings. The central claim is that this deterministic chain visits all $(n-1)!$ beads exactly once, so the flattened output is a superpermutation, produced in $O(n!)$ time with only $O(n)$ working space. If correct, this would make generation of larger $n$ practical where factorial-memory recursive or graph-theoretic methods are not, and would give an explicit word of length $\\sum_{k=1}^n k!$ for every $n$.","feed_headline":"Superpermutations stream from one bead using O(n) memory","feed_subtitle":"A mirror-shift chain reuses overlap so only a single bead is stored, not all n! permutations.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the minimal superpermutation problem and supplies the recursive and graph-theoretic baselines used in the time and space comparison.","marker":"[1]"},{"why":"Provides the insertion-style recursive construction whose cumulative subcase storage the paper contrasts with its own streaming method.","marker":"[2]"},{"why":"Supplies the lower-bound context for shortest superpatterns, used when the paper notes that its length formula is not a minimality claim.","marker":"[3]"},{"why":"Models permutation overlap as a Hamiltonian-path problem in a Cayley digraph, the graph-theoretic baseline with factorial-space cost.","marker":"[4]"}],"fun_headline_variants":["Superpermutations from a single bead using O(n) space","Mirror-shift bead chain yields all permutations in O(n)","Palindromic bead stream constructs superpermutations compactly","O(n) memory: superpermutations without factorial storage"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Superpermutations from a single bead using O(n) space","Mirror-shift bead chain yields all permutations in O(n)","Palindromic bead stream constructs superpermutations compactly","O(n) memory: superpermutations without factorial storage"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000221,"raw_usage":{"total_tokens":1393,"prompt_tokens":830,"completion_tokens":563,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":446,"completion_tokens_details":{"reasoning_tokens":494}},"tokens_in":446,"tokens_out":563,"duration_ms":5674,"temperature":1.0,"reasoning_tokens":494,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:12:56.465196+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":": Non-uniqueness of minimal superpermutations","cited_arxiv_id":null,"evidence_quote":"Provides the insertion-style recursive construction whose cumulative subcase storage the paper contrasts with its own streaming method."},{"cited_title":", Houston , R","cited_arxiv_id":null,"evidence_quote":"Supplies the lower-bound context for shortest superpatterns, used when the paper notes that its length formula is not a minimality claim."}],"review_version":1}