🔢 mathematics

List Recovery for Random Low-Rate Linear Codes

This paper proves that random low-rate linear codes over sufficiently large prime fields are nearly optimally list recoverable for a wide range of input list sizes, establishing both a high-probability upper bound via a novel combination of graph-theoretic and algebraic techniques and a matching lower bound for codes of dimension at least two.

Original authors: Isaac M Hair, Amit Sahai

Published 2026-05-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Isaac M Hair, Amit Sahai

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find a specific needle in a massive haystack, but you don't know exactly what the needle looks like. Instead, you have a list of possible shapes for the needle at every single spot in the haystack. Your goal is to find all the "needles" (codewords) that match the shapes on your lists for almost the entire haystack, allowing for just a few mistakes.

This paper is about a mathematical game called List Recovery. Here is the story of what the authors discovered, explained simply:

The Players: The Haystack and the Rules

The Code (The Haystack): Imagine a secret message is hidden in a long string of numbers. This string is generated by a simple, fixed set of rules (a "linear code"). The authors are looking at codes that are very "short" in terms of rules (low dimension) but very "long" in terms of the message length.
The Lists (The Clues): At every position in the string, you are given a small list of possible numbers.
The Goal: You want to find every possible secret message that fits the lists at almost every position. If the code is "good," there should only be a tiny, manageable number of such messages. If the code is "bad," there could be millions of messages that fit, making it impossible to know which one is the real one.

The Big Discovery: Randomness is a Superpower

The authors asked: If we build these secret messages completely at random (using a large prime number system), how well do they work at this game?

They proved that random codes are incredibly good at this.

Even if you give the player a huge list of possibilities at every single spot, as long as the list isn't too huge, a random code will almost certainly limit the number of matching messages to a very small, predictable number.

The Analogy:
Imagine you are trying to guess a friend's phone number.

The "Bad" Scenario: If the number follows a predictable pattern (like 1-2-3-4...), and you have a list of 100 possibilities for each digit, you might find thousands of numbers that fit the pattern.
The "Good" (Random) Scenario: If the number is truly random, and you have a list of 100 possibilities for each digit, the math shows that it is extremely unlikely that more than a handful of numbers will fit the pattern perfectly. The randomness acts like a filter, crushing the number of "false alarms."

How They Proved It: The Detective's Toolkit

The authors didn't just guess; they built a mathematical detective story using three main tools:

The Graph Detective: They turned the problem into a map (a graph). If there were too many "fake" messages fitting the lists, the map would have to look a very specific, messy way.
The Tree Builder: They showed that if the map is messy enough, you can always find a set of "trees" (branching paths) that don't share any colors.
The Magic Formula: They used a special algebraic formula (a determinant) that acts like a truth serum. If the trees exist and the formula isn't zero, it proves that all the "fake" messages must actually be the same message. Since they started with different messages, this creates a contradiction, proving that the "fake" messages couldn't have existed in the first place.

They also used a famous math trick called the Schwartz–Zippel lemma, which essentially says: "If you pick numbers randomly from a big pool, it's almost impossible for a complex equation to accidentally equal zero." This ensured their "truth serum" worked.

The Limit: Why You Can't Cheat the System

The paper also has a "reality check" section. They proved that if you make the lists of possibilities too big (exponentially huge compared to the message length), then no code can save you. Even a random code will fail, and you will be flooded with too many possible answers.

Think of it like a lock:

If the lock is random and the key is slightly wrong (small list), the lock still works.
If you give the lockmaster a list of every possible key in the universe, the lock is useless because everything fits.

The Human-AI Collaboration Twist

The authors added a fascinating note about how they wrote this paper. They started with a human idea and a "less optimal" proof. Then, they asked an AI (specifically a tool called "Moonshot AI" using GPT-5.5Pro) to help.

The AI didn't just fix typos; it completely rewrote the proof, making it stronger and more elegant than the human version. The authors emphasize that the question was human, but the solution was a collaboration where the AI's mathematical reasoning surpassed their own.

Summary

In short, this paper proves that randomness is a powerful shield. If you build a communication code randomly, it is nearly perfect at filtering out false matches, even when you have a lot of uncertainty about what the message should look like. The only way to break this shield is to make the uncertainty so massive that the system is overwhelmed, which the authors show is the absolute limit of what is possible.

Technical Summary: List Recovery for Random Low-Rate Linear Codes

Problem Statement

This work investigates the list recovery properties of random linear codes over sufficiently large prime fields $\mathbb{F}_p$ . Specifically, the authors study the regime where the code dimension $d$ is fixed while the block length $n$ tends to infinity (an essentially zero-rate regime).

The central problem is defined via $(\alpha, \ell, L)$ -list recoverability: A code $C \subseteq \Sigma^n$ is $(\alpha, \ell, L)$ -list recoverable if, for any input lists $S_1, \dots, S_n \subseteq \Sigma$ of size $\ell$ , there are at most $L$ codewords $x \in C$ such that the number of coordinates where $x_i \notin S_i$ is at most $\alpha n$ .

The paper addresses the behavior of random $d$ -dimensional linear codes $C \subseteq \mathbb{F}_p^n$ when the input list size $\ell$ grows with $n$ . The goal is to determine the maximum $\ell$ for which the output list size $L$ remains small (specifically, close to the information-theoretic lower bound of $\frac{1+\epsilon}{1-\alpha \ell}$ ).

Methodology

The proof strategy bridges combinatorial graph theory and algebraic geometry, inspired by the work of Matoušek, Pˇr´ıvˇetiv´y, and Škovroˇn on reconstructing point sets from projections. The methodology proceeds through four main stages:

Graph-Theoretic Reduction:
The authors translate the failure of list recovery into a problem on edge-colored multigraphs. If a code fails to be list recoverable, there exists a set of messages $A$ whose codewords land in prescribed lists for most coordinates. This structure implies that for many coordinates, pairs of points in $A$ map to the same value (lie in the same fiber of the coordinate linear form). These pairs form matchings, and the coordinates act as edge colors. A failure of list recovery thus yields a graph where many color classes are large matchings.
Deterministic Graph Certificate:
Using a maximal-density induced subgraph argument, the authors prove that if a graph has many color classes that are large matchings, one can find a subset of vertices supporting $d$ spanning trees with pairwise disjoint color sets. This is established via a probabilistic argument showing that random subsets of colors connect the graph under suitable expansion hypotheses (Lemma 5 and Lemma 6).
Algebraic Certificate (Non-vanishing Determinant):
The $d$ disjoint spanning trees are converted into an algebraic system. The edges of these trees impose linear equations on the differences between the points in $A$ . Because the trees have disjoint color sets, the resulting system matrix has a determinant that is a non-zero polynomial in the coefficients of the linear forms defining the code.
By the Schwartz–Zippel lemma, if the linear forms (the code generator matrix entries) are chosen uniformly at random from a sufficiently large field, the probability that this determinant vanishes is negligible. If the determinant is non-zero, the system forces all points in the certificate to coincide, contradicting the assumption that $A$ contains distinct messages.
Lower Bound Construction:
To show optimality, the authors construct a counter-example for any linear code of dimension at least two when the list size $\ell$ is exponential in $n$ ( $\ell \ge 2^{\Omega(n)}$ ). They utilize a two-dimensional subcode and construct a "generalized arithmetic box" (a set of codewords formed by linear combinations of basis vectors with bounded coefficients). This set is designed such that its projections onto every coordinate are small (size $\le \ell$ ), yet the set itself contains more than the allowed number of codewords.

Key Contributions and Results

Main Theorem (Upper Bound)

The paper proves that for fixed dimension $d$ , error fraction $\alpha$ , and accuracy $\epsilon$ , a random $d$ -dimensional linear code over a sufficiently large prime field is $(\alpha, \ell, \frac{1+\epsilon}{1-\alpha \ell})$ -list recoverable with high probability.

Scope: This holds simultaneously for all input list sizes $\ell$ up to $2^{\delta n / \log n}$ for some constant $\delta > 0$ .
Optimality: The dependence on $n$ in the list size bound is nearly optimal. The authors show that for any linear code of dimension $\ge 2$ , list recovery fails for list sizes $\ell \ge 2^{\Omega(n)}$ .

The Lower Bound

The paper establishes that no linear code of dimension at least two can be $(\alpha, \ell, \frac{1+\epsilon}{1-\alpha \ell})$ -list recoverable for feasible list sizes $\ell \ge 2^{\delta n}$ . This demonstrates that the exponential gap between the achievable list size in the random case ( $2^{n/\log n}$ ) and the failure threshold for general codes ( $2^n$ ) is a fundamental limitation of the linear structure in this regime.

Significance and Claims

The authors position this work as a study of a "complementary, essentially zero-rate random-linear-code regime" where dimension is fixed and block length grows.

Near-Optimality: The result is claimed to be "nearly optimal" because the achievable list size $\ell \approx 2^{n/\log n}$ is close to the theoretical limit where list recovery becomes impossible for any linear code of dimension $\ge 2$ .
Methodological Novelty: The proof introduces a novel combination of a deterministic graph-theoretic certificate (finding disjoint spanning trees from large matchings) and a non-vanishing determinant criterion. This approach adapts techniques from point-set reconstruction to coding theory.
AI-Assisted Proof: The authors explicitly note that while the initial results were derived via human reasoning, the final, superior proof (both quantitatively and qualitatively) was generated by an AI harness (UCLA Moonshot AI for Math using GPT-5.5Pro). They state that direct queries to the AI without human guidance failed to produce the theorem, highlighting a specific workflow where human intuition framed the problem and AI executed the complex proof synthesis.

The paper does not propose new applications or experimental proposals but focuses strictly on establishing the theoretical limits of list recovery for random low-rate linear codes.