Skip to main content
1 of 5
John Baez
  • 22.3k
  • 3
  • 85
  • 170

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 1}$ 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_1 = 1, \; T_2 = 1, \; T_3 = 1, \; T_4 = 1, \; T_5 = 1, \; T_6 = 2, \; T_7 = 1, \; T_8 = 5, \dots$$

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

There are many such sequences that are not model sequences, since there are only countably many model sequences (since our theory has a finite signature). So, the challenge is just to name one.

There may be easy constraints on model sequences that I haven't noticed. The two I noticed are that we must have $T_0 = 0,1$ (which is why I did not include the zeroth term of the sequence $T_n$) and that the number of $k$-ary operations on an $n$-element set is $n^{n^k}$, which puts an upper bound on the growth rate of $T_n$ (which caused me to include a much harsher upper bound in my question).

John Baez
  • 22.3k
  • 3
  • 85
  • 170