HEXAGONbeta

Average-radius list decoding of random linear matrix codes at rank-metric capacity

Primarily AI-generated textHuman understanding: some partsmath.IT — Information Theorycs.IT — Information Theory

Contributed by Matěj Kripner ↗, Václav Rozhoň ↗, Robert Šámal ↗, Martin Šindelář, Adrián Zámečník

Version 1 / Oct 14, 2026 / CC BY 4.0

Abstract

We show that for every fixed prime power qq and 0<p<10<p<1, a uniformly random Fq\mathbb F_q-linear rank-metric code in Fqn×n\mathbb F_q^{n\times n} of rate (1−p)2−ε(1-p)^2-\varepsilon is, with high probability, average-radius list-decodable at radius pnpn with list size Op,q(1/ε)O_{p,q}(1/\varepsilon). This answers a question of Guruswami, Li and Singhal; the case q=2q=2 was known. The failure probability is explicit and remains small when ε\varepsilon depends on nn with εn2→∞\varepsilon n^2\to\infty. The proof combines a weighted affine extraction, span estimates for matrices from nearby rank shells, and Gaussian summation over rank profiles.

Provenance statement

This work was produced within the Bolzano project (https://bolzano.app), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking. Text origin: primarily AI-generated. Human understanding: some parts of this contribution have been checked and understood by a human. The manuscript received only limited human checking. Automated editorial and literature checks are not human verification. The binary rank-metric average-radius result was already known and is explicitly credited. The claim here is the all-fixed-finite-field square-matrix version, with a bound uniform in the capacity gap. No decoding algorithm, rectangular-model extension, or complete Lean verification is asserted.

Tools used

Bolzano team
Bolzano

References

  1. V. Guruswami, S. Li and M. Singhal, Average-Radius List-Decodability of Random Linear Codes , arXiv:2608.22663v1, 2026. https://arxiv.org/abs/2608.22663v1.arXiv
  2. V. Guruswami and N. Resch, On the list-decodability of random linear rank-metric codes , ISIT 2018, 1505--1509. https://doi.org/10.1109/ISIT.2018.8437698. Theorem and lemma numbering follows arXiv:1710.11516v1 (2017), https://arxiv.org/abs/1710.11516v1.arXivDOI
  3. V. Guruswami, R. Li, J. Mosheiff, N. Resch, S. Silas and M. Wootters, Bounds for list-decoding and list-recovery of random linear codes , IEEE Transactions on Information Theory 68 (2022), 923--939. https://doi.org/10.1109/TIT.2021.3127126. The cited Remark 5.6 is in the authors' April 2020 preprint, https://www.cs.bgu.ac.il/~mosheiff/publications/RLCBounds.pdf.DOI
  4. P. Delsarte, Bilinear forms over a finite field, with applications to coding theory , Journal of Combinatorial Theory, Series A 25 (1978), 226--241. https://doi.org/10.1016/0097-3165(78)90015-8.DOI
  5. E. M. Gabidulin, Theory of codes with maximum rank distance , Problems of Information Transmission 21 (1985), no. 1, 1--12.
  6. R. M. Roth, Maximum-rank array codes and their application to crisscross error correction , IEEE Trans. Inform. Theory 37 (1991), no. 2, 328--336. https://doi.org/10.1109/18.75248.DOI
  7. P. Elias, Error-correcting codes for list decoding , IEEE Trans. Inform. Theory 37 (1991), no. 1, 5--12. https://doi.org/10.1109/18.61123.DOI
  8. A. Wachter-Zeh, Bounds on list decoding of rank-metric codes , IEEE Trans. Inform. Theory 59 (2013), no. 11, 7268--7277. https://doi.org/10.1109/TIT.2013.2274653.DOI
  9. V. Guruswami, J. Hå stad and S. Kopparty, On the list-decodability of random linear codes , IEEE Transactions on Information Theory 57 (2011), 718--725. https://doi.org/10.1109/TIT.2010.2095170. Preprint: https://arxiv.org/abs/1001.1386.DOI
  10. Y. Ding, On list-decodability of random rank metric codes and subspace codes , IEEE Transactions on Information Theory 61 (2015), 51--59. https://doi.org/10.1109/TIT.2014.2371915. Preprint: https://arxiv.org/abs/1401.2693.DOI
Show all 16 referencesShow fewer references
  1. R. Li and M. Wootters, Improved list-decodability of random linear binary codes , IEEE Transactions on Information Theory 67 (2021), 1522--1536. https://doi.org/10.1109/TIT.2020.3041650. Preprint: https://arxiv.org/abs/1801.07839.DOI
  2. A. Rudra and M. Wootters, Average-radius list-recoverability of random linear codes , SODA 2018, 644--662. https://doi.org/10.1137/1.9781611975031.42. Preprint: https://arxiv.org/abs/1704.02420.DOI
  3. Z. Guo, C. Xing, C. Yuan and Z. Zhang, Gabidulin codes achieve list decoding capacity with an order-optimal column-to-row ratio , APPROX/RANDOM 2025, LIPIcs 353 , 43:1--43:20. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2025.43.DOI
  4. Y. Liu, A. Baumeister and A. Wachter-Zeh, On the list-decodability of random (linear) sum-rank metric codes , arXiv:2503.10234v1, 2025. https://arxiv.org/abs/2503.10234v1.arXiv
  5. S. Li, C. Xing, C. Yuan and R. Zhu, Proximity gaps for Gabidulin codes and applications , arXiv:2609.09838v1, September 9, 2026. https://arxiv.org/abs/2609.09838v1.arXiv
  6. R. Goyal and V. Guruswami, Improved analysis of list-decodability of random linear codes: It's all about counting constraints , Electronic Colloquium on Computational Complexity, Report TR26-074, May 12, 2026. https://eccc.weizmann.ac.il/report/2026/074/.link

Version history

  1. v1Submitted by Václav RozhoňInitial depositCurrentOct 14, 2026