%\documentclass[compress]{beamer}   % {{{
\documentclass[compress,handout]{beamer}
\usepackage{amsfonts, amsmath, amssymb, amsthm, mathtools}
\usepackage{tikz, float, tabu, multirow, cancel}
\usetikzlibrary{calc,decorations.markings,matrix,arrows,positioning}

% color settings
\mode<presentation>{
\usetheme{Madrid}
\usecolortheme{default}
\beamertemplatenavigationsymbolsempty
}
\setbeamercolor{alerted text}{fg=blue}
\setbeamertemplate{items}[circle]
\setbeamercovered{transparent}

% mathbb and mathcal symbols
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\V}{\mathcal{V}}
\newcommand{\A}{\mathbb{A}}
\newcommand{\m}[1]{\mathbb{#1}}    % for models
\newcommand{\cl}[1]{\mathcal{#1}}  % for classes

% theorems and similar environments
\theoremstyle{plain} \newtheorem{thm}{Theorem}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\theoremstyle{definition} \newtheorem{defn}[thm]{Definition}
\theoremstyle{remark} \newtheorem*{rk}{Remark}
\theoremstyle{plain} \newtheorem*{Q}{Question}
\newcommand{\Case}[1]{\smallskip \textbf{Case #1:}}

% custom commands
\DeclareMathOperator{\Cg}{\text{Cg}}
\DeclareMathOperator{\Sg}{\text{Sg}}
\DeclareMathOperator{\Con}{\text{Con}}
\DeclareMathOperator{\Clo}{\text{Clo}}
\DeclareMathOperator{\Rel}{\text{Rel}}
\DeclareMathOperator{\diag}{\text{diag}}
\newcommand{\pmat}[1]{\ensuremath{ \begin{pmatrix} #1 \end{pmatrix} }}
\newcommand{\bmat}[1]{\ensuremath{ \begin{bmatrix} #1 \end{bmatrix} }}

% symbol overrides
\let\emph\textbf
\renewcommand{\phi}{\varphi}
\renewcommand{\epsilon}{\varepsilon}

% document specific stuff

%============================================================================}}}

\begin{document}
% title page {{{
\title{Absorption and directed J\'{o}nsson terms}
\author{Matthew Moore}
\institute[VU]{Vanderbilt University}
\date[2015-06-11]{June 11, 2015}

\begin{frame}
\titlepage
\end{frame}
%============================================================================}}}

\begin{frame} % joint work with... {{{
This is joint work with
\begin{itemize}
  \bigskip
  \item Alexandr Kazda, Institute of Science and Technology
  \bigskip
  \item Marcin Kozik, Jagiellonian University
  \bigskip
  \item Ralph McKenzie, Vanderbilt University
\end{itemize}
\end{frame}
%============================================================================}}}
\begin{frame} \frametitle{Congruence distributive algebras}   % {{{
$\V$ is \emph{congruence distributive (CD)} if for every $\A\in \V$ the
lattice of congruences of $\A$ is a distributive lattice.

\vfill \pause

$\Leftrightarrow$ no
\begin{tikzpicture} % M3 {{{
  [baseline=(mid2.south), scale=0.3, every node/.style={transform shape}]
  \node (top) {$\circ$};
  \node [below left=of top] (mid1) {$\circ$};
  \node [below=of top] (mid2) {$\circ$};
  \node [below right=of top] (mid3) {$\circ$};
  \node [below=of mid2] (bottom) {$\circ$};
  \draw (top) -- (mid1) -- (bottom) (top) -- (mid2) -- (bottom)
    (top) -- (mid3) -- (bottom);
\end{tikzpicture}  % }}}
or
\begin{tikzpicture} % N5 {{{
  [baseline=(mid2.south), scale=0.3, every node/.style={transform shape}]
  \node (top) {$\circ$};
  \node [below right=of top] (a1) {$\circ$};
  \node [below left=of top] (temp1) {};
  \node at ($(top)!0.6!(a1)$) (temp2) {};
  \node at (temp2-|temp1) (c) {$\circ$};
  \node [below left= of a1] (bottom) {$\circ$};
  \node at ($(bottom)!0.6!(a1)$) (temp2) {};
  \node at (temp2-|temp1) (a2) {$\circ$};
  \draw (top) -- (a1) -- (bottom) (top) -- (c) -- (a2) -- (bottom);
\end{tikzpicture}  % }}}
in congruence lattices

\vfill \pause

$\Leftrightarrow$ there are \emph{J\'{o}nsson terms}: $J_0, \ldots,
J_{2n+1}$ such that $\V$ models
\begin{gather*}
  J_1(x,x,y) = x, \qquad
    J_{2n+1}(x,y,y) = y, \qquad
    J_i(x,y,x) = x \\
  J_{2i+1}(x,y,y) = J_{2i+2}(x,y,y), \qquad
    J_{2i}(x,x,y) = J_{2i+1}(x,x,y).
\end{gather*}

\vfill \pause

\& locally finite $\Rightarrow$ $\V$ has finite residual bound and is
finitely axiomatizable.
\end{frame}
%============================================================================}}}
\begin{frame} \frametitle{J\'{o}nsson terms}   % {{{
\begin{gather*}
  J_1(x,x,y) = x, \qquad
    J_{2n+1}(x,y,y) = y, \qquad
    J_i(x,y,x) = x \\
  J_{2i+1}(x,y,y) = J_{2i+2}(x,y,y), \qquad
    J_{2i}(x,x,y) = J_{2i+1}(x,x,y).
\end{gather*}

\vfill \pause

If $J_i(x,x,y) \to J_i(x,y,y)$, then \pause
% undirected Jonsson picture {{{
\begin{center} \begin{tikzpicture} [font = \scriptsize, node distance=2em]
  \tikzstyle{multiline} = [ node distance=0, align=left, font=\tiny ]

  \node (x) {$x$};
  \node [multiline, above=of x] { $x = J_1(x,x,y)$ };

  \pause

  \node [below right=of x] (a1) {$a_1$};
  \node [multiline, below=of a1] 
    { $a_1 = J_1(x,y,y)$ \\ 
      \hspace{1.3em}$= J_2(x,y,y)$ };
  \draw[->] (x) -- (a1);

  \pause

  \node [above right=of a1] (a2) {$a_2$};
  \node [multiline, above=of a2] 
    { $a_2 = J_2(x,x,y)$ \\ 
      \hspace{1.3em}$= J_3(x,x,y)$ };
  \draw[->] (a2) -- (a1);

  \pause

  \node [below right=of a2] (a3) {$a_3$};
  \node [multiline, below=of a3] 
    { $a_3 = J_3(x,y,y)$ \\ 
      \hspace{1.3em}$= J_4(x,y,y)$ };
  \draw[->] (a2) -- (a3);

  \pause

  \node [above right=of a3] (a4) {};
  \draw[->] (a4) -- (a3);
  \node at ($(a3)!0.5!(a4)$) (temp1) {};
  \node [right=of temp1, yshift=0.5em] {$\dots$};
  \node [right=5em of a3] (a2n-1) {};
  \node [above right=of a2n-1] (a2n) {$a_{2n}$};
  \node [multiline, above=of a2n] 
    { $a_{2n} = J_{2n}(x,x,y)$ \\ 
      \hspace{1.8em}$= J_{2n+1}(x,x,y)$ };
  \draw[->] (a2n) -- (a2n-1);

  \pause

  \node [below right=of a2n] (y) {$y$};
  \node [multiline, below=of y] { $y = J_{2n+1}(x,y,y)$ };
  \draw[->] (a2n) -- (y);
\end{tikzpicture} \end{center}  % }}}
\end{frame}
%============================================================================}}}
\begin{frame} \frametitle{Absorption}   % {{{
A \emph{near unanimity (NU) term} for a variety $\V$ is an idempotent term
$t(\cdots)$ such that
\[
  \V\models t(y,x,\dots,x) \approx t(x,y,\dots,x) \approx t(x,\dots,x,y)
    \approx x.
\]
\vspace{-2.5em} \pause
\begin{align*}
  \exists \text{ NU term} 
  \pause
  & \Leftrightarrow \text{CD, every finite algebra is finitely related} \\
  \pause
  & \Leftrightarrow \text{CD, finite algebras are dualizable}
\end{align*}

\vfill \pause

\begin{defn}
For algebra $\A$ with subalgebra $\m{B}\leq \A$, $\m{B}$ \emph{absorbs $\A$}
(written $\m{B}\trianglelefteq \A$) if there is an idempotent term
$t(\cdots)$ such that for all $i$,
\vspace{-1em}
\[
  t(B,\dots,B,\stackrel{i}{\widehat{A}},B,\dots, B) \subseteq B
\]
\end{defn}
\end{frame}
%============================================================================}}}
\begin{frame} \frametitle{Absorption theorems}   % {{{
\begin{thm}[Barto, Kozik 2012]
Let $\V$ be a locally finite idempotent variety. TFAE
\begin{itemize}
  \item $\V$ is a Taylor variety,
  \item for all finite $\A,\m{B}\in \V$ and all linked $\m{R}\leq_{sd}
    \A\times \m{B}$,
    \begin{itemize}
      \item $\m{R} = \A\times \m{B}$, or
      \item $\A$ has a proper absorbing subuniverse, or
      \item $\m{B}$ has a proper absorbing subuniverse.
    \end{itemize}
\end{itemize}
\end{thm}

\vfill

\begin{thm}[Barto, Kozik, Willard 2012]
Let $\A$ be a finite algebra and $\m{R}\trianglelefteq \m{S} \leq \A^n$ such
that $\m{R}\leq_{sd} \A^n$ and $\Delta_n\leq \m{S}$. Then $\Delta_n\cap R
\neq \emptyset$.
\end{thm}
\end{frame}
%============================================================================}}}
\begin{frame} \frametitle{From near unanimity to directed J\'{o}nsson terms}   % {{{
Let $t(\cdots)$ be an $n$-ary near unanimity term for $\A$:
\[
  \A\models t(y,x,\dots,x) \approx t(x,y,\dots) \approx t(x,\dots,x,y)
    \approx x.
\]

\pause

Define terms $D_1,\dots,D_n$ by
\begin{align*}
  & D_1(x,y,z) = t(x,\dots,x,y), \qquad 
    D_n(x,y,z) = t(y,z,\dots,z), \\
  & D_i(x,y,z) = t(x,\dots,x,y,z,\dots,z) \qquad 
    y \text{ in the $(n-i+1)th$ place}.
\end{align*}

\vfill \pause

It's not hard to see that these satisfy the \emph{directed J\'{o}nsson
identities}:
\begin{gather*}
  D_1(x,x,y) = x, \qquad
    D_n(x,y,y) = y, \\
  D_i(x,y,y) = D_{i+1}(x,x,y), \qquad
    D_i(x,y,x) = x.
\end{gather*}
\pause These identities imply CD.

\vfill \pause

% NU, DJ, J implication diagram {{{
\begin{center} \begin{tikzpicture} [ font=\scriptsize ] 
  \tikzstyle{implication} = [-implies,double equal sign distance];
  \tikzstyle{double_implication} = [implies-implies,double equal sign distance];
 
  \node (NU) {NU};
  \node [right=of NU] (DJ) {dir. J\'{o}nsson};
  \node [right=of DJ] (CD) {CD};
  \node [above=1.25em of CD] (J)  {J\'{o}nsson};
  \node [below=0.25em of CD] (CD_FR) {CD, fin. related};
  \node [below=0.25em of NU,text=white] (NU_below) {NU};

  \draw[implication] (NU) -- (DJ);
  \draw[implication] (DJ) -- (CD);
  \draw[double_implication] (CD) -- (J);
  \draw[double_implication] (CD_FR) -- (NU_below);
\end{tikzpicture} \end{center}   % }}}
\end{frame}
%============================================================================}}}
\begin{frame} \frametitle{Directed J\'{o}nsson terms}   % {{{
\begin{gather*}
  D_1(x,x,y) = x, \qquad
    D_n(x,y,y) = y, \\
  D_i(x,y,y) = D_{i+1}(x,x,y), \qquad
  D_i(x,y,x) = x
\end{gather*}

\vfill \pause

If $D_i(x,x,y) \to D_i(x,y,y)$, then \pause
% directed Jonsson picture {{{
\begin{center} \begin{tikzpicture} [font = \scriptsize, node distance=2em]
  \tikzstyle{multiline} = [ node distance=0, align=left, font=\tiny ]

  \node (x) {$x$};
  \node [multiline, above=of x] { $x = D_1(x,x,y)$ };

  \pause

  \node [below right=of x] (a1) {$a_1$};
  \node [multiline, below=of a1] 
    { $a_1 = D_1(x,y,y)$ \\ 
      \hspace{1.3em}$= D_2(x,x,y)$ };
  \draw[->] (x) -- (a1);

  \pause

  \node [above right=of a1] (a2) {$a_2$};
  \node [multiline, above=of a2] 
    { $a_2 = D_2(x,y,y)$ \\ 
      \hspace{1.3em}$= D_3(x,x,y)$ };
  \draw[->] (a1) -- (a2);

  \pause

  \node [below right=of a2] (a3) {$a_3$};
  \node [multiline, below=of a3] 
    { $a_3 = D_3(x,y,y)$ \\ 
      \hspace{1.3em}$= D_4(x,x,y)$ };
  \draw[->] (a2) -- (a3);

  \pause

  \node [above right=of a3] (a4) {};
  \node at ($(a3)!0.5!(a4)$) (temp1) {};
  \node [right=of temp1, yshift=0.5em] {$\dots$};
  \draw[->] (a3) -- (a4);
  \node [right=5em of a3] (an-1) {};
  \node [above right=of an-1] (an) {$a_n$};
  \node [multiline, above=of an] 
    { $a_n = D_n(x,y,y)$ \\ 
      \hspace{1.3em}$= D_{n+1}(x,x,y)$ };
  \draw[->] (an-1) -- (an);

  \pause

  \node [below right=of an] (y) {$y$};
  \node [multiline, below=of y] { $y = D_{n}(x,y,y)$ };
  \draw[->] (an) -- (y);
\end{tikzpicture} \end{center}  % }}}
\end{frame}
%============================================================================}}}
\begin{frame} \frametitle{From absorption to weak directed J\'{o}nsson terms} % {{{
Suppose that $\m{B}\trianglelefteq \A$ via the $n$-ary term $t(\cdots)$ and
define
\begin{align*}
  & D_1(x,y,z) = t(x,\dots,x,y), \qquad 
    D_n(x,y,z) = t(y,z,\dots,z), \\
  & D_i(x,y,z) = t(x,\dots,x,y,z,\dots,z) \qquad 
    y \text{ in the $(n-i+1)th$ place}.
\end{align*}

\vfill \pause

These satisfy the \emph{weak directed J\'{o}nsson identities}:
\begin{gather*}
  D_1(x,x,y) = x, \qquad
    D_n(x,y,y) = y, \\
  D_i(x,y,y) = D_{i+1}(x,x,y), \qquad
    \text{\xcancel{$D_i(x,y,x) = x$}},
\end{gather*}
\end{frame}
%============================================================================}}}
\begin{frame} \frametitle{J\'{o}nsson absorption}   % {{{
$\m{B}\trianglelefteq \A$ via $t(\cdots)$, from which the $D_i$ were
defined.
\begin{gather*}
  D_1(x,x,y) = x, \qquad
    D_n(x,y,y) = y, \\
  D_i(x,y,y) = D_{i+1}(x,x,y), \qquad
    D_i(B,A,B) \subseteq B,
\end{gather*}
\pause If we have terms $D_i$ and $\m{B}\leq \A$ satisfying these, we say
$\m{B}$ \emph{directed J\'{o}nsson absorbs} $\A$ and write
$\m{B}\triangleleft_{DJ} \A$.

\vfill \pause

Similarly, replacing $J_i(x,y,x) = x$ with $J_i(B,A,B) \subseteq B$ in the
J\'{o}nsson identities, we obtain \emph{J\'{o}nsson absorption}, written
$\m{B}\triangleleft_J \A$.

\vfill \pause

$\A$ has J\'{o}nsson terms if and only if $\{a\} \triangleleft_J \A$ for all
$a\in A$.

\vfill \pause

$\A$ has directed J\'{o}nsson terms if and only if $\{a\} \triangleleft_{DJ}
\A$ for all $a\in A$.
\end{frame}
%============================================================================}}}
\begin{frame} \frametitle{Directed J\'{o}nsson terms in a finite algebra} % {{{
\begin{thm}
Suppose that $\A$ is \emph{finite} and $\m{E},\m{F}\leq \A^2$ are preorders
(i.e. reflexive and transitive). If $\m{E}\triangleleft_J \m{F}$ then $\m{E}
= \m{F}$.
\end{thm}

\vfill \pause

\emph{How to get directed J\'{o}nsson terms (finite $\A$):} Suppose $\V$ is
  CD.
\pause \begin{itemize}[<+->]
  \item $\A$ is finite, so $\V(\A)$ is locally finite.
  \item $\m{F}_2 = \m{F}(x,z)$ and $\m{F}_3 = \m{F}(x,y,z)$ are finite.
  \item Let $\mathcal{G} = \{ t(x,y,z)\in \m{F}_3 \mid t(x,z,x) = x \}$,
    $F = \big\{ \big( t(x,x,z), t(x,z,z) \big) \mid t\in \m{F}_3 \big\}$,
    $E = \big\{ \big( t(x,x,z),t(x,z,z) \big) \mid t\in \mathcal{G} \big\}$.
  \item Let $\to$ and $\dashrightarrow$ be the transitive closures of $E$
    and $F$, resp.
  \item $E$, $F$, $\to$, and $\dashrightarrow$ are subalgebras of $\m{F}_2$
    and $\to$, $\dashrightarrow$ are preorders.
  \item The J\'{o}nsson terms for $\V$ witness $\m{E}\triangleleft_J \m{F}$,
    so $\to \triangleleft_J \dashrightarrow$, so $\to = \dashrightarrow$.
  \item $(x,z)\in F$, so $x\to z$, so there are witnessing $E$-related terms
    $D_i\in \mathcal{G}$.
  \item These are the directed J\'{o}nsson terms!
\end{itemize}
\end{frame}
%============================================================================}}}
\begin{frame} \frametitle{$x\to z\dots$} % {{{ \vspace{-3em}
\vspace{-3em}
\begin{align*}
  \mathcal{G} & = \big\{ t(x,y,z)\in \m{F}_3 \mid t(x,z,x) = x \big\}, \\
  E & = \big\{ \big( t(x,x,z),t(x,z,z) \big) \mid t\in \mathcal{G} \big\}, \\
  \to & = \text{transitive closure of } E
\end{align*}

\vfill

$x\to z$

\vfill \pause

There is a sequence in $E$ witnessing $x\to z$: \pause
% E-chain picture {{{
\begin{center} \begin{tikzpicture} [ font=\scriptsize ]
  \node (x) {$x$};

  \pause

  \node[below=0.25em of x, anchor=center, rotate=90] {$=$};
  \node[below=0.5em of x, xshift=3em] (D1) {$(D_1(x,x,z),D_1(x,z,z))$};

  \pause

  \node[above=0.25em of D1, xshift=2.4em, anchor=center, rotate=90] {$=$};
  \node[above=0.5em of D1, xshift=5.5em] (D2) {$(D_2(x,x,z),D_2(x,z,z))$};

  \pause

  \node[below=0.25em of D2, xshift=2.4em, anchor=center, rotate=90] {$=$};
  \node[below=0.5em of D2, xshift=5.5em] (D3) {$(D_3(x,x,z),D_3(x,z,z))$};

  \pause

  \node at ($(D2)!0.5!(D3)$) (temp1) {};
  \node [right=1em of D3] (temp2) {};
  \node at (temp1-|temp2) (dots) {$\cdots$};
  \node [right=0.25em of dots] (temp1) {};
  \node at (temp1|-D2) (Dn) [anchor=west] (Dn) {$(D_n(x,x,z),D_n(x,z,z))$};

  \pause

  \node[below=0.25em of Dn, xshift=2.4em, anchor=center, rotate=90] {$=$};
  \node[below=0.5em of Dn, xshift=2.4em] (z) {$z$};
\end{tikzpicture} \end{center}  % }}}
\pause Every pair comes from $\mathcal{G}$, so $D_i(x,z,x) = x$.

\vfill \pause

These are the directed J\'{o}nsson terms!
\end{frame}
%============================================================================}}}
\begin{frame} \frametitle{Directed J\'{o}nsson terms in general}   % {{{
\begin{thm}
Let $\V$ be a variety and $\mathcal{J}$ a system of weak J\'{o}nsson terms.
Then there is a system of weak directed J\'{o}nsson terms $\mathcal{D}$ such
that for all $\A, \m{B}\in \V$ if $\m{B}\triangleleft_J \A$ via
$\mathcal{J}$ then $\m{B}\triangleleft_{DJ} \m{A}$ via $\mathcal{D}$.
\end{thm}

\vfill \pause

\emph{How to get directed J\'{o}nsson terms:} \pause
\begin{itemize}[<+->]
  \item Let $\V$ be a variety with J\'{o}nsson terms $\mathcal{J}$ and let
    $\m{F}_3^{id}$ be the idempotent reduct of $\m{F}(x,y,z)$.
  \item $\mathcal{J}$ are J\'{o}nsson terms for $\V$, so
    $\{x\}\triangleleft_J \m{F}^{id}_3$. 
  \item Thus there are directed J\'{o}nsson terms $\mathcal{D}$ such that
    $\{x\}\triangleleft_{DJ} \m{F}^{id}_3$.
  \item The elements of $\mathcal{D}$ are weak directed J\'{o}nsson terms
    plus the identities $D_i(x,y,x) = x$.
  \item Thus $\m{F}^{id}_3$ has directed J\'{o}nsson terms.
\end{itemize}
\end{frame}
%============================================================================}}}
\begin{frame} \frametitle{J\'{o}nsson if and only if directed J\'{o}nsson}   % {{{
\begin{thm}
Let $\V$ be any variety. $\V$ is congruence distributive if and only if it
has directed J\'{o}nsson terms.
\end{thm}

\vfill

% NU, DJ, J implication diagram {{{
\begin{center} \begin{tikzpicture} [ font=\scriptsize ] 
  \tikzstyle{implication} = [-implies,double equal sign distance];
  \tikzstyle{double_implication} = [implies-implies,double equal sign distance];
 
  \node (NU) {NU};
  \node [right=of NU] (DJ) {dir. J\'{o}nsson};
  \node [right=of DJ] (CD) {CD};
  \node [above=1.25em of CD] (J)  {J\'{o}nsson};

  \draw[implication] (NU) -- (DJ);
  \draw[implication] (DJ) -- (CD);
  \draw[double_implication] (CD) -- (J);
  \draw[implication,blue] (J) -- node[auto,swap]{for all $\V$} (DJ);
\end{tikzpicture} \end{center}   % }}}
\end{frame}
%============================================================================}}}
\begin{frame} \frametitle{New Maltsev conditions}   % {{{
We can prove similar absorption theorems for (directed) Gumm terms and
Pixley terms.

\medskip \pause

\begin{thm}
Let $\V$ be any variety. \pause
\begin{itemize}[<+->]
  \item $\V$ is congruence distributive iff it has directed J\'{o}nsson
    terms.
  \item For any integer $k\geq 1$, a $\V$ is congruence distributive and has
    $(k+1)$-permuting congruences iff it has Pixley terms of length $k$.
  \item $\V$ is congruence modular iff it has directed Gumm terms.
\end{itemize}
\end{thm}

\vfill

\only<6->{ \centering \textbf{Thank you.} }
\end{frame}
%============================================================================}}}
\end{document}
