Mathematical equality of objects or expression in SymPy

[Gaurav Dhingra]

Hi everyone,

   I was interested to know what would be a good answer to the question:
 Q. How to check mathematical equality of objects in SymPy? (Here the object is general, can be `PermutationGroup`, equality of `Order` or any other object possible)
like mathematically `O( log(n!) , (n, oo) )` equals `O( n*log(n), (n, oo) )`)   -> currently not done in SymPy )

 For above question i read some past archives, one of them being:  https://groups.google.com/forum/#!searchin/sympy/Mathematical$20equality/sympy/nK7UjJx28J4/LEsdy_Otl90J
Especially the @mrocklin 's comment.
I also beforehand thought of `.equals` method ( definetly not good to go with `==` ). But i suspect, since the mathematical equality in Symbolic system can be very difficult to check,
so defining `.equals` would be difficult for every object also, but for some objects it can be possible.

The other thing i thought of is `.rewrite` methods.
So in general what would be the answer to the above question? Perhaps some light upon this will be helpful.

Thanks
Gaurav Dhingra (gxyd)

[Aaron Meurer]

equals does a heuristic check using random floating point evaluation.
That obviously doesn't fit for PermutationGroup or O, but I think it
makes sense for an equals method on those objects to do mathematical
equality. For regular expressions we also recommend checking if
simplify(a - b) is 0, but that doesn't work in this case either.

For O(), I believe the best way to check equality is to check
a.contains(b) and b.contains(a). For a permutation group I'd imagine
there are different algorithms depending on the representation of the
group so an equals method probably makes sense as an abstraction.

The key thing with equals is that you either have to stipulate that a
True answer could be wrong (which is what Expr.equals does, since
random numerical testing doesn't prove two expressions are equal), or
allow it to return True, False, or None, like the assumptions system
does.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at https://groups.google.com/group/sympy.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sympy/5a91154a-eb2a-4b5f-ab6a-9dc32b4779eb%40googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Richard Fateman]

Lisp answers this question by having a bunch of equality predicates.

EQ  is true if the objects are identical in the sense of occupying the same memory location.

EQUAL tests for equal trees, where the nodes are EQ

=  is a test for numerical equality   1.0d0  and 1  for example.

There are also  predicates eql and equalp.

For a symbolic math system, for an algebra that has subtraction and zero and simplification in it,

a test for

   zerop(   simplify(A-B))    is stronger  than

  equal (simplify(A), simplify(B))

The floating point heuristic is not a great idea,  but may be useful.

A much more interesting program by W.A. Martin  (circa 1968)  and

similar work by Gaston Gonnet   is based on (essentially) hashcoding.

That is , do all arithmetic in an expression in a large-ish finite field with

random values for variables.    It was used this way:

If two expressions A B have the same hashcode, then assume they are

equal.  If they differ in structure, decide which is "simpler" by, say,

counting nodes.   If B has fewer nodes, then B is a simpler form for

A.  replace all instances of A  by B.

Does that make you squirm?

RJF

[Chris Smith]

I believe it is the intention that `equals` never (modulo errors in SymPy) returns True for questionable expressions. Are you aware of results to the contrary?

[Aaron Meurer]

Maybe I misremembered how it works. If it ever returns True based on floating point evaluation alone then it is possible for it to be wrong. 

Aaron Meurer

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/f69f4ba4-8b2d-4ee3-b6eb-d7579d74b7e8%40googlegroups.com.