\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern,amsmath,amssymb,amsthm,mathtools,microtype,needspace}
\usepackage[a4paper,hmargin=23mm,vmargin=25mm]{geometry}
\usepackage{xcolor}
\usepackage{hyperref}
\hypersetup{pdftitle={Average-radius list decoding of random linear matrix codes at rank-metric capacity},pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{question}[theorem]{Question}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}
\newcommand{\F}{\mathbb F}
\newcommand{\C}{\mathcal C}
\newcommand{\qbinom}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\spanF}{span}
\DeclareMathOperator{\aff}{aff}
\DeclareMathOperator{\col}{col}
\DeclareMathOperator{\supp}{supp}
\title{Average-radius list decoding of random linear matrix codes\\at rank-metric capacity\thanks{This work was produced within the Bolzano project (\url{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.}}
\author{Mat\v{e}j Kripner \qquad V\'aclav Rozho\v{n} \qquad Robert \v{S}\'amal\\[0.4em]
Martin \v{S}indel\'a\v{r} \qquad Adri\'an Z\'ame\v{c}n\'ik}
\date{}

% Collection typography; mathematical statements and proofs are unchanged.
\definecolor{BolzanoInk}{HTML}{24445C}
\hypersetup{colorlinks=true,linkcolor=BolzanoInk,citecolor=BolzanoInk,
  urlcolor=BolzanoInk,pdfauthor={Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník},pdflang={en-US}}
\urlstyle{same}
\setlength{\emergencystretch}{1em}
\let\BolzanoBibliography\thebibliography
\renewcommand{\thebibliography}[1]{\BolzanoBibliography{#1}\raggedright}
\begin{document}
\maketitle
\begin{abstract}
We show that for every fixed prime power $q$ and $0<p<1$, a uniformly
random $\F_q$-linear rank-metric code in $\F_q^{n\times n}$ of rate
$(1-p)^2-\varepsilon$ is, with high probability, average-radius
list-decodable at radius $pn$ with list size $O_{p,q}(1/\varepsilon)$.
This answers a question of Guruswami, Li and Singhal; the case $q=2$
was known. The failure probability is explicit and remains small when
$\varepsilon$ depends on $n$ with $\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.
\end{abstract}

\section{Introduction}
\subsection{Background and the source problem}
Rank measures the number of independent error directions, rather than
the number of changed matrix entries: a nonzero outer product $uv^T$
has rank one even when every entry is nonzero. This geometry leads to
the rank metric, studied in Delsarte's work on bilinear
forms~\cite{Delsarte}.
Let $q$ be a prime power and let $V_n=\F_q^{n\times n}$. The rank
metric on $V_n$ is $d(X,Y)=\rank(X-Y)$, and a linear matrix code is
an $\F_q$-linear subspace $\C\le V_n$. Its rate is
$\dim_{\F_q}\C/n^2$. Ordinary list decoding controls the number
of codewords in a ball about any center. Average-radius list decoding
controls the average distance of a list from its center, so it also
excludes lists with some members outside the prescribed ball.

\begin{definition}[Average-radius convention]\label{def:average}
A code $\C\subseteq V_n$ has no bad average-radius list of size $L$
at radius $pn$ if every $Y\in V_n$ and every $L$ distinct codewords
$c_1,\ldots,c_L\in\C$ satisfy
\begin{equation}\label{eq:goodlist}
 \sum_{i=1}^L\rank(c_i-Y)>pnL.
\end{equation}
Here $L$ is the \emph{forbidden-list size}. In the convention of
\cite[Section 1]{GLS}, this is $(p,L-1)$-average-radius
list-decodability, with normalized rank distance in place of normalized
Hamming distance.
\end{definition}
For square matrices, the exponent of a rank ball of relative radius $p$
is $f(p)n^2$, where $f(p)=2p-p^2$. The corresponding capacity rate
is $1-f(p)=(1-p)^2$. Guruswami and Resch
\cite[Theorem 1.1]{GR} prove ordinary list-decodability of random linear
rank-metric codes at this rate minus $\varepsilon$, with list size
$O_{p,q}(1/\varepsilon)$. Their result also treats rectangular matrices.
Guruswami, Li and Singhal prove the average-radius counterpart for the
Hamming metric in \cite[Theorem 1]{GLS}, and ask the following rank-metric
question in their final section.

\begin{question}[{\cite[Section 4, ``Extension to the rank metric'']{GLS}}]\label{q:source}
Can the $O_{p,q}(1/\varepsilon)$ list-size result for random
$\F_q$-linear codes in $\F_q^{n\times n}$ of rate
$(1-p)^2-\varepsilon$ be extended to average-radius list decoding
at radius $pn$?
\end{question}
The binary case was already observed in
\cite[Remark 5.6]{GLMRSSW}: its potential argument gives the
average-radius guarantee for random linear rank-metric codes over
$\F_2$, with a sharper list-size constant. The contribution here is
the general finite-field assertion asked for in Question~\ref{q:source},
together with a finite estimate uniform in the capacity gap. We restrict
to square matrices, as in that question. No decoding algorithm or
extension to every rectangular aspect ratio is asserted.

\Needspace{13\baselineskip}
\subsection{Main results}
Our main result answers Question~\ref{q:source} affirmatively.
\begin{theorem}\label{thm:main}
Fix a prime power $q$ and $0<p<1$. There are positive constants
$B_1,B_2,B_3$, depending only on $p,q$, such that the following holds
for every $n\ge1$ and $0<\varepsilon<(1-p)^2$. Set
\[
 k=\left\lfloor\bigl((1-p)^2-\varepsilon\bigr)n^2\right\rfloor,
\]
and choose $\C$ uniformly among the $k$-dimensional subspaces of $V_n$.
There is an integer $L\le B_3/\varepsilon$ for which
\begin{equation}\label{eq:mainprob}
 \Pr[\C\text{ has a bad list of size }L]
 \le q^{-2n^2+B_1/\varepsilon+B_2\log_q(n+1)}.
\end{equation}
An explicit finite estimate and choice of $L$ are given in
Theorem~\ref{thm:finite} below.
\end{theorem}
The proof has three components.
\begin{enumerate}
\item Lemma~\ref{lem:extraction} extracts either a large independent
set of small average weight or a smaller independent set whose span
contains many of the original points. Its affine version preserves the
single-center condition in a codeword list.
\item Theorem~\ref{thm:localshell} bounds the number of low-rank points
in every translate of the span of matrices drawn from nearby rank
shells. The bound is uniform over translations; no independence of the
generators as vectors is required.
\item Proposition~\ref{prop:weighted} combines this estimate with a
quadratic rank-profile deficit. Theorem~\ref{thm:finite} then proves
\eqref{eq:mainprob} by counting affine witnesses.
\end{enumerate}
The proof follows the span-counting framework behind \cite{GR} and
the greedy-basis approach in \cite[Section 1.2]{GLS}. The two-sum and
span estimates in \cite[Lemmas 4.1--4.2]{GR} concern generators drawn
from a rank ball. Here those estimates are proved for prescribed nearby
rank shells and all translated spans, then combined with a weighted
profile count. This is what allows a constraint on the average rank.

The distinction between probabilistic independence of sampled matrices
and linear independence of a witness is essential. The shell estimates
use the former, while containment in a random code is charged only for
the independent differences in an affine witness.

\begin{corollary}\label{cor:varying}
For fixed $p,q$, let $0<\varepsilon_n<(1-p)^2$ and suppose
$\varepsilon_n n^2\to\infty$. There are forbidden-list sizes
$L_n=O_{p,q}(1/\varepsilon_n)$ such that the random codes of
Theorem~\ref{thm:main} have no bad lists of size $L_n$ with probability
at least $1-q^{-2n^2+o(n^2)}$.
\end{corollary}
\begin{proof}
The hypothesis gives $1/\varepsilon_n=o(n^2)$, and
$\log(n+1)=o(n^2)$. Substitute these estimates in
\eqref{eq:mainprob}.
\end{proof}

\subsection{Related work}
\emph{Rank-metric codes and list decoding.} Rank-metric codes were
introduced by Delsarte~\cite{Delsarte} and Gabidulin~\cite{Gabidulin},
who constructed the maximum rank distance codes now called Gabidulin
codes; Roth~\cite{Roth} independently studied them for crisscross error
correction. List decoding goes back to Elias and Wozencraft; see
Elias~\cite{Elias}. For Gabidulin codes, Wachter-Zeh~\cite{WZ} showed that
list sizes become exponential beyond the Johnson radius, and that no
Johnson-type polynomial bound depending only on the length and minimum
distance can hold in the rank metric. Capacity-achieving list
decodability in the rank metric is therefore sought in other ensembles,
such as random linear codes.

\emph{Random linear codes.} The central difficulty for random linear codes is dependence between
codewords. A list can be large while its linear span has small dimension,
so estimates based only on independent codewords lose an exponential
factor in the list size. Guruswami, H\aa stad and
Kopparty~\cite[Theorems~6 and~10 of the preprint]{GHK}
overcame this obstacle in the Hamming metric by controlling how many
points of a ball can lie in the span of a few randomly chosen ball
points. Their method gives list size $O_{p,q}(1/\varepsilon)$ at
capacity minus $\varepsilon$ for every fixed field and admissible
Hamming radius.

\emph{Rank metric.} In the rank metric, Ding~\cite[Section~IV]{Ding} established capacity
for random $\F_q$-linear matrix codes with list size exponential in
$1/\varepsilon$. Guruswami and Resch~\cite{GR} reduced this to
$O_{p,q}(1/\varepsilon)$ by adapting the span argument.
For binary codes, Li and Wootters~\cite[Section~5]{LW} obtained a
sharper ordinary-list constant through a potential-function argument.
The extension of that argument to average radius is precisely the
earlier binary result in \cite[Remark~5.6 of the 2020 preprint]{GLMRSSW}.
Thus neither the binary theorem nor the ordinary rank-metric
capacity theorem is a new claim here.

\emph{Average-radius list decoding.} Average-radius guarantees also have a substantial Hamming-metric
history. Rudra and Wootters~\cite[Corollary~3.4 of the preprint]{RW}
gave capacity-rate guarantees with quasipolynomial list sizes in a
specified constant-alphabet parameter range, within a framework also
covering list recovery. The all-fixed-field linear dependence on
$1/\varepsilon$ is supplied by Guruswami, Li and Singhal~\cite{GLS}.
Their greedy-basis argument and entropy count motivate the weighted
extraction and rank-profile count below. The two metrics have different
volume exponents; in particular, the rank radius may be any $p<1$,
whereas their Hamming theorem assumes $p<1-1/q$.
For large Hamming alphabets, Goyal and
Guruswami~\cite[Theorems~1.1--1.2]{GG} obtain improved alphabet-size
bounds for average-radius guarantees approaching the generalized
Singleton bound, for both random linear and additive codes. Their
coordinatewise constraint count addresses a different metric and
alphabet-size question.

\emph{Other ensembles and metrics.} Other rank-metric results use different ensembles or guarantees.
Guo, Xing, Yuan and Zhang~\cite[Theorem~4]{GXYZ} prove average-radius
list-decodability for random Gabidulin codes over $\F_{q^m}$.
Writing their block length as $\nu$ and their gap parameter as $\delta$,
the theorem requires $m\ge c\ell(\ell+1)\nu/\delta$ and gives
radius $\frac{\ell}{\ell+1}(1-R-\delta)$ with maximum list size
$\ell$. These are extension-field-linear codes represented by
$m\times\nu$ matrices; this theorem does not supply the square,
uniformly random $\F_q$-subspace assertion considered here.

Liu, Baumeister and Wachter-Zeh~\cite[Theorem~6]{LBW} extend the
ordinary-list span method to the sum-rank metric, where the weight is
the sum of ranks of matrix blocks. Their conclusion bounds the number
of codewords in each sum-rank ball. Recent work of Li, Xing, Yuan and
Zhu~\cite[Definition~1.1 and Theorems~1.2--1.3]{LXYZ} instead controls
how often points on an affine line are close to a rank-metric code,
with applications to proofs of proximity. Neither statement is the
average-distance guarantee for lists of codewords in Question~\ref{q:source}.

\subsection{Why the weighted argument works}
A bad list may contain offsets of several different ranks. Removing
those with rank above $(p+\eta)n$, for a small fixed $\eta>0$,
retains a fixed positive fraction of the list and leaves its average
rank at most $pn$. The greedy affine extraction then gives two
possibilities: many affinely independent offsets, whose simultaneous
occurrence is unlikely, or a smaller witness whose affine span contains
many low-rank points. This second possibility is ruled out by estimates
on matrices sampled independently from exact-rank shells.

There is a useful distinction within the latter estimate. If many ranks
are far from $pn$, their profile already has few realizations. Indeed,
for $a_i=r_i/n$ and $\sum_i a_i\le tp$, the quadratic rank exponent
$f(a)=2a-a^2$ satisfies
\[
 \sum_{i=1}^t f(a_i)\le tf(p)-\sum_{i=1}^t(a_i-p)^2.
\]
Otherwise only a bounded number of generators fall below $p-\eta$;
the others lie in nearby shells, where the translated-span estimate
applies. Retaining half the quadratic deficit allows the remaining
profile sum to factor into bounded discrete Gaussian sums. This
replaces an overhead $(n+1)^t$ by a constant to the power $t$, and
is what makes the estimate useful when the gap varies with $n$.

Finally, the center is encoded by offsets. An affinely independent
$t$-tuple $X_i=c_i-Y$ requires only its $t-1$ independent differences
to lie in the random code. Counting those tuples already accounts for
all possible centers. Charging a further factor $q^{n^2}$ for the
center would lose part of the available exponential saving.

\begin{example}
The difference between average and maximum distance can already be seen
at one center in $\F_2^{2\times2}$. The offsets $0$ and $I_2$ have
ranks 0 and 2. Their average rank is 1, although the second offset is
outside the radius-1 ball. Thus a proof for average-radius lists must
allow generators with different ranks; counting only one ball is not
sufficient.
\end{example}

\section{Rank profiles and random-subspace containment}
Throughout the proof put $N=n^2$, $f(a)=2a-a^2$, and
\[
 B(a)=\{X\in V_n:\rank(X)\le an\},\qquad
 \Gamma=\prod_{j=1}^{\infty}(1-q^{-j})^{-1}.
\]
The radius in $B(a)$ is automatically rounded down. The infinite product
is finite because $\sum_jq^{-j}<\infty$.

\begin{lemma}\label{lem:ranks}
If $M_r$ is the number of rank-$r$ matrices in $V_n$, then
\begin{equation}\label{eq:ranks}
 \Gamma^{-2}q^{2nr-r^2}\le M_r\le\Gamma q^{2nr-r^2}
 \qquad(0\le r\le n).
\end{equation}
For an exact rank profile $r_1,\ldots,r_t$ with
$\sum_i r_i\le pnt$, put $a_i=r_i/n$ and
$\Delta=\sum_i(a_i-p)^2$. The number of tuples realizing the profile
is at most
\begin{equation}\label{eq:profile}
 \Gamma^tq^{(tf(p)-\Delta)N}.
\end{equation}
Also $|B(a)|\le\Gamma(n+1)q^{f(a)N}$ for $0\le a\le1$.
\end{lemma}
\begin{proof}
Factor a rank-$r$ matrix into a full-column-rank $n\times r$ matrix
and a full-row-rank $r\times n$ matrix. Each matrix has exactly
$|\mathrm{GL}_r(\F_q)|$ such factorizations. Hence
\[
 M_r=q^{2nr-r^2}
 \frac{\prod_{i=0}^{r-1}(1-q^{i-n})^2}
 {\prod_{i=0}^{r-1}(1-q^{i-r})}.
\]
Every finite product of distinct factors $1-q^{-j}$ lies between
$\Gamma^{-1}$ and 1, proving \eqref{eq:ranks}, including the empty
product at $r=0$. For \eqref{eq:profile}, multiply the upper bounds
and use the exact identity
\begin{equation}\label{eq:deficit}
 f(a)=f(p)+2(1-p)(a-p)-(a-p)^2.
\end{equation}
The linear terms sum to a nonpositive number. Finally, $f$ is increasing
on $[0,1]$, so summing \eqref{eq:ranks} over ranks at most $an$
gives the ball bound.
\end{proof}
\begin{remark}[The capacity rate]\label{rem:capacity}
The rank count also explains the rate in Question~\ref{q:source}.
If a nonempty code has no bad list of size $L\ge2$, each radius-$pn$
ball contains at most $L-1$ codewords. Count pairs $(c,Y)$ with
$c\in\C$ and $\rank(c-Y)\le pn$ first by $c$ and then by $Y$.
Translation invariance gives
\[
 |\C|\,|B(p)|\le(L-1)q^N.
\]
With $r=\lfloor pn\rfloor$, the lower bound in \eqref{eq:ranks}
therefore gives
\[
 \frac{\log_q|\C|}{N}
 \le 1-f(r/n)+\frac{\log_q(L-1)+2\log_q\Gamma}{N}.
\]
If $\log L=o(n^2)$, then $r/n\to p$ and the asymptotic upper
bound is $(1-p)^2$. This argument does not require linearity.
\end{remark}

The Gaussian binomial coefficient, counting $v$-dimensional subspaces
of $\F_q^u$, satisfies
\begin{equation}\label{eq:gaussianbinomial}
 \Gamma^{-1}q^{v(u-v)}\le \qbinom{u}{v}
 \le\Gamma q^{v(u-v)}.
\end{equation}
Indeed, counting ordered independent bases gives
$\qbinom{u}{v}=q^{v(u-v)}\prod_{i=0}^{v-1}(1-q^{i-u})/
\prod_{i=0}^{v-1}(1-q^{i-v})$, to which the same product bounds apply.

\begin{lemma}\label{lem:containment}
For a fixed $s$-dimensional subspace $U\le\F_q^N$ and a uniformly
random $k$-dimensional subspace $\C$,
\[
 \Pr[U\subseteq\C]\le\Gamma q^{-(N-k)s}.
\]
\end{lemma}
\begin{proof}
The probability is zero if $s>k$. Otherwise invariance under invertible
linear maps, applied to ordered independent $s$-tuples, gives
\[
 \Pr[U\subseteq\C]=\prod_{i=0}^{s-1}\frac{q^k-q^i}{q^N-q^i}.
\]
After factoring out $q^{-(N-k)s}$, the numerator is at most 1 and
the denominator at least $\Gamma^{-1}$. The formula also covers $s=0$.
\end{proof}

\begin{lemma}\label{lem:gaussiansum}
Set $G_q=2\sum_{j=0}^{\infty}q^{-j^2/2}$. Then
$G_q\le2/(1-q^{-1/2})$, and for every real $x$,
\[
 \sum_{r=0}^nq^{-(r-x)^2/2}\le G_q.
\]
Consequently the number of ordered $t$-tuples of matrices of average
rank at most $pn$ is at most
\begin{equation}\label{eq:alltuples}
 (\Gamma G_q)^tq^{tf(p)N}.
\end{equation}
\end{lemma}
\begin{proof}
For every integer $j\ge0$, the integers at distance in $[j,j+1)$
from $x$ lie in $[x+j,x+j+1)$ or $(x-j-1,x-j]$. Each interval
contains at most one integer. Their total contribution is at most
$2q^{-j^2/2}$. Summing proves the first bound, and $j^2\ge j$
gives the geometric-series estimate on $G_q$.
For a rank profile, \eqref{eq:profile} has deficit
$\Delta N=\sum_i(r_i-pn)^2$. Sum over the allowed profiles, enlarge
to all profiles in $\{0,\ldots,n\}^t$, and use
$q^{-u^2}\le q^{-u^2/2}$. The resulting product of $t$
one-dimensional sums proves \eqref{eq:alltuples}.
\end{proof}

\section{Weighted affine extraction}
\begin{lemma}\label{lem:extraction}
Let $S$ be a nonempty finite set of nonzero vectors over a field,
with $|S|=s$. Give its elements nonnegative weights of average at most
$\mu$. For every positive integer $D$, either
\begin{enumerate}
\item $S$ contains $D$ linearly independent vectors of average weight
at most $\mu$; or
\item for some $1\le d<D$, it contains independent vectors
$x_1,\ldots,x_d$ of average weight at most $\mu$ with
$|S\cap\spanF(x_1,\ldots,x_d)|>sd/D$.
\end{enumerate}
\end{lemma}
\begin{proof}
Greedily choose a minimum-weight element outside the previous span,
obtaining a basis $x_1,\ldots,x_r$ of $\spanF(S)$. Put
$b_j=w(x_j)$, $W_j=\spanF(x_1,\ldots,x_j)$, and
$m_j=|S\cap W_j|$. The sequence $b_j$ is nondecreasing, and every
point outside $W_{j-1}$ has weight at least $b_j$.
If the first $D$ elements exist and have average weight at most $\mu$,
we have the first conclusion. If all greedy prefixes have average at
most $\mu$ but this conclusion fails, then $r<D$, and $d=r$
gives $m_r=s>sr/D$.

In the remaining case let $h$ be the first index with
$\sum_{i=1}^h b_i>h\mu$. Then $2\le h\le D$: the first weight
is at most the average over $S$, and failure of the first conclusion
forces such an index by $D$ if the basis has that many elements.
All shorter prefixes have average at most $\mu$, and $b_h>\mu$.
Suppose $m_j\le sj/D$ for every $j<h$. Points entering the span
at step $i$ have weight at least $b_i$, and those outside $W_{h-1}$
have weight at least $b_h$. Thus
\begin{align*}
 \sum_{x\in S}w(x)
 &\ge sb_h-\sum_{j=1}^{h-1}m_j(b_{j+1}-b_j)\\
 &\ge sb_h-\frac{s}{D}\sum_{j=1}^{h-1}j(b_{j+1}-b_j)\\
 &=\frac{s}{D}\left(\sum_{i=1}^h b_i+(D-h)b_h\right)>s\mu.
\end{align*}
The last inequality uses $D-h\ge0$ and $b_h>\mu$. This contradicts
the assumed average. Some $d<h$ therefore satisfies $m_d>sd/D$,
and its prefix gives the second conclusion.
\end{proof}

\begin{corollary}\label{cor:affine}
If $S\subseteq V_n$ is nonempty and has average rank at most $pn$,
then either it contains $D$ affinely independent matrices of average
rank at most $pn$, or, for some $1\le t<D$, it contains affinely independent matrices
$Z_1,\ldots,Z_t$ of that average rank such that
\[
 |S\cap\aff(Z_1,\ldots,Z_t)|>\frac{|S|t}{D}.
\]
\end{corollary}
\begin{proof}
Apply Lemma~\ref{lem:extraction} to the nonzero lifted vectors $(X,1)$,
weighted by $\rank(X)$. Independence of these lifts is affine
independence of the matrices. A point $(X,1)$ is in their linear span
exactly when its coefficients sum to 1, which is precisely the affine
span condition.
\end{proof}

\section{Separated balls and nearby rank shells}
\begin{lemma}\label{lem:intersection}
Let $0\le r<n$ be an integer. Suppose $\rank(A)\ge an$ and
$n-r\ge bn$ for positive $a,b$, and put
$\kappa=\min\{ab/2,b^2/4\}$. Then
\begin{equation}\label{eq:intersection}
 |\{X:\rank(X)\le r,\ \rank(X-A)\le r\}|
 \le(n+1)\Gamma^5q^{2nr-r^2-\kappa N}.
\end{equation}
\end{lemma}
\begin{proof}
Write $a_A=\rank(A)$. For each counted $X$, extend the column spaces
of $X$ and $X-A$ to $r$-dimensional subspaces $U,V\le\F_q^n$.
Overcounting is harmless. Put $j=r-\dim(U\cap V)$, so
$0\le j\le\min(r,n-r)$ and $\dim(U+V)=r+j$.
For fixed $U,V$, a necessary and sufficient condition for the column
constraints to have a solution is $\col(A)\subseteq U+V$.
When it holds, each column of $X$ lies in an affine coset of $U\cap V$,
giving exactly $q^{n(r-j)}$ possible matrices.

For a fixed $j$, the number of ordered pairs $(U,V)$ is
\[
 \qbinom{n}{r}\qbinom{r}{j}\qbinom{n-r}{j} q^{j^2}
 \le\Gamma^3q^{r(n-r)+jn-j^2}.
\]
To obtain the formula, choose $U$, its $(r-j)$-dimensional intersection
with $V$, and the $j$-dimensional image of $V$ in $\F_q^n/U$.
The remaining choice is the graph of a map from that image into the
$j$-dimensional quotient of $U$, giving $q^{j^2}$ possibilities.
The inequality follows from \eqref{eq:gaussianbinomial}.
By the transitive action of $\mathrm{GL}_n(\F_q)$, the sums $U+V$
are equally distributed over all $(r+j)$-dimensional subspaces.
If $a_A>r+j$, no pair is admissible. Otherwise the fraction containing
$\col(A)$ is
\[
 \qbinom{n-a_A}{r+j-a_A}\,\qbinom{n}{r+j}^{-1}
 \le\Gamma^2q^{-a_A(n-r-j)}.
\]
Multiplication by $q^{n(r-j)}$ gives, for this $j$, the bound
\[
 \Gamma^5q^{2nr-r^2-j^2-a_A(n-r-j)}.
\]
Write $h=n-r$. If $j\ge h/2$, then $j^2\ge b^2N/4$.
If $j<h/2$, then $a_A(h-j)\ge abN/2$.
In both cases the exponent loses at least $\kappa N$.
There are at most $n+1$ values of $j$, proving \eqref{eq:intersection}.
\end{proof}

\begin{lemma}\label{lem:twosum}
There are constants $\eta,c>0$, depending only on $p$, with
$0<p-\eta<p+\eta<1$, such that the following holds. Put
$\rho=p+\eta$ and $C_0=2\Gamma^7$. Let $X_1,X_2$ be independent
and uniform on exact-rank shells of ranks $r_1,r_2$, where
$p-\eta\le r_i/n\le p+\eta$. For every fixed $Z\in V_n$ and
nonzero $a_1,a_2\in\F_q$,
\begin{equation}\label{eq:twosum}
 \Pr[a_1X_1+a_2X_2+Z\in B(\rho)]
 \le C_0(n+1)q^{-cN}.
\end{equation}
\end{lemma}
\begin{proof}
Let $\beta=1-p$, $c_2=\min\{p\beta/8,\beta^2/16\}$, and choose
\[
 0<\eta\le\min\{p/4,\beta/4,c_2/8\}.
\]
Set $c_1=f(3p/4)-f(p/2)>0$ and $c=\min\{c_1,c_2/2\}$.
Nonzero scalar multiplication preserves every exact-rank shell, so
it suffices to take $a_1=a_2=1$. Write $A=X_1+Z$.
The number of $X_1$ with $\rank(A)<pn/2$ is at most $|B(p/2)|$.
Using Lemma~\ref{lem:ranks} and $p-\eta\ge3p/4$ gives
\[
 \Pr[\rank(A)<pn/2]
 \le\Gamma^3(n+1)q^{[f(p/2)-f(p-\eta)]N}
 \le\Gamma^3(n+1)q^{-c_1N}.
\]
For all other $X_1$, put $r=\lfloor\rho n\rfloor$.
Then $n-r\ge\beta n/2$. Lemma~\ref{lem:intersection} with
$a=p/2$ and $b=\beta/2$ yields
\[
 |B(\rho)\cap(-A+B(\rho))|
 \le(n+1)\Gamma^5q^{[f(\rho)-c_2]N}.
\]
The rank-$r_2$ shell is contained in $B(\rho)$ and has at least
$\Gamma^{-2}q^{f(p-\eta)N}$ elements. Conditional on this $X_1$,
the probability that $X_2+A$ is in $B(\rho)$ is therefore at most
\[
 (n+1)\Gamma^7q^{[f(p+\eta)-f(p-\eta)-c_2]N}
 \le(n+1)\Gamma^7q^{-c_2N/2},
\]
since $f(p+\eta)-f(p-\eta)=4(1-p)\eta\le c_2/2$.
Add the exceptional probability and use $\Gamma\ge1$. All bounds
are uniform in $Z$.
\end{proof}

\section{Coefficient sets and translated spans}
For $v\in\F_q^g$, write $\supp(v)=\{j:v_j\ne0\}$.
Call $w_1,\ldots,w_m$ \emph{two-increasing} if each $w_i$ has at
least two support coordinates outside the union of the earlier supports.
A coordinate rectangle in $T\subseteq\F_q^g$ means that its projection
onto two coordinates contains the Cartesian product of two two-element
sets. Witnesses to the four corners need not agree elsewhere.
Put $A_q=\binom q2$.

\begin{lemma}\label{lem:rectangle}
A set $T\subseteq\F_q^g$ with no coordinate rectangle satisfies
$|T|\le1+A_qg$.
\end{lemma}
\begin{proof}
Induct on $g$, the case $g=0$ being immediate. Project onto the first
$g-1$ coordinates, obtaining $P$. For each $x\in P$, let $F_x$
be its nonempty fiber of last-coordinate values. Then
\[
 |T|=|P|+\sum_{x\in P}(|F_x|-1).
\]
A fixed pair of distinct symbols can belong to at most one $F_x$.
If it belonged to $F_x$ and $F_y$ for $x\ne y$, a coordinate where
$x,y$ differ, together with the last coordinate, would give a rectangle.
Since $s-1\le\binom s2$ for $s\ge1$, the sum is at most $A_q$.
The projection $P$ has no rectangle either, so induction gives
$|P|\le1+A_q(g-1)$, as required.
\end{proof}

\begin{lemma}\label{lem:chain}
If $m\ge1$ and $|T|>q^{2(m-1)}(1+A_qg)$, then there are
$v_0,v_1,\ldots,v_m\in T$ such that $v_1-v_0,\ldots,v_m-v_0$
is two-increasing. For $g\ge1$, the sufficient condition $|T|>Hg$
may be used, where $H=q^{2(m-1)}(1+A_q)$.
\end{lemma}
\begin{proof}
Induct on $m$, simultaneously for every $g$. For $m=1$,
Lemma~\ref{lem:rectangle} supplies a rectangle, and two opposite corners
give points differing in two coordinates. For $m\ge2$, choose a
rectangle and partition $T$ by the values of its two coordinates.
A largest fiber $F$ has size
\[
 |F|\ge |T|/q^2>q^{2(m-2)}(1+A_qg)
 \ge q^{2(m-2)}(1+A_q(g-2)).
\]
Delete the two fixed coordinates and apply induction inside $F$,
obtaining $v_0,\ldots,v_{m-1}$. Let the fixed coordinate values
be $a,b$. In each of the two sides of the original rectangle, choose
a value different from the corresponding $a$ or $b$. Its corner has
a witness $v_m\in T$. The difference $v_m-v_0$ is nonzero in both
fixed coordinates, whereas all earlier differences vanish there.
Appending it gives the chain. Finally,
$(1+A_q)g\ge1+A_qg$ for $g\ge1$.
\end{proof}
Fix the constants of Lemma~\ref{lem:twosum}, and henceforth put
\begin{equation}\label{eq:constants}
 m=\lceil4/c\rceil,\quad H=q^{2(m-1)}(1+A_q),\quad
 b=\lceil6/\eta^2\rceil,\quad K=q^b(H+1).
\end{equation}
All depend only on $p,q$.

\begin{theorem}\label{thm:localshell}
Let $X_1,\ldots,X_g$ be independent, each uniform on an exact-rank
shell whose normalized rank belongs to $[p-\eta,p+\eta]$, where
$g\ge1$. Then
\begin{equation}\label{eq:local}
 \Pr\left[\exists Z:\left|(Z+\spanF(X_1,\ldots,X_g))
 \cap B(\rho)\right|>Hg\right]
 \le C_0^m(n+1)^m q^{-3N+mg}.
\end{equation}
\end{theorem}
\begin{proof}
For a realization, define $T_X(v)=\sum_jv_jX_j$. If a translate
$Z+\spanF(X_1,\ldots,X_g)$ contains more than $Hg$ distinct points
of $B(\rho)$, then
\[
 S=\{v\in\F_q^g:Z+T_X(v)\in B(\rho)\}
\]
has more than $Hg$ elements: each such point has a preimage.
Lemma~\ref{lem:chain} supplies $v_0,\ldots,v_m\in S$, with
$w_i=v_i-v_0$ two-increasing. Set $A=Z+T_X(v_0)$.
Then $A+T_X(w_i)\in B(\rho)$ for every $i$.

Fix now a \emph{deterministic} matrix $A$ and a deterministic
two-increasing sequence $w_1,\ldots,w_m$. Let $E_i$ denote the
corresponding low-rank event and put
$\delta=C_0(n+1)q^{-cN}$. Choose two coordinates of $w_m$ that do
not occur in any earlier support. Conditional on all generators except
these two, the earlier events are determined, while $E_m$ involves two
independent shell matrices with nonzero coefficients and a fixed shift.
Lemma~\ref{lem:twosum} gives
\[
 \Pr(E_1\cap\cdots\cap E_m)
 \le\delta\Pr(E_1\cap\cdots\cap E_{m-1}).
\]
Repeat on the shortened chain to obtain a bound of $\delta^m$.
There are $q^N$ possible deterministic $A$ and at most $q^{mg}$
coefficient sequences. A union bound yields
\[
 q^{N+mg}\delta^m
 =C_0^m(n+1)^m q^{-(cm-1)N+mg}
 \le C_0^m(n+1)^m q^{-3N+mg}.
\]
This union covers all possible shifts. In particular, the proof never
conditions on the random anchor $Z+T_X(v_0)$; doing so would not
preserve the independence used in the two-shell estimate.
\end{proof}

\section{Weighted spans and Gaussian summation}
\begin{proposition}\label{prop:weighted}
For every positive integer $t$, the number of ordered tuples
$(X_1,\ldots,X_t)$ satisfying
\begin{equation}\label{eq:richconditions}
 X_i\in B(\rho),\qquad \sum_i\rank(X_i)\le pnt,\qquad
 |\spanF(X_1,\ldots,X_t)\cap B(\rho)|>Kt
\end{equation}
is at most
\begin{equation}\label{eq:weighted}
 (\Gamma G_q)^t C_0^m(n+1)^m q^{(tf(p)-3)N+mt}.
\end{equation}
No linear or affine independence is required, and $t$ may depend on $n$.
\end{proposition}
\begin{proof}
Fix an allowed rank profile, put $a_i=r_i/n$, and let
$\Delta=\sum_i(a_i-p)^2$. Write
$P_{n,t}=C_0^m(n+1)^m q^{mt}\ge1$. We will bound the number of
rich tuples with this profile by
\begin{equation}\label{eq:richprofile}
 \Gamma^tP_{n,t}q^{(tf(p)-3)N}q^{-\Delta N/2}.
\end{equation}
If $\Delta\ge6$, the bound for all tuples in
\eqref{eq:profile} suffices, since $\Delta\ge3+\Delta/2$.

Suppose $\Delta<6$. Call $i$ exceptional when $a_i<p-\eta$.
Each exceptional index contributes more than $\eta^2$ to $\Delta$,
so there are at most $b$ of them. All other ranks lie in
$[p-\eta,p+\eta]$, because $X_i\in B(\rho)$.
Sample the matrices independently and uniformly from their specified
shells, and condition on the exceptional matrices. Their span $U$ has
at most $q^b$ elements. Let $W$ be the span of the $g$ remaining
matrices. If $g=0$, the full span has size at most $q^b<Kt$, and
cannot be rich. If $g\ge1$ and every translate of $W$ contains at
most $Hg$ low-rank points, then
\[
 |(U+W)\cap B(\rho)|
 \le\sum_{Z\in U}|(Z+W)\cap B(\rho)|
 \le q^bHg\le q^bHt<Kt.
\]
Thus richness implies the event in Theorem~\ref{thm:localshell} for
the good generators. They remain independent and uniform on their
shells after conditioning. The conditional probability of richness is
at most $P_{n,t}q^{-3N}$, uniformly in the exceptional values.
Multiply by the profile count
$\Gamma^tq^{tf(p)N-\Delta N}$ from \eqref{eq:profile}. The result
is bounded by \eqref{eq:richprofile}, since $\Delta\ge0$.
This proves the same profile bound in both cases.

Finally sum \eqref{eq:richprofile} over allowed profiles and enlarge
the residual nonnegative sum to all $r_i\in\{0,\ldots,n\}$.
Because $\Delta N=\sum_i(r_i-pn)^2$, this sum factors into $t$
one-dimensional Gaussian sums, each at most $G_q$ by
Lemma~\ref{lem:gaussiansum}. Substituting $P_{n,t}$ gives
\eqref{eq:weighted}.
\end{proof}

\section{Counting bad affine lists}
\begin{theorem}\label{thm:finite}
Use the constants above and set
\[
 A_{p,q}=\Gamma G_q q^m,\qquad
 D=\lceil3/\varepsilon\rceil,\qquad
 L=\left\lceil\frac{\rho K}{\eta}D\right\rceil.
\]
For the random code of Theorem~\ref{thm:main},
\begin{equation}\label{eq:finitefailure}
 \Pr[\C\text{ has a bad list of size }L]
 \le D\Gamma C_0^m(n+1)^m A_{p,q}^Dq^{-2n^2}.
\end{equation}
Moreover $L\le(4\rho K/\eta+1)/\varepsilon$.
\end{theorem}
\begin{proof}
Put $\alpha=f(p)+\varepsilon$. Then $\alpha<1$ and
$N-k\ge\alpha N$. If $X_1,\ldots,X_t$ are affinely independent,
their differences $X_i-X_1$ for $i\ge2$ span a $(t-1)$-dimensional
space. Lemma~\ref{lem:containment} bounds the probability that all
these differences lie in $\C$ by
$\Gamma q^{-\alpha(t-1)N}$.
There is no additional factor for the center: offsets $X_i=c_i-Y$
from a common center have all their differences in $\C$; conversely,
if those differences lie in $\C$, then the codewords $c_i'=X_i-X_1$
and the center $Y'=-X_1$ realize the same offsets. Distinct offsets
produce distinct codewords.

First consider affinely independent $D$-tuples of average rank at most
$pn$ whose differences lie in $\C$. By \eqref{eq:alltuples} and
the containment bound, their existence has probability at most
\begin{equation}\label{eq:largewitness}
 \Gamma(\Gamma G_q)^D
 q^{[Df(p)-\alpha(D-1)]N}
 =\Gamma(\Gamma G_q)^Dq^{(\alpha-\varepsilon D)N}
 \le\Gamma(\Gamma G_q)^Dq^{-2N}.
\end{equation}
The last inequality uses $\varepsilon D\ge3$ and $\alpha<1$.

For each $1\le t<D$, consider affinely independent tuples satisfying
\eqref{eq:richconditions} whose differences lie in $\C$.
Proposition~\ref{prop:weighted} and the same containment bound give
probability at most
\begin{align}
 &\Gamma(\Gamma G_q)^t C_0^m(n+1)^m
 q^{mt+[tf(p)-3-\alpha(t-1)]N}\notag\\
 &\hspace{20mm}\le\Gamma C_0^m(n+1)^m A_{p,q}^tq^{-2N},
 \label{eq:smallwitness}
\end{align}
because $tf(p)-3-\alpha(t-1)=\alpha-3-\varepsilon t\le-2$.
If affine independence is impossible for dimension reasons, the
corresponding event is empty, and these estimates remain valid.

It remains to prove that every bad list produces one of the witnesses
just counted. Let $X_i=c_i-Y$ be $L$ distinct offsets with total
rank at most $pnL$. Keep precisely those with rank at most $\rho n$,
forming $S$ of size $s$. The removed offsets have rank greater than
$\rho n$, so
\[
 \rho n(L-s)\le pnL,\qquad
 s\ge\frac{\eta}{\rho}L\ge KD.
\]
Their removal leaves average rank at most $pn$: subtracting numbers
greater than $pn$ from a total at most $pnL$ leaves a total at most
$pns$. Apply Corollary~\ref{cor:affine} to $S$.
Its first alternative gives the witness in \eqref{eq:largewitness}.
Otherwise there are $t<D$ affinely independent $Z_1,\ldots,Z_t\in S$
of average rank at most $pn$ with
\[
 |S\cap\aff(Z_1,\ldots,Z_t)|>st/D\ge Kt.
\]
Since $S\subseteq B(\rho)$ and the affine span is contained in the
linear span, this tuple satisfies \eqref{eq:richconditions}.
Its differences lie in $\C$, because its members come from the same
original list. It is therefore a witness in \eqref{eq:smallwitness}.

There are $D$ event types: one large type and $D-1$ small types.
As $A_{p,q}>1$ and $C_0^m(n+1)^m\ge1$, each bound is at most
$\Gamma C_0^m(n+1)^m A_{p,q}^Dq^{-2N}$. Summing proves
\eqref{eq:finitefailure}. Finally, $0<\varepsilon<1$ gives
$D\le4/\varepsilon$, and hence
\[
 L\le\frac{\rho K}{\eta}D+1
 \le\frac{4\rho K/\eta+1}{\varepsilon}.
\]
\end{proof}
\begin{proof}[Proof of Theorem~\ref{thm:main}]
Take the list size in Theorem~\ref{thm:finite}. The base-$q$ logarithm
of its prefactor is
\[
 \log_qD+\log_q\Gamma+m\log_qC_0
 +m\log_q(n+1)+D\log_qA_{p,q}.
\]
All constants depend only on $p,q$, and $D\le4/\varepsilon$.
Since $q\ge2$, we have $\log_qD\le D$. Using also
$1/\varepsilon>1$, one may therefore take
\[
 B_1=4+\log_q\Gamma+m\log_qC_0+4\log_qA_{p,q},\qquad
 B_2=m,\qquad B_3=4\rho K/\eta+1.
\]
These constants give \eqref{eq:mainprob}.
\end{proof}

\section{Concluding remarks}
The constants obtained from translated coefficient chains and exceptional
rank profiles are large. Improving their dependence on $p$ and $q$ is
a separate question. The proof treats $p,q$ as fixed and gives no
uniform control as $p$ approaches 0 or 1 or as the field grows.
Its finite estimate does allow the capacity gap to vary with $n$;
when $\varepsilon n^2$ stays bounded, that estimate need not tend
to zero. The rectangular model of \cite{GR} would require a version
of the shell and profile arguments with its two dimension parameters.

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