Schönert & Seress Algorithm – Computing all block systems – blocks of imprimitivity

computational-algebracomputer-algebra-systemsgapgroup-theorymagma-cas

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?

Best Answer

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

Related Question