Normal bases of PI-algebras. (Q863320)

This is a survey on selected aspects of the algorithmic theory of PI-algebras, in terms of normal bases of affine (finitely generated) algebras, with indication of directions for further research, written by three of the leading experts in the field. Let \(\Omega=\{a_1,\dots,a_l\}\) be a finite set of symbols and let \(\Omega^*\) be the set of all words in \(\Omega\), equipped with the deg-lex order. The normal base of the associative algebra \(A\) generated by \(\Omega\) over an infinite field \(k\) is the set of all words in \(\Omega^*\) which cannot be written as linear combinations of smaller words. The first topic of the survey is the relation between normal bases with different versions of the Shirshov height theorem. The latter gives that the affine PI-algebra \(A\) behaves like a finitely generated module over a polynomial algebra: If \(A\) satisfies a polynomial identity of degree \(d\), then it is spanned by products \(y_1^{m_1}\cdots y_t^{m_t}\), where \(y_i\) is a word of length \(<d\) and \(t\leq h\). The minimal \(h\) with this property is called the height of \(A\). An improved version of the Shirshov theorem replaces the estimate \(<d\) for the length of \(y_i\) with the inequality \(\leq n\) if the matrix algebra \(M_{n+1}(k)\) does not satisfy all polynomial identities of \(A\). Another version involves the notion of essential height, when \(A\) is spanned by products \(s_0y_1^{m_1}s_1\cdots s_{t-1}y_t^{m_t}s_t\) and \(s_i\) belongs to a fixed finite subset of \(\Omega^*\). Among the consequences of the Shirshov theorem is the theorem of Berele that affine PI-algebras have finite Gelfand-Kirillov dimension. By the theory of Kemer finitely generated relatively free algebras are representable, i.e., isomorphic to a subring of \(M_n(F)\) for a field \(F\). The Gelfand-Kirillov dimension of a representable algebra is equal to the essential height. Further, the authors discuss monomial algebras and their representability. The final topic of the article is the isomorphism problem for subalgebras of matrix algebras with polynomial entries. The problem is algorithmically unsolvable in characteristic 0. On the other hand, the authors show that the isomorphism problem for monomial subalgebras of matrix algebras in positive characteristic (defined in terms of their generators) is algorithmically solvable. The paper concludes with several conjectures relating representable algebras, formal languages, and Shirshov's height theorem.