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

\title{On Mal'cev conditions}

\author{Ross Willard}

\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}
\maketitle

\section{Introduction}

When dinosaurs walked the earth we knew all about Mal'cev conditions. And then, in AD 2008, a giant meteor hit the Earth:

\begin{theorem}[M. Siggers, 2008]\label{thm1}
Let $\vr v$ be a locally finite variety. $\vr v$ has a Taylor term iff $\vr v$ omits type $\mathbf{1}$ iff $\vr v$ satisfies certain strong Mal'cev condition.
\end{theorem}

Another meteor came our way this year:

\begin{theorem}[M. Ol\v sak, 2016, see \cite{olshak}]\label{thm2}
Let $\vr v$ be a variety. $\vr v$ has a Taylor term iff $\vr v$ satisfies certain strong Mal'cev condition.
\end{theorem}

Also, a meteorite appeared in 2009:

\begin{theorem}[M. Kozik, 2009, see \cite{KKVW}]\label{thm3}
Let $\vr v$ be a locally finite variety. $\vr v$ is congruence meet-semidistributive iff $\vr v$ omits types $\mathbf{1}$ and $\mathbf{2}$ iff $\vr v$ satisfies certain strong Mal'cev condition.
\end{theorem}

The question naturally arises whether Meteor 2 will also be followed by a meteorite:

\begin{problem}\label{prb1}
In general varieties, is congruence meet-semidistributivity equivalent to a strong Mal'cev condition?
\end{problem}

\section{On $SD(\wedge)$-terms}

An idempotent term $t(x_1,\ldots,x_n)$ is an $SD(\wedge)$-term for a variety $\vr v$ (as defined in \cite{KKVW}) if 
\begin{align*}
\vr v\models t\begin{pmatrix}
\left[\begin{array}{ccccc}
x & & & & \\
 & x & & * & \\
 & & \ddots & & \\
 & A & & \ddots & \\
 & & & & x
\end{array}\right]
\end{pmatrix}
\approx
t\begin{pmatrix}
\left[\begin{array}{ccccc}
y & & & & \\
 & y & & * & \\
 & & \ddots & & \\
 & A & & \ddots & \\
 & & & & y
\end{array}\right]
\end{pmatrix}
\end{align*}
(Each of the entries is $x$ or $y$, the ones below the main diagonal of the left hand matrix match those below the main diagonal of the right hand matrix, while the ones above the main diagonals do not have to match). Similarly, $t$ is a strong $SD(\wedge)$-term for $\vr v$ if
\begin{align*}
\vr v\models t\begin{pmatrix}
\left[\begin{array}{ccccc}
x & & & & \\
 & x & & B & \\
 & & \ddots & & \\
 & A & & \ddots & \\
 & & & & x
\end{array}\right]
\end{pmatrix}
\approx
t\begin{pmatrix}
\left[\begin{array}{ccccc}
y & & & & \\
 & y & & B & \\
 & & \ddots & & \\
 & A & & \ddots & \\
 & & & & y
\end{array}\right]
\end{pmatrix}
\end{align*}
(here all entries of the left hand matrix equal those of the right hand matrix, except those on the main diagonal).

It is known that if a variety has an $SD(\wedge)$-term, or a strong $SD(\wedge)$-term, then this variety is congruence meet-semidistributive. 

The following was proved in \cite{BKS}:
\begin{theorem}[L. Barto, M. Kozik and D. Stanovsky]\label{thm4}
Let $\vr v$ be a locally finite variety. $\vr v$ is congruence meet-semidistributive iff $\vr v$ has a strong $SD(\wedge)$-term (of unknown arity).
\end{theorem}

A natural problem arises:

\begin{problem}\label{prb2}
Does every congruence meet-semidistributive variety have an $SD(\wedge)$-term? A strong $SD(\wedge)$-term?
\end{problem}

Also, the bound on arity in the locally finite case is unknown.

\begin{problem}\label{prb3}
Does there exist $n$ such that every locally finite congruence meet-semidistributive variety has an $SD(\wedge)$-term of arity $n$? How about a strong $SD(\wedge)$-term of arity $n$? 
\end{problem}

Answer to the first part of Problem~\ref{prb3}: Petar Markovi\'c pointed out that the first question has a positive answer with $n=4$. One needs to recall the following theorem:

\begin{theorem}[J. Jovanovi\'c, P. Markovi\'c, R. McKenzie and M. Moore, \cite{JMMM}]\label{thm5}
Let $\vr v$ be a locally finite variety. $\vr v$ is congruence meet-semidistributive iff there exists a $\vr v$-term $p(x,y,z,u)$ such that $\vr v \models p(x,x,x,x)\approx x$ and $\vr v\models p(x,x,x,y)\approx p(x,x,y,x)\approx p(x,y,x,x)\approx p(y,x,x,x)\approx p(x,x,y,y)\approx p(x,y,x,y)$ $\approx p(x,y,y,x)$.
\end{theorem}

Then one needs to rearrange the identities satisfied by $p$ to obtain

\begin{align*}
\vr v\models p\begin{pmatrix}
\left[\begin{array}{cccc}
x & y & x & x\\
x & x & x & y \\
x & x & x & y\\
x & x & y & x
\end{array}\right]
\end{pmatrix}
\approx
p\begin{pmatrix}
\left[\begin{array}{cccc}
y & x & x & x\\
x & y & x & y \\
x & x & y & y\\
x & x & y & y
\end{array}\right]
\end{pmatrix}
\end{align*}

This is an $SD(\wedge)$-term for $\vr v$ which fails to be a strong $SD(\wedge)$-term because of only one position, the position $(1,2)$ in the matrix. So the second half of Problem~\ref{prb3} is still open.

Bounding the arity of $SD(\wedge)$-terms might be interesting regardless of whether they are equivalent to congruence meet-semidistributivity.

\begin{problem}\label{prb4}
Does there exist a natural number $n$ such that in general varieties existence of an $SD(\wedge)$-term implies the existence of an $SD(\wedge)$-term of arity $n$?
\end{problem}

\section{What other conditions might be strong?}

As mentioned, we know that in locally finite varieties the following properties are strong Mal'cev properties: existence of a Taylor term and congruence meet-semidistributivity. A property which may be of interest in this respect is {\em having a weak difference term}. $d$ is a weak difference term for variety $\vr v$ iff for all algebras $\m a\in\vr v$, all congruences $\theta\in \vr a$, if $(x,y)\in\theta$, then $d(x,x,y)[\theta,\theta]y$ and $d(x,y,y)[\theta,\theta]x$. 

\begin{problem}
Is there a Condition (strong Mal'cev) involving a 3-ary $p(x,y,z)$ such that:
\begin{enumerate}
\item If $\vr v$ satisfies Condition, then $p$ is a weak difference term for $\vr v$ and
\item If $\vr v$ is a locally finite variety with a weak difference term then $\vr v$ satisfies Condition.
\end{enumerate}
\end{problem}

Barto and Kozik (~2009) provided a candidate for Condition which is:
\begin{align*}
s(y,x,x)\approx s(x,y,x)\approx t(y,x,x,x)\approx t(x,y,x,x)\approx t(x,x,y,x)\\
s(x,x,y)\approx p(y,x,x)\approx p(x,x,y)\approx t(x,x,x,y)
\end{align*}

\section{Testing the complexity of strong Mal'cev conditions in finite algebras}

In the following three problems, $\m a$ is a finite idempotent algebra which is the input of the problem. The problems are motivated by the results of \cite{FV}.

\begin{problem}
Is minority operation testable in polynomial time?
\end{problem}

\begin{problem}
Is every linear idempotent strong Mal'cev condition testable in polynomial time?
\end{problem}

\begin{problem}
What about idempotent strong Mal'cev conditions not equivalent to linear strong Mal'cev conditions? Can \underline{any} such be tested in polynomial time? In particular, can existence of a semilattice term, or of a 2-semilattice term, be tested in polynomial time?
\end{problem}

In general, non-idempotent finite algebras, the question is whether testing for a condition is Exptime-complete. The following problems are always in Exptime, but might be easier:

\begin{problem}
Is testing for [Mal'cev/Pixley/discrimonator/majority] Exptime-hard?
\end{problem}

For the conditions $CD(n)$, where $n\geq 4$, R. Freese and M. Valeriote proved (see \cite{FV}) that it is Exptime-complete.
\begin{thebibliography}{9}
\bibitem{BKS}
	Barto, L., Kozik, M., Stanovsk\'y, D.: 
	Mal’tsev conditions, lack of absorption, and solvability. 
	Algebra Universalis
	{\bf 74} no. 1 (2015),
	185--206.
	
\bibitem{FV}
	Freese, R., Valeriote, M.:
	On the complexity of some Maltsev conditions,
	Intern. J. Algebra \& Computation {\bf 19} (2009), 41--77.

\bibitem{JMMM} 
Jovanovi\'c, J., Markovi\'c, P., McKenzie, R., Moore, M.: Optimal strong Mal’cev conditions for congruence meet-semidistributivity in locally finite varieties, Algebra Universalis (in press), 21pp.
	
\bibitem{KKVW}
	Kozik, M., Krokhin, A., Valeriote, M., Willard, R.:
	Characterizations of several Maltsev conditions.
	Algebra Universalis
	{\bf 73} no. 3 (2015), 205–-224.

\bibitem{olshak} 
	Ol\v sak, M.:
	The weakest nontrivial idempotent equations,
	preprint, \url{arxiv.org/abs/1609.00531}.

\bibitem{siggers}
	Siggers, M.:
	A strong Mal'cev condition for locally finite varieties omitting the unary type.
	Algebra Universalis
	{\bf 64} no. 1 (2010),
	15--20.
\end{thebibliography}
\end{document}

