On my continued absence

Hello all-

You might have noticed that daily updates haven’t happened for a while now. I haven’t abandoned this blog or my quest to conquer Dummit and Foote; rather, I’ve spent the last month and a half working furiously on my dissertation. I have my sights set on graduating this summer, which means that some of my other activities (like the Crazy Project or a regular sleep schedule) are on hold until I finish.

I will be back to work here “soon”. :)

NB

March 2, 2012 – 2:00 am Categories: Meta | Comments (2)

The order of the Frobenius map on a finite field

Let \varphi denote the Frobenius map x \mapsto x^p on \mathbb{F}_{p^n}. Prove that \varphi is an automorphism and compute its order in \mathsf{Aut}(\mathbb{F}_{p^n}).

Recall that \varphi is a homomorphism. Moreover, if \alpha \in \mathsf{ker}\ \varphi, then \alpha^p = 0. Since fields contain no nontrivial zero divisors, we have \alpha = 0 (using induction if you want). So the kernel of \varphi is trivial, and thus \varphi is injective. Since \mathbb{F}_{p^n} is finite, \varphi is surjective, and so is a field isomorphism.

Next, we claim that \varphi^t(\alpha) = \alpha^{p^t} for all \alpha and all t \geq 1, and will show this by induction. The base case certainly holds, and if \varphi^t(\alpha) = \alpha^{p^t}, then \varphi^{t+1}(\alpha) = \varphi(\varphi^t(\alpha)) = \varphi(\alpha^{p^t}) = (\alpha^{p^t})^p = \alpha^{p^{t+1}} as desired.

Now \varphi^n(\alpha) = \alpha^{p^n} = \alpha, since the elements of \mathbb{F}_{p^n} are precisely the roots of x^{p^n}-x. So we have \varphi^n = 1.

If \varphi^t = 1, then we have \alpha^{p^t} - \alpha = 0 for all \alpha, so that each \alpha is a root of x^{p^t}-x. So x^{p^n-1}-1 divides x^{p^t-1}-1, and so p^n-1 divides p^t-1 (by this previous exercise) and then n divides t (by this previous exercise). In particular, n \leq t.

So n is the order of \varphi in \mathsf{Aut}(\mathbb{F}_{p^n}).

February 5, 2012 – 10:00 am Categories: AA:DF | Post a comment

Tagged , , |

Over CC, matrices of finite multiplicative order are diagonalizable

Let A be an n \times n matrix over \mathbb{C}. Show that if A^k=I for some k, then A is diagonalizable.

Let F be a field of characteristic p. Show that A = \begin{bmatrix} 1 & \alpha \\ 0 & 1 \end{bmatrix} has finite order but cannot be diagonalized over F unless \alpha = 0.

Since A^k = I, the minimal polynomial m of A over \mathbb{C} divides x^k-1. In particular, the roots of m are distinct. Since \mathbb{C} contains all the roots of unity, by Corollary 25 on page 494 of D&F, A is diagonalizable over \mathbb{C}.

Note that \begin{bmatrix} 1 & \alpha \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & \beta \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & \alpha+\beta \\ 0 & 1 \end{bmatrix}. By an easy inductive argument, then, \begin{bmatrix} 1 & \alpha \\ 0 & 1 \end{bmatrix}^t = \begin{bmatrix} 1 & t\alpha \\ 0 & 1 \end{bmatrix}, and in particular, A^p = I.

Suppose \alpha \neq 0. Now \frac{1}{\alpha}A is in Jordan canonical form, and is not diagonalizable. (See Corollary 24 on page 493 of D&F.) So A cannot be diagonalizable, for if it were, then so would \frac{1}{\alpha}A. (If P^{-1}AP = D is diagonal, then so is P^{-1}\frac{1}{\alpha}AP = \frac{1}{\alpha}D.)

February 4, 2012 – 12:00 pm Categories: AA:DF | Post a comment

Tagged , , |

On the factors of a cyclotomic polynomial over ZZ/(p)

Let \ell be a prime and let \Phi_\ell(x) = \frac{x^\ell-1}{x-1} \in \mathbb{Z}[x] be the \ellth cyclotomic polynomial. (Remember that \Phi_\ell is irreducible over \mathbb{Z}.) Let p be a prime and let \zeta denote any fixed primitive \ellth root of unity.

  1. Show that if p=\ell then \Phi_\ell(x) = (x-1)^{\ell-1} \in \mathbb{F}_p[x].
  2. Suppose p \neq \ell and let f denote the order of p in \mathbb{F}_\ell. (That is, f is minimal such that p^f \equiv 1 mod \ell.) Show that f is minimal such that \zeta \in \mathbb{F}_{p^f}. Conclude that the minimal polynomial of \zeta over \mathbb{F}_p has degree f.
  3. Show that \mathbb{F}_p(\zeta) = \mathbb{F}_p(\zeta^a) for any integer a not divisible by \ell. Conclude that, in \mathbb{F}_p[x], \Phi_\ell(x) is the product of \frac{\ell-1}{f} distinct irreducible polynomials of degree f.
  4. As an example, find the degrees of the irreducible factors of \Phi_7(x) over \mathbb{F}_p.
  1. Mod p=\ell, we have x^\ell-1 = (x-1)^\ell. So \Phi_\ell(x) = (x-1)^{\ell-1} as desired.
  2. Note that \zeta \in \mathbb{F}_{p^f} precisely when \zeta is a root of x^{p^f-1}-1. Since p^f \equiv 1 mod \ell, we have that \ell divides p^f-1. By this previous exercise, x^\ell - 1 divides x^{p^f-1}-1. Since \zeta is a \ellth root of unity, \zeta \in \mathbb{F}_{p^f}. Conversely, suppose \zeta \in \mathbb{F}_{p^t}. Now \zeta^\ell \equiv 1, so \ell divides p^t-1 by Lagrange’s theorem in the group \mathbb{F}_{p^t}^\times. Thus p^t \equiv 1 mod \ell, and so f divides t. So f is minimal such that \zeta \in \mathbb{F}_{p^f}.

    Next we claim that \mathbb{F}_p(\zeta) = \mathbb{F}_{p^f}. The (\subseteq) inclusion is clear since \zeta \in \mathbb{F}_{p^f}. (\supseteq) \mathbb{F}_p(\zeta) = \mathbb{F}_{p^t} for some t, since finite fields are essentially unique. By the preceding argument, f|t, so \mathbb{F}_{p^f} \subseteq \mathbb{F}_{p^t} = \mathbb{F}_p(\zeta) using this previous exercise.

  3. It is clear that \mathbb{F}_p(\zeta^a) \subseteq \mathbb{F}_p(\zeta). Conversely, since \ell does not divide a$, by Bezout’s identity there exist x,y \in \mathbb{Z} such that ax + \ell y = 1. Now (\zeta^a)^x = \zeta^{ax} = \zeta^{1-\ell y} = \zeta. So \mathbb{F}_p(\zeta) = \mathbb{F}_p(\zeta^a) provided \ell does not divides a.

    Now consider \Phi_\ell(x) as a polynomial over \mathbb{F}_p. Let \zeta_i be the distinct primitive \ellth roots of unity. By part (b), \mathbb{F}_p(\zeta_i) has degree f over \mathbb{F}_p for each i, so the minimal polynomial of \zeta_i over \mathbb{F}_p has degree f. So the irreducible factors of \Phi_\ell have degree f, and there are \frac{\ell-1}{f} such factors. Moreover, since \Phi_\ell is separable, its factors are distinct.

  4. If p \equiv 1 mod 7, then \Phi_7(x) = (x-1)^6 by part (a). Evidently 2 and 4 have order 3 mod 7, so if p \in \{2,4\} mod 7 then \Phi_7(x) factors into two irreducible cubics. Similarly, 3 and 5 have order 6 mod 7, so that if p \in \{3,5\} mod 7 then \Phi_7(x) is irreducible. Since 6 has order 2 mod 7, if p \equiv 6 mod 7, then \Phi_7(x) factors into three irreducible quadratics.
February 4, 2012 – 11:00 am Categories: AA:DF | Post a comment

Tagged , , |

An alternate characterization of cyclotomic polynomials

Prove that \Phi_n(x) = \prod_{d|n} (x^d-1)^{\mu(n/d)}, where \Phi_n is the nth cyclotomic polynomial and \mu is the Möbius function on \mathbb{N}^+ defined by \mu(1) = 1, \mu(m) = (-1)^r if m is squarefree with r distinct prime factors, and \mu(m) = 0 if m is divisible by a square.

[I consulted this document from the Berkeley Math Circle when preparing this solution.]

Before we approach this (seemingly magical) identity, let’s build up some machinery.

Given an abelian group A, let A_0^\mathbb{N} denote the set of all functions \mathbb{N}^+ \rightarrow A. Recall that A^\mathbb{N}_0 is itself an abelian group under pointwise addition.

Now let R be a commutative ring with 1 and let M be a left R-module. Define an operator R_0^\mathbb{N} \times M_0^\mathbb{N} \rightarrow M_0^\mathbb{N} by (f \ast_{R,M} g)(n) = \sum_{st=n} f(s) g(t). Note that since n is positive, this sum is finite, and that s and t are nonzero. We will usually drop the subscripts on \ast. This operator is called the Dirichlet convolution of f and g.

Lemma 1: Let f,g \in R^\mathbb{N}_0 and h \in M^\mathbb{N}_0. Then f \ast_{R,M} (g \ast_{R,M} h) = (f \ast_{R,R} g) \ast_{R,M} h. Proof: We have

(f \ast (g \ast h))(n)  =  \sum_{st=n} f(s)(g \ast h)(t)
 =  \sum_{st=n} f(s) \sum_{uv=t} g(u)h(v)
 =  \sum_{st=n} \sum_{uv=t} f(s)g(u)h(v)
 =  \sum_{suv=n} f(s)g(u)h(v)
 =  \sum_{tv=n} \sum_{su=t} f(s)g(u)h(v)
 =  \sum_{tv=n} (\sum_{su=t} f(s)g(u)) h(v)
 =  \sum_{tv=n} (f \ast g)(t)h(v)
 =  ((f \ast g) \ast h)(n)

As desired. \square

Lemma 2: Let f,g \in R^\mathbb{N}_0 and h,k \in M^\mathbb{N}_0. Then (using pointwise addition) we have (f+g) \ast h = (f \ast h) + (g \ast h) and f \ast (h + k) = (f \ast h) + (f \ast k). Proof: We have

(f \ast (h+k))(n)  =  \sum_{st=n} f(s)(h+k)(t)
 =  \sum_{st=n} f(s)(h(t)+k(t))
 =  \sum_{st=n} f(s)h(t) + \sum_{st=n} f(s)k(t)
 =  (f \ast h)(n) + (f \ast k)(n)
 =  ((f \ast h) + (f \ast k))(n)

as desired. The other equality is analogous. \square

Corollary 1: R^\mathbb{N}_0 is a ring with pointwise addition and Dirichlet convolution, and M^\mathbb{N}_0 is a left R^\mathbb{N}_0 module via Dirichlet convolution. Proof: Follows from Lemmas 1 and 2. \square

Let \delta_{1,n} denote the Kronecker delta (whose value is 1 if n=1 and 0 otherwise) and let \mu : \mathbb{N}^+ \rightarrow R be the Möbius function.

Lemma 3: For all g \in R^\mathbb{N}+0, \delta_{1,n} \ast g = g. Proof: We have (\delta_{1,n} \ast g)(n) = \sum_{st=n} \delta_{1,s}g(t). Now the delta function is 0 unless s = 1, in which case t = n, and so this sum is precisely g(n) as desired. \square

Now let 1 denote the constant function whose value is 1.

Lemma 4: \mu \ast 1 = \delta_{1,n}. Proof: We have (\mu \ast 1)(n) = \sum_{st=n} \mu(s)1(t) = \sum_{s|n} \mu(s). If n = 1, then we have (\mu \ast 1)(1) = \delta_{1,1}. Now suppose n = p_1^{e_1} \cdots p_k^{e_k}, with the p_i prime. Now s = p_1^{d_1} \cdots p_k^{d_k}, where 0 \leq d_i \leq e_i. Note that if any d_i is greater than 1, then (by definition) \mu(s) = 0. So the only summands which contribute to (\mu \ast 1)(n) those with d_i \in \{0,1\}. Moreover, in this case, the value of \mu(s) depends only on whether the number of nonzero d_i is even or odd. There are 2^k subsets of \{1,\ldots,k\}, half of which have an even number of elements and half odd. So \sum_{s|n} \mu(s) = \sum_{S \subseteq \{1,\ldots,k\}} (-1)^{|S|} = 0. Hence \mu \ast 1 = \delta_{1,n}. \square

Now given f : \mathbb{N}^+ \rightarrow M, define F = 1 \ast f- so F(n) = \sum_{d|n} f(d). Then \mu \ast F = (\mu \ast 1) \ast f = f.

Now let M be the abelian group F(x)^\times. (The nonzero rational functions over F in one variable). This is an abelian group, hence a \mathbb{Z}-module, where we write our operator multiplicatively and our \mathbb{Z}-action by exponentiation. Let f : \mathbb{N}^+ \rightarrow M be given by f(n) = \Phi_n(x), and let F(n) = (1 \ast f)(n) = \sum_{d|n} \varphi_n(x) = x^n-1. Now \mu \ast F = f, which expanded out gives the identity \Phi_n(x) = \prod_{st=n} (x^s-1)^{\mu(t)} as desired.

February 4, 2012 – 10:00 am Categories: AA:DF | Post a comment

Tagged , , , |

A fact about cyclotomic polynomials

Let n > 1 be an odd integer. Prove that \Phi_{2n}(x) = \Phi_n(-x), where \Phi_n(x) denotes the nth cyclotomic polynomial.

We begin with a lemma.

Lemma: -1 is not an nth root of unity for odd n. Proof: (-1)^n-1=-1-1=-2$. \square

Let \zeta be a primitive nth root of unity. Now suppose (-\zeta)^t = 1, so that (-1)^t\zeta^t = 1, so \zeta^t = (-1)^t. Since \zeta is a primitive nth root of unity, with n odd, the powers of \zeta are nth roots of unity. By the lemma, we must have (-1)^t = 1, so that 2|t, and thus \zeta^t=1, so that n|t. Since 2 and n are relatively prime, 2n|t, and so -\zeta is a primitive 2nth root of unity.

In particular, \Phi_n(-x) divides \Phi_{2n}(x).

Now \Phi_n(-x) has degree \varphi(n), and \Phi_{2n}(x) has degree \varphi(2n), where \varphi denotes the Euler totient. Since 2 and n are relatively prime, we have \varphi(2n) = \varphi(2)\varphi(n) = \varphi(n). So in fact \varphi_{2n}(x) = \varphi_n(-x).

February 3, 2012 – 12:00 pm Categories: AA:DF | Post a comment

Tagged , |

Finite extensions of the rationals contain only finitely many roots of unity

Let K be a finite extension of \mathbb{Q}. Prove that K contains only finitely many roots of unity.

Suppose to the contrary that K contains infinitely many roots of unity. Now for each n, there are only finitely many primitive roots of unity (in fact \varphi(n) of them). So for each m, the number of primitive roots of unity of order at most m is finite. In particular, for any m, there exists a primitive nth root of unity for some n > m.

Let m be the degree of K over \mathbb{Q}. If \zeta \in K is a primitive kth root of unity, then [\mathbb{Q}(\zeta):\mathbb{Q}] = \varphi(k) by Corollary 42 on page 555, where \varphi denotes the Euler totient. By this previous exercise, since k is arbitrarily large, \varphi(k) is arbitrarily large. So there exists a primitive kth root \zeta such that \varphi(k) > m, a contradiction since \mathbb{Q}(\zeta) \subseteq K.

February 3, 2012 – 11:00 am Categories: AA:DF | Post a comment

Tagged , , , |

There are m distinct pᵏmth roots of unity over a field of characteristic p, for p a prime not dividing m

Let n = p^km, where p is a prime not dividing m, and let F be a field of characteristic p. Prove that there are m distinct nth roots of unity over F.

Note that x^n-1 = x^{p^km}-1 = (x^m)^{p^k}-1 = (x^m-1)^{p^k}. That is, the distinct nth roots of unity over F are precisely the distinct roots of x^m-1 over F.

If m=1, then certainly there is only 1 root of x-1.

Suppose m > 1. Now D(x^m-1) = mx^{m-1}, which has only the root 0 with multiplicity m-1. Clearly 0 is not a root of x^m-1, so that x^m-1 and its derivative are relatively prime, and thus x^m-1 is separable. Hence there are m distinct mth roots of unity over F, and so m distinct nth roots of unity over F.

February 3, 2012 – 10:00 am Categories: AA:DF | Post a comment

Tagged , |

Any field containing the nth roots of unity for odd n also contains the 2nth roots of unity

Let F be a field over which x^n-1 splits where n is odd. Show that x^{2n}-1 also splits over F.

Note that x^{2n}-1 = (x^n)^2-1 = (x^n+1)(x^n-1).

Since n is odd, if \zeta is a root of x^n-1, then (-\zeta)^n+1 = -\zeta^n+1 = 0. That is, the roots of x^n+1 are precisely the negatives of the roots of x^n-1 (note that these are all distinct, since the derivative of x^n-1 has no nonzero roots). So any field containing the roots of x^n-1 also contains the roots of x^{2n}-1.

February 2, 2012 – 12:00 pm Categories: AA:DF | Post a comment

Tagged , |

If ζ is a primitive nth root of unity and d divides n, then ζᵈ is a primitive (n/d)th root of unity

Let \zeta be a primitive nth root of unity and let d|n. Prove that \zeta^d is a primitive n/dth root of unity.

Certainly (\zeta^d)^{n/d} = 1. Now if (\zeta^d)^t = 1, we have n|dt, and so n/d divides t. So n/d is the order of \zeta^d, and thus \zeta^d is a primitive n/dth root of unity.

February 2, 2012 – 11:00 am Categories: AA:DF | Post a comment

Tagged , , |

Follow

Get every new post delivered to your Inbox.

Join 39 other followers