Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a finite group $G$, how efficient can one make an algorithm to find the size of the smallest set $S$ such that $G$ is isomorphic to a group of permutations of the members of $S$? And does the answer change if one requires the output to specify not only the cardinality of $S$ but the particular action of $G$ on $S$? Might this be an NP-hard problem? Or is it a trivial thing whose solution is known to everyone on earth except me? Or somewhere in between?

share|improve this question
1  
What's trivial are the bounds that $\#G$ divides $\#S!$ and $\#S\le \#G$ or that the answer for cyclic $G$ of order $\prod p^{k_p}$ is $\sum p^{k_p}$, bu tbeyond that things can get messy ... –  Hagen von Eitzen Oct 11 '13 at 20:26
4  
I think this is a difficult problem, and that there is no efficient algorithm known. It might be easier to find an action that was close to being optimal. –  Derek Holt Oct 11 '13 at 21:04
    
Slightly less trivial is that $|S|<|G|$ except when $G$ is prime cyclic or generalized quaternion. I do remember a question about this very thing being asked on math.SE a while ago, and @JackSchmidt giving a nice summary of what's known. But I cannot find it now. –  user641 Oct 11 '13 at 23:28
    
Here are Jack Schmidt's answers, apparently mostly on group theory: math.stackexchange.com/users/583/jack-schmidt?tab=answers –  Michael Hardy Oct 11 '13 at 23:50
1  
Also see this : math.stackexchange.com/questions/514650/… –  Prahlad Vaidyanathan Oct 12 '13 at 4:04
show 1 more comment

1 Answer

up vote 3 down vote accepted

See this MO answer for links to several important papers.

The main citation is: Johnson, D. L. "Minimal permutation representations of finite groups." Amer. J. Math. 93 (1971), 857-866.

Edit (10/30/13): Check the comment below for an entire book on this subject.

share|improve this answer
    
I now find what appears to be a whole book addressing this question: Neil Saunders, Minimal Faithful Permutation Representations of Finite Groups, University of Sydney, 2011 books.google.com/… PS: OK, I now see that it's a Ph.D. thesis. It turned up in a Google Books search. –  Michael Hardy Oct 30 '13 at 23:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.