Zhuk’s bridges, centralizers, and similarity

Ross Willard · 2025

Read Zhuk’s bridges, centralizers, and similarity by Ross Willard (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-2503-03551.txt.

Introduction

Ross Willard extended key constructions in 2025 from a celebrated proof in universal algebra. The solo paper is the second of three driven by his wish to explain, in algebraic terms, one part of Dmitriy Zhuk's proof of the CSP dichotomy theorem. That theorem settled when constraint satisfaction problems are easy versus hard.

Zhuk's device, called a bridge, is extended here to arbitrary meet-irreducible congruences of finite algebras in a broad class of varieties. Willard then ties bridges to centrality and similarity, two other structural notions. In particular, in the variety class at hand, Zhuk's bridges and the similarity bridges from his first paper carry the same information. The catalog creator field appends a funding note; the head byline governs. Readers get a translation between two toolkits for the same deep proof.

Catalog record

CREATORRoss Willard
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE85 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-03551

Browse the full library · About the Tower of Babel

Full text

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

Zhuk’s bridges, centralizers, and similarity Thanks: The support of the Natural Sciences and Engineering Research Council (NSERC) of Canada is gratefully acknowledged. Ross Willard Abstract . This is the second of three papers motivated by the author’s desire to understand and explain “algebraically” one aspect of Dmitriy Zhuk’s proof of the CSP Dichotomy Theorem. In this paper we extend Zhuk’s “bridge” construction to arbitrary meet-irreducible congruences of finite algebras in locally finite varieties with a Taylor term. We then connect bridges to centrality and similarity. In particular, we prove that Zhuk’s bridges and our “proper bridges” (defined in our first paper) convey the same information in locally finite Taylor varieties. 2010 Mathematics Subject Classification 08A05, 08B99 (Primary), 08A70 (Secondary). 1. Introduction Arguably the most important result in universal algebra in the last ten years is the positive resolution to the Constraint Satisfaction Problem (CSP) Dichotomy Conjecture, announced independently in 2017 by Andrei Bulatov [ 2 ] and Dmitriy Zhuk [ 17 , 18 ] . One particular feature of Zhuk’s proof is his analysis of “rectangular critical” subdirect products R\leq_{sd}{\mathbf{A}}_{1}\times\cdots\times{\mathbf{A}}_{n} of finite algebras {\mathbf{A}}_{1},\ldots,{\mathbf{A}}_{n} in certain locally finite idempotent Taylor varieties. Zhuk showed that such relations R induce derived relations, which he named “bridges,” between certain meet-irreducible congruences of {\mathbf{A}}_{1},\ldots,{\mathbf{A}}_{n} which R determines. Zhuk also established a number of useful properties of his bridges, and ultimately used them to tease out implicit linear equations in CSP instances. In this and two companion papers [ 16 , 15 ] , we aim to understand “algebraically” Zhuk’s bridges and their application to rectangular critical relations. Our goal in this paper is to establish precise connections between Zhuk’s bridges, centrality, and a relation called “similarity” due to Freese [ 4 ] in the congruence modular setting and extended to varieties with a weak difference term (including locally finite Taylor varieties) in our first paper [ 16 ] . In Section 2 we give the basic definitions and tools needed in this paper. In Section 3 we summarize the results about similarity from [ 16 ] which we will use here. With these preliminaries out of the way, we address two technical limitations of Zhuk’s original presentation: Zhuk defined his bridges between pairs ({\mathbf{A}},\rho) and ({\mathbf{B}},\sigma) where (i) {\mathbf{A}} and {\mathbf{B}} are finite algebras in a very special kind of Taylor variety, and (ii) \rho and \sigma are congruences satisfying an “irreducibility” property stronger than meet-irreducibility. In fact, Zhuk’s definitions, and all but one of Zhuk’s theorems about bridges (see Theorem 6.4 ), work in arbitrary locally finite Taylor varieties, so in Section 4 we present his definitions and basic results avoiding limitation (i). Then in Section 5 we use tame congruence theory to show how Zhuk’s definitions and basic results can extend to arbitrary meet-irreducible congruences, avoiding limitation (ii). Finally, in Section 6 we align Zhuk’s bridges, in this broader context, with the algebraic relations of centrality and similarity. In particular, we show that Zhuk’s bridges and our “proper bridges” defined in [ 16 ] (see Definition 3.7 ) are equivalent. 2. Definitions and helpful results We assume that the reader is familiar with the fundamentals of universal algebra as given in [ 3 ] , [ 13 ] or [ 1 ] . Our notation generally follows that in [ 13 ] , [ 1 ] and [ 9 ] . If {\mathbf{A}} is an algebra, then \Con({\mathbf{A}}) denotes its congruence lattice. The smallest and largest congruences of {\mathbf{A}} are the diagonal 0_{A}:=\{(a,a)\,:\,\text{$a\in A$}\} and the full congruence 1_{A}:=A^{2} respectively; they may be denoted 0 and 1 if no confusion arises. If \alpha,\beta\in\Con({\mathbf{A}}) with \alpha\leq\beta , then \beta/\alpha denotes the congruence of {\mathbf{A}}/\alpha corresponding to \beta via the Correspondence Theorem ( [ 13 , Theorem 4.12] or [ 1 , Theorem 3.6] ). If in addition \gamma,\delta\in\Con({\mathbf{A}}) with \gamma\leq\delta , then we write (\alpha,\beta)\nearrow(\gamma,\delta) and say that (\alpha,\beta) is perspective up to (\gamma,\delta) , or transposes up to (\gamma,\delta) , if \beta\wedge\gamma=\alpha and \beta\vee\gamma=\delta . The notation (\gamma,\delta)\searrow(\alpha,\beta) means the same thing. We write \alpha\prec\beta and say that \beta covers \alpha , or is an upper cover of \alpha , if \alpha<\beta and there does not exist a congruence \gamma satisfying \alpha<\gamma<\beta . A congruence \alpha is minimal if it covers 0 , and is completely meet-irreducible if \alpha\neq 1 and there exists \alpha^{+} with \alpha\prec\alpha^{+} and such that \alpha<\beta\implies\alpha^{+}\leq\beta for all \beta\in\Con({\mathbf{A}}) . When {\mathbf{A}} is finite, we use the phrase “ meet-irreducible ” to mean the same thing. We say that {\mathbf{A}} is subdirectly irreducible if 0 is completely meet-irreducible, in which case 0^{+} is called the monolith of {\mathbf{A}} . A subset T\subseteq A is a transversal for a congruence \alpha if it contains exactly one element from each \alpha -class. If f:A\rightarrow B is a function, then its graph is the set \operatorname{graph}(f)=\{(a,f(a))\,:\,\text{$a\in A$}\} . If n>0 , then [n] denotes \{1,2,\ldots,n\} . If R\subseteq A_{1}\times\cdots\times A_{n} and i,j\in[n] , then \operatorname{pr}_{i}(R) denotes the projection of R onto its i -th coordinate, and \operatorname{pr}_{i,j}(R) denotes \{(a_{i},a_{j})\,:\,\text{$(a_{1},\ldots,a_{n})\in R$}\} . We follow [ 9 ] and refer to a set of operation symbols with assigned arities as a signature . Every algebra comes equipped with a signature, which indexes the basic operations of the algebra. Terms are formal recipes for constructing new operations from the basic operations via composition and variable manipulations; see [ 13 ] or [ 1 ] or any textbook on first-order logic. We will not distinguish between terms and the term operations they define in an algebra, except when the distinction is crucial. A polynomial of an algebra {\mathbf{A}} is any operation on A having the form t(x_{1},\ldots,x_{n},\mathbf{c}) where t is an (n+k) -ary term in the signature of {\mathbf{A}} and \mathbf{c}\in A^{k} . \Pol_{n}({\mathbf{A}}) is the set of all n -ary polynomials of {\mathbf{A}} . If {\mathbf{A}} is an algebra, a term t(x_{1},\ldots,x_{n}) of {\mathbf{A}} is idempotent if {\mathbf{A}} satisfies the identity t(x,\ldots,x)\approx x , and is a Taylor term if it is idempotent, n>1 , and for each i\in[n] , {\mathbf{A}} satisfies an identity of the form t(u_{1},\ldots,u_{n})\approx t(v_{1},\ldots,v_{n}) where each u_{j} and v_{k} is the variable x or y , and \{u_{i},v_{i}\}=\{x,y\} . An algebra is said to be Taylor if it has a Taylor term. A particularly important example of a Taylor term is a weak near-unanimity term (WNU), which is an n -ary idempotent term w(x_{1},\ldots,x_{n}) with n>1 which satisfies the identities w(y,x,x,\ldots,x)\approx w(x,y,x,\ldots,x)\approx w(x,x,y,\ldots,x)\approx\cdots\approx w(x,\ldots,x,y). Another important example of a Taylor term is a Maltsev term ; this is a ternary term p(x,y,z) satisfying the identities (2.1) p(x,x,y)\approx y\approx p(y,x,x). The identities ( 2.1 ) are called the Maltsev identities . Any ternary operation (whether a term or not) satisfying them is called a Maltsev operation . A variety is a class of algebras (in a common signature) which is closed under subalgebras, homomorphic images, and direct products of arbitrary (including infinite) families of algebras. \mathsf{HSP}({\mathbf{A}}) denotes the smallest variety containing {\mathbf{A}} . A term is a Taylor term, or a WNU term, for a variety if it is such for every algebra in the variety. Because the definitions of Taylor terms and WNU terms are given in terms of

Read the complete text