[math-fun] Can you please tell me the name of this pretty group?
Can any of you please tell me the name of this pretty group? 0 1 2 3 4 5 6 7 1 0 4 5 2 3 7 6 2 4 0 6 1 7 3 5 3 5 6 0 7 1 2 4 4 2 1 7 0 6 5 3 5 3 7 1 6 0 4 2 6 7 3 2 5 4 0 1 7 6 5 4 3 2 1 0 What do you think would be the best way of answering similar queries? Thanks! --MLB
Neil's already answered this, but it brings up an interesting general question: Suppose that you're given a finite group G via black-box. That is you're given its order, n. There's a black box which you can query by giving it a pair of indices between 1 and n and gives back the index of their product (and perhaps you're told that element, 1, say is the identity, and perhaps given an oracle for the inverse). What's the most efficient algorithm to identify the isomorphism class of the group, where the efficiency might be measured in how many queries you need to make? Victor On Mon, Sep 6, 2010 at 2:34 PM, Marc LeBrun <mlb@well.com> wrote:
Can any of you please tell me the name of this pretty group?
0 1 2 3 4 5 6 7 1 0 4 5 2 3 7 6 2 4 0 6 1 7 3 5 3 5 6 0 7 1 2 4 4 2 1 7 0 6 5 3 5 3 7 1 6 0 4 2 6 7 3 2 5 4 0 1 7 6 5 4 3 2 1 0
What do you think would be the best way of answering similar queries?
Thanks! --MLB
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Monday 06 September 2010 19:55:00 Victor Miller wrote:
Suppose that you're given a finite group G via black-box. That is you're given its order, n. There's a black box which you can query by giving it a pair of indices between 1 and n and gives back the index of their product (and perhaps you're told that element, 1, say is the identity, and perhaps given an oracle for the inverse). What's the most efficient algorithm to identify the isomorphism class of the group, where the efficiency might be measured in how many queries you need to make?
Google brings up a paper by someone called Kavitha which purports (presumably correctly, but I haven't checked) to prove that you can tell in time O(n) - whether the group is abelian; - whether the group is nilpotent; - what the order of each element is; - if the group is known to be abelian, what abelian group it is. Presumably the general case is much more difficult. Supposedly it's known to be in NP n co-NP for solvable groups, and it can't be any harder than graph isomorphism. Oh, I just found a paper by one Francois Le Gall which says that there's an algorithm for the abelian group isomorphism problem that takes time O(sqrt(n) log(n)^O(1)). As Kavitha's paper points out, though, there's no way even to tell whether a group is abelian without taking time proportional to n, because the centre of a nonabelian group can be large so you can't distinguish an abelian group from a nonabelian group with large centre without lots of queries. (Le Gall's paper is about efficient *quantum* algorithms for the problem, for a very restricted class of nonabelian groups.) -- g
Terrific. I also came across a paper constructive recognition -- i.e. if you're given a black box group and told that it's isomorphic to a particular group (or one of a family of groups, such as GL(n,GF(2)) to actually construct an isomorphism -- Fast constructive recognition of black box unitary groups <http://www.facstaff.bucknell.edu/pbrooksb/Papers/Br5.pdf> http://www.facstaff.bucknell.edu/pbrooksb/Papers/Br5.pdf As far as abelian groups I suspect that if you are guaranteed that the group is abelian (but told nothing else) that you can figure out its isomorphism type in time it takes to factor n. Victor On Mon, Sep 6, 2010 at 9:13 PM, Gareth McCaughan <gareth.mccaughan@pobox.com
wrote:
On Monday 06 September 2010 19:55:00 Victor Miller wrote:
Suppose that you're given a finite group G via black-box. That is you're given its order, n. There's a black box which you can query by giving it a pair of indices between 1 and n and gives back the index of their product (and perhaps you're told that element, 1, say is the identity, and perhaps given an oracle for the inverse). What's the most efficient algorithm to identify the isomorphism class of the group, where the efficiency might be measured in how many queries you need to make?
Google brings up a paper by someone called Kavitha which purports (presumably correctly, but I haven't checked) to prove that you can tell in time O(n) - whether the group is abelian; - whether the group is nilpotent; - what the order of each element is; - if the group is known to be abelian, what abelian group it is.
Presumably the general case is much more difficult. Supposedly it's known to be in NP n co-NP for solvable groups, and it can't be any harder than graph isomorphism.
Oh, I just found a paper by one Francois Le Gall which says that there's an algorithm for the abelian group isomorphism problem that takes time O(sqrt(n) log(n)^O(1)). As Kavitha's paper points out, though, there's no way even to tell whether a group is abelian without taking time proportional to n, because the centre of a nonabelian group can be large so you can't distinguish an abelian group from a nonabelian group with large centre without lots of queries.
(Le Gall's paper is about efficient *quantum* algorithms for the problem, for a very restricted class of nonabelian groups.)
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Gareth McCaughan -
Marc LeBrun -
Victor Miller