La expresión exponencial de las funciones generatrices y su combinatoria

FACULTAD DE CIENCIAS TRABAJO FIN DE MÁSTER Máster en Matemáticas LA EXPRESIÓN EXPONENCIAL DE LAS FUNCIONES GENERATRICES Y SU COMBINATORIA. Autora: Raquel Melgar Fernández Tutor: Antonio Campillo López Año: 2022-2023 ´ Indice general Introducci´on 5 1. Definiciones y resultados previos. 7 1.1. Poliedros, conos y polaridad. ............................. 7 1.2. Resultados sobre descomposici´on de poliedros. ................... 11 2. Dos evaluaciones para poliedros. Presentaci´on del cambio exponencial. 13 2.1. Una evaluaci´on para contar los puntos reticulares de un poliedro. ........ 13 2.2. Una evaluaci´on para obtener el volumen (generalizado) de un poliedro. ..... 17 2.3. El cambio exponencial en la evaluaci´on Ψ...................... 21 3. Una f´ormula para calcular el n´umero de puntos reticulares en un politopo. 29 3.1. Una evaluaci´on para conos racionales. ........................ 30 3.2. La f´ormula de Berline-Vergne. ............................ 41 4. El cambio exponencial para semigrupos num´ericos. 45 4.1. Funciones generatrices de semigrupos num´ericos. .................. 45 4.2. El cambio exponencial en funciones generatrices de semigrupos num´ericos. . . . 50 4.3. Series de Poincar´e de semigrupos num´ericos. .................... 53 4.4. Perspectivas y conclusiones. ............................. 56 A. Funci´on en SageMath para calcular el polinomio de huecos de un semigrupo con 3 generadores. 59 Bibliograf´ıa 62 3 Introducci´on Las funciones generatrices se estudian habitualmente como series formales de potencias cuyos coeficientes codifican una cierta informaci´on discreta: una cierta sucesi´on, los elementos de un semigrupo, los n´umeros con coordenadas enteras contenidos en un poliedro... En palabras de Herbert S. Wilf [12]: “Una funci´on generatriz es una cuerda de la ropa en la que tendemos una sucesi´on de n´umeros para exhibirla”. En este trabajo se estudiar´a una expresi´on exponencial para ciertas funciones generatrices que resulta de utilidad en los c´alculos. El presente trabajo surge a ra´ız de mi Trabajo Fin de Grado [10] en el que, siguiendo el trabajo de M.Brion [6] y A.Barvinok [1], se estudian a fondo dos c´elebres evaluaciones de poliedros: una evaluaci´on para calcular el n´umero de puntos reticulares de un poliedro reticular y una evaluaci´on para calcular el volumen generalizado de un poliedro. En la primera de estas evaluaciones surge de manera natural la idea de hacer el cambio de variables x7→ eypara facilitar el c´alculo del n´umero de puntos reticulares contenidos en un poliedro. Uno de los objetivos de este trabajo es analizar este cambio de variable y observar qu´e sucede al realizarlo en la funci´on generatriz de un semigrupo. El primer cap´ıtulo introduce las definiciones y resultados sobre teor´ıa de poliedros que ser´an necesarios en los siguientes cap´ıtulos. El segundo cap´ıtulo presenta las dos evaluaciones antes mencionadas y estudia las propiedades del cambio exponencial x7→ eyen la primera de ellas. Se aportan varios ejemplos expl´ıcitos de c´alculo tras dicho cambio. Estos c´alculos est´an relacionados con los Polinomios de Todd. El tercer cap´ıtulo presenta un resultado reciente de gran relevancia en la teor´ıa de poliedros: la f´ormula de Berline-Vergne. Estas dos matem´aticas francesas proporcionan una nueva f´ormula para expresar X x∈P∩Zd h(x) donde Pes un politopo racional de dimensi´on dyh(x) un polinomio, como la suma extendida a las caras Fde Pde el volumen de Fpor una cierta evaluaci´on relacionada con F. Se explicitar´a esta nueva evaluaci´on y se demostrar´a la f´ormula para el caso h(x) = 1. Tambi´en se ver´a como esta f´ormula generaliza a dimensi´on superior la conocida f´ormula de Pick. El cuarto y ´ultimo cap´ıtulo aborda otro problema combinatorio como es el de determinar los huecos de un semigrupo num´erico. Se plantea c´omo aprovechar el cambio exponencial que ya 5 ´ Indice general 6 se ha planteado para la funci´on generatriz de un semigrupo num´erico. Se obtiene una soluci´on concluyente para esta cuesti´on a trav´es de las sumas de Newton y se implementa una funci´on en SageMath para el caso de semigrupos generados por tres elementos. Cap´ıtulo 1 Definiciones y resultados previos. En este cap´ıtulo se introducen las definiciones y resultados relativos a la teor´ıa de poliedros que ser´an necesarios en los cap´ıtulos 2 y 3. En [10] y [1] aparecen las definiciones expuestas con m´as detalle y aparecen demostrados los resultados que en este cap´ıtulo solo se enuncian. Se considerar´a el espacio vectorial V=Rdcon d≥0. 1.1. Poliedros, conos y polaridad. Definici´on 1.1. Un poliedro P⊂Ves un conjunto definido por una cantidad finita de inecuaciones lineales: P:= {x∈V:ℓi(x)≤αi, i ∈I}(1.1) Para un conjunto Ifinito, donde ℓi:V−→ Rson funciones lineales y αison n´umeros reales. Es decir, un poliedro es un subconjunto que se puede escribir como la intersecci´on de un conjunto finito de semiespacios cerrados. Diremos que un poliedro es racional si en la expresi´on 1.1, se pueden escoger αiy los coeficientes de ℓiracionales. Si un poliedro es racional entonces en los hiperplanos que delimitan Phay puntos de Zd. Observamos que un poliedro es un conjunto convexo y cerrado por definici´on. Si un poliedro es acotado diremos que es un politopo. La dimensi´on de un poliedro Pes la dimensi´on del menor subespacio af´ın que lo contiene. Definici´on 1.2. Sea P⊂Vun poliedro y sea v∈P. Decimos que ves un v´ertice de Psi cuando se tienen v1, v2∈Ptales que v=v1+v2 2entonces necesariamente v1=v2=v. Es decir, ves un v´ertice si no existen v1yv2puntos distintos de Ptales que vsea su punto medio. Definici´on 1.3. Sea F⊂Pdecimos que Fes una cara de Psi existe ℓ:V−→ Runa funci´on lineal y α∈Rtal que ℓ(x)≤αpara todo x∈Py F={x∈P:ℓ(x) = α}. 7 Cap´ıtulo 1. Definiciones y resultados previos. 8 En particular dado un poliedro P, el propio Pes una cara de Py los v´ertices de Pson caras de P. Definici´on 1.4. Sea A⊂Vun conjunto. Entonces la funci´on caracter´ıstica de A,1Aes la funci´on 1A:V−→ Rdada por: 1A(x) = (1si x ∈A 0si x /∈A. (1.2) Denotaremos P(V), el espacio vectorial sobre Rgenerado por las funciones caracter´ısticas de los poliedros de V,P⊂V. Esto es, es el m´ınimo espacio vectorial que contiene las funciones caracter´ısticas de los poliedros P⊂V. Entonces los elementos de P(V) son las combinaciones lineales finitas con coeficientes en Rde funciones caracter´ısticas de poliedros. Es decir, si f∈ P(V), entonces fes de la forma: f=X i∈I αi1Pi donde Pi⊂Vson una cantidad finita de poliedros y αison n´umeros reales. An´alogamente se define Pb(V) el espacio vectorial sobre Rde las funciones caracter´ısticas de politopos. Definici´on 1.5. Una evaluaci´on de P(V) o P(V)es una transformaci´on lineal T:P(V),Pb(V)−→ W donde Wes un espacio vectorial. Hay otras evaluaciones, definidas de la misma forma, con salida en otros espacios vectoriales. En la memoria se considerar´a alguna de estas tambi´en. Una caracter´ıstica fundamental de las evaluaciones es la siguiente: la evaluaci´on de (la funci´on caracter´ıstica de) la uni´on de dos poliedros es la suma de las evaluaciones de (las funciones caracter´ısticas de) de dos poliedros menos la evaluaci´on de (la funci´on caracter´ıstica de) la intersecci´on. Es decir, si PyQson poliedros y Tes una evaluaci´on se tiene: T(1P∪Q) = T(1P) + T(1Q)−T(1P∩Q). Resultado 1.1. Un poliedro no vac´ıo contiene un v´ertice si y solo si no contiene ninguna recta. A continuaci´on se define un caso particular de poliedro que ser´a de gran importancia en el trabajo. Definici´on 1.6. Un poliedro K⊂Ves un cono si 0 ∈Ky para cada x∈Ky cada λ≥0 se tiene que λx ∈K. Cap´ıtulo 1. Definiciones y resultados previos. 9 El ´unico posible v´ertice de un cono es 0. Por el resultado 1.1 se tiene que 0 es un v´ertice del cono si y solo si el cono no contiene rectas. Un cono que no contiene rectas recibe el nombre de cono punteado. Definici´on 1.7. Un punto v∈Vse dice que es combinaci´on c´onica de los puntos v1, v2, ..., vm∈ Vsi v= m X i=1 λividonde λi≥0. El conjunto de combinaciones c´onicas de un conjunto dado A⊂Vrecibe el nombre de combinaci´on c´onica de Ay se denota co(A) y es el m´ınimo cono que contiene a los puntos de A. Decimos que un cono K⊂Ves simplicial si puede ser escrito como K=co(u1, u2, ..., ud) donde {u1, u2, ..., ud}es una base de V. Para d= 2 todos los conos son simpliciales. Definici´on 1.8. Sean u1, ..., uk∈Zdvectores linealmente independientes y sea K=co(u1, ..., uk) el m´ınimo cono que los contiene.Decimos que el cono Kes regular si el paralelep´ıpedo semiabierto D={ k X i=1 αiui: 0 ≤αi<1para i = 1, ..., k} no contiene puntos reticulares que no sean el origen. Este paralelep´ıpedo recibe el nombre de paralelep´ıpedo fundamental de K. Figura 1.1: Conos y sus paralelep´ıpedos fundamentales. Dado un poliedro P⊂Rddefinimos a continuaci´on varios conos asociados a P. Cap´ıtulo 2. Dos evaluaciones para poliedros. Presentaci´on del cambio exponencial. 16 donde p(x) es el polinomio indicador reticular del paralelep´ıpedo fundamental Dde K. Es decir, polinomio indicador reticular de la regi´on: D={ d X i=1 αiui: 0 ≤αi<1, i = 1,2, ..., d} Frecuentemente denotaremos hv(x) := Ψfcono(P,v)(x). Un ejemplo 2-dimensional de esta curiosa simplificaci´on es el siguiente. Ejemplo 2.1. Se considera en R2el tri´angulo Tque tiene como v´ertices (0,0),(3,0) y(0,3). Entonces se tiene X m∈T∩Z2 xm=h(0,0)(x1, x2) + x3 1h(3,0)(x1, x2) + x3 2h(0,3)(x1, x2) =1 (1 −x1)(1 −x2)+x3 1 (1 −x−1 1)(1 −x−1 1x2)+x3 2 (1 −x−1 2)(1 −x1x−1 2) = 1 + x1+x2 1+x3 1+x2(1 + x1+x2 1) + x2 2(1 + x1) + x3 2 (2.4) La suma de funciones racionales se simplifica en un polinomio en el que los exponentes son los puntos reticulares contenidos en T. Observaci´on 2.1.En particular se tiene que si Pes un politopo, entonces ΦP(y) es un polinomio y que #P∩Zd= ΨP(1). En el ejemplo que acabamos de ver se ha obtenido que #P∩Zd= 10. Cap´ıtulo 2. Dos evaluaciones para poliedros. Presentaci´on del cambio exponencial. 17 2.2. Una evaluaci´on para obtener el volumen (generalizado) de un poliedro. Se considera en Rdel producto escalar usual ⟨·,·⟩. Dado un poliedro P⊂Rd, usualmente se define la medida de Lebesgue de Pcomo ZV 1P(ξ)dξ =ZP dξ. De aqu´ı en adelante nos referiremos a la medida de Lebesgue de un poliedro como “volumen” independientemente de cual sea el valor de d. A priori, solo tiene sentido definir as´ı el volumen en el caso de que Psea un politopo y en ese caso se puede extender esta noci´on de volumen a Pb(Rd) por linealidad. El siguiente teorema generaliza esta idea de volumen para un poliedro Pno necesariamente acotado. Denotaremos por RM(Rd) el espacio vectorial sobre Rengendrado por las funciones del tipo f(y) = e⟨y,v⟩ d Y i=1 1 ⟨−y, xi⟩con y ∈Rd donde v∈Rdyu1, u2, ..., udes una base de Rd. El espacio vectorial RM(Rd) es un subespacio del cuerpo de funciones meromorfas reales M(Rd) = M(x1, x2, ..., xd) visto como espacio vectorial sobre R. Teorema 2.2. [10] Existe una evaluaci´on Φ : P(Rd)−→ RM(Rd) que verifica lo siguiente: 1. Sea P⊂Rdun poliedro no vac´ıo que no contiene rectas y sea K⊂Rdsu cono de recesi´on. Entonces, para cada y∈intKo, la integral ZP e⟨ξ,y⟩dξ converge absolutamente y uniformemente en los conjuntos compactos de intKohacia la funci´on Φ(1P,·)∈ RM(Rd) que usualmente denotaremos por ΦP(y). Cap´ıtulo 2. Dos evaluaciones para poliedros. Presentaci´on del cambio exponencial. 18 2. Si Pcontiene alguna recta, entonces Φ(1P)≡0. Entonces, en el caso de que Psea un politopo, se tendr´a ΦP(y) = ZP e⟨ξ,y⟩dξ y en particular ΦP(0) = ZP 1dξ, que es el volumen usual de P. Nota 2.2. Tambi´en en este caso se puede enunciar y demostrar el teorema en t´erminos de series formales sin tener en cuenta la convergencia. Para ello consideramos el anillo Hde funciones enteras reales, por SC el anillo de series de potencias convergentes en el origen y por SP =R[[y]] el anillo de series de potencias formales en las variables y1, y2, ..., ydcon coeficientes reales. Todos ello son m´odulos sobre el anillo de polinomios R[y]y tras identificar cada funci´on entera con su desarrollo en serie de Taylor en el origen se tiene la siguiente cadena de inclusiones: R[y]→ H → SC →SP En [10] se demuestra que los elementos de SC y de Hse identifican con las series X m∈Nd amym con am∈Rque verifican que l´ım k→∞(P|m|=k|ak|)1/k no es +∞o es 0 respectivamente. Podemos localizar la cadena de inclusiones anterior en los conjuntos multiplicativamente cerrados S0= R[y]\{0}yS1={productos finitos de polinomios lineales homogeneos}para obtener las cadenas de inclusiones: R(y)→ H(0) →SC(0) →SP(0) R[y](1) → H(1) →SC(1) →SP(1) Tambi´en se tienen las inclusiones R[y](1) ⊂R(y),H(1) ⊂ H(0),SC(1) ⊂SC(0)ySP(1) ⊂SP(0) As´ı, para escribir el teorema 2.2 en t´erminos formales, se construye la evaluaci´on Φ : P(Rd)→ H(0) que asigna a la funci´on caracter´ıstica de un poliedro el cociente h qdonde qes un producto de formas lineales y hes una funci´on entera que se obtiene por extensi´on anal´ıtica (y por tanto Cap´ıtulo 2. Dos evaluaciones para poliedros. Presentaci´on del cambio exponencial. 19 necesariamente ´unica) de la funci´on Rqe⟨y,ξ⟩dξ que a priori solo converge en el conjunto intPo . Adem´as como intPo=∅si y solo si Pcontiene alguna recta (resultado 1.3), se obtiene el apartado 2 del teorema: ΦP(y) = 0 cuando Pcontiene alguna recta. Se tiene ΦP(y)∈ H(1) ⊂ H(0). Igual que antes, aplicando esta evaluaci´on Φ a la relaci´on 2.2 se obtiene la relaci´on: ΦP(y) = X v∈V ert(P) Φtcono(P,v)(y) De hecho, haciendo un cambio de variable en la integral que define Φtcono(P,v)se puede escribir Φtcono(P,v)(y) = e⟨y,v⟩Φfcono(P,v)(y). Normalmente denotaremos Φfcono(P,v)(y) = fv(y). Es decir, dado un poliedro cualquiera P⊂Rd, podemos asociarle una funci´on meromorfa ΦP(y) (a la que llamaremos volumen generalizado de P) que verifique que si Pes acotado, ΦP(y) est´a bien definida en 0 y ΦP(0) coincide con el volumen usual de P. Adem´as, la funci´on volumen generalizado de un poliedro Pse obtiene como la suma de los vol´umenes generalizados de los conos tangentes en los v´ertices de P. La construcci´on de esta evaluaci´on para los conos tangentes se explicita en [10]. Pero como antes, nos basaremos en la descomposici´on de cualquier cono en conos simpliciales. Si K= co(u1, u2, ..., ud) es un cono simplicial, entonces ΦK(y) = ZK e⟨y,ξ⟩dξ =|u1∧u2∧... ∧ud| d Y i=1 1 ⟨−y, ui⟩ donde |u1∧u2∧... ∧ud|es el volumen del paralelep´ıpedo generado por u1, u2, ..., ud, es decir |u1∧u2∧... ∧ud|=vol{ d X i=1 uiαi: 0 ≤αi≤1para i = 1, ..., d} Veamos dos ejemplos de esta curiosa simplificaci´on para d= 2. Ejemplo 2.2. Supongamos que T⊂R2es de nuevo el tri´angulo de v´ertices (0,0),(0,3) y(3,0) y sea y= (y1, y2)(ver figura 2.1). Entonces se tiene que: ZT e⟨y,ξ⟩dξ =X v∈V ertT Φ(1tcono(P,v)) = X v∈V ertT e⟨y,v⟩fv(y) =1 (−y1)(−y2)+e3y1 y2(y2−y1)+e3y2 y1(y1−y2). (2.5) Cap´ıtulo 2. Dos evaluaciones para poliedros. Presentaci´on del cambio exponencial. 20 Figura 2.1: Tri´angulo Tcon sus conos de direcciones factibles Como el numerador de las funciones es siempre una funci´on entera, consideramos su desarrollo de Taylor en el origen para obtener: 1 (−y1)(−y2)+e3y1 y2(y2−y1)+e3y2 y1(y1−y2)= (y1−y2) + y2(1 + 3y1+9y2 1 2! +...)−y1(1 + 3y2+9y2 2 2! +...) y1y2(y1−y2)= 9 2+9 2(y1+y2) + 27 8(y2 1+y1y2+y2 2) + ... (2.6) Esto es, al evaluar en 0 la funci´on obtenida, se tiene ΦT(0) = 9/2, el volumen usual del tri´angulo T. Ejemplo 2.3. Consideramos el cuadril´atero Pcon conjunto de v´ertices {(0,0),(0,3),(2,2) y(3,0)}, que tiene ´area 6 (ver figura 2.2). Figura 2.2: Segundo ejemplo c´alculo de volumen Cap´ıtulo 2. Dos evaluaciones para poliedros. Presentaci´on del cambio exponencial. 21 Entonces: ϕ(P, y) = X v∈V ertP e⟨v,y⟩fv(y) = 1 y1y2 +2e3y1 (y1−2y2)y1 +3e3y2 (y2−2y1)y2 +2e2y1+2y2 (2y2−y1)(2y1−y2)=h q. Con q=y1y2(y1−2y2)(y2−2y1) h= (y1−2y2)(y2−2y1)+2e3y1y2(y2−2y1)+2e3y2y1(y1−2y2)+3y1y2e2(y1+y2). Ahora, tras desarrollar hen serie de Taylor vemos qu´e sucede en cada uno de sus t´erminos. No hay t´ermino independiente ni t´ermino lineal. El t´ermino cuadr´atico: 5y1y2−2y2 1−2y2 2−4y1y2+ 2y2 1−4y1y2+ 3y1y2= 0 El t´ermino c´ubico: 6y1(y2 2−2y1y2)+6y2(y2 1−2y1y2) + 6(y1+y2)y1y2= 0 El t´ermino cu´artico:  2y2(y2−2y1)9y2 1  2! + 2y1(y1−2y2)9y2 2  2! +3y1y24(y1+y2)2 2! = 30y2 1y2 2−12y1y3 2− 12y3 2y1= 6q. Los t´erminos de grado ≥5de hson tambi´en polinomios homog´eneos m´ultiplos de q. En efecto, el t´ermino de grado k-´esimo para k≥5es: 2y2(y2−2y1)(3y1)k−2 (k−2)! + 2y1(y1−2y2)(3y2)k−2 (k−2)! + 3y1y2 2k−2(y1+y2)k−2 (k−2)! y por la regla de Ruffini, es m´ultiplo de qpues se anula para las sustituciones y1= 0,y2= 0, y1= 2y2yy2= 2y1. As´ı, deducimos que: ϕ(P, 0) = 6. Observaci´on 2.2.En los ejemplos, los t´erminos con exponente negativo en el desarrollo de Laurent de ΦP(y) se cancelan y se obtiene una funci´on entera. En [10] se demuestra que en el caso de que Psea un politopo, ΦP(y) es siempre una funci´on entera. 2.3. El cambio exponencial en la evaluaci´on Ψ. Se presenta a continuaci´on una idea principal en este trabajo. Nos preguntamos qu´e sucede si en expresiones del tipo 2.1 consideramos el cambio de variable x7→ ey. Se obtendr´ıa la siguiente expresi´on: X m∈P∩Zd e⟨m,y⟩.(2.7) Cap´ıtulo 2. Dos evaluaciones para poliedros. Presentaci´on del cambio exponencial. 22 Sin embargo, e⟨m,y⟩= 1+⟨m, y⟩+⟨m, y⟩2/2+· · · es una unidad en Q[[y]] pues tiene t´ermino independiente no nulo y a priori no est´a bien definido el t´ermino independiente de la serie que se obtiene tras hacer la sustituci´on en 2.1. Sin embargo, por el teorema 2.1 ya sabemos que si Pes un poliedro racional, entonces 2.1 se puede expresar como una funci´on racional que vive en R(Qd), es decir, es combinaci´on lineal finita de expresiones del tipo xv (1 −xu1)· · · (1 −xud) donde el cambio exponencial est´a bien definido. En otras palabras, aunque SPtenga infinitos t´erminos, la funci´on racional F(SP) es una funci´on racional para la cual el cambio exponencial est´a bien definido. En efecto, tendr´ıamos: e⟨y,v⟩ (1 −e⟨y,u1⟩)· · · (1 −e⟨y,ud⟩)=e⟨y,v⟩ (−1)dQd i=1⟨y, ui⟩(1 + ⟨y,ui⟩ 2! +⟨y,ui⟩2 3! +· · · ). Denotamos Ui= 1 + ⟨y,ui⟩ 2! +⟨y,ui⟩2 3! +· · · . Al tener t´ermino independiente no nulo, esta serie de potencias es invertible. Si denotamos por U−1 ia su inversa, entonces se obtiene (−1)de⟨y,v⟩ d Y i=1 U−1 i ⟨y, ui⟩= (−1)de⟨y,v⟩U−1 d Y i=1 1 ⟨y, ui⟩ donde U−1=Qd i=1 U−1 ies una unidad en R[[y]] con t´ermino independiente 1. De aqu´ı en adelante, denotaremos Γ a la evaluaci´on que se obtiene tras hacer el cambio de variable x7→ eyen la evaluaci´on Ψ. Es decir Γ(1P, y) = Ψ(1P, ey) Recapitulando, se tiene que para un poliedro racional Pde dimensi´on d ΦP(y) = X v∈V ertP Φtcono(P,v)(y) = X v∈V ertP e⟨y,v⟩Φfcono(P,v)(y)=X v∈V ertP e⟨y,v⟩fv(y) ΓP(y) = X v∈V ertP Γtcono(P,v)(y) = X v∈V ertP e⟨y,v⟩Γfcono(P,v)(y)=X v∈V ertP e⟨y,v⟩gv(y) donde fv(y) es una funci´on racional cociente de dos polinomios homog´eneos y de grado −dy gv(y) es cociente de una funci´on entera entre un producto de formas lineales. Podemos escribir e⟨y,v⟩gv(y) = gv,0(y) + gv,1(y) + · · · +gv,k(y) + · · · Cap´ıtulo 2. Dos evaluaciones para poliedros. Presentaci´on del cambio exponencial. 23 donde gv,k es un cociente de polinomios homog´eneos de grado k−dy an´alogamente e⟨y,v⟩fv(y) = fv,0(y) + fv,1(y) + · · · +fv,k(y) + · · · siendo fv,k(y) = ⟨y,v⟩k k!fv(y) la expresi´on expl´ıcita para fv,k(y). Proposici´on 2.1. Con las notaciones anteriores, se tiene que gv,0(y) = fv,0(y) = fv(y) Demostraci´on. La segunda igualdad es clara. Para demostrar la primera veamos primero el caso de conos simpliciales. Sea vun v´ertice tal que fcono(P, v) = co(u1, u2, ..., ud) es un cono simplicial. Entonces fvygvse escriben: fv(y) = ZK e⟨y,ξ⟩dξ =|u1∧u2∧ · · · ∧ ud| d Y i=1 1 ⟨−y, ui⟩ gv=p(ey)U−1(y) Qd i=1⟨−y, ui⟩ donde p(X)∈Z[X] es el polinomio indicador reticular del paralelep´ıpedo fundamental Dde fcono(P, v). Los t´erminos homog´eneos de grado −den estas expresiones son |u1∧u2∧ · · · ∧ ud| d Y i1 1 ⟨−y, ui⟩ y #D∩Zd Qd i=1⟨−y, ui⟩ respectivamente. Como se tiene la igualdad |u1∧u2∧ · · · ∧ ud|= #D∩Zd, ya est´a probado el resultado para conos simpliciales. Veamos que tambi´en se da la igualdad en conos arbitrarios. Ya sabemos (resultado 1.6) que todo cono Kpuede ser escrito como suma finita de conos simpliciales 1K=X i∈I ±1Ki. Alguno de estos conos Kitendr´an dimensi´on < d, pero para ellos la aportaci´on al volumen es nula. Adem´as en la expresi´on de gv(y), los conos de dimensi´on d′< d, tienen t´erminos de grado −d′como mucho. As´ı gv,0(y) no queda afectado por estos conos, solo afectan los conos Kjde dimensi´on d. De modo que tambi´en se tiene gv,0=fv(y) para el caso no simplicial. Cap´ıtulo 2. Dos evaluaciones para poliedros. Presentaci´on del cambio exponencial. 24 Denotamos gP,k yfP,k las partes homog´eneas de grado k−den el desarrollo de Laurent de ΓP(y)yΦP(y) respectivamente. Cuando Pes un politopo, se tiene que ΦP(y)yΓP(y) son funciones enteras. As´ı, si k < d entonces gP,k =fP,k = 0. Si k≥dentonces gP,k yfP,k son polinomios homog´eneos de grado k. En particular: 1. gP,k(y) = fP,k(y) = 0 para k < d. 2. gP,0yfP0son constantes y adem´as gP,0= #P∩Zd yfP,0es el volumen usual de P. Veamos un ejemplo de esto, volviendo a considerar el caso en que T⊂R2es el tri´angulo de v´ertices {(0,0),(3,0),(0,3)}. Ejemplo 2.4. Hab´ıamos visto que ΨT(x1, x2) = 1 (1 −x1)(1 −x2)+x3 1 (1 −x−1 1)(1 −x−1 1x2)+x3 2 (1 −x−1 2)(1 −x1x−1 2) entonces ΓP(y1, y2) = 1 (1 −ey1)(1 −ey2)+e3y1 (1 −e−y1)(1 −ey2−y1)+e3y2 (1 −e−y2)(1 −ey1−y2). Si, como ya hemos hecho antes denotamos U(y) = 1 + y 2! +y2 3! +y3 4! +· · · entonces U−1(y) = 1 −y 2+y2 12 +· · · y la expresi´on de ΓP(y1, y2)queda ΓP(y1, y2) =U−1(y1)U−1(y2) y1y2 +(1 + 3y1+(3y1)2 2+· · · )U−1(−y1)U−1(y2−y1) y1(y2−y1)+ (1 + 3y2+· · · )U−1(−y2) y2(y1−y2) (2.8) Haciendo los c´alculos se obtiene que los t´erminos homog´eneos de grados −1y−2de cada Cap´ıtulo 2. Dos evaluaciones para poliedros. Presentaci´on del cambio exponencial. 25 uno de los sumandos se cancelan entre si. Para obtener el valor de la funci´on suma en 0, calculamos la aportaci´on al t´ermino homog´eneo de grado 0 de cada unos de los sumandos. Primer sumando: 1/12y2 1+ 1/12y2 2+ 1/4y1y2 y1(y1−y2)=y2 1+y2 2+ 3y1y2 12y1y2(y1−y2). Numerador del segundo sumando: 9 2y2 1+1 12y2 1+(y2−y1)2 12 −3 2y2 1+3 2(y2−y1)−1 2y1(y2−y1) y la aportaci´on del segundo sumando es 95y2 2−23y1y2+y2 1 12y2(y1−y2) Tercer sumando: 95y2 1−23y1y2+y2 2 −12y1(y1−y2)) . Sumando todos y operando se obtiene 120y1y2(y1−y2) 12y1y2(y1−y2)= 10. Es decir el t´ermino independiente del desarrollo de Taylor de la funci´on ΓT(y)es el n´umero de puntos reticulares contenidos en T. Figura 2.3: Poliedros que aparecen en los ejemplos. Ejemplo 2.5. Veamos un nuevo ejemplo de este tipo de c´alculo para el n´umero de puntos reticulares. Consideremos el cuadril´atero Pde v´ertices {(0,0),(0,3),(3,0),(2,2)}. Cap´ıtulo 3. Una f´ormula para calcular el n´umero de puntos reticulares en un politopo. 32 m´as adelante vamos a ver que los ´unicos t´erminos no nulos son una cantidad finita; los que corresponden a los subespacios paralelos a las caras de K. Como en el sumatorio solo hay un subespacio Lde dimensi´on 0 que es el v´ertice, podemos escribir. Γ(1A, y) = ω(A, y)e⟨y,v⟩+X L:dimL>0 ω(A/L, y)ΦL(1A∩(L+v), y) y podemos definir ω(A, y) de manera recursiva. Si dimA = 0 entonces ω(A, y) = 1, si no ω(A, y) = e−⟨y,v⟩Γ(1A, y)−e−⟨y,v⟩X L:dimL>0 ω(A/L, y)ΦL(1A∩(L+v), y)) (3.3) Veamos a continuaci´on algunos ejemplos de c´alculo expl´ıcito de esta funci´on y de el valor que toma en 0. Ejemplo 3.1 (Conos unidimensionales.).En este ejemplo consideramos V=Rcon el producto escalar est´andar, Λ = Z,A= [α, ∞)con α∈Q. Entonces en el sumatorio de 3.3 solo existe un subespacio de dimensi´on >0, que es L=V. Γ(1A, y) = X m∈A∩Z emy = ∞ X m=⌈α⌉ emy =e⌈α⌉y 1−ey Por otro lado ΦL(1A, y) = Z[α,∞) eyξ dξ =−eαy y. As´ı que finalmente se obtiene: ω(A, y) = e−αy(e⌈α⌉y 1−ey+eαy y) (3.4) y si denotamos β=⌈α⌉ − αse tiene la siguiente expresi´on ω(A, y) = eβy 1−ey+1 y(3.5) Esta funci´on es anal´ıtica en un entorno de 0. Veamos que valor toma en 0 tomando el desarrollo de Taylor en el origen eβy 1−ey+1 y=y((1 + yβ +(βy)2 2+· · · )−(1 + y 2+y2 3! +· · · )) −y2(1 + y 2+y2 3! +· · · )=1 2−β+ (β2 2−β 2−1 12)y+· · · de modo que ω(A, 0) = 1 2−β Ejemplo 3.2 (Cono bidimensional regular con v´ertice en el origen.).Supongamos que Kes un cono punteado con v´ertice en el origen. Sean u1yu2sus vectores primitivos que verifican Cap´ıtulo 3. Una f´ormula para calcular el n´umero de puntos reticulares en un politopo. 33 |u1∧u2|= 1 . Vamos que forma tienen los elementos de la expresi´on 3.3. Por un lado Γ(1K, y) = 1 (1 −e⟨y,u1⟩)(1 −e⟨y,u2⟩), y como subespacios de dimensi´on positiva en el sumatorio deben aparecer V, span(u1)y span(u2). Para L=span(u1),V/L =L⊥es la recta perpendicular a u1y una base del ret´ıculo Z2/L es la proyecci´on de u2sobre L⊥, dada por w1=u2−⟨u1, u2⟩ ⟨u1, u1⟩u1 Calculamos ω(K/L, y), por un lado Γ(1K/L, y) = X K/L∩Z2/L e⟨m,y⟩= ∞ X k=1 e⟨nw1,y⟩=1 1−e⟨w1,y⟩ ΦL(1K∩L, y) = 1 ⟨w1, y⟩ de modo que ω(K/L, y) = 1 1−e⟨w1,y⟩+1 ⟨w1, y⟩ Para L=span(u2)se procede igual. Para L=Vse tiene ω(K/L, y) = 1 yΦL(1K∩L, y) = 1 ⟨y,u1⟩⟨y,u2⟩. Uniendo todas las expresiones y denotando α=⟨y, w1⟩yβ=⟨y, w2⟩se obtiene ω(K, y) = 1 (1 −e⟨y,u1⟩)(1 −e⟨y,u2⟩) + ( 1 1−eα+1 α)1 ⟨y, u1⟩+ ( 1 1−eβ+1 β)1 ⟨y, u2⟩ −1 ⟨y, u1⟩⟨y, u2⟩. (3.6) Y haciendo los c´alculos con los desarrollos de Taylor de forma similar al ejemplo anterior se obtiene ω(K, 0) = 1 4+⟨u1, u2⟩ 12 (1 ⟨v1, v1⟩+1 ⟨v2, v2⟩). Cap´ıtulo 3. Una f´ormula para calcular el n´umero de puntos reticulares en un politopo. 34 Ya hemos visto c´omo se define ω(A, y) cuando Aes la traslaci´on racional de un cono racional. Sin embargo, queremos ver que ωpuede ser extendida a una evaluaci´on con espacio de salida en Av(V). Es decir, queremos ver que ωrespeta las relaciones lineales entre funciones caracter´ısticas de traslaciones racionales de conos racionales. Es decir, que si fijado v∈Vracional, A1, A2, ...Am son traslaciones de conos racionales por vy se tiene una relaci´on del tipo: m X i=1 αi1Ai= 0 entonces se tiene que m X i=1 αiω(Ai, y)=0. Para demostrar esto, utilizaremos un lema que nos dice que basta probar un caso particular mucho m´as simple. Lema 3.1. Sean v∈Vracional, Wun espacio vectorial y θuna aplicaci´on que a cada traslaci´on A=v+Kdonde Kes un cono racional, le asigna un elemento θ(A)⊂W. Sea Hun hiperplano af´ın racional tal que v∈Hy sean H+yH−los correspondientes semiespacios cerrados que Hdelimita. Sean A+=A∩H+y A−=A∩H− Supongamos que para cada cono racional Ky cada hiperplano racional Hcon v∈Hse tiene la igualdad : θ(A) = θ(A+) + θ(A−)−θ(A∩H). Entonces la aplicaci´on θse puede extender a una evaluaci´on (transformaci´on lineal): Θ : Av−→ W de manera que Θ(1A) = θ(A)para todo cono Aque sea una traslaci´on A=K+vde un cono racional. Demostraci´on. Sin p´erdida de generalidad, consideraremos el problema trasladado al origen, es decir v= 0. Sean K1, K2, ..., Km⊂Vun conjunto de conos racionales y sea m X i=1 αi1Ki= 0 Cap´ıtulo 3. Una f´ormula para calcular el n´umero de puntos reticulares en un politopo. 35 una relaci´on lineal entre sus funciones caracter´ısticas. Nuestro objetivo ser´a probar que m X i=1 αiθ(Ki)=0 lo cual implicar´ıa que la aplicaci´on θse extiende a une evaluaci´on Θ. Si nombramos {Hi,j :j∈Ji}a los hiperplanos que delimitan las caras de cono Ki, y definimos H={Hi,j :i= 1,2, ..., m j ∈Ji}. Entonces los hiperplanos de Hdividen el espacio Ven una cantidad finita de conos racionales de dimensi´on m´axima tales que la intersecci´on de dos de ellos siempre tiene dimensi´on menor. Sea {Cj:j∈J}el conjunto de todos estos conos junto con todas sus caras no vac´ıas (que tambi´en ser´an conos de dimensi´on menor). Equivalentemente, este conjunto se puede definir como el de los conjuntos que son intersecci´on de semiespacios definidos por elementos de H y tales que al intersecarlos con cualquier otro semiespacio definido por un elemento de H, su dimensi´on disminuye. Nos interesa probar que las funciones 1Cjson linealmente independientes; supongamos que tenemos una relaci´on lineal X j∈J γj1Cj= 0. Nos fijamos en los Cjde dimensi´on m´axima, sabemos que cada par de estos interseca en otro Cide dimensi´on estrictamente menor. As´ı para cada jtal que Cjtiene dimensi´on m´axima se verifica que γj= 0. Si repetimos el argumento fij´andonos en los Cjde dimensi´on dim(V)−1 tambi´en se obtiene que para ellos γj= 0. Se repite el argumento reduciendo la dimensi´on hasta llegar a la cara de menor dimensi´on que tambi´en deber´a tener coeficiente nulo. Ahora observamos que para cada i= 1,2, ..., m podemos escribir 1Ki=X j∈J βij1Cj, para ciertos βij y aplicando la hip´otesis de forma recursiva podemos deducir que θ(Ki) = X j∈J βijθ(Cj). Entonces m X i=1 X j∈J αiβij1Cj= 0 y por ser linealmente independientes los 1Cjse tiene que Pm i=1 αiβij = 0 para cada j∈Jde Cap´ıtulo 3. Una f´ormula para calcular el n´umero de puntos reticulares en un politopo. 36 donde se deduce que m X i=1 αiθ(Ki) = m X i=1 X j∈J αiβijθ(Ki) = 0 como quer´ıamos demostrar. Una vez presentado este lema estamos en condiciones de demostrar que la aplicaci´on ω(A, y) que hemos definido, se extiende a una evaluaci´on y que verifica ciertas propiedades que nos interesan. Recordamos que M(V) es el espacio de funciones meromorfas en V. Teorema 3.1. Sean Vun espacio eucl´ıdeo, Λun ret´ıculo en Vyv∈Vun punto racional, entonces podemos considerar una evaluaci´on (aplicaci´on lineal) Ω : Av(V)−→ M(V) verificando las siguientes propiedades: 1. Sea K⊂Vun cono racional. Sea A=K+vsu traslaci´on racional y sea L⊂V un espacio reticular. Entonces la proyecci´on A/L ⊂V/L es la traslaci´on racional (respecto del ret´ıculo Λ/L) de un cono racional K/L ⊂V/L de manera que las funciones Ω(1A/L),Ω(1A)∈ M(V)est´an bien definidas y se verifica la identidad Γ(1A) = X L Ω(1A/L)ΦL(1A∩(L+v)) donde el sumatorio recorre todos los subespacios L⊂Vparalelos a las caras de A. 2. Si A=K+ves una traslaci´on racional de un cono racional K⊂Vque contiene alguna recta, entonces Ω(1A) = 0. 3. Si A=K+ves una traslaci´on racional de un cono racional K⊂V, entonces la funci´on Ω(1A)∈ M(V)es anal´ıtica en y= 0. Demostraci´on. Procederemos por inducci´on sobre dim(V) = d. Si d= 0, entonces Ω(f) = f(0) para toda f∈ Av(V) y se verifica cada punto del teorema. Para d≥1, como ya se ha desarrollado antes, si queremos que se verifique (1), vamos a definir recursivamente Ω(1A, y) = e−⟨y,v⟩Γ(1A, y)−e−⟨y,v⟩X L:dimL>0 Ω(1A/L)ΦL(1A∩(L+v), y) (3.7) Cap´ıtulo 3. Una f´ormula para calcular el n´umero de puntos reticulares en un politopo. 37 para A=K+vla traslaci´on por vde un cono racional Ky donde el sumatorio recorre los subespacios de dimensi´on positiva paralelos a las caras de A. Para ver (2), supongamos que Kcontiene una recta. Entonces es inmediato que Γ(1A) = 0. Tambi´en toda cara A∩(L+v) de dimensi´on positiva, contiene una recta de modo que ΦL(1A∩(L+v)) = 0, de modo que se tiene Ω(1A) = 0. Se concluye Ω(1A) = 0. Tambi´en hay que probar que la suma se puede extender a todos los subespacios reticulares de dimensi´on positiva, ya que solo los paralelos a las caras de Atienen un aporte no nulo. Es decir, queremos ver que si no hay una cara Fque genere L, entonces Ω(1A/L)ΦL(A∩(L+v)=0. Supongamos que L⊂span(K) con dim(F)> dim(L), entonces A/L es una traslaci´on de un cono K/L que contiene una recta y en consecuencia Ω(1A/L) = 0. Por otro lado, si se tiene que dim(L∩K)< dim(L). Ahora hay que demostrar que, as´ı definida, podemos extender Ω a una evaluaci´on en Av(V). Ya sabemos que para ello basta con probar el caso particular del lema anterior. Manteniendo las notaciones de dicho lema hay que probar que Ω(1A) = Ω(1A+) + Ω(1A−)−Ω(1A∩H). Como Γ y ΦLson evaluaciones, tenemos que Γ(1A) = Γ(1A+) + Γ(1A−)−Γ(1A∩H). y que ΦL(1A∩(L+v)) = ΦL(1A+∩(L+v))+ΦL(1A−∩)L+v))−ΦL(1A∩H∩(L+v)). Adem´as, las proyecciones preservan las relaciones lineales entre funciones caracter´ısticas de poliedros, entonces 1A/L =1A+/L +1A−/L −1A∩H/L y por hip´otesis de inducci´on Ω(1A/L) = Ω(1A+/L) + Ω(1A−/L)−Ω(1A∩H/L). Si definimos Π(A, L) := Ω(1A/L)ΦL(1A∩(L+v)) entonces observando la expresi´on de Ω(1A), basta probar que se verifica Π(A, L) = Π(A+, L) + Π(A−, L)−Π(A∩H, L).(3.8) Sea Funa cara no vac´ıa de A, consideremos los posibles casos que podr´ıan darse y veamos que se verifica la igualdad en cada uno de ellos. Cap´ıtulo 3. Una f´ormula para calcular el n´umero de puntos reticulares en un politopo. 38 (a) F⊂H (b) Fest´a en contenida en H+. (c) Fest´a contenida en H−. (d) Hpasa por un punto del interior de Fde forma transversal. (e) Les un subespacio paralelo a una cara G=F∩Hde A∩Hdonde Fes una cara de A, Hpasa por un punto interior de Fy lo interseca de manera transversal. Figura 3.1: Cono Ade dimensi´on 3 y las posibles posiciones de un hiperplano H, una cara F de Ay una cara Gde A∩H. Supongamos que estamos en el caso (a), entonces se tiene que A∩(L+v) = A+∩(L+v) = A−∩(L+v) = A∩H∩(L+v). Entonces, como hemos visto que se tiene Ω(1A/L) = Ω(1A+/L) + Ω(1A−/L)−Ω(1A∩H/L), se verifica 3.8. Supongamos ahora que se tiene (b), F⊂H+. Entonces se tiene que A/L =A+/L y entonces dim(A−∩(L+v)) < dim(L) y dim(A+∩(L+v)) < dim(L). As´ı se tiene que Π(A, L) = Π(A+, L) y que Π(A−, L) = Π(A∩H, L)=0 Cap´ıtulo 3. Una f´ormula para calcular el n´umero de puntos reticulares en un politopo. 39 y se tiene la igualdad pedida. Para el caso (c) se razona de forma an´aloga. Supongamos que Les paralelo a una cara Fde Ade forma que Hpasa por un punto interior de Fy lo corta transversalmente. Entonces A/L =A+/L =A−/L, ΦL(1A∩H∩(L+v)) = 0 y como Φ es una evaluaci´on se tiene la condici´on pedida. Finalmente, si se tiene el caso (e) entonces A∩(L+v) = A+∩(L+v) = A−∩(L+v) = A∩H∩(L+v) y se verifica la condici´on ya que Ω(1A/L) = Ω(1A+/L) + Ω(1A−/L)−Ω(1A∩H/L). Observamos que cada cara de A+(respectivamente de A−) es, o bien la intersecci´on de una cara de Acon H+(respectivamente de A+) o bien la intersecci´on de una cara de Acon H. Tambi´en, cada cara de A∩Hes la intersecci´on de una cara de Acon H. De modo que, restringirnos a los subespacios del tipo (a)-(e) basta para concluir que Ω(1A) = Ω(1A+) + Ω(1A−)−Ω(1A∩H). Para acabar de demostrar el teorema necesitamos demostrar que Ω(1A, y) es una funci´on anal´ıtica en y= 0, para ello vamos a proceder por inducci´on sobre d=dim(V). Supongamos que A=K+ves la traslaci´on de un cono racional Kque no contiene rectas y es de dimensi´on m´axima. Sino fuese de dimensi´on m´axima, lo podr´ıamos considerar como un cono de span(K) y habr´ıamos terminado. Ahora vamos a utilizar que todo cono Kracional que no contiene rectas de dimensi´on m´axima, puede ser escrito como combinaci´on lineal de conos regulares racionales de dimensi´on m´axima m´odulo conos racionales que no contienen rectas (resultado 1.8). Como ya hemos visto que Ω es una evaluaci´on basta probar que Ω(1A) = ω(K+v) es una funci´on anal´ıtica en y= 0 siendo K=co(u1, u2, ..., ud) y {u1, u2, ..., ud}una base de Λ. Antes de ver c´omo queda la f´ormula es necesario tener en cuenta lo siguiente. En el teorema 2.1 hab´ıamos visto la evaluaci´on Ψ para poliedros con v´ertices en puntos reticulares. En este caso nos interesa poder considerar la evaluaci´on en el caso de que los v´ertices sean puntos racionales del ret´ıculo Λ. Es decir, puntos vtales que existe q∈Ztal que qv ∈Λ. En particular, nos interesa que esta evaluaci´on exista para los conos regulares con v´ertice en un punto racional. Cap´ıtulo 3. Una f´ormula para calcular el n´umero de puntos reticulares en un politopo. 40 En este caso concreto, no es dif´ıcil construir esta extensi´on. La idea es que si A=v+K=v+co(u1, u2, ..., ud) siendo {u1, u2, ..., ud}una base de Λ buscamos un punto w∈Λ que verifique que Λ∩(w+co(u1, ..., ud) = Λ ∩(v+co(u1, ..., ud). Este w∈Λ lo denotaremos por w=⌈v⌉Ky se construye de la siguiente forma. Si expresamos ven la base {u1, u2, ..., ud}: v= d X i=1 αiuientonces ⌈v⌉K= d X i=1 ⌈αi⌉ui. Una vez visto esto, Γ(1A) = Γ(1K+v) = e⟨y,w⟩Γ(1K) = e⟨y,w⟩ d Y i=1 1 1−e⟨y,ui⟩. Adem´as, ya hemos visto que los subespacios Lque aparecen en la expresi´on de Ω(1A) son aquellos paralelos a las caras de A. Es decir son subespacios de la forma L=LI=span(ui:i∈I⊂ {1,2, ..., d}. Entonces ΦL(1A∩(L+v)=e⟨y,v⟩Y i∈I 1 ⟨−y, ui⟩. Por hip´otesis de inducci´on se tiene que Ω(1A/L) es una funci´on anal´ıtica en y= 0. Entonces observando la expresi´on de Ω(1A) (3.7) tenemos Ω(1A, y) = e−⟨y,v⟩e⟨y,w⟩ d Y i=1 1 1−e⟨y,ui⟩−e−⟨y,v⟩X L:dimL>0 e⟨y,v⟩Y i∈I 1 ⟨−y, ui⟩(3.9) Es decir, que Ω(1A) es una funci´on meromorfa y sus posibles polos en un entorno de y= 0 se encontrar´ıan en los hiperplanos ⟨y, ui⟩= 0.Para demostrar que en efecto es anal´ıtica en y= 0 basta demostrar que Ω(1A, y)⟨y, ui⟩ es id´enticamente nula en el hiperplano ⟨y, ui⟩= 0. Prob´emoslo sin p´erdida de generalidad para i= 1. Cap´ıtulo 3. Una f´ormula para calcular el n´umero de puntos reticulares en un politopo. 41 Primero, observemos que ⟨y, u1⟩ 1−e⟨y,u1⟩=−U−1(⟨y, u1⟩) vale −1 en los puntos del hiperplano ⟨y, u1⟩= 0. De modo que al multiplicar por ⟨y, u1⟩la expresi´on 3.9 se obtiene: Ω(1A, y)⟨y, u1⟩=−e⟨y,w−v⟩ d Y i=2 1 1−e⟨y,ui⟩+X I⊂{1,...,d}: 1∈I Ω(1A/LI)Y i∈I\{1} 1 ⟨y, ui⟩.(3.10) Consideremos ahora la proyecci´on sobre el complemento ortogonal de span(u1). As´ı, denotamos A′=A/span(u1), u′ i=ui/span(u1), K′=co(u′ 1, u′ 2, ..., u′ d)yΛ′el ret´ıculo generado por los vectores u′ 2, ..., u′ d. Entonces K′es un cono (d−1)-dimensional regular con respecto al ret´ıculo Λ′. Como y es ortogonal a u1, entonces se tiene ⟨c, ui⟩=⟨c, u′ i⟩para i= 2, ..., d y podemos reescribir la expresi´on 3.10 como Ω(1A′)−e⟨y,w′−v′⟩ d Y i=2 1 1−e⟨y,u′ i⟩+X I⊂{2,...,d}:I=∅ Ω(1A′/LI)Y i∈I 1 ⟨−y, u′ i⟩ Y podemos reescribir esta expresi´on como Ω(1A′)−e−⟨y,v′⟩Γ(1A′) + e−⟨y,v′⟩X L:dimL>0 Ω(1A′/L)ΦL(1(A′+(L+v))) y por la expresi´on 3.7 se tiene que esta expresi´on vale 0 y hemos finalizado la demostraci´on. 3.2. La f´ormula de Berline-Vergne. Ahora vamos a ver como se puede utilizar esta evaluaci´on Ω y el hecho de que sea anal´ıtica en y= 0 para construir una nueva expresi´on para el n´umero de puntos reticulares de un politopo. Para ello se presenta el siguiente teorema que es central en este trabajo. Teorema 3.2. Sea Vun espacio vectorial con un ret´ıculo Λy sea P⊂Vun politopo racional. Para cada cara Fde P, definimos los valores vol(F)yα(P, F)de la siguiente forma: sea L=LF⊂Vel subespacio vectorial paralelo a F. En Lnormalizamos la medida de Lebesgue de manera que det(Λ ∩L) = 1 denotamos vol(F)la medida de Lebesgue de Ftras realiza dicha normalizaci´on. Sea tcono(P, F)el cono tangente de Pen un punto interior de Fy sea A=AF=tcono(P, F)/L la proyecci´on ortogonal de tcono(P, F)sobre L⊥. Entonces,definimos Cap´ıtulo 4. El cambio exponencial para semigrupos num´ericos. 48 Veamos ahora qu´e es lo que se sabe sobre la obtenci´on de estas funciones racionales a partir de los generadores a1, a2, ..., andel semigrupo S. Proposici´on 4.2. Sea Sel semigrupo generado por aybcon mcd(a, b)=1, entonces la funci´on generatriz del semigrupo ℓS(x)se puede expresar como: ℓS(x) = 1−xab (1 −xa)(1 −xb) Demostraci´on. El semigrupo Ses S={αa +βb : (α, β)∈N2}. Representamos todos los elementos (algunos repetidos) del semigrupo en la siguiente tabla. ··· ··· ··· ··· ··· ··· ··· ab +b b +ba +a b +ba + 2a· · · · · · · · · · · · ab ab +a ab + 2a· · · · · · 2ab · · · (a−1)b(a−1)b+a(a−1)b+ 2a· · · · · · (a−1)b+ba · · · · · · · · · · · · · · · · · · · · · · · · · · · 2b2b+a2b+ 2a· · · 2b+ (b−1)a2b+ba 2b+ba +a· · · b b +a b + 2a· · · b+ (b−1)a b +ba b +ba +a· · · 0a2a· · · (b−1)a ba ba +a· · · Cuadro 4.1: Representaci´on de los elementos del semigrupo S Observamos que en la regi´on encuadrada, que llamaremos R, est´an representados de forma ´unica cada uno de los elementos del semigrupo. En efecto, los elementos de esta regi´on son R={αa +βb : 0 ≤β≤(a−1), α ∈N} Si s=α′a+β′b∈Sentonces: Si β′≤a−1 entonces s∈R Si β′≥aentonces puedo escribir β′=ak+rcon r≤a−1 para obtener s=a(α′+k)+rβ y entonces s∈R. Adem´as los elementos del semigrupo aparecen una ´unica vez en R; si tenemos s=α′a+β′b=αa +βb con β, β′< a entonces, al ser aybcoprimos se tiene que βb ≡β′b(mod a)⇒β′=βy en consecuencia α′=α. Cap´ıtulo 4. El cambio exponencial para semigrupos num´ericos. 49 Ahora, teniendo en cuenta que P∞ m=0 xm=1 1−xy que Pk m=0 xm=1−xk+1 1−x, al sumar los elementos de la banda se obtiene: ℓs(x) = a−1 X β=0 ∞ X α=0 xαa+βb =1 1−xa a−1 X β=0 (xb)β=1 1−xa·1−(xb)a−1+1 1−xb= =1−xab (1 −xa)(1 −xb). El problema de obtener esta funci´on racional se vuelve notablemente m´as complicado al aumentar el n´umero nde generadores del semigrupo S. Para n= 3, en [8] se demuestra que la funci´on generatriz de S(a1, a2, a3), se puede escribir como X m∈S xm=1−xp1−xp2−xp3+xp4+xp5 (1 −xa1)(1 −xa2)(1 −xa3) donde los exponentes pison enteros no necesariamente distintos que dependen de los generadores a1, a2ya3. Para n= 4, en [11] se demuestra que para un semigrupo S=S(a1, a2, a3, a4) se tiene que X m∈S xm=p(x) (1 −xa1)(1 −xa2)(1 −xa3)(1 −xa4) donde p(x) es un polinomio cuyo n´umero de monomios con coeficiente no nulo puede ser arbitrariamente grande dependiendo de los generadores ai. Es decir, el car´acter sencillo de la funci´on racional asociada al semigrupo desaparece al aumentar el n´umero de generadores. Sin embargo A.Barvinok y K.Woods demuestran en [3] que, fijado el n´umero de generadores n, la funci´on generatriz del semigrupo generado por a1, a2, ..., an que hab´ıamos visto que tiene la forma ℓS(x) = n Y i=1 p(x) 1−xai puede ser calculada en tiempo polin´omico. No obstante, existen expresiones expl´ıcitas precisas para el polinomio p(x) que se estudiar´an en un trabajo posterior. Cap´ıtulo 4. El cambio exponencial para semigrupos num´ericos. 50 4.2. El cambio exponencial en funciones generatrices de semigrupos num´ericos. Vamos ahora c´omo podemos aprovechar el cambio de variable que hemos presentado para obtener informaci´on sobre los huecos de un semigrupo. Sea Hel conjunto de huecos de un semigrupo S, entonces se tiene que S=N\Hy en consecuencia se tiene la expresi´on: ℓS(x) = X m∈S xm=X m∈N xm−X h∈H xh=1 1−x−X h∈H xh. Es aqu´ı donde vamos a hacer el cambio de variable y definimos ¯ ℓS(y) ¯ ℓS(y) = ℓS(ey) = 1 1−ey−X h∈H ey. Para el primer sumando, consideramos el desarrollo de Taylor de la funci´on exponencial: 1 1−ey=1 −y·(1 + y/2 + y2/3! + · · · )=−1 y·U=−U−1 y con U−1= 1 −1/2y+ 1/12y2−1/720y4+· · · . Denotamos por fjal coeficiente j-´esimo de esta serie, ya hemos visto que estos dependen de los coeficientes de los Polinomios de Todd. Para el segundo sumando X h∈H ey=X h∈H ∞ X j=0 (hy)j j!=|H|+ ∞ X j=1 X h∈H (hy)j j! Entonces hemos obtenido que: ℓS(ey) = −1 y ∞ X j=0 fjyj− |H| − ∞ X j=1 (hy)j j!= ∞ X j=−1 ajyj. Es decir, los coeficientes de la serie de Laurent asociada a la funci´on del semigrupo tras el cambio exponencial nos proporciona informaci´on acerca de los huecos del semigrupo. Estos coeficientes son (a−1=−1 aj=fj+1 −1 j!Ph∈Hhj=fj+1 −1 j!Njpara j = 0,1,2, ... (4.3) Cap´ıtulo 4. El cambio exponencial para semigrupos num´ericos. 51 Es decir, del coeficiente a0=1 2− |H|se deduce |H|=gel n´umero de huecos del semigrupo, al que denotaremos g, del coeficiente a1se deduce la suma N1de los huecos del semigrupo, del coeficiente a2la suma N2de los cuadrados de los huecos... y as´ı sucesivamente. Ahora, nos interesa saber cu´antos de estos t´erminos Nies necesario conocer para determinar los huecos del semigrupo h1, h2, ..., hg. Es decir, tenemos un sistema de la forma:                h1+h2+· · · +hg=N1 h2 1+h2 2+· · · +h2 g=N2 · · · hi 1+hi 2+· · · +hi g=Ni · · · (4.4) y queremos saber cu´antas ecuaciones necesitamos para determinar h1, h2, ..., hg. Observamos que para un semigrupo distinto de N, el primer hueco es siempre h1= 1. De modo que el sistema que nos interesa es:                h2+· · · +hg=N1−1 h2 2+· · · +h2 g=N2−1 · · · hi 2+· · · +hi g=Ni−1 · · · (4.5) Estos t´erminos Ni−1 son las sumas de Newton del polinomio m´onico PSque tiene a h2, ..., hgcomo ra´ıces. Utilizando las identidades de Newton es posible, a partir de estos t´erminos N1, N2, ..., Ng−1, obtener los coeficientes del polinomio PS, que llamaremos polinomio de huecos. Los coeficientes bkse obtienen recursivamente a partir de los Nkcomo:                      b0= 1 b1=−N1 b2=1 2(−N2b0−N1b1) b3=1 3(−N3b0−N2b1−N1b2) · · · bg−1=1 g−1(−Ng−1b0−Ng−2b1−... −N1bg−2) (4.6) Observaci´on 4.1.Al hacer el desarrollo de Laurent de la funci´on ℓS(ey), y con todo lo anterior se obtiene una serie ¯ ℓS(y) = ℓS(ey) = −y−1+a0+a1y+a2y2+· · · +akyk+· · · . Cap´ıtulo 4. El cambio exponencial para semigrupos num´ericos. 52 Las relaciones entre los coeficientes ajde ¯ ℓS(y), los coeficientes bkdel polinomio de huecos y las sumas de Newton Nison las expresadas anteriormente. Hemos visto que basta con observar hasta el t´ermino ag−1para determinar el semigrupo S a partir de sus huecos h1, h2, ..., hg. No sucede as´ı al hacer el desarrollo en Taylor de la serie ℓS(x). En efecto, para los semigrupos S=S(5,6,9) = {5,6,9,10,11,12,13, c = 14, ...}con g = 7 S′=S(5,6,9,13) = {5,6, c = 9, ...}con g′= 6 se tiene que los desarrollos de Taylor de ℓS(x) y ℓS′(x) coinciden hasta el t´ermino 12. Mientras que tras hacer el cambio exponencial basta con desarrollar hasta el t´ermino 5 y 6 respectivamente. Veamos un ejemplo sencillo en el que realizar estos c´alculos. Ejemplo 4.2. Consideramos el semigrupo generado por 3 y 4 S(3,4) = {α3 + β4 : (α, β)∈N2} Por inspecci´on, se tiene que su conjunto de huecos es HS={1,2,5}. Por la proposici´on 4.2 sabemos que ℓS(x) = 1−x12 (1 −x3)(1 −x4). Y entonces ℓS(ey) = 1−e12y (1 −e3y)(1 −e4y)=−(1 + 12y 2+(12y)2 3! +· · · )(1 −3y 2+(3y)2 12 +· · · )(1 −4y 2+(4y)2 12 +· · · ) y y podemos ir obteniendo los t´erminos a−1, a0, a1, ... a−1=−1, a0=−5 2, a1=−97 12 , a2=−15 de donde se deduce que g= 3, N1= 8, N2= 30. Y sabemos que los huecos ordenados h1, h2, h3verifican (h1+h2+h3= 8 h2 1+h2 2+h2 3= 30 (4.7) Como adem´as el primero de los huecos ha de ser 1, tenemos el sistema Cap´ıtulo 4. El cambio exponencial para semigrupos num´ericos. 53 (h2+h3= 7 h2 2+h2 3= 29 (4.8) y utilizando las identidades de Newton se obtiene el polinomio P(t) = t2−7t+ 10 que tiene como ra´ıces a los huecos distintos de uno del semigrupo. En el ap´endice A se describe el c´odigo de una funci´on que dada la funci´on generatriz de un semigrupo S(m1, m2, m3), devuelve su polinomio de huecos. Con dicha funci´on se han calculado los siguientes ejemplos. Ejemplo 4.3. Para el semigrupo S(4,6,13) con g= 8 yc= 16, se tiene PS(t) = t7−52t6+ 1095t5−12050t4+ 74399t3−255888t2+ 450585t−311850. Ejemplo 4.4. Para el semigrupo S(5,6,9) con g= 7 yc= 14 se tiene PS(t) = t6−37t5+ 529t4−3739t3+ 13750t2−24952t+ 17472. 4.3. Series de Poincar´e de semigrupos num´ericos. En esta secci´on estudiaremos una nueva forma de escribir la funci´on generatriz de un semigrupo num´erico S⊂N. Para ello consideraremos el semigrupo como un subconjunto de Zde modo que el conjunto de huecos ser´a H=Z\S={..., −3,−2,−1} ∪ (N\S) ygser´a el n´umero de huecos positivos: g= #(N\S)<∞. Entonces el conjunto Hcontiene a todos los enteros negativos y a los huecos positivos. Se tienen las series indicatrices ℓS(t) = X m∈S tm, ℓH(t) = X h∈H th.(4.9) Ambas son series de Laurent con coeficientes enteros que verifican ℓS+ℓH=· · · +t−2+t−1+1+t+t2+· · · y por lo tanto (t−1)(ℓS+ℓH) = 0 Cap´ıtulo 4. El cambio exponencial para semigrupos num´ericos. 54 y si definimos los conjuntos I={s∈S:s−1∈H}, J ={h∈H:h−1∈S}.(4.10) Es decir, el conjunto de elementos del semigrupo tal que el anterior elemento no est´a en el semigrupo y el conjunto huecos tales que el elemento anterior est´a en el semigrupo. Es claro que estos dos conjuntos son finitos y que se tiene la relaci´on (t−1)ℓS=−(t−1)ℓH=X r∈J tr−X s∈I ts. As´ı, (t−1)ℓSy−(t−1)ℓHson polinomios y en consecuencia ℓSyℓHson series de Laurent racionales. Como ya definimos en el cap´ıtulo2, las series de Laurent racionales (RL) son aquellas series de Laurent spara las que existen dos polinomios p, q ∈Q[x] con q= 0 de forma que q·s=p. Para ellas, est´a bien definida la aplicaci´on F:RL −→ Q(x) definida por F(s) = p qy es un homomorfismo de PL-m´odulos. Entonces definimos la serie de Poincar´e de SPSy la serie de Poincar´e de HPHcomo: PS=F(ℓS) = Ps∈Its−Pr∈Jtr 1−t,PH=F(ℓH) = Pr∈Jtr−Ps∈Its 1−t y verifican PS+PH= 0. Se definen tambi´en el polinomio de Poincar´e de SQSy el polinomio de Poincar´e de HQH como QS=X s∈I ts−X r∈J tr,QH=X r∈J tr−X s∈I ts=−QS. Ejemplo 4.5. Para el semigrupo S=S(5,6,9) = {0,5,6,9,10,11,12, c = 14, ...}se tiene I={0,5,9,14},J={1,7,13}. QS= 1 −t+t5−t7+t9−t13 +t14 =−QH. Proposici´on 4.3. Los coeficientes de los polinomios QSyQHson 1 y -1 altern´andose seg´un crecen los exponentes de I∪J. Adem´as, cualquiera de ellos determina el semigrupo S. Demostraci´on. El m´ınimo de I∪Jes 0 ∈I, el m´ınimo de Jes 1. Despu´es de 1, los siguientes enteros son huecos hasta llegar al segundo elemento de I, desde este elemento hasta el segundo elemento de Json enteros que pertenecen a S, luego siguen huecos consecutivos y se sigue razonando igual alternando los signos. Observando los bloques de huecos y elementos del semigrupo queda determinado el semigrupo S. Cap´ıtulo 4. El cambio exponencial para semigrupos num´ericos. 55 El n´umero de Frobenius fes el m´aximo elemento de Hya que a partir del conductor c=f+ 1 no hay m´as huecos. Definimos el siguiente conjunto H′:= {h∈H:f−h /∈H} ⊂ H. Definici´on 4.1. Diremos que un semigrupo Ses sim´etrico si H=H′. Es decir, un semigrupo es sim´etrico si siempre que restamos un hueco hal n´umero de Frobenius fobtenemos un elemento del semigrupo. Por ejemplo S1=S(5,6,9) es un semigrupo sim´etrico, pero S2=S(5,6,7,8,9) no lo es. Los huecos de S2son H={..., −3,−2,−1} ∪ {1,2,3,4}yH′ 2={..., −3,−2,−1} ∪ {4}. Es decir, hay 3 elementos en H\H′. Cuando Ses sim´etrico fes impar, ces par y g=c 2ya que en [0, f]∩Zla mitad son elementos de Sy otra mitad son huecos. Definici´on 4.2. Decimos que un elemento m∈Ses irreducible si no existen m1, m2∈S\{0} tales que m=m1+m2. Denotaremos por eal n´umero de elementos irreducibles de un semigrupo S. Proposici´on 4.4. (a) fes el m´aximo de H′. (b) Si h1, h2∈Hentonces h1+h2−f∈H′. (c) H′={f−m:m∈S} (d) e={h∈H′:f+h=h1+h2∀h1, h2∈H′\{f}} Demostraci´on. Para demostrar (a) basta darse cuenta de que f∈H′ya que f−f= 0 /∈H. (b)h1, h2∈H′entonces f−h1, f −h2∈Syf−(h1+h2−f)∈Sde modo que h1+h2∈H′. (c) Si h∈H′entonces f−h /∈Hy entonces m=f−h∈Sde modo que h=f−m. Rec´ıprocamente, si h=m−fcon m∈Sentonces f−h∈Syh∈H′. (d)h∈H′,h=f−mcon m∈S, dicho mes irreducible si y solo si m=f−h=n1+n2 con n1, n2∈S{0}. De modo que f−h= (f−h1)+(f−h2) con h1, h2∈H′\{f}si y solo si f+h=h1+h2,h1, h2∈H′\{f}. Se presenta ahora un problema abierto para semigrupos num´ericos que es la conjetura de Wilf. Conjetura 4.1 (Wilf, 1978).Para todo semigrupo num´erico Sse tiene la siguiente desigualdad: e(c−g)≥c Cap´ıtulo 4. El cambio exponencial para semigrupos num´ericos. 56 Ejemplo 4.6. Para el semigrupo S1=S(5,6,9),f= 13 H′=H={..., −3,−2,−1}∪{1,2,3,4,7,8,13} e= 3 porque 5, 6 y 9 son los irreducibles (o, utilizando (d) porque solo f+ 8 = 21,f+ 7 = 20 yf+ 4 = 17 no son suma de elementos de H′\{13}. La conjetura de Wilf afirma: 3(14 −7) ≥14 Ejemplo 4.7. Para el semigrupo S2=S(5,6,7,8,9),f= 4 H′={..., −3,−2,−1}∪{4} e= 5 porque 5,6,7,8y9son los irreducibles de S2(o porque f= 4,f−1 = 3,f−2 = 2, f−4 = 0 yf−5 = −1no son suma de elementos de H′\{4}={..., −3,−2,−1}) y la conjetura de Wilf afirma 5(5 −4) ≥5. Hay varios casos para los que ya se ha probado que la conjetura de Wilf se verifica: Si e≤4. Si Ses un semigrupo irreducible (i.e. no se puede escribir como intersecci´on de semigrupos). Si Ses un semigrupo sim´etrico. Si Stiene un sistema de generadores que es una progresi´on aritm´etica Si c≤4 c−g Si Ses un semigrupo con g≤60. En [7] se recopila la informaci´on que se tiene hasta hoy acerca de este problema combinatorio y se exponen muchos m´as casos para los que la conjetura es cierta. 4.4. Perspectivas y conclusiones. Para finalizar este trabajo vamos a recapitular los diferentes escenarios que hemos repasado. La situaci´on general es que tenemos una cierta informaci´on, en los casos estudiados se trata de la lista de puntos reticulares de un poliedro, los elementos de un semigrupo num´erico y el volumen de un politopo, que est´a expresada en una funci´on generatriz(en los casos mencionados se trata Cap´ıtulo 4. El cambio exponencial para semigrupos num´ericos. 57 de una serie de Laurent, una serie de potencias y una funci´on racional respectivamente). Para los dos primeros, tenemos la informaci´on expresada en una serie de potencias en las variables x y hemos realizado el cambio de variables x7→ eyobteniendo as´ı una expresi´on de esta serie en las variables y. Para el caso del volumen la informaci´on viene dada directamente en las variables yy est´a vinculada no a una serie sino a una integral que depende de los par´ametros y. Para que el cambio exponencial sea viable, se requiere frecuentemente sustituir la informaci´on disponible por la de su imagen a trav´es de una evaluaci´on apropiada. En los tres casos anteriores se tiene la siguiente situaci´on: al multiplicar las expresiones en ypor un cierto polinomio q(y), que es producto de formas lineales, se obtiene una serie de potencias s∈SP. Por lo tanto, el cociente s qes un elemento de SP(1) y por lo tanto tambi´en de SP(0). De hecho en algunos casos, esta serie sser´a convergente y entonces estar´a en SC(1) o incluso definir´a una funci´on entera y estar´a en H(1). Este ´ultimo es el escenario que se tiene en los tres casos antes mencionados. No sucede as´ı por ejemplo con la evaluaci´on Ω del cap´ıtulo 3, en la que solo se tiene que ses convergente. Otro caso relevante, no considerado en la memoria es el de las series de Poincar´e asociadas a filtraciones por multi´ındices, para las cuales spuede ser una serie de potencias no convergente en general. Cuando se realiza el cambio exponencial, la mencionada situaci´on se detecta antes de realizar el cambio si la informaci´on viene dada por una serie (en general de Laurent) cuyo producto con un producto de polinomios del tipo (xm−1) es una serie de potencias que define una funci´on anal´ıtica para la que el cambio exponencial es viable. Al cociente s qlo llamaremos expresi´on exponencial del la funci´on generatriz correspondiente. Si consideramos la expresi´on como serie de potencias de s s=s0+s1+s2+· · · se tiene que s q=s0 q+s1 q+s2 q+· · · de modo que si des el grado de q, entonces la componente homog´enea de grado k−des la funci´on racional homog´enea sk q. La definici´on de expresi´on exponencial de una cierta funci´on generatriz genera de forma natural otros problemas interesantes. Uno de ellos podr´ıa ser: ¿cu´antos t´erminos sk qdel desarrollo son necesarios para recuperar la informaci´on que ten´ıamos antes de hacer el cambio?. Naturalmente, los infinitos t´erminos de la expresi´on determinan la informaci´on; la pregunta es qu´e cantidad finita de t´erminos es suficiente. Para el caso de semigrupos num´ericos ya se ha demostrado que el n´umero de huecos ges el t´ermino independiente del desarrollo de dicha serie y que basta con calcular g−1 t´erminos para determinar qui´enes son estos huecos. Es decir, para recuperar toda la informaci´on hay que