如何证明这个公式L_0(x) = Z_H(x)/(n * (x - 1))

[cliff0412]

在阅读plonk代码的时候可以看到上面的公式
Z_H(x)是vanishing poly. L_0(x)是lagrange basis 0, 分母里面的n应该是等于(1-x_1)(1-x_2)...(1-x_k)。我用(1,5,12,8) % 13这个例子可以验证这个式子确实成立，比如在这个例子里面n=4.
(1-x_1)(1-x_2)...(1-x_k) = (1-5)(1-12)(1-8) % 13 = 4 = n

如何数学上证明呢？

[KyrinCode]

请明确一下问题的出处，我感觉不记得协议里有这么个式子

[cliff0412]

公式来自这里https://github.com/0xPolygonZero/plonky2/blob/main/plonky2/src/plonk/plonk_common.rs#L59
L_0(x) = (x^n - 1) / (n * (x - 1)) = Z(x) / (n * (x - 1))
x_0 = 1, x_1 = \omega^1, x_2 = \omega^2, ...
和lagrange basis得公式比较，假如上面的公式成立可以推出
(x_0 - x_1)(x_0 -x_2)...(x_0 -x_{n-1}) = n
x_0 = 1，
所以
(1-x_1)(1-x_2)...(1-x_{n-1}) = n

根据上面举出的例子就是
(1-5)(1-12)(1-8) % 13 = 4
4刚好是sub group的order

列举另一个例子依然成立
\omega=3, P=13, H=[1,3,9], n=3
(1-3)(1-9) = 3

应该不是巧合

[MakiSonomura]

You could consider calculating the derivative of Z(x) at the point x = 1. Alternatively, consider the polynomial: Y(x) = Z(x) / (x - 1)
What you're looking for is Y(1).

[cliff0412]

thanks for your answer. i got it. that's my sketch of proof

[zilong-dai]

已知($w$的阶是n) $w^{n}=1$ , 则对于 $\forall i \in {0, 1, \ldots, n -1}$, 有 $(w^{i})^{n} - 1 = (w^{n})^{i} - 1 = 0$. 又 $1, w, \ldots, w^{n-1}$ 互不相等, 则 $1, w, \ldots, w^{n-1}$ 是 $x^{n} - 1$ 的 n 个根.

[KyrinCode]

Received.Kyrin