For every prime power q and every p∈(0,1-1/q), let H_q(p) denote the q-ary entropy. As varepsilon→0 with 1-H_q(p)-varepsilon>0, a random linear code C⊆F_q^n of rate 1-H_q(p)-varepsilon is, with probability tending to 1 as n→∞, (p,L)-list-decodable for L=fracH_q(p)varepsilon(1+o_varepsilon(1)); that is, for every y∈F_q^n, the Hamming ball of radius pn centered at y contains at most L codewords of C.

Asymptotically optimal list size of random linear codes

For every prime power $q$ and every $p\in(0,1-1/q)$ , let $H_q(p)$ denote the $q$ -ary entropy. As $\varepsilon\to0$ with $1-H_q(p)-\varepsilon>0$ , a random linear code $C\subseteq\mathbb{F}_q^n$ of rate $1-H_q(p)-\varepsilon$ is, with probability tending to $1$ as $n\to\infty$ , $(p,L)$ -list-decodable for $L=\frac{H_q(p)}{\varepsilon}(1+o_{\varepsilon}(1))$ ; that is, for every $y\in\mathbb{F}_q^n$ , the Hamming ball of radius $pn$ centered at $y$ contains at most $L$ codewords of $C$ .

References

Primary source

arXiv

Additional references

Asymptotically Optimal List Size of Random Linear Codes — arXiv

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A September 2026 unrefereed preprint claims to settle the optimal list-size question for random linear codes over every finite field, but independent verification is absent.

The problem asks for the smallest list size, near the random-coding rate, that random linear codes require for list decoding over finite fields. Earlier work established the sharp scale in the binary case and conjectured an analogous result for larger alphabets.

Known results

Binary random linear codes: list size at most $\lfloor h_2(p)/\varepsilon\rfloor+2$ with high probability (2018).
General finite fields: a lower bound $L\ge \lfloor h_q(p)/\varepsilon+0.99\rfloor$ was proved, while the matching upper bound remained conjectural (2020).

September 2026 claimed resolution

A new preprint claims an average-radius upper bound for every prime-power alphabet, extending the binary result and asserting a sharper additive-constant form. The claim is based on an unrefereed preprint and has no recorded independent verification.

Current status (as of September 2026): Binary codes have near-sharp bounds, while the claimed all-finite-field resolution and sharper additive-constant estimate remain unverified.

Sources

No solutions have been posted yet.