PaperlayerView exact revision on arXiv

Source-linked AI summary

Linear programming bounds for binary and ternary LCD Codes

Ming-Hsuan Kang, Maosheng Xiong

arXiv:2609.08662v2cs.ITcs.DMmath.COmath.IT

TL;DR

Existing LP bounds for binary and ternary LCD codes leave room for stronger constraints on their ordinary weight distributions. This paper uses finitely many Gauss phases to add such constraints without increasing the variable count, and reports exact improvements over existing LP relaxations.

  • Problem

    The paper seeks stronger upper bounds on minimum distance for binary and ternary LCD codes than the real-valued LCD counting LP provides.

    Source: §1 · pp. 1–2

  • Method

    It converts special weight-enumerator values into finitely many Gauss phases and uses each phase to impose linear constraints on ordinary weight distributions.

    Source: §1 · p. 2, §6 · p. 13

  • Results

    62 binary and 39 ternary pairs show strict improvements over the LCD counting LP, and four binary comparisons exactly improve on the joint-weight-enumerator LP.

    Source: §6 · p. 13

  • Takeaways & Limitations

    The method strengthens these LP relaxations while retaining 2(n + 1) ordinary weight-distribution variables and using a bounded number of branches and added equations.

    Source: §6 · p. 13

    Feasibility is only a necessary condition for a code's existence, and the comparisons do not establish dominance over the joint model for all parameters.

    Source: §4.2 · p. 11, §6 · p. 13

Abstract

from arXiv · show

We derive linear programming (LP) bounds on the minimum distance of binary and ternary linear complementary dual (LCD) codes by imposing arithmetic constraints on their weight enumerators. Special values of the weight enumerator give finitely many Gauss phases, each of which yields linear equations in the ordinary weight-distribution variables. The resulting bounds strengthen the real-valued LCD counting LP without introducing additional variables; both the number of branches and the number of added equations per branch are bounded independently of the code length. Exact certificates establish strict improvements for 62 binary parameter pairs of length at most 20 and 39 ternary pairs of length at most 14. For four binary pairs, the bounds also improve the joint-weight-enumerator LP while using fewer variables per branch. These comparisons show that Gauss-phase information provides a compact strengthening of existing LP relaxations for LCD codes.

1 Introduction

The paper strengthens existing LP bounds for binary and ternary LCD codes by converting weight-enumerator Gauss-phase information into constraints on ordinary weight distributions. It targets these alphabets because, for q > 3, every linear code is monomially equivalent to an LCD code.

1 Introduction

  • For q > 3, every linear code is monomially equivalent to an LCD code, so the paper focuses on binary and ternary codes.The target is upper bounds on minimum distance for fixed length and dimension.Source: §1 · p. 1
  • Earlier LCD counting bounds combine weight-counting inequalities with MacWilliams identities, while the joint-weight-enumerator approach uses O(n^3) coefficients.The counting LP has reported useful bounds in certain parameter ranges; a direct ternary extension of the joint formulation would involve more coordinate patterns and likely greater computational cost.Source: §1 · pp. 1–2
  • The new bounds strengthen the LCD counting LP while retaining O(n) ordinary weight variables, and four selected binary comparisons also improve the joint-weight-enumerator LP.The joint-weight-enumerator LP uses O(n^3) coefficients; the four improvements are verified exactly.Source: §1 · p. 2
  • The special-value characterizations used here follow earlier matroid and Tutte-polynomial work, with ternary and binary expressions also given by Gioan and Las Vergnas and Pendavingh.The paper presents them through quadratic forms modulo three and modulo four, interpreting the special weight-enumerator values as Gauss sums.Source: §1 · p. 2
  • The method fixes one of finitely many Gauss-sum phases to derive linear constraints on ordinary weight distributions; every LCD code satisfies at least one resulting LP.The paper presents this as the first use of these weight-enumerator characterizations to derive LP bounds for binary and ternary LCD codes.Source: §1 · p. 2

2 Preliminaries

The preliminaries set up code and dual weight distributions and the identities used to relate them. They also establish the LCD condition through the code's hull.

2 Preliminaries

  • An [n, k, d]_q code is a k-dimensional linear subspace of Fq^n with minimum distance d.The passage introduces the code notation used in the preliminaries.Source: §2 · p. 3
  • The hull of C is C ∩ C⊥, and C is LCD precisely when this hull is zero.Source: §2 · p. 3
  • The weight enumerator is denoted WC(z), with Aj and Bj representing the weight distributions of C and C⊥, respectively.The text also considers real arrays that need not be weight distributions, whose polynomial form supplies duality relations for the LP bounds.Source: §2 · p. 3
  • The MacWilliams identities relate the weight distributions of a code and its dual through q-ary Krawtchouk polynomials.Source: §2 · p. 3

3 Characterization of ternary and binary LCD codes

The section characterizes ternary and binary LCD codes through special weight-enumerator values and the phases of their associated quadratic-form Gauss sums. It gives quadratic-form proofs of these characterizations and uses MacWilliams identities to derive duality relations.

3.1 Ternary LCD codes

  • For ternary codes, C is LCD exactly when |WC(ω)| = 3^(k/2), and the special value is the Gauss sum of its quadratic form.The radical of the restricted form is C ∩ C⊥; the form is nondegenerate precisely when that radical is zero.Source: §3.1 · p. 4

3 Characterization of ternary and binary LCD codes

  • MacWilliams identities evaluated at ω for ternary codes and at i and −1 for binary codes yield relations for real weight-distribution arrays, with duality applied to C and C⊥.The characterizations draw on earlier matroid and Tutte-polynomial work, while the section supplies quadratic-form proofs and uses MacWilliams identities for duality relations.Source: §3 · p. 4, §3.1 · p. 5, §3.2 · p. 7

3.2 Binary LCD codes

  • For binary codes, C is LCD exactly when |WC(i)| = 2^(k/2), where WC(i) is the Gauss sum of the restricted quadratic refinement.The restricted form is nondegenerate precisely when its radical is zero.Source: §3.2 · p. 6
  • For binary LCD codes, the phase of WC(i) is indexed by β(C), the Brown invariant, with allowed phases restricted by whether the code contains an odd-weight word.When the form is alternating, k is even; the resulting Brown invariant lies in {0, 4}.Source: §3.2 · pp. 6–7

4 Linear programming bounds

Gauss-phase refinements turn special-value characterizations into branch-specific linear constraints on ordinary weight distributions. These constraints strengthen the LCD counting LP while retaining its variables.

4 Linear programming bounds

  • The baseline LP uses real code and dual weight variables, MacWilliams identities, and counting inequalities for positive-weight codewords.Its distance bound is the largest proposed minimum distance for which the feasibility problem remains feasible.Source: §4 · p. 8

4.1 Ternary LP bounds

  • In the ternary case, fixing one of two phases determines residue totals and adds two linear equations; the largest feasible distance gives an upper bound for every ternary LCD code.The bound is found by testing candidate distances from the Singleton bound downward until a branch is feasible.Source: §4.1 · p. 9

4.2 Binary LP bounds

  • In the binary case, fixing the parity type and phase determines residue totals; at most eight branches add three equations and the endpoint constraint A_n = η.The largest distance with an admissible feasible branch bounds every binary LCD code; feasibility remains only necessary for code existence.Source: §4.2 · pp. 10–11

4 Linear programming bounds

  • Both refinements retain the 2(n + 1) real variables of the LCD counting LP, adding residue constraints for fixed phase choices.A feasible relaxation is only a necessary condition for a code to exist.Source: §4 · p. 8, §4.2 · p. 11

5 Numerical bounds and exact verification

Across the tested parameter ranges, Gauss-phase bounds strictly improve the LCD counting LP for many binary and ternary pairs, with exact verification for every reported improvement. Comparisons with the binary joint-weight-enumerator LP show gains in some cases but no general dominance.

5.1 Bounds and parameter ranges

  • For all 1 ≤ k < n, the study considers 190 binary parameter pairs across lengths 2–20 and 91 ternary parameter pairs across lengths 2–14.A feasible LP point need not correspond to a code.Source: §5.1 · p. 11
  • Exact bounds use rational feasible points and integer infeasibility certificates; values obtained only by floating-point optimization are labeled screening values.Verification details are provided in Online Resource 1.Source: §5.1 · p. 11

5.2 Comparison with the LCD counting LP

  • 62 binary and 39 ternary parameter pairs have strictly smaller Gauss-phase bounds than the LCD counting LP; all 101 comparisons are exactly verified.Every improvement is by one except binary (15, 4), where the bound falls from 8 to 6.Source: Table 1 · p. 11, §5.2 · p. 11, Table 2 · p. 12

5.3 Comparison with the binary joint-weight-enumerator LP

  • The joint-weight-enumerator comparison has equal screening values in 57 cases; Gauss-phase is stronger in four and the joint LP in one.The four Gauss-phase improvements are exactly verified, but these computations establish no general dominance.Source: Table 4 · p. 13, §5.3 · p. 13

6 Conclusion

The paper converts Gauss-phase information in binary and ternary weight enumerators into linear constraints for minimum-distance bounds. Exact scans show strict improvements over the LCD counting LP, with four binary improvements over the joint-weight-enumerator LP.

6 Conclusion

  • Gauss-phase information becomes linear constraints while preserving 2(n + 1) ordinary weight-distribution variables and requiring only bounded branches and additional equations.The number of branches and added equations per branch is bounded independently of code length.Source: §6 · p. 13
  • 62 binary and 39 ternary parameter pairs strictly improve on the real-valued LCD counting LP, with exact endpoint verification for all 101 comparisons; four binary comparisons also improve on the joint-weight-enumerator LP.The scans cover lengths through 20 for binary codes and 14 for ternary codes.Source: §6 · p. 13
  • The comparisons concern the specified relaxations and do not establish dominance over the joint model for all parameters or improvements over tables combining several upper bounds.Source: §6 · p. 13
  • Further work could combine Gauss-phase equations with the joint-weight-enumerator model or seek additional arithmetic constraints that preserve the ordinary-weight formulation’s small size.Source: §6 · p. 13

A The binary joint-weight-enumerator benchmark

The binary joint-weight-enumerator LP serves as a benchmark for the Gauss-phase bounds. It models coordinate patterns of codeword pairs, adds constraints to the LCD counting LP, and uses joint MacWilliams invariance.

A The binary joint-weight-enumerator benchmark

Data and code availability

The paper’s frozen companion archive provides the computational materials supporting Section 5 and instructions for reproducing them.

Data and code availability

  • The self-contained Online Resource 1 archive contains code, exact certificates, rational feasibility witnesses, machine-readable results, and reproduction guidance in its README.The archive is version 2026-09-13 and does not require access to the development repository.Source: Data and code availability · p. 14

Statements and Declarations

The declarations report research support, no competing interests, and the authors’ use of generative AI during manuscript preparation.

Funding

  • Ming-Hsuan Kang’s work was supported by Taiwan’s National Science and Technology Council under Grant NSTC 115-2115-M-A49-010.Source: Funding · p. 15
  • Maosheng Xiong’s work was supported by the Hong Kong Research Grant Council under Grant no. 16307524.Source: Funding · p. 15

Competing interests

Use of generative AI

  • OpenAI Codex assisted with manuscript restructuring, software integration, and computational consistency checks; the authors say they independently reviewed and validated the work and take responsibility for it.Source: Use of generative AI · p. 15
Loading 2609.08662v2…