Nonlinear fixed-distance codes via real lifts of moment configurations

Let $A_q(n,d)$ denote the largest size of a code of length $n$ and minimum Hamming distance $d$ over an alphabet of $q$ symbols. For fixed $q\ge 2$ and $d\ge 4$ we construct codes with redundancy
$n–{log}_q{A}_q(n,d)\le (d–3){log}_{q}n+O(\sqrt{logn})$ for all large $n$.
No algebraic structure is imposed on the alphabet, and the codes are not linear. For $d=4$ and $d=5$ the coefficient of ${log}_{q}n$ matches the Hamming bound, so the redundancy is determined up to lower-order terms. At distance four the codes are provably better than every linear code: by the polynomial-method bound for cap sets, ${𝔽}_q$-linear codes with $q\ge 3$ require a strictly larger coefficient in front of ${log}_{q}n$.

The construction imposes moment checksums over an auxiliary finite field, as BCH codes do, but one fewer than the distance would normally require. The affine-line theorem from prior work describes the dependencies left by these checks. We exclude them by placing the code positions inside a specially structured subset of the field, built from Behrend’s sphere construction with the help of algebraic number theory.