CS Paper Radar

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

Sam Blake

cs.IT math.CO ·submitted 2026-11-16 09:50 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.IT math.CO ·2026-11-14 ·Sam Blake
similarity 0.69
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$.

0.50

Quasilinear multiplication in the Cayley-Dickson tower

cs.SC math.RAmath.NA ·2026-09-10 ·Harrison Lemley
code/data similarity 0.56
Abstract · 28 pages, 2 tables. v2: title changed from 'Quasilinear multiplication in the real Cayley--Dickson tower'; results generalized from $\mathbb…

Direct evaluation of the defining product of the Cayley-Dickson algebra $A_n$ of rank $N:=2^n$ over a unital commutative ring $R$ in which $2$ is invertible requires a quadratic number of arithmetic operations. This paper gives a uniform bilinear algorithm for multiplication in this algebra costing $O(N \log N)$ arithmetic operations in $R$ and $O(N)$ auxiliary storage when the doubling parameters of $A_n$ are units whose square roots lie in a fixed commutative coefficient algebra $S$ finitely generated as an $R$-module and admitting an $R$-linear map $π\colon S \to R$ with $π(1) = 1$. In particular, over $\mathbb{R}$ and every finite field $\mathbb{F}_{q}$ of odd characteristic, a quadratic field extension contains a square root of every possible doubling parameter, so the algorithm applies to every Cayley-Dickson tower over these fields, and the tensor rank of multiplication in $A_n$ over them is at most $(9n-21)2^n+28$ when $n\ge2$. When the top doubling parameter is a non-square, as in the standard real tower, the bound is $(9n-15)2^{n-1}+10$. To the author's knowledge, the algorithm presented in this paper is the first uniform subquadratic algorithm for multiplication in $A_n$. When $R=\mathbb{R}$ with every doubling parameter equal to $-1$, the real quasilinear schedule uses fewer total arithmetic operations than both direct multiplication and a uniform algorithm of Cariow-Cariowa for $n\ge4$. An implementation for the standard real tower is available in the MIT-licensed C11 library fastCD, with a NumPy-backed Python interface. In single-core benchmarks against direct multiplication and the uniform Cariow-Cariowa method, the quasilinear implementation had the lowest mean time of the three at every tested dimension $N\ge32$, for both single and batched products, and was over $17$ times faster than direct multiplication at $N=1024$.

0.34

A Memory-Magic Exchange Law in Streaming Clifford+T Compilation

cs.IT quant-phmath.NT ·2026-09-29 ·Jinze Yang, Yangyang Li, Xiu-Hao Deng
code/data similarity 0.52
Abstract · 39 pages, 2 figures. v2: unconditional rate improved from 17/7 to every alpha < 5/2 (Theorem 8, Appendices G-H, exact SMT check). Code, data…

A phase that reaches a fault-tolerant processor in additive pieces can be remembered until the last piece arrives, or executed on arrival: the first option costs classical memory carried across rounds, the second costs magic states committed before the phase is known. We determine the exchange rate $α$, committed $T$ gates per bit of memory forgone, for ancilla-free coordinatewise Clifford+$T$ compilation. The Ramanujan bound gives $α\ge2$ with explicit constants, the square-root barrier of the spectral method. An elementary determinant method, using that quaternion numerators lie on spheres in both real embeddings of $\mathbb{Q}(\sqrt2)$, counts words near any rotation coset below that barrier. With a height dichotomy for the sphere sections it produces and a fibration over rational projections, it gives every $α<5/2$ unconditionally and uniformly over frames, by an exact SMT check of its continuum case analysis; $5/2$ is where this method stops. At Clifford-framed cosets the volume law holds up to subexponential factors: all but a vanishing fraction of $z$-rotations need $T$-count $(3-o(1))\log_2(1/\varepsilon)$, and processes whose committed pieces are near Clifford-framed $z$-rotations, including per-rotation pipelines, have $α\ge3-o(1)$, which a fractional-passthrough family attains under the Ross-Selinger typical-cost hypothesis. Under an equidistribution conjecture supported by exhaustive enumeration to $T$-count 22, $α=3$ in general and memory should be shed in whole rotations. The bounds hold even when the phases cancel to the identity; side information enters through a conditional entropy; probabilistic mixing halves the costs but not the rate. With clean ancillas and a phase-gradient catalyst, table lookups batched over coordinates drive the rate to $O(1/\log\log(1/\varepsilon))$, so the constant-rate law is specific to coordinatewise synthesis.

0.46

Uniform Quantum Average-Case Fine-Grained Hardness of Arithmetized $k$-Orthogonal Vectors

cs.CC ·2026-11-10 ·Dhruv Prasad Deshpande, Abhishek Mishra
similarity 0.52
Abstract · 21 pages

We study exact evaluation of the arithmetized $k$-Orthogonal Vectors polynomial $FOV^k$ of Ball et al. (2017, 2018). For every fixed integer $k \geq 3$, set $d(n) = \left \lceil \log^2 n \right \rceil$. Assuming the basic decision version of Quantum Strong Exponential-Time Hypothesis (QSETH), for every constant $\varepsilon > 0$, no uniform quantum algorithm runs in $O(n^{k/2 - \varepsilon})$ time on every input and evaluates this polynomial correctly with probability at least $3 / 4$ over a uniformly random input in $\mathbb F_{p(n)}^{knd(n)}$ and the algorithm's internal randomness, for all sufficiently large $n$. This holds when $p(n)$ is the smallest prime greater than $n^{k - 1}$ and when it is the smallest prime greater than $n^k$. Our direct reduction combines classical polynomial self-correction with calls to a quantum average-case evaluator. For the smaller prime, random sampling finds an orthogonal tuple with constant probability whenever the count is large enough to wrap around modulo $p(n)$; otherwise, the exact residue determines the answer. For the larger prime, quantum minimum finding and an asymptotic prime-gap bound account for the cost of generating the prescribed field. In view of prior isolation-based reductions permitting small characteristics, we present these results as explicit reductions for the two canonical-prime families, with all setup costs included in the uniform quantum running time. The hardness guarantee concerns single-instance exact evaluation; a matching quantum evaluation algorithm and a quantum proof-of-work protocol remain open.

0.17

Euclidean and Hermitian Self-Orthogonal Codes from Divisible Codes

cs.IT ·2026-11-10 ·Ziling Heng, Chenkun Xie
theory similarity 0.52
Abstract · 26 pages

Self-orthogonality and divisibility are two fundamental properties of linear codes, and the relationship between them has long been of interest. Huffman and Pless (2003) showed that every binary \(4\)-divisible code is Euclidean self-orthogonal, that a ternary code is Euclidean self-orthogonal if and only if it is \(3\)-divisible, and that a quaternary code is Hermitian self-orthogonal if and only if it is \(2\)-divisible. The general case remained open for a long time. In 2024, Li and Heng settled the odd-characteristic case, proving that every \(p\)-divisible code over \(\F_{p^m}\), with \(p\) odd, that contains the all-one vector is Euclidean self-orthogonal. In this paper we treat the even-characteristic case: we prove that every \(4\)-divisible code over \(\F_{2^m}\) containing the all-one vector is Euclidean self-orthogonal. We also prove that, for every prime \(p\), every \(p\)-divisible linear code over \(\F_{q^2}\), where \(q=p^m\), that contains the all-one vector is Hermitian self-orthogonal. In addition, we generalize the Hermitian criterion to the Galois self-orthogonal case, proving that any $p$-divisible linear code over $\gf_{q^r}$ that contains the all-one vector is $\ell$-Galois self-orthogonal for \(\ell\in\{1,\dots,r-1\}\). These criteria make the construction of self-orthogonal codes from divisible codes simple and efficient. As applications, we recover the known Euclidean and Hermitian self-orthogonality of generalized Reed--Muller codes and obtain several infinite families of new Euclidean and Hermitian self-orthogonal codes, which give rise to infinite families of quantum codes with excellent parameters.

0.11

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

Comments on "Multidimensional Costas Arrays and Their Periodicity"

cs.IT math.CO ·2026-10-25 ·Shiv Munagala
similarity 0.51
Abstract · Comment arXiv:2208.02378

Rubio and Torres conjectured that a multidimensional Costas array, defined by a bijection between two boxes of integer points whose domain has at least as many dimensions as its image, can stay Costas in every window of its periodic extension only if its order is a power of two fixed by the dimension of the domain. We give a four-dimensional periodic Costas array of order $6$, with a two-dimensional domain and a two-dimensional image, so the conjecture is false. The verification reduces to $36$ windows. It has been confirmed by computer and in the Lean proof assistant. The array also meets with equality the pigeonhole bound that Rubio and Torres use for their non-existence results, so that bound is tight.

0.27

Eventual Nonnegativity of a Matrix Is in P

cs.LO ·2026-09-20 ·Julian D'Costa
theorycode/data similarity 0.51
Abstract · 19 pages, including appendix. v2: added a reference and minor edits to the exposition. A Lean 4 formalisation of the structural criterion an…

Given a rational matrix $A$, is every sufficiently large power $A^n$ entrywise nonnegative? We prove that this problem is decidable in deterministic polynomial time. This is in contrast with deciding eventual nonnegativity of a single prescribed entry sequence $(A^n)_{ij}$, which amounts to the Ultimate Positivity Problem for linear recurrence sequences, whose decidability is open. The previous decidability procedure (D'Costa, Ouaknine and Worrell, STACS 2024) splits the matrix powers into residue classes modulo a torsion exponent $D$ whose value can be exponential in the input size. We show that it is sufficient to check a single progression $A^{Dk+1}$: the exponents $n$ with $A^n \geq 0$ are closed under addition, and two consecutive exponents of the progression are coprime, so they generate every sufficiently large exponent. Along the progression, eigenvalues are grouped by their common $D$th power, and the required coefficients for each group are computed without forming $A^D$, any $λ^D$, or a splitting field: each summand is evaluated in its own root field $\mathbb{Q}(λ)$, and Galois equivariance keeps the degree and height of every class sum polynomially bounded, enabling certified zero and sign tests. The same algorithm with one case rejected decides eventual positivity, and a variant decides whether the matrix has any nonnegative power at all.

0.40