Evaluation Basis

\gdef\vec#1{\bm{#1}} \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\Mod#1{\delim[{#1}]} \gdef\F{\mathbb{F}} \gdef\G{\mathbb{G}} \gdef\g{\mathrm{g}} \gdef\NTT{\mathsf{NTT}} \gdef\MSM{\mathsf{MSM}} \gdef\Mul{\mathsf{Mul}} \gdef\Mulc{\mathsf{Mul}^{\mathsf{C}}} \gdef\Add{\mathsf{Add}} \gdef\D#1{\mathrm{\partial}_{#1}} \gdef\Z{\mathrm{Z}} \gdef\T{\mathsf{T}} \gdef\I{\mathrm{I}} \gdef\J{\mathrm{J}} \gdef\ω{\mathrm{ω}} \gdef\diag{\operatorname{diag}} \gdef\set#1{\delim\{{#1}\}}

Given a finite field \F_q we can construct a polynomial ring \F[X].

Fermat's little theorem: X^q-X has as roots all of

https://en.wikipedia.org/wiki/Frobenius_endomorphism

If \F is a prime field or order p then \Z_{\F}(X) = X^p - X has as roots all elements of \F.

https://en.wikipedia.org/wiki/Fermat%27s_little_theorem

\Z_{\F}'(X) = p⋅X^{p-1} - 1 = -1

\delim\vert{\F_q[X]_{<n}}\vert = q^n

\F_q[X]_{<n} \sim \F_q^n

\delim\vert{\F_q → \F_q}\vert = q^q

Basis for \F_q[X].

E_a(X) = \frac{\Z_{\F \setminus \set{a}}(X)}{\Z_{\F}'(a)} = -\frac{X^p - X}{X - a}

Idea. Since X^{q-1} is 0 for X=0 and 1 otherwise we have E_0(X) = 1 - X^{q-1}. Furthermore we have E_a(X) = E_0(X-a). This gives

\begin{aligned} 1 - \p{X-a}^{q-1} &= -\frac{X^q - X}{X - a} \\ \p{X-a} - \p{X-a}^q &= -\p{X^q - X} \\ X-a - \p{X-a}^q &= -X^q + X \\ \p{X-a}^q &= X^q - a \\ \end{aligned}

Which is a basic consequence of the Frobenius endomorphism and Fermat's little theorem.

This creates a map from functions over \F to \F_q[X]_{<q}. Given f(x) the equivalent P(X) is

P(X) = \sum_{a∈\F} f(a) ⋅ E_a\p{X}

\Z_{\F}(X) = X^p - X

So we can not distinguish between \F_q[X] and \F_q[X]/\p{X^q-X} by evaluations. But what about the differential operator \D{X}? Can it somehow shift in the X^q and higher terms?

\D{X} X^q = q⋅X^{q-1}

and since q = 0 in \F_q this is also zero. So the differential operator also does not distinguish.

Question. How does this work in extension fields? We would already have p = 0 not q = p^n.

A derivative operator is a linear map that satisfies \D{X}\p{a⋅b} = \D{X}\p{a}⋅b + a⋅\D{X}\p{b}.

Question. Given that every function can be represented by a polynomial. How does the multiplicative inversion operator look?

Q(X) = \frac{1}{P(X)}

We can start simple by \frac 1X:

\begin{aligned} P(X) &= \sum_{a∈\F} f(a) ⋅ E_a\p{X} \\ &= - \sum_{a∈\F} \frac 1a ⋅\frac{X^p - X}{X - a} \\ \end{aligned}

Question. Or the applicative-inversion operator.

Q(X) = P^{-1}(X)

Monomial basis

Given a field \F and a polynomial ring \F[X] over it. A n-term polynomials P∈\F[X] can be written in monomial form

P(X) = c_0 + c_1 ⋅ X + c_2 ⋅ X^2 + ⋯ + c_{n-1} ⋅ X^{n-1}

where \vec c ∈ \F^n is the vector of coefficients. This is a basis in the linear algebra sense as we can construct a vector \vec m ∈ \F[X]^n such that P is the inner product \vec c ⋅ \vec m. Such a \vec m is called a standard basis.

P(X) = \begin{bmatrix} c_0 \\ c_1 \\ c_2 \\ ⋮ \\ c_{n-1} \end{bmatrix} ⋅ \begin{bmatrix} 1 \\ X \\ X^2 \\ ⋮ \\ X^{n-1} \end{bmatrix}

Zero polynomial

Polynomials that can be factored into a constant linear factors are called splitting.

P(X) = a⋅(X - x_0)⋅(X - x_1)⋅⋯⋅(X - x_{n-1})

the set \mathcal S \subset \F are called roots as P(x) = 0 iff x ∈ \mathcal S. Define the zero polynomial over a set \mathcal S as

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

this is the minimal polynomial such that

\forall_{x ∈ \mathcal S}\quad \Z_{\mathcal S}(x) = 0

the roots allow for some set theoretic operations (todo. generalize to multisets)

\begin{aligned} \Z_{\mathcal A \cup \mathcal B}(X) &= \frac{\Z_{\mathcal A}(X)⋅\Z_{\mathcal B}(X)}{\Z_{\mathcal A ∩ \mathcal B}(X)} & \Z_{\mathcal A \setminus \mathcal B}(X) &= \frac{\Z_{\mathcal A}(X)}{\Z_{\mathcal A ∩ \mathcal B}(X)} \\ \end{aligned}

in particular for x ∈ \mathcal S:

\Z_{\mathcal S \setminus \set{x}}(X) = \frac{\Z_{\mathcal S}(X)}{X - x}

Derivative

The derivative of \Z_{\mathcal S} can be found using the product rule or the logarithmic derivative

\begin{aligned} \Z_{\mathcal S}'(X) &= \sum_{x∈\mathcal S} \Z_{\mathcal S \setminus \set{x}}(X) = \sum_{x∈\mathcal S} \frac{\Z_{\mathcal S}(X)}{X - x} = \Z_{\mathcal S}(X) ⋅ \sum_{x∈\mathcal S} \frac{1}{X - x} \end{aligned}

The first form is suitable to evaluate on the domain \mathcal S, which has an elegant result:

\begin{aligned} \forall_{x ∈ \mathcal S}\quad \Z_{\mathcal S}'(x) = \Z_{\mathcal S \setminus \set{x}}(x) \end{aligned}

Specific values

If \mathcal S are the n-th roots of unity \mathcal Ω_n = \set{1, ω_n, ω_n^2, …, ω_n^{n-1}} the zero polynomial has a sparse monomial form:

\begin{aligned} \Z_{\mathcal Ω_n}(X) &= X^n - 1 &\quad \Z_{\mathcal Ω_n}'(X) &= n⋅X^{n-1} \end{aligned}

If \mathcal S is the sequence [0,n) = \set{0,1,2,…,n-1} the zero polynomial is the falling factorial. For (-n, 0] it is the rising factorial:

\begin{aligned} \Z_{[0,n)}(X) &= X^{\underline{n}} &\quad \Z_{(-n,0]}(X) &= X^{\overline{n}} & \end{aligned}

These are related to the factorial and gamma function

\begin{aligned} \Z_{[0,n)}(X) &= \frac{\Gamma\p{X + 1}}{\Gamma\p{X - n + 1}} &\quad \Z_{(-n,0]}(X) &= \frac{\Gamma\p{X + n}}{\Gamma\p{X}} \end{aligned}

In general they have lots of uses in combinatorics and umbral calculus (todo explore)

Evaluation basis

Given an evaluation domain \vec x ∈ \F^n containing n distinct elements, we can also represent P uniquely by its evaluations \vec y ∈ \F^n on this domain y_i = P(x_i).

We can again construct a standard basis \vec L ∈ \F[X]^n, in this case called a Lagrange basis

L_i(X) = \frac{\Z_{\vec x \setminus \set{x_i}}(X)}{\Z_{\vec x \setminus \set{x_i}}(x_i)} = \frac{\Z_{\vec x \setminus \set{x_i}}(X)}{\Z_{\vec x}'(x_i)}

these satisfy L_i(x_j) = δ_{ij}.

If we define normalization constants l_i = \p{Z_{\vec x \setminus \set{x_i}}(x_i)}^{-1} then we get the barycentric form:

L_i(X) = \Z_{\vec x}(X)⋅\frac{l_i}{X - x_i}

this form is useful for evaluating the basis in x∉\vec x as Z_{\vec x}(x) can be computed once. The fraction is ill-defined on \vec x though, so this form is more appropriate

L_i(X) = l_i⋅\frac{\Z_{\vec x}(X)}{X - x_i}

Derivative

Say we have P(X) ∈ \F[X] represented in evaluations basis on domain \vec x as \vec p and we wish to know its derivative P'(X) in the same basis.

\begin{aligned} P(X) &= \sum_{i∈[0,n)} p_i ⋅ L_i(x) &\quad P'(X) &= \sum_{i∈[0,n)} p_i ⋅ L_i'(x) \end{aligned}

so to compute P'(X) in the evaluation basis we need to know L_i'(x_j). Start with computing the derivate

L_i'(X) = \sum_{x∈\mathcal S \setminus \set{x_i}} \frac{L_i(X)}{X - x}

L_i'(X) = \frac{\Z_{\vec x \setminus \set{x_i}}'(X)}{\Z_{\vec x \setminus \set{x_i}}(x_i)}

The on-diagonal elements L_i'(x_i) are

L_i'(x_i) = \frac{\Z_{\vec x \setminus \set{x_i}}'(x_i)}{\Z_{\vec x \setminus \set{x_i}}(x_i)} = \sum_{x ∈ \vec x \setminus \set{x_i}} \frac{1}{x_j - x}

The off-diagonal elements L_i'(x_j) are

L_i'(x_j) = \frac{\Z_{\vec x \setminus \set{x_i}}'(x_j)}{\Z_{\vec x \setminus \set{x_i}}(x_i)} = \frac{\Z_{\vec x \setminus \set{x_i,x_j}}(x_j)}{\Z_{\vec x \setminus \set{x_i}}(x_i)} = \frac{1}{x_j - x_i}⋅ \frac{\Z_{\vec x \setminus \set{x_j}}(x_j)}{\Z_{\vec x \setminus \set{x_i}}(x_i)} = \frac{1}{x_j - x_i}⋅ \frac{\Z_{\vec x}'(x_j)}{\Z_{\vec x}'(x_i)}

Todo. What is the rank of this matrix?

Roots of unity

On-diagonal

L_i'(\ω^i) = \frac{\Z_{Ω_n \setminus \set{\ω^i}}'(\ω^i)}{\Z_{Ω_n \setminus \set{\ω^i}}(\ω^i)} = \frac{\Z_{Ω_n \setminus \set{\ω^i}}'(\ω^i)}{\Z_{Ω_n}'(\ω^i)} = \frac{? }{n⋅\ω^{-i}}

\Z_{\mathcal A \setminus \mathcal B}'(X) = \D{X} \p{\frac{\Z_{\mathcal A}(X)}{\Z_{\mathcal A ∩ \mathcal B}(X)}} = \frac{\Z_{\mathcal A}'(X)⋅\Z_{\mathcal A ∩ \mathcal B}(X) - \Z_{\mathcal A}(X)⋅\Z_{\mathcal A ∩ \mathcal B}'(X)}{\p{\Z_{\mathcal A ∩ \mathcal B}(X)}^2}

$$ \begin{aligned} \Z_{Ω_n \setminus \set{\ω^i}}'(X) &= \frac{\Z_{Ω_n}'(X)⋅\Z_{\set{\ω^i}}(X) - \Z_{Ω_n}(X)⋅\Z_{\set{\ω^i}}'(X)}{\p{\Z_{\set{\ω^i}}(X)}^2} \ &= \frac{\p{n⋅X^{n -1}}⋅\p{X - \ω^i} - \p{X^n-1}}{\p{X - \ω^i}^2} \ &= \frac{n⋅X^{n -1}}{X - \ω^i}

• \frac{\p{X^n-1}}{\p{X - \ω^i}^2} \end{aligned} $$

Off-diagonal

L_i'(\ω^j) = \frac{1}{\ω^j - \ω^i}⋅ \frac{\Z_{Ω_n}'(\ω^j)}{\Z_{Ω_n}'(\ω^i)} = \frac{\ω^{i -j}}{\ω^j - \ω^i}

This is a Cauchy-like matrix

to do. Test these results numerically.

https://www.ams.org/journals/mcom/1988-50-181/S0025-5718-1988-0917825-9/S0025-5718-1988-0917825-9.pdf

https://link.springer.com/article/10.1007/s11075-022-01391-y

https://arxiv.org/pdf/1506.02285.pdf

CRT Basis

E_i(X) = \delim[{\frac{m_1(X)}{M(X)}}]_{m_1}⋅\frac{M(X)}{m_1(X)}

NTT Solution

Pick \vec x roots of unity and use \NTT_n to convert to monomial form. Convert back to a coset \vec y using \NTT_n. Square all values 2⋅n⋅\Mul_{\F}, convert to monomial form \NTT_{2⋅n}. We now have coefficients of P^2(X).

Basis transformations

Can every polynomial basis be written as a combination of point and derivative?

• Polynomial bases
  • Evaluation bases
    • Roots of unity bases
  • Derivative bases (Taylor series)
    • Monomial basis
  • Mixed point/derivative bases
  • https://en.wikipedia.org/wiki/Category:Orthogonal_polynomials
  • Are there more?

The conversion between monomial and roots-of-unity is the \NTT.

Multiplication by a constant polynomial

Division by a constant polynomial

Modulo operations

Derivatives

The formal derivative is a linear operator.

\D{X} P(X)

\D{X}\p{a_0 + a_1 ⋅X + a_2 ⋅ X^2 + ⋯} = a_1 + 2 ⋅ a_2 ⋅ X + 3⋅a_3⋅X^3 ⋯

Given a basis, linear operators can be expressed as a matrix. The monomial basis almost diagonalizes the derivative operator:

\begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 3 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix}

Q: Which basis diagonalizes it? Is there always such a basis?

https://en.wikipedia.org/wiki/Multiplier_(Fourier_analysis)#On_the_unit_circle

Multiplications

P(c ⋅ X)

a_0 + a_1⋅(c⋅ X) + a_2 ⋅ (c ⋅ X)^2 + ⋯ = a_0 + a_1 ⋅ c ⋅ X + a_2 ⋅ c^2 ⋅ X^2 + ⋯

\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & c & 0 & 0 \\ 0 & 0 & c^2 & 0 \\ 0 & 0 & 0 & c^3 \\ \end{bmatrix}

Translations

P(X+δ)

a_0 + a_1⋅(X + δ) + a_2 ⋅ (X + δ)^2 + ⋯ = \p{a_0 + a_1⋅δ + a_2 ⋅δ^2 + ⋯} + \p{a_1 + 2⋅a_2⋅δ + ⋯}⋅X + \p{a_2 + ⋯} ⋅ X^2 + ⋯

(X + δ)^2 = X^2 + 2⋅δ⋅X + δ^2

Chinese Remainder Theorem

A.B mod X-1

https://en.wikipedia.org/wiki/Companion_matrix#Diagonalizability

HSS Matrices: https://mipals.github.io/pubs/matrix/hss/

Coding Theory

Reed-Solomon codes. Linear block codes that have maximal separation.

Vandermonde matrix V:

\begin{bmatrix} I & V \end{bmatrix}

Cauchy matrix C

\begin{bmatrix} I & C \end{bmatrix}

https://web.eecs.utk.edu/~jplank/plank/papers/CS-05-569.pdf

List decoding

Linear Algebra

A vector space \F^n and a matrix space \F^{n×m}.

Linear maps \F^n ⇄ \F^{n×1}, \F^n ⇄ \F^{1×n}, \F^n → \F^{n×1}. Given \vec a ∈ \F^n.

row-vector, column-vector, diagonal matrix.

\begin{aligned} \begin{bmatrix} a_0 \\ a_1 \\ ⋮ \\ a_{n-1} \end{bmatrix}, \begin{bmatrix} a_0 & a_1 & ⋯ & a_{n-1} \end{bmatrix}, \begin{bmatrix} a_0 & 0 & ⋯ & 0 \\ 0 & a_1 & ⋯ & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & ⋯ & a_{n-1} \end{bmatrix} \end{aligned}

row-major order, column-mjor order, z-order

https://en.wikipedia.org/wiki/Row-_and_column-major_order

\F^{n⋅m} ⇄ \F^{n×m}

\begin{aligned} \begin{bmatrix} a_0 & a_1 & ⋯ & a_{n-1} \\ a_n & a_{n+1} & ⋯ & a_{2⋅n - 1} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{(m-1)⋅n} & a_{(m-1)⋅n + 1} & ⋯ & a_{n⋅m-1} \end{bmatrix}, \begin{bmatrix} a_0 & a_n & ⋯ & a_{(m-1)⋅n-1} \\ a_1 & a_{n+1} & ⋯ & a_{(m-1)⋅n - 1} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n-1} & a_{2⋅n - 1} & ⋯ & a_{n⋅m-1} \end{bmatrix} \end{aligned}

https://en.wikipedia.org/wiki/Z-order_curve

CRT order. As in Good-Thomas FFT.

n → (\Mod{n}_{m_1},\Mod{n}_{m_2})

Permutation Matrix

Rader's permutation https://en.wikipedia.org/wiki/Rader%27s_FFT_algorithm

The multiplicative group is cyclic

\F_p^× ≅ C_{p-1}