text:
# Groups of small homological dimension and the Atiyah Conjecture

## 1 Notation

Throughout this paper let $`G`$ be a (discrete) group. It has *homological dimension $`n`$* if $`H_p(G;M)=\mathrm{Tor}_p^G(,M)`$ vanishes for each $`G`$-module $`M`$ and each $`p>n`$. It has *cohomological dimension $`n`$* if $`H^p(G;M)=\mathrm{Ext}_G^p(,M)`$ vanishes for each $`G`$-module $`M`$ and each $`p>n`$.

We call $`G`$ *locally free* if each finitely generated subgroup is free. The *class of elementary amenable groups* is defined as the smallest class of groups, which contains all finite and all abelian groups and is closed under taking subgroups, taking quotient groups, extensions and directed unions. Each elementary amenable group is amenable, but the converse is not true.

## 2 Review of the Atiyah Conjecture

Denote by $`𝒩(G)`$ the group von Neumann algebra associated to $`G`$ which we will view as a ring (not taking the topology into account) throughout this paper. For a $`𝒩(G)`$-module $`M`$ let $`dim_{𝒩(G)}(M)[0,\mathrm{}]`$ be its dimension in the sense of \[8, Theorem 6.7\]. Let $`\frac{1}{𝒩(G)}`$ be the additive abelian subgroup of $``$ generated by the inverses $`|H|^1`$ of the orders $`|H|`$ of finite subgroups $`H`$ of $`G`$. Notice that $`\frac{1}{𝒩(G)}`$ agrees with $``$ if and only if $`G`$ is torsion-free.

###### Conjecture 1 (Atiyah Conjecture).

Consider a ring $`A`$ with $`A`$. The *Atiyah Conjecture for $`A`$ and $`G`$* says that for each finitely presented $`AG`$-module $`M`$ we have

$$dim_{𝒩(G)}\left(𝒩(G)_{AG}M\right)\frac{1}{𝒩(G)}.$$

For a discussion of this conjecture and the classes of groups for which it is known we refer for instance to \[8, Section 10.1\]. It is not clear whether the Atiyah conjecture is subgroup closed; however in the case $`G`$ is torsion-free, then it certainly is. This can be seen from \[8, Theorem 6.29(2)\]. We mention Linnell’s result  that the Atiyah Conjecture is true for $`A=`$ and all groups $`G`$ which can be written as an extension with a free group as kernel and an elementary amenable group as quotient and possess an upper bound on the orders of its finite subgroups. The Atiyah Conjecture has also been proved by Schick  for $`A=`$ and torsion-free groups $`G`$ which are residually torsion-free elementary amenable.

## 3 Results

###### Theorem 2.

A locally free group $`G`$ has homological dimension $`1`$.

If $`G`$ is a group of homological dimension $`1`$ and the Atiyah Conjecture 1 holds for $`G`$, then $`G`$ is locally free.

###### Theorem 3.

Let $`G`$ be an elementary amenable group of cohomological dimension $`2`$. Then

1. Suppose that $`G`$ is finitely generated. Then $`G`$ possesses a presentation of the form

$$x,yyxy^1=x^n.$$

In particular there is a finite $`2`$-dimensional model for $`BG`$ and the trivial $`G`$-module $``$ possesses a $`2`$-dimensional resolution by finitely generated free $`G`$-modules;
2. Suppose that $`G`$ is countable but not finitely generated. Then $`G`$ is a non-cyclic subgroup of the additive group $``$.

## 4 Proofs

###### Lemma 4.

Let $`A`$ be a ring with $`A`$. Let $`P`$ be a projective $`AG`$-module such that for some finitely generated $`AG`$-submodule $`MP`$ we have $`dim_{𝒩(G)}(𝒩(G)_{AG}P/M)=0`$. Then $`P`$ is finitely generated.

Proof: Choose a free $`AG`$-module $`F`$ and $`AG`$-maps $`i:PF`$ and $`r:FP`$ with $`ri=\mathrm{id}`$. Since $`MP`$ is finitely generated, there is a finitely generated free direct summand $`F_0F`$ with $`i(M)F_0`$ and $`F_1:=F/F_0`$ a free $`AG`$-module. Hence $`i`$ induces a map $`f:P/MF_1`$. It suffices to show that $`f`$ is trivial because then $`i(P)F_0`$ and the restriction of $`r`$ to $`F_0`$ yields an epimorphism $`F_0P`$.

Let $`g:AGP/M`$ be any $`AG`$-map. The map $`𝒩(G)_{AG}(fg)`$ factorizes through $`𝒩(G)_{AG}P/M`$. Hence its image has von Neumann dimension zero because $`dim_{𝒩(G)}`$ is additive \[8, Theorem 6.7\] and $`dim_{𝒩(G)}(𝒩(G)_{AG}P/M)=0`$ holds by assumption. Since the von Neumann algebra $`𝒩(G)`$ is semi-hereditary (see \[8, Theorem 6.5 and Theorem 6.7\]), the image of $`𝒩(G)_{AG}(fg)`$ is a finitely generated projective $`𝒩(G)`$-module, whose von Neumann dimension is zero, and hence is the zero-module. Therefore $`𝒩(G)_{AG}(fg)`$ is the zero map. Since $`AG𝒩(G)`$ is injective, $`fg`$ is trivial. This implies that $`f`$ is trivial since $`g`$ is any $`AG`$-map. ∎

###### Lemma 5.

Let $`A`$ be a ring with $`A`$. Suppose that there is a positive integer $`d`$ such that the order of any finite subgroup of $`G`$ divides $`d`$ and that the Atiyah Conjecture holds for $`A`$ and $`G`$. Let $`N`$ be a $`AG`$-module. Suppose that $`dim_{𝒩(G)}(𝒩(G)_{AG}N)<\mathrm{}`$. Then there is a finitely generated $`AG`$-submodule $`MN`$ with $`dim_{𝒩(G)}(𝒩(G)_{AG}N/M)=0`$.

Proof: Since $`N`$ is the colimit of the directed system of its finitely generated $`AG`$-modules $`\{M_iiI\}`$ and tensor products commute with colimits, we get $`\mathrm{colim}_{iI}𝒩(G)_{AG}N/M_i=0`$. Additivity (see \[8, Theorem 6.7\]) implies $`dim_{𝒩(G)}(𝒩(G)_{AG}N/M_i)<\mathrm{}`$ for all $`iI`$ since $`dim_{𝒩(G)}(𝒩(G)_{AG}N)<\mathrm{}`$ holds by assumption. We conclude from Additivity and Cofinality (see \[8, Theorem 6.7\]) and the fact that the functor colimit over a directed system of modules is exact

$$inf\{dim_{𝒩(G)}(𝒩(G)_{AG}N/M_i)iI\}=0.$$

The assumption about $`G`$ implies using \[8, Lemma 10.10 (4)\]

$$ddim_{𝒩(G)}(𝒩(G)_{AG}N/M_i).$$

Hence there must be an index $`iI`$ with $`dim_{𝒩(G)}(𝒩(G)_{AG}N/M_i)=0`$. ∎

Proof of Theorem 2: A finitely generated free group has obviously homological dimension $`1`$. Since homology is compatible with colimits over directed systems (in contrast to cohomology), we get for every group $`G`$, which is the directed union of the family of subgroups $`\{G_iiI\}`$, and every $`G`$-module $`M`$

$$H_n(G;M)=\mathrm{colim}_{iI}H_n(G_i;\mathrm{res}_iM),$$

where $`\mathrm{res}_iM`$ is the restriction of $`M`$ to a $`G_i`$-module. Hence any locally free group has homological dimension $`1`$.

Suppose that $`G`$ has homological dimension $`1`$. Let $`HG`$ be a finitely generated subgroup. Then the homological dimension of $`H`$ is $`1`$. Since each countably presented flat module is of projective dimension $`1`$ \[1, Lemma 4.4\], we conclude that the cohomological dimension of $`H`$ is $`2`$. We can choose an exact sequence $`0PH^sH`$, where $`s`$ is the number of generators and $`P`$ is projective. Since the homological dimension is $`1`$, the induced map $`𝒩(H)_{𝒩(H)}P𝒩(H)_{𝒩(H)}H^s`$ is injective and hence $`dim_{𝒩(H)}(𝒩(H)_{𝒩(H)}P)dim_{𝒩(H)}(𝒩(H)_{𝒩(H)}H^s)=s`$. Suppose that $`G`$ satisfies the Atiyah Conjecture. Since $`G`$ cannot contain a non-trivial finite subgroup, $`H`$ also satisfies the Atiyah Conjecture, and Lemma 4 and Lemma 5 imply that $`P`$ is finitely generated. Hence $`H`$ is of type $`FP`$. Since each finitely presented flat module is projective \[1, Lemma 4.4\], the cohomological dimension and the homological dimension agree for groups of type $`FP`$. Hence $`H`$ has cohomological dimension $`1`$. A result of Stallings  implies that $`H`$ is free. ∎

In  the notion of Hirsch length for an elementary amenable group was defined, generalizing that of the Hirsch length of a solvable group. This was used in the proof of \[5, Corollary 2\] to show that an elementary amenable group of finite cohomological dimension is virtually solvable with finite Hirsch number, see \[4, Theorem 1.11\] for further details. We can now state

###### Lemma 6.

If $`G`$ is an elementary amenable group of homological dimension $`2`$, then $`G`$ is metabelian.

Proof: A group is metabelian if and only if each finitely generated subgroup is metabelian. Hence we can assume without loss of generality that $`G`$ is finitely generated. Then by the above remarks and \[1, Theorem 7.10(a)\], $`G`$ is virtually solvable of Hirsch length $`2`$.

If $`G`$ has Hirsch length 1, then $`G`$ is infinite cyclic, so we may assume that $`G`$ has Hirsch length 2. Let $`N`$ denote the Fitting subgroup of $`G`$ (so $`N`$ is generated by the nilpotent normal subgroups of $`G`$ and is a locally nilpotent normal subgroup).

Suppose that $`N`$ has finite index in $`G`$. Then $`N`$ is finitely generated and is therefore free abelian of rank 2. Also $`G/N`$ acts faithfully by conjugation on $`N`$ (a torsion-free group with a central subgroup of finite index must be abelian). If $`gGN`$, then $`g^rN1`$ for some positive integer $`r`$ and thus $`g`$ fixes a nonidentity element of $`N`$. We deduce that $`|G/N|2`$ and it follows that $`G`$ is metabelian.

On the other hand if $`N`$ has infinite index in $`G`$, then it has Hirsch length 1. Hence every finitely generated subgroup of $`N`$ is trivial or isomorphic to $``$. This implies that $`N`$ is abelian and any automorphism of finite order $`f:NN`$ has the property that $`f(x)\{x,x\}`$ holds for $`xN`$. Since the group $`G/N`$ acts faithfully by conjugation on $`N`$ and is virtually cyclic, we conclude that $`G/N`$ is isomorphic to $``$ or $`\times /2`$. Hence $`G`$ is metabelian. ∎

Proof of Theorem 3: Since $`G`$ has cohomological dimension 2, it certainly has homological dimension at most 2 and so by Lemma 6 is metabelian. A result of Gildenhuys \[2, Theorem 5\], states that a solvable group $`G`$ of cohomological dimension 2 has a presentation of the form $`x,y;y^1xy=x^n`$ for some $`n`$ if $`G`$ is finitely generated and is a non-cyclic subgroup of the additive group $``$ if $`G`$ is not finitely generated. Given a torsion free finitely generated one-relator group $`G`$, the finite two-dimensional $`CW`$-complex associated to a presentation with finitely many generators and one non-trivial relation is a model for $`BG`$ (see \[7, Chapter III §§9 -11\]). This finishes the proof of Theorem 3. ∎

Address:
Peter Kropholler, Department of Mathematics, University at Glasgow, University Garden, Glasgow G12 8QW, Scotland, p.h.kropholler@maths.gla.ac.uk, http://www.maths.gla.ac.uk/people/?id=289
Peter Linnell, Department of Mathematics, Virginia Tech, Blacksburg, VA 24061-0123, USA, linnell@math.vt.edu, http://www.math.vt.edu/people/linnell/
Wolfgang Lück, FB Mathematik, Universität Münster, Einsteinstr. 62, D-48149 Münster, Germany, lueck@math.uni-muenster.de, http://wwwmath.uni-muenster.de/math/u/lueck/


format: text

text:
# Mg-Ni-H films as selective coatings: tunable reflectance by layered hydrogenation

\[

## Abstract

Unlike other switchable mirrors, Mg2NiHx films show large changes in reflection that yield very low reflectance (high absorptance) at different hydrogen contents, far before reaching the semiconducting state. The resulting reflectance patterns are of interference origin, due to a self-organized layered hydrogenation mechanism that starts at the substrate interface, and can therefore be tuned by varying the film thickness. This tunability, together with the high absorptance contrast observed between the solar and the thermal energies, strongly suggests the use of these films in smart coatings for solar applications.

\]

The discovery of the YHx switchable mirrors by Huiberts et al.  in 1996 has been followed by extensive studies on rare-earth hydride films. Upon absorbing hydrogen, a switchable mirror transforms from a shiny metal to a transparent semiconductor. The same behaviour was later observed in Mg-alloyed rare-earth hydrides  and Mg-Ni hydrides . However, at low hydrogen concentration the Mg-Ni hydrides also present a third intriguing ”black” state with low reflectance and zero transmittance in the whole visible range, which immediately suggests their application as switchable smart coatings in, e.g. solar heat collectors.

Since this type of applications generally involves absorption of the solar spectrum (at photon energies between 0.5$`<`$ $`E<`$ 4 eV) and/or emission of thermal radiation (at $`E<`$ 0.5 eV, for 100oC), investigation of the switching behavior in the infrared is also essential. In this letter, we study the peculiar optical patterns observed in MgyNiHx films ($`y`$2) during hydrogenation (0$`<x<`$4) in the infrared between $`0.2<E<1`$ eV ($`1.2<\lambda <6.2`$ $`\mu `$m), with special attention to their applicability as selective tunable absorbers.

Films of MgyNi (1.4$`<y<`$2.4), with a thickness between 140 and 500 nm, are deposited on CaF2 substrates by magnetron sputtering from a Mg target with Ni additions. The background and Ar pressures are $`10^5`$ Pa and 1 Pa, respectively. The films are covered with a thin (3–11 nm) Pd layer both to protect the films against oxidation and to catalyze the hydrogen uptake. Profilometry and Rutherford backscattering (RBS) are used to measure the film thickness and composition. Optical measurements at near normal incidence ($`15^{}`$) are performed from the substrate side in situ during hydrogen loading and unloading in a Bruker IFS 66 Fourier transform infrared spectrometer. Simultaneously, the electrical resistivity of the film is recorded in a Van der Pauw configuration. During loading, the hydrogen gas pressure is adjusted between $`10^2`$ and $`10^5`$ Pa, depending on the kinetics of the sample. For unloading, the films are exposed to air at temperatures between 30 and 120C.

MgyNi ($`y2`$) films exhibit metallic behavior with resistivities, $`\rho `$, of about 50 $`\mu \mathrm{\Omega }`$cm and high reflectance values that vary between 0.85 at 0.2 eV and 0.6 at 1 eV. As shown in Fig. 1 for 0.85 eV ($`\lambda `$= 1.46 $`\mu `$m), already a small amount of H in the films (short loading times or low $`\rho `$) is enough to dramatically decrease the reflectance while the resistivity still shows clear metallic behavior. This highly-absorbing state is the natural extension to infrared energies of the ”black state” observed in Mg2NiHx films in the whole solar range. Further increase of the hydrogen content produces alternating recovery and loss of reflectance and reveals that the highly-absorbing states are not, or not only, related to a particular hydrogen composition. Finally, Mg2Ni is transformed into Mg2NiH4, which is a semiconductor with a band gap of about 1.6 eV, and the film becomes transparent, as indicated by the onset of the transmittance $`T`$ in Fig. 1. In the fully loaded state $`\rho `$ is of the order of 10 m$`\mathrm{\Omega }`$cm.

Figure 2 shows contour plots of the reflectance $`R`$, as a function of photon energy, $`E`$, and resistivity (an indirect measure of $`x`$), during loading, for films of various thickness, $`d`$. For a specific $`E`$, the $`R`$ pattern as a function of $`\rho `$ produces a plot similar to that in Fig.1. In Fig. 2a the reflectance is also depicted during unloading, showing the reversibility of the hydrogenation process. It is clearly observed that the reflectivity oscillations during loading (or unloading) evolve into the interference fringes of the fully-loaded transparent state, which already points to a common origin for both of them. Since the measurements are performed from the substrate side, the existence of interference already in the first stages of the hydrogenation process, when there is still no transmission through the film, can only be explained by the formation of a well defined transparent layer, presumably Mg2NiH4, at the substrate-film interface. This layer, of thickness $`t(x)<d`$, grows during H loading and finally reaches the total thickness of the film, $`d`$. The two main features observed in Fig 2, namely, the hyperbolic-like bending of the minima and maxima as a function of the energy, and the increment of the number of reflectance oscillations with increasing thickness, are consistent with this model. This can be qualitatively understood from the interference condition $`2t(x)n=N\lambda `$ $`N/E`$, where $`n`$ and $`N`$ are the refraction index and interference order, respectively. Quantitative evidence of this phenomenon has been obtained by modelling the reflection and transmission of a three-layer stack (Pd-Mg2NiH0.3-Mg2NiH4) at various hydrogenation stages. It is worth to notice that the same self-organized layered mechanism occurs during unloading in a completely reversible way (see Fig. 2a).

The observed fringes lead to a switchable and highly tunable reflectance, $`R`$, or absorptance, $`A`$ (during loading, when there is no transmission through the film, $`A=1R`$), and strongly suggest the use of these films as smart coatings. Figure 3 shows the reflectance as a function of photon energy for different loading stages (A to E in Fig. 2a), in a film with $`d`$= 475 nm. The metallic reflectance of the unloaded film (stage A), as high as 0.85 at 0.2 eV, is plotted in Fig. 3a. With only a small amount of hydrogen added, at a composition of about Mg2NiH0.6 (the average H content depending on $`d`$), the film becomes black. The reflectance decreases drastically at $`E>`$ 0.5 eV ($`\lambda <`$2.5 $`\mu `$m), and varies between 0.05 and 0.3 at 0.5$`<E<`$ 4 eV (see Fig. 3b and ref.), while it is still reflecting ($`R>`$ 0.6) in the thermal range. By linearly extrapolating the reflectance of Fig. 3b to low energies and convoluting $`A=1R`$ with the blackbody radiation at 100oC, one can estimate the thermal emittance in this state to be about 0.16. Similarly, a solar absorptance of about 0.84 is estimated by using the data at $`E>`$ 0.5 eV in the same figure together with those obtained for similar films at energies up to 4 eV. These high solar absorptance and low thermal emittance are comparable to those recently reported for films of a-Si:H/Ti on Al substrates, proposed as good candidates for selective coatings in solar collectors. The main advantage of the Mg2Ni films is that their behaviour is switchable. Moreover, the small amount of H needed, which involves minimal morphology changes and thus little aging, makes the switching between A and B very attractive from the applications point of view. Another advantage of these films is the simplicity of the design since the active layer is a single film which in itself switches between reflecting and absorbing.

Upon increasing the H content (stage C) a very different reflectance pattern is measured with a narrow highly absorbing state at $`0.4`$ eV ($`\lambda `$ 3.1 $`\mu `$m), whose energy and width can be tuned by varying the film thickness. Due to the layered loading mechanism, the reflectance spectrum at this state of the loading process is identical to that of a later loading stage in a thinner 250 nm film (F), as shown in Fig. 3c. A larger H content in a thick enough film gives raise to more than one $`R`$ minima (D).

As shown above, a transparent MgyNiHx ($`x=4`$ for $`y=2`$) growing layer determines the reflectance spectra, even at the initial loading states. The spectrum in Fig. 3d shows the interference pattern observed when the whole film is transparent. The solid line is the result of fitting $`R`$ and $`T`$ ($`T`$ not shown for clarity) to those of a MgyNiHx film with a Pd cap layer, both of known thickness and unknown $`n`$ and absorption coefficient, $`k.`$ The optical constants obtained for the transparent layer from the fits of the films under study are in between 2.5$`n`$4.0 and 0.01$`k`$1.5, depending on composition, in the investigated energy range. The lowest $`k`$ values are desirable since they produce the largest interference contrast. This can be observed by comparing the high contrast of the film in Fig. 1, with $`k`$ 0.03 and the lower contrast of the film in Fig. 2c with $`k`$ 1.

Nucleation of the transparent layer at the film-substrate interface is observed for all compositions under study, however the Mg/Ni ratio influences the growth of the transparent layer. In slightly Mg-rich films with 2.0$`<y<`$ 2.4 only the first minimum and maximum are observed, in agreement with Isidorsson et al.. The contrast is also found to greatly decrease with the Mg content for 2.0$``$ $`y`$ $`<`$ 2.4, pointing to the formation of a hydride layer with ill-defined interfaces. Whether the role of the Mg/Ni ratio is direct, e.g. due to the catalytic properties of Ni, or indirect, e.g. due to the low degree of crystallinity of the Ni-rich films is not clear yet. Work is in progress to elucidate the catalytic properties of the substrate-film interface and the role of the Mg/Ni ratio during loading.

In summary, MgyNiHx films with y$``$ 2 are particularly suitable as smart coatings due to their energy tunability, high reflectance contrast and switching capabilities. While the metallic state reflects about 60 % of the incoming solar radiation, a small amount of H is enough to change from reflective to black, absorbing 84% of the solar spectrum. As the film in this state emits only 16% of the 100oC blackbody radiation , it can be used as a switchable solar absorber in solar collectors. Such absorbers can be temperature controlled, which make them also ideally suited for integration with photovoltaic cells.

The authors are grateful to A. Borgschulte, S. Enache, I.A.M.E. Giebels and A.C. Lokhorst for very useful discussions. Support from the Dutch Stichting voor Fundamenteel Onderzoek der Materie (FOM) and the Stichting Technische Wetenschappen (STW) is also acknowledged.


text:
# 1. The hypermetric cone

## 1. The hypermetric cone

For more details on the material of this Section see Chapters $`13`$$`16`$ of (7). For the use of affine basis and hypermetrics for computing combinatorial types of Delaunay polytopes, see (9).

Denote by $`S(c,r)`$ the sphere of center $`c`$ and radius $`r`$. For every family $`𝐀=\{v_0,\mathrm{},v_m\}`$ of vertices of a Delaunay polytope $`P`$ circumscribed by the sphere $`S(c,r)`$ one can define a distance function $`d_𝐀`$ by $`(d_𝐀)_{ij}=v_iv_j^2`$. The function $`d_𝐀`$ turns out to be a hypermetric by the following formula (see (1) and (7) p. 195) :

$$H(b)d_𝐀=\underset{0i,jm}{}b_ib_j(d_𝐀)_{ij}=2(r^2\underset{i=0}{\overset{m}{}}b_iv_ic^2)0.$$

On the other hand, Assouad has shown in (1) that every $`dHYP_{n+1}`$ can be expressed as $`d_𝐀`$ with $`𝐀`$ being a family of vertices of a Delaunay polytope $`P`$ of dimension less or equal to $`n`$.

###### Definition 1.

Let $`P`$ be an $`n`$-dimensional Delaunay polytope with vertex-set $`𝐕`$.

(i) A family $`v_0`$, …, $`v_n`$ of vertices of $`P`$ is called an affine basis if for all $`v𝐕`$ there exists an unique vector $`b=(b_i)_{0in}Z^{n+1}`$, such that

$$\underset{i=0}{\overset{n}{}}b_iv_i=v\text{ and }\underset{i=0}{\overset{n}{}}b_i=1.$$

(ii) The Delaunay polytope $`P`$ is called basic if it has at least one affine basis. The vertices of an affine basis are called basic vertices.

All Delaunay polytopes of dimension less, than $`6`$, are basic (see (9)). The adjacency method, described later, applies only to basic Delaunay polytopes. There is no proof that all Delaunay polytopes are basic and the only indication for this conjecture is that all known Delaunay polytopes are basic (see (7)).

The metric cone $`MET_{n+1}`$ is defined as the set of functions $`d=(d_{ij})_{0i<jn}`$ satisfying all triangular inequalities $`d_{ij}d_{ik}+d_{jk}`$; such inequalities correspond to the hypermetric inequality with vector $`b`$, such that $`b_i=b_j=1`$, $`b_k=1`$ and $`b_l=0`$, otherwise. Therefore $`HYP_{n+1}MET_{n+1}`$.

Given $`dHYP_{n+1}`$ we define

$$Ann(d)=\{bZ^{n+1}\text{ : }\underset{i=0}{\overset{n}{}}b_i=1\text{ and }H(b)d=0\}.$$

###### Theorem 1.

Let $`P`$ be an $`n`$-dimensional extreme Delaunay polytope and $`𝐁=\{v_0,\mathrm{},v_n\}`$ an affine basis of $`P`$. Then the following statements hold:

(i) The mapping $`b_{i=0}^nb_iv_i`$ establishes a bijection between $`Ann(d)`$ and the vertex-set of $`P`$.

(ii) It is possible to compute (in finite time) the list of hypermetric inequalities $`H(b_i)d0`$ with $`1im`$ incident to $`d_𝐁`$.

(iii) $`P`$ has at least $`\frac{(n+2)(n+1)}{2}1`$ vertices. If it has exactly $`\frac{(n+2)(n+1)}{2}1`$ vertices, then all $`b_i`$ correspond to facets of $`HYP_{n+1}`$. If $`P`$ has more vertices, then it is possible to compute in finite time which of the $`b_i`$ correspond to facets of $`HYP_{n+1}`$.

###### Proof.

Let $`S(c,r)`$ be the empty sphere around $`P`$ and let us write the affine basis as $`v_0`$, …, $`v_n`$. The equality $`H(b)d_𝐁=0`$ corresponds to

$$\begin{array}{ccc}\hfill H(b)d_𝐁& =& 2(r^2_{i=0}^nb_iv_ic^2)=0\hfill \\ & =& 2(r^2v_0c+_{i=1}^nb_i(v_iv_0)^2)=0.\hfill \end{array}$$

This establishes a bijection between solutions of the equation $`H(b)d_𝐁=0`$ and vertices of the Delaunay polytope $`P`$.

Moreover, the solution-set is exactly a closest vector problem; therefore, it is solvable in finite time. Note that all $`e_i=(0,\mathrm{},1,\mathrm{},0)`$ with $`0in`$ belong to $`Ann(d_𝐁)`$; for those vector $`H(e_i)=0`$, therefore we do not list them in the list of vector $`(b_i)_{1im}`$.

The Delaunay polytope is extreme; therefore, the rank of the system of equations $`H(b_i)d=0`$ is equal to $`\frac{n(n+1)}{2}1`$. This implies $`m\frac{n(n+1)}{2}1`$. Since the vertex-set contains also the affine basis, it has at least $`n+1+m=\frac{(n+1)(n+2)}{2}1`$ vertices.

Any extreme ray of $`HYP_{n+1}`$ is incident to at least $`\frac{n(n+1)}{2}1`$ facets. Therefore, if $`P`$ has $`\frac{(n+1)(n+2)}{2}1`$ vertices, then all the $`H(b_i)`$ are facets of $`HYP_{n+1}`$.

Let us assume that a facet $`H(b_i)`$ is redundant. Then, $`H(b_i)`$ can be expressed as a sum with positive coefficients of other facets of $`HYP_{n+1}`$:

$$H(b_i)=\underset{jJ}{}\alpha _jH(b_j^{})\text{ with }\alpha _j>0$$

The relation $`H(b_i)d_𝐁=0`$ implies that for all $`jJ`$, we have $`H(b_j^{})d_𝐁=0`$. Therefore, $`b_j^{}`$ belongs to the list of $`b_i`$. So, the problem of redundancy is reduced to the one for the list of facets $`H(b_i)`$ with $`1im`$, which is solvable by linear programming (see polyhedral FAQ222http://www.ifor.math.ethz.ch/~fukuda/polyfaq/polyfaq.html).

Above theorem is very useful for finding hypermetric facets. The Delaunay polytopes, whose number of vertices is exactly $`\frac{(n+1)(n+2)}{2}1`$ are especially useful for the adjacency method, by the simplicity of the computation of their adjacencies. The Schläfli polytope and the infinite serie of extreme Delaunay polytopes in (12) satisfy this lower bound.

###### Theorem 2.

$`HYP_8`$ has at least $`298592`$ facets and at least $`86`$ orbits of facets.

###### Proof.

We know that all facets $`H(b)`$ of $`HYP_n`$ yield facets $`H(b^{})`$ of $`HYP_{n+1}`$, with $`b^{}`$ obtained by adding a zero to $`b`$. Since $`HYP_7`$ has $`14`$ orbits of facets (see (10)), this yields $`14`$ orbits.

Moreover, all hypermetric facets of $`CUT_n`$ are facets of $`HYP_n`$. In (4), a conjectural list of orbits of facets of $`CUT_8`$ is computed. This yields $`16`$ orbits of facets of $`HYP_8`$.

We know two extreme Delaunay polytopes in dimension $`7`$: the Gosset polytope and a polytope found by Erdahl and Rybnikov (see (12)). By computing all affine basis of them and using above theorem we obtain some more facets. It is known (see (7) p. 229) that the switchting of a facet of $`HYP_n`$ is again a facet of $`HYP_n`$. Combining all this we obtain $`298592`$ facets of $`HYP_8`$ in $`86`$ orbits.

###### Definition 2.

(i) Two Delaunay polytopes $`P_1`$ and $`P_2`$ are called isomorphic if there exists an isometry transforming one into the other.

(ii) The automorphism group $`Aut(P)`$ of a Delaunay polytope $`P`$ is the set of all isometries leaving it invariant.

Denote by $`𝐕_1`$ and $`𝐕_2`$ the vertex-sets of $`P_1`$ and $`P_2`$, respectively. In order to test the existence of such an isometry, it suffices to test if there exist a mapping $`\varphi :𝐕_1𝐕_2`$ satisfying to $`d(\varphi (x),\varphi (y))=d(x,y)`$ for all $`x,y𝐕_1`$. The test of existence of an isometry is therefore a combinatorial problem. If the set of possible pairwise distances is $`\{d_1,\mathrm{},d_h\}`$, then the isomorphy problem becomes a problem of isomorphy of association schemes. The problem of computing the automorphism group of a Delaunay polytope is the same as of computing the automorphism group of an association scheme. Unfortunately, we do not know about a program doing such computations.

Therefore, it will be presented here some algorithms doing computations using the nauty program (see (13)). Problem (ii) can be solved easily by associating, to every possible distance $`d`$ between two vertices of $`P`$ the graph $`G_d`$, formed by making two vertices adjacent if $`d(x,y)=d`$. So, we have

$$Aut(P)=_{i=1}^hG_{d_i},$$

Problem (i) can be solved by associating to $`P_1`$ and $`P_2`$ a graph encoding pairwise distances, but this approach leads to graphs, whose size is too big for the nauty program. So, we use procedures, which are not guaranteed to work in any cases but which have worked so far in all cases considered of extreme Delaunay polytopes.

Take two Delaunay polytopes $`P_1`$ and $`P_2`$ and compute their skeleton graphs (i.e. the graph formed by their vertices with two vertices adjacent if they generate a two dimensional face), $`G_1`$ and $`G_2`$, respectively. If those graphs are not isomorphic, then $`P_1`$ and $`P_2`$ are not isomorphic. If they are isomorphic, then there exists an isomorphism $`\varphi :G_1G_2`$. If this mapping satisfies $`d(\varphi (x),\varphi (y))=d(x,y)`$, then $`P_1`$ and $`P_2`$ are isomorphic. This approach does not always work, i.e. some automorphisms of $`G_1`$ do not correspond to isometries of $`P_1`$ and therefore the mapping $`\varphi `$ computed is not the right one.

A similar approach is to consider the ridge graph (i.e. the graph formed by their facets with two facets being adjacent if their intersection is of dimension $`n2`$) $`G_1^{}`$ and $`G_2^{}`$ of $`P_1`$ and $`P_2`$. If $`G_1^{}`$ and $`G_2^{}`$ are not isomorphic, then $`P_1`$ and $`P_2`$ are not isomorphic. If they are isomorphic, then there exists an isomorphism $`\varphi ^{}:G_1^{}G_2^{}`$. Since every vertex is an intersection of some facets, this mapping lifts to an isomorphism $`\varphi :G_1G_2`$. We then test if $`\varphi `$ defines an isometry. In all cases considered, $`\varphi `$ was an isometry, i.e. we were able to check the isomorphy of extreme Delaunay polytopes efficiently. There is no reason to think that this will always be the case.

## 2. The Adjacency Method

We consider in this section the details of the adjacency algorithm that takes an extreme ray $`e`$ of $`HYP_{n+1}`$, corresponding to an $`n`$-dimensional extreme Delaunay polytope and finds the adjacent extreme rays $`(e_i)_{1im}`$ in $`HYP_{n+1}`$.

The problem in doing this computation is that the description of facets of $`HYP_n`$ is known only for $`n7`$ (see (9), (10) and (3)). Anyway, using the complete list of facets is not a good idea, since, for example, $`HYP_8`$ has at least $`298,592`$ facets.

The algorithm, which we use, is as follows:

1. Given an initial extreme ray $`e`$, find the list of hypermetric vectors $`(b_i)_{1im}`$ such that $`H(b_i)e=0`$. We then take as initial list $`𝐅`$ of facets all vectors $`(b_i)_{1im}`$ plus all permutations of $`(1^2,1,0^{n2})`$ (they correspond to triangular inequalities).
2. Define the cone $`𝐂(𝐅)`$ by taking all hypermetric inequality in $`𝐅`$.
3. Since $`e`$ is an extreme ray of the cone $`𝐂(𝐅)`$, we can find the extreme rays $`(e_j)_{1jp}`$ of $`𝐂(𝐅)`$ that are adjacent to $`e`$.
4. Test if $`e_j`$ is hypermetric, using the closest vector problem.
5. If the ray $`e_j`$ is hypermetric, then we finish. If not, then some hypermetric inequalities $`H(b)d0`$ are violated. So, we add those $`b`$ to $`𝐅`$ and go back to step 2.

Since the cone $`HYP_{n+1}`$ is polyhedral, the inner loop will eventually finish.

The key step in above algorithm is the ability to check if $`H(b)d0`$ is true for all vector $`bZ^{n+1}`$ with $`_ib_i=1`$. This is equivalent to

$$H(b)d_𝐁=2(r^2v_0c+\underset{i=1}{\overset{n}{}}b_i(v_iv_0)^2)0.$$

If we denote by $`L`$ the lattice generated by the family $`(v_iv_0)_{1in}`$, then the problem is expressed as

Does there exist $`vL`$ such that $`v_0c+v<r`$?

This problem is a closest vector problem (i) except that the scalar product (which comes from the distance $`d`$) is not always positive definite.

We associate to $`d`$ the Gram matrix $`G=(g_{ij})`$ defined by $`g_{ij}=\frac{1}{2}(d_{i0}+d_{j0}d_{ij})`$.

If $`G`$ admits a negative eigenvalue, then one can find a vector $`vL`$, such that $`v_0c+v<0`$, thereby solving the problem.

If $`G`$ is positive but not positive definite, then this means that $`L`$ is of dimension inferior to $`n`$ and that the $`n+1`$ vectors $`v_i`$ form a Delaunay polytope of a lower dimensional lattice, which is not a simplex. In that case the algorithm is as follows:

1. Find the rank $`r`$ of the matrix $`G`$.
2. Find a family $`𝐅=\{v_{i_0},\mathrm{},v_{i_r}\}`$, such that all points $`v_i`$ can be expressed in terms of $`𝐅`$ with integer coefficient (this is not always possible).
3. If preceding step has succeeded, then the problem takes the form

Does there exist $`b_{i_j}`$, such that $`_{j=0}^rb_{i_j}v_{i_j}cr`$?

The corresponding Gram matrix is positive definite. Therefore, this is a closest vector problem of type (i).

## 3. Example of application of the Adjacency Method

In (6) (see also (7)) an extreme $`15`$-dimensional Delaunay polytope with $`135`$ vertices, i.e. having the minimal number of vertices, is given. We applied the adjacency method to one of its affine basis and found one new extreme Delaunay polytope, let us denote it by $`ED_8`$ of dimension $`8`$. This polytope belongs to an infinite serie $`(ED_n)_{n6}`$ of extreme Delaunay polytopes (see (10)); this serie was found from $`ED_8`$.

We then apply the adjacency decomposition method to the polytope $`ED_8`$ and found $`24`$ extreme Delaunay polytope of dimension $`8`$.

It is well-known (see (7)) that the Gosset polytope $`Gos`$ is an extreme $`7`$-dimensional Delaunay polytope. All orbits of affine basis of $`Gos`$ were found by direct enumeration.

We apply the Adjacency Method to all orbits of affine basis of $`Gos`$ and found an extreme Delaunay polytope of dimension $`7`$ with $`35`$ vertices and a symmetry group of size $`1440`$. In fact, this extreme Delaunay polytope was already found by Erdahl and Rybnikov in (12). We conjecture that there is no other extreme Delaunay polytopes in dimension $`7`$.

REFERENCES

1. P. Assouad (1982), Sous-espaces de $`L^1`$ et inégalités hypermétriques, Compte Rendus de l’Académie des Sciences de Paris, 294(A) 439–442.
2. E.P. Baranovski, Simplexes of $`L`$-subdivisions of Euclidean spaces, Mathematical Notes, 10 (1971) 827-834.
3. E.P. Baranovskii, The conditions for a simplex of $`6`$-dimensional lattice to be $`L`$-simplex, (in Russian) Nauchnyie Trudi Ivanovo state university. Mathematica, 2 (1999) 18–24.
4. T. Christof and G. Reinelt (2001), Decomposition and parallelization techniques for enumerating the facets of combinatorial polytopes, Internat. J. Comput. Geom. Appl., 11-4 423–437.
5. M. Deza and M. Dutour (2003), The hypermetric cone on seven vertices, to appear in Experimental Mathematics.
6. M. Deza, V.P. Grishukhin, and M. Laurent, Extreme hypermetrics and L-polytopes, in G.Halász et al. eds Sets, Graphs and Numbers, Budapest (Hungary), 1991, 60 Colloquia Mathematica Societatis János Bolyai, (1992) 157–209.
7. M. Deza and M. Laurent (1997), Geometry of Cuts and Metrics, Berlin, Heidelberg, New York: Springer Verlag.
8. I. Dinur, G. Kindler, S. Safra (1998), Approximating CVP to within almost-polynomial factors is NP-hard, 39th Annual IEEE Symposium on Foundations of Computer Science.
9. M. Dutour (2003), The six-dimensional Delaunay polytopes, to appear in European Journal of Combinatorics.
10. M. Dutour (2003), Infinite serie of extreme Delaunay polytopes, to appear in European Journal of Combinatorics.
11. M. Dutour (2003), Lattice-CVP, http://www.liga.ens.fr/~dutour/CVP/index.html
12. R. Erdahl and K. Rybnikov, Supertopes, http://faculty.uml.edu/krybnikov/
13. B. McKay, The nauty program, http://cs.anu.edu.au/people/bdm/nauty/
14. F. Vallentin (1999), ShVec, http://www-m10.ma.tum.de/~vallenti/shvec.02nov99.tar.gz

Hebrew University Jerusalem and École Normale Supérieure Paris

e-mail: Mathieu.Dutour@ens.fr


text:
# Determining the Location of the Tip of the Red Giant Branch in Old Stellar Populations: M33, Andromeda I & II.

## 1 Introduction

The accurate determination of distances in the Universe is a fundamental and difficult problem in astronomy. Parallax is the ideal method of distance determination as it is completely independent of the physical nature of the body of interest. However, this geometrical method can only be currently applied successfully in the nearby Galaxy due to limitations in the accuracy of the astrometry required. For systems external to this we are forced to search for some standard candle - an object whose intrinsic brightness we think we know. Measurement of the apparent brightness can then, after correction for extinction effects, lead to an estimate of its actual distance. The most successful and reliable standard candle known in astrophysics is the Cepheid variable, whose well studied Period-Luminosity relation sets the foundation for the entire cosmological distance ladder (see, for example, Tanvir 1999).

One of the limitations of the Cepheid method is that it is confined to relatively massive Population I systems. In order to calculate distances to older, more metal poor galaxies some other standard candle is required. The Tip of the Red Giant Branch (TRGB) offers an ideal alternative for these systems. Physically, this stage in stellar evolution represents the point of the core helium flash. Here, the temperature of the degenerate, quasi-isothermal core is only dependent upon the properties of the thin H-burning shell around it and this varies only very slightly with chemical abundance and surrounding mass. The TRGB is thus of roughly constant intrinsic brightness. Iben & Renzini (1983) realised that for low mass, metal poor stars ($`[\mathrm{Fe}/\mathrm{H}]<0.7`$ dex) the TRGB varies by only $`0^m.1`$ for any star older than 2 Gyrs. The absolute I band magnitude is also found to be constant for these stars as absorption effects in the stellar atmosphere are minimal, but for stars more metal rich than this molecular absorption causes the TRGB to appear dimmer in this band. A more recent study of the theoretical predictions concerning this stage in stellar evolution has been conducted by Salaris & Cassisi (1997) and a comparison with other distance indicators, such as Cepheid and RR Lyrae variables, was made. They found agreement between these methods at the level of $`0^m.1`$.

Da Costa & Armandroff (1990) compared the brightest RGB stars in various globular clusters to the theoretical predictions for core helium ignition and found very good agreement between the two, with only a very weak dependency on metallicity. They were dealing with relatively sparse colour magnitude diagrams however. A more recent study by Bellazzini, Ferraro & Pancino (2001) of the globular cluster $`\omega `$ Centauri came to similar conclusions. They obtained a value of the absolute I band magnitude of the TRGB of $`4^m.04\pm 0^m.12`$. We shall later use this value in order to calculate the distance modulus to several galaxies (see Section 3.2 for a discussion of this result).

Several authors have used various techniques to derive TRGB distances. For example, Harris et al. (1998) used a model fitting technique to the luminosity function, although the most influential method to determine the location of the TRGB is due to Lee et al. (1993). Prior to this publication, estimates of the location of the TRGB had mostly been made by eye. Such a qualitative approach is of course not ideal as it is not reproducible. However, Lee et al. (1993) put the method on a quantitative basis by employing an edge detection algorithm. Essentially, an edge detection algorithm in this context compares neighbouring star counts and looks for the largest absolute change between neighbouring bins - in essence, it models the TRGB edge as a step. Specifically, Lee et al. used a zero-sum Sobel kernel \[-2, 0, 2\] and convolved it with the binned luminosity function. The range over which this kernel is applied is defined by the sampling of the luminosity function. In practise, the output of this displays a maximum in the bin coincident with the largest absolute change in the counts. The midpoint of this bin was then assumed to be the magnitude of the TRGB. Typical uncertainties in this quantity were quoted as $`0^m.10^m.2`$.

Three years later, Sakai et al. (1996) adapted this method to make it independent of binning. They constructed a smoothed luminosity function $`\mathrm{}(m)`$ such that

$$\mathrm{}\left(m\right)=\underset{i=1}{\overset{N_{}}{}}\frac{1}{\sqrt{2\pi }\sigma _i}\mathrm{exp}\left(\frac{\left(m_im\right)^2}{2\sigma _i}\right),$$
(1)
where $`m_i`$ and $`\sigma _i`$ are the magnitude and photometric error of the $`i^{th}`$ star from a sample of $`N_{}`$. In the limit of large $`N_{}`$, the result can be thought of as a luminosity probability distribution. Hereafter, we adopt the abbreviation LPD for this function, to distinguish it from the binned luminosity function. Sakai et al. then convolved this with a smoothed Sobel Kernel, this time in the form of \[-2, -1, 0, 1, 2\] - this kernel is less sensitive to spikes due to Poisson noise than the previously used one, as it allows for some smoothing of the luminosity function over a small range. This allowed them to find the position of the TRGB, as they had defined it, to within an uncertainty of $`0^m.1`$. More recently, Mendez et al. (2002) have refined this method further, and they have also used it in conjunction with a maximum likelihood method. This involved modelling the RGB in the luminosity function as a truncated power law and attributing the TRGB as the location at which the power law is truncated. We believe that such a technique is a significant improvement over the Sobel edge-detection algorithms and it offers many advantages - for example it is much more stable against noise effects. However, a step model (an abrupt cut-off in number counts) is still implicitly assumed as the intrinsic shape of the TRGB in their analysis.

It is not clear that an edge detection algorithm, or any method that assumes a step in the luminosity function, is necessarily the best approach to this problem, as there is no a priori reason why the luminosity function at the location of the tip should be a simple step function. It may equally well be a slope, or a parabola, or something else - the exact shape of the luminosity function at the TRGB edge is currently unknown. We note that Zocacali & Piotto (2000) show that the bright end of RGB luminosity function is well modelled by a simple power law, but there is no model that predicts the shape of the TRGB edge, although this doubtlessly depends upon the number of stars that contribute to the luminosity function. Generally, we might expect the number of stars to decrease gradually over a short magnitude range as we approach the tip from along the RGB. The luminosity function would then exhibit more of a slope at the TRGB, an abrupt change in the bright end of this slope would then be, by definition, the TRGB. The Sobel edge detection algorithm does not always produce a peak in such a situation (see, for example, Figure 1 of Madore & Freedman 1995). In practice, the resulting signal is not easy to detect over and above all the other random variations that the output of this procedure creates when dealing with all but the most idealised noise-free luminosity functions.

In Section 2 of this paper, we review the main difficulties with using the TRGB as a distance indicator. We then describe and test a new algorithm that we have created in order to measure the TRGB location. This algorithm is based upon a least-squares fitting procedure and makes less assumptions about the shape of the luminosity function at the TRGB, working equally well for situations where the TRGB is marked by a sudden or gradual rise in star-counts. This data adaptive slope technique gives uncertainties in the distance modulus obtained typically of order $`0^m.05`$, but most importantly reflects the quality of the luminosity function used. We also demonstrate an additional simple empirical heuristic scheme that allows a first pass estimate of this location to be made. In Section 3 we go on to apply our method to calculate the distances to the spiral galaxy M33 and the dwarf galaxies And I & II.

## 2 Locating the TRGB

### 2.1 Data Considerations

Finding the apparent magnitude of the TRGB in a satisfactory, quantitative manner has proved a challenge with several different techniques having been used in the literature. Madore & Freedman (1995) have already written an excellent review and used computer simulations to analyse the effects of these difficulties on the Sobel edge detection algorithm. They concluded:

1. low signal to noise (S/N) can hide the location of the tip in a luminosity function or lead to the false identification of this point, with a jump due to noise possibly being attributed to the luminosity of core He ignition;
2. bright Asymptotic Giant Branch (AGB) stars can contaminate the luminosity function in the region of the tip, and may hide its true location;
3. foreground stars masquerade as members of the stellar system and will contaminate the luminosity function.

Poisson noise is usually the dominant uncertainty in any luminosity function, and becomes a serious issue if we intend to try and measure a specific location defined by some discontinuity in star-counts. Although the algorithm we describe later is less sensitive to Poisson noise than an edge detection algorithm, or such like, it is still not immune. The only way to overcome Poisson errors successfully is to get photometry for more stars. As well as decreasing the resulting noise in a luminosity function, large star-counts also ensure that the luminosity function we construct from our sample is as close to the underlying luminosity function of the population as possible. Therefore, the most luminous RGB stars are more likely to be at the point of core helium ignition - although we note that Crocker & Rood (1984) conducted Monte-Carlo simulations which suggest that there is a large probability of observing a star close to the tip location even for a sample of relatively few RGB stars. Additionally, the effect of Malmquist bias on a well sampled luminosity function is negligible.

Many previous TRGB distance studies have used Hubble Space Telescope (HST) WFPC2 data (eg. Kim et al. 2002, Maiz-Appellaniz et al. 2002). However, despite WFPC2’s superb resolution, its relatively small field of view (an L-shaped 2.5’ x 2.5’) may sometimes not allow for as large a number of bright RGB stars to be observed as is required for a relatively noise-free luminosity function suitable for TRGB analysis. Instead, wherever possible, to maximise the number of stars observed and to increase the reliability of the TRGB measurement, we advocate the use of ground based wide field cameras, for example the Wide Field Camera on the Isaac Newton Telescope ($`0.29^{}`$ FOV) or MEGACAM on the Canada-France-Hawaii Telescope ($`1^{}`$ FOV). The accuracy of the technique that we introduce later is significantly improved if used on a well-defined luminosity function, although realistic error estimations are obtained regardless of the number of stars contributing to the measurement. In these situations however, we may need to concern ourselves with whether the luminosity function we create is representative of the underlying population.

Having maximised the number of stars with reliable photometry, we then want to increase the S/N for the resultant luminosity function. By signal we refer to RGB stars in the system of interest, and by noise we refer to everything else - AGB stars and foreground stars, in particular. The most obvious way to increase the fraction of RGB stars on the luminosity function is to take the luminosity function along the red giant branch only. This is most easily illustrated by looking at Figure 8, which shows the colour magnitude diagram for And I & II. The luminosity function is only plotted for the stars bounded by the dotted lines. Their positions are determined by taking star counts in strips parallel to the RGB and placing the boundaries on either side of the maximum. The exact position or separation of the boundaries makes no difference to the derived value for the tip, as should be expected. All the other stars outside of this area are ignored, as they contribute nothing to the RGB and would only act to hide the tip. Some bright AGB stars may still be present but their effect has been lessened. Further, as we demonstrate in Section 2.2.1, our technique for finding the RGB appears robust even with a significant AGB population.

Some foreground stars will have survived the cut that we have applied to our data and will be contaminating our RGB luminosity function. We cannot hope to identify foreground stars individually but with wide field data we are able to apply a statistical correction for them by using a luminosity function of a neighbouring region consisting only of foreground stars. Then, assuming all the brighter stars in our fields of interest are foreground objects, we can use these to scale the reference luminosity function to our data if necessary.

Finally, we propose to use, in the same way as Sakai et al. (1996), the LPD given by Equation 1 instead of the normal binned histogram. This makes the process independent of any binning considerations and yields a continuous function for the analysis, with the drawback that the error analysis becomes more complicated than for a normal luminosity function. Taken as a whole, the above methodology creates clean LPDs optimised to measure the TRGB. Further specific discussion of our data is deferred until Section 3 after we have describing the algorithm we are using to analyse LPDs for TRGB locations.

### 2.2 Least-Squares Fitting of an Adaptive Slope

The technique that we use to locate the TRGB involves finding the region on a LPD that shows the most significant decline in star counts. The base of this decline (slope) will be attributable to the TRGB. The main complication arises due to our lack of knowledge of the intrinsic shape of the LPD around the TRGB location, and what gradient best resembles the slope in this region. Fitting an optimum model to the LPD therefore implies a generalised least-squares fitting procedure. Note that the model we use is not defined over the full range of the LPD, as it is not our intention to model the LPD but to locate a specific point of the LPD. By making this our goal we minimise the assumptions that we are forced to make concerning the intrinsic shape of the LPD: we instead repeatedly look at the LPD through a window, and find the window in which the LPD is best fit as a simple slope function, that is, the region that when coming from the faint end demonstrates the most significant decline in star counts.

In least-squares fitting, we seek to find the values of model parameters which for independent errors minimise the function $`\chi ^2`$, given by

$$\chi ^2=\underset{i=1}{\overset{N}{}}\frac{\left(d_im_i\right)^2}{\sigma _i^2}$$
(2)
where $`d_i`$ is the $`i^{th}`$ data point with an uncertainty $`\sigma _i`$, and $`m_i`$ is the corresponding point in the model. Assuming the model chosen is a good one, then the best fit should produce a $`\chi _{min}^2`$ which is equal to the number of degrees of freedom. If we used a single model shape, then we would require only one parameter, $`\tau `$, which would govern the x-axis offset between data and model. However, we do not want to specify the slope to be fitted, and so instead we use a family of templates, $`\varphi _s`$, where $`s`$ is a parameter which governs the gradient of the template. In all, the template is defined over a $`1^m`$ range, chosen empirically as the range that is generally sufficient to show the feature we are attempting to fit, while still allowing our model to be a reasonable approximation to the feature. Since this extends over a shorter x-axis range than the complete LPD, then the y-axis range of the data that we fit to changes with $`\tau `$. We thus need to introduce two scaling parameters to deal with this; a vertical scale factor $`k_{\tau ,s}`$ and a ’dc offset’ $`a_{\tau ,s}`$. For any values of $`s`$ and $`\tau `$, the relationship between the actual model fitted, $`m_{\tau ,s}`$, and the template, $`\varphi _s`$, is then

$$m_{\tau ,s}=k_{\tau ,s}\varphi _s+a_{\tau ,s}$$
(3)
and so we are left to minimise the expression

$$\chi ^2(s,\tau ,k,a)=\underset{i=1}{\overset{N}{}}\frac{\left(d_{i+\tau }\left(k_{\tau ,s}\varphi _{s,i}+a_{\tau ,s}\right)\right)^2}{\sigma _{i+\tau }^2}$$
(4)
where $`N`$ now signifies the number of points defining our template $`\varphi _s`$, and we have defined $`\tau `$ such that it corresponds to an integer number of points in the data. Simple expressions for $`a_{\tau ,s}`$ and $`k_{\tau ,s}`$ may be derived by looking for the values which produce a minimum in $`\chi ^2`$. By defining our templates such that $`_{i=1}^N\varphi _{s,i}=0`$ and assuming a constant error term we then find that

$$a_{\tau ,s}=\frac{1}{N}\underset{i=1}{\overset{N}{}}d_{i+\tau }$$
(5)
$$k_{\tau ,s}=\frac{_{i=1}^Nd_{i+\tau }\varphi _{s,i}}{_{i=1}^N\varphi _{s,i}^2}$$
(6)
A constant error term is a reasonable approximation to the error distribution of the LPD, although its actual error distribution is complicated by the covariance of neighbouring regions. Every point on the LPD is a sum of contributions from every star and so a simple Poisson distribution is not valid. However, given that there are a large number of stars contributing to every point, then the central limit theorem implies that the errors can be well approximated by a constant error in this limit. A check of the validity of this approximation and its effect on the resulting uncertainties on the parameters is conducted with the M33 data in Section 3.3, and it is shown to be robust.

Our method is then as follows: we calculate $`m_{\tau ,s}`$ for every value of $`\tau `$ and $`s`$ by using the above prescription to calculate $`k_{\tau ,s}`$ and $`a_{\tau ,s}`$. We then conduct a simple least-squares fit of these models to the LPD, in $`1^m`$ windows, and we find the values of $`s`$ and $`\tau `$ that minimise $`\chi ^2(s,\tau k_{\tau ,s},a_{\tau ,s})`$. This then gives us the TRGB. Examination of the $`1\sigma `$ contours in the $`\tau s`$ plane also gives us the uncertainty associated with this value. Due to the general nature of this fit, it is possible that at times the method may locate a feature that is nothing to do with the TRGB, but is perhaps due to noise. However, such cases are rare for a well sampled luminosity function, and are generally obvious. They are usually easily identified by visual inspection of the fit and appropriate constraints to the parameters can be applied if neccessary.

#### 2.2.1 Testing the Data Adaptive Least Squares Method

To test the robustness of the data-adaptive slope method, we generated model CMDs that had a TRGB at 20th magnitude, marked by a steady rise in star counts. Photometric noise was added by selecting a value from a gaussian distribution with $`\sigma =0^m.02`$, the typical photometric uncertainty in our data at 20th magnitude. It should be noted that we experimented with different error weightings but found it had a negligible effect on our results, as in the range of interest around the TRGB the photometric error is well approximated by an error of $`0^m.02`$. We used a background of 8000 stars randomly distributed between 19th and 23rd magnitude and populated a red giant branch between 20th and 23rd magnitude. Our method was then applied to this model CMD. Measuring the S/N as the ratio of the number of stars on the TRGB to those in the background (ie. unwanted contaminants), the results as the S/N increases can be seen as the solid line in Figure 1. For a S/N greater than approximately one, the measured position of the tip differs from the actual position by, at most, $`0^m.02`$. This nicely shows that the method is able to identify and fit the region of the TRGB to a high accuracy.

We ran a second set of tests which also included a large population of 1000 AGB stars randomly distributed between $`19^m.5`$ and $`20^m.5`$, which will act to mask the tip (dashed line in Figure 1). The behaviour of convergence with increasing S/N remains virtually unaltered for $`\mathrm{S}/\mathrm{N}>1`$ even with a significant AGB population.

A third set of tests were conducted on the M33 data. In Section 3.2 we calculate that the TRGB for this galaxy lies at $`20^m.54`$ (uncorrected for reddening), based upon some 20000 stars contributing to the LPD. Figure 2 shows how our measured value of the TRGB varies as we continually reduce this number. It is evident that although the number of stars we use changes by 2 orders of magnitude, the peak-to-peak variation in the measured value of the tip is only $`0^m.12`$, decreasing to $`0^m.05`$ when more than 2000 stars are considered. This demonstrates the stability of our technique over a very large range in star counts. There is also evidence of a trend such that, as we go to larger numbers, the measured location of the tip tends to brighter magnitudes. This is not to be unexpected since the larger sample of stars will ensure that the brightest RGB stars lie closer to the true tip location. This fact, and the decreasing scatter in the measured values as we go to larger numbers, shows that large number statistics are desirable for such a study.

### 2.3 Relative Increases (Heuristic)

Finally, we have developed a second, much simpler, method to estimate the location of the TRGB. This involves monitoring the relative increase in star counts between neighbouring bins in the foreground-corrected RGB luminosity function once the counts have exceeded a threshold level. Since we are only comparing neighbouring bins, then noise effects will affect us to a significant degree. To combat this, we (non-recursively) average each bin with its two immediate neighbours. The output should show a peak near the location of the TRGB. It is very useful to have such a simple method to provide an independent sanity-check of the results from the data-adaptive least-squares technique.

## 3 Distance Determinations to Some Local Group Members

### 3.1 Data

The Wide Field Camera on the 2.5m Isaac Newton Telescope consists of a four-chip EEV 4K x 2K CCD mosaic camera that images $``$ 0.29 deg2 per exposure (Walton et al. 2001). Over the past 3 years we have been using this to conduct a survey of the halo and outer disk of our nearest neighbour M31. This survey now extends out to over 55 kpc in projection from the centre of this galaxy. In 2002, we extended this project to include M33 which has now been mapped out to a radius of $`20`$ kpc. Even the early results of these surveys were startling, with the halo of M31 showing significant and unexpected substructure; the most spectacular of these being a massive tidal stream stretching out as far as we have surveyed (Ibata et al. 2001, Ferguson et al. 2002, McConnachie et al. 2003). As part of the M31 and M33 surveys we also took fields covering two of M31’s dwarf spheroidal satellites, And I & II.

Images were taken in the equivalent of Johnson V ($`V^{}`$) and Gunn i ($`i^{}`$) bands. For both surveys, most of the data was taken in photometric conditions. The few non-photometric nights were calibrated using overlapping fields and the whole system was placed on a consistent scale using all of the field overlaps. The data for And I & II were deliberately acquired under photometric conditions. Exposure times of 800 - 1000 s per passband allowed us to reach $`i^{}=23^m.5`$ and $`V^{}=24^m.5`$ (S/N $``$ 5), and is sufficient to detect individual RGB stars to $`M_V^{}0^m`$ and main-sequence stars to $`M_V^{}1^m`$ at the distance of M31. Several fields taken in poorer conditions were reobserved and co-added as necessary to give an approximately uniform overall survey depth. For this paper, we have converted our data to the Johnson-Cousins system. The transformations employed are $`\mathrm{I}=i^{}0.101\times (\mathrm{V}\mathrm{I})`$ and $`\mathrm{V}=V^{}+0.005\times (\mathrm{V}\mathrm{I})`$ and have been derived by comparison with observations of several Landolt standard fields 111http://www.ast.cam.ac.uk/$``$wfcsur/colours.php.

All the on-target data plus calibration frames were processed using the standard INT Wide Field Survey (WFS) pipeline supplied by the Cambridge Astronomical Survey Unit (Irwin & Lewis 2001), which provides all the usual facilities for instrumental signature removal and astrometric and photometric calibration. Internal cross-calibration of the four CCDs is achieved at a level better than 1% for each pointing. The overall derived photometric zero points for the entire survey are good to the level of $`\pm 2\%`$ in both bands. Object classification uses the observed morphological structure on the CCDs but is vulnerable at faint magnitudes to distant compact galaxies, which may be misclassified as stars. However, this does not seriously affect us here as we are generally dealing only with stars near the TRGB. For the purposes of this analysis, we concern ourselves only with those objects classified as stellar in both the $`V^{}`$ and $`i^{}`$ passbands.

As already discussed, the Galactic foreground stellar population should be subtracted from the data to minimise contaminants. In order to compensate for this population, we use a number of outer halo fields from our M31 survey for both M33 (where there is no suitable local reference field we can use) and And I (which is sufficiently close to M31 for the foregrounds to similar). Although there is a low level M31 halo population in these reference fields, the dominant population is galactic foreground stars, thus making them suitable as reference fields and allowing a statistical correction to be applied. The computed scaling using the brighter part of the CMDs compensates not only for the difference in area but also to first order the Galactic population gradient. For And II, we are able to apply a local foreground correction (see Section 3.5). In this study we typically find that the foreground contamination in the region of the TRGB is $`15`$ stars/sq.deg/mag for the selection criteria that we apply.

### 3.2 The Adopted Absolute I Magnitude of the TRGB

In order to calculate distances to these galaxies, we must adopt a value for the I-band absolute magnitude of the TRGB. We use the most recent observational determination of this position, given by Bellazzini et al. (2001). These authors studied the galactic globular cluster $`\omega `$ Centauri using a very large photometic database and an independently derived distance estimate to this system which used a detached eclipsing binary star. They derive a value of $`4^m.04\pm 0^m.12`$ for the I-band magnitude of the TRGB at a metallicity of $`[\mathrm{Fe}/\mathrm{H}]1.7`$ dex, which agrees extremely well with theoretically-derived estimates of this point. Although there is a small variation of this magnitude with metallicity, it is significantly less than the quoted uncertainty for the range of metallicities that we will be considering, given the stellar systems we are analysing. As such, we adopt the value as constant. It is important to note that the uncertainty on this value as it stands would be the single biggest contributor to the uncertainties in our final derived distances, and is approximately 4 times bigger than our systematic errors. This degree of uncertainty is somewhat conservative, and the error quoted is primarily due to the uncertainty in the true distance modulus of $`\omega `$ Cen, which is of order $`0^m.1`$. We therefore adopt $`M_{TRGB}=4^m.04\pm 0^m.05`$, and note that although it is possible that the scale may be shifted by up to $`0^m.1`$, this will affect all of our measurements in the same way. The relative distances, to say M31, will essentially remain unchanged.

### 3.3 M33

The RGB distribution from the central pointings of our survey of M33 (Ferguson et al. 2004, in preparation), located at 1h 33m 50.9s, 30 39’ 35.8”, is shown in Figure 3 for all stars brighter than $`\mathrm{I}=22^m.5`$ in the strip indicated in Figure 5. The orientations of M33’s axes are indicated, as is an elliptical annulus around the edge of the disk, selected so as to avoid the effects of crowding in the inner region while still sampling stars across the entirety of M33’s disk. The inner ellipse has a semi-major axis $`a=0^{}.5`$, while the outer ellipse has $`a=0^{}.8`$. To provide a check that our resulting RGB luminosity function does not suffer heavily from blending effects, we have compared the RGB luminosity functions for elliptical annuli at different galactocentric radius. The results are shown in Figure 4 and are all foreground-corrected. The outer annulus samples a region of M33 where we expect negligible crowding, while the innermost annulus might be expected to sample many blended stars. Indeed, the innermost RGB luminosity function is seen to extend to brighter magnitudes than the outermost RGB luminosity function suggesting that blending may be affecting the inner fields to some extent. In this respect, the middle annulus results in a RGB luminosity function whose overall shape is very similar to the outermost RGB luminosity function, given that the outer RGB luminosity function samples fewer stars and is necessarily more noisy. In fact, the location of the TRGB for the outer annulus is at $`20^m.56\pm 0^m.02`$, which compares very well with our final derived value of $`20^m.54\pm 0^m.01`$. This implies that the effect of crowding on our M33 data is negligible for $`a>0^{}.5`$.

The CMD of the stars we analyse to measure the TRGB are shown in Figure 5. It is obvious from the width of the RGB that M33 contains a larger spread in age/metallicity than the Andromeda dwarfs (Figure 8), and the region of the tip lacks a definite edge with many bright AGB stars visible in that region. This is illustrated in the RGB luminosity function (Figure 6) where we see that the tip of the luminosity function delimits a change in slope rather than an edge, and the AGB stars are also visible here for $`\mathrm{I}<20^m.6`$. A weak blue plume representative of a younger stellar population is also evident in the CMD at $`\mathrm{V}\mathrm{I}0`$.

A least-squares fit to the RGB LPD gives a TRGB of $`\mathrm{I}=20^m.54\pm 0^m.01`$. The uncertainty in this measurement is given by the $`1\sigma `$ contour in the $`\tau s`$ plane (see Figure 7). This contour plot was constructed assuming a constant error term in the LPD (Section 2.2). To provide a check of this approximation, we also conduct a similar $`\chi ^2`$ fit to the binned luminosity fuction, where we know the errors to be well described by a Poisson distribution. The expressions for $`a`$ and $`k`$ given by Equations 3 and 4 become necessarily more complex, but the contour levels remain nearly unchanged.

From the extinction maps of Schlegel et al. (1998), the interstellar reddening $`\mathrm{E}(\mathrm{B}\mathrm{V})`$ is found to be $`0^m.042`$, and they state that these values are accurate to within 16%. Using the relation between reddening and extinction in the Landolt system (Landolt 1992), given in the same paper, $`A_I=1.94E\left(BV\right)`$, implies that $`A_I=0^m.081`$. We take the absolute I magnitude of the TRGB to be $`M_{TRGB}=4^m.04\pm 0^m.05`$ as discussed in Section 3.2.. The other uncertainty that we take into account are the mean systematic photometric error in our measurements, which is of order $`0^m.02`$. Blending has already been shown to have a negligible effect on our measurement of the TRGB. Combining the observational errors lead to an overall error of $`0^m.03`$ \- $`0^m.04`$ in the measured value of the TRGB magnitude. We calculate the distance, $`D`$, to the galaxy from $`IM_{TRGB}=5\mathrm{log}_{10}D5+A_I`$ and conclude that overall, $`D_{M33}=794\pm 23`$ kpc. Application of the heuristic method identifies a tip at $`20^m.6`$, in good agreement with the more detailed treatment.

This result brings the TRGB distance to M33 into excellent agreement with the Cepheid distances (see Table 1). The suggestion of a significant amount of reddening in M33 by Kim et al (2002), to explain the discrepancy between their TRGB measurements and their Cepheid measurements (Lee et al. 2002), seems unlikely. We attribute the difference in our results to the fact that we have better statistics than was possible to achieve with their smaller HST fields - we do not see evidence for a significant jump at $`20^m.9`$, as these authors do (see their Figure 4). Of the 10 fields that they analyse, several of the luminosity functions do show evidence for a discontinuity in the slope at $`20^m.520^m.6`$, which may well be associated with the discontinuity that we attribute as the TRGB in our luminosity function. Since our algorithm defines the location of the TRGB somewhat differently to an edge detection algorithm, then this location is highlighted in preference to any absolute change in counts. Additionally, it is unlikely that we have instead measured a feature due to AGB contamination - an AGB population is clearly observed in the CMD and RGB luminosity function for this galaxy (Figures 5 and 6) and so there would have to be a second AGB population in the CMD exactly coincident with the top of the RGB, although this seems unlikely. We would also expect that, if this was the case, their effect would be lessened in a luminosity function located at larger galactocentric distance. Inspection of Figure 4 shows that this is not the case for these stars, even though the contribution from the known AGB component can be seen to reduce in the expected way.

Kim et al. has also calculate the distance to M33 using the red clump (RC), finding agreement with their TRGB measurement. This feature represents stars with a helium core and a hydrogen shell passing through a relatively slow phase of their luminosity evolution, leading to a clump appearing in the CMD. They have recently been suggested for use as a distance indicator by Paczynski & Stanek (1998). They compared the I-band magnitude of OGLE RC stars seen through Baade’s Window with a sample from the Hipparcos catalogue with parallaxes known to $`10\%`$, allowing the absolute I magnitude of the RC ($`M_I^{RC}`$), and hence a distance, to be calculated for the stars seen towards the Galactic Centre. The reliability of this method when applied to other stellar systems relies on the similarity of the Hipparcos sample with the RC stars in the system of interest, and remains a controversial point due to possible dependecies of $`M_I^{RC}`$ on the properties of the population. Theoretical models seem to predict a relatively strong dependency of $`M_I^{RC}`$ with age and metallicity (eg. Cole 1998; Girardi et al. 1998; Girardi 2000; Girardi & Salaris 2001) while observational studies are in apparent disagreement with each other (eg. Udalski 1998; Sarajedini 1999). However, both observation and theory show that $`M_I^{RC}`$ is significantly fainter for stars with ages $`>10`$ Gyrs than for their intermediate age counterparts (Udalski 1998, Girardi & Salaris 2001). Kim et al (2002) assume that the majority of the stellar population in M33 is old ($`>10`$ Gyrs) in order to associate the mean metallicity of the RGB with the metallicity of the RC. This metallicity is then used to calculate $`M_I^{RC}`$ using the calibrations for $`M_I^{RC}`$ vs $`[Fe/H]`$ by Udalski (1998) and Popowski (2000). However, it is not clear that these calibrations are valid for M33 given the assumption about the age of the bulk of the stellar population. If $`M_I^{RC}`$ is significantly fainter in this galaxy due to age then M33 will be correspondingly closer than these authors calculated.

### 3.4 And I

The dwarf spheroidal galaxy And I was discovered by van den Bergh (1971) and lies at 0h 45m 39.8s, 38 2’ 28”. It is a satellite galaxy of M31 at a projected distance of $`40`$ kpc. Mould & Kristian (1990) were the first to study its RGB using CCD images taken at the prime focus of the Hale telescope. Using an eyeball determination of the TRGB they found it to be at a distance of $`790\pm 60`$ kpc. They also concluded the galaxy to be of intermediate metallicity. Da Costa et al. (1996) obtained HST WFPC2 images of this system and by comparison with the giant branches of several globular clusters confirmed the metallicity to be $`<[Fe/H]>=1.45\pm 0.2`$ dex. By analysing the morphology of the horizontal branch they also came to the conclusion that the majority of the population is approximately 10 Gyrs old, However, the presence of a blue horizontal branch and RR Lyrae stars shows that there is a minority population at least 3 Gyrs older than this. And I, like many other dwarf spheroidals, appears to have undergone an extended period of star formation.

The colour magnitude diagram for And I is shown in the left panel of Figure 8. The upper few magnitudes of the RGB are clearly observed and even by visual inspection we can determine that the tip is at $`I20^m.45`$. One interesting point of note is the additional red feature ($`\mathrm{V}\mathrm{I}>2`$) that is not present in the And II CMD (right panel). This is due to the giant stellar stream first discovered by our survey of the outer regions of M31, which is sufficiently broad that part of it lies along the line-of-sight to And I.

Application of the least-squares method identifies the TRGB to be at $`I=20^m.40_{0^m.02}^{+0^m.03}`$, as shown in Figure 9. Schlegel et al. (1998) gives $`E(BV)=0^m.056`$ for the interstellar reddening, and so we derive $`D_{AndI}=735\pm 23`$ kpc, closer than had previously been determined (Table 2) but still in reasonable agreement. Application of the heuristic method identifies the tip to lie at $`20^m.45`$ (Figure 9), in excellent agreement with the adaptive slope, not unexpected for such a clean LPD.

### 3.5 And II

And II is another dwarf spheroidal satellite of M31 discovered at the same time as And I. It lies at 1h 16m 29.8s, 33 25’ 9”, approximately 140 kpc in projection from M31, towards M33. Despite the fact that it lies significantly closer to M33 in projection, the larger mass of M31 means that it is most likely a satellite of M31. Da Costa et al. (2000) derive a mean metallicity of $`<[Fe/H]>=1.49\pm 0.11`$ dex with a significantly larger abundance spread than in And I. An old ($`10`$ Gyrs) population is again implied from the presence of a blue horizontal branch. The presence of young or intermediate populations in this galaxy remains a possibility from their study, but we detect no sign of such a population to $`M_V0^m`$.

The colour magnitude diagram for And II (right panel of Figure 8) again shows the upper parts of the RGB very clearly, with a tip visible at $`I20^m.1`$. We construct the luminosity function for And II by using stars withing $`0.1^{}`$ from its centre. This then allows us to apply a local foreground correction to the luminosity function by using as a reference population all stars on the same INT field outside of this radius, scaled in the usual way. The result is shown in Figure 10, where an unambiguos tip can be observed. We find the TRGB to lie at $`20^m.13\pm 0^m.02`$ ($`20^m.15`$ using the heuristic technique). From Schlegel et al. (1998), $`E(BV)=0^m.063`$. This corresponds to $`D_{AndII}=645\pm 19`$ kpc, in reasonable agreement with estimates that have been made using other methods (Table 3).

## 4 Summary

In this paper we have introduced a new quantitative method for the determination of distances to metal poor stellar systems using the TRGB as a standard candle, accurate to typically $`\pm 0^m.02`$ rms, $`\pm 0^m.03`$ systematic. The method involves a least-squares fit of a data-adaptive slope template to the foreground-corrected RGB LPD in $`1^m`$ windows, to find the region of the LPD that is best fit as a simple slope function ie. the region that shows the most significant change in slope as we go to brighter magnitudes. This determines the apparent magnitude of the TRGB, as represented in the luminosity function. Observations and stellar evolutionary codes agree that this magnitude is virtually constant for old, metal poor populations and so the photometric parallax can easily be calculated.

We believe that our method provides significant improvements over previous attempts to locate the TRGB in a luminosity function. By only considering stars along a strip in the CMD, we minimise contamination from other stellar populations. Further, for systems with broader red giant branches we ensure our sample of RGB stars all have similar age/metallicity rather than analysing all the stars in the RGB. Poisson noise will affect us to a much smaller degree than previous methods since we consider a range in magnitude when determining the position of the tip, rather than just comparing neighbouring star counts. Tests of our method on both synthetic and real data demonstrate the robustness of this method, even with relatively poor S/N. Perhaps most importantly, we demonstrate that accurate TRGB determinations require the use of Wide Field Cameras, such as that on the INT, in order to boost star counts and allow the measured RGB to be as accurate and complete a representation of the population as possible.

The methodology that we develop in this paper is applied to three galaxies - And I & II, and M33. We derive distances to these objects of $`735\pm 23`$ kpc, $`645\pm 19`$ kpc and $`794\pm 23`$ kpc respectively (see Tables 1, 2 and 3 for comparison with previous results). The contribution to this uncertainty due to the algorithm is only of order $`15`$ kpc, demonstrating a significant improvement over other previous techniques that have been used. What is perhaps of greatest importance when comparing this algorithm with, for example, the edge detection alogorithm of Sakai et al. (1996) or the maximum likelihood method of Mendez et al. (2002), is that it uses a different set of criteria to define the location of the tip. In the majority of situations, where the tip position is marked by a significant jump in star counts, the methods will be expected to give the same result. In other situations (such as a gradual increase in star-counts at the TRGB edge, nicely demonstrated in M33) we would not necessarily expect the algorithms to agree as they search for fundamentaly different features in the luminosity function. In the second paper in this series (McConnachie et al. 2004) we apply our algorithm to 11 other Local Group galaxies - And III, And V, And VI, And VII, NGC185, NGC 147, Pegasus, WLM, LGS3, Cetus and Aquarius - to create a homogeneous set of distances to nearby galaxies, a majority of which are members of the M31 subgroup.

## Acknowledgments

Many thanks to the referee, Barry Madore, for a careful reading of this manuscript and useful comments. Additionally, we would like to thank Minsun Kim and collaborators for supplying us with their M33 HST/WFPC2 data, and Eline Tolstoy for her opinion on some of the arguments presented in this paper. The research of AMNF has been supported by a Marie Curie Fellowship of the European Community under contract number HPMF-CT-2002-01758.