# Reduce can't reduce an equation without appropriate assumptions

When there are three unknowns (x, y, z), Mathematica can solve it:

Reduce[ Abs[x] + Abs[y] + Abs[z] == 1 && z != 0, {x, y, z},
Reals, Backsubstitution -> True]


for four variables (x, y, z, t), Mathematica can't return a result in reasonable time:

Reduce[ Abs[x] + Abs[y] + Abs[z] + Abs[t] == 1 && t != 0, {x, y, z, t},
Reals, Backsubstitution -> True]


Maple can solve this quickly:

Is it possible to solve this with Mathematica?

-

Working with such a sophisticated function as Reduce, if we can't get the result initially we should add possibly many assumptions. Without the Backsubstitution option it yielded:

Reduce[ Abs[x] + Abs[y] + Abs[z] + Abs[t] == 1 && t != 0, {x, y, z, t}, Reals]

No more memory available.
Mathematica kernel has shut down.
Try quitting other applications and then retry.


One simple idea which comes to consideration is supplementing the system with obvious assumptions like x >= -1 && y >= -1 && z >= -1. Supplemeting the system with another inequalities restricts the search space considerably. Now we have after a bit (it took roughly 2 minutes):

Reduce[ Abs[x] + Abs[y] + Abs[z] + Abs[t] == 1 && t != 0 &&
x >= -1 && y >= -1 && z >= -1, {x, y, z, t}, Reals, Backsubstitution -> True]

(-1 < x <= 0 && -1 - x < y <= 0 && -1 - x - y < z <= 0 && t == -1 - x - y - z) ||
(-1 < x <= 0 && -1 - x < y <= 0 && -1 - x - y < z <= 0 && t == 1 + x + y + z) ||
(-1 < x <= 0 && -1 - x < y <= 0 && 0 < z < 1 + x + y && t == -1 - x - y + z) ||
(-1 < x <= 0 && -1 - x < y <= 0 && 0 < z < 1 + x + y && t == 1 + x + y - z) ||
(-1 < x <= 0 && 0 < y < 1 + x && -1 - x + y < z <= 0 && t == -1 - x + y - z) ||
(-1 < x <= 0 && 0 < y < 1 + x && -1 - x + y < z <= 0 && t == 1 + x - y + z) ||
(-1 < x <= 0 && 0 < y < 1 + x && 0 < z < 1 + x - y && t == -1 - x + y + z) ||
(-1 < x <= 0 && 0 < y < 1 + x && 0 < z < 1 + x - y && t == 1 + x - y - z) ||
(0 < x < 1/6 && -1 + x < y <= 0 && -1 + x - y < z <= 0 && t == -1 + x - y - z) ||
(0 < x < 1/6 && -1 + x < y <= 0 && -1 + x - y < z <= 0 && t == 1 - x + y + z) ||
(0 < x < 1/6 && -1 + x < y <= 0 && 0 < z < 1 - x + y && t == -1 + x - y + z) ||
(0 < x < 1/6 && -1 + x < y <= 0 && 0 < z < 1 - x + y && t == 1 - x + y - z) ||
(0 < x < 1/6 && 0 < y < 1 - x && -1 + x + y < z <= 0 && t == -1 + x + y - z) ||
(0 < x < 1/6 && 0 < y < 1 - x && -1 + x + y < z <= 0 && t == 1 - x - y + z) ||
(0 < x < 1/6 && 0 < y < 1 - x && 0 < z < 1 - x - y && t == -1 + x + y + z) ||
(0 < x < 1/6 && 0 < y < 1 - x && 0 < z < 1 - x - y && t == 1 - x - y - z) ||
(1/6 <= x < 1 && -1 + x < y < 0 && -1 + x - y < z <= 0 && t == -1 + x - y - z) ||
(1/6 <= x < 1 && -1 + x < y < 0 && -1 + x - y < z <= 0 && t == 1 - x + y + z) ||
(1/6 <= x < 1 && -1 + x < y < 0 && 0 < z < 1 - x + y && t == -1 + x - y + z) ||
(1/6 <= x < 1 && -1 + x < y < 0 && 0 < z < 1 - x + y && t == 1 - x + y - z) ||
(1/6 <= x < 1 && y == 0 && -1 + x < z < 0 && t == -1 + x - z) ||
(1/6 <= x < 1 && y == 0 && -1 + x < z < 0 && t == 1 - x + z) ||
(1/6 <= x < 1 && y == 0 && 0 <= z < 1 - x && t == -1 + x + z) ||
(1/6 <= x < 1 && y == 0 && 0 <= z < 1 - x && t == 1 - x - z) ||
(1/6 <= x < 1 && 0 < y < 1 - x && -1 + x + y < z <= 0 && t == -1 + x + y - z) ||
(1/6 <= x < 1 && 0 < y < 1 - x && -1 + x + y < z <= 0 && t == 1 - x - y + z) ||
(1/6 <= x < 1 && 0 < y < 1 - x && 0 < z < 1 - x - y && t == -1 + x + y + z) ||
(1/6 <= x < 1 && 0 < y < 1 - x && 0 < z < 1 - x - y && t == 1 - x - y - z)


We can guess that an arbitrary restriction of the numbers of underlying cases behind the system appears to be a critical issue.

Another approach is CylindricalDecomposition (it assumes that all variables are real):

CylindricalDecomposition[ Abs[x] + Abs[y] + Abs[z] + Abs[t] == 1 && t != 0 &&
x >= -1 && y >= -1 && z >= -1, {x, y, z, t}

(-1 < x <= 0 && (
(-1 - x < y <= 0 && (
(-1 - x - y < z <= 0 && (t == -1 - x - y - z || t == 1 + x + y + z)) ||
(0 < z < 1 + x + y && (t == -1 - x - y + z || t == 1 + x + y - z)))) ||
(0 < y < 1 + x && (
(-1 - x + y < z <= 0 && (t == -1 - x + y - z || t == 1 + x - y + z)) ||
(0 < z < 1 + x - y && (t == -1 - x + y + z || t == 1 + x - y - z)))))) ||
(0 < x < 1/6 && (
(-1 + x < y <= 0 && (
(-1 + x - y < z <= 0 && (t == -1 + x - y - z || t == 1 - x + y + z)) ||
(0 < z < 1 - x + y && (t == -1 + x - y + z || t == 1 - x + y - z)))) ||
(0 < y < 1 - x && (
(-1 + x + y < z <= 0 && (t == -1 + x + y - z || t == 1 - x - y + z)) ||
(0 < z < 1 - x - y && (t == -1 + x + y + z || t == 1 - x - y - z)))))) ||
(1/6 <= x < 1 && (
(-1 + x < y < 0 && ((-1 + x - y < z <= 0 && (t == -1 + x - y - z ||
t == 1 - x + y + z)) ||
(0 < z < 1 - x + y && (t == -1 + x - y + z || t == 1 - x + y - z)))) ||
(y == 0 && ((-1 + x < z < 0 && (t == -1 + x - z || t == 1 - x + z)) ||
(0 <= z < 1 - x && (t == -1 + x + z || t == 1 - x - z)))) ||
(0 < y < 1 - x && ((-1 + x + y < z <= 0 && (t == -1 + x + y - z ||
t == 1 - x - y + z)) || (0 < z < 1 - x - y && (t == -1 + x + y + z ||
t == 1 - x - y - z))))))


An interesting observation is that if we add also this condition t >= -1 the system cannot be reduced and we get ... Mathematica kernel has shut down. .... We encounter this issue working with Reduce as well as with CylindricalDecomposition. However it might depend on accessible size of memory. In such cases we can exploit SemialgebraicComponentInstances yielding a sample of points in each connected component of semialgebraic set defined by system of inequalities:

SemialgebraicComponentInstances[ Abs[x] + Abs[y] + Abs[z] + Abs[t] == 1 && t != 0 &&
x >= -1 && y >= -1 && z >= -1 && t >= -1,
{x, y, z, t}] // Short

{{x -> -(1/2), y -> 0, z -> 0, t -> -(1/2)}, {x -> -(1/2), y -> 0, z -> 0, t -> 1/2},
{x -> -(1/4), y -> -(1/4), z -> 0, t -> -(1/2)}, <<49>>,
{x -> 1/2, y -> 0, z -> 0, t -> -(1/2)}, {x -> 1/2, y -> 0, z -> 0, t -> 1/2}}

-
Strange that it splits up the $0<x<\frac16$ and $\frac16\le x<1$ cases, which are otherwise essentially identical. – Rahul Dec 1 '13 at 19:18

One way that works is to solve for one of the variables first. This seems like a natural first step. Perhaps, though, it will be considered a drawback that not all of the absolute values are expanded. We can deal with that later, if desired. Most importantly, though, finding the solution takes less than 0.2 seconds.

Reduce[Equal @@ #[[1]], {x, y, z, t}, Reals, Backsubstitution -> True] & /@
Solve[Abs[x] + Abs[y] + Abs[z] + Abs[t] == 1 && t != 0, t, Reals]

(* {(-1 < x <= 0 && -1 - x < y <= 0 && -1 - x - y < z < 1 + x + y &&
t == 1 - Abs[x] - Abs[y] - Abs[z]) ||
(-1 < x <= 0 && 0 < y < 1 + x && -1 - x + y < z < 1 + x - y &&
t == 1 - Abs[x] - Abs[y] - Abs[z]) ||
(0 < x < 1 && -1 + x < y <= 0 && -1 + x - y < z < 1 - x + y &&
t == 1 - Abs[x] - Abs[y] - Abs[z]) ||
(0 < x < 1 && 0 < y < 1 - x && -1 + x + y < z < 1 - x - y &&
t == 1 - Abs[x] - Abs[y] - Abs[z]),
(-1 < x <= 0 && -1 - x < y <= 0 && -1 - x - y < z < 1 + x + y &&
t == -1 + Abs[x] + Abs[y] + Abs[z]) ||
(-1 < x <= 0 &&  0 < y < 1 + x && -1 - x + y < z < 1 + x - y &&
t == -1 + Abs[x] + Abs[y] + Abs[z]) ||
(0 < x < 1 && -1 + x < y <= 0 && -1 + x - y < z < 1 - x + y &&
t == -1 + Abs[x] + Abs[y] + Abs[z]) ||
(0 < x < 1 && 0 < y < 1 - x && -1 + x + y < z < 1 - x - y &&
t == -1 + Abs[x] + Abs[y] + Abs[z])}   *)


One can manually expand the absolute values with the following. It it replaces an equation with the form Abs[u] in it by two, one with u plus the condition that u >= 0 and one with -u plus the condition that u < 0.

absExpand = eq_Equal?(! FreeQ[#, Abs] &) :>
Fold[(#1 /. Abs[#2] :> #2) && #2 >= 0 || (#1 /. Abs[#2] :> -#2) && #2 < 0 &,
eq,
Union @ Cases[Abs[x] + Abs[y] + Abs[z] + Abs[t] == 1, Abs[u_] :> u,
Infinity]]


One can then take the output above and process it further with Reduce:

Reduce[Or @@ # /. absExpand, {x, y, z, t}, Reals, Backsubstitution -> True] &@
(Reduce[Equal @@ #[[1]], {x, y, z, t}, Reals, Backsubstitution -> True] & /@
Solve[Abs[x] + Abs[y] + Abs[z] + Abs[t] == 1 && t != 0, t, Reals])


It takes about 10 seconds and 200 MB in all, which considerable faster than using just a single Reduce. The output looks identical to Artes's first one, with the interval 1 <= x <= 1 divided into three intervals at 0 and 1/6.

-
Reduce[#, {x, y, z, t}, Reals] & /@
PiecewiseExpand[Abs[x] + Abs[y] + Abs[z] + Abs[t] == 1, Reals]

Reduce[Abs@x + Abs@y + Abs@z + Abs@t == 1 && x < 0 && y z t != 0, {y, z, t}, Reals] ||
Reduce[Abs@x + Abs@y + Abs@z + Abs@t == 1 && x > 0 && y z t != 0, {y, z, t}, Reals] /.
{Less -> LessEqual,  Greater -> GreaterEqual} // BooleanMinimize

Reduce[Abs@x + Abs@y + Abs@z + Abs@t == 1 && #, {x, y, z, t}] & /@
(And @@@ Tuples[{# < 0, # > 0} & /@ {x, y, z, t}]) /.
{Less -> LessEqual, Greater -> GreaterEqual, List -> Or} // BooleanMinimize


-