\documentclass{amsart}
\usepackage{amsmath,amsthm,amssymb,url}
\def\Dj{\mbox{\raise0.3ex\hbox{-}\kern-0.4em D}}

\title{Local Mal'cev-like conditions}

\author{Miroslav Ol\v sak}



\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{example}[theorem]{Example}

\newcommand{\lb}{\langle}
\newcommand{\rb}{\rangle}
\newcommand{\m}[1]{{\mbox{\uppercase {\bf {#1}}}}}
\newcommand{\sm}[1]{{\mbox{\scriptsize {\uppercase {\bf {#1}}}}}}
\newcommand{\cn}[1]{{\rm Con}\: {\m{#1}}}
\newcommand{\vr}[1]{{\uppercase {\mathcal{#1}}}}
\newcommand{\Sg}[1]{{\rm Sg}^{\sm #1}}
\newcommand{\Cg}[1]{{\rm Cg}^{\sm #1}}

\begin{document}
\setcounter{section}{1}
\maketitle

All operations which will be discussed are idempotent. By a \emph{strong Mal'cev condition} we mean a finite set of identities in some language. Informally, a strong Mal'cev condition is {\em realized} in an algebra $\m a$ (or variety $\vr V$) if there is a way to interpret the function symbols appearing in the condition as term operations of $\m a$ (or $\vr V$) so that the identities in the Mal'cev condition become true equations in $\m a$ (or $\vr V$).  Another way of saying that an algebra $\m a$ realizes a condition $\vr c$ is saying that $\m a$ has a $<$description of the condition $\vr c>$-term. 


\begin{example}
If an algebra has a commutative idempotent binary term operation $+$ then this algebra has a 4-ary weak near-unanimity term. Proof: just use $w(x,y,z,u)=(x+y)+(z+u)$.
\end{example}

Now we introduce the local satisfaction of a Mal'cev condition.

\begin{definition}
Let \m a be an algebra, let $\vr c$ be a strong Mal'cev condition and and let $X\subseteq A$. We say that $\m a$ realizes $\vr c$ on $X$ if there is a way to interpret the operations as terms of $\m a$ so that for all evaluations of the variables as elements of $X$, all identities in $\vr c$ are true in those evaluations.
\end{definition}

\begin{problem} Let $\m a$ be an algebra and $X\subseteq A$. If $\m a$ has a commutative binary term on $X$, must \m a also have a 4-ary weak near-unanimity term on $X$?
\end{problem}

\underline{Motivations}:
\begin{enumerate}
\item Continuous (for usual implications) vs. uniformly continuous (for local implications) clone homomorphisms.
\item Local is simpler than global!
\end{enumerate}

\begin{definition}
{\em The double loop term} is a strong Mal'cev condition in one 12-ary operation symbol $t$ and two identities plus idempotence. It is given by 
\begin{align*}
t
\begin{pmatrix}
\begin{bmatrix}
x \\
x \\
x \\
y
\end{bmatrix},
\begin{bmatrix}
x \\
x \\
y \\
x
\end{bmatrix},
\begin{bmatrix}
y \\
y \\
x \\
y
\end{bmatrix},
\begin{bmatrix}
y \\
y \\
y \\
x
\end{bmatrix},
\begin{bmatrix}
x \\
y \\
x \\
x
\end{bmatrix},
\begin{bmatrix}
y \\
x \\
x \\
x
\end{bmatrix},
\begin{bmatrix}
x \\
y \\
y \\
y
\end{bmatrix},
\begin{bmatrix}
y \\
x \\
y \\
y
\end{bmatrix},
\begin{bmatrix}
x \\
y \\
x \\
y
\end{bmatrix},
\begin{bmatrix}
x \\
y \\
y \\
x
\end{bmatrix},
\begin{bmatrix}
y \\
x \\
x \\
y
\end{bmatrix},
\begin{bmatrix}
y \\
x \\
y \\
x
\end{bmatrix}
\end{pmatrix}
= 
\begin{bmatrix}
a \\
a \\
b \\
b
\end{bmatrix},
\end{align*}
i.e. one identity between the terms in the first two rows and the other identity is between the terms in the second two rows of the above figure.
\end{definition}

\begin{problem}\label{prb2} Let $\m a$ be an algebra and $X\subseteq A$. If $\m a$ has a Taylor term on $X$, must \m a also have a 12-ary double loop term on $X$?
\end{problem}

We fix a variety $\vr v$ with a Taylor term $t$. Let $\m f=\m f_{\vr v}(X)$ and $X=\{x,y\}$.

Define $\m Q\leq \m f^4$ by 
\begin{align*}
Q=\Sg{a^4}\begin{pmatrix}
\left\{
\begin{bmatrix}
x \\
x \\
x \\
y
\end{bmatrix}\!\!,
\begin{bmatrix}
x \\
x \\
y \\
x
\end{bmatrix}\!\!,
\begin{bmatrix}
y \\
y \\
x \\
y
\end{bmatrix}\!\!,
\begin{bmatrix}
y \\
y \\
y \\
x
\end{bmatrix}\!\!,
\begin{bmatrix}
x \\
y \\
x \\
x
\end{bmatrix}\!\!,
\begin{bmatrix}
y \\
x \\
x \\
x
\end{bmatrix}\!\!,
\begin{bmatrix}
x \\
y \\
y \\
y
\end{bmatrix}\!\!,
\begin{bmatrix}
y \\
x \\
y \\
y
\end{bmatrix}\!\!,
\begin{bmatrix}
x \\
y \\
x \\
y
\end{bmatrix}\!\!,
\begin{bmatrix}
x \\
y \\
y \\
x
\end{bmatrix}\!\!,
\begin{bmatrix}
y \\
x \\
x \\
y
\end{bmatrix}\!\!,
\begin{bmatrix}
y \\
x \\
y \\
x
\end{bmatrix}
\right\}
\end{pmatrix}
\end{align*}
and define $\m r\leq \m f^2$ by
\begin{align*}
\begin{bmatrix}
a \\
b
\end{bmatrix}
\in R \text{ iff }(\exists c\in F)
\begin{bmatrix}
a \\
b \\
c \\
c
\end{bmatrix}
\in Q.
\end{align*}
By the definition of $Q$ we know 
\begin{align*}
\begin{bmatrix}
x \\
y
\end{bmatrix},
\begin{bmatrix}
y \\
x
\end{bmatrix}
\in R
\end{align*}
Moreover, since the set of all generators of $Q$ is invariant under transposition of the first two coordinates, then so is the whole of $Q$. It follows that $R$ is also invariant under the transposition of the first two coordinates as
\begin{align*}
\begin{bmatrix}
a \\
b
\end{bmatrix}
\in R \text{ iff }(\exists c\in F)
\begin{bmatrix}
a \\
b \\
c \\
c
\end{bmatrix}
\in Q \text{ iff }(\exists c\in F)
\begin{bmatrix}
b \\
a \\
c \\
c
\end{bmatrix}
\in Q \text{ iff }
\begin{bmatrix}
b \\
a
\end{bmatrix}
\in R.
\end{align*}

The above argument proves that $R$ is a symmetric relation. Next we prove

\begin{theorem}\label{thm1}
The set $A:=\left\{\begin{bmatrix}
x\\
y
\end{bmatrix}\!,
\begin{bmatrix}
y\\
x
\end{bmatrix}
\right\}$ absorbs the set $B:=\left\{\begin{bmatrix}
x\\
x
\end{bmatrix}\!,
\begin{bmatrix}
y\\
y
\end{bmatrix}
\right\}$ into $R$.
\end{theorem}

\begin{proof}

We will prove absorption via the Taylor term $t$.

Indeed, let $i\leq n$, let $[a_1,b_1]^T,\ldots,[a_{i-1}]^T,[a_{i+1}]^T,\ldots ,[a_n,b_n]^T\in A$ and let $[a_i,b_i]^T\in B$ (of course, all $a_j,b_k\in\{x,y\}$). Since $t$ is Taylor, there exist $c_1,\ldots,c_n,$ $d_1,\ldots,d_n\in\{x,y\}$ such that $c_i=x$, $d_i=y$ and $t(c_1,\ldots,c_n)\approx t(d_1,\ldots,d_n)$. Let $t(c_1,\ldots,c_n)=z$. Note that for all $j\neq i$, $[a_j,b_j,c_j,d_j]^T\in Q$ (actually they are among the generators of $Q$) since $[a_j,b_j]^T\in A$, so $\{a_j,b_j\}=\{x,y\}$. Moreover, either $[a_i,b_i,c_i,d_i]^T=[x,x,x,y]^T$ or $[a_i,b_i,c_i,d_i]^T=[y,y,x,y]^T$, so $[a_i,b_i,c_i,d_i]^T\in Q$. We compute
\begin{align*}
t
\begin{pmatrix}
\begin{bmatrix}
a_1 \\
b_1 \\
c_1 \\
d_1
\end{bmatrix}\!\!,
\begin{bmatrix}
a_2 \\
b_2 \\
c_2 \\
d_2
\end{bmatrix}\!\!,\ldots,
\begin{bmatrix}
a_n \\
b_n \\
c_n \\
d_n
\end{bmatrix}
\end{pmatrix}=\begin{bmatrix}
u \\
v \\
z \\
z
\end{bmatrix}
\end{align*}
So 
\begin{align*}
t
\begin{pmatrix}
\begin{bmatrix}
a_1 \\
b_1 
\end{bmatrix}\!\!,
\begin{bmatrix}
a_2 \\
b_2 
\end{bmatrix}\!\!,\ldots,
\begin{bmatrix}
a_n \\
b_n 
\end{bmatrix}
\end{pmatrix}\in R\text{, as desired}.
\end{align*}
\end{proof}

We would like to prove that in the above situation $R$ has a loop, but we can't do it. So we have

\begin{problem}\label{prb3}
Prove or disprove that $R$ must have a loop.
\end{problem}

We can prove Problem \ref{prb3} when $t$ is 3-ary:

\begin{theorem}
Let $A:=\left\{\begin{bmatrix}
x\\
y
\end{bmatrix}\!,
\begin{bmatrix}
y\\
x
\end{bmatrix}
\right\}$ absorb the set $B:=\left\{\begin{bmatrix}
x\\
x
\end{bmatrix}\!,
\begin{bmatrix}
y\\
y
\end{bmatrix}
\right\}$ into $R$ via a ternary idempotent operation $t$. Then $R$ contains a loop.
\end{theorem}

\begin{proof}
Notation: to avoid even longer expressions, we will write $(abc)$ for $t(a,b,c)$. Denote $a=((xyy)(xyx)(xxy))$, $b=((yxx)(yxy)(xxy))$ and $c=((yxx)(xyx)(yyx))$. We will force the loop at $(abc)$. We do it by proving that $[(abc),a]^T\in R$, $[(abc),b]^T\in R$ and $[(abc),c]^T\in R$ and then applying $t$ to those three vectors (and using idempotence). Indeed,
\(
\begin{bmatrix}
(abc)\\
a
\end{bmatrix}
=\)
\[\left(
\begin{array}{ccccccccc}
((xyy) & (xyx) & (xxy)) & ((yxx) & (yxy) & (xxy)) & ((yxx) & (xyx) & (yyx))\\
(\;\;\;x\;\;\; & y & \;\;\;y\;\;\;) & ((xyx) & (xyx) & (xyx)) & ((xxy) & (xxy) & (xxy))
\end{array}
\right).
\]
Here the first three vector columns are in $R$ since $A$ absorbs $B$ into $R$ via $t$, while the remaining six are in $t$ applied to vectors in $A$. Similarly, 
\(
\begin{bmatrix}
(abc)\\
b
\end{bmatrix}
=\)
\[\left(
\begin{array}{ccccccccc}
((xyy) & (xyx) & (xxy)) & ((yxx) & (yxy) & (xxy)) & ((yxx) & (xyx) & (yyx))\\
((yxx) & (yxx) & (yxx)) & (\;\;\;y\;\;\; & x & \;\;\;y\;\;\;) & ((xxy) & (xxy) & (xxy))
\end{array}
\right).
\]
Here we apply absorption to the middle three vector columns. Finally, \(
\begin{bmatrix}
(abc)\\
c
\end{bmatrix}
=\)
\[\left(
\begin{array}{ccccccccc}
((xyy) & (xyx) & (xxy)) & ((yxx) & (yxy) & (xxy)) & ((yxx) & (xyx) & (yyx))\\
((yxx) & (yxx) & (yxx)) & ((xyx) & (xyx) & (xyx)) & (\;\;\;y\;\;\; & y & \;\;\;x\;\;\;)
\end{array}
\right).
\]
\end{proof}

As a side note, Libor was able to prove it using $t$ of arity 5, however he needs to to assume finiteness.

Note that $R$ must contain an odd cycle. Indeed, let $a_1^0,\ldots,a_n^0=x$ and for $0<i\leq n$ define $a_i^i=a_i^{i-1}$, while for $j\neq i$, if $a_j^{i-1}=x$ then $a_j^i=y$, while if $a_j^{i-1}=y$ then $a_j^i=x$. Now compute
\begin{align*}
\begin{bmatrix}
b^0 \\
b^1 \\
\vdots \\
b^n
\end{bmatrix}:=
t
\begin{pmatrix}
\begin{bmatrix}
a_1^0 \\
a_1^1 \\
\vdots \\
a_1^n
\end{bmatrix}\!\!,
\begin{bmatrix}
a_2^0 \\
a_2^1 \\
\vdots \\
a_2^n
\end{bmatrix}\!\!,
\ldots,
\begin{bmatrix}
a_n^0 \\
a_n^1 \\
\vdots \\
a_n^n
\end{bmatrix}
\end{pmatrix}
\end{align*}
For all $0\leq i<n$, from Theorem~\ref{thm1} follows that $[b^i,b^{i+1}]^T\in R$. Moreover, $b^0=x$ by idempotence and if $n$ is odd, then $b^n=t(x,x,\ldots,x)=x$ so we have an odd cycle in $R$, while if $n$ is even, then $b^n=t(y,y,\ldots,y)=y$ and since $[y,x]^T\in R$, we get an odd cycle in $R$ again.

Denote by $R^{\rightarrow k}:=R\circ R\circ\ldots\circ R$ (using $k-1$ symbols $\circ$). Since there is an odd cycle in $R$, and $R$ is a symmetric relation, then $R$ contains odd cycles of all except finitely many lengths. Assume that $R$ has no loop. Let $k$ be maximal such that $R^{\rightarrow 3^k}$ contains no loop. $R^{\rightarrow 3^k}$ contains a triangle. So, if we were able to prove that triangle implies loop, we would be in business for Problem~\ref{prb3}.

By assuming an additional absorption condition, we can complete this proof. We will prove two statements by a simultaneous induction on the arity of the term $n$ which is used in the absorption.

\begin{theorem}\label{thm3}
Let $R$ be binary, symmetric, contains a triangle $a,b,c$ and let $a^+$ absorb $a$. Then $R$ has a loop.
\end{theorem}

\begin{theorem}\label{thm2}
Let $\m a$ be an algebra with a Taylor term $t$. Let $R$ be a symmetric, nonempty binary relation on $A$, $R\lhd \Delta_A$. Then $R$ contains a loop.
\end{theorem}

\begin{proof}[Proof of the base case $n=1$ of Theorem~\ref{thm3}]
The base case follows from idempotence. Indeed, $t(a)\in a^+$ by the fact that $a^+$ absorbs $a$ via $t$. Therefore, $[a,a]^T\in R$ is the desired loop.
\end{proof}

Now come the inductive steps.

\begin{proof}[Proof of Theorem~\ref{thm3} assuming Theorem~\ref{thm2} for $n-1$]:
Let the arity $n$ of $t$ be greater than 1. Define $R':=R\cap a^+$ and $A'=\{x\in a^+:x$ is not an isolated vertex in $R'\}$. We know that $b,c\in A'$ and $[b,c]^T\in R'$. We define a new "strong absorption" by $B\lhd\!\!\!\lhd A$ if there exists a term $s$ in more than one variable such that whenever at most two entries in a tuple $\overline{a}$ are in $A$, but the rest are in $B$, then $s(\overline{a})\in B$. Finally, denote $S:=R'\circ R'\circ R'$.

We claim that $S\lhd\!\!\!\lhd\; (A')^2$. We will put the vectors in $(A')^2$ on the outside to be easier to see what we are doing but it should be obvious they can be on any two positions in the term. We assume that $[a_1,d_1]^T,[a_n,d_n]^T\in (A')^2$ and that for all $1<i<n$, $[a_i,b_i]^T,[b_i,c_i]^T,[c_i,d_i]^T\in R'$. We select any $c_1$ and $b_n$ such that $[c_1,d_1]^T,[a_n,b_n]^T\in R'$ (we can because $d_1$ and $a_n$ are not isolated vertices).
\begin{align*}
t
\begin{pmatrix}
\begin{bmatrix}
a_1 \\
a \\
c_1 \\
d_1
\end{bmatrix}\!\!,
\begin{bmatrix}
a_2 \\
b_2 \\
c_2 \\
d_2
\end{bmatrix}\!\!,
\ldots,
\begin{bmatrix}
a_{n-1} \\
b_{n-1} \\
c_{n-1} \\
d_{n-1}
\end{bmatrix},
\begin{bmatrix}
a_n \\
b_n \\
a \\
d_n
\end{bmatrix}
\end{pmatrix}
=
\begin{bmatrix}
a' \\
b' \\
c' \\
d'
\end{bmatrix}
\end{align*}
Note that $b',c'\in a^+$ since $a^+$ absorbs $a$ and that none of $a',b',c',d'$ are isolated. So we have for the term $t'=t(x_1,x_2,\ldots,x_{n-1},x_1)$ that $A'$ and $S$ satisfy that $S$ absorbs $(A')^2$ via $t'$. $S$ is clearly nonempty and symmetric. Therefore we have more than enough to apply Theorem~\ref{thm2} and deduce that the graph $(A',S)$ contains a loop. This loop is a triangle $a',b',c'$ in $(A',R')$. Together with $a$ we get a complete $R$-graph $\m k_4$ on the vertices $\{a,a',b',c'\}$.

So with respect to the graph $(A',R')$ we have all the same assumptions as in the statement of Theorem~\ref{thm3}. Note that since $x^+$ absorbs $x$ with $x^+$ computed relative to $R$, then $x^+$ absorbs $x$ with $x^+$ computed relative to $R'$. This means that we can continue and find a triangle in $a'^+$ (computed with respect to $R'$) and therefore a complete graph with 5 vertices in $(A,R)$. Continuing like this, we get as large a finite clique as we need in $R$, and we need the size $n+1$. Let this clique be on the vertices $\{a,x_1,x_2,\ldots,x_n\}$. Define $y_1=t(a,x_1,\ldots,x_1)$, $y_2=t(x_2,a,x_2,\ldots,x_2)$ and so on, till $y_n=t(x_n,x_n,\ldots,x_n,a)$. Then we claim $[t(y_1,y_2,\ldots,y_n),y_i]^T\in R$ for all $1\leq i\leq n$. We show how this works for $i=2$, you can imagine the analogous arguments for other $i$:
\begin{align*}
t
\begin{pmatrix}
\begin{bmatrix}
t(a,x_1,\ldots,x_1) \\
x_2 
\end{bmatrix}\!\!,
\begin{bmatrix}
t(x_2,a,x_2,\ldots,x_2) \\
a 
\end{bmatrix}\!\!,\ldots,
\begin{bmatrix}
t(x_n,x_n,\ldots,x_n,a) \\
x_2 
\end{bmatrix}
\end{pmatrix}\in R,
\end{align*}
using the fact that $R$ absorbs the diagonal. Finally we prove that there is a loop at $t(y_1,y_2,\ldots,y_n)$ using idempotence.
\end{proof}

Now we turn to Theorem~\ref{thm2}.

\begin{proof}[Proof of Theorem~\ref{thm2} assuming Theorem~\ref{thm3} for $n$]
First note that there exists an odd cycle in $R$. If we just take an element $c\in A$ which is not isolated in $R$ and if $[c,d]^T\in R$, then the argument above the statement of Theorem~\ref{thm2} with $c$ playing the role of $x$ and $d$ playing the role of $y$ proves that $R$ has an odd cycle. As noted before, since $R$ is symmetric and contains an odd cycle, if there were no loops in $R$, then there exists the largest $k$ such that the power $R^{\rightarrow 3^k}$ contains no loops. So, we may replace $R$ by $R^{\rightarrow 3^k}$ and note that $R^{\rightarrow 3^k}$ still absorbs $\Delta_A$, it is still symmetric and nonempty , but it also contains a 3-cycle. If we were to prove that $R^{\rightarrow 3^k}$ contained a loop, we would be done by contradiction. The letter $S$ will from now on stand in place of $R^{\rightarrow 3^k}$.

Let $a\in F$ be such that $a^+$ (with respect to $S$) is nonempty. Then we claim that $a^+$ absorbs $a$. Indeed, let $t$ be the term of arity $n$ modulo which $S$ absorbs $\Delta_A$. Then for any $1\leq i\leq n$ and any $b_1,\ldots,b_{i-1},b_{i+1},\ldots,b_n\in a^+$,
\begin{align*}
t
\begin{pmatrix}
\begin{bmatrix}
a \\
b_1 
\end{bmatrix}\!\!,\ldots,
\begin{bmatrix}
a \\
b_{i-1}
\end{bmatrix}\!\!,
\begin{bmatrix}
a \\
a
\end{bmatrix}\!\!,
\begin{bmatrix}
a \\
b_{i+1}
\end{bmatrix}\!\!,\ldots,
\begin{bmatrix}
a_n \\
b_n 
\end{bmatrix}
\end{pmatrix}.
\end{align*}
Hence, $[a,t(b_1,\ldots,b_{i-1},a,b_{i+1},\ldots,b_n)]^T\!\!\in\! S$, so $t(b_1,\ldots,b_{i-1},a,b_{i+1},\ldots,b_n)\in a^+$, proving the desired absorption.

Finally we apply Theorem~\ref{thm3} to $S$ to derive that the graph $(A,S)$ has a loop.
\end{proof}


\end{document}

