For a permutation group G on a set X, a mixed identity is an expression of the form w(x_1,...,x_n,g_1,...,g_m)=1, where w is a word in the language of groups with constants g_1,...,g_m from G and free variables x_1,...,x_n. We say that the mixed identity holds in G if substitution of arbitrary elements of G for the free variables yields a true statement. The mixed identity is singular if deletion of all constants yields a true statement in the free group: for example, xgx^{-1}=1 (where x is a variable and g a constant) is singular. We consider the question which non-singular mixed identities hold in a given group G. The group G is oligomorphic if it acts with finitely many orbits on X^n, for all n. Based on several examples, Bodirsky, Schneider, and Thom have conjectured that in oligomorphic groups only singular identities can hold. We confirm this conjecture for all oligomorphic G without algebraicity, i.e. with the property that for any tuple t of elements of X, the stabilizer of t in G does not stabilize any element outside t. In fact, we obtain this result under even more general conditions satisfied e.g. by the general linear group of any infinite vector space over a finite field. This is joint work with Paolo Marimon (Oxford).
Mixed identities in oligomorphic groups Sponsored by the Meyer Fund
We study constraint satisfaction problems (CSPs) where the constraint languages are defined by finite automata, giving rise to automata-based CSPs. The key notion is the concept of Automatic Constraint Satisfaction Problem ($\AutCSP$) where constraint languages and instances are specified by finite automata. The $\AutCSP$ captures infinite yet finitely describable sets of relations, enabling concise representations of complex constraints. Studying the complexity of the $\AutCSP$s illustrates the interplay between classical CSPs, automata, and logic, sharpening the boundary between tractable and intractable constraints. We show that checking whether an operation is a polymorphism of such a language can be done in polynomial time. Building on this, we establish several complexity classification results for the $\AutCSP$. In particular, we prove that Schaefer’s Dichotomy Theorem extends to the $\AutCSP$ over the Boolean domain, and we provide algorithms that decide tractability of some classes of $\AutCSP$s over arbitrary finite domains via automatic polymorphisms. An important part of our work is that our polynomial-time algorithms run on $\AutCSP$ instances that can be exponentially more succinct than their standard CSP counterparts.
Automatic constraint satisfaction problem Sponsored by the Meyer Fund
Mixed identities in oligomorphic groups