Group Order Logic

Anatole Dahan · 2025

Read Group Order Logic by Anatole Dahan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-15359.txt.

Introduction

Anatole Dahan published a research paper in 2025 introducing a logic that can count the size of a group built from definable permutations. Logicians hunt for a logic that captures exactly the queries a computer can answer in reasonable time. Adding a rank operator got close but failed on a known hard case.

The new operator extends rank by counting the groups it forms. Checking formulas in the new logic stays fast. The counterexample that defeated the rank version becomes expressible here, because the logic can standardize structures with abelian color classes. The result makes the new logic a fresh candidate for capturing efficient computation.

Catalog record

CREATORAnatole Dahan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE176 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-15359

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Group Order Logic Thanks: Funded in part by UK Research and Innovation (UKRI) under the UK government’s Horizon Europe funding guarantee: grant number EP/X028259/1. Thanks: Funded in part by ANR - project QUID Thanks: Funded in part by ANR - project δ \delta ifference Anatole Dahan Abstract We introduce an extension of fixed-point logic ( 𝖥𝖯 {\mathsf{FP}} ) with a group-order operator ( 𝗈𝗋𝖽 \mathsf{ord} ), that computes the size of a group generated by a definable set of permutations. This operation is a generalization of the rank operator ( 𝗋𝗄 \mathsf{rk} ). We show that 𝖥𝖯 + 𝗈𝗋𝖽 {\mathsf{FP}}+\mathsf{ord} constitutes a new candidate logic for the class of polynomial-time computable queries ( 𝖯 {\mathsf{P}} ). As was the case for 𝖥𝖯 + 𝗋𝗄 {\mathsf{FP}}+\mathsf{rk} , the model-checking of 𝖥𝖯 + 𝗈𝗋𝖽 {\mathsf{FP}}+\mathsf{ord} formulae is polynomial-time computable. Moreover, the query separating 𝖥𝖯 + 𝗋𝗄 {\mathsf{FP}}+\mathsf{rk} from 𝖯 {\mathsf{P}} exhibited by Lichter in his recent breakthrough is definable in 𝖥𝖯 + 𝗈𝗋𝖽 {\mathsf{FP}}+\mathsf{ord} . Precisely, we show that 𝖥𝖯 + 𝗈𝗋𝖽 {\mathsf{FP}}+\mathsf{ord} canonizes structures with Abelian colors, a class of structures which contains Lichter’s counter-example. This proof involves expressing a fragment of the group-theoretic approach to graph canonization in the logic 𝖥𝖯 + 𝗈𝗋𝖽 {\mathsf{FP}}+\mathsf{ord} . I Introduction The quest to identify a logic that precisely characterizes the class of problems solvable in polynomial time ( {\mathsf{P}} ) is a central challenge in descriptive complexity. This question can be traced back to [ 1 ] , and its modern formulation was stated by Gurevich [ 2 ] . While fixed-point logic ( {\mathsf{FP}} ) captures {\mathsf{P}} on ordered structures, no logic is currently known to capture {\mathsf{P}} in the general case. {\mathsf{FP}} and its natural extensions, such as fixed-point logic with counting ( \mathsf{FPC} ), fail to capture {\mathsf{P}} [ 3 ] . This limitation of \mathsf{FPC} was demonstrated using the \mathsf{CFI} -construction, a class of structures encoding the satisfiability of systems of equations over the finite field \mathbb{F}_{2} [ 3 ] . To address these limitations, extensions of {\mathsf{FP}} incorporating linear-algebraic operations, such as the rank operator ( \mathsf{rk} ), have been proposed [ 4 , 5 , 6 , 7 ] . However, even {\mathsf{FP}}+\mathsf{rk} falls short of capturing {\mathsf{P}} , as recently shown by Lichter [ 8 ] through a generalized class of \mathsf{CFI} -structures. On the other hand, a lot of work has been devoted to partial capture results, showing that on restricted classes of structures, extensions of {\mathsf{FP}} are able to define all {\mathsf{P}} queries. For instance, Grohe showed that \mathsf{FPC} captures {\mathsf{P}} on any class of structures which excludes a minor [ 9 ] . Those results usually rely on the definition within the logic at hand of a canonization of the structures under consideration. Indeed, for any logic extending {\mathsf{FP}} , the Immerman-Vardi theorem implies that the definability of a canonization on a class of structures yields the capture of {\mathsf{P}} on that class. This motivates the study of canonization algorithms, and their definability in candidate logics for {\mathsf{P}} . Parallel to this investigation, significant progress has been made in the development of efficient algorithms for graph isomorphism and canonization through a group-theoretic approach. This line of research has yielded polynomial-time isomorphism and canonization algorithms for various classes of structures [ 10 , 11 , 12 ] , as well as Babai’s recent breakthrough that general graph isomorphism is solvable in quasi-polynomial time [ 13 ] . Notably, an early result in this area demonstrates the polynomial-time canonization of \mathsf{CFI} -structures. This result generalizes seamlessly to the broader classes of \mathsf{CFI} -constructions used in [ 7 ] , or even in [ 8 ] to separate {\mathsf{FP}}+\mathsf{rk} from {\mathsf{P}} . These findings underscore the potential of integrating group-theoretic operators into {\mathsf{FP}} to extend its expressive power. The most fundamental polynomial-time permutation group algorithm is probably Schreier-Sims algorithm [ 14 , 15 ] , which enables, given a set of permutations, to compute the order, and recognize elements of the group generated by that set. However, this procedure relies on stabilizing one by one the elements of the domain on which the permutations act. This process thus depends on an ordering of the domain of the permutation group at hand, and cannot be defined in an isomorphism-invariant way, while its output is isomorphism-invariant. This situation is quite similar to the one which motivated the introduction of the \mathsf{rk} operator: Gaussian elimination is inherently dependent on an ordering of the rows and columns of the matrix at hand, yet the rank of the matrix is not. Note that, the fact that {\mathsf{FP}}+\mathsf{rk} is strictly more expressive than \mathsf{FPC} implies that \mathsf{FPC} indeed cannot define Gaussian elimination, nor can it define the rank of a matrix by any other means. In this article, we introduce a novel group-theoretic operator, \mathsf{ord} , which computes the order of a group generated by a definable set of permutations. Because the Schreier-Sims algorithm enables the computation of this operation in polynomial-time, whether a structure satisfies a formula in {\mathsf{FP}}+\mathsf{ord} can be decided in polynomial-time (in the size of the structure). Thus, like \mathsf{rk} , the \mathsf{ord} operator defines the isomorphism-invariant result of a polynomial-time algorithm whose computation inherently depends on an ordering of the structure at hand. The \mathsf{ord} operator fills an interesting space within the algebraic extensions of fixed-point logics that have been studied. In [ 16 ] , the authors consider various solvability quantifiers — expressing the satisfiability of definable systems of equations over different algebraic structures, as abelian groups, fields, or commutative rings. In this work, the authors suggest a new permutation group membership (GM) quantifier, that subsumes all the quantifiers considered in this article. The \mathsf{ord} operator defines this quantifier. Actually, the \mathsf{ord} operator can be thought of as being to the GM quantifier what the \mathsf{rk} operator is to the field solvability quantifier. This should be contrasted with the apparent absence of such a matrix rank operator in the context of rings. Even with this operator available, simulating group-theoretic algorithms within {\mathsf{FP}}+\mathsf{ord} presents significant challenges due to the reliance of those algorithms on an implicit ordering of the domain. This difficulty is particularly pronounced in graph canonization. In this context, the group-theoretic approach consists in the computation of a canonical labeling coset. A labeling coset is a set of permutations of the domain of a structure which behaves almost like a group. Building a canonical labeling coset rather than a mere encoding of the canonical structure enables exploiting the structure of underlying permutation groups, but depends on the existence of an ordering of the domain. Indeed, in the ordered setting, a labeling is a reordering, and thus a permutation; while in the unordered setting, it is a bijection from the domain to an initial segment of the integers, and those bijections cannot be composed. Schweitzer et al. [ 17 ] provide such a definition of labeling cosets that accounts for the distinct nature of the structure’s domain and its canonical numerical representation. However, their contributions remain algorithmic and do not provide an isomorphism-invariant representation of labeling cosets. Our main result is that {\mathsf{FP}}+\mathsf{ord} strictly extends the expressive power of {\mathsf{FP}}+\mathsf{rk} . Precisely, we show that the

Read the complete text