Tag Archives: polynomial

A fact about multivariate polynomials over ZZ

Let f(x_1,\ldots,x_n) \in \mathbb{Z}[x_1,\ldots,x_n], and let p be a prime. Prove that f(x_1,\ldots,x_n)^p = f(x_1^p,\ldots,x_n^p) mod p.

Remember that \alpha^p \equiv \alpha mod p for all \alpha. Say f = \sum_i c_i \prod_j x_j^{e_{i,j}}.

Then f(x_1,\ldots,x_n)^p = (\sum_i c_i \prod_j x_j^{e_{i,j}})^p = \sum_i c_i^p \prod_j x_j^{e_{i,j}p} = \sum_i c_i \prod_j (x_j^p)^{e_{i,j}} = f(x_1^p,\ldots,x_n^p) as desired.

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.

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.

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

Compute the splitting field of x⁶-4 over QQ

Compute the splitting field of p(x) = x^6-4 over \mathbb{Q} and its degree.

Note that x^6-1 factors as x^6-1 = (x+1)(x-1)(x^2+x+1)(x^2-x+1). (Using only the difference of squares and sum of cubes formulas familiar to middle schoolers.) Using the quadratic formula (again familiar to middle schoolers) we see that the roots of p(x) are \pm 1 and \pm \dfrac{1}{2} \pm \dfrac{i\sqrt{3}}{2}.

Now if \zeta is a 6th root of 1, then \sqrt[6]{4}\zeta is a root of p(x), where \sqrt[6]{4} = \sqrt[3]{2} denotes the positive real 6th root of 4 (aka the positive cube root of 2). (Middle schoolers could verify that.) Evidently, then, the splitting field of p(x) is \mathbb{Q}(\sqrt[3]{2}, \sqrt[3]{2}(1+i\sqrt{3}, \sqrt[3]{2}(1-i\sqrt{3}) = \mathbb{Q}(\sqrt[3]{2}, i\sqrt{3}).

Now \mathbb{Q}(\sqrt[3]{2}) has degree 3 over \mathbb{Q}, and \mathbb{Q}(i\sqrt{3}) has degree 2 over \mathbb{Q}. (Use Eisenstein for both.) By Corollary 22 on page 529 of D&F, then, \mathbb{Q}(\sqrt[3]{2}, i\sqrt{3}) has degree (as a middle schooler could compute) 3 \cdot 2 = 6 over \mathbb{Q}.

So we have proved not only that the splitting field of p(x) has degree 6 over \mathbb{Q}, but, in a metamathematical twist, also that a middle schooler could prove this as well.

Compute the splitting field of x⁴+2 over QQ

Compute the splitting field of p(x) = x^4+2 over \mathbb{Q} and its degree.

The roots of p(x) exist in \mathbb{C} (if we don’t know this yet, just assume some roots are in \mathbb{C}). Let \zeta = a+bi be such a root; then \zeta^4 = -2.

Evidently, \zeta^4 = [a^4-6a^2b^2 + b^4] + [4ab(a^2-b^2]i. Comparing coefficients, we see that either a = 0, b = 0, or a^2 = b^2. If a = 0, then b^4 = -2, a contradiction in \mathbb{R}. Likewise, if b = 0 we get a contradiction. Thus a^2 = b^2. Substituting, we have b^4 - 6b^4 + b^4 = -2, so -4b^4 = -2, and so b^4 = 1/2. There is a unique positive 4th root of 1/2, which we denote by 2^{-1/4}; so b = \pm 2^{-1/4} and a = \pm 2^{-1/4}, and hence \zeta = \pm 2^{-1/4} \pm 2^{-1/4}i. There are 4 such roots, and so we have completely factored p(x). (WolframAlpha agrees.)

So the splitting field of p(x) is \mathbb{Q}(\pm 2^{-1/4} \pm 2^{-1/4}i). Note that if \zeta_1 = 2^{-1/4} + 2^{-1/4}i and \zeta_2 = \pm 2^{-1/4} - 2^{-1/4}i, then (\zeta_1 + \zeta_2)/2 = 2^{-1/4}, and (\zeta_1 - \zeta_2)/22^{-1/4} = i. Thus \mathbb{Q}(\pm 2^{-1/4} \pm 2^{-1/4}i) = \mathbb{Q}(i,2^{-1/4}).

Note that 2^{-1/4} is a root of q(x) = 2x^4 - 1, and that the reverse of q(x) is t(x) = -x^4+2. Now t(x) is irreducible over the UFD \mathbb{Z}[i], since it is Eisenstein at the irreducible element 1+i. So t(x) is irreducible over \mathbb{Q}(i), the field of fractions of \mathbb{Z}[i] as a consequence of Gauss’ Lemma. As we showed previously, the reverse of t, namely q, is also irreducible over \mathbb{Q}(i). So \mathbb{Q}(i,2^{-1/4}) has degree 4 over \mathbb{Q}(i), and thus has degree 8 over \mathbb{Q}.

Prove that a given polynomial is irreducible over QQ

Show that p(x) = x^3 + x^2 - 2x - 1 is irreducible over \mathbb{Q}. Use the fact (to be proven later) that \alpha = 2 \mathsf{cos}(2\pi/7) is a root of p to argue that the regular 7-gon is not constructible by straightedge and compass.

Using the rational root theorem, any rational roots of p(x) must be either 1 or -1. Certainly then p(x) has no rational roots. Since p(x) has degree 3, it is irreducible over \mathbb{Q} if and only if it has no roots (in \mathbb{Q}), so that p(x) is irreducible. In particular, the roots of p(x) lie in degree 3 extensions of \mathbb{Q}.

Suppose now that the regular 7-gon is constructible. The exterior angles of a regular 7-gon have measure 2\pi/7, so in particular, if the regular 7-gon is constructible, then so is the point (\mathsf{cos}(2\pi/7), \mathsf{sin}(2\pi/7)), so that the number 2\mathsf{cos}(2\pi/7) is constructible. But we have seen that any constructible element must have degree a power of 2 over \mathbb{Q}. Given that \alpha is a root of p(x), this yields a contradiction.

A procedure for finding a polynomial satisfied by an element of a given algebraic field extension

Let F be a field, K an extension of F of finite degree, and let \alpha \in K. Show that if A is the matrix of the linear transformation \varphi_\alpha corresponding to ‘multiplication by \alpha‘ (described here) then \alpha is a root of the characteristic polynomial of A. Use this result to obtain monic polynomials of degree 3 satisfied by \alpha = \sqrt[3]{2} and \beta = 1 + \sqrt[3]{2} + \sqrt[3]{4}.

Let \Psi : K \rightarrow \mathsf{Mat}_n(F) be the F-linear transformation described here. If c(x) is the characteristic polynomial of A, then we have c(A) = 0. On the other hand, 0 = c(A) = c(\Psi(\alpha)) = \Psi(c(\alpha)), and so c(\alpha) = 0 since \Psi is injective. So \alpha is a root of c(\alpha).

Consider the basis \{1,\sqrt[3]{2},\sqrt[3]{4}\} of \mathbb{Q}(\sqrt[3]{2}) over \mathbb{Q}. Evidently, with respect to this basis, the matrix of \varphi_\alpha is A = \begin{bmatrix} 0 & 0 & 2 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}. As we showed previously, the characteristic polynomial of A is x^3-2. So \sqrt[3]{2} satisfies x^3-2. (Surprise!)

Similarly, \varphi_\beta has the matrix B = \begin{bmatrix} 1 & 2 & 2 \\ 1 & 1 & 2 \\ 1 & 1 & 1 \end{bmatrix}. Evidently, the characteristic polynomial of B is x^3-3x^2-3x-1. We can verify that \beta actually satisfies this polynomial (WolframAlpha agrees.)

On the degrees of the divisors of a composite polynomial

Let f(x) be an irreducible polynomial of degree n over a field F, and let g(x) be any polynomial in F[x]. Prove that every irreducible factor of the composite (f \circ g)(x) has degree divisible by n.

Let \beta be a root of f \circ g, and let m be the degree of \beta over F. Now g(\beta) \in F(\beta), and moreover g(\beta) is a root of the irreducible polynomial f(x). So F(g(\beta)) has degree n over F. Graphically, we have the following diagram of fields.

A field diagram

By Theorem 14 in D&F, n|m.

All matrices over a field having a given characteristic polynomial are similar if and only if the polynomial is squarefree

Let F be a field and let p(x) be a polynomial over F whose roots all lie in K. Prove that all matrices over F having characteristic polynomial p(x) are similar if and only if p(x) is squarefree.

Suppose p(x) has a repeated factor. Then there are at least two possible lists of elementary divisors whose product is p(x); in particular there exist two matrices with characteristic polynomial p(x) which are not similar. So if all matrices with characteristic polynomial p(x) are similar, then p(x) has no repeated factors.

Conversely, suppose p(x) has no repeated factors. then there is only one possible list of elementary divisors, and so any two matrices having characteristic polynomial p(x) are similar.