text:
# Heavy Element Abundances and Dust Depletions in the Host Galaxies of Three Gamma–Ray Bursts

## 1 INTRODUCTION

Gamma–ray bursts (GRBs) are among the most dramatic events in the Universe. Their luminosities are so high ($`10^{51}10^{54}`$ ergs are emitted in a few seconds) that they can be seen at the highest redshifts. However, since the decline in their energy emission is very fast, the investigation and understanding of their physical nature is is not particularly easy (Piran 2001). For instance, the redshift of the afterglow or host galaxy has been measured in only 24 cases111see http://www.mpe.mpg.de/$``$jcg/grbgen.html for the complete list of GRB redshifts.

Only eight of these objects have been targeted quickly enough by ground–based telescopes to obtain low resolution spectra of the optical transient, and all show a common peculiarity: very strong UV absorption lines of low ionization species (Fiore 2001; Fynbo et al. 2002). This is similar to what is seen in damped Lyman–$`\alpha `$ systems (DLAs) associated with intervening galaxies along QSO sight lines. GRB–DLAs are certainly an unexplored and important source of information on the circumburst and/or interstellar medium (ISM) of the GRB host galaxy. Here we explore in more detail their properties and compare them with those of QSO–DLA galaxies.

We use the curve of growth (COG) analysis to derive column densities of low ionization species in several GRB–DLAs. As for QSO–DLAs, we neglect ionization effects to derive the abundances of several heavy elements. The low ionization of the gas is warranted by the large equivalent widths of the low ionization lines, and the low equivalent widths of the moderate and high ionization lines. The difference in abundances between weakly and greatly dust depleted elements provides an estimate of the dust content.

The COG analysis was applied to QSO–DLAs (Blades et al. 1982; Turnshek et al. 1989) before the advent of high resolution spectroscopy, which allows a direct fitting of individual absorption lines. Since GRB emission fades very rapidly, high resolution (FWHM $`10`$ km s-1) spectra of GRB afterglows are very hard to obtain.

In this work, we interpret strong differences between GRB–DLAs and QSO–DLAs as the result of the difference in the densities of the intervening gas. Since GRBs are, at least for some time, brighter than primarily optically selected QSOs, they can be observed even if their sight lines cross very dense and dusty regions, such as molecular clouds, where extinction is very severe. On the other hand, QSO sight lines are easier to detect when intersecting less dusty interstellar clouds.

This bias in QSO–DLAs has been already suggested in the past (see, for instance, Fall & Pei 1993; Boissé et al. 1998). More recently, Ellison et al. (2001) have studied a small sample of radio–selected QSOs and tentatively found more DLAs than in optically selected QSOs. Even if this result is affected by small number statistics (significant at $`2\sigma `$ level), it supports the idea of dust obscuration in optically selected QSO–DLAs.

Our analysis is alternative to and independent of the dust content estimate obtained so far for GRBs. The dust reddening in GRB afterglows has been derived in several objects (see for instance Reichart 1998; Jensen et al. 2001; Rhoads & Fruchter 2001; Fynbo et al. 2001; Galama & Wijers 2001) and in most cases it has been found to be small or negligible. The method applied assumes initial power law emission from the GRBs, and steep extinction curves such as those in the Milky Way (MW) or Large & Small Magellanic Clouds (MC). Possible discrepancies with the results of our analysis challenge the two initial assumptions of very steep extinction and initial power law emission of the central source.

For this study, we examine the absorption lines of three of the eight GRBs with UV rest frame spectra, namely GRB990123 ($`z=1.601`$, Kulkarni et al. 1999), GRB010222 ($`z=1.475`$, Masetti et al. 2001; Jha et al. 2001; Salamanca et al. 2001; Mirabal et al. 2002), and GRB000926 ($`z=2.0379`$, Castro et al. 2001). We exclude GRB970508 ($`z=0.835`$, Metzger et al. 1997), GRB990510 ($`z=1.619`$, Vreeswijk et al. 2001) GRB000301C ($`z=2.04`$, Jensen et al. 2001), GRB990712 ($`z=0.4331`$, Vreeswijk et al. 2001), and GRB011211 (Holland et al. 2002) for poor quality of the spectra and therefore lack of interesting absorption features.

## 2 GRB–DLAs COLUMN DENSITY DETERMINATION

Similarly to QSO–DLAs, GRB–DLAs show strong Fe II, Mg II, and Si II absorptions, together with relatively weak Zn II and Cr II. Table 1 lists oscillator strengths $`f_\lambda `$ (from the recent compilation by Prochaska et al. 2001) and rest frame equivalent widths $`W_r`$ of absorption lines in the three GRBs used in the present analysis. The large $`W_r`$ of all these species relative to higher ionization species like C IV, Si III and Si IV, indicate that the medium is weakly ionized. From the equivalent widths (EWs), we derive column densities and directly compare the results with typical column densities in QSO–DLAs. Comparing column densities instead of metallicities \[X/H\] has the advantage that the H I column density (known only in GRB000926 with large uncertainty; Fynbo et al. 2002) is not required. Moreover, it is not necessary to make any assumptions about the dust depletion, cosmic abundance or ionization level of the considered element, but we can still search for similarities and differences between GRB–DLAs and QSO–DLAs.

A direct comparison is complicated by the fact that normally QSO–DLAs are observed at high spectral resolution (FWHM $`10`$ km s-1) in a large wavelength range (thanks to echelle spectroscopy), allowing a good determination of column densities of many ions, even in cases where saturated or weak lines in complex features are detected (see for instance Lu et al. 1996; Pettini et al. 1997; Prochaska & Wolfe 1999). On the other hand, the typical resolution of GRB optical spectra is FWHM $`>100`$ km s-1. Moreover, the majority of absorption lines are saturated, and it is not possible to use the linear part of the COG to determine column densities. However, the lines are numerous and so, even if the uncertainty may be large, it is possible to make an abundance analysis using the general COG analysis (Spitzer 1978). Since the typical resolution of GRB spectra does not allow the separation of the different components of a complex feature, due to the many clouds along the line of sight, in our analysis we adopt a large “effective” Doppler parameter, being the result of the superposition of many narrow absorption lines. For reference, we note that typical velocities in QSO–DLAs are $`100`$ km s-1 or more. The COG analysis applied with the single component approximation was used for QSO–DLA studies before high resolution spectroscopy of QSOs became possible (see for instance Blades et al. 1982; Turnshek et al. 1989). In fact, Jenkins (1986) showed that the COG technique applied to complex features gives nearly the correct answer (the simulated–to–true column density ratio rarely goes below 0.8) even if different lines have very different saturation levels or Doppler parameters. This general result is also confirmed by Savage & Sembach (1991).

The best–fitting column density is determined by using simultaneously different EWs of various ions and choosing the COG with an effective Doppler parameter that minimizes the $`\chi ^2`$. Once the best effective Doppler parameter is determined, the error on the column density for each ion is determined by varying $`\mathrm{log}N`$ for which $`\chi ^2/dof1`$. In the following § 2.1–2.3, we discuss column density measurements in each individual GRB. Figures 13 show the best–fitting $`W_r/\lambda `$ and column densities, and the corresponding COG. Estimated column densities are given in Table 2.

### 2.1 GRB990123

The optical transient of GRB990123 at $`z=1.6004`$ was observed with the Keck/LRIS (Kulkarni et al. 1999) for a final resolution and signal–to–noise ratio of FWHM $`=11.6`$ Å ($`400700`$ km s-1) and S/N $`30`$, respectively. The very weak Fe II $`\lambda 2260`$ EW gives inconsistent results with other Fe II lines, and thus this detection has not been considered in our analysis. Fe II $`\lambda 2374`$ is not reliable because it is probably partly blended with the Fe II $`\lambda `$2382 line.

For the four remaining Fe II lines, we get a best–fit of $`\mathrm{log}N(`$Fe II$`)=14.78^{+0.17}_{0.10}`$ and $`b=50`$ km s-1(Figure 1). From the EW of Zn II $`\lambda 2026`$ and considering $`b=50`$ km s-1, we derive a Zn II column density of $`\mathrm{log}N(`$Zn II$`)14`$, and calculate a Zn II $`\lambda 2062`$ contribution to the Zn II $`\lambda 2062`$ \+ Cr II $`\lambda 2062`$ blend of $`W_r=0.58`$ Å, to be compared with the detected $`W_r=0.48\pm 0.04`$ Å. This means that the contribution of the Cr II $`\lambda 2062`$ line to the blend is negligible or non existing. Therefore we recalculate the Zn II column density from the Zn II $`\lambda 2026`$ and Zn II $`\lambda 2062`$ doublet, from which we derive $`\mathrm{log}N(`$Zn II$`)=13.95^{+0.05}_{0.05}`$

### 2.2 GRB000926

GRB000926 at $`z=2.0379`$ was observed with the Keck/ESI echelle spectrograph (Castro et al. 2001), with a good signal–to–noise ratio (S/N $`=1020`$) and relatively high resolution (FWHM $`80`$ km s-1). Castro et al. (2001) also show a low resolution spectrum, with EW measurements that are systematically larger than those obtained from the high resolution spectrum, but the authors claim that the high resolution measurements are more accurate, so we only use these. The spectrum shows at least two absorbing clouds separated by 168 km s-1. In our analysis, we consider the total equivalent widths of the two components together, since the resolution does not allow them to be clearly separated.

The observed Si II $`\lambda 1808`$ and Si II $`\lambda 1526`$ lines, and the five detected Fe II lines give $`\mathrm{log}N(`$Si II$`)=16.47^{+0.10}_{0.15}`$ and $`\mathrm{log}N(`$Fe II$`)=15.6^{+0.20}_{0.15}`$, respectively ($`b=115`$ km s-1, Figure 2). If we assume $`b=115`$ km s-1, we get $`\mathrm{log}N(`$Cr II$`)=14.34^{+0.05}_{0.05}`$ from the Cr II $`\lambda 2056`$ EW. This corresponds to $`W_r=0.50.6`$ Å and $`W_r=0.350.43`$ Å for Cr II $`\lambda 2062`$ and Cr II $`\lambda 2066`$, respectively. Neither of these measurements is consistent with those observed ($`W_r<0.28`$ Å and $`W_r<0.2`$ Å, respectively); this might indicate a contamination of the Cr II $`\lambda 2056`$ line by an unidentified absorption associated with an intervening metal system. Moreover, the Cr II $`\lambda 2062`$ is probably corrupted by a noise spike in the spectrum (see Figure 3 of Castro et al. 2001) probably due to a remnant of the strong sky line at $`\lambda =6258.05`$ Å. The same contamination might also effect the Zn II $`\lambda 2062`$ line (the EW is inconsistently lower than expected from Zn II $`\lambda 2026`$), therefore the Zn column density is determined from Zn II $`\lambda 2026`$ only: $`\mathrm{log}N(`$Zn II$`)=13.82\pm 0.05`$ for $`b=115`$ km s-1. The lack of Fe II $`\lambda 2586`$ detection is puzzling. If, for instance, we assume $`W_r(`$Fe II$`\lambda 2586)<1`$ Å (way above the detection limit in the spectrum), the line is almost unsaturated, and $`\mathrm{log}N(`$Fe II$`)<14.6`$ for $`b>70`$ km s-1, inconsistent with what is found from the other Fe II lines.

Fynbo et al. (2001) report a tentative H I column density measurement of $`N(`$H I$`)2\times 10^{21}`$ cm-2. This leads to a relatively high metallicity with \[Zn/H\] $`0.13`$.

### 2.3 GRB010222

The optical transient of GRB010222 at $`z=1.475`$ was observed with the FLWO 1.5m telescope (Jha et al. 2001; FWHM $`=6`$ Å or $`300450`$ km s-1, S/N $`10`$), with the 3.58m TNG (Masetti et al. 2001; FWHM $`=4.8`$ Å or $`200400`$ km s-1, S/N $`=1020`$), with the 4.2m WHT (Salamanca et al. 2001; FWHM $`=3.35.8`$ Å or $`300`$ km s-1, S/N $`10`$), and with Keck/LRIS and ESI (Mirabal et al. 2002; FWHM $`=1113`$ Å or $`650`$ km s-1, and FWHM $`=0.40.8`$ Å or $`30`$ km s-1). Even though the different spectra span a time interval of $`27`$ hours, starting 5 hours after the burst, the absorption line equivalent widths do not show significant time variability (Mirabal et al. 2002). Therefore, to obtain a better estimate of column densities, we combined the EWs of the same lines from different observations weighted according to the errors. We constrain the effective Doppler parameter to $`b=70`$ km s-1, using the Si II $`\lambda 1526`$ and Si II $`\lambda 1808`$ lines, and seven Fe II lines (Figure 3). We get $`\mathrm{log}N(`$Si II$`)=16.09\pm 0.05`$ and $`\mathrm{log}N(`$Fe II$`)=15.32^{0.15}_{0.10}`$. The Fe II lines are scattered in the COG diagram, probably because of non–uniform EW measurements by the four groups.

The Zn II $`\lambda 2026`$ line at $`\lambda 5018`$ Å is blended with the Mg I $`\lambda 2026`$ line. The contamination of Mg I to this doublet is estimated using the Mg I $`\lambda 2852`$ line at $`\lambda 7065`$ Å and $`W_r(`$Mg I $`\lambda 2852)=1.22\pm 0.04`$ Å. Assuming an effective Doppler parameter $`b>35`$ km s-1, we get $`\mathrm{log}N(`$Mg I$`)<14`$ and $`W_r(`$Mg I $`\lambda 2026)<0.04`$ Å. We then assume that the feature at $`\lambda 5018`$ Å is dominated by the Zn II $`\lambda 2026`$ absorption, with $`W_r=0.79_{0.07}^{+0.05}`$ Å and the lower error determined by a possible contamination from Mg I $`\lambda 2026`$.

The Cr II $`\lambda 2056`$ EW is very low, therefore it must be weakly or not at all saturated. From Cr II $`\lambda 2056`$ and Cr II $`\lambda 2066`$ lines, we get $`\mathrm{log}N(`$Cr II$`)=14.04^{+0.04}_{0.06}`$. From this, we calculate a contribution of Cr II to the Zn II $`\lambda 2062`$ \+ Cr II $`\lambda 2062`$ doublet of $`W_r(`$Cr II $`\lambda 2062)=0.32\pm 0.04`$ Å. For this doublet we only use the measurements given by Jha et al., Salamanca et al. and Mirabal et al. (weighted mean $`W_r=0.73\pm 0.02`$ Å), because the spectrum by Masetti et al. shows strong blending with other absorption lines. Once the Cr II contribution is taken into account, we derived $`W_r(`$Zn II $`\lambda 2062)=0.41\pm 0.05`$ Å. Using also the Zn II $`\lambda 2026`$ detection, we obtain $`\mathrm{log}N(`$Zn II$`)=13.78\pm 0.07`$ for $`b=70`$ km s-1. The Mn II column density is obtained from the Mn II $`\lambda \lambda 2576,2594,2606`$ triplet. For $`b=70`$ km s-1, we get $`\mathrm{log}N(`$Mn II$`)=13.61^{0.08}_{0.06}`$.

## 3 HEAVY ELEMENT ABUNDANCES IN GRB–DLAs

Figure 4 displays the QSO–DLA column density histograms222We have not used Al II measurements detected in GRB000926 and GRB010222, because not included in the QSO–DLA sample, and because \[Fe/Al\] $`=0.3\pm 0.3`$ and $`0.4\pm 0.2`$ for GRB000926 and GRB010222, respectively, which is not particularly interesting for our discussion. of Fe II, Cr II, Zn II, and Si II. These column densities are obtained from a large compilation of QSO–DLA measurements collected from the literature (see Savaglio 2000 for a description of the compilation). The sample contains 98 QSO absorption line systems associated with mostly neutral gas clouds (H I column density larger than $`10^{19}`$ cm-2) of the ISM in $`0.0<z<4.6`$ galaxies, for which the column density of one or more of the following elements is measured: Zn II, Si II, Cr II, Fe II. The symbols in Figure 4 indicates the column densities of the same ions measured for the three GRB–DLAs. This reveals several differences between QSO–DLAs and GRB–DLAs. The Zn II column density in GRB–DLAs shows the most striking difference, being much larger than in QSO–DLAs. For Si and Cr the deviations are also very large. Fe II behaves differently, being quite consistent with the upper part of the Fe II QSO–DLA distribution.

If the gas is nearly neutral, as suggested by the large EWs of the low ionization lines, the ionization correction can be neglected and it is possible to calculate the element relative abundance from ions with ionization potential above 13.6 eV. This assumption is also widely used to derive abundances in QSO–DLAs. Table 3 shows the comparison between heavy element relative abundances in QSO–DLAs (mean values, column four) and in the three GRB–DLAs (columns five, six and seven) . Columns two and three also give the number of QSO–DLAs considered and the mean redshift, respectively. For both GRB–DLAs and QSO–DLAs, the standard solar abundances from Grevesse, Noels, & Sauval (1996) are adopted. The very low \[Fe/Zn\] values in three GRB–DLAs ($`2.03`$, $`1.08`$, and $`1.32`$) are much smaller than in QSO–DLAs: $``$\[Fe/Zn\]$`=0.46\pm 0.24`$ in 32 objects. This is an indication of strong dust content in the GRB circumburst medium and/or in the ISM of the host galaxy, because while Fe is heavily depleted on dust in the ISM of galaxies, Zn is marginally depleted only in the densest clouds (Savage & Sembach 1996a). The plot of \[X/Zn\] abundances as a function of the Zn II column density is also very interesting (Figure 5). In QSO–DLAs these show a trend, the \[X/Zn\] being smaller for larger $`\mathrm{log}N(`$Zn II). The \[X/Zn\] values for GRB–DLAs are located at the extension of the \[X/Zn\] vs. $`\mathrm{log}N(`$Zn II) distribution in QSO–DLAs. The gap between QSO–DLAs and GRB–DLAs is filled by a completely different class of absorbers: those in the ISM of the MW and MC. Low values of \[Fe/Zn\] are also an indication of high dust content. Petitjean, Srianand, & Ledoux (2002) discuss the gas density in QSO–DLAs with H2 detection, and suggest that the dust depletion might be larger in denser clouds. If this can be extended to GRB–DLAs, it might imply that their gas density is higher than in QSO–DLAs.

The small \[X/Zn\] values found in GRB–DLAs might be a general property of high metal column density systems rather than a peculiarity of GRBs themselves. GRBs are initially brighter than QSOs, hence detectable even in cases of heavy dust obscuration. In other words, QSO–DLAs and GRB–DLAs might probe the same population of galaxies, but different regions: the sight lines of the former cross moderately dense regions, while the sight lines of the latter might cross denser regions such as molecular clouds in a star forming environment.

As already discussed in § 2, the COG analysis may underestimate column densities if the lines are strongly saturated, as in the case of Fe II. This would artificially create a large dust depletion if \[Fe/Zn\] were used as an indicator. However, the underestimate of saturated lines is in most cases not larger than 0.1 dex (Jenkins 1986). Moreover, an independent check of consistency is provided by the comparison of Fe II with Si II and Cr II. Si II and Fe II have similar problems with saturation, but Si is much less dust depleted (Savage & Sembach 1996a). The iron–to–silicon relative abundance is low in the two GRB–DLAs discussed here, indicating high depletion of iron in dust: \[Fe/Si\] $`=0.83_{0.18}^{+0.25}`$ and $`0.73_{0.11}^{+0.16}`$ in GRB000926 and GRB010222, respectively. Also \[Cr/Zn\] is a dust indicator. Cr II absorption lines are generally weakly saturated, but the column densities in the same two GRB–DLAs are low compared to Zn II: \[Cr/Zn\] = $`0.51\pm 0.07`$ and $`0.77_{0.09}^{+0.08}`$ in the same two GRBs.

There are indications that the H I column density in GRB–DLAs is larger than in typical QSO–DLAs. In 89 QSO–DLAs with $`\mathrm{log}N(`$H I$`)20.0`$, only 15 (17%) have $`\mathrm{log}N(`$H I$`)>21.0`$. The H I column density has been estimated in GRB000301C by Jensen et al. (2001), who report $`N(`$H I$`)=1.5^{+3.0}_{1.0}\times 10^{21}`$ cm-2. GRB000926 has also been observed with the Nordic Optical Telescope (Fynbo et al. 2002) and a very strong Ly$`\alpha `$ absorption line identified, with column density $`2\times 10^{21}`$ cm-2. This is in a very noisy part of the spectrum, but if we assume that this H I column density is close to the correct value and neglect ionization correction, we derive \[Si/H\] $`=0.38`$, \[Zn/H\] $`=0.13`$, \[Cr/H\] $`=0.64`$, \[Fe/H\] $`=1.21`$, suggesting a large metallicity and dust depletion for a large H I GRB–DLA. In comparison, in 8 QSO–DLAs with $`\mathrm{log}N(`$H I$`)>21.0`$, and measured Zn II and Cr II, we find $``$\[Zn/H\]$`=1.46\pm 0.34`$ and $``$\[Cr/H\]$`=1.74\pm 0.22`$.

## 4 DUST DEPLETION AND EXTINCTION

Since four elements are measured in GRB000926, it is possible to derive its dust depletion pattern. We adopt the method described in Savaglio (2000). Basically, we consider the four depletion patterns observed in the Milky Way, e.g. the depletion patterns in the warm halo (WH), warm disk+halo (WDH), warm disk (WD), and cool disk (WC) clouds (Savage & Sembach 1996a). For each depletion pattern, we find the best–fit values for the dust–to–metals ratio ($`d/d_j`$, where $`j`$ depends on the depletion pattern assumed) and the metallicity compared to solar $`Z/Z_{\mathrm{}}`$. The result for GRB000926 at $`z=2.038`$ is shown in Figure 6. The best fit is given by the warm halo cloud pattern, with $`Z/Z_{\mathrm{}}=0.78`$. This is higher than the metallicities in QSO–DLAs: $`Z/Z_{\mathrm{}}=0.22\pm 0.23`$ in 21 DLAs at $`1.7<z<2.3`$ (Savaglio 2000).

We can now estimate the obscuration of the GRB due to dust distributed along its line of sight. This is proportional to the column density of metals. The extinction in the V–band, due to dust, can be approximated by:

$$A_V=0.54\frac{d}{d_{WH}}\frac{Z}{Z_{\mathrm{}}}\frac{N(\mathrm{HI})}{10^{21}\mathrm{cm}^2}$$
(1)
where 0.54 is the typical value of $`A_V`$ in the solar neighborhood for a column density of gas with $`\mathrm{log}N(`$H I$`)=21.0`$. For GRB000926, we find $`A_V0.9`$ mag. This is much higher than in QSO–DLAs, where $`V`$ extinction is typically lower than 0.1 mag.

The depletion pattern and extinction can also be calculated for GRB990123 and GRB010222, because this depends on the product of metallicity and H I column density, i.e., the column density of metals. We consider the Zn II column density and neglect the dust depletion correction for this element. Best–fits for these two GRB–DLAs give a warm halo cloud depletion pattern (Figure 7), and dust extinctions of $`A_V1.1`$ and 0.7 mags for GRB990123 and GRB010222, respectively.

## 5 DISCUSSION

We have used the curve of growth to study the heavy element absorption lines associated with three GRBs, namely GRB990123 (Kulkarni et al. 1999), GRB000926 (Castro et al. 2001), and GRB010222 (Masetti et al. 2001; Jha et al. 2001; Salamanca et al. 2001; Mirabal et al. 2002). These are the only GRBs with available UV spectra obtained so far with quality good enough to detect high S/N absorption lines. All GRB spectra show very high Zn II absorption associated with the circumburst medium or interstellar medium of the host galaxy, from which we derive a mean column density of $`\mathrm{log}N(`$Zn II$`)=13.85`$ at $`z=1.70`$. This is $`3`$ times larger than the largest Zn II column density detected so far in QSO–DLAs. High Zn II columns indicate high metallicity and/or low ionization of the gas, also supported by the presence of strong Fe II, Si II, and Cr II, as well as Mg II together with Mg I. Moreover, the GRB–DLAs analyzed here satisfied the criteria found by Rao & Turnshek (2000) that are used for QSO–DLA selection, namely $`W_r(`$Mg II $`\lambda 2796)0.6`$ Å and $`W_r(`$Fe II $`\lambda 2600)0.5`$ Å.

Since the metal column densities are so high, the dust extinction can be very important. A good indicator of dust content is given by the \[Fe/Zn\] values; in the GRB–DLAs these are much smaller (higher dust depletion) than those seen in QSO–DLAs: $``$\[Fe/Zn\]$`=1.48`$ in the former, $``$\[Fe/Zn\]$`=0.46`$ in the latter. The combination of large column densities of metals and large dust depletion can lead to large extinction in GRB–DLAs. If we compare metal column densities with the ones in the solar neighborhood, where extinction is very well studied, we find optical extinction of $`A_V0.7,0.9`$ and 1.1 magnitudes. This is much larger than that found for most QSO–DLAs: $`A_V0.1`$. We notice, however, that another possible explanation for the very low \[Fe/Zn\] values would be a nucleosynthetic production of Fe and Zn in GRBs and/or their environment being different from the standard solar pattern.

These strong differences between QSO–DLAs and GRB–DLAs do not necessarily indicate a difference in the nature of the host galaxies. Indeed, the distribution of the Zn relative abundances as a function of Zn II column density in GRB–DLAs and QSO–DLAs is consistent for these two classes of objects. \[Fe/Zn\], \[Cr/Zn\], and \[Si/Zn\] decrease as a function of $`\mathrm{log}N(`$Zn II) for QSO–DLAs and GRB–DLAs, which are located in the upper left part and in the lower right part of the diagram, respectively. The QSO–DLA and GRB–DLA distributions are bridged by the heavy element abundances in the diffuse and dense ISM of the Milky Way and the Magellanic Clouds. This suggests that the galaxies associated with the absorbing gas around GRBs are not different from those of QSO–DLAs. The important difference is in the column densities of the intervening ISM: GRBs are (at least for some time) much brighter than optically selected QSOs, so their sight lines can probe much denser and dustier regions of galaxies. Indications of a bias effect in QSO–DLAs due to dust obscuration have been pointed out by several authors (Fall & Pei 1993; Boissé et al. 1998; Savaglio 2000; Petitjean et al. 2002).

Reichart (1998), Jensen et al. (2001), Rhoads & Fruchter (2001), Fynbo et al. (2001), and Galama & Wijers (2001) have estimated the dust extinction in GRBs from curvature in their spectra, assuming that the intrinsic GRB spectra from the UV to IR bands are power laws. This approach gives a small $`V`$ extinction only if MW or MC laws are assumed: $`A_V00.2`$ for GRB970508, GRB000301C, GRB000926, and GRB990123. The result for GRB990123 is supported by the lack of spectral slope variation going from the optical to x–ray bands (Castro-Tirado et al. 1999). Šimon et al. (2001) have found that the color variation during GRB decline in 17 objects (three of which are the ones studied in this paper) is relatively small, suggesting similar and low reddening in these GRBs. However, they also notice that another sample of five GRBs (not included in the first one, for lack of complete photometric information) have much redder colors. Low extinction can be explained by sublimation of dust grains due to UV emission (Waxman & Draine 2000). Fruchter, Krolik, & Rhoads (2001) suggest grain destruction by GRB heating and grain charging. These effects can be present up to a distance of $`100`$ pc from the GRB source.

This is in principle in contradiction with our findings. However, the dust disruption mechanisms suggested by Fruchter et al. (2001), or other mechanisms, such as sputtering (Draine & Salpeter 1979), predict that small grains are destroyed first. Dust destruction of small grains would still give a large content of dust, if the initial grain–size distribution is dominated by large grains, as suggested in models of MW an MC extinction curves (Weingartner & Draine 2001). Therefore, what remains in dust can still be an important fraction of the total metal content. Grain coagulation favored by high densities, leading to the formation of large grains, is also possible (Mathis 1990). In these cases, MW or MC extinction curves might be inappropriate to describe dust obscuration. A dust grain distribution skewed toward large grains would give a grey extinction, therefore may explain the low reddening found in GRB afterglows (Stratta et al. 2002). This is a plausible speculation, but quantitative calculations, needed to determine if it works in practice, are beyond the scope of this paper. A first attempt is instead presented by Perna & Lazzati (2002), who have developed a detailed numerical code that describes, among other effects, the dust destruction under an intense X–ray and UV radiation field the very first seconds after the burst. Alternative explanations are unknown systematic effects. For instance, the low reddening suggested relies on the assumption of an intrinsic power law emission of the optical afterglow, which in principle cannot be tested. It might also be that the extinction in itself is a power law, and when combined with the intrinsic GRB power law emission, would still give a power law spectrum. Therefore, this would require low or no rectification.

The main result of the present work is the strong difference between QSO–DLA and GRB–DLA heavy element column densities. GRB–DLAs occur most likely along the sight line of much brighter sources, and are embedded in star forming and therefore metal rich regions, where the dust extinction is probably not negligible. This is another evidence supporting the idea that DLAs in front of the fainter QSO radiation, can be detected and studied in detail only when the sight line crosses less dense, metal polluted and/or extincted regions of high redshift galaxies.

We thank Tim Heckman, Fiona Harrison, Eliana Palazzi and Ken Sembach for fruitful information on GRB spectra and ISM absorptions. We are particularly grateful to Daniela Calzetti, Julian Krolik, Nicola Masetti, Nino Panagia, and James Rhoads for stimulating discussions that helped to improve this paper.


format: text

text:
# 1 Introduction

## 1 Introduction

Evolutionary algorithms have been shown by many authors (e.g. ?) to be suited for solving complex optimization problems, and there are a highly developed theory of evolution processes ? and lots of recipes for successfully applying evolutionary algorithms ?. Particularly in combinatoric optimization where many other standard techniques fail, considerable success has been achieved by using evolutionary algorithms. Obviously, each particular optimization problem could be solved more effectively (i.e. less computer time consuming) by a deterministic algorithm, provided the algorithm is known. The main advantage of evolutionary algorithms is their simplicity and universality. In most cases evolutionary algorithms can be parallelized in a trivial way by distributing the individuals among a set of parallel processors. This may be considered as another advantage.

One of the most well-known examples, which has drawn the attention of scientists from various disciplines, is the Travelling Salesman Problem (TSP). In its standard formulation, the TSP has been proven to be NP complete ?, and many authors have tried to tackle this problem using different types of evolutionary strategies as well as other methods (e.g. ?,?,?,?,?,?).

To apply an evolutionary algorithm one has to provide two essential ingredients: First, one needs a fitness function which evaluates a solution. This fitness function must be calculable very effectively (in terms of computer time) since it has to be evaluated extremely often during the calculation. Hence, the fitness function is required to be simple. Second, one needs a mutation operator which takes into account the topology of the fitness as a function of the parameters to be optimized. If the mutation operator does not care about the topology it happens that even a small mutation may lead to an extreme change in the fitness, and hence, the evolution algorithm turns into stochastic search. Examples can be found in the literature where either the first or the second precondition is violated and where the evolutionary algorithm does not work effectively.

In the present paper we investigate an evolutionary game where each individual is a set of points, i.e. a team, which solves a well defined problem by cooperative behavior, i.e., by “team work”. In the beginning neither the number of points per team $`N_{min}`$ which is necessary to solve the problem nor the detailed solution is known. Both have to be found during the evolutionary game. Formally, one can consider the solution to be a subspace of the configuration space of dimension $`2N_{min}`$.

It will be shown that even if we knew the number of necessary points it would be favourable to solve first a simpler problem, in which the teams consist of more points than necessary, and then stepwise to increase the complexity of the problem by reducing the number of points. Solving such a hierarchy of problems and using the solution of a simple problem as the initial condition for the next difficult problem can be much more effective.

## 2 Description of the Problem

Assume we have a complicated shaped room with polygonal ground-plan. The $`M`$ even walls of the room have to be illuminated completely using a set of $`N`$ light bulbs. The questions which will be investigated here are: How many light bulbs are needed at minimum to illuminate the walls of the room, and where to place them?

Although we cannot provide a proof for $`NP`$-completeness of the problem, probably most people will agree that this problem is complex in the general case. There is a short proof for the upper limit of bulbs needed to illuminate a room bounded by $`M`$ even walls ?. Provided that the room does not have columns one does not need more than $`N=M/3`$ bulbs, where $`a`$ denotes the integer of $`a`$. Figure 1 displays a room where one needs indeed $`N=M/3`$ bulbs. In many cases, however, significantly less than $`N=M/3`$ are necessary for complete illumination. We want just to note that for the case that the room has $`S`$ inner columns (of polygonal cross section) one claims (?) that $`N=(M+S)/3`$ lamps are needed, where $`M`$ includes the number of walls of the room and of the columns. So far, however, there is no proof.

Fig. 1. In the drawn case of a room with 15 walls we find the worst case where $`N=15/3=5`$ light bulbs will be needed to illuminate the walls completely. The dots show the positions of the bulbs.

A related problem is the so called gallery watchman problem?. The question here is how many (static) watchmen are needed to watch the walls of a museum (e.g. ?), or in the dynamic formulation what is the shortest path of a watchman to pass through all points of interest. There are many formulations of the watchman problem and much theoretic work has been done in this field (e.g. ?,?,?,?,?). A technical application of a one dimensional version of the dynamic watchman problem solved by an evolutionary algorithm was recently investigated by Heckman ?. A machine consisting of a number of pickers assembled in a linear array across a conveyor belt was optimized to pick up pieces which move on the conveyor. The algorithm had to decide which of the pickers picks up the next coming piece.

In the case of our problem we assume that the room has no columns, therefore the number $`N_{min}`$ of actually needed lamps is always less than the third of the number of walls $`N_{min}M/3`$. The fitness $`F`$ of an individual, i.e., of a set of light bulbs, is given by the illuminated area***Since the problem is two dimensional we may call the length of a certain part of the border of the room area. of all walls

$$F_i=\frac{\underset{i=1}{\overset{M}{}}k_i}{\underset{i=1}{\overset{M}{}}l_i},$$
(1)
where $`k_i`$ is the illuminated area of the $`i`$th wall and $`l_i`$ is its total area. Hence we find for the fitness $`F[0,1]`$. During the optimization we try to maximize $`F`$ by changing the positions of the light bulbs. The solution is found when we have determined the positions of the minimum of a number of bulbs to illuminate the room, i.e. $`F=1`$. The function $`F`$ is embedded in the $`2N`$ dimensional space of the coordinates of the $`N`$ bulbs. It may have a complex topology, in particular numerous discontinuities, local extrema and flat plateaus. Hence a simple gradient strategy would fail to find the optimum and one has to chose a more sophisticated optimization strategy. In light of the generally used classification scheme introduced by Schwefel ? our algorithm is of $`(\mu ,\lambda )`$–type.

Each individual $`\alpha `$, ($`\alpha =1\mathrm{}\mu `$) in our evolutionary game is a set of $`N_{max}NN_{min}`$ light bulbs, where $`N_{max}=M/3`$ and $`N_{min}`$ is the (unknown) minimal number of bulbs which are needed to illuminate the room. The algorithm starts with $`\mu `$ of such individuals, the positions $`\stackrel{}{S}_i^\alpha `$, $`i=1\mathrm{}N`$ of the lamps are random. The optimization scheme reads as follows:

1. The individuals are mutated by varying the position of each lamp

$$\stackrel{}{S}_{i}^{}{}_{}{}^{\alpha }\stackrel{}{S}_{i}^{}{}_{}{}^{\alpha }+m_w\stackrel{}{A}_i^\alpha ,$$
(2)
with $`i[1,N]`$ and $`\alpha [1,\mu ]`$. The components of the two dimensional vector $`\stackrel{}{A}_i^\alpha `$ are chosen equally distributed from the interval $`[0,1]`$. The mutation step length $`m_w`$ is constant. To avoid that the individuals persist in deep local maxima, with a small frequency $`P`$ the new position of a lamp is completely random.
2. All individuals are rated by means of the fitness function (1).
3. If no set $`\alpha [1\mathrm{}\mu ]`$ solves the problem, i.e. $`F_\alpha 1`$, the $`\lambda `$ sets of lamps (individuals) with the highest fitness values are copied and brought over to the next generation. The remaining $`\mu \lambda `$ individuals die out. Steps 1 to 3 are to be repeated until at least one of the individuals has the fitness $`F_\alpha =1`$.
4. If at least one individual has fitness $`F=1`$, the solution is found and we start to solve the next difficult problem, i.e., we try to solve the same optimization problem, now with each individual consisting of $`N1`$ lamps only. The solution of the previous problem with $`N`$ lamps is used to initialize the new positions of $`N1`$ lamps per individual: The winning individual with fitness $`F=1`$ is copied $`\mu `$ times and for each individual one randomly chosen lamp is removed. Then we start the new optimization run with $`N1`$ bulbs beginning with item 1.

This procedure is continued until no solution can be found anymore. The last solution, found by the algorithm will be assumed to be the solution of the optimization problem stated at the beginning of this paragraph.

## 3 Results and discussion

The proposed algorithm was applied to illuminate a room ($`M=82`$) with the ground-plan shown in Fig. 2. The solution given by $`N_{min}=10`$ crosses was found during an evolutionary game of $`\mu =60`$ individuals. The optimization parameters were $`\lambda =5`$, $`P=10^3`$ and $`m_w=\mathrm{min}(x_{max},y_{max})10^2`$ where $`x_{max}`$ and $`y_{max}`$ denote the maximum extent of the room in the $`x`$\- and $`y`$-directions respectively.

Fig. 2. Solution with $`N_{min}=10`$ lamps for an arbitrary created room with $`M=82`$ walls. The position of the lamps are drawn with (+)- and (\*)-symbols. The room is completely illuminated, one can easily check that each place of the wall can be connected by a straight line with at least one lamp without intersecting the wall. The shadowed area displays the section which is illuminated by the lamp which position is given by the (\*)-symbol.

The parameters were chosen to give a satisfying efficiency of the optimization for a much simpler room. We did not further optimize these parameters, because the aim of the paper is to present a new optimization scheme but not to improve the efficiency of the well-known evolutionary algorithm. For the optimization of the parameters see e.g. ref. ?.

In Fig. 3 the fitness $`F_I`$ of the fittest individual $`I`$ is plotted versus the number of evolutionary steps. We start up with random sets of $`N=N_{min}=10`$ lights. The fitness is not monotonously increasing in time but there are long periods of stagnation interrupted by rapid jumps in the fitness. (Note that the abscissa is drawn in log scale.) This behavior, which seems to be typical for evolutionary processes was observed by several authors for various problems before, e.g. ?, and substantiated theoretically (see ?).

Fig. 3. Time evolution of the fitness $`F`$ of the best individual for four runs starting with different initial conditions. There are long periods of nearly constant fitness interrupted by short periods of rapid fitness increasing.

Usually a priori we do not know the number $`N_{min}`$ of lamps needed to illuminate the room and we start the optimization procedure with $`N_0>N_{min}`$ lamps per individual. But even if we would know the number it would be favourable to start with a larger amount of lamps than needed. In the following we will show and explain, that the algorithm for our optimization problem is up to about 10 times faster for that case.

To ensure approximately the same amount of computer time for each evolutionary step unaffected by the number of lamps each set consists of, the number of individuals $`\mu `$ was chosen

$$\mu =\mu _{max}\frac{N_{min}}{N_0},$$
(3)
where $`\mu _{max}=60`$ is the number of individuals for an optimization starting with $`N_0=N_{min}`$ light bulbs per individual. Hence, we can identify the number of evolutionary steps with time when we assume that the computer time needed for each step is mainly determined by the time required to calculate the fitness, i.e., it is proportional to the total amount of light bulbs.

Fig. 4. Number of optimization steps $`t`$ to find the final solution versus the number of bulbs $`N_0`$ in the starting iteration. The computer time which is proportional to the number of iteration steps decreases with increasing $`N_0`$ and reaches a minimum at $`N_0=16`$. For larger $`N_0`$ the value increases slowly.

Fig. 4 shows that the algorithm is in average about 10 times faster if one starts with sets consisting of $`N_0=16`$ lamps instead of the required $`N_{min}=10`$. Each data point in this figure is the mean value of the needed optimization steps of five runs with different starting configurations. The data show that the time needed to compute the solution decreases with increasing starting number of lamps for $`N_0<16`$. When we start with larger sets $`N_0>16`$ the computer time increases slowly. There are two mechanisms responsible for this behavior:

1. Suppose we would do stochastic search, and suppose there would be a unique solution for the optimization problem. If we assume that $`\tau `$ is the time a single searcher needs to find one particular of the $`N_{min}`$ places then $`N`$ random independent searchers need the time

$$\tau ^{}=\frac{\tau }{NN_{min}}$$
(4)
to find any of the places. The aspect of team work is included by assuming that a searcher who has found “its place” will not leave this place until the solution of the problem is found: It will survive the following evolutionary steps. Then we find for the time to find all places, i.e. to solve the optimization problem

$$T(N)=\underset{i=0}{\overset{N_{min}1}{}}\frac{\tau }{\left(Ni\right)\left(N_{min}i\right)}.$$
(5)
By replacing the sum by an integral we get the analytic solution

$`T(N)`$ $``$ $`\tau {\displaystyle \underset{\frac{1}{2}}{\overset{N_{min}\frac{1}{2}}{}}}{\displaystyle \frac{1}{(Nx)\left(N_{min}x\right)}}𝑑x`$ (6)
$`={\displaystyle \frac{\tau \mathrm{ln}\left(\frac{2N1}{\left(2N_{min}1\right)(2N2N_{min}+1)}\right)}{N_{min}N}}.`$
Obviously $`T(N)T(N+1)`$ is a positive number, i.e. the solution will be found quicker when starting with $`N+1`$ lamps instead of $`N`$.

Fig. 5. Number of optimization steps $`T_N`$ versus the number of lamps $`N`$. The averaged data over five runs of the evolution algorithm are drawn by crosses and error bars. The full line and the dashed line show the estimates due to eq. (5) and the last term of the sum in eq. (5) respectively. The time $`\tau `$ has been assumed to be a fit parameter.

Apart from this simple estimate we realize that typically the “attractor regions” for the positions of the bulbs do not have the same size but their sizes differ significantly. Usually the positions with the smallest “attractors” are found at the end of the optimization procedure, and the time is mainly determined by the last term of the sum in eq. (5). To provide better estimate one needs knowledge about the fitness landscape of the problem. For very simple problems it has been shown that one can conclude the properties of convergence based on knowledge od statistical properties of the fitness landscape ?.

Fig. 5 shows the results from the optimization as well as the discussed estimates.

Fig. 6. Sample optimization runs. After finding a solution for $`N_0>N_{min}`$ lamps the algorithm finds quickly the solution for smaller $`N`$. In accordance with fig. 4 the algorithm becomes slightly less effective when starting with larger $`N_0`$ (Explanation see text).
2. Fig. 6 shows the progress of the optimization procedure for $`N_0=\{16,18,20,22\}`$ lights in the starting configuration. One should read the figure from right to left: the ordinate shows the number of evolution cycles which have been necessary to solve the problem for $`N`$ lamps. In the case of the run started with $`N_0=18`$ light bulbs the solution for $`N=N_{min}`$ was found almost exclusively by removing lights.

Fig. 4 shows that the optimization time rises slightly for large $`N_0`$. Comparing the solutions of one optimization run for different $`N`$ we note that for $`N_0\stackrel{<}{}18`$ the initial solution (for $`N=N_0`$) is frequently very close to the final solution (for $`N=N_{min}`$). Hence, the solution for $`N1`$ lamps can be found from the solution for $`N`$ lamps just by deleting one of the lamps and performing few evolution steps (see Fig. 6).

For $`N_0\stackrel{>}{}18`$ the initial solution could differ very much from the final solution, and also the solutions of the successive problems for $`N_0`$, $`N_01\mathrm{},N_{min}`$ differ from each other. The solutions are not really adapted to the geometry of the room, but they are more the results of a random search. Therefore the system does not take too much advantage from knowing the solution for $`N`$ lamps solving the problem for $`N1`$ lamps. Hence the calculation time in Fig. 4 rises slightly for larger values of $`N`$. Nevertheless the algorithm is still much faster compared with the time needed for the solution starting with $`N=N_{min}`$ bulbs.

The situation is quite similar to a neural network applied to a pattern recognition problem: if it has too many neurons the network just stores the patterns instead of finding characteristic features (e.g. ?). If this network is applied to an unknown pattern it fails since none of the stored patterns has enough overlap with the unknown pattern. A network with less neurons might be able to solve the problem since it checks whether the unknown pattern reveals characteristic features.

## 4 Conclusion

We have shown that for the investigated problem it is favourable to start the optimization with more points than necessary $`N_0>N_{min}`$. First we find a solution, i.e. the positions of the points for a higher number of points, and then we stepwise decrease $`N`$ while using the solution for $`N`$ as initial condition for finding the solution for $`N1`$ points. It turns out that the procedure to solve the chain of problems for $`N_0,N_01,N_02,\mathrm{},N_{min}`$ is up to about ten times faster then to solve the problem for $`N_{min}`$ directly. Formally we first solve the optimization problem in a high dimensional space of dimension $`2N_0`$. Once the solution is found we stepwise reduce the dimensionality and end up with dimension $`2N_{min}`$.

The theoretical basis of the optimization speedup in higher dimension is provided by Morse theory ?. Qualitatively Morse Lemma says that under rather mild assumptions the fraction of saddle points of a function of its critical points rises with dimension. Hence the relation of extrema and saddle points decreases when increasing the dimension. The idea of the lemma becomes clear in one and two dimensions: to reach the optimum of a one dimensional function one has to “walk through” all local extrema in between the starting point and the global extremum. In two dimensions in many cases one can “walk around” local extrema and hence one avoids time consuming escape procedures. Similar in higher dimension: the higher the dimension the more bypasses do exist to reach a certain point without getting stuck in local extrema.

We assume that this behavior is typical for a certain class of optimization problems. The main characteristic of this class is that the problem can be transformed into another problem containing a parameter $`N`$ where the solution of the original problem with the parameter being $`N^{}`$ is contained in the set of solutions of the easier to solve problems with $`NN^{}`$. Obviously the entire class of coverage problems belongs to this class. Further investigations will be necessary to substantiate this hypothesis. For the problem of the travelling salesman, for instance, the easier task could be to find a minimal length where some cities ($`N`$) are allowed to be visited twice, followed by a successively reduction of the number of those cities.

The authors thank T. Asselmeyer, W. Ebeling, H. Herzel, G. Rudolph and L. Schimansky-Geier for stimulating discussions. V.B. thanks project EVOALG (BMBF) for financial support.

## 5 References