text:
# The properties of the absorbing and line emitting material in IGR J16318-4848

## 1 Introduction

IGR J16318-4818 was discovered by the ISGRI detector of the IBIS instrument onboard the INTEGRAL satellite (Corvoisier et al. 2003) on January 29, 2003, with a 15–40 keV flux of 50–100 mCrab. It was initially interpreted as a new ”transient” X-ray source. However, a reanalysis of archival ASCA data revealed the presence of a source whose position was coincident with that of IGR J16318-4818 (Murakami et al. 2003), and with a 2–10 keV observed flux of about $`4\times 10^{11}`$ erg cm-2 s-1.

The INTEGRAL discovery prompted a Target of Opportunity observation with XMM-Newton (Jansen et al. 2001) on February 10, 2003. The EPIC spectra unveiled a variable and strongly absorbed source, with evidence for strong emission lines (Schartel et al. 2003). This is in agreement with the ASCA source, in which Revnivtsev et al. (2003) suggested a column density $`>4\times 10^{23}`$ cm-2. Preliminary spectral fits (de Plaa et al. 2003) indeed suggested that during the XMM-Newton observation IGR J16318-4818 was obscured by a Compton-thick absorber \[$`N_H=(1.66\pm 0.16)\times 10^{24}`$ cm-2; all errors quoted hereinafter are at the 90% confidence level for one interesting parameter\]. The emission complex could be resolved in three lines, with centroid energy of $`6.410\pm 0.003`$ keV, $`7.09\pm 0.02`$ keV and $`7.47\pm 0.02`$ keV.

In this paper we exploit the unprecedented sensitivity of the EPIC detectors above 5 keV (where fluorescent transition of Fe and Ni are concentrated) to characterize the physical properties of the matter responsible for the obscuration of the X-ray source and the associated reprocessing features. To achieve this goal, we compare the spectral fit results (presented and discussed in Sect. 3.1 of this Letter) with Monte-Carlo simulations of the X-ray transmission by neutral matter (Matt et al. 1999; Matt 2002; see Sect. 3.2), originally developed in the context of obscured AGN. We demonstrate in this paper that a proper modeling of the scattering effect is crucial to correctly identify the properties of the absorber, as standard fits with approximate model can grossly overestimate the actual absorbing column density and covering factor of the obscuring matter. Study of the spectral variability during the XMM-Newton observation allowed us to set stringent constraints on the geometry of the absorbing matter (see Sect. 3.3). Our findings and conclusions are summarized in Sect. 4.

## 2 Data reduction

In this paper, we discuss the pn data only (Strüder et al. 2001), as this instrument seems to be the best calibrated among the EPIC cameras (see, for instance, the discussion in Molendi et al. 2003), at least in their highest energy band.

Data were retrieved from the XMM-Newton Target of Opportunity public WEB page as Observation Data Files (ODF), and reprocessed with SAS v.5.4.1, using a calibration index file corresponding to the most updated calibration files available at February 21, 2003. Spectra were extracted from a circular region around the source centroid ($`\alpha _{2000}=16^h31^m48^s.6`$, $`\delta _{2000}=48^o49\mathrm{}00\mathrm{}`$; Schartel et al. 2003) with a 52$`\mathrm{}`$ radius. As the extraction region encompassed two CCDs, background spectra were extracted from a nearby source-free region, having the same area ratio between the two chips as the source extraction region. We verified that the results are not substantially different, if the source and background pn spectra are extracted from a smaller region (11$`\mathrm{}`$ radius), fully comprised in the same CCD. The spectra were accumulated using single- and double-events. Pile-up is negligible, as well as the contribution of the background, lower than 0.1% in the 5–15 keV energy band. Nevertheless, a short interval of about 1.25 ks duration, where the background count rate (calculated on the single-event light curve extracted above 10 keV) exceeded 1 $`s^1`$, was removed from the scientific product accumulation. The background is otherwise quite stable. The fits described in this Letter were performed with XSPEC v.11.1.

## 3 Data analysis and results

### 3.1 Time integrated spectrum: summary of spectral results

As already noted by de Plaa et al. (2003), the XMM-Newton spectra are characterized by a heavily absorbed continuum and 3 emission lines. The lines are most naturally interpreted as the Fe K$`\alpha `$ and K$`\beta `$ and the Ni K$`\alpha `$. We therefore fitted the spectrum (in the 5-13 keV energy band, as below 5 keV a small excess emission is present, see below) with the simplest possible model: an absorbed power law plus three (unabsorbed) narrow (i.e. intrinsic width, $`\sigma `$, fixed to 1 eV) Gaussian lines. The photoelectric absorption model varabs has been used with element abundances from Anders & Grevesse (1989) and photoelectric cross sections from Balucinska-Church & McCammon (1992). We left the iron abundance free to vary independently of the other elements. As the absorbing matter results to be Compton–thick (see below), we included also Thompson absorption (model cabs). It is worth noting that this model, ignoring the scattering of photons, is, strictly speaking, valid only for absorbing matter along the line of sight with a negligible covering factor (see below for a discussion),

The fit is reasonably good ($`\chi ^2`$=99.1/64 d.o.f.), but residuals around the iron K$`\alpha `$ line are visible, most likely due to the Compton Shoulder (CS), as already observed in the reflection spectrum of the Circinus Galaxy (Bianchi et al. 2002; Molendi et al. 2003), and expected on theoretical ground (see Matt 2002 and references therein). Modeling for simplicity the Compton Shoulder with a Gaussian with centroid energy fixed to 6.3 keV, and $`\sigma `$ fixed to 50 eV, a significant improvement is found ($`\chi ^2`$=80.9/63 d.o.f., corresponding to 99.96% confidence level). In the following we will refer to the complete model (absorbed power-law plus 4 Gaussian emission lines) as the baseline model. The best fit results are summarized in Table 1. The observed 2-10 keV flux is 6.7$`\times `$10-12 erg cm-1 s-1. The flux corrected for absorption is instead 1.1$`\times `$10-9 erg cm-1 s-1, corresponding to a luminosity of 1.3$`\times 10^{37}d_{10}^2`$ erg s-1, where $`d_{10}`$ is the distance to the source in units of 10 kpc.

Given the large column density of the line–of–sight absorber, if the covering factor of the absorbing matter is large, a significant contribution from photons scattered towards the line of sight is expected, as discussed in Matt et al. (1999). We therefore fitted the spectrum with the Monte-Carlo model described in that paper. The fit is completely unacceptable. This may be due to the fact that the model has been calculated adopting the Morrison & McCammon (1983) cross sections, which made use of the Anders & Ebihara (1982) element abundances. In this set the iron abundance is about 0.7 times that given by Anders & Grevesse (1983), while from Table 1 it seems that the actual iron abundance (mainly derived in the fit from the depth of the iron edge) in the absorbing material is closer to the one given by the latter authors. Moreover, the Matt et al. (1999) model assumed spherical geometry and homogeneous matter, while the covering factor may be significantly smaller than one and the average column density smaller than that on the line–of–sight (see below).

Coming back to the results summarized in Table 1, we must first of all remark that the rather small errors on $`\mathrm{\Gamma }`$ and NH are somewhat misleading. In fact, as it is clear from the contour plot (Fig. 1), the $`\chi ^2`$ distribution is shallow and not very smooth. The calculated errors correspond to the $`\mathrm{\Delta }\chi ^2`$ in the vicinity of the best fit, but other regions with $`\mathrm{\Delta }\chi ^2`$ less than 2.71 do exist. We have verified that NH and AFe are only slightly correlated each other. To avoid problems in the estimate of the errors for the line parameters, we fixed $`\mathrm{\Gamma }`$ and NH to their best fit values. This does not affect very much the errors on the Fe and Ni K$`\alpha `$ lines, but stabilizes the values for the Fe K$`\beta `$, which otherwise would be very difficult to find, due to its proximity to the iron edge.

### 3.2 The physical properties of the absorber

The energies of the Fe and Ni K$`\alpha `$ lines correspond to neutral or low ionized atoms (House 1969). On the contrary, the Fe K$`\beta `$ centroid energy is significantly larger than expected. This cannot be due to high ionization, not only because it does not agree with the K$`\alpha `$ energy, but also because for significantly ionized matter the K$`\beta `$ line becomes much fainter, to disappear completely for Fe xvii or more, when no M electrons remain. Instead the observed K$`\beta `$/K$`\alpha `$ ratio ($`0.20\pm _{0.03}^{0.02}`$) is slightly larger than expected for neutral iron (see the discussion in Molendi et al. 2003, where however the matter was seen in reflection, not transmission; the arguments given there must therefore be taken with caution, until proper calculations will be available). It should however be noted that, given the proximity to the iron edge, the parameters of the K$`\beta `$ line are necessarily difficult to estimate, and may suffer from a too simple modeling of the edge (Palmeri et al. 2002).

The Ni to Fe K$`\alpha `$ line ratio is about 6%, suggesting a possible Ni overabundance (see again the discussion in Molendi et al. 2003, with the same caution given above). In Table 1, the EW of the lines with respect to the unabsorbed continuum (to make easier the comparison with the expected value for the iron K$`\alpha `$ presented in Matt 2002), are also given. The value reported in Fig. 1 of Matt (2002) are for Morrison & McCammon (1983) abundances, and a power law index of 2. We therefore calculated the expected Fe K$`\alpha `$ properties using the code described in Matt (2002), adopting the Anders & Grevesse abundances and the best fit value for $`\mathrm{\Gamma }`$, NH, and AFe. The expected value of the ratio, $`f`$, between the Compton Shoulder and the line core is 0.44, to be compared with a measured value of $`0.12\pm _{0.05}^{0.04}`$. $`f`$ does not depend much on the geometry, but rather on the column density (Matt 2002). The observed value would correspond to a column density of a few $`\times 10^{23}`$ cm-2, for which values around 100 eV of the EW are expected (a value of about 20 eV is instead expected for 1.9$`\times 10^{24}`$ cm-2). The observed EW is instead about 13 eV. It is then possible that the matter is very inhomogeneous, with a denser blob just on the line of sight (which is what the fit can measure) but an average optical depth an order of magnitude less, and a covering factor, taking into account the uncertainties on the power law index, of about 0.1–0.2. The lower (with respect to the line of sight) average column density, along with the relative small covering factor, would explain the failure of the Matt et al. (1999) model in fitting the data.

Because there is evidence that the absorbing material has a covering factor less than 1, part of the X–ray illuminated surface should be directly visible, producing a Compton reflection component (George & Fabian 1991; Matt, Perola & Piro 1991) as commonly observed in Compton–thick AGN (Matt et al. 2000 and references therein). As discussed above, the average column density is possibly as low as a few $`\times 10^{23}`$ cm-2; however, below the iron line energy the reflection component for this column density is very similar to that for Compton–thick matter (Matt et al. 2003). This component could therefore account for the excess emission below 5 keV (see Fig. 2, where the whole 0.3-13 keV spectrum is shown, after being fitted with the baseline model), and down to about 2 keV (the further excess at lower energies should have a different origin). Fitting the 2-13 keV spectrum with the baseline model gives $`\chi ^2`$=104.9/68 d.o.f., and a very flat ($`\mathrm{\Gamma }`$=0.6) power law. The addition of a pure Compton reflection component (with the photon index linked to that of the absorbed power law, and fixed to 1.6) improves the fit significantly, giving $`\chi ^2`$=79.9/68 d.o.f.. The value of $`R`$, 0.003, implies that the visible part of the illuminated matter is very small ($`R`$ is equal to 1 for 2$`\pi `$ visible solid angle, i.e. a covering factor of 0.5). As the source lies on the Galactic plane, absorption from interstellar matter is likely to be significant. We then added an absorption component, but the fit does not significantly improve ($`\chi ^2`$=77.9/68 d.o.f.). The best-fit face value for the column density of this further absorber is about 5$`\times 10^{22}`$ cm-2, and $`R`$=0.0045. (If this is indeed the column density of the interstellar absorption, the emission below 2 keV is likely due to another, nearby confusing source.) The other parameters are similar to those listed in Table 1. The iron line EW with respect to the reflection component is very large, $``$28 keV, implying that almost all of the line is related to the transmitted component. Of course, part of the excess emission may be due to photons scattered in transmission rather than reflection, i.e. escaping from the far side (with respect to the X-ray source) of the obscuring matter.

The small value of $`R`$ may, at the first glance, appears rather surprising, given the value of the covering factor deduced from the iron line EW and the CS (about 0.1). It may be explained if, e.g., the absorber has a flat configuration (similar to the ‘torus’ envisaged in Unification Models for AGN), seen at high inclination.

### 3.3 Time resolved spectra

IGR J16318-4848 exhibits a complex variability pattern during the XMM-Newton observation (see Fig. 3). The pn flux varied by a factor of 2.5 during the first 8 ks, stabilized at a constant level of $``$0.15$`s^1`$ (0.5-15 keV band) for the next 13 ks and than underwent a sudden burst, brightening by a factor $``$3 within $``$500–1000 s. This behavior is associated with spectral variability. In Fig. 4 we show the count spectra extracted in the 3 consecutive different time intervals highlighted in Fig. 3: 0–8 ks, 8–18.5 ks, and 18.5–25 ks (elapsed time) after the observation start. The exposure times corresponding to the three spectra are 7.7, 7.3 and 5.1 ks, respectively.

To test whether the flux variations are due to a change in the column density of the absorber, or rather in the properties of the primary emission, we performed three different fits: with $`\mathrm{\Gamma }`$ and the normalization of the power law kept fixed to the time integrated best fit values (baseline model), and NH free to vary (model 1); with only $`\mathrm{\Gamma }`$ fixed and the normalization and NH free (model 2); and with $`\mathrm{\Gamma }`$ and normalization free and NH fixed (model 3). For the sake of simplicity, the fits have been performed in the 5-13 keV energy band. Hereinafter, all fits have been performed with the centroid energies of the emission lines (which do not exhibit significant evidence for variations among the time-resolved spectra) and the relative iron abundance kept fixed to the best fit values for the baseline model, as reported in Table 1. The resulting $`\chi ^2`$ are given in Table 2. While for the 2nd interval all models are acceptable, for the 1st and 3rd intervals model 1 is unacceptable, while model 2 and 3 are both acceptable. For model 2, the best fit values of NH are (see also Table 3): 1.76$`{}_{0.10}{}^{}{}_{}{}^{+0.11}`$, 1.93$`{}_{0.12}{}^{}{}_{}{}^{+0.15}`$ and 2.06$`{}_{0.09}{}^{}{}_{}{}^{+0.09}`$. For model 3, the best fit values of $`\mathrm{\Gamma }`$ are: 1.85$`\pm _{0.10}^{0.20}`$, 1.55$`\pm `$0.19 and 1.30$`\pm `$0.18.

In Table 3 the best fit parameters for the absorbing column density and the 8–15 keV and line fluxes (obtained with model 2; the results on the line fluxes are similar if model 3 is adopted) are summarized. It is interesting to note that the fluxes of the lines are correlated with the flux of the continuum; the only exception is the Compton shoulder, but the errors are pretty large. This applies in particular for the spectra corresponding to Interval 2 (pre-burst) and 3 (post-burst). The ratios of the iron line fluxes between the post- and pre-burst phases ($`1.8\pm 0.2`$ and $`2.4\pm _{1.3}^{0.8}`$ for K$`\alpha `$ and K$`\beta `$, respectively) are comparable with the average 8–15 keV continuum flux ratio between the same intervals ($`2.41\pm 0.04`$). To further explore the relation between the emission line and the continuum fluxes, in Fig. 5 the light curves for the 8–15 keV (which is dominated by the continuum) and the 6–6.6 keV (dominated by the iron K$`\alpha `$ line) are shown. The line varies on time scales as short as 1000 s, implying that the size of the emitting region cannot be larger than about 3$`\times 10^{13}`$ cm, consistent with a scenario in which the absorbing matter is e.g. due to the stream of material flowing through the Lagrangian point in a Roche Lobe overflow, to eventually form an accretion disc.

The line flux follows the variations of the continuum, but not precisely, as it is clear from the line–to–continuum flux ratio (lower panel of Fig. 5), suggesting that on these time scales also the properties of the cold matter, i.e. the covering factor and/or the average column density, change.

## 4 Summary

We have performed a detailed analysis of the XMM–Newton observation of IGR J16318-4848, in order to characterize the properties of the matter responsible for the obscuration along the line-of-sight and for the emission of Fe and Ni lines. Our results can be summarized as follows:

a) the line of sight material has a column density of about 2$`\times 10^{24}`$ cm-2;

b) from the value of the Fe K$`\alpha `$ line EW and Compton Shoulder, an average column density of a few $`\times 10^{23}`$ cm-2 (indicating dishomogeneous or blobby material) and a covering factor of about 0.1–0.2 are estimated;

c) the small value of the Compton reflection component suggests a flat configuration of the matter, with a large inclination angle;

d) the iron K$`\alpha `$ line varies on time scales as short as 1000 s, implying a size of the emitting region not exceeding $`3\times 10^{13}`$ cm. The flux of the line roughly follows the variations of the continuum, but not exactly, suggesting a variation of the geometrical properties of the emitting region on similar time scales.

Finally, a few words on the putative “transient” nature of this source. A reanalysis of an archival 1994 ASCA observation (Murakami et al. 2003) points to a flux variation of a factor of just a few in about 8.5 years. The comparison between the flux measured by INTEGRAL in the 15–40 keV and by XMM-Newton in the 5–15 keV is not conclusive, given the large uncertainties associated with the determination of the intrinsic flux in such an absorbed source. Therefore, it cannot be ruled out that the XMM-Newton (and ASCA) observations represent already its normal flux level.

## Acknowledgments

This work is based on observations obtained with XMM-Newton, an ESA science mission with instruments and contributions directly funded by ESA Member States and the USA (NASA). The XMM-Newton Science Operation Center is gratefully acknowledged for having produced with unprecedented speed, and made publicly available ODF for the observation described in this paper.


format: text

text:
# Temperature dependent optical studies of Ti1-xCoxO2

## Abstract

We present the results of Raman and photoluminescence (PL) studies on epitaxial anatase phase Ti1-xCoxO2 films for $`x`$ = 0-0.07, grown by pulsed laser deposition. The low doped system ($`x`$=0.01 and 0.02) shows a Curie temperature of 700 K in the as-grown state. The Raman spectra from the doped and undoped films confirm their anatase phase. The photoluminescence spectrum is characterized by a broad emission from self-trapped excitons (STE) at 2.3 eV at temperatures below 120 K. This peak is characteristic of the anatase-phase TiO2 and shows a small blueshift with increasing doping concentration. In addition to the emission from STE, the Co-doped samples show two emission lines at 2.77 eV and 2.94 eV that are absent in the undoped film indicative of a spin-flip energy.

Dilute magnetic semiconductors (DMS) based on II-VI semiconductors, such as Mn-doped CdTe and ZnSe, furdyna  and III-Vs, such as Mn-doped GaAs ohno  have been studied extensively in the last decade due to their potential usage of both charge and spin degrees of freedom of carriers in electronic devices. However, these materials undergo a ferromagnetic phase transition temperature much below room temperature. The discovery of ferromagnetism with Curie temperatures above 300 K in cobalt-doped TiO2 has generated considerable amount of interest in this system and similar oxide based ferromagnetic semiconductors.matsumoto ; shinde  First-Principles calculations of Co-doped TiO2 elucidate on the electronic structure and microscopic distribution of Co atoms crucial for ferromagnetic ordering.park ; yang  Recently, Mn-doped GaN films are also known to show room temperature ferromagnetism.Reedgan ; sasakigan

TiO2 is a wide band gap semiconductor with excellent transmittance in the visible and near-infrared regions, high refractive index, and high dielectric constant. It occurs in three crystal structures: rutile, anatase, and brooklite. Anatase TiO2 is composed of stacked edge-sharing octahedrons formed by six oxygen anions. There are significant differences in the electronic structure between the anatase and rutile crystal structures. Anatase TiO2 has a very shallow donor level and high electron mobilities compared to the rutile phase.forro  The $`n`$-type carriers in TiO2 result from oxygen vacancies, which provide tunability to its properties. Detailed investigations of the absorption edges in anatase and rutile phases by Tang et al. have shown that that the excitonic states of the anatase phase are self-trapped while that of the rutile phase are free.tang1

In this work we present the results of Raman and photoluminescence (PL) studies on epitaxial anatase phase Ti1-xCoxO2 films for $`x`$ = 0, 0.01, 0.02, 0.04, and 0.07, grown by pulsed laser deposition (PLD). Thin films of Ti1-xCoxO2 were deposited at a pressure of 2-4$`\times `$10-5 on LaAlO3 (001) substrates by PLD, using sintered targets synthesized by the standard solid-state route. The substrate temperature, laser energy, and pulse repetition rate were kept at 700 oC, 1.8 J/cm2, and 10 Hz, respectively. The thickness of the films were $``$100nm.

X-ray diffraction (XRD) was employed for structural characterization. The hysteresis loops and magnetization were obtained using a SQUID magnetometer. The Raman measurements were carried out in a backscattering geometry using a fiber-optically coupled confocal micro-Raman system (TRIAX 320) equipped with a liquid N2 cooled charge coupled detector. The 514.5 nm line of an $`\mathrm{Ar}^+`$ ion laser was the excitation source. The microscope is equipped with a holographic super-notch filter to block the elastically scattered light. A 50 X microscope objective was used to focus and collect the scattered laser light, with a spatial resolution of about 5$`\mu `$m. The PL spectra were excited using the 363.8 nm line of an $`\mathrm{Ar}^+`$ laser. The luminescence excitation was analyzed with a SPEX 0.85 m double monochromator equipped with a cooled GaAs photomultiplier tube and standard photon counting electronics. For low temperature measurements a closed cycle refrigerator was employed.

Figure 1 (a) and (b) shows the XRD pattern and the magnetic response, respectively, of Ti0.98Co0.02O2 on LaAlO3 (001). The (004) and the (008) peaks of the anatase phase are clearly observed in the XRD. The XRD rocking curve full width at half maximum of the sample peaks are $``$0.3 o. The magnetic response was measured as a function of the magnetic field strength at room temperature. Hysteresis is observed indicating that the film is ferromagnetic even at room temperature. The low doped system ($`x`$=0.01 and 0.02) shows a Curie temperature of $``$ 700 K in the as-grown state.shinde

The anatase and the rutile phase belong to the symmetry space groups D$`{}_{4h}{}^{}{}_{}{}^{19}`$ and D$`{}_{4h}{}^{}{}_{}{}^{14}`$, respectively.ocana  Group theory predicts six Raman active modes for the anatase phase; Eg: 147 cm-1, Eg: 198 cm-1, B$`{}_{1}{}^{}g`$: 398 cm-1, A$`{}_{1}{}^{}g`$ and B$`{}_{1}{}^{}g`$: 515 cm-1, and Eg: 640 cm-1. The rutile phase has four Raman active modes, the predominant ones are Eg: 448 cm-1, A$`{}_{1}{}^{}g`$: 612 cm-1, and B$`{}_{1}{}^{}g`$: 827 cm-1. Since the Raman peaks from each phase are clearly separated in frequency, the two phases are easily distinguishable by their Raman spectra.

Figure 2 shows the Raman spectra from Ti1-xCoxO2 for various Co concentrations. The 485 cm-1 peak is from the LaAlO3 substrate and serves as a good calibrant. Since the notch filter cuts off energy positions below 200 cm-1, we do not observe the low energy Eg Raman peaks. The Raman peaks at 398 cm-1 and 515 cm -1 clearly show that the samples are in the anatase phase. A signature of the 640 cm-1 is observed for $`x`$ =0.01 and 0.02 samples. Within the experimental accuracy of a few wavenumbers there is no discernable shift of the Raman peaks of the sample with higher Co-doping concentration. However, for the higher Co-doped samples the Raman peaks broaden. This may be an indication of limited Co solubility resulting in a disorder of the crystal structure. A recent work by Shinde et al. shows that higher Co-doping (beyond $`x`$ =0.02) without annealing results in the formation of Co clusters in Ti1-xCoxO2.shinde

Though the absorption edge of anatase TiO2 is at $``$ 3.2 eV, the luminescence spectrum Stokes shifts by almost 1 eV. A broad greenish-yellow emission, centered at 2.3 eV is observed from films and crystals of anatase TiO2.tang1 ; kiisk  The TiO6 octahedra in the anatase phase are distorted to lower symmetry, which lifts degeneracies and creates band splitting resulting in a narrowing of the conduction band. The band-to-band excitation therefore results in self-trapped excitonic states due to a localization of the excited state and its energy is lowered by the lattice relaxation energy.tang1

Figure 3 shows the PL spectra of Ti1-xCoxO2 for various values of $`x`$, measured at 30 K. The spectra are characterized by a broad emission centered at 2.3 eV due to the self-trapped excitons. The individual spectra have been normalized to the 2.3 eV emission and vertically shifted for clarity. A recent work using polarized PL shows that this broad emission can be further resolved into at least two peaks centered at 2.2 eV and 2.4 eV.kiisk  The center of the self-trapped emission (STE) shows a slight blueshift in energy with increased doping concentration.

The most striking feature of Fig. 3 is the appearance of two peaks at 2.77 eV and 2.94 eV in the Co-doped samples which are absent in the undoped samples. At 30 K the 2.77 eV peak appears as a weak shoulder in the low doped samples. To understand the origin of the above peaks, we have carried out a thorough temperature dependence of the PL. Since higher cobalt doping leads to clustering in as-grown films,shinde  we compare the PL from undoped TiO2 to the low Co-doped samples as a function of temperature.

Figure 4 shows the PL spectra for a few selected values of temperature for (a) $`x`$=0.02 and (b) $`x`$=0.0 samples. The spectra have been normalized to the STE emission for both (a) and (b). With increasing temperature the intensity of the STE drops and beyond 120 K it is barely visible. For the $`x`$=0.02 sample the energy position of STE shows almost no shift with increasing temperatures. This is in contrast to other doped system, such as Al-doped anatase TiO2, where the STE redshifts by more than 500 mev from 5 K to 150 K due to trapping of excitons at higher temperatures by Al acceptor levels.tang1  Our results clearly show that the cobalt impurities do not result in any additional self-trapping mechanism.

The absolute intensities of the 2.77 eV and 2.94 eV PL peaks do not change significantly with temperature. Since the PL spectra are normalized to the STE peak in Fig. 4 (a), it appears that the 2.94 eV and the 2.77 eV peaks gain intensity upon increasing temperatures. These two peaks are not related to any oxygen vacancies. We have compared the PL spectra (at different temperatures) from two halves of the $`x`$=0.02 sample: one half being the as-grown and the other half was annealed in an oxygen atmosphere. The PL spectra at all temperatures from both samples are identical, eliminating any issues related to oxygen vacancies. The difference in energy of 170 meV between the 2.77 eV and the 2.94 eV peaks may be related to states with a given spin and a spin-flipped state.

Band structure calculations show that the valence band derives primarily from oxygen p-levels, the conduction band from the Ti d-levels and the crystal-field split Co d-levels fall within the energy gap. The local-spin-density approximation (LSDA) calculations by Park et al. show that the crystal field splitting between $`t_{2g}`$ and $`e_g`$ states is larger than the exchange splitting between $`t_{2g}`$ states, suggesting a low spin state of Co.park  The appearance of the 2.77 eV and the 2.94 eV energy levels in our PL spectra appear well below the absorption edge of 3.2 eV in Ti1-xCoxO2,simpson  indicating that they most probably arise from the cobalt $`e_g`$ energy levels. Moreover, the 170 meV difference between the two PL peaks agree well with the energy separation between the spin-up and spin-down $`e_g`$ states of the LSDA calculation.park

The location of Co midgap levels also depends on the nature of the microscopic distribution of the co atoms, as seen in the work by Yang et al.yang  The local oxygen non-stoichiometry (which influences the valence states of cations) also affects the band filling. Thus, the assignment of the observed levels to specific electronic states would require these inputs. Based on the total energies calculated for various configurations, Yang et al. suggest that cobalt ions in the Ti1-xCoxO2 matrix would prefer non-uniform doping mode with short Co-Co distances.yang  Future work involving magneto-optical techniques should reveal the nature of magnetic coupling and magnetic excitations from various Ti1-xCoxO2 configurations and their possible participation in optical processes.

###### Acknowledgements.

S.G. acknowledges the donors of the American Chemical Society Petroleum Research Fund Grant No. 38193-B7 and the Research Corporation Grant No. CC5332. Work at UMD is supported under NSF-MRSEC DMR Grant No.00-80008.


text:
# Random Graphs with Hidden Color

(March 16, 2024)

## Abstract

We propose and investigate a unifying class of sparse random graph models, based on a hidden coloring of edge-vertex incidences, extending an existing approach, random graphs with a given degree distribution, in a way that admits a nontrivial correlation structure in the resulting graphs. The approach unifies a number of existing random graph ensembles within a common general formalism, and allows for the analytic calculation of observable graph characteristics. In particular, generating function techniques are used to derive the size distribution of connected components (clusters) as well as the location of the percolation threshold where a giant component appears.

graph theory; random graph; stochastic process; phase transition; critical phenomena; percolation  preprint: LU TP 03-12

Introduction.
There is a growing interest in complex networks, in the physics community as well as in other sciences, partly due to an increased availability of data on real-world networks. This is reflected in a rapidly increasing number of models of random graphs Erdős and Rényi (1960); Bender and Canfield (1978); Watts and Strogatz (1998); Söderberg (2002); Berg and Lässig (2002) and dynamical random graphs Barabási and Albert (1999); Albert and Barabási (2000); Callaway et al. (2001); Turova (2002); Dorogovtsev et al. (2001), with varying degrees of generality.

This multitude of models calls for a unifying formalism, including more specific models as special cases, while allowing for the calculation of observable characteristics that can be compared to those of real networks. Dynamical models are interesting in their own right, but the dynamics is seldom directly observable in real-world networks, and we will focus on static ensembles of random graphs, irrespective of whether they result from a dynamical process or not.

Specifically, we will consider models of simple, undirected graphs that are sparse (the edge count grows linearly with the node count $`N`$) and truly random (having no underlying regular structure). The classic random graph in its sparse version is of this type Erdős and Rényi (1960); Janson et al. (2000); Bollobás (2001), where each of the $`N(N1)/2`$ possible edges is independently and randomly realized with a fixed probability $`p=c/N`$. It has a Poissonian asymptotic degree (connectivity) distribution with average $`c`$, and a percolation threshold at $`c=1`$. It fails, however, to describe most real-world networks.

Instead we turn to two of the more general approaches, based on slightly different philosophies. One, to be referred to as DRG (Degree-driven random graphs), amounts to chosing a random member from the set of simple labelled graphs with a given arbitrary degree distribution Bender and Canfield (1978); Molloy and Reed (1995); Newman et al. (2001). The other is Inhomogeneous random graphs Söderberg (2002), IRG, where the classic model is generalized by randomly coloring vertices according to a color distribution $`\{r_i\}`$, and realizing edges independently with color-dependent probabilities $`c_{ij}/N`$. Both yield analytically tractable models displaying well-defined percolation thresholds and degree distributions, both include a number of more specific models – and both have limitations: DRG fails to produce non-trivial edge correlations, as seen in the factorization of the combined degree distribution of connected vertex pairs Callaway et al. (2001); in IRG, the resulting degree distribution is limited to a mix of Poissonians Söderberg (2002).

These approaches are not unrelated: The restriction of DRG to degree distributions in the form of a Poissonian mix is in fact asymptotically equivalent to the restriction of IRG to a rank-one $`c`$ matrix, $`c_{ab}=C_aC_b`$ (exhibiting DRG’s lack of correlations); this common subset contains the classic model Söderberg (2002).

Basic Idea.
By combining the philosophies of DRG and IRG, a more general class of analytically tractable sparse random graph models can be constructed. This unifying approach, to be referred to as CDRG (for Colored DRG), contains IRG and DRG as particular subsets, and is defined as a direct extension of DRG by assigning a hidden color to each vertex connection (a half-edge, or stub). As a result each edge will be associated with a pair of colors, one for each endpoint. We then consider a given distribution $`\{p_𝐦\}`$ of colored degrees $`𝐦=(m_1\mathrm{}m_K)`$, where for each vertex its number $`m_k`$ of stubs of each color $`k`$ is accounted for, and allow the edge distribution to be color-sensitive by specifying also the distribution of edge color pairs. The resulting ensemble of stub-colored graphs yields, if the coloring is considered unobservable, a well-defined graph ensemble. The coloring thus can be thought of as a set of hidden variables, the purpose of which is to induce correlations in the resulting graphs.

Below, we will discuss the definition and implementation of CDRG models, derive the asymptotic cluster size distribution yielding equations for the percolation threshold, and identify the subsets corresponding to DRG (trivial) and IRG (less trivial).

Asymptotic Model Specification.
A particular asymptotic CDRG model is defined by specifying:

* a definite color space, say $`\{1,2,\mathrm{},K\}`$;
* an asymptotic colored degree distribution (CDD), $`p_𝐦`$, defining the relative frequencies of vertices with different colored degrees $`𝐦=(m_1,\mathrm{},m_K)`$, where $`m_a`$ is the number of $`a`$-colored stubs of the vertex. We will assume here that all its moments, $`m_a_𝐦p_𝐦m_a`$, $`m_am_b`$, etc., are defined;
* a symmetric, non-negative $`K\times K`$ color preference matrix $`𝐓`$, controling the relative abundance, $`m_aT_{ab}m_b`$, of edges between different color pairs $`a,b`$. It must satisfy

$$\underset{b=1}{\overset{K}{}}T_{ab}m_b=1.$$
(1)

Note that the total degree of a vertex is simply the sum of its colored degree components; the usual degree distribution is thus also fixed, and amounts to $`p_m=_𝐦\delta (m,_am_a)p_𝐦`$.

Truncation to Finite $`N`$.
We want to implement such an asymptotic model with a specific $`N`$. This can be done e.g. by transforming the CDD into a definite colored degree sequence, as described by the number of vertices $`N_𝐦Np_𝐦`$ with colored degree $`𝐦`$, subject to obvious constraints such as $`m<N`$, $`_𝐦N_𝐦=N`$, and $`mN_𝐦`$ is even. Similarly, the matrix $`𝐓`$ is used to determine the number of edges with color-pair $`ab`$ as $`n_{ab}Nm_aT_{ab}m_b`$. Note that each $`ab`$-edge is counted twice, as $`ab`$ and as $`ba`$, so the diagonal elements, $`n_{aa}`$, must be even. The number of edge endpoints (butts) with color $`a`$ becomes $`n_a=_bn_{ab}Nm_a_bT_{ab}m_b`$, and care must be taken that this matches the corresponding number of stubs, $`_𝐦m_aN_𝐦Nm_a`$ – thus the constraint (1) on $`𝐓`$.

This yields a pool of vertices with definite colored degrees and a pool of edges with definite color pairs, all to be considered distinguishable. The set of distinct ways to combine these into a simple graph with color-matching between butts and stubs defines a set of colored graphs. By drawing a random member from this set and neglecting the coloring, the desired truncated CDRG ensemble results.

Implementation in Practice.
When it comes to the practical task of generating random graphs from this ensemble, the tricky step is that of picking a random member from the set of colored graphs consistent with definite $`N_𝐦`$ and $`n_{ab}`$. A random stub-pairing method for DRG Bender and Canfield (1978) can be extended to the case of colored stubs as follows.

1. For each color $`a`$, make a complete random assignment between the $`n_a`$ butts of color $`a`$ and the $`n_a`$ matching stubs, to determine which butt should attach to which stub.
2. While the resulting graph is not simple, repeat step 1

Alternatively, the implementation could be done in a fully stochastic manner, where an extra initial step is to draw $`N`$ colored degrees independently from $`p_𝐦`$, and a pool of edges from $`q_{ab}=m_aT_{ab}m_b/_cm_c`$, subject to matching counts of stubs and butts of each color. In the thermodynamic limit, the result would be equivalent. Such a method would be more in line with the identification of CDRG with the Feynman graphs of zero-dimensional multi-component field theories, in analogy to the the relation between DRG models and zero-dimensional scalar field theories Burda et al. (2001)

Of course, either generation method is feasible only if the probability of obtaining a simple graph in each pairing attempt is not too small. This probability is asymptotically calculable.

Pairing Efficiency.
A completely random pairing without the restriction that the resulting graph be simple yields an ensemble of multigraphs, i.e. possibly non-simple graphs where loops (cycles of length 1) and/or multiple edges are allowed. The efficiency of the above method depends on the probability to obtain a simple graph, which in turn depends on the abundance of loops and multiple edges. In a sparse graph, the probability for an edge between a given pair of nodes scales as $`1/N`$, so we expect a finite number both of double edges (a factor of $`N^2`$ for the choice of a node-pair, and $`1/N^2`$ for two edges), and of loops ($`N`$ for the choice of node, and $`1/N`$ for the edge making a loop).

In fact, we can compute the asymptotically expected number of loops and double edges in a random pairing to leading order:
Loops: For a single vertex with colored degree $`𝐦`$, the probability that two of its stubs will be connected is given by $`_{ab}(m_am_bm_a\delta _{ab})T_{ab}/2N`$. Averaging over $`𝐦`$ and summing over the node choice yields the expected number of loops as $`\alpha =_{ab}M_{ab}T_{ab}/2`$, i.e.

$$\alpha =\frac{1}{2}\text{Tr}(\mathrm{𝐓𝐌}),$$
(2)
where $`𝐌=\{M_{ab}\}`$ stands for the matrix of moments $`m_am_bm_a\delta _{ab}`$.
Double edges Similarly, for an arbitrary pair of nodes with colored degrees $`𝐦,𝐦^{}`$, the probability of a double edge asymptotically amounts to $`_{abcd}(m_am_bm_a\delta _{ab})(m_c^{}m_d^{}m_c^{}\delta _{cd})T_{ac}T_{bd}/(2N^2)`$. Averaging over $`𝐦,𝐦^{}`$ and summing over the choice of node pair yields the expected number of double edges as $`\beta =_{abcd}M_{ab}M_{cd}T_{ac}T_{bd}/4`$, i.e.

$$\beta =\frac{1}{4}\text{Tr}(\mathrm{𝐓𝐌})^2,$$
(3)
while triple edges etc. can be neglected altogether.

In a similar way, the asymptotically expected number of more general small subgraphs can be computed, which in particular enables the computation of the expectation of higher powers of the loop and double edge counts, resulting in the two counts asymptotically behaving as independent Poissonian random variables. Hence, the probability of obtaining a simple graph in the random pairing can be estimated as

$$\text{Prob}(\text{simple})\mathrm{exp}(\alpha \beta ).$$
(4)
As a result, an average of $`\mathrm{exp}(\alpha +\beta )`$ pairing attempts is needed, rendering the method feasible for reasonably small $`\alpha +\beta `$; in other cases an alternative generation method will have to be employed, such as starting from an arbitrary colored graph consistent with $`N_𝐦,n_{ab}`$ and applying a colored extension of a degree-preserving random rewiring algorithm suggested for DRG Maslov and Sneppen (2002).

Connected Component Statistics.
The size-distribution of the connected components (clusters) of a random graph can be probed by choosing an initial vertex at random and recursively following edges to new neighbors Molloy and Reed (1995). The sparsity of edges forces a finite set of revealed vertices to form a tree in the thermodynamic limit, since cross-linking is suppressed by factors of $`1/N`$. Hence, loops and double edges can be neglected to leading order, and the random color-matched pairing between stubs and butts reduces to a random branching process (branched polymer) based on the rules: (i) an edge emanating from a stub of color $`a`$ ends in a stub of color $`b`$ with probability $`T_{ab}m_b`$; (ii) given the color $`b`$ of a stub, it belongs to a vertex with colored degree $`𝐦`$ with probability $`m_bp_𝐦/m_b`$.

The asymptotic random branching process is conveniently described in terms of a generating function $`g(z)=_nP_nz^n`$ for the probability $`P_n`$ that the connected component being revealed consists of $`n`$ vertices. $`g(z)`$ can be expressed in terms of the corresponding generating functions $`𝐡(z)=\{h_a(z)\}`$ for the number of nodes in a branch starting from a stub of color $`a`$. $`g(z)`$ and $`𝐡(z)`$ satisfy the recursive relations

$`g(z)`$ $`=`$ $`z{\displaystyle \underset{𝐦}{}}p_𝐦{\displaystyle \underset{a}{}}h_a(z)^{m_a}zH(𝐡(z))`$ (5a)
$`h_a(z)`$ $`=`$ $`z{\displaystyle \underset{b}{}}T_{ab}{\displaystyle \underset{𝐦}{}}p_𝐦m_b{\displaystyle \underset{c}{}}h_c(z)^{m_c\delta _{cb}}`$ (5b)
$``$ $`z{\displaystyle \underset{b}{}}T_{ab}_bH(𝐡(z)),`$
where $`H(𝐱)=_𝐦p_𝐦𝐱^𝐦_𝐦p_𝐦_ax_a^{m_a}`$ is the multivariate generating function for the CDD, while $`_b`$ stands for the derivative with respect to the $`b`$th argument of $`H`$. Eqs. (5) can be derived as follows. (5a): The explicit factor of $`z`$ accounts for the initial vertex, while the remainder consists in an average over the colored degree $`𝐦`$ of the initial vertex, of a factor $`h_a(z)`$ for each stub of color $`a`$, accounting for the contribution of the branch starting in that stub. (5b): Starting from a stub of color $`a`$, the asymptotic probability that the other end of the attached edge has color $`b`$ and is connected to a vertex having colored degree $`𝐦`$ is given by $`T_{ab}p_𝐦m_b`$; include a factor $`z`$ for that vertex, and a factor $`h_c(z)`$ for each branch reached via one of its remaining $`(m_c\delta _{cb})`$ stubs of color $`c`$.

Percolation Threshold.
Of particular interest is the value of $`g`$ for $`z=1`$: naively we expect $`g(1)=h_a(1)=1`$, expressing the normalization of probability. Indeed, this defines a fixed point of the recurrences (5), which however may be unstable. The stability can be analyzed by linearization of eq. (5b) around $`𝐡(1)=\mathrm{𝟏}`$, yielding the Jacobian matrix $`𝐉`$ defined by

$$J_{ab}=\underset{c}{}T_{ac}_c_bH(𝐡)|_{𝐡=\mathrm{𝟏}},$$
(6)
which can be written as $`𝐉=\mathrm{𝐓𝐌}`$ (c.f. eqs. (2,3)).

The point is that if an eigenvalue of $`𝐉`$ exceeds 1, the naive fixed point $`𝐡(1)=\mathrm{𝟏}`$ turns unstable, signalling supercriticality of the branching process. In such a case another fixed point will appear, and take over as a stable solution with $`h_a(1)<1`$ yielding $`g(1)<1`$. Analogous phenomenona occur in the classic model as well as in IRG and DRG; the associated probability deficit $`1g(1)`$ is interpreted as the probability of hitting a giant component asymptotically containing a finite fraction $`1g(1)`$ of the vertices. This corresponds to a percolating phase; the percolation threshold is defined by the largest eigenvalue of $`\mathrm{𝐓𝐌}`$ being precisely 1.

Inclusion of other models.
With a single color, $`K=1`$, CDRG trivially reduces to DRG, where a model is based on a given degree distribution $`\{p_m\}`$, while the preference matrix $`𝐓`$ reduces to a number, which by virtue of the constraint (1) must equal $`m^1`$. Equations (5) reduce to the corresponding DRG equations,

$`g(z)`$ $`=`$ $`zH(h(z)),`$ (7a)
$`h(z)`$ $`=`$ $`z{\displaystyle \frac{H^{}(h(z))}{H^{}(1)}},`$ (7b)
with $`H(x)_mp_mx^m`$ generating $`p_m`$. The percolating phase is defined by $`Jm(m1)/m>1`$, yielding the well-known $`m(m2)>0`$ Molloy and Reed (1995).

The relation to IRG is less trivial: Assume the CDD to be in the form of a multi-Poissonian mix, i.e. $`H(𝐱)=_ir_i\mathrm{exp}\left(_aC_{ia}(x_a1)\right)`$. Define

$`g_i(z)`$ $``$ $`z\mathrm{exp}\left({\displaystyle \underset{a}{}}C_{ia}(h_a(z)1)\right),`$ (8a)
$`c_{ij}`$ $``$ $`{\displaystyle \underset{ab}{}}C_{ia}T_{ab}C_{jb},`$ (8b)
in terms of which equations (5) reduce to

$`g(z)`$ $`=`$ $`{\displaystyle \underset{i}{}}r_ig_i(z),`$ (9a)
$`g_i(z)`$ $`=`$ $`z\mathrm{exp}\left({\displaystyle \underset{j}{}}r_jc_{ij}\left(g_j(z)1\right)\right).`$ (9b)
Eqs. (9) exactly reproduce the result for $`g(z)`$ in an IRG model with $`r_i`$ taken as the probability of vertex color $`i`$ and $`c_{ij}/N`$ the probability of an edge between a pair of vertices with colors $`i,j`$ Söderberg (2002).

Conversely, given an IRG model in terms of $`\{r_i,c_{ij}\}`$, one can always find $`\{C_{ia},T_{ab}\}`$ satisfying eq. (8b) such that $`_aC_{ia}=_jc_{ij}r_j`$.

It follows that CDRG contains also ensembles resulting from dynamical models such as Randomly grown graphs Callaway et al. (2001) and Dynamical random graphs with memory Turova (2002), that can be described in IRG Söderberg (2002), albeit at the cost of infinitely many colors.

Concluding Remarks.
The above analysis shows that DRG and IRG can be unified into a more general class of random graph models, defined in terms of a hidden coloring of stubs and butts, with specified distributions of color-extended vertex degrees as well of edge colorpairs. The purpose of the hidden coloring is to enable a nontrivial correlation structure in the resulting graphs.

This approach yields a general formalism for a large class of analytically tractable models on a given degree distribution, where local and global properties of the resulting graphs are calculable in the thermodynamic limit. Such a formalism also defines a suitable target for statistical model inference based on observed structural properties.

We have here assumed all moments of the degree distribution to exist, excluding e.g. power behavior. The approach will be extended also to models with “fat tails”. These are sensitive to the precise truncation method and will be treated elsewhere.

A more detailed investigation, addressing aspects and properties of CDRG models not treated in this letter, is in progress and will the subject of a forthcoming article, as will the extension to directed graphs and to degree distributions with power tails.

###### Acknowledgements.

This work was in part supported by the Swedish Foundation for Strategic Research.


text:
# Optically-induced lensing effect on a Bose-Einstein condensate expanding in a moving lattice

## Abstract

We report the experimental observation of a lensing effect on a Bose-Einstein condensate expanding in a moving 1D optical lattice. The effect of the periodic potential can be described by an effective mass dependent on the condensate quasi-momentum. By changing the velocity of the atoms in the frame of the optical lattice we induce a focusing of the condensate along the lattice direction. The experimental results are compared with the numerical predictions of an effective 1D theoretical model. Besides, a precise band spectroscopy of the system is carried out by looking at the real-space propagation of the atomic wavepacket in the optical lattice.

The experimental realization of Bose-Einstein condensation allowed significant advances in the field of atom optics. Forces resulting from the interaction with coherent light can be used to manipulate coherent matter waves atomoptics . Bragg scattering from two pulsed laser beams bragg  has provided a simple tool for the implementation of atomic mirrors, beam splitters and diffraction gratings. Superradiant Rayleigh scattering has been used as the gain mechanism for the development of a coherent matter waves amplifier superradiance . Atom lasers have been realized, providing pulsed and quasi-cw sources of coherent matter waves atomlaser . Nonlinearities in the atomic wave equation have been exploited in experiments of nonlinear atom optics, such as the realization of four wave mixing fwm  or the observation of soliton propagation solitons . One main difference between atoms and photons is the mass, which can be modified by the presence of a periodic potential, such as that resulting from the interference of two counterpropagating laser beams. The superfluid behavior of a condensate in such an optical lattice has been studied in collective  showing the role of the effective mass in shifting the collective mode frequencies. The possibility of achieving experimental control over the effective mass allows the dispersion management of the matter wavepacket. Several fascinating effects are predicted to appear in the negative effective mass regime, such as the formation of gap solitons in a condensate with repulsive interactions gapsolitons .

In this Letter we demonstrate the possibility to change the expansion of a Bose-Einstein condensate (BEC) using a moving optical lattice, which acts as a lens for matter waves, focusing or defocusing the atomic cloud along the direction of the lattice, as recently predicted in massignan02 . The observed center-of-mass dynamics can be well explained in terms of band structure and Bloch states, familiar concepts to solid state physics. This picture has been confirmed by many experimental results, including the observation of Bloch oscillations morsch01  and an extensive work on loading and manipulating a condensate in an optical lattice phillips02 . In the rest frame of the lattice the eigenenergies of the system are $`E_n(q)`$, where $`q`$ is the quasimomentum and $`n`$ the band index. According to band theory, the velocity in the $`n`$-th band is $`v_n=\mathrm{}^1E_n/q`$ and the effective mass is $`m^{}=\mathrm{}^2(^2E_n/q^2)^1`$. We demonstrate that the expansion of the condensate is strongly modified by the change in the single particle effective mass $`m^{}`$, which enters the diffusive (kinetic) term in the Gross-Pitaevskii equation. The expansion of a BEC in a static optical lattice has been already studied in morsch02 . Here we use a moving optical lattice to load the condensate in quasimomentum states with different effective mass. This ability to access regions of negative effective mass allows us to change the sign of the matter wave dispersion, inducing the condensate to compress along the lattice direction instead of expanding massignan02 .

The experiment is performed on a Bose-Einstein condensate of 87Rb produced in a standard double magneto-optical trap apparatus by means of combined laser and RF-evaporative cooling. The evaporation is performed in a Ioffe-Pritchard magnetic trap with frequencies $`\nu _x=8.8`$ Hz and $`\nu _{}=90`$ Hz along the axial and radial directions respectively. We typically produce condensates of $`10^5`$ atoms in the hyperfine level $`|F=1,m_F=1`$ of the ground state. The optical lattice is provided by two counterpropagating phase-locked laser beams aligned along the axial direction of the cigar-shaped condensate. The two beams are circularly polarized and blue-detuned 0.5 nm from the Rb D2 line at $`\lambda =780`$ nm. The interference of the two beams, derived by the same Ti:Sa laser and controlled by two independent acousto-optic modulators, produces an optical lattice moving at velocity $`v_L=\lambda \mathrm{\Delta }\nu /2`$, where $`\mathrm{\Delta }\nu `$ is the frequency difference of the two beams. In the laboratory frame the resulting potential can be written as $`V=sE_R\mathrm{cos}^2[k(xv_Lt)]`$, where $`k=2\pi /\lambda `$ is the modulus of the wavevector and $`s`$ measures the depth of the optical lattice in units of the recoil energy $`E_R=\mathrm{}^2k^2/2m`$.

The experiment is performed as follows (see Fig. 1). After producing the BEC, we switch off the magnetic trap and let the atomic cloud expand. After 1 ms of expansion we adiabatically switch on the moving lattice by ramping the intensity of the two laser beams in 2 ms. We let the condensate expand in the lattice and after a total expansion time of 13 ms we take an absorption image of the cloud along the radial horizontal direction looking at the position and dimensions of the condensate. We note that the waist of the laser beams (about 2.0 mm) is big enough to provide a constant light intensity during the entire expansion of the condensate. This loading procedure allows us to project the condensate in a Bloch state of well-defined energy and quasimomentum phillips02 . We verified the adiabaticity of this procedure by checking that, applying the reverse ramp to switch off the lattice, at the end of the expansion we still have only one momentum component in the atomic cloud (i.e. we have populated only one energy band). In our experiments we typically move the optical lattice with velocities $`v_L`$ between 0 and $`2v_B`$, where $`v_B=q_B/m=\mathrm{}k/m=5.89`$ mm/s is the recoil velocity of an atom absorbing one lattice photon. As a result of the adiabatic loading we can access different energy bands: for $`0<v_L<v_B`$ we populate the first band, while for $`v_B<v_L<2v_B`$ the second band is populated.

From the measured positions of the condensate center-of-mass at the end of the expansion we extract the velocity of the atoms inside the periodic potential. In the moving frame of the lattice the atomic velocity is given by $`v=v_L\mathrm{\Delta }x/\mathrm{\Delta }t`$, where $`\mathrm{\Delta }x`$ is the axial displacement of the condensate and $`\mathrm{\Delta }t`$ is the time of expansion inside the optical lattice (Fig. 1). In Fig. 2a we report the experimental velocities as a function of quasimomentum for two different lattice depths: $`s=1.3(1)`$ and $`s=3.8(1)`$. The error bars include the indetermination in $`\mathrm{\Delta }t`$ due to the adiabatic switching on of the optical lattice. The lines shown in the figure are obtained from the calculation of the velocity in the first two energy bands. The measured spectrum of velocities shows a very good agreement with theory. We note that the theoretical curves are derived from the simple one-particle model neglecting the effect of interactions. As a matter of fact, since the experiment is performed after some expansion, we expect that interactions play a negligible role on the energy spectrum (after 2 ms of expansion the interaction energy has been almost completely converted into kinetic energy). An adequate sampling of the experimental velocities allows us to reconstruct the effective mass by evaluating the derivative $`v/q`$ from the finite increment between consecutive points. In Fig. 2b we report the results of such analysis on the data taken at $`s=1.3`$ together with the theoretical curve. This experimental study allows us to make a precise spectroscopy of the energy bands, measuring the velocity spectrum and the effective mass of the condensate in the periodic potential.

However, the most interesting feature of this experiment concerns the observed dependence of the dimensions of the expanded condensate on different lattice velocities (hence different quasimomenta of the condensate in the frame of the moving lattice). Typical absorption images for different $`q`$ are reported in the upper part of Fig. 3. In the bottom of Fig. 3 we report the measured Thomas-Fermi radii of the condensate as obtained from a 2D fit of the measured density distribution nota . We note that, approaching the boundary of the first Brillouin zone for $`qq_B`$, the axial dimension of the condensate gets smaller as a consequence of the modified effective mass $`m^{}<0`$ (see Fig. 3b). In fact, it is easy to show that a change of sign in the effective mass corresponds to a time-reversed evolution under the influence of an inverted external potential (if present). Since in our case the condensate is initially expanding outwards, when $`m^{}`$ becomes negative an inversion of dynamics takes place nota3 . This contraction continues for times much longer than those considered in this experiment, until the wavepacket eventually reaches its minimum allowed size (when dynamics inverts again).

This focusing effect along the axial direction is balanced by an increased expansion along the radial axis, that we attribute to an effect of interactions. In fact, due to the compression along the lattice direction, the fast radial expansion is further enhanced by the increase of the mean-field energy. When the condensate is loaded in the second band, for $`qq_B`$, the axial expansion is enhanced due to the strong positive curvature of the second energy band near the zone boundary, where $`0<m^{}<m`$ (see Fig. 3c). As one would expect, in this case the radial dynamics is not modified, since the residual mean-field energy is further reduced by the fast axial expansion, causing a suppression of the non-linear coupling between the axial and radial dynamics. In Fig. 4 we also show the (radial to axial) aspect ratio of the condensate nota2 , which is characterized by a marked discontinuity across the boundary between the first and second zone as predicted in massignan02 .

To get further insight on the behavior of the condensate during the expansion, we have analyzed the experimental results by means of the 1D effective model presented in massignan02 . According to this model, the full 3D Gross-Pitaevskii description of the system is first dynamically rescaled by using the unitary scaling and gauge transformations of castin ; kagan , and then reduced to an effective 1D equation (dr-GPE) by a gaussian factorization of the radial wavefunction salasnich . Despite its 1D nature, the model is capable to account both for the axial and radial dynamics of the system, as discussed in massignan02 . In the present case the factorization of the wavefunction is further justified by the fact that during the expansion the axial and radial degrees of freedom almost decouple.

Actually, Fig. 3 shows that the model qualitatively reproduces the behavior observed in the experiment, even though it does not fit precisely the data. In particular, approaching the first zone boundary, the observed focusing effect along the axial direction is slightly smaller than the calculated one, and at the same time the expansion along the radial direction (not directly affected by the lattice) is enhanced. Instead, in the second band the radial behavior is well reproduced by the model, whereas there is still a discrepancy concerning the axial expansion. We remark that in the region near to the band edge ($`0.95q_B<q<1.05q_B`$) the process of switching on the optical lattice is no longer adiabatic, and the description is complicated by the fact that more than one energy band gets populated. Indeed what we actually see in the experiment is a superposition of two atomic clouds with different shapes resulting from the minor population of a different energy band. At the present stage of the experiment, we cannot increase arbitrarily the ramp time of the lattice intensity as the condensate, under the effect of gravity, falls out of the lattice beams.

In conclusion, we have achieved a lensing effect on a Bose-Einstein condensate expanding inside a moving optical lattice. Tuning the velocity of the lattice we can set the lensing power of the periodic potential, all the way from focusing to defocusing of the atomic cloud. The demonstrated experimental control of the matter wave dispersion is likely to open new possibilities in the field of atom optics, including the observation of non linear effects such as the generation of gap solitons. The experimental techniques introduced in this work will also allow future high precision studies of the band structure of a Bose-Einstein condensate in an optical lattice.

We acknowledge P. Massignan for stimulating discussions and theoretical support in the initial stage of this experiment. This work has been supported by the EU under Contracts Numbers HPRI-CT 1999-00111 and HPRN-CT-2000-00125, by the MURST through the PRIN2000 Initiatives and by the INFM Progetto di Ricerca Avanzata “Photon Matter”. M.Z. acknowledges partial support of the grant PBZ/KBN/043/PO3/2001.

Note added. Only after completion of this work we became aware of the publication of a paper oberthaler  showing results similar to those presented in this Letter.


text:
# Recent Results on No-Free-Lunch Theorems for Optimization

## 1 Introduction

Search heuristics such as evolutionary algorithms, grid search, simulated annealing, and tabu search are general in the sense that they can be applied to any target function $`f:𝒳𝒴`$, where $`𝒳`$ denotes a finite search space and $`𝒴`$ is a finite set of totally ordered cost-values. Much research is spent on developing search heuristics that are superior to others when the target functions belong to a certain class of problems. But under which conditions can one search method be better than another? The No-Free-Lunch-theorem for optimization (NFL-theorem) roughly speaking states that all non-repeating search algorithms have the same mean performance when averaged uniformly over *all* possible objective functions $`f:𝒳𝒴`$ . Of course, in practice an algorithm need not perform well on all possible functions, but only on a subset that arises from the real-world problems at hand, e.g., optimization of neural networks. Recently, a sharpened version of the NFL-theorem has been proven that states that NFL-results hold (i.e., the mean performance of all search algorithms is equal) for any subset $`F`$ of the set of all possible functions if and only if $`F`$ is closed under permutation (c.u.p.) and each target function in $`F`$ is equally likely .

In this paper, we address the following basic questions: When all algorithms have the same mean performance—how long does it take on average to find a desirable solution? How likely is it that a randomly chosen subset of functions is c.u.p., i.e., fulfills the prerequisites of the sharpened NFL-theorem? Do constraints relevant in practice lead to classes of target functions that are c.u.p.? And finally: How can the NFL-theorem be extended to non-uniform distributions of target functions? Answers to all these questions are given in the sections 3 to 5. First, the scenario considered in NFL-theorems is described formally.

## 2 Preliminaries

A finite search space $`𝒳`$ and a finite set of cost-values $`𝒴`$ are presumed. Let $``$ be the set of all objective functions $`f:𝒳𝒴`$ to be optimized (also called target, fitness, energy, or cost functions). NFL-theorems are concerned with non-repeating black-box search algorithms (referred to as algorithms) that choose a new exploration point in the search space depending on the history of prior explorations: The sequence $`T_m=(x_1,f(x_1)),(x_2,f(x_2)),\mathrm{},(x_m,f(x_m))`$ represents $`m`$ pairs of different search points $`x_i𝒳`$, $`i,j:x_ix_j`$ and their cost-values $`f(x_i)𝒴`$. An algorithm $`a`$ appends a pair $`(x_{m+1},f(x_{m+1}))`$ to this sequence by mapping $`T_m`$ to a new point $`x_{m+1}`$, $`i:x_{m+1}x_i`$. In many search heuristics, such as evolutionary algorithms or simulated annealing in their canonical form, it is not ensured that a point in the search space is evaluated only once. However, these algorithms can become non-repeating when they are coupled with a search-point database, see  for an example in the field of structure optimization of neural networks.

The performance of an algorithm $`a`$ after $`m`$ iterations with respect to a function $`f`$ depends only on the sequence $`Y(f,m,a)=f(x_1),f(x_2),\mathrm{},f(x_m)`$ of cost-values, the algorithm has produced. Let the function $`c`$ denote a performance measure mapping sequences of cost-values to the real numbers. For example, in the case of function minimization a performance measure that returns the minimum cost-value in the sequence could be a reasonable choice. See Fig. 1 for a schema of the scenario assumed in NFL-theorems.

Using these definitions, the original NFL-theorem for optimization reads:

###### Theorem 2.1 (NFL-theorem )

For any two algorithms $`a`$ and $`b`$, any $`k`$, any $`m\{1,\mathrm{},|𝒳|\}`$, and any performance measure $`c`$

$$\underset{f}{}\delta (k,c(Y(f,m,a)))=\underset{f}{}\delta (k,c(Y(f,m,b))).$$
(1)
Herein, $`\delta `$ denotes the Kronecker function ($`\delta (i,j)=1`$ if $`i=j`$, $`\delta (i,j)=0`$ otherwise). Proofs can be found in . This theorem implies that for any two (deterministic or stochastic, cf. ) algorithms $`a`$ and $`b`$ and any function $`f_a`$, there is a function $`f_bF`$ on which $`b`$ has the same performance as $`a`$ on $`f_a`$. Hence, statements like “Averaged over all functions, my search algorithm is the best” are misconceptions. Note that the summation in (1) corresponds to uniformly averaging over all functions in $``$, i.e., each function has the same probability to be the target function.

Recently, theorem 2.1 has been extended to subsets of functions that are closed under permutation (c.u.p.). Let $`\pi :𝒳𝒳`$ be a permutation of $`𝒳`$. The set of all permutations of $`𝒳`$ is denoted by $`\mathrm{\Pi }(𝒳)`$. A set $`F`$ is said to be c.u.p. if for any $`\pi \mathrm{\Pi }(𝒳)`$ and any function $`fF`$ the function $`f\pi `$ is also in $`F`$.

###### Example 1

Consider the mappings $`\{0,1\}^2\{0,1\}`$, denoted by $`f_0,f_1,\mathrm{},f_{15}`$ as shown in table 1. Then the set $`\{f_1,f_2,f_4,f_8\}`$ is c.u.p., also $`\{f_0,f_1,f_2,f_4,f_8\}`$. The set $`\{f_1,f_2,f_3,f_4,f_8\}`$ is not c.u.p., because some functions are “missing”, e.g., $`f_5`$, which results from $`f_3`$ by switching the elements $`(0,1)^T`$ and $`(1,0)^T`$.

In  it is proven:

###### Theorem 2.2 (sharpened NFL-theorem )

For any two algorithms $`a`$ and $`b`$, any $`k`$, any $`m\{1,\mathrm{},|𝒳|\}`$, and any performance measure $`c`$

$$\underset{fF}{}\delta (k,c(Y(f,m,a)))=\underset{fF}{}\delta (k,c(Y(f,m,b)))$$
(2)
iff $`F`$ is c.u.p.

This is an important extension of theorem 2.1, because it gives necessary and sufficient conditions for NFL-results for subsets of functions. But still theorem 2.2 can only be applied if all elements in $``$ have the same probability to be the target function, because the summations average uniformly over $`F`$.

In the following, the concept of $`𝒴`$-histograms is useful. A *$`𝒴`$-histogram* (*histogram* for short) is a mapping $`h:𝒴_0`$ such that $`_{y𝒴}h(y)=|𝒳|`$. The set of all histograms is denoted $``$. Any function $`f:𝒳𝒴`$ implies the histogram $`h_f(y)=|f^1(y)|`$ that counts the number of elements in $`𝒳`$ that are mapped to the same value $`y𝒴`$ by $`f`$. Herein, $`f^1(y),y𝒴`$ returns the preimage $`\{x|f(x)=y\}`$ of $`y`$ under $`f`$. Further, two functions $`f,g`$ are called *$`h`$-equivalent* iff they have the same histogram. The corresponding $`h`$-equivalence class $`B_h`$ containing all functions with histogram $`h`$ is termed a *basis class*.

###### Example 2

Consider the functions in table 1. The $`𝒴`$-histogram of $`f_1`$ contains the value zero three times and the value one one time, i.e., we have $`h_{f_1}(0)=3`$ and $`h_{f_1}(1)=1`$. The mappings $`f_1`$, $`f_2`$, $`f_4`$, $`f_8`$ have the same $`𝒴`$-histogram and are therefore in the same basis class $`B_{h_{f_1}}=\{f_1,f_2,f_4,f_8\}`$. The set $`\{f_1,f_2,f_4,f_8,f_{15}\}`$ is c.u.p. and corresponds to $`B_{h_{f_1}}B_{h_{f_{15}}}`$.

It holds:

###### Lemma 1 ()

1. Any subset $`F`$ that is c.u.p. is uniquely defined by a union of pairwise disjoint basis classes.
2. $`B_h`$ is equal to the permutation orbit of any function $`f`$ with histogram $`h`$, i.e.,

$$B_h=\underset{\pi \mathrm{\Pi }(𝒳)}{}\{f\pi \}.$$
(3)

A proof is given in .

## 3 Time to Find a Desirable Solution

Theorem 2.2 tells us that on average all algorithms need the same time to find a desirable, say optimal, solution—but how long does it take? The average number of evaluations, i.e., the mean first hitting time $`\text{E}\{𝒯\}`$, needed to find an optimum depends on the cardinality of the search space $`|𝒳|`$ and the number $`n`$ of search points that are mapped to a desirable solution.

Let $`F_n`$ be the set of all functions where $`n`$ elements in $`𝒳`$ are mapped to optimal solutions. For *non-repeating* black-box search algorithms it holds:

###### Theorem 3.1 ()

Given a search space of cardinality $`|𝒳|`$ the expected number of evaluations $`\text{E}\{𝒯_{|𝒳|,n}\}`$ averaged over $`F_n`$ is given by

$$\text{E}\{𝒯_{|𝒳|,n}\}=\frac{|𝒳|+1}{n+1}.$$
(4)
A proof can be found in , where this result is used to study the influence of neutrality (i.e., of non-injective genotype-phenotype mappings) on the time to find a desirable solution.

## 4 Fraction of Subsets Closed under Permutation

The NFL-theorems can be regarded as the basic skeleton of combinatorial optimization and are important for deriving theoretical results as the one presented in the previous section. However, are the preconditions of the NFL-theorems ever fulfilled in practice? How likely is it that a randomly chosen subset is c.u.p.?

There exist $`2^{\left(|𝒴|^{|𝒳|}\right)}1`$ non-empty subsets of $``$ and it holds:

###### Theorem 4.1 ()

The number of non-empty subsets of $`𝒴^𝒳`$ that are c.u.p. is given by

$$2^{\left(\genfrac{}{}{0pt}{}{|𝒳|+|𝒴|1}{|𝒳|}\right)}1$$
(5)
and therefore the fraction of non-empty subsets c.u.p. is given by

$$\left(2^{\left(\genfrac{}{}{0pt}{}{|𝒳|+|𝒴|1}{|𝒳|}\right)}1\right)/\left(2^{\left(|𝒴|^{|𝒳|}\right)}1\right).$$
(6)
The proof is given in .

Figure 2 shows a plot of the fraction of non-empty subsets c.u.p. versus the cardinality of $`𝒳`$ for different values of $`|𝒴|`$. The fraction decreases for increasing $`|𝒳|`$ as well as for increasing $`|𝒴|`$. More precisely, for $`|𝒴|>e|𝒳|/(|𝒳|e)`$ it converges to zero double exponentially fast with increasing $`|𝒳|`$. Already for small $`|𝒳|`$ and $`|𝒴|`$ the fraction almost vanishes.

Thus, the statement “I’m only interested in a subset $`F`$ of all possible functions, so the precondition of the sharpened NFL-theorems is not fulfilled” is true with a probability close to one (if $`F`$ is chosen uniformly and $`𝒴`$ and $`𝒳`$ have reasonable cardinalities). The fact that the precondition of the NFL-theorem is violated does not lead to “Free Lunch”, but nevertheless ensures the possibility of a “Free Appetizer”.

## 5 Search Spaces with Neighborhood Relations

Although the fraction of subsets c.u.p. is close to zero already for small search and cost-value spaces, the absolute number of subsets c.u.p. grows rapidly with increasing $`|𝒳|`$ and $`|𝒴|`$. What if these classes of functions are the relevant ones, i.e., those we are dealing with in practice?

Two assumptions can be made for most of the functions relevant in real-world optimization: First, the search space has some structure. Second, the set of objective functions fulfills some constraints defined based on this structure. More formally, there exists a non-trivial neighborhood relation on $`𝒳`$ based on which constraints on the set of functions under consideration are formulated, e.g., concepts like ruggedness or local optimality and constraints like upper bounds on the ruggedness or on the maximum number of local minima can be defined.

A neighborhood relation on $`𝒳`$ is a symmetric function $`n:𝒳\times 𝒳\{0,1\}`$. Two elements $`x_i,x_j𝒳`$ are called neighbors iff $`n(x_i,x_j)=1`$. A neighborhood relation is called non-trivial iff $`x_i,x_j𝒳:x_ix_jn(x_i,x_j)=1`$ and $`x_k,x_l𝒳:x_kx_ln(x_k,x_l)=0`$. It holds:

###### Theorem 5.1 ()

A non-trivial neighborhood relation on $`𝒳`$ is not invariant under permutations of $`𝒳`$.

This result is quite general. Assume that the search space $`𝒳`$ can be decomposed as $`𝒳=𝒳_1\times \mathrm{}\times 𝒳_l,l>1`$, and let on one component $`𝒳_i`$ exist a non-trivial neighborhood $`n_i:𝒳_i\times 𝒳_i\{0,1\}`$. This neighborhood induces a non-trivial neighborhood on $`𝒳`$, where two points are neighbored iff their $`i`$-th components are neighbored with respect to $`n_i`$. Thus, the constraints discussed below need only refer to a single component. Note that the neighborhood relation need not be the canonical one (e.g., Hamming-distance for Boolean search spaces). For example, if integers are encoded by bit-strings, then the bit-strings can be defined as neighbored iff the corresponding integers are.

Some constraints that are defined with respect to a neighborhood relation and that are relevant in practice are now discussed, cf. . For this purpose, a metric $`d_𝒴:𝒴\times 𝒴`$ on $`𝒴`$ is presumed, e.g., in the typical case of real-valued target functions $`𝒴`$ the Euclidean distance.

A constraint on steepness leads to a set of functions that is not c.u.p. Based on a neighborhood relation on the search space, we can define a simple measure of maximum steepness of a function $`f`$ by the maximum distance of the target values of neighbored points $`s^{\mathrm{max}}(f)=\mathrm{max}_{x_i,x_j𝒳n(x_i,x_j)=1}d_𝒴(f(x_i),f(x_j))`$. Further, for a function $`fF`$, the diameter of its range can be defined as $`d^{\mathrm{max}}(f)=\mathrm{max}_{x_i,x_j𝒳}d_𝒴(f(x_i),f(x_j))`$.

###### Corollary 1 ()

If the maximum steepness $`s^{\mathrm{max}}(f)`$ of every function $`f`$ in a non-empty subset $`F`$ is constrained to be smaller than the maximal possible $`\mathrm{max}_{fF}d^{\mathrm{max}}(f)`$, then $`F`$ is not c.u.p.

Consider the number of local minima, which is often regarded as a measure of complexity . For a function $`f`$ a point $`x𝒳`$ is a local minimum iff $`f(x)<f(x_i)`$ for all neighbors $`x_i`$ of $`x`$. Given a function $`f`$ and a neighborhood relation on $`𝒳`$, let $`l^{\mathrm{max}}(f)`$ be the maximal number of minima that functions with the same $`𝒴`$-histogram as $`f`$ can have (i.e., functions where the number of $`𝒳`$-values that are mapped to a certain $`𝒴`$-value are the same as for $`f`$).

###### Corollary 2 ()

If the number of local minima of every function $`f`$ in a non-empty subset $`F`$ is constrained to be smaller than the maximal possible $`\mathrm{max}_{fF}l^{\mathrm{max}}(f)`$, then $`F`$ is not c.u.p.

###### Example 3

Consider all mappings $`\{0,1\}^{\mathrm{}}\{0,1\}`$ that have less than the maximum number of $`2^{n1}`$ local minima w.r.t. the ordinary hypercube topology on $`\{0,1\}^{\mathrm{}}`$. This means, this set does not contain mappings such as the parity function, which is one iff the number of ones in the input bitstring is even. This set is not c.u.p.

Hence, statements like “In my application domain, functions with maximum number of local minima are not realistic” and “For some components, the objective functions under consideration will not have the maximal possible steepness” lead to scenarios where the precondition of the NFL-theorem is not fulfilled.

## 6 A Non-Uniform NFL-theorem

In the sharpened NFL-theorem it is implicitly presumed that all functions in the subset $`F`$ are equally likely since averaging is done by uniform summation over $`F`$. Here, we investigate the general case when every function $`f`$ has an arbitrary probability $`p(f)`$ to be the objective function. Such a non-uniform distribution of the functions in $`F`$ appears to be much more realistic. Until now, there exist only very weak results for this general scenario. For example, let for all $`x𝒳`$ and $`y𝒴`$

$$p_x(y):=\underset{f}{}p(f)\delta (f(x),y),$$
(7)
i.e., $`p_x(y)`$ denotes the probability that the search point $`x`$ is mapped to the cost-value $`y`$. In  it has been shown that a NFL-result holds if within a class of functions the function values are i.i.d., i.e., if

$$x_1,x_2𝒳:p_{x_1}=p_{x_2}\text{ and }p_{x_1,x_2}=p_{x_1}p_{x_2},$$
(8)
where $`p_{x_1,x_2}`$ is the joint probability distribution of the function values of the search points $`x_1`$ and $`x_2`$. However, this is not a necessary condition and applies only to extremely “unstructured” problem classes.

The following theorem gives a necessary and sufficient condition for a NFL-result in the general case of non-uniform distributions:

###### Theorem 6.1 (non-uniform sharpened NFL)

For any two algorithms $`a`$ and $`b`$, any value $`k`$, and any performance measure $`c`$

$$\underset{f}{}p(f)\delta (k,c(Y(f,m,a)))=\underset{f}{}p(f)\delta (k,c(Y(f,m,b)))$$
(9)
iff for all $`h`$

$$f,gB_hp(f)=p(g).$$
(10)
###### Proof

First, we show that (10) implies that (9) holds for any $`a`$, $`b`$, $`k`$, and $`c`$. It holds by lemma 1(a)

$`{\displaystyle \underset{f}{}}p(f)\delta (k,c(Y(f,m,a)))`$ $`={\displaystyle \underset{h}{}}{\displaystyle \underset{fB_h}{}}p(f)\delta (k,c(Y(f,m,a)))`$ (11)
using $`f,gB_hp(f)=p(g)=p_h`$
$`={\displaystyle \underset{h}{}}p_h{\displaystyle \underset{fB_h}{}}\delta (k,c(Y(f,m,a)))`$ (12)
as each $`B_h`$ is c.u.p. we may use theorem 2.2
$`={\displaystyle \underset{h}{}}p_h{\displaystyle \underset{fB_h}{}}\delta (k,c(Y(f,m,b)))`$ (13)
$`={\displaystyle \underset{f}{}}p(f)\delta (k,c(Y(f,m,b))).`$ (14)
Now we prove that (9) being true for any $`a`$, $`b`$, $`c`$, and $`k`$ implies (10) by showing that if (10) is not fulfilled then there exist $`a`$, $`b`$, $`c`$, and $`k`$ such that (9) is also not valid. Let $`f,gB_h`$, $`fg`$, $`p(f)p(g)`$, and $`g=f\pi `$. Let $`𝒳=\{\xi _1,\mathrm{},\xi _n\}`$. Let $`a`$ be an algorithm that always enumerates the search space in the order $`\xi _1,\mathrm{},\xi _n`$ regardless of the observed cost-values and let $`b`$ be an algorithm that enumerates the search space always in the order $`\pi ^1(\xi _1),\mathrm{},\pi ^1(\xi _n)`$. It holds $`g(\pi ^1(\xi _i))=f(\xi _i)`$ for $`i=1,\mathrm{},n`$ and $`Y(f,n,a)=Y(g,n,b)`$. We consider the performance measure

$$c^{}(y_1,\mathrm{},y_m)=\{\begin{array}{cc}1\hfill & \text{if }m=ny_1,\mathrm{},y_m=f(\xi _1),\mathrm{},f(\xi _n)\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$$
(15)
for any $`y_1,\mathrm{},y_m𝒴`$. Then, for $`m=n`$ and $`k=1`$, we have

$$\underset{f^{}}{}p(f^{})\delta (k,c^{}(Y(f^{},n,a)))=p(f),$$
(16)
as $`f^{}=f`$ is the only function $`f^{}`$ that yields

$$f^{}(\xi _1),\mathrm{},f^{}(\xi _n)=f(\xi _1),\mathrm{},f(\xi _n),$$
(17)
and

$$\underset{f^{}}{}p(f^{})\delta (k,c^{}(Y(f^{},n,b)))=p(g),$$
(18)
and therefore (9) does not hold. ∎

The sufficient condition given in  is a special case of theorem 6.1, because (8) implies

$$g=f\pi p(f)=p(g)$$
(19)
for any $`f,g`$ and $`\pi \mathrm{\Pi }(𝒳)`$, which in turn implies $`g,fB_hp(f)=p(g)`$ due to lemma 1(b).

The probability that a randomly chosen distribution over the set of objective functions fulfills the preconditions of theorem 6.1 has measure zero. This means that in this general and realistic scenario the probability that the conditions for a NFL-result hold vanishes.

## 7 Conclusion

Several recent results on NFL-theorems for optimization presented in  were summarized and extended. In particular, we derived necessary and sufficient conditions for NFL-results for arbitrary distributions of target functions and thereby presented the “sharpest” NFL theorem so far. It turns out that in this generalized scenario, the necessary conditions for NFL-results can not be expected to be fulfilled.

### Acknowledgments

This work was supported by the DFG, grant Solesys-II SCHO 336/5-2. We thank Stefan Wiegand for fruitful discussions.


text:
# Chromofields of Strings and Baryons Work supported by BMBF

## 1 Introduction

Quantum chromodynamics (QCD) is the widely accepted theory for the dynamics of quarks and gluons. Despite its success in the regime of high momemtum transfer it remains an outstanding task to explain the low energy behavior of hadrons within QCD. Only in the last 10 years lattice QCD (lQCD) has found detailed evidence for the confinement of quarks in hadrons Bali:2000gf  but it still fails to give a dynamical description of this phenomenon. It is therefore necessary to rely on models, capable to describe confinement dynamically on the one hand and to reproduce static results of lQCD on the other hand.

In this talk we present static calculations within the Chromodielectric Model Friedberg:1977eg ; Friedberg:1977xf ; Traxler:1998bk , namely the detailed analysis of quark–antiquark strings and three–quark configurations.

## 2 Phenomenology of the Model

In the Chromodielectric Model (CDM) it is assumed, that the vacuum of QCD behaves in the long range limit as a perfect color dielectric medium with vanishing dielectric constant $`\kappa =0`$. The medium is generated through the non-abelian part of the gluonic sector of QCD which is represented in CDM as a scalar color singlet field $`\sigma `$. The remaining two abelian gluon fields are able to propagate through this medium. The scalar field $`\sigma `$ is driven by a scalar potential $`U(\sigma )`$ (see fig. 1) which exhibits two (quasi) stable points, separating the non-perturbative, perfect dielectric phase where $`\sigma =\sigma _{\text{vac}}`$, from the perturbative phase with $`\kappa =1`$, where the color fields can propagate freely and $`\sigma =0`$.

In our description quarks are treated classically and the gluons are coupled to the quark current $`j^{\mu ,a}`$. This results in the following Lagrangian

$``$ $`=`$ $`_q+_g+_\sigma `$ (1)
$`_q`$ $`=`$ $`{\displaystyle \underset{k}{}}m_k\sqrt{1\dot{\stackrel{}{x}}_k^2}w\left(\stackrel{}{x}\stackrel{}{x}_k(t)\right)`$
$`g_sj_\mu ^aA^{\mu ,a}`$
$`_g`$ $`=`$ $`\frac{1}{4}\kappa (\sigma )F_{\mu \nu }^aF^{\mu \nu ,a}`$ (3)
$`_\sigma `$ $`=`$ $`\frac{1}{2}_\mu \sigma ^\mu \sigma U(\sigma )`$ (4)
$`F^{\mu \nu ,a}`$ $`=`$ $`^\mu A^{\nu ,a}^\nu A^{\mu ,a},a\{3,8\}`$ (5)
$`j^{\mu ,a}`$ $`=`$ $`{\displaystyle \underset{k}{}}q_k^au_k^\mu w\left(\stackrel{}{x}\stackrel{}{x}_k(t)\right)=(\rho ^a,\stackrel{}{ȷ}^a)`$ (6)
with $`u_k^\mu `$ being the 4-velocity of particle $`k`$ with classical charge $`q_k^a`$ (see fig. 1) and extension $`w\left(\stackrel{}{x}\stackrel{}{x}_k(t)\right)`$. The scalar potential $`U(\sigma )`$ is chosen to be of a quartic form and is shown in fig. 1. In this work $`U(\sigma )`$ has no relative maximum between $`\sigma =\sigma _{\text{vac}}`$ and $`\sigma =0`$ and $`U`$ is determined through the bag pressure $`B=U(0)`$ and $`\sigma _{\text{vac}}`$ alone. The dielectric function is of the form $`\kappa (\sigma )=\mathrm{exp}\left(\frac{\sigma ^3}{\sigma _0^3}\right)`$ for $`\sigma 0`$ and $`\kappa (\sigma )=1`$ else and has $`\kappa (\sigma _{\text{vac}})\kappa _{\text{vac}}1`$.

In the static case, the equations of motion for the electric potentials $`\mathrm{\Phi }^a`$ and for the confinement field $`\sigma `$ following from eq. (1) are:

$$\stackrel{}{}\left(\kappa (\sigma )\stackrel{}{}\mathrm{\Phi }^a\right)=g_s\rho ^a$$
(7)
and

$$^2\sigma =U^{}(\sigma )\frac{1}{2}\frac{\kappa ^{}(\sigma )}{\kappa (\sigma )^2}\left(\stackrel{}{D^3}\stackrel{}{D^3}+\stackrel{}{D^8}\stackrel{}{D^8}\right),$$
(8)
where $`\stackrel{}{D^a}=\kappa (\sigma )\stackrel{}{}\mathrm{\Phi }^a`$ denotes the color electric displacement. The energy (neglecting quark masses) is given by:

$`E`$ $`=`$ $`E_\sigma +E_g`$ (9)
$`E_\sigma `$ $`=`$ $`{\displaystyle \left(\frac{1}{2}(\sigma )^2+U(\sigma )\right)d^3r}`$ (10)
$`E_g`$ $`=`$ $`{\displaystyle \frac{1}{2}}{\displaystyle \left(\stackrel{}{E^3}\stackrel{}{D^3}+\stackrel{}{E^8}\stackrel{}{D^8}\right)d^3r}{\displaystyle \epsilon _gd^3r}.`$ (11)
Confinement of color fields in our model is achieved by means of Gauss’s law in eq. (7) and the characteristic form of the dielectric function $`\kappa (\sigma )`$: A single colored quark would generate a spherical electric field. In the vicinity of the quark the field is strong enough to push the confinement field from $`\sigma =\sigma _{\text{vac}}`$ towards smaller values and forms a cavity in the surrounding vacuum. As $`\kappa (\sigma )`$ drops to zero at the boundary of the cavity, the electric field $`\stackrel{}{E^a}=\frac{\stackrel{}{D^a}}{\kappa (\sigma )}`$ diverges and so does the electric field energy (11). Note that in this version of CDM there is no direct coupling between the quarks and the confinement field as proposed in Friedberg:1977eg ; Schuh:1986mi .

## 3 $`\overline{q}q`$ Strings

In contrast to configurations with net color, all white configurations have finite energy and color fields are confined into well defined spatial regions. Again, eq. (7) enforces an electric color field, but field lines now end on the anti–color and are parallel to the boundary of the cavity. In this case the color electric displacement is suppressed with the dielectric constant in the non-perturbative vacuum. Both the electric field energy and the confinement field energy are negligible in the outside.

In this section we study the field configurations of color flux tubes stretching from a quark $`q`$ to an antiquark $`\overline{q}`$. We start by showing the electric field $`\stackrel{}{E^3}`$ and $`\stackrel{}{D^3}`$ in fig. 2.

It is seen that the electric displacement vanishes outside the cavity. The flux tube can be characterized by the profile function, i. e. the component of $`\stackrel{}{D}`$ parallel to the string axis along the center line perpendicular to the string axis. This profile has been studied within lQCD in Bali:1995de . 111Note that in CDM the $`\stackrel{}{D}`$ field is confined and we compare it to the $`\stackrel{}{E}`$ field of reference Bali:1995de .  The profile depends mainly on the choice of $`U(\sigma )`$, i. e. on the bag constant $`B`$ and the vacuum value $`\sigma _{\text{vac}}`$ as shown in fig. 3. The bag constant acts as a pressure against the electric field and therefore an increasing $`B`$ leads to decreasing width of the profile. In order to fulfill Gauss’s law (7) the electric $`\stackrel{}{D}`$ field on the string axis must increase with increasing $`B`$.

The value of $`\sigma _{\text{vac}}`$ controls the surface of the bag. Decreasing its value leads to a sharper surface. In our simulations the detailed form of the dielectric function (see fig. 1) has little effect on the profile.

With the parameters given in tab. 1 we reproduce the results of lQCD Bali:2000gf ; Bali:1995de  as can be seen in fig. 4.

Using the same parameters we can calculate the string tension of the flux tube. We vary the $`q`$-$`\overline{q}`$ distance $`r`$ and plot the total energy of eq. (9) as a function of $`r`$ in fig. 4. For $`r>0.5`$ fm the energy rises linearly. We fit our results to a Cornell potential

$$E_c(r)=E_0+\tau r\frac{\alpha _{\text{eff}}}{r},$$
(12)
where the linear term reflects the confinement behavior for large $`\overline{q}q`$-separations and the Coulomb term describes the one gluon exchange dominant at small $`r`$. The constant term $`E_0=560`$ MeV is due to electric self energies included in eq. (11). We find a string tension $`\tau =988`$ MeV/fm and a value $`\alpha _{\text{eff}}=0.291`$ which is to be compared to lQCD results where $`\alpha _{\text{eff}}=0.295`$ Bali:2000gf . It should be noted, that due to the high bag pressure $`B`$ the electric fields are not strong enough to expel totally the non-perturbative vacuum out of the string. The confinement field only drops to $`\sigma 0.5\sigma _{\text{vac}}`$, i. e. the dielectric function rises to $`\kappa 0.5`$. However, confinement is still achieved as the energy of the color fields does not leak into the outside.

## 4 Baryons

In this section we study color fields of baryon like $`qqq`$–configurations. Given that the energy scales linearly with the $`\overline{q}q`$-separation, one can argue that configurations with 3 quarks sitting on the corner of an equilateral triangle will form strings with minimal total string length. This would be a configuration with a central *Steiner* point, called a $`Y`$ configuration. However, if only two quark interactions are dominant, one might expect strings stretching pairwise from one quark to another, which would be the $`\mathrm{\Delta }`$ configuration. In lQCD the $`qqq`$ potential has been studied and there are indications for both the $`\mathrm{\Delta }`$ baryon Bali:2000gf ; Alexandrou:2001ip  and the $`Y`$ baryon Takahashi:2002bw . However in the Gaussian Stochastic Vacuum model Kuzmenko:2000rt  clear evidence for the $`Y`$ ansatz is found.

In fig. 5 we plot the electric field distribution for the baryon with the parameters given in tab. 1. The quarks are separated a distance $`\mathrm{}=0.7(1.3)`$ fm from the Steiner point, i.e. the $`qq`$ distance is $`L=\sqrt{3}\mathrm{}1.2(1.7)`$ fm.

The field is clearly different from a simple superposition of 3 flux tubes between the quarks (see fig. 2). The electric energy is pushed towards the center of the baryon, and a $`Y`$ shaped configuration (at least for large quark separations) is seen.

## 5 Summary

We have analyzed the $`\overline{q}q`$ string within CDM and have reproduced the geometric profile function as well as the potential. With a bag constant $`B=(320\text{MeV})^4`$ and $`\sigma _{\text{vac}}=1.5`$ fm-1 we get a string tension $`\tau =988`$ MeV/fm and an effective strong coupling $`\alpha _{\text{eff}}=0.29`$. $`qqq`$ configurations with large $`qq`$ separations tend to show a $`Y`$ shaped geometry.