Source-linked AI summary
Asymptotically Optimal List Size of Random Linear Codes
Chen Yuan, Ruiqi Zhu
TL;DR
The paper addresses the unresolved sharp leading constant in list size for random linear codes over alphabets q > 2. It develops an increasing-chain and union-bound argument, bounding relevant configurations and proving that large lists in Hamming balls occur with exponentially small probability.
Problem
The optimal leading constant in the Θ_{p,q}(1/ε) list-size order remained open for q > 2, although the binary case was known.
Method
The proof combines a bound on relevant configuration sets with an increasing-chain argument and a union bound over configuration types.
Results
The analysis bounds N(A) by q^(rH_q(p)+η)n and shows that, with probability 1 − q^−Ω_{p,q}(εn), no Hamming ball of radius pn contains t codewords.
Takeaways & Limitations
The proof establishes the sharp H_q(p)-based leading behavior sought for random linear-code list size beyond the previously resolved binary case.
Takeaways & Limitations
The analysis is scoped to uniformly random k-dimensional linear codes and uses specific configuration-chain assumptions in its proof.
Abstract
from arXiv · showhide
We prove that for every fixed prime power $q$, every $p\in(0,1-1/q)$, and every $\varepsilon>0$ with $1-H_q(p)-\varepsilon>0$, a random linear code over $\mathbb{F}_q$ of rate $1-H_q(p)-\varepsilon$ is $(p,\,\left\lceil\frac{H_q(p)}{\varepsilon}\right\rceil+O_{p,q}(1))\text{-list-decodable}$ with probability at least $1-q^{-Ω(n)}$. Guruswami, Li, Mosheiff, Resch, Silas, and Wootters showed that, for sufficiently small $\varepsilon$, random linear codes require list size at least $\left\lfloor\frac{H_q(p)}{\varepsilon}+0.99\right\rfloor,$ and conjectured that $\frac{H_q(p)}{\varepsilon}(1+o(1))$ suffices as $\varepsilon\to 0$. This conjecture was previously known for $q=2$, where the upper bound $H_2(p)/\varepsilon+2$ was established. For $q>2$, however, the best known upper bound was $C_{p,q}/\varepsilon$ for a constant $C_{p,q}$ depending on $p$ and $q$. Our result resolves the conjecture for every prime power $q$ and, in fact, establishes the sharper upper bound $\frac{H_q(p)}{\varepsilon}+O_{p,q}(1)$.
1 Introduction
Random linear codes achieve the optimal Θ(1/ε) list-size order, while the paper addresses the remaining sharp leading constant. Its main result resolves the conjectured constant for every fixed prime power q.
- Background: List decoding allows a decoder to output multiple candidate codewords from a Hamming ball.A code is (p,L)-list-decodable when every radius-pn Hamming ball contains at most L codewords.
- Background: Random nonlinear codes achieve list size O(1/ε) at rate 1−H_q(p), and this order is tight up to constants.The list-decoding capacity is 1−H_q(p).
- Prior work: Random linear codes attain the optimal O(1/ε) order over every fixed alphabet, but earlier bounds used a constant C_{p,q} depending on p and q.Linear-code dependencies make the random-coding analysis more delicate than for unrestricted random codes.
- Open problem: The sharp leading constant remained open: lower bounds require H_q(p), while the binary case showed that H_2(p) is achievable.The conjecture was known for q=2 but remained open for q>2.
- Proof approach: The proof bounds structured collections of candidate vectors and then applies probability estimates and a union bound over their types.For the relevant neighborhood set N(A), the argument obtains size at most q^(rH_q(p)+η)n for any small constant η.
- Main contribution: Theorem 1.2 considers random linear codes of rate 1−H_q(p)−ε under the stated positivity condition.The supplied theorem passage introduces the random-code setting for the paper’s main result.
2 Preliminaries
The preliminaries define q-ary entropy, Hamming weight and support, Hamming balls, affine spaces, and affine independence for the subsequent list-decoding arguments.
- Entropy: The q-ary entropy function is H_q(x)=x log_q(q−1)−x log_q x−(1−x)log_q(1−x).It is defined for x in (0,1−1/q).
- Vector notation: The support of a vector contains its nonzero coordinates, and Hamming weight equals the support-set size.These notions connect vector structure to Hamming distance and weight bounds.
- Hamming geometry: A q-ary Hamming ball of radius pn is centered at a vector y and contains vectors within that radius.This is the neighborhood used in list-decodability definitions.
- Affine structure: An affine space of dimension r contains r+1 affinely independent vectors forming an affine basis.Affine independence means that the differences from one chosen vector are linearly independent.
3 Proof of Asymptotically Optimal List Size
The proof reduces list-decodability to controlling affine configurations of codewords inside Hamming balls, then bounds their probability in a random linear code. The main theorem follows by combining affine-rank structure, Hamming-ball intersection bounds, and subspace-containment probabilities.
- Main theorem: At rate R=1−H_q(p)−ε, the proof shows that, with probability 1−q^−Ω_{p,q}(εn), no radius-pn Hamming ball contains t codewords for the theorem’s chosen t.This establishes the claimed list-decodability bound for uniformly random linear codes over every fixed prime-power alphabet.
- Proof strategy: The proof reformulates a large list in a Hamming ball as an affine coset containing many codewords, with an associated subspace D contained in C.An intersection of size t and affine dimension r yields D of dimension r and a translate z + D whose intersection with the ball has size t.
- Random-code probability: For fixed r, a random linear code contains a prescribed r-dimensional subspace with probability q^−(n−k)r+o(n).This subspace-containment estimate supplies the probabilistic factor used after enumerating possible affine configurations.
- Intersection bounds: Hamming-ball intersection estimates show that centers with sufficiently large weight have exponentially smaller intersections, with exponent H_q(p)−c_τ.The argument samples a random vector with coordinate distribution determined by p and applies Hoeffding’s inequality.
- Proof strategy: A set of many coefficient vectors admits an increasing-chain structure that produces a basis in which many points have controlled linear representations.The construction uses affine rank, supports of coefficient vectors, and a basis change to expose repeated low-weight offsets.
- Intersection bounds: For sufficiently large coefficient sets, the number of admissible tuples is at most q^[rH_q(p)+η]n, enabling a union bound over affine configurations.The proof chooses τ so that H_q(τ)<η and derives a bound of q^[rH_q(p)+H_q(τ)]n before absorbing the entropy term into η.