Códigos Goppa

Códigos Goppa Antonio Beato Caro Códigos Goppa Antonio Beato Caro Memoria presentada como parte de los requisitos para la obtención del título de Grado en Matemáticas por la Universidad de Sevilla. Tutorizada por Dr. Jose María Tornero Sánchez Agradecimientos A todos los profesores que he tenido en la carrera por haber conseguido fomentar mi curiosidad por las matemáticas. En especial a José María Tornero Sánchez por ese infinito (no numerable) de veces que ha leído este trabajo y haberme ayudado tanto a mejorarlo. A todos los amigos que he hecho durante esta etapa porque son ellos los que harán que recuerde estos años como unos de los mejores de mi vida. A mi familia por haberme dado esta oportunidad y por estar siempre ahí cuando me sentía frustrado (que no han sido pocas veces). A Natalia porque no solo me he acompañado en este ciclo sino también lo hará en el que está por venir. Listen to me, Morty. I know that new situations can be intimidating. You’re lookin’ around and it’s all scary and different, but y’know ... meeting them head-on, charging into ‘em like a bull — that’s how we grow as people. Rick a Morty Índice general English Abstract 0 1. Conceptos generales 1 1.1. Introducción................................ 1 1.2. Preliminares sobre códigos correctores de errores ................................... 2 1.3. Códigoscíclicos .............................. 12 1.4. CódigosBCH................................ 14 1.5. Códigos de Goppa clásicos . . . . . . . . . . . . . . . . . . . . . . . . 17 2. Preludio de curvas algebraicas 23 2.1. Anillos de valoración . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2. Divisores.................................. 27 2.3. Lugares................................... 32 2.4. Puntos racionales de una curva . . . . . . . . . . . . . . . . . . . . . . 35 2.5. Divisores en cuerpos arbitrarios y la desigualdad de Riemann . . . . . 39 3. Códigos Algebraico-Geométricos 43 3.1. Definición ................................. 43 4códigos goppa 3.2. Generalizaciones y ejemplos . . . . . . . . . . . . . . . . . . . . . . . 46 3.3. Mejora de la cota de Gilbert-Varshamov . . . . . . . . . . . . . . . . . 53 4. Apéndice 55 4.1. Dualidad en códigos correctores . . . . . . . . . . . . . . . . . . . . . 55 4.2. Género de una curva proyectiva sin puntossingulares ............................. 57 4.3. El teorema de Riemann-Roch. Dualidad en códigosdeGoppa.............................. 62 4.4. Descripción de Gal(𝑘∕𝑘)......................... 66 Resumen El objetivo de este trabajo es servirnos de las herramientas impartidas en la asignatura de Álgebra Conmutativa y Geometría Algebraica para estudiar la teoría de códigos correctores de errores, presentada en la asignatura Teoría de Códigos y Criptografía. Esto servirá de pretexto para profundizar en temas importantes de la geometría algebraica como la teoría de divisores para curvas. Como principal aplicación para la teoría de códigos, definiremos los códigos Goppa, una familia de códigos de gran importancia histórica pues es la primera familia infinita de códigos en superar la cota de Gilbert-Varshamov. En cuanto a la organización del trabajo, este se encuentra dividido en tres capítulos y un apéndice: El primer capítulo presenta, en sus tres primeras secciones un repaso de los conceptos básicos de la asignatura de Teoría de Códigos y Criptografía (Definición de código corrector de errores, corrección por mínima distancia, matrices de control, códigos cíclicos...). Las dos secciones siguientes están dedicadas a dos familias de códigos que fueron posteriormente generalizados por los códigos Goppa: los códigos BCH y los códigos de Goppa clásicos. En el segundo capítulo se desarrolla la geometría algebraica necesaria para definir los códigos de Goppa. El capítulo comienza exponer técnicas para describir curvas proyectivas sin puntos singulares sobre cuerpos algebraicamente cerrados a través de estudiar los llamados anillos de valoración de su cuerpo de funciones. Tras eso, se da una pequeña introducción a la teoría de divisores en dicho caso y se definen los espacios de Riemman-Roch, los cuales que serán la base de los códigos Goppa. En las últimas secciones del capítulo se define la noción de curva proyectiva abstracta que será de gran utilidad para extender la teoría a cuerpos arbitrarios. 1 Conceptos generales 1.1 Introducción Si uno ha rayado uno de los ya antiguos DVDs alguna vez en su vida, tal vez haya tenido la suerte de comprobar que, a no ser que el daño fuera demasiado grande, los lectores DVD eran capaces de acceder a su contenido sin perder nada de información, reproduciéndolo exactamente segundo a segundo como si no se hubiese rayado nunca. ¿Cómo es esto posible? El deterioro de la superficie definitivamente altera y hace que se pierda parte del contenido que el disco tuviese grabado. La respuesta a esta pregunta se halla en una manera muy precisa de almacenar la información: los códigos correctores de errores. Planteemos el problema con antelación al incidente. Supongamos que como fabricantes de DVDs, sabemos que probablemente, tarde o temprano, nuestros discos pueden sufrir desperfectos y por tanto, decidimos utilizar parte de la capacidad de almacenamiento del DVD para, posiblemente, arreglar dichos desperfectos. Digamos que, como en última instancia es bien conocido que la información puede ser codificada de forma discreta en una sucesión de 1s y 0s, queremos almacenar un gran número escrito en código binario en nuestro DVD. Podríamos por ejemplo, almacenar el mismo número tres veces y así, cuando el lector examine la información, podría ir examinando el número cifra a cifra y en caso de que haya discordancia entre una cifra y sus dos supuestas copias, tomar como valor definitivo a leer del que haya mayor ocurrencia, como tenemos la información repetida tres veces, no es posible que haya empates. Este ejemplo es lo que se conoce como un código de repetición de longitud 3. Esto parecería solucionar el problema. Sin embargo, el procedimiento antes descri- to tiene notables desventajas, por ejemplo, a la hora de querer almacenar información, 2códigos goppa solamente utilizamos un tercio de la capacidad disponible del disco, dejándose dos tercios de la misma como "datos redundantes". Además de esto, es sencillo darse cuenta de que este método no es capaz de lidiar con dos o más errores coincidiendo en la misma posición de una cifra en dos de las copias de los números. La teoría de códigos correctores de errores trata precisamente de generalizar esta idea a procedimientos que acaban siendo muchísimo más eficientes que el código de repetición. Por poner en perspectiva los números, el código de Hamming (cuyo creador, Richard Hamming, fue en 1950 un pionero en la materia) es, al igual que el código de repetición, un procedimiento para detectar y corregir un error que solamente usa 3∕7 de la capacidad de almacenamiento para redundancia mejorando de entrada, notoriamente, los 2∕3 del código anterior. 1.2 Preliminares sobre códigos correctores de errores Para empezar el estudio de estos métodos, comencemos dando algunas definiciones. Como se ha dicho anteriormente, entendemos que a la hora de almacenar la información es posible tenerla en una forma discretizada, siendo así posible codificarla a través de una serie de caracteres (en el caso anterior, 1s y 0s). Por ello, empezamos con la siguiente definición. Definición 1.1. Un alfabeto es un conjunto no vacío de símbolos que no tienen significado individual. Una palabra o un bloque de longitud 𝑛es un elemento de 𝑛. Ejemplo 1.1.Si entendemos que vamos a utilizar dos símbolos para transmitir información podemos asumir que =𝔽2, el cuerpo de dos elementos, teniendo así los símbolos 0y1. En este caso las 𝑛–uplas de elementos se pueden denotar indistintamente de la forma usual (por ejemplo (0,0,0,1,1,1,0,1) ∈ 𝔽8 2) o, usando una notación más compacta, yuxtaponiendo los elementos (en el ejemplo anterior 00011101). Supondremos siempre que la información a codificar puede ser dividida en bloques de longitud 𝑛para ser descodificada de forma independiente. Esto es, que podemos dividir una larga cadena de símbolos en bloques de manera que el significado de cada palabra no depende del resto de palabras. Teniendo esto en cuenta, comencemos por los objetos con los que estudiaremos: los códigos. 1. conceptos generales 3 Definición 1.2. Un código de longitud 𝑛es un conjunto no vacío de palabras, es decir es un subconjunto ⊆𝑛. Si es finito, se llama tamaño del código a su cardinal, #(). En cierto sentido, las palabras de son las que se entienden como "palabras correctas". Es decir, de todas las posibles palabras de 𝑛, nos restringiremos a almacenar la información solamente utilizando palabras de . Así, si tenemos algún tipo de distorsión de la información y observamos palabras que no están en , seremos capaces de detectar que ha habido un error. Ejemplo 1.2.Si es un alfabeto cualquiera, el código de repetición de longitud 𝑛 sobre el alfabeto es = {(𝑎, 𝑎, …, 𝑎)|𝑎∈}⊆𝑛 Para este código se suele tomar =𝔽2y𝑛= 8. En este caso, si en una transmisión de información en la que se usa este código, al recibir la palabra 𝐜= 00000001 detectaríamos que ha habido un error en la transmisión ya que 𝐜∉. Más aún, si la situación es adecuada, podríamos plantearnos incluso reemplazar la palabra errónea por aquella de que "se le parezca más" (en este caso no es difícil adivinar que sería 00000000). Con este objetivo introducimos la siguiente definición. Definición 1.3. La distancia de Hamming en 𝑛es la aplicación 𝑑∶𝑛×𝑛←→ ℝ≥0 (𝐱,𝐲)←→ #{𝑖∣𝑥𝑖≠𝑦𝑖, 𝑖 = 1,…, 𝑛} Esto es, 𝑑(𝐱,𝐲)mide el número de coordenadas distintas de 𝐱e𝐲. Proposición 1.1.La distancia de Hamming es una distancia (en el sentido topológico) sobre 𝑛. Demostración. Se dio en la asignatura de Teoría de Códigos y Criptografía. De esta forma, podemos al recibir una palabra 𝐲∈𝑛, reemplazarla por alguna palabra de que esté a distancia mínima: Definición 1.4 (Descodificación por mínima distancia). Si recibimos la palabra 𝐲∈𝑛, se define su codificación por mínima distancia a la única palabra 𝐱∈ (caso de existir) que minimiza 𝑑(𝐱,𝐲). 4códigos goppa Por tanto, a la hora de descodificar por mínima distancia (la descodificación habitual en los códigos que vamos a estudiar1), nos interesará que las palabras del código disten entre sí lo máximo posible. En el ejemplo de antes, el código anterior tenía solamente dos palabras = {00000000,11111111} y la distancia entre ellas es 8por lo que si el emisor del mensaje envía una palabra del código y hay un fallo en la comunicación de esta, es necesario que se cometan 8o más errores en la transmisión para que no se detecte el error. Se dice en este caso que detecta 7errores. Para medir las bondades de un código, definimos algunos parámetros de interés. Definición 1.5. Si #() = 𝑞y dado un código ⊆𝑛, definimos: 1. Distancia mínima del código al número 𝑑()=m ın{𝑑(𝐱,𝐯) ∣ 𝐱,𝐯∈} 2. Distancia mínima relativa del código al número 𝛿() = 𝑑() 𝑛 3. Tasa de transmisión de información del código al número 𝑅() = log𝑞(#()) 𝑛 4. Redundancia del código al número 𝑛− log𝑞(#()) Trataremos de construir códigos que tengan buenos parámetros concentrándonos especialmente en la distancia mínima del código y en su tasa de información ya que esta está directamente relacionada con el coste de transmisión de la información. Observación 1.1 (Detección de errores).Si es un código de longitud 𝑛y distancia mínima 𝑑y si 𝐜∈y𝐱∈𝑛, se tiene que, si 𝑑(𝐜,𝐱)< 𝑑, entonces 𝐱∉. Decimos en este caso que el código detecta 𝑑−1 errores como vimos en el ejemplo anterior del código de repetición. 1En teoría de códigos se pueden considerar otros métodos de descodificación como los basados en métodos de máxima verosimilitud. 1. conceptos generales 5 Observación 1.2 (Corrección de errores).Si es un código de longitud 𝑛y distancia mínima 𝑑, para cualesquiera 𝐜𝟏,𝐜𝟐∈ 𝐵(𝐜1,⌊𝑑− 1 2⌋)∩𝐵(𝐜2,⌊𝑑− 1 2⌋)= ∅ Dicho de otro modo, si 𝐱∈𝑛no es posible que: 𝑑(𝐜𝑖,𝐱)≤⌊𝑑− 1 2⌋, 𝑖 = 1,2 Entonces si recibimos una palabra que no está en el código, 𝐱∉, y dista de alguna palabra de nuestro código 𝐜∈una cantidad menor o igual a ⌊(𝑑− 1)∕2⌋ sabremos inmediatamente que su descodificación por mínima distancia (la palabra más cercana a 𝐱de nuestro código que supondremos que es la que se tenía intención de transmitir) es necesariamente la palabra 𝐜. Definición 1.6. Diremos que un código corrige ⌊(𝑑− 1)∕2⌋errores cuando se da esta situación. Evidentemente no tiene por qué ser siempre el caso de que cualquier palabra admita una decodificación por mínima distancia. Podríamos, a priori, recibir una palabra que no estuviera a distancia menor o igual a ⌊(𝑑−1)∕2⌋de ninguna de y ahí podrían surgir problemas. Existen códigos (que veremos luego) cuya construcción evita estos casos. Los códigos en general, a nivel conjuntista, son objetos de difícil trato pues no es sencillo, en general, computar parámetros como la distancia mínima o la tasa de información de manera rápida. Por ello, vamos a dotar de un poco de estructura a los objetos con los que vamos a trabajar, introduciendo la familia de los códigos lineales. Definición 1.7. Un código lineal de longitud 𝑛sobre el alfabeto =𝔽𝑞es un subespacio vectorial de 𝔽𝑛 𝑞. Solemos decir que un código lineal es de tipo (𝑛, 𝑚, 𝑑)para decir que es de longitud 𝑛, tamaño 𝑚y distancia mínima 𝑑. Observación 1.3.Si tenemos un código lineal ⊆𝔽𝑛 𝑞con dim() = 𝑘, tenemos que es un código de tipo (𝑛, 𝑞𝑘, 𝑑)y por tanto su tasa de transmisión es () = 𝑘∕𝑛. Además, su redundancia sería 𝑛−𝑘, esto es, de las 𝑛coordenadas, 𝑘son las que llevan la información lo cual es coherente con que el código sea de dimensión 𝑘. 6códigos goppa Ejemplo 1.3 (Código del bit de paridad).Si nuestro alfabeto es =𝔽𝑞, el código del bit de paridad de longitud 𝑛es el conjunto: 𝐶={(𝑐1,…, 𝑐𝑛) ∈ 𝔽𝑛 𝑞||| 𝑛 ∑ 𝑘=1 𝑐𝑘= 0}. El nombre de este código está inspirado en el caso en el que =𝔽2en cuyo caso, el último elemento de cada vector se conoce como bit de paridad y controla si la palabra que se transmite es de suma par o impar. Está claro que entonces 𝑛=𝑞𝑛, y dim() = 𝑞𝑛−1 por venir el código dado por una ecuación implícita. Nos falta ver su distancia mínima. Pronto veremos que, gracias a que el sistema viene dado por una ecuación implícita, es fácil ver que 𝑑= 2. Para ello, hablemos un poco de la distancia mínima en un código lineal. Proposición 1.2.En un código lineal ⊆𝔽𝑛 𝑞se tiene que 𝑑()=m ın {𝑑(𝐜,𝟎)|𝐜∈⧵{𝟎}}. Demostración. Basta observar que si 𝐱,𝐲∈, entonces 𝑑(𝐱,𝐲) = 𝑑(𝐱−𝐲,𝟎)pero como es cerrado para la suma, 𝐱−𝐲∈. A la cantidad 𝑑(𝐱,𝟎)para una palabra 𝐱∈𝔽𝑛 𝑞se le denomina el peso de 𝐱, se denotará por 𝑤(𝐱)y por tanto, con esta nomenclatura, la distancia mínima de un código coincide con el mínimo peso de las palabras no nulas del código. Veamos que podemos caracterizar esta cantidad de manera algebraica. Para ello, usemos la estructura de espacio vectorial de dimensión finita de los códigos lineales. Definición 1.8. Sea ⊂𝔽𝑛 𝑞un código lineal. Si viene expresado por un sistema de ecuaciones implícitas independientes, 𝐴⎛⎜⎜⎝ 𝑥1 ⋮ 𝑥𝑛⎞⎟⎟⎠ =𝟎∈((𝑛−𝑘)×1,𝔽𝑞) diremos que A es una matriz de control de . La existencia de una matriz de control ya proporciona una ventaja considerable de los códigos lineales frente a los que no lo son desde el punto de vista de la práctica pues en vez de tener que almacenar todas las palabras del código, basta con saber cuál 1. conceptos generales 7 es la matriz de control para ir comprobando si las palabras recibidas pertenecen o no a. Además, esta matriz nos da una manera sencilla de calcular la distancia mínima de . Teorema 1.1 (Distancia mínima mediante una matriz de control). Si 𝐴es una matriz de control de un código lineal , la distancia mínima de es la menor cantidad de columnas de 𝐴que necesitamos para formar un conjunto linealmente dependiente. Demostración. Probaremos que existe un vector de peso exactamente 𝑟en el código si y sólo si existe una combinación lineal de exactamente 𝑟columnas con coeficientes no nulos que da 𝟎. Sea 𝐱∈,con 𝑤(𝐱) = 𝑟. Entonces 𝐱∈⇐⇒ 𝐴𝐱=𝟎⇐⇒ 𝑥1𝐶(𝐴)1+⋯+𝑥𝑛𝐶(𝐴)𝑛=𝟎∈𝔽𝑛−𝑘 𝑞 donde exactamente 𝑟de las 𝑛coordenadas de 𝐱son no nulas. Por tanto, 𝑑es precisamente el cardinal del menor conjunto de columnas de 𝐴que formen un conjunto linealmente dependiente. Con esta proposición podemos hallar la distancia mínima de un código sin necesidad de conocer el peso de todas las palabras del código. Por ejemplo, ahora está claro que la distancia mínima del código del ejemplo 1.3 es 𝑑= 2. Veamos como aplicación adicional la distancia mínima del código de Hamming original, el primer ejemplo de códigos correctores de errores de la historia. Ejemplo 1.4 (Código de Hamming original).El código de Hamming original puede ser introducido de una gran variedad de formas, cada una apoyándose y resaltando alguna de las muchas propiedades que este código posee. Nosotros lo veremos como las soluciones de un sistema de ecuaciones, es decir, por su matriz de control. El código de Hamming original se construye sobre =𝔽2, como el conjunto de soluciones en 𝔽7 2del sistema ⎧ ⎪ ⎨ ⎪ ⎩ 𝑥1+𝑥3+𝑥5+𝑥7= 0 𝑥2+𝑥3+𝑥6+𝑥7= 0 𝑥4+𝑥5+𝑥6+𝑥7= 0 Esto es, una matriz de control del código es 𝐴=⎛⎜⎜⎝ 1010101 0110011 0001111⎞⎟⎟⎠ 8códigos goppa Es sencillo comprobar que la distancia mínima del código es 3ya que dos a dos las columnas de 𝐴no son colineales y la primera y segunda columna suman la tercera. Por tanto, en este caso diríamos que el código de Hamming es un código lineal (𝑛= 7, 𝑚 = 24, 𝑑 = 3). Esto quiere decir que el código de Hamming original es un código que detecta 𝑑− 1 = 2 errores y corrige ⌊(𝑑− 1)∕2⌋= 1 error. Su tasa de transmisión sería () = 𝑘∕𝑛= 4∕7. En breve veremos qué hace al código de Hamming un código con tan buenas propiedades. De la misma forma, podemos introducir un código lineal a través de un sistema de generadores. Codificamos esta información en una matriz con la siguiente definición. Definición 1.9. Sea ⊂𝔽𝑛 𝑞un código lineal. Diremos que es una matriz generatriz de cuando las columnas de formen una base de como subespacio vectorial. Observación 1.4.De la propia definición se deduce que es una matriz de rango la dimensión de como espacio vectorial y que además verifica que, si 𝐴es una matriz de control de , entonces 𝐴⋅= 0. Por último, es importante si estamos tratando de optimizar ciertos parámetros de los códigos, estudiar las relaciones que hay entre ellos. A continuación haremos precisamente eso, veremos cotas asociadas a los códigos lineales que son de vital importancia a la hora de establecer si ciertas combinaciones de parámetros son óptimas o no. Observación 1.5.Si es un código lineal, debido a que la distancia de Hamming es invariante por traslación, se tiene que para todo 𝐱∈𝑛y para todo 𝑟∈ℤ≥0, #(𝐵(𝐱, 𝑟))= #(𝐵(𝟎, 𝑟)) por lo que designaremos a este número por 𝑉(𝑟). Proposición 1.3.En las condiciones anteriores 𝑉(𝑟) = 𝑟 ∑ 𝑗=0 (𝑛 𝑗)(𝑞− 1)𝑗. Demostración. Basta observar que para cada 𝑗fijo existen (𝑛 𝑗)(𝑞− 1)𝑗 1. conceptos generales 9 vectores en 𝑛de peso exactamente 𝑗, pues tenemos 𝑛posibles coordenadas de las cuales exactamente 𝑗son no nulas (de ahí el número combinatorio) y en cada una de las coordenadas no nulas escogidas tenemos 𝑞− 1 posibilidades (de ahí el término (𝑞− 1)𝑗). Teorema 1.2 (Cota de Hamming). Si es un código lineal de longitud 𝑛que corrige 𝑡errores (recordemos que 𝑡=⌊(𝑑− 1)∕2⌋) entonces 𝑚𝑉 (𝑡)≤𝑞𝑛, siendo 𝑚el tamaño de . Demostración. Como corrige 𝑡errores, las bolas centradas en las palabras de  con radio 𝑡son disjuntas luego la suma de los cardinales de estas bolas es menor a la cantidad de palabras del espacio total, que es 𝑞𝑛. A los códigos que alcanzan la igualdad en esta cota se les denomina códigos perfectos y son los códigos en los cuales las bolas centradas en las palabras de y de radio la capacidad de corrección 𝑡recubren todo el espacio, luego la detección y la corrección de errores son equivalentes. No hay muchos códigos perfectos y su clasificación es un problema ya resuelto y bien conocido2. Veamos ahora que la dimensión del código (y por tanto la tasa de transmisión) y la distancia mínima de un código no pueden crecer demasiado al mismo tiempo. Teorema 1.3 (Cota de Singleton). Si es un código lineal de tipo (𝑛, 𝑞𝑘, 𝑑)sobre 𝔽𝑞, entonces 𝑘+𝑑≤𝑛+ 1. Demostración. Si 𝐴es una matriz de control de , la distancia mínima de es el mínimo número de columnas linealmente dependientes de 𝐴. Como el rango de 𝐴es 𝑛−𝑘, este número es, a lo más, 𝑛−𝑘+ 1 luego 𝑑≤𝑛−𝑘+ 1. A los códigos que alcanzan la igualdad se les llama códigos de máxima distancia de separación o MDS. La familia de códigos MDS, al contrario que los códigos perfectos, presentan problemas aún abiertos en teoría de códigos. Por último, acabemos con una cota de existencia, es decir, una cota que debe superar al menos algún código lineal. 2Los únicos códigos perfectos son los de la familia de códigos de Hamming y los de la familia de códigos de Golay. Para más información ver [3]. 10 códigos goppa Teorema 1.4 (Cota de Gilbert-Shannon-Varshamov). Si se verifica que 𝑞𝑛−𝑘+1 > 𝑉 (𝑟− 1), entonces existe un código lineal de tipo (𝑛, 𝑞𝑘, 𝑑)con 𝑑≥𝑟. Demostración. La prueba se trata de dar una construcción inductiva. Sea 𝐜1un vector de peso mayor o igual que 𝑟,𝑤(𝐜1)≥𝑟y tomamos 1=⟨𝐜1⟩. En el paso de inducción seleccionados 𝐜1,…,𝐜𝑖−1 independientes generadores de un código lineal 𝑖−1 con parámetros (𝑛, 𝑞𝑖−1, 𝑑), con 𝑑≥𝑟, por hipótesis de inducción se tiene que 𝑞𝑗−1𝑉(𝑑− 1) < 𝑞𝑛, por lo que existe al menos un vector 𝐜𝑖∈𝔽𝑛 𝑞que dista al menos 𝑟de todas las palabras de 𝑖−1 entonces 𝑖=⟨𝐜1,…,𝐜𝑖⟩es el código buscado. La cota de Gilbert-Shannon-Varshamov tiene un gran valor histórico para la teoría de códigos pues el encontrar familias de códigos (no códigos individuales, que se pueden construir siguiendo la demostración) que superasen esta cota fue un reto para la disciplina. Analicemos por último las cotas del ejemplo del código de Hamming original. Ejemplo 1.5 (Cotas del código de Hamming original).Para empezar, 𝑚𝑉 (𝑡)=24𝑉(1) = 24[(7 0)+(7 1)]= 24⋅8=27=𝑞𝑛, luego el código de Hamming original es un código perfecto. Por otro lado, 𝑘+𝑑= 4 + 3 = 7 <8 = 𝑛+ 1, luego el código de Hamming original no es un código MDS. Terminemos la sección con una manera de construir códigos a partir de otros que nos será de utilidad en capítulos posteriores. Consideremos un código lineal  de tipo (𝑛, 𝑞𝑘, 𝑑)sobre un cuerpo de 𝑞elementos y con 𝑞=𝑟𝑚una potencia (donde 𝑟no es necesariamente un primo, lo importante es que es una potencia 𝑚-ésima). Supongamos que tenemos otro código lineal ′de tipo (𝑛′, 𝑟𝑚, 𝑑′)sobre un cuerpo de 𝑟elementos. 1. conceptos generales 17 si 𝑐(𝛼)=0, entonces 𝑐(𝛼2)=0y por tanto de hecho se tiene que 2=3={𝑐(𝑥) ∈ 𝔽2[𝑥]∕⟨𝑥𝑛− 1⟩|||𝑐(𝛼) = 𝑐(𝛼2)=0} Por lo que 2es un código de distancia mínima mayor o igual que 3a pesar de que su distancia prevista fuera 2. De hecho, es posible comprobar que, salvo reordenación de las variables, este código coincide con el código original de Hamming presentado en el ejemplo 2.1 siendo su distancia mínima exactamente 3. El estudio de la distancia real de los códigos BCH no es factible en general en la práctica por lo que se suele utilizar 𝜆normalmente como sustituto. Existen algunos casos particulares en los que sí se puede averiguar con precisión esta distancia, y esta sería la discusión que vendría a continuación, de tratar este documento sobre códigos BCH. Sin embargo, como se ha dicho anteriormente, solo introducimos estos códigos para motivar los códigos de Goppa que vendrán a continuación por lo que nos limitaremos a dar una referencia donde se puede encontrar un tratamiento más extenso sobre este caso (puede verse en [4]). 1.5 Códigos de Goppa clásicos Los códigos de Goppa4clásicos son una de las muchas generalizaciones de los códigos BCH. Para motivar su definición, recordemos que un código BCH (en sentido estricto, esto es 𝑏= 1) de longitud 𝑛y distancia prevista 𝜆está definido como ={(𝑐0,…, 𝑐𝑛−1)∈𝔽𝑛 𝑞||| 𝑛−1 ∑ 𝑖=0 𝑐𝑖(𝛼𝑗)𝑖= 0,1≤𝑗≤𝜆− 1} Supongamos entonces la factorización de 𝑥𝑛− 1 en una extensión adecuada de 𝔽𝑞 es 𝑥𝑛− 1 = (𝑥−𝛼)⋯(𝑥−𝛼−1)⋯(𝑥− 1). Dividiendo esta expresión por 𝑥−𝛼−𝑖se obtiene que 𝑥𝑛− 1 𝑥−𝛼−𝑖= 𝑛−1 ∑ 𝑘=0 (𝛼−𝑖)𝑛−1−𝑘𝑥𝑘= 𝑛−1 ∑ 𝑘=0 𝛼𝑖(𝑘+1)𝑥𝑘, 4En honor de Valery Denisovich Goppa, matemático ruso nacido en 1939 que los introdujo por primera vez. 18 códigos goppa donde simplemente hemos desarrollado el producto y agrupado términos. Ahora bien, si (𝑐0,…, 𝑐𝑛−1) ∈ 𝔽𝑛 𝑞, multiplicando por 𝑐𝑖y sumando en 𝑖se tiene que 𝑛−1 ∑ 𝑖=0 𝑐𝑖 𝑥−𝛼−𝑖=1 𝑥𝑛− 1 𝑛−1 ∑ 𝑖=0 𝑐𝑖 𝑛−1 ∑ 𝑘=0 𝛼𝑖(𝑘+1)𝑥𝑘 si (𝑐0,…, 𝑐𝑛−1)fuera una palabra del código, los términos de la derecha de grado me- nor o igual a 𝜆− 1 se cancelarían obteniéndose así que lo restante es un múltiplo de 𝑥𝜆−1 esto es: 𝑛−1 ∑ 𝑖=0 𝑐𝑖 𝑥−𝛼−𝑖=𝑥𝜆−1𝑝(𝑥) 𝑥𝑛− 1 para un cierto polinomio 𝑝(𝑥). Esto es, si la palabra está en el código, se tiene que ∑𝑛−1 𝑖=0 𝑐𝑖∕(𝑥−𝛼−𝑖)escrita como función racional 𝑝(𝑥)∕𝑞(𝑥)tiene numerador divisible por 𝑥𝜆−1. Esto también funciona en la dirección contraria, pues caso de ser tener esta suma escrita como función racional denominador múltiplo de 𝑥𝜆−1, observando el término de la derecha se tendría que los términos correspondientes a grado de 𝑥menor a𝜆− 1 se anularían lo que implica que la palabra está en el código. Generalizamos esta observación para introducir la definición de código de Goppa clásico: Definición 1.14 (Código de Goppa clásico). Sea 𝑔(𝑥)un polinomio mónico sobre 𝔽𝑞𝑚de grado 𝑡sin raíces dobles y 𝐿= {𝛾0,…, 𝛾𝑛−1}⊆𝔽𝑞𝑚tal que 𝑔(𝛾𝑖)≠0, para cada 0≤𝑖≤𝑛− 1. El código de Goppa clásico de parámetros 𝐿y𝑔(denotado como Γ(𝐿, 𝑔)) es el conjunto de palabras (𝑐0,…, 𝑐𝑛−1) ∈ 𝔽𝑛 𝑞tales que 𝑛−1 ∑ 𝑖=0 𝑐𝑖 𝑥−𝛾𝑖 ≡0 m od 𝑔(𝑥). Claramente así definidos, los códigos de Goppa clásicos son códigos lineales de longitud 𝑛. Además, por la condición de que 𝑔(𝛾𝑖)≠0, el elemento 𝑥−𝛾𝑖será invertible en el anillo 𝔽𝑞𝑚[𝑥]∕⟨𝑔(𝑥)⟩. En concreto 1 𝑥−𝛾𝑖 =−1 𝑔(𝛾𝑖)(𝑔(𝑥) − 𝑔(𝛾𝑖) 𝑥−𝛾𝑖) Por tanto, debemos entender 1∕(𝑥−𝛾𝑖)como la única clase del anillo 𝔽𝑞𝑚[𝑥]∕⟨𝑔(𝑥)⟩, pongamos 𝑓(𝑥), tal que (𝑥−𝛾𝑖)𝑓(𝑥)≡1 m  od 𝑔(𝑥). 1. conceptos generales 19 Observación 1.6.En general los códigos de Goppa clásicos no son cíclicos. Sí lo son en el caso en el que 𝑔(𝑥) = 𝑥𝜆−1 y𝐿= {𝛼−𝑖|0≤𝑖≤𝑛− 1} pues, como hemos observado anteriormente, coincide con un código BCH en sentido estricto. Observación 1.7.Si 𝑔(𝑥)es un polinomio irreducible (o sea, 𝑡 > 1), entonces la condición 𝑔(𝛾𝑖)≠0se verifica siempre. Tratemos de dar una matriz de control para un código de Goppa clásico. Digamos que 𝑔(𝑥) = 𝑔0+𝑔1𝑥+…+𝑔𝑡𝑥𝑡. Recordando que 1 𝑥−𝛾𝑖 =−1 𝑔(𝛾𝑖)(𝑔(𝑥) − 𝑔(𝛾𝑖) 𝑥−𝛾𝑖), tenemos que 𝑔(𝑥) − 𝑔(𝛾𝑖) 𝑥−𝛾𝑖 =𝑔𝑡(𝑥𝑡−1 +𝑥𝑡−2𝛾𝑖+…+𝛾𝑡−1 𝑖)+…+𝑔2(𝑥+𝛾𝑖)+𝑔1 dividiendo por −𝑔(𝛾𝑖)para obtener la inversa de 𝑥−𝛾𝑖, podemos comprobar que una matriz de control para un código de Goppa clásico es: 𝐴= ⎛⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝ −𝑔𝑡 𝑔(𝛾0)…−𝑔𝑡 𝑔(𝛾𝑛−1) −(𝑔𝑡−1 +𝑔𝑡𝛾0) 𝑔(𝛾0)…−(𝑔𝑡−1 +𝑔𝑡𝛾𝑡−1) 𝑔(𝛾𝑛−1) ⋮ ⋮ −(𝑔1+𝑔2𝛾0+…+𝑔𝑡𝛾𝑡−1 0) 𝑔(𝛾0)…−(𝑔1+𝑔2𝛾𝑛−1 +…+𝑔𝑡𝛾𝑡−1 𝑛−1) 𝑔(𝛾𝑛−1) ⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠ Observación 1.8.Al igual que pasaba en los códigos BCH, esta matriz no es una matriz de control en el sentido clásico pues no tiene coeficientes en 𝔽𝑞en general. Sin embargo, si se sustituye cada entrada de la matriz por un vector columna tomando coordenadas en el cuerpo base se obtendría, tras eliminar filas redundantes, una matriz de control real del código. 20 códigos goppa Además, esta matriz puede escribirse como el producto de las matrices 𝐴=⎛⎜⎜⎜⎜⎝ 𝑔𝑡0⋯0 𝑔𝑡−1 𝑔𝑡⋯0 ⋮ ⋮ ⋱ ⋮ 𝑔0𝑔1⋯𝑔𝑡 ⎞⎟⎟⎟⎟⎠ ⎛⎜⎜⎜⎜⎝ 1 1 ⋯1 𝛾0𝛾1⋯𝛾𝑛−1 ⋮ ⋮ ⋱ ⋮ 𝛾𝑡−1 0𝛾𝑡−1 1⋯𝛾𝑡−1 𝑛−1 ⎞⎟⎟⎟⎟⎠ ⎛⎜⎜⎜⎜⎝ 𝑔(𝛾0)−1 𝑔(𝛾1)−1 ⋱ 𝑔(𝛾𝑛−1)−1 ⎞⎟⎟⎟⎟⎠ Como la matriz de la izquierda es invertible (𝑔𝑡≠0), podemos tomar el producto de las otras dos como matriz de control del código. Esto es, una matriz de control de un código de Goppa clásico sería: 𝐻=⎛⎜⎜⎜⎜⎝ 𝑔(𝛾0)−1 𝑔(𝛾1)−1 ⋯𝑔(𝛾𝑛−1)−1 𝛾0𝑔(𝛾0)−1 𝛾1𝑔(𝛾1)−1 ⋯𝛾𝑛−1𝑔(𝛾𝑛−1)−1 ⋮ ⋮ ⋱ ⋮ 𝛾𝑡−1 0𝑔(𝛾0)−1 𝛾𝑡−1 1𝑔(𝛾1)−1 ⋯𝛾𝑡−1 𝑛−1𝑔(𝛾𝑛−1)−1 ⎞⎟⎟⎟⎟⎠ Gracias a esta matriz de control, podemos dar una cota de la distancia mínima y la dimensión de los códigos de Goppa clásicos. Proposición 1.9 (Parámetros de los códigos de Goppa clásicos).Si es un código de Goppa clásico Γ(𝐿, 𝑔), se tiene que: 1) 𝑘= dim𝔽𝑞()≥𝑛−𝑚𝑡, 2) 𝑑=𝑑()≥𝑡+ 1, donde 𝑡es el grado de 𝑔(𝑥) ∈ 𝔽𝑞𝑚[𝑥]. Demostración. Si sustituimos en 𝐻cada término por un vector columna tomando coordenadas en una base de 𝔽𝑞𝑚como 𝔽𝑞-espacio vectorial, obtenemos tras eliminar filas redundantes, una matriz de control en el sentido clásico de . Esta matriz tendría dimensiones 𝑝×𝑛con 𝑝≤𝑚𝑡 lo que prueba el primer apartado (pues la dimensión sería 𝑛−𝑝≥𝑛−𝑚𝑡). La cota de la distancia mínima puede deducirse rápidamente de la definición ya que, como el código es lineal su distancia mínima coincide con el mínimo peso de las palabras del código. Por tanto, si 𝑐∈tiene peso 𝑤, en la expresión 𝑛−1 ∑ 𝑖=0 𝑐𝑖 𝑥−𝛾𝑖 ≡0 m od 𝑔(𝑥) 1. conceptos generales 21 podemos tomar su expresión racional quedando así en el numerador un polinomio de grado a lo más 𝑤−1 (puesto que el el numerador aparecerían los productos de los 𝑐𝑖no nulos por el resto de los 𝑥−𝛼𝑗correspondientes a 𝑐𝑗no nulos) y en el denominador un producto de polinomios de grado 1que sabemos que no influyen para ver si el polinomio es 0módulo 𝑔(𝑥). Por tanto, como 𝑔es mónico de grado 𝑡, la única manera de que un polinomio de grado 𝑤− 1 sea 0módulo 𝑔(𝑥)es que 𝑤− 1 ≥𝑡probando así la desigualdad de la distancia. En el caso en el que el cuerpo base es 𝔽2se puede mejorar la cota de la distancia. Hemos de introducir un lema previo. Lema 1.1.Sea 𝑓(𝑥) = ∏𝑛 𝑖=1(𝑥−𝑎𝑖)𝑏𝑖. Entonces el cociente de su derivada formal por sí mismo es 𝑓′(𝑥) 𝑓(𝑥)= 𝑛 ∑ 𝑖=1 𝑏𝑖 𝑥−𝑎𝑖 . Demostración. Por la derivada del producto para 𝑛funciones se tiene que 𝑓′(𝑥) = 𝑛 ∑ 𝑘=1 𝑏𝑘(𝑥−𝑎𝑘)𝑏𝑘−1 ∏ 𝑖≠𝑘 (𝑥−𝑎𝑖)𝑏𝑖 Dividiendo esta expresión por 𝑓(𝑥)se cancelan todos los términos para cada 𝑘fijo menos los correspondientes al propio 𝑥−𝑎𝑘en el que queda 𝑏𝑘∕(𝑥−𝑎𝑘)probando así el resultado. Proposición 1.10.Sea = Γ(𝐿, 𝑔)un código de Goppa clásico definido sobre 𝔽2. Entonces 𝑑()≥2𝑡+1 (luego su capacidad de corrección es, al menos, el grado de 𝑔). Demostración. Sea 𝐜= (𝑐0,…, 𝑐𝑛−1)una palabra de no nula. Sea así mismo 𝑓(𝑥) = ∏𝑛−1 𝑖=0 (𝑥−𝛾𝑖)𝑐𝑖. Por el lema anterior, 𝑛−1 ∑ 𝑖=0 𝑐𝑖 𝑥−𝛾𝑖 =𝑓′(𝑥) 𝑓(𝑥) ahora bien, el polinomio 𝑓′(𝑥)solo posee monomios de potencias pares ya que el cuerpo base es de característica 2(y por tanto la derivada de los monomios de exponente par se anula). Teniendo en cuenta que además en característica 2se tiene que (𝑎+𝑏)2=𝑎2+𝑏2, podemos expresar 𝑓′(𝑥) = 𝑝2(𝑥)para algún polinomio 𝑝. Ahora bien, 𝑓es invertible módulo 𝑔(𝑥)y por tanto para que esta palabra esté en el código (y dado que no es nula) debe tenerse que 𝑔(𝑥)divide a 𝑓′(𝑥) = 𝑝2(𝑥). Ahora bien, 𝑔 no tiene raíces múltiples y por tanto 𝑔2(𝑥)divide a 𝑓′(𝑥), por lo que, por el mismo 22 códigos goppa razonamiento que hemos hecho en la prueba anterior para la distancia, 𝑤(𝐜)−1≥2𝑡 lo que prueba el enunciado. Terminemos la sección con un ejemplo de código de Goppa clásico. Será un ejemplo simple extraído de [5]. Ejemplo 1.7.Sea 𝔽24el cuerpo representado por el cociente 𝔽2[𝑥]∕⟨𝑥4+𝑥+ 1⟩. Denotemos por 𝛼el generador de 𝔽∗ 24. Queremos tener la máxima dimensión posible del código por tanto, en virtud de la proposición 1.9 escogemos tantas raíces como podamos. Por ejemplo sea 𝐿= {𝛼𝑖∣ 2 ≤𝑖≤13} y tomemos 𝑔(𝑥) = (𝑥+𝛼)(𝑥+𝛼14). En tal caso, como 𝑔no se anula en 𝐿, podemos considerar = Γ(𝐿, 𝑔). Estimando sus parámetros con 1.9, tenemos que 𝑘≥13 − 8 = 5 y𝑑≥3. Si queremos obtener una matriz de control para , tenemos que evaluar 𝑔en cada una de los elementos de 𝐿e ir calculando sus inversos. Por ejemplo, 𝑔(𝛼2)−1 = (𝛼4+ 𝛼9+ 1)−1. Reduciendo módulo 𝛼4+𝛼+ 1 tenemos que 𝛼4+𝛼9+ 1 = 𝛼9+𝛼=𝛼(𝛼4)2+𝛼=𝛼(𝛼+ 1)2+𝛼=𝛼(𝛼2+ 1) + 𝛼=𝛼3 por tanto obtenemos que (𝛼4+𝛼9+ 1)−1 = (𝛼3)−1 =𝛼12. Haciendo esto para todos los elementos de 𝐿obtenemos que una matriz de control sería 𝐻=(𝛼9𝛼10 𝛼9𝛼14 𝛼60𝛼10 𝛼8𝛼2𝛼7𝛼14 𝛼6 𝛼12 𝛼6𝛼6𝛼 𝛼11 1𝛼14 𝛼8𝛼11 𝛼14 𝛼12 𝛼) Por último, podemos hacer la identificación de estos elementos con la base {1, 𝛼, 𝛼2, 𝛼3} para obtener una matriz de control en el sentido clásico obteniendo: 𝐻= ⎛⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝ 010100110110 111000100100 010010111001 101110000111 100001110110 100110001011 111010011010 111010101110 ⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠ . 2 Preludio de curvas algebraicas Para introducir los códigos de Goppa algebraico geométricos, es necesario utilizar resultados de geometría algebraica sobre cuerpos que no son algebraicamente cerrados. Introducir estos conceptos con generalidad ocuparía demasiada extensión y no es el onjetivo de este trabajo. Sin embargo, en el caso concreto del estudio de las curvas, es posible dar un enfoque particular mucho más sencillo que relaja los prerrequisitos para entender la materia. Nuestro objetivo será mostrar los conceptos con los que vamos a trabajar y tendremos que asumir, por desgracia, algunos resultados como ciertos para que la extensión del trabajo no sea excesiva. En esta sección daremos por conocidos los resultados obtenidos sobre geometría algebraica en cuerpos algebraicamente cerrados de la asignatura Álgebra Conmutativa y Geometría Algebraica (ACGA en lo sucesivo) del grado en matemáticas. 2.1 Anillos de valoración Veamos algunos resultados adicionales sobre variedades de dimensión uno que se obtienen directamente de los resultados ya conocidos de geometría algebraica, para el caso de cuerpos algebraicamente cerrados (por ahora, al menos). Comencemos caracterizando la singularidad para el caso particular de las curvas en función de su anillo local. Como ser regular es una propiedad local, podemos asumir en principio que nuestra curva es afín. Proposición 2.1.Sea 𝑋una curva sobre un cuerpo algebraicamente cerrado 𝑘. Entonces un punto 𝑃∈𝑋es no singular si y solo si el único ideal maximal 𝔪𝑃del anillo local de las funciones racionales definidas en 𝑃,𝑃, es principal. Demostración. Basta recordar que el que 𝑃sea no singular es equivalente a que 𝑃 24 códigos goppa sea un anillo regular, es decir, su ideal maximal puede ser generado con tantos elementos como su dimensión de Krull. Como 𝑋es de dimensión 1, significa que 𝔪𝑃=𝑡𝑝𝑃 para algún 𝑡𝑝∈𝑃. Definición 2.1. En las condiciones anteriores, a un generador del ideal maximal 𝑡𝑝 lo llamaremos un parámetro local (o parámetro de uniformización) de la curva en 𝑃. Ejemplo 2.1.Sea 𝑋=(𝑓), con 𝑓∈𝑘[𝑥, 𝑦], una curva y, sin pérdida de generalidad, supongamos que 𝑃= (0,0) ∈ 𝑋es un punto no singular, sabemos entonces que 𝑃=(𝑘[𝑥, 𝑦]∕⟨𝑓⟩)⟨𝑥,𝑦⟩ es el localizado del anillo de funciones regulares en el ideal maximal del punto 𝑃. Ahora bien, decir que 𝑃= (0,0) ∈ 𝑋es equivalente a que 𝑓no tenga término constante. Como además es no singular, alguna de las derivadas parciales no se anula. Supongamos, de nuevo sin pérdida de generalidad, que 𝜕𝑓∕𝜕𝑥 ≠0, esto es, 𝑓tiene término lineal en 𝑥no nulo. En tal caso, como 𝑓= 0 ∈ 𝑘[𝑥, 𝑦]∕⟨𝑓⟩, y por ser su término lineal no nulo, podemos expresar, a partir de 𝑓= 0 y, extrayendo factor común 𝑥si es necesario 𝑥=𝑢(𝑥, 𝑦)⋅𝑔(𝑥, 𝑦)⋅𝑦, para algunos 𝑔(𝑥, 𝑦) ∈ 𝑘[𝑥, 𝑦]y𝑢(𝑥, 𝑦) ∈ ∗ 𝑃 y por tanto, en 𝑃,𝑥∈⟨𝑦⟩, lo que prueba que ⟨𝑥, 𝑦⟩=⟨𝑦⟩por lo que 𝑦es un parámetro local. A partir de ahora supondremos que tratamos con un punto 𝑃∈𝑋no singular para hacer un estudio local. Nuestro siguiente objetivo es ver que podemos expresar cualquier función regular en 𝑃en función de nuestro parámetro local 𝑡𝑝. Este resultado no es difícil de probar pero daremos antes una definición previa para mostrar que la razón de que esto sea así es debido a que 𝑃es un anillo de valoración (discreta, para ser precisos). Definición 2.2. Sea 𝐵un dominio de integridad y sea 𝐾su cuerpo de fracciones. 𝐵 es un anillo de valoración de 𝐾si para cada 𝑥∈𝐾no nulo, se tiene que 𝑥∈𝐵o que 𝑥−1 ∈𝐵. Ejemplo 2.2.El anillo ℤno es un anillo de valoración de ℚ. Observación 2.1.No es difícil ver entonces que 𝑃es un anillo de valoración ya que su cuerpo de fracciones es el cuerpo de funciones racionales (𝑋). Esto se debe a 2. preludio de curvas algebraicas 25 que 𝑃contiene al anillo de funciones regulares (𝑋)y el cuerpo de fracciones de este es (𝑋), que contiene a 𝑃. Además sabemos que 𝑃es el localizado de (𝑋) en el ideal maximal asociado a 𝑃,𝔪𝑝, luego una función racional de (𝑋)o está bien definida en 𝑃o su inversa se anula en 𝑃(y por tanto está bien definida) por la definición de localizado. Además, como se vio en ACGA (ejercicio 9.7), todo anillo de valoración es un anillo local lo cual ya sabíamos en el caso particular de 𝑃. Podemos ahora probar con mayor fluidez el siguiente resultado: Proposición 2.2.Sea 𝑓∈(𝑋). Entonces 𝑓tiene una única representación de la forma 𝑓=𝑡𝑟𝑢para 𝑟∈ℤy𝑢∈∗ 𝑃. Demostración. Para la existencia, como 𝑃contiene a 𝑓o a 𝑓−1 y𝑟∈ℤ, asumamos, sin pérdida de generalidad que 𝑓∈𝑃. Si 𝑓∈∗ 𝑃,𝑓=𝑡0𝑓. En caso contrario, existe un máximo 𝑚≥1tal que 𝑓∈𝑡𝑚𝑃 ya que 𝑓puede representarse localmente como un cociente de polinomios. Escribiendo 𝑓=𝑡𝑚𝑢con 𝑢∈𝑃,𝑢debe ser una unidad ya que en caso de no serlo estaría en 𝔪𝑝=𝑡𝑃contradiciendo a que 𝑚sea máximo. La unicidad está clara, usando que 𝑢es una unidad. En esta prueba hemos visto que a cualquier función racional en la curva, le podemos asociar un único número entero directamente asociado con un parámetro local de la curva en 𝑃. Es decir, que tenemos una aplicación que identifica a nuestras funciones definidas en 𝑃salvo unidad asociándoles un número entero. Esto motiva la siguiente definición 1. Definición 2.3. Sea 𝑅una 𝑘-álgebra. Una valoración discreta (o valuación discreta) sobre 𝑅es una aplicación 𝑣∶𝑅→ℤ∪ {∞} que verifica: 𝑣(𝑥)=∞ ⇐⇒ 𝑥= 0. 𝑣(𝑥𝑦) = 𝑣(𝑥) + 𝑣(𝑦) ∀𝑥, 𝑦 ∈𝑅. 𝑣(𝑥+𝑦)≥m ın{𝑣(𝑥), 𝑣(𝑦)} ∀𝑥, 𝑦 ∈𝑅(Desigualdad triangular). Existe un elemento 𝑧∈𝑅con 𝑣(𝑧)=1. 𝑣(𝑎)=0,∀𝑎∈𝑘. 1Pueden encontrarse otras definiciones similares pero no exactamente iguales de valoración discreta; esta será la que usemos en esta memoria 26 códigos goppa En este contexto, ∞es un elemento que verifica que ∞+∞ = ∞+𝑛=𝑛+∞ = ∞ y∞> 𝑚 para todos 𝑚, 𝑛 ∈ℤ. De la segunda y la cuarta propiedad se sigue que 𝑣∶𝐹→ℤ∪ {∞} es sobreyectiva. Con esta terminología, si a cada función racional en nuestra curva le asociamos el entero correspondiente a su representación en función de un parámetro local, tenemos una valoración discreta en (𝑋). Al número entero 𝑚que le asociamos le llamamos orden de la función en 𝑃. Si 𝑚 > 0diremos que 𝑃es un cero de 𝑓, y si 𝑚 < 0diremos que es un polo. Los nombres están justificados ya que si 𝑓=𝑡𝑚𝑢con 𝑡∈𝑚𝑝y𝑢∈𝑃, como 𝑢es invertible localmente en 𝑃, es el parámetro local 𝑡lo que marca si 𝑓es un cero o un polo dependiendo del signo de 𝑚. Además notemos que este número 𝑚no depende del parámetro local escogido ya que si 𝑡′es otro parámetro local con 𝑡=𝑡′, entonces deben diferenciarse en una unidad y por tanto la valoración de una función arbitraria 𝑓no cambia. Para hablar de la valoración de una función racional 𝑓en un punto 𝑃∈𝑋, se usarán indistintamente las notaciones 𝑣𝑃(𝑓)uord𝑃(𝑓). Ejemplo 2.3.Consideremos la curva dada por 𝑋=(ℎ)con ℎ=𝑥3𝑦+𝑦3+𝑥 conocida como cuártica de Klein afín. Como la parcial con respecto a 𝑥es no nula, 𝑦es un parámetro local de la curva en 𝑃= (0,0). Calculemos la valoración de la función 𝑓=𝑥3+𝑦3en 𝑃. Procediendo como en el ejemplo anterior, 𝑥=𝑦(−𝑥3−𝑦2)y por tanto sustituyendo en nuestra función regular: 𝑓=𝑥3+𝑦3=𝑦3(−𝑥3−𝑦2)3+𝑦3=𝑦3((−𝑥3−𝑦2)3+ 1) Como (−𝑥3−𝑦2)3+ 1 no se anula en 𝑃, es una unidad en nuestro anillo local y por tanto la valoración de 𝑓en 𝑃, es 𝑣𝑃(𝑓)=3. Las valoraciones discretas nos ayudan a describir una biyección que será en la que nos basaremos para extender nuestro entendimiento de curvas sobre cuerpos algebraicamente cerrados a cuerpos arbitrarios. En concreto, notemos que que podemos describir el anillo local 𝑃en función de la valoración como: 𝑃={𝑓∈(𝑋)|𝑣(𝑓) ∈ ℤ≥0∪ {∞}}. Observación 2.2.Es fácil comprobar que de hecho los elementos de valoración mayor o igual a cero forman un anillo de valoración dando sentido a la terminología del anillo. A este anillo lo llamaremos anillo de valoración asociado a 𝑣. 2. preludio de curvas algebraicas 33 (a)  𝑘 ⊆ y 𝑘∩𝑃= {0}. (b) 𝑃es un ideal principal. (c) Si 𝑃=𝑡, entonces cualquier elemento 𝑓∈𝐾tiene una única representación de la forma 𝑓=𝑡𝑛𝑢con 𝑛∈ℤy𝑢∈∗. En particular, el entero 𝑛no depende de la elección de 𝑡. Demostración. (a) Si 𝑥∈ 𝑘pero 𝑥∉, entonces 𝑥−1 ∈por ser local. Como 𝑥−1 es algebraico sobre 𝑘, existen 𝑎0, 𝑎1,…, 𝑎𝑛∈𝑘tales que 𝑎0+𝑎1𝑥−1 + …𝑎𝑛𝑥−𝑛= 0 por lo que 𝑧=−𝑎𝑛(𝑥−1)𝑛−1 −…−𝑎1 𝑎0 ∈, donde hemos usado que 𝑎0≠0puesto que el polinomio lo podemos tomar irreducible. Como 𝑃no puede contener unidades se tiene que  𝑘∪𝑃= {0}. (b) Si 𝑃no es principal, existen elementos no nulos 𝑥1, 𝑥2∈𝑃con 𝑃≠𝑥1y 𝑥2∈𝑃⧵𝑥1. En tal caso, 𝑥2𝑥−1 1∉y por tanto 𝑥−1 2𝑥1∈𝑃por ser un elemento no invertible en . Obtendríamos por tanto que 𝑥1∈𝑥2𝑃. Podemos por tanto hacer un proceso inductivo en el que encontraríamos una sucesión infinita {𝑥𝑖|𝑖∈ℕ}tales que 𝑥𝑖∈𝑥𝑖+1𝑃para todo 𝑖. La demostración de que esto no puede ocurrir se da a través de un lema técnico que vendrá a continuación que nos limitamos a citar ya que no es de mayor interés salvo para esta prueba. (c) La prueba de este punto es parecida a la del caso en el que el cuerpo 𝑘es algebraicamente cerrado (ver proposición 2.2) pero hay que justificar que existe un máximo 𝑚≥1tal que cualquier 𝑓∈𝐾verifica que 𝑓∈𝑡𝑚en el caso que nos ocupa. Esto se hace a través del lema técnico siguiente que cierra la prueba. Lema 2.3.Sea un anillo de valoración de un cuerpo de funciones algebraicas 𝐾. Sea 𝑃su ideal maximal y sea 𝑥≠0 ∈ 𝑃. Sean 𝑥1,…, 𝑥𝑛∈𝑃que verifiquen que 𝑥1=𝑥y𝑥𝑖∈𝑥𝑖+1𝑃, entonces 𝑛≤[𝐾∶𝑘(𝑥)] <∞. Demostración. La prueba puede encontrarse en [6] o en [7]. Introducimos ahora el concepto de lugar, el cual hará el papel de los puntos en el caso en el que 𝑘no sea algebraicamente cerrado. Definición 2.10. Un lugar 𝑃de un cuerpo de funciones 𝐾sobre 𝑘es el ideal maximal de cualquier anillo de valoración de 𝐾. Cualquier elemento 𝑡∈𝑃tal que 𝑃=𝑡se dice que es un parámetro local (o parámetro de uniformización) en 𝑃. El conjunto de todos los lugares de 𝐾se denotará2por ℙ𝑛(𝐾). 2No confundir con la notación de espacio proyectivo, ℙ𝐾. 34 códigos goppa Observación 2.7.El punto (c) del teorema 3.8prueba que todo anillo de valoración ⊆ 𝐾 es de hecho un anillo de valoración discreta. A la valoración discreta que arroja (c) en el punto 𝑃la denotaremos por 𝑣𝑃igual que en la sección anterior. Observación 2.8.Un anillo de valoración queda unívocamente determinado por su ideal maximal 𝑃, en concreto, = {𝑓∈𝐾|𝑓−1 ∉𝑃}. A este anillo se le denotará por 𝑃y le llamaremos el anillo de valoración en el lugar 𝑃. Ejemplo 2.8.Si 𝑝(𝑥) ∈ 𝑘[𝑥]es un polinomio irreducible y consideramos la aplicación 𝑣𝑝(𝑥)∶𝑘(𝑥)→ℤ∪ {∞} definida como: Si 𝑓(𝑥) ∈ 𝑘[𝑥]es no nulo, 𝑣𝑝(𝑥)(𝑓) = 𝑚, donde 𝑚es la mayor potencia de 𝑝(𝑥) que divide a 𝑓(𝑥). Si 𝑓(𝑥)∕𝑔(𝑥) ∈ 𝑘(𝑥),𝑣𝑝(𝑥)(𝑓∕𝑔) = 𝑣𝑝(𝑥)(𝑓) − 𝑣𝑝(𝑥)(𝑔). 𝑣𝑝(𝑥)(0) = ∞. Entonces 𝑣𝑝(𝑥)es una valoración discreta que define un lugar 𝑃que es el conjunto de todas las funciones racionales 𝑓(𝑥)∕𝑔(𝑥) ∈ 𝑘(𝑥)tales que 𝑝(𝑥)divide a 𝑓(𝑥)pero 𝑝(𝑥)no divide a 𝑔(𝑥). Observación 2.9.Si 𝑘es algebraicamente cerrado y 𝑋es una curva proyectiva sin puntos singulares, el teorema 2.1 dice que existe una correspondencia biyectiva entre los puntos 𝑃∈𝑋y los lugares de 𝐾=(𝑋). Al igual que en el caso de tratar con curvas proyectivas, diremos que una función 𝑓∈𝐾tiene un cero en 𝑃si la valoración en 𝑃es positiva y diremos que tiene un polo en 𝑃si la valoración en 𝑃es negativa. Por último, diremos que 𝑓está definida en 𝑃si su valoración es no negativa. En términos de la valoración podemos describir los conjuntos: 𝑃= {𝑓∈𝐾|𝑣𝑃(𝑓)>0},𝑃= {𝑓∈𝐾|𝑣𝑃(𝑓)≥0}. Como veremos en la siguiente sección, a la hora de tratar con una curva no singular sobre un cuerpo cualquiera, es conveniente pensar en sus puntos como los anillos de valoración de su cuerpo de funciones. En virtud de la observación 2.9, esta definición es equivalente a la que se da en geometría algebraica clásica. Definición 2.11 (Curva proyectiva no singular). Sea 𝑘un cuerpo y sea 𝐾un cuerpo de funciones sobre 𝑘. Una curva proyectiva no singular es un conjunto 𝑋que está en biyección con el conjunto de los anillos de valoración de 𝐾,Val(𝐾∕𝑘), tal que la intersección ∩𝑃∈Val(𝐾∕𝑘)𝑃=𝑘. 2. preludio de curvas algebraicas 35 La condición de que la intersección de los anillos de valoración del cuerpo de funciones sea el cuerpo base refleja la idea de que cualquier función racional definida en cualquier punto de una curva proyectiva debe ser constante. Esta definición da además sentido a la notación de los lugares por 𝑃puesto que estos están en correspondencia con los puntos de la curva que representa el cuerpo de funciones 𝐾. Hablemos por último de los cuerpos residuales de los anillos de valoración de 𝐾. Como sabemos, en el caso de que 𝐾=(𝑋)sea el cuerpo de funciones racionales de una curva proyectiva no singular sobre un cuerpo algebraicamente cerrado se estudió en ACGA que el cuerpo residual de cada uno de los anillos de valoración de 𝐾son isomorfos al cuerpo base 𝑘. En general, sin embargo, este cuerpo residual no tiene por qué coincidir con el cuerpo base sino que puede ser una extensión finita de este. Un ejemplo claro puede encontrarse fácilmente tomando 𝑘=ℝ,𝐾=𝑘(𝑥)y considerando la valoración del ejemplo 2.8 con 𝑝(𝑥) = 𝑥2+ 1. En tal caso, el cuerpo residual del anillo de valoración asociado a 𝑣𝑝(𝑥)es isomorfo a ℝ[𝑥]𝑥2+1 ⟨𝑥2+ 1⟩ℝ[𝑥]𝑥2+1 ≅ℝ[𝑥] ⟨𝑥2+ 1⟩≅ℂ. Al cuerpo residual del anillo de valoración 𝑃lo denotaremos por 𝑘𝑃. Proposición 2.4.La extensión 𝑘⊆𝑘𝑃es finita y su grado está acotado por el grado de la extensión de 𝐾sobre 𝑘(𝑥). Demostración. La prueba es una consecuencia del lema 2.3. Puede encontrarse en detalle en [7]. Definición 2.12. Al grado de la extensión [𝑘∶𝑘𝑃]lo llamaremos el grado del lugar 𝑃. Lo denotaremos por deg(𝑃). Por tanto, en el caso en el que 𝑘es algebraicamente cerrado, como 𝑘⊆𝑘𝑃es finita, 𝑘𝑃=𝑘para cualquier 𝑃, es decir el grado de cada lugar es 1. 2.4 Puntos racionales de una curva Cabe ahora considerar una pregunta que es natural plantearse a la hora de estudiar curvas algebraicas sobre cuerpos que no son algebraicamente cerrados. Digamos que 𝑘es un cuerpo cualquiera. Entonces podríamos haber considerado las curvas 𝑋=(ℎ1,…, ℎ𝑟),con ℎ1,…, ℎ𝑟∈𝑘[𝑥0,…, 𝑥𝑛] 36 códigos goppa de 𝑘como las curvas 𝑋definidas por las mismas ecuaciones que en su cierre algebraico 𝑘, pero cuyos puntos tengan todas las coordenadas en 𝑘. A estos puntos se les suele llamar puntos racionales de la curva 𝑋 ⊆ ℙ𝑛(𝑘)(sobrentendiendo quién es el cuerpo 𝑘, evidentemente). Teniendo en cuenta esta manera de extender los conceptos tan natural cabe preguntarse si existe alguna relación con la manera puramente algebraica de tratar con curvas que hemos visto en esta sección. La respuesta a esto es afirmativa. Recordemos que el teorema 2.1 nos decía que existía una correspondencia biyectiva entre los puntos de una curva y los lugares de su cuerpo de funciones cuando trabajamos sobre un cuerpo algebraicamente cerrado. En el caso en el que nuestro cuerpo 𝑘no sea algebraicamente cerrado tendremos que pedirle a 𝑘que sea un cuerpo perfecto, o equivalentemente, que toda extensión algebraica suya sea separable (cosa que sabemos que verifican los cuerpos finitos). En tal caso, los anillos de valoración de lo que definiremos como el cuerpo de funciones asociada a la curva, se corresponderán en este caso, no con un punto de la curva sino con un conjunto de puntos conjugados por la acción del grupo de Galois de la extensión 𝑘 ⊆ 𝑘 de la curva considerada sobre 𝑘. A partir de ahora supondremos que nuestras curvas son planas por simplicidad. Definición 2.13. Sea 𝑘un cuerpo. Una variedad proyectiva 𝑋sobre el cuerpo 𝑘o más brevemente, una 𝑘−variedad, 𝑋 ⊆ ℙ𝑛(𝑘)es el conjunto de ceros comunes de un conjunto de polinomios con coeficientes en 𝑘. En tal caso, dado un cuerpo 𝑘′tal que 𝑘⊆𝑘′⊆ 𝑘, denotamos por 𝑋(𝑘′)el conjunto de puntos racionales de la 𝑘−variedad 𝑋sobre el cuerpo 𝑘′. Esto es, el conjunto de puntos que admiten una representación3con todas las coordenadas en 𝑘′de la variedad 𝑋 ⊆ ℙ𝑛(𝑘). Dado un punto 𝑃∈𝑋, el cuerpo de definición de 𝑃sobre 𝑘es el menor cuerpo intermedio 𝑘′generado por unas coordenadas de 𝑃. En otras palabras, es el menor cuerpo 𝑘′en el que 𝑃es un punto racional. Ejemplo 2.9.La cuártica de Klein dada por (𝐹)⊂ℙ2con 𝐹=𝑥3𝑦+𝑦3𝑧+𝑧3𝑥es una 𝑘−variedad para cualquier cuerpo base 𝑘. Tomemos 𝑘=𝑘′=𝔽2, entonces 𝑋(𝑘′) consta de solamente 3puntos: (0 ∶ 0 ∶ 1),(0 ∶ 1 ∶ 0) y(1 ∶ 0 ∶ 0). Definición 2.14. Sean 𝑘 ⊆ 𝑘 en las condiciones anteriores. Definimos el grupo de Galois, Gal(𝑘∕𝑘)(también conocido como el grupo absoluto de Galois) como el conjunto de los automorfismos de 𝑘que dejan invariante a 𝑘. 3Dado que un punto proyectivo puede venir dado por varias (𝑛+ 1)-uplas de coordenadas proyectivas. 2. preludio de curvas algebraicas 37 En el caso de que 𝑘=𝔽𝑞sea un cuerpo finito, el grupo absoluto de Galois se puede describir explícitamente, esto se hace con detalle en el material adicional (ver 4.4). El grupo de Galois actúa de manera natural sobre el espacio ℙ2(𝑘)de manera que 𝜎(𝑝0∶𝑝1∶𝑝2)=(𝜎(𝑝0) ∶ 𝜎(𝑝1) ∶ 𝜎(𝑝2)). En tal caso, está claro que, por construcción, 𝑋(𝑘′) = {𝑥∈𝑋|𝜎(𝑥) = 𝑥, ∀𝜎∈ Gal(𝑘∕𝑘′)} y que además, si 𝑃∈𝑋, el cuerpo de definición de 𝑃es precisamente 𝑘𝐺𝑃donde 𝐺𝑃= {𝜎∈ Gal(𝑘∕𝑘)|𝜎(𝑃) = 𝑃}es el subgrupo denominado estabilizador de 𝑃. Utilizando teoría de Galois se puede deducir entonces que si 𝑘es un cuerpo perfecto, entonces la órbita de cada punto 𝑃∈𝑋tiene exactamente [𝑘𝐺𝑃∶𝑘]puntos distintos. Digamos ahora que tenemos una curva plana sobre un cuerpo arbitrario 𝑘descrita por 𝐹∈𝑘[𝑥0, 𝑥1, 𝑥2]homogéneo. Esto es, 𝑋=(𝐹). A partir de ahora supondremos que 𝐹es totalmente irreducible, es decir, no solo 𝐹es irreducible en 𝑘sino también en 𝑘lo cual hará que podamos trabajar con su cuerpo de funciones sobre 𝑘. Así definida, la acción del grupo de Galois sobre ℙ2(𝑘)se restringe a una acción sobre la curva 𝑋ya que 𝐹tiene coeficientes en 𝑘luego 𝐹(𝜎(𝑃)) = 𝜎(𝐹(𝑃)) = 𝜎(0) = 0 para cualquier 𝑃∈𝑋. Como además 𝐹es totalmente irreducible, podemos considerar (𝑋)su cuerpo de funciones y denotaremos análogamente por (𝑋)al conjunto de cocientes de polinomios homogéneos del mismo grado con coeficientes en 𝑘. Exactamente igual que en el caso en el que 𝑘es algebraicamente cerrado, (𝑋)es un cuerpo de grado de trascendencia 1sobre 𝑘y además (𝑋)⊆(𝑋). Si denotamos por Val(∕𝑘)el conjunto de anillos de valoración de un cuerpo de funciones algebraicas sobre 𝑘, entonces podemos obtener los anillos de valoración de (𝑋)a través de los anillos de valoración de (𝑋)como: 𝐼𝑣𝑎𝑙 ∶ Val ((𝑋)∕𝑘)←→ Val((𝑋)∕𝑘) ←→ ∩𝑘(𝑋𝐹). Además, siguiendo la analogía que teníamos para un cuerpo algebraicamente cerrado, la aplicación 𝑃→𝑃de 𝑋en Val((𝑋)∕𝑘)es una biyección según el teorema 2.1. Es decir, teníamos una biyección entre los anillos de valoración del cuerpo de funciones de la curva y los puntos de la misma. Llamaremos a esta aplicación biyectiva 38 códigos goppa 𝐼𝑘. En el caso en el que 𝑘no sea algebraicamente cerrado, tenemos que esta biyección es entre los anillos de valoración de su cuerpo de funciones y las órbitas de cada punto según Gal(𝑘∕𝑘). Es decir, hay una biyección: 𝐼𝑘∶𝑋∕ Gal(𝑘∕𝑘)←→ Val((𝑋)∕𝑘) órbita de 𝑃←→ 𝑃∩(𝑋) Todo esto se resume en este teorema: Teorema 2.4 (Correspondencia entre puntos conjugados y anillos de valoración). Sea 𝑘un cuerpo y 𝐹∈𝑘[𝑥0, 𝑥1, 𝑥2]un polinomio homogéneo. Supongamos que 𝑋=(𝐹)⊆ℙ2(𝑘)es una curva no singular. Entonces 𝐼𝑘esá bien definido, es biyectivo y el siguiente diagrama es conmutativo: 𝑋Val((𝑋∕𝑘)) 𝑋∕ Gal(𝑘∕𝑘) Val((𝑋∕𝑘)) 𝐼𝑘 𝐼𝑣𝑎𝑙 𝐼𝑘 Además, el cuerpo de definición de 𝑃∈𝑋es precisamente el dado por 𝐼𝑘, esto es 𝑃∩(𝑋). Demostración. La prueba, aunque no es difícil y solo requiere algunas comprobaciones, no la daremos y nos limitaremos a citarla ya que no es el tema principal del trabajo. Aún así, una pequeña idea de cómo iría es que, dado que sabemos que 𝐼𝑘es isomorfismo e 𝐼𝑣𝑎𝑙 es sobreyectivo, se sigue que 𝐼𝑘es sobreyectivo y por tanto solo habría que probar que es inyectivo. Esto requeriría de estudiar previamente los ideales maximales del anillos 𝑘[𝑥, 𝑦]y comprobar que puntos conjugados dan lugar al mismo anillo de valoración. Una demostración de este hecho con detalle puede encontrarse en [1]. Corolario 2.2.En virtud del teorema anterior, el conjunto de puntos conjugados de 𝑋por la acción de Gal(𝑘∕𝑘)es una curva proyectiva no singular sobre 𝑘en el sentido de la definición 2.11 siendo su cuerpo de funciones 𝐾=(𝑋). Corolario 2.3.Si 𝑘es un cuerpo perfecto y dado 𝑃∈𝑋, el cuerpo de definición de 𝑃 tiene grado sobre 𝑘exactamente [𝑘𝑃∶𝑘], a lo que llamamos deg(𝑃)en la definición 2.12 que a su vez coincide con el número de elementos en la órbita de 𝑃. Observación 2.10.Como para cada cuerpo finito 𝑘=𝔽𝑞solo existe una única extensión de cada grado, el corolario anterior nos dice que si tengo deg(𝑃)puntos conjugados a un punto 𝑃, todos estos puntos tienen como cuerpo de definición a 𝑘′=𝔽𝑞deg(𝑃). 2. preludio de curvas algebraicas 39 Ejemplo 2.10 (La cuártica de Klein).Sea 𝑘=𝔽2y sea 𝐹=𝑥3𝑦+𝑦3𝑧+𝑧3𝑥∈𝔽2[𝑥, 𝑦, 𝑧]. Entonces ya vimos que 𝑋=(𝐹)tiene 3puntos en 𝑘. Esto es, 3puntos de grado 1. Para ver sus puntos de grado 2debemos tomar una extensión la extensión de grado 2de 𝑘, por ejemplo 𝑘′=𝔽4=𝔽2[𝑎]∕⟨𝑎2+𝑎+ 1⟩. En tal caso en 𝑋(𝑘′)aparecen dos puntos de grado 1conjugados: (1 ∶ 𝑎∶ 1 + 𝑎)y(1 ∶ 1 + 𝑎∶𝑎). Este par de puntos define un punto de grado 2sobre 𝑘. En particular, esto nos dice que el cuerpo de funciones racionales de 𝑋sobre 𝔽2solo tiene un lugar de grado 2. Si quisiéramos ver los puntos de grado 3, tomaríamos 𝑘′=𝔽8. Como sabemos, existe un generador de la extensión 𝔽8=𝔽2(𝜉). Resulta que una posible elección de generador es un elemento que cumpla 𝜉3=𝜉+ 1. Si alguna de las coordenadas del punto es cero, recuperamos los puntos de grado 1de 𝔽2. En caso contrario tomamos sin pérdida de generalidad 𝑧= 1 y obtenemos que poniendo 𝑦=𝜉𝑚y𝑥=𝜉𝑝y sustituyendo en la ecuación, obtenemos que los puntos de la forma (𝜉3𝑚𝜂∶𝜉𝑚∶ 1) con 𝜂=𝜉, 𝜉2, 𝜉4son soluciones. Reordenando todos las posibles combinaciones obtenemos un total de 24 puntos de grado 1sobre 𝔽8lo cual nos dice que, quitando los 3que había sobre 𝔽2de grado 1, tenemos 7puntos de grado 3que deben ser conjugados sobre 𝔽2. 2.5 Divisores en cuerpos arbitrarios y la desigualdad de Riemann Podemos ahora introducir el concepto de divisores que será con el que construiremos los espacios 𝐿(𝐷)sobre los cuales construiremos los códigos Goppa. Lo que veremos a continuación puede generalizarse para un cuerpo de funciones algebraicas cualquiera pero por simplicidad, supondremos que 𝐾=(𝑋)es el cuerpo de funciones de una curva plana, proyectiva sin puntos singulares sobre un cuerpo perfecto 𝑘. Definición 2.15. El grupo de los divisores de (𝑋),𝐷𝑖𝑣((𝑋)) es el grupo abeliano libre generado por sumas de la forma 𝐷=∑ 𝑃∈ℙ(𝑋) 𝑎𝑃𝑃 donde 𝑎𝑃son todos nulos salvo un número finito. La suma se toma sobre todos los lugares de (𝑋)o, dicho de otro modo, en virtud 40 códigos goppa del teorema 2.4, la suma es sobre conjuntos de puntos conjugados por la acción del grupo de Galois. Definición 2.16. El grado del divisor 𝐷=∑𝑃∈ℙ𝐾𝑎𝑃𝑃es deg(𝐷) = ∑ 𝑃∈ℙ𝐾 𝑎𝑝deg(𝑃). Observación 2.11.Esta definición del grado es compatible con la que se dio para cuando 𝑘es algebraicamente cerrado ya que en ese caso, el grado de cada punto es 1. Esto refleja el hecho de que, según el teorema 2.4, si tomamos el lugar 𝑃con coeficiente 𝑎𝑃en nuestro divisor, como 𝑃puede entenderse como deg(𝑃)puntos de 𝑋conjugados, tenemos que contar el lugar 𝑃tantas veces como indique el grado de su cuerpo residual. Definición 2.17. Si 𝑓∈𝐾se define el divisor de 𝑓,(𝑓)como (𝑓) = ∑ 𝑃∈ℙ𝐾 𝑣𝑃(𝑓)𝑃 A los divisores que son divisores de alguna función les llamaremos divisores principales. Al igual que en el caso proyectivo habitual se tiene este importante resultado. Teorema 2.5. El grado de un divisor principal es cero. Demostración. Como 𝑓∈(𝑋),𝑓es cociente de dos polinomios 𝑓=𝑔∕ℎcon 𝑔, ℎ ∈𝑘[𝑥0, 𝑥1, 𝑥2]homogéneos del mismo grado. Entonces por tener 𝑔yℎcoeficientes en 𝑘,𝑔yℎtienen, respectivamente, la misma valoración para puntos conjugados por la acción del grupo de Galois por estar estos puntos asociados al mismo lugar de (𝑋)en virtud del teorema 2.4. Así podemos asociar, a cada divisor 𝐷de 𝐷𝑖𝑣((𝑋)), un divisor en 𝐷𝑖𝑣((𝑋)), descomponiendo cada lugar 𝑃en la suma de los puntos que conforman su órbita. Dado que la valoración de 𝑓en cada punto conjugado es la misma, está claro que deg(𝐷)visto en 𝐷𝑖𝑣((𝑋)) coincide con deg(𝐷)visto en 𝐷𝑖𝑣((𝑋)) luego por el teorema 2.2 se sigue el resultado. Por último, hemos de introducir la desigualdad de Riemann, la cual es un caso particular del teorema de Riemann-Roch original. Tratar con este teorema en su forma completa requeriría previamente introducir el concepto de formas diferenciales lo 2. preludio de curvas algebraicas 41 cual va más allá del objetivo del capítulo. Por ello, hablaremos simplemente de la desigualdad de Riemann, utilizada por este mismo y más tarde completada con el teorema de Gustav Roch. Aún así, un tratamiento un poco más exhaustivo se puede encontrar en el apéndice del trabajo, en la sección 4.2. Para introducir la desigualdad de Riemann es preciso dar la definición de género de una curva. Para no extender demasiado la exposición del trabajo, solamente diremos que el género de una curva es un invariante por morfismo birracionales que se le asocia a curvas proyectivas sobre un cuerpo 𝑘. Una definición precisa y puramente algebraica puede encontrarse en el apéndice del trabajo. En el caso de que estemos en ℙ2y la curva sea plana, no singular, dada por 𝐹= 0 con 𝐹de grado 𝑑, el género 𝑔 puede ser calculado según la fórmula de Plücker4: 𝑔=1 2(𝑑− 1)(𝑑− 2). Teorema 2.6 (Desigualdad de Riemann). Sea 𝑋una curva proyectiva de género 𝑔sobre un cuerpo 𝑘y sea 𝐷∈𝐷𝑖𝑣(𝐾(𝑋)). Entonces: 𝑙(𝐷)≥deg(𝐷) − 𝑔+ 1. Además, si deg(𝐷)>2𝑔− 2, se tiene la igualdad. Demostración. No la damos aquí. Se puede encontrar en la sección 4.2 del apéndice del trabajo. 4Una indicación de en qué se basa la prueba de esta fórmula puede encontrarse en el apéndice del trabajo (ver sección 4.3) 3. códigos algebraico-geométricos 49 Teorema 3.2 (Cota de Hasse-Weil). Sea 𝑋una curva de género 𝑔sobre 𝔽𝑞. Si denotamos por 𝑁𝑞(𝑋)el número de puntos racionales de 𝑋, se tiene que: |||𝑁𝑞(𝑋)−(𝑞+ 1)|||≤2𝑔√𝑞. Demostración. Una demostración que sigue la línea de la teoría desarrollada en el apéndice puede encontrarse en [1]. Gracias a este resultado podemos buscar las curvas que tengan el máximo número de puntos racionales según esta cota y construir códigos Goppa sobre ellas. Ejemplo 3.3 (Curvas Hermitianas).Consideremos la curva 𝑋=(𝐹)⊆ℙ2(𝔽𝑞)con 𝐹=𝑥𝑟+1+𝑦𝑟+1+𝑧𝑟+1 ∈𝑘[𝑥, 𝑦, 𝑧]. Estas curvas (variando 𝑟) forman la familia conocida como curvas hermitianas. Consideremos el caso particular 𝑞=𝑟2= 2𝑙. Por la fórmula de Plücker, 𝑔=𝑟(𝑟− 1) 2=1 2(𝑞−√𝑞). Veamos que estas curvas tienen el máximo número de puntos racionales. Esto es, por la cota de Hasse-Weil, un máximo de 𝑁𝑞(𝑋) = 1 + 𝑞√𝑞puntos de grado 1. Pongamos que una de las tres variables es nula, 𝑥𝑦𝑧 = 0, entonces, sin pérdida de generalidad, la otra es 1y tenemos que 𝑥𝑟+1 = 1 ya que estamos en un cuerpo de característica 2. Como nuestro cuerpo tiene 𝑟2elementos, su grupo multiplicativo tiene 𝑟2− 1 = (𝑟+ 1)(𝑟− 1) elementos. Usando además que sabemos que el grupo multiplicativo es cíclico, digamos 𝔽∗ 𝑞=⟨𝛽⟩, tenemos que las soluciones son explícitamente {𝛽𝑟−1, 𝛽2(𝑟−1),…, 𝛽(𝑟−1)(𝑟+1)}por lo que llegamos a que en el cuerpo están todas las 𝑟+1 soluciones de 𝑥𝑟+1 = 1. Permutando, tenemos que hay 3(𝑟+ 1) puntos racionales con 𝑥𝑦𝑧 = 0. Digamos ahora que 𝑥𝑦𝑧 ≠0y razonemos de forma similar. Sin pérdida de generalidad, 𝑧= 1 y despejando se tiene que 𝑥𝑟+1 = 1 + 𝑦𝑟+1. Si 𝑦𝑟+1 ≠1, entonces 1 + 𝑦𝑟+1 ≠0y, dado que 𝛽genera 𝔽∗ 𝑞,𝛽𝑟+1 genera 𝔽𝑟(ya que 𝔽∗ 𝑞tiene (𝑟+ 1)(𝑟− 1) elementos) lo cual nos dice que 𝑦𝑟+1 ∈𝔽𝑟y por tanto que 1 + 𝑦𝑟+1 ∈𝔽𝑟luego este elemento se puede poner como una potencia (𝑟+ 1)-ésima de 𝛽y por tanto tiene una raíz (𝑟+ 1)-ésima. Esto, junto con que 𝑥𝑟+1 = 1 tiene las 𝑟+ 1 soluciones, prueba fundas conexiones que descubrió entre la teoría de números y la geometría algebraica, es una de las figuras más destacadas del siglo XX en ambos campos. 50 códigos goppa que tenemos 𝑟+ 1 soluciones para 𝑥para cada elección de 𝑦. Como para 𝑦tenemos 𝑟2− 1 − (𝑟+ 1) = (𝑟+ 1)(𝑟− 1 − 1) = (𝑟+ 1)(𝑟− 2) opciones, esto nos da (𝑟− 2)(𝑟+ 1)2 valores para 𝑥e𝑦. Se tiene por tanto que 𝑋tiene 3(𝑟+ 1) + (𝑟− 2)(𝑟+ 1)2= 3(𝑟+ 1) + 𝑟3− 3𝑟− 2 = 𝑟3+ 1 = 1 + 𝑞√𝑞 puntos racionales, que, por el teorema 3.2, es el máximo número de puntos racionales posibles para este cuerpo y este género. Procedemos como siempre y tomamos 𝐺=𝑚𝑄 con 𝑄un punto que puede ser arbitrario, digamos por fijar, 𝑄= (0 ∶ 1 ∶ 1) y pongamos 𝑞−√𝑞 < 𝑚 < 𝑞√𝑞para obtener un código fuertemente algebraico geométrico. Tomemos por último 𝐷como la suma del resto de puntos racionales. Entonces, por la proposición 3.1, se tiene que 𝑘=𝑚+1−𝑔y la distancia 𝑑es por el teorema 3.1, 𝑑≥𝑑∗=𝑛−𝑚. Veamos lo buenos que son estos códigos. Tomemos 𝑞= 16 y𝑚= 37. Entonces 𝑘= 32 y𝑑≥𝑑∗= 27. Comparando esto con los códigos tipo Reed-Solomon del ejemplo 3.1 (que son los códigos más utilizados a día de hoy) sobre el mismo alfabeto, 𝔽16 y tomemos 𝑟= 8. Con esta elección de 𝑟hacemos que ambos códigos tengan el ratio tasa de transmisión, 1∕2. Obtenemos entonces que el código Reed-Solomon puede transmitir palabras de tamaño 15 con una distancia mínima de 7unidades. Para un canal con el que la probabilidad de transmitir mal un caracter sea de 𝑝= 0.01 y asumiendo que recibimos una palabra equivocada, obtenemos que el código Reed-Solomon tiene una probabilidad de aún tener una palabra incorrecta de alrededor de 3⋅10−4 lo cual es muy bueno. Sin embargo, 𝐶(𝐺, 𝐷)tiene un probabilidad de fallar menor a 2⋅10−7 que es una mejora de 3órdenes de magnitud. Observación 3.1.Según el teorema 3.2, la cuártica de Klein del ejemplo 3.2 puede tener hasta 25 puntos racionales y ya vimos en el ejemplo 2.10 que tenía 24. Al tener casi todos sus puntos racionales posibles, es una curva idónea para la construcción de códigos Goppa. Solo tenemos una cosa pendiente: hemos de construir explícitamente los códigos de los que hemos estado hablando de forma teórica todo este tiempo. Para ello, es necesario hallar o bien una matriz generatriz, o bien una matriz de control de estos códigos la que nos sirve además para los algoritmos de decodificación que precisan de ella. Encontrar una de estas matrices se basa en conocer bien el espacio 𝐿(𝐺)en los ejemplos anteriores y será la geometría, por tanto, la que nos permita resolver este problema. 3. códigos algebraico-geométricos 51 Ejemplo 3.4 (Matriz generatriz para la cuártica de Klein).Sea 𝑋la cuártica de Klein dada en el ejemplo 3.2 sobre 𝔽8. Ya vimos en el ejemplo 2.3 que 𝑦∕𝑧es un parámetro local en el 𝑄= (0 ∶ 0 ∶ 1). De forma totalmente análoga se prueba que las funciones 𝑧∕𝑥y𝑥∕𝑦son parámetros locales en 𝑃1=(1∶0∶0)y𝑃2=(0∶1∶0) respectivamente. Vamos a ver cómo se comporta 𝑦∕𝑧en estos dos puntos. De la ecuación de 𝑋en 𝑃1obtenemos despejando que 𝑦 𝑧=(𝑧 𝑥)2𝑥3 𝑥3+𝑦2𝑧 Como 𝑥3+𝑦2𝑧no se anula en 𝑃1,𝑦∕𝑧tiene un cero de multiplicidad 2. De forma análoga, en 𝑃2tenemos que 𝑦 𝑧=(𝑦 𝑥)3𝑦3+𝑧2𝑥 𝑦3, por lo que tenemos un polo de multiplicidad 3. Estos son todos los posibles ceros y polos de 𝑦∕𝑧, de donde (𝑦 𝑧)= 2𝑃1− 3𝑃2+𝑄. Con razonamientos similares se acaba deduciendo que (𝑥 𝑦)= −3𝑃1+𝑃2+ 2𝑄, (𝑧 𝑥)=𝑃1+ 2𝑃2− 3𝑄. La observación fundamental para acabar calculando 𝐿(𝐺) = 𝐿(10 𝑄)es que (𝑧 𝑥)𝑎(𝑦 𝑥)𝑏 ∈𝐿(10 𝑄),para 0≤3𝑎+ 2𝑏≤10,0≤𝑏≤2𝑎, que es una mera comprobación después de haber ajustado los valores de 𝑎y𝑏para que estas funciones estén en el espacio. Esto nos da un total de 8funciones que están en 𝐿(10 𝑄)que coincide con la dimensión del espacio 𝑙(10 𝑄) = deg(10 𝑄) + 1 − 𝑔= 8. Falta comprobar que son independientes pero esto se tiene debido a que cada una de estas 8funciones tiene un polo de orden distinto en 𝑄, haciendo las cuentas (órdenes 0,2,5,6,7,8,9,10 respectivamente). 52 códigos goppa Ya solamente falta sustituir las coordenadas de los puntos racionales de 𝑋para conseguir una matriz generatriz. El resultado es una matriz 23 × 8 que, desgraciadamente, es demasiado grande para que quepa en una hoja. No debemos aún así preocuparnos pues existen librerías de Sage con estos códigos ya implementados. Ejemplo 3.5 (Matriz generatriz para curvas hermitianas).Ya vimos en el ejemplo 3.3 que para la curva hermitiana sobre 𝔽16 con 𝑞−√𝑞 < 𝑚 < 𝑞√𝑞se tenía que 𝑙(𝐺) = 𝑙(𝑚𝑄) = 𝑚+1−𝑔siendo 𝑄= (0 ∶ 1 ∶ 1). Al igual que en el ejemplo anterior, vamos a dar una base de 𝐿(𝐺)explícitamente. Estas serán las funciones: 𝑓(𝑎, 𝑏;𝑥, 𝑦, 𝑧) = 𝑥𝑎𝑦𝑏 (𝑦+𝑧)𝑎+𝑏; 0 ≤𝑎≤4,4𝑎+ 5𝑏≤𝑚 𝑎, 𝑏 ∈ℤ Esto nos da, efectivamente, un total de 𝑚− 5 = 𝑚+1−𝑔funciones diferentes. Veamos que todas estas están en 𝐿(𝐺)y que son independientes. Considerando la carta afín 𝑧= 1, tenemos que 𝑄se corresponde con el punto afín (0,1). En tal caso, la función 𝑥∕𝑧parece una elección muy razonable para ser un parámetro local en 𝑄. En efecto, haciendo el cambio para trabajar con el origen, uno comprueba que 𝜕𝑓 ∕𝜕𝑦(0,1) = 𝑟+ 1 ≠0puesto que 𝑟+ 1 es impar por ser 𝑟2una potencia de 2. Por tanto, 𝑥∕𝑧es un parámetro local en 𝑄. Análogamente, otro parámetro local de la curva en 𝑄sería 𝑥∕𝑦. Teniendo esto en cuenta podemos observar que en la curva: 𝑥 (𝑦+𝑧)=𝑥(∑𝑖+𝑘=𝑟𝑦𝑖𝑧𝑗) 𝑦𝑟+1 +𝑧𝑟+1 =(𝑧 𝑥)𝑟∑𝑖+𝑘=𝑟𝑦𝑖𝑧𝑗 𝑧𝑟, donde hemos usado la identidad clásica (𝑎+𝑏)𝑛= (𝑎+𝑏)(∑ 𝑖+𝑘=𝑛 𝑎𝑖𝑏𝑗), que se da en cuerpos de característica 2. De igual forma, aplicando esta misma identidad a 𝑦∕(𝑦+𝑧)obtenemos que 𝑦 𝑦+𝑧=𝑦(∑𝑖+𝑘=𝑟𝑦𝑖𝑧𝑗) 𝑦𝑟+1 +𝑧𝑟+1 =(𝑦 𝑥)𝑟+1 (∑𝑖+𝑘=𝑟𝑦𝑖𝑧𝑗) 𝑦𝑟 En conclusión, la función 𝑥∕(𝑦+𝑧)tiene un polo de orden 𝑟en 𝑄y la función 𝑦∕(𝑦+𝑧)tiene un polo de orden 𝑟+ 1 en 𝑄. En el caso que nos concierne, 𝑟= 4 y por 3. códigos algebraico-geométricos 53 tanto podemos concluir que la función 𝑓(𝑎, 𝑏;𝑥, 𝑦, 𝑧) = 𝑥𝑎𝑦𝑏 (𝑦+𝑧)𝑎+𝑏 tiene un polo en 𝑄de orden 4𝑎+ 5𝑏y por tanto todas estas funciones son independientes. Por último, las condiciones impuestas sobre 𝑎y𝑏hacen que las funciones 𝑓(𝑎, 𝑏;𝑥, 𝑦, 𝑧)estén en 𝐿(𝐺)por definición. La matriz generatriz del código se podría obtener por tanto, sustituyendo estas funciones en cada uno de los puntos racionales de nuestra curva. Observación 3.2.La construcción anterior es válida para cualquier 𝑞en las condiciones del ejemplo 3.3. Hemos tomado 𝑞= 16 por ser el ejemplo más conocido históricamente sobre este tipo de códigos. 3.3 Mejora de la cota de Gilbert-Varshamov Los códigos algebraico-geométricos presentan una de las familias de códigos lineales más generales que existen. En función de la curva que escojamos y de los puntos racionales de esta, podemos construir códigos con una cantidad muy diversa de parámetros. Además cuanta más información tengamos sobre la curva, más información podemos obtener sobre los códigos algebraico-geométricos que podemos construir sobre ella. Un ejemplo de esto lo hemos visto al tratar de acercarnos a la cota de Hasse-Weil en la sección anterior. El gran desarrollo de la geometría algebraica en cuerpos finitos por André Weil y más tarde las técnicas creadas por Alexander Grothendieck4para atacar estos problemas, arrojan una cantidad de resultados sorprendentes sobre los códigos algebraico-geométricos. En particular cabe resaltar que existe una familia infinita de códigos algebraico-geométricos que se hallan por encima de la cota de Gilbert-Varshamov. Hasta ese entonces, se conocía que si entre todos los códigos conocidos se toma una sucesión "al azar" una restricción sobre la distancia mínima relativa al código, entonces su tasa de transmisión converge a cero casi seguro, lo cual implicaría que se superaba la cota de Gilbert-Varshamov. Sin embargo ninguna familia infinita de códigos conocidos hasta la fecha verificaba tal propiedad. Los códigos Goppa rompieron con esta tendencia teniéndose este teorema, probado por Tsfasman, Vlăduţ y Zink: 4Matemático franco–alemán nacido en 1928 y fallecido en 2014. Uno de los fundadores de la geometría algebraica moderna y uno de los matemáticos más influyentes del siglo XX. 54 códigos goppa Teorema 3.3 (Tsfasman, Vlăduţ y Zink). Si 𝑞es una potencia par de un primo, existe una familia infinita de curvas 𝑖(𝑖∈ℕ), tal que 𝑖tiene 𝑛𝑖+ 1 puntos racionales y género 𝑔𝑖teniéndose que 𝑛𝑖tiende a infinito cuando lo hace 𝑖y tal que 𝑔𝑖 𝑛𝑖 ←→ (𝑞1 2− 1)−1 ,cuando 𝑖→∞. Demostración. La prueba se encuentra en el libro de Tsfasman, Vlăduţ y Zink en [8]. Como se puede deducir del teorema 3.1, esto implica que el código fuertemente algebraico-geométrico correspondiente a esta curva con 𝐺=𝑚𝑖𝑄y𝐷=∑𝑛𝑖 𝑘=1 𝑃𝑘 tiene ratio (𝑚𝑖−𝑔𝑖+ 1)∕𝑛𝑖y distancia mínima 𝑑𝑖≥𝑛𝑖−𝑚𝑖luego asintóticamente estos códigos superan la cota de Gilbert-Varshamov. En concreto, uno encuentra una mejora estricta de la cota para 𝑞≥49 marcando un antes y un después para la rama de teoría de códigos. 4 Apéndice 4.1 Dualidad en códigos correctores Veremos en esta breve sección que dado un código lineal , podemos construir un código asociado a él al que denominaremos el dual de cuyos parámetros y propiedades pueden ser deducidas en su mayoría, a través del estudio del código . Sea por tanto ⊂𝔽𝑛 𝑞un código lineal y sea 𝐴una matriz de control de este. Como 𝐴es de rango máximo, 𝐴𝑡puede ser interpretada como una matriz generatriz de otro código sobre 𝔽𝑞. Definición 4.1. En las condiciones anteriores, tal código es llamado el código dual de y se denotará como ⟂. Por construcción, si es de dimensión 𝑘,⟂es de dimensión 𝑛−𝑘. Si además  es una matriz generatriz de , sabemos que 𝐴⋅=𝟎lo que implica que 𝑡⋅𝐴𝑡=𝟎 y𝑡es de rango máximo luego es una matriz de control para ⟂. Para entender la relación entre estos dos códigos, introducimos una forma bilineal que imita al producto escalar de ℝ. Consideramos la forma bilineal definida como sigue: si 𝐱,𝐲∈𝔽𝑛 𝑞, 𝐱⋅𝐲= 𝑛 ∑ 𝑖=1 𝑥𝑖𝑦𝑖∈𝔽𝑞, a la que llamaremos producto escalar, igual que en ℝ. Esta nomenclatura no es precisa, ya que la operación anterior no es un producto escalar en el sentido estricto de la palabra. Por ejemplo, en 𝔽4 2,1100 ⋅1100 = 0. Sin embargo, sí que es una operación simétrica y lineal en cada uno de los factores. Utilizando estas propiedades y el mismo argumento que en ℝo en ℂ, puede demos- 56 códigos goppa trarse que la dimensión del ortogonal de un subespacio vectorial de dimensión 𝑘es de dimensión 𝑛−𝑘(pues es el conjunto de soluciones de un sistema lineal homogéneo de 𝑘ecuaciones). La única diferencia principal con un producto escalar propiamente dicho es pues la existencia de vectores ortogonales a sí mismo y por tanto, el hecho de que la intersección de y su ortogonal puede ser no nula. Proposición 4.1.Si es un código lineal, su dual, ⟂, es el ortogonal de . Demostración. Se deduce directamente de que el producto de la matriz generatriz de por la matriz generatriz de ⟂es nula como hemos visto antes. Por tanto el código generado por las filas de la matriz generatriz está contenido en ⟂. Al tener la misma dimensión, se prueba que este código es, de hecho, el código ortogonal. Para finalizar esta sección, enunciaremos un teorema que no se probará relativo al cálculo de la distancia mínima del código ⟂. Definición 4.2. Si ⊂𝔽𝑛 𝑞es un código lineal, se define el polinomio de pesos 𝑊(𝑥) = 𝑛 ∑ 𝑖=0 𝑎𝑖𝑥𝑖, donde 𝑎𝑖es el número de elementos de de peso exactamente 𝑖. Se define el polinomio de pesos homogeneizado 𝑊(𝑥, 𝑦)como el homogeneizado de 𝑊(𝑥)a grado 𝑛mediante la variable 𝑦. Observación 4.1.Con la definición anterior, está claro que la distancia mínima de  coincide con el primer índice no nulo cuyo coeficiente 𝑎𝑖tiene un valor distinto de cero. La ventaja de introducir este polinomio que recoge la distribución de pesos es que muchas veces en teoría de códigos, si es un código de tamaño muy elevado, su dual ⟂será pequeño por lo que su polinomio de pesos será de cómputo más sencillo y podemos relacionar estos dos a través del siguiente resultado: Teorema 4.1 (Identidad de MacWilliams). Si es un código de longitud 𝑛y dimensión 𝑘sobre 𝔽𝑞y𝑊(𝑥, 𝑦)y𝑊⟂(𝑥, 𝑦)son los polinomios de pesos homogeneizados de y⟂respectivamente, se tiene que 𝑊⟂(𝑥, 𝑦)=𝑞−𝑘𝑊(𝑦−𝑥, 𝑦 + (𝑞− 1)𝑥). Demostración. Puede encontrarse en [2]. 4. apéndice 57 4.2 Género de una curva proyectiva sin puntos singulares Tradicionalmente al estudiar códigos algebraico-geométricos es necesario pasar por estudiar formas diferenciales sobre curvas. Esto implica tener que alejarse de una perspectiva puramente algebraica del tema para introducirse en el estudio de unos objetos más relacionados con la teoría de la integración. Por eso, proponemos aquí un enfoque canalizado a través de la aritmética geométrica que no precisa de la mención de 1-formas. Para esta sección, cambiaremos la notación habitual de 𝐿(𝐷)para el espacio de Riemman-Roch asociado al divisor 𝐷por la notación1𝐻0(𝐷)y su dimensión la denotaremos por ℎ0(𝐷)en vez de 𝑙(𝐷). El objetivo de esta sección será describir el género de una curva de manera algebraica. Definición 4.3. Sea 𝑋una curva proyectiva no singular sobre un cuerpo 𝑘. Para cada 𝑃∈𝑋definimos 𝐻0(𝐷)𝑃como: 𝐻0(𝐷)𝑃={𝑓∈(𝑋)|ord𝑃(𝑓) + ord𝑃(𝐷)≥0}. Consideremos el siguiente homomorfismo de 𝑘-espacios vectoriales: 𝜑𝐷∶(𝑋)←→ ⨁𝑃∈𝑋((𝑋)∕𝐻0(𝐷)𝑃) 𝑓←→ ⨁𝑃∈𝑋(𝑓m od 𝐻0(𝐷)𝑃) Por definición, ker(𝜑𝐷) = 𝐻0(𝐷). Definición 4.4. El espacio 𝐻1(𝐷)se define2como el conúcleo de la aplicación anterior, 𝐻1(𝐷) = coker(𝜑𝐷). Con esta definición, está claro que, por construcción, la siguiente sucesión es exacta: 0→𝐻0(𝐷)←→ (𝑋)𝜑𝐷 ←→ ⨁ 𝑃∈𝑋((𝑋)∕𝐻0(𝐷)𝑃)←→ 𝐻1(𝐷)→0 1Esta notación tan sugerente se debe a que este espacio es isomorfo al grupo 0-ésimo de una cierta cohomología que se asigna a una curva no singular y al divisor 𝐷. 2Como el lector puede imaginarse, este espacio es isomorfo al primer grupo de la cohomología de la que se habló en el anterior pie de página. 58 códigos goppa Es decir, 𝐻1(𝐷)mide la diferencia entre el espacio "global" 𝐻0(𝐷)y el espacio "local" ⨁𝑃∈𝑋(𝑓m od 𝐻0(𝐷)𝑃). Esta diferencia es precisamente lo que trata de medir el género de una curva. Para ver la definición en concreto, tenemos que hablar un poco del espacio 𝐻1(𝐷). Teorema 4.2. 𝐻1(𝐷)es de dimensión finita para cualquier divisor. Demostración. La prueba es bastante técnica y se apoya en el uso de la estructura de los anillos de funciones regulares para abiertos en la curva, los cuales son dominios de Dedekind. La demostración completa puede encontrarse en [1]. A la dimensión del espacio 𝐻1(𝐷)la denotaremos por ℎ1(𝐷). Vamos por último a ver en detalle la prueba de que el número entero ℎ0(𝐷)−ℎ1(𝐷)−deg(𝐷)es una constante que no depende del divisor 𝐷escogido. Para ello, vamos primero a establecer la situación general con la que vamos a trabajar y después veremos un par de lemas previos a la prueba. Sean 𝐷≥𝐸dos divisores. Entonces por definición, 𝐻0(𝐸)⊆ 𝐻0(𝐷). Sea 𝜑1la inclusión entre estos dos espacios. Denotemos por 𝜑2la identidad en (𝑋)y sea 𝜑3∶⨁ 𝑃 (𝑋)∕𝐻0(𝐸)𝑃→⨁ 𝑃 (𝑋)∕𝐻0(𝐷)𝑃 la aplicación sobreyectiva que se obtiene como la suma directa de las aplicaciones 𝜑3,𝑃 ∶(𝑋)∕𝐻0(𝐸)𝑃→(𝑋)∕𝐻0(𝐷)𝑃 que induce la inclusión 𝐻0(𝐸)𝑃⊆ 𝐻0(𝐷)𝑃. Entonces se tiene el siguiente diagrama conmutativo: 0𝐻0(𝐸)(𝑋)⨁𝑃∈𝑋((𝑋)∕𝐻0(𝐸)𝑃)𝐻1(𝐸) 0 0𝐻0(𝐷)(𝑋)⨁𝑃∈𝑋((𝑋)∕𝐻0(𝐷)𝑃)𝐻1(𝐷) 0 𝜑1 𝜑𝐷 𝜑2𝜑3𝜑𝐸,𝐷 (4.1) donde 𝜑𝐸,𝐷 es la aplicación inducida por 𝜑3entre los conúcleos de 𝜑𝐸y𝜑𝐷. Nuestro objetivo es probar que ker(𝜑3)es de dimensión finita y hallar su dimensión. Para ello, usaremos algunos lemas. Observación 4.2.Si 𝑘es un cuerpo y tenemos unas inclusiones de 𝑘-espacios vectoriales de la forma: 0 = 𝑉0⊂ 𝑉1⊂…⊂ 𝑉𝑞−1 ⊂ 𝑉𝑞=𝑉 , 4. apéndice 65 Una vez visto cómo funciona el teorema de Riemman-Roch, veamos qué consecuencia arroja sobre los códigos algebraico-geométricos y demos una explicación a porqué a los códigos de Goppa clásicos se les da dicho nombre. Teorema 4.6 (Dualidad en códigos de Goppa). Sea 𝐶(𝐷, 𝐺)un código de Goppa. Si denotamos por 𝐶(𝐷, 𝐺)⟂su código dual como en 4.1, entonces: 𝐶(𝐷, 𝐺)⟂=𝐶(𝐷, 𝐾 +𝐷−𝐺), donde 𝐾es un divisor de clase canónica. Demostración. Recordemos que si 𝐶(𝐷, 𝐺)es un código algebraico-geométrico, su dimensión viene dada por 𝑘=ℎ0(𝐺) − ℎ0(𝐺−𝐷)luego el código 𝐶(𝐷, 𝐾 +𝐷−𝐺) tendrá dimensión 𝑘′=ℎ0(𝐾− (𝐺−𝐷)) − ℎ0(𝐾−𝐺). Por tanto, por el teorema de Riemman-Roch, si sumamos estas dos cantidades obtenemos que: 𝑘+𝑘′=ℎ0(𝐺) − ℎ0(𝐾−𝐺)−(ℎ0(𝐺−𝐷) − ℎ0(𝐾− (𝐺−𝐷))) =𝑔− 1 − deg(𝐺−𝐷)−(𝑔− 1 − deg(𝐺)) = deg(𝐺−𝐷) + deg(𝐺) = deg(𝐷) = 𝑛 Luego las dimensiones son adecuadas. Por otro lado, si 𝑓∈𝐻0(𝐺)y𝑔∈𝐻0(𝐾+ 𝐷−𝐺), su producto 𝑓𝑔 ∈𝐻0(𝐾+𝐷). Algunos resultados extras y un poco más de trabajo prueba que al sumar sobre todos los puntos de evaluación obtenemos cero probando que el código es el ortogonal. La prueba completa puede verse en [9]. Ejemplo 4.1 (Códigos de Goppa clásicos).Terminemos la sección viendo los códigos de Goppa clásicos como un códigos algebraico-geométricos utlilizando el teorema anterior. Al igual que dijimos de forma vaga en la sección 3.2, tomaremos 𝑍como el divisor de ceros de una función 𝑔(𝑥) ∈ 𝔽𝑞𝑚[𝑥]en la curva 𝑋=ℙ1que será la recta proyectiva. Tomando 𝑄= (1 ∶ 0),𝑃𝑖= (𝛾𝑖∶ 1) de manera que 𝑔no se anula en nigún 𝛾𝑖y𝐷=𝑃0+…+𝑃𝑛−1, vamos a ver que el código de Goppa clásico Γ(𝐿, 𝑔)(donde 𝐿= {𝛾0,…, 𝛾𝑛−1}) es el espacio 𝐶(𝐷, 𝑍 −𝑄)⟂lo que, en virtud del teorema anterior, probará que Γ(𝐿, 𝑔)es el código algebraico geométrico 𝐶(𝐷, 𝐾 +𝐷−𝑍+𝑄). Para ello, observamos que ℎ0(𝑍−𝑄) = deg(𝑍) − deg(𝑄) = deg(𝑍)−1ya que la desigualdad de Riemman se da con igualdad por estar en una curva de género cero. Por tanto, un conjunto generador de 𝐻0(𝑍−𝑄)serían las funciones de la forma 𝑥1∕(𝑥0−𝜁𝑗)donde los 𝜁𝑗son los ceros de 𝑔. Por ende, una palabra (𝑐0,…, 𝑐𝑛−1)está en Γ(𝐿, 𝑔)si y solo si 𝑛−1 ∑ 𝑖=0 𝑐𝑖 𝑥−𝛾𝑖 ≡0 m od 𝑔, 66 códigos goppa lo cual es equivalente a decir que dicho polinomio se anula en todos los ceros de 𝑔 pero observamos que eso es equivalente a decir que un elemento de 𝐶(𝐷, 𝑍 −𝑄)por (𝑐0,…, 𝑐𝑛−1)sea cero lo cual prueba que Γ(𝐿, 𝑔) = 𝐶(𝐷, 𝑍 −𝑄)⟂y por tanto prueba que Γ(𝐿, 𝑔)es un código algebraico-geométrico sobre la recta proyectiva con divisor 𝐺=𝐾+𝐷−𝑍+𝑄. 4.4 Descripción de Gal(𝑘∕𝑘) Basándonos en la teoría básica de cuerpos finitos, pasamos a describir la estructura del grupo absoluto de Galois sobre uno de estos cuerpos. Para ello, asumiremos todos los resultados de Teoría de Códigos y Criptografía y ACGA. Recordemos que si 𝑘=𝔽𝑝𝑟es un cuerpo finito de característica 𝑝 > 0, entonces su clausura algebraica 𝑘= ∞ ⋃ 𝑠=1 𝔽𝑞𝑠 es la unión de todos los cuerpos finitos de característica 𝑝. Lema 4.4.Si 𝑞=𝑝𝑟con 𝑝un primo, todo subcuerpo de 𝔽𝑞tiene cardinal 𝑝𝑠con 𝑠|𝑟. Recíprocamente, si 𝑠|𝑟, existe un único subcuerpo de 𝔽𝑞con 𝑝𝑠elementos. Demostración. Que todo subcuerpo contenido en 𝔽𝑝𝑟tiene 𝑝𝑠elementos con 𝑠|𝑟es evidente ya que 𝔽𝑝𝑟tendrá estructura de espacio vectorial sobre ese cuerpo. Recíprocamente, si 𝑠|𝑟, es fácil comprobar que (𝑝𝑠− 1)|(𝑝𝑟− 1) por lo que (𝑥𝑝𝑠−1 − 1)|(𝑥𝑝𝑟−1 − 1) lo que implica que (𝑥𝑝𝑠−𝑥)|(𝑥𝑝𝑟−𝑥). Como los polinomios de la forma 𝑥𝑞−𝑥 factorizan completamente en 𝔽𝑞, vemos que las raíces de 𝑥𝑝𝑠−𝑥forman un cuerpo de 𝑝𝑠elementos. Para ver la unicidad, basta usar que todo elemento de 𝔽𝑞es raíz de 𝑥𝑞−𝑥luego si hubiese dos cuerpos de 𝑝𝑠elementos, todos los elementos de la unión deberían ser raíces de 𝑥𝑝𝑠−𝑥pero este polinomio solo puede tener 𝑝𝑠raíces. Sea 𝔽𝑞𝑚el cuerpo finito de 𝑞𝑚elementos. Por el lema anterior, 𝔽𝑞⊆𝔽𝑞𝑚. Sea ahora 𝛼∈𝔽∗ 𝑞𝑚y consideremos su polinomio irreducible 𝑓(𝑥)sobre 𝔽𝑞. Si 𝔽𝑞𝑟=𝔽𝑞[𝛼]es 4. apéndice 67 el cuerpo más pequeño que contiene a 𝛼, entonces 𝑓es de grado 𝑟y podemos ver 𝔽𝑞⊆𝔽𝑞𝑟⊆𝔽𝑞𝑚. Entonces se tiene que: Lema 4.5.En las condiciones anteriores, las raíces de 𝑓son 𝛼, 𝛼𝑞,…, 𝛼𝑞𝑟−1 y todas son distintas entre sí. Por tanto, el grupo de Galois de cualquier extensión 𝔽𝑞⊆𝔽𝑞𝑟es isomorfo a ℤ∕ℤ𝑟. Demostración. Recordemos que en 𝔽𝑞,𝑎𝑞=𝑎∀𝑎∈𝔽𝑞y que (𝑎+𝑏)𝑝=𝑎𝑝+𝑏𝑝. Por tanto, si 𝑓(𝑥) = 𝑎0+𝑎1𝑥+…+𝑎𝑟−1𝑥𝑟−1 +𝑥𝑟con 𝑎𝑖∈𝔽𝑞, se tiene que 𝑓(𝑥𝑞) = 𝑎0+…+𝑎𝑟−1𝑥𝑞(𝑟−1) +𝑥𝑞𝑟 = (𝑎0+…+𝑎𝑟−1𝑥𝑟−1 +𝑥𝑟)𝑞=𝑓(𝑥)𝑞 luego todos los elementos 𝛼, 𝛼𝑞,…, 𝛼𝑞𝑟−1 son raíces de 𝑓. Por otro lado, si existiesen 𝑖, 𝑗 tales que 𝛼𝑞𝑖=𝛼𝑞𝑗, entonces 𝛼𝑞𝑗−𝑖= 1 lo que nos daría un polinomio de grado menor que 𝑟para 𝛼lo cual no puede pasar porque 𝑓es su polinomio mínimo. Corolario 4.6.El grupo de Galois de la extensión 𝔽𝑞⊆𝔽𝑞𝑚es cíclico de orden 𝑚y está generado por el automorfismo de Frobenius 𝜙∶𝔽𝑞𝑚←→ 𝔽𝑞𝑚 𝑥←→ 𝜙(𝑥) = 𝑥𝑞 Proposición 4.2 (Estructura de Gal(𝑘∕𝑘)).Si 𝑘=𝔽𝑞es un cuerpo finito, entonces Gal(𝑘∕𝑘)es isomorfo al grupo de los enteros profinitos, esto es, el conjunto de sucesiones {𝑎𝑛}𝑛∈ℕde manera que 𝑎𝑛∈ℤ∕ℤ𝑛para todo 𝑛y si 𝑚|𝑛,𝑎𝑚≡𝑎𝑛mod 𝑚con la operación de sumar componente a componente. Demostración. Si 𝜎∈ Gal(𝑘∕𝑘), su restricción a cualquier cuerpo 𝔽𝑞𝑛es alguna potencia del automorfismo de Frobenius 𝜙, esto es, 𝜎=𝜙𝑎𝑛restringiendo 𝜎a𝔽𝑞𝑛para algún 0≤𝑎𝑛< 𝑛. Como 𝔽𝑞es la unión de todas las extensiones de 𝔽𝑞,𝜎queda unívocamente determinado por estos números 𝑎𝑛. Además, por el lema 4.4, si 𝑚|𝑛, se tiene que 𝔽𝑚⊆𝔽𝑛y por tanto las correspondientes potencias del automorfismo de Frobenius deben coincidir, esto es, 𝑎𝑚≡𝑎𝑛mod 𝑚. Se puede comprobar que la composición de automorfismos se corresponde con la suma componente a componente de estas sucesiones lo que concluye la prueba. Bibliografía [1] Lorenzini, Dino: An invitation to arithmetic geometry. American Mathematical Society (1996). [2] MacWilliams, F. J., Sloane, N. J. A., & Goethals, J. M. (1972). The MacWilliams identities for nonlinear codes. Bell System Technical Journal, 51(4), 803-819. [3] Munuera, Carlos; Tena, Juan: Codificación de la Información. Universidad de Valladolid (1997). [4] Peterson, William W.; Weldon, Jr. Edward J.: Error-correcting codes. MIT Press (1972). [5] Singh, Harshdeep: Code based Cryptography: Classic McEliece. arXiv preprint ar- Xiv:1907.12754. [6] Stichtenoth, Henning: Algebraic function fields and codes. Springer (2009). [7] Tsfasman, Michael A.; Vlăduţ, Serge G.; Nogin, Dmitry: Algebraic Geometric Codes: Basic Notions: Basic Notions. American Mathematical Society (2007). [8] Tsfasman, Michael A.; Vlăduţ, Serge G.; Zink, Thomas: Modular curves, Shimura curves, and Goppa codes, better than Varshamov-Gilbert bound. Mathematische Nachrichten 109 (1) 21–28. [9] Van Lint, Jacobus H.; van der Geer, Gerard: Introduction to coding theory and algebraic geometry. Birkhäuser (2012).