Improvement of the square-root low bounds on the minimum distances of BCH codes and Matrix-product codes

Xiaoqiang Wang, Liuyi Li, Yansheng Wu, Dabin Zheng, Shuxian LuarXiv 2025 · DOI · arXiv

This paper, recently published on arXiv, provides a significant theoretical leap in coding theory, specifically focusing on the "minimum distance" of error-correcting codes. The minimum distance ($d$) is the holy grail of code design: it determines exactly how many errors a code can fix.

The authors tackle the notoriously difficult task of finding infinite families of self-dual codes where the minimum distance grows at least as fast as the square root of the code's length ($d \ge \sqrt{n}$).

TL;DR

The researchers significantly sharpen the lower bounds for the minimum distance of dual BCH codes, achieving improvements by factors as large as the field size ($q$). They then leverage these refined bounds through matrix-product constructions to build new infinite families of self-dual codes that meet or exceed the elusive "square-root lower bound."

What Problem Does This Paper Address?

In coding theory, self-dual codes are highly prized for their mathematical symmetry and applications in cryptography and lattice theory. However, as the length of a code ($n$) increases toward infinity, ensuring that the minimum distance ($d$) remains large is extremely challenging.

The "square-root bound" ($d \approx \sqrt{n}$) is a major benchmark. While some codes are known to meet this, constructing infinite families of such codes—especially cyclic codes like BCH codes—has remained a "hard problem" for decades. Previous research had established some lower bounds, but they were often quite loose, leaving a gap between what was proven and what was likely possible.

Methods

The authors employ a two-step strategy combining deep algebraic analysis with structural code construction:

  1. Refined Cyclotomic Coset Analysis: The "zeroes" of a cyclic code (like a BCH code) are determined by sets of integers called cyclotomic cosets. The authors performed a granular analysis of the $q$-adic expansions of these coset leaders. By proving new lemmas (specifically Lemma 5 and Lemma 8) about the properties of these expansions, they were able to identify more "guaranteed" zeroes in the dual codes than previous researchers had found.
  2. Matrix-Product Construction: This is a method of building a long code by combining several shorter "component" codes using a specific matrix. The authors used the $(u | u+v)$ construction and its generalizations. By plugging their newly improved BCH distance bounds into these matrix-product frameworks, they generated self-dual codes with superior distance properties.

Datasets

As a theoretical paper in mathematics and information theory, this work does not use empirical datasets. Instead, it relies on mathematical proofs and provides numerical examples (found in Tables 1 and 2) to compare their new lower bounds against previous benchmarks established in the literature.

Key Insights and Ideas

  • The Power of $q$: The most striking insight is that existing bounds for the duals of BCH codes were missing a factor roughly equal to the size of the finite field ($q$ or $q^s-1$). This suggests that the error-correcting potential of these dual codes was significantly underestimated.
  • Beyond Narrow-Sense: While much work focuses on "narrow-sense" BCH codes, this paper provides improvements for Euclidean and Hermitian duals across specific ranges of "designed distances," offering a more flexible toolkit for code designers.
  • Structural Synergy: The paper demonstrates that matrix-product constructions are not just a way to make codes longer, but a powerful "multiplier" for improvements made at the component code level.

Key Results

  • Massive Bound Improvements: For the duals of BCH codes, the new lower bounds are roughly $q$ to $q^s$ times larger than previous results.
  • Example from Table 2: For a specific code over $\mathbb{F}_{25}$, the previous best-known lower bound for the distance was 131. This paper improves that bound to 625.
  • New Self-Dual Families: The authors successfully constructed several new classes of Euclidean and Hermitian self-dual codes. These codes are proven to have minimum distances that either hit the square-root bound ($\sqrt{n}$) or a "square-root-like" bound ($c\sqrt{n}$ with $c=1/2$).
  • Generalization: The work generalizes and improves upon recent high-profile results (e.g., Chen and Ding, 2023), providing larger distance guarantees for the same code lengths.

Limitations and Future Work

  • Range Specificity: The improved bounds apply to specific ranges of the "designed distance" ($\delta$). While these ranges are significant, they do not cover every possible BCH code configuration.
  • The Cyclic Holy Grail: While the authors improved results for self-dual linear codes, they acknowledge that constructing infinite families of self-dual cyclic codes with square-root bounds remains an exceptionally difficult open problem.
  • Future Direction: The authors invite the community to explore whether these $q$-adic expansion techniques can be applied to other families of cyclic codes beyond the BCH class.

Summary updated

BibTeX
@misc{wang2025improvement,
  author = {Xiaoqiang Wang and Liuyi Li and Yansheng Wu and Dabin Zheng and Shuxian Lu},
  title = {{Improvement of the square-root low bounds on the minimum distances of BCH codes and Matrix-product codes}},
  year = {2025},
  eprint = {2504.12116},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2504.12116},
}

Loading related content...

Figure