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.