Number Theory and Semigroups of Intermediate Growth

From MaRDI portal





The length of an element \(s\in S\) in a semigroup finitely generated by \(A\) is the smallest integer \(m=l_A(s)\) such that \(s\) can be written as the product of \(m\) elements of \(A\). The growth function \(\gamma_A(n)\) of \(S\) with respect to \(A\) counts the number of elements \(s\in S\) of length at most \(n\). The semigroup \(S\) has intermediate (i.e. between polynomial and exponential) growth with respect to \(A\) if, for every positive integer \(k\) and for every real number \(\theta>1\), we have \(n^k<\gamma_A(n)<\theta^n\) for all sufficiently large \(n\). In this note a simple and self-contained proof of the existence of semigroups of intermediate growth is given. The author uses the following upper bound for the Hardy-Ramanujan partition function \(p(n)\): Lemma 1. For every integer \(n\geq 2\), \(p(n)<2n^{2\sqrt n}\). More precisely: Theorem 1. Let \(S\) be the semigroup of \(2\times 2\) matrices generated by the set \(A=\{a,b\}\) where \(a=\left[\begin{smallmatrix} 1 &1\\ 0 &1\end{smallmatrix}\right]\) and \(b=\left[\begin{smallmatrix} 1 &0\\ 1 &0\end{smallmatrix}\right]\). Then \[ 2^{2c_1\sqrt n/\log n}\leq\gamma_A(n)<n^2p(n)<2n^{2\sqrt n+2} \] for some constant \(c_1>0\) and all sufficiently large \(n\). The above semigroup is known, but the proof by means of elementary number theory is new.











This page was built for publication: Number Theory and Semigroups of Intermediate Growth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2757396)