Subgroup Accessibility in Group Order Logic
Abstract
We investigate the expressive power of fixed-point logics (FP) and their extensions in defining generating sets for accessible subgroups of definable permutation groups. This operation, computable in polynomial time via the Schreier-Sims algorithm, plays a central role in the group-theoretic approach to Graph Isomorphism and Graph Canonisation. In particular, it underpins polynomial-time canonisation for bounded colour-class graphs--a class for which no natural logic capturing P is currently known. We first show that this operation cannot, in general, be expressed in any logic for P. This limitation arises from the fact that accessible subgroups need not admit symmetric generating sets of polynomial size. However, we prove that when the base group admits a definable ordered generating set, the accessible subgroup operation becomes definable in fixed-point logic with the group order operator (FP + ord). This is achieved by partially simulating the Schreier-Sims algorithm within FP + ord. As a corollary, we show that fixed-point logic with counting (FPC) can also define the operation when the base group is abelian. In particular, FPC can define the automorphism group of any graph with abelian colours--despite being unable to canonise such graphs.
Related
- On a finite group in which every maximal subgroup of order divisible by p containing the normalizer of some Sylow subgroup is nilpotent
- On a finite group in which every non-nilpotent maximal invariant subgroup of order divisible by p is normal
- On a finite group in which every non-supersolvable maximal subgroup is a TI-subgroup
- Generating the twist subgroup of the level $2$ mapping class group of a non-orientable closed surface
- On the Torsion Subgroup of the Néron--Severi Group
BibTeX
@misc{dahan2026subgroup,
title = {{Subgroup Accessibility in Group Order Logic}},
author = {Anatole Dahan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.00499},
eprint = {2609.00499},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.00499},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Subgroup Accessibility in Group Order Logic
AU - Anatole Dahan
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.00499
UR - https://arxiv.org/abs/2609.00499
AB - We investigate the expressive power of fixed-point logics (FP) and their extensions in defining generating sets for accessible subgroups of definable permutation groups. This operation, computable in polynomial time via the Schreier-Sims algorithm, plays a central role in the group-theoretic approach to Graph Isomorphism and Graph Canonisation. In particular, it underpins polynomial-time canonisation for bounded colour-class graphs--a class for which no natural logic capturing P is currently known. We first show that this operation cannot, in general, be expressed in any logic for P. This limitation arises from the fact that accessible subgroups need not admit symmetric generating sets of polynomial size. However, we prove that when the base group admits a definable ordered generating set, the accessible subgroup operation becomes definable in fixed-point logic with the group order operator (FP + ord). This is achieved by partially simulating the Schreier-Sims algorithm within FP + ord. As a corollary, we show that fixed-point logic with counting (FPC) can also define the operation when the base group is abelian. In particular, FPC can define the automorphism group of any graph with abelian colours--despite being unable to canonise such graphs.
ER -