Paper 2026/1432

Reed–Solomon Mutual Correlated Agreement Beyond the Johnson Radius

Abstract

Mutual correlated agreement (MCA) bounds how many points on an affine line of received words can agree with codewords on many coordinates when the line does not admit a common codeword explanation on those coordinates; the corresponding line parameters are called bad. MCA arises in the soundness analysis of code-based proof systems. For Reed-Solomon codes with arbitrary prescribed evaluation sets, existing deterministic bounds apply only at integer error budgets strictly below the exact Johnson boundary. Fix integers $r\ge2$ and $h\ge1$. For every sufficiently large $K$, let $L\subseteq\mathbb{F}_q$ be any set of $n=rK$ distinct points and set $C=\operatorname{RS}_{<K}(\mathbb{F}_q,L)$. At error budget $E=\left\lfloor{n-\sqrt{n(K-1)}}\right\rfloor+h$, we prove that every affine line has at most $O_{r,h}(K^6)$ bad parameters. Hence \[ \varepsilon_{\mathrm{mca}}(C,E)=O_{r,h}(K^6/q). \] Thus, at each fixed rate $1/r$, any fixed number of integer steps beyond Johnson admits a deterministic polynomial bound on the number of bad parameters; in relative-radius units, the gain is $O(1/n)$. We also derive a MCA upper bound for maximum distance separable (MDS) codes from a sharp lower bound on the number of rejected local membership tests. For Reed-Solomon codes over sufficiently large fields, the resulting endpoint bound is exact whenever at most $K+1$ agreements are required. It yields exact $2^{-128}$ thresholds for four explicit smooth-domain codes of length $64$: we identify the largest safe integer budget and prove that the next one is unsafe. As a concrete application to the Grand MCA Challenge, we exhibit a single prime field $\mathbb{F}_Q$, with $Q<2^{256}$, that supports the required smooth domains at all four target rates. With $K=2^{18}$, the first post-Johnson budget has MCA error below $2^{-128}$ at rates $1/2,1/4,1/8,$ and $1/16$, as does the second such budget at rate $1/8$.