text:
# Multiplicative measures on free groups

## 1 How one can measure subsets in the free group?

### 1.1 Motivation

The present paper is motivated by needs of practical computations in finitely presented groups. In particular, we wish to develop tools which can be used in the analysis of the “practical” complexity of algorithmic problems for discrete infinite groups, as well as in the analysis of the behaviour of heuristic (e.g. genetic) algorithms for infinite groups .

In most computer-based computations in finitely presented groups $`G=F/R`$ the elements are represented as freely reduced words in the free group $`F`$, with procedures for comparing their images in the factor group $`G=F/R`$. Therefore the ambient algebraic structure in all our considerations is the free group $`F=F(X)`$ on a finite set $`X=\{x_1,\mathrm{},x_m\}`$. We identify $`F`$ with the set of all freely reduced words in the alphabet $`XX^1`$, with the multiplication given by concatenation of words with the subsequent free reduction.

The most natural and convenient way to generate pseudorandom elements in $`G`$ is to produce pseudorandom freely reduced words in $`F`$. The most abstract mathematical model of a random word generator in $`F`$ is just a probabilistic distribution on $`F`$. We find ourselves in the setting of the paper , which initiated a general discussion of probabilistic measures on the free group. Analysis of complexity of algorithms on groups necessarily involves the study of their behaviour with respect to the size of the input, usually, the length of input words. Different probabilistic distributions on $`F`$ represent pseudorandom generators with varying mean length of words. This mean length is one of the most important parameters of a pseudorandom generator. Since we wish to vary the mean length of inputs, a single fixed distribution on $`F`$ does not suffice, and we need a parametric family of probabilistic distributions $`𝒫=\{P_l\}`$ of varying mean length $`l`$ of elements. This leads to the crucial point of our approach: a measure of a given subset $`RF`$ is not a particular number $`P_l(R)`$ (which is usually meaningless), but rather a function $`𝒫(R):lP_l(R)`$ which naturally encodes all statistical properties of $`R`$ with respect to the family of distributions $`𝒫`$. It turns out that such well-known asymptotic characteristics of $`R`$ as asymptotic density, co-growth rate, etc., are just the standard analytic characteristics of the function $`𝒫`$. This opens the way to apply classical analytical methods for description of statistical behaviour of algorithms in groups. In Section 1.5 we introduce a hierarchy of subsets $`R`$ in $`F`$ with respect to their size, which is based on linear approximations of the function $`\mu (R)`$. This hierarchy is quite sensitive, for example, it allows one to differentiate between sets with the same asymptotic density.

Our requirements to probabilistic distributions are motivated by a very practical, engineering approach to computations in groups. First of all, the probabilistic distribution should not be unnatural in the context of computational group theory. It should provide an easy way to make crude estimates of probabilities of various subsets important in standard problems of group theory: subgroups (first of all, normal or finitely generated subgroups), cosets with respect to subgroups, conjugacy classes, sets of words of special nature (say, squares or commutators). It should also provide for an easy analysis of asymptotic behaviour of probabilities when the mean word length tends to infinity.

Many sets we wish to measure have happened to be context free languages . An important subclass is made of regular subsets (that is, subsets produced by deterministic finite automata). This very natural class of subsets includes finitely generated subgroups and their cosets, and finitely generated cones (sets of all words which start with an initial segment belonging to a given finite set of words). The class of regular sets in $`F`$ is closed under Boolean operations, and under translation and conjugation by elements of $`F`$.

### 1.2 Generation of random words in $`F`$

Let $`F=F(X)`$ be a free group with basis $`X=\{x_1,\mathrm{},x_m\}`$. We use, as our random word generator, the following no-return random walk $`W_s`$ ($`s(0,1]`$) on the Cayley graph $`C(F,X)`$ of $`F`$ with respect to the generating set $`X`$. We start at the identity element $`1`$ and either do nothing with probability $`s`$ (and return value $`1`$ as the output of our random word generator), or move to one of the $`2m`$ adjacent vertices with equal probabilities $`(1s)/2m`$. If we are at a vertex $`v1`$, we either stop at $`v`$ with probability $`s`$ (and return $`v`$), or move, with probability $`\frac{1s}{2m1}`$, to one of the $`2m1`$ adjacent vertices lying away from $`1`$, thus producing a new freely reduced word $`vx_i^{\pm 1}`$. In other words, we make random freely reduced words $`w`$ of random lengths $`|w|`$ distributed according to the geometric law

$$P(|w|=k)=s(1s)^k,$$

in such way that words of the same length $`k`$ are produced with equal probabilities (in terminology of , we say that our measure is moderated by the geometric distribution of $`\{\mathrm{\hspace{0.17em}0}\}`$). Observe that the set of all words of length $`k`$ in $`F`$ forms the sphere $`S_k`$ of radius $`k`$ in $`C(F,X)`$ of cardinality $`|S_k|=2m(2m1)^{k1}`$. It is easy to see that the resulting probabilistic atomic measure111Recall that a measure $`\mu `$ on a countable set $`X`$ is atomic if every subset $`YX`$ is measurable. This is equivalent to saying that every singleton subset $`\{x\}`$ is measurable. Obviously, $`\mu (Y)=_{xY}\mu (x)`$. $`\mu _s`$ on $`F`$ is given by the formula

$$\mu _s(w)=\frac{s(1s)^{|w|}}{2m(2m1)^{|w|1}}\text{ for }w1$$
(1)
and

$$\mu _s(1)=s.$$
(2)
Thus, $`\mu _s(w)`$ is the probability that the random walk $`W_s`$ stops at $`w`$. The mean length $`L_s`$ of words in $`F`$ distributed according to $`\mu _s`$ is equal to

$$L_s=\underset{wF}{}|w|\mu _s(w)=s\underset{k=1}{\overset{\mathrm{}}{}}k(1s)^{k1}=\frac{1}{s}1.$$

Hence we have a family of probabilistic distributions $`\mu =\{\mu _s\}`$ with the stopping probability $`s(0,1)`$ as a parameter, which is related to the average length $`L_s`$ as

$$s=\frac{1}{L_s+1}.$$

By $`\mu (R)`$ we denote the function

$`\mu (R):(0,1)`$ $``$ $``$
$`s`$ $``$ $`\mu _s(R);`$
we call it measure of $`R`$ with respect to the family of distributions $`\mu `$.

Denote by $`n_k=n_k(R)=|RS_k|`$ the number of elements of length $`k`$ in $`R`$, and by $`f_k=f_k(R)`$ the relative frequencies

$$f_k=\frac{|RS_k|}{|S_k|}$$

of words of length $`k`$ in $`R`$. Notice that $`f_0=1`$ or $`0`$ depending on whether $`R`$ contains $`1`$ or not. Recalculating $`\mu (R)`$ in terms of $`s`$, we immediately come to the formula

$$\mu (R)=s\underset{k=0}{\overset{\mathrm{}}{}}f_k(1s)^k,$$

and the series on the right hand side is convergent for all $`s(0,1)`$. Thus, for every subset $`RF`$, $`\mu (R)`$ is an analytic function of $`s`$. When studying the behaviour of $`\mu (R)`$, we mostly restrict it to real arguments, but occasionally need to work with extensions of $`\mu (R)`$ to larger regions of the complex plane. We use only most basic facts of the theory of analytic functions which can be found in any book on complex analysis.

Notice that the asymptotic behaviour of the set $`R`$ when $`L_s\mathrm{}`$ corresponds to the behaviour of the function $`\mu (R)`$ when $`s0^+`$. This will be discussed in more detail in Section 1.4. Here we just mention how one can obtain a first coarse approximation of the asymptotic behaviour of the function $`\mu (R)`$. Let $`W_0`$ be the no-return non-stop simple random walk on $`C(F,X)`$ (like $`W_s`$ with $`s=0`$), where the walker moves from a given vertex to any adjacent vertex away from the initial vertex 1 with equal probabilities $`1/2m`$. In this event, the probability $`\lambda (w)`$ that the walker hits an element $`wF`$ in $`|w|`$ steps (which is the same as the probability that the walker ever hits $`w`$) is equal to

$$\lambda (w)=\frac{1}{2m(2m1)^{|w|1}},\text{ if }w1,\text{ and }\lambda (1)=1.$$

This gives rise to an atomic measure

$$\lambda (R)=\underset{wR}{}\lambda (w)=\underset{k=0}{\overset{\mathrm{}}{}}f_k(R)$$

where $`\lambda (R)`$ is just the sum of the relative frequencies of $`R`$. This measure is not probabilistic, since some sets have no finite measure (obviously, $`\lambda (F)=\mathrm{}`$), moreover, the measure $`\lambda `$ is finitely additive, but not $`\sigma `$-additive. We shall call $`\lambda `$ the frequency  measure on $`F`$. If $`R`$ is $`\lambda `$-measurable (i.e., $`\lambda (R)<\mathrm{}`$) then $`f_k(R)0`$ when $`k\mathrm{}`$, so intuitively, the set $`R`$ is ”small” in $`F`$.

A number of papers (see, for example, , , , ), used the asymptotic density (or more, precisely, the spherical asymptotic density)

$$\rho (R)=limsupf_k(R)$$

as a numeric characteristic of the set $`R`$ reflecting its asymptotic behavior. Unfortunately, the asymptotic density is not even finitely additive, and it is not sensitive enough: many interesting sets have asymptotic density either $`1`$ or $`0`$.

More subtle analysis of asymptotic behaviour of $`R`$ in some cases provides the relative growth rate

$$\gamma (R)=limsup\sqrt[k]{f_k(R)}.$$

Notice the obvious inequality $`\gamma (R)1`$. If $`\gamma (R)<1`$ (we will have to say more about this case in Section 2), then, by an elementary result from Calculus, the series $`f_k`$ converges. This shows that if $`\gamma (R)<1`$ then $`R`$ is $`\lambda `$-measurable.

Our distribution $`\mu _s`$ has the uncomfortably big standard deviation $`\sigma =\frac{\sqrt{1s}}{s}`$. This reflects the fact that it is strongly skewed towards ‘short’ elements. However, since real life computations take place in the vicinity of $`1`$, we believe that our model is useful as a first step in developing statistical approach to computational group theory.

### 1.3 The multiplicativity of the measure and generating functions

It is convenient to renormalise our measures $`\mu _s\mu `$ and work with the parametric family $`\mu ^{}=\{\mu _s^{}\}`$ of adjusted measures

$$\mu _s^{}(w)=\left(\frac{2m}{2m1}\frac{1}{s}\right)\mu _s(w).$$
(3)
This new measure $`\mu _s^{}`$ is multiplicative in the sense that

$$\mu _s^{}(uv)=\mu _s^{}(u)\mu _s^{}(v),$$
(4)
where $`uv`$ denotes the product of non-empty words $`u`$ and $`v`$ such that $`|uv|=|u|+|v|`$ i.e. there is no cancellation between $`u`$ and $`v`$. The measure $`\mu `$ itself is almost multiplicative in the sense that

$$\mu _s(uv)=c\mu _s(u)\mu _s(v)\text{for}c=\frac{2m}{2m1}\frac{1}{s}$$
(5)
for all non-empty words $`u`$ and $`v`$ such that $`|uv|=|u|+|v|`$.

If we denote

$$t=\mu _s^{}(x_i^{\pm 1})=\frac{1s}{2m1}$$
(6)
then

$$\mu _s^{}(w)=t^{|w|}$$
(7)
for every non-empty word $`w`$.

Similarly, we can adjust the frequency measure $`\lambda `$ making it into a multiplicative atomic measure

$$\lambda ^{}(w)=\frac{1}{(2m1)^{|w|}}.$$
(8)
Let now $`R`$ be a subset in $`F`$ and $`n_k=n_k(R)=|RS_k|`$ be the number of elements of length $`k`$ in $`R`$. The sequence $`\{n_k(R)\}_{k=0}^{\mathrm{}}`$ is called the spherical growth sequence of $`R`$. We assume, for the sake of minor technical convenience, that $`R`$ does not contain the identity element $`1`$, so that $`n_0=0`$. It is easy to see now that

$$\mu ^{}(R)=\underset{k=0}{\overset{\mathrm{}}{}}n_kt^k.$$

One can view $`\mu ^{}(R)`$ as the generating function of the spherical growth sequence of the set $`R`$ in variable $`t`$ which is convergent for each $`t[0,1)`$. This simple observation will allow us (see Sections 3 and 4) to apply a well established machinery of generating functions of context-free languages to estimate probabilities of sets.

### 1.4 Cesaro density

Let $`\mu =\{\mu _s\}`$ be the parametric family of distributions defined above. For a subset $`R`$ of $`F`$ we define the limit measure $`\mu _0(R):`$

$$\mu _0(R)=\underset{s0^+}{lim}\mu (R)=\underset{s0^+}{lim}s\underset{k=0}{\overset{\mathrm{}}{}}f_k(1s)^k.$$

The function $`\mu _0`$ is additive, but not $`\sigma `$-additive, since $`\mu _0(w)=0`$ for a single element $`w`$. It is easy to construct a set $`R`$ such that $`lim_{s0^+}\mu (R)`$ does not exist. However, in the applications that we have in mind we have not yet encountered such a situation. Strictly speaking, $`\mu _0`$ is not a measure because the set of all $`\mu _0`$-measurable sets is not closed under intersections (though it is closed under complements). Because $`\mu _s(R)`$ gives an approximation of $`\mu _0(R)`$ when $`s0^+`$, or equivalently, when $`L_s\mathrm{}`$, we shall call $`R`$ measurable at infinity if $`\mu _0(R)`$ exists, otherwise $`R`$ is called singular.

If $`\mu (R)`$ can be expanded as a convergent power series in $`s`$ at $`s=0`$ (and hence in some neighborhood of $`s=0`$):

$$\mu (R)=m_0+m_1s+m_2s^2+\mathrm{},$$

then

$$\mu _0(R)=\underset{s0^+}{lim}\mu (R)=m_0.$$

A corollary from a theorem by Hardy and Littlewood \[13, Theorem 94\] (see Corollary 5.2 in Section 5) asserts that $`\mu _0`$ can be computed as the Cesaro limit

$$\mu _0(R)=\underset{n\mathrm{}}{lim}\frac{1}{n}\left(f_1+\mathrm{}+f_n\right).$$
(9)
So it will be also natural to call $`\mu _0`$ the Cesaro density, or asymptotic average density.

Notice, that the Cesaro density $`\mu _0`$ is more sensitive then the standard asymptotic density $`\rho `$. For example, if $`R`$ is a coset of a subgroup $`H`$ of finite index in $`F`$ then it follows from Woess  that

$$\mu _0(R)=\frac{1}{|G:H|},$$

while, obviously, $`\rho (H)=1`$ for the group $`H`$ of index $`2`$ consisting of all elements of even length.

On the other hand, if $`lim_k\mathrm{}f_k(R)`$ exists (hence is equal to $`\rho (R)`$) then $`\mu _0(R)`$ also exists and $`\mu _0(R)=\rho (R)`$. In particular, if a set $`R`$ is $`\lambda `$-measurable, then it is $`\mu _0`$-measurable, and $`\mu _0(R)=0`$.

### 1.5 Asymptotic classification of subsets

In this section we introduce a classification of subsets $`R`$ in $`F`$ according to the asymptotic behaviour of the functions $`\mu (R)`$.

Let $`\mu =\{\mu _s\}`$ be the family of measures defined in Section 1.2. We start with a global characterization of subsets of $`F`$.

Let $`R`$ be a subset of $`F`$. By its construction, the function $`\mu (R)`$ is analytic on $`(0,1)`$. The subset $`R`$ is called rational, algebraic, etc,  with respect to $`\mu `$ if the function $`\mu (R)`$ is rational, algebraic, etc. We say that $`R`$ is smooth if $`\mu (R)`$ can be analytically extended to a neighborhood of $`0`$ and is regular at $`0`$.

#### Algebraic sets and context free languages.

If the set $`R`$ is an (unambiguous) context free language then, by a classical theorem of Chomsky and Schutzenberger , the generating function $`\mu ^{}(R)=n_kt^k`$, and hence the function $`\mu (R)`$, are algebraic functions of $`s`$. Moreover, if $`R`$ is regular then $`\mu (R)`$ is a rational function with rational coefficients .

An important class of example of algebraic subsets is provided by a theorem of Muller and Schupp : A normal subgroup $`RF`$ is a context free language if and only if the factor group $`F/R`$ is free-by-finite. Notice that, for the derived subgroup $`R=[F,F]`$ of the free group of rank $`2`$, the measure $`\mu (R)`$ is not an algebraic function. Richard Sharp kindly informed us that this follows from a remark on p. 127 of his paper . See also Example 2.

It is well known that singular points of an algebraic function are either poles or branching points. Since $`\mu (R)`$ is bounded for $`s(0,1)`$, this means that, for a context-free set $`R`$, the function $`\mu (R)`$ has no singularity at $`0`$ or has a branching point at $`0`$. After uniformisation, we can expand $`\mu (R)`$ as a fractional power series:

$$\mu (R)=m_0+m_1s^{1/n}+m_2s^{2/n}+\mathrm{}.$$

If $`R`$ is regular, than we actually have the usual power series expansion:

$$\mu (R)=m_0+m_1s+m_2s^2+\mathrm{};$$

in particular, $`\mu (R)`$ can be analytically extended in the vicinity of $`0`$ and $`R`$ is smooth.

#### Linear approximation.

If the set $`R`$ is smooth then the linear term in the expansion of $`\mu (R)`$ gives a linear approximation of $`\mu (R)`$:

$$\mu (R)=m_0+m_1s+O(s^2).$$

Notice that, in this case, $`m_0=\mu _0(R)`$ is the Cesaro density of $`R`$. It can be shown (see Corollary 5.3 in Section 5) that if $`\mu _0(R)=0`$ then

$$m_1=\underset{k=1}{\overset{\mathrm{}}{}}f_k(R)=\lambda (R).$$

On the other hand, even without assumption that $`R`$ is smooth, if $`R`$ is $`\lambda `$-measurable (that is, the series $`f_k(R)`$ converges), then, by Corollary 5.3,

$$\mu _0(R)=0\text{ and }\underset{s0^+}{lim}\frac{\mu (s)}{s}=\lambda (R).$$

This give us a good excuse to use for the limit

$$\mu _1=\underset{s0^+}{lim}\frac{\mu (s)}{s},$$

if it exists, the same term frequency measure as for $`\lambda `$. The function $`\mu _1`$ is an additive measure on $`F`$ (though it is not $`\sigma `$-additive).

#### Asymptotic classification of sets.

Now we introduce a subtler classification of sets in $`F`$ (which is based on the linear approximation of $`\mu (R)`$:

* Thick subsets: $`\mu _0(R)`$ exists, $`\mu _0(R)>0`$ and

$$\mu (R)=\mu _0(R)+\alpha _0(s),where\underset{s0^+}{lim}\alpha _0(s)=0.$$
* Sparse subsets: $`\mu _0(R)=0`$, $`\mu _1(R)`$ exists and

$$\mu (R)=\mu _1(R)s+\alpha _1(s)where\underset{s0^+}{lim}\frac{\alpha _1(s)}{s}=0.$$
* Intermediate density subsets: $`\mu _0(R)=0`$ but $`\mu _1(R)`$ does not exist.
* Singular sets: $`\mu _0(R)`$ does not exist.

We put on record the following simple observation which follows from discussions in Section 1.2.

###### Lemma 1.1

Every $`\lambda `$-measurable set is sparse. In particular, if $`\gamma (R)<1`$ then $`R`$ is sparse.

We shall see in Section 3 that, for the important class of regular sets, the generating function is a rational function and hence every regular set is either thick or sparse.

### 1.6 Degrees of polynomial growth

In this section we introduce degrees of polynomial growth “on average” for functions on the free group with respect to the family of distributions $`\mu `$. In particular, it would produce hierarchies of the average case complexity of various algorithms for infinite groups, which would make meaningful statements like “the algorithm works in cubic time on average”. A different approach to degrees of growth “on average” was suggested in .

Let $`\mu =\{\mu _s\}`$ be the family of measures constructed in Section 1.2 and $`\lambda `$ be the frequency measure on $`F`$. Let $`f:F_n`$ be a non-negative real valued function.

The average value $`E_k=E_k(f)`$ of the function $`f`$ on the sphere $`S_k`$ (with respect to $`\lambda `$) is equal to:

$$E_k=\underset{wS_k}{}f(w)\lambda (w)=\underset{|w|=k}{}\frac{f(w)}{|S_k|}.$$

For every fixed stopping probability $`s(0,1)`$ we evaluate the mean value $`M_f(s)`$ of the function $`f`$ with respect to $`\mu _s`$ as

$`M_f(s)`$ $`=`$ $`{\displaystyle \underset{wF}{}}f(w)\mu _s(w)`$
$`=`$ $`s{\displaystyle \underset{k=0}{\overset{\mathrm{}}{}}}E_k(1s)^k.`$
If for every $`s(0,1)`$ the value $`M_f(s)`$ is finite then the function $`M_f(s)`$ is called the mean value  of $`f`$ with respect to the family of distributions $`\mu `$. The growth of the function $`M_f`$ at $`s=0`$ corresponds to the growth of the mean values of $`f`$ with respect to the family $`\mu `$ when the mean length $`L=\frac{1}{s}1`$ tends to infinity. Therefore, if we rewrite $`M_f(s)`$ in the variable $`L`$:

$$M_f^{}(L)=M_f\left(\frac{1}{L+1}\right),L(0,\mathrm{}),$$

then the growth of $`M_f^{}`$ at $`\mathrm{}`$ reflects the growth of the initial function $`f`$ when the length of words tends to $`\mathrm{}`$. This allows one to introduce the notion of the polynomial growth of $`f`$ on average.

Let $`\nu :(1,\mathrm{})`$ be an arbitrary continuous probability density on the interval $`(1,\mathrm{})`$ and $`\nu (x)dx`$ the corresponding probabilistic measure. We say that a non-negative real valued function $`f:F`$ has a polynomial growth of degree $`d`$ on average with respect to $`\mu `$ and $`\nu `$ if the function $`M_f^{}`$ has polynomial growth of degree $`d`$ on average with respect to $`\nu `$, i.e., the following improper integral converges at $`\mathrm{}`$:

$$_0^{\mathrm{}}\frac{M_f^{}(x)}{x^d}\nu (x)𝑑x.$$

and $`d`$ is the minimal with this property.

If $`\eta (s)ds`$ is the measure on $`(0,1)`$ obtained from $`\nu (x)dx`$ by the change of variables $`s=1/(x+1)`$, then this is the same as to say that

$$_0^1s^dM_f(s)\eta (s)𝑑s$$

converges at $`0`$. In most cases we can use the standard measure $`ds`$ on $`(0,1)`$.

Elementary results from analysis give the following simple and useful test for polynomial growth of functions on average.

###### Lemma 1.2

Let $`f:F`$ be a non-negative real valued function on $`F`$. If the mean value function $`M_f(s)`$ is defined for $`s(0,1)`$ and, in the vicinity of $`0`$,

$$M_f(s)=O(s^d)$$

for some positive integer $`d`$ then $`f`$ has polynomial growth of degree at most $`d`$ on average for any continuous probabilistic measure $`\eta (s)ds`$ on $`(0,1)`$.

Our definition of polynomial growth on average is justified by the following simple observation.

###### Lemma 1.3

The function $`f(w)=|w|^n`$ has growth of degree $`n`$ on average.

Proof. In view of Lemma 1.2, it will suffice to prove that, in the vicinity of $`0`$,

$$M_f(s)=O(s^n).$$

We shall work with a larger function

$$g(w)=(|w|+1)(|w|+2)\mathrm{}(|w|+n).$$

Without loss of generality, we can assume $`g(1)=0`$. It is easy to see that its mean

$$M_g(s)=s\underset{k=1}{\overset{\mathrm{}}{}}(k+1)(k+2)\mathrm{}(k+n)(1s)^k.$$

After changing the variable, $`z=1s`$, it is enough to prove that the function

$$M(z)=(1z)\underset{k=1}{\overset{\mathrm{}}{}}(k+1)(k+2)\mathrm{}(k+n)z^k$$

has a pole of degree at most $`d`$ at $`z=1`$. But it is very easy to see that

$$M(z)=(1z)\frac{d^n}{dz^n}\left(\frac{z^{n+1}}{1z}\right)$$

has a pole of degree $`n`$ at $`z=1`$. $`\mathrm{}`$

The following lemma shows that our definition of growth is natural in the sense that polynomial growth of averages $`E_k(f)`$ of the function $`f`$ over the spheres $`S_k`$ implies polynomial growth of the function $`f`$ on average in the sense of our definition.

###### Lemma 1.4

If $`F_k(f)Ck^d`$ for some constant $`C`$, then $`f(w)`$ has polynomial growth of degree at most $`d`$.

Proof. Immediately follows from the previous lemma. $`\mathrm{}`$

### 1.7 Negligible sets

Let $`RF`$ and $`\chi `$ be the characteristic function of $`R`$. We say that a set $`R`$ is polynomially negligible if for every positive integer $`d`$, the polynomial function $`|w|^d\chi (w)`$ restricted to $`R`$ has growth of degree at most $`0`$ on average.

The purpose of this concept is that, in computations of degrees of growth on average, we can use a ‘cut and paste’ technique and ignore any polynomial function of any degree with support restricted to $`R`$.

###### Theorem 1.5

Let $`RF`$ and $`f_k=|RS_k|/|S_k|`$ be the relative frequency of elements of $`R`$ in the sphere $`S_k`$. Assume that the function

$$\mu ^{}(R)=\frac{2m}{2m1}\underset{k=0}{\overset{\mathrm{}}{}}f_k(1s)^k$$

can be continued analytically to a neighborhood of $`0`$ and is regular at $`0`$. Then the set $`R`$ is polynomially negligible.

#### Proof.

We can assume without loss of generality that $`RF\{1\}`$ hence $`f_0=0`$. Following the same line of argument as in Lemma 1.3, we replace $`|w|^n`$ with the larger function

$$g(w)=(|w|+1)(|w|+2)\mathrm{}(|w|+n)$$

and set $`g(1)=0`$. Let $`z=1s`$ and $`r(z)=f_kz^k`$. Observe that $`r(z)`$ is analytic and regular in a neighbourhood of $`z=1`$. It is enough to prove that

$$G(z)=(1z)\underset{k=0}{\overset{\mathrm{}}{}}(k+1)(k+2)\mathrm{}(k+n)f_kz^k$$

is regular at $`z=1`$. But this is obvious because

$$G(z)=(1z)\frac{d^n}{dz^n}\left(z^{n+1}r(z)\right)$$

is regular at $`z=1`$. $`\mathrm{}`$

###### Corollary 1.6

If the relative growth rate $`\gamma (R)<1`$ then $`R`$ is negligible.

#### Proof.

Since the radius of convergence $`r`$ of the series $`f_k(R)(1s)^k`$ is computed as $`r=1/\gamma (R)`$, we see that the function $`f_k(R)(1s)^k`$ is analytic and regular in the vicinity of $`0`$. Hence $`R`$ is negligible by Theorem 1.5. $`\mathrm{}`$

## 2 Normal subgroups and cogrowth

### 2.1 Non-recurrent and non-amenable factor groups

Let $`G`$ be a finitely generated group with an atomic probability measure $`\nu :G[0,1]`$. The measure $`\nu `$ is called symmetric if $`\nu (g)=\nu (g^1)`$ for all $`gG`$. The support of $`\nu `$ is defined as

$$\mathrm{supp}(\nu )=\{gG\nu (g)0\}.$$

With a given measure $`\nu `$ on $`G`$ one can associate a random walk $`W_\nu `$ on $`G`$ such that the transition probability from $`g`$ to $`h`$ is equal to $`\nu (g^1h)`$. A finitely generated group $`G=F/R`$ is called recurrent, if it admits a symmetric atomic probability measure $`\nu :G[0,1]`$, whose support generates $`G`$, and such that the corresponding random walk $`W_\nu `$ on $`G`$ is recurrent. Recall, that a random walk is recurrent if it returns to $`1`$ infinitely many times with probability $`1`$, i.e., the series

$$\underset{n=0}{\overset{\mathrm{}}{}}p^{(n)}(1),$$

where $`p^{(n)}(1)`$ is the probability for the walker to return to $`1`$ in $`n`$ steps, is divergent. By a result of Varopoulos  based on Gromov’s polynomial growth theorem , a group is recurrent if and only if it is finite or a finite extension of $``$ or $`^2`$. Grigorchuk gave in  another useful characterization of recurrent groups: the group $`G=F/R`$ is recurrent if and only if the series

$$\underset{k=0}{\overset{\mathrm{}}{}}\frac{n_k(R)}{(2m1)^k}$$

diverges. Observe, that the latter is equivalent to the condition that $`_{k=0}^{\mathrm{}}f_k(R)`$ is divergent, i.e., $`\lambda (R)=\mathrm{}`$.

###### Theorem 2.1

Let $`R`$ be a normal subgroup in a free group $`F`$. If the factor group $`F/R`$ is not recurrent then $`R`$ is sparse.

#### Proof.

Let $`F`$ be a free group of rank $`m`$, $`R`$ be a normal subgroup of $`F`$ such that $`F/R`$ is not recurrent. Let $`n_k=|RS_k|`$, and $`f_k=n_k/|S_k|`$. Since $`F/R`$ is not recurrent, it is infinite and, by a result of Woess , the asymptotic density $`\rho (R)=lim_k\mathrm{}f_k`$ exists and equal to $`0`$. By the criterion above the series $`_{k=0}^{\mathrm{}}f_k`$ converges. Therefore it is Abel summable, i.e., there exists a limit

$$\underset{s0^+}{lim}\underset{k=0}{\overset{\mathrm{}}{}}f_k(1s)^k=\underset{k=0}{\overset{\mathrm{}}{}}f_k$$

and

$`\mu (R)`$ $`=`$ $`s{\displaystyle \underset{k=0}{\overset{\mathrm{}}{}}}f_k(1s)^k`$
$`=`$ $`\mu _1s+o(s),`$
where

$$\mu _1=\underset{k=0}{\overset{\mathrm{}}{}}f_k.$$

$`\mathrm{}`$

A classical criterion of amenability, due to Cohen  and Grigorchuk  claims that a finitely generated group $`F/R`$ is amenable if and only if the cogrowth coefficient $`limsup(n_k(R))^{1/k}=2m1`$. This immediately gives the following result.

###### Theorem 2.2

Let $`R`$ be a normal subgroup in $`F`$. If the factor group $`F/R`$ is not amenable then $`R`$ is sparse and polynomially negligible.

#### Proof.

We have mentioned in Section 1.2 that if $`\gamma (R)<1`$ then $`R`$ is $`\lambda `$-measurable, i.e., the series $`_{k=0}^{\mathrm{}}f_k(R)`$ converges. In the same time,

$`{\displaystyle \frac{limsup\left(n_k(R)\right)^{1/k}}{2m1}}`$ $`=`$ $`limsup\left({\displaystyle \frac{n_k(R)}{(2m1)^k}}\right)^{1/k}`$
$`=`$ $`limsup\left({\displaystyle \frac{n_k(R)}{2m(2m1)^{k1}}}\right)^{1/k}`$
$`=`$ $`limsup\left(f_k\right)^{1/k}`$
$`=`$ $`\gamma (R)`$
Hence if $`limsup(n_k(R))^{1/k}<2m1`$ then $`\gamma (R)<1`$ and $`R`$ is sparse by Lemma 1.1. By Corollary 1.6, $`R`$ is polynomially negligible and the theorem follows. $`\mathrm{}`$

It is worth mentioning a corollary from the proof: since the convergence radius of the generating function

$$N(R)=\underset{k=0}{\overset{\mathrm{}}{}}n_kt^k,$$

is $`\left(limsup\left(n_k(R)\right)^{1/k}\right)^1`$, we have:

###### Corollary 2.3

The convergence radius of $`N(R)(t)`$ is $`((2m1)\gamma (R))^1`$.

### 2.2 Return generating function

Let $`M=M(X)`$ be the free monoid generated by $`XX^1`$ and

$$\eta :M(X)F(X)$$

the canonical epimorphism of monoids which is induced by the identity map on $`XX^1`$. Analogously to free groups, denote by $`S_k(M)`$ the set (sphere) of all words in $`M`$ of length $`k`$. Then, given a normal subgroup $`RF`$, we can consider two generating functions,

$$N(t)=n_kt^k\text{ and }N^{}(t)=n_k^{}t^k,$$

where $`n_k=n_k(R)=|RS_k|`$ and $`n_k^{}=n_k^{}(R)=|\eta ^1(R)S_k(M)|`$ (the number of words of length $`k`$ in $`M`$ which are mapped into $`R`$ by $`\eta `$). The function $`N^{}(t)`$ is called the return generating function.

The following formula links the functions $`N(t)`$ and $`N^{}(t)`$ for a normal subgroup $`RF`$:

$$\frac{N(t)}{1t^2}=\frac{N^{}\left(\frac{t}{1+(2m1)t^2}\right)}{1+(2m1)t^2}.$$
(10)
(In  Bartholdi proved a more general result (see Section 2.3), attributing Equation (10) to Godsil \[10, p. 72\].)

> Example 1. We shall use Equation (10) for the computation of the measure of the co-diagonal subgroup $`D`$ of $`F`$, that is, the kernel of the homomorphism $`F`$ defined by mapping all generators $`x_iX`$ to the generator $`1`$ of $``$.
>
> It is easy to see that there are $`\left(\begin{array}{c}2k\\ k\end{array}\right)m^{2k}`$ words of length $`2k`$ in $`M`$ which are mapped by $`\eta `$ into $`D`$. Indeed, these words are $`2k`$-tuples of elements $`x_i`$ (and there are $`m^{2k}`$ of them) with the exponents $`\pm 1`$ assigned to them such that the sum of exponents is $`0`$; there are $`\left(\begin{array}{c}2k\\ k\end{array}\right)`$ assignments of exponents. Since
>
> $$\underset{k=0}{\overset{\mathrm{}}{}}\left(\begin{array}{c}2k\\ k\end{array}\right)t^{2k}=\frac{1}{\sqrt{14t^2}}$$
>
> (see sequence A000984 of ),
>
> $$N^{}\left(t\right)=\underset{k=0}{\overset{\mathrm{}}{}}\left(\begin{array}{c}2k\\ k\end{array}\right)m^{2k}t^{2k}=\frac{1}{\sqrt{14m^2t^2}},$$
>
> and
>
> $`N\left(t\right)`$ $`=`$ $`{\displaystyle \frac{1t^2}{\left(1+\left(2m1\right)t^2\right)\sqrt{1\frac{4m^2t^2}{\left(1+\left(2m1\right)t^2\right)^2}}}}`$
> $`=`$ $`\sqrt{{\displaystyle \frac{1t^2}{1\left(2m1\right)^2t^2}}}`$
> A close look at the zeroes of the denominator in the expression for $`N(t)`$ tells us that the convergence radius of $`N(t)`$ is $`1/(2m1)`$, and Corollary 2.3 reinterprets this statement as $`\gamma (D)=1`$. A direct computation shows that
>
> $$\mu \left(D\right)=\frac{\left(m1\right)}{m\sqrt{2\frac{2}{m}}}\sqrt{s}+o\left(\sqrt{s}\right).$$
>
> An analysis along the lines of the proof of Theorem 1.5 shows that $`D`$ is not polynomially negligible.

Notice that

$$p_k=\frac{n_k^{}}{(2m)^k}$$

is the probability for a simple random walk222This means that we move from a vertex to any of $`2m`$ adjacent vertices with equal probabilities $`1/2m`$. on $`\mathrm{\Gamma }`$ to return to the initial vertex $`H`$ after $`k`$ steps. A considerable body of literature on random walks on groups contains various information about the return probability generating function $`P(t)=_{k=0}^{\mathrm{}}p_kt^k`$ (which is a special instance of the Green function of the random walk). Since $`N^{}(t)=P(2mt)`$ and the frequency generating function

$$F(t)=\underset{k=0}{\overset{\mathrm{}}{}}f_kt^k=1+\underset{k=1}{\overset{\mathrm{}}{}}\frac{n_k}{2m(2m1)^{k1}}t^k$$

is related to $`N(t)`$ as

$$F(t)=1+\frac{2m1}{2m}\left(N\left(\frac{t}{2m1}\right)1\right),$$

we easily convert (10) into the following formula:

$$F(t)=\frac{1}{2m}\frac{(2m1)^2t^2}{(2m1)+t^2}P\left(\frac{2mt}{(2m1)+t^2}\right)+\frac{1}{2m}.$$
(11)
> Example 2. For a normal subgroup $`NF`$, Equation 11 reduces the question of algebraicity of the function $`\mu (N)`$ to that one for the generating function $`N^{}(t)=n_k^{}t^k`$ for the number of non-reduced words in $`N`$. Assume that $`F`$ has rank $`2`$ and take for $`N`$ the derived subgroup $`N=[F,F]`$ of $`F`$. Then non-reduced words of length $`k`$ from the free monoid $`M`$ correspond to simple random walks of length $`k`$ on the factor group $`F/N\times `$ which start and end at $`0`$, the probability of that event being $`n_k^{}/(2m)^k`$. We found ourselves in the classical realm of random walks on lattices. A paper by Montrol \[25, p. 201\] (see also ) contains a closed formula for the return probabilities generating function for a simple random walk on $`\times `$:
>
> $$P\left(t\right)=\frac{2}{\pi z}Q_{1/2}\left(\frac{2t^2}{t^2}\right),$$
>
> where $`Q_{1/2}(z)`$ is a Legendre function of the second kind. As shown in \[25, Equation 22 on p. 201\],
>
> $$P\left(t\right)\frac{1}{\pi t}\mathrm{log}\left(\frac{1t^2}{t^2}\right)\text{as}t1.$$
>
> Since $`\mu _s(N)=sF(1s)`$, after an easy calculation with Equation 11, we see that the function $`\mu (N)`$ is not algebraic and
>
> $$\mu _s\left(N\right)\frac{s\mathrm{log}s}{\pi }\text{as}s0.$$
>
> In particular, $`\mu _s(N)/s`$ has logarithmic divergence at $`s=0`$, $`\mu _1`$ does not exists and $`N=[F,F]`$ is a subgroup of intermediate density.

### 2.3 Non-normal subgroups and random walks on regular graphs

In this section, we transfer Theorem 2.2 from normal to arbitrary subgroups of $`F`$.

If $`H`$ is a (not necessarily normal) subgroup of $`F=F(X)`$, the set $`F/H`$ of right cosets gives rise to the Schreier graph of $`H`$, denoted by $`\mathrm{\Gamma }`$, if we connect the cosets $`Hy`$ and $`Hyx`$, $`xX`$, by a directed edge marked $`x`$. Every closed path in $`\mathrm{\Gamma }`$ from $`H`$ to $`H`$ gives a word in the free monoid $`M(X^{\pm 1})`$ which represents an element from $`H`$, if we read the edge label when we go along the edge, and its inverse, if we go against the direction of the edge. Reduced words correspond to paths without backtracking of edges.

Notice that $`\mathrm{\Gamma }`$ is is a $`2m`$-regular graph, that is, every its vertex has valency $`2m`$.

Denote by $`n_k`$ the number of closed paths without backtracking of edges which start and end at the vertex $`H`$. Notice that $`n_k=n_k(H)`$ is exactly the number of reduced words of length $`k`$ in $`H`$. Also, denote by $`b_k=b_k(H)`$ the number of all paths of length $`k`$ from $`H`$ to $`H`$, and let

$$N(t)=\underset{0}{\overset{\mathrm{}}{}}n_kt^k\text{ and }B(t)=\underset{0}{\overset{\mathrm{}}{}}b_kt^k$$

be the corresponding generating functions.

Formula (10) is a special case of the following result valid for all regular graphs :

$$\frac{N(t)}{1t^2}=\frac{B\left(\frac{t}{1+(2m1)t^2}\right)}{1+(2m1)t^2}.$$
(12)
Denote by

$$p_k=\frac{b_k}{(2m)^k}$$

the probability for a simple random walk on $`\mathrm{\Gamma }`$ to return to the initial vertex $`H`$ after $`k`$ steps. The quantity

$$\nu =limsup\sqrt[k]{p_k}$$

is called the spectral radius of $`\mathrm{\Gamma }`$. Obviously, $`\nu 1`$.

###### Theorem 2.4

If the coset graph $`\mathrm{\Gamma }`$ of a subgroup $`H<F`$ has spectral radius $`\nu <1`$ then $`H`$ is sparse and polynomially negligible.

#### Proof.

Let $`r^{}`$ and $`r^{\prime \prime }`$ be the convergence radii of the formal power series $`N(t)`$ and $`B(t)`$, then, by the well-known result from calculus,

$$r^{}=(limsup\sqrt[k]{n_k})^1\text{ and }r^{\prime \prime }=(limsup\sqrt[k]{b_k})^1.$$

If $`\nu <1`$ then, obviously, $`r^{\prime \prime }>1/(2m)`$. The formula (12) relates the convergence radii of $`N(t)`$ and $`B(t)`$ (see also  where this relation was developed earlier). It is easy to see that $`r^{}>1/(2m1)`$, hence for the relative growth rate of $`H`$ we have: $`\gamma (H)<2m1`$, and by Corollary 1.6 $`H`$ is sparse and polynomially negligible. $`\mathrm{}`$

A similar technique with the use of results from \[18, Chapter 7\] proves the following theorem.

###### Theorem 2.5

(T. Smirnova-Nagnibeda, private communication) If$`H<F`$ is a subgroup of infinite index then its asymptotic density

$$\rho (H)=0.$$

In particular, it follows that $`\mu _0(H)=0`$.

### 2.4 Preimages of quasiconvex subgroups
of hyperbolic factor groups are negligible

Recall that a finitely generated group $`G`$ is word-hyperbolic if for any (some) finite generating set $`S`$ of $`G`$ there is $`\delta 0`$ such that all geodesic triangles in in the Cayley graph $`C(G,S)`$ of $`G`$ with respect to $`S`$ are $`\delta `$-thin, that is, each side is contained in the closed $`\delta `$-neighbourhood of the union of the other two sides. A subgroup $`H`$ of a word-hyperbolic group $`G`$ is quasiconvex if for any (some) generating set $`S`$ of $`G`$ there is $`ϵ0`$ such that every geodesic in $`C(G,S)`$ with both endpoints in $`H`$ is contained in the $`ϵ`$-neighbourhood of $`H`$.

In \[15, Theorem 1.2\] I. Kapovich proved that the coset graph $`G/H`$ of a quasiconvex subgroup $`H`$ of a hyperbolic group $`G`$ has spectral radius $`<1`$. Now, as an application of Theorem 2.4 we have the following result.

###### Theorem 2.6

Let $`RF`$ be a normal subgroup of a free group $`F`$ such that $`F/R`$ is a non-elementary word-hyperbolic group, and $`RH<F`$ a subgroup of infinite index in $`F`$ such that $`H/R`$ is a quasiconvex subgroup of $`F/R`$. Then $`H`$ is sparse and polynomially negligible in $`F`$.

## 3 Measure of a regular set

### 3.1 Regular Languages and finite automata

In this section we show how to compute the measure $`\mu (R)`$ of a regular subset of the free group $`F=F(X)`$ of rank $`m`$. Most of the results here are just a proper interpretation of some well-known facts about regular sets. We refer to  for detailed discussion of regular subsets of $`F`$.

Recall that a finite automaton $`𝒜`$ is a finite labelled oriented graph (possibly with multiple edges and loops). We refer to its vertices as states. Some of the states are called initial states, some accept states. We assume further that every edge of the graph is labelled by one of the symbols $`x^{\pm 1},xX`$. A path in A is a set of edges $`e_0,\mathrm{},e_l`$ such that, for each $`i=1,\mathrm{},l`$, the endpoint of $`e_{i1}`$ is equal to the starting point of $`e_i`$. Reading the labels on edges along the path in the natural order, we get the label of the path. The language accepted by an automaton $`𝒜`$ is the set $`=(𝒜)`$ of labels on paths from an initial state to an accept state. An automaton is said to be deterministic if, for any state, there is at most one arrow with the given label exiting from the state. A regular set is a language accepted by a finite deterministic automaton. For every finite deterministic automaton $`𝒜`$ one can construct a finite deterministic automaton $`𝒜^{}`$ such that $`(𝒜)=(𝒜^{})`$ and where the sets of initial and accept states are disjoint. It would be convenient for us to work only with non-empty words, that is, elements in $`F\{1\}`$.

We assemble here some (mostly well known) facts about regular sets.

###### Theorem 3.1

Let $`A`$ and $`B`$ are regular subsets in $`F`$.

* The sets $`AB`$, $`AB`$ and $`AB`$ are regular.
* The prefix closure $`\overline{A}`$ of a regular set $`A`$ is regular. Here, the prefix closure $`\overline{A}`$ is the set of all initial segments of all words in $`A`$.
* If $`C`$ is a regular set in the free monoid $`M`$ freely generated by $`XX^1`$ then its image $`\overline{C}`$ under the natural reduction homomorphism $`MF`$ is regular.
* The product

$$AB=\{abaA,bB\}$$

and the set of inverses

$$A^1=\{a^1aA\}$$

are regular.
* Every finite subset in $`F`$ is regular.
* If $`\varphi :FF`$ is an endomorphism then the set $`\varphi (A)`$ is regular.

Now we will show how to compute the measure $`\mu ()`$ of a regular language accepted by a finite deterministic automaton $`𝒜`$. Recall, that the measure $`\mu =\{\mu _s\}`$ gives rise to a multiplicative measure $`\mu ^{}=\{\mu _s^{}\}`$

$$\mu _s^{}(w)=\left(\frac{2m}{2m1}\frac{1}{s}\right)\mu _s(w),$$

such that

$$\mu _s^{}(w)=t^{|w|},wheret=\frac{1s}{2m1}.$$

By numbering the states by numbers $`1,\mathrm{},n`$, we can associate with the automaton $`𝒜`$ its adjacency matrix $`A`$ by taking an $`n\times n`$ matrix and writing the number of arrows from from state $`i`$ to state $`j`$ in the position $`(i,j)`$. It is easy to see that the number of different paths of length $`l`$ from state $`i`$ to state $`j`$ is $`(A^l)_{ij}`$ and the measure of the set of labels on these paths is $`t^l(A^l)_{ij}`$. Let $`I`$ and $`J`$ be the sets of initial and accept states. If we denote $`T=tA`$ then it follows that

$$\mu _s^{}()=\underset{iI,jJ}{}((T)_{ij}+(T^2)_{ij}+\mathrm{}).$$

In particular, the series on the right converges for every given $`s`$. Denote by $`B=T+T^2+\mathrm{}`$ the matrix with entries from the ring of formal power series $`[[t]]`$, then, obviously,

$$\mu ^{}()=\underset{iI,jJ}{}B_{ij}$$

and

$$B=(I_nT)^1I_n.$$

We come to the following formula:

$$\mu ^{}()=\underset{iI,jJ}{}((I_nT)^1I_n)_{ij}.$$

If we replace $`𝒜`$ by the automaton $`𝒜^{}`$ which accepts the same language and where an initial state is never an accept state, we can simplify the formula and write

$$\mu ^{}()=\underset{iI,jJ}{}((I_nT)^1)_{ij}.$$

We have as a corollary the following result.

###### Theorem 3.2

The measure $`\mu ^{}(R)`$ (and hence the probability measure $`\mu (R)`$) of a regular subset of $`F`$ is a rational function in $`t`$ (and hence in $`s`$) with rational coefficients.

We can now apply this theorem to the Cesaro density (see Section 1.4) and asymptotic classification of regular sets (see Section 1.5).

###### Corollary 3.3

The Cesaro density of a regular set is a rational number.

###### Corollary 3.4

Every regular set is either thick or sparse.

### 3.2 Thick regular sets

We describe below thick regular sets.

A cone $`C=C(w)`$ with the vertex $`w`$ is a set of all elements in $`F`$ containing the given word $`w`$ as initial segment. Obviously, cones are regular sets.

Let $`B=\{u|u|k1\}`$ be the ball of radius $`k1`$. Then $`FB`$ is the union of $`|S_k|`$ cones each of which has the same measure as the given cone $`C=C(w)`$ with $`|w|=k`$. Hence

$$\mu (C(w))=\frac{1\mu (B)}{|S_{|w|}|}=\frac{1}{|S_{|w|}|}+O(s).$$

In particular, a cone is a thick regular set. The following theorem shows that every thick regular set involves a cone.

###### Theorem 3.5

Let $`R`$ be a regular subset of $`F`$. Then $`R`$ is thick if and only if its prefix closure $`\overline{R}`$ contains a cone.

#### Proof.

Notice that if a regular set $`R`$ is accepted by a finite deterministic automaton $`𝒜`$, then its prefix closure $`\overline{R}`$ is accepted by the automaton $`\overline{𝒜}`$ obtained from $`𝒜`$ by extending the set of accept states by adding all states which belong to a directed path in $`𝒜`$ from an initial state of $`𝒜`$ to an accept state of $`𝒜`$.

Since cones are thick sets, one direction of our theorem immediately follows from the following lemma.

###### Lemma 3.6

Let $`RF`$ be a regular set. Then $`R`$ is thick if and only if its prefix closure $`\overline{R}`$ is thick.

#### Proof.

Of course, if $`R`$ is thick then $`\overline{R}`$ is thick. To prove the reverse, we use the obvious observation that the union of finitely many of sparse sets is sparse (if $`\mu _0`$-measurable). Let $`𝒜`$ be a finite deterministic automaton which accepts $`R`$ and $`v_1,\mathrm{},v_n`$ the accept states of $`\overline{𝒜}`$. Denote by $`R_i`$ the subset of $`\overline{R}`$ accepted by the state $`v_i`$. Then $`\overline{R}=R_1\mathrm{}R_n`$ and one of the regular sets $`R_i`$ is thick. If $`w`$ is a label on a directed path from $`v_i`$ to an accept state, say $`v_j`$, of $`𝒜`$ then

$$R_iw=\{xwxR_i\}$$

is obviously a thick set and belongs to $`R`$. $`\mathrm{}`$

Now we can assume that the set $`R`$ is thick. Since the union of finitely many sparse sets is sparse, we can assume without loss of generality that a finite deterministic automaton $`𝒜`$ for $`R`$ has only one initial state $`I`$ and one accept state $`Z`$. We have to remember that our automaton accepts only reduced words. Therefore $`𝒜`$ can be rewritten in the form where

* For any state $`A`$ of $`𝒜`$, all arrows which enter $`A`$ have the same label $`aXX^1`$ and arrows exiting from $`A`$ cannot have label $`a^1`$ (this can be achieved by splitting the states of $`𝒜`$ in the way shown on Figure 1.) We shall say in this situation that $`A`$ has type $`a`$.
* For every state $`A`$ of $`𝒜`$, there is a directed path from $`A`$ to the accept state $`Z`$.
* In addition, it is easy to arrange that there are no arrows entering the initial state $`I`$.

This means, in particular, that there are at most $`2m`$ arrows exiting from the initial state $`I`$, and at most $`2m1`$ arrows exiting from any other state. We can assign frequencies $`1/2m`$ to arrows exiting from $`I`$ and frequencies $`1/(2m1)`$ to arrows exiting from other states. Now, for a word $`w`$ accepted by $`𝒜`$, its relative frequency

$$\lambda (w)=\frac{1}{2m(2m1)^{|w|1}}$$

is the product of frequencies of arrows in a directed path from the initial state $`I`$ to the accept state $`Z`$ which correspond to the word $`w`$. We aim at proving the following statement from which our theorem immediately follows by virtue of Lemma 1.1:

> If $`\overline{R}`$ contains no cone then it is $`\lambda `$-measurable, that is,
>
> $$\lambda (R)=\underset{wR}{}\lambda (w)$$
>
> is finite.

For that purpose form the automaton $`𝒜_1`$ obtained from $`𝒜`$ by removing all arrows exiting from $`Z`$; we take $`I`$ and $`Z`$ for its initial and accept states, correspondingly. Consider also the automaton $`𝒜_2`$ formed by all states accessible from the state $`Z`$, with the same arrows between them as in $`𝒜`$; we take $`Z`$ for the both initial and accept states.

We assign to arrows in $`𝒜_1`$ and $`𝒜_2`$ the same frequencies as to arrows in $`𝒜`$. Since $`I`$ does not belong to $`𝒜_2`$, all arrows in $`𝒜_2`$ have frequencies $`1/(2m1)`$. If now $`R_1`$ and $`R_2`$ are languages accepted by $`𝒜_1`$ and $`𝒜_2`$ then, obviously, $`R=R_1R_2`$. Moreover, if $`uR_1`$ and $`vR_2`$ then the word $`uv`$ is reduced and

$$\lambda (uv)=\lambda (u)\lambda ^{}(v).$$

Since the presentation of $`R`$ in the form $`R=R_1R_2`$ is unambiguous, it follows that

$$\lambda (R)=\lambda (R_1)\lambda ^{}(R_2).$$

Transform the automaton $`𝒜_2`$ further by splitting the state $`Z`$ into separate initial state $`Z_1`$ (with no arrows entering it, and those arrows which exited from $`Z`$ now exiting from $`Z_1`$), and the accept state $`Z_2`$ (with no arrows exiting from it, and those arrows which entered $`Z`$ now entering $`Z_1`$). If $`R_3`$ is the language accepted by the new automaton $`𝒜_3`$, then, obviously,

$$R_2=R_3(R_3R_3)(R_3R_3R_3)\mathrm{}$$

and

$$\lambda ^{}(R_2)\lambda ^{}(R_3)+\lambda ^{}(R_3)^2+\lambda ^{}(R_3)^3+\mathrm{}.$$

Assume that $`\overline{R}`$ contains no cone. Then the both subsets $`\overline{R}_1`$ and $`\overline{R}_2`$ contains no cone.

Let us look first at $`𝒜_2`$. Assume that, for every state $`A`$ of $`𝒜_2`$ of type $`aXX^1`$, every possible label from $`XX^1\{a\}`$ is present on one of the arrows exiting from $`A`$. Then it is easy to see that $`\overline{R}_2`$ contains a cone. Therefore we can assume that, for some state $`A`$, there are less than $`2m1`$ arrows exiting from $`A`$. If we now look at the automaton $`𝒜_3`$, it becomes obvious that $`\lambda ^{}(R_3)<1`$. To see this formally, we can consider a Markov chain $``$ whose states are the states of $`𝒜_3`$ together with a additional dead state $`D`$ (see  for background material on Markov chains). We set the transition probabilities from $`Z_2`$ to $`Z_2`$ and from $`D`$ to $`D`$ being equal $`1`$. Every arrow in $`𝒜_3`$ corresponds to a transition in $``$ with the transition probability $`1/(2m1)`$. If at some state $`A`$ of $`𝒜_2`$ there is no arrow labelled $`bXX^1`$ exiting from $`A`$, we make in $``$ a transition from $`A`$ to $`D`$ with the transition probability $`1/(2m1)`$. The probability distribution on $``$ concentrated at the initial state $`Z_1`$, converges to the steady state $`P`$ which is zero everywhere with the exception of the two dead states $`Z_2`$ and $`D`$. Since $`P(D)1`$, $`P(Z_2)<1`$. But, obviously, $`P(Z_2)=\lambda ^{}(R_3)`$.

Now the summation of the geometric progression for $`\lambda ^{}(R_2)`$ shows that $`\lambda ^{}(R_2)<\mathrm{}`$.

An analogous argument for $`𝒜_1`$ shows that $`\lambda (R_1)<\mathrm{}`$. Therefore $`\lambda (R)<\mathrm{}`$. $`\mathrm{}`$ $`\mathrm{}`$

### 3.3 Measures of finitely generated subgroups

Let $`F=F(X)`$ be the free group with basis $`X`$. It is well known that finitely generated subgroups in $`F`$ are regular sets; the most suitable for our purpose exposition of this and similar results can be found in .

Let $`\mu ^{}`$ be the adjusted multiplicative measure on $`F`$. Let $`H`$ be a subgroup of $`F`$ generated by elements $`h_1,\mathrm{},h_k`$. We shall slightly modify the arguments from the previous section to produce a somewhat more practical procedure for computing the measure $`\mu ^{}(H)`$. In particular, $`\mu ^{}(H)`$ will be expressed as a rational function of measures $`\mu ^{}(w_i)`$ of certain words $`w_1,\mathrm{},w_s`$ which do not depend on choice of generators $`h_1,\mathrm{},h_m`$ in $`H`$ although can be easily computed from them.

Let $`\mathrm{\Gamma }`$ be the core subgroup graph of $`H`$ in sense of . Notice that $`\mathrm{\Gamma }`$ does not depend on a particular choice of generators of $`H`$. We mark on $`\mathrm{\Gamma }`$ the initial vertex $`1`$ and those vertices which have degree at least $`3`$. This new vertex set $`V^{}`$ can be turned into a digraph $`\mathrm{\Gamma }^{}`$ with edges labelled by freely reduced words from $`F`$. To do so, we define edges of $`\mathrm{\Gamma }^{}`$ to be reduced paths in $`\mathrm{\Gamma }`$ which start and end at vertices in $`V^{}`$ and do not pass through any other vertex from $`V^{}`$. The label of the path becomes the label of the corresponding edge in $`\mathrm{\Gamma }^{}`$. We call $`\mathrm{\Gamma }^{}`$ the consolidated subgroup graph of $`H`$.

Now it is easy to see that, since $`\mathrm{\Gamma }`$ is folded, a reduced path in $`\mathrm{\Gamma }^{}`$, viewed as a path in $`\mathrm{\Gamma }`$, is also reduced. Every element $`hH`$ is the label of a reduced path in $`\mathrm{\Gamma }`$ from $`1`$ to $`1`$, as well as, the label $`w_1\mathrm{}w_l`$ of the corresponding reduced path in $`\mathrm{\Gamma }^{}`$ from $`1`$ to $`1`$. It follows that $`\mu ^{}(h)=\mu ^{}(w_1)\mathrm{}\mu ^{}(w_l)`$.

Our description of the matrix method of computing the measure of a finitely generated subgroup will be illustrated by the following example, which we do in parallel with the formal discussion.

> Example 3. Let $`C`$ be a subgroup generated by a single element $`c`$. Obviously $`c`$ can be presented in the form $`c=uvu^1`$ without cancellations between the words $`u`$, $`v`$ and $`u^1`$. The consolidated subgroup graph $`\mathrm{\Gamma }^{}(C)`$ of $`C`$ has the form

We start with the consolidated subgroup graph $`\mathrm{\Gamma }^{}`$ of $`H`$. If $`e`$ is an edge in $`\mathrm{\Gamma }^{}`$, we denote its label by $`\lambda (e)`$. As usually, we use the convention that for every edge $`e`$ we also have an edge with the opposite direction and the inverse label $`\lambda (e)^1`$,

> so, in our example, $`\mathrm{\Gamma }^{}(C)`$ is a digraph with $`4`$ directed edges.

The process of writing non-trivial random words from $`H`$ can be described by the automaton $`T`$ which consists of one state for each directed edge of the digraph $`\mathrm{\Gamma }^{}`$ plus one initial state. Every directed edge $`e`$ of $`\mathrm{\Gamma }^{}`$ is interpreted as the state “we wrote the word $`\lambda (e)`$ of $`e`$”, the initial state is “we wrote the empty word”. If the origin of edge $`f`$ is the terminus of edge $`e`$, we say that there is a transition from the state “we wrote the word $`\lambda (e)`$ to the state “we wrote the word $`\lambda (f)`$”, and we assign to this transition measure $`\mu ^{}(\lambda (f))`$. To a directed edge $`e`$ which exits from the initial vertex $`1`$ of $`\mathrm{\Gamma }^{}`$, we assign the transition from the state “we wrote the empty word” to the state “we wrote the word $`\lambda (e)`$” with measure $`\mu ^{}(\lambda (e))`$. Finally, the accept states of our automaton $`T`$ correspond to directed edges of $`\mathrm{\Gamma }^{}`$ whose terminuses are the initial vertex $`1`$.

We label the states of $`T`$ by consecutive numbers $`1,2,3,\mathrm{}`$, so that the initial state “we wrote the empty word” has label $`1`$. Now the transition measures of automaton $`T`$ form a matrix which we denote $`A`$.

> In our Example 2, the states are:
>
> * We wrote an empty word (the initial state);
> * we wrote $`u`$;
> * we wrote $`v`$;
> * we wrote $`v^1`$;
> * we wrote $`u^1`$ (the accept state).
>
> and the transition matrix is
>
> $$A=\left(\begin{array}{ccccc}0& p& 0& 0& 0\\ 0& 0& q& q& 0\\ 0& 0& q& 0& p\\ 0& 0& 0& q& p\\ 0& 0& 0& 0& 0\end{array}\right),$$
>
> where $`p=\mu ^{}(u)`$ and $`q=\mu ^{}(v)`$.

Let $`j_1,\mathrm{},j_k`$ be the accept states of $`T`$. The multiplicativity of the adjusted measure $`\mu ^{}`$ allows to use the same matrix technique as in computations on Markov chains, and the measure of the set of words from $`H`$ which can be obtained by $`l`$ moves becomes the sum

$$\left(A^l\right)_{1j_1}+\mathrm{}+\left(A^l\right)_{1j_k}$$

of the matrix elements of the matrix $`A^l`$ which correspond to transition from the initial to an accept state. Notice that we produce only non-trivial elements of $`H`$. Hence the set $`H\{1\}`$ of non-trivial elements in $`H`$ has the measure

$$\mu ^{}(H\{1\})=\underset{i=1}{\overset{k}{}}\left(A+A^2+\mathrm{}+A^n+\mathrm{}\right)_{1j_i}.$$

Denote $`B=A+A^2+\mathrm{}`$, then, obviously,

$$B=(EA)^1E,$$

where $`E`$ is the identity matrix. Since, by our construction, the initial state is never an accept state, the matrix elements $`(B)_{ij_1},\mathrm{},(B)_{1j_k}`$ do not lie on the diagonal and therefore $`(B)_{1j_i}=((EA)^1)_{1j_i}`$ for all $`i=1,\mathrm{},k`$. Hence

$$\mu ^{}(H\{1\})=\underset{i=1}{\overset{k}{}}\left((EA)^1\right)_{1j_i}.$$
(13)
Since the elements of the inverse matrix $`(EA)^1`$ are rational functions of matrix elements of the matrix $`A`$, we proved the following theorem.

###### Theorem 3.7

If $`\mu `$ is the multiplicative measure on $`F`$, the measure $`\mu (H)`$ of a finitely generated subgroup $`H`$ of $`F`$ is a rational function of the measures of labels on the consolidated subgroup graph of $`H`$.

In particular, $`\mu (H)`$ is a rational function of $`s`$.

> In Example 3, a direct computation with Mathematica shows that
>
> $$\left(EA\right)^1=\left(\begin{array}{ccccc}1& p& \frac{pq}{1q}& \frac{pq}{1q}& \frac{2p^2q}{1q}\\ 0& 1& \frac{q}{1q}& \frac{q}{1q}& \frac{2pq}{1q}\\ 0& 0& \frac{1}{1q}& 0& \frac{p}{1q}\\ 0& 0& 0& \frac{1}{1q}& \frac{p}{1q}\\ 0& 0& 0& 0& 1\end{array}\right)$$
>
> and
>
> $`\mu ^{}\left(C\left\{1\right\}\right)`$ $`=`$ $`{\displaystyle \frac{2p^2q}{1q}}`$
> $`=`$ $`{\displaystyle \frac{2t^{2\left|u\right|}t^{\left|v\right|}}{1t^{\left|v\right|}}}.`$
> Hence
>
> $`\mu \left(C\left\{1\right\}\right)`$ $`=`$ $`{\displaystyle \frac{2m1}{2m}}s{\displaystyle \frac{2\left(\frac{1s}{2m1}\right)^{2\left|u\right|+\left|v\right|}}{1\left(\frac{1s}{2m1}\right)^{\left|v\right|}}}`$
> $`=`$ $`{\displaystyle \frac{2}{2m\left(2m1\right)^{2\left|u\right|+\left|v\right|1}\left(1\left(\frac{1}{2m1}\right)^{\left|v\right|}\right)}}s+o\left(s\right).`$

### 3.4 Normal subgroups of finite index

Kouksov  proved that a normal subgroup $`NF`$ has a rational cogrowth function $`f(t)=n_kt^k`$ if and only if the index $`|F:N|`$ is finite. In that case $`N`$ is finitely generated, and its subgroup graph $`\mathrm{\Gamma }`$ is the Cayley graph of $`G`$. In notation of (10), the generating function $`N^{}(t)`$ for the number of non-reduced words in $`N`$ has a very beautiful form found by Quenell :

$$N^{}(t)=\frac{1}{|G:N|}\frac{1}{1\lambda _it},$$

where $`\lambda _i`$ are the eigenvalues of the adjacency matrix of $`\mathrm{\Gamma }`$.

## 4 Context free languages

Combinatorial analysis of context free languages is a well established area of combinatorics with powerful tools for manipulating generating functions of languages; a very good exposition of the theory, pioneered by Chomski and Schutzenberger , can be found in . Here we give only a small example of use of this machinery, motivated by applications of our methods to study of complexity of algorithms on amalgamated products of free groups . We do not give rather technical and lengthy definitions related to context-free languages which can be found in  (see also  for a compact formal definition).

Let $`M`$ be the free monoid generated by $`XX^1`$. We call two subsets $`R,SM`$ isobaric if, for every $`k`$, they contain equal number of words of length $`k`$, that is, if the have the same generating function.

> Example 4. Let $`X=YZ`$, where $`|Y|=l1`$ and $`|Z|=n1`$. We shall find the measure of the set
>
> $$R=\underset{gF}{}F\left(Y\right)_{}^{\mathrm{}}{}_{}{}^{g}$$
>
> of all elements in $`F`$ conjugate to non-identity elements in $`F(Y)`$. Here, as usually, we denote by $`F(Y)^{\mathrm{}}`$ the set of non-identity elements of $`F(Y)`$. Obviously, we can decompose
>
> $$R=F\left(Y\right)^{\mathrm{}}F\left(Y\right)^h,$$
>
> where the union is taken over all elements in $`F`$ which start with letters in $`ZZ^1`$. The generating function for $`F(Y)^{\mathrm{}}`$ is obvious:
>
> $`f\left(t\right)`$ $`=`$ $`{\displaystyle \underset{k=1}{\overset{\mathrm{}}{}}}2l\left(2l1\right)^{k1}t^k`$
> $`=`$ $`2lt\left(1\left(2l1\right)t\right)^1.`$
> Denote $`L_1=F(Y)^{\mathrm{}}`$ and let $`L_2`$ be the cone of words in $`F`$ which start from symbols in $`ZZ^1`$. It is easy to see that, in the free monoid $`M(X)`$, the language $`L_2^1L_1L_2`$ is isobaric to to the language $`L_1L_2^2`$, where $`L_2^2=\{fffL_2\}`$ and $``$ denotes formal product in $`M(X)`$ without cancellation. The generating function of $`L_2`$ is
>
> $$g\left(t\right)=\underset{k=1}{\overset{\mathrm{}}{}}2n\left(2m1\right)^{k1}t^k=2nt\left(1\left(2m1\right)t\right)^1,$$
>
> and the generating function for $`L_2^2`$ is $`g(t^2)`$. According to the standard rules of computation of generating functions for context-free languages , the generating function for $`L_1L_1L_2^2`$ is
>
> $$f\left(t\right)+f\left(t\right)g\left(t^2\right)=2lt\left(1\left(2l1\right)t\right)^1\left(1+2nt^2\left(1\left(2m1\right)t^2\right)^1\right)$$
>
> and therefore
>
> $`\mu \left(R\right)`$ $`=`$ $`{\displaystyle \frac{2m1}{2m}}s2l{\displaystyle \frac{1s}{2m1}}\left(1\left(2l1\right){\displaystyle \frac{1s}{2m1}}\right)^1`$
> $`\times \left(1+2n\left({\displaystyle \frac{1s}{2m1}}\right)^2\left(1\left(2m1\right)\left({\displaystyle \frac{1s}{2m1}}\right)^2\right)^1\right)`$
> $`=`$ $`{\displaystyle \frac{l}{m}}\left(1{\displaystyle \frac{2l1}{2m1}}\right)^1\left(1+{\displaystyle \frac{2n}{\left(2m1\right)^2}}\right)\left(1{\displaystyle \frac{1}{2m1}}\right)^1s+o\left(s\right).`$

Notice that by , a normal subgroup $`NF`$ is context-free if and only if the factor group $`F/N`$ is free-by-finite.

## 5 Addendum: A Tauberian Theorem by Hardy and Littlewood

We found ourselves in the context where generalised summation methods for series are essential.

> Example 5. Consider the subgroup $`H`$ of index $`2`$ in $`F`$ which consists of all words of even length in $`F`$. Let $`n_k`$ be the number of elements of length $`k`$ in $`H`$ and
>
> $$f_k=\frac{n_k}{\left|S_k\right|}$$
>
> be the relative frequency of elements of length $`k`$ from $`H`$ among all elements of length $`k`$ in $`F`$. Obviously,
>
> $$f_k=\{\begin{array}{cc}\hfill 1& \text{ if }k\text{ is even}\hfill \\ \hfill 0& \text{ if }k\text{ is odd}\hfill \end{array}.$$
>
> One can easily see that
>
> $`\mu \left(H\right)`$ $`=`$ $`s+s{\displaystyle \underset{k=1}{\overset{\mathrm{}}{}}}\left(1s\right)^{2k}`$
> $`=`$ $`s+{\displaystyle \frac{s\left(1s\right)^2}{1\left(1s\right)^2}}`$
> $`=`$ $`{\displaystyle \frac{1}{2}}+{\displaystyle \frac{s}{4}}+{\displaystyle \frac{s^2}{8}}+{\displaystyle \frac{s^3}{16}}+\mathrm{}`$
> When $`s0^+`$, $`\mu (H)1/2`$.

To explain the rather expected appearance of $`1/2`$ as the ‘limit probability’ of the subgroup $`H`$ in Example 5, we need to invoke one of the so-called Tauberian theorems by Hardy and Littlewood.

###### Theorem 5.1

\[13, Theorems 94\] Let $`\{a_n\}`$ be a sequence of real numbers such that the sequence of partial sums

$$S_n=a_0+\mathrm{}+a_n$$

is bounded from below. Assume also that the limit (the Abelian sum of $`\{a_n\}`$)

$$\underset{x1^{}}{lim}\underset{k=0}{\overset{\mathrm{}}{}}a_kx^k$$

exists and equals $`S`$. Then the sequence $`\{a_n\}`$ is Cesaro summable in the sense that the limit

$$\underset{n\mathrm{}}{lim}\frac{S_0+S_1+\mathrm{}+S_n}{n+1}$$

exists and equal $`S`$.

###### Corollary 5.2

Assume that the sequence $`\{f_n\}`$ of non-negative real numbers is bounded and the sum $`_{k=0}^{\mathrm{}}f_k(1s)^k`$ converges for all $`0<s<1`$. Assume, in addition, that there exists the limit

$$\underset{s0^+}{lim}s\underset{k=0}{\overset{\mathrm{}}{}}f_k(1s)^k=\mu _0.$$

Then

$$\mu _0=\underset{k\mathrm{}}{lim}\frac{f_0+f_1+\mathrm{}+f_k}{k+1}$$

#### Proof.

Set $`t=1s`$ and rewrite

$`s{\displaystyle \underset{k=0}{\overset{\mathrm{}}{}}}f_k(1s)^k`$ $`=`$ $`(1t){\displaystyle \underset{k=0}{\overset{\mathrm{}}{}}}f_kt^k`$
$`=`$ $`f_0+(f_1f_0)t+(f_2f_1)t^2+\mathrm{},`$
and the series on the right converges for all $`0<t<1`$. Moreover,

$$\underset{t1^{}}{lim}\left(f_0+\underset{k=1}{\overset{\mathrm{}}{}}(f_kf_{k1})t^k\right)=\mu _0.$$

Since the partial sums

$$f_0+(f_1f_0)+\mathrm{}+(f_kf_{k1})=f_k$$

are bounded from below, the previous theorem yields

$`\mu _0`$ $`=`$ $`\underset{k\mathrm{}}{lim}{\displaystyle \frac{[f_0]+[f_0+(f_1f_0)]+\mathrm{}+[f_0+(f_1f_0)+\mathrm{}+(f_kf_{k1})]}{k+1}}`$
$`=`$ $`\underset{k\mathrm{}}{lim}{\displaystyle \frac{f_0+f_1+\mathrm{}+f_k}{k+1}}.`$
$`\mathrm{}`$

Corollary 5.2 explains, in particular, that for our subgroup $`H`$ of index $`2`$ in $`F`$, $`\mu (H)=\mu _0+o(1)`$, where

$$\mu _0=\underset{n\mathrm{}}{lim}\frac{1+0+\mathrm{}+1+0}{2n}=\frac{1}{2}.$$

The following corollary is an easy consequence of Corollary 5.2 and Theorem 5.1.

###### Corollary 5.3

Assume that the sequence $`\{f_k\}`$ of non-negative real numbers is bounded, the sum $`_{k=0}^{\mathrm{}}f_k(1s)^k`$ is convergent for all $`0<s<1`$ and the function

$$\mu (s)=s\underset{k=0}{\overset{\mathrm{}}{}}f_k(1s)^k$$

has the limit

$$\underset{s0^+}{lim}\mu (s)=\mu _0.$$

Then

* $`\mu _0`$ is the Cesaro limit

$$\mu _0=\underset{k\mathrm{}}{lim}\frac{f_0+f_1+\mathrm{}+f_k}{k+1}.$$
* If $`\mu _0=0`$ and the limit

$$\mu _1=\underset{s0^+}{lim}\frac{\mu (s)}{s}$$

exists then the sum $`f_k`$ is convergent and

$$\mu _1=\underset{k=1}{\overset{\mathrm{}}{}}f_k.$$
* If the series $`f_k`$ converges, then $`\mu _0`$ and $`\mu _1`$ exist, $`\mu _0=0`$ and

$$\mu _1=\underset{k=0}{\overset{\mathrm{}}{}}f_k.$$
* In particular, if the function $`\mu (s)`$ is analytic in the vicinity of $`0`$ and regular at $`s=0`$, then, in the power series expansion at $`s=0`$,

$$\mu _0=\underset{k\mathrm{}}{lim}\frac{f_0+f_1+\mathrm{}+f_k}{k+1},$$

and, if $`\mu _0=0`$, the next coefficient is given by

$$\mu _1=\underset{k=1}{\overset{\mathrm{}}{}}f_k.$$

#### Proof.

(a) directly follows from 5.2.

For a proof of (b), notice that by Theorem 5.1

$$\mu _1={}_{}{}^{C}\underset{k=1}{\overset{\mathrm{}}{}}f_k,$$

where the sum $`{}_{}{}^{C}f_k`$ is understood in the sense of the Cesaro limit of the partial sums $`S_k=f_1+\mathrm{}+f_k`$:

$${}_{}{}^{C}\underset{k=1}{\overset{\mathrm{}}{}}f_k=\underset{n\mathrm{}}{lim}\frac{1}{n}(S_1+\mathrm{}+S_n).$$

But for non-negative series, Cesaro summability is equivalent to the ordinary convergence, which yields the result.

For (c), assume that the series $`f_k`$ converges. By Abel’s theorem on continuity of sums of power series, the function $`f(s)`$ is continuous on the interval $`[0,1)`$ and hence

$$\mu _1=\underset{s0^+}{lim}f(s)=\underset{k=0}{\overset{\mathrm{}}{}}f_k$$

and

$$\mu _0=\underset{s0^+}{lim}sf(s)=0.$$

(d) is an immediate corollary of (a)- and (b). $`\mathrm{}`$

### Acknowledgements

The authors thank Ilya Kapovich, Ziad Maassarani, Guennadi Noskov, Mark Policott, Richard Sharp and Tatiana Smirnova-Nagnibeda for useful discussions.

Alexandre V. Borovik, Department of Mathematics, UMIST, PO Box 88,Manchester M60 1QD, United Kingdom

borovik@umist.ac.uk

http://www.ma.umist.ac.uk/avb/

Alexei G. Myasnikov, Department of Mathematics, The City College of New York, New York, NY 10031, USA

alexeim@att.net

http://home.att.net/~alexeim/index.htm

Vladimir N. Remeslennikov, Omsk Branch of Mathematical Institute SB RAS,13 Pevtsova Street, Omsk 644099, Russia

remesl@iitam.omsk.net.ru


format: text

text:
# Leptogenesis and Low Energy CP Violation 11footnote 1Talk given by MNR at the RTN meeting : “Across the Present Energy Frontier : Probing the Origin of Mass”, Corfu, Greece, 10 September- 13 September 2001

## 1 Introduction

In the Standard Model (SM) neutrinos are massless and there is no CP violation in the leptonic sector. However at present there is strong evidence for neutino oscillations reported by the SuperKamiokande experiment  and recently confirmed by the results of the Sudbury Neutrino Observatory (SNO) , both pointing towards nonzero neutrino masses. The most straightforward way of extending the SM in order to incorporate neutrino masses is to add one right-handed neutrino field per generation, singlet under the $`SU(3)_c\times SU(2)\times U(1)`$ gauge symmetry, in analogy with the quark sector. In Grand Unified Theories (GUTs), such as $`SO(10)`$ GUTs , these right-handed neutrino states appear in irreducible representations, together with quarks and leptons. Although this might look like a trivial extension of the SM it is far reaching in its consequences, giving rise to entirely new phenomena in the leptonic sector, due to the fact that neutrinos are neutral particles. In fact, if lepton number conservation is not imposed, a Majorana mass term for the neutral right-handed gauge singlets must be included in the Lagrangean, together with the usual Dirac mass term, leading to the seesaw mechanism  which accounts, in an elegant way, for the smallness of neutrino masses. Furthermore mixing and CP violation in the leptonic sector naturally arise once right-handed neutrino singlets are included 666It was shown long ago that mixing and CP violation in the leptonic sector can also occur with strictly massless neutrinos in a model where, in addition to right-handed neutrinos, an equal number of gauge singlet leptons are included . CP violation in the leptonic sector can have profound cosmological implications leading to the generation of the observed Baryon number Asymmetry of the Universe (BAU) via Leptogenesis. In this framework, the starting point is a CP asymmetry generated through out-of-equilibrium L-violating decays of the heavy Majorana neutrinos  leading to a lepton asymmetry L$``$0 while B=0 is still maintained. Subsequently, sphaleron processes , which are (B+L) violating and (B-L) conserving restore (B+L)=0 thus creating a nonvanishing B. This mechanism is, at present, one of the most appealing scenarios for Baryogenesis. Leptogenesis has been studied in detail by several groups  and it has been shown that the observed BAU of $`n_B/s10^{10}`$ can be obtained in the above scenario without any fine-tuning of parameters. In our work  we address the question of whether it is possible to establish a connection between CP breaking necessary to generate leptogenesis and CP violation at low energies. More specifically, assuming that baryogenesis is achieved through leptogenesis, can one infer the strength of CP violation at low energies from the size and sign of the observed BAU? We start by studying the various sources of CP violation in the minimal seesaw model (i.e.,no left-handed Majorana mass terms) identifying both the CP violating phases and the weak-basis (WB) invariants which are associated to leptogenesis and those relevant for CP violation at low energies. We proceed by showing that this connection is not possible in general, but we present special scenarios where the connection can be established. Several authors have addressed this question under different assumptions .

## 2 Framework

Let us consider a minimal extension of the SM which consists of adding to the standard spectrum one right-handed neutrino per generation. After spontaneous gauge symmetry breaking the leptonic mass terms can be written as

$`_m`$ $`=`$ $`[\overline{\nu _L^0}m_D\nu _R^0+{\displaystyle \frac{1}{2}}\nu _R^{0T}CM_R\nu _R^0+\overline{l_L^0}m_ll_R^0]+h.c.=`$ (1)
$`=`$ $`[{\displaystyle \frac{1}{2}}n_L^TC^{}n_L+\overline{l_L^0}m_ll_R^0]+h.c.`$
where $`m_D`$, $`M_R`$ and $`m_l`$ denote the neutrino Dirac mass matrix, the right-handed neutrino Majorana mass matrix and the charged lepton mass matrix, respectively, and $`n_L=(\nu _L^0,(\nu _R^0)^c)`$. Obviously in this minimal extension of the SM a term of the form $`\frac{1}{2}\nu _L^{0T}Cm_L\nu _L^0`$ does not appear in the Lagrangean and the matrix $``$ is given by:

$$=\left(\begin{array}{cc}0& m\\ m^T& M\end{array}\right)$$
(2)
with a zero entry on the (11) block. For notation simplicity, we have dropped the subscript in $`m_D`$ and $`M_R`$. It has been shown that in the most general case, when $``$ includes $`m_L`$, the number of CP violating phases in $``$ is given by :

$$N_{CP}=nn^{}+\frac{n(n1)}{2}$$
(3)
where $`n`$ is the number of $`\nu _L`$ fields and $`n^{}`$ the number of $`\nu _R`$ fields. In our case $`n=n^{}`$. Without $`m_L`$ the number of independent CP violating phases was computed in Ref. to be:

$$n_{CP}=n^2n$$
(4)
For defineteness, we shall consider the case of three generations (three light neutrinos). In this case the number of physical parameters contained in $`_m`$ is a total of fifteen real parameters and six CP violating phases as can be easily seen by going to the weak-basis (WB) where $`m_l`$ and $`M`$ are chosen to be diagonal and real matrices. Of course there is no loss of generality in the choice of a weak-basis. In this WB, there will be six real parameters in $`m_l`$ and $`M`$, on the other hand $`m`$ is a general three-by-three matrix and can be written as the product of a unitary times a Hermitian matrix:

$$m=UH=P_\xi \widehat{U}_\rho P_\tau P_\beta ^{}\widehat{H_\sigma }P_\beta $$
(5)
with $`P_\xi =\mathrm{diag}.(\mathrm{exp}(i\xi _1),\mathrm{exp}(i\xi _2),\mathrm{exp}(i\xi _3))`$, $`P_\tau =\mathrm{diag}.(1,\mathrm{exp}(i\tau _1),\mathrm{exp}(i\tau _2))`$ and $`P_\beta =\mathrm{diag}.(1,\mathrm{exp}(i\beta _1),\mathrm{exp}(i\beta _2))`$. In the second equality we have factored out of U and H as many phases as possible leaving $`\widehat{U}_\rho `$ and $`\widehat{H_\sigma }`$ with only one phase each. Since $`P_\xi `$ can be rotated away by a WB transformation corresponding to a simultaneous phase redefinition of the left-handed charged lepton fields, and the left-handed neutrino fields, the matrix $`m`$ is left with six independent phases and nine real parameters. We shall denote the six independent phases as $`\rho `$ in $`\widehat{U}_\rho `$, $`\alpha _1`$, $`\alpha _2`$ in the product $`(P_\tau P_\beta ^{})`$, $`\sigma `$ in $`\widehat{H_\sigma }`$ and $`\beta _1`$, $`\beta _2`$ in $`P_\beta `$.

## 3 CP violating phases relevant for leptogenesis

Leptogenesis gives rise to the BAU through out-of-equilibrium decay of heavy Majorana neutrinos in the symmetric phase (i.e., before spontaneous gauge symmetry breakdown). The computation of the lepton number asymmetry, in this extension of the SM, resulting from the decay of a heavy Majorana neutrino $`N^j`$ into charged leptons $`l_i^\pm `$ ($`i`$= e, $`\mu `$ , $`\tau `$) can be done both in the symmetric phase  and in the broken phase , . We define the lepton family number asymmetry as $`\mathrm{\Delta }A_{}^{j}{}_{i}{}^{}=N_{}^{j}{}_{i}{}^{}\overline{N}_{}^{j}{}_{i}{}^{}`$. The lepton number asymmetry from j th heavy Majorana particle is then given by:

$$A^j=\frac{_i\mathrm{\Delta }A_{}^{j}{}_{i}{}^{}}{_i\left(N_{}^{j}{}_{i}{}^{}+\overline{N^j}_i\right)}$$
(6)
with the sum in $`i`$ running over the three flavours $`i`$ = e $`\nu `$ $`\tau `$. In this framework the calculations lead to:

$`A^j`$ $`=`$ $`{\displaystyle \frac{g^2}{M_{W}^{}{}_{}{}^{2}}}{\displaystyle \underset{kj}{}}\left[\mathrm{Im}\left((m^{}m)_{jk}(m^{}m)_{jk}\right){\displaystyle \frac{1}{16\pi }}\left(I(x_k)+{\displaystyle \frac{\sqrt{x_k}}{1x_k}}\right)\right]{\displaystyle \frac{1}{(m^{}m)_{jj}}},`$ (7)
$`=`$ $`{\displaystyle \underset{kj}{}}\left[\mathrm{Im}\left((y_{D}^{}{}_{}{}^{}y_D)_{jk}(y_{D}^{}{}_{}{}^{}y_D)_{jk}\right){\displaystyle \frac{1}{8\pi }}\left(I(x_k)+{\displaystyle \frac{\sqrt{x_k}}{1x_k}}\right)\right]{\displaystyle \frac{1}{(y_{D}^{}{}_{}{}^{}y_D)_{jj}}},`$
The second equality results from the substitution $`m_{ij}=y_{Dij}\frac{v}{\sqrt{2}}`$, with $`y_{Dij}`$ denoting the coefficients of the neutrino Yukawa couplings and $`v`$ the Higgs vacuum expectation value. The variable $`x_k`$ is defined as $`x_k=\frac{M_{k}^{}{}_{}{}^{2}}{M_{j}^{}{}_{}{}^{2}}`$ and $`I(x_k)=\sqrt{x_k}\left(1+(1+x_k)\mathrm{log}(\frac{x_k}{1+x_k})\right)`$. From Eq.(7) it can be seen that the lepton number asymmetry is only sensitive to the CP violating phases appearing in $`m^{}m`$. With the choice of phases of Eq.(5) leptogenesis is only sensitive to $`\sigma `$, $`\beta _1`$ and $`\beta _2`$.

## 4 Weak-basis invariants and CP violation

The most general CP transformation of the leptonic fermion fields, still in a WB, which leaves the gauge interaction invariant is of the form

$`\mathrm{CP}l_L(\mathrm{CP})^{}`$ $`=`$ $`U^{}\gamma ^0\mathrm{C}\overline{l_L}^T\mathrm{CP}l_R(\mathrm{CP})^{}=V^{}\gamma ^0\mathrm{C}\overline{l_R}^T`$
$`\mathrm{CP}\nu _L(\mathrm{CP})^{}`$ $`=`$ $`U^{}\gamma ^0\mathrm{C}\overline{\nu _L}^T\mathrm{CP}\nu _R(\mathrm{CP})^{}=W^{}\gamma ^0\mathrm{C}\overline{\nu _R}^T`$ (8)
where $`U^{}`$, $`V^{}`$, $`W^{}`$ are unitary matrices acting in flavour space and where for notation simplicity we have dropped here the superscript 0 in the fermion fields. Invariance of the mass terms under the above CP transformation, requires that the following relations have to be satisfied:

$`W^TMW^{}`$ $`=`$ $`M^{}`$ (9)
$`U^{}mW^{}`$ $`=`$ $`m^{}`$ (10)
$`U^{}m_lV^{}`$ $`=`$ $`m_{l}^{}{}_{}{}^{}`$ (11)
From Eqs. (10), (9), one obtains:

$`W^{}hW^{}`$ $`=`$ $`h^{}`$
$`W^{}HW^{}`$ $`=`$ $`H^{}`$ (12)
with $`h=m^{}m`$, $`H=M^{}M`$. It can be then readily derived, from Eqs. (9) and (12), that CP invariance requires:

$`I_1\mathrm{ImTr}[hHM^{}h^{}M]=0`$
$`I_2\mathrm{ImTr}[hH^2M^{}h^{}M]=0`$
$`I_3\mathrm{ImTr}[hH^2M^{}h^{}MH]=0`$ (13)
By construction, these WB invariants are only sensitive to the CP violating phases which appear in leptogenesis. This is due to the fact that m always appears in the combination $`m^{}m`$. WB invariant conditions are particularly useful because they can be evaluated and analysed in any conveniently chosen WB (see Ref.  for further discussion of these conditions). Since there are six independent CP violating phases, one may wonder whether one can construct other three independent WB invariants, apart from $`I_i`$, which would describe CP violation in the leptonic sector. This is indeed possible, a simple choice are the WB invariants $`\overline{I}_i(i=1,2,3)`$, obtained from $`I_i`$, through the substitution of $`h`$ by $`\overline{h}=m^{}h_lm`$, where $`h_l=m_lm_{l}^{}{}_{}{}^{}`$. For example one has:

$$\overline{I}_1=\mathrm{ImTr}(m^{}h_lmHM^{}m^Th_{l}^{}{}_{}{}^{}m^{}M)$$
(14)
and similarly for $`\overline{I_2},\overline{I_3}`$. As it was the case for $`I_i`$, CP invariance requires that $`\overline{I_i}=0`$.

## 5 CP violating phases relevant at low energies

The neutrino mass matrix $``$ is diagonalized by the transformation:

$$V^T^{}V=𝒟$$
(15)
where $`𝒟=\mathrm{diag}.(m_{\nu _1},m_{\nu _2},m_{\nu _3},M_{\nu _1},M_{\nu _2},M_{\nu _3})`$, with $`m_{\nu _i}`$ and $`M_{\nu _i}`$ denoting the physical masses of the light and heavy Majorana neutrinos, respectively. It is convenient to write $`V`$ and $`𝒟`$ in the following form:

$`V=\left(\begin{array}{cc}K& R\\ S& T\end{array}\right);𝒟=\left(\begin{array}{cc}d& 0\\ 0& D\end{array}\right).`$ (20)
From Eq. (15) one obtains to an excellent approximation:

$`S^{}=K^{}mM^1`$ (21)
$`K^{}m{\displaystyle \frac{1}{M}}m^TK^{}=d`$ (22)
Eq.(22) is the usual seesaw formula. In this approximation K is a unitary matrix corresponding to the three-by-three Maki-Nakagawa-Sakata matrix . The neutrino weak-eigenstates are related to the mass eigenstates by:

$$\nu _{i}^{0}{}_{L}{}^{}=V_{i\alpha }\nu _{\alpha }^{}{}_{L}{}^{}=(K,R)\left(\begin{array}{c}\nu _{i}^{}{}_{L}{}^{}\\ N_{i}^{}{}_{L}{}^{}\end{array}\right)\left(\begin{array}{c}i=1,2,3\\ \alpha =1,2,\mathrm{}6\end{array}\right)$$
(23)
and thus the leptonic charged current interactions are given by:

$$\frac{g}{\sqrt{2}}\left(\overline{l_{iL}}\gamma _\mu K_{ij}\nu _{j}^{}{}_{L}{}^{}+\overline{l_{iL}}\gamma _\mu R_{ij}N_{j}^{}{}_{L}{}^{}\right)W^\mu +h.c.$$
(24)
From Eqs.(23), (24) it follows that $`K`$ and $`R`$ give the charged current couplings of charged leptons to the light neutrinos $`\nu _j`$ and to the heavy neutrinos $`N_j`$, respectively. In this approximation, with $`K`$ a unitary matrix, it is clear that we can rotate away three phases on the left by a redefinition of the physical charged leptonic fields so that $`K`$ is left with three physical CP violating phases, one of Dirac type, $`\delta `$, and two of Majorana type, which have an interesting geometrical interpretation in terms of unitarity triangles . These are the three CP violating phases relevant at low energies. On the other hand from Eq.(15), taking into account the zero entry in $``$, one derives the following exact relation:

$$R=mT^{}D^1$$
(25)
In the WB where the right-handed Majorana neutrino mass is diagonal it follows to an excellent approximation that:

$$R=mD^1\mathrm{or}\mathrm{else}R_{ij}D_j=m_{ij}$$
(26)
leading to:

$$A^j=\frac{g^2}{M_{W}^{}{}_{}{}^{2}}\underset{kj}{}\left[(M_k)^2\mathrm{Im}\left((R^{}R)_{jk}(R^{}R)_{jk}\right)\frac{1}{16\pi }\left(I(x_k)+\frac{\sqrt{x_k}}{1x_k}\right)\right]\frac{1}{(R^{}R)_{jj}}.$$
(27)
From the first equality in Eq.(26) and Eq.(5) we see, once again, that only the phases $`\sigma `$, $`\beta _1`$ and $`\beta _2`$ are relevant for leptogenesis. Furthermore the first equality in Eq.(26) implies that the two CP violating phases $`\beta _1`$ and $`\beta _2`$ in m (see Eq.(5)) appear in Eq.(24) as Majorana type phases since $`P_\beta `$ commutes with $`D^1`$ and, as a result, these phases can be shifted to the physical heavy neutrino masses.

## 6 Relating CP violation in leptogenesis with CP violation at low energies

In this section we address the question of whether it is possible to infer about the size of CP violation at low energies from the size and sign of the observed BAU. For definiteness, let us consider the parametrization of $`m`$ given before, where the six phases are $`\rho `$, $`\alpha _1`$, $`\alpha _2`$, $`\sigma `$, $`\beta _1`$, $`\beta _2`$. We have already seen that leptogenesis is controlled by the phases $`\sigma `$, $`\beta _1`$, and $`\beta _2`$. On the other hand the phases relevant at low energies are those appearing in $`K`$ and resulting from the diagonalization of the effective left-handed neutrino mass matrix given by:

$$m_{ef}=m\frac{1}{D}m^T$$
(28)
The strength of CP violation at low energies, observable for example through neutrino oscillations, can be obtained from the following low-energy WB invariant:

$$Tr[h_{ef},h_l]^3=6i\mathrm{\Delta }_{21}\mathrm{\Delta }_{32}\mathrm{\Delta }_{31}\mathrm{Im}\{(h_{ef})_{12}(h_{ef})_{23}(h_{ef})_{31}\}$$
(29)
where $`h_{ef}=m_{ef}m_{ef}^{}{}_{}{}^{},h_l=m_lm_{l}^{}{}_{}{}^{}`$ and $`\mathrm{\Delta }_{21}=(m_{\mu }^{}{}_{}{}^{2}m_{e}^{}{}_{}{}^{2})`$ with analogous expressions for $`\mathrm{\Delta }_{31}`$, $`\mathrm{\Delta }_{32}`$. CP violation in neutrino oscillations  is only affected by the phase $`\delta `$. The important point is that the phase $`\delta `$ is, in general, a function of all the six phases $`\rho `$, $`\alpha _1`$, $`\alpha _2`$, $`\sigma `$, $`\beta _1`$, $`\beta _2`$ as can be seen from Eq. (22). Since leptogenesis only depends on $`\sigma `$, $`\beta _1`$ and $`\beta _2`$, it is clear that, in general, one cannot directly relate the size of CP violation responsible for leptogenesis with the strength of CP violation at low energies. Yet it can be seen by computing the invariant $`Tr[h_{ef},h_l]^3`$ that in a model where the leptonic mass matrices are constrained (e. g. by flavour symmetries) so that only one of the phases (for example $`\sigma `$ ) is non-vanishing, one can establish a direct connection between the size of the observed BAU and the strength of CP violation at low energies observable, for example, in neutrino oscillations. Of special interest are specific GUT inpired scenarios such as the case of m given by:

$$m=dU_R$$
(30)
where d is diagonal and $`U_R`$ is a generic unitary matrix, in a WB where $`m_l`$ and M are both real and diagonal. This case has been discussed with all generality in Branco et al. in Ref. . Another interesting possibility are models with spontaneous CP violation at a high energy scale such as the one presented in Ref. .

## 7 Concluding remarks

This talk is based on a more detailed work  where we studied the possible sources of CP violation in the minimal seesaw model and addressed the question of whether it is possible to establish a connection between CP violation responsible for leptogenesis and CP violation observable at low energies. It was shown that, in general, such a connection does not exist but there are special interesting scenarios where it may be established.

## Acknowledgments

Contributed paper based on Ref.  The authors of Ref.  thank the CERN Theory Division for hospitality during its preparation and also T. Endoh, R. González Felipe, T. Onogi and A. Purwanto for useful discussions. The work of TM was supported by a fellowship for Japanese Scholar and Researcher abroad from the Ministry of Education, Science and Culture of Japan. The work of BMN was supported by Fundação para a Ciência e a Tecnologia (FCT) (Portugal) through fellowship SFRH/BD/995/2000; GCB, BMN and MNR received partial support during the preparation of Ref.  from FCT through Project CERN/P/FIS/40134/2000, Project POCTI/36288/FIS/2000 and Project CERN/C/FIS/40139/2000. The participation of MNR at the RTN Meeting “Across the Present Energy Frontier: Probing the Origin of Mass”, Corfu2001, where this talk was presented, was partially supported by the EC under contract HPRN-CT-2000-00148 and by the Project CERN/P/ FIS/40134/2000. Finally we specially thank the Organizers of Corfu2001 for the stimulating Meeting.