Discrete derivatives

If you've taken calculus, and someone asks you what the derivative of x⁵ is, you can say without hesitation that it's 5x⁴.

Now suppose they come back and say, I'm sorry. I forgot to give you any context. Here x⁵ is a polynomial in the field of 343 elements."

It turns out that this additional information does not change your answer, but it greatly changes how things are defined.

Derivatives are defined in terms of limits, but you don't have limits over a finite field. And not only that, polynomials aren't even functions when you're working over a finite field [1].

You can define the derivative of a polynomial over any field to be just what you'd get if you were working over real numbers, if you interpreting things correctly. That works, and it's useful. You can use this derivative in a purely algebraic setting to do some of the same sorts of things you'd use a derivative for in analysis, such as determining whether a polynomial has a multiple root.

You can define the derivative of a term

axⁿ

to be

nax^n-1

and define the derivative of a polynomial to be the sum of the derivatives of each term.

Here a is an element of the base field and n is a positive integer. The expression na indicates the sum of the field element a with itself n times. (You can't just multiply an integer by an element of an arbitrary field.)

This post was motivated by a tweet from Sam Walters this morning.

[1] When you're working with polynomials over a finite field, a polynomial is not a function. You could say that a polynomial is never a function, but the distinction is usually pedantic. When you're working over an infinite field, you won't get in trouble if you think of polynomials as functions. Even over a finite field you often won't get into trouble, though sometimes you will.

The post Discrete derivatives first appeared on John D. Cook.