← All papers
First page of Affine Combiners for Reed-Solomon Proximity Gaps

Affine Combiners for Reed-Solomon Proximity Gaps

Alessandro Chiesa, Guy Weissenberg, Eylon Yogev, Kai Zhe Zheng

cs.IT Nov 11, 2026 · v2 cs.CC cs.CR
Main Reed–Solomon affine-combiner proximity gap theorem was formalized in Lean with AI assistance; Reed–Muller and equal-degree extensions are not covered.
Reed-Solomon proximity gaps establish soundness guarantees for protocols that test received words through random combinations. For length-$n$ codes over $\mathbb{F}_q$, classical scalar combiners achieve error $O(n/q)$ in the unique-decoding regime, with larger known bounds near the Johnson radius. We prove smaller error bounds using affine combiners, which combine two received words $f,g$ as $f(x)+(α+βx)g(x)$, where $α,β$ are independent uniform elements of $\mathbb{F}_q$. For output degree bound $d=ρn$, fixed $ρ\in(0,1)$ and $0<η<1-\sqrtρ$, and sufficiently large block length $n$, we prove mutual correlated agreement (MCA) with one coordinate of agreement loss at threshold $A=\lceil(\sqrtρ+η)n\rceil$, with error $O_{ρ,η}\left(\frac{1}{q}+\frac{n^2}{q^2}\right)$. The result holds over arbitrary evaluation domains in every finite field, including prime and binary extension fields. The agreement threshold can approach the Johnson threshold, beyond unique decoding. For $q\ge n^2$, our error is $O_{ρ,η}(1/q)$, an asymptotic factor-$n$ separation from scalar combiners: we prove that their worst-case MCA error is $Ω_{ρ,η}(n/q)$ at the same agreement threshold and with the same one-coordinate loss. We also prove that affine combiners incur worst-case error $Ω_{ρ,η}(n/q)$ when no agreement loss is allowed. Thus one coordinate of agreement loss is necessary for our guarantee; this relaxation of standard MCA reduces the guaranteed common agreement fraction by at most $1/n$. We also extend the result to $k$-variate Reed-Muller codes on subfield grids, obtaining MCA error $O_{ρ,η,k}(q^{-k})$ for fixed $ρ,η,k$, sufficiently large $n$, and $q\ge n^{k+1}$, with agreement loss $n^{1-1/k}$.

Reed–Solomon proximity gaps underpin the soundness of proof systems such as FRI, STIR and WHIR. Classical scalar combiners incur error O(n/q), which costs about log2 n bits of soundness.

Two received words are combined as f(x)+(α+βx)g(x), with α and β uniform and independent. The analysis treats this as restricting a bivariate table to affine lines and uses Guruswami–Sudan-style interpolation plus algebraic-geometric root counting. The proofs were AI-generated; the authors edited and verified them, and the main theorem was formalized in Lean.

Affine combiners achieve mutual correlated agreement up to near the Johnson threshold, with one coordinate of agreement loss and error O(1/q + n²/q²). Scalar combiners have worst-case error Ω(n/q), and the one-coordinate loss is shown to be necessary. An extension to Reed–Muller codes gives error O(q^{-k}), but this extension is not covered by the Lean formalization.