Proximity Gaps Conjecture Fails Near Capacity over Prime Fields

This paper proves that for a specific family of Reed-Solomon codes over prime fields, the Proximity Gaps Conjecture fails at radii within $O(1/\log n)$ of the code's capacity rate, thereby formalizing a sketch by Krachun and Kazanin.

The Gist

The Big Picture: A Broken Rule of Thumb

Imagine you are trying to send a secret message using a very specific set of rules (a Reed-Solomon code). These rules are like a "magic grid" where only certain patterns of dots are allowed. If you send a message that is slightly messy (has a few errors), the receiver can usually fix it easily.

For a long time, mathematicians believed in a "Rule of Thumb" called the Proximity Gaps Conjecture. Here is how it works in plain English:

The Conjecture: Imagine you have a straight line drawn on a piece of paper. If you pick many different points along that line, and each of those points looks very close to a valid "magic pattern," then the entire line must be close to a special "double pattern" (an interleaved code).

Think of it like this: If you see a row of people, and almost every single person looks like they are wearing a uniform, you assume the whole row is a marching band. You wouldn't expect the row to be a chaotic mix of random people just because they happen to look similar individually.

This paper proves that this Rule of Thumb is WRONG when you push the system to its absolute limit (near "capacity").

---

The Analogy: The "Almost-Perfect" Line

Let's break down the specific scenario the authors created to break the rule.

1. The Setup: The Magic Grid and the Line

• The Code (The Grid): Imagine a giant checkerboard where only specific squares are "valid."
• The Line: Imagine drawing a straight line across this board. This line represents a mathematical formula ($f + zg$). As you change the variable $z$, you move along the line.
• The "Near-Codewords": The authors found a specific line where, if you stop at many different spots along the line, each spot looks almost like a valid checkerboard pattern. It's so close that a computer would say, "This is definitely a valid pattern, just with a tiny bit of noise."

2. The Surprise: The Line is a Lie

According to the old Rule of Thumb (the Conjecture), if all those spots look valid, the entire line should be a "valid double pattern."

The authors proved this is false.
They showed a line where:

• Spot A: Looks 99% like a valid pattern.
• Spot B: Looks 99% like a valid pattern.
• Spot C: Looks 99% like a valid pattern.
• ...and so on for hundreds of spots.

BUT, the line itself is not a valid pattern. It's a "fake" line that just happens to pass through many valid-looking spots by pure coincidence. It's like a line of people who all happen to be wearing red shirts, but they aren't a marching band; they are just random people who bought red shirts at the same store.

How Did They Do It? (The Recipe)

The authors didn't just guess; they built a mathematical machine to create this "fake line." They used two main ingredients:

Ingredient 1: The "Group Hopping" Trick

They used a mathematical structure called a multiplicative subgroup.

• Analogy: Imagine a clock with 100 hours. If you only look at the numbers that are multiples of 5 (5, 10, 15...), you get a specific pattern.
• They created a line where the "errors" (the parts that make the pattern invalid) are hidden in a way that, when you add them up in specific groups, they cancel each other out perfectly on most of the board. This makes the line look valid at many points, even though it isn't.

Ingredient 2: The "Prime Number Lottery"

To make sure this trick works, they needed to find a specific type of number (a prime number) that acts as the "size" of their board.

• They needed a prime number that is huge, but not too huge, and has a very specific relationship with the size of their code.
• They used a famous math tool called Linnik's Theorem (which is like a map for finding prime numbers in specific neighborhoods).
• They proved that there are enough "good" prime numbers out there to guarantee that they can build this fake line without the math collapsing.

Why Does This Matter?

You might ask, "Who cares if a math rule breaks?"

1. It Defines the Limits: This paper tells us exactly how close we can get to the "perfect" transmission rate before the rules of error correction start to break down. It's like finding the exact speed limit where a car's tires start to lose grip.
2. Security and Cryptography: Many modern encryption systems rely on these codes. If we thought the "Rule of Thumb" was always true, we might have built security systems that are weaker than we thought. Knowing where the rule fails helps us build stronger locks.
3. Data Storage: When we store data on hard drives or in the cloud, we use these codes to fix corrupted bits. This research helps engineers understand the absolute worst-case scenarios for data corruption.

Summary in One Sentence

The authors proved that you can draw a mathematical line that passes through hundreds of "almost perfect" data patterns, yet the line itself is completely broken, shattering the long-held belief that "if many points look right, the whole line must be right" when you are operating at the very edge of what is mathematically possible.

Technical Summary

1. Problem Statement

The paper addresses the Proximity Gaps Conjecture in the context of Reed–Solomon (RS) codes over prime fields.

• The Conjecture: Introduced in prior work [2], the conjecture posits that if a significant fraction of points on an affine line $f + zg$ are "close" to a Reed–Solomon code $\mathcal{C}$, then the entire line must be "explained" by a nearby codeword pair. Specifically, the pair $[f, g]$ should be close to the corresponding interleaved Reed–Solomon code $\mathcal{C}^2$ (a condition known as correlated agreement).
• The Gap: While this phenomenon is well-understood up to the Johnson bound, its behavior in the regime above the Johnson bound but near the information-theoretic capacity ($1 - k/n$) remains unclear.
• The Objective: The authors aim to disprove the conjecture in the near-capacity regime. They seek to construct a family of RS codes where there exists a line containing many points close to the code, yet the line itself is not close to the interleaved code (i.e., correlated agreement fails).

2. Methodology

The proof is a constructive counterexample combining coding theory and quantitative number theory. The methodology proceeds in two main stages:

A. Coding-Theoretic Construction (The Counterexample)

The authors construct a specific line $L = \{f + \lambda g \mid \lambda \in \mathbb{F}_p\}$ within the space of words $\mathbb{F}_p^D$.

• Parameters: They define a code $\mathcal{C} = \text{RS}[\mathbb{F}_p, D, k]$ where $D$ is a multiplicative subgroup of $\mathbb{F}_p^*$ generated by a primitive $n$-th root of unity.
• The Line: The functions are chosen as monomials: $f = X^{rm}$ and $g = X^{(r-1)m}$.
• The Mechanism:
  1. They define a set $H$ (a subgroup) and consider sums of $r$ distinct elements from $H$.
  2. For any $\lambda$ formed by such a sum, the polynomial $X^{rm} - \lambda X^{(r-1)m}$ vanishes on a large subset of $D$ (specifically, a union of $r$ cosets of $H$).
  3. This vanishing property implies that $f + \lambda g$ agrees with a low-degree polynomial (degree $\le (r-2)m$) on a set of size $(1-\delta)n$.
  4. Consequently, the Hamming distance $\Delta(f + \lambda g, \mathcal{C}) \le \delta$.
• Failure of Correlated Agreement: The authors prove that despite many points on the line being close to $\mathcal{C}$, the pair $[f, g]$ is far from $\mathcal{C}^2$. If correlated agreement held, $g$ would have to agree with a low-degree polynomial on a set larger than its degree allows, leading to a contradiction.

B. Quantitative Number-Theoretic Argument (Existence of Parameters)

To ensure the counterexample works, the authors must prove the existence of a prime $p$ and a sufficient number of distinct scalars $\lambda$ (sums) such that the sums do not "collide" (i.e., distinct sets of elements do not sum to the same value modulo $p$).

• Linnik's Theorem: They utilize a quantitative version of Linnik's Theorem on the least prime in an arithmetic progression. This guarantees the existence of a prime $p$ in the interval $[4s, 8s]$ such that $p \equiv 1 \pmod n$.
• Collision Avoidance: They analyze the "bad" primes that would cause distinct subset sums to collide. By bounding the resultant of specific polynomials, they show that the number of such bad primes is negligible compared to the total number of primes in the interval.
• Result: This ensures the existence of a "good" prime $p < n^A$ where the number of distinct sums $|\mathcal{H}^{(r)}|$ is polynomially large ($n^C$).

3. Key Contributions

1. Disproof of Proximity Gaps Near Capacity: The paper provides the first explicit construction showing that the Proximity Gaps Conjecture fails for Reed–Solomon codes at radii $\delta = (1 - k/n) - \Omega(1/\log n)$. This is asymptotically close to the code's capacity.
2. Explicit Parameterization: Unlike previous sketches, this work makes all bounds and parameter choices explicit. It defines the relationship between the block length $n$, dimension $k$, field size $p$, and the distance parameter $\delta$.
3. Synthesis of Fields: The proof successfully bridges algebraic coding theory (Reed–Solomon structure, multiplicative subgroups) with analytic number theory (Linnik's theorem, prime distribution in arithmetic progressions, resultants).
4. Quantitative Bounds: The authors derive specific constants ($C, \rho, A$) showing that the failure occurs for a number of points scaling as $n^C$, which is significant for list-decoding applications.

4. Main Results

Theorem 1: For any constant $C > 0$ and rate $\rho \in (0, 1/2)$, there exist infinitely many block lengths $n$ and dimensions $k$ such that:

• There exists a prime $p < n^A$ (where $A$ is a constant depending on $\rho$ and $C$).
• For the code $\mathcal{C} = \text{RS}[\mathbb{F}_p, D, k]$ with $D$ being the group of $n$-th roots of unity:
  • There exist words $f, g \in \mathbb{F}_p^D$.
  • There are at least $n^C$ distinct scalars $z \in \mathbb{F}_p$ such that the Hamming distance $\Delta(f + zg, \mathcal{C}) \le \delta$.
  • However, the distance to the interleaved code satisfies $\Delta([f, g], \mathcal{C}^2) > \delta$.
• Here, $\delta = (1 - k/n) - \Omega(1/\log n)$, meaning the failure occurs just below the capacity limit.

5. Significance

• Theoretical Limits: This result clarifies the boundary of the Proximity Gaps Conjecture, demonstrating that it does not hold all the way up to the information-theoretic limit for prime fields. It suggests that "list-decodability" or "curve-decodability" properties might fail in regimes previously thought to be safe.
• Implications for Cryptography and FRI: Reed–Solomon codes are foundational in modern cryptographic protocols, particularly FRI (Fast Reed-Solomon Interactive Oracle Proofs) used in Zero-Knowledge proofs. The failure of proximity gaps near capacity implies that certain security assumptions or soundness arguments relying on the conjecture in the high-rate, near-capacity regime may need re-evaluation.
• Concurrent Work: The paper notes that its results were used in concurrent work (Appendix A.5 of [3]) to formalize conjectures regarding the list-decodability of RS codes over prime fields, highlighting its role as a foundational building block for future research in coding theory.

In summary, Kambiré's paper rigorously demonstrates that the "proximity gap" phenomenon breaks down for Reed–Solomon codes over prime fields when approaching the code's capacity, using a sophisticated interplay of algebraic construction and prime number theory.