On the growth of algebras, semigroups, and hereditary languages (Q2030397)

Let \(X\) be a finite alphabet, consider a subset \(W\) in the set of all words \(X^*\). The \textit{hereditary language} \(L_W (X)\) is defined as the set of all words in \(X\) that do not contain a subword lying in \(W\). The function that counts all words in \(L_W (X)\) of length \(\le n\) is called the \textit{growth function} of the language. Similarly one defines the growth functions of semigroups and algebras. Given two weakly increasing functions \(f ,g : \mathbb N \to [1,\infty)\), then write \(g\prec f\), if there is a positive integer \(C\) such that \(g(n) \le f (Cn)\) for all \(n\). If \(g \prec f\) and \(f \prec g\) then the functions \(f, g\) are said \textit{asymptotically equivalent} (\(f \sim g\)). Given a map \(F : \mathbb N \to \mathbb N\), consider its \textit{(discrete) derivative} \(F'(n) := F(n)-F(n -1)\), \(F '(0) := F(0)\). \par An arbitrary \textit{submultiplicative} (i.e. \(f(n+m)\le f(n)f(m)\) for all \(n,m\)) increasing function satisfying \(f (n)\succeq n ^{\log(n)}\) is asymptotically equivalent to a growth function of an associative algebra [\textit{A. Smoktunowicz} and \textit{L. Bartholdi}, Q. J. Math. 65, No. 2, 421--438 (2014; Zbl 1312.16017)]. A similar result was obtained for simple associative algebras [\textit{B. Greenfeld}, J. Algebra 489, 427--434 (2017; Zbl 1380.16020)]. \par Improving the result above, the authors completely describe possible growth functions of semigroups, hereditary languages, and associative algebras as follows. Theorem. A growth function of an associative algebra is asymptotically equivalent to a constant function, a linear function, or a weakly increasing function \(F : \mathbb N \to \mathbb N\) with the following properties: (i) \(F'(n) \ge n + 1\) for all \(n\); (ii) \(F'(m) \le F'(n)^ 2\) for \(n \ge 1\) and \(m\in \{n,\ldots ,2n\}\). Conversely, if \(F(n)\) is either a constant function, a linear function, or a weakly increasing function with the above properties then it is asymptotically equivalent to the growth function of a hereditary language. In particular, this gives a complete characterization of the functions that can occur as the growth function of an associative algebra, a semigroup, and of a hereditary language. \par We cite the following result on possible weird growth functions for Lie algebras. For any prime characteristic, restricted Lie algebras of intermediate oscillating growth were constructed, namely, their growth oscillate between a function with the Gelfand-Kirillov dimension one and the function \(\exp( n/ (\ln n)^{\lambda})\), \(\lambda\) being a constant. Moreover, these restricted Lie algebras have a nil \(p\)-mapping [the reviewer, J. Algebra 588, 349--407 (2021; Zbl 1482.17043)].