Solving Systems of Equations and Inequalities over Specified Domains

Adam Strzebonski

The development version of Mathematica contains an extended version of Reduce  function which can solve  (possibly quantified) systems of equations and inequalities with domain restrictions on the variables. In this talk I will show some examples, discuss what we can and what we can't solve, and what algorithms we use. 
	The domains currently supported are Complexes, Reals, Algebraics, Rationals, Integers, and Primes. The classes of systems that we can solve in full generality include quantified systems of polynomial equations and inequations in complex variables (using Groebner bases), quantified systems of polynomial equations and inequalities with real or complex variables (using cylindrical algebraic decomposition), and systems of linear equations and inequalities in integer, real, or complex variables (using several algorithms depending on the domain of variables and on whether inequalities are present). With certain restrictions, we can also solve quantified real or complex systems containing algebraic functions. We can also solve several classes of transcendental systems, using various heuristics in order to reduce the problem to solving algebraic systems and simple transcendental equations and inequalities. 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 certain classes of such systems, including systems of linear or univariate Diophantine equations and inequalities, binary quadratic Diophantine equations (with some inequality restrictions allowed), Thue equations, and systems for which the set of real solutions is bounded. We have also implemented several heursitics allowing to solve various other classes of Diophantine systems.

Quantified systems of complex polynomial equations and inequations

Reduce can solve arbitrary systems of complex equations and inequations (the old Reduce was able to do it as well). The solutions can be expressed using equations and inequations.

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 (this is different than in the old Reduce). 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 ReplaceValues.

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

Here is a more convincing example of why it is sensible to have ReplaceValues->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}, 
      ReplaceValues -> True]

We can also solve arbitrary quantified systems of complex 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[%]]

Quantified systems of real polynomial equations and inequalities

Reduce can solve arbitrary systems of real equations and inequalities. The solutions can be expressed using equations and inequalities. 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, {x, y}]

We can also solve arbitrary quantified systems of real equations and inequalities. For instance, we can use the definition of limit to find vertical asymptotes of (1/((y^2) - 2)).

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

Mixed real and complex polynomial 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]

With the default option setting DefaultDomain->Automatic, variables appearing in  inequalities on the polynomial level are assumed to be real.

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

With DefaultDomain->Complexes all variables unrestricted by Element statements are assumed to be Complex.

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

Systems containing Abs of complex variables are transformed to real polynomial systems.

Reduce[Abs[z] == 1, z]

Diophantine equations and inequalities

Diophantine equations and inequalities cannot be algorithmically solved in general, however Reduce contains methods for solving some solvable classes of Diophantine equations and inequalities.

Systems of linear equations and inequalities

For systems of linear Diophantine equations we get solutions parametrized by new integer parameters.

Reduce[
      x + 2 y + 3 z - 4 t == 5 && -3 x + 5 y - 2 z + t == 
          3 && (x | y | z | t) ∈ Integers, {x, y, z, 
        t}]

For systems of linear Diophantine equations and inequalities we get solutions parametrized by new nonnegative integer parameters.

Reduce[
      2 x - 3 y + 5 z == 1 && 
        3 x - y + z > 7 && (x | y | z) ∈ Integers, {x, y, 
        z}]

Univariate polynomial equations

Reduce can solve sparse univariate equations of degrees to high even for square-free factoring.

f = 
        Expand[(1234 (x^9999999) - 9876 (x^7777777) - 1221) (x - 
                12)];

Reduce[f == 0 && x ∈ Integers, x] // Timing

Exponent[f, x]

f = (x^123456) - 98765 (x^34567) + 212121 (x^777);
biginteger = 
        f /. x -> 1234567890;

Reduce[f == biginteger && x ∈ Integers, x] // 
      Timing

N[biginteger]

Binary quadratic equations

Parabolic type (Δ==0).

Reduce[
      (x^2) + 2 x y + (y^2) - 3 x + 4 y - 7 == 0 && (x | y) ∈ 
          Integers, {x, y}]

Elliptic type (Δ<0).

Reduce[
      (x^2) - x y + (y^2) - 1280292621682670451 == 0 && (x | y) ∈ 
          Integers, {x, y}]

Hyperbolic Pell type (Δ>0 and not a square).

Reduce[
      4 (x^2) - 3 x y - 4 (y^2) - x - y == 4 && (x | y) ∈ 
          Integers, {x, y}]

Reduce[4 (x^2) - 3 x y - 4 (y^2) - x - y == 
            4 && (x | y) ∈ Integers  && 
        0 ≤ x ≤ 10^20 && 
        0 ≤ y ≤ 10^20, {x, y}]

Hyperbolic non-Pell type (Δ>0 and a square).

Reduce[
      5 x + 2 (x^2) - y - 5 x y + 2 (y^2) == 
          7 && (x | y) ∈ Integers, {x, y}]

A reducible equation.

Reduce[
      5 x + 2 (x^2) - y - 5 x y + 2 (y^2) == 
          3 && (x | y) ∈ Integers, {x, y}]

Thue equations

Thue equations are equations of the form f(x, y)==c, where f is an irreducible homogenous form of degree >=3. Any Thue equation has a finite number of solutions.

Reduce[
      (x^3) - 4 x (y^2) + (y^3) == 1 && (x | y) ∈ Integers, {x, 
        y}]

The most difficult part of solving a Thue equation is finding a reasonably small bound on the size of solutions. If such a bound follows from the inequalities supplied to Reduce the equation can be solved much faster.

Reduce[
      (x^7) - 3 x (y^6) + 5 (y^7) == 3061061 && (x | y) ∈ 
          Integers && 0 < y < (10^100), {x, y}]

Sums of squares

Reduce[
      (x^2) + 4 (y^2) + 9 (z^2) + 16 (t^2) == 
          125 && (x | y | z | t) ∈ Integers && 
        x ≥ 0 && y ≥ 0 && z ≥ 0 && 
        t ≥ 0, {x, y, z, t}]

Systems with empty or bounded and small sets of real solutions

Reduce[
      (x^8) + (y^8) + (z^8) < 0 && (x | y | z) ∈ Integers, {x, y, 
        z}]

Reduce[
      (x^2) + 2 (y^4) + 3 (z^8) == 21 && (x | y | z) ∈ 
          Integers, {x, y, z}]

Systems with a finite number of complex solutions

Reduce[x^2 + 2  x y + 3  z^2 == 64 && 
          x - 2  y + z^2 == 12 && 
          2  y + 5 x z == 46 && (x | y | z) ∈ 
          Integers, {x, y, z}]

Systems of equations and inequalities which have no solutions modulo a small prime

Reduce[
      (x^5) - 2 (y^7) + 4 (z^4) + 3 x - 1 == 0 && (x | y | z) ∈ 
          Integers, {x, y, z}]

Systems of equations and inequalities with all variables existentially quantified, which have small solutions

Reduce[(Subscript[∃ , {x, y, z}, (x | y | z) ∈ Integers])((x^11) + 3 x (z^7) - 2 (y^2) + 4 == 0 && x ≥ 0 && 
            (x^2) + (z^2) ≤ y)]

Equations of the form c x==f(y).

Reduce[
      2423425 x == 
          1342455 + 53466 y + 352111 (y^2) + 
            45123344 (y^3) && (x | y) ∈ Integers, {x, 
        y}]

Systems that can be solved by various heuristics based on factoring, divisibility etc.

This equation factors.

Reduce[(x - 2 y + 3 z) ((x^2) - 2 (y^2) - 1) == 0 && 
        x ≥ 0 && 
        y ≥ 0 && (x | y | z) ∈ Integers, {x, y, 
        z}]

Here the nonconstant part of the equation factors.

Reduce[(x - 2 (y^2) - 3 (x^2) y) ((x^2) - 2 (y^2) - x y) == 
          4 && (x | y) ∈ Integers, {x, y}]

To solve this we use a heuristics based on divisibility.

Reduce[-(x^2) + y + x (y^3) == 0 && x > 0 && 
        y > 0 && (x | y) ∈ Integers, {x, y}]

Transcendental equations and inequalities

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]

Timing[
      sol = Reduce[
          Cos[x + y] - 2 Sin[x - y]^3 == 1 && Tan[2 x + y]^2 == 3, {x, 
            y}]]

ByteCount[sol]

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

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

Reduce[(E^(5 x)) == 
          (1/(E^(2 x))) + a && (x | a) ∈ Reals, 
      x]

Reduce[1 < Tan[x] < (Sqrt[3]) && x ∈ Reals, x]

Reduce[(E^Sin)[x] == 2, x]

Reduce[Sinh[x] == a && (E^x) == b, x]

Reduce[-1 < Log[x] < 5 && x ∈ Integers, x]

Reduce[ArcCosh[x + (y^2) - x y] == a, {x, y}]

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

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

Reduce[
      (1/5) (5^(2 x)) (7^(3 x + 2)) ≤ 
          (25/7) (7^(2 x)) (5^(3 x)) && x ∈ Reals, 
      x]

Reduce[Log[y, x] - Log[x, y] == (8/3) && x y == 16, {x, y}, 
      DefaultDomain -> Reals]

From L. Bernardin's benchmarks

Reduce[(E^(x + 3 y - 2)) == 7 && 
        (3^(2 x - y + 4)) == 2, {x, y}]

The benchmark gives a 1-parameter solution (without C[1]).

FullSimplify[(E^(x + 3 y - 2)) == 7 && 
          (3^(2 x - y + 4)) == 2 /. 
        ToRules[Drop[%,  1]], %[[1]]]

Reduce[(((x + 1))^(x + a)) == (((x + 1))^3), {x}, 
      DefaultDomain -> Reals]

The benchmark gives x==0 or x==-1 or x==3-a, no conditions on a, and no last family of solutions.

From M. Wester's benchmarks

Reduce[Sin[x] == Tan[x], x]

A combination of transcendental solver and Diophantine solver.

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