🔢 mathematics

Block Tensor Rank of Sum-Rank Metric Codes

This paper introduces the block tensor rank as a new invariant for sum-rank metric codes, proves its additive decomposition across blocks to derive explicit lower bounds (including Singleton and Griesmer variants), and constructs families of codes that attain these bounds while identifying cases where existing codes fall short.

Original authors: Huimin Lao, Huy Pham, Hoang Ta, Van Khu Vu

Published 2026-06-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Huimin Lao, Huy Pham, Hoang Ta, Van Khu Vu

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 very specific set of luggage into a truck. But this isn't just any truck; it's a truck with several distinct, separate compartments (blocks).

In the world of data transmission (coding theory), we often need to send messages that are robust against errors. To do this, we turn our messages into "codewords." In this paper, the authors are studying a special type of codeword called a Sum-Rank Code.

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

1. The Problem: Packing the Luggage

Think of a Sum-Rank code as a collection of suitcases. Each suitcase is actually a grid of numbers (a matrix).

The Old Way: Sometimes, we treat the whole grid as one big messy pile (Rank Metric). Other times, we treat every single number in the grid as its own tiny item (Hamming Metric).
The New Way (Sum-Rank): We treat the grid as a set of distinct blocks. The "weight" or "size" of a suitcase is calculated by adding up the complexity of each individual block.

The authors wanted to answer a specific question: What is the most efficient way to build these suitcases?

2. The New Tool: "Block-Simple" Bricks

To build a suitcase, you need building blocks.

In the old "Rank" world, you could build anything using "rank-one" bricks (simple, flat sheets of numbers).
In the "Sum-Rank" world, the authors realized you can't just throw a brick anywhere. You must use "Block-Simple" bricks.
- The Analogy: Imagine your truck has 3 separate compartments. A "Block-Simple" brick is a sheet of material that fits perfectly inside only one of those compartments. It cannot stretch across two compartments at once.

The "Block Tensor Rank" is simply the minimum number of these specific bricks you need to stack together to build every possible suitcase in your collection. If you need 10 bricks, the rank is 10. If you need 100, the rank is 100. The lower the number, the more "economical" or efficient the code is.

3. The Big Discovery: The "Add-Up" Rule

The most important finding in the paper is a surprising rule about how to count these bricks.

The authors proved that you don't need to look at the whole truck at once to figure out the brick count. Instead, you can look at each compartment separately:

Look at Compartment 1. How many bricks does it take to build the stuff inside?
Look at Compartment 2. How many bricks does it take?
The Magic: The total number of bricks for the whole truck is just the sum of the bricks needed for each compartment.

Why this matters: It turns a giant, scary, complicated math problem into a bunch of smaller, easier problems. You solve the small ones, add them up, and you have your answer.

4. The "Best Case" Scenarios (The Gold Standards)

The paper sets up two "Gold Standards" for efficiency. If a code hits these targets, it is considered perfect in its own way.

The "Singleton" Standard (The BTR Code): This is the theoretical minimum number of bricks you should need based on the size of the message and how much protection you want. If you hit this number, you are a "Block Tensor Rank Minimum" (BTR) code. It's like packing your luggage so perfectly that you use the absolute fewest boxes possible.
The "Griesmer" Standard (The Extremal Code): Sometimes, due to the rules of the universe (mathematics), you can't hit the Singleton target. The Griesmer bound is a slightly higher, but still very strict, target. If you hit this, you are "Block-Tensor-Rank-Extremal."

The authors showed how to build codes that hit these gold standards. They did this by taking a known, perfect code from a simpler world (Hamming codes) and "lifting" it up into this new block world.

5. The Twist: Not All Perfect Codes are Perfect Here

The paper also discovered something interesting about codes that are already famous for being "perfect" in a different sense (called MSRD codes).

Some codes are famous for having the maximum amount of data they can hold (MSRD).
The authors found that being "Maximum Data" does not automatically mean you are "Minimum Bricks" (BTR).
In some cases, a code can hold a lot of data but still require a huge number of bricks to build, making it inefficient by this new "Block Tensor" measure. They even calculated exactly how much more inefficient some famous codes are.

Summary

In short, the authors invented a new way to measure the "efficiency" of complex data codes.

They defined a new unit of measurement: Block-Simple Bricks.
They proved that to count the bricks, you just add up the counts for each separate block.
They built new, highly efficient codes that use the fewest bricks possible.
They showed that just because a code is "big" (holds lots of data), it doesn't mean it's "efficient" (uses few bricks).

This work helps engineers understand the hidden structure of these codes, potentially leading to better ways to store and send data in networks, though the paper itself focuses strictly on the math of the structure rather than specific real-world applications.

Technical Summary: Block Tensor Rank of Sum-Rank Metric Codes

Problem Statement
Sum-rank metric codes generalize both Hamming-metric and rank-metric codes by representing codewords as tuples of matrices partitioned into fixed blocks, with weight defined as the sum of the ranks of these blocks. While the tensor-rank invariant for rank-metric codes (the minimum number of rank-one matrices spanning a code) is well-studied, a corresponding invariant adapted to the block structure of sum-rank codes has not been systematically developed. The paper addresses the challenge of defining and computing a "block tensor rank" for sum-rank codes that respects the block decomposition, distinguishing it from support-theoretic invariants and existing equivalence-testing tensor approaches.

Methodology and Definitions
The authors introduce the concept of block-simple tensors, defined as rank-one matrices supported entirely within a single block of the sum-rank tuple. The block tensor rank of a sum-rank code $C$ , denoted $btrk(C)$, is defined as the smallest number of block-simple tensors whose linear span contains $C$ .

The core methodological approach involves:

Generator Tuples: Associating each code with a tuple of 3-tensors (one per block) that generate the code via linear maps.
Blockwise Decomposition: Proving that the block tensor rank of the entire code is the sum of the tensor ranks of its individual block projections. This reduces the global problem to standard tensor-rank problems on rank-metric codes.
Coordinate-Code Argument: Constructing a linear block code over the base field $\mathbb{F}_q$ (the "coordinate code") by mapping codewords to their coefficients relative to a block-simple basis. This allows the transfer of classical Hamming-metric bounds to the block tensor rank setting.

Key Contributions and Results

Structural Decomposition Theorem: The paper establishes that $btrk(C) = \sum_{i=1}^t trk(\pi_i(C))$ , where $\pi_i(C)$ is the projection of the code onto the $i$ -th block and $trk$ denotes the standard tensor rank. This identity implies that computing the block tensor rank separates into independent tensor-rank computations for each block.
Lower Bounds: Two complementary lower bounds are derived:
- Projection-wise Bound: Derived directly from the decomposition theorem, stating $btrk(C) \ge \sum N_q(k_i, d_i)$ , where $k_i$ and $d_i$ are the dimension and minimum rank distance of the $i$ -th projection.
- Coordinate-Code Bound: Derived from the global parameters $(k, d)$ of the code, stating $btrk(C) \ge N_q(k, d)$ , where $N_q(k, d)$ is the minimum length of a linear code with dimension $k$ and minimum Hamming distance $d$ .
- Singleton and Griesmer Refinements: By applying classical Singleton and Griesmer bounds to $N_q(k, d)$ , the authors derive the Singleton coordinate-code bound ( $btrk(C) \ge k + d - 1$ ) and the Griesmer coordinate-code bound ( $btrk(C) \ge G_q(k, d)$ ).
Extremal Notions:
- BTR Codes: Codes attaining the Singleton coordinate-code bound ($btrk(C) = k + d - 1$).
- Block-Tensor-Rank-Extremal Codes: Codes attaining the sharper bound $btrk(C) = N_q(k, d)$ .
Constructions:
- Block-Diagonal Lifting: A general method is introduced to construct sum-rank codes by lifting classical linear block codes (the "backbone") into matrix blocks via diagonal maps.
- BTR Families: Explicit constructions of BTR codes are provided using MDS backbones (e.g., Reed–Solomon codes) under specific parameter regimes (Fat-block, Uniform MDS-backbone, and Pooling regimes).
- Griesmer-Optimal Families: Using Griesmer-optimal backbones (e.g., Simplex and MacDonald codes), the authors construct codes that attain the Griesmer coordinate-code bound, which are extremal but not necessarily BTR when $G_q(k, d) > k + d - 1$ .
Comparison with MSRD Codes: The paper demonstrates that BTR optimality and Maximum Sum-Rank Distance (MSRD) optimality are distinct. Specifically, in the uniform MDS-backbone lifting regime, codes cannot simultaneously achieve the BTR threshold and the uniform MSRD dimension. Furthermore, the authors apply their projection-gap criterion to existing constructions (Chen [19] and Lao et al. [20]), showing that while some are close to the BTR threshold, others (like certain MSRD codes) exhibit large gaps due to high tensor ranks in their block projections.

Significance and Claims
The paper claims to provide the first systematic framework for analyzing sum-rank codes through the lens of block-adapted tensor rank. Its significance lies in:

Unification: Connecting sum-rank coding theory with tensor decomposition theory and classical Hamming-metric bounds.
Computational Reduction: The blockwise decomposition theorem simplifies the calculation of block tensor rank to known rank-metric tensor rank problems.
New Optimality Criteria: Introducing BTR and block-tensor-rank-extremal codes as new classes of optimal codes, distinct from MSRD codes.
Structural Insight: The authors suggest that block tensor rank serves as a measure of the "algebraic economy" of a code. They posit that this invariant could be relevant for distinguishing structured code families from random ones in post-quantum cryptography, though they do not propose specific cryptographic schemes or attacks.

The work concludes by identifying open problems, including the classification of parameter regimes for BTR existence beyond lifting constructions and the potential use of block tensor rank as a structural distinguisher in code-based cryptography.