Homework 3

This homework covers the material from lectures 10 to 13

Due date: March 8th.

PDF version of Homework 3.

LaTeX template for homework 3, 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 - Hensel Lifting and Factoring (20 points)

Given

$$ a(x) = x^4 − 2 x^3 − 233 x^2 − 214 x + 85 $$

and image polynomials

$$ u_0(x) = x^2 − 3 x − 2 \ \ \text{ and } \ \ w_0(x) = x^2 + x + 3,$$

satisfying $a \equiv u_0 w_0 \bmod 7$, lift the image polynomials using Hensel lifting to find (if there exist) $u(x)$ and $w(x)$ in $\mathbb{Z}[ x ]$ such that $a = uw$ and $u \equiv u_0 \bmod 7$ and $w \equiv w_0 \bmod 7$.

Given

$$b(x) = 48 x^4 − 22 x^3 + 47 x^2 + 144$$

and an image polynomials

$$u_0(x) = x^2 + 4 x + 2 \ \ \text{ and } \ \ w_0(x) = x^2 + 4 x + 5$$

satisfying $b \equiv 6 u_0 w_0 \bmod 7$, lift the image polynomials using Hensel lifting to find (if there exist) $u(x)$ and $w(x)$ in $\mathbb{Z}[x]$ such that $b = uw$ and $u \equiv u_0 \bmod 7$ and $w \equiv w_0 \bmod 7$.

Acknowledgment: this problem was given to us by Michael Monagan

Problem 2 - vectors of small norm in lattice (20 points)

Let $g_1, \ldots, g_n \in \mathbb{R}^n$ be linearly independent and $\mathcal{L} = \mathbb{Z} g_1 + \cdots + \mathbb{Z} g_n$ be the lattice they generate. Prove that for any vector $x \in \mathbb{R}^n$ there is a vector $g \in \mathcal{L}$ such that

$$ || x - g ||_2^2 \leq \dfrac{1}{4} \cdot \left( ||g_1||_2^2 + \cdots + ||g_n||_2^2 \right) $$

Hint: Prove it by induction on $n$. For the induction step, find $\lambda \in \mathbb{Z}$ such that the vector $x - \lambda g_n$ has minimal distance to hyperplane spanned by $g_1, \ldots, g_{n-1}$.

Problem 3 - Reducing dimension of a low-dimensional lattice (20 points)

Let $m < n$ be integers. If $b_1, \ldots, b_m \in \mathbb{R}^n$ are linearly independent vectors, then we will show that we can construct vectors $c_1, \ldots, c_m \in \mathbb{R}^{n-1}$ such that the lattices corresponding to $\mathbb{Z} b_1 + \cdots + \mathbb{Z} b_m$ and to $\mathbb{Z} c_1 + \cdots + \mathbb{Z} c_m$ are essentially equivalent (up to a multiplicative constant).

Show that there exists a vector $v \in \mathbb{R}^n$ such that $\langle v , b_i \rangle = 0$, for all $i \in [m]$
Use the Gram-Schmidt procedure and $v$ to construct an orthogonal basis $(h_1, \ldots, h_n)$ of $\mathbb{R}^n$ with each $h_i \in \mathbb{R}^n$, with one of the $h_i$'s orthogonal to every $b_j$ and $|| h_i ||_2 = || h_j ||_2$.
Let $H$ be the $n \times n$ matrix given by $$ H = \begin{pmatrix} h_1^T \\ h_2^T \\ \vdots \\ h_n^T \end{pmatrix}, $$

where the $h_i$'s are the vectors that you constructed in part 2.

Let $$ \begin{pmatrix} c_1 & c_2 & \cdots & c_n \end{pmatrix} = H \cdot \begin{pmatrix} b_1 & b_2 & \cdots & b_n \end{pmatrix},$$

where the matrix of $c_i$'s and $b_j$'s are column matrices.

If $\alpha = || h_i ||_2$ from the previous part, show that for each $k \in [m]$: $$ || c_k ||_2 = \alpha \cdot || b_k ||_2 $$

Show that $H^T \cdot H = \alpha^2 \cdot I$. Show that the lattices $\alpha^2 \left( \mathbb{Z} b_1 + \cdots + \mathbb{Z} b_m \right)$ and $\alpha^2 \left( \mathbb{Z} c_1 + \cdots + \mathbb{Z} c_m \right)$ are equivalent, that is: $$ u \in \alpha^2 \left( \mathbb{Z} c_1 + \cdots + \mathbb{Z} c_m \right) \Leftrightarrow \dfrac{1}{\alpha^2} \cdot H^T u \in \alpha^2 \left( \mathbb{Z} b_1 + \cdots + \mathbb{Z} b_m \right) $$

Thus, a vector $u$ is a shortest vector in $\alpha^2 \left( \mathbb{Z} c_1 + \cdots + \mathbb{Z} c_m \right)$ iff $\dfrac{1}{\alpha^2} \cdot H^T u$ is a shortest vector in $\alpha^2 \left( \mathbb{Z} b_1 + \cdots + \mathbb{Z} b_m \right)$.

But notice that each $c_i$ has its first coordinate equal to $0$, so the $c_i$'s are naturally integer vectors in $\mathbb{R}^{n-1}$.

Problem 4 - Issues with the division algorithm - CLO 2.3.5 (20 points)

Let $f(x,y,z) = x^3 - x^2 y - x^2 z + x, \ f_1(x,y,z) = x^2y - z, \ \text{ and } f_2(x,y,z) = xy -1$.

Compute using the graded lexicographic order: $$ r_1 = \text{ remainder of } f \text{ on division by } (f_1, f_2)$$ $$ r_2 = \text{ remainder of } f \text{ on division by } (f_2, f_1)$$

Your results should be different. Where in the division algorithm did the difference occur?

Is $r = r_1 - r_2$ in the ideal $(f_1, f_2)$? If so, find an explicit expression $r = A f_1 + B f_2$. If not, say why not.
Compute the remainder of $r$ on division by $(f_1, f_2)$. Why could you have predicted your answer before doing the division?
Find another polynomial $g \in (f_1, f_2)$ such that the remainder of division by $g$ by $(f_1, f_2)$ is non-zero.

Hint: $(xy +1 ) \cdot f_2 = x^2y^2 -1$ whereas $y \cdot f_1 = x^2y^2 - yz$.

Does the division algorithm give us a solution to the ideal membership problem for $(f_1, f_2)$? Explain.

Problem 5 - Different monomial orders - CLO 2.4.10 (20 points)

The following orders are called weight orders. Let $u = (u_1, \ldots, u_n) \in \mathbb{R}^n$ such that $u_1, \ldots, u_n$ are positive real numbers which are linearly independent over $\mathbb{Q}$. We say that $u$ is an independent weight vector. Then, for $\alpha, \beta \in \mathbb{N}^n$, define:

$$ \alpha >_{u} \beta \Leftrightarrow u \cdot \alpha > u \cdot \beta $$

This is the weight order determined by $u$.

Use the corollary of Dickson’s lemma from class to prove that $>_{u}$ is a monomial order.
Show that $u = (1, \sqrt{2})$ is an independent weight vector, so that $>_u$ is a weight order on $\mathbb{N}^2$

Problem 6 - Monomial Ideals (20 points)

Let $I_1 = (x^{\alpha_1}, \ldots, x^{\alpha_s})$ and $I_2 = (x^{\beta_1}, \ldots, x^{\beta_t})$ be monomial ideals of $\mathbb{C}[x_1, \ldots, x_n]$, where each $\alpha_i, \beta_j \in \mathbb{N}^n$.

Show that $I_1 \cap I_2$ is generated by the elements $LCM(x^{\alpha_i}, x^{\beta_j})$.
When is $I_1 I_2 = I_1 \cap I_2$? Provide proof of your statement.

Practice Problems

You are not required to submit the solution to these problems, but highly encouraged to attempt them for your own knowledge sake. :)

Problem 1 - Proving that the Swapping Step of LLL decreases potential function

Coming soon

Problem 2 - Structure of monomial ideals - Eisenbud Exercise 3.6

Which monomial ideals are prime? Irreducible? Radical? Primary?