Weighted-homogeneous structure of polynomial equations

Solving equations and systems of equations has historically been a guiding problem in mathematics, and one which appears in many applications. The nature of the equations, and the tools used to solve them, depend on the application. For instance, linear systems of equations are at the core of many modern digital tools, from search engines to artificial intelligence. One more general class of equations which has attracted significant attention since the 20th century is the class of systems of polynomial equations. Such equations can encode questions from physics to engineering, as well as arise in different areas of mathematics. Different algorithms have been proposed and implemented for solving them. The generality of those systems comes with a cost, and it is proved that there exists systems which no algorithm can solve in a practical time. On the other hand, those systems are designed for that purpose, and to the contrary, the existing algorithms perform remarkably well on most systems arising in applications. In order to bridge this gap between prohibitive worst-case complexity, and reasonable complexity in practice, mathematicians have studied properties of systems leading to one behaviour or the other. In particular, a significant achievement was the proof, completed in the early 2000`s, that solving a random system which has finitely many solutions takes time polynomial in the number of solutions. The main ingredient in the proof is the observation that random systems satisfy regularity properties. On the other hand, systems which appear in applications are not random systems, and they actually frequently fail to satisfy the necessary regularity properties. To generalize those results, researchers have focused on specific structural properties of polynomial systems, and whether it is possible to generalize regularity properties to systems with specific structures. One example of such structures is the class of so-called weighted-homogeneous systems. Such systems appear in several contexts, for instance in physics or cryptography. Earlier results showed how to "regularize" a weighted homogeneous systems when all the weights are positive, in order to recover a complexity polynomial in the number of solutions. This project aims at generalizing this early work, namely by allowing weights to be zero or negative, and by considering systems which are weighted-homogeneous for several systems of weights. The goal is to design adapted regularization techniques for such systems, design and implement dedicated algorithms for solving them, and bound their complexity. Beyond immediate applications to solving such systems, for example in physics, we propose to use such generalized weighted-homogeneous structures to modelize systems used when eliminating unknowns from a system of polynomial equations. The goal there is to obtain better complexity bounds for this operation, which is a crucial step in many other algorithms.

The goal of the project was to investigate algorithms for solving systems with different structures, by assigning different weights to the variables, as well as algorithms for simplifying systems of polynomial equations by eliminating variables. In a first step, we broadly investigated algebraic properties of a class of structured systems, and proposed different algorithms for solving them, under some hypotheses on the structure. Unlike in the classical cases, those algorithms are not equivalent. In terms of studying the complexity, we proposed different characterizations of the behavior of generic systems, and examined their difference and limitations. We were able to produce early complexity results under some of those hypotheses. Those results were not enough to propose a new approach for polynomial elimination. Instead, we focused our efforts on some situations where existing algorithms are not able to perform elimination. One of these situations is the use of so-called signature Gröbner bases in automatic theorem proving. Previous algorithms for computing signature Gröbner bases in this case had restrictions which made elimination impossible. This, in turn, significantly restricted the scope of those algorithms. We generalized the algorithms to accommodate more types of equations, and to lift those restrictions, so that polynomial elimination is now possible. In a separate body of work on this topic, we also produced an optimization algorithm for finding shorter proofs of relations. Another situation where elimination is impossible is the case of so-called Tate series. Those are objects arising in number theory, and there, intrinsic properties of those series make it impossible to perform elimination with the usual method of using elimination orders. However, we proved that in practice, it is possible to find a valid order which yields the same results as an elimination order. Effectively, it is done by approximating an elimination ordering, assigning a small weight to variables which should have weight zero. We then further continued this study in giving an algorithm for listing all possible weighted orderings for a given system, and in doing so computing what is called a "tropical variety". Beyond the geometric and number theoretic applications of these computations, this study can be seen as a first step towards exploring good systems of weights for systems for which there is no apparent weighted structure.