Orden monomial

En matemáticas , un orden monomial (a veces llamado orden de término u orden admisible ) es un orden total en el conjunto de todos los monomios ( mónicos ) en un anillo polinomial dado , que satisface la propiedad de respetar la multiplicación, es decir,

Si y es cualquier otro monomio, entonces . $u\leq v$ ${\estilo de visualización w}$ $uw\leq vw$

Los ordenamientos monomiales se utilizan con mayor frecuencia con bases de Gröbner y división multivariante . En particular, la propiedad de ser una base de Gröbner siempre es relativa a un orden monomial específico.

Definición, detalles y variaciones

Además de respetar la multiplicación, a menudo se requiere que los órdenes de los monomios sean correctos , ya que esto garantiza que el procedimiento de división multivariante terminará. Sin embargo, también existen aplicaciones prácticas para las relaciones de orden que respetan la multiplicación en el conjunto de monomios que no son correctos.

En el caso de un número finito de variables, el buen orden de un monomio es equivalente a la conjunción de las dos condiciones siguientes:

El pedido es un pedido total .
Si u es cualquier monomio entonces . $1\leq u$

Dado que estas condiciones pueden ser más fáciles de verificar para un orden monomial definido a través de una regla explícita, que probar directamente que es un buen orden, a veces se prefieren en las definiciones de orden monomial.

Monomios, términos y coeficientes principales

La elección de un orden total de los monomios permite ordenar los términos de un polinomio. El término principal de un polinomio es, por tanto, el término del monomio más grande (para el orden de monomios elegido).

Concretamente, sea $R$ un anillo cualquiera de polinomios. Entonces, el conjunto $M$ de los monomios (mónicos) en $R$ es una base de $R$ , considerada como un espacio vectorial sobre el cuerpo de los coeficientes. Por lo tanto, cualquier polinomio distinto de cero $p$ en $R$ tiene una expresión única como una combinación lineal de monomios, donde $S$ es un subconjunto finito de $M$ y los $c$ $u$ son todos distintos de cero. Cuando se ha elegido un orden monomial, el monomio principal es el $u$ más grande en $S$ , el coeficiente principal es el $c$ $u$ correspondiente y el término principal es el $c$ $u$ $u$ correspondiente . El monomio/coeficiente/término principal se usa a veces como sinónimo de "principal". Algunos autores usan "monomio" en lugar de "término" y "producto de potencia" en lugar de "monomio". En este artículo, se supone que un monomio no incluye un coeficiente. $p=\textstyle \suma _{u\in S}c_{u}u$

La propiedad definitoria de los ordenamientos monomiales implica que el orden de los términos se mantiene al multiplicar un polinomio por un monomio. Además, el término principal de un producto de polinomios es el producto de los términos principales de los factores.

Ejemplos

En el conjunto de potencias de cualquier variable x , los únicos órdenes monomiales son el orden natural 1 < x < x ² < x ³ < ... y su inverso, el último de los cuales no es un buen orden. Por lo tanto, la noción de orden monomial se vuelve interesante solo en el caso de múltiples variables. $\left\{x^{n}\mid n\in \mathbb {N} \right\}$

El orden monomial implica un orden en las indeterminaciones individuales. Se puede simplificar la clasificación de los órdenes monomiales suponiendo que las indeterminadas se nombran x ₁ , x ₂ , x ₃ , ... en orden decreciente para el orden monomial considerado, de modo que siempre x ₁ > x ₂ > x ₃ > ... . (Si hubiera infinitas indeterminaciones, esta convención es incompatible con la condición de ser un buen orden, y uno se vería forzado a usar el orden opuesto; sin embargo, el caso de polinomios en infinitas variables rara vez se considera.) En el ejemplo siguiente usamos x , y y z en lugar de x ₁ , x ₂ y x ₃ . Con esta convención todavía hay muchos ejemplos de diferentes órdenes monomiales.

Orden lexicográfico

El orden lexicográfico (lex) compara primero los exponentes de x ₁ en los monomios, y en caso de igualdad compara los exponentes de x ₂ , y así sucesivamente. El nombre se deriva de la similitud con el orden alfabético habitual utilizado en lexicografía para los diccionarios, si los monomios se representan por la secuencia de los exponentes de los indeterminados. Si el número de indeterminados es fijo (como suele ser el caso), el orden lexicográfico es un buen orden , aunque este no es el caso del orden lexicográfico aplicado a secuencias de varias longitudes (véase Orden lexicográfico § Ordenación de secuencias de varias longitudes ).

Para monomios de grado a lo sumo dos en dos indeterminados , el orden lexicográfico (con ) es $Estilo de visualización x_{1},x_{2}$ $Estilo de visualización x_{1}>x_{2}}$

$x_{1}^{2}>x_{1}x_{2}>x_{1}>x_{2}^{2}>x_{2}>1.$

Para los cálculos de la base de Gröbner , el orden lexicográfico tiende a ser el más costoso; por lo tanto, debe evitarse, en la medida de lo posible, excepto para cálculos muy simples.

Orden lexicográfico graduado

El orden lexicográfico graduado (grlex o deglex para el orden lexicográfico de grado ) compara primero el grado total (suma de todos los exponentes) y, en caso de empate, aplica el orden lexicográfico. Este orden no solo es un buen orden, sino que también tiene la propiedad de que cualquier monomio está precedido solo por un número finito de otros monomios; este no es el caso del orden lexicográfico, donde todas las potencias (infinitas) de y son menores que x (que el orden lexicográfico sea, no obstante, un buen orden está relacionado con la imposibilidad de construir una cadena infinita decreciente de monomios).

Para monomios de grado a lo sumo dos en dos indeterminados , el orden lexicográfico graduado (con ) es $Estilo de visualización x_{1},x_{2}$ $Estilo de visualización x_{1}>x_{2}}$

$x_{1}^{2}>x_{1}x_{2}>x_{2}^{2}>x_{1}>x_{2}>1.$

Aunque es muy natural, este ordenamiento rara vez se utiliza: la base de Gröbner para el orden lexicográfico inverso graduado, que sigue, es más fácil de calcular y proporciona la misma información sobre el conjunto de entrada de polinomios.

Orden lexicográfico inverso graduado

El orden lexicográfico inverso graduado (grevlex o degrevlex para el orden lexicográfico inverso de grado ) compara primero el grado total, luego usa un orden lexicográfico como desempate, pero invierte el resultado de la comparación lexicográfica de modo que los monomios lexicográficamente más grandes del mismo grado se consideran degrevlex más pequeños. Para que el orden final muestre el ordenamiento convencional x ₁ > x ₂ > ... > x _n de los indeterminados, es además necesario que el orden lexicográfico de desempate antes de la inversión considere que el último indeterminado x _n es el más grande, lo que significa que debe comenzar con ese indeterminado. Una receta concreta para el orden lexicográfico inverso graduado es entonces comparar primero por el grado total, luego comparar los exponentes del último indeterminado x _n pero invirtiendo el resultado (de modo que el monomio con el exponente menor sea mayor en el ordenamiento), seguido (como siempre, solo en caso de empate) por una comparación similar de x _{n −1} , y así sucesivamente terminando en x ₁ .

Las diferencias entre los órdenes lexicográficos graduados e inversos graduados son sutiles, ya que, de hecho, coinciden para los indeterminados 1 y 2. La primera diferencia se produce en los monomios de grado 2 en los indeterminados 3, que están ordenados lexicográficamente de forma gradual como pero ordenados lexicográficamente inversos de forma gradual como . La tendencia general es que el orden inverso exhibe todas las variables entre los monomios pequeños de cualquier grado dado, mientras que con el orden no inverso los intervalos de los monomios más pequeños de cualquier grado dado solo se formarán a partir de las variables más pequeñas. $x_{1}^{2}>x_{1}x_{2}>x_{1}x_{3}>x_{2}^{2}>x_{2}x_{3}>x_{3}^{2}$ $x_{1}^{2}>x_{1}x_{2}>x_{2}^{2}>x_{1}x_{3}>x_{2}x_{3}>x_{3}^{2}$

Orden de eliminación

El orden de bloques u orden de eliminación (lexdeg) puede definirse para cualquier número de bloques pero, por simplicidad, consideramos sólo el caso de dos bloques (sin embargo, si el número de bloques es igual al número de variables, este orden es simplemente el orden lexicográfico). Para este ordenamiento, las variables se dividen en dos bloques x ₁ ,..., x _h e y ₁ ,..., y _k y se elige un orden monomial para cada bloque, normalmente el orden lexicográfico inverso graduado. Se comparan dos monomios comparando su parte x , y en caso de empate, comparando su parte y . Este ordenamiento es importante ya que permite la eliminación , una operación que corresponde a la proyección en geometría algebraica.

Orden de peso

El orden de peso depende de un vector llamado vector de peso. Primero compara el producto escalar de las secuencias de exponentes de los monomios con este vector de peso y, en caso de empate, utiliza algún otro orden monomial fijo. Por ejemplo, los órdenes graduados anteriores son órdenes de peso para el vector de peso de "grado total" (1,1,...,1). Si los a _i son números racionalmente independientes (por lo que, en particular, ninguno de ellos es cero y todas las fracciones son irracionales), entonces nunca puede ocurrir un empate y el vector de peso en sí mismo especifica un orden monomial. En el caso contrario, se podría utilizar otro vector de peso para deshacer los empates, y así sucesivamente; después de utilizar n vectores de peso linealmente independientes, no puede haber ningún empate restante. De hecho, se puede definir cualquier ordenamiento monomial mediante una secuencia de vectores de peso (Cox et al., págs. 72-73), por ejemplo (1,0,0,...,0), (0,1,0,...,0), ... (0,0,...,1) para lex, o (1,1,1,...,1), (1,1,..., 1,0), ... (1,0,...,0) para grevlex. $(a_{1},\ldots ,a_{n})\in \mathbb {R} _{\geq 0}^{n}$ ${\frac {a_{i}}{a_{j}}}$

Por ejemplo, considere los monomios , , , y ; los órdenes de monomios anteriores ordenarían estos cuatro monomios de la siguiente manera: $Estilo de visualización xy^{2}z$ ${\estilo de visualización z^{2}}$ ${\estilo de visualización x^{3}}$ $Estilo de visualización x^{2}z^{2}}$

Lex: (poder de domina). $x^{3}>x^{2}z^{2}>xy^{2}z>z^{2}$ ${\estilo de visualización x}$
Grlex: (el grado total domina; el mayor poder de desempate entre los dos primeros). $x^{2}z^{2}>xy^{2}z>x^{3}>z^{2}$ ${\estilo de visualización x}$
Grevlex: (el grado total domina; la potencia menor rompe el empate entre los dos primeros). $xy^{2}z>x^{2}z^{2}>x^{3}>z^{2}$ ${\estilo de visualización z}$
Un orden de peso con vector de peso (1,2,4): (los productos escalares 10>9>8>3 no dejan ningún empate que romper aquí). $x^{2}z^{2}>xy^{2}z>z^{2}>x^{3}$

Nociones relacionadas

Un orden de eliminación garantiza que un monomio que involucre a cualquiera de un conjunto de indeterminados siempre será mayor que un monomio que no involucre a ninguno de ellos.
Un orden de producto es el ejemplo más sencillo de un orden de eliminación. Consiste en combinar órdenes monomiales de conjuntos disjuntos de indeterminados en un orden monomial de su unión. Simplemente compara los exponentes de los indeterminados del primer conjunto utilizando el primer orden monomial, luego desempata utilizando el otro orden monomial de los indeterminados del segundo conjunto. Este método obviamente se generaliza a cualquier unión disjunta de conjuntos de indeterminados; el orden lexicográfico se puede obtener así a partir de los conjuntos singleton { x ₁ }, { x ₂ }, { x ₃ }, ... (con el orden monomial único para cada singleton).

Cuando se utilizan ordenaciones monomiales para calcular bases de Gröbner, diferentes órdenes pueden llevar a diferentes resultados, y la dificultad del cálculo puede variar drásticamente. Por ejemplo, el orden lexicográfico inverso graduado tiene la reputación de producir, casi siempre, las bases de Gröbner que son las más fáciles de calcular (esto se ve reforzado por el hecho de que, en condiciones bastante comunes en el ideal, los polinomios en la base de Gröbner tienen un grado que es, como máximo, exponencial en el número de variables; no existe un resultado de complejidad similar para ninguna otra ordenación). Por otro lado, los órdenes de eliminación son necesarios para los problemas relativos y de eliminación .

Referencias

David Cox; John Little; Donal O'Shea (2007). Ideales, variedades y algoritmos: una introducción a la geometría algebraica computacional y al álgebra conmutativa . Springer. ISBN 978-0-387-35650-1.