Opened 8 years ago

Last modified 2 years ago

#11941 needs_work defect

Solve and assumptions too aggressive with cube root of negative numbers

Reported by: kcrisman Owned by: burcin
Priority: major Milestone: sage-7.6
Component: symbolics Keywords:
Cc: pelegm Merged in:
Authors: Reviewers:
Report Upstream: Not yet reported upstream; Will do shortly. Work issues: report upstream
Branch: Commit:
Dependencies: Stopgaps:

Description

#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.

Attachments (1)

trac_11941.patch (1.0 KB) - added by mboratko 8 years ago.
limited workaround for assumption and solve

Download all attachments as: .zip

Change History (30)

comment:1 Changed 8 years ago by jdemeyer

  • Milestone sage-4.7.3 deleted

Milestone sage-4.7.3 deleted

comment:2 Changed 8 years ago by mboratko

  • Milestone set to sage-4.8

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.

comment:3 Changed 8 years ago by kcrisman

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!

comment:4 follow-up: Changed 8 years ago by burcin

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.

comment:5 in reply to: ↑ 4 ; follow-up: Changed 8 years ago by kcrisman

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.

comment:6 in reply to: ↑ 5 Changed 8 years ago by 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:

{{{(%i8) domain:complex;

(%o8) complex (%i9) solve(x3+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)]

}}}

comment:7 Changed 8 years ago by mboratko

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)]

comment:8 Changed 8 years ago by kcrisman

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)

comment:9 Changed 8 years ago by mboratko

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.

Changed 8 years ago by mboratko

limited workaround for assumption and solve

comment:10 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:11 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:12 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:13 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:14 Changed 5 years ago by rws

  • Status changed from new to needs_review

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

comment:15 Changed 5 years ago by rws

  • Report Upstream changed from N/A to Not yet reported upstream; Will do shortly.
  • Status changed from needs_review to needs_work
  • Work issues set to report upstream

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.

comment:16 Changed 3 years ago by rws

  • Cc pelegm added
  • Milestone changed from sage-6.4 to sage-7.6

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.

comment:17 Changed 3 years ago by pelegm

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]

comment:18 Changed 3 years ago by rws

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

comment:19 follow-up: Changed 2 years ago by rws

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?

comment:20 in reply to: ↑ 19 Changed 2 years ago by charpent

Replying to rws:

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 ?

comment:21 follow-up: Changed 2 years ago by 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

comment:22 Changed 2 years ago by kcrisman

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.

comment:23 in reply to: ↑ 21 Changed 2 years ago by charpent

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.

comment:24 follow-up: Changed 2 years ago by kcrisman

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.

comment:25 in reply to: ↑ 24 ; follow-up: Changed 2 years ago by charpent

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...

Last edited 2 years ago by charpent (previous) (diff)

comment:26 follow-up: Changed 2 years ago by charpent

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: [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...

Version 0, edited 2 years ago by charpent (next)

comment:27 in reply to: ↑ 25 Changed 2 years ago by rws

Replying to charpent:

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.

comment:28 in reply to: ↑ 26 ; follow-up: Changed 2 years ago by rws

Replying to charpent:

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?

comment:29 in reply to: ↑ 28 Changed 2 years ago by charpent

Replying to rws:

Replying to charpent:

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.

Note: See TracTickets for help on using tickets.