p-grupos finitos

Universitat de València Facultat de Matemàtiques Departament d’Àlgebra p-Grupos Finitos Autor: Ramón Esteban Romero Director: Dr. D. Antonio Vera López Memoria presentada para optar al grado de Doctor en Ciencias Matemáticas Valencia, 1997 2 3 4 Índice general Introducción 11 I El vector de conjugación de un p-grupo finito 15 1. Número de clases de longitud máxima 17 1.1. Definiciones y resultados previos . . . . . . . . . . . . . . . . . 17 1.2. Resultados sobre s........................ 21 1.3. Caso br(G)máximo ........................ 29 1.3.1. Los vectores de conjugación . . . . . . . . . . . . . . . 32 1.3.2. Estudio de G/Z(G).................... 38 1.3.3. Cuestiones aritméticas . . . . . . . . . . . . . . . . . . 40 1.3.4. Estudio del exponente de estos grupos . . . . . . . . . 44 1.4. Conjeturas y problemas abiertos . . . . . . . . . . . . . . . . . 47 1.4.1. Conjetura “class-breadth” . . . . . . . . . . . . . . . . 47 1.4.2. Conjeturas sobre grupos con br(G) = pm−b−1. . . . . . 48 II p-grupos de clase maximal 51 2. Preliminares 53 2.1. Conceptosbásicos......................... 53 2.2. Cotasanteriores.......................... 73 2.3. Construcción de álgebras de Lie . . . . . . . . . . . . . . . . . 78 5 6ÍNDICE GENERAL 2.4. Cotas en función de byl..................... 79 2.5. Cotas en función de c0yl.................... 89 2.6. Cotas para c0≤5......................... 94 3. Cotas para 6≤c0≤10 105 3.1. Introducción............................105 3.2. Elalgoritmo............................106 4. Nuevas cotas 135 4.1. Resultados obtenidos a partir de las zi.............135 4.2. Lasconjeturas...........................138 4.3. Cotas de la forma 2c≥m−p−2l+c0..............156 4.4. Cotas del tipo 2c≥m−p−1..................176 4.5. Cotas del tipo 2c≥m−2l−c0−1...............180 4.6. Cotas del tipo 2c≥m−p−2l+c0−1.............191 4.6.1. El caso p−c0= 2l−4..................193 4.6.2. El caso p−c0= 4l−6..................196 4.6.3. El caso p−c0= 4l−8..................198 4.6.4. Los determinantes . . . . . . . . . . . . . . . . . . . . 200 4.7. Un ejemplo de las soluciones para p= 17 ............217 A. Listados de los programas utilizados 223 A.1.Cerosynoceros..........................223 A.1.1. El archivo bullet.h ...................223 A.1.2. El archivo bulletvl.h ..................226 A.1.3. El archivo Makefile ...................229 A.1.4. El archivo arbol.c ....................231 A.1.5. El archivo despeje.c ...................233 A.1.6. El archivo fraccion.c ..................236 A.1.7. El archivo casilla.c ...................240 A.1.8. El archivo output.c ...................241 A.1.9. El archivo primos.c ...................246 A.1.10.El archivo triang.c ...................248 ÍNDICE GENERAL 7 A.1.11.El archivo bullet.c ...................250 A.1.12.El archivo zeta.c .....................253 A.1.13.El archivo zeta2.c ....................255 A.1.14.El archivo gros.c .....................264 A.1.15.El archivo fraccionvl.c .................271 A.1.16.El archivo casillavl.c .................281 A.1.17.El archivo zetavl.c ...................282 A.1.18.El archivo outputvl.c ..................294 A.1.19.El archivo primosvl.c ..................299 A.1.20.El archivo despejevl.c .................301 A.1.21.El archivo jacobi1.c ...................303 A.2. Algoritmo de cálculo de cotas . . . . . . . . . . . . . . . . . . 319 A.2.1. El archivo factors.c ...................319 A.2.2. El archivo pjacobi.c ...................323 A.2.3. El archivo power.c ....................323 A.2.4. El archivo legendre.c ..................324 A.2.5. El archivo shanks.c ...................326 A.2.6. El archivo modular.c ...................328 A.2.7. El archivo quadr.c ....................340 A.2.8. El archivo jacarbol.c ..................341 A.2.9. El archivo pjacobi.h ...................349 A.2.10.El archivo Makefile ...................358 Bibliografía 361 Índice de materias 365 8ÍNDICE GENERAL Índice de cuadros 1.1. Los 3-grupos de orden menor o igual que 729 con br(G)máximo 30 1.2. Los 2-grupos de orden menor o igual que 256 con br(G)máximo 31 3.1. Número de configuraciones para la generación de triángulos . . 110 3.2. Tiempos de cálculo para el segundo algoritmo . . . . . . . . . 111 3.3. Cotas obtenidas con la identidad de Jacobi . . . . . . . . . . . 118 3.4. Álgebras de Lie para c0= 6 ...................119 3.5. Álgebras de Lie para c0= 7 ...................120 3.6. Álgebras de Lie para c0= 8 ...................121 3.7. Álgebras de Lie para c0= 9 ...................122 3.8. Álgebras de Lie para c0= 10 ...................123 3.9. Álgebras de Lie correspondientes a los casos especiales con c0 par.................................133 3.10.Losotroscasos ..........................134 4.1. Cotas para p= 5 (Blackburn, [2]) . . . . . . . . . . . . . . . . 139 4.2. Cotas para p= 7 (Shepherd, [22]) . . . . . . . . . . . . . . . . 139 4.3. Cotas para p= 11 .........................139 4.4. Cotas para p= 13 .........................140 4.5. Cotas para p= 17 .........................140 4.6. Cotas para p= 19 .........................141 4.7. Cotas para p= 23 .........................142 4.8. Cotas para p= 29 .........................143 4.9. Cotas para p= 31 .........................144 9 Capítulo 1 Algunas cuestiones sobre el número de clases de conjugación de longitud máxima de un p-grupo finito 1.1. Definiciones y resultados previos En todo este capítulo, supondremos que Ges un p-grupo finito de orden pm. Denotaremos por rG(S)el número de clases de conjugación de Gque cortan al subconjunto S, en particular, denotaremos r(G) = rG(G). Si Ses un subconjunto de G, el vector de conjugación de Srelativo a Gse define como ∆G S= (|CG(g1)|,|CG(g2)|,...,|CG(gl)|), donde g1,g2, . . .,glson las clases de conjugación de Gque cortan a Sordenadas de tal manera que |ClG(gi)| ≤ |ClG(gi+1)|para todo i∈ {1, . . . , l −1}. Denotamos, además, ∆G= ∆G G, que abreviaremos a ∆cuando no haya posibilidad de confusión. Sea Nun subgrupo maximal de G, y G/N =hgNi. Se tiene entonces el siguiente resultado (ver [24, Theorem 4]): Proposición 1.1.1. ∆G gN = ∆G gjN= (r1, . . . , rs)para cada j= 1, . . . , p −1, 17 18 CAPÍTULO 1. NÚMERO DE CLASES DE LONGITUD MÁXIMA y la r(G)-tupla (p|CN(n1)|, . . . , p|CN(ns)|, t=(r(N)−s)/p z }| { |CN(m1)|,...,|CN(mt)|, p−1 z }| { r1, . . . , r1, . . . p−1 z }| { rs,...rs), donde ClN(n1), . . .,ClN(ns)son las clases de conjugación de Nfijadas por g yClG(m1), . . .,ClG(mt)son el resto de las G-clases de conjugación de N, es la tupla vector de conjugación excepto el orden de las componentes. El número s=rG(gN)coincide, además, con el número de clases de conjugación de Nfijadas por el automorfismo ψg:N−→ Ndefinido por ψg(n) = ng para cada n∈N, y se verifica la relación r(G) = ps +r(N)−s p, según el texto de Burnside [3, Note E]. Dado un p-grupo G, denotamos por b=b(G)al número tal que pb(G)es la mayor longitud de una clase de conjugación de G. Dado un subconjunto normal Tde G, denotaremos con brG(T)el número de clases de conjugación de Gcontenidas en Tde longitud pb(G). Denotaremos por br(G) = brG(G), el número de clases de conjugación de Gde longitud pb(G). Una observación elemental nos lleva al siguiente resultado: Proposición 1.1.2. Si Nes un subgrupo maximal de Gyg∈G\N, entonces se verifica que brG(G) = (p−1)brG(gN) + brG(N). Demostración. Basta observar que, por la proposición 1.1.1 se tiene que el número de G-clases de conjugación de longitud máxima que aparecen en todos los rG(gN)son iguales, con lo cual, si expresamos Gcomo unión disjunta de Ny de las coclases gjNcon j∈ {1, . . . , p −1}se tiene el resultado. Recordemos también que, según [24, Theorem 2], se verifica que rG(gN)≡1 (m´od p−1) para cada g∈Gy para cada Nsubgrupo normal de G. M. R. Vaughan-Lee probó en [23] el siguiente resultado, que relaciona b(G) con el orden de G0, el subgrupo derivado de G. 1.1. DEFINICIONES Y RESULTADOS PREVIOS 19 Teorema 1.1.3 (Vaughan-Lee, [23]).Si Ges un p-grupo con b=b(G), entonces |G0| ≤ pb(b+1) 2. Dicho resultado puede ser combinado con la siguiente relación elemental entre b(G)y|G0|: Lema 1.1.4. Si Ges un grupo y x∈Gentonces |ClG(x)| ≤ |G0|. En particular, si Ges un p-grupo y b=b(G), concluimos que pb≤ |G0|. Demostración. Para ver la primera afirmación, construiremos una aplicación inyectiva τxentre ClG(x)y|G0|. Dicha aplicación vendrá dada por τx(xg) = x−1xg,τxes inyectiva, pues si x−1xg=x−1xh,xg=xh. Por tanto, |ClG(x)| ≤ |G0|. La segunda afirmación se deduce inmediatamente de la primera, notando que pbes el cardinal de la mayor clase de conjugación de G. Denotemos con Wpla clase de p-grupos finitos tales que los elementos no centrales tienen el mismo número de conjugados. Libero Verardi ha probado los siguientes resultados: Teorema 1.1.5 (Verardi, [36, 2.3]).Si G∈ Wp, entonces exp G/Z(G) = p. Corolario 1.1.6 (Verardi, [36, 2.4]).Si G∈ W2, entonces Ges nilpotente de clase 2. Denotamos por Yi=Yi(G)los términos de la serie central descendente, esto es, Y2=G0,Yk= [Yk−1, G]. Corolario 1.1.7 (Verardi, [36, 2.5]).Si p > 2yG∈ Wptiene clase de nilpotencia c > 2, entonces Yc−1(G)es abeliano elemental. 20 CAPÍTULO 1. NÚMERO DE CLASES DE LONGITUD MÁXIMA Bert Beisiegel define los grupos semiextraespeciales (s.e.s.) como aquellos p-grupos Gtales que para cada subgrupo Hmaximal en Z(G)se tiene que G/H es extraespecial. Recordemos que un p-grupo no abeliano es especial cuando su centro, su derivado y su subgrupo de Frattini coinciden, y es extraespecial cuando es especial y su centro tiene orden p. Prueba que si |G|=pm+sy|G0|=ps, entonces m= 2n, con n≥s, y define los grupos ultraespeciales (u.s.) como aquellos p-grupos Gpara los cuales s=n. Existen ejemplos de grupos u.s. de exponente pyp2: para los primeros valen los p-subgrupos de Sylow de SL(3, pn). Diremos que dos grupos GyHson isoclínicos si existen dos isomorfismos ξ:G/Z(G)−→ H/Z(G), η:G0−→ H0 tales que para todo x,y∈G, si se verifican simultáneamente las dos siguientes condiciones, x1Z(H) = xZ(G)ξy1Z(H) = yZ(G)ξ, entonces [x, y]η= [x1, x2](véase, por ejemplo, [13]). La relación de isoclinismo es una relación de equivalencia en grupos. Son conocidos los siguientes resultados sobre grupos s.e.s.: Teorema 1.1.8. Sea p > 2, y G∈ Wp. Entonces b=ksi, y sólo si, Ges isoclínico a un grupo semiextraespecial de exponente p. Definimos unos grupos Gnde la siguiente manera. Sea F1=GF(p), si definimos para cada ξ= (x1, . . . , x5)yη= (y1, . . . , yt)de F5 1 ξη =x1+y1, x2+y2, x3+y3+x2y1, x4+y4+x3y1+1 2(x2y2 1−x2y1), x5+y5+x−3y2+x2y1y2+1 2(x2 2y1−x2y1), entonces obtenemos un grupo G1. Entonces sea Fn=GF(pn): con la misma definición de una operación en F5 n, obtenemos un p-grupo Gnde orden p5n 1.2. RESULTADOS SOBRE s21 en el cual [ξ, η] = 0,0, x2, y1−x1, y2, x3y1−x1y3+1 2(x1y2−x2y1+x2y2 1−y2x2 1), x3y2−x2y3+x2y1y2−x1x2y2 +1 2(x1y2−x2y1+x2 2y1−y2 2x1). Entonces podemos verificar que (Gn)0={(0,0, x3, x4, x5)|xi∈Fn, i = 3,4,5}, y Z(Gn) = {(0,0,0, x4, x5)|xi∈Fn, i = 4,5}. Más aún, [Gn:C(ξ)] = p2npara cada ξ∈Gn\Z(Gn), con lo cual Gn∈ Wp y, como Y3(Gn) = Z(Gn), entonces c= 3. Nota 1.1.9. Para el grupo P=G1, tenemos que m=s+b+ 1 (para m, s,bdefinidos como en la introducción). Notemos que exp P=psi p > 3y exp P= 9 si p= 3. Teorema 1.1.10. Si p > 2yG∈ Wpes tal que c > 2ys+b+ 1 = m, entonces c= 3,b= 2 yGes isoclínico al grupo G1definido anteriormente. 1.2. Resultados sobre s Lema 1.2.1. Si Ges un p-grupo no abeliano, y G=L0> L1>· · · > Lt> Lt+1 >· · · > Ln= 1 es una serie principal de G, entonces, para cualquier t∈ {1, . . . , n −1}, se tiene que br(G) = t X i=1 (p−1)brG(giLi) + brG(Lt), donde, para cada i∈ {1,...t−1},gi∈Li+1 \Li. En particular, tenemos que br(G)≡0 (m´od p−1). 22 CAPÍTULO 1. NÚMERO DE CLASES DE LONGITUD MÁXIMA Demostración. Dado Lun subgrupo normal de Gyhun elemento de G, denotamos por Th=Sx∈GhxL(ver [24]). Evidentemente, se tiene que ClG(¯y1) = ClG(¯y2)si, y sólo si, Ty1=Ty2. Consideremos LyL0dos subgrupos normales de Gtales que L≤L0y |L0/L|=p. Se tiene entonces que L0/L ≤Z(G/L), con lo que si h∈L0\Ly j∈ {1, . . . , p −1}, entonces Th=Thjsi, y sólo si, ClG/L(hL) = ClG/L(hjL), lo que nos lleva a que hL =hjL, al ser hN un elemento central en G/N. Por tanto, aplicando [24, Theorem 3], deducimos que ∆G Thj= ∆G Th, en particular, que brG(hjL) = brG(hL). Para obtener el resultado, bastará con razonar por inducción sobre t. Desde luego, si t= 0, el resultado es claro por (1.1.2). Si la fórmula es válida para un cierto valor de t, tenemos que br(G) = t X i=1 (p−1)brG(giLi) + brG(Lt), con lo que, aplicando el párrafo anterior a L0=LtyL=Lt+1, se verifica que brG(Lt) = (p−1)brG(gt+1Lt+1) + brG(Lt+1), con lo que tenemos probado el resultado para t+ 1, ya que br(G) = t+1 X i=1 (p−1)brG(giLi) + brG(Lt+1). Notemos que brG(Ln) = 0, con lo que tenemos probada la congruencia. En lo sucesivo, denotaremos por b=b(G). Proposición 1.2.2. El número sverifica la siguiente acotación: pm−b−1≤s≤r(G) p. Demostración. Expresemos gN como unión disjunta de clases de conjugación de G, esto es, gN = ClG(y1)∪ · · · ∪ ClG(ys). 1.2. RESULTADOS SOBRE s23 Tenemos entonces que |ClG(yi)| ≤ pb, con lo que se verifica que |G| p≤s·pb, o sea, pm−1≤spb, de donde se obtiene la primera desigualdad pm−b−1≤s. Para ver la segunda desigualdad, recordemos que se tiene el siguiente resultado: s=rG(gN)≤rG(N)≤r(N). De esta manera, tenemos que r(G)=(p−1)rG(gN) + rG(N)≥(p−1)rG(gN) + rG(gN) = ps, de donde se obtiene que s≤r(G) p y tenemos la segunda desigualdad probada. Notemos que si se tiene que s=pm−b−1, entonces todas las G-clases de conjugación de gN deben ser de cardinalidad máxima pb. Más en general, se tiene la siguiente acotación de s: Proposición 1.2.3. Sea br=brG(G)el número de clases de conjugación de Gde cardinalidad máxima pb. Tenemos entonces que s≥pm−b−br. 24 CAPÍTULO 1. NÚMERO DE CLASES DE LONGITUD MÁXIMA Demostración. Distinguimos dos casos: Si (p−1)pm−b−1≤br, entonces tenemos que, por la proposición anterior, se verifica que s≥pm−b−1, y pm−b−br≤pm−b−1≤s, puesto que pm−b−pm−b−1= (p−1)pm−b−1≤br. Si (p−1)pm−b−1>br, entonces, en la descomposición gN = ClG(y1)∪ · · · ∪ ClG(ys) tiene que haber alguna clase que no sea de longitud maximal, ya que, de otro modo, aparecerían como mínimo pm−b−1(p−1) >br clases de conjugación de longitud maximal. Teniendo en cuenta que para todo j∈ {1, . . . , p −1}se tiene que brG(gjN) = brG(gN), tenemos que brG(gN)≤br p−1.(1.1) Los elementos de gN que no están en G-clases de conjugación de gN de longitud maximal serán |G| p−pbbrG(gN) = pm−1−pbbrG(gN), y estarán repartidos en G-clases de conjugación de longitud menor o igual que pb−1. Esto nos da pm−b−pbrG(gN) G-clases de conjugación de longitud no maximal. En total, tenemos que hay, al menos, pm−b−pbrG(gN) + brG(gN) = pm−b−(p−1)brG(gN) G-clases de conjugación en gN. Teniendo en cuenta la relación (1.1), tenemos que s=pm−b−(p−1)brG(gN)≥pm−b−br, que es lo que queríamos demostrar. 1.2. RESULTADOS SOBRE s25 Observemos también que si ps =r(G), entonces s=rG(gN) = rG(N) = r(N)y el vector de conjugación de Gqueda totalmente caracterizado por ser (salvo el orden) la concatenación de pveces el vector de conjugación de N (véase [24, Corollary 2]). Se conocen grupos en los cuales se alcanzan las cotas anteriores para algún subgrupo maximal. Ejemplos 1. Supongamos que Ges el siguiente grupo: G=((C8×C4)·C4)·C4 =((hai×hbi)·hci)·hdi con las relaciones a8=b4= [a, b] = 1, c2=a2b2, d2=a4b, ac=ad=a7, bc=b3, bd=b, cd=cab3. Se tiene que el vector de conjugación de Ges de la forma (1282,647,324,168,82). Para los subgrupos maximales M1=ha, b, di, M2=ha, b, cdi, se tiene que rG(cMi) = 6, con lo que se alcanza la cota dada por 1.2.3, puesto que pm−b= 8 ybr= 2. 2. Consideremos el grupo G=C4·(C8·(C2×C4×C2)) = (C4·(C8·(C4×C2))) ×C2 =ha1i·(ha2i·(ha3i×ha4i×ha5i))=(ha1i·(ha2i·(ha4i×ha5i)))×ha3i sujeto a las relaciones a2 3=a4 4=a2 5= [a3, a4]=[a3, a5]=[a4, a5] = 1, 32 CAPÍTULO 1. NÚMERO DE CLASES DE LONGITUD MÁXIMA Esta relación se verifica porque en G\Nbestán todas las clases de conjugación de Gde longitud máxima, y sólo ellas, con lo que, al ser Nbel único subgrupo normal de orden pbde G, estará contenido en todos los maximales. Por consiguiente, todas las clases de conjugación de G\M, para cada subgrupo maximal M, serán de cardinalidad máxima pb. 1.3.1. Los vectores de conjugación Proposición 1.3.1. En todos los casos, Z(G)≤Nb. Demostración. Los elementos de G\Nbno serán nunca centrales, ya que sus clases de conjugación tienen cardinal máximo pb. Por consiguiente, teniendo en cuenta que el único subgrupo normal de orden pbes Nb, podemos concluir que Z(G)deberá estar contenido en él, ya que no puede tener orden mayor sin contenerlo. Los subgrupos maximales no parecen darnos ideas para la inducción. Por ejemplo, el grupo 729#472 tiene sus subgrupos maximales con un vector de conjugación de la forma (2439,8124,2718), y un vector de conjugación relativo de la forma (7299,8126). Otra observación elemental. Si b= 1, tenemos que Nbes un subgrupo normal de orden p, con lo que debe coincidir necesariamente con Z(G), que está contenido en él. Proposición 1.3.2. Si b= 2, entonces Nb=Z(G). Demostración. Supongamos que b= 2 y que Nb6=Z(G). Esto significa que hay elementos en Nbque no están en Z(G), con lo que deben tener clases de conjugación de longitud comprendida entre 1yp2estrictamente, o sea, p. De este modo, el vector de conjugación de Ges (pm)p,(pm−1)p−1,(pm−2)pm−2−1. Entonces r(G) = pm−2+ 2p−2≡ |G|(m´od (p2−1)(p−1)). Si escribimos n= 2m+e, sabemos que pm≡(p2−1)m+pe(m´od (p2−1)(p−1)), 1.3. CASO br(G)MÁXIMO 33 pm−2≡(p2−1)(m−1) + pe(m´od (p2−1)(p−1)), y podemos substituir en la congruencia anterior estos valores para obtener (p2−1)m+pe≡(p2−1)(m−1) + pe+ 2p−2 (m´od (p2−1)(p−1)), con lo que p2−1≡2p−2 (m´od (p2−1)(p−1)) y deducimos que p2−2p+ 1 = (p−1)2≡0 (m´od (p2−1)(p−1)), lo cual es un claro absurdo, ya que (p2−1)(p−1) = (p−1)2(p+ 1). Por consiguiente, si b= 2,Nb=Z(G). Dado un p-grupo G, se denota por aiel número de clases de conjugación de Gde cardinalidad pi. Teorema 1.3.3. Sea Gun p-grupo con b(G) = 3 ybr(G) = pm−3−1. Entonces se tiene una de las siguientes posibilidades: Nb=Z(G),∆G=(pm)p3,(pm−3)pm−3−1yr(G) = pm−3+p3−1. |G|=p2n+1,r(G) = pm−3+p2+p−2y se da una de los dos siguientes casos: •∆G=(pm)p2,(pm−2)p−1,(pm−3)pm−3−1, o •∆G=(pm)p,(pm−1)p2−1,(pm−3)pm−3−1. |G|=p2n,∆G=(pm)p2,(pm−1)p2−p,(pm−3)pm−3−1yr(G) = pm−3+ 2p2−p−1. Demostración. Supongamos que no se tiene el caso 1de la tesis. Se tiene la igualdad p3=|Z(G)|+a1p+a2p2, y sabemos que los aiverifican que ai≡0 (m´od p−1), i = 1,2. Denotemos pt=|Z(G)|. 34 CAPÍTULO 1. NÚMERO DE CLASES DE LONGITUD MÁXIMA Si a2=p−1, entonces p3−(p3−p2) = p2=pt+a1p, con lo cual se dan los siguientes casos: •t= 1, con lo que a1=p2−p p=p−1yrG(Nb)=3p−2. •t= 2, con lo que a1= 0 yrG(Nb) = p2+p−1. Si a2= 0, se tiene que p3=pt+a1p, con lo que tenemos las siguientes posibilidades: •t= 1, de donde a1=p2−1yrG(Nb) = p2+p−1. •t= 2, de donde a1=p2−pyrG(Nb) = 2p2−p. Obtenemos, pues, que rG(Nb)∈ {3p−2, p2+p−1,2p2−p}. Como rG(G\Nb) = br(G) = pm−3−1, deducimos que r(G)∈ {pm−3+ 3p−3, pm−3+p2+p−2, pm−3+ 2p2−p−1}. Si escribimos m= 2n+e, donde e∈ {0,1}, tenemos la siguiente igualdad: pm−3=p2n+e−3=p2(n−2+e)+1−e, con lo que pm−3≡(n−2 + e)(p2−1) + p1−e(m´od (p2−1)(p−1)), y r(G)≡n(p2−1) + pe(m´od (p2−1)(p−1)). Deducimos que r(G)−pm−3≡(2 −e)(p2−1) −p1−e+pe(m´od (p2−1)(p−1)). Si a2=p−1,t= 2 ya1= 0, o si a2= 0,t= 1,a1=p2−1, entonces r(G)−pm−3=pm−3+p2+p−2−pm−3=p2+p−2, y tenemos que (2 −e)(p2−1) −p1−e+pe≡p2+p−2 (m´od (p2−1)(p−1)). 1.3. CASO br(G)MÁXIMO 35 •Si e= 0, tenemos que 2(p2−1) −p−p2−p+ 2 + 1 = p2−2p+ 1 = (p−1)2, y (p−1)2≡0 (m´od (p2−1)(p−1)), contradicción. •Si e= 1, deducimos que (p2−1) −1 + p−p2+p+ 2 ≡p−2 (m´od (p2−1)(p−1)), y se llega al caso 2del enunciado. Si a2=p−1,t= 1,a1=p−1, entonces r(G)−pm−3≡pm−3+ 3p−3−pm−3= 3p−3 (m´od (p2−1)(p−1)), con lo cual (2 −e)(p2−1) + pe−p1−e≡3p−3 (m´od (p2−1)(p−1)). •Si e= 0, tenemos que 2(p2−1) −p+ 1 −3p+ 3 = 2p2−4p+ 2 = 2(p−1)2 y 2(p−1)2≡0 (m´od (p2−1)(p−1)), imposible. •Si e= 1, resulta que p2−1+1−1 + p−3p−3 + p2−2p+ 1 = (p−1)2 y (p−1)2≡0 (m´od (p2−1)(p−1)), lo cual es otra contradicción. Por último, si a2= 0,t= 2,a1=p2−p, tenemos que r(G)−pm−3≡2p2−p−1 (m´od (p2−1)(p−1)), de donde (2 −e)(p2−1) + pe−p1−e≡2p2−p−1. 36 CAPÍTULO 1. NÚMERO DE CLASES DE LONGITUD MÁXIMA •Si e= 0, tenemos que 2(p2−1) + 1 −p−2p2+p+ 1 ≡0 (m´od (p2−1)(p−1)). En este caso, |G|=p2n,r(G) = pm−3+ 2p2−p−1,|Z(G)|=p2y ∆G=(pm)p2,(pm−1)p2−p,(pm−3)pm−3−1, con lo que se cumple la parte 2 de la tesis. •Si e= 1, resulta que p2−1 + p−1−2p2+p+ 1 = −p2+ 2p−1 = −(p−1)2 y −(p−1)2≡0 (m´od (p2−1)(p−1)), lo cual es absurdo. Conocemos ejemplos del primero y del tercer tipo. De momento, no conocemos ejemplos en los que los vectores de conjugación tomen los otros dos valores. Por ejemplo, el siguiente grupo tiene su vector de conjugación del tercer tipo: G1=C3hC3C3[C3×C3×C3×C3]i=hg1, g2, g3, g4, g5, g6, g7i con las relaciones gg1 2=g2g5 gg2 3=g3g2 5g6gg1 3=g3g6 gg3 4=g4g7gg2 4=g4g5gg1 4=g4g5g6 gg3 5=g5gg2 5=g5gg1 5=g5g7 gg3 6=g7gg2 6=g6g7gg1 6=g6g2 7 gg3 7=g7gg2 7=g7gg1 7=g7 g3 3= 1 g3 2= 1 g3 1= 1 tiene como series centrales (tanto ascendente como descendente) hg7i≤hg5, g6, g7i ≤ G. En este grupo, b(G)=3, y el subgrupo normal de orden 33es abeliano elemental, hg5, g6, g7i.G/Z(G)∼ =729#469, y ∆G= (21873,7298,8180). Los grupos ultraespeciales definidos en [1, Lemma 3] son un buen ejemplo de grupos de orden p3ny con b(G) = n. La construcción es como sigue: 1.3. CASO br(G)MÁXIMO 37 Lema 1.3.4 (Beisiegel, [1, Lemma 3]).Sea pun primo, Lel cuerpo de pn elementos y Kel cuerpo primo de L. En el producto cartesiano L(3) =P definimos un producto como sigue: (a, b, c)(a0, b0, c0) = a+a0, b +b0, c +c0+f(a, b0), donde fes una aplicación K-lineal de L×Len L. Se tiene: Pes un p-grupo de clase 2. Pes ultraespecial cuando para cada elemento a∈L\ {0}, {f(a, l)|l∈L}={f(l, a)|l∈L}=L. Lema 1.3.5. Sea Pel grupo definido en el Lema 1.3.4 para el caso especial f(a, b) = ab. Entonces: Pes un grupo ultraespecial. Pes isomorfo a un p-subgrupo de Sylow de SL(3, pn). Ptiene un automorfismo ϕde orden pn−1que actúa sin puntos fijos sobre P/P0y trivialmente sobre P. La siguiente presentación define un grupo Gultraespecial de orden 39, para el cual b(G) = 3 y∆G= (1968327,729728): G=hC3×C3×C3i ×ϕhC3×C3×C3×C3×C3×C3i =hg1, g2, g3i ×ϕhg4, g5, g6, g7, g8, g9i con las relaciones siguientes: gg1 4=g4g8g2 9gg2 4=g4g7g2 8g2 9gg3 4=g4g7 gg1 5=g5g7g2 8g2 9gg2 5=g5g7gg3 5=g5g8 gg1 6=g6g7gg2 6=g6g8gg3 6=g6g9 gg1 7=g7gg2 7=g7gg3 7=g7 gg1 8=g8gg2 8=g8gg3 8=g8 gg1 9=g9gg2 9=g9gg3 9=g9 38 CAPÍTULO 1. NÚMERO DE CLASES DE LONGITUD MÁXIMA 1.3.2. Estudio de G/Z(G) En todos los casos observados hasta ahora, el centro es abeliano elemental. También se observa que G/Z(G)es un grupo de la familia, o es abeliano elemental. Sin embargo, si Nes un subgrupo normal minimal de G, no podemos afirmar que b(G/N)< b(G), como se puede ver en el grupo G= 243#3, para el cual b(G) = 2 = b(G/N)para cualquier subgrupo normal minimal Nde G, ni G/N ∈ F para ningún Nnormal minimal. Por tanto, no podemos aplicar directamente el resultado sobre b(G)de “Clases de conjugación de cardinalidad máxima en un p-grupo finito” ([35]). Sin embargo, sí que se tienen los siguientes resultados. Teorema 1.3.6. Sea Gun p-grupo tal que br(G) = pm−1−1yb(G) = 1. Entonces Z(G)∼ =CpyG/Z(G)es abeliano elemental. Recíprocamente, si G es un p-grupo no abeliano tal que Z(G)∼ =CpyG/Z(G)es abeliano, entonces b(G)=1ybr(G) = pm−1−1. Demostración. Consideremos H=Qx∈GG/Nx, donde Nx=CG(x)(notemos que CG(x)es siempre un subgrupo normal de G, puesto que tiene índice 1para los elementos centrales, y tiene índice ppara los elementos no centrales, cuya clase de conjugación tiene longitud p). Consideremos la aplicación ρ:G−→ H g7−→ (gNx)x∈G. Tenemos que Ker ρ={g∈G|gNx=Nx∀x∈G} ={g∈G|g∈Nx∀x∈G} =Z(G), y, por el Teorema de Isomorfía, se tiene que G/ Ker ρ=G/Z(G)es isomorfo a un subgrupo de H. El grupo Hes un producto de grupos de orden 1óp, con lo que es abeliano elemental. Deducimos que G/Z(G)es abeliano elemental. Recíprocamente, supongamos que Z(G)∼ =CpyG/Z(G)es abeliano y no trivial. Dados g, h ∈G, tenemos que (g−1gh)Z(G) = Z(G), 1.3. CASO br(G)MÁXIMO 39 con lo cual g−1gh∈Z(G) y existe z∈Z(G)tal que gh=gz. Por consiguiente, |ClG(g)| ≤ p, de donde b(G) = 1 ybr(G) = pm−1−1. Corolario 1.3.7. 1. Sea Gun p-grupo con b(G)=1ybr(G) = pm−1−1. Entonces Ges isomorfo a un producto directo con centro amalgamado de grupos no abelianos Gicon |Gi/Z(Gi)|=p2yZ(Gi) = Z(G). 2. Sea Gun 2-grupo con b(G)=1ybr(G)=2m−1−1. Entonces Ges un producto directo con centro amalgamado de mcopias del grupo diédrico de orden 8, o un producto directo con centro amalgamado de m−1 copias del grupo diédrico de orden 8 y una copia del grupo cuaternio de orden 8, siendo |G|= 22m+1. Demostración. Véase [12, pp. 353–356, Sätze 13.7, 13.8]. Proposición 1.3.8. Supongamos que b(G) = 2 ybr(G) = pm−2−1, y que G/Z(G)es un grupo abeliano. Si Aes un subgrupo normal minimal de G, entonces G=G/A es un grupo con b(G) = 1 ybr(G) = pm−1−1. Demostración. Si Aes un subgrupo normal minimal de G, tenemos que r(G)≥r(G/A) + p−1 p· |Z(G)| (véase [33, Lemma 2.1]). Sabemos que r(G) = pm−2+p2−1si |G|=pm, y que |Z(G)|=p2. Por tanto, pm−2+p2−1≥r(G/A)+(p−1)p, o sea, pm−2+p−1≥r(G/A). Por otro lado, como Z(G/A)≥Z(G)/A,|Z(G/A)| ≥ pyG/Z(G)es abeliano, resulta que G0=Z(G)y(G/A)0=G0/A tiene orden p. Deducimos así que b(G) = 1, ya que la longitud de una clase de conjugación está acotada por el orden del derivado. Denotemos pz=|Z(G/A)|, 40 CAPÍTULO 1. NÚMERO DE CLASES DE LONGITUD MÁXIMA entonces r(G/A) = pz+pm−1−pz p=pm−2+pz−pz−1=pm−2+pz−1(p−1), esto es, r(G/A)≥pm−2+p−1, de donde r(G/A) = pm−2+p−1yz= 1, o sea, G=G/A es un grupo con |Z(G)|=p,G/Z(G)abeliano y b(G)=1, que, por el resultado anterior es un grupo de nuestra familia. 1.3.3. Cuestiones aritméticas Otra propiedad común que se observa en los ejemplos es la siguiente: |G/G0| es un cuadrado perfecto. En este sentido, tenemos los siguientes resultados. Proposición 1.3.9. Supongamos que b(G) = 1 ybr(G) = pm−1−1. Entonces |G/G0|es un cuadrado perfecto. Demostración. Sabemos que si b(G)=1ybr(G) = pm−1−1, entonces |G0|= |Z(G)|=p, y que r(G) = pm−1+p−1. Escribamos |G|=pm, con m= 2n+eye∈ {0,1}. Como |G0|=p, decir que |G/G0|es un cuadrado perfecto, equivale a decir que e= 1. Supongamos, pues, que e= 0 y veamos que se llega a un absurdo. Es conocido que r(G)≡ |G|(m´od (p2−1)(p−1)), y que pm=p2n≡n(p2−1) + 1 (m´od (p2−1)(p−1)), pm−1=p2(n−1)+1 ≡(n−1)(p2−1) + p(m´od (p2−1)(p−1)), con lo que n(p2−1) + 1 ≡(n−1)(p2−1) + p+p−1 (m´od (p2−1)(p−1)), de donde 1≡ −p2+ 1 + 2p−1 (m´od (p2−1)(p−1)), 1.3. CASO br(G)MÁXIMO 41 esto es, 0≡ −(p−1)2(m´od (p2−1)(p−1)). Esto es absurdo, con lo que e= 1 y|G/G0|es un cuadrado perfecto. Proposición 1.3.10. Supongamos que b(G)=2ybr(G) = pm−2−2. Supongamos que se da, además, uno de los dos siguientes casos: 1. G=G/Z(G)es un grupo abeliano. 2. G=G/Z(G)es un grupo no abeliano con b(G)=1,br(G) = pm−2−1 (esto es, un grupo no abeliano de F). Entonces |G/G0|es un cuadrado perfecto. Demostración. Si G/Z(G)es abeliano, sabemos, por 1.3.8, que si Aes un normal minimal de G,G/A ∈ F yb(G/A)=1, y por 1.3.9, (G/A)(G/A)0∼ = G/G0tiene orden cuadrado perfecto. Supongamos ahora que G/Z(G)∈ F es un grupo no abeliano. Sabemos, por un resultado de Vaughan-Lee ([23]) que |G0| ≤ pb(G)b(G)+12, con lo que, en este caso, |G0|=p3y, por estar la longitud de cada clase de conjugación de G/Z(G)acotada por el orden de su subgrupo derivado, y al ser el orden de G/Z(G)0=G0/Z(G)igual a p, deducimos que G/Z(G)G/Z(G)0∼ = G/G0tiene orden cuadrado perfecto, en virtud de 1.3.9. Podemos afinar aún más el razonamiento anterior. Proposición 1.3.11. Supongamos que b(G)=2, y que br(G) = pn−2−1. Entonces G/Z(G)es abeliano elemental y su orden es un cuadrado perfecto, oG/Z(G)es isoclínico a un grupo extraespecial de exponente py|G/Z2(G)| es un cuadrado perfecto. Demostración. Si G/Z(G)es abeliano, ya hemos visto que es abeliano elemental. Supongamos que G/Z(G)no es abeliano elemental. Se tiene que el orden del subgrupo derivado de G,G0, es menor o igual que p3. De este modo, |G0/Z(G)|=G/Z(G)0≤p. 48 CAPÍTULO 1. NÚMERO DE CLASES DE LONGITUD MÁXIMA Teorema 1.4.2 (Josep A. Gallian, [8]).Sea Gun p-grupo de orden pncon b=b(G)y clase de nilpotencia c. 1. Si b≤c+ 1 yK=Sb−2 i=1 Cc−ies tal que |K| ≤ pn−pn−1, entonces c≤b+ 1. 2. Si b≤p+ 1, entonces c≤b+ 1 (Theorem 1). 3. Si c≤p+ 3, entonces c≤b+ 1. 4. Si p+ 1 ≤b≤c+p−1y, además, Yc−b+p≤Z(Y2), entonces c≤b+ 1 (Theorem 2). 5. Si Yp+2 ≤Z(Y2), entonces c≤b+ 1. 6. Si Y2puede ser generado por 2elementos, entonces c≤b+ 1. 7. Si b > 1, entonces c < p(b+ 1) −2 p−1 (Theorem 3). 8. Si b > 1, entonces c < 2b, y c= 2bsi b= 1. Teorema 1.4.3 (M. Cartwright, [4]).Sea Pun p-grupo de clase ctal que b(G) = b. Entonces c≤5 3b+ 1. 1.4.2. Conjeturas sobre grupos con br(G) = pm−b−1. La proposición 1.3.3 establece condiciones restrictivas sobre el vector de conjugación para b= 3. La respuesta a la primera pregunta debe buscarse entre grupos que verifiquen las condiciones impuestas por las Proposiciones 1.3.8, 1.3.13 y 1.3.14, si G/Z(G)es abeliano. ¿Podemos asegurar que todo grupo de Fcon b≥1tiene un cociente por el centro abeliano elemental o en F? Para b= 2, nos falta por probar esto en el caso en que G/Z(G)no es abeliano. De todos modos, hemos visto que esto es así salvo isoclinismo. ¿Es siempre G/Z(G)un grupo de exponente p? 1.4. CONJETURAS Y PROBLEMAS ABIERTOS 49 Debemos hacer constatar la dificultad en buscar ejemplos con estas condiciones, ya que el grupo factor derivado debe tener un rango bastante grande, lo que hace que el Algoritmo de Generación de p-Grupos (véase [19], [20]) no sea una herramienta eficiente para su búsqueda. 50 CAPÍTULO 1. NÚMERO DE CLASES DE LONGITUD MÁXIMA Parte II p-grupos de clase maximal 51 Capítulo 2 Preliminares 2.1. Conceptos básicos En todo lo siguiente, pdenotará un número primo impar. Definición 2.1.1. Llamaremos p-grupo de clase maximal a un p-grupo Gde orden pm, con m≥4, y clase de nilpotencia m−1. La teoría de los p-grupos de clase maximal se inició con Blackburn, en su trabajo [2]. En este artículo se utilizan algunos resultados probados por Hall en [10] y [11]. A continuación definimos algunos subgrupos importantes de los p-grupos de clase maximal. Definición 2.1.2. Dado un p-grupo de clase maximal G, se define la siguiente serie de subgrupos: 1. Para i≥2,Yi=Yi(G)será el término de la serie central descendente, dada por Y2(G) = G0= [G, G]y, para i≥2,Yi+1(G) = [Yi(G), G]. 2. Para i= 1,Y1=Y1(G)se define por medio de la relación Y1/Y4= CG/Y4(Y2/Y4). 3. Para i= 0, definimos Y0(G) = G. 53 54 CAPÍTULO 2. PRELIMINARES Veamos a continuación que la serie G=Y0> Y1> Y2>· · · > Ym−1> Ym= 1 (2.1) es una cadena de subgrupos característicos de Gen la que el índice de cada subgrupo en el anterior es siempre p. Denotaremos por Zi(G)los términos de la serie central ascendente, dada por Z1(G) = Z(G)yZi(G)/Zi−1(G) = ZG/Zi−1(G)para i≥2. Lema 2.1.3. Sea Gun p-grupo de clase maximal y orden pm. Entonces son ciertas las siguientes afirmaciones: 1. |G/Y2(G)|=p2y|Yi(G)/Yi+1(G)|=ppara 2≤i≤m−1. 2. Para todo i≥2,Yi(G)es el único subgrupo normal de índice pi. 3. Si NEGy|G/N| ≥ p2, entonces G/N es un p-grupo de clase maximal. 4. Se tiene que Zi(G) = Ym−i(G)para 0≤i≤m−2. Demostración. 1. Esta afirmación se sigue directamente de la igualdad |G|=pm= m−1 Y i=2 |Yi(G)/Yi+1(G)|·|G/Y2(G)| y de las desigualdades |G/Y2(G)| ≥ p2y|Yi(G)/Yi+1(G)| ≥ ppara 2≤i≤m−1. 2. Sea NEGcon |G/N|=pi. Entonces G/N es un p-grupo de clase a lo sumo i−1. Por tanto, 1 = Yi(G/N) = Yi(G)N/N, y, de este modo, Yi(G)≤N. Como tenemos que |G/Yi(G)|=pi, podemos concluir que N=Yi(G). 3. Sea |G/N|=pi≥p2. Del apartado anterior podemos concluir que N=Yi(G). Así, pues, G/N tiene clase i−1y, consecuentemente, es un p-grupo de clase maximal (nótese que para 2≤j≤i−1se tiene: Yj(G/N)/Yj+1(G/N) = Yj(G)N/NYj+1(G)N/N =Yj(G)/NYj+1(G)/N =Yj(G)/Yj+1(G), 2.1. CONCEPTOS BÁSICOS 55 de orden p, y también se tiene que (G/N)Y2(G/N)=(G/N)Y2(G)/N=|G/Y2(G)|=p2, como queríamos ver). 4. Como Ges de clase m−1, se sigue que Zm−1(G) = G, siendo Z0(G) = 1, Z1(G) = Z(G)yZi(G)/Zi−1(G) = ZG/Zi−1(G)para i≥2. Tenemos entonces la cadena 1 = Z0(G)< Z1(G)<· · · < Zm−1(G) = G y|G/Zm−2(G)| ≤ p2, por tanto, necesariamente |Zi(G)|=pipara i≤m−2, y según el segundo apartado, podemos concluir que Zi(G) = Ym−1(G). Lema 2.1.4. Sea Gun p-grupo de clase maximal y orden pm, con m≥4. Entonces se verifican las siguientes afirmaciones: 1. |G/Y1|=p. 2. Y1/Y36≤ Z(G/Y3). Demostración. 1. Tenemos que existe un monomorfismo entre el grupo cociente (G/Y4)CG/Y4(Y2/Y4)y el grupo de automorfismos Aut(Y2/Y4), por tanto, |G/Y1|debe dividir a |Aut(Y2/Y4)|. Este último número coincide con p(p−1) o con (p2−1)(p2−p), según sea Y2/Y4isomorfo a Cp2 o a Cp×Cp. De este modo, |G/Y1| ≤ p. Si Y1=G, se tiene que [G/Y4, Y2/Y4] = 1, luego [G, Y2] = Y3≤Y4, lo cual es imposible. Por tanto, Y1< G y, necesariamente, |G/Y1|=p, como queríamos ver. 2. Supongamos que Y1/Y3≤Z(G/Y3). Tenemos que (G/Y3)(Y1/Y3) = Cpy la inclusión anterior fuerzan que G/Y3sea abeliano, luego G0= Y2≤Y3, una contradicción. Definición 2.1.5. El grado de conmutatividad de un p-grupo de clase maximal G,c=c(G), viene definido por c(G) = m´ax{k|k≤m−2,[Yi, Yj]≤Yi+j+k, i, j ≥1}. 56 CAPÍTULO 2. PRELIMINARES Puesto que [Yi, Yj]≤Yi+jpara i,j≥1, se sigue que c(G)≥0en cualquier caso. Definición 2.1.6. Sea Gun p-grupo de clase maximal y orden pmcon m≥5. Decimos que Ges un p-grupo excepcional si existe ital que 3≤i≤m−2 con Y16=CG(Yi/Yi+2). Veremos que el calificativo de excepcional que reciben estos grupos está justificado en función de algunas de las propiedades de estos grupos. También vamos a caracterizar los p-grupos excepcionales como aquellos en los que c(G)=0. Para ello, necesitaremos algunos resultados previos. Lema 2.1.7. Sea Gun pgrupo de clase maximal de orden pm, con m≥4. Supongamos que Gno es excepcional. Entonces definimos elementos s,s1de Gtales que G=hY1, si,Y1=hY2, s1iy definimos recursivamente elementos si, con i≥2, como sigue: si= [si−1, s]. Entonces se tiene que Yi=hYi+1, sii para 2≤i≤m−1. Demostración. Tenemos que G=hY1, si=hY2, s1, siy que Y2=G0≤ Φ(G), el subgrupo de Frattini de G, luego G=hs, s1i, pues Φ(G)consta precisamente de los no generadores de G. Es un resultado conocido (véase [12, III-1.11]) que Y2=Y2(G) = h[s1, s], Y3(G)i=hs2, Y3i. Supongamos demostrado que Yi−1=hYi, si−1i. Como G=hs, s1i, se tiene: Yi= [Yi−1, G] = hYi+1,[si−1, s],[si−1, s1]i. Como Gno es excepcional, se tiene que [si−1, s1]∈[Yi−1, Y1]≤Yi+1 para i≤m−1. Además, [si−1, s] = si, luego concluimos el resultado deseado. Lema 2.1.8. Sea Gun p-grupo de clase maximal y orden pmcon m≥5. Supongamos que [Yi, Yj]≤Yi+j+1 para i,jcualesquiera con 2< i+j≤m−2. Sean sys1elementos de Gtales que G=hY1, siyY1=hY2, s1i. Definimos recursivamente los elementos si,2≤i≤m−2, mediante si= [si−1, s]. Entonces se satisfacen las igualdades siguientes: [s1, sm−2] = [s2, sm−3]−1=· · · = [si, sm−i−1](−1)i−1=· · · = [sm−2, s1](−1)m−1. 2.1. CONCEPTOS BÁSICOS 57 Demostración. Según nuestra hipótesis, tenemos que, para i,jcualesquiera con 2< i +j≤m−2, [Yi, Yj]≤Yi+j+1 (2.2) Supongamos que 2≤i≤m−2. Entonces tenemos: [si, sm−i−1] = s−1 issm−i−1 i=s−1 i[si−1, s]sm−i−1=s−1 i[ssm−i−1 i−1, ssm−i−1]. Por (2.2) tenemos: [si−1, sm−i−1]∈[Yi−1, Ym−i−1]≤Ym−1=Z(G). Así, pues, tenemos: [si, sm−i−1] = s−1 issm−i−1 i =s−1 i[si−1, s]sm−i−1 =s−1 i[ssm−i−1 i−1, ssm−i−1] =s−1 isi−1[si−1, sm−i−1], s[s, sm−i−1] =s−1 isi−1, s[s, sm−i−1] =s−1 i[si−1, ss−1 m−i] =s−1 i[si−1, s−1 m−i][si−1, s]s−1 m−i, utilizando propiedades de los conmutadores. Se verifica, además, que [si−1, s−1 m−i]∈[Yi−1, Ym−i]≤Ym−1=Z(G), y, por otro lado, [si−1, s] = si, por tanto, se tiene que [si, sm−i−1]=[si−1, s−1 m−i]s−1 iss−1 m−i i = [si−1, s−1 m−i][si, s−1 m−i], pero [si, s−1 m−1]∈[Yi, Ym−i]≤Ym= 1, y, teniendo en cuenta que [si−1, s−1 m−i] = [si−1, sm−i]−1, podemos concluir que [si, sm−i−1]=[si−1, sm−i]−1 para 2≤i≤m−2, como queríamos probar. 64 CAPÍTULO 2. PRELIMINARES En particular, tenemos que [s2, sm−4]≡sm−2(m´od Ym−1), y como, además, Ym−1=Z(G), se tiene: [sm−2, s1] = [s2, sm−4], s1= [s2, sm−4]−1[s2, sm−4]s1.(2.16) Por tanto, tenemos: [s2, sm−4]s1= [ss1 2, ss1 m−4] = s2[s2, s1], sm−4[sm−4, s1]. Como m > 5, de (2.11) se tiene que [s2, s1]∈Y4. Por tanto, [s2, s1] conmuta con el elemento ss1 m−4de Ym−4. De este modo, [s2, sm−4]s1=s2, sm−4[sm−4, s1][s2,s1]. Como [s2, s1]∈Y4,[s2, Ym−4]≤Ym−2y[Y4, Ym−2] = 1, se sigue que [s2, sm−4]s1=s2, sm−4[sm−4, s1]. De (2.11) se obtiene que [sm−4, s1]∈Ym−2. Como [Y2, Ym−2]=1, se sigue que [s2, sm−4]s1= [s2, sm−4][sm−4,s1]= [s2, sm−4]. Ahora bien, de (2.16) se sigue que [sm−2, s1]=1, luego sm−2∈CG(Y1), pues Y1=hY2, s1iy[sm−2, Y2] = 1. Por (2.14) tenemos que Ym−2= hYm−1, sm−2i=CG(Y1). Así, pues, [Y1, Ym−2] = 1.(2.17) Como Ym−26=Ym−1=Z(G), es claro que sm−2/∈Z(G). De este modo, CG(Ym−2) = CG(sm−2) = Y1y[sm−2, s]6= 1. Pongamos sm−1= [sm−2, s].(2.18) Entonces se verifica que Ym−1=hsm−1i, pues Ym−1es cíclico de orden p. Demostraremos ahora por inducción sobre ique [si, sm−i−1] = s(−1)i−1(i−1) m−1para i∈ {2, . . . , m −3}.(2.19) 2.1. CONCEPTOS BÁSICOS 65 Para i= 2, se tiene que [s2, sm−3] = s−1 2ssm−3 2 =s−1 2[s1, s]sm−3 =s−1 2[ssm−3 1, ssm−3] =s−1 2s1[s1, sm−3], s[s, sm−3]. Como [s, sm−3]∈Ym−2, de (2.17) se sigue que [s, sm−3]conmuta con cada elemento de Y1. Así, pues, por (2.13) tenemos: [s2, sm−3] = s−1 2[s1s−1 m−2, s] = s−1 2[s1, s]s−1 m−2[s−1 m−2, s]. Dado que [s1, s] = s2∈CG(Ym−2)y que [sm−2, s]∈Ym−1=Z(G), se sigue que [s2, sm−3] = s−1 2s2[sm−2, s]−1=s−1 m−1, que es la afirmación (2.19) para i= 2. Supongamos que i > 2y que está demostrado que [si−1, sm−i] = s(−1)i(i−2) m−1.(2.20) Como 2< i ≤m−3, por (2.10) se sigue que [si, sm−i−1] = s−1 i[si−1, s]sm−i−1 =s−1 i[ssm−i−1 i−1, ssm−i−1] =s−1 isi−1[si−1, sm−i−1], s[s, sm−i−1] =s−1 isi−1[si−1, sm−i−1], ss−1 m−i. Según (2.12), con i−1en lugar de i, y (2.13), se tiene que [si−1, sm−i−1]≡[s1, sm−3](−1)i≡s(−1)i−1 m−2(m´od Ym−1). Como Ym−1=Z(G)se sigue que [si, sm−i−1] = s−1 i[si−1s(−1)i−1 m−2, ss−1 m−i] =si−1[s−1 is(−1)i−1 m−2, s−1 m−i][si−1s(−1)i−1 m−2, s]s−1 m−i =s−1 i[si−1s(−1)i−1 m−2, s−1 m−i][si−1s(−1)i−1 m−2, s], 66 CAPÍTULO 2. PRELIMINARES pues [Yi, sm−i]≤Ym= 1. Tenemos que [si−1, s−1 m−i]=[si−1, sm−i]−1∈ Ym−1=Z(G),[s(−1)i−1 m−2, s−1 m−i]∈[Ym−2, Y2] = 1 (pues i≤m−3), [si−1, s] = siy[s(−1)i−1 m−2, s] = s(−1)i−1 m−1(usando (2.18)). De este modo, por (2.20) se sigue que [si, sm−i−1] = s−1 i[si−1, sm−i]−1sis(−1)i−1 m−1 =s(−1)i−1(i−2) m−1s(−1)i−1 m−1 =s(−1)i−1(i−1) m−1, y, consecuentemente, (2.19) queda demostrado. Ahora ponemos en (2.19) i= (m−1)/2(esto tiene sentido, pues mes impar y también, como m≥5,(m−1)/2≤m−3), y obtenemos que s(m−3)/2 m−1= 1. Como sm−16= 1, se tiene que m−3≡0 (m´od p), en contra de nuestra hipótesis m≤p+ 2. De este modo, se tiene nuestro resultado para m≤p+ 2. Lema 2.1.15. Sea Gun p-grupo de clase maximal y orden pm, con m≥4. Sea s∈Gys /∈CG(Yi/Yi+2)para cada i∈ {2, . . . , m −2}(en particular, s /∈CG(Y2/Y4) = Y1y, por tanto, G=hY1, si). Entonces se tiene: 1. CG(s) = hYm−1, si=hsiYm−1. 2. sp∈Ym−1, por tanto, o(s)≤p2y|CG(s)|=p2. 3. ClG(s) = sY2. 4. Si sY2=s0Y2, entonces sp= (s0)p. Demostración. 1. Tenemos que G=hY1, si=hsiY1, luego si g∈G, entonces se tiene que g=sjxpara algún x∈Y1. Por tanto, se sigue directamente el resultado deseado si probamos que Y1∩CG(s) = Ym−1. Consideremos z∈Y1∩CG(s). Entonces existe j≥1tal que z∈Yj\Yj+1. Supongamos que j= 1. Entonces Y1=hY2, zi. Además, G=hY1, si yz∈CG(s), luego G=hY2, z, si=hΦ(G), z, si=hz, si, abeliano, lo cual es imposible. Supongamos que 2≤j≤m−2. Entonces Yj= hYj+1, zi,[s, z] = 1 y[s, Yj+1]≤Yj+2. Esto origina que [s, Yj]≤Yj+2, en contra de la elección de s. Así, pues, j=m−1yz∈Ym−1, esto es, Y1∩CG(s) = Ym−1. 2.1. CONCEPTOS BÁSICOS 67 2. Tenemos que G/Y1=h¯si∼ =Cp, luego sp∈Y1∩CG(s) = Ym−1, por tanto, o(s)≤p2. Además, s /∈Ym−1, luego |CG(s)|=|hsiYm−1|= p|Ym−1|=p2. 3. Según el apartado anterior, tenemos que |ClG(s)|=pm−2yClG(s)⊆ sY2, pues sg=s[s, g]∈sY2y también |sY2|=|Y2|=pm−2, luego necesariamente ClG(s) = sY2. 4. Si sY2=s0Y2, según el apartado anterior existe x∈Gtal que s0=sx y, según 2, sp∈Z(G). Por tanto, (s0)p= (sx)p= (sp)x=sp, como queríamos probar. Nota 2.1.16. Si hubiéramos demostrado que G/Y1no es excepcional, entonces tendríamos que Y1=CG(Y1/Yi+2)para 2≤i≤m−3, y como Gtiene exactamente p+ 1 subgrupos maximales de índice p(pues G/G0∼ =Cp×Cp), se seguiría que existiría U≤Gtal que |G:U|=pyY16=U6=CG(Ym−2). Si elegimos stal que U=hY2, si, entonces stiene la propiedad dada en 2.1.15. Para los siguientes resultados necesitaremos hacer uso de la noción de p-grupo regular. Los resultados sobre p-grupos regulares aparecen demostrados en [12, III-10]. Definición 2.1.17. Dado un p-grupo G, definimos los siguientes subgrupos: Ωi(G) = hg∈G|gpi= 1i y fi(G) = hgpi|g∈Gi. Se denota pω(G)=|G/f1(G)|. Un p-grupo Gse dice regular si, para cada x∈G,y∈G, se verifica que xpyp= (xy)pY i dp i con dielementos de hx, yi0. Es sencillo observar que los subgrupos Ωi(G)yfi(G)son característicos. El siguiente teorema aparece en [12, Satz III-10.2]. 68 CAPÍTULO 2. PRELIMINARES Teorema 2.1.18. Sea Gun p-grupo. Se tiene: 1. Si la clase de nilpotencia de Ges a lo sumo p, entonces Ges regular. 2. Si |G| ≤ pp, entonces Ges regular. 3. Si G0es cíclico y p > 2, entonces Ges regular. 4. Si exp G=p, entonces Ges regular. El siguiente teorema está en [12, Haupsatz III-10.5]. Teorema 2.1.19. Sea Gun p-grupo regular, y kun número natural. 1. Si xpk=ypk= 1, entonces (xy)pk= 1. Los elementos xde Gtales que xpk= 1 componen el subgrupo característico de GΩk(G). 2. Para cada x,y∈G,xpkypk=zpkpara un elemento adecuado z∈G, que dependerá de xy de y. Las potencias pk-ésimas de elementos de G componen el subgrupo característico fk(G)de G. El siguiente resultado aparece en [12, Satz III-10.7]. Teorema 2.1.20. Sea Gun p-grupo regular. 1. Se tiene que |G/Ωk(G)|=|fk(G)|. 2. Escribamos |Ωk(G)/Ωk−1(G)|=pωk, entonces se tiene que ω1≥ω2≥ · · · ≥ ωµ, donde pµes el exponente de G. Por último, el siguiente resultado aparece en [12, Satz III-10.13]. Teorema 2.1.21. Si se tiene que ωYi(G)≤p−ipara algún icon 2≤i≤p o si ω(G)≤p−1, , entonces Ges regular. Lema 2.1.22. Sea Gun p-grupo de clase maximal y orden pmcon 5≤m≤ p+ 1. Entonces Y2yG/Ym−1tienen ambos exponente p. 2.1. CONCEPTOS BÁSICOS 69 Demostración. De 2.1.14, se tiene que G/Ym−1no es excepcional. Por tanto, se verifica que Y1=CG(Y1/Yi+2) para 2≤i≤m−3, aunque puede ser Y16=CG(Ym−2). Como p > 2yGtiene exactamente p+ 1 ≥4subgrupos maximales, entonces existen dos de ellos hs, Y2iyhs0, Y2idistintos de todos los CG(Yi/Yi+2),2≤i≤m−2. Así, pues, tenemos que s,s0/∈CG(Yi/Yi+2)para 2≤i≤m−2. Se tiene entonces que G=hs, s0, Y2i=hs, s0,Φ(G)i=hs, s0iy, además, se satisfacen las hipótesis de 2.1.15, luego sp∈Ym−2y(s0)p∈Ym−1. Por tanto, Ym−1está generado por dos elementos de orden a lo sumo p. Como |G/Ym−1|=pm−1≤pp, según 2.1.18, Ges regular y, consecuentemente, según 2.1.19, Gtiene exponente p. Como |Y1|=pm−1≤pp, usando de nuevo 2.1.18, Y1también es regular. Se sigue entonces que f1(Y1)≤f1(G)≤Ym−1. Así, pues, por 2.1.20, |Ω1(Y1)|= |Y1/f1(Y1)| ≥ |Y1/Ym−1|=pm−2. Por tanto, Y2≤Ω1(Y1)y, de este modo, Y2 tiene exponente p. Lema 2.1.23. Sea Gun p-grupo de clase maximal y orden pmcon m > p+1. Sea Y1=hY2, s1i. Entonces se tiene que sp 1∈Yp\Yp+1. Demostración. Aplicando 2.1.22 a G/Yp+1 obtenemos que sp 1∈Yp. Sea G= hY1, siysi= [si−1, s]para i∈ {2, . . . , p}. Como p+ 2 es impar (puesto que p6= 2), G/Yp+2 no es excepcional según 2.1.14. Por 2.1.7, se tiene que Yp=hYp+1, spiysp/∈Yp+1. La identidad de Zassenhaus dice que sp= [s1, (p−1) z }| { s, . . . , s]∈Yp+1f1(G). Como sp/∈Yp+1, se tiene que f1(G)6≤ Yp+1. Por tanto, existe x∈Gtal que xp/∈Yp+1. Supongamos que x /∈Y1. Como G/Yp+2 no es excepcional y x /∈Y1, se sigue de 2.1.15 la contradicción xp∈Yp+1. Así, pues, x∈Y1=hY2, s1i. Según 2.1.22, tenemos que f1(Y2)≤Yp+1. Si sp 1∈Yp+1, de la regularidad de Y1/Yp+1 se seguiría que Y1/Yp+1 tiene exponente p. Como x∈Y1, esto origina la contradicción xp∈Yp+1. De este modo, sp 1/∈Yp+1, como queríamos probar. Nota 2.1.24. La condición m>p+ 1 es necesaria, como lo prueba el producto orlado regular de dos grupos cíclicos de orden primo p. 70 CAPÍTULO 2. PRELIMINARES Lema 2.1.25. Sea Gun p-grupo de clase maximal y orden pm, con m>p+1. Entonces se verifica que f1(Yi) = Yi+p−1para 1≤i≤m−p+ 1. Además, Y1es un p-grupo regular con f1(Y1) = Ym−p−1y|Y1/f1(Y1)|=pp−1. Demostración. Según 2.1.3, se tiene que f1(Y1) = Ykpara algún k. La condición del Lema 2.1.22 sobre G/Yp+1 origina que f1(Y1)≤Yp. Así, pues, p≤k. Si fuese p<k, entonces tendríamos que sp 1∈f1(Y1)≤Yp+1, en contra de 2.1.23. Por tanto, f1(Y1) = Yp. De esto se sigue que |Y1/f1(Y1)|=|Y1/Yp|=pp−1, y la regularidad de Y1es consecuencia de 2.1.21. Por tanto, según 2.1.20, se tiene que |Ω1(Y1)|=|Y1/f1(Y1)|=pp−1, y, por consiguiente, Ω1(Y1) = Ym−p+1, según 2.1.3. Supongamos que 1< i ≤ m−p+ 1. Como Yies un subgrupo de Y1,Yies regular. Teniendo en cuenta que i≤m−p+ 1,Ω1(Yi) = Ym−p+1 ≤Yi, así, pues, Ω1(Y1) = Ω1(Yi)y, por tanto, |Yi/f1(Yi)|=|Ω1(Yi) = pp−1, de este modo, |G/f1(Yi)|=pi+p−1y de 2.1.3 se sigue que f1(Yi) = Yi+p−1, como queríamos ver. La demostración del siguiente resultado aparece en [12, Satz III-11.4]. Lema 2.1.26 (Huppert).Sea Gun p-grupo con p > 2. Entonces Ges metacíclico cuando se da la condición |G/f1(G)| ≤ p2. Los p-grupos regulares con |G/f1(G)|=p2son los p-grupos metacíclicos no abelianos. El siguiente resultado es un corolario de 2.1.25. Teorema 2.1.27. Sea Gun 3-grupo de clase maximal. Entonces se tiene que G00 = 1 y que Y1es metacíclico con clase de nilpotencia menor o igual que 2. En particular, cada 3-grupo de clase maximal es no excepcional, según 2.1.13. Demostración. Si |G| ≤ 34, entonces se tiene que |G0| ≤ 32yG00 = 1. Supongamos que |G|= 3m, con m≥5. De 2.1.25 se tiene que |Y1/f1(Y1)|= 32, por tanto, según 2.1.26, Y1es un grupo metacíclico y, por tanto, Y0 1es cíclico. Según 2.1.3, existe ktal que Y0 1=Yk. De 2.1.25 se sigue que f1(Ym−2) = Ym= 1. Por tanto, Ym−2tiene exponente 3y no es cíclico por ser de orden 32. De este modo, k≥m−1. Esto implica que |Y0 1| ≤ 3y que Y0 1≤Z(Y1). Por tanto, 2.1. CONCEPTOS BÁSICOS 71 se tiene que [x3, y] = [x, y]3= 1 para todo x,y∈Y1, luego f1(Y1)≤Z(Y1). Cada subgrupo maximal de Y1es ahora abeliano, ya que es una extensión cíclica de f1(Y1) = Φ(Y1). En particular, esto se satisface para Y2=G0, como queríamos ver. Teorema 2.1.28. Sea Gun p-grupo de clase maximal y orden pm, con m≥ p+ 2. Entonces se tiene: 1. G/Ym−1no es un grupo excepcional, así, pues, Y1=CG(Y1/Yi+2)para 2≤i≤m−3. 2. Si Ges un grupo excepcional, entonces p > 3,mes par y también 6≤m≤p+ 1. Demostración. Supongamos ahora que m≥p+ 2. Tenemos que probar que si Ges un p-grupo de clase maximal de orden pm, con m≥p+ 2, entonces Gno es excepcional. Probaremos esto argumentando por inducción sobre m. Para m=p+ 2, el resultado es cierto, según hemos visto en 2.1.14. Supongamos ahora que m > p + 2. Tenemos que m−1≥p+ 2, por tanto, la inducción aplicada a G/Ym−1nos conduce a que G/Ym−1no es excepcional. Como antes, consideremos G=hY1, si,Y1=hY2, s1iysi+1 = [si, s]para 1≤ i≤m−2. Según 2.1.7, se tiene que Yi=hYi+1, siipara i∈ {1,2, . . . , m −2}. Por el Lema 2.1.23, se tiene que sp 1∈Yp\Yp+1. Así, pues, existen k, con 0< k < p, y x∈Yp+1 tales que sp 1=xs−k p∈Yp=Yp+1hspi. En consecuencia, [sp 1sk p, sm−p−1]∈[Yp+1, Ym−p−1]≤Ym= 1. Luego se tiene que 1 = [sp 1, sm−p−1]sk p[sk p, sm−p−1]. Como [sp 1, sm−p−1]∈[Yp, Ym−p−1]≤Ym−1=Z(G)y[sp, sm−p−1]∈Ym−1, se sigue que [sm−p−1, sp]k= [sp 1, sm−p−1] = s−p 1(sp 1)sm−p−1=s−p 1(ssm−p−1 1)p=s−p 1(s1y)p, con y= [s1, sm−p−1]. Como G/Ym−1no es excepcional, y observando que m− p−1≤m−3, se sigue de 2.1.9 que y= [s1, sm−p−1]∈[Y1, Ym−p−1]≤Ym−p+1. Según 2.1.25, Y1es regular y Ω1(Y1) = Ym−p−1tiene exponente p. Como y∈ Ym−p−1, se tiene también que hs1, yi0está contenido en Ym−p+1. El carácter regular de Y1origina que (s1y)p=sp 1yp=sp 1. Por tanto, [sm−p−1, sp]k= 1. 72 CAPÍTULO 2. PRELIMINARES Como kno es un múltiplo de p, se sigue que [sm−p−1, sp]=1. Teniendo en cuenta que G/Ym−1no es excepcional, obtenemos de 2.1.9 y de 2.1.8 que [s1, sm−2] = [sp, sm−p−1](−1)p−1= 1. Tenemos que Y1=hY2, s1i. Aplicando 2.1.7 a G/Ym−1obtenemos que Ym−2=hYm−1, sm−2i. Por tanto, [Y1, Ym−2] = 1. Como G/Ym−1no es excepcional, también se verifica que [Y1, Yi]≤Yi+2 para i≤m−3. Por tanto, Ges, asimismo, no excepcional, como queríamos probar. Teorema 2.1.29. Sea Gun p-grupo de clase maximal. Si Gno es excepcional, entonces cada uno de los subgrupos maximales de Gdistintos de Y1es un p-grupo de clase maximal. Demostración. Tenemos que probar que cada subgrupo maximal Hde G distinto de Y1tiene clase m−2. Sea G=hY1, si,Y1=hY2, s1iysi+1 = [si, s]. Entonces cada subgrupo maximal Hde Gdistinto de Y1tiene la forma H= hY2, ssi 1ipara un iadecuado con 0≤i≤p−1, ya que G/G0=hsG0, s1G0i∼ = C2 p. Demostraremos por inducción sobre jque, para 1≤j≤m−3, [s2, (j) z }| { ssi 1, . . . , ssi 1]≡sj+2 (m´od Yj+3) Para j= 1, tenemos que [s2, s1]∈Y4y, por tanto, se sigue el resultado trabajando módulo Y4. Supongamos que [s2, (j−1) z }| { ssi 1, . . . , ssi 1] = sj+1y, con y∈Yj+2 yj≤m−3. Entonces se tienen las siguientes congruencias módulo Yj+3: [sj+1y, ssi 1] = [sj+1, ssi 1]y[y, ssi 1] ≡[sj+1, ssi 1] ≡[sj+1, si 1][sj+1, s][sj+1, s, si 1] ≡[sj+1, si 1]sj+2. 2.2. COTAS ANTERIORES 73 Según nuestra hipótesis, Gno es excepcional, por tanto, para j+ 1 ≤m−2 se tiene: [sj+1, si 1]∈[Yj+1, Y1]≤Yj+3. Esto demuestra nuestra afirmación. Como Ym−1= 1, se tiene lo siguiente: sm−1= [s2, (m−3) z }| { ssi 1, . . . , ssi 1]∈Ym−2(H). Según hemos visto en 2.1.14, G/Ym−1no es excepcional, y, por 2.1.7 se verifica que Ym−2=hYm−1, sm−2i. Como s /∈Y1=CG(Ym−2), se tiene que [sm−2, s] = sm−16= 1. De aquí se obtiene que Htiene al menos clase m−2. Como H tiene orden pm−1, se sigue que Htiene trivialmente clase m−2. Como hemos visto en las demostraciones anteriores, el sistema formado por los elementos s∈G\Y1∪CG(Ym−2),s1∈Y1\Y2ysi= [si−1, s]∈Yi\Yi+1 para i∈ {2, . . . , m −1}tiene una importancia capital. Por ello presentamos la siguiente definición. Definición 2.1.30. Denominamos G-sistema generador al vector (s, s1, . . . , sm−1). 2.2. Cotas anteriores Blackburn probó las siguientes cotas para c(G): Teorema 2.2.1 ([2, Theorem 2.11]).Si mes un número impar, entonces c(G)≥1. Teorema 2.2.2 ([2, Theorem 3.8]).Si m≥p+ 2, entonces c(G)≥1. Teorema 2.2.3 ([2, Theorem 3.12]).1. Si Ges metaabeliano, entonces c(G)≥m−p−1. 2. Si Gadenota la familia de los p-grupos de clase maximal cuyo mayor subgrupo normal abeliano es Ya, entonces G∈ Gaya≥3implican que c(G)≥m−p−2a+ 4. 80 CAPÍTULO 2. PRELIMINARES Yf(i,j,c), y, en consecuencia, los invariantes bylestán prefijados. Por tanto, es importante conocer a priori tanta información como sea posible sobre c en relación a m, que nos permitiría simplificar cálculos, esto es, queremos encontrar funciones hi=hi(b, l),1≤i≤3, que son independientes de my que satisfacen las desigualdades p≥h1(b, l), c ≥h2(b, l) =⇒c≥m−h3(b, l)/2,(2.24) y lo más pequeñas posibles entre las que verifiquen estas condiciones. Se prueba que h1(b, l) = m´ax2(b−l), b+l, h2(b, l) = 2(b−l)−3, h3(b, l)=3b−(l+1) satisfacen (2.24) en el caso b≤2l−1. Además, para l=b−1yb≥3, las hipótesis son válidas, y existen ejemplos que satisfacen la igualdad c= (m−3b+l+ 1)/2para cada pyc, por tanto, c≥(m−3b+l+ 1)/2 es la mejor cota posible. Por otro lado, la diferencia b−les pequeña para los grupos que tienen exponente pequeño. Es interesante obtener información sobre estos grupos. En este sentido, para b−l=i,1≤i≤3, y para cualquier py cualquier c, se prueba que la desigualdad c≥(m−3b+l+1)/2 es también válida. Finalmente, usando que c≥(m−3b+5)/2, se prueba que c≥(m−3b+l+ 1)/2es válida, incluso en el caso b−l= 4. Recordemos que si G∈ F, entonces se tiene la siguiente desigualdad: c≥m−p−1. Claramente, F ⊆ T1, donde Ti={G|l(G) = b(G)−i}, para i∈ {1, . . . , b −1}. Blackburn [2] mostró que c(G)≥m−p−2a+ 4, siendo a≥3. Obviamente, b≤ayc≤m−2b. En [31], las desigualdades c≥m−p−1yc≥m−p−2b+ 4 se prueban para los casos b= 2 yb≥3, respectivamente. Si b=b(G) = 2, es claro también que G∈ T1. Más aún, es 2.4. COTAS EN FUNCIÓN DE bYl81 obvio que si b=b(G)≤5, entonces G∈S4 i=1 Ti.En este artículo se obtiene la siguiente desigualdad: c≥m−p−2b+ 2l+ 1 si p≥m´ax2(b−l)−1, b +lyb≤2l. En particular, esta desigualdad se da en el caso p≥2b−1yb≤2l. Por otra parte, si H0=G > H1>· · · > Hb−2 es una cadena de p-subgrupos de clase maximal de Gtal que |Hi|=pm−i, entonces se dan las siguientes desigualdades: c≥m−p−2b+ 2l(Hi)+1 para cada i∈[0, b −2] tal que b≤2l(Hi) + iyp≥2(b−i)−1(observemos que l(Hi)≥2si, y sólo si, αi+1,i+2 = 0). Por otro lado, en el caso p+ 3 ≤ 2b≤2l+ (p+ 1)/2la siguiente desigualdad es válida: c≥m−p−2b+ 2l(Hb−((p+1)/2))+1. En el teorema 2.4 se prueba la siguiente desigualdad: c≥m−p−2b+ 2(b−l)+1 si b≤2l. Estas desigualdades son especialmente interesantes cuando pes pequeño en relación a m, puesto que, en este caso, estas desigualdades dan más información que las desigualdades de tipo c≥m−h3(b, l)2. Finalmente, para b−lpequeño, se obtienen las siguientes desigualdades: si G∈ T1, c≥m−p−1; si G∈ T2, c≥m−p−3; si G∈ T3, entonces c≥     m−p−4,si l= 1; m−p−6,si l= 2; m−p−5si l≥3. 82 CAPÍTULO 2. PRELIMINARES Finalmente, si G∈ T4, entonces tenemos c≥                    m−p−6,si l= 1; m−p−8,si l= 2; m−p−10,si l= 3; m−p−7,si l≥4y2l6=p−3; m−p−12,si l= 4 y2l=p−3; m−p−9,si l≥5y2l=p−3. Sea T RGel siguiente triángulo matricial: T RG= α1,m−c−2α2,m−c−3. . . αm−c−3,2αm−c−2,1 α1,m−c−3α2,m−c−4. . . αm−c−3,1 . . .. . ....... α1,5α2,4α3,3α4,2α5,1 α1,4α2,3α3,2α4,1 α1,3α2,2α3,1 α1,2α2,1 α1,1 esto es, T RG={αi,j |i, j ≥1, i +j≤m−c−1}. De las definiciones de c(G)se sigue que T RG6= (0). Para cada número natural g≤m−c−1, definimos el siguiente subtriángulo de T RG: T Rg=T Rg(G) = {αi,j |i, j ≥1, i +j≤g}. El conjunto T RFg={ai,j |i+j=g} se llama g-ésima fila de la tabla T RG, y el conjunto T RCg={αg,j |1≤j≤m−c−1−g}, g ≤m−c−2 recibe el nombre de g-ésima columna de T RG. Lema 2.4.1. Supongamos que b≥2. El invariante v(G) = m´ınj∈ {2,3, . . . , m −c−2} | α1,j 6= 0 satisface las siguientes condiciones: 2.4. COTAS EN FUNCIÓN DE bYl83 1. v= 2lpara algún natural l=l(G). 2. l≤b−1. 3. 2l≤p−1. Más aún, si 2l+ 2 ≤m−c−1, entonces 2l≤p−3. Lema 2.4.2. 1. La totalidad de valores de la j-ésima columna de la matriz T RGsólo depende de los valores de la (j+ 1)-ésima columna y de cualquier valor prefijado en la j-ésima columna. 2. La totalidad de valores de la t-ésima fila de la matriz T RGsólo depende de los valores de la (t−1)-ésima fila y de cualquier valor prefijado de la t-ésima fila. Corolario 2.4.3. 1. Si la j-ésima columna de la matriz T RGtiene un cero, entonces todos los valores de esta columna sólo dependen de los valores de la (j+ 1)-ésima columna de T RG. 2. Si la t-ésima columna de la matriz T RGtiene un cero, entonces todos los valores de esta fila sólo dependen de los valores de la (t−1)-ésima fila de T RG. Corolario 2.4.4. 1. Si {αi1,j1, . . . , αik,jk}es un conjunto de representantes de la uw-ésima fila, w= 1, . . . ,k, esto es, si iw+jw=uw, w= 1, . . . ,k, entonces todos los valores de T RGpueden darse en términos de los valores de este conjunto, esto es, son variables que generan todos los valores de la tabla T RG. Además, k≤b−1. 2. Si {αv1,z1, . . . , αvs,zs}es un conjunto de representantes de la vw-ésima columna, w= 1, . . . ,s, entonces todos los valores de T RGpueden darse en términos de los valores de este conjunto, esto es, son variables que generan todos los valores de la tabla T RG. Proposición 2.4.5. Se tienen las siguientes afirmaciones: 1. Si vs< m −c−2, entonces c≥m−p−vs. 2. Si v1≥p, entonces c≥m−p−v1+ 1. 3. Si v1≤p−1, entonces c≥m−2(p−1). 84 CAPÍTULO 2. PRELIMINARES Lema 2.4.6. Para cada número natural ntal que 2l+n≤m−c−1, tenemos: αi,2l+n−i= [(n+1)/2] X g=1 (−1)l−i−g+1l−i+n−g n−(2g−1)xg(2.25) Lema 2.4.7. Sean l,e,denteros con d≥e−1≥0. Sea A= (ai,j)∈ Mat(e×e, Z)la matriz definida por ai,j =       l+d+i−j−1 2i−j+d−1∗ si j= 1, l+d+i−j−1 2i−j+d−1∗2l−2i+ 2j−1 2j−3∗∗ en otro caso. Entonces det A= (−1)e(e−1)/2 e−1 Y k=2 k! e−2 Y t=0 (4l+ 2d−1−2t)e−t−1 e Y i=1 l+d+i−e−1 2i−e+d−1∗ . Lema 2.4.8 (periodicidad módulo c+b−1).Los valores de la parte [α1,b, . . . , α1,m−c−2] de la primera columna de la tabla T RGtienen periodicidad c+b−1, esto es, α1,u =α1,u−(c+b−1) para todo u∈[2b−1 + c, m −c−2]. Obviamente, de la relación αk,b+e=αk,2b−1+c+epara todo k∈[1, m −2c−2b−e], que aparece en la demostración de este lema, se sigue que la periodicidad c+b−1es verdadera para todos los valores de las columnas del subtriángulo de T RGque tienen como vértices (1, m −c−2),(m−c−b−1, b)y(1, b). De la definición de bse tiene que αi,j = 0 para i,j≥bcuando esta expresión tiene sentido. En [31] se vio que el resto de los αi,j pueden ser expresados en términos de los αk,b con 1≤k≤b−1, esto es, para 1≤i≤b−1se tienen las siguientes igualdades: αi,j = b−i−1 X g=0 (−1)gj−b gαi+g,b,(2.26) 2.4. COTAS EN FUNCIÓN DE bYl85 para cada j∈[b, m −c−i−1], y αi,j = j−i−1 X g=0 (−1)gb−j−1 + g b−j−1αi+g,b + b−i−2 X g=j−ib−j−1 + g g−b−j−1 + g g+i−jαi+g,b, (2.27) para 1≤j < b. Lema 2.4.9. Supongamos que c= (m−2b−1)/2. Sea yj=αj,b. Entonces se verifican las siguientes igualdades: −yj b−i−1 X g=0 (−1)gj+cgyi+g!+yi b−j−1 X g=0 (−1)gc+igyj+g!= 0,(2.28) para i,jcualesquiera que satisfagan 1≤i<j≤b−1,b−c≤i+j≤b. Lema 2.4.10. Supongamos que c=m−p−2b+ 4,p≥7yb≥6. Sea x=αb−1,b. Entonces tenemos que αb−2,b =−3x, αb−3,b = 2x, αb−4,b =αb−5,b = 0. Lema 2.4.11. Supongamos que b= 6 yc= (m−2b−1)/2≥3. Entonces Qb−1 i=0 (c+i)6= 0, y α1,b =α1,66= 0. Lema 2.4.12. Supongamos que b= 6. Entonces c6= (m−2b−1)/2. Teorema 2.4.13. Supongamos que b≥6. Entonces c≥(m−3b+ 6)/2. Lema 2.4.14. Sean l,c,enúmeros naturales tales que c≥2e−3. Sea A= (aij), con aij =l+c−(i−1) c−2i+j+ 2 para 1≤i, j ≤e. Entonces det(A) = Qe−1 k=1 k!·Qe−1 k=1 Qe−k j=1(2l+c−j+k)·Qc+3−2i k=1 (l+c+ 2 −i−k) Qe i=1(c−2i+e+ 2)! . 86 CAPÍTULO 2. PRELIMINARES Teorema 2.4.15. Supongamos que p≥m´ax2(b−l)−1, b +lyb≤2l. Entonces se tiene la siguiente desigualdad: c≥m−p−2b+ 2l+ 1. Corolario 2.4.16. Sea H0=G > H1>· · · > Hb−2una cadena de psubgrupos de clase maximal de Gcon |Hi|=pm−i,i∈ {0,1, . . . , b −2}. Se tienen entonces las siguientes desigualdades: c≥m−p−2b+ 2l(Hi)+1 para cada i∈[0, b −2] tal que b≤2l(Hi) + iyp≥2(b−i)−1. Corolario 2.4.17. Si p+ 3 ≤2b≤(p+ 1)/2+2l, se tiene la siguiente desigualdad: c≥m−p−2b+ 2l(Hb−p+1 2)+1. Teorema 2.4.18. Si b≤2l, entonces c≥m−p−2b+ 2(b−l)+1. Teorema 2.4.19. Supongamos que se dan las siguientes condiciones: p≥m´ax2(b−l)−1, b +l, c ≥2(b−l)−3yb≤2l−1. Entonces tenemos que c≥m−3b+l+ 1 2. A continuación se estudia la familia T1. Teorema 2.4.20. Supongamos que l=b−1. Se tiene entonces la siguiente desigualdad: c≥m−p−1. Corolario 2.4.21. Si G∈ F, entonces se tiene la desigualdad c≥m−p−1. Teorema 2.4.22. Supongamos que l=b−1, y sea x1=αl,l+1. Entonces los valores de la tabla T RGson los siguientes: αi,2l+n−i=((−1)l−il+n−i−1 n−1x1,para n≥1,2l+n≤m−c−1; 0,para n∈[−2l+ 2,0]. 2.4. COTAS EN FUNCIÓN DE bYl87 Teorema 2.4.23. Supongamos que b≥3yl=b−1. Entonces c≥(m− 2b)/2. Teorema 2.4.24. Sea Kun cuerpo tal que car K6= 2 y sea Lun K-espacio vectorial de dimensión m. Sea {e0, e1, . . . , em−1}una K-base de L. Sean v, c,lnúmeros enteros tales que v≥0,0≤c≤m−2, l ≤(p−3)/2, m = 2c+ 2l+ 2 −v. Definimos ei= 0 para cada i≥m, y 1. [ei, e0] = ei+1 para i≥1, 2. [ei, e0] = −[e0, ei]para i≥1, 3. [ei, ej]=(−1)i+1l+w−i−1 w−1ei+j+csi i+j= 2l+w,i,j≥1. Entonces se tienen las siguientes afirmaciones: 1. [ei, ei] = 0 para todo i≥0. 2. [ei, ej] = −[ej, ei], para 0≤i<j. 3. ρ(i, j, k) = [ei, ej, ek]+[ek, ei, ej]+[ej, ek, ei]=0para 0≤i < j < k. Entonces (L, [,]) es una K-álgebra de Lie de clase de nilpotencia maximal. Corolario 2.4.25. Sea m≥6un número par menor o igual que p. Entonces existen p-grupos de clase maximal de orden pmque satisfacen las condiciones c= (m−2b)/2, l =b−1. En el siguiente parágrafo, se estudia la familia T2. Teorema 2.4.26. Si l=b−2, entonces c≥m−p−3. Teorema 2.4.27. Supongamos que l=b−2. Entonces para 2≤2l+n≤ m−c−1, tenemos que αi,2l+n−i= (−1)l−il−i+n−1 n−1x1+ (−1)l−i−1l−i+n−2 n−3x2, donde x1=αl,l+1,x2=αl+1,l+2. 88 CAPÍTULO 2. PRELIMINARES Teorema 2.4.28. Supongamos que l=b−2. Entonces c≥(m−2b−1)/2. En el parágrafo 5se estudia la familia T3. Teorema 2.4.29. Si l=b−3, entonces tenemos que c≥     m−p−4si l= 1; m−p−6si l= 2; m−p−5si l≥3. Teorema 2.4.30. Supongamos que l=b−3. Entonces, para 2≤2l+n≤ m−c−1tenemos que αi,2l+n−i= (−1)l−i l−i+n−1 n−1x1−l−i+n−2 n−3x2 +l−i+n−3 n−5x3!, donde x1=αl,l+1,x2=αl+1,l+2,x3=αl+2,l+3. Teorema 2.4.31. Supongamos que l=b−3. Entonces c≥(m−2b−2)/2. Por último, se estudia la familia T4. Teorema 2.4.32. Supongamos que l=b−4. Entonces tenemos: c≥                    m−p−6si l= 1; m−p−8si l= 2; m−p−10 si l= 3; m−p−7si l≥4y2l6=p−3; m−p−12 si l= 4 y2l=p−3; m−p−9si l≥5y2l=p−3. Teorema 2.4.33. Supongamos que l=b−4. Entonces los valores de la tabla T RGson los siguientes: αi,2l+n−i=    P4 g=1(−1)l−i−g+1l+n−i−g n+1−2gxg,para n≥1, 2l+n≤m−c−1; 0,para n∈[−2l+ 2,0]. Teorema 2.4.34. Supongamos que l=b−4. Entonces c≥(m−2b−3)/2. 2.5. COTAS EN FUNCIÓN DE c0Yl89 2.5. Cotas en función de c0yl En el artículo [28], A. Vera-López, J. M. Arregi y F. J. Vera-López obtienen nuevas cotas inferiores para el grado de conmutatividad de un p-grupo de clase maximal. Estas cotas muestran la relación entre el invariante l(G)asociado a la estructura normal de G(que se usa en el cálculo de las relaciones definitorias de G) y el grado de conmutatividad. Lema 2.5.1. Sean eytnúmeros naturales tales que t≥e, y sea runa indeterminada. Consideremos la matriz A= (ai,j)1≤i,j≤e, con ai,j =r−i t−2i+j. Entonces det A=Qm´ın(e,[(t+1)/2]) i=1 [r−i, t −2i+ 1] ·Qe−1 k=2 k!·Qs−1 j=1(2r−t+e−s+ 1 −j) Qe i=1(t−2i+e)! ·Qe s=2 Q(t+e−s+2)/2≤i≤e(r+e−s+ 1 −i). Nota 2.5.2. Tras una reordenación adecuada, la expresión para det Apuede ser escrita de un modo más compacto como det A=F(r, t, e) F(t, t, e),(2.29) donde F(r, t, e) = Y 1≤w≤t−1 (r−w)m´ın(w,t−e,t−w) ×Y t−e+1≤w≤t+e−3 (2r−w−1)m´ın([ e−t+w+1 2],[e+t−w−1 2]).(2.30) Se denota por c0la clase residual de c(G)módulo p−1. Lema 2.5.3. Supongamos que l≥c0+2 y2l+c0+2 ≤m−2c−1. Entonces 2c≥m−2l−c0−2. 96 CAPÍTULO 2. PRELIMINARES Sea TGel siguiente triángulo matricial: TG= α1,m−c−2α2,m−c−3. . . α1,m−c−3α2,m−c−4. . . . . .. . . α1,5α2,4 α1,4α2,3 α1,3 α1,2 esto es, TG={αi,j |i, j ≥1, i < j, i +j≤m−c−1}. De la definición de c(G), se sigue que TG6= (0). Definimos xλ=αλ,λ+1 para 2λ+ 1 ≤m−c−1. La propiedad de Bernoulli (C3) toma una de las siguientes formas: αi,j =αi,j+1 +αi+1,j,si i+j+ 1 ≤m−c−1; αi,j =αi,j−1−αi+1,j−1,si j > 1; αi,j =αi−1,j −αi−1,j+1,si i > 1. Recurrencia sobre w≥0para cada una de estas tres fórmula nos lleva a las siguientes expresiones más generales: αi,j = w X u=0 w uαi+u,j+w−u,si i+j+w≤m−c−1; (2.33) αi,j = w X u=0 (−1)uw uαi+u,j−w,si j > w;(2.34) αi,j = w X u=0 (−1)uw uαi−w,j+u,si i > w. (2.35) Para r+s+t≤m−c−1, denotemos R(r, s, t) = {αi,j |i≥r,j≥s,i+j≤r+s+t}, 2.6. COTAS PARA c0≤597 el triángulo (⊂ TG) de vértices αr,s,αr,s+t,αr+t,s,t≥1. Las fórmulas (2.33), (2.34) y (2.35) permiten determinar los αi,j en R(r, s, t)cuando se conocen los valores correspondientes a un lado de R(r, s, t). En particular, si los valores en un lado de R(r, s, t)son todos cero, entonces los valores en todo el triángulo son cero. Supongamos que i+j+p−1≤m−c−1. Denotamos z(j) i=αi,p−c0−1+jy zi=z(1) i=αi,p−c0. Por la periodicidad módulo p−1y por (2.34), obtenemos αij =αi,j+p−1= w X u=0 (−1)uw uαi+u,j+p−1−w= w X u=0 (−1)uw uz(j+c0−w) i+u, (2.36) para cada w≥0tal que j+p−1> w yw≤j+c0. En particular, para w=j+c0−1tenemos: αij =αi,j+p−1= j+c0−1 X u=0 (−1)uj+c0−1 uzi+u.(2.37) En [18], los αij son expresados en función de los valores fundamentales xk= αk,k+1 como sigue: αi,j = [(i+j−1)/2] X k=i (−1)k−ij−k−1 k−ixk.(2.38) Supongamos que i+j+1+p−c0−1≤m−2c−1. Aplicando la identidad de Jacobi a la terna (i, j, p−c0−1) y teniendo en mente la periodicidad módulo p−1, tenemos la factorización rij =αij(αi+j+c0,p−c0−1−αi,p−c0−1−αj,p−c0−1) = 0, esto es, αij(z(0) i+j+c0−z(0) 1−z(0) j) = 0. Lema 2.6.1. Supongamos que i+j+1+p−c0−1≤m−2c−1. Se tienen las siguientes afirmaciones: 1. αi+1,j 6= 0 6=αi,j+1 implica que zi=zj. 2. αi,j 6= 0 6=αi+1,j implica que zi=zi+j+c0. 3. αi,j 6= 0 6=αi,j+1 implica que zj=zi+j+c0. 98 CAPÍTULO 2. PRELIMINARES 4. Si j≥2,0/∈ {αi,j, αi,j+1, αi+1,j−1, αi+2,j−1}yαi+1,j = 0, entonces zj=zi+j+c0=zi+1. En la tabla TG, el caso 1 corresponde a dos valores consecutivos no nulos en la misma fila, lo que denotaremos por • • El caso 2 corresponde a dos valores no nulos consecutivos en una misma diagonal, lo que denotamos por • • El caso 3 corresponde a dos valores no nulos consecutivos en la misma columna, lo que denotaremos por • • El caso 4 corresponde a la configuración siguiente: •0• aij=• • Con esta notación, cálculos usando la propiedad de Bernoulli muestran que todas las posibles configuraciones para i+j≤8son las de las tablas I, II, III dadas al final del artículo. En cualquier caso, la existencia de valores no nulos consecutivos fuerza una ligadura en los elementos de la (p−c0)-ésima diagonal. Sabemos a priori la existencia de filas de TGcon muchos valores no nulos. Particularmente, las filas i+j= 2l+ 1,2l+ 2 de TG(esta última cuando existe) tienen todos sus valore no nulos. Por tanto, aplicando el Lema 2.6.1, obtenemos relaciones entre los zj. Lema 2.6.2. 1. En la fila i+j= 2l+ 1 de TG, todos los valores son no nulos. 2. Supongamos que 2l+2 ≤m−c−1. En la fila i+j= 2l+2 de TG, todos los valores son no nulos. Además, si 2l+2+p−c0−1≤m−2c−1 yl≥2, entonces zj=z1para cada j∈[1,2l]\ {l}. 2.6. COTAS PARA c0≤599 3. Supongamos que 2l+ 3 ≤m−c−1. En la fila i+j= 2l+ 3 de TG, existe a lo sumo un cero. Se define yv=α1,2l+vpara 0≤v≤m−c−2l−2. Entonces Lema 2.6.3. 1. αi,j = 0 para i+j≤2l. 2. Si 2l+ 1 ≤i+j≤m−c−1, entonces αij = τ X v=0 (−1)v−ji−1 τ−vyv, con τ=i+j−2l−1. Lema 2.6.4. Para l≤i≤(m−c−3)/2se tienen las siguientes desigualdades: yτi= τi−1 X v=0 (−1)τi−v+1 i−1 τi−vyv,con τi= 2(i−l)−1. Lema 2.6.5. Supongamos que 2l+p−1≤m−c−1yzj=z1para todo j≤c0. Entonces: αij = 0 para todo αij ∈ R(1, p −c0+ 1,2l+c0−3). 2l≤p−2c0−1. zj=z1para todo j≤2l+c0−1. Supongamos que zj=z1para todo j≤c0yc0+2 ≤l. Usando el Lema 2.6.5 y el Teorema 2.5.4 de [28] se obtiene que 2c≥m−2l−c0−2óc≥m−2l−p+1. Teorema 2.6.6. Supongamos que zj=z1para todo j≤c0. Para cada k≥0 que satisfaga las condiciones 2k+p−c0−1≤m−2c−1yk+c0≤p, tenemos que x1=x2=· · · =xk−1==, esto es, l≥k. Notemos que el Teorema 2.6.6 es cierto cuando pno divide a c0+µ,µ∈ [0, k −1]. Corolario 2.6.7. Supongamos que zj=z1para todo j≤c0. Entonces 2c≥ m−2l−p+c0−1. 100 CAPÍTULO 2. PRELIMINARES Lema 2.6.8. Supongamos que 2l+ 3 ≤m−c−1yl≥3. Entonces o bien b=l+ 1 o existe el mínimo t∈[2, m −c−1−(2l+ 1)] que satisface αl+1,l+t6= 0. En el primer caso, tenemos que c≥m−2l−p−1, con lo que 2c≥m−p−2l+c0+1, y, en el otro caso, si 2l+t+1+p−c0−1≤m−2c−1, entonces zj=z1para todo j∈[1,2l]. A continuación se da una demostración del Teorema de Shepherd [22, Thm. 2.12]. Corolario 2.6.9. Supongamos que c0+ 1 ≤2l. Entonces 2c≥m−2l−p+ c0−1. Consecuentemente, 2c≥m−2p+c0+ 2, y si se tiene la igualdad, entonces c0= 3 y2l=p−3. Corolario 2.6.10. Supongamos que c0= 2l. Entonces, si p > 7, tenemos que 2c≥m−p−2l+c0−2. A continuación se estudian los casos l= 1,2. Lema 2.6.11. Supongamos que 2l+ 4 ≤m−c−1. Tenemos: 1. (y2, y3)6= (0,0). 2. Si y3= 0, entonces y1−y26= 0. 3. Si αl+1,l+2 = 0, tenemos que z1=z2l+1 =z2l+2,z2=z2l=z2l+1 para cada l≥3. Corolario 2.6.12. Supongamos que c0−1 = 2l. Si p > 7, entonces tenemos que 2c≥m−p−2l+c0−3. Corolario 2.6.13. Supongamos que c0−2=2l. Entonces tenemos las siguientes afirmaciones: 1. Si l≥3yp > 7, entonces 2c≥m−p−2l+c0−5. 2. Si l= 2 yp > 7, entonces 2c≥m−p−1. 3. Si l= 1 yp > 7, entonces 2c≥m−p−2. Corolario 2.6.14. 1. Si c0= 1, tenemos que c0+ 1 ≤2l, de donde 2c≥ m−p−2l+ 1. 2.6. COTAS PARA c0≤5101 2. Si c0= 2, entonces c0≤2l, con lo que 2c≥m−p−2l+c0−2 = m−p−2 si l= 1, y c0+ 1 ≤2lsi l≥2, luego 2c≥m−p−2l+c0−1. 3. Si c0= 3, entonces c0−1≤2l, de donde 2c≥m−p−2l+c0−3 = m−p−2si l= 1, y c0+1 ≤2lsi l≥2, luego 2c≥m−p−2l+c0−1. 4. Si c0= 4, entonces c0−2 = 2l, para l= 1 y2c≥m−p−2, y c0= 2l para l= 2, luego también 2c≥m−p−2yc0+ 1 ≤2l, para l≥3, con lo que 2c≥m−p−2l+c0−1en este caso. En cualquier caso, para 1≤c0≤4, tenemos que 2c≥m´ın(m−p−2, m −p−2l+c0−1). Como aplicación de los lemas anteriores, se analizan los p-grupos de clase maximal que satisfacen la condición c0= 5. Lema 2.6.15. Sea Gun p-grupo de clase maximal tal que c0= 5. Supongamos que p > 7, y 8 + p−c0−1≤m−2c−1, entonces x1=x2=x3. Lema 2.6.16. Supongamos que c0= 5,12 ≤m−2c−1yx1=x2=x3. Entonces x1=x2=x3= 0. Corolario 2.6.17. Supongamos que c0= 5 yp≥11. Entonces 2c≥m´ın(m−p−22, m −2l−p+c0−1). En lo sucesivo, se refina el resultado anterior en los casos 2l≤p−11 yp > 19. Lema 2.6.18. Supongamos que c0= 5,p > 19,x1=x2=x3y17 ≤ m−2c−1, entonces x1=x2=x3=x4=x5=x6= 0, esto es, l≥c0+ 2. Teorema 2.6.19. Supongamos que c0= 5,2l≤p−2c0−1 = p−11 y p > 19, entonces 2c≥m−p−2. Supongamos que c0= 5. En lo sucesivo, calculamos cotas sobre c, determinando el álgebra de Lie asociada L=L(m, c, αij)en los casos p= 13,17, 19, de acuerdo con los posibles valores de len relación a my a c. Los valores αij pueden ser dados en términos de los xλ, que están determinados. Analizamos los posibles valores de los xλpara λ≤p−1cuando la cota se alcanza: 2c=m−2p+c0−3. 102 CAPÍTULO 2. PRELIMINARES Sea tun número natural tal que t≤m−2c−1. El sistema {f(i, j, k)=0|i+j+k≤t} se denota por S(t). Proposición 2.6.20. Supongamos que c0= 5 yp= 13. Entonces 2c≥ m−18 = m−p−5 = m−2p+c0+ 3. Más aún, se tienen las siguientes afirmaciones: 1. x1=x2=x3= 0 satisface S(15). 2. Si 16 ≤m−2c−1, entonces se satisface S(16) si, y sólo si, x1=x2= x3=x4= 0 óx1=x2=x3= 0,x4=x5. 3. Si 17 ≤m−2c−1, entonces se satisface S(17) si, y sólo si, x1=x2= x3=x4= 0. 4. Si 18 ≤m−2c−1, entonces se satisface S(18) si, y sólo si, x1=x2= x3=x4=x5= 0. Por consiguiente, 2c≥m−18 = m−p−5. Nota 2.6.21. Concluimos que la asignación 0 = x1=x2=x3=x4,x6= 8x5,x7= 7x5,x8= 9x5,x9=x5,x10 = 7x5,x11 = 8x5,x12 = 6x5satisface S(17) y existe un álgebra de Lie L(m, c)que satisface p= 13 y17 = m−2c−1. Proposición 2.6.22. Supongamos que c0= 5 yp= 17. Entonces 2c≥ m−26 = m−2p+c0+3. Más aún, se tiene una de las siguientes afirmaciones: 1. Si 23 ≤m−2c−1, entonces xi= 0,1≤i≤5. Más aún, las asignaciones a)x1=x2=x3=x4=x5= 0, ó b)x1=x2=x3=x4= 0,x7=−2x5,x6= 2x5,x56= 0 satisfacen el sistema de Jacobi S(22). 2. Si 25 ≤m−2c−1, entonces xi= 0,1≤i≤6, esto es, l≥c0+ 2 = 7. Nota 2.6.23. Concluimos que la asignación 0 = x1=x2=x3=x4=x5=x6, x8= 2x7, x9=−2x7, x10 = 4x7, x11 = 7x7, x12 =−6x7, x13 =x7, x14 =−8x7, x15 =−7x7, x16 = 8x7, satisface S(25) y existe un álgebr de Lie L(m, c)que satisface p= 17 y 26 = m−2c−1. 2.6. COTAS PARA c0≤5103 Proposición 2.6.24. Supongamos que c0= 5 yp= 19. Entonces 2c≥ m−30 = m−2p+c0+ 3. Más aún, 1. Si 24 ≤m−2c−1, entonces xi= 0,1≤i≤5. Además, la asignación x1=x2=x3=x4= 0,x6= 7x5,x7= 4x5,x8= 10x5,x56= 0, satisface S(23). 2. Si 27 ≤m−2c−1, entonces xi= 0,1≤i≤6, esto es, l≥c0+ 2 = 7. Además, la asignación xi= 0,1≤i≤5,x7= 7x6,x8= 4x6, satisface S(26). 3. La asignación xi= 0,1≤i≤6,x8=−3x7,x76= 0, satisface S(28). 4. Si 29 ≤m−2c−1, entonces xi= 0,1≤i≤7. Nota 2.6.25. Notemos que la asignación 0 = x1=x2=x3=x4=x5=x6=x7, x9= 7x8, x10 = 4x8, x11 =−9x8, x12 =−2x8, x13 =−7x8, x14 = 7x8, x15 =−x8, x16 = 9x8, x17 = 8x8, x18 =−9x8, satisface S(29) y existe un álgebra de Lie L(m, c)que satisface p= 19, 30 = m−2c−1. Teorema 2.6.26. Supongamos c0= 5 yp > 19. Entonces 1. Si 2l≤p−11, entonces 2c≥m−p−2. 2. Si p−1>2l≥p−9, tenemos 2c≥m−2l−p+c0−1≥m−2p+c0+ 3 3. Si 2l=p−1, entonces c≥m−p−1. Teorema 2.6.27. Si c0= 5, entonces Cl(Y1)≤3, salvo en los siguientes casos excepcionales: 1. Cl(Y1)=4,c=p+ 4 ym≤4p. 2. c= 5,m≤2p+ 2. 104 CAPÍTULO 2. PRELIMINARES Capítulo 3 Cotas para 6≤c0≤10 3.1. Introducción En este capítulo nos proponemos ampliar el estudio realizado en [29] a los p-grupos de clase maximal con 6≤c0≤10. Nuestro objetivo en este capítulo es probar el siguiente resultado, que extiende el ya conocido para 6≤c0≤10: Teorema 3.1.1. Sea Gun p-grupo de clase maximal con p > 13 y6≤c0≤ 10, entonces 2c≥m´ın(m−p−2, m −2l−p+c0−1). Además, para l≥c0−2, podemos precisar la cota de acuerdo con la tabla 3.3. Observamos que la periodicidad módulo p−1es una condición fundamental para probar este teorema, y encontramos ejemplos de álgebras de Lie que no verifican la periodicidad módulo p−1pero sí satisfacen las condiciones de Jacobi (por supuesto, estas álgebras de Lie no podrán ser nunca las álgebras de Lie de p-grupos de clase maximal). En particular, encontramos un contraejemplo a la cota 2c≥m−2p+ 5, encontrada por G. A. Fernández-Alcober en [7] cuando se suprime la condición sobre la periodicidad módulo p−1. Las técnicas computacionales desarrolladas para implementar estos lemas y obtener los resultados se explican en la sección 3.2. Los resultados teóricos preliminares necesarios ya han sido explicados en la sección 2.6. 105 112 CAPÍTULO 3. COTAS PARA 6≤c0≤10 Si queremos obtener cotas más pequeñas para estos valores, podemos modificar este algoritmo tomando más filas (por ejemplo, c0+ 2 filas para obtener la cota 2c≥m−p−3, en lugar de la cota 2c≥m−p−2obtenida con c0+ 1 filas). Esto permite obtener zj=z1,j≤c0, en todas las configuraciones derivadas de las configuraciones en las que el primer método falla, con la excepción de aquellas con el triángulo TGcon sólo ceros. A continuación mostramos un ejemplo de aplicación del algoritmo recién descrito: Ejemplo 3.2.4. Consideremos la siguiente configuración: •0• • • • 0 0•0 • • • • • • 30 Por aplicación del Lema 2.6.1, obtenemos: z1=z13 z2=z14 z3=z13 z4=z13 z5=z13 z6=z13 z7=z14 z8=z8 z9=z14 z10 =z13 z11 =z13 z12 =z13 z13 =z13 z14 =z14 3.2. EL ALGORITMO 113 Los αi,j que se anulan son los siguientes: α1,1= 5z13 −5z14 α2,2= 7z8+ 14z13 −21z14 α3,3=−56z8−42z13 + 98z14 α4,4= 126z8+ 84z13 −210z14 α2,7= 924z8+ 658z13 −1582z14 α3,5=−252z8−168z13 + 420z14 α1,6=−330z8−286z13 + 616z14 α3,4=−126z8−84z13 + 210z14 Tenemos que hacer substituciones. Teniendo en cuenta que α1,1= 5z13 −5z14, tenemos que z14 =z13. Esta substitución es válida para p > 5. De este modo los valores de las αi,j nulas y las zison: α1,1= 0 α2,2= 7z8−7z13 α3,3=−56z8+ 56z13 α4,4= 126z8−126z13 α2,7= 924z8−924z13 α3,5=−252z8+ 252z13 α1,6=−330z8+ 330z13 α3,4=−126z8+ 126z13 z1=z13 z2=z13 z3=z13 z4=z13 114 CAPÍTULO 3. COTAS PARA 6≤c0≤10 z5=z13 z6=z13 z7=z13 z8=z8 z9=z13 z10 =z13 z11 =z13 z12 =z13 z13 =z13 z14 =z13 Algoritmo 3.2.5 (Aplicación de la identidad de Jacobi).Es posible precisar aún más las cotas 2c≥m−2l−p+c0−1, al menos, en los casos c0−2≤lmediante un nuevo algoritmo que usa la identidad de Jacobi. Para obtener una cota de tipo 2c≥m−a, suponemos que a≤m−2c−1, y, aplicando la identidad de Jacobi, que tiene sentido mientras que i+j+k≤a, se llega a la contradicción xl= 0. De este modo, expresamos los valores de los αi,j que aparecen en estas identidades de Jacobi como función de los xk, y usamos que xk= 0 para k < l y que xl6= 0. Esto nos permite obtener una forma cuadrática en las variables xique, en algunos casos, puede ser factorizada por xl(en algunos casos, la forma puede ser factorizado por xl+1 o una combinación de xlyxl+1). En consecuencia, tenemos una forma lineal en las variables xique se anula y podemos despejar la variable que tenga el menor número primo como máximo divisor primo de su coeficiente. Substituimos el valor de esta variable en una lista de las variables xi,l≤i≤l+c0. Calculamos también el menor número primo que hace que todas estas substituciones tengan sentido. Estos cálculos pueden hacerse usando el tipo entero descrito en el segundo algoritmo. En algunos casos, la identidad de Jacobi toma la forma ax2 l+bxlxl+1 +cx2 l+1. En este caso, buscamos dos identidades no proporcionales de este tipo y eliminamos x2 l+1 entre ellas. Esto nos permite despejar xl+1 como función de xl, después de eliminar el factor común xl6= 0. Estas factorizaciones nos aparecen en el caso l=c0−2. De esta manera, obtenemos todas las identidades de Jacobi f(i, j, k)con i+j+k=npara valores crecientes de ncon n≥6. El primer npara el cual obtenemos xl= 0 es el adado al principio. El algoritmo también da 3.2. EL ALGORITMO 115 los valores de xl+1,. . .,xl+c0que satisfacen todas las ecuaciones de Jacobi f(i, j, k)para i+j+k < a. Para saber los primos para los cuales este argumento es válido, tenemos que recordar la periodicidad módulo p−1, que nos permite sólo asignar hasta (p−3)/2variables (las otras están asignadas por la periodicidad). Podemos obtener también una nueva versión de este programa en el caso en que fijamos un primo p. Podemos argumentar como antes con enteros ordinarios módulo p(lo cual incrementa considerablemente la velocidad de los cálculos). La periodicidad módulo p−1está implementada mediante las condiciones α1,p = 0 yαi,p+i=xi; cada una de estas condiciones nos da una nueva variable, hasta que obtenemos todos los valores de xi,i≤p−2. Describimos a continuación algunos datos sobre esta última versión del algoritmo. Algo que resulta fundamental en el desarrollo de este algoritmo es un algoritmo de factorización de formas cuadráticas en Zp, que esquematizamos como sigue: Supongamos que la forma que deseamos factorizar viene dada por Pai,jxixj, en primer lugar se estudia si existe un ai,i distinto de cero o si todos los ai,i valen cero. 1. Si existe un ital que ai,i = 0, en la descomposición de la forma bilineal en factores lineales debe aparecer la variable xi. Entonces la descomposición es del tipo (xi+f)(xi+g). Para lograr el resto de los sumandos, nos fijamos en los términos en xixjcon j6=i. Tomemos el primero de ellos. Si la forma factorizase, en uno de los factores o en ambos debería aparecer xj. Para obtener el coeficiente de xjen estos factores se tiene sólo en cuenta la parte ai,ix2 i+ai,jxixj+aj,jx2 jy se escribe en la forma (xi+bxj)(xi+cxj), siendo byclas raíces de la ecuación ai,iy2+ai,jy+aj,j = 0. Si esta ecuación en yno tiene raíces, la descomposición no es posible y se termina el proceso. Si tiene raíces, ya tenemos los dos primeros sumandos de la factorización. Para buscar el siguiente sumando, tomamos el siguiente xixkque aparece en la forma bilineal con k6=i,ai,k 6= 0. Repetimos el estudio de ai,ix2 i+ai,kxixk+ak,kx2 k. Si la ecuación en yasociada tiene solución y sus raíces son dye, entonces los primeros sumandos serán (xi+bxj+dxk)(xi+cxj+exk) o(xi+bxj+exk)(xi+cxj+dxk)y el propio programa se encarga de seleccionar la factorización adecuada o de determinar que la factorización no es posible por no verificarse las relaciones debidas entre xjy 116 CAPÍTULO 3. COTAS PARA 6≤c0≤10 xk. Dicho procedimiento se sigue hasta que se obtiene la factorización o se llega a la conclusión de que ésta es imposible. 2. Si todos los coeficientes ai,i son nulos, entonces xisólo puede aparecer en uno de los factores. Entonces, si es que existe descomposición, debe ser de la forma (Pbixi) (Pcixi), donde bi= 0 si ci6= 0. Se toma un xixjtal que ai,j 6= 0. Se examinan las relaciones que deben existir entre los coeficientes y así se obtiene la descomposición o se determina que ésta no existe. En este algoritmo es necesario resolver una ecuación cuadrática en Zp. Los algoritmos para su resolución, en particular, el algoritmo de Shanks para la extracción de raíces cuadradas en Zp, figuran en [9, capítulos 3, 4 y 11]. El algoritmo de cálculo de cotas comienza expresando xkpara k≥(p−1)/2 en función de xl,xl+1, . . .,x(p−3)/2utilizando la periodicidad módulo p−1. Comenzamos con n= 6,nc= 5,nm= 5. Calculamos las expresiones de Jacobi en el nivel n, y analizamos si alguna de ellas factoriza como producto de dos formas lineales. Si es así, guardamos uno de ellos en una pila junto con los valores actuales de ncy las xiy despejamos de la otra una de las variables, substituimos y volvemos a plantear las ecuaciones de Jacobi para el nivel n=nc+ 1. Si ninguna de las formas factoriza, entonces aumentamos ny calculamos las expresiones de Jacobi para el nuevo valor de nhasta que alguna forma factorice. Al mismo tiempo, el valor de nmse incrementa si n pasa a ser mayor que nm. Este proceso se sigue realizando hasta que se llegue a la contradicción xl= 0. En este caso, se recupera de la pila el valor del factor que nos quedaba y despejamos una variable de esta forma y volvemos a plantear las ecuaciones de Jacobi para el nivel n=nc+1, con el nctomado de la pila y los valores de las xialmacenados en la pila. Este proceso se reitera hasta que tengamos la pila vacía. Desde luego, hay que tener en cuenta que si uno de los factores que aparece en una factorización es xl, o si ambos factores son iguales, no hace falta guardar en la pila el otro factor, lo cual permite no considerar algunas ramas en el algoritmo. Se puede obtener una cota “exacta” si la contradicción se alcanza en el nivel máximo nm. Sin embargo, en algunos casos esto no ocurre, ya que no aparece ninguna ecuación de Jacobi que factorice hasta un determinado nivel nmy después, al hacer las substituciones en niveles nmás bajos, se obtenga la 3.2. EL ALGORITMO 117 contradicción. Esto ocurre para valores de lpequeños, como se ve en las tablas 4.26 y 4.27. Se puede instruir al algoritmo para que dé los valores de las variables xien cada nivel, en particular, en el nivel anterior al nmde la contradicción. La versión de este algoritmo sin números primos nos llevó 1081,44 segundos de CPU, mientras que la segunda versión necesitó 781,01 segundos de CPU. Escribimos en las tablas 3.3 las cotas obtenidas de modo que el número a significa 2c≥m−a. Los valores para las xique nos permiten afirmar que estas cotas son las mejores posibles son los que aparecen en las tablas 3.4 a 3.8. El signo ∗ denota que cualquier valor posible de la variable en dicha columna satisface el álgebra de Lie correspondiente, mientras que combinaciones que no son de la forma xi=r·xlaparecen escritas en la forma xi=r1xj1+r2xj2+· · · . El siguiente ejemplo nos muestra el resultado del algoritmo para c0= 6. Ejemplo 3.2.6. Supongamos que l= 5,c0= 6. En el nivel 12: Consideremos la ecuación de Jacobi: f(1,5,6) = x5−330x5+252x6−84x7+ 8x8. Despejamos x8de −330x5+ 252x6−84x7+ 8x8= 0. La substitución es válida para p > 2. x5=x5 x6=x6 x7=x7 x8= (165/4)x5−(63/2)x6+ (21/2)x7 x9=x9 x10 =x10 x11 =x11 En el nivel 13: Consideremos la ecuación de Jacobi: f(2,5,6) = x5−990x5+672x6−168x7+ x9. 118 CAPÍTULO 3. COTAS PARA 6≤c0≤10 Cuadro 3.3: Cotas obtenidas con la identidad de Jacobi c0= 6 p= 17 p= 19 p= 23 p≥29 l= 4 20 21 16 16 l= 5 22 24 17 18 l= 6 23 26 29 20 l= 7 25 27 32 22 c0= 7 p= 17 p= 19 p= 23 p= 29 p= 31 p > 31 l= 5 21 23 26 19 19 19 l= 6 23 25 29 21 21 21 l= 7 27 31 22 23 23 l= 8 28 33 38 24 25 c0= 8 p= 19 p= 23 p= 29 p= 31 p > 31 l= 6 24 28 21 22 22 l= 7 25 30 35 23 24 l= 8 32 38 39 26 l= 9 33 40 42 28 c0= 9 p= 19 p= 23 p= 29 p= 31 p= 37 p > 37 l= 7 24 29 35 36 25 25 l= 8 31 37 39 27 27 l= 9 32 39 41 28 29 l= 10 41 43 48 31 c0= 10 p= 23 p= 29 p= 31 p= 37 p= 41 p= 43 p > 43 l= 8 29 36 38 27 28 28 28 l= 9 31 38 40 45 30 30 30 l= 10 40 42 48 31 32 32 l= 11 41 44 50 53 33 34 3.2. EL ALGORITMO 119 Cuadro 3.4: Álgebras de Lie para c0= 6 l= 4 p x5/x4x6/x4x7/x4x8/x4x9/x4x10/x4 17 2 15 4 19 7 4 10 17 >23 20/11 25/11 200/77 35/11 56/11 210/11 l= 5 p x6/x5x7/x5x8/x5x9/x5x10/x5x11/x5 17 10 14 19 7 4 10 23 14 8 12 10 21 >23 5/2 25/6 25/4 10 21 105 l= 6 p x7/x6x8/x6x9/x6x10/x6x11/x6x12/x6 17 ∗ 19 16 10 23 20 7 21 4 >23 36/11 7 40/3 27 72 462 l= 7 p x8/x7x9/x7x10/x7x11/x7x12/x7x13/x7 17 19 ∗ 23 20 7 21 >23 91/22 364/33 26 65 429/2 1716 120 CAPÍTULO 3. COTAS PARA 6≤c0≤10 Cuadro 3.5: Álgebras de Lie para c0= 7 l= 5 p x6/x5x7/x5x8/x5x9/x5x10/x5x11/x5x12/x5 17 12 7 19 16 10 8 23 20 7 21 4 3 >23 30/13 45/13 175/39 75/13 108/13 210/13 990/13 l= 6 p x7/x6x8/x6x9/x6x10/x6x11/x6x12/x6x13/x6 17 13 19 12 14 23 20 7 21 4 >23 3 63/11 28/3 15 27 66 396 l= 7 p x8/x7x9/x7x10/x7x11/x7x12/x7x13/x7x14/x7 19 13 23 8 20 6 29 6 1 2 6 19 28 >29 49/13 98/11 196/11 35 77 231 1716 l= 8 p x9/x8x10/x8x11/x8x12/x8x13/x8x14/x8x15/x8 19 23 11 19 29 18 12 16 17 24 31 7 13 29 13 12 2 >31 60/13 1890/143 350/11 75 198 715 6435 3.2. EL ALGORITMO 121 Cuadro 3.6: Álgebras de Lie para c0= 8 l= 6 p x7/x6x8/x6x9/x6x10/x6x11/x6x12/x6x13/x6x14/x6 19 13 8 23 8 20 6 5 29 26 2 24 4 14 26 18 >29 14/5 49/10 392/55 49/5 14 231/10 264/5 3003/10 l= 7 p x8/x7x9/x7x10/x7x11/x7x12/x7x13/x7x14/x7x15/x7 19 ∗ 23 11 19 3 29 18 12 16 17 24 19 31 19 29 19 11 23 15 13 >31 7/2 98/13 147/11 245/11 77/2 77 429/2 3003/2 l= 8 p x9/x8x10/x8x11/x8x12/x8x13/x8x14/x8x15/x8x16/x8 23 12 8 29 18 12 16 17 24 31 27 23 30 26 3 18 >31 64/15 144/13 3360/143 140/3 96 1144/5 2288/3 6435 l= 9 p x10/x9x11/x9x12/x9x13/x9x14/x9x15/x9x16/x9x17/x9 23 ∗ 29 3 3 10 9 31 27 23 30 26 3 >31 51/10 204/13 510/13 1190/13 221 3094/5 2431 24310 128 CAPÍTULO 3. COTAS PARA 6≤c0≤10 Despejamos x8a partir de 12x5+ 5x6+ 11x7+ 8x8= 0. x5=x5 x6=x6 x7=x7 x8= 8x5+ 16x6+x7 En el nivel 13: Consideremos la ecuación de Jacobi: f(2,5,6) = x52x5+ 17x6+ 3x7. Despejamos x7a partir de 2x5+ 17x6+ 3x7= 0. x5=x5 x6=x6 x7= 12x5+ 7x6 x8=x5+ 4x6 En el nivel 23: Consideremos la ecuación de Jacobi: f(6,8,9) = x513x5+ 9x6. Despejamos x6a partir de 13x5+ 9x6= 0. x5=x5 x6= 7x5 3.2. EL ALGORITMO 129 x7= 4x5 x8= 10x5 En el nivel 24: Consideremos la ecuación de Jacobi: f(7,8,9) = x511x5. Despejamos x5a partir de 11x5= 0. x5= 0 x6= 7x5 x7= 4x5 x8= 10x5 Consideremos ahora los valores l= 5,c0= 6,p= 23. Éstos son los valores iniciales: x5=x5 x6=x6 x7=x7 x8=x8 x9=x9 x10 =x10 x11 = 22x5+ 4x6+ 5x7+ 13x8+ 21x9+ 20x10 x12 = 4x5+ 10x6+ 12x7+ 12x8+ 19x9+ 7x10 x13 = 10x5+ 9x6+ 22x7+ 11x8+ 21x9+ 21x10 x14 =x5+ 2x6+ 22x7+ 19x8+ 15x9+ 4x10 x15 = 3x5+ 17x6+ 22x7+ 5x8+ 11x9+ 3x10 x16 = 20x5+ 15x6+ 9x7+ 15x8+ 22x9+ 2x10 x17 = 14x5+ 5x6+ 2x7+ 12x8+ 11x9+ 16x10 x18 = 20x5+ 9x6+ 16x7+ 3x8+ 3x9+ 9x10 130 CAPÍTULO 3. COTAS PARA 6≤c0≤10 x19 = 4x5+ 10x6+ 8x7+ 18x8+ 8x9+ 22x10 x20 = 3x5+ 5x7+ 18x8+ 20x9+ 11x10 x21 = 15x5+x6+ 9x7+ 10x8+ 19x9+ 10x10 En el nivel 12: Consideremos la ecuación de Jacobi: f(1,5,6) = x515x5+22x6+8x7+8x8. Despejamos x8a partir de 15x5+ 22x6+ 8x7+ 8x8= 0. x5=x5 x6=x6 x7=x7 x8=x5+ 3x6+ 22x7 x9=x9 x10 =x10 En el nivel 13: Consideremos la ecuación de Jacobi: f(2,5,6) = x522x5+ 5x6+ 16x7+x9. Despejamos x9a partir de 22x5+ 5x6+ 16x7+x9= 0. x5=x5 x6=x6 x7=x7 x8=x5+ 3x6+ 22x7 x9=x5+ 18x6+ 7x7 x10 =x10 3.2. EL ALGORITMO 131 En el nivel 14: Consideremos la ecuación de Jacobi: f(3,5,6) = x517x5+x6+ 22x7. Despejamos x7a partir de 17x5+x6+ 22x7= 0. x5=x5 x6=x6 x7= 17x5+x6 x8= 7x5+ 2x6 x9= 5x5+ 2x6 x10 =x10 En el nivel 15: Consideremos la ecuación de Jacobi: f(4,5,6) = x519x5+ 10x6+ 22x10. Despejamos x10 a partir de 19x5+ 10x6+ 22x10 = 0. x5=x5 x6=x6 x7= 17x5+x6 x8= 7x5+ 2x6 x9= 5x5+ 2x6 x10 = 19x5+ 10x6 En el nivel 16: Consideremos la ecuación de Jacobi: f(3,6,7) = x617x5+ 7x6. 132 CAPÍTULO 3. COTAS PARA 6≤c0≤10 Despejamos x6a partir de 17x5+ 7x6= 0. x5=x5 x6= 14x5 x7= 8x5 x8= 12x5 x9= 10x5 x10 = 21x5 En el nivel 17: Consideremos la ecuación de Jacobi: f(4,6,7) = x52x5. Despejamos x5a partir de 2x5= 0. x5= 0 x6= 14x5 x7= 8x5 x8= 12x5 x9= 10x5 x10 = 21x5 Nota 3.2.7. Ya mencionamos anteriormente que existían algunos casos en los cuales la identidad zi=zjpara j≤c0no se da, entre ellos, los correspondientes a x16= 0,x2=x3=· · · =xc/2= 0,x(c/2)+1 = (−1)(c/2)+1x1. Para estas configuraciones, obtenemos la igualdad z1=zjcuando tomamos una fila más. Esto nos permite afirmar que 2c≥m−p−3, pero podemos usar argumentos similares a los empleados para l≥c0−2y obtener así cotas mejores. La tabla 3.9 nos muestra las cotas correspondientes a c0= 6,c0= 8 yc0= 10, así como las correspondientes álgebras de Lie. 3.2. EL ALGORITMO 133 Cuadro 3.9: Álgebras de Lie correspondientes a los casos especiales con c0 par c06 8 10 2c≥12 14 16 p > 7>13 >11 x20 0 0 x30 0 0 x4x10 0 x52x1−x10 x63x1(−10/3)x1x1 x7(32/7)x1(−73/9)x15x1 x89x1(−487/27)x118x1 x9(−3124/81)x159x1 x10 16x1188x1 x11 (6540/11)x1 x12 25x1 134 CAPÍTULO 3. COTAS PARA 6≤c0≤10 Cuadro 3.10: Los otros casos c08 9 10 10 l5 6 6 7 2c≥p+ 3 p+ 4 p+ 3 p+ 5 Los casos no desechados por nuestros algoritmos se estudian añadiendo suficientes filas al triángulo TGhasta que obtenemos la condición z1=zjpara j≤c0. La tabla 3.10 muestra las cotas halladas para estos casos. Nota 3.2.8. Existen álgebras de Lie no asociativas sobre Fpque no cumplen la periodicidad módulo p−1. En efecto, consideremos el álgebra de Lie dada por x1=x2=x3= 0,x4=x56= 0,x6=−4x4,x7=−28x4,x8= 3x4, x9= 4x4,x10 =−10x4,x11 = 8x4,x12 =x13 = 0,x14 6= 0,x15 =x16 =x17 = x18 =x19 =x20 = 0, pero x46=x4+17−1=x20 = 0. Esta álgebra satisface las igualdades de Jacobi, pero no verifica la propiedad (C4) (periodicidad módulo p−1), luego no puede ser el álgebra de Lie de un p-grupo. Más aún, no podemos omitir la hipótesis (C4) para probar la cota 2c≥m−2p+ 5 dada por Fernández-Alcober en [7], porque m−2c−1≥34 para esta álgebra. Capítulo 4 Nuevas cotas Tras aplicar los algoritmos mostrados en el capítulo 3 conjeturamos la existencia de regiones dependientes de c0,lypen las cuales las cotas para el grado de conmutatividad de un p-grupo de clase maximal son exactas, en el sentido de la existencia de álgebras de Lie para los niveles anteriores. Mediante los invariantes lyc0asociados a estos grupos, encontramos nuevas cotas para c(G)de la forma 2c≥m−g(c0, l, p)para g(c0, l, p)una función adecuada de c0,lyp. Presentamos algunas conjeturas para estas cotas, y probamos algunas de ellas. En muchos de estos resultados juegan un papel importante los coeficientes zi=αi,p−c0, es éste el motivo de la siguiente sección. 4.1. Resultados obtenidos a partir de las zi Lema 4.1.1. Supongamos que 2l+c0≤p≤2c0+ 2l−3yz1=zjpara 1≤j≤p−c0−2l+ 3. Entonces se llega a la contradicción xl= 0. Demostración. Como z1=zjfor 1≤l≤p−c0−2l+ 3, obtenemos que αi,p−c0+1 = 0 para 1≤i≤p−c0−2l+ 2. Tenemos también que αi,p−c0+1 = [(p−c0+i)/2] X k=i (−1)k−ip−c0−k k−ixk = [(p−c0+i)/2]−l+1 X s=1 (−1)s+l−1−ip−c0−l+ 1 −s p−c0−2l+ 2 −2s+ixs+l−1. 135 136 CAPÍTULO 4. NUEVAS COTAS Denotemos r=p−c0−l+ 1,t=e=p−c0−2l+ 2. Si el determinante de la matriz de coeficientes es un múltiplo de p(notemos que es una matriz cuadrada, porque la condición p−c0+e 2−l+1 = p−c0+p−c0−2l+ 2 2−l+1 = p−c0−2l+2 = e se tiene), pdebe dividir r−wpara 1≤w≤t−1, o pdebe dividir 2r−w−1 para t−e+ 1 ≤w≤t+e−3. Pero 0< l ≤r−w≤p−c0−l < p para 1≤w≤t−1 = p−c0−2l+ 1, y, si t−e+ 1 ≤w≤t+e−3, 1≤w≤2p−2c0−4l+ 1, luego 0<2l≤2r−w−1 = 2p−2c0−2l+ 1 −w≤2p−2c0−2l y, por hipótesis, 2c0+ 2l≥p+ 3, de donde 2p−2c0−2l≤p−3< p. Por consiguiente, el determinante es múltiplo de p. Concluimos que xl= 0. Lema 4.1.2. Supongamos que (p+ 3)/2≤2l+c0≤p≤2c0+ 2l−3y c0+ 1 ≤2l. Entonces 2c≥m−p−2l+c0−1. Demostración. Supongamos que 2l+p−c0+ 1 ≤m−2c−1. Considerando pares de valores adyacentes no nulos en las filas 2l+ 1 y2l+ 2 del triángulo TG, obtenemos que zi=z2l+1+c0para 1≤i≤l−1y que zi=z2l+1+c0para l+ 1 ≤i≤2l. Supongamos que c0+ 1 ≤2l. Consideremos α1,2l−c0= 2l−1 X u=0 (−1)u2l−1 uz1+u. Sabemos que z1+u=z2l+c0+1 cuando u6=l−1, luego tenemos que α1,2l−c0= (−1)l−12l−1l−1zl−(−1)l−12l−1l−1z2l+1+c0= 0, teniendo en cuenta que P2l−1 u=0 (−1)u2l−1 u= 0. Por tanto, obtenemos que zl=z2l+1+c0, y tenemos la condición z1=zjpara 1≤j≤2l. Un argumento inductivo nos muestra que z1=zjpara 1≤j≤c0+ 2l. Efectivamente, si tenemos que z1=zjpara 1≤j≤k, con 2l≤k < c0+ 2l, podemos considerar α1,k+1−c0= k X u=0 (−1)uk uz1+u, 4.1. RESULTADOS OBTENIDOS A PARTIR DE LAS zi137 y teniendo en cuenta que Pk−1 u=0(−1)uk−1u= 0, obtenemos que α1,k+1−c0= (−1)kzk+1 −(−1)kz1= 0, de donde z1=zk+1. Recordando que (p+ 3)/2≤2l+c0, deducimos que p≤4l+ 2c0−3, so p−c0−2l+3 ≤2l+c0. Por el lema anterior, se llega a una contradicción. Lema 4.1.3. Supongamos que c0≥2ly2l+c0≤p≤3l+c0−4. Entonces 2c≥m−(p+ 2l−c0+ 1). Demostración. Observemos que, si c0≥2l,3l+c0−4≤l+ 2c0−4≤ 2c0+ 2l−3, ya que −4≤l−3. Supongamos que p+ 2l−c0+ 1 ≤m−2c−1. Como p≤3l+c0−4, p−2l−c0+ 3 ≤l−1. Además, z1=zjpara j≤l−1. Por consiguiente, zj=z1para 1≤j≤p−2l−c0+3. Como 2l+c0≤p≤3l+c0−4, llegamos a la contradicción xl= 0. Lema 4.1.4. Supongamos que c0≥2lyl+c0+2 ≤p≤2l+c0−1. Entonces 2c≥m−(p+ 2l−c0+ 1). Demostración. Supongamos que p+2l−c0+1 ≤m−2c−1. Como p≥l+c0+2, 2l+ 1 −p+c0≤l−1. En consecuencia, zj=z1para 1≤j≤2l+ 1 −p+c0. Por otra parte, z1=α1,p−c0= 0, ya que p−c0+ 1 ≤2l, y z2l+1−p+c0= α2l+1−p+c0,p−c0= 0, una contradicción, ya que (2l+ 1 −p+c0) + (p−c0) = 2l+ 1. Obsérvese que hemos probado que, si c0≥2lyl+c0+ 2 ≤p≤3l+c0−4, entonces 2c≥m−(p+ 2l−c0+ 1). Lema 4.1.5. Supongamos que l≥3,4l≤p+ 5 yc0=p−3l+ 3. Entonces 2c≥m−(p+ 2l−c0+ 1). Demostración. Supongamos que l≥3,4l≤p+ 5 yc0=p−3l+ 3, y p+2l−c0+1 ≤m−2c−1. En primer lugar, tenemos que z1=zjpara j≤l−1. 144 CAPÍTULO 4. NUEVAS COTAS p= 31 1 2 3 4 5 6 7 8 9 10 11 12 13 14 c0= 0 32 6 8 10 12 14 16 18 20 22 24 26 28 30 c0= 1 33 9 9 11 13 15 17 19 21 23 25 27 29 30 c0= 2 32 10 10 12 14 16 18 20 22 24 26 28 29 57 c0= 3 32 11 11 13 15 17 19 21 23 25 27 28 54 57 c0= 4 32 12 12 14 16 18 20 22 24 26 27 51 54 55 c0= 5 31 15 13 15 17 19 21 23 25 26 48 51 53 54 c0= 6 30 17 14 16 18 20 22 24 25 45 48 50 51 53 c0= 7 29 18 15 17 19 21 23 24 42 45 47 49 51 52 c0= 8 28 24 16 18 20 22 23 39 42 44 46 48 49 51 c0= 9 27 23 19 19 21 22 36 39 41 43 45 47 48 50 c0= 10 26 25 18 20 21 33 36 38 40 42 44 45 47 49 c0= 11 25 24 21 20 30 33 35 37 39 41 43 45 46 48 c0= 12 24 24 20 27 30 32 34 36 38 40 42 43 45 47 c0= 13 24 23 24 27 29 31 33 35 37 39 41 42 44 46 c0= 14 25 22 24 26 28 30 32 34 36 38 39 41 43 45 c0= 15 32 22 23 25 27 29 31 33 35 37 39 40 42 44 c0= 16 30 21 22 24 26 28 30 32 34 36 37 39 41 43 c0= 17 28 20 21 23 25 27 29 31 33 35 36 38 40 42 c0= 18 26 19 21 23 24 26 28 30 32 33 35 37 39 41 c0= 19 24 18 20 21 23 25 27 29 31 33 34 36 38 40 c0= 20 23 17 19 21 22 24 26 28 30 32 33 35 37 39 c0= 21 22 16 18 19 21 23 25 27 32 30 32 34 36 38 c0= 22 26 15 17 18 20 22 24 32 27 29 31 33 35 37 c0= 23 23 14 15 17 19 21 32 24 26 28 30 32 34 36 c0= 24 24 13 15 16 18 32 21 23 25 27 29 31 33 35 c0= 25 26 12 13 15 32 18 20 22 24 26 28 30 32 34 c0= 26 28 11 12 32 15 17 19 21 23 25 27 29 31 33 c0= 27 30 9 32 12 14 16 18 20 22 24 26 28 30 32 c0= 28 32 32 9 11 13 15 17 19 21 23 25 27 29 31 c0= 29 32 6 8 10 12 14 16 18 20 22 24 26 28 30 Cuadro 4.9: Cotas para p= 31 4.2. LAS CONJETURAS 145 p= 37 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 c0= 0 38 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 c0= 1 39 9 9 11 13 15 17 19 21 23 25 27 29 31 33 35 36 c0= 2 38 10 10 12 14 16 18 20 22 24 26 28 30 32 34 35 69 c0= 3 38 11 11 13 15 17 19 21 23 25 27 29 31 33 34 66 69 c0= 4 38 12 12 14 16 18 20 22 24 26 28 30 32 33 63 66 67 c0= 5 37 15 13 15 17 19 21 23 25 27 29 31 32 60 63 65 66 c0= 6 36 17 14 16 18 20 22 24 26 28 30 31 57 60 62 63 65 c0= 7 35 18 15 17 19 21 23 25 27 29 30 54 57 59 61 63 64 c0= 8 35 28 16 18 20 22 24 26 28 29 51 54 56 58 60 61 63 c0= 9 33 31 24 19 21 23 25 27 28 48 51 53 55 57 59 60 62 c0= 10 32 28 18 20 22 24 26 27 45 48 50 52 54 56 57 59 61 c0= 11 32 27 28 21 23 25 26 42 45 47 49 51 53 55 57 58 60 c0= 12 31 29 31 22 24 25 39 42 44 46 48 50 52 54 55 57 59 c0= 13 30 29 30 25 24 36 39 41 43 45 47 49 51 53 54 56 58 c0= 14 29 28 24 23 33 36 38 40 42 44 46 48 50 51 53 55 57 c0= 15 28 29 23 30 33 35 37 39 41 43 45 47 49 51 52 54 56 c0= 16 29 28 27 30 32 34 36 38 40 42 44 46 48 49 51 53 55 c0= 17 29 26 27 29 31 33 35 37 39 41 43 45 47 48 50 52 54 c0= 18 38 26 26 28 30 32 34 36 38 40 42 44 45 47 49 51 53 c0= 19 36 25 25 27 29 31 33 35 37 39 41 43 45 46 48 50 52 c0= 20 34 24 24 26 28 30 32 34 36 38 40 42 43 45 47 49 51 c0= 21 32 23 23 25 27 29 31 33 35 37 39 41 42 44 46 48 50 c0= 22 30 22 23 25 27 28 30 32 34 36 38 39 41 43 45 47 49 c0= 23 28 21 22 24 25 27 29 31 33 35 37 39 40 42 44 46 48 c0= 24 27 19 21 23 24 26 28 30 32 34 36 38 39 41 43 45 47 c0= 25 26 18 20 21 23 25 27 29 31 33 38 36 38 40 42 44 46 c0= 26 28 17 19 21 22 24 26 28 30 38 33 35 37 39 41 43 45 c0= 27 29 16 18 19 21 23 25 27 38 30 32 34 36 38 40 42 44 c0= 28 26 15 17 18 20 22 24 38 27 29 31 33 35 37 39 41 43 c0= 29 28 14 15 17 19 21 38 24 26 28 30 32 34 36 38 40 42 c0= 30 30 13 15 16 18 38 21 23 25 27 29 31 33 35 37 39 41 c0= 31 32 12 13 15 38 18 20 22 24 26 28 30 32 34 36 38 40 c0= 32 34 11 12 38 15 17 19 21 23 25 27 29 31 33 35 37 39 c0= 33 36 9 38 12 14 16 18 20 22 24 26 28 30 32 34 36 38 c0= 34 38 38 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 c0= 35 38 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 Cuadro 4.10: Cotas para p= 37 146 CAPÍTULO 4. NUEVAS COTAS p= 41 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 c0= 0 42 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 c0= 1 43 9 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 40 c0= 2 42 10 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 39 77 c0= 3 42 11 11 13 15 17 19 21 23 25 27 29 31 33 35 37 38 74 77 c0= 4 42 12 12 14 16 18 20 22 24 26 28 30 32 34 36 37 71 74 75 c0= 5 41 15 13 15 17 19 21 23 25 27 29 31 33 35 36 68 71 73 74 c0= 6 40 17 14 16 18 20 22 24 26 28 30 32 34 35 65 68 70 71 73 c0= 7 39 18 15 17 19 21 23 25 27 29 31 33 34 62 65 67 69 71 72 c0= 8 39 28 16 18 20 22 24 26 28 30 32 33 59 62 64 66 68 69 71 c0= 9 37 31 17 19 21 23 25 27 29 31 32 56 59 61 63 65 67 68 70 c0= 10 36 33 18 20 22 24 26 28 30 31 53 56 58 60 62 64 65 67 69 c0= 11 36 31 28 21 23 25 27 29 30 50 53 55 57 59 61 63 65 66 68 c0= 12 34 30 29 22 24 26 28 29 47 50 52 54 56 58 60 62 63 65 67 c0= 13 34 30 34 23 25 27 28 44 47 49 51 53 55 57 59 61 62 64 66 c0= 14 33 31 33 24 26 27 41 44 46 48 50 52 54 56 58 59 61 63 65 c0= 15 32 31 32 27 26 38 41 43 45 47 49 51 53 55 57 59 60 62 64 c0= 16 31 31 31 26 35 38 40 42 44 46 48 50 52 54 56 57 59 61 63 c0= 17 31 32 27 32 35 37 39 41 43 45 47 49 51 53 55 56 58 60 62 c0= 18 32 31 29 32 34 36 38 40 42 44 46 48 50 52 53 55 57 59 61 c0= 19 33 30 29 31 33 35 37 39 41 43 45 47 49 51 53 54 56 58 60 c0= 20 42 28 28 30 32 34 36 38 40 42 44 46 48 50 51 53 55 57 59 c0= 21 40 29 27 29 31 33 35 37 39 41 43 45 47 49 50 52 54 56 58 c0= 22 38 27 26 28 30 32 34 36 38 40 42 44 46 47 49 51 53 55 57 c0= 23 36 26 25 27 29 31 33 35 37 39 41 43 45 47 48 50 52 54 56 c0= 24 34 25 24 27 29 30 32 34 36 38 40 42 44 45 47 49 51 53 55 c0= 25 32 24 24 26 27 29 31 33 35 37 39 41 43 44 46 48 50 52 54 c0= 26 30 23 23 25 27 28 30 32 34 36 38 40 42 43 45 47 49 51 53 c0= 27 30 21 22 24 25 27 29 31 33 35 37 39 42 42 44 46 48 50 52 c0= 28 29 21 21 23 24 26 28 30 32 34 36 42 39 41 43 45 47 49 51 c0= 29 28 19 20 21 23 25 27 29 31 33 42 36 38 40 42 44 46 48 50 c0= 30 32 17 19 21 22 24 26 28 30 42 33 35 37 39 41 43 45 47 49 c0= 31 29 16 18 19 21 23 25 27 42 30 32 34 36 38 40 42 44 46 48 c0= 32 30 15 17 18 20 22 24 42 27 29 31 33 35 37 39 41 43 45 47 c0= 33 32 14 15 17 19 21 42 24 26 28 30 32 34 36 38 40 42 44 46 c0= 34 34 13 15 16 18 42 21 23 25 27 29 31 33 35 37 39 41 43 45 c0= 35 36 12 13 15 42 18 20 22 24 26 28 30 32 34 36 38 40 42 44 c0= 36 38 11 12 42 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 c0= 37 40 9 42 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 c0= 38 42 42 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 c0= 39 42 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 Cuadro 4.11: Cotas para p= 41 Blackburn dio en [2] la cota 2c≥m−6para p= 5 para cualquier valor de c0 (véase la tabla 4.1). Shepherd probó en [22, Theorem 1.27] la cota 2c≥m−8 para c0∈ {0,1,4,5}y2c≥m−9para c0∈ {2,3}, como se puede observar en la tabla 4.2. La observación de las tablas 4.1 a 4.12 nos lleva a realizar las siguientes conjeturas: Conjetura A. 1. Si p+7 6≤l=p+1 2−c0, entonces 2c≥m−p−2l+c0. 2. Si p−c0≤l≤p−3 2, entonces 2c≥m−p−2l+c0. 3. Si c0≥2p−4l−2y3l > p, o c0= 2p−4l−4y3l > p, entonces 2c≥m−p−2l+c0. 4.2. LAS CONJETURAS 147 p= 43 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 c0= 0 44 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 c0= 1 45 9 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 42 c0= 2 44 10 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 41 81 c0= 3 44 11 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 40 78 81 c0= 4 44 12 12 14 16 18 20 22 24 26 28 30 32 34 36 38 39 75 78 79 c0= 5 43 15 13 15 17 19 21 23 25 27 29 31 33 35 37 38 72 75 77 78 c0= 6 42 17 14 16 18 20 22 24 26 28 30 32 34 36 37 69 72 74 75 77 c0= 7 41 18 15 17 19 21 23 25 27 29 31 33 35 36 66 69 71 73 75 76 c0= 8 40 28 16 18 20 22 24 26 28 30 32 34 35 63 66 68 70 72 73 75 c0= 9 39 31 24 19 21 23 25 27 29 31 33 34 60 63 65 67 69 71 72 74 c0= 10 38 33 25 20 22 24 26 28 30 32 33 57 60 62 64 66 68 69 71 73 c0= 11 37 35 28 21 23 25 27 29 31 32 54 57 59 61 63 65 67 69 70 72 c0= 12 36 32 30 22 24 26 28 30 31 51 54 56 58 60 62 64 66 67 69 71 c0= 13 36 31 30 23 25 27 29 30 48 51 53 55 57 59 61 63 65 66 68 70 c0= 14 35 33 35 25 26 28 29 45 48 50 52 54 56 58 60 62 63 65 67 69 c0= 15 34 32 34 29 27 28 42 45 47 49 51 53 55 57 59 61 63 64 66 68 c0= 16 33 32 33 28 27 39 42 44 46 48 50 52 54 56 58 60 61 63 65 67 c0= 17 32 33 32 27 36 39 41 43 45 47 49 51 53 55 57 59 60 62 64 66 c0= 18 33 33 31 33 36 38 40 42 44 46 48 50 52 54 56 57 59 61 63 65 c0= 19 33 33 30 33 35 37 39 41 43 45 47 49 51 53 55 57 58 60 62 64 c0= 20 34 31 30 32 34 36 38 40 42 44 46 48 50 52 54 55 57 59 61 63 c0= 21 44 29 29 31 33 35 37 39 41 43 45 47 49 51 53 54 56 58 60 62 c0= 22 42 30 28 30 32 34 36 38 40 42 44 46 48 50 51 53 55 57 59 61 c0= 23 40 29 27 29 31 33 35 37 39 41 43 45 47 49 51 52 54 56 58 60 c0= 24 38 28 26 28 30 32 34 36 38 40 42 44 46 48 49 51 53 55 57 59 c0= 25 36 27 25 27 30 31 33 35 37 39 41 43 45 47 48 50 52 54 56 58 c0= 26 34 26 25 27 29 30 32 34 36 38 40 42 44 45 47 49 51 53 55 57 c0= 27 32 24 24 26 27 29 31 33 35 37 39 41 43 45 46 48 50 52 54 56 c0= 28 32 23 23 25 27 28 30 32 34 36 38 40 42 44 45 47 49 51 53 55 c0= 29 30 21 22 24 25 27 29 31 33 35 37 39 44 42 44 46 48 50 52 54 c0= 30 28 19 21 23 24 26 28 30 32 34 36 44 39 41 43 45 47 49 51 53 c0= 31 35 18 20 21 23 25 27 29 31 33 44 36 38 40 42 44 46 48 50 52 c0= 32 32 17 19 21 22 24 26 28 30 44 33 35 37 39 41 43 45 47 49 51 c0= 33 30 16 18 19 21 23 25 27 44 30 32 34 36 38 40 42 44 46 48 50 c0= 34 32 15 17 18 20 22 24 44 27 29 31 33 35 37 39 41 43 45 47 49 c0= 35 34 14 15 17 19 21 44 24 26 28 30 32 34 36 38 40 42 44 46 48 c0= 36 36 13 15 16 18 44 21 23 25 27 29 31 33 35 37 39 41 43 45 47 c0= 37 38 12 13 15 44 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 c0= 38 40 11 12 44 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 c0= 39 42 9 44 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 c0= 40 44 44 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 c0= 41 44 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 Cuadro 4.12: Cotas para p= 43 148 CAPÍTULO 4. NUEVAS COTAS Conjetura B. 1. Si p+ 6 ≤c0+ 4l≤2p−5, entonces 2c≥m−p−2l+ c0−1. 2. Si p+ 4 = c0+ 4l≤2p−5, entonces 2c≥m−p−2l+c0−1. 3. Si p+ 6 ≤c0+ 4l= 2p−3, entonces 2c≥m−p−2l+c0−1. 4. Si l≥3,p+1 2≤c0+l−1,c0+ 2 <2(p−1) 3yc0+ 4l≤2p−5o c0+ 4l= 2p−3, then 2c≥m−p−2l+c0−1. 5. Si c0+l= 3l=p−2, entonces 2c≥m−p−2l+c0−1. Conjetura C. Si l=p−c0−1y3l < p, entonces 2c≥m−p−1. Conjetura D. 1. Si 2 + c0 7≤l≤p−5 2−c0, entonces 2c≥m−2l−c0−2. 2. Si 3 + c0 7≤l=p−3 2−c0, entonces 2c≥m−2l−c0−2. Conjetura E. Si p+5 6≤l=p−1 2−c0, entonces 2c≥m−2l−c0−1. Conjetura F. 1. Si 3≤l,c0+4l=p+5 oc0+4l≤p+3, y c0+3 ≥2 3p, entonces 2c≥m−p−2l+c0−2. 2. Si l= 1,p−1 2≤c0<2 3(p−1), entonces 2c≥m−2p+ 2c0. Conjetura G. Si l= 1,p≥13 yp−2−p−1 6≤c0≤p−2, entonces 2c≥m−p−1 + 2(p−c0−3). Para las casillas de la tabla que no corresponden a las regiones cubiertas por las conjeturas previas, observamos que los valores asociados son menores que 3p/4. El siguiente Lema será utilizado en las Secciones 4.3 y 4.5. Lema 4.2.1. Si 3l≤m−2c−1yl≥2, entonces α1,2l+c0+k= 0 para 1≤k≤l−1. Demostración. Tenemos que 3l≤m−2c−1, luego podemos aplicar la identidad de Jacobi para las ternas (l−k, l, l + 1), siendo k∈ {1, . . . , l −1}. Entonces obtenemos que 0 = xlα2l+1+c0,l−k, 4.2. LAS CONJETURAS 149 p = 17 1 2 3 4 5 6 7 0 6 8 10 12 14 16 1 9 11 13 15 16 2 10 12 14 15 29 3 11 13 14 26 29 4 13 23 26 27 5 12 20 23 25 26 6 20 22 23 25 7 17 19 21 23 24 818 17 18 20 21 23 916 15 17 19 20 22 10 15 16 18 19 21 11 13 15 18 18 20 12 12 18 15 17 19 13 16 9 18 12 14 16 18 14 18 18 9 11 13 15 17 15 18 6 8 10 12 14 16 Cuadro 4.13: Cotas conjeturadas para p= 17 150 CAPÍTULO 4. NUEVAS COTAS a p = 19 1 2 3 4 5 6 7 8 0 6 8 10 12 14 16 18 1 9 11 13 15 17 18 2 10 12 14 16 17 33 3 11 13 15 16 30 33 4 12 14 15 27 30 31 5 14 24 27 29 30 6 21 24 26 27 29 7 21 23 25 27 28 8 18 20 22 24 25 27 920 17 19 21 23 24 26 10 18 17 18 20 21 23 25 11 16 15 17 19 21 22 24 12 15 16 18 20 21 23 13 13 15 20 18 20 22 14 16 12 20 15 17 19 21 15 18 9 20 12 14 16 18 20 16 20 20 9 11 13 15 17 19 17 20 6 8 10 12 14 16 18 Cuadro 4.14: Cotas conjeturadas para p= 19 4.2. LAS CONJETURAS 151 p = 23 1 2 3 4 5 6 7 8 9 10 0 6 8 10 12 14 16 18 20 22 1 9 11 13 15 17 19 21 22 2 10 12 14 16 18 20 21 41 3 11 13 15 17 19 20 38 41 4 12 14 16 18 19 35 38 39 5 13 15 17 18 32 35 37 38 6 14 16 17 29 32 34 35 37 7 16 26 29 31 33 35 36 8 26 28 30 32 33 35 9 23 25 27 29 31 32 34 10 20 22 24 26 28 29 31 33 11 24 19 21 23 25 27 29 30 32 12 22 19 21 22 24 26 27 29 31 13 20 18 19 21 23 25 26 28 30 14 17 18 20 22 24 25 27 29 15 15 17 19 21 24 24 26 28 16 15 16 18 24 21 23 25 27 17 13 15 24 18 20 22 24 26 18 20 12 24 15 17 19 21 23 25 19 22 9 24 12 14 16 18 20 22 24 20 24 24 9 11 13 15 17 19 21 23 21 24 6 8 10 12 14 16 18 20 22 Cuadro 4.15: Cotas conjeturadas para p= 23 152 CAPÍTULO 4. NUEVAS COTAS p = 29 1 2 3 4 5 6 7 8 9 10 11 12 13 0 6 8 10 12 14 16 18 20 22 24 26 28 1 9 11 13 15 17 19 21 23 25 27 28 2 10 12 14 16 18 20 22 24 26 27 53 3 11 13 15 17 19 21 23 25 26 50 53 4 12 14 16 18 20 22 24 25 47 50 51 5 13 15 17 19 21 23 24 44 47 49 50 6 14 16 18 20 22 23 41 44 46 47 49 7 15 17 19 21 22 38 41 43 45 47 48 8 18 20 21 35 38 40 42 44 45 47 9 20 32 35 37 39 41 43 44 46 10 32 34 36 38 40 41 43 45 11 29 31 33 35 37 39 41 42 44 12 26 28 30 32 34 36 38 39 41 43 13 23 25 27 29 31 33 35 37 38 40 42 14 30 22 24 26 28 30 32 34 35 37 39 41 15 28 21 23 25 27 29 31 33 35 36 38 40 16 26 21 23 24 26 28 30 32 33 35 37 39 17 24 20 21 23 25 27 29 31 32 34 36 38 18 19 21 22 24 26 28 30 31 33 35 37 19 18 19 21 23 25 27 30 30 32 34 36 20 17 18 20 22 24 30 27 29 31 33 35 21 15 17 19 21 30 24 26 28 30 32 34 22 15 16 18 30 21 23 25 27 29 31 33 23 24 13 15 30 18 20 22 24 26 28 30 32 24 26 12 30 15 17 19 21 23 25 27 29 31 25 28 9 30 12 14 16 18 20 22 24 26 28 30 26 30 30 9 11 13 15 17 19 21 23 25 27 29 27 30 6 8 10 12 14 16 18 20 22 24 26 28 Cuadro 4.16: Cotas conjeturadas para p= 29 4.2. LAS CONJETURAS 153 p = 31 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 6 8 10 12 14 16 18 20 22 24 26 28 30 1 9 11 13 15 17 19 21 23 25 27 29 30 2 10 12 14 16 18 20 22 24 26 28 29 57 3 11 13 15 17 19 21 23 25 27 28 54 57 4 12 14 16 18 20 22 24 26 27 51 54 55 5 13 15 17 19 21 23 25 26 48 51 53 54 6 14 16 18 20 22 24 25 45 48 50 51 53 7 15 17 19 21 23 24 42 45 47 49 51 52 8 18 20 22 23 39 42 44 46 48 49 51 9 19 21 22 36 39 41 43 45 47 48 50 10 33 36 38 40 42 44 45 47 49 11 33 35 37 39 41 43 45 46 48 12 30 32 34 36 38 40 42 43 45 47 13 27 29 31 33 35 37 39 41 42 44 46 14 24 26 28 30 32 34 36 38 39 41 43 45 15 32 23 25 27 29 31 33 35 37 39 40 42 44 16 30 22 24 26 28 30 32 34 36 37 39 41 43 17 28 21 23 25 27 29 31 33 35 36 38 40 42 18 26 21 23 24 26 28 30 32 33 35 37 39 41 19 24 20 21 23 25 27 29 31 33 34 36 38 40 20 19 21 22 24 26 28 30 32 33 35 37 39 21 18 19 21 23 25 27 32 30 32 34 36 38 22 17 18 20 22 24 32 27 29 31 33 35 37 23 15 17 19 21 32 24 26 28 30 32 34 36 24 24 15 16 18 32 21 23 25 27 29 31 33 35 25 26 13 15 32 18 20 22 24 26 28 30 32 34 26 28 12 32 15 17 19 21 23 25 27 29 31 33 27 30 9 32 12 14 16 18 20 22 24 26 28 30 32 28 32 32 9 11 13 15 17 19 21 23 25 27 29 31 29 32 6 8 10 12 14 16 18 20 22 24 26 28 30 Cuadro 4.17: Cotas conjeturadas para p= 31 256 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS extern long int CONTADOR; extern long int LONG_FILA_TeX; extern long int OVERFLOW, STACK_OVERFLOW; int zetas_iguales(zeta_vector *z, int c_cero) { int res, i; res=1; for (i=1; (i<c_cero)&&res; i++) { if (!son_casillas_iguales(**z, *(*z+i))) { res=0; }; }; return(res); } int numero_de_ceros(triang tr, int fila) { int num_de_ceros, i, j; num_de_ceros=0; for (i=fila-1;i>=0;i--) { for (j=0;j<=(i/2);j++) { if (es_cero(tr[i][j])) { num_de_ceros++; }; }; }; return(num_de_ceros); } int iniciar_zetas(zeta_vector *z, indice_de_casilla **z_cas, triang tr, int fila, int c_cero) { int i,j,k,num_de_ceros,u; num_de_ceros=numero_de_ceros(tr,fila); for (i=0;i<num_de_ceros+tr[0][0].longitud;i++) { (*z+i)->longitud=fila+c_cero+1; for (u=0;u<fila+c_cero+1;u++) { (*z+i)->coef[u].num=0; (*z+i)->coef[u].den=1; }; }; vermem(*z_cas=(indice_de_casilla*) malloc((num_de_ceros+tr[0][0].longitud) * sizeof(indice_de_casilla))); for (i=0;i<tr[0][0].longitud;i++) { A.1. CEROS Y NO CEROS 257 for (u=0;u<i+c_cero+1;u++) { ((*z+i)->coef)[i+u].num=(u%2) ? (-choose(i+c_cero,u)) : (choose(i+c_cero,u)); ((*z+i)->coef)[i+u].den=1; }; (*z_cas)[i][0]=i+1; (*z_cas)[i][1]=i+1; }; k=tr[0][0].longitud; for(i=fila-1;i>=0;i--) { for (j=0;j<=(i/2);j++) { if (es_cero(tr[i][j])) { for (u=0;u<i+2-j+c_cero;u++) { ((*z+k)->coef[j+u]).num=(u%2) ? (-choose(i-j+1+c_cero,u)) : (choose(i-j+1+c_cero,u)); ((*z+k)->coef[j+1]).den=1; }; (*z_cas)[k][0]=j+1; (*z_cas)[k][1]=i+2-j; k++; }; }; }; return(num_de_ceros+tr[0][0].longitud); } /* Definicion de numero combinatorio */ unsigned long int choose(unsigned long int x1, unsigned long int x2) { unsigned long int i, res, temp; STACK_OVERFLOW++; if (STACK_OVERFLOW > MAX_STACK_OVERFLOW) { fprintf(stderr,"Desbordamiento de pila en funci\363n choose.\n"); exit(1); }; if (x2>x1) { STACK_OVERFLOW--; return ((unsigned long) 0); } else { if (2*x2>x1) { STACK_OVERFLOW--; return(choose(x1,x1-x2)); } else { 258 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS res=1; for (i=0;i<x2;i++) { temp=(x1-i)/(i+1); if (log_2_int(temp)+log_2_int(res) > 31) { OVERFLOW=1; return(res); }; res*=temp; }; STACK_OVERFLOW--; return(res); }; }; } void aplicar_lema_dos_uno(int mat[], int long_mat, int a, int b) { int i, mat_a, mat_b; mat_a=mat[a-1]; mat_b=mat[b-1]; if (mat_a>mat_b) { aplicar_lema_dos_uno(mat, long_mat, b, a); } else { if (mat_a<mat_b) { for (i=0;i<long_mat;i++) { if (mat[i]==mat_a) { mat[i]=mat_b; }; }; }; }; /* no se hace nada si mat[a-1]==mat[b-1] */ } void iniciar_lema_dos_uno(int mat[], int long_mat) { int i; for (i=0; i<long_mat; i++) { mat[i]=i+1; }; } void lema_dos_uno(zeta_vector *z, indice_de_casilla **z_cas, zeta_vector *zeta, triang tr, int fila, int c_cero, int num_de_alphas_nulas, FILE *salida) { A.1. CEROS Y NO CEROS 259 int *mat; int i, j, k, long_mat; long_mat=fila+c_cero+1; vermem(mat=(int *) malloc(long_mat*sizeof(int))); iniciar_lema_dos_uno(mat, fila+c_cero+1); for (i=0;i<fila;i++) { for (j=0;j<=(i/2);j++) { if (!es_cero(tr[i][j])) { if (j < (i/2)) { if (!es_cero(tr[i][j+1])) { aplicar_lema_dos_uno(mat, long_mat, j+1, i-j+1); }; }; if (i < fila-1) { if (j < ((i+1)/2)) { if (!es_cero(tr[i+1][j+1])) { aplicar_lema_dos_uno(mat, long_mat, j+1, 3+i+c_cero); } }; if (!es_cero(tr[i+1][j])) { aplicar_lema_dos_uno(mat, long_mat, i+2-j, 3+i+c_cero); if (j<((i+1)/2)-1) { if (es_cero(tr[i+1][j+1])) { if (!es_cero(tr[i+1][j+2])) { if (!es_cero(tr[i][j+1])) { aplicar_lema_dos_uno(mat, long_mat, j+2, i+2-j); } }; }; }; }; }; }; }; }; for(i=0; i<num_de_alphas_nulas;i++) 260 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS { substituye_rapido_casilla(*z+i,mat); }; verifica(fprintf(salida, "Por aplicaci\\’on del \\LemaDosUno," " obtenemos:\n")); verifica(fprintf(salida, "\\begin{eqnarray*}\n")); for (i=0;i<fila+c_cero+1;i++) { (*zeta+i)->longitud=fila+c_cero+1; for (k=0; k<fila+c_cero+1; k++) { (*zeta+i)->coef[k].num=0; (*zeta+i)->coef[k].den=1; }; (*zeta+i)->coef[mat[i]-1].num=1; verifica(fprintf(salida, "z_{%d}&=&", i+1)); escribe_casilla_archivo_TeX(*(*zeta+i), "z", salida); if (i<fila+c_cero) { verifica(fprintf(salida, "\\\\")); }; verifica(fprintf(salida, "\n")); }; verifica(fprintf(salida, "\\end{eqnarray*}\n\n\\begin{eqnarray*}\n")); for (k=0; k<num_de_alphas_nulas; k++) { verifica(fprintf(salida, "\\alpha_{%d,%d}&=&", (*z_cas)[k][0], (*z_cas)[k][1])); escribe_casilla_archivo_TeX(*(*z+k), "z", salida); if (k<num_de_alphas_nulas-1) { verifica(fprintf(salida, "\\\\")); }; verifica(fprintf(salida, "\n")); }; verifica(fprintf(salida, "\\end{eqnarray*}\n\n")); free(mat); } /* en la fila i, columna j, nos aparece el $\alpha_{j+1, i+2-j}$ */ void substituye_rapido_casilla(casilla *cas, int mat[]) { int i; for (i=0; i<cas->longitud; i++) { if (i!=mat[i]-1) { cas->coef[mat[i]-1]=sum(cas->coef[mat[i]-1], cas->coef[i]); cas->coef[i].num=0; cas->coef[i].den=1; }; }; } void debuga_casillas(zeta_vector zv, int numero_de_filas) { A.1. CEROS Y NO CEROS 261 int i; for(i=0; i<numero_de_filas; i++) { escribe_casilla(*(zv+i)); printf(" - [%d]\n",i); }; } int despejar_una_variable_en_lista(zeta_vector *z, indice_de_casilla **z_cas, zeta_vector *zeta, triang tr, int fila, int c_cero, int num_de_alphas_nulas, FILE *salida, FILE *salida_log, FILE *salida_log2) { despeje des, des1; int i, posicion_en_lista; long int p, mp; posicion_en_lista=-1; mp=0; for (i=0;i<num_de_alphas_nulas;i++) { if (!es_cero(*(*z+i))) { des1=despejar_una_variable(*(*z+i)); p=mayor_primo(des1.cas.coef[des1.pos].num); if (OVERFLOW) { break; }; if ((mp>p) || (posicion_en_lista<0)) { mp=p; des=des1; posicion_en_lista=i; if (mp==1) { break; }; }; }; }; if (OVERFLOW) { fprintf(stderr, "Detectado desbordamiento entero.\n"); verifica(fprintf(salida, "\n\n{\\Huge\\bf Desbordamiento entero, " "empezamos de nuevo.}\n")); return(0); }; if (posicion_en_lista < 0) { /* Lo siento, todo son ceros */ verifica(fprintf(salida, "\n\n{\\Huge\\bf Imposible" " seguir adelante $\\ldots$}\n")); escribe_salida(tr,fila,salida_log); 262 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS verifica(fprintf(salida_log2, "%ld\n", CONTADOR)); return(0); } else { substituir_una_variable_en_lista(z, z_cas, zeta, tr, fila, c_cero, num_de_alphas_nulas, posicion_en_lista, des, salida); if (OVERFLOW) { fprintf(stderr, "Desbordamiento entero detectado.\n"); return(0); }; return(1); }; } void substituir_una_variable_en_lista(zeta_vector *z, indice_de_casilla **z_cas, zeta_vector *zeta, triang tr, int fila, int c_cero, int num_de_alphas_nulas, int num_de_var, despeje des, FILE *salida) { zeta_vector zz; int i; long int el_mcd; int *anulado, nanulados; /* Primero obtenemos los indices para los cuales cambiamos de cero a */ /* no cero al hacer la substitucion. Efectuamos primero la */ /* substitucion.*/ vermem(anulado=(int *) malloc((fila+c_cero+1)*sizeof(int))); nanulados=0; vermem(zz=(zeta_vector) malloc(num_de_alphas_nulas*sizeof(casilla))); for (i=0; i<num_de_alphas_nulas;i++) { *(zz+i)= substituir(*(*z+i),des); if (OVERFLOW) { break; }; if(!es_cero(*(*z+i))) { if (es_cero(*(zz+i))) { anulado[nanulados]=i; nanulados++; }; }; }; for (i=0;i<fila+c_cero+1;i++) { A.1. CEROS Y NO CEROS 263 /* for (k=0; k<fila+c_cero+1; k++) { escribe_casilla(*(*zeta+k)); printf("=z_%d\n", k+1); }; for (k=0; k<num_de_ceros; k++) { escribe_casilla(*(*z+k)); printf("=\\alpha correspondiente a k=%d\n", k); }; */ if (!es_cero(*(*zeta+i))) { *(*zeta+i)= substituir(*(*zeta+i),des); if (OVERFLOW) { break; }; }; }; if (OVERFLOW) { return; }; if (!nanulados) { anulado[0]=0; }; el_mcd=(*z+anulado[0])->coef[des.pos].num; if (nanulados==1) { verifica(fprintf(salida,"\nRealizamos una substituci\\’on," " a partir del valor" " de $\\alpha_{%d,%d}$:\n", (*z_cas)[anulado[0]][0], (*z_cas)[anulado[0]][1])); } else { verifica(fprintf(salida, "\nRealizamos una substituci\\’on, a" " partir de los valores " "de $\\alpha_{%d,%d}$", (*z_cas)[anulado[0]][0], (*z_cas)[anulado[0]][1])); for (i=1;i<nanulados;i++) { el_mcd=gcd(el_mcd, (*z+anulado[i])->coef[des.pos].num); if (OVERFLOW) { break; }; if (i<nanulados-1) { verifica(fprintf(salida, ", ")); } else { 264 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS verifica(fprintf(salida, " y ")); }; verifica(fprintf(salida, "$\\alpha_{%d,%d}$", (*z_cas)[anulado[i]][0], (*z_cas)[anulado[i]][1])); }; verifica(fprintf(salida, ":\n")); }; if (OVERFLOW) { return; }; verifica(fprintf(salida, "\\begin{eqnarray*}\n")); for (i=0;i<nanulados;i++) { verifica(fprintf(salida, "\\alpha_{%d,%d} &=& ", (*z_cas)[anulado[i]][0], (*z_cas)[anulado[i]][1])); escribe_casilla_archivo_TeX(*(*z+(anulado[i])), "z", salida); if (i<nanulados-1) { verifica(fprintf(salida, "\\\\")); }; verifica(fprintf(salida, "\n")); }; verifica(fprintf(salida, "\\end{eqnarray*}\n$$z_{%d}=", des.pos+1)); escribe_casilla_archivo_TeX(*(*zeta+des.pos), "z", salida); verifica(fprintf(salida, "$$\n")); verifica(fprintf(salida, "\nEsta substituci\\’on es v\\’alida para" " $p>%ld$.\n", mayor_primo(el_mcd))); for (i=0; i<num_de_alphas_nulas;i++) { *(*z+i) =*(zz+i); }; free(zz); free(anulado); } A.1.14. El archivo gros.c #include <stdio.h> #include "bullet.h" #include "bulletvl.h" long int CONTADOR, LONG_FILA_TeX, STACK_OVERFLOW, OVERFLOW; verylong longint2vl(unsigned long int a) { verylong res; int k; res.sgn=0; res.coef[0]=a&0xFFFF; A.1. CEROS Y NO CEROS 265 res.coef[1]=a>>16; for (k=2;k<MAYOR;k++) { res.coef[k]=0; }; return(res); }; verylong sumavl(verylong a, verylong b) { verylong res; int i; if (es_cerovl(a)) { return(b); }; if (es_cerovl(b)) { return(a); }; for (i=0;i<MAYOR;i++) { res.coef[i]=0; }; res.sgn=0; if (a.sgn==b.sgn) { res.sgn=a.sgn; for(i=0;i<MAYOR-1;i++) { res.coef[i]+=a.coef[i]+b.coef[i]; if (res.coef[i] > 0xFFFF) { res.coef[i+1]++; res.coef[i] &= 0xFFFF; }; }; res.coef[MAYOR-1]+=a.coef[MAYOR-1]+b.coef[MAYOR-1]; if (res.coef[MAYOR-1] > 0xFFFF) { fprintf(stderr, "Desbordamiento en funci\363n sumavl:\n"); exit(1); }; }; if (a.sgn!=b.sgn) { if (!a.sgn) /* a>0>b */ { if (es_mayorvl(a,menosvl(b))) { res=(restavl(a, menosvl(b))); } else { res=(menosvl(restavl(menosvl(b), a))); 272 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS #include "bulletvl.h" extern long int CONTADOR; extern long int STACK_OVERFLOW; /* La siguiente funcion suma dos fraccionvles. */ fraccionvl sumfrvl(fraccionvl primero, fraccionvl segundo) { fraccionvl res, res2; res.num=sumavl(prodvl(primero.num, segundo.den), prodvl(primero.den, segundo.num)); res.den=prodvl(primero.den, segundo.den); res2=simplificafrvl(res); return(res2); } /* Calculo del opuesto de una fraccionvl */ fraccionvl menosfrvl(fraccionvl fr) { fraccionvl res; res.num=menosvl(fr.num); res.den=fr.den; return(simplificafrvl(res)); } /* Funcion disenyada para simplificar una fraccionvl */ fraccionvl simplificafrvl(fraccionvl fr) { verylong mcd; fraccionvl res; if (es_cerovl(fr.num)) { res.num=longint2vl(0); res.den=longint2vl(1); } else { mcd=gcdvl(fr.num,fr.den); res.num=divvl(fr.num,mcd); res.den=divvl(fr.den,mcd); }; if (res.den.sgn) { res.num.sgn=1-res.num.sgn; res.den.sgn=1-res.den.sgn; }; return res; } fraccionvl prodfrvl(fraccionvl primero, fraccionvl segundo) { fraccionvl t1, t2, t3, t4, t5, t6, res; A.1. CEROS Y NO CEROS 273 t1=simplificafrvl(primero); t2=simplificafrvl(segundo); t3.num=t1.num; t3.den=t2.den; t4.num=t2.num; t4.den=t1.den; t5=simplificafrvl(t3); t6=simplificafrvl(t4); res.num=prodvl(t5.num,t6.num); res.den=prodvl(t5.den,t6.den); /* res2=simplifica(res);*/ return (res); } fraccionvl inversafrvl(fraccionvl fr) { fraccionvl res; if (es_cerovl(fr.num)) { fprintf ( stderr, "Error en funcion \"inversafrvl\": No puedo" "dividir por cero"); exit(1); } else { res.num=fr.den; res.den=fr.num; return(res); }; } verylong gcdvl(verylong a, verylong b) { /* Nuestro objetivo aqui es aplicar el algoritmo de Euclides para el */ /* calculo del mcd de dos numeros enteros.*/ verylong res; STACK_OVERFLOW++; if (STACK_OVERFLOW > MAX_STACK_OVERFLOW) { fprintf(stderr, "Desbordamiento de pila en funcion gcdvl con parametros:\n"); escribevl_archivo(stderr, a); fprintf(stderr, "\ny\n"); escribevl_archivo(stderr, b); fprintf(stderr, "\n"); exit(1); }; if (es_cerovl(b)) { STACK_OVERFLOW--; return (a); } else { if (b.sgn) 274 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS { res=gcdvl(a,menosvl(b)); STACK_OVERFLOW--; return(res); }; if (a.sgn) { res=gcdvl(menosvl(a),b); STACK_OVERFLOW--; return(res); }; res=gcdvl(b,modvl(a,b)); STACK_OVERFLOW--; return(res); }; } void escribe_fraccionvl(fraccionvl fr) { printf("("); representa(fr.num); printf("/"); representa(fr.den); printf(")"); } verylong modvl(verylong a, verylong b) { int na, nb; /* ultimo "digito" significativo */ verylong res; /* el resultado que se debe devolver */ long int parcial[MAYOR+1]; /* resto parcial */ int i, j, k; /* contadores de bucle */ int e; /* un e de modo que multiplicaremos restos */ /* parciales y divisor por 2^e */ unsigned long int div1, div2;/* primera y segunda cifras, */ /* respectivamente, del divisor, una */ /* vez multiplicado por 2^e. */ unsigned long int m01, m2; /* dos primeras cifras y tercera */ /* cifra, respectivamente, de los */ /* restos parciales.*/ unsigned long int qi; /* cifra del cociente */ unsigned long int c; /* producto de dos digitos */ unsigned short int d; /* acarreo */ /*Esta rutina ha sido adaptada a partir del programa GAP, archivo */ /*"src/integer.c", por Martin Sch\"onert, Alice Niemeyer y Werner */ /*Nickel, v 3.9, 1993/01/28 18:51:32, que por supuesto no tienen */ /*nada que ver con los posibles desaguisados que puedan salir de */ A.1. CEROS Y NO CEROS 275 /*aqui. */ /* Eliminemos, en primer lugar, el caso trivial en que el divisor es */ /* cero. */ if (es_cerovl(b)) { fprintf(stderr,"Error: divisi\363n por cero.\n"); exit(1); }; /* Calculamos el numero de cifras significativas del dividendo y del */ /* divisor.*/ na=0; nb=0; for (i=0; i<MAYOR; i++) { if ((a.coef[i])) { na=i; }; if ((b.coef[i])) { nb=i; }; }; /* El caso en que no hay cifras significativas en el divisor se */ /* trata con una funcion especial */ if (!nb) { res.sgn=a.sgn; for (k=1; k<MAYOR; k++) { res.coef[k]=0; }; res.coef[0]=mod_intvl(a,b.coef[0]); return(res); }; /* Tambien es trivial el caso en que hay mas cifras en el divisor */ /* que en el dividendo. */ if (nb>na) { return(a); }; /* Los otros casos no han sido tratados anteriormente */ /* Obtenemos primero un e adecuado tal que multiplicaremos los */ /* restos parciales y el divisor por 2^e. */ for (e=0; (b.coef[nb]<<e) + (b.coef[nb-1]>>(16-e)) < 0x8000; e++); div1= (b.coef[nb]<<e) + (b.coef[nb-1]>>(16-e)); div2= ((b.coef[nb-1]<<e) + (nb>=2 ? b.coef[nb-2]>>(16-e) : 0))&0xFFFF; 276 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS /* Ya tenemos el divisor multiplicado por un 2^e suficientemente */ /* grande como para hacer los cocientes con un minimo de garantias. */ /* Observese que solo hemos tomado dos cifras del divisor, ya que el */ /* tipo long int tiene 32 bits. A continuacion se van calculando */ /* cifras del cociente y restos parciales. */ /* Antes de liarnos con el calculo de los cocientes y los restos */ /* parciales, asignaremos el dividendo como primer resto parcial. */ for (i=0; i<MAYOR; i++) { parcial[i]=a.coef[i]; }; parcial[MAYOR]=0; /* A continuacion nos queda devolver el resultado. */ for (i=(na-nb); i>=0; i--) { /* primer paso: intentar adivinar el cociente parcial */ j=i+nb; m01=((65536*parcial[j+1]+parcial[j])<<e) + (parcial[j-1]>>(16-e)); if (m01==0) continue; /*Si las dos primeras cifras del resto */ /*parcial son cero, "bajamos" la cifra */ /*siguiente */ m2=(parcial[j-1]<<e) + (j>=2 ? parcial[j-2]>>(16-e) : 0); /* Aqui se ha tratado de diferenciar los casos en que podemos */ /* considerar o no cifras anteriores. Hay que verificar la */ /* condicion, que esta de prueba.*/ if ((parcial[j+1]<<e) + (parcial[j]>>(16-e)) < div1) { qi=m01 / div1; /* !‘tiene sentido la division entera! */ } else { qi=0xFFFF; /* para las pruebas, tomaremos el mayor valor */ /* posible*/ }; while (m01-qi*div1<0x10000 && 0x10000 * (m01-qi*div1)+m2 < qi*div2) { qi--; }; /* aqui se trata de afinar la cifra del cociente */ /* a continuacion, se calcula el nuevo resto parcial */ d=0; for (k=0; k<=nb; k++) { c=parcial[k+i]-qi*b.coef[k]-d; parcial[k+i]=c&0xFFFF; d=-(c>>16); } A.1. CEROS Y NO CEROS 277 c=parcial[i+nb+1]-d; parcial[i+nb+1]=c&0xFFFF; d=-(c>>16); /* Si nos hemos quedado con valores finales negativos, anyadimos */ /* de nuevo */ if (d!=0) { d=0; for (k=0; k<=nb; k++) { c=parcial[k+i]+b.coef[k]+d; parcial[k+i]=c &0xFFFF; d=(c>>16); }; c=parcial[1+nb+i]+d; parcial[1+nb+i]=c& 0xFFFF; d=(c>>16); qi--; }; /* ?‘Funcionara? */ /* printf("i=%i\nrestos parciales:", i); for (k=MAYOR-1;k>=0; k--) { printf("%lu:",parcial[k]&0xFFFF); }; printf("\n"); */ }; for (k=0;k<MAYOR; k++) { res.coef[k]=parcial[k]; }; res.sgn=a.sgn; return(res); } verylong divvl(verylong a, verylong b) { int na, nb; /* ultimo "digito" significativo */ verylong res; /* el resultado que se debe devolver */ long int parcial[MAYOR+1]; /* resto parcial */ int i, j, k; /* contadores de bucle */ int e; /* un e de modo que multiplicaremos restos */ /* parciales y divisor por 2^e */ unsigned long int div1, div2;/* primera y segunda cifras, */ /* respectivamente, del divisor, una */ /* vez multiplicado por 2^e. */ 278 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS unsigned long int m01, m2; /* dos primeras cifras y tercera */ /* cifra, respectivamente, de los */ /* restos parciales.*/ unsigned long int qi; /* cifra del cociente */ unsigned long int c; /* producto de dos digitos */ unsigned short int d; /* acarreo */ /*Esta rutina ha sido adaptada a partir del programa GAP, archivo */ /*"src/integer.c", por Martin Sch\"onert, Alice Niemeyer y Werner */ /*Nickel, v 3.9, 1993/01/28 18:51:32, que por supuesto no tienen */ /*nada que ver con los posibles desaguisados que puedan salir de */ /*aqui. */ /* Eliminemos, en primer lugar, el caso trivial en que el divisor es */ /* cero. */ if (es_cerovl(b)) { fprintf(stderr,"Error: divisi\363n por cero.\n"); exit(1); }; res.sgn=(a.sgn!=b.sgn); for (k=0; k<MAYOR; k++) { res.coef[k]=0; }; /* Calculamos el numero de cifras significativas del dividendo y del */ /* divisor.*/ na=0; nb=0; for (i=0; i<MAYOR; i++) { if ((a.coef[i])) { na=i; }; if ((b.coef[i])) { nb=i; }; }; /* El caso en que no hay cifras significativas en el divisor se */ /* trata con una funcion especial */ if (!nb) { return(div_intvl(a,b.coef[0])); }; /* Tambien es trivial el caso en que hay mas cifras en el divisor */ /* que en el dividendo. */ if (nb>na) A.1. CEROS Y NO CEROS 279 { res.sgn=0; for (i=0; i<MAYOR; i++) { res.coef[i]=0; }; return(res); }; /* Los otros casos no han sido tratados anteriormente */ /* Obtenemos primero un e adecuado tal que multiplicaremos los */ /* restos parciales y el divisor por 2^e. */ for (e=0; (b.coef[nb]<<e) + (b.coef[nb-1]>>(16-e)) < 0x8000; e++); div1= (b.coef[nb]<<e) + (b.coef[nb-1]>>(16-e)); div2= ((b.coef[nb-1]<<e) + (nb>=2 ? b.coef[nb-2]>>(16-e) : 0))&0xFFFF; /* Ya tenemos el divisor multiplicado por un 2^e suficientemente */ /* grande como para hacer los cocientes con un minimo de garantias. */ /* Observese que solo hemos tomado dos cifras del divisor, ya que el */ /* tipo long int tiene 32 bits. A continuacion se van calculando */ /* cifras del cociente y restos parciales. */ /* Antes de liarnos con el calculo de los cocientes y los restos */ /* parciales, asignaremos el dividendo como primer resto parcial. */ for (i=0; i<MAYOR; i++) { parcial[i]=a.coef[i]; }; parcial[MAYOR]=0; for (i=(na-nb); i>=0; i--) { /* primer paso: intentar adivinar el cociente parcial */ j=i+nb; m01=((65536*parcial[j+1]+parcial[j])<<e) + (parcial[j-1]>>(16-e)); if (m01==0) continue; /*Si las dos primeras cifras del resto */ /*parcial son cero, "bajamos" la cifra */ /*siguiente */ m2=(parcial[j-1]<<e) + (j>=2 ? parcial[j-2]>>(16-e) : 0); /* Aqui se ha tratado de diferenciar los casos en que podemos */ /* considerar o no cifras anteriores. Hay que verificar la */ /* condicion, que esta de prueba.*/ if ((parcial[j+1]<<e) + (parcial[j]>>(16-e)) < div1) { qi=m01 / div1; /* !‘tiene sentido la division entera! */ } else { qi=0xFFFF; /* para las pruebas, tomaremos el mayor valor */ /* posible*/ }; 280 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS while (m01-qi*div1<0x10000 && 0x10000 * (m01-qi*div1)+m2 < qi*div2) { qi--; }; /* aqui se trata de afinar la cifra del cociente */ /* a continuacion, se calcula el nuevo resto parcial */ d=0; for (k=0; k<=nb; k++) { c=parcial[k+i]-qi*b.coef[k]-d; parcial[k+i]=c&0xFFFF; d=-(c>>16); } c=parcial[i+nb+1]-d; parcial[i+nb+1]=c&0xFFFF; d=-(c>>16); /* Si nos hemos quedado con valores finales negativos, anyadimos */ /* de nuevo */ if (d!=0) { d=0; for (k=0; k<=nb; k++) { c=parcial[k+i]+b.coef[k]+d; parcial[k+i]=c &0xFFFF; d=(c>>16); }; c=parcial[1+nb+i]+d; parcial[1+nb+i]=c& 0xFFFF; d=(c>>16); qi--; }; /* ?‘Funcionara? */ res.coef[i]=qi; /* printf("i=%i\nrestos parciales:", i); for (k=MAYOR-1;k>=0; k--) { printf("%lu:",parcial[k]&0xFFFF); }; printf("\n"); */ }; /* A continuacion nos queda devolver el resultado. */ return(res); } A.1. CEROS Y NO CEROS 281 A.1.16. El archivo casillavl.c /* Archivo casillavl.c */ /* Operaciones con casillavls del triangulo T_G usando enteros */ /* larguisimos.*/ #include <stdio.h> #include <stdlib.h> #include "bullet.h" #include "bulletvl.h" casillavl prodescvl(fraccionvl escalar, casillavl cas) { unsigned char i; casillavl res; res.longitud=cas.longitud; for (i=0; i<cas.longitud; i++) { res.coef[i]=prodfrvl(escalar, cas.coef[i]); }; return(res); } casillavl menos_casvl(casillavl cas) { fraccionvl menosuno; menosuno.num=longint2vl(1); menosuno.num.sgn=1; menosuno.den=longint2vl(1); return(prodescvl(menosuno,cas)); } casillavl sum_casvl(casillavl cas1, casillavl cas2) { unsigned char i; casillavl res; if (cas1.longitud!=cas2.longitud) { fprintf(stderr, "Error, solo esta definida la suma de" "\"casillavls\" de igual longitud"); exit(1); } else { res.longitud=cas1.longitud; for (i=0;i<cas1.longitud;i++) { res.coef[i]=sumfrvl(cas1.coef[i],cas2.coef[i]); } return (res); }; } int es_cero_casillavl(casillavl cas) { int escero; 288 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS int despejar_una_variablevl_en_lista(zeta_vectorvl *z, indice_de_casilla **z_cas, zeta_vectorvl *zeta, triang tr, int fila, int c_cero, int num_de_alphas_nulas, FILE *salida, FILE *salida_log, FILE *salida_log2) { despejevl des, des1; int i, posicion_en_lista; verylong p, mp; posicion_en_lista=-1; mp=longint2vl(0); for (i=0;i<num_de_alphas_nulas;i++) { if (!es_cero_casillavl(*(*z+i))) { des1=despejar_una_variablevl(*(*z+i)); p=mayor_primovl(des1.cas.coef[des1.pos].num,(es_cerovl(mp) ? MAXPR : mp)); if (es_mayorvl(mp,p) || (posicion_en_lista<0)) { mp=p; des=des1; posicion_en_lista=i; if (es_igualvl(mp,longint2vl(1))) { break; }; }; }; }; if (posicion_en_lista < 0) { /* Lo siento, todo son ceros */ verifica(fprintf(salida, "\n\n{\\Huge\\bf Imposible" " seguir adelante $\\ldots$}\n")); escribe_salida(tr,fila,salida_log); verifica(fprintf(salida_log2, "%ld\n", CONTADOR)); return(0); } else { substituir_una_variablevl_en_lista(z, z_cas, zeta, tr, fila, c_cero, num_de_alphas_nulas, posicion_en_lista, des, salida); return(1); }; } void substituir_una_variablevl_en_lista(zeta_vectorvl *z, indice_de_casilla **z_cas, zeta_vectorvl *zeta, triang tr, int fila, int c_cero, int num_de_alphas_nulas, int num_de_var, A.1. CEROS Y NO CEROS 289 despejevl des, FILE *salida) { zeta_vectorvl zz; int i; verylong el_mcd; int *anulado, nanulados; /* Primero obtenemos los indices para los cuales cambiamos de cero a */ /* no cero al hacer la substitucion. Efectuamos primero la */ /* substitucion.*/ vermem(anulado=(int *) malloc((fila+c_cero+1)*sizeof(int))); nanulados=0; vermem(zz=(zeta_vectorvl) malloc(num_de_alphas_nulas*sizeof(casillavl))); for (i=0; i<num_de_alphas_nulas;i++) { *(zz+i)= substituirvl(*(*z+i),des); if(!es_cero_casillavl(*(*z+i))) { if (es_cero_casillavl(*(zz+i))) { anulado[nanulados]=i; nanulados++; }; }; }; for (i=0;i<fila+c_cero+1;i++) { if (!es_cero_casillavl(*(*zeta+i))) { *(*zeta+i)= substituirvl(*(*zeta+i),des); }; }; if (!nanulados) { anulado[0]=0; }; el_mcd=(*z+anulado[0])->coef[des.pos].num; printf("Substitucion de z_%d.\n\t a partir de la fila %d\n", des.pos+1, anulado[0]); if (nanulados==1) { verifica(fprintf(salida,"\nRealizamos una substituci\\’on," " a partir del valor" " de $\\alpha_{%d,%d}$:\n", (*z_cas)[anulado[0]][0], (*z_cas)[anulado[0]][1])); } else { verifica(fprintf(salida, "\nRealizamos una substituci\\’on, a" " partir de los valores " "de $\\alpha_{%d,%d}$", (*z_cas)[anulado[0]][0], (*z_cas)[anulado[0]][1])); 290 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS for (i=1;i<nanulados;i++) { el_mcd=gcdvl(el_mcd, (*z+anulado[i])->coef[des.pos].num); if (i<nanulados-1) { verifica(fprintf(salida, ", ")); } else { verifica(fprintf(salida, " y ")); }; verifica(fprintf(salida, "$\\alpha_{%d,%d}$", (*z_cas)[anulado[i]][0], (*z_cas)[anulado[i]][1])); }; verifica(fprintf(salida, ":\n")); }; verifica(fprintf(salida, "\\begin{eqnarray*}\n")); for (i=0;i<nanulados;i++) { verifica(fprintf(salida, "\\alpha_{%d,%d} &=& ", (*z_cas)[anulado[i]][0], (*z_cas)[anulado[i]][1])); escribe_casillavl_archivo_TeX(*(*z+(anulado[i])), "z", salida); if (i<nanulados-1) { verifica(fprintf(salida, "\\\\")); }; verifica(fprintf(salida, "\n")); }; verifica(fprintf(salida, "\\end{eqnarray*}\n$$z_{%d}=", des.pos+1)); escribe_casillavl_archivo_TeX(*(*zeta+des.pos), "z", salida); verifica(fprintf(salida, "$$\n")); verifica(fprintf(salida, "\nEsta substituci\\’on es v\\’alida para" " $p>%ld$.\n", mayor_primovl(el_mcd, MAXPR).coef[0] + 65536 * mayor_primovl(el_mcd, MAXPR).coef[1])); for (i=0; i<num_de_alphas_nulas;i++) { *(*z+i) =*(zz+i); }; printf("Nuevas casillas:\n"); debuga_casillavls(zz, 18); printf("\n"); free(zz); free(anulado); } int mainvl(triang *tr, int tamanyo, indice_de_casilla **z_cas, FILE *salida, FILE*salida_log, FILE*salida_log2) { int se_puede_despejar; zeta_vectorvl *zvl, *zetavl; int num_de_alphas_nulas, i, num_de_ceros; fprintf(stderr, "CONTADOR=%ld - Enteros muy grandes...\n", CONTADOR); A.1. CEROS Y NO CEROS 291 /* escribe_bullets_uno(*tr, tamanyo, salida);*/ verifica(fprintf(salida, "\n\nRepetimos con enteros largos.\n\n")); num_de_ceros=numero_de_ceros(*tr,tamanyo); vermem(zvl=(zeta_vectorvl*) malloc(sizeof(zeta_vector))); vermem(*zvl=(zeta_vectorvl) malloc((num_de_ceros+(*tr)[0][0].longitud)*sizeof(casillavl))); vermem(zetavl=(zeta_vectorvl*) malloc(sizeof(zeta_vector))); vermem(*zetavl=(zeta_vectorvl) malloc((2*tamanyo)*sizeof(casillavl))); num_de_alphas_nulas=iniciar_zetasvl(zvl, z_cas, *tr, tamanyo, tamanyo-1); lema_dos_unovl(zvl, z_cas, zetavl, *tr, tamanyo, tamanyo-1, num_de_alphas_nulas, salida); se_puede_despejar=1; while (!zetas_igualesvl(zetavl, tamanyo-1) && se_puede_despejar) { verifica(fprintf(salida, "\nHay que hacer" " substituciones.\n")); se_puede_despejar= despejar_una_variablevl_en_lista(zvl, z_cas, zetavl, *tr, tamanyo, tamanyo-1, num_de_alphas_nulas, salida, salida_log, salida_log2); }; if (se_puede_despejar) { verifica(fprintf(salida, "\n!‘Hecho!\n\n")); }; verifica(fprintf(salida, "\n\\’Estos son los valores" " de las alphas nulas y las $z_i$:\n" "\\begin{eqnarray*}\n")); for (i=0; i<num_de_alphas_nulas; i++) { verifica(fprintf(salida, "\\alpha_{%d,%d} &=&", (*z_cas)[i][0], (*z_cas)[i][1])); escribe_casillavl_archivo_TeX(*(*zvl+i), "z", salida); if (i<num_de_alphas_nulas-1) { verifica(fprintf(salida, "\\\\")); } verifica(fprintf(salida, "\n")); }; verifica(fprintf(salida, "\\end{eqnarray*}\n\\begin{eqnarray*}\n")); for (i=0; i<(2*tamanyo); i++) { verifica(fprintf(salida, "z_{%d}&=&", i+1)); escribe_casillavl_archivo_TeX(*(*zetavl+i), "z", salida); if (i<(2*tamanyo)-1) { verifica(fprintf(salida, "\\\\")); }; verifica(fprintf(salida, "\n")); }; 292 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS verifica(fprintf(salida, "\\end{eqnarray*}\n\\clearpage\n\n")); free(*z_cas); free(*zetavl); free(zetavl); free(*zvl); free(zvl); fflush(salida); fflush(salida_log); fflush(salida_log2); return (CONTADOR); } int main_esp(int argc, char **argv) { int se_puede_despejar; zeta_vector *z, *zeta; indice_de_casilla **z_cas; triang *tr; int tamanyo, num_de_alphas_nulas, i, num_de_ceros; FILE *entrada, *salida, *salida_log, *salida_log2; char *nombre_salida, *nombre_salida_log, *nombre_salida_log2; if ((entrada=fopen(argv[1], "rt"))==NULL) { perror("Error en archivo de entrada"); } else { if (fscanf(entrada, "%d ", &tamanyo)<=0) { perror("Error de lectura en archivo de entrada"); exit(1); }; }; vermem(nombre_salida=(char *) malloc(sizeof(char)*(strlen(argv[1])+5))); strcpy(nombre_salida, argv[1]); strcat(nombre_salida, "z.tex"); if ((salida=fopen(nombre_salida, "wt"))==NULL) { perror("Error en archivo de salida"); exit(1); }; vermem(nombre_salida_log=(char *) malloc(sizeof(char)*(strlen(argv[1])+6))); strcpy(nombre_salida_log, argv[1]); strcat(nombre_salida_log, ".zlog"); if ((salida_log=fopen(nombre_salida_log, "wt"))==NULL) { perror("Error en archivo de salida"); exit(1); }; vermem(nombre_salida_log2=(char *) malloc(sizeof(char)*(strlen(argv[1])+7))); strcpy(nombre_salida_log2, argv[1]); strcat(nombre_salida_log2, ".zlog2"); if ((salida_log2=fopen(nombre_salida_log2, "wt"))==NULL) { perror("Error en archivo de salida"); A.1. CEROS Y NO CEROS 293 exit(1); }; vermem(tr=(triang *) malloc(sizeof(triang))); vermem(z=(zeta_vector *) malloc(sizeof(zeta_vector))); vermem(z_cas=(indice_de_casilla**) malloc(sizeof(indice_de_casilla*))); vermem(zeta=(zeta_vector *) malloc((2*tamanyo)*sizeof(zeta_vector))); vermem(*zeta=(zeta_vector) malloc((2*tamanyo)*sizeof(casilla))); CONTADOR=0; LONG_FILA_TeX=9; while (!feof(entrada)) { lee_triangulo(tr, tamanyo, entrada); OVERFLOW=0; CONTADOR++; fprintf(stderr, "CONTADOR=%ld\n", CONTADOR); escribe_bullets_uno(*tr, tamanyo, salida); verifica(fprintf(salida, "\n\n")); num_de_ceros=numero_de_ceros(*tr,tamanyo); vermem(*z=(zeta_vector) malloc((num_de_ceros+(*tr)[0][0].longitud)*sizeof(casilla))); num_de_alphas_nulas=iniciar_zetas(z, z_cas, *tr, tamanyo, tamanyo-1); lema_dos_uno(z, z_cas, zeta, *tr, tamanyo, tamanyo-1, num_de_alphas_nulas, salida); se_puede_despejar=1; while (!zetas_iguales(zeta, tamanyo-1) && se_puede_despejar) { verifica(fprintf(salida, "\nHay que hacer" " substituciones.\n")); se_puede_despejar= despejar_una_variable_en_lista(z, z_cas, zeta, *tr, tamanyo, tamanyo-1, num_de_alphas_nulas, salida, salida_log, salida_log2); }; if (se_puede_despejar) { verifica(fprintf(salida, "\n!‘Hecho!\n\n")); }; verifica(fprintf(salida, "\n\\’Estos son los valores" " de las alphas nulas y las $z_i$:\n" "\\begin{eqnarray*}\n")); for (i=0; i<num_de_alphas_nulas; i++) { verifica(fprintf(salida, "\\alpha_{%d,%d} &=&", (*z_cas)[i][0], (*z_cas)[i][1])); escribe_casilla_archivo_TeX(*(*z+i), "z", salida); if (i<num_de_alphas_nulas-1) { verifica(fprintf(salida, "\\\\")); } verifica(fprintf(salida, "\n")); 294 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS }; verifica(fprintf(salida, "\\end{eqnarray*}\n\\begin{eqnarray*}\n")); for (i=0; i<(2*tamanyo); i++) { verifica(fprintf(salida, "z_{%d}&=&", i+1)); escribe_casilla_archivo_TeX(*(*zeta+i), "z", salida); if (i<(2*tamanyo)-1) { verifica(fprintf(salida, "\\\\")); }; verifica(fprintf(salida, "\n")); }; verifica(fprintf(salida, "\\end{eqnarray*}\n\\clearpage\n\n")); free(*z_cas); free(*z); fflush(salida); fflush(salida_log); fflush(salida_log2); }; free(*zeta); fclose(entrada); fclose(salida); fclose(salida_log); fclose(salida_log2); free(nombre_salida); free(nombre_salida_log); free(nombre_salida_log2); free(tr); free(z); free(z_cas); free(zeta); return(CONTADOR); } A.1.18. El archivo outputvl.c #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/stat.h> #include "bullet.h" #include "bulletvl.h" extern long int CONTADOR; /* void verifica(int valor) { if (valor<0) { perror("Error de escritura"); exit(1); }; } A.1. CEROS Y NO CEROS 295 void lee_triangulo(triang *tr, int fila, FILE *archivo) { int i,j, longitud; longitud=(fila+1)/2; for (i=fila-1;i>=0;i--) { for (j=0;j<=(i/2);j++) { lee_casilla(&((*tr)[i][j]), longitud, archivo); }; }; } */ /*void lee_casillavl(casillavl *cas, int longitud, FILE *archivo) { int j; cas->longitud=longitud; for (j=0; j<longitud; j++) { if (!fscanf(archivo,"(%ld/%ld)", &(cas->coef[j].num), &(cas->coef[j].den))) { printf ("Error %c\n", ’\007’); }; }; fscanf(archivo," "); } */ void escribe_fraccionvl_archivo(FILE *archivo, fraccionvl fr) { verifica(fprintf(archivo, "(")); escribevl_archivo(archivo, fr.num); verifica(fprintf(archivo, "/")); escribevl_archivo(archivo, fr.den); verifica(fprintf(archivo, ")")); }; void escribe_casillavl_archivo(casillavl cas, int longitud, FILE *archivo) { int j; cas.longitud=longitud; for (j=0; j<longitud; j++) { escribe_fraccionvl_archivo(archivo,cas.coef[j]); }; verifica(fprintf(archivo," ")); } /*void escribe_triangulo_archivo(triang tr, int fila, FILE *archivo) { int i,j, longitud; longitud=(fila+1)/2; 296 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS for (i=fila-1;i>=0;i--) { for (j=0;j<=(i/2);j++) { escribe_casilla_archivo(tr[i][j], longitud, archivo); }; verifica(fprintf(archivo,"\n")); }; verifica(fprintf(archivo,"\n")); } */ void escribe_casillavl_archivo_TeX(casillavl cas, char *nom_var, FILE *archivo) { int j; int salio_primer_elemento; if (es_cero_casillavl(cas)) { verifica(fprintf(archivo, "0")); } else { salio_primer_elemento=0; for (j=0; j<cas.longitud; j++) { if (!es_cerovl(cas.coef[j].num)) { if (!es_igualvl(cas.coef[j].den,longint2vl(1))) { if (!es_igualvl(cas.coef[j].num,longint2vl(0)) && !cas.coef[j].num.sgn) { if (!salio_primer_elemento) { escribe_fraccionvl_archivo(archivo, cas.coef[j]); verifica(fprintf(archivo,"%s_{%d}", nom_var, j+1)); salio_primer_elemento=1; } else /* ya salio primer elemento */ { verifica(fprintf(archivo, "+")); escribe_fraccionvl_archivo(archivo, cas.coef[j]); verifica(fprintf(archivo, "%s_{%d}", nom_var, j+1)); }; } else /* cas.coef[j]<0 */ { verifica(fprintf(archivo, "-")); escribe_fraccionvl_archivo(archivo, menosfrvl(cas.coef[j])); A.1. CEROS Y NO CEROS 297 verifica(fprintf(archivo,"%s_{%d}", nom_var, j+1)); salio_primer_elemento=1; } } else /* cas.coef[j].den=1, esto es, es entero */ { if (!es_igualvl(cas.coef[j].num,longint2vl(0))&& !cas.coef[j].num.sgn) { if (!salio_primer_elemento) { if (!es_igualvl(cas.coef[j].num,longint2vl(1))) { escribevl_archivo(archivo, cas.coef[j].num); verifica(fprintf(archivo, "%s_{%d}", nom_var, j+1)); salio_primer_elemento=1; } else /* cas.coef[j].num=1 */ { verifica(fprintf(archivo, "%s_{%d}", nom_var, j+1)); salio_primer_elemento=1; }; } else /* salio_primer_elemento */ { if (!es_igualvl(cas.coef[j].num,longint2vl(1))) { verifica(fprintf(archivo, "+")); escribevl_archivo(archivo, cas.coef[j].num); verifica(fprintf(archivo, "%s_{%d}", nom_var, j+1)); } else /* cas.coef[j].num==1 */ { verifica(fprintf(archivo, "+%s_{%d}", nom_var, j+1)); salio_primer_elemento=1; } } } else /* cas.coef[j].num<0 */ { if (!es_igualvl(cas.coef[j].num, menosvl(longint2vl(1)))) { escribevl_archivo(archivo, cas.coef[j].num); verifica(fprintf(archivo, "%s_{%d}", nom_var, j+1)); } else /* cas.coef[j].num==-1 */ { verifica(fprintf(archivo, "-%s_{%d}", nom_var, j+1)); 304 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS void escribe_casillavl_archivo_TeX_l(casillavl cas, char *nom_var, FILE *archivo); void escribe_jacobi(gran_jacobi jac); int aplica_tecnica_2(gran_jacobi *jac, int n); /* En la siguiente funcion se define la version vl de los numeros */ /* combinatorios.*/ /***********************************************************************/ verylong choosevl(unsigned long int x1, unsigned long int x2) /***********************************************************************/ /* En esta funcion se define la version verylong de los numeros */ /* combinatorios. */ /***********************************************************************/ { unsigned long int i; verylong res, num; STACK_OVERFLOW++; if (STACK_OVERFLOW > MAX_STACK_OVERFLOW) { fprintf(stderr,"Desbordamiento de pila en funci\363n choose.\n"); exit(1); }; if (x2>x1) { STACK_OVERFLOW--; return (longint2vl(0)); } else { if (2*x2>x1) { STACK_OVERFLOW--; return(choosevl(x1,x1-x2)); } else { res=longint2vl(1); for (i=0;i<x2;i++) { num=prodvl(res,longint2vl(x1-i)); res=divvl(num,longint2vl(i+1)); }; STACK_OVERFLOW--; return(res); }; }; } /* La siguiente funcion calcula $\alpha_{i,j}$ en funci\’on de las */ /* $x_i$. */ /***********************************************************************/ casillavl alpha(int i, int j) /***********************************************************************/ A.1. CEROS Y NO CEROS 305 /* Esta funcion devuelve $\alpha_{i,j}$ en funcion de los $x_k$. */ /***********************************************************************/ { casillavl res, sumando, res1; int k; fraccionvl fr; if (i>j) { return(menos_casvl(alpha(j,i))); }; res.longitud=C_0_MAX; for (k=0; k<C_0_MAX; k++) { res.coef[k].num=longint2vl(0); res.coef[k].den=longint2vl(1); }; for (k=(i+j-1)/2; k>=l && k>=i; k--) { fr.num=(k-i)%2 ? menosvl(choosevl(j-1-k, k-i)): choosevl(j-1-k, k-i); fr.den=longint2vl(1); sumando=prodescvl(fr, *(equis+(k-l))); res1=sum_casvl(res, sumando); res=res1; }; return(res); } /***********************************************************************/ void aplica_jacobi(gran_jacobi *jac) /***********************************************************************/ /* Esta funcion trata de aplicar Jacobi hasta llegar una contradiccion */ /* del tipo x_l=0. */ /***********************************************************************/ { int n, a, b, j; verylong p; int contradiccion, se_ha_despejado, hay_que_repetir; casillavl forma; contradiccion=0; n=5; /* minimo valor del nivel menos uno */ while (!contradiccion) { n++; /* incrementamos el nivel */ se_ha_despejado=1; hay_que_repetir=0; fprintf(salida_TeX, "\n\nNivel %d\n\n", n); for (a=(n/3)-1; a>0 && !contradiccion; a--) { 306 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS for (b=(n-a-1)/2; b>a && !contradiccion; b--) { jacobi(a,b,n-a-b, jac); printf("Jacobi (%d, %d, %d):\n", a, b, n-a-b); escribe_jacobi(*jac); /* Aqui aplicamos una hipotesis muy fuerte, que es que */ /* el factor $x_l$ o el factor $x_{l+1}$ se obtiene en */ /* los Jacobi no nulos que vayan apareciendo.*/ if (!es_cero_jacobi(*jac)) { if (factorizable_l(*jac)) { /* Se factoriza x_l */ forma=entre_x_l(*jac); fprintf(salida_TeX, "\nConsideremos " "Jacobi: " "$f(%d, %d, %d)=x_{%d}\\bigl(", a, b, n-a-b, l); escribe_casillavl_archivo_TeX_l(forma, "x", salida_TeX); fprintf(salida_TeX, "\\bigr)$.\n\n"); contradiccion=substituir_formas(forma); /* El primo... */ if (!contradiccion) { p=menor_mayor_primo_casillavl(forma); } else { p=mayor_primovl(forma.coef[0].num, MAXPR); }; fprintf(salida_TeX, "\nLa substituci\\’on" " es v\\’alida para $p>"); escribevl_archivo(salida_TeX, p); fprintf(salida_TeX, "$.\n"); if (!se_ha_despejado) { hay_que_repetir=1; }; } else { if (factorizable_l_1(*jac)) { /* Entonces se factoriza por x_{l+1} */ forma=entre_x_l_1(*jac); /* Hipotesis adicional: se llega mas alla */ /* suponiendo que x_{l+1}\ne 0 que si */ /* x_{l+1}=0. */ fprintf(salida_TeX, "\nConsideremos" " Jacobi:" " $f(%d, %d, %d)=x_{%d}\\bigl(", a, b, n-a-b, l+1); escribe_casillavl_archivo_TeX_l(forma, "x", A.1. CEROS Y NO CEROS 307 salida_TeX); fprintf(salida_TeX, "\\bigr)$.\n\n"); contradiccion=substituir_formas(forma); /* El primo... */ if (!contradiccion) { p=menor_mayor_primo_casillavl(forma); } else { p=mayor_primovl(forma.coef[0].num, MAXPR); }; fprintf(salida_TeX, "\nLa substituci\\’on" " es v\\’alida para $p>"); escribevl_archivo(salida_TeX, p); fprintf(salida_TeX, "$.\n"); if (!se_ha_despejado) { hay_que_repetir=1; }; } else { se_ha_despejado=0; } }; }; }; }; /* Escribimos los valores validos para el algebra de Lie */ fprintf(salida_TeX, "\\begin{eqnarray*}\n"); for (j=0; j<C_0_MAX; j++) { fprintf(salida_TeX, "x_{%d}&=&", j+l); escribe_casillavl_archivo_TeX_l(*(equis+j), "x", salida_TeX); if (j<C_0_MAX-1) { fprintf(salida_TeX, "\\\\\n"); }; }; fprintf(salida_TeX, "\n\\end{eqnarray*}\n\n"); fflush(salida_TeX); if (!se_ha_despejado) { contradiccion=aplica_tecnica_2(jac, n); hay_que_repetir=1; }; if (hay_que_repetir) { n--; }; }; fprintf(salida_TeX, "\n\nNotemos que, en virtud de la" " periodicidad mod $p-1$, que $p>%d$.\n\n", 2*(c0+l)+3); } 308 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS /***********************************************************************/ void inicia_equis() /***********************************************************************/ /* En esta funcion se inicializan los valores de las $x_i$ con objeto */ /* de que puedan ser substituidas por otros valores a lo largo del */ /* algoritmo. */ /***********************************************************************/ { int i, j; vermem(equis=malloc(C_0_MAX*sizeof(casillavl))); for (i=0; i<C_0_MAX; i++) { (equis+i)->longitud=C_0_MAX; for (j=0; j<C_0_MAX; j++) { (equis+i)->coef[j].num=longint2vl(i==j); (equis+i)->coef[j].den=longint2vl(1); }; }; } /***********************************************************************/ int main(int argc, char *argv[]) /***********************************************************************/ /* Funcion principal del programa. */ /***********************************************************************/ { /* verylong p; casillavl cas;*/ gran_jacobi *jac; int kkk; char *nombre_salida_TeX; if (argc<3) { l=4; c0=6; printf("Asignados los valores por defecto c0=6, l=4.\n"); }; l=atoi(argv[2]); c0=atoi(argv[1]); /* if (l<=((1+c0)/2)) { fprintf(stderr, "l ha de ser mayor que (c0+1)/2\n"); exit(1); }; */ printf("Asignados los valores $c_0=%d$, $l=%d$.\n", c0, l); inicia_equis(); vermem(jac=malloc(sizeof(gran_jacobi))); vermem((*jac)=malloc(C_0_MAX*sizeof(fraccionvl*))); vermem(nombre_salida_TeX=malloc(12+(l>9?1:0)+(c0>9?1:0))); for (kkk=0; kkk<C_0_MAX; kkk++) { vermem(*(*jac+kkk)= malloc((kkk+1)*sizeof(fraccionvl))); A.1. CEROS Y NO CEROS 309 }; sprintf(nombre_salida_TeX, "c_0=%d-l=%d.tex", c0, l); if ((salida_TeX=fopen(nombre_salida_TeX, "wt"))==NULL) { perror("Error en archivo de salida TeX"); exit(1); }; fprintf(salida_TeX, "Asignados los valores $l=%d$, $c_0=%d$.\n", l, c0); aplica_jacobi(jac); fclose(salida_TeX); return(0); } /***********************************************************************/ verylong menor_mayor_primo_casillavl(casillavl cas) /***********************************************************************/ /* Esta funcion devuelve el menor maximo primo presente en una */ /* casillavl. */ /***********************************************************************/ { despejevl des; des=despejar_final_variablevl(cas); return(mayor_primovl(des.cas.coef[des.pos].num, MAXPR)); } /***********************************************************************/ int factorizable_l(gran_jacobi jac) /***********************************************************************/ /* Devuelve $1$ si $x_l$ es un factor comun de la expresion de Jacobi. */ /* Devuelve $0$ en otro caso. */ /***********************************************************************/ { int res, i, j; res=1; for (i=0; i<C_0_MAX && res; i++) { for (j=1; j<=i && res; j++) { res=es_cerovl((*(*(jac+i)+j)).num); }; }; return(res); } /***********************************************************************/ int factorizable_l_1(gran_jacobi jac) /***********************************************************************/ /* Devuelve $1$ si $x_{l+1}$ es un factor comun de la expresion de */ /* Jacobi. En otro caso, devuelve $0$. */ /***********************************************************************/ { int res, i, j; 310 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS res=1; for (i=0; i<C_0_MAX && res; i++) { for (j=0; j<=i && res; j++) { if (j!=1) { if (i!=1) { res=es_cerovl((*(*(jac+i)+j)).num); }; }; }; }; return(res); } /***********************************************************************/ casillavl entre_x_l(gran_jacobi jac) /***********************************************************************/ /* Divide la forma cuadratica del argumento entre $x_{l}$. */ /***********************************************************************/ { casillavl res; int i; res.longitud=C_0_MAX; for (i=0; i<C_0_MAX; i++) { res.coef[i]=*(*(jac+i)); }; return(res); } /***********************************************************************/ casillavl entre_x_l_1(gran_jacobi jac) /***********************************************************************/ /* Divide la forma cuadratica del argumento entre $x_{l+1}$. */ /***********************************************************************/ { casillavl res; int i; res.longitud=C_0_MAX; for (i=1; i<C_0_MAX; i++) { res.coef[i]=*(*(jac+i)+1); }; res.coef[0]=*(*(jac+1)); return(res); } /***********************************************************************/ int substituir_formas(casillavl cas) /***********************************************************************/ A.1. CEROS Y NO CEROS 311 /* Despeja una variable de la forma lineal de su argumento y la */ /* substituye en el vector de las $x_k$ hasta que se anula la */ /* variable $x_l$, caso en que devuelve $1$, o se substituyen todas, */ /* caso en que devuelve $0$. */ /***********************************************************************/ { int i; despejevl des; int escero; casillavl temp; escero=1; for (i=1; i<C_0_MAX && escero; i++) { escero=es_cerovl(cas.coef[i].num); }; if (escero) { return (1); }; des=despejar_una_variablevl_al_final(cas); temp=substituirvl(*equis, des); fprintf(salida_TeX, "\n\nRealizamos una substituci\\’on," " a partir de $x_{%d}$,\n$$", des.pos+l); escribe_casillavl_archivo_TeX_l(des.cas, "x", salida_TeX); fprintf(salida_TeX, "=0$$\n\n"); *equis=temp; if (es_cero_casillavl(*equis)) { return(1); } else { for (i=1; i<C_0_MAX; i++) { temp=substituirvl(*(equis+i), des); *(equis+i)=temp; }; return(0); }; } /***********************************************************************/ int es_cero_jacobi(gran_jacobi jac) /***********************************************************************/ /* Devuelve $1$ si su argumento es una forma cuadratica nula, o $0$ en */ /* caso contrario. */ /***********************************************************************/ { int res, i, j; res=1; for (i=0; i<C_0_MAX && res; i++) { for (j=0; j<=i && res; j++) { 312 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS res=es_cerovl((*(*(jac+i)+j)).num); }; }; return(res); } /***********************************************************************/ void jacobi(int i, int j, int k, gran_jacobi *res) /***********************************************************************/ /* Calcula la forma cuadratica de Jacobi $f(i,j,k)$. */ /***********************************************************************/ { int i1, j1; casillavl aij, bij, ajk, bjk, aki, bki; fraccionvl f1, f2, f3, f4; aij=alpha(i,j); bij=alpha(i+j+c0,k); ajk=alpha(j,k); bjk=alpha(j+k+c0, i); aki=alpha(k,i); bki=alpha(k+i+c0, j); for (i1=0; i1<C_0_MAX; i1++) { for (j1=0; j1<i1; j1++) { f1=sumfrvl(prodfrvl(aij.coef[i1], bij.coef[j1]), prodfrvl(bij.coef[i1], aij.coef[j1])); f2=sumfrvl(prodfrvl(ajk.coef[i1], bjk.coef[j1]), prodfrvl(bjk.coef[i1], ajk.coef[j1])); f3=sumfrvl(prodfrvl(aki.coef[i1], bki.coef[j1]), prodfrvl(bki.coef[i1], aki.coef[j1])); f4=sumfrvl(f1,f2); *(*((*res)+i1)+j1)=sumfrvl(f4,f3); }; f1=prodfrvl(aij.coef[i1], bij.coef[i1]); f2=prodfrvl(ajk.coef[i1], bjk.coef[i1]); f3=prodfrvl(aki.coef[i1], bki.coef[i1]); f4=sumfrvl(f1,f2); *(*((*res)+i1)+i1)=sumfrvl(f4,f3); }; } /***********************************************************************/ despejevl despejar_final_variablevl(casillavl c) /***********************************************************************/ /* Despeja una variable de la forma lineal c. El criterio seguido es */ /* el de considerar la variable con el menor mayor primo lo mas a la */ /* derecha posible. */ /***********************************************************************/ { despejevl res; int i,j, i1; verylong mp, mpc; A.1. CEROS Y NO CEROS 313 /* escribe_casillavl(c);*/ j=1; while (es_cerovl(c.coef[j].num)) { j++; }; i1=j; for(i=i1;i<c.longitud; i++) { if (!es_cerovl(c.coef[i].num)) { if (es_mayorvl(absvl(c.coef[i1].num), absvl(c.coef[i].num))) { i1=i; }; }; }; mp=mayor_primovl(c.coef[j].num, MAXPR); res.pos=j; for (i=0; i<c.longitud; i++) { res.cas.coef[i].num=prodvl(c.coef[i].num,longint2vl(1)); res.cas.coef[i].den=prodvl(c.coef[i].den,longint2vl(1)); }; res.cas.longitud=c.longitud; j=0; while (es_cerovl(c.coef[j].num)) { j++; }; for (i=j+1;i<c.longitud; i++) { if (!es_cerovl(c.coef[i].num)) { mpc=mayor_primovl(c.coef[i].num, (!es_mayorvl(mp,longint2vl(0)) ? mp : MAXPR)); if (es_mayorvl(mp,mpc)) { mp=mpc; res.pos=i; }; }; }; return (res); } /***********************************************************************/ despejevl despejar_una_variablevl_al_final(casillavl c) /***********************************************************************/ /* Despeja una variable de la forma lineal c. El criterio seguido es */ /* el de considerar la variable con el menor mayor primo lo mas a la */ /* derecha posible. */ /***********************************************************************/ { 320 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS for (i=0; i<C_0_MAX; i++) { if ((*(*(a+i)+i))%p) { especial=i; i=p; }; }; if (especial!=-1) { inv=invmodp(*(*(a+especial)+especial), p); for (i=0; i<C_0_MAX; i++) { for (j=0; j<=i; j++) { *(*(d+i)+j)=(((inv*(*(*(a+i)+j)))%p)+p)%p; }; }; #ifdef DRAFT printf("\nd=\n"); escribe_jacobi_modp(d); #endif b->coef[especial]=1; c->coef[especial]=1; for (i=0;i<C_0_MAX;i++) { if (i!=especial) { miembro=0; for (j=0; j<=i; j++) { if (*(*(a+i)+j)%p) { miembro=1; j=p; }; }; if (miembro==0) { for (j=i+1;j<C_0_MAX;j++) { if (*(*(a+j)+i)%p) { miembro=1; j=p; }; }; }; if (miembro==1) { if (i>especial) { solve2(*(*(a+especial)+especial), *(*(a+i)+especial), *(*(a+i)+i), p, una_solucion); } else A.2. ALGORITMO DE CÁLCULO DE COTAS 321 { solve2(*(*(a+especial)+especial), *(*(a+especial)+i), *(*(a+i)+i), p, una_solucion); }; if (!una_solucion->haysolucion) { for (k=0; k<C_0_MAX;k++) { free(*(d+k)); }; free(d); free(una_solucion); return 0; }; b->coef[i]=(p-una_solucion->sol1)%p; c->coef[i]=(p-una_solucion->sol2)%p; #ifdef DRAFT printf("[%ld,%ld]",b->coef[i],c->coef[i]); printf("\nd=\n"); escribe_jacobi_modp(d); #endif exito=1; for (j=0; j<i; j++) { t=*(*(d+i)+j) - (b->coef[i] * c->coef[j]+ c->coef[i] * b->coef[j]); t=((t%p)+p)%p; if (t) { exito=0; j=p; }; }; if (!exito) { b->coef[i]=(p-una_solucion->sol2)%p; c->coef[i]=(p-una_solucion->sol1)%p; #ifdef DRAFT printf("(cambiado)[%ld,%ld]",b->coef[i],c->coef[i]); printf("\nd=\n"); escribe_jacobi_modp(d); #endif for (j=0;j<i;j++) { t=*(*(d+i)+j)-(b->coef[i] * c->coef[j] + c->coef[i] * b->coef[j]); t%=p; if (t) { #ifdef DRAFT printf("\n\n"); #endif for (k=0; k<C_0_MAX;k++) { free(*(d+k)); }; 322 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS free(d); free(una_solucion); return 0; }; }; }; }; }; } } else { for (i=0; i<C_0_MAX; i++) { for (j=0; j<i; j++) { if ((*(*(a+i)+j))%p) { inv=invmodp(*(*(a+i)+j),p); for (k=j;k<=i;k++) { b->coef[k]=*(*(a+k)+j)*inv; b->coef[k]=(((b->coef[k])%p)+p)%p; }; for (k=0; k<j; k++) { c->coef[k]=*(*(a+i)+k)%p; b->coef[k]=(*(*(a+j)+k)*inv)%p; }; j=p; i=p; }; }; }; for (i=0; i<C_0_MAX; i++) { for (j=0; j<i; j++) { t=*(*(a+i)+j)-(b->coef[i] * c->coef[j] + c->coef[i] * b->coef[j]); t=((t%p)+p)%p; if (!t) { for (k=0; k<C_0_MAX;k++) { free(*(d+k)); }; free(d); free(una_solucion); return 0; }; }; }; }; for (k=0; k<C_0_MAX;k++) { A.2. ALGORITMO DE CÁLCULO DE COTAS 323 free(*(d+k)); }; free(d); free(una_solucion); return 1; } A.2.2. El archivo pjacobi.c /*********************************************************************/ /* Archivo pjacobi.c, con la funcion main() del programa pjacobi. */ /*********************************************************************/ #include <stdio.h> #include <stdlib.h> #include "pjacobi.h" void prueba(); gran_jacobi_modp jaco; /*********************************************************************/ int main(int argc, char*argv[]) /*********************************************************************/ /* Funcion main() que no hace mas que llamar a main_function(). */ /*********************************************************************/ { /* prueba(argc,argv);*/ /* return 0;*/ return main_function(argc,argv); } A.2.3. El archivo power.c /*********************************************************************/ /*********************************************************************/ /** Archivo power.c **/ /** Contiene la definicion de una funcion para calcular potencias **/ /** modulo p. **/ /*********************************************************************/ /*********************************************************************/ #include <stdio.h> #include <stdlib.h> #include "pjacobi.h" /*********************************************************************/ long int power(long int base, long int exponente, long int modulo) /*********************************************************************/ /* Esta funcion calcula la potencia base^exponente y reduce el */ /* resultado al modulo dado. Ha sido extraida del libro de Peter */ 324 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS /* Giblin, "Primes and Programming". */ /*********************************************************************/ { long int d, res, pow,bas; res=1; pow=exponente; bas=base; while (pow > 0) { d=pow-2*(pow/2); if (d==1) { res*=bas; res=((res%modulo)+modulo)%modulo; }; bas=bas*bas; bas=((bas%modulo)+modulo)%modulo; pow=(pow-d)/2; } return res; } /* int main() { long int a, n, m, r; printf("Escribe los valores de a, n, m, separados por espacios.\n"); scanf("%ld %ld %ld",&a, &n, &m); r=power(a,n,m); printf("El valor de (%ld)^(%ld) mod %ld es %ld.\n", a,n,m,r); return 0; } */ A.2.4. El archivo legendre.c /*********************************************************************/ /* Archivo legendre.c */ /* En este archivo se definen funciones para el calculo de simbolos */ /* de Legendre/Jacobi */ /*********************************************************************/ #include <stdio.h> #include <stdlib.h> #include "pjacobi.h" /*********************************************************************/ void WriteRatio(long int n, long int k, int sign) /*********************************************************************/ A.2. ALGORITMO DE CÁLCULO DE COTAS 325 /* Esta funcion escribe en pantalla de una manera simplificada los */ /* simbolos de Legendre/Jacobi que aparecen en el calculo. Solo se */ /* usa cuando esta definido DRAFTSHANKS. */ /*********************************************************************/ { if (sign==-1) { printf("-[ %ld / %ld ]\n",n,k); } else { printf("+[ %ld / %ld ]\n",n,k); } } /*WriteRatio*/ /*********************************************************************/ int legendre(long int ene, long int ka) /*********************************************************************/ /* Esta funcion devuelve el simbolo de Legendre/Jacobi ${n\brack */ /* k}$. La idea del algoritmo es del texto de Giblin. */ /*********************************************************************/ { long int n,k,count,x, y, xtempk; int sign; n=ene; k=ka; sign=1; while (n>1) { n%=k; #ifdef DRAFTSHANKS WriteRatio(n,k,sign); #endif count=0; while (!(n%2)) /* o sea, cuando n es par */ { n/=2; count++; }; if (count%2) /* o sea, count es impar */ { x=k%8; if ((x==3)||(x==5)) { sign*=-1; /* propiedades del simbolo $2\brack p$ */ }; }; #ifdef DRAFTSHANKS if (count > 0) { WriteRatio(n,k,sign); 326 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS }; #endif if (n>1) { xtempk=k; k=n; n=xtempk; /* Hemos intercambiado n y k */ x=k%4; y=n%4; if (x==3) { if (y==3) { sign*=-1; } }; #ifdef DRAFTSHANKS WriteRatio(n,k,sign); #endif }; } return sign; } A.2.5. El archivo shanks.c /* Archivo shanks.c */ /* Contiene el algoritmo de Shanks en la version descrita en el texto */ /* de Giblin para calcular las raices cuadradas en el cuerpo de $p$ */ /* elementos.*/ #include <stdio.h> #include <stdlib.h> #include "pjacobi.h" /* La funcion shanks_sqrt_intermedio determina la raiz cuadrada de a */ /* dado el valor inicial z del algoritmo de Shanks.*/ /*********************************************************************/ long int shanks_sqrt_intermedio(long int a,long int p,long int z) /*********************************************************************/ /* La funcion shanks_sqrt_intermedio determina la raiz cuadrada de a */ /* dado el valor inicial z del algoritmo de Shanks. */ /*********************************************************************/ { long int b, c, p1, n, odd, k1, x, y, looplength, i, index, s; p1=p-1; index=0; while(!(p1%2)) /* p1 par */ { A.2. ALGORITMO DE CÁLCULO DE COTAS 327 p1/=2; index++; }; s=index; odd=p1; /* El numero 2k+1 del texto */ c=power(z,odd,p); n=power(a,odd,p); #ifdef DRAFTSHANKS printf("n=%ld\n",n); #endif k1=(odd+1)/2; /* k+1 */ x=power(a,k1,p); #ifdef DRAFTSHANKS printf("x=%ld\n",x); #endif while (n>1) { looplength=s; y=n; /* y sera la variable que se eleva al cuadrado */ for (i=1;i<=looplength;i++) { if (y==1) { y=c; s=i-1; } else { y=y*y; y=((y%p)+p)%p; }; }; b=y; c=b*b; c=((c%p)+p)%p; x=b*x; x=((x%p)+p)%p; #ifdef DRAFTSHANKS printf("x=%ld\n", x); #endif n*=c; n=((n%p)+p)%p; #ifdef DRAFTSHANKS printf("n=%ld\n", n); #endif }; return x; } /*********************************************************************/ long int shanks_inicial(long int p) /*********************************************************************/ /* Obtiene un valor inicial para el algoritmo de Shanks, esto es, un */ /* no residuo cuadratico. */ /*********************************************************************/ { 328 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS long int z; for (z=2;;z++) { if (legendre(z,p)==-1) break; }; return z; } /*********************************************************************/ long int shanks_sqrt(long int a, long int p) /*********************************************************************/ /* Algoritmo de Shanks para el calculo de la raiz cuadrada mod p */ /*********************************************************************/ { long int z, res; if (a%p==0) { return 0; } else { z=shanks_inicial(p); res=shanks_sqrt_intermedio(a,p,z); return res; }; } A.2.6. El archivo modular.c /* Archivo modular.c, que tiene definidas funciones para trabajar mod */ /* p. Las funciones para invertir mod p han sido hurtadas de Peter */ /* Giblin, "Primes and Programming", Cambridge, pag. 21. */ #include <stdio.h> #include <stdlib.h> #include "pjacobi.h" /***********************************************************************/ long int choose_modp(unsigned long int x1, unsigned long int x2) /***********************************************************************/ /* Esta funcion calcula el numero combinatorio ${x1\choose x2}$ mod p. */ /***********************************************************************/ { unsigned long int i; long int res, num; STACK_OVERFLOW++; if (STACK_OVERFLOW > MAX_STACK_OVERFLOW) { fprintf(stderr,"Desbordamiento de pila en funci\363n choose_modp.\n"); exit(1); }; if (x2>x1) A.2. ALGORITMO DE CÁLCULO DE COTAS 329 { STACK_OVERFLOW--; return ((unsigned long) 0); } else { if (2*x2>x1) { res=choose_modp(x1,x1-x2); STACK_OVERFLOW--; return res; } else { res=(unsigned long int) 1; for (i=0;i<x2;i++) { num=(((res*(x1-i)) % primo)+primo)%primo; res=(((num*invmodp(i+1, primo)) % primo)+primo)%primo; }; STACK_OVERFLOW--; return(res); }; }; } /***********************************************************************/ EUCLIDES eucgcd(long int a0, long int b0) /***********************************************************************/ /* Esta funcion calcula el maximo comun divisor de dos numeros */ /* enteros, a0 y b0, asi como los coeficientes que aparecen en la */ /* relacion de Bezout. Estos tres datos aparecen reflejados en el */ /* tipo EUCLIDES. El algoritmo empleado es el de Euclides, en la */ /* version descrita en lenguaje PASCAL por Peter Gibling, "Primes and */ /* Programming", Cambridge, en la pagina 21. */ /***********************************************************************/ { EUCLIDES res; long int a, b, q, r, s, s1, s2, t, t1, t2; a=a0; b=b0; s2=1; s1=0; t2=0; t1=1; while (b>0) { q=a/b; r=a-b*q; s=s2-q*s1; t=t2-q*t1; /* Tenemos que a0*s+b0*t=r */ a=b; b=r; s2=s1; 336 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS { res=((*(*(jac+i)+j))==0); }; }; return(res); } /***********************************************************************/ casillamodp entre_x_l_modp(gran_jacobi_modp jac) /***********************************************************************/ /* Trata de dividir el Jacobi entre $x_l$, supuesto que $x_l$ es */ /* factor comun. */ /***********************************************************************/ { casillamodp res; int i; res.longitud=C_0_MAX; for (i=0; i<C_0_MAX; i++) { res.coef[i]=*(*(jac+i)); }; return(res); } /***********************************************************************/ int substituir_formas_modp(casillamodp cas) /***********************************************************************/ /* Dada una casilla, despeja una variable y substituye el resultado en */ /* el vector de las $x_i$ hasta que $x_l=0$. En este caso, devuelve */ /* $1$, en otro caso, substituye todas las variables $x_i$ y devuelve */ /* $0$. */ /***********************************************************************/ { int i; despejemodp des; int escero, res; casillamodp temp; escero=1; res=0; for (i=0; i<C_0_MAX && escero; i++) { escero=(0==cas.coef[i]); }; if (escero) { res=1; }; des=despejar_una_variablemodp(cas); temp=substituir_modp(*equis, des); #ifndef SIN_SALIDA A.2. ALGORITMO DE CÁLCULO DE COTAS 337 fprintf(salida_TeX, "\n\nRealizamos una substituci\\’on," " a partir de $x_{%d}$,\n$$", des.pos+l); escribe_casillamodp_archivo_TeX_l(des.cas, "x", salida_TeX); fprintf(salida_TeX, "=0$$\n\n"); #endif *equis=temp; if (es_cero_cas_modp(*equis)) { res=1; } else { for (i=1; i<C_0_MAX; i++) { temp=substituir_modp(*(equis+i), des); *(equis+i)=temp; }; res=0; }; return res; } /***********************************************************************/ int es_cero_jacobi_modp(gran_jacobi_modp jac) /***********************************************************************/ /* Devuelve $1$ si el Jacobi correspondiente es nulo, $0$ en caso */ /* contrario. */ /***********************************************************************/ { int res, i, j; res=1; for (i=0; i<C_0_MAX && res; i++) { for (j=0; j<=i && res; j++) { res=(0==(*(*(jac+i)+j))); }; }; return(res); } /***********************************************************************/ void jacobi_modp( int i, int j, int k, gran_jacobi_modp *res) /***********************************************************************/ /* Asigna a *res los coeficientes de la forma cuadratica f(i,j,k). */ /***********************************************************************/ { int i1, j1; casillamodp aij, bij, ajk, bjk, aki, bki; long int f1, f2, f3, f4; aij=alpha_modp(i,j); bij=alpha_modp(i+j+c0,k); ajk=alpha_modp(j,k); bjk=alpha_modp(j+k+c0, i); aki=alpha_modp(k,i); 338 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS bki=alpha_modp(k+i+c0, j); for (i1=0; i1<C_0_MAX; i1++) { for (j1=0; j1<i1; j1++) { f1=(((aij.coef[i1] * bij.coef[j1])%primo) + ((bij.coef[i1] * aij.coef[j1]) % primo)) % primo; f2=(((ajk.coef[i1] * bjk.coef[j1])%primo) + ((bjk.coef[i1] * ajk.coef[j1]) % primo)) % primo; f3=(((aki.coef[i1] * bki.coef[j1])%primo) + ((bki.coef[i1] * aki.coef[j1]) % primo)) % primo; f4=(f1+f2) % primo; *(*((*res)+i1)+j1)=(f4+f3) % primo; }; f1=(aij.coef[i1] * bij.coef[i1]) % primo; f2=(ajk.coef[i1] * bjk.coef[i1]) % primo; f3=(aki.coef[i1] * bki.coef[i1]) % primo; f4=(f1 + f2) % primo; *(*((*res)+i1)+i1)=(f4 + f3) % primo; }; } /***********************************************************************/ void escribe_casillamodp_archivo_TeX_l(casillamodp cas, char *nom_var, FILE *archivo) /***********************************************************************/ /* Escribe en un archivo TeX el valor de una casilla, denotando con el */ /* nombre *nom_var las diversas variables. */ /***********************************************************************/ { int j; int salio_primer_elemento; if (es_cero_cas_modp(cas)) { verifica(fprintf(archivo, "0")); } else { salio_primer_elemento=0; for (j=0; j<cas.longitud; j++) { if ((cas.coef[j]%primo)!=0) { if (!salio_primer_elemento) { if (((cas.coef[j]-1)%primo)!=0) { verifica(fprintf(archivo, "%ld" ,cas.coef[j])); verifica(fprintf(archivo, "%s_{%d}", nom_var, j+l)); salio_primer_elemento=1; } else /* cas.coef[j]=1 */ A.2. ALGORITMO DE CÁLCULO DE COTAS 339 { verifica(fprintf(archivo, "%s_{%d}", nom_var, j+l)); salio_primer_elemento=1; }; } else /* salio_primer_elemento */ { if (((cas.coef[j]-1)%primo)!=0) { verifica(fprintf(archivo, "+%ld", cas.coef[j])); verifica(fprintf(archivo, "%s_{%d}", nom_var, j+l)); } else /* cas.coef[j].num==1 */ { verifica(fprintf(archivo, "+%s_{%d}", nom_var, j+l)); } } } }; }; verifica(fprintf(archivo, " ")); } /***********************************************************************/ void escribe_jacobi_modp(gran_jacobi_modp jac) /***********************************************************************/ /* Escribe en pantalla el valor de un Jacobi. */ /***********************************************************************/ { int i,j; for (i=0; i<C_0_MAX; i++) { for (j=0; j<=i; j++) { if (((*(*(jac+i)+j))%primo)!=0) { printf("%ld",(*(*(jac+i)+j))); printf("x_%d x_%d\n", i+l, j+l); }; }; }; } /***********************************************************************/ void verifica(int valor) /***********************************************************************/ /* Esta funcion detiene el programa si su argumento, una funcion de */ /* escritura, devuelve un numero negativo. */ /***********************************************************************/ 340 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS { if (valor<0) { perror("Error de escritura"); exit(1); }; } A.2.7. El archivo quadr.c /*********************************************************************/ /* Archivo quad.c */ /* Contiene las definiciones de funciones necesarias para resolver */ /* una ecuacion de segundo grado mod p. */ /*********************************************************************/ #include <stdio.h> #include <stdlib.h> #include "pjacobi.h" /*********************************************************************/ void solve2(long int a, long int b, long int c, long int p, solucion res) /*********************************************************************/ /* Esta funcion obtiene la solucion de la ecuacion de segundo grado */ /* $ax^2+bx+c=0$ en el cuerpo $Z_p$ (supuesto que sea resoluble) y */ /* coloca la solucion en res. Caso de no ser resoluble, devuelve un */ /* puntero con un indicador de que no hay solucion. */ /*********************************************************************/ { long int disc, r, inverso, b1,c1; if (!((2*a)%p)) /* o sea, 2a es cong con 0 mod p */ { res->haysolucion=0; res->sol1=0; res->sol2=0; } else { disc=b*b-4*a*c; disc=((disc%p)+p)%p; if (disc) { if (legendre(disc, p)==1) { /* Hay solucion */ r=shanks_sqrt(disc,p); inverso=invmodp(2*a,p); b1=(((inverso*(-b+r))%p)+p)%p; c1=(((inverso*(-b-r))%p)+p)%p; res->haysolucion=1; res->sol1=b1; A.2. ALGORITMO DE CÁLCULO DE COTAS 341 res->sol2=c1; } else { res->haysolucion=0; res->sol1=0; res->sol2=0; }; } else { res->haysolucion=1; inverso=invmodp(2*a,p); res->sol1=(inverso*(p-b))%p; res->sol2=res->sol1; }; }; } A.2.8. El archivo jacarbol.c /* Archivo jacarbol.c */ #include <stdio.h> #include <stdlib.h> #include "pjacobi.h" /* Si se define */ /* #define REQUETEVERBOSE 1*/ /* se ve en la salida estandar como va el calculo. */ #ifdef LINEAL void procesar_jacobi_no_fact(gran_jacobi_modp jac); #endif /***********************************************************************/ int main_function(int argc, char *argv[]) /***********************************************************************/ /* Funcion principal de este programa. Contiene la descripcion */ /* general del algoritmo. */ /***********************************************************************/ { gran_jacobi_modp *jac; int kkk; char *nombre_salida_TeX; if (argc<4) { l=4; c0=6; primo=19; printf("Asignados los valores por defecto $c0=6$, $l=4$, $p=19$.\n"); } else { 342 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS l=atoi(argv[2]); c0=atoi(argv[1]); primo=atol(argv[3]); printf("Asignados los valores $c_0=%d$, $l=%d$, $p=%ld$.\n", c0, l, primo); }; C_0_MAX=primo-l; vermem(jac=malloc(sizeof(gran_jacobi_modp))); vermem((*jac)=malloc(C_0_MAX*sizeof(long int *))); vermem(nombre_salida_TeX=malloc(22)); for (kkk=0; kkk<C_0_MAX; kkk++) { vermem(*(*jac+kkk)= malloc((kkk+1)*sizeof(long int))); }; sprintf(nombre_salida_TeX, "c_0=%d-l=%d-p=%ld.tex", c0, l, primo); if ((salida_TeX=fopen(nombre_salida_TeX, "wt"))==NULL) { perror("Error en archivo de salida TeX"); exit(1); }; fprintf(salida_TeX, "Asignados los valores $l=%d$," " $c_0=%d$, $p=%ld$.\n", l, c0, primo); inicia_equis_modp(); ene=(C_0_MAX)*(C_0_MAX+1)/2; #ifdef REQUETEVERBOSE printf("El valor de ene es %ld.\n", ene); #endif aplica_jacobi_modp(jac); fclose(salida_TeX); for (kkk=0; kkk<C_0_MAX; kkk++) { free(*(*jac+kkk)); }; free (*jac); free(jac); return(0); } /***********************************************************************/ void aplica_jacobi_modp(gran_jacobi_modp *jac) /***********************************************************************/ /* Aplica las relaciones de Jacobi para los distintos niveles tratando */ /* de factorizarlas hasta conseguir una contradiccion. */ /***********************************************************************/ { int a, b, j, todos_los_jacobis_son_nulos; casillamodp forma; contradiccion=0; nivel_de_reserva=5; maximo_nivel_hallado=5; hay_que_repetir=0; nivel=5; /* minimo valor del nivel menos uno */ A.2. ALGORITMO DE CÁLCULO DE COTAS 343 inicia_superpila(); for (;;) { while (!contradiccion) { nivel++; /* incrementamos el nivel */ hay_jacobi_despejado=0; se_ha_despejado=1; todos_los_jacobis_son_nulos=1; #ifdef REQUETEVERBOSE printf("\n\nNivel actual: %d\nNivel de reserva:" " %d\nMaximo nivel hallado: %d\n", nivel, nivel_de_reserva, maximo_nivel_hallado); #endif if (maximo_nivel_hallado<nivel) { maximo_nivel_hallado=nivel; }; se_ha_despejado=1; fprintf(salida_TeX, "\n\nNivel %d\n\n", nivel); for (a=(nivel/3)-1; a>0 && !contradiccion; a--) { for (b=(nivel-a-1)/2; b>a && !contradiccion; b--) { jacobi_modp(a,b,nivel-a-b, jac); #ifdef REQUETEVERBOSE printf("Jacobi (%d, %d, %d):\n", a, b, nivel-a-b); escribe_jacobi_modp(*jac); #endif if (!es_cero_jacobi_modp(*jac)) { todos_los_jacobis_son_nulos=0; if (factorizable_l_modp(*jac)) { /* Se factoriza x_l */ #ifdef REQUETEVERBOSE printf("** Factorizacion tipo 1 **\n"); #endif forma=entre_x_l_modp(*jac); fprintf(salida_TeX, "\nConsideremos " "Jacobi: " "$f(%d, %d, %d)=x_{%d}\\bigl(", a, b, nivel-a-b, l); escribe_casillamodp_archivo_TeX_l(forma, "x", salida_TeX); fprintf(salida_TeX, "\\bigr)$.\n\n"); contradiccion=substituir_formas_modp(forma); hay_jacobi_despejado=1; if (!se_ha_despejado) { hay_que_repetir=1; }; } else { se_ha_despejado=0; 344 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS }; }; }; }; if ((hay_jacobi_despejado)&&(!se_ha_despejado)) { hay_que_repetir=1; }; /* Escribimos los valores validos para el algebra de Lie */ fprintf(salida_TeX, "\\begin{eqnarray*}\n"); for (j=0; j<C_0_MAX; j++) { fprintf(salida_TeX, "x_{%d}&=&", j+l); escribe_casillamodp_archivo_TeX_l(*(equis+j), "x", salida_TeX); if (j<C_0_MAX-1) { fprintf(salida_TeX, "\\\\\n"); }; }; fprintf(salida_TeX, "\n\\end{eqnarray*}\n\n"); fflush(salida_TeX); if (!hay_jacobi_despejado&&!todos_los_jacobis_son_nulos) { #ifdef REQUETEVERBOSE printf("Imposible despejar de momento.\n"); #endif contradiccion=aplica_tecnica_2_modp(jac, nivel); hay_que_repetir=1; }; if (hay_jacobi_despejado&&hay_que_repetir) { nivel=nivel_de_reserva; hay_jacobi_despejado=0; hay_que_repetir=0; }; if (hay_jacobi_despejado&&!hay_que_repetir) { nivel_de_reserva=nivel; }; if (todos_los_jacobis_son_nulos && (nivel_de_reserva==nivel-1)) { nivel_de_reserva++; }; }; if (superpila->siguiente==NULL) { break; }; restaura_superpila(); nivel--; contradiccion=0; continue; }; A.2. ALGORITMO DE CÁLCULO DE COTAS 345 fprintf(salida_TeX, "\nLa pila ha quedado vaciada del todo.\n\n\n" "El nivel m\\’aximo al que se ha llegado " "(el valor de la tabla) es $%d$.\n\n", maximo_nivel_hallado); printf("\n\nNivel de contradiccion: %d\n\n", maximo_nivel_hallado); } /***********************************************************************/ void inicia_superpila() /***********************************************************************/ /* La siguiente funcion prepara una pila para guardar nuevos datos en */ /* la tecnica 2 de factorizacion. */ /***********************************************************************/ { caso_actual=1; vermem(superpila=malloc(sizeof(PILA))); superpila->siguiente=(PILA*)NULL; superpila->equis_actuales=(casillamodp*)NULL; superpila->substitucion_actual=(casillamodp*)NULL; superpila->numero_de_caso=0; superpila->nivel_de_substitucion=0; } /***********************************************************************/ void anyade_a_superpila(casillamodp *substitucion) /***********************************************************************/ /* Esta funcion anyade a la superpila una substitucion procedente de */ /* una factorizacion. Guarda el contenido de las equis actuales con */ /* animo de poderlas restaurar despues. */ /***********************************************************************/ { PILA *nueva_superpila; int i, j; vermem(nueva_superpila=malloc(sizeof(PILA))); nueva_superpila->numero_de_caso=caso_actual; fprintf(salida_TeX, "\nA\\~nadimos a la pila $"); escribe_casillamodp_archivo_TeX_l(*substitucion,"x",salida_TeX); fprintf(salida_TeX, "$ y lo guardamos como el caso $n=%d$.\n\n", caso_actual); caso_actual++; vermem(nueva_superpila->equis_actuales=malloc(C_0_MAX * sizeof(casillamodp))); for (i=0; i<C_0_MAX; i++) { (nueva_superpila->equis_actuales+i)->longitud=C_0_MAX; for (j=0; j<C_0_MAX; j++) { ((nueva_superpila->equis_actuales)+i)->coef[j]=(equis+i)->coef[j]; }; }; nueva_superpila->nivel_de_substitucion=nivel_de_reserva; nueva_superpila->substitucion_actual=substitucion; nueva_superpila->siguiente=superpila; superpila=nueva_superpila; 352 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS } psolucion; /*********************************************************************/ /* El tipo de datos pila permite almacenar uno de los valores de las */ /* substituciones en las disyuntivas que se plantean al factorizar */ /* los Jacobi cuando uno de los factores no es $x_l$. Almacena un */ /* numero de caso para las referencias, el valor de las $x_i$ */ /* actuales, el nivel para el cual estamos seguros que todas las */ /* ecuaciones de Jacobi de niveles no superiores a el se satisfacen, */ /* la forma que se despeja y el valor siguiente para ser recuperado. */ /*********************************************************************/ struct pila { int numero_de_caso; casillamodp *equis_actuales; int nivel_de_substitucion; casillamodp *substitucion_actual; PILA *siguiente; }; /*********************************************************************/ /* El puntero gran_jacobi_modp sirve para almacenar los valores de */ /* $x_{i+l}$ en funcion de las variables que queden libres. Tambien */ /* se usa para variables auxiliares de calculo con datos de este */ /* tipo. */ /*********************************************************************/ typedef long int **gran_jacobi_modp; /*********************************************************************/ /* solucion no es mas que un puntero a una psolucion, solucion de */ /* una ecuacion de segundo grado. */ /*********************************************************************/ typedef psolucion *solucion; /*********************************************************************/ /*********************************************************************/ /** VARIABLES GLOBALES **/ /*********************************************************************/ /*********************************************************************/ PILA *superpila; casillamodp *equis; long int C_0_MAX, primo, ene, terminos_asignados; int l, c0, STACK_OVERFLOW, caso_actual, nivel, maximo_nivel_hallado, nivel_de_reserva, contradiccion, se_ha_despejado, hay_que_repetir, hay_jacobi_despejado, num_jacobis_en_pila; A.2. ALGORITMO DE CÁLCULO DE COTAS 353 FILE *salida, *salida_TeX, *salida_cab_TeX, *salida_maple; /*********************************************************************/ /*********************************************************************/ /** FUNCIONES DEFINIDAS **/ /*********************************************************************/ /*********************************************************************/ /*********************************************************************/ /* power.c */ /*********************************************************************/ long int power(long int base, long int exponente, long int modulo); /*********************************************************************/ /* Esta funcion calcula la potencia base^exponente y reduce el */ /* resultado al modulo dado. Ha sido extraida del libro de Peter */ /* Giblin, "Primes and Programming". */ /*********************************************************************/ /*********************************************************************/ /* legendre.c */ /*********************************************************************/ void WriteRatio(long int n, long int k, int sign); /*********************************************************************/ /* Esta funcion escribe en pantalla de una manera simplificada los */ /* simbolos de Legendre/Jacobi que aparecen en el calculo. Solo se */ /* usa cuando esta definido DRAFTSHANKS */ /*********************************************************************/ int legendre(long int n, long int k); /*********************************************************************/ /* Esta funcion devuelve el simbolo de Legendre/Jacobi ${n\brack */ /* k}$. La idea del algoritmo es del texto de Giblin. */ /*********************************************************************/ /*********************************************************************/ /* shanks.c */ /*********************************************************************/ long int shanks_sqrt_intermedio(long int a,long int p,long int z); /*********************************************************************/ /* La funcion shanks_sqrt_intermedio determina la raiz cuadrada de a */ /* dado el valor inicial z del algoritmo de Shanks. */ /*********************************************************************/ 354 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS long int shanks_inicial(long int p); /*********************************************************************/ /* Obtiene un valor inicial para el algoritmo de Shanks, esto es, un */ /* no residuo cuadratico. */ /*********************************************************************/ long int shanks_sqrt(long int a, long int p); /*********************************************************************/ /* Algoritmo de Shanks para el calculo de la raiz cuadrada mod p */ /*********************************************************************/ /*********************************************************************/ /* modular.c */ /*********************************************************************/ long int choose_modp(unsigned long int x1, unsigned long int x2); /*********************************************************************/ /* Esta funcion calcula el numero combinatorio ${x1\choose x2}$ mod */ /* p. */ /*********************************************************************/ EUCLIDES eucgcd(long int a0, long int b0); /*********************************************************************/ /* Esta funcion calcula el maximo comun divisor de dos numeros */ /* enteros, a0 y b0, asi como los coeficientes que aparecen en la */ /* relacion de Bezout. Estos tres datos aparecen reflejados en el */ /* tipo EUCLIDES. El algoritmo empleado es el de Euclides, en la */ /* version descrita en lenguaje PASCAL por Peter Gibling, "Primes */ /* and Programming", Cambridge, en la pagina 21. */ /*********************************************************************/ long int invmodp(long int a0, long int p); /*********************************************************************/ /* En esta funcion se obtiene el inverso de a0 mod p. Hace uso de la */ /* funcion definida anteriormente, y, en el caso de que p no sea */ /* primo y $\gcd(a0, p)\ne 1$, se genera un mensaje de error. */ /*********************************************************************/ casillamodp substituir_modp(casillamodp, despejemodp); /*********************************************************************/ /* Substituye en una casillamodp una variable despejada mod p de */ /* otra casilla. */ /*********************************************************************/ despejemodp despejar_una_variablemodp(casillamodp c); /*********************************************************************/ /* En esta funcion se intenta despejar una variable (mod p) de una */ /* casilla. Despejamos la variable situada mas a la derecha. */ /*********************************************************************/ casillamodp prodesc_modp(long int, casillamodp); A.2. ALGORITMO DE CÁLCULO DE COTAS 355 /*********************************************************************/ /* En esta funcion se da el resultado de multiplicar un escalar (un */ /* entero mod p) por una casilla (esto es, una forma lineal). */ /*********************************************************************/ /*********************************************************************/ casillamodp menos_cas_modp(casillamodp cas); /*********************************************************************/ /* Multiplica por -1 la casillamodp cas. */ /*********************************************************************/ casillamodp sum_cas_modp(casillamodp, casillamodp); /*********************************************************************/ /* Suma dos casillas mod p. */ /*********************************************************************/ int es_cero_cas_modp(casillamodp); /*********************************************************************/ /* Devuelve 1 si la casilla es nula, 0 en caso contrario. */ /*********************************************************************/ void escribe_casillamodp(casillamodp); /*********************************************************************/ /* Escribe en stdout una casilla mod p. */ /*********************************************************************/ /*********************************************************************/ int son_casillamodps_iguales(casillamodp cas1, casillamodp cas2); /*********************************************************************/ /* Devuelve $1$ si las dos casillas son iguales, $0$ en otro caso. */ /*********************************************************************/ casillamodp alpha_modp(int i, int j); /*********************************************************************/ /* Calcula $\alpha_{i,j}$ mod p en funcion de los $x_k$. */ /*********************************************************************/ void inicia_equis_modp(void); /*********************************************************************/ /* Inicializa el vector de las $x_i$, haciendo cada elemento igual a */ /* la $x_i$ correspondiente, y aplicando despues, mientras sea */ /* posible, la periodicidad mod p-1. */ /*********************************************************************/ int factorizable_l_modp(gran_jacobi_modp); /*********************************************************************/ /* Devuelve $1$ si la relacion de Jacobi tiene como factor comun */ /* $x_l$, y $0$ en otro caso. */ /*********************************************************************/ casillamodp entre_x_l_modp(gran_jacobi_modp); /*********************************************************************/ /* Trata de dividir el Jacobi entre $x_l$, supuesto que $x_l$ es */ /* factor comun. */ /*********************************************************************/ int substituir_formas_modp(casillamodp); 356 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS /*********************************************************************/ /* Dada una casilla, despeja una variable y substituye el resultado */ /*en el vector de las $x_i$ hasta que $x_l=0$. En este caso, */ /*devuelve $1$, en otro caso, substituye todas las variables $x_i$ y */ /*devuelve $0$. */ /*********************************************************************/ int es_cero_jacobi_modp(gran_jacobi_modp); /*********************************************************************/ /* Devuelve $1$ si el Jacobi correspondiente es nulo, $0$ en caso */ /* contrario. */ /*********************************************************************/ void jacobi_modp(int i, int j, int k, gran_jacobi_modp *res); /*********************************************************************/ /* Asigna a *res los coeficientes de la forma cuadratica f(i,j,k). */ /*********************************************************************/ void escribe_casillamodp_archivo_TeX_l(casillamodp cas, char *nom_var, FILE *archivo); /*********************************************************************/ /* Escribe en un archivo TeX el valor de una casilla, denotando con */ /* el nombre *nom_var las diversas variables. */ /*********************************************************************/ void escribe_jacobi_modp(gran_jacobi_modp jac); /*********************************************************************/ /* Escribe en pantalla el valor de un Jacobi. */ /*********************************************************************/ void verifica(int valor); /*********************************************************************/ /* Esta funcion detiene el programa si su argumento, una funcion de */ /* escritura, devuelve un numero negativo. */ /*********************************************************************/ /*********************************************************************/ /* jacarbol.c */ /*********************************************************************/ int main_function(int argc, char *argv[]); /*********************************************************************/ /* Funcion principal de este programa. Contiene la descripcion */ /* general del algoritmo. */ /*********************************************************************/ void aplica_jacobi_modp(gran_jacobi_modp *jac); /*********************************************************************/ /* Aplica las relaciones de Jacobi para los distintos niveles */ /* tratando de factorizarlas hasta conseguir una contradiccion. */ /*********************************************************************/ void inicia_superpila(); A.2. ALGORITMO DE CÁLCULO DE COTAS 357 /*********************************************************************/ /* Esta funcion prepara una pila para guardar nuevos datos en */ /* la tecnica 2 de factorizacion. */ /*********************************************************************/ void anyade_a_superpila(casillamodp *substitucion); /*********************************************************************/ /* Esta funcion anyade a la superpila una substitucion procedente de */ /* una factorizacion. Guarda el contenido de las equis actuales con */ /* animo de poderlas restaurar despues. */ /*********************************************************************/ void restaura_superpila(); /*********************************************************************/ /* Esta funcion restaura los valores de la superpila tras haberse */ /* producido una contradiccion. */ /*********************************************************************/ int aplica_tecnica_2_modp(gran_jacobi_modp *jac, int n); /*********************************************************************/ /* Esta funcion intenta factorizar Jacobis que no son de la forma */ /* $x_lt(x_l,\ldots, x_{p-1})$. */ /*********************************************************************/ /*********************************************************************/ /* quadr.c */ /*********************************************************************/ void solve2(long int a, long int b, long int c, long int p, solucion res); /*********************************************************************/ /* Esta funcion obtiene la solucion de la ecuacion de segundo grado */ /* $ax^2+bx+c=0$ en el cuerpo $Z_p$ (supuesto que sea resoluble) y */ /* coloca la solucion en res. Caso de no ser resoluble, devuelve un */ /* puntero con un indicador de que no hay solucion. */ /*********************************************************************/ /*********************************************************************/ /* factors.c */ /*********************************************************************/ int factorizar(gran_jacobi_modp a, long int p, casillamodp *b, casillamodp *c); /*********************************************************************/ /* Trata de dar una factorizacion de la expresion de Jacobi a mod p. */ /* Caso de existir, la coloca en los punteros b y c. Devuelve un */ 358 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS /* entero que indica si dicha solucion existe o no existe. */ /*********************************************************************/ /*********************************************************************/ /* pjacobi.c */ /*********************************************************************/ int main(int argc, char *argv[]); /*********************************************************************/ /* Funcion main() que no hace mas que llamar a main_function(). */ /*********************************************************************/ A.2.10. El archivo Makefile cc=cc -Wall OBJETOS=arbol.o despeje.o fraccion.o casilla.o primos.o triang.o output.o OBJETOSVL=$(OBJETOS) despejevl.o fraccionvl.o casillavl.o primosvl.o\ gros.o outputvl.o zetavl.o zeta2.o cabeceras= bullet.h all: bullet zeta prueba arbol.o: arbol.c $(cabeceras) $(cc) -c -g arbol.c despeje.o: despeje.c $(cabeceras) $(cc) -c -g despeje.c fraccion.o: fraccion.c $(cabeceras) $(cc) -c -g fraccion.c casilla.o: casilla.c $(cabeceras) $(cc) -c -g casilla.c output.o: output.c $(cabeceras) $(cc) -c -g output.c primos.o: primos.c $(cabeceras) $(cc) -c -g primos.c triang.o: triang.c $(cabeceras) $(cc) -c -g triang.c bullet.o: bullet.c $(cabeceras) $(cc) -c -g bullet.c A.2. ALGORITMO DE CÁLCULO DE COTAS 359 bullet: bullet.o $(OBJETOS) $(cabeceras) $(cc) -o bullet -g bullet.o $(OBJETOSVL) zeta: zeta.o zeta2.o $(OBJETOSVL) $(cabeceras) $(cc) -o zeta -g zeta.o $(OBJETOSVL) zeta.o: zeta.c $(cabeceras) $(cc) -c -g zeta.c zeta2.o: zeta2.c $(cabeceras) $(cc) -c -g zeta2.c gros.o: gros.c bulletvl.h $(cc) -c -g gros.c fraccionvl.o: fraccionvl.c bulletvl.h $(cc) -c -g fraccionvl.c casillavl.o: casillavl.c bulletvl.h $(cc) -c -g casillavl.c zetavl.o: zetavl.c bulletvl.h $(cc) -c -g zetavl.c outputvl.o: outputvl.c bulletvl.h $(cc) -c -g outputvl.c primosvl.o: primosvl.c bulletvl.h $(cc) -c -g primosvl.c despejevl.o: despejevl.c bulletvl.h $(cc) -c -g despejevl.c prueba.o: prueba.c bulletvl.h bullet.h $(cc) -g -c prueba.c prueba: prueba.o $(OBJETOSVL) $(cc) -g -o prueba prueba.o $(OBJETOSVL) 360 APÉNDICE A. LISTADOS DE LOS PROGRAMAS UTILIZADOS Bibliografía [1] B. Beisiegel. Semiextraspezielle p-gruppen. Math. Z., 156:247–254, 1977. [2] N. Blackburn. On a special class of p-groups. Acta Math., 100:45–92, 1958. [3] W. Burnside. Theory of Groups of Finite Order. Cambridge University Press. Reprinted by Dover 1955, New York, 2nd edition, 1911. [4] M. Cartwright. Class and breadth of a finite p-group. Bull. London Math. Soc., 19:425–430, 1987. [5] B.W. Char, K.O. Geddes, G.H. Gonnet, M.B. Monagan, and S.M. Watt. Maple reference manual. New York, 1988. [6] Waltraud Felsch, Joachim Neubüser, and Wilhelm Plesken. Space groups and groups of prime-power order IV. Counterexamples to the classbreadth conjecture. J. London Math. Soc. (2), 24:113–122, 1981. [7] G. A. Fernández-Alcober. The exact lower bound for the degree of commutativity of a p-group of maximal class. J. Algebra, 174:523–530, 1995. [8] Joseph A. Gallian. On the breadth of a finite p-group. Math. Z., 126:224– 226, 1972. [9] Peter Giblin. Primes and Programming. Cambridge University Press, Cambridge, Great Britain, 1993. [10] P. Hall. A contribution to the theory of groups of prime-power order. Proc. London Math. Soc., 36:29–95, 1933. 361