Frobenius orbit codes and finite-field Fourier spectra: exact distance and coset distributions

Abstract

Let $q$ be a prime power, let $m\ge 1$, put $Q=q^m$, and let a permutation $\pi$ of a finite index set $I$ satisfy ${\pi }^m=1$. We study the $\F q$-linear code \[ \mathcal C(π)=\{x\in\Lfield^I:x_{π(i)}=x_i^q\}, \] which includes the Fourier spectra of $\K$-valued functions on finite abelian groups split by $\Lfield$. Our structural starting point is a $\F q$-linear Hamming isometry taking each cycle of $\pi$ of length $\ell$ to the subfield repetition code $\{(b,\ldots,b):b\in\F{q^\ell}\}$. From this normal form we obtain exact symbol weight and received-word distance enumerators, all list sizes, and the covering radius. An occupancy generating function gives the complete coset-leader distribution, the exact mean distance, the probability of a unique nearest word, and the number of deep holes. For the full cyclic family of length $q^m-1$, the deficit of a uniformly random ambient word from the covering radius is asymptotically Poisson with mean $(m-1)/2$, with an additional $1$ when $m$ is even; a central limit theorem follows. We also determine the deep-hole probability and the second-order gap to the sphere-covering bound. Classical Fourier--Galois descent and cyclotomic orbit enumeration enter only to identify the Fourier specialization.

13 pages. Substantially revised and refocused version: new title, new structural normal form, exact distance and coset-leader distributions, list-size formulas, covering and deep-hole results, and new probabilistic asymptotics. The exposition and bibliography have been reorganized