Algorithm to find relations between polynomials

Question

Let $p_1,\ldots,p_k\in\mathbb{C}[x_1,\ldots,x_n]$ be polynomials. Is there an algorithm to compute the ideal of relations between them?

More precisely, to find a set of generators for the kernel of the ring homomorphism $$\mathbb{C}[y_1,\ldots,y_k]\to \mathbb{C}[x_1,\ldots,x_n],\quad y_i\mapsto p_i(x_1,\ldots,x_n).$$ (This enables us to compute $\mathbb{C}[p_1,\ldots,p_k]$).

Example: Consider $$x_1x_2,x_3x_4,x_1x_3,x_2x_4\in\mathbb{C}[x_1,x_2,x_3,x_4].$$ One obvious relation between them is $$(x_1x_2)(x_3x_4)=(x_1x_3)(x_2x_4).$$ Thus, if $$\varphi:\mathbb{C}[y_1,y_2,y_3,y_4]\to\mathbb{C}[x_1,x_2,x_3,x_4]$$ is the homomorphism defined by $$y_1\mapsto x_1x_2,\quad y_2\mapsto x_3x_4,\quad y_3\mapsto x_1x_3,\quad y_4\mapsto x_2x_4,$$ then $y_1y_2-y_3y_4\in\ker \varphi$. It is easy to see that $\ker\varphi$ is in fact generated by $y_1y_2-y_3y_4$, so $$\mathbb{C}[x_1x_2,x_3x_4,x_1x_3,x_2x_4]\cong\mathbb{C}[y_1,y_2,y_3,y_3]/(y_1y_2-y_3y_4).$$

Answer 1

You can do this using elimination. Among other places, this is explained in this blog post.

The input is a list $(f_1,...,f_r)$ of polynomials in $R = k[x_1,...,x_n]$. Adjoin $r$ new variables, giving $S = k[x_1,...,x_n,y_1,...,y_r]$. Define the ideal $$ I = (y_1-f_1, ..., y_r-f_r) $$ of $S$ and notice that $I$ is precisely the kernel of the $R$-algebra morphism $$ \psi\colon\; S \to R,\; y_i \mapsto f_i \,\text. $$ Eliminate the $x$-variables from $I$, for instance by computing a Gröbner basis with respect to a suitable ordering, to get $$ I \cap k[y_1,...,y_r] \,\text. $$ This set is an ideal of $T=k[y_1,...,y_r]$ which contains precisely the polynomial relations you are looking for.

Proof: The morphism $\varphi\colon\; T\to R,\; y_i\mapsto f_i$ factors as $T \overset\iota\hookrightarrow S \overset\psi\twoheadrightarrow R$, hence $\ker\varphi = \iota^{-1}(\ker\psi) = \iota^{-1}(I) = I \cap T$.

---

In SageMath, your example can be solved as follows:

sage: R.<x1,x2,x3,x4> = QQ[]
sage: fs = Sequence([x1*x2, x3*x4, x1*x3, x2*x4])
sage: fs.algebraic_dependence()
Ideal (T0*T1 - T2*T3) of Multivariate Polynomial Ring in T0, T1, T2, T3 over Rational Field