Re: InequalitySolve with algebraic numbers and Simplify
- To: mathgroup at smc.vnet.net
- Subject: [mg23018] Re: [mg22987] InequalitySolve with algebraic numbers and Simplify
- From: Adam Strzebonski <adams at wolfram.com>
- Date: Tue, 11 Apr 2000 23:18:35 -0400 (EDT)
- Organization: Wolfram Reasearch, Inc
- References: <8crsqo$2b8@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Andrzej Kozlowski wrote:
>
> on 00.4.9 2:45 PM, Gianluca Gorni at gorni at dimi.uniud.it wrote:
>
> >
> > Hello!
> >
> > I had a system of *linear* inequalities in two variables x,y,
> > with simple algebraic numbers as coefficients,
> > to solve with InequalitySolve[], and I naively assumed
> > that the solution would be a set of likewise *linear*
> > inequalities. So I was surprised at results like this:
> >
> > Needs["Algebra`InequalitySolve`"]
> >
> > InequalitySolve[{y <= x*Sqrt[2], y <= x}, {x, y}]
> >
> > x <= 0 && y <= -(Sqrt[2]*Sqrt[x^2]) || x > 0 && y <= x
> >
> > Strictly speaking the result is correct, but it does not look
> > good, because of that Sqrt[x^2]. I tried with
> > Experimental`CylindricalAlgebraicDecomposition,
> > but it gives exactly the same answer.
CylindricalAlgebraicDecomposition algorithm works with polynomials
with rational number coefficients. Algebraic numbers are replaced
with new variables, so that the system in your example becomes
y <= a*x && y <= x && a^2 == 0 (and we remember that a is Sqrt[2]),
so it is no longer linear. InequalitySolve does not automatically
simplify its output.
Here is a (somewhat more general than the one given by Andrzej
Kozlowski) function which simplifies output of InequalitySolve
without changing the structure of inequalities.
In[1]:= CADSimplify[a_, assum_] :=
Switch[Head[a],
And,
CADSimplify[First[a], assum] && CADSimplify[Rest[a], First[a] &&
assum],
Or,
CADSimplify[#, assum]&/@a,
Inequality|Less|LessEqual|Greater|GreaterEqual|Equal|Unequal,
Simplify[#, assum]&/@a,
_,
a]
In[2]:= CADSimplify[a_] := CADSimplify[a, True]
In[3]:= x <= 0 && y <= -(Sqrt[2]*Sqrt[x^2]) || x > 0 && y <= x //
CADSimplify
Out[3]= x <= 0 && y <= Sqrt[2] x || x > 0 && y <= x
> >
> > Trying to reduce the results to a more manageable form, I
> > met some somewhat disappointing behaviour of Simplify[]
> > with assumptions (of Mathematica version 4):
> >
> > In: Simplify[Sqrt[x^2], x == 1 + Sqrt[2]]
> >
> > Out: Sqrt[x^2]
> >
> > It seems that Mathematica doesn't notice that 1+Sqrt[2] is real and
> > positive!
Simplify does not attempt to extract variable domain information
from equation assumptions. It would require finding all solutions,
which in general is too time consuming. Possibly FullSimplify
should do it... I am not convinced that Simplify should be
optimized for assumptions of the form x==constant. I would
expect that in most cases what one really wants is
Simplify[expr/.x->constant]
rather than
Simplify[expr, x==constant].
> > So let's teach Mathematica that it is real, at least:
> >
> > In: Simplify[Sqrt[x^2], {Element[x, Reals], x == 1 + Sqrt[2]}]
> >
> > Out: x
> >
> > Somehow I would have expected the answer to be 1+Sqrt[2], what
> > about you? Even if x has a smaller LeafCount than 1+Sqrt[2].
Simplify's objective is to minimize the ComplexityFunction...
Simplify[expr/.x->constant] would give the expected answer.
> >
> > Best regards,
> >
> > Gianluca Gorni
>
> It seems to me that you have come across some unpleasant quirks in
> Mathematica if not exactly bugs. As for the first one, I don't now exactly
> the cause of it but in general it seems that Mathematica generally has
> problems with expressions like Sqrt[x^2] in logical expressions. For
> example, compare the following behaviour:
>
> In[1]:=
> And[x < 3, x < 2] // Simplify
> Out[1]=
> x < 2
>
> In[2]:=
> And[x < 4, x > 5] // Simplify
> Out[2]=
> False
>
> In[3]:=
> And[x > 3, x^2 < 9] // Simplify
> Out[3]=
> False
>
> In[4]:=
> And[x > 3, Sqrt[x^2] < 3] // Simplify
> Out[4]=
> 2
> x > 3 && Sqrt[x ] < 3
>
> That last one should have been false, of course. On the other Simplify with
> assumptions behaves correctly in such cases:
>
> In[5]:=
> Simplify[x > 3, Sqrt[x^2] < 3]
>
> Out[5]=
> False
>
The problem is that there is an underlying assumption in
Mathematica that all variables represent complex quantities.
This means that Simplify is not allowed to simplify inequalities
using the cylindrical algebraic decomposition (CAD) algorithm,
unless all variables that appear in the inequalities are assumed
to be real. For instance, one may argue that I is a legitimate
complex solution of x^2 < 0, while we have
In[5]:= Experimental`CylindricalAlgebraicDecomposition[x^2<0, x]
Out[5]= False
On the other hand, all variables which appear in inequality
_assumptions_ are automatically assumed to be real, so the
difference between In[4] and In[5] above is that in In[4] x is
not assumed to be real, so CAD cannot be used, while in In[5]
x is assumed to be real, so CAD can be used.
The CAD algorithm is not the only method Simplify may use to
simplify inequalities. It also uses a few heuristics doing
some simple transformations of inequalities. This is how In[1],
In[2], and In[3] above get simplified to False.
The heuristics use inequality transformations which give equivalent
formulas in the language of ordered fields. They do not necessarily
give expressions equivalent to the original ones under replacement
of variables with arbitrary complex constants. For instance we have
In[1]:= Simplify[x - y < 0]
Out[1]= x <
y
even though replacing {x -> a + b I, y -> c + b I}, with a<c,
in x - y < 0 gives True, while in x < y the same replacement
gives an invalid comparison of two complex numbers.
It is somewhat of an inconsistency, but I think it is useful
to have these transformations anyway...
> This makes me feel that it should not be impossible to fix the first problem
> you pointed out. For example one might define a function:
>
> mysimplify[expr_] :=
> expr /. And[LessEqual[x_, 0], y_] /; Not[FreeQ[y, x]] :>
> And[LessEqual[x, 0], Simplify[y, LessEqual[x, 0]]]
>
> Now,
>
> In[7]:=
> Experimental`CylindricalAlgebraicDecomposition[{y <= x*Sqrt[2], y <= x},
> {x,y}]
>
> Out[7]=
> 2
> x <= 0 && y <= -Sqrt[2] Sqrt[x ] || x > 0 && y <= x
>
> We can improve this by applying mysimplify
>
> In[8]:=
> mysimplify[%]
>
> Out[8]=
> x <= 0 && y <= Sqrt[2] x || x > 0 && y <= x
>
> gives the kind of answer one would expect. Of course one would need
> something a lot more sophisticated to deal with all the cases in which this
> sort of problem may arise.
>
> The second one has indeed something to do with the ComplexityFunction.
> Mathematica does indeed give;
>
> In[9]:=
> Simplify[Sqrt[x^2], { x == 1 + Sqrt[2]}]
>
> Out[9]=
> 2
> Sqrt[x ]
>
> Suppose however, we define a complexity function f by:
>
> cf[expr_] := Count[expr, _?(Not[NumericQ[#]] &), {0, Infinity}]
>
> Now we notice something curious:
>
> In[11]:=
> Simplify[Sqrt[x^2], { x == 1 + Sqrt[2]}, ComplexityFunction -> cf]
>
> Out[11]=
> Sqrt[3 + 2 Sqrt[2]]
>
> That's a bit weird. If we try FullSimplify (Simplify does not work here!) we
> indeed get:
>
> In[12]:=
> FullSimplify[%]
>
> Out[12]=
> 1 + Sqrt[2]
>
> Why did we not get this answer the first time? Both 1+Sqrt[2] and Sqrt[3 + 2
> Sqrt[2]] have the same value of cf, namely 0, but of course the firs tone
> has much smaller LeafCount. It seems that Simplify never considered the
> simpler answer.
Simplify uses equation assumptions to PolynomialReduce expressions
w.r.t. a DegRevLex GroebnerBasis of the ideal generated by the
equations. (Of course, this is not the best way of using assumptions
x==constant, but as I mentioned above, Simplify is not optimized
for this special form of assumptions.) We have
In[1]:= PolynomialReduce[Sqrt[x^2], {x-(1 + Sqrt[2])}, {x}][[2]]
2
Out[1]= Sqrt[x ]
no complexity improvement here, so Simplify attempts to simplify
subexpressions
In[2]:= PolynomialReduce[x^2, {x-(1 + Sqrt[2])}, {x}][[2]]
Out[2]= 3 + 2 Sqrt[2]
This improves the value of cf, so Simplify replaces x^2
with 3 + 2 Sqrt[2], and gets Sqrt[3 + 2 Sqrt[2]] as a new
form of the whole expression. Now the only way to simplify
this is to use RootReduce, but RootReduce is used only by
FullSimplify.
> This happens even if we modify cf so as to make
> cf[1+Sqrt[2]] explicitly smaller than cf[Sqrt[3 + 2 Sqrt[2]]:
>
> In[16]:=
> Clear[cf]
>
> In[17]:=
> cf[expr_] :=
> 10*Count[expr, _?(Not[NumericQ[#]] &), {0, Infinity}] + LeafCount[expr]
>
> In[18]:=
> cf[1 + Sqrt[2]]
>
> Out[18]=
> 7
>
> In[19]:=
> cf[Sqrt[3 + 2*Sqrt[2]]]
>
> Out[19]=
> 13
>
> However:
>
> In[20]:=
> Simplify[Sqrt[x^2], { x == 1 + Sqrt[2]}, ComplexityFunction -> cf]
>
> Out[20]=
> Sqrt[3 + 2 Sqrt[2]]
>
> Fortunately
>
> In[21]:=
> FullSimplify[Sqrt[x^2], { x == 1 + Sqrt[2]}, ComplexityFunction -> cf]
>
> Out[21]=
> 1 + Sqrt[2]
>
> Note also that with the previous complexity function cf, which is zero on
> both 1+Sqrt[2] and Sqrt[3 + 2 Sqrt[2]]) even FullSimplify chooses the latter
> answer!. All of it does seem weirs and in need of improvement.
The given ComplexityFunction cf is the only criterion FullSimplify
has for deciding which expression is simpler. It has no reason to
choose 1+Sqrt[2] instead of Sqrt[3 + 2 Sqrt[2]], unless
cf[1+Sqrt[2]] < cf[Sqrt[3 + 2 Sqrt[2]]].
Best Regards,
Adam Strzebonski
Wolfram Research
>
> --
> Andrzej Kozlowski
> Toyama International University
> Toyama, Japan