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