# Algorithm to find relations between polynomials

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).$$

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