On the non-existence of perfect codes in the sum-rank metric

Giuseppe Del Prete, Antonio Roccolano, Ferdinando Zullo · 2025

Read On the non-existence of perfect codes in the sum-rank metric by Giuseppe Del Prete, Antonio Roccolano, Ferdinando Zullo (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-20940.txt.

Introduction

Giuseppe Del Prete, Antonio Roccolano, and Ferdinando Zullo prove in 2025 that perfect codes cannot exist in a certain distance measure used for modern data transmission. The sum-rank metric blends two older measures and matters for network coding spread over several shots and for space-time coding.

A perfect code would tile the whole space with equal balls around its codewords, wasting nothing. Perfect codes under the older measures are fully classified, but the sum-rank case stayed open. The authors study the shape and volume of the balls and show that linear perfect codes are ruled out, closing a gap in coding theory.

Catalog record

CREATORGiuseppe Del Prete, Antonio Roccolano, Ferdinando Zullo
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-20940

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the non-existence of perfect codes in the sum-rank metric Giuseppe Del Prete, Antonio Roccolano, Ferdinando Zullo Abstract . We study perfect codes in the sum-rank metric, a generalization of both the Hamming and rank metrics relevant in multishot network coding and space-time coding. A perfect code attains equality in the sphere-packing bound, corresponding to a partition of the ambient space into disjoint metric balls. While perfect codes in the Hamming and rank metrics are completely classified, the existence of nontrivial perfect codes in the sum-rank metric remains largely open. In this paper, we investigate linear perfect codes in the sum-rank metric. We analyze the geometry of balls and derive bounds on their volumes, showing how the sphere-packing bound applies. For two-block spaces, we determine explicit parameter constraints for the existence of perfect codes. For multiple-block spaces, we establish non-existence results for various ranges of minimum distance, divisibility conditions, and code dimensions. We further provide computational evidence based on congruence conditions imposed by the volume of metric balls. 2020 Mathematics Subject Classification 11T71; 51E20; 94B05 1. Introduction Consider a finite metric space (X,d) . An s -code \mathcal{C} in X is a subset of X with at least two elements such that for every c_{1},c_{2}\in\mathcal{C} with c_{1}\neq c_{2} , we have d(c_{1},c_{2})\geq s . For c\in X and an integer r\geq 0 , we define the ball of radius r centered at c as B_{r}(c)=\{a\in X:d(a,c)\leq r\}. Since d is a metric, one immediately observes that the balls of radius k=\Big\lfloor\tfrac{s-1}{2}\Big\rfloor centered at the elements of an s -code are pairwise disjoint, and their union is contained in X . This yields the bound \sum_{c\in\mathcal{C}}|B_{k}(c)|\leq|X|. If, in addition, the metric d is translation-invariant, then all balls of radius k have the same size, so (1) |\mathcal{C}|\,|B_{k}(c)|\leq|X|,\qquad\text{for some }c\in\mathcal{C}. When d is the Hamming metric and X=\mathbb{F}_{q}^{n} , where {\mathbb{F}}_{q} is a finite field of order q , the bound ( 1 ) is known as the sphere-packing bound (or Hamming bound ), and codes achieving equality in ( 1 ) are called perfect codes . By analogy, we will refer to ( 1 ) as the sphere-packing bound in the general setting, and to codes attaining equality as perfect codes . Examples of linear perfect codes in the Hamming metric are: • trivial codes (i.e., \mathbb{F}_{q}^{n} and the repetition code); • Hamming codes; • the binary and ternary Golay codes of length 23 and 11 , respectively. After a series of works (see [ 11 , 3 , 2 , 28 , 27 , 26 , 23 , 25 ] ), Tietäväinen [ 24 ] completely classified the linear perfect codes in the Hamming metric as precisely those listed above (up to equivalence). Another well-studied case is the rank metric. Taking X=\mathbb{F}_{q}^{m\times n} with d the rank metric, Loidreau [ 13 ] proved that the only linear perfect codes in this setting are the trivial ones. More recently, the situation in which X is a restricted matrix space (i.e., when X is the space of symmetric, Hermitian, or alternating matrices over \mathbb{F}_{q} ) has also been studied; see [ 18 , 17 , 1 ] . This paper is dedicated to the study of perfect codes in the sum-rank metric. Let \mathbb{F}_{q} be a finite field, and consider a vector partitioned into several blocks, where each block is a matrix over \mathbb{F}_{q} . The sum-rank weight of such a vector is defined as the sum of the ranks of all its blocks. Similarly, the sum-rank distance between two vectors is defined as the sum of the ranks of the differences between corresponding blocks. The sum-rank metric generalizes both the Hamming and the rank metrics. If each block consists of a single element, it coincides with the Hamming metric; if there is only one block, it reduces to the rank metric. This metric is particularly useful in coding theory, as it captures both block-wise and rank-based error structures. Applications include multishot network coding , where errors can affect multiple transmissions, and space-time coding in wireless communications, where blocks correspond to different antennas or time slots. For further details, we refer to [ 7 , 15 , 14 ] . Covering properties have been widely studied in both the rank-metric and the sum-rank metric (see [ 4 , 5 , 6 , 29 ] ), and a detailed study of the geometry of balls in the sum-rank metric has been carried out in [ 22 , 20 , 7 , 19 ] . The first study of perfect codes in the sum-rank metric was conducted by Martinez-Peñas in [ 16 ] , where he observed that perfect codes in the Hamming metric can also be viewed as perfect codes in the sum-rank metric. He left as an open question the existence of perfect codes in the sum-rank metric that do not arise from the Hamming metric. To the best of our knowledge, no other perfect codes are known, though a construction of quasi-perfect sum-rank metric codes was recently provided by Chen in [ 10 ] . In this paper, we focus on detecting parameter sets for which linear perfect codes in the sum-rank metric do not exist. After recalling some preliminaries and notation for sum-rank metric codes in Section 2 , in Section 3 we study spheres and balls in the sum-rank metric and describe how the sphere-packing bound appears in this context. We also derive some bounds on the volumes of spheres and balls. In Section 4 , we study perfect codes in \mathbb{F}_{q}^{\,n\times n}\oplus\mathbb{F}_{q}^{\,n\times n} . Following the approach of Loidreau in [ 13 ] , which combines the bounds we have on the volumes of the balls with the Singleton-like bound, we prove that perfect codes in \mathbb{F}_{q}^{n\times n}\oplus\mathbb{F}_{q}^{n\times n} can exist only for specific parameters. Section 5 addresses the case of perfect codes in \underbrace{\mathbb{F}_{q}^{n\times n}\oplus\ldots\oplus{\mathbb{F}}_{q}^{n\times n}}_{t\text{ times}} . The situation here is more complicated, but we are able to provide non-existence conditions when: • the minimum distance is 3 or 4 and q is sufficiently large (see Proposition 5.1 ); • the minimum distance is 5 or 6 and t satisfies certain divisibility conditions (see Proposition 5.2 ); • the minimum distance is 5 or 6 and the dimension of the code is not a multiple of n (see Proposition 5.4 ); • the minimum distance is large enough with respect to t (see Theorems 5.5 and 5.6 ); • q , t , and the minimum distance satisfy certain divisibility conditions (see Theorem 5.8 and Proposition 5.10 ). In Section 6 , since the existence of perfect codes in \underbrace{\mathbb{F}_{q}^{n\times n}\oplus\ldots\oplus{\mathbb{F}}_{q}^{n\times n}}_{t\text{ times}} requires that the volume of a ball of radius \lfloor\frac{d-1}{2}\rfloor (where d is the minimum distance of the code) satisfies a congruential relation modulo the characteristic of the field, we provide some computational results based on this observation. 2. Sum-rank metric codes We fix now the notation that we will use for the whole paper. For us q is a prime power and {\mathbb{F}}_{q} is the finite field with q elements. We will often consider the degree m extension field {\mathbb{F}}_{q^{m}} of {\mathbb{F}}_{q} . Let t be a positive integer. From now on

Read the complete text