UTM Ideals Varieties and Algorithm - Chapter 2 Section 2 Exercise 7

Problem:

Solution:

It took me a good while to solve this problem, but looking in retrospect, this problem is easy. It is just that the notation tripped me up.

(a)

First, note that $ \alpha \in \mathbf{Z}_{\ge 0}^{n} $, so $ \alpha = 0 $ means it is an n-tuple of all 0, which means all the powers are 0, which means the monomial is actually 1, not 0.

With that in mind, the solution for this is not hard, we do infinity descent here as follow. Suppose the contrary, we have :

$ 0 > \beta $ for some $ \beta $
$ \beta = 0 + \beta  > \beta + \beta =2\beta $
$ 2\beta = 0 + 2\beta > \beta + 2\beta = 3\beta $

and so on.

Now we have a sequence of $ 0, \beta, 2\beta, 3\beta, \cdots $ and this is an infinitely decreasing sequence with no minimum, contradicting the well ordering property required for monomial order.

(b)

Now we know 1 as a term is the minimum monomial for all order, in particular, we know

$ 1 \le x^{\beta - \alpha} $

Multiplying $ x^{\alpha} $ on both side we get the inequality we wanted

$ x^{\alpha} \le x^{\beta} $.

The converse is not true, in particular, we know in lex order

$ x < y $.

But obviously neither divide each other.

(c)

We do a similar infinite descent for this one, support the contrary, we have

$ \alpha + \beta < \alpha $

We reach the same conclusion as above, to be more concrete, we can write

$ \alpha + \beta +k\beta < \alpha + k\beta $.

So we have the sequence $ \alpha, \alpha + \beta, \alpha + 2\beta, \cdots $. This is an infinitely decreasing sequence with no minimum, so again it contradicts the well ordering property.

UTM Ideals Varieties and Algorithm - Chapter 2 Section 2 Exercise 6

Problem:

Solution:

It is simply reversing the variable order.

Suppose a set of polynomial is invlex ordered with respect to the variable order $ x > y > z $, then it is lex ordered with respect to the variable order $ z > y > x $, this is obvious to see from the definition.

UTM Ideals Varieties and Algorithm - Chapter 2 Section 2 Exercise 5

Problem:

Solution:

All we needed to do for this problem is to verify the three rules.

(i) > is a total (or linear order) on $ \mathbf{Z}^n_{\ge 0} $

This is simple to verify according to the definition. As long as two monomials are not the same, then either one is strictly larger than the other.

(ii) If $ \alpha > \beta $ and $ \gamma \in \mathbf{Z}^n_{\ge 0} $, then $ \alpha + \gamma > \beta + \gamma $.

This is also simple to verify. if $ \alpha $ has a total degree larger than $ \beta $, then so is $ \alpha + \gamma $ and $ \beta + \gamma $. Otherwise if the rightmost element of $ \alpha - \beta $ is negative, then so is $ \alpha + \gamma $ and $ \beta + \gamma $ as well.

(iii) > is a well ordering

For any set of $ n $ tuple, their total order is a set of non-negative integer and therefore there exist a smallest total degree, consider that subset of $ n $ tuples with smallest total degree.

For any set of $ n $ tuple with the same total order, their last element is an integer, and therefore exists a smallest first element, consider that subset of $ n $ tuples with smallest total degree and smallest last element. (*)

Repeat the above until we find the one with every element smallest. Now we have found a smallest element.

Suppose we have two elements $ \alpha $ and $ \beta $ with same total degree to compare with and $ \alpha $ has a smallest last element, then $ \alpha - \beta $ will have a negative rightmost non-zero element.

UTM Ideals Varieties and Algorithm - Chapter 2 Section 2 Exercise 4

Problem:

Solution:

All we needed to do for this problem is to verify the three rules.

(i) > is a total (or linear order) on $ \mathbf{Z}^n_{\ge 0} $

This is simple to verify according to the definition. As long as two monomials are not the same, then either one is strictly larger than the other.

(ii) If $ \alpha > \beta $ and $ \gamma \in \mathbf{Z}^n_{\ge 0} $, then $ \alpha + \gamma > \beta + \gamma $.

This is also simple to verify. if $ \alpha $ has a total degree larger than $ \beta $, then so is $ \alpha + \gamma $ and $ \beta + \gamma $. Otherwise if $ \alpha $ is lexicographically larger than $ \beta $, then so is $ \alpha + \gamma $ and $ \beta + \gamma $ as well.

(iii) > is a well ordering

For any set of $ n $ tuple, their total order is a set of non-negative integer and therefore there exist a smallest total degree, consider that subset of $ n $ tuples with smallest total degree.

For any set of $ n $ tuple with the same total order, their first element is an integer, and therefore exists a smallest first element, consider that subset of $ n $ tuples with smallest total degree and smallest first element.

Repeat the above until we find the one with every element smallest. Now we have found a smallest element.

UTM Ideals Varieties and Algorithm - Chapter 2 Section 2 Exercise 3

Problem:

Solution:

Here is the Exercise 1 statement.

Okay, I know this is stupid, this is just an exercise!

Part (a)
lex order: $ -z^2 + z + 3y + x^3 + x^2 + 2x $
$ LM(f) = z^2 $
$ LT(f) = -z^2 $
$ multideg(f) = (2, 0, 0) $
(2, 0, 0)
(1, 0, 0)
(0, 1, 0)
(0, 0, 3)
(0, 0, 2)
(0, 0, 1)

grlex order: $ x^3 - z^2  + x^2 + z + 3y + 2x $
$ LM(f) = x^3 $
$ LT(f) = x^3 $
$ multideg(f) = (0, 0, 3) $
(0, 0, 3)
(2, 0, 0)
(0, 0, 2)
(1, 0, 0)
(0, 1, 0)
(0, 0, 1)

grevlex order: $ x^3 + z^2 - x^2 + z + 3y + 2x $
$ LM(f) = x^3 $
$ LT(f) = x^3 $
$ multideg(f) = (0, 0, 3) $
(0, 0, 3)
(2, 0, 0)
(0, 0, 2)
(1, 0, 0)
(0, 1, 0)
(0, 0, 1)

Part (b)
lex order: $ -3x^5yz^4  + xyz^3 + 2x^2y^8 - xy^4 $
$ LM(f) = x^5yz^4 $
$ LT(f) = - 3x^5yz^4 $
$ multideg(f) = (4, 1, 5) $
(4, 1, 5)
(3, 1, 1)
(0, 8, 2)
(0, 4, 1)

grlex order: $ -3x^5yz^4 + 2x^2y^8 + xyz^3 - xy^4 $
$ LM(f) = x^5yz^4 $
$ LT(f) = - 3x^5yz^4 $
$ multideg(f) = (4, 1, 5) $
(4, 1, 5)
(0, 8, 2)
(3, 1, 1)
(0, 4, 1)

grevlex order: $ 2x^2y^8 - 3x^5yz^4 + xyz^3 - xy^4 $
$ LM(f) = x^2y^8 $
$ LT(f) =  2x^2y^8 $
$ multideg(f) = (0, 8, 2) $
(0, 8, 2)
(4, 1, 5)
(3, 1, 1)
(0, 4, 1)

UTM Ideals Varieties and Algorithm - Chapter 2 Section 2 Exercise 2

Problem:

Solution:

Part (a) grlex
Part (b) grevlex
Part (c) lex

UTM Ideals Varieties and Algorithm - Chapter 2 Section 2 Exercise 1

Problem:

Solution:

It is a really simple sorting exercise, so let's do some warmup.

Part (a)
lex order: $ x^3 + x^2 + 2x + 3y - z^2 + z $
$ LM(f) = x^3 $
$ LT(f) = x^3 $
$ multideg(f) = (3, 0, 0) $
(3, 0, 0)
(2, 0, 0)
(1, 0, 0)
(0, 1, 0)
(0, 0, 2)
(0, 0, 1)

grlex order: $ x^3 + x^2 - z^2 + 2x + 3y + z $
$ LM(f) = x^3 $
$ LT(f) = x^3 $
$ multideg(f) = (3, 0, 0) $
(3, 0, 0)
(2, 0, 0)
(0, 0, 2)
(1, 0, 0)
(0, 1, 0)
(0, 0, 1)

grevlex order: $ x^3 + x^2 - z^2 + 2x + 3y + z $
$ LM(f) = x^3 $
$ LT(f) = x^3 $
$ multideg(f) = (3, 0, 0) $
(3, 0, 0)
(2, 0, 0)
(0, 0, 2)
(1, 0, 0)
(0, 1, 0)
(0, 0, 1)

Part (b)
lex order: $ -3x^5yz^4 + 2x^2y^8  - xy^4 + xyz^3 $
$ LM(f) = x^5yz^4 $
$ LT(f) = - 3x^5yz^4 $
$ multideg(f) = (5, 1, 4) $
(5, 1, 4)
(2, 8, 0)
(1, 4, 0)
(1, 1, 3)

grlex order: $ -3x^5yz^4 + 2x^2y^8  - xy^4 + xyz^3 $
$ LM(f) = x^5yz^4 $
$ LT(f) = - 3x^5yz^4 $
$ multideg(f) = (5, 1, 4) $
(5, 1, 4)
(2, 8, 0)
(1, 4, 0)
(1, 1, 3)

grevlex order: $ 2x^2y^8 - 3x^5yz^4 - xy^4 + xyz^3 $
$ LM(f) = x^2y^8 $
$ LT(f) =  2x^2y^8 $
$ multideg(f) = (2, 8, 0) $
(2, 8, 0)
(5, 1 ,4)
(1, 4, 0)
(1, 1, 3)

UTM Ideals Varieties and Algorithm - Chapter 2 Section 1 Exercise 5

Problem:

Solution:

For part (a), the number of monomials is easy to count by listing them in a pyramid like this

$
\begin{array}{cccc}
   x^0 &            &        &        \\
   x^1 & y^1        &        &        \\
   x^2 & x^1y^1     & y^2    &        \\
\cdots & \cdots     & \cdots &  \\
   x^m & x^{m-1}y^1 & \cdots & y^m
\end{array}
$

Now counting them is trivial, it is just $ 1 + 2 + \cdots + (m + 1) = \frac{(m+1)(m+2)}{2} $

For part (b), I read part (c) as a hint. It doesn't quite mention what does it mean by "monomial" and "linear dependent".

I figured it actually means regarding polynomial as vectors. Notice when we add two polynomials, we need to match the degree when we add terms together, so a polynomial is really a vector (can be think of as tuple of numbers).

Now, let imagine if we expand $ [f(t)]^a[g(t)]^b $, the lowest degree term is constant, and the highest degree term is $ t^{na}t^{nb} \le t^{mn} $, and the expansion could have terms of any power of $ t $ in between. We can then think of them as vector space of dimension $ mn + 1 $

If we think of the collection of all polynomials of form $ [f(t)]^a[g(t)]^b $, by part (a), there are $ \frac{(m+1)(m + 2)}{2} $ of them, and all of them are vectors of dimension $ mn + 1 $, so if $ \frac{(m+1)(m + 2)}{2} > mn + 1 $, then by definition these vectors must be linear dependent.

As for part (c), we know those 'vectors' are linear dependent. We can find ourselves a formula $ \sum a_i p_i = 0 $, because these $ p_i $ are just $ x^a y^b $, so the overall formula is a polynomial in $ k[x, y] $.

Suppose a point is on the parametric curve, we know for sure that it is on the polynomial we found. On the other hand, for a point on the polynomial, we do NOT really know if it is on the parametric curve or not, that's why the problem is carefully crafted and say that the parametric curve is contained in the variety, not that the parametric curve IS the variety.

Part (d) is basically the same idea as part (b) and (c) except we go up one dimension. We consider the 'monomial' $ [f(t, u)]^a[g(t, u)]^b[h(t, u)]^c $.

To count the number of these 'monomials', we need to be more imaginative. Consider a pile of balls arranged in a tetrahedral shape like this.

The red ball represents the 'monomial' $ [f(t,u)]^0[g(t, u)]^0[h(t, u)]^0 $, the blue ball represents $ [f(t,u)]^1[g(t, u)]^0[h(t, u)]^0 $ and so on. The total number of 'monomials' is known as the tetrahedral numbers and there is $ \frac{m(m+1)(m+2)}{6} $ of them.

The total number of terms in such expression, however, is going to be bounded by the degree of $ t $ and $ u $ just like what we did in part (b). The maximum degree in $ t $ and $ u $ is both mn. So there can be at most $ (mn + 1)^2 $ terms.

Therefore we can still pick $ m $ such that $ \frac{m(m+1)(m+2)}{6} > (mn+1)^2 $ and therefore we can still argue for the vectors being linearly dependent.

Once we have that linear dependency, we can have the  $ \sum a_i p_i = 0 $ expression again, and once again that will be our $ F $ for the surface case!

UTM Ideals Varieties and Algorithm - Chapter 2 Section 1 Exercise 4

Problem:

Solution:

For part (a), in order to show a set is an ideal, we check the two conditions for ideals.

Condition 1: If $ a \in I $, then $ h a \in I $ for all $ h \in R $.

This is true for I because if $ a \in I $, then $ a = x_{t_1}f_1 +  \cdots + x_{t_m}f_m $,
so $ ha = h(x_{t_1}f_1 +  \cdots + x_{t_m}f_m) = x_{t_1}(hf_1) +  \cdots + x_{t_m}(hf_m) \in I $.

Condition 2: If $ a \in I $ and $ b \in I $, then $ a + b \in I $.

This is also true because

$ a \in I $, then $ a = x_{t_1}f_1 +  \cdots + x_{t_m}f_m $,
$ b \in I $, then $ b = x_{u_1}g_1 +  \cdots + x_{u_m}g_m $,

The sum then must also be the same form and therefore $ a + b \in I $.

For part (b), if $ I $ has a finite generating set, then each element is a polynomial and therefore by definition above, a finite linear combination of monomials.

Therefore the number of variables involved in that finite generating set must be finite, but the ideal has infinite number of variables. So there cannot be a finite generating set.

UTM Ideals Varieties and Algorithm - Chapter 2 Section 1 Exercise 3

Problem:

Solution:

For part (a), note that according to the errata, the last equation should be $ x_3 = -t + 6 $.

First note that all the equations are linear and there is one parameter, it is a line. We should expect two linear equations defining two planes.

From the first equation, it is obvious that $ t = x_1 + 5 $, so we get from the second equation $ x_2 = 2t + 1 = 2 (x_1 + 5) + 1 = 2x_1 + 11 $, and from the third equation $ x_3 = -t + 6 = -(x_1 + 5) + 6 = 1 - x_1 $, so the solution is:

$ x_2 = 2x_1 + 11 $
$ x_3 = 1 - x_1 $

Part (b) is more complicated, it is a two dimensional 'plane' in a 4 dimensional space. Adhoc methods like the previous problem does not work great, so we will try something different. We model the problem using this matrix.

$ \begin{array}{ccccccc}t & u & x_1 & x_2 & x_3 & x_4 & t\\2 & -5 & -1 & 0 & 0 & 0 & 0\\1 & 2 & 0 & -1 & 0 & 0 & 0\\-1 & 1 & 0 & 0 & -1 & 0 & 0\\1 & 3 & 0 & 0 & 0 & -1 & 0\end{array} $

Next, we find the reduced row echelon form using MATLAB (using the function rref), and we get this.

$ \begin{array}{ccccccc}t & u & x_1 & x_2 & x_3 & x_4 & t\\1 & 0 & 0 & 0 & 0.75 & -0.25 & 0\\0 & 1 & 0 & 0 & -0.25 & -0.25 & 0\\0 & 0 & 1 & 0 & 2.75 & 0.75 & 0\\0 & 0 & 0 & 1 & 0.25 & -0.75 & 0\end{array} $

We claim that the last two rows is our solution. To see that, any point that satisfied the parametrization must satisfy all four equations, and therefore it satisfy the last two. For any point satisfy the last two equations, we can always find $ t $ and $ u $ by equation 1 and 2, so we have proved the answer is

$ x_1 + 2.75x_3 + 0.75x_4 = 0 $

$ x_2 + 0.25x_3 - 0.75x_4 = 0 $

Part (c) is pretty easy, it is simple to inspect the answer is

$ x^4 = y $

$ x^7 = z $

UTM Ideals Varieties and Algorithm - Chapter 2 Section 1 Exercise 2

Problem:

Solution:

For part (a), we can use MATLAB to compute the reduced row echelon form quickly.

rref([[2 3 -1;1 -1 0;3 7 -2] [9;1;17]])

That gives

   1.00000   0.00000  -0.20000   2.40000
   0.00000   1.00000  -0.20000   1.40000
   0.00000   0.00000   0.00000   0.00000

which means

$ x - 0.2z = 2.4 $
$ y - 0.2z = 1.4 $

That give the parametrization $ (2.4 + 0.2t, 1.4 + 0.2t, t) $

For part (b), we could use MATLAB again, but it is simple so I will skip and do that manually.

It is obvious that we need two parameters, and it is easy to have $ x_1 = u $ and $ x_3 = v $ as the parameters, so the second equation gives $ x_2 = u + v $.

The first equation then give $ u + (u + v) - v - x_4 = 0 $, so the parametrization is $ (u, u + v, v, 2u) $.

For part (c), the answer is right in front of us if we simply let $ x = w $ be the parameter, so the parametrization is simply $ (w, w^3, w^5) $.

UTM Ideals Varieties and Algorithm - Chapter 2 Section 1 Exercise 1

Problem:

Solution:

What would you do if you already have a hammer and you are seeing a nail?

Nail it!

My program for computing GCD and division just fit the purpose, so i just do it.

from polynomial_module import *

# check if polynomial poly is in the ideal defined by the collection of polynomials in ideal
def is_in_ideal(poly, ideal):
    gcd = ideal[0]
    i = 1
    while (i < len(ideal)):
        gcd = polynomial.polynomial_gcd(gcd, ideal[i])
        i = i + 1
    (quotient, remainder) = polynomial.polynomial_divide(poly, gcd)
    return remainder.isZero()
    
def problem_2_1_1():
    print is_in_ideal(polynomial.from_string("x^2 - 3x + 2"), [polynomial.from_string("x - 2")])
    print is_in_ideal(polynomial.from_string("x^5 - 4x + 1"), [polynomial.from_string("x^3 - x^2 + x")])
    print is_in_ideal(polynomial.from_string("x^2 - 4x + 4"), [polynomial.from_string("x^4 - 4x^2 + 12x - 8"), polynomial.from_string("2x^3 - 10x^2 + 16x - 8")])
    print is_in_ideal(polynomial.from_string("x^3 - 1"), [polynomial.from_string("x^9 - 1"), polynomial.from_string("x^5 + x^3 - x^2 - 1")])

The answers are:

a) Yes
b) No
c) Yes
d) Yes

UTM Ideals Varieties and Algorithm - Chapter 1 Section 5 Exercise 17

Problem:

Solution:

This is basically exercising the algorithm we developed in the last problem, the flow goes like this

$ I(V(f_1, f_2)) = I(V(g)) $
$ I(V(g)) = \langle g_{\text{red}} \rangle $
$ g_{\text{red}} = \frac{g}{d} $
$ d = gcd(g, g') $

$ g = x^4 - 2x^3 + 2x - 1 $
$ g' = 4x^3 - 6x^2 + 2 $
$ d = x^2 - 2x + 1 $
$ g_{\text{red}} = x^2 - 1 $

Therefore $ I(V(x^5 - 2x^4 + 2x^2 - x, x^5 - x^4 - 2x^3 + 2x^2 + x - 1)) = \langle x^2 - 1 \rangle $

All these are computed using this program

print "Problem 17"
f = polynomial.from_string("x^5 - 2x^4 + 2x^2 - x")
g = polynomial.from_string("x^5 - x^4 - 2x^3 + 2x^2 + x - 1")
gcd = polynomial.polynomial_gcd(f, g)
gcdd = gcd.derivative()
d = polynomial.polynomial_gcd(gcd, gcdd)
(gred, r) = polynomial.polynomial_divide(gcd, d)
print gcd
print gcdd
print d
print gred

UTM Ideals Varieties and Algorithm - Chapter 1 Section 5 Exercise 16

Problem:

Solution:

The previous exercises basically outlined the whole algorithm.

First, find the GCD, $ g $, of $ f_1, \cdots, f_s $. We know that $ V(f_1, \cdots, f_s) = V(g) $.

Next, compute $ g_{\text{red}} = \frac{g}{GCD(g, g')} $

Now we know $ I(V(f_1, \cdots, f_s)) = I(V(g)) = \langle g_{\text{red}} \rangle $

UTM Ideals Varieties and Algorithm - Chapter 1 Section 5 Exercise 15

Problem:

Solution:

Part (a) is obvious

$ \begin{eqnarray*} & & \frac{f}{GCD(f, f')} \\ &=& \frac{c(x - a_1)^{r_1} \cdots (x - a_n)^{r_n}}{(x - a_1)^{r_1 - 1} \cdots (x - a_n)^{r_n - 1}} \\ &=& c(x - a_1) \cdots (x - a_n) \\ &=& f_{\text{red}} \end{eqnarray*} $

Part (b) is just an application of the formula.

print "Problem 15"
f = polynomial.from_string("x^11 - x^10 + 2x^8 - 4x^7 + 3x^5 - 3x^4 + x^3 + 3x^2 - x - 1")
fd = f.derivative()
g = polynomial.polynomial_gcd(f, fd)
(q, r) = polynomial.polynomial_divide(f, g)
print q

The square free part of the polynomial is $ x^5 + x^2 - x - 1 $

UTM Ideals Varieties and Algorithm - Chapter 1 Section 5 Exercise 14

Problem:

Solution:

Part (a)

$ f' = r(x - a)^{r-1}h + (x-a)^r h' = (x - a)^{r-1}(rh + (x-a) h') $

Therefore $ h_1 = rh + (x-a) h' $, $ h_1(a) = rh(a) + (a - a)h' = rh(a) \ne 0 $.

Part (b)

Using product rule, we differentiate one of the term and keep the rest, and then we sum them up, so the derivative is

$ f' = \sum\limits_{k = 1}^{n}\left(cr(x-a_k)^{r_k - 1}\prod\limits_{j=1, j \ne k}^{n}(x - a_j)^{r_j}\right) $

Therefore, for the final sum, we can always factor out $ (x - a_1)^{r_1 - 1} \cdots (x - a_n)^{r_n - 1}$

$ f' = \prod\limits_{j=1}^{n}(x - a_j)^{r_j - 1} \sum\limits_{k = 1}^{n}\left(cr\prod\limits_{j=1, j \ne k}^{n}(x - a_j)\right) $

Now after factoring out, the $ k $ term is simply $ cr(x - a_1) \cdots (x - a_n) $ (the product goes without $ (x - a_k) $), so the $ k $ term does not vanish for $ a_k $, but all other terms does, That's why $ H $ does not vanish for any $ a_k $.

Part (c)

With part (b), we proved $ (x - a_1)^{r_1 - 1} \cdots (x - a_n)^{r_n - 1} $ is a common factor. The only roots in $ f $ is $ \{ a_1 \cdots a_n \} $, so if the common factor is not greatest, we contradict the fact that $ H $ does not vanish for any of those roots. 

UTM Ideals Varieties and Algorithm - Chapter 1 Section 5 Exercise 13

Problem:

Solution:

Throughout the problem, we let $ f(x) = \sum\limits_{i = 0}^{n} c_i x^i $, $ g(x) = \sum\limits_{i = 0}^{n} d_i x^i $,

Part (a)

$ \begin{eqnarray*} & & (bf)' \\ &=& \sum\limits_{i = 1}^{n} i c_i b x^{i-1} \\ &=& b \sum\limits_{i = 1}^{n} i c_i x^{i-1} \\ &=& bf' \end{eqnarray*} $

Part (b) - suppose the two polynomials do not have same degree, just pad the shorter one with 0 coefficients.

$ \begin{eqnarray*} & & (f + g)' \\ &=& \sum\limits_{i = 1}^{n} i (c_i + d_i) x^{i-1} \\ &=& \sum\limits_{i = 1}^{n} i c_i x^{i-1} + \sum\limits_{i = 1}^{n} i d_i x^{i-1}\\ &=& f' + g' \end{eqnarray*} $

Part (c)

$ \begin{eqnarray*} & & (fg)' \\ &=& ((\sum\limits_{i = 0}^{n}c_i x^i)(\sum\limits_{j = 0}^{n}d_j x^j))' \\ &=& (\sum\limits_{i = 0}^{n}\sum\limits_{j = 0}^{n}c_i d_j x^{i+j})' \\ &=& \sum\limits_{i = 0}^{n}\sum\limits_{j = 0}^{n}(i + j)c_i d_j x^{i+j-1} \\ &=& \sum\limits_{i = 0}^{n}\sum\limits_{j = 0}^{n}ic_i d_j x^{i+j-1} + \sum\limits_{i = 0}^{n}\sum\limits_{j = 0}^{n}jc_i d_j x^{i+j-1} \\ &=& (\sum\limits_{i = 1}^{n}ic_i x^{i-1})(\sum\limits_{j = 0}^{n}d_j x^j) + (\sum\limits_{i = 0}^{n}c_ix^{i})(\sum\limits_{j = 1}^{n}j d_j x^{j-1}) \\ &=& f'g + fg' \end{eqnarray*} $

Note - in the third and fourth equal sign, the double summation should exclude $ i + j = 0 $ case, that would explain the switching of summation limits on the fifth equal sign.

UTM Ideals Varieties and Algorithm - Chapter 1 Section 5 Exercise 12

Problem:

Solution:

Part (a) is simple.

A point is in the variety if it is a root.

For part (b).

$ g \in I(V(f))  \Leftrightarrow g(a_i) = 0 \text{ }, \forall i \Leftrightarrow g = f_{\text{red}}h \Leftrightarrow g \in \langle f_{\text{red}} \rangle $

UTM Ideals Varieties and Algorithm - Chapter 1 Section 5 Exercise 11

Problem:

Solution:

Part (a) is really just another way of stating the fundamental theorem of algebra. Note that the set $ V(f) $ is simply the set of root of $ f $.

Part (b), GCD is 1 $ \Leftrightarrow $ these polynomial do not have a common monic factor $ \Leftrightarrow $ these polynomial does not have a common root $ \Leftrightarrow $ the variety is the empty set.

Part (c), Compute the GCD, and return the variety is empty if the GCD is 1.

UTM Ideals Varieties and Algorithm - Chapter 1 Section 5 Exercise 10

Problem:

Solution:

The key idea is to return more values in each call to GCD.

Function ExtendedGCD(f, g) = (A, B, h):
  if (degree(A) > degree(B)):
    return ExtendedGCD(g, f)
  else:
    (quotient, remainder) = divide(A, B)
    if (remainder == 0):
      # A - B * quotient = 0
      # A + B - B * quotient = B
      # A + B * (1 - quotient) = B
      return (1, 1-quotient, B)
    else
      (p, q, gcd) = GCD(B, remainder)
      # A - B * quotient = remainder
      # p * B + q * remainder = gcd
      # p * B + q * (A - B * quotient) = gcd
      # q * A + (p - q * quotient) * B = gcd
      return (q, p - q * quotient, gcd)

Now even my pseudocode are pythonic!