Math 380, Spring 2018, Assignment 4

I was at the mathematical school, where the master taught his pupils after a method scarce imaginable to us in Europe. The proposition and demonstration were fairly written on a thin wafer, with ink composed of a cephalic tincture. This the student was to swallow upon a fasting stomach, and for three days following eat nothing but bread and water. As the wafer digested the tincture mounted to the brain, bearing the proposition along with it.

- Jonathan Swift, Gulliver's Travels

Read:

1. Section 1.5.
2. Section 2.1.

Carefully define the following terms, then give one example and one non-example of each:

1. Monic polynomial (in $\mathsf{k}[x]$).
2. $\mathrm{gcd}(f,g)$ (where $f,g\in\mathsf{k}[x]$).

Carefully state the following theorems (you do not need to prove them):

1. Theorem concerning the division algorithm.
2. Classification of ideals in $\mathsf{k}[x]$ ("Every ideal in $\mathsf{k}[x]$ is generated by...").
3. Theorem concerning monic generators of ideals in $\mathsf{k}[x]$.
4. Theorem relating $\mathrm{gcd}(f,g)$ to common divisors of $f$ and $g$.
5. Theorem relating $\left\langle f,g\right\rangle$ to $\left\langle g,r\right\rangle$ when $f=gq+r$.

Carefully describe the following algorithms:

1. Division algorithm (to compute quotient and remainder when $f$ is divided by $g$).
2. Euclid's algorithm (to compute $\mathrm{gcd}(f,g)$).
3. Algorithm to replace any system of finitely many univariate equations by a single univariate equation.
4. Algorithm to factor polynomials over $\mathbb{C}$. (Note: this algorithm is conceptually simple but should NOT be used in engineering applications; it is numerically unstable. See books on numerical analysis for more practical algorithms.)

Solve the following problems:

1. Section 1.5, problems 1, 3, 4, 11, and 12.
2. Prove that for any $f_1,\dots,f_s\in\mathsf{k}[x]$, one has $\left\langle f_1,f_2,f_3,\dots,f_s\right\rangle = \left\langle \mathrm{gcd}(f_1,f_2),f_3,\dots,f_s\right\rangle$. (Hint: use the ideal containment criterion from the previous assignment.)
3. Optional (but interesting): section 1.5, problem 17. (You may need to use the results of problems 13, 14, and 15.)

--------------------End of assignment--------------------

Solutions:

1.5.1: It is known that every nonconstant polynomial in $\mathbb{C}[x]$ has a root in $\mathbb{C}$. Let $a_1$ be such a root. By the factor theorem, $f$ is divisible by $x-a_1$ with remainder zero, that is $f=(x-a_1)q$ where $q$ is the quotient. If $q$ is a nonconstant polynomial, repeat this argument with $q$ instead of $f$, otherwise $q$ is the constant c in the desired form. Thus every univariate polynomial of degree $n>0$ over the complex numbers may be written $f=c(x-a_1)\cdots(x-a_n)$ where $a_1,\ldots,a_n,c\in\mathbb{C}$ and $c\neq0$.

1.5.3: We wish to prove that $I=\langle x,y\rangle\subseteq k[x,y]$ is not a principal ideal, that is, that it is not generated by one element. Suppose it were. Let $f$ be the single generator, i.e., $\langle x,y\rangle=\langle f\rangle$. Obviously $f$ cannot be a constant. Then every polynomial in $\langle x,y\rangle$ is equal to $fg$ for some $g\in k[x,y]$. Consider $x\in\langle x,y\rangle$. Then $x=fg$ for some $g$. Taking the degree of both sides we have $\text{deg}(x)=1=\text{deg}(fg)=\text{deg}(f)+\text{deg}(g)$. The only way this can be satisfied is if $f$ or $g$ is a constant and the other is degree 1. Since $f$ cannot be a constant, $g$ is. Say $g=c$, then $x=cf\implies f=\frac{x}{c}$. Since $f$ generates $\langle x,y\rangle$, it must also be that $y=fh$ for some $h\in k[x,y]$. Then $y=\frac{x}{c}h$, but this clearly cannot be satisfied, so we have a contradiction. Thus $\langle x,y\rangle$ is not a principal ideal.

1.5.4: $\text{gcd}(f,g)$ is the monic generator of the ideal $\langle f,g\rangle$, so, if $h=\text{gcd}(f,g)$, then $\langle h\rangle=\langle f,g\rangle$. By definition, this means that $h\in\langle f,g\rangle$, so there exists $A,B\in k[x]$ such that $Af+Bg=h$.

1.5.11: (a) As noted in class, every nonconstant polynomial has a root so $\mathbb{V}(f)\neq \emptyset$ iff $f$ is not a constant.

(b) If $\text{gcd}(f_1,\ldots,f_s)=1$, we have $\langle f_1,\ldots,f_s\rangle=\langle 1 \rangle$ and so $\mathbb{V}(f_1,\ldots,f_s)=\mathbb{V}(1)=\emptyset$. If $\mathbb{V}(f_1,\ldots f_s)=\emptyset$, then $\mathbb{V}(\text{gcd}(f_1,\ldots,f_s))=\emptyset$. This means that $\text{gcd}(f_1,\ldots,f_s)$ is a polynomial in $\mathbb{C}[x]$ which doesn't have a root in $\mathbb{C}$. Therefore it is a constant polynomial. By the definition of the gcd, it is monic, so $\text{gcd}(f_1,\ldots,f_s)=1$.

(c) Determine $\text{gcd}(f_1,\ldots,f_s)$. If this is not equal to $1$ then the affine variety $\mathbb{V}(f_1,\ldots,f_s)$ is not empty.

1.5.12: (a) By inspection of the factored form of $f$, the polynomial vanishes at the points $\{a_1,\ldots a_l\}$ and doesn't vanish at any others. Thus $\mathbb{V}(f)=\{a_1,\ldots, a_l\}$.

(b) We wish to show $\mathbb{I}(\mathbb{V}(f))=\langle f_\text{red}\rangle$. We proceed by mutual inclusion. $\mathbb{I}(\mathbb{V}(f))$ is the set of all polynomials which vanish at $\{a_1,\ldots,a_l\}$. We can clearly see that $f_\text{red}$, as defined, vanishes at all of these points, so $f_\text{red}\in\mathbb{I}(\mathbb{V}(f))\implies \langle f_\text{red}\rangle\subseteq\mathbb{I}(\mathbb{V}(f))$. Now let $g\in\mathbb{I}(\mathbb{V}(f))$. We want to show that $g\in\langle f_\text{red}\rangle$. Since $g\in\mathbb{I}(\mathbb{V}(f))$, $g$ has, among its roots, $\{a_1\ldots,a_l\}$. As it is a univariate polynomial over $\mathbb{C}$, we may write $g$ in the fully factored form \[ g=c(x-b_1)^{n_1}\cdots(x-b_s)^{n_s}\;. \] But it must be that $l$ of the roots are the $a_i$, so we can arrange to write $g$ as \[ g=c(x-a_1)^{n_1}\cdots(x-a_l)^{n_l}(x-b_{s-l})^{n_{s-l}}\cdots(x-b_s)^{n_s}\;. \] By inspection, then, we can see that $g=h f_\text{red}$ for an appropriately choosen $h\in\mathbb{C}[x]$, and so $g\in\langle f_\text{red}\rangle\implies \mathbb{I}(\mathbb{V}(f))\subseteq\langle f_\text{red}\rangle$.

2: $\text{gcd}(f_1,f_2)$ is the unique monic generator of $\langle f_1,f_2\rangle$. Consequently, $\langle \text{gcd}(f_1,f_2)\rangle=\langle f_1,f_2\rangle\implies\text{gcd}(f_1,f_2)\in\langle f_1,f_2\rangle\implies\text{gcd}(f_1,f_2)\in\langle f_1,\ldots,f_s\rangle\implies\langle \text{gcd}(f_1,f_2),f_3,\ldots,f_s\rangle\subseteq\langle f_1,\ldots,f_s\rangle$. Since $\text{gcd}(f_1,f_2)$ is a divisor of $f_1$, $f_1=h_1 \text{gcd}(f_1,f_2)$. Likewise $f_2=h_2 \text{gcd}(f_1,f_2)$. This shows that $f_1,f_2\in\langle \text{gcd}(f_1,f_2)\rangle\implies\langle f_1,f_2\rangle\subseteq\langle\text{gcd}(f_1,f_2)\rangle$. We can add the generators $f_3,\ldots,f_s$ to both ideals without changing the inclusion, so we have $\langle f_1,\ldots,f_s\rangle\subseteq\langle\text{gcd}(f_1,f_2),f_3,\ldots,f_s\rangle$.

1.5.17: First let's convert the variety into one with only one equation by finding the gcd of the two polynomials. Note that $x$ can be factored out of the first polynomial, but not out of the second. Clearly $x$ is not a common divisor, so we seek $\text{gcd}(x^4-2x^3+2x-1,x^5-x^4-2x^3+2x^2+x-1)$. Polynomial division quickly reveals that the first divides the second with remainder zero, so $x^4-2x^3+2x-1$ is the gcd. From problem (1.5.12), we learned that $\mathbb{I}(\mathbb{V}(f))=\langle f_\text{red}\rangle$ and the result of problem (1.5.15) tells us that \[ f_\text{red}=\frac{f}{\text{gcd}(f,f')}\;, \] where $f'$ is the formal derivative of $f$. The formal derivative of $x^4-2x^3+2x-1$ is $4x^3-6x^2+2$. Running the gcd algorithm takes a couple steps, which I'm not going to typeset. We obtain $\text{gcd}(x^4-2x^3+2x-1,4x^3-6x^2+2)=x^2-2x+1$. Thus, \[ f_\text{red}=\frac{x^4-2x^3+2x-1}{x^2-2x+1}=x^2-1\;. \] Thus we have $\mathbb{I}(\mathbb{V}(x^5-2x^4+2x^2-x,x^5-x^4-2x^3+2x^2+x-1))=\langle x^2-1\rangle$, that is, a basis for the ideal is $x^2-1$.

Endorsing all of the solutions above, except that (2) is perhaps a little unclear (it looks like you have inclusion in only one direction).

Note that the machinery developed in problems 13-17 leads to a field-agnostic method for simplifying a system of equations even further than the methods developed in class. As problem 17 shows, the final factorization problem is often far simpler after applying these methods, so they should always be included in "production code" for solving univariate polynomial systems.

-Steven.Jackson (talk) 09:15, 19 February 2018 (EST)

N.B.: I wrote somewhat carelessly in the remark above. The methods of problems 13-17 are valid over any field of characteristic zero. One must take greater care in characteristic $p$. The root of the difficulty is that, in positive characteristic, a polynomial may have vanishing derivative even if it is not constant. To get a feeling for what goes wrong, work over $\mathbb{Z}_p$ and try to apply the methods of problems 13-17 to the equation $x^p=0$. For methods that work over finite fields (or over the algebraic closure of $\mathbb{Z}_p$), and for some partial results for general fields of characteristic $p$, see Maurice Mignotte, Mathematics for Computer Algebra, section 6.3.

-Steven.Jackson (talk) 10:02, 19 February 2018 (EST)

Actually I was reading too quickly. (2) looks fine.

-Steven.Jackson (talk) 09:57, 20 February 2018 (EST)