# Are there any "simple" monoids with intermediate growth?

The discovery of the Grigorchuk group which has intermediate growth caused a number of other such groups to be found, but they are all fairly complicated, and as far as I know none of them are finitely presented.

Are there simpler examples of intermediate growth if we drop the requirement that there exists an inverse?

• I'd be curious of a "simple" example that's a submonoid of a group, too.
– YCor
Mar 27, 2021 at 17:52
• @YCor, such an example only exists if a “simple” group example exists. Any cancellative semigroup of subexponential growth is amenable and is Ore and so has a group of fractions. Clearly the group of fractions is just as “simple". Mar 27, 2021 at 20:33
• @BenjaminSteinberg but the group of fractions might have exponential growth, mightn't it?
– YCor
Mar 27, 2021 at 20:34
• @YCor, That would surprise me but I must think about it. How far can the fraction form be from a geodesic? Mar 27, 2021 at 20:39
• @YCor, I know Grigorchuk proved for cancellative semigroups of polynomial growth the group of fractions also has polynomial growth but the paper is in Russian so I don't know if it would prove the group of fractions of a cancelative monoid of intermediate growth is intermediate. Mar 27, 2021 at 20:48

Yes. Jan Okninski showed that $$\begin{bmatrix} 1 & 1 \\ 0 &1\end{bmatrix}\ \text{and}\ \begin{bmatrix} 1 & 0\\ 1 & 0\end{bmatrix}$$ generate a semigroup of intermediate growth. Details can be found in Nathanson. The growth was estimated there to be like the Hardy-Ramanujan estimate of the partition function. An exact asymptotic growth rate of $$e^{\sqrt{n/\log n}}$$ was obtained for this semigroup by Lavrik-Mannnlin.

There are also finitely presented examples. The simplest example I know is Yuji Kobayashi. A finitely presented monoid which has solvable word problem but has no regular complete presentation. Theoret. Comput. Sci., 146(1-2):321–329, 1995.. This example is almost cancellative. It has a zero but you can cancel whenever neither product is zero. The growth is essentially the same as Okninski’s example. The first finitely presented example is due to James Shearer (James B. Shearer. A graded algebra with a nonrational Hilbert series. J. Algebra, 62(1):228– 231, 1980) and in a note added in proof he gives essentially the same presentation as Kobayashi but without proof. The generators are $$a,b,c,0$$ and the relations are $$0x=0=x0$$ for $$x$$ any generator and $$ab=ba$$, $$bc=aca$$ and $$acc=0$$.

One can also build monomial examples easily that are not finitely presented. Take any infinite word $$w$$ over a finite alphabet $$A$$ whose factor complexity has intermediate growth (these exist for example here) and take the quotient of the free semigroup on $$A$$ by the ideal of all words not appearing as a factor in $$w$$. This is I believe the oldest construction due to Govorov I believe.

• Are there any explicit superpolynomial lower bound and subexponential upper bound (asympotically) for the Okninski example? None seems mentioned in the linked survey (end of p3 – beginning of p4).
– YCor
Mar 27, 2021 at 16:29
• @YCor, this is known but I linked the wrong Nathanson paper. I'll fix Mar 27, 2021 at 16:44
• @YCor, I changed the link to the correct Nathanson paper where the information is in theorem 1 Mar 27, 2021 at 16:45
• Thanks: it gives $\exp(c\sqrt{n}/\log n)\le b(n)\le 2n^2\exp(2\sqrt{n}\log n)$ for $n\gg 1$.
– YCor
Mar 27, 2021 at 16:52
• @YCor, the exact growth of that semigroup is known. I'll add it. Mar 27, 2021 at 17:49