Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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:

enter image description here

Is it possible to solve this with Mathematica?

share|improve this question

3 Answers 3

up vote 13 down vote accepted

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}}
share|improve this answer
3  
Strange that it splits up the $0<x<\frac16$ and $\frac16\le x<1$ cases, which are otherwise essentially identical. –  Rahul Narain 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.

share|improve this answer
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

enter image description here

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.