# Minimize the number of components in the output of Reduce

Reduce typically tries to minimize the number of components used in describing a region, but it sometimes fails, as in the following example:

Reduce[{
{x1,x2,x3} == {x1,x2,x3},
0≤x1≤1,0≤x2≤1,0≤x3≤1,x1+x2+x3==1
},{x1,x2,x3},Reals,Backsubstitution->True]


This returns:

(0 ≤ x1 < 1 && 0 ≤ x2 ≤ 1-x1 && x3 == 1-x1-x2) || (x1==1 && x2==0 && x3==0)

The desired output would be:

(0 ≤ x1 1 && 0 ≤ x2 ≤ 1-x1 && x3 == 1-x1-x2)

How can I minimize the number of components in the output of Reduce in this type of problem? The equations in my case are always polynomial, so (I believe that) Mathematica uses CylindricalDecomposition and then tries to reduce the number of components, but it sometimes does not do it as much as it is possible.

• Note the value of {x1, x2, x3} == {x1, x2, x3} as passed to Reduce[] is True; it plays no role here and may be omitted. Commented Jul 10 at 3:57
• Mathematica always had problems with simplifying such expressions. I do not know why since it is quite trivial. It is even unable to verify that the two expressions are equivalent. Commented Jul 10 at 6:09
• @azerbajdzan Reduce[Equivalent[ And @@ {{x1, x2, x3} == {x1, x2, x3}, 0 <= x1 <= 1, 0 <= x2 <= 1, 0 <= x3 <= 1, x1 + x2 + x3 == 1}, (0 <= x1 <= 1 && 0 <= x2 <= 1 - x1 && x3 == 1 - x1 - x2)], Reals] returns True for me. I think the issue is the dimension of the cross-section for x1 = const. For 0 ≤ x1 < 1, the dimension is 2; for x = 1, it is 0. Maybe the CAD algorithm keeps them disjoint. Commented Jul 10 at 23:08
• @MichaelE2 You got your code wrong. It should be equivalence of (0 ≤ x1 < 1 && 0 ≤ x2 ≤ 1-x1 && x3 == 1-x1-x2) || (x1==1 && x2==0 && x3==0) and (0 ≤ x1 ≤ 1 && 0 ≤ x2 ≤ 1-x1 && x3 == 1-x1-x2) in which case it is not able to verify that they are equivalent. Commented Jul 11 at 9:04
• @azerbajdzan Ok, Reduce[Equivalent[(0 <= x1 < 1 && 0 <= x2 <= 1 - x1 && x3 == 1 - x1 - x2) || (x1 == 1 && x2 == 0 && x3 == 0), (0 <= x1 <= 1 && 0 <= x2 <= 1 - x1 && x3 == 1 - x1 - x2)], Reals] returns True. Not sure why you say it doesn't. Sorry about the mistake before. I had done this calc earlier but didn't see a need to post until you claimed the opposite. Unfortunately I copied the wrong code from the OP in my first comment. Commented Jul 11 at 14:20

## 2 Answers

The following is like something I did once to have Mathematica set up and illustrate iterated integrals over regions in $${\Bbb R}^3$$. It works on the example at hand, but it probably needs more testing and thought about your actual use-cases. In integration, I didn't mind if I lost a component of measure zero.

interiorRule = {LessEqual -> Less, GreaterEqual -> Greater};
closureRule = {Less -> LessEqual, Greater -> GreaterEqual};

reg = And @@ {
0 <= x1 <= 1,
0 <= x2 <= 1,
0 <= x3 <= 1,
x1 + x2 + x3 == 1};
Replace[
reg,
r_ :> With[{closed = Reduce[r /. interiorRule,
{x1, x2, x3}, Reals, Backsubstitution -> True] /. closureRule},
closed /; TrueQ@Reduce[Equivalent[reg, closed], Reals]]
]

(*  0 <= x1 <= 1 && 0 <= x2 <= 1 - x1 && x3 == 1 - x1 - x2  *)


The condition makes the replacement only when equivalent; otherwise, the original region reg is untransformed. You could reduce reg first, reduced = Reduce[reg,...]; and then Replace[reduced,...] to get the reduced region if the closure is not equivalent.

If this is not helpful, I will delete it.

• @ Michael Thank you so much for your efforts, I really appreciate it. Your answer is indeed helpful, so I would definitely not delete it. I'll wait a few more days to see whether someone proposes a better approach, but this is definitely useful. Thanks a lot
– Luis
Commented Jul 11 at 21:57
• @Luis Oops, I had Reduce in the wrong place. With the update, the remark after the code makes more sense. Commented Jul 11 at 22:14

My problem was that the solutions provided by Reduce included both

• isolated points such as (x1==1 && x2==0 && x3==0), and
• open intervals whose closure was also part of the solution, such as (0 ≤ x1 < 1 && 0 ≤ x2 ≤ 1-x1 && x3 == 1-x1-x2).

I wanted to get the solution described with closed intervals whenever possible.

Thanks to Michael's code I was able to solve my problem. In the following, I refer to intervals as "components" and to isolated points as just "points".

The logic of the algorithm to solve my problem is:

1. Separate components and points in the original solution

2. Start with an empty newSolution

3. Scan through the components. For each component: Check if (Closure of component + Original solution) is equivalent to Original solution. If it is, add the closure of the component to the newSolution. Otherwise add the component.

4. Now we Scan through the points. For each point: Check if (point + newSolution) is equivalent to newSolution. If it is, do nothing. Otherwise add the point to newSolution.

I attach the code below:

solution =
Reduce[{{x1, x2, x3} == {x1, x2, x3}, 0 <= x1 <= 1, 0 <= x2 <= 1,
0 <= x3 <= 1, x1 + x2 + x3 == 1}, {x1, x2, x3}, Reals,
Backsubstitution -> True];

pointsRules = Select[List[ToRules[solution]], ListQ];
components =
Map[Apply[List, #] &,
Select[List[ToRules[solution]], Not[ListQ[#]] &]];

BackToEquations[expr_] :=
Map[# /. Rule -> Equal /. List -> And &, expr]
(*https://mathematica.stackexchange.com/questions/270822/converting-\
solutions-back-to-equations-inverse-of-torules*)

points = BackToEquations[pointsRules];

closureRule = {Less -> LessEqual, Greater -> GreaterEqual};
newSolution = False;

AddComponent[component_] :=
Module[{closedComponent = component /. closureRule},
newSolution = Or[newSolution,
If[TrueQ@
Reduce[Equivalent[Or[closedComponent, solution], solution],
Reals],
closedComponent,
component
]]
];

AddPoint[point_] := Module[{},
If[Not@
TrueQ@Reduce[Equivalent[Or[point, newSolution], newSolution],
Reals],
newSolution = Or[newSolution, point]
]
];

newSolution = False;
Scan[AddComponent[First[#]] &, components]
newSolution
Scan[AddPoint, points]
newSolution


Thanks so much Michael, the credit should go to you. So, if you like, edit this response as you wish, post it, and I'll accept it as an answer and delete this one.