Graphs and Bergman's GK gap theorem (Q1322071)

Using an intricate analysis of the combinatorics of words, Bergman proved that an algebra over a field cannot have Gelfand-Kirillov dimension strictly between 1 and 2. The paper under review clarifies and sharpens this method. Let \(K\) be a field, let \(F = K \langle x_ 1,x_ 2,\dots,x_ n\rangle\) be the free algebra on the letters \(x_ 1,\dots,x_ n\), and let \(A\) be the monomial algebra \(F/I\), where \(I\) is an ideal in \(F\) generated by a set of words in the free monoid on \(x_ 1,\dots, x_ n\). Then the set \(B\) of nonrelation words can be taken to be a basis of \(A\), and for any positive integer \(d\) a directed graph \(\Gamma\) can be constructed whose vertices are the words in \(B\) of length \(d\), and where an arrow is drawn from \(u\) to \(v\) if there exists a word of length \(d + 1\) in \(B\) having \(u\) as prefix and \(v\) as suffix. This graph is related to that of \textit{V. Ufnarovskij} [Mat. Zametki 31, 465- 472 (1982; Zbl 0491.05041)]. The authors prove that each connected component of \(\Gamma\) contains at most one directed circuit and that for each vertex in the component there is at most one directed path leading into or out of the circuit. As a consequence, if the basis \(B\) of the monomial algebra \(A\) contains at most \(d\) words of length \(d\) for some \(d\), then it has at most \((d+ 1/2)^ 2\) words of length \(m\) for any \(m \geq 2d\), improving the bound of \(d^ 3\) obtained by Bergman. An example is provided to show that the above bound is best possible. The authors acknowledge that their results have independently been obtained also by \textit{S. Kobayashi} and \textit{Y. Kobayashi} [Proc. Am. Math. Soc. 119, 1095-1104 (1993; Zbl 0807.16025)].