Function Repository Resource:

DixonResultant

Source Notebook

Compute the Dixon resultant with respect to a set of polynomials and variables

Contributed by: Daniel Lichtblau

ResourceFunction["DixonResultant"][polys,vars]

computes the Dixon resultant of polys with respect to vars.

Details and Options

The Dixon resultant, in effect, eliminates the chosen variables, returning a single polynomial in any remaining variables.
The number of polynomials must be one larger than the number of variables.
The polynomials can have coefficients that involve parameters. In this case, the parameters will also appear in the Dixon resultant.
ResourceFunction["DixonResultant"] is an implementation of the method by Kapur, Saxena and Yang (see Citations subsection).
As with the ordinary resultant, the resulting polynomial must vanish in order for there to be simultaneous roots to the given system. The points at which it vanishes thus provide necessary conditions for the simultaneous vanishing of the original system.
The Dixon resultant can have factors that do not give vanishing conditions for the input polynomials. These are known as "extraneous" (or "spurious") factors.
ResourceFunction["DixonResultant"] takes a Modulus option which must be 0 (default) or a prime.
Most examples come from the provided references.

Examples

Basic Examples (3) 

Eliminate {x,y} from three polynomials to obtain conditions on the coefficient parameter, a, for which the polynomials simultaneously vanish:

In[1]:=
polys = {(x - y + a - 1)*(y + 2 + a), (x + 3*a*y)*(a*x + y), (x - 2*y)*(x + y + a - 1)};
dr = ResourceFunction["DixonResultant"][polys, {x, y}]
Out[2]=

We can find the specific values of a for which the three polynomials can simultaneously vanish in {x,y}:

In[3]:=
roots = Solve[dr == 0, a]
Out[3]=

Checking reveals that all but the last two values for a give rise to solutions in {x,y}:

In[4]:=
Map[Solve[polys == 0 /. #] &, roots]
Out[4]=

Scope (1) 

Here are two polynomials that vanish at x=1:

In[5]:=
polys = {(x - 1)*(x + 3)*(x - 4), (x + 4)*(x - 1)};
dr = ResourceFunction["DixonResultant"][polys, {x}]
Out[6]=

Options (1) 

Use the Dixon resultant modulo 127 to eliminate four variables from a system of five polynomials (example is taken from reference by Tang and Feng):

In[7]:=
polys = {9 x1 + 37 x3 + 17 x1 x2 + 120 x2 x3 + 18 x3 x5 + 58 x4^2 + 87,
   46 x1 + 43 x3 + 117 x5 + 43 x1 x2 + 93 x1 x3 + 61 x3 x4 + 48,
   32 x1 x2 + 54 x1 x4 + 56 x2 x3 + 93 x3 x5 + 60 x5^2 + 45,
   124 x1 + 93 x1 x3 + 78 x1 x4 + 45 x1 x5 + 39 x2 x3 + 38 x2 x4 + 46,
   27 x2 + 95 x2 x5 + 85 x3^2 + 74 x3 x4 + 46 x3 x5 + 77 x4 x5 + 66
   };
Timing[dixres = ResourceFunction["DixonResultant"][polys, {x1, x2, x3, x4}, Modulus -> 127]]
Out[8]=

Possible Issues (2) 

Dixon resultant computations involve symbolic row reduction and computation of determinants, and this can be slow (example is from Feng and Li reference):

In[9]:=
polys = {-99 d^2 + 90 d^4 + 86 d^4 b - 84 b f^4 + 8 m^2 d^2 n b - 10 n b^3 f,
   78 m n + 34 m b + 66 m - 53 d b + 59 b^2 + 28 b f,
   -79 m b + 53 n m^2 + 63 m^2 b - 24 n^3 - 29 d^2 f - 4 d b^2
   };
Timing[dixres = ResourceFunction["DixonResultant"][polys, {b, d}];]
Out[10]=

The result is a polynomial that eliminates the variables {b,d} from the system and it is not small:

In[11]:=
{Variables@dixres, Length@Expand@dixres, LeafCount@dixres}
Out[11]=

Here is a substantially more difficult example:

In[12]:=
polys = {x1^2 + x2^2 - 2*c12*x1*x2 - b1,
   x2^2 + x3^2 - 2*c23*x2*x3 - b2,
   x3^2 + x4^2 - 2*c34*x3*x4 - b3,
   x4^2 + x1^2 - 2*c41*x4*x1 - b4
   };

It is easy to obtain a resultant when numerical values are substituted for parameters:

In[13]:=
Timing[res = ResourceFunction["DixonResultant"][
   polys /. {c12 -> 2/3, c23 -> -1/2, c34 -> 1/2, c41 -> -3/4, b1 -> 7/3, b2 -> 11/5, b3 -> 9/7, b4 -> 2/11}, {x2, x3, x4}]]
Out[13]=

Obtaining the parametrized resultant takes far longer:

In[14]:=
Timing[dr = ResourceFunction["DixonResultant"][polys, {x2, x3, x4}];]
Out[14]=

This result is big:

In[15]:=
{Length[Expand[dr]], LeafCount[dr]}
Out[15]=

Properties and Relations (2) 

Resultants can be used to recover the usual "discriminant" from school algebra, though with an extraneous factor (to account for the possibility of the leading term vanishing):

In[16]:=
poly = a*x^2 + b*x + c;
ResourceFunction["DixonResultant"][{poly, D[poly, x]}, {x}] // Factor
Out[17]=

For two polynomials the Dixon resultant agrees with the usual resultant except perhaps for multiplicities of extraneous factors:

In[18]:=
Resultant[poly, D[poly, x], x] // Factor
Out[18]=

Define a polynomial surface implicitization problem (example is from the Tran reference):

In[19]:=
TranPolys = {-17 - 27 s + 36 s^2 - 19 s^3 - 45 s t^2 + 81 s^2 t^2 - 54 s^3 t^2 + 30 s t^3 - 54 s^2 t^3 + 36 s^3 t^3 + 10 x, 198 s - 369 s^2 t + 246 s^3 t - 198 t^2 + 369 s^2 t^2 - 246 s^3 t^2 + 100 y, -57 - 81 s^2 + 42 s^3 + 99 t^2 - 81 s t^2 - 108 s^2 t^2 + 90 s^3 t^2 - 66 t^3 + 54 s t^3 + 72 s^2 t^3 - 60 s^3 t^3 + 40 z};
elims = {s, t};
vars = {x, y, z};

Calculate the Dixon resultant:

In[20]:=
Timing[drT = ResourceFunction["DixonResultant"][TranPolys, elims];]
Out[20]=

A Groebner basis can also be used to eliminate variables; this example requires some non-default settings as well as a numeric-to-exact conversion in order to be at all efficient:

In[21]:=
Timing[gbT = GroebnerBasis[TranPolys, vars, elims, Sort -> True, MonomialOrder -> EliminationOrder, CoefficientDomain -> InexactNumbers[1000], Method -> {"GroebnerWalk", "EarlyEliminate" -> True}];]
Out[21]=

These agree up to a multiplicative constant (so there are no extraneous factors in the Dixon resultant in this example):

In[22]:=
Together[drT/Rationalize[gbT]]
Out[22]=

Applications (4) 

One common use of these resultants is to find the implicit form of a parametrized surface. We illustrate using two parametrized bicubic patches from the Newell (or Utah) Teapot. One gives an easy problem, whereas the other is more challenging:

In[23]:=
patches3D1 = {-(7/5) + (231 s^2)/125 - (56 s^3)/125 + (3 t)/16 - (
    99 s^2 t)/400 + (3 s^3 t)/50 - (39 t^2)/80 + (1287 s^2 t^2)/
    2000 - (39 s^3 t^2)/250 + t^3/5 - (33 s^2 t^3)/125 + (8 s^3 t^3)/
    125 + x, (294 s)/125 - (63 s^2)/125 - (56 s^3)/125 - (63 s t)/
    200 + (27 s^2 t)/400 + (3 s^3 t)/50 + (819 s t^2)/1000 - (
    351 s^2 t^2)/2000 - (39 s^3 t^2)/250 - (42 s t^3)/125 + (
    9 s^2 t^3)/125 + (8 s^3 t^3)/125 + y, -(12/5) - (63 t)/160 + (
    63 t^2)/160 + z};
patches3D20 = {-(33/10) + (9 s^2)/5 - (6 s^3)/5 - (27 t)/40 + (
    9 s^2 t)/8 - (3 s^3 t)/4 + (9 t^2)/10 - (27 s^2 t^2)/10 + (
    9 s^3 t^2)/5 - t^3/8 + (39 s^2 t^3)/40 - (13 s^3 t^3)/20 + x, -((3 s)/4) + (3 s^2)/4 + (9 s t^2)/10 - (9 s^2 t^2)/10 - (
    3 s t^3)/5 + (3 s^2 t^3)/5 + y, -(12/5) - (9 t)/32 + (27 s^2 t)/
    160 - (9 s^3 t)/80 + (9 t^2)/40 + (9 t^3)/160 - (27 s^2 t^3)/
    160 + (9 s^3 t^3)/80 + z};
elims = {s, t};
In[24]:=
Timing[implicit1 = ResourceFunction["DixonResultant"][patches3D1, elims];]
Out[24]=

Plot this surface:

In[25]:=
d = 6;
ContourPlot3D[
 Expand[implicit1] == 0, {x, -d, d}, {y, -d, d}, {z, -d, d}, PlotPoints -> 50]
Out[26]=

Here is the plot of the original parametrized form:

In[27]:=
d = 4;
ParametricPlot3D[{-(-(7/5) + (231 s^2)/125 - (56 s^3)/125 + (3 t)/
     16 - (99 s^2 t)/400 + (3 s^3 t)/50 - (39 t^2)/80 + (
     1287 s^2 t^2)/2000 - (39 s^3 t^2)/250 + t^3/5 - (33 s^2 t^3)/
     125 + (8 s^3 t^3)/125), -((294 s)/125 - (63 s^2)/125 - (56 s^3)/
     125 - (63 s t)/200 + (27 s^2 t)/400 + (3 s^3 t)/50 + (819 s t^2)/
     1000 - (351 s^2 t^2)/2000 - (39 s^3 t^2)/250 - (42 s t^3)/125 + (
     9 s^2 t^3)/125 + (8 s^3 t^3)/125), -(-(12/5) - (63 t)/160 + (
     63 t^2)/160)}, {s, -2 d/3, 2 d/3}, {t, -d, d}, PlotPoints -> 10]
Out[28]=

The second patch above is more difficult to put into implicit form:

In[29]:=
Timing[implicit20 = ResourceFunction["DixonResultant"][patches3D20, elims];]
Out[29]=
In[30]:=
{LeafCount[Expand@implicit1], LeafCount[Expand@implicit20]}
Out[30]=

Version History

  • 1.1.0 – 13 August 2023
  • 1.0.0 – 09 July 2020

Source Metadata

Related Resources

License Information