渐进RS MCA问题最终版代码已发布GitHub

The final push towards Asymptotic RS MCA just landed on Github and I think it's a beautiful piece of mathematics merging moduli viewpoint with deep additive combinatorics results of Tao and Gowers.

So let me take a step back and explain what we're doing with Proximity Prize.

A Reed-Solomon code is a way of encoding a low-degree polynomial by evaluating it at many points. It is one of the basic error-correcting codes behind FRI, STARKs, and many polynomial-commitment protocols.

The RS MCA problem asks something like this: if you take two received words and look at random linear combinations of them, how often can that combination look close to a Reed-Solomon codeword even though the two original words do not share a common Reed-Solomon explanation? This matters because proximity tests and proof systems often rely on the idea that random lines through received words behave predictably.

Our asymptotic result says that for smooth Reed-Solomon domains, the critical radius is controlled by a simple entropy balance. There are many possible agreement sets, and there are also base-field constraints that those sets must satisfy. The threshold is the point where those two counts balance.

In plain language: below the threshold, there are enough possible agreement sets that many bad MCA challenges can be constructed. Above the threshold, the constraints dominate, and bad challenges become too rare.

The important conceptual point is that the threshold is governed by the base/generated field of the domain, not just by the larger extension or challenge field. So using a huge extension field does not automatically make the MCA problem safe up to Reed-Solomon capacity.

The proof has two parts:

First, we explicitly build many bad examples below the entropy threshold (a lot of manual/agentic work goes here).

Second, above the threshold, we classify the structured ways bad examples can happen, and then use additive combinatorics to rule out the remaining unstructured cases (I'm quite excited by using Balog–Szemeredi–Gowers result here).

This is a solution claim that still needs to go under heavy scrutiny, cleaning, formalization in Lean and so on, but I'm happy with the conceptual part.

It's very exciting also because additive combinatorics part was my idea that I learned while attempting Erdos problems. And moduli-theoretic viewpoint is something I learned working on Langlands program during my PhD and beyond.

The work goes on.