🔢 mathematics

Constructing Good Abelian Codes via Shift Bounds and Genetic Algorithms

This paper proposes a framework for constructing linear codes by deriving generalized shift bounds for abelian codes and employing genetic algorithms to search for optimal defining sets, successfully yielding record-breaking parameters over $\mathbb{F}_3$ and $\mathbb{F}_4$ that surpass existing tables.

Original authors: Cong Yu, Hao Chen, Zhonghua Sun, Shixin Zhu

Published 2026-08-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Cong Yu, Hao Chen, Zhonghua Sun, Shixin Zhu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of modern communication, from satellite links to deep-space probes, the reliability of data transmission depends on invisible mathematical shields known as error-correcting codes. These are carefully designed sets of numbers that allow a receiver to detect and fix mistakes that occur when a signal travels through a noisy environment. The quality of such a code is measured by three main factors: how much information it can carry, how long the message is, and most importantly, how many errors it can correct before the message becomes garbled. For decades, mathematicians have searched for the perfect balance among these factors, trying to find codes that are as efficient as possible. While simple, repeating patterns of numbers have served well for basic tasks, more complex structures are needed to push the boundaries of what is possible, especially when dealing with large amounts of data.

A team of researchers has recently explored a powerful family of these mathematical shields called abelian codes. These are sophisticated arrangements of numbers built upon the symmetry of groups, which are collections of elements that follow specific rules of combination. Unlike the simpler, one-dimensional codes that have been studied for years, these new codes utilize multi-dimensional structures, offering a much richer playground for discovery. The researchers faced a dual challenge: they needed to prove that certain arrangements of these codes would always work well, and they also needed a way to find the very best arrangements among the billions of possibilities that exist. To solve this, they combined rigorous mathematical theory with a computational strategy inspired by natural evolution, successfully uncovering several new codes that outperform everything previously known.

The first part of their work focused on establishing a solid theoretical foundation. The team developed a method to calculate a guaranteed minimum distance for these codes, which essentially tells us the maximum number of errors the code can handle. They achieved this by extending a known mathematical technique, originally designed for simpler codes, to work with these more complex, multi-dimensional structures. By carefully selecting specific patterns within the code's structure, they were able to prove that entire families of these codes would always perform at a certain high level. This was not just a theoretical exercise; they explicitly constructed infinite families of these codes, including examples using binary and ternary systems, proving that they could reliably correct more errors than previously thought possible for their size.

However, theory alone could not find every possible improvement. The space of potential codes is so vast that checking every single combination by hand or with a standard computer program is impossible. To navigate this enormous search space, the researchers turned to a genetic algorithm, a type of computer program that mimics the process of natural selection. In this digital ecosystem, each potential code is represented as a chromosome, a string of bits where each bit decides whether a specific mathematical building block is included or excluded. The program starts with a random population of these chromosomes and then tests them to see how well they perform. Those that perform poorly are discarded, while the best ones are allowed to "reproduce," mixing their traits to create new generations of codes. Over many cycles, this process evolves increasingly effective codes, much like how nature evolves better-adapted species over time.

Using this evolutionary search, the team discovered several record-breaking codes that surpassed the best-known parameters listed in the standard reference tables for the field. Specifically, they found new codes over fields with four and three elements that could correct more errors than any previously known code of the same length and information capacity. For instance, they identified a code with a length of 75 that could carry 17 units of information while correcting 35 errors, improving upon the previous best by one error. They found similar improvements for codes with lengths of 169, where the new discoveries allowed for significantly better error correction. These findings were not just simulations; the researchers used specialized mathematical software to verify the exact performance of each code, ensuring that the improvements were real and mathematically sound.

The researchers did not stop at simply finding these superior codes. They also demonstrated how to combine them to create even more powerful tools. By taking two of their new codes where one is contained within the other, they applied a construction method that allowed them to build a third, even better code. This technique, known as Construction X, enabled them to generate additional record-breaking codes with improved parameters. The study concludes that while mathematical theory provides a reliable map for known territories, heuristic search methods like genetic algorithms are essential for exploring the uncharted regions where the best codes might be hiding. The work confirms that abelian codes, when paired with intelligent search strategies, remain a fertile ground for discovering the next generation of error-correcting codes that will keep our digital world running smoothly.

Technical Summary: Constructing Good Abelian Codes via Shift Bounds and Genetic Algorithms

Problem Statement
The construction of linear codes with optimal or near-optimal parameters (length $n$ , dimension $k$ , and minimum distance $d$ ) remains a central challenge in algebraic coding theory. While Abelian codes, defined as ideals in the group algebra $\mathbb{F}_qG$ where $G$ is a finite Abelian group, offer greater flexibility in parameters compared to classical cyclic codes, their systematic construction is difficult. Existing literature has largely focused on the structural classification of these codes or theoretical distance bounds (such as the generalized shift bound) without providing systematic methods to generate infinite families with guaranteed parameters. Furthermore, the search space for Abelian codes—defined by unions of $q$ -cyclotomic cosets—is exponentially large, making exhaustive enumeration computationally infeasible for moderate group orders.

Methodology
The paper employs a dual approach combining theoretical algebraic bounds with heuristic computational search:

Theoretical Framework (Shift Bound):
The authors formalize the theory of multivariate $q$ -cyclotomic cosets and derive a concrete shift bound for two-dimensional Abelian groups $G = C_m \times C_n$ . This bound generalizes the classical Van Lint–Wilson bound for cyclic codes. By constructing independent sequences on the dual character group relative to the defining set $D(f)$ , the authors establish a lower bound on the minimum distance of the code $\langle f \rangle$ . This theoretical tool is used to explicitly construct several infinite families of Abelian codes with guaranteed minimum distances, extending previous cyclic code constructions to cases involving even integers $r$ .
Heuristic Search (Genetic Algorithm):
To discover codes with parameters beyond those guaranteed by theoretical bounds, the authors design a Genetic Algorithm (GA).
- Encoding: Chromosomes are binary vectors representing the inclusion or exclusion of entire $q$ -cyclotomic cosets in the code's defining set. This ensures that the algebraic structure of the Abelian code is preserved during evolution.
- Fitness Function: The fitness of a chromosome is determined by the difference between the code's true minimum distance (computed via the Magma computer algebra system) and the Best Known Linear Code (BKLC) lower bound from Grassl's tables.
- Operators: The algorithm utilizes tournament selection, single-point crossover, and bit-flip mutation. Strategies are implemented to control chromosome weight, focusing on high-dimension codes or their duals to leverage Magma's computational efficiency.
- Post-Processing: The nested structure of the discovered codes is exploited using Construction X (combining a subcode, a supercode, and an auxiliary code) to generate additional linear codes with improved parameters.

Key Contributions

Theoretical Extension: The paper extends the shift bound to two-dimensional Abelian groups and uses it to construct infinite families of binary and ternary Abelian codes. These constructions generalize known cyclic code families (from reference [4]) to include even values of $r$ , thereby enriching the repository of linear codes with favorable distance parameters.
Algorithmic Innovation: This work represents the first application of genetic algorithms to the search of Abelian codes over principal ideal group algebras. The proposed method successfully navigates the vast search space of defining sets, outperforming traditional exhaustive search methods.
Record-Breaking Codes: The search yielded multiple linear codes over $\mathbb{F}_3$ and $\mathbb{F}_4$ that surpass the previously best-known parameters documented in Grassl's tables. Notable examples include codes over $C_{13} \times C_{13}$ and $C_{15} \times C_5$ .
Parameter Improvement via Construction X: By identifying nested Abelian codes, the authors applied Construction X to derive further linear codes with improved parameters, many of which also break existing records.

Results
The experimental results, conducted over groups such as $C_{13} \times C_{13}$ (length 169) and $C_{15} \times C_5$ (length 75), demonstrate the efficacy of the proposed methodology.

Direct Discoveries: The GA identified numerous codes with minimum distances exceeding the BKLC bounds. For instance, a $[169, 18, 87]_3$ code was found, improving the distance by 3 over the previous best of 84.
Construction X Outcomes: Applying Construction X to the nested structures found by the GA produced additional record-breaking codes, such as a $[179, 19, 90]_3$ code, improving the distance by 1 over the known bound of 89.
Data Availability: The generator matrices for all record-breaking codes and related data are made available to promote reproducibility.

Significance and Claims
The paper claims that Abelian codes, when combined with heuristic search techniques like genetic algorithms, constitute a viable and effective strategy for discovering linear codes with unknown or record-breaking parameters. The authors emphasize that while theoretical bounds provide a foundation for infinite families, computational search is necessary to uncover specific, high-performing codes that may not fit into simple algebraic patterns. The work bridges the gap between structural theory and practical code construction, demonstrating that the shift bound can guide the design of good codes while genetic algorithms can efficiently explore the remaining space to find optimal instances. The authors modestly note that a further question remains regarding whether the lower bounds of the specific record-breaking codes found via the GA can also be theoretically derived via the shift bound.

More like this