format: text

text:
# Graph inverse semigroups, groupoids and their 𝐶^∗-algebras

## 1. Introduction

There is now a substantial literature on the $`C^{}`$-algebra associated with a (countable) directed graph. Among the motivations for this are the Bratteli diagrams for AF-algebras and especially the Cuntz-Krieger algebras, which can be interpreted in graphical terms with the matrix $`A`$, determining such an algebra, regarded as the incidence matrix of the graph. A helpful survey of the field up to 1998 has been given by A. Kumjian (). In the literature surveyed by Kumjian, the graphs considered satisfy finiteness conditions on the edges coming into and going out of a vertex. Usually, local finiteness has been required, viz. that at each vertex $`v`$, only finitely many edges end at $`v`$, and only finitely many edges start at $`v`$. Many of these results were shown to be valid in the row finite case, i.e. where we only assume that finitely many edges start at $`v`$ for each vertex $`v`$ of the graph.

Recently, there has been interest in removing the finiteness requirements on the graph. See, for example, . Motivation for this is to be found even in the original paper  of Cuntz in which he studied what are now called the Cuntz algebras $`𝒪_n`$. These are graph $`C^{}`$-algebras, the natural graph associated with $`𝒪_n`$ being a bouquet of $`n`$ circles (one vertex). When $`n<\mathrm{}`$, the graph is locally finite. When $`n=\mathrm{}`$, this is no longer the case. (Indeed up to the work of Exel and Laca (), $`𝒪_{\mathrm{}}`$ was the only known example that had been worked out of a Cuntz-Krieger algebra whose matrix was not row-finite.) Even in the case of the Cuntz algebras, there is a significant difference between the row finite/non-row finite cases. This is shown by the fact that in , in a number of instances, proofs given for $`𝒪_n`$ with $`n<\mathrm{}`$ do not apply in the case of $`𝒪_{\mathrm{}}`$, so that different proofs were required for that case.

A representation of a directed graph $``$ is determined by certain partial isometries on a Hilbert space indexed by the vertices and edges. The $`C^{}`$-algebra $`C^{}()`$ of $``$ is the universal $`C^{}`$-algebra for such representations. In the locally finite case, insight into this $`C^{}`$-algebra is provided by the path groupoid $`G`$ of $``$. This is an r-discrete groupoid, and its units are just the infinite paths in $``$. Then (cf. ) if $``$ is locally (or even row) finite and has no sinks, we have $`C^{}()C^{}(G)`$, and this groupoid connection ennables one to interpret properties of $`C^{}()`$ in dynamical terms.

When we look for this groupoid connection without assuming local finiteness, we run into a problem since the space of infinite paths in $``$ is not a locally compact Hausdorff space in any obvious way. The main objective of this paper is to show that, despite this problem with the infinite paths, there is a natural path groupoid available in complete generality. A peculiarity of this groupoid is that we have to include some finite paths. To determine what this groupoid is, we use an approach based on inverse semigroups.

Indeed, there is a close connection between inverse semigroups and r-discrete groupoids. This was first observed and studied by J. Renault in his monograph . Recently, the present author in his book  gave a detailed account of this connection. One of the main results of \[12, Ch.4\] is a construction which associates with any (countable) inverse semigroup $`S`$ a universal groupoid $`H`$ canonically related to $`S`$ such that $`C^{}(S)C^{}(H)`$. The path groupoid will be a reduction of the universal groupoid for a certain inverse semigroup associated with the graph. So we have to come up with an appropriate inverse semigroup $`S`$ for $``$.

In the $`𝒪_n`$-case, the appropriate inverse semigroup is $`S_n`$ which was introduced by Renault in \[14, p.141\]. For a general directed graph $``$, a natural candidate for such an inverse semigroup is the inverse semigroup of path pairs $`(\alpha ,\beta )`$ considered in \[12, p.158\]. As mentioned there, an unsatisfactory feature of this inverse semigroup is that, unlike the Cuntz case, it is not generated by the edges. The way out of this difficulty is suggested by the definition of a representation of $``$ referred to above. We have to include the vertices in the inverse semigroup.

The precise details of this are given in §2. The graph inverse semigroup of $``$, denoted by $`S_{}`$, is defined as the inverse semigroup generated by the edges and vertices of $``$ subject to certain “Cuntz-like” relations. We show that $`S=S_{}`$ can be identified with an inverse semigroup of path pairs, where we permit vertices to stand as surrogates for “paths” of zero length. This “path-pair” characterization of $`S`$ is useful for calculation purposes.

The universal groupoid $`H`$ of $`S`$ is then determined in the paper. We focus on a natural reduction of this which we will call the graph groupoid $`G`$. This groupoid is similar to the graph groupoid in the locally finite case and indeed is the same groupoid in that case. The main difference is that we must include in the unit space $`G^0`$ those finite paths ending in a vertex $`vV_{\mathrm{}}`$, where $`V_{\mathrm{}}`$ is the set of vertices emitting infinitely many edges. Sequences of infinite paths can converge to such finite paths, in particular to $`V_{\mathrm{}}`$-vertices. We write $`V_f`$ for $`VV_{\mathrm{}}`$, the set of vertices emitting only finitely many edges.

The representations of $``$ correspond to a certain class of representations of $`S`$, and using the canonical identification of $`C^{}(S)`$ with $`C^{}(H)`$ in \[12, Ch. 4\], we show that in fact these representations correspond to the representations of $`G`$. So we obtain that $`C^{}()=C^{}(G)`$ just as in the locally finite case.

Next we turn to the issue of the amenability of $`C^{}()`$. A groupoid form of Cuntz’s crossed-product argument for the nuclearity (and hence amenability) of $`𝒪_n`$ was given by J. Renault in his book \[14, p.138ff.\]. For the case of a locally finite graph $``$, an ingenious adaptation of this groupoid argument was given by Kumjian, Pask, Raeburn and Renault () to show that $`C^{}()`$ is always amenable. We adapt this argument further to establish the same result in complete generality. The technical difficulty is that of dealing with the paths of finite length in $`G^0`$.

The last section of the paper deals with the simplicity of $`C^{}()`$. Kumjian, Pask, Raeburn and Renault () characterized the simplicity of $`C^{}()`$ in terms of condition (K) and cofinality in the locally finite case. (See below.) Recently, W. Szymanski (\[19, Theorem 12\]) characterized the simplicity of $`C^{}()`$ for general $``$ using the approach of Exel and Laca (). He showed that $`C^{}()`$ is simple if and only if ($`\alpha `$) and ($`\beta `$) hold where:

* all loops in $``$ have exits;
* for any $`vV`$, the smallest hereditary, saturated subset of $`V`$ that contains $`v`$ is equal to $`V`$.

(In $`(\beta )`$, a subset $`H`$ of $`V`$ is called hereditary if $`wH`$ whenever there is a path from some $`vH`$ to $`w`$, and is called saturated if $`wH`$ whenever $`wV_f`$ and every edge starting at $`w`$ ends in $`H`$.)

We show first that for general $``$, the condition (K) of  \- that there are no vertices emitting exactly one loop - is equivalent to $`G`$ being essentially principal (i.e. every closed, invariant subset of $`G^0`$ contains a dense subset of elements with trivial isotropy). (This result is a counterpart to the result of Kumjian, Pask and Raeburn (\[10, Lemma 3.4\]) that, in the locally finite case (no sinks), the groupoid $`G`$ is essentially free if and only if every loop in $``$ has an exit.) We then show (Theorem 4) that $`C^{}()`$ is simple if (a), (b) and (c) hold, where:

* $``$ has property (K);
* $``$ is cofinal (i.e. given any $`vV`$ and any infinite path $`z`$, then there is a path from $`v`$ to at least one of the vertices that $`z`$ passes through);
* if $`vV`$ and $`wV_{\mathrm{}}`$, then there is a path from $`v`$ to $`w`$.

It is not difficult to show that (a),(b) and (c) together are equivalent to ($`\alpha `$) and ($`\beta `$) together, so that Theorem 4 is effectively just one of the implications in Szymanski’s theorem. The point of including Theorem 4 in the present paper is that it gives an alternative approach to the simplicity of $`C^{}()`$ using the groupoid $`G`$ of the paper. The groupoid proof that we give is just a variant of the method used by J. Renault in his book  (see also the approach of ) to establish the simplicity of the Cuntz $`C^{}`$-algebras: using $`G`$ in place of the Cuntz groupoids, Renault’s approach works for a completely general graph $``$.

Another approach to the simplicity of graph $`C^{}`$-algebras has been given by Jürgen Schweizer (). Schweizer introduces the concept of a continuous measured diagram, in which we are given locally compact spaces $`D,X,Y`$ with continuous maps $`s:DX`$, $`r:DY`$, together with certain measures on $`D`$ indexed by the elements of $`Y`$. The case where $`X=Y`$ gives a natural $`C^{}`$-correspondence, which in turn determines a Cuntz-Pimsner algebra $`𝒪_𝔇`$. The discrete case of such a diagram is just that of a directed graph with set of vertices $`X`$, and in that case, $`𝒪_𝔇`$ is the same as the graph $`C^{}`$-algebra. Using , Schweizer (\[17, Corollary 5.2\]) proves that when $`X`$ is compact and $`r`$ is onto, $`𝒪_𝔇`$ is simple if and only if the continuous measured diagram is non-periodic and minimal. The simplicity results of Schweizer and Szymanski are different. On the one hand, Schweizer’s result is not restricted to the discrete (graphical) case, while on the other hand, its compactness condition on $`X`$ in the graphical situation forces the vertex set to be finite. It would be interesting to relate the approach of Schweizer to the groupoid approach.

The author is grateful to Iain Raeburn and David Pask for bringing to his attention the theorem of Wojciech Szymanski described above, and for pointing out an error in an earlier version of the paper. He is also grateful to Marcelo Laca, David Pask, Iain Raeburn, Jürgen Schweizer and Wojciech Szymanski for sending him recent papers on graph $`C^{}`$-algebras. Finally, he wishes to thank Alan Donsig, John Meakin, David Pitts and Baruch Solel for helpful conversations on the topics of this paper.

## 2. Some preliminaries

Let $``$ be a directed graph. Its set of vertices is denoted by $`V`$ and its set of edges by $`E`$. For each edge $`e`$, $`s(e)`$ is the initial vertex (source) of $`e`$ and $`r(e)`$ the terminal vertex of $`e`$. It is assumed throughout the paper that $`V`$ and $`E`$ are countable sets.

The graph $``$ is called row finite if for each $`vV`$, the set of edges starting at $`v`$ is finite. The graph is called locally finite if for each $`vV`$, the set of edges starting at $`v`$ is finite, and the set of edges terminating at $`v`$ is finite. A vertex $`v`$ is called a sink if there are no edges starting at $`v`$. Throughout the paper we will assume that there are no sinks in $``$ (unless the contrary is explicitly specified.)

A reason for this is as follows. We want to examine $`C^{}()`$ using a “path groupoid” $`G`$, and the paths that make up the unit space of the appropriate groupoid $`G`$ are such that they cannot end at a sink. So if we want to use the path groupoid to study $`C^{}()`$, then we cannot allow sinks in $``$. The $`C^{}`$-algebra $`C^{}()`$ still makes good sense whether there are sinks or not, and indeed, groupoid techniques can still be used using the universal groupoid $`H`$ introduced in the paper rather than the path groupoid $`G`$. Further, as is pointed out in , it is technically easy to reduce to the case where there are no sinks.

The set $`V`$ of vertices is the disjoint union of the sets $`V_f`$ and $`V_{\mathrm{}}`$, where $`vV_f`$ if there are finitely many edges starting at $`v`$, while $`vV_{\mathrm{}}`$ if there are infinitely many edges starting at $`v`$.

The edge $`e`$ with reversed orientation is denoted by $`e^{}`$. So $`s(e^{})=r(e)`$ and $`r(e^{})=s(e)`$. We write $`E^{}`$ as the set of $`e^{}`$’s.

A finite path is a sequence $`\alpha `$ of edges $`e_1,\mathrm{},e_k`$ where $`s(e_{i+1})=r(e_i)`$ for $`1ik1`$. We write $`\alpha =e_1e_2\mathrm{}e_k`$. The length $`l(\alpha )`$ of $`\alpha `$ is just $`k`$. Each vertex $`v`$ is regarded as a finite path of length $`0`$. We define $`r(\alpha )=r(e_k)`$ and $`s(\alpha )=s(e_1)`$. For $`vV`$, we set $`r(v)=v=s(v)`$. The set of finite paths in $``$ is denoted by $`Y`$. Note that $`VY`$. The set of infinite paths $`z=z_1z_2\mathrm{}`$ in $``$ is denoted by $`Z`$. The length $`l(z)`$ of $`zZ`$ is defined to be $`\mathrm{}`$.

Given two vertices $`v,w`$, we say that $`vw`$ if there exists a path $`\alpha `$ such that $`s(\alpha )=v,r(\alpha )=w`$. If $`z`$ is a path in $``$ and $`vV`$, then we write $`zv`$ to mean that $`r(z_i)v`$ for all $`i`$. We write $`zv`$ if $`r(z_i)v`$ for all $`i`$.

We now briefly discuss inverse semigroups. A semigroup $`S`$ is called an inverse semigroup if for all $`sS`$, there exists a unique element $`tS`$ such that $`sts=s,tst=t`$. We write the element $`t`$ as $`s^{}`$. Note that $`s^{}=s`$. Inverse semigroups can be identified with semigroups of partial one-to-one maps on a set that contain their inverses. Every element $`ss^{}`$ belongs to the set $`I`$ of idempotents of $`S`$. The set $`I`$ is a commutative subsemigroup of $`S`$ and so is a semilattice. (In semigroup theory, the semilattice of idempotents in $`S`$ is usually denoted by $`E`$, but in this paper, $`E`$ stands for the set of edges in $``$.) Homomorphic images of inverse semigroups are inverse semigroups.

A congruence $`\rho `$ on a semigroup $`S`$ is an equivalence relation for which $`(xa,xb),(ax,bx)\rho `$ whenever $`(a,b)\rho `$. If $`\rho `$ is a congruence on $`S`$, then $`S/\rho `$ is a semigroup in the natural way.

We now recall the definition (\[2, pp.40-41\]) of the semigroup $`S`$ generated by a set $`X`$ subject to the generating relations $`u_\lambda =v_\lambda `$ ($`\lambda \mathrm{\Lambda }`$). Let $`F_X`$ be the semigroup of words in $`X`$ with juxtaposition as product, and for $`\lambda \mathrm{\Lambda }`$, let $`u_\lambda ,v_\lambda F_X`$. Then $`S`$ is just the quotient $`F_X/\rho `$ where $`\rho `$ is the smallest congruence on $`F_X`$ containing all of the pairs $`(u_\lambda ,v_\lambda )`$.

Throughout the paper, we will assume the theory of r-discrete groupoids as presented, for example, in .

## 3. The inverse semigroup of a graph and the path groupoid

Let $`z`$ be an element not in $`VEE^{}`$. The graph inverse semigroup $`S=S_{}`$ of the graph $``$ is defined to be the semigroup generated by $`(VEE^{})\{z\}`$ subject to the relations:

* $`z`$ is a zero for $`S`$;
* $`s(e)e=e=er(e),r(e)e^{}=e^{}=e^{}s(e)`$ for all $`eE`$;
* $`ab=z`$ if $`a,bVEE^{}`$ and $`r(a)s(b)`$;
* $`e^{}f=z`$ if $`e,fE`$ and $`fe`$.

Note that $`S`$ is countable since $`EV`$ is.

We will see in a moment that $`S`$ is actually an inverse semigroup. But for the present, we describe a model $`T`$ for $`S`$. The elements of $`T`$ are the pairs of finite paths $`(\alpha ,\beta )`$ with $`r(\alpha )=r(\beta )`$, together with a zero element $`z`$. An involution is defined on $`T`$ by: $`z^{}=z,(\alpha ,\beta )^{}=(\beta ,\alpha )`$, and the product is determined by:

(3.1) $`(\alpha ,\alpha ^{}\mu )(\alpha ^{},\beta )`$ $`=`$ $`(\alpha ,\beta \mu )`$
(3.2) $`(\alpha ,\alpha ^{})(\alpha ^{}\mu ,\beta ^{})`$ $`=`$ $`(\alpha \mu ,\beta ^{})`$
All other products in $`T`$ are $`z`$. Note that for finite paths $`\alpha ,\beta `$, the expression $`\alpha `$$`\beta `$ is defined only when $`r(\alpha )=s(\beta )`$, and in that case, is just the finite path obtained in the obvious way by juxtaposition. Recall that each vertex $`v`$ is regarded as a finite path. For any finite path $`\mu `$, we specify that $`s(\mu )\mu =\mu =\mu r(\mu )`$. Note that the product of two pairs $`(\alpha _1,\beta _1),(\alpha _2,\beta _2)`$ is non-zero if and only if $`\beta _1`$ is an initial segment of $`\alpha _2`$ or conversely. In this case, we say that $`\beta _1`$, $`\alpha _2`$ are comparable. Note that if $`\alpha \mu ,\beta \nu `$ are comparable, then so are $`\alpha ,\beta `$. The set $`I`$ of idempotents of $`S`$ is just the set of pairs $`(\alpha ,\alpha )`$, and so can be identified with $`Y`$. The product on $`I`$ of two elements $`\alpha ,\beta z`$ is given by $`\alpha \beta =\alpha =\beta \alpha `$ if $`\beta `$ is an initial segment of $`\alpha `$, and is $`z`$ if $`\alpha ,\beta `$ are not comparable.

A similar semigroup to $`T`$ was suggested by the author in \[12, p.158\] but there is a significant difference: in , the paths $`\alpha ,\beta `$ were of finite, non-zero length, and the edges and vertices do not lie in the semigroup. However, as we will see (Proposition 2), the edges and vertices lie inside and generate $`T`$.

###### Proposition 1.

The set $`T`$, with the above involution and product, is an inverse semigroup.

###### Proof.

We first have to show that the product in $`T`$ is associative. If one of the terms is $`z`$, then this is obvious. So let $`(\alpha _i,\beta _i)T`$ ($`1i3`$), $`w_1=(\alpha _1,\beta _1)((\alpha _2,\beta _2)(\alpha _3,\beta _3))`$ and $`w_2=((\alpha _1,\beta _1)(\alpha _2,\beta _2))(\alpha _3,\beta _3)`$. We have to show that $`w_1=w_2`$.

The cases that give $`w_1z`$ are as follows (for appropriate words $`\mu ,\nu `$):

* $`\beta _2=\alpha _3\mu `$, $`\beta _1=\alpha _2\nu `$, $`w_1=(\alpha _1,\beta _3\mu \nu )`$;
* $`\beta _2=\alpha _3\mu `$, $`\alpha _2=\beta _1\nu `$, $`w_1=(\alpha _1\nu ,\beta _3)`$;
* $`\alpha _3=\beta _2\mu `$, $`\beta _1=\alpha _2\mu \nu `$, $`w_1=(\alpha _1,\beta _3\nu )`$;
* $`\alpha _3=\beta _2\mu `$, $`\alpha _2\mu =\beta _1\nu `$, $`w_1=(\alpha _1\nu ,\beta _3)`$;

One checks directly that in each of these four cases, $`w_2=w_1`$. (In case (4), one needs to consider separately the cases $`\alpha _2=\beta _1\xi `$ and $`\beta _1=\alpha _2\xi `$.) So if $`w_1z`$, then $`w_1=w_2`$. Similarly, one shows that if $`w_2z`$, then $`w_2=w_1`$. The associative law then follows.

Next we have to show that for each $`tT`$, $`t^{}`$ is the only element $`t^{}`$ for which $`tt^{}t=t,t^{}tt^{}=t^{}`$. If $`t=z`$, then this is trivial. If $`t=(\alpha ,\beta )`$, then since $`tt^{}t=t=(\alpha ,\beta )`$, then $`t^{}=(\alpha ^{},\beta ^{})`$ for some finite paths $`\alpha ^{},\beta ^{}`$, with $`\beta ^{},\alpha `$ and $`\beta ,\alpha ^{}`$ comparable. If $`\beta ^{}=\alpha \mu `$ with $`l(\mu )>0`$, then the second component of $`tt^{}t`$ would be longer than $`\beta `$, the second component of $`t`$, and we contradict $`tt^{}t=t`$. Similarly, by considering $`t^{}tt^{}=t^{}`$ we obtain that $`\alpha `$ is not of the form $`\beta ^{}\mu `$ for any $`\mu `$ of positive length. So $`\beta ^{}=\alpha `$. Similarly, $`\alpha ^{}=\beta `$ and $`t^{}=t^{}`$. Obviously $`tt^{}t=t,t^{}tt^{}=t^{}`$. ∎

###### Proposition 2.

The map $`\mathrm{\Phi }:S=S_{}T`$ where

$$\mathrm{\Phi }(v)=(v,v),\mathrm{\Phi }(e)=(e,r(e)),\mathrm{\Phi }(e^{})=(r(e),e),\mathrm{\Phi }(z)=z,$$

is a semigroup isomorphism.

###### Proof.

Let $`W=VEE^{}\{z\}`$. Then $`\mathrm{\Phi }`$ extends in the obvious way to a homomorphism, also denoted $`\mathrm{\Phi }:F_WT`$. The map $`\mathrm{\Phi }:F_WT`$ is onto since every $`tT`$ is a product of $`\mathrm{\Phi }(w)`$’s: for example, if $`\alpha =\alpha _1\mathrm{}\alpha _k`$ and $`\beta =\beta _1\mathrm{}\beta _l`$, and $`t=(\alpha ,\beta )T`$, then

$$(\alpha ,\beta )=\mathrm{\Phi }(\alpha _1)\mathrm{}\mathrm{\Phi }(\alpha _k)\mathrm{\Phi }(\beta _l^{})\mathrm{}\mathrm{\Phi }(\beta _1^{}).$$

Let $``$ be the congruence on $`F_W`$ generated by the relations (i)-(iv) above. To prove that $`\mathrm{\Phi }`$ descends to a homomorphism $`\stackrel{~}{\mathrm{\Phi }}`$ from $`S=F_W/`$ onto $`T`$, we just have to check that the elements of $`\mathrm{\Phi }(W)`$ satisfy the relations in $`T`$ corresponding to (i)-(iv). This is straightforward. (i) is trivially true. In (ii), for example, the equalities

$$\mathrm{\Phi }(s(e))\mathrm{\Phi }(e)=\mathrm{\Phi }(e)=\mathrm{\Phi }(e)\mathrm{\Phi }(r(e))$$

are just

$$(s(e),s(e))(e,r(e))=(e,r(e))=(e,r(e))(r(e),r(e)).$$

In (iii), if $`a=vV`$ and $`r(a)s(b)`$, then either $`b=wV`$ with $`wv`$, or $`b=e`$ with $`vs(e)`$ or $`b=e^{}`$ with $`vr(e)`$. Then $`\mathrm{\Phi }(a)\mathrm{\Phi }(b)`$ is either $`(v,v)(w,w)`$ or $`(v,v)(e,r(e))`$ or $`(v,v)(r(e),e)`$ and these are all $`z`$. The other possibilities for $`a`$ are dealt with similarly. For (iv), $`\mathrm{\Phi }(e^{})\mathrm{\Phi }(f)=(r(e),e)(f,r(f))=z`$ if $`ef`$.

To show that $`\stackrel{~}{\mathrm{\Phi }}:ST`$ is an isomorphism, suppose that for some $`s,s^{}F_W`$ we have $`\mathrm{\Phi }(s)=\mathrm{\Phi }(s^{})`$. We have to show that $`ss^{}`$. Using the relations (i)-(iv), we can find $`t,t^{}F_W`$, where $`st`$, $`s^{}t^{}`$ and, either $`t=t^{}=z`$, in which case $`ss^{}`$, or, in an obvious notation, $`t=\alpha \beta ^{},t^{}=\alpha ^{}(\beta ^{})^{}`$ for paths $`\alpha ,\beta ,\alpha ^{},\beta ^{}`$ with $`r(\alpha )=r(\beta ),r(\alpha ^{})=r(\beta ^{})`$. Then

$$(\alpha ,\beta )=\mathrm{\Phi }(t)=\mathrm{\Phi }(s)=\mathrm{\Phi }(s^{})=\mathrm{\Phi }(t^{})=(\alpha ^{},\beta ^{})$$

and $`\alpha =\alpha ^{},\beta =\beta ^{}`$. So $`t=t^{}`$ and $`ss^{}`$. ∎

For the rest of the paper, we shall usually identify $`S`$ with $`T`$.

As a very simple example of the inverse semigroup $`S`$ of a graph $``$, consider the case where $``$ has exactly one edge $`e`$ with initial and terminal vertices $`v_1,v_2`$ respectively. (In this case, $``$ has a sink.) The elements of $`S`$ are then: $`v_1=(v_1,v_1),v_2=(v_2,v_2),(e,v_2),(v_2,e),(e,e)`$ and the zero $`z`$. Then the idempotent set $`I`$ of $`S`$ is $`\{v_1,v_2,(e,e),z\}`$, and $`v_1v_2=z`$, $`v_1(e,e)=(e,e)`$ and $`v_2(e,e)=z`$. The involution on $`S`$ interchanges $`(e,v_2)`$ and $`(v_2,e)`$ and leaves every other element of $`S`$ fixed. The other non-zero products in $`S`$ are: $`v_1(e,v_2)=(e,v_2)=(e,v_2)v_2,(e,v_2)(v_2,e)=(e,e),(v_2,e)(e,e)=(v_2,e)`$, $`(v_2,e)(e,v_2)=v_2`$ and the equalities obtained from these by applying the involution.

The next objective is to identify the universal groupoid of $`S`$ for general $``$. The universal groupoid (\[12, Ch. 4\]) $`H`$ of a countable inverse semigroup $`S`$ is constructed as follows. The unit space $`H^0`$ of $`H`$ is just the set of non-zero semicharacters $`\chi :I\{0,1\}`$, where $`I`$ is the commutative semigroup of idempotents of $`S`$. The topology on $`H^0`$ is just the topology of pointwise convergence on $`I`$. There is a dense subset $`\overline{I}=\{\overline{\alpha }:\alpha I\}`$ of $`H^0`$, where $`\overline{\alpha }(\beta )=1`$ if and only if $`\alpha \beta =\alpha `$. There is a natural right action of $`S`$ on $`H^0`$ given as follows. First, an element $`xH^0`$ is in the domain $`D_s`$ of $`sS`$ if $`x(ss^{})=1`$. The element $`x.sH^0`$ is given by: $`x.s(\alpha )=x(s\alpha s^{})`$. The map $`xx.s`$ is a homeomorphism from $`D_s`$ onto $`D_s^{}`$. The family of sets of the form $`D_{\alpha ,\alpha _1,\mathrm{}\alpha _n}`$, where

(3.3)
$$D_{\alpha ,\alpha _1,\mathrm{}\alpha _n}=D_\alpha D_{\alpha _1}^c\mathrm{}D_{\alpha _r}^c$$

(with $`c`$ standing for “complement” and $`\alpha ,\alpha _iI,\alpha \alpha _i,1ir`$) is a basis for the topology of $`H^0`$.

The universal groupoid $`H`$ is the quotient

$$\{(x,s):xD_s,sS\}/$$

where $`(x,s)(y,t)`$ whenever $`x=y`$ and there exists $`\alpha I`$ such that $`x(\alpha )=1(=x(ss^{})=x(tt^{}))`$ and $`\alpha s=\alpha t`$. The composable pairs are pairs of the form $`(\overline{(x,s)},\overline{(x.s,t)})`$ ($`xD_s`$, $`x.sD_t`$, $`s,tS`$), while the product and involution on $`H`$ are respectively given by $`(\overline{(x,s)},\overline{(x.s,t)})\overline{(x,st)}`$ and $`\overline{(x,s)}`$$``$$`\overline{(x.s,s^{})}`$. Then $`H`$ is an r-discrete groupoid and the map $`\mathrm{\Psi }`$, where $`\mathrm{\Psi }(s)=\{\overline{(x,s)}:xD_s\}=A_s`$ is an inverse semigroup isomorphism from $`S`$ into the ample semigroup $`H^a`$ of $`H`$. (Recall that for any r-discrete groupoid $`G`$, the ample semigroup $`G^a`$ is the inverse semigroup of compact, open, Hausdorff subsets of $`G`$.) Note that $`\mathrm{\Psi }(\alpha )=D_\alpha `$ for all $`\alpha I`$. A basis for the topology of $`H`$ is given by sets of the form $`D_{\alpha ,\alpha _1,\mathrm{},\alpha _n}\mathrm{\Psi }(s)`$ ($`\alpha ,\alpha _iI,\alpha _i\alpha ,sS`$).

We now specify the universal groupoid $`H=H_{}`$ of $`S=S_{}`$. The discussion parallels that for the Cuntz inverse semigroups $`S_n`$ ($`1n\mathrm{}`$) given in \[12, pp.182f.\]. We first determine the unit space $`H^0`$ of $`H`$. For $`\alpha I`$, we will write $`\alpha `$ in place of $`\overline{\alpha }`$. The context will make clear if $`\alpha `$ is being regarded as an element of $`I`$ or as a semicharacter. Recall that $`Y`$ and $`Z`$ are respectively the sets of finite and infinite paths in $``$.

###### Proposition 3.

The unit space $`H^0`$ of $`H`$ is the disjoint union:

(3.4)
$$H^0=YZ\{z\}.$$

Then the topology for $`H^0`$ is specified by:

* the singleton set $`\{z\}`$ is both open and closed in $`H^0`$;
* a neighborhood basis at $`uZ`$ is given by sets of the form $`D_\alpha =\{\mathrm{\alpha }\mathrm{\gamma }YZ:\gamma YZ\}`$ ($`\alpha Y`$) where $`\alpha `$ is an initial segment of $`u`$;
* if $`yY_f`$, then $`\{y\}`$ is an open set;
* if $`yY_{\mathrm{}}`$, then a neighborhood basis at $`y`$ is given by sets of the form $`D_{y,ye_1,\mathrm{},ye_n}`$ where $`e_1,\mathrm{}e_n`$ are edges in $``$ starting at $`r(y)`$.

###### Proof.

Let $`\chi H^0`$. If $`\chi (z)=1`$, then since $`\alpha z=z`$ for all $`\alpha I`$, we have $`\chi (\alpha )=1`$, the constant non-zero semicharacter on $`E`$. Clearly $`\chi =z`$ $`(=\overline{z})`$. The set $`\{z\}`$ is open in $`H^0`$ since it is just $`\{\chi ^{}H^0:\chi ^{}(z)=1\}`$. This gives (i).

Suppose then that $`\chi z`$. Then $`\chi (z)=0`$. Recall that $`I`$ is identified with the set of finite paths $`\alpha `$ together with the zero $`z`$, and a product of two of these paths is $`z`$ only when one path is an initial segment of the other, and in that case, the product is just the longer path. The set of paths $`\alpha `$ for which $`\chi (\alpha )=1`$ is a subsemigroup of $`I`$ and so each such path is an initial segment of any other or vice versa. There thus exists a path $`\gamma YZ`$ such that $`\chi (\alpha )=1`$ if and only if $`\gamma `$ is of the form $`\alpha \mu `$. Identifying $`\chi `$ with $`\gamma `$ gives (3.4). Note that if $`\gamma Y`$, then $`\chi =\gamma `$ ($`=\overline{\gamma }`$).

By the above, a basis for the topology on $`YZ`$ is given by sets of the form $`D_{\alpha ,\alpha _1,\mathrm{},\alpha _n}`$. Suppose that $`uZ`$ and that $`uD_{\alpha ,\alpha _1,\mathrm{},\alpha _n}`$. Then $`u`$ starts with $`\alpha `$ but not with any $`\alpha _i`$. So for some $`n`$, $`u_1\mathrm{}u_nD_{\alpha ,\alpha _1,\mathrm{},\alpha _n}`$, and so $`D_{u_1u_2\mathrm{}u_n}=\{u_1\mathrm{}u_n\gamma YZ:\gamma YZ\}D_{\alpha ,\alpha _1,\mathrm{},\alpha _n}`$. So the sets of the form $`D_\alpha `$ ($`\alpha =u_1\mathrm{}u_n`$) form a neighborhood base at $`u`$ in $`YZ`$. This gives (ii).

For (iii), if $`yY_f`$ and $`e_1,\mathrm{},e_n`$ are all of the edges starting at $`r(y)`$, then

$$\{y\}=D_yD_{ye_1}^c\mathrm{}D_{ye_n}^c=D_{y,ye_1,\mathrm{},ye_n}$$

is open in $`YZ`$.

Lastly, suppose that $`yY_{\mathrm{}}`$ and that $`y`$ is in some $`D_{\alpha ,\alpha _1,\mathrm{},\alpha _n}`$. Then $`y`$ begins with $`\alpha `$ and the $`\alpha _i`$’s all begin with $`y`$ and are longer than $`y`$. Write $`\alpha _i=ye_i\mathrm{}`$. Then $`yD_{y,ye_1,\mathrm{},ye_n}D_{\alpha ,\alpha _1,\mathrm{},\alpha _n}`$ and (iv) follows. ∎

It is instructive to specify the convergent sequences in $`YZ`$. If $`uZ`$, then $`x^nu`$ if and only if $`l(x^n)\mathrm{}`$, and for each $`i`$, $`x_i^n=u_i`$ eventually. Next, let us say that a sequence $`\{e^n\}`$ in $`E`$ is wandering if, for any $`eE`$, $`e^ne`$ eventually. Let $`\alpha =\alpha _1\alpha _2\mathrm{}\alpha _NY`$. Suppose that $`x^nYZ`$ and that $`x^n\alpha `$ for any $`n`$. Then $`x^n\alpha `$ if and only if, eventually, $`l(x^n)>l(\alpha )`$, $`x_i^n=\alpha _i`$ for $`1iN`$, and $`\{x_{N+1}^n\}`$ is wandering. Note that in this case, $`\alpha Y_{\mathrm{}}`$. It follows that each $`yY_{\mathrm{}}`$ is a limit point of $`Z`$, and so we have the following proposition.

###### Proposition 4.

The set $`Z`$ of infinite paths is dense in $`Y_{\mathrm{}}Z`$. If $`\alpha Y`$, then $`\{\alpha \}`$ is open in $`H^0`$ if and only if $`\alpha Y_f`$.

###### Theorem 1.

The universal groupoid $`H`$ for $`S`$ can be identified with the union of $`\{z\}`$ and the set of all triples of the form $`(\alpha \gamma ,l(\alpha )l(\beta ),\beta \gamma )`$ where $`\alpha ,\beta Y`$, $`\gamma YZ`$, and $`\alpha \gamma ,\beta \gamma YZ`$. Multiplication on $`H`$ is given by: $`(x,m,y)(y,n,z)=(x,m+n,z)`$ and inversion by $`(x,m,y)^1=(y,m,x)`$. The canonical map $`\mathrm{\Psi }:SH^a`$ sends $`z`$ to $`\{z\}`$ and any element $`(\alpha ,\beta )`$ to the (compact open) set $`A_{\alpha ,\beta }`$ of all triples of the form $`(\alpha \gamma ,l(\alpha )l(\beta ),\beta \gamma )`$. The locally compact groupoid $`H`$ is Hausdorff.

###### Proof.

The proof is close to that for the Cuntz semigroup $`S_n`$ in \[12, pp.182-186\]. We can restrict consideration to $`H\{z\}`$. Let $`s=(\alpha ,\beta )`$, $`xD_s`$. This means that $`x(ss^{})=x(\alpha )=1`$. If $`\alpha ^{}I`$ is such that $`x(\alpha ^{})=1,\alpha ^{}ss^{}`$, then $`\alpha ^{}=\alpha \delta Y`$, and $`\alpha ^{}s=(\alpha \delta ,\beta \delta )`$. Then $`x=\alpha \delta \gamma `$ for some $`\gamma `$ and $`(\alpha \delta \gamma ,l(\alpha \delta )l(\beta \delta ),\beta \delta \gamma )=(\alpha \delta \gamma ,l(\alpha )l(\beta ),\beta \delta \gamma )`$. So the map $`(x,s)(\alpha \delta \gamma ,l(\alpha )l(\beta ),\beta \delta \gamma )`$ is constant on the equivalence class of $`(x,s)`$ in $`H`$, and so defines a map on $`H`$. The argument reverses to give that this map is a bijection. We now prove that $`H`$ is Hausdorff, leaving the remaining verifications of the theorem to the reader.

Let $`a=(\alpha ,l(\alpha )l(\beta ),\beta )`$, $`b=(\alpha ^{},l(\alpha ^{})l(\beta ^{}),\beta ^{})`$ belong to $`H`$ with $`ab`$. If $`A_{\alpha ,\beta }A_{\alpha ^{},\beta ^{}}=\mathrm{}`$, then then we can separate $`a`$ and $`b`$ using $`A_{\alpha ,\beta },A_{\alpha ^{},\beta ^{}}`$. Suppose then that $`A_{\alpha ,\beta }A_{\alpha ^{},\beta ^{}}\mathrm{}`$. Then there exist $`\gamma ,\gamma ^{}`$ such that

$$(\alpha \gamma ,l(\alpha )l(\beta ),\beta \gamma )=(\alpha ^{}\gamma ^{},l(\alpha ^{})l(\beta ^{}),\beta ^{}\gamma ^{}).$$

Then $`l(\alpha )l(\beta )=l(\alpha ^{})l(\beta ^{})`$ and $`\alpha ,\alpha ^{}`$ and $`\beta ,\beta ^{}`$ are comparable. We can suppose that for some $`\mu `$, $`\alpha ^{}=\alpha \mu `$. Then $`\beta ^{}=\beta \nu `$ where $`l(\mu )=l(\nu )`$, and $`\nu =\mu `$ since both are initial segments of $`\gamma `$. Since $`ab`$, we have $`l(\mu )>0`$. Then $`A_{\alpha ,\beta }A_{\alpha ^{},\beta ^{}}^c`$, $`A_{\alpha ^{},\beta ^{}}`$ separate $`a`$ and $`b`$. So $`H`$ is Hausdorff. ∎

We next set $`X=Y_{\mathrm{}}ZH^0`$. Then (Proposition 3) $`X`$ is a closed invariant subset of $`H^0`$ and so is a locally compact Hausdorff space in its own right. Let $`G_{}=G`$ be the reduction of $`H`$ to $`X`$. We will call $`G`$ the path groupoid of $``$. (The groupoid $`G`$ coincides with the usual path groupoid of a graph in the locally finite case (e.g. ).) Then $`G`$ is a closed subgroupoid of $`H`$, and is an r-discrete groupoid in its own right with counting measures giving a left Haar system. For $`\alpha ,\beta Y`$, we define $`A^{}(\alpha ,\beta )=A(\alpha ,\beta )G`$ and $`D_\alpha ^{}=D_\alpha X`$.

We now relate the representations of $`G`$ to those of $`H`$.

###### Proposition 5.

Each representation $`\sigma `$ of $`C_c(G)`$ determines a representation $`\sigma ^{}`$ of $`C_c(H)`$ by: $`\sigma ^{}(f)=\sigma (fG)`$. A representation $`\mathrm{\Pi }`$ of $`C_c(H)`$ is of the form $`\sigma ^{}`$ for some representation $`\sigma `$ of $`C_c(G)`$ if and only if

(3.5)
$$\mathrm{\Pi }(\chi _{\{z\}})=0=\mathrm{\Pi }(\chi _{\{\alpha \}})$$

for all $`\alpha Y_f`$.

###### Proof.

If $`\sigma `$ is a representation of $`C_c(G)`$ on a Hilbert space $``$ then $`\sigma ^{}:C_c(G)B()`$ is a -homomorphism. Since the homomorphism $`ffG`$ from $`C_c(H)`$ into $`C_c(G)`$ is continuous for the $`I`$-norm, it immediately follows that $`\sigma ^{}`$ is $`I`$-norm continuous and so is a representation of $`C_c(H)`$. It is obvious from the definition that $`\sigma ^{}`$ satisfies (3.5) (with $`\sigma ^{}`$ in place of $`\mathrm{\Pi }`$).

Conversely, suppose that $`\mathrm{\Pi }:C_c(H)B()`$ is a representation satisfying (3.5). By the proof of \[12, Theorem 3.1.1\], the representation $`\mathrm{\Pi }`$ extends to a continuous representation $`\stackrel{~}{\mathrm{\Pi }}`$ of $`(B_c(H),._I)`$ where $`B_c(H)`$ is the convolution algebra of bounded Borel functions on $`H`$ with compact supports. Let $`\sigma `$ be the restriction of $`\stackrel{~}{\mathrm{\Pi }}`$ to $`C_c(G)B_c(H)`$. Then $`\sigma `$ is a representation (a priori possibly degenerate) of $`C_c(G)`$ on $``$. Let $`fC_c(H)`$ and $`U`$ be an open subset of $`H`$ with compact closure and which contains the support of $`f`$. We have to show that $`\mathrm{\Pi }(f)=\stackrel{~}{\mathrm{\Pi }}(fG)`$ $`(=\sigma (fG)).`$ Let $`\xi `$. As in \[12, Theorem 3.1.1\], there exists a positive regular Borel measure $`\mu `$ on $`H`$ such that for all $`gB_c(H)`$ with $`supp(g)U`$, we have

(3.6)
$$\stackrel{~}{\mathrm{\Pi }}(g)\xi ,\xi =_Ug𝑑\mu .$$

Now $`HG`$ is the reduction of $`H`$ to $`Y_f\{z\}`$ and is countable. For $`aHG`$, we have $`a=ar(a)`$ with $`r(a)Y_f\{z\}`$. So $`\mathrm{\Pi }(\chi _{\{a\}})=\mathrm{\Pi }(\chi _{\{a\}})\mathrm{\Pi }(\chi _{\{r(a)\}})=0`$ by (3.5). From (3.6), $`\mu (\{a\})=0`$. Since $`HG`$ is countable, it follows that $`\mu (HG)=0`$, and for $`fC_c(G)`$,

$$\stackrel{~}{\mathrm{\Pi }}(f)\xi ,\xi =_UfGd\mu =\stackrel{~}{\mathrm{\Pi }}(fG)\xi ,\xi ,$$

and $`\mathrm{\Pi }(f)=\sigma (fG)`$. ∎

The requirement (3.5) of the preceding proposition can be replaced by the corresponding requirement in which $`\alpha Y_f`$ is replaced by $`vV_f`$:

(3.7)
$$\mathrm{\Pi }(\chi _{\{z\}})=0=\mathrm{\Pi }(\chi _{A(v,v)})\underset{s(e)=v}{}\mathrm{\Pi }(\chi _{A(e,e)}).$$

To show this, $`\mathrm{\Pi }(\chi _{A(v,v)})_{s(e)=v}\mathrm{\Pi }(\chi _{A(e,e)})=\mathrm{\Pi }(\chi _{\{v\}})`$ and one way follows trivially since $`vY_f`$. For the other way, we just use the fact that $`\chi _{\{\alpha \}}=\chi _{\{\alpha \}}\chi _{\{r(\alpha )\}}`$ and the fact that $`\mathrm{\Pi }`$ is a homomorphism.

We now give the definition of a representation of the graph $``$. The definition is taken from . Note that in the $`𝒪_{\mathrm{}}`$ case, condition (iii) below assumes the form (\[3, p.174\]) $`_{i=1}^rS_iS_i^{}1`$ for all $`r1`$. Further, $`1`$ is just $`P_v`$ where $`v`$ is the sole vertex of the directed graph which is the infinite bouquet of circles.

###### Definition 1.

A representation of $``$ on a Hilbert space $``$ is given by a family $`\{P_v:vV\}`$ of mutually orthogonal projections, and a family $`\{S_e:eE\}`$ of partial isometries such that the family of projections $`S_eS_e^{}`$ are mutually orthogonal and:

1. $`S_e^{}S_e=P_{r(e)}`$ for all $`eE`$;
2. if $`vV_f`$, then

(3.8)
$$P_v=\underset{s(e)=v}{}S_eS_e^{};$$
3. $`P_{s(e)}S_eS_e^{}=S_eS_e^{}`$ for all $`eE`$.

By multiplying both sides of (i) on the right by $`S_e^{}`$ we get

(3.9)
$$S_e^{}=P_{r(e)}S_e^{}.$$

Similarly, using (iii), we get that

(3.10)
$$P_{s(e)}S_e=S_e.$$

In the following, representations of graphs and inverse semigroups are assumed to be non-degenerate in the obvious sense. (Representations of locally compact groupoids are “non-degenerate” almost by definition.)

###### Theorem 2.

There are natural one-to-one correspondences between: (a) the class $`_{}`$ of representations of $``$; (b) the class $`_S`$ of representations of $`S`$ that vanish on $`z`$ and on elements of the form $`v_{s(e)=v}(e,e)`$ for all $`vV_f`$; (c) the class $`_G`$ of representations of the locally compact groupoid $`G`$.

###### Proof.

Let $`Q=\{\{P_v\},\{S_e\}\}_{}`$ and be realized on a Hilbert space $``$. For $`\alpha =e_1e_2\mathrm{}e_nY`$, define $`S_\alpha =S_{e_1}S_{e_2}\mathrm{}S_{e_n}`$. (i) above generalizes to:

(3.11)
$$S_\alpha ^{}S_\alpha =P_{r(\alpha )}.$$

For example, if $`\alpha =e_1e_2`$, then using (i), (iii) and (3.10), we have $`S_\alpha ^{}S_\alpha =S_{e_2}^{}[S_{e_1}^{}S_{e_1}]S_{e_2}=S_{e_2}^{}P_{s(e_2)}S_{e_2}=(S_{e_2}^{}S_{e_2})=P_{r(e_2)}=P_{r(\alpha )}.`$ It immediately follows from (3.10) and (3.9) that:

(3.12)
$$P_{s(\alpha )}S_\alpha =S_\alpha ,P_{r(\alpha )}S_\alpha ^{}=S_\alpha ^{}.$$

Define a -map $`\mathrm{\Pi }:SB()`$ by:

$$\mathrm{\Pi }(v)=P_v,\mathrm{\Pi }(\alpha ,\beta )=S_\alpha S_\beta ^{},\mathrm{\Pi }(z)=0.$$

Then $`\mathrm{\Pi }`$ is a -homomorphism. The proof is simple. One checks that $`\mathrm{\Pi }(st)=\mathrm{\Pi }(s)\mathrm{\Pi }(t)`$ for the different kinds of product using (3.11) and (3.12). For example, to prove that $`\mathrm{\Pi }(\alpha ,\beta \mu )=\mathrm{\Pi }(\alpha ,\alpha ^{}\mu )\mathrm{\Pi }(\alpha ^{},\beta )`$, one argues:
$`\mathrm{\Pi }(\alpha ,\alpha ^{}\mu )\mathrm{\Pi }(\alpha ^{},\beta )=S_\alpha S_\mu ^{}S_\alpha ^{}^{}S_\alpha ^{}S_\beta ^{}=S_\alpha S_\mu ^{}P_{r(\alpha ^{})}S_\beta ^{}=S_\alpha S_\mu ^{}S_\beta ^{}=\mathrm{\Pi }(\alpha ,\beta \mu ).`$ Since $`\mathrm{\Pi }(z)=0`$, $`S_eS_e^{}=\mathrm{\Pi }((e,e))`$ and $`\mathrm{\Pi }`$ vanishes on elements of the form $`(v_{s(e)=v}(e,e))`$ for $`vV_f`$, it follows from (3.8) that $`\mathrm{\Pi }_S`$.

Conversely, any $`\mathrm{\Pi }^{}_S`$ determines an element of $`_{}`$ by taking $`P_v=\mathrm{\Pi }^{}(v,v),S_e=\mathrm{\Pi }^{}(e,r(e))`$. Since $`S_eS_e^{}=\mathrm{\Pi }^{}((e,r(e))(r(e),e))=\mathrm{\Pi }^{}(e,e)`$, (ii) of Definition 1 follows. (i) and (iii) follow since $`\mathrm{\Pi }^{}`$ is a -homomorphism on $`S`$. This establishes the correspondence between the representations of (a) and (b).

The correspondence between the representations in (b) and (c) is implemented by using the natural bijection between representations of $`S`$ and $`(H,\mathrm{\Psi })`$ (the universal groupoid of $`S`$) established in \[12, Ch.4\]. We now recall what this bijection is.

Let $`\rho `$ be a representation of $`S`$ on a Hilbert space $``$. Then there is a representation $`\mathrm{\Pi }`$ of $`C_c(H)`$ determined by:

$$\mathrm{\Pi }(\chi _{\mathrm{\Psi }(s)})=\rho (s)$$

for all $`sS`$ where $`\mathrm{\Psi }(s)`$ is given in Theorem 1. Further, the map $`\rho \mathrm{\Pi }`$ is one-to-one and onto. It remains then to show that the representations $`\rho `$ of $`S`$ that satisfy the conditions of (b) correspond to the representations $`\mathrm{\Phi }`$ of $`C_c(G)`$. This follows by Proposition 5 (and the remark following that proposition), and so we have established the correspondence between $`_S`$ and $`_G`$. ∎

We now translate (a), (b) and (c) of the preceding theorem into $`C^{}`$-algebra terms. The $`C^{}`$-algebra determined by the groupoid representations of (c) is just the groupoid $`C^{}`$-algebra $`C^{}(G)`$. The $`C^{}`$-algebra associated with (b) is obtained on the semigroup algebra $`\mathrm{}^1(S)`$ as follows. Every representation $`\mathrm{\Pi }`$ of $`S`$ gives a bounded representation $`\mathrm{\Pi }`$ of $`\mathrm{}^1(S)`$ in the natural way, and $`C^{}(S)`$ is just the enveloping $`C^{}`$-algebra of $`\mathrm{}^1(S)`$ obtained by taking the biggest $`C^{}`$-norm coming from such $`\mathrm{\Pi }`$’s. The $`C^{}`$-algebra that we want here, which we will denote by $`C_0^{}(S)`$, is obtained in the same way only using $`\mathrm{\Pi }`$’s for which $`\mathrm{\Pi }(z)=0=\mathrm{\Pi }(v_{s(e)=v}(e,e))`$ for all $`vV_f`$. It is easy to show that $`C_0^{}(S)`$ is the enveloping $`C^{}`$-algebra of $`\mathrm{}^1(S)/I`$, where $`I`$ is the closed ideal of $`\mathrm{}^1(S)`$ generated by elements of the form $`z`$ and $`v_{s(e)=v}(e,e)`$ ($`vV_f`$).

We take $`C^{}()`$ to be the universal $`C^{}`$-algebra for the representations of $``$. By the above, we then obtain the following corollary to Theorem 2.

###### Corollary 1.

$`C^{}()C_0^{}(S)C^{}(G).`$

In the case of $`𝒪_{\mathrm{}}`$, the graph $``$ is a bouquet of circles $`\{e_n:n1\}`$ (one vertex $`v`$). The inverse semigroup $`S_{}`$ in this case is the set of pairs $`(\alpha ,\beta )`$ where $`\alpha ,\beta `$ are finite words in $``$ together with the identity $`v`$ and zero $`z`$. Then $`G`$ is the groupoid $`O_{\mathrm{}}`$ of \[12, p.184f.\].

Now let $``$ be a general directed graph and $`S=S_{}`$ as before. For the purposes of the next section, we need to use a related inverse semigroup $`S^n`$ with associated groupoid $`G^n`$. Here, $`n`$, $`Y^n=\{yY:0l(y)n\}`$ and $`S^n`$ is the inverse subsemigroup of $`S`$ given by:

$$S^n=\{(\alpha \mu ,\beta \mu )S:\alpha ,\beta Y^n,l(\alpha )=l(\beta )\}\{z\}.$$

It is easy to check that $`S^n`$ is an inverse subsemigroup of $`S`$ and that $`I(S^n)=I(S)`$. We now describe the universal groupoid $`H^n`$ of $`S^n`$ and the related groupoid $`G^n`$. The proofs of the assertions below are very similar to the corresponding proofs for $`S`$, and are left to the reader.

The universal groupoid $`H^n`$ for $`S^n`$ can be identified with the union of $`\{z\}`$ and the set of all pairs of the form $`(\alpha \gamma ,\beta \gamma )`$ where $`\alpha ,\beta Y^n`$, $`l(\alpha )=l(\beta )`$, $`\gamma YZ`$, and $`\alpha \gamma ,\beta \gamma YZ`$. Identify $`(\alpha \gamma ,\beta \gamma )S^n`$ with $`(\alpha \gamma ,0,\beta \gamma )H`$. Then $`H^n`$ is a subgroupoid of $`H`$ with the same unit space, and the multiplication and inversion for $`H^n`$ are just those that $`H^n`$ inherits as a subgroupoid of $`H`$. The canonical map $`\mathrm{\Psi }^n:S^n(H^n)^a`$ is just the restriction of the map $`\mathrm{\Psi }`$ of Theorem 1 to $`S^n`$. The groupoid $`G^n`$ is defined to be the reduction of $`H^n`$ to $`X`$.

The principal transitive equivalence relation on a (discrete) set with $`k`$ elements ($`1k\mathrm{}`$) is denoted by $`T_k`$. (In less elaborate language, this is the equivalence relation for which any element of the set is equivalent to any other.) For the following definitions, see \[14, p.123\]. An r-discrete groupoid is called elementary if it is isomorphic to the disjoint union of a sequence of groupoid products of the form $`T_k\times Q`$ for some $`k`$ and some locally compact space $`Q`$, and is called AF if its unit space is totally disconnected and it is the inductive limit of a sequence of elementary groupoids.

###### Proposition 6.

The locally compact groupoid $`G^n`$ is an AF-groupoid.

###### Proof.

Obviously, the unit space $`G^0`$ of $`G^n`$ is totally disconnected. Enumerate $`E`$ as $`e_1,e_2,\mathrm{}`$, and let $`N`$. Let $`F=\{e_1,\mathrm{},e_N\}`$. For $`0rn`$, let $`A_r`$ be the set of all finite paths of the form $`e_{p_1}\mathrm{}e_{p_r}`$ where each $`e_{p_i}F`$. We take $`A_0=s(F)`$. Let $`B_r`$ be the set of pairs $`(\alpha \gamma ,\beta \gamma )G^n`$ where $`\alpha ,\beta A_r`$ and $`\gamma `$ is arbitrary. Clearly, $`B_r`$ is a compact, open subgroupoid of $`G^n`$ (being a finite union of $`\mathrm{\Psi }^n(\alpha ,\beta )`$’s). For each $`vr(F)`$, let

$$X^v=\{\gamma X:s(\gamma )=v\}.$$

Then $`X^v=A(v,v)`$ is a compact, open subset of $`X`$. Note that if $`\alpha ,\beta A_r`$ with $`r(\alpha )=v=r(\beta )`$, then $`(\alpha \gamma ,\beta \gamma )B_r`$ if and only if $`\gamma X^v`$. Let

$$L^N=_{r=0}^nB_r.$$

Then $`L^N`$ is also a compact, open subgroupoid of $`G^n`$. We will show that $`L^N`$ is elementary.

To this end we “disjointify” the $`B_r`$’s. Let $`C_r`$ be the unit space $`B_r^0`$ of $`B_r`$. The elements of $`C_r`$ are of the form $`\alpha `$$`\gamma `$ for $`\alpha A_r,\gamma X^{r(\alpha )}`$. Clearly $`C_nC_{n1}\mathrm{}C_0=\{xX:s(x)A_0\}`$. Let $`C_n^{}=C_n`$ and, for $`0r<n`$, let $`C_r^{}=C_rC_{r+1}`$. Let

$$B_r^{}=\{(\alpha \gamma ,\beta \gamma )B_r:\alpha ,\beta A_r,\alpha \gamma ,\beta \gamma C_r^{}\}.$$

Then $`L^N`$ is the disjoint union of the compact, open subgroupoids $`B_r^{}`$ of $`G^n`$. The fact that $`L^N`$ is elementary will follow once we have shown that each $`B_r^{}`$ is elementary. To this end, fix $`r`$, and for each $`vr(F)`$, let

$$W_v=\{(\alpha \gamma ,\beta \gamma )B_r^{}:\alpha ,\beta A_r,v=r(\alpha )=r(\beta )=s(\gamma )\}.$$

Then $`B_r^{}`$ is the disjoint union of the compact, open subgroupoids $`W_v`$, and for each $`v`$, $`W_v`$ is isomorphic to $`T_{k_v}\times (X^v)^{}`$, where $`(X^v)^{}`$ is an open subset of $`X^v`$, and $`k_v`$ is the number of $`\alpha `$’s in $`A_r`$ with $`r(\alpha )=v`$ and such that $`\alpha \gamma C_r^{}`$ for some $`\gamma `$. So $`B_r^{}`$, and hence $`L^N`$, is elementary.

We now claim that $`G^n`$ is the inductive limit of the $`L^N`$’s and hence is an AF-groupoid. To this end (cf. \[14, pp.122-3\]), $`G^n`$ is a union of the increasing sequence of elementary, open subgroupoids $`L^N`$. It is easily checked that a set $`VG^n`$ is open in the inductive limit topology if and only if it is open in $`G^n`$, so that the inductive limit topology on $`G^n`$ coincides with the given topology on $`G^n`$. Further, the counting measure left Haar system on $`G^n`$ is compatible with the counting measure left Haar systems on the $`L^N`$’s. So $`G^n`$ is the inductive limit of the $`L^N`$’s. ∎

At the $`S^n`$ level (for $`𝒪_{\mathrm{}}`$), Cuntz observes (\[3, 1.5\]) that $`^{\mathrm{}}`$ is an AF $`C^{}`$-algebra.

## 4. Graph groupoids are amenable

In , Cuntz showed that $`𝒪_n`$ ($`n2`$) is isomorphic to the crossed product of an AF-algebra by an automorphism, cut down by a projection. It follows () that $`𝒪_n`$ is therefore nuclear (=amenable). Cuntz used a separate argument to deal with the case $`n=\mathrm{}`$. Renault (\[14, p.138f.\]) showed that the Cuntz groupoids $`O_n`$ ($`n<\mathrm{}`$) are amenable as locally compact groupoids. (The amenability of $`𝒪_n`$ then follows.) The groupoid case when $`n=\mathrm{}`$ remained unclear.

Kumjian, Pask, Raeburn and Renault () adapted Renault’s original argument to establish the amenability of the groupoid $`G=G_{}`$ when $``$ is locally finite. In this section, we further adapt the argument of  to show that $`G`$ is amenable in complete generality. In particular, this covers the groupoid case for $`O_{\mathrm{}}`$.

As in , we assume initially that every vertex receives an edge. For each $`vV`$, fix an edge $`e(v)E`$ for which $`r(e(v))=v`$. Next we consider the following space $`𝔛`$ of two-sided paths. The elements of $`𝔛`$ are sequences $`x=\{x_i\}`$ of edges, where $`\mathrm{}<i<k\mathrm{}`$ with $`k`$ depending on $`x`$ and $`r(x_i)=s(x_{i+1})`$ whenever that makes sense. So the sequence $`x`$ is infinite to the left, and may or may not be infinite to the right. If the sequence $`x`$ is finite to the right, then $`r(x)`$ makes sense in the obvious way, and we require that $`r(x)V_{\mathrm{}}`$. Define a function $`h:𝔛\{\mathrm{}\}`$ as follows: $`h(x)=\mathrm{}`$ if $`x`$ is infinite to the right, and otherwise, is the largest $`i`$ for which $`x_i`$ is defined.

For each $`n`$, we now define a subset $`P_n`$ of $`𝔛`$ by specifying that $`xP_n`$ if and only if $`h(x)(n1)`$ and $`x_i=e(s(x_{i+1}))`$ for all $`i<n`$. If $`h(x)=n1`$, then we require $`x_{n1}`$ to be some $`e(v)`$. The set of $`x`$’s in $`P_n`$ for which $`h(x)=n1`$ can be identified with $`V_{\mathrm{}}`$ by sending $`x`$ to $`r(x)`$. Note that $`P_nP_{n1}`$.

Let $`n1`$. There is a natural bijection $`f_n:P_nX=G^0`$ defined by translating to the right by $`n+1`$ and chopping off what is to the left of $`1`$. Precisely, $`f_n(x)_m=x_{n+m1}`$ if $`h(x)>(n1)`$ and $`f_n(x)=r(x)`$ when $`h(x)=n1`$. We give $`P_n`$ the topology for which $`f_n`$ is a homeomorphism.

Note that $`P_n`$ is an open subset of $`P_{n1}`$. Indeed $`f_{n1}(P_n)`$ is the (open) set of elements of $`X`$ of the form $`e(s(x))x`$ for some $`xX`$.

Let $`R_n`$ be the equivalence relation on $`P_n`$ defined by: $`(x,y)R_n`$ if and only if $`h(x)=h(y)`$, and if $`h(x)=n1`$ then $`r(x)=r(y)`$, while if $`h(x)>n`$, then $`x_i=y_i`$ for $`i>n`$. Note that when $`h(x)=n1`$, then $`xR_ny`$ if and only if $`x=y`$. Note also that if $`h(x)>n`$, then since $`x_{n+1}=y_{n+1}`$, we have $`r(x_n)=s(x_{n+1})=s(y_{n+1})=r(y_n)`$. The unit space of $`R_n`$ is $`P_n`$. Of course, we give $`R_n`$ the product topology that it inherits as a subset of $`P_n\times P_n`$.

###### Proposition 7.

The equivalence relation groupoid $`R_n`$ is an AF groupoid.

###### Proof.

The map $`(x,y)(f_n(x),f_n(y))`$ is an isomorphism of locally compact groupoids from $`R_n`$ onto $`G^{2n+1}`$ and therefore is an AF groupoid by Proposition 6. ∎

Clearly, $`R_n`$ is an open subset of $`R_{n+1}`$, and the topology on $`R_n`$ is the relative topology that it inherits as a subset of $`R_{n+1}`$. Also, the canonical left Haar system $`\{\lambda _{n+1}(u)\}`$ (counting measure on the $`(R_{n+1})^u`$’s) gives by restriction the left Haar system $`\{\lambda _n(u)\}`$ on $`R_n`$.

It follows as in \[14, p.122\] that $`R=_{n1}R_n`$ is an r-discrete groupoid in the inductive limit topology. (As pointed out in , this notion of inductive limit is more general than the r-discrete case considered by Renault inasmuch as the unit spaces of the $`R_n`$’s are increasing rather than being fixed.) It also follows that $`R`$ is amenable since each $`R_n`$ is AF and therefore amenable (\[14, p.123\]).

The argument for the amenability of $`G`$ now proceeds almost exactly as in  (to which the reader is referred for further details). We will be content with a sketch of the argument in the present context to indicate the minor changes needed.

Let $`P=_1^{\mathrm{}}P_n`$ be the unit space of $`R`$. Then $`P`$ is the inductive limit of the $`P_n`$’s. The left shift map $`h`$ on $`P`$, where $`h(\{x_i\})_j=x_{j+1}`$, is a homeomorphism on $`P`$ since it maps $`P_n`$ homeomorphically onto $`P_{n1}`$, and it induces a homeomorphism $`\sigma `$ on $`R`$, where $`\sigma (u,v)=(h(u),h(v))`$, which is also a groupoid homomorphism. One then considers the semi-direct product $`R\times _\sigma `$. This groupoid consists () of triples $`(u,v,k)R\times `$ with $`r(u,v,k)=u,s(u,v,k)=h^kv`$, inverse by $`(u,v,k)^1=(\sigma ^k(v,u),k)`$ and product by:

$$(u,h^k(p),k)(p,q,l)=(u,h^k(q),k+l).$$

Then $`R\times _\sigma `$ is amenable (\[14, p.96\]) and hence (\[14, p.92\]) so is its reduction $`G^{}`$ to the closed subset $`P_1`$ of $`P`$.

We now claim that $`G^{}`$ is isomorphic to the graph groupoid $`G`$ (so that $`G`$ is also amenable). Firstly, the unit space $`P_1`$ of $`G^{}`$ can be identified with $`X`$ by sending $`\mathrm{}e(s(z_1))z_1z_2\mathrm{}`$ to $`z=z_1z_2\mathrm{}`$. The natural isomorphism $`F:GG^{}`$ is given by (cf. \[11, Proposition 4.4\]):

$$F(xz,k,yz)=(xz,h^k(yz),k).$$

Here, $`x=x_1\mathrm{}x_r,y=y_1\mathrm{}y_{rk}`$ and $`xz,yz`$ on the right-hand side are abbreviations for $`\mathrm{}e(s(x_1))xz,\mathrm{}e(s(y_1))yzP_1`$.

Checking that $`F`$ is a groupoid isomorphism is straighforward. That $`F`$ is a homeomorphism follows effectively from the way that we defined the topology of $`P_n`$ in terms of $`X`$. To check that $`F`$ is a homomorphism, one argues ($`k=l(x)l(y),l=l(y_1)l(a),yz=yy^{}z^{}=y_1z^{}`$):

$`F(xz,k,yz)F(yz,l,az^{})`$ $`=`$ $`(xz,h^k(yz),k)(yz,h^l(az^{}),l)`$
$`=`$ $`(xz,h^k[h^l(az^{})],kl)`$
$`=`$ $`(xz,h^{(k+l)}(az^{}),(k+l))`$
$`=`$ $`F((xz,k,yz)(y_1z^{},l,az^{})).`$
The other facts to be checked are left to the reader.

This deals with the case where every vertex $`v`$ is $`r(e)`$ for some $`eE`$. For the general case, one considers a larger graph $`^{}`$ obtained by adding an infinite left tail to each $`vV`$ for which $`r^1(\{v\})=\mathrm{}`$, applies the preceding result to $`^{}`$ and performs a reduction to obtain that $`G`$ is amenable. (Note that $`G^0=G()^0`$ is a closed subset of $`G(^{})^0`$.) We therefore have:

###### Theorem 3.

For any directed graph $``$, the graph groupoid $`G`$ is amenable.

## 5. The simplicity of $`C^{}()`$

In this section we will use the groupoid $`G`$ to obtain conditions sufficient for $`C^{}()`$ to be simple. As discussed in the Introduction, the result obtained (Theorem 4) is effectively due to W. Szymanski who also proved the converse. (It seems likely that the approach to the converse for the row finite case in  can be adapted to apply within the groupoid context of the present paper.)

For $`vV`$, a loop based at $`v`$ is a finite path $`\alpha =e_1\mathrm{}e_n`$ such that $`r(\alpha )=s(\alpha )=v`$ and $`r(e_i)v`$ for $`1i<l(\alpha )`$. The subsets $`V_0,V_1,V_2`$ of $`V`$ are the sets of vertices $`v`$ such that there are respectively no loops based at $`v`$, exactly one loop based at $`v`$ and at least two distinct loops based at $`v`$. The graph $``$ is said to satisfy condition (K) (\[11, §6\]) if $`V_1=\mathrm{}`$.

Recall that a locally compact groupoid $`H`$ is called essentially principal (\[14, p.100\]) if whenever $`F`$ is a closed invariant subset of $`H^0`$, then the set of $`u`$’s in $`F`$ with trivial isotropy group is dense in $`F`$. It is shown in \[11, Proposition 6.3\] that if $``$ is row finite and satisfies condition (K), then $`G`$ is essentially principal. We now show that for general $``$, $`G`$ is essentially principal if and only if $``$ satisfies condition (K).

###### Proposition 8.

The r-discrete groupoid $`G`$ is essentially principal if and only if $``$ satisfies condition (K).

###### Proof.

Suppose that $``$ satisfies condition (K). Let $`F`$ be a closed invariant subset of $`G`$. Note that any finite path $`yY`$ has trivial isotropy. So we need only consider infinite paths. The proof of \[11, Proposition 6.3\] then goes through verbatim to give that $`G`$ is essentially principal.

Conversely, suppose that $`G`$ is essentially principal and that $`V_1\mathrm{}`$. Let $`vV_1`$ and $`\alpha `$ be the loop in $``$ based at $`v`$. Let

$$C=\{zZ:zv\}.$$

Note that $`\gamma =\alpha \alpha \mathrm{}`$ belongs to $`C`$. Let $`F=\overline{C}`$, the closure of $`C`$ in $`X`$. We claim that $`F`$ is a closed invariant subset of $`X`$.

Trivially, $`F`$ is closed. To prove invariance, let $`\{z^i\}`$ be a sequence in $`C`$ and $`z^ixX`$. Suppose that $`x`$ is equivalent to $`yY`$. Either $`l(x)=\mathrm{}`$ or $`l(x)<\mathrm{}`$. Suppose first that $`l(x)=\mathrm{}`$. Then for some $`\alpha ^{}`$ and some $`zZ`$, we have $`x=\alpha ^{}z,y=\beta z`$. Then eventually, every $`z^i=\alpha ^{}w^i`$, and so $`\beta w^iC`$ and $`\beta w^iy`$. So $`yF`$. If $`l(x)<\mathrm{}`$, then $`r(x)=r(y)`$, and a similar argument gives that $`yF`$. So $`F`$ is invariant. Note that if $`xF`$, then $`xv`$ for all $`v`$ (so that $`FZ=C`$).

We will contradict the assumption $`V_1\mathrm{}`$ by showing that if $`xF`$ and $`s(x)=v`$, then $`x=\gamma `$. (For then any sequence in $`F`$ converging to $`\gamma `$ will eventually coincide with $`\gamma `$ and so eventually, the terms of the sequence will not have trivial isotropy.) We can suppose that $`xC`$ since each $`x^{}F`$ of finite length and with $`s(x^{})=v`$ is the limit of a sequence of such infinite paths $`x`$. For each $`n`$, there is a path $`y`$ starting and finishing at $`v`$ obtained by following $`x`$ until we reach $`r(x_n)`$ and then taking a path from $`r(x_n)`$ to $`v`$. Since $`\alpha `$ is the only loop based at $`v`$, $`y`$ is of the form $`\alpha \alpha \mathrm{}\alpha `$. It follows every initial segment of $`x`$ is an initial segment of $`\gamma `$ and so $`x=\gamma `$. ∎

The groupoid $`G`$ is called minimal (\[14, p.35\]) if the only open invariant subsets of $`G^0`$ are $`G^0`$ and the empty set. Since $`G`$ is amenable, we have $`C^{}(G)=C_{red}^{}(G)`$ (\[14, p.92\]). Assume that $``$ satisfies condition (K). Then by the above, the r-discrete groupoid $`G`$ is essentially principal. So by \[14, Proposition 2.4.6, p.103\], we have that $`C^{}(G)`$ is simple if and only if $`G`$ is minimal. We now give a groupoid proof of the simplicity result for $`C^{}()`$ (\[19, Theorem 12\]).

###### Theorem 4.

The graph $`C^{}`$-algebra $`C^{}()`$ is simple if (a), (b) and (c) hold, where:

* $``$ has property (K);
* $``$ is cofinal () in the sense that given $`vV`$ and $`zZ`$, there exists an $`n`$ such that $`vr(z_n)`$;
* if $`vV`$ and $`wV_{\mathrm{}}`$, then there is a path from $`v`$ to $`w`$.

###### Proof.

Suppose that $`G`$ satisfies (a), (b) and (c). By the preceding comments, we just need to show that $`G`$ is minimal.

Let $`U\mathrm{}`$ be an open invariant subset of $`X`$. By Proposition 4, $`UZ\mathrm{}`$. By considering a neighborhood in $`X`$ of some $`zUZ`$ and using (ii) of Proposition 3, we have that for some $`\alpha `$, $`D_\alpha ^{}U`$. Let $`zZ`$. By (b), there is a path $`\beta `$ from $`r(\alpha )`$ to $`r(z_n)`$ for some $`n`$. Then $`z^{}=\alpha \beta z_{n+1}\mathrm{}D_\alpha ^{}U`$. Since $`z^{}`$ is tail equivalent to $`z`$ and $`U`$ is invariant, we have $`zU`$. Next let $`yY_{\mathrm{}}`$. By (c), there is a path $`\beta ^{}`$ from $`r(\alpha )`$ to $`r(y)`$. Then $`\alpha \beta ^{}`$ is equivalent to $`y`$, and $`\alpha \beta ^{}U`$. So $`yU`$. So $`U=ZY_{\mathrm{}}=X`$ and $`G`$ is minimal. ∎


text:
# The cosmological constant and the paradigm of adiabaticity

## 1 Introduction

There are now at least 5 completely independent observations which consistently point toward a majority of the energy-density of the Universe being in the form of a “cosmological constant”, $`\mathrm{\Omega }_\mathrm{\Lambda }`$. Those observations are: cosmic microwave background anisotropies (CMB), large scale structure (LSS), supernovae typ IA, strong and weak gravitational lensing. The very nature of this mysterious component remains unknown, and the so called “smallness problem” (i.e. why $`𝒪(\mathrm{\Omega }_\mathrm{\Lambda })1`$ and not $`\mathrm{\Omega }_\mathrm{\Lambda }>10^{58}`$ as expected from particle physics arguments) is still unsolved. It is therefore important to test the robustness of results indicating a non-vanishing cosmological constant with respect to non-standard physics. One possibile extension of the “concordance model” is given by non-adiabatic initial conditions for the cosmological perturbations, i.e. isocurvature modes. Another test is the use of a different statistical approach then the usual Bayesian one, namely the frequentist method. We discuss this points in the next section, and present their application to the cosmological constant problem in section 3. Section 4 is dedicated to our conclusions.

## 2 Testing the assumption of adiabaticity

### 2.1 Statistics

Most of the recent literature on cosmological parameters estimation uses Bayesian inference: the Maximum Likelihood (ML) principle states that the best estimate for the unknown parameters is the one which maximizes the likelihood function. Therefore, in the grid-based method, one usually minimizes the $`\chi ^2`$ over the parameters which one is not interested in. Then one defines $`1\sigma `$, $`2\sigma `$ and $`3\sigma `$ likelihood contours around the best fit point, as the locus of models within $`\mathrm{\Delta }\chi ^2\chi _{\mathrm{ML}}^2=2.30`$, $`6.18`$, $`11.83`$ away from the ML value for the joint likelihood in two parameters, $`\mathrm{\Delta }=1`$, $`4`$, $`9`$ for the likelihood in only one parameter. Based on Bayes’ Theorem, likelihood intervals measure our degree of belief that the particular set of observations used in the analysis is generated by a parameter set belonging to the specified interval statistics . Since Bayesian likelihood contours are drawn with respect to the ML point, if the best fit value for the $`\chi ^2`$ is much lower then what one would expect statistically for Gaussian variables (i.e. $`\chi ^2/F1`$, were $`F`$ denotes the number of degrees of freedom, dof), Bayesian contours will underestimate the real errors.

The grid-based parameter estimation method can however be used for a determination of true exclusion region (frequentist approach). The Bayesian and frequentist methods can give quite different errors on the parameters, since the meaning of the confidence intervals is different. The frequentist approach answers the question: What is the probability of obtaining the experimental data at hand, if the Universe has some given cosmological parameters? To the extent to which the $`C_{\mathrm{}}`$’s can be approximated as Gaussian variables, the quantity $`\chi ^2`$ is distributed according to a chi-square probability distribution with $`F=NM`$ dof, where $`N`$ is the number of independent (uncorrelated) experimental data points and $`M`$ is the number of fitted parameters. Since the chi-square distribution, $`P^{(F)}`$, is well known, one can readily estimate confidence intervals, by finding the quantile of $`P^{(F)}`$ for the chosen (1 tail) confidence level. The so obtained exclusion regions do not rely on the ML point. On the other hand, they are rigorously correct only if the assumption of Gaussianity holds, and the number of dof is precisely known. In general one should keep in mind that frequentist contours are less stringent than likelihood (Bayesian) contours.

### 2.2 Dependence on initial conditions

CMB anisotropies are sensitive not only to the matter-energy content of the universe, but also to the type of initial conditions (IC) for cosmological perturbations. Initial conditions are set at very early times, and determining them gives precious hints on the type of physical process which produced them. In the context of the inflationary scenario, the type of IC is related to the number of scalar fields in the very early universe and to their masses. For instance, the simplest inflationary model, namely with only one scalar field, predicts adiabatic (AD) initial conditions. In this case, the initial density contrast for all components (baryons, CDM, photons and neutrinos) is the same, up to a constant:

$$\frac{\delta \rho _b}{\rho _b}=\frac{\delta \rho _c}{\rho _c}=\frac{3}{4}\frac{\delta \rho _\gamma }{\rho _\gamma }=\frac{3}{4}\frac{\delta \rho _\nu }{\rho _\nu }\mathrm{\Delta }_{AD}\text{(AD).}$$

This excites a cosine oscillatory mode in the photon-baryon fluid, which induces a first peak at $`\mathrm{}220`$ in the angular power spectrum for a flat universe. Another possibility are CDM isocurvature initial conditions. Then the total energy-density perturbation vanishes (setting $`\frac{\delta \rho _b}{\rho _b}=\frac{\delta \rho _\nu }{\rho _\nu }=0`$ without loss of generality):

$$\frac{\delta \rho _{\mathrm{tot}}}{\rho _{\mathrm{tot}}}=\frac{\delta \rho _c}{\rho _c}+\frac{\delta \rho _\gamma }{\rho _\gamma }=0\text{(CDM ISO)}$$

and therefore the gravitational potential $`\mathrm{\Psi }`$ is approximately zero as well (“isocurvature”). CDM isocurvature IC excite a sine oscillation, and the resulting first peak in the power spectrum is displaced to $`\mathrm{}330`$. Generation of isocurvature initial conditions requires the presence of (at least) a second light scalar field during inflation. The observation of the first peak at $`\mathrm{}=220.1\pm 0.8`$ Page03  has ruled out the possibility of pure CDM isocurvature initial conditions. However, a subdominant isocurvature contribution to the prevalent adiabatic mode cannot be excluded.

Beside AD and CDM isocurvature, the complete set of IC for a fluid consisting of photons, neutrinos, baryons and dark matter in general relativity consists of three more modes BMT . These are the baryon isocurvature mode (BI), the neutrino isocurvature density (NID) and neutrino isocurvature velocity (NIV) modes. Those five modes are the only regular ones, i.e. they do not diverge at early times. The NID mode can be understood as a neutrino entropy mode, while the NIV consists of vanishing density perturbations for all fluids but non-zero velocity perturbations between fluids. The CDM and BI modes are identical, and therefore it suffices to consider only one of them. In the most general scenario, one would expect all four modes to be present with arbitrary initial amplitude and arbitrary correlation or anti-correlation, with the restriction that their superposition must be a positive quantity. For simplicity we consider the case where all modes have the same spectral index, $`n_\mathrm{S}`$. The most general initial conditions are then described by the spectral index $`n_\mathrm{S}`$ and a positive semi-definite $`4\times 4`$ matrix, which amounts to eleven parameters instead of two in the case of pure AD initial conditions. More details can be found in Refs. TRD1 ; TRD2 . The CMB and matter power spectra for the different types of initial conditions are plotted in Fig. 2.

### 2.3 The matter power spectrum

Inclusion of general initial conditions in the analysis can lead to very important degeneracies in the IC parameter space, which spoil the accuracy with which other cosmological parameters can be measured by CMB alone. This has been demonstrated in a striking way for the case of the Hubble parameter and the baryon density in Ref TRD1 , cf Fig. 1. An effective way to break this degeneracy is achieved by the inclusion of large scale structure (LSS) data. The key point is that, once the corresponding CMB power spectrum amplitude has been COBE-normalized, the amplitude of the AD matter power spectrum is nearly two orders of magnitude larger than any of the isocurvature contribution (cf Fig. 2). Therefore the matter power spectrum essentially measures the adiabatic part, and is nearly insensitive to isocurvature contributions. The argument holds true for observations of the matter spectrum on all scales, ranging from large scale structure to weak lensing and Lyman $`\alpha `$-clouds. In view of optimally constraining the isocurvature content, it is therefore essential to combine those observations with CMB data, in order to break the strong degeneracy among initial conditions which is present in the CMB power spectrum alone Tprep .

## 3 The cosmological constant and isocurvature IC

We apply the above statistical (Bayesian or frequentist) and physical (general initial conditions, matter power spectrum) considerations to the study of the cosmological constant problem from pre-WMAP data. We outline the method and the main results below (see Ref. TRD2  for more details) and comment at the end on the qualitative impact of the new WMAP data on those findings.

Our analysis makes use of the COBE, BOOMERanG and Archeops data CMBdata , covering the range $`3\mathrm{}1000`$ in the CMB power spectrum. For the matter power spectrum, we use the galaxy-galaxy linear power spectrum from the 2dF data 2dFdata , and we assume that light traces mass up to a (scale independent) bias factor $`b`$, over which we maximise. The main focus being on the type of initial conditions, we restrict our analysis to only 3 cosmological parameters: the scalar spectral index, $`n_S`$, the cosmological constant $`\mathrm{\Omega }_\mathrm{\Lambda }`$ in units of the critical density and the Hubble parameter, $`H_0=100h\mathrm{km}\mathrm{s}^1\mathrm{Mpc}^1`$. We consider flat universes only and neglect gravitational waves.

When we set to zero the isocurvature modes, we recover the well-known results for purely AD perturbations. Because of the “geometrical degeneracy”, CMB alone cannot put very tight lower limits on $`\mathrm{\Omega }_\mathrm{\Lambda }`$ even if we allow only for flat universes. The degeneracy can be broken either by putting an external prior on $`h`$ or via the LSS spectrum, since $`P_\mathrm{m}`$ is mainly sensitive to the shape parameter $`\mathrm{\Gamma }\mathrm{\Omega }_\mathrm{m}h`$. Combination of CMB and LSS data yields the following likelihood (Bayesian) intervals for $`\mathrm{\Omega }_\mathrm{\Lambda }`$:

$$\mathrm{\Omega }_\mathrm{\Lambda }=0.70_{0.05}^{+0.05}\text{ at }1\sigma \text{ and }_{0.27}^{+0.15}\text{ at }3\sigma .$$
(1)
From the Bayesian analysis, one concludes that CMB and LSS together with purely AD initial conditions require a non-zero cosmological constant at very high significance, more than $`7\sigma `$ for the points in our grid! However, our best fit has a reduced chi-square $`\chi /F=0.59`$, significantly less than $`1`$. This leads to artificially tight likelihood regions: the observationally excluded part of parameter space is less extended, and is given by the frequentist analysis. From the frequentist approach, we obtain instead the following confidence intervals:

$$0.15<\mathrm{\Omega }_\mathrm{\Lambda }<0.90\text{ at }1\sigma \text{ and }\mathrm{\Omega }_\mathrm{\Lambda }<0.92\text{ at }3\sigma .$$
(2)
When we enlarge the space of models by including all possible isocurvature modes, likelihood (Bayesian) and confidence (frequentist) contours widen up along the $`\mathrm{\Omega }_\mathrm{\Lambda }`$, $`h`$ degeneracy, and this produces a considerable worsening of the likelihood limits. For general initial conditions we now find (Bayesian, CMB and LSS together):

$$\mathrm{\Omega }_\mathrm{\Lambda }=0.70_{0.10}^{+0.15}\text{ at }1\sigma \text{ and }_{0.48}^{+0.25}\text{ at }3\sigma .$$
(3)
Again, the frequentist statistics give less tight bounds:

$$\mathrm{\Omega }_\mathrm{\Lambda }<0.90\text{ at }1\sigma \text{ and }\mathrm{\Omega }_\mathrm{\Lambda }<0.95\text{ at }3\sigma ,$$
(4)
and in particular we cannot place any lower limit on the value of the cosmological constant. A complete discussion can be found in Ref. TRD2 . Joint likelihood contours for $`\mathrm{\Omega }_\mathrm{\Lambda }`$, $`h`$ with AD and general isocurvature initial conditions are plotted in Fig. 3 for both statistical approaches.

From the frequentist point of view, the region in the $`\mathrm{\Omega }_\mathrm{\Lambda },h`$ plane which is incompatible with data at more than $`3\sigma `$ is nearly independent on the choice of initial conditions (compare left and right panel of Fig. 3). Enlarging the space of initial conditions seemingly does not have a relevant benefit on fitting pre-WMAP data with or without a cosmological constant. In Fig. 4 we plot the best fit model (which has $`\chi /F=0.67`$) with general initial conditions and $`\mathrm{\Omega }_\mathrm{\Lambda }=0`$. As a consequence of the red spectral index ($`n_S=0.80`$) and of the absence of the early Integrated Sachs-Wolfe effect (since $`\mathrm{\Omega }_\mathrm{\Lambda }=0`$), the best fit model has a very low first acoustic peak, even in the presence of isocurvature modes. This is compatible with the BOOMERanG and Archeops data only if the absolute calibration of the experiments is reduced by $`28\%`$ and $`12\%`$, respectively. Furthermore, this best fit model has a rather low value of the Hubble parameter, $`h=0.35`$, which is many sigmas away from the value obtained by the HST Key Project, namely $`h=0.72\pm 0.08`$ HST . We conclude that a good fit to the pre-WMAP CMB data combined with LSS measurements can only be obtained at the price of pushing hard the other parameters, even when general initial conditions are allowed for.

Finally, in order to constrain deviations from perfect adiabaticity, it is interesting to limit quantitatively the isocurvature contribution. To this end, one can phenomenologically quantify the isocurvature contribution to the CMB power by a parameter $`0\beta 1`$, defined in Ref. TRD2 , so that purely AD IC are characterized by $`\beta =0`$, while purely isocurvature IC correspond to $`\beta =1`$. In Fig. 5 we plot the value of $`\beta `$ for the best fit models, with the frequentist exclusion regions superimposed. Within $`2\sigma `$ c.l. (frequentist), the isocurvature contribution to the IC is bounded to be less then $`40\%`$.

Although a quantitative analysis using the more precise WMAP data has not yet been carried out, some qualitative features of the expected results can be discussed. In particular, the first peak has been measured by WMAP to be 10% higher then in previous observations WMAP . On the other hand, our work indicates that the first peak is very suppressed even in the presence of general IC for $`\mathrm{\Omega }_\mathrm{\Lambda }=0`$. Therefore one expects that WMAP data will exclude with much higher confidence a vanishing cosmological constant. In fact, our pre-WMAP best fit $`\mathrm{\Omega }_\mathrm{\Lambda }=0`$ model, when compared to the WMAP data WMAP , has $`\chi _{WMAP}^2/F4.4`$, and is therefore found to be totally incompatible with the new data. Furthermore, the constraints on non-adiabatic contributions should improve considerably, especially in view of the inclusion of polarization data BMTpol .

## 4 Conclusions

We have shown that the statistical approach (Bayesian or frequentist) can have an important impact in the determination of errors from CMB and LSS data. We found that structure formation data tend to prefer a non-zero cosmological constant even if general isocurvature initial conditions are allowed for. The isocurvature contribution is constrained to be $`40\%`$ at $`2\sigma `$ c.l. (frequentist).

## Aknowledgments

It is a pleasure to thank Alessandro Melchiorri and all the organizers of the workshop. I am also grateful to Alain Riazuelo and Ruth Durrer for a most pleasant collaboration. RT is partially supported by the Schmidheiny Foundation, the Swiss National Science Foundation and the European Network CMBNET.


text:
# 1 Introduction

## 1 Introduction

The genetic information in DNA is stored in sequences built up from four bases (nucleotides) $`C`$, $`T`$, $`G`$, $`A`$ (in mRNA, which plays a key role in the construction of proteins, the base $`T`$ is replaced by $`U`$). The proteins are made up from 20 different amino-acids. The “quantum” of genetic information is constituted by an ordered triplet of nucleotides (codon). There are therefore 64 possible codons, which encode 20 amino-acids, plus the three signals of the termination of the biosynthesis process. It follows that the genetic code, i.e. the correspondence between codons and amino-acids, is degenerate, and almost all the amino-acids are encoded by multiple codons (synonymous codons). Degeneracy is mainly found in the third position of the codon. For a long time it was accepted that: 1) there was no preference for the use of any particular codon, except for the enhancement due to the abundance of a particular basis (nucleotide); 2) the codon usage frequency was strongly dependent on the considered biological species, and no regular pattern could therefore be extracted.

The currently available data show that some codons are used much more frequently than others to encode a particular amino-acid. Let us, indeed, define the usage probability for the codon $`XZN`$ ($`X,Z,N\{A,C,G,U\}`$) in a quartet as

$$P(XZN)=\underset{n_{tot}\mathrm{}}{lim}\frac{n_{XZN}}{n_{XZ}}$$
(1)
where $`n_{XZN}`$ is the number of times the codon $`XZN`$ has been used in the biosynthesis process of the corresponding amino-acid and $`n_{XZ}`$ is the total number of codons used to synthetize this amino-acid. It follows that our analysis and predictions hold for biological species with sufficiently large statistics of codons. The above definition holds also for the usage probability for doublets, in which case we have to consider two possibilities: $`NY(=C,U)`$ and $`NR(=G,A)`$. Let us point out that we consider a sextet as the sum of a quartet and a doublet, and a triplet as the sum of a doublet and a singlet. Therefore, in the following, we consider eight quartets, corresponding to the five quartets plus the quartet subparts of the three sextets of the eukaryotic code. In the following the probabilities for each quartet or each doublet are normalized to 1. It is currently believed that a non-uniform usage of synonymous codons is a widespread phenomenon and it is experimentally observed that the pattern of codon usage varies between species and even between tissues within a species; see refs. , which contain a large number of references to the original works on the subject. The main reasons for the codon usage biases are believed to be: the mutational biases, the translation efficiency, the natural selection and the abundance of specific anticodons in the tRNA. However, the aim of this paper is not to compare the different proposed explanations, but to put in evidence a general pattern of the bias.

To our knowledge, systematic studies of codon usage for eukaryotes are rather fragmentary, while the case of bacteriae has been widely studied. Most of the analyses of the codon usage frequencies have addressed an analysis of the relative abundance of a specified codon in different genes of the same biological species or in the comparison of the relative abundance in the same gene for different biological species. Little attention has been paid to analyze the codon usage frequency summed over the whole available sequences to infer global correlations between different biological species. Indeed, in , analysing a large sample of species, a correlation between the GC content and the codon usage has been pointed out and explained on the basis of a mutational model at the nucleotide level. In , starting from the so-called crystal basis model for the genetic code proposed a few years ago by the present authors in , it has been derived that the sum of the codon usage probabilities for codons belonging to quartets, in the generalized meaning specified above, with third nucleotide $`C`$ and $`A`$ (or $`G`$ and $`U`$), should be a constant (sum rule). In the present paper we pursue the analysis and the developments of these sum rules, in particular investigating the consequences on the correlation matrix. With the twofold aim of focussing on the implications of the sum rules and of making the paper more easily legible to a wide range of readers, which may be not acquainted with the mathematical background of our model, no reference will be made either to the model itself or to the mathematical reasoning that led to the derivation of the sum rules. The interested reader can find details in the quoted papers and references therein. We simply state the results, which will be the input for the further analysis presented below.

Sum rules: for the codons belonging to quartets and for biological species belonging to vertebrates,

$`P(XZC)+P(XZA)=\text{Const.}(XZ=NC,CU,GU,CG,GG)`$ (2)
holds. Here Const. means a value, depending on $`XZ`$, but independent on the biological species. In  a table with the values of these quantities can be found. From (2), one gets immediately

$`P(XZC)`$ $`=`$ $`\rho (XZC)+H_{bs}(XZC)`$
$`P(XZA)`$ $`=`$ $`\rho (XZA)H_{bs}(XZC)`$
$`P(XZG)`$ $`=`$ $`\rho (XZG)+H_{bs}(XZG)`$
$`P(XZU)`$ $`=`$ $`\rho (XZU)H_{bs}(XZG),`$ (3)
where $`\rho `$ are functions independent on the biological species while the functions $`H_{bs}`$ depend on the biological species.

In  the r.h.s. of eq. (2) has been fitted to the experimental data. Therefore it is natural to wonder how the experimentally fitted values depend on the data. In table 3 we have computed, for two biological species, namely Homo sapiens and Danio rerio, the probabilities for the codons in quartets with the last nucleotide $`C`$ or $`A`$ and their sum, using different releases of available data from GenBank in the last four years, in order to investigate the dependence on the statistics. One can remark that the experimentally computed probabilities change, but that in about $`80\%`$ of cases an increase in $`P(XZA)`$ corresponds to a decrease in $`P(XZC)`$ and vice versa. This property is an indication of the existence of an anticorrelation between $`P(XZC)`$ and $`P(XZA)`$. An analogous analysis for other biological species belonging to the sample listed in table 1 shows the same behaviour. Let us remark that from this kind of analysis, one expects that for statistics of codons lower than roughly 100 000, the statistical fluctuations become non-negligible.

## 2 Correlation matrix

Let us introduce now the correlation matrix $`\mathrm{\Gamma }`$ between two discrete random variables $`X`$ and $`Y`$. For a sample of size $`n`$, it is defined by

$$\mathrm{\Gamma }(X,Y)=\frac{1}{\sigma _X\sigma _Y}\underset{k=1}{\overset{n}{}}\frac{1}{n}\left(X_kX\right)\left(Y_kY\right)$$
(4)
where $`\sigma _X`$ is the standard deviation

$$\sigma _X=\sqrt{\frac{1}{n(n1)}\left(n\underset{k=1}{\overset{n}{}}X_k^2\left(\underset{k=1}{\overset{n}{}}X_k\right)^2\right)}$$
(5)
and $`X`$ is the mean value

$$X=\frac{1}{n}\underset{k=1}{\overset{n}{}}X_k.$$
(6)
In our context, $`X_k`$ (resp. $`Y_k`$) are the usage probability functions $`P(XZN)`$ (resp. $`P(X^{}Z^{}N^{})`$) for the $`k`$-th biological species for the same or different amino-acids. The sample we consider is given in table 1.

We can then construct a $`32\times 32`$ correlation matrix $`\mathrm{\Gamma }`$ whose entries are the correlation coefficients $`\mathrm{\Gamma }(P(XZN),`$ $`P(X^{}Z^{}N^{}))`$, where $`XZ,X^{}Z^{}=CC,UC,GC,AC,CU,GU,CG,GG`$. From the expressions of the probabilities (1) and the sum rules (2) we derive for the same amino-acid the following symmetric submatrix:

$$\begin{array}{ccccc}& & & & \\ & P(XZU)& P(XZC)& P(XZA)& P(XZG)\\ & & & & \\ P(XZU)& 1& x& x& 1\\ P(XZC)& x& 1& 1& x\\ P(XZA)& x& 1& 1& x\\ P(XZG)& 1& x& x& 1\end{array}$$

where $`x`$ is a theoretically undetermined quantity to be fitted experimentally for any amino-acid. This kind of pattern can be easily compared with the experimental data for vertebrates (see the list of biological species and the corresponding number of codons used) from GenBank (release 131.0 of August 2002). One gets for the eight quartets

$$\begin{array}{ccccccc}& & & & & & \\ & \mathrm{\Gamma }_{UC}& \mathrm{\Gamma }_{UA}& \mathrm{\Gamma }_{UG}& \mathrm{\Gamma }_{CA}& \mathrm{\Gamma }_{CG}& \mathrm{\Gamma }_{AG}\\ & & & & & & \\ \text{Pro}\hfill & 0.75& 0.71& 0.68& 0.88& 0.22& 0.53\\ \text{Thr}\hfill & 0.89& 0.88& 0.62& 0.89& 0.27& 0.62\\ \text{Ala}\hfill & 0.86& 0.70& 0.46& 0.80& 0.17& 0.61\\ \text{Ser}\hfill & 0.75& 0.44& 0.67& 0.84& 0.30& 0.40\\ \text{Val}\hfill & 0.55& 0.51& 0.89& 0.67& 0.32& 0.66\\ \text{Leu}\hfill & 0.83& 0.43& 0.82& 0.47& 0.57& 0.78\\ \text{Arg}\hfill & 0.36& 0.34& 0.92& 0.88& 0.03& 0.16\\ \text{Gly}\hfill & 0.78& 0.78& 0.91& 0.92& 0.63& 0.80\end{array}$$

where $`\mathrm{\Gamma }_{NN^{}}`$ denotes for short $`\mathrm{\Gamma }(P(XZN),P(XZN^{}))`$, for some amino-acid related to a quartet of codons $`XZN`$.

From the above table, we remark that the values of some antidiagonal elements $`\mathrm{\Gamma }_{NN^{}}`$ are very close to the theoretical values $`1`$, namely $`\mathrm{\Gamma }_{UG}`$ and $`\mathrm{\Gamma }_{CA}`$ for Arg and Gly, $`\mathrm{\Gamma }_{CA}`$ for Pro, Thr, Ala, Ser and $`\mathrm{\Gamma }_{UG}`$ for Val and Leu 111In the crystal basis model , the mathematical assignment of the codons encoding for the eight quartets exhibit the same pattern of grouping of codons.. We also note that the entries $`\mathrm{\Gamma }_{UN}`$ for all eight amino-acids are in good agreement with the theoretical values, while the entries $`\mathrm{\Gamma }_{CG}`$, $`\mathrm{\Gamma }_{AG}`$ show a large numerical discrepancy. These facts mean that the small violations of the sum rules are averaged, in the sum defining the correlation coefficients, almost to zero for $`\mathrm{\Gamma }_{UN}`$, but not for the other ones, as can be inferred from the analysis of the values of the probabilities $`P(XZN)`$ given in tables 4 to 7. It is evident that the degree of correlation is not the same for the eight amino-acids, Thr and Leu being the most correlated ones, and Arg the least one.

It may be useful to compute the average value over the eight amino-acids of the entries of the correlation matrix

$`\mathrm{\Gamma }_{CA}=0.79,`$ $`\mathrm{\Gamma }_{CG}=0.32,`$ $`\mathrm{\Gamma }_{CU}=0.72,`$
$`\mathrm{\Gamma }_{GU}=0.75,`$ $`\mathrm{\Gamma }_{AU}=0.60,`$ $`\mathrm{\Gamma }_{AG}=0.57.`$ (7)
We see that the average values differ within $`20\%`$ from the expected ones, except for $`\mathrm{\Gamma }_{CG}`$, which is almost half of the expected value. We shall comment later on this point.

For different amino-acids we derive from (3) that for the eight amino-acids related to quartets, the theoretical correlation pattern, for the different probabilities take the following form

$$\begin{array}{ccccc}& & & & \\ & P(XZU)& P(XZC)& P(XZA)& P(XZG)\\ & & & & \\ P(X^{}Z^{}U)& y& z& z& y\\ P(X^{}Z^{}C)& t& x& x& t\\ P(X^{}Z^{}A)& t& x& x& t\\ P(X^{}Z^{}G)& y& z& z& y\end{array}$$

This kind of pattern can also be easily compared with the experimental data. One obtains, for example, for the correlations between the probabilities of codon usage of Valine and Threonine:

$$\begin{array}{ccccc}& & & & \\ & P(GUU)& P(GUC)& P(GUA)& P(GUG)\\ & & & & \\ P(ACU)& 0.76& 0.64& 0.75& 0.76\\ P(ACC)& 0.83& 0.64& 0.72& 0.81\\ P(ACA)& 0.72& 0.80& 0.83& 0.67\\ P(ACG)& 0.23& 0.57& 0.57& 0.22\end{array}$$

for Glycine and Alanine:

$$\begin{array}{ccccc}& & & & \\ & P(GGU)& P(GGC)& P(GGA)& P(GGG)\\ & & & & \\ P(GCU)& 0.83& 0.80& 0.71& 0.67\\ P(GCC)& 0.65& 0.86& 0.80& 0.54\\ P(GCA)& 0.56& 0.79& 0.69& 0.40\\ P(GCG)& 0.48& 0.35& 0.22& 0.31\end{array}$$

We can extend the correlation matrix by taking into account the correlations between quartets and doublets, getting a $`58\times 58`$ matrix. We obtain, for the correlation entries between quartets and doublets:

$$\begin{array}{ccccc}& & & & \\ & P(XZU)& P(XZC)& P(XZA)& P(XZG)\\ & & & & \\ P(X^{}Z^{}U)& x& y& y& x\\ P(X^{}Z^{}C)& x& y& y& x\\ & & & & \\ P(X^{}Z^{}A)& z& t& t& z\\ P(X^{}Z^{}G)& z& t& t& z\end{array}$$

Note that the structure of the doublets implies that the second and fourth lines are direct consequences of the first and third lines, respectively. As an example, we obtain, for the correlations between Pro versus Asp and Glu:

$$\begin{array}{ccccc}& & & & \\ & P(CCU)& P(CCC)& P(CCA)& P(CCG)\\ & & & & \\ P(GAU)& 0.68& 0.76& 0.88& 0.55\\ & & & & \\ P(GAA)& 0.54& 0.58& 0.75& 0.54\end{array}$$

Also in this case, the largest discrepancy appears in the matrix entry $`\mathrm{\Gamma }_{CG}`$.

An analysis of the above tables shows that there are numerical violations with respect to the theoretical correlation matrix, but that the signs, with few exceptions corresponding to values close to zero, are preserved. Let us remark that for each pair of quartets (or quartet and doublet), provided that the codons are put in the order $`U,C,A,G`$ and assuming that the number $`x,y,z,t`$ are all of the same sign, one obtains a correlation matrix whose entries show alternating signs along each row and each column. An inspection of the correlation matrix shows that the 406 independent parameters that appear in our model are all positive. This intriguing property, which is likely to reflect some “dynamical” behaviour, requires further analysis in order to be well understood and also to evaluate to what extent it depends on the choice of the sample. A comparison with the experimentally computed $`58\times 58`$ correlation matrix shows that this property is verified with a very good approximation. Indeed it is violated only for a few per cent of the entries: in these cases the correlation coefficients with wrong sign are very small, i.e. they concern poorly correlated codon usage probabilities, which are expected to be much more sensitive to fluctuations.

## 3 Shannon entropy

The order of magnitude of the biological species independent term $`\rho (XZN)`$ in (3) is around the mean value denoted $`P_N`$ in tables 4 to 7, and the biological species dependent term in (3) is around $`\sigma (P_N)`$ ($`N=C,A,U,G`$). Note that the ratio $`\sigma (P_N)/P_N`$ is around 10% in each case. A rough analysis of the distribution of the probabilities $`P_N`$ seems to indicate a standard distribution, although the small size of the sample does not allow us to draw a reliable conclusion.
In order to check the effectiveness of the sum rules in the light of the above estimations, we compute the Shannon entropy related to the eight amino-acids, all considered as encoded by quartets:

$$S_{XZ}=\underset{N=C,A,U,G}{}P(XZN)\mathrm{ln}_2P(XZN)$$
(8)
where $`P(XZN)`$ is given by eq. (3). Since $`H_{bs}^{}{}_{N}{}^{}/\rho _N1`$, we can approximate $`\mathrm{ln}(1\pm H_{bs}^{}{}_{N}{}^{}/\rho _N)`$ by $`\pm H_{bs}^{}{}_{N}{}^{}/\rho _N\frac{1}{2}H_{bs}^{2}{}_{N}{}^{}/\rho _N^2`$. So we get for the Shannon entropy for a given amino-acid related to a dinucleotide $`XZ`$:

$`S_{XZ}`$ $``$ $`{\displaystyle \underset{N=C,A,U,G}{}}\rho _N\mathrm{ln}_2\rho _NH_{bs}^{}{}_{C}{}^{}\mathrm{ln}_2{\displaystyle \frac{\rho _C}{\rho _A}}H_{bs}^{}{}_{G}{}^{}\mathrm{ln}_2{\displaystyle \frac{\rho _G}{\rho _U}}`$ (9)
$``$ $`{\displaystyle \frac{1}{2\mathrm{ln}2}}H_{bs}^{2}{}_{C}{}^{}\left({\displaystyle \frac{1}{\rho _C}}+{\displaystyle \frac{1}{\rho _A}}\right){\displaystyle \frac{1}{2\mathrm{ln}2}}H_{bs}^{2}{}_{G}{}^{}\left({\displaystyle \frac{1}{\rho _G}}+{\displaystyle \frac{1}{\rho _U}}\right),`$
where for simplicity $`\rho _N`$, $`H_{bs}^{}{}_{N}{}^{}`$ and $`P_N`$ stand for $`\rho (XZN)`$, $`H_{bs}(XZN)`$ and $`P(XZN)`$ respectively, the dinucleotide $`XZ`$ being fixed. In this equation, the first sum corresponds to the biological species independent part of the Shannon entropy, while the second and third terms are the first- and second-order biological species dependent corrections. From the above formula, we expect the entropy to be independent of the biological species within a few per cent. We report in table 9 the Shannon entropy for the eight amino-acids related to quartets for the sample of biological species of table 1. The standard deviation is in this case reduced with respect to the standard deviations of the probability distributions $`P(XZN)`$, see tables 4 to 7, as can be easily checked quantitatively from the last terms of (9). Let us remark that there is no clear dependence of the Shannon entropies $`S_{XZ}`$ on the total exonic $`GC`$ content of the biological species.

Now we can compute the contribution of each quartet to the Shannon entropy of the total exonic region, defined as:

$$S_{tot}=\underset{i}{}p_i\mathrm{ln}_2p_i,$$
(10)
where the sum runs over all the coding codons and $`p_i`$ is the usage probability of the codon $`i`$, i.e.

$$p_i=\frac{n_i}{N_{tot}}$$
(11)
where $`n_i`$ is the number of times the codons $`i`$ has been used and $`N_{tot}`$ is the total number of coding codons.
The contribution to the Shannon entropy (10) of the amino-acid encoded by the codons $`XZN`$ ($`N=C,A,U,G`$) is

$$S_{tot}^{XZ}=\underset{N=C,A,U,G}{}p_N\mathrm{ln}_2p_N.$$
(12)
As $`p_N=P(XZN){\displaystyle \frac{n_{XZ}}{N_{tot}}}`$, we get

$$S_{tot}^{XZ}=P_{XZ}\mathrm{ln}_2P_{XZ}+P_{XZ}S_{XZ},$$
(13)
where $`P_{XZ}`$ is the probability of the amino-acid encoded by $`XZN`$, i.e. $`P_{XZ}={\displaystyle \frac{n_{XZ}}{N_{tot}}}`$, and $`S_{XZ}`$ is given by eq. (8).

Therefore, from the remarked biological species independence of $`S_{XZ}`$, we derive that the contribution of an amino-acid (encoded by a quartet) to the total Shannon entropy depends only on its frequency. This is a non trivial result. Indeed, the probability of an amino-acid depends of course on the probabilities of the encoding codons, but a priori one might obtain the same amino-acid probability with different distributions of the encoding codons, therefore with different contributions to the total Shannon entropy. On the contrary, eq. (13) tells us that the contribution to the entropy is, within a few per cent, equal for all vertebrates for a fixed frequency of the amino-acid.

## 4 Conclusion

The above analysis provides a strong support of the validity for the sum rules equation (2). The emerging pattern, for vertebrates, is the existence of a species independent codon usage bias. From tables 4 to 7, it is clear that the third nucleotides in the quartets are in decreasing usage order: $`C>U>A>G`$ for Pro, Ala and Ser, $`C>U>G>A`$ for Thr, $`G>C>U>A`$ for Val and Leu, $`CG>AU`$ for Arg and $`C>A>G>U`$ for Gly. Some biological species show different patterns (e.g. Danio rerio and Macaca fascicularis). The deviations from the values given by the sum rules are fluctuations that shift the numerical values of the correlation matrix entries from the expected ones, but are not strong enough to change the sign. The existence of sum rules indicates correlations in the whole set of the coding sequences of DNA, while in the literature it is stated that correlations essentially appear in the non-coding part of DNA. It should be quoted that Zeeberg , from an analysis of over 7000 genes for Homo sapiens, has derived parameters for linear regression for codon nucleotide composition versus the per cent of $`GC`$ content in genomic regions. From his analysis, one expects a correlation of the same order for codons having $`C`$ or $`U`$, and $`C`$ or $`A`$ in third position. Our result shows a stronger correlation in the latter case.

As noted above, the values of the entry $`\mathrm{\Gamma }_{CG}`$ are smaller than those expected. This feature may be due to the known suppression of the codons containing a dinucleotide CG, see ref. , and for a thermodynamical explanation of this phenomenon, see ref. . Note that this suppression can be inferred by looking at the first four columns of table 7. An inspection of the columns 5 and 6 of table 5 shows that there is also a suppression in the usage of codons containing the dinucleotide $`UA`$. It is worthwhile to further investigate this suppression in the other codons. Indeed an analysis of the codon usage probabilities of the codons $`AUA`$ encoding for Ile and $`UUA`$ encoding for Leu confirms this suppression. It is also interesting to observe that the codons $`UAR`$, being nonsense codons, are rarely used.

We have also remarked that the Shannon entropies related to the eight amino-acids, encoded by quartets in the present scheme, are biological species independent within a few per cent. Moreover, the contribution of these amino-acids to the total Shannon entropy (10) depends only on their frequencies.

It would be interesting to extend this type of analysis to a suitably chosen sample of plants or of invertebrates, while bacteriae seem to behave in a peculiar different way.

Acknowledgements: A.S. is indebted to the Université de Savoie for financial support and LAPTH for its kind hospitality.