🔢 mathematics

Embedding linear codes over Z4 into self-orthogonal codes

This paper investigates the self-orthogonal embedding problem for linear codes over $\mathbb{Z}_4$ by establishing tight bounds and exact lengths for shortest embeddings, completely classifying the binary case, providing a construction algorithm for free codes, and discovering twelve new codes with improved minimum Lee distances.

Original authors: Junmin An, Jon-Lark Kim, San Ling

Published 2026-06-09

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Junmin An, Jon-Lark Kim, San Ling

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 an architect designing a special kind of digital fortress. In the world of coding theory, these "fortresses" are codes—mathematical structures used to send messages reliably. Some codes are "self-orthogonal," which is a fancy way of saying the code has a built-in symmetry where every part of the message is perfectly balanced against every other part. This symmetry is incredibly useful for creating stronger, more secure codes.

However, you often start with a code that isn't perfectly balanced. The problem this paper tackles is: "How many extra bricks (columns) do we need to add to our existing, unbalanced code to make it perfectly symmetrical (self-orthogonal) without making the structure unnecessarily huge?"

The authors are working with a specific type of digital material called $\mathbb{Z}_4$ . Think of $\mathbb{Z}_4$ as a four-sided die (with faces 0, 1, 2, 3) instead of the usual two-sided coin (0 and 1) used in standard binary codes.

Here is a breakdown of their journey and discoveries using simple analogies:

1. The "Shadow" Strategy (Residue Codes)

The authors realized that solving the difficult puzzle of balancing the four-sided $\mathbb{Z}_4$ codes is easier if you look at their "shadows."

The Analogy: Imagine your $\mathbb{Z}_4$ code is a complex 3D sculpture. If you shine a light on it, it casts a 2D shadow on the wall. This shadow is called the residue code (a standard binary code).
The Discovery: The paper proves that to figure out the minimum number of bricks needed to balance the 3D sculpture, you first need to figure out how to balance its 2D shadow. Specifically, they found that if the shadow is balanced in a very strict way (called "doubly even"), you can often use that solution to balance the original 3D sculpture perfectly.

2. The "Double-Even" Challenge

Before they could solve the $\mathbb{Z}_4$ problem, they had to solve a harder version of the binary problem: making a code "doubly even."

The Analogy: In a normal balanced code, the weight of every message is an even number (like 2, 4, 6). In a "doubly even" code, the weight must be a multiple of 4 (like 4, 8, 12).
The Result: They completely mapped out exactly how many extra bricks are needed to turn any binary code into this "doubly even" state. They found that you almost never need more than two extra bricks beyond the absolute minimum required for a normal balance. They created a precise rulebook for every possible scenario.

3. The Tight Bounds (The "Goldilocks" Zone)

For the $\mathbb{Z}_4$ codes, the authors established a "Goldilocks" range for the number of extra bricks needed.

The Analogy: If you have a code of a certain size, the number of extra bricks needed isn't a single fixed number, but it falls within a very tight range.
The Finding: They proved that the number of extra bricks is at least the size of the "imbalance" in the code, and at most three times that size plus a small constant. In many specific cases (like when the "shadow" code is already very well-behaved), they found the exact number needed, not just a range.

4. The "Preparata" Success Story

To prove their theory works, they applied it to a famous family of codes called Preparata codes.

The Result: Just like solving a specific riddle, they calculated the exact number of bricks needed to make these specific $\mathbb{Z}_4$ codes perfectly symmetrical. This confirmed their "shadow" strategy works in real-world scenarios.

5. The Construction Algorithm (The "Lego Kit")

Finally, they didn't just stop at theory; they built a tool (an algorithm) to actually construct these codes.

How it works: If you have a code where the "shadow" solution matches the 3D solution, their algorithm acts like a precise Lego instruction manual. It takes your existing code and tells you exactly which extra columns to add to make it self-orthogonal.
The Outcome: Using this manual, they built 12 new codes that are "stronger" (have higher minimum distances, meaning they can detect more errors) than any previously known codes of the same size in a major database (Aydin's database).

Summary

In short, this paper is a guidebook for upgrading digital codes. The authors discovered that to upgrade a complex four-sided code, you should first look at its simpler two-sided "shadow." They figured out the exact rules for balancing the shadow, which in turn tells you exactly how to balance the complex code. Using these rules, they built a method to create 12 new, superior codes that were previously unknown.

Technical Summary: Embedding Linear Codes over $\mathbb{Z}_4$ into Self-Orthogonal Codes

Problem Statement
The paper addresses the problem of embedding a given linear code $C$ over the ring $\mathbb{Z}_4$ into a self-orthogonal code by adding the minimum number of columns. The central objective is to determine the length of the shortest such embedding, denoted as $n_s(C)$ , and to provide explicit construction methods. This problem is motivated by the need to construct new, high-performance codes, particularly since self-orthogonal codes over $\mathbb{Z}_4$ can be expanded into self-dual codes, which are crucial for constructing optimal binary nonlinear codes (e.g., Kerdock, Preparata, Goethals) via the Gray map.

Methodology
The authors' approach relies on a reduction strategy that connects codes over $\mathbb{Z}_4$ to binary codes via residue and torsion codes.

Binary Reduction: The study first investigates the shortest doubly even self-orthogonal embedding for binary linear codes. The length of this embedding is denoted as $n_{de}(C)$ . The authors establish that $n_{de}(C)$ is closely related to the shortest self-orthogonal embedding length $n_s(C)$ , differing by at most 2.
Classification of Binary Cases: The paper completely classifies the exact length $n_{de}(C)$ $n_{d e} (C)$ for all binary linear codes. This involves:
- Analyzing the hull of the code, $\text{Hull}(C)$ .
- Distinguishing between even and odd-like codes.
- Utilizing quadratic forms and Arf invariants to determine the number of doubly even codewords, which dictates whether the embedding length increases by 0, 1, or 2 relative to $n_s(C)$ .
- Specifically determining the lengths for extended Hamming codes.
Lifting to $\mathbb{Z}_4$ : For a code $C$ over $\mathbb{Z}_4$ , the authors derive bounds on $n_s(C)$ based on the type of the code generated by $GG^T$ (where $G$ is the generator matrix). They prove that if the residue code $\text{Res}(C)$ is Linear Complementary Dual (LCD) or satisfies specific hull conditions, the shortest self-orthogonal embedding length of $C$ is exactly equal to the shortest doubly even self-orthogonal embedding length of $\text{Res}(C)$ .
Algorithmic Construction: An algorithm is presented to construct all possible shortest self-orthogonal embeddings for free codes over $\mathbb{Z}_4$ when the length condition $n_s(C) = n_{de}(\text{Res}(C))$ holds. This involves lifting binary embeddings and solving specific matrix equations over $\mathbb{Z}_4$ to ensure orthogonality.

Key Contributions and Results

Binary Classification: The paper provides a complete classification of the exact length of the shortest doubly even self-orthogonal embedding for any binary linear code, covering even and odd-like cases, and utilizing the Arf invariant of associated quadratic forms.
Bounds for $\mathbb{Z}_4$ : Tight bounds are established for the length of the shortest self-orthogonal embedding of a code over $\mathbb{Z}_4$ . Specifically, for a code with generator matrix $G$ where $\langle GG^T \rangle$ has type $4^a 2^b$ , the length $n_s(C)$ satisfies $n + a + b \leq n_s(C) \leq n + 3a + 2b$ .
Exact Lengths for Specific Codes: Under the condition that the residue code is LCD, the authors determine the exact length of the shortest self-orthogonal embedding for the quaternary Preparata codes. This length is shown to be identical to that of the corresponding binary extended Hamming codes.
Construction Algorithm: A constructive algorithm is provided for generating shortest self-orthogonal embeddings for free codes over $\mathbb{Z}_4$ satisfying the residue code condition.
New Codes: Applying this algorithm to codes from the BKLC (Best Known Linear Codes) database and Aydin's $\mathbb{Z}_4$ code database, the authors identified twelve linear codes over $\mathbb{Z}_4$ with minimum Lee distances strictly higher than those of existing codes in Aydin's database for the same length and rank.

Significance
The paper claims significance in shifting the focus of self-orthogonal embedding problems from finite fields to rings, specifically $\mathbb{Z}_4$ . By establishing a direct link between the embedding problem over $\mathbb{Z}_4$ and the doubly even embedding problem over binary fields, the authors provide a systematic method to determine exact embedding lengths rather than just bounds. This is particularly valuable for constructing optimal self-dual codes over $\mathbb{Z}_4$ , which serve as the foundation for important families of binary nonlinear codes. The work demonstrates that for specific classes of codes (such as those with LCD residue codes), the complex problem over the ring can be solved exactly by solving the corresponding problem over the binary field. The discovery of codes with improved minimum Lee distances validates the practical utility of the proposed construction method.