Comprobar si el polinomio está en el álgebra de una colección dada de polinomios

Question

Una colección $\Sigma$ de polinomios es un álgebra si:

1. $\lambda f + \eta g \in \Sigma$ para cualquier $f,g \in \Sigma, \lambda,\eta \in \mathbb{R}$

2. $f,g \in \Sigma$ implica $fg \in \Sigma$ .

3. $1 \in \Sigma$

Decimos que $P$ está en el álgebra de $\{P_1,\dots,P_n\}$ si $P$ está en el álgebra más pequeña que contiene $P_1,\dots,P_n$ .

Me preguntaba si había una forma, en cualquier programa de matemáticas de ordenador, de comprobar si un determinado $P$ está en el álgebra de una colección determinada $P_1,\dots,P_n$ . Sé que Mathematica puede comprobar si $P$ está en el ideal generado por $P_1,\dots,P_n$ pero no sé de álgebras, ni de ningún otro software aparte de Mathematica (que apenas conozco).

Ejemplo : Tome $n \ge 1$ y que $P_1 = x_1+\dots+x_n, P_2 = x_1^2+\dots+x_n^2,\dots P_n = x_1^n+\dots+x_n^n$ . Entonces todos $n$ de las siguientes funciones simétricas están en el álgebra generada por $P_1,\dots,P_n$ : $$x_1+\dots+x_n$$ $$x_1x_2+\dots+x_{n-1}x_n$$ $$x_1x_2x_3+\dots+x_{n-2}x_{n-1}x_n$$ $$\dots$$ $$x_1\dots x_n$$

Agradecería cualquier ayuda.

Answer 1

En primer lugar, no conozco ningún programa informático que lo solucione. Pero tengo algunas ideas que podrían ser útiles.

Tu ejemplo ya incluye polinomios de varias variables, pero déjame centrarme primero en los polinomios de una sola variable.

El álgebra generada por $\{P_1,...,P_n\}$ es el subespacio lineal de dimensión infinita de $\mathbb{R}[X]$ abarcados por todos los monomios con respecto a estos polinomios, como $P_1^5$ y $P_3^2P_5P_6$ pero también $P_1$ y sólo $1$ .

En primer lugar, el caso $n=1$ es muy fácil. Todos los elementos del álgebra son de la forma $\lambda_0+\lambda_1P_1+\lambda_2P_1^2+...+\lambda_kP_1^k$ con $k=0$ o $\lambda_k\neq0$ . Obsérvese que el grado de este polinomio es $k\cdot\mbox{deg}(P_1)$ . Esto ya demuestra que el grado de $P$ tiene que ser un múltiplo de la de $P_1$ . Si este es el caso, entonces puede averiguar qué $\lambda_k$ debe ser y restar $\lambda_kP_1^k$ de $P$ para reducir el grado de $P$ . A continuación, basta con repetir el proceso para determinar si $P$ pertenece al álgebra generada por $P_1$ .

Cuando $n$ se hace más grande, el problema se vuelve mucho más difícil. Consideremos primero el caso en el que todos los $P_i$ son monomios $P_i(X)=X^{k_i}$ . Entonces requerimos para cada coeficiente no nulo $\lambda_k$ de $P$ que $k$ puede escribirse como una suma de números, con repetición permitida, de $\{k_1,...,k_n\}$ . La lectura de la Problema de Frobenius me hace sospechar que esto ya es NP-completo con respecto a $n$ .

Cuanto más pienso en el problema general, más sospecho que es indecidible. Pero aquí hay un algoritmo que debería encontrar una solución con relativa rapidez (véase: polinómico en los grados, pero exponencial en $n$ ) si existe una, y se ejecutará para siempre si no hay solución.

Generar todos los monomios con respecto a los polinomios $P_1,...,P_n$ por orden de grado. Esto se puede hacer de manera eficiente con una cola de prioridad. Por cada monomio que encuentres, añádelo a la lista de monomios hasta ahora. Esta lista puede verse como una lista de vectores en $\mathbb{R}^d$ con $d$ el grado máximo de los monomios hasta ahora. Entonces nos preguntamos si $P$ es una combinación lineal de estos vectores.

Ejemplo: Considere $P(X)=X+2$ , $P_1(X)=X+X^2$ , $P_2(X)=X+X^3$ . Encontramos los siguientes monomios con sus correspondientes vectores: \begin{align*} 1&&(1,0,0,0,0,0,0)\\ P_1&&(0,1,1,0,0,0,0)\\ P_2&&(0,1,0,1,0,0,0)\\ P_1^2&&(0,0,1,2,1,0,0)\\ P_1P_2&&(0,0,1,1,1,1,0)\\ P_2^2&&(0,0,1,0,2,0,1)\\ P_1^3&&(0,0,0,1,3,3,1)\\ \end{align*} En este punto, tenemos $7$ vectores linealmente independientes en $7$ dimensiones, por lo que podemos escribir $P$ como una combinación lineal de estos monomios.

Obsérvese que el mismo algoritmo puede utilizarse para polinomios multivariables. Aunque el algoritmo será mucho menos eficiente.

Answer 2

(Esta respuesta se divide en cuatro secciones. La primera sección es una implementación en Mathematica de Daniel Schepler 's respuesta . La segunda sección describe el uso de las funciones incorporadas de Mathematica para abordar el ejemplo muy simétrico de la pregunta. Las secciones tercera y cuarta son código de Mathematica para el problema general de encontrar una reducción explícita de un polinomio dado en el álgebra abarcada por un conjunto dado de polinomios sin usar la maquinaria de Bases Groebner . La tercera sección, que implementa la versión multivariable de SmileyCraft 's respuesta , amplía los productos de las potencias de los generadores por el grado total $1$ , lo que probablemente requerirá menos tiempo y memoria para encontrar una reducción que el código de la cuarta sección (que se escribió al mismo tiempo y sin conocer la respuesta de SmileyCraft), que se expande tomando todos los productos de los pares del conjunto parcial actual).

inAlgebra[gens_List, vars_List, target_, gensSymbol_Symbol: None] := 
  (*  Adapted by Eric Towers from a description in https://math.stackexchange.com/a/3516363/123905  *)
  Module[{
      P, kernelGens, answerRels
    },
    kernelGens = GroebnerBasis[Join[Array[P, Length[gens]] - gens, {P - target}], 
      Join[Array[P, Length[gens]], {P}], vars, MonomialOrder -> EliminationOrder];
    answerRels = Simplify[P /. Solve[# == 0, P]] & /@ 
      Select[kernelGens, And[NumericQ[D[#, P]], D[#, P] != 0] &];
    Flatten[ReplaceAll[
      answerRels,
      Rule @@ # & /@ Transpose[{Array[P, Length[gens]], 
        If[gensSymbol === None, gens, Array[gensSymbol, Length[gens]]]}]
    ], 1]
  ]

Esta versión añade una opción que no estaba presente en las versiones anteriores: la salida puede ser en términos de potencias de un símbolo indexado, en lugar de literalmente los generadores. El cuarto argumento es opcional. Si no se da, o se da como None entonces la reducción del polinomio objetivo a una combinación lineal de productos de potencias de los generadores se da explícitamente. Si el cuarto argumento es un Símbolo, P por ejemplo, entonces la salida se escribe como una combinación lineal de productos de potencias de ese símbolo indexado por el ordinal del generador en el gens argumento. Ejemplo:

inAlgebra[{x1 + x2, x1 x2}, {x1, x2}, x1^2 + x2^2]
inAlgebra[{x1 + x2, x1 x2}, {x1, x2}, x1^2 + x2^2, None]
inAlgebra[{x1 + x2, x1 x2}, {x1, x2}, x1^2 + x2^2, P]
(*  {-2 x1 x2 + (x1 + x2)^2}  *)
(*  {-2 x1 x2 + (x1 + x2)^2}  *)
(*  {P[1]^2 - 2 P[2]}  *)

Aquí, P[1] es el primer generador, x1 + x2 y P[2] es el segundo generador, x1 x2 .

Ahora los otros ejemplos, duplicados usando el nuevo argumento opcional.

inAlgebra[{x1 + x2, x1^2 + x2^2}, {x1, x2}, x1 x2]
inAlgebra[{x1 + x2, x1^2 + x2^2}, {x1, x2}, x1 x2, Gen]
inAlgebra[{x1 + x2 + x3, x1^2 + x2^2 + x3^2, x1^3 + x2^3 + x3^3}, {x1, x2, x3}, x1 x2 + x1 x3 + x2 x3]
inAlgebra[{x1 + x2 + x3, x1^2 + x2^2 + x3^2, x1^3 + x2^3 + x3^3}, {x1, x2, x3}, x1 x2 + x1 x3 + x2 x3, P]
inAlgebra[{x1 + x2 + x3, x1^2 + x2^2 + x3^2, x1^3 + x2^3 + x3^3}, {x1, x2, x3}, x1 x2 x3]
inAlgebra[{x1 + x2 + x3, x1^2 + x2^2 + x3^2, x1^3 + x2^3 + x3^3}, {x1, x2, x3}, x1 x2 x3, T]
(*  {1/2 (-x1^2 - x2^2 + (x1 + x2)^2)}  *)
(*  {1/2 (Gen[1]^2 - Gen[2])}  *)
(*  {1/2 (-x1^2 - x2^2 - x3^2 + (x1 + x2 + x3)^2)}  *)
(*  {1/2 (P[1]^2 - P[2])}  *)
(*  {1/6 ((x1 + x2 + x3)^3 - 3 (x1 + x2 + x3) (x1^2 + x2^2 + x3^2) + 2 (x1^3 + x2^3 + x3^3))}  *)
(*  {1/6 (T[1]^3 - 3 T[1] T[2] + 2 T[3])}  *)

---

El ejemplo está mucho más estructurado que el problema general del que parte la pregunta. El siguiente código de Mathematica expresa el polinomios simétricos elementales en términos de suma de potencias de polinomios simétricos mucho más directamente que calcular el $\Bbb{R}$ -span de aproximaciones sucesivas al monoide de potencias de los generadores. Para ello se utiliza el teorema fundamental de los polinomios simétricos, según el cual cualquier polinomio simétrico puede escribirse como un polinomio en los polinomios simétricos elementales. Entonces, invertimos la relación para escribir los polinomios simétricos elementales en términos de los polinomios simétricos de la suma de potencias.

elementariesAsSymmetricPowerSums[n_] := Module[{
    vars,
    powerSumsymmetricPolynomials,
    elementarySymmetricReductions
  },
  vars = Array[x, n];
  powerSumsymmetricPolynomials = Table[Sum[x[i]^power, {i, 1, n}], {power, 1, n}];
  elementarySymmetricReductions = 
    SymmetricReduction[#, vars, Array[(esp[n, #] &), n]][[1]] & /@ 
      powerSumsymmetricPolynomials;
  Solve[Array[pssp[n, #] &, n] == elementarySymmetricReductions, Array[(esp[n, #] &), n]]
]

En este caso, utilizamos los símbolos \begin{align*} \mathrm{pssp}[v,p] &= \sum_{i=1}^v x_i^p \\ \mathrm{esp}[v,p] &= \sum_{1 \leq i_1 \leq i_2 \leq \cdots \leq i_p \leq v} x_{i_1} x _{i_2}\cdots x_{i_p} \text{,} \end{align*} donde $v$ es el número de variables, $p$ es el grado total de los términos del polinomio, $\mathrm{pssp}$ da polinomios simétricos de suma de potencias, y $\mathrm{esp}$ da los polinomios simétricos elementales.

elementariesAsSymmetricPowerSums[3]
(*  {{esp[3, 1] -> pssp[3, 1], 
      esp[3, 2] -> 1/2 (pssp[3, 1]^2 - pssp[3, 2]), 
      esp[3, 3] -> 1/6 (pssp[3, 1]^3 - 3 pssp[3, 1] pssp[3, 2] + 2 pssp[3, 3])}}  *)

Esto dice \begin{align*} x_1 + x_2 + x_3 &= x_1 + x_2 + x_3 \\ x_1 x_2 + x_1 x_3 + x_2 x_3 &= \frac{1}{2}(x_1 + x_2 + x_3)^2 - (x_1^2 + x_2^2 + x_3^2) \\ x_1 x_2 x_3 &= \frac{1}{6}(x_1 + x_2 + x_3)^3 - 3(x_1 + x_2 + x_3)(x_1^2 + x_2^2 + x_3^2) + 2 (x_1^3 + x_2^3 + x_3^3) \end{align*}

Este método debería ser capaz de manejar rápidamente instancias mucho más grandes. Como ejemplo...

elementariesAsSymmetricPowerSums[8]
(*  {{esp[8, 1] -> pssp[8, 1], 
      esp[8, 2] -> 1/2 (pssp[8, 1]^2 - pssp[8, 2]), 
      esp[8, 3] -> 1/6 (pssp[8, 1]^3 - 3 pssp[8, 1] pssp[8, 2] + 2 pssp[8, 3]), 
      esp[8, 4] -> 1/24 (pssp[8, 1]^4 - 6 pssp[8, 1]^2 pssp[8, 2] + 3 pssp[8, 2]^2 + 8 pssp[8, 1] pssp[8, 3] - 6 pssp[8, 4]), 
      esp[8, 5] -> 1/120 (pssp[8, 1]^5 - 10 pssp[8, 1]^3 pssp[8, 2] + 15 pssp[8, 1] pssp[8, 2]^2 + 20 pssp[8, 1]^2 pssp[8, 3] - 20 pssp[8, 2] pssp[8, 3] - 30 pssp[8, 1] pssp[8, 4] + 24 pssp[8, 5]), 
      esp[8, 6] -> 1/720 (pssp[8, 1]^6 - 15 pssp[8, 1]^4 pssp[8, 2] + 45 pssp[8, 1]^2 pssp[8, 2]^2 - 15 pssp[8, 2]^3 + 40 pssp[8, 1]^3 pssp[8, 3] - 120 pssp[8, 1] pssp[8, 2] pssp[8, 3] + 40 pssp[8, 3]^2 - 90 pssp[8, 1]^2 pssp[8, 4] + 90 pssp[8, 2] pssp[8, 4] + 144 pssp[8, 1] pssp[8, 5] - 120 pssp[8, 6]), 
      esp[8, 7] -> (1/5040)(pssp[8, 1]^7 - 21 pssp[8, 1]^5 pssp[8, 2] + 105 pssp[8, 1]^3 pssp[8, 2]^2 - 105 pssp[8, 1] pssp[8, 2]^3 + 70 pssp[8, 1]^4 pssp[8, 3] - 420 pssp[8, 1]^2 pssp[8, 2] pssp[8, 3] + 210 pssp[8, 2]^2 pssp[8, 3] + 280 pssp[8, 1] pssp[8, 3]^2 - 210 pssp[8, 1]^3 pssp[8, 4] + 630 pssp[8, 1] pssp[8, 2] pssp[8, 4] - 420 pssp[8, 3] pssp[8, 4] + 504 pssp[8, 1]^2 pssp[8, 5] - 504 pssp[8, 2] pssp[8, 5] - 840 pssp[8, 1] pssp[8, 6] + 720 pssp[8, 7]), 
      esp[8, 8] -> (1/40320)(pssp[8, 1]^8 - 28 pssp[8, 1]^6 pssp[8, 2] + 210 pssp[8, 1]^4 pssp[8, 2]^2 - 420 pssp[8, 1]^2 pssp[8, 2]^3 + 105 pssp[8, 2]^4 + 112 pssp[8, 1]^5 pssp[8, 3] - 1120 pssp[8, 1]^3 pssp[8, 2] pssp[8, 3] + 1680 pssp[8, 1] pssp[8, 2]^2 pssp[8, 3] + 1120 pssp[8, 1]^2 pssp[8, 3]^2 - 1120 pssp[8, 2] pssp[8, 3]^2 - 420 pssp[8, 1]^4 pssp[8, 4] + 2520 pssp[8, 1]^2 pssp[8, 2] pssp[8, 4] - 1260 pssp[8, 2]^2 pssp[8, 4] - 3360 pssp[8, 1] pssp[8, 3] pssp[8, 4] + 1260 pssp[8, 4]^2 + 1344 pssp[8, 1]^3 pssp[8, 5] - 4032 pssp[8, 1] pssp[8, 2] pssp[8, 5] + 2688 pssp[8, 3] pssp[8, 5] - 3360 pssp[8, 1]^2 pssp[8, 6] + 3360 pssp[8, 2] pssp[8, 6] + 5760 pssp[8, 1] pssp[8, 7] - 5040 pssp[8, 8])}}  *)

Lo anterior es muy específico para su ejemplo. Pero si su ejemplo es muy cercano a sus problemas más generales, esto podría ser un mejor punto de partida que el código genérico, a continuación.

---

La primera versión de la búsqueda de propósito general a través del tramo de productos de potencias de generadores de bajo grado total era muy ineficiente a la hora de ampliar la colección de productos de potencias de generadores. En lugar de generar los nuevos términos multiplicando (frecuentemente de forma redundante) pares de miembros de $\Sigma$ . En lugar de ello, utilizamos los composiciones enteras para construir directamente los vectores de los exponentes en los productos de las potencias, por lo que generamos directamente todos los términos de grado total específico de una vez, sin producir ningún duplicado que debamos eliminar posteriormente.

inAlgebra[gens_List, vars_List, target_] :=
  Module[{
    C,
    compositions, expansion,
    partialRSpanningSet, realSolution,
    iterationDepth, attemptedSolution
    },
    compositions[total_, parts_] :=
      Flatten[Table[
          Join[{k}, #] & /@ compositions[total - k, parts - 1],
          {k, 0, total}
        ], 1];
    compositions[total_, 1] := {{total}};
    expansion[set_List, totalOrder_] := (Times @@ Power[set, #]) & /@ compositions[totalOrder, Length[set]];

    realSolution[set_] := 
      SolveAlways[C[0] + Table[C[i], {i, 1, Length[set]}].set == target, vars];

    iterationDepth = 1;
    partialRSpanningSet = Union[{}, expansion[gens, iterationDepth]];
    attemptedSolution = realSolution[partialRSpanningSet];
    While[Not[And[Head[attemptedSolution] === List, Length[attemptedSolution] > 0]],
      iterationDepth++;
      If[iterationDepth > $IterationLimit, 
        Print["$IterationLimit exceeded.  See documentation for $IterationLimit to see how to increase $IterationLimit in a Block[]."];
        Abort[];
      ];
      partialRSpanningSet = Join[partialRSpanningSet, expansion[gens, iterationDepth]];
      attemptedSolution = realSolution[partialRSpanningSet];
    ];
    (C[0] + Table[C[i], {i, 1, Length[partialRSpanningSet]}].partialRSpanningSet) /. attemptedSolution
  ]

Comprobando la salida de nuevo...

inAlgebra[{x1 + x2, x1^2 + x2^2}, {x1, x2}, x1 x2]
inAlgebra[{x1 + x2 + x3, x1^2 + x2^2 + x3^2, x1^3 + x2^3 + x3^3}, {x1, x2, x3}, x1 x2 + x1 x3 + x2 x3]
inAlgebra[{x1 + x2 + x3, x1^2 + x2^2 + x3^2, x1^3 + x2^3 + x3^3}, {x1, x2, x3}, x1 x2 x3]
(*  {1/2 (x1 + x2)^2 + 1/2 (-x1^2 - x2^2)}  *)
(*  {1/2 (x1 + x2 + x3)^2 + 1/2 (-x1^2 - x2^2 - x3^2)}  *)
(*  {1/6 (x1 + x2 + x3)^3 - 1/2 (x1 + x2 + x3) (x1^2 + x2^2 + x3^2) + 1/3 (x1^3 + x2^3 + x3^3)}  *)

---

(Esta es la primera versión del código de Mathematica para reducir un polinomio dado en una combinación lineal de productos de potencias de un conjunto dado de generadores. Más arriba aparece una versión a veces más rápida y, muy probablemente, con menos consumo de memoria).

El siguiente código de Mathematica hace lo que usted solicita.

inAlgebra[gens_List, vars_List, target_] :=
  Module[{C,
      iterate,
      partialRSpanningSet, realSolution,
      iterationDepth, attemptedSolution
    },
    iterate[set_List] := Union[set,
      Reap[
        Table[
          Sow[Times[set[[f]], set[[g]] ]],
          {f, 1, Length[set]}, {g, f, Length[set]}]][[2, 1]]
      ];

    realSolution[set_] := 
      SolveAlways[C[0] + Table[C[i], {i, 1, Length[set]}].set == target, 
vars];

    partialRSpanningSet = gens;
    iterationDepth = 0;
    attemptedSolution = realSolution[partialRSpanningSet];
    While[Not[And[Head[attemptedSolution] === List, 
        Length[attemptedSolution] > 0]],
      partialRSpanningSet = iterate[partialRSpanningSet];
      iterationDepth++;
      If[iterationDepth > $IterationLimit, 
        Print[
          "$IterationLimit exceeded.  See documentation for $IterationLimit to see how to increase $IterationLimit in a Block[]."];
        Abort[];
      ];
      attemptedSolution = realSolution[partialRSpanningSet];
    ];
    (C[0] + Table[C[i], {i, 1, Length[partialRSpanningSet]}].partialRSpanningSet) /. attemptedSolution
]

Se basa en la siguiente observación: un producto de combinaciones lineales de elementos de $\Sigma$ es una combinación lineal de productos de potencias del $P_i$ . Así, primero buscamos una combinación lineal de los $P_i$ que da el polinomio objetivo. Luego buscamos combinaciones lineales entre los productos de $\leq 2$ de la $P_i$ entonces entre los productos de $\leq 3$ de la $P_i$ continuando hasta que encontremos una solución, abortemos por exceso de iteración o se termine externamente. Usos:

inAlgebra[{x1 + x2, x1^2 + x2^2}, {x1, x2}, x1 x2]
(*  {1/2 (x1 + x2)^2 + 1/2 (-x1^2 - x2^2)}  *)

inAlgebra[{x1 + x2 + x3, x1^2 + x2^2 + x3^2, x1^3 + x2^3 + x3^3}, {x1, x2, x3}, x1 x2 + x1 x3 + x2 x3]
(*  {1/2 (x1 + x2 + x3)^2 + 1/2 (-x1^2 - x2^2 - x3^2)}  *)

inAlgebra[{x1 + x2 + x3, x1^2 + x2^2 + x3^2, x1^3 + x2^3 + x3^3}, {x1, x2, x3}, x1 x2 x3]
(*  {1/6 (x1 + x2 + x3)^3 - 1/2 (x1 + x2 + x3) (x1^2 + x2^2 + x3^2) + 1/3 (x1^3 + x2^3 + x3^3)}  *)

Answer 3

Supongamos que queremos determinar si $q \in \mathbb{R}[x_1, \ldots, x_r]$ está en la subálgebra generada por $p_1, \ldots, p_n$ . La teoría general de las bases de Groebner nos permite encontrar una base de Groebner del núcleo de la $\mathbb{R}$ -homomorfismo de álgebra $$\mathbb{R}[t_1, \ldots, t_n, s] \to \mathbb{R}[x_1, \ldots, x_r], t_i \mapsto p_i, s \mapsto q.$$ Además, si el orden monomial que elegimos tiene $s > t_1^{d_1} \cdots t_r^{d_r}$ para todos $d_1, \ldots, d_r \ge 0$ entonces $q$ estará en la subálgebra generada por $p_1, \ldots, p_n$ si y sólo si uno de los elementos de esta base de Groebner del núcleo es igual a $\lambda s - F(t_1, \ldots, t_n)$ para algunos $\lambda \in \mathbb{R}^*, F \in \mathbb{R}[x_1, \ldots, x_r]$ .

Si algún sistema de álgebra computacional específico no tiene una función incorporada para encontrar núcleos, pero sí tiene una rutina general de cálculo de bases de Groebner, entonces se puede encontrar el núcleo requerido calculando una base de Groebner para el ideal $\langle t_i - p_i, s - q \rangle$ de $\mathbb{R}[t_1, \ldots, t_n, s, x_1, \ldots, x_r]$ utilizando un orden de eliminación tal que los monomios de $\mathbb{R}[t_1, \ldots, t_n, s]$ son menores que cualquier monomio que contenga una potencia positiva de $x_j$ . A continuación, tome los elementos de la base de Groebner de este ideal que se encuentran en $\mathbb{R}[t_1, \ldots, t_n, s]$ y formarán la base de Groebner deseada del núcleo.

---

Esto tiene la desventaja de tener que hacer un nuevo cálculo de la base de Groebner para cada nuevo $q$ aunque $p_1, \ldots, p_n$ son fijos. Sin embargo, también podemos elaborar una variante del algoritmo que permite realizar el cálculo de la base de Groebner una vez para los fijos $p_1, \ldots, p_n$ con $q$ variando: encontrar una base de Groebner del ideal $I = \langle t_i - p_i \rangle$ de $\mathbb{R}[t_1, \ldots, t_n, x_1, \ldots, x_r]$ con respecto a un orden de eliminación donde los monomios en $t_1, \ldots, t_n$ son menores que cualquier monomio con una potencia positiva de algún $x_j$ . Ahora, dado $q$ el proceso de reducción de la división $q$ (o técnicamente $1 \otimes q \in \mathbb{R}[t_1, \ldots, t_n] \otimes_{\mathbb{R}} \mathbb{R}[x_1, \ldots, x_r] \simeq \mathbb{R}[t_1, \ldots, t_n, x_1, \ldots, x_r]$ ) por elementos de la base de Groebner dará o bien cero o bien el representante de $(1 \otimes q) + I$ con el mínimo monomio principal. Entonces $q$ está en la subálgebra generada por $p_1, \ldots, p_n$ si y sólo si ese resto de $(1 \otimes q) \mathop{\mathrm{mod}} I$ está en $\mathbb{R}[t_1, \ldots, t_n]$ (si y sólo si el monomio principal del resto está en $\mathbb{R}[t_1, \ldots, t_n]$ ).