🔢 mathematics

Strong Singleton-Like Bounds, Quasi-Perfect Codes and Distance-Optimal Codes in the Sum-Rank Metric

This paper advances the theory of sum-rank metric codes by deriving new upper bounds on their parameters through connections with Hamming metric covering codes, and by presenting explicit constructions of distance-optimal and quasi-perfect codes, including infinite families and improved Singleton-like bounds.

Original authors: Chao Liu, Hao Chen, Qinqin Ji, Ziyan Xie, Dabin Zheng, Yongbo Xia

Published 2026-02-19

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Chao Liu, Hao Chen, Qinqin Ji, Ziyan Xie, Dabin Zheng, Yongbo Xia

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.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 running a massive, high-speed delivery network. In this network, packages aren't just single boxes; they are complex crates containing multiple items. Sometimes, a whole row of items in a crate gets damaged, or a whole crate gets lost. Your job is to design a system of "backup codes" (like a secret language or a checksum) that can detect and fix these errors, no matter how the damage happens.

This paper is about building better, smarter backup systems for a specific type of complex delivery network called the Sum-Rank Metric.

Here is the breakdown of what the authors did, using simple analogies:

1. The Problem: The "Multi-Crate" Delivery System

In the old days (the Hamming Metric), we only worried about single letters getting swapped in a word (like "HELLO" becoming "HEXLO"). We had great rules for fixing those.

But in modern tech (like sending data to many satellites or storing files across many servers), data comes in matrices (grids of numbers).

The Sum-Rank Metric is a way of measuring errors in these grids. It counts how many rows or columns are messed up, not just individual numbers.
The Challenge: We didn't have good rules for how much data we could send before it became too risky, or how to build the most efficient "safety nets" for these grids.

2. The First Breakthrough: The "Master Key" (Covering Codes)

The authors realized they could build a safety net for these complex grids by using safety nets they already knew how to build for simple words.

The Analogy: Imagine you have a master key that opens a simple lock. The authors figured out how to combine $m$ of these simple keys to create a "super-key" that opens a complex, multi-tumbler lock.
What they did: They took existing, well-understood error-correcting codes (the simple keys) and stitched them together to create new codes for the complex grid system.
The Result: They proved that if you know how to cover a small room with blankets, you can figure out exactly how many blankets you need to cover a giant warehouse. This gave them new, tighter limits on how much data can be sent safely.

3. The Second Breakthrough: The "Super Tight" Rules (Strong Singleton Bounds)

In coding theory, there's a famous rule called the Singleton Bound. It's like a speed limit sign saying, "You can't go faster than X miles per hour." For a long time, this was the best we knew.

The Discovery: The authors found that for very long delivery routes (large block lengths), the old speed limit was too loose. It was like saying "You can drive 100 mph," when in reality, the road conditions only allow 60 mph.
The Metaphor: They built a "Strong Singleton Bound." Think of this as a new, stricter traffic law that applies specifically to long highways. It tells us exactly how much data we can pack into a message before it becomes impossible to fix errors. Their new rule is much stricter and more accurate than the old one.

4. The Third Breakthrough: The "Perfect" and "Almost Perfect" Packages

The authors wanted to build codes that are as efficient as possible.

Perfect Codes: Imagine a puzzle where every single piece fits perfectly with no gaps. In coding, this means every possible error pattern is covered exactly once. These are rare and hard to find.
Quasi-Perfect Codes: These are the "next best thing." They have tiny gaps, but they cover almost everything perfectly.
Distance-Optimal Codes: These are the most efficient codes possible for a given size. You can't make them smaller without losing the ability to fix errors.

What they built:

They created infinite families of these "Quasi-Perfect" codes for specific grid sizes (like $2 \times m$ matrices).
They built "Distance-Optimal" codes for $2 \times 2$ and $s \times s$ grids.
The Magic Trick: They used Cyclic Codes (codes that work like a rotating dial) from the simple world to build these complex, high-performance grid codes.

5. The Fourth Breakthrough: The "Lego Block" Method (Plotkin Sum)

Finally, they introduced a way to combine two existing codes to make a bigger, better one.

The Analogy: Imagine you have two Lego structures. The Plotkin Sum is a technique where you take the first structure, duplicate it, and attach the second structure to the copy in a specific way.
The Result: This creates a new, larger structure that is stronger than the sum of its parts. They used this to create even more efficient codes for binary (0s and 1s) systems.

Why Does This Matter?

This isn't just abstract math. These codes are the backbone of:

Network Coding: Sending data efficiently across the internet.
Space-Time Coding: Sending signals to satellites and cell towers without losing them.
Distributed Storage: Saving your photos and files across many different hard drives so that if one breaks, you don't lose anything.

In Summary:
The authors took the tools we use for simple data (letters and words) and upgraded them to handle complex data (grids and matrices). They built better safety nets, set stricter and more accurate speed limits for data transmission, and invented new ways to combine these safety nets to make our digital world more reliable and efficient. They essentially said, "We thought we knew the limits of how much data we could send safely, but we found a way to push those limits further."

1. Problem Statement

The paper addresses the fundamental challenges in coding theory within the sum-rank metric, a metric space that generalizes both the Hamming metric and the rank metric. Sum-rank codes are crucial for applications in multishot network coding, space-time coding, and distributed storage.

The specific problems tackled are:

Lack of Tight Bounds: Existing upper bounds on code sizes (like the classical Singleton-like bound) are often loose, particularly for large block lengths. There is a need for "Strong Singleton-like bounds" that provide tighter constraints.
Construction of Optimal Codes: There is a scarcity of explicit constructions for distance-optimal codes (codes that cannot have their minimum distance increased without reducing size) and quasi-perfect codes (codes with a covering radius exactly one unit larger than the packing radius) in the sum-rank metric, especially for matrix sizes larger than $1 \times 1$ .
Covering Code Theory: The relationship between covering codes in the Hamming metric and the sum-rank metric is not fully explored, specifically regarding how to derive bounds on block length functions and code sizes in the sum-rank setting.

2. Methodology

The authors employ a combination of algebraic constructions, combinatorial arguments, and metric generalizations:

Construction via Hamming Codes: The core methodology involves constructing sum-rank codes from existing codes in the Hamming metric.
- Covering Code Construction: They define a mapping where $m$ Hamming codes over $\mathbb{F}_{q^m}$ are combined to form a sum-rank code over $\mathbb{F}_q$ with matrix size $m \times m$ . This relies on an isomorphism between the matrix space and a direct sum of vector spaces.
- Sum-Rank Code Construction: They utilize cyclic codes (specifically BCH codes and Reed-Solomon codes) in the Hamming metric to generate sum-rank codes with specific minimum distances.
Block Length Functions: The authors introduce and analyze block length functions $\ell_{q,m}(r, R)$ for sum-rank covering codes, generalizing the concept from Hamming metric covering codes.
Plotkin Sum: They adapt the Plotkin sum construction (common in Hamming metric) to the sum-rank metric to combine two codes and generate new codes with improved parameters.
Combinatorial Volume Analysis: To prove distance-optimality, they calculate the volume of balls in the sum-rank metric ( $V_{sr}(q, r)$ ) and compare them against the total space size to show that no larger code with the same distance can exist.

3. Key Contributions and Results

A. Strong Singleton-Like Bounds

The paper derives new upper bounds on the size of sum-rank codes that are significantly tighter than the classical Singleton-like bound when block lengths are large.

Method: By constructing covering codes from binary BCH codes and analyzing their covering radii, the authors prove that for large block lengths $t$ , the size of a code $|C|$ is bounded by $2^{m^2(t-ne)}$ (for specific distance parameters), which is much smaller than the classical bound.
Significance: This establishes that for large block lengths, the gap between the theoretical maximum size and the actual achievable size is larger than previously thought, providing a more accurate limit for code design.

B. Quasi-Perfect Sum-Rank Codes

The authors present explicit constructions of infinite families of quasi-perfect sum-rank codes.

Matrix Size $2 \times m$ : Using a combination of a Hamming code and a trivial cyclic code over $\mathbb{F}_{q^m}$ , they construct a sum-rank code with block length $t = \frac{q^{mu}-1}{q^m-1}$ , matrix size $2 \times m$ , minimum distance 4, and covering radius 2.
Matrix Size $2 \times 2$ (Binary): By leveraging known quasi-perfect codes over $\mathbb{F}_4$ and applying the specific sum-rank construction, they create binary quasi-perfect codes with matrix size $2 \times 2$ and minimum distance 4.
Implication: Since quasi-perfect codes with even minimum distances are automatically distance-optimal, these constructions provide a rich source of optimal codes.

C. Distance-Optimal Codes

The paper provides explicit constructions of distance-optimal codes with minimum sum-rank distance 4:

Cyclic Constructions: They construct infinite families of distance-optimal $q$ $q$ -ary cyclic sum-rank codes with matrix sizes $s \times s$ $s \times s$ and $2 \times 2$ $2 \times 2$ .
- For $s \times s$ , they use cyclic codes with defining sets involving cyclotomic cosets to ensure minimum distance 4.
- For $2 \times 2$ , they construct a code with block length $q^4-1$ and Singleton defect 4.
Almost MSRD Codes: They construct "almost MSRD" (Maximum Sum-Rank Distance) codes with block lengths up to $q^2$ and Singleton defect 2. This is a significant improvement over previous MSRD constructions which were limited to block lengths of $q-1$ .

D. Plotkin Sum Application

The authors demonstrate that the Plotkin sum can be effectively used in the sum-rank metric.

They show that taking the Plotkin sum of a trivial code and a distance-optimal code yields a new distance-optimal code with doubled block length ( $2t$ ) while maintaining the minimum distance (or improving it). This provides a recursive method to generate larger optimal codes.

4. Significance and Impact

Theoretical Advancement: The paper bridges the gap between Hamming metric covering code theory and the sum-rank metric, providing the first strong Singleton-like bounds that outperform classical bounds for large block lengths.
Practical Construction: It moves beyond existence proofs to provide explicit constructions for optimal codes. This is vital for practical implementation in network coding and distributed storage systems where specific matrix sizes and distances are required.
New Families of Codes: The introduction of infinite families of quasi-perfect and distance-optimal codes with parameters (like block lengths up to $q^2$ or $q^4-1$ ) that were previously unattainable or unknown expands the toolkit for coding theorists.
Optimality Verification: The rigorous volume arguments used to prove distance-optimality set a standard for verifying the efficiency of sum-rank codes in future research.

In summary, this paper significantly advances the theory of sum-rank codes by tightening theoretical bounds and providing concrete, optimal code constructions that are directly applicable to modern communication and storage systems.