Homework 1

This homework covers the material from lectures 1 to 7.

Due date: May 30th, 10pm Waterloo time.

LaTeX template, in case you want to write it in LaTeX.

Required Exercises

For the homework, unless otherwise specified, we will be working over a field $\mathbb{F}$ of characteristic $0$.

Problem 1 - Relating Size and Depth (20 points)

Recall that [Borodin 1977, Lemma 1] states that there is a TM $M$ solving the circuit value problem (CVP) on input $(C, x)$ with $SPACE_M(C, x) = O(DEPTH(C) + \log SIZE(C))$. In lecture 2 we saw a proof that $SPACE_M(C, x) = O(DEPTH(C) \cdot \log SIZE(C))$.

In this problem we will formally fully design and prove the improved relationship between size and depth given in [Borodin 1977, Lemma 1].

Provide a full description of the algorithm which achieves the above space complexity, together with a formal analysis of the space complexity of your algorithm.

The input circuit is encoded as a string where each node has an address, type (AND, OR, NOT) and the addresses of its children. The input $x$ is encoded as a string of bits.

Problem 2 - Linear System Solving in Parallel (20 points)

In this problem we will work out the details of a result from lecture 2 that was only stated in class.

Design and analyse a parallel algorithm for the problem of solving a system of linear equations, described as follows:

LINEAR-SYSTEM($A, b$):

• Input: matrix $A \in \mathbb{F^{m \times n}}$ and vector $b \in \mathbb{F^m}$.
• Output: vector $x \in \mathbb{F^n}$ such that $Ax = b$, if one exists (else output FAIL).

Problem 3 - Computing Basic Operations on Ideals (20 points)

Given two ideals $I := (f_1, \ldots, f_r)$ and $J := (f_{r+1}, \ldots, f_s)$ in $\mathbb{F}[x_1, \ldots, x_n]$, show how to compute the following operations by using the algorithm to solve a homogeneous system of polynomial equations:

Part 1 (10 points)

The intersection $I \cap J$ of the two ideals $I$ and $J$.

Part 2 (10 points)

The colon ideal $I : J$ of the two ideals $I$ and $J$.

Problem 4 - Monomial Orderings and Division Algorithm (20 points)

Let us consider the polynomial ring $R := \mathbb{F}[x_1, x_2, \ldots, x_n]$.

Part 1 (5 points)

The graded lexicographic order (GLex) is defined as follows: given monomials $x^{\alpha}, x^{\beta} \in R$, we say that $x^{\alpha} \succ_{GLex} x^{\beta}$ if and only if

1. $\sum_{i=1}^n \alpha_i > \sum_{i=1}^n \beta_i$ or
2. $\sum_{i=1}^n \alpha_i = \sum_{i=1}^n \beta_i$ and $x^{\alpha} \succ_{Lex} x^{\beta}$.

Show that GLex is a monomial ordering on $R$.

Part 2 (5 points)

The graded reverse lexicographic order (GRevLex) is defined as follows: given monomials $x^{\alpha}, x^{\beta} \in R$, we say that $x^{\alpha} \succ_{GRevLex} x^{\beta}$ if and only if

1. $\sum_{i=1}^n \alpha_i > \sum_{i=1}^n \beta_i$ or
2. $\sum_{i=1}^n \alpha_i = \sum_{i=1}^n \beta_i$ and in the difference $\alpha - \beta$ the rightmost non-zero entry is negative.

Show that GRevLex is a monomial ordering on $R$.

Part 3 (5 points)

There is a general method to specify a monomial ordering on $R$ via a linear transformation on the exponent vectors. Given any real matrix $M \in \mathbb{R}^{m \times n}$, with rows denoted by $M_1, \dots, M_m \in \mathbb{R}^n$, we can define a monomial order $\succ_M$ on $R$ as follows: given monomials $x^{\alpha}, x^{\beta} \in R$, we say that $x^{\alpha} \succ_M x^{\beta}$ if and only if there exists $i \in [m]$ such that $\langle M_j, \alpha \rangle = \langle M_j, \beta \rangle$ for all $j < i$ and $\langle M_i, \alpha \rangle > \langle M_i, \beta \rangle$.

Prove that the following matrices $A, B, C \in \mathbb{R}^{3 \times 3}$ define the Lex, GRevLex and GRevLex monomial orderings over $\mathbb{F}[x_1, x_2, x_3]$, respectively:

$$ A = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}, \quad B = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}, \quad C = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 0 & -1 \\ 0 & -1 & 0 \end{pmatrix}. $$

Remark: By a result of Robbiano, any monomial ordering on $R$ can be obtained from an invertible matrix $M \in \mathbb{R}^{n \times n}$.

Part 4 (5 points)

Solve exercise 5 from [CLO1, Section 2.3].

Problem 5 - Gröbner Bases (20 points)

Part 1 - from [CLO1, Chapter 2.3] (10 points)

Determine if the following sets of polynomials are Gröbner bases, and in case they are not, compute the reduced Gröbner basis for the ideal they generate:

1. $G := (x^2-y, x^3-z)$, with respect to the graded lexicographic order (GLex).
2. $G := (xy^2-xz + y, xy - z^2, x - yz^4)$, with respect to the lexicographic order (Lex).

Part 2 - from [CLO1, Chapter 2.9] (10 points)

Suppose that $I = (f_1, \ldots, f_r)$ is an ideal in $\mathbb{F}[x_1, \ldots, x_n]$ such that $gcd(LM(f_i), LM(f_j)) = 1$ for all $i \neq j$. Show that the set $G = \{f_1, \ldots, f_r\}$ is a Gröbner basis of $I$.

Practice Problems

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

• All exercises from [CLO1, Chapter 2].
• All exercises from [CLO2, Chapters 1, 2].
• Exercises 3.5.1 to 3.5.5 from [GP, Chapter 3].