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?
Hi. On 10.07.10 21:40, 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. In what follows I assume "elements from K" ==> "variables" Can we decide weather these two expressions are equivalent? If there is such an algorithm, where can I find something in Haskell about it? Using distributivity of ring you convert an expression to a normal form. "A normal form" is "a sum of products". If normal forms are equal (up to associativity and commutativity of ring), expressions are equivalent. I am not aware whether Haskell has a library.
-- Best regards, Roman Beslik.
With arbitrary presentations of the ring allowed, this problem has as a
corner case the word problem for groups (
http://en.wikipedia.org/wiki/Word_problem_for_groups).
We take the ring to be K = CG, the group algebra over C of a group G. Then
take the two elements in K to be the images under the natural inclusion of G
in CG of two elements of G.
Regards,
Michael
On Sat, Jul 10, 2010 at 10:09 PM, Roman Beslik
Hi.
On 10.07.10 21:40, 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.
In what follows I assume "elements from K" ==> "variables"
Can we decide weather these two expressions are equivalent? If there is
such an algorithm, where can I find something in Haskell about it?
Using distributivity of ring you convert an expression to a normal form. "A normal form" is "a sum of products". If normal forms are equal (up to associativity and commutativity of ring), expressions are equivalent. I am not aware whether Haskell has a library.
-- Best regards, Roman Beslik.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
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
participants (4)
-
Grigory Sarnitskiy -
Heinrich Apfelmus -
Michael Magee -
Roman Beslik