En matemáticas , un politopo integral tiene un polinomio de Ehrhart asociado que codifica la relación entre el volumen de un politopo y el número de puntos enteros que contiene el politopo. La teoría de los polinomios de Ehrhart puede verse como una generalización de dimensiones superiores del teorema de Pick en el plano euclidiano .
Estos polinomios llevan el nombre de Eugène Ehrhart, quien los estudió en la década de 1960.
Definición
De manera informal, si P es un politopo y tP es el politopo formado al expandir P por un factor de t en cada dimensión, entonces L ( P , t ) es el número de puntos de rejilla enteros en tP .
Más formalmente, considere una celosía en el espacio euclidiano y un politopo P d - dimensional encon la propiedad de que todos los vértices del politopo son puntos de la celosía. (Un ejemplo común esy un politopo para el cual todos los vértices tienen coordenadas enteras .) Para cualquier entero positivo t , sea tP la dilatación t- pliegue de P (el politopo formado al multiplicar cada coordenada del vértice, en una base para la red, por un factor de t ), y deja
sea el número de puntos de celosía contenidos en el politopo tP . Ehrhart demostró en 1962 que L es un polinomio racional de grado d en t , es decir, existen números racionales tal que:
para todos los enteros positivos t .
El polinomio de Ehrhart del interior de un politopo convexo cerrado P se puede calcular como:
donde d es la dimensión de P . Este resultado se conoce como reciprocidad de Ehrhart-Macdonald. [1]
Ejemplos de
Sea P un hipercubo unitario d- dimensional cuyos vértices son los puntos de celosía enteros cuyas coordenadas son 0 o 1. En términos de desigualdades,
Entonces, la dilatación del pliegue t de P es un cubo con una longitud de lado t , que contiene ( t + 1) d puntos enteros. Es decir, el polinomio de Ehrhart del hipercubo es L ( P , t ) = ( t + 1) d . [2] [3] Además, si evaluamos L ( P , t ) en números enteros negativos, entonces
como cabría esperar de la reciprocidad de Ehrhart-Macdonald.
Muchos otros números figurados se pueden expresar como polinomios de Ehrhart. Por ejemplo, los números piramidales cuadrados vienen dados por los polinomios de Ehrhart de una pirámide cuadrada con una unidad entera cuadrada como base y una altura de uno; el polinomio de Ehrhart en este caso es1/6( t + 1) ( t + 2) (2 t + 3) . [4]
Cuasi polinomios de Ehrhart
Sea P un politopo racional. En otras palabras, suponga
dónde y (De manera equivalente, P es el casco convexo de un número finito de puntos en) Entonces defina
En este caso, L ( P , t ) es un cuasi polinomio en t . Al igual que con los politopos integrales, se mantiene la reciprocidad de Ehrhart-Macdonald, es decir,
Ejemplos de cuasi polinomios de Ehrhart
Sea P un polígono con vértices (0,0), (0,2), (1,1) y ( 3/2, 0). El número de puntos enteros en tP será contado por el cuasi-polinomio [5]
Interpretación de coeficientes
Si P es cerrado (es decir, las caras del límite pertenecen a P ), algunos de los coeficientes de L ( P , t ) tienen una interpretación fácil:
- el coeficiente principal, , es igual al volumen d- dimensional de P , dividido por d ( L ) (ver rejilla para una explicación del contenido o covolumen d ( L ) de una rejilla);
- el segundo coeficiente, , se puede calcular de la siguiente manera: la celosía L induce una celosía L F en cualquier cara F de P ; tome el volumen ( d - 1) -dimensional de F , divida por 2 d ( L F ) y sume esos números para todas las caras de P ;
- el coeficiente constante un 0 es la característica de Euler de P . Cuando P es un politopo convexo cerrado,.
El teorema de Betke-Kneser
Ulrich Betke y Martin Kneser [6] establecieron la siguiente caracterización de los coeficientes de Ehrhart. Un funcional definido en politopos integrales es un y valoración invariante de traducción si y solo si hay números reales tal que
Serie Ehrhart
Podemos definir una función generadora para el polinomio de Ehrhart de un politopo P integral d -dimensional como
Esta serie se puede expresar como función racional . Específicamente, Ehrhart demostró (1962) [ cita requerida ] que existen números complejos, , tal que la serie Ehrhart de P es
Además, el teorema de no negatividad de Richard P. Stanley establece que bajo las hipótesis dadas, serán enteros no negativos, por .
Otro resultado de Stanley [ cita requerida ] muestra que si P es un politopo reticular contenido en Q , entoncespara todos j . La-vector no es en general unimodal, pero lo es siempre que es simétrico, y el politopo tiene una triangulación unimodal regular. [7]
Serie Ehrhart para politopos racionales
Como en el caso de los politopos con vértices enteros, se define la serie de Ehrhart para un politopo racional. Para un politopo P racional d -dimensional , donde D es el número entero más pequeño tal que DP es un politopo entero ( D se llama denominador de P ), entonces uno tiene
donde el siguen siendo números enteros no negativos. [8] [9]
Límites de coeficientes no principales
Los coeficientes no principales del polinomio en la representacion
puede tener un límite superior: [10]
dónde es un número de Stirling del primer tipo . También existen límites inferiores. [11]
Variedad tórica
El caso y de estos enunciados produce el teorema de Pick . Las fórmulas para los otros coeficientes son mucho más difíciles de obtener; Para este propósito se han utilizado las clases de Todd de variedades tóricas , el teorema de Riemann-Roch y el análisis de Fourier .
Si X es la variedad tórica correspondiente al abanico normal de P , entonces P define un haz de líneas amplio en X , y el polinomio de Ehrhart de P coincide con el polinomio de Hilbert de este haz de líneas.
Los polinomios de Ehrhart se pueden estudiar por sí mismos. Por ejemplo, se podrían hacer preguntas relacionadas con las raíces de un polinomio de Ehrhart. [12] Además, algunos autores han abordado la cuestión de cómo se podrían clasificar estos polinomios. [13]
Generalizaciones
Es posible estudiar el número de puntos enteros en un politopo P si dilatamos algunas facetas de P pero no otras. En otras palabras, a uno le gustaría saber el número de puntos enteros en politopos semidilatados. Resulta que dicha función de conteo será lo que se llama un cuasi-polinomio multivariado. Un teorema de reciprocidad de tipo Ehrhart también será válido para dicha función de conteo. [14]
Contar el número de puntos enteros en semidilataciones de politopos tiene aplicaciones [15] para enumerar el número de disecciones diferentes de polígonos regulares y el número de códigos no restringidos no isomórficos, un tipo particular de código en el campo de la teoría de la codificación .
Ver también
- Cuasi polinomio
- Teorema de reciprocidad de Stanley
Notas
- ^ Macdonald, Ian G. (1971). "Polinomios asociados con complejos celulares finitos". Revista de la Sociedad Matemática de Londres . 2 (1): 181-192. doi : 10.1112 / jlms / s2-4.1.181 .
- ^ De Loera, Rambau y Santos (2010)
- ↑ Mathar (2010)
- ^ Beck y col. (2005) .
- ^ Beck, Matthias; Robins, Sinai (2007). Calcular lo continuo de forma discreta . Nueva York: Springer. págs. 46 –47. Señor 2271992 .
- ^ Betke, Ulrich; Kneser, Martin (1985), "Zerlegungen und Bewertungen von Gitterpolytopen", Journal für die reine und angewandte Mathematik , 358 : 202-208, MR 0797683
- ^ Athanasiadis, Christos A. (2004). " h * -vectores, polinomios eulerianos y politopos estables de gráficos" . Revista electrónica de combinatoria . 11 (2). doi : 10.37236 / 1863 .
- ^ Stanley, Richard P. (1980). "Descomposiciones de politopos convexos racionales". Annals of Discrete Mathematics . 6 : 333–342. doi : 10.1016 / s0167-5060 (08) 70717-9 . ISBN 9780444860484.
- ^ Beck, Matthias; Sottile, Frank (enero de 2007). "Demostraciones irracionales de tres teoremas de Stanley". Revista europea de combinatoria . 28 (1): 403–409. arXiv : matemáticas / 0501359 . doi : 10.1016 / j.ejc.2005.06.003 . S2CID 7801569 .
- ^ Betke, Ulrich; McMullen, Peter (1 de diciembre de 1985). "Puntos de celosía en politopos de celosía". Monatshefte für Mathematik . 99 (4): 253-265. doi : 10.1007 / BF01312545 . ISSN 1436-5081 . S2CID 119545615 .
- ^ Henk, Martin; Tagami, Makoto (1 de enero de 2009). "Límites inferiores de los coeficientes de polinomios de Ehrhart". Revista europea de combinatoria . 30 (1): 70–83. arXiv : 0710.2665 . doi : 10.1016 / j.ejc.2008.02.009 . ISSN 0195-6698 . S2CID 3026293 .
- ^ Braun, Benjamin; Develin, Mike (2008). Raíces polinomiales de Ehrhart y teorema de no negatividad de Stanley . Matemáticas contemporáneas. 452 . Sociedad Matemática Estadounidense . págs. 67–78. arXiv : matemáticas / 0610399 . doi : 10.1090 / conm / 452/08773 . ISBN 9780821841730. S2CID 118496291 .
- ^ Higashitani, Akihiro (2012). "Clasificación de polinomios de Ehrhart de Simplices integrales" (PDF) . Actas del DMTCS : 587–594.
- ^ Beck, Matthias (enero de 2002). "Reciprocidad multidimensional de Ehrhart". Revista de teoría combinatoria . Serie A. 97 (1): 187-194. arXiv : matemáticas / 0111331 . doi : 10.1006 / jcta.2001.3220 . S2CID 195227 .
- ^ Lisonek, Petr (2007). "Familias combinatorias enumeradas por cuasi-polinomios". Revista de teoría combinatoria . Serie A. 114 (4): 619–630. doi : 10.1016 / j.jcta.2006.06.013 .
Referencias
- Beck, Matthias; De Loera, Jesús A .; Develin, Mike ; Pfeifle, Julian; Stanley, Richard P. (2005), "Coeficientes y raíces de polinomios de Ehrhart", Puntos enteros en poliedros: geometría, teoría de números, álgebra, optimización , matemáticas contemporáneas, 374 , Providence, RI: American Mathematical Society , págs. 15–36 , MR 2134759.
- Beck, Matthias; Robins, Sinai (2007), Computación discreta de lo continuo: enumeración de puntos enteros en poliedros , Textos de pregrado en matemáticas , Nueva York: Springer-Verlag, ISBN 978-0-387-29139-0, Señor 2271992.
- De Loera, Jesús A .; Rambau, Jörg; Santos, Francisco (2010), "Polinomios de Ehrhart y triangulaciones unimodulares", Triangulaciones: Estructuras para Algoritmos y Aplicaciones , Algoritmos y Computación en Matemáticas, 25 , Springer, p. 475, ISBN 978-3-642-12970-4.
- Díaz, Ricardo; Robins, Sinai (1996), "El polinomio de Ehrhart de una celosía n- simple", Anuncios de investigación electrónica de la Sociedad Matemática Estadounidense , 2 : 1–6, doi : 10.1090 / S1079-6762-96-00001-7 , MR 1405963. Introduce el enfoque del análisis de Fourier y ofrece referencias a otros artículos relacionados.
- Ehrhart, Eugène (1962), "Sur les polyèdres rationnels homothétiques à n Dimensions", Comptes rendus de l'Académie des Sciences , 254 : 616–618, MR 0130860. Definición y primeras propiedades.
- Mathar, Richard J. (2010), recuentos de puntos de y algo y celosías enteras dentro de hipercubos , arXiv : 1002.3844 , Bibcode : 2010arXiv1002.3844M
- Mustață, Mircea (febrero de 2005), "Polinomios de Ehrhart", Notas de clase sobre variedades tóricas.