Number Theory and Semigroups of Intermediate Growth
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.
- Additive number theory and linear semigroups with intermediate growth.
- Special semi-groups in elementary number theory
- Number theory of matrix semigroups
- On numerical semigroups
- On numerical semigroups
- ON SOME SEMIGROUPS OF INTERMEDIATE GROWTH
- On Semigroups of Intermediate Growth
- Numerical semigroups of Szemerédi type
- Dynamical height growth: left, right, and total orbits
- The smallest Mealy automaton of intermediate growth.
- ON SOME SEMIGROUPS OF INTERMEDIATE GROWTH
- Additive number theory and linear semigroups with intermediate growth.
- The branching number of intermediate growth trees
- The number of boundedly generated semigroups is super-exponential in the cardinality
- On the 3-state Mealy automata over an \(m\)-symbol alphabet of growth order \([n^{\log n/2\log m}]\).
- Semigroups of matrices of intermediate growth.
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)