Exercises

Macaulay2 general

Rewriting polynomials

Let \(I = (x^2+y^2,x^2y^2,x^3y-xy^3) \subset \mathbb{Q}[x,y]\).

  1. Check that \(y^4 \in I\).

  2. Write \(y^4\) as a polynomial combination of the above generators

Minimal polynomials

Set \(\alpha = 3^{\frac{1}{5}}\) and \(\beta = 5^{\frac{1}{3}}\).

  1. Compute the minimal polynomial of \(\alpha+\beta\) over \(\mathbb{Q}\).

  2. Represent \(\frac{1}{\alpha + \beta}\) as a polynomial of \(\alpha, \beta\) over \(\mathbb{Q}\).

Geometry

Let \(V\) be Veronese surface in \(\mathbb{P}^5\). It is the image of \(\mathbb{P}^2 \to \mathbb{P}^5\) given by \((x : y : z) \mapsto (x^2 : y^2 : z^2 : xy : xz : yz)\).

  1. Compute the ideal of \(V\) in \(\mathbb{Q}[x_0,\dotsc,x_5]\).

  2. Check that \(V\) is smooth

  3. Does the point \((0 : 0 : 0 : 1 : 1 : 1)\) lie on the variety? How about \((1 : 1 : 1 : 1 : 1 : 1)\)?

  4. Does the line \(L = V(x_0 + x_1 + x_2, x_3, x_4, x_5)\) meet \(V\)?

Ring maps

Consider the endomorphism \(\phi \colon \mathbb{Q}[x,y,z] \to \mathbb{Q}[x,y,z]\) defined by

\[x \mapsto yz, \quad y \mapsto xz, \quad z \mapsto xy\]

Show that \(\phi\) induces an isomorphism on \(\mathbb{Q}[x,y,z]/(xyz-1)\)

Symmetric polynomials

Let \(R = k[x_1,\dotsc,x_n]\). The elementary symmetric polynomials are

\[\begin{split}\begin{align*} e_1(x) &= \sum_i x_i \\ e_2(x) &= \sum_{i<j} x_i x_j \\ &\vdots\\ e_n(x) &= x_1\dotsb x_n \end{align*}\end{split}\]

  1. Given \(n\), generates all elementary symmetric polynomials. Try to write in a functional style avoid loops. The command subsets may help.

  2. Define the ring map \(\phi \colon k[e_1,\dotsc,e_n] \to k[x_1,\dotsc,x_n]\) that sends the symbol \(e_i\) to the \(i\) th elementary symmetric polynomial.

  3. The image of \(\phi\) is precisely the set of symmetric polynomials. Set \(n=4\) and write the following polynomial in terms of elementary symmetric polynomials: -x_1^2*x_2^2*x_3-x_1^2*x_2*x_3^2-x_1*x_2^2*x_3^2-x_1^2*x_2^2*x_4-3*x_1^2*x_2*x_3*x_4-3*x_1*x_2^2*x_3*x_4-x_1^2*x_3^2*x_4-3*x_1*x_2*x_3^2*x_4-x_2^2*x_3^2*x_4-x_1^2*x_2*x_4^2-x_1*x_2^2*x_4^2-x_1^2*x_3*x_4^2-3*x_1*x_2*x_3*x_4^2-x_2^2*x_3*x_4^2-x_1*x_3^2*x_4^2-x_2*x_3^2*x_4^2+x_1*x_2*x_3*x_4+x_1^2+2*x_1*x_2+x_2^2+2*x_1*x_3+2*x_2*x_3+x_3^2+2*x_1*x_4+2*x_2*x_4+2*x_3*x_4+x_4^2

Regular sequences

Let \(M\) be an \(R\)-module. A sequence \(f_1,\dotsc,f_r \in R\) is a regular sequence if \(M \neq \langle f_1,\dotsc,f_r \rangle M\), and \(f_i\) is a nonzerodivisor on \(M/\langle f_1,\dotsc,f_{i-1} \rangle M\) for all \(i\).

  1. Program a routine that, checks whether a given sequence of polynomials \(f_1,\dotsc,f_r\) is a regular sequence on \(R\).

  2. A permutation of a regular sequence may not be a regular sequence. Write a functions that finds all permutations of \(f_1,\dotsc,f_r\) that are regular sequences.

  3. Run the above function for \(R = \mathbb{Q}[x,y,z]\), \(f_1 = (x-1)z\), \(f_2 = (x-1)y\), \(f_3 = x\).

Decomposing

Let \(S, C \subseteq \mathbb{C}[x,y,z]\) be ideals corresponding to a surface and a curve. We define S = ideal(x^5+y^5+z^5-1), and

C = ideal(x*y^5*z-2*x^2*y^3*z^2+x^3*y*z^3-2*y^4+4*x*y^2*z-2*x^2*z^2,y^7-3*x^2*y^3*z^2+2*x^3*y*z^3+x^2*y^4-2*x^3*y^2*z+x^4*z^2-4*y^4+8*x*y^2*z-4*x^2*z^2,x^2*y^5-x^3*y^3*z+x^4*y^2-x^5*z-y^5*z+2*x*y^3*z^2-x^2*y*z^3+2*y^5-x^2*y^2*z-2*x*y^3*z+x^3*z^2+2*x^2*y^2-2*x^3*z-2*y^2*z+2*x*z^2,y^5*z^3-2*x*y^3*z^4+x^2*y*z^5-x*y^4*z^2-2*y^5*z^2+2*x^2*y^2*z^3+2*x*y^3*z^3-x^3*z^4-2*y^6+2*x*y^4*z-2*x^2*y^2*z^2+2*x^3*z^3-2*x^2*y^3+2*x^3*y*z+2*y^2*z^3-2*x*z^4+2*y^3*z-2*x*y*z^2,x^3*y^2*z^3-2*x^2*y^3*z^3-x^4*z^4+2*x^3*y*z^4-2*x*y^6+x^3*y^3*z+2*x^2*y^4*z-x^4*y*z^2-2*x^3*y^2*z^2+2*x^4*z^3-2*x^3*y^3+2*x^4*y*z-x*y^3*z^2+2*y^4*z^2+x^2*y*z^3-2*x*y^2*z^3-4*y^4*z+8*x*y^2*z^2-4*x^2*z^3-2*x^2*y^2+2*x^3*z+2*y^2*z-2*x*z^2,y^6*z^2-2*x*y^4*z^3+x^2*y^2*z^4-2*y^6*z+2*x*y^4*z^2-2*x*y^5+2*x^3*y*z^2-2*x^3*y^2+2*x^4*z+2*y^3*z^2-2*x*y*z^3+2*x*y^2*z-2*x^2*z^2,x^2*y^4*z^2-2*x^2*y^3*z^3-x^4*z^4+2*x^3*y*z^4-2*x*y^6+2*x^3*y^3*z+2*x^2*y^4*z-2*x^4*y*z^2-2*x^3*y^2*z^2+2*x^4*z^3-2*x^3*y^3+2*x^4*y*z-2*x*y^3*z^2+2*y^4*z^2+2*x^2*y*z^3-2*x*y^2*z^3-2*x*y^3*z-4*y^4*z+2*x^2*y*z^2+8*x*y^2*z^2-4*x^2*z^3-4*x^2*y^2+4*x^3*z+4*y^2*z-4*x*z^2,2*x^4*y^2*z^2-x^5*z^3+x^4*y^3+x^5*y*z-x*y^4*z^2+x^2*y^2*z^3+x^6-2*y^6-2*x^2*y^3*z+6*x*y^4*z-2*x^2*y^2*z^2+2*x^2*y^3-2*x^4*z+2*x^3*y*z+y^3*z^2-x*y*z^3+2*x^4-2*y^3*z+x^2*z^2-2*x*y*z^2-4*x^2*z+2*z^2,x^3*y^4*z+x^4*y^3+x^5*y*z-x*y^4*z^2+x^2*y^2*z^3+x^6-2*x^2*y^3*z+2*x*y^4*z+2*x^2*y^3-2*x^4*z+2*x^3*y*z+y^3*z^2-x*y*z^3+2*x^4-2*y^3*z+x^2*z^2-2*x*y*z^2-4*x^2*z+2*z^2,2*x^4*z^5+6*x^4*y*z^3+24*x^2*y^3*z^3-16*x^3*y*z^4+2*x^3*y^4+8*x*y^6+8*x^2*y^4*z+4*x^5*z^2+16*x^3*y^2*z^2+x*y^4*z^2+2*y^5*z^2-8*x^4*z^3-2*x^2*y^2*z^3-4*x*y^3*z^3+x^3*z^4-2*x^2*y*z^4+2*x^5*y+16*x^3*y^3+2*y^6+8*x^4*y*z-6*x*y^4*z-4*y^5*z+2*x^2*y^2*z^2+12*x*y^3*z^2-16*y^4*z^2-6*x^3*z^3-8*x^2*y*z^3+8*x^5+2*x^2*y^3+8*y^5-6*x^3*y*z+4*x^2*y^2*z-24*x*y^3*z+32*y^4*z-4*x^3*z^2-16*x^2*y*z^2-64*x*y^2*z^2+32*x^2*z^3+2*y^2*z^3+8*x^2*y^2-24*x^3*z-2*y^3*z+4*x*y*z^2-4*y^2*z^2+4*x*z^3+8*y*z^3-8*y^2*z+16*x*z^2,x*y^4*z^4-x^2*y^2*z^5-2*x*y^4*z^3-x^3*y^2*z^2-6*x^2*y^3*z^2+x^4*z^3-y^3*z^4+x*y*z^5-2*x^2*y^4-2*x^3*y^2*z-2*x^4*z^2+x*y^2*z^3+2*y^3*z^3-x^2*z^4+2*x*y*z^4-2*x^4*y+2*y^4*z+2*x*y^2*z^2+4*x^2*z^3-4*y^4+4*x^2*y*z+8*x*y^2*z-4*x^2*z^2-2*z^4-2*y*z^2,x^2*y^3*z^4-x^3*y*z^5-4*x^2*y^3*z^3+2*x^3*y*z^4-x^3*y^3*z-4*x^2*y^4*z+x^4*y*z^2-2*x^3*y^2*z^2-y^4*z^3+x*y^2*z^4-2*x^3*y^3-4*x^4*y*z+x*y^3*z^2+4*y^4*z^2-x^2*y*z^3-2*x*y^2*z^3+2*x^2*z^4-2*x^5+4*x*y^3*z-4*y^4*z+4*x^2*y*z^2+8*x*y^2*z^2-4*x^2*z^3+2*x^2*y^2+2*x^3*z-2*y*z^3-2*y^2*z,2*x^4*y*z^4+3*x^5*z^3-x^4*y^3+x^5*y*z+3*x*y^4*z^2-7*x^2*y^2*z^3-x^6+6*y^6+2*x^2*y^3*z-14*x*y^4*z-4*x^3*y*z^2+6*x^2*y^2*z^2-4*x^3*z^3+2*x^2*y^3+2*x^4*z-14*x^3*y*z-y^3*z^2+3*x*y*z^3-6*x^4-2*y^3*z-x^2*z^2+14*x*y*z^2+12*x^2*z-6*z^2)

  1. How many irreducible components do \(S,C\) have?

  2. What does the intersection of the surface and the curve look like? How many distinct points are there on the intersection? What are their multiplicities?

  3. Let \(I = C+S\), but now in the ring \(\mathbb{Z}/11\mathbb{Z}\). How many points (over the algebraic closure) does this ideal correspond to?

  4. How many of these points are in \(\mathbb{Z}/11\mathbb{Z}\)? Find all of them.

Working with files

  1. Let \(R = QQ[x,y,z]\) with a lexicographic monomial order, where \(x > y > z\). Let \(I\) be the ideal

    \[I = (x^3 + y^3 + z^2 - 1, x^7 + y^5 + z^3 - 1)\]

    Compute a Grobner basis of \(I\). (If it’s too slow, change the first \(x^3\) to \(x^2\))

  2. Save this into a file. You can use for example f = "gb.txt" << toExternalString gens gb I;.

  3. We now close the file handle: close f.

  4. You can now admire the file gb.txt, which contains a long Grobner basis.

  5. You can read and evaluate the output by using value get "gb.txt.

  6. How would you avoid future recomputations of the Grobner basis? (hint: viewHelp forceGB).

  7. Consider the same ideal above, but we vary the exponents on \(x\). In other words, let

    \[I_{i,j} = (x^i + y^3 + z^2 - 1, x^j + y^5 + z^3 - 1)\]

    Create a function that takes a pair \((i,j)\), and writes the number \(k\) of total terms in the Lex Grobner basis of \(I_{i,j}\) into a file. Each result should be on a single line, with the format (i,j) has k terms, where i,j,k are replaced by actual values. Run the function for successively larger i,j until it starts taking too long. See for example viewHelp openOutAppend and viewHelp "<<" for inspiration.

Exact eigenvalues and vectors

A matrix with entries in \(\mathbb{Q}\) has eigenvalues and vectors in a finite field extension of \(\mathbb{Q}\), namely \(\mathbb{Q}[i]/(i^2+1)\). Write a function that does the following

  1. Constructs this field.

  2. Computes the characteristic polynomial \(p(\lambda) = \det(M - \lambda I)\) and factors it.

  3. Outputs the eigenvalues and eigenvectors.

For example, the matrix \(\begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix}\) has eigenvalues \(\pm i\), and vectors \([\pm 1, i]^T\).

Solving by elimination

In this exercise we will solve zero-dimensional polynomial systems. Let \(I \subseteq R := k[x_1,\dotsc,x_n]\) be a zero-dimensional ideal.

  1. Suppose \(h\) is a linear polynomial in \(R\). We get a map \(\phi : k[y] \to R/I\). Let \(J = (g(y)) = \ker \phi\). The polynomial \(g(y)\) is called the eliminant of \(h\). Write the function eliminant(h). If you want, you can add an optional parameter Ring => ....

  2. Choose \(h = x_1\), and define a lexicographic monomial order \(x_1 < x_2 < \dotsb < x_n\). The Shape lemma says that the Grobner basis has the form \(g(x_1), x_2 - g(x_1), \dotsc, x_n - g_n(x_1)\). Using this information, find all exact solutions to the system \(I = (x+z+2,z^2+1,y^2-4z-4)\).

  3. (bonus) make the function eliminant(h) faster by using linear algebra instead of a naive kernel computation.

  4. Why is this method not numerically stable? Consider for example \(I = (x(x-10000), y-x^{1000}, z-yx)\)

Solving by eigenvalues

This is a continuation of the previous exercise. As before, let \(I \subseteq R := k[x_1,\dotsc,x_n]\) be a zero-dimensional ideal.

  1. The ring \(R/I\) is a finite-dimensional vector space. The \(R\)-module action is a linear mapping on this space. If \(R = \mathbb{Q}[x,y,z]\) and \(I = (x+z+2,z^2+1,y^2-4z-4)\), compute the three matrices \(M_x, M_y, M_z\) corresponding to multiplication by \(x,y,z\).

  2. For any polynomial \(h \in R\), we have a corresponding multiplication matrix. Write a function that computes this matrix, given the input \(h\).

  3. Choose your favorite polynomial \(h \in R\). Compute the eigenvalues and eigenvectors of \(M_h\). How many are there?

  4. Choose another polynomial \(h \in R\). What happened to the eigenvectors?

  5. Choose your favorite eigenvector. Let \(h_1 = x\), \(h_2 = y\), \(h_3 = z\). What are the three eigenvalues?

  6. Is this numerically better than the method in the previous exercise?

  7. Using this method, implement a function that find all roots (approximately/exactly) for any zero-dimensional ideal \(I\).

Fano varieties

Consider the ideal \(I = (x^3+yz^2-w^2z+w^3) \in \mathbb{C}[x,y,z,w]\) and its corresponding variety \(V(I) \in \mathbb{P}^3\).

  1. What are the dimension and degree of \(I\)?

  2. Without computing, can you guess how many lines lie on \(V(I)\)?

  3. We will compute all lines on \(V(I)\).

    1. We can represent a line in \(\mathbb{P}^3\) in parametric form as

      \[\begin{split}\begin{bmatrix} s & t \end{bmatrix} \begin{bmatrix} p_0 & p_1 & p_2 & p_3 \\ q_0 & q_1 & q_2 & q_3 \end{bmatrix}\end{split}\]

      Construct a ring \(S\) with the 10 parameters above

    2. If we view \(p_i, q_i\) as fixed, the above describes a map from \(\mathbb{P}^1 \to \mathbb{P}^3\). This is a parametrization of a line. Construct the corresponding ring map \(\phi\) from \(R\) to \(S\).

    3. Compute the conditions on the \(p_i, q_i\) so that the parametrized line lies on \(V(I)\). This will be an ideal \(J \in S' := \mathbb{Q}[p_0,\dotsc,p_3,q_0,\dotsc,q_3]\).

    4. We can also describe lines as points on a Grassmannian. Construct a ring \(T\) with variables \(p_{0,1}, p_{0,2}, p_{0,3}, p_{1,2}, p_{1,3}, p_{2,3}\).

    5. Construct the map from \(T\) to \(S'/J\) that sends \(p_{i,j}\) to the \(2 \times 2\) minor of the matrix

      \[\begin{split}\begin{bmatrix} p_0 & p_1 & p_2 & p_3 \\ q_0 & q_1 & q_2 & q_3 \end{bmatrix}\end{split}\]

      using columns \(i,j\).

    6. The kernel of this map is an ideal. What does it represent?

  4. Counting with multiplicity, how many lines lie on \(V(I)\)?

  5. Counting without muliplicities, how many lines are there?

  6. How many of these lines are real?

  7. Write down equations for one of these lines.

Plucker relations

  1. Compute all polynomial relations between \(2 \times 2\) minors of a generic \(2 \times 4\) matrix. Avoid manual labor, this should be done purely programmatically. hint: Create a map from a polynomial ring \(\mathbb{Q}[p_{0,1}, p_{0,2}, p_{0,3}, p_{0,3}, p_{1,2}, p_{1,3}, p_{2,3}]\) to a ring with 8 variables. You want the kernel of this map.

  2. Make the matrices bigger, i.e. find relations between \(n \times n\) minors of \(n \times m\) matrices, where \(n \leq m\). How far can you go before the computations take too long?

  3. The same output can be obtained using the command Grassmannian(n,m). Take a pair \((n,m)\) which didn’t terminate in the previous steps, and try it git Grassmannian. Why was this so much faster?

Lie Algebra Structures

Let \(e_1, e_2, e_3\) be a basis of \(\mathbb{C}^3\). A Lie algebra struture on \(\mathbb{C}^3\) is given by a bracket

\[[e_i, e_j] = a_{ij1}e_1 + a_{ij2}e_2 + a_{ij3} e_3\]

with the constraints

\[[e_i, e_j] = -[e_j, e_i]\]
\[[e_i, [e_j, e_k]] + [e_j, [e_k, e_i]] + [e_k, [e_i,e_j]] = 0\]

  1. Find all polynomial relations among the unknowns \(a_{ijk}\). Avoid manual labor, write a program that will generate them for you. Hint: look at \(a_{iik}\) first, then compare \(a_{ijk}\) to \(a_{jik}\).

  2. What is the dimension of this variety of Lie algebras?

  3. How many irreducible components does this have, and what are they?

  4. What about Lie algebras on \(\mathbb{C}^4\)? See also https://arxiv.org/abs/2208.14631

Coins, math, and computer science

We will be studying two approaches to solve an integer programming problem. The US dollar contains four common coins: pennies, nickels, dimes, and quarters. Their values in cents are 1,5,10, and 25 respectively.

  1. How many distinct ways are there to make \(n\) dollars using \(m\) coins?

    1. We start with the mathematical approach. Create a polynomial ring with variables \(p,n,d,q\), with the degree {1,1} for \(p\), {1,5} for \(n\), {1,10} for \(d\), and {1,25} for \(q\). (see viewHelp Degrees).

    2. Take the monomial \(pdq^3\). What is its degree? What do the numbers mean?

    3. How many ways are there to make 10 dollars using 100 coins? (hint viewHelp basis).

    4. How many unique values can be made using 5 coins?

    5. How many ways are there to make 2.5 dollars using any number of coins? (hint there is a one-line solution if you change your ring)

    6. A computer scientist would approach the above question recursively. Let’s order the denomination as follows: p,n,d,q. Let \(a_{i,j}\) be the number of ways to create \(j\) dollars using the first \(i\) denominations. E.g. \(a_{2,7}\) is the number of ways to create \(7\) dollars using pennies and nickels (the answer is 2: seven pennies, or one nickel + 2 pennies). Define the base cases \(a_{0,j}\) and \(a_{i,0}\), and find a recursion. Program this in Macaulay2.

    7. Which approach is faster? (viewHelp elapsedTime).

  2. What is the smallest number of coins needed to make \(n\) dollars?

  1. Adapt the previous, degree-based method to solve the question: what is the smallest number of coins needed to make 2.47 dollars?

  2. We will write another CS style solver. Let \(b_n\) be smallest number of coins needed to make \(n\) dollars. Set up initial conditions, and a recursion.

  3. Here is another approach: Set up a polynomial ring with variables \(x,y\) and \(p,d,n,q\). Define a monomial order that refines the order which first looks at the \(x,y\) degrees, and breaks ties using the \(p,d,n,q\) degrees (see viewHelp Weights). Define the ideal \(I = (xy - p, xy^5 - d, xy^{10} - n, xy^{25} - q)\). What does this ideal represent?

  4. We want to find the smallest \(k\) such that \(x^k y^{247}\) can be written in normal form without \(x\) or \(y\) variables. What does this normal form represent?

  5. Which method is faster?

Algebraic optimization, ED-degree

  1. The twisted cubic \(C\) is the image of the map \(\phi \colon x \mapsto (x,x^2,x^3)\). Find the ideal \(I_C\) corresponding to the image.

  2. What is its dimension and degree? Is it a complete intersection?

  3. The critical ideal of a variety \(C\) is

    \[\begin{split}\left( I_C + \left\langle c+1 \times c+1 \text{ minors of } \begin{pmatrix} u - x \\ J(I_C) \end{pmatrix} \right \rangle \right) \colon I_\text{sing}^\infty\end{split}\]

    where \(I_{\text{sing}}\) is the ideal corresponding to the singular locus, \(c\) is the codimension of \(C\), and \(J(I_C)\) is the Jacobian of the generators of \(I\). The singular locus is given by

    \[I_\text{sing} = I_C + \langle c \times c \text{ minors of } J(I_C) \rangle.\]

  4. Let \(u = (-7,4,1) \in \mathbb{C}^3\) be a point. The distance between \(C\) and \(u\) is the minimizer of the Euclidean distance \((x_1 + 7)^2 + (x_2 - 4)^2 + (x_3 - 1)^2\), where \(x \in C\). The set of critical points is the set of \(x \in C\) such that \(u-x \perp T_x(C)\), where \(T_x(C)\) is the tangent space of \(C\) at \(x\). This is the set of points corresponding to the critical ideal. Compute this ideal in this case. What is the closest point on \(C\) to \(u = (-7,4,1)\)?

  5. What is the dimension and degree? What happens to these when you change \(u\)? This degree is called the Euclidean distance degree.

  6. Consider the cardioid in \(\mathbb{R}^2\). It is the variety \(X\) corresponding to the equation \((x^2 + y^2 + x)^2 - x^2 - y^2\). What is its singular locus?

  7. Choose your favorite point \(u \in \mathbb{R}^2\), and compute the critical ideal. What is its degree?

  8. Compute the set of points \(u \in \mathbb{R}^2\) for which the degree of the critical ideal is not the expected one.

Algebraic optimization: Lagrange multipliers

Suppose \(V \in \mathbb{Q}^n\) is a variety given by \(I = \langle g_1,\dotsc,g_k \rangle \subseteq \mathbb{Q}[x_1,\dotsc,x_n]\). If \(f\) is a polynomial, we want the local extrema of \(f|_V \colon V \to Q\).

  1. If \(V\) is smooth, we can use Lagrange multipliers. Write a function that tests whether a variety is smooth.

  2. The Lagrange polynomial is

    \[F(x,\lambda) := f(x) + \sum_{i=1}^k \lambda_i g_i(x)\]

    Write a function that that computes this polynomial.

  3. If \(p \in V\) is a local extremum of \(f |_V\), then there exists \(\lambda^*\) such that the system \(\nabla_x F(x,\lambda) = \nabla_\lambda F(x,\lambda) = 0\). Write a function that creates and solves the system (the command diff might help).

  4. Compute the critical points of \(f(x,y) = x^2 + y^2\) under the condition \(g(x,y) = y-2x+1 = 0\).

  5. Check that the variety \(V = V(x^2 + y^2 + z^2 - 16, -x - 2y + z)\) is smooth, and compute the critical points of \(f(x,y,z) = 2x_4y-5z\) on the variety.

Ideals of Points and Hilbert functions

a. Write a Macaulay2 script (without using the command hilbertFunction) which takes a set of points in \(\mathbb{P}^2\) and a degreee \(i\), and computes the Hilbert function. Hint: determine the rank of the matrix obtained by evaluating the monomials of degree \(i\) at the points. To get the monomials of degree \(i\) in the ring R use the command basis(i,R). To evaluate at a point \((b_0:b_1:b_2)\) you might find the command map(R,R,{b0,b1,b2}) useful.

Modules, syzygies, free resolutions

  1. Let \(R = \mathbb{Q}[x,y,z]\). Find the set of all \((f_1,f_2,f_3,f_4) \in R^3\) such that

    \[x^2f_1 + xy f_2 + xz f_3 + y^2 f_4 = 0\]

    hint: you should get a module

  2. Let \(a_1,\dotsc,a_r\) be the generators of the above module. Find the set of \((f_1,\dotsc,f_r) \in R^r\) such that

    \[f_1 a_1 + f_2 a_2 + \dotsb + f_r a_r = 0\]

    Note that this set is again a module.

  3. Let \(b_1, \dotsc, b_s\) be the generators of the above module. Find the set \((f_1,\dotsc,f_s) \in R^r\) such that

    \[f_1 b_1 + f_2 b_2 + \dotsb + f_r b_s = 0\]

  4. By repeatedly solving, we have obtained a free resolution. Try the command res and see if you can replicate what we did here. The command res returns and instance of ChainComplex. The sequence of maps can be accessed by using the key dd, e.g. complex = res coker M; complex.dd.

  5. Compute a free resolution of the module coker matrix {{x^3, x*y, y^5}}.

  6. What does the command betti return when the input is the above resolution? Can you decipher the meaning of the numbers?

  7. Check that the command res in fact computes an exact complex by computting the homology of this complex e.d. HH(complex).

  8. Create a complex that has nontrivial homology. Check your result using HH.

Primary decomposition of modules

Suppose \(R\) is a polynomial ring, and fix

\[\begin{split}A = \begin{pmatrix} x^2 & y^2 & x z-y z+2 \\ x+y-z & x^2 y & y z \end{pmatrix}\end{split}\]

Let \(M\) be the \(R\)-submodule of \(R^2\) generated by the columns of the above matrix.

  1. Compute a primary decomposition of \(M\), i.e. write \(M = M_1 \cap \dotsb \cap M_k\), where each \(M_i\) is a primary \(R\)-submodule of \(R^2\). note when we say \(M_i\) is a primary submodule of \(R^2\), we mean \(R^2/M_i\) is primary. hint: Macaulay2 cannot directly compute primary decompositions of submodules, but one can start with a primary decomposition of the \(R\)-module \(R^2/M\).

  2. What are the associated primes?

  3. Check that the following varieties are equal

    1. The union of the varieties corresponding to associated primes

    2. The set of points where the rank of \(A\) drops.

    3. The annihilator of the comodule R^2/M.

Truth/liar riddle 1

There are three people: A, B, and C. They say the following

  1. B is lying

  2. C is not lying

  3. either A or B is not lying

Who is lying and who is telling the truth? Solve the riddle using Grobner bases. Hint Create a polynomial ring with 3 variables over the field \(\mathbb{Z}/2\mathbb{Z}\). Write the above three statements as three equations.

Truth/liar riddle 2

There are now four people: A, B, C, and D. They say the following

  1. B is telling the truth

  2. C or D are telling the truth

  3. D is lying

  4. There is only one liar

  1. How would one formulate a statement about the number of liars?

  2. Program a \(4 \times 5\) table, where each row corresponds to an elementary symmetric polynomial \(e_i\), each column is a number \(0 \leq j \leq 4\), and the entry \((i,j)\) is the value of \(e_i\) when there are \(j\) liars. You can use netList to make your table look nice in the terminal.

  3. Make a function taking a number \(n\) as an input, and returning the \(n \times (n+1)\) table as above.

  4. Formulate the four statements as a polynomial system, and solve it.

Truth/liar riddle 3

Suppose there are \(n\) people, with the following statements:

  • 1 says 2 is lying

  • 2 says 3 is lying

  • 3 says 4 is lying

  • etc..

  • n-1 says n is lying

  • n says: I am not lying

Solve the riddle for several values of n. How far can you go? Is there a pattern?

Try the following

  • 1 says that n is lying

  • 2 says that 1 is lying

  • 3 says that 1 and 2 are lying

  • 4 says that 1, 2, and 3 are lying

  • etc…

  • n-1 says that 1,2,3, …, n-2 are lying

Solve it for several n. How far can you go? What happens to the degree of the Grobner basis?

Graph colorings

We describe a graph on \(n\) nodes by a list of pairs \(\{i,j\}\), which indicate an edge between \(i\) and \(j\). We will assign three colors, -1, 1, and 1, to each node so that no neighboring nodes have the same color. Thus a coloring is a point \((x_1,\dotsc,x_n) \in \mathbb{F}_3^n\), such that \(x_i \neq x_j\) when \(\{i,j\}\) is an edge.

  1. Define a polynomial ring \(R = \mathbb{F}_3[x_1,\dotsc,x_n]\) over the finite field with 3 elements. Show that the set of all possible color assigments are described by the ideal \(I = (x_1^3 - x_1, \dotsc, x_n^3 - x_n)\).

  2. Prove that \(i,j\) have different colors if and only if \(x_i^2 + x_i x_j + x_j^2 - 1 = 0\).

  3. Write a Macaulay2 function that takes a list of edges, and returns the ideal corresponding to graph colorings.

  4. We get a symmetry by permuting the colors. How would you mitigate that?

  5. Compute all colorings (up to color permutations) of the graph {{1,2},{1,4},{1,5},{2,3},{2,4},{2,5},{2,6},{3,4},{3,5},{4,6},{4,7},{5,6},{5,7}}. Draw one of the colorings.

  6. Take the regular 7-gon, add a vertex in the middle, and connect the middle vertex to all other vertices. You should have 8 vertices and 14 edges. Show that this graph is not 3-colorable.

  7. Bonus turn the function into a methods, and allow instances of Graph as input (you will needsPackage "Graphs").

Types and packages

Multiset

A multiset is a set, where each element can occur more than once

  1. Implement the type Multiset (hint inherit from HashTable). One should be able to instantiate a multiset from a list, e.g. multiset {1,2,2,3} should return a new instance of Multiset.

  2. Make it print nicely (implement at least expression Multiset).

  3. Implement the comparison operators. For example A <= B if every element of A is in B.

  4. Implement #Multiset, which returns the number of elements in the multiset.

  5. Implement unique Multiset, which return a Set.

  6. Implement any number of other functions and method you deem necessary. For inspiration, check viewHelp Set.

  7. Create a package called Multiset containing all previously made methods and functions. Write a minimal documentation and a couple of tests. Make sure the package can be installed (installPackage), documentation works (viewHelp), and tests pass (check).

  8. Ideally, you can create a repository on GitHub, and collaborate and divide tasks among teammates. Make sensible commits with descriptive messages.

Hypergraphs

A hypergraph is a pair \(G = (V, E)\), where \(V\) is a finite set, and \(E\) is a set of disjoint subsets of \(V\).

../_images/Hypergraph-wikipedia.svg

  1. Define a type Hypergraph, along with useful basic functionality (e.g. expression Hypergraph, AfterPrint…).

  2. If we assign to every \(v_i \in V\) a variable \(x_i\), we can turn a hypergraph into a monomial ideal by setting

    \[I_G = \left( \prod_{v_i \in e} x_i \middle| e \in E \right)\]

    This is called the edge ideal. Write the Macaulay2 method edgeIdeal(Hypergraph).

  3. We say \(I = J + K\) is a Betti splitting if for all \(i,j \geq 0\),

    \[\beta_{i,j}(I) = \beta_{i,j}(J) + \beta_{i,j}(K) + \beta_{i-1,j}(J \cap K)\]

    where \(\beta_{i,j}\) is the \({i,j}\) Betti number. Check that

    \[J = (x_1x_2, x_5x_1) \qquad \text{ and } K = (x_2x_3, x_3x_4, x_4x_5)\]

    is a Betti splitting.

  4. Write the methods isBettiSplitting(Ideal,Ideal), isBettiSplitting(Hypergraph, Hypergraph). They should return either true or false.

  5. We say \(e \in E\) is a splitting edge if \(I_G = I_{G \setminus \{e\}} + I_{\{e\}}\) is a Betti splitting. Write a method splittingEdges(Hypergraph), which returns a list of all splitting edges.

  6. What are the splitting edges of the hypergraph in the image above?

Git and Github

Although everything can be done in a terminal, it is recommended to use a GUI for some of the more complex operations (e.g. 3-way merging). VScode has a nice built-in nice interface, which can be extended with the GitLens extension. It is also recommended to enable the “Git merge editor” setting in VScode settings. Another nice git interface is Sublime Merge.

Merge conflicts

By following the instructions below, we will be triggering several issues.

  1. Open a terminal, create a directory mkdir git_test, enter the directory cd git_test

  2. Initialize a git repository git init

  3. Create a file myFile, write a couple of lines, save

  4. Add and commit the newly created file git add myFile, git commit -m "Created my file!".

  5. Create and checkout a new branch git checkout -b newBranch

  6. Change the every line of the file, you can also add lines if you want. Save, add, commit

  7. Checkout the main branch git checkout main

  8. Note the changes and additions are gone. Well, not really, they’re just on the other branch.

  9. Now change the first line of the file.

  10. Merge newBranch into main: git merge newBranch.

You will now have a merge conflict. Read the message, and attempt to fix it. hint look at the state of myFile now. Where is the issue? Why couldn’t git figure it out on its own? Did it manage to figure something out?

Fix the merge conflict as you see fit, then git add myFile and finally git commit (or git merge --continue).

Pull requests, working with forks

This exercise needs to be done in a team.

  1. Have one team member create a GitHub repository, and add some content. We will call this the upstream repository.

  2. Other members should now fork the repository, and make a local clone.

  3. Everyone should now make additions and modifications on their own side.

  4. In order to include your changes in other peoples’ forks, you need to do a pull request on GitHub. One team member should now create a pull request from their fork to upstream.

  5. If there are no conflicts, GitHub will be able to merge. If there are conflicts, resolve them and merge.

  6. Changes are now reflected in GitHub, in the upstream repository. The owner of upstream can use git pull to update their local version.

  7. Changes in upstream are not reflected in any of the forks. Each team member should add a remote called “upstream”: git remote add upstream <url for the upstream repo>.

  8. Run git fetch upstream. What does this do?

  9. We can now incorporate changes from upstream to our branch. There are a couple of options.

    1. git merge upstream/main: will (usually) create a merge commit. If there are conflicts, you will be asked to resolve them.

    2. git merge --ff-only upstream/main: will create a fast-forward merge. This will not work if there are merge conflicts. Use this if your fork has no additions compared to upstream.

    3. git rebase upstream/main: you can also try this one out. Note that this rewrites history, so only use it if you know what you are doing. This is used in many projects to keep history linear.

Pulling, pushing, stashing

Now we will have several people working on the same repository

  1. Have one person add other people as collaborators in their GitHub repository. In Github, go to Settings -> Collaborators.

  2. Have all collaborators clone the repository.

  3. Now everyone has the same version. Have one person make a change, commit, and push.

  4. Everyone else is now behind. Everyone can now get up to date using git pull.

  5. Have two people make conflicting changes, which we will refer to as A and B. Commit both A and B, but push A first. When B tries to push, you will be asked to pull first.

  6. Since the changes are conflicting, pulling will fail. There are a few options here

    1. git pull --merge will create a merge commit. This makes commits A and B happen in parallel, with an additional merge commit to fix the conflict.

    2. git pull --rebase will rebase B on A. This makes commit B happen after commit A. Since there is a conflict, we will have to amend commit B.

  7. Have a third person make a change C, but don’t commit. git pull will now fail, because there are uncommited changes. git stash will save all uncommited changes to a “stash”, and return the repository to the state of the latest commit.

  8. Once the changes are stashed, we can git pull without any issues. git stash pop will now apply the previously statshed uncommited changes ontop of the latest commit. If there are conflicts, you will have to resolve them.

Discarding work

What are the differences between git reset, git reset --hard, git reset --soft? What about git revert? Try it out

  1. Checkout a new branch called discarding, and make a bunch of commits (3 or 4 should suffice).

  2. Use git log to see your commits. Copy one of the commit hashes, and run git revert <hash>. Check git log.

  3. Pick an old commit hash, and try git reset --soft <old commit>, or git reset <old commit> (the only difference is that git reset does not stage files for commit). Try git log now. What happened? Did we lose any code?

  4. We decided this was a bad idea. Let’s undo this. The command git reflog shows all past operations, along with a hash. We can go back to the previous state by using git reset --hard HEAD@{1}. Now hopefully git log is back to normal.

  5. Take the same <old commit> as above, and do a git reset --hard <old commit>. Try git log. Did we lose anything?

Rewriting history means trouble (unless…)

We will be simulating an unfortunate rewrite of history. This also must be done in a team.

  1. Choose one repository as “upstream”, and let other be forks.

  2. Create a new branch called bad_branch in upstream, and commit a 3-4 incremental changes, push (e.g. add a file, commit, add a line, commit, add another line, commit, etc…)

  3. In the forks, create new branches based on bad_branch. Do this by adding a remote git remote add upstream <url here>, fetching git fetch upstream, and creating a branch git checkout -b <name here> upstream/bad_branch.

  4. In the forks, make an addition/change, commit and push git push origin.

  5. In the upstream fork, we will rewrite history. The easiest way is to change the most recent commit. Make a change to the file, git add <file> and then git commit --amend.

  6. (bonus) Change older commits. This is a little bit complicated, and conflicts will emerge. Using a GUI should make it easier, but we decribe the procedure for the terminal. Use git log to find the commit hash that you want to change, and then git rebase -i <commit hash>. Read the file that gets output, and change one of the pick to edit. If there are conflicts, solve them and git rebase --continue.

  7. In the upstream fork, push the changes to remote. git push will fail (why?), but you can git push --force.

  8. Try to make a pull request from one of the forks to upstream. This should fail catastrophically.

  9. A possible fix wold be to rebase the forks to the new upstream. Try it out and see if you can fix it (git rebase -i <commit hash>).