$$
\def\bell{{\boldsymbol\ell}}
$$

# Lagrange Interpolation

## Main Idea

Given the points $\{(x_i, y_i)\}$ of a function, find a polynomial that passes through the points, thus approximating the function.

For each input $x_i$ to the function, create a [Lagrange basis] polynomial that evaluates to $y_i$ on $x_i$ and $0$ on all other inputs $x_{j \neq i}$. The interpolating polynomial is the sum of these polynomials, i.e. on input $x_i$ the interpolating polynomial outputs $y_i$.

## Background

### Evaluation Form of Functions

The set of all input-output pairs for a function $f: S \rightarrow S$:
$$
f(x) = \{(x, y) \mid \forall x \in S, f(x) = y\} \quad.
$$

### Linear Factorization of Polynomials

A polynomial's roots are the set of inputs that evaluate to $0$; i.e. where the polynomial crosses the x-axis.

A reducible polynomial can be factored into a set of linear (degree-$1$) polynomials where each contains a root:
$$
f(x) = x^2 + 5x + 6 \Longrightarrow (x + 2)(x + 3) \\
\textbf{roots}(f) = \{-2, -3\} \quad.
$$

## Lagrange Basis Polynomials

Given a set $S = (x_1, \dots, x_n)$ of length $n$, Lagrange basis polynomials for $S$ are a set of $n$ polynomials $\bell(S) = \{\ell_1, \dots, \ell_n\}$ such that $\ell_i(x_i) = 1$ and $\ell_i(x_{j \neq i}) = 0$:
$$
\ell_i(x_j) = \begin{cases}
1 & \text{if } i = j \\
0 & \text{otherwise } i \neq j \\
\end{cases} \quad\quad ^\ast\text{where } i, j \in [n] \quad.
$$

Each $\ell_i$ can be thought of as a unit step function at $x_i$.

We can write each step function as a [Lagrange basis] polynomial $\ell_i$ with roots $x_{j \neq i}$ and which evaluates to $1$ at $x_i$ via:
$$
\ell_i(x) = \prod_{j \in [n] \setminus i} {(x - x_j) \over (x_i - x_j)} \quad.
$$

### Deriving the Lagrange Basis Polynomial Equation

We want to express each step function $\ell_i$ as a polynomial. We know that if $\ell_i$ is a polynomial then it contains the roots $\textbf{roots}(\ell_i) = \{x_1, \dots, x_n\} {\setminus} x_i$. The polynomial that contains the roots $x_{j \neq i}$ is:
$$
r_i(x) = \prod_{j \in [n] \setminus i} (x - x_j) \quad.
$$

The above polynomial correctly evaluates to $0$ for $n - 1$ of the inputs (the roots), but does not evaluate to $1$ at the final input $x_i$:
$$
r_i(x_i) = (x_i - x_1) \dots (x_i - x_{i - 1})(x_i - x_{i + 1}) \dots (x_i - x_n) \neq 1 \quad.
$$

If we divide the above polynomial by its output at exactly $x_i$, we create a polynomial that outputs $1$ on input $x_i$ (because the numerator will equal the denominator) and outputs $0$ on each root $x_{j \neq i}$ (because one linear factor in the numerator will equal $0$):
$$
\ell_i(x) = {r_i(x) \over r_i(x_i)} = \prod_{j \in [n] \setminus i} {(x - x_j) \over (x_i - x_j)} \quad.
$$

## Functions as Sums of Lagrange Basis Polynomials

### Constant Functions

For a single input $x_i$, the sum of all step functions evaluated at $x_i$ is $1$:
$$
\ell_1(x_i) + \dots + \ell_n(x_i) = (n - 1)0 + 1 = 1 \quad.
$$ 

Thus, the the constant function $f(x) = 1$ can be written as a sum of Lagrange basis polynomials $\bell(\{x_1, \dots, x_n\})$:
$$
\eqalign{
\text{Evaluation Form: } & f(x) &= \{(x_1, 1), \dots, (x_n, 1)\} \\
\text{Lagrange Basis Form: } & f(x_i) &= 1 \\
& & =\sum_{j \in [n]}\ell_j(x_i) = (n - 1)0 + 1
}
$$ and $f(x) = c$ can be written in Lagrange basis form by:
$$
\eqalign{
\text{Evaluation Form: } & f(x) &= \{(x_1, c), \dots, (x_n, c)\} \\
\text{Lagrange Basis Form: } & f(x_i) &= c \\
& & = c\left(\sum_{j \in [n]}\ell_j(x_i)\right) \\
& & = c(n - 1)0 + c1 \quad.
}
$$

### Non-Constant Functions

Given a non-constant function's $f(x_i) = y_i$ evaluation form $\{(x_1, y_1), \dots, (x_n, y_n)\}$, we can create a polynomial that passes through each evaluation point using a sum of scaled Lagrange basis polynomials $\bell(\{x_1, \dots, x_n\})$.

To represent a constant function $f(x) = c$ as the sum of Lagrange basis polynomials, we scaled each polynomial by a constant factor $c$. To represent a non-constant function, we scale each Lagrange basis polynomial $\ell_i$ by its own factor $y_i$.
$$
\eqalign{
\text{Evaluation Form: } & f(x) &= \{(x_1, y_1), \dots, (x_n, y_n)\} \\
\text{Lagrange Basis Form: } & f(x_i) &= y_i \\
& & = \sum_{j \in [n]} y_i\ell_j(x_i) \\
& & = 0y_1 + 0y_{i - 1} + 1y_i + 0y_{i + 1} + \dots + 0y_n \quad.
}
$$

## Lagrange Interpolation

Lagrange interpolation takes a set of input-output pairs for a function and returns a polynomial passing through each of the points. The interpolating polynomial is written as a sum of Lagrange basis polynomials for the set of function inputs.

$$
\eqalign{
\text{given: } & \{(x_1, y_1), \dots, (x_n, y_n)\} \\
\text{let: } & \bell(\{x_1, \dots, x_n\}) = \{\ell_1, \dots, \ell_n\} \ \text{ be the Lagrange basis polynomials for all known inputs} \\
\text{then: } & \text{the sum of scaled Lagrange basis polynomials } \sum_{j \in [n]} y_i\ell_j(x_i) \ \text{ is a polynomial that passes through every point } (x_i, y_i)
}
$$

## Usage in PLONK

### Multiplicative Subgroups Simplify Lagrange Bases
PLONK uses a multiplicative subgroup of a field $\mathbb{F}$, which simplifies the Lagrange-base equation.

Given a field $\mathbb{F}$ and a multiplicative subgroup $\mathbb{H} < \mathbb{F}$ which is cyclic $\mathbb{H} = \langle \omega \rangle = \{\omega^1, \dots, \omega^n\}$ having order $|\mathbb{H}| = n$, if we create Lagrange bases $\bell(\mathbb{H})$ over the subgroup $\mathbb{H}$ then the Lagrange-base equation
$$
\ell_i(X) = \prod_{j \in [n] \setminus i} {X - x_j \over x_i - x_j} = \begin{cases}
1 & \text{if } X = x_i \\
0 & \text{otherwise } X = x_{j \neq i}
\end{cases}
$$ simplifies to:
$$
\ell_i(X) = c_i {X^{n + 1} - 1 \over X - x_i}
$$ for a constant $c_i$.

### Converting the Constraint System into Polynomials

Given a PLONK constraint system is a matrix containing $n$ rows, where $|\mathbb{F}| = n$, Lagrange interpolation is used to convert a column of values from the matrix into a polynomial. Thus, the witnesses to a constraint system (columns) can be encoded as polynomials.

For example, given the cyclic field $\mathbb{F} = \langle \omega \rangle = \{\omega^1, \dots, \omega^n\}$ and a column $\boldsymbol{a} = \{a_1, \dots, a_n\} \in \mathbb{F}^n$, we create the evaluation form $\{(\omega^1, a_1), \dots, (\omega^n, a_n)\}$. We then find Lagrange basis polynomials for the input values $\bell(\mathbb{F}) = \{\ell_1, \dots, \ell_n\}$ and scale each polynomial by the value $a_i$. The sum of the scaled Lagrange basis polynomials $f(\omega^i) = \sum_{j \in [n]} a_j\ell_j(\omega^i)$ is a polynomial [the Lagrange interpolating polynomial] that outputs $a_i$ on $\omega^i$.

### Checking Constraint System Satisfaction using the Vanishing Polynomial

Given the cyclic multiplicative subgroup $\mathbb{H} = \langle \omega \rangle = \{\omega^1, \dots, \omega^n\} < \mathbb{F}$, the zero function $Z(X)$ for $\omega^i \in \mathbb{H}$ (vanishing polynomial) is the polynomial that has roots at every $\omega_i$:
$$
Z_\mathbb{H}(X) = \prod_{i \in [n]}(X - \omega^i) \quad.
$$

The PLONK constraint system contains $|\mathbb{H}| = n$ rows of the constraint:
$$
s_lx_l + s_rx_r + s_ms_ls_r = s_ox_o + c
$$ which forms a matrix with columns $\boldsymbol{x_l}, \boldsymbol{x_r}, \boldsymbol{x_o}, \boldsymbol{s_l}, \boldsymbol{s_r}, \boldsymbol{s_m}, \boldsymbol{s_o}, \boldsymbol{c}$. If each column is interpolated as a polynomial, e.g. $\boldsymbol{x_l}$ would be interpolated as $f_{x_l}(X) = \sum_{j \in [n]} x_{l, j}\ell_j(X)$ where $\ell_i \in \bell(\mathbb{H})$, then the equation to check that the constraint system is satisfied is:
$$
f_{s_l}(X)f_{x_l}(X) + f_{s_r}(X)f_{x_r}(X) + f_{s_m}(X)f_{x_l}(X)f_{x_r}(X) = f_{s_o}(X)f_{x_o} + f_c(X)
$$ which is equivalent to the zero polynomial modulo the vanishing function:
$$
f_{s_l}(X)f_{x_l}(X) + f_{s_r}(X)f_{x_r}(X) + f_{s_m}(X)f_{x_l}(X)f_{x_r}(X) - f_{s_o}(X)f_{x_o} - f_c(X) = 0 \text{ mod } Z_\mathbb{H} \quad.
$$

Thus, to check that the constraint system is satisfied, we check this single equality (does the sum of polynomials have a remainder $\text{mod } Z_\mathbb{H}$) using a polynomial commitment scheme.