Arity Hierarchies for Quantifiers Closed Under Partial Polymorphisms

Dawar, Anuj; Hella, Lauri; Pago, Benedikt

doi:10.4230/LIPIcs.CSL.2026.9

Arity Hierarchies for Quantifiers Closed Under Partial Polymorphisms

Anuj Dawar

Department of Computer Science and Technology, University of Cambridge, UK Lauri Hella

Faculty of Information Technology and Communication Sciences, Tampere University, Finland Benedikt Pago

Department of Computer Science and Technology, University of Cambridge, UK

Abstract

We investigate the expressive power of generalized quantifiers closed under partial polymorphism conditions motivated by the study of constraint satisfaction problems. We answer a number of questions arising from the work of Dawar and Hella (CSL 2024) where such quantifiers were introduced. For quantifiers closed under partial near-unanimity polymorphisms, we establish hierarchy results clarifying the interplay between the arity of the polymorphisms and of the quantifiers: The expressive power of $(\ell+1)$ -ary quantifiers closed under $\ell$ -ary partial near-unanimity polymorphisms is strictly between the class of all quantifiers of arity $\ell-1$ and $\ell$ . We also establish an infinite hierarchy based on the arity of quantifiers with a fixed arity of partial near-unanimity polymorphisms. Finally, we prove inexpressiveness results for quantifiers with a partial Maltsev polymorphism. The separation results are proved using novel algebraic constructions in the style of Cai-Fürer-Immerman and the quantifier pebble games of Dawar and Hella (2024).

Keywords and phrases:

finite model theory, constraint satisfaction problems, generalized quantifiers

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Finite Model Theory

Related Version:

Full Version: https://arxiv.org/abs/2511.11326 [11]

Acknowledgements:

We thank Victor Lagerkvist for pointers to the literature on the use of partial polymorphisms in CSP algorithms.

Funding:

Research funded in part by UK Research and Innovation (UKRI) under the UK government’s Horizon Europe funding guarantee: grant number EP/X028259/1.

DOI:

10.4230/LIPIcs.CSL.2026.9

Event:

34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Editors:

Stefano Guerrini and Barbara König

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The study of generalized quantifiers, also known as Lindström quantifiers [13], has played a major role in the development of finite model theory. This theory is concerned with the expressive power of logics over finite structures. When any particular class $\mathcal{K}$ of structures is not definable in a logic $L$ , we can adjoin to $L$ a Lindström quantifier $\mathcal{Q}_{\mathcal{K}}$ , which serves as an oracle for querying membership in $\mathcal{K}$ . Extending $L$ with this quantifier yields, in a precise sense, the minimal extension of $L$ that can also express $\mathcal{K}$ . Thus, the investigation of the structure and interdefinability of quantifiers is the core of finite model theory.

Results about inexpressibility, commonly referred to as lower bound results for logic, are often established by means of exhibiting winning strategies for model-comparison games. Some of the most striking such results in finite model theory have come from model-comparison games developed for Lindström quantifiers. In particular, Hella’s bijection game [15] was introduced to establish the arity hierarchy for generalized quantifiers. This game has since been widely used to establish many inexpressibility results in descriptive complexity and beyond. Hella’s proof that there is a strict hierarchy of expressive power obtained by classifying quantifiers according to their arity has as a consequence that meaningful logics in descriptive complexity (such as those closed under first-order reductions) should include quantifiers of arbitrary arities. Including all quantifiers clearly leads to logics that are far too rich. This leads us to study extensions of first-order logic with restricted families of quantifiers, but of unbounded arity.

A natural restriction is to require closure conditions on the classes of structures $\mathcal{K}$ whose Lindström quantifiers $\mathcal{Q}_{\mathcal{K}}$ we include in the logic. By default, such classes $\mathcal{K}$ are closed under isomorphism because logics never distinguish between isomorphic structures. Interestingly, by imposing stricter closure conditions, one can often obtain nicely behaved logics that admit a useful game characterization while still being rich in expressive power (i.e. stronger than first-order logic with counting quantifiers). One such example is first-order logic augmented by all linear-algebraic quantifiers [9]. Its expressive power is characterized by the invertible map game, which was used by Lichter [21] in a highly sophisticated lower bound proof. The classes $\mathcal{K}$ defining linear-algebraic quantifiers are closed under an equivalence relation coarser than isomorphism, which is based on similarity of adjacency matrices over all finite fields [8]. More generally we can ask: For which closure conditions on classes $\mathcal{K}$ do the Lindström quantifiers $\mathcal{Q}_{\mathcal{K}}$ give rise to logics that are both powerful and analyzable via a natural model-comparison game?

The present paper should be seen as a contribution to this research programme. The closure condition we are concerned with here is closure under partial polymorphisms, which was first studied by Dawar and Hella in 2024 [10]. An $\ell$ -ary polymorphism from a structure $\mathbf{A}$ to $\mathbf{B}$ is a homomorphism from the $\ell$ -th power of $\mathbf{A}$ to $\mathbf{B}$ . The interest in the notion comes from the theory of constraint satisfaction problems (CSP). For a fixed finite structure $\mathbf{B}$ , called the template, $\text{CSP}(\mathbf{B})$ denotes the class of structures $\mathbf{A}$ that map homomorphically to $\mathbf{B}$ . The algebraic approach to CSP relates the computational complexity of $\text{CSP}(\mathbf{B})$ to the algebra of polymorphisms of $\mathbf{B}$ (that is, polymorphisms from $\mathbf{B}$ to itself) and more particularly to the equational theory of that algebra (see e.g. [3]). The success of this programme culminated in the celebrated dichotomy theorem for finite-domain CSPs of Bulatov and Zhuk [4, 23]. Natural examples of quantifiers $\mathcal{Q}_{\mathcal{K}}$ closed under partial polymorphisms are thus CSP quantifiers, that is, $\mathcal{K}=\text{CSP}(\mathbf{B})$ for a template structure $\mathbf{B}$ that also has the respective (partial) polymorphism. Such CSP quantifiers were first introduced by Hella [16], where a strict hierarchy of expressive power in terms of the size of $\mathbf{B}$ was demonstrated. This size hierarchy is quite different from the arity hierarchy that we establish here. Moreover, it should be stressed that families of quantifiers closed under partial polymorphisms are a more general concept and contain more than just CSP quantifiers.

Our main results are about the interaction of partial polymorphism conditions with restrictions on the arity of quantifiers. The conditions require that the class of structures defining a quantifier is closed under partial functions satisfying certain equational conditions. The conditions we are particularly interested in (already introduced in prior work [10]) are partial near-unanimity polymorphisms and partial Maltsev polymorphisms. Their total counterparts play a key role in the classification of tractable CSP, since templates with these polymorphisms give rise to CSP with relatively simple polynomial time algorithms [2, 5]. The corresponding partial polymorphisms, which we use here, are significant for another reason: For NP-complete CSP, they essentially govern the fine-grained exponential complexity under the strong exponential-time hypothesis, and they have applications in parameterized complexity as well (see e.g. [17, 18, 19]).

Previous work [10] developed games for logics with quantifiers closed under partial polymorphisms and used these to establish that the problem of solving systems of equations over the Boolean field is not definable in the extension of infinitary logic with all quantifiers closed under partial near-unanimity polymorphisms.

In the present paper we answer a number of natural questions arising from this previous work concerning arity hierarchies within the class of quantifiers closed under partial near-unanimity polymorphisms, and also establish the first expressivity bounds for quantifiers closed under partial Maltsev polymorphisms. To be specific, we establish in Section 3 an arity reduction showing that any $r$ -ary quantifier $Q$ which is closed under a partial near-unanimity polymorphism of arity $\ell\leq r$ can be defined using quantifiers of arity at most $\lceil\frac{\ell-1}{\ell}\cdot r\rceil$ . On the other hand, our main results in Section 4 show that the arity of such quantifiers does not collapse, and they exhibit in fact a strict infinite hierarchy of expressive power. First, we prove that quantifiers of arity $\ell+1$ with a partial near-unanimity polymorphism of arity $\ell$ are, in terms of expressive power, strictly between all quantifiers of arity $\ell-1$ and all quantifiers of arity $\ell$ (Corollary 17). Secondly, we establish in Theorem 18 that for every fixed arity of polymorphisms, we can always gain in expressive power by increasing the arity of quantifiers. The results can be seen as a refinement of the arity hierarchy of Hella [15], and the separation results require novel constructions in the style of Cai-Fürer-Immerman [6] (called CFI-like henceforth). In Section 5 we move on to study a more powerful type of quantifiers, which cannot be fooled by CFI-like constructions, namely those with a partial Maltsev polymorphism. Also for these, we obtain a strict arity hierarchy (Theorem 36). Moreover, we establish a first lower bound: When both the arity of the quantifiers as well as the number of variables are limited to $k$ , Maltsev-closed quantifiers are strictly weaker than general ones (Theorem 37). This proof requires playing the Maltsev-closed quantifier pebble game on another original algebraic construction. It remains an intriguing open problem to prove lower bounds for first-order logic with Maltsev-closed quantifiers of arity $k$ , but an unbounded number of variables. We believe that finding a suitable hard example would also inspire progress on other open problems, as it would have to be radically different from the CFI-like constructions typically used in many known lower bound results.

2 Preliminaries

We denote structures by boldface letters $\mathbf{A},\mathbf{B},\ldots$ , and their universes by the corresponding Roman letters $A,B,\ldots$ . All structures we consider in the paper are finite and relational. Thus, we assume without further mention that the universe $A$ of each structure $\mathbf{A}$ is finite and the vocabulary of $\mathbf{A}$ is a finite set of relation symbols. Let $\mathbf{A}$ and $\mathbf{B}$ be $\tau$ -structures for a vocabulary $\tau$ . A function $f\colon C\to D$ is a partial isomorphism from $\mathbf{A}$ to $\mathbf{B}$ if $C\subseteq A$ , $D\subseteq B$ and $f$ is an isomorphism from the substructure of $\mathbf{A}$ induced by $C$ to the substructure of $\mathbf{B}$ induced by $D$ .

Let $\mathbf{A}$ and $\mathbf{B}$ be $\tau$ -structures. We write $\mathbf{A}\leq\mathbf{B}$ if $A=B$ and $R^{\mathbf{A}}\subseteq R^{\mathbf{B}}$ for all $R\in\tau$ . The union $\mathbf{A}\cup\mathbf{B}$ of $\mathbf{A}$ and $\mathbf{B}$ is the $\tau$ -structure with universe $A\cup B$ and relations $R^{\mathbf{A}\cup\mathbf{B}}\coloneqq R^{\mathbf{A}}\cup R^{\mathbf{B}}$ for each $R\in\tau$ .

We denote first-order logic by $\mathrm{FO}$ , and the infinitary logic with $k$ variables by $\mathcal{L}^{k}$ . Furthermore, we write $\mathcal{L}\coloneqq\bigcup_{k\in\mathbb{N}}\mathcal{L}^{k}$ . We refer to [12] and [20] for precise definitions of these logics. Given a logic $L$ and two $\tau$ -structures $\mathbf{A}$ and $\mathbf{B}$ , we write $\mathbf{A}\equiv_{L}\mathbf{B}$ if $\mathbf{A}$ and $\mathbf{B}$ satisfy exactly the same $L$ -sentences of vocabulary $\tau$ . For any positive integer $n$ , we denote the set $\{1,\ldots,n\}$ by $[n]$ .

Generalized quantifiers

Let $\tau=\{R_{1},\ldots,R_{m}\}$ be a vocabulary and let $\mathcal{K}$ be a class of $\tau$ -structures that is closed under isomorphisms. The extension $L(Q_{\mathcal{K}})$ of a logic $L$ by the generalized quantifier $Q_{\mathcal{K}}$ (also called Lindström quantifier) is obtained by adding the following formula formation rule to the syntax of $L$ :

For any vocabulary $\sigma$ , if $\Psi=(\psi_{1},\ldots,\psi_{m})$ is a tuple of $\sigma$ -formulas, and $\bar{y}_{1},\ldots,\bar{y}_{m}$ are tuples of variables such that $|\bar{y}_{i}|=\operatorname{ar}(R_{i})$ for $i\in[m]$ , then $Q_{\mathcal{K}}\bar{y}_{1},\ldots,\bar{y}_{m}\Psi$ is a $\sigma$ -formula. A variable is free in this formula if, for some $i\in[m]$ , it is free in $\psi_{i}$ , but not in $\bar{y}_{i}$ .

The sequence $\Psi=(\psi_{1},\ldots,\psi_{m})$ of $\sigma$ -formulas defines an interpretation of a $\tau$ -structure in any $\sigma$ -structure $\mathbf{A}$ with an assignment $\alpha$ that interprets all free variables of $Q_{\mathcal{K}}\bar{y}_{1},\ldots,\bar{y}_{m}\Psi$ : we define $\Psi(\mathbf{A},\alpha)\coloneqq(A,\psi_{1}^{\mathbf{A},\alpha},\ldots,\psi_{m% }^{\mathbf{A},\alpha})$ , where $\psi_{i}^{\mathbf{A},\alpha}\coloneqq\{\bar{b}\in A^{\operatorname{ar}(R_{i})}% \mid(\mathbf{A},\alpha[\bar{b}/\bar{y}_{i}])\models\psi_{i}\}$ for $i\in[m]$ . The semantics of the formula $Q_{\mathcal{K}}\bar{y}_{1},\ldots,\bar{y}_{m}\Psi$ can now be defined as follows:

Let $\mathbf{A}$ be a $\sigma$ -structure and $\alpha$ an assignment on $\mathbf{A}$ that interprets all free variables of $Q_{\mathcal{K}}\bar{y}_{1},\ldots,\bar{y}_{m}\Psi$ . Then $(\mathbf{A},\alpha)\models Q_{\mathcal{K}}\bar{y}_{1},\ldots,\bar{y}_{m}\Psi$ if, and only if, $\Psi(\mathbf{A},\alpha)\in\mathcal{K}$ .

The extension $L(\mathcal{Q})$ of a logic $L$ by a collection $\mathcal{Q}$ of quantifiers is defined in the natural way by adding the corresponding formula formation and semantic rules for each quantifier $Q_{\mathcal{K}}$ in $\mathcal{Q}$ . The arity of a quantifier $Q_{\mathcal{K}}$ is the maximum arity of relations in the vocabulary of the class $\mathcal{K}$ . For each $r\geq 1$ , we denote the collection of all quantifiers of arity at most $r$ by $\mathcal{Q}_{r}$ .

Bijective pebble games

We apply the bijective pebble game of Hella [15] in proving our arity hierarchy results in Section 4. Let $r\leq k$ be positive integers, and $\mathbf{A}$ and $\mathbf{B}$ be structures.

Definition 1.

The $k, r$ -bijection game $\mathrm{BP}^{k}_{r}(\mathbf{A},\mathbf{B})$ is played between two players, Duplicator and Spoiler. Positions of the game are pairs $(\alpha,\beta)$ , where $\alpha$ and $\beta$ are assignments on $\mathbf{A}$ and $\mathbf{B}$ , respectively, such that $\mathrm{dom}(\alpha)=\mathrm{dom}(\beta)\subseteq X\coloneqq\{x_{1},\ldots,x_{% k}\}$ . The initial position is $(\emptyset,\emptyset)$ . Let $(\alpha,\beta)$ be the position after some round of the game. The next round consists of the following steps:

(1)

Duplicator chooses a bijection $f\colon A\to B$ . If $|A|\not=|B|$ , then Spoiler wins the play.
(2)

Spoiler chooses an $r$ -tuple $\bar{y}$ of distinct variables in $X$ and an $r$ -tuple $\bar{a}\in A^{r}$ .
(3)

The next position is $(\alpha^{\prime},\beta^{\prime})$ , where $\alpha^{\prime}\coloneqq\alpha[\bar{a}/\bar{y}]$ and $\beta^{\prime}\coloneqq\beta[f(\bar{a})/\bar{y}]$ . If $\alpha^{\prime}\mapsto\beta^{\prime}$ is not a partial isomorphism $\mathbf{A}\to\mathbf{B}$ , then Spoiler wins the play.

Duplicator wins the play if Spoiler does not win it in a finite number of rounds.

The $k, r$ -bijection game characterizes equivalence with respect to the infinitary $k$ -variable logic with all $r$ -ary quantifiers.

Proposition 2 ([15]).

Let $k\geq r$ be positive integers. Then Duplicator has a winning strategy in $\mathrm{BP}^{k}_{r}(\mathbf{A},\mathbf{B})$ if, and only if, $\mathbf{A}\equiv_{\mathcal{L}^{k}(\mathcal{Q}_{r})}\mathbf{B}$ .

We say that a sentence $\psi$ of some logic separates two disjoint classes $\mathcal{K}$ and $\mathcal{K}^{\prime}$ of structures if every structure in $\mathcal{K}$ satisfies $\psi$ , but no structure in $\mathcal{K}^{\prime}$ satisfies $\psi$ .

Corollary 3.

Fix a positive integer $r$ . Let $\mathcal{K}$ and $\mathcal{K}^{\prime}$ be two disjoint classes of structures. If for every $k\geq r$ , there exist $\mathbf{A}\in\mathcal{K}$ and $\mathbf{B}\in\mathcal{K}^{\prime}$ such that Duplicator has a winning strategy in $\mathrm{BP}^{k}_{r}(\mathbf{A},\mathbf{B})$ , then no sentence in $\mathcal{L}(\mathcal{Q}_{r})$ separates $\mathcal{K}$ from $\mathcal{K}^{\prime}$ .

Partial polymorphisms

We go briefly through the basic notions related to families of partial polymorphisms. For a more detailed treatment and motivation, we refer to [10], where closure of generalized quantifiers with respect to such families was first considered.

Let $p\colon A^{\ell}\to A$ be a partial function. Then for any $r\geq 1$ , $p$ induces a partial function $\hat{p}\colon(A^{r})^{\ell}\to A^{r}$ defined by applying $p$ “column wise”: if $\bar{a}_{i}=(a_{i1},\ldots,a_{ir})\in A^{r}$ for $i\in[\ell]$ , then $\hat{p}(\bar{a}_{1},\ldots,\bar{a}_{\ell})\coloneqq(p(a_{11},\ldots,a_{\ell 1}% ),\ldots,p(a_{1r},\ldots,a_{\ell r}))$ . Naturally $\hat{p}(\bar{a}_{1},\ldots,\bar{a}_{\ell})$ is undefined if, and only if, $p(a_{1j},\ldots,a_{\ell j})$ is undefined for at least one $j\in[r]$ . Sometimes we also view the tuples $\bar{a}_{1},\dots,\bar{a}_{\ell}$ as the rows of an $\ell\times r$ -matrix $M$ and write $\hat{p}(M)$ for $\hat{p}(\bar{a}_{1},\ldots,\bar{a}_{\ell})$ . Given a relation $R\subseteq A^{r}$ , we write $p(R):=\{\hat{p}(\bar{a}_{1},\ldots,\bar{a}_{\ell})\mid\bar{a}_{1},\ldots,\bar{% a}_{\ell}\in R\}$ . Furthermore, if $\mathbf{A}$ is a $\tau$ -structure we denote by $p(\mathbf{A})$ the $\tau$ -structure with the same universe and relations $p(R^{\mathbf{A}})$ , $R\in\tau$ .

We say that a partial function $p\colon A^{\ell}\to A$ is a partial polymorphism of $\mathbf{A}$ if $p(\mathbf{A})\leq\mathbf{A}$ . A family $\mathcal{P}$ of $\ell$ -ary partial functions consists of a partial function $p_{A}\colon A^{\ell}\to A$ for every finite set $A$ . The family respects bijections if $f(p_{A}(a_{1},\ldots,a_{\ell}))\simeq p_{B}(f(a_{1}),\ldots,f(a_{\ell}))$ whenever $f\colon A\to B$ is a bijection. Here $s\simeq t$ means that either $s=t$ , or both $s$ and $t$ are undefined.

Let $\mathcal{P}$ be a family of partial functions that respects bijections, and let $Q_{\mathcal{K}}$ be a quantifier for a class $\mathcal{K}$ of $\tau$ -structures. We say that $Q_{\mathcal{K}}$ is $\mathcal{P}$ -closed if for every $\mathbf{B}\in\mathcal{K}$ and every $\mathbf{A}\leq\mathbf{B}\cup p_{B}(\mathbf{B})$ , we also have $\mathbf{A}\in\mathcal{K}$ . We denote the collection of all $\mathcal{P}$ -closed quantifiers by $\mathcal{Q}^{\mathcal{P}}$ . It follows immediately from the definition that all $\mathcal{P}$ -closed quantifiers $Q_{\mathcal{K}}$ are downwards monotone: If $\mathbf{B}\in\mathcal{K}$ and $\mathbf{A}\leq\mathbf{B}$ , then $\mathbf{A}\in\mathcal{K}$ .

The most interesting families of partial functions are based on equations on the components of the input tuple. Two examples of such families were studied in [10]:

Example 4.

(a)

The Maltsev family $\mathcal{M}$ consists of functions $m_{A}\colon A^{3}\to A$ such that $m_{A}(a,a,b)=m_{A}(b,a,a)=b$ and $m_{A}(a,b,c)$ is undefined if $a\not=b$ and $b\not=c$ .
(b)

The family $\mathcal{N}^{\ell}$ of $\ell$ -ary partial near-unanimity functions consists of functions $n^{\ell}_{A}\colon A^{\ell}\to A$ defined as follows: $n^{\ell}_{A}(a_{1},\ldots,a_{\ell})=a$ if at least $\ell-1$ of the inputs $a_{i}$ are equal to $a$ ; else, $n^{\ell}_{A}(a_{1},\ldots,a_{\ell})$ is undefined.

Note that the definition of $n^{\ell}_{A}(a_{1},\dots,a_{\ell})$ is actually independent of the set $A$ . Thus, we omit the subscript $A$ and write simply $n^{\ell}$ instead of $n^{\ell}_{A}$ .

It is straightforward to show that $n^{\ell}$ is a partial polymorphism of any structure with at most $\ell-1$ -ary relations:

Lemma 5 ([10, Lemma 9]).

Let $\mathbf{A}$ be a $\tau$ -structure such that $\operatorname{ar}(R)<\ell$ for all $R\in\tau$ . Then $n^{\ell}$ is a partial polymorphism of $\mathbf{A}$ .

CSP quantifiers

Let $\mathbf{A}$ and $\mathbf{B}$ be $\tau$ -structures. A function $h\colon A\to B$ is a homomorphism from $\mathbf{A}$ to $\mathbf{B}$ if for all $R\in\tau$ and $\bar{a}\in A^{\operatorname{ar}(R)}$ , $\bar{a}\in R^{\mathbf{A}}$ implies that $h(\bar{a})\in R^{\mathbf{B}}$ . We write $\mathbf{A}\to\mathbf{B}$ if there exists a homomorphism from $\mathbf{A}$ to $\mathbf{B}$ . For any fixed $\tau$ -structure $\mathbf{B}$ we denote the class $\{\mathbf{A}\mid\mathbf{A}\to\mathbf{B}\}$ by $\mathrm{CSP}(\mathbf{B})$ . The class $\mathrm{CSP}(\mathbf{B})$ is usually regarded as the (non-uniform) constraint satisfaction problem (CSP): Given an input structure $\mathbf{A}$ , decide whether there exists a homomorphism from $\mathbf{A}$ to $\mathbf{B}$ . Here $\mathbf{B}$ is the template of the CSP. It is a consequence of the results of Bulatov and Zhuk [4, 23] that, for any finite template $\mathbf{B}$ , the corresponding CSP is either decidable in polynomial time or NP-complete, and which of these is the case depends only on the polymorphisms of $\mathbf{B}$ . A generalized quantifier $Q_{\mathcal{K}}$ is a CSP quantifier if the defining class $\mathcal{K}$ is of the form $\mathrm{CSP}(\mathbf{B})$ for some template $\mathbf{B}$ . For CSP quantifiers, being closed under partial polymorphisms is a natural notion: If $\mathbf{B}$ is a structure which has a (total) polymorphism that satisfies an identity, this yields a natural partial polymorphism of the class of structures $\mathrm{CSP}(\mathbf{B})$ . Thus, quantifiers closed under this partial polymorphism are a generalization of CSP quantifiers based on a structure with the corresponding total polymorphism. The following collections of CSP quantifiers are of particular interest to us.

$\blacksquare$

For $r\geq 1$ , $\mathcal{Q}^{\text{CSP}}_{r}\subseteq\mathcal{Q}_{r}$ is the collection of all CSP quantifiers of arity at most $r$ .
$\blacksquare$

For $\ell\geq 3$ , $\mathcal{Q}^{\mathcal{N}_{\text{CSP}}^{\ell}}\subseteq\mathcal{Q}^{\mathcal{N}% ^{\ell}}$ is the collection of all $\mathcal{N}^{\ell}$ -closed CSP quantifiers.
$\blacksquare$

For $\ell\geq 3$ and $r\geq 1$ , $\mathcal{Q}^{\mathcal{N}_{\text{CSP}}^{\ell}}_{r}\coloneqq\mathcal{Q}^{% \mathcal{N}_{\text{CSP}}^{\ell}}\cap\mathcal{Q}_{r}$ .
$\blacksquare$

$\mathcal{Q}^{\mathcal{M}}$ is the collection of all quantifiers closed under the partial Maltsev polymorphism, and $\mathcal{Q}^{\mathcal{M}}_{r}\coloneqq\mathcal{Q}^{\mathcal{M}}\cap\mathcal{Q}% _{r}$ , for every $r\geq 1$ .

Dawar and Hella [10, Proposition 11] proved that if $p_{B}$ is a partial polymorphism of $\mathbf{B}$ , then $Q_{\mathrm{CSP}(\mathbf{B})}$ is $\mathcal{P}$ -closed, assuming that $\mathcal{P}$ is projective¹¹1See [10, Definition 6] for the definition of projective.. In particular, this holds for the family $\mathcal{N}_{\ell}$ for any $\ell\geq 3$ . We conclude this section by proving a converse of this result. A relational structure is a core if every homomorphism from it to itself is an automorphism. If a structure is not a core itself, it has a unique (up to isomorphism) substructure that is (see [14, Proposition 3.3]).

Lemma 6.

Let $\mathcal{P}$ be a family of partial functions. Assume that $\mathbf{B}$ is a core such that the corresponding CSP quantifier $Q_{\mathrm{CSP}(\mathbf{B})}$ is $\mathcal{P}$ -closed. Then $p_{B}$ is a partial polymorphism of $\mathbf{B}$ .

Proof.

We trivially have $\mathbf{B}\in\mathrm{CSP}(\mathbf{B})$ , and since $Q_{\mathrm{CSP}(\mathbf{B})}$ is $\mathcal{P}$ -closed, also $\mathbf{B}\cup p_{B}(\mathbf{B})\in\mathrm{CSP}(\mathbf{B})$ . So there is a homomorphism $h\colon\mathbf{B}\cup p_{B}(\mathbf{B})\to\mathbf{B}$ . Now $h$ maps $R^{\mathbf{B}}$ to itself for every relation $R$ in the vocabulary $\tau$ of $\mathbf{B}$ , and because $\mathbf{B}$ is a core, $h$ must be a permutation of $B$ . But then we must have $p_{B}(\mathbf{B})\leq\mathbf{B}$ because otherwise, for some $R\in\tau$ , $h$ would map a tuple in $R^{p_{B}(\mathbf{B})}\setminus R^{\mathbf{B}}$ to a tuple in $R^{\mathbf{B}}$ , which is not possible because $h$ induces a bijection between the tuples in $R^{\mathbf{B}}$ . $\hfill\blacktriangleleft$

Corollary 7.

Let $\mathbf{B}$ be a structure. The CSP quantifier $Q_{\mathrm{CSP}(\mathbf{B})}$ is in $\mathcal{Q}^{\mathcal{N}_{\text{CSP}}^{\ell}}$ if, and only if, $n^{\ell}$ is a partial polymorphism of the core of $\mathbf{B}$ .

Proof.

Note that $\mathrm{CSP}(\mathbf{B})=\mathrm{CSP}(\mathbf{B}^{\prime})$ for the core $\mathbf{B}^{\prime}$ of $\mathbf{B}$ . Thus, the implication from left to right follows from Lemma 6, and the implication from right to left follows from [10, Proposition 11]. $\hfill\blacktriangleleft$

3 Arity reductions

Our aim is to prove arity hierarchies for $\mathcal{N}^{\ell}$ -closed quantifiers. Dawar and Hella [10] introduced a model-comparison game for $\mathcal{L}^{k}(\mathcal{Q}^{\mathcal{N}^{\ell}})$ , and used it to prove that for any $\ell\geq 3$ there is an $\ell$ -ary CSP quantifier in $\mathcal{Q}^{\mathcal{N}^{\ell+1}}$ that is not definable in $\mathcal{L}(\mathcal{Q}^{\mathcal{N}^{\ell}})$ . However, they left open the question whether for every fixed $\ell$ , there is an arity hierarchy within the class of $\mathcal{N}^{\ell}$ -closed quantifiers. This question turns out to be nontrivial: In this section, we show that any $\mathcal{N}^{\ell}$ -closed quantifier of arity at least $\ell$ can be defined by a quantifier with strictly smaller arity. Moreover, the arity of some natural $\mathcal{N}^{\ell}$ -closed quantifiers can even be reduced all the way down to $2$ in this way. Omitted proofs in this and the following sections can be found in [11].

Example: Hypergraph colouring

For $m\geq r\geq 2$ let $H^{r}_{m}$ be the $r$ -uniform hypergraph of size $m$ , i.e., $H^{r}_{m}:=([m],R^{r}_{m})$ , where $R^{r}_{m}$ is the set of all tuples $(a_{1},\ldots,a_{r})\in[m]^{r}$ such that $a_{i}\not=a_{j}$ for all $i\not=j$ . Note that $H^{2}_{m}$ is just the complete graph $K_{m}$ on $m$ vertices. In [10] the authors proved that the CSP quantifier corresponding to the class $\mathrm{CSP}(H^{r}_{m})$ is $\mathcal{N}^{\ell}$ -closed for any $\ell\geq 3$ .

Thus, one might think that the quantifiers $Q_{\mathrm{CSP}(H^{r}_{m})}$ , for $m\geq r\geq 2$ , would form a natural arity hierarchy within $\mathcal{Q}^{\mathcal{N}^{\ell}}$ . However, this is not the case: Each $\mathrm{CSP}(H^{r}_{m})$ can be defined already by the binary quantifier $Q_{\mathrm{CSP}(K_{m})}$ :

Proposition 8.

There is an $\mathrm{FO}$ -definable reduction from $\mathrm{CSP}(H^{r}_{m})$ to $\mathrm{CSP}(K_{m})$ .

Proof sketch.

Given $\mathbf{A}$ in the vocabulary $\{R\}$ with $\operatorname{ar}(R)=r$ , let $\mathcal{G}(\mathbf{A})$ be the graph (possibly with self-loops) on vertex set $A$ with edges $\{(a_{i},a_{j})\mid(a_{1},\ldots,a_{r})\in R^{\mathbf{A}},i\not=j\}$ . Clearly $\mathcal{G}(\mathbf{A})$ is $\mathrm{FO}$ -definable in $\mathbf{A}$ . It can be verified that $\mathbf{A}\to H^{r}_{m}$ if, and only if, $\mathcal{G}(\mathbf{A})\to K_{m}$ . $\hfill\blacktriangleleft$

Arity reductions for $\mathcal{N}^{\ell}$ -closed quantifiers

We now show a general arity reduction result for $N^{\ell}$ -closed quantifiers. We start with the easier case of CSP quantifiers. Let $r\geq 1$ and let $R\subseteq B^{r}$ be an $r$ -ary relation. For $i,j\in[r]$ , $i\leq j$ , let $p_{\setminus[i,j]}$ be the projection function $B^{r}\to B^{r-(j-i+1)}$ that maps $(b_{1},\ldots,b_{r})$ to $(b_{1},\ldots,b_{i-1},b_{j+1},\ldots,b_{r})$ . Furthermore, let $R_{\setminus[i,j]}$ be the $r-(j-i+1)$ -ary relation that is the projection of $R$ to $[r]\setminus\{i,i+1,...,j\}$ , i.e., $R_{\setminus[i,j]}=\{p_{\setminus[i,j]}(\bar{b})\mid\bar{b}\in R\}$ .

Lemma 9.

Let $\ell\geq 3$ and $r\geq\ell$ , and let $(i_{1},j_{1}),(i_{2},j_{2}),...,(i_{\ell},j_{\ell})$ be a division of $[r]$ into $\ell$ intervals. Let $B$ be a finite set and $R\subseteq B^{r}$ . Assume that $n^{\ell}$ is a partial polymorphism of $(B,R)$ . Then $\bar{b}\in R$ if, and only if, $p_{\setminus[i_{n},j_{n}]}(\bar{b})\in R_{\setminus[i_{n},j_{n}]}$ for every $n\in[\ell]$ .

Proof.

Let $\bar{b}\in B^{r}$ . If $\bar{b}\in R$ , then $p_{\setminus[i_{n},j_{n}]}(\bar{b})\in R_{\setminus[i_{n},j_{n}]}$ by definition. For the other direction, assume that $p_{\setminus[i_{n},j_{n}]}(\bar{b})\in R_{\setminus[i_{n},j_{n}]}$ for every $n\in[\ell]$ . This means that there exist tuples $\bar{c}_{1},...,\bar{c}_{\ell}\in R$ such that $p_{\setminus[i_{n},j_{n}]}(\bar{c}_{n})=p_{\setminus[i_{n},j_{n}]}(\bar{b})$ for each $n\in[\ell]$ . Clearly then $\widehat{n^{\ell}}(\bar{c}_{1},\ldots,\bar{c}_{\ell})=\bar{b}$ , and since $n^{\ell}$ is a partial polymorphism of $(B,R)$ , it follows that $\bar{b}\in R$ . $\hfill\blacktriangleleft$

We use the following notation in the rest of this section. Let $\mathbf{C}$ be a $\tau$ -structure, where $\operatorname{ar}(R)\leq r$ for all $R\in\tau$ , and let $(i_{1},j_{1}),(i_{2},j_{2}),...,(i_{\ell},j_{\ell})$ be a division of $[r]$ into intervals. For each $R\in\tau$ and $n\in[\ell]$ , let

R^{\mathbf{C}}_{n}\coloneqq\begin{cases}R^{\mathbf{C}}_{\setminus[i_{n},j_{n}]% }&\text{if }j_{n}\leq\operatorname{ar}(R),\\ R^{\mathbf{C}}_{\setminus[i_{n},\operatorname{ar}(R)]}&\text{if }i_{n}\leq% \operatorname{ar}(R)<j_{n},\\ \emptyset&\text{if }\operatorname{ar}(R)<i_{n}.\end{cases}

Then we denote by $\mathbf{C}^{*}$ the structure $(C,(R^{\mathbf{C}}_{n})_{R\in\tau,n\in[\ell]})$ . Note that $\mathbf{C}^{*}$ is $\mathrm{FO}$ -definable in $\mathbf{C}$ .

Lemma 10.

Let $\ell,r$ and $(i_{1},j_{1}),(i_{2},j_{2}),...,(i_{\ell},j_{\ell})$ be as in Lemma 9, and let $\mathbf{A}$ and $\mathbf{B}$ be $\tau$ -structures, where $\operatorname{ar}(R)\leq r$ for all $R\in\tau$ . Assume that $n^{\ell}$ is a partial polymorphism of $\mathbf{B}$ . Then $\mathbf{A}\to\mathbf{B}$ if, and only if, $\mathbf{A}^{*}\to\mathbf{B}^{*}$ .

Proof.

Let $h:\mathbf{A}\to\mathbf{B}$ be a homomorphism, and let $\bar{a}\in R^{\mathbf{A}}_{n}$ for some $R\in\tau$ and $n\in[\ell]$ . Then there is a tuple $\bar{c}\in R^{\mathbf{A}}$ such that $\bar{a}=p_{\setminus[i_{n},j_{n}]}(\bar{c})$ . Since $h(\bar{c})\in R^{\mathbf{B}}$ , also $h(\bar{a})=p_{\setminus[i_{n},j_{n}]}(h(\bar{c}))\in R^{\mathbf{B}}_{n}$ . Hence, $h$ is a homomorphism from $\mathbf{A}^{*}$ to $\mathbf{B}^{*}$ .

Conversely, assume that $h$ is a homomorphism from $\mathbf{A}^{*}$ to $\mathbf{B}^{*}$ . Let $\bar{a}\in R^{\mathbf{A}}$ for some $R\in\tau$ . Then for every $n\in[\ell]$ , $p_{\setminus[i_{n},j_{n}]}(h(\bar{a}))=h(p_{\setminus[i_{n},j_{n}]}(\bar{a}))% \in R^{\mathbf{B}}_{n}$ . By Lemma 9, we have $h(\bar{a})\in R^{\mathbf{B}}$ . $\hfill\blacktriangleleft$

Corollary 11.

Let $r\geq\ell\geq 3$ . Every quantifier in $\mathcal{Q}_{r}^{\mathcal{N}_{\text{CSP}}^{\ell}}$ is $\mathrm{FO}$ -definable by a quantifier in $\mathcal{Q}^{\text{CSP}}_{\lceil\frac{\ell-1}{\ell}\cdot r\rceil}$ .

Proof.

Let $\mathbf{B}$ be a $\tau$ -structure such that $Q_{\mathrm{CSP}(\mathbf{B})}$ is a quantifier in $\mathcal{Q}_{r}^{\mathcal{N}_{\text{CSP}}^{\ell}}$ . W.l.o.g. we can assume that $\mathbf{B}$ is a core, and hence by Corollary 7, $n^{\ell}$ is a partial polymorphism of $\mathbf{B}$ . Consider now a division $(i_{1},j_{1}),(i_{2},j_{2}),...,(i_{\ell},j_{\ell})$ of $[r]$ into intervals such that the size of of each $[i_{n},j_{n}]$ is at least $\lfloor\frac{r}{\ell}\rfloor$ . Then the arity of each relation $R^{\mathbf{B}}_{n}$ of $\mathbf{B}^{*}$ is at most $r-\lfloor\frac{r}{\ell}\rfloor=\lceil\frac{\ell-1}{\ell}\cdot r\rceil$ . Thus, $Q_{\mathrm{CSP}(\mathbf{B}^{*})}\in\mathcal{Q}^{\text{CSP}}_{\lceil\frac{\ell-% 1}{\ell}\cdot r\rceil}$ .

By Lemma 10, for any $\tau$ -structure $\mathbf{A}$ we have $\mathbf{A}\in\mathrm{CSP}(\mathbf{B})$ if, and only if, $\mathbf{A}^{*}\in\mathrm{CSP}(\mathbf{B}^{*})$ . Thus, the mapping $\mathbf{A}\mapsto\mathbf{A}^{*}$ is an $\mathrm{FO}$ -definable reduction of $\mathrm{CSP}(\mathbf{B})$ to $\mathrm{CSP}(\mathbf{B}^{*})$ . $\hfill\blacktriangleleft$

It should be noted that $n^{\ell}$ is usually not a partial polymorphism of the structure $\mathbf{B}^{*}$ in Lemma 10. Otherwise we could iterate the arity reduction trick to obtain even lower arity quantifiers that define $\mathrm{CSP}(\mathbf{B})$ .

If we allow ourselves to use the infinitary logic $\mathcal{L}$ rather than just FO in the reductions, then the arity reduction works for any $\mathcal{N}^{\ell}$ -closed quantifier, not just CSPs. The general reduction consists in first closing the given structure $\mathbf{A}$ under $n^{\ell}$ (which is an $\mathcal{L}$ -definable fixed-point induction), and then applying to it the FO-definable operator ^∗ defined before Lemma 10. This yields the following arity reduction.

Lemma 12.

Let $r\geq\ell\geq 3$ . Let $\mathcal{K}$ be an $\mathcal{N}^{\ell}$ -closed class of $\tau$ -structures, where $\operatorname{ar}(R)\leq r$ for all $R\in\tau$ . Then there exists a vocabulary $\sigma$ with at most $\lceil\frac{\ell-1}{\ell}\cdot r\rceil$ -ary relations, a class $\mathcal{K}^{\prime}$ of $\sigma$ -structures, and an $\mathcal{L}$ -definable reduction $f$ that maps $\tau$ -structures to $\sigma$ -structures in such a way that $\mathbf{A}\in\mathcal{K}$ if, and only if, $f(\mathbf{A})\in\mathcal{K}^{\prime}$ .

Corollary 13.

Let $r\geq\ell\geq 3$ . Every quantifier in $\mathcal{Q}_{r}^{\mathcal{N}^{\ell}}$ is definable in $\mathcal{L}(\mathcal{Q}_{\lceil\frac{\ell-1}{\ell}\cdot r\rceil})$ .

Here and in Theorem 15 below, the expression $\lceil\frac{\ell-1}{\ell}\cdot r\rceil$ may equivalently be read as $r-i$ , for the $i$ such that $i\cdot\ell\leq r<(i+1)\cdot\ell$ . Note that the arity reduction result in Corollary 11 for CSP quantifiers is not a special case of Corollary 13, as the latter does not provide an $\mathrm{FO}$ -definable reduction. Moreover, in Corollary 11, the defining quantifier is again a CSP quantifier.

Summarizing our arity collapse results, we obtain the following picture. First, we note that if the arity $\ell$ of the partial near-unanimity function $n^{\ell}$ is greater than the arity of the relations, then being $\mathcal{N}^{\ell}$ -closed is not a restriction:

Theorem 14.

Let $\ell>r\geq 1$ , $\ell\geq 3$ . Then $\mathcal{L}(\mathcal{Q}^{\mathcal{N}^{\ell}}_{r})\equiv\mathcal{L}(\mathcal{Q}% _{r})$ and $\mathcal{L}(\mathcal{Q}^{\mathcal{N}_{\text{CSP}}^{\ell}}_{r})\equiv\mathcal{L% }(\mathcal{Q}^{\text{CSP}}_{r})$ .

Proof.

The first claim follows from [10, Lemma 9] and the argument for [10, Corollary 10]. The second claim follows from Corollary 7 and Lemma 5. $\hfill\blacktriangleleft$

Hence, only for $r\geq\ell$ , the situation is interesting. In this case, we have:

Theorem 15.

Let $r\geq\ell\geq 3$ . Then we have $\mathcal{L}(\mathcal{Q}_{\ell-1}^{\text{CSP}})\leq\mathcal{L}(\mathcal{Q}_{r}^% {\mathcal{N}_{\text{CSP}}^{\ell}})\leq\mathcal{L}(\mathcal{Q}^{\text{CSP}}_{% \lceil\frac{\ell-1}{\ell}\cdot r\rceil})$ and $\mathcal{L}(\mathcal{Q}_{\ell-1})\leq\mathcal{L}(\mathcal{Q}_{r}^{\mathcal{N}^% {\ell}})\leq\mathcal{L}(\mathcal{Q}_{\lceil\frac{\ell-1}{\ell}\cdot r\rceil})$ .

In particular, in the case $r=\ell$ we have $\mathcal{L}(\mathcal{Q}_{r}^{\mathcal{N}_{\text{CSP}}^{r}})\equiv\mathcal{L}(% \mathcal{Q}^{\text{CSP}}_{r-1})$ and $\mathcal{L}(\mathcal{Q}_{r}^{\mathcal{N}^{r}})\equiv\mathcal{L}(\mathcal{Q}_{r% -1})$ .

Proof.

The inclusions $\mathcal{L}(\mathcal{Q}_{r}^{\mathcal{N}_{\text{CSP}}^{\ell}})\leq\mathcal{L}(% \mathcal{Q}^{\text{CSP}}_{\lceil\frac{\ell-1}{\ell}\cdot r\rceil})$ and $\mathcal{L}(\mathcal{Q}_{r}^{\mathcal{N}^{\ell}})\leq\mathcal{L}(\mathcal{Q}_{% \lceil\frac{\ell-1}{\ell}\cdot r\rceil})$ follow from Corollaries 11 and 13. The inclusions $\mathcal{L}(\mathcal{Q}_{\ell-1}^{\text{CSP}})\leq\mathcal{L}(\mathcal{Q}_{r}^% {\mathcal{N}_{\text{CSP}}^{\ell}})$ and $\mathcal{L}(\mathcal{Q}_{\ell-1})\leq\mathcal{L}(\mathcal{Q}_{r}^{\mathcal{N}^% {\ell}})$ follow from Theorem 14, since clearly $\mathcal{L}(\mathcal{Q}_{\ell-1}^{\mathcal{N}_{\text{CSP}}^{\ell}})\leq% \mathcal{L}(\mathcal{Q}_{r}^{\mathcal{N}_{\text{CSP}}^{\ell}})$ and $\mathcal{L}(\mathcal{Q}_{\ell-1}^{\mathcal{N}^{\ell}})\leq\mathcal{L}(\mathcal% {Q}_{r}^{\mathcal{N}^{\ell}})$ . $\hfill\blacktriangleleft$

4 Arity hierarchies for partial near-unanimity quantifiers

Theorem 15 shows that restricting quantifiers of arity $r$ to those that are also $\mathcal{N}^{r}$ -closed has the same effect on expressive power as reducing the arity to $r-1$ , and does not really give rise to a new interesting logic. Thus, the natural question arises whether there are any combinations of polymorphism arities $\ell$ and quantifier arities $r$ for which the $\mathcal{N}^{\ell}$ -closed quantifiers yield a logic that is strictly different from any $\mathcal{L}(\mathcal{Q}_{r^{\prime}})$ . In other words, we would like to know if the inclusions in Theorem 15 are strict if $r\neq\ell$ . The following theorem establishes this already for the case $r=\ell+1$ :

Theorem 16.

Fix $\ell\geq 3$ . Then $\mathcal{L}(\mathcal{Q}_{\ell+1}^{\mathcal{N}_{\text{CSP}}^{\ell}})\not\leq% \mathcal{L}(\mathcal{Q}_{\ell-1})$ .

Corollary 17.

For every $\ell\geq 3$ , $\mathcal{L}(\mathcal{Q}_{\ell-1})\lneq\mathcal{L}(\mathcal{Q}_{\ell+1}^{% \mathcal{N}^{\ell}})\lneq\mathcal{L}(\mathcal{Q}_{\ell}).$

Proof.

The first inclusion follows with Theorem 15, and the fact that it is strict is a consequence of Theorem 16, which shows that already the fragment $\mathcal{L}(\mathcal{Q}_{\ell+1}^{\mathcal{N}_{\text{CSP}}^{\ell}})$ of $\mathcal{L}(\mathcal{Q}_{\ell+1}^{\mathcal{N}^{\ell}})$ is not contained in $\mathcal{L}(\mathcal{Q}_{\ell-1})$ . The second inclusion is a consequence of Theorem 15, and $\mathcal{L}(\mathcal{Q}_{\ell})\not\leq\mathcal{L}(\mathcal{Q}_{\ell+1}^{% \mathcal{N}^{\ell}})$ was shown in [10, Theorem 30]. $\hfill\blacktriangleleft$ A second natural question that we answer in this section is whether the polymorphism-closed quantifiers exhibit an arity hierarchy with respect to the arity of the quantifiers (keeping the arity of the polymorphism fixed): For the class of all generalized quantifiers, Hella [15] proved that $\mathcal{L}(\mathcal{Q}_{r})\lneq\mathcal{L}(\mathcal{Q}_{r+1})$ for all $r\in\mathbb{N}$ . The following result shows that for every fixed polymorphism-arity $\ell$ , one can always gain strictly more expressive power by sufficiently increasing the arity of the quantifiers.

Theorem 18.

Let $r\geq\ell\geq 3$ . Then $\mathcal{L}(\mathcal{Q}^{\mathcal{N}_{\text{CSP}}^{\ell}}_{q(r,\ell)})\nleq% \mathcal{L}(\mathcal{Q}_{r})$ , where $q(r,\ell)=(2r+1)(\lfloor\frac{2r+1}{\ell-1}\rfloor+2)$ .

Corollary 19.

Let $r\geq\ell\geq 3$ . Then there is an $r^{\prime}>r$ such that $\mathcal{L}(\mathcal{Q}^{\mathcal{N}_{\text{CSP}}^{\ell}}_{r})\lneq\mathcal{L}% (\mathcal{Q}^{\mathcal{N}_{\text{CSP}}^{\ell}}_{r^{\prime}})$ .

Note that the separation $\mathcal{L}(\mathcal{Q}_{\ell+1}^{\mathcal{N}_{\text{CSP}}^{\ell}})\not\leq% \mathcal{L}(\mathcal{Q}_{\ell-1})$ in Theorem 16 is tighter than the one that is implied by Theorem 18 for $r=\ell+1$ . So neither of the two results implies the other.

The proofs of Theorems 16 and 18 are structured similarly but employ different constructions. In both cases we construct a CSP template structure whose associated CSP quantifier can be used to distinguish certain CFI-like structures, which we view as the CSP instances. These instances are such that they cannot be distinguished in the logic $\mathcal{L}(\mathcal{Q}_{r})$ , for the respective value of $r$ that we have to beat in the theorems. The novelty in both constructions is that we enforce the template structure to be closed under the $\ell$ -ary partial near-unanimity function, so that the corresponding CSP quantifier is indeed in $\mathcal{Q}^{\mathcal{N}_{\text{CSP}}^{\ell}}$ .

The rest of the section is divided into three parts: First, construction of the respective templates needed for the proofs of the two theorems, then construction of the instances, and finally, we provide winning strategies for Duplicator in the bijective pebble game to prove indistinguishability of the instances in the respective logic $\mathcal{L}(\mathcal{Q}_{r})$ .

4.1 Construction of polymorphism-closed templates

The templates we construct have as relations the solution spaces of certain systems of linear equations. To make them closed under the partial near-unanimity function $n^{\ell}$ , we ensure that no collection of tuples in a relation satisfies the conditions for applicability of $n^{\ell}$ , except in cases where $n^{\ell}$ outputs a tuple that is already in the collection. Then $n^{\ell}$ is a partial polymorphism of the template.

Template structure for the proof Theorem 16

We start by developing the ideas to forbid the applicability of $n^{\ell}$ . We say that an $n\times m$ -matrix over a ring or field has the $n$ -near-unanimity property if in every column, all entries except possibly one (the minority entry), are equal. Throughout this section, arithmetic operations are always meant in the ring $\mathbb{Z}_{3}$ . Omitted/shortened proofs can be found in the full version [11].

Lemma 20.

Let $A\in\mathbb{Z}_{3}^{3\times 3}$ be a matrix satisfying:

1.

$A$ has the $3$ -near-unanimity property.
2.

$\sum_{j\in[3]}a_{1j}=\sum_{j\in[3]}a_{2j}=\sum_{j\in[3]}a_{3j}$ , that is, the row-sums are all equal.
3.

$\widehat{n^{3}}(A)$ is a triple that is not a row of $A$ .

Then $A\cdot(0,1,2)^{T}$ is a vector in $\mathbb{Z}_{3}^{3}$ with all three entries distinct.

Proof.

Assumption 3) entails that no two rows of $A$ are identical. Since no two rows of $A$ are equal, the row $A_{2-}$ differs from $A_{1-}$ in at least one position. They cannot differ in all positions because then, by the first property, $A_{3-}$ must be identical to either $A_{1-}$ or $A_{2-}$ , which cannot be the case. If $A_{1-}$ and $A_{2-}$ differ in only one position, then $\widehat{n^{3}}(A)\in\{A_{1-},A_{2-}\}$ , so this also contradicts assumption 3). Thus, $A_{1-}$ and $A_{2-}$ differ in exactly two positions. Assume first that $a_{11}\neq a_{21}$ and $a_{12}\neq a_{22}$ , but $a_{13}=a_{23}$ . Let $v_{1}=A_{1-}\cdot(0,1,2)^{T}$ and $v_{2}=A_{2-}\cdot(0,1,2)^{T}$ . Then $v_{2}-v_{1}=a_{22}-a_{12}\neq 0$ , so $v_{1}\neq v_{2}$ . The same argument works in case that $a_{11}\neq a_{21}$ and $a_{13}\neq a_{23}$ . In case that $a_{11}=a_{21}$ , $a_{12}\neq a_{22}$ , and $a_{13}\neq a_{23}$ , we have $v_{2}-v_{1}=a_{22}-a_{12}+2(a_{23}-a_{13})$ . By condition 2) and because $a_{11}=a_{21}$ , we have $a_{12}+a_{13}=a_{22}+a_{23}$ . So

v_{2}-v_{1}=a_{22}-a_{12}+2(a_{23}-a_{13})=a_{22}+a_{23}+a_{23}-(a_{12}+a_{13}% +a_{13})=a_{23}-a_{13}\neq 0.

Therefore, in all cases, $v_{1}\neq v_{2}$ . The same reasoning can be applied to any pair of rows, and thus also shows that $v_{3}=A_{3-}\cdot(0,1,2)^{T}\neq v_{1}$ , and $v_{3}\neq v_{2}$ . $\hfill\blacktriangleleft$

The lemma also generalizes to square matrices of larger dimensions because one can always find a $(3\times 3)$ -submatrix with the properties required by Lemma 20 in them.

Lemma 21.

Let $\ell\geq 3$ and let $A\in\mathbb{Z}_{3}^{\ell\times\ell}$ be a matrix satisfying:

1.

$A$ has the $\ell$ -near-unanimity property.
2.

The row-sums of $A$ are all equal.
3.

$\widehat{n^{\ell}}(A)$ is not a row of $A$ .

Then $A\cdot(0,1,2,0,0,...,0)^{T}$ is a vector in $\mathbb{Z}_{3}^{\ell}$ that has at least three distinct entries.

We also need to consider the case where $\widehat{n^{\ell}}(A)$ is in fact a row of $A$ . The following can be shown with a combinatorial argument.

Lemma 22.

Let $\ell\geq 3$ , and let $A\in\mathbb{Z}_{3}^{\ell\times\ell}$ be a matrix that satisfies the first two conditions from Lemma 21. Then $\widehat{n^{\ell}}(A)$ is a row of $A$ if and only if two rows of $A$ are identical.

For each $\ell\geq 3$ as in Theorem 16, we now define the template structure $\mathbf{B}_{\ell}$ that is used to show the separation $\mathcal{L}(\mathcal{Q}_{\ell+1}^{\mathcal{N}_{\text{CSP}}^{\ell}})\not\leq% \mathcal{L}(\mathcal{Q}_{\ell-1})$ .

Definition 23.

Let $\ell\geq 3$ be fixed. Let $\bar{u}$ denote the vector $(0,1,2,0,\dots,0)\in\mathbb{Z}_{3}^{\ell}$ . Let $\mathbf{B}_{\ell}=(\mathbb{Z}_{3},R_{0},R_{1},R_{2})$ with each $R_{j}$ defined as follows. For each $j\in\{0,1,2\}$ , let $R_{j}^{\mathbf{B}_{\ell}}\coloneqq\{(a_{1},...,a_{\ell},\bar{u}\cdot\bar{a})% \mid\bar{a}\in\mathbb{Z}_{3}^{\ell},\sum_{i\in[\ell]}a_{i}=j\}.$

Lemma 24.

For each $\ell\geq 3$ , $n^{\ell}$ is a partial polymorphism of the structure $\mathbf{B}_{\ell}$ .

Proof.

Let $j\in\mathbb{Z}_{3}$ and $\ell\geq 3$ . Let $\bar{b}_{1},\dots,\bar{b}_{\ell}\in R_{j}^{\mathbf{B}_{\ell}}$ . We show that either, $\widehat{n^{\ell}}(\bar{b}_{1},\dots,\bar{b}_{\ell})\in\{\bar{b}_{1},\dots,% \bar{b}_{\ell}\}$ , or $\widehat{n^{\ell}}(\bar{b}_{1},\dots,\bar{b}_{\ell})$ is undefined. Let $A\in\mathbb{Z}_{3}^{\ell\times\ell}$ be the matrix whose rows are the projections of the tuples $\bar{b}_{1},\dots,\bar{b}_{\ell}$ to their first $\ell$ components. If $A$ does not have the $\ell$ -near-unanimity property, then $\widehat{n^{\ell}}(A)$ is undefined, and hence $\widehat{n^{\ell}}(\bar{b}_{1},\dots,\bar{b}_{\ell})$ is undefined. So suppose $A$ has the $\ell$ -near-unanimity property. The row-sums of $A$ are all equal to $j$ by definition of $R_{j}^{\mathbf{B}_{\ell}}$ . If $\widehat{n^{\ell}}(A)$ is not a row of $A$ , then $A$ satisfies the assumptions of Lemma 21. Hence $A\cdot(0,1,2,0,0,\dots,0)^{T}$ contains three distinct entries. This means that $n^{\ell}(\bar{b}_{1(\ell+1)},\dots,\bar{b}_{\ell(\ell+1)})$ is undefined. If $\widehat{n^{\ell}}(A)$ is a row $\bar{a}$ of $A$ , then by Lemma 22, there are two identical rows in $A$ , and these must be equal to $\bar{a}$ . Therefore, the value $\bar{a}\cdot\bar{u}$ also appears at least twice as the $(\ell+1)$ st component of the tuples $\bar{b}_{1},\dots,\bar{b}_{\ell}$ . Hence, if $n^{\ell}(\bar{b}_{1(\ell+1)},\dots,\bar{b}_{\ell(\ell+1)})$ is defined, it yields the correct value $\bar{a}\cdot\bar{u}$ , and thus $\widehat{n^{\ell}}(\bar{b}_{1},\dots,\bar{b}_{\ell})\in\{\bar{b}_{1},\dots,% \bar{b}_{\ell}\}$ . $\hfill\blacktriangleleft$

Template structure for the proof Theorem 18

In Theorem 18, the arity of the quantifiers can be much larger than the arity of the polymorphisms. Thus, the matrices of interest are no longer square, but rectangular, and we cannot directly use Lemma 21. Instead, we use the following. It can be shown with similar reasoning as in the proof of Lemma 20.

Lemma 25.

Let $\ell\geq 3$ , $r\geq\ell$ , $q=\lfloor\frac{r}{\ell-1}\rfloor$ , and $p=r-q(\ell-1)$ . There is a collection $\mathcal{U}\subseteq\mathbb{Z}_{3}^{r}$ of size $|\mathcal{U}|=(\ell-1)q(q-1)+2pq$ such that for every matrix $A\in\mathbb{Z}_{3}^{\ell\times r}$ with the $\ell$ -ary near-unanimity property, one of the following two is the case:

1.

If $\widehat{n^{\ell}}(A)$ is not a row of $A$ , there is a vector $\bar{u}\in\mathcal{U}$ such that $A\cdot\bar{u}$ contains three distinct entries.
2.

If $\widehat{n^{\ell}}(A)$ is a row $\bar{a}$ of $A$ , then either there exists a $\bar{u}\in\mathcal{U}$ such that $A\cdot\bar{u}$ contains three distinct entries, or for all $\bar{u}\in\mathcal{U}$ , $\widehat{n^{\ell}}(A\cdot\bar{u})=\bar{a}\cdot\bar{u}$ .

Proof sketch.

Split $[r]$ into sets $K_{1}\uplus\cdots\uplus K_{\ell-1}=[r]$ such that $|K_{1}|=\cdots=|K_{p}|=q+1$ and $|K_{p+1}|=\cdots=|K_{\ell-1}|=q$ . Define $\mathcal{U}$ as follows. For every $2$ -element set of columns $\{j_{1},j_{2}\}$ such that $\{j_{1},j_{2}\}\subseteq K_{i}$ for some $i\in[\ell-1]$ , include in $\mathcal{U}$ two vectors $\bar{u}^{11},\bar{u}^{12}\in\mathbb{Z}_{3}^{r}$ such that $\bar{u}^{11}_{j_{1}}=1,\bar{u}^{11}_{j_{2}}=1$ , and $\bar{u}^{12}_{j_{1}}=1,\bar{u}^{12}_{j_{2}}=2$ . In all other components, the two vectors are zero. Note that $|\mathcal{U}|=2\bigl(p\binom{q+1}{2}+(\ell-1-p)\binom{q}{2}\bigr)=2\bigl(p% \frac{(q+1)q}{2}+(\ell-1-p)\frac{q(q-1)}{2}\bigr)=(\ell-1)q(q-1)+2pq$ .

Assume first that $\widehat{n^{\ell}}(A)$ is not a row of $A$ . Then $A$ must have $\ell$ non-constant columns whose minority entry is in a different row, respectively. So there is an $i\in[\ell-1]$ such that $K_{i}$ contains at least two of these columns, call them $j_{1},j_{2}$ . By definition of $\mathcal{U}$ , the vectors $\bar{u}^{11},\bar{u}^{12}$ for $j_{1},j_{2}$ are in $\mathcal{U}$ . Then it can be verified that $A\cdot\bar{u}^{11}$ or $A\cdot\bar{u}^{12}$ contains three distinct entries.

Now assume that $\widehat{n^{\ell}}(A)=\bar{a}$ is a row of $A$ . It can be checked that if $\widehat{n^{\ell}}(A\cdot\bar{u})$ is defined for all $\bar{u}\in\mathcal{U}$ , then for every $\bar{u}\in\mathcal{U}$ , there must be at least two rows of $A\cdot\bar{u}$ whose entry is $\bar{a}\cdot\bar{u}$ . Then it follows that $\widehat{n^{\ell}}(A\cdot\bar{u})=\bar{a}\cdot\bar{u}$ for all $\bar{u}\in\mathcal{U}$ , as desired. $\hfill\blacktriangleleft$

The template structure used for Theorem 18 is similar to the previous one, except that it has more extra entries in the relations to forbid the applicability of $n^{\ell}$ (using the set of vectors $\mathcal{U}$ from the above lemma). For $r\geq\ell$ , the instances of this template are supposed to be indistinguishable in $\mathcal{L}(\mathcal{Q}_{r})$ . But the construction using the vectors in $\mathcal{U}$ effectively makes it possible to fix two entries of the original relation with just one variable. To ensure $\mathcal{L}(\mathcal{Q}_{r})$ -indistinguishability of the instances, we therefore need to base the template on $(2r+1)$ -ary relations, augmented by the products with all vectors in $\mathcal{U}$ . For every $\ell\geq 3$ and $r\geq\ell$ , we define the template structure $\mathbf{B}^{*}_{r,\ell}$ over $\mathbb{Z}_{3}$ as follows.

Definition 26.

Let $\ell\geq 3$ and $r\geq\ell$ . Let $\mathcal{U}$ be the set of vectors from Lemma 25, for $(2r+1)$ instead of $r$ . Note that then $m\coloneqq|\mathcal{U}|=(\ell-1)q(q-1)+2pq$ , where $q=\lfloor\frac{2r+1}{\ell-1}\rfloor$ and $p=2r+1-\lfloor\frac{2r+1}{\ell-1}\rfloor(\ell-1)<\ell-1$ . Thus, $m<(\ell-1)q(q-1)+2(\ell-1)q=(\ell-1)q(q+1)\leq(2r+1)(\lfloor\frac{2r+1}{\ell-1% }\rfloor+1)$ . In $\mathbf{B}^{*}_{r,\ell}$ , we define the relations $R_{j}$ , for $j\in\mathbb{Z}_{3}$ as: $R_{j}^{\mathbf{B}^{*}_{r,\ell}}\coloneqq\{(a_{1},\dots,a_{2r+1},\bar{a}\cdot% \bar{u}_{1},\dots,\bar{a}\cdot\bar{u}_{m})\mid\sum_{i\in[2r+1]}a_{i}=j\},$ where $\bar{u}_{1},...,\bar{u}_{m}$ is an enumeration of the set $\mathcal{U}$ .

Note that for fixed $\ell$ , the arity of the template structure is quadratic in $r$ .

Lemma 27.

For all $\ell\geq 3$ and $r\geq\ell$ , $n^{\ell}$ is a partial polymorphism of the structure $\mathbf{B}^{*}_{r,\ell}$ .

Proof.

Analogous to the proof of Lemma 24, now using Lemma 25. $\hfill\blacktriangleleft$

4.2 Constructing instances

We aim to prove $\mathcal{L}(\mathcal{Q}_{\ell+1}^{\mathcal{N}_{\text{CSP}}^{\ell}})\nleq% \mathcal{L}(\mathcal{Q}_{\ell-1})$ by exhibiting two classes $\mathcal{K}_{\ell},\tilde{\mathcal{K}}_{\ell}$ of structures that cannot be distinguished by any sentence in $\mathcal{L}(\mathcal{Q}_{\ell-1})$ but are separated by a sentence in $\mathcal{L}(\mathcal{Q}_{\ell+1}^{\mathcal{N}_{\text{CSP}}^{\ell}})$ . Likewise, we prove $\mathcal{L}(\mathcal{Q}^{\mathcal{N}_{\text{CSP}}^{\ell}}_{q(r,\ell)})\nleq% \mathcal{L}(\mathcal{Q}_{r})$ by constructing classes $\mathcal{K}^{*}_{r,\ell},\tilde{\mathcal{K}}^{*}_{r,\ell}$ of structures that cannot be distinguished by any sentence in $\mathcal{L}(\mathcal{Q}_{r})$ but are separated by a sentence in $\mathcal{L}(\mathcal{Q}^{\mathcal{N}_{\text{CSP}}^{\ell}}_{q(r,\ell)})$ . Both classes of structures are obtained with a CFI-like construction over an $\ell$ -regular (or $(2r+1)$ -regular, respectively) base graph. With each vertex $v$ in the base graph, we associate a substructure, also called vertex gadget. In the first construction, this gadget is denoted $\mathbf{A}(v,s)$ . In the second construction it is $\mathbf{A}^{*}(v,s)$ . In both cases, $s\in\mathbb{Z}_{3}$ is a “charge” we associate with $v$ . We only present $\mathbf{A}(v,s)$ here. The gadget $\mathbf{A}^{*}(v,s)$ is analogous, but such that it matches the template relations from Definition 26 instead of Definition 23. For $v\in V(G)$ , let $E(v)\subseteq E(G)$ denote the set of edges incident to $v$ .

Definition 28 (Vertex gadgets).

Fix $\ell\geq 3$ and let $G=(V,E)$ be a connected $\ell$ -regular graph with an order $\leq^{G}$ on its vertices. Let $\bar{u}\in\mathbb{Z}_{3}^{\ell}$ be the vector from Definition 23, $v\in V$ and $\bar{e}(v)=(e_{1},\dots,e_{\ell})$ the set $E(v)$ , written as a tuple in the order induced by $\leq^{G}$ . Then for each $s\in\mathbb{Z}_{3}$ , we let $\mathbf{A}(v,s)\coloneqq(A_{v},R_{0}^{\mathbf{A}(v,s)},R_{1}^{\mathbf{A}(v,s)}% ,R_{2}^{\mathbf{A}(v,s)})$ , where

$\blacksquare$

$A_{v}\coloneqq B_{v}\cup C_{v}$ for $B_{v}\coloneqq E(v)\times\mathbb{Z}_{3}$ and $C_{v}\coloneqq\{v\}\times\mathbb{Z}_{3}$ ,
$\blacksquare$

$R_{j}^{\mathbf{A}(v,s)}\coloneqq\{((e_{1},a_{1}),\ldots,(e_{\ell},a_{\ell}),(v% ,\bar{a}\cdot\bar{u}))\mid\sum_{i\in[\ell]}a_{i}=j-s\}$ for each $j\in\{0,1,2\}$ ,

We can now define our CFI structures that separate the desired logics. Starting with a suitable base graph, we simply replace every vertex $v$ with a gadget of the form $\mathbf{A}(v,s)$ or $\mathbf{A}^{*}(v,s)$ . We present in the following only the construction that uses the gadgets $\mathbf{A}(v,s)$ (for Theorem 16). The other construction for the proof of Theorem 18 and its relevant properties are completely analogous. Putting together the structures $\mathbf{A}(v,s)$ we have defined for each vertex of $G$ , we obtain our CFI structures:

Definition 29.

Let $G=(V,E,\leq^{G})$ be an $\ell$ -regular connected graph with a linear order on its vertices.

(a)
For each $U\subseteq V$ , we define $\mathbf{A}(G,U)=(A_{G},R_{0}^{\mathbf{A}(G,U)},R_{1}^{\mathbf{A}(G,U)},R_{2}^{% \mathbf{A}(G,U)})$ , where
- $\blacksquare$
  
  $A_{G}\coloneqq\bigcup_{v\in V}A_{v}$ ,
- $\blacksquare$
  
  $R_{j}^{\mathbf{A}(G,U)}\coloneqq\bigcup_{v\in V\setminus U}R_{j}^{\mathbf{A}(v% ,0)}\cup\bigcup_{v\in U}R_{j}^{\mathbf{A}(v,1)}$ for each $j\in\{0,1,2\}$ .
(b)

Furthermore, we define $\mathbf{A}(G)\coloneqq\mathbf{A}(G,\emptyset)$ and $\tilde{\mathbf{A}}(G)\coloneqq\mathbf{A}(G,\{\tilde{v}\})$ , where $\tilde{v}\in V$ is the smallest vertex of $G$ with respect to the order $\leq^{G}$ .

We write $\mathbf{A}^{*}(G)$ and $\tilde{\mathbf{A}}^{*}(G)$ to refer to the analogous structures obtained by using the vertex gadgets $\mathbf{A}^{*}(v,s)$ instead of $\mathbf{A}(v,s)$ .

To define the classes of structures that separate the logics, we apply the above construction to base graphs similar to the ones used by Hella in [15]. For a number $k\in\mathbb{N}$ , we call a graph $k$ -connected if it is connected and remains so after the removal of any $k_{1}$ vertices and $k_{2}$ edges, for any $k_{1}+k_{2}<k$ . Arbitrarily large graphs having this and other useful properties exist, for example constructions based on higher-dimensional grids.

Lemma 30.

For every $d\geq 2$ and for infinitely many $n\in\mathbb{N}$ , there exists a $d$ -regular bipartite graph that is $d$ -connected and satisfies that each part of the bipartition contains exactly $n$ vertices.

For fixed $d,n\in\mathbb{N}$ , we now define a graph that we denote $G_{d,n}$ . This will be used as the base graph for our construction detailed above. Let $H$ denote a fixed graph with the properties from Lemma 30 for values $(d-1),n$ . Now $G_{d,n}$ consists of $n+1$ disjoint copies of $H$ , denoted $H_{1},\dots,H_{n+1}$ . We also add connections between the $H_{i}$ such that for each $i\in[n+1]$ , every vertex in $H_{i}$ has precisely one edge leading into a different copy $H_{j}$ . Formally, name the vertices in the two parts of the bipartition of $H_{i}$ as follows: $V(H_{i})=\{v_{ij}\mid j\in[n+1]\setminus\{i\}\}\uplus\{w_{ij}\mid j\in[n+1]% \setminus\{i\}\}.$ Then let $E(G_{d,n})\coloneqq\bigcup_{i\in[n+1]}E(H_{i})\cup\{v_{ij}w_{ji}\mid i,j\in[n+% 1],i\neq j\}.$ Note that $G_{d,n}$ is again bipartite with the $v$ -vertices and the $w$ -vertices forming the two parts of the bipartition. Moreover, $G_{d,n}$ is $d$ -regular because $H$ is $(d-1)$ -regular. For values $n\in\mathbb{N}$ for which Lemma 30 does not guarantee the existence of a graph, $G_{d,n}$ is simply undefined.

For the proofs of Theorems 16 and 18, we use the following classes of structures, which will be shown to be inseparable in the respective logics of interest. For Theorem 16, for each $\ell\geq 3$ , the two classes are $K_{\ell}\coloneqq\{\mathbf{A}(G_{\ell,n})\mid n\in\mathbb{N}\}$ and $\tilde{\mathcal{K}}_{\ell}\coloneqq\{\tilde{\mathbf{A}}(G_{\ell,n})\mid n\in% \mathbb{N}\}$ . For Theorem 18, for $r\geq\ell\geq 3$ , the classes are $K^{*}_{r,\ell}\coloneqq\{\mathbf{A}^{*}(G_{2r+1,n})\mid n\in\mathbb{N}\}$ and $\tilde{\mathcal{K}}^{*}_{r,\ell}\coloneqq\{\tilde{\mathbf{A}}^{*}(G_{2r+1,n})% \mid n\in\mathbb{N}\}$ .

4.3 (In-)distinguishability of the instances

We first show that there is a sentence in $\mathcal{L}(\mathcal{Q}_{\ell+1}^{\mathcal{N}_{\text{CSP}}^{\ell}})$ that separates $\mathcal{K}_{\ell}$ from $\tilde{\mathcal{K}}_{\ell}$ .

Lemma 31.

For each $n\in\mathbb{N}$ , there exists a homomorphism $h\colon\mathbf{A}(G_{\ell,n})\to\mathbf{B}_{\ell}$ .

Proof.

Let $G_{\ell,n}=(V,E)$ . A homomorphism $h\colon\mathbf{A}(G_{\ell,n})\to\mathbf{B}_{\ell}$ can be defined by letting $h(e,a)=a$ for each $e\in E,a\in\mathbb{Z}_{3}$ , and likewise, $h(v,a)=a$ for every $v\in V$ . By definition of the relations $R_{j}$ in $\mathbf{A}(G_{\ell,n})$ and $\mathbf{B}_{\ell}$ , this is a homomorphism. $\hfill\blacktriangleleft$

Lemma 32.

For each $n\in\mathbb{N}$ , there exists no homomorphism from $\tilde{\mathbf{A}}(G_{\ell,n})$ to $\mathbf{B}_{\ell}$ .

Proof.

Again, let $G_{\ell,n}=(V,E)$ . Consider the following system of linear equations $\mathcal{E}$ over $\mathbb{Z}_{3}$ : For each $e\in E$ , it has one variable $x_{e}$ , and for each $v\in V\setminus\{\tilde{v}\}$ , it has the equation $\sum_{e\in E(v)}x_{e}=0$ . The equation associated with $\tilde{v}$ reads $\sum_{e\in E(\tilde{v})}x_{e}=1$ . Now suppose for a contradiction that there exists a homomorphism $h\colon\tilde{\mathbf{A}}(G_{\ell,n})\to\mathbf{B}_{\ell}$ . Then $h$ defines a solution $\lambda$ for $\mathcal{E}$ via $\lambda(x_{e})\coloneqq h(e,0)$ .

But such a solution cannot exist: Let $S\uplus T=V(G)$ be the bipartition of $G_{\ell,n}$ . We assume w.l.o.g. that $\tilde{v}\in S$ . Then we have $\sum_{v\in S}\sum_{e\in E(v)}\lambda(x_{e})=1$ and $\sum_{v\in T}\sum_{e\in E(v)}\lambda(x_{e})=0$ . However, this is a contradiction since clearly $\sum_{v\in S}\sum_{e\in E(v)}\lambda(x_{e})=\sum_{e\in E}\lambda(x_{e})=\sum_{% v\in T}\sum_{e\in E(v)}\lambda(x_{e})$ . $\hfill\blacktriangleleft$

Corollary 33.

There is a sentence $\psi\in\mathcal{L}(\mathcal{Q}_{\ell+1}^{\mathcal{N}_{\text{CSP}}^{\ell}})$ such that for each $n\in\mathbb{N}$ , $\mathbf{A}(G_{\ell,n})$ and $\tilde{\mathbf{A}}(G_{\ell,n})$ are separated by $\psi$ .

Proof.

By Lemma 24, $n^{\ell}$ is a polymorphism of $\mathbf{B}_{\ell}$ . Thus, the CSP quantifier for the $(\ell+1)$ -ary template $\mathbf{B}_{\ell}$ is in $\mathcal{Q}_{\ell+1}^{\mathcal{N}_{\text{CSP}}^{\ell}}$ . By Lemmas 31 and 32, this quantifier distinguishes $\mathbf{A}(G_{\ell,n})$ and $\tilde{\mathbf{A}}(G_{\ell,n})$ , for every $n\in\mathbb{N}$ . $\hfill\blacktriangleleft$ The preceding assertions can be shown in exactly the same way for the classes $\mathcal{K}^{*}_{r,\ell}$ and $\tilde{\mathcal{K}}^{*}_{r,\ell}$ , where the polymorphism-closedness of the template $\mathbf{B}^{*}_{r,\ell}$ is due to Lemma 27.

To finish the proof of the separation $\mathcal{L}(\mathcal{Q}_{\ell+1}^{\mathcal{N}_{\text{CSP}}^{\ell}})\nleq% \mathcal{L}(\mathcal{Q}_{\ell-1})$ (and thus of Theorem 16), we show that no sentence in $\mathcal{L}(\mathcal{Q}_{\ell-1})$ can distinguish between the classes $\mathcal{K}_{\ell}$ and $\tilde{\mathcal{K}}_{\ell}$ . To achieve this, we show that for every $k\geq\ell-1$ , there exists $n\in\mathbb{N}$ such that Duplicator has a winning strategy in the game $\mathrm{BP}^{k}_{\ell-1}(\mathbf{A}(G_{\ell,n}),\tilde{\mathbf{A}}(G_{\ell,n}))$ . Then it follows with Corollary 3 that $\mathcal{K}_{\ell}$ and $\tilde{\mathcal{K}}_{\ell}$ cannot be separated by a sentence of $\mathcal{L}(\mathcal{Q}_{\ell-1})$ .

The indistinguishability of $\mathcal{K}^{*}_{r,\ell}$ and $\tilde{\mathcal{K}}^{*}_{r,\ell}$ in $\mathcal{L}(\mathcal{Q}_{r})$ is shown with a similar argument. So from now on, let $k\geq\ell-1$ be a fixed number of pebbles. We choose $n\in\mathbb{N}$ so that $G_{\ell,n}$ is defined, and $n$ is sufficiently larger than $k$ . In the following, write $G\coloneqq G_{\ell,n}$ and let $V$ and $E$ be the vertex and edge set of $G$ . Recall that $G$ is the disjoint union of identical graphs $H_{1},\dots H_{n+1}$ with certain connections between them.

Lemma 34.

Duplicator has a winning strategy in the game $\mathrm{BP}^{k}_{\ell-1}(\mathbf{A}(G),\tilde{\mathbf{A}}(G))$ .

The lemma is proved by showing that Duplicator can maintain an invariant which prevents Spoiler from winning. Let $(\alpha,\beta)$ be a position in the game $\mathrm{BP}^{k}_{\ell-1}(\mathbf{A}(G),\tilde{\mathbf{A}}(G))$ with $\mathrm{dom}(\alpha)=\mathrm{dom}(\beta)\subseteq\{x_{1},\ldots,x_{k}\}$ . For the sake of simplicity, we denote the tuples of pebbled elements in the image of $\alpha$ and $\beta$ by $\bar{\alpha}$ and $\bar{\beta}$ , respectively. Furthermore, we call $(\bar{\alpha},\bar{\beta})$ the corresponding pebble position of the game.

A vertex $u\in V(G)$ is safe in a pebble position $(\bar{\alpha},\bar{\beta})$ if $u=v_{ij}$ or $u=w_{ij}$ and $A_{v}$ is pebble-free (i.e., no component of $\bar{\alpha}$ or $\bar{\beta}$ is in $A_{v}$ ) for every $v\in V(H_{i})\cup V(H_{j})$ .

Let $u\in V$ . We call a bijection $f\colon A_{G}\to A_{G}$ good bar $u$ if for every $v\in V\setminus\{u\}$ , $f|_{A_{v}}\colon A_{v}\to A_{v}$ is a partial isomorphism $\mathbf{A}(G)\to\tilde{\mathbf{A}}(G)$ (thus, $f$ is an isomorphism between $\mathbf{A}(G)$ and $\tilde{\mathbf{A}}(G)$ except at $A_{u}$ ).

To prove Lemma 34, we show that Duplicator can maintain the following invariant for the pebble positions $(\bar{\alpha},\bar{\beta})$ reached by the moves of the players: There exists a bijection $f\colon A_{G}\to A_{G}$ with $f(\bar{\alpha})=\bar{\beta}$ that is good bar $u$ , for some $u\in V$ which is safe.

Lemma 35.

Let $(\bar{\alpha},\bar{\beta})$ be the current pebble position in $\mathrm{BP}^{k}_{\ell-1}(\mathbf{A}(G),\tilde{\mathbf{A}}(G))$ . Assume the invariant holds in the beginning of the round. Then Duplicator has a strategy to ensure the invariant also in the beginning of the following round.

The proof idea is as follows. Duplicator begins the round by playing the bijection $f\colon\mathbf{A}(G)\to\tilde{\mathbf{A}}(G)$ sending $\bar{\alpha}$ to $\bar{\beta}$ which exists because the invariant holds at the beginning of the round. Let $u$ be the vertex such that $f$ is good bar $u$ . Now Spoiler modifies the position of up to $\ell-1$ pebbles in both structures, leading to a new pebble position $(\bar{\alpha}^{\prime},\bar{\beta}^{\prime})$ . Duplicator has to find a new bijection $f^{\prime}$ that satisfies the invariant again. This can be done using a pebble-free path $P$ from $u$ to another vertex $u^{\prime}$ which is safe with respect to $(\bar{\alpha}^{\prime},\bar{\beta}^{\prime})$ : Indeed, a standard property of CFI-like constructions is that inconsistencies in bijections can always be “shifted” along a path in the base graph. More precisely, for every path $P$ , and each constant $c\in\mathbb{Z}_{3}$ , there exists a bijection $g_{P,c}\colon\mathbf{A}(G)\to\tilde{\mathbf{A}}(G)$ that induces a local isomorphism everywhere except at the vertex gadgets belonging to the two endpoints $v_{1},v_{2}$ of $P$ : For each $j\in\{1,2\}$ , $g_{P,c}$ induces an isomorphism from $\mathbf{A}(v_{j},s_{j})$ to $\mathbf{A}(v_{j},s_{j}+c)$ , where $s_{j}\in\mathbb{Z}_{3}$ is the charge associated with $v_{j}$ in $\mathbf{A}(G)$ . In other words, for $P$ a pebble-free path from $u$ to some safe $u^{\prime}$ , and for the appropriate choice of $c\in\mathbb{Z}_{3}$ , $f^{\prime}\coloneqq g_{P,c}\circ f$ will be good bar $u^{\prime}$ . It remains to argue why such a pebble-free path to a safe vertex always exists. This can be done exactly like in [15]: Because the number of copies of $H_{i}$ in $G$ is sufficiently larger than $k$ , there always exists some pebble-free copy $H_{i}$ and safe $u^{\prime}\in V(H_{i})$ . The pebble-avoiding path $P$ from $u$ to $u^{\prime}$ exists because each copy $H_{i}$ is sufficiently connected. The only difference to [15] is that now, if a pebble has been placed on $C_{u}=\{u\}\times\mathbb{Z}_{3}$ , one has to take extra care: If the path $P$ starts in $u$ via the edge $e_{2}$ or $e_{3}\in\bar{e}(u)$ , then there is a problem because $\bar{u}_{i}\neq 0$ for $i\in\{2,3\}$ (see Definition 23 for the vector $\bar{u}$ ). As a consequence of this, $g_{P,c}$ cannot be defined so that it fixes the pebbled elements in $C_{u}$ . The workaround in this case is to use two paths $P_{1},P_{2}$ from $u$ to the same safe vertex $u^{\prime}$ , one via $e_{2}$ and one via $e_{3}$ , and to suitably distribute the value $c\in\mathbb{Z}_{3}$ by which $f$ has to be corrected at $u$ across the two paths.

The proof of Theorem 16 is now straightforward: Corollary 33 shows that for every fixed $\ell\geq 3$ , our constructed classes $\mathcal{K}_{\ell}$ and $\tilde{\mathcal{K}}_{\ell}$ are separated by a sentence of $\mathcal{L}(\mathcal{Q}_{\ell+1}^{\mathcal{N}_{\text{CSP}}^{\ell}})$ . Lemma 34 together with Corollary 3 shows that the classes are inseparable in $\mathcal{L}(\mathcal{Q}_{\ell-1})$ . Thus, $\mathcal{L}(\mathcal{Q}_{\ell+1}^{\mathcal{N}_{\text{CSP}}^{\ell}})\not\leq% \mathcal{L}(\mathcal{Q}_{\ell-1})$ . The proof of Theorem 18 is analogous. We show that for every pebble number $k\geq r$ , there is an $n\in\mathbb{N}$ such that Duplicator has a winning strategy in $\mathrm{BP}^{k}_{r}(\mathbf{A}^{*}(G_{2r+1,n}),\tilde{\mathbf{A}}^{*}(G_{2r+1,% n}))$ . The invariant that Duplicator maintains in this game is the same as above. From the existence of the winning strategy it follows that $\mathcal{K}^{*}_{r,\ell}$ and $\tilde{\mathcal{K}}^{*}_{r,\ell}$ cannot be separated by a sentence in $\mathcal{L}(\mathcal{Q}_{r})$ . Separability of the classes with a CSP quantifier is shown similarly as in Corollary 33.

5 Limitations of partial-Maltsev-closed quantifiers

Write $\mathcal{Q}_{r}^{\mathcal{M}}$ for the class of all $r$ -ary quantifiers that are closed under the partial Maltsev operation. Note that the Maltsev operation is a fixed operation of arity three, and thus the arity of the polymorphism is not a variable that plays a role in our study. Instead, we establish a hierarchy based on the arity of the quantifiers and also construct an example that separates the logic with $r$ -ary Maltsev-closed quantifiers from the logic with all $r$ -ary generalized quantifiers, at least in the context of a fixed number of variables. The interest in this lies in the novel nature of the construction and also the novelty in the use of a Spoiler-Duplicator game specific to Maltsev-closed quantifiers. In the present section we give a brief summary of the results. Full details of the construction and proofs can be found in [11].

We obtain the arity hierarchy for Maltsev-closed quantifiers by noting that the quantifiers used to establish the arity hierarchy in [15] are Maltsev-closed. To be specific, define for each $r\geq 3$ the structure $\mathbf{B}_{r}=(\{0,1\},R_{0},R_{1})$ where $R_{i}=\{(a_{1},\ldots,a_{r})\mid\sum_{1\leq j\leq r}a_{j}=i\pmod{2}\}$ . Then, it follows from the proof of [15, Theorem 8.6] that $\mathrm{CSP}(\mathbf{B}_{r+1})$ is not definable in $\mathcal{L}(\mathcal{Q}_{r}^{\mathcal{M}})$ . Since $\mathbf{B}_{r}$ admits a Maltsev polymorphism, the following is immediate.

Theorem 36.

For every $r\geq 3$ , $\mathcal{L}(\mathcal{Q}_{r}^{\mathcal{M}})\lneq\mathcal{L}(\mathcal{Q}^{% \mathcal{M}}_{r+1}).$

Finally, we show that if we limit our logic to exactly $k$ variables, then there is a quantifier of arity $k$ that cannot be defined by using Maltsev-closed quantifiers of arity $k$ , giving us the following theorem.

Theorem 37.

For every $k\geq 3$ , $\mathcal{L}^{k}(\mathcal{Q}_{k}^{\mathcal{M}})\lneq\mathcal{L}^{k}(\mathcal{Q}% _{k}).$

The proof requires a novel construction and substantial technical work to establish. The details are given in [11]. It leaves open the interesting question of whether we can show that this quantifier is not definable in $\mathcal{L}(\mathcal{Q}_{k}^{\mathcal{M}})$ , without the limitation on the number of variables. The apparent difficulty in obtaining such inexpressibility results for Maltsev-closed quantifiers lies in the fact that the typical hard examples, which are based on the CFI-construction, cannot be used: Their templates admit a Maltsev polymorphism, and so they are distinguishable by a quantifier in $\mathcal{Q}^{\mathcal{M}}$ .

6 Conclusion

Our main results show that the quantifiers closed under $\ell$ -ary partial near-unanimity polymorphisms introduced at CSL’24 [10] indeed give rise to new and interesting logics whose expressive power, in particular if $r=\ell+1$ , is strictly different from any of the logics $\mathcal{L}(\mathcal{Q}_{r})$ that were studied by Hella in 1996 [15].

This establishes the logics $\mathcal{L}(\mathcal{Q}_{r}^{\mathcal{N}^{\ell}})$ as formalisms whose finite-model-theoretic properties deserve further study. One question that comes to mind is what can be said about the equivalence relation induced by $\mathcal{L}(\mathcal{Q}_{r}^{\mathcal{N}^{\ell}})$ on finite structures. Can it be characterized as a homomorphism indistinguishability relation or via a game comonad [1]? For the logics $\mathcal{L}(\mathcal{Q}_{r})$ , the answer is affirmative [7], but for example, the invertible-map equivalences (which also stem from certain generalized quantifiers strictly between $\mathcal{Q}_{r}$ and $\mathcal{Q}_{r+1}$ ), there provably is no such characterization [22], so it would be interesting to clarify the situation for $\mathcal{L}(\mathcal{Q}_{r}^{\mathcal{N}^{\ell}})$ . It would also be desirable to tighten the gap between the arity reduction we have in Theorem 15 and the quadratic arity increase in Theorem 18: It seems plausible that already a smaller increase in arity should give strictly more expressive power.

The long-term goal of the study of polymorphism-closed quantifiers is, however, to establish inexpressibility results for quantifiers stronger than $\mathcal{Q}_{r}^{\mathcal{N}^{\ell}}$ , in particular the partial Maltsev-closed ones. Theorem 37 is a first (and highly non-trivial) step in that direction but ultimately, we would like to exhibit an $r$ -ary class of structures that is undefinable in the full logic $\mathcal{L}(\mathcal{Q}_{r}^{\mathcal{M}})$ , without a restriction on the number of variables.

An even harder open problem is to understand the expressive power of quantifiers closed under partial weak near-unanimity polymorphism, for which we do not even know a model-comparison game yet. From a CSP perspective, weak near-unanimity is the most interesting condition as it characterizes precisely the finite-domain CSPs that are solvable in polynomial time (assuming P $\neq$ NP).

References

[1] S. Abramsky, A. Dawar, and P. Wang. The pebbling comonad in finite model theory. In 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–12. IEEE, 2017. URL: https://dl.acm.org/doi/10.5555/3329995.3330064.
[2] L. Barto and M. Kozik. Constraint satisfaction problems of bounded width. In 2009 50th Annual IEEE symposium on foundations of computer science, pages 595–603. IEEE, 2009. URL: https://dl.acm.org/doi/10.1109/FOCS.2009.32.
[3] L. Barto, A. Krokhin, and R. Willard. Polymorphisms, and How to Use Them. In Andrei Krokhin and Stanislav Zivny, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1–44. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2017. doi:10.4230/DFU.Vol7.15301.1.
[4] A. Bulatov. A Dichotomy Theorem for Nonuniform CSPs. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 319–330, 2017. doi:10.1109/FOCS.2017.37.
[5] A. Bulatov and V. Dalmau. A simple algorithm for mal’tsev constraints. SIAM J. Comput., 36:16–27, 2006. doi:10.1137/050628957.
[6] J. Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12:389–410, 1992. doi:10.1007/BF01305232.
[7] A. Ó Conghaile and A. Dawar. Game comonads & generalised quantifiers. In Christel Baier and Jean Goubault-Larrecq, editors, 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, January 25-28, 2021, Ljubljana, Slovenia (Virtual Conference), volume 183 of LIPIcs, pages 16:1–16:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.CSL.2021.16.
[8] A. Dawar. Linear algebraic quantifiers. In K. Meer, A. Rabinovich, E. Ravve, and A. Villaveces, editors, Model Theory, Computer Science, and Graph Polynomials, pages 215–237. Springer, 2025. Festschrift in Honor of Johann A. Makowsky.
[9] A. Dawar, E. Grädel, and W. Pakusa. Approximations of isomorphism and logics with linear-algebraic operators. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, 2019. doi:10.4230/LIPIcs.ICALP.2019.112.
[10] A. Dawar and L. Hella. Quantifiers Closed Under Partial Polymorphisms. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024), volume 288 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1–23:19, 2024. doi:10.4230/LIPIcs.CSL.2024.23.
[11] Anuj Dawar, Lauri Hella, and Benedikt Pago. Arity hierarchies for quantifiers closed under partial polymorphisms, 2025. arXiv:2511.11326.
[12] H-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 2nd edition, 1999.
[13] H.D. Ebbinghaus. Extended logics: the general framework. In J. Barwise and S. Feferman, editors, Model-Theoretic Logics, pages 25–76. Springer, 1985.
[14] R. Fagin, P. G. Kolaitis, and L. Popa. Data exchange: getting to the core. ACM Trans. Database Syst., 30:174–210, 2005. doi:10.1145/1061318.1061323.
[15] L. Hella. Logical hierarchies in PTIME. Information and Computation, 129:1–19, 1996. doi:10.1006/INCO.1996.0070.
[16] L. Hella. The expressive power of CSP-quantifiers. In 31st EACSL Annual Conference on Computer Science Logic, CSL, pages 25:1–25:19, 2023. doi:10.4230/LIPIcs.CSL.2023.25.
[17] P. Jonsson, V. Lagerkvist, G. Nordh, and B. Zanuttini. Strong partial clones and the time complexity of SAT problems. J. Comput. Syst. Sci., 84:52–78, 2017. doi:10.1016/J.JCSS.2016.07.008.
[18] V. Lagerkvist and M. Wahlström. Sparsification of SAT and CSP problems via tractable extensions. ACM Trans. Comput. Theory, 12(2):13:1–13:29, 2020. doi:10.1145/3389411.
[19] V. Lagerkvist and M. Wahlström. The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems. ACM Trans. Comput. Theory, 14(1):2:1–2:54, 2022. doi:10.1145/3492336.
[20] L. Libkin. Elements of Finite Model Theory. Springer, 2004.
[21] M. Lichter. Separating rank logic from polynomial time. J. ACM, 70(2):14:1–14:53, 2023. doi:10.1145/3572918.
[22] M. Lichter, B. Pago, and T. Seppelt. Limitations of Game Comonads for Invertible-Map Equivalence via Homomorphism Indistinguishability. In Aniello Murano and Alexandra Silva, editors, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024), volume 288 of Leibniz International Proceedings in Informatics (LIPIcs), pages 36:1–36:19, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.CSL.2024.36.
[23] D. Zhuk. A proof of the CSP dichotomy conjecture. J. ACM, 67:30:1–30:78, 2020. doi:10.1145/3402029.

[bib.bib1] [1] S. Abramsky, A. Dawar, and P. Wang. The pebbling comonad in finite model theory. In 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–12. IEEE, 2017. URL: https://dl.acm.org/doi/10.5555/3329995.3330064.

[bib.bib2] [2] L. Barto and M. Kozik. Constraint satisfaction problems of bounded width. In 2009 50th Annual IEEE symposium on foundations of computer science, pages 595–603. IEEE, 2009. URL: https://dl.acm.org/doi/10.1109/FOCS.2009.32.

[bib.bib3] [3] L. Barto, A. Krokhin, and R. Willard. Polymorphisms, and How to Use Them. In Andrei Krokhin and Stanislav Zivny, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1–44. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2017. doi:10.4230/DFU.Vol7.15301.1.

[bib.bib4] [4] A. Bulatov. A Dichotomy Theorem for Nonuniform CSPs. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 319–330, 2017. doi:10.1109/FOCS.2017.37.

[bib.bib5] [5] A. Bulatov and V. Dalmau. A simple algorithm for mal’tsev constraints. SIAM J. Comput., 36:16–27, 2006. doi:10.1137/050628957.

[bib.bib6] [6] J. Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12:389–410, 1992. doi:10.1007/BF01305232.

[bib.bib7] [7] A. Ó Conghaile and A. Dawar. Game comonads & generalised quantifiers. In Christel Baier and Jean Goubault-Larrecq, editors, 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, January 25-28, 2021, Ljubljana, Slovenia (Virtual Conference), volume 183 of LIPIcs, pages 16:1–16:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.CSL.2021.16.

[bib.bib8] [8] A. Dawar. Linear algebraic quantifiers. In K. Meer, A. Rabinovich, E. Ravve, and A. Villaveces, editors, Model Theory, Computer Science, and Graph Polynomials, pages 215–237. Springer, 2025. Festschrift in Honor of Johann A. Makowsky.

[bib.bib9] [9] A. Dawar, E. Grädel, and W. Pakusa. Approximations of isomorphism and logics with linear-algebraic operators. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, 2019. doi:10.4230/LIPIcs.ICALP.2019.112.

[bib.bib10] [10] A. Dawar and L. Hella. Quantifiers Closed Under Partial Polymorphisms. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024), volume 288 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1–23:19, 2024. doi:10.4230/LIPIcs.CSL.2024.23.

[bib.bib11] [11] Anuj Dawar, Lauri Hella, and Benedikt Pago. Arity hierarchies for quantifiers closed under partial polymorphisms, 2025. arXiv:2511.11326.

[bib.bib12] [12] H-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 2nd edition, 1999.

[bib.bib13] [13] H.D. Ebbinghaus. Extended logics: the general framework. In J. Barwise and S. Feferman, editors, Model-Theoretic Logics, pages 25–76. Springer, 1985.

[bib.bib14] [14] R. Fagin, P. G. Kolaitis, and L. Popa. Data exchange: getting to the core. ACM Trans. Database Syst., 30:174–210, 2005. doi:10.1145/1061318.1061323.

[bib.bib15] [15] L. Hella. Logical hierarchies in PTIME. Information and Computation, 129:1–19, 1996. doi:10.1006/INCO.1996.0070.

[bib.bib16] [16] L. Hella. The expressive power of CSP-quantifiers. In 31st EACSL Annual Conference on Computer Science Logic, CSL, pages 25:1–25:19, 2023. doi:10.4230/LIPIcs.CSL.2023.25.

[bib.bib17] [17] P. Jonsson, V. Lagerkvist, G. Nordh, and B. Zanuttini. Strong partial clones and the time complexity of SAT problems. J. Comput. Syst. Sci., 84:52–78, 2017. doi:10.1016/J.JCSS.2016.07.008.

[bib.bib18] [18] V. Lagerkvist and M. Wahlström. Sparsification of SAT and CSP problems via tractable extensions. ACM Trans. Comput. Theory, 12(2):13:1–13:29, 2020. doi:10.1145/3389411.

[bib.bib19] [19] V. Lagerkvist and M. Wahlström. The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems. ACM Trans. Comput. Theory, 14(1):2:1–2:54, 2022. doi:10.1145/3492336.

[bib.bib20] [20] L. Libkin. Elements of Finite Model Theory. Springer, 2004.

[bib.bib21] [21] M. Lichter. Separating rank logic from polynomial time. J. ACM, 70(2):14:1–14:53, 2023. doi:10.1145/3572918.

[bib.bib22] [22] M. Lichter, B. Pago, and T. Seppelt. Limitations of Game Comonads for Invertible-Map Equivalence via Homomorphism Indistinguishability. In Aniello Murano and Alexandra Silva, editors, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024), volume 288 of Leibniz International Proceedings in Informatics (LIPIcs), pages 36:1–36:19, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.CSL.2024.36.

[bib.bib23] [23] D. Zhuk. A proof of the CSP dichotomy conjecture. J. ACM, 67:30:1–30:78, 2020. doi:10.1145/3402029.

Arity Hierarchies for Quantifiers Closed Under Partial Polymorphisms

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

2 Preliminaries

Generalized quantifiers

Bijective pebble games

Definition 1.

Proposition 2 ([15]).

Corollary 3.

Partial polymorphisms

Example 4.

Lemma 5 ([10, Lemma 9]).

CSP quantifiers

Lemma 6.

Proof.

Corollary 7.

Proof.

3 Arity reductions

Example: Hypergraph colouring

Proposition 8.

Proof sketch.

Arity reductions for 𝓝ℓ-closed quantifiers

Lemma 9.

Proof.

Lemma 10.

Proof.

Corollary 11.

Proof.

Lemma 12.

Corollary 13.

Theorem 14.

Proof.

Theorem 15.

Proof.

4 Arity hierarchies for partial near-unanimity quantifiers

Theorem 16.

Corollary 17.

Proof.

Theorem 18.

Corollary 19.

4.1 Construction of polymorphism-closed templates

Template structure for the proof Theorem 16

Lemma 20.

Proof.

Lemma 21.

Lemma 22.

Definition 23.

Lemma 24.

Proof.

Template structure for the proof Theorem 18

Lemma 25.

Proof sketch.

Definition 26.

Lemma 27.

Proof.

4.2 Constructing instances

Definition 28 (Vertex gadgets).

Definition 29.

Lemma 30.

4.3 (In-)distinguishability of the instances

Lemma 31.

Proof.

Lemma 32.

Proof.

Corollary 33.

Proof.

Lemma 34.

Lemma 35.

5 Limitations of partial-Maltsev-closed quantifiers

Theorem 36.

Arity reductions for $\mathcal{N}^{\ell}$ -closed quantifiers