7
$\begingroup$

Atkinson as well as Schönert and Seress describe methods to compute the minimal block system; in particular in Permutation Group Algorithms by Ákos Seress, we find

Theorem 5.5.1 Suppose that a set S of generators for some transitive $G \leq Sym(\Omega)$ is given and $|\Omega| = n$. Then a minimal block of imprimitivity can be computed in $\mathcal{O}(n\log^3|G|+n|S|\log|G|)$ time by a deterministic algorithm.

What is hard to find, however is the time complexity of computing all non-trivial blocks of imprimitivity.

I have worked out some ideas but they all seem to be incorrect, so help is very appreciated.

  • Let $Sym(n)$.
  • Let $G = \langle x_1, ..., x_n\rangle \leq Sym(n)$ be transitive, so $|S|=n$.

According to Handbook of Computational Group Theory by Bettina Eick, Derek F. Holt, and Eamonn O'Brien then we need to run the algorithm mentioned above $n-1$ times, on the pairs $\{1, \alpha\}$ for $2 \leq \alpha \leq n$ which gives us something like $\mathcal{O}(n^2\log^3|G|+n^3\log|G|)$.

To make things a bit simpler, we expect $n \leq |G| \leq n!$ so let us consider $|G| = n!$, which gives us $\mathcal{O}(n^2\log^3n!+n^3\log n!)$ . Now, since $\log n! = \log n + \log (n-1) + ... + \log 2 \leq n\log n$, we get $\mathcal{O}(n^2(n\log n)^3+n^4\log n)$ and so $\mathcal{O}(n^5\log^3+n^4\log n)$.

And this does not even account for finding all non-trivial block systems, only the minimal ones. Then we need to "expand" these partitions by joining and joining until no new partition shows up which has its own complexity which would be nice to know.

Is there anyone out there with an idea about the theoretical complexity of computing all these block systems?

$\endgroup$

1 Answer 1

4
$\begingroup$

An arbitrary block system can be generated by $O(\log n)$ minimal block systems, so the complexity is $n^{O(\log n)}$.

Note that in the case of the regular permutation representation of a group $G$, the problem is equivalent to finding all subgroups of $G$, and an elementary abelian $2$-group of order $2^k$ has $2^{\Omega(k^2)}$ subgroups (it's about $2^{k^2/4}$), so you cannot do any better than $n^{O(\log n)}$, because that's the size of the output.

So the answer is $n^{\Theta(\log n)}$.

$\endgroup$
2
  • $\begingroup$ thank you. However, it is not clear to me how it jumps from $\mathcal{O}(n^5\log^3+n^4\log n)$. Could you elaborate on that, or, even better, could you point out any sources that explain the reasoning? $\endgroup$
    – Ingolfur
    May 24 at 13:02
  • 2
    $\begingroup$ As I pointed out, the complexity of the calculation cannot be less than the size of the output. $\endgroup$
    – Derek Holt
    May 24 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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