Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper constructs non-linear codes with fixed minimum Hamming distance $d \ge 4$ over $q$-ary alphabets, achieving a redundancy of $(d-3)\log_q n + O(\sqrt{\log n})$ for large $n$. This construction significantly improves upon existing bounds, particularly for $d=4$ and $d=5$, where the coefficient of $\log_q n$ matches the Hamming bound and surpasses the best known linear codes. The method leverages "real lifts" of moment configurations and moment checksums over an auxiliary finite field, excluding dependencies via a specially structured subset of the field derived from Behrend's sphere construction.
Non-linear codes achieve near-optimal redundancy for fixed distance $d \ge 4$, outperforming all linear codes at $d=4$.
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\ge2$ and $d\ge4$ we construct codes with redundancy $n-\log_q A_q(n,d)\le(d-3)\log_q n+O(\sqrt{\log n})$ 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, $\mathbb{F}_q$-linear codes with $q>2$ 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.