CS Paper Radar

A Recursive Construction of Perfect and Odd Perfect Sequences of Unbounded Length over the Unit Quaternions

Sam Blake

cs.IT math.CO ·submitted 2026-11-14 21:23 UTC · v1

Abstract

We give a recursive construction, with closed-form index functions, of perfect and odd perfect periodic autocorrelation sequences over the eight simple unit quaternions $\Qe=\{\pm1,\pm i,\pm j,\pm k\}$ in every length $2^n$. The sequences are built, as in the recursive perfect array construction of Blake, from \emph{twisted periodic extensions}: a short sequence continued with period $M$ up to a right factor $u\in\Qe$. Over roots of unity the twists cannot be regenerated by a one-dimensional recursion, consistently with Mow's conjecture; over $\Qe$ we show that no single sequence of length $M\not\equiv0\pmod 4$ carries a twist $\pm i,\pm j$ or $\pm k$ either, but that \emph{pairs} of sequences whose $i$- and $(-i)$-twisted autocorrelations are complementary do. These $i$-pairs behave exactly like Golay pairs: they double under interleaving with a right factor $j$ in place of a sign, every Golay pair of length $n$ gives an $i$-pair of length $2n$, and they exist in length $6$ where no Golay pair exists. An $i$-pair of length $M$ interleaves to an odd perfect sequence of length $4M$, and a perfect and an odd perfect sequence of length $M$ interleave to a perfect sequence of length $4M$ with the array orthogonality property for the divisor $2$. The $i$-pairs of length $2^t$ are $x^{(t)}_{r,a}=j^{w_t(r,a)}$, where $w_t(r,a)$ counts the changes in the bit string formed by $r$ and the binary digits of $a$, and the odd perfect sequence of length $2^{t+2}$ is $y^{(t)}_{2a+r}=j^{w_t(r,\,a\bmod 2^t)}\, i^{(1-2r)\lfloor a/2^t\rfloor}$. The construction also gives odd perfect sequences over $\Qe$ in every length $24\cdot2^s$ and perfect sequences in every length $6\cdot4^s$.

Closest papers

Nearest neighbours by meaning across the whole index.

A Recursive Construction of Perfect Arrays of Every Shape $2^{a_1}\times\cdots\times2^{a_d}$ over the Unit Quaternions

cs.IT math.CO ·2026-11-16 ·Sam Blake
theory similarity 0.69
Abstract

We extend the recursive construction of perfect and odd perfect sequences over the simple unit quaternions $\Qe=\{\pm1,\pm i,\pm j,\pm k\}$ of Blake to arrays of any dimension. The three operations of that construction act on one direction of an array at a time, and are valid whenever the array is periodic in the remaining directions. Starting from a perfect array $P$ of shape $M_2\times\cdots\times M_d$ they give perfect arrays of shape $2^a\times M_2\times\cdots\times M_d$ for every $a\ge0$, with explicit index functions and with the array orthogonality property for the divisor $2$ in the lifted direction; from $a=5$ on these arrays are, in general, Kronecker products of a sequence with $P$ in neither order. Applied direction by direction, the construction gives perfect arrays over $\Qe$ in every shape $2^{a_1}\times\cdots\times2^{a_d}$, and in every shape $2^{a_1}\times\cdots\times2^{a_{d-1}}\times N$ for which a perfect sequence of length $N$ over $\Qe$ exists. The contrast with the binary alphabet is sharp: a perfect binary array of shape $2^{a_1}\times\cdots\times2^{a_d}$ exists only when $\sum a_k$ is even and $\max a_k\le\frac12\sum a_k+1$, by a theorem of Jedwab and Kraemer on Menon difference sets in abelian $2$-groups, whereas over $\Qe$ there is no constraint on the shape. We also show that, unlike the one-dimensional case, single arrays carrying a non-central twist do exist in two dimensions, and determine where the one-dimensional non-existence argument breaks.

0.26

A Quaternary Legendre Pair of Length 64

cs.DM math.CO ·2026-09-22 ·Harshit Verma
unusual similarity 0.57
Abstract

A quaternary Legendre pair of length $\ell$ is a pair of sequences over $\{\pm 1, \pm \mathrm{i}\}$ whose periodic autocorrelations sum to $-2$ at every nonzero shift. We give a quaternary Legendre pair of length $64$. To the best of our knowledge, this is the first reported construction at this length.

0.28

Reduced APN permutations and a disproof of the Galois-ring lifting conjecture

cs.IT math.NT ·2026-08-31 ·Daniele Bartoli, Pantelimon Stanica
similarity 0.55
Abstract

We construct infinite families of reduced almost perfect nonlinear (APN) permutations of $\mathbb{F}_{2^m}$ that admit coefficientwise permutation lifts to $\mathrm{GR}(2^k,m)$ for every $k>1$. These families disprove Conjecture~2 of Rønjom and Sandrib (Cryptogr. Commun., 2026), even for reduced polynomial representatives. For every odd $m\ge5$ with $3\nmid m$, we obtain explicit seven-term polynomials over $\mathbb{F}_2$ with formal derivative identically one. We derive them from a complete criterion for the reduced representative of $A(x)^{2^s+1}$ to have no critical point in $\mathbb{F}_{2^m}$, where $A$ is an invertible linearized polynomial and $\gcd(s,m)=1$. We then apply the cube case to construct a second family of degree $2^{m-1}+2$, whose nonconstant derivatives avoid zero by an explicit trace identity. A fixed parameter in $\mathbb{F}_{32}$ gives this family in every dimension $m=5r$ with $r$ odd, including a degree-$18$ example over $\mathbb{F}_{32}$. Both constructions remain in Gold linear equivalence classes, so liftability of reduced representatives is not invariant under invertible $\mathbb{F}_2$-linear input changes. We obtain the lifting conclusions from the standard Galois-ring permutation criterion. We also verify a degree-$24$ example supplied by Zhang and Haobo, prove a trace-adjoint criterion for reduced quadratic functions, and interpret the derivative condition through ramification at rational points.

0.44

Some results on Archdeacon's conjecture for rotation systems

cs.CG math.CO ·2026-09-10 ·Arahat Chikkatur, Ji Zeng
theory similarity 0.53
Abstract

A rotation system on $n$ elements assigns to each element a cyclic order of the other $n-1$ elements. A four-element subset is non-planar if its induced rotation system cannot be realized by a crossing-free drawing of $K_4$. As a combinatorial strengthening of Hill's conjecture on the crossing number of the complete graph, Archdeacon conjectured that every rotation system on $n$ elements has at least $H(n)=\frac{1}{4} \lfloor\frac {n}{2}\rfloor \lfloor\frac{n-1}{2}\rfloor \lfloor\frac{n-2}{2}\rfloor \lfloor\frac{n-3}{2}\rfloor$ non-planar four-element subsets. We computationally verify Archdeacon's conjecture for $n\leq 10$ and show that every extremal rotation system in these orders is realizable by a simple drawing. With computer assistance, we prove that every rotation system on $n$ elements has at least $(8/9 - o(1)) H(n)$ non-planar four-element subsets. We also present a proof by hand for a weaker lower bound of $(2/3-o(1)) H(n)$. Finally, extending recent work of Felsner on antipodal pairs in drawings, we show that Archdeacon's conjecture holds for antipodally shellable rotation systems.

0.39

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

Three Quadratic Recurrences Modulo 3: What We Can Prove and What We Can Guess

cs.DM math.NTmath.CO ·2026-10-25 ·Steven Finch
similarity 0.52
Abstract · 10 pages

We study three innocent-looking recurrences modulo $3$, each built from squares of two earlier terms. One of them turns out to be secretly $\textit{linear}$, and we can compute its periods exactly. One is a $\textit{permutation}$ hiding a small, perfectly orderly piece inside a large, random-looking one. The third looks thoroughly random, but it still has a few provable features. Along the way we meet open problems that need nothing beyond a first course in abstract algebra to state. This paper is a starting point, not the final word in any sense.

0.31

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

cs.DM math.CO ·2026-09-23 ·Tim Gerlach, Elizabeth Hartung, Pia Herkenrath, Joe Sawada, Aaron Williams
similarity 0.52
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.

0.23

Rotating-Memory Fibonacci Numbers and Periodic Tilings

cs.DM math.CO ·2026-09-11 ·Walid Abdelaidoum, El-Mehdi Mehiri, Hacène Belbachir
similarity 0.51
Abstract

We introduce and study the rotating-memory Fibonacci numbers, a periodic variable-order analogue of the Fibonacci sequence in which the number of preceding terms used in the recurrence changes cyclically with the index. Despite this varying memory, the resulting sequences exhibit a remarkably rigid structure. We derive closed forms, rational generating functions, arithmetic properties, and exact growth behavior, and show that the sequence decomposes naturally into geometric subsequences. We also develop combinatorial interpretations in terms of periodically constrained tilings, and restricted compositions, including bijective explanations for the multiplicative structure of the sequence. In addition, the first two nonclassical periods admit natural geometry-driven realizations: the period-2 sequence arises from monomer--dimer tilings of a triangular chain, while the period-3 sequence is related to tilings of a double hexagon strip by single and double hexagons. These connections provide geometric interpretations of the rotating recurrence in which the periodic behavior is induced by the underlying structures themselves, and suggest a broader problem of constructing analogous models for higher periods.

0.25