En matemáticas , y más específicamente en álgebra computacional, geometría algebraica computacional y álgebra conmutativa computacional , una base de Gröbner es un tipo particular de conjunto generador de un ideal en un anillo polinómico K [ x 1 ,…, x n ] sobre un campo K . Una base de Gröbner permite deducir fácilmente muchas propiedades importantes del ideal y la variedad algebraica asociada , como la dimensióny el número de ceros cuando es finito. El cálculo de bases de Gröbner es una de las principales herramientas prácticas para resolver sistemas de ecuaciones polinomiales y calcular las imágenes de variedades algebraicas bajo proyecciones o mapas racionales .
El cálculo de la base de Gröbner puede verse como una generalización multivariante, no lineal, tanto del algoritmo de Euclides para calcular los divisores comunes máximos de polinomios , como de la eliminación gaussiana para sistemas lineales. [1]
Las bases de Gröbner se introdujeron en 1965, junto con un algoritmo para calcularlas ( algoritmo de Buchberger ), por Bruno Buchberger en su Ph.D. tesis. Los nombró en honor a su asesor Wolfgang Gröbner . En 2007, Buchberger recibió la Association for Computing Machinery 's París Kanellakis Teoría y Práctica premio para este trabajo. Sin embargo, el matemático ruso Nikolai Günther había introducido una noción similar en 1913, publicada en varias revistas matemáticas rusas. Estos artículos fueron en gran parte ignorados por la comunidad matemática hasta que fueron redescubiertos en 1987 por Bodo Renschuch et al. [2] En 1964, Heisuke Hironaka desarrolló de forma independiente un concepto análogo para las series de potencias multivariadas , quien las denominó bases estándar . Este término ha sido utilizado por algunos autores para denotar también bases de Gröbner.
Muchos autores han extendido la teoría de las bases de Gröbner en diversas direcciones. Se ha generalizado a otras estructuras como polinomios sobre anillos ideales principales o anillos polinomiales , y también a algunas clases de anillos y álgebras no conmutativas, como las álgebras de Ore .
Fondo
Anillo polinomial
Las bases de Gröbner se definen principalmente para ideales en un anillo polinomial sobre un campo K . Aunque la teoría funciona para cualquier campo, la mayoría de los cálculos de base de Gröbner se realizan cuando K es el campo de los racionales o los enteros módulo un número primo.
Un polinomio es una suma donde el son elementos distintos de cero de K y elson monomios o "productos energéticos" de las variables. Esto significa que un monomio M es un producto donde el son números enteros no negativos. El vectorse llama el vector exponente de M . La notación a menudo se abrevia como. Los monomios se definen de forma única por sus vectores exponentes, por lo que las computadoras pueden representar los monomios de manera eficiente como vectores exponentes y los polinomios como listas de vectores exponentes y sus coeficientes.
Si es un conjunto finito de polinomios en un anillo polinomial R , el ideal generado por F es el conjunto de combinaciones lineales de elementos de F con coeficientes en todo R :
Orden monomial
Todas las operaciones relacionadas con las bases de Gröbner requieren la elección de un orden total en los monomios, con las siguientes propiedades de compatibilidad con la multiplicación. Para todos los monomios M , N , P ,
- .
Un pedido total que satisface estas condiciones a veces se denomina pedido admisible .
Estas condiciones implican que el orden es un orden de pozo , es decir, cada secuencia estrictamente decreciente de monomios es finita.
Aunque la teoría de la base de Gröbner no depende de una elección particular de una ordenación monomial admisible, tres ordenaciones monomiales son especialmente importantes para las aplicaciones:
- Ordenamiento lexicográfico , comúnmente llamado lex o plex (para ordenamiento léxico puro).
- Orden lexicográfico inverso de grado total , comúnmente llamado degrevlex .
- Orden de eliminación , lexdeg .
La teoría de la base de Gröbner se introdujo inicialmente para el ordenamiento lexicográfico. Pronto se advirtió que la base de Gröbner para degrevlex es casi siempre mucho más fácil de calcular, y que casi siempre es más fácil calcular una base de lex Gröbner calculando primero la base degrevlex y luego usando un "algoritmo de cambio de orden". Cuando se necesita eliminación , degrevlex no es conveniente; se pueden usar tanto lex como lexdeg pero, de nuevo, muchos cálculos son relativamente fáciles con lexdeg y casi imposibles con lex.
Una vez que se fija el orden de un monomio, los términos de un polinomio (producto de un monomio con su coeficiente distinto de cero) se ordenan naturalmente por monomios decrecientes (para este orden). Esto hace que la representación de un polinomio como una lista ordenada de pares vector coeficiente-exponente sea una representación canónica de los polinomios. La primera (la más grande) término de un polinomio p para este pedido y la correspondiente monomio y el coeficiente se llaman, respectivamente, el término principal , que conduce monomio y coeficiente principal y denotado, en este artículo, LT ( p ), lm ( p ) y lc ( p ).
Reducción
El concepto de reducción , también llamado división multivariante o cálculo de forma normal , es fundamental para la teoría de bases de Gröbner. Es una generalización multivariante de la división euclidiana de polinomios univariados .
En esta sección suponemos una ordenación monomial fija, que no se definirá explícitamente.
Dados dos polinomios f y g , se dice que f es reducible por g si algún monomio m en f es un múltiplo del monomio principal lm ( g ) de g . Si m es el monomio principal de f, entonces se dice que f es reducible con plomo por g . Si c es el coeficiente de m en f y m = q lm ( g ), la reducción de un paso de f por g es la operación que asocia af el polinomio
Las principales propiedades de esta operación son que el polinomio resultante no contiene el monomio my que los monomios mayores que m (para el orden de los monomios) permanecen sin cambios. Esta operación no está, en general, definida de forma única; si varios monomios en f son múltiplos de lm ( g ), entonces se puede elegir arbitrariamente cuál reducir. En la práctica, es mejor elegir el más grande para el orden del monomio, porque de lo contrario las reducciones posteriores podrían reintroducir el monomio que se acaba de eliminar.
Dado un conjunto finito G de polinomios, se dice que f es reducible o de plomo-reducible por G si es reducible o de plomo-reducible, respectivamente, por un elemento g de G . Si es el caso, entonces se define. La reducción (completa) de f por G consiste en aplicar iterativamente este operador hasta obtener un polinomio , Que es irreducible por G . Se llama una forma normal de f por G . En general, esta forma no se define de forma única (no es una forma canónica ); esta no unicidad es el punto de partida de la teoría de bases de Gröbner.
Para los cálculos de base de Gröbner, excepto al final, no es necesario hacer una reducción completa: una reducción de plomo es suficiente, lo que ahorra una gran cantidad de cálculo.
La definición de la reducción muestra inmediatamente que, si h es una forma normal de f por G , entonces tenemos
donde el son polinomios. En el caso de polinomios univariados, si G consta de un solo elemento g , entonces h es el resto de la división euclidiana de f por g , q g es el cociente y el algoritmo de división es exactamente el proceso de reducción de adelanto. Por esta razón, algunos autores utilizan el término división multivariante en lugar de reducción.
Ejemplos de reducción
En los ejemplos de esta sección, los polinomios tienen tres indeterminados x , y y z , y el orden monomial que se usa es el orden monomial cones decir, para comparar dos monomios, primero se comparan los exponentes de x ; sólo cuando los exponentes de x son iguales, se comparan los exponentes de y ; y los exponentes de z se comparan solo cuando los demás exponentes son iguales.
Para tener una visión clara del proceso de reducción, uno tiene que reescribir polinomios con sus términos en orden decreciente. Por ejemplo, si
debe ser reescrito
Esto permite tener el monomio principal primero (para el orden elegido); aquí
Considere la reducción de por con y
Para el primer paso de reducción, se puede reducir el primero o el segundo término. Sin embargo, la reducción de un término equivale a eliminar este término a costa de agregar nuevos términos más bajos, y, si no es el primer término reducible que se reduce, es posible que una reducción adicional agregue un término similar, que debe ser reducido de nuevo. Por lo tanto, siempre es mejor reducir primero el término reducible más grande (para el orden monomial).
El término principal de f es reducible por Entonces el primer paso de reducción consiste en multiplicar por –2 x y sumando el resultado af :
Como el término principal de es un múltiplo de los principales monomios de ambos y uno tiene dos opciones para el segundo paso de reducción. Si uno elige se obtiene un polinomio que se puede reducir de nuevo mediante
No es posible una mayor reducción, por lo que se puede elegir para la reducción completa de f . Sin embargo, uno obtiene un resultado diferente con la otra opción para el segundo paso:
Por lo tanto, la reducción completa de f puede resultar en o
Se ha introducido el algoritmo de Buchberger para resolver las dificultades inducidas por esta no unicidad. En términos generales consiste en añadir a G los polinomios que son necesarios para la singularidad de la reducción por G .
Aquí el algoritmo de Buchberger comenzaría agregando a G el polinomio
En efecto, puede reducirse aún más por y esto produce de nuevo. Sin embargo, esto no completa el algoritmo de Buchberger, ya que xy da resultados diferentes, cuando se reduce por o
Definicion formal
Una base de Gröbner G de un I ideal en un anillo polinomial R sobre un campo es un conjunto generador de I caracterizado por cualquiera de las siguientes propiedades, expresadas en relación con algún orden monomial :
- el ideal generado por los términos principales de polinomios en I es igual al ideal generado por los términos principales de G ;
- el término principal de cualquier polinomio en I es divisible por el término principal de algún polinomio en G ;
- la división multivariante de cualquier polinomio en el anillo polinomial R por G da un resto único;
- la división multivariante por G de cualquier polinomio en el ideal I da el resto 0 .
Todas estas propiedades son equivalentes; diferentes autores utilizan diferentes definiciones según el tema que eligen. Las dos últimas propiedades permiten realizar cálculos en el anillo de factores R / I con la misma facilidad que la aritmética modular. Es un hecho significativo del álgebra conmutativa que las bases de Gröbner siempre existen y pueden calcularse eficazmente para cualquier ideal dado por un subconjunto generador finito.
La división multivariante requiere un ordenamiento monomial, la base depende del ordenamiento monomial elegido, y diferentes ordenamientos pueden dar lugar a bases de Gröbner radicalmente diferentes. Dos de los ordenamientos más utilizados son el ordenamiento lexicográfico y el orden lexicográfico inverso de grados (también llamado orden lexicográfico inverso graduado o simplemente orden de grados total ). El orden lexicográfico elimina las variables; sin embargo, las bases de Gröbner resultantes suelen ser muy grandes y costosas de calcular. El orden lexicográfico inverso de grados generalmente proporciona los cálculos de base de Gröbner más rápidos. En este orden, los monomios se comparan primero por grado total, con los lazos rotos tomando el monomio más pequeño con respecto al orden lexicográfico con las variables invertidas.
En la mayoría de los casos (polinomios en un número finito de variables con coeficientes complejos o, más generalmente, coeficientes sobre cualquier campo, por ejemplo), existen bases de Gröbner para cualquier orden monomial. El algoritmo de Buchberger es el método más antiguo y conocido para calcularlos. Otros métodos son los algoritmos F4 y F5 de Faugère , basados en las mismas matemáticas que el algoritmo de Buchberger, y los enfoques involutivos, basados en ideas del álgebra diferencial . [3] También hay tres algoritmos para convertir una base de Gröbner con respecto a un orden monomial a una base de Gröbner con respecto a un orden monomial diferente: el algoritmo FGLM , el algoritmo impulsado por Hilbert y el algoritmo de caminata de Gröbner . Estos algoritmos se emplean a menudo para calcular bases lexicográficas de Gröbner (difíciles) a partir de bases de Gröbner de grado total (más fáciles).
Una base de Gröbner se denomina reducida si el coeficiente principal de cada elemento de la base es 1 y no hay monomio en ningún elemento de la base en el ideal generado por los términos principales de los otros elementos de la base. En el peor de los casos, el cálculo de una base de Gröbner puede requerir un tiempo exponencial o incluso doblemente exponencial en el número de soluciones del sistema polinomial (para el orden lexicográfico inverso de grado y el orden lexicográfico, respectivamente). A pesar de estos límites de complejidad, tanto las bases de Gröbner estándar como las reducidas son a menudo computables en la práctica, y la mayoría de los sistemas de álgebra por computadora contienen rutinas para hacerlo.
El concepto y los algoritmos de las bases de Gröbner se han generalizado a submódulos de módulos libres sobre un anillo polinomial. De hecho, si L es un módulo libre sobre un anillo R , entonces se puede considerar R ⊕ L como un anillo definiendo el producto de dos elementos de L como 0. Este anillo puede identificarse con, dónde es una base de L . Esto permite identificar un submódulo de L generado por con el ideal de generado por y los productos , . Si R es un anillo polinomial, esto reduce la teoría y los algoritmos de las bases de módulos de Gröbner a la teoría y los algoritmos de las bases de ideales de Gröbner.
El concepto y los algoritmos de las bases de Gröbner también se han generalizado a ideales sobre varios anillos, conmutativos o no, como anillos polinomiales sobre un anillo ideal principal o álgebras de Weyl .
Ejemplo y contraejemplo
Sea R = Q [ x , y ] el anillo de polinomios bivariados con coeficientes racionales y considere el ideal I = < f , g > generado por los polinomios
- f ( x , y ) = x 2 - y
- g ( x , y ) = x 3 - x
Otros dos elementos de I son los polinomios
- k ( x , y ) = - xf ( x , y ) + g ( x , y ) = xy - x
- h ( x , y ) = xk ( x , y ) - ( y - 1) f ( x , y ) = y 2 - y
Bajo orden lexicográfico con x > y tenemos
- lt ( f ) = x 2
- lt ( g ) = x 3
- lt ( h ) = y 2
El ideal generado por {lt ( f ), lt ( g )} solo contiene polinomios que son divisibles por x 2 lo que excluye lt ( h ) = y 2 ; de ello se deduce que { f , g } no es una base de Gröbner para I.
Por otro lado, podemos demostrar que { f , k , h } es de hecho una base de Gröbner para I.
En primer lugar, f y g, y por lo tanto también h, k y todos los otros polinomios en el ideal I tienen las siguientes tres ceros en la ( x , y ) plano en común, como se indica en la figura: {(1,1), (−1,1), (0,0)}. Esos tres puntos no son colineales, por lo que no contiene ningún polinomio de primer grado. Ni puedo yo contener polinomios de la forma especial
- m ( x , y ) = cx + p ( y )
con c un número racional distinto de cero yp un polinomio en la variable y solamente; la razón es que tal m nunca puede tener dos ceros distintos con el mismo valor para y (en este caso, los puntos (1,1) y (−1,1)).
De lo anterior se deduce que I, aparte del polinomio cero, solo contiene polinomios cuyo término principal tiene un grado mayor o igual a 2; por lo tanto, sus términos principales son divisibles por al menos uno de los tres monomios
- { x 2 , xy , y 2 } = {lt ( f ), lt ( k ), lt ( h )}.
Esto significa que { f , k , h } es una base de Gröbner para I con respecto al ordenamiento lexicográfico con x > y.
Propiedades y aplicaciones de las bases Gröbner
A menos que se indique explícitamente, todos los resultados que siguen [4] son verdaderos para cualquier orden monomial (vea ese artículo para las definiciones de los diferentes órdenes que se mencionan a continuación).
Es un error común pensar que el orden lexicográfico es necesario para algunos de estos resultados. Por el contrario, el orden lexicográfico es, casi siempre, el más difícil de calcular, y su uso hace impracticables muchos cálculos que son relativamente fáciles con el orden lexicográfico inverso graduado (grevlex) o, cuando se necesita eliminación, el orden de eliminación (lexdeg ) que restringe a grevlex en cada bloque de variables.
Igualdad de ideales
Las bases de Gröbner reducidas son únicas para cualquier ideal dado y cualquier orden monomial. Por lo tanto, dos ideales son iguales si y solo si tienen la misma base de Gröbner (reducida) (normalmente, un software de base de Gröbner siempre produce bases de Gröbner reducidas).
Membresía e inclusión de ideales
La reducción de un polinomio f por el Gröbner base G de un ideal I rendimientos 0 si y sólo si f está en I . Esto permite probar la pertenencia de un elemento a un ideal. Otro método consiste en verificar que la base de Gröbner de G ∪ { f } es igual a G .
Para probar si el ideal I generada por f 1 , ..., f k está contenido en el ideal J , basta con prueba de que cada f i es en J . También se puede probar la igualdad de las bases de Gröbner reducidas de J y J ∪ { f 1 , ..., f k }.
Soluciones de un sistema de ecuaciones algebraicas
Cualquier conjunto de polinomios puede verse como un sistema de ecuaciones polinomiales al igualar los polinomios a cero. El conjunto de las soluciones de tal sistema depende únicamente del ideal generado y, por lo tanto, no cambia cuando el grupo electrógeno dado es reemplazado por la base de Gröbner, para cualquier ordenamiento, del ideal generado. Tal solución, con coordenadas en un campo algebraicamente cerrado que contiene los coeficientes de los polinomios, se llama cero del ideal . En el caso habitual de coeficientes racionales , este campo algebraicamente cerrado se elige como campo complejo .
Un ideal no tiene cero (el sistema de ecuaciones es inconsistente ) si y solo si 1 pertenece al ideal (este es el Nullstellensatz de Hilbert ), o, de manera equivalente, si su base de Gröbner (para cualquier ordenamiento monomial) contiene 1, o, también, si la base de Gröbner reducida correspondiente es [1].
Dada la base de Gröbner G de un ideal I , tiene solo un número finito de ceros, si y solo si, para cada variable x , G contiene un polinomio con un monomio inicial que es una potencia de x (sin ninguna otra variable que aparezca en el término principal). Si es el caso, el número de ceros, contó con la multiplicidad, es igual al número de monomios que no son múltiplo de cualquier monomio líder de G . Este número se llama grado del ideal.
Cuando el número de ceros es finito, la base de Gröbner para un ordenamiento monomial lexicográfico proporciona, teóricamente, una solución: las primeras coordenadas de una solución es una raíz del máximo común divisor de polinomios de la base que depende solo de la primera variable. Después de sustituir esta raíz en la base, las segundas coordenadas de esta solución es una raíz del máximo común divisor de los polinomios resultantes que depende solo de esta segunda variable, y así sucesivamente. Este proceso de resolución es solo teórico, porque implica el cálculo MCD y la búsqueda de raíces de polinomios con coeficientes aproximados, que no son practicables debido a la inestabilidad numérica. Por lo tanto, se han desarrollado otros métodos para resolver sistemas polinomiales a través de bases de Gröbner (ver Sistema de ecuaciones polinomiales para más detalles).
Dimensión, grado y serie de Hilbert
La dimensión de un ideal I en un anillo de polinomios R es la dimensión Krull del anillo de R / I y es igual a la dimensión del conjunto algebraica de los ceros de I . También es igual al número de hiperplanos en posición general que se necesitan para tener una intersección con el conjunto algebraico, que es un número finito de puntos. El grado del ideal y de su conjunto algebraico asociado es el número de puntos de esta intersección finita, contados con multiplicidad. En particular, el grado de una hipersuperficie es igual al grado de su polinomio de definición.
Tanto el grado como la dimensión dependen únicamente del conjunto de los principales monomios de la base de Gröbner del ideal para cualquier ordenamiento monomial.
La dimensión es el tamaño máximo de un subconjunto S de las variables de tal manera que no hay monomio líder dependiendo sólo de las variables en S . Por lo tanto, si el ideal tiene dimensión 0, entonces para cada variable x hay un monomio principal en la base de Gröbner que es una potencia de x .
Tanto la dimensión como el grado pueden deducirse de la serie de Hilbert del ideal, que es la serie, dónde es el número de monomios de grado i que no son múltiplos de ningún monomio principal en la base de Gröbner. La serie de Hilbert se puede sumar en una fracción racional
donde d es la dimensión del ideal y es un polinomio tal que es el grado del ideal.
Aunque la dimensión y el grado no dependen de la elección del orden monomial, la serie de Hilbert y el polinomio cambiar cuando uno cambia de orden monomial.
La mayoría de los sistemas informáticos de álgebra que proporcionan funciones para calcular las bases de Gröbner también proporcionan funciones para calcular la serie de Hilbert y, por tanto, también la dimensión y el grado.
Eliminación
El cálculo de las bases de Gröbner para un ordenamiento monomial de eliminación permite la teoría de la eliminación computacional . Esto se basa en el siguiente teorema.
Considere un anillo polinomial en la que las variables se dividen en dos subconjuntos X y Y . Elijamos también un orden de monomio de eliminación "eliminando" X , es decir, un orden de monomio para el que se comparan dos monomios comparando primero las partes X y, en caso de igualdad únicamente, considerando las partes Y. Esto implica que un monomio que contiene una X -Variable es mayor que cada monomio independiente de X . Si G es una base de Gröbner de un I ideal para este orden monomial, entonces es una base de Gröbner de (este ideal a menudo se denomina ideal de eliminación ). Es más,consiste exactamente en los polinomios de G cuyos términos principales pertenecen a K [ Y ] (esto hace muy fácil el cálculo de, ya que solo es necesario verificar los principales monomios).
Esta propiedad de eliminación tiene muchas aplicaciones, algunas de ellas se describen en las siguientes secciones.
Otra aplicación, en geometría algebraica , es que la eliminación realiza la operación geométrica de proyección de un conjunto algebraico afín en un subespacio del espacio ambiental: con la notación anterior, el ( cierre de Zariski de) la proyección del conjunto algebraico definido por el ideal I en el subespacio Y se define por el ideal
El ordenamiento lexicográfico tal que es una orden de eliminación para cada partición Por lo tanto, una base de Gröbner para este pedido contiene mucha más información de la que normalmente es necesaria. Esto puede explicar por qué las bases de Gröbner para el ordenamiento lexicográfico suelen ser las más difíciles de calcular.
Intersección de ideales
Si I y J son dos ideales generados respectivamente por { f 1 , ..., f m } y { g 1 , ..., g k }, entonces un solo cálculo de la base de Gröbner produce una base de Gröbner de su intersección I ∩ J . Para esto, se introduce una nueva t indeterminada , y se usa un orden de eliminación tal que el primer bloque contenga solo ty el otro bloque contenga todas las demás variables (esto significa que un monomio que contiene t es mayor que todo monomio que no contiene t ). Con este orden monomial, una base de Gröbner de I ∩ J consiste en los polinomios que no contienen t , en la base de Gröbner del ideal
En otras palabras, I ∩ J se obtiene por la eliminación de t en K . Esto puede demostrarse observando que el K ideal consiste en los polinomios tal que y . Tal polinomio es independiente de t si y solo a = b , lo que significa que
Implicitación de una curva racional
Una curva racional es una curva algebraica que tiene una ecuación paramétrica de la forma
dónde y son polinomios univariados para 1 ≤ i ≤ n . Uno puede (y lo hará) suponer que y son coprime (no tienen factores comunes no constantes).
La implícitaidad consiste en calcular las ecuaciones implícitas de dicha curva. En el caso de n = 2, es decir, para curvas planas, esto se puede calcular con la resultante . La ecuación implícita es la siguiente resultante:
La eliminación con bases de Gröbner permite implícitamente para cualquier valor de n , simplemente eliminando t en el idealSi n = 2, el resultado es el mismo que con la resultante, si el mapaes inyectable para casi todos los t . En el otro caso, la resultante es una potencia del resultado de la eliminación.
Saturación
Al modelar un problema mediante ecuaciones polinomiales, es muy frecuente que se suponga que algunas cantidades no son cero, porque, si son cero, el problema se vuelve muy diferente. Por ejemplo, cuando se trata de triángulos , muchas propiedades se vuelven falsas si el triángulo está degenerado, es decir, si la longitud de un lado es igual a la suma de las longitudes de los otros lados. En tales situaciones, no hay esperanza de deducir información relevante del sistema polinomial si no se eliminan las soluciones degeneradas. Más precisamente, el sistema de ecuaciones define un conjunto algebraico que puede tener varios componentes irreductibles , y hay que eliminar los componentes en los que las condiciones de degeneración son cero en todas partes.
Esto se hace saturando las ecuaciones por las condiciones de degeneración, lo que se puede hacer usando la propiedad de eliminación de las bases de Gröbner.
Definición de la saturación
La localización de un anillo consiste en unir a él las inversas formales de algunos elementos. Esta sección se refiere solo al caso de un solo elemento, o equivalentemente a un número finito de elementos (unir los inversos de varios elementos equivale a unir el inverso de su producto). La localización de un anillo R por un elemento f es el anillodonde t es un nuevo indeterminado que representa la inversa de f . La localización de un ideal I de R es el ideal de Cuando R es un anillo polinomial, calcular enno es eficiente, debido a la necesidad de administrar los denominadores. Por lo tanto, la operación de localización generalmente se reemplaza por la operación de saturación .
La saturación con respectoafde un idealIenRes la imagen inversa debajo el mapa canónico de R a Es el ideal que consiste en todos los elementos de R cuyos productos por un poder de f pertenece a I .
Si J es el ideal generado por I y 1 pie en R [ t ], entoncesDe ello se deduce que, si R es un anillo polinomial, un cálculo de la base de Gröbner que elimina t permite calcular una base de Gröbner de la saturación de un ideal por un polinomio.
La propiedad importante de la saturación, que asegura que elimina del conjunto algebraico definido por el ideal I las componentes irreductibles en las que el polinomio f es cero, es la siguiente: La descomposición primaria de Consiste en los componentes de la descomposición primaria de I que no contienen ninguna potencia de f .
Cálculo de la saturación
Una base de Gröbner de la saturación por f de un polinomio ideal generado por un conjunto finito de polinomios F , puede obtenerse eliminando t enes decir, manteniendo los polinomios independientes de t en la base de Gröbner depara una eliminación ordenando eliminando t .
En lugar de utilizar F , también se puede iniciar desde una base de Gröbner de F . El método que sea más eficaz depende del problema. Sin embargo, si la saturación no elimina ningún componente, es decir, si el ideal es igual a su ideal saturado, calcular primero la base de Gröbner de F suele ser más rápido. Por otro lado, si la saturación elimina algunos componentes, el cálculo directo puede ser dramáticamente más rápido.
Si se quiere saturar con respecto a varios polinomios o con respecto a un solo polinomio que es un producto Hay tres formas de proceder que dan el mismo resultado pero pueden tener tiempos de cálculo muy diferentes (depende del problema que sea más eficiente).
- Saturando por en un único cálculo básico de Gröbner.
- Saturando por luego saturando el resultado por y así.
- Sumando a F oa su base de Gröbner los polinomios y eliminando el en un único cálculo básico de Gröbner.
Nullstellensatz efectivo
Nullstellensatz de Hilbert tiene dos versiones. El primero afirma que un conjunto de polinomios tiene un conjunto vacío de ceros comunes en un cierre algebraico del campo de los coeficientes si y solo si 1 pertenece al ideal generado. Esto se prueba fácilmente con un cálculo de base de Gröbner, porque 1 pertenece a un ideal si y solo si 1 pertenece a la base de Gröbner del ideal, para cualquier orden monomial.
La segunda versión afirma que el conjunto de ceros comunes (en un cierre algebraico del campo de los coeficientes) de un ideal está contenido en la hipersuperficie de los ceros de un polinomio f , si y solo si una potencia de f pertenece al ideal . Esto puede comprobarse saturando el ideal con f ; de hecho, una potencia de f pertenece al ideal si y solo si la saturación por f proporciona una base de Gröbner que contiene 1.
Implicitación en dimensión superior
Por definición, una variedad racional afín de dimensión k puede describirse mediante ecuaciones paramétricas de la forma
dónde son n +1 polinomios en las k variables (parámetros de la parametrización) Así, los parámetros y las coordenadas de los puntos de la variedad son ceros del ideal
Se podría adivinar que basta con eliminar los parámetros para obtener las ecuaciones implícitas de la variedad, como se ha hecho en el caso de las curvas. Desafortunadamente, este no es siempre el caso. Si eltienen un cero común (a veces llamado punto base ), cada componente irreducible del conjunto algebraico no vacío definido por eles un componente irreducible del conjunto algebraico definido por I . De ello se desprende que, en este caso, la eliminación directa de la proporciona un conjunto vacío de polinomios.
Por lo tanto, si k > 1, se necesitan dos cálculos de base de Gröbner para implícita:
- Saturar por para conseguir una base Gröbner
- Elimina el de para obtener una base de Gröbner del ideal (de las ecuaciones implícitas) de la variedad.
Implementaciones
- Sistema informático de álgebra libre CoCoA para calcular bases de Gröbner.
- Sistema de álgebra computarizado libre de GAP que puede realizar cálculos de bases de Gröbner.
- FGb, la propia implementación de Faugère de su algoritmo F4 , disponible como una biblioteca de Maple . [5] Hasta la fecha, a partir de 2014, es, con Magma, la implementación más rápida para coeficientes racionales y coeficientes en un campo finito de orden primo.
- Software gratuito Macaulay 2 para realizar cálculos de polinomios, en particular cálculos de bases de Gröbner.
- Magma tiene una implementación muy rápida del algoritmo F4 de Faugère. [6]
- Maple tiene implementaciones de los algoritmos F4 de Buchberger y Faugère, así como el seguimiento de Gröbner.
- Mathematica incluye una implementación del algoritmo de Buchberger, con técnicas de mejora del rendimiento como la caminata de Gröbner, la traza de Gröbner y una mejora de las bases tóricas.
- Software libre SINGULAR para el cálculo de bases de Gröbner conmutativas y no conmutativas.
- SageMath proporciona una interfaz unificada para varios sistemas informáticos de álgebra (incluidos SINGULAR y Macaulay) e incluye algunos algoritmos de base de Gröbner propios.
- El sistema de álgebra computacional SymPy Python utiliza bases de Gröbner para resolver sistemas polinomiales.
Áreas de aplicación
Códigos de corrección de errores
La base de Gröbner se ha aplicado en la teoría de códigos de corrección de errores para la decodificación algebraica. Utilizando el cálculo de base de Gröbner en varias formas de ecuaciones de corrección de errores, se desarrollaron métodos de decodificación para corregir errores de códigos cíclicos, [7] códigos de variedades afines, [8] códigos algebraico-geométricos e incluso códigos de bloques lineales generales. [9] La aplicación de la base de Gröbner en la decodificación algebraica es todavía un área de investigación de la teoría de la codificación de canales.
Ver también
- Algoritmo de Buchberger
- Algoritmos F4 y F5 de Faugère
- Base más grave
- Base de janet
- Cadenas regulares , una forma alternativa de representar conjuntos algebraicos
Referencias
- ^ Lazard, Daniel (1983). "Bases de Gröbner, eliminación gaussiana y resolución de sistemas de ecuaciones algebraicas". Álgebra informática . Apuntes de conferencias en Ciencias de la Computación. 162 . págs. 146-156. doi : 10.1007 / 3-540-12868-9_99 . ISBN 978-3-540-12868-7.
- ^ Renschuch, Bodo; Roloff, Hartmut; Rasputin, Georgij G .; Abramson, Michael (junio de 2003). "Contribuciones a la teoría del ideal polinomial constructivo XXIII: trabajos olvidados del matemático de Leningrado NM Gjunter sobre la teoría del ideal polinomial" (PDF) . Toro SIGSAM . 37 (2): 35–48. doi : 10.1145 / 944567.944569 . S2CID 1819694 .
- ^ Gerdt, Vladimir P .; Blinkov, Yuri A. (1998). "Bases involutivas de ideales polinomiales". Matemáticas y Computación en Simulación . 45 (5–6): 519–541. arXiv : matemáticas / 9912027 . doi : 10.1016 / S0378-4754 (97) 00127-4 . S2CID 10243294 .
- ^ Cox, David A .; Pequeño John; O'Shea, Donal (1997). Ideales, variedades y algoritmos: una introducción a la geometría algebraica computacional y el álgebra conmutativa . Saltador. ISBN 0-387-94680-2.
- ^ Página de inicio de FGb
- ^ Acero, Allan. "Página de tiempos de base de Gröbner" .
- ^ Chen, X .; Reed, ES; Helleseth, T .; Truong, TK (1994). "Uso de bases de Gröbner para decodificar códigos cíclicos binarios hasta la distancia mínima verdadera". Transacciones IEEE sobre teoría de la información . 40 (5): 1654–61. doi : 10.1109 / 18.333885 .
- ^ Fitzgerald, J .; Lax, RF (1998). "Decodificación de códigos de variedades afines utilizando bases de Gröbner". Diseños, Códigos y Criptografía . 13 (2): 147-158. doi : 10.1023 / A: 1008274212057 . S2CID 2515114 .
- ^ Bulygin, S .; Pellikaan, R. (2009). "Decodificación de códigos de corrección de errores lineales hasta la mitad de la distancia mínima con bases Gröbner". Bases de Gröbner, codificación y criptografía . Saltador. págs. 361–5. ISBN 978-3-540-93805-7.
Otras lecturas
- Adams, William W .; Loustaunau, Philippe (1994). Introducción a las bases de Gröbner . Estudios de Posgrado en Matemáticas . 3 . Sociedad Matemática Estadounidense . ISBN 0-8218-3804-0.
- Li, Huishi (2011). Bases de Gröbner en la teoría de anillos . World Scientific. ISBN 978-981-4365-13-0.
- Becker, Thomas; Weispfenning, Volker (1998). Bases Gröbner . Textos de Posgrado en Matemáticas. 141 . Saltador. ISBN 0-387-97971-9.
- Buchberger, Bruno (1965). Un algoritmo para encontrar los elementos básicos del anillo de clases de residuos de un ideal polinomial de dimensión cero (PDF) (PhD). Universidad de Innsbruck.- (2006). Traducido por Abramson, M. "Tesis doctoral de Bruno Buchberger 1965: Un algoritmo para encontrar los elementos base del anillo de clases de residuos de un ideal polinomial de dimensión cero" . Revista de Computación Simbólica . 41 (3–4): 471–511. doi : 10.1016 / j.jsc.2005.09.007 . [Esta es la tesis de Buchberger sobre la invención de las bases de Gröbner].
- Buchberger, Bruno (1970). "Un criterio algorítmico para la solubilidad de un sistema de ecuaciones algebraicas" (PDF) . Aequationes Mathematicae . 4 : 374–383. doi : 10.1007 / BF01844169 . S2CID 189834323 . (Esta es la publicación en revista de la tesis de Buchberger). Burchberger, B .; Winkler, F., eds. (26 de febrero de 1998). "Un criterio algorítmico para la solubilidad de un sistema de ecuaciones algebraicas" . Bases y aplicaciones de Gröbner . Serie de notas de conferencias de la London Mathematical Society. 251 . Prensa de la Universidad de Cambridge. págs. 535–545. ISBN 978-0-521-63298-0.
- Buchberger, Bruno; Kauers, Manuel (2010). "Bases de Gröbner" . Scholarpedia . 5 (10): 7763. doi : 10.4249 / scholarpedia.7763 .
- Fröberg, Ralf (1997). Introducción a las bases de Gröbner . Wiley. ISBN 0-471-97442-0.
- Sturmfels, Bernd (noviembre de 2005). "¿Qué es ... una base Gröbner?" (PDF) . Avisos de la Sociedad Matemática Estadounidense . 52 (10): 1199–1200, una breve introducciónCS1 maint: posdata ( enlace )
- Shirshov, Anatoliĭ I. (1999). "Ciertos problemas algorítmicos para álgebras de Lie" (PDF) . Boletín ACM SIGSAM . 33 (2): 3–6. doi : 10.1145 / 334714.334715 . S2CID 37070503 .(traducido de Sibirsk. Mat. Zh. Siberian Mathematics Journal 3 (1962), 292-296).
- Aschenbrenner, Matthias ; Hillar, Christopher (2007). "Generación finita de ideales simétricos" . Transacciones de la American Mathematical Society . 359 (11): 5171–92. doi : 10.1090 / S0002-9947-07-04116-5 . S2CID 5656701 . (sobre bases de Gröbner de dimensión infinita para anillos polinomiales en infinitos indeterminados).
enlaces externos
- La propia implementación de Faugère de su algoritmo F4
- "Base de Gröbner" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
- Buchberger, B. (2003). "Bases de Gröbner: una breve introducción para teóricos de sistemas" (PDF) . En Moreno-Diaz, R .; Buchberger, B .; Freire, J. (eds.). Teoría de los sistemas asistidos por computadora - EUROCAST 2001: Selección de artículos del 8º Taller Internacional de Teoría de los Sistemas Asistidos por Computadora . Saltador. págs. 1–19. ISBN 978-3-540-45654-4.
- Buchberger, B .; Zapletal, A. "Bibliografía de bases de Gröbner" .
- Página de tiempos comparativos para el software Gröbner Bases
- Prof. Bruno Buchberger Bruno Buchberger
- Weisstein, Eric W. "Gröbner Basis" . MathWorld .
- Introducción básica de Gröbner en Scholarpedia