Linear codes meeting Griesmer bound must follow divisibility rules
A Hyperplane Bound and Ward's Divisibility Conjecture
Information Theory
Summary
The paper addresses a mathematical question about special error-correcting codes called linear codes. The authors prove that when these codes are as efficient as possible (meeting the Griesmer bound), they also follow a certain divisibility pattern related to prime numbers, which was previously conjectured by Ward. Their proof uses a mix of geometry and algebra to understand how these codes behave. This result confirms a long-standing belief about the structure of these codes.
What this means in practice
- •For error correcting code designers: Ensure constructed codes meet known divisibility constraints improving reliability checks for optimal codes.
- •For cryptography engineers: Use divisibility properties of codes meeting the Griesmer bound to analyze and design secure coding schemes.
A theory result. No direct application yet.
Authors
Guanghui Zhang
Abstract
Let $q=p^f$, where $p$ is prime. We prove that every $q$-ary linear code meeting the Griesmer bound, with positive dimension and minimum distance $d\ge1$, is $p^{\max\{0,ν_p(d)-f+1\}}$-divisible, as asserted in Ward's conjecture. Arbitrary projective column multiplicities are allowed. The geometric ingredient is a bound independent of dimension: a nonzero scalar-invariant function $F:\mathbb{F}_q^k\to\mathbb{F}_p$, with $F(0)=0$ and prime-field algebraic degree at most $(f+s)(p-1)$, vanishes identically on at most $p^s(q-1)$ linear hyperplanes when $0\le s<f$. A truncated digit-sum inequality forces selected coefficient polynomials to be homogeneous of ordinary degree less than $q$. Weighted moments on a projective line then bound their linear factors, while a second-moment argument handles the complementary support configuration. An elementary finite-difference calculation supplies the degree bound for divided weight residues. Endpoint shortenings prove the basic divisibility layers; endpoint lifting, a surjective linear functional, and residual-code induction extend the argument to every valuation. We include the proofs of the classical ingredients, identify their sources, and distinguish the present argument from an earlier reported unpublished proof.