text:
# Charge ratio of muons from atmospheric neutrinos

## Abstract

We calculate the intensities and angular distributions of positive and negative muons produced by atmospheric neutrinos. We comment on some sources of uncertainty in the charge ratio. We also draw attention to a potentially interesting signature of neutrino oscillations in the muon charge ratio, and we discuss the prospects for its observation (which are not quite within the reach of currently planned magnetized detectors).

The MINOS detector  under construction in the Soudan Mine for study of neutrino oscillations with a neutrino beam from Fermilab will be able to measure the momentum and charge of muons in the energy range from just below one GeV to about 70 GeV/c.  In addition to its use as the far detector for accelerator neutrinos, MINOS is sufficiently large to detect a significant number of atmospheric neutrinos. Muons entering from outside the detector as well as muons originating from vertices inside the detector will occur. These events will provide a useful calibration beam for the detector.

The detector, which is now under construction at Soudan, has already detected atmospheric muons and neutrinos. After completion, MINOS will continue to collect cosmic-ray data for some time before the accelerator neutrino beam turns on and afterwards as well. Because the atmospheric neutrino beam has comparable fluxes of neutrinos and anti-neutrinos, it will be possible  to search for any sign of differences in oscillation properties of $`\nu _\mu `$ and $`\overline{\nu }_\mu `$. Such differences could arise in theories in which there is intrinsic violation of CPT . They could also arise from matter effects, for example with mixing of three active neutrino flavors if $`\mathrm{sin}^2\theta _{12}`$ is large enough  or with non-maximal $`\nu _\mu \nu _s`$ mixing.

The purpose of this letter is to calculate the rates of atmospheric neutrino interactions in a detector like MINOS as a function of direction and energy separately for neutrinos and anti-neutrinos. We briefly discuss some sources of systematic uncertainty, and we note a potentially interesting effect of oscillations as reflected in the charge ratio of atmospheric muons.

To illustrate the basic result, we start with the atmospheric neutrino spectrum of Ref. . We integrate the spectra of atmospheric neutrinos folded with $`d\sigma /dy`$ to obtain the rate of events with contained vertices. To obtain the rates of external muons, the convolution also includes the muon range.  For simplicity we use the GRV94 structure functions  to obtain the spectra of neutrino-induced $`\mu ^+`$ and $`\mu ^{}`$. (We have checked that the results for the limited range of $`x`$ and $`Q^2`$ relevant here are essentially the same as those obtained with more complicated structure functions.) In Table 1 we show expected event rates as a function of muon energy with and without oscillations, separately for contained vertices and for external upward-moving neutrino-induced muons. Full mixing with $`\mathrm{\Delta }m^2=2.5\times 10^3`$ eV2  was assumed for the oscillation case. Contained vertices are shown integrated over all directions; neutrino-induced muons are summed over the upward $`2\pi `$ steradian.

The first point to note is that the charge ratio for neutrino-induced muons is reversed relative to that for atmospheric muons. There are more negative than positive neutrino-induced muons ($`\mu ^+/\mu ^{}\stackrel{<}{}1/2`$), whereas for muons produced in the atmosphere, $`\mu ^+/\mu ^{}1.25`$  This is a consequence of the ratio of cross sections, $`\sigma _\nu /\sigma _{\overline{\nu }}>1`$, and the fact that $`\nu _\mu \mu ^{}`$ while $`\overline{\nu }_\mu \mu ^+`$. In addition, the ratio $`\nu _\mu /\overline{\nu }_\mu `$ increases slowly above its low energy value of unity, first as muon-decay becomes unimportant and at higher energy because of the increasing importance of the channel $`p\mathrm{\Lambda }K^+\nu _\mu \mu ^+`$.

Secondly, the energy spectrum of the external muons is significantly harder than for the contained vertices. This is a consequence of the increase of the muon range with energy. A much higher range of neutrino energies contributes to the external events than to the events with interaction vertex inside the detector. For $`E_\nu >100`$ GeV kaons become the dominant source of neutrinos, with a big contribution from the process $`p\mathrm{\Lambda }K^+\nu _\mu `$. As a result, the charge asymmetry is somewhat larger for external events than for contained vertices.

It is also interesting to look at the angular dependence of neutrino-induced muons with and without oscillations. Fig. 1 shows the zenith angle dependence of the neutrinos that produce muons with contained vertices and upward going neutrino-induced muons originating outside the detector. The strongest effect of oscillations is on the contained vertex events above 1 GeV.

The symmetric shape of the no oscillation case is replaced by an asymmetric distribution with a deficit due to oscillations for upward muons from neutrinos with pathlengths comparable to the radius of the Earth. This effect is in reality obscured by the large angle between the neutrino and muon direction at low energy as shown by the dashed lines in Fig. 1b. The effect of the oscillations is also obvious in the higher energy ($`E>10`$ GeV) sample. The rate of vertically upgoing contained vertex muons is decreased by a factor of $`2`$. The muon–neutrino angle in this case is significantly smaller and does not affect much the oscillation features. The smallest effect is in the case of external events. On one hand, the contribution of high energy, non-oscillating neutrinos is the largest and on the other the downgoing external muon rate is dominated by atmospheric muons, so most of the downward hemisphere is not available as a probe of neutrino oscillations with external events. The muon–neutrino angle for this sample is negligible. The background of atmospheric muons is low enough at the depth of Soudan so that neutrino-induced, external muons can be measured up to $`\mathrm{cos}\theta 0.1`$, about $`6^{}`$ above the horizon. Integrated over all upward-going external events the, oscillations decrease the rate by 22%, which is comparable to the uncertainty in the expected flux.  Instead, the effect of oscillations is visible as a distortion of the angular distribution, as observed at MACRO  and Super-K.

We assume here that neutrinos and anti-neutrinos have identical oscillations properties. Because of the properties of the differential charged current cross sections of neutrinos, however, the relation between $`E_\nu `$ and $`E_\mu `$ is different for $`\nu _\mu `$ and $`\overline{\nu }_\mu `$. As a consequence, when the muon charge ratio is plotted as a function of muon energy for a given angular bin (corresponding to a given pathlength) oscillation features appear in the ratio because the oscillation minima show up at different energies for $`\mu ^+`$ and $`\mu ^{}`$. Figure 2 illustrates this for contained vertices (a) and for external muons (b). The ratios are shown for three bins of $`\mathrm{cos}\theta `$ going from nearly vertical ($`1<\mathrm{cos}\theta <0.9`$) to nearly horizontal ($`0.2<\mathrm{cos}\theta <0.1`$). The solid lines show the charge ratios in the absence of oscillations. The baseline charge ratio increases slightly at high energy and is larger near the vertical because of the increased importance of kaon decay relative to pion decay.

Calculation of external events involves an integral over all contributing neutrino energies taking account of the increase of muon range with energy. The growth of the charge ratio with muon energy is stronger than for contained vertices because of the contribution of higher energy neutrinos. In the oscillation case the variations are smaller than for contained vertex events and do not show the secondary sinusoidal features. For the external events, the peaks are wider and shallower than for contained vertices because of the contribution of a broader range of neutrino energies.

For more insight into the origin of this behavior, we show in Fig. 3 the charge ratio with and without oscillations for the vertically upward bin of zenith angle, for which the pathlength $`L10^4`$ km. The lower panel shows the corresponding survival probability, which is assumed identical for neutrinos and antineutrinos. An approximate, quantitative understanding of the features can be obtained by considering the leading term in the differential neutrino charged current cross sections. For neutrinos

$$\frac{d\sigma (E_\nu )}{dz^{}}\sigma _0\times E_\nu /GeV$$
(1)
and

$$\frac{d\sigma (E_{\overline{\nu }})}{dz^+}\sigma _0\times (z^+)^2\times E_{\overline{\nu }}/GeV$$
(2)
for antineutrinos. Here $`0z=E_\mu /E_\nu 1`$ and $`\sigma _00.8\times 10^{38}`$cm2. Using the approximation 1 we can estimate the relation for neutrinos by evaluating the average $`E_\nu `$ for the distribution

$$\varphi (E_\nu )\frac{d\sigma (E_\nu )}{dE_\mu ^{}}.$$
(3)
Here

$$\varphi (E_\nu )E_\nu ^{(\gamma +1)}$$
(4)
is a power-law approximation for the differential spectrum of neutrinos. Then

$$E_\nu \frac{\gamma }{\gamma 1}E_\mu ^{}.$$
(5)
The corresponding result for antineutrinos is

$$E_{\overline{\nu }}\frac{\gamma +2}{\gamma +1}E_{\mu ^+}.$$
(6)
With $`\gamma 2`$ in the relevant energy range , we have $`E_{\overline{\nu }}/E_{\mu ^+}4/3`$ and $`E_\nu /E_\mu ^{}2`$. Thus the first oscillation minimum at $`24`$ GeV should be reflected at $`18`$ GeV in $`\overline{\nu }_\mu `$ and $`\mu ^+`$ as an increase in the $`\mu ^{}/\mu ^+`$ ratio and at $`12`$ GeV in the opposite channel, reflected as the minimum in the $`\mu ^{}/\mu ^+`$ ratio below 12 GeV. The slight deviations from these numbers in Fig. 3 reflect the breadth and asymmetry of the oscillation features folded with the neutrino spectrum.

Unfortunately, the MINOS detector is not large enough to see the oscillation effect in the charge ratio well, if at all. For example, we estimate that there will be only some 12 $`\mu ^{}`$ and 5 $`\mu ^+`$ events with energy between 10 and 30 GeV in 25 kt-yr in the angular region $`1<\mathrm{cos}\theta <0.5`$, where the charge ratio is high (see Fig. 2). Our estimates are based on the angular distribution of the interacting neutrinos and do not account for the experimental efficiency.

The best way to use all the data is to bin every event by $`L/E`$. Fig. 4 shows the charge ratio in upward going contained vertex events for the standard oscillation parameters as a function of $`L/E`$ for nine different $`\mathrm{cos}\theta `$ bins. The horizontal bin is not included because the fast change of the oscillation length there requires a much more exact calculation. One can easily identify the peaks and valleys in the charge ratio that follow the oscillation structure of the atmospheric neutrino flux. The main feature is at $`L/E`$ of $``$ 600, where the charge ratio can grow to almost twice its baseline value of $`\mu ^{}/\mu ^+2`$. The valley is at $`L/E`$ of $``$ 1200. One can subdivide the $`L/E`$ range in two parts with different charge ratios, 2.36 in the $`L/E`$ from 300 to 900 and 1.84 from 900 to 1500. The expected number of muons for 25 kT.yr are 26.7 $`\mu ^{}`$ & 11.3 $`\mu ^+`$ and 15.5 & 8.4 respectively, still very small statistics.

One should also note that Fig. 4 shows the neutrino pathlength $`L`$ which is not experimentally measured. For some of these events, where the sinusoidal variation happens at energies below 10 GeV, the angular smearing of the neutrino–muon angle will seriously obscure the effect when plotted as $`L_\mu /E_\mu `$.

It is interesting to ask if one could distinguish oscillations from neutrino decay with an observation of the muon charge ratios. The $`L/E<`$ 1500 part of Fig. 4 would not change for a decay scenario that fits the muon disappearance observations. At higher $`L/E`$ values the charge ratio behavior would be much smoother without the secondary and tertiary peaks at $`L/E`$ of about 2000 and 3000. The increase of the charge ratio at these positions are however small and even more difficult to detect.

The reliable detection of the variation of the muon charge ratio would require a much bigger detector. The MONOLITH  detector with mass of 30 kT was proposed for the Gran Sasso Laboratory. If this detector had been built and were operated for five years it would be able to measure the effect at the 3$`\sigma `$ level.

The MINOS detector will be able to measure the total neutrino energy but assume that the muon and neutrino directions coincide. The difference between the neutrino and muon energy spectra as a function of L, as well as the charge ratios, could provide additional observable parameters for the more exact derivation of the oscillation parameters.

The exact manifestation of the effect however has systematic uncertainties related to the uncertainties of the atmospheric flux. These arise from the limited knowledge of the primary cosmic ray spectrum and the production of pions and kaons. The overall uncertainty for $`E_\nu 10`$ GeV is estimated in Ref.  as $`\pm 25`$%.

The uncertainty in the ratio $`\nu _\mu /\overline{\nu }_\mu `$ should be significantly less than the uncertainty in the magnitude of the flux because the normalization of the primary cosmic ray spectrum cancels. The largest remaining source of uncertainty in the ratio is from production of charged pions and kaons, especially in the forward fragmentation region, as reflected by the spectrum weighted moments, $`Z_{p\pi ^+}`$, $`Z_{p\pi ^{}}`$, $`Z_{pK^+}`$ and $`Z_{pK^{}}`$. For pions and especially for kaons, the positive channel dominates, and kaons become relatively more important at high energy.

We can estimate the uncertainty in the $`\nu _\mu /\overline{\nu }_\mu `$ ratio by combining in quadrature the estimates in Ref.  of uncertainty in the flux of $`\nu _\mu +\overline{\nu }_\mu `$ from each of the four channels independently. This leads to an estimate of $`\pm 8`$% below $`10`$ GeV and $`\pm 9`$% for $`10<E_\nu <100`$ GeV. Analysis of data from forthcoming hadron production experiments with CERN  and Fermilab  should lead to a reduction of this estimate.

The effect we described above should also be detectable in a slightly different form in the long baseline oscillation experiment with the NuMI neutrino beam. The experimental statistics would be fully sufficient and the exact manifestation would strongly depend on the beam energy spectrum, purity, and composition. All of these three parameters are currently still at the design stage.

Acknowledgments. We are grateful for helpful discussions with Doug Michael and Teresa Montaruli. This work is supported in part by the U.S. Dept. of Energy under Grant No. DE-FG02-91ER40626.


format: text

text:
# Stacking Clusters in the ROSAT All-Sky Survey

## 1 Introduction

With moderately deep, wide-area imaging surveys in the optical or near infrared it is now possible to detect large samples of galaxy clusters. Dalcanton (1996) proposed that clusters could be detected as surface brightness enhancements even when all but a few of their galaxies are too faint to be detected individually. Her suggested procedure consists of identifying and removing stars and galaxies from carefully flat-fielded images, smoothing the residual with a kernel matched to the core size of clusters, and searching for significant peaks in the resulting smoothed map. Gonzalez et al. (2001) successfully constructed the Las Campanas Distant Cluster Survey (LCDCS) by applying this technique to drift-scan data taken with the Las Campanas Great Circle Camera (Zaritsky, Schectman & Bredthauer 1996). They mapped well over 100 square degrees and constructed a catalog of 1073 groups and clusters. The estimated redshift limits of the catalog range from $`0.3`$ for groups to $`0.9`$ for massive galaxy clusters.

The high intrinsic uniformity of drift-scan surveys like the LCDCS makes them ideal for applying Dalcanton’s cluster-detection technique. In a theoretical study, Bartelmann & White (2002) showed that massive galaxy clusters should be detectable in the Sloan Digital Sky Survey (SDSS) out to redshifts of $`1.2`$ if data in the $`r^{}`$, $`i^{}`$ and $`z^{}`$ bands are summed. For the final projected SDSS survey area of $`10^4`$ square degrees, $`10^5`$ galaxy clusters should be detectable at the 5-$`\sigma `$ level, and $`10\%`$ of those are expected to be at redshifts $`0.8`$.

Relatively little is known about the X-ray emission of clusters at redshifts beyond $`0.5`$ despite numerous cluster surveys based on X-ray data. The main reason for this is the steep decrease with redshift of the observed X-ray flux, which implies that at $`z>0.5`$ individual massive clusters produce at most a few photons in surveys like the ROSAT All-Sky Survey (RASS; Snowden & Schmitt 1990). Detections of distant galaxy clusters from the X-ray data alone are limited to very luminous systems which can be detected in the restricted areas where deeper observations are available.

The upcoming availability of large cluster surveys in wavebands other than the X-ray regime allows a reversal of the traditional X-ray survey strategy. Rather than identifying clusters in the X-ray data, it becomes possible to stack X-ray survey data for a large number of fields where clusters are already known from other surveys. The low background count rate at X-ray wavelengths makes this an efficient technique for detecting the summed emission from a large stack of clusters.

In this paper we investigate the prospects for using the RASS to detect X-rays from suitable samples of clusters identified in the SDSS data. In Sect. 2 we describe our model for the cluster population. This is based closely on the properties of nearby clusters and specifies the cluster distribution in mass, redshift, X-ray temperature and luminosity. In Sect. 3 we convert cluster X-ray luminosities to count distributions expected in the ROSAT All-Sky Survey. Based on these, we calculate in Sect. 4 the expected signal-to-noise both for the detection of mean cluster emission and for estimates of mean cluster temperature. Sect. 5 summarises and discusses our conclusions.

## 2 Model specifications

### 2.1 Cosmology

Much evidence suggests that the universe is spatially flat with low nonrelativistic matter density $`\mathrm{\Omega }_0`$. Baryons make up only a small fraction of this matter; the rest is dark, presumably consisting of some massive, weakly interacting particle. A cosmological constant $`\mathrm{\Omega }_\mathrm{\Lambda }`$ or an equivalent “quintessence” field contributes the remaining energy density. For definiteness, we assume $`\mathrm{\Omega }_0=0.3`$, $`\mathrm{\Omega }_\mathrm{\Lambda }=0.7`$ and $`h=0.7`$

We assume structure to form from an initially Gaussian density fluctuation field $`\delta `$ with statistical properties specified by its linear power spectrum, for which we adopt the CDM form given by Bardeen et al. (1986) with primordial spectral index $`n=1`$. The only remaining free parameter is then the normalisation of the initial fluctuation field which we take as $`\sigma _8=0.9`$. This value was originally estimated based on the observed local abundance of galaxy clusters (White, Efstathiou & Frenk 1993; Eke, Cole & Frenk 1996; Viana & Liddle 1996; Pierpaoli, Scott & White 2001; Evrard et al 2002) but some recent analyses favour smaller values (Reiprich & Böhringer 2002; Viana, Nichol & Liddle 2002; Lahav et al. 2002). We will show results for $`\sigma _8=0.9\pm 0.1`$.

### 2.2 Cluster population

Haloes form from Gaussian primordial density fluctuations through gravitational collapse. Press & Schechter (1974) first derived an approximate formula for the mass distribution of haloes as a function of redshift $`z`$. This has recently been modified by Sheth, Mo & Tormen (2001) and Sheth & Tormen (2002) based on an ellipsoidal rather than a spherical model for collapse. They give the differential comoving number density of haloes as

$$n(M,z)\mathrm{d}M=A\sqrt{\frac{2}{\pi }}\left(1+\frac{1}{\nu ^{2q}}\right)\frac{\overline{\rho }}{M}\frac{\mathrm{d}\nu }{\mathrm{d}M}\mathrm{exp}\left(\frac{\nu ^2}{2}\right)\mathrm{d}M,$$
(1)
where $`\nu =\sqrt{a}\delta _\mathrm{c}\sigma ^1(M,z)`$ defines the linear amplitude required for collapse of a density fluctuation and $`\overline{\rho }`$ is the mean cosmic density today. $`\sigma (M,z)`$ in this definition is equal to $`\sigma _0(M)D_+(z)`$, where $`\sigma _0(M)`$ is the present *rms* fluctuation in the dark matter density contrast within spheres containing the mean mass $`M`$, and $`D_+(z)`$ (with $`D_+(0)=1`$) is the growth factor for the linear growing mode (cf. Carroll, Press & Turner 1992). The linear density contrast required for collapse $`\delta _\mathrm{c}`$ depends weakly on cosmology; for the $`\mathrm{\Lambda }`$CDM model we have chosen $`\delta _\mathrm{c}=1.673`$ (e.g. Łokas & Hoffman 2001). The parameters $`A`$, $`a`$ and $`q`$ are constants; the original Press-Schechter formula is obtained from (1) by putting $`A=0.5`$, $`a=1`$ and $`q=0`$. This mass function, with $`A=0.322`$, $`a=0.707`$ and $`q=0.3`$, has been shown to fit high resolution numerical simulations of structure growth in a wide range of cosmologies, provided the halo mass is defined at fixed density contrast relative to the cosmic mean density (Jenkins et al. 2001).

Next, we need to know the X-ray luminosity of a cluster of mass $`M`$. We adopt the observed relation between cluster temperature $`T`$ and bolometric X-ray luminosity $`L_X`$

$$L_X=10^{44}\mathrm{erg}\mathrm{s}^1\left(\frac{kT}{1.66\mathrm{keV}}\right)^{2.331},$$
(2)
as derived by Allen & Fabian (1998). Observations suggest that there is little evolution in the $`L_XT`$ relation out to redshifts $`z0.4`$ (e.g. Mushotzky & Scharf 1997; Allen & Fabian 1998; Reichart, Castander & Nichol 1999). Lacking any reliable information about evolution to higher redshifts, we assume (2) to hold at all redshifts. This, of course, is a major uncertainty of our study.

According to the virial theorem, a halo of mass $`M`$ in equilibrium at redshift $`z`$ with a structure similar to observed clusters should have a mean temperature given by

$$kT=4.88\mathrm{keV}\left[\frac{Mh(z)}{10^{15}M_{}}\right]^{2/3},$$
(3)
where $`h(z)`$ is the Hubble constant at redshift $`z`$ in units of $`100\mathrm{km}\mathrm{s}^1\mathrm{Mpc}^1`$ and, in contrast to Eq. (1), $`M`$ is here defined as the mass interior to a sphere with mean overdensity $`200`$ times the *critical* value at redshift $`z`$. Recall that we assume $`h(0)=0.7`$ throughout our analysis. The constant in this relation is taken from the cluster simulations of Mathiesen & Evrard (2001; their Table 1) and is appropriate for specifying the temperature of the best fit single temperature model for the X-ray spectrum over the mass and redshift ranges of interest. When necessary, we use an NFW model of concentration parameter 5 to convert between cluster masses defined at different overdensities.

### 2.3 X-ray emission

We assume that clusters emit X-rays through thermal radiation according to a Raymond-Smith plasma model (Raymond & Smith 1977). Apart from cluster temperature and redshift, the model has two free parameters, the metal abundance and an overall normalisation corresponding to the total X-ray luminosity. We fix the metal abundance to $`Z=0.3Z_{}`$ at all $`z`$ in agreement with the observed abundances of local clusters (e.g. Fukazawa et al. 1998). The results of Schindler (1999) suggest little evolution towards higher redshift and the final count rates we derive depend only very weakly on metallicity. Thus neglecting any dependence on redshift does not induce significant uncertainty.

Let $`F_\nu (T,z)d\nu `$ be the total X-ray luminosity emitted in the spectral interval $`[\nu ,\nu +d\nu ]`$ by a cluster of temperature $`T`$ at redshift $`z`$. If the cluster is observed in an energy band bounded by $`E_1`$ and $`E_2>E_1`$, only a fraction $`f`$ of its bolometric flux is included in the bandpass, where

$$f=_{E_1(1+z)}^{E_2(1+z)}F_\nu (T,z)d\nu \left[_0^{\mathrm{}}F_\nu (T,z)d\nu \right]^1.$$
(4)
Thus the band-limited flux $`S_X`$ is related to the bolometric X-ray luminosity through

$$S_X=\frac{fL_X}{4\pi D_\mathrm{L}^2(z)},$$
(5)
where $`D_\mathrm{L}(z)`$ is the luminosity distance from the observer to redshift $`z`$. Note that this flux must still be modified to account for foreground absorption.

We use version 11.1 of the *xspec* software package (Arnaud 1996) to tabulate $`f`$ for an observing band between $`0.5`$ and $`2.4`$keV, for cluster temperatures between $`0.5`$ and $`12`$keV, and for redshifts between 0 and 2. Interpolating within this table and using Eqs. (2), (3) and (5), we can convert cluster masses to cluster temperatures, X-ray luminosities, and finally to unabsorbed fluxes in the observed energy range.

The azimuthally averaged X-ray surface brightness profile $`\mathrm{\Sigma }(\theta )`$ of galaxy clusters is often modelled using the so-called beta profile (Cavaliere & Fusco-Femiano 1978),

$$\mathrm{\Sigma }(\theta )=\mathrm{\Sigma }_0\left[1+\left(\frac{\theta }{\theta _\mathrm{c}}\right)^2\right]^{(3\beta 1/2)},$$
(6)
where $`\theta _\mathrm{c}`$ is an angular core radius, and the amplitude $`\mathrm{\Sigma }_0`$ is chosen to produce the required X-ray flux $`S_X`$. Based on observation, we choose $`\beta =2/3`$ (e.g. Mohr, Mathiesen & Evrard 1999). For the linear core radius $`r_\mathrm{c}`$, we adopt the relation

$$r_\mathrm{c}=125\mathrm{kpc}h^1\left(\frac{L_X}{5\times 10^{44}\mathrm{erg}\mathrm{s}^1}\right)^{0.2},$$
(7)
where $`L_X`$ is the X-ray luminosity between $`0.5`$ and $`2.4`$keV. This relation is a fair representation of at least some clusters with luminosities within $`10^{4345}\mathrm{erg}\mathrm{s}^1`$ (Jones et al. 1998). Following Vikhlinin et al. (1998), we assume that (7) does not evolve with redshift. The angular core radius is then $`\theta _\mathrm{c}=r_\mathrm{c}D^1(z)`$, where $`D(z)`$ is the angular-diameter distance. In fact, Eq. (6) is a poor fit to the profiles of many clusters, particularly those with strong apparent cooling flows. This is not, however, of any great consequence for our modelling since the RASS does not, in any case, resolve the inner regions of most clusters.

Having fixed $`\beta `$, $`S_X`$ and the angular core radius $`\theta _\mathrm{c}`$, the beta profile is normalised by

$$\mathrm{\Sigma }_0=\frac{S_X}{2\pi \theta _\mathrm{c}^2}.$$
(8)
## 3 Halo detection

### 3.1 Point-spread function

The point-spread function $`f(\theta ;E,\varphi )`$ of the ROSAT-PSPC had three components, a Gaussian kernel, Lorentzian wings, and a component which falls off exponentially with the angular separation $`\theta `$ from the centre of the image (Hasinger et al. 1995). The parameters for these components generally depend not only on photon energy $`E`$, but also on $`\varphi `$, the off-axis angle of the source.

The width of the PSPC point-spread function can be characterised by the effective solid angle $`\delta \mathrm{\Omega }(E,\varphi )`$ covered,

$$\delta \mathrm{\Omega }(E,\varphi )=2\pi _0^{\mathrm{}}\theta d\theta f(\theta ,E,\varphi ),$$
(9)
and we can define an effective radius $`\theta _{\mathrm{eff}}(E,\varphi )`$ by

$$\theta _{\mathrm{eff}}(E,\varphi )=\left(\frac{\delta \mathrm{\Omega }(E,\varphi )}{\pi }\right)^{1/2}.$$
(10)
The effective radii for six different off-axis angles between $`10^{}`$ and $`60^{}`$ are shown as functions of photon energy in Fig. 1.

The field-of-view of the PSPC was large, with a radius of approximately $`60^{}`$. Since a given point on the sky was scanned at many different off-axis angles during the All-Sky Survey, the appropriate point-spread function for the ROSAT All-Sky Survey at a given photon energy is an area-weighted average of $`f(\theta ;E,\varphi )`$ over the field-of-view,

$$\overline{f}(\theta ,E)=\frac{2}{(60^{})^2}_0^{60^{}}\varphi d\varphi f(\theta ,E,\varphi ).$$
(11)
Figure 2 shows the result for four different photon energies between $`0.5`$ and $`2.0`$keV.

Figure 2 shows that the point-spread function, averaged over off-axis angles, falls to $`10\%`$ of its peak value within 2–3 arc minutes with little dependence on photon energy. Figure 1 confirms this weak dependence on photon energy, and illustrates the strong dependence of effective PSF radius on off-axis angle. While $`\theta _{\mathrm{eff}}`$ is below $`0.5^{}`$ for nearly on-axis photons, it increases above $`1^{}`$ for photons coming from the edge of the field-of-view.

The effective radius of the averaged point-spread function $`\overline{f}(\theta ,E)`$ can finally be averaged over photon energies to obtain an average effective radius valid for the hard band of the All-Sky Survey. Performing this average and weighting the photon energies with the effective detector area as a function of $`E`$, we find $`\overline{\theta }_{\mathrm{eff}}=2.1^{}`$.

### 3.2 Converting fluxes to count rates

We now need to estimate the signal expected in the All-Sky Survey from a cluster with unabsorbed flux $`S_X`$ and temperature $`T`$ at redshift $`z`$. To do this, we first modify the fluxes $`S_X`$ calculated using Eq. (5) to allow for absorption by foreground neutral hydrogen. We assume a constant hydrogen column of $`4\times 10^{20}\mathrm{cm}^2`$, which is typical for the high galactic latitudes covered by the SDSS (e.g. Dickey & Lockman 1990). We convert the absorbed fluxes to PSPC count rates, using the *fakeit* task of the *xspec* package with the PSPC response matrix111electronically provided at ftp://ftp.xray.mpe.mpg.de/rosat/calibration/data.

In practice, we compute a two-dimensional table containing PSPC count rates in the energy range between $`0.5`$ and $`2`$keV for *absorbed* Raymond-Smith spectra of a fixed *unabsorbed* flux normalisation and for cluster temperatures between $`0.5`$ and $`12`$keV and redshifts between 0 and 2. Fluxes determined from (5) can then be converted to absorbed count rates by interpolating within this table.

### 3.3 Exposure times; background level

The effective exposure time in the All-Sky Survey varies across the sky because of the ROSAT scanning strategy. It is highest near the ecliptic poles and lowest close to the ecliptic plane (cf. Snowden et al. 1995). Maps for the exposure time and the background count rates were downloaded from the ROSAT All-Sky Survey web page222http://www.xray.mpe.mpg.de/cgi-bin/rosat/rosat-survey/. The left panel in Fig. 3 shows the cumulative exposure-time distribution for the complete All-Sky Survey (dashed curve), and for the area around the Northern Galactic cap covered by the Sloan Digital Sky Survey. The median exposure times are marked by vertical lines.

The effective exposure times on the whole sphere and on the SDSS area are only marginally different. For the SDSS area, we find a median value

$$t_{\mathrm{exp}}=414\mathrm{s}.$$
(12)
Similarly, the background level is anisotropic across the sky. The right panel in Fig. 3 shows the cumulative distributions of the background count rate in the All-Sky Survey for the whole sky (dashed line) and for the SDSS area (solid line).

The background count rate within the SDSS area is noticeably lower than on the whole sky; its median value is

$$B=0.94\mathrm{s}^1\mathrm{deg}^2=2.61\times 10^4\mathrm{s}^1\mathrm{arcmin}^2.$$
(13)
## 4 Results

Figure 4 shows photon-count contours in the plane spanned by cluster mass and redshift. On a grid covering that plane, we compute temperature, luminosity, flux, and count rate as described in the previous section. We then multiply the count rate by the median exposure time in the SDSS area, averaged over photon energies in the $`0.52.4`$keV band.

The contours are logarithmically spaced by $`0.25`$ dex between 0.1 and 100 counts (upper and lower solid curves, respectively). They appear jagged because a substantial fraction of the X-ray flux is contributed by metal lines which move in and out of the observed energy band as the redshift changes. The contours become smooth if the metal abundance is set to zero. From this plot one can see, for example, that the redshift limit below which individual clusters contribute more than ten photons to the All-Sky Survey increases from $`z_{\mathrm{max}}0.1`$ at $`M=10^{14}h^1M_{}`$ to $`z_{\mathrm{max}}0.8`$ at $`M=10^{15}h^1M_{}`$. The dashed curve shows the redshift limit for detection of clusters as 5-$`\sigma `$ surface brightness enhancements in the combined $`r^{}`$, $`i^{}`$ and $`z^{}`$ data of the SDSS (Bartelmann & White 2002). Clearly the SDSS should produce cluster catalogues which are much deeper at all masses than those that can be made from the RASS.

Figure 4 illustrates that only 0.3 photons per cluster are expected for clusters of $`M10^{14}h^1M_{}`$ at redshift $`z0.8`$. The number of such clusters expected in the SDSS is so large, however, that it should be possible to determine their mean X-ray properties by stacking data for many fields. This is true even if the mass-redshift plane is divided into relatively narrow bins. We now investigate this in more detail.

The background level of the All-Sky Survey is quite low, of order $`1\mathrm{s}^1\mathrm{deg}^2`$ which translates to approximately $`0.8`$ total counts per resolution element within the median exposure time of the survey. The background will nevertheless dominate the noise in a stacked image of distant clusters. Let $`B`$ be the mean surface density of background photons in a single image, and $`C(M,z)`$ be the expected number of photons from a single cluster of mass $`M`$ at redshift $`z`$. Let $`p(\theta )`$ be the expected surface density of these cluster photons as a function of angular distance $`\theta `$ from cluster centre. $`p(\theta )`$ is given by a convolution of the mean cluster surface brightness profile \[Eq. (6)\] with the point-spread-function of the survey (Fig. 2) and we normalise it so that $`p(\theta )\mathrm{\hspace{0.17em}2}\pi \theta d\theta =1`$. In practice for distant clusters the *p.s.f.* is much broader than the cluster image so that $`p(\theta )`$ is proportional to the *p.s.f.* itself.

For a stack of $`N`$ cluster fields the surface density of the background is $`NB`$ and the expected surface density profile is $`NCp(\theta )`$. Assuming Poisson photon statistics, the optimal estimator of the cluster signal is then:

$$\stackrel{~}{NC}=w(\theta )[O(\theta )B]2\pi \theta d\theta ,$$
(14)
where $`2\pi O(\theta )\theta \mathrm{d}\theta `$ is the observed photon count in an annulus width $`\mathrm{d}\theta `$, and the filter function $`w`$, normalised so that $`w(\theta )p(\theta )\mathrm{\hspace{0.17em}2}\pi \theta d\theta =1`$, is given by

$$w(\theta )=\frac{p(\theta )}{p(\theta )+B/C}\left[\frac{p^22\pi \theta \mathrm{d}\theta }{p+B/C}\right]^1$$
(15)
Clearly the expectation value of the estimator of equation (14) is just $`NC`$ while its variance is

$$\mathrm{Var}(\stackrel{~}{NC})=NCw^2(\theta )p(\theta )\mathrm{\hspace{0.17em}2}\pi \theta d\theta .$$
(16)
Thus the expected signal-to-noise for detecting the stacked cluster is

$$\left(\frac{S}{N}\right)=(NC)^{1/2}\left[\frac{p^2(\theta )\mathrm{\hspace{0.17em}2}\pi \theta \mathrm{d}\theta }{p(\theta )+B/C}\right]^{1/2}.$$
(17)
If clusters are individually well above background ($`Cp(\theta )B`$ over most of the broadened image) this gives the obvious result, $`(S/N)(NC)^{1/2}`$ for the stack. When background dominates ($`Cp(0)B`$) the corresponding result is $`(S/N)NC/[NBp^2(\theta )\mathrm{\hspace{0.17em}2}\pi \theta d\theta ]^{1/2}`$. In both cases the signal-to-noise of the detection grows as $`N^{1/2}`$ for the stacked image. Figure 5 shows the number of cluster fields required for a 5-$`\sigma `$ detection in the stacked image as a function of cluster mass and redshift.

Contours are shown for $`N=1`$ (lower solid curve), $`N=10`$, and $`N=100`$ (upper solid curve). The figure shows that it takes 100 stacked cluster fields to obtain a 5-$`\sigma `$ detection of clusters with $`M10^{14}h^1M_{}`$ at redshift $`z0.4`$, but the contours rise steeply enough that with the same number of stacked fields one reaches redshifts above unity for cluster masses $`M3\times 10^{14}h^1M_{}`$. As in Fig. 4, the dashed line shows the upper redshift limit expected for 5-$`\sigma `$ cluster detection in the combined $`r^{}`$, $`i^{}`$ and $`z^{}`$ bands of the SDSS.

We now have to compare the number of cluster fields needed to achieve a high signal-to-noise ratio with All-Sky Survey data to the number of clusters we can expect to be available. The idea is to select fields around clusters which are known from other data, and we continue to take the SDSS as an example. We therefore ask how many clusters can be expected in the SDSS data.

To give specific examples, we select two redshift intervals of width $`\mathrm{\Delta }z=0.1`$ each, one over $`0.6z0.7`$ and the other over $`0.9z1.0`$. Our previous work has obtained the expected redshift limit $`z_{\mathrm{lim}}(M)`$ as a function of cluster mass for detection in SDSS data (Bartelmann & White 2002). For a 5-$`\sigma `$ detection in the combined $`r^{}`$, $`i^{}`$ and $`z^{}`$ bands, it is indicated by a dashed line in Figs. 4 and 5. For each redshift interval, we thus know the completeness limit in cluster mass, i.e. the lowest cluster mass $`M_{\mathrm{lim}}`$ above which clusters in that interval are expected to be detectable. For the lower and upper redshift intervals defined above, we obtain $`M_{\mathrm{lim}}=3.9\times 10^{13}h^1M_{}`$ and $`M_{\mathrm{lim}}=2.0\times 10^{14}h^1M_{}`$ respectively. For each interval we then define a series of mass bins between $`M_{\mathrm{lim}}`$ and $`10^{15}h^1M_{}`$ such that $`\mathrm{\Delta }\mathrm{ln}M0.3`$.

The number of clusters in the redshift interval $`[z_i,z_i+\mathrm{\Delta }z]`$ per mass bin $`[M_j,M_{j+1}]`$ is obtained through an integral of the mass function (1) multiplied by the comoving cosmic volume,

$$\mathrm{\Delta }N_{ij}=_{z_i}^{z_i+\mathrm{\Delta }z}dz_{M_j}^{M_{j+1}}dMn(M,z)\left|\frac{\mathrm{d}V}{\mathrm{d}z}\right|(1+z)^3.$$
(18)
The volume per unit redshift is

$$\left|\frac{\mathrm{d}V}{\mathrm{d}z}\right|=\pi D^2(z)\left|\frac{\mathrm{d}D_{\mathrm{prop}}}{\mathrm{d}z}\right|,$$
(19)
where $`D`$ is the angular diameter distance and $`D_{\mathrm{prop}}`$ the proper distance. The factor $`\pi `$ instead of $`4\pi `$ accounts for the fact that the SDSS only covers a quarter of the sky. Figure 6 shows the resulting cluster numbers $`\mathrm{\Delta }N_{ij}`$ and the total photon numbers $`\mathrm{\Delta }C_{ij}`$ expected from these clusters. The solid and dotted curves show results for the lower and upper redshift bins, respectively. In order to illustrate the sensitivity of the results to $`\sigma _8`$, the error bars mark the range obtained for $`\sigma _8=0.9\pm 0.1`$. The curves showing the total photon counts received in each mass bin are flatter than those showing the total cluster number because clusters with higher mass are more X-ray luminous.

The figure shows that, even with relatively fine mass binning, more than $`10^4`$ clusters should be detectable per mass bin below $`10^{14}h^1M_{}`$ in the lower redshift interval $`0.6z0.7`$. For comparison, Fig. 5 shows that several hundred stacked cluster fields are already sufficient for a 5-$`\sigma `$ X-ray detection in the RASS. Similarly, more than $`10^3`$ clusters are expected per mass bin below $`4\times 10^{14}h^1M_{}`$ at higher redshifts, $`0.9z1.0`$, where fewer than $`100`$ cluster fields need to be stacked for an X-ray detection. A useful way to quantify these numbers is by calculating the expected signal-to-noise ratio in a stack of all the cluster fields in each mass bin and in each of our two redshift intervals. The results are shown in Fig. 7.

At the lower redshift the signal-to-noise ratio starts above $`40`$ near $`4\times 10^{13}h^1M_{}`$, where the contribution of metal lines to the flux is high. With increasing mass, the line contribution decreases and $`S/N`$ has a shallow minimum near $`10^{14}h^1M_{}`$. Increasing continuum emission causes a broad peak at $`40`$ centred on $`3\times 10^{14}h^1M_{}`$. It then decreases slowly towards higher masses. The drop-off results from from the low cluster number at the high-mass end. If we set the metal abundance to zero, the low X-ray flux at the low-mass end makes the signal-to-noise drop to $`20`$ near $`4\times 10^{13}h^1M_{}`$. Even in the upper redshift interval, the signal-to-noise ratio is above 10, rising to $`20`$ in the lowest mass bin. These results are, however, very sensitive to $`\sigma _8`$. Near $`10^{15}h^1M_{}`$ in the upper redshift interval, the signal-to-noise ratio varies between $`5`$ and $`20`$ as $`\sigma _8`$ is increased from $`0.8`$ to $`1.0`$.

The high signal-to-noise ratio even for high-redshift clusters encourages us to investigate whether it will be possible to estimate cluster temperatures from hardness ratios. We introduce two energy bands, one with $`0.5E/\mathrm{keV}<1`$ and the second with $`1E/\mathrm{keV}2`$. The counts $`C_{1,2}`$ in these two bands determine the hardness ratio

$$=\frac{\text{hard counts}}{\text{soft counts}}=\frac{C_2}{C_1}.$$
(20)
We use *xspec* to compute the hardness ratio $`(T,z)`$ expected for RASS data for clusters with temperature $`T`$ at redshift $`z`$. For clusters of mass $`M`$ at redshift $`z`$, the uncertainty in the temperature measurement is then

$$\mathrm{\Delta }T(M,z)=\left(\frac{}{T}[T(M),z]\right)^1\mathrm{\Delta },$$
(21)
where the uncertainty $`\mathrm{\Delta }`$ of the measured hardness ratio (20) is determined by the count statistics. The boundaries of the energy bands were chosen so that $``$ is typically of order unity in the mass and redshift ranges considered here. The signal-to-noise ratio of the hardness ratio $`/\mathrm{\Delta }`$ is $`10`$ for all cluster mass bins in the redshift interval $`0.6z0.7`$, and is $`8`$ for the bins in the redshift interval $`0.9z1.0`$. The derivative of $``$ with respect to $`T`$ is $`0.8`$ for $`T1`$keV and falls to $`0.1`$ the highest temperatures. As a result temperature determinations should be most accurate for clusters with $`M10^{14}h^1M_{}`$; at lower masses, line emission in the low-energy band dominates and the uncertainty $`\mathrm{\Delta }`$ increases because of poor photon statistics in the high-energy band. We show $`T`$ and $`\mathrm{\Delta }T/T`$ in Fig. 8 for the same mass bins and redshift intervals used previously. For comparison, the plot also gives the mean cluster temperature expected as a function of mass in each redshift interval. Note that both $`T`$ and $`\mathrm{\Delta }T/T`$ are emitted rather than observed values.

Figure 8 shows that the relative uncertainty in the mean temperature of the clusters in each mass bin is remarkably small for $`0.6z0.7`$. For cluster masses $`>10^{14}h^1M_{}`$ it is $`\mathrm{\Delta }T/T0.15`$. Over the mass range $`10^{14}10^{15}h^1M_{}`$, it appears that a $`>10\sigma `$ measurement of cluster temperature should be possible. As in Figs. 6 and 7, the error bars in Fig. 8 indicate the range obtained by varying the power-spectrum normalisation $`\sigma _8`$ by $`\pm 0.1`$. For clusters in the high-redshift band, $`0.9z1.0`$, the relative temperature uncertainty increases both because of count statistics and because of decreasing sensitivity of $``$ to $`T`$. Despite this, temperature measurements at $`3`$ to $`10\sigma `$ should be possible. Note that a careful maximum likelihood measurement of $`T`$ would give results with somewhat higher significance than the simple hardness ratio approach we have adopted here.

## 5 Discussion

Ongoing and planned wide-area surveys will detect tens of thousands of galaxy clusters out to redshifts near and above unity. For example, searching for surface-brightness enhancements in a smoothed stack of the $`r^{}`$-, $`i^{}`$\- and $`z^{}`$-band data of the Sloan Digital Sky Survey should allow clusters of $`5\times 10^{13}h^1M_{}`$ to be detected out to $`z0.7`$, while $`z>1`$ is reached for masses above $`3\times 10^{14}h^1M_{}`$ (Bartelmann & White 2002).

We have investigated here whether existing X-ray data can be used to measure the X-ray emission of these clusters by stacking sufficiently many fields. We assume clusters to be distributed in mass and redshift as given by the numerical results of Jenkins et al. (2001). Their temperatures are taken to be proportional to $`[Mh(z)]^{2/3}`$, with the normalisation taken from the N-body/SPH simulations of Mathiesen & Evrard (2001). We adopt the observed low-redshift relation between bolometric X-ray luminosity and temperature, and we assume that it holds at all redshifts. We model cluster X-ray surface-brightness profiles by a beta profile, although this has little effect on our results because most distant clusters are not resolved in the RASS. We convert the bolometric X-ray luminosity into a count rate using the *xspec* software, assuming a Raymond-Smith plasma model with a metallicity of $`0.3`$ solar and a foreground neutral-hydrogen column of $`4\times 10^{20}\mathrm{cm}^2`$.

The only suitable survey of the X-ray sky is the ROSAT All-Sky Survey (RASS). With its median exposure time of approximately $`415`$ seconds and its effective detector area of $`230\mathrm{cm}^2`$, it detected $`10`$ photons from a cluster of mass $`10^{14}h^1M_{}`$ at $`z0.1`$, and only about one photon from a similar cluster at $`z0.5`$. Since the effective angular resolution of the RASS is $`2^{}`$, cluster emission is typically spread over an effective solid angle of $`14`$ square arcminutes. Due to the low background of the PSPC detector, only $`1.5`$ background photons are expected within this solid angle during the median RASS exposure time. This corresponds to the number of photons expected from a cluster with mass $`M10^{14}h^1M_{}`$ at redshift $`z0.35`$, or with mass $`M4\times 10^{14}h^1M_{}`$ at $`z1`$. Thus stacked cluster fields are background dominated at lower mass or higher redshift than this.

Requiring a signal-to-noise exceeding 5, we find that 100 fields must be stacked to get a significant detection of clusters with $`M10^{14}h^1M_{}`$ at $`z0.4`$, or with $`M3\times 10^{14}h^1M_{}`$ at $`z1.0`$. A stack of ten cluster fields should give a 5-$`\sigma `$ detection of massive clusters with $`M10^{15}h^1M_{}`$ at $`z1.1`$, should any such exist.

The number of clusters expected in wide-field surveys like the SDSS is enormous and allows the detection of X-ray emission from even fairly low-mass clusters out to surprisingly high redshift. In the redshift interval between $`0.6`$ and $`0.7`$, the surface-brightness technique of Dalcanton (1996) should detect clusters in the SDSS data down to a mass limit of $`3.9\times 10^{13}h^1M_{}`$. If we bin the clusters by mass into logarithmic bins with width $`\mathrm{\Delta }\mathrm{ln}M=0.3`$, the signal-to-noise ratio for the X-ray detection exceeds 35 near $`10^{14}h^1M_{}`$, rises above 40 near $`3\times 10^{14}h^1M_{}`$ and drops to $`25`$ at $`10^{15}h^1M_{}`$. In the interval between redshifts $`0.9`$ and $`1.0`$, the mass completeness limit for SDSS cluster detection increases to $`2\times 10^{14}h^1M_{}`$, but X-ray detections are still possible with signal-to-noise ratios above 10 if clusters are binned by mass as described.

We have also shown that the signal-to-noise ratio of the stacked cluster images is high enough to divide the photons into two energy bands, $`E[0.5,1]`$ and $`E[1,2]`$, and to estimate cluster temperatures from the count ratio. In particular, for clusters with $`0.6z0.7`$ and masses $`>10^{14}h^1M_{}`$, the hardness ratio changes with cluster temperature sufficiently strongly for mean cluster temperatures to be determined with a typical relative uncertainty of $`\mathrm{\Delta }T/T15\%`$.

Of course, these results depend on the modelling assumptions we have made. Their sensitivity to changes in the power-spectrum normalisation $`\sigma _8`$ is shown in Figs. 6, 7 and 8, where the error bars bracket results obtained adopting $`\sigma _8=0.9\pm 0.1`$. Other critical assumptions are that the relation between bolometric X-ray luminosity and temperature is independent of redshift, and that the cluster temperature scales with cluster mass as given by simulations. Our assumptions about cluster X-ray profiles are less critical because of the low angular resolution of the RASS.

Using photometric redshifts for brightest cluster members, it should be possible to determine redshifts for SDSS clusters with an accuracy of $`\mathrm{\Delta }z0.05`$. On the other hand, at best very rough estimates of cluster mass can be obtained from the optical data. The optically selected clusters in a given redshift interval can be binned by magnitude, and the study suggested here will then give relations between optical luminosity and mean X-ray luminosity and temperature. The latter can then be used to give an improved estimate of mean cluster mass.

Wide-area surveys in the microwave regime will be carried out in the near future which will detect of order one cluster per square degree trough the thermal Sunyaev-Zel’dovich effect. The *Planck* satellite, for instance, due for launch in early 2007, is expected to detect of order $`30000`$ galaxy clusters on the sky outside the Galactic plane, approximately 10% of which will be at redshifts beyond $`0.5`$. Stacking these clusters in the same way as described here, and combining their total integrated Compton-$`y`$ parameter with their X-ray emission, will allow their total baryonic mass and perhaps their temperatures to be constrained.


text:
# Cellular automata and communication complexity

## 1 Introduction

The model of cellular automata was invented in the 1950’s mostly by von Neumann as a tool to study self-reproduction (see \[vN67\]). It was then meant both as a tool to model real life dynamical systems and as a model of an actual computer. Since then cellular automata are studied theoretically either as a model of massive parallel computation or as a discrete dynamical system. They are also studied experimentally either as a tool to model complex natural systems ranging from economy, geology, biology, chemistry, sociology, etc or as a framework to do simulations. For a general introduction, see \[DM99\].

A cellular automaton is an infinite and discrete grid of cells. Each cell contains at every time step a particular state from a finite set. The cell state obeys a local rule, mapping its state and the state of the neighborhood to a new cell state. This rule is applied uniformly and synchronously to all cells of the grid. So the local rule generates a global mapping on grid configurations, which can be quite complex. For example, some simple local rules give computation universal cellular automata.

It is an important issue to understand the relationship between local and global mappings. In this paper we view a cellular automaton as a grid of communicating cells. During the evolution information can flow through the whole grid. In one-dimensional cellular automata a fixed cell divides the grid into two parts and we are interested in the way information flows through the cell. By studying the communication complexity of successive iterations of the local function we provide a new way to look at the global behavior of cellular automata.

## 2 Elementary cellular automata and $`01`$ matrices

In this paper we mainly focus on elementary cellular automata (ECA) which we define hereafter, although generalization to any one-dimensional cellular automata (CA) is always possible and quite straightforward.

We consider the one-dimensional cellspace, where each cell can be either in state $`0`$ or in state $`1`$. An ECA is defined by a local function $`f:\{0,1\}^3\{0,1\}`$ which maps the state of a cell and its two immediate neighbors to a new cell state. There are exactly $`2^{2^3}=256`$ ECA and each of them is is identified with its *Wolfram number*, which is between 0 and 255 and defined as

$$\underset{a,b,c\{0,1\}}{}(4a+2b+c)f(abc).$$

Following the cellular automata’s paradigm, all the cells change their states synchronously according to the local function. This endows the line of cells with a global dynamics whose links with the local function are still to be understood in the general case as already pointed out in the introduction. Let us remark however that some simple transformations on the local function induce simple transformations on the global dynamics: the space-symmetric ECA of $`f`$ is the ECA $`f^{}`$ with $`f^{}(a,b,c)=f(c,b,a)`$ and the state-symmetric is the ECA $`f^{\prime \prime }`$ with $`f^{\prime \prime }(a,b,c)=\overline{f(\overline{a},\overline{b},\overline{c})}`$. Thus we consider only ECA whose Wolfram number is minimal among its symmetries. This leaves 88 out of 256 ECA to consider, which is more than 256/4 because some ECA are symmetric.

To tackle the issue of local/global relationships, we study the evolution of one cell’s state after finitely many time steps. Given that after $`n`$ time steps the value of a cell depends on its own initial state and the initial states of the $`n`$ immediate left and $`n`$ immediate right neighbor cells, we define the $`n`$-th iteration of $`f`$, $`f^n:\{0,1\}^{2n+1}\{0,1\}`$, as $`f^1=f`$ and for $`n2`$ as

$$\begin{array}{cc}\hfill f^n(x_n,\mathrm{},x_1,x_0,x_1,\mathrm{},x_n)=f(& f^{n1}(x_n,\mathrm{},x_{n2}),\hfill \\ & f^{n1}(x_{n+1},\mathrm{},x_{n1}),\hfill \\ & f^{n1}(x_{n+2},\mathrm{},x_n)).\hfill \end{array}$$

Notice that knowing a simple description of $`f^n`$ for arbitrary $`n`$ is knowing the *long term* (asymptotic) behavior of the whole line of cells.

We therefore propose to measure the complexity of an ECA $`f`$ by the asymptotic complexity of the functions $`\left(f^n\right)`$. For that purpose, $`01`$ matrices reveal themselves to be a striking representation. When fixing the state of the central cell among $`2n+1`$ adjacent ones to $`0`$ for instance, $`2^{2n}`$ initial configurations are possible each leading the central cell to a peculiar state after $`n`$ time steps. This can be summarized in a square matrix $`M_0^n`$ of size $`2^n`$ defined as follows:

$$M_0^n(i,j):=f^n(\stackrel{}{b_i},0,b_j)$$

where $`b_k`$ is the binary representation of the integer $`k`$ on exactly $`n`$ bits, and $`\stackrel{}{b_k}`$ its reverse representation. Each value $`n`$ defines a different matrix, and we have, for each ECA, an infinite family of binary matrices for $`n=1,2,\mathrm{}`$.

Note that the definition of $`M_0^n`$ is unique up to permutation of rows and columns. We could as well have defined $`\stackrel{~}{M}_0^n(i,j):=f^n(b_i,0,\stackrel{}{b_j})`$ for example.

Fixing the center cell to $`0`$ was arbitrary. We could as well have chosen $`1`$. Therefore, any ECA $`f`$ defines two families of binary matrices (see figure 1). Note that the first matrix of each family, standing for $`n=1`$, defines completely the local function. One can think of these matrices as seeds for the families.

The matrices can in some cases ease the understanding of the global behavior. In figure 2 we show the space time diagram of rule 105 for some arbitrary configuration, and on the right the matrix $`M_0^5`$. In contrast with the space-time diagram, the matrix looks simple, and indeed there is a small description of the *additive* rule 105 (which is given later in the paper). We should emphasize that the space-time diagram shows the evolution of only a single configuration, while the matrix covers all configurations.

Different measures on the matrices are possible in order to analyze the underlying ECA. Among them we choose the simplest one: the number of different rows. To be precise we define $`d_n`$ as the maximum of the $`4`$ following integers: number of different rows of $`M_0^n`$, number of different columns of $`M_0^n`$, number of different rows of $`M_1^n`$, number of different columns of $`M_1^n`$.

## 3 Experimental measuring

Since the family of matrices of a given ECA defines the global and long term behavior, we can express $`d_n`$ as a known function of $`n`$ only once we understood the global behavior. However in some cases, seeing the matrices helped us to understand the global function.

We did brute force computations in order to compute $`d_n`$ for $`n\{1,\mathrm{},12\}`$ and for all ECAs. The complete results are shown in the web page www.lri.fr/`~`durr/CACC/. Figure 3 plots $`d_n`$ for different rules. We obtain quite different sequences, which we classify as follows:

there is $`b`$ such that $`n:d_nb`$.

there are values $`a_0`$ and $`a_1`$ such that $`d_n=a_1n+a_0`$, for all $`nn_0`$ for some fixed value $`n_0`$.

in this class we put rules where non of above applies. In some cases $`d_n`$ seems to be bounded by a polynomial in $`n`$, and in some cases $`d_n`$ seems to be exponential.

We want to emphasize that this classification is mainly experimental. Most of the time we don’t have mathematical evidence for determining whether a rule belongs to one class rather than to another. Table 1 shows the classification of all rules (again, only up to symmetric transformations which preserve $`d_n`$).

The following sections are devoted to the few ECA where we were able to give a closed formula for $`d_n`$ making their classification rigorous.

## 4 Communication complexity

The communication complexity framework appears as an extremely useful tool for calculating $`d_n`$. The communication complexity theory studies the information exchange required by different actors to accomplish a common computation when the data is initially distributed among them. To tackle that kind of questions, A.C. Yao \[Yao79\] suggested the two-party model: two persons, say Alice and Bob, are asked to compute together the values taken by a function $`f`$ of $`2`$ variables ($`x`$ and $`y`$ taking values in a finite set), Alice always knowing the value of $`x`$ only and Bob that of $`y`$ only. Moreover, they are asked to proceed in such a way that the cost — the total number of exchanged bits — is minimal in the worst case. Now different restrictions on the communication protocol lead to different communication complexity measures.

###### Definition 1 (Many round communication complexity).

The many round communication complexity $`CC(f)`$ of a function $`f`$ is the cost of the best protocol for $`f`$.

###### Definition 2 (One-way communication complexity).

A protocol is AB-one-way if only Alice is allowed to send information to Bob, and Bob has to compute the function solely on its input, and the received information. The AB-one-way communication complexity is the worst case number of bits Alice needs to send. BA-one-way complexity is defined in the same manner. Finally, the one-way complexity $`C(f)`$ of $`f`$ is the maximum of its AB-one-way and BA-one-way complexities.

Whereas most studies concern the many round communication complexity, we focus only on the one-way communication complexity. In terms of cellular automata it will permit us to measure the amount of information which have to flow from one side to another. Also from a practical point of view, the former measure is extremely difficult to compute for most functions, while the last measure is quite easy as shown by the next fact.

###### Fact 3 (\[KN97\]).

Let $`f`$ be a binary function of $`2n`$ variables and $`M_f\{0,1\}^{2^n\times 2^n}`$ its matrix representation, defined by $`M_f(x,y)=f(xy)`$ for $`x,y\{0,1\}^n`$. Let $`d(M_f)`$ be the maximum of the number of different rows and the number of different columns in $`M_f`$. We have

$$C(f)=\mathrm{log}_2\left(d(M_f)\right).$$

###### Proof.

Let be a AB-one-way protocol, where Alice knows $`x\{0,1\}^n`$ and Bob $`y\{0,1\}^n`$. Suppose Alice sends to Bob at most $`k`$ bits which depend solely on $`x`$, say by some mapping $`g:\{0,1\}^n\{0,1\}^k`$. Then since Bob knows $`f(x,y)`$ only from $`y`$ and $`g(x)`$, we must have $`f(x,y)=f(x^{},y)`$ for all $`x,x^{}`$ with $`g(x)=g(x^{})`$. In terms of matrix representation it means that the rows in $`M_f`$ indexed by $`x`$ and $`x^{}`$ are the same. So we must have $`k\mathrm{log}_2\left(d(M_f)\right)`$.

Conversely, $`\mathrm{log}_2\left(d(M_f)\right)`$ are sufficient for Alice: knowing $`M_f`$ she only has to say to Bob the group of identical rows the current entry belongs to. ∎

Then, up to a $`\mathrm{log}`$ transformation, the complexity measure $`d_n`$ appears to be precisely the exchanged information amount required for Alice and Bob to compute $`f^n`$ when Alice has the $`n`$ left cells and Bob has the $`n`$ right cells, both knowing the value of the central cell and maximizing over the scenario where only Alice is allowed to talk, and the scenario where only Bob is allowed to talk.

## 5 ECA with bounded complexity

We will now give formal proofs for some ECA to be in the bounded complexity class.

###### Definition 4.

An ECA is *nilpotent* if it converges to a unique configuration from any initial configuration in finite time.

Given that an ECA $`f`$ is nilpotent if and only if there is $`n_0`$ such that $`f^n`$ is constant for all $`nn_0`$, it is clear that a nilpotent ECA will have $`d_n=1`$ for large enough $`n`$: no communication is needed between Alice and Bob to compute the final state of the central cell.

There is a natural condition generalizing nilpotency, which can be used to prove bounded complexity for ECA.

###### Definition 5.

An ECA $`f`$ has a *limited sensibility* if the number of cells $`f^n`$ actually depends on is bounded by a constant independent of $`n`$. Formally there is a constant $`c`$ such that $`n`$ $`w\{0,1\}^{2n+1}`$ with $`_{i=1}^{2n+1}w_ic`$ and $`f^n(u)=f^n(uw)`$ for all $`u\{0,1\}^{2n+1}`$ where $``$ is the bitwise boolean and.

The ECA has *half-limited sensibility* if the condition above holds for the weaker condition $`_{i=1}^nw_ic`$ or equivalently $`_{i=n+1}^{2n+1}w_ic`$.

Clearly if $`f`$ has limited sensibility $`c`$ at most $`c`$ bits need to be exchanged between Alice and Bob. We show now that the half-limited sensibility is enough to achieve bounded one-way communication complexity.

###### Lemma 6.

An ECA with half-limited sensibility is in the bounded complexity class.

###### Proof.

Without loss of generality, let us assume that Alice knows the left cells and that the sensibility of $`f^n`$ is limited by $`c`$ on the first $`n`$ cells. There is a trivial AB-one-way protocol of cost $`c`$. We give a BA-one-way protocol of cost $`2^c`$, which is worse but still constant. Bob successively guesses each possible value of Alice’s sensible cells and sends the list of the corresponding values for $`f^n`$. Then Alice select among this list, the entry corresponding to the actual values of its sensible cells. ∎

An interesting example is rule 60. It has sensibility $`0`$ on the second half, and unlimited sensibility on the first half, as it computes the parity of the first $`n+1`$ cells, whenever $`n+1`$ is a power of $`2`$.

Unfortunately, it is undecidable to determine whether a given CA has a limited sensibility (by reduction from the nilpotency problem which is undecidable \[Kar92\]). Except some particular examples, we can only guess if a ECA has limited sensibility based on brute force computation for small values of $`n`$.

However there is a decidable property, which is sufficient for a ECA to be in the bounded class.

###### Definition 7.

An ECA $`f`$ is *additive* is there are binary operators $``$ and $``$ (not necessarily distinct), and a neutral element $`e`$ such that for all $`x`$, $`xe=ex=x`$ and with

$$x,y,z,x^{},y^{},z^{}\{\begin{array}{cc}\hfill f(xx^{},yy^{},zz^{})& =f(x,y,z)f(x^{},y^{},z^{})\hfill \\ \hfill f(xx^{},yy^{},zz^{})& =f(x,y,z)f(x^{},y^{},z^{})\hfill \end{array}$$

###### Remark.

The previous definition can naturally be extended to longer operator chains. However, as far as ECA are concerned, $`2`$ operators are sufficient to capture all additive rules.

Additivity is preserved by iterations of the local rule, as stated in the following lemma which can be proved straightforwardly by induction on $`n`$.

###### Lemma 8.

For all integer $`n`$ we have $`u,u^{}\{0,1\}^{2n+1}`$:

$`f^n(uu^{})`$ $`=`$ $`\{\begin{array}{cc}f^n(u)f^n(u^{})\hfill & \text{if }n\text{ is odd,}\hfill \\ f^n(u)f^n(u^{})\hfill & \text{otherwise,}\hfill \end{array}`$
$`f^n(uu^{})`$ $`=`$ $`\{\begin{array}{cc}f^n(u)f^n(u^{})\hfill & \text{if }n\text{ is even,}\hfill \\ f^n(u)f^n(u^{})\hfill & \text{otherwise.}\hfill \end{array}`$
where $``$ and $``$ act bitwise on bitstrings.

###### Property 9.

If $`f`$ is additive, $`d_n`$ is bounded by 2.

###### Proof.

Let $`f`$ be additive for $``$ and $``$ with the neutral element $`e`$. We give a one-way protocol computing $`f^n`$, where Alice sends a single bit to Bob, who can then compute the function. Bob could have started as well in this protocol. Let $`c`$ be the state of the central cell and $`u`$ and $`v`$ the states of the $`n`$ left cells and $`n`$ right cells. Alice knows $`u,c`$; Bob knows $`v,c`$; and the goal is to compute $`f^n(u,c,v)`$. The protocol is the following:

1. Alice computes the single bit $`b=f^n(u,c,\underset{n}{\underset{}{e\mathrm{}e}})`$ and sends it to Bob;
2. then Bob computes

$$\{\begin{array}{cc}bf^n(\underset{n}{\underset{}{e\mathrm{}e}},c,v)\hfill & \text{if }n\text{ is even}\hfill \\ bf^n(\underset{n}{\underset{}{e\mathrm{}e}},c,v)\hfill & \text{if }n\text{ is odd.}\hfill \end{array}$$

By Lemma 8 the protocol is correct. ∎

As an example we consider the additive rule 105. In the following table we write its local function $`f(x,y,z)`$ above all combinations of $`x,y,z`$. By the way, note that by definition of Wolfram numbers, the first row contains the number 105 in reverse binary notation.

The local function can be written as

$$f(x,c,y)=xcy1,$$

where $``$ is the exclusive or. Given that $``$ is associative, commutative and admits a neutral element ($`0`$), the rule clearly fits definition 7. This explains why the matrices $`M_c^n`$ have only two different rows or columns, as depicted in figure 2.

These observations permit us to refine the class of ECA having bounded complexity, and distinguish the following cases. Note that the first subclass is rigorous as it is based on proven properties of the local function, while limited sensibility is mostly based on brute force computation. The last subclass contains ECA for which we were not able to give a general reason for their membership to this class, although some of them are easy to understand individually (for instance, rule $`32`$).

15, 51, 60, 90, 105, 108, 128, 136, 150, 160, 170, 204

0, 1, 2, 3, 4, 5, 8, 10, 12, 19, 24, 29, 34, 36, 38, 42, 46, 72, 76, 78, 108, 138, 200

7, 13, 28, 140, 172

27, 32, 130, 156, 162

## 6 ECA with linear complexity

The case of linear complexity illustrates very nicely the relationship between communication complexity and ECA. We would like to emphasize on the fractal structure of the matrices for some rules, see figure 4. For those matrices the number of different rows is logarithmic in the size of the matrix, which makes it linear in $`n`$.

As an example we consider rule 132:

Figure 5 shows the fractal structure of its matrices. The space time diagram gives an explanation. Any block consisting of several 1’s, shrinks at every time step by 1 at each end, and either vanishes or remains a single 1, depending on the parity of its length.

###### Lemma 10.

For rule 132 we have $`d_n=n+1`$.

###### Proof.

For an upper bound we give a very simple communication protocol. If the center is $`0`$, no communication at all is needed, as the answer will always be $`0`$. Now suppose the center is $`1`$. It is part of a block consisting of $`k`$ cells on Alice’s side, and of $`l`$ cells on Bob’s side, where $`0k,ln`$. Now Alice sends $`k`$ to Bob, and Bob answers $`1`$ if $`k=l`$ and $`0`$ otherwise. The protocol is correct, since after $`n`$ steps the center will remain $`1`$ only if it is in the center of an even length block or if it is distant by at least $`n`$ to each end of the block. For the protocol, Alice needs to send a number out of $`n+1`$ different values. It would be the same if Bob starts first. Therefore $`d_nn+1`$.

For the lower bound, we give a submatrix in $`M_0^n`$ which is the identity. This submatrix is of dimension $`(n+1)\times (n+1)`$, which will show that there are at least $`n+1`$ different rows and at least as must different columns. Let $`R_k`$ be the row in $`M_0^n`$ corresponding to $`0^{nk}1^k`$, and let $`C_l`$ be the column corresponding to $`1^l0^{nl}`$. The submatrix made up of the intersection of rows $`R_k`$ and columns $`C_l`$ for $`0k,ln`$ is the identity matrix. ∎

This example is also interesting because the number of different rows in $`M_c^n`$ is $`1`$ if $`c=0`$ and $`n+1`$ if $`c=1`$, while for most rules the number of different rows seems to be the same (or at least similar) for the two families of matrices.

Another example is rule 23:

In this rule, cells become alternatively 0 and 1 with exception of those being inside a block of alternating 0’s and 1’s. Since the neighboring cells of such a block alternate their states, a block shrinks at both ends by 2 cells every second time steps. One can apply the same method to prove $`d_n=n+1`$.

## 7 ECA with other complexity

The ECA of this class are not well understood yet. For example, it contains rules 110 and 54, which are conjectured to be computation universal.111Rule 110 has been proven universal in some sense by M. Cook who presented his results during the CA98 workshop at Santa Fe Institute. The result is also presented in the book “A New Kind of Science” by S. Wolfram . But as far as we know a complete and detailed proof doesn’t appear in any reference. However for larger cell states we were able to prove polynomial and even exponential complexity for some CA.

The following CA with $`3`$ states has quadratic complexity and the construction can be generalized for more states to achieve complexity $`\mathrm{\Theta }(n^k)`$ for any $`k`$.

Let be the state set $`\{0,1,2\}`$. The cellular automata is defined for all $`i,j,k`$ by

$$f(i,j,k)=\{\begin{array}{cc}j\hfill & \text{if }j=0\text{ and }i=k,\hfill \\ \mathrm{max}\{i,j,k\}\hfill & \text{otherwise}.\hfill \end{array}$$

Note that each state is quiescent. The global behavior can be explained like this (see figure 7). Every cell different from $`0`$ tends to expand in both directions. Whenever a $`1`$-expansion and a $`2`$-expansion meet, the $`2`$-expansion overrules the former. There is a single situation where a $`0`$ cell can remain $`0`$, it is when two expansions of the same state reach at the same time the left and right neighbor.

To make this statement formal, consider the cell at position $`0`$. Let $`r_2`$ be the position of the first state-2-cell on the right between $`1`$ and $`n`$, and $`\mathrm{}`$ if there is no such cell. Let $`r_1`$ be the position of the first state-1-cell between $`1`$ and $`r_21`$ and $`\mathrm{}`$ if there is no such cell. The positions $`l_1,l_2`$ are defined in the same manner for the left neighborhood. Now we can completely determine the cell state after $`n`$ steps.

* If the cell was in state $`2`$, then it remains $`2`$ forever.
* If the cell was in state $`1`$, then it remains $`1`$ after $`n`$ steps if and only if $`l_2<n`$ and $`n<r_2`$.
* If the cell was in state $`0`$, then it remains $`0`$ after $`n`$ steps if and only if ($`l_2<n`$ and $`n<r_2`$ or $`l_2=r_2`$) and ($`l_1<n`$ and $`n<r_1`$ or $`l_1=r_1`$).

From these observations we can determine its complexity.

###### Lemma 11.

The complexity of the CA defined above is $`d_n\mathrm{\Theta }(n^2)`$.

###### Proof.

We will construct $`\mathrm{\Omega }(n^2)`$ different rows in the matrix $`M_0^n`$, which will suffice for the lower bound by symmetry of the matrix. For every $`0jin`$ let be $`R_{i,j}`$ the row corresponding to the left neighborhood

$$\underset{ni}{\underset{}{2\mathrm{}2}}\underset{ij}{\underset{}{1\mathrm{}1}}\underset{j}{\underset{}{0\mathrm{}0}}.$$

Let be $`C_{i,j}`$ the column corresponding to the similar (reversed) right neighborhood. Then row $`R_{i,j}`$ is $`0`$ only at column $`C_{i,j}`$, showing that all rows $`R_{i,j}`$ are different.

Conversely for the upper bound, it is clear from the above description of the rule that a correct one-way communication protocol can be achieved with complexity $`2\mathrm{log}_2(n+1)`$, since Alice needs only to send the numbers $`l_1,l_2`$ to Bob, while each can have only $`n+1`$ different values. ∎

We show now a very well known and simple CA, which has exponential complexity.

Let be state set $`\{0,1,\stackrel{~}{0},\stackrel{~}{1}\}`$. We define the cellular automata $`f`$ such that $`f^n(u,1,v)`$ compares the strings $`u`$ and $`v`$, with $`u\{0,1\}`$ and $`v\{\stackrel{~}{0},\stackrel{~}{1}\}`$. Let be $`x,c,y\{0,1\}`$ and $`z\{0,1,\stackrel{~}{0},\stackrel{~}{1}\}`$, then

$`f(z,\stackrel{~}{c},\stackrel{~}{y})=\stackrel{~}{y}`$ (shift left to the center)
$`f(x,c,y)=x`$ (shift right to the center)
$`f(x,1,\stackrel{~}{y})=\{\begin{array}{cc}1\hfill & \text{if }x=y\hfill \\ 0\hfill & \text{if }xy\hfill \end{array}`$ (a difference makes the center 0)
For all other values $`f`$ is $`0`$.

###### Lemma 12.

The complexity $`d_n`$ of the CA defined above is exponential in $`n`$.

###### Proof.

Clearly $`M_1^n`$ contains at least $`2^n`$ different rows (among $`4^n`$): for every row indexed by $`u\{0,1\}^n`$ there is a single entry $`1`$, at a column $`v`$, where $`v`$ is the reverse dual of $`u`$, and any other row contains only $`0`$. ∎

## 8 Future directions

The purpose of this paper was to show a relationship between cellular automata and communication complexity. For this we deliberately made simple choices: elementary cellular automata and particular one-way communication. Our approach can be generalized in several ways:

* We partitioned evenly the $`2n+1`$ cells between Alice and Bob, and also fixed the center cell. This does not take into account asymmetric behavior for some CA. When $`f^n`$ is fixed, we can define a matrix representation $`M_p^n`$ of dimension $`2^p\times 2^{2n+1p}`$ (for $`1p2n+1`$) such that $`M_p^n(u,v)=f(u\stackrel{}{v})`$, *i.e.* where Alice knows the $`p`$ leftmost cells and Bob the $`np`$ rightmost. Then an interesting complexity measure is:

$$R_n=\underset{p}{\mathrm{max}}|rows(M_p^n)|,$$

where $`|rows()|`$ stands for the number of different rows. The value of $`p`$ where the maximum is reached is non trivial and, while clearly connected to the global behavior, hard to predict from the local rule. A striking example is ECA rule 7 which has a bounded $`d_n`$ complexity due to its half-limited sensibility but has a linear $`R_n`$ complexity, maximum being reached around $`p=\frac{n}{3}`$, as indicated by brute force computations.

Following this idea, we could as well define $`R_n`$ symmetrically on rows and columns as follows:

$$R_n=\underset{p}{\mathrm{max}}\mathrm{max}\{|rows(M_p^n)|,|cols(M_p^n)|\}.$$
* The link between communication complexity and matrix representations is not reduced to Fact 3. Actually, many round communication complexity is lower-bounded by the log of the rank of the matrix representation (see \[KN97\]). Moreover, it is conjectured that a poly-log of the rank is also an upper-bound.
* Finally, considering the more general framework of all one-dimensional CA (with any radius and any state set), it is interesting to note that a classification based on the asymptotic behavior of $`d_n`$ has some very reassuring properties such as:

+ the class of a CA $`A`$ is “higher” than the class of any of its sub-CA ;
    + the complexity of the Cartesian product $`A\times B`$ is the product of the complexities of $`A`$ and $`B`$.

Another important issue of course, is to give mathematical rigorous proofs for the complexity of some ECA, which however is at least as difficult as understanding completely the global behavior.

## 9 Acknowledgment

We would like to thank Nicolas Ollinger for helpful discussions.