Block (permutation group theory)

In permutation group theory, a block (also known as a system of imprimitivity, or a block of imprimitivity) for a permutation group G acting on a set Ω is a non-empty subset B ⊆ Ω such that for all g ∈ G, either B^g = B or B^g ∩ B = ∅. Here, B^g denotes the image of the set B under the permutation g.

The sets ∅, Ω, and the singletons {ω} for ω ∈ Ω are always blocks; these are called the trivial blocks. A permutation group is said to be primitive if it only possesses trivial blocks. Otherwise, it is called imprimitive. The notion of primitivity is central to the structure theory of permutation groups.

The blocks of a permutation group form a partition of Ω. If B is a block for the group G, then the set {B^g | g ∈ G} forms a system of imprimitivity for G. This system of imprimitivity is the set of all images of the block B under the action of G. The elements of a system of imprimitivity form a partition of Ω.

The existence of non-trivial blocks indicates that the permutation action can be broken down into smaller, more manageable parts. In essence, if a non-trivial block B exists, it suggests that the action of G on Ω can be viewed as first acting on the blocks themselves, and then acting within each block.

The concept of blocks is also closely related to the notion of imprimitivity. A transitive permutation group G acting on Ω is imprimitive if there is a non-trivial block B for G on Ω. Otherwise, G is primitive. Primitivity is a strong condition on a permutation group, and primitive groups have a significantly simpler structure than imprimitive groups.

Finding blocks is crucial in many applications of permutation groups, such as in computational group theory, where algorithms often exploit the imprimitivity structure to decompose problems into smaller subproblems. The structure of the lattice of blocks (under inclusion) provides important information about the structure of the group itself.