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 pth 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.