# Sequences that don't count algebraic structures on finite sets

People count $$n$$-element groups, $$n$$-element monoids, $$n$$-element commutative monoids, etcetera - always up to isomorphism. The algebraic structures I've listed, and many more, are studied systematically in universal algebra. In this subject any theory $$T$$ with a finite signature - loosely, any finite collection of finitary operations obeying equational laws - will give a sequence $$(T_n)_{n \ge 0}$$ where $$T_n$$ is the number of isomorphism classes of algebras of $$T$$ having $$n$$ elements. Andrej Bauer dubbed $$T_n$$ the model sequence of the theory $$T$$.

For example, if $$T$$ is the theory of groups we have

$$T_0 = 0, \; T_1 = 1, \; T_2 = 1, \; T_3 = 1, \; T_4 = 2,$$ $$T_5 = 1, \; T_6 = 2, \; T_7 = 1, \; T_8 = 5, \dots$$

My (revised) question is: what are all the constraints on sequences $$(a_n)_{n \ge 1}$$ of natural numbers that are model sequences?

There may be easy constraints on model sequences that I haven't noticed. The two I noticed are:

• we must have $$T_0 = 0$$ or $$T_0 = 1$$.

• the number of $$k$$-ary operations on an $$n$$-element set is $$n^{n^k}$$, which leads to an upper bound on the growth rate of $$T_n$$, given that there are only finitely many operations.

• A constraint: if $T_n,T_m\neq 0$ then $T_{nm}\neq 0$.
– YCor
Sep 7 at 12:39
• Even more so, $T_{nm} \leq (nm)! T_n T_m$ since $T_n$ is the lower bound for the number of algebras having $n$ elements not up to isomorphism, that sequence is supermultiplicative, and $T_n n!$ is an upper bound for the number of algebras having $n$ elements not up to isomorphism. This bound can surely be improved: I think $T_2 (T_2+1) /2 \leq 3 T_4$ since each four-element algebra can be written as a product of two two-element algebras (without ordering them) in at most 3 ways. Sep 7 at 13:39
• Why is T0 for groups equal to 1. I believe the empty set is not a group because a group has a zero-ary operation the identity Sep 7 at 18:48
• I've always been impressed that while there are 5 isomorphism classes of groups of order 8, there are 3,684,030,417 isomorphism classes of semigroups of order 8. Seems quite extraordinary to me. (Sloane A027851) Sep 7 at 20:23
• The usual term for a "model sequence" is the fine spectrum of a universal algebraic variety; the spectrum being the set of indices on which the fine spectrum is non-zero (e.g. Boolean algebras have spectrum $\{2^n\mid n\in\mathbb{N}\}$, and the fine spectrum takes the value 1 on any of these indices). You can put immediate constraints on fine spectra using the fact that algebraic structures are closed under products, but in 1979 Taylor wrote that characterization of such functions seems hopeless: it appears this hasn't changed yet. Sep 8 at 4:33

The original question was:

My question is: can anyone name a sequence $$(a_n)_{n\geq 1}$$ of natural numbers that grows more slowly than exponentially, yet is not a model sequence?

Any model sequence $$(a_n)_{n\geq 1}$$ must satisfy $$a_n\leq a_{n^k}$$ for all $$n, k\geq 1$$. This follows from Theorem 4.2 of

Operations with structures
László Lovász
volume 18, (1967) 321-328

which states:

(4.2) If $$A$$ and $$B$$ are finite structures and $$A^n\cong B^n$$, then $$A\cong B$$.

One applies Lovasz's Theorem as follows to prove the inequality $$a_n\leq a_{n^k}$$. Assume that $$A_1, \ldots, A_{a_n}$$ is a list of algebras in the variety which represents all isomorphism types of $$n$$-element algebras. Then $$A_1^k, \ldots, A_{a_n}^k$$ is a list of $$n^k$$-element algebras which represent distinct isomorphism types of $$n^k$$-element algebra. This shows that $$a_n\leq a_{n^k}$$.

One can use this to exhibit an explicit sub-exponential sequence that is not a model sequence, such as the almost-constant sequence $$(a_{n})_{n\geq 1}$$ where $$a_n = 17$$ for all $$n$$ except that $$a_{25}=3$$. (For then, $$a_5\not\leq a_{5^2}$$.)

A paper relevant to this question is

The fine spectrum of a variety
Walter Taylor
Algebra Univ. 5 (1975) 263-303

Taylor introduces the fine spectrum of a variety $$\mathcal V$$ as follows: $$f_{\mathcal V}(\lambda) = \textrm{the number of isomorphism types of \mathcal V-algebras of size \lambda.}$$ Taylor was interested in those varieties with finitely many isomorphism types of algebras of size $$n$$ for any $$n\in\omega$$. (Let me call these finite-ish varieties. Any variety defined with finitely many basic operations is finite-ish.) If $$\mathcal V$$ is finite-ish, then $$f_{\mathcal V}\in \omega^{\omega}$$ (the Baire space). Taylor asks: Let $$F\subseteq \omega^{\omega}$$ be the set of fine spectra of finite-ish varieties. Is $$F$$ closed in $$\omega^{\omega}$$?

This question is still open. In the 1980's, both Ralph McKenzie and I proved independently that the topological closure of $$F$$ in $$\omega^{\omega}$$ is the set $$P$$ = the set of fine spectra of all finite-ish pseudovarieties. (A pseudovariety is a class of finite algebras closed under the formation of homomorphic images, subalgebras, and finite products.) What remains to determine is whether $$F=P$$.

Because it's too long for a comment I'll post this as an answer: I just want to provide Omar Antolín's nice proofs of the following facts. These facts probably go back to this paper:

but Lovász did not phrase them using category theory.

Theorem 1. Suppose $$T$$ is a Lawvere theory having finitely many isomorphism classes of algebras of cardinality $$n$$ for each $$n \in \mathbb{N}$$. If $$(a_n)_{n \ge 0}$$ is the number of isomorphism classes of algebras of cardinality $$n$$, then

$$a_{n^k} \ge a_n$$

for each $$n, k \in \mathbb{N}$$.

This follows easily from

Theorem 2. Let $$A, B$$ be two algebras of a Lawvere theory whose underlying sets are finite. If $$A^k \cong B^k$$ for some natural number $$k$$ then $$A \cong B$$.

Theorem 2 in turn follows from this lemma:

Super-Yoneda Lemma. Let $$\mathsf{C}$$ be the category of algebras of some Lawvere theory, and let $$A, B \in \mathsf{C}$$ be two algebras whose underlying sets are finite. If the functors $$\mathrm{hom}(-,A)$$ and $$\mathrm{hom}(-,A)$$ are unnaturally isomorphic, then $$A \cong B$$.

Here we say the functors $$\mathrm{hom}(-,A)$$ and $$\mathrm{hom}(-,B)$$ are unnaturally isomorphic if

$$\mathrm{hom}(X,A) \cong \mathrm{hom}(X,B)$$

for all $$X \in \mathsf{C}$$. We're not imposing the usual naturality condition involving a commuting square — indeed we can't, since we're not even giving any specific choice of isomorphism!

If $$A$$ and $$B$$ are objects in any category and $$\mathrm{hom}(-,A)$$ and $$\mathrm{hom}(-,B)$$ naturally isomorphic, we can show $$A \cong B$$ using the Yoneda Lemma. But when they're unnaturally isomorphic, we need to use the Super-Yoneda Lemma, which has more restrictive hypotheses.

Here's how the Super-Yoneda Lemma implies Theorem 2.. Since $$A^k \cong B^k$$, we have natural isomorphisms

$$\mathrm{hom}(-,A)^k \cong \mathrm{hom}(-, A^k) \cong \mathrm{hom}(-, B^k) \cong \mathrm{hom}(-,B)^k$$

so for any $$X \in \mathsf{C}$$ the sets $$\mathrm{hom}(X,A)^k$$ and $$\mathrm{hom}(X,B)^k$$ have the same cardinality. This means we have an unnatural isomorphism

$$\mathrm{hom}(-,A) \cong \mathrm{hom}(-,B)$$

The lemma then lets us conclude that

$$A \cong B$$

Next let's turn to the lemma. I'll just quote Omar Antolín's proof, since I can't improve on it. Remember, $$A$$ and $$B$$ are algebras of some Lawvere theory whose underlying sets are finite:

Let $$\mathrm{mon}(X, A)$$ be the set of monomorphisms, which here are just homomorphisms that are injective functions. I claim you can compute the cardinality of $$\mathrm{mon}(X, A)$$ using the inclusion-exclusion principle in terms of the cardinalities of $$\mathrm{hom}(Q, A)$$ for various quotients of $$X$$.

Indeed, for any pair of elements $$x, y \in X$$, let $$S(x, y)$$ be the set for homomorphisms $$f \colon X \to A$$ such that $$f(x) = f(y)$$. The monomorphisms are just the homomorphisms that belong to none of the sets $$S(x, y)$$, so you can compute how many there are via the inclusion-exclusion formula: you'll just need the cardinality of intersections of several $$S(x_i, y_i)$$.

Now, the intersection of some $$S(x_i, y_i)$$ is the set of homorphisms $$f$$ such that for all $$i$$, $$f(x_i) = f(y_i)$$. Those are in bijection with the homorphisms $$Q \to A$$ where $$Q$$ is the quotient of $$X$$ obtained by adding the relations $$x_i=y_i$$ for each $$i$$.

So far I hope I've convinced you that if $$\mathrm{hom}(-, A)$$ and $$\mathrm{hom}(-, B)$$ are unnaturally isomorphic, so are $$\mathrm{mon}(-, A)$$ and $$\mathrm{mon}(-, B)$$. Now it's easy to finish: since $$\mathrm{mon}(A, A)$$ is non-empty, so is $$\mathrm{mon}(A, B)$$, so $$A$$ is isomorphic to a subobject of $$B$$. Similarly $$B$$ is isomorphic to a subobject of $$A$$, and since they are finite, they must be isomorphic.

If you examine this argument you'll see we didn't use the full force of the assumptions. We didn't need $$A$$ and $$B$$ to be algebras of a Lawvere theory. They could have been topological spaces, or posets, or simple graphs, or various other things. It seems all we really need is a category $$\mathsf{C}$$ of gadgets with a forgetful functor

$$U \colon \mathsf{C} \to \mathsf{FinSet}$$

that is faithful and has some extra property... roughly, that we can take an object in $$\mathsf{C}$$ and take a quotient of it where we impose a bunch of extra relations $$x_i = y_i$$, and maps out of this quotient will behave as you'd expect. More precisely, I think the extra property is this:

Given any $$X \in \mathsf{C}$$ and any surjection $$p \colon U(X) \to S$$, there is a morphism $$j \colon X \to Q$$ such that the morphisms $$f \colon X \to A$$ that factor through $$j$$ are precisely those for which $$U(f)$$ factors through $$p$$.

I would like to understand this better. This paper should help:

but I haven't had time to absorb it yet. Here's the abstract:

A classical result due to Lovasz (1967) shows that the isomorphism type of a graph is determined by homomorphism counts. That is, graphs $$G$$ and $$H$$ are isomorphic whenever the number of homomorphisms from $$K$$ to $$G$$ is the same as the number of homomorphisms from $$K$$ to $$H$$ for all graphs $$K$$. Variants of this result, for various classes of finite structures, have been exploited in a wide range of research fields, including graph theory and finite model theory.

We provide a categorical approach to homomorphism counting based on the concept of polyadic (finite) set. The latter is a special case of the notion of polyadic space introduced by Joyal (1971) and related, via duality, to Boolean hyperdoctrines in categorical logic. We also obtain new homomorphism counting results applicable to a number of infinite structures, such as finitely branching trees and profinite algebras.

• Typo in Theorem 1? $a_{n^k}\ge a_n$ rather than $\le$. This was the main contents of Keith Kearnes' answer, by the way.
– YCor
Sep 9 at 17:40