Score:1

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

et flag

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$

Marc Ilunga avatar
tr flag
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.
et flag
@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.
Marc Ilunga avatar
tr flag
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.
et flag
@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.
Marc Ilunga avatar
tr flag
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$.
Score:2
tr flag

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)}.$$

kodlu avatar
sa flag
thanks for getting to this, nice answer, I guessed the derivative had to be involved but had no time to go through the steps
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.