text:
# Problems and algorithms for affine semigroups

## 1. Introduction

Affine semigroups – discrete analogues of convex polyhedral cones – mark the cross-roads of algebraic geometry, commutative algebra and integer programming. They constitute the combinatorial background for the theory of toric varieties, which is their main link to algebraic geometry. Initiated by the work of Demazure \[De\] and Kempf, Knudsen, Mumford and Saint-Donat \[KKMS\] in the early 70s, toric geometry is still a very active area of research.

However, the last decade has clearly witnessed the extensive study of affine semigroups from the other two perspectives. No doubt, this is due to the tremendously increased computational power in algebraic geometry, implemented through the theory of Gröbner bases, and, of course, to modern computers.

In this article we overview those aspects of this development that have been relevant for our own research, and pose several open problems. Answers to these problems would contribute substantially to the theory.

The paper treats two main topics: (1) affine semigroups and several covering properties for them and (2) algebraic properties for the corresponding rings (Koszul, Cohen-Macaulay, different “sizes” of the defining binomial ideals). We emphasize the special case when the initial data are encoded into lattice polytopes. The related objects – polytopal semigroups and algebras – provide a link with the classical theme of triangulations into unimodular simplices.

We have also included an algorithm for checking the semigroup covering property in the most general setting (Section 4). Our counterexample to certain covering conjectures (Section 3) was found by the application of a small part of this algorithm. The general algorithm could be used for a deeper study of affine semigroups.

This paper is an expanded version of the talks given by the first and the third author in the Problem session of the Colloquium on Semigroups held in Szeged in July 2000.

## 2. Affine and polytopal semigroups and their algebras

We use the following notation: $``$, $``$, $``$ are the additive groups of integral, rational, and real numbers, respectively; $`_+`$, $`_+`$ and $`_+`$ denote the corresponding additive subsemigroups of non-negative numbers, and $`=\{1,2,\mathrm{}\}`$.

### 2.1. Affine semigroups

An *affine semigroup* is a semigroup (always containing a neutral element) which is finitely generated and can be embedded in $`^n`$ for some $`n`$. Groups isomorphic to $`^n`$ are called *lattices* in the following.

We write $`\mathrm{gp}(S)`$ for the group of differences of $`S`$, i. e. $`\mathrm{gp}(S)`$ is the smallest group (up to isomorphism) which contains $`S`$.

If $`S`$ is contained in the lattice $`L`$ as a subsemigroup, then $`xL`$ is *integral* over $`S`$ if $`cxS`$ for some $`c`$, and the set of all such $`x`$ is the *integral closure* $`\overline{S}_L`$ of $`S`$ in $`L`$. Obviously $`\overline{S}_L`$ is again a semigroup. As we shall see in Proposition 2.1.1, it is even an affine semigroup, and can be described in geometric terms.

By a *cone* in a real vector space $`V=^n`$ we mean a subset $`C`$ such that $`C`$ is closed under linear combinations with non-negative real coefficients. A cone is finitely generated if and only if it is the intersection of finitely many vector halfspaces. (Sometimes a set of the form $`z+C`$ will also be called a cone.) If $`C`$ is generated by vectors with rational or, equivalently, integral components, then $`C`$ is called *rational*. This is the case if and only if the halfspaces can be described by homogeneous linear inequalities with rational (or integral) coefficients.

This applies especially to the cone $`C(S)`$ generated by $`S`$ in the real vector space $`L`$:

($``$)
$$C(S)=\{xL:\sigma _i(x)0,i=1,\mathrm{},s\}$$

where the $`\sigma _i`$ are linear forms on $`L`$ with integral coefficients.

###### Proposition 2.1.1.

* *(Gordan’s lemma)* Let $`CL`$ be a finitely generated rational cone (i. e. generated by finitely many vectors from $`L`$). Then $`LC`$ is an affine semigroup and integrally closed in $`L`$.
* Let $`S`$ be an affine subsemigroup of the lattice $`L`$. Then

+ $`\overline{S}_L=LC(S)`$;
    + there exist $`z_1,\mathrm{},z_u\overline{S}_L`$ such that $`\overline{S}_L=_{i=1}^uz_i+S`$;
    + $`\overline{S}_L`$ is an affine semigroup.

###### Proof.

* Note that $`C`$ is generated by finitely many elements $`x_1,\mathrm{},x_mL`$. Let $`xLC`$. Then $`x=a_1x_1+\mathrm{}+a_mx_m`$ with non-negative rational $`a_i`$. Set $`b_i=a_i`$. Then

($``$)
$$x=(b_1x_1+\mathrm{}+b_mx_m)+(r_1x_1+\mathrm{}+r_mx_m),0r_i<1.$$

The second summand lies in the intersection of $`L`$ with a bounded subset of $`C`$. Thus there are only finitely many choices for it. These elements together with $`x_1,\mathrm{},x_m`$ generate $`LC`$. That $`LC`$ is integrally closed in $`L`$ is evident.
* Set $`C=C(S)`$, and choose a system $`x_1,\mathrm{},x_m`$ of generators of $`S`$. Then every $`xLC`$ has a representation $`()`$. Multiplication by a common denominator of $`r_1,\mathrm{},r_m`$ shows that $`x\overline{S}_L`$. On the other hand, $`LC`$ is integrally closed by (a) so that $`\overline{S}_L=LC`$.

The elements $`y_1,\mathrm{},y_u`$ can now be chosen as the vectors $`r_1x_1+\mathrm{}+r_mx_m`$ appearing in $`()`$. Their number is finite since they are all integral and contained in a bounded subset of $`L`$. Together with $`x_1,\mathrm{},x_m`$ they certainly generate $`\overline{S}_L`$ as a semigroup.

Proposition 2.1.1 shows that normal affine semigroups can also be defined by finitely generated rational cones $`C`$: the semigroup $`S(C)=LC`$ is affine and integrally closed in $`L`$.

We introduce special terminology in the case in which $`L=\mathrm{gp}(S)`$. Then the integral closure $`\overline{S}=\overline{S}_{\mathrm{gp}(S)}`$ is called the *normalization*, and $`S`$ is *normal* if $`S=\overline{S}`$. Clearly the semigroups $`S(C)`$ are normal, and conversely, every normal affine semigroup $`S`$ has such a representation, since $`S=S(C(S))`$ (in $`\mathrm{gp}(S)`$).

Suppose that $`L=\mathrm{gp}(S)`$ and that representation $`()`$ of $`C(S)`$ is irredundant. Then the linear forms $`\sigma _i`$ describe exactly the support hyperplanes of $`C(S)`$, and are therefore uniquely determined up to a multiple by a non-negative factor. We can choose them to have coprime integral coefficients, and then the $`\sigma _i`$ are uniquely determined. We call them the *support forms* of $`S`$, and write

$$\mathrm{supp}(S)=\{\sigma _1,\mathrm{},\sigma _s\}.$$

We call a semigroup $`S`$ *positive* if $`0`$ is the only invertible element in $`S`$. It is easily seen that $`\overline{S}`$ is positive as well and that positivity is equivalent to the fact that $`C(S)`$ is a pointed cone with apex $`0`$. It is easily seen that the map $`\sigma :S_+^s`$, $`\sigma (x)=(\sigma _1(x),\mathrm{},\sigma _s(x))`$, is an embedding if $`S`$ positive. It follows that every element of $`S`$ can be written as the sum of uniquely determined irreducible elements. Since $`S`$ is finitely generated, the set of irreducible elements is also finite. It constitutes the *Hilbert basis* $`\mathrm{Hilb}(S)`$ of $`S`$; clearly $`\mathrm{Hilb}(S)`$ is the uniquely determined minimal system of generators of $`S`$. For a finitely generated positive rational cone $`C`$ we set $`\mathrm{Hilb}(C)=\mathrm{Hilb}(S(C))`$.

Especially for normal $`S`$ the assumption that $`S`$ is positive is not a severe restriction. It is easily seen that one has a splitting

$$S=S_0S^{}$$

into the maximal subgroup $`S_0`$ of $`S`$ and a positive normal affine semigroup $`S^{}`$, namely the image of $`S`$ in $`\mathrm{gp}(S)/S_0`$.

### 2.2. Semigroup algebras

Now let $`K`$ be a field. Then we can form the *semigroup algebra* $`K[S]`$. Since $`S`$ is finitely generated as a semigroup, $`K[S]`$ is finitely generated as a $`K`$-algebra. When an embedding $`S^n`$ is given, it induces an embedding $`K[S]K[^n]`$, and upon the choice of a basis in $`^n`$, the algebra $`K[^n]`$ can be identified with the Laurent polynomial ring $`K[T_1^{\pm 1},\mathrm{},T_n^{\pm 1}]`$. Under this identification, $`K[S]`$ has the monomial basis $`T^a`$, $`aS^n`$ (where we use the notation $`T^a=T_1^{a_1}\mathrm{}T_n^{a_n}`$).

If we identify $`S`$ with the semigroup $`K`$-basis of $`K[S]`$, then there is a conflict of notation: addition in the semigroup turns into multiplication in the ring. The only way out would be to avoid this identification and always use the exponential notation as in the previous paragraph. However, this is often cumbersome. We can only ask the reader to always pay attention to the context.

It is now clear that affine semigroup algebras are nothing but subalgebras of $`K[T_1^{\pm 1},\mathrm{},T_n^{\pm 1}]`$ generated by finitely many monomials. Nevertheless the abstract point of view has many advantages. When we consider the elements of $`S`$ as members of $`K[S]`$, we will usually call them *monomials*. Products $`as`$ with $`aK`$ and $`sS`$ are called *terms*.

The Krull dimension of $`K[S]`$ is given by $`\mathrm{rank}S=\mathrm{rank}\mathrm{gp}(S)`$, since $`\mathrm{rank}S`$ is obviously the transcendence degree of $`\mathrm{QF}(K[S])=\mathrm{QF}\left(K[\mathrm{gp}(S)]\right)`$ over $`K`$.

If $`S`$ is positive, then $`\mathrm{Hilb}(S)`$ is a minimal set of generators for $`K[S]`$.

It is not difficult to check, and the reader should note that the usage of the terms “integral over”, “integral closure”, “normal” and “normalization” is consistent with its use in commutative algebra. So $`K[\overline{S}_L]`$ is the integral closure of $`K[S]`$ in the quotient field $`\mathrm{QF}(K[L])`$ of $`K[L]`$ etc.

### 2.3. Polytopal semigroup algebras

Let $`M`$ be a subset of $`^n`$. We set

$`L_M`$ $`=M^n,`$
$`E_M`$ $`=\{(x,1):xL_M\}^{n+1};`$
so $`L_M`$ is the set of lattice points in $`M`$, and $`E_M`$ is the image of $`L_M`$ under the embedding $`^n^{n+1}`$, $`x(x,1)`$. Very frequently we will consider $`^n`$ as a hyperplane of $`^{n+1}`$ under this embedding; then we may identify $`L_M`$ and $`E_M`$. By $`S_M`$ we denote the subsemigroup of $`^{n+1}`$ generated by $`E_M`$.

Now suppose that $`P`$ is a (finite convex) lattice polytope in $`^n`$, where ‘lattice’ means that all the vertices of $`P`$ belong to the integral lattice $`^n`$. The affine semigroups of the type $`S_P`$ will be called *polytopal semigroups*. A lattice polytope $`P`$ is *normal* if $`S_P`$ is a normal semigroup.

Let $`K`$ be a field. Then

$$K[P]=K[S_P]$$

is called a *polytopal semigroup algebra* or simply a *polytopal algebra*. Since $`\mathrm{rank}S_P=dimP+1`$ and $`dimK[P]=\mathrm{rank}S_P`$ as remarked above, we have

$$dimK[P]=dimP+1.$$

Note that $`S_P`$ (or, more generally, $`S_M`$) is a graded semigroup, i. e. $`S_P=_{i=0}^{\mathrm{}}(S_P)_i`$ such that $`(S_P)_i+(S_P)_j(S_P)_{i+j}`$; its $`i`$-th graded component $`(S_P)_i`$ consists of all the elements $`(x,i)S_P`$. Moreover, $`S_P`$ is even *homogeneous*, namely generated by its elements of degree $`1`$.

Therefore $`R=K[P]`$ is a graded $`K`$-algebra in a natural way and generated by its degree $`1`$ elements. Its $`i`$-th graded component $`R_i`$ is the $`K`$-vector space generated by $`(S_P)_i`$. The elements of $`E_P=(S_P)_1`$ have degree $`1`$, and therefore $`R`$ is a homogeneous $`K`$-algebra in the terminology of Bruns and Herzog \[BH\]. The defining relations of $`K[P]`$ are the binomials representing the affine dependencies of the lattice points of $`P`$. (In Section 5 we will discuss the properties of the ideal generated by the defining binomials.) Some easy examples:

###### Examples 2.3.1.

* $`P=\mathrm{conv}(1,4)^1`$. Then $`P`$ contains the lattice points $`1,2,3,4`$, and the relations of the corresponding generators of $`K[P]`$ are given by

$$X_1X_3=X_2^2,X_1X_4=X_2X_3,X_2X_4=X_3^2.$$
* $`P=\mathrm{conv}((0,0),(0,1),(1,0),(1,1))`$. The lattice points of $`P`$ are exactly the 4 vertices, and the defining relation of $`K[P]`$ is $`X_1X_4=X_2X_3`$.
* $`P=\mathrm{conv}((1,0),(0,1),(1,1))`$. There is a fourth lattice point in $`P`$, namely $`(0,0)`$, and the defining relation is $`X_1X_2X_3=Y^3`$ (in suitable notation).

Note that the polynomial ring $`K[X_1,\mathrm{},X_n]`$ is a polytopal algebra, namely $`K[\mathrm{\Delta }_{n1}]`$ where $`\mathrm{\Delta }_{n1}`$ denotes the $`(n1)`$-dimensional unit simplex.

It is often useful to replace a polytope $`P`$ by a multiple $`cP`$ with $`c`$. The lattice points in $`cP`$ can be identified with the lattice points of degree $`c`$ in the cone $`C(S_P)`$; in fact, the latter are exactly of the form $`(x,c)`$ where $`xL_{cP}`$.

Polytopal semigroup algebras appear as the coordinate rings of projective toric varieties; see Oda \[Oda\]

## 3. Hilbert bases of affine normal semigroups

### 3.1. Normality and covering

In this section we will investigate the question whether the normality of a positive affine semigroup can be characterized in terms of combinatorial conditions on its Hilbert basis.

Let $`C`$ be a cone in $`^n`$ generated by finitely many rational (or integral) vectors. We say that a collection of rational subcones $`C_1,\mathrm{},C_m`$ is a *triangulation* of $`C`$ if $`C_i`$ is simplicial for all $`i`$ (i.e. generated by a linearly independent set of vectors), $`C=C_1\mathrm{}C_m`$ and $`C_{i_1}\mathrm{}C_{i_k}`$ is a face of $`C_{i_1},\mathrm{},C_{i_k}`$ for every subset $`\{i_1,\mathrm{},i_k\}\{1,\mathrm{},m\}`$.

Let $`M`$ be a subset of a cone $`C`$ as above. An *$`M`$-triangulation of $`C`$* is a triangulation into simplicial cones spanned by subsets of $`M`$, and a *Hilbert triangulation* is a $`\mathrm{Hilb}(S(C))`$-triangulation of $`C`$.

Correspondingly, a *Hilbert subsemigroup* $`S^{}`$ of $`S`$ is a subsemigroup generated by a subset of $`\mathrm{Hilb}(S)`$. We say that $`S`$ is *covered* by subsemigroups $`S_1,\mathrm{},S_m`$ if $`S=S_1\mathrm{}S_m`$.

A subset $`X`$ of $`^n`$ is called *unimodular* if it is part of a basis of $`^n`$; in other words, if it is linearly independent and generates a direct summand of $`^n`$. Cones and semigroups are *unimodular* if they are generated by unimodular sets, and a collection of unimodular objects is likewise called unimodular.

###### Proposition 3.1.1.

If $`S`$ is covered by unimodular subsemigroups, then it is normal. More generally, if $`S`$ is the union of normal subsemigroups $`S_i`$ such that $`\mathrm{gp}(S_i)=\mathrm{gp}(S)`$, then $`S`$ is also normal.

This follows immediately from the definition of normality.

We will see in Corollary 4.2.3 that the hypothesis $`\mathrm{gp}(S_i)=\mathrm{gp}(S)`$ is superfluous, and that it is even enough that the $`S_i`$ cover $`S`$ “asymptotically” .

The following converse is important for the geometry of toric varieties; it provides the combinatorial basis for the equivariant resolution of their singularities.

###### Theorem 3.1.2.

Every finitely generated rational cone $`C^n`$ has a unimodular triangulation.

It is not difficult to prove the theorem for which we may assume that $`dimC=n`$. One starts with an arbitrary triangulation of $`C`$, and considers each of the involved simplicial subcones $`C^{}`$. The shortest nonzero integer vectors on each of the rays of $`C^{}`$ form a linearly independent set $`X`$. If $`X`$ is not unimodular, then $`X`$ is not the Hilbert basis of $`S(C^{})`$, and one subdivides $`C^{}`$ by one of the vectors $`r_1x_1+\mathrm{}+r_mx_m`$ appearing in the proof of Gordan’s lemma. For each of the simplicial subcones $`C^{\prime \prime }`$ generated by subdivision the group $`\mathrm{gp}(S(C^{\prime \prime }))`$ has smaller index than $`\mathrm{gp}(S(C^{}))`$ in $`^n`$. After finitely many steps one thus arrives at a unimodular triangulation.

Especially for polytopal semigroups, Theorem 3.1.2 is not really satisfactory, since it is not possible to interpret it in the lattice structure of a polytope $`P^n`$. In fact, only the simplicial Hilbert subcones of $`C(S_P)`$ correspond to the lattice simplices contained in $`P`$. It is not hard to see that the cone spanned by a lattice simplex $`\delta P`$ is unimodular if and only if $`\delta `$ has the smallest possible volume $`1/n!`$. Such simplices are also called *unimodular*. Furthermore, $`P`$ (regardless of its dimension) can be triangulated into *empty* lattice simplices, i. e. simplices $`\delta `$ such that $`\delta ^n`$ is exactly the set of vertices of $`\delta `$.

Suppose now that $`P`$ is a lattice polytope of dimension $`2`$ and triangulate it into empty lattice simplices. Since, by Pick’s theorem, an empty simplex of dimension $`2`$ has area $`1/2`$, one automatically has a unimodular triangulation. It follows immediately that $`S_P`$ is the union of unimodular Hilbert subsemigroups and thus normal. Moreover, $`C(S_P)`$ has a unimodular Hilbert triangulation.

More generally, Sebő has shown the following

###### Theorem 3.1.3.

Every positive finitely generated cone of dimension $`3`$ has a unimodular Hilbert triangulation.

We refer the reader to Sebős paper \[Se\] or to \[BG3\] for the proof, which is by no means straightforward. The much simpler polytopal case discussed above is characterized by the fact that the elements of the Hilbert basis of $`C(S)`$ lie in a hyperplane.

Theorem 3.1.3 also holds in dimension $`1`$ and $`2`$ where it is easily proved, but it cannot be extended to dimension $`4`$, as shown by a counterexample due to Bouvier and Gonzalez-Sprinberg \[BoGo\].

As has been mentioned already, triangulations are very interesting objects for the geometry of toric varieties. Triangulations also provide the connection between discrete geometry and Gröbner bases of the binomial ideal defining a semigroup algebra. See Sturmfels \[Stu1\] for this important and interesting theme; we will briefly discuss it in Section 5.

Despite of counterexamples to the existence of unimodular Hilbert triangulations in dimension $`4`$, it is still reasonable to consider the following, very natural sufficient condition of *unimodular Hilbert covering* for positive normal semigroups $`S`$:

(UHC) *$`S`$ is covered by its unimodular Hilbert subsemigroups.*

For polytopal semigroups (UHC) has a clear geometric interpretation: it just says that $`P`$ is the union of its unimodular lattice subsimplices.

Sebő \[Se, Conjecture B\] has conjectured that (UHC) is satisfied by all normal affine semigroups. Below we present a $`6`$-dimensional counterexample to Sebő’s conjecture. However there are also positive results on (UHC) and even on unimodular triangulations for multiples $`cP`$ of polytopes; see Subsection 3.3.

A natural variant of (UHC), and weaker than (UHC), is the existence of a *free Hilbert cover*:

(FHC) *$`S`$ is the union (or covered by) the subsemigroups generated by the linearly independent subsets of $`\mathrm{Hilb}(S)`$.*

For (FHC) – in contrast to (UHC) – it is not evident that it implies the normality of the semigroup. Nevertheless it does so, as we will see in Corollary 4.2.3. A formally weaker – and certainly the most elementary – property is the *integral Carathéodory property*:

(ICP) *Every element of $`S`$ has a representation $`x=a_1s_1+\mathrm{}+a_ms_m`$ with $`a_i_+`$, $`s_i\mathrm{Hilb}(C)`$, and $`m\mathrm{rank}S`$.*

Here we have borrowed the well-motivated terminology of Firla and Ziegler \[FZ\]: (ICP) is obviously a discrete variant of Carathéodory’s theorem for convex cones. It was first asked in Cook, Fonlupt, and Schrijver \[CFS\] whether all cones have (ICP) and then conjectured in \[Se, Conjecture A\] that the answer is ‘yes’.

Later on we will use the *representation length*

$$\rho (x)=\mathrm{min}\{mx=a_1s_1+\mathrm{}+a_ms_m,a_i_+,s_i\mathrm{Hilb}(S)\}$$

for an element $`x`$ of a positive affine semigroup $`S`$. If $`\rho (x)m`$, we also say that $`x`$ is $`m`$-*represented*. In order to measure the deviation of $`S`$ from (ICP), we introduce the notion of *Carathéodory rank* of an affine semigroup $`S`$,

$$\mathrm{CR}(S)=\mathrm{max}\{\rho (x)xS\}.$$

Variants of this notion, called asymptotic and virtual Carathéodory rank will be introduced in Section 4.

The following $`10`$ vectors constitute the Hilbert basis of a normal positive semigroup $`S_6`$:

$`z_1`$ $`=(0,\mathrm{\hspace{0.17em}1},\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}0}),`$ $`z_6`$ $`=(1,\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}2},\mathrm{\hspace{0.17em}1},\mathrm{\hspace{0.17em}1},\mathrm{\hspace{0.17em}2}),`$
$`z_2`$ $`=(0,\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}1},\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}0}),`$ $`z_7`$ $`=(1,\mathrm{\hspace{0.17em}2},\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}2},\mathrm{\hspace{0.17em}1},\mathrm{\hspace{0.17em}1}),`$
$`z_3`$ $`=(0,\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}1},\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}0}),`$ $`z_8`$ $`=(1,\mathrm{\hspace{0.17em}1},\mathrm{\hspace{0.17em}2},\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}2},\mathrm{\hspace{0.17em}1}),`$
$`z_4`$ $`=(0,\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}1},\mathrm{\hspace{0.17em}0}),`$ $`z_9`$ $`=(1,\mathrm{\hspace{0.17em}1},\mathrm{\hspace{0.17em}1},\mathrm{\hspace{0.17em}2},\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}2}),`$
$`z_5`$ $`=(0,\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}1}),`$ $`z_{10}`$ $`=(1,\mathrm{\hspace{0.17em}2},\mathrm{\hspace{0.17em}1},\mathrm{\hspace{0.17em}1},\mathrm{\hspace{0.17em}2},\mathrm{\hspace{0.17em}0}).`$
As a counterexample to (UHC) it was found by the first two authors \[BG1\]. In cooperation with Henk, Martin and Weismantel \[BGHMW\] it was then shown that $`\mathrm{CR}(S_6)=7`$ so that (ICP) does not hold for all normal affine semigroups $`S`$. The cone $`C_6`$ and the semigroup $`S_6=S(C_6)`$ have several remarkable properties; for example, $`\mathrm{Aut}(S_6)`$ operates transitively on the Hilbert basis. The reader can easily check that $`z_1,\mathrm{},z_{10}`$ lie on a hyperplane. Therefore $`S_6=S_P`$ for a $`5`$-dimensional lattice polytope $`P`$. Further details can be found in the papers just quoted.

A crucial idea in finding $`S_6`$ was the introduction of the class of *tight* cones and semigroups; see \[BG1\].

So far one does not know a semigroup $`S`$ satisfying (ICP), but not (UHC). This suggests the following problem:

###### Problem 1.

Does *(ICP)* imply *(UHC)*?

Since the positive results end in dimension $`3`$ and the counterexample lives in dimension $`6`$, the situation is completely open in dimensions $`4`$ and $`5`$:

###### Problem 2.

Prove or disprove *(ICP)* and/or *(UHC)* in dimension $`4`$ and $`5`$.

We have seen above that every triangulation of a lattice polygon into empty lattice simplices is unimodular. This property is truly restricted to dimension at most $`2`$. In fact, Hosten, MacLagan, and Sturmfels \[HMS\] have given an example of a $`3`$-dimensional cone that contains no finite set $`M`$ of lattice points such that every triangulation of $`C`$ using all the points of $`M`$ is unimodular.

### 3.2. An upper bound for Carathéodory rank

Let $`p_1,\mathrm{},p_n`$ be different prime numbers, and set $`q_j=_{ij}p_i`$. Let $`S`$ be the subsemigroup of $`_+`$ generated by $`q_1,\mathrm{},q_n`$. Since $`\mathrm{gcd}(q_1,\mathrm{},q_n)=1`$, there exists an $`m_+`$ with $`uS`$ for all $`um`$. Choose $`um`$ such that $`u`$ is not divisible by $`p_i`$, $`i=1\mathrm{},n`$. Then all the $`q_i`$ must be involved in the representation of $`u`$ by elements of $`\mathrm{Hilb}(S)`$. This example shows that there is no bound of $`\mathrm{CR}(S)`$ in terms of $`\mathrm{rank}S`$ without further conditions on $`S`$.

For normal $`S`$ there is a linear bound for $`\mathrm{CR}(S)`$ as given by Sebő \[Se\]:

###### Theorem 3.2.1.

Let $`S`$ be a normal positive affine semigroup of rank $`2`$. Then $`\mathrm{CR}(S)2(\mathrm{rank}(S)1)`$.

For the proof we denote by $`C^{}(S)`$ the convex hull of $`S\{0\}`$ (in $`\mathrm{gp}(S)`$). Then we define the *bottom* $`B(S)`$ of $`C^{}(S)`$ by

$$B(S)=\{xC^{}(S):[0,x]C^{}(S)=\{x\}\}$$

($`[0,x]=\mathrm{conv}(0,x)`$ is the line segment joining $`0`$ and $`x`$). In other words, the bottom is exactly the set of points of $`C^{}(S)`$ that are *visible* from $`0`$ (see Figure 4).

Let $`H`$ be a support hyperplane intersecting $`C^{}(S)`$ in a compact facet. Then there exists a unique primitive $``$-linear form $`\gamma `$ on $`\mathrm{gp}(S)`$ such that $`\gamma (x)=a>0`$ for all $`xH`$ (after the extension of $`\gamma `$ to $`\mathrm{gp}(S)`$). Since $`\mathrm{Hilb}(S)H\mathrm{}`$, one has $`a`$. We call $`\gamma `$ the *basic grading* of $`S`$ associated with the facet $`HC^{}(S)`$ of $`C^{}(S)`$. It can be thought of as the graded structure

$$\mathrm{deg}_\gamma :S_+,x\gamma (x).$$

###### Proof of Theorem 3.2.1.

It is easily seen that the bottom of $`S`$ is the union of finitely many lattice polytopes $`F`$, all of whose lattice points belong to $`\mathrm{Hilb}(S)`$. We now triangulate each $`F`$ into empty lattice subsimplices. Choose $`xS`$, and consider the line segment $`[0,x]`$. It intersects the bottom of $`S`$ in a point $`y`$ belonging to some simplex $`\sigma `$ appearing in the triangulation of a compact facet $`F`$ of $`C^{}(S)`$. Let $`z_1,\mathrm{},z_n\mathrm{Hilb}(S)`$, $`n=\mathrm{rank}(S)`$, be the vertices of $`\sigma `$. Then we have

$$x=(a_1z_1+\mathrm{}+a_nz_n)+(q_1z_1+\mathrm{}+q_nz_n),a_i_+,q_i,0q_i<1,$$

as in the proof of Gordan’s lemma. Set $`x^{}=_{i=1}^nq_iz_i`$, let $`\gamma `$ be the basic grading of $`S`$ associated with $`F`$, and $`a=\gamma (y)`$ for $`yF`$. Then $`\gamma (x^{})<na`$, and at most $`n1`$ elements of $`\mathrm{Hilb}(S)`$ can appear in a representation of $`x^{}`$. This shows that $`\mathrm{CR}(S)2n1`$.

However, this bound can be improved. Set $`x^{\prime \prime }=x_1+\mathrm{}+x_nx^{}`$. Then $`x^{\prime \prime }S`$, and it even belongs to the cone generated by $`x_1,\mathrm{},x_n`$. If $`\gamma (x^{\prime \prime })<a`$, one has $`x^{\prime \prime }=0`$. If $`\gamma (x^{\prime \prime })=a`$, then $`x^{\prime \prime }`$ is a lattice point of $`\sigma `$. By the choice of the triangulation this is only possible if $`x^{\prime \prime }=x_i`$ for some $`i`$, a contradiction. Therefore $`\gamma (x^{\prime \prime })>a`$, and so $`\gamma (x^{})<(n1)a`$. It follows that $`\mathrm{CR}(S)2n2`$. ∎

In view of Theorem 3.2.1 it makes sense to set

$$𝒞(n)=\mathrm{max}\left\{\mathrm{CR}(S):S\text{ is normal positive and }\mathrm{rank}S=n\right\}.$$

With this notion we can reformulate Theorem 3.2.1 as $`𝒞(n)2(n1)`$. On the other hand, the counterexample $`S_6`$ to (ICP) presented above implies that

$$𝒞(n)\frac{7n}{6}.$$

In fact, $`\mathrm{rank}S_6=6`$ and $`\mathrm{CR}(S_6)=7`$. Therefore suitable direct sums $`S_6\mathrm{}S_6_+^p`$ attain the lower bound just stated.

###### Problem 3.

Improve one or both of the inequalities for $`𝒞(n)`$.

### 3.3. Unimodular covering of high multiples of polytopes

The counterexample presented above shows that a normal lattice polytope need not be covered by its unimodular lattice subsimplices. However, this always holds for a sufficiently high multiple of $`P`$ \[BGT\]:

###### Theorem 3.3.1.

For every lattice polytope $`P`$ there exists $`c_0>0`$ such that $`cP`$ is covered by its unimodular lattice subsimplices (and, hence, is normal by Proposition 3.1.1) for all $`c`$, $`c>c_0`$.

A proof can be found in \[BGT\] or \[BG3\]. For elementary reasons one can take $`c=1`$ in dimension $`1`$ and $`2`$, and it was communicated by Ziegler that $`c=2`$ suffices in dimension $`3`$. This is proved by Kantor and Sarkaria \[KS\]; moreover, they show that $`4P`$ has a unimodular triangulation for every lattice polytope $`P`$ in dimension $`3`$.

###### Problem 4.

Is it possible to choose $`c_0`$ only depending on the dimension of $`P`$? If the answer is positive, give an explicit estimate for $`c_0`$ in terms of $`dimP`$.<sup>1</sup><sup>1</sup>1Problem 4 has meanwhile been solved positively. See W. Bruns and J. Gubeladze, Unimodular covers of multiples of polytopes (in preparation), where a subexponential bound for $`c_0`$ is given.

For normality (without unimodular covering) this problem has a satisfactory answer:

###### Theorem 3.3.2.

For every lattice polytope $`P`$ the multiples $`cP`$ are normal for $`cdimP1`$.

This can be shown by essentially the same arguments as Theorem 3.2.1; see \[BGT\] for another argument.

In fact, it is proved in \[KKMS\] that one even has a stronger statement on the existence of unimodular Hilbert triangulations:

###### Theorem 3.3.3.

For every lattice polytope $`P`$ there exists $`c_0>0`$ such that $`cP`$ has a unimodular triangulation for all multiples $`c=kc_0`$, $`k`$.

However, note that Theorem 3.3.1 makes an assertion on all sufficiently large $`c`$, whereas Theorem 3.3.3 only concerns the multiples of a single $`c_0>0`$:

###### Problem 5.

Does $`cP`$ have a unimodular triangulation for all $`c0`$?

For applications in algebraic geometry or commutative algebra one is especially interested in so-called *regular* (or projective) triangulations. We will come back to this point in Section 5.

## 4. Algorithms for coverings

An affine semigroup $`S`$ is a subset of a free abelian group equipped with a minimal amount of algebraic structure, but this suffices to specify $`S`$ by finite data, namely a generating set. Therefore, the question of deciding whether an affine semigroup is the union of a given system of sub-semigroups, also specified in terms of generators, seems interesting. In this section we develop an algorithm deciding in a finite number of steps whether $`S`$ is covered by a system of subsemigroups. Actually, in the process of checking this property we have to treat the more general situation of “modules” over affine semigroups. The connection with Carathéodory ranks and (ICP) will also be outlined.

The algorithm contains subalgorithms for checking *asymptotic* and *virtual* covering properties.

For subsets $`A,B^n`$ we use the following notation

$$\pi (A|B)=\underset{\epsilon \mathrm{}}{lim}\frac{\mathrm{\#}\{aAB:a<\epsilon \}}{\mathrm{\#}\{bB:b<\epsilon \}}$$

provided the limit exists. (Here $``$ denotes the standard Euclidean norm in $`^n`$.) One should interpret $`\pi (A|B)`$ as the probability with which a random element of $`B`$ belongs to $`A`$.

From the view point of geometry it is preferable to associate objects in $`^n`$ with polytopes and cones. However, the reader should note that all data are specified in terms of rational vectors, and that the algorithms below only require arithmetic over $``$ (or $``$).

### 4.1. Normal affine semigroups

For the algorithms developed below it is important that certain basic computations for normal semigroups can be carried out:

* The determination of the Hilbert basis of $`S(C)`$ where $`C`$ is the cone given by finitely many elements $`z_1,\mathrm{},z_m^n`$. They generate the integral closure of the affine semigroup $`_+z_1+\mathrm{}+_+z_m`$.
* The determination of a finite system of generators of $`S(C)`$ as a module over the semigroup generated by $`z_1,\mathrm{},z_m`$.
* The description of the cone $`C`$ by a system of homogeneous rational inequalities.
* The reverse process of determining $`\mathrm{Hilb}(C)`$ from a description of $`C`$ by inequalities.
* The computation of a triangulation of $`C`$ into simplicial subcones spanned by elements of $`\{z_1,\mathrm{},z_m\}`$.

Note that the computations (b) and (c) are dual to each other under exchanging $`C`$ with its dual cone $`C^{}=\{\phi (^n)^{}:\phi (C)_+\}`$. Nevertheless one should mention (c) explicitly, since it allows one to compute intersections of cones.

Algorithms for (a)–(d) have already been implemented in NORMALIZ \[BK\], and the documentation of this program describes the details. In the following we will refer to NORMALIZ whenever one of these computations has to be carried out.

### 4.2. Asymptotic covers

Let $`S^n`$ be an affine semigroup, neither necessarily positive nor necessarily of full rank $`n`$. A subset $`M^n`$ is called an *$`S`$-module* if $`S+MM`$. A module $`M`$ is called *finitely generated* if $`M=\{m_1+s,\mathrm{},m_k+s:sS\}`$ for some finite subset $`\{m_1,\mathrm{},m_k\}M`$. For finitely generated modules we write $`M𝕄(S)`$. Notice, that in the special case $`S=0`$ a finitely generated $`S`$-module is just a finite set (maybe $`\mathrm{}`$).

Consider an affine semigroup $`S`$ and a finite family of affine semigroups

$$S_1,\mathrm{},S_tS.$$

We say that $`S`$ is covered *asymptotically* by the $`S_i`$ if $`\pi (S_1\mathrm{}S_t|S)=1`$. One should observe that the notion of asymptotic covering is an intrinsic property of the semigroup $`S`$ and the family $`\{S_1,\mathrm{},S_t\}`$. In other words, it does not depend on the embedding $`S^n`$. Further, $`S`$ is said to be *virtually* covered by the $`S_i`$ if $`\mathrm{\#}\left(S(S_1\mathrm{}S_t)\right)<\mathrm{}`$.

Now assume we are given a finitely generated $`S`$-module $`M`$ and $`S_i`$-submodules $`M_iM`$ so that $`M_i𝕄(S_i)`$ $`i[1,t]`$. One then introduces the notions of covering, asymptotic covering and virtual covering of $`M`$ by the $`M_i`$ in the obvious way.

###### Lemma 4.2.1.

For an affine semigroup $`S`$ the conductor ideal $`𝔠_{\overline{S}/S}=\{xS:x+\overline{S}S\}`$ is a nonempty set.

###### Proof.

Let $`G`$ be a generating set of $`S`$ and $`\overline{G}`$ be a finite generating set of $`\overline{S}`$ as a module over $`S`$. That $`\overline{S}`$ is in fact a finitely generated $`S`$-module, has been stated in Lemma 2.1.1. Fix representations $`z=x_zy_z`$, $`z\overline{G}`$, $`x_z,y_zG`$. Then $`_{zG}y_z𝔠_{\overline{S}/S}`$. ∎

Since one can effectively compute a system of generators of the $`S`$-module $`\overline{S}`$ once a generating set of $`S`$ is given, the proof of Lemma 4.2.1 provides an algorithm for computing an element of $`𝔠_{\overline{S}/S}`$ if a generating set of $`S`$ is given. This algorithm is called CONDUCTOR.

Consider an affine semigroup $`S^n`$ and a family of affine sub-semigroups $`S_1,\mathrm{},S_tS`$, $`t`$. Their cones in $`^n`$ will be denoted correspondingly by $`C(S),C(S_1),\mathrm{},C(S_t)`$. A family of *non-empty* modules $`M𝕄(S)`$, $`M_1𝕄(S_1),\mathrm{},M_t𝕄(S_t)`$, such that $`M_1,\mathrm{},M_tM`$ ($`^n`$), is also assumed to be given.

Put

$$\mathrm{\Sigma }=\{\sigma [1,t]:dim(\underset{i\sigma }{}C(S_i))=\mathrm{rank}S\text{and}\underset{i\sigma }{}\mathrm{gp}(S_i)=\mathrm{gp}(S)\}$$

and

$$C_\sigma =\underset{i\sigma }{}C(S_i),\sigma \mathrm{\Sigma }.$$

###### Lemma 4.2.2.

$`S`$ is asymptotically covered by $`S_1,\mathrm{},S_t`$ if and only if $`C(S)=_\mathrm{\Sigma }C_\sigma `$. Moreover, $`M`$ is asymptotically covered by the $`M_i`$ if and only if the following implication holds for every $`z^n`$:

$$\begin{array}{c}(z+\mathrm{gp}(S))M\mathrm{})\hfill \\ \hfill S\text{is asymptotically covered by}\{S_j:j[1,t],(z+\mathrm{gp}(S))M_j\mathrm{}\}.\end{array}$$

###### Proof.

Consider finite generating sets $`G_iS_i`$, $`i[1,n]`$. The affine hyperplanes in $`\mathrm{gp}(S)`$, spanned by the elements of $`_1^nG_i`$, cut the cone $`C(S)`$ into subcones which we call *elementary cells*, i. e. the elementary cells are the maximal dimensional cones in the obtained polyhedral subdivision of $`C(S)`$. Clearly, the elementary cells are again finite rational cones. So by Gordan’s lemma the semigroups $`SC`$ are all affine. (The general form of Gordan’s lemma used here and below follows from 2.1.1 and \[BG2, 7.2\].)

$`S`$ is asymptotically covered by the $`S_i`$ if and only if $`\pi \left(S_1\mathrm{}S_n|SE\right)=1`$ for every elementary cell $`E`$, or equivalently

$$\pi \left(\underset{i\sigma _E}{}S_iE|SE\right)=1$$

where $`\sigma _E=\{i[1,n]:EC(S_i)\}`$, $`E`$ running through the set elementary cells.

We claim that $`S`$ is asymptotically covered if and only if $`\sigma _E\mathrm{\Sigma }`$. This clearly proves the first part of the lemma.

The “only if” part of the claim follows easily from the fact that $`\mathrm{gp}(SE)=\mathrm{gp}(S)`$. For the “if” part we pick elements $`z_i𝔠_{\overline{S}_i/S_i}`$, $`i\sigma _E`$ (Lemma 4.2.1). Then the assumption $`\sigma _E\mathrm{\Sigma }`$ implies

$$S_0:=\mathrm{gp}(S)E\left(\underset{i\sigma _E}{}\left(z_i+C(S_i)\right)\right)SE$$

and we are done because by elementary geometric consideration one has

$$\pi \left(\underset{i\sigma _E}{}S_iE|S_0\right)=1.$$

Now assume the implication $``$ of the lemma holds. $`M`$ is contained in finitely many residue classes in $`^n`$ modulo $`\mathrm{gp}(S)`$. By fixing origins in these classes and taking intersections with the modules $`M,M_1,\mathrm{},M_t`$, the general case reduces to the situation when $`M,M_1,\mathrm{},M_t\mathrm{gp}(S)`$. Pick elements $`y_iM_i`$. Then we have

$$M_\sigma :=\mathrm{gp}(S)\underset{i\sigma }{}\left(y_i+z_i+C(S_i)\right)M,\sigma \mathrm{\Sigma },$$

with the $`z_i`$ chosen as above. We are done by the following observations:

$$M_\sigma \underset{i\sigma }{}M_i$$

and

$$\pi \left(\underset{\sigma \mathrm{\Sigma }}{}M_\sigma |M\right)=1,$$

the latter equality being easily deduced from the condition $`C(S)=_\mathrm{\Sigma }C_\sigma `$.

Now assume $`M`$ is asymptotically covered by the $`M_i`$. Then we have the implication

$$\begin{array}{c}(z+\mathrm{gp}(S))M\mathrm{})(z+\mathrm{gp}(S))M\text{is asymptotically covered by}\hfill \\ \hfill \{(z+\mathrm{gp}(S))M_j:j[1,t],(z+\mathrm{gp}(S))M_j\mathrm{}\}.\end{array}$$

It only remains to notice that each of these $`(s+\mathrm{gp}(S))M_j`$ is asymptotically covered by $`m_j+S`$ for an arbitrary element $`m_j(z+\mathrm{gp}(S))M_j`$, and, similarly, $`(z+\mathrm{gp}(S))M`$ is asymptotically covered by $`m+S`$, $`m(z+\mathrm{gp}(S))M`$. ∎

The proof of Lemma 4.2.2 gives an algorithm deciding whether $`S`$ is asymptotically covered by $`S_1,\mathrm{}S_t`$, using explicit generating sets as input. In fact, the conditions (i) that a finite rational cone is covered by a system of finite rational subcones and (ii) that a finitely generated free abelian group is covered by a system of subgroups, can both be checked effectively. It is of course necessary that we are able to compute the cone of an affine semigroup once a generating set of the semigroup is given (NORMALIZ), to form the intersection of a system of finite rational cones (given in terms of the support inequalities) and, furthermore, to compute the group of differences of an affine semigroups.

In fact, for the cone covering property we first triangulate the given cone $`C`$ (using only extreme generators) and then inspect successively the resulting simplicial subcones as follows. If such a simplicial cone $`T`$ is contained in one of the given cones, say $`C_1,\mathrm{},C_t`$, it is neglected and we pass to another simplicial cone. If it is not contained in any of the cones $`C_1,\mathrm{},C_t`$, then we split $`T`$ into two cones (of the same dimension) by the affine hull of a facet $`FC_i`$ for some $`i[1,t]`$. Thereafter the two pieces of $`T`$ are tested for the containment property in one of the $`C_i`$. If such a facet $`F`$ in not available, $`C`$ is not covered by the $`C_i`$. The process must stop because we only have finitely many affine spaces for splitting the produced cones.

As for the group covering test, we first form the intersection $`U`$ of all the given full rank subgroups $`G_1,\mathrm{},G_m^r`$. Then we check whether an element of each the finitely many residue classes in $`^r/U`$ in $`^r`$ belongs to one of the $`G_j`$.

Moreover, using the algorithm INTERSECTION in Subsection 4.3 below, which computes intersections of modules with affine subspaces, we can also give an algorithm for deciding whether $`M`$ is asymptotically covered by $`M_1,\mathrm{}M_t`$ (again using generating sets as input). One only needs to consider the finite number of residue classes in $`^n`$ modulo $`\mathrm{gp}(S)`$ represented by the given generators of $`M`$ – their union contains $`M`$.

The obtained algorithms, checking the asymptotic covering condition both for semigroups and modules, will be called ASYMPTOTIC.

We recall from \[BG1\] that the *asymptotic Carathéodory rank* $`\mathrm{CR}^\mathrm{a}(S)`$ of a positive affine semigroup $`S^n`$ is defined as

$$\mathrm{min}\left\{r:\pi (\{xS:\rho (x)r\}|S)=1\right\}.$$

($`\rho `$ is the representation length, see Subsection 3.1), and the *virtual Carathéodory rank* $`\mathrm{CR}^\mathrm{v}(S)`$ is defined as

$$\mathrm{min}\left\{r:\mathrm{\#}(S\{xS:\rho (x)r\})<\mathrm{}\right\}.$$

Lemma 4.2.2 has the following

###### Corollary 4.2.3.

* Suppose $`S^n`$ is an affine semigroup and $`S_1,\mathrm{},S_t`$ are affine sub-semigroups $`S_1,\mathrm{},S_t`$ of $`S`$. If these sub-semigroups are normal and cover $`S`$ asymptotically, then $`S`$ is normal and covered by $`S_1,\mathrm{},S_t`$.
* Assume $`S^n`$ is a positive affine semigroup. If $`\mathrm{CR}^\mathrm{a}(S)=\mathrm{rank}S`$ then $`S`$ is normal, $`\mathrm{CR}^\mathrm{v}(S)=\mathrm{CR}(S)=\mathrm{rank}S`$ and, moreover, $`S`$ satisfies (FHC). In particular, (ICP) and (FHC) are equivalent and they imply the normality.
* For $`S`$ as in upright there is an algorithm for computing $`\mathrm{CR}(S)`$ and, in particular, for checking (ICP) in finitely many steps.

###### Proof.

Claim (a) is a direct consequence of Lemma 4.2.2. Claim (b) follows from the same lemma and the observation that if $`\mathrm{CR}^\mathrm{a}(S)=\mathrm{rank}S`$, then the full rank free sub-semigroups of $`S`$, generated by elements of $`\mathrm{Hilb}(S)`$, cover $`S`$ asymptotically. This is so because the contribution from degenerate subsets of $`\mathrm{Hilb}(S)`$ is “thin” and cannot affect the asymptotic covering property. (c) follows from (b) and ASYMPTOTIC. ∎

###### Remark 4.2.4.

A motivation for the introduction of asymptotic and virtual Carathéodory ranks of positive semigroups is the following improvement of Sebő’s inequality 3.2.1. Suppose $`S`$ is an affine positive normal semigroup and $`\mathrm{rank}S3`$; then

$$\mathrm{CR}^\mathrm{a}(S)2\mathrm{rank}S3$$

and if, in addition, $`S`$ is *smooth*, then

$$\mathrm{CR}^\mathrm{v}(S)2\mathrm{rank}S3.$$

“Smooth” here means $`x+S_+^{\mathrm{rank}S1}`$ for each extreme generator of $`S`$. (Equivalently, for a field $`K`$ the variety $`\mathrm{Spec}(K[S])\{𝔪\}`$ is smooth, where $`𝔪`$ is the monomial maximal ideal of $`K[S]`$.) These inequalities have been proved in \[BG1\].

### 4.3. Virtual covers

Now we develop an algorithm checking the virtual covering condition. First we need an auxiliary algorithm that computes intersections of semigroups and modules with affine spaces.

More precisely, assume $`S^n`$ is an affine semigroup and $`M^n`$ is a finitely generated $`S`$-module, both given in terms of generating sets, say $`G_S`$ and $`G_M`$. Let $`H_0^n`$ be a rational subspace, given by a system of rational linear forms, and $`h^n`$. By Gordan’s lemma $`S_0=SH_0`$ is an affine semigroup and by \[BG2, 7.2\] $`M_h=M(h+H_0)`$ is a finitely generated module over it. Our goal is to find their generating sets.

By considering the intersections $`(z+S)(h+H_0)`$, $`z`$ running through $`G_M`$ one reduces the task to the special case when $`M`$ is generated by a single element, i. e. when $`M`$ is a parallel shift of $`S`$ in $`^n`$, say by $`z`$. Changing $`M`$ by $`z+M`$ and $`h`$ by $`hz`$ we can additionally assume $`M=S`$. Furthermore, taking the intersection $`H_0(\mathrm{gp}(S))`$, we may suppose that $`H_0\mathrm{gp}(S)`$. In other words, it is enough to consider the case $`n=\mathrm{rank}S`$.

Fix a surjective semigroup homomorphism $`\phi :_+^sS`$, $`s=\mathrm{\#}G_S`$, mapping the standard generators of $`_+^n`$ to the elements of $`G_S`$. It gives rise to a surjective linear mapping $`^s^n`$ which we denote again by $`\phi `$. Next we compute $`\mathrm{Ker}(\phi )`$ and, using it, the preimage $`L_0=\phi ^1(H_0)`$ – the latter is generated by $`\mathrm{Ker}(\phi )`$ and arbitrarily chosen preimages of a basis of the rational space $`H_0`$. Then we find an element $`l\phi ^1(h)`$. (Finding preimages requires only solving linear systems of equations.)

When we have computed a generating set of the semigroup $`_+^sL_0`$ and that of the module $`_+^s(l+L_0)`$ over it, then, by applying $`\phi `$, we find the desired generating sets. In other words, we have further reduced the problem to the special case when $`S=_+^n`$. The semigroup $`_+^nH_0`$ is normal and positive. Its Hilbert basis is computed using NORMALIZ.

Next we check whether $`^n(h+H_0)=\mathrm{}`$. This is done as follows. We compute a group basis $`B_1`$ of $`H_0^n`$ and find a system of vectors $`B_2`$, disjoint form $`B_1`$, such that $`B_1B_2`$ is a basis of $`^n`$. Then $`B_2`$ corresponds to a basis of the real space $`^n/H_0`$. We only need to check that the residue class of $`h`$ is integral with respect to it. This is a necessary and sufficient condition for $`^n(h+H_0)\mathrm{}`$.

If $`^n(h+H_0)\mathrm{}`$, then we can pick a lattice point $`p`$ in $`^n(h+H_0)`$. We declare it as the origin of the affine subspace $`p+H_0`$ with the coordinate system represented by $`p+B_1`$.

Next we compute the intersections $`C=_+^nH_0`$ and $`P=_+^n(h+H_0)`$, representing them by systems of inequalities in the coordinate systems of $`H_0`$ and $`h+H_0`$, which are given by $`B_1`$ and $`p+B_1`$ respectively.

We can make the natural identification $`H_0=^m`$, $`m=\mathrm{\#}B_1`$. Consider the convex hull $`\mathrm{\Pi }`$ in $`^{m+1}`$ of the subset

$$(C,0)(p+P,1)^{m+1}.$$

The crucial observation is that $`\mathrm{\Pi }`$ is a finite rational pointed cone (for a similar construction in the context of divisorial ideals see \[BG2, Section 5\]). Then, using again NORMALIZ we compute $`\mathrm{Hilb}(\mathrm{\Pi })`$. The last step consists of listing those elements of $`\mathrm{Hilb}(\mathrm{\Pi })`$ which have 1 as the last coordinate. Returning to the old copy of $`^n`$ these elements represent the minimal generating set of

$$_+^n(h+H_0)𝕄(_+^nH_0).$$

This algorithm will be called INTERSECTION.

Note that we do not exclude the case when $`H_0S=\{0\}`$. Then the algorithm above just lists the elements of the finite set $`M(h+H_0)`$.

Now assume $`S_1,\mathrm{},S_tS`$ and $`M,M_1,\mathrm{},M_t`$ are as in Subsection 4.2, given in terms of their generators. By $`\mathrm{\Sigma }`$, $`C_\sigma `$ and $`z_i`$ we refer to the same objects as in Lemma 4.2.2. We will describe an algorithm deciding the virtual covering property for the given semigroups and modules. It uses induction on $`\mathrm{rank}S`$.

In the case $`\mathrm{rank}S=1`$ one easily observes that asymptotic and virtual covering conditions coincide by Lemma 4.2.1. So we can apply ASYMPTOTIC.

Assume $`\mathrm{rank}S>1`$. Using ASYMPTOTIC we first check that we have at least asymptotic covering.

Let us first consider the case of semigroups. For every $`\sigma \mathrm{\Sigma }`$ we can pick an element $`z_\sigma _{i\sigma }(z_i+C(i))`$. Then

$$S_\sigma :=\mathrm{gp}(S)(z_\sigma +C_\sigma )S.$$

An important observation is that the complement $`(C_\sigma S)S_\sigma `$ is contained in finitely many sets of the type $`(h+F)S`$, where $`h\mathrm{gp}(S)`$ and $`FC_\sigma `$ is a facet. ($`F`$ refers to the linear space spanned by $`F`$.) Moreover, we can list explicitly such affine subspaces $`h+F`$ that cover this complement. Namely, for any facet $`FC_\sigma `$ we consider a system of vectors

$$\{h_0,h_1,\mathrm{},h_{v_F(z_\sigma )}\}\mathrm{gp}(S)$$

satisfying the condition $`v_F(h_j)=j`$, $`j[0,v_F(z_\sigma )]`$, where $`v_F:\mathrm{gp}(S)`$ is the surjective group homomorphism uniquely determined by the conditions $`v(F\mathrm{gp}(S))=0`$ and $`v_F((C_\sigma \mathrm{gp}(S))0`$.

The semigroup $`S`$ is virtually covered by $`S_1,\mathrm{},S_t`$ if and only if $`S(h+F)𝕄(SF)`$ is virtually covered by the modules

$$S_i(h+F)𝕄(S_iF),i[1,t]$$

for all the (finitely many) possibilities $`\sigma \mathrm{\Sigma }`$, $`FC_\sigma `$ and $`h\mathrm{gp}(S)`$ as above.

All of these intersection semigroups and modules can be computed with INTERSECTION. Therefore, having decreased the rank by one, we can use induction.

In the case of modules we first reduce the general case to the situation when $`M\mathrm{gp}(S)`$ – we just split the problem into finitely many similar problems corresponding to the set of residue classes of the given generators of $`M`$ modulo $`\mathrm{gp}(S)`$. We then pick elements (say, among the given generators) $`y_iM_i`$, $`i[1,t]`$ and also elements

$$m_\sigma \underset{i\sigma }{}(y_i+z_i+C(S_i)),\sigma \mathrm{\Sigma }.$$

We have

$$M_\sigma :=\mathrm{gp}(S)(m_\sigma +C_\sigma )M,\sigma \mathrm{\Sigma }.$$

Let $`m`$ be an element of the given generating set for $`M`$. Then the complement $`(M(m+C_\sigma ))M_\sigma `$ is contained in finitely many sets of the type $`(h+F)M`$, where the $`F`$ are as above and the $`h\mathrm{gp}(S)`$ constitute a finite system such that the $`v_F(h)`$ exhaust the integers between $`v_F(m)`$ and $`v_F(m_\sigma )`$. We see that all the steps we have carried out for the semigroups can be performed in the situation of modules as well – we only need to go through the whole process for every generator of $`M`$.

The produced algorithm, deciding the virtual covering property, is called VIRTUAL.

### 4.4. Covers

Now we complete the algorithm deciding covering property for semigroups and their modules, as mentioned at the beginning of Section 4. The algorithm will be called COVERING. Again, we use induction on rank of the big semigroup. Analyzing VIRTUAL one observes that the inductive step in developing COVERING can be copied word-by-word from VIRTUAL. So the only thing we need to describe is COVERING for rank 1 semigroups.

Assume $`S,S_1,\mathrm{},S_t`$ and $`M,M_1,\mathrm{},M_t`$ are as above and, in addition, $`\mathrm{rank}S=1`$. We restrict ourselves to the case when $`S`$ is positive. The other case can be done similarly.

After computing $`\mathrm{gp}(S)`$, we can assume $`\mathrm{gp}(S)=`$ without loss of generality. Since $``$ is covered by a finite system of subgroups exactly when one of the subgroups is the whole $``$ we must check (according to Lemma 4.2.2) that one of the groups $`\mathrm{gp}(S_1),\mathrm{},\mathrm{gp}(S_t)`$ coincides with $``$. Assume $`\mathrm{gp}(S_1)=`$. By CONDUCTOR we find an element $`z𝔠_{\overline{S}_1/S_1}`$. Now we only need to make sure that the finite set $`[1,z]S`$ is in the union $`S_1\mathrm{}S_t`$.

For the modules we first reduce the general case to the situation $`M`$ (as we did in the previous subsection) and, by a suitable shift, further to the special case $`0M_+`$. By Lemma 4.2.2 there is no loss of generality in assuming that $`M_1\mathrm{}`$. Then, again, we only have a finite problem of checking that $`[0,z+m]MM_1\mathrm{}M_t`$, where $`z`$ is as above and $`mM_1`$ is arbitrarily chosen element (say, a given generator).

###### Remark 4.4.1.

As mentioned, our goal in this section was to show that the question whether a given affine semigroup is covered by a finite system of affine sub-semigroups can be checked algorithmically. However, we did not try to make the algorithm as optimal as possible. For instance, our arguments use heavily conductor ideals and we work with random elements in these ideals. On the other hand in some special cases one can compute $`𝔠_{\overline{S}/S}`$ exactly. Especially this is possible in the situation when $`S`$ is a positive affine semigroup, generated by $`\mathrm{rank}S+1`$ elements; see \[RR\].

The real motivation for implementing a part of the algorithms above would be a semigroup that violates (UHC), but resists all random tests for detecting the violation of (ICP) (or, equivalently, (FHC); see Corollary 4.2.3(b)). Unfortunately, so far we have only found 2 essentially different semigroups violating (UHC), and they violate (ICP) too.

## 5. Algebraic properties of affine semigroup algebras

In this section we always consider affine semigroups $`S`$ of $`_+^r`$ (often $`r`$ will be the rank of $`S`$, but we do not necessarily assume this). Then the affine semigroup algebra $`K[S]`$ over a field $`K`$ can be viewed as a subalgebra of the polynomial ring $`K[T_1,\mathrm{},T_r]`$.

### 5.1. Defining equations

Let $`\mathrm{Hilb}(S)=\{x_1,\mathrm{},x_n\}`$. Consider the semigroup homomorphism $`\pi :_+^nS`$ given by $`(u_1,\mathrm{},u_n)u_1x_1+\mathrm{}+u_nx_n`$. Let $`K[X]=K[X_1,\mathrm{},X_n]`$ be a polynomial ring over a field $`K`$ in $`n`$ indeterminates. The map $`\pi `$ lifts to a homomorphism of semigroup algebras $`\phi :K[X]K[S]`$. The kernel of $`\phi `$ is a prime ideal $`I_S`$ in $`K[X]`$ and we have a representation of the semigroup algebra

$$K[S]K[X]/I_S.$$

The ideal $`I_S`$ is often called the *toric ideal* of $`S`$. The following result is well-known (for example, see Gilmer \[Gi\]).

###### Proposition 5.1.1.

The toric ideal $`I_S`$ is generated by the set of binomials

$$\{X^uX^v|u,v_+^n\text{with}\pi (u)=\pi (v)\}.$$

Let $`\mu (I)`$ denote the minimal number of generators of an ideal $`I`$. Because of the above property of $`I_S`$ one might think that $`\mu (I_S)`$ could not be big or, more precisely, that $`\mu (I_S)`$ were bounded by a number which depends only on the number $`n`$. But that is not the case.

Let $`S`$ be a *numerical semigroup*, that is $`S_+`$. If $`n=2`$, then $`\mu (I_S)=1`$ because $`I_S`$ is a principal ideal in $`K[X_1,X_2]`$. If $`n=3`$, Herzog \[He\] proved that $`\mu (I_S)3`$. If $`n4`$, Bresinsky \[Bre1\] showed that $`\mu (I_S)`$ can be arbitrarily large.

However, one may expect that $`\mu (I_S)`$ depends only on $`n`$ for special classes of affine semigroups. Let $`S`$ be generated by $`n`$ non-negative integers $`x_1,\mathrm{},x_n`$. Without restriction we may assume that $`x_1,\mathrm{},x_n`$ have no common divisor other than 1. Then there exists an integer $`c`$ such that $`aS`$ for all integers $`ac`$ (i. e. $`c`$ is in the conductor ideal). Let $`c`$ be the least integer with this property. We call $`S`$ a *symmetric numerical semigroup* if $`aS`$ whenever $`ca1S`$, $`a`$.

###### Example 5.1.2.

Let $`S=6,7,8`$. Then

$$S=\{0,6,7,8,12,13,14,15,16,18,19,20,21,22,\mathrm{}\}.$$

Hence $`c=18`$. It is easy to check that $`S`$ is a symmetric numerical semigroup.

The interest on symmetric numerical semigroups originated from the classification of plane algebroid branches \[Ap\]. Later, Herzog and Kunz \[HK\] realized that symmetric numerical semigroups correspond to Gorenstein affine monomial curves.

###### Problem 6.

Let $`S`$ be a symmetric numerical semigroup. Does there exist an upper bound for $`\mu (I_S)`$ which depends only on the minimal number of generators of $`S`$?

If $`n=3`$, Herzog \[He\] proved that $`\mu (I_S)=2`$. If $`n=4`$, Bresinsky \[Bre2\] proved that $`\mu (I_S)5`$. If $`n=5`$, Bresinsky \[Bre3, Theorem 1\] proved that $`\mu (I_S)13`$, provided $`x_1+x_2=x_3+x_4`$. It was also Bresinsky \[Bre2, p. 218\], who raised the above problem which has remained open until today.

Instead of estimating the number of generators of $`I_S`$ one can also try to bound the degree of the generators. We will discuss this problem in Subsections 5.2 and 5.4.

We call the least integer $`s`$ for which there exist binomials $`f_1,\mathrm{},f_s`$ such that $`I_S`$ is the radical of the ideal $`(f_1,\mathrm{},f_s)`$ the *binomial arithmetical rank* of $`I_S`$ and we will denote it by $`\mathrm{bar}(I_S)`$. Geometrically, this means that the affine variety defined by $`I_S`$ is the intersection of the hypersurfaces $`f_1=0,\mathrm{},f_s=0`$. In general, we have $`\mathrm{ht}I_S\mathrm{bar}(I_S)\mu (I_S)`$.

###### Problem 7.

Does there exist an upper bound for $`\mathrm{bar}(I_S)`$ in terms of $`n`$?

We mention only a few works on this problem. If $`S`$ is a homogeneous (i.e. graded and generated by elements of degree $`1`$) affine semigroup in $`_+^2`$, Moh \[M\] proved that $`\mathrm{bar}(I_S)=n2`$ for $`K`$ of positive characteristic. This implies that $`I_S`$ is a set-theoretic complete intersection. If $`K`$ has characteristic $`0`$ and $`S`$ is as above, then Thoma \[Th\] has shown that $`\mathrm{bar}(I_S)=n2`$ if $`I_S`$ is a complete intersection, otherwise $`\mathrm{bar}(I_S)=n1`$. These results have been recently generalized by Barile, Morales and Thoma \[BMT\] to affine semigroup algebras of the form

$$K[S]=K[t_1^{d_1},\mathrm{},t_r^{d_r},t_1^{a_{11}}\mathrm{}t_r^{a_{1r}},\mathrm{},t_1^{a_{s1}}\mathrm{}t_r^{a_{sr}}],$$

where $`d_1,\mathrm{},d_r`$ and $`a_{11},\mathrm{},a_{sr}`$ are positive integers.

### 5.2. Initial ideals and the Koszul property

Let $`K[X]=K[X_1,\mathrm{},X_n]`$ be a polynomial ring over a field $`k`$. As usual, we will identify a monomial $`X^u=X_1^{u_1}\mathrm{}X_n^{u_n}`$ with the lattice point $`u=(u_1,\mathrm{},u_n)`$. A total order $`<`$ on $`_+^n`$ is a *term order* if it has the following properties:

* the zero vector 0 is the unique minimal element;
* $`v<w`$ implies $`u+v<u+w`$ for all $`u,v,w^n`$.

Given a term order $`<`$, every non-zero polynomial $`fK[X]`$ has a largest monomial which is called the *initial monomial* of $`f`$. If $`I`$ is an ideal in $`K[X]`$, we denote by $`\mathrm{in}(I)`$ the ideal generated by the initial monomials of the elements of $`I`$. This ideal is called the *initial ideal* of $`I`$. The passage from $`I`$ to $`\mathrm{in}(I)`$ is a flat deformation (see e.g. \[Ei, 15.8\]). Hence one can study $`I`$ be means of $`\mathrm{in}(I)`$.

With every monomial ideal $`J`$ we can associate the following combinatorial object

$$\mathrm{\Delta }(J):=\{F\{1,\mathrm{},n\}:\text{there is no monomial in }J\text{ whose support is }F\}$$

where the support of a monomial $`X^a`$ is the set $`\{i:a_i0\}`$. Clearly $`\mathrm{\Delta }(J)`$ is a simplicial complex on the vertex set $`\{1,\mathrm{},n\}`$, and it easily seen that $`J`$ and its radical $`\sqrt{J}`$ define the same simplicial complex: $`\sqrt{J}`$ is generated by all *square-free monomials* $`X_{i_1}\mathrm{}X_{i_s}`$, $`i_1<\mathrm{}<i_s`$, for which $`\{i_1,\mathrm{},i_s\}`$ is not a face of $`\mathrm{\Delta }(J)`$.

We call $`\mathrm{\Delta }(\mathrm{in}(I))`$ the *initial complex* of $`I`$ (with respect to the term order $`<`$).

For a toric ideal $`I_S`$ one may ask whether there is a combinatorial description of the initial ideal $`\mathrm{in}(I_S)`$ or, at least, their radicals.

In the remaining part of this subsection we assume that $`S`$ is a homogeneous affine semigroup $`S_M^{r+1}`$ with Hilbert basis $`M=\{x_1,\mathrm{},x_n\}^r`$. By $`C`$ we denote the cone $`C(S)`$.

An $`M`$-triangulation of $`C`$ is called *regular* if there is a *weight vector* $`\omega =(\omega _1,\mathrm{},\omega _n)_+^n`$ such that the simplicial cones of the triangulation are spanned exactly by those subsets $`FM`$ for which there exists a vector $`c^r`$ with

$`c,x_i=\omega _i`$ $`\text{ if }x_iF,`$
$`c,x_j<\omega _j`$ $`\text{ if}x_jF.`$
Geometrically, the simplicial cones of a regular triangulation of $`C(S)`$ are the projections of the lower faces of the convex hull $`P`$ of the vectors $`\{(x_1,\omega _1),\mathrm{},(x_n,\omega _n)\}`$ in $`^{r+1}`$ onto the first $`r`$ coordinates. Note that a face of $`P`$ is lower if it has a normal vector with negative last coordinate.

It is clear that every $`M`$-triangulation of $`C(S)`$ can be identified with the simplicial complex of those subsets $`\{i_1,\mathrm{},i_r\}\{1,\mathrm{},n\}`$ for which the vectors $`x_{i_1},\mathrm{},x_{i_r}`$ span a face of a simplicial cone of the triangulation. Using this identification, Sturmfels \[Stu1\], Theorem 8.3 and Corollary 8.4, discovered the following connections between the initial complexes of $`I_S`$ and the triangulations of $`C(S)`$.

###### Theorem 5.2.1.

The initial complexes $`\mathrm{\Delta }(\mathrm{in}(I_S))`$ are exactly the simplicial complexes of the regular $`M`$-triangulations of $`C(S)`$.

###### Corollary 5.2.2.

The ideal $`\mathrm{in}(I_S)`$ is generated by square-free monomials if and only if the corresponding regular $`M`$-triangulation of $`C(S)`$ is unimodular.

Therefore, if $`I_S`$ has a square-free initial ideal, then $`S`$ must be normal and, being generated in degree $`1`$, polytopal (see Proposition 3.1.1). On the other hand, as the counterexample in Subsection 3.1 shows, there exist normal lattice polytopes without any unimodular triangulation (even without unimodular covering). Therefore $`I_S`$ need not have a square-free initial ideal for normal polytopal semigroups $`S`$. (There also exist polytopes that have a unimodular triangulation, but no such regular triangulation; see Ohsugi and Hibi \[OH1\].)

However, as observed in Subsection 3.1, any triangulation of a lattice polytope of dimension 2 into empty lattice simplices is unimodular by Pick’s theorem, and $`I_S`$ has plenty of square-free initial ideals in this special situation.

The results of Sturmfels give us a method to prove that a semigroup algebra is Koszul. Recall that a homogeneous algebra $`A`$ over a field $`K`$ is called *Koszul* if $`K`$ as an $`A`$-module has a resolution:

$$\mathrm{}E_2\stackrel{\phi _2}{}E_1\stackrel{\phi _1}{}AK0,$$

where $`E_1,E_2,\mathrm{}`$ are free $`R`$-modules and the entries of the matrices $`\phi _1,\phi _2,\mathrm{}`$ are forms of degree 1 in $`A`$. For more information see the survey of Fröberg \[Fr\].

Let $`A=R/I`$ be a presentation of $`A`$, where $`R`$ is a polynomial ring over $`K`$ and $`I`$ is a homogeneous ideal in $`R`$. If $`A`$ is a Koszul algebra, then $`I`$ must be generated by quadratic forms. The converse is not true. However, $`A`$ is Koszul if there exists a term order $`<`$ such that the initial ideal $`\mathrm{in}(I)`$ is generated by quadratic monomials. Therefore, if a lattice polytope $`P`$ has a unimodular regular triangulation whose minimal non-faces are edges, then the semigroup algebra $`K[P]`$ is Koszul.

We have proved in \[BGT\] that the following classes of lattice polytopes have this property:

* lattice polytopes in $`^2`$ whose boundaries have more than 3 lattice points,
* lattice polytopes in $`^r`$ whose facets are parallel to the hyperplanes given by the equations $`T_i=0`$ and $`T_iT_j=0`$.

In particular, it can be shown that if $`P`$ is a lattice polytope in $`^2`$ with more than 3 lattice points, then $`K[P]`$ is Koszul if and only if the boundary of $`P`$ has more than 3 lattice points.

It would be of interest to find more lattice polytopes which have unimodular regular triangulations whose minimal non-faces are edges. For any lattice polytope $`P^r`$, it is known that the semigroup algebra $`K[cP]`$ is Koszul for $`cr`$ \[BGT, Theorem 1.3.3\]. This has led us to the following problem.

###### Problem 8.

Does $`cP`$, $`c0`$, have a unimodular regular triangulation $`\mathrm{\Delta }`$ such that the minimal non-faces of $`\mathrm{\Delta }`$ are edges?

We have already stated this problem in Subsection 3.3, however without the attribute “regular” and the condition that the minimal non-faces of $`\mathrm{\Delta }`$ should be edges. In this connection we have pointed out that unimodular triangulations for $`cP`$ have been constructed for infinitely many $`c`$ in \[KKMS\]; these triangulations are in fact regular.

It has been asked whether a Koszul semigroup algebra always has an initial ideal generated by quadratic monomials. But this question has a negative answer by Roos and Sturmfels \[RS\]. There also exist normal non-Koszul semigroup algebras defined by quadratic binomials; see Ohsugi and Hibi \[OH2\].

### 5.3. The Cohen-Macaulay and Buchsbaum properties

Let $`(A,𝔪)`$ be a local ring. A system of elements $`x_1,\mathrm{},x_s`$ of $`A`$ is called a *regular sequence* if

$$(x_1,\mathrm{},x_{i1}):x_i=(x_1,\mathrm{},x_{i1}),i=1,\mathrm{},s.$$

It is called a *weak-regular sequence* if

$$𝔪[(x_1,\mathrm{},x_{i1}):x_i](x_1,\mathrm{},x_{i1}),i=1,\mathrm{},s.$$

Let $`d=dimA`$. A system of $`d`$ elements $`x_1,\mathrm{},x_d`$ of $`A`$ is called a *system of parameters* of $`A`$ if the ideal $`(x_1,\mathrm{},x_d)`$ is an $`𝔪`$-primary ideal. The local ring $`A`$ is called a *Cohen-Macaulay ring* if there exists an (or every) system of parameters of $`A`$ is a regular sequence. It is called a *Buchsbaum ring* if every system of parameters of $`A`$ is a weak-regular sequence. If $`A`$ is a finitely generated homogeneous algebra over a field and $`𝔪`$ is its maximal homogeneous ideal, then we call $`A`$ a Cohen-Macaulay resp. Buchsbaum ring if the local ring of $`A`$ at $`𝔪`$ is Cohen-Macaulay resp. Buchsbaum. Cohen-Macaulay resp. Buchsbaum rings can be characterized in different ways and they have been main research topics in Commutative Algebra. See \[BH\] and \[SV\] for more information on these classes of rings.

By a fundamental theorem of Hochster \[Ho\] normal affine semigroup rings are Cohen-Macaulay. For general affine semigroup rings the Cohen-Macaulay property has been characterized in \[TH, Theorem 3.1\], which is based on earlier work of Goto and Watanabe \[GW\]. For two subsets $`E`$ and $`F`$ of $`^r`$ we set

$$E\pm F=\{v\pm w|vE,wF\}.$$

Let $`F_1,\mathrm{},F_m`$ be the facets of the cone $`C(S)`$. Put $`S_i=S(SF_i)`$ and

$$S^{}=\underset{i=1}{\overset{m}{}}S_i.$$

For every subset $`J`$ of the set $`[1,m]=\{1,\mathrm{},m\}`$ we set

$$G_J=\underset{iJ}{}S_i\underset{jJ}{}S_j,$$

and we denote by $`\pi _J`$ the simplicial complex of non-empty subsets $`I`$ of $`J`$ with $`_{iI}(SF_i)\{0\}`$.

###### Theorem 5.3.1.

$`K[S]`$ is a Cohen-Macaulay ring if and only if the following conditions are satisfied:

* $`S^{}=S`$;
* $`G_J`$ is either empty or acyclic over $`K`$ for every proper subset $`J`$ of $`[1,m]`$.

Though Buchsbaum rings enjoy many similar properties like those of Cohen-Macaulay rings, one has been unable to find a similar characterization for the Buchsbaum property of $`K[S]`$.

###### Problem 9.

Find criteria for an affine semigroup algebra $`K[S]`$ to be a Buchsbaum ring in terms of the affine semigroup $`S`$.

Recall that an affine semigroup $`S`$ is called *simplicial* if $`C(S)`$ is spanned by $`r`$ vectors of $`S`$, where $`r=\mathrm{rank}S`$. Geometrically, this means that $`C(S)`$ has $`r`$ extreme rays or, equivalently, $`r`$ facets. This class contains all affine semigroups in $`^2`$. Goto, Suzuki and Watanabe \[GSW\] resp. Trung \[Tr1\] gave the following simple criteria for a simplicial affine semigroup algebra to be Cohen-Macaulay resp. Buchsbaum.

###### Theorem 5.3.2.

Let $`S`$ be a simplicial affine semigroup with $`d=\mathrm{rank}\mathrm{gp}(S)`$. Let $`v_1,\mathrm{},v_d`$ be the vectors of $`S`$ which span $`C(S)`$. Then

* $`K[S]`$ is Cohen-Macaulay if and only if

$$\{v\mathrm{gp}(S):v+v_i,v+v_jS\text{for some indices }ij\}=S;$$
* $`K[S]`$ is Buchsbaum if and only if

$$\{v\mathrm{gp}(S)|v+2v_i,v+2v_jS\text{for some indices }ij\}+\mathrm{Hilb}(S)S.$$

The above criteria are even effective. For example consider (a). Then we form the intersection

$$(s_i+S)(s_j+S)$$

of $`S`$-modules and test whether this module is contained in $`S`$. Section 4 contains algorithms for these tasks. From the ring-theoretic point of view, the main special property of simplicial affine semigroups is the existence of a homogeneous system of parameters consisting of monomials. Therefore certain homological properties that depend on system of parameters can be formulated in terms of the semigroup.

What we know on a given affine semigroup is usually its Hilbert basis. Therefore, we raise the following stronger problem.

###### Problem 10.

Find criteria for $`K[S]`$ to be a Cohen-Macaulay or Buchsbaum ring in terms of $`\mathrm{Hilb}(S)`$.

This problem is not even solved for the class of homogeneous affine semigroups in $`_+^2`$ which are generated by subsets of

$$M_e=\{v=(v_1,\mathrm{},v_r)_+^r|v_1+\mathrm{}+v_r=e\},$$

where $`e`$ is a given positive number. The algebra of the semigroup generated by the full set $`M_e`$ is just the homogeneous coordinate ring of the $`e`$-th Veronese embedding of the $`(r1)`$-dimensional projective space. The algebras generated by subsets of $`M_e`$ are the homogeneous coordinate rings of projections of this Veronese variety.

Gröbner \[Gr\] was the first who studied the Cohen-Macaulay property of such semigroup algebras. Let $`H`$ be an arbitrary subset of $`M_e`$ and $`S=H`$. If $`H`$ is obtained from $`M_e`$ by deleting one, two, or three vectors, we know exactly when $`K[S]`$ is a Cohen-Macaulay or Buchsbaum ring \[Sch, Tr1, Hoa\]. If $`r=2`$, we may identify $`H`$ with the sequence $`\alpha _1,\mathrm{},\alpha _n`$ of the first coordinates of the vectors of $`H`$. There have been some attempts to determine when $`K[S]`$ is a Buchsbaum or Cohen-Macaulay ring in terms of $`\alpha _1,\mathrm{},\alpha _n`$. But satisfactory answers were obtained only in a few special cases \[Bre4, BSV, Tr2\].

### 5.4. Castelnuovo-Mumford regularity

Let $`A=_{t0}A_t`$ be a finitely generated homogeneous algebra over the field $`K`$. Let $`A=R/I`$ be a representation of $`A`$, where $`R`$ is a polynomial ring over $`K`$ and $`I`$ a homogeneous ideal of $`R`$. Then we have a finite minimal free resolution of $`A`$ as a graded $`R`$-module:

$$0E_s\mathrm{}E_1RA0,$$

where $`E_1,\mathrm{},E_s`$ are graded $`R`$-modules. Let $`b_i`$ be the maximum degree of the generators of $`E_i`$, $`i=1,\mathrm{},s`$. Then the Castelnuovo-Mumford regularity of $`A`$ is defined as the number

$$\mathrm{reg}(A):=\mathrm{max}\{b_ii|i=1,\mathrm{},s\}.$$

It is independent of the representation of $`A`$. In fact, it can be defined solely in terms of $`A`$ as follows.

Let $`𝔪`$ denote the maximal homogeneous ideal of $`A`$. For any $`A`$-module $`M`$ we set

$$\mathrm{\Gamma }_𝔪(M):=\{xM|x𝔪^t=0\text{for some number }t0\}.$$

Then $`\mathrm{\Gamma }_𝔪()`$ is a left exact additive functor from the category of $`A`$-modules into itself. Let $`H_𝔪^i()`$ denote the $`i`$-th right derived functor of $`\mathrm{\Gamma }_𝔪()`$. Then $`H_𝔪^i(M)`$ is called the $`i`$-th *local cohomology module* of $`M`$ (with respect to $`𝔪`$). If $`M`$ is a graded $`A`$-module, then $`H_𝔪^i(M)`$ is also a graded $`A`$-module. Write $`H_𝔪^i(M)=_tH_𝔪^i(M)_t`$. It is known that $`\mathrm{reg}(A)`$ is the least integer $`m`$ such that $`H_𝔪^i(A)_t=0`$ for all $`t>mi`$ and $`i0`$.

The Castelnuovo-Mumford regularity $`\mathrm{reg}(A)`$ is an extremely important invariant because it is a measure for the complexity of $`A`$. For instance, $`\mathrm{reg}(A)+1`$ is an upper bound for the maximal degree of the defining equations of the ideal $`I`$. See \[EG\] and \[Ei\] for more information on the Castelnuovo-Mumford regularity.

It is a standard fact that the *Hilbert function* $`dim_KA_t`$ is a polynomial $`P_A(t)`$ of degree $`d1`$ for $`t0`$, where $`d=dimA`$. If we write

$$P_A(t)=\frac{et^{d1}}{(d1)!}+\text{terms of degree }<d1,$$

then $`e`$ is called the *multiplicity* of $`A`$. Let $`n`$ denote the minimal number of generators of $`A`$. In general, the regularity is bounded by a double exponential function of $`e`$, $`d`$ and $`n`$. However, if $`A`$ is a domain, there should be an upper bound for $`\mathrm{reg}(A)`$ with lower complexity. In this case, Eisenbud and Goto \[EG\] have conjectured that

$$\mathrm{reg}(A)e+nd.$$

Gruson, Lazarsfeld and Peskine proved this conjecture in the case $`dimA=2`$ \[GLP\] (the case $`dimA=1`$ is trivial). For $`dimA3`$, it has been settled only under some additional conditions on $`A`$.

For affine semigroup algebras, the above conjecture is still open. Except those cases which can be derived from the known results for homogeneous domains, the conjecture has been settled only for affine semigroup algebras of codimension 2 ($`nd=2`$) by Peeva and Sturmfels \[PS\].

Let $`S`$ be a homogeneous affine semigroup. Then $`\mathrm{Hilb}(S)`$ must lie on a hyperplane of $`^r`$. It is known that the multiplicity $`e`$ of $`K[S]`$ is equal to the normalized volume of the convex polytope spanned by $`\mathrm{Hilb}(S)`$ in this hyperplane (for example, see \[BH, 6.3.12\]). Moreover, one can also describe the regularity \[Stu1\] and the local cohomology of $`K[S]`$ combinatorially in terms of $`S`$ (see e.g. \[St1, TH, SS\] or \[BH, Ch. 6\]).

For a homogeneous affine semigroup $`S`$ in $`_+^2`$, this description is very simple. Without restriction we may assume that $`\mathrm{Hilb}(S)`$ consists of vectors of the forms $`(a,1)`$, $`0ae`$, where the vectors $`v_1=(0,1)`$ and $`v_2=(e,1)`$ belong to $`S`$. Let $`S^{}`$ denote the set of vectors $`v_+^2`$ for which there are positive integers $`m_1,m_2`$ such that $`v+m_1v_1S`$, $`v+m_2v_2S`$. Then $`\mathrm{reg}(K[S])=\mathrm{max}\{a+b|(a,b)S^{}S\}+1`$. By the result of Gruson, Lazarsfeld and Peskine, $`\mathrm{reg}(K[S])en+2`$, where $`n`$ is the number of vectors of $`\mathrm{Hilb}(S)`$. It would be nice if we could find a combinatorial proof for this bound.

We say that a binomial $`X^uX^vI_S`$ is *primitive* if there is no other binomial $`X^u^{}X^v^{}I_S`$ such that $`X^u^{}`$ divides $`X^u`$ and $`X^v^{}`$ divides $`X^v`$. The set of all primitive binomials of $`I_S`$ generates $`I_S`$. It is called the *Graver basis* of $`I_S`$ and denoted by $`\mathrm{Gr}_S`$. A binomial $`\zeta `$ in $`I_S`$ is called a *circuit* of $`S`$ if its support $`\mathrm{supp}(\zeta )`$ (the set of variables appearing in $`\zeta `$) is minimal with respect to inclusion. The *index* of a circuit $`\zeta `$ is the index of the additive group generated by $`\mathrm{supp}(\zeta )`$ in the intersection of $`\mathrm{gp}(S)`$ with the linear space spanned by $`\mathrm{supp}(\zeta )`$ in $`^n`$.

###### Problem 11.

Prove that the degree of every binomial in $`\mathrm{Gr}_S`$ is bounded above by the maximum of the products of the degree and the index of the circuits of $`S`$.

This problem was raised by Sturmfels in \[Stu2, Section 4\]. If it has a positive answer, then one can show that $`K[S]`$ is defined by binomials of degree $`e1`$.

Suppose now that $`P`$ is a normal lattice polytope of dimension $`d`$. Then the Castelnuovo-Mumford regularity of $`R=K[P]`$ has a very simple geometric description. In fact,

$$\mathrm{reg}(R)=d+1\mathrm{}$$

where $`\mathrm{}`$ is the minimal degree of a lattice point in the interior of $`C(P)`$. In particular, one always has $`\mathrm{reg}(A)d`$, and it follows that the ideal $`I=I_{S_P}`$ is generated by binomials of degree $`d+1`$. It easily seen that the bound $`d+1`$ is attained if $`P`$ is a simplex (i.e. spanned by $`d+1`$ lattice points) with at least one lattice point in its interior, but no lattice points in its boundary different from its vertices. However, no counterexample seems to be known to the following question:

###### Problem 12.

Let $`P`$ a normal lattice polytope of dimension $`d`$ whose boundary contains at least $`d+2`$ lattice points. Is $`K[P]`$ defined by binomials of degree $`d`$?

Clearly the answer is “yes” if $`P`$ has no interior lattice point, and as we have seen in the previous section, it is also “yes” for $`d=2`$ since for $`d=2`$ one can even find a Gröbner basis of $`I`$ of binomials of degree $`2`$ if $`P`$ contains at least $`4`$ lattice points in its boundary. As far as the combinatorics of triangulations is concerned, the result can be extended to higher dimension. In fact, one has the following theorem (\[BGT, 3.3.1\])

###### Theorem 5.4.1.

Let $`P`$ be a lattice polytope of dimension $`d`$ with at least $`d+2`$ lattice points in its boundary and at least one interior lattice point. Then $`P`$ has a regular triangulation $`\mathrm{\Delta }`$ into empty lattice simplices such that the minimal non-faces of $`\mathrm{\Delta }`$ have dimension $`d1`$.

Since one cannot expect the triangulation to be unimodular for $`d3`$, the theorem only bounds the degree of the generators of $`\sqrt{\mathrm{in}(I)}`$. Nevertheless, one should strengthen the last problem as follows:

###### Problem 13.

Let $`P`$ a normal lattice polytope of dimension $`d`$ whose boundary contains at least $`d+2`$ lattice points. Does $`I_{S_P}`$ have a Gröbner basis consisting of binomials of degree $`d`$?

We would like to mention that Sturmfels already raised in \[Stu2\] the conjecture that for any normal lattice polytope of dimension $`d`$, there exists a Gröbner basis for $`I_{S_P}`$ consisting of binomials of degree $`d+1`$. There one can find some interesting problems on the maximal degree of the defining equations and the regularity of toric ideals.


format: text

text:
# The operation threshold of a double barrier phonon laser

## 1 Introduction

Sasers are devices capable of producing beams of coherent phonons. Besides the system considered here, several other kinds of such devices were proposed and constructed .

In recent works  the kinetics and the dynamical properties of the double barrier phonon laser were discussed. In this paper we study the system from a point of view close to that used in quantum optics to study the onset of the lasing regime. In spite of the fact that the system is far from equilibrium and thus concepts like temperature and chemical potential can not be applied, the process is analogous to a phase transition . This transition is not governed by temperature but an energy flux (in this case by the injection rate of primary longitudinal optical $`LO_1`$ phonons). We were able to obtain the potential that describes the states of our system and consequently, the threshold value for the coherent transversal acoustic ($`TA`$) phonon emission.

The paper is organized as follows. A description of the saser device is presented in section 2. The multimode case is analyzed in section 3. In section 4 the potential that describes our system is obtained. Finally, in section 5 we present our results and conclusions.

## 2 The system

The phonon laser studied here consists of an AlGaAs/GaAs double-barrier heterostructure (DBH). This device was designed in such a way that, for a small applied bias $`V`$, the difference $`\mathrm{\Delta }\epsilon `$ between the first excited level $`\epsilon _1`$ and the ground state $`\epsilon _0`$ in the well is less than the longitudinal optical ($`LO_1`$) phonon energy $`\mathrm{}\omega _1`$. For a greater bias the resonant condition $`\mathrm{\Delta }\epsilon \mathrm{}\omega _1`$ is achieved and the electrons begin to decay to the ground state by emitting primary $`LO_1`$ phonons. For an $`Al`$ concentration greater than $`0.25`$  or $`0.3`$ , these phonons are confined inside the well (they can be also absorbed by exciting electrons from $`\epsilon _0`$ to $`\epsilon _1`$).

The process described above, acts in parallel with the decay of primary $`LO_1`$ phonons due to anharmonicity. One of the products of this decay is a secondary longitudinal optical phonon ($`LO_2`$), the other is a $`TA`$ phonon . The $`LO_2`$-$`TA`$ pair is produced by stimulated emission. Therefore these $`TA`$ phonons could be coherent and form a beam that it is called saser by analogy with a laser.

The DBH saser beam could be applied to acoustic nanoscopy, phonoelectronics and phonolitography. This was discussed in more detail in a previous article .

The potential profile and the level positions at the resonant condition are shown in figure 1.

## 3 The multimode case

The fundamental mechanism in this saser is the generation of the $`TA`$ phonons due to the decay of primary $`LO_1`$ phonons. Therefore, the other processes (i.e., emission-absorption of the $`LO_1`$ phonon through electron transitions and the $`LO_2`$ phonon decay) are secondary and are taken into account just as a result of the interaction of each phonon with its reservoir.

As the $`TA`$ phonon emission results from the decay of $`LO_1`$ phonons, they could be emitted in many modes, corresponding to the different values of its wave vector $`𝐪_3`$ parallel to the interface.

The number $`N_{𝐪_3}`$ of wave vectors parallel to the interface can be estimated as $`N_{𝐪_3}S_0/a^2`$, where $`S_0`$ is the device area and $`a`$ is the lattice parameter. For the values used here, $`S_0=0.510^3mm^2`$ and $`a=2.825`$ Å, $`N_{𝐪_3}`$ is of the order of $`710^9`$. The total number of emitted $`TA`$ phonons is $`210^4`$ , which means that, at the beginning of the phonon emission, the number of phonons per wave vector $`𝐪_3`$ is $`310^6`$. As the applied bias increases, the emission in a particular mode called $`𝐪_3^0`$ grow slowly until a certain threshold value $`V=V_{th}`$ is reached. For values of $`V`$ greater than $`V_{th}`$, the phonons in that mode are emitted in a coherent way implying that the population $`n_{𝐪_3^0}`$ is the only one macroscopically non zero. In this section, the possibility of macroscopically coexistence of more than one mode is studied.

### 3.1 The Hamiltonian

The Hamiltonian that describes our system can be written as:

$`=`$ $`\mathrm{}\omega _1{\displaystyle \underset{𝐪_1}{}}b_{𝐪_1}^{}b_{𝐪_1}+\mathrm{}\omega _2{\displaystyle \underset{𝐪_2}{}}b_{𝐪_2}^{}b_{𝐪_2}+\mathrm{}\omega _3{\displaystyle \underset{𝐪_3}{}}b_{𝐪_3}^{}b_{𝐪_3}+`$ (1)
$`\mathrm{}\gamma {\displaystyle \underset{𝐪_1,𝐪_2,𝐪_3}{}}\left(b_{𝐪_1}^{}b_{𝐪_2}b_{𝐪_3}+b_{𝐪_1}b_{𝐪_2}^{}b_{𝐪_3}^{}\right),`$
where $`𝐪_1`$, $`𝐪_2`$ and $`𝐪_3`$ are respectively the $`LO_1`$, $`LO_2`$ and $`TA`$ wave vectors parallel to the interfaces, and must satisfy $`𝐪_1=𝐪_2+𝐪_3`$, $`\mathrm{}\omega _i`$ $`(i=1,2,3)`$ are the energies of each kind of phonons and $`\gamma `$ is the phonon-phonon interaction coefficient.

#### 3.1.1 The Langevin equations

The equations of motion for the operators $`n_{𝐪_1}`$ ($`n_{𝐪_i}=b_{𝐪_i}^{}b_{𝐪_i}`$), $`b_{𝐪_2}`$, $`b_{𝐪_3}`$ are obtained from the Hamiltonian (1). We remark that the saser system is coupled to reservoirs. The $`LO_1`$ phonons are coupled through the emission and absorption processes to the electron system. In the case of the $`LO_2`$ phonons, they are coupled to the other phonon modes to which they decay, whereas the $`TA`$ phonons are connected to the other $`TA`$ phonon modes outside the well. Thus the total Hamiltonian includes, besides the terms shown in equation (1), the interaction with the reservoirs. By using the methods described in references , the reservoir coordinates can be eliminated leading to the following Langevin equations

$`{\displaystyle \frac{dn_{𝐪_1}}{dt}}`$ $`=`$ $`i\gamma {\displaystyle \underset{𝐪_2,𝐪_3}{}}\left\{b_{𝐪_1}^{}b_{𝐪_2}b_{𝐪_3}b_{𝐪_1}b_{𝐪_2}^{}b_{𝐪_3}^{}\right\}+G_{𝐪_1}\mathrm{\Gamma }_1n_{𝐪_1}+\widehat{F}_1,`$ (2)
$`{\displaystyle \frac{db_{𝐪_2}}{dt}}`$ $`=`$ $`(i\omega _2+\kappa _2)b_{𝐪_2}i\gamma {\displaystyle \underset{𝐪_1,𝐪_3}{}}b_{𝐪_1}b_{𝐪_3}^{}+\widehat{F}_2,`$ (3)
$`{\displaystyle \frac{db_{𝐪_3}}{dt}}`$ $`=`$ $`(i\omega _3+\kappa _{𝐪_3})b_{𝐪_3}i\gamma {\displaystyle \underset{𝐪_1,𝐪_2}{}}b_{𝐪_1}b_{𝐪_2}^{}+\widehat{F}_3,`$ (4)
where $`G_{𝐪_1}`$ and $`\mathrm{\Gamma }_1`$ are the emission and absorption rates for the $`LO_1`$ phonons due the interaction with its reservoir (i.e., the electrons), $`\kappa _2`$ is the decay rate of $`LO_2`$ phonons, $`\kappa _{𝐪_3}`$ is the escape rate of the $`TA`$ phonons and $`\widehat{F}_i(i=1,2,3)`$ are the fluctuation forces. The $`TA`$ phonons escape rate is different for each mode, thus depending on $`𝐪_3`$. As we are not interested in studying the statistical properties of the saser, in the following the fluctuation forces will not be considered.

In order to obtain only one equation for the $`TA`$ phonons, we make the adiabatic approximation in equations (2) and (3). First we replace $`b_{𝐪_1}\left(t\right)=\stackrel{~}{b}_{𝐪_1}\left(t\right)e^{i\omega _1t}`$ and $`b_{𝐪_3}\left(t\right)=\stackrel{~}{b}_{𝐪_3}\left(t\right)e^{i\omega _3t}`$ in (3). Secondly, we integrate (3) explicitly to get

$$b_{𝐪_2}=i\gamma \underset{𝐪_1,𝐪_3}{}\underset{\mathrm{}}{\overset{t}{}}e^{\left[i\left(\omega _1\omega _2\omega _3\right)+\kappa _2\right]\left(t\tau \right)}\left(\stackrel{~}{b}_{𝐪_1}\stackrel{~}{b}_{𝐪_3}^{}\right)_\tau 𝑑\tau .$$
(5)
Assuming that the relaxation time of the $`b_{𝐪_2}`$ phonons is much smaller than the relaxation of $`\stackrel{~}{b}_{𝐪_1}`$ and $`\stackrel{~}{b}_{𝐪_3}^{}`$, we can take $`\stackrel{~}{b}_{𝐪_1}\stackrel{~}{b}_{𝐪_3}^{}`$ out of the integral in equation (5) obtaining

$$b_{𝐪_2}=i\gamma \underset{𝐪_1,𝐪_3}{}\frac{e^{i\left(\omega _1\omega _3\right)t}}{i\nu +\kappa _2}\stackrel{~}{b}_{𝐪_1}\stackrel{~}{b}_{𝐪_3}^{},$$
(6)
where $`\nu =\omega _1\omega _2\omega _3`$.

In a similar way, we obtain for $`n_{𝐪_1}`$

$$n_{𝐪_1}=\frac{G_{𝐪_1}}{\mathrm{\Gamma }_1}\left(1\frac{\mathrm{\Omega }}{\mathrm{\Gamma }_1}\underset{𝐪_3}{}n_{𝐪_3}\right),$$
(7)
where

$$\mathrm{\Omega }=\frac{2\gamma ^2\kappa _2}{\nu ^2+\kappa _2^2}.$$

Finally, we replace (6) and (7) in (4) and we get, after some manipulations, an equation for the $`TA`$ phonon populations

$$\frac{dn_{𝐪_3}}{dt}=(\mathrm{\Omega }n_12\kappa _{𝐪_3})n_{𝐪_3},$$
(8)
where $`n_1=\underset{𝐪_1}{}n_{𝐪_1}`$.

Considering as an example only two modes, $`𝐪_3^0`$ and $`𝐪_3^1`$, we get for the stationary case of equation (8):

$`n_3^0\left(\mathrm{\Omega }n_12\kappa _3^0\right)=0,`$ (9)
$`n_3^1\left(\mathrm{\Omega }n_12\kappa _3^1\right)=0.`$ (10)
If both modes would be present, ($`n_3^00`$ and $`n_3^10`$) both parenthesis in (9) and (10) would be zero. This is a contradiction (because $`\kappa _3^0\kappa _3^1`$). This contradiction only can be solved if just one mode is present and the other one has died out. Therefore, only a single mode, the one with largest lifetime inside the well and closest to resonance, survives. The former analysis also can be done quite rigorously for many modes.

When the $`LO_1`$ decay, the $`TA`$ phonons are emitted in the \[$`111`$\] direction . The device is grown in this direction, such that the $`TA`$ phonon beam will make multiple reflections between the walls of the well, implying in large lifetime for these phonons. Indeed, for a small applied bias, the $`TA`$ phonons are emitted with any wave vector $`𝐪_3`$. In this regime, the device works as a sound emitting diode (SED). With a further increase in the applied potential, when a certain value of $`V`$ is reached, the $`TA`$ phonon distribution on $`𝐪_3`$ become more and more sharp giving place to a phase transition. In this case $`n_3^0`$ grows suddenly from about $`10^6`$ to about $`10^4`$. Thus, a great number of $`TA`$ phonons would have only one mode: $`𝐪_3^0=0`$ (which imply $`𝐪_1=𝐪_2`$). This mode will survive and slave the others, making the system to self-organize and emit just in this mode.

## 4 The single mode case

In order to get the threshold for which $`n_3^0`$ begins to be macroscopically non zero, we must first obtain an equation for the amplitude of the single mode $`b_3^0`$ that slaves the system. To do that, we make the same approximations as described in the previous section. The equation obtained for $`b_3^0`$ is

$$\frac{db_3}{dt}=\left(\frac{\gamma ^2}{\mathrm{\Gamma }_1\kappa _2}G_1\kappa _3\right)b_3^02G_1\left(\frac{\gamma ^2}{\mathrm{\Gamma }_1\kappa _2}\right)^2b_{3}^{0}{}_{}{}^{}b_3^0b_3^0,$$
(11)
where $`G_1=\underset{𝐪_1}{}G_{𝐪_1}`$.

The right-hand side of (11) can be obtained from the potential:

$$U_c\left(b_3^0\right)=\alpha \left|b_3^0\right|^2+\beta \left|b_3^0\right|^4,$$
(12)
with

$$\alpha =\kappa _3\frac{\gamma ^2}{\mathrm{\Gamma }_1\kappa _2}G_1,\beta =G_1\left(\frac{\gamma ^2}{\mathrm{\Gamma }_1\kappa _2}\right)^2,$$

such that

$$\frac{db_3^0}{dt}=\frac{dU_c\left(b_3^0\right)}{db_3^{}}.$$
(13)
The expressions for the parameters $`G_1`$ and $`\mathrm{\Gamma }_1`$ are

$$\mathrm{\Gamma }_1=w\left(N_0N_1\right),G_1=wN_1.$$

where $`w`$ is the electron transition rate and $`N_0`$ and $`N_1`$ are respectively the electron populations of the fundamental and excited levels.

The shape of the potential (12) is similar to that obtained in the Ginzburg-Landau phase transition theory. For $`\alpha >0`$ the potential has a minimum at $`n_3^0=0`$ ($`n_3^0=\left|b_3^0\right|^2`$). In the case of $`\alpha <0`$, the minimum is obtained for $`n_3^00`$. The transition from $`\alpha >0`$ to $`\alpha <0`$ is due to the competition between processes of gain, with a rate $`G_1\frac{\gamma ^2}{\mathrm{\Gamma }_1\kappa _2}`$ and losses, with a rate $`\kappa _3`$. The threshold is attained when $`\alpha =0`$, i.e., $`G_1=\frac{\mathrm{\Gamma }_1\kappa _2\kappa _3}{\gamma ^2}`$.

## 5 Results and Conclusions

The parameters used in our calculation are: the escape rate of $`TA`$ phonons $`\kappa _3^0=0.05ps^1`$, estimated from its group velocity near the $`L`$ point of the Brillouin zone, the decay rate of the $`LO_2`$ phonons $`\kappa _2=20ps^1`$ (by assuming a small stimulated decay) and the phonon-phonon interaction coefficient $`\gamma =0.5ps^1`$ calculated in reference  following the work of Klemens . The decay rate $`\gamma _0`$ obtained from this value is in agreement with the experimental result of Vallée . The values of $`G_1`$ and $`\mathrm{\Gamma }_1`$ depend on the $`LO_1`$ phonon emission rate $`w`$ and on the electron populations $`N_0`$ and $`N_1`$ that were calculated in reference  by solving the kinetic equations.

The total generation rate of the $`LO_1`$ phonons $`G_1`$, depends on the applied bias $`V`$ (i.e., it turns out from electron transitions that are $`V`$ dependent ). Thus, the applied bias is the external parameter that control the intensity of the saser emission.

In figure 2, the potential (12) is plotted as a function of the $`TA`$ phonon amplitude for different values of the applied bias $`V`$. As it can be seen, for $`V>V_{th}=59.4mV`$ this potential has different minima for different values of $`V`$. These minima represent the stable points $`b_3^s`$ of the system.

In figure 3 the stable points are plotted as function of $`V`$. The solid line represents the $`n_3^s`$ calculated in this work. The dashed line is the $`TA`$ phonon population calculated in a previous work from the kinetic equations .

Figure 4 shows a comparison in the region where the $`TA`$ generation begins (dashed region in figure 3). From this comparison two conclusions arise. First, as it can be seen (solid line), the $`TA`$ coherent emission does not start until a certain threshold of the applied bias is reached. At $`V_{th}`$ the $`LO_1`$ emission rate $`G_1`$ is of the order of $`279ps^1`$ and the total $`TA`$ phonon population $`n_3`$ is $`4658`$, whereas $`n_3^s=0`$. The $`TA`$ phonons generated for a bias greater than $`V_{th}`$ are coherent. Secondly, our previous calculations , even without considering the self-organization process, gave results that agree quite well with those presented here. This results show that the coherent emission occurs immediately after the condition of $`LO_1`$ phonon emission is reached. That means that it is not necessary a big “optical” pumping to get a sasing region. In summary, we show in this work that the $`TA`$ phonons, produced by stimulated emission, constitute a coherent phonon beam in the parameter region discussed above.