Gröbner bases and the second generalized Hamming weight of a linear code

Basic Information

• Paper ID: 2510.09917
• Title: Gröbner bases and the second generalized Hamming weight of a linear code
• Authors: Hernán de Alba (Universidad Autónoma de Zacatecas), Cecilia Martínez-Reyes (Universidad Autónoma de Zacatecas)
• Classification: math.AC (Commutative Algebra), cs.IT (Information Theory), math.IT (Mathematical Information Theory)
• Publication Date: October 10, 2025
• Paper Link: https://arxiv.org/abs/2510.09917v1

Abstract

It is known that for binary codes, Gröbner bases can be used to obtain a subset of minimal support codewords, which can be used to determine the second generalized Hamming weight of the code. This paper establishes conditions under which non-binary codes satisfy the same property. We also construct families of codes over arbitrary non-binary finite fields that do not satisfy this property. Furthermore, we prove that when the subset obtained through Gröbner bases is sufficient to determine the second generalized Hamming weight, this invariant can also be recovered from the degrees of the syzygies in the minimal free resolution.

Research Background and Motivation

Problem Background

Generalized Hamming weights (GHWs) are important parameters of linear codes with widespread applications in information theory. For a linear code C ⊂ F_q^n, the i-th generalized Hamming weight is defined as:

d_i(C) = min{ω(D) : D is an i-dimensional subspace of C}

where ω(D) denotes the weight of the subspace D (the size of its support).

Research Motivation

1. Known results for binary codes: For binary codes, García-Marco et al. proved that the reduced Gröbner basis of the binomial ideal associated with the code can be used to determine the first and second generalized Hamming weights.
2. Challenges for non-binary codes: It remains unclear whether the same method applies to non-binary codes (q > 2), which is the 4th problem posed by García-Marco et al. in 10.
3. Theoretical completeness: There is a need to establish a complete theoretical framework to understand the applicability of the Gröbner basis method over different finite fields.

Core Contributions

1. Establishing sufficient conditions: Proposes sufficient conditions for the set M_G of non-binary codes to be a d_2-test set (Theorem 4.7)
2. Constructing counterexamples: For each q > 2, constructs families of linear codes where M_G is not a d_2-test set (Theorem 5.1)
3. Connecting to free resolutions: Proves that when M_G is a d_2-test set, the second generalized Hamming weight can be determined from the Betti numbers of the minimal free resolution (Theorem 6.2)
4. Introducing the d_2-test set concept: Provides theoretical tools for more precisely characterizing the computation of the second generalized Hamming weight

Methodology Details

Problem Formulation

Given a linear code C ⊂ F_q^n, the goal is to determine when the second generalized Hamming weight d_2(C) can be computed through the Gröbner basis method.

Core Concepts

d_2-test set

Definition 3.1: For a linear code C ⊂ F_q^n, a set M ⊂ M_C is called a d_2-test set of C if there exist c_1, c_2 ∈ M such that dim⟨c_1, c_2⟩ = 2 and ω(⟨c_1, c_2⟩) = d_2(C).

Key set construction

For a linear code C of dimension k ≥ 2, define:

• M_1 = {m ∈ C \ {0} | ∃m' ∈ C such that d_2(C) = ω(⟨m,m'⟩)}
• m_1 = min_≺(M_1) (using a specific ordering relation)
• M_2 = {m ∈ C | d_2(C) = ω(⟨m_1,m⟩)}
• m_2 = min_≺(M_2)

Main Theoretical Results

Theorem A (Theorem 4.7)

Sufficient condition: Let C ⊂ F_q^n be a linear code satisfying |I_C ∩ J_C| ≤ (|J_C| + 1)/2, where I_C = supp(m_1) and J_C = supp(m_2). If G is a reduced Gröbner basis of I(C), then M_G is a d_2-test set.

Theorem B (Theorem 5.1)

Existence of counterexamples: For each q > 2, there exists a linear code C ⊂ F_q^n such that M_G is not a d_2-test set.

Theorem C (Theorem 6.2)

Free resolution characterization: Let C ⊂ F_q^n be a linear code of dimension k, and M ⊂ M_C. Then:

1. min{j | β_{1,j}(R/I_M) ≠ 0} = d_1(C) if and only if M contains a codeword of minimal Hamming weight
2. min{j | β_{2,j}(R/I_M) ≠ 0} = d_2(C) if and only if M is a d_2-test set

Technical Innovations

1. Condition characterization: Generalizes the inequality |I_C ∩ J_C| ≤ |I_C|/2 from binary codes to the non-binary case |I_C ∩ J_C| ≤ (|J_C| + 1)/2
2. Counterexample construction: Through careful code construction, demonstrates the limitations of the Gröbner basis method in the non-binary case
3. Algebraic geometry connection: Establishes deep connections between coding theory and free resolution theory in commutative algebra

Experimental Setup

Construction Examples

Example 4.8: Consider a linear code over F_3^9 with generator matrix:

G = [1 0 0 0 0 1 0 2 0]
    [0 1 0 0 1 1 1 0 1]
    [0 0 1 1 2 2 1 1 0]

Through computation, verification shows:

• I_C = {1, 6, 8}, J_C = {2, 5, 6, 7, 9}
• |I_C ∩ J_C| = 1 < 3 = (|J_C| + 1)/2
• d_2(C) = |I_C ∪ J_C| = 7
• M_G is indeed a d_2-test set

Counterexample Construction

Example 5.4: For q > 2, construct D' = ⟨c_1, c_2⟩ ⊂ F_q^{2q+2}, where:

• c_1 = (1, 1, α, α^2, ..., α^{q-1}, α, α^2, ..., α^{q-1}, 0, 0)
• c_2 = (0, 0, 1, 1, ..., 1, 1, 1, ..., 1, 1, 1)

Verification shows |I_{D'} ∩ J_{D'}| = 2q - 2 > (2q + 1)/2, violating the sufficient condition.

Experimental Results

Main Findings

1. Necessity of conditions: Concrete examples verify the importance of the conditions in Theorem 4.7
2. Algorithm implementation: SageMath is used to implement the FGLM algorithm for computing reduced Gröbner bases
3. Computational complexity: In Example 4.8, the reduced Gröbner basis G contains 457 binomials, of which 27 belong to R_X

Theoretical Verification

Through constructed counterexamples, it is demonstrated that:

• For q > 2, there exist linear codes such that M_G is not a d_2-test set
• This shows that results for binary codes cannot be directly generalized to non-binary cases
• Additional conditions are necessary to ensure the validity of the method

Related Work

Coding Theory Background

• Generalized Hamming weights: Introduced by Wei in 1991, with important applications in information theory
• Special code classes: Generalized Hamming weights of cyclic codes, Reed-Muller codes, trace codes, etc. have been extensively studied
• Computational methods: Including quadratic form methods, Gröbner basis methods, free resolution methods, etc.

Applications of Gröbner Bases in Coding Theory

• Binomial ideals: Márquez-Corbella et al. established connections between linear codes and binomial ideals
• Test set theory: Barg et al. developed the concept of test sets for minimum distance decoding

Algebraic Geometry Methods

• Free resolutions: Johnsen and Verdure proved that all generalized Hamming weights can be recovered from Betti numbers of Stanley-Reisner rings
• Monomial ideals: Study of monomial ideals related to codeword supports

Conclusions and Discussion

Main Conclusions

1. Condition characterization: Establishes sufficient conditions for M_G to be a d_2-test set in non-binary codes
2. Revealing limitations: Proves that results for binary codes cannot be simply generalized to non-binary cases
3. Algebraic connections: Establishes deep connections between coding theory and commutative algebra

Limitations

1. Sufficiency of conditions: The given conditions are sufficient but may not be necessary
2. Computational complexity: Gröbner basis computation may face complexity issues in practical applications
3. Generalizability: Results are primarily focused on the second generalized Hamming weight; generalization to higher-order weights requires further research

Future Directions

1. Necessary and sufficient conditions: Seek necessary and sufficient conditions for M_G to be a d_2-test set
2. Algorithm optimization: Develop more efficient computational methods
3. Higher-order generalization: Extend results to higher-order generalized Hamming weights
4. Application exploration: Specific applications in cryptography and communication theory

In-Depth Evaluation

Strengths

1. Theoretical depth: Establishes deep connections between coding theory and algebraic geometry with significant theoretical value
2. Completeness: Provides not only positive results but also constructs counterexamples, presenting a complete picture of the problem
3. Technical innovation: Introduces the d_2-test set concept, providing new tools for related research
4. Rigorous proofs: All major results have complete mathematical proofs with sound logic

Weaknesses

1. Practical limitations: Primarily theoretical results; the value in practical coding applications remains to be verified
2. Computational complexity: The complexity of Gröbner basis computation may limit the practical applicability of the method
3. Generalization limitations: Results are primarily focused on the second generalized Hamming weight; generalization to more general cases is unclear

Impact

1. Academic contribution: Opens new directions for cross-disciplinary research between coding theory and algebraic geometry
2. Theoretical completeness: Perfects the theoretical framework for computing generalized Hamming weights
3. Methodological value: Provides methodological guidance for studying similar problems

Applicable Scenarios

1. Theoretical research: Suitable for cross-disciplinary research between coding theory and algebraic geometry
2. Algorithm design: Provides theoretical foundation for developing new algorithms for computing generalized Hamming weights
3. Teaching and research: Serves as a typical example of applying algebraic methods in coding theory

References

Main references include:

• 10 García-Marco et al.'s work on free resolutions and generalized Hamming weights of binary codes
• 19 Johnsen and Verdure's research on the relationship between Betti numbers of Stanley-Reisner rings and Hamming weights
• 23 Márquez-Corbella et al.'s foundational work on ideals associated with linear codes
• 30 Wei's original definition of generalized Hamming weights

This paper makes important contributions at the intersection of coding theory and algebraic geometry. Through rigorous mathematical analysis, it reveals the applicability and limitations of the Gröbner basis method for non-binary codes, laying a solid theoretical foundation for further research in related fields.