# Finding a Rational univariate representation (RUR) for a Polynomial System

According to Wikipedia, a RUR of a zero-dimensional system consists in a linear combination of the variables, $$x_0$$ called ''separating variable'', and a system of equations : $$\begin{cases} h(x_0)=0\\ x_1=g_1(x_0)/g_0(x_0)\\ \quad\vdots\\ x_n=g_n(x_0)/g_0(x_0), \end{cases}$$ where $$h$$ is a univariate polynomial in $$x_0$$ of degree $$D$$ and $$g_0, \dots, g_n$$ are univariate polynomials in $$x_0$$ of degree less than $$D$$.

Is there a way to find such a system in Mathematica, given a list of polynomials?

## 1 Answer

I do not recall offhand how these are computed in general. For the case of distinct roots I can illustrate one method. I'll take the example in that Wikipedia article.

We have polynomials as below.

polys = {x^2-1, (x-1)*(y-1), y^2-1};


We take as separating element t = (x-y)/2.

seppoly = t-(x-y)/2;


First compute the polynomial referred to as h(t). Then take its derivative.

tpoly =
First[GroebnerBasis[Join[polys, {seppoly}], t, {x, y},
MonomialOrder -> EliminationOrder]]
dtpoly = D[tpoly, t];

(* Out[132]= -t + t^3 *)


Now call that derivative den and find "numerator" polynomials g1 and g2 such that den*x=g1 and similar for y. I use GroebnerBasis with a monomial order that is efficient for eliminating {x,y,den} and in effect solving for {g1,g2} in terms of t.

gb = GroebnerBasis[
Join[polys, {seppoly, dtpoly - den}, den*{x, y} - {g1, g2}], {g1,
g2, t}, {x, y, den},
MonomialOrder -> {{1, 1, 1, 0, 0, 0}, {0, 0, -1, 0, 0, 0}, {0, -1,
0, 0, 0, 0}, {0, 0, 0, 1, 1, 0}, {0, 0, 0, 0, 0, 1}, {0, 0, 0,
0, -1, 0}}]

(* Out[161]= {-t + t^3, 1 + g2 + 2 t - t^2, 1 + g1 - 2 t - t^2} *)


The numerators are readily recovered.

numerators = {g1, g2} /.
First[Solve[Rest[gb] == 0, {g1, g2}]]

(* Out[164]= {-1 + 2 t + t^2, -1 - 2 t + t^2} *)


The rational univariate representation:

rur = Join[{tpoly}, {x, y} - numerators/dtpoly]

(* Out[167]= {-t + t^3, -((-1 + 2 t + t^2)/(-1 + 3 t^2)) +
x, -((-1 - 2 t + t^2)/(-1 + 3 t^2)) + y} *)

• Is there a general way to find a separating element? Or does one just have to try different things? – Thomas Ahle Mar 23 at 13:26
• A random linear combination of the variables will be a separating element with probability 1. – Daniel Lichtblau Mar 23 at 13:30
• Could you talk about how you came up with the matrix you used in MonomialOrder? – J. M.'s discontentment Mar 25 at 1:19
• @J.M'sTech... (First, thanks for fixing the typo) It is basically a block order with the elimination variables handled in a degree-reverse-lax block. The lower block is constructed to soleve for two variables in terms of a third, and those two are weighted equally for efficiency. Provided we have a correct separating element this will work since both will end up as linear leading monomials. I could have used something closer to the matrix form of EliminationOrder and maybe that would in general be more efficient for the purposes at hand. – Daniel Lichtblau Mar 25 at 15:17