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.