Project Topics
Get Complete Project Material File(s) Now! »
Gr¨obner bases for polynomial system solving
The general method to solve a polynomial equation set is to transform it into several equation sets of triangular-like shapes with the same solutions, and then extend the solution of each univariate polynomial within to that of the whole polynomial equation set. Therefore we start the study on polynomial system solving with Gr¨obner bases with univariate polynomial equations.
Univariate polynomial equation solving
For a univariate polynomial F ∈ K[x], now consider its solutions in some algebraic extension ˜K of K. By the algebraic fundamental theorem, F has at most deg(F) roots in ˜K, and they are the solutions of the equation F = 0. Therefore by solving F = 0 we mean to find an appropriate way to represent all these roots in ˜K of F. First, to obtain the solutions of F = 0 in Q one can use factorization of F over Q. Take F = 2×4 − 3×3 + 2×2 − 1 for example. With methods for factorization (see Section 1.4. Gr¨obner bases for polynomial system solving e.g., [153, Chapters 14&15]), one can factorize F as F = (x − 1)(2x + 1)(x2 − x + 1). Then it is known that there exist two and only two rational solutions of F = 0: x = 1 and x = 1/2. Take the fact that all integers and rational numbers can be represented precisely in computers, one knows that the whole solving process of F = 0 in Q can be implemented in computers.
Then for the solutions in R and C, we can use formula by radicals to represent precisely the solutions of F = 0 if deg(F) ≤ 4. However, the solvability by radicals has been proved to be not feasible for general equations of degree ≥ 5 as in the Galois theory [86, Chapter VI]. But this does not mean that we can do nothing to solve equations with higher degrees, for example we can adopt the numeric methods like the Newton method [82].
But in Computer Algebra we have a symbolic method to represent the real solutions of a polynomial equation, that is the real root isolation [30, 136]. It means to compute a sequence of disjoint rational intervals such that each real root of F is contained in some interval and there is only one root in each interval. As the lengths of the intervals can be arbitrarily small, we can regard these intervals as a “precise” representation of all the real roots of F without errors. Or in other words, all the distinct real solutions can be computed precisely.
To summarize, the solutions of a univariate polynomial equation in various number fields can be represented in an appropriate way, and there exist applicable methods to solve them. Therefore, in the following we always assume that any univariate polynomial equation is solvable.
Zero-dimensional polynomial equation set
In previous discussions we have made clear that the common method to solve a zerodimensional polynomial equation set via Gr¨obner bases consists of three steps: computing Gr¨obner bases w.r.t. DRL, changing their orderings to LEX, and transforming Gr¨obner bases w.r.t. LEX to either triangular sets or rational univariate representations.
We have reviewed the first two steps in this chapter, next we briefly show how the rational univariate representation (short as RUR) can be used to represent the solutions of zero-dimensional polynomial equation sets, leaving the contents for transformation to triangular sets in Section 2.4.
The rational univariate representation is a special representation of the solutions of zero-dimensional polynomial equation sets over Q (in fact it is effective over fields of characteristic 0 and of “large” positive characteristics) [135]. For a polynomial equation set defined by F ⊂ Q[x], its RUR is composed of two parts: (1) a separating variable, which is usually a linear combination of x1, . . . , xn; (2) a polynomial set in Q[x0, x1, . . . , xn] of the shape H(x0) = 0.
Characteristic sets and Wu–Ritt algorithm
Definition 2.2.1. A triangular set T = [T1, . . . , Tr] ⊂ K[x] is said to be an ascending set, if each polynomial Ti is reduced w.r.t. all Tj (j 6= i) for i = 1, . . . , r. Furthermore, for a polynomial set P ⊂ K[x], an ascending set C is a characteristic set of P if C ⊂ hPi, and prem(P, C) = {0}.
As one can see from the definition of characteristic sets and Proposition 2.1.2, the notion of characteristic sets is introduced to study the zeros of polynomial sets. The following zero relationship makes a step further.
Proposition 2.2.1. Let T = [T1, . . . , Tr] be a characteristic set of a polynomial set P ⊂ K[x]. Denote Pi = P ∪ {ini(Ti)} for i = 1, . . . , r. Then Zero(T / ini(T )) ⊂ Zero(P) ⊂ Zero(T ).
Polynomial system solving over finite fields
In general, solving a polynomial equation set F = 0 for F ⊂ K[x] means to find all its solutions in ˜Kn, where ˜K is an extension of K. Usually the solutions in the algebraic closure of K are of interest. However, for polynomial system solving over a finite field Fq, compared with the solutions in F n q , those in Fnq are usually more important because of their practical background in applications like cryptography and Coding Theory. It is obvious that the number of solutions of F = 0 in Fnq is finite, and thus one trivial method to compute them is traversing all possibilities to check whether they satisfy F = 0. This method is useful when both the cardinality q and the number of variable n are small. However, when the number of possible solutions is large (for example, in multivariate public-key cryptography the solution space is usually of cardinality greater than 2160), the traversal method is no longer applicable. In this case, one has to turn to other solving methods like those based on Gr¨obner bases and triangular sets.
A common strategy to restrict the solutions of F = 0 in Fnq is to solve F ∪ P = 0 instead, where P = {xq 1 − x1, . . . , xq n − xn} is the set of field polynomials of Fq. It is easy to prove that this strategy works as intended. To facilitate polynomial system solving over F2, the Computer Algebra system Magma introduces the Boolean polynomial ring defined over F2 whose polynomials are automatically reduced with the field relations x2i = xi for i = 1, . . . , n.
Most methods based on Gr¨obner bases and triangular sets for solving polynomial systems over fields of characteristic 0 are also applicable to systems over finite fields with the above strategy (Clearly RUR does not work any longer). However, specialized algorithms for computing Gr¨obner bases (e.g., the XL algorithm) and triangular sets over finite fields have also been designed taking the structure of finite fields into consideration [32, 3, 64, 15], and these algorithms, which are usually more efficient, should be chosen when applied to solve polynomial systems over finite fields. Furthermore, algorithms for solving SAT problems can also be used to solve polynomial systems over F2 [40, 117]. In particular SAT solvers are effective tools to achieve this purpose [47, 142].
Squarefree decomposition over finite fields
Squarefree decomposition is a fundamental tool to understand the inherent structure of a polynomial. For a principal ideal domain, there is a close relationship between radical ideals and squarefree polynomials: an ideal is radical if and only if its generating polynomial is squarefree. We will use this result later, but over a specific ring.
Furthermore, squarefree decomposition is usually a proceeding step for polynomial factorization, and thus in factorization we usually assume the input polynomial is squarefree.
Table of contents :
Introduction
I Background
Chapter 1 Gr¨obner bases
1.1 Preliminaries
1.2 Gr¨obner bases and Buchberger algorithm
1.3 FGLM algorithm
1.4 Gr¨obner bases for polynomial system solving
Chapter 2 Triangular sets
2.1 Concepts and terminologies
2.2 Characteristic sets and Wu–Ritt algorithm
2.3 Regular, simple and irreducible triangular sets
2.4 Triangular sets for polynomial system solving
Chapter 3 Some constructions in algebra
3.1 Commutative algebra
3.2 Basics of finite fields
Chapter 4 Sparse FGLM algorithms
4.1 Ideals in shape position
4.2 General ideals
4.3 Multiplication matrices
4.4 Implementation and experimental results
Chapter 5 Simple decomposition over finite fields
5.1 Simple sets revisited
5.2 Zero-dimensional polynomial sets
5.3 Positive-dimensional polynomial sets
5.4 Implementation and experimental results
Chapter 6 Squarefree decomposition and factorization over unmixed products of field extensions
6.1 Unmixed products of field extensions
6.2 Squarefree decomposition over unmixed products
6.3 Factorization over unmixed products
6.4 Examples and experiments
Chapter 7 Applications
7.1 Detection of steady states and their numbers for finite biological models
7.2 Sparse FGLM algorithm for interpolation problem in list decoding
Conclusions
Bibliography
