Gordan's lemma
# Gordan's lemma

Gordan's lemma is a lemma in convex geometry and algebraic geometry. It can be stated in several ways.

* Let $A$ be a matrix of integers. Let $M$ be the set of non-negative integer solutions of $A\cdot x=0$. Then there exists a finite subset of vectors in $M$, such that every element of $M$ is a linear combination of these vectors with non-negative integer coefficients.
* The semigroup of integral points in a rational convex polyhedral cone is finitely generated.
* An affine toric variety is an algebraic variety (this follows from the fact that the prime spectrum of the semigroup algebra of such a semigroup is, by definition, an affine toric variety).

The lemma is named after the mathematician Paul Gordan (1837–1912). Some authors have misspelled it as "Gordon's lemma".

## Proofs

There are topological and algebraic proofs.

### Topological proof

Let $\sigma$ be the dual cone of the given rational polyhedral cone. Let $u_{1},\dots ,u_{r}$ be integral vectors so that $\sigma =\{x\mid \langle u_{i},x\rangle \geq 0,1\leq i\leq r\}.$ Then the $u_{i}$'s generate the dual cone $\sigma ^{\vee }$; indeed, writing C for the cone generated by $u_{i}$'s, we have: $\sigma \subset C^{\vee }$, which must be the equality. Now, if x is in the semigroup

    $S_{\sigma }=\sigma ^{\vee }\cap \mathbb {Z} ^{d},$

then it can be written as

    $x=\sum _{i}n_{i}u_{i}+\sum _{i}r_{i}u_{i},$

where $n_{i}$ are nonnegative integers and $0\leq r_{i}\leq 1$. But since x and the first sum on the right-hand side are integral, the second sum is a lattice point in a bounded region, and so there are only finitely many possibilities for the second sum (the topological reason). Hence, $S_{\sigma }$ is finitely generated.

### Algebraic proof

The proof is based on a fact that a semigroup S is finitely generated if and only if its semigroup algebra $\mathbb {C} [S]$ is a finitely generated algebra over $\mathbb {C}$. To prove Gordan's lemma, by induction (cf. the proof above), it is enough to prove the following statement: for any unital subsemigroup S of $\mathbb {Z} ^{d}$,

    If S is finitely generated, then $S^{+}=S\cap \{x\mid \langle x,v\rangle \geq 0\}$, v an integral vector, is finitely generated.

Put $A=\mathbb {C} [S]$, which has a basis $\chi ^{a},\,a\in S$. It has $\mathbb {Z}$-grading given by

    $A_{n}=\operatorname {span} \{\chi ^{a}\mid a\in S,\langle a,v\rangle =n\}$.

By assumption, A is finitely generated and thus is Noetherian. It follows from the algebraic lemma below that $\mathbb {C} [S^{+}]=\oplus _{0}^{\infty }A_{n}$ is a finitely generated algebra over $A_{0}$. Now, the semigroup $S_{0}=S\cap \{x\mid \langle x,v\rangle =0\}$ is the image of S under a linear projection, thus finitely generated and so $A_{0}=\mathbb {C} [S_{0}]$ is finitely generated. Hence, $S^{+}$ is finitely generated then.

Lemma: Let A be a $\mathbb {Z}$-graded ring. If A is a Noetherian ring, then $A^{+}=\oplus _{0}^{\infty }A_{n}$ is a finitely generated $A_{0}$-algebra.

Proof: Let I be the ideal of A generated by all homogeneous elements of A of positive degree. Since A is Noetherian, I is actually generated by finitely many $f_{i}'s$, homogeneous of positive degree. If f is homogeneous of positive degree, then we can write $f=∑_ig_if_i{\textstyle$ f=\sum _{i}g_{i}f_{i}} with $g_{i}$ homogeneous. If f has sufficiently large degree, then each $g_{i}$ has degree positive and strictly less than that of f. Also, each degree piece $A_{n}$ is a finitely generated $A_{0}$-module. (Proof: Let $N_{i}$ be an increasing chain of finitely generated submodules of $A_{n}$ with union $A_{n}$. Then the chain of the ideals $N_{i}A$ stabilizes in finite steps; so does the chain $N_{i}=N_{i}A\cap A_{n}.$) Thus, by induction on degree, we see $A^{+}$ is a finitely generated $A_{0}$-algebra.

## Applications

A multi-hypergraph over a certain set $V$ is a multiset of subsets of $V$ (it is called "multi-hypergraph" since each hyperedge may appear more than once). A multi-hypergraph is called regular if all vertices have the same degree. It is called decomposable if it has a proper nonempty subset that is regular too. For any integer n, let $D(n)$ be the maximum degree of an indecomposable multi-hypergraph on n vertices. Gordan's lemma implies that $D(n)$ is finite. Proof: for each subset S of vertices, define a variable $x_S$ (a non-negative integer). Define another variable d (a non-negative integer). Consider the following set of n equations (one equation per vertex):

$\sum _{S\ni v}x_{S}-d=0{\text{ for all }}v\in V$

Every solution (x,d) denotes a regular multi-hypergraphs on $V$, where x defines the hyperedges and d is the degree. By Gordan's lemma, the set of solutions is generated by a finite set of solutions, i.e., there is a finite set $M$ of multi-hypergraphs, such that each regular multi-hypergraph is a linear combination of some elements of $M$. Every non-decomposable multi-hypergraph must be in $M$ (since by definition, it cannot be generated by other multi-hypergraph). Hence, the set of non-decomposable multi-hypergraphs is finite.

