L'Hôpital rules in finite fields

Warning. "I have only proved it correct, not tried it."

Given P,Q ∈ \F[X]. Consider the fraction

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

If this fraction is \dfrac 00 indeterminate in some value α ∈ \F, we can eliminate the zeros we found:

\frac{P(X)/(X - α)}{Q(X)/(X - α)}

If necessary we can repeat this until the fraction is no longer indeterminate.

In real numbers, there is an alternative trick, where instead we differentiate the numbers:

\frac{\frac{\d}{\d X} P(X)}{\frac{\d}{\d X} Q(X)}

again, repeated as necessary. This trick can be applied in Finite Fields too, if we use formal derivatives.

Intuition suggest that L'Hospital's rule should give the same result at X = α. This essentially boils down to the following identity:

Lemma. Given P,Q ∈ \F[X] and α ∈ \F, then

\left. \frac{\frac{\d}{\d X} P(X)}{\frac{\d}{\d X} Q(X)} \right\vert_{X = α} = \left. \frac{P(X)/(X - α)}{Q(X)/(X - α)} \right\vert_{X = α}

Proof. Follows directly from below lemma.

Lemma. Given P ∈ \F[X] and α ∈ \F with P(α) = 0 then

\left. \frac{\d}{\d X} P(X) \right\vert_{X = α} = \left. \frac{P(X)}{X - α} \right\vert_{X = α}

Proof. Substitute X = U + α with \frac{\d}{\d X} = \frac{\delta U}{\delta X}\frac{\d}{\d U} = \frac{\d}{\d U}:

\left. \frac{\d}{\d U} P(U + α) \right\vert_{U = 0} = \left. \frac{P(U + α)}{U} \right\vert_{U = 0}

Write S(U) = P(U + α) such that S(0) = 0 and S(U) = s_1 U + s_2 U^2 + ⋯.

\begin{aligned} \left. \frac{\d}{\d U} S(U) \right\vert_{U = 0} &= \left. \frac{S(U)}{U} \right\vert_{U = 0} \\ \left. \frac{\d}{\d U} \left(s_1 U + s_2 U^2 + ⋯ \right) \right\vert_{U = 0} &= \left. \frac{s_1 U + s_2 U^2 + ⋯}{U} \right\vert_{U = 0} \\ \left. \left(s_1 + 2 s_2 U + 3 s_3 U^2 ⋯ \right) \right\vert_{U = 0} &= \left. \left(s_1 + s_2 U + s_3 U^2 ⋯ \right) \right\vert_{U = 0} \\ s_1 &= s_1 \end{aligned} □

Note. The left-hand side expression does not depend on α, so the differentiated polynomial will give the divided out values wherever P(X) = 0. P of \deg P = n has at most n roots and interpolates n + 1 points. P'(X) has \deg P' = n - 1 and interpolates the n roots and their associated divided out values.

Corrolary. The formal derivative of a polynomial is the polynomial that interpolates all the 'divided out zeros'.

To do. What if the the original polynomial contains zeros of higher multiplicity?

To do. What if the original polynomial contains irreducible factors of higher degree?

The above suggest a more general theorem:

Lemma. Given P ∈ \F[X] and z ∈ \F, the following holds:

\left. \frac{\d}{\d X} P(X) \right\vert_{X = z} = \left. \frac{P(X) - P(z)}{X - z} \right\vert_{X = z}

P(X) = \prod_i (X - a_i)

Can this be evaluated using dual numbers? See https://en.wikipedia.org/wiki/Dual_number .

Evaluate over \F[\bar X,Ε]/(Ε^2) with X = \bar X + Ε:

P(X) = \prod_i (\bar X + Ε - a_i)

The result will be P(\bar X) + \left(\frac{\d}{\d \bar X} P(\bar X)\right) E, i.e. the first derivative will be the coefficient of E.

Using a higher cut-off \F[\bar X,Ε]/(Ε^n), higher order derivates can be obtained.

The division function can be modified to automatically apply L'Hospital's rule when it faces a \frac 00 indeterminate. This allows an evaluation strategy that would normally fail suceed anyway when executed over the dual numbers.

Take for example the i-th Lagrange interpolants over ⟨ω⟩

\frac{X^n - 1}{X - ω^i}