format: text

text:
# Measuring sets in infinite groups

## 1. Introduction

A new part of group theory, often called “statistical group theory”, is becoming increasingly popular since it connects group theory to other areas of science, most of all to statistics and to theoretical computer science.

A typical result in this area would say something like “a random element (or a tuple of elements) of a group $`G`$ has a property P with probability $`p`$” (see e.g. , , ). The validity of a statement like that does, of course, heavily depend on how one defines probability on groups, or, equivalently, how one measures sets in a group. This is the problem that we address in the present paper; we feel that it deserves some discussion at a general methodological level. A much more technical development of some of the ideas can be found in .

Our approach to statistical group theory is formed by needs of practical computations with infinite groups. In particular, the starting point of our study of measures on groups was the desire to identify measures which can be used in the analysis of the behaviour of genetic algorithms on infinite groups . Hence one of our main requirements for a measure is that it reflects the nature of algorithms used for generating random or pseudo-random elements of a group. In Section 2 we discuss some other natural conditions which would make a measure suitable for practical computations.

Since we focus mostly on finitely generated discrete groups, almost all measures defined in the present paper are atomic. Recall that a probabilistic measure on a countable set is atomic if every subset is measurable. Clearly, the latter condition is natural in the context of computational group theory where we are restricted to dealing with finite sets of elements. In Section 3, we suggest a simple (perhaps even naive) general approach to constructing atomic measures on countable groups associated with various length (or “complexity”) functions.

In Sections 4, 5, we look at the problem of measuring sets in infinite groups when pseudorandom elements of a group are generated by a deterministic process. This naturally leads to Kolmogorov complexity of words as a more adequate concept of the “length function” on a free group. The invariance theorems for Kolmogorov complexity provide for a uniform treatment of different ways to define computational complexity functions on groups.

Section 6 deals with the so-called short elements bias which occurs in any generator of random elements of a group $`G`$ with a given atomic probability distribution $`\mu `$. This effect is based on a simple observation that the measure $`\mu (S)`$ of an infinite set $`SG`$ is essentially defined by a few short elements from $`S`$. There are several principal approaches to this problem. The most popular one suggests to consider relative frequencies

$$\rho _k(S)=\frac{|SB_k|}{|B_k|}$$

(where $`B_k`$ is the ball of radius $`k`$ in the Cayley graph of $`G`$ with respect to a given set of generators) and their behaviour at “infinity” when $`k\mathrm{}`$. This leads to the notion of asymptotic density  of $`S`$ defined as the following limit (if it exists):

$$\rho (S)=\underset{k\mathrm{}}{lim}\frac{|SB_k|}{|B_k|}.$$

Another way to avoid the short elements bias is to replace a single measure $`\mu `$ on $`G`$ by a parametric family of distributions $`\{\mu _L\}`$ in which $`L`$ is the average length of elements of $`G`$ relative to $`\mu _L`$. In this case the asymptotic behaviour of the set $`S`$ is described by the limit

$$\mu _{\mathrm{}}(S)=\underset{L\mathrm{}}{lim}\mu _L(S).$$

We discuss asymptotic densities in the last section and refer to  for a detailed discussion of the second method.

In Section 7, we show how a specific choice of the probability distribution on a free group allows one to introduce degrees of polynomial growth “on average” for functions on groups. In particular, it is a possible way for introducing hierarchies of the average case complexity of various algorithms for infinite groups, making meaningful statements like “the algorithm works in cubic time on average”.

Section 8 discusses probability measures generated by random walks on the Cayley graph of a free group $`F_n`$. This class of measures is well suited for analysis of randomized algorithms on groups and behaves nicely with respect to taking finite factor groups.

In Section 10, we analyze some limitations of the asymptotic density as a tool for measuring sets in infinite groups. The most important one is that it is not sensitive enough, i.e., many sets of intuitively different sizes have the same asymptotic density (usually $`1`$ or $`0`$). Indeed, in , Woess proved that every normal subgroup of infinite index in a free group $`F_n`$, $`n2`$, has asymptotic density $`0`$.

Another disappointment is offered by Theorem 10.4 which states that the set of primitive elements of a free group $`F_n`$, $`n2`$, has asymptotic density $`0`$. In fact, our proof provides lower and upper bounds for the relative frequencies of the set of primitive elements of $`F_n`$, which is a result of independent interest.

One way around this problem is to consider the so-called growth rate of the relative frequency defined by

$$\gamma (S)=\underset{k\mathrm{}}{lim\; sup}\sqrt[k]{\rho _k(S)}.$$

This is a useful characteristic of growth of the set $`S`$ and it is more sensitive than the asymptotic density $`\rho (S)`$ (see Section 10.2).

On the other hand, the function $`\gamma (S)`$ is not even additive, which makes it difficult to use as a measuring tool.

It would be very interesting to check whether sets having the same asymptotic densities (see, for example, , , ) will show different sizes with respect to a more sensitive and adequate measure.

## 2. Conditions on a measure

Let $`G`$ be a group (finite or countable infinite). A probabilistic measure $`\mu `$ on $`G`$ has to satisfy the standard axioms of a probability space.

Recall that a probability space is a set $`X`$ together with a $`\sigma `$-algebra of subsets $`𝒜`$ of $`X`$ and a probability measure $`\mu :𝒜R`$ which is a real-valued function satisfying the following axioms:

* For any set $`S𝒜`$, $`\mu (S)0`$.
* $`\mu (X)=1`$.
* If $`S_i,iI`$, is a countable collection of pairwise disjoint sets from $`𝒜`$, then

$$\mu \left(\underset{iI}{}S_i\right)=\underset{iI}{}\mu (S_i).$$

Analysis of behaviour of randomized algorithms on groups requires estimation of the probability of a given element. A measure $`\mu `$ on $`X`$ is atomic if it satisfies the following condition

* $`X`$ is countable and every subset $`SX`$ is $`\mu `$-measurable.

In this paper, we shall consider mostly atomic measures on a free group $`F_n`$ of rank $`n`$ with basis $`\{x_1,\mathrm{},x_n\}`$. Note that since every coset with respect to a subgroup $`H<F_n`$ is measurable, this defines an induced measure on the factor set $`F_n/H`$; this new induced measure is also atomic.

A question that might arise (and which is usually addressed in the theory of growth of groups) is whether or not a measure should depend on a particular basis of $`F_n`$. Independence of a basis means invariance of the measure under the action of $`\mathrm{Aut}F_n`$. In the case of atomic measures, this implies that infinitely many singletons $`\{g^h\}`$, $`hF_n`$, have the same measure as $`\{g\}`$ does, which implies $`\mu (g)=0`$. Hence the only $`(\mathrm{Aut}F_n)`$-invariant atomic measure on $`F_n`$ is the singular measure concentrated at the origin $`1`$, and atomic measures necessarily depend on the choice of a basis in $`F_n`$.

Finally, we record several informal conditions on a measure which will guide us in evaluating behaviour of various measures:

* a measure should be natural, i.e., it should meet our expectations of what the sizes of various sets in a group are.
* a measure should be sensitive, i.e., sets that (intuitively) seem to be of different sizes, should have different measures.
* $`\mu (S)`$ (or, at least, rather tight bounds for $`\mu (S)`$) should be easily computable for “natural” sets $`SF_n`$.
* a measure should admit a natural generator of random elements in the group.

In the rest of the paper we consider various approaches to constructing measures on groups, checking them against our list of conditions (C1)–(C4).

## 3. Atomic probability measures

In this section, we discuss a general method which allows one to define atomic probabilistic measures on countable groups. Our definition of a measure is based on a notion of “complexity” of elements of $`G`$ and a probability distribution on the set of all non-negative integers $`𝒩`$. These are the initial basic objects which determine the intrinsic behaviour of the corresponding measure.

Depending on a problem at hand, one can use different types of complexities, for example, it can be a descriptive complexity, a computational complexity, the minimal length of the word representing an element with respect to a given generating set, or the length of the normal form of an element. In general, a complexity function (or a complexity) on a group $`G`$ is an arbitrary non-negative integral function $`c:G𝒩`$ such that for every $`n𝒩`$ the preimage $`c^1(n)`$ is a finite subset of $`G`$. Note that a group $`G`$ with a complexity function is countable. At the end of the section we discuss more general complexity functions which allow elements of $`G`$ to have infinite complexity and elements with real value complexities (in this case the group $`G`$ can be uncountable).

The most important example of a complexity function is the length function on a group. Let $`G`$ be a finitely generated group with a given finite set of generators $`SG`$. For an element $`gG`$ by $`l_S(g)`$ we denote the minimal non-negative integer $`n`$ such that $`g=y_1\mathrm{}y_n`$ for some $`y_iSS^1`$. If $`H`$ is a subgroup of $`G`$ then the restriction of $`l_S`$ on $`H`$ gives rise to a new complexity function on $`H`$, which might not be a length function on $`H`$.

In Section 4 we consider another important type of complexity functions on $`G`$, so-called Kolmogorov complexity functions.

For a given complexity function $`c`$ on $`G`$ and a discrete probability distribution on non-negative integers $`𝒩`$, given by a density function $`d:𝒩R`$, we are going to construct an atomic measure $`\mu _{c,d}`$ on $`G`$.

Recall that, for an atomic measure on a countable set $`X`$, the value of $`\mu `$ on an arbitrary subset $`SX`$ is defined uniquely by the formula

(3.1)
$$\mu (S)=\underset{wS}{}\mu (w).$$

This shows that an atomic measure $`\mu `$ is completely determined by its values on singletons $`\{w\},wX.`$ In other words, to define $`\mu `$ it suffices to define a function $`p:XR`$ (and put $`\mu (w)=p(w)`$), which is called a probability mass function or a density function on $`X`$, such that:

$$p(w)0\text{ for all }xX,$$

$$\underset{wX}{}p(w)=1.$$

Now we put forward one more condition on the measure $`\mu `$ which ties $`\mu `$ to a complexity function $`c:G𝒩`$:

* for any $`u,vG`$, $`c(u)=c(v)`$ implies $`\mu (u)=\mu (v)`$.

We call a measure $`\mu `$ on $`G`$ $`c`$-invariant if $`\mu `$ satisfies (C5), i.e., elements of the same $`c`$-complexity have the same measure.

The following result describes $`c`$-invariant measures on $`G`$. For $`k𝒩`$ define the $`k`$-sphere $`C_k`$ with respect to a complexity $`c`$ as follows:

$$C_k=\{wGc(w)=k\}.$$

Similarly, by $`B_n`$ we denote the disc or the ball of radius $`n`$ with respect to $`c`$:

$$B_n=\{wGc(w)n\}.$$

###### Lemma 3.1.

Let $`\mu `$ be an atomic measure on $`G`$ and $`c`$ a complexity function on $`G`$. Then:

1. If $`\mu `$ is $`c`$-invariant, then the function $`d_\mu :𝒩R`$ defined by

$$d_\mu :k\mu (C_k)$$

is a probability measure on $`𝒩`$;
2. if $`d:𝒩R`$ is a probability measure on $`𝒩`$, then the function $`p_{c,d}:G`$ defined by

$$p_{c,d}(w)=\frac{d(c(w))}{C_n}$$

is a probability function which gives rise to an atomic $`c`$-invariant measure on $`G`$.

Proof is obvious. $`\mathrm{}`$

###### Remark 3.2.

If $`c(w)`$ is the length of an element $`wG`$ with respect to a given finite set of generators of $`G`$, then $`c`$-invariant measures play an important role in asymptotic group theory. We will call such measures homogeneous.

Since $`d(k)0`$ as $`k\mathrm{}`$, the following elementary but fundamental property of $`\mu _{c,d}`$ holds.

> More complex (with respect to a given complexity $`c`$) elements of a set $`SX`$ contribute less to $`\mu _{c,d}(S).`$

This discussion shows that in defining the probability measures $`\mu _{c,d}`$ on $`G`$, everything boils down to the problem of choosing a complexity function $`c:G𝒩`$ and a moderating distribution $`d:𝒩`$. This choice might depend on a particular problem one would like to address. To that end, it seems reasonable to:

* use complexity functions on $`G`$ which reflect intrinsic features of the problem at hand;
* use probability distributions on $`𝒩`$ which reflect the nature of the process which generates (pseudo)random elements of the group, or which allow to study the statistical properties of the group in a meaningful and computationally feasible way.

We discuss possible complexity functions on groups in the next section. Here are some well-established parametric families of density functions on $`𝒩`$ that we have considered in this framework:

(i) The Poisson density:

$$d_\lambda (k)=e^\lambda \frac{\lambda ^k}{k!}$$

(ii) The exponential density:

$$d_\lambda (k)=(1e^\lambda )e^{\lambda k}$$

(iii) The standard normal (Gauss) density:

$$d_{a,\sigma }(k)=be^{\frac{(ka)^2}{\sigma }}$$

(iv) The Cauchy density:

$$d_\lambda (k)=b\frac{1}{(k\lambda )^2+1}$$

(v) The Dirac density:

$$d_m(k)=\{\begin{array}{cc}1\hfill & \text{if }k=m\hfill \\ 0\hfill & \text{if }km\hfill \end{array}$$

The following density function depends on a given complexity function $`c`$ on $`G`$: (vi) The finite disc uniform density:

$$d_m(k)=\{\begin{array}{cc}\frac{|C_k|}{|B_m|}\hfill & \text{if }km\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$$

For example, the Cauchy density functions are very convenient for defining degrees of polynomial growth “on average”, while the exponential density functions are suitable for defining degrees of exponential growth “on average” (see Section 7).

On the other hand, different distributions arise from different random generators of elements in a group. For example, Dirac densities correspond to the uniform random generators on the spheres $`C_n`$; finite disc densities arise from uniform random generators on the discs $`B_n`$. Measures on the free group $`F_n`$ associated with the exponential moderating distribution on $`𝒩`$ have especially nice properties and are studied in some detail in .

###### Remark 3.3.

Sometimes we allow for some elements in the set $`X`$ to have infinite complexity $`\mathrm{}`$. In this case we consider complexity functions of the type $`c:XN\{\mathrm{}\}`$ such that $`c^1(n)`$ is a finite subset of $`X`$ for every integer $`n`$ (so that we may have infinitely many elements in $`X`$ with complexity $`\mathrm{}`$). Following our requirement that more complex elements contribute less to the measure, we define the probability density function $`p`$ on $`X`$ for elements with finite complexity, and for elements $`xX`$ of infinite complexity we just put $`p(x)=0`$.

## 4. Kolmogorov complexity functions

### 4.1. Kolmogorov complexity functions on free groups

In this section we discuss complexity functions on free groups. We are going to represent elements of free groups as reduced words in a given basis, so the starting point of this discussion is complexity of words.

Let $`A`$ be a finite alphabet and $`A^{}`$ the set of all finite words in $`A`$. The length $`|w|`$ of a word $`w=x_1\mathrm{}x_n,`$ $`x_iA`$, is equal to $`n`$. The length function $`l:w|w|`$ maps $`A^{}`$ into $`𝒩`$. Observe that $`l^1(n)=|A|^n`$. It follows that

* The length function $`l:A^{}𝒩`$ is a complexity function on $`A^{}`$.

This is one of the basic complexity functions that we will consider in this paper. The problem however is that some very long words in $`A^{}`$ do not look very complex. For example, the word $`a^{10^{100}}`$, where $`aA,`$ has length $`10^{100}`$, but this word is very easy to describe. This leads to the notion of Kolmogorov complexity, or descriptive complexity, or sometimes it is called algorithmic complexity. We refer to ,  for detailed treatment of Kolmogorov complexity.

Intuitively, Kolmogorov complexity of a word $`wA^{}`$ is the minimum possible size (length) of a description of $`w`$ with respect to a given formal general procedure. For example, one may think of the descriptive complexity of $`w`$ as of the the minimum possible size of a program, in a given programming language, which produces $`w`$ after finitely many steps. In this case, the word $`a^{10^{100}}`$ above will have complexity much less than $`10^{100}`$.

Now we give a formal definition of Kolmogorov complexity.

It is sufficient to consider programs of a very particular type, say, Turing machines. Denote by $`B=\{0,1\}`$ the standard binary alphabet and by $`B^{}`$ the set of all finite binary strings. Every Turing machine $`M`$ determines a partial (perhaps empty) recursive function $`f_M:B^{}A^{}`$. The function $`f_M`$ is defined on $`xB^{}`$ if and only if the machine $`M`$ starts on the tape with a word $`x`$, halts in finitely many steps, and a word $`wA^{}`$ is written on the tape. In this event, $`f_M(x)=w`$. Denote by $`s_M(x)`$ and $`t_M(x)`$, respectively, the tape space and the number of steps needed for $`M`$ to write $`w`$ and halt.

The Kolmogorov complexity of a word $`wA^{}`$ with respect to a given machine $`M`$ is defined as follows:

$$K_M(w)=\{\begin{array}{cc}\mathrm{min}\{|x|xB^{}\&f_M(x)=w\}\hfill & \text{if such }x\text{ exists}\hfill \\ \mathrm{}\hfill & \text{otherwise}\hfill \end{array}$$

Similarly, one can define time bounded and space bounded  Kolmogorov complexities of a word $`wA^{}`$. Namely, for a Turing machine $`M`$ and a function

$$\beta :𝒩𝒩$$

(a bound) define the space bounded and time bounded Kolmogorov complexities $`KS_M(x,\beta )`$ and $`KT_M(x,\beta )`$ (with respect to the bound $`\beta `$) as follows:

$$KS_M(w,\beta )=\{\begin{array}{cc}\mathrm{min}\{|x|xB^{}\&f_i(x)=w\&s_M(x)\beta (|x|)\}\hfill & \text{if such }x\text{ exists}\hfill \\ \mathrm{}\hfill & \text{otherwise}\hfill \end{array}$$

$$KT_M(w,\beta )=\{\begin{array}{cc}\mathrm{min}\{|x|xB^{}\&f_i(x)=w\&t_M(x)\beta (|x|)\}\hfill & \text{if such }x\text{ exists}\hfill \\ \mathrm{}\hfill & \text{otherwise}\hfill \end{array}$$

These definitions depend on a given Turing machine $`M`$. It turns out that a universal Turing machine $`M`$ provides an optimal notion of Kolmogorov complexity. Namely, the following invariance theorem holds.

Invariance Theorem I ( , ). There exists a Turing machine $`U`$ such that for any Turing machine $`M`$ and for any word $`wA^{}`$ the following inequality holds:

$$K_U(w)K_M(w)+C_M,$$

where $`C_M`$ is a constant which does not depend on $`w`$.

Similar results hold for space bounded and time bounded Kolmogorov complexities.

Invariance Theorem II . There exists a Turing machine $`U`$ such that for any Turing machine $`M`$, for any bound $`\beta :𝒩𝒩`$, and for any word $`wA^{}`$ the following inequalities hold:

$$KS_U(w,C_M\beta )K_M(w,\beta )+C_M,$$

$$KT_U(w,C_M\beta \mathrm{log}(\beta )K_M(w,\beta )+C_M,$$

where $`C_M`$ is a constant which does not depend on $`w`$.

The theorems above allow one to consider $`K_U(w)`$ as the Kolmogorov complexity $`K(w)`$ of a word $`wA^{}`$, were $`U`$ is an arbitrary fixed optimal machine.

We will use these different types of Kolmogorov complexities in constructing measures on a free group. But first, two remarks are in order (a bad news and a good news).

###### Remark 4.1.

The function $`wK(w)`$ is not recursive. Thus, we cannot effectively compute the Kolmogorov complexity of a given word. However, it turns out that we can estimate $`K(w)`$ by the length of $`w.`$ This shows that the length $`|w|`$ as a complexity of $`w`$ is back in the game.

###### Remark 4.2.

There exists a constant $`C`$ such that for any word $`wA^{}`$

$$K(w)|w|\mathrm{log}_2|A|+C.$$

Actually, there are better estimates which will be discussed elsewhere.

Now we define Kolmogorov complexity of an element of a free group $`F=F(X)`$ with a basis $`X`$. Let $`X^1=\{x^1xX\}`$ and $`A=XX^1.`$ For an element $`fF`$ denote by $`w_f`$ the unique reduced word in the alphabet $`A`$ which represents $`f`$.

Now the Kolmogorov complexity $`K(f,X)`$ of $`f`$, with respect to the basis $`X`$, is defined as

$$K(f)=K(w_f).$$

It is easy to see that for different bases $`X`$ and $`Y`$ of $`F`$, the corresponding Kolmogorov complexities are equivalent up to some additive constants, i.e., there are positive integers $`C_1`$ and $`C_2`$ such that for any $`fF`$,

$$K(f,Y)C_1K(f,X)K(f,Y)+C_2.$$

This allows us to fix an arbitrary basis of the free group $`F`$ and consider all the Kolmogorov complexities with respect to this particular basis.

## 5. Kolmogorov complexity functions on finitely generated groups

Let $`G`$ be a group generated by a finite set $`X`$. There are several ways of introducing Kolmogorov complexity on $`G`$.

Method I. Let $`F(X)`$ be a free group on $`X`$ and let $`\eta :F(X)G`$ be the canonical epimorphism. For an element $`gG`$ define the Kolmogorov complexity $`K(g,X)`$ of $`g`$ with respect to $`X`$ as follows

$$K(g,X)=\mathrm{min}\{K(w,X)\eta (w)=g\},$$

i.e., the Kolmogorov complexity of $`gG`$ is the minimum of Kolmogorov complexities of representatives of $`g`$ with respect to $`X`$.

As we have already seen, $`K(g,X)`$ can be estimated from above by the geodesic length of $`g`$ in the Cayley graph of $`G`$ with respect to the set $`X`$ of generators. It is extremely difficult to deal with this type of complexity if the set of such geodesics is itself very complex. In this event, it might be useful to consider some special normal forms of elements. For example, this is the case for braid groups with respect to the set of Artin generators.

Method II. Suppose the group $`G`$ has a set of normal forms $`V`$, i.e., there exists a subset $`VF`$ such that $`\eta _V`$ is one-to-one. Then one can define Kolmogorov complexity of $`gG`$ with respect to $`V`$ as

$$K(g,V)=K(\eta ^1|_V(g)).$$

The following method provides an average Kolmogorov complexity with respect to a given measure on $`F`$.

Method III. Let $`\eta :FG`$ be as above. Let $`d:𝒩R`$ be a probability on $`𝒩`$ and $`c:F𝒩`$ a Kolmogorov complexity function on $`F`$. As we have discussed above, there exists a probability measure $`\mu =\mu _{c,d}`$ on the group $`F`$. Define an average Kolmogorov complexity of $`gG`$ with respect to $`d`$, $`c`$, and $`X`$ as follows:

$$KA(g,d,c,X)=\frac{_{w\eta ^1(g)}c(w)\mu _{c,d}(w)}{_{w\eta ^1(g)}\mu _{c,d}(w)}.$$

## 6. Short elements bias and behaviour at infinity

In this section we discuss how to deal with short elements bias in an infinite group.

Let $`G`$ be a finitely generated group with a finite set $`X`$ of generators. For simplicity we will discuss only measures corresponding to the length function $`l_X`$ on $`G`$, but similar arguments can be applied for other complexity functions as well. Let

$$C_n=\{gGl_X(g)=n\},B_n=\{gGl_X(g)n\}$$

Let $`\mu `$ be an atomic function on $`G`$. Since $`\mu (C_k)=1`$, we have $`\mu (C_k)0`$ as $`k\mathrm{}`$. Therefore elements of bigger length in a set $`SG`$ contribute less to $`\mu (S)`$, i.e., we witness the short elements bias. On one hand, this meets our intuitive expectations because, technically, random elements of a very big length are inaccessible to us, e.g., no computer can generate for us a random element of length $`>10^{100}`$. On the other hand, it may happen that only a few short elements essentially define the measure of an infinite set.

There are several approaches to deal with the short elements bias.

Method I.

In practical computations with groups, when we wish to evaluate performance of a given algorithm $`𝒜`$, a typical solution to this problem is the following. Choose a sufficiently big random positive integer $`n`$ (or several of them), generate (pseudo) randomly and uniformly enough elements of length $`n`$, and run your algorithm on the produced inputs. The choice of $`n`$ usually depends on the computer resources and the hardness of the algorithm. Mathematically this can be modelled by the probability distribution $`\mu _{l_X,d_n}`$ with Dirac density $`d_n`$. The only problem is the choice of $`n`$. Theoretically, to avoid the bias toward short elements, one has to take the limit when $`n\mathrm{}`$. More precisely, let $`R`$ be a subset of $`G`$. Denote by $`\rho _n(R)`$ the measure of $`R`$ with respect to Dirac density concentrating at $`n`$:

$$\rho _n^{(s)}(R)=\frac{|RC_n|}{|C_n|}.$$

Then the asymptotic behaviour of the set $`R`$ (with respect to Dirac densities) can be characterized by the following limit (if it exists):

$$\rho ^{(s)}(R)=\underset{n\mathrm{}}{lim}\rho _n^{(s)}(R)$$

This limit is called the shperical asymptotic density of the set $`R`$.

Similarly, if we measure $`R`$ with respect to the disc uniform density function (with respect to the complexity function $`l_X`$):

$$\rho _n^{(d)}(R)=\frac{|RB_n|}{|B_n|},$$

and then take the limit (if it exists)

$$\rho ^{(d)}(R)=\underset{n\mathrm{}}{lim}\rho _n^{(d)}(R)$$

then we get the disc asymptotic density of the set $`R`$.

In Section 10 we discuss asymptotic densities in detail, here it is worthwhile to mention only that these characteristics are not sensitive enough to distinguish various subsets of groups. For example, all subgroups of infinite index have the same asymptotic density (disc or spherical) equal to $`0`$.

Method II.

Let $`\mu `$ be a probability distribution on $`G`$. Then the mean length $`L_{\mu ,X}`$ of elements of $`G`$ with respect to $`\mu `$ and the set $`X`$ of generators is the expected value of the length function $`l_X`$:

$$L_{\mu ,X}=\underset{gG}{}l_X(g)\mu (g).$$

For example, if $`G=F(X)`$ and a measure $`\mu _\lambda =\mu _{l_X,d_\lambda }`$ is given on $`F(X)`$ by the exponential density:

$$d_\lambda (k)=(1e^\lambda )e^{\lambda k}$$

then the mean length $`L_\lambda `$ of words in $`F`$ distributed according to $`\mu _\lambda `$ is equal to

$$L_\lambda =\underset{wF}{}|w|\mu (w)=(1e^\lambda )\underset{k=1}{\overset{\mathrm{}}{}}k(e^\lambda )^k=$$

$$=\frac{(1e^\lambda )}{e^\lambda }\underset{k=1}{\overset{\mathrm{}}{}}k(e^\lambda )^{k1}=\frac{1}{(e^\lambda 1)e^\lambda }.$$

Hence $`L_\lambda \mathrm{}`$ when $`\lambda 0`$. Thus, we have

> a family of probabilistic distributions $`\{\mu _\lambda \}_\lambda `$ with parameter $`\lambda `$ such that the mean length $`L_\lambda `$ tends to $`\mathrm{}`$ when the parameter $`\lambda `$ approaches $`0`$.

Similar results hold for all other distributions introduced in Section 3 (after renormalizing the parameters).

Now one can measure the behaviour of $`R`$ at infinity by the following limit (if it exists)

$$\mu _{\mathrm{}}(R)=\underset{\lambda 0}{lim}\mu _\lambda (R).$$

A study of limits of this type was initiated in .

Note that if $`\{\mu _k\}_k`$ is the Dirac parametric family of distributions, then

$$\mu _{\mathrm{}}(R)=\rho ^{(s)}(R),$$

and if $`\{\mu _k\}_k`$ is the parametric family of disc uniform distributions, then

$$\mu _{\mathrm{}}(R)=\rho ^{(d)}(R).$$

## 7. Degrees of polynomial growth “on average”

Let $`c:F_n`$ be a complexity function and $`\mu `$ the measure moderated by the Cauchy distribution

$$d(k)=\frac{6}{\pi ^2}\frac{1}{k^2}.$$

The advantage of this distribution is that it allows to measure degrees of polynomial growth of functions on $`F_n`$ “on average” in the following sense.

Let $`f:F_n`$ be a non-negative real valued function. We say that $`f`$ has polynomial growth of degree $`\alpha 0`$ if $`\alpha `$ is the greatest lower bound of the set of real positive numbers $`\beta `$ such that the mean value of $`\frac{f(w)}{c(w)^{\beta 1}}`$ is finite, that is,

(7.1)
$$\alpha =inf\left\{\beta \right|\underset{wF_n}{}\frac{f(w)}{c(w)^{\beta 1}}\mu _{c,d}(w)\text{ converges}\}.$$

It follows immediately from the construction of our measure that the function $`c(w)^m`$ has growth of degree $`m`$. (Just recall that the series $`\frac{1}{n^{1+ϵ}}`$ converges for all $`ϵ>0`$, while the harmonic series $`\frac{1}{n}`$ diverges.)

In particular, if $`f(x)`$ is the running time of some algorithm with input $`x`$, this definition allows us to make meaningful statements like “the algorithm works in cubic time on average”.

Now we are going to generalize this situation and try to find sufficient conditions to define the degrees of growth of functions on an arbitrary infinite factor group of $`F_n`$.

Let $`G=F_n/R`$ be an infinite factor group of the free group $`F_n`$ and $`\eta :F_nG`$ the natural homomorphism. We shall list some natural conditions for the complexity function $`c`$ on $`F_n`$ and the moderating probability distribution $`d`$ which allow us to define degrees of the average growth of functions on $`G`$.

* (Existence of a complexity function on $`G`$.) The mean complexity

$$\overline{c}(\overline{g})=\frac{_{w\overline{g}}c(w)\mu _{c,d}(w)}{_{w\overline{g}}\mu _{c,d}(w)}$$

is finite for every $`\overline{g}G`$.

* (Existence of degrees.) There exists a positive number $`\tau `$ such that the series

$$\underset{\overline{g}G}{}\overline{c}(\overline{g})^a\overline{\mu }(\overline{g})$$

converges for $`a<\tau `$ and diverges for $`a>\tau `$; $`\overline{\mu }`$ here is the measure on $`G`$ induced by the measure $`\mu _{c,d}`$ on $`F_n`$.

If these conditions are satisfied, we can define the degree of growth of an arbitrary nonnegative real valued function $`f(\overline{g})`$ on $`G`$ as

(7.2)
$$(\text{degree of growth of }f)=inf\left\{\beta \right|\underset{\overline{g}G}{}\frac{f(\overline{g})}{\overline{c}(\overline{g})^{\beta \tau }}\overline{\mu }(\overline{g})\text{converges}\}.$$

Now we at least have the (easy to check) property that the degree of growth of the function $`\overline{c}(\overline{g})^m`$ is $`m`$.

Note that not every moderating probability distribution $`d`$ on $`\{0\}`$ is suitable for defining degrees of polynomial growth. For example, if we take in the definition of the degrees of growth on the free group $`F_n`$, the exponential distribution

$$d(k)=(1e^\lambda )e^{\lambda k},$$

we note that the series

$$\underset{xF_n}{}c(x)^a\mu _{c,d}(x)$$

converges for all $`a`$.

###### Question 7.1.

Can one find a moderating probability distribution $`d`$ such that the conditions D1 and D2 are satisfied for every factor group $`G=F_n/R`$ of infinite index and the measure $`\overline{\mu }`$ on $`G`$ induced from $`\mu _{c,d}`$?

The Cauchy distribution $`d(k)=\frac{6}{\pi ^2}\frac{1}{k^2}`$ is still on the list of candidates for the affirmative answer.

We need to warn that the degree of growth of a function $`f`$ on $`G`$ is not necessarily equal to the degree of growth of its lift $`f\eta :F_n`$. It might happen that, for certain problems, it is much more convenient to work in a free group than in its factor group $`G`$ and evaluate the degrees of growth of the lifted function $`f\eta `$ instead of those of $`f`$. Therefore general results concerning relations between degrees of growth on $`F_n`$ and $`G=F_n/R`$ would be rather interesting.

## 8. Measures generated by random walks

### 8.1. Random walks

An interesting and, in some cases, easier to analyze class of measures is related to random walks on Cayley graphs of groups. From an algorithmic point of view, the most natural way to produce a random element in a finitely generated group is to first make a random word on the generators, and then apply relations. This is, in disguise, a random walk on the Cayley graph of a given group. This becomes especially relevant when hardware random numbers generators are used to produce random words.

Let us look at this basic procedure in more detail.

Let $`F_n`$ be a free group on free generators $`x_1,\mathrm{},x_n`$. We can associate with it a free monoid $`M_n`$ with the generators $`x_1,X_1,\mathrm{},x_n,X_n`$ and the natural homomorphism $`\pi :M_nF_n`$ which sends $`x_i`$ to $`x_i`$ and $`X_i`$ to $`x_i^1`$. A random walk of length $`l`$ on the Cayley tree of $`F_k`$ which starts at the identity $`1`$ is naturally described by a word of length $`l`$ in $`M_n`$.

In essence, we take $`M_n`$, not $`F_n`$, as the ambient algebraic structure, and introduce measures and complexity functions on $`M_n`$ rather than on $`F_n`$. There is a compelling evidence that, in at least some problems, it might be convenient to work in the ambient free monoid $`M_n`$. For example, it appears that physicists prefer to use the random walk approach in their study of statistics of braids, knots and heaps, the latter being closely related to locally free groups

$$_n=f_1,\mathrm{},f_n[f_i,f_j]=1\text{ for }|ij|>1$$

(see e.g. ). In any case, the physical process of the accumulation of soot (in the 2-dimensional case) is most naturally modeled by random walks on the monoid of positive words in $`_n`$.

Let $`d:\{0\}`$ be a moderating probability distribution. Following the analogy with our constructions for a free group, we introduce an atomic probability measure $`\stackrel{~}{\mu }`$ on $`M_n`$ by assigning equal probabilities to words of equal complexity and the total measure $`d(k)`$ to the set of words of complexity $`k`$. This can be interpreted as running random walks on $`F_n`$ of random complexities $`k`$ distributed with the probability density $`d(k)`$. The probability for a random walk to stop at the element $`xF_k`$ defines a measure $`\mu (x)`$ on $`F_k`$. Obviously,

$$\mu (x)=\underset{\pi (w)=x}{}\stackrel{~}{\mu }(w).$$

### 8.2. How is this new measure related to Kolmogorov complexity measures?

The measure that we have just defined should have properties very close to Kolmogorov complexity measures described in Section 4. The word $`x=\pi (w)`$ is obtained from a word $`w`$ by cancelling all adjacent pairs of elements of the form $`x_iX_i`$, which amounts to running a certain Turing machine on the input word $`w`$. Therefore, in view of the previous discussion, the Kolmogorov complexity $`c(x)`$ of $`x`$ differs from the Kolmogorov complexity $`c(w)`$ of $`w`$ by at most an additive constant:

$$c(x)c(w)+C.$$

Since for most words of a fixed big length $`l`$, Kolmogorov complexity is close to the length of the word, we should expect roughly the same asymptotic behaviour from a random walk measure as we do from a measure associated with Kolmogorov complexity.

### 8.3. Comparing the length of a random walk with the geodesic length

In a simple case, where the complexity function on $`M_n`$ is just the usual length function $`l(w)`$, we can similarly compare its behaviour with the behaviour of the geodesic length $`l=l_{\mathrm{geod}}(x)`$ of the end point $`x=\pi (w)`$ of the walk on the Cayley tree $`\mathrm{\Gamma }(F_n)`$ of $`F_n`$, described by the word $`w`$.

It is easy to see that the function $`xl_{\mathrm{geod}}(x)`$ maps a random walk on $`\mathrm{\Gamma }(F_n)`$ to a non-symmetric random walk $`𝒲_+`$ on the set $`\{0\}`$ of nonnegative integers with reflection at $`0`$. In this new walk, we make steps of length $`1`$; we move from the point $`l=0`$ to the right with probability $`1`$, and, from any other point $`l0`$, we move to the right with the probability $`p=\frac{2n1}{2n}`$ and to the left with the probability $`q=\frac{1}{2n}`$. Obviously, the mean value of $`l`$ is at least the mean value of $`l`$ for a random walk $`𝒲`$ on $``$ without reflection at $`0`$; in this walk we start at $`0`$ and move by $`1`$ to the right with the probability $`p`$ and by $`1`$ to the left with the probability $`q`$. In $`𝒲`$, we make $`m`$ moves to the right with the probability $`\left(\genfrac{}{}{0pt}{}{k}{m}\right)p^mq^{km}`$ and end up at the point $`l^{}=m(km)=2mk`$. Thus, the random variable $`l^{}`$ is a linear transformation of the random variable $`m`$ distributed according to the binomial distribution. Since the expectation $`E(m)=pk`$, we deduce that $`E(l^{})=2pkk=\frac{n1}{n}k`$.

Therefore, for the random walk $`𝒲_+`$, the expected value of $`l`$ is bounded from below by $`\frac{n1}{n}k=E(l^{})E(l)`$. The upper bound $`E(l)k`$ is obvious. Thus, the expected geodesic length $`E(l_{\mathrm{geod}}(x))`$ of an element $`xF_n`$ produced by a random walk of length $`k`$ is estimated as

$$\frac{n1}{n}kE(l_{\mathrm{geod}}(x))k.$$

## 9. Behaviour of the induced measures on finite factor groups

In this section we try to establish possible criteria to evaluate how “natural” a given measure is, i.e., how it matches our expectations of what the probability of hitting particular sets should be. In general, these expectations may, of course, vary from individual to individual, but we have some common grounds, at least, in the case of finite sets. So, our idea is to set up some tests to compare a given measure $`\mu `$ on a free group $`F=F_n`$ with the induced measures on finite quotients of $`F`$. Most people will probably agree that, for example, the probability for a randomly chosen element of $`F`$ to have even length should be about $`1/2`$. More generally, it is natural to expect that a subgroup $`H<F`$ of an index $`m`$ would have the measure (approximately) equal to $`\frac{1}{m}`$. Unfortunately, this is not the case if $`\mu (1)>0`$, indeed, if $`m>>\frac{1}{\mu (1)}`$ then $`\mu (H)\mu (1)>>\frac{1}{m}`$.

Moreover, most people working with probabilities on finite groups are likely to prefer measures which are well behaved with respect to taking “big” finite factors $`F_n/R`$, for example, measures which yield reasonable bounds for the total variance distance

(9.1)
$$\frac{1}{2}\underset{\overline{g}F_n/R}{}\left|\mu (\overline{g})\frac{1}{|F_n:R|}\right|$$

of the induced distribution from the uniform distribution on $`F_n/R`$. Again, this natural condition cannot be satisfied basically for the same reason, namely, the value of (9.1) is bounded from below by $`\frac{1}{2}|\mu (1)(1/m)|`$, where $`m=|F_n:R|`$, and does not converge to $`0`$ as $`m\mathrm{}`$.

This is a typical example of an unexcusable dependance of a measure on short elements. This is one of the many reasons to believe in the following (maybe controversial) metamathematical thesis:

There is no particular atomic measure on an infinite group which would meet our expectations of sizes of particular sets in the group

A possible practical outcome of this thesis is either to consider a whole family of parametric measures on a group instead of a fixed one, or to adjust our criteria to allow a margin of an error of approximation. The first approach was developed to some extent in , here we make an attempt to consider the second one.

One may wish to exclude anomalously big probabilities of short elements by taking the measure of an element $`gR`$ in a finite factor group $`F_n/R`$ to be the renormalized measure of the set of “large” elements in $`gR`$:

(9.2)
$$\overline{\mu }_l(gR)=\frac{\mu ((F_nB_l)gR)}{\mu (F_nB_l)},$$

where $`B_l`$ is the ball of radius $`l`$ centered at $`1`$. Anyway, it is only natural to assume that, when assessing the average case complexity of algorithmic problems of practical interest, we are working with words of sufficiently large size; the bias towards short elements can be safely ignored. A measure $`\mu `$ can be accepted as “good” if, for values of $`l`$ much smaller than $`m`$,

(9.3)
$$\frac{1}{2}\underset{\overline{g}F_n/R}{}\left|\overline{\mu }_l(\overline{g})\frac{1}{|F_n:R|}\right|<\frac{1}{e},$$

or is bounded by some other reasonable constant, or decreases exponentially with the growth of $`l`$:

(9.4)
$$\frac{1}{2}\underset{\overline{g}F_n/R}{}\left|\overline{\mu }_l(\overline{g})\frac{1}{|F_n:R|}\right|=o(e^{cl}).$$

The reader probably feels already at this point that we are leaning towards the classical concept of a random walk on a group. Taking images of “sufficiently long” elements means allowing a sufficiently long random walk on the finite group $`F_n/R`$. It is reasonable to take the mixing time of the random walk on the factor group $`F_n/R`$ with respect to the generators $`x_1R,\mathrm{},x_nR`$ for the characteristic word length $`l`$ in the criterion (9.3). Recall that the mixing time is defined as the minimum $`l_0`$ such that

(9.5)
$$P_{l_0}U=\frac{1}{2}\underset{\overline{g}F_n/R}{}\left|P_{l_0}(\overline{g})\frac{1}{|F_n:R|}\right|<\frac{1}{e},$$

where $`P_l(\overline{g})`$ is the probability for a random walk of length $`l`$ to end up at the element $`\overline{g}`$, and $`U`$ is the uniform distribution on $`F_n/R`$. From the mixing time on, a random walk distribution converges to the uniform distribution exponentially fast:

(9.6)
$$P_{kl_0}U=\frac{1}{2}\underset{\overline{g}F_n/R}{}\left|P_{kl_0}(\overline{g})\frac{1}{|F_n:R|}\right|=o(e^{ck}).$$

Therefore, we can consider an alternative criterion for good behaviour of the measure on finite factor groups:

* For every finite factor group $`G=F_n/R`$ there exists a number $`l_0`$ such that

$$\frac{1}{2}\underset{\overline{g}F_n/R}{}\left|\overline{\mu }_{kl_0}(\overline{g})\frac{1}{|F_n:R|}\right|=o(e^k).$$

Of course, the value of $`l_0`$ (“the mixing time”) is all important. One should expect from a ‘good’ measure on $`F_n`$ that it is approximately the same as the mixing time of a random walk on $`F_n/R`$. It is worth mentioning here, that, by a result by Pak , a random walk on a finite group $`G`$ with respect to a random generating set of size $`O(\mathrm{log}|G|)`$ mixes under $`O(\mathrm{log}|G|)`$ steps.

It is relatively easy to see that our criterion (C1\*) is met by a wide class of measures associated with the length function on $`F_n`$.

###### Theorem 9.1.

If the moderating distribution $`d(k)`$ satisfies a rather natural condition $`d(k)>0`$ for infinitely may values of $`k`$ then, for every finite factor group $`G=F_n/R`$, the induced measure $`\overline{\mu }_l`$ on $`G`$ satisfies the condition (C1\*).

### 9.1. Proof of Theorem 9.1

Let $`|G|=m`$. Every probability distribution on $`G`$ is a vector $`p_1,\mathrm{},p_m`$ of non-negative real numbers subject to the condition $`p_1+\mathrm{}+p_m=1`$. Thus, the set of all probability distributions on $`G`$ is the convex hull $`\mathrm{\Delta }`$ of the distributions $`E_g`$ concentrated at $`gG`$, i.e., $`E_g(h)=1`$ if $`h=g`$ and $`0`$ otherwise. We introduce on $`\mathrm{\Delta }`$ the total variance metric

$$PQ=\frac{1}{2}\underset{gG}{}|P(g)Q(g)|.$$

A step of a random walk induces an affine transformation $`\tau :^m^m`$ by the rule

$$\tau :E_g\frac{1}{2n}\underset{h\text{ adjacent to }g}{}E_h,$$

where the adjacency is considered in the Cayley graph of $`G`$.

Since all vertices of the Cayley graph of $`G`$ have the same degree, $`\tau `$ fixes the uniform distribution $`U=(1/m,\mathrm{},1/m)`$. By somewhat abusing the notation, we can move the origin of the coordinate system in $`^m`$ to the point $`U`$. It will be convenient to restrict the action of $`\tau `$ to the subspace $`^{m1}`$ spanned in $`^m`$ by the polytope $`\mathrm{\Delta }`$. Then the distance $`XU`$ becomes a norm on $`^{m1}`$ (which we denote by $`X`$; hopefully, this will not cause a confusion), and $`\tau `$ becomes a linear operator on $`^{m1}`$. Note that the norms $`\tau ^k(E_g)`$ of vertices of the convex polytope $`\tau ^k(\mathrm{\Delta })`$ are all equal. Since $`\tau `$ maps the vertices $`E_g`$ of $`\mathrm{\Delta }`$ to points of $`\mathrm{\Delta }`$, it does the same to the vertices of $`\tau ^k(\mathrm{\Delta })`$. As a result, we have the following monotonicity property:

$$\tau ^{k+1}(E_g)\tau ^k(E_g).$$

We can use again the property that $`\tau `$ maps the vertices $`E_g`$ of the convex polytope $`\mathrm{\Delta }`$ to prove that $`\tau (E_g)_E<E_g_E`$ for all $`gG`$, where $`_E`$ stands for the standard Euclidean norm on $`^{m1}`$. It follows that

$$\tau _E=\underset{X\mathrm{\Delta },X0}{\mathrm{max}}\frac{\tau (X)_E}{X_E}<1,$$

hence $`\tau ^k(X)_E0`$ as $`k\mathrm{}`$ for every distribution $`X`$. Moreover, $`\tau ^k(X)_E`$ decreases exponentially: $`\tau ^k(X)_E=o(c^k)`$. Since any two norms on a finite dimensional space are equivalent, we have

$$\frac{1}{C}X_E<X<CX_E$$

for some constant $`C`$, and it follows that $`\tau ^k(X)=o(c^k)`$.

We have, in our new notation,

$`{\displaystyle \frac{1}{2}}{\displaystyle \underset{gG}{}}\left|\overline{\mu }_l(g){\displaystyle \frac{1}{m}}\right|=\overline{\mu }_l={\displaystyle \frac{1}{_{kl}d(k)}}{\displaystyle \underset{kl}{}}d(k)\tau ^k(E_1)`$
$`={\displaystyle \frac{1}{_{kl}d(k)}}{\displaystyle \underset{kl}{}}d(k)\tau ^k(E_1){\displaystyle \frac{1}{_{kl}d(k)}}{\displaystyle \underset{kl}{}}d(k)\tau ^l(E_1)`$
$`=\tau ^l(E_1){\displaystyle \frac{_{kl}d(k)}{_{kl}d(k)}}=\tau ^l(E_1).`$
We see that the probabilistic distribution on $`G`$ produced by a random walk of random length $`l`$ converges to the uniform distribution as fast as the probability distribution after $`l`$ steps of the usual random walk does. In particular, this proves that the measure $`\overline{\mu }_l`$ on $`G`$ satisfies the condition (C1\*).

## 10. The growth function and asymptotic density

In this section, we discuss an approach to analyze the asymptotic behaviour of sets in a group via asymptotic densities introduced in Section 6.

Let $`G`$ be a group with a complexity function $`c:G𝒩`$ (for example, a group generated by a finite set $`X`$ with the length function $`l_X`$).

A pseudo-measure on $`G`$ is a real-valued nonnegative additive function defined on some subsets of $`G`$. The pseudo-measure $`\mu `$ is called atomic if $`\mu (S)`$ is defined for any finite subset $`S`$ of $`G`$. Let $`C_k`$ and $`B_k`$ be, respectively, the sphere and the ball of radius $`k`$ in $`G`$ with respect to the complexity $`c`$.

For a set $`RF`$, we define its spherical asymptotic density with respect to $`\mu `$ as the following limit (if it exists):

$$\rho _\mu ^{(s)}(R)=\underset{k\mathrm{}}{lim}\rho _k^{(s)}(R),$$

where

$$\rho _k^{(s)}(R)=\frac{\mu (RC_k)}{\mu (C_k)}.$$

Similarly, we define disc asymptotic density of $`R`$ as the limit (if it exists):

$$\rho _\mu ^{(d)}(R)=\underset{k\mathrm{}}{lim}\rho _k^{(d)}(R),$$

where

$$\rho _k^{(d)}(R)=\frac{\mu (RB_k)}{\mu (B_k)}.$$

One can also define the density functions above using $`limsup`$ rather then $`lim`$.

For example, if $`\mu `$ is the cardinality function, i.e., $`\mu (A)=|A|`$, then we obtain the standard asymptotic density functions $`\rho ^{(c)}`$ and $`\rho ^{(d)}`$ on $`G`$.

Moreover, if $`\mu `$ is $`c`$-invariant, i.e., $`\mu (u)=\mu (v)`$ provided $`c(u)=c(v)`$, then the spherical asymptotic density with respect to $`\mu `$ is equal to the standard spherical asymptotic density:

$$s\rho _\mu =s\rho .$$

###### Lemma 10.1.

For any atomic pseudo-measure $`\mu `$ on $`G`$, the asymptotic densities $`\rho ^{(c)}`$ and $`\rho ^{(d)}`$ are also atomic pseudo-measures on $`G`$.

Proof  is obvious.

###### Lemma 10.2.

Let $`\mu `$ be a pseudo-measure on $`G`$. Suppose that

$$\underset{k\mathrm{}}{lim}\mu (B_k)=\mathrm{}.$$

Then, for any subset $`RG`$, if the spherical asymptotic density $`\rho _\mu ^{(c)}(R)`$ exists, then the disc asymptotic density $`\rho _\mu ^{(d)}(R)`$ exists, too, and

$$\rho _\mu ^{(c)}(R)=\rho _\mu ^{(d)}(R).$$

Proof. Let $`x_k=\mu (RB_k)`$ and $`y_k=\mu (B_k)`$. Then $`y_k<y_{k+1}`$ and $`limy_k=\mathrm{}`$. By Stolz’s theorem

$$\underset{k\mathrm{}}{lim}\frac{x_k}{y_k}=\underset{k\mathrm{}}{lim}\frac{x_kx_{k1}}{y_ky_{k1}}.$$

Hence

$$\rho _\mu ^{(d)}(R)=\underset{k\mathrm{}}{lim}\frac{\mu (RS_k)}{\mu (S_k)}=\rho _\mu ^{(s)}(R),$$

as claimed.

In view of this result we will refer to the standard (spherical or disc) densities $`\rho `$.

Asymptotic densities provide a useful, though very coarse, tool to describe behaviour of sets at infinity. Furthermore, there are very natural subsets which are sadly unmeasurable with respect to $`\rho `$. To see this, consider the set $`E_n`$ of words of even length in a free group $`F_n`$ of rank $`n`$. Then $`\rho (E_n)`$ is easily seen to be undefined. A way around this problem (involving generalized summation methods for series) is discussed in .

Moreover, the following well-known result shows that that $`\rho `$ is not sufficiently sensitive.

###### Theorem 10.3.

(Woess ) If $`N`$ is a normal subgroup of $`F_n`$, $`n2`$, of infinite index, then $`\rho (N)=0`$.

Another disappointment is offered by the following result. As usual, we call an element $`uF_n`$ primitive if it is part of a free basis of $`F_n`$, or, equivalently, if $`\alpha (u)=x_1`$ for some $`\alpha Aut(F_n)`$.

###### Theorem 10.4.

Let $`F_n`$ be the free group of a finite rank $`n2`$. Then:

$$\rho (\mathrm{Pr}_n)=0,$$

where $`\mathrm{Pr}_n`$ is the set of all primitive elements of the group $`F_n`$. More precisely, if $`P(n,k)`$ is the number of primitive elements of length $`k`$ in $`F_n,n3`$, then for some constants $`c_1,c_2`$, one has

$$c_1(2n3)^kP(n,k)c_2(2n2)^k.$$

We see that the asymptotic density $`\rho `$ is not sensitive enough in measuring sets in $`F_n`$. It would be very interesting therefore to check whether probabilistic results of, say, , , , that are based on the asymptotic density $`\rho `$, will hold upon replacing $`\rho `$ with a more adequate measuring tool.

### 10.1. Proof of Theorem 10.4

Our proof is based on the fact that the Whitehead graph of any primitive element of length $`>2`$ has either an isolated edge or a cut vertex, i.e., a vertex that, having been removed from the graph together with all incident edges, increases the number of connected components of the graph. Recall that the Whitehead graph $`Wh(u)`$ of a word $`u`$ is obtained as follows. The vertices of this graph correspond to the elements of the free generating set $`X`$ and their inverses. If the word $`u`$ has a subword $`x_ix_j`$, then there is an edge in $`Wh(u)`$ that connects the vertex $`x_i`$ to the vertex $`x_j^1`$; if $`u`$ has a subword $`x_ix_j^1`$, then there is an edge that connects $`x_i`$ to $`x_j`$, etc. We note that usually, there is one more edge (the external edge) included in the definition of the Whitehead graph: this is the edge that connects the vertex corresponding to the last letter of $`u`$, to the vertex corresponding to the inverse of the first letter.

Assume first that the Whitehead graph of $`u`$ has a cut vertex. We are going to show that the number of elements $`u`$ of length $`k`$ with this property is no bigger than $`C(2n2)^{k1}`$, where $`C=C(n)`$ is a constant.

Let $`Wh(u)`$ be a disjoint union of two graphs, $`\mathrm{\Gamma }_1`$ and $`\mathrm{\Gamma }_2`$, complemented by a (cut) vertex $`A`$ together with all incident edges. Let $`n_11`$ and $`n_21`$ be the number of vertices in $`\mathrm{\Gamma }_1`$ and $`\mathrm{\Gamma }_2`$, respectively. Then, in particular, $`n_1+n_2=2n1`$. Let $`m=\mathrm{min}(n_1,n_2)`$.

The first letter of $`u`$ can be any of the $`2n`$ possible ones. For the following letter however we have no more than $`2nm`$ possibilities since, for example, if the first letter, call it $`x_i`$, corresponds to a vertex from $`\mathrm{\Gamma }_1`$, then the following letter, call it $`x_j`$, cannot be such that the vertex corresponding to $`x_j^1`$ belongs to $`\mathrm{\Gamma }_2`$, because otherwise, there would be an edge in $`Wh(u)`$ that connects $`\mathrm{\Gamma }_1`$ to $`\mathrm{\Gamma }_2`$ directly, not through $`A`$, i.e., $`A`$ would not be a cut vertex.

Thus, there are only $`2nn_22nm`$ possibilities for the following letter in $`u`$. The same argument applies to every letter in $`u`$, starting with the second one; therefore, the total number of possibilities (corresponding to a particular choice of $`n_1`$ and $`n_2`$) is no bigger than $`C(2nm)^{k1}`$, where $`C=C(n)`$ is a constant.

Now consider two cases:

* $`m2`$.

In this case, the number in question is bounded by $`C(2n2)^{k1}`$.

* $`m=1`$.

In this case, one of the graphs, say, $`\mathrm{\Gamma }_2`$, consists of a single vertex (call it $`x_1`$ for notational convenience) connected only to the cut vertex (call it $`x_2`$); in particular, the vertex $`x_1`$ is a terminal vertex of the graph $`Wh(u)`$, and, whenever the letter $`x_1`$ occurs in $`u`$, it is followed by $`x_2^1`$. Let $`q1`$ be the number of occurrences of $`x_1`$ in $`u`$.

Apply the automorphism $`\varphi :x_1x_1x_2,x_ix_i,i2`$, to the element $`u`$. Then $`|\varphi (u)|=|u|q<|u|`$. Now $`\varphi (u)`$ is a primitive element, too; hence the whole argument above is applicable to $`\varphi (u)`$. In particular, if, in the notation above, $`m2`$ for this element $`\varphi (u)`$, then, as we have just proved, the number of those elements is bounded by $`C(2n2)^{k1q}`$ for some $`C=C(n)`$. This number is also equal to the number of elements $`u`$ of the type we are considering now (for a particular $`q`$) because of the one-to-one correspondence between elements $`u`$ and $`\varphi (u)`$.

If $`m=1`$ for the element $`\varphi (u)`$, then we use the same trick again, until we get to a primitive element with $`m2`$. In any case, the number of primitive elements of length $`k`$, with $`m=1`$, and with $`q1`$ occurrences of $`x_1`$, is bounded by $`C(2n2)^{k1q}`$ for some $`C=C(n)`$.

Now we have to sum up for all possible values of $`q`$. Note that $`q`$ cannot be equal to $`k`$ since $`x_1^k`$ is not a primitive element; also, $`q`$ cannot be equal to $`k1`$ since in the Whitehead graph of $`x_1^{k1}x_2`$, the vertex corresponding to $`x_1`$ is not a terminal vertex. Hence, we have

$$\underset{q=1}{\overset{k2}{}}C(2n2)^{k1q}=C\frac{(2n2)^{k1}1}{2n3}C(2n2)^{k1}.$$

Finally, we have to multiply this number by the number of ways we can choose two vertices (terminal and cut) out of $`2n`$, i.e., by $`(2n1)n`$, but this does not change the type of the bound. Therefore, we get here the same bound as we got in the case $`m2`$.

Thus, summing up for all possible values of $`n_11`$ and $`n_21`$ such that $`n_1+n_2=2n1`$, we see that the total number of possibilities in (i) and (ii) is bounded by $`C(2n2)^k`$ for some $`C=C(n)`$.

Finally, we address the remaining case, where the Whitehead graph of $`u`$ has an isolated edge. In that case, some cyclic permutation of $`u`$ must be of the form $`x_i^{\pm 1}x_j^{\pm 1}u_1`$, where $`u_1`$ does not depend on $`x_i`$, $`x_j`$, and $`j`$ does not have to be different from $`i`$. The number of elements with this property is easily seen to be bounded by $`Ck(2n3)^{k1}`$ for some constant $`C=C(n)`$.

Therefore, the ratio of the number of primitive elements of length $`k`$ to the number of all elements of length $`k`$ is no more than $`C\frac{(2n2)^k}{2n(2n1)^{k1}}=C^{}(\frac{2n2}{2n1})^k`$, where $`C^{}=C^{}(n)`$ is a constant. This ratio obviously tends to 0, and, moreover, well-known properties of a geometric series now imply that the ratio of the number of primitive elements of length $`k`$ to the number of all elements of length $`k`$ tends to 0, too.

Finally, we note that the lower bound $`c_1(2n3)^kP(n,k)`$ is obvious because every element of the form $`x_1u(x_2,\mathrm{},x_{n1})`$ is primitive.

Just to complete the picture, we also mention here the bounds for the number of primitive elements of length $`k`$ in $`F_2`$:

###### Proposition 10.5.

() The number of primitive elements of length $`k`$ in the group $`F_2`$ is:

* more than $`\frac{4}{\sqrt{3}}(\sqrt{3})^k`$ if $`k`$ is odd.
* more than $`\frac{4}{3}(\sqrt{3})^k`$ if $`k`$ is even.

Informally speaking, “most” primitive elements in $`F_2`$ are conjugates of primitive elements of smaller length. This is not the case in $`F_n`$ for $`n>2`$, where “most” primitive elements are of the form $`ux_i^{\pm 1}v`$, where $`u,v`$ are arbitrary elements that do not depend on $`x_i`$.

### 10.2. The rate of convergence of the asymptotic density

Let $`S`$ be a subset of a free group $`F_n`$ of rank $`n2`$. As we have mentioned in the Introduction, the growth rate of the set $`S`$ is defined as the limit

$$\gamma (S)=\underset{k\mathrm{}}{lim\; sup}\sqrt[k]{\rho _k(S)},$$

where

$$\rho _k(S)=\frac{|SB_k|}{|B_k|}$$

are the disc relative frequencies of $`S`$. The growth rate $`\gamma (S)`$ is gauging the speed of convergence to zero of the sequence $`\rho _k(S)`$. Indeed, the standard results from calculus show that if $`\gamma (S)<1`$, then $`\rho (S)=0`$, and, moreover, the sequence $`\rho _k(S)`$ converges to $`0`$ exponentially fast.

A classical theorem by Grigorchuk  states that if $`NF_n`$ is a normal subgroup and $`F_n/N`$ is not an amenable group, then $`\gamma (N)<1`$. This gives us many easy examples of normal subgroups $`N`$ with the exponential speed of convergence of the asymptotic density. For example, this happens every time when the factor group $`F_n/N`$ contains a non-abelian free group.

It would be interesting to have a look at the other end of the spectrum and estimate the speed of convergence of the sequence $`\rho _k(N)`$ for an obviously “big” subgroup $`NF_n`$. The following result is one of the very few instances where we have concrete information:

###### Theorem 10.6.

(Sharp ) If $`n2`$, then the spherical relative frequencies

$$\rho _k^{(s)}=\frac{|[F_n,F_n]S_k|}{|S_k|}$$

of words of length $`k`$ from the derived subgroup $`[F_n,F_n]`$ of the free group $`F_n`$ asymptotically behave as

$$\rho _k^{(s)}\{\begin{array}{cc}0& \text{ if}k\text{ is odd},\hfill \\ \frac{C}{k^{n/2}}& \text{ if}k\text{ is even.}\hfill \end{array}$$


text:
# Equation of state of a multicomponent 𝑑-dimensional hard-sphere fluid [Mol. Phys. 96, 1–5 (1999)]

## Abstract

A simple recipe to derive the compressibility factor of a multicomponent mixture of $`d`$-dimensional additive hard spheres in terms of that of the one-component system is proposed. The recipe is based (i) on an exact condition that has to be satisfied in the special limit where one of the components corresponds to point particles; and (ii) on the form of the radial distribution functions at contact as obtained from the Percus-Yevick equation in the three-dimensional system. The proposal is examined for hard discs and hard spheres by comparison with well-known equations of state for these systems and with simulation data. In the special case of $`d=3`$, our extension to mixtures of the Carnahan-Starling equation of state yields a better agreement with simulation than the already accurate Boublík-Mansoori-Carnahan-Starling-Leland equation of state.

Due to their importance in liquid state theory, for years researchers have proposed empirical or semi-empirical (analytical) equations of state of various degrees of complexity for one-component hard-sphere fluids. Notable among these, is the celebrated Carnahan-Starling (CS) equation of state CS , which is not only rather simple but also accurate in comparison with computer simulation data. In the case of hard-sphere mixtures, the proposals, also empirical or semi-empirical in nature, are much more limited, with the Boublík-Mansoori-Carnahan-Starling-Leland (BMCSL) equation Bou70  standing out as the usual favorite. The situation for one-component hard-disc fluids is rather similar. Here, no analog of the CS equation using the $`\frac{1}{3}\text{(v)}+\frac{2}{3}\text{(c)}`$ recipe has been derived, due to the absence of an analytical solution of the Percus-Yevick (PY) equation in this instance. Nevertheless, accurate and simple equations of state have been proposed, such as the popular Henderson equation DH  and the recent one by the present authors SHY . Hard-disc mixtures, on the other hand, have received much less attention and the proposed equations of state for these systems are rather scarce. Given this scenario, the major aim of this paper is to show that, on the basis of a simple recipe, accurate equations of state of a multicomponent $`d`$-dimensional additive hard-sphere mixture may be derived, requiring the equation of state of the one-component system as the only input. The recipe makes use of a consistency condition that arises in the case that one of the components in the mixture has a vanishing size, as well as from some insight gained from the form of the radial distribution functions at contact given by the solution of the Percus-Yevick equation for a hard-sphere fluid in three dimensions L64 .

Let us consider an $`N`$-component system of hard spheres in $`d`$ dimensions. The total number density is $`\rho `$, the set of molar fractions is $`\{x_1,\mathrm{},x_N\}`$, and the set of diameters is $`\{\sigma _1,\mathrm{},\sigma _N\}`$. The volume packing fraction is $`\eta =v_d\rho \sigma ^d`$, where $`v_d=(\pi /4)^{d/2}/\mathrm{\Gamma }(1+d/2)`$ is the volume of a $`d`$-dimensional sphere of unit diameter and $`\sigma ^n_ix_i\sigma _i^n`$. In the case of a polydisperse mixture ($`N\mathrm{}`$) characterized by a size distribution $`f(\sigma )`$, $`\sigma ^n𝑑\sigma \sigma ^nf(\sigma )`$. Our goal is to propose a simple equation of state (EOS) for the mixture, $`Z^{(N)}(\eta )`$, consistent with a given EOS for a one-component system, $`Z^{(1)}(\eta )`$, where $`Z=p/\rho k_BT`$ is the usual compressibility factor. A consistency condition appears when one of the species, say the $`N`$-th, has a vanishing diameter, i.e. $`\sigma _N0`$. In that case,

$$Z^{(N)}(\eta )(1x_N)Z^{(N1)}(\eta )+\frac{x_N}{1\eta }.$$
(1)
At a more fundamental level, we will consider the contact values of the radial distribution functions, $`g_{ij}^{(N)}(\sigma _{ij})`$, the knowledge of which implies that of the EOS through the relation

$$Z^{(N)}(\eta )=1+2^{d1}\eta \underset{i=1}{\overset{N}{}}\underset{j=1}{\overset{N}{}}x_ix_j\frac{\sigma _{ij}^d}{\sigma ^d}g_{ij}^{(N)}(\sigma _{ij}).$$
(2)
Taking as a guide the form of $`g_{ij}^{(N)}`$ obtained through the solution of the PY equation for hard spheres ($`d=3`$) L64 , we propose to approximate $`g_{ij}^{(N)}`$ by a linear interpolation between $`g^{(1)}`$ and $`(1\eta )^1`$, namely

$$g_{ij}^{(N)}(\sigma _{ij})=\frac{1}{1\eta }+\left[g^{(1)}(\sigma )\frac{1}{1\eta }\right]\frac{\sigma ^{d1}}{\sigma ^d}\frac{\sigma _i\sigma _j}{\sigma _{ij}}.$$
(3)
When the above ansatz is inserted into equation (2), one gets

$`Z^{(N)}(\eta )1`$ $`=`$ $`\left[Z^{(1)}(\eta )1\right]2^{1d}\mathrm{\Delta }_0`$ (4)
$`+{\displaystyle \frac{\eta }{1\eta }}\left(1\mathrm{\Delta }_0+{\displaystyle \frac{1}{2}}\mathrm{\Delta }_1\right),`$
where

$`\mathrm{\Delta }_p`$ $`=`$ $`{\displaystyle \frac{\sigma ^{d+p1}}{\sigma ^d^2}}{\displaystyle \underset{n=p}{\overset{d1}{}}}{\displaystyle \frac{(d+p1)!}{n!(d+p1n)!}}\sigma ^{np+1}\sigma ^{dn},`$ (5)
$`(p=0,1).`$
This form of the EOS complies with the requirement (1). Note that equation (4) expresses $`Z^{(N)}(\eta )1`$ as a linear combination of $`Z^{(1)}(\eta )1`$ and $`(1\eta )^11`$, but the dependence of the coefficients on the size distribution is much more involved than in equation (3). The key outcome of this paper is the EOS given by equation (4), in which the compressibility factor of the mixture is obtained from that of the one-component system for arbitrary values of the dimensionality $`d`$ and the number of components $`N`$. It is worth noticing that in the one-dimensional case, equation (4) yields the exact result $`Z^{(N)}(\eta )=Z^{(1)}(\eta )`$.

As a straightforward application of equation (4), one can easily get $`B_n^{(N)}=v_d^{n1}\sigma ^d^{n1}\left[2^{1d}\mathrm{\Delta }_0b_n^{(1)}+1\mathrm{\Delta }_0+\frac{1}{2}\mathrm{\Delta }_1\right]`$, where the virial coefficients $`B_n^{(N)}`$ are defined by $`Z^{(N)}(\eta )=1+_{n=2}^{\mathrm{}}B_n^{(N)}\rho ^{n1}`$. and where $`b_n^{(1)}`$ are the reduced virial coefficients of the one-component system, i.e. $`Z^{(1)}(\eta )=1+_{n=2}^{\mathrm{}}b_n^{(1)}\eta ^{n1}`$.

We will now focus on the case of hard discs ($`d=2`$). Equation (4) then becomes

$$Z^{(N)}(\eta )=Z^{(1)}(\eta )\frac{\sigma ^2}{\sigma ^2}+\frac{1}{1\eta }\left(1\frac{\sigma ^2}{\sigma ^2}\right).$$
(6)
The relationship between $`Z^{(N)}(\eta )`$ and $`Z^{(1)}(\eta )`$ as given by equation (6) rests on a different rationale from that pertaining to another simple proposal, namely the Conformal Solution Theory (CST) HM86 ; Baus . In this latter theory, the EOS reads $`Z_{\text{CST}}^{(N)}(\eta )=Z^{(1)}(\eta _{\text{eff}})`$ with $`\eta _{\text{eff}}=\frac{1}{2}\left(1+\sigma ^2/\sigma ^2\right)\eta `$, but we note that this equation does not comply with the general requirement (1). If the one-component system is assumed to be described by the Scaled Particle Theory (SPT) RFL , our extension to mixtures takes on a particularly simple form:

$$Z_{\text{SPT}}^{(N)}(\eta )=\frac{1\left(1\sigma ^2/\sigma ^2\right)\eta }{(1\eta )^2}.$$
(7)
This is precisely the true SPT EOS for mixtures Baus , which is indeed rewarding. The EOS $`Z^{(1)}(\eta )=\left[12\eta +(2\eta _01)\eta ^2/\eta _0^2\right]^1`$, where $`\eta _0=\sqrt{3}\pi /6`$ is the crystalline close-packing fraction, has been recently proposed by us SHY  to describe a one-component system. When this EOS, hereafter referred to as the SHY EOS following the nomenclature introduced in reference Fpictures , is substituted into equation (6), we obtain the following extension:

$$Z_{\text{eSHY}}^{(N)}(\eta )=\frac{\sigma ^2/\sigma ^2}{12\eta +(2\eta _01)\eta ^2/\eta _0^2}+\frac{1}{1\eta }\left(1\frac{\sigma ^2}{\sigma ^2}\right).$$
(8)
The well-known Henderson (H) EOS DH  can also be extended:

$$Z_{\text{eH}}^{(N)}(\eta )=\frac{1\left(1\sigma ^2/\sigma ^2\right)\eta +(b_3^{(1)}3)\left(\sigma ^2/\sigma ^2\right)\eta ^2}{(1\eta )^2},$$
(9)
where $`b_3^{(1)}=\frac{16}{3}\frac{4}{\pi }\sqrt{3}`$. This equation is quite similar to the one proposed by Barrat et al. Baus , the only difference being that the coefficient of $`\eta ^2`$ in the numerator is $`b_3^{(N)}12\sigma ^2/\sigma ^2`$, where $`b_3^{(N)}`$ is the exact (reduced) third virial coefficient. Nevertheless, since $`b_3^{(N)}`$ is well approximated by $`1+(b_3^{(1)}1)\sigma ^2/\sigma ^2`$, both EOS are practically indistinguishable. Although we could consider the extensions of other EOS originally proposed for a one-component system of hard discs (for a list of many such EOS we refer the reader to references SHY ; Fpictures ), for the sake of simplicity we will restrict our analysis to the SPT, eSHY and eH EOS.

Let us now consider the virial coefficients $`B_n^{(N)}`$ for hard discs. It follows that in this case $`B_n^{(N)}=\left(\pi /4\right)^{n1}\sigma ^2^{n1}\left[1+(b_n^{(1)}1)\sigma ^2/\sigma ^2\right]`$. This equation yields the exact second virial coefficient Baus , the higher coefficients being approximate. In the particular case of a binary mixture, the composition-independent coefficients $`B_{n_1,n_2}^{(2)}`$ are defined through $`B_n^{(2)}=_{n_1=0}^n\frac{n!}{n_1!(nn_1)!}B_{n_1,nn_1}^{(2)}x_1^{n_1}x_2^{nn_1}`$. According to equation (6),

$`B_{n_1,n_2}^{(2)}`$ $`=`$ $`\left({\displaystyle \frac{\pi }{4}}\right)^{n1}\sigma _1^{2(n1)}\alpha ^{2(n_21)}[{\displaystyle \frac{n_1}{n}}\alpha ^2+{\displaystyle \frac{n_2}{n}}+(b_n^{(1)}1)`$
$`\times ({\displaystyle \frac{n_1(n_11)}{n(n1)}}\alpha ^2+{\displaystyle \frac{2n_1n_2}{n(n1)}}\alpha +{\displaystyle \frac{n_2(n_21)}{n(n1)}})],`$
where $`n=n_1+n_2`$ and $`\alpha =\sigma _2/\sigma _1`$. This form has the same structure as the interpolation formula suggested by Wheatley W98 . In fact, he proposes an EOS (henceforth labelled as W) of the form

$$Z_\text{W}^{(2)}(\eta )=\frac{_{n=0}^7c_n\eta ^n}{(\eta \eta _0)^2},$$
(11)
where the coefficients $`c_n`$ are chosen so as to reproduce the first eight virial coefficients given by the interpolation formula W98 .

Now, let us consider the case $`d=3`$. Equation (4) then yields

$`Z^{(N)}(\eta )`$ $`=`$ $`=1+\left[Z^{(1)}(\eta )1\right]{\displaystyle \frac{\sigma ^2}{2\sigma ^3^2}}\left(\sigma ^2^2+\sigma \sigma ^3\right)`$ (12)
$`+{\displaystyle \frac{\eta }{1\eta }}\left[1{\displaystyle \frac{\sigma ^2}{\sigma ^3^2}}\left(2\sigma ^2^2\sigma \sigma ^3\right)\right].`$
Using the CS EOS CS , $`Z^{(1)}(\eta )=(1+\eta +\eta ^2\eta ^3)/(1\eta )^3`$, the result may be expressed as

$$Z_{\text{eCS}}^{(N)}(\eta )=Z_{\text{BMCSL}}^{(N)}(\eta )+\frac{\eta ^3}{(1\eta )^3}\frac{\sigma ^2}{\sigma ^3^2}\left(\sigma \sigma ^3\sigma ^2^2\right),$$
(13)
where the BMCSL EOS Bou70  is

$$Z_{\text{BMCSL}}^{(N)}(\eta )=\frac{1}{1\eta }+\frac{3\eta }{(1\eta )^2}\frac{\sigma \sigma ^2}{\sigma ^3}+\frac{\eta ^2(3\eta )}{(1\eta )^3}\frac{\sigma ^2^3}{\sigma ^3^2}.$$
(14)
As another, example, let us consider the Carnahan-Starling-Kolafa (CSK) EOS Ko86 , $`Z^{(1)}(\eta )=[1+\eta +\eta ^22\eta ^3(1+\eta )/3]/(1\eta )^3`$. Its extension is

$`Z_{\text{eCSK}}^{(N)}(\eta )`$ $`=`$ $`Z_{\text{eCS}}^{(N)}(\eta )+{\displaystyle \frac{\eta ^3(12\eta )}{(1\eta )^3}}{\displaystyle \frac{\sigma ^2}{6\sigma ^3^2}}`$ (15)
$`\times \left(\sigma ^2^2+\sigma \sigma ^3\right),`$
which does not coincide with Boublík’s extension to mixtures of the CSK EOS Bou86 :

$$Z_{\text{BCSK}}^{(N)}(\eta )=Z_{\text{BMCSL}}^{(N)}(\eta )+\frac{\eta ^3(12\eta )}{(1\eta )^3}\frac{\sigma ^2^3}{3\sigma ^3^2}.$$
(16)
Recently, Henderson and Chan (HC) have proposed a modification of the BMCSL EOS HSW98 ; Yau96  for the particular case of a binary mixture in which the concentration of the large spheres is exceedingly small, starting from an asymmetric prescription for the radial distribution functions at contact. The resulting EOS, with $`\sigma _1\sigma _2`$, is

$`Z_{\text{HC}}^{(2)}(\eta )`$ $`=`$ $`Z_{\text{BMCSL}}^{(2)}(\eta )+{\displaystyle \frac{4\eta x_1}{\sigma ^3}}\{x_1\sigma _1^3\{{\displaystyle \frac{3\eta }{2(1\eta )^2}}`$
$`\left(1{\displaystyle \frac{\sigma ^2}{\sigma ^3}}\sigma _1\right)+{\displaystyle \frac{\eta ^2}{2(1\eta )^3}}\left[1\left({\displaystyle \frac{\sigma ^2}{\sigma ^3}}\sigma _1\right)^2\right]`$
$`+\mathrm{exp}\left[{\displaystyle \frac{3\eta }{2(1\eta )^2}}({\displaystyle \frac{\sigma ^2}{\sigma ^3}}\sigma _11)\right]1\}`$
$`+{\displaystyle \frac{\eta ^2x_2}{4(1\eta )^3}}\left({\displaystyle \frac{\sigma ^2}{\sigma ^3}}\sigma _2\right)^2(\sigma _1\sigma _2)`$
$`\times [(\sigma _1+\sigma _2)^2\eta \sigma _2(\sigma _1^2+\sigma _2^2+\sigma _1\sigma _2){\displaystyle \frac{\sigma ^2}{\sigma ^3}}]\}.`$
We shall now perform a comparison with the (very few) available computer simulation data. We begin with hard-disc mixtures. In figure 1 we display the packing-fraction dependence of the compressibility factor $`Z`$ for the SPT, W, eH and eSHY EOS, together with the simulation results of Barrat et al. Baus , for the binary mixture defined by $`x_1=0.351`$ and $`\sigma _2/\sigma _1=0.8`$. In this case, the performance of the eSHY EOS is outstanding and clearly superior to all the other choices. To complete the picture, in figure 2 we present the results for the ratio of the fifth virial coefficient to the fourth power of the (exact) second virial coefficient as a function of the larger disc concentration and for two size ratios. Here, the best agreement with the numerical data of Wheatley WH98  is obtained with the eH EOS, which is not very surprising since in the one-component case ($`x_1=1`$) it gives a very good estimate of this ratio. Nevertheless, the overall trends including the position of the maximum are still captured in all approximations.

As far as hard-sphere mixtures are concerned, the following comments can be made. To our knowledge, only simulation results for binary mixtures have been reported. The most recent data BMLS96  indicate that the BMCSL EOS underestimates the pressure as obtained through simulation. In fact, the BCSK EOS is geared to correct this deficiency, at least for $`\eta <0.5`$, in a similar fashion as the CSK EOS corrects the CS EOS. As a general trend, for $`\eta <0.5`$, our extended EOS, namely the eCS and the eCSK, also go in the correct direction. Moreover, in this density range, $`Z_{\text{BMCSL}}<Z_{\text{eCS}}<Z_{\text{eCSK}}`$ and $`Z_{\text{BMCSL}}<Z_{\text{BCSK}}<Z_{\text{eCSK}}`$. Although limited in scope, the results shown in figure 3 illustrate these features. Here we have considered an equimolar binary mixture with size ratio $`\sigma _2/\sigma _1=0.6`$. As the differences between the values predicted by the various EOS for the compressibility factor $`Z`$ are very small, we have chosen to present the results, including the simulation data of Yau et al. Yau96  (open circles) and Barošová et al. BMLS96  (filled circles), in terms of the packing fraction dependence of $`ZZ_{\text{BMCSL}}`$. Despite the scatter of the simulation results of Yau et al. Yau96 , it is apparent that, depending on the range, both the eCSK and eCS EOS seem to do a better job than either the BMCSL, BCSK or HC EOS (although in all fairness we should add that the equimolar condition is beyond the scope for which the latter EOS was originally devised). In fact, if one considers a higher density point computed by Yau et al. Yau96  ($`\eta =0.59`$, $`Z_{\text{simul}}Z_{\text{BMCSL}}=0.26`$) that is off the scale, it appears that the overall trend is better captured by the eCS EOS, although for $`\eta <0.5`$ the eCSK should probably be the preferred EOS. The results for the composition dependence of the fifth virial coefficient for a binary mixture and two values of $`\sigma _2/\sigma _1`$ displayed in figure 4 also indicate that all the approximations lead to very good values as compared to the recent numerical data of Enciso et al. Enciso98 , with a slight superiority of the BCSK EOS for the region around the maximum. The HC and the eCSK results have not been included, since they are almost identical to the ones of the BMCSL and the eCS, respectively.

In conclusion, it is fair to state that we have introduced a very simple and general recipe that allows one to get a reasonably accurate approximation to the EOS of a multicomponent mixture of $`d`$-dimensional hard-spheres from any reasonable EOS of the one-component system. It also seems that, as exemplified in the case of binary three-dimensional hard-sphere mixtures, the more accurate the EOS of the one-component system, the better results the approximation yields.

Two of us (A. S.) and (S. B. Y.) would like to acknowledge partial support from the DGES (Spain) through Grant No. PB97-1501 and from the Junta de Extremadura (Fondo Social Europeo) through Grant No. PRI97C1041. M. L. H. wants to thank the hospitality of Universidad de Extremadura, where the draft of the paper was prepared.