orden monomio

Orden de los términos de un polinomio

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

• Si y es cualquier otro monomio, entonces . ${\displaystyle u\leq v}$ ${\displaystyle w}$ ${\displaystyle uw\leq vw}$

Los ordenamientos monomios se utilizan más comúnmente con bases de Gröbner y división multivariada . En particular, la propiedad de ser una base de Gröbner es siempre relativa a un orden monomio 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 buenos órdenes , ya que esto garantiza que el procedimiento de división multivariante terminará. Sin embargo, también existen aplicaciones prácticas para relaciones de orden que respetan la multiplicación en el conjunto de monomios que no son de buen orden.

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

1. El orden es un orden total .
2. Si u es cualquier monomio entonces . ${\displaystyle 1\leq u}$

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

Monomios, términos y coeficientes principales

La elección de un orden total sobre 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 los monomios elegido).

Concretamente, sea R cualquier anillo de polinomios. Entonces el conjunto M de los monomios (mónicos) en R es una base de R , considerado como un espacio vectorial sobre el campo de los coeficientes. Por lo tanto, cualquier polinomio p distinto de cero en R tiene una expresión única como una combinación lineal de monomios, donde S es un subconjunto finito de M y cu _son todos distintos de cero. Cuando se ha elegido un orden de monomio, el monomio principal es el u más grande en S , el coeficiente principal _es el cu correspondiente y el término principal es el cu _u correspondiente . El monomio/coeficiente/término principal se utiliza a veces como sinónimo de "principal". Algunos autores utilizan "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. ${\displaystyle p=\textstyle \sum _{u\in S}c_{u}u}$

La propiedad definitoria del ordenamiento de los monomios 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 monomios son el ordenamiento natural 1 <  x  < x ²  < x ³  < ... y su recíproco, el último de los cuales no es un buen ordenamiento. Por lo tanto, la noción de orden monomial resulta interesante sólo en el caso de múltiples variables. ${\displaystyle \left\{x^{n}\mid n\in \mathbb {N} \right\}}$

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

orden lexicográfico

El orden lexicográfico (lex) primero compara exponentes de x ₁ en los monomios, y en caso de igualdad compara 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 están representados 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 (ver Orden lexicográfico § Ordenación de secuencias de varias longitudes ).

Para monomios de grado como máximo dos en dos indeterminados , el orden lexicográfico (con ) es ${\displaystyle x_{1},x_{2}}$ ${\displaystyle x_{1}>x_{2}}$

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

Para los cálculos basados ​​en 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 en cálculos muy simples.

Orden lexicográfico graduado

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

Para monomios de grado como máximo dos en dos indeterminados , el orden lexicográfico graduado (con ) es ${\displaystyle x_{1},x_{2}}$ ${\displaystyle x_{1}>x_{2}}$

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

Aunque es muy natural, este orden 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 polinomios de entrada.

Orden lexicográfico inverso graduado

El orden lexicográfico inverso graduado (grevlex, o degrevlex para 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 se obtienen monomios lexicográficamente más grandes del mismo grado. Se considera degrevlex más pequeño. Para que el orden final exhiba 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 mayor, lo que significa que debe comenzar con ese indeterminado. Una receta concreta para el orden lexicográfico inverso graduado es, por tanto, 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 exponente menor sea mayor en el orden), seguido (como siempre sólo en caso de empate) mediante una comparación similar de x _{n −1} , y así sucesivamente terminando con x ₁ .

Las diferencias entre los órdenes lexicográficos graduados y lexicográficos inversos graduados son sutiles, ya que de hecho coinciden para 1 y 2 indeterminados. La primera diferencia viene para monomios de grado 2 en 3 indeterminados, que se clasifican lexicográficamente ordenados como pero se clasifican lexicográficamente inversos ordenados 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. ${\displaystyle x_{1}^{2}>x_{1}x_{2}>x_{1}x_{3}>x_{2}^{2}>x_{2}x_{3}>x_{3}^{2}}$ ${\displaystyle 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 los bloques o el orden de eliminación (lexdeg) se puede definir 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 orden, las variables se dividen en dos bloques x ₁ ,..., x _h e y ₁ ,..., y _k y se elige un orden monomio para cada bloque, generalmente el orden lexicográfico inverso graduado. Dos monomios se comparan comparando su parte x y, en caso de empate, comparando su parte y . Este ordenamiento es importante ya que permite la eliminación , operación que corresponde a la proyección en geometría algebraica.

Orden de peso

El orden de los pesos depende de un vector llamado vector de pesos. Primero compara el producto escalar de las secuencias exponentes de los monomios con este vector de peso y, en caso de empate, utiliza algún otro orden de monomio fijo. Por ejemplo, las órdenes calificadas 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í especifica un orden monomial. En el caso contrario, se podría utilizar otro vector de peso para romper empates, y así sucesivamente; después de usar n vectores de peso linealmente independientes, no puede haber ningún vínculo restante. De hecho, se puede definir cualquier orden monomio 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. ${\displaystyle (a_{1},\ldots ,a_{n})\in \mathbb {R} _{\geq 0}^{n}}$ ${\displaystyle {\tfrac {a_{i}}{a_{j}}}}$

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

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

Nociones relacionadas

• Un orden de eliminación garantiza que un monomio que incluya a cualquiera de un conjunto de indeterminados siempre será mayor que un monomio que no incluya a ninguno de ellos.
• Un pedido de producto es el ejemplo más sencillo de un pedido 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 en el primer conjunto usando el primer orden monomial, luego rompe los empates usando el otro orden monomial en los indeterminados del segundo conjunto. Obviamente, este método se generaliza a cualquier unión disjunta de conjuntos de indeterminados; el orden lexicográfico se puede obtener a partir de los conjuntos singleton { x ₁ }, { x ₂ }, { x ₃ }, ... (con el ordenamiento monomial único para cada singleton).

Cuando se utilizan ordenamientos de monomios para calcular bases de Gröbner, diferentes órdenes pueden conducir a resultados diferentes y la dificultad del cálculo puede variar dramáticamente. 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 una grado que es como mucho exponencial en el número de variables; no existe tal resultado de complejidad para ningún otro ordenamiento). Por otro lado, se requieren órdenes de eliminación para problemas de eliminación y relativos.

Referencias

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