I'm trying to solve an exercise in Fulton's book on toric varieties, and have reduced it to the following:

Let $M$ be a lattice of rank $n$ with $M \otimes \mathbb{R} = V$, and $S$ be a finitely generated semigroup of $M$, such that the following conditions hold:

i) S is saturated. (If $v \in M, n \in \mathbb{Z}_{> 0}$ with $nv \in S$, then $v \in S$.)

ii) S generates M as a group.

Then the lattice points inside the real cone on $S$ are simply the integer cone on $S$.

In other words, given a saturated semigroup $S=\langle v_1,\dots,v_k\rangle_{\mathbb{Z}_{\geq 0}}$ with $S=\langle v_1,\dots,v_k\rangle_{\mathbb{Z}} = M$, then $\langle v_1,\dots,v_k\rangle_{\mathbb{R}_{\geq 0}}\cap M = S$. This seems geometrically obvious, but I can't find a way to prove it.

I can prove the result if $\langle v_1,\dots,v_k\rangle_{\mathbb{R}_{\geq 0}}\cap M=\langle v_1,\dots,v_k\rangle_{\mathbb{Q}_{\geq 0}}\cap M$ using the saturatedness of $S$, the problem is showing that any positve real linear combination of the $v_i$ lying in the lattice can also be written as a positive rational combination.

Thinking about the different ways to represent the same vector, we see that finding $r=(r_1,\dots,r_k)$ such that $\sum r_iv_i = v$ is equivalent to saying that $r$ is a solution to the matrix equation:

$$\bigg(v_1 \dots v_k \bigg)x=v $$

The solutions to this equation are either an empty set, of an affine subspace of $\mathbb{R}^k$. But if $v$ is in the intersection we're lookinh at, we know that the solution space contains a "positive" point, i.e. a point of $(\mathbb{R}_{\geq 0})^k$, and an "integer" point, i.e. a point of $\mathbb{Z}^k$. I'd like to use this somehow to show that it also contains a positive rational point, which is easy enough if the positive point lies in the strict interior of the set of positive points, but seems like it could be impossible in some examples, such as if the solution space is an affine line running tangent to the set of positive points, so I'm not sure if this approach will work...

  • 1
    $\begingroup$ You want to prove that if a given system of linear equations (in finitely many variables, with rational coefficients) has a solution in nonnegative reals, then it has a solution in nonnegative rationals. This is a particular case of the fact that if a given system of linear inequalities (in finitely many variables, with rational coefficients) has a solution in reals, then it has a solution in rationals. And this follows from the fact that such systems can be solved algorithmically using rational computations (e.g., by the Fourier-Motzkin algorithm). $\endgroup$ Apr 28, 2016 at 0:08

1 Answer 1


The question you ask (which is a variation on the theme of Gordan's lemma) appears exactly (and with almost exactly the same notations) as the "conversely" part of proposition 1.1 on page 3 in Tadao Oda's Convex Bodies and Algebraic Geometry (An Introduction to the Theory of Toric Varieties) (Springer 1985).

The key point is that if $v$ belongs to the convex cone $\rho$ generated by $v_1,\ldots,v_k$, then in fact there are $n$ among the $v_i$ (where $n = \dim\langle v_1,\ldots,v_k\rangle_{\mathbb{R}}$), say w.l.o.g. $v_1,\ldots,v_n$, linearly independent over $\mathbb{R}$, such that in fact $v$ belongs to the convex cone $\rho'$ generated by $v_1,\ldots,v_n$. This is Carathéodory's theorem (the version on Wikipedia doesn't say exactly the same thing, but the proof given there works). But now the coefficients $r_1,\ldots,r_n$ of $v \in M\cap\rho'$ on the $v_1,\ldots,v_n$ are uniquely determined, so the question is trivial: they are rational because $v \in M$ (and $v_1,\ldots,v_n$ generate $M\otimes\mathbb{Q}$ over the rationals) and nonnegative because $v \in \rho'$. And since $S$ is saturated, we can get nonnegative integer coefficients.

Edit: Following OP's comment, let me spell out the argument why $v_1,\ldots,v_n$ generate $M\otimes\mathbb{Q}$. They are in $M\otimes\mathbb{Q}$ and linearly independent over $\mathbb{R}$ (this follows from the proof of Carathéodory's theorem, although people usually forget to put this in the statement for some reason); so in particular, they are linearly independent over $\mathbb{Q}$. But $M\otimes\mathbb{Q}$ has dimension $n$ as a $\mathbb{Q}$-vector space (because the rank of $M$ as a free $\mathbb{Z}$-module is the rank of $M\otimes\mathbb{Q}$ as a $\mathbb{Q}$-vector space or of $M\otimes\mathbb{R}$ as an $\mathbb{R}$-vector space, and that is what we are calling $n$). So they are a basis of $M\otimes\mathbb{Q}$. This explains why the coefficients of $v$ on $v_1,\ldots,v_n$ are unique (and rational).

  • $\begingroup$ Thanks for the answer. I had thought about a reduction to this case, but the question then is why should $v_1, \dots v_n$ generate $M \otimes \mathbb{Q}$? The $\mathbb{R}$ basis you pick isn't guaranteed to be a basis for the lattice, so I think it still remains to prove either that $\langle v_1,\dots, v_n\rangle_{\mathbb{Q}} = M_{\mathbb{Q}}$, or $\langle v_1,\dots,v_k\rangle_{\mathbb{R}_{\geq 0}}\cap M_{\mathbb{Q}}=\langle v_1,\dots,v_k\rangle_{\mathbb{Q}_{\geq 0}}$, or something similar. $\endgroup$ May 2, 2016 at 17:18
  • $\begingroup$ @TomOldfield I added an argument explaining this in detail. $\endgroup$
    – Gro-Tsen
    May 2, 2016 at 17:35
  • $\begingroup$ @Oh, of course, it's just dimension counting, that was silly of me! I've been trying to avoid dimension counting when working with lattices since it's often misleading! I'll try and look at Cartheodory's theorem later today and then accept the answer when I can see how it works, thanks. $\endgroup$ May 2, 2016 at 17:44
  • $\begingroup$ The fact that I had initially written "and $v_1,\ldots,v_k$ generate $M\otimes\mathbb{Q}$ over the rationals" instead of "$v_1,\ldots,v_n$" probably didn't help either. $\endgroup$
    – Gro-Tsen
    May 2, 2016 at 17:50
  • $\begingroup$ @TomOldfield So, are you convinced? I find it a bit weird that Carathéodory's theorem is stated in terms of the number of vectors spanning the given points rather than their linear/affine independence, which seems a better conclusion in every respect, but that's really what the proof gives us. $\endgroup$
    – Gro-Tsen
    May 3, 2016 at 19:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .