Solving systems of equations and inequalities over specified domains

Adam Strzebonski

Wolfram Research, Inc.

Abstract

Mathematica 5 contains new functionality which allows to solve, possibly quantified, systems of equations and inequalities with domain restrictions on the variables. The function Reduce eliminates quantifiers and provides an explicit description of the entire solution set. The function FindInstance allows to find a specified finite number of solutions (if they exist). The function Resolve eliminates quantifiers producing an equivalent quantifier free system. In the upcoming version of Mathematica the functionality has been extended to handle several new classes of systems. The classes of systems that we can solve in full generality include quantified systems of polynomial equations and inequations in complex variables or in integers modulo n, quantified systems of polynomial equations and inequalities in real or complex variables, systems of linear equations and inequalities in integer, real, or complex variables, systems of polynomial congruences, and quantified systems of equations and inequalities in real variables containing real algebraic functions. Complex systems containing algebraic functions can be solved up to branch cut dependent equalities. We can also solve several classes of transcendental systems that can be decomposed into algebraic and simple transcendental systems. Polynomial systems in integer variables are not solvable in general (by Matiyasevich's solution of Hilbert's 10th problem), however we have implemented algorithms for solving several classes of such systems. Systems involving piecewise functions can be solved as long as the piecewise functions are constructed with conditions and functions of solvable types. In this talk I will show some examples, discuss what we can and what we can't solve, and what algorithms we use.

Systems of Polynomial Equations and Inequations in Complex Variables

Reduce can solve arbitrary systems of complex polynomial equations and inequations. The solutions can be expressed using equations and inequations, in general involving algebraic functions. The main solving tool here is the Groebner basis algorithm.

Reduce[(x - y) ((x^2) - 2 z + 1) == 1 && (x^3) - (z^2) == 2 && 
        (x^3) - (x^2) - x ≠ 3, {x, y, z}]

By default, the variables that appear later on the variable list are expressed using all variables that appear earlier. In this example z is expressed using x and y, even though we could express it using x only. On the other hand we get the same formula expressing z for both solutions for y. To get z expressed using x only we can use an option Backsubstitution.

Reduce[(x - y) ((x^2) - 2 z + 1) == 1 && (x^3) - (z^2) == 2 && 
        (x^3) - (x^2) - x ≠ 3, {x, y, z}, 
      Backsubstitution -> True]

Here is a more convincing example of why it is sensible to have Backsubstitution->False by default.

Reduce[(x^2) + a x + b == 0 && (y^5) + a y + x == 0, {x, y}]

Reduce[(x^2) + a x + b == 0 && (y^5) + a y + x == 0, {x, y}, 
      Backsubstitution -> True]

Quantified Complex Polynomial Systems

Reduce can solve arbitrary quantified systems of complex polynomial equations and inequations. For instance, here is a condition for a quartic to have all roots equal.

Reduce[(Subscript[∃ , x, (x^4) + a (x^3) + b (x^2) + c x + d == 0])((Subscript[∀ , y, (y^4) + a (y^3) + b (y^2) + c y + d == 0])x == y), {a, b, 
        c, d}]

Factor[(x^4) + a (x^3) + b (x^2) + c x + d /. ToRules[%]]

Complex Algebraic Systems

Reduce can solve arbitrary systems of complex algebraic equations and inequations, as long as the solution does not depend on the branch cut structure of algebraic functions.

Reduce[(Sqrt[(x^2) - y + 1]) == 7 && (x^2) + 4 (Sqrt[y]) == 77, {x, 
        y}]

If the solution depends on the branch cut structure of algebraic functions, the result of Reduce contains unsolved equations isolating the branch cut structure dependent part of the problem. The unsolved equations are always given with zero left hand side.

Reduce[(Sqrt[(x^2) - y + 1]) == 2 x - 2, {x, y}]

Systems of Polynomial Equations and Inequations in Real Variables

Reduce can solve arbitrary systems of real polynomial equations and inequalities. The solutions can be expressed using equations and inequalities, in general involving real algebraic functions. The main solving tool here is the cylindrical algebraic decomposition algorithm.

Even if the system contains only equations we may need inequalities to express the solutions (that's why Solve does not naturally extend to handle the real systems).

Reduce[(x^2) + (y^2) == 1, {x, y}, Reals]

The algebraic functions given in the solution are well defined and real valued in the solution branch in which they are used. For instance, here if 0 < x < (32/81) then the Root objects Root[-1 - 2 #1 + 3 x #(1^3) &, i] with i=1,2,3 are all well defined and real valued.

Reduce[3  (y^3) x - 2  y == 1, {x, y}, Reals]

Quantified Real Polynomial Systems

Reduce can solve arbitrary quantified systems of real polynomial equations and inequalities. The main solving tool here is the cylindrical algebraic decomposition algorithm. Additionally, Mathematica uses methods based on linear programming (for linear decision problems), and on the Loos-Weispfenning linear quantifier elimination algorithm (when the system is linear in the quantifier variables).

This uses the definition of limit to find the vertical asymptotes of (1/((y^2) - 2)).

Reduce[(Subscript[∀ , M, M > 0])((Subscript[∃ , δ, δ > 0])((Subscript[∀ , y, 0 < Abs[y - x] < δ])Abs[(1/((y^2) - 2))] > 
                    M)), x, Reals] // Timing

Here we can eliminate the quantifiers using the Loos-Weispfenning algorithm. The algorithm does not depend much on the number of parameters and the exponents with which they appear. Solving the quantifier free system using the cylindrical algebraic decomposition algorithm would be much harder.

\(Resolve[∃ \_{x, y}\((a\^77\ x + 9\ a\^54\ c\^23\ y - 
                a\^33\ d\^4 == 21 && 
            33\ a\^25\ x + 27\ d\^51\ y ≤ 3)\), Reals]\)

Real Algebraic Systems

Reduce can solve arbitrary systems of real algebraic equations and inequalities.

Reduce[(Sqrt[(x^2) - y + 1]) ≤ 7 && (x^2) + 4 (Sqrt[y]) > 3, {x, y}, 
      Reals]

Note that with domain Reals specified, Reduce assumes not only that all variables are assumed to be real, but also that all functions involved are real valued.

Reduce[(Sqrt[x + 2 y]) == (Sqrt[2 x - y]) - x + 1, {x, y}, 
      Reals]

If we specify that only the variables are real Reduce may be able to prove that the algebraic functions involved must be real valued, and it will still solve the problem.

Reduce[(Sqrt[x + 2 y]) == (Sqrt[2 x - y]) - x + 
            1 && (x | y) ∈ Reals, {x, y}]

However, in some cases making the variables real does not make the algebraic functions real valued, and Reduce cannot solve the problem.

Reduce[(Sqrt[x + 2 y]) == (Sqrt[2 x - y]) && (x | y) ∈ 
          Reals, {x, y}]

And indeed the equation has real solutions for which the square roots are not real valued.

Reduce[(Sqrt[x + 2 y]) == (Sqrt[2 x - y]), {x, y}]

Mixed Real and Complex Systems

Systems containing real and complex variables can be transformed to systems in real variables by replacing complex variables with their real and imaginary part.

Reduce[(Subscript[∃ , x, x ∈ Reals])(y^4) == x, y]

By default the polynomial level variables appearing in inequalities are assumed to be real.

Reduce[(x^2) + (y^2) < 1, {x, y}]

Specifying domain to be Complexes makes Reduce assume that all variables unrestricted by Element statements are Complex.

Reduce[(x^2) + (y^2) < 1, {x, y}, Complexes]

Diophantine Systems

Polynomial systems in integer variables are not solvable in general (by Matiyasevich's solution of Hilbert's 10th problem), however Reduce can solve several classes of such systems.

• Advanced documentation

One of the new classes of systems solvable in Mathematica 5.1 are systems of modular equations.

Reduce[
      Mod[2  x^2 - x y + z^2, 3] == 1 && 
        Mod[3 x z - y^2 - z, 5] == 3, {x, y, z}, Integers]

Transcendental Systems

Reduce uses several heuristics for reducing transcendental equations and inequalities to polynomial problems. Here are some examples that it can solve.

Reduce[Cos[x] == (1/2), x]

Reduce[(3^((x^2) + 2 x - 7)) == (a^2) - 1, x, Reals]

Reduce[(x^2) (2^x) == 3, x]

Reduce methods call Reduce recursively to solve the generated subproblems. This equation is solved by a combination of transcendental and Diophantine methods.

Reduce[(E^((x^2) - 5 (y^2) + 1)) + (x^2) - 5 (y^2) == 
        0, {x, y}, Integers]

Piecewise Systems

Reduce solves systems involving piecewise functions by transforming them to piecewise normal form and treating the piecewise conditions as part of the system.

Reduce[
      Max[x^2 - y^2, x + y] + Abs[x] ≥ 
        Piecewise[{{x, x ≥ 0}}, 2 y^2] + 7, {x, y}]

PiecewiseExpand[
      Max[x^2 - y^2, x + y] + Abs[x] ≥ 
        Piecewise[{{x, x ≥ 0}}, 2 y^2] + 7, 
      Method -> {"BooleanResult" -> False}]

PiecewiseExpand[
      Max[x^2 - y^2, x + y] + Abs[x] ≥ 
        Piecewise[{{x, x ≥ 0}}, 2 y^2] + 7]