Narrow Results

We show that if G ≤ S_A is a permutation group on a finite set A satisfying |A| ≥ 3, then the set of G-closed clones on A that contain all constant operations is finite iff G = S_A, A_A, AGL(1,5) (|A| = 5), PSL(2,5) (|A| = 6), PGL(2,5) (|A| = 6), PGL(2,7) (|A| = 8), PGL(2,8) (|A| = 9), or PΓL(2,8) (|A| = 9).

In 1999, Bergman et al. showed that the following two problems are EXPTIME-complete: GENCLO, which decides whether an operation on a finite set A belongs to a clone generated by a finite set of operations on A; and TERMEQUIV, which decides whether two algebras on the same finite set and with finitely many fundamental operations are term-equivalent. However, the proof of one of the key statements was not correct. Using the techniques proposed by Bergman et al., in this paper we present the correct proof.

Algebras on the natural numbers and their clones of term operations can be classified according to their descriptive complexity. We give an example of a closed algebra which has only unary operations and whose clone of term operations is not Borel. Moreover, we provide an example of a coatom in the clone lattice whose obvious definition via an ideal of subsets of natural numbers would suggest that it is complete coanalytic, but which turns out to be a rather simple Borel set.

A finite unary algebra of finite type with a constant function 0 that is a one-element subalgebra, and whose operations have range {0, 1}, is called a {0, 1}-valued unary algebra with 0. Such an algebra has a finite basis for its quasi-equations if and only if the relation defined by the rows of the nontrivial functions in the clone form an order ideal.

For $n$ a positive integer and $K$ a finite set of finite algebras, let $L(n,K)$ denote the largest $n$-generated subdirect product whose subdirect factors are algebras in $K$. When $K$ is the set of all $n$-generated subdirectly irreducible algebras in a locally finite variety ${𝒱}$, then $L(n,K)$ is the free algebra $F_{{𝒱}}(n)$ on $n$ free generators for ${𝒱}$. For a finite algebra $A$ the algebra $L(n,\{A\})$ is the largest $n$-generated subdirect power of $A$. For every $n$ and finite $A$ we provide an upper bound on the cardinality of $L(n,\{A\})$. This upper bound depends only on $n$ and these basic parameters: the cardinality of the automorphism group of $A$, the cardinalities of the subalgebras of $A$, and the cardinalities of the equivalence classes of certain equivalence relations arising from congruence relations of $A$. Using this upper bound on $n$-generated subdirect powers of $A$, as $A$ ranges over the $n$-generated subdirectly irreducible algebras in ${𝒱}$, we obtain an upper bound on $|F_{{𝒱}}(n)|$. And if all the $n$-generated subdirectly irreducible algebras in ${𝒱}$ have congruence lattices that are chains, then we characterize in several ways those ${𝒱}$ for which this upper bound is obtained.

A classical theorem of Baker and Pixley states that if $A$ is a finite algebra with a majority term and $f$ is an $n$-ary operation on $A$ which preserves every subuniverse of $A\times A$, then $f$ is representable by a term in $A$. We give a generalizacion of this theorem for the case in which $A$ is a finite algebra belonging to some relatively congruence distributive quasivariety.

We prove that there are continuum many clones on a three-element set even if they are considered up to homomorphic equivalence. The clones we use to prove this fact are clones consisting of self-dual operations, i.e. operations that preserve the relation $\{(0,1),(1,2),(2,0)\}$. However, there are only countably many such clones when considered up to equivalence with respect to minor-preserving maps instead of clone homomorphisms. We give a full description of the set of clones of self-dual operations, ordered by the existence of minor-preserving maps. Our result can also be phrased as a statement about structures on a three-element set: we give a full description of the structures containing the relation $\{(0,1),(1,2),(2,0)\}$, ordered by primitive positive constructability, because there is a minor-preserving map from the polymorphism clone of a finite structure $𝔄$ to the polymorphism clone of a finite structure $𝔅$ if and only if there is a primitive positive construction of $𝔅$ in $𝔄$.

Two algebraic structures with the same universe are called term-equivalent if they have the same clone of term operations. We show that the problem of determining whether two finite algebras of finite similarity type are term-equivalent is complete for deterministic exponential time.