🔢 mathematics

Semidefinite and linear programming bounds for sum-rank-metric codes and non-existence results

This paper establishes new sharp upper bounds on the size of sum-rank-metric codes by leveraging semidefinite and linear programming techniques, demonstrating their superiority over existing methods and utilizing them to prove the non-existence of certain optimal and perfect codes.

Original authors: Aida Abiad, Antonina P. Khramova, Sven C. Polak, Ferdinando Zullo

Published 2026-05-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Aida Abiad, Antonina P. Khramova, Sven C. Polak, Ferdinando Zullo

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 trying to pack a suitcase, but the rules for what fits inside are very strange. You aren't just counting how many items you have; you are measuring how "different" they are from each other in a complex, multi-layered way. This is the world of sum-rank-metric codes, a mathematical framework used to organize data for things like sending messages over shaky networks or storing files across many computers.

The main goal of this paper is to answer a simple question: What is the absolute maximum number of items (codewords) you can pack into this suitcase before they start bumping into each other? If they get too close, the data gets corrupted.

Here is a breakdown of the paper's findings using everyday analogies:

1. The Problem: A Hybrid Suitcase

Think of the "sum-rank metric" as a suitcase that has two types of compartments:

The Hamming compartments: Like standard suitcases where you count how many individual socks are missing or swapped.
The Rank compartments: Like suitcases where you care about the pattern of the clothes (e.g., is the whole shirt wrinkled, or just the sleeve?).

The "sum-rank" metric is a hybrid. It counts both the individual missing socks and the pattern wrinkles. The authors want to know the limit: How many outfits can you fit in this hybrid suitcase so that no two outfits are too similar?

2. The Old Tools: Measuring with a Ruler

Before this paper, mathematicians used "rulers" (mathematical bounds) to guess the maximum number of outfits.

The Linear Programming (LP) Bound: Imagine trying to estimate the suitcase's capacity by looking at the average space between items. It's a good guess, but it assumes the items are arranged in a very simple, predictable way.
The Ratio-type Bound: This is another ruler that looks at the "neighbors" of your items. It asks, "If I pick one outfit, how many other outfits are right next to it?"

The paper shows that for some specific types of suitcases (specifically when the "rank" part is the only thing that matters, or when it's just a standard "Hamming" suitcase), these two rulers actually give the exact same answer. They are equivalent.

3. The New Tool: The 3D Scanner (SDP)

The paper's biggest innovation is introducing a new tool called Semidefinite Programming (SDP).

The Analogy: If the old tools (LP) looked at pairs of items (Item A and Item B), the new SDP tool looks at triplets (Item A, Item B, and Item C) all at once.
Why it matters: Imagine trying to fit three people into a small car. If you only look at how much space Person A and Person B need, you might think they fit. But if you look at all three together, you realize they can't all sit comfortably. The SDP tool catches these "group dynamics" that the older tools miss.
The Result: The authors built a computer program to run this new 3D scanner. They found that in many cases, this new tool says, "Actually, you can fit fewer outfits than the old rulers predicted." This means the old rulers were too optimistic. The new tool gives a tighter, more accurate limit.

4. The "Impossible" Suitcases (Non-Existence Results)

The ultimate goal of knowing the maximum limit is to prove that certain "perfect" suitcases cannot exist.

The "Perfect" Code: Imagine a suitcase that is packed so perfectly that there is absolutely no wasted space. Every inch is used, and no two items are too close. In math, this is called a "perfect code."
The "Maximum Distance" Code: Imagine a suitcase where the items are as far apart from each other as physically possible, maximizing the safety margin. This is an "MSRD code."

The authors used their new, sharper rulers (the SDP and the refined LP bounds) to look at specific suitcase sizes. They found that for many of these sizes, the math proves that a "perfect" or "maximum distance" suitcase is impossible to build.

It's like trying to build a house with a specific number of bricks that must form a perfect square. You might think it's possible, but if you measure the bricks precisely, you realize the math doesn't add up—the house simply cannot be built. The paper lists many specific scenarios where these "perfect" codes are mathematically impossible.

Summary

The Setting: A complex way of measuring data errors (sum-rank metric).
The Goal: Find the maximum number of data items you can store safely.
The Innovation: A new mathematical "3D scanner" (SDP) that looks at groups of three items instead of just pairs.
The Discovery: This new scanner proves that the old estimates were too high.
The Conclusion: Because the limits are tighter than we thought, many "perfect" data storage systems that people hoped could exist are actually impossible to create.

The paper doesn't claim to build a new suitcase or fix a specific network today; rather, it provides a more accurate map of the mathematical landscape, showing us exactly where the "perfect" solutions lie (and where they don't).

1. Problem Statement

The paper addresses the fundamental problem in coding theory of determining the maximum size, denoted as $A(q, n, m, d)$ , of a code with a prescribed minimum distance $d$ within the sum-rank metric.

Context: The sum-rank metric generalizes both the Hamming metric (symbol-wise errors) and the Rank metric (rank-type errors). It is crucial for modern applications like multishot network coding, distributed storage, and space-time coding.
Challenge: While bounds exist for Hamming and Rank metrics, the hybrid nature of the sum-rank metric creates unique combinatorial and algebraic phenomena. Existing bounds (e.g., Singleton, Hamming, Plotkin, and classical Delsarte LP) often fail to provide tight upper bounds or fail to rule out the existence of optimal codes (such as Maximum Sum-Rank Distance (MSRD) or Perfect codes) in specific parameter regimes.
Goal: To derive sharper upper bounds using spectral graph theory and optimization techniques (Linear Programming and Semidefinite Programming) and to use these bounds to prove non-existence results for extremal codes.

2. Methodology

The authors employ a multi-faceted approach combining algebraic graph theory, combinatorial optimization, and computational experiments:

Graph Theoretical Framework: They associate the sum-rank metric space $F_q^{n \times m}$ with a graph $\Gamma$ where vertices are codewords and edges represent distance 1. The problem of finding the maximum code size is equivalent to bounding the independence number of this graph.
Spectral Methods: They utilize the eigenvalues of the adjacency matrix of the sum-rank-metric graph to derive bounds.
- Ratio-type Bound: A spectral bound based on the eigenvalues of the graph.
- Lovász Theta Number: An algebraic-graph-theoretical bound.
Linear Programming (LP):
- Delsarte LP: Based on the association scheme of the sum-rank metric, utilizing the second eigenmatrix to constrain the distribution of distances.
- Ratio-type LP: An LP formulation derived from the Ratio-type bound using minor polynomials.
Semidefinite Programming (SDP):
- Schrijver-type SDP: The authors introduce a new SDP bound that extends the Delsarte framework. While Delsarte's LP considers pairwise distances, this SDP incorporates constraints based on triples of codewords (specifically triples containing the zero vector), leveraging the positive semidefiniteness of a matrix encoding these triples.
Computational Verification: The authors use the Julia programming language with the Jordan symmetry reduction package to compute these bounds for various parameters, comparing them against known theoretical bounds.

3. Key Contributions

A. A New Semidefinite Programming (SDP) Bound

The paper introduces a Schrijver-type SDP bound for the sum-rank metric.

Mechanism: It strengthens the pairwise Delsarte LP by imposing constraints on triples of codewords.
Performance: Computational experiments show that this SDP bound strictly improves upon the best existing bounds (including Delsarte LP, Ratio-type, and classical coding bounds) in several parameter regimes.
Hierarchy: The paper establishes the hierarchy: $A(q, n, m, d) \leq \text{SDP} \leq \text{Delsarte LP}$ .

B. Equivalence of LP Bounds in Extremal Regimes

The authors perform a rigorous comparison between the Delsarte LP bound and the Ratio-type LP bound:

Rank-Metric Case ( $t=1$ ): They prove that for bilinear forms graphs (pure rank metric), the optimum of the Delsarte LP is exactly equal to the optimum of the Ratio-type LP. Both equal the Singleton bound $q^{m(n-d+1)}$ .
Hamming Case ( $n_i=m_i=1$ ): They prove that for Hamming graphs, the two bounds are equivalent under specific conditions (e.g., when $q \geq \max\{d, t-d+2\}$ ). They also provide specific counter-examples (e.g., binary Hamming codes) where the bounds are equal but strictly smaller than the Singleton bound, demonstrating that the bounds are tight in those specific cases.

C. Non-Existence Results for Extremal Codes

Using the newly derived and refined bounds, the paper proves the non-existence of certain optimal codes:

MSRD Codes: Codes attaining the Singleton bound. The authors show that for specific parameters (e.g., $m=n=(2, \dots, 2)$ with $t \geq q-1$ and $d=3$ ), the Ratio-type bound is strictly smaller than the Singleton bound, proving MSRD codes do not exist in these regimes.
Perfect Codes: Codes attaining the Sphere-Packing bound with equality.
- They derive explicit conditions involving the volume of balls in the sum-rank metric where perfect codes cannot exist.
- They use congruence arguments (mod $p$ ) to rule out additive perfect codes.
- They show that for $d=3$ , the Ratio-type bound often strictly outperforms the Sphere-Packing bound, thereby proving the non-existence of perfect codes for parameters where $t \not\equiv 1 \pmod q$ .

4. Key Results

Tighter Upper Bounds: The new SDP bound provides the tightest known upper bounds for sum-rank codes in many tested scenarios, outperforming the Delsarte LP.
Theoretical Unification: The proof of equivalence between Delsarte and Ratio-type bounds in the rank-metric case unifies two previously distinct approaches, showing they yield the same structural limit.
Non-Existence Theorems:
- Theorem 5.2/5.3: MSRD codes with $d=3$ do not exist for $m=n=(2, \dots, 2)$ when $t \geq q-1$ .
- Theorem 5.7/5.9: Perfect codes with $d=3$ do not exist in spaces with $m=(m, 1, \dots, 1)$ if $t \not\equiv 1 \pmod q$ .
- Theorem 5.10/5.11: Perfect codes with $d=3$ do not exist in spaces with $m=n=(2, \dots, 2)$ if $t(q+1) \not\equiv 1 \pmod{q^2}$ .

5. Significance

Methodological Advancement: This is the first application of Schrijver-type SDP bounds to the sum-rank metric. It demonstrates that optimization techniques beyond classical LP are necessary to capture the "hybrid" nature of the sum-rank metric effectively.
Resolution of Open Questions: The paper resolves questions regarding the relationship between different spectral and LP bounds in the sum-rank setting, clarifying when they are equivalent and when they diverge.
Practical Impact: By proving the non-existence of perfect and MSRD codes in specific parameter regimes, the paper guides researchers away from futile searches for optimal constructions in those areas and suggests that the known bounds are likely the true limits.
Future Directions: The work highlights the potential of symmetry reduction in SDP to handle larger parameters and suggests that the gap between different bounds in the general sum-rank setting warrants further theoretical investigation.

In summary, the paper significantly advances the understanding of sum-rank-metric codes by introducing powerful new optimization tools (SDP), unifying existing spectral methods, and providing definitive non-existence proofs for optimal codes in previously unresolved cases.