El lema de Gordon es un lema de geometría convexa y geometría algebraica . Se puede enunciar de varias maneras.
- DejarSea una matriz de enteros.sea el conjunto de soluciones enteras no negativas deEntonces existe un subconjunto finito de vectores en, de tal manera que cada elemento dees una combinación lineal de estos vectores con coeficientes enteros no negativos. [ 1 ]
- El semigrupo de puntos enteros en un cono poliédrico convexo racional es finitamente generado. [ 2 ]
- Una variedad tórica afín es una variedad algebraica (esto se deduce del hecho de que el espectro primo del álgebra de semigrupo de dicho semigrupo es, por definición, una variedad tórica afín ).
El lema recibe su nombre del matemático Paul Gordon (1837-1912). Algunos autores lo han escrito erróneamente como "el lema de Gordon".
Pruebas
Existen demostraciones topológicas y algebraicas.
Demostración topológica
DejarSea el cono dual del cono poliédrico racional dado.sean vectores enteros de modo queEntonces elgeneran el cono doble; de hecho, escribir C para el cono generado por's, tenemos:, que debe ser la igualdad. Ahora, si x está en el semigrupo
entonces se puede escribir como
dóndeson enteros no negativos y. Pero como x y la primera suma del lado derecho son enteros, la segunda suma es un punto de la red en una región acotada, y por lo tanto solo hay un número finito de posibilidades para la segunda suma (la razón topológica). Por lo tanto,es generado de forma finita.
Demostración algebraica
La demostración [ 3 ] se basa en el hecho de que un semigrupo S es finitamente generado si y solo si su álgebra de semigruposes un álgebra finitamente generada sobrePara demostrar el lema de Gordan, por inducción (véase la demostración anterior), basta con probar la siguiente afirmación: para cualquier subsemigrupo unitario S de,
- Si S es finitamente generado, entonces, v un vector integral, es finitamente generado.
Poner, que tiene una baseTiene-calificación otorgada por
- .
Por hipótesis, A es finitamente generado y, por lo tanto, es noetheriano. Del lema algebraico que se presenta a continuación se deduce quees un álgebra finitamente generada sobreAhora, el semigrupoes la imagen de S bajo una proyección lineal, por lo tanto, finitamente generada y asíes finitamente generado. Por lo tanto,entonces se genera de forma finita.
Lema : Sea A un- anillo graduado . Si A es un anillo noetheriano , entonceses un finito generado-álgebra.
Demostración: Sea I el ideal de A generado por todos los elementos homogéneos de A de grado positivo. Dado que A es noetheriano, I es generado en realidad por un número finito de elementos homogéneos de A., homogéneo de grado positivo. Si f es homogéneo de grado positivo, entonces podemos escribirconhomogéneo. Si f tiene un grado suficientemente grande, entonces cadatiene grado positivo y estrictamente menor que el de f . Además, cada pieza de gradoes un finito generado-módulo. (Prueba: Seaser una cadena creciente de submódulos generados finitamente decon unión. Luego la cadena de los idealesse estabiliza en pasos finitos; también lo hace la cadena) Así, por inducción sobre el grado, vemoses un finito generado-álgebra.
Aplicaciones
Un hipergrafo múltiple sobre un conjunto determinadoes un multiconjunto de subconjuntos de(Se denomina "multihipergrafo" ya que cada hiperarista puede aparecer más de una vez). Un multihipergrafo se denomina regular si todos sus vértices tienen el mismo grado . Se denomina descomponible si posee un subconjunto propio no vacío que también es regular. Para cualquier entero n , seaSea el grado máximo de un multihipergrafo indescomponible con n vértices. El lema de Gordon implica quees finito. [ 1 ] Demostración : para cada subconjunto S de vértices, definamos una variable x S (un entero no negativo). Definamos otra variable d (un entero no negativo). Consideremos el siguiente conjunto de n ecuaciones (una ecuación por vértice):Cada solución ( x , d ) denota un multihipergrafo regular endonde x define las hiperaristas y d es el grado. Por el lema de Gordon, el conjunto de soluciones está generado por un conjunto finito de soluciones, es decir, hay un conjunto finitode multihipergrafos, de tal manera que cada multihipergrafo regular es una combinación lineal de algunos elementos de. Todo multihipergrafo no descomponible debe estar en(ya que, por definición, no puede ser generado por otro multihipergrafo). Por lo tanto, el conjunto de multihipergrafos no descomponibles es finito.
Véase también
- El algoritmo de Birkhoff es un algoritmo que, dada una matriz biestocástica (una matriz que resuelve un conjunto particular de ecuaciones), encuentra su descomposición en matrices enteras. Está relacionado con el lema de Gordon, ya que demuestra que el conjunto de estas matrices se genera a partir de un conjunto finito de matrices enteras.
Referencias
- 1 2 Alon, N ; Berman, KA (1986-09-01). "Hipergrafos regulares, lema de Gordon, lema de Steinitz y teoría de invariantes" . Journal of Combinatorial Theory, Serie A . 43 (1): 91– 97. doi : 10.1016/0097-3165(86)90026-9 . ISSN 0097-3165 .
- ↑ David A. Cox, Lecciones sobre variedades tóricas . Lección 1. Proposición 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., Lema 4.12.
Véase también
- Lemas
- Teoremas en geometría convexa
- Geometría algebraica