Combinatorial List-Size Classification of Linearized Reed–Solomon Codes Across All Sum-Rank Parameter Regimes

Linearized Reed–Solomon (LRS) codes are the standard family of codes meeting the Singleton bound for the sum-rank metric, interpolating between Reed–Solomon codes (Hamming metric extreme) and Gabidulin codes (rank-metric extreme). Puchinger and Rosenkilde (2021) proved that many LRS families have exponentially large decoding lists — for $\ell\in o(n)$ blocks with minimal extension degree directly above the Johnson radius, and for explicit constant-$\ell$ families directly above half the minimum distance — but their results cover only part of the parameter space. The open problem is to complete the combinatorial classification: determine, for every asymptotic scaling of the number of blocks $\ell$, the extension degree $m$, the block length $\eta$, and the dimension $k$ of LRS codes, the precise thresholds (in terms of $\ell,m,\eta,k$ and the relative decoding radius) governing regimes where every full LRS family has exponentially large lists and regimes where some full LRS family admits polynomially bounded lists. The Hamming endpoint of this spectrum coincides with the classical open problem of Reed–Solomon list sizes beyond the Johnson radius, and the rank endpoint already carries both the exponential behavior of square and explicit Gabidulin families and the capacity-achieving positive behavior of random Gabidulin codes over large alphabets.

Background

A linear code of length $n$ over a finite field encodes messages into codewords so that errors introduced by a noisy channel can be corrected. In list decoding, instead of demanding a unique decoded message, one allows the decoder to output a short list of candidate codewords, which makes it possible to correct more errors than unique decoding allows. The list size $L(C,\tau)$ of a code $C$ is the worst-case number of codewords of $C$ inside a ball of radius $\tau$ around an arbitrary received word, where the radius is measured in a chosen metric; if $L(C,\tau)$ grows exponentially with $n$, efficient (polynomial-time) list decoding at that radius is impossible even in principle.

The sum-rank metric interpolates between the two classical metrics of coding theory. A word of length $n=\ell\eta$ over the extension field $\mathbb{F}_{q^m}$ is split into $\ell$ blocks of $\eta$ symbols, and the distance between two words is the sum over the $\ell$ blocks of the rank (over the subfield $\mathbb{F}_q$) of the difference of the corresponding blocks, viewed as matrices. For $\ell=n$ each block has size one and this is the Hamming metric (the usual symbol-error metric); for $\ell=1$ it is the rank metric (errors modeled as low-rank matrices, arising in network coding and storage). Linearized Reed–Solomon (LRS) codes, introduced by Martínez-Peñas in 2018 via evaluation of skew polynomials (polynomials over $\mathbb{F}_{q^m}$ whose multiplication is twisted by the Frobenius map $\sigma(a)=a^q$, i.e. $xa=\sigma(a)x$ for scalars $a$), are the natural analogue of Reed–Solomon (RS) codes for this metric: a codeword is the evaluation of a skew polynomial $f$ of $q$-degree (the analogue of degree for skew polynomials) less than $k$ at $\ell$ collections of $\eta$ points of $\mathbb{F}_{q^m}$, and one requires $\eta\le m$ and $\ell<q$. LRS codes meet the Singleton bound for the sum-rank metric (they are maximum sum-rank distance, MSRD, codes): their minimum sum-rank distance is exactly $d=n-k+1$. For $\ell=n$ they specialize to generalized RS codes and for $\ell=1$ to Gabidulin codes, so the class contains both extremes.

The two extremes behave in opposite ways under list decoding. For RS codes, a classical argument of Johnson guarantees polynomially bounded list sizes up to the relative radius $J_R=1-\sqrt{R}$, where $R=k/n$ is the rate; whether RS codes can have polynomial-size lists at radii beyond $J_R$ is a famous long-standing open problem, with exponential lower bounds known only for RS codes whose dimension grows exponentially slower than the length (Justesen–Høholdt; Ben-Sasson–Kopparty–Radhakrishnan). For Gabidulin codes the first results were negative: Wachter-Zeh, and later Raviv–Wachter-Zeh, showed that square Gabidulin codes with $n=m$ have exponential list sizes already from the Johnson radius, and constructed explicit families (of rate at least $0.2$) with exponential list size directly above half the minimum distance — i.e., directly beyond the unique-decoding radius $\lfloor(d-1)/2\rfloor$, beyond which unique decoding is impossible. These negative results are specific to square or explicitly constructed families: Guo–Xing–Yuan–Zhang (ref. 8) proved that random Gabidulin codes over sufficiently large alphabets attain the optimal generalized Singleton bound for list decoding, so the rank extreme also carries a known positive (polynomial-list) regime at non-minimal extension degree $m=\Omega(n^2)$.

Puchinger and Rosenkilde (2021) initiated the study of the intermediate sum-rank regime. By counting skew polynomials whose evaluations have small sum-rank weight and applying a pigeonhole argument on the top message coefficients, they proved: (i) a general lower bound on $L(C,\tau)$ valid for every LRS code; (ii) for families with number of blocks $\ell\in o(n)$ and minimal extension degree $m=\eta=n/\ell$ and rate $R$, the list size grows faster than $q^{\varepsilon n}$ at radii just above the Johnson radius $1-\sqrt{R}$; (iii) for certain families with $\ell$ a constant fraction of $n$, exponential list size slightly beyond $1-\sqrt{R}$; and (iv) explicit constant-$\ell$ families (of rate at least $0.2$ for $\ell=1$, and asymptotically at least $1-\Theta(1/\sqrt{\ell})$ as the constant $\ell$ grows) whose list size is exponential directly above the unique-decoding radius $\lfloor(d-1)/2\rfloor$. These results indicate Gabidulin-like behavior in the studied regimes, but they leave most of the parameter space unclassified: in particular regimes with non-minimal extension degree $m>\eta$, the sharp thresholds for intermediate block counts, and any positive (polynomial-list) regime for full LRS codes with $1<\ell<n$.

Problem Statement

Determine the combinatorial list-decodability of linearized Reed–Solomon code families over the full parameter spectrum of the sum-rank metric. Concretely: for LRS codes of length $n=\ell\eta$ over $\mathbb{F}_{q^m}$ with block count $\ell<q$, block length $\eta\le m$, extension degree $m$, and dimension $k$ (rate $R=k/n$), characterize the asymptotic regimes of the scaling of $(\ell,m,\eta,k)$ and of the relative decoding radius $\tau/n$, and determine the precise radius thresholds governing (a) the regimes in which every full LRS family has exponentially growing list size $L(C,\tau)$ at that radius and (b) the regimes in which some full LRS family (not a subcode) has polynomially bounded list sizes at that radius. These two conditions are not complementary: the thresholds for (a) and (b) are to be reported separately, and any intermediate regime in which neither condition holds is part of the required classification. This includes in particular: (i) regimes with non-minimal extension degree $m>\eta=n/\ell$, where the volume geometry of sum-rank balls changes; the general Puchinger–Rosenkilde lower bound (their Theorem 4) applies there, and the rank extreme $\ell=1$ is partly settled by the random-Gabidulin list-decoding-capacity result (ref. 8), but no sharp exponential/polynomial threshold is known for general intermediate block counts; (ii) the sharp transition between the constant-$\ell$ families with exponential lists directly above the unique-decoding radius $\lfloor(d-1)/2\rfloor$ (constructed by Puchinger–Rosenkilde, rates up to $1-\Theta(1/\sqrt{\ell})$) and the Johnson-radius behavior established for $\ell\in o(n)$ and some $\ell=\Theta(n)$ families; (iii) whether any family of full LRS codes (not a subcode) with $1<\ell<n$ admits polynomially bounded list sizes beyond half the minimum distance; and (iv) the behavior of the sharp thresholds as the block count approaches the Hamming extreme $\ell=n$, whose endpoint coincides with the classical open problem of whether Reed–Solomon codes can have polynomial-size lists at radii beyond the Johnson radius $J_R=1-\sqrt{R}$. These thresholds are expressed as quantified upper and lower bounds on $L(C,\tau)$ over every asymptotic scaling of the parameters, with matching constructions where the bounds are tight, in the standard $n\to\infty$ asymptotic framework for code families.

References

1. Sven Puchinger and Johan Rosenkilde, "Bounds on List Decoding of Linearized Reed-Solomon Codes", 2021. arXiv:2102.03079, https://arxiv.org/abs/2102.03079 (full version; also in Proc. 2021 IEEE International Symposium on Information Theory (ISIT), DOI: 10.1109/ISIT45174.2021.9517777, https://doi.org/10.1109/ISIT45174.2021.9517777)
2. Umberto Martínez-Peñas, "Skew and linearized Reed–Solomon codes and maximum sum rank distance codes over any division ring", Journal of Algebra 504:587–612, 2018. DOI: 10.1016/j.jalgebra.2018.02.005, https://doi.org/10.1016/j.jalgebra.2018.02.005
3. Antonia Wachter-Zeh, "Bounds on List Decoding of Rank-Metric Codes", IEEE Transactions on Information Theory 59(11):7268–7277, 2013. DOI: 10.1109/TIT.2013.2274653, https://doi.org/10.1109/TIT.2013.2274653
4. Netanel Raviv and Antonia Wachter-Zeh, "Some Gabidulin Codes Cannot Be List Decoded Efficiently at any Radius", IEEE Transactions on Information Theory 62(4):1605–1615, 2016. DOI: 10.1109/TIT.2016.2532343, https://doi.org/10.1109/TIT.2016.2532343
5. J. Justesen and T. Høholdt, "Bounds on list decoding of MDS codes", IEEE Transactions on Information Theory 47(4):1604–1609, 2001. DOI: 10.1109/18.923744, https://doi.org/10.1109/18.923744
6. Eli Ben-Sasson, Swastik Kopparty, and Jaikumar Radhakrishnan, "Subspace Polynomials and Limits to List Decoding of Reed–Solomon Codes", IEEE Transactions on Information Theory 56(1):113–120, 2010. DOI: 10.1109/TIT.2009.2034780, https://doi.org/10.1109/TIT.2009.2034780
7. Venkatesan Guruswami, Carol Wang, and Chaoping Xing, "Explicit List-Decodable Rank-Metric and Subspace Codes via Subspace Designs", IEEE Transactions on Information Theory 62(5):2707–2718, 2016. DOI: 10.1109/TIT.2016.2544347, https://doi.org/10.1109/TIT.2016.2544347 (a subspace design is an explicit collection of subspaces intersecting every low-dimensional subspace in few dimensions, used here to restrict message spaces)
8. Zeyu Guo, Chaoping Xing, Chen Yuan, and Zihan Zhang, "Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric", in Proc. 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), 2024. DOI: 10.1109/FOCS61266.2024.00111, https://doi.org/10.1109/FOCS61266.2024.00111
9. Yang Liu, Anna Baumeister, and Antonia Wachter-Zeh, "On the List-Decodability of Random (Linear) Sum-Rank Metric Codes", 2025. arXiv:2503.10234, https://arxiv.org/abs/2503.10234
10. Thomas Jerkovits, Hannes Bartz, and Antonia Wachter-Zeh, "Randomized Decoding of Linearized Reed-Solomon Codes Beyond the Unique Decoding Radius", in Proc. 2023 IEEE International Symposium on Information Theory (ISIT), 2023. arXiv:2306.04359, https://arxiv.org/abs/2306.04359
11. Hao Chen, "Covering Codes, List-Decodable Codes and Strong Singleton-Like Bounds in the Sum-Rank Metric", 2023. arXiv:2311.07831, https://arxiv.org/abs/2311.07831
12. Kuo Shang, Chen Yuan, and Ruiqi Zhu, "Explicit List-Decodable Linearized Reed-Solomon and Folded Linearized Reed-Solomon Subcodes", 2026. arXiv:2602.05462, https://arxiv.org/abs/2602.05462