format: text

text:
# QUANTUM COSMOLOGY WITH CURVATURE SQUARED ACTION

## I Introduction

In analogy with the particle quantum dynamics and the quantum field theory,Hartle-Hawking  suggested that the ground state wave function of the universe is given by

$$\psi _0[h_{ij}]=N\delta gexp(I_E[g]),$$
(1)
with the proposal that the sum should be taken over all compact four geometries. This implies that the universe does not have any boundary in the euclidean regime. The above functional integral over all compact four geometries bounded by a given three geometry is interpreted as amplitude of the given three geometry to arise from a zero three geometry,where $`\psi _0[h_{ij}]`$ is finite. Thus the ground state is the amplitude of the universe to arise from nothing.

The euclidean form of the Einstein-Hilbert action is not positive definite. Therefore the functional integral for the wave function of the universe as proposed by Hartle-Hawking runs into serious problems, since the wave function diverges badly.There are some prescriptions to make the above path integral convergent.In one of the prescriptions , , , it was suggested that the proper choice of the contour of integration in the functional integral might yield positive definite action, while in another prescription  a suitable choice of conformal factor may give rise to positive definite action. Unfortunately, a completely satisfactory result has not yet been obtained through the above two prescriptions.

Further to explain the inflationary scenario without invoking phase transition in the very early universe, Starobinsky  considered a field equation containing only the geometric terms, but this field equation could not be obtained from the action principle,as the terms in the field equations are obtained from the perturbative quantum field theory. Starobinsky and Schmidt  later have shown that the inflationary phase is an attractor in the neighbourhood of the solution of the fourth order gravity theory.

However,to get a convergent integral for the wave function Horowitz  proposed an action in the form

$$S=\frac{1}{4}d^4X\sqrt{g}[AC_{ijkl}^2+B(R4\mathrm{\Lambda })^2],$$
(2)
where, $`C_{ijkl}`$ is the Weyl tensor, $`R`$ is the Ricci scalar,$`\mathrm{\Lambda }`$ is the cosmological constant and $`A,B`$ are coupling constants. In the weak energy limit this action (2) reduces to the Einstein-Hilbert action for gravity. To obtain a workable and simplified form of the field equations, we consider a homogeneous and isotropic minisuperspace model. Then $`C_{ijkl}`$ vanishes trivially and if one chooses $`\mathrm{\Lambda }=0`$, for the sake of simplicity, the action (2) retains only the curvature squared term.

The classical field equations for $`R^2`$ gravity can be obtained by the standered variational principle. In the variational principle total derivative terms in action are extracted and yields a surface integral and it is assumed that the surface integral vanishes at boundary of variation, or, the action is chosen in such a way that those surface integral terms have no contribution in the action. However for canonical quantisation this principle is not of much help. For this purpose one has to express the action in the canonical form. Boulware et al  has proposed that this can be achived by introducing a new variable,which is the first derivative of the action with respect to the highest derivative of the field variable that appears in the action.

Hawking and Luttrell  utlised the technique to identify the new variable and the conformal factor and showed that the Einstein-Hilbert action along with the curvature squared term reduces to the Einstein’s gravity being coupled to a massive scalar field. Horowitz  on the other hand retained only the curvature squared term and showed that the corresponding Wheeler-deWitt equation looks very similar to the Schr$`\ddot{o}`$dinger equation. The semi-classical approximation to such quantum equation has also been presented by him. Pollock has also introduced the same technique to the induced gravity theory and obtained the same type of result as that obtained by Horowitz  in the sense that the corresponding Wheeler-deWitt equation looks similar to the Schr$`\ddot{o}`$dinger equation.

In the present paper we shall deal with the curvature squared term with a view to study at which stage the new variable should be introduced to obtain the correct Wheeler-deWitt equation. Our proposal is that one should introduce the new variable only after removing all the total derivative terms from the action and the new variable is the first derivative of the action (free from total derivative terms) with respect to the highest derivative of the field variable. Then one should express the action in the canonical form with respect to the new variable. At this stage one should also remove the total derivative terms (if any) from the action and the variation of the action yields the classical field equations.

It is important to note that the classical field equations remain the same both in our proposal and in the Boulware’s  proposal. However the canonical quantization in our proposal yields inequivalent Wheeler-deWitt equation from that obtained by the technique followed by Horowitz .

To elucidate our proposal we shall consider a toy model of the vacuum Einstein-Hilbert action in section 2., and show that the introduction of a new variable following Horowitz and Pollock leads to a wrong Wheeler-deWitt equation. We therefore conclude that such a variable should be introduced only after removing all the total derivative terms from the action.

In section 3, we shall consider curvature squared action and with the proper choice of the variable ,we show that the corresponding Wheeler-deWitt equation is different from that obtained by Horowitz , though it still looks similar to the Schr$`\ddot{o}`$dinger equation.In order to compare these results we have chosen FRW model in conformal time coordinate for closed ($`k=1`$) universe.The Wheeler-deWitt equation thus obtained contains an effective potential $`V`$. The presence of the potential is in sharp contrast from that obtained by Horowitz . The potential $`V`$ is a function of the expansion parameter (i.e. the Hubble parameter) of the classical field equations and it is diverging both at the zero’s and at the very large values of the expansion parameter. further the effective potential is also asymmetric with respect to the expansion and collapse of the universe. The physical interpretation of the potential is not yet clear to us, however its extremum yields interesting results. One of the extremum of the potential corresponds to the classical vacuum Einstein equation ,while the other can be viewed upon as a classical equation which admits inflation . In fact, the classical field equation obtained from the extremum of the potential is not surprising, but it should be a desirable feature of higher derivative gravity theory at the weak energy limit (i.e. at the long wavelength limit), where the contribution of the kinetic energy is sufficiently small with comparison to the potential energy in the Hamiltonian; justifying the idea of extremum of the potential.

In section 4, we shall present the Hamilton-Jacobi equation corresponding to the Schr$`\ddot{o}`$dinger equation and then we can identify the time parameter that appears in the Hamilton-Jacobi equation. In this section we shall also present a particular solution of the Wheeler-deWitt equation for $`n=0`$ operator ordering,which is well behaved for all values of the expansion parameters and at the vanishing three space volume. The probability density $`\psi ^{}\psi `$ is a real quantity and is proportional to the scale factor of the universe.

In section 5, we have treated the same problem in proper time coordinate for arbitrary three space curvature ($`k=o,\pm 1`$) . This shows that the form of the Wheeler-deWitt equation remains unchanged . We then turn our attention (see section 6) to compare our formalism to that developed by Schmidt earlier. For this purpose we have chosen $`k=0`$ and have shown that the formalism of Schmidt following Ostrogradski \[reference cited therein\] is different from that of ours, though the new variables in both the formalisms turn out to be the same and hence the Hamiltonian. This approach of Schmidt has recently been considered by Fabris and Reuter . However in our method we have introduced the variables in two stages systematically, first, to obtain the field equations and then to find the right Hamiltonian that should be quantized. The method is simple and straight forward. While the other formalism introduced the variables at one stage only, to find the Hamiltonian. This formalism would yield the same Hamiltonian as that of ours only if one starts from an action free from surface term.

In section 7, we present a brief conclusion.

## II Introducing The New Variable In The Vacuum Einstein-Hilbert Action (a toy model)

The vacuum Einstein-Hilbert action is

$$S=\frac{1}{2\pi ^2}d^4X\sqrt{g}R.$$
(3)
We consider the closed Robertson-Walker metric in the form

$$ds^2=exp2\alpha (\eta )[d\eta ^2d\chi ^2sin^2\chi (d\theta ^2+sin^2\theta d\varphi ^2)],$$
(4)
where $`R=6exp[2\alpha ](1+\dot{\alpha }^2+\ddot{\alpha })`$ and $`\dot{\alpha }=\frac{d\alpha }{d\eta }`$.
The action (3) can be expressed as

$$S=exp[2\alpha ](1+\dot{\alpha }^2+\ddot{\alpha })𝑑\eta =exp[2\alpha ](1\dot{\alpha }^2)𝑑\eta +S_m,$$
(5)
where $`S_m`$ is the surface term given by $`S_m=exp[2\alpha ]\dot{\alpha }`$.The classical field equation (assuming $`S_m=0`$ at the boundary) is

$$\ddot{\alpha }+\dot{\alpha }^2+1=0.$$
(6)
The constraint equation is $`H=0`$i.e.,

$$1+\dot{\alpha }^2=0$$
(7)
and the Wheeler-deWitt equation is

$$\frac{^2\psi }{\alpha ^2}+\frac{n}{\alpha }\frac{\psi }{\alpha }\frac{4}{\mathrm{}^2}exp[4\alpha ]\psi =0,$$
(8)
where, $`n`$ is the operator ordering index. Now instead of removing total derivative term from the action (5) if one introduces a new variable $`Q`$ as

$$Q=\frac{S}{\ddot{\alpha }},$$
(9)
then we have $`Q=exp[2\alpha ]`$.Hence the action (5) can be written in the canonical form as

$$S=[Q(1+\dot{\alpha }^2)+Q\ddot{\alpha }]𝑑\eta =[\dot{Q}\dot{\alpha }Q(1+\dot{\alpha }^2)]𝑑\eta S_m.$$
(10)
one can observe that the surface terms both in (5) and (10) are the same. Apart from the surface term in (10) we have

$$p_\alpha =\frac{L}{\dot{\alpha }}=\dot{Q}2Q\dot{\alpha }$$
(11)
and

$$p_Q=\frac{L}{\dot{Q}}=\dot{\alpha }.$$
(12)
Then the classical field equation with respect to the variation of $`\alpha `$ is

$$\ddot{Q}2Q\ddot{\alpha }2\dot{Q}\dot{\alpha }=0.$$
(13)
One can observe that the above field equation is identically satisfied by equation $`Q=exp(2\alpha )`$. The other field equation is

$$\ddot{\alpha }+\dot{\alpha }^2+1=0.$$
(14)
Hence,the classical field equations do not change even with the introduction of the new variable. We now express the Hamiltonian constraint in the phase space variables,so

$$H=p_\alpha p_Q+Qp_Q^2+Q=0.$$
(15)
Now canonical quantization should be performed with basic variables viz, $`\alpha `$ and $`\dot{\alpha }`$ (Boulware et al). Let $`\dot{\alpha }=x`$,so we replace $`p_Q`$ by $`x`$ and since $`Q=\frac{S}{\ddot{\alpha }}=\frac{L}{\ddot{\alpha }}=\frac{L}{\dot{x}}=p_x`$, so $`Q`$ should be replaced by $`p_x`$. Hence

$$H=xp_\alpha x^2p_xp_x=0.$$
(16)
Hence the Wheeler-deWitt equation in this case turns out to be

$$\frac{\psi }{\alpha }=\frac{1+x^2}{x}\frac{\psi }{x},$$
(17)
whose solution is

$$\psi =\psi _0exp(c\alpha )(1+x^2)^{c/2},$$
(18)
where $`c`$ is a constant. Clearly this does not satisfy equation (8). Hence the equation (17) is not the correct Wheeler-deWitt equation. Therefore we conclude that in order to obtain the correct quantum dynamics one should first remove all the total derivative terms from the action and then introduce the new variable if at all required.

## III Curvature Squared Action And The Correct Wheeler-deWitt Equation

We assume the action as

$$S=\frac{m}{4}(1+\dot{\alpha }^2+\ddot{\alpha })^2𝑑\eta ,$$
(19)
where the background geometry is given by metric (4).According to our proposal we remove the total derivative terms from the action (19).Hence

$$S=\frac{m}{4}[(1+\dot{\alpha }^2)^2+\ddot{\alpha }^2]𝑑\eta +S_m,$$
(20)
where $`m=12\pi ^2\beta `$ and $`S_m=\frac{m}{6}(3+\dot{\alpha }^2)`$ .Now we introduce the new variable to cast the action (20) in the canonical form

$$\frac{m}{4}Q=\frac{S}{\ddot{\alpha }}=m\ddot{\alpha }/2.$$
(21)
Hence

$$S=m/4[\dot{\alpha }\dot{Q}(1+\dot{\alpha }^2)^2+Q^2/4]𝑑\eta +S_{m_1}$$
(22)
where $`S_{m_1}`$ is the surface term given by

$$S_{m_1}=\frac{m}{6}\dot{\alpha }(3+\dot{\alpha }^2+3\ddot{\alpha }).$$
(23)
Assuming $`S_{m_1}`$ vanishes at the boundary, the classical field equations are

$$\ddot{Q}12\dot{\alpha }^2\ddot{\alpha }4\ddot{\alpha }=0,$$
(24)
and

$$Q=2\ddot{\alpha }.$$
(25)
The definition of $`Q`$ in (21) is thus recovered in (25) and the equation (24) is the correct classical field equation as can be observed by replacing $`Q`$ by $`2\ddot{\alpha }`$ . Now the Hamiltonian constraint equation is

$$H=\frac{4}{m}p_\alpha p_Q+\frac{64}{m^3}p_Q^4+\frac{8}{m}p_Q^2\frac{m}{16}Q^2+\frac{m}{4},$$
(26)
where $`p_\alpha `$ and $`p_Q`$ are the canonical momenta corresponding to $`\alpha `$ and $`Q`$ respectively. Since the canonical quantization should be performed with basic variables viz., $`\alpha `$ and $`\dot{\alpha }`$, therefore choosing $`\dot{\alpha }=x`$, we replace $`p_Q`$ by $`\frac{mx}{4}`$ and $`Q`$ by $`\frac{4p_x}{m}`$ .Hence

$$H=xp_\alpha \frac{p_x^2}{m}+\frac{m}{4}(1+x^2)^2.$$
(27)
The corresponding Wheeler-deWitt equation is

$$i\mathrm{}\frac{\psi }{\alpha }=\frac{\mathrm{}^2}{mx}\frac{^2\psi }{x^2}+\frac{n\mathrm{}^2}{mx^2}\frac{\psi }{x}+\frac{m}{4x}(1+x^2)^2\psi ,$$
(28)
where $`n`$ is the operator ordering index. Though the Wheeler-deWitt equation (28) looks similar to the Schr$`\ddot{o}`$dinger equation it differs from that obtained by Horowitz . For $`n=0`$, the first derivative term in the right hand side of (28) disappears, while the Wheeler-deWitt equation obtained by Horowitz always retains the first derivative term on the right hand side. We have also obtained an effective potential $`V(x)`$ in the process,which has not been obtained by Horowitz. The equation (28) can be written as

$$i\mathrm{}\frac{\psi }{\alpha }=\widehat{H}_0\psi ,$$
(29)
where,

$$\widehat{H}_0=\frac{\mathrm{}^2}{mx}(\frac{^2}{x^2}+\frac{n}{x}\frac{}{x})+\frac{m}{4x}(1+x^2)^2.$$
(30)
It is noted that $`\widehat{H}_0`$ operator is hermitian and as a consequence we obtain the equation of continuity

$$\frac{\rho }{\alpha }+𝐉=\mathrm{𝟎},$$
(31)
where $`\rho `$ and $`𝐉`$ are the probability density and the current density respectively for $`n=1`$.The $`\rho `$ and $`𝐉`$ are given by $`\rho =\psi ^{}\psi `$ and $`𝐉=(𝐉_𝐱,\mathrm{𝟎},\mathrm{𝟎})`$; where

$$J_x=\frac{i\mathrm{}}{mx}(\psi ^{}\psi _x\psi \psi _x^{}).$$
(32)
For other operator ordering index $`n`$ we can also obtain the continuity equation, but with respect to a new variable $`y`$ which is functionally related to $`x`$ only. It is noted that no such continuity equation can be obtained from the Wheeler-deWitt equation presented by Horowitz . In analogy with the quantum mechanics it is apparent from (29) and (31) that the variable $`\alpha `$ can be identified as the time parameter in quantum comosmology, and the variable $`x`$ acts as a spatial coordinate variable in the quantum cosmology. The coordinate variable $`x=\dot{\alpha }`$, which is just the expansion parameter and the Hamiltonian operator $`\widehat{H}_0`$ diverges at the bounce of the universe i.e., $`\dot{\alpha }=0`$. Further in the weak energy limit, the contribution of the kinetic energy is sufficiently small with respect to the potential energy in the Hamiltonian $`H_0`$. At that regime the Hamiltonian is almost dominated by the potential energy. Now the extremum of the potential $`V(x)`$ yields

$$1+\dot{\alpha }^2=0$$
(33)
or,

$$\dot{\alpha }^21/3=0.$$
(34)
The equation (33) is the classical vacuum Einstein equation. It is to be noted that the equation (33) which we obtain here is not surprising, rather it should be a desirable feature of higher derivative gravity theory at the weak energy limit. Equation (34) on the other hand is just the equation admitting inflation, supporting the idea of Starobinsky to explain the inflationary scenario without invoking phase transition.

## IV Solution Of The Wheeler-deWitt Equation

The Hamilton Jacobi equation can be obtained from (29) and is given by

$$\frac{A}{\alpha }+\frac{1}{mx}(\frac{A}{x})^2\frac{m}{4x}(1+x^2)^2=0,$$
(35)
where $`A`$ is the Hamilton Jacobi function. This is the exact form of the classical Hamiltonian equation given by

$$\frac{A}{\alpha }+H_0=0,$$
(36)
where $`H_0`$ is the Hamiltonian and is given by $`H_0=\frac{p_x^2}{mx}\frac{m}{4x}(1+x^2)^2`$. The parameter $`\alpha `$ in (36) or (35) is simply the time parameter as we have already claimed from equations (28) and (29) in the previous section.

A particular solution of (28) for $`n=0`$ is given by

$$\psi =\psi _0exp[\alpha +\frac{im}{2\mathrm{}}(x+\frac{x^3}{3})].$$
(37)
The wave function $`\psi `$ is well behaved for all values of $`x`$ (i.e.,for any expansion parameter) and at the vanishing three space volume. The probability density $`\psi ^{}\psi `$ is just $`|\psi _0|^2exp(2\alpha )`$, and it is a real quantity and propor tional to the scale factor of the universe. However for normalization of the probability density one needs boundary condition of the universe. Recntly, Bachmann and Schmidt  have solved the Wheeler-deWitt equation for a minimally coupled scalar field in Bianchi type-I model and shown that the notion of a cosmological quantum boundary is well defined. The solution (37) is not a semiclassical one, as the terms within the exponential of (37) does not satisfy the Hamilton-Jacobi equation. Therefore it is not clear wheather such boundary can be called upon in the present context.

## V Curvature Squared Action In Proper Time Coordinate

In this section our first attempt is to show that the Wheeler-deWitt equation remains unchanged even in the proper time coordinate and then we compare our formalism with that of Schmidt  formulated earlier. For this purpose we consider the FRW metric in proper time coordinate given by

$$ds^2=dt^2a^2[\frac{dr^2}{1kr^2}+r^2(d\theta ^2+sin^2\theta d\varphi ^2)].$$
(38)
Removing the total derivative terms the action can now be cast in the following form

$$S=\frac{m}{4}[a\ddot{a}^2+\frac{(\dot{a}^2+k)^2}{a}]𝑑t+S_1,$$
(39)
Where dot represents derivative with respect to the proper time and $`S_1=\frac{m}{2}(k\dot{a}+\dot{a}^3/3)`$. Introducing the new variable

$$Q=\frac{4}{m}\frac{S}{\ddot{a}}=2a\ddot{a}$$
(40)
and expressing the action in the canonical form we have

$$S=\frac{m}{4}[\dot{a}\dot{Q}\frac{(\dot{a}^2+k)^2}{a}+\frac{Q^2}{4a}]𝑑t+S_2,$$
(41)
where $`S_2=\frac{m}{6}\dot{a}(3k+\dot{a}^2+3a\ddot{a})`$. The canonical momenta are

$$p_a=\frac{L}{\dot{a}}=\frac{m}{4}[\dot{Q}4\dot{a}(\dot{a}^2+k)/a]$$
(42)
and

$$p_Q=\frac{L}{\dot{Q}}=m\dot{a}/4.$$
(43)
It is now possible to find the classical field equations, one of which turns out to be the definition of $`Q`$ and the other is found to resemble with one already obtained in section 3. The Hamiltonian turns out to be

$$H=\frac{4}{m}(p_ap_Q+\frac{16p_Q^4}{m^2a}+\frac{2kp_Q^2}{a}+\frac{m^2k^2}{16a}\frac{m^2Q^2}{64a}).$$
(44)
Now, for canonical quantization we invoke the basic variables, i.e., choose $`\dot{a}=x`$, replace $`Q`$ by $`4p_y/m`$ and $`p_Q`$ by $`my/4`$. Thus the Hamiltonian turns out to be

$$H=yp_y\frac{p_y^2}{ma}+\frac{m}{4a}(y^2+k)^2,$$
(45)
whose quantum version viz., the Wheeler-deWitt equation is

$$i\mathrm{}a\frac{\psi }{a}=\frac{\mathrm{}^2}{my}(\frac{^2\psi }{y^2}+\frac{n}{y}\frac{\psi }{y})+\frac{m}{4y}(y^2+k)^2,$$
(46)
where $`n`$ is the operator ordering index. Now choosing $`a=e^q`$ the Wheeler-deWitt equation can be written as

$$i\mathrm{}\frac{\psi }{q}=\frac{\mathrm{}^2}{my}(\frac{^2\psi }{y^2}+\frac{n}{y}\frac{\psi }{y})+\frac{m}{4y}(y^2+k)^2.$$
(47)
It is interesting to note that this form of Wheeler-deWitt equation is the same as that obtained in equation (28) of section 3, in conformal time.

## VI Comparison With Schmidt’s Formalism

Let us turn our attention to compare our formalism with that proposed by Schmidt  earlier. For this purpose we choose $`k=0`$ and $`a=e^q`$.Thus the action (39) turns out to be

$$S=\frac{m}{4}\ddot{q}^2e^{3q}𝑑t.$$
(48)
Following the method already proposed, our new variable is

$$Q=2\ddot{q}e^{3q}$$
(49)
and the canonical action is

$$S=\frac{m}{4}[\dot{q}\dot{Q}+\frac{Q^2}{4}e^{3q}]𝑑t+S_3,$$
(50)
vwhere $`S_3=\frac{m}{4}Q\dot{q}`$. The canonical momenta are $`p_q=m\dot{Q}/4`$ and $`p_Q=m\dot{q}/4`$. Hence the Hamiltonian is

$$H=\frac{4}{m}p_qp_Q\frac{m}{16}Q^2e^{3q}.$$
(51)
Introducing basic variable $`x=\dot{q}`$ and replacing $`Q`$ by $`4p_x/m`$ and $`p_Q`$ by $`mx/4`$, we find

$$H=xp_q\frac{p_x^2}{m}e^{3q}.$$
(52)
Now replacing $`q`$ by $`Q_1`$, $`\dot{q}=x`$ by $`Q_2`$, $`p_q=m\dot{Q}/4=\frac{m}{4}\frac{d}{dt}(2\ddot{q}e^{3q})`$ by $`mP_1/4`$ and finally $`p_x=mQ/4=\frac{m}{4}(2\ddot{q}e^{3q})`$ by $`mP_2/4`$ we can express equation (52) as

$$H=\frac{m}{4}(P_1Q_2+\frac{1}{4}P_2^2e^{3Q_1}).$$
(53)
This Hamiltonian other than the factor $`m/4`$ was obtained by Schmidt  following Ostrogradski’s prescription. Though the new variables introduced in both the cases to construct the Hamiltonian are found to match, yet the formalisms differ. In our method after eliminating surface terms from the action we have introduced variables at two stages, first to cast the action in the canonical form for obtaining the classical field equations and then to construct the Hamiltonian suitable for quantization, basic variables have been called upon. On the other hand the basic variables in the Schmidt’s proposal have been introduced from the very begining and there is no prescription suggested to eliminate the surface term. Here lies the difference between the two proposals.The Hamiltonian (53) turns out to be the same since Schmidt has considered the action (48) which is already free from the surface term. It is not difficult to show that Schmidt’s formalism would yield a different Hamiltonian if action (19) would have been considered.

## VII Conclusion

We conclude that whenever a Lagrangian contains terms higher than the first derivative, the correct quantum dynamics would be obtained if one casts the action in the canonical form by introducing a new variable only after removing all the total derivative terms from the action. We have shown that in our proposal there is no change in the classical field equations, but the quantum dynamics changes sharply as it is evident from (29) in comparison with the same equation obtained by Horowitz. Therefor, the quantum dynamics is greatly influenced by the presence of the surface term in the action. Further the equation of continuity (31) identifies the nature of space and time like variables in the minisuperspace and therefore establishes the idea of probality density and current density in quantum cosmology. In the weak energy limit we are able to recover the classical Einstein’s field equations from the quantum dynamics of higher derivative gravity theory. The solution (37) corresponds to a real probability density and it is not a semiclassical solution, however for normalization one needs boundary conditions of the universe.

Acknowledgement
The authors like to thank Dr. S.Biswas for valuable suggestions.


text:
# Higher-rank graphs and their 𝐶^∗-algebras

## 1. Introduction

The $`C^{}`$-algebras of higher-rank graphs of Kumjian and Pask  generalise the higher-rank Cuntz-Krieger algebras of Robertson and Steger  in the same way that the $`C^{}`$-algebras of infinite graphs generalise the original Cuntz-Krieger algebras . In , Kumjian and Pask analysed higher-rank graph algebras using a groupoid model like that used in  and  to analyse graph algebras. The results in  and  were sharpened in  using a direct analysis based on the original arguments used by Cuntz and Krieger in  and ; the analysis of  applies to the algebras of quite general row-finite graphs, and in particular the graphs can have sinks or sources.

Here we carry out a direct analysis of the $`C^{}`$-algebras of row-finite higher-rank graphs. One interesting new feature is the difficulty in extending results to higher-rank graphs with sources: the paths $`\lambda `$ in higher-rank graphs have degrees $`d(\lambda )`$ in $`^k`$ rather than lengths in $`,`$ and vertices may receive edges of some degrees and not of others. To overcome this difficulty we modify the Cuntz-Krieger relation to ensure that Cuntz-Krieger algebras have a spanning family of the usual sort, and identify a local convexity condition under which a higher-rank graph admits a nontrivial Cuntz-Krieger family. We then prove versions of the gauge-invariant uniqueness theorem and the Cuntz-Krieger uniqueness theorem for locally convex higher-rank graphs, extending the results of , and use them to investigate the ideal structure.

The Cuntz-Krieger relation of  involves the spaces $`\mathrm{\Lambda }^p`$ of paths of degree $`p^k`$. Our key technical innovation is the introduction of path spaces $`\mathrm{\Lambda }^p`$ consisting of the paths $`\lambda `$ with $`d(\lambda )p`$ which cannot be extended to paths $`\lambda \mu `$ with $`d(\lambda \mu )p`$; the key Lemmas 3.6 and 3.7 say that the spaces $`\mathrm{\Lambda }^p`$ have combinatorial properties like those of the spaces $`\mathrm{\Lambda }^p`$, and ensure that the $`C^{}`$-algebras behave like Cuntz-Krieger algebras (see Proposition 3.5). These new path spaces would also have simplified the analysis of the core in the $`C^{}`$-algebras of graphs with sinks in \[3, §2\]. Indeed, the $`\mathrm{\Lambda }^q`$ notation works so smoothly that arguments sometimes appear deceptively easy.

## 2. Higher-rank graphs

###### Definitions 2.1.

Given $`k`$, a graph of rank $`k`$ (or $`k`$-graph) $`(\mathrm{\Lambda },d)`$ consists of a countable category $`\mathrm{\Lambda }=(\mathrm{Obj}(\mathrm{\Lambda }),\mathrm{Hom}(\mathrm{\Lambda }),r,s)`$ together with a functor $`d:\mathrm{\Lambda }^k`$, called the degree map, which satisfies the factorisation property: for every $`\lambda \mathrm{\Lambda }`$ and $`m,n^k`$ with $`d(\lambda )=m+n`$, there are unique elements $`\mu ,\nu \mathrm{\Lambda }`$ such that $`\lambda =\mu \nu `$, $`d(\mu )=m`$ and $`d(\nu )=n`$. Elements $`\lambda \mathrm{\Lambda }`$ are called paths. For $`m^k`$ and $`v\mathrm{Obj}(\mathrm{\Lambda })`$, we define $`\mathrm{\Lambda }^m:=\{\lambda \mathrm{\Lambda }:d(\lambda )=m\}`$ and $`\mathrm{\Lambda }^m(v):=\{\lambda \mathrm{\Lambda }^m:r(\lambda )=v\}`$. A morphism between two $`k`$-graphs $`(\mathrm{\Lambda }_1,d_1)`$ and $`(\mathrm{\Lambda }_2,d_2)`$ is a functor $`f:\mathrm{\Lambda }_1\mathrm{\Lambda }_2`$ which respects the degree maps. $`(\mathrm{\Lambda },d)`$ is row-finite if for each $`v\mathrm{Obj}(\mathrm{\Lambda })`$ and $`m^k`$, the set $`\mathrm{\Lambda }^m(v)`$ is finite; $`(\mathrm{\Lambda },d)`$ has no sources if $`\mathrm{\Lambda }^m(v)\mathrm{}`$ for all $`v\mathrm{Obj}(\mathrm{\Lambda })`$ and $`m^k`$.

The factorisation property says that there is a unique path of degree $`0`$ at each vertex, and hence allows us to identify $`\mathrm{Obj}(\mathrm{\Lambda })`$ with $`\mathrm{\Lambda }^0`$.

###### Examples 2.2.

(i) Let $`E`$ be a directed graph, and $`l:E^{}`$ the length function on the path space. Then $`(E^{},l)`$ is a $`1`$-graph.

(ii) Let $`k`$, let $`m(\{\mathrm{}\})^k`$, and define a partial ordering on $`^k`$ by $`mnm_in_i`$ for all $`i`$. $`(\mathrm{\Omega }_{k,m},d)`$ is the $`k`$-graph with category $`\mathrm{\Omega }_{k,m}`$ defined by

$$\mathrm{Obj}(\mathrm{\Omega }_{k,m}):=\{p^k:pm\},$$

$$\mathrm{Hom}(\mathrm{\Omega }_{k,m}):=\{(p,q)\mathrm{Obj}(\mathrm{\Omega }_{k,m})\times \mathrm{Obj}(\mathrm{\Omega }_{k,m}):pq\},$$

$`r(p,q):=p`$, $`s(p,q):=q`$, and degree map $`d(p,q):=qp`$.

When each $`m_i=\mathrm{}`$, the resulting $`k`$-graph is the main example $`\mathrm{\Omega }_k`$ used in .

When $`m^k`$, the resulting $`k`$-graphs are important because every path $`\lambda `$ of degree $`m`$ in a $`k`$-graph $`\mathrm{\Lambda }`$ determines a graph morphism $`x_\lambda :\mathrm{\Omega }_{k,m}\mathrm{\Lambda }`$: set $`x_\lambda (p,q):=\lambda ^{\prime \prime }`$ where $`\lambda =\lambda ^{}\lambda ^{\prime \prime }\lambda ^{\prime \prime \prime }`$ and $`d(\lambda ^{})=p`$, $`d(\lambda ^{\prime \prime \prime })=mq`$. Indeed, this sets up a bijection between $`\mathrm{\Lambda }^m`$ and the graph morphisms $`x:\mathrm{\Omega }_{k,m}\mathrm{\Lambda }`$.

To visualise a $`k`$-graph, we draw its *$`1`$-skeleton*, which is the graph with vertex set $`\mathrm{\Lambda }^0`$, edge set $`_{i=1}^k\mathrm{\Lambda }^{e_i}`$, range and source maps inherited from $`\mathrm{\Lambda }`$, and with the edges of different degrees distinguished using $`k`$ different colours. (In the pictures here, we imagine that dashed lines are red and dotted lines are blue.) For example, the $`1`$-skeleton of $`\mathrm{\Omega }_{2,(3,2)}`$ is

(2.1) $``$$``$$``$$``$$``$$``$$``$$``$$``$$``$$``$$``$....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................$`(0,0)`$$`(3,2)`$$`g`$$`e`$$`f`$$`h`$$`v`$
Because the edges represent morphisms in a category, we write $`eg`$ for the path in the $`1`$-skeleton which consists of $`g`$ followed by $`e`$.

The $`1`$-skeleton of a $`k`$-graph does not always suffice to determine the $`k`$-graph: we have to say how the edges in $`\mathrm{\Lambda }^{e_i}`$ fit together to give elements of $`\mathrm{\Lambda }^n`$. We interpret elements of $`\mathrm{\Lambda }^n`$ as commuting diagrams of shape $`n`$ in which the morphisms correspond to edges in the given $`1`$-skeleton. Thus, for example, in a $`2`$-graph with $`1`$-skeleton

(2.2) $``$$``$.............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................$`u`$$`v`$$`f`$$`e`$$`g`$$`h`$
where the dashed lines have degree $`(0,1)`$, the unique example of a $`(3,1)`$ path $`\lambda `$ with $`r(\lambda )=u`$ and $`s(\lambda )=v`$ is

$``$$``$$``$$``$$``$$``$$``$$``$................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................$`u`$$`u`$$`u`$$`u`$$`v`$$`v`$$`v`$$`v`$$`g`$$`g`$$`e`$$`e`$$`f`$$`h`$$`f`$$`g`$$`g`$$`h`$
From such a picture we can read off the factorisations of $`\lambda `$: $`\lambda =gegh=gefg=gheg=fgeg`$.

When $`k=2`$, it suffices to specify the factorisations of paths $`ef`$ of length $`2`$ in the $`1`$-skeleton for which $`e`$ and $`f`$ have different colours. Any collection $`S`$ of squares which contains each such bi-coloured path exactly once determines a unique $`2`$-graph $`\mathrm{\Lambda }`$ with the given $`1`$-skeleton and $`\mathrm{\Lambda }^{(1,1)}=S`$ (see \[7, §6\]); there may be no such collection, or there may be many. For the $`1`$-skeleton in (2.2), the factorisation property implies that $`\mathrm{\Lambda }^{(1,1)}`$ consists of the two squares

$``$$``$$``$$``$................................................................................................................................................................................................................................................................................................$`g`$$`g`$$`f`$$`h`$$``$$``$$``$$``$................................................................................................................................................................................................................................................................................................$`e`$$`e`$$`h`$$`f`$
and hence there is exactly one $`2`$-graph with this $`1`$-skeleton. However, if we add one extra edge to the $`1`$-skeleton in (2.2), we have to make a choice. For example, in the $`1`$-skeleton

$``$$``$.............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................$`u`$$`v`$$`f`$$`e`$$`k`$$`g`$$`h`$
there are four possible bi-coloured paths from $`u`$ to $`v`$, and we have to decide how to pair these off into paths of degree $`(1,1)`$: either

$``$$``$$``$$``$................................................................................................................................................................................................................................................................................................$`e`$$`e`$$`h`$$`f`$or$``$$``$$``$$``$................................................................................................................................................................................................................................................................................................$`k`$$`e`$$`h`$$`f`$
is a path of degree $`(1,1)`$, and once we have decided which, the other pairing is determined by the factorisation property.

For $`k>2`$, a collection $`S`$ of squares may not be the set of paths of degree $`(1,1)`$ for any $`k`$-graph with the given $`1`$-skeleton. However, \[6, Theorem 2.1\] tells us that it suffices to know that for every tri-coloured path $`efg`$ in the $`1`$-skeleton, the six squares on the sides of the cube

$``$$``$$``$$``$$``$$``$$``$$``$............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................$`e`$$`f`$$`g`$
give a well-defined path of degree $`(1,1,1)`$. More precisely, we need to know that the path $`g^2f^2e^2`$ with reverse colouring obtained by successively filling in the three visible squares agrees with the path $`g_2f_2e_2`$ obtained by filling in the three invisible squares:

$``$$``$$``$$``$$``$$``$$``$.........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................$`e`$$`f`$$`g`$$`g^1`$$`f^1`$$`g^2`$$`e^1`$$`f^2`$$`e^2`$$``$$``$$``$$``$$``$$``$$``$.........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................$`e`$$`f`$$`g`$$`f_1`$$`e_1`$$`g_1`$$`g_2`$$`f_2`$$`e_2`$
(In the left-hand diagram, we first use the right hand face to determine $`g^1f^1`$, then use the front to find $`g^2e^1`$, and then the top to find $`f^2e^2`$; in the right-hand diagram, we use the bottom first.) A family of squares which contains each bi-coloured path exactly once and which satisfies this condition on cubes determines a unique $`k`$-graph (see Theorem 2.1 and Remark 2.3 in ).

## 3. Higher-rank graphs and their $`C^{}`$-algebras

For a row-finite $`k`$-graph $`\mathrm{\Lambda }`$ with no sources the authors of  define a Cuntz-Krieger $`\mathrm{\Lambda }`$-family to be a family of partial isometries $`\{s_\lambda :\lambda \mathrm{\Lambda }\}`$ such that $`\{s_v:v\mathrm{\Lambda }^0\}`$ are mutually orthogonal projections, $`s_\lambda s_\mu =s_{\lambda \mu }`$ for all $`\lambda ,\mu \mathrm{\Lambda }`$ with $`r(\mu )=s(\lambda )`$, $`s_\lambda ^{}s_\lambda =s_{s(\lambda )}`$ for all $`\lambda \mathrm{\Lambda }`$, and

(3.1)
$$s_v=\underset{\lambda \mathrm{\Lambda }^m(v)}{}s_\lambda s_\lambda ^{}\text{for all }v\mathrm{\Lambda }^0\text{ and }m^k\text{.}$$

When $`\mathrm{\Lambda }`$ has sources there is trouble with relation (3.1) in the sense that $`\mathrm{\Lambda }^m(v)`$ may be nonempty for some values of $`m`$ and empty for others. If a vertex $`v\mathrm{\Lambda }^0`$ receives no edges we could just impose no relation for that vertex as is done for directed graphs in ; if $`v`$ receives edges of some degrees but not others, then we have to change (3.1) in more subtle ways. The obvious strategy is to observe that when $`\mathrm{\Lambda }^{e_i}(v)\mathrm{}`$ for all $`i\{1,\mathrm{},k\}`$ and $`v\mathrm{\Lambda }^0`$, (3.1) is equivalent to (3.2), and then to replace (3.1) with

(3.2)
$$s_v=\underset{\lambda \mathrm{\Lambda }^{e_i}(v)}{}s_\lambda s_\lambda ^{}\text{for }v\mathrm{\Lambda }^0\text{ and }1ik\text{ with }\mathrm{\Lambda }^{e_i}(v)\mathrm{}\text{.}$$

While this works for a large class of $`k`$-graphs (see Proposition 3.11), in general there are problems. We consider the following key example.

(3.3) $``$$``$$``$.....................................................................................................................................................................................................$`e`$$`f`$$`v`$$`w`$$`z`$
In the $`2`$-graph of (3.3), relation (3.2) would say $`s_es_e^{}=s_v=s_fs_f^{}`$. But then $`s_e^{}s_f`$ would be a partial isometry with source projection $`s_w`$ and range projection $`s_z`$, and consequently would not be expressible as a sum of partial isometries of the form $`s_\lambda s_\mu ^{}`$; thus the $`C^{}`$-algebra generated by $`\{s_f,s_e,s_v\}`$ would not look like a Cuntz-Krieger algebra. This problem does not arise in the $`2`$-graph given by (2.1): the compositions $`eg`$ and $`fh`$ define the same path in $`\mathrm{\Lambda }^{(1,1)}`$, so $`s_es_g=s_fs_h`$, and $`s_e^{}s_f=s_gs_h^{}`$.

Our adaptation of (3.1) retains relations for each $`m^k`$, but involves sums over paths which extend as far as possible in the direction $`m`$. Formally, we introduce:

###### Definition 3.1.

Let $`(\mathrm{\Lambda },d)`$ be a $`k`$-graph. For $`q^k`$ and $`v\mathrm{\Lambda }^0`$ we define

$$\mathrm{\Lambda }^q:=\{\lambda \mathrm{\Lambda }:d(\lambda )q,\text{ and }\mathrm{\Lambda }^{e_i}(s(\lambda ))=\mathrm{}\text{ when }d(\lambda )+e_iq\},$$

and

$$\mathrm{\Lambda }^q(v):=\{\lambda \mathrm{\Lambda }^q:r(\lambda )=v\}$$

###### Remarks 3.2.

Notice that $`\mathrm{\Lambda }^q(v)`$ is never empty: if there are no nontrivial paths of degree less than or equal to $`q`$, then $`\mathrm{\Lambda }^q(v)=\{v\}`$; in particular, if $`r^1(v)=\mathrm{}`$, then $`\mathrm{\Lambda }^q(v)=\{v\}`$ for all $`q^k`$. The sets $`\mathrm{\Lambda }^q`$ and $`\mathrm{\Lambda }^q(v)`$ are used in arguments where the $`\mathrm{\Lambda }^q`$ and $`\mathrm{\Lambda }^q(v)`$ may have been used in ; when $`\mathrm{\Lambda }`$ has no sources, $`\mathrm{\Lambda }^q=\mathrm{\Lambda }^q`$.

###### Definition 3.3.

Let $`\mathrm{\Lambda }`$ be a row-finite $`k`$-graph. A Cuntz-Krieger $`\mathrm{\Lambda }`$-family in a $`C^{}`$-algebra $`B`$ consists of a family of partial isometries $`\{s_\lambda :\lambda \mathrm{\Lambda }\}`$ satisfying the Cuntz-Krieger relations:

* $`\{s_v:v\mathrm{\Lambda }^0\}`$ is a family of mutually orthogonal projections,
* $`s_{\lambda \mu }=s_\lambda s_\mu `$ for all $`\lambda ,\mu \mathrm{\Lambda }`$ with $`s(\lambda )=r(\mu )`$,
* $`s_\lambda ^{}s_\lambda =s_{s(\lambda )}`$,
* $`s_v={\displaystyle \underset{\lambda \mathrm{\Lambda }^m(v)}{}}s_\lambda s_\lambda ^{}`$ for all $`v\mathrm{\Lambda }^0`$ and $`m^k`$.

###### Examples 3.4.

For the $`2`$-graph given by (2.1), the relations at $`v`$ say $`s_v=s_es_e^{}`$ for $`m=(1,0)`$, $`s_v=s_fs_f^{}`$ for $`m=(0,1)`$, and $`s_v=s_{eg}s_{eg}^{}=s_{fh}s_{fh}^{}`$ for $`m=(1,1)`$. For any $`m^2`$ with $`m(1,1)`$, the relation at $`v`$ for $`m`$ reduces to that for $`(1,1)`$.

In the $`2`$-graph given by (3.3), the relation $`s_v=s_es_e^{}+s_fs_f^{}`$ for $`m=(1,1)`$ combines with $`s_es_e^{}=s_v=s_fs_f^{}`$ to force everything to be zero.

The following proposition shows that our Cuntz-Krieger relations yield the usual type of spanning family (see Remark 3.8 (1)).

###### Proposition 3.5.

Let $`(\mathrm{\Lambda },d)`$ be a row-finite $`k`$-graph and let $`\{s_\lambda :\lambda \mathrm{\Lambda }\}`$ be a Cuntz-Krieger $`\mathrm{\Lambda }`$-family. Then for $`\lambda ,\mu \mathrm{\Lambda }`$ and $`q^k`$ with $`d(\lambda ),d(\mu )q`$ we have

(3.4)
$$s_\lambda ^{}s_\mu =\underset{\begin{array}{c}\lambda \alpha =\mu \beta \\ \lambda \alpha \mathrm{\Lambda }^q\end{array}}{}s_\alpha s_\beta ^{}.$$

To prove this, we need some properties of $`\mathrm{\Lambda }^q`$.

###### Lemma 3.6.

Let $`(\mathrm{\Lambda },d)`$ be a $`k`$-graph, $`\lambda \mathrm{\Lambda }^m`$, and $`\alpha \mathrm{\Lambda }^n(s(\lambda ))`$. Then $`\lambda \alpha \mathrm{\Lambda }^{m+n}`$.

###### Proof.

We know $`d(\lambda \alpha )m+n`$. Suppose there exists $`i`$ such that $`d(\lambda \alpha )+e_im+n`$. If $`d(\alpha )+e_in`$, then $`\mathrm{\Lambda }^{e_i}(s(\lambda \alpha ))=\mathrm{\Lambda }^{e_i}(s(\alpha ))=\mathrm{}`$, so suppose not. Then $`d(\alpha ),e_i=n,e_i`$, so $`d(\lambda \alpha )+e_im+n`$ implies that $`d(\lambda )+e_im`$. But $`\lambda \mathrm{\Lambda }^m`$, so $`\mathrm{\Lambda }^{e_i}(s(\lambda ))=\mathrm{}`$. Now suppose that there exists $`\beta \mathrm{\Lambda }^{e_i}(s(\lambda \alpha ))=\mathrm{\Lambda }^{e_i}(s(\alpha ))`$. Then by the factorisation property there exist $`\mu _1,\mu _2\mathrm{\Lambda }`$ such that $`\mu _1\mu _2=\alpha \beta `$ and $`d(\mu _1)=e_i`$. But then $`\mu _1\mathrm{\Lambda }^{e_i}(s(\lambda ))`$, a contradiction. Therefore $`\mathrm{\Lambda }^{e_i}(s(\lambda \alpha ))=\mathrm{}`$, and $`\lambda \alpha \mathrm{\Lambda }^{m+n}`$. ∎

###### Lemma 3.7.

Let $`(\mathrm{\Lambda },d)`$ be a row-finite $`k`$-graph and let $`\{s_\lambda :\lambda \mathrm{\Lambda }\}`$ be a Cuntz-Krieger $`\mathrm{\Lambda }`$-family. Then for $`q^k`$ and $`\lambda ,\mu \mathrm{\Lambda }^q`$, $`s_\lambda ^{}s_\mu =\delta _{\lambda ,\mu }s_{s(\lambda )}`$.

###### Proof.

The Cuntz-Krieger relations (1) and (4) tell us that the projections $`\{s_\alpha s_\alpha ^{}:\alpha \mathrm{\Lambda }^q\}`$ are mutually orthogonal. Cuntz-Krieger relations (2) and (3) then give

$`s_\lambda ^{}s_\mu =(s_\lambda ^{}s_\lambda )s_\lambda ^{}s_\mu (s_\mu ^{}s_\mu )`$ $`=s_\lambda ^{}(s_\lambda s_\lambda ^{})(s_\mu s_\mu ^{})s_\mu =\delta _{\lambda ,\mu }s_{s(\lambda )}.`$
###### Proof of Proposition 3.5.

$`s_\lambda ^{}s_\mu `$ $`=s_{s(\lambda )}s_\lambda ^{}s_\mu s_{s(\mu )}\text{using Definition }\text{3.3}\text{ (2)}`$
$`=\left({\displaystyle \underset{\alpha \mathrm{\Lambda }^{qd(\lambda )}(s(\lambda ))}{}}s_\alpha s_\alpha ^{}\right)s_\lambda ^{}s_\mu \left({\displaystyle \underset{\beta \mathrm{\Lambda }^{qd(\mu )}(s(\mu ))}{}}s_\beta s_\beta ^{}\right)`$
using Definition 3.3 (4)
$`=\left({\displaystyle \underset{\alpha \mathrm{\Lambda }^{qd(\lambda )}(s(\lambda ))}{}}s_\alpha s_{\lambda \alpha }^{}\right)\left({\displaystyle \underset{\beta \mathrm{\Lambda }^{qd(\mu )}(s(\mu ))}{}}s_{\mu \beta }s_\beta ^{}\right)`$
using Definition 3.3 (2)
$`={\displaystyle \underset{\alpha \mathrm{\Lambda }^{qd(\lambda )}(s(\lambda ))}{}}{\displaystyle \underset{\beta \mathrm{\Lambda }^{qd(\mu )}(s(\mu ))}{}}s_\alpha s_{\lambda \alpha }^{}s_{\mu \beta }s_\beta ^{}`$
$`={\displaystyle \underset{\begin{array}{c}\lambda \alpha =\mu \beta \\ \lambda \alpha \mathrm{\Lambda }^q(r(\lambda ))\end{array}}{}}s_\alpha s_{s(\alpha )}s_\beta ^{}\text{ by Lemma }\text{3.6}\text{ and Lemma }\text{3.7}`$
$`={\displaystyle \underset{\begin{array}{c}\lambda \alpha =\mu \beta \\ \lambda \alpha \mathrm{\Lambda }^q(r(\lambda ))\end{array}}{}}s_\alpha s_\beta ^{}\text{using Definition }\text{3.3}\text{ (2)}`$
###### Remarks 3.8.

(1) Proposition 3.5 implies that

$$C^{}(\{s_\lambda :\lambda \mathrm{\Lambda }\})=\overline{\mathrm{span}}\{s_\alpha s_\beta ^{}:s(\beta )=s(\alpha )\}.$$

(2) When $`q=d(\lambda )d(\mu )`$, if $`\lambda \alpha =\mu \beta `$ and $`\lambda \alpha \mathrm{\Lambda }^q(r(\lambda ))`$, then $`d(\lambda \alpha )=d(\mu \beta )=q`$. Notice that if we take $`\lambda =\mu `$ in Proposition 3.5, then the lemma reduces to relation (4) of Definition 3.3 at the vertex $`s(\lambda )`$. Hence (4) could be replaced with relation (3.4) from Proposition 3.5: this relation would be harder to verify in examples, but might provide more insight.

Given a row-finite $`k`$-graph $`(\mathrm{\Lambda },d)`$, there is a $`C^{}`$-algebra $`C^{}(\mathrm{\Lambda })`$ generated by a universal Cuntz-Krieger $`\mathrm{\Lambda }`$-family $`\{s_\lambda :\lambda \mathrm{\Lambda }\}`$ (see \[2, §1\]); in other words, for each Cuntz-Krieger $`\mathrm{\Lambda }`$-family $`\{t_\lambda :\lambda \mathrm{\Lambda }\}`$, there is a homomorphism $`\pi :C^{}(\mathrm{\Lambda })C^{}(\{t_\lambda \})`$ such that $`\pi (s_\lambda )=t_\lambda `$ for every $`\lambda \mathrm{\Lambda }`$. Contrary to our experience with directed graphs and their $`C^{}`$-algebras, it is not straightforward to construct Cuntz-Krieger $`\mathrm{\Lambda }`$-families $`\{t_\lambda \}`$ in which all the partial isometries $`t_\lambda `$ are nonzero; in fact, as we saw in Examples 3.4, the $`2`$-graph of (3.3) admits no such families. We will show that the existence of nontrivial Cuntz-Krieger families is characterised by a local convexity condition on the $`k`$-graph.

###### Definition 3.9.

A $`k`$-graph $`(\mathrm{\Lambda },d)`$ is locally convex if, for all $`v\mathrm{\Lambda }^0,i,j\{1,\mathrm{},k\}`$ with $`ij,\lambda \mathrm{\Lambda }^{e_i}(v)`$ and $`\mu \mathrm{\Lambda }^{e_j}(v)`$, $`\mathrm{\Lambda }^{e_j}(s(\lambda ))`$ and $`\mathrm{\Lambda }^{e_i}(s(\mu ))`$ are nonempty.

###### Remark 3.10.

The $`2`$-graph of (3.3) is not locally convex since $`r^1(u)=r^1(w)=\mathrm{}`$. Every $`1`$-graph is locally convex, as is every higher-rank graph without sources.

###### Proposition 3.11.

Let $`(\mathrm{\Lambda },d)`$ be a locally convex row-finite $`k`$-graph. Then the Cuntz-Krieger relation (4) of Definition 3.3 is equivalent to (3.2).

The crucial idea in the proof of Proposition 3.11 is that, when the $`k`$-graph is locally convex, the factorisation property of paths extends to elements of $`\mathrm{\Lambda }^m(v)`$. This is not the case for the $`2`$-graph of (3.3): the path $`f`$ is in $`\mathrm{\Lambda }^{(1,1)}(v)`$, but does not factor as $`\lambda ^{}\lambda ^{\prime \prime }`$ with $`\lambda ^{}\mathrm{\Lambda }^{(1,0)}(v)`$.

###### Lemma 3.12.

Let $`(\mathrm{\Lambda },d)`$ be a $`k`$-graph, and suppose that $`(\mathrm{\Lambda },d)`$ is locally convex. Then for all $`v\mathrm{\Lambda }^0`$, $`m^k\{0\}`$, and $`j\{1,\mathrm{},k\}`$ with $`m,e_j1`$, we have

$$\mathrm{\Lambda }^m(v)=\{\lambda ^{}\lambda ^{\prime \prime }\mathrm{\Lambda }:\lambda ^{}\mathrm{\Lambda }^{me_j}(v)\text{ and }\lambda ^{\prime \prime }\mathrm{\Lambda }^{e_j}(s(\lambda ^{}))\}.$$

###### Proof.

Fix $`j\{1,\mathrm{},k\}`$ with $`m,e_j1`$; there is at least one such $`j`$ since $`m0`$. If $`\lambda ^{}\lambda ^{\prime \prime }\mathrm{\Lambda }`$ satisfies $`\lambda ^{}\mathrm{\Lambda }^{me_j}(v)`$ and $`\lambda ^{\prime \prime }\mathrm{\Lambda }^{e_j}(s(\lambda ^{}))`$, then by Lemma 3.6 $`\lambda ^{}\lambda ^{\prime \prime }\mathrm{\Lambda }^m(v)`$, so we have the containment

$$\mathrm{\Lambda }^m(v)\{\lambda ^{}\lambda ^{\prime \prime }\mathrm{\Lambda }:\lambda ^{}\mathrm{\Lambda }^{me_j}(v)\text{ and }\lambda ^{\prime \prime }\mathrm{\Lambda }^{e_j}(s(\lambda ^{}))\}.$$

Now suppose $`\lambda \mathrm{\Lambda }^m(v)`$. Since $`d(\lambda )m`$, we must have:

* $`d(\lambda ),e_j<m,e_j`$, or
* $`d(\lambda ),e_j=m,e_j`$.

First suppose (1) holds. Then $`d(\lambda )me_j`$, and hence $`\lambda \mathrm{\Lambda }^{me_j}`$. Also $`\mathrm{\Lambda }^{e_j}(s(\lambda ))=\mathrm{}`$ (since $`\lambda \mathrm{\Lambda }^m(v)`$, and hence $`\mathrm{\Lambda }^{e_j}(s(\lambda ))=\{s(\lambda )\}`$). Taking $`\lambda ^{}=\lambda `$ and $`\lambda ^{\prime \prime }=s(\lambda )`$ gives $`\lambda =\lambda ^{}\lambda ^{\prime \prime }`$ with $`\lambda ^{}\mathrm{\Lambda }^{me_j}(v)`$ and $`\lambda ^{\prime \prime }\mathrm{\Lambda }^{e_j}(s(\lambda ^{}))`$. Now suppose (2) holds. Then we can factorise $`\lambda =\lambda ^{}\lambda ^{\prime \prime }`$ with $`d(\lambda ^{\prime \prime })=e_j`$, so $`\lambda ^{\prime \prime }\mathrm{\Lambda }^{e_j}(s(\lambda ^{}))`$. We claim that $`\lambda ^{}\mathrm{\Lambda }^{me_j}(v)`$. To see this, suppose that $`\lambda ^{}\mathrm{\Lambda }^{me_j}(v)`$. Then there exists $`i`$ such that $`d(\lambda ^{})+e_ime_j`$ and $`\mathrm{\Lambda }^{e_i}(s(\lambda ^{}))\mathrm{}`$, say $`\alpha \mathrm{\Lambda }^{e_i}(s(\lambda ^{}))`$. By (2) we know that $`d(\lambda ^{}),e_j=me_j,e_j`$, so $`ij`$. Since $`\mathrm{\Lambda }`$ is locally convex there is a $`\beta \mathrm{\Lambda }^{e_i}(s(\lambda ^{\prime \prime }))`$, but this implies $`d(\lambda \beta )m`$, a contradiction since $`\lambda \mathrm{\Lambda }^m(v)`$. Hence $`\lambda =\lambda ^{}\lambda ^{\prime \prime }`$ with $`\lambda ^{}\mathrm{\Lambda }^{me_j}(v)`$ and $`\lambda ^{\prime \prime }\mathrm{\Lambda }^{e_j}(s(\lambda ^{}))`$. ∎

###### Remark 3.13.

The $`k`$-graphs $`(\mathrm{\Lambda },d)`$ studied in  have no sources; that is, $`\lambda ^m(v)\mathrm{}`$ for all $`v\mathrm{\Lambda }^0`$ and $`m^k`$. Then $`\mathrm{\Lambda }^m(v)=\mathrm{\Lambda }^m(v)`$, and Lemma 3.12 just says that a path $`\lambda \mathrm{\Lambda }^m(v)`$ can be factorised into $`\lambda =\lambda ^{}\lambda ^{\prime \prime }`$ with $`d(\lambda ^{})=me_j`$ and $`d(\lambda ^{\prime \prime })=e_j`$. Thus local convexity ensures that $`\mathrm{\Lambda }^m(v)`$ has factorisation properties like those of $`\mathrm{\Lambda }^m(v)`$.

###### Proof of Proposition 3.11.

Property (3.2) merely consists of specific cases of Cuntz-Krieger relation (4), so suppose (3.2) holds. Define a map $`l:^k`$ by $`l(m)=_{i=1}^km_i`$. We prove (4) by induction on $`l(n).`$

The $`n=0`$ case is trivial since it amounts to the tautology $`s_v=s_v`$, and the $`n=1`$ case follows directly from (3.2) since $`l^1(1)=\{e_1,\mathrm{},e_k\}`$. Suppose (4) holds for all $`m`$ such that $`l(m)n`$. Let $`m^k`$ satisfy $`l(m)=n+1`$ and choose $`j`$ such that $`m_j1`$. Using Lemma 3.12 we have

$`{\displaystyle \underset{\lambda \mathrm{\Lambda }^m(v)}{}}s_\lambda s_\lambda ^{}`$ $`={\displaystyle \underset{\lambda ^{}\mathrm{\Lambda }^{me_j}(v)}{}}{\displaystyle \underset{\lambda ^{\prime \prime }\mathrm{\Lambda }^{e_j}(s(\lambda ^{}))}{}}s_{\lambda ^{}\lambda ^{\prime \prime }}s_{\lambda ^{}\lambda ^{\prime \prime }}^{}`$
$`={\displaystyle \underset{\lambda ^{}\mathrm{\Lambda }^{me_j}(v)}{}}s_\lambda ^{}\left({\displaystyle \underset{\lambda ^{\prime \prime }\mathrm{\Lambda }^{e_j}(s(\lambda ^{}))}{}}s_{\lambda ^{\prime \prime }}s_{\lambda ^{\prime \prime }}^{}\right)s_\lambda ^{}^{}`$
$`={\displaystyle \underset{\lambda ^{}\mathrm{\Lambda }^{me_j}(v)}{}}s_\lambda ^{}s_{s(\lambda ^{})}s_\lambda ^{}^{}\text{by (}\text{3.2}\text{)}`$
$`={\displaystyle \underset{\lambda ^{}\mathrm{\Lambda }^{me_j}(v)}{}}s_\lambda ^{}s_\lambda ^{}^{}`$
$`=s_v\text{by inductive hypothesis}.`$
Hence (4) holds whenever $`l(m)=n+1`$. ∎

Kumjian and Pask use the infinite path space $`\mathrm{\Lambda }^{\mathrm{}}`$ of a $`k`$-graph $`\mathrm{\Lambda }`$ with no sources to produce a Cuntz-Krieger $`\mathrm{\Lambda }`$-family of nonzero partial isometries (see \[7, Proposition 2.11\]). In a $`k`$-graph which admits sources, however, not every finite path is contained in an infinite path of the form defined in , and hence the proof of \[7, Proposition 2.11\] does not carry over. To allow for sources, we replace $`\mathrm{\Lambda }^{\mathrm{}}`$ with a boundary-path space $`\mathrm{\Lambda }^{\mathrm{}}`$; for locally convex $`k`$-graphs, we can achieve this construction using the $`k`$-graphs $`\mathrm{\Omega }_{k,m}`$ of Example 2.2(ii).

###### Definition 3.14.

Let $`\mathrm{\Lambda }`$ be a locally convex $`k`$-graph. A boundary path in $`\mathrm{\Lambda }`$ is a graph morphism $`x:\mathrm{\Omega }_{k,m}\mathrm{\Lambda }`$ for some $`m(\{\mathrm{}\})^k`$ such that, whenever $`v\mathrm{Obj}(\mathrm{\Omega }_{k,m})`$ satisfies $`(\mathrm{\Omega }_{k,m})^{e_i}(v)=\{v\},`$ we also have $`\mathrm{\Lambda }^{e_i}(x(v))=\{x(v)\}.`$ We denote the collection of all boundary paths in $`\mathrm{\Lambda }`$ by $`\mathrm{\Lambda }^{\mathrm{}}.`$ The range map of $`\mathrm{\Lambda }`$ extends naturally to $`\mathrm{\Lambda }^{\mathrm{}}`$ via $`r(x):=x(0).`$ For $`v\mathrm{\Lambda }^0,`$ we write $`\mathrm{\Lambda }^{\mathrm{}}(v)`$ for $`\{x\mathrm{\Lambda }^{\mathrm{}}:r(x)=v\}.`$ We define a degree map $`d_{\mathrm{}}:\mathrm{\Lambda }^{\mathrm{}}(\{\mathrm{}\})^k`$ by setting $`d_{\mathrm{}}(x):=m`$ when $`x:\mathrm{\Omega }_{k,m}\mathrm{\Lambda }.`$

As with the infinite paths of , a boundary path $`x`$ is completely determined by the set of paths $`\{x(0,p):pd_{\mathrm{}}(x)\}.`$ In fact, when the $`k`$-graph has no sources, $`\mathrm{\Lambda }^{\mathrm{}}`$ is exactly the infinite path space from . If a $`k`$-graph $`\mathrm{\Lambda }`$ is locally convex then for any vertex $`v`$ of $`\mathrm{\Lambda },`$ the set $`\mathrm{\Lambda }^{\mathrm{}}(v)`$ is nonempty: even if $`v`$ emits no paths of nonzero degree, we have $`\mathrm{\Lambda }^{\mathrm{}}(v)=\{v\}\mathrm{}.`$

###### Theorem 3.15.

Let $`(\mathrm{\Lambda },d)`$ be a row-finite $`k`$-graph. Then there is a Cuntz-Krieger $`\mathrm{\Lambda }`$-family $`\{S_\lambda :\lambda \mathrm{\Lambda }\}`$ with each $`S_\lambda `$ nonzero if and only if $`\mathrm{\Lambda }`$ is locally convex.

###### Proof.

First suppose that $`\mathrm{\Lambda }`$ is not locally convex. Then there exists a vertex $`v\mathrm{\Lambda }^0`$ and $`\mu \mathrm{\Lambda }^{e_i}(v)`$ for some $`i\{1,\mathrm{},k\}`$ such that $`\mathrm{\Lambda }^{e_j}(v)\mathrm{}`$ and $`\mathrm{\Lambda }^{e_j}(s(\mu ))=\mathrm{}`$ for some $`ji`$. Considering the partial isometry $`s_\mu C^{}(\mathrm{\Lambda })`$, we have

$$s_\mu =s_vs_\mu =\underset{\nu \mathrm{\Lambda }^{e_j}(v)}{}s_\nu s_\nu ^{}s_\mu =\underset{\nu \mathrm{\Lambda }^{e_j}(v)}{}s_\nu \underset{\begin{array}{c}\nu \alpha =\mu \beta \\ d(\mu \beta )=e_i+e_j\end{array}}{}s_\alpha s_\beta ^{},$$

but since $`\mathrm{\Lambda }^{e_j}(s(\mu ))=\mathrm{}`$, no such $`\beta `$ exists. Thus $`s_\mu =0`$, and so by the universal property of $`C^{}(\mathrm{\Lambda })`$ any Cuntz-Krieger $`\mathrm{\Lambda }`$-family $`\{S_\lambda :\lambda \mathrm{\Lambda }\}`$ must have $`S_\mu =0`$.

Now suppose that $`\mathrm{\Lambda }`$ is locally convex. Let $`:=\mathrm{}^2(\mathrm{\Lambda }^{\mathrm{}})`$, and for each $`\lambda \mathrm{\Lambda }`$ define $`S_\lambda B()`$ by

(3.5)
$$S_\lambda u_x:=\{\begin{array}{cc}u_{\lambda x}\text{if }s(\lambda )=r(x)\hfill & \\ 0\text{otherwise},\hfill & \end{array}$$

where $`\{u_x:x\mathrm{\Lambda }^{\mathrm{}}\}`$ is the usual basis for $``$. Each $`S_\lambda 0`$ because $`\mathrm{\Lambda }^{\mathrm{}}(s(\lambda ))\mathrm{}`$. Cuntz-Krieger relations (1)-(3) follow directly from the definition of the operators $`S_\lambda `$; it remains to show that relation (4) is fulfilled. Since $`\mathrm{\Lambda }`$ is locally convex, by Proposition 3.11 it suffices to show that for each $`v\mathrm{\Lambda }^0`$ and $`i\{1,\mathrm{},k\}`$, $`S_v={\displaystyle \underset{\lambda \mathrm{\Lambda }^{e_i}(v)}{}}S_\lambda S_\lambda ^{}`$. If $`\mathrm{\Lambda }^{e_i}(v)=\{v\}`$, then the relation is trivially true, so suppose $`\mathrm{\Lambda }^{e_i}(v)\{v\}`$. For $`x\mathrm{\Lambda }^{\mathrm{}}`$ we have

$`{\displaystyle \underset{\lambda \mathrm{\Lambda }^{e_i}(v)}{}}S_\lambda S_\lambda ^{}u_x`$ $`={\displaystyle \underset{\lambda \mathrm{\Lambda }^{e_i}(v)}{}}S_\lambda (\delta _{\lambda ,x(0,e_i)}u_{x(e_i,\mathrm{})})`$
$`={\displaystyle \underset{\lambda \mathrm{\Lambda }^{e_i}(v)}{}}\delta _{\lambda ,x(0,e_i)}u_x`$
$`=\{\begin{array}{cc}u_x\text{if there exists }\lambda \mathrm{\Lambda }^{e_i}(v)\text{ such that }\lambda =x(0,e_i)\hfill & \\ 0\text{otherwise}.\hfill & \end{array}`$
Taking $`\lambda =v`$ in (3.5), we can see that it suffices to show that $`r(x)=v`$ if and only if there exists $`\lambda \mathrm{\Lambda }^{e_i}(v)`$ such that $`\lambda =x(0,e_i)`$. If $`\lambda =x(0,e_i)`$ for some $`\lambda \mathrm{\Lambda }^{e_i}(v)`$, then $`r(x)=r(\lambda )=v`$. If $`r(x)=v`$, then $`x(0,e_i)\mathrm{\Lambda }^{e_i}(v)`$ because $`\mathrm{\Lambda }^{e_i}(v)\{v\}`$ and $`x`$ is a boundary path. ∎

## 4. The uniqueness theorems

### 4.1. The gauge-invariant uniqueness theorem

Our gauge-invariant uniqueness theorem extends \[7, Theorem 3.4\] to row-finite $`k`$-graphs with sources.

Let $`(\mathrm{\Lambda },d)`$ be a row-finite $`k`$-graph. For $`z𝕋^k`$ and $`n^k`$, let $`z^n:=z_1^{n_1}\mathrm{}z_k^{n_k}.`$ Then $`\{z^{d(\lambda )}s_\lambda :\lambda \mathrm{\Lambda }\}`$ is a Cuntz-Krieger $`\mathrm{\Lambda }`$-family which generates $`C^{}(\mathrm{\Lambda })`$, and the universal property of $`C^{}(\mathrm{\Lambda })`$ gives a homomorphism $`\gamma _z:C^{}(\mathrm{\Lambda })C^{}(\mathrm{\Lambda })`$ such that $`\gamma _z(s_\lambda )=z^{d(\lambda )}s_\lambda `$ for $`\lambda \mathrm{\Lambda }`$; $`\gamma _{\overline{z}}`$ is an inverse for $`\gamma _z,`$ so $`\gamma _z`$ is an automorphism. An $`ϵ/3`$-argument shows that $`\gamma `$ is a strongly continuous action of $`𝕋^k`$ on $`C^{}(\mathrm{\Lambda })`$, which is called the gauge action.

###### Theorem 4.1 (The Gauge-Invariant Uniqueness Theorem).

Let $`(\mathrm{\Lambda },d)`$ be a locally convex row-finite $`k`$-graph, let $`\{t_\lambda :\lambda \mathrm{\Lambda }\}`$ be a Cuntz-Krieger $`\mathrm{\Lambda }`$-family, and let $`\pi `$ be the representation of $`C^{}(\mathrm{\Lambda })`$ such that $`\pi (s_\lambda )=t_\lambda `$. If each $`t_v`$ is nonzero and there is a strongly continuous action $`\beta :𝕋^k\mathrm{Aut}(C^{}(\{t_\lambda :\lambda \mathrm{\Lambda }\}))`$ such that $`\beta _z\pi =\pi \gamma _z`$ for $`z𝕋^k`$, then $`\pi `$ is faithful.

###### Remark 4.2.

Strictly speaking, it is not necessary to assume that $`\mathrm{\Lambda }`$ is locally convex; if there is a Cuntz-Krieger $`\mathrm{\Lambda }`$-family $`\{t_\lambda :\lambda \mathrm{\Lambda }\}`$ with each $`t_v`$ nonzero, then Theorem 3.15 implies that $`\mathrm{\Lambda }`$ is locally convex.

The first part of the proof, the analysis of the core $`C^{}(\mathrm{\Lambda })^\gamma `$, is the same for both uniqueness theorems. Using our$`\mathrm{\Lambda }^p`$, and Lemmas 3.6 and 3.7, we can follow the argument of \[7, §3\]. We consider the map $`\mathrm{\Phi }:C^{}(\mathrm{\Lambda })C^{}(\mathrm{\Lambda })`$ defined by

$$\mathrm{\Phi }(a):=_{𝕋^k}\gamma _z(a)𝑑z,$$

which is faithful on positive elements, and has range the fixed point algebra $`C^{}(\mathrm{\Lambda })^\gamma .`$ To identify the structure of $`C^{}(\mathrm{\Lambda })^\gamma `$, we let $`v\mathrm{\Lambda }^0`$, $`q^k`$, and define

$$_q(v):=\overline{\mathrm{span}}\{s_\lambda s_\mu ^{}:\lambda ,\mu \mathrm{\Lambda }^q,d(\lambda )=d(\mu ),s(\lambda )=s(\mu )=v\}.$$

It follows from Lemma 3.7 that $`_q(v)`$ is the direct sum of the subalgebras

$$_{q,p}(v):=\overline{\mathrm{span}}\{s_\lambda s_\mu ^{}:\lambda ,\mu \mathrm{\Lambda }^q,d(\lambda )=d(\mu )=p,s(\lambda )=s(\mu )=v\},$$

that

(4.1)
$$_{q,p}(v)=𝒦(\mathrm{}^2(\{\lambda \mathrm{\Lambda }^q:d(\lambda )=p\text{ and }s(\lambda )=v\})),$$

and that for fixed $`q`$, the $`_q(v)`$’s are mutually orthogonal. Since the elements $`s_\lambda s_\mu ^{}`$ span $`C^{}(\mathrm{\Lambda })`$, and since $`\gamma _z(s_\lambda s_\mu ^{})=z^{d(\lambda )d(\mu )}s_\lambda s_\mu ^{}`$, the algebras $`_q:=_{v\mathrm{\Lambda }^0}_q(v)`$ span $`C^{}(\mathrm{\Lambda })^\gamma `$. When $`pq`$, we have $`_p_q`$ by Lemma 3.6, so $`C^{}(\mathrm{\Lambda })^\gamma `$ is the direct limit $`\overline{_{q^k}_q}`$ of the algebras $`_q`$. In particular, $`C^{}(\mathrm{\Lambda })^\gamma `$ is AF.

###### Proof of Theorem 4.1.

Because each $`t_v`$ is nonzero, and $`t_\lambda `$ has initial projection $`t_{s(\lambda )}`$, each $`t_\lambda `$ is nonzero, and hence the representation $`\pi `$ is nonzero on each $`_{q,p}(v)`$. It follows from (4.1) that $`\pi `$ is faithful on $`_{p,q}(v)`$, hence on $`_q(v)`$ and on $`_q`$. Since $`C^{}(\mathrm{\Lambda })^\gamma =\underset{}{\mathrm{lim}}_q`$, it follows that $`\pi `$ is faithful on $`C^{}(\mathrm{\Lambda })^\gamma `$ (see \[1, Lemma 1.3\], for example). We can now use the argument of \[7, page 11\]. ∎

### 4.2. The Cuntz-Krieger uniqueness theorem

Our Cuntz-Krieger uniqueness theorem extends \[7, Theorem 4.6\] to row-finite $`k`$-graphs with sources (see Remark 4.4 below).

###### Theorem 4.3.

Let $`(\mathrm{\Lambda },d)`$ be a locally convex row-finite $`k`$-graph, and suppose that:

(B) for each $`v\mathrm{\Lambda }^0`$, there exists $`x\mathrm{\Lambda }^{\mathrm{}}(v)`$ such that $`\alpha \beta `$ implies $`\alpha x\beta x`$.
Let $`\{t_\lambda :\lambda \mathrm{\Lambda }\}`$ be a Cuntz-Krieger $`\mathrm{\Lambda }`$-family, and let $`\pi `$ be the representation of $`C^{}(\mathrm{\Lambda })`$ such that $`\pi (s_\lambda )=t_\lambda `$. If each $`t_v`$ is non-zero, then $`\pi `$ is faithful.

###### Proof.

For $`\lambda \mathrm{\Lambda }\mathrm{\Lambda }^{\mathrm{}}`$ and $`p^k`$, we write $`\lambda (0,p)`$ for the unique path such that $`\lambda =\lambda (0,p)\lambda ^{}`$ with $`d(\lambda (0,p))=pd(\lambda )`$.

We know from the analysis in §4.1 that $`\pi `$ is faithful on the fixed-point algebra $`C^{}(\mathrm{\Lambda })^\gamma `$, and hence the standard argument will work once we know that

(4.2)
$$\pi (\mathrm{\Phi }(a))\pi (a)\text{ for }aC^{}(\mathrm{\Lambda }).$$

Recalling that $`\mathrm{span}\{s_\lambda s_\mu ^{}:s(\lambda )=s(\mu )\}`$ is dense in $`C^{}(\mathrm{\Lambda })`$, we consider arbitrary $`a=_{(\lambda ,\mu )F}\zeta _{(\lambda ,\mu )}s_\lambda s_\mu ^{}`$ where $`F`$ is finite and $`\zeta _{(\lambda ,\mu )}`$. Let $`l`$ be the least upper bound of $`\{d(\lambda )d(\mu ):(\lambda ,\mu )F\}.`$ Then

$$\mathrm{\Phi }(a)=\underset{\{(\lambda ,\mu )F:d(\lambda )=d(\mu )\}}{}\zeta _{(\lambda ,\mu )}s_\lambda s_\mu ^{}_l.$$

For $`(\lambda ,\mu )F`$, we define

$$F_{(\lambda ,\mu )}=\{(\lambda \nu ,\mu \nu ):\nu \mathrm{\Lambda }^{ld(\lambda )}(s(\lambda ))\},$$

and $`E=_{(\lambda ,\mu )F}F_{(\lambda ,\mu )}`$. For $`\nu \mathrm{\Lambda }^{ld(\lambda )}(s(\lambda ))`$, we define

$$\xi _{(\lambda \nu ,\mu \nu )}=\underset{\{(\lambda ^{},\mu ^{})F:(\lambda \nu ,\mu \nu )=(\lambda ^{}\nu ^{},\mu ^{}\nu ^{})\text{ for some }\nu ^{}\mathrm{\Lambda }\}}{}\zeta _{(\lambda ^{},\mu ^{})},$$

and using Cuntz-Krieger relation (4) we then have

$$a=\underset{(\alpha ,\beta )E}{}\xi _{(\alpha ,\beta )}s_\alpha s_\beta ^{};$$

the point is that now $`\alpha \mathrm{\Lambda }^l`$ for all $`(\alpha ,\beta )E`$.

Since $`_l`$ decomposes as a direct sum $`_{v\mathrm{\Lambda }^0}_l(v)`$, so does its image under $`\pi `$, and there is a vertex $`v\mathrm{\Lambda }^0`$ such that

(4.3)
$$\pi (\mathrm{\Phi }(a))=\underset{\{(\alpha ,\beta )E:d(\alpha )=d(\beta )\text{ and }s(\alpha )=v\}}{}\xi _{(\alpha ,\beta )}t_\alpha t_\beta ^{}.$$

Choose a boundary path $`x\mathrm{\Lambda }^{\mathrm{}}(v)`$ such that $`\alpha x\beta x`$ for all $`\alpha \beta \mathrm{\Lambda }`$; then for each $`\alpha \beta \mathrm{\Lambda }`$, there exists $`M_{\alpha ,\beta }d(\alpha )d(\beta )`$ such that $`(\alpha x)(0,m)(\beta x)(0,m)`$ whenever $`mM_{\alpha ,\beta }`$. Let

$$T=\{\tau \mathrm{\Lambda }^l:\tau =\alpha \text{ or }\tau =\beta \text{ for some }(\alpha ,\beta )E,s(\tau )=v\}.$$

Let $`M`$ be the least upper bound of $`\{M_{\tau ,\beta }:\tau T,(\alpha ,\beta )E\text{ for some }\alpha \}`$. In particular,

(4.4)
$$(\beta x)(0,M)(\tau x)(0,M)$$

when $`\beta `$ is the second coordinate of an element of $`E`$, $`\tau T`$, and $`\beta \tau `$. Write $`x_M`$ for $`x(0,M)`$.

For each $`nl,`$ we define

$$Q_n:=\underset{\{\tau T:d(\tau )=n\}}{}t_{\tau x_M}t_{\tau x_M}^{}.$$

Now we define $`Q:C^{}(\{t_\lambda :\lambda \mathrm{\Lambda }\})C^{}(\{t_\lambda :\lambda \mathrm{\Lambda }\})`$ by

$$Q(b):=\underset{nl}{}Q_nbQ_n.$$

Since the $`Q_n`$ are mutually orthogonal projections, we have

$$Q(b)=\underset{nl}{}Q_nbQ_nb\text{ for }bC^{}(\{t_\lambda \}).$$

We aim to show that $`Q(\pi (\mathrm{\Phi }(a)))=\pi (\mathrm{\Phi }(a)),`$ and that $`Q(\pi (a))=Q(\pi (\mathrm{\Phi }(a)))`$; this will give us

(4.5)
$$\pi (\mathrm{\Phi }(a))=Q(\pi (\mathrm{\Phi }(a)))=Q(\pi (a))\pi (a),$$

and the proof will be complete.

Write $`M_T`$ for the matrix algebra spanned by $`\{s_\lambda s_\mu ^{}:\lambda ,\mu T,d(\lambda )=d(\mu )\}`$. Notice that $`M_T_l(v)`$. For $`s_\lambda s_\mu ^{}M_T`$ we have $`\lambda ,\mu \mathrm{\Lambda }^l,`$ so for $`\tau T,`$ $`t_\tau ^{}t_\lambda =0`$ unless $`\tau =\lambda ,`$ and $`t_\mu ^{}t_\tau =0`$ unless $`\tau =\mu ,`$ and hence

$`Q(\pi (s_\lambda s_\mu ^{}))`$ $`={\displaystyle \underset{nl}{}}\left({\displaystyle \underset{\{\tau T:d(\tau )=n\}}{}}t_{\tau x_M}t_{\tau x_M}^{}\right)t_\lambda t_\mu ^{}\left({\displaystyle \underset{\{\tau ^{}T:d(\tau ^{})=n\}}{}}t_{\tau ^{}x_M}t_{\tau ^{}x_M}^{}\right)`$
$`=t_{\lambda x_M}t_{x_M}^{}t_\lambda ^{}t_\lambda t_\mu ^{}t_\mu t_{x_M}t_{\mu x_M}^{}`$
$`=t_{\lambda x_M}t_{\mu x_M}^{}`$
$`0.`$
Using Lemma 3.7, it follows that $`\{Q(\pi (s_\lambda s_\mu ^{})):s_\lambda s_\mu ^{}M_T\}`$ is a family of nonzero matrix units, and from this we deduce that the map $`bQ(\pi (b))`$ is a faithful representation of $`M_T.`$ Since both $`\pi `$ and $`Q\pi `$ are faithful on $`M_T`$ and since

$$\underset{\{(\alpha ,\beta )E:d(\alpha )=d(\beta )\text{ and }s(\alpha )=v\}}{}\xi _{(\alpha ,\beta )}t_\alpha t_\beta ^{}M_T,$$

it follows from (4.3) that $`\pi (\mathrm{\Phi }(a))=Q(\pi (\mathrm{\Phi }(a)))`$.

To establish that $`Q(\pi (a))=Q(\pi (\mathrm{\Phi }(a)))`$, we show that $`Q(t_\alpha t_\beta ^{})=0`$ whenever $`(\alpha ,\beta )E`$ and $`d(\alpha )d(\beta );`$ this shows that $`Q`$ kills those terms of $`\pi (a)`$ which are the images under $`\pi `$ of terms of $`a`$ killed by $`\mathrm{\Phi }`$. Notice that if $`(\alpha ,\beta )E`$ then $`\alpha \mathrm{\Lambda }^l,`$ so for $`\tau T,`$ $`t_\tau ^{}t_\alpha =0`$ unless $`\tau =\alpha .`$ Hence, for $`(\alpha ,\beta )E`$ with $`d(\alpha )d(\beta )`$, we have

$`Q(t_\alpha t_\beta ^{})`$ $`={\displaystyle \underset{nl}{}}\left({\displaystyle \underset{\{\tau T:d(\tau )=n\}}{}}t_{\tau x_M}t_{\tau x_M}^{}\right)t_\alpha t_\beta ^{}\left({\displaystyle \underset{\{\tau ^{}T:d(\tau ^{})=n\}}{}}t_{\tau ^{}x_M}t_{\tau ^{}x_M}^{}\right)`$
$`={\displaystyle \underset{\{\tau ^{}T:d(\tau ^{})=d(\alpha )\}}{}}t_{\alpha x_M}t_{\beta x_M}^{}t_{\tau ^{}x_M}t_{\tau ^{}x_M}^{}`$
$`={\displaystyle \underset{\{\tau ^{}T:d(\tau ^{})=d(\alpha )\}}{}}t_{\alpha x_M}\left({\displaystyle \underset{\begin{array}{c}\beta x_M\eta =\tau ^{}x_M\zeta \\ d(\beta x_M\eta )=d(\beta x_M)d(\tau ^{}x_M)\end{array}}{}}t_\eta t_\zeta ^{}\right)t_{\tau ^{}x_M}^{},`$
which is nonzero if and only if there exist $`\eta ,\zeta \mathrm{\Lambda }`$ such that

(4.6)
$$(\beta x_M\eta )(0,M)=(\tau ^{}x_M\zeta )(0,M).$$

But $`(\beta x_M\eta )(0,M)=(\beta x_M)(0,M)`$ : if not, then there exists an $`i`$ such that $`d(\beta x_M)_i<M_i`$ and $`d(\eta )_i>0.`$ But

$$d(\beta x_M)_i<M_id(x_M)_i<M_i\mathrm{\Lambda }^{e_i}(s(x_M))=\mathrm{}$$

since $`x`$ is a boundary path. Likewise, $`(\tau ^{}x_M\zeta )(0,M)=(\tau ^{}x_M)(0,M)`$, and so (4.6) is equivalent to $`(\beta x_M)(0,M)=(\tau ^{}x_M)(0,M)`$, which is impossible by (4.4). This proves (4.5), and the result follows. ∎

###### Remark 4.4.

The condition (B) in Theorem 4.3 is automatic if $`\mathrm{\Lambda }`$ has no sources and satisfies the aperiodicity condition (A) of \[7, Definition 4.3\]. To see this, let $`\sigma `$ be the shift map on $`\mathrm{\Lambda }^{\mathrm{}}`$ defined as in  by $`\sigma ^p(x)=x(p,\mathrm{})`$. Suppose that $`\mathrm{\Lambda }`$ has no sources and (B) does not hold. Then there is a vertex $`v\mathrm{\Lambda }^0`$ such that for each $`x\mathrm{\Lambda }^{\mathrm{}}(v)`$, there exist $`\alpha _x\beta _x`$ such that $`\alpha _xx=\beta _xx`$. Then for $`x\mathrm{\Lambda }^{\mathrm{}}(v)`$,

$$\begin{array}{cc}\hfill \sigma ^{d(\alpha _x)d(\beta _x)d(\alpha _x)}(x)& =\sigma ^{d(\alpha _x)d(\beta _x)}(\alpha _xx)\hfill \\ & =\sigma ^{d(\alpha _x)d(\beta _x)}(\beta _xx)=\sigma ^{d(\alpha _x)d(\beta _x)d(\beta _x)}(x).\hfill \end{array}$$

Hence condition (A) of \[7, Definition 4.3\] does not hold at $`v`$.

Thus Theorem 4.3 is formally stronger than \[7, Theorem 4.6\] even when $`\mathrm{\Lambda }`$ has no sources. We have been unable to decide whether it is equivalent: we do not know whether in graphs without sources, (B) implies (A). For 1-graphs with no sources, we can prove that (B) implies (A) because it is easy to construct aperiodic paths (see the proof of \[8, Lemma 3.4\]). In higher-rank graphs, it is hard to produce aperiodic paths, and we suspect that in practice (B) might be easier to check than (A).

## 5. The ideal structure

Let $`(\mathrm{\Lambda },d)`$ be a locally convex row-finite $`k`$-graph. Define a relation on $`\mathrm{\Lambda }^0`$ by setting $`vw`$ if there is a path $`\lambda \mathrm{\Lambda }`$ with $`r(\lambda )=v`$ and $`s(\lambda )=w`$. A subset $`H`$ of $`\mathrm{\Lambda }^0`$ is hereditary if $`vw`$ and $`vH`$ imply $`wH`$; $`H`$ is saturated if for $`v\mathrm{\Lambda }^0`$,

$$\{s(\lambda ):\lambda \mathrm{\Lambda }^{e_i}(v)\}H\text{ for some }i\{1,\mathrm{},k\}vH.$$

The saturation of a set $`H`$ is the smallest saturated subset $`\overline{H}`$ of $`\mathrm{\Lambda }^0`$ containing $`H`$.

###### Lemma 5.1.

Suppose $`\mathrm{\Lambda }`$ is a locally convex row-finite $`k`$-graph, and $`H`$ is a hereditary subset of $`\mathrm{\Lambda }^0`$. Then the saturation $`\overline{H}`$ is hereditary.

###### Proof.

We use an inductive construction of $`\overline{H}`$ like that used by Szymaǹski for 1-graphs in . For $`F\mathrm{\Lambda }^0`$, we define

$$\mathrm{\Sigma }(F):=\underset{i=1}{\overset{k}{}}\{v\mathrm{\Lambda }^0:s(\lambda )F\text{ for all }\lambda \mathrm{\Lambda }^{e_i}(v)\},$$

and write $`\mathrm{\Sigma }^n(F)`$ for the set obtained by repeating the process $`n`$ times. Notice that if $`F`$ is hereditary, then $`F\mathrm{\Sigma }(F)`$. We will show that $`_{n=1}^{\mathrm{}}\mathrm{\Sigma }^n(H)`$ is hereditary and equal to $`\overline{H}`$.

We begin by showing that if $`F`$ is hereditary, then $`\mathrm{\Sigma }(F)`$ is hereditary. To see this, suppose that $`v\mathrm{\Sigma }(F)`$ and that $`vw.`$ Then there exists $`\lambda \mathrm{\Lambda }^0`$ such that $`r(\lambda )=v`$ and $`s(\lambda )=w.`$ If $`d(\lambda )=0`$, then $`w=vF`$, so suppose $`d(\lambda )_j>0`$, and factor $`\lambda =\lambda ^{}\lambda ^{\prime \prime }`$ where $`d(\lambda ^{})=e_j`$. We claim that $`s(\lambda ^{})\mathrm{\Sigma }(F)`$. To see this, choose $`i`$ such that $`\{s(\mu ):\mu \mathrm{\Lambda }^{e_i}(v)\}F.`$ If $`\mathrm{\Lambda }^{e_i}(v)=\{v\}`$ or if $`i=j`$, then $`s(\lambda ^{})F\mathrm{\Sigma }(F)`$. So suppose that $`\mathrm{\Lambda }^{e_i}(v)\{v\}`$ and $`ij`$. Since $`\mathrm{\Lambda }`$ is locally convex, $`\mathrm{\Lambda }^{e_i}(s(\lambda ^{}))\mathrm{}`$, so it suffices to show that $`\nu \mathrm{\Lambda }^{e_i}(s(\lambda ^{}))`$ implies $`s(\nu )F`$. Let $`\nu \mathrm{\Lambda }^{e_i}(s(\lambda ^{}))`$. Then $`\lambda ^{}\nu =\mu \nu ^{}`$ for some $`\mu \mathrm{\Lambda }^{e_i}(v)`$. But now $`s(\mu )F`$ and hence $`s(\nu ^{})=s(\nu )F`$ because $`F`$ is hereditary. Thus $`s(\lambda ^{})\mathrm{\Sigma }(F)`$ as claimed. By induction on the length of $`\lambda `$, it follows that $`w\mathrm{\Sigma }(F)`$, and hence $`\mathrm{\Sigma }(F)`$ is hereditary.

We now know that $`\mathrm{\Sigma }^n(H)\mathrm{\Sigma }^{n+1}(H)`$ for all $`n`$, and that $`\mathrm{\Sigma }^n(H)`$ is hereditary for all $`n`$; thus $`_{n=1}^{\mathrm{}}\mathrm{\Sigma }^n(H)`$ is also hereditary. It remains to show that $`\overline{H}=_{n=1}^{\mathrm{}}\mathrm{\Sigma }^n(H)`$. Because applying $`\mathrm{\Sigma }`$ can never take us outside of a saturated set, we have $`\mathrm{\Sigma }^n(H)\overline{H}`$, so it is enough to show that $`_{n=1}^{\mathrm{}}\mathrm{\Sigma }^n(H)`$ is saturated. To see this, suppose that $`v\mathrm{\Lambda }^0`$ and $`\{s(\lambda ):\lambda \mathrm{\Lambda }^{e_i}(v)\}_{n=1}^{\mathrm{}}\mathrm{\Sigma }^n(H)`$. Then, since $`\mathrm{\Lambda }`$ is row finite, we have $`\{s(\lambda ):\lambda \mathrm{\Lambda }^{e_i}(v)\}\mathrm{\Sigma }^N(H)`$ for some $`N`$ and it follows that $`v\mathrm{\Sigma }^{N+1}(H)`$. Thus $`_{n=1}^{\mathrm{}}\mathrm{\Sigma }^n(H)`$ is saturated. ∎

###### Theorem 5.2.

Let $`(\mathrm{\Lambda },d)`$ be a locally convex row-finite $`k`$-graph. For each subset $`H`$ of $`\mathrm{\Lambda }^0`$, let $`I_H`$ be the closed ideal in $`C^{}(\mathrm{\Lambda })`$ generated by $`\{s_v:vH\}`$.

* The map $`HI_H`$ is an isomorphism of the lattice of saturated hereditary subsets of $`\mathrm{\Lambda }^0`$ onto the lattice of closed gauge-invariant ideals of $`C^{}(\mathrm{\Lambda })`$.
* Suppose $`H`$ is saturated and hereditary. Then

$$\mathrm{\Gamma }(\mathrm{\Lambda }H):=(\mathrm{\Lambda }^0H,\{\lambda \mathrm{\Lambda }:s(\lambda )H\},r,s)$$

is a locally convex row-finite $`k`$-graph, and $`C^{}(\mathrm{\Lambda })/I_H`$ is canonically isomorphic to $`C^{}(\mathrm{\Gamma }(\mathrm{\Lambda }H))`$.
* If $`H`$ is any hereditary subset of $`\mathrm{\Lambda }^0`$, then

$$\mathrm{\Lambda }(H):=(H,\{\lambda \mathrm{\Lambda }:r(\lambda )H\},r,s)$$

is a locally convex row-finite $`k`$-graph, $`C^{}(\mathrm{\Lambda }(H))`$ is canonically isomorphic to the subalgebra $`C^{}(\{s_\lambda :r(\lambda )H\})`$ of $`C^{}(\mathrm{\Lambda })`$, and this subalgebra is a full corner in $`I_H`$.

###### Proof.

The proof of Theorem 5.2 is the same as the proof of \[3, Theorem 4.1\] once we establish that $`\mathrm{\Gamma }(\mathrm{\Lambda }H)`$ and $`\mathrm{\Lambda }(H)`$ from parts (b) and (c) are locally convex row-finite $`k`$-graphs. This is easy to check for $`\mathrm{\Lambda }(H)`$, and the row-finiteness of $`\mathrm{\Gamma }(\mathrm{\Lambda }H)`$ follows from that of $`\mathrm{\Lambda }`$. We need to check that $`\mathrm{\Gamma }(\mathrm{\Lambda }H)`$ is a $`k`$-graph and is locally convex. For convenience, write $`\mathrm{\Gamma }=\mathrm{\Gamma }(\mathrm{\Lambda }H)`$.

To show that the factorisation property holds for $`(\mathrm{\Gamma },d)`$, take $`\lambda \mathrm{\Gamma }`$ and suppose $`d(\lambda )=p+q`$. We know there exist unique $`\mu ,\nu \mathrm{\Lambda }`$ such that $`\lambda =\mu \nu `$, $`d(\mu )=p`$ and $`d(\nu )=q`$. Certainly $`s(\nu )=s(\lambda )H`$, and if $`s(\mu )H`$, then $`s(\nu )H`$, a contradiction. Hence $`\mu ,\nu \mathrm{\Gamma }`$, and $`\mathrm{\Gamma }`$ is a sub-$`k`$-graph.

Now we show that $`\mathrm{\Gamma }`$ is locally convex. Consider an arbitrary vertex $`v\mathrm{\Gamma }^0`$ which has $`\lambda \mathrm{\Gamma }^{e_i}(v)`$ and $`\mu \mathrm{\Gamma }^{e_j}(v)`$ for some $`ij`$. We know that $`s(\lambda ),s(\mu )H`$, and since $`\mathrm{\Lambda }`$ is locally convex, we also know there exist $`\alpha \mathrm{\Lambda }^{e_i}(s(\mu ))`$ and $`\beta \mathrm{\Lambda }^{e_j}(s(\lambda ))`$. If $`\mathrm{\Gamma }^{e_i}(s(\mu ))=\mathrm{}`$, then $`\{s(\alpha ):\alpha \mathrm{\Lambda }^{e_i}(s(\mu ))\}H`$, and similarly, if $`\mathrm{\Gamma }^{e_j}(s(\mu ))=\mathrm{}`$, then $`\{s(\beta ):\beta \mathrm{\Lambda }^{e_j}(s(\lambda ))\}H`$; in either case saturatedness implies that $`s(\mu )H`$ or $`s(\lambda )H`$, a contradiction. Hence $`\mathrm{\Gamma }^{e_i}(s(\mu ))\mathrm{}`$ and $`\mathrm{\Gamma }^{e_j}(s(\lambda ))\mathrm{}`$, so $`\mathrm{\Gamma }`$ is locally convex. ∎

The proof of the next theorem is the same as the first two paragraphs of the proof of \[3, Theorem 4.1\] except that in the first paragraph, we apply the Cuntz-Krieger uniqueness theorem rather than the gauge-invariant uniqueness theorem to show that $`HI_H`$ is onto.

###### Theorem 5.3.

Let $`(\mathrm{\Lambda },d)`$ be a locally convex row-finite $`k`$-graph such that for every saturated hereditary subset $`H`$ of $`\mathrm{\Lambda }^0`$, $`\mathrm{\Gamma }(\mathrm{\Lambda }H)`$ satisfies condition (B) of Theorem 4.3. Then $`HI_H`$ is an isomorphism of the lattice of saturated hereditary subsets of $`\mathrm{\Lambda }^0`$ onto the lattice of closed ideals of $`C^{}(\mathrm{\Lambda })`$.


text:
# Galaxies and Genes: Towards an Automatic Modeling of Interacting Galaxies

## 1 Introduction

Interacting galaxies are among the most fascinating astronomical objects in the universe. The fate of these galaxies span a wide range from single distant encounters to close encounters which might end in a single merged system. Typical morphologies include e.g. bridges between the interaction partners or tidal tails. These structures are usually the sites of strong star formation resulting in dense star clusters or even dwarf galaxy sized objects. Additionally, a central star burst might be triggered by tidally induced bars which funnel matter to the galactic centre. This coupling between galactic dynamics and ”microphysical” processes (like star formation) provides a unique tool for a deeper understanding of galactic evolution.

An important prerequisite for the analysis of dynamically induced mechanisms is the knowledge of the dynamics of the interaction itself. E.g. the age of a tidally formed stellar system derived from a colour-magnitude diagram should be related to the time passed by since the last perigalactic passage(s) (though they need not to be identical). The main difficulty for a detailed modeling is the extended parameter space which contains orbital and structural parameters of both interacting galaxies. Already a simple interaction of a galactic disk with a galaxy described by a point mass needs 7 parameters. Covering this parameter space by a ”complete” grid of 10 grid points per dimension requires more than 4 years of CPU time on a GRAPE5 special purpose computer. More efficient search strategies like gradient methods suffer from their dependence on initial conditions and, thus, a possible trapping in local optima.

An alternative are genetic algorithms (GAs) (Holland 1975, Charbonneau 1995) coupled with fast N-body methods. Because GAs need about $`10^4`$ or more simulations, a single simulation should not exceed 10 CPU secs. Contrary to self-consistent simulations, restricted N-body simulations (Toomre & Toomre 1972) can be performed in one or a few CPU seconds on a modern PC. Hence, they allow for a fast investigation of the parameter space including both, finding a good fit and testing preferred models on their uniqueness (Wahde 1998, Theis 1999).

So far, the GA-based analyses have been used to model artificial data generated by restricted N-body simulations. By this, the uniqueness of preferred interaction scenarios for NGC 4449 (Theis & Kohle 2001) and NGC 4631 (Theis & Harfst 2001) have been tested. In this paper, we investigate if and how observed data can be modeled automatically without the need of a known reference model calculated by a restricted N-body simulation. In the next section we describe the basics of genetic algorithms. In Sect. 3 we study two cases: First, we generate an artificial FITS image from a self-consistent N-body simulation and try to fit it by our GA. In the second test, we use HI observations as direct input (data from M 51). The results are summarized in Sect. 4.

## 2 Genetic Algorithm

The main idea of genetic algorithms is the application of evolutionary mechanisms in order to ’breed’ a more and more adapted population (Fig. 1). Each member of a population represents a single point in parameter space, i.e. a N-body simulation with a given set of parameters. The members are characterized by their fitness which quantifies the correspondance between the simulations and the reference map (observation or numerical model). In order to determine the ’parents’ two individuals are selected according to their fitness. These parents are two points in parameter space. The parameters of each individual are converted to a ”universal” alphabet (here 4-digit numbers) and then combined to a single string, the ’chromosome’. This chromosome is subject to a cross-over111Cross-over e.g. is realized by swapping the ends of two chromosomes at a randomly chosen cross-over position. and a mutation operation resulting in a new individual which is a member of the next generation. Such a breeding is repeated until the next generation has been formed. Finally, the whole process of creating new generations is repeated iteratively until the population confines one or several regions of sufficiently high fitness in parameter space. For more details see Theis (1999) or Theis & Kohle (2001).

In addition to the advantage of GAs to be almost independent on the initial (randomly) chosen population and, hence, their ability to leave local optima, GAs are easily parallelized. Using a master-slave technique a single fit can be done in a few CPU minutes on a CRAY T3E or a large Beowulf cluster (Theis & Harfst 2000).

## 3 Towards an automatic fitting procedure

### 3.1 Recovering artificial intensity maps

This section describes two tests. In the first test we use a self-consistent model of NGC 4449. We ”observe” it with a numerical telescope and use the derived FITS image as an input for our GA. Contrary to previous applications this task checks the applicability of FITS images as an input source of the GA. Additionally (and more important), it tests whether the restricted N-body models can be used to fit a system with an independently derived map: here differences between the restricted N-body and the self-consistent simulations concern e.g. the treatment of the halo and the initial setup of the disk (no dark halo and – initially – only purely circular motions in the case of restricted N-body simulations).

The self-consistent numerical model is identical to the $`e=0.5`$ model of Theis & Kohle (2001). Fig. 2 shows the particle distribution of the N-body simulation and the derived intensity map (contour lines). The comparison between this reference map and the numerical simulations, i.e. the determination of the fitness, is performed by $`f=1/w_id_i`$, where the sum extends over all grid cells. $`d_i`$ quantifies the deviation between both maps. It can be calculated e.g. from relative or absolute differences of the intensities. $`w_i`$ is the statistical weight of a cell. If all cells have equal weight, we get here a poor fit, as Tab. 1 demonstrates (though some parameters like the orientation of the disk are nicely reproduced).

A much better fit can be achieved, if the tidally induced structures get a larger statistical weight. As an example we split the fitness grid into three regions (Fig. 2, right): One region contains the main tidal feature, the streamers (dark), another one covers the region where galactic matter is found ($`w_i=1`$) and, finally, there is a region without any particles. Already a weight of $`w_i=4`$ of the streamers improves the result substantially: all parameters are recovered within 15% accuracy, most of them even much better.

### 3.2 Recovering observational intensity maps

As a second test we used HI observations of M 51 (Rots et al. 1990) as a direct input for our genetic algorithm. The HI data are shown in the upper left diagram of Fig. 3. The centers of both galaxies are in the dark area covering only two adjacent grid cells. However, the HI distribution is much more extended. Assuming that these structures are formed by galactic tides, they should be the prime targets for modeling the interaction of NGC 5194 and NGC 5195. Therefore, we increased their statistical weight in the GA analysis.

Typically, the GA easily recovers the extended tidal arm in the south-east. Additionally, HI is found north of NGC 5195, though its detailed structure is more difficult to model. Different to the artificial maps created by an N-body simulation, the error cannot be estimated from the known solution. Therefore, we compared the results of a small series of different GA runs. The relative deviation of the derived parameters varies between a few percent (the orbital inclination) up to 25% (e.g. eccentricity, mass ratio of the galaxies). It is remarkable that all models are characterized by a highly inclined ($`i=73^{}\pm 3^{}`$), elliptical ($`e=0.72\pm 0.15`$) orbit. The mass ratio of both galaxies is $`q=0.29\pm 0.06`$.

## 4 Summary

We have demonstrated that GA-based fitting strategies cannot only be used to check the uniqueness of preferred interaction scenarios, but also for an automatic fit of given observational high-quality data. Different to uniqueness tests where the same numerical procedures are applied for the generation of reference maps and the GA fitting procedure, it is – at least – useful (if not necessary) to emphasize tidally affected structures by a larger statistical weight. In that case the GA is able to reproduce given intensity maps (here for M 51 and NGC 4449). The interaction parameters are determined within a statistical error of 25% or better.

As a next step we plan to use the velocity information for the fitness calculation. At least for some interacting galaxies, we expect to get better constrained models, as Salo & Laurikainen (2000) demonstrated in the case of M 51.

Acknowledgements. The authors are grateful to Paul Charbonneau and Barry Knapp for providing their (serial) genetic algorithm pikaia. Additionally, we thank Albert Bosma and Lia Athanassoula for providing us with the HI data of M 51. The artificial intensity map of the self-consistent simulation was created with the NEMO N-body analysis package.

References

Charbonneau P., 1995, Astrophys. J. Supp., 101, 309

Holland J., 1975, Adaptation in natural and artificial systems, Univ. of Michigan Press, Ann Arbor

Rots A.H., Bosma A., van der Hulst J.M. et al., 1990, Astron. J., 100, 387

Salo H., Laurikainen E., 2000, Mon. Not. R. Astron. Soc., 319, 377

Theis Ch., 1999, Rev. Mod. Astron., 12, 309

Theis Ch., Harfst S., 2000, in Dynamics of Galaxies: from the Early Universe to the Present, F. Combes et al. (eds.), ASP conf. ser. 197, p. 357

Theis Ch., Harfst S., 2001, in Proc. of Evolution of Galaxies. I – Observational clues, Granada, J. Vilches et al. (eds.), in press

Theis Ch., Kohle S., 2001, Astron. Astrophys., in press (see also astro–ph/0104304)

Wahde M., 1998, Astron. Astrophys. Supp., 132, 417