# Growth and relations in graded rings

## 1 Introduction

Let $`k`$ be a field. We will call a vector $`k`$–space, a $`k`$–algebra, or $`k`$–algebra module graded, if it is $`𝐙_+`$–graded and finite–dimensional in every component. For a such space $`V`$ (in particular, $`V`$ may be an algebra or a module) we denote by $`V(x)`$ its Hilbert series $`\underset{i0}{}\text{dim }V_ix^i`$. A graded algebra $`A=A_0A_1\mathrm{}`$ is called connected, if its zero component $`A_0`$ is $`k`$; a connected algebra is called standard, if it is generated by $`A_1`$ and a unit.

The word ”algebra” below denotes an associative graded algebra. All inequalities between Hilbert series are coefficient–wise, i. e., we write $`_ia_it^i_ib_it^i`$ iff $`a_ib_i`$ for all $`i0`$.

We are interested in the following situation. Suppose $`A`$ is a graded algebra, $`\alpha A`$ is a subset consisting of homogeneous elements such that $`\alpha `$ minimally generates an ideal $`IA`$, and $`B=A/I`$. What can we say about relations of the Hilbert series $`A(t),B(t)`$, and the generating function $`\alpha (t)`$?

If $`A`$ is a free associative algebra, then a partial answer is given by Golod–Shafarevich theorem (see \[GSh\] or Corollary 2 below). In particular, it follows that if the number of elements of $`\alpha `$ of every degree is sufficiently small, then $`B`$ is infinite-dimensional \[GSh\] (moreover, if in this case $`A`$ is standard, then $`B`$ grows exponentially \[P\]). On the other hand, V. E. Govorov (see \[Gov\] or Theorem 5 below) gives some estimates for a number of relations $`\mathrm{\#}\alpha `$, whenever $`B(t)`$ is known (if all elements of $`\alpha `$ have the same degree).

Our first goal is to demonstrate that the equality cases in the Golod–Shafarevich theorem and in both of Govorov’s inequalities coincide (Theorem 6). Sets $`\alpha `$ such that equality holds are called strongly free \[A1\], or inert \[HL\]; they are non-commutative analogues of regular sequences in commutative ring theory \[A1\], \[Gol\]. If $`A`$ is free, then the set $`\alpha A`$ of homogeneous elements is strongly free iff

$$\text{gl. dim }A/id(\alpha )2.$$

In the general case of an arbitrary connected algebra $`A`$, the property of being strongly free is defined by certain conditions on Hilbert series \[A1\]. E. g., for every set of homogeneous elements $`\alpha A`$ the following inequality holds:

$$(Bk\alpha )(t)A(t);$$

the equality holds iff $`\alpha `$ is strongly free (where star denotes a free product of algebras).

As for our question in the case of an arbitrary algebra $`A`$, we need to consider an asymptotical characteristics of the algebra’s growth. General graded algebras (even finitely generated ones) have exponential growth, so, for a such algebra $`A`$, $`\text{GK–dim }A=\mathrm{}`$. Let us introduce the following analogue of Gelfand–Kirillov dimension: if $`a_i=\text{dim }A_i`$, then define the exponent of growth of $`A`$ by

$$p(A)=inf\{q>0|c>0n0a_ncq^n\}.$$

At least for a finitely generated algebra $`A`$, $`p(A)`$ is finite. If $`A(t)`$ is known, it is clear how to compute $`p(A)`$: if $`r(A)`$ is a radius of convergence of the series $`A(t)`$, then

$$p(A)=\overline{lim}\sqrt[n]{a_n}=r(A)^1.$$

Notice that $`p(A)`$ depends of the grading on $`A`$ (for example, if $`A=kx,y|\text{deg }x=\text{deg }y=d`$, then $`p(A)=\sqrt[d]{2}`$ depends of $`d`$), so it is not a “dimension” in the usual sense.

It is proved in \[A2\] that over a field of zero characteristic there is no algorithm to decide whether or not a given quadratic subset of standard free algebra is strongly free. Using this fact and our criteria for strongly free sets, we proved in Section 4 the following. Let $`R`$ be a finitely presented standard $`s`$–generated algebra with a set of relations $`\alpha `$. Then for some particular $`s,\alpha `$ for some rational numbers $`q,r`$ there is no algorithm to decide, when $`\alpha `$ is given, whether or not $`R(q)=r`$. Moreover, for some integer $`n`$ there is no algorithm to decide, when $`\alpha `$ is given, whether or not $`p(R)=n`$. It means that in the simplest case that the algebra $`A`$ is free and standard, even the asymptotical version of our question is undecidable in general.

In Section 5 below we introduce a concept of extremal algebra: specifically, a graded algebra $`A`$ is called extremal, if for any proper quotient $`B=A/I`$

$$p(B)<p(A).$$

If $`A`$ is an extremal algebra, then it is prime (Theorem 13), and $`p(A)`$ is finite (Proposition 12). Any free product of two connected algebras is extremal (Theorem 15), as is any algebra that includes a strongly free set (Corollary 17).

Using extremality, we generalize Govorov’s inequality for an arbitrary connected algebra $`A`$ (Theorem 19): if $`A(t)`$ and $`B(t)`$ are known, we obtain an estimate for the generating function $`\alpha (t)`$. Also, we find a new characterizing of strongly free sets in terms of algebras’ growth (Proposition 18, Theorem 19): if a set $`\alpha `$ is strongly free, then not only the Hilbert series $`A(t)`$, but also the exponent of growth $`p(A)`$ is as small as possible. This characterizing generalizes the one of D. Anick \[A1, theorem 2.6\].

I am grateful to Professor E. S. Golod for fruitful discussions.

## 2 Golod–Shafarevich theorem and homology

Let $`R=R_0R_1\mathrm{}`$ be a standard associative algebra. Suppose a set $`\{x_1,\mathrm{},x_s\}`$ is a basis in the space $`R_1`$. Then $`R=F/I`$, where $`F=kx_1,\mathrm{},x_s=T(R_1)`$ is a free associative algebra, $`IF`$ is a two–sided ideal generated by homogeneous elements of degrees $``$ 2. Let $`\alpha =\{f_1,f_2,\mathrm{}\}`$ be a minimal system of generators of $`I`$, and let $`u=k\alpha I/PI+IP`$ be a vector space generated by $`\alpha `$ (here $`P=F_1F_2\mathrm{}`$ is an augmentation ideal of $`F`$).

Suppose

$$0k\stackrel{d_0}{}RH_0\stackrel{d_1}{}RH_1\stackrel{d_2}{}\mathrm{}$$
(1)   
be a minimal free left $`R`$–resolution of $`k`$; here $`H_i\text{Tor }_i^R(k,k)=H_i(R),`$ i. e.

$$H_0=k,H_1R_1,H_2u$$

etc.

Let $`\mathrm{\Omega }^i=\text{Coker }d_{i1}`$ be the $`i`$–th syzygy module. Since the Hilbert series of a tensor product is a product of the factors’ Hilbert series, using the Euler formula for the exact sequence

$$0k\stackrel{d_0}{}RH_0\stackrel{d_1}{}\mathrm{}\stackrel{d_i}{}RH_i\mathrm{\Omega }^i0$$

we obtain the following

###### Proposition 1

There is an equality of formal power series

$$R(x)(1sx+u(x)H_3(x)+\mathrm{}+(1)^iH_i(x))=1+(1)^i\mathrm{\Omega }^i(x).$$

In particular, there are inequalities

$$R(x)(1H_0(x)+\mathrm{}H_{2i1}(x))1,$$

$$R(x)(1H_0(x)+\mathrm{}+H_{2i}(x))1;$$

equalities hold iff $`\text{gl. dim }R2i1`$ (respectively, $`\text{gl. dim }R2i`$).

###### Corolary 2 (Golod–Shaferevich theorem)

There is an inequality

$$R(x)(1sx+u(x))1.$$
(2)   
Equality holds iff $`\text{gl. dim }R2`$.

The inequality is proved in \[GSh\], the equality condition is proved in \[A1\]. A non-empty set $`\alpha `$ such that the equality above holds is called strongly free, or inert in $`F`$; since in our case $`\alpha `$ is not empty, these properties are equivalent to the equality $`\text{gl. dim }R=2`$.

The equality $`R(x)(1sx+u(x))=1\mathrm{\Omega }^3(x)`$ shows that for a finitely presented algebra $`R`$ we can compute the Hilbert series $`R(x)`$ whenever $`\mathrm{\Omega }^3(x)`$ is known. So it is interesting to study the module $`\mathrm{\Omega }^3`$.

###### Proposition 3

Denote by $`L=F\alpha F`$ the left ideal generated by $`\alpha `$. There is an isomorphism of left $`R`$–modules

$$\mathrm{\Omega }^3\text{Tor }_1^F(R,P/L).$$

Proof Suppose $`\{u_1,\mathrm{},u_s|\text{deg }u_i=1\}`$ is a basis of the space $`H_1`$ and $`\{r_1,r_2,\mathrm{}|\text{deg }r_i=\text{deg }f_i\}`$ is a basis of $`H_2`$. Then we may assume that the map $`d_2`$ in the resolution (1) is given by the following way: if $`f_i=\underset{j=1}{\overset{n}{}}a_i^jx_j,`$ then $`d_2(r_i)=\underset{j=1}{\overset{n}{}}\overline{a_i^j}u_j,`$ where the overbar denotes the image of an element of $`F`$ in $`R`$.

On the other hand, since any left ideal in a free algebra is a free module, taking the long sequence of graded $`\text{Tor }_{}^F(R,P/L)`$ we obtain:

$$0\text{Tor }_1^F(R,P/L)R\underset{F}{}L\stackrel{\varphi }{}R\underset{F}{}PR\underset{F}{}P/L0.$$

Here $`R\underset{F}{}LRu,`$ $`R\underset{F}{}PRR_1.`$ So the map $`\varphi `$ induced by the inclusion $`LP`$ coinsides with the map $`d_2`$ above. Therefore,

$$\text{Tor }_1^F(R,P/L)\text{Ker }d_2\mathrm{\Omega }^3.$$

###### Corolary 4

The non-empty set $`\alpha `$ is strongly free iff $`\text{Tor }_1^F(R,P/L)=0`$.

Remark

All results of this section hold for an arbitrary connected algebra $`R`$. The only change is to replace in all formulae the term $`sx`$ by a generating function in the algebra’s generators $`_{i1}t^{\text{deg }x_i}`$.

## 3 Estimates for the number of relations

We keep the notation of the previous section.

Suppose that the ideal $`I`$ is minimally generated by $`t`$ ($`t>0`$) elements of degree $`l`$, i. e., $`\alpha =\{f_1,\mathrm{},f_t|\text{deg }f_i=l\}`$. Let $`a_i`$ denote the dimension of the space $`R_i`$:

$$R(x)=\underset{i0}{}a_ix^i.$$

In the situation above, V. E. Govorov proved the following theorem.

###### Theorem 5 (\[Gov\])

The series $`R(x)`$ converges for $`x=s^1`$. The following inequalities hold:

$$t\frac{s^l}{R(s^1)}$$
(3)   
and

$$t\frac{sa_{n1}a_n}{a_{nl}}$$
(4)   
for all possible $`n`$. Equality holds in (4) for all possible $`n`$ if and only if $`\text{Tor }_1^F(R,P/L)=0`$.

The following theorem shows that the equality hold simultaneously in (3), (4), and the Golod–Shafarevich theorem.

###### Theorem 6

The following conditions are equivalent:

(i) The set $`\alpha `$ is strongly free.

(ii) Equality holds in (3).

(iii) Equality holds in (4) for all possible $`n`$.

Proof

The implications $`(i)(iii)`$ follow immediately from Corollary 4 and Theorem 5. Let us prove $`(i)(ii)`$.

Let us take $`x=s^1`$ in (2). Since $`u(x)=tx^l,`$ we have the inequality

$$R(s^1)ts^l1,$$

which is equivalent to (3). So, if $`\alpha `$ is strongly free, then equality holds in (3).

Conversely, if $`\alpha `$ is not strongly free, then the inequality of formal power series (2) is strict, i. e., the following inequality holds

$$R(x)(1sx+tx^l)1+ax^n,$$

where $`n0,a>0`$. Put $`x=s^1`$. We obtain

$$R(s^1)ts^l1+as^n>1,$$

or

$$t>\frac{s^l}{R(s^1)}.$$

So, the inequality (3) is strict too.

## 4 Radii of convergence of Hilbert series: non-existence of algorithms

For a graded algebra $`A`$, let $`r(A)`$ denotes the radius of convergence of the series $`A(t)`$.

The following properties of radii of convergence are clear and well known.

###### Proposition 7

Let $`A`$ be a graded algebra.

(i) $`r(A)=\mathrm{}`$ iff $`A`$ is finite-dimensional.

(ii) If $`A`$ is finitely generated, then $`r(A)>0`$.

(iii) $`r(A)=1`$ iff $`A`$ is not finite-dimensional and $`A`$ has sub-exponential growth.

(iv) If $`B`$ is either a subalgebra or a quotient algebra of A with the induced grading, then $`r(B)r(A)`$.

(v) If $`r(A)>0,`$ then $`\underset{tr(A)}{lim}A(t)=\mathrm{}`$. So, if $`A`$ is connected, then the function $`f(t)=A(t)^1`$ is continuous on $`[0,r(A)]`$ with $`f(0)=1,f(r(A))=0.`$

Under the notation of previous sections, let $`l=2`$. It is shown by D. Anick \[A2, Theorem 3.1\] that over a field of zero characteristic for some positive integers $`s`$ and $`t`$, there is no algorithm which, when given a set $`\alpha F`$ of $`t`$ homogeneous quadratic elements, always decides in a finite number of steps whether or not $`\alpha `$ is strongly free. We will call such a pair of integers $`(s,t)`$ undecidable.

###### Lemma 8

Let $`l`$ be a positive integer, and let $`(s,t)`$ be an undecidable pair. Then the pair $`(s+l,t)`$ is undecidable.

Proof

Let $`G=Fkx_{s+1},\mathrm{},x_{s+l}`$ be a free algebra of rank $`s+l`$. Then a set $`\alpha F`$ is strongly free in $`F`$ iff it is strongly free in $`G`$. So there is no algorithm to recognize it.

###### Lemma 9

Let $`s`$ be an even integer. If the pair $`(s,t)`$ is undecidable, then the pair $`(2s,s^2/4)`$ is undecidable too.

Proof

By \[A4\], a quadratic strongly free set in $`F`$ consting of $`q`$ elements does exist iff $`4qs^2`$. So $`ts^2/4`$. Let $`\beta `$ is a quadratic strongly free set in the algebra $`G=kx_{s+1},\mathrm{},x_{2s}`$ consisting of $`s^2/4t`$ elements. Then the set $`\alpha \beta `$ is strongly free in the algebra $`FG=kx_1,\mathrm{},x_{2s}`$ if and only if the set $`\alpha `$ is strongly free in $`F`$.

###### Corolary 10

For large enough integer $`d`$, the pair $`(4d,d^2)`$ is undecidable.

###### Theorem 11

Let $`\text{char }k=0`$. Let us denote by $`F_s`$ the free associative algebra of rank $`s`$ with standard grading.

(i) Let $`s,t`$ be an undecidable pair of integers. Then there is no algorithm which, when given a set $`\alpha F_s`$ of $`t`$ homogeneous quadratic elements, always decides whether or not the equality

$$R(s^1)=\frac{s^2}{t}$$

holds, where $`R=F_s/\text{id }(\alpha )`$.

(ii) For some positive integers $`s`$, $`t`$, and $`q`$, there is no algorithm which, when given a set $`\gamma F_s`$ of $`t`$ homogeneous quadratic elements, always decides whether or not the equality

$$r(R)=q^1$$

holds, where $`R=F_s/\text{id }(\gamma )`$. For large enough integer $`d`$, we can put $`s=64d`$, $`t=241d^2`$, and $`q=60d`$.

Proof

The statement (i) follows from Theorem 6 and Corollary 10. To prove (ii), let $`d`$ be an integer such that the pair $`(60d,15^2d^2)`$ is undecidable. Let $`\alpha F_{60d}`$ be a quadratic set consisting of $`15^2d^2`$ elements, and let $`B=F_{60d}/\text{id }(\alpha )`$. Let us denote by $`A`$ the standard algebra $`k\{1,y_1,\mathrm{},y_{4d}\}=ky_1,\mathrm{},y_{4d}|y_iy_j=0,1i,j4d`$. Then the algebra $`C=kx_1,\mathrm{}x_{64d}/\text{id }(\gamma )`$ is isomorphic to $`AB,`$ where $`\gamma =\alpha \{x_ix_j=0|60d+1i,j64d\}`$. So $`C`$ is an algebra with $`s=64d`$ generators and $`t=(4d)^2+15^2d^2=241d^2`$ quadratic relations. It is sufficient to proof that the set $`\alpha `$ is strongly free in $`F_{60d}`$ if and only if $`r(C)=(60d)^1`$.

We have

$$C^1(x)=B^1(x)+A^1(x)1=B^1(x)+\frac{1}{1+4dx}1=B^1(x)\frac{4dx}{1+4dx}.$$

If $`\alpha `$ is strongly free in $`F_{60d}`$, then by Corollary 2 we have $`B^1(x)=160dx+225d^2x^2,`$ so

$$C^1(x)=160dx+225d^2x^2\frac{4dx}{1+4dx}=\frac{(160dx)(115d^2x^2)}{1+4dx}.$$

By Proposition 7, $`(v)`$, we obtain $`r(C)=(60d)^1`$.

Now let $`\alpha `$ is not strongly free in $`F_{60d}`$. By Theorem 6, we have $`B^1((60d)^1)<225d^2/(60d)^2=1/16`$. So 

$$C^1((60d)^1)=B^1((60d)^1)\frac{4d(60d)^1}{1+4d(60d)^1}<1/16\frac{1}{1+1/(4d(60d)^1)}=0.$$

We obtain $`r(C)(60d)^1`$, contradicting Proposition 7, $`(v)`$.

## 5 Algebras of extremal growth

Now we introduce the following concept.

###### Definition 1

A graded algebra $`A`$ is said to be extremal, if for every nonzero homogeneous ideal $`IA`$ we have $`r(A/I)>r(A)`$.

We will discuss some properties of extremal algebras.

###### Proposition 12

If $`A`$ is an extremal algebra, then $`0<r(A)<\mathrm{}`$.

Proof

Let us proof the other inequality.

Suppose that $`r(A)=0`$. Let $`aA`$ be a nonzero homogeneous element of degree $`d>0`$, let $`I`$ be an ideal generated by $`a`$, and let $`B=A/I`$. Since $`A`$ is extremal, $`r(B)>0`$.

Let $`F=kc|\text{deg }c=d`$. By the obvious inequality of Hilbert series

$$(BF)(t)A(t),$$

$`r(BF)`$ must be equal to 0.

On the other hand,

$$(BF)(t)^1=b(t)^1dt,$$

where $`b(t)`$ is equal to $`B(t)`$ (resp., $`B(t)+1`$), if $`B`$ is unitary (resp., non-unitary, i. e. $`B_0=0`$). Since the right side is an analytical function in a neighborhood of zero, and this function takes $`0`$ into $`1`$, then in a neighborhood of zero its image does not contain $`0`$. So the function $`(BF)(t)`$ is analitycal in a neighborhood of zero. Therefore $`r(BF)>0`$.

###### Theorem 13

Let $`A`$ be an extremal algebra. Then $`A`$ is prime.

Proof

Obviously, it is sufficient to prove that for any two nonzero homogeneous ideals $`I`$ and $`J`$ of $`A`$, $`I.J0`$. Without loss of generality, we can assume that $`J`$ is a principal ideal generated by an element $`a`$ of a degree $`h`$.

Suppose $`I.J=0`$. Let $`B=A/I,C=A/J,`$ and let $`A=IV,`$ there $`V`$ is a graded vector space. We have

$$J=ka+Aa+aA+AaA=ka+Va+aV+VaV.$$

Therefore, there is an inequality of Hilbert series

$$J(t)t^h+2t^hV(t)+t^hV(t)^2,$$

or

$$A(t)C(t)t^h(B(t)+1)^2.$$

So, we have

$$A(t)C(t)+t^h(B(t)+1)^2.$$

Thus, for radii of convergence we obtain

$$r(A)\mathrm{min}\{r(B),r(C)\},$$

contradicting the extremality of $`A`$.

Remark

In fact, we have proved that for any two homogeneous ideals $`I,J`$ of a graded algebra $`A`$, if $`I.J=0,`$ then $`r(A)=\mathrm{min}\{r(A/I),r(A/J)\}.`$

###### Corolary 14

Let $`A`$ be a (non-graded) locally finite filtered algebra such that the associated graded ring $`\text{gr }A`$ is extremal. Then $`A`$ is prime.

Now, let us consider examples of extremal algebras. In fact, the extremality of nontrivial free algebras is proved by V. E. Govorov in \[Gov\]. We add the following

###### Theorem 15

Let $`A,B`$ be non-trivial connected algebras such that $`r(A)>0`$ and $`r(B)>0`$. Then the algebra $`AB`$ is extremal.

Proof of Theorem 15

Let $`C=AB`$. By the formula

$$C(t)^1=A(t)^1+B(t)^11,$$

the function $`C(t)^1`$ is analytical and nonzero in a neighborhood of zero, so $`r(C)>0`$. For $`t(0,r(C)]`$, we have $`0A(t)^1<1`$ and $`0B(t)^1<1`$. Since $`A(r(C))^1+B(r(C))^11=0,`$ we obtain $`A(r(C))^1>0`$ and $`B(r(C))^1>0`$; hence $`r(C)<\mathrm{min}\{r(A),r(B)\}`$.

It follows from the standard Gröbner bases arguments that we may assume the algebras $`A`$ and $`B`$ to be monomial. (Indeed, if we fix an order on monomials, then, denoting by $`\overline{R}`$ the associated monomial algebra of an algebra $`R`$, we have $`\overline{C}=\overline{A}\overline{B}`$; moreover, if $`I`$ is a homogeneous ideal in $`C`$, then there exists an ideal $`J\overline{C}`$ such that $`r(C/I)r(\overline{C}/J)`$.)

Now, let $`A=kX/I`$ and $`B=kY/J`$, there $`X,Y`$ are homogeneous sets minimally generating algebras $`A`$ and $`B`$, and $`I,J`$ are ideals generated by monomials of elements of $`X`$ and $`Y`$. If $`A`$ and $`B`$ are two–dimensional, i. e., $`Akx|x^2=0`$ and $`Bkx|x^2=0`$, then there is nothing to prove. So, we can assume that $`\text{dim }B3`$.

Let $`SC`$ be a nonzero principal ideal generated by a non-empty monomial $`m`$: it is sufficient to prove that $`r(C/S)>r(C)`$. We will say that a non-empty monomial $`a`$ is an overlap of two monomials $`b,c`$ if there are non-empty monomials $`f,g`$ such that $`b=fa,c=ag`$. Now we need the following

###### Lemma 16

Let $`A,B`$ be connected monomial algebras such that $`\text{dim }_kB3`$, where $`B`$ is minimally generated by the set $`Y=\{y_i\}_{i\mathrm{\Gamma }}`$, and let $`S`$ be a monomial ideal in the algebra $`C=AB`$. Then $`S`$ contains a nonzero monomial $`p`$ with the following properties: all monomials $`p_{ij}=y_ipy_j,i,j\mathrm{\Gamma }`$ are nonzero, and, moreover, for any two monomials $`p_{ij}`$ and $`p_{kl}`$, there are no overlaps in the case $`jk`$ and there is the unique overlap $`y_j`$ in the case $`j=k`$.

Proof of Lemma 16

It is obvious that $`S`$ contains a nonzero monomial $`n`$ such that $`n=xn^{}x`$, where $`n^{}`$ is a monomial, $`xX`$, where $`X`$ is the set of generators of $`A`$. To construct such a monomial $`p`$, let us consider two cases.

Case 1 Let $`\mathrm{\#}Y=1`$, i. e., $`Y=\{y\}`$. Since $`\text{dim }B3`$, then $`y^20`$. Let $`l0`$ be the largest integer satisfying $`n=(xy^2)^ln_1`$, where $`n_1`$ is a monomial. Put $`p=y(xy^2)^qn_1(yx)^q`$, where $`q>\mathrm{max}\{l,\text{len }n_1+3\}`$; then $`p_{11}=y^2(xy^2)^qn_1(yx)^qy`$.

Assume that a monomial $`a`$ is an overlap for the pair $`p_{11},p_{11}`$. Then there exist non-empty monomials $`c,d`$ such that $`p_{11}=ca=ad`$. Hence $`a`$ has the form $`(y^2x)^qf(xy)^q,`$ where $`f`$ is a monomial; therefore, $`\text{len }c=\text{len }d=\text{len }p_{11}\text{len }a<q`$. Since $`p_{11}=y^2(xy^2)^qn_1(yx)^qy=c(y^2x)^qf(xy)^q`$, $`c`$ has the form $`(y^2x)^r`$ for some $`r>0`$. By the maximality of $`l`$, we have $`r=1`$, so $`\text{len }c=\text{len }d=3`$. On the other hand, it follows from the equality $`p_{11}=ad`$ that $`d`$ has the form $`(xy)^l`$ for some $`l`$, so $`\text{len }d`$ must be even.

Case 2 Let $`\mathrm{\#}Y2`$, i. e., $`Y=\{y_1,y_2,\mathrm{}\}`$. Put $`p=(xy_1)^qn(y_2x)^q`$, where $`q>\text{len }n`$. For some monomials $`p_{ij}`$ and $`p_{kl}`$, suppose $`a`$ is an overlap such that $`\text{len }a2`$. Then there exists an overlap of monomials $`p,p`$. It means that the set $`\{p\}`$ is not combinatorial free, so, it is not strongly free in a free associative algebra generated by the set $`XY`$ \[A1\]. By \[HL, Proposition 3.15\], this means that there exist a non-empty monomial $`a`$ and a monomial $`b`$ such that

$$p=aba$$

(at least in the monomial case, the proof in \[HL\] did not really use the assumption $`\text{char }k=0`$). Then $`a`$ has the form $`a=(xy_1)^qc(y_2x)^q`$ for a monomial $`c`$, so $`\text{len }a4q`$ and $`\text{len }p8q,`$ contradicting the choice of $`q`$.

Returning to the general proof, let $`PC`$ be an ideal generated by all of the monomials $`p_{ij}`$, and let $`D=C/P`$. Since $`PS`$, it is sufficient to prove that $`r(D)>r(C)`$. To prove this, we will compute the homology of the algebra $`D`$ and obtain its Hilbert series as the Euler characteristic.

Recall how to compute homologies of a monomial algebra (see details in \[A3\]; we use the terminology of \[U\]). Suppose $`F`$ is a free associative algebra generated by a set $`X`$, $`IF`$ is an ideal minimally generated by a set of monomials $`U`$, and $`M`$ is the quotient algebra $`F/I`$. Let us define a concept of a chain of a rank $`n`$ and its tail.

For $`n=0`$, every generator $`xX`$ is called a chain of rank $`0`$; it coinsides with its tail. For $`n>0,`$ a monomial $`f=gt`$ is called a chain of rank $`n`$ and $`t`$ is called its tail, if the following conditions hold: (i) $`g`$ is a chain of rank $`n1`$; (ii) if $`r`$ is a tail of $`g`$, then $`rt=vu,`$ where $`v,u`$ are monomials and $`uU`$; (iii) excluding the word $`u`$ as the end, there are no subwords of $`rt`$ lying in $`U`$.

Let us denote by $`C_n^M`$ the set of chains of rank $`n`$; for example, $`C_0^M=X`$ and $`C_1^M=U`$. Then for all $`n0`$ there are the following isomorphisms of graded vector spaces:

$$kC_n^M\text{Tor }_{n+1}^M(k,k).$$

Letting $`c_j^i`$ denote the number of chains of degree $`i`$ having a rank $`j`$, consider the generating function

$$C^M(s,t)=\underset{i0}{}\underset{j0}{}c_j^is^jt^i.$$

Arguing as in Proposition 1, taking the Euler characteristic of the minimal resolution, we obtain

$$M(t)^1=1C^M(1,t);$$

the formal power series in the right side does exist since every vector space $`\text{Tor }_n^M(k,k)`$ is concentrated in degrees $`n`$.

By definition, for all $`i0,`$ we have

$$C_i^C=C_i^AC_i^B$$

and $`C_0^D=C_0^C`$. Therefore,

$$C^C(s,t)=C^A(s,t)+C^B(s,t),$$

so

$$C^D(s,t)=C^A(s,t)+C^B(s,t)+C^{}(s,t),$$

there the set $`C^{}`$ consists of chains that have a subword $`p`$. Thus the set $`C_0^{}`$ is empty, and $`C_1^{}=\{p_{ij}\}`$.

Let us prove that the set $`C^{}`$ consists of all monomials of the form

$$c_1pc_2p\mathrm{}pc_n$$
(5)   
for $`n2`$, where $`c_1,\mathrm{},c_nC^B`$ . It is clear that all these monomials are chains of $`C^{}`$. Let us prove the converse.

Since $`C_0^B=Y`$, this is obvious for chains of rank $`1`$. Now, let $`f=gtC_n^{}`$, where $`g`$ is a chain of lesser rank and $`t`$ is a tail of the chain $`f`$. Let $`r`$ be the tail of $`g`$. By induction, we may assume that $`gC^B`$ or $`g`$ has the form (5); in the second case, $`r`$ is the tail of $`c_n`$, or has the form $`py_i,`$ where $`y_i=c_nY`$. If $`t`$ is a word of the alphabet $`Y`$, then $`gtC^B`$, or $`c_ntC^B`$, so $`f`$ has the desired form. Otherwise, $`t`$ must contain a subword equal to $`p`$; hence, $`t=py_j`$ for some $`j`$. Thus,

$$f=c_1pc_2p\mathrm{}pc_npy_j.$$

Now, let us compute the generating function. Notice that if a chain $`f`$ has the form (5), then the rank of $`f`$ is equal to $`k+n1,`$ where $`k`$ is the sum of ranks of the chains $`c_1,\mathrm{},c_n`$. Let $`\text{deg }p=b`$. By (5), we have

$$C^{}(s,t)=\underset{i1}{}(st^b)^i\left(C^B(s,t)\right)^{i+1}=\frac{st^b\left(C^B(s,t)\right)^2}{1st^bC^B(s,t)}.$$

Put $`q(t)=1B(t)^1=C^B(t,1)`$. Obviously, for $`0<tr(B)`$, we have $`q(t)>0`$.

We obtain

$$D(t)^1=C(t)^1C^{}(1,t),$$

hence,

$$D(r(C))^1=C^{}(1,r(C))=\frac{r(C)^bq(r(C))^2}{1+r(C)^bq(r(C))}>0.$$

Since $`r(D)r(C)`$ and $`D(r(C))>0`$, we obtain $`r(D)>r(C)`$. This completes the proof ot Theorem 15.

###### Corolary 17

Let $`A`$ be a connected algebra such that $`r(A)>0`$. If there exists a strongly free set in $`A`$, then $`A`$ is extremal.

Proof

By \[A1, Lemma 2.7\], any subset of a strongly free set is strongly free; so, there is a strongly free element $`fA`$. Let $`L`$ be the ideal generated by $`f`$, and let $`B=A/L`$.

If $`A`$ is generated by $`f`$, then, since every strongly free set generates a free subalgebra, $`A=kf`$; hence, every proper quotient of $`A`$ is finitely-dimensional, so $`A`$ is extremal. Otherwise, the algebra $`B`$ is not trivial, so the algebra $`C=Bkg|\text{deg }g=\text{deg }f`$ is extremal by Theorem 15.

By \[A1, Section 2\], there is an isomorphism of graded vector spaces $`\rho :CA`$ having the following properties:

(i) the restriction of $`\rho `$ to $`B`$ is a right inverse to the canonical projection $`AB`$;

(ii) $`\rho (g)=f`$, and $`\rho (a_1ga_2\mathrm{}ga_n)=\rho (a_1)f\rho (a_2)\mathrm{}f\rho (a_n)`$.

Suppose $`mA`$ is an arbitrary homogeneous element, $`m=\rho (c)`$, and $`I=AmA`$ is the ideal generated by $`m`$. We need to prove that $`r(A/I)>r(A)`$. Indeed, let $`c^{}=gcg`$, let $`m^{}=fmf=\rho (c^{})`$, and let $`JA`$ (respectively, $`KC`$) be the ideal generated by $`m^{}`$ (resp., $`c^{}`$). For every $`a,bC`$ we get

$$\rho (ac^{}b)=\rho (agcgb)=\rho (a)f\rho (c)f\rho (b)=\rho (a)m^{}\rho (b).$$

Therefore $`\rho (K)J`$, so $`(A/J)(t)(C/K)(t)`$. We obtain

$$r(A/I)r(A/J)r(C/K)>r(C)=r(A).$$

## 6 How a quotient algebra may grow?

Suppose that $`A`$ is a connected algebra such that $`r(A)>0,`$ $`SA`$ is a non-empty set of homogeneous elements minimally generating an ideal $`I=ASA`$, and $`B=A/I`$. Let $`C=BkS`$, and let

$$D=A/II/I^2I^2/I^3\mathrm{}$$

with the induced grading; then $`D(t)=A(t)`$. By \[HL, Theorem 2.4\], we have a epimorphism

$$f:CD,$$

which is an isomorphism iff the set $`S`$ is strongly free. Since $`C`$ is either a free algebra or a free product of non-trivial algebras, it is extremal; so, we obtain the following 

###### Proposition 18

Using the notation above,

$$r(A)r(C).$$

Equality holds if and only if the set $`S`$ is strongly free.

Now, by the formula for the Hilbert series of a free product, we have

$$C(t)^1=B(t)^1S(t).$$

Since $`C`$ is extremal, the series $`B(t)`$ and $`S(t)`$ converge for $`t[0,r(C)]`$, so

$$B(r(C))^1S(r(C))=0,$$

or

$$B(r(C))S(r(C))=1.$$

Since $`r(A)r(C)`$, we have

$$B(r(A))S(r(A))1$$

(where $`\mathrm{}>1`$); the equality holds iff $`r(A)=r(C)`$.

Thus we obtain:

###### Theorem 19

Using our notation,

$$B(r(A))S(r(A))1,$$

and the following conditions are equivalent:

(i) the equality above holds;

(ii) $`r(A)=r(C)`$;

(iii) the set $`SA`$ is strongly free.

In particular, if the set $`S`$ consists of $`t`$ elements of degree $`l`$, then we have

$$tB(r(A))^1r(A)^l,$$

where equality holds iff $`S`$ is strongly free. This estimate generalizes Govovrov’s inequality (3).

Remark

Suppose that $`\text{char }k=0`$, the algebra $`A`$ is free of rank $`s`$, and $`\alpha `$ is a set of $`t`$ quadratic elements. If the pair $`(s,t)`$ is undecidable, then $`C`$ is finitely presented and connected (but non-standard) algebra such that there is no algorithm do decide whether or not $`r(C)=1/s`$.