Divisibility of Griesmer Codes
Haihua Deng Hexiang Huang Qing Xiang · 2025
Read Divisibility of Griesmer Codes by Haihua Deng Hexiang Huang Qing Xiang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-07846.txt.
Introduction
Haihua Deng, Hexiang Huang, and Qing Xiang study the weights of special codes in a 2025 math paper. Griesmer codes are error-correcting codes that meet a known length bound exactly. A past result by Ward showed a clean split rule: if a prime power divides the smallest weight, it divides every weight in the code. That proof covered only prime-sized symbol sets.
The authors extend the rule to symbol sets of prime power size. First they build a basis of the code with strong traits. The first few basis words span a smaller Griesmer code of one fixed weight. Using that basis with both algebra and geometry, they prove the split rule for all weights. A sharper divisor comes out of the geometric side of the proof.
Catalog record
| CREATOR | Haihua Deng Hexiang Huang Qing Xiang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-07846
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Divisibility of Griesmer Codes Haihua Deng Hexiang Huang Qing Xiang Abstract In this paper, we consider Griesmer codes, namely those linear codes meeting the Griesmer bound. Let C C be an [ n , k , d ] q [n,k,d]_{q} Griesmer code with q = p f q=p^{f} , where p p is a prime and f ≥ 1 f\geq 1 is an integer. In 1998, Ward proved that for q = p q=p , if p e | d p^{e}|d , then p e | wt ( c ) p^{e}|\mathrm{wt}(c) for all c ∈ C c\in C . In this paper, we show that if q e | d q^{e}|d , then C C has a basis consisting of k k codewords such that the first min { e + 1 , k } \min\left\{e+1,k\right\} of them span a Griesmer subcode with constant weight d d and any k − 1 k-1 of them span a [ g q ( k − 1 , d ) , k − 1 , d ] q [g_{q}(k-1,d),k-1,d]_{q} Griesmer subcode. Using the p p -adic algebraic method together with this basis, we prove that if q e | d q^{e}|d , then p e | wt ( c ) p^{e}|\mathrm{wt}(c) for all c ∈ C c\in C . Based on this fact, using the geometric approach with the aforementioned basis, we show that if p e | d p^{e}|d , then Δ | wt ( c ) \Delta|{\rm wt}(c) for all c ∈ C c\in C , where Δ = ⌈ p e − ( f − 1 ) ( q − 2 ) ⌉ \Delta=\left\lceil p^{e-(f-1)(q-2)}\right\rceil . MSC 2020. 11T71; 11A07, 94B05, 94B65 Keywords. Griesmer code, Divisible code, Algebraic method, Geometric approach. 1 Introduction The notion of divisible codes was first introduced by Ward [ 18 ] in 1981. Divisible codes are linear codes whose codeword weights share a common divisor larger than one. A linear code C is called \Delta -divisible if the weights \mathrm{wt}(c) of all codewords c\in C are divisible by some positive integer \Delta . In such a case, we call \Delta a \mathit{divisor} of C . There is an extensive survey on divisible codes by Kurz [ 10 ] (We will use some results from [ 10 ] later). In [ 18 ] , Ward proved a fundamental theorem regarding divisible codes, which states that any \Delta -divisible code C over \mathbb{F}_{q} with \gcd(\Delta,q)=1 is equivalent to a \Delta -fold repetition of some code C^{\prime} , supplemented by sufficiently many 0 coordinates. Therefore, p -power divisible codes over \mathbb{F}_{q} will be of particular interest, where p is the characteristic of \mathbb{F}_{q} (we will write q=p^{f} throughout this paper). Many structural codes such as simplex codes, cyclic codes, and generalized Reed-Muller codes exhibit good divisibility , meaning that all weights are divisible by a “large” p -power; see [ 1 , 19 , 21 ] . Griesmer codes, as a special class of length-optimal codes including the aforementioned simplex codes, also seem to exhibit good divisibility. We first recall the Griesmer bound. Let C be an [n,k,d]_{q} code. In 1960, Griesmer [ 7 ] proved that for binary linear codes (i.e., q=2 ), we have n\geq\sum_{i=0}^{k-1}\left\lceil\frac{d}{2^{i}}\right\rceil . Later, in 1965, Solomon and Stiffler [ 13 ] generalized this result, leading to the following theorem. Theorem 1.1 (The Griesmer Bound [ 7 , 13 ] ) . Let C be an [n,k,d]_{q} code. Then n\geq\sum_{i=0}^{k-1}\left\lceil\frac{d}{q^{i}}\right\rceil. The bound in Theorem 1.1 will be called the Griesmer bound and the quantity on the right-hand side of the above inequality will be denoted by g_{q}(k,d) ; that is, g_{q}(k,d):=\sum\limits_{i=0}^{k-1}\left\lceil\frac{d}{q^{i}}\right\rceil . Any [n,k,d]_{q} code C with code length meeting the Griesmer bound will be called a Griesmer code . Besides the simplex codes, there are many other examples of Griesmer codes, such as maximum distance separable (MDS) linear codes, the 1^{\text{st}} order Reed-Muller codes and Belov codes (see [ 2 , 6 ] ). We shall present two examples of Griesmer codes arising from finite geometry as follows. Example 1.2 . A unital in \mathrm{PG}(2,q^{2}) is a set \mathcal{U} of q^{3}+1 points such that every line meets \mathcal{U} in 1 or q+1 points. Let G be a 3\times(q^{3}+1) matrix with columns g_{1},g_{2},\ldots,g_{q^{3}+1} such that \mathcal{U}:=\{\left\langle g_{1}\right\rangle,\left\langle g_{2}\right\rangle,\ldots,\left\langle g_{q^{3}+1}\right\rangle\} is a unital in \mathrm{PG}(2,q^{2}) . Then the linear code C with G as a generator matrix is a [q^{3}+1,3,q^{3}-q]_{q^{2}} Griesmer code. Note that C is actually a two-weight code with nonzero weights q^{3}-q and q^{3} . Example 1.3 . An ovoid in \mathrm{PG}(3,q) is a set \mathcal{O} of q^{2}+1 points such that no three of them are collinear and every hyperplane meets \mathcal{O} in 1 or q+1 points. Let G be a 4\times(q^{2}+1) matrix with columns g_{1},g_{2},\ldots,g_{q^{2}+1} such that \mathcal{O}:=\{\left\langle g_{1}\right\rangle,\left\langle g_{2}\right\rangle,\ldots,\left\langle g_{q^{2}+1}\right\rangle\} is an ovoid in \mathrm{PG}(3,q) . Then the linear code C with G as a generator matrix is a [q^{2}+1,4,q^{2}-q]_{q} Griesmer code. Note that C is in fact a two-weight code with nonzero weights q^{2}-q and q^{2} . Let C be a [g_{q}(k,d),k,d]_{q} Griesmer code. In 1984, Dodunekov and Manev [ 5 ] first showed that in the case when q=2 , if 2^{e}|d , then 2^{e}|\mathrm{wt}(c) for all c\in C . In 1998, Ward proved the following divisibility result on Griesmer codes. Theorem 1.4 (Theorem 1 in [ 20 ] ) . Let C be a [g_{p}(k,d),k,d]_{p} Griesmer code where p is a prime. If p^{e}|d , then p^{e}|\mathrm{wt}(c) for all c\in C . The above theorem shows that Griesmer codes over the prime field \mathbb{F}_{p} have a good divisibility property. However, when the field size is q=p^{f} (f>1) , in general, we cannot hope for a divisibility result as good as in the case when q=p ; that is, if C is a [g_{q}(k,d),k,d]_{q} Griesmer code and q^{e}|d , q^{e} may not divide \mathrm{wt}(c) for all c\in C . For example, the hexacode H (see [ 4 ] for definition) is a [6,3,4]_{4} code containing 45 codewords of weight 4, 18 codewords of weight 6 and the zero codeword. The divisor of H is 2 but not 4 although 4|d=4 . Despite this obstruction, Ward proved further divisibility results on Griesmer codes. Theorem 1.5 ( [ 21 ] ) . Let C be a [g_{q}(k,d),k,d]_{q} Griesmer code. 1. If q|d , then C is p -divisible. 2. In the case when q=4 , if 2^{e}|d , then 2^{e-1} is a divisor of C . Ward then proposed the following conjecture. Conjecture 1.6 (Conjecture 10 in [ 21 ] ) . Let C be a [g_{q}(k,d),k,d]_{q} Griesmer code where q=p^{f} . Suppose that p^{e}|d and p^{e}\geq q . Then p^{e+1}/q is a divisor of C . In Section 5 , we will prove Theorem 1.7 using the p -adic algebraic method, extending Theorem 1 of [ 20 ] and Proposition 13 of [ 21 ] . In Section 6 , we will prove Theorem 1.8 from the geometric point of view. Theorem 1.7 . Let C be a [g_{q}(k,d),k,d]_{q} Griesmer code where q=p^{f} . If q^{e}|d , then p^{e}|\mathrm{wt}(c) for all c\in C . Theorem 1.8 . Let C be a [g_{q}(k,d),k,d]_{q} Griesmer