Source-linked AI summary
A proof of Ward's conjecture on Griesmer codes
Haihua Deng, Weiye Zhang
TL;DR
Ward’s conjecture concerns p-power divisibility in Griesmer codes. The paper proves it using polynomial properties and endpoint shortenings, establishing the conjectured divisibility in full generality.
Problem
The paper addresses Ward’s conjecture on the p-power divisibility of Griesmer codes.
Source: §1 · pp. 1–2Method
The proof develops polynomial identities and a shortened-subcode criterion, then applies endpoint shortening inductively.
Source: §3.2 · p. 6, §3.3 · pp. 7–8, §4 · p. 9Results
Takeaways & Limitations
Griesmer codes are shown to possess good p-power divisibility, alongside other structural codes discussed in the introduction.
Source: §1 · pp. 1–2Theorem 3.5 requires N > (q − 1)p^(t−1); an example shows that equality does not suffice.
Source: §3.3 · p. 8
Abstract
from arXiv · showhide
Let $C$ be an $[n,k,d]_q$ Griesmer code, where $q=p^f$ with $p$ prime, and write $e=\nu_p(d)$. Ward conjectured that $C$ is $p^{\max\{0,e-f+1\}}$-divisible. In this paper, we prove this conjecture.
1. Introduction
The introduction places Ward’s conjecture in the study of p-power divisibility of Griesmer codes and states that the paper proves it in full generality. It also relates the conjecture to earlier prime-field results and to divisibility properties of other structural codes.
1. Introduction
- Griesmer codes are among structural codes noted for good divisibility, meaning their weights are divisible by a large p-power.The introduction also points to generalized Reed–Muller and Abelian codes as examples of structural codes with this property.Source: §1 · p. 1
- Removing repetitions from a Griesmer code preserves the Griesmer property, so the introduction focuses on p-power divisibility.The cited result on divisible codes motivates this reduction.Source: §1 · pp. 1–2
- For prime fields, earlier results establish νp(C) = e, while equality can fail over proper extension fields.These extension-field results led Ward to formulate the conjecture addressed here.Source: §1 · p. 2
- The paper proves Ward’s conjecture in full generality for Griesmer codes.Theorem 1.1 is stated for a [gq(k, d), k, d]q Griesmer code with νp(d) = e.Source: §1 · p. 2
2. Preliminaries
The preliminaries represent linear codes through projective multisets and define endpoints and shortened subcodes. They then collect properties of Griesmer codes used in the proof.
2.1. Linear codes and projective multisets
- A full-length code can be represented by the projective multiset of generator-matrix columns, with projective equivalence corresponding to linear equivalence of codes.The multiset records coordinate forms on the dual space of the code.Source: §2.1 · p. 3
- An endpoint is a projective point of maximum multiplicity in the code’s multiset, and the set of endpoints has size N(C).The maximum multiplicity is denoted γ(C).Source: §2.1 · p. 3
- Shortening at P = ⟨λ⟩ takes the kernel of λ, reducing dimension by one and effective length by MC(P).The resulting subcode is denoted CP.Source: §2.1 · p. 3
2.2. Properties of Griesmer codes
- Shortening a Griesmer code at an endpoint yields a Griesmer code with the same minimum distance and dimension k − 1.Its parameters are [gq(k − 1, d), k − 1, d]q.Source: §2.2 · p. 4
- For a Griesmer code, the number N(C) of endpoints is bounded below by gq(k, η), where 1 ≤ η ≤ qk−1.The parameter η is introduced in Lemma 2.2.Source: §2.2 · p. 4
- If qk−1 divides d, every nonzero codeword in the Griesmer code has weight d.Source: §2.2 · p. 4
3. Polynomial identities and shortened codes
The section develops polynomial identities that detect p-power divisibility, then uses them to give a threshold criterion for recovering divisibility from shortened subcodes. The strict threshold matters: equality alone need not suffice.
3. Polynomial identities and shortened codes
- For an [n, r]_q code with generator matrix A, the construction uses column linear forms in formal variables and polynomial coefficients to capture divisibility.The section uses p-adic valuations and base-p digit sums to establish the identities.Source: §3 · p. 4, §3.1 · p. 4, §3.2 · p. 5
3.2. Polynomials arising from divisible codes
- If D is p^t-divisible, then every coefficient F_j in the polynomial expansion vanishes for 1 ≤ j < p^t.The identities extend the use of the first coefficient to higher coefficients for detecting p-power divisibility.Source: §3 · p. 4, §3.2 · p. 6
3.3. A divisibility criterion using shortened subcodes
- If N distinct shortened subcodes are p^t-divisible and N > (q − 1)p^(t−1), then the original code is p^t-divisible.The argument uses the shortened-code identities to show that each corresponding linear form divides the relevant coefficient polynomial; the degree bound forces that polynomial to vanish.Source: §3.3 · p. 8
- At equality, 6 shortened subcodes of the [6, 3, 4]_4 hexacode are 4-divisible, but the original code is not 4-divisible.Here 6 = (4 − 1)2, illustrating why the criterion requires a strict inequality.Source: §3.3 · p. 8
4. Proof of Theorem 1.1
The proof proceeds by induction on dimension, reducing the remaining case to endpoint-shortened Griesmer subcodes and applying Theorem 3.5. It concludes that C is p^t-divisible for t = e − f + 1.
4. Proof of Theorem 1.1
- For e < f the assertion is trivial, and for k = 1 every nonzero codeword has weight d.The induction is on dimension k, simultaneously for all positive minimum distances d.Source: §4 · p. 8
- When e ≥ f(k − 1), q^(k−1) divides d and Lemma 2.3 applies; otherwise the proof sets t = e − f + 1.Source: §4 · p. 9
- In the remaining range, each endpoint-shortened subcode is a [g_q(k−1, d), k−1, d]_q Griesmer subcode and is p^t-divisible by induction.The proof also establishes p^e | η and η ≥ p^e using Lemma 2.2.Source: §4 · p. 9
- Theorem 3.5 yields that C is p^t-divisible, completing the induction.Source: §4 · p. 9