Algorithms for 4 dimensional Licci Gorenstein Stanley-Reisner ideal

In the paper G. Rinaldo, N.Terai, 4-dimensional Licci Gorenstein Stanley-Reisner ideals, we classified licci Gorenstein squarefree monomial ideals \(I\) with dim \(S/I \leq 4\) where \(S=K[x_1,\ldots,x_n]\) is a polynomial ring on a field \(K\).

To reach this result we used the following facts (1. and 2.), classification and database (3.):

If \(I\) is licci of dimension 4 then \(n\leq 9\) (see Corollary 1.3);
If \(S/I\) is Gorenstein and licci implies \(S/I^2\) is Cohen-Macaulay (see Theorem 1.4).
The classification of Frank H. Lutz in the paper F. H .Lutz Combinatorial 3-manifolds with 10 vertices, Beitr. Algebra. Geom. 49(2008), 97-106, whose database is here.

We refer to the article for an in-depth description of the notation and results. In this page you will find a description of the algorithm and an implementation with obtained results.

Description of the algorithm

Unfortunately the database provided by Frank H. Lutz is quite big, i.e. in the cases \(n\in\{8,9\}\) there are respectively 39 and 1296 \(S^3\) triangulations to check. Hence we needed an effective and efficient algorithm to filter the database using a condition induced by 2. In particular, we recall that:

\(S/I^2\) is Cohen-Macaulay if and only if \(S/I^{(2)}\) is Cohen-Macaulay and \(I^2=I^{(2)}\) (well known);
If \(S/I^{(2)}\) is Cohen-Macaulay then \(S/I^{(2)}\) satisfies \(S_2\) condition (well known);
\(S/I^{(2)}\) satisfies \(S_2\) condition if and only if diam\((link_\Delta F))\leq 2\) for any \(F \in \Delta\) with dim \(link_\Delta F\geq 1\) (see Theorem 1.6).

Hence we decided to filter the database by the following conditions:

\(I^2=I^{(2)}\);
diam\((link_\Delta F))\leq 2\) for any \(F \in \Delta\) with dim \(link_\Delta F\geq 1\).

The first condition can be computed by any computer algebra system like CoCoA (we decided to use it). In fact given the primary decomposition of \(I\), it is possible to compute the symbolic power \(I^{(2)}\) and compare it with \(I^2\) (see Section 1). These operations are already implemented in CoCoA.

The last condition is purely combinatorial and can be tested by an effective and quite efficient algorithm. We describe it in detail.

We recall that diameter, diam(), is computed on the skeleton of dimension 1 of a certain simplicial complex \(\Delta\), roughly speaking on the graph whose edges are the facets of the subcomplex of dimension 1, namely \(G=skel_1(\Delta)\). As an example in the images you see \(\Delta\) that is given by the boundary of the octahedron, and its 1-skeleton.

Octahedron Octahedral skeleton

The diameter is the maximal distance between all the vertices of G, namely \(V(G)=\{1,\ldots,n\}\). Since we want diam\((G)\leq 2\) it is sufficient that in two steps it is possible to reach any vertex by any other vertex. Let \(L=\{L_1,\ldots,L_n\}\) be the adiacency set of \(G\) on the vertices \(V(G)\). That is \(L_i\) is the set of vertices adjacent to the vertex \(i\), for \(i\in\{1,\ldots,n\}\).

Let \(d(v,w)\) be the distance between two vertices of \(G\). Focus on the vertex 1, we want to test \(d(1,v)\leq 2\) for all \(v\in \{2,\ldots,n\}\). It is sufficient to consider the union

\[U= L_1 \cup_{i\in L_1} L_i \]

If \(U=\{1,\ldots,n\}\) then \(d(1,v)\leq 2\), otherwise there exists a v such that \(d(1,v)>2\).

Hence if \(d(1,v)\leq 2\) we can continue with \(d(2,v)\) and so on, otherwise we stop returning that diameter is greater than 2. If the algorithm terminates without interruption than the diameter is \(\leq 2\).

As an example if we focus on a vertex of the graph induced by octahedron, namely 1, we see that \(L_1\) is a set of 4 vertices, namely, 2,3,4,5, and \(L_2=L_3=L_4=L_5=\{1,6\}\). Hence \(U=\{1,\ldots,6\}\). The same happens for all the vertices of \(\Delta\) that is its diameter is 2. Now, focus on a vertex of \(\Delta\), namely 1. Its link is given by the cycle C of length 4, whose vertices are, 2,3,4 and 5. Applying the same algorithm to the graph C we easily obtain that its diameter is 2. Hence the octahedron satisfies the \(S_2\) condition (see also Proposition 2.3(4)).

We observe that if we focus on a n-gonal bypiramid with \(n\geq 6\) the algorithm gives a negative answer. In fact even if \(diam(\Delta)\) is 2 again, if we consider the link of one of the apex we obtain a n-gon that has diameter \(n/2\).

Implementation of the algorithm and results

In this section we give the results of our computation by the routines that we implemented in c++ (using g++ of gcc ver. 4.8) and CoCoA 4.7 whose sources are downloadable from here. Moreover in the same archive you will find the files: v8.txt and v9.txt. These files are taken from the database of Frank H. Lutz: They are the 3-folds respectively with 8 and 9 vertices.

The program in c++ has been developed under Linux on Ubuntu distribution (tested on versions 14.04 and 18.04). It uses only standard library and with some effort can work on any platforms. To use it you have to download, and extract by

tar -xzvf LicciGorenstein.tgz

move to the folder

cd LicciGorenstein

and then compile the c++ program by

make

Now we are ready to make the filtrations used in the proofs of Lemma 4.2 and Lemma 4.4. We show the input and the output in the console. We can filter by the \(S_2\) condition, thanks to the algorithm explained in the previous section, by the following 2 commands. These take as input the files v8.txt and v9.txt and generate the files v8d2.txt and v9d2.txt.

 
./diameterTwo 8 3 < v8.txt > v8d2.txt 
./diameterTwo 9 3 < v9.txt > v9d2.txt

The output file v8d2.txt contains a list of 7 triangulations of \(S^3\):

 L:=[
[[1,2,3,4],[1,2,3,5],[1,2,4,6],[1,2,5,7],[1,2,6,7],[1,3,4,5],[1,4,5,8],[1,4,6,8],[1,5,7,8],[1,6,7,8],[2,3,4,5],[2,4,5,6],[2,5,6,7],[4,5,6,8],[5,6,7,8]],
[[1,2,3,4],[1,2,3,5],[1,2,4,6],[1,2,5,7],[1,2,6,7],[1,3,4,5],[1,4,5,8],[1,4,6,8],[1,5,7,8],[1,6,7,8],[2,3,4,6],[2,3,5,6],[2,5,6,7],[3,4,5,6],[4,5,6,8],[5,6,7,8]],
[[1,2,3,4],[1,2,3,5],[1,2,4,6],[1,2,5,7],[1,2,6,7],[1,3,4,5],[1,4,5,8],[1,4,6,8],[1,5,7,8],[1,6,7,8],[2,3,4,6],[2,3,5,6],[2,5,6,7],[3,4,5,8],[3,4,6,8],[3,5,6,8],[5,6,7,8]],
[[1,2,3,4],[1,2,3,5],[1,2,4,6],[1,2,5,7],[1,2,6,7],[1,3,4,5],[1,4,5,8],[1,4,6,8],[1,5,7,8],[1,6,7,8],[2,3,4,6],[2,3,5,7],[2,3,6,7],[3,4,5,8],[3,4,6,8],[3,5,7,8],[3,6,7,8]],
[[1,2,3,4],[1,2,3,5],[1,2,4,6],[1,2,5,7],[1,2,6,7],[1,3,4,8],[1,3,5,8],[1,4,6,8],[1,5,7,8],[1,6,7,8],[2,3,4,5],[2,4,5,6],[2,5,6,7],[3,4,5,8],[4,5,6,8],[5,6,7,8]],
[[1,2,3,4],[1,2,3,5],[1,2,4,6],[1,2,5,7],[1,2,6,7],[1,3,4,8],[1,3,5,8],[1,4,6,8],[1,5,7,8],[1,6,7,8],[2,3,4,8],[2,3,5,8],[2,4,6,8],[2,5,7,8],[2,6,7,8]],
[[1,2,3,4],[1,2,3,5],[1,2,4,6],[1,2,5,6],[1,3,4,7],[1,3,5,7],[1,4,6,7],[1,5,6,7],[2,3,4,8],[2,3,5,8],[2,4,6,8],[2,5,6,8],[3,4,7,8],[3,5,7,8],[4,6,7,8],[5,6,7,8]]
];

The output file v9d2.txt contains a list of 11 triangulations of \(S^3\).

 
L:=[
[[1,2,3,4],[1,2,3,5],[1,2,4,6],[1,2,5,7],[1,2,6,7],[1,3,4,8],[1,3,5,8],[1,4,6,8],[1,5,7,9],[1,5,8,9],[1,6,7,9],[1,6,8,9],[2,3,4,5],[2,4,5,6],[2,5,6,7],[3,4,5,8],[4,5,6,8],[5,6,7,9],[5,6,8,9]],
[[1,2,3,4],[1,2,3,5],[1,2,4,6],[1,2,5,7],[1,2,6,7],[1,3,4,8],[1,3,5,8],[1,4,6,8],[1,5,7,9],[1,5,8,9],[1,6,7,9],[1,6,8,9],[2,3,4,5],[2,4,5,6],[2,5,6,7],[3,4,5,8],[4,5,6,9],[4,5,8,9],[4,6,8,9],[5,6,7,9]],
[[1,2,3,4],[1,2,3,5],[1,2,4,6],[1,2,5,7],[1,2,6,7],[1,3,4,8],[1,3,5,8],[1,4,6,8],[1,5,7,9],[1,5,8,9],[1,6,7,9],[1,6,8,9],[2,3,4,5],[2,4,5,7],[2,4,6,7],[3,4,5,8],[4,5,7,8],[4,6,7,8],[5,7,8,9],[6,7,8,9]],
[[1,2,3,4],[1,2,3,5],[1,2,4,6],[1,2,5,7],[1,2,6,7],[1,3,4,8],[1,3,5,8],[1,4,6,8],[1,5,7,9],[1,5,8,9],[1,6,7,9],[1,6,8,9],[2,3,4,5],[2,4,5,7],[2,4,6,7],[3,4,5,8],[4,5,7,9],[4,5,8,9],[4,6,7,9],[4,6,8,9]],
[[1,2,3,4],[1,2,3,5],[1,2,4,6],[1,2,5,7],[1,2,6,7],[1,3,4,8],[1,3,5,8],[1,4,6,8],[1,5,7,9],[1,5,8,9],[1,6,7,9],[1,6,8,9],[2,3,4,5],[2,4,5,7],[2,4,6,7],[3,4,5,9],[3,4,8,9],[3,5,8,9],[4,5,7,9],[4,6,7,9],[4,6,8,9]],
[[1,2,3,4],[1,2,3,5],[1,2,4,6],[1,2,5,7],[1,2,6,7],[1,3,4,8],[1,3,5,8],[1,4,6,8],[1,5,7,9],[1,5,8,9],[1,6,7,9],[1,6,8,9],[2,3,4,7],[2,3,5,7],[2,4,6,7],[3,4,7,9],[3,4,8,9],[3,5,7,9],[3,5,8,9],[4,6,7,9],[4,6,8,9]],
[[1,2,3,4],[1,2,3,5],[1,2,4,6],[1,2,5,7],[1,2,6,7],[1,3,4,8],[1,3,5,8],[1,4,6,8],[1,5,7,9],[1,5,8,9],[1,6,7,9],[1,6,8,9],[2,3,4,8],[2,3,5,8],[2,4,6,8],[2,5,6,7],[2,5,6,8],[5,6,7,9],[5,6,8,9]],
[[1,2,3,4],[1,2,3,5],[1,2,4,6],[1,2,5,7],[1,2,6,7],[1,3,4,5],[1,4,5,8],[1,4,6,8],[1,5,7,8],[1,6,7,8],[2,3,4,5],[2,4,5,9],[2,4,6,9],[2,5,7,9],[2,6,7,9],[4,5,8,9],[4,6,8,9],[5,7,8,9],[6,7,8,9]],
[[1,2,3,4],[1,2,3,5],[1,2,4,6],[1,2,5,7],[1,2,6,7],[1,3,4,5],[1,4,5,8],[1,4,6,8],[1,5,7,8],[1,6,7,8],[2,3,4,6],[2,3,5,7],[2,3,6,7],[3,4,5,9],[3,4,6,9],[3,5,7,9],[3,6,7,9],[4,5,8,9],[4,6,8,9],[5,7,8,9],[6,7,8,9]],
[[1,2,3,4],[1,2,3,5],[1,2,4,6],[1,2,5,7],[1,2,6,7],[1,3,4,5],[1,4,5,8],[1,4,6,8],[1,5,7,8],[1,6,7,8],[2,3,4,9],[2,3,5,9],[2,4,6,9],[2,5,7,9],[2,6,7,9],[3,4,5,9],[4,5,8,9],[4,6,8,9],[5,7,8,9],[6,7,8,9]],
[[1,2,3,4],[1,2,3,5],[1,2,4,6],[1,2,5,7],[1,2,6,7],[1,3,4,8],[1,3,5,8],[1,4,6,8],[1,5,7,8],[1,6,7,8],[2,3,4,9],[2,3,5,9],[2,4,6,9],[2,5,7,9],[2,6,7,9],[3,4,8,9],[3,5,8,9],[4,6,8,9],[5,7,8,9],[6,7,8,9]]
];

Now the two files are ready to be filtered by the condition \(I^2=I^{(2)}\) developed in CoCoA.

 
cocoa I2Equality8.coc 
cocoa I2Equality9.coc

The first one gives the following output (see Lemma 3.2):


Ideal(x[3]x[8], x[3]x[7], x[3]x[6], x[2]x[8], x[4]x[7], x[1]x[5]x[6], x[1]x[2]x[4]x[5]) --> S/I^2 CM
Ideal(x[2]x[8], x[4]x[7], x[3]x[7], x[3]x[8], x[1]x[5]x[6], x[2]x[4]x[5], x[1]x[3]x[6]) --> S/I^2 CM
Ideal(x[2]x[8], x[4]x[7], x[3]x[7], x[1]x[5]x[6], x[2]x[4]x[5], x[4]x[5]x[6], x[1]x[3]x[6], x[1]x[3]x[8]) --> S/I^2 CM
Ideal(x[2]x[8], x[4]x[7], x[5]x[6], x[2]x[4]x[5], x[1]x[3]x[6], x[1]x[3]x[7], x[1]x[3]x[8]) --> S/I^2 CM
Ideal(x[2]x[8], x[4]x[7], x[3]x[6], x[3]x[7], x[1]x[5]x[6], x[1]x[4]x[5]) --> S/I^2 CM
Ideal(x[4]x[7], x[4]x[5], x[5]x[6], x[3]x[6], x[3]x[7], x[1]x[2]x[8]) --> S/I^2 CM
Ideal(x[4]x[5], x[3]x[6], x[2]x[7], x[1]x[8]) --> S/I^2 CM

The second one gives the following output (see Lemma 3.4):

 
Ideal(x[2]x[9], x[2]x[8], x[4]x[9], x[4]x[7], x[7]x[8], x[3]x[6], x[3]x[7], x[3]x[9], x[1]x[5]x[6], x[1]x[4]x[5]) --> S/I^2 CM
Ideal(x[2]x[9], x[2]x[8], x[7]x[8], x[4]x[7], x[3]x[6], x[3]x[7], x[3]x[9], x[5]x[6]x[8], x[1]x[5]x[6], x[1]x[4]x[5], x[1]x[4]x[9]) --> S/I^2 CM
Ideal(x[2]x[9], x[2]x[8], x[5]x[6], x[4]x[9], x[3]x[6], x[3]x[7], x[3]x[9], x[1]x[7]x[8], x[1]x[4]x[5], x[1]x[4]x[7]) --> S/I^2 CM
Ideal(x[2]x[9], x[2]x[8], x[7]x[8], x[5]x[6], x[3]x[6], x[3]x[7], x[3]x[9], x[1]x[4]x[5], x[1]x[4]x[7], x[1]x[4]x[9]) --> S/I^2 CM
Ideal(x[2]x[9], x[2]x[8], x[5]x[6], x[7]x[8], x[3]x[6], x[3]x[7], x[1]x[3]x[9], x[4]x[5]x[8], x[1]x[4]x[5], x[1]x[4]x[7], x[1]x[4]x[9]) --> S/I^2 CM
Ideal(x[2]x[9], x[2]x[8], x[5]x[6], x[3]x[6], x[4]x[5], x[7]x[8], x[1]x[3]x[9], x[1]x[3]x[7], x[1]x[4]x[7], x[1]x[4]x[9]) --> S/I^2 CM
Ideal(x[4]x[9], x[4]x[7], x[4]x[5], x[2]x[9], x[7]x[8], x[3]x[6], x[3]x[7], x[3]x[9], x[1]x[2]x[8], x[1]x[5]x[6]) --> S/I^2 CM
Ideal(x[3]x[9], x[3]x[8], x[3]x[7], x[3]x[6], x[2]x[8], x[4]x[7], x[5]x[6], x[1]x[9], x[1]x[2]x[4]x[5]) --> S/I^2 CM
Ideal(x[2]x[9], x[2]x[8], x[3]x[8], x[4]x[7], x[5]x[6], x[1]x[9], x[2]x[4]x[5], x[1]x[3]x[6], x[1]x[3]x[7]) --> S/I^2 CM
Ideal(x[2]x[8], x[5]x[6], x[4]x[7], x[3]x[6], x[3]x[7], x[3]x[8], x[1]x[9], x[2]x[4]x[5]) --> S/I^2 CM
Ideal(x[2]x[8], x[3]x[7], x[3]x[6], x[5]x[6], x[4]x[5], x[4]x[7], x[1]x[9]) --> S/I^2 CM

We observe that in both cases the condition \(I^2=I^{(2)}\) has been verified for all the \(S^3\) triangulations satisfying the \(S_2\) condition. Moreover the same programs check if the rings \(S/I^2\) are Cohen-Macaulay by the internal command of CoCoA

 
Depth(S/I^2);

and the depth is equal to 4 for all the rings in the two sets.