       Re: Simplify UnitStep expressions

• To: mathgroup at smc.vnet.net
• Subject: [mg69326] Re: Simplify UnitStep expressions
• From: p-valko at tamu.edu
• Date: Thu, 7 Sep 2006 04:30:15 -0400 (EDT)
• References: <edm1qa\$cps\$1@smc.vnet.net>

```With all due respect I am afraid the phenomenon has little to do with
the actual algorithms used in Simplify[] and FullSimplify[], but rather
with the way how assumptions are treated in general.

To illustrate my statement, I show an example without any Simplify[] or
FullSimplify[]:

In:
Assuming[a > 2, Not[a > 2] ]

I would like to get an answer False, but Mathematica gives

Out:
a <= 2

Pretty surprising result ! ! !

Regards
Peter

> Andrzej Kozlowski wrote:
> >
> > On 5 Sep 2006, at 16:20, Adam Strzebonski wrote:
> >
> >> Andrzej Kozlowski wrote:
> >>
> >>> On 1 Sep 2006, at 11:41, L. Dwynn Lafleur wrote:
> >>>
> >>>> The following is transcribed from a Mathematica 5.2 notebook in
> >>>> Windows XP:
> >>>>
> >>>> In:= Simplify[UnitStep[a-x/b], a-x/b > 0]
> >>>> Out= 1
> >>>>
> >>>> In:= Simplify[UnitStep[a-Pi/b], a-Pi/b > 0]
> >>>> Out= UnitStep[a-Pi/b]
> >>>>
> >>>> Why does the second output different from the first?  I know it has
> >>>> something to do with the fact that Pi is internally defined in
> >>>> Mathematica
> >>>> because a similar result occurs Pi is replaced with E, but what
> >>>> logic is
> >>>> being followed?
> >>>>
> >>>> --
> >>>> ======================================
> >>>>  L. Dwynn Lafleur
> >>>>  Professor of Physics
> >>>>  University of Louisiana at Lafayette
> >>>>  lafleur at louisiana.edu
> >>>> ======================================
> >>>>
> >>> Curiously, if you use FullSimplify rather then Simplify you will get:
> >>> FullSimplify[UnitStep[a-Pi/b], a-Pi/b > 0]
> >>> 1
> >>> The same holds if Pi is replaces by E, or indeed by explicit
> >>> functions of E or Pi such as Pi^2, E^Pi etc. In all such cases
> >>> FullSimplify works but Simplify does not work. Strange.
> >>> Andrzej Kozlowski
> >>
> >>
> >> The cylindrical algebraic decomposition (CAD) algorithm used by  Simplify
> >> to prove inference requires polynomial inequalities with rational  number
> >> coefficients. a-x/b > 0 is equivalent to a polynomial inequality
> >> -(a*b^2) + b*x < 0 which has rational number coefficients.
> >> a-Pi/b > 0 is equivalent to a polynomial inequality -(a*b^2) + b*Pi  < 0
> >> which has a numeric coefficient Pi which is not a rational number.
> >>
> >> Mathematica has two ways of dealing with nonrational numeric
> >> coefficients in CAD. One is to replace each nonrational coefficient
> >> with a new variable. This method always allows to decide inference
> >> (modulo the ability to zero-test the exact numeric constants), but
> >> it is potentially very expensive - CAD has a doubly exponential
> >> complexity in the number of variables and we add a new variable for
> >> each nonrational coefficient. The second method replaces nonrational
> >> numeric coefficients with their approximations. This is much less
> >> expensive, but in some cases it fails to decide inference.
> >> Simplify uses the second method which in this case is insufficient.
> >>
> >> FullSimplify uses more transformations, and one of the additional
> >> transformations succeeds.
> >>
> >> Best Regards,
> >>
> >> Wolfram Research
> >>
> >>
> >>
> >
> > Thanks for the explanation. I feel I should have guessed it, but  there
> > is one thing that still puzzles me. What exactly makes the  rational
> > approximation fail for Pi or E, since it seems to work fine  for
> > algebraic numbers such as Sqrt or 3^(1/3)? It certainly can't  be
> > anything to do with Pi or E not being algebraic, so presumably it  is
> > something to do with the way the rational approximation is chosen?  This
> > sounds very interesting; could you explain the exact reason why  the
> > rational approximation in this case doe snot work and in what  other
> > cases will it not work in general? It sounds like the reason  might be
> > mathematically interesting (?).
> >
> > Andrzej Kozlowski
> >
>
> For Pi or E the assumption mechanism uses inexact (bignum)
> approximations and constructs CAD with inexact sample point
> coordinates. If we have an inequality f(X)<0 and we do not
> find a cell with a sample point P for which f(P)<0, but we
> do find a cell with a sample point P for which f(P) is
> a bignum zero (for instance 0``20) then we cannot tell
> whether f(X)<0 has any solutions or not.
>
> For algebraic numbers the assumption mechanism does not use
> approximations. It replaces the algebraic numbers with new
> variables, because in this case it does not contribute that
> much to the complexity. We do not need to compute projections
> wrt. the new variables. Instead we make the variables last in
> the projection ordering, and in the lifting phase we only lift
> the one-point cell which corresponds to the new variables being
> equal to the corresponding algebraic numbers.
>
> Best Regards,
>