Can I test that a Cayley table represents a group?

asked 2016-08-11 19:04:56 +0200

Bill_Bell gravatar image

Or can I test that the operation satisfies the axioms one at a time?

edit retag flag offensive close merge delete


You could probably do it, in the sense that you could make a loop that checks every single triple of elements (say) satisfies transitivity (by which I mean associativity) ... I'm not sure how one would do this automatically in any easier way, perhaps you have an example in mind that is more specific? (You should be able to edit your post to do so.)

kcrisman gravatar imagekcrisman ( 2016-08-11 21:15:29 +0200 )edit

You're right of course. But I could do that in Python (say). I'm actually asking for something like a test that you would apply to a single number to know whether it's prime: isPrime(7). I'm new to sage, I admit. _To me_ it seems reasonable to be able to pass a table to a constructor and then ask when it satisfies the group axioms. But I would also admit that this doesn't seem to be the way sage is intended to work.

Bill_Bell gravatar imageBill_Bell ( 2016-08-11 22:54:13 +0200 )edit

Sure, you could make a function that did that. My point is that I don't think anyone has done so, nor that what they implemented would (or could!) necessarily be any faster than checking every single possibility. Maybe there is a result that not every one would have to be checked. If you create such a function, you could consider submitting it to be added to Sage!

kcrisman gravatar imagekcrisman ( 2016-08-12 16:58:02 +0200 )edit

As mentioned here, there is a probabilistic algorithm which has running time close to $O(n^2)$. I wonder if there is a deterministic algorithm with running time less than $O(n^3)$.

A.Alharbi gravatar imageA.Alharbi ( 2016-08-12 23:26:29 +0200 )edit

I just read what appears to be theanswer on (Justin Rising's answer). (Always check wikipedia first.)

Bill_Bell gravatar imageBill_Bell ( 2016-08-13 00:18:09 +0200 )edit