[GAP Forum] calculating maximal blocks

[Max Horn]

Dear Will,

> On 12. Nov 2021, at 04:01, Will Chen <oxeimon at gmail.com> wrote:
> 
> Dear all,
> 
> Suppose M is a permutation group. What exactly is the behavior of
> MaximalBlocks?

Good question, of course, as the documentation is fuzzy resp. arguably wrong. It states that it

> ... returns  a block system that is maximal (i.e., blocks are maximal with respect to inclusion) for the action of G on Omega. If seed is given, a block system is computed in which seed is a subset of one block.

The "i.e." is misleading, as then of course one could always return the block consisting of all points in the domain 


Looking at the code, it seems what it actually is captured by this code comment:

  # iterate until the action becomes primitive

Indeed, that matches what you see:


> It seems that when M is primitive, MaximalBlocks(M, MovedPoints(M)) returns
> the trivial block system with 1 block (containing everything). Is this
> always the case?

and:

> 
> On the other hand, when M is not primitive MaximalBlocks seems to return
> something nontrivial. In this case, is it always guaranteed to return a
> nontrivial block system on which the action of M is primitive?
> 
> These two different behaviors seem confusing to me. I would have expected
> MaximalBlock to give the trivial block system of singletons in the
> primitive case.

If I was to write this function from scratch, that's probably what I'd aim for.
As it is, we can't just change long established behavior. But we definitely should adjust the documentation. I've logged an issue for that: <https://github.com/gap-system/gap/issues/4700>

> 
> Separately, is there a simple way to compute a maximal block of minimal
> cardinality?

You most likely already though of that, but you could call `AllBlocks` and then filter out all non-maximal block systems, and finally take a minimal one among all maximals. But perhaps that's not efficient enough for your application?


Best wishes
Max