Minimal Linear Codes Violating the Ashikhmin-Barg Condition from Arbitrary Projective Linear Codes
Hao Chen, Yaqi Chen, Conghui Xie, Huimin Lao · 2025
Read Minimal Linear Codes Violating the Ashikhmin-Barg Condition from Arbitrary Projective Linear Codes by Hao Chen, Yaqi Chen, Conghui Xie, Huimin Lao (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-2505-07130.txt.
Introduction
Hao Chen, Yaqi Chen, Conghui Xie, and Huimin Lao wrote a mathematics paper in two thousand twenty-five on a class of error-correcting codes. The codes are called minimal linear codes. Some of them break a classic rule known as the Ashikhmin-Barg condition, and building such codes has drawn much recent work.
The authors give a general way to turn a code that obeys the rule into one that breaks it. They also show how to start from almost any projective linear code and reach the same end. From that method they build many new families of codes. They work out the weight patterns of the new codes as well.
Catalog record
| CREATOR | Hao Chen, Yaqi Chen, Conghui Xie, Huimin Lao |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-07130
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Minimal Linear Codes Violating the Ashikhmin-Barg Condition from Arbitrary Projective Linear Codes Hao Chen, Yaqi Chen, Conghui Xie, Huimin Lao Abstract In recent years, there have been many constructions of minimal linear codes violating the Ashikhmin-Barg condition from Boolean functions, linear codes with few nonzero weights, posets, and partial difference sets. In this paper, we first give a general method to transform a minimal code satisfying the Ashikhmin-Barg condition to a minimal code violating the Ashikhmin-Barg condition. Then we give a construction of a minimal code satisfying the Ashikhmin-Barg condition from an arbitrary projective linear code. Hence an arbitrary projective linear code can be transformed to a minimal codes violating the Ashikhmin-Barg condition. Then we give infinitely many families of minimal codes violating the Ashikhamin-Barg condition. Weight distributions of constructed minimal codes violating the Ashikhmin-Barg condition in this paper are determined. Many minimal linear codes violating the Ashikhmin-Barg condition with their minimum weights equal to or close to the optimal or the best known minimum weights of linear codes are constructed in this paper. Moreover, many infinite families of self-orthogonal binary minimal codes violating the Ashikhmin-Barg condition are also given. Index terms: Minimal linear code. Ashikhmin-Barg condition. Weight distribution. 1 Introduction 1.1 Preliminaries The Hamming weight wt({\bf a}) of a vector {\bf a}=(a_{0},\ldots,a_{n-1})\in{\bf F}_{q}^{n} is the cardinality of its support, supp({\bf a})=\{i:a_{i}\neq 0\}. The Hamming distance d({\bf a},{\bf b}) between two vectors {\bf a} and {\bf b} is d({\bf a},{\bf b})=wt({\bf a}-{\bf b}) . Then {\bf F}_{q}^{n} is a finite Hamming metric space. The minimum (Hamming) distance of a code {\bf C}\subset{\bf F}_{q}^{n} is, d({\bf C})=\min_{{\bf a}\neq{\bf b}}\{d({\bf a},{\bf b}),{\bf a}\in{\bf C},{\bf b}\in{\bf C}\}. One of the main goals of coding theory is to construct codes {\bf C}\subset{\bf F}_{q}^{n} with large cardinalities and minimum distances. In general, there are some upper bounds on cardinalities or minimum distances of codes. Optimal codes attaining these bounds are particularly interesting, see [ 30 ] . The Singleton bound for general codes asserts M\leq q^{n-d+1} and codes attaining this bound is called (nonlinear) maximal distance separable (MDS) codes. Reed-Solomon codes are well-known linear MDS codes, see [ 30 ] . For a linear code {\bf C}\subset{\bf F}_{q}^{n} , we denote A_{i}({\bf C}) the number of codewords with the weight i , 0\leq i\leq n . In this paper, we call a linear [n,k,d]_{q} code optimal, if there is no linear [n,k,d+1]_{q} code. A linear [n,k,d]_{q} code is called almost optimal, if there is no linear [n,k,d+2]_{q} code and there exists a linear [n,k,d+1]_{q} code. Minimal codewords were first introduced in [ 22 ] for decoding linear block codes. Then minimal binary linear codes were studied in [ 11 ] in the name linear interesting codes. In [ 3 ] , minimal codes and minimal codewords were introduced for general q -ary linear codes and studied systematically. A nonzero codeword {\bf c} of a linear [n,k,d]_{q} code {\bf C} is called minimal, if for any codeword {\bf c}^{\prime} satisfying supp({\bf c}^{\prime})\subseteq supp({\bf c}) , then there is a nonzero \lambda\in{\bf F}_{q} , such that, {\bf c}^{\prime}=\lambda{\bf c} . A linear code {\bf C} is called minimal if each nonzero codeword is minimal. The Griesmer bound for a linear [n,k,d]_{q} code in [ 17 ] asserts n\geq\Sigma_{i=0}^{k-1}\lceil\frac{d}{q^{i}}\rceil, or see [ 23 , Theorem 2.7.4, page 81] . Set g_{q}(k,d)=\Sigma_{i=0}^{k-1}\lceil\frac{d}{q^{i}}\rceil , for a linear [n,k,d]_{q} code, the Griesmer defect is g({\bf C})=n-g_{q}(k,d) . A linear [n,k,d]_{q} code attaining is called a Griesmer code, see [ 37 , 21 ] . It is clear that small Griesmer defect codes are more interesting, see [ 37 , 21 ] . 1.2 Related works In [ 3 ] , the Ashikhmin-Barg criterion \frac{w_{min}}{w_{max}}>\frac{q-1}{q} was proposed as a sufficient condition for a q -ary linear code to be minimal, where w_{min} and w_{max} are minimum and maximum weights of the code. However, this is certainly not a necessary condition for the minimality of linear codes. In [ 7 ] the first family of minimal binary linear codes violating the Ashikhmin-Barg criterion was constructed. Then several families of minimal binary linear codes violating the Ashikhmin-Barg criterion were constructed in [ 15 ] from binary linear codes with few nonzero weights. From then many minimal binary codes violating the Ashikhmin-Barg criterion or with optimal lengthes were constructed from finite geometries, Boolean functions, trace representations, posets, or partial difference sets, see [ 15 , 19 , 5 , 4 , 28 , 8 , 39 , 42 , 38 , 31 , 33 , 32 , 44 , 40 , 26 , 34 , 35 , 2 , 45 ] and references therein. In particular, in [ 24 , 25 ] some optimal minimal codes violating the Ashikhmin-Barg conditions were constructed. We refer to [ 1 ] for combinatorial properties of minimal linear codes. In the following table, we list minimal linear codes violating the Ashikhmin-Barg conditions constructed in these previous papers. Only very few of these minimal codes are close to optimal codes or best known codes in [ 16 ] . Table 1: Known minimal q -ary linear codes violating the Ashikhmin-Barg condition [n,k] Minimal distance Condition Method Reference [3^{m}-1,m+1]_{3} \sum_{j=1}^{k}2^{j}\binom{m}{j} 2\leq k\leq\left\lfloor\frac{m-1}{2}\right\rfloor Boolean functions [ 19 ] [2^{m}-1,m+1]_{2} s(2^{t}-1) m=2t,s\leq 2^{t-2} Boolean functions [ 15 ] 2^{m-1}-2^{m-s-1}(s-1) s=\frac{m+1}{2} \sum_{j=1}^{k}\binom{m}{j} 2\leq k\leq\left\lfloor\frac{m-3}{2}\right\rfloor [2^{m}-1,m+1]_{2} 2^{m-1}+\theta_{2} - Partial Difference Sets [ 40 ] [\binom{m}{2},m-1]_{2} m-1 - - [ 45 ] [\binom{m}{2}+1,m-1]_{2} m [\binom{m}{1}+\binom{m}{2},m]_{2} m [\binom{m}{1}+\binom{m}{2}+1,m]_{2} m+1 [2^{m}-1,m+2]_{2} 2^{\frac{n}{2}}-2 - Vectorial [ 26 ] [2^{m}-1,m+n]_{2} 2^{m-2}+2^{\frac{m}{2}+1} 2<n\leq\frac{m}{2}+1 Boolean [2^{m}-1,2m+1]_{2} 2^{m-2}+2^{\frac{m}{2}+1} - Functions [2^{m}-1,m+1]_{2} 2^{\frac{m-1}{2}-1}(\frac{m+1}{2}+1)-1 - Characteristic [ 32 ] [p^{m}-1,m+1]_{p} - p be prime functions [p^{m}-1,m+1]_{p} p^{m-s-1}(p-1)(s(p-1)+1) p be prime, (p-1)(p^{s-2}-s)>1 Maiorana [ 43 ] a(p^{m-s}-p^{m-s-1})(p^{k}-1) p be prime, k\geq 2,(k,p)\neq(2,2) , McFarland 2\leq a\leq(p-1)p^{k-2},s=2k functions [p^{m}-1,m]_{p} (p-1)^{2}p^{m-2} m>2 , p be odd prime p -ary functions [ 42 ] [p^{m}-1,m-1]_{p} [p^{m}-1,m]_{p} p^{m-1}(p-2) [q^{m}-1,m+1]_{q} \sum_{j=1}^{k}(q-1)^{j}\binom{m}{j} q=p^{h} , p be odd prime, h\geq 1 Boolean functions [ 4 ] 1.3 Our contributions In this paper, we prove the following results. Theorem 1.1. Let {\bf C}\subset{\bf F}_{q}^{n} be a q -ary k -dimensional linear code with the maximum and minimum weights w_{max} and w_{min} . Suppose that the Ashikhmin-Barg condition of this code {\bf C} \frac{w_{min}}{w_{max}}>\frac{q-1}{q} is satisfied and thus {\bf C} is a minimal code. Set n^{\prime}=\lceil\frac{qw_{min}}{q-1}\rceil-w_{max}. Then we construct an explicit q -ary minimal linear code {\bf C}^{\prime}\subset{\bf F}_{q}^{n+n^{\prime}} with the maximum weight at least w_{max}+n^{\prime} and the minimum weight w_{min} satisfying \frac{w_{min}}{w_{max}+n^{\prime}}\leq\frac{q-1}{q}. The linear code {\bf C}^{\prime} is a minimal linear code violating the Ashikhmin-Barg condition. Theorem 1.2. Let {\bf C}\subset{\bf F}_{q}^{n} be a projective linear [n,k]_{q} code with the maximum weight w\leq n . Let h be a positive integer. Then we construct explicit simplx complementary [\frac{q^{k+h}-1}{q-1}-n,k+h]_{q} code with the maximum weight q^{k+h-1} and the minimum weight q^{k+h-1}-w . When h>\log_{q}w-k+2 , this simplex complementary code is a minimal code satisfying the Ashikhmin-Barg condition. Corollary 1.1. Let \mathbf{C}^{\prime}\subset\mathbf{F}_{q}^{n+n^{\prime}} be the minimal linear code constructed in Theorem 1.1 from an [n,k,d] linear code \mathbf{C} with the generator matrix {\bf G} and the weight distribution [A_{0},A_{w_{1}},A_{w_{2}},\dots,A_{w_{t}}] . Let {\mathbf{{C}}}^{*}\subset\mathbb{F}_{q}^{n} denote the (k-1) -dimensional subcode of {\mathbf{{C}}} generated by removing the first row of {\bf G} , and assume its weight distribution is [A^{*}_{0},A^{*}_{w_{1}},A^{*}_{w_{2}},\dots,A^{*}_{w_{t}}] . Then