# PLONK's computation of the first Lagrange polynomial at $\zeta$

From the PLONK paper.

On Page 31, Point 6

Compute the Lagrange Polynomial Evaluation $$L_1(\zeta) = \frac{\omega(\zeta^n - 1)} {n(\zeta- \omega)}$$

I don't think this formula is correct.

We have $$n$$ gates from $$H=\lbrace 1, \omega, \omega^2, \omega^3, ..., \omega^{n-1}\rbrace$$.

So the formula for computing $$L_1(X)$$ should be

$$L_1(X) = \frac {(X-\omega)(X-\omega^2)(X-\omega^3)...(X-\omega^{n-1})}{(1-\omega)(1-\omega^2)(1-\omega^3)...(1-\omega^{n-1})}$$

To get the $$X^n-1$$ term in the numerator, I multiply numerator & denominator by $$(X-1)$$

$$L_1(X) = \frac {(X-1)(X-\omega)(X-\omega^2)(X-\omega^3)...(X-\omega^{n-1})}{(X-1)(1-\omega)(1-\omega^2)(1-\omega^3)...(1-\omega^{n-1})}$$

It can be shown that $$X^n-1 = (X-1)(X-\omega)(X-\omega^2)(X-\omega^3)...(X-\omega^{n-1})$$

So

$$L_1(X) = \frac {X^n-1}{(X-1)(1-\omega)(1-\omega^2)(1-\omega^3)...(1-\omega^{n-1})}$$

So $$L_1(\zeta) = \frac {\zeta^n-1}{(\zeta-1)(1-\omega)(1-\omega^2)(1-\omega^3)...(1-\omega^{n-1})}$$

The above doesn't match with the formula in the paper i.e. $$L_1(\zeta) = \frac{\omega(\zeta^n - 1)} {n(\zeta- \omega)}$$

I tested with sample values also. Let's say we are in $$\mathbb F_{17}$$ & $$\omega = 4$$ which is the 4th root of unity in $$\mathbb F_{17}$$.

So $$H=\lbrace 1, \omega, \omega^2, \omega^3 \rbrace$$.

Let $$\zeta = 5$$

Using the paper's formula.

$$L_1(5) = \frac {4(5^4 -1)}{4(5-4)}$$

$$L_1(5) = 12$$

And if I use my formula

$$L_1(5) = \frac {5^4-1}{(5-1)(1-4)(1-4^2)(1-4^3)}$$

$$L_1(5) = 5$$

• How do you conclude that the paper is wrong? Numerical comparison with examples should also be done more carefully. It would better to compare the paper’s result to that of a vanilla Lagrange output rather than the intermediate formula in question which hasn’t been proven equivalent to the Lagrange polynomial. Aug 21, 2023 at 21:11
• @MarcIlunga I concluded it's wrong not on the basis of the numerical example but based on the formula for calculation of Lagrange bases. I have shown what I think is the right way to calculate $L_1(\zeta)$ in my question - that's how Lagrange bases are calculated . The numerical example isn't to show that it's wrong but to show that my way & their way aren't equivalent. Aug 21, 2023 at 23:58
• The issue is that youut $L_1$ does not compute the right polynomial. Recall that $L_i$ should be one only for $\omega^i$. In your case you are computing $L_0$ instead. Aug 22, 2023 at 5:40
• @MarcIlunga $L_1$ here is the first lagrange base - they are indexing from $1$ & not from $0$. If you check the formula in Round 2, it uses $L_1$ at the beginning & then $L_2$ to $L_n$ inside the $\sum$. Since there are only $n$ gates, there are $n$ Lagrange bases. If there was an $L_0$ also, you will end up with $n+1$ Langrange Bases which would be wrong. Aug 22, 2023 at 5:54
• We are working in a subgroup of order $n$ so $L_n$ is effectively $L_0$. Stated differently, you are computing $L_n$ instead of $L_1$. Please review the definition of $L_i$ and recompute it for $i = 1$, meaning $\omega^1$. Aug 22, 2023 at 6:12

Given the subgroup $$H=\lbrace 1, \omega, \omega^2, \omega^3, ..., \omega^{n-1}\rbrace$$ of order $$n$$, the Lagrange basis of this subgroup is given by the set of polynomials $$\lbrace L_i \rbrace_{i=1}^n$$ such that $$L_i(w^k) = 1$$ if and only if $$i=k$$ and $$0$$ otherwise.

The well-known interpolation methods gives $$L_i(x) = \frac{\prod_{k \neq i}(x - \omega^k)}{\prod_{k \neq i}(\omega^i - \omega^k)}$$.

As per the definitions of the basis, the $$L_1$$ expression in the question $$L_1(X) = \frac {(X-\omega)(X-\omega^2)(X-\omega^3)...(X-\omega^{n-1})}{(1-\omega)(1-\omega^2)(1-\omega^3)...(1-\omega^{n-1})}$$ does not compute the correct value and is instead computing $$L_n$$ ($$L_0$$ given that $$\omega^n = \omega^0 = 1)$$.

$$L_1(x)$$ should instead be $$L_1(X) = \frac {(X-1)(X-\omega^2)(X-\omega^3)...(X-\omega^{n-1})}{(\omega-1)(\omega-\omega^2)(\omega-\omega^3)...(\omega-\omega^{n-1})}.$$

Using the numerical example, it can be verified that $$L_1(5) = 12$$, which corresponds to $$L_1(5) = \frac {4(5^4 -1)}{4(5-4)}$$.

This can also be verified using the sagemath snippet below

F = GF(17)
w = F(4)
s = 5
idxs = lambda i: [k for k in range(4) if i != k]
li = lambda i,x: prod([x - w^k for k in idxs(i)])/prod([w^i - w^k for k in idxs(i)])
# Sanity check
[[li(j,w^i) for i in range(4)] for j in range(4)]
# L_i(s)
print([li(i,s) for i in range(4)])


The output is [5, 12, 8, 10]. Which also shows that $$5$$ the result of $$L_n(5)$$.

Now, what about the connection between the "normal" Lagrange polynomial and the one defined in the paper? The paper "Fractal: Post-Quantum and Transparent Recursive Proofs from Holography" explained this. At a high level, the vanishing polynomial $$Z_H(x)$$ for $$H$$ and the polynomials $$L_i$$ are quite related.

Indeed, $$Z_H$$ is almost the same as $$Z_H(x)/(x-\omega^i)$$. But, not quite, since the latter polynomial does not evaluate to $$i$$ in $$\omega^i$$, so we need some normalization.

Consider the derivative of $$Z_H(x)$$, when evaluated at $$w^i$$ we get $$Z_H'(w^i) = 1\times\prod_{k \neq i}(\omega^i - \omega^k) + (w^i-w^i)\times\text{stuff} = \prod_{k \neq i}(\omega^i - \omega^k).$$ Consequently, we can see that $$L_i(x) = \frac{1}{Z_H'(\omega^i)} \frac{Z_H(x)}{(x-w^i)}.$$

And $$L_1(x) = \frac{1}{n\omega^{-1}} \frac{x^n - 1}{(x-w)}.$$

• thanks for getting to this, nice answer, I guessed the derivative had to be involved but had no time to go through the steps Aug 22, 2023 at 16:18
• @kodlu, it was a nice excuse to look deeper into PLONK : ) Oct 5, 2023 at 10:30
• Is there any intuition to this another expression of Lagrange polynomial? Jan 13 at 15:40