Return to Question

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 = 1, \; 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,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.

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.

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 = 2, \; 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).

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 = 1, \; 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,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.

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).

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 = 2, \; 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).