Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Solve and assumptions too aggressive with cube root of negative numbers #11941

Open
kcrisman opened this issue Oct 18, 2011 · 28 comments
Open

Solve and assumptions too aggressive with cube root of negative numbers #11941

kcrisman opened this issue Oct 18, 2011 · 28 comments

Comments

@kcrisman
Copy link
Member

#6515 did a great job helping us start to catch some assumptions when we do solving.

However, this ask.sagemath.org post catches a case where it's too aggressive, because Sage says that (-1)^(1/3) is not real.

sage: solve(x^3+1==0,x)
[x == 1/2*I*(-1)^(1/3)*sqrt(3) - 1/2*(-1)^(1/3), x == -1/2*I*(-1)^(1/3)*sqrt(3) - 1/2*(-1)^(1/3), x == (-1)^(1/3)]
sage: assume(x,'real')
sage: solve(x^3+1==0,x)
[]

What's weird about this is that the Maxima in Sage should just return x==-1.

(%i2) display2d:false;

(%o2) false
(%i3) solve(x^3+1=0,x);

(%o3) [x = -(sqrt(3)*%i-1)/2,x = (sqrt(3)*%i+1)/2,x = -1]

Not sure what's going on with that.

Upstream: Not yet reported upstream; Will do shortly.

CC: @pelegm

Component: symbolics

Work Issues: report upstream

Issue created by migration from https://trac.sagemath.org/ticket/11941

@jdemeyer
Copy link

jdemeyer commented Nov 3, 2011

Milestone sage-4.7.3 deleted

@jdemeyer jdemeyer removed this from the sage-4.8 milestone Nov 3, 2011
@mboratko
Copy link
Mannequin

mboratko mannequin commented Nov 17, 2011

comment:2

The fact that Maxima normally returns -1
and Sage returns (-1)^(1/3) is a bit odd,
as you mentioned. At a more basic level,
Sage doesn't seem to think that (-1)^(1/3)
is in RR:

sage: (-1)^(1/3) in RR
False
sage: (2)^(1/3) in RR
True

So if we fix that problem, then at least it would
return (-1)^(1/3). I also suspect that it would
properly simplify to -1 at that point as well,
based on the following example:

sage: solve(x^3 - 8 == 0, x)
[x == I*sqrt(3) - 1,
 x == -I*sqrt(3) - 1,
 x == 2]
sage: solve(x^3 + 8 == 0, x)
[x == I*(-1)^(1/3)*sqrt(3) - (-1)^(1/3),
 x == -I*(-1)^(1/3)*sqrt(3) - (-1)^(1/3),
 x == 2*(-1)^(1/3)]

(Note that the (1/3) exponent appears everywhere
next to the -1, as if some rule specifies that
Sage should not simplify it out.)

I am new, however, and I am not sure where next to look.

@mboratko mboratko mannequin added this to the sage-4.8 milestone Nov 17, 2011
@kcrisman
Copy link
Member Author

comment:3

Well, in general we do not want to do this. It's been discussed ad nauseam many times, and the sense is that:

  • Similar programs don't necessarily do this
  • (-1)^(1/3) is not really -1 but a primitive complex root of -1.

This ticket is about the fact that Maxima returns three solutions to the equation, but when we do the assume(x,'real') they all mysteriously vanish!

@burcin
Copy link

burcin commented Nov 17, 2011

comment:4

Here's what maple does:

> solve( x^3+1= 0, x);
                                     1/2               1/2
                    -1, 1/2 - 1/2 I 3   , 1/2 + 1/2 I 3

I wonder why maxima is returning (-1)^(1/3). Maybe we should ask the Maxima developers.

@kcrisman
Copy link
Member Author

comment:5

I wonder why maxima is returning (-1)^(1/3). Maybe we should ask the Maxima developers.

No, no! See this example from the description:

(%i2) display2d:false;

(%o2) false
(%i3) solve(x^3+1=0,x);

(%o3) [x = -(sqrt(3)*%i-1)/2,x = (sqrt(3)*%i+1)/2,x = -1]

We are somehow getting the (-1)^(1/3) by doing something nonstandard in Maxima, apparently. But their vanilla thing is just right.

@mboratko
Copy link
Mannequin

mboratko mannequin commented Nov 17, 2011

comment:6

It seems that sage sets domain: complex (I was made aware of this by burcin in IRC). You do get this result as follows:

{{{(%i8) domain:complex;

(%o8) complex
(%i9) solve(x^3+1=0,x);

(%o9) [x = ((-1)(1/3)sqrt(3)%i-(-1)(1/3))/2,
x = -((-1)(1/3)sqrt(3)%i+(-1)(1/3))/2,x = (-1)^(1/3)]
}}}

@mboratko
Copy link
Mannequin

mboratko mannequin commented Nov 17, 2011

comment:7

Ugh, all my comments have screwed up formatting. I wish I could edit them (can I?). I should have been:


(%i8) domain:complex;

(%o8) complex
(%i9) solve(x^3+1=0,x);

(%o9) [x = ((-1)^(1/3)*sqrt(3)*%i-(-1)^(1/3))/2,
       x = -((-1)^(1/3)*sqrt(3)*%i+(-1)^(1/3))/2,x = (-1)^(1/3)]

@kcrisman
Copy link
Member Author

comment:8

Replying to @mboratko:

It seems that sage sets domain: complex (I was made aware of this by burcin in IRC). You do get this result as follows:

Yes, we do, but I didn't bother checking that. Good work.

So of course now the question becomes what the "right" thing to do is? I don't think we want to set and unset domain:real/complex in Maxima every time we use solve, because presumably this would break other things. Or? At any rate we definitely need to keep domain:complex in general, if I recall correctly other problems that occur without it.

(%i1) (-1)^(1/3);
(%o1)                                 - 1
(%i2) domain:complex;
(%o2)                               complex
(%i3) (-1)^(1/3);
                                        1/3
(%o3)                              (- 1)

Typically we would want the latter answer, e.g in

sage: a = (-1)^(1/3)
sage: a.simplify()
(-1)^(1/3)

@mboratko
Copy link
Mannequin

mboratko mannequin commented Nov 17, 2011

comment:9

I've attached a fairly limited workaround, but it does give (semi?) desirable behavior:

sage: assume(x, 'real')
sage: solve(x^3+1==0,x)
[x == (-1)^(1/3)]

If it is then up to the user to interpret the result, this seems ok. If they want to programmatically use the result later, it's really no good. I suppose if they were aware of this and wanted to fix the result to be real then they could manually employ the same method as in my patch to the result.

I guess, as a more general question, do we want the results of solve to always return a result with domain: real, and if so can we make this change for just this function? If there is a use case where this is undesirable, then I think the only option is make the assumptions file not only check the returned value, but also modify it (so that if assume is real, then the value is actually replaced with the real values). Perhaps another option is to allow the user to specify the desired domain of results from solve.

@mboratko
Copy link
Mannequin

mboratko mannequin commented Nov 17, 2011

Attachment: trac_11941.patch.gz

limited workaround for assumption and solve

@jdemeyer jdemeyer modified the milestones: sage-5.11, sage-5.12 Aug 13, 2013
@sagetrac-vbraun-spam sagetrac-vbraun-spam mannequin modified the milestones: sage-6.1, sage-6.2 Jan 30, 2014
@sagetrac-vbraun-spam sagetrac-vbraun-spam mannequin modified the milestones: sage-6.2, sage-6.3 May 6, 2014
@sagetrac-vbraun-spam sagetrac-vbraun-spam mannequin modified the milestones: sage-6.3, sage-6.4 Aug 10, 2014
@rwst
Copy link

rwst commented Jan 31, 2015

comment:14

You need to set "needs review" if you want someone to look at your code. I'll do that now.

@rwst
Copy link

rwst commented Mar 11, 2015

comment:15

As Karl-Dieter says in comment:8 it is not desirable to switch back and forth with Maxima domain commands, so I don't think your patch is the right way to solve it, esp. since you don't get the right result, either. Presumably the failure of assumption should be reported upstream.

@rwst
Copy link

rwst commented Mar 11, 2015

Upstream: Not yet reported upstream; Will do shortly.

@rwst
Copy link

rwst commented Mar 11, 2015

Work Issues: report upstream

@rwst
Copy link

rwst commented Dec 5, 2016

comment:16

As found in #22017 SymPy gets it right. If SymPy is better than Maxima with symbolic polynomial roots then I think we should switch to SymPy for the special case.

@rwst rwst modified the milestones: sage-6.4, sage-7.6 Dec 5, 2016
@pelegm
Copy link
Contributor

pelegm commented Dec 5, 2016

comment:17

Note that sympy also incorporates assumptions into the solver:

In [2]: x = var('x', real=True)

In [3]: solve(Eq(x**3, -8))
Out[3]: [-2]

@rwst
Copy link

rwst commented Dec 5, 2016

comment:18

Switching to SymPy would also depend on something like #22024.

@rwst
Copy link

rwst commented Nov 2, 2017

comment:19

With #22024 we have now:

sage: solve(x^3+1==0,x,algorithm='sympy')
[x == -1, x == -1/2*I*sqrt(3) + 1/2, x == 1/2*I*sqrt(3) + 1/2]
sage: solve(x^3+1==0,x,algorithm='sympy', domain='real')
[x == -1]

which, as I understand the notorious discussion, isn't right either because in the complex domain Maxima's results are not reproduced?

@EmmanuelCharpentier
Copy link
Mannequin

EmmanuelCharpentier mannequin commented Nov 14, 2017

comment:20

Replying to @rwst:

With #22024 we have now:

sage: solve(x^3+1==0,x,algorithm='sympy')
[x == -1, x == -1/2*I*sqrt(3) + 1/2, x == 1/2*I*sqrt(3) + 1/2]
sage: solve(x^3+1==0,x,algorithm='sympy', domain='real')
[x == -1]

which, as I understand the notorious discussion, isn't right either because in the complex domain Maxima's results are not reproduced?

Hmmm... things seems to have changed on Maxima's front. Compare :

charpent@p-202-021:~$ sage -maxima
;;; Loading #P"/usr/local/sage-8/local/lib/ecl/sb-bsd-sockets.fas"
;;; Loading #P"/usr/local/sage-8/local/lib/ecl/sockets.fas"
;;; Loading #P"/usr/local/sage-8/local/lib/ecl/defsystem.fas"
;;; Loading #P"/usr/local/sage-8/local/lib/ecl/cmp.fas"
Maxima 5.39.0 http://maxima.sourceforge.net
using Lisp ECL 16.1.2
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
The function bug_report() provides bug reporting information.
(%i1) forget();
(%o1)                                 []
(%i2) solve(x^3+1=0,x);
                     sqrt(3) %i - 1      sqrt(3) %i + 1
(%o2)         [x = - --------------, x = --------------, x = - 1]
                           2                   2
(%i3) declare(x,real);
(%o3)                                done
(%i4) solve(x^3+1=0,x);
                     sqrt(3) %i - 1      sqrt(3) %i + 1
(%o4)         [x = - --------------, x = --------------, x = - 1]
                           2                   2
(%i5) quit();

[ Note : this is "our" Maxima ; but Maxima 5.40.0 as packaged in Debian and Cocalc's version both give the same answers... ]

and :

charpent@p-202-021:~$ sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 8.1.rc0, Release Date: 2017-11-08                 │
│ Type "notebook()" for the browser-based notebook interface.        │
│ Type "help()" for help.                                            │
└────────────────────────────────────────────────────────────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Warning: this is a prerelease version, and it may be unstable.     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
sage: forget();
sage: solve(x^3+1==0,x)
[x == 1/2*I*sqrt(3)*(-1)^(1/3) - 1/2*(-1)^(1/3), x == -1/2*I*sqrt(3)*(-1)^(1/3) - 1/2*(-1)^(1/3), x == (-1)^(1/3)]
sage: assume(x,"real")
sage: solve(x^3+1==0,x)
[]
sage: quit
Exiting Sage (CPU time 0m1.63s, Wall time 1m2.97s).

Maxima's second answer may be disputable (it doesn't account for the declaration of x as real), but Sage's is indisputably wrong, wrong, wrong.

I'm painfully tempted to file a new ticket and flag it as critical. Advice ?

@kcrisman
Copy link
Member Author

comment:21

As pointed out earlier, this is due to domain:complex:

Maxima 5.39.0 http://maxima.sourceforge.net
using Lisp ECL 16.1.2
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
The function bug_report() provides bug reporting information.
(%i1) domain:complex;
(%o1)                               complex
(%i2) solve(x^3+1=0,x);
                1/3                   1/3
           (- 1)    sqrt(3) %i - (- 1)
(%o2) [x = ------------------------------, 
                         2
                                       1/3                   1/3
                                  (- 1)    sqrt(3) %i + (- 1)              1/3
                            x = - ------------------------------, x = (- 1)   ]
                                                2

@kcrisman
Copy link
Member Author

comment:22

And if you can figure out how to deal with this - in Maxima or elsewhere - please do! I don't think this was ever reported upstream.

@EmmanuelCharpentier
Copy link
Mannequin

EmmanuelCharpentier mannequin commented Nov 14, 2017

comment:23

Replying to @kcrisman:

As pointed out earlier, this is due to domain:complex:

Maxima 5.39.0 http://maxima.sourceforge.net
using Lisp ECL 16.1.2
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
The function bug_report() provides bug reporting information.
(%i1) domain:complex;
(%o1)                               complex
(%i2) solve(x^3+1=0,x);
                1/3                   1/3
           (- 1)    sqrt(3) %i - (- 1)
(%o2) [x = ------------------------------, 
                         2
                                       1/3                   1/3
                                  (- 1)    sqrt(3) %i + (- 1)              1/3
                            x = - ------------------------------, x = (- 1)   ]
                                                2

OK. I agree that this is only disputable.

My beef is with Sage's second answer, which tells us that Sage is unable to find a real root to x^3+1==O. Maxima returns a list of three candidate answers, among whom two turn out to be unacceptable. Sage turns out no candidate.

@kcrisman
Copy link
Member Author

comment:24

You can definitely feel free to fix it or report upstream though! It is ugly to say the least.

The second answer I can't quite explain. Typically solve has nothing to do with our assumptions - least of all the declare syntax Maxima uses for what we do with things like assuming real or integer. But we do have some minimal checking (see below).

(%i3) declare(x,real);
(%o3)                                done
(%i4) solve(x^3+1=0,x);
                1/3                   1/3
           (- 1)    sqrt(3) %i - (- 1)
(%o4) [x = ------------------------------, 
                         2
                                       1/3                   1/3
                                  (- 1)    sqrt(3) %i + (- 1)              1/3
                            x = - ------------------------------, x = (- 1)   ]
                                                2

However, note that without domain:complex we get

(%i1) declare(x,real);
(%o1)                                done
(%i2) solve(x^3+1=0,x);
                     sqrt(3) %i - 1      sqrt(3) %i + 1
(%o2)         [x = - --------------, x = --------------, x = - 1]
                           2                   2

as perhaps noted above.

Here is the relevant code for how Sage checks for assumptions with solving.

        # make sure all the assumptions are satisfied
        from sage.symbolic.assumptions import assumptions
        to_check = assumptions()
        if to_check:
            for ix, soln in reversed(list(enumerate(X))):
                if soln.lhs().is_symbol():
                    if any([a.contradicts(soln) for a in to_check]):
                        del X[ix]
                        if multiplicities:
                            del ret_multiplicities[ix]
                        continue

Apparently something is going wrong here with x == -1, but I'm not sure what.

@EmmanuelCharpentier
Copy link
Mannequin

EmmanuelCharpentier mannequin commented Nov 14, 2017

comment:25

Replying to @kcrisman:

You can definitely feel free to fix it or report upstream though! It is ugly to say the least.

Inded. But the point of not replacing (-1)!^(1/n) by -1 is well taken : the first expression may, after all, be any nth root of -1 (see an example below).

So I'm not sure it's a bug. But yes, it's ugly as hell... (more tolerable in \LaTeX...).

The second answer I can't quite explain. Typically solve has nothing to do with our assumptions - least of all the declare syntax Maxima uses for what we do with things like assuming real or integer. But we do have some minimal checking (see below).

(%i3) declare(x,real);
(%o3)                                done
(%i4) solve(x^3+1=0,x);
                1/3                   1/3
           (- 1)    sqrt(3) %i - (- 1)
(%o4) [x = ------------------------------, 
                         2
                                       1/3                   1/3
                                  (- 1)    sqrt(3) %i + (- 1)              1/3
                            x = - ------------------------------, x = (- 1)   ]
                                                2

However, note that without domain:complex we get

(%i1) declare(x,real);
(%o1)                                done
(%i2) solve(x^3+1=0,x);
                     sqrt(3) %i - 1      sqrt(3) %i + 1
(%o2)         [x = - --------------, x = --------------, x = - 1]
                           2                   2

as perhaps noted above.

Here is the relevant code for how Sage checks for assumptions with solving.

        # make sure all the assumptions are satisfied
        from sage.symbolic.assumptions import assumptions
        to_check = assumptions()
        if to_check:
            for ix, soln in reversed(list(enumerate(X))):
                if soln.lhs().is_symbol():
                    if any([a.contradicts(soln) for a in to_check]):
                        del X[ix]
                        if multiplicities:
                            del ret_multiplicities[ix]
                        continue

Apparently something is going wrong here with x == -1, but I'm not sure what.

I think that our code for testing that an expression is real is too weak. After all,

sage: ((-1)^(1/3)).is_real()
False

A workaround is to force the evaluation of each root "in Sage terms", as demonstrates the following crock :

sage: Sols=solve(x^3+1==0,x);Sols
[x == 1/2*I*sqrt(3)*(-1)^(1/3) - 1/2*(-1)^(1/3), x == -1/2*I*sqrt(3)*(-1)^(1/3) - 1/2*(-1)^(1/3), x == (-1)^(1/3)]
sage: [t.rhs().is_real() for t in Sols]
[False, False, False]

None of these roots is known as real (in direct contradiction of d'Alembert's theorem, no less...). Try to force a re-evaluation of these expressions :

sage: [t.rhs().real_part()+I*t.rhs().imag_part() for t in Sols]
[-1, -1/2*I*sqrt(3) + 1/2, 1/2*I*sqrt(3) + 1/2]

(Note that this implies that, in that specific case, (-1)^(1/3) is (I*sqrt(3)+1)/2...)

Now, these re-evaluated quantities can be effectively tested for "reality" :

sage: [(t.rhs().real_part()+I*t.rhs().imag_part()).is_real() for t in Sols]
[True, False, False]

I do not know what code uses the .contradict() method for the assertion x is real, but it may fall in the same trap.

The problem is now to know what code is to be fixed : assumptions ? Or more general algebraic code ? Is this problem specific to Maxima-generated expressions, or more general ? How to force re-evaluation (real_part() and imag_part() may be highly nontrivial, or even impossible for some expressions) ?

Advice more than welcome...

@EmmanuelCharpentier
Copy link
Mannequin

EmmanuelCharpentier mannequin commented Nov 15, 2017

comment:26

One more data point : Maxima seems to be able to solve the specific test which is problematic for the current Sage assumption code. Consider :

sage: ## A few abbreviations, I'm lazy
sage: def mrhs(x):return(maxima_lib.rhs(x))
sage: def mreal(x):return(maxima_lib.featurep(x,"real"))
sage: def msolve(e,v):return(maxima_lib.solve(*[t._maxima_lib_() for t in [e,v]]
....: ))
sage: assumptions()
[]
sage: maxima_lib.facts()
[kind(sinh,one_to_one),kind(log,one_to_one),kind(tanh,one_to_one),kind(log,increasing)]
sage: [mreal(mrhs(t)) for t in msolve(x^3+1==0,x)]
[true, false, false]

Questions :

  • Should we use this ? If so
    • where ?
    • with what generality ?

Advice necessary...

@rwst
Copy link

rwst commented Nov 16, 2017

comment:27

Replying to @EmmanuelCharpentier:

I think that our code for testing that an expression is real is too weak. After all,

sage: ((-1)^(1/3)).is_real()
False

The False from is_real (and any of these functions) just means "I don't know" in absence of a Python tri-state logic. It may be possible to return Unknown here by implementing is_complex.

@rwst
Copy link

rwst commented Nov 16, 2017

comment:28

Replying to @EmmanuelCharpentier:

sage: [mreal(mrhs(t)) for t in msolve(x^3+1==0,x)]
[true, false, false]

Is that root really real? In what domain is Maxima at that point?

@EmmanuelCharpentier
Copy link
Mannequin

EmmanuelCharpentier mannequin commented Nov 16, 2017

comment:29

Replying to @rwst:

Replying to @EmmanuelCharpentier:

sage: [mreal(mrhs(t)) for t in msolve(x^3+1==0,x)]
[true, false, false]

Is that root really real?

That's what Maxima says. Whatever it does is probably more credible than what we do (see below).

In what domain is Maxima at that point?

Look for yourself :

sage: from sage.interfaces.maxima_lib import maxima_lib as ml
sage: def mrhs(x):return(ml.rhs(x))
sage: def msolve(e,v):return(ml.solve(*[t._maxima_lib_() for t in [e,v]]))
sage: def mreal(x):return(ml.featurep(x,"real"))
sage: ml.ev("domain")
complex
sage: sol=msolve(x^3+1==0,x);sol
[_SAGE_VAR_x=((-1)^(1/3)*sqrt(3)*%i-(-1)^(1/3))/2,_SAGE_VAR_x=-((-1)^(1/3)*sqrt(3)*%i+(-1)^(1/3))/2,_SAGE_VAR_x=(-1)^(1/3)]
sage: ml.ev("domain")
complex
sage: [mreal(mrhs(t)) for t in sol]
[true, false, false]
sage: [mrhs(t).sage().n() for t in sol]

[-1.00000000000000 + 1.11022302462516e-16*I,
 0.500000000000000 - 0.866025403784439*I,
 0.500000000000000 + 0.866025403784439*I]

The numerical values tend to confirm that the first root is real.

And that is our problem : the .contradicts code (in $SAGE_ROOT/src/sage/symbolic/assumptions.py) is piss-poor : it coerces the value to be tested to CC and tests if the resulting coercion belongs to RR. Aaaaarghhh...

That said, I stumbled on another problem. Our current code doesn't pass declarations to Maxima correctly :

age: assume(z,"integer")
sage: assume(z>0)
sage: assumptions()
[z is integer, z > 0]
sage: ml.facts()
[kind(sinh,one_to_one),kind(log,one_to_one),kind(tanh,one_to_one),kind(log,increasing),_SAGE_VAR_z>0]
sage: maxima_calculus("facts()")
[kind(sinh,one_to_one),kind(log,one_to_one),kind(tanh,one_to_one),kind(log,increasing),_SAGE_VAR_z>0]

I haven't (yet) checked trac to see if this is known. If not, that's a nice ticket to file.

I don't (yet) have a solution.

@mkoeppe mkoeppe removed this from the sage-7.6 milestone Dec 29, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

6 participants