2
$\begingroup$

I'm reading inner product from generalized sumcheck in baloo paper (P.13), I'm confused with $\lambda_j(0) = N^{-1}$. Can anyone shed some light?

Here's excerpt from the paper

The intuition is that for all Lagrange interpolation polynomials $\{\lambda_j(X)\}_{j=1}^{N}$ corresponding to a multiplicative subgroup H of size N, we have $\lambda_j(0) = N^{-1}$

My understanding is that Lagrange polynomials at zero would not necessarily yield $N^{-1}$, unless specifically normalized to do so, especially since they are constructed to be $1$ at their corresponding point in the subgroup and $0$ at all others.

Reference: baloo: https://eprint.iacr.org/2022/1565.pdf (see page 13 for the relevant section).

$\endgroup$
2
  • $\begingroup$ Please use mathjax and edit equations properly $\endgroup$
    – kodlu
    Jan 13 at 8:48
  • $\begingroup$ @kodlu thank you, I've modified the format $\endgroup$
    – Paul Yu
    Jan 13 at 8:57

1 Answer 1

2
$\begingroup$

In the paper (section 3.1) the polynomials $\lambda_j(X)$ specifically refer to the Lagrange basis polynomials at the $N$th roots of unity which are 0 at exactly one of the roots and zero at the others, which normalises them.

Specifically, we have $$\lambda_j(X):=\prod_{i\neq j}\frac{X-\omega_i}{\omega_j-\omega_i}.$$ Now recall that $\prod_i\omega_i=(-1)^{N+1}$, so that $\prod_{i\neq j}(-\omega_i)=\omega_j^{-1}$. Recall further that $$\prod_{i\neq 0}(X-\omega_i)=\frac{(X^N-1)}{(X-1)}=1+X+\cdots+X^{N-1}.$$

Now \begin{eqnarray}\lambda_j(0)&=&\frac{\prod_{i\neq j}(-\omega_i)}{\prod_{i\neq j}(\omega_j-\omega_i)}\\ &=&\frac{\omega_j^{-1}}{\omega_j^{-1}\prod_{i\neq j}(1-\omega_{i-j})}\\ &=&\frac1{\prod_{i'\neq 0}(1-\omega_{i'})}\\ &=&\frac1{1+1+1^2+\cdots+1^{N-1}}\\ &=&\frac1N \end{eqnarray}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.