A Recursive Construction of Perfect Kn× Kn Arrays over K Roots of Unity
Abstract
We give a uniform, explicit and elementary recursive construction of two-dimensional arrays with perfect (ideal) periodic autocorrelation over a \emph{fixed} alphabet of K roots of unity and \emph{unbounded} size: for every integer K≥2 and every n≥1 a perfect Kn× Kn array whose entries are K-th roots of unity, given by a nested sum of floor terms. The construction works with \emph{twisted} (quasi-perfect) arrays indexed by a type v∈ZK2, of which ordinary perfect arrays are the type v=0 members. For K=2 the types are Jedwab's generalised perfect binary arrays and the recursion specialises to the doubling constructions of Jedwab--Mitchell and Wild; for prime K the arrays are the relative difference sets whose existence in abelian p-groups was settled by Ma and Schmidt; and the bare existence of perfect Kn× Kn arrays over K roots of unity follows, for every K, from recent constructions of group-invariant Butson Hadamard matrices. The contribution of this note is therefore not existence but the calculus: types with arbitrary entries in ZK2; three spectral lemmas (a twisted periodic extension of a type-v array has a flat spectrum supported on one coset of KZ2; interleaving arrays whose spectra are flat on disjoint cosets gives a perfect array; and a shear of the index plane with a floor-function carry permutes types through the action of SL2(ZK) on ZK2, whose orbits are the classes gcd(v1,v2,K)=g); a one-directional lift that produces every type at side KM from every type at side M for arbitrary K; and the resulting closed index function, which is the recursive form of the floor-function arrays of \cite{Blake2017}.
Related
- Colored Khovanov homology theories at prime roots of unity
- Gelfand--Tsetlin bases for representations of Uq(gln) at roots of unity
- Zeros and Roots of Unity for Characters of Solvable Groups
- PGL2 webs at roots of unity
- Small sums of roots of unity: polylogarithmic exceptional sets and conditional separation
BibTeX
@misc{blake2026recursive,
title = {{A Recursive Construction of Perfect $K^n\times K^n$ Arrays over $K$ Roots of Unity}},
author = {Sam Blake},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.24408},
eprint = {2610.24408},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.24408},
}
RIS
TY - UNPB
TI - A Recursive Construction of Perfect K^n× K^n Arrays over K Roots of Unity
AU - Sam Blake
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2610.24408
UR - https://arxiv.org/abs/2610.24408
AB - We give a uniform, explicit and elementary recursive construction of two-dimensional arrays with perfect (ideal) periodic autocorrelation over a \emph{fixed} alphabet of K roots of unity and \emph{unbounded} size: for every integer K≥2 and every n≥1 a perfect K^n× K^n array whose entries are K-th roots of unity, given by a nested sum of floor terms. The construction works with \emph{twisted} (quasi-perfect) arrays indexed by a type v∈Z_K^2, of which ordinary perfect arrays are the type v=0 members. For K=2 the types are Jedwab's generalised perfect binary arrays and the recursion specialises to the doubling constructions of Jedwab--Mitchell and Wild; for prime K the arrays are the relative difference sets whose existence in abelian p-groups was settled by Ma and Schmidt; and the bare existence of perfect K^n× K^n arrays over K roots of unity follows, for every K, from recent constructions of group-invariant Butson Hadamard matrices. The contribution of this note is therefore not existence but the calculus: types with arbitrary entries in Z_K^2; three spectral lemmas (a twisted periodic extension of a type-v array has a flat spectrum supported on one coset of KZ^2; interleaving arrays whose spectra are flat on disjoint cosets gives a perfect array; and a shear of the index plane with a floor-function carry permutes types through the action of SL_2(Z_K) on Z_K^2, whose orbits are the classes gcd(v_1,v_2,K)=g); a one-directional lift that produces every type at side KM from every type at side M for arbitrary K; and the resulting closed index function, which is the recursive form of the floor-function arrays of \cite{Blake2017}.
ER -