base de gröbner

Construcción matemática en álgebra informática.

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 ₁ ,..., 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ón y 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 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 multivariada y no lineal tanto del algoritmo de Euclides para calcular el máximo común divisor polinómico como de la eliminación gaussiana para sistemas lineales. ^[1]

Las bases de Gröbner fueron introducidas por Bruno Buchberger en su doctorado de 1965. tesis, que también incluía un algoritmo para calcularlos ( algoritmo de Buchberger ). Los nombró en honor a su asesor Wolfgang Gröbner . En 2007, Buchberger recibió el Premio París Kanellakis de Teoría y Práctica de la Asociación de Maquinaria de Computación por 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 medida ignorados por la comunidad matemática hasta su redescubrimiento en 1987 por Bodo Renschuch et al. ^[2] Heisuke Hironaka desarrolló de forma independiente un concepto análogo para series de potencias multivariadas en 1964, quien las denominó bases estándar . Algunos autores han utilizado este término para denominar también las bases de Gröbner.

La teoría de las bases de Gröbner ha sido ampliada por muchos autores 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 conmutativos, como las álgebras de Ore .

Herramientas

Anillo polinómico

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 la base de Gröbner se realizan cuando K es el campo de los racionales o los números enteros módulo de un número primo. ${\displaystyle R=K[x_{1},\ldots ,x_{n}]}$

En el contexto de las bases de Gröbner, un polinomio in distinto de cero se representa comúnmente como una suma en la que son elementos distintos de cero de K , llamados coeficientes , y son monomios (llamados productos de potencia por Buchberger y algunos de sus seguidores) de la forma en la que son enteros no negativos. El vector se llama vector exponente del monomio. Cuando la lista de variables es fija, la notación de monomios a menudo se abrevia como ${\displaystyle R=K[x_{1},\ldots ,x_{n}]}$ ${\displaystyle c_{1}M_{1}+\cdots +c_{m}M_{m},}$ ${\displaystyle c_{i}}$ ${\displaystyle M_{i}}$ ${\displaystyle x_{1}^{a_{1}}\cdots x_{n}^{a_{n}},}$ ${\displaystyle a_{i}}$ ${\displaystyle A=[a_{1},\ldots ,a_{n}]}$ ${\displaystyle X=[x_{1},\ldots ,x_{n}]}$ ${\displaystyle x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}=X^{A}.}$

Los monomios se definen de forma única por sus vectores exponentes y, cuando se fija el orden de un monomio (ver más abajo), un polinomio se representa de forma única mediante la lista ordenada de pares ordenados formados por un vector exponente y el coeficiente correspondiente. Esta representación de polinomios es especialmente eficiente para el cálculo de bases de Gröbner en computadoras, aunque es menos conveniente para otros cálculos como la factorización de polinomios y el máximo común divisor de polinomios .

Si es un conjunto finito de polinomios en el anillo polinomial R , el ideal generado por F es el conjunto de combinaciones lineales de elementos de F con coeficientes en R ; ese es el conjunto de polinomios que se pueden escribir con ${\displaystyle F=\{f_{1},\ldots ,f_{k}\}}$ ${\textstyle \sum _{i=1}^{k}g_{i}f_{i}}$ ${\displaystyle g_{1},\ldots ,g_{k}\in R.}$

Orden monomio

Todas las operaciones relacionadas con las bases de Gröbner requieren la elección de un orden total sobre los monomios, con las siguientes propiedades de compatibilidad con la multiplicación. Para todos los monomios M , N , P ,

1. ${\displaystyle M\leq N\Longleftrightarrow MP\leq NP}$
2. ${\displaystyle M\leq MP}$.

Un orden total que satisface estas condiciones a veces se denomina ordenamiento admisible .

Estas condiciones implican que el orden es un buen orden , es decir, toda secuencia estrictamente decreciente de monomios es finita.

Aunque la teoría de bases de Gröbner no depende de una elección particular de un ordenamiento de monomios admisible, tres ordenamientos de monomios son especialmente importantes para las aplicaciones:

• Ordenamiento lexicográfico , comúnmente llamado lex o plex (por orden léxico puro).
• Orden lexicográfico inverso de grado total , comúnmente llamado degrevlex .
• Orden de eliminación , lexdeg .

La teoría de bases de Gröbner se introdujo inicialmente para el ordenamiento lexicográfico. Pronto se dio cuenta de 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 es necesaria la eliminación, degrevlex no es conveniente; Se pueden usar tanto lex como lexdeg pero, nuevamente, muchos cálculos son relativamente fáciles con lexdeg y casi imposibles con lex.

Operaciones básicas

Término principal, coeficiente y monomio.

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 mediante monomios decrecientes (para este orden). Esto hace que la representación de un polinomio como una lista ordenada de pares de vector coeficiente-exponente sea una representación canónica de los polinomios (es decir, dos polinomios son iguales si y solo tienen la misma representación).

El primer término (mayor) de un polinomio p para este orden y el monomio y coeficiente correspondientes se denominan respectivamente término principal , monomio principal y coeficiente principal y se denotan, en este artículo, lt( p ), lm( p ) y lc( pag ) .

La mayoría de las operaciones polinómicas relacionadas con las bases de Gröbner involucran los términos principales. Así, la representación de polinomios como listas ordenadas hace que estas operaciones sean particularmente eficientes (leer el primer elemento de una lista lleva un tiempo constante, independientemente de la longitud de la lista).

Operaciones polinómicas

Las otras operaciones polinómicas involucradas en los cálculos de la base de Gröbner también son compatibles con el ordenamiento de los monomios; es decir, se pueden realizar sin reordenar el resultado:

• La suma de dos polinomios consiste en una fusión de las dos listas de términos correspondientes, con un tratamiento especial en caso de conflicto (es decir, cuando aparece el mismo monomio en los dos polinomios).
• La multiplicación de un polinomio por un escalar consiste en multiplicar cada coeficiente por este escalar, sin ningún otro cambio en la representación.
• La multiplicación de un polinomio por un monomio m consiste en multiplicar cada monomio del polinomio por m . Esto no cambia el término ordenamiento por definición de ordenamiento monomio.

Divisibilidad de monomios

Sean y dos monomios, con vectores exponentes y ${\displaystyle M=x_{1}^{a_{1}}\cdots x_{n}^{a_{n}}}$ ${\displaystyle N=x_{1}^{b_{1}}\cdots x_{n}^{b_{n}}}$ ${\displaystyle A=[a_{1},\ldots ,a_{n}]}$ ${\displaystyle B=[b_{1},\ldots ,b_{n}].}$

Se dice que M divide a N , o que N es múltiplo de M , si para cada i ; es decir, si A no es mayor que B en sus componentes . En este caso, el cociente se define como En otras palabras, el vector exponente de es la resta por componentes de los vectores exponentes de N y M. ${\displaystyle a_{i}\leq b_{i}}$ ${\textstyle {\frac {N}{M}}}$ ${\textstyle {\frac {N}{M}}=x_{1}^{b_{1}-a_{1}}\cdots x_{n}^{b_{n}-a_{n}}.}$ ${\textstyle {\frac {N}{M}}}$

El máximo común divisor mcd( M , N ) de M y N es el monomio cuyo vector exponente es el mínimo por componentes de A y B. El mínimo común múltiplo mcm( M , N ) se define de manera similar con max en lugar de min . ${\textstyle x_{1}^{\min(a_{1},b_{1})}\cdots x_{n}^{\min(a_{n},b_{n})}}$

Uno tiene

${\displaystyle \operatorname {lcm} (M,N)={\frac {MN}{\gcd(M,N)}}.}$

Reducción

La reducción de un polinomio por otros polinomios con respecto al orden de un monomio es fundamental para la teoría de bases de Gröbner. Es una generalización de la reducción de filas que ocurre en los pasos de eliminación y división gaussiana de la división euclidiana de polinomios univariados . ^[1] Cuando se completa tanto como sea posible, a veces se le llama división multivariada, aunque su resultado no está definido de forma única.

La reducción de plomo es un caso especial de reducción que es más fácil de calcular. Es fundamental para el cálculo de la base de Gröbner, ya que la reducción general sólo es necesaria al final de un cálculo de la base de Gröbner, para obtener una base de Gröbner reducida a partir de una no reducida.

Fijemos un orden de monomios admisible, al que se refiere cada comparación de monomios que se realizará en esta sección.

Un polinomio f es reducible en plomo por otro polinomio g si el monomio principal lm( f ) es múltiplo de lm( g ) . El polinomio f es reducible por g si algún monomio de f es múltiplo de lm( g ) . (Entonces, si f es reducible con plomo por g , también es reducible, pero f puede ser reducible sin serlo con plomo).

Supongamos que f es reducible por g y sea cm un término de f tal que el monomio m sea múltiplo de lm( g ) . Una reducción en un paso de f por g consiste en reemplazar f por

${\displaystyle \operatorname {red} _{1}(f,g)=f-{\frac {c}{\operatorname {lc} (g)}}\,{\frac {m}{\operatorname {lm} (g)}}\,g.}$

Esta operación elimina el monomio m de f sin cambiar los términos con un monomio mayor que m (para el orden de los monomios). En particular, una reducción de un paso de f produce un polinomio cuyos monomios son más pequeños que lm( f ) .

Dado un conjunto finito G de polinomios, se dice que f es reducible o reducible en plomo por G si es reducible o reducible en plomo, respectivamente, por al menos un elemento g de G . En este caso, una reducción de un paso (resp. reducción de avance de un paso) de f por G es cualquier reducción de un paso (resp. reducción de avance de un paso) de f por un elemento de G.

La reducción (completa) (respectivamente, reducción principal) de f por G consiste en iterar reducciones de un paso (respectivamente, reducciones principales de un paso) hasta obtener un polinomio que es irreducible (resp. irreducible) por G . A veces se le llama forma normal de f por G . En general, esta forma no está definida de forma única porque, en general, hay varios elementos de G que pueden usarse para reducir f ; esta no unicidad es el punto de partida de la teoría de bases de Gröbner.

La definición de la reducción muestra inmediatamente que, si h es una forma normal de f por G , se tiene

${\displaystyle f=h+\sum _{g\in G}q_{g}\,g,}$

donde h es irreducible por G y son polinomios tales que 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 , y q _g es el cociente. Además, el algoritmo de división es exactamente el proceso de reducción de leads. Por esta razón, algunos autores utilizan el término división multivariada en lugar de reducción. ${\displaystyle q_{g}}$ ${\displaystyle \operatorname {lm} (q_{g}\,g)\leq \operatorname {lm} (f).}$

No unicidad de la reducción

En el ejemplo siguiente, hay exactamente dos reducciones de plomo completas que producen dos resultados muy diferentes. El hecho de que los resultados sean irreducibles (no sólo irreducibles con plomo) es específico del ejemplo, aunque esto es bastante común en ejemplos tan pequeños.

En este ejemplo de dos variables, el orden monomial que se utiliza es el orden lexicográfico con y consideramos la reducción de ${\displaystyle x>y,}$

$${\displaystyle f=2x^{3}-x^{2}y+y^{3}+3y}$$

${\displaystyle G=\{g_{1},g_{2}\},}$

$${\displaystyle {\begin{aligned}g_{1}&=x^{2}+y^{2}-1,\\g_{2}&=xy-2.\end{aligned}}}$$

Para el primer paso de reducción, se puede reducir el primer o el segundo término de f . Sin embargo, la reducción de un plazo equivale a eliminar dicho plazo a costa de añadir nuevos términos inferiores; si no es el primer término reducible el que se reduce, puede ocurrir que una reducción adicional agregue un término similar, que deba reducirse nuevamente. Por lo tanto, siempre es mejor reducir primero el término reducible más grande (para el orden monomio); es decir, en particular, conducir-reducir primero hasta obtener un polinomio plomo-irreducible.

El término principal de f es reducible por y no por Por lo tanto, el primer paso de reducción consiste en multiplicar por –2 x y sumar el resultado a f : ${\displaystyle 2x^{3}}$ ${\displaystyle g_{1}}$ ${\displaystyle g_{2}.}$ ${\displaystyle g_{1}}$

${\displaystyle f\;{\overset {-2xg_{1}}{\longrightarrow }}\;f_{1}=f-2xg_{1}=-x^{2}y-2xy^{2}+2x+y^{3}+3y.}$

El término principal de es un múltiplo de los monomios principales de ambos y Entonces, uno tiene dos opciones para el segundo paso de reducción. Si uno elige, obtiene un polinomio que se puede reducir nuevamente por ${\displaystyle -x^{2}y}$ ${\displaystyle f_{1}}$ ${\displaystyle g_{1}}$ ${\displaystyle g_{2},}$ ${\displaystyle g_{2},}$ ${\displaystyle g_{2}\colon }$

${\displaystyle f\;{\overset {-2xg_{1}}{\longrightarrow }}\;f_{1}\;{\overset {xg_{2}}{\longrightarrow }}\;-2xy^{2}+y^{3}+3y\;{\overset {2yg_{2}}{\longrightarrow }}\;f_{2}=y^{3}-y.}$

No es posible ninguna reducción adicional, al igual que una reducción completa de f . ${\displaystyle f_{2}}$

Uno obtiene un resultado diferente con la otra opción para el segundo paso:

${\displaystyle f\;{\overset {-2xg_{1}}{\longrightarrow }}\;f_{1}\;{\overset {yg_{1}}{\longrightarrow }}\;-2xy^{2}+2x+2y^{3}+2y\;{\overset {2yg_{2}}{\longrightarrow }}\;f_{3}=2x+2y^{3}-2y.}$

Una vez más, el resultado es irreducible, aunque sólo se hicieron reducciones de plomo. ${\displaystyle f_{3}}$

En resumen, la reducción completa de f puede resultar en uno o ${\displaystyle f_{2}=y^{3}-y}$ ${\displaystyle f_{3}=2x+2y^{3}-2y.}$

Para abordar los problemas planteados por esta no unicidad, Buchberger introdujo las bases de Gröbner y los polinomios S. Intuitivamente, 0 = f − f puede reducirse a Esto implica que pertenece al ideal generado por G . Entonces, este ideal no cambia agregando a G , y esto permite más reducciones. En particular, se puede reducir a by y esto restablece la unicidad de la forma reducida. ${\displaystyle f_{2}-f_{3}.}$ ${\displaystyle f_{2}-f_{3}}$ ${\displaystyle f_{3}-f_{2}}$ ${\displaystyle f_{3}}$ ${\displaystyle f_{2}}$ ${\displaystyle f_{3}-f_{2}}$

Aquí el algoritmo de Buchberger para bases de Gröbner comenzaría sumando a G el polinomio

${\displaystyle g_{3}=yg_{1}-xg_{2}=2x+y^{3}-y.}$

Este polinomio, llamado S -polinomio por Buchberger, es la diferencia de las reducciones en un paso del mínimo común múltiplo de los monomios principales de y (en este ejemplo, se tiene. Esto no completa el algoritmo de Buchberger, ya que xy da resultados diferentes, cuando reducido por o ${\displaystyle x^{2}y}$ ${\displaystyle g_{1}}$ ${\displaystyle g_{2}}$ ${\displaystyle g_{3}=f_{3}-f_{2}).}$ ${\displaystyle g_{2}}$ ${\displaystyle g_{3}.}$

S -polinomio

El polinomio S , también llamado par crítico , con respecto a un orden monomio dado, de dos polinomios f y g es el polinomio

${\displaystyle {\begin{aligned}S(f,g)&=\operatorname {red} _{1}(\mathrm {lcm} ,g)-\operatorname {red} _{1}(\mathrm {lcm} ,f)\\&={\frac {1}{\operatorname {lc} (f)}}\,{\frac {\operatorname {lm} (g)}{\mathrm {gcd} }}\,f-{\frac {1}{\operatorname {lc} (g)}}\,{\frac {\operatorname {lm} (f)}{\mathrm {gcd} }}\,g,\end{aligned}}}$

donde mcm y mcd denotan respectivamente el mínimo común múltiplo y el máximo común divisor de los monomios principales de f y g .

Como los monomios que son reducibles tanto por f como por g son exactamente múltiplos de lcm , se pueden abordar todos los casos de no unicidad de la reducción considerando solo los S -polinomios. Este es un hecho fundamental para la teoría de bases de Gröbner y todos los algoritmos para calcularlas.

Definición

Sea un anillo polinomial sobre un campo F . En esta sección, suponemos que se ha fijado un orden de monomio admisible. ${\displaystyle R=F[x_{1},\ldots ,x_{n}]}$

Sea G un conjunto finito de polinomios en R que genera un I ideal . El conjunto G es una base de Gröbner (con respecto al ordenamiento de los monomios), o, más precisamente, una base de Gröbner de I si

1. el ideal generado por los monomios principales de los polinomios en I es igual al ideal generado por los monomios principales de G ,

o equivalente,

2. el monomio principal de todo polinomio en I es un múltiplo del monomio principal de algún polinomio en G.

Hay muchas propiedades caracterizantes, cada una de las cuales puede tomarse como una definición equivalente de las bases de Gröbner. Para ser concisos, en la siguiente lista, la notación "una palabra/otra palabra" significa que se puede tomar "una palabra" u "otra palabra" por tener dos caracterizaciones diferentes de las bases de Gröbner. Todas las siguientes afirmaciones son caracterizaciones de las bases de Gröbner:

3. un polinomio f está en I , si y sólo si alguna/cada reducción/reducción completa de f por G produce el polinomio cero;
4. para cada S -polinomio s de elementos de G , alguna/cada reducción/reducción completa de s por G produce cero;
5. todas las reducciones completas de un elemento de R producen el mismo resultado;
6. los monomios que son irreducibles por G forman una base del espacio vectorial F ${\displaystyle R/I.}$

Contando la definición anterior, esto proporciona 12 caracterizaciones de bases de Gröbner. El hecho de que sean posibles tantas caracterizaciones hace que las bases de Gröbner sean muy útiles. Por ejemplo, la condición 3 proporciona un algoritmo para probar la membresía ideal ; la condición 4 proporciona un algoritmo para probar si un conjunto de polinomios es una base de Gröbner y forma la base del algoritmo de Buchberger para calcular las bases de Gröbner; Las condiciones 5 y 6 permiten calcular de una manera muy similar a la aritmética modular . ${\displaystyle R/I}$

Existencia de bases Gröbner. Para cada ordenamiento de monomios admisible y cada conjunto finito G de polinomios, existe una base de Gröbner que contiene G y genera el mismo ideal. Además, dicha base de Gröbner puede calcularse con el algoritmo de Buchberger .

Este algoritmo utiliza la condición 4 y procede aproximadamente de la siguiente manera: suma a G todos los resultados distintos de cero de una reducción completa por G de un polinomio S de dos elementos de G ; repita esta operación con los nuevos elementos de G incluidos hasta que, eventualmente, todas las reducciones produzcan cero. El algoritmo termina siempre debido al lema de Dickson o porque los anillos polinomiales son noetherianos ( teorema de la base de Hilbert ). La condición 4 asegura que el resultado sea una base de Gröbner.

Bases de Gröbner reducidas

Una base de Gröbner esmínimo si todos los monomios principales de sus elementos son irreducibles por los demás elementos de la base. Dada una base de Gröbner de un idealI, se obtiene una base de Gröbner mínima deIeliminando los polinomios cuyos monomios principales son múltiplos del monomio principal de otro elemento de la base de Gröbner. Sin embargo, si dos polinomios de la base tienen el mismo monomio principal, sólo se debe eliminar uno. Entonces, cada base de Gröbner contiene una base de Gröbner mínima como subconjunto.

Todas las bases de Gröbner mínimas de un ideal dado (para un orden de monomio fijo) tienen el mismo número de elementos y los mismos monomios principales, y las bases de Gröbner no mínimas tienen más elementos que las mínimas.

Una base de Gröbner esreducido si cada polinomio que contiene es irreducible por los demás elementos de la base y tiene1como coeficiente principal. Por lo tanto, cada base de Gröbner reducida es mínima, pero no es necesario reducir una base de Gröbner mínima.

Dada una base de Gröbner de un ideal I , se obtiene una base de Gröbner reducida de I eliminando primero los polinomios que son reducibles en plomo por otros elementos de la base (para obtener una base mínima); reemplazando luego cada elemento de la base por el resultado de la reducción completa por los demás elementos de la base; y, finalmente, dividiendo cada elemento de la base por su coeficiente principal.

Todas las bases de Gröbner reducidas de un ideal (para un orden monomio fijo) son iguales. De ello se deduce que dos ideales son iguales si y sólo si tienen la misma base de Gröbner reducida.

A veces, las bases de Gröbner reducidas se definen sin la condición de los coeficientes principales. En este caso, la unicidad de las bases de Gröbner reducidas es cierta sólo hasta la multiplicación de polinomios por una constante distinta de cero.

Cuando se trabaja con polinomios sobre el cuerpo de los números racionales , es útil trabajar sólo con polinomios con coeficientes enteros. En este caso, la condición sobre los coeficientes principales en la definición de una base reducida puede reemplazarse por la condición de que todos los elementos de la base sean polinomios primitivos con coeficientes enteros, con coeficientes principales positivos. Esto restaura la singularidad de las bases reducidas. ${\displaystyle \mathbb {Q} }$

En la mayoría de las implementaciones del cálculo de bases de Gröbner, las bases de Gröbner que se generan siempre se reducen. ^{[ cita necesaria ]}

Casos especiales

Para cada ordenamiento de monomios, el conjunto vacío de polinomios es la única base de Gröbner del ideal cero .

Para cada ordenamiento de monomios, un conjunto de polinomios que contiene una constante distinta de cero es una base de Gröbner del ideal unitario (el anillo polinómico completo). Por el contrario, cada base de Gröbner del ideal unitario contiene una constante distinta de cero. La base de Gröbner reducida de la unidad está formada por el polinomio simple 1 .

En el caso de polinomios de una sola variable, existe un único ordenamiento de monomios admisible, el ordenamiento por grados. Las bases mínimas de Gröbner son los singleton que constan de un solo polinomio. Las bases de Gröbner reducidas son los polinomios mónicos .

Ejemplo y contraejemplo

Los ceros de forman la parábola roja; los ceros de forman las tres líneas verticales azules. Su intersección consta de tres puntos. ${\displaystyle f}$ ${\displaystyle g}$

Sea el anillo de polinomios bivariados con coeficientes racionales y consideremos el ideal generado por los polinomios. ${\displaystyle R=\mathbb {Q} [x,y]}$ ${\displaystyle I=\langle f,g\rangle }$

${\displaystyle f=x^{2}-y}$,

${\displaystyle g=x^{3}-x}$.

Reduciendo g por f , se obtiene un nuevo polinomio k tal que ${\displaystyle I=\langle f,k\rangle :}$

${\displaystyle k=g-xf=xy-x.}$

Ninguno de f y k es reducible por el otro, pero xk es reducible por f , lo que da otro polinomio en I :

${\displaystyle h=xk-(y-1)f=y^{2}-y.}$

Bajo orden lexicográfico con tenemos ${\displaystyle x>y}$

lt( f ) = x ²

lt( k ) = xy

lt( h ) = y ²

Como f , k y h pertenecen a I , y ninguno de ellos es reducible por los demás, ninguno de y es una base de Gröbner de I . ${\displaystyle \{f,k\},}$ ${\displaystyle \{f,h\},}$ ${\displaystyle \{h,k\}}$

Por otro lado, { f , k , h } es una base de Gröbner de I , ya que los S-polinomios

${\displaystyle {\begin{aligned}yf-xk&=y(x^{2}-y)-x(xy-x)=f-h\\yk-xh&=y(xy-x)-x(y^{2}-y)=0\\y^{2}f-x^{2}h&=y(yf-xk)+x(yk-xh)\end{aligned}}}$

se puede reducir a cero mediante f , k y h .

El método que se ha utilizado aquí para encontrar hyk y demostrar que { f , k , h } es una base de Gröbner es una aplicación directa del algoritmo de Buchberger . Por lo tanto, se puede aplicar mecánicamente a cualquier ejemplo similar, aunque, en general, hay muchos polinomios y polinomios S que considerar, y el cálculo generalmente es demasiado grande para realizarlo sin una computadora.

Propiedades y aplicaciones de las bases de Gröbner.

A menos que se indique explícitamente, todos los resultados que siguen ^[3] son ​​verdaderos para cualquier orden monomial (consulte ese artículo para conocer las definiciones de los diferentes órdenes que se mencionan a continuación).

Es un error común pensar que se necesita el orden lexicográfico 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 poco prácticos 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 monomio. Por tanto, dos ideales son iguales si y sólo si tienen la misma base de Gröbner (reducida) (normalmente un software de bases de Gröbner siempre produce bases de Gröbner reducidas).

Pertenencia e inclusión de ideales

La reducción de un polinomio f por la base de Gröbner G de un ideal I produce 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 comprobar que la base de Gröbner de G ∪{ f } es igual a G .

Para comprobar si el ideal I generado por f ₁ , ..., f _k está contenido en el ideal J , basta comprobar que todo f _I está en J . También se puede probar la igualdad de las bases de Gröbner reducidas de J y J ∪ { f ₁ , ..., f _k } .

Soluciones de un sistema de ecuaciones algebraicas.

Cualquier conjunto de polinomios puede verse como un sistema de ecuaciones polinómicas igualando los polinomios a cero. El conjunto de soluciones de dicho sistema depende únicamente del ideal generado y, por lo tanto, no cambia cuando el conjunto generador 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 ningún cero (el sistema de ecuaciones es inconsistente ) si y sólo si 1 pertenece al ideal (este es el Nullstellensatz de Hilbert ), o, de manera equivalente, si su base de Gröbner (para cualquier orden monomial) contiene 1, o, además, si la base de Gröbner reducida correspondiente es [1].

Dada la base de Gröbner G de un ideal I , tiene sólo un número finito de ceros, si y sólo si, para cada variable x , G contiene un polinomio con un monomio principal que es una potencia de x (sin que aparezca ninguna otra variable en el término principal). Si este es el caso, entonces el número de ceros, contados con multiplicidad , es igual al número de monomios que no son múltiplos de ningún monomio principal de G. Este número se llama grado del ideal.

Cuando el número de ceros es finito, la base de Gröbner para el ordenamiento lexicográfico de monomios proporciona, teóricamente, una solución: la primera coordenada de una solución es la raíz del máximo común divisor de polinomios de la base que dependen únicamente de la primera variable. Después de sustituir esta raíz en la base, la segunda coordenada de esta solución es una raíz del máximo común divisor de los polinomios resultantes que dependen sólo de la segunda variable, y así sucesivamente. Este proceso de resolución es sólo teórico, porque implica el cálculo del MCD y la búsqueda de raíces de polinomios con coeficientes aproximados, que no son practicables debido a la inestabilidad numérica. Por ello, se han desarrollado otros métodos para resolver sistemas polinomiales mediante bases de Gröbner (ver Sistema de ecuaciones polinómicas para más detalles).

Dimensión, grado y serie de Hilbert.

La dimensión de un ideal I en un anillo polinómico R es la dimensión de Krull del anillo R / I y es igual a la dimensión del conjunto algebraico 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 monomios principales de la base de Gröbner del ideal para cualquier orden de monomios.

La dimensión es el tamaño máximo de un subconjunto S de las variables tal que no existe un monomio principal que dependa únicamente de las variables en S. Por 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 , donde 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 resumir en una fracción racional. ${\textstyle \sum _{i=0}^{\infty }d_{i}t^{i}}$ ${\displaystyle d_{i}}$

${\displaystyle \sum _{i=0}^{\infty }d_{i}t^{i}={\frac {P(t)}{(1-t)^{d}}},}$

donde d es la dimensión del ideal y es un polinomio tal que es el grado del ideal. ${\displaystyle P(t)}$ ${\displaystyle P(1)}$

Aunque la dimensión y el grado no dependen de la elección del orden de los monomios, la serie de Hilbert y el polinomio cambian cuando se cambia el orden de los monomios. ${\displaystyle P(t)}$

La mayoría de los sistemas de álgebra informática 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 polinómico en el que las variables se dividen en dos subconjuntos X e Y. Elijamos también un orden monomio de eliminación "eliminando" X , es decir, un orden monomio para el cual 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 variable X es mayor que todo monomio independiente de X. Si G es una base de Gröbner de un ideal I para este orden monomial, entonces es una base de Gröbner de (este ideal a menudo se denomina ideal de eliminación ). Además, consta exactamente de los polinomios de G cuyos términos principales pertenecen a K [ Y ] (esto facilita el cálculo de , ya que sólo es necesario verificar los monomios principales). ${\displaystyle K[x_{1},\ldots ,x_{n},y_{1},\ldots ,y_{m}]=K[X,Y],}$ ${\displaystyle G\cap K[Y]}$ ${\displaystyle I\cap K[Y]}$ ${\displaystyle G\cap K[Y]}$ ${\displaystyle G\cap K[Y]}$

Esta propiedad de eliminación tiene muchas aplicaciones, algunas de las cuales 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, la ( cierre de Zariski de) la proyección del conjunto algebraico definido por el ideal I en el subespacio Y está definido por el ideal ${\displaystyle I\cap K[Y].}$

El orden lexicográfico es un orden de eliminación para cada partición. Por lo tanto, una base de Gröbner para este orden contiene mucha más información de la que normalmente es necesaria. Esto puede explicar por qué las bases de Gröbner para el orden lexicográfico suelen ser las más difíciles de calcular. ${\displaystyle x_{1}>\cdots >x_{n}}$ ${\displaystyle \{x_{1},\ldots ,x_{k}\},\{x_{k+1},\ldots ,x_{n}\}.}$

Ideales que se cruzan

Si I y J son dos ideales generados respectivamente por { f ₁ , ..., f _m } y { g ₁ , ..., g _k }, entonces un cálculo de una sola base de Gröbner produce una base de Gröbner de su intersección I ∩ J . Para esto, se introduce un nuevo indeterminado t y se usa un orden de eliminación tal que el primer bloque contiene solo t y el otro bloque contiene todas las demás variables (esto significa que un monomio que contiene t es mayor que todo monomio que no contiene t ). Con este ordenamiento de monomios, una base de Gröbner de I ∩ J consiste en los polinomios que no contienen t , en la base de Gröbner del ideal

${\displaystyle K=\langle tf_{1},\ldots ,tf_{m},(1-t)g_{1},\ldots ,(1-t)g_{k}\rangle .}$

En otras palabras, I  ∩  J se obtiene eliminando t en K . Esto puede demostrarse observando que el K ideal está formado por polinomios tales que y . Tal polinomio es independiente de t si y sólo si a = b , lo que significa que ${\displaystyle (a-b)t+b}$ ${\displaystyle a\in I}$ ${\displaystyle b\in J}$ ${\displaystyle b\in I\cap J.}$

Implicitización de una curva racional.

Una curva racional es una curva algebraica que tiene un conjunto de ecuaciones paramétricas de la forma

${\displaystyle {\begin{aligned}x_{1}&={\frac {f_{1}(t)}{g_{1}(t)}}\\&\;\;\vdots \\x_{n}&={\frac {f_{n}(t)}{g_{n}(t)}},\end{aligned}}}$

donde y son polinomios univariados para 1 ≤ i ≤ n . Uno puede (y lo hará) suponer que y son coprimos (no tienen factores comunes no constantes). ${\displaystyle f_{i}(t)}$ ${\displaystyle g_{i}(t)}$ ${\displaystyle f_{i}(t)}$ ${\displaystyle g_{i}(t)}$

La implicitización 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:

${\displaystyle {\text{Res}}_{t}(g_{1}x_{1}-f_{1},g_{2}x_{2}-f_{2}).}$

La eliminación con bases de Gröbner permite implícitamente para cualquier valor de n , simplemente eliminando t en el ideal Si n = 2, el resultado es el mismo que con la resultante, si el mapa es inyectivo para casi todo t . En el otro caso, la resultante es una potencia del resultado de la eliminación. ${\displaystyle \langle g_{1}x_{1}-f_{1},\ldots ,g_{n}x_{n}-f_{n}\rangle .}$ ${\displaystyle t\mapsto (x_{1},x_{2})}$

Saturación

Al modelar un problema mediante ecuaciones polinómicas, a menudo se supone que algunas cantidades son distintas de cero, para evitar casos degenerados. Por ejemplo, cuando se trata de triángulos , muchas propiedades se vuelven falsas si el triángulo degenera a un segmento de línea, es decir, la longitud de un lado es igual a la suma de las longitudes de los otros lados. En tales situaciones, no se puede deducir información relevante del sistema polinomial a menos que se ignoren las soluciones degeneradas. Más precisamente, el sistema de ecuaciones define un conjunto algebraico que puede tener varios componentes irreducibles , 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 con las condiciones de degeneración, lo que se puede hacer mediante 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 unirle las inversas formales de algunos elementos. Esta sección se refiere únicamente al caso de un solo elemento, o equivalentemente a un número finito de elementos (unir las inversas de varios elementos equivale a unir la inversa de su producto). La localización de un anillo R por un elemento f es el anillo donde 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 polinómico, el cálculo no es eficiente debido a la necesidad de gestionar los denominadores. Por tanto, la localización suele ser sustituida por la operación de saturación . ${\displaystyle R_{f}=R[t]/(1-ft),}$ ${\displaystyle R_{f}I}$ ${\displaystyle I_{f}.}$ ${\displaystyle R_{f}}$

ElLa saturación con respecto afde un idealIenRes la imagen inversa debajo la aplicación canónica deRaEs el idealque consiste en todos los elementos deRcuyo producto con alguna potencia defperteneceaI. ${\displaystyle R_{f}I}$ ${\displaystyle R_{f}.}$ ${\displaystyle I:f^{\infty }=\{g\in R\mid (\exists k\in \mathbb {N} )f^{k}g\in I\}}$

Si J es el ideal generado por I y 1 − ft en R [ t ], entonces se deduce que, si R es un anillo polinomial, un cálculo en base de Gröbner que elimina t produce una base de Gröbner de la saturación de un ideal por un polinomio. ${\displaystyle I:f^{\infty }=J\cap R.}$

La propiedad importante de la saturación, que asegura que elimina del conjunto algebraico definido por el ideal I las componentes irreducibles en las que el polinomio f es cero, es la siguiente: La descomposición primaria de consta de las componentes de la descomposición primaria de I que no contienen ningún poder de f . ${\displaystyle I:f^{\infty }}$

Cálculo de la saturación.

Se puede obtener una base de Gröbner de la saturación por f de un polinomio ideal generado por un conjunto finito de polinomios F eliminando t , es decir, manteniendo los polinomios independientes de t en la base de Gröbner para un orden de eliminación eliminando t . ${\displaystyle F\cup \{1-tf\},}$ ${\displaystyle F\cup \{1-tf\}}$

En lugar de utilizar F , también se puede partir de una base de Gröbner de F . El método 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 respecto de varios polinomios o respecto de un solo polinomio que es producto hay tres formas de proceder que dan el mismo resultado pero pueden tener tiempos de cálculo muy diferentes (depende del problema cuál es la más eficiente). ). ${\displaystyle f_{1},\ldots ,f_{k}}$ ${\displaystyle f=f_{1}\cdots f_{k},}$

• Saturando en un cálculo de base única de Gröbner. ${\displaystyle f=f_{1}\cdots f_{k}}$
• Saturando luego saturando el resultado y así sucesivamente. ${\displaystyle f_{1},}$ ${\displaystyle f_{2},}$
• Sumando a F o a su base de Gröbner los polinomios y eliminando el cálculo en una sola base de Gröbner. ${\displaystyle 1-t_{1}f_{1},\ldots ,1-t_{k}f_{k},}$ ${\displaystyle t_{i}}$

Nullstellensatz eficaz

El Nullstellensatz de Hilbert tiene dos versiones. El primero afirma que un conjunto de polinomios no tiene ceros comunes sobre una clausura algebraica del cuerpo de los coeficientes, si y sólo si 1 pertenece al ideal generado. Esto se prueba fácilmente con un cálculo de la base de Gröbner, porque 1 pertenece a un ideal si y sólo 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 una clausura algebraica del campo de los coeficientes) de un ideal está contenido en la hipersuperficie de los ceros de un polinomio f , si y sólo 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 sólo si la saturación por f proporciona una base de Gröbner que contiene 1.

Implicitización en una dimensión superior.

Por definición, una variedad racional afín de dimensión k puede describirse mediante ecuaciones paramétricas de la forma

${\displaystyle {\begin{aligned}x_{1}&={\frac {p_{1}}{p_{0}}}\\&\;\;\vdots \\x_{n}&={\frac {p_{n}}{p_{0}}},\end{aligned}}}$

donde hay 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 ${\displaystyle p_{0},\ldots ,p_{n}}$ ${\displaystyle t_{1},\ldots ,t_{k}.}$ ${\displaystyle t_{1},\ldots ,t_{k}}$ ${\displaystyle x_{1},\ldots ,x_{n}}$

${\displaystyle I=\left\langle p_{0}x_{1}-p_{1},\ldots ,p_{0}x_{n}-p_{n}\right\rangle .}$

Se podría suponer 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 tienen un cero común (a veces llamado punto base ), cada componente irreducible del conjunto algebraico no vacío definido por es un componente irreducible del conjunto algebraico definido por I. De ello se deduce que, en este caso, la eliminación directa de proporciona un conjunto vacío de polinomios. ${\displaystyle p_{i}}$ ${\displaystyle p_{i}}$ ${\displaystyle t_{i}}$

Por lo tanto, si k >1, se necesitan dos cálculos de base de Gröbner para implícitamente:

1. Saturar para obtener una base de Gröbner ${\displaystyle I}$ ${\displaystyle p_{0}}$ ${\displaystyle G}$
2. Elimina el de para obtener una base de Gröbner del ideal (de las ecuaciones implícitas) de la variedad. ${\displaystyle t_{i}}$ ${\displaystyle G}$

Algoritmos e implementaciones.

El algoritmo de Buchberger es el algoritmo más antiguo para calcular bases de Gröbner. Ha sido ideada por Bruno Buchberger junto con la teoría de bases de Gröbner. Es sencillo de implementar, pero pronto resultó que las implementaciones en bruto sólo pueden resolver problemas triviales. Las principales cuestiones son las siguientes:

1. Incluso cuando la base de Gröbner resultante es pequeña, los polinomios intermedios pueden ser enormes. El resultado es que la mayor parte del tiempo de cálculo puede dedicarse a la gestión de la memoria . Por tanto, los algoritmos especializados de gestión de memoria pueden ser una parte fundamental de una implementación eficiente.
2. Los números enteros que aparecen durante un cálculo pueden ser lo suficientemente grandes como para que los algoritmos de multiplicación rápida y la aritmética multimodular sean útiles. Por este motivo, la mayoría de las implementaciones optimizadas utilizan GMPlibrary . Además, en implementaciones optimizadas se utilizan la aritmética modular , el teorema del resto chino y el levantamiento de Hensel.
3. La elección de los polinomios S a reducir y de los polinomios utilizados para reducirlos está dedicada a la heurística . Como ocurre con muchos problemas computacionales, la heurística no puede detectar la mayoría de las simplificaciones ocultas y, si se evitan las elecciones heurísticas, se puede obtener una mejora espectacular de la eficiencia del algoritmo.
4. En la mayoría de los casos, la mayoría de los polinomios S que se calculan se reducen a cero; es decir, la mayor parte del tiempo de cálculo se dedica a calcular el cero.
5. El orden monomial que se necesita con mayor frecuencia para las aplicaciones (lexicográfico puro) no es el orden que conduce al cálculo más fácil, generalmente el orden degrevlex .

Para resolver 3. se han propuesto muchas mejoras, variantes y heurísticas antes de la introducción de los algoritmos F4 y F5 por parte de Jean-Charles Faugère . Como estos algoritmos están diseñados para coeficientes enteros o con coeficientes en números enteros módulo un número primo , el algoritmo de Buchberger sigue siendo útil para coeficientes más generales.

En términos generales, el algoritmo F4 resuelve 3. reemplazando muchas reducciones de polinomios S por la reducción de filas de una única matriz grande para lo cual se pueden usar métodos avanzados de álgebra lineal . Esto resuelve parcialmente el problema 4, ya que las reducciones a cero en el algoritmo de Buchberger corresponden a relaciones entre filas de la matriz a reducir, y las filas cero de la matriz reducida corresponden a una base del espacio vectorial de estas relaciones.

El algoritmo F5 mejora el F4 introduciendo un criterio que permite reducir el tamaño de las matrices a reducir. Este criterio es casi óptimo, ya que las matrices a reducir tienen rango completo en casos suficientemente regulares (en particular, cuando los polinomios de entrada forman una secuencia regular ). Ajustar F5 para un uso general es difícil, ya que su rendimiento depende de un orden en los polinomios de entrada y de un equilibrio entre el incremento del grado del polinomio de trabajo y del número de polinomios de entrada que se consideran. Hasta la fecha (2022), no existe una implementación distribuida que sea significativamente más eficiente que F4, pero, sobre enteros modulares, F5 se ha utilizado con éxito para varios desafíos criptográficos ; por ejemplo, por romper el desafío HFE .

El problema 5 se ha resuelto mediante el descubrimiento de algoritmos de conversión de bases que parten de la base de Gröbner para el orden de un monomio para calcular una base de Gröbner para otro orden de monomio. El algoritmo FGLM es un algoritmo de conversión de bases que funciona sólo en el caso de dimensión cero (donde los polinomios tienen un número finito de ceros comunes complejos) y tiene una complejidad polinómica en el número de ceros comunes. Un algoritmo de conversión de bases que funciona en el caso general es el algoritmo de paseo de Gröbner . ^[4] En su forma original, FGLM puede ser el paso crítico para resolver sistemas de ecuaciones polinómicas porque FGML no tiene en cuenta la escasez de matrices involucradas . Esto se ha solucionado mediante la introducción de algoritmos FGLM dispersos . ^[5]

La mayoría de los sistemas de álgebra informática de propósito general tienen implementaciones de uno o varios algoritmos para bases de Gröbner, a menudo también integrados en otras funciones, como para resolver sistemas de ecuaciones polinómicas o para simplificar funciones trigonométricas; este es el caso, por ejemplo, de CoCoA , GAP , Macaulay 2 , Magma , Maple , Mathematica , SINGULAR , SageMath y SymPy . Cuando F4 está disponible, generalmente es mucho más eficiente que el algoritmo de Buchberger. Las técnicas de implementación y las variantes algorítmicas no siempre están documentadas, aunque pueden tener un efecto dramático en la eficiencia.

A partir de 2022 ^[update], las implementaciones más rápidas de F4 y (escaso)-FGLM parecen ser las de la biblioteca Msolve . ^[6] Además de los algoritmos de Gröbner, Msolve contiene algoritmos rápidos para el aislamiento de raíces reales y combina todas estas funciones en un algoritmo para las soluciones reales de sistemas de ecuaciones polinomiales que supera dramáticamente a otros programas para este problema (Maple y Magma). ^[6] Msolve está disponible en GitHub y tiene interfaz con Julia , Maple y SageMath; esto significa que Msolve se puede utilizar directamente desde estos entornos de software.

Complejidad

La complejidad de los cálculos de la base de Gröbner se evalúa comúnmente en términos del número n de variables y el grado máximo d de los polinomios de entrada.

En el peor de los casos, el parámetro principal de la complejidad es el grado máximo de los elementos de la base de Gröbner reducida resultante. Más precisamente, si la base de Gröbner contiene un elemento de gran grado D , este elemento puede contener términos distintos de cero cuyo cálculo requiere un tiempo de Por otro lado, si todos los polinomios en la base de Gröbner reducida un ideal homogéneo tienen un grado de como máximo D , la base de Gröbner se puede calcular mediante álgebra lineal en el espacio vectorial de polinomios de grado menor que 2 D , que tiene una dimensión. Entonces, la complejidad de este cálculo es ${\displaystyle \Omega (D^{n})}$ ${\displaystyle \Omega (D^{n})>D^{\Omega (n)}.}$ ${\displaystyle O(D^{n}).}$ ${\displaystyle O(D^{n})^{O(1)}=D^{O(n)}.}$

La complejidad del peor de los casos de un cálculo basado en Gröbner es doblemente exponencial en n . Más precisamente, la complejidad está limitada superiormente por un polinomio en Usando poca notación o , por lo tanto está limitada por. Por otro lado, se han dado ejemplos de bases de Gröbner reducidas que contienen polinomios de grado o que contienen elementos. Como todo algoritmo para calcular una base de Gröbner debe escribir su resultado, esto proporciona un límite inferior de complejidad. ${\textstyle d^{2^{n}}.}$ ${\textstyle d^{2^{n+o(n)}}.}$ ${\textstyle d^{2^{\Omega (n)}},}$ ${\textstyle d^{2^{\Omega (n)}}}$

La base de Gröbner es EXPSPACE completa . ^[7]

Generalizaciones

El concepto y los algoritmos de las bases de Gröbner se han generalizado a submódulos de módulos libres sobre un anillo polinómico. De hecho, si L es un módulo libre sobre un anillo R , entonces se puede considerar la suma directa como un anillo definiendo el producto de dos elementos de L como 0 . Este anillo puede identificarse con , donde 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 bases de módulos de Gröbner a la teoría y los algoritmos de bases de ideales de Gröbner. ${\displaystyle R\oplus L}$ ${\displaystyle R[e_{1},\ldots ,e_{l}]/\left\langle \{e_{i}e_{j}|1\leq i\leq j\leq l\}\right\rangle }$ ${\displaystyle e_{1},\ldots ,e_{l}}$ ${\displaystyle g_{1},\ldots ,g_{k}}$ ${\displaystyle R[e_{1},\ldots ,e_{l}]}$ ${\displaystyle g_{1},\ldots ,g_{k}}$ ${\displaystyle e_{i}e_{j}}$ ${\displaystyle 1\leq i\leq j\leq l}$

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 .

Áreas de aplicación

Códigos de corrección de errores

La base de Gröbner se ha aplicado en la teoría de los códigos de corrección de errores para la decodificación algebraica. Utilizando el cálculo de la base de Gröbner en diversas formas de ecuaciones de corrección de errores, se desarrollaron métodos de decodificación para corregir errores de códigos cíclicos, ^[8] códigos de variedades afines, ^[9] códigos algebraicos-geométricos e incluso códigos de bloques lineales generales. ^[10] La aplicación de la base de Gröbner en la decodificación algebraica sigue siendo un área de investigación de la teoría de la codificación de canales.

Ver también

• Lema del diamante de Bergman , una extensión de las bases de Gröbner a anillos no conmutativos
• base más grave
• base janet
• Cadenas regulares , una forma alternativa de representar conjuntos algebraicos

Referencias

1. Lazard, Daniel (1983). "Bases de Gröbner, eliminación gaussiana y resolución de sistemas de ecuaciones algebraicas". Álgebra informática . Apuntes de conferencias sobre informática. vol. 162, págs. 146-156. doi :10.1007/3-540-12868-9_99. ISBN 978-3-540-12868-7.
2. Renschuch, Bodo; Roloff, Hartmut; Rasputín, Georgij G.; Abramson, Michael (junio de 2003). "Contribuciones a la teoría constructiva del ideal polinómico XXIII: obras olvidadas del matemático de Leningrado NM Gjunter sobre la teoría del ideal polinómico" (PDF) . Toro SIGSAM . 37 (2): 35–48. doi : 10.1145/944567.944569. S2CID  1819694.
3. Cox, David A .; Pequeño John; O'Shea, Donal (1997). Ideales, variedades y algoritmos: una introducción a la geometría algebraica computacional y al álgebra conmutativa . Saltador. ISBN 0-387-94680-2.
4. Collart, Stéphane; Kalkbrener, Michael; Centro comercial, Daniel (1997). "Conversión de bases con el paseo de Gröbner". Revista de Computación Simbólica . 24 (3–4). Elsevier: 465–469. doi : 10.1006/jsco.1996.0145 .
5. Faugère, Jean-Charles ; Chenqi, Mou (2017). "Algoritmos FGLM dispersos". Revista de Computación Simbólica . 80 . Elsevier: 538–569. arXiv : 1304.1238 . doi : 10.1016/j.jsc.2016.07.025 . S2CID  149627.
6. Berthomieu \first1=Jérémy; Eder, cristiano; Safey El Din, Mohab (2021). Msolve: una biblioteca para resolver sistemas polinomiales. 2021 Simposio Internacional sobre Computación Simbólica y Algebraica. 46º Simposio Internacional sobre Computación Simbólica y Algebraica. San Petersburgo, Rusia. arXiv : 2104.03572 . doi :10.1145/3452143.3465545.{{cite conference}}: CS1 maint: numeric names: authors list (link)
7. Mayr, Ernst W. (septiembre de 1997), "Algunos resultados de complejidad para ideales polinomiales", Journal of Complexity , 13 (3): 303–325, doi : 10.1006/jcom.1997.0447
8. Chen, X.; Caña, ES; Helleseth, T.; Truong, TK (1994). "Uso de bases de Gröbner para decodificar códigos cíclicos binarios hasta la distancia mínima real". Transacciones IEEE sobre teoría de la información . 40 (5): 1654–61. doi : 10.1109/18.333885.
9. Fitzgerald, J.; Laxo, 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.
10. Bulygin, S.; Pellikaan, R. (2009). "Decodificación de códigos lineales de corrección de errores hasta la mitad de la distancia mínima con bases de 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 . vol. 3. Sociedad Matemática Estadounidense . ISBN 0-8218-3804-0.
• Li, Huishi (2011). Bases de Gröbner en la teoría de anillos . Científico Mundial . ISBN 978-981-4365-13-0.
• Becker, Thomas; Weispfenning, Volker (1998). Bases de Gröbner: un enfoque computacional del álgebra conmutativa . Textos de Posgrado en Matemáticas. vol. 141. Saltador. ISBN 0-387-97971-9.
• Buchberger, Bruno (1965). Un algoritmo para encontrar los elementos básicos del anillo de clase de residuo de un polinomio ideal de dimensión cero (PDF) (PhD). Universidad de Innsbruck. — (2006). "Tesis doctoral de Bruno Buchberger 1965: un algoritmo para encontrar los elementos básicos del anillo de clase de residuo de un polinomio ideal de dimensión cero". Revista de Computación Simbólica . 41 (3–4). Traducido por Abramson, M.: 471–511. doi : 10.1016/j.jsc.2005.09.007 . [Ésta 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) . Aecuaciones 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 Sociedad Matemática de Londres. vol. 251. Prensa de la Universidad de Cambridge. págs. 535–545. ISBN 978-0-521-63298-0.
• Buchberger, Bruno; Kauers, Manuel (2010). "Bases Gröbner". Scholarpedia . 5 (10): 7763. Código bibliográfico : 2010SchpJ...5.7763B. doi : 10.4249/scholarpedia.7763 .
• Froberg, 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ón{{cite journal}}: CS1 maint: postscript (link)
• 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, Matías ; Hillar, Christopher (2007). "Generación finita de ideales simétricos". Transacciones de la Sociedad Matemática Estadounidense . 359 (11): 5171–92. arXiv : matemáticas/0411514 . 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 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-Díaz, R.; Buchberger, B.; Freire, J. (eds.). Teoría de sistemas asistidos por computadora - EUROCAST 2001: una selección de artículos del 8º Taller internacional sobre teoría de sistemas asistidos por computadora. Saltador. págs. 1-19. ISBN 978-3-540-45654-4.
• Buchberger, B.; Zapletal, A. "Bibliografía de las bases de Gröbner".
• Página comparativa de horarios para el software Gröbner Bases
• Prof. Bruno Buchberger Bruno Buchberger
• Weisstein, Eric W. "Base Gröbner". MundoMatemático .
• Introducción a la base de Gröbner en Scholarpedia