Zarathustra Brady, Simplifying clones with partial semilattice operations

Tue, 21 Feb 2023, 5:00 pm MST

If you have a non-invertible unary operation $f$ on a finite set, a natural thing to do with it is to create a compositional power $f^n$ which satisfies $f^n(f^n(x)) \approx f^n(x)$. Using this compositional power of $f$, you can produce a simpler clone on a smaller set which satisfies every height-one identity which is satisfied by the original clone. By repeating this process, we can eventually reduce questions about height-one identities in finite algebras to the case of idempotent algebras. It turns out that one can do something similar with two-variable operations: starting from any idempotent binary operation $t$ on a finite set, there is a (nontrivial) functorial construction of a two-variable operation $s$ in the clone generated by $t$ which satisfies the identities $s(x,s(x,y)) \approx s(s(x,y),x) \approx s(x,y)$. Such operations were used extensively by Andrei Bulatov in his proof of the CSP Dichotomy Conjecture, and I call them “partial semilattice operations”. I will describe this functorial construction and show how we can make use of such operations to simplify the behavior of binary absorption in finite algebras while preserving many types of height-one identities.

[slides] [video]