# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Create a triangular set decomposition for a given list of polynomials and variables

Contributed by:
Daniel Lichtblau

ResourceFunction["TriangularSets"][ computes a triangular decomposition of polynomials |

A triangular decomposition is a type of characteristic set, as defined by Ritt and Wu.

A set of polynomials is triangular with respect to a set of variables if the last polynomial is univariate in the last variable, the penultimate one has only the last two variables, etc.

The solution set for a polynomial ideal with finitely many solutions can be represented by a list of triangular sets.

Every solution for the polynomial system is also a solution of at least one triangular set. Every solution of a triangular set is either a solution of the original system, or else causes a leading term of a set member to vanish (where the *n*^{th} element is regarded as a polynomial in the *n*^{th} variable, with coefficients in lesser variables).

A Gröbner basis in lexicographic order is often a triangular set. Specifically, it is a triangular set whenever the ideal is radical (has no multiple solutions), and in general position with respect to the variables (has no coordinates taking the same value in more than one solution).

ResourceFunction["TriangularSets"] uses iterated pseudoremainders, while also removing polynomial divisors common to the multiplier and remainder coefficients.

ResourceFunction["TriangularSets"] replaces powers of a polynomial with the polynomial itself. In so doing, it destroys multiplicity in a solution set.

ResourceFunction["TriangularSets"] takes a Modulus option to compute triangular sets over a prime field.

Triangularize a system of three polynomials in three variables:

In[1]:= |

Out[1]= |

Check that all solutions to this system (as found by NSolve) are solutions of at least one of the triangular sets:

In[2]:= |

Out[2]= |

TriangularSets can handle more than three variables, as illustrated on a standard benchmark known as the Trinks system:

In[3]:= |

Out[3]= |

Check the size of the result in terms of number of sets and leaf count:

In[4]:= |

Out[4]= |

Show that the solutions are all solutions of at least one triangular set:

In[5]:= |

Out[5]= |

Find a triangular set decomposition for a perturbation of another benchmark known as the Caprasse system:

In[6]:= |

Out[6]= |

Check the results:

In[7]:= |

Out[7]= |

Decompose the Cassou–Nouges benchmark system into triangular sets:

In[8]:= |

Out[8]= |

Check the results:

In[9]:= |

Out[9]= |

TriangularSets can be given a prime modulus:

In[10]:= |

Out[10]= |

Obtain the modular solutions to the original system:

In[11]:= |

Out[11]= |

The fifth triangular set contains all three solutions:

In[12]:= |

Out[12]= |

Speed can vary considerably depending on the order of the variables:

In[13]:= |

Out[13]= |

The size of result can also vary considerably:

In[14]:= |

Out[14]= |

Even for a seemingly small system, this function can be slow and can return a very large result. Demonstrate this on the Katsura-5 benchmark system:

In[15]:= |

Out[15]= |

Check the number of sets and the leaf count of the result:

In[16]:= |

Out[16]= |

Check that all solutions of this system are contained in the solution sets of the triangular sets:

In[17]:= |

Out[17]= |

- 1.0.0 – 14 June 2021

This work is licensed under a Creative Commons Attribution 4.0 International License