Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric

Gabidulin codes, serving as the rank-metric counterpart of Reed-Solomon codes, constitute an important class of maximum rank distance (MRD) codes. However, unlike the fruitful positive results about the list decoding of Reed-Solomon codes, results concerning the list decodability of Gabidulin codes in the rank metric are all negative so far. For example, in contrast to Reed-Solomon codes, which are always list decodable up to the Johnson bound in the Hamming metric, Raviv and Wachter-Zeh (IEEE TIT, 2016 and 2017) constructed a class of Gabidulin codes that are not even combinatorially list decodable beyond the unique decoding radius in the rank metric. Proving the existence of Gabidulin codes with good combinatorial list decodability in the rank metric has remained a long-standing open problem. In this paper, we resolve the aforementioned open problem by showing that, with high probability, random Gabidulin codes over sufficiently large alphabets attain the optimal generalized Singleton bound for list decoding in the rank metric. In particular, they achieve list decoding capacity in the rank metric. Our work is significantly influenced by the recent break-throughs in the combinatorial list decodability of Reed-Solomon codes, especially the work by Brakensiek, Gopi, and Makam (STOC 2023). Our major conceptual and technical contributions, which may hold independent interest, consist of the following: (1) We initiate the study of “higher order MRD codes” and provide a novel unified theory, which runs parallel to the theory of “higher order MDS codes” developed by Brakensiek, Gopi, and Makam. (2) We prove a natural analog of the GM-MDS theorem, proven by Lovett (FOCS 2018) and Yildiz and Hassibi (IEEE TIT, 2019), which we call the GM-MRD theorem. In particular, our GMMRD theorem for Gabidulin codes is strictly stronger than the GM-MDS theorem for Gabidulin codes proven by Yildiz and Hassibi.