aszepieniec    2024-12-09 👍 2 👎

Let $f\left(X\right)$ be a trace polynomial and let $D=\left\{{\omega }^i\right|0\le i<2^k\}$ be the domain over which the trace is interpolated. We want to enforce a boundary constraint, namely that $f\left(X\right)$ takes the value $y$ in the point $z={\omega }^0=1$. To enforce this constraint, we compute the quotient $q\left(X\right)=\frac{f\left(X\right)-y}{X-z}$ and require that $q\left(x\right)$ has low degree (in addition to $f\left(X\right)$). The reason why this works is because if $f\left(z\right)\ne y$ then we get unclean division and no low-degree polynomial $q\left(X\right)$ can exist – and so it must be rejected by FRI.

The reason why it is called “interpolant” is because it is the natural generalization of single-point boundary constraints. Suppose we want to enforce two boundary constraints, a) $f\left(z_0\right)=y_0$ and $f\left(z_1\right)=y_1$. Then the interpolant is $p\left(X\right)=y_0·(X-z_1)·(z_0-z_1{)}^{-1}+y_1·(X-z_0)·(z_1-z_0{)}^{-1}$, the zerofier is $z\left(X\right)=(X-z_1)·(X-z_0)$, and the quotient is $q\left(X\right)=\frac{f\left(X\right)-p\left(X\right)}{z\left(X\right)}$. The same intuition about soundness applies.