[Haskell-cafe] Re: Equivalence of two expressions

[Heinrich Apfelmus]

Grigory Sarnitskiy wrote:
> I'm not very familiar with algebra and I have a question.
> 
> Imagine we have ring K. We also have two expressions formed by
> elements from K and binary operations (+) (*) from K.
> 
> Can we decide weather these two expressions are equivalent? If there
> is such an algorithm, where can I find something in Haskell about it?
> 
> If there is no such algorithm for a ring, maybe there is for a field?

Deciding whether two elements are equal depends a lot on the ring K in 
question. For instance, if K is the ring of polynomials in one variable, 
you have, every element has the normal form

    a_0 + a_1 * x + a_2 * x^2 + .. + a_n * x^n

and you can compare coefficients to decide whether equalities like

    (x-1)(x^2+x+1) = x^3 - 1

hold. For polynomial rings in several variables, things are trickier, 
but there is Buchberger's algorithm that can be used to solve such problems.


As Michael already mentioned, the problem is undecidable in general 
since it includes group rings.


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com