Semigroup generators and Cones

Question

In $\mathbb{R}^2$, let $C$ be the cone (non-negative linear combinations) on the two vectors $$ v_1=\begin{pmatrix} 1 \\ 0 \end{pmatrix}, \quad v_2=\begin{pmatrix} 2 \\ 3 \end{pmatrix} $$

Consider the semigroup $S=C\cap\Bbb{Z}^2$. I want to find a generating set for $S$ (as $\Bbb{Z}$-module).

Clearly $v_1$ and $v_2$ are not enough since they do not generate $v_3=(1,1)$. Intuitively it is clear to me that $v_1,v_2,v_3$ is a good set of generators, but I am not sure how to show that. Any hint?

Also, are there some general results (minimality, etc.) for finding generators for these kind of "semi-lattices" ?

Answer 1

I'll share a possible answer to this that I found in the proof of Gordan's Lemma.

In its proof [see Fulton, Toric Varieties] it is shown that a generating set for $S$ is contained in the (finite) set $ \Bbb{Z}^d \cap \{\sum \ t_i v_i: \ 0\leq t_i\leq 1\} $ where $v_1,\dots,v_d$ are the generators of the cone.

(geometrically they are the integer-points inside the parallelogram spanned by the vectors $v_i$).

For example in our case one has to solve the following system: $$ t_1v_1+t_2v_2= \begin{pmatrix} t_1+2t_2 \\ 3t_2 \end{pmatrix} \in \Bbb{Z}^2, \quad 0\leq t_i\leq 1 $$ which gives $v_1, v_2$ and $v_3=(1,1)$ as a set of $\Bbb{Z}$-independent solutions.

Answer 2

This is related to the Frobenius coin-change problem, but in higher dimensions. The traditional such problem is to find maximal elements in $S$ but not in the semigroup generated by the generating set ($\{v_1,v_2\}$ in your example). Some progress on that question appears in author link.

Your question is to find a generating set for the cone. To my knowledge not a lot is known, but for non-simplicial cones the problem can be tricky. In $\mathbb{R}^2$, all cones are simplicial, but in $\mathbb{R}^3$, you can have four generators and the cone has a roughly square cross-section. To get the elements of $S$ near the four faces of the cone may require a lot of additional vectors.

Answer 3

You may find an useful information in the paper

J. Amos, I. Pascu, V. Ponomarenko, E. Treviño, Yan Zhang, The multidimensional Frobenius problem, INVOLVE 4:2(2011)

and references in it.