PaperlayerView exact revision on arXiv

Source-linked AI summary

Nonlinear fixed-distance codes via real lifts of moment configurations

Sergey Yekhanin

arXiv:2610.19960v1cs.ITcs.DMmath.COmath.IT

TL;DR

For larger alphabets, how to achieve low redundancy at fixed distance remains less complete than for binary codes. This paper combines moment checks with a geometrically restricted locator set, obtaining normalized redundancies converging to 1 and 2 at distances four and five. Its distance-four improvement over linear codes requires nonlinear codes.

  • Problem

    For larger alphabets, the fixed-distance redundancy picture is less complete than for binary codes, where extended BCH codes attain the Hamming-bound coefficient.

    Source: §1 · pp. 1–2

  • Method

    The construction uses d−3 moment checks and geometrically restricts locators, using real lifts and a Behrend-style sphere.

    Source: §1.2 · p. 3, §1.3 · p. 4, §7.1 · p. 22

  • Results

    At distances four and five, normalized redundancies converge to 1 and 2, respectively.

    Source: §1 · p. 2

  • Takeaways & Limitations

    At distance four, nonlinear codes are essential to the construction’s improvement over linear codes.

    Source: §1.2 · p. 3

    The finite-shape argument uses k=s−2=d−3 moments; with fewer checks, solution loci can have positive dimension, so bounded-shape polynomial relations no longer follow.

    Source: §7.1 · p. 22

Abstract

from arXiv · show

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.

1 Introduction

For fixed q and distance d≥4, the paper constructs nonlinear codes over arbitrary q-symbol alphabets with leading redundancy coefficient d−3; at distances four and five, this matches the Hamming coefficient. Its construction replaces an additional moment check with a geometric restriction on field locators, while the introduction compares the result with linear-code bounds and prior work.

1 Introduction

  • At distances four and five, normalized redundancies converge to 1 and 2, respectively, matching the Hamming-bound coefficients.The construction’s loss is exp(Oq,d(√log n)) in the number of codewords, so coefficient optimality does not imply an O(1) redundancy overhead.Source: §1 · p. 2

1.1 Why nonlinearity matters at distance four

  • For every prime-power q>2, nonlinear codes attain a leading redundancy coefficient unavailable to any linear family.The introduction attributes the linear-code comparison to the polynomial-method bound for cap sets.Source: §1.1 · p. 2

1.2 Prior work and what is new

  • The construction gives coefficient d−3 for every alphabet and fixed d≥4, improving the prior coefficient by 1/(d−2).At distances four and five, this reaches the Hamming coefficient over every alphabet.Source: §1.2 · p. 3

1.3 Overview of the method

  • The method uses d−3 moment checks and restricts the field locators to a large set that avoids the remaining troublesome configurations.The checks leave a restricted family of configurations, which the locator selection excludes.Source: §1.3 · pp. 3–4
  • Chebotarev-selected primes make dependency ratios reductions of finitely many real algebraic numbers, which the number-field sphere construction lifts to real geometry.Small algebraic-integer coordinates ensure the relevant congruences are equalities before reduction; a prohibited triple would then contradict the fact that a line meets a sphere in at most two points.Source: §1.3 · p. 4
  • The locator set yields n elements in a field of size n exp(Oq,d(√log n)), so the checks and restriction add only Oq,d(√log n) beyond the leading term.The geometric restriction replaces an entire moment check at lower-order cost.Source: §1.3 · p. 4

1.4 Organization

  • The paper proves the distance-four result and linear-code comparison first, develops the moment and sphere machinery next, and closes with limitations and questions.The overview assigns distance five to an elementary argument and the general-distance construction to polynomial relations and Chebotarev’s theorem.Source: §1.3 · pp. 4–5, §1.4 · p. 5

2 Distance four

At distance four, Behrend-style locator sets give nonlinear codes whose redundancy matches the Hamming-bound coefficient up to lower-order terms. Cap-set bounds show that prime-power linear codes with q>2 cannot match that coefficient.

2.1 The construction

  • Behrend sphere locators yield K-weighted-average-free sets, allowing short integer checks to produce distance-four code fibers.The weighted-average-free condition excludes the three-locator relations that could otherwise support a difference between words in one fiber.Source: §2 · p. 5, §2.1 · pp. 6–7
  • Redundancy is log_q n + O_q(√log n) at distance four, matching the Hamming-bound coefficient.The construction uses constant-cost symbol-sum checks and locators from a K-weighted-average-free set.Source: §2.1 · pp. 5–7
  • For q=2, the weighted-average-free condition is vacuous, while the construction's integer-representative map is not an F_q-linear syndrome.The sphere is needed only for larger alphabets.Source: §2.1 · p. 7

2.2 A linear obstruction

  • For prime-power q>2, cap-set bounds force linear distance-four codes to have a redundancy coefficient strictly above one.The linear-code argument interprets parity-check columns as a cap set; the polynomial-method bound has exponent log 3/log θ3 > 1.Source: §2.2 · pp. 7–8

3 Moment checksums and affine-line structure

Moment checksums partition words into fibers, and admissible locator sets make those fibers distance-d codes. The remaining dependencies are constrained to affine lines, but their field-valued ratios still require special treatment.

3 Moment checksums and affine-line structure

  • The checks use a symbol sum and r=d−3 moments; any dependency among locators has at least r+2=d−1 elements.A dependency is a bounded-integer relation reduced modulo p; the Vandermonde argument rules out smaller ones.Source: §3 · pp. 8–9
  • An admissible locator set S with at least n elements yields a q-ary length-n code of minimum distance at least d and size at least q^n/p^(rm+1).The construction partitions words according to checksum values and retains a largest fiber.Source: §3 · p. 8
  • Normalized dependencies have at most r! shapes, each isolated and nonsingular in characteristic zero or characteristic p>max(r,K).In characteristic zero, their coordinates are algebraic numbers.Source: §3 · p. 9
  • For p>(r+2)K and prime m>r!, the Yekhanin–Dumer theorem puts every dependency's locators on x1+(x2−x1)Fp [17].The theorem follows by showing normalized shape coordinates are fixed by the coordinatewise pth-power map.Source: §3 · p. 10
  • The affine-line theorem does not lift arbitrary Fp coefficients to bounded real coefficients; the construction therefore needs real lifts of particular ratios.The ratio singled out is y1=(x3−x1)/(x2−x1).Source: §3 · p. 10

4 A sphere over a number field

The construction uses small algebraic integers and a sphere in a real number field to transfer affine-ratio avoidance into finite fields. A localization datum then turns those locator sets into codes.

4.1 Small algebraic integers

  • If an element reduces to zero and is small under every embedding, its norm is divisible by p but has absolute value below p, forcing the element to be zero.The norm is an integer, and it vanishes only for the zero element.Source: §4.1 · pp. 11–12

4.2 Exact lifting from a box

  • For sufficiently large p, reduction is injective on the box BH and preserves specified affine relations with coefficients from Λ exactly.The lifting condition is p^(1/D)≥4C, with the constants and finite coefficient set fixed.Source: §4.2 · p. 12

4.3 A large level set

  • A quadratic level set in the real number field has no three distinct collinear points, so its reduction avoids the affine ratios in Λ.Exact lifting would turn any forbidden reduced triple into a collinear triple on the level set.Source: §4.3 · p. 13

4.4 From locator sets to codes

  • A localization datum for (q,d) implies Theorem 1.1; for large p, prime m > r!, and every n ≤ |S_{p,m}|, there is a length-n q-ary code of distance at least d and redundancy at most (rm+1) log_q p.Condition (i) is essential; an infinite set of permitted primes with arbitrarily large multiplicative gaps would not suffice.Source: §4.4 · p. 14

5 Distance five

For distance five, two moment checks leave only four-locator dependencies, whose normalized ratios can be controlled using quadratic equations and suitable primes. This yields redundancy 2 log_q n + O_q(√log n) through a direct localization argument.

5 Distance five

  • The symbol sum and first two moments leave only four-locator dependencies, and their normalized ratios are roots of quadratic or linear polynomials.The section uses these quadratic shapes as a template for the general case.Source: §5 · p. 15, §5.1 · p. 15

5.1 The shapes

  • The real roots of the finitely many shape polynomials lie in a multiquadratic field generated using primes at most K.The construction selects a real embedding and an order of algebraic integers for the localization argument.Source: §5.1 · p. 15, §5.2 · pp. 15–16

5.2 The field and the primes

  • Suitable auxiliary primes force each four-locator dependency onto a line with ratio from a finite set of real roots.For primes p > 4K satisfying the stated conditions and odd m, the ratio is the reduction of some λ in Λ.Source: §5.2 · p. 16
  • 2 log_q n + O_q(√log n) is the distance-five redundancy bound, matching the Hamming lower bound up to lower-order terms.The direct localization proof establishes the bound without relying on the alternative Sidon-set estimate attributed to unpublished work.Source: §5.2 · p. 17
  • The alternative k-fold Sidon-set route would give a shorter proof, but its required simultaneous estimate is attributed to unpublished work and is not used here.The authors report a potential difficulty for equations whose four-coefficient product is not a square.Source: §5.2 · p. 17

6 General distance

For general fixed distance, the proof constrains the ratios in troublesome dependencies by polynomial relations, then chooses primes that make finite-field roots lift to real algebraic numbers. A localization datum and the sphere construction exclude those ratios while retaining the redundancy coefficient d −3.

6 General distance

  • The general argument starts with K = q −1 and r = d −3, using the affine-line theorem to reduce dependencies to a finite set of ratios.It remains to show that a normalized coordinate is the reduction of one of finitely many fixed real algebraic numbers.Source: §6 · p. 18

6.1 One polynomial for the first coordinate

  • A one-variable polynomial identity gives each normalized shape coordinate a polynomial relation that survives reduction modulo suitable primes.The proof reduces the identity directly and does not require every finite-field shape to lift to characteristic zero.Source: §6.1 · p. 18

6.2 Choosing primes with real root lifts

  • Chebotarev-selected primes make finite-field roots of the fixed polynomials reductions of real roots, while also providing the required reductions of the order.Lemma 6.2 supplies both properties for the chosen primes.Source: §6.2 · p. 20

6.3 The localization datum

  • The resulting data form a localization datum, separating the roles of affine-line structure, polynomial constraints, real lifting, and the arithmetic sphere.The proof only needs to lift the one coordinate defining a locator triple, not the other shape coordinates.Source: §6.3 · p. 21

6.4 Two calculations at distance six

  • At distance six, the ternary examples show that when 2 is a nonsquare and m is odd, neither of two five-point patterns occurs, so the whole field can serve as locators.This gives coefficient three without a sphere in those examples, but does not improve the known ternary distance-six bounds [17, Section II].Source: §6.4 · p. 22

7 Limitations and questions

The method's boundary is d −3 nonconstant moments: fewer checks can leave positive-dimensional configuration families. The paper asks whether the Hamming coefficient is reachable at every fixed distance and alphabet.

7.1 Why the argument stops at d −3 moments

  • With fewer than d −3 nonconstant moments, configurations may be positive-dimensional, so finiteness no longer supplies the polynomial relations used by the proof.This is a limitation of the method, not a lower bound for unrestricted codes.Source: §7.1 · p. 22

7.2 Questions

  • Open questions include whether every fixed distance and alphabet can reach the Hamming coefficient, and how far nonlinear constructions can separate from linear ones beyond distance four.Pushing real-lifting below d −3 moments would require handling positive-dimensional configurations or another way to constrain short dependencies.Source: §7.2 · p. 22
Loading 2610.19960v1…