1
$\begingroup$

Given a finite permutation group $G$ (a subgroup of the symmetric group on a finite set) in terms of its generators, what is known about the decision problem of deciding if $G$ is $k$-transitive for a given $k \ge 1$?

What can we say about the complexity of this problem, and in what complexity class is it contained?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ You can compute a base and strong generating set in polynomial time, from which you can immediately read off information about the transitivity degree and much more. $\endgroup$
    – Derek Holt
    Commented Mar 4, 2018 at 7:54

2 Answers 2

Reset to default
6
$\begingroup$

There have been several articles on this forum discussing these topics, but here is a quick review.

A base $B$ for a subgroup $G \le {\rm Sym}(X)$ is a sequence $(\alpha_1,\ldots,\alpha_k)$ of points in $X$, such that the stabilizer $G_B$ of the sequence (i.e. the intersections of the stabilizers of the $\alpha_i$) is trivial.

For $1 \le i \le k+1$, let $G^{(i)}$ denote the stabilizer of the initial subsequence $(\alpha_1,\ldots,\alpha_{i-1})$ of $B$ (so $G^{(1)}=G$ and $G^{(k+1)} = G_B = 1$).

An strong generating set of $G$ w.r.t $B$ is a generating set that includes generators of each of the subgroup $G^{(i)}$.

Given a strong generating set, we can easily calculate the basic orbits, which are the orbits of $\alpha_i$ under $G_i$ for $1 \le i \le k$, and the order of $G$ is the product of the lengths of the basic orbits. In particular, $G$ is $k$-transitive if and only if the sequence of basic orbit lengths starts $n,n-1,\ldots,n-k+1$ where $n=|X|$.

The Schreier-Sims algorithm computes a base and strong generating set for $G$ in polynomial time, given an arbitrary generating set as input. There are many heuristics and tricks that can be used to speed it up in certain situations, and some of these were used by Sims (who sadly died recently) in his proofs of the existence of some of the sporadic finite simple groups.

Incidentally, the O'Nan simple group, which arises as a subgroup of $S_{122760}$ is the only remaining sporaic group for which no computer-free existence proof has been found. Its existence can now be proved using versions of this algorithm in a few seconds on a laptop.

See the Wikipedia article for morec details and references.

Improve this answer
$\endgroup$
4
  • $\begingroup$ How is it that the O'Nan simple group requires a computer? I wasn't aware of that. I would imagine you could just painstakingly write out what the computer does. Is this a "we wouldn't count that as computer-free" type of thing, or would any such attempt eventually require some hideously awful calculation that's just not really doable without the computer? $\endgroup$
    – zibadawa timmy
    Commented Mar 4, 2018 at 20:27
  • $\begingroup$ That's a strange question! It requires a computer for the same reason that any long calculation requires a computer. This is a calculation in $S_{122760}$. $\endgroup$
    – Derek Holt
    Commented Mar 4, 2018 at 20:41
  • $\begingroup$ But there are sporadic simples whose minimum permutation degree is several orders of magnitude larger; or whose smallest faithful representation degree is much larger. Perhaps I don't know the story of the sporadics as well as I'd like, but what I've read hasn't usually been all that clear on which proofs of existence require a computer and which don't. My meager understanding of the Monster says a dimension 196,883 algebra was constructed "by hand" by Griess, for example. $\endgroup$
    – zibadawa timmy
    Commented Mar 4, 2018 at 23:11
  • 2
    $\begingroup$ For all of the sporadic groups except for O'Nan, alternative existence proofs have been found that are more conceptual and do not involve large amounts of brute force computation. You are right in saying that the O'Nan group is very small compared with some fo the other examples (for example the Baby Monster was originally constructed computationally on about 13000 million points), so it does seem strange that it is the only one left with no alternative construction. $\endgroup$
    – Derek Holt
    Commented Mar 4, 2018 at 23:18
4
$\begingroup$

To check $k$-transitivity of an action of a finite group $G=\langle g_1,...,g_n\rangle$ on a finite set $X$ consider the graph $\Gamma$ where vertices are $k$-tuples of distinct elements of $X$ and edges are $(v, g_i\cdot v)$. The action is $k$-transitive if and only if the graph $\Gamma$ is connected. Since checking connectedness of a graph is in $P$, and the number of vertices of $\Gamma$ is $\le |X|^k$, your problem is in $P$.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ That seems to assume that $k$ is a constant. $\endgroup$
    – Derek Holt
    Commented Mar 4, 2018 at 7:57
  • 1
    $\begingroup$ The question says "for a given $k$". Yes, it is constant ($k$ is not a part of an input). $\endgroup$
    – user6976
    Commented Mar 4, 2018 at 12:51
  • $\begingroup$ Oh sure, but it doesn't need to be constant. You can compute a base and strong generating set in time $O(|S||X|^5)$ (I think that's the best known general result) where $S$ is the given generating set, and then you can just read off the degree of transitivity. $\endgroup$
    – Derek Holt
    Commented Mar 4, 2018 at 13:49
  • $\begingroup$ @Derek: I just answered the question. I do not even know what a strong generating set is. $\endgroup$
    – user6976
    Commented Mar 4, 2018 at 14:48
  • $\begingroup$ Yes I know. But I find myself incapable of distinguishing between theoretical complexity proofs and practical considerations. Even for $k=2$, you would not want to use your method if say $|X| = 10^6$, because of the space requirements. $\endgroup$
    – Derek Holt
    Commented Mar 4, 2018 at 16:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .