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.