$$ \newcommand{\ff}[0]{\mathbb{F}} \newcommand{\ffOmega}[0]{\ff^\Omega} \newcommand{\ffOmegaSqrd}[0]{\ff^{\Omega^2}} \newcommand{\fxd}[0]{\ff[X]^{< d}} \newcommand{\fxdHalf}[0]{\ff[X]^{< {d/2}}} \newcommand{\RS}[0]{\mathrm{RS}} \newcommand{\RSd}[0]{\mathrm{RS}_d[\Omega]} \newcommand{\RSdHalf}[0]{\mathrm{RS}_{d/2}[\Omega^2]} \newcommand{\fo}[0]{\ff^\Omega} \newcommand{\eval}[0]{\mathrm{E}} \newcommand{\uZero}[0]{u^{(0)}} \newcommand{\uOne}[0]{u^{(1)}} \newcommand{\fZero}[0]{f^{(0)}} \newcommand{\fOne}[0]{f^{(1)}} $$
An important step in the soundness analysis of the FRI-IOPP is bounding the probability of an “unlucky fold”: assuming that the prover is cheating (so that the initial oracle is $\delta$-far from the code), how likely is it that the verifier “unluckily” chooses a folding challenge $\alpha \in \ff$ such that the $\alpha$-folding of the oracle is not $\delta$-far from its code? We describe here how to bound this probability using the Correlated Agreement Theorem from [PG-RSC].
Notation
Let $\ff$ be a finite field and suppose $\Omega \subset \ff^\times$ is a multiplicative subgroup with even order, so that $\omega \mapsto \omega^2$ is a 2-to-1 map $\Omega \to \Omega^2$. Write $\ffOmega$ (resp. $\ffOmegaSqrd$) for the space of all $\ff$-valued functions on $\Omega$ (resp. $\Omega^2$). Denote by $\eval_\Omega$ the evaluation map $f \mapsto (f(\omega))_{\omega \in \Omega} \in \ffOmega$, and for any $d > 0$, write $\RSd = \eval_\Omega (\fxd)$ for the Reed-Solomon code consisting of evaluations of polynomials with degree less than $d$ on $\Omega$. Write $\Delta$ for the relative Hamming distance.
Define $\Theta = (\Theta_0, \Theta_1): \ffOmega \to \ffOmegaSqrd \times \ffOmegaSqrd$ by $$ (\Theta_0 u)_{\omega^2} = \frac{u_\omega + u_{-\omega}}{2}, \qquad (\Theta_1 u)_{\omega^2} = \frac{u_\omega – u_{-\omega}}{2\omega}, \qquad \forall \omega \in \Omega,\ \forall u \in \ffOmega.$$ The map $\Theta$, which operates in the evaluation domain, corresponds to the familiar even/odd decomposition of a polynomial in the coefficient domain. In particular: $$u_\omega = (\Theta_0 u)_{\omega^2} + \omega (\Theta_1 u)_{\omega^2}, \qquad \forall \omega \in \Omega,\ \forall u \in \ffOmega,$$ and so the folding $\Psi_\alpha u$ of $u \in \ffOmega$ using $\alpha \in \ff$ can be defined using $\Theta$ via: $$ \Psi_\alpha : \ffOmega \to \ffOmegaSqrd, \qquad u \mapsto (\Theta_0 u) + \alpha (\Theta_1 u), \qquad \forall u \in \ffOmega.$$
The “Correlated Agreement Theorem” $\mathrm{CAT}_{d, \Omega}$
Let $\rho = d/|\Omega|$, and write $\mathrm{CAT}_{d, \Omega}$ for the following statement, proven in [PG-RSC] (as Theorem 4.1):
Suppose that $\delta \in (0, \frac{1 – \rho}{2}]$, and that $\uZero, \uOne \in \ffOmega$ are such that $$ |\ \{ \alpha \in \ff \ |\ \Delta (\uZero + \alpha \uOne, \RSd) < \delta \}\ | \geq |\Omega|.$$ Then there exists $\Lambda \subset \Omega$ with $\frac{|\Lambda|}{|\Omega|} \geq 1 – \delta$ and $\fZero, \fOne \in \fxd$ such that $$ \fZero(\lambda) = \uZero_\lambda, \qquad \fOne(\lambda) = \uOne_\lambda, \qquad \forall \lambda \in \Lambda.$$
The Correlated Agreement Theorem & Unlucky Folds
The contrapositive of $\mathrm{CAT}_{d/2, \Omega^2}$ can be used to bound the probability of an unlucky fold as follows.
Assume that $u \in \ffOmega$ is $\delta$-far from $\RSd$. Then $$ \Delta(u, \eval_\Omega f) \geq \delta, \qquad \forall f \in \fxd.$$ Suppose (for contradiction) that there exist $\fZero, \fOne \in \fxdHalf$ and $\Lambda \subset \Omega^2$ with $|\Lambda| / |\Omega^2| \geq 1 – \delta$ and $$ \fZero (\lambda) = (\Theta_0 u)_\lambda, \qquad \fOne (\lambda) = (\Theta_1 u)_\lambda, \qquad \forall \lambda \in \Lambda.$$ Set $f(X) = \fZero(X^2) + \fOne(X^2)$ and write $\sqrt \Lambda = \{ \omega \in \Omega \ | \ \omega^2 \in \Lambda \}$. Then for any $\lambda \in \Lambda$ and either of its two square roots $\omega \in \sqrt \Lambda$: $$ f(\omega) = \fZero(\lambda) + \omega \fOne(\lambda) = (\Theta_0 u)_\lambda + \omega (\Theta_1 u)_\lambda = u_\omega,$$ and so $f \in \fxd$ and $u \in \ffOmega$ agree on a subset $\sqrt \Lambda \subset \Omega$ of density $$ \frac{|\sqrt \Lambda|}{|\Omega|} = \frac{|\Lambda|}{|\Omega^2|} \geq 1 – \delta.$$ Thus we would have that $\Delta(u, \eval_\Omega f) < \delta$, which would contradict the $\delta$-farness of $u$ from the code. Thus no such $\fZero$, $\fOne$ and $\Lambda$ exist. Therefore, by the contrapositive of $\mathrm{CAT}_{d/2, \Omega^2}$, we have that $$ |\ \{ \ \alpha \in \ff \ |\ \Delta (\Theta_0u + \alpha \Theta_1 u, \RSdHalf) < \delta \ \}\ | < |\Omega|.$$ i.e. that the probability of the folding $\Psi_\alpha u$ failing to be $\delta$-far from $\RSdHalf$ (an “unlucky fold”) is strictly less than $\epsilon = \frac{|\Omega|}{|\ff|}$.
Proving the Correlated Agreement Theorem
The Correlated Agreement Theorem, in the case where $\delta$ is at most the unique decoding radius, can be proven by running the Berlekamp-Welch decoder over the function field $\ff (\alpha)$ (where $\alpha$, transcendental over $\ff$, stands in for the folding challenge). This works since the Berlekamp-Welch decoder is really just a result from linear algebra, and so works over any field. The other ingredient is the Polishchuk-Spielman Lemma. A proof of the theorem and this lemma are given in [PG-RSC].
References
[PG-RSC]: E. Ben-Sasson, D. Carmon, Y. Ishai, S. Kopparty and S. Saraf, “Proximity Gaps for Reed–Solomon Codes,”, 2020 (pdf).