kcrisman commented 13 years ago

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 commented 13 years ago

Milestone sage-4.7.3 deleted

803d690d-7156-4da7-a7d7-44cfd611c2f8 commented 12 years ago

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.

kcrisman commented 12 years ago

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 commented 12 years ago

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 commented 12 years ago

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.

803d690d-7156-4da7-a7d7-44cfd611c2f8 commented 12 years ago

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

803d690d-7156-4da7-a7d7-44cfd611c2f8 commented 12 years ago

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 commented 12 years ago

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)

803d690d-7156-4da7-a7d7-44cfd611c2f8 commented 12 years ago

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.

803d690d-7156-4da7-a7d7-44cfd611c2f8 commented 12 years ago

Attachment: trac_11941.patch.gz

limited workaround for assumption and solve

rwst commented 9 years ago

comment:14

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

rwst commented 9 years ago

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 commented 9 years ago

Upstream: Not yet reported upstream; Will do shortly.

rwst commented 9 years ago

Work Issues: report upstream

rwst commented 7 years ago

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.

pelegm commented 7 years ago

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 commented 7 years ago

comment:18

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

rwst commented 7 years ago

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?

7822f248-ba56-45f1-ab3d-4de7482bdf9f commented 6 years ago

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 commented 6 years ago

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 commented 6 years ago

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.

7822f248-ba56-45f1-ab3d-4de7482bdf9f commented 6 years ago

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 commented 6 years ago

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.

7822f248-ba56-45f1-ab3d-4de7482bdf9f commented 6 years ago

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

7822f248-ba56-45f1-ab3d-4de7482bdf9f commented 6 years ago

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 commented 6 years ago

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 commented 6 years ago

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?

7822f248-ba56-45f1-ab3d-4de7482bdf9f commented 6 years ago

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.

sagemath / sage

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

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