Gordan's lemma

Last updated January 30, 2023

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.^[1]
The semigroup of integral points in a rational convex polyhedral cone is finitely generated.^[2]
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^[3] 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 ${\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.^[1]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.

Related Research Articles

In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.

<span class="mw-page-title-main">Generating set of a group</span> Abstract algebra concept

In abstract algebra, a generating set of a group is a subset of the group set such that every element of the group can be expressed as a combination of finitely many elements of the subset and their inverses.

In mathematics, in particular abstract algebra, a graded ring is a ring such that the underlying additive group is a direct sum of abelian groups $such that . The index set is usually the set of nonnegative integers or the set of integers, but can be any monoid. The direct sum decomposition is usually referred to as gradation or grading .$

In mathematics, homology is a general way of associating a sequence of algebraic objects, such as abelian groups or modules, with other mathematical objects such as topological spaces. Homology groups were originally defined in algebraic topology. Similar constructions are available in a wide variety of other contexts, such as abstract algebra, groups, Lie algebras, Galois theory, and algebraic geometry.

In abstract algebra, a Dedekind domain or Dedekind ring, named after Richard Dedekind, is an integral domain in which every nonzero proper ideal factors into a product of prime ideals. It can be shown that such a factorization is then necessarily unique up to the order of the factors. There are at least three other characterizations of Dedekind domains that are sometimes taken as the definition: see below.

In the mathematical field of real analysis, the monotone convergence theorem is any of a number of related theorems proving the convergence of monotonic sequences that are also bounded. Informally, the theorems state that if a sequence is increasing and bounded above by a supremum, then the sequence will converge to the supremum; in the same way, if a sequence is decreasing and is bounded below by an infimum, it will converge to the infimum.

In mathematics, particularly in functional analysis, the spectrum of a bounded linear operator is a generalisation of the set of eigenvalues of a matrix. Specifically, a complex number $is said to be in the spectrum of a bounded linear operator if$

<span class="mw-page-title-main">Representation of a Lie group</span> Group representation

In mathematics and theoretical physics, a representation of a Lie group is a linear action of a Lie group on a vector space. Equivalently, a representation is a smooth homomorphism of the group into the group of invertible operators on the vector space. Representations play an important role in the study of continuous symmetry. A great deal is known about such representations, a basic tool in their study being the use of the corresponding 'infinitesimal' representations of Lie algebras.

In transcendental number theory, the Lindemann–Weierstrass theorem is a result that is very useful in establishing the transcendence of numbers. It states the following:

In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem, and uses a specified set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing families of expander graphs.

<span class="mw-page-title-main">Burnside's theorem</span> Mathematic group theory

In mathematics, Burnside's theorem in group theory states that if G is a finite group of order $where p and q are prime numbers, and a and b are non-negative integers, then G is solvable. Hence each non-Abelian finite simple group has order divisible by at least three distinct primes.$

In mathematics, Stickelberger's theorem is a result of algebraic number theory, which gives some information about the Galois module structure of class groups of cyclotomic fields. A special case was first proven by Ernst Kummer (1847) while the general result is due to Ludwig Stickelberger (1890).

In measure theory, Carathéodory's extension theorem states that any pre-measure defined on a given ring of subsets R of a given set Ω can be extended to a measure on the σ-algebra generated by R, and this extension is unique if the pre-measure is σ-finite. Consequently, any pre-measure on a ring containing all intervals of real numbers can be extended to the Borel algebra of the set of real numbers. This is an extremely powerful result of measure theory, and leads, for example, to the Lebesgue measure.

In commutative algebra, an element b of a commutative ring B is said to be integral overA, a subring of B, if there are n ≥ 1 and a_j in A such that

In mathematics, the Artin–Rees lemma is a basic result about modules over a Noetherian ring, along with results such as the Hilbert basis theorem. It was proved in the 1950s in independent works by the mathematicians Emil Artin and David Rees; a special case was known to Oscar Zariski prior to their work.

In mathematics, an approximately finite-dimensional (AF) C*-algebra is a C*-algebra that is the inductive limit of a sequence of finite-dimensional C*-algebras. Approximate finite-dimensionality was first defined and described combinatorially by Ola Bratteli. Later, George A. Elliott gave a complete classification of AF algebras using the K₀ functor whose range consists of ordered abelian groups with sufficiently nice order structure.

In the theory of partial differential equations, Holmgren's uniqueness theorem, or simply Holmgren's theorem, named after the Swedish mathematician Erik Albert Holmgren (1873–1943), is a uniqueness result for linear partial differential equations with real analytic coefficients.

In algebra and number theory, a distribution is a function on a system of finite sets into an abelian group which is analogous to an integral: it is thus the algebraic analogue of a distribution in the sense of generalised function.

In abstract algebra, a branch of mathematics, an affine monoid is a commutative monoid that is finitely generated, and is isomorphic to a submonoid of a free abelian group $. Affine monoids are closely connected to convex polyhedra, and their associated algebras are of much use in the algebraic study of these geometric objects.$

This is a glossary for the terminology in a mathematical field of functional analysis.

References

1 2 Alon, N; Berman, K.A (1986-09-01). "Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory". Journal of Combinatorial Theory, Series A. 43 (1): 91–97. doi: 10.1016/0097-3165(86)90026-9 . ISSN 0097-3165.
↑ David A. Cox, Lectures on toric varieties. Lecture 1. Proposition 1.11.
↑ Bruns, Winfried; Gubeladze, Joseph (2009). Polytopes, rings, and K-theory. Springer Monographs in Mathematics. Springer. doi:10.1007/b105283. ISBN 978-0-387-76355-2., Lemma 4.12.