Homework 4
This homework covers the material from lectures 14 to 17
Due date: March 22nd.
LaTeX template for homework 4, in case you want to write it in LaTeX.
Required Exercises
Remember that you are only required to turn in 5 out of the 6 exercises below.
Problem 1 - Polynomial Parametric Curves in Algebraic Sets - CLO exercise 2.1.5 (20 points)
- Show that the number of distinct monomials $x^a y^b$ of total degree $\leq m$ in $\mathbb{F}[x,y]$ is equal to $(m+1)(m+2)/2$.
- Show that if $f(t)$ and $g(t)$ are polynomials of degree $\leq n$ in $t$, then for $m$ large enough, the “monomials” $$ f(t)^a g(t)^b $$ with $a+b \leq m$ are linearly dependent.
- Deduce from part (2) that if $C$ is a curve in $\mathbb{F}^2$ given parametrically by $x = f(t), \ y = g(t)$ for $f(t), g(t) \in \mathbb{F}[t]$, then $C$ is contained in $V(F)$ for some non-zero $F \in \mathbb{F}[x,y]$.
- Generalize parts (1), (2) and (3) to show that any polynomial parametric surface $$ x = f(t,u), \ \ y = g(t,u), \ \ z = h(t,u) $$ is contained in an algebraic surface $V(F)$, where $F \in \mathbb{F}[x,y,z]$ is non-zero.
Problem 2 - Exercises on S-polynomials - from CLO 3.6 (20 points)
- Compute $S(f, g)$ using the lex order for:
- $f = 4x^2z - 7y^2, \ g = xyz^2 + 3xz^4$
- $f = x^4y - z^2, \ g = 3xz^2 -y$
- Does $S(f,g)$ depend on the monomial order being used? Illustrate your assertion with examples.
- Prove that $multideg(S(f, g)) < \gamma$, where $x^\gamma = LCM(LM(f), LM(g))$. Explain why this inequality is a precise version of the claim that S-polynomials are designed to produce cancellation.
- Let $f, g \in \mathbb{F}[x_1, \ldots, x_n]$ be nonzero and $x^\alpha, x^\beta$ be monomials. Verify that
$$ S(x^\alpha f, x^\beta g) = x^\gamma S(f,g) $$
where
$$ x^\gamma = \dfrac{LCM(x^\alpha LM(f), x^\beta LM(g))}{LCM(LM(f), LM(g))}. $$
Problem 3 - Exploring Groebner bases - CLO 2.6 and 2.7 (20 points)
- Let $I \subseteq \mathbb{F}[x_1, \ldots, x_n]$ be an ideal, and let $G$ be a Groebner basis of $I$.
- Show that $f^G = g^G$ if, and only if, $f-g \in I$.
- Show that $(f+g)^G = f^G + g^G$
- Deduce that $(fg)^G = (f^G \cdot g^G)^G$
- Let $G$ and $G'$ be Groebner bases for an ideal $I$ with respect to the same monomial order in $\mathbb{F}[x_1, \ldots, x_n]$. Show that $f^G = f^{G’}$ for any $f \in \mathbb{F}[x_1, \ldots, x_n]$. Hence, the remainder on division by a Groebner basis is even independent of which Groebner basis we use, as long as we use the same monomial ordering.
- Show that $\{ y - x^2, z - x^3 \}$ is not a Groebner basis for $(y - x^2, z - x^3)$ with lex order with $x > y > z$
Problem 4 - Groebner bases and Geometry - CLO 2.8 and 2.9 (20 points)
- Groebner basis and Lagrange interpolation: let $V = \{ (a_1, b_1), \ldots, (a_n, b_n) \} \subset \mathbb{F}^2$, where $a_1, \ldots, a_n$ are distinct. The Lagrange interpolation polynomial of $V$ is given by:
$$ h(x) = \sum_{i=1}^n b_i \cdot \prod_{j \neq i} \dfrac{x-a_j}{a_i - a_j} \in \mathbb{F}[ x ] $$
We will now see how $h(x)$ relates to the reduced Groebner basis of $I(V) \subseteq \mathbb{F}[x, y]$.
- Prove that $I(V) = (f(x), y - h(x))$, where $f(x) = \prod_{i=1}^n (x-a_i)$.
Hint: divide $g \in I(V)$ by $f(x), y-h(x)$ using lex order with $y > x$.
- Prove that $\{ f(x), y-h(x) \}$ is the reduced Groebner basis for $I(V) \subseteq \mathbb{F}[x,y]$ for lex order with $y > x$.
- A critical point of a differentiable function $f(x,y)$ is a point where all the partial derivatives $\partial_x f$ and $\partial_y f$ vanish simultanously. When $f \in \mathbb{R}[x,y]$, it follows that the critical points can be found by applying our techniques to the system of polynomial equations
$$ \partial_x f = \partial_y f = 0 $$
Consider the function:
$$ f(x,y) = (x^2+ y^2-4)(x^2 + y^2 -1) + (x-3/2)^2 + (y-3/2)^2 $$
- Find all critical points of $f$
- Classify your critical points as local maxima, local minima, or saddle points.
Hint: use the second derivative test.
- If you didn’t do it before, compute the Groebner basis of the ideal $(\partial_x f , \partial_y f)$
Problem 5 - Computing the invariant ring for the left multiplication action (20 points)
In this exercise we will work out how to prove that the invariant ring for the left multiplication action $G = \mathbb{SL}(n)$ on matrices $V = Mat(n)$ is given by $\mathbb{C}[ X ]^G = \mathbb{C}[\det(X)]$, $X = (x_{i,j})_{i,j=1}^n$.
Let $I$ be the ideal of $\mathbb{C}[X]$ generated by all non-constant, homogeneous invariant polynomials.
- Prove that if a matrix $A \in V$ is singular, then any non-constant homogeneous invariants $p \in I$ must vanish on $A$.
Hint: to show the above, show that for a singular matrix there is a sequence of group elements $\{ g_k \}_{k \geq 1}$ such that $\lim_{k \rightarrow \infty} (g_k \cdot A) = 0$. Then use the fact that polynomials are continuous functions to prove that if $p$ is a homogeneous invariant then $p(A)$ must be equal to zero.
Hint to hint: think of row reduction.
- Conclude that the zero set of all polynomials in $I$ is the set of singular matrices.
Hint: show that a non-singular matrix $B$ is not in the zero set of the polynomials in $I$ by finding one polynomial where $B$ does not evaluate to zero.
-
Conclude that $I = ( \det(X) )$.
-
Since $\det(X)$ is an irreducible polynomial, we showed that $I$ is a prime ideal. From this, conclude that any homogeneous non-constant invariant must be a power of $\det(X)$. Then conclude that $\mathbb{C}[X]^G = \mathbb{C}[\det(X)]$
Problem 6 - Bivariate Factorisation (20 points)
Factor the following polynomial using the bivariate factorisation algorithm from class.
$$p(x,y) = 5x^5y + 2x^4y^2 + 6x^3y^3 - x^2y^4 + 5x^4y - 5x^3y^2 - 3x^2y^3 + 4xy^4 - 7x^3 - x^2y + 8xy^2 + 4y^3 - 6x^2 + 2xy - 3y^2 $$
Where $p(x,y) \in \mathbb{Z}_{17}[x, y]$. You can, and are highly encouraged to, use Macaulay 2 to handle the steps of the algorithm.
Practice Problems
You are not required to submit the solution to these problems, but highly encouraged to attempt them for your own knowledge sake. :)
Any problem from CLO Chapters 2 and 3.
-
Do exercise 13 of CLO 2.10 to understand how different monomial orderings can lead to very different bases.
-
Do exercises 12 and 13 from CLO 3.6 to see when the resultant does not behave nicely with respect to specializations.
-
Exercise 14 from CLO 3.6 to prove property of Resultant under variable substitution.