El lema de Gordon

El lema de Gordan es un lema en geometría convexa y geometría algebraica . Se puede expresar de varias maneras.

• Sea una matriz de números enteros. Sea el conjunto de soluciones enteras no negativas de . Entonces existe un subconjunto finito de vectores en , tal que cada elemento de es una combinación lineal de estos vectores con coeficientes enteros no negativos. ^[1] ${\displaystyle A}$ ${\displaystyle M}$ ${\displaystyle A\cdot x=0}$ ${\displaystyle M}$ ${\displaystyle M}$
• El semigrupo de puntos integrales en un cono poliédrico convexo racional se genera de forma finita. ^[2]
• Una variedad tórica afín es una variedad algebraica (esto se deriva del hecho de que el espectro primo del álgebra de semigrupos de dicho semigrupo es, por definición, una variedad tórica afín ).

El lema lleva el nombre del matemático Paul Gordan (1837-1912). Algunos autores lo han escrito mal como "lema de Gordon".

Pruebas

Hay pruebas topológicas y algebraicas.

Prueba topológica

Sea el cono dual del cono poliédrico racional dado. Sean vectores integrales de modo que Entonces generen el cono dual ; de hecho, escribiendo C para el cono generado por 's, tenemos: , que debe ser la igualdad. Ahora bien, si x está en el semigrupo ${\displaystyle \sigma }$ ${\displaystyle u_{1},\dots ,u_{r}}$ ${\displaystyle \sigma =\{x\mid \langle u_{i},x\rangle \geq 0,1\leq i\leq r\}.}$ ${\displaystyle u_{i}}$ ${\displaystyle \sigma ^{\vee }}$ ${\displaystyle u_{i}}$ ${\displaystyle \sigma \subset C^{\vee }}$

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

entonces se puede escribir como

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

donde son números enteros no negativos y . Pero como x y la primera suma del lado derecho son integrales, la segunda suma es un punto de red en una región acotada, por lo que sólo hay un número finito de posibilidades para la segunda suma (la razón topológica). Por tanto, se genera de forma finita. ${\displaystyle n_{i}}$ ${\displaystyle 0\leq r_{i}\leq 1}$ ${\displaystyle S_{\sigma }}$

prueba algebraica

La prueba ^[3] se basa en el hecho de que un semigrupo S se genera finitamente si y sólo si su álgebra de semigrupo es un álgebra generada finitamente sobre . Para probar el lema de Gordan, por inducción (cf. la prueba anterior), basta con probar la siguiente afirmación: para cualquier subsemigrupo unital S de , ${\displaystyle \mathbb {C} [S]}$ ${\displaystyle \mathbb {C} }$ ${\displaystyle \mathbb {Z} ^{d}}$

Si S se genera de forma finita, entonces v , un vector integral, se genera de forma finita. ${\displaystyle S^{+}=S\cap \{x\mid \langle x,v\rangle \geq 0\}}$

Put , que tiene una base . Tiene una calificación dada por ${\displaystyle A=\mathbb {C} [S]}$ ${\displaystyle \chi ^{a},\,a\in S}$ ${\displaystyle \mathbb {Z} }$

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

Por suposición, A se genera de forma finita y, por tanto, es noetheriano. Del siguiente lema algebraico se deduce que es un álgebra generada finitamente . Ahora bien, el semigrupo es la imagen de S bajo una proyección lineal, por lo que se genera de forma finita y, por lo tanto, se genera de forma finita. Por tanto, se genera de forma finita. ${\displaystyle \mathbb {C} [S^{+}]=\oplus _{0}^{\infty }A_{n}}$ ${\displaystyle A_{0}}$ ${\displaystyle S_{0}=S\cap \{x\mid \langle x,v\rangle =0\}}$ ${\displaystyle A_{0}=\mathbb {C} [S_{0}]}$ ${\displaystyle S^{+}}$

Lema : Sea A un anillo graduado. Si A es un anillo noetheriano, entonces es un álgebra generada finitamente . ${\displaystyle \mathbb {Z} }$ ${\displaystyle A^{+}=\oplus _{0}^{\infty }A_{n}}$ ${\displaystyle A_{0}}$

Prueba: Sea I el ideal de A generado por todos los elementos homogéneos de A de grado positivo. Dado que A es noetheriano, I en realidad es generado por un número finito de homogéneos de grado positivo. Si f es homogénea de grado positivo, entonces podemos escribir con homogénea. Si f tiene un grado suficientemente grande, entonces cada uno tiene un grado positivo y estrictamente menor que el de f . Además, cada pieza de grado es un módulo generado de forma finita. (Prueba: Sea una cadena creciente de submódulos finitamente generados de con unión . Entonces la cadena de los ideales se estabiliza en pasos finitos; también lo hace la cadena ) Así, por inducción en grado, vemos que es un -álgebra finitamente generada . ${\displaystyle f_{i}'s}$ ${\textstyle f=\sum _{i}g_{i}f_{i}}$ ${\displaystyle g_{i}}$ ${\displaystyle g_{i}}$ ${\displaystyle A_{n}}$ ${\displaystyle A_{0}}$ ${\displaystyle N_{i}}$ ${\displaystyle A_{n}}$ ${\displaystyle A_{n}}$ ${\displaystyle N_{i}A}$ ${\displaystyle N_{i}=N_{i}A\cap A_{n}.}$ ${\displaystyle A^{+}}$ ${\displaystyle A_{0}}$

Aplicaciones

Un multihipergrafo sobre un determinado conjunto es un multiconjunto de subconjuntos de (se llama "multihipergrafo" ya que cada hiperborde puede aparecer más de una vez). Un hipergrafo múltiple se llama regular si todos los vértices tienen el mismo grado . Se llama descomponible si tiene un subconjunto adecuado no vacío que también sea regular. Para cualquier número entero n , sea el grado máximo de un hipergrafo múltiple indescomponible en n vértices. El lema de Gordon implica que es finito. ^[1] Prueba : para cada subconjunto S de vértices, defina una variable x _S (un número entero no negativo). Defina otra variable d (un número entero no negativo). Considere el siguiente conjunto de n ecuaciones (una ecuación por vértice): Cada solución ( x , d ) denota múltiples hipergrafos regulares en , donde x define los hiperbordes y d es el grado. Según el lema de Gordan, el conjunto de soluciones es generado por un conjunto finito de soluciones, es decir, hay un conjunto finito de multihipergrafos, de modo que cada multihipergrafo regular es una combinación lineal de algunos elementos de . Cada multihipergrafo no descomponible debe estar en (ya que, por definición, no puede ser generado por otro multihipergrafo). Por tanto, el conjunto de multihipergrafos no descomponibles es finito. ${\displaystyle V}$ ${\displaystyle V}$ ${\displaystyle D(n)}$ ${\displaystyle D(n)}$ $${\displaystyle \sum _{S\ni v}x_{S}-d=0{\text{ for all }}v\in V}$$ ${\displaystyle V}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$

Ver también

• El algoritmo de Birkhoff es un algoritmo que, dada una matriz bistocástica (una matriz que resuelve un conjunto particular de ecuaciones), encuentra una descomposición de la misma en matrices integrales. Está relacionado con el lema de Gordon en que muestra que el conjunto de estas matrices es generado por un conjunto finito de matrices integrales.

Referencias

1. Alon, N; Berman, KA (1 de septiembre de 1986). "Hipergrafos regulares, lema de Gordon, lema de Steinitz y teoría invariante". Revista de teoría combinatoria, serie A. 43 (1): 91–97. doi : 10.1016/0097-3165(86)90026-9 . ISSN  0097-3165.
2. David A. Cox, Conferencias sobre variedades tóricas. Conferencia 1. Proposición 1.11.
3. Bruns, Winfried; Gubeladze, José (2009). Politopos, anillos y teoría K. Monografías de Springer en Matemáticas. Saltador. doi :10.1007/b105283. ISBN  978-0-387-76355-2., Lema 4.12.

Ver también

• Lema de Dickson