Nonlinear fixed-distance codes via real lifts of moment configurations
Abstract
Let Aq(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≥2 and d≥4 we construct codes with redundancy n−logq Aq(n,d)≤(d−3)logq n+O(√(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 logq 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>2 require a strictly larger coefficient in front of logq 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.
Related
- Mark distance correlation functions: from moment-based to distributional mark summary characteristics in spatial point processes
- New distance bounds for one-generator quasi-cyclic codes with applications to Hermitian LCD codes and entanglement-assisted quantum codes
- Evolving Towards Better Codes: LLM-Guided Search for High-Distance Binary Linear Codes
- Cubature-Based Statistical Moment Steering for Nonlinear, Non-Gaussian Trajectory Optimization
- Iterative Bounded Distance Decoding With 2-Bit Reliability Marker For Product-Like Codes
BibTeX
@misc{yekhanin2026nonlinear,
title = {{Nonlinear fixed-distance codes via real lifts of moment configurations}},
author = {Sergey Yekhanin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19960},
eprint = {2610.19960},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19960},
}
RIS
TY - UNPB
TI - Nonlinear fixed-distance codes via real lifts of moment configurations
AU - Sergey Yekhanin
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.19960
UR - https://arxiv.org/abs/2610.19960
AB - 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≥2 and d≥4 we construct codes with redundancy n−log_q A_q(n,d)≤(d−3)log_q n+O(√(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, 𝔽_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.
ER -