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 group G of order n and a subset S of G such that |S|=m.

What is the best algorithm for generating all the subgroups of G that contain S? How the complextity of such algorithm depends on n and m? Does it become easyer if G is a symmetric group?

share|improve this question
    
I guess that finding the smallest subgroup contaning $S$ will be a good start –  Belgi Aug 7 '12 at 9:18
    
I can not come up with a better idea for doing that than calculating all the possible multiplications of elements from S. What I really need is a proof that there is no polynomial time algorithm that will solve the above problem. –  jack Aug 7 '12 at 10:09
    
Then give some context, where does this question comes from ? –  Belgi Aug 7 '12 at 10:15
1  
@jack: Do you know to work with GAP? –  Babak S. Aug 7 '12 at 12:24
1  
How does the guesser ever win? If his only move is to guess elements, then he can only stalemate (just choose the identity element over and over). When you answer, think about how the game will work for G of order 2. Is there any strategy for the guesser (no matter how computationally expensive) that is better than "guess once completely randomly"? –  Jack Schmidt Aug 7 '12 at 14:51

1 Answer 1

I worry you have asked the wrong question. In many cases computational resources will not help the guesser. By the time the computations are non-trivial, the chance of winning even with unlimited resources is quite low.

Games where the guesser nearly always loses

If you let $G$ be even a moderately sized symmetric group, then the guesser will almost always lose, even when $k=2$. Larger $k$ just makes the game harder (until $k>m$ and it becomes impossible), so $k=2$ is the easiest version of the game. The easiest version is still hopeless.

The subgroup proposer decides (either privately or publicly) to always choose $m=2$. Even if the guesser knows that $m=2$ and plays optimally (with infinite computing resources), then the probability of winning is given in the following table where $d$ is the number of points of the symmetric group:

$$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c} d & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \ldots & 20 \\ \hline 1/p & 1 & 3 & 9 & 25 & 75 & 231 & 763 & 2619 & 9495 & \ldots & 23758664095 \\ \end{array}$$ So that by the time $G=S_{10}$, the guesser has only a 1 in 9495 chance of winning, and by the time $G=S_{20}$, the chance has dropped to less than 1 in a billion.

A nicer game, still loses

Suppose the subgroup proposer is nicer and always chooses a bigger subgroup, one that is not contained in any larger subgroup except $G$ itself (and keeps $k=2$). Even if the guesser knows this, he can only improve his chances to: $$\tiny\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c} d & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ \hline p & 1/4 & 1/2 & 7/22 & 18/53 & 31/184 & 78/353 & 197/1376 & 360/3977 & 511/363904 & 6343/396498 & 3904/39920896 \\ p & 0.25 & 0.50 & 0.32 & 0.34 & 0.17 & 0.22 & 0.14 & 0.09 & 0.001 & 0.016 & 0.0001 \\ \end{array}$$

The probability depends a little on the arithmetic properties of $d$, but overall is decreasing rapidly (especially when $d$ is prime). When $d=17$, I believe the probability of winning has decreased to less than 1 in a million.

Guesser always wins

On the other hand, if $G$ is cyclic of prime power order, then the guesser wins unless the game is patently impossible. The guesser's best strategy does not involve knowing $m$ or $k$. He just guesses elements of $G$ sorted by order (identity first, then elements of order p, then elements of order $p^2$, etc.) until you tell him he has won. The only way he can fail to win is if $k > m$, that is if you make him guess more often then there are actually correct guesses.

Similarly, if $k=1$, then the guesser always wins by choosing the identity element.

Algorithms

To determine if a guess is bad is easy in the symmetric group: this is the so-called “giant test” and is polynomial time. A good strategy would actually involve calculating the entire lattice of subgroups (reasonable only up to $d$ around 10) and choosing elements that have the highest probability of remaining in the subgroup.

Obviously, if one has correctly guessed $x$ and $y$, it would be foolish to guess anything truly new until one had finished guessing every element expressible as a product of $x$ and $y$. In other words, the smart guesser will always enumerate $\langle S \rangle$ before choosing a truly new element. This can be done in polynomial time (via the obvious naive algorithm).

Finding maximal subgroups in symmetric groups can be done quickly, but finding the full subgroup lattice is not feasible beyond $S_{20}$ (and I think $S_{15}$ takes a few days via table lookup).

share|improve this answer

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.