\documentclass{au}
\usepackage[english,polish]{babel}
\newtheorem{problem}{Problem}
\setlength{\mathsurround}{1.67pt}
\def\r#1{{\rm #1}}
\newcommand{\who}[3][Discussed]{\bigskip\noindent{#1
by {\bf #2 ({\tt #3}):}}\medskip\par}
\newcommand{\waiting}{\par (Write-up not yet received.)}
\begin{document}
\selectlanguage{english}
\subjclass[2000] {Primary: 08-02 Secondary: 55-02, 06-02, 03-02}
\keywords{open problems in general algebra}
\title[Problem List]
{Problem List\\[.1in]
{\small From Algebras, Lattices and Varieties: a Conference in Honor of \\
Walter \mbox{Taylor},
held at the University of Colorado, 15--18 August, 2004}}
\maketitle
\vspace{-14em}
\begin{center}
\texttt{
This is the final preprint version of a problem list which
appeared \\[.3em]at Algebra Universalis 55 (2006) 509-526.
The published version is\\[.3em] \mbox{accessible to subscribers
at \ http://dx.doi.org/10.1007/s00012-006-2020-y .}}
\end{center}
\vspace{9em}
Most of these problems were discussed at a Problems Session
at the end of the conference.
Though Walter did not pose any problems at the time, he
subsequently discovered and contributed to this
collection a treasure trove of ten problems that
he had lectured on, but not published, 18 years earlier.
These appear, with his notes on their status as of 2005,
at the end of the list
as Problems~\ref{WT1eqcpdlat}--\ref{WT10univalg}.
$${-}\ {-}\ {-}\ {-}$$
\who{George Bergman}{gbergman@math.berkeley.edu}
\begin{problem}[Hotzel \cite{Hotzel}]\label{monoidACC}
If $M$ is a monoid such that the lattice of left congruences on $M$
has ascending chain condition, must $M$ be finitely generated?
\end{problem}
Hotzel asks this for semigroups and right congruences;
his and the above version are equivalent.
{\em Left congruences} on $M$ are equivalence relations
closed under all left translations;
these are thus equivalent to congruences
on the free left $M\!$-set on one generator.
When $M$ is a group, any left congruence is the decomposition of $M$
into the left cosets of some subgroup, so the lattice of left
congruences is isomorphic to the subgroup lattice.
Thus, finite generation of a group is equivalent to the
compactness of the greatest element in the lattice of left congruences,
while ACC on that lattice
is the stronger condition that all its elements be compact.
On a general monoid, there are several interesting sorts
of left congruences.
If a left congruence $C$ is generated by pairs of the
form $(a,1),$ then $C$ is determined by $M_C=\{a\in M\mid (a,1)\in C\}.$
The subsets $M_C\subseteq M$ that arise in this way are precisely the
submonoids closed under left division, i.e., such that if
$ab$ and $a$ belong to the submonoid, so does $b.$
Hence compactness of the greatest element of the left congruence lattice
is equivalent to finite generation of $M$ as a
{\em left-division-closed} submonoid of itself.
This can hold without $M$ being finitely generated as a monoid.
E.g., if $M$ is the additive monoid of nonnegative elements of
$\mathbb{Z\times Z}$
under lexicographic order, it is generated in this sense by
$(0,1)$ and $(1,0)$, but requires $(0,1)$ and infinitely many of the
elements $(1,-n)$ to generate it as a monoid.
A {\em Rees left congruence} $C$ is the relation one gets
by taking a nonempty left ideal $I\subseteq M$ (a subset closed under
all left translations) and making it one congruence class
(a ``zero element'' of the left $M\!$-set $X/C),$
while making all other congruence classes singletons.
In the submonoid of $\mathbb{Z\times Z}$ noted above, the principal
ideals generated by $(1,0),\ (1,-1),\ (1,-2), \dots$ form a strictly
ascending chain, so the Rees left congruences do not satisfy ACC.
Finally, for every $c\in M,$ the relation $c^\perp =
\{(a,b)\mid ac=bc\}$ is a left congruence.
Kozhukhov~\cite{Kozhukhov} obtains several results toward an
affirmative answer to Problem~\ref{monoidACC};
in particular, he shows that ACC on right {\em and} left
congruences together do imply finite generation.
(The non-specialist should read~\cite{Kozhukhov}
with~\cite{C+P} in hand for notation and terminology.)
An appealing approach to Problem~\ref{monoidACC} is the following.
Note that every left congruence $C$ on $M$ contains a greatest
{\em two-sided congruence} (congruence in the variety of monoids)
$C^\mathrm{int}.$
Now if $M$ gave a negative answer to the
question, then by ACC on left congruences it would have a
left congruence $C$ maximal for the property that $M/C^\mathrm{int}$
was non-finitely-generated.
Thus, adjoining any new pair to $C$ would yield a congruence
$C'$ such that the action of $M$ on $M/C'$ was essentially
the action of some finitely generated submonoid of $M;$
a situation from which one might be able to get a contradiction, or
ideas for constructing an example.
Since monoids are essentially unary clones, one might ask more
generally whether an arbitrary
clone for which every free object on finitely many generators
has ACC on congruences has to be finitely generated.
That this is not so is shown by the example of the clone of operations
of $k\!$-vector-spaces, for $k$ a fixed infinite field.
\begin{problem}[Wasserman \cite{DW}]\label{Lat-DW}
Is there a nontrivial lattice that is not generated by the union
of two proper sublattices?
\end{problem}
Wasserman notes that such a lattice would have no minimal
generating set, would admit no map onto a nontrivial finite lattice,
and would have no maximal proper sublattice.
An example with all three of these properties that is
nonetheless not of the desired sort may be obtained by taking an
infinite binary tree with root at the top, and throwing in a
bottom element to make it a lattice.
It was noted at the conference that a J\'onsson lattice would
yield an affirmative answer to Problem~\ref{Lat-DW}.
J\'onsson lattices of regular cardinality are known not to
exist~\cite{Whaley}; the singular-cardinality case is open.
Freese, Hyndman and Nation~\cite{FHN-join} provide conditions under
which the answer to Problem~\ref{Lat-DW} is negative. In particular, if $L$
is a finitely atomistic semimodular lattice or an atomistic modular
complete lattice then $L$ is generated by the union of two proper
sublattices.
\begin{thebibliography}{1}
\bibitem{C+P}
A. H. Clifford and G. B. Preston,
{\it The algebraic theory of semigroups, v.\,I.,} Mathematical
Surveys No. 7, American Mathematical Society, 1961, xv$+$224~pp.
%MR{\bf 24}\#A2627.
\bibitem{FHN-join}
Ralph Freese, Jennifer Hyndman, and J. B. Nation,
{\it Lattices that are the join of two proper sublattices}, 12\,pp.,
manuscript,
http://www.math.hawaii.edu/$\!\sim\!$jb/sublatt.pdf\,.
\bibitem{Hotzel}
E. Hotzel, {\it On semigroups with maximal conditions,}
Semigroup Forum {\bf 11} (1975/76), 337--362.
%MR{\bf 52}\#10921.
\bibitem{Kozhukhov}
I. B. Kozhukhov, {\it Semigroups with certain conditions on
congruences,} J. Math. Sci. (N.Y.) {\bf 114} (2003), 1119--1126.
%MR{\bf 2004b}:20087.
\bibitem{DW}
David Wasserman,
{\it Is there a nontrivial lattice that is not generated by the union
of two proper sublattices?} 1\,p., manuscript,
http://home.earthlink.net/$\!\sim\!$dwasserm/Sublattice.pdf\,.
\bibitem{Whaley}
Thomas P. Whaley,
{\it Large sublattices of a lattice,}
Pacific J. Math. {\bf 28} (1969) 477--484.
%MR{\bf 39}\#2670.
\end{thebibliography}
\who{Stan Burris}{snburris@thoralf.uwaterloo.ca}
Given a class $\mathcal A$ of algebras let $a(n)$ be the number
of algebras in $\mathcal A$ that have size $n$ (counting up to
isomorphism).
Walter Taylor called the function $a(n)$ the {\em fine spectrum} of
$\mathcal A$ in the case that ${\mathcal A}$ is a variety.
In the study of asymptotic density in [2] we require
that the finite members of ${\mathcal A}$ have the Unique Factorization
Property (UFP). Then with $p(n)$ the count function for the
indecomposable members of ${\mathcal A}$ we have
\[
\sum_{n\ge 1} a(n)n^{-x}\ =\ %
\prod_{n\ge 2} \big(1-n^{-x}\big)^{-p(n)}.
\]
We assume in all questions below: {\bf the finite members of
$\mathcal A$ have the UFP.}\\
An important condition in the study of logical limit laws is that
the function $A(x) = \sum_{n \le x} a(n)$ have
{\em regular variation (at infinity of index $\alpha$)},
which means
\[
\lim_{t\rightarrow \infty} \frac{A(tx)}{A(t)}\ =\ x^\alpha\ .
\]
{\em Recall the UFP assumption:}\\
\begin{problem}\label{reg-var}
What can we say about a \r(locally finite\r) variety
${\mathcal A}$ when $A(x)$ has regular variation?
\end{problem}
Jason Bell [1] proved that if $P(x)=\sum_{n\le x} p(n)$
has polylog growth, that is, $P(x)={\rm O}\big((\log x)^c\big)$,
then ${\mathcal A}$ has a first-order 0--1 law.
\begin{problem}\label{Bell-cdns}
If ${\mathcal A}$ is a \r(locally finite\r) variety of algebras,
what do Bell's conditions say about ${\mathcal A}$?\\
\end{problem}
In~\cite{Bell}, p.~228, it is proved that if $A(x) \sim Cx^\alpha$ then
${\mathcal A}$ has a first-order limit law.
\begin{problem}\label{x^alpha}
If ${\mathcal A}$ is a \r(locally finite\r) variety of algebras
with $A(x) \sim Cx^\alpha$, what can we say about ${\mathcal A}$?\\
\end{problem}
\begin{thebibliography}{1}
\bibitem{Bell}
Jason P.~Bell, {\em Sufficient conditions for zero-one laws.}
Trans. Amer. Math. Soc. {\bf 354}
(2002), no. 2, 613--630.
\bibitem{Burris}
Stanley N.~Burris, {\it Number Theoretic Density
and Logical Limit Laws.} Mathematical Surveys and Monographs,
{\bf 86}, Amer. Math. Soc., Providence, 2001. xx+289 pages.
\end{thebibliography}
\who{Brian Davey}{b.davey@latrobe.edu.au}
Here are two old problems that are still of interest.
Some progress has been made on the second.
None has been made on the first.
\begin{problem}\label{decide-dualbl}
Is dualisability of a finite algebra of finite type
decidable?
\end{problem}
\begin{problem}\label{full_vs_strong}
Does full dualisability imply strong dualisability?
\end{problem}
For details see:
\begin{thebibliography}{1}
\bibitem{Clark+Davey}
D.M. Clark and B.A. Davey,
\textit{Natural Dualities for the Working Algebraist},
Cambridge Studies in Advanced Mathematics, \textbf{57}, Cambridge
University Press, Cambridge, 1998. xii+356 pages.
\end{thebibliography}
\who{Klaus Denecke}{kdenecke@rz.uni-potsdam.de}
Let $\tau = (n_i)_{i \in I}$ be a type of algebras, indexed by a
set $I$, with operation symbols $f_i$ of arity $n_i$.
Let $X = \{x_1, x_2, x_3, \ldots\}$ be a countably infinite set of
variables.
We denote by $W_{\tau}(X)$ the set of all terms of type $\tau.$
Any mapping $\sigma: \{f_i \mid i \in I\} \to W_{\tau}(X)$ which
preserves the arity is called a hypersubstitution.
In a canonical way, each hypersubstitution $\sigma$ can be extended
to a mapping $\hat \sigma: W_{\tau}(X) \to W_{\tau}(X)$.
The set $\mathrm{Hyp}(\tau)$ of all hypersubstitutions of type $\tau$
forms a monoid with respect to the composition operation
$\sigma_1 \circ_h \sigma_2 := \hat \sigma_1 \circ \sigma_2$, where
$\circ$ is the usual composition of mappings, and the identity
hypersubstitution $\sigma_{\mathrm{id}}$ mapping each
$f_i$ to $f_i(x_1, \ldots, x_{n_i})$.
If ${\mathcal A}:= (A; (f_i^A)_{i \in I})$ is an algebra of type
$\tau,$ then for any $\sigma \in \mathrm{Hyp}(\tau)$ the algebra
$\sigma({\mathcal A}):= (A; (\sigma(f_i^A)_{i \in I})$ is called
a derived algebra.
For a variety $W$ of algebras of the same type we denote by $\sigma(W)$
the class of all algebras derived from algebras in $W$ by $\sigma.$
The relation
$$R:= \{(\sigma,W)\mid\sigma \in \mathrm{Hyp}(\tau)\text{ and }
W \in {\mathcal L}(V)\text{ and }\sigma[W] \subseteq W\}$$
\\
defines a Galois connection $(\iota, \mu)$ between $\mathrm{Hyp}(\tau)$
and the lattice ${\mathcal L}(V)$ of all subvarieties of $V$ with
the corresponding maps $\iota$ and $\mu$ defined by
$$\mu(m):= \{W \in {\mathcal L}(V)\mid\forall \sigma \in m~ ((\sigma,W)
\in R)\}$$
and
$$\iota(l):=\{\sigma\in\mathrm{Hyp}(\tau)\mid\forall W\in l~
((\sigma,W)\in R)\},$$
\\
for any $m \subseteq \mathrm{Hyp}(\tau)$ and any $l \subseteq
{\mathcal L}(V)$.
Use this Galois connection to answer the following question:
\begin{problem}\label{hypersub}
What monoids of hypersubstitutions give lattices of varieties
satisfying interesting lattice properties and conversely?
\end{problem}
\who{Martin Goldstern}{goldstern@tuwien.ac.at}
\begin{problem}\label{continuum}
Let $C$ be a precomplete clone on an infinite set $X$ \r(i.e., a
coatom in $\mathrm{Clone}(X)$, the lattice of all clones on $X).$
Write $C^{(1)}$ for the clone
generated by the unary functions of $C$.
Must the interval $[C^{(1)}, C]$ \r(in $\mathrm{Clone}(X))$
have cardinality $2^{2^{|X|}}$?
%% \r(
More generally, for which clones $C$ is the interval
$\{D: D^{(1)} = C^{(1)}\}$ small?
%% \/\r)
\end{problem}
\begin{problem}\label{Clduatom}
Is $\mathrm{Clone}(X)$ dually atomic?
That is, is every proper clone
below a coatom in the lattice $\mathrm{Clone}(X)$?
\end{problem}
The answer is ``yes'' if $X$ is finite (easily), and ``no'' if
$X$ is countable, assuming CH, see \cite{GS:2005}.
Nothing is known for uncountable $X$.\medskip
Background: See \cite{PK:1979} for many general
results on clones, and an extensive bibliography of older papers.
Most results in clone theory are established only for finite base
sets; see \cite{Szendrei:1986} for a survey of such results.
The clone lattice on a fixed infinite set $X$ is very large (of size
$2^{2^{|X|}})$, and in fact many naturally defined subsets (such as
the set of its coatoms) are of the same size, see \cite{Rosenberg:1976}.
It is naturally
partitioned via the map $C \mapsto C^{(1)}$; each equivalence
class is a closed interval (the ``monoidal interval of $C$'').
For many clones $C$ it is known that $C$'s monoidal interval is very
large; for a few clones (e.g., the clone generated by the permutations)
this interval is known to be small, and its lattice-theoretic
structure is known.
However, there are no general methods to investigate
the monoidal intervals. Problem~\ref{continuum} expresses our ignorance
of the structure of the clone lattice and of the monoidal intervals.
Problem~\ref{Clduatom} is a very old question that tests our
understanding
of the clone lattice on infinite $X$; for countable sets, it
was already asked by Gavrilov in \cite[page 22/23]{Gavrilov:1959}.
This question is also listed as problem P8 in \cite[page 91]{PK:1979}.
\begin{thebibliography}{1}
\bibitem[Gavrilov 1959]{Gavrilov:1959}
G.~P. Gavrilov,
\newblock \emph{Certain conditions for completeness in countable-valued logic,}
\newblock Dokl. Akad. Nauk SSSR {\bf 128} (1959), 21--24 (Russian).
\bibitem[Goldstern-Shelah 2005]{GS:2005}
Martin Goldstern and Saharon Shelah,
\newblock \emph{Clones from Creatures},
\newblock Trans. Amer. Math. Soc. {\bf 357} (2005), no. 9, 3525--3551 (electronic).
\bibitem[P{\"o}schel-Kalu{\v{z}}nin 1979]{PK:1979}
R.~P{\"o}schel and L.~A. Kalu{\v{z}}nin,
{\em Funktionen- und Relationenalgebren},
Mathematische Monographien {\bf 15},
VEB Deutscher Verlag der Wissenschaften, Berlin, 1979.
\bibitem[Rosenberg 1976]{Rosenberg:1976}
I.~G. Rosenberg,
\newblock \emph{The set of maximal closed classes of operations on an
infinite set ${A}$ has cardinality $2^{2^{|\kern-0.1mm{A}|}},$}
\newblock Arch. Math. (Basel), {\bf 27} (1976), no. 6, 561--568.
\bibitem[Szendrei 1986]{Szendrei:1986}
{\'A}gnes Szendrei,
\newblock {\em Clones in universal algebra},
\newblock Presses de l'Universit\'e de Montr\'eal, Montreal, Que., 1986.
\end{thebibliography}
\newpage
%% This page break is here because of an ugly page break without it.
%% I don't know how to fix it any other way.
\who{Jennifer Hyndman}{hyndman@unbc.ca}
\begin{problem}\label{PrimPositive}
\quad\vspace{.25\baselineskip}
\begin{enumerate}
\item
Does there exist a type of primitive positive formula whose
presence implies that a finite dualizable algebra is not strongly dualizable?
\item
Can primitive positive formul\ae\ be used to classify which finite
algebras are or are not strongly dualizable?
\end{enumerate}
\end{problem}
Primitive positive formul\ae\ arise in the study of duality theory in the
lifting of homomorphisms. For $\mathbf M$ a finite algebra and
$\mathbf B \leq \mathbf A \leq \mathbf M^I$ if $h : \mathbf B
\rightarrow \mathbf M$ does not lift to some $h' : \mathbf A \rightarrow
\mathbf M$ then $h$ is irresponsible with respect to some primitive
positive formula. That is, there is some primitive positive formula
$\psi$ in the language of $\mathbf M$ on $n$ free variables defining an
$n$-ary relation where for some $a_1, \ldots, a_n$ in $\mathbf B$ the relation
$\psi(a_1, \ldots, a_n)$ holds in $\mathbf A$ but $\psi(h(a_1), \ldots,
h(a_n))$ does not hold in $\mathbf M$.
Lampe, McNulty and Willard \cite{LMW01} show that a finite dualizable
algebra with enough algebraic operations is strongly dualizable. In contrast,
a finite unary algebra with a primitive positive formula defining a
pp-acyclic relation does not have enough algebraic operations and does
not have a finite basis for its quasi-equations~\cite{jph-pp}.
Beveridge, Casperson, Hyndman and Niven \cite{bchn} define, for $\mathbf
M$ a finite algebra and $\mathbf A$ a subalgebra of a power of $\mathbf M$,
the concept of a dense subset of ${\rm Frag}_{\mathbf D(\mathbf A)},$ the
algebraic operations
on finite subalgebras of $\mathbf A$ that extend to $\mathbf A$. If there
exists a nonempty, dense subset of ${\rm Frag}_{D(A)}$ that does not
contain any projections or constant homomorphisms, then $\mathbf M$ is
not strongly dualizable. On finite unary algebras the existence of a
transitive, antisymmetric, almost-reflexive binary relation defined by a
primitive positive formula can be used to construct the appropriate
dense set to show the algebra is not strongly dualizable.
\begin{thebibliography}{1}
\bibitem{bchn}
Erin Beveridge, David Casperson, Jennifer Hyndman, and Todd Niven,
{\em Irresponsibility indicates an inability to be strong}, 19\,pp., manuscript.
\bibitem{jph-pp}
Jennifer Hyndman,
{\em Positive primitive formulas preventing enough algebraic operations},
Algebra Universalis {\bf 52} (2004), no. 2-3, 303--312.
\bibitem{LMW01}
William A.~Lampe, George F.~McNulty and Ross Willard, {\em Full duality
among graph algebras and flat graph algebras}, Algebra Universalis
{\bf 45} (2001), 311--334.
\end{thebibliography}
\who{Ralph McKenzie}{mckenzie@math.vanderbilt.edu}
\begin{problem}[Mikl\'os Mar\'oti, personal communication, July
2004]\label{findeg-fingen}\quad\vspace{.25\baselineskip}
\begin{enumerate}
\item
Does there exist an algorithm to: input a finite system
of operations on a finite set and determine if the generated
clone has finite degree \r(i.e., is the set of admissible operations
for one finitary relation\r)?
\item
Does there exist an algorithm to: input a finitary relation
on a finite set and determine if the clone of admissible
operations is finitely generated?
\end{enumerate}
\end{problem}
\who{George McNulty}{mcnulty@math.sc.edu}
Given a variety $\mathcal V$ of algebras of some finite signature, for
each natural number $n$ there are, up to isomorphism, only finitely many
algebras of cardinality less than $n$ that fail to be in $\mathcal V$.
For each such algebra pick an equation of smallest length that is true
in $\mathcal V$ but fails in the algebra.
In this way a finite set of equations has been selected.
Let $\beta_{\mathcal V}(n)$ be the length of the longest equation in
this finite set. Recent work of Sz\'ekely \cite{Szekely:1998}, Kun,
Vertesi, and Kosik has focussed on the asymptotics of this function.
Every finitely based variety of finite signature has a $\beta$ that
is eventually dominated by a constant function.
Conversely, for locally finite varieties $\mathcal V$, it is not hard
to see that if $\beta_{\mathcal V}$ is dominated by a constant,
then either $\mathcal V$
is finitely based or it is inherently nonfinitely based.
\begin{problem}[S. Eilenberg and M.~P.~Schutzenberger 1976
\cite{EilenbergSchutzenberger:1976}]
Is it true $\mathcal V$ is finitely based whenever $\mathcal V$ is
a variety generated by a finite algebra of finite signature such that
$\beta_{\mathcal V}$ is dominated by a constant?
\end{problem}
The answer is ``yes'' when $\mathcal V$ is generated by a finite
semigroup, as shown by Sapir \cite{Sapir:1988}.
Robert Cacioppo in his dissertation \cite{Cacioppo:1987} and in
\cite{Cacioppo:1988,Cacioppo:1993} has provided further evidence
that this problem may have a positive solution.
The paper of Eilenberg and Schutzenberger concerned pseudovarieties.
The connection is as follows.
A pseudovariety is said to be \textbf{finitely based} provided it
is the class of all finite algebras belonging to some finitely based
variety (warning: this variety may be larger than the variety
generated by the pseudovariety).
For a variety $\mathcal V$, the contention that $\beta_{\mathcal V}$
is dominated by a constant is equivalent to the
contention that the finite members of $\mathcal V$ comprise a
finitely based pseudovariety.\smallskip
For the next problem, let $\mathbb R$ denote the topological
space of real numbers.
Walter Taylor in \cite{Taylor2005} proved that there is no algorithm
which upon input of a finite set of equations will decide whether
the set of equations is compatible with $\mathbb R$; that is whether
$\mathbb R$ can be equipped with continuous operations to produce a
model of the set of equations.
An important step in Taylor's argument is that the system of real
functions $x+y,$ $x-y,$ $x\cdot y,$ $\sin(\frac{\pi}{2}x),$
$\cos(\frac{\pi}{2}x),$
$\sqrt{\cos(\frac{\pi}{2}\sin(\frac{\pi}{2}x))},$
and the constant function $1$ is actually determined up to
topological and algebraic isomorphism by a finite set of equations.
Call such a system of continuous operations \textbf{finitely determined}
for the topological space $\mathbb R$.
\begin{problem}\quad\vspace{.25\baselineskip}
\begin{enumerate}
\item
Is there a finite system of continuous operations which is finitely
determined with respect to $\mathbb R$ and which includes
$x+y,$ $x-y,$ $x\cdot y,$ $\sin x,$ and $1$?
What about replacing $\sin x$ with $e^x$?
\item
Is there a finite system of continuous operations which is finitely
determined with respect to $\mathbb R$ and which includes a conjugated
pair of decoding functions?
\end{enumerate}
\end{problem}
\noindent
Here, $F$ and $G$ are conjugated decoding functions provided for
every pair $\langle a,b\rangle$ of real numbers there is a real
number $c$ so that $F(c)=a$ and $G(c)=b$.
An affirmative answer to the first question (with $\sin x$) might
provide a simpler
route to Taylor's compatibility result. The availability of conjugated
decoding functions might lead to a direct way to simulate computations
in the clone of continuous operations on $\mathbb R$.
Similar problems could be formulated for other topological spaces.
\begin{thebibliography}{9}
\bibitem{Cacioppo:1987}
Robert Cacioppo,
\newblock
\emph{Finite bases for varieties and pseudovarieties,}
\newblock
Ph.D. thesis, University of Iowa, 1987, 62$+$viii.
\bibitem{Cacioppo:1988}
Robert Cacioppo,
\newblock
\emph{On finite bases for varieties and pseudovarieties,}
\newblock
Algebra Universalis, \textbf{25} (1988), 263--280.
\bibitem{Cacioppo:1993}
Robert Cacioppo,
\newblock
\emph{Nonfinitely based pseudovarieties and inherently nonfinitely based
varieties,}
\newblock
Semigroup Forum \textbf{47} (1993), 223--226.
\bibitem{EilenbergSchutzenberger:1976}
S.~Eilenberg and M.~P.~Schutzenberger,
\newblock
\emph{On pseudovarieties,}
\newblock
Advances in Mathematics \textbf{19} (1976), 413--418.
\bibitem{Sapir:1988}
Mark Sapir,
\newblock
\emph{On the finite basis property of finite semigroups,}
\newblock
C. R. Acad. Scr. Paris S\'er. I Math. \textbf{306} (1988), 795--797 (French).
\bibitem{Taylor2005}
Walter Taylor,
\newblock
\emph{Equations on real intervals}, %% Get the page numbers right!
\newblock Algebra Universalis, {\bf 55} (2006), .
\bibitem{Szekely:1998}
Zolt\'an Sz\'ekely,
\newblock
\emph{Complexity of the finite algebra membership problem,}
\newblock
Ph.D. thesis, University of South Carolina, 1998, 168$+$viii.
\end{thebibliography}
\who{Luis Sequeira}{lfsequeira@fc.ul.pt}
\begin{problem}
Is every finite algebra having a ``pre-near-unanimity'' term dualizable?
\end{problem}
\begin{problem}
Does every finite algebra which is dualizable and generates a
congruence-modular variety have a ``pre-near-unanimity'' term?
\end{problem}
\who{Ross Willard}{rdwillar@uwaterloo.ca}
A finite algebra in a finite language is said to be \emph{inherently
nonfinitely $q$-based} if it does not belong to any locally finite,
finitely
axiomatizable quasivariety. J.~Lawrence and I gave examples of such
algebras, each of which generates a variety in which only
type~$1$ occurs (in the sense of tame congruence theory).
Recently, M.~Mar\'oti and R.~McKenzie have shown that no example can
generate a variety which omits types~$1$ and~$2$.
\begin{problem}
Does there exist an inherently nonfinitely $q$-based \r(finite\r)
algebra whose generated variety omits type~$1$?
\end{problem}
\who[Contributed]{Walter Taylor}{wtaylor@euclid.Colorado.edu}
\newcommand{\EQ}{\mbox{$\;\; = \;\;$}}
\newcommand{\FROM}{\!:\!}
\newcommand{\TO}{\longrightarrow}
\newcommand{\GOESTO}{\longmapsto}
\newcommand{\Reals}{{\mathbb R}} % not used
\newcommand{\Integers}{{\mathbb Z}} % not used
\newcommand{\Compos}{\!\circ\! }
\newcommand{\Dash}{\rule[.9mm]{1.5cm}{.1mm}\hspace{2mm}}
In September, 1986, I prepared this (until now unpublished) list of ten
problems for presentation to seminars (at the University of
Colorado, the University of Hawaii, and McMaster University). I
recently found one surviving copy. I transcribed each
problem, almost exactly as it was stated then, and after each problem
I have added comments and updates for 2005.
They were then reformatted somewhat for this problem list.
Six of the problems (numbers~\ref{WT1eqcpdlat},
\ref{WT2embeqcp}, \ref{WT7congmodpm}, \ref{WT8avoidwd},
\ref{WT9uniqfac}, \ref{WT10univalg}) remain unsolved
(although a very significant advance was made in the case of
Problem~\ref{WT8avoidwd}).
Each of the remaining four (Problems~\ref{WT3ident},
\ref{WT4interpatom}, \ref{WT5interpcover}, \ref{WT6interpbigantich}) has
been solved in at least a narrow sense, although each of them
points toward further questions and further discoveries.
I wish to thank George Bergman, Ralph Freese and George McNulty for many useful
comments on the presentation of this material.
\vspace*{0.1in}
\begin{problem}[J. Mycielski, 1964---see \cite{myc-some-comp}]
\label{WT1eqcpdlat}
Is every equationally compact distributive lattice $L$ a retract of
some compact topological lattice?
\end{problem}
The corresponding assertion
has been proved {\em ad hoc} for Boolean algebras, for Abelian
groups, for vector spaces over a field, and for mono-unary
algebras. It fails for bi-unary algebras and semigroups. It
also remains unknown for groups.
An algebra $\mathbf A$ is called
{\em weakly equationally $\kappa$-compact} iff the following holds
for every set $\Sigma$ of equations in the similarity type of
$\mathbf A$ with $|\Sigma|<\kappa$ (and with no restriction on the
number of variables appearing in $\Sigma$): if every finite subset
of $\Sigma$ is satisfiable in $\mathbf A$, then $\Sigma$ is
satisfiable in $\mathbf A.$ An algebra $\mathbf A$ is called {\em
equationally $\kappa$-compact} iff $\langle\mathbf
A,a\rangle_{a\in A}$ ($\mathbf A$ with all constants added to the
similarity type) is weakly equationally $\kappa$-compact, and {\em
equationally compact} iff it is equationally $\kappa$-compact for
every $\kappa.$ It is known that if $\mathbf A$ is equationally
$|A|^{++}$-compact, then $\mathbf A$ is equationally compact.
If $\mathbf A\subseteq\mathbf B$, then a {\em retraction of
$\mathbf B$ onto $\mathbf A$} is a homomorphism $f\FROM\mathbf
B\TO\mathbf A$ such that $f|_A$ is the identity on $A$. If such an
$f$ exists, then we say that $\mathbf B$ {\em retracts onto
$\mathbf A.$} {\em An algebra $\mathbf A$ is equationally compact
iff every ultrapower of $\mathbf A$ retracts onto $\mathbf A,$ iff
every elementary extension of $\mathbf A$ retracts onto $\mathbf
A$.} A {\em compact topological algebra} is an algebra $\langle
A,F_t\rangle_{t\in T}$ equipped with a compact Hausdorff topology
$\mathcal T$ such that each $F_t$ is continuous as a map from
$A^{n_t}$ (in the Tychonov product topology) to $A$. An easy
application of the definition implies that {\em every compact
topological algebra is equationally compact}. It is also easy to
check that {\em the class of equationally compact algebras is
closed under the formation of retracts}; hence {\em every retract
of a compact topological algebra is equationally compact.}
Mycielski's question asked whether this condition characterizes
equational compactness. The answer turned out to be no in general,
but nevertheless the question remains for such simple classes as
distributive lattices. \vspace{0.1in}
{\em 2005 Comment.} There has been no progress on any
version of the above problem since around 1979. Mycielski's original
problem was stated in 1964---see \cite[Problem
484]{myc-some-comp}. The mentioned negative solutions for
bi-unaries and for semigroups may be found in two 1972 papers of
W. Taylor---\cite[page 111]{wtaylor-acee} and \cite{wtaylor-ecs},
respectively. A
negative solution for groups was given\footnote{%
The Kel'tenova reference is in a journal from Alma-Ata that is not
easily accessible to me; I rely here on Mathematical Reviews.}%
by R. T. Kel'tenova in 1976---see \cite{keltenova}---although
apparently I did not know of it in 1984. D. K. Haley obtained a
negative answer for rings in 1979---see \cite{haley}. The positive
solution for Abelian groups (which in fact seeded the whole
theory) was given by J. \L o\'s in 1957---see \cite{los-b}.
Positive solutions for vector spaces and for Boolean algebras were
\selectlanguage{polish}%
given by B. W"eglorz in 1966---see
\selectlanguage{english}%
\cite{weg-I}. S. Bulman-Fleming gave a positive solution for
semilattices in 1972---see \cite{sbf-semilattice}. \vspace{0.1in}
{\em Background to Problem~\ref{WT2embeqcp}.}
It turns out that a variety
$\mathcal V$ has the property that each of its algebras is
embeddable in an equationally compact algebra iff $\mathcal V$ is
residually small, i.e.\ there is an upper bound on the
cardinality of subdirectly irreducible algebras occurring in
$\mathcal V$.
\begin{problem}[W. Taylor, 1972]\label{WT2embeqcp}
Does every residually small variety also have
the property that each of its algebras is embeddable in a compact
topological algebra?
\end{problem}
It would be enough, of course, to prove that
each subdirectly irreducible algebra in $\mathcal V$ is so
embeddable. For known residually small varieties, there is usually
an obvious construction, e.g., if all the subdirectly irreducible
algebras are finite. But for Abelian groups there is a very
special construction: $\Integers_{p^{\infty}}$ gets embedded into
the circle group. \vspace{0.1in}
{\em 2005 Comment.} Nothing further is known on the above
problem. The original statement of the problem was in 1972---see
W. Taylor \cite[p.\,43]{wtaylor-rsv}. The theorem quoted as
background is from \cite{wtaylor-rsv}. In the Abelian group
case, the Bohr compactification yields an embedding of each such
group into a compact Abelian group. The same construction works for
modules over an arbitrary ring---see Warfield \cite{warfield}.
\begin{problem}[Taylor, from about 1976]\label{WT3ident}
Does there exist an
interesting finite set of identities which is satisfiable on any
unusual (but well-known) topological space?
\end{problem}
A set $\Sigma$ of identities may be called interesting if $\Sigma$
cannot be
satisfied on a set of more than one element by using projection
functions for its operations. (This means that $\Sigma$ does not
represent the least element of the Neumann-Garc\'{\i}a-Taylor
lattice.) An unusual space is one where the classical
topological-algebraic constructions are not (and cannot be)
encountered. A good test case is a two-dimensional manifold of
genus 2 (i.e., the surface of a two-holed torus). (I have added
the ``well-known'' proviso, because there is a method, due to S.
\'Swierczkowski, of freely constructing spaces that satisfy any
consistent finite $\Sigma.$ These aren't what we are looking for.)
\vspace{0.1in}
{\em 2005 Comment.} For the test case mentioned here---the
surface $G_2$ of genus two---the best possible answer was
published by W. Taylor in 2000---see \cite{wtaylor-sae}. A theory
$\Sigma$ is modelable with continuous operations on $G_2$ only if
$\Sigma$ is {\em undemanding}, i.e. $\Sigma$ can already be
modeled with constant and projection operations. (And
``demanding'' turns out to be the right notion---not the
``interesting'' that we originally had in the statement of
Problem~\ref{WT3ident}.)
The same result has been proved also for a number of other spaces:
figure-eight, spheres $S^n$ other than for $n=1,3,7,$ and spaces
that are similar to these in cohomology. The results may be found
in W. Taylor \cite{wtaylor-sae}. The method clearly extends
further than it was taken in \cite{wtaylor-sae}, but it isn't
clear exactly how far. At this point it seems that, if there is an
interesting example, it is arcane and hard to find.
When I wrote loosely, twenty years ago, of ``classical
constructions,'' I was thinking of spaces where algebraic
structure can be imposed through such well-known methods as matrix
multiplication, quaternion operations, groups on cubic curves,
lattice and median operations arising from the natural ordering of
$\Reals$, and the like. One thrust of the question was whether
some further methods might be found; such further methods, if any,
remain undiscovered. In fact \cite{wtaylor-sae} rendered their
existence less likely. From this point of view, progress on
Problem~\ref{WT3ident} has been disappointing.
The varietal interpretability lattice $\mathcal L$ was introduced
by W. D. Neumann in \cite{neumann} and studied by O. Garc\'{\i}a
and W. Taylor in \cite{garcia-wt}.
For the mentioned construction of S. \'Swierczkowski, see his
paper \cite{swiercz}. See also J. P. Coleman \cite{coleman}.
\begin{problem}[Garc\'{\i}a and Taylor, 1984]\label{WT4interpatom}
Does the lattice of
interpretability have a least element greater than $0$?
\end{problem}
\ldots
It is known that $0$ is $\wedge$-irreducible, and there are either no
atoms or a single atom \ldots~. In the case of no atoms, there
would be a countably infinite descending sequence that meets to
$0$. \ldots
\vspace{0.1in}
{\em 2005 Comment.} There is a countably infinite
descending sequence that meets to $0$. A direct construction was
given by W. Taylor in 1988---see \cite{wtaylor-vwi}. Further
interesting non-trivial infinite meets (implying non-existence of
certain covers) may be found in R. McKenzie and S. \'Swierczkowski
\cite{mckenz-swiercz}. \vspace{0.1in}
\begin{problem}[Garc\'{\i}a and Taylor, 1984]\label{WT5interpcover}
Find any covering
whatever in the lattice of interpretability.
\end{problem}
Note of caution
here: if one insists that $\Gamma_1 =$ a single constant $C$ is
different from $\Gamma_2 =$ a unary operation obeying $F(x)\approx
F(y)$, then indeed $\Gamma_1$ covers $\Gamma_2$. (This is a
book-keeping quibble, rather than a genuine example. We defined
things in Garc\'{\i}a and Taylor in such a manner that this
doesn't occur.)
\vspace{0.1in}
{\em 2005 Comment.} R. McKenzie discovered a cover of
Boolean algebras in 1993; see \cite{mcken-ba}. His method was
adapted and extended for further examples by J. Hyndman in
1996--7. See \cite{hynd-cover-a,hynd-cover-b}. She also proved
that $\mathcal L$ has no subinterval that is a three-element
chain.
\vspace{0.1in}
\begin{problem}[Garc\'{\i}a and Taylor, 1984]\label{WT6interpbigantich}
Find an uncountable
antichain in the lattice $\mathcal L$ of interpretability. If you
can do that, then find one which is a proper class.
\end{problem}
There do exist proper classes inside $\mathcal L$,
but the ones we know are all chains.
\vspace{0.1in}
{\em 2005 Comment.} In 2002, V. Trnkov\'a and A.
Barkhudaryan proved \cite{trnko-bark} that for every cardinal
$\kappa$ there is an antichain of power $\kappa$ in $\mathcal L$.
They also proved that the existence of a proper-class antichain is
equivalent to the negation of {\em Vop\v enka's principle} (a
proposed higher axiom of set theory). Thus, in particular, if
there is no measurable cardinal then such a proper class exists,
and it is consistent (under some set-theoretic assumptions) that
no such proper class exists. \vspace{0.1in}
\begin{problem}[Garc\'{\i}a and Taylor, 1984]\label{WT7congmodpm}
Prove that congruence modularity is a prime Mal'tsev condition.
\end{problem}
Recall that a Mal'tsev
condition is a certain kind of filter in the lattice $\mathcal L$
of interpretability, and that we call a filter $\mathcal F$ {\em
prime} iff $\mathcal F$ satisfies the following condition: if
$x\vee y\in\mathcal F$, then $x\in\mathcal F$ or $y\in\mathcal F$.
It is the primeness that is at issue here.
Here is a more down-to-earth statement of the problem.
\vspace{0.1in}
{\em Suppose that we are given two finite sets of equations, $\Sigma$
and $\Gamma$, in disjoint languages. Is it true that if
$\Sigma\cup\Gamma$ is congruence-modular, then either $\Sigma$ is
congruence-modular or $\Gamma$ is congruence-modular?}
\vspace{0.1in}
In 1983, S. Tschantz gave a heroic proof of the corresponding
result for permutability. The complication that arose from the
innocent-seeming equations $p(x,z,z)\approx x$ and
$p(x,x,z)\approx z$ is incredible.
By the way, the filter defined by congruence distributivity is
not prime: it is a proper intersection of two Mal'tsev filters.
\vspace{0.1in}
{\em 2005 Comment.} The above question remains open. (And indeed
the Tschantz result remains unpublished.) The question---both for
permutability and for modularity---appears on page 58 of
Garc\'{\i}a and Taylor \cite{garcia-wt}. L. Sequeira proved
\cite{seq-thesis} that terms of depth 2 alone cannot be used to
construct a counterexample to the question. The assertion (at the
end) about congruence-distributivity may be found in
\cite[Proposition 35, p.59]{garcia-wt}.
\vspace{0.1in}
For the next problem we need some definitions.
Let $W$ be a word in alphabet
$\Sigma$ and $U$ a word in alphabet $\Sigma'$. We say that $W$
{\em avoids} $U$ iff no image of $U$ [by a semigroup homomorphism]
is a factor of $W$. For example, if $U=xx$ and $W=abcdbcde$, then
$W$ does not avoid $U$, since $W$ has the factor $bcd\cdot bcd$,
which is the image of $xx$ under the homomorphism that takes $x$
to $bcd$. We call $U$ $\Sigma$-{\em avoidable} iff there is an
infinite word $W$ on the alphabet $\Sigma$ that avoids $U$. If $U$
is $\Sigma$-avoidable for some $\Sigma$ that has $\leq n$ letters,
then $U$ is said to be $n$-{\em avoidable}. Finally, we say that
$U$ is {\em avoidable} iff $U$ is $n$-avoidable for some $n$.
\begin{problem}[G. McNulty, around 1974]\label{WT8avoidwd}
Is there a largest $N$ such that there is an $N$-avoidable word
(as defined above)
that is not $(N\!-\!1)$-avoidable? If so, what is it?
\end{problem}
So far we know that $N\geq 4$. The following word is 4-avoidable but
not 3-avoidable:
\begin{align*}
U \;=\; ab\cdot w\cdot bc\cdot x\cdot ca\cdot y\cdot
ba\cdot z\cdot ac.
\end{align*}
Words that avoid $xx$ are called {\em square-free} and have played
an important role in some investigations of dynamical systems.
Thue's infinite square-free word on three letters was useful in
the Burris-Nelson result that the subvariety lattice of the
variety of semigroups satisfying $x^2\approx x^3$ has a sublattice
isomorphic to the infinite partition lattice.\vspace{0.1in}
{\em 2005 Comment.} We now have $N\geq 5$. R. J. Clark
proved in 2001 that
\begin{align*}
W\EQ abebafacgbchcdaidcd
\end{align*}
is 5-avoidable but not 4-avoidable (see \cite{clark}). Yet it
still seems difficult to continue to $N\geq 6$. The 4-avoidable
word $U$ written above appears in Baker, McNulty and Taylor
\cite{kab-gm-wt}. By the way, the dots appearing in our
description of $U$ have no mathematical content; they are there
simply as punctuation. (See \cite{kab-gm-wt} or \cite{clark} for
reasons why such punctuation is helpful conceptually.)
Avoidance of $x^2$ (using three letters) and $x^3$ (using two
letters) goes back to Thue in 1906---see \cite{thue-a} and
\cite{thue-b}; see also the 1944 work of Morse and Hedlund
\cite{morse-hedlund}. Avoidance made an appearance in the 1968
Novikov-Adian solution of the Burnside problem---see \cite{adian}.
The first statement of the general definition appeared in 1979 in
Bean, Ehrenfeucht, McNulty---see \cite{bean-e-m}. An equivalent
definition was independently given in 1984 by Zimin \cite{zimin}.
Problem~\ref{WT8avoidwd} was first published in
1989---see \cite{kab-gm-wt}.
The Burris-Nelson result mentioned above appears in
\cite{burris-nelson}. For two other interesting algebraic
applications of avoidability, see Je\v zek \cite{jezek} and Sapir
\cite{sapir}.
\vspace{0.1in}
\begin{problem}\label{WT9uniqfac}
Do the following conditions on an algebra $\mathbf
A$ imply that $\mathbf A$ is uniquely factorable under direct
product?
\begin{enumerate}
\item $\mathbf A$ has a one-element subalgebra.
\item $\text{\bf Con } \mathbf A$ is modular.
\item $\text{\bf Con } \mathbf A$ has finite height.
\end{enumerate}
\end{problem}
Factorization refers here to an isomorphism between $\mathbf A$
and a product $\mathbf B_1\times\cdots\times\mathbf B_k$, with
each $\mathbf B_i$ product-indecomposable. Uniqueness means that
the factors in any one factorization correspond bijectively to the
factors in any other factorization, with corresponding factors
isomorphic. The indicated result holds either if we strengthen
(2) to congruence permutability (Ore and Birkhoff), or if we
strengthen (3) to say that $\mathbf A$ is finite (J\'onsson).
There are numerous examples to show that the assertion is false if
(1) is not assumed.\vspace{0.1in}
{\em 2005 Comment.} This
problem was later stated on page 276 of McKenzie, McNulty,
Taylor \cite{mck-mcn-wt}. For the Birkhoff-Ore Theorem see
\cite[Theorem 5.3]{mck-mcn-wt}, and for J\'onsson's Theorem see
\cite[Theorem 5.4]{mck-mcn-wt}. The presentation in
\cite{mck-mcn-wt} attempts parallel proofs of the two results, but
is nevertheless unable to solve our Problem~\ref{WT9uniqfac}. For some
counterexamples that involve possible weakenings of (1--3), see
\cite[pp.\ 264--267]{mck-mcn-wt}. \vspace{0.1in}
The proof of J\'onsson's Theorem in \cite{mck-mcn-wt} uses Lemma~4
\cite[pp.\ 270]{mck-mcn-wt} which states that if $\mathbf A$ is finite
and if $\alpha \times \alpha' = \beta \times \beta' = \alpha \wedge
\beta' = \alpha' \wedge \beta$ in $\text{\bf Con } \mathbf A$, then also
$\alpha \times \beta'$ exists and equals $\alpha \times \alpha'$. It is
noted in \cite{mck-mcn-wt} that if the hypothesis of Lemma~4 could be
weakened to $\text{\bf Con } \mathbf A$ is modular and of finite height
then Problem~\ref{WT9uniqfac} would have a positive answer. Freese
\cite{freese-direct} shows that if there is no homomorphism from the
sublattice generated by $\{\alpha, \alpha', \beta, \beta'\}$ onto
${\mathbf M}_4,$ then the strengthened Lemma~4 is true.
In~\cite{freese-four} Freese gives an example showing the desired
strengthening of Lemma~4 is false. However, this example is not a
counterexample to Problem~\ref{WT9uniqfac}.
%% Moreover, there is a different conjectured extension of Lemma~4, which also
%% would imply the desired common generalization of the Birkhoff-Ore and
%% J\'onsson theorems, that is still open. So this approach to the problem
%% is still viable.
\begin{problem}[J. Mycielski, G. McNulty {\em et al.}]
\label{WT10univalg}
Does there exist an algorithm to determine whether a semigroup word is
universal? Does there exist a semigroup word that is universal in
one infinite power but not all infinite powers? How about the same
questions for finite sets of semigroup words?
\end{problem}
A semigroup word is
a finite sequence of letters $a_1a_2a_3\cdots a_n$ selected from a
finite alphabet $\Sigma.$ It is {\em universal in power} $\kappa$
iff the following is true: for every function
$F\FROM\kappa\TO\kappa$ there exists a map
$\Sigma\TO\kappa^{\kappa}$, denoted $a\GOESTO\overline{a}$, such
that $F=\overline{a}_1\Compos\overline{a}_2\Compos \cdots
\Compos\overline{a}_n$. A word is called {\em universal} iff it is
universal in power $\kappa$ for every infinite $\kappa$. The
extension of these definitions to finite or infinite sets of words
is more or less obvious. (Given words $F_0$, $F_1$, \ldots~, there
must exist a {\em single} map $\Sigma\TO\kappa^{\kappa}$ such that
each $F_i$ is represented in the manner described above.)
(Let $w_1$, $w_2$, \ldots be a family of words in two letters $u$
and $v$ that is universal in every infinite power $\kappa$. (Such
a family exists, by Sierpi\'nski \cite{sierpinski}.) The
universality of $a_1a_2a_3\cdots a_n$ in power $\kappa$ is clearly
equivalent to the universality of $w_1w_2w_3\cdots w_n$ (the
concatenation of the words $w_i$) in power $\kappa$. Thus it is
enough to consider the above problems for two letters only, i.e.\
for $|\Sigma|=2$.)
In 1979 W. Taylor answered both the decidability question and the
infinite powers question for
universality as defined for finite sequences of terms involving
functions of more than one variable. In that larger context,
universality is not decidable, and the class of infinite $\kappa$
for which a given finite set of terms is universal can be
arbitrarily wild. Needless to say, the proofs there made essential
use of binary (and higher) functions. The only evidence in the
unary case is the work of Don Silberger ({\em et al.}): they have
characterized universality for some very short semigroup words;
the rapid growth in complexity of these partial answers lends some
credence to the idea of recursive undecidability in the unary
case. \vspace{0.1in}
{\em 2005 Comment.} Nothing further is known on the above
problem. In its general form (involving sets of operations of
arbitrary arities), the algorithmic question was first stated by
G. McNulty in 1976---see \cite[page 205]{mcnulty-aml}. Taylor's
(negative) solution to that problem appeared in 1979---see
\cite{wt-ust}. The possibility still remains of an algorithm for
the restricted problem involving unary functions only. That is the
(algorithmic) question that is asked here.
The question about the class of infinite powers over which a word
is universal is stated by Isbell in \cite{isbell-univ-term} and
attributed there to Mycielski. The problem is restated in McNulty
\cite[page 205]{mcnulty-aml}, and extended there to sets of terms
of arbitrary arity (solved by Taylor in \cite{wt-ust}). One may
consult McNulty \cite[\S 2]{mcnulty-aml} for a compendium of most
of the known general facts about, and constructions of, universal
sets. The open problems there [{\em loc.\ cit.,} pp.\,228--9]
overlap with all the problems mentioned here (and indeed go
further). The early work of Silberger (and co-workers) may be
found in \cite{ehren-silb} and its references.
Examples of universal sets of terms were presented in 1934 by
Sierpi\'nski \cite{sierpinski}, in 1935 by Banach \cite{banach},
in 1949 by Hall \cite{hall}, in 1950 by \L o\'s \cite{los-a}, and
in 1966 by Mal'tsev \cite{maltsev}. These papers apply the
existence of such universal sets to various problems in algebra
and logic. Some universal sets of terms were useful to G. McNulty
\cite{mcnulty-jsl} \cite{mcnulty-aml} in his studies on
algorithmic properties of sets of equations. For universality of
terms in the context of topological spaces, see W. Taylor
\cite[Chapter 4]{wtaylor-cots}.
One can define universality of {\em group} terms by putting the
symmetric group on $\kappa$ in place of the semigroup $\kappa^\kappa$.
Ore \cite{ore} showed the group term $xyx^{-1}y^{-1}$ universal; the set
of all universal group terms was determined by Lyndon \cite{lyndon};
see also Dougherty and Mycielski \cite{D+M}.
%\newcommand{\AMS}{{American Mathematical Society}}
\newcommand{\AMS}{{Amer. Math. Soc.}}
\newcommand{\AU}{{Algebra Universalis}}
%\newcommand{\AML}{{Annals of Mathematical Logic}}
\newcommand{\AML}{{Ann. of Math. Logic}}
%\newcommand{\COLLOQ}{{Col\-lo\-qui\-um Ma\-the\-ma\-ti\-cum}}
\newcommand{\COLLOQ}{{Colloq. Math.}}
%\newcommand{\FM}{{Fun\-da\-men\-ta Ma\-the\-ma\-ti\-cae}}
\newcommand{\FM}{{Fund. Math.}}
%\newcommand{\JAMS}{{Journal of the Australian Mathematical Society}}
\newcommand{\JAMS}{{J. Aust. Math. Soc.}}
\newcommand{\JSL}{{J. Symbolic Logic}}
\newcommand{\MAMS}{{Mem. \AMS}}
\newcommand{\NORSK}{{Norske Vid. Selssk. Skr. I, Mat. Nat.
Kl. Chris\-ti\-a\-nia}}
%\newcommand{\PACIFIC}{{Pacific Journal of Mathematics}}
\newcommand{\PACIFIC}{{Pacific J. Math.}}
\newcommand{\PAMS}{{Proc. \AMS}}
\newcommand{\SF}{{Semigroup Forum}}
%\newcommand{\TAMS}{{Transactions of the \AMS}}
\newcommand{\TAMS}{{Trans. \AMS}}
\newcommand{\TCS}{{Theoret. Comput. Sci.}}
\def\upbrace(#1){\doBrace{#1}}
\newcommand{\doBrace}[1]{\textup{(}#1\textup{)}}
\begin{thebibliography}{99}
\bibitem{adian}
S. I. Adian, {\em The Burnside problem and identities in
groups}, Springer, New York, 1979.
\bibitem{kab-gm-wt}
K. A. Baker, G. F. McNulty, and W. Taylor, \emph{Growth problems for
avoidable words}, \TCS\ \textbf{69} (1989),
319--345.
\bibitem{banach}
S. Banach, \emph{Sur un th\'eor\`eme de M. Sierpsinski},
\FM\ \textbf{25} (1935), 5--6.
\bibitem{bean-e-m}
D. R. Bean, A. Ehrenfeucht, and G. F. McNulty, \emph{Avoidable
patterns in strings of symbols}, \PACIFIC\ \textbf{85} (1979), 261--294.
%% MR 81i:20075
\bibitem{sbf-semilattice}
S. Bulman-Fleming,
\emph{On equationally compact semilattices}, \AU\ \textbf{2}
(1972), 146--151. %positive solution for semilattices
\bibitem{burris-nelson}
S. Burris and E. Nelson, \emph{Embedding the dual of $\Pi_{\infty}$ in
the lattice of equational classes of semigroups}, \AU\ \textbf{1}
(1971--72), 248--253.
\bibitem{clark}
R. J. Clark, \emph{Avoidable Formulas in Combinatorics on Words}, Ph.D.
thesis, UCLA, 2001,
http://www.math.ucla.edu/$\!\sim\!$rclark/thesis.pdf\,.
\bibitem{coleman}
J. P. Coleman, \emph{Topologies in free algebras}, Ph.D. thesis,
University of Colorado, 1992. University Microfilms number AAT
9318085.
\bibitem{D+M}
Randall Dougherty and Jan Mycielski,
\emph{Representations of infinite permutations by words.~II},
\PAMS\ \textbf{127} (1999), 2233--2243.
\bibitem{ehren-silb}
A. Ehrenfeucht and D. M. Silberger, \emph{Universal terms of the
form $B^nA^m,$}
\AU\ \textbf{10} (1980), 96--116.
\bibitem{freese-direct}
R. Freese, \emph{Notes on Direct Decompositions}, 4\,pp., manuscript,
http://www.math.hawaii.edu/$\!\sim\!$ralph/Notes/dirprod.pdf\,.
\bibitem{freese-four}
\Dash \emph{On extending Lemma 4}, 3\,pp., manuscript,
http://www.math.hawaii.edu/$\!\sim\!$ralph/Notes/lemma4.pdf\,.
\bibitem{garcia-wt}
O. C. Garcia and W. Taylor, \emph{The lattice of interpretability
types of varieties}, \MAMS\ \textbf{50}, 1984,
125 pp.
\bibitem{haley}
David K. Haley, \emph{Equational compactness in rings. With applications
to the theory of topological rings,}
Lecture Notes in Mathematics, \textbf{745},
Springer-Verlag, Berlin, 1979. iii+167 pages.
\bibitem{hall}
M. Hall, \emph{The word problem for semigroups with
two generators}, \JSL\ \textbf{14} (1949), 115--118.
\bibitem{hynd-cover-a}
J. Hyndman, \emph{Covers of primal varieties}, \AU\ \textbf{35} (1996), 167--184.
\bibitem{hynd-cover-b}
\Dash \emph{Covers of some varietal products}, \AU\
\textbf{37} (1997), 154--184.
\bibitem{isbell-univ-term}
J. R. Isbell,
\emph{On the problem of universal terms}, Bull. Acad. Polon.
Sci. S\'er. Sci. Math. Astronom. Phys.
\textbf{14} (1966), 593--595.
\bibitem{jezek}
J. Je\v zek, \emph{Intervals in the lattice of varieties}, \AU\ \textbf{6}
(1976), 147--158.
\bibitem{keltenova}
R. T. Kel'tenova, \emph{On the theory of equationally compact
algebras}, pp. 32--37, 227 in: Collection of questions
on mathematics and mechanics,
Izdanie Kazah. Gos. Univ., Alma-Ata, No. 8, 1976
(Russian).
%% (MR 58 \#27698)
\bibitem{los-a}
J.\L o\'s, \emph{Un th\'eor\`eme sur les superpositions des fonctions
d\'efinies dans les ensembles arbitraires}, \FM\ \textbf{37} (1950),
84--86.
\bibitem{los-b}
\Dash \emph{Abelian groups that are direct summands of every
Abelian group which contains them as pure subgroups}, \FM\ \textbf{44}
(1957), 84--90.
\bibitem{lyndon}
R. C. Lyndon, \emph{Words and infinite permutations},
Mots 143--152, Lang. Raison. Calc., Herm\'es, Paris, 1990.
\bibitem{maltsev}
A. I. Mal'tsev, \emph{Identical relations of varieties of
quasigroups}, Mat. Sb. \textbf{69} (1966), 3--12 (Russian).
Translation: \AMS\ Translations,
Series 2, \textbf{82} (1968), 225--235.
\bibitem{mcken-ba}
R. McKenzie, \emph{On the covering relation in the
interpretability lattice of equational theories},
\AU\ \textbf{30} (1993), 399--421.
\bibitem{mck-mcn-wt}
R. N. McKenzie, G. F. McNulty, and W. Taylor, {\em Algebras,
Lattices, Varieties}, Wadworth \& Brooks-Cole, Monterey, 1987.
\bibitem{mckenz-swiercz}
R. McKenzie and S. \'Swierczkowski, \emph{Non-covering in the
interpretability lattice of equational
theories}, \AU\ \textbf{30} (1993), 157--170.
\bibitem{mcnulty-jsl}
G. McNulty, \emph{Undecidable properties of finite sets of equations},
\JSL\ \textbf{41} (1976), 9--15.
\bibitem{mcnulty-aml}
\Dash \emph{The decision problem for equational bases of
algebras}, \AML\ \textbf{11} (1976), 193--259.
\bibitem{morse-hedlund}
M. Morse and G. Hedlund, \emph{Unending chess, symbolic dynamics, and
a problem in semigroups}, Duke Math. J. \textbf{11}
(1944), 1--7.
\bibitem{myc-some-comp}
J. Mycielski, \emph{Some compactifications of general algebras},
\COLLOQ\ \textbf{13} (1964), 1--9.
\bibitem{myc-rn}
J. Mycielski and C. Ryll-Nardzewski, \emph{Equationally compact
algebras \upbrace(II)}, \FM\ \textbf{61} (1968), 271--281.
\bibitem{neumann}
W. D. Neumann, \emph{On Mal'cev conditions}, \JAMS\ \textbf{17} (1974),
376--384.
\bibitem{ore}
O. Ore, \emph{Some remarks on commutators}, \PAMS\ \textbf{2} (1951), 307--314.
\bibitem{sapir}
M. Sapir, \emph{Inherently non-finitely based semigroups}, Mat.
Sb. (N.S.), \textbf{133} (\textbf{175}) (1987), 154--166, 270 (Russian).
\bibitem{seq-thesis}
L. Sequeira, \emph{Is modularity prime?}, Ph.D. thesis, Universidade de Lisboa, 2002.
An abstract may be viewed at
http://www.lmc.fc.ul.pt/$\!\sim\!$lsequeir/math/extabstract.pdf\,.
\bibitem{sierpinski}
W. Sierpi\'nski, \emph{Sur les suites infinies des fonction d\'efinies
dans les ensembles quelconques}, \FM\ \textbf{24} (1934), 209--212.
\bibitem{swiercz}
S. \'Swierczkowski, \emph{Topologies in free algebras},
Proc. London Math.\ Soc.\ (3) \textbf{14} (1964), 566--576.
\bibitem{wtaylor-acee}
W. Taylor, \emph{Atomic compactness and elementary equivalence},
\FM\ \textbf{71} (1971), 103--112.
\bibitem{wtaylor-ecs}
\Dash \emph{On equationally compact semigroups},
\SF\ \textbf{5} (1972), 81--88.
\bibitem{wtaylor-rsv}
\Dash \emph{Residually small varieties}, \AU\ \textbf{2} (1972), 33--53.
\bibitem{wt-ust}
\Dash \emph{Some universal sets of terms}, \TAMS\ \textbf{267} (1981),
595--607.
\bibitem{wtaylor-cots}
\Dash
\emph{The clone of a topological space},
Research and Exposition in Mathematics, \textbf{13} Helderman
Verlag, Berlin, 1986. v+91 pages.
\bibitem{wtaylor-vwi}
\Dash \emph{Some very weak identities},
\AU\ \textbf{25} (1988), 27--35.
\bibitem{wtaylor-sae}
\Dash
\emph{Spaces and equations}, \FM\ \textbf{164} (2000), 193--240.
\bibitem{thue-a}
A. Thue, \emph{\"Uber unendliche Zeichenreihe}, \NORSK\ \textbf{7} (1906), 1--22.
\bibitem{thue-b}
\Dash \emph{\"Uber die gegenseitigen Lage gleicher Teile gewisser
Zeichenreihen}, \NORSK\ \textbf{1} (1912), 1--67.
\bibitem{trnko-bark}
V. Trnkov\'a and A. Barkhudaryan,
\emph{Some universal properties of the category of clones}, \AU\
\textbf{47} (2002), 239--266.
\bibitem{warfield}
R. B. Warfield Jr., \emph{Purity and algebraic compactness for modules},
\PACIFIC\ \textbf{28} (1969), 699--719.
%% MR39 \#4212.
\selectlanguage{polish}%
\bibitem{weg-I}
B. W"eglorz, \emph{Equationally compact algebras \upbrace(I)},
\FM\ \textbf{59} (1966), 289--298.
\selectlanguage{english}%
\bibitem{zimin}
A. I. Zimin, \emph{Blocking sets of terms}, Mat.\ Sb.\
(N.S.) \textbf{119} (\textbf{161}) (1982), 363--375, 447 (Russian).
%% MR 84d:20072
\end{thebibliography}
\end{document}