0
$\begingroup$

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?

  • 0
    I guess that finding the smallest subgroup contaning $S$ will be a good start2012-08-07
  • 0
    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.2012-08-07
  • 0
    Then give some context, where does this question comes from ?2012-08-07
  • 0
    I think that if you take $S={{e}},G=S_n$ there are exponential number of subgroups and so an optimal algorithm can't be polynomial2012-08-07
  • 0
    The problem comes from the following: I pick a subgroup of a symmetric group. You should guess, what subgroup did I pick by asking questions like: does the permutation **a** in your subgroup? You loose at your first question that has a negative answer. In case of positive answers you need to check only the subgroups that contain the elements you successfully checked. In my turn I should pick a subgroup in such a way to make it difficult for you to guess it.2012-08-07
  • 1
    @jack: Do you know to work with GAP?2012-08-07
  • 0
    @BabakSorouh: no I don't2012-08-07
  • 0
    Interestingly, there is no such algorithm for general infinite groups! As in, if you give me an element $g\in G$ and a subgroup $H\leq G$ it is in general undecidable if $g\in H$. The canonical example is taking $G=F_2\times F_2$. See [here](http://mathoverflow.net/questions/54335/showing-the-subgroup-membership-problem-is-undecidable-for-f-2-times-f-2).2012-08-07
  • 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"?2012-08-07
  • 0
    @JackSchmidt: The guesser wins the game after guessing $k$ different elements consecutively. Let he guessed the elements $a_{1},...,a_{l}$ (possibly by random choice) and let my subgroup is of order $m$ and $G$ is of order $n$ than in case of completely random choice in the step $l+1$ he will guess with probability $(m-l)/(n-l)$ but if he can find and discard the set of elements $R$ that can not appear with $a_{1},...,a_{l}$ in any subgroup of G (assuming I did not pick G as a subgroup) then his random choice will give him higher probability of success: $(m-l)/(n-l-|R|)$2012-08-08

1 Answers 1

2

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).