On the growth of algebras, semigroups, and hereditary languages
- PDF / 288,190 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 52 Downloads / 192 Views
On the growth of algebras, semigroups, and hereditary languages Jason Bell1 · Efim Zelmanov2 Received: 30 July 2019 / Accepted: 22 October 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract We determine the possible functions that can occur, up to asymptotic equivalence, as growth functions of semigroups, hereditary languages, and algebras. Mathematics Subject Classification 16P90 · 20M25
1 Introduction Let S be a semigroup generated by a finite subset X . Consider the function d X (n), defined to be the number of distinct elements in nk=1 X k . Then d X (n) is a weakly increasing function and this is called the growth function of S with respect to the generating set X . If Y ⊆ S is another finite generating subset then since X c ⊇ Y and Y c ⊇ X for some c ≥ 1, we get the inequalities d X (n) ≤ dY (cn)
and
dY (n) ≤ d X (cn).
In light of this fact, it is more natural to only consider functions up to asymptotic equivalence. Given two weakly increasing functions f , g : N → [1, ∞), we say that f is asymptotically greater than or equal to g (written f g or g f ), if there is a positive integer C such that g(n) ≤ f (Cn) for all n. If g f and f g then we say that the functions f and g are asymptotically equivalent ( f ∼ g). If X and Y are finite generating subsets of S then d X (n) ∼ dY (n). Thus, regardless of choice of generating set for S, the growth function lies in a fixed equivalence class and hence we may speak unambiguously of the growth function of S. Let X be a finite alphabet, let X ∗ be the set of all words in X , and let W ⊆ X ∗ . The hereditary language L W (X ) is defined as the set of all words in X that do not contain
B
Jason Bell [email protected] Efim Zelmanov [email protected]
1
Department of Pure Mathematics, University of Waterloo, 200 University Avenue West, Waterloo, ON N2L 3G1, Canada
2
Department of Mathematics, University of California, 9500 Gilman Dr., La Jolla, CA 92093, USA
123
J. Bell, E. Zelmanov
subwords lying in W . The function d(n) that counts all words in L W (X ) of length ≤ n is called the growth function of L W (X ) (see [9,10]). The language L W (X ) can be identified with the set of all nonzero elements in the monomial semigroup with zero X |W . For algebras, one can produce analogous functions as follows. If A is a finitely generated algebra over a field k and V is a finite-dimensional k-vector space that generates A as a k-algebra, then one can produce a function dV (n) = dimk (V n ), where V n is the subspace of A formed by taking the span of all m-fold products of in V , with 1 ≤ m ≤ n. As above, for any two finite-dimensional generating subspaces V and W of the algebra A, we have dV (n) ∼ dW (n). A basic question in the theories of the above classes is: which functions can be realized as growth functions? We start with the following two necessary conditions for a growth function f (n): (i) it is weakly increasing; (ii) it is submultiplicative, i.e., f (m + n) ≤ f (m) f (n) for all m, n. In the case of groups, Gromov’s work [11],
Data Loading...
