# Polynomials

$$\gdef\F{\mathbb{F}} \gdef\Z{\mathrm{Z}}$$

### Polynomial basis

We convert this to a polynomial problem by picking a basis $\vec x ∈ \F^n$. Define zero polynomials to mean

$$\Z_{\mathcal S}(X) = \prod_{s ∈ \mathcal S} \p{X - s}$$

When not otherwise specified, take $\mathcal S$ to be $\vec x$. Take $\overline s$ to mean the set $\vec x \setminus \set{x}$. Define Lagrange basis functions

$$L_{s}(X) = \frac{\Z_{\overline s}(X)}{\Z_{\overline s}(s)}$$

This function is zero on the set $\overline s$ and one on $s$. Take $L_i$ to mean $L_{x_i}$.

Q: Are all the multiplicative subgroups of a field roots of unity?

### A convenient polynomial basis

A computationally convenient choice for basis $\vec x$ are the $n$-th roots of unity $x_i = \mathrm{ω}_n^i$. In particular this leads to the simplification $Z(X) = X^n - 1$.

$$Z_{\overline s}(X) = \begin{cases} \frac{X^n - 1}{X - s} & X ≠ s \\ n ⋅ s^{n - 2} & X = s \end{cases}$$

Where the $X=s$ case is derived using L'Hôpital's rule.

TODO: Check the $X = s$ case.

$$L_{i}(X) = \begin{cases} \frac{\mathrm{ω}_n^{2·i}}{n} · \frac{X^n - 1}{X - ω_n^i} & X ≠ ω_n^i \\ 1 & X = ω_n^i \end{cases}$$

### Vanishing on a square

$$\Z_{\set{α ⋅ ω_n^i}}(X) = X^n - α^n$$

Ben+19b from Marlin:

which is a polynomial of individual degree |S| − 1 because X − Y divides X^i − Y^i for any positive integer i.

It is zero on $\mathcal S × \mathcal S$ except for the diagonal.

Remco Bloemen
Math & Engineering
https://2π.com