[]# Lagrange Kate tricks
[Keccake256 aka Felix1 @ <0x64563911a4eC3A2c4f2693e79340b0af93972d32>

Let \(\omega^n=1\). Define the Lagrange polynomials
\[ L_j(x) = \prod_{i=0}^{n-1} \frac{x-\omega^j}{\omega^i-\omega^j} = \frac{A(x)}{A'(\omega^j) (x-\omega^j)} \]
where \(A(x) = x^n-1 = \prod_{i=0}^{n-1} (x-\omega^i)\) and \(A'(x)=nx^{n-1}\) is its formal derivative.

Then, for \(i \neq j\), (either using partial fraction decomposition or by decomposing in the Lagrange basis)
\[ \frac{L_i(x)}{x-\omega^j} = \frac{L_i(x)-\omega^{i-j}L_j(x)}{\omega^i-\omega^j} \]

Let’s use this to re-express quotient polynomials in the Lagrange basis: Let \(f(x)=\sum_{i=0}^{n-1} f_i L_i\). Then
\[ \frac{f(x) - f(\omega^j)}{x-\omega^j} = \sum_{i=0 \atop i \neq j}^{n-1} \frac{(f_i - f_j) L_i(x)}{x-\omega^j} = \sum_{i=0 \atop i \neq j}^{n-1} \frac{(f_i - f_j) (L_i(x)-\omega^{i-j}L_j(x))}{\omega^i-\omega^j} \]

Kate proofs in Lagrange basis

Let’s assume a trusted setup consisting of \(L_i(s) G \in G_1\), \(s H \in G_2\). Then the proof for \(f(x=\omega^j) = f_j\) can be expressed as

\[ \pi(f(x=\omega^j) = f_j) = \sum_{i=0 \atop i \neq j}^{n-1} \frac{(f_i - f_j) (L_i(s) G -\omega^{i-j}L_j(s) G)}{\omega^i-\omega^j} \]

The proof can be computed in \(n\) group operations and \(O(n)\) field operations (no Fourier transform required).

Question

Can we somehow find some intermediate values to store to make this proof cheaper to compute?

The main problem here is the factor of \(\frac{1}{\omega^i-\omega^j}\), which does not behave nicely (if all the factors were of the form \(\omega^i\) or \(\omega^j\), then FFT-like techniques could probably be used to construct the proof from a small number of precomputed elements)