# Differentiate polynomials in $\mathbb{Z}_2[x]$

It seems suggested that the differential of a polynomial in $\mathbb{Z}_2$ is as I would expect:

\begin{align} &f = x^6 + x^3 + x + 1 \\ &f' = 6x^5 + 3x^2 +1 \mod 2 \\ &f'= x^2 + 1 \\ \end{align}

This seems very strange because there are situations like:

\begin{align} &f=x^4 + x^2 + 1 \\ &f'=0 \\ & \\ &f=x^5 + x^4 + 1 \\ &f'=x^4 \\ & \\ &f=x^7 + x^4 + x^3 + x + 1 \\ &f'=x^6 + x^2 + 1 \\ \end{align}

but if that is correct then so be it.

Are these correct?

• Already 30 months a member. Time to learn how to properly type mathematics here, imo: meta.math.stackexchange.com/questions/5020/… – Timbuc Apr 10 '15 at 16:49
• @Timbuc - Thanks for the motivation - better? – OldCurmudgeon Apr 10 '15 at 23:40
• Debugging Java code is off-topic, but regarding formal derivative, see Wikipedia. Notice that your link to Yun's algorithm indicates that this version of the algorithm it's valid over a field of characteristic 0. – Jean-Claude Arbaut Apr 14 '15 at 12:51
• Do not forget that you are wearing the formal derivative which has nothing to do with the fundamental notion of limit and that is why they appear "strange things" sometimes. – Piquito Apr 14 '15 at 12:51
• @LuisGomezSanchez - I expect wierd stuff in a finite field but have I got them right? – OldCurmudgeon Apr 14 '15 at 12:55

## 2 Answers

What we see here is the formal derivative. If $A$ is a ring, then we can define the formal derivative $D\colon A[X]\to A[X]$ via $$D(\sum_{k=0}^n a_kX^k):=\sum_{k=0}^{n-1}(k+1)a_{k+1}X^k$$ (where $k+1$ is not an element of $\mathbb Z$, but rather viewed as the element $\underbrace{1+1+\ldots+1}_{k+1}\in A$, which may be zero $\in A$ even if it is nonzero $\in\mathbb Z$).

This looks exactly like the derivative $\frac{\mathrm d}{\mathrm dx}$ when applied to a polynomial function. However, in genreal, for example if $A$ is a finite field, we have no such thing as $\lim_{h\to 0}$ that is needed in the analytic definition of derivative. Consequently, $D$ cannot tell us things like how a function value changes if ew change the argument by a tiny amount - because in general there is no such thing as a tiny amount. Nevertheless, $D$ is a derivation and the most important rules of derivatives hold: Apart from being a linear map, we have the product rule $D(fg)=fD(g)+D(f)g$. Also, $D(a)=0$ for $a\in A$, but the converse need not be true any more.

By these facts, $D$ can still tell us things that $\frac{\mathrm d}{\mathrm dx}$ could tell us, provided they are not about the "forbidden" notion of "tiny changes". For example, $a\in\mathbb R$ is a multiple root of a polynomial function $f$ iff $a$ is a common root of $f$ and $f'$. Likewise, $f\in A[X]$ is divisible by $g^2$ (which means that any root of $g$ in either $A$ or a ring extension of $A$ is a multiple root of $f$) iff $g$ divides both $f$ and $D(f)$. Thus a simple algebraic calculation of $\gcd(f,D(f))$ gives us a polynomial that tells us where to look for multiple roots of $f$.

You had the example $f=X^4+X^2+1\in\mathbb Z_2[X]$ (or over any ring of characteristic $2$) with $D(f)=0$; thus here $\gcd(f,D(f))=f$, i.e., any root of $f$ is in fact a multiple root (there are none in $\mathbb Z_2$, but in suitable extensions); indeed, the factorization $f=(X^2+X+1)^2$ shows this explicitly.

In summary: In all your examples, you computed the formal derivative correctly and should not take the fact that "weird" things happen as an indication of error.

Yes this is correct. In fact you've noted an important result that sometimes in a field of positive characteristic, polynomials of degree >1 can vanish when you apply a formal derivative. This doesn't happen in fields of characteristic $0$. In fact, you need this idea to understand separable extensions (or more inseparable extensions) from Galois theory. This isn't really an answer, but hopefully it will give you some reason to think that your observation is significant:

Let $K$ be a field. A separable polynomial is a polynomial $p(t)\in K[t]$ such that when it is factorised into its irreducible factors, say $p(t)=\Pi_i q_i(t)$, each irreducible factor has distinct roots in its splitting field - a certain field which is large enough so that $q_i$ 'splits' into linear factors. Inseparable polynomials are very hard to find, e.g. you might think $x^2$ is an inseparable polynomial, at first glance, but $x^2=x \cdot x$ and this is still separable since each irreducible factor, $x$ has distinct roots (here it has only one root, namely $0$).

In our search for an inseparable polynomial, let's try to form an irreducible polynomial $f(t)$ in $K(t)$ with a repeated root in its splitting field $L/K$. After some fiddling with formal derivatives on $K$ and proving that things work as you'd expect (similar to what is done in Hagen von Eitzen's answer) you prove that such a polynomial must have $D(f)=0$ (the zero polynomial). If our $K$ is of characteristic $0$, i.e. an extension of $\mathbb Q$ this only happens if $f$ is of degree 1, and so $f$ is obviously separable. So we need a field of characteristic $p$, like in your examples, with $p=2$.

In these fields, we can define the Frobenius endomorphism $F:K\to K$, by $F(\lambda)=\lambda ^p$. It's a bit of a miracle that this is a homomorphism, so I'll leave the joy of the proof to you. If $F$ is surjective, then for our irreducible $f(t) \in K[t]$, let $f(t)=a_0 + a_1 t+ a_2 t^2 + \ldots +a_n t^n$. Remember we needed $D(f)=0$, so $0\equiv a_1+2a_2t+\ldots+na_nt^{n-1}$. But now because of the definition of formal derivatives, the $ia_i$ are now elements of $K$. As this polynomial is the zero polynomial, we must have that $ia_i=0$ for all $i$. So either $i=0$ or $a_i=0$ in $K$. But $i=0$ in $K$ if and only if $p | i$ in the integers, since we're in characteristic $p$. So the only times when we can have $a_i$ non-zero, is when $p|i$. Hence $f(t)=a_0+a_pt^p+a_{2p}t^{2p}+\ldots +a_{rp}t^{rp}$ for some $r \in \mathbb Z$. Now we use surjectivity of $F$: for some $b_i \in K$ we get $$f(t)=F(b_0)+F(b_p)t^p+F(b_{2p})t^{2p}+\ldots +F(b_{rp})t^{rp}\\ =b_0^p+(b_pt)^p+(b_{2p}t^2)^{p}+\ldots +(b_{rp}t^r)^{p}\\ =\left(b_0+b_pt+b_{2p}t^{2}+\ldots +b_{rp}t^{r} \right)^p$$ with the last line coming from the fact that $F$ is a homomorphism, if you think about it. But now $f$ isn't irreducible. So we have to look for our $f$ in places where $F$ is not surjective. But any finite field $K$ has $F:K \to K$ surjective. Indeed, $F$ is a field homomorphism, so it's an injective map between two sets of the same size. Thus it's surjective.

We need to have an infinite field of characteristic $p$; we try $K=\mathbb F_p(x)$ - the field of fractions of the polynomial ring $\mathbb F_p[x]$. Then $f(t)=t^p-x \in K[t]$ is irreducible (by Eisentein for the UFD $\mathbb F_p[x]$). But now if we work in a splitting field $L$ for $f$, there will necessarily be a root $\alpha\in L$ for $f$, so then $\alpha^p=x$. Then $f(t)=t^p-\alpha^p=(t-\alpha)^p$ in $L[t]$. Hence $f$ has the repeated root $\alpha$ appearing $p$ times, so $f$ is inseparable.