text:
# Fluctuations in the Radio Background from Intergalactic Synchrotron Emission

## 1 Introduction

More than a third of all X-ray clusters with luminosities $`10^{45}\mathrm{erg}\mathrm{s}^1`$ possess diffuse radio halos (Giovannini, Tordi, & Feretti 1999). Based on energy arguments and circumstantial evidence, these radio halos are believed to be caused by synchrotron emission from shock-accelerated electrons during the merger events of their host clusters (Harris et al. 1980; Tribble 1993; Feretti 2000; see Liang et al. 2000 for references to alternative, less successful models). These highly-relativistic electrons cool primarily through inverse-Compton scattering off the microwave background. Since their cooling time is much shorter than the dynamical time of their host cluster, the radio emission is expected to last as long as the shock persists and continues to accelerate fresh electrons to relativistic energies. Intergalactic shocks also occur along the filaments and sheets that channel mass into the clusters. These structures, also traced by the galaxy distribution (e.g. Doroshkevich et al. 1996), are induced by gravity and form due to converging large-scale flows in the intergalactic medium.

In a previous paper (Loeb & Waxman 2000), we have shown that most of the diffuse $`\gamma `$–ray background (Sreekumar et al. 1998) might have been generated by the shocks resulting from the formation of large-scale structure in the intergalactic medium. These shocks produce a population of highly-relativistic electrons with a maximum Lorentz factor $`10^7`$ that scatter a small fraction of the microwave background photons in the present-day universe up to $`\gamma `$-ray energies, thereby providing the $`\gamma `$-ray background. The predicted flux agrees with the observed diffuse background over more than four decades in photon energy, provided that the fraction of shock energy carried by relativistic electrons is $`\xi _e0.05`$ (a value consistent with that inferred for supernovae shocks). The brightest shocks are caused by the accretion onto (or mergers of) X-ray clusters. The same electrons that emit $`\gamma `$-rays by inverse-Compton scattering of microwave background photons, also produce synchrotron radiation in the radio band due to intergalactic magnetic fields. The existence of magnetic fields with an amplitude $`0.1\mu `$G, is inferred in cluster halos (Kim et al. 1989; Fusco-Femiano et al. 1999; Rephaeli et al. 1999; Kaastra et al. 1999), and is also required for the Fermi acceleration of these electrons. The appearance of radio halos around young X-ray clusters is therefore a natural consequence and an important test of our model for the extragalactic $`\gamma `$-ray background. The combination of radio and $`\gamma `$-ray data can be used to calibrate $`\xi _e`$ and determine the strength of the intergalactic magnetic field.

The intergalactic synchrotron emission contaminates the microwave background anisotropies – relic from the epoch of recombination, and as such needs to be considered in the design and analysis of anisotropy experiments at low frequencies. Previous estimates of synchrotron contamination of the cosmic anisotropies focused on Galactic emission, which occurs primarily at low Galactic latitudes and large angular scales (Tegmark et al. 2000). In this Letter, we calculate the intergalactic synchrotron contribution to the fluctuations in the radio sky as a function of frequency and angular scale. We assume that most of the emission originates from the virialization shocks around X-ray clusters, and use the Press-Schechter mass function to describe the abundance of such clusters as a function of redshift. Our simplified analytic calculation should be regarded only as a first estimate of the synchrotron fluctuations and could be refined with future numerical simulations (Keshet et al. 2000). Throughout the paper we adopt the popular set of cosmological parameters (Ostriker & Steinhardt 1995) with $`\mathrm{\Omega }_M=0.3`$, $`\mathrm{\Omega }_\mathrm{\Lambda }=0.65`$, $`\mathrm{\Omega }_b=0.05`$, $`h=0.7`$, $`\sigma _8=0.9`$, and $`n=1`$. In §2 we describe the method of the calculation. In §3 we discuss the results and their main implications. Finally, we summarize our conclusions in §4.

## 2 Method of Calculation

### 2.1 Emission from a Single Halo

Let us first consider the luminosity produced by inverse-Compton and synchrotron emission of electrons accelerated to high energies in the accretion shock around a halo of mass $`M`$ at a redshift $`z`$. Assuming that the shock is strong (i.e. the gas is not pre-heated), the population of shock-accelerated electrons acquires a number versus energy distribution with a power law index, $`pd\mathrm{ln}N_e/d\mathrm{ln}E=2`$ (Bell (1978); Blandford & Ostriker (1978)). The inverse-Compton luminosity is then given by

$$\nu L_\nu ^{\mathrm{IC}}=\frac{1}{2\mathrm{ln}(\gamma _{\mathrm{max}})}\frac{\mathrm{\Omega }_b}{\mathrm{\Omega }_m}\frac{\dot{M}(M,z)}{\mu m_p}\xi _e\frac{3}{2}kT(M,z),$$
(1)
where $`\mathrm{\Omega }_m=\mathrm{\Omega }_M+\mathrm{\Omega }_b`$, $`\mu m_p`$ is the average particle mass in the gas including electrons ($`\mu =0.65`$), $`T`$ is the post shock temperature, $`\gamma _{\mathrm{max}}10^7`$ is the maximum Lorentz factor of the accelerated electrons (Loeb & Waxman 2000), $`\dot{M}`$ is the mass accretion rate across the virialization shock, and $`\xi _e`$ is the fraction of thermal shock energy carried by relativistic electrons. The synchrotron luminosity is then given by

$$\nu L_\nu ^{\mathrm{syn}}=\frac{u_B(M,z)}{u_{\mathrm{CMB}}}\nu L_\nu ^{\mathrm{IC}},$$
(2)
where $`u_B`$ and $`u_{\mathrm{CMB}}`$ are the energy densities of the post shock magnetic-field and the cosmic microwave backround (CMB), respectively.

The velocity dispersion, $`\sigma `$, of a halo can be related to its mass through the relation

$$M=\frac{\sqrt{2}}{5}\frac{\sigma ^3(M,z)}{GH(z)},$$
(3)
where

$$H=H_0a^{3/2}g(a)$$
(4)
is the Hubble parameter, with $`a(1+z)^1`$ and $`g(a)=[\mathrm{\Omega }_m+\mathrm{\Omega }_\mathrm{\Lambda }a^3+(1\mathrm{\Omega }_m\mathrm{\Omega }_\mathrm{\Lambda })a]^{1/2}`$. The numerical constant was chosen so that, for an isothermal sphere of velocity-dispersion $`\sigma `$, the quantity $`M`$ is the mass enclosed within a sphere of average density $`\overline{\rho }=200\rho _c`$, where $`\rho _c=3H^2/8\pi G`$ is the critical density at the corresponding redshift. On dimensional grounds, the ensemble-averaged mass accretion rate onto a halo of velocity dispersion $`\sigma `$ can be written as (White 1994)

$$\dot{M}(M,z)=f_{\mathrm{acc}}\frac{\sigma ^3(M,z)}{G},$$
(5)
while the shock temperature and radius are given by

$$kT(M,z)=f_T\mu m_p\sigma ^2(M,z),$$
(6)
$$r_{\mathrm{sh}}(M,z)=f_{\mathrm{sh}}\frac{\sqrt{2}}{5}\frac{\sigma (M,z)}{H(z)}.$$
(7)
The factors $`f_T`$, $`f_{\mathrm{acc}}`$ and $`f_{\mathrm{sh}}`$ are dimensionless numbers of order unity, which depend only weakly on the background cosmology for the relevant range of $`0.3\mathrm{\Omega }_m<1`$, and should be calibrated based on numerical simulations (see, e.g. Miniati et al. 2000). We have chosen the normalization in equation (7) so that for an isothermal sphere density distribution, the post shock density is $`\rho _{\mathrm{sh}}=50\rho _c/3`$, similar to the result for the self-similar accretion solution in an Einstein de-Sitter ($`\mathrm{\Omega }_m=1`$) cosmology (Bertschinger 1985). Note, that in this case the mass enclosed within $`r<r_{\mathrm{sh}}`$ is $`2M`$.

We assume that the magnetic field energy density is a fixed fraction of the post-shock energy density,

$$u_B(M,z)=\xi _B\frac{3}{2}kT(M,z)\frac{\mathrm{\Omega }_b}{\mathrm{\Omega }_m}\frac{\sigma ^2}{2\pi Gr_{\mathrm{sh}}^2\mu m_p}.$$
(8)
With the above definitions, we find

$$B(M,z)=0.14\left[\left(\frac{7\mathrm{\Omega }_b}{\mathrm{\Omega }_m}\right)\left(\frac{\xi _B}{0.01}\right)f_T\right]^{1/2}f_{\mathrm{sh}}^1h_{70}^{4/3}a^2[g(a)]^{4/3}M_{14}^{1/3}\mu \mathrm{G},$$
(9)
where $`H_0=70h_{70}\mathrm{km}\mathrm{s}^1\mathrm{Mpc}^1`$, $`M=10^{14}M_{14}M_{}`$. Thus, for values of $`\xi _B0.01`$ well below unity, we obtain a magnetic field amplitude consistent with observations (Kim et al. 1989; Fusco-Femiano et al. 1999; Rephaeli et al. 1999; Kaastra et al. 1999) and with our model for the $`\gamma `$-ray background (Loeb & Waxmann 2000). The implied synchrotron luminosity is

$$\nu L_\nu ^{\mathrm{syn}}=5.1\times 10^{38}f_{\mathrm{acc}}f_T^{3/2}f_{\mathrm{sh}}^2\left(\frac{7\mathrm{\Omega }_b}{\mathrm{\Omega }_m}\right)^2\left(\frac{\xi _B}{0.01}\right)\left(\frac{\xi _e}{0.05}\right)h_{70}^2a[g(a)]^2T_{\mathrm{keV}}^{7/2}\mathrm{erg}\mathrm{s}^1,$$
(10)
which can be related to the cluster mass through equation (6),

$$M_{14}=0.54f_T^{3/2}h_{70}^1a^{3/2}[g(a)]^1T_{\mathrm{keV}}^{3/2},$$
(11)
where $`T_{\mathrm{keV}}=(kT/1\mathrm{k}\mathrm{e}\mathrm{V})`$. While $`\gamma `$-ray observations can be used to calibrate $`\xi _e0.05`$ (Loeb & Waxman 2000), radio synchrotron observations of clusters calibrate $`\xi _B`$. The synchrotron luminosity predicted by equation (10) is consistent with the values observed for the brightest radio halos of unrelaxed X-ray clusters for $`\xi _B0.01`$ (see the upper envelope in Fig. 9 of Liang et al. 2000, obtained for $`h=0.5`$ and $`z0.3`$). Similarly to observations, our model predicts a radio luminosity which increases with cluster temperature and a nearly flat radio spectrum (see Fig. 6 in Liang et al. 2000).

The above expressions apply only to clusters which possess a strong shock with a Mach number $`\mathrm{{\rm Y}}1`$. Non-accreting clusters or low-mass clusters which accrete gas that was already pre-heated close to their virial temperature (e.g., due to prior collapse of their environment or because of supernova energy injection), will not show significant non-thermal emission. For a shock front moving at a moderate Mach number, the accelerated electrons acquire a number-energy distribution with a power-law index $`p=(r+2)/(r1)`$, where $`r=8\mathrm{{\rm Y}}^2/(6+2\mathrm{{\rm Y}}^2)`$ is the shock compression ratio for a gas with an adiabatic index $`\gamma =5/3`$. This in turn yields steep non-thermal spectra with $`\nu L_\nu ^{\mathrm{IC},\mathrm{syn}}\nu ^{[2/(\mathrm{{\rm Y}}^21)]}`$; implying that for weak shocks with $`\mathrm{{\rm Y}}2`$, most of the non-thermal emission is at undetectable low frequencies.

### 2.2 Background Flux and Anisotropy

The observed intensity at Earth of inverse-Compton and synchrotron emission is given by integrating (1) and (2) over halo mass and cosmic time, $`t`$. Thus,

$$\nu I_\nu ^{\mathrm{IC},\mathrm{syn}}=dz\frac{c\mathrm{d}t}{\mathrm{d}z}dM\frac{\mathrm{d}n}{\mathrm{d}M}\frac{\nu L_\nu ^{\mathrm{IC},\mathrm{syn}}(M,z)}{4\pi (1+z)^4},$$
(12)
where angular brackets denote sky average and $`\mathrm{d}n/\mathrm{d}M`$ is the differential number density of halos per physical volume as a function of their mass. Using the Press-Schechter (1974) mass function, we find for the cosmological parameters we have chosen, $`\nu I_\nu ^{\mathrm{IC}}=1.5f_{\mathrm{acc}}f_T(\xi _e/0.05)\mathrm{keV}\mathrm{cm}^2\mathrm{s}^1\mathrm{sr}^1`$. Thus, our model reproduces the $`\gamma `$-ray background intensity for a reasonable choice of parameters, namely $`f_{\mathrm{acc}}f_T(\xi _e/0.05)1`$ (Loeb & Waxman 2000). Given the calibration of the $`\gamma `$-ray background we predict a radio background with

$$\nu I_\nu ^{\mathrm{syn}}=5.0\times 10^{12}f_{\mathrm{acc}}\left(\frac{f_T}{f_{\mathrm{sh}}}\right)^2\left(\frac{\xi _e}{0.05}\right)\left(\frac{\xi _B}{0.01}\right)\mathrm{erg}\mathrm{cm}^2\mathrm{s}^1\mathrm{sr}^1.$$
(13)
We find that 90$`\%`$ (50$`\%`$) of the contribution to this background comes from massive clusters with $`M>10^{14}M_{}`$ ($`M>5\times 10^{14}M_{}`$), which are less sensitive to pre-heating of the accreting gas and for which the strong shock assumption is likely to apply.

The intensity fluctuations can be calculated from

$`\delta ^2I(\theta )`$ $`I_\nu (0)I_\nu (\theta )I_\nu ^2`$ (14)
$`=`$ $`{\displaystyle dz\frac{c\mathrm{d}t}{\mathrm{d}z}dM\frac{\mathrm{d}n}{\mathrm{d}M}\frac{\left[\nu L_\nu (M,z)\right]^2}{16\pi ^3(1+z)^8r_{\mathrm{sh}}^2(M,z)}P_{1,2}\left[\frac{\theta d_A(z)}{r_{\mathrm{sh}}(M,z)}\right]}.`$ (15)
Here, $`I_\nu (0)I_\nu (\theta )`$ is the sky average of the product of intensities along two lines of sight, 1 and 2, separated by an angle $`\theta `$, $`d_A`$ is the angular diameter distance, and $`P_{1,2}`$ is the probability that line-of-sight 2 passes through a halo of radius $`r_{\mathrm{sh}}`$ given that line-of-sight 1 passes through the same halo,

$$P_{1,2}(x)=\frac{2}{\pi }_0^\pi d\varphi _0^1dyy\times \{\begin{array}{cc}1,\hfill & \text{for }(y+x\mathrm{cos}\varphi )^2+x^2\mathrm{sin}^2\varphi <1\text{;}\hfill \\ 0,\hfill & \text{otherwise .}\hfill \end{array}$$
(16)
We have neglected in equation (15) halo-halo correlations, and assumed that the only contribution to the integral is from both lines-of-sights passing through the same halo. This assumption is justified since the optical depth (the average number of halos along a given line of sight) is much smaller than unity for the typical parameter values. In particular, we find that clusters with $`M>5\times 10^{14}M_{}`$ ($`M>10^{15}M_{}`$) cover $`<10\%`$ ($`<2\%`$) of the sky. Note that the fractional fluctuations, $`\delta ^2I/I^2`$ are independent of $`f_T`$, $`f_{\mathrm{acc}}`$, $`\xi _e`$, and $`\xi _B`$, and their dependence on $`f_{\mathrm{sh}}`$ is simply given by $`f_{\mathrm{sh}}^2\delta ^2I(f_{\mathrm{sh}}\theta )/I^2=[\delta ^2I(\theta )/I^2]_{f_{\mathrm{sh}}=1}`$.

## 3 Results

The fluctuations in the radio and $`\gamma `$-ray background intensities, derived from equation (15), are shown in Figure 1. Although the synchrotron background amounts to only a small fraction of the CMB intensity, $`I_\nu ^{\mathrm{syn}}/I_\nu ^{\mathrm{CMB}}=6\times 10^6(f_T/f_{\mathrm{sh}}^2)(\xi _B/0.01)(\nu /10\mathrm{G}\mathrm{H}\mathrm{z})^3`$ for $`f_{\mathrm{acc}}f_T(\xi _e/0.05)=1`$, its fluctuations could dominate over the primordial CMB fluctuations at low photon frequencies, $`\nu 10`$ GHz. Our results imply that radio emission from cluster shocks contributes a fluctuation amplitude between $`30`$ and $`50\mu `$K $`\times (f_T/f_{\mathrm{sh}}^2)(\xi _B/0.01)(\nu /10\mathrm{G}\mathrm{H}\mathrm{z})^3`$ to the CMB on angular scales between 1 and $`0.1^{}`$, respectively. Interestingly, current anisotropy experiments are just sensitive to this level of fluctuations111See table summary of current experiments at http://www.hep.upenn.edu/$``$max/index.html, or at http://cfa-www.harvard.edu/$``$mwhite/cmbexptlist.html. Existing detections by CAT ($`50\pm 15\mu `$K at 15 GHz on 0.2–0.5°scales) and OVRO ($`56_{6.6}^{+8.5}\mu `$K at 20 GHz on 0.1–0.6°scales), as well as 95% upper limits ($`40\mu `$K on arcminute scales at 9-15 GHz by the ATCA, RYLE and VLA detectors) are consistent with our prediction222 Note that although the cluster contribution declines rapidly at high frequencies, some of these experiments, like CAT or OVRO, measured fluctuations at only one frequency and could not reject a synchrotron contribution to the measured signal..

For bright clusters, the flux increment due to synchrotron emission by the non-thermal electrons accelerated in the cluster accretion shock is larger at low frequencies than the Sunyaev-Zeldovich decrement due to the thermal intra-cluster electrons. For a gas density profile of an isothermal sphere,

$$\frac{\mathrm{\Delta }I_\nu ^{\mathrm{syn}}}{\mathrm{\Delta }I_\nu ^{\mathrm{SZ}}}=3.8f_{\mathrm{acc}}f_Tf_{\mathrm{sh}}^3\left(\frac{7\mathrm{\Omega }_b}{\mathrm{\Omega }_m}\right)\left(\frac{\xi _B}{0.01}\right)\left(\frac{\xi _e}{0.05}\right)h_{70}^{11/3}a^{5/2}[g(a)]^{11/3}M_{14}^{2/3}\left(\frac{\theta d_A}{r_{\mathrm{sh}}}\right)\left(\frac{\nu }{10\mathrm{G}\mathrm{H}\mathrm{z}}\right)^3.$$
(17)
In the X-ray regime, the central surface brightness due to thermal bremsstrahlung emission by the intra-cluster gas exceeds by orders of magnitude the inverse-Compton brightness; however, due to the rapid decline of the thermal brightness with projected radius outside the cluster core ($`\theta ^3`$), we find that the non-thermal brightness might dominate around the shock radius.

The cumulative (all sky) number of radio and $`\gamma `$-ray halos as a function of flux or surface-brightness thresholds are shown at the top and bottom panels of Figure 2. We find that $`30`$ $`\gamma `$-ray halos have a flux exceeding the EGRET detection threshold of $`10^{11}\mathrm{erg}\mathrm{cm}^2\mathrm{s}^1`$. Such halos may therefore constitute, as recently pointed out by Totani & Kitayama (2000), a significant fraction of the unidentified extra-Galactic EGRET sources ($`60`$ sources over all sky; see Özel & Thompson 1996). Note, however, that since the angular extension of the brightest halos is large, a careful analysis is required to determine the detectability of such halos by the source search analysis which was applied to the EGRET data.

## 4 Conclusions

The production of a fluctuating synchrotron background by strong intergalactic shocks is a natural consequence of structure formation in the Universe. The brightest emission originates from the virialization shocks on Mpc scales around newly formed, massive X-ray clusters. We estimate that the combined emission from all clusters produces fluctuations in the microwave background temperature of order $`40\mu \mathrm{K}(\xi _B/0.01)(\xi _e/0.05)(\nu /10\mathrm{G}\mathrm{H}\mathrm{z})^3`$ on sub-degree scales (Fig. 1), where $`\xi _B0.01`$ is the value required to explain the brightest radio halos of nearby clusters and $`\xi _e0.05`$ accounts for the $`\gamma `$-ray background. The foreground synchrotron fluctuations might be comparable to the anisotropy signals detected by existing low-frequency CMB experiments, and can be easily isolated through multi-frequency observations. Polarization anisotropy experiments could then constrain the coherence length of the intergalactic magnetic field.

Our model predicts a fluctuation amplitude $`40\%`$ in the $`\gamma `$-ray background intensity on sub-degree scale (Fig. 1), and the existence of extended, $`1\mathrm{°}`$, $`\gamma `$-ray halos, associated with newly formed massive clusters (Fig. 2). On scales larger than a degree the fluctuation amplitude declines and is well below the anisotropy limits from EGRET (see Fig. 5 in Sreekumar et al. 1998), although somewhat higher than expected from an analogy to the X-ray background (Loeb & Waxman 2000). Detection of the predicted signals will provide a calibration of the uncertain model parameter $`\xi _e`$. The high-energy maps required to detect the predicted anisotropy signal will be made between 20 MeV and 300 GeV by the GLAST instrument333See http://glast.gsfc.nasa.gov/ for more details. (planned for launch in 2005), which is expected to be more sensitive than EGRET by an order-of-magnitude (Bloom (1996)). The predicted $`\gamma `$-ray halos may constitute a significant fraction of the unidentified extra-Galactic EGRET sources (see also Totani & Kitayama 2000). However, since the angular extension of the brightest halos is large, a more careful analysis is required to assess the detectability of such halos by EGRET.

A future, dedicated, all-sky anisotropy experiment, operating at several frequencies below 10 GHz, would be able to map the fluctuations in the intergalactic synchrotron background. The resulting synchrotron map could then be cross-correlated with full-sky maps at hard X-ray or $`\gamma `$-ray energies to confirm its cosmic origin. Identification of the synchrotron fluctuations together with their counterpart inverse-Compton emission of hard X-rays or $`\gamma `$-rays by the same population of shock-accelerated electrons, can be used to empirically determine the strength and spatial distribution of the intergalactic magnetic fields. Similarly, the correlation between radio and $`\gamma `$-ray halos may be detectable around individual X-ray clusters. Strong radio halos could be the best indicators for bright $`\gamma `$-ray clusters, which would provide the first obvious targets for GLAST.

For the sake of simplicity, our model associated the intergalactic shocks with smooth spherical accretion of gas onto clusters, while in reality they result from asymmetric mergers as well as from converging flows in large scale sheets and filaments. The more realistic emission from these complex geometries can be best modeled through detailed hydrodynamic simulations (Miniati et al. 2000; Keshet et al. 2000). However, we note that mergers of comparable mass clusters would tend to produce only mild shocks due to the prior heating of the shocked gas, and hence result in negligible non-thermal emission due to the steep power-law slope of the accelerated electrons.

This work was supported in part by grants from the Israel-US BSF (BSF-9800343) and NSF (AST-9900877). EW thanks the Harvard-Smithsonian Center for Astrophysics for its kind hospitality during the course of this work. EW is the incumbent of the Beracha foundation career development chair.


format: text

text:
# Enumerations of lattice animals and trees

## 1 Introduction

The enumeration of lattice animals is a classical combinatorial problem of great interest in it own right . Lattice animals are connected subgraphs of a lattice. A site animal can be viewed as a finite set of lattice sites connected by a network of nearest neighbor bonds. The fundamental problem is the calculation (up to translation) of the number of animals, $`a_n`$, with $`n`$ sites. In the physics literature lattice animals are often called clusters due to their close relationship to percolation problems . Series expansions for various percolation properties, such as the percolation probability or the average cluster size, can be obtained as weighted sums over the number of lattice animals, $`g_{n,m}`$, enumerated according to the number of sites $`n`$ and perimeter $`m`$ . In mathematics, and combinatorics in particular, the term polyominoes is frequently used. A polyomino is a set of lattice cells joined at their edges. So polyominoes are identical to site animals on the dual lattice. Furthermore, the enumeration of lattice animals has traditionally served as a benchmark for computer performance and algorithm design .

Lattice trees form a proper subset of lattice animals, and can be defined as those animals containing no circuits. Another way of defining trees is that a tree is a finite connected set of sites with the property that a walk starting from any given site cannot return to the original site without self-intersections. Lattice trees have been suggested as a model of branched polymers . Lattice animals and trees are expected to belong to the same universality class  and thus have the same critical exponents.

An algorithm for the calculation of $`g_{n,m}`$ has been published by Martin  and Redner . It was used by Sykes and co-workers to calculate series expansions for percolation problems on various lattices. In particular Sykes and Glen  calculated $`g_{n,m}`$ up to $`n=19`$ on the square lattice, and thus obtained the number of lattice animals, $`a_n=_mg_{n,m}`$, to the same order. Redelmeier  presented an improved algorithm for the enumeration of lattice animals and extended the results to $`n=24`$. This algorithm was later used by Mertens  to devise an improved algorithm for the calculation of $`g_{n,m}`$ and a parallel version of the algorithm appeared a few years later . The next major advance was obtained by Conway  who used the finite lattice method with an associated transfer-matrix algorithm to calculate $`a_n`$ and numerous other series up to $`n=25`$ . In unpublished work Oliveira e Silva  used the parallel version of the Redelmeier algorithm  to extend the enumeration to $`n=28`$. In this work we use an improved version of Conway’s algorithm to extend the enumeration to $`n=46`$. We also calculate the number of lattice trees up to $`n=44`$ and the radius of gyration of lattice animals and trees up to $`n=42`$.

The quantities and functions we consider in this paper are: (i) the number of lattice animals $`a_n`$ and the associated generating function, $`𝒜(u)=a_nu^n`$; (ii) the number of lattice trees $`t_n`$ with generating function, $`𝒯(u)=t_nu^n`$; and (iii) the mean-square radius of gyration of animals or trees of size $`n`$, $`R^2_n`$. These quantities are expected to behave as

$`a_n`$ $`=`$ $`A\lambda ^nn^\tau [1+o(1)],`$
$`t_n`$ $`=`$ $`T\lambda _0^nn^\tau [1+o(1)],`$ (1)
$`R^2_n`$ $`=`$ $`Rn^{2\nu }[1+o(1)],`$
where $`\lambda `$ and $`\lambda _0`$ are the reciprocals $`u_c^1`$ of the critical point of, respectively, the animal and tree generating functions. From numerical evidence it is well-established that $`\tau =1`$.

In Section 2 we give a detailed description of the finite lattice method for enumerating lattice animals. Some initial results of the analysis of the series are presented in Section 3.

## 2 Enumerations of lattice animals and trees

The method we use to enumerate site animals and trees on the square lattice is based on the method used by Conway  for the calculation of series expansions for percolation problems, and is similar to methods devised by Enting for enumeration of self-avoiding polygons  or the algorithm used by Derrida and De Seze to study percolation and lattice animals . In the following we give a detailed description of the algorithm used to count lattice animals. We then show how to generalise the method to calculate the radius of gyration and obtain series for lattice trees.

### 2.1 Transfer matrix algorithm

The number of animals that span rectangles of width $`W`$ and length $`L`$ are counted using a transfer matrix algorithm. By combining the results for all $`W\times L`$ rectangles with $`WW_{\mathrm{max}}`$ and $`W+L2W_{\mathrm{max}}+1`$ we can count all animals up to $`n=2W_{\mathrm{max}}`$. Due to symmetry we only consider rectangles with $`LW`$ and thus count the contributions for rectangles with $`L>W`$ twice.

The transfer matrix technique involves drawing a boundary line through the rectangle intersecting a set of $`W`$ sites. For each configuration of occupied or empty sites along the boundary we maintain a generating function for partially completed animals intersecting the boundary in that particular pattern. Animals in a given rectangle are enumerated by moving the boundary so as to add one site at a time, as shown in figure 1. Each configuration can be represented by a set of states $`\{\sigma _i\}`$, where the value of the state $`\sigma _i`$ at position $`i`$ must indicate first of all if the site is occupied or empty. An empty site is simply indicated by $`\sigma _i=0`$. Since we have to ensure that we count only connected graphs more information is required if a site is occupied. In short we need a way of describing which other occupied sites on the boundary it is connected to via a set of occupied sites to the left of the boundary. The most compact encoding of this connectivity is

$$\sigma _i=\{\begin{array}{cc}\hfill 0& \text{empty site},\hfill \\ \hfill 1& \text{occupied site not connected to others on the boundary},\hfill \\ \hfill 2& \text{first among a set of connected boundary sites},\hfill \\ \hfill 3& \text{intermediate among a set of connected boundary sites},\hfill \\ \hfill 4& \text{last among a set of connected boundary sites}.\hfill \end{array}$$
(2)
Configurations are read from the bottom to the top. As an example the configuration along the boundary of the partially completed animal in figure 1 is $`\{102023404\}`$.

In addition to the configuration of states along the boundary line we also have to specify whether or not the partially completed animals include sites on the lower and/or upper borders of the rectangle. This can simply be done by marking a configuration with a 0 if none of the borders have been touched, and a 1, 2 or 3 if, respectively, the lower border, upper border or both borders have been touched. In this way we can be sure to count only those animals which span a given rectangle in the vertical direction. That all animals span the horizontal direction is ensured by the set updating rules detailed below.

The total configuration of occupied sites and the touching of the borders can be encoded by a pair of integers $`(S,k)`$, where $`k`$ indicates which borders have been touched, and $`S`$ is the integer whose binary representation is obtained by assigning 3 bits to each $`\sigma _i`$ in the configuration of occupied sites, $`S=_{i=0}^{W1}\sigma _i8^i`$. We shall call such a $`(S,k)`$-pair a signature, and in practise represent it by an integer $`\widehat{S}=S+k8^W`$. For $`W20`$ a signature can thus conveniently be stored in the computer as a 64-bit integer, while for $`W>20`$ we need to switch to a more complicated representation, say, in terms of several 16-bit integers. Often we shall explicitly write out the configuration $`\{\sigma _i\}`$ instead of $`S`$ and use the notation $`\{S_1S_2\}`$ to indicate a configuration obtained by concatenating the strings $`S_1`$ and $`S_2`$.

The major improvement of the method used to enumerate animals in this paper is that we require animals to span the rectangle in both directions. In the original approach  animals were only required to span in the lengthwise direction and animals of width less than $`W`$ were generated many times. It is however easy to obtain the animals of width exactly $`W`$ and length exactly $`L`$ from this enumeration . The only drawback of the new approach is that for most configurations we have to use four distinct generating functions. The major advantage is that the memory requirement of the algorithm is exponentially smaller.

Realizing the full savings in memory usage comes from two enhancements to the original algorithm. Firstly, for each configuration we keep track of the current minimum number of occupied sites $`N_{\mathrm{cur}}`$ which have been inserted to the left of the intersection in order to build up that particular configuration. Secondly, we calculate the minimum number of additional sites $`N_{\mathrm{add}}`$ required to produce a valid animal. There are three contributions, namely the number of sites required to connect all the separate pieces of the partially completed animal, the number of sites needed to ensure that the animal touches both the lower and upper boundary, and finally the number of sites needed to extend at least $`W`$ columns in the length-wise direction. If the sum $`N_{\mathrm{cur}}+N_{\mathrm{add}}>2W_{\mathrm{max}}`$ we can discard the partial generating function for that configuration because it won’t make a contribution to the animal count up to the size we are trying to obtain. Furthermore, for any $`W`$ we know that contributions will start at $`2W1`$ since the smallest animals have to span a $`W\times W`$ rectangle. So for each configuration we need only retain $`2(W_{\mathrm{max}}W)+1`$ terms of the generating functions. With the original algorithm contributions started at $`W`$ because the animals were required to span only in the length-wise direction.

#### 2.1.1 Derivation of updating rules

In Table I we have listed the possible local ‘input’ states and the ‘output’ states which arise as the kink in the boundary is propagated by one step. The most important boundary site is the ‘lower’ one situated at the bottom of the kink (the site marked with the second ‘2’ in figure 1). This is the position in which the lattice is being extended and obviously the new site can be either empty or occupied. The second most important boundary site is the ‘upper’ one at the top of the kink (the site marked ‘3’ in figure 1). The state of the upper site is very important in determining the state of the lower site when occupied. The state of the upper site is likely to be changed as a result of the move. In addition the state of a site further afield may have to be changed if a branch of a partially completed animal terminates at the new site or if two independent components of a partially completed animal join at the new site. In the following we give the details of how some of these updating rules are derived. We shall refer to the signature before the the move as the ‘source’ and a signature produced as a result of the move as a ‘target’.

00: The lower and upper sites are empty. If the new site is empty the signature is unchanged. If the new site is occupied it isn’t connected to other sites in the boundary and is in state 1. From the source configuration $`\{S_100S_2\}`$ we get the targets $`\{S_100S_2\}`$ and $`\{S_110S_2\}`$.

01: The lower site is empty and the upper site is isolated. If the new site is empty the signature is unchanged. If the new site is occupied it is connected to the upper site and is in state 2 while the state of the upper site is changed to state 4.

02: When the new site is occupied it is connected to the upper site. The state of the lower site becomes 2 (the new first site in the set) while the state of the upper site is changed to 3 (it is now an intermediate site).

10: The lower site was an isolated occupied site so if the new site is empty we have created a separate graph. This is only allowed if there are no other occupied sites on the boundary line (otherwise we generate graphs with separate components) and if both the lower and upper borders have been touched. The result are valid lattice animals. The generating function is accumulated into the final animal generating function. If the new site is occupied it isn’t connected to other sites in the boundary and is therefore still in state 1.

11: The new site has to be occupied and it is connected to the upper site. The new site is in state 2 while the state of the upper site is changed to state 4.

14: This situation never occur. The upper site is the last among a set of occupied sites. This implies that the site immediately to the left of the upper site is occupied, this in turn is connected to the lower site, which therefore cannot be an isolated occupied site.

20: The lower site is the first among a set of occupied sites, so if the new site is empty, another site in this set changes its state. Either the first intermediate site becomes the new first site, and its state is changed from 3 to 2, or, if there are no intermediate sites, the last site becomes an isolated occupied site, and its state is changed from 4 to 1. Note that there could be connected parts of the animal interspersed between the first site and the matching intermediate or last site, so locating the site which has to be changed requires a little computation. This is illustrated in figure 1 where the first 2 is connected to the last 4, and a piece of the animal is placed in between these two sites. In this example if the first 2 became a 0 the last 4 becomes a 1, while if the second 2 becomes a 0 the 3 above it becomes a 2. In general the nesting can be quite complicated and the general rule for updating the configuration is as follows: Start from the 2, which we are changing to a 0, and move upwards in the configuration. Count the number of 2’s and 4’s as we pass them. If an equal number has been passed and we encounter a 3 or 4 this is the matching site we are looking for and it is changed either to 2 or 1. This change of a matching site is indicated in Table I by over-lining. When the new site is occupied the configuration is unchanged. So from the source $`\{S_120S_2\}`$ we get the targets $`\{S_100\overline{S_2}\}`$ and $`\{S_120S_2\}`$.

22: The updating when the new site is empty is as before. When the new site is occupied the connectivity is altered since we are joining two separate pieces of the animal. The new site remains the first site in the joined piece while the upper site becomes an intermediate site. The last site in the set of connected sites starting at the upper site also becomes an intermediate site in the joined piece. Locating this site is similar to the operation indicated by over-lining. However, in this case we ignore sites in state 3 and the matching site in state 4 becomes a 3. We indicate this type of transformation by putting a hat over the string. The source $`\{S_122S_2\}`$ gives rise to the targets $`\{S_102\overline{S_2}\}`$ and $`\{S_123\widehat{S_2}\}`$.

40: When the new site is empty we must change a matching site, either an intermediate site to a last site or a first site to an isolated occupied site. The transformation is similar to the case 20, but we have to search downwards in the configuration.

43: When the new site is occupied we change the connectivity. The first site, from the set of sites connected to the lower site, is changed to an intermediate site. This transformation is similar to the ‘hat’ transformation described at case 22, but we now have to search downwards in the configuration.

44: This can’t happen for the same reason that 14 is impossible.

#### 2.1.2 The algorithm

As a new site is added to the lattice we construct a new set of partial generating functions from the existing set. This can be done by running through all members of the existing set. Using bit-masking we can extract the states of the lower and upper sites and then apply the relevant updating rules, which generate at most 2 target signatures. First we check if the signature already exists, if so the generating functions of the source and target are added (with an addition weight factor $`u`$ on the source if the new site is occupied). If the signature doesn’t exist already, we check whether or not it makes a contribution, that is, we see if $`N_{\mathrm{cur}}+N_{\mathrm{add}}2W_{\mathrm{max}}`$ ($`N_{\mathrm{cur}}`$ of the target is $`N_{\mathrm{cur}}`$ of the source if the new site is empty and $`N_{\mathrm{cur}}+1`$ otherwise). If the target makes a contribution it is assigned a storage position and its generating function is the generating function of the source (again with an extra factor of $`u`$ if the new site is occupied). When the target generating functions have been created the storage position of the source generating function is released since it is no longer required and thus can be recycled.

The algorithm for the enumeration of animals spanning a $`W\times L`$ strip is:

1. Start by inserting an isolated occupied site in the top left corner. This configuration has the signature $`(8^{W1},2)`$, which enters with a count of 1.
2. For $`j`$ from 2 to $`W1`$ add a site to the lattice in the first column. Run through all existing signatures using the updating rules described above (note that as this is the first column the lower site is always empty). Add an additional configuration with a single occupied site at position $`Wj`$ with a count of 1. These configurations have the signature $`(8^{Wj},0)`$, since none of the borders have been touched.
3. Put in the last site in the first column. Again we run through all existing signatures. If the new site occupied we have to mark the signature as having touched the lower border. Add an additional configuration with a single occupied site in the lower left corner with a count of 1, the signature is $`(1,1)`$.
4. Put in the top site in the next column. Run through all existing signatures. Since we are at the top border we only use the updating rules in Table I with the upper site in state 0 (obviously the lower site cannot be in states 2 or 3). If the new site is occupied make sure that the signature is marked as having touched the upper border. In this generic case we do not put in the additional configuration of a single isolated occupied site since it would not touch the left-most border.
5. For $`j`$ from 2 to $`W1`$ add a site to the lattice in row $`Wj`$. Run through all existing signatures using the updating rules. Again no isolated occupied should be inserted.
6. Put in the last site in the column. If the new site is occupied make sure that the signature is marked as having touched the lower border.
7. If the number of completed columns is less than $`L`$ go to 4.

#### 2.1.3 Computational complexity

The algorithm has exponential complexity, that is the time required to obtain the animals up to size $`n`$ grows exponentially with $`n`$. Time and memory requirements are basically proportional to the maximum number of distinct configuration generated during a calculation. This in turn depends on the maximum number of terms we wish to calculate and thus on $`W_{\mathrm{max}}`$. In figure 2 we have shown how the maximal number of configurations, $`N_{\mathrm{Conf}}`$, grows with $`W_{\mathrm{max}}`$. From this it is clear $`N_{\mathrm{Conf}}a^{W_{\mathrm{max}}}`$, and from the figure we estimate that $`a`$ is a little larger than 2. Since we obtain $`2W_{\mathrm{max}}`$ terms the computational complexity grows exponentially with growth constant $`\sqrt{a}`$. Note that this is much better than a direct enumeration in which time requirements are proportional to the number of animals and therefore has the growth constant, $`\lambda 4.06\mathrm{}`$, of lattice animals. The price we have to pay for a faster algorithm is that the memory requirement also grows exponentially like $`N_{\mathrm{Conf}}`$, whereas in direct enumerations the memory requirement typically grows like a polynomial in the number of terms.

#### 2.1.4 Further particulars

Finally a few remarks of a more technical nature. The number of contributing configurations becomes very sparse in the total set of possible states along the boundary line and as is standard in such cases one uses a hash-addressing scheme . Since the integer coefficients occurring in the expansion become very large, the calculation was performed using modular arithmetic . This involves performing the calculation modulo various prime numbers $`p_i`$ and then reconstructing the full integer coefficients at the end. In order to save memory we used primes of the form $`p_i=2^{15}r_i`$ so that the residues of the coefficients in the polynomials could be stored using 16 bit integers. The Chinese remainder theorem ensures that any integer has a unique representation in terms of residues. If the largest integer occurring in the final expansion is $`m`$, then we have to use a number of primes $`k`$ such that $`p_1p_2\mathrm{}p_k>m`$. Up to 6 primes were needed to represent the coefficients correctly.

### 2.2 Calculation of the radius of gyration

In the following we show how the definition of the radius of gyration can be expressed in a form suitable for a transfer matrix calculation. As is well-known the radius of gyration of $`n`$ points at positions $`𝐫_i`$ is

$$n^2R_n^2=\underset{i>j}{}(𝐫_i𝐫_j)^2=(n1)\underset{i}{}(x_i^2+y_i^2)2\underset{i>j}{}(x_ix_j+y_iy_j).$$
(3)
This last expression is suitable for a transfer matrix calculation. As usual we actually calculate the generating function, $`_g^2(u)=_na_nR^2_nn^2u^n`$, since this ensures that the coefficients are integers. In order to do this we have to maintain five partial generating functions for each signature, namely

* $`A(u)`$, the number of (partially completed) animals.
* $`R^2(u)`$, the sum over animals of the squared components of the distance vectors.
* $`X(u)`$, the sum of the $`x`$-component of the distance vectors.
* $`Y(u)`$, the sum of the $`y`$-component of the distance vectors.
* $`XY(u)`$, the sum of the ‘cross’ product of the components of the distance vectors, e.g., $`_{i>j}(x_ix_j+y_iy_j)`$.

As the boundary line is moved to a new position each configuration $`S`$ might be generated from several configurations $`S^{}`$ in the previous boundary position. The partial generation functions are updated as follows

$`A(u,S)`$ $`=`$ $`{\displaystyle \underset{S^{}}{}}u^{n(S^{})}A(u,S^{}),`$
$`R^2(u,S)`$ $`=`$ $`{\displaystyle \underset{S^{}}{}}u^{n(S^{})}[R^2(u,S^{})+n(S^{})(x^2+y^2)A(u,S^{})],`$
$`X(u,S)`$ $`=`$ $`{\displaystyle \underset{S^{}}{}}u^{n(S^{})}[X(u,S^{})+xn(S^{})A(u,S^{})],`$ (4)
$`Y(u,S)`$ $`=`$ $`{\displaystyle \underset{S^{}}{}}u^{n(S^{})}[Y(u,S^{})+yn(S^{})A(u,S^{})],`$
$`XY(u,S)`$ $`=`$ $`{\displaystyle \underset{S^{}}{}}u^{n(S^{})}[XY(u,S^{})+xn(S^{})X(u,S^{})+yn(S^{})Y(u,S^{})]`$
where $`n(S^{})`$ is the number of occupied site added to the animal.

### 2.3 Enumeration of lattice trees

Lattice trees can be enumerated in essentially the same manner as animals. We merely get some further restrictions on the rules listed in Table I. The necessary restriction is that the new site cannot be occupied if the lower and upper sites already are connected, since this would obviously result in the formation of a circuit. So in the cases ‘23’, ‘24’, ‘33’, and ‘34’ the new site cannot be occupied, otherwise the updating rules are identical to those for animals.

## 3 Analysis of the series

The series listed in Table II have coefficients which grow exponentially, with sub-dominant term given by a critical exponent. The generic behaviour is $`g_n\mu ^nn^{\xi 1}`$, and hence the generating function has the behaviour, $`G(u)=_ng_nu^n(1u/u_c)^\xi ,`$ where $`u_c=1/\mu `$. From (1) we get the following predictions for the animal generating functions:

$`𝒜(u)`$ $`=`$ $`{\displaystyle \underset{n}{}}a_nu^n=A(u)(1u\lambda )^{1\tau },`$ (5)
$`_g^2(u)`$ $`=`$ $`{\displaystyle \underset{n}{}}a_nR^2_nn^2u^n={\displaystyle \underset{n}{}}r_nu^nR(u)(1u\lambda )^{(\tau +2\nu +1)}.`$ (6)
Similar expressions hold for the corresponding tree generating functions though with a different growth constant $`\lambda _0`$. So the animal and tree generating functions are expected to have a logarithmic singularity, while the radius of gyration series are expected to diverge with an exponent $`2+2\nu `$, where we assumed the conjecture $`\tau =1`$ to be correct.

In the first stage of the analysis, we used the method of differential approximants . Estimates of the critical point and critical exponent were obtained by averaging values obtained from second order inhomogeneous differential approximants. In Table III we have listed the estimates obtained from this analysis. The error quoted for these estimates reflects the spread (basically one standard deviation) among the approximants. Note that these error bounds should not be viewed as a measure of the true error as they cannot include possible systematic sources of error. From this we see that the animal generating function has a singularity at $`u_c=0.246150(1)`$, and thus we obtain the estimate, $`\lambda =4.06256(2)`$, for the growth constant. The exponent estimates are consistent with the expected logarithmic divergence, thus confirming the conjecture $`\tau =1`$. The central estimates of $`u_c`$ obtained from the radius of gyration series are a little larger than, but nonetheless consistent with the animal generating function. From this analysis we see that the series has a divergence at $`u_c`$ with an exponent $`2+2\nu =3.2840(8)`$, and thus $`\nu =0.6420(4)`$.

The tree generating function has a singularity at $`u_c=0.2634870(5)`$, and thus $`\lambda _0=3.795254(8)`$, with the expected logarithmic divergence. In this case estimates from the radius of gyration series yield $`2+2\nu =3.2823(1)`$, and thus $`\nu =0.64115(5)`$. Since the $`u_c`$ estimates from the two tree series are in excellent agreement we claim that the best estimate for $`\nu `$ is the one obtained from the tree series. This estimate is consistent with, but much more accurate than, the recent estimate $`\nu =0.642(2)`$ obtained from Monte Carlo simulations of lattice trees . It is also consistent with the estimate $`\nu =0.6408(3)`$ obtained using phenomenological renormalization to lattice animals .

A more detailed analysis of the animal series was performed in . It showed that in a plot of exponent vs $`u_c`$ estimates, as $`1\tau `$ approach 0, $`u_c`$ approach 0.2461497. From the spread among the approximants we obtained the final estimate $`u_c=0.2461496(5)`$, and thus the growth constant $`\lambda =4.062570(8)`$. A similar analysis of the radius of gyration series yielded estimates of $`\nu `$ consistent with those obtained for lattice trees.

Finally we use the series to derive improved rigorous lower bounds for the growth constants of lattice animals and trees. Using concatenation arguments Rands and Welsh  showed that if we define a sequence $`p_n`$ such that

$$a_{n+1}=p_{n+1}+p_na_2+\mathrm{}p_3a_{n1}+p_2a_n,$$
(7)
and construct the generating functions

$$𝒜^{}(u)=1+\underset{n=1}{\overset{\mathrm{}}{}}a_{n+1}u^n$$
(8)
and

$$𝒫(u)=\underset{n=1}{\overset{\mathrm{}}{}}p_{n+1}u^n$$
(9)
then

$$𝒜^{}(u)=1+𝒜^{}(u)𝒫(u)$$
(10)
and $`𝒜^{}(u)`$ is singular when $`𝒫(u)=1`$. The coefficients in $`𝒫(u)`$ are obviously known correctly to the same order $`N=2W_{\mathrm{max}}1`$ as $`𝒜^{}(u)`$. If we look at the polynomial $`P_N`$ obtained by truncating $`𝒫(u)`$ at order $`N`$ then the unique positive zero, $`1/\lambda _N`$, of $`P_N1=0`$ is a lower bound for $`\lambda `$. Using our extended series we find that $`\lambda 3.903184\mathrm{}`$.

For site trees the best lower bound appears to arise from a different concatenation procedure , which leads to the equation

$$𝒯(u)=\frac{1𝒬(u)}{12𝒬(u)}$$
(11)
and $`𝒯(u)`$ is singular when $`𝒬(u)=1/2`$. This approach yields a lower bound for site trees, $`\lambda _03.613957\mathrm{}`$.

## 4 Conclusion

We have presented an improved algorithm for the enumeration of site animals on the square lattice. The computational complexity of the algorithm is exponential with time (and memory) growing as $`a^{n/2}`$, where $`a`$ appears to be a little larger than 2. Implementing this algorithm has allowed us to count the number of site animals up size 46. Our extended series enables us to give an improved estimate for the growth constant and confirm to a very high degree of certainty that the associated generating function has a logarithmic divergence. The algorithm was also modified to enumerate lattice trees up to size 44, and a generalised version was used to calculate the radius of gyration of animals and trees up to size 42. Analysis of the series confirmed that animals and trees belong to the same universality class and an accurate estimate was obtained for the size exponent $`\nu `$.

## E-mail or WWW retrieval of series

The series for the generating functions studied in this paper can be obtained via e-mail by sending a request to I.Jensen@ms.unimelb.edu.au or via the world wide web on the URL http://www.ms.unimelb.edu.au/~iwan/ by following the instructions.

## Acknowledgements

Financial support from the Australian Research Council is gratefully acknowledged.


text:
# Quenching and Annealing in the Minority Game

## Abstract

We report the occurrence of quenching and annealing in a version of the Minority Game (MG) in which the winning option is to join a given fraction of the population that is a free, external parameter. We compare this to the different dynamics of the Bar Attendance Model (BAM)where the updating of the attendance strategy makes use of all the available information about the system and quenching does not occur. We provide an annealing schedule by which the quenched configuration of the MG reaches equilibrium and coincides with the one obtained with the BAM.

Keywords: Minority game, Organization, Evolution

In recent times considerable attention has been given to the description of self-organization phenomena in multi agent models. These are geared to explain how (and which) individual decisions give rise to cooperative effects that show up in the behavior of the system as a whole. Such models have applications in a variety of situations that range from routing of messages in an information network to the way in which equilibrium is (dynamically) achieved by an ensemble of economic agents.

A well known framework in this line of research is the Bar Attendance Model (BAM) proposed by B Arthur in . In this model, $`N`$ agents have to decide whether or not to go to a bar at a certain date. The customers share the perception that the attendance should not exceed a value $`n`$, $`n<N`$ in order to avoid crowding. If the attendance is kept below that threshold, they derive a positive utility. As all the agents accommodate their individual attendance strategies seeking to increase their own utility, the whole system self-organises keeping the attendance at the required value.

In recent times a simplified version of the BAM called the Minority Game (MG) has received much attention - .The main simplification is that agents derive utility whenever their choice coincides with that of the minority. This is equivalent to fix $`n`$ in the BAM at $`n=(N1)/2`$. The agents update their attendance strategies making use of information concerning the attendance of the previous days.

Several variations of this model have been discussed in the literature. They essentially differ in the way in which the adaptation process takes place. We restrict ourselves to consider the probabilistic version  of the Johnson et al. model with a slight change in order to leave the accepted level of attendance $`n`$ as an external free parameter. Each agent has a given strategy expressed by a probability $`p_i`$ ($`i=1,2,\mathrm{},N`$) to attend the bar. If her option is to go (not to go) and the attendance $`A`$ is $`An`$ $`(A>n)`$, the agent gains a point. Otherwise, the agent looses a point. If her total number of points falls below a fixed negative threshold her account is reset to zero and her strategy $`p_i`$ is updated changing its value into one chosen at random in the interval $`(p_i\delta p,p_i+\delta p)`$. Reflective boundary conditions are used whenever necessary. The parameter $`\delta p`$ is kept fixed. If $`n=(N1)/2`$ this framework coincides with the well known MG.

The state of the many agent system is described by the density distribution $`P(p)`$ that gives the fraction of agents that have a strategy within the interval $`(p,p+dp)`$. Within the framework of the MG, an asymptotic $`P_{\mathrm{}}(p)`$ is reached that displays a polarization of the population: essentially half of the agents always go to the bar while the other half never go thus keeping the average attendance close to $`N/2`$ as expected.

The evolution of the MG with $`\mu =n/N1/2`$ has been studied by Johnson  reporting that a situation can be reached in which no further updating of the strategies takes place and the distribution $`P_q(p)`$ that is reached strongly differs from $`P_{\mathrm{}}(p)`$. In the present note we investigate this effect in detail. We prove that this is a situation in which the system is far from equilibrium. We also provide a prescription that can be followed to effectively reach equilibrium starting from a quenched configuration.

We have performed extensive numerical simulations starting with an initial condition for $`P(p)`$ in which all agents have a strategy $`p`$ that is chosen at random in the interval $`(0,1)`$ with uniform probability. We have used several values of $`N`$ and changed $`\mu `$ above and below $`1/2`$. The overall behavior of the many agent system has been found to be nearly symmetric around $`\mu =1/2`$. Hence, we only show results for $`\mu >1/2.`$

We find that if $`\mu \mu _{cr}`$ a quenched distribution $`P_q(p)`$ is reached. We establish that quenching has occurred when no further updating of strategies takes place. This naturally happens when all agents have more than a sizable number of positive points. In what follows most of our discussions assume that the prize for winning measured in units of the fine for loosing is $`G=1`$. We explicitely remark when this is not the case.

Some examples of $`P_q(p)`$ are shown in Fig.1. It is worth to remark three features. First the value $`P_q(p)=0`$ for $`0<p<1/2`$ (or $`1/2<p<1`$) , second that the width of the peak near $`p=1/2`$ is only a function of $`\delta p`$ and third that the total attendance never reaches the required fraction $`\mu `$. These features can qualitatively be understood. If one assumes that $`\mu `$ is large enough, agents face very different situations depending whether they have $`p<1/2`$ or $`p1`$. In the first case the agents loose points frequently and therefore change their strategies constantly increasing the value of $`p`$. Those agents with $`p1/2`$ will instead seldom loose and their strategies are rarely updated. The attendance will therefore not increase significantly from the initial value and a quenched state is rapidly reached.

The above arguments indicate that the shape of $`P_q(p)`$ strongly depends upon the initial conditions. This is the reason why we prefer to call this effect “quenching” rather that “freezing”. The latter suggests a new ordering that bears no relationship with the initial conditions, while the former indicates that a dynamics has been imposed that suddenly fixes the internal parameters of the system at values that are close to those corresponding to initial conditions and are far from equilibrium.

Quenching starts to show up in a narrow region below a critical value $`\mu _{cr}`$. The fact that this region becomes narrower for greater values of $`N`$ indicates that its existence is to be attributed to the fact that we are dealing with a finite number of agents. For the same reasons the values $`\mu _{cr}`$ also display some dependence upon $`N`$ (see Fig 3). These values become smaller (larger) if $`G`$ is increased (diminished).

The occurrence of quenching can also be investigated in the BAM. According to the rules of the BAM agents derive utility in two situations: one when they decide to go to the bar and $`A<n`$ and when they decide not to attend the bar and $`A>n`$. The adaptive dynamics of the BAM has been studied with schemes either borrowed from genetic algorithms    or bearing strong resemblances with that scheme. A purely probabilistic, mean field approach is however desirable to ease the comparison with the treatments of the MG.

We suggest a dynamics that is based upon the same information as in the MG but uses it differently keeping track of the reasons for loosing or winning. We introduce “points” and “credits”. Points are gained or lost if the option of attending the bar is correct or not. Credits are instead gained or lost depending whether the option of not attending the bar is correct or not. We therefore carry a double account: if an agent chooses to attend (not to attend) the bar and $`A<n`$ ($`A>n`$)gains a point (a credit). Otherwise, she looses a point (a credit). When either the number of points or the number of credits falls below a negative threshold the corresponding account is reset to zero and the strategy is changed in the same fashion as already mentioned for the MG.

Using the above dynamics we have obtained the asymptotic density distributions for various settings. We compare them with the ones obtained with the MG in Fig.1. Whenever $`\mu <\mu _{cr}`$ and no quenching is found in the MG, both distributions $`P_{\mathrm{}}^{MG}`$ and $`P_{\mathrm{}}^{BAM}`$ can barely be distinguished from each other. In this regime while the distribution remains stationary individual strategies are continously updated and the level of attendance reaches the accepted fraction $`\mu `$. However if $`\mu >\mu _{cr}`$ the distribution $`P_{\mathrm{}}^{BAM}(p)`$ is completely different to $`P_q^{MG}(p)`$ for the same settings. While in the MG no further updating of strategies takes place, strategies in the BAM continue to be updated at all times. In addition the density distribution has lost all memory of the initial conditions and displays a strong (asymmetric) self-organization: many agents attend the bar almost all the time, while a smaller fraction have a very small probability to go.

It is possible to support these facts with a simple analytical discussion. We note that if all agents share the same strategy $`p`$, the probabilities $`\mathrm{\Pi }_{pt}`$ and $`\mathrm{\Pi }_{cd\text{ }}`$of winning respectively points and credits are given by

$`\mathrm{\Pi }_{pt}(p)`$ $`=`$ $`S(N,n,p)={\displaystyle \underset{i=0}{\overset{n1}{}}}\left({\displaystyle \genfrac{}{}{0pt}{}{N1}{i}}\right)p^i(1p)^{N1i}`$ (1)
$`\mathrm{\Pi }_{cd}(p)`$ $`=`$ $`1S(N,n+1,p)`$ (2)
for simplicity, we will write down the $`N`$ and $`n`$ dependence of $`\mathrm{\Pi }_{pt,cd}`$ only when necessary. In order to be quenched the probabilities $`\mathrm{\Pi }_{pt}`$ and $`\mathrm{\Pi }_{cd}`$ should both be greater than the probabilities of loosing respectively points and credits, namely, $`i.e.`$ $`\mathrm{\Pi }_{pt}1/2,`$ and $`\mathrm{\Pi }_{cd}1/2.`$ This can clearly not be fulfilled simultaneously. Therefore agents either win points and loose credits or vice versa forcing an updating of their strategies $`p`$.

A similar analysis can be made for the MG. If the system is prepared with a distribution $`P_0(p)=\delta (pp_o)`$ and $`G=1`$ this will be quenched if the probability of winning $`\mathrm{\Pi }_w(p)`$ fulfills $`\mathrm{\Pi }_w1\mathrm{\Pi }_w`$, namely

$$\mathrm{\Pi }_w(p_o)=p_o\mathrm{\Pi }_{pt}(p_o)+(1p_o)\mathrm{\Pi }_{cd}(p_o)\frac{1}{2}$$
(3)
the case for $`G1`$ can easily be taken into account changing the r.h.s. of Eq.3 into $`1/(1+G)`$.

The situation for the MG is completely different than for the BAM. The function $`\mathrm{\Pi }_w(p)`$ has a single maximum in the interval $`0p1`$. Furthermore, the curves $`\mathrm{\Pi }_w(N,n,p)`$ fulfill $`\mathrm{\Pi }_w(N,n,p)`$ $`\mathrm{\Pi }_w(N,Nn,1p)`$. Strict equality holds in the limit $`N\mathrm{},`$ $`\mu 0,1.`$ In Fig.2 we show an example of the functions $`S(N,n,p)`$ and $`\mathrm{\Pi }_w(p)`$ for typical values of $`N`$ and $`n`$, and $`\mu >1/2`$.

For finite $`N`$ and $`\mu 1/2`$ the value max$`[\mathrm{\Pi }_w]=\mathrm{\Pi }_w^{mx}`$ is less than $`1/2`$ and no quenching occurs. For greater values of $`\mu `$ one can define a critical value $`\mu _{cr}=n_{cr}/N`$ for which $`\mathrm{\Pi }_w^{mx}=1/2`$ and quenching occurs. If one sets $`\mu `$= 1/2, the value of $`\mathrm{\Pi }_w^{mx}`$ is seen to approach the value 1/2 as $`N\mathrm{}`$ thus suggesting that an infinite agent system prepared with the initial conditions $`P_0(p)=\delta (p1/2)`$ is almost quenched. (see Fig. 3).

Above $`\mu _{cr}`$ Eq.3 is fulfilled for any $`p_o`$ in the interval limited by $`p_<`$ and $`p_>`$ that are the two roots of the equation $`\mathrm{\Pi }_w(p)=1/2`$. Any system prepared with a distribution $`P_0(p)=\delta (pp_o)`$ with $`p_o`$ within that region will rapidly be quenched $`i.e.`$ will not change under the evolutive dynamics.

It can be checked that the system evolves quite differently if the initial conditions are $`p_o<p_<`$ or $`p_o>p_>`$. In the first case the whole population of agents update their strategies, forcing all individual $`p`$’s to surpass the value $`p_<`$. Once this happens, updating stops and the system gets quenched with an attendance level below the accepted fraction $`\mu `$. For $`p_o>p_>`$ the asymptotic distribution $`P_{\mathrm{}}^{MG}`$ displays a strong (asymmetric) polarization, updating of strategies continues to take place continuously and the attendance reaches the required fraction $`\mu `$. We have checked numerically this with initial conditions of the type $`P_0(p)=\delta (pp_o)`$. Typical examples of the asymptotic distributions are shown in Fig.2. Those that correspond to initial conditions with $`p_o>p_>`$ are not distinguishable from those obtained with BAM for the same settings.

The situations described hitherto indicate that outside a very restricted region of $`\mu `$ and for different initial conditions, the dynamics of the MG rapidly approaches quenching. The many agent system stops evolving, the attendance remains fixed at a value that is far from the tolerated fraction $`\mu `$ and all the other internal parameters remain close to the initial conditions. The results reported in  can be seen to fall also in the framework presented here.

Opposed to this, the BAM approaches always a distribution $`P_{\mathrm{}}^{BAM}(p)`$ that corresponds to what one expects of thermodynamics equilibrium: the attendance fluctuates around the expected fraction $`\mu `$, all agents continue to update their individual strategies and $`P_{\mathrm{}}^{BAM}(p)`$ remains stationary.

The way to regain equilibrium within the framework of the MG is through an annealing protocol geared to correct progressively the quenched distribution $`P_q(p)`$. The key point is to realize that quenching is produced by the memory stored in the points gained by the agents. In fact the quenched state remains fixed because there are no agents that ever loose points. We have implemented a procedure that consists in obliterating periodically the memory of the system by removing all the points gained by all the agents in each annealing episode.

The results are displayed in Fig.4 for the case $`\mu =85/101`$. At the end of the first episode the distribution $`P^1(p)`$ is entirely similar to those shown in Fig1. As agents are repeatedly deprived of points some are increasingly forced to update their strategies. Successive changes approach $`P_{\mathrm{}}^{BAM}(p)`$. The way in which the annealing protocol works is shown in the inset of Fig.4. Quenching is checked by establishing that all agents have more than, say, 5 points. In addition we count how many steps are required to reach such quenched state. During the first 15 annealing episodes very few steps are required in order to have all the 101 agents with more than 5 points. After that moment the number of (quenched) agents that have more than 5 points starts to fall while the number of steps grows rapidly thus showing the occurrence of a greater number of individual updatings. After 40 episodes full equilibrium is reached and the number of steps saturates at the maximum allowed for each annealing episode. Throughout this process the attendance steadily grows approaching the required fraction of $`\mu 0.85`$.

In the present note we have discussed how quenching occurs in the MG. The quenched state is far from equilibrium and strongly depends upon the initial conditions. This situation is a direct consequence of the dynamics for updating the individual attendance strategies. Contrary to this the BAM reaches a situation that can be thought as thermodynamic equilibrium. This difference has to be attributed to the fact the MG makes not full use of the (global) available information about the system while the BAM dynamics keeps instead track of the reasons for previous successes and failures. We also show how the quenched state can be brought back to equilibrium through an annealing protocol that amounts to periodically obliterate the memory stored in the system by removing all the points that have been gained by the agents. E.B. has been partially supported by CONICET of Argentina, PICT-PMT0051;H.C. and R.P. were partially supported by EC grant ARG/b7-3011/94/27, Contract 931005 AR.


text:
# The star formation history of resolved galaxies: Composite H-R diagram.

## 1. Introduction

We can study the evolution of the nearest galaxies in exquisite detail from the information contained in the H-R diagram -or Color-Magnitude Diagram, CMD- of their resolved stars. From it, it is possible to retrieve the star formation and chemical enrichment histories (SFH and Z(t)), with a level of detail that mainly depends on the magnitude limit of the available CMD. For CMDs reaching the oldest main-sequence (MS) turnoffs, it is possible to break the age-metallicity degeneracy that affects most methods of retrieving SFHs. Even if we can pursue this kind of study only in a very limited volume of the Universe, it is a worthwhile task, key to understand galaxy formation and evolution in general, because:

$``$ In our neighborhood, we have representatives of almost any kind of galaxies in the Universe: in the Local Group there are three spirals, and a large number of dwarf -both dIr and dSph- galaxies; the nearest gE, NGC5128 is at $`4.0`$ Mpc, and similarly, the nearest BCD and LSB galaxies are in the M81 group, also at $`4.0`$ Mpc. In addition, by studying the details of the SFHs in the nearest galaxies, we may be able to identify the evolved counterparts of distant objects that are experiencing characteristic star forming episodes.

$``$ This kind of study provides detailed information on the first events of star formation in the nearest galaxies. Therefore, we can address questions like “have the oldest stars in galaxies all the same age?” or, “are there differences, in the epoch or strength of the early star formation, depending on environment”.

$``$ We can test the hypothesis of galaxies being assembled by merging through the almost direct observation of the merging history of the Milky Way.

$``$ It offers an alternative to the cosmologic look-back-time approach to study galaxy evolution, by tracing the complete evolution of particular objects.

Furthermore, it is indeed a feasible task. From the observational point of view, we have the means of gathering the necessary observations. For the nearest objects, the dSph satellites of the Milky Way and the Magellanic Clouds, we have excellent wide-field CCDs on ground-based telescopes. Observations of this kind have already revealed in amazing detail the varied SFHs of these galaxies, and we will be able to reach the same level of detail for the remaining Local Group galaxies using the Advanced Camera for Surveys (ACS) on the HST. Further improvements in optical capabilities on space (e.g. NGST) or the ground (e.g. adaptive optic systems) will be important to pursue the same kind of studies, with similar precision to larger distances. From the theoretical point of view, and hand in hand with increasing computational power, we are seeing important improvement on stellar evolution models (through e.g. more realistic treatments of convection or rotation, or improved opacities), and on the accurate modeling of synthetic CMDs with realistic simulations of observational errors.

There is three main levels of information in the CMD depending on the magnitude limit of the available data: the one we obtain when we reach the oldest MS turnoffs, the one provided by reaching the horizontal branch (HB) level, and when we only observe a couple of magnitudes below the tip of the red-giant branch (RGB); see Figure 1. I will discuss them separately below.

## 2. A quantitative method of deriving SFHs: synthetic CMDs

The comparison of the observed CMDs with synthetic CMDs computed using stellar evolution models is a fundamental tool that is becoming widely used to quantitatively retrieve the SFH from the CMD. With this technique, a number of synthetic -or model- CMDs are computed assuming possible scenarios for the SFH, which can be reasonably decomposed in a number of simpler functions: the instantaneous star formation rate, SFR($`t`$), the chemical enrichment law, $`Z(t)`$, the initial mass function, IMF, and a function $`\beta (f,q)`$ controlling the fraction $`f`$ and mass ratio distribution $`q`$ of binary stars (Aparicio 1998; Gallart et al. 1999b). This basic approach has been followed, with variation in the details, by a number of groups (Bertelli et al. 1992; Gallart et al. 1996a; Tolstoy & Saha 1996; Dolphin 1997; Hernández, Valls-Gabaud & Gilmore 1998; Hurley-Keller, Mateo & Nemec 1998; Ng 1998), and it has proven particularly successful, and leading to basically unique results when applied to data reaching the oldest MS turnoffs (Gallart et al. 1999b). In the following, I will comment on the application of this method to CMDs of different magnitude limits.

## 3. The best case: when the CMD reaches the oldest MS turnoffs

During the last decade, our conception of the evolution of the dSph galaxies satellites of the Milky Way, has changed dramatically from the idea that they were predominantly old systems, to our current knowledge of their varied SFHs. Indeed, we find almost every imaginable evolutionary history in this sample of galaxies, from the extreme case of Leo I (Gallart et al. 1999a,b), which has formed over 80% of its stars from 6 to 1 Gyr ago, to intermediate cases like Carina (Smecker-Hane et al. 1996; Hurley-Keller et al. 1998) and Fornax (Stetson, Hesser & Smecker-Hane 1997; Buonanno et al. 1999), with prominent intermediate-age populations, to predominantly old ($``$ 10 Gyr old) systems like Sculptor (Hurley-Keller, Mateo & Grebel 1999), Draco (Aparicio, Carrera & Martínez-Delgado 2000), Ursa Minor (Martínez-Delgado & Aparicio 1998) or Leo II (Mighell & Rich 1996). Studies of the LMC SFH have also benefited of CMDs of this quality (e.g. Holtzman et al. 1999). This clear and extremely interesting picture has only been obtained when CMDs reaching the oldest MS turnoffs, and covering a substantial fraction of the galaxy have been available.

Even though CMDs of this kind offer qualitative first glance SFHs (e.g. in the case of Carina, the most emblematic example, one can see, just by comparing the CMD with isochrones, that there has been three major events of star formation), a quantitative determination of the SFH requires a detailed comparison of the distribution of stars in the CMD with that predicted by model CMDs. With CMDs reaching the old MS turnoffs, there is the advantage that the stellar evolution involved (that of MS and subgiant-branch stars) is relatively well known, and there is less intrinsic degeneracy age-metallicity. Indeed, we have shown that, with this method, it is possible to break the classical age-metallicity degeneracy in stellar populations (Gallart et al. 1999b). This is so because detailed information on the age distribution of the stars is gained from their distribution along the MS and subgiant branches. Once this is determined, the possibilities for metallicity distributions are relatively unique in order to fit the detailed distribution of stars in the CMD. Admittedly, the position of the stars in the MS and subgiant branches also depends on metallicity, but, in practice, only narrow combinations of $`Z(t)`$, SFR($`t`$) and $`\beta (f,q)`$ can reproduce the distribution of stars in the CMD.

## 4. How well can we do with CMDs not reaching the oldest MS turnoffs?

Here I will distinguish two cases depending on the information they provide: when the CMD reaches below the HB level, $`M_I1`$, and when only 2-3 magnitudes below the tip of the RGB are observed, $`M_I2`$ (see Figure 1). In both cases, the CMD is populated by stars of all ages, and therefore, it must be possible, in principle, to retrieve information about the complete SFH. As before, the analysis of the CMD using synthetic CMDs is potentially the best method to derive quantitative information. However, the detail with which the SFH can be retrieved is necessarily smaller than in the previous case.

We are undertaking a project, using CTIO MOSAIC data of the LMC, to quantify the maximum amount of information on the SFH that one should aim to retrieve from CMDs with different magnitude limits. Thanks to its proximity, the LMC is ideal for this project because one can obtain wide field, good precision old MS turnoff photometry from the ground. Photometry over large areas is necessary to obtain good statistics of stars in short lived evolutionary phases, which are key in the analysis of shallower CMDs. The aim is to independently retrieve the SFH from CMDs of different limiting magnitudes, to learn both about the information we loose at each step and about possible strategies to help make the most of the available data. Such test is important because we can potentially obtain HB and particularly, RGB photometry out to distances like those of the nearest clusters of galaxies, and we must know how confidently we can derive SFHs there. A similar project, to compare SFHs obtained through CMD analysis and integrated spectroscopy is underway together with several participants in this conference (Alloin, Demarque, Fritze von-Alvensleben, Hardy et al.)

### 4.1. CMDs reaching the HB level

The main age markers here are the (blue and red) HB and the red-clump (RC) of core He-burning stars. The presence and appearance of these features, and in particular that of the HB depends on both age and metallicity, although other factors, particularly the amount of mass loss during the RGB phase, may also play a role (Lee 1993). Very old, low metallicity stars distribute along the HB during the core He-burning phase and, generally speaking, produce a red HB when the core He burners are not so old, or more metal rich, or both. A RC well populated and extended in luminosity (like that of Leo I in Figure 1) denotes the presence of a large intermediate-age population. In addition, the vertical RC (Zaritsky & Lin 1997) is populated by few hundred Myr old stars that don’t undergo the He-flash (Beaulieu & Sackett 1998; Gallart 1998)

One should aim at retrieving old and intermediate-age star formation rates, integrated over intervals of a few Gyr, by fitting the number of stars in the HB, the RC and the RGB using synthetic CMDs. In spite of the uncertainties in the modeling of these advanced stellar evolution phases, the comparison of the models with the CMDs and luminosity functions of star clusters (see Maeder & Renzini 1983; Renzini & Fusi Pecci 1988; Chiosi, Bertelli & Bressan 1992) show reasonable agreement, (e.g. Zoccali & Piotto 2000) even though some parameters in the models are still uncertain (e.g. the He content, the $`{}_{}{}^{12}C(\alpha ,\gamma )^{16}O`$or the details of the mixing processes, see Zoccali et al. 2000).

HST has provided HB-RC CMDs for a sample of Local Group galaxies outside the Milky Way system. The M31 dSph satellites have been studied by Da Costa et al. (1996, 2000), while the remaining M31 satellites have been studied by a variety of authors (e.g., M32: Grillmair et al. 1996; NGC147: Han et al. 1997; NGC185 and NGC205: Geisler et al. 1998). Similar data have been analized for some of the dIr (Leo A: Tolstoy et al. 1998; Pegasus: Gallagher et al. 1998; IC1613: Cole et al. 1999; WLM: Dolphin 2000; Sextans A: Dohm-Palmer et al. 1997). Also VLT is starting to produce results in this regard (Tolstoy et al. 2000; Held et al. 2000). It is beyond the scope of this paper to summarize the results of these works, and I would just like to comment on very general aspects. In the case of the M31 companions, the main general conclusion may be the diversity of their SFHs, much like among the Milky Way satellites (Da Costa et al. 2000). For the dIr, it has been possible to retrieve in detail the SFH up to about 1 Gyr ago using MS and blue-loop stars (Dohm-Palmer et al. 1997), and to reveal a prominent intermediate-age star formation. However, the positional overlap of the blue HB with the generally well populated $``$ 1 Gyr old MS in the CMD difficults the characterization of the old population, and therefore, additional constraints on the old stars, like studies of RR Lyrae variables, are important. As for the Milky Way satellites, CMDs reaching the oldest MS turnoffs of dwarf galaxies through the Local Group would reveal the detail of their SFHs and would allow us to study the early evolution of isolated dwarf galaxies, as well as dwarfs in a different satellite system like that of M31. And they would provide us, again and very likely, with fundamental surprises. This will become technically feasible for the first time with ACS on HST.

Finally, I would like to mention other potentially very useful stellar population markers in the HB-RC area of the CMD, namely the RGB-bump, the AGB-bump (Gallart 1998) and the vertical structure of the RC (Piatti et al. 1999). These structures are produced by very short-lived phases of stellar evolution, and they have only become evident in the CMDs of composite stellar populations when very densely populated CMDs have been available. While the RGB and AGB-bumps are produced by stellar populations of basically any age, and their structure depends on both age and metallicity, the vertical structure is predicted to be produced by relatively metal rich stars (Z $``$ 0.004) in a very narrow range of masses and ages around 1 Gyr (Girardi 1999).

### 4.2. CMDs reaching just below the tip of the RGB

Gallart et al. (1996a,b) and Aparicio, Gallart & Bertelli (1997a,b) used synthetic CMDs to constrain the SFHs of the dIr galaxies NGC6822, Pegasus and LGS3 using this kind of data. Only star formation rates averaged over relatively long periods of time can be obtained in this way (see also Aparicio 1998), but it was also possible to conclude that star formation began in these galaxies at an early epoch ($`1510`$ Gyr ago), and that they contained a relatively prominent old population. In addition, some constraints on the chemical enrichment history were obtained by including different parameterizations of Z(t) in the models.

The position and width of the RGB have been widely used to derive the mean metallicity and metallicity dispersion of the stars in dwarf galaxies (Da Costa & Armandroff 1990; Lee, Freedman & Madore 1993; Saviane et al. 2000). This method, however, assumes that the contribution of the dispersion in age to the width of the RGB is basically negligible, and it has to be used with care when there is a substantial intermediate-age population since, in this case, and specially for low metallicity systems, a substantial fraction of the RGB width may be contributed by age. Finally, AGB stars are useful tracers of intermediate-age star formation (Gallart et al. 1994).

CMDs of this kind are available for basically all Local Group dwarf galaxies. Besides the ones referenced above, good examples among those not yet superseded by published deeper data are the following. Phoenix: Martínez-Delgado, Gallart & Aparicio, 1999; NGC3109: Minniti & Zijlstra 1997; DDO210: Lee et al. 2000; Sag DIG: Karachentsev, Aparicio & Makarova 1999; Antlia: Piersimoni et al. 1999; And VI: Armandroff, Jacoby & Davies 1999; Grebel & Guhatakurta 1999; Gallart et al. 1998). CMDs for very distant galaxies, of types not represented in the Local Group have been obtained using HST (e.g. Schulte-Ladbeck et al. 1999; Harris, Harris & Poole 1999).

## 5. Summary and concluding remarks

Deep CMDs, in particular those reaching the oldest MS turnoffs, are our most valuable tools to retrieve in detail the SFH of nearby galaxies. Spectroscopy is a very useful complement, but, on its own, it is not well suited to derive SFR($`t`$), or even Z($`t`$) directly; instead, the temporal information is beautifully laid out in the CMD. Even if possible for a very limited volume of the Universe, I have argued that this is a worthwhile task, key to understand galaxy formation and evolution in general, because we have representatives of most types of galaxies in our neighborhood, and because using nearby objects, we can learn what can be obtained, and trusted, from integrated properties. And most importantly, it is a really feasible task using the latest generations of telescopes and instruments, particularly HST (specially with ACS) and the new generations of 8–10m class telescopes, equipped with some kind of adaptative optics capability.

But still a lot remains to be done. Even for some of the nearest galaxies (the satellites of the Milky Way) for which beautiful CMDs exist, analysis using the full power of current modeling techniques are still lacking. For the most distant galaxies, the optimal data does not yet exist, but is under reach of current instrumentation. Representations of the SFHs of the more distant LG galaxies like those presented by Mateo (1998) or Grebel (1998) provide an useful, qualitative view of the SFH of these systems as inferred from different stellar tracers but should not be taken literally: we still don’t know, in any level of detail, the evolutionary histories of Local Group galaxies outside the Milky Way neighborhood, and reliable population boxes (Hodge 1989) for these systems in such a level of detail will only be available when deeper data (reaching at least the HB level, and preferably the old MS turnoffs) will be quantitatively analized. But we are getting there. And we will get there faster if we can persuade our colleagues on TAC’s that this type of study is a key path and ingredient in our quest for the global understanding of galaxy formation and evolution.

#### Acknowledgments.

I thank A. Aparicio. J. Gallagher and D. Mardones for a critical reading of the manuscript, and the conference organization for financial support.

## References

Aparicio, A. 1998, in IAU Symp. 192, The Stellar Content of Local Group Galaxies, ed. P. Whitelock & R. Cannon, ASP Conference Series

Aparicio, A., Carrera, R. & Martínez-Delgado, D. 2000, AJ, submitted

Aparicio, A., Gallart, C., Bertelli, G. 1997a, AJ, 114, 669

Aparicio, A., Gallart, C., Bertelli, G. 1997b, AJ, 114, 680

Armandroff, T.E., Jacoby, G.H. & Davies, J.E. 1999, AJ, 118, 1220

Beaulieu J.P. & Sackett, P.D. 1998, AJ, 116, 209

Bertelli, G., Bressan, A., Chiosi, C., Fagotto, F. & Nasi, E. 1994, A&AS, 106, 275

Bertelli, G., Mateo, M. Chiosi, C. & Bressan, A. 1992, ApJ, 388, 400

Buonanno, R. et al. 1999, AJ, 118, 1671

Chiosi, C., Bertelli, G., Bressan, A. 1992, ARAA, 30, 235

Cole, A., et al. 1999, AJ, 118, 1657

Da Costa, G. S. & Armandroff, T. E. 1990, AJ, 100, 162

Da Costa, G.S., Armandroff, T.E., Caldwell, N. & Seitzer, P.1996, AJ, 112, 2576

Da Costa, G.S., Armandroff, T.E., Caldwell, N. & Seitzer, P. 2000, AJ, 119, 705

Dohm-Palmer, R.C. et al. 1997, AJ, 114, 2527

Dolphin, A. 1997, New Astronomy, 2 (5), 397

Dolphin, A. 2000, ApJ, 531, 804

Gallagher, J.S. et al. 1998, AJ, 115, 1869

Gallart, C. 1998, ApJ, 495, L43

Gallart, C., Aparicio, A., Bertelli, G. & Chiosi, C. 1996a, AJ, 112, 1950

Gallart, C., Aparicio, A., Bertelli, G. & Chiosi, C. 1996b, AJ, 112, 2596

Gallart, C., Aparicio, A., Chiosi, C., Bertelli, G. & Vílchez, J.M. 1994, ApJ, 425, L9

Gallart, C. et al. 1999a, ApJ, 514, 665

Gallart, C., Freedman, W.L., Aparicio, A., Bertelli, G., Chiosi, C. 1999b, AJ, 118, 2245

Gallart, C., Martínez-Delgado, D., Aparicio, A. & Freedman, W.L. 1998, in IAU Symp. 192, The Stellar Content of Local Group Galaxies, ed. P. Whitelock & R. Cannon, ASP Conference Series

Geisler, D., Sarajedini, A., Armandroff, T. E., Da Costa, G., Lee, M. G. 1998, in IAU Symp. 192, The Stellar Content of Local Group Galaxies, ed. P. Whitelock & R. Cannon, ASP Conference Series

Girardi, L. 1999, MNRAS, 308, 818

Grebel, E.K. 1998, in IAU Symp. 192, The Stellar Content of Local Group Galaxies, ed. P. Whitelock & R. Cannon, ASP Conference Series, 1

Grebel, E.K. & Guhathakurta, P. 1999, ApJ, 511, L101

Grillmair, C.J. et al. 1996, AJ, 112, 1975

Han, M., Hoessel, J.G., Gallagher, J.S., Holtzman, J. & Stetson, P.B. 1997, AJ, 113, 1001

Harris, G.L.H., Harris, W.E. & Poole, G.B. 1999, AJ, 117, 855

Held, E.V., Saviane, I., Momany, Y., Rizzi, L. & Bertelli, G. 2000, in The Evolution of Galaxies. I- Observational Clues, eds. J.M. Vílchez, G. Stasinska & Pérez, E. Ap&SS, in press

Hernandez, X., Valls-Gabaud, D. & Gilmore, G. 1998, MNRAS, 304, 705

Hodge, P.W. 1989, ARAA, 27, 139

Holtzman, J.A. et al. 1999, AJ, 118, 2262

Hurley-Keller, D., Mateo, M. & Grebel, E. K. 1999, ApJ, 523, L25

Hurley–Keller, D., Mateo, M. & Nemec, J. 1998, AJ, 115, 1840

Karachentsev, I. Aparicio, A. & Makarova, L. 1999, A&A, 352, 363

Kroupa, P., Tout, C.A. & Gilmore, G. 1993, MNRAS, 262, 545

Lee, Y.-W. 1993, in The Globular Cluster-Galaxy Connection, eds. G.H. Smith & J.P. Brodie, ASP Conference Series 48, 142

Lee, M.G., Aparicio, A., Tikonov, N., Byun, Y.-I. & Kim, E. 2000, AJ, 118, 853

Lee, M. G., Freedman, W. L. & Madore, B. F. 1993 ApJ, 417, 553

Maeder, A. & Renzini, A. (Eds) 1983, IAU Symp. 105, Observational Tests of the Stellar Evolution Theory (Dordrecht: Reidel).

Piersimoni et al. 1999, A&A, 352, L63

Martínez-Delgado, D. & Aparicio, A. 1998, in IAU Symp. 192, The Stellar Content of Local Group Galaxies, ed. P. Whitelock & R. Cannon, ASP Conference Series

Martínez-Delgado, D., Gallart, C. & Aparicio, A. 1999, AJ, in press

Mateo, M. 1998, ARAA, 36, 455

Mighell, K. J. & Rich, R. M. 1996, AJ, 111, 159

Minniti, D. & Zijlstra, A.A. 1997, AJ, 114, 147

Ng, Y.K. 1998, A&AS, 132, 133

Piatti, A. et al. 1999, AJ, 118,2865

Renzini, A. & Fusi Pecci, F. 1988, ARAA, 26, 199

Saviane, I., Rosenberg, A., Piotto, G. & Aparicio, A. 2000, A&A, 355, 966

Schulte-Ladbeck, R.E., Hopp, U., Crone, M.M., Greggio, L. 1999, ApJ, 525, 709

Smecker-Hane, T. A., Stetson, P. B., Hesser, J. E. & van den Bergh, D. A. 1996 in From stars to galaxies…, eds. C. Leitherer, U. Fritze-van Alvensleben & J. Huchra. ASP Conf Series, 98, 328.

Stetson P. B., Hesser, J. E. & Smecker-Hane, T. A. 1998, PASP, 110, 533

Tolstoy, E. et al. 1998, AJ, 116, 1244

Tolstoy et al. 2000, The Messenger, 99, 16

Tolstoy, E. & Saha, A. 1996, ApJ, 462, 672

Zaritsky, D. & Lin, D.N.C. 1997, AJ, 114, 2545

Zoccali, M., Cassisi, S., Bono, G., Piotto, G., Rich, R.M. & Djorgovski, S.G., 2000, astro-ph/0003004

Zoccali, M. & Piotto, G. 2000, astro-ph/0005034