Equations and Inequalities over Domains

The Wolfram Language normally assumes that variables which appear in equations can stand for arbitrary complex numbers. But when you use (RefLink[Reduce, paclet:ref/Reduce]), you can explicitly tell the Wolfram Language that the variables stand for objects in more restricted domains.

Solving over domains.

(RefLink[Reduce, paclet:ref/Reduce]) by default assumes that x can be complex, and gives all five complex solutions:

Reduce[x^6-x^4-4x^2+4==0,x]

But here it assumes that x is real, and gives only the real solutions:

Reduce[x^6-x^4-4x^2+4==0,x,Reals]

And here it assumes that x is an integer, and gives only the integer solutions:

Reduce[x^6-x^4-4x^2+4==0,x,Integers]

A single polynomial equation in one variable will always have a finite set of discrete solutions. And in such a case one can think of (RefLink[Reduce, paclet:ref/Reduce])[eqns,vars,dom] as just filtering the solutions by selecting the ones that happen to lie in the domain dom.

But as soon as there are more variables, things can become more complicated, with solutions to equations corresponding to parametric curves or surfaces in which the values of some variables can depend on the values of others. Often this dependence can be described by some collection of equations or inequalities, but the form of these can change significantly when one goes from one domain to another.

This gives solutions over the complex numbers as simple formulas:

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

To represent solutions over the reals requires introducing an inequality:

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

Over the integers, the solution can be represented as equations for discrete points:

Reduce[x^2+y^2==1,{x,y},Integers]

If your input involves only equations, then (RefLink[Reduce, paclet:ref/Reduce]) will by default assume that all variables are complex. But if your input involves inequalities, then (RefLink[Reduce, paclet:ref/Reduce]) will assume that any algebraic variables appearing in them are real, since inequalities can only compare real quantities.

Since the variables appear in an inequality, they are assumed to be real:

Reduce[{x+y+z==1,x^2+y^2+z^2<1},{x,y,z}]

Schematic building blocks for solutions to polynomial equations and inequalities.

For systems of polynomials over real and complex domains, the solutions always consist of a finite number of components, within which the values of variables are given by algebraic numbers or functions.

Here the components are distinguished by equations and inequations on x:

Reduce[x y^3+y==1,{x,y},Complexes]

And here the components are distinguished by inequalities on x:

Reduce[x y^3+y==1,{x,y},Reals]

While in principle (RefLink[Reduce, paclet:ref/Reduce]) can always find the complete solution to any collection of polynomial equations and inequalities with real or complex variables, the results are often very complicated, with the number of components typically growing exponentially as the number of variables increases.

With 3 variables, the solution here already involves 8 components:

Reduce[x^2==y^2==z^2==1,{x,y,z}]

As soon as one introduces functions like (RefLink[Sin, paclet:ref/Sin]) or (RefLink[Exp, paclet:ref/Exp]), even equations in single real or complex variables can have solutions with an infinite number of components. (RefLink[Reduce, paclet:ref/Reduce]) labels these components by introducing additional parameters. By default, the n(^th) parameter in a given solution will be named (RefLink[C, paclet:ref/C])[n]. In general you can specify that it should be named f[n] by giving the option setting (RefLink[GeneratedParameters, paclet:ref/GeneratedParameters])->f.

The components here are labeled by the integer parameter (Subscript[c, 1]):

Reduce[Exp[x]==2,x,GeneratedParameters->(Subscript[c,#]&)]

(RefLink[Reduce, paclet:ref/Reduce]) can handle equations not only over real and complex variables, but also over integers. Solving such Diophantine equations can often be a very difficult problem.

Describing the solution to this equation over the reals is straightforward:

Reduce[x y==8,{x,y},Reals]

The solution over the integers involves the divisors of 8:

Reduce[x y==8,{x,y},Integers]

Solving an equation like this effectively requires factoring a large number:

Reduce[{x y==7777777,x>y>0},{x,y},Integers]

(RefLink[Reduce, paclet:ref/Reduce]) can solve any system of linear equations or inequalities over the integers. With m linear equations in n variables, n-m parameters typically need to be introduced. But with inequalities, a much larger number of parameters may be needed.

Three parameters are needed here, even though there are only two variables:

Reduce[{3x-2y>1,x>0,y>0},{x,y},Integers]

With two variables, (RefLink[Reduce, paclet:ref/Reduce]) can solve any quadratic equation over the integers. The result can be a Fibonacci-like sequence, represented in terms of powers of quadratic irrationals.

Here is the solution to a Pell equation:

Reduce[{x^2==13 y^2+1,x>0,y>0},{x,y},Integers]

The actual values for specific (RefLink[C, paclet:ref/C])[1] as integers, as they should be:

FullSimplify[%/.Table[{(C[1])->i},{i,4}]]

(RefLink[Reduce, paclet:ref/Reduce]) can handle many specific classes of equations over the integers.

Here (RefLink[Reduce, paclet:ref/Reduce]) finds the solution to a Thue equation:

Reduce[x^3-4 x y^2+y^3==1,{x,y},Integers]

Changing the right-hand side to 3, the equation now has no solution:

Reduce[x^3-4 x y^2+y^3==3,{x,y},Integers]

Equations over the integers sometimes have seemingly quite random collections of solutions. And even small changes in equations can often lead them to have no solutions at all.

For polynomial equations over real and complex numbers, there is a definite decision procedure for determining whether or not any solution exists. But for polynomial equations over the integers, the unsolvability of Hilbert’s Tenth Problem demonstrates that there can never be any such general procedure.

For specific classes of equations, however, procedures can be found, and indeed many are implemented in (RefLink[Reduce, paclet:ref/Reduce]). But handling different classes of equations can often seem to require whole different branches of number theory, and quite different kinds of computations. And in fact it is known that there are universal integer polynomial equations, for which filling in some variables can make solutions for other variables correspond to the output of absolutely any possible program. This then means that for such equations there can never in general be any closed-form solution built from fixed elements like algebraic functions.

If one includes functions like (RefLink[Sin, paclet:ref/Sin]), then even for equations involving real and complex numbers the same issues can arise.

(RefLink[Reduce, paclet:ref/Reduce]) here effectively has to solve an equation over the integers:

Reduce[Sin[Pi x]^2+Sin[Pi y]^2+(x^2+y^2-25)^2==0,{x,y},Reals]

Handling equations involving integers modulo n.

Since there are only ever a finite number of possible solutions for integer equations modulo n, (RefLink[Reduce, paclet:ref/Reduce]) can systematically find them.

This finds all solutions modulo 4:

Reduce[x^5==y^4+x y+1,{x,y},Modulus->4]

(RefLink[Reduce, paclet:ref/Reduce]) can also handle equations that involve several different moduli.

Here is an equation involving two different moduli:

Reduce[Mod[2x+1,5]==Mod[x,7]&&0<x<50,x]

Different ways to specify domains for variables.

This assumes that x is an integer, but y is a real:

Reduce[{x^2+2y^2==1,x ∈ Integers,y ∈ Reals},{x,y}]

(RefLink[Reduce, paclet:ref/Reduce]) normally treats complex variables as single objects. But in dealing with functions that are not analytic or have branch cuts, it sometimes has to break them into pairs of real variables (RefLink[Re, paclet:ref/Re])[z] and (RefLink[Im, paclet:ref/Im])[z].

The result involves separate real and imaginary parts:

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

Here again there is a separate condition on the imaginary part:

Reduce[Log[z]==a,{a,z}]

(RefLink[Reduce, paclet:ref/Reduce]) by default assumes that variables that appear algebraically in inequalities are real. But you can override this by explicitly specifying (RefLink[Complexes, paclet:ref/Complexes]) as the default domain. It is often useful in such cases to be able to specify that certain variables are still real.

(RefLink[Reduce, paclet:ref/Reduce]) by default assumes that x is a real:

Reduce[x^2<1,x]

This forces (RefLink[Reduce, paclet:ref/Reduce]) to consider the case where x can be complex:

Reduce[x^2<1,x,Complexes]

Since x does not appear algebraically, (RefLink[Reduce, paclet:ref/Reduce]) immediately assumes that it can be complex:

Reduce[Abs[x]<1,x]

Here x is a real, but y can be complex:

Reduce[{Abs[y]<Abs[x],x ∈ Reals},{x,y}]

Finding particular solutions in domains.

(RefLink[Reduce, paclet:ref/Reduce]) always returns a complete representation of the solution to a system of equations or inequalities. Sometimes, however, you may just want to find particular sample solutions. You can do this using (RefLink[FindInstance, paclet:ref/FindInstance]).

If (RefLink[FindInstance, paclet:ref/FindInstance])[expr,vars,dom] returns {} then this means that the Wolfram Language has effectively proved that expr cannot be satisfied for any values of variables in the specified domain. When expr can be satisfied, (RefLink[FindInstance, paclet:ref/FindInstance]) will normally pick quite arbitrarily among values that do this, as discussed for inequalities in "Inequalities: Manipulating Equations and Inequalities".

Particularly for integer equations, (RefLink[FindInstance, paclet:ref/FindInstance]) can often find particular solutions to equations even when (RefLink[Reduce, paclet:ref/Reduce]) cannot find a complete solution. In such cases it usually returns one of the smallest solutions to the equations.

This finds the smallest integer point on an elliptic curve:

FindInstance[{x^2==y^3+12,x>0,y>0},{x,y},Integers]

One feature of (RefLink[FindInstance, paclet:ref/FindInstance]) is that it also works with Boolean expressions whose variables can have values (RefLink[True, paclet:ref/True]) or (RefLink[False, paclet:ref/False]). You can use (RefLink[FindInstance, paclet:ref/FindInstance]) to determine whether a particular expression is satisfiable, so that there is some choice of truth values for its variables that makes the expression (RefLink[True, paclet:ref/True]).

This expression cannot be satisfied for any choice of p and q:

FindInstance[p&&!(p||!q),{p,q},Booleans]

But this can:

FindInstance[p&&!(!p||!q),{p,q},Booleans]