Problem List

From Algebras, Lattices and Varieties: a Conference in Honor of Walter Taylor, held at the University of Colorado, 15–18 August, 2004

 This is the final preprint version of a problem list which appeared
 at Algebra Universalis 55 (2006) 509-526.  The published version is
accessible to subscribers at  https://dx.doi.org/10.1007/s00012-006-2020-y .

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 18–27.

− − − −

Discussed by George Bergman (gbergman@math.berkeley.edu):

Problem 1 (Hotzel [3]). If M is a monoid such that the lattice of left congruences on M has ascending chain condition, must M be finitely generated?

Hotzel asks this for semigroups and right congruences; his and the above version are equivalent.

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 ∈ M | (a, 1) ∈ C}. The subsets M_{C} ⊆ 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 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 ℤ × ℤ 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 Rees left congruence C is the relation one gets by taking a nonempty left ideal I ⊆ 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

2000 Mathematics Subject Classification: Primary: 08-02 Secondary: 55-02, 06-02, 03-02.

Key words and phrases: open problems in general algebra.

classes singletons. In the submonoid of ℤ × ℤ noted above, the principal ideals generated by (1, 0), (1, −1), (1, −2), … form a strictly ascending chain, so the Rees left congruences do not satisfy ACC.

Finally, for every c ∈ M, the relation c^{⊥} = {(a, b) | ac = bc} is a left congruence. Kozhukhov [4] obtains several results toward an affirmative answer to Problem 1;

in particular, he shows that ACC on right and left congruences together do imply finite generation. (The non-specialist should read [4] with [1] in hand for notation and terminology.)

An appealing approach to Problem 1 is the following. Note that every left congruence C on M contains a greatest two-sided congruence (congruence in the variety of monoids) C^{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^{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.

Problem 2 (Wasserman [5]). Is there a nontrivial lattice that is not generated by the union of two proper sublattices?

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ónsson lattice would yield an affirmative answer to Problem 2. Jónsson lattices of regular cardinality are known not to exist [6]; the singular-cardinality case is open.

Freese, Hyndman and Nation [2] provide conditions under which the answer to Problem 2 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.

References

[1] A. H. Clifford and G. B. Preston, The algebraic theory of semigroups, v. I., Mathematical Surveys No. 7, American Mathematical Society, 1961, xv + 224 pp.

[2] Ralph Freese, Jennifer Hyndman, and J. B. Nation, Lattices that are the join of two proper sublattices, 12 pp., manuscript, http://www.math.hawaii.edu/∼jb/sublatt.pdf .

[3] E. Hotzel, On semigroups with maximal conditions, Semigroup Forum 11 (1975/76), 337–362.

[4] I. B. Kozhukhov, Semigroups with certain conditions on congruences, J. Math. Sci. (N.Y.) 114 (2003), 1119–1126.

[5] David Wasserman, Is there a nontrivial lattice that is not generated by the union of two proper sublattices? 1 p., manuscript, http://home.earthlink.net/∼dwasserm/Sublattice.pdf .

[6] Thomas P. Whaley, Large sublattices of a lattice, Pacific J. Math. 28 (1969) 477–484.

Discussed by Stan Burris (snburris@thoralf.uwaterloo.ca):

Given a class A of algebras let a(n) be the number of algebras in A that have size n (counting up to isomorphism). Walter Taylor called the function a(n) the fine spectrum of A in the case that A is a variety.

In the study of asymptotic density in [2] we require that the finite members of A have the Unique Factorization Property (UFP). Then with p(n) the count function for the indecomposable members of A we have

∑_{n≥1} a(n)n^{−x} = ∏_{n≥2} (1 − n^{−x})^{−p(n)}.

We assume in all questions below: the finite members of A have the UFP.

An important condition in the study of logical limit laws is that the function A(x) = ∑_{n≤x} a(n) have regular variation (at infinity of index α), which means

lim_{t→∞} \frac{A(tx)}{A(t)} = x^{α} .

Recall the UFP assumption:

Problem 3. What can we say about a (locally finite) variety A when A(x) has regular variation?

Jason Bell [1] proved that if P (x) = ∑_{n≤x} p(n) has polylog growth, that is, P (x) = O((log x)^{c}), then A has a first-order 0–1 law.

Problem 4. If A is a (locally finite) variety of algebras, what do Bell’s conditions say about A?

In [1], p. 228, it is proved that if A(x) ∼ Cx^{α} then A has a first-order limit law.

Problem 5. If A is a (locally finite) variety of algebras with A(x) ∼ Cx^{α}, what can we say about A?

References

[1] Jason P. Bell, Sufficient conditions for zero-one laws. Trans. Amer. Math. Soc. 354 (2002), no. 2, 613–630.

[2] Stanley N. Burris, Number Theoretic Density and Logical Limit Laws. Mathematical Surveys and Monographs, 86, Amer. Math. Soc., Providence, 2001. xx+289 pages.

Discussed by 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.

Problem 6. Is dualisability of a finite algebra of finite type decidable?

Problem 7. Does full dualisability imply strong dualisability?

For details see:

References

[1] D.M. Clark and B.A. Davey, Natural Dualities for the Working Algebraist, Cambridge Studies in Advanced Mathematics, 57, Cambridge University Press, Cambridge, 1998. xii+356 pages.

Discussed by Klaus Denecke (kdenecke@rz.uni-potsdam.de):

Let τ = (n_{i})_{i∈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}, …} be a countably infinite set of variables. We denote by W_{τ} (X) the set of all terms of type τ.

Any mapping σ : {f_{i} | i ∈ I} → W_{τ} (X) which preserves the arity is called a hypersubstitution. In a canonical way, each hypersubstitution σ can be extended to a mapping σ̂ : W_{τ} (X) → W_{τ} (X) . The set Hyp(τ) of all hypersubstitutions of type τ forms a monoid with respect to the composition operation σ_{1} ∘_{h} σ_{2} := σ̂_{1} ∘ σ_{2} , where ∘ is the usual composition of mappings, and the identity hypersubstitution σ_{id} mapping each f_{i} to f_{i}(x_{1}, …, x_{n_{i}}) .

If A := (A; (f_{i}^{A})_{i∈I}) is an algebra of type τ, then for any σ ∈ Hyp(τ) the algebra σ(A) := (A; (σ(f_{i}^{A})_{i∈I}) is called a derived algebra.

For a variety W of algebras of the same type we denote by σ(W) the class of all algebras derived from algebras in W by σ. The relation

R := {(σ, W) | σ ∈ Hyp(τ) and W ∈ L(V) and σ[W] ⊆ W }

defines a Galois connection (ι, μ) between Hyp(τ) and the lattice L(V) of all subvarieties of V with the corresponding maps ι and μ defined by

μ(m) := {W ∈ L(V) | ∀σ ∈ m ((σ, W) ∈ R)}

and

ι(l) := {σ ∈ Hyp(τ) | ∀W ∈ l ((σ, W) ∈ R)},

for any m ⊆ Hyp(τ) and any l ⊆ L(V) .

Use this Galois connection to answer the following question:

Problem 8. What monoids of hypersubstitutions give lattices of varieties satisfying interesting lattice properties and conversely?

Discussed by Martin Goldstern (goldstern@tuwien.ac.at):

Problem 9. Let C be a precomplete clone on an infinite set X (i.e., a coatom in 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] (in Clone(X)) have cardinality 2^{2^{|X|}} ?

More generally, for which clones C is the interval {D : D^{(1)} = C^{(1)}} small?

Problem 10. Is Clone(X) dually atomic? That is, is every proper clone below a coatom in the lattice Clone(X) ?

The answer is “yes” if X is finite (easily), and “no” if X is countable, assuming CH, see [Goldstern-Shelah 2005]. Nothing is known for uncountable X.

Background: See [Pöschel-Kalužnin 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 [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 [Rosenberg 1976]. It is naturally partitioned via the map C ↦ 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 9 expresses our ignorance of the structure of the clone lattice and of the monoidal intervals.

Problem 10 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 [Gavrilov 1959, page 22/23]. This question is also listed as problem P8 in [Pöschel-Kalužnin 1979, page 91].

References

[Gavrilov 1959] G. P. Gavrilov, Certain conditions for completeness in countable-valued logic,

Dokl. Akad. Nauk SSSR 128 (1959), 21–24 (Russian). [Goldstern-Shelah 2005] Martin Goldstern and Saharon Shelah, Clones from Creatures, Trans.

Amer. Math. Soc. 357 (2005), no. 9, 3525–3551 (electronic). [Pöschel-Kalužnin 1979] R. Pöschel and L. A. Kalužnin, Funktionen- und Relationenalgebren,

Mathematische Monographien 15, VEB Deutscher Verlag der Wissenschaften, Berlin, 1979. [Rosenberg 1976] I. G. Rosenberg, The set of maximal closed classes of operations on an

infinite set A has cardinality 2^{2^{|A|}}, Arch. Math. (Basel), 27 (1976), no. 6, 561–568. [Szendrei 1986] Ágnes Szendrei, Clones in universal algebra, Presses de l’Université de Montréal,

Montreal, Que., 1986.

Discussed by Jennifer Hyndman (hyndman@unbc.ca):

Problem 11.

(1) Does there exist a type of primitive positive formula whose presence implies that a finite dualizable algebra is not strongly dualizable?

(2) Can primitive positive formulæ be used to classify which finite algebras are or are not strongly dualizable?

Primitive positive formulæ arise in the study of duality theory in the lifting of homomorphisms. For M a finite algebra and B ≤ A ≤ M^{I} if h : B → M does not lift to some h′ : A → M then h is irresponsible with respect to some primitive positive formula. That is, there is some primitive positive formula ψ in the language of M on n free variables defining an n -ary relation where for some a_{1}, …, a_{n} in B the relation ψ(a_{1}, …, a_{n}) holds in A but ψ(h(a_{1}), …, h(a_{n})) does not hold in M .

Lampe, McNulty and Willard [3] 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 quasiequations [2].

Beveridge, Casperson, Hyndman and Niven [1] define, for M a finite algebra and A a subalgebra of a power of M , the concept of a dense subset of Frag_{D(A)}, the algebraic operations on finite subalgebras of A that extend to A . If there exists a nonempty, dense subset of Frag_{D(A)} that does not contain any projections or constant homomorphisms, then 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.

References

[1] Erin Beveridge, David Casperson, Jennifer Hyndman, and Todd Niven, Irresponsibility indicates an inability to be strong, 19 pp., manuscript.

[2] Jennifer Hyndman, Positive primitive formulas preventing enough algebraic operations, Algebra Universalis 52 (2004), no. 2-3, 303–312.

[3] William A. Lampe, George F. McNulty and Ross Willard, Full duality among graph algebras and flat graph algebras, Algebra Universalis 45 (2001), 311–334.

Discussed by Ralph McKenzie (mckenzie@math.vanderbilt.edu):

Problem 12 (Miklós Maróti, personal communication, July 2004).

(1) 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 (i.e., is the set of admissible operations for one finitary relation)?

(2) 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?

Discussed by George McNulty (mcnulty@math.sc.edu):

Given a variety 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 V. For each such algebra pick an equation of smallest length that is true in V but fails in the algebra. In this way a finite set of equations has been selected. Let β_{V}(n) be the length of the longest equation in this finite set. Recent work of Székely [7], Kun, Vertesi, and Kosik has focussed on the asymptotics of this function. Every finitely based variety of finite signature has a β that is eventually dominated by a constant function. Conversely, for locally finite varieties V, it is not hard to see that if β_{V} is dominated by a constant, then either V is finitely based or it is inherently nonfinitely based.

Problem 13 (S. Eilenberg and M. P. Schutzenberger 1976 [4]). Is it true V is finitely based whenever V is a variety generated by a finite algebra of finite signature such that β_{V} is dominated by a constant?

The answer is “yes” when V is generated by a finite semigroup, as shown by Sapir [5]. Robert Cacioppo in his dissertation [1] and in [2, 3] 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 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 V, the contention that β_{V} is dominated by a constant is equivalent to the contention that the finite members of V comprise a finitely based pseudovariety.

For the next problem, let ℝ denote the topological space of real numbers. Walter Taylor in [6] 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 ℝ; that is whether ℝ 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·y, sin(\frac{π}{2} x), cos(\frac{π}{2} x), \sqrt{cos(\frac{π}{2} sin(\frac{π}{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 finitely determined for the topological space ℝ.

Problem 14.

(1) Is there a finite system of continuous operations which is finitely determined with respect to ℝ and which includes x + y, x − y, x · y, sin x, and 1 ? What about replacing sin x with e^{x}?

(2) Is there a finite system of continuous operations which is finitely determined with respect to ℝ and which includes a conjugated pair of decoding functions?

Here, F and G are conjugated decoding functions provided for every pair ⟨a, b⟩ 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 ℝ.

Similar problems could be formulated for other topological spaces.

References

[1] Robert Cacioppo, Finite bases for varieties and pseudovarieties, Ph.D. thesis, University of Iowa, 1987, 62 + viii.

[2] Robert Cacioppo, On finite bases for varieties and pseudovarieties, Algebra Universalis, 25 (1988), 263–280.

[3] Robert Cacioppo, Nonfinitely based pseudovarieties and inherently nonfinitely based varieties, Semigroup Forum 47 (1993), 223–226.

[4] S. Eilenberg and M. P. Schutzenberger, On pseudovarieties, Advances in Mathematics 19 (1976), 413–418.

[5] Mark Sapir, On the finite basis property of finite semigroups, C. R. Acad. Scr. Paris Sér. I Math. 306 (1988), 795–797 (French).

[6] Walter Taylor, Equations on real intervals, Algebra Universalis, 55 (2006), .

[7] Zoltán Székely, Complexity of the finite algebra membership problem, Ph.D. thesis, University of South Carolina, 1998, 168 + viii.

Discussed by Luis Sequeira (lfsequeira@fc.ul.pt):

Problem 15. Is every finite algebra having a “pre-near-unanimity” term dualizable?

Problem 16. Does every finite algebra which is dualizable and generates a congruencemodular variety have a “pre-near-unanimity” term?

Discussed by Ross Willard (rdwillar@uwaterloo.ca):

A finite algebra in a finite language is said to be 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óti and R. McKenzie have shown that no example can generate a variety which omits types 1 and 2 .

Problem 17. Does there exist an inherently nonfinitely q -based (finite) algebra whose generated variety omits type 1 ?

Contributed by Walter Taylor (wtaylor@euclid.Colorado.edu):

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 18, 19, 24, 25, 26, 27) remain unsolved (although a very significant advance was made in the case of Problem 25). Each of the remaining four (Problems 20, 21, 22, 23) 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.

Problem 18 (J. Mycielski, 1964—see [31]). Is every equationally compact distributive lattice L a retract of some compact topological lattice?

The corresponding assertion has been proved 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 A is called weakly equationally κ -compact iff the following holds for every set Σ of equations in the similarity type of A with |Σ| < κ (and with no restriction on the number of variables appearing in Σ ): if every finite subset of Σ is satisfiable in A , then Σ is satisfiable in A. An algebra A is called equationally κ -compact iff ⟨A, a⟩_{a∈A} ( A with all constants added to the similarity type) is weakly equationally κ -compact, and equationally compact iff it is equationally κ - compact for every κ. It is known that if A is equationally |A|^{++} -compact, then A is equationally compact.

If A ⊆ B , then a retraction of B onto A is a homomorphism f:B ⟶ A such that f|_{A} is the identity on A. If such an f exists, then we say that B retracts onto A. An algebra A is equationally compact iff every ultrapower of A retracts onto A, iff every elementary extension of A retracts onto A . A compact topological algebra is an algebra ⟨A, F_{t}⟩_{t∈T} equipped with a compact Hausdorff topology 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 every compact topological algebra is equationally compact. It is also easy to check that the class of equationally compact algebras is closed under the formation of retracts; hence 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.

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 [31, Problem 484]. The mentioned negative solutions for bi-unaries and for semigroups may be found in two 1972 papers of W. Taylor—[39, page 111] and [40], respectively. A negative solution for groups was given^{1}by R. T. Kel’tenova in 1976—see [20]—although apparently I did not know of it in 1984. D. K. Haley obtained a negative answer for rings in 1979—see [14]. The positive solution for Abelian groups (which in fact seeded the whole theory) was given by J. Łoś in 1957—see [22]. Positive solutions for vector spaces and for Boolean algebras were given by B. W_{}eglorz

1The Kel’tenova reference is in a journal from Alma-Ata that is not easily accessible to me; I rely here on Mathematical Reviews.

in 1966—see [50]. S. Bulman-Fleming gave a positive solution for semilattices in 1972—see [5].

Background to Problem 19. It turns out that a variety V has the property that each of its algebras is embeddable in an equationally compact algebra iff V is residually small, i.e. there is an upper bound on the cardinality of subdirectly irreducible algebras occurring in V.

Problem 19 (W. Taylor, 1972). Does every residually small variety also have the property that each of its algebras is embeddable in a compact topological algebra?

It would be enough, of course, to prove that each subdirectly irreducible algebra in 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: ℤ_{p^{∞}} gets embedded into the circle group.

2005 Comment. Nothing further is known on the above problem. The original statement of the problem was in 1972—see W. Taylor [41, p. 43]. The theorem quoted as background is from [41]. 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 [49].

Problem 20 (Taylor, from about 1976). Does there exist an interesting finite set of identities which is satisfiable on any unusual (but well-known) topological space?

A set Σ of identities may be called interesting if Σ cannot be satisfied on a set of more than one element by using projection functions for its operations. (This means that Σ does not represent the least element of the Neumann-Garcí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. Świerczkowski, of freely constructing spaces that satisfy any consistent finite Σ. These aren’t what we are looking for.)

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 [45]. A theory Σ is modelable with continuous operations on G_{2} only if Σ is undemanding, i.e. Σ 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 20.) 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 [45]. The method clearly extends further than it was taken in [45], 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 ℝ, 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 [45] rendered their existence less likely. From this point of view, progress on Problem 20 has been disappointing.

The varietal interpretability lattice L was introduced by W. D. Neumann in [33] and studied by O. García and W. Taylor in [13].

For the mentioned construction of S. Świerczkowski, see his paper [38]. See also J. P. Coleman [8].

Problem 21 (García and Taylor, 1984). Does the lattice of interpretability have a least element greater than 0 ?

… It is known that 0 is ∧ -irreducible, and there are either no atoms or a single atom …. In the case of no atoms, there would be a countably infinite descending sequence that meets to 0 ….

2005 Comment. There is a countably infinite descending sequence that meets to 0 . A direct construction was given by W. Taylor in 1988—see [44]. Further interesting non-trivial infinite meets (implying non-existence of certain covers) may be found in R. McKenzie and S. Świerczkowski [27].

Problem 22 (García and Taylor, 1984). Find any covering whatever in the lattice of interpretability.

Note of caution here: if one insists that Γ_{1} = a single constant C is different from Γ_{2} = a unary operation obeying F (x) ≈ F (y) , then indeed Γ_{1} covers Γ_{2} . (This is a book-keeping quibble, rather than a genuine example. We defined things in García and Taylor in such a manner that this doesn’t occur.)

2005 Comment. R. McKenzie discovered a cover of Boolean algebras in 1993; see [25]. His method was adapted and extended for further examples by J. Hyndman in 1996–7. See [16, 17]. She also proved that L has no subinterval that is a three-element chain.

Problem 23 (García and Taylor, 1984). Find an uncountable antichain in the lattice L of interpretability. If you can do that, then find one which is a proper class.

There do exist proper classes inside L, but the ones we know are all chains.

2005 Comment. In 2002, V. Trnková and A. Barkhudaryan proved [48] that for every cardinal κ there is an antichain of power κ in L. They also proved that the existence of a proper-class antichain is equivalent to the negation of Vopěnka’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.

Problem 24 (García and Taylor, 1984). Prove that congruence modularity is a prime Mal’tsev condition.

Recall that a Mal’tsev condition is a certain kind of filter in the lattice L of interpretability, and that we call a filter F prime iff F satisfies the following condition: if x ∨ y ∈ F , then x ∈ F or y ∈ F . It is the primeness that is at issue here.

Here is a more down-to-earth statement of the problem.

Suppose that we are given two finite sets of equations, Σ and Γ , in disjoint languages. Is it true that if Σ∪Γ is congruence-modular, then either Σ is congruencemodular or Γ is congruence-modular?

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) ≈ x and p(x, x, z) ≈ 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.

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ía and Taylor [13]. L. Sequeira proved [36] 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 [13, Proposition 35, p.59].

For the next problem we need some definitions. Let W be a word in alphabet Σ and U a word in alphabet Σ′. We say that W 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·bcd, which is the image of xx under the homomorphism that takes x to bcd. We call U Σ - avoidable iff there is an infinite word W on the alphabet Σ that avoids U . If U is Σ -avoidable for some Σ that has ≤ n letters, then U is said to be n -avoidable. Finally, we say that U is avoidable iff U is n -avoidable for some n.

Problem 25 (G. McNulty, around 1974). 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?

So far we know that N ≥ 4 . The following word is 4-avoidable but not 3avoidable:

U = ab · w · bc · x · ca · y · ba · z · ac.

Words that avoid xx are called 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} ≈ x^{3} has a sublattice isomorphic to the infinite partition lattice.

2005 Comment. We now have N ≥ 5 . R. J. Clark proved in 2001 that

W = abebafacgbchcdaidcd

is 5-avoidable but not 4-avoidable (see [7]). Yet it still seems difficult to continue to N ≥ 6 . The 4-avoidable word U written above appears in Baker, McNulty and Taylor [2]. By the way, the dots appearing in our description of U have no mathematical content; they are there simply as punctuation. (See [2] or [7] 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 [46] and [47]; see also the 1944 work of Morse and Hedlund [30]. Avoidance made an appearance in the 1968 Novikov-Adian solution of the Burnside problem—see [1]. The first statement of the general definition appeared in 1979 in Bean, Ehrenfeucht, McNulty—see [4]. An equivalent definition was independently given in 1984 by Zimin [51]. Problem 25 was first published in 1989—see [2].

The Burris-Nelson result mentioned above appears in [6]. For two other interesting algebraic applications of avoidability, see Ježek [19] and Sapir [35].

Problem 26. Do the following conditions on an algebra A imply that A is uniquely factorable under direct product?

(1) A has a one-element subalgebra.

(2) Con A is modular.

(3) Con A has finite height.

Factorization refers here to an isomorphism between A and a product B_{1}×⋯× B_{k}, with each 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 A is finite (Jónsson). There are numerous examples to show that the assertion is false if (1) is not assumed.

2005 Comment. This problem was later stated on page 276 of McKenzie, Mc-Nulty, Taylor [26]. For the Birkhoff-Ore Theorem see [26, Theorem 5.3], and for Jónsson’s Theorem see [26, Theorem 5.4]. The presentation in [26] attempts parallel proofs of the two results, but is nevertheless unable to solve our Problem 26. For some counterexamples that involve possible weakenings of (1–3), see [26, pp. 264–267].

The proof of Jónsson’s Theorem in [26] uses Lemma 4 [26, pp. 270] which states that if A is finite and if α × α′ = β × β′ = α ∧ β′ = α′ ∧ β in Con A , then also α × β′ exists and equals α × α′. It is noted in [26] that if the hypothesis of Lemma 4 could be weakened to Con A is modular and of finite height then Problem 26 would have a positive answer. Freese [11] shows that if there is no homomorphism from the sublattice generated by {α, α′, β, β′} onto M_{4}, then the strengthened Lemma 4 is true. In [12] Freese gives an example showing the desired strengthening of Lemma 4 is false. However, this example is not a counterexample to Problem 26.

Problem 27 (J. Mycielski, G. McNulty et al.). 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?

A semigroup word is a finite sequence of letters a_{1}a_{2}a_{3} ⋯ a_{n} selected from a finite alphabet Σ. It is universal in power κ iff the following is true: for every function F : κ ⟶ κ there exists a map Σ ⟶ κ^{κ}, denoted a ⟼ \overline{a}, such that F = \overline{a}_{1} ∘\overline{a}_{2} ∘⋯∘\overline{a}_{n}. A word is called universal iff it is universal in power κ for every infinite κ. The extension of these definitions to finite or infinite sets of words is more or less obvious. (Given words F_{0} , F_{1} , …, there must exist a single map Σ ⟶ κ^{κ} such that each F_{i} is represented in the manner described above.)

(Let w_{1} , w_{2} , … be a family of words in two letters u and v that is universal in every infinite power κ. (Such a family exists, by Sierpiński [37].) The universality of a_{1}a_{2}a_{3} ⋯ a_{n} in power κ is clearly equivalent to the universality of w_{1}w_{2}w_{3} ⋯ w_{n} (the concatenation of the words w_{i}) in power κ. Thus it is enough to consider the above problems for two letters only, i.e. for |Σ| = 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 κ 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 (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.

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 [29, page 205]. Taylor’s (negative) solution to that problem appeared in 1979—see [42]. 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 [18] and attributed there to Mycielski. The problem is restated in McNulty [29, page 205], and extended there to sets of terms of arbitrary arity (solved by Taylor in [42]). One may consult McNulty [29, §2] for a compendium of most of the known general facts about, and constructions of, universal sets. The open problems there [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 [10] and its references.

Examples of universal sets of terms were presented in 1934 by Sierpiński [37], in 1935 by Banach [3], in 1949 by Hall [15], in 1950 by Łoś [21], and in 1966 by Mal’tsev [24]. 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 [28]

[29] in his studies on algorithmic properties of sets of equations. For universality of terms in the context of topological spaces, see W. Taylor [43, Chapter 4].

One can define universality of group terms by putting the symmetric group on κ in place of the semigroup κ^{κ}. Ore [34] showed the group term xyx^{−1}y^{−1} universal; the set of all universal group terms was determined by Lyndon [23]; see also Dougherty and Mycielski [9].

References

[1] S. I. Adian, The Burnside problem and identities in groups, Springer, New York, 1979.

[2] K. A. Baker, G. F. McNulty, and W. Taylor, Growth problems for avoidable words, Theoret. Comput. Sci. 69 (1989), 319–345.

[3] S. Banach, Sur un théorème de M. Sierpsinski, Fund. Math. 25 (1935), 5–6.

[4] D. R. Bean, A. Ehrenfeucht, and G. F. McNulty, Avoidable patterns in strings of symbols, Pacific J. Math. 85 (1979), 261–294.

[5] S. Bulman-Fleming, On equationally compact semilattices, Algebra Universalis 2 (1972), 146–151.

[6] S. Burris and E. Nelson, Embedding the dual of Π_{∞} in the lattice of equational classes of semigroups, Algebra Universalis 1 (1971–72), 248–253.

[7] R. J. Clark, Avoidable Formulas in Combinatorics on Words, Ph.D. thesis, UCLA, 2001, http://www.math.ucla.edu/∼rclark/thesis.pdf .

[8] J. P. Coleman, Topologies in free algebras, Ph.D. thesis, University of Colorado, 1992. University Microfilms number AAT 9318085.

[9] Randall Dougherty and Jan Mycielski, Representations of infinite permutations by words. II, Proc. Amer. Math. Soc. 127 (1999), 2233–2243.

[10] A. Ehrenfeucht and D. M. Silberger, Universal terms of the form B^{n}A^{m}, Algebra Universalis 10 (1980), 96–116.

[11] R. Freese, Notes on Direct Decompositions, 4 pp., manuscript, http://www.math.hawaii.edu/∼ralph/Notes/dirprod.pdf .

[12] On extending Lemma 4, 3 pp., manuscript, http://www.math.hawaii.edu/∼ralph/Notes/lemma4.pdf .

[13] O. C. Garcia and W. Taylor, The lattice of interpretability types of varieties, Mem. Amer. Math. Soc. 50, 1984, 125 pp.

[14] David K. Haley, Equational compactness in rings. With applications to the theory of topological rings, Lecture Notes in Mathematics, 745, Springer-Verlag, Berlin, 1979. iii+167 pages.

[15] M. Hall, The word problem for semigroups with two generators, J. Symbolic Logic 14 (1949), 115–118.

[16] J. Hyndman, Covers of primal varieties, Algebra Universalis 35 (1996), 167–184.

[17] Covers of some varietal products, Algebra Universalis 37 (1997), 154–184.

[18] J. R. Isbell, On the problem of universal terms, Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 14 (1966), 593–595.

[19] J. Ježek, Intervals in the lattice of varieties, Algebra Universalis 6 (1976), 147–158.

[20] R. T. Kel’tenova, 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).

[21] J.Łoś, Un théorème sur les superpositions des fonctions définies dans les ensembles arbitraires, Fund. Math. 37 (1950), 84–86.

[22] Abelian groups that are direct summands of every Abelian group which contains them as pure subgroups, Fund. Math. 44 (1957), 84–90.

[23] R. C. Lyndon, Words and infinite permutations, Mots 143–152, Lang. Raison. Calc., Hermés, Paris, 1990.

[24] A. I. Mal’tsev, Identical relations of varieties of quasigroups, Mat. Sb. 69 (1966), 3–12 (Russian). Translation: Amer. Math. Soc. Translations, Series 2, 82 (1968), 225–235.

[25] R. McKenzie, On the covering relation in the interpretability lattice of equational theories, Algebra Universalis 30 (1993), 399–421.

[26] R. N. McKenzie, G. F. McNulty, and W. Taylor, Algebras, Lattices, Varieties, Wadworth & Brooks-Cole, Monterey, 1987.

[27] R. McKenzie and S. Świerczkowski, Non-covering in the interpretability lattice of equational theories, Algebra Universalis 30 (1993), 157–170.

[28] G. McNulty, Undecidable properties of finite sets of equations, J. Symbolic Logic 41 (1976), 9–15.

[29] The decision problem for equational bases of algebras, Ann. of Math. Logic 11 (1976), 193–259.

[30] M. Morse and G. Hedlund, Unending chess, symbolic dynamics, and a problem in semigroups, Duke Math. J. 11 (1944), 1–7.

[31] J. Mycielski, Some compactifications of general algebras, Colloq. Math. 13 (1964), 1–9.

[32] J. Mycielski and C. Ryll-Nardzewski, Equationally compact algebras (II ), Fund. Math. 61 (1968), 271–281.

[33] W. D. Neumann, On Mal’cev conditions, J. Aust. Math. Soc. 17 (1974), 376–384.

[34] O. Ore, Some remarks on commutators, Proc. Amer. Math. Soc. 2 (1951), 307–314.

[35] M. Sapir, Inherently non-finitely based semigroups, Mat. Sb. (N.S.), 133 (175) (1987), 154–166, 270 (Russian).

[36] L. Sequeira, Is modularity prime?, Ph.D. thesis, Universidade de Lisboa, 2002. An abstract may be viewed at http://www.lmc.fc.ul.pt/∼lsequeir/math/extabstract.pdf .

[37] W. Sierpiński, Sur les suites infinies des fonction définies dans les ensembles quelconques, Fund. Math. 24 (1934), 209–212.

[38] S. Świerczkowski, Topologies in free algebras, Proc. London Math. Soc. (3) 14 (1964), 566–576.

[39] W. Taylor, Atomic compactness and elementary equivalence, Fund. Math. 71 (1971), 103–112.

[40] On equationally compact semigroups, Semigroup Forum 5 (1972), 81–88.

[41] Residually small varieties, Algebra Universalis 2 (1972), 33–53.

[42] Some universal sets of terms, Trans. Amer. Math. Soc. 267 (1981), 595–607.

[43] The clone of a topological space, Research and Exposition in Mathematics, 13 Helderman Verlag, Berlin, 1986. v+91 pages.

[44] Some very weak identities, Algebra Universalis 25 (1988), 27–35.

[45] Spaces and equations, Fund. Math. 164 (2000), 193–240.

[46] A. Thue, Über unendliche Zeichenreihe, Norske Vid. Selssk. Skr. I, Mat. Nat. Kl. Christiania 7 (1906), 1–22.

[47] Über die gegenseitigen Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selssk. Skr. I, Mat. Nat. Kl. Christiania 1 (1912), 1–67.

[48] V. Trnková and A. Barkhudaryan, Some universal properties of the category of clones, Algebra Universalis 47 (2002), 239–266.

[49] R. B. Warfield Jr., Purity and algebraic compactness for modules, Pacific J. Math. 28 (1969), 699–719.

[50] B. W_{}eglorz, Equationally compact algebras (I ), Fund. Math. 59 (1966), 289–298.

[51] A. I. Zimin, Blocking sets of terms, Mat. Sb. (N.S.) 119 (161) (1982), 363–375, 447 (Russian).