CS Paper Radar

Shorthand Universal Tori for Permutations: Existence, Symmetry, and Generation of Twori

Tim Gerlach, Elizabeth Hartung, Pia Herkenrath, Joe Sawada, Aaron Williams

cs.DM math.CO ·submitted 2026-09-23 09:01 UTC · v1

Abstract

A de Bruijn sequence packs all $n$-bit binary words into a cycle of length $2^n$. A de Bruijn torus is the two-dimensional analogue in which each word appears exactly once in a rectangular window. Here we consider the natural analogue for permutations using their shorthand representation (i.e., each permutation's final redundant value is omitted from the window). We show that these tori exist when $n = 2m + 1$ is odd and the torus and windows have two rows (i.e., the torus is a "tworus"). These twori can be constructed with a high degree of symmetry. More specifically, there are twori that can be partitioned into $2^{m-1}$ matching blocks where each block contains the same sequence of unordered columns. Furthermore, given one such block we can generate each successive column of a tworus in amortized $\mathcal{O}(1)$-time. We also prove non-existence results for certain sizes of tori and provide algorithms for constructing multiversal cycles (perfect necklaces) of unlabeled binary words.

Closest papers

Nearest neighbours by meaning across the whole index.

Heap-type permutation generation with a prescribed final arrangement

cs.DM math.COcs.DS ·2026-11-17 ·Luís M. S. Russo
theory similarity 0.68
Abstract · 22 pages. Software archived at https://doi.org/10.5281/zenodo.24311260

Heap's algorithm generates all permutations of an array of n items, obtaining each one from its predecessor by a single swap. We determine the net permutation applied to the array by every complete recursive call: a transposition when the number of items is odd and at least three, and a cycle through all items when it is even. We show that the output of each call is a concatenation of right cosets of the symmetric group on one item fewer, and we prove a general formula: the order in which the items are parked at the last position may be chosen freely, every such order corresponds to exactly one valid schedule, and it determines the net permutation of the call. Two variants follow. In the cyclic variant a complete sweep over an even number of items rotates the array by one position. In the extremal variant, for even n, a sweep started from the identity ends in the lexicographically largest arrangement that any single-swap enumeration can leave; by a parity argument this is the reversal exactly when n is congruent to 2 modulo 4. The construction of the extremal variant is proved correct when n is divisible by 4 and verified by computer for all even n up to 10000.

0.41

Protected tails and polynomial-time enumeration of permutations avoiding a direct sum of an increasing pattern and 231

cs.DM math.COcs.DScs.LO ·2026-09-14 ·Henning Arnór Skeggi Úlfarsson
code/data similarity 0.64
Abstract · 36 pages, 4 figures, 1 table. v2: revised and shortened exposition, corrected account of prior work, the first 151 terms tabulated, a proved…

We give an algorithm counting the permutations that avoid a fixed pattern of the following form: the direct sum of an increasing pattern and 231. The first members of the family are 1342 and 12453. For each member the algorithm uses polynomially many operations and stored integers, with degrees that grow linearly in the length of the pattern. It comes from a recurrence that reads a permutation from left to right and records the constraints that the letters read so far impose on those still unread. This recurrence has exponentially many states, but part of each state is protected: later steps carry it along unchanged and do not depend on it, and factoring the protected part out leaves a dynamic program of polynomial size. For 12453 a translation symmetry sharpens the bounds to degree seven for the operations and degree four for the storage. We also compute the number of 12453-avoiding permutations of every length up to 150. The previously published series, due to Biers-Ariel (2019), reached length 38. We also give a sampler of uniformly random avoiders. A floating-point implementation of it, proved to be within total variation distance $3.5\cdot10^{-5}$ of uniform for ideal random bits, draws the one million 12453-avoiding permutations of length 300 shown in a heatmap. The literal and kernel recurrences for 1342 and 12453 are verified in the Lean 4 proof assistant.

0.32

Unranking $S$-avoiding permutations with two forbidden offsets

cs.DM math.CO ·2026-10-09 ·Antônio Augusto André
similarity 0.63
Abstract · 6 pages

Given a finite family of combinatorial objects with a total order, ranking asks for the position of a given object, and unranking asks for the object occupying a given position. Both provide algorithmic access to families too large to enumerate. Kagey gave a polynomial-time algorithm for several position-restricted families and left open the case of $\{-1,1\}$-avoiding permutations. We show that when $|S| = 2$, the graph of forbidden squares is $2$-regular, a disjoint union of cycles, and that fixing a prefix leaves only paths and untouched cycles. This yields polynomial-time prefix counting, ranking and unranking for every two-element set of offsets, covering $\{-1,1\}$. The same structure gives a short proof that the number of $\{-1,1\}$-avoiding permutations equals the $n$-th ménage number for odd $n$ and exceeds it by $2$ for even $n$, proving a conjecture recorded in the OEIS entry A354152.

0.20

A proof of Lehmer's permutation conjecture for neighbor-swap graphs

cs.DM math.COcs.LO ·2026-10-01 ·Tom Verhoeff
theory similarity 0.63
Abstract · 29 pages, 3 figures

In 1965, D. H. Lehmer conjectured that the permutations of every multiset admit an imperfect Hamiltonian traversal by adjacent swaps: a walk in the neighbor-swap graph that visits every word, with some words visited twice in order to reach a neighbor and return. The question is posed as an unsolved research problem in Knuth's Art of Computer Programming. Verhoeff (2017) chose the stutter words, in which every domino is a double, as the words to be reached this way, and reformulated the conjecture as the Hamiltonicity of the graph $N(S)$ on the non-stutter words, with two exceptional families --- binary signatures with an odd multiplicity, and the permutations of $(2k,1,1)$ --- that admit a Hamiltonian path but no cycle. This article proves the reformulated conjecture, and with it Lehmer's conjecture. The key structure is a partition of the words into hypercubes: the swaps inside dominoes turn each class of words with the same domino contents into a hypercube, and the stutters are exactly the $0$-dimensional classes. When every multiplicity is even, Hamiltonian cycles of the hypercubes are glued along a spanning tree, with no finite check. The case of exactly one odd multiplicity reduces to the all-even case and to a theorem of Stachowiak (1992), the one inherited Hamiltonicity input, which also settles two or more odd multiplicities. The only finite ingredients are two explicit cycles, of 28 and 84 words. Every construction is implemented in Python and checked against brute-force graphs, and the proof is formalized in Lean 4 over Mathlib.

0.31

Shift-Invariant Permutations with Polynomial Composition: Construction and Algebraic Structure

cs.IT ·2026-09-25 ·Cheng Lyu, Dabin Zheng, Mu Yuan, Lei Hu
theory similarity 0.62
Abstract

Shift-invariant permutations of $\mathbb F_2^n$ are particularly attractive in symmetric cryptography because of their regularity and implementation efficiency. Constructing such permutations with an explicit algebraic structure remains a challenging problem. In this paper, we study a family of shift-invariant transformations of $\mathbb F_2^n$ constructed from a recursively defined sequence of mappings $\{γ_j\}_{j\ge 0}$ associated with landscapes. First, we prove that, under an explicit dimension condition relating $n$ to the support of the landscape, the sequence $\{γ_j\}_{j\ge 0}$ has the polynomial composition property if and only if the corresponding landscape is quasi-conserved on $\mathbb F_2^n$ with a nonzero special index. Then, we determine the eventual zero or periodic behavior of $\{γ_j\}_{j\ge0}$, including the exact index at which the sequence either first vanishes or becomes periodic, together with the least eventual period, and establish linear independence until the first linear relation occurs. When the polynomial composition property holds, we establish an explicit isomorphism between the group of permutation elements in the monoid generated by these mappings and the unit group of a quotient ring $\mathbb F_2[z]/\langle p(z)\rangle$, where $p(z)$ is a monomial or a binomial determined by the landscape. This framework reduces the tasks of testing bijectivity, computing iterates, and determining compositional inverses and orders of permutation elements to polynomial computations. Finally, we apply the results to mappings represented by binomials and trinomials in the quotient ring, obtaining explicit criteria and formulas, and tabulate more than one hundred representative constructions of shift-invariant permutations, recovering and unifying several previously studied families.

0.07

Block-exchange descent for insertion: commuting projections and minimum masks

cs.FL math.CO ·2026-10-29 ·Haobo Ma, Wenlin Zhang, Charles E. Hughes
theorycode/data similarity 0.59
Abstract · 22 pages, 10 tables. Software and verification data: https://github.com/the-omega-institute/insertion-degree-descent/releases/tag/v1.0

For fixed nonempty words $u,v$, the minimum insertion degree of a shuffle is the least number of inserted-source runs among its representations. We prove that, after a block exchange from a minimum mask of degree $r$, the minimum over masks with commuting source projections is exactly $r-1$; a larger decrease occurs precisely when a noncommuting mask has fewer runs. If either source is unary, every such exchange is exact. We prove an explicit repair for an infinite periodic degree-three family. Computer-assisted results establish first-mask descent through combined length seventeen over every alphabet, degree-three first-mask descent through length thirty, and a uniform repair of all degree-three failures through length thirty, including all further letter identifications. Counterexamples to arbitrary, first, and last minimum-mask choices explain the need for alternative masks. Finally, we prove that minimum iteration depths have no gaps for arbitrary languages. General block-exchange descent and Singleton No-Gap remain open.

0.50

Repetition Avoidance in Curling-Number Transforms

cs.DM math.COcs.FL ·2026-08-16 ·Geoffrey Caveney, Haoxuan, Dong, Jeffrey Shallit
similarity 0.59
Abstract

We study repetition avoidance in a word ${\bf w}$ and its curling-number transform $C({\bf w})$. For alphabets of sizes $2$, $3$, and $4$, we use Thue-Morse-based morphic constructions and exhaustive finite searches. A ternary word for which both ${\bf w}$ and $C({\bf w})$ are overlap-free has length at most $84$, whereas over four letters an infinite example exists. Hence $4$ is the smallest alphabet size admitting simultaneous infinite overlap-freeness. The infinite constructions are verified in Walnut; the finite maxima are obtained by exhaustive breadth-first search and checked independently.

0.04

Shuffle squares in smooth binary words and the Kolakoski sequence

cs.FL math.CO ·2026-10-01 ·Kory Kilpatrick
similarity 0.58
Abstract · Includes an exact finite certificate and standalone Python verifier. Research, computation, and writing performed by GPT-5.6 Sol and GPT-6-A…

A binary word is a shuffle square if its positions can be partitioned into two identical subsequences. A finite word over $\{1,2\}$ is smooth if repeated finite run-length differentiation remains binary until the empty word is reached. This paper proves that every smooth binary word in which both letters have even multiplicity is a shuffle square once its length is at least $18$. There are exactly $34$ exceptions, all of length at most $16$. The infinite part of the proof is a parity-return atom induction: a smooth even-Parikh word factors uniquely into smooth parity atoms, and every such atom has length at most $8$. A finite, independently checkable certificate handles lengths $18$ through $40$. As a consequence, a nonempty prefix of the classical Kolakoski sequence is a shuffle square if and only if both symbols occur an even number of times and its length is not $4$ or $8$. There are infinitely many such prefixes. In fact, the entire infinite Kolakoski sequence can be partitioned into two identical infinite subsequences with monochromatic blocks of uniformly bounded length.

0.54