🔢 mathematics

New optimal linear codes over $\ZZ_4$

This paper introduces novel construction methods for linear codes over $\mathbb{Z}_4$ that yield new optimal codes, specifically determining all optimal codes for parameters $k_1=2, k_2=0$ and many for $k_1=3, k_2=0$ .

Original authors: Hopein Christofen Tang, Djoko Suprijanto

Published 2026-08-14

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Hopein Christofen Tang, Djoko Suprijanto

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

Imagine you are sending a secret message across a noisy room. To make sure your friend hears it right, you don't just shout the words; you repeat them, change the pitch, or add extra "check" sounds. In the world of digital communication, this is called coding theory. It's the science of packing information into strings of numbers so that even if a little static or interference messes up the signal, the receiver can still figure out the original message.

For a long time, scientists mostly used simple "on/off" switches (like 0s and 1s) to build these codes, similar to a light switch that is either off or on. But in the 1970s, researchers realized that using a slightly more complex switch—one that could be in four different states (0, 1, 2, or 3)—could create much smarter, more efficient messages. This is the world of $\mathbb{Z}_4$ codes. Think of it like a traffic light that doesn't just say "stop" or "go," but also has "caution" and "slow" to give the driver more nuance. The goal for mathematicians is to find the "perfect" code: one that is as short as possible (to save space) but has the strongest possible "error-detecting superpower" (to fix mistakes). This superpower is called the minimum distance. The bigger the distance between valid messages, the harder it is for noise to turn one valid message into another by accident.

In this paper, authors Hopein Christofen Tang and Djoko Suprijanto act like master architects in this digital city. They aren't just looking for one good building; they are inventing new blueprints to construct entire neighborhoods of these perfect codes. They start by proving a fundamental rule about how far apart these messages must be to stay safe, using a clever, simple trick that makes an old, complicated math proof look like child's play. Then, they use this rule to build a toolbox of new methods. With these tools, they successfully construct a massive collection of new codes that are "optimal," meaning they are as strong as mathematically possible for their size. They specifically found all the best possible codes for certain sizes and discovered many new champions for others, beating the previous records held in the global database of known codes. They also showed that some old ideas about what was possible were actually impossible, clearing the path for these new discoveries.

The Story of the Perfect Message

Imagine you are trying to send a secret code to a friend, but you know the messenger might drop a letter or swap a number by mistake. To protect your message, you add extra "guard" numbers. The more guards you have, the safer the message, but the longer the message gets. The big question in this field is: How do we make the message as short as possible while keeping it as safe as possible?

The authors of this paper are working with a special kind of math alphabet that has four letters: 0, 1, 2, and 3. In the past, people mostly used just 0 and 1. But using four letters allows for more complex and efficient codes. The "safety" of a code is measured by something called the Lee distance. You can think of this as the "effort" it takes to turn one valid code into another. If the distance is small, a tiny mistake (like a 1 turning into a 2) could accidentally turn your secret message into a completely different, valid message, and your friend would never know. If the distance is huge, you'd need to make a lot of mistakes to mess it up, so the code is very strong.

The paper tackles two main challenges. First, the authors wanted to prove a "speed limit" for these codes. There is a famous rule (called the Plotkin bound) that says, "You cannot make a code shorter than this without making it weaker." The authors found a new, much simpler way to prove this rule for their four-letter alphabet. It's like showing that a car simply cannot drive faster than the speed limit without crashing, but doing it with a simple logic puzzle instead of a complex physics equation.

Second, and most importantly, they wanted to build the best possible codes that fit right up against this speed limit. These are called optimal codes. They are the "Goldilocks" codes: not too long, not too weak, but just right.

Building the New Codes

The authors didn't just find one or two good codes; they built a whole factory for them. They introduced several new construction methods, which are like recipes for mixing different ingredients to create a perfect code.

One of their key discoveries is a specific type of code where every single non-zero message has the exact same strength. They call these constant weight codes. Imagine a team of superheroes where every single member has exactly the same superpower level. This makes the team incredibly predictable and strong. The authors proved that for any size of code they wanted, they could build this perfect team.

They then used these perfect teams as building blocks. They showed that if you take two good codes and stick them together side-by-side, you get a new, longer code that is still very strong. They also showed how to take a code and "stretch" it out, making it four times longer but keeping its strength proportional. By repeating these steps over and over, they generated a huge list of new codes.

The Results: Beating the Records

The authors tested their new recipes against the "Hall of Fame" of known codes, which is a database maintained by other mathematicians. They found that for codes with a specific structure (where the first part of the code has 2 "free" dimensions and the second part has 0), they found all the optimal codes. This means they didn't just find a good code; they found every possible best code for that specific size.

For a slightly different structure (where the first part has 3 dimensions), they found many new codes that were better than anything previously known. In fact, for many lengths, their new codes had a higher "safety distance" than the previous champions. They even found codes that were so good they were "Plotkin-optimal," meaning they were as close to the theoretical speed limit as math allows.

However, they also had to be the "bad news" bearers in some cases. They proved that for certain specific lengths, it is impossible to build a code that hits the absolute theoretical limit perfectly. It's like trying to build a square circle; the math simply doesn't allow it. They showed that for some lengths, the best you can do is get very close, but you will always be off by a tiny bit (at most 1 or 2 units of distance). This is a crucial finding because it stops other researchers from wasting time trying to solve an impossible puzzle.

Why This Matters

Why should a curious teenager care about four-letter codes? Because every time you send a text, stream a video, or download a file, these codes are working in the background to make sure your data arrives without errors. The more efficient and stronger these codes are, the faster and more reliable our digital world becomes.

By proving new rules and building new, stronger codes, Tang and Suprijanto have given engineers better tools to fight against digital noise. They didn't just find a few new keys; they built a whole new keyring. While they didn't solve every single mystery in the universe of codes (there are still many sizes where the perfect code is unknown), they have significantly expanded the map of what is possible. They showed that with the right construction methods, we can push the boundaries of how much information we can pack into a signal while keeping it safe from errors.

In the end, this paper is a testament to the power of simple, clever thinking. By breaking down a complex problem into smaller, manageable building blocks and proving the rules of the game with a fresh perspective, the authors have unlocked a treasure chest of new, optimal codes that will help keep our digital conversations clear and secure.

Technical Summary: New Optimal Linear Codes over $\mathbb{Z}_4$

Problem Statement
The paper addresses the construction of linear codes over the ring $\mathbb{Z}_4$ (integers modulo 4) with optimal minimum Lee distance. While significant progress has been made in understanding codes over finite rings, particularly through the work of Hammons et al. [16] linking them to nonlinear binary codes, the direct construction of optimal linear codes (specifically those that are not self-dual) remains in its initial stages. Existing literature, such as the database by Aydin and Asamov [3, 4], contains limited results on non-self-dual optimal codes. Furthermore, codes obtained indirectly via Gray maps from other finite rings often suffer from suboptimal minimum distances. The authors aim to fill this gap by developing direct construction methods to generate new linear codes over $\mathbb{Z}_4$ that achieve the highest known minimum Lee distances or meet theoretical bounds.

Methodology
The authors employ a combination of theoretical bounding and recursive matrix construction techniques:

Theoretical Bounds:
- The paper provides an elementary proof of a Plotkin-type bound for the minimum Lee distance of linear codes over $\mathbb{Z}_4$ . This bound is given by $d_L \leq \frac{|C|}{|C|-1}n$ .
- Codes achieving a minimum distance nearest to this upper bound are defined as Plotkin-optimal.
- The authors also reference the Singleton-type Lee distance bound (Dougherty and Shiromoto [14]) but note that Maximum Lee Distance Separable (MLDS) codes (meeting the Singleton bound) are non-existent except for trivial cases. Consequently, the focus shifts to Plotkin-optimality.
Construction Methods:
The paper introduces several recursive and combinatorial construction methods to generate new codes from known ones:
- Base Codes: A family of codes $C(k_1, k_2)$ is defined with generator matrices containing all possible nonzero vectors in $\mathbb{Z}_4^{k_1} \times (2\mathbb{Z}_4)^{k_2}$ . These codes are shown to be Plotkin-optimal with constant Lee weight.
- Construction A (Concatenation): Combining two codes $C_1$ and $C_2$ via a generator matrix $[G_1 | G_2]$ to create a code with length $n(C_1) + n(C_2)$ and minimum distance at least $d_L(C_1) + d_L(C_2)$ .
- Construction B (Expansion): Recursive expansion of a generator matrix $G$ to form larger codes. Specifically, stacking $G$ three times with specific row additions yields codes of length $4n$ , while stacking twice with specific additions yields codes of length $2n$ .
- Corollary Constructions: The authors derive specific corollaries (Construction 1 through 4) that apply these methods to generate families of optimal codes for specific parameter sets, particularly for free linear codes (where $k_2 = 0$ ).

Key Contributions and Results
The primary contributions of the work are the introduction of these construction methods and the resulting generation of new optimal codes:

New Optimal Codes: The authors successfully construct many new free linear codes over $\mathbb{Z}_4$ that possess the highest known minimum Lee distances.
Specific Parameter Sets:
- Case $k_1 = 2, k_2 = 0$ : The authors determined all optimal codes for this parameter set. They found that the difference between the Plotkin bound and the actual minimum Lee distance of the derived optimal codes is at most 1.
- Case $k_1 = 3, k_2 = 0$ : The authors constructed many new optimal and nearly optimal codes for this set, which were previously unknown in the database [4]. For this case, the difference between the bound and the achieved distance is at most 2.
Two-Weight Codes: The paper demonstrates the existence of free optimal two-weight codes (codes with exactly two nonzero weights) using the proposed constructions.
Database Improvement: The results significantly contribute to the Aydin and Asamov database [3, 4], providing updated entries for lengths $n$ up to 61 for $k_1=2$ and up to 66 for $k_1=3$ .

Significance and Claims
The paper claims that its significance lies in moving beyond the reliance on indirect constructions (Gray maps) and self-dual codes to provide direct construction methods for linear codes over $\mathbb{Z}_4$ . By establishing a simple proof for the Plotkin-type bound and utilizing it to define "Plotkin-optimal" codes, the authors provide a framework for systematically generating codes that are close to the theoretical limit of performance.

The authors modestly note that while they have solved the case for $k_1=2$ completely and made substantial progress for $k_1=3$ , the general problem for higher $k_1$ remains open. They propose a conjecture regarding the existence of free linear codes with minimum distances satisfying a specific inequality involving constants $a$ and $b$ . Additionally, the authors indicate that their methods and bounds are being generalized to codes over rings $\mathbb{Z}_{2^r}$ , a result they plan to publish separately. The paper concludes that applying the Gray map to their new Plotkin-optimal codes could yield interesting binary codes, suggesting a potential avenue for further investigation.

The Story of the Perfect Message

Building the New Codes

The Results: Beating the Records

Why This Matters

More like this