## Monthly Archives: January 2012

### f(x)ᵖ = f(xᵖ) over ZZ/(p)

Prove that $f(x)^p = f(x^p)$ for all $f(x) \in \mathbb{F}_p[x]$.

Let $f(x) = \sum c_ix^i$. Remember that the elements of $\mathbb{F}_p$ are precisely the roots of $x^p-x$; in particular, $\alpha^p = \alpha$ for all $\alpha \in \mathbb{F}_p$.

Then $f(x)^p = (\sum c_ix^i)^p$ $= \sum (c_ix^i)^p$ $= \sum c_i^p(x^i)^p$ $= \sum c_i (x^p)^i$ $= f(x^p)$ as desired.

### Over an imperfect field of characteristic p, there exist irreducible inseparable polynomials

Let $K$ be an imperfect field of characteristic $p$. Prove that there exist irreducible inseparable polynomials over $K$. Conclude that there exist inseparable finite extensions of $K$.

Let $\alpha \in K$ be an element which is not a $p$th power in $K$, and let $\zeta$ be a root of $x^p-\alpha$. In particular, $\zeta \notin K$. Now consider $q(x) = (x-\zeta)^p = x^p-\alpha$. Suppose $t(x)$ is an irreducible factor of $q$ over $K$. Now $t$ cannot be linear, since $\zeta \notin K$. But any factor of $q$ of degree at least 2 has a multiple root (since all the roots are $\zeta$). So $t$ is an irreducible inseparable polynomial over $K$.

Then $K(\zeta)$ is an inseparable extension of $K$.

### Wilson’s Theorem

Prove that $x^{p^n-1}-1 = \prod_{\alpha \in \mathbb{F}_{p^n}^\times} (x-\alpha)$. Conclude that $\prod_{\alpha \in \mathbb{F}_{p^n}^\times} \alpha = (-1)^{p^n}$. Deduce Wilson’s Theorem: if $p$ is an odd prime, then $(p-1)! \equiv -1$ mod $p$.

Recall that $x^{p^n}-x = \prod_{\alpha \in \mathbb{F}_{p^n}^\times}(x-\alpha)$ by definition, and that $0 \in \mathbb{F}_{p^n}$ is merely the root having minimal polynomial $x$. So $x^{p^n-1}-1 = \prod_{\alpha \in \mathbb{F}_{p^n}^\times} (x-\alpha)$. Comparing constant coefficients, we have $\prod_{\alpha \in \mathbb{F}_{p^n}^\times} (-\alpha) = -1$, so that \$latex $(-1)^{p^n-1} \prod_{\alpha \in \mathbb{F}_{p^n}^\times} \alpha = -1$, and hence $\prod_{\alpha \in \mathbb{F}_{p^n}^\times} \alpha = (-1)^{p^n}$.

Restrict now to the field $\mathbb{F}_p \cong \mathbb{Z}/(p)$ with $p$ odd. Then $\prod_{\alpha \in \mathbb{F}_p} \alpha = (p-1)!$, and $(-1)^p = -1$. Thus $(p-1)! \equiv -1$ mod $p$.

(I’d like to point out that this is a really roundabout way to prove Wilson’s Theorem. The easy(ier) way is to note that in $\mathbb{Z}/(p)^\times$, every element but -1 is distinct from its inverse.)

### xᵖ-x+a is irreducible and separable over ZZ/(p)

Prove that for any prime $p$ and any nonzero $a \in \mathbb{F}_p$, $q(x) = x^p-x+a$ is irreducible and separable over $\mathbb{F}_p$.

Note that $D_x(q) = px^{p-1}-1 = -1$, so that $q$ and $D(q)$ are relatively prime. So $q$ is separable.

Now let $\alpha$ be a root of $q$. Using the Frobenius endomorphism, $(\alpha+1)^p-(\alpha+1)+a = \alpha^p - \alpha + a = 0$, so that $\alpha+1$ is also a root. By induction, $\alpha_k$ is a root for all $k \in \mathbb{F}_p$, and since $q$ has degree $p$, these are all of the roots.

Now $\mathbb{F}_p(\alpha+k) = \mathbb{F}_p(\alpha)$, and in particular the minimal polynomials of $\alpha$ and $\alpha+k$ have the same degree over $\mathbb{F}_p$ – say $d$. Since $q$ is the product of the minimal polynomials of its roots, we have $p = dt$ for some $t$. Since $p$ is prime, we have either $d=1$ (so that $\alpha \in \mathbb{F}_p$, a contradiction) or $d=p$, so that $q$ itself is the minimal polynommial of $\alpha$, hence is irreducible.

### If a is an integer greater than 1, then aᵈ-1 divides aⁿ-1 if and only if d divides n

Fix an integer $a > 1$. Prove that for all $d,n \in \mathbb{N}$, $d$ divides $n$ if and only if $a^d-1$ divides $a^n-1$. Conclude that $\mathbb{F}_{p^d} \subseteq \mathbb{F}_{p^n}$ if and only if $d|n$.

If $d|n$, then by this previous exercise, $x^d-1$ divides $x^n-1$ in $\mathbb{Z}[x]$, and so $a^d-1$ divides $a^n-1$ in $\mathbb{Z}$.

Conversely, suppose $a^d-1$ divides $a^n-1$. Using the Division Algorithm, say $n = qd+r$. Now $a^n-1 = (a^d)^qa^r - a^r + a^r - 1$ $= a^r((a^d)^q-1) + (a^r-1)$. If $q = 1$, then we have $a^r-1 = 0$, so that $r = 0$ and $d|n$. If $q > 1$, then $a^n-1 = a^r(a^d-1)(\sum_{i=0}^{q-1} (a^d)^i) + (a^r-1)$, and again we have $r = 0$, so that $d|n$ as desired.

Recall that $\mathbb{F}_{p^k}$ is precisely the roots (in some splitting field) of $x^{p^k}-x$. Now $d|n$ if and only if $p^d-1$ divides $p^n-1$ by the above argument, if and only if $x^{p^d-1}-1$ divides $x^{p^n-1}-1$ by a previous exercise, if and only if $x^{p^d}-x$ divides $x^{p^n}-x$, if and only if $\mathbb{F}_{p^d} \subseteq \mathbb{F}_{p^n}$.

### xᵈ-1 divides xⁿ-1 if and only if d divides n

Prove that $x^d-1$ divides $x^n-1$ if and only if $d$ divdes $n$.

Suppose $d|n$; say $n = dt$.

If $t = 1$, there is nothing to show. Suppose $t > 1$; then $x^n-1 = (x^d)^t - 1$ $= (x^d-1)(\sum_{i=0}^{t-1} (x^d)^i)$, so that $x^d-1$ divides $x^n-1$.

Now suppose $x^d-1$ divides $x^n-1$. By the Division Algorithm in $\mathbb{N}$, we have $q$ and $r$ such that $n = qd+r$. Now $x^n-1 = x^{qd}x^r - 1$ $= x^{qd}x^r -x^r + x^r - 1$ $= x^r(x^{qd}-1) + (x^r-1)$. If $q=1$, then (by the uniqueness part of the division algorithm in $\mathbb{Q}[x]$) $x^r-1 = 0$, so $r = 0$ and $d|n$. If $q > 1$, then $x^n - 1 = x^r(x^d-1)(\sum_{i=0}^{q-1} (x^d)^i) + (x^r-1)$, and again we have $r = 0$, so $d|n$.

### Find the irreducible polynomials of degree 1, 2, and 4 over ZZ/(2)

Find all the irreducible polynomials of degree 1, 2, or 4 over $\mathbb{F}_2$, and verify that their product is $x^{16}-x$.

Note that there are $2^k$ (monic) polynomials of degree $k$, as each non-leading coefficient can be either 0 or 1.

The polynomials of degree 1, $p_1(x) = x$ and $p_2(x) = x+1$, are both irreducible.

There are 4 polynomials of degree 2, one of which is irreducible.

1. $x^2 = xx$ is reducible
2. $x^2+1 = (x+1)^2$ is reducible
3. $x^2+x = x(x+1)$ is reducible
4. $p_3(x) = x^2+x+1$ has no roots, and so is irreducible.

Before we address the degree 4 polynomials, we prove a lemma.

Lemma 1: If $p(x)$ is a degree 4 polynomial over $\mathbb{F}_2$ with constant term 1 and $p$ factors as a product of quadratics, then the linear and cubic terms of $p$ are equal. Proof: We have (as we assume) $p(x) = (x^2+ax+b)(x^2+cx+d)$ $= x^4 + (a+c)x^3 + (b+d+ac)x^2 + (ad+bc)x+bd$. Now $bd = 1$, so that $b = d = 1$. So $p(x) = x^4 + (a+c)x^3 + acx^2 + (a+c)x + 1$, as desired. $\square$

Lemma 2: $\Phi_5(x) = x^4+x^3+x^2+x+1$ is irreducible over $\mathbb{F}_2$. Proof: Clearly this has no roots. By Lemma 1, if $\Phi_5(x)$ factors into two quadratics, then the factors’ linear terms, $a$ and $c$, satisfy $a+c=ac=1$, which is impossible over $\mathbb{F}_2$. $\square$

There are 16 polynomials of degree 4.

1. $x^4 = xx^3$ is reducible
2. $x^4+1 = (x^2+1)^2$ is reducible
3. $x^4+x = x(x^3+1)$ is reducible
4. $x^4+x^2 = x^2(x^2+1)$ is reducible
5. $x^4+x^3 = x^3(x+1)$ is reducible
6. $p_4(x) = x^4+x+1$ clearly has no roots, and by the lemma, has no quadratic factors. So $p_4$ is irreducible.
7. $x^4+x^2+1 = (x^2+x+1)^2$ is reducible
8. $p_5(x) = x^4+x^3+1$ clearly has no roots, and by Lemma 1, has no quadratic factors. So $p_5$ is irreducible.
9. $x^4+x^2+x = x(x^3+x+1)$ is reducible
10. $x^4+x^3+x = x(x^3+x^2+1)$ is reducible
11. $x^4+x^3+x^2 = x^2(x^2+x+1)$ is reducible
12. $x^4+x^2+x+1$ has 1 as a root, so is reducible
13. $x^4+x^3+x^2+1 = (x+1)(x^3+1)$ is reducible
14. $x^4+x^3+x^2+1$ has 1 as a root, so is reducible
15. $x^4+x^3+x^2+x = x(x^3+x^2+x+1)$ is reducible
16. $p_6(x) = x^4+x^3+x^2+x+1 = \Phi_5(x)$ is irreducible

So there are six irreducible polynomials of degree 1, 2, or 4 over $\mathbb{F}_2$:

1. $p_1(x) = x$
2. $p_2(x) = x+1$
3. $p_3(x) = x^2+x+1$
4. $p_4(x) = x^4+x+1$
5. $p_5(x) = x^4+x^3+1$
6. $p_6(x) = x^4+x^3+x^2+x+1$

It is easy (if tedious) to verify that the product of these polynomials is $x^{16}-x$. (WolframAlpha agrees.)

### Properties of derivatives

Let $R$ be a commutative ring and let $p(x) = \sum_{i=0}^n c_ix^i \in R[x]$. Recall that the derivative $D_x(p)$ is defined to be $D_x(p)(x) = \sum_{i=0}^{n-1} (i+1)c_{i+1}x^i$. Prove that for all $f,g \in R[x]$, $D_x(f+g) = D_x(f) + D_x(g)$, $D_x(fg) = D_x(f)g + fD_x(g)$, and (for good measure) $D_x(f \circ g) = (D_x(f) \circ g)D_x(g)$.

Let $f(x) = \sum_{i=0}^n c_ix^i$ and $g(x) = \sum_{i=0}^n d_ix^i$. (For ease of exposition, pad $f$ or $g$ with zero terms so that they have the same nominal degree.)

Now $D_x(f+g)(x) = \sum_{i=0}^{n-1} (i+1)(c_{i+1}+d_{i+1})x^i$ $= \sum_{i=0}^{n-1} (i+1)c_{i+1}x^i + \sum_{i=0}^{n-1} (i+1)d_{i+1}x^i$ $= D_x(f)(x) + D_x(g)(x)$.

We will now prove the ‘product rule’ in pieces. First, for monic monomials.

Lemma 0: If $r \in R$, then $D_x(rf) = rD_x(f)$. Proof: $D_x(rf) = D_x(\sum_{i=0}^n rc_ix^i)$ $= \sum_{i=0}^{n-1}r(i+1)c_{i+1}x^i$ $= rD_x(f)$. $\square$

Lemma 1: For all $n,m \in \mathbb{N}$, we have $D_x(x^nx^m) = D_x(x^n)x^m + x^nD_x(x^m)$. Proof: If $n = 0$, then $D_x(x^0x^m) = D_x(1 \cdot x^m)$ $= D_x(x^0)x^m + x^0D_x(x^m)$ as desired. Similarly for $m = 0$. Now $D_x(x^{n+1}x^{m+1}) = D_x(x^{n+m+2})$ $= (n+m+2)x^{n+m+1}$ $(n+1)x^nx^{m+1} + x^n(m+1)x^m$ $= D_x(x^n)x^m + x^nD_x(x^m)$. $\square$

Lemma 2: For all $m \in \mathbb{N}$ and $f \in R[x]$, $D_x(x^mf)(x) = D_x(x^m)f + x^mD_x(f)$. Proof: We have $D_x(x^mf) = D_x(\sum_{i=0}^n c_ix^mx^i)$ $= \sum_{i=0}^n c_i D_x(x^mx^i)$ $= \sum_{i=0}^n c_i(D_x(x^m)x^i + x^mD_x(x^m))$ $= \sum_{i=0}^n c_iD_x(x^i)x^m + \sum_{i=0}^n c_ix^iD_x(x^m)$ $= D_x(x^m)f + x^mD_x(f)$ as desired. $\square$

Lemma 3: For all $f,g \in R[x]$, $D_x(fg) = D_x(f)g + fD_x(g)$. Proof: We have $D_x(fg) = D_x(\sum_{i=0}^n d_ix^ig)$ $= \sum_{i=0}^n d_i D_x(x^ig)$ $= \sum_{i=0}^n d_i (D_x(x^i)g + x^iD_x(g))$ $= \sum_{i=0}^n d_i D_x(d^i)g + \sum_{i=0}^n d_ix^iD_x(g)$ $= D_x(f)g + fD_x(g)$ as desired. $\square$

Now recall that if $f(x) = \sum c_ix^i$, then $(f \circ g)(x) = \sum c_ig(x)^i$.

Lemma 4: For all $m \in \mathbb{N}$, $D_x(x^m \circ f) = (D_x(x^m) \circ f)D_x(f)$. Proof: We proceed by induction on $m$. For $m = 0$ and $m = 1$, the result is clear. (Note that $1 \circ f = 1$.) Suppose the result holds for some $m \geq 2$. Now $D_x(x^{m+2} \circ f)$ $= D_x(ff^{m+1})$ $= D_x(f)f^{m+1} + fD_x(f^{m+1})$ $= D_x(f)f^{m+1} + (m+1)f^{m+1}D_x(f)$ $((m+2)f^{m+1})D_x(f)$ $= (D_x(x^{m+2}) \circ f)D_x(f)$ as desired. $\square$

Lemma 5: For all $f,g,h \in R[x]$, $(f+g) \circ h = (f \circ h) + (g \circ h)$. Proof: Let $f = \sum c_ix^i$, $g = \sum d_ix^i$, and $h = \sum e_ix^i$, padding to make the degrees nominally $n$. Then $(f+g) \circ h = \sum(c_i+d_i)x^i \circ h$ $= \sum c_ih^i + \sum d_ih^i$ $= (f \circ h) + (g \circ h)$. $\square$

Lemma 6: For all $f,g \in R[x]$, $D(f \circ g) = (D(f) \circ g)D(g)$. Proof: We have $D_x(f \circ g) = D_x(\sum c_ix^i \circ g)$ $= \sum c_i D_x(x^i \circ g)$ $= \sum c_i (D_x(x^i) \circ g)D_x(g)$ $= (D(f) \circ g)D(g)$ as desired. $\square$

### Composites and intersections of finite dimensional splitting fields are splitting fields

Let $K_1,K_2$ be finite dimensional splitting fields over a field $F$ and contained in a field $K$. Show that $K_1K_2$ and $K_1 \cap K_2$ are also finite dimensional splitting fields over $F$ (and contained in $K$).

Say $K_1$ and $K_2$ are splitting fields over $F$ for the finite sets $S_1,S_2 \subseteq F[x]$.

We claim that $K_1K_2$ is a splitting field over $F$ for $S_1 \cup S_2$. To see this, note that each polynomial in $S_1 \cup S_2$ splits over $K_1K_2$. Now if $E$ is a field over which $S_1 \cup S_2$ split, then the polynomials in $S_1$ split over $E$, so that $K_1 \subseteq E$. Likewise $K_2 \subseteq E$, and so $K_1K_2 \subseteq E$. So $K_1K_2$ is a splitting field for $S_1 \cup S_2$ over $F$.

Now suppose $q(x)$ is irreducible over $F$ with a root in $K_1 \cap K_2$. This root is in the splitting field $K_1$, so $q$ splits over $K_1$ by this previous exercise. Likewise, $q$ splits over $K_2$. Thus $q$ splits over $K_1 \cap K_2$. Again using this exercise, $K_1 \cap K_2$ is a splitting field over $F$.

### A finite field extension K of F is a splitting field if and only if every irreducible polynomial over F has no roots in K or splits over K

Let $K$ be a finite extension of a field $F$. Prove that $K$ is a splitting field over $F$ if and only if every irreducible polynomial over $F$ with a root in $K$ splits over $K$.

We begin with some lemmas.

Lemma 1: Let $K$ be a finite extension of $F$, and let $\alpha$ be algebraic over $F$. If $K$ is a splitting field for a set $S \subseteq F[x]$, then $K(\alpha)$ is a splitting field for $S$ considered as polynomials over $F(\alpha)$. Proof: Certainly the roots of elements of $S$ are in $K(\alpha) \supseteq K$. Now suppose $E$ is a splitting field for $S$ over $F(\alpha)$; in particular, $E$ contains $F$ and the roots of the polynomials in $S$, so $K \subseteq E$. Moreover $\alpha \in E$, so $K(\alpha) \subseteq E$. Hence $K(\alpha)$ is a splitting field for $S$ over $F(\alpha)$. $\square$

Suppose $K$ is a splitting field for some (finite) set $S \subseteq F[x]$. Let $q(x)$ be irreducible over $F$, and suppose $\alpha$ and $\beta$ are roots of $q$ with $\alpha \in K$. By Theorem 8 on page 519 of D&F, $\sigma : \alpha \mapsto \beta$ extends to an isomorphism $\sigma : F(\alpha) \rightarrow F(\beta)$. Now $K(\alpha)$ is the splitting field for $S \subseteq F(\alpha)[x]$, and likewise $K(\beta)$ is the splitting field for $S$ over $F(\beta)$. By Theorem 27 on page 541 of D&F, the isomorphism $\sigma$ extends to an isomorphism $\psi : K(\alpha) \rightarrow K(\beta)$. We can visualize this using the following diagram.

A field diagram

Since $\alpha \in K$, $[K(\alpha):K] = 1$, and so $[K(\beta):K] = 1$, and we have $\beta \in K$. That is, if an irreducible polynomial over $F$ has any roots in $K$, then it splits completely over $K$.

Conversely, suppose $K$ is finite over $F$ and that every irreducible polynomial with a root in $K$ has all roots in $K$. Since $K$ is a finite extension, it is algebraic (see Theorem 17 on page 526 of D&F). Say $K = F(\alpha_1,\ldots,\alpha_n)$, and let $m_i$ be the minimal polynomial of $\alpha_i$ over $F$. By our hypothesis, each $m_i$ splits over $K$. Moreover, any field over which all the $m_i$ split must contain the $\alpha_i$. So in fact $K$ is the splitting field over $F$ of the set of polynomials $m_i$.