%
% file: banach-aaa.tex (based on banach-ostrava.tex)
% purpose: talk at AAA Prague, May 2016
% created: pasha may 24 2016
% modified:
% modification:
%
\documentclass{beamer}
\usepackage{graphicx}
\def\darkblue{black!35!blue}
\setcounter{framenumber}{-1}
\setbeamertemplate{navigation symbols}{}
\setbeamercolor{block title}{fg=\darkblue}
\setbeamercolor{frametitle}{fg=\darkblue}
\title{On extensions of multiary maps to superposition of binary ones}
\author{Pasha Zusmanovich}
\institute{University of Ostrava}
\date{AAA92, Prague \\ May 28, 2016}
%\setbeamertemplate{frametitle}
%{
% \vskip8pt\insertframetitle
%}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\titlepage
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% from now on, display counters
\setbeamertemplate{headline}
{
\vskip2pt\hskip1pt\insertframenumber /\inserttotalframenumber
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{The last question of Banach}
{\color{\darkblue}Andrzej Alexiewicz}'s diary, December 29, 1944:
\medskip
``There exists a nontrivial example of ternary multiplication, which is not
generated by binary multiplication ({\color{\darkblue}Banach}). Can any finite set with ternary
commutative multiplication be extended so that ternary multiplication is
generated by a binary multiplication?''
\bigskip
\begin{center}
\includegraphics[scale=0.42]{alexiewicz.jpg}
\hskip 30pt
\includegraphics[scale=0.22]{banach.jpg}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{What does this question mean?}
Interpretation of ``multiplication'' and ``generated''?
\bigskip
Connection with:
\begin{itemize}
\item History
\item Semigroups
\item Theory of clones
\item Hilbert's 13th problem (superposition of functions)
\item Logic
\item Combinatorics
\item Computer calculations
\item Lie theory
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{First interpretation: semigroups}
``Multiplication'':
ternary semigroup, i.e.
\begin{gather*}
f: X \times X \times X \to X \\
f(f(x,y,z),u,v) = f(x,f(y,z,u),v) = f(x,y,f(z,u,v)) .
\end{gather*}
Commutativity:
$$
f(x_{\sigma(1)}, x_{\sigma(2)}, x_{\sigma(3)}) = f(x_1, x_2, x_3)
$$
for any $\sigma \in S_3$.
\medskip
``Generation'': $f(x,y,z) = (x*y)*z$.
\begin{block}{Theorem ({\L}o\'s 1955, Monk--Sioson 1966)}
Every (commutative) ternary semigroup can be extended to a (commutative) ternary
semigroup given by
$$
f(x,y,z) = (x*y)*z ,
$$
where $*$ is a (commutative) binary semigroup.
\end{block}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Second interpretation: clones}
``Multiplication'': an arbitrary map $X \times X \times X \to X$.
``Generation'': superposition.
\bigskip
\begin{block}{Theorem (Sierpi\'nski 1935, Banach 1935)}
Any countable number of unary maps on an infinite set can be generated by
two maps.
($\Leftrightarrow$ A countable transformation semigroup is $2$-generated).
\end{block}
\bigskip
Generalizations:
\begin{itemize}
\item Other kinds of semigroups, generation ``up to approximation''
({\color{\darkblue} Schreier--Ulam, Jarn\'ik--Knichal}, et al.)
\item Unary $\to$ multiary
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Second interpretation: clones}
\begin{block}{Theorem}
Any countable number of maps of arbitrary arity on a set $X$ can be generated by
one binary map on $X$.
($\Leftrightarrow$ The clone of all maps on $X$ is generated by its binary
fragment).
\end{block}
{\color{\darkblue} Webb 1935}: finite $X$ (generalization of Sheffer's stroke)
$$
p \uparrow q = \neg (p \wedge q)
$$
{\color{\darkblue} {\L}o\'s 1950, Goldstern 2012}: infinite $X$
\begin{block}{Conclusion}
``Banach's claim'' is false in this context.
\end{block}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Interlude}
{\color{\darkblue} Erd\"os} (on another occasion, from a preface to the
\emph{Scottish Book}):
\vskip 5pt
\fontsize{10}{10}\selectfont
``Now it frequently happens in problems of this sort
that the infinite dimensional case is easier to settle than the finite
dimensional analogues. This moved {\color{\darkblue}Ulam} and me to paraphrase a well known maxim
of the American armed forces in WWII: 'The difficult we do immediately, the
impossible takes a little longer', viz: 'The infinite we do immediately, the
finite takes a little longer'.''
\medskip
\includegraphics[scale=0.39]{Stanislaw_Ulam_ID_badge.png}
\hskip 0.5cm
\includegraphics[scale=0.35]{Jerzy_Los_caricature.png}
\hskip 0.5cm
\includegraphics[scale=0.22]{sierpinski.jpg}
{\tiny
\hskip 1cm
Stanis{\l}aw Ulam
\hskip 2.6cm
Jerzy {\L}o\'s
\hskip 2.3cm
Wac{\l}aw Sierpi\'nski
\vskip -3pt
\hskip 0.9cm
(PhD Lvov 1933)
\hskip 1.6cm
(student at Lvov, 1937--1939)
\hskip 0.7cm
(professor at Lvov, 1908--1914)
}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Connection: Hilbert's 13th problem}
\begin{block}{Theorem (P\'olya and Szeg\"o,
\emph{Problems and Theorems in Analysis}, 1925, Problem 119
``Are there actually functions of $3$ variables?'', Sierpi\'nski 1934,1945)}
For any binary bijection $g: X \times X \to X$ on an (infinite) set $X$,
and any ternary map $f: X \times X \times X \to X$, there is a binary map
$h: X \times X \to X$ such that
$$
f(x,y,z) = g(h(x,y),z) .
$$
\end{block}
\begin{block}{Theorem (Kolmogorov 1956, Arnold 1957)}
Any continuous real function in any number of variables can be represented as
superposition of continuous real functions in $2$ variables.
\end{block}
\begin{block}{Questions (Mark Kac--Ulam 1960,1968)}
Extensions of Hilbert's 13th problem: on $\mathbb R^n$, in various classes
(smooth, analytic).
\end{block}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Connection: Logic}
%Completness of multivalued propositional calculi.
{\color{\darkblue}{\L}ukasiewicz}'s $3$-valued logic: ``implication''
{\it {\L}}:
$$\begin{array}{c|ccc}
& 0 & \frac 12 & 1 \\
\hline
0 & 1 & 1 & 1 \\
\frac 12 & \frac 12 & 1 & 1 \\
1 & 0 & \frac 12 & 1
\end{array}$$
and ``negation'' $N$:
$$
0 \mapsto 1, \> {\textstyle \frac 12} \mapsto {\textstyle \frac 12}, \>
1 \mapsto 0 .
$$
\begin{block}{Theorem (S{\l}upecki 1936)}
There are multiary maps on $\{0,\frac 12,1\}$ which are not superposition of
{\it {\L}} and $N$.
\end{block}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{$2\frac{1}{2}$th interpretation: clones with additional structure}
``Multiplication'':
a map $X \times X \times X \to X$ preserving an additional structure on $X$.
``Generation'': composition.
\bigskip
``Banach's claim'' is true for smooth functions. For example:
$$
F(x,y,z) = f(g(h(x,y),z),z)
$$
satisfies the differential equation
$$
\frac{\partial^2 F}{\partial x \partial z} \frac{\partial F}{\partial y}
- \frac{\partial F}{\partial x} \frac{\partial^2 F}{\partial y \partial z} = 0 .
$$
\bigskip
Not suitable for finite $X$.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Third interpretation: operadic-like}
``Multiplication'': an arbitrary map $f: X \times X \times X \to X$.
``Generation'': $f(x,y,z) = (x*y)*z$ or $x*(y*z)$.
\bigskip
For $X$ finite, ``Banach's claim'' is true:
number of ternary maps generated by binary ones $< 2|X|^{|X|^2}$
number of ternary maps $= |X|^{|X|^3}$.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Question(s): number of ternary maps generated by binary ones}
{\small
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline
\shortstack[c]{$|X| = n$ \\ \phantom{a} \\ \phantom{a}} &
\shortstack[c]{number of \\ binary maps \\ $= n^{n^2}$} &
\shortstack[c]{number of maps \\ $(x*y)*z$ \\ \phantom{a} \\ \phantom{a}} &
\shortstack[c]{number of maps \\ $(x*y)*z$ \\ and \\ $x*(y*z)$} &
\shortstack[c]{number of \\ commutative \\ maps \\ $(x*y)*z^{\dagger}$
}
\\ \hline
$1$ & $1$ & $1$ & $1$ & $1$ \\ \hline
$2$ & $16$ & $14$ & $21$ & $5$ \\ \hline
$3$ & $19683$ & $19292$ & $38472$ & $48$ \\ \hline
\end{tabular}
\end{center}
${}^\dagger$ the same number with and without assumption of commutativity of $*$
}
\bigskip
Absent in OEIS!
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Jacobson answers Banach (sort of)}
\begin{block}{Theorem}
Any ternary map $f: X \times X \times X \to X$ on a finite $X$ can be extended
to a ternary map generated by a binary map.
\end{block}
\begin{block}{Proof (trivial)}
$Y = X \cup (X \times X) .$
$x * y = (x,y); \quad (x,y) * z = f(x,y,z).$
\end{block}
\vskip 20pt
Modification of this: commutative version,
result of {\L}o\'s and Monk-Sioson,
generalization to $n$-ary maps, etc., etc.
can be established using {\color{\darkblue}Jacobson}'s ideas about
Lie and Jordan triple systems (1949).
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% don't include this final frame into the total count;
% TeX twice for that!
\newcounter{finalframe}
\setcounter{finalframe}{\value{framenumber}}
\setbeamertemplate{headline}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{center}
Thanks to:
\\
Martin Goldstern, Kateryna Pavlyk, Witold Wi\c{e}s{\l}aw, Jan Wole\'nski
\vskip 30 pt
Based on arXiv:1408.2982 (to appear in Expos. Math.)
\vskip 30pt
{\Huge
That's all. Thank you.
}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setcounter{framenumber}{\value{finalframe}}
\end{document}
% eof