# How is $\lambda_j(0) = N^{-1}$ for Lagrange polynomials in the Baloo paper's generalized sumcheck?

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

• Please use mathjax and edit equations properly Jan 13 at 8:48
• @kodlu thank you, I've modified the format Jan 13 at 8:57

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