format: text

text:
# Quasar Lensing: the Observer’s Point of View

## 1. Why Observing Lensed Quasars ?

Gravitational lensing is a well established field of astrophysics. It is well enough understood that it can be applied to other areas of astrophysics in order to tackle astrophysical problems under a new angle. Some applications of gravitational lensing concentrate on the study of the objects responsible for the deflection of light, the lenses. Others, aim at studying the stretched, distorted and (de)magnified images of the background objects, the sources. For example, stellar micro-lensing is used to probe the content of our own galaxy in dark low-mass stars, or micro-lenses. The weak distortions of very distant galaxies is used to detect indirectly and even to map what might be the largest lenses in the Universe: the Large Scale Structures. In many multiply imaged quasars, (micro)lenses are found within (macro)lenses: quasar micro- or milli-lensing provides us with information on the structure of both the sources and the lenses (see for example Schechter 2003; Wambsganss 2003).

Many of the applications of gravitational lensing, and in particular of quasar lensing, were known and described decades ago. They nevertheless only start now to be implemented on a systematic basis, taking advantage of the recent explosion of the number of large observatories that operate at high angular resolution and down to very faint magnitudes.

Quasar lensing helps us to study lenses and sources, but it also consists in a fantastic tool to study the space between the lenses and the sources ! While the light travels from the source to the observer, it is absorbed by the Inter Stellar Medium of the lens, and by the neutral gas of the Inter-Galactic Medium. The study of absorption lines in multiply imaged quasars provides us with information about the geometry of intergalactic clouds (Smette 2003). Last, but not least, multiply imaged quasars tell us about the size of the Universe, through the measurement of the so-called “time-delay” between the lensed images. This quantity is directly related to the mass distribution in the lensing galaxy and to the Hubble parameter H0. The measurement of H0 using lensed quasars is the topic of the present chapter.

## 2. First Discoveries and Searches

### 2.1. A Few Lucky Cases

The observational history of lensed quasars starts with a few lucky cases found “by accident” during surveys or follow-up observations of projects unrelated to gravitational lensing. The very first case was the double quasar Q 0957+561. When observed at optical wavelengths, the z=1.405 quasar appeared as two point sources separated by 5.7′′ (Walsh et al. 1979). Spectra obtained with the Multi-Mirror-Telescope showed that both objects had almost identical spectral properties (Weymann et al. 1979), strongly supporting the hypothesis of gravitational lensing: two images of one single object were seen, due to the potential well created by a galaxy along the line of sight. In fact, not only the spectra were identical, but subtraction of the quasar images also revealed, for the first time, the lensing galaxy, hidden by the much brighter quasar images. With such observational material, no serious doubts could remain about the lensed nature of Q 0957+561.

Other cases were found soon after, such as the quadruply imaged quasar PG 1115+080 (Weymann et al. 1980) that we will use in this article to illustrate how lensed quasars can help use to determine H0. Even the famous “Einstein Cross”, Q 2237+0305 (Huchra et al. 1985; see Fig. 1), was discovered during follow-up observations in the course of the CfA redshift survey: a spectrum obtained of the central parts of a z=0.04 redshift galaxy, turned out to display the exact characteristics of a quasar at much higher redshift, z=1.7. In addition, the total apparent luminosity of the bulge of the galaxy was far too high for a normal spiral. Indeed, it was in fact the combined light of the actual galaxy’s bulge and of the four (unresolved) quasar images. High resolution images taken a few years later nicely confirmed that the object was composed of four separate quasar images almost aligned with the bulge of the spiral galaxy (Schneider et al. 1988; see Fig. 2).

### 2.2. Systematic Searches and the Magnification Bias

While the very first lenses were found by chance (and there are still lenses found by chance from time to time; see for example Sluse et al. 2003), observational strategies were soon designed to find many more, on purpose !

Such an enterprise requires to estimate the number of lensed objects within a sample of quasars, given the selection criteria, in general a flux limit. The exercise has been done many times by many groups, following the ideas first proposed by Turner (1980). The original idea of Turner was to describe the effect of undetected lenses on the apparent evolution of quasars. As lensing amplifies the apparent luminosity of background objects, significant modifications of the observed luminosity function of quasars were suspected, in particular toward the bright end. Several ingredients are needed to carry out the calculation: (1) the spatial distribution of lenses, (2) the spatial distribution of sources, (3) a realistic mass model for the lenses in order to estimate the amplification, (4) a cosmological model and, (5) the (unlensed) luminosity function of the sources. Although none of these were precisely known in the eighties, it was quickly understood that lens statistics was a particularly sensitive function of the slope of the source luminosity function: the relative weights of the faint to bright quasar number counts give rise to the so-called “magnification bias” (see contribution by Smette, 2003 for more details). Its net effect on a flux limited sample is that the fraction of sources likely to be magnified by a given amount $`\mu `$ is higher for apparently bright sources than for fainter ones (see for example Schneider, Ehlers & Falco, 1992). In other words, bright sources are seen bright, because they are (more likely to be) lensed.

Based on this simple, but important finding, several surveys were started, targeting at quasars with the brightest absolute magnitude in large samples. Because at the time of the first surveys were initiated, high angular resolution was easier to achieve in the radio than in the visible, multiply imaged quasars were often the found in large radio surveys (e.g., Lawrence et al. 1986; Langston et al. 1989; Hewitt et al. 1992). The largest of these surveys so far are probably CLASS, the “Cosmic Lens All Sky Survey” and JVAS, the “Jorell Bank - VLA Astrometric Surveys” (see, among others, Patnaik et al. 1992; Myers et al. 1995; Jackson et al. 1998).

Almost in parallel with radio surveys, optical searches started and successfully yielded a significant harvest of multiply imaged quasars. Among the first ones to be discovered, were the double UM 673 (Surdej et al. 1987), the quadruple “cloverleaf” H 1413+117 (Magain et al. 1988), followed by some cases in the Hamburg/ESO survey for bright quasars (e.g., Wisotzki et al. 1993). The search for new cases is still ongoing, with a success rate that makes it difficult to keep track of every new discovery. Large multi-wavelengths wide field surveys are now relatively easy to carry out and the “multiband” magnification bias is studied in order to understand the effect of lensing on such data (Wyithe et al. 2003). The prospects to find many new lenses suitable for cosmological applications (e.g., in SLOAN, FIRST, GOODS, etc…) are therefore excellent. At the time of the writing of this article, several new good candidates from these surveys are under analyze.

## 3. Lensed Quasars and $`H_0`$

Quasar lensing helps to solves astrophysical puzzles in various ways, but one of its most beautiful applications is probably the determination of the Hubble parameter H0.

### 3.1. The Time-delay Method

In 1964, the Norwegian astronomer Sjur Refsdal proposed an original method (Refsdal 1964) to use gravitational lensing as a tool to measure the size/age of the Universe. When photons propagate from a distant source toward the observer, they are under the effect of the gravity field of lenses along the line of sight. They do not follow a straight line anymore, but their trajectory is curved and longer than the original one. As a consequence, it takes more time for the photons to travel from a lensed source than from an unlensed one. The geometrical difference introduced by the lens between the two, lensed and unlensed paths, introduces a time-lag between the arrival times of the (lensed and unlensed) photons at the position of the observer. This time lag is called the geometrical “time-delay”, $`t_{\mathrm{geom}}`$. While passing in the immediate vicinity of the gravity field of the lens, the light is affected by a second delay: the gravitational time-delay, $`t_{\mathrm{grav}}`$. A “lensed photon” will be seen by an observer with a total time-delay $`t_{\mathrm{tot}}=t_{\mathrm{geom}}+t_{\mathrm{grav}}`$, with respect to the observation of the same photon if it were not lensed.

The time-delay is a function of image position in projection on the plane of the sky. One can then define an arrival time surface that associates, to each position on the sky, a given a value of the time-delay. Most of this surface is missed by the observer who has only access to the few areas where the lensed images form. When two or more images of the source are observed it is possible to compare the arrival times at the positions of the lensed images and to determine a “relative time-delay”. This is in fact the only truly measurable quantity, rather than the actual time-delay between the lensed and unlensed paths to the source, since the unlensed source is never visible.

In practice, time-delays are measured taking advantage of a lensed source with significant photometric variations. Due to the time-delay, the variations will be detected by the observer at different times in the light curves of each image. The shift in time between the light curves is simply the (total) time-delay between the images. Refsdal (1964) proposed to measure time-delays in lensed supernovae, but his method was published just when the first quasars were discovered (Schmidt 1963). Quasars, that later turned out to be very numerous in the sky, rather bright, and photometrically variable, were promising objects to measure time-delays if at least some of them were found to be lensed. They appeared in any case much more promising than rare and transient phenomena such as supernovae. Indeed, thousands of quasars are now known, and several tens of them are lensed. Measured quasar time-delays span over a broad range of values, between days and months. One is larger than a year: Q 0957+561 (e.g., Vanderriest et al. 1989).

### 3.2. Constraints and Uncertainties

Time-delays can be predicted from lens modeling, for any observed image configuration and compared with the measured ones in order to infer the value of H0. The task requires detailed observations, deep, and at high angular resolution, and a good mass model for the lensing galaxy, as can be seen from the explicit expression for the time-delay in equations (1-3). A full description of the calculation can be found in Schneider, Ehlers & Falco (1992). We only use the result here to illustrate how observations help to achieve our goal. As explained above, the total time delay is the sum of two contributions, so that:

$$t_{\mathrm{tot}}=t_{\mathrm{geom}}+t_{\mathrm{grav}},$$
(1)
Each contribution to the total time-delay writes as:

$$t_{\mathrm{geom}}(\stackrel{}{\theta })=(1+z_\mathrm{L})\frac{D_\mathrm{L}D_\mathrm{S}}{cD_{\mathrm{LS}}}(\stackrel{}{\theta }\stackrel{}{\beta })^2,$$
(2)
$$t_{\mathrm{grav}}(\stackrel{}{\theta })=(1+z_\mathrm{L})\frac{8\pi G}{c^3}^2\mathrm{\Sigma }(\stackrel{}{\theta }).$$
(3)
where zL is the redshift of the lensing galaxy. As illustrated in Fig. 3, the angle $`\stackrel{}{\theta }`$ (in 2D in real cases) gives the position of the images on the plane of the sky and $`\beta `$ is the angular position of the source.

The Hubble parameter H0 is contained in the geometrical part of the time-delay, through the angular diameter distances to the lens DL, to the source DS and through the distance between the lens and the source, DLS.

Equation (3), the gravitational part of the time-delay, depends only on well known physical constants, and on the inverse of the 2D Laplacian of the mass density profile in the lensing galaxy $`\mathrm{\Sigma }(\stackrel{}{\theta })`$. In other words, it strongly depends on the shape of the 2D mass profile of the lens (ellipticity, position angle), and on its slope. We will see later that the main source of uncertainty on the gravitational part of the time-delay comes from the radial slope of the mass distribution.

Several of the ingredients necessary to compute the time-delay can be precisely measured from observations. Although every lensed system has its own particularities, the positions of the lensed images defined by $`\stackrel{}{\theta }`$ are usually the easiest quantities to constrain. With present day instrumentation, an accuracy of a few milli-arcsec is reached. The position of the lensing galaxy relative to the quasar images, when it is not double or multiple can be of the order of 10 milli-arcsec. As for the position $`\stackrel{}{\beta }`$ of the source relative to the lens, it is usually free in lens models. No observation can constrain it.

In most cases, astrometry is not a major limitation to the use of lensed quasars. However, image configurations that are very symmetric about the center of the lens are more sensitive to astrometric errors than assymetric configurations. Let us assume that $`\stackrel{}{\beta }`$ is very small compared with $`\stackrel{}{\theta }`$ (i.e., the source is almost aligned with the lens and the observer). Lets then consider a doubly imaged quasar with two images located at positions $`\stackrel{}{\theta }_1`$ and $`\stackrel{}{\theta }_2`$ away from the lens, and separated by $`\stackrel{}{\theta }`$. The geometrical time-delay between the two images is:

$`\mathrm{\Delta }t_{\mathrm{geom}}=t(\stackrel{}{\theta _1})t(\stackrel{}{\theta }_2)`$ $``$ $`(1+z_\mathrm{L}){\displaystyle \frac{D_\mathrm{L}D_\mathrm{S}}{cD_{\mathrm{LS}}}}(\stackrel{}{\theta _1^2}\stackrel{}{\theta _2^2})`$ (4)
$`=`$ $`(1+z_\mathrm{L}){\displaystyle \frac{D_\mathrm{L}D_\mathrm{S}}{cD_{\mathrm{LS}}}}[\stackrel{}{\theta }(2\stackrel{}{\theta }_1\stackrel{}{\theta })].`$
If we now consider that the error on the image separation $`\stackrel{}{\theta }`$ is much smaller than the error on the position of image 1 relative to the lens, $`\stackrel{}{\theta _1}`$, we can approximate the error on the time-delay. Since the errors $`d\stackrel{}{\theta }_1`$ and $`d\stackrel{}{\theta }`$ on $`\stackrel{}{\theta }_1`$ and $`\stackrel{}{\theta }`$ are not much correlated, they propagate on the time-delay as

$$\frac{d\mathrm{\Delta }t_{\mathrm{geom}}}{\mathrm{\Delta }t_{\mathrm{geom}}}\frac{2}{(|2\stackrel{}{\theta }_1\stackrel{}{\theta }|)}d\theta _1.$$
(5)
In symmetric configurations, where the lens is almost midway between the images, $`2|\stackrel{}{\theta }_1||\stackrel{}{\theta }|`$, so that the denominator in equation (5) is zero or close to it, leading to large relative errors on the time-delay, and hence on H0, whatever mass model is adopted for the lensing galaxy.

The advantage of symmetric configurations over assymetric ones is that they often have more than two lensed images (the source is more likely to be within the area enclosed by the radial caustic; see previous chapters on the basics of quasar lensing), offering the opportunity to measure several time-delays per system. The drawback is a larger sensitivity to astrometric errors.

Redshift information is also of capital importance in the calculation of the time-delay. Time-delays are proportional to $`(1+z_\mathrm{L})`$ as seen in equation (4). The angular diameter distances also depend on the redshift of the lens and source $`z_\mathrm{L}`$ and $`z_\mathrm{S}`$. Both should therefore be measured carefully. Although the lens and source redshifts are available for most know system, their measurement is not as straightforward as one could expect. Given the small separation between the lensed images and the high luminosity contrast between the source and lens, obtaining a spectrum of the lens is often challenging and may involve significant struggling with the data (e.g., Lidman et al. 2000). In other cases, for example in systems discovered in the radio, one faces the opposite situation: the optical counterpart of the source is so faint that no spectrum can be obtained of it, while the lens is well visible (e.g., Rusin et al. 2001).

Finally, the other cosmological parameters such as $`\mathrm{\Omega }_\mathrm{\Lambda }`$ and $`\mathrm{\Omega }_0`$ also play a role in the calculation of the time-delay, through the angular diameter distances. The dependence of the distances on ($`\mathrm{\Omega }_\mathrm{\Lambda }`$,$`\mathrm{\Omega }_0`$) is however very weak. In addition, other methods (Supernovae, CMB) seem much better at pinning down their values than quasar lensing does. One shall therefore use the known values of ($`\mathrm{\Omega }_\mathrm{\Lambda }`$,$`\mathrm{\Omega }_0`$) in quasar lensing and infer H0, to which it is much more sensitive.

### 3.3. The Mass Model and Degeneracies

Most unknowns in the calculation of the time-delay can be measured from deep and sharp images (and spectra), but we have not paid much attention, so far, on the gravitational part of the time-delay. It depends on the mass surface density distribution $`\mathrm{\Sigma }(\stackrel{}{\theta })`$ of the lensing object(s), which can not be measured directly. It has therefore to be modeled, and getting a “realistic” estimate of $`\mathrm{\Sigma }(\stackrel{}{\theta })`$ is not trivial.

A good lens model should in principle be able to reproduce the observables with as few free parameters as possible. Ideally, this model should be unique. It is “asked” to reproduce the astrometry of the quasar images with a very high accuracy, as well as their flux ratios. In fact we will not consider the latter as a strong constrain. Even if flux ratios can be measured with an accuracy of the order of the percent, they are affected by extinction by dust and by microlensing events due to the random motion of stars in the lensing galaxy (see Schechter 2003; Wambsganss 2003). Flux ratios may therefore vary with time and wavelength. In addition, they should be corrected for the effect of the time-delay, i.e., each quasar image should be measured when the quasar is seen in the same state of activity. This can be done for quasars with known time-delays and well measured light curves. Curiously, such a correction is not much taken into account in the literature, even for quasars with known time-delays.

When modeling lensed quasars, one is asked, on the basis of a few (usually 2 or 4) quasar images, to model the whole two-dimensional gravitational potential of the lensing galaxy or galaxies. There is of course no unique solution to the problem: too few observational constraints are available and several mass models giving each one a different time-delay can reproduce a given image configuration, its astrometry and flux ratios. In other words, lens models are degenerate.

Degeneracies have been described and blamed abundantly in the literature for being the main source of uncertainty in lens models (see for example Saha 2000; Wucknitz 2002). Whatever precision on the measured astrometry and time-delay, several mass models will predict several time-delays and hence several H0. One must devise techniques to break the degeneracies or find quasars that are less affected by them.

The main degeneracy one has to face in quasar lensing is called the mass sheet degeneracy: when adding to a given mass model, a sheet of constant mass density (i.e., constant convergence $`\kappa `$, as defined in the preceding chapters), one does not change any of the observables, except for the time-delay. The additional mass can be internal to the lensing galaxy (e.g., ellipticity does not change the total mass within the Einstein radius, but does change $`\kappa `$ at the position of the images) or due to intervening objects along the line of sight. The exact mass introduced by the mass sheet increases the total mass of the lens, but one can re-scale it and locally change its slope at the position of the images. The result is that the image configuration does not change, but the convergence $`\kappa `$, at the position of the images does change, and modifies the time-delay. Therefore, knowledge of the the slope of the mass profile of the lensing galaxy, whether it be under the form of a model or of a measurement, is one of the keys to the determination of a “good” model.

Changing the slope of the lens will change $`\kappa `$ at the position of the images, but adding intervening objects along the line of sight to the lens has a similar effect. A group or cluster of galaxies, located angularly close to the lens, will add its own contribution to the total mass density at the position of the images. If the group/cluster has a constant density $`\kappa `$, rescaling the total mass of the lensing galaxy by $`1/(1\kappa )`$ will leave the observed images configuration unchanged, as illustrated in Fig. 4, but will change the time-delay.

Adding convergence also modifies the shear $`\gamma `$, hence the ellipticity of the main lens. There are therefore several ways of reproducing a given combination of shear and convergence at the position of the images, as illustrated in Fig. 4. In the left panel of the figure, the shear $`\gamma `$, is produced only by the main elliptical lensing galaxy. In the right panel, the total shear is a combination of the lens-induced shear and of that of the nearby galaxy cluster. In principle, it is even possible to model a given system equally with either one single elliptical lens or with a completely circular lens and an intervening cluster responsible for an “external” source of shear.

Both types of degeneracies can be broken or, at least, their effect can be strongly minimized, by constraining in an independent way (1) the mass profile of the main lens, and (2) the total mass (and possibly also the radial mass profile) of any intervening cluster along the line of sight. This work can be done with detailed imaging, spectroscopy of all objects along the line of sight, and by using numerical multi-components models for the total lensing potential. This is the topic of the next section, illustrated through the example of the well studied quadruple PG 1115+080.

## 4. PG 1115+080: a Clean Quadruple

PG 1115+080 is one of the first case of quadruply imaged quasar (Weymann et al. 1980) and among the best studied lensed quasars, one of the still rare systems with well measured time-delays (Schechter et al. 1997). The tremendous gain in spatial resolution achieved since the eighties (see Fig. 5), has allowed detailed understanding of the system. Since the range of observational data available for PG 1115+080 is so broad, we take this object as an example to show how observations help to pin down the Hubble parameter H0.

PG 1115+080 is a bright quasar at z=1.722, with a relatively “wide” angular separation between its images, of the order of 2′′. Two images are isolated (B and C in Fig. 5) and a blend of two brighter images, is located on the other side of the lens in projection on the plane of the sky (A1/A2 on Fig. 5). This blend A1/A2 was not resolved on the discovery images of the object, and PG 1115+080 was subsequently believed to be a triple until more detailed observations revealed it was in fact a quadruple (Young et al. 1981). Applying Refsdal’s method (1964) to PG 1115+080 has been a long process. Some of the ingredients necessary to the lens modeling had to wait for years before suitable observations finally became available.

### 4.1. Redshifts

As already mentioned, the redshift of the lensing galaxy $`z_\mathrm{L}`$ is mandatory for the determination of any model. Although PG 1115+080 was discovered in 1980, it is only in 1997 that $`z_\mathrm{L}`$ was measured (Kundic et al. 1997), by using the Keck telescope. The galaxy is at low redshift, z$`{}_{\mathrm{L}}{}^{}=0.311`$. With deeper exposures, its velocity dispersion has also been measured, $`\sigma _\mathrm{L}=281\pm 25`$ km.s-1 as well as the velocity dispersion of a group of galaxies found along the line of sight (Fig. 6), $`\sigma _{\mathrm{grp}}=326`$ km.s-1 (Tonry 1998). These measurements provide us with an independent estimate of the total mass of the lens and intervening group. They are crucial when trying to break the mass sheet degeneracy.

### 4.2. Time-delays and Temporal Sampling

With its bright images, its wide angular separation, and with the availability of reference stars within a few arc-minutes, PG 1115+080 is an excellent target for photometric monitoring. Excellent does not automatically imply easy ! Photometric monitoring still requires good seeing, at least a medium size telescope (2m) and a temporal sampling adapted to the observed variations.

Choosing the temporal sampling of the light curves is critical. It is often claimed that it should be smaller than half the expected time-delay, but this is not quite true. The measurement of the time-delay is done through the measurement of the photometric variations of the quasar itself. Therefore, the sampling should be chosen according to the typical time-scale observed or expected in the photometric light curves. In an ideal case where the intrinsic variations of the source are slow compared with the time-delay, one can in principle chose a sampling even larger than the time-delay. The situation is quite the same than in image processing where one can measure the position of an object on a CCD frame with a much higher accuracy than the sampling adopted to represent this signal.

However, while one do not need in principle very high temporal sampling, the situation in practice is just the opposite. First, one does not know in advance what the time-scale of the variations will be: the frequency range in quasar variability spans from days to weeks or even months. Second, even if the variations are slow, their amplitude is small, often of the order of a few tens of a magnitude, sometimes a bit more in the case of Broad Absorption Lines (BAL) quasars. Measuring faint variations is easier with well sampled light curves. Well sampled curved are, in addition, well suited to the use of cross-correlation techniques in order to measure the time-delay. Finally, microlensing by stars in the lensing galaxy introduces flickering of the light curves, with a frequency that is in general unknown and not even easy to predict before the data are actually taken. There is therefore no general line to adopt on the choice of the sampling other than trying to get “the finest possible sampling” !

The case of PG 1115+080 is lucky enough that the photometric variations of the source are slow, and well sampled light curves could be obtained (Schechter et al. 1997; see Fig. 7). Even with light curve of such a quality, extracting the time-delay(s) can be tricky. Schechter et al. (1997) uses the method devised by Press et al. (1982) to compute a global $`\chi ^2`$ between shifted versions of the light curves. They estimate the time-delay between components C and B to be $`\mathrm{\Delta }t(CB)=23.7\pm 3.4`$ days and the time-delay between component C and A is $`\mathrm{\Delta }t(CA)=9.4`$ days, where C is always the first one to vary, i.e., the “leading image”. A different approach was chosen by Barkana (1997) to analyse the same data. Using an analytical representation of the light curves and taking into account the correlations between the errors on the individual photometric measurements, they derive a very similar time-delay between components C and B, $`\mathrm{\Delta }t(CB)=25_{3.8}^{+3.3}`$ but the second time-delay is significantly longer $`\mathrm{\Delta }t(CA)=13`$ days.

### 4.3. Modeling and Influence of the Astrometry

Using a simple isothermal model plus external shear (induced by the cluster) Schechter et al. (1997) infered H0 = 42 km.s-1.Mpc-1, but no detailed observations of the lensing galaxy was available at that time. In fact, Schechter et al. (1997) found that a value as high as 84 was possible as well. Keeton & Kochanek (1997) investigated analytical models for the lensing galaxy, including isothermal profiles and softened power laws with core radius. They found that the potential well in PG 1115+080 could not be modeled using a single lensing galaxy, whatever its mass profile. External shear by the nearby group had to be invoked. A combination of models were tested for the main lens and for the cluster, and analyzed in a statistical way in order to derive a probability density for H0. The experiment is done in two ways: by taking into account only one time-delay in PG 1115+080, and by using the two measured time-delays.

The models by Keeton & Kochanek are based on astrometry obtained with HST data, before the optics was refurbished (Kristian et al. 1993), and with rather large astrometric errors. As systems with symmetric image configurations about the lens are more sensitive to errors on the astrometry than assymetric ones, the result by Keeton & Kochanek could be improved further, simply by improving the HST astrometry. This was done by applying deconvolution techniques to ground based images of PG 1115+080. Fig. 8 illustrates the gain in the accuracy. With the new astrometry, not only the width of the probability distributions is decreased, but there is also better agreement between the curves obtained for one and for two time-delays. The combined probability for the pre-refurbishment HST astrometry is H0 of 51$`{}_{10}{}^{}{}_{}{}^{+14}`$ km.s-1.Mpc-1while H0 = 53$`{}_{7}{}^{}{}_{}{}^{+10}`$ km.s-1.Mpc-1with the improved astrometry.

In parallel with the efforts to improve the observational constraints for PG 1115+080, new models were developed, with the aim of exploring more of the parameter space defined by the slope of the mass profile of the lens, its ellipticity and its position angle. One approach to the problem is to consider a family of non-parametric models, where the lensing galaxy is decomposed on a grid of mass “pixels” or tiles. The astrometry, flux ratios, and time-delays are given as observational constraints, and the output of the procedure is a pixelized mass map of the lens, as well as its slope. As is done for parametric models, one can have a statistical approach and run many models in order to infer a probability density for H0 (Williams & Saha 2000). As the range of possible models is much broader with the non-parametric approach than with the parametric one, it was found that H0 could be anything between 42 and 84, given the observations available for PG 1115+080 at that time (Saha & Williams 1997) !

### 4.4. HST Imaging: the Quasar Host Galaxy

Improving the astrometry over and over, helps, but does not solve the fundamental problem imposed by the mass sheet degeneracy. The number of lensed images available can not be increased, so that potential well of the lens, and hence the arrival-time surface, are probed only at a very limited number of points. This is quite not true as soon as one considers extended sources. Quasars have host galaxies. They are faint, but they have a much larger angular size than the quasar they harbourgh. The effect of lensing on their shape, distorted and stretched, is much stronger than on the point source quasar. The role of high angular resolution observations therefore extends well beyond the simple aim of measuring the image positions and fluxes. Each detail discovered in the lensed image of the host galaxy is an additional point in the mass map.

PG 1115+080 has been observed with the refurbished HST, in the infrared (Impey et al. 1998), with a resolution and depth sufficient to unveil an almost full ring joining the quasar images (Fig. 9). While the host galaxy provides more constraints for the models, it also forces to introduces more degrees of freedom. Indeed, a model has to be chosen to represent the “unlensed” host, for example an exponential disk, as done in Impey et al. (1998). Feeding the lensing model with the image positions, time-delays, flux ratios, lens ellipticity, position of the nearby group of galaxies, and the model for the host, one can reproduce the observed ring.

The actual gain brought by the ring is significant but not always sufficient to discriminate between lens models. Impey et al. (1998) give two estimates for H0 for two different type of lens models. One assumes that light traces mass, i.e., that the mass-to-light ratio is constant in every point of the lens. The second, more realistic according to our current knowledge of the mass distribution in galaxies, includes a dark halo component. Using these two models, they find H0 = 66 km.s-1.Mpc-1and H0 = 44 km.s-1.Mpc-1, respectively.

A complete Einstein ring was found in PG 1115+080, but with no resolved details, only the surface brightness can be used to constrain the models. Because the of the high degree of symmetry of the system, and given the resolution of the observations, it is not clear whether full rings are actually useful for sorting out between different mass models, or not (see, e.g., Saha & Williams, 2001).

Many other lensed hosts galaxies have been discovered using HST images (Lehar et al. 2000), in systems that are less symmetric than PG 1115+080, and with higher degree of detail. A good example is the double Q 0957+561 in which the host galaxy reveals clumps, distorted arcs and for which a different approach of the modeling was used, not involving any prior model for the host’s surface brightness (Keeton et al. 2000). Since the observations of the host of Q 0957+561 are probably the most detailed existing so far, we will briefly leave PG 1115+080 aside and use Q 0957+561 to illustrate the use of hosts in quasar lensing. The observations are shown in Fig. 10, while Fig. 11 illustrates the modeling method. Based on the image of the brighter component A of the host, mapping it back onto the source plane, the unlensed host is reconstructed. It is then re-imaged, in order to produce the fainter image B, and a $`\chi ^2`$ is minimized, between the observed image and the prediction from the model. The method takes advantage of the high degree of details in the host, and on the assymetric configuration of the system. It does not require any strong prior knowledge on the host. The method allows to rule out several models previously published in the literature.

### 4.5. Yet Further Constraints: Spectroscopy

So far, and mainly for technical reasons, the most important constraints on lens models were coming from imaging. Spectroscopy is nevertheless another key component, that will become of growing importance in the near future, thanks to 3D spectrographs mounted on large telescopes.

Spectroscopy provides independent access to the total mass of the lenses: whenever an intervening cluster or group is seen close to the line of sight to a lens, measuring its velocity dispersion helps to break the mass sheet degeneracy it introduces with the mass of the main lens (e.g., Falco et al. 1997; Tonry 1998; Kneib et al. 2000). If a measurement of the velocity dispersion of the main lens is available as well, the effect of the mass sheet degeneracy is greatly minimized In the case of PG 1115+080, both the velocity dispersion of the main lens and nearby group are available (see Table 1).

For an isothermal sphere the line of sight velocity dispersion $`\sigma `$ is directly related to the Einstein radius, through the H0 independent relation:

$$\theta _\mathrm{E}=4\pi \frac{\sigma ^2}{c^2}\frac{D_\mathrm{L}}{D_\mathrm{S}}$$
(6)
Since the Einstein radius $`\theta _\mathrm{E}`$ only depends on the total mass of the lens (within the Einstein radius), measuring the velocity dispersion does not yield the mass profile of the lens. Nevertheless, it can be used to put strong constraints on the mass profile, using further knowledge we have on galaxies in general. Treu & Koopmans (2002) take the problem under this view angle and feed dynamical models of galaxies with the measured velocity dispersions in PG 1115+080. In their model, the lensing galaxy is composed of a dark matter halo with a mass density profile of the form $`\rho (r)=r^\gamma `$ ($`\gamma =1`$ for a Navarro, Frenk & White (1997) profile) and a Jaffe stellar density profile (Jaffe 1983). New parameters appear in the model: the slope $`\gamma `$ or the dark matter halo, and the fraction of the galaxy that is under the form of (luminous) stars, f. However, ($`\gamma `$, f) define a parameter space with a rather sharp peak, centered at $`\gamma 2.35`$ and f$`{}_{}{}^{}0.67`$, for PG 1115+080. There is therefore a rather small range of lens models that fit simultaneously the physical properties of the lens, and the constraints imposed by lensing. Using this approach leads to H$`{}_{0}{}^{}=59_7^{+12}`$ km.s-1.Mpc-1, a value which is much less affected by systematic errors than other estimates, not taking the dynamical information into account.

Measuring velocity dispersions in faint objects in not easy, especially when they are blended with bright quasar images. It has been possible, so far, only for a few systems, but spectrographs are starting to be used on large telescopes where adaptive optics observations are carried out in a flexible way. Three-dimensional spectrographs are planed on these telescopes, and may well yield not only the velocity dispersion of lenses, but also their full velocity field. In many cases, one will be able to measure at least the velocity dispersion profile, hence constraining much better the mass profile of the lens, independent of lensing.

### 4.6. H0 with PG 1115+080

Although many lensed quasars are potentially as powerful as PG 1115+080 for constraining H0, this nice quadruple remains one of the best studied cases so far, along with the double Q 0957+561. Basically all possible observational tools have been used to study PG 1115+080, and we have adopted it as an example to illustrate how observations help the theorist in quasar lensing. Some of the main results obtained for PG 1115+080 are summarized in Table 1, following the chronological order of the observational saga of the object.

As the observations of PG 1115+080 were improving, various values were found for H0 along the years. This is mainly a consequence of the mass sheet degeneracy and to the lack of observational constraints on the actual mass profile of the lens. Among the range of possible values, the highest ones were obtained for lenses with constant mass-to-light ratios, and lower values of H0 were found for models including a dark matter halo. If our knowledge of the physics of galaxies is any good, the latter lens model is closer to the truth than the former. This results in values for H0 that disagree (see Table 1) with local estimates, based on standard candles, i.e., H0 = 72$`\pm `$8 km.s-1.Mpc-1 (Freedman et al. 2001).

## 5. Mass Production of Time-Delays: H0 with Other Lenses

Measuring time-delays has long been the main limitation to the use of quasar lenses in cosmology. Indeed, obtaining on a regular basis images of good quality and for long period of time is not easy. With the increasing number of large telescopes in excellent sites, and operated in “service mode”, we have nevertheless entered a phase of mass production of time-delays. It took more than a decade to obtain the time-delay in Q 0957+561, but four time-delays were recently measured in one single thesis (Burud, 2000b) thanks to modern instrumentation and image deconvolution techniques. In addition, systematic imaging campaigns of lensed quasars such as the one carried out by CASTLE, facilitate the modeling of lens galaxies. Deep HST images are used in combination with spectroscopy, and along with what we know of the physics/dynamics of galaxies, to break the degeneracies between the models.

Even if the observational situation in quasar lensing is expected to improve a lot in the coming years, thanks to adaptive optics and 3D spectrographs, we can already say, with the precision of the observations collected so far, that lensed quasars are at least as powerful as other methods to determine H0.

Let us play the naive game that consists in taking from literature the nine estimates of H0, for each of the nine measured time-delays, and average them. This is summarized in Table 2 for all known lenses, along with the time-delay measurements. We indicate in the table the value obtained for H0 with all kind of different models, just scaling the published errors to 1$`\sigma `$. Some authors consider isothermal spheres or ellipsoids with and without external shear. Others prefer to use lenses with constant mass-to-light ratios. In other words, the values we quote in Table 2 are all affected by unknown systematics. These systematics have been estimated by each author and included in the published error bars. If they had been under- or over- estimated, the dispersion between all the individual estimates of H0, and the published errors on one single measurement, would be incompatible. Following our naive idea the averaged value for H0, (without error weighting) is H0=61$`\pm `$7 km.s-1.Mpc-1. Figure 12 is another way of displaying the data of Table 2, showing the value of H0 as a function of the lens redshift. The 1$`\sigma `$ error region is dashed on the figure. Four measurements (in fact 3, if we include the mean value for the 2 estimates for HE 1104-1805 in the dashed area) are outside the 1$`\sigma `$ region, as expected for 9 independent measurements. Unless all the authors did the same systematic error (and this is unlikely because of the very different choices of models), the dispersion between the points is fully compatible with the individual error bars. This means that even if the models suffer from systematics, the amplitude of the error has been correctly estimated by the authors.

A more correct approach is to impose that a given family of profiles is used to model the mass distribution of lenses in general, and to impose that H0 should be the same everywhere in the Universe. This has been done so far by very few authors. Williams & Saha (2000), use two systems and their non-parametric models, to infer H0=61$`\pm `$11 km.s-1.Mpc-1(1$`\sigma `$ error). Courbin et al. (2002) add two other lenses to the Williams & Saha sample, and adopt the same non-parametric technique to infer H0=64$`\pm `$4 km.s-1.Mpc-1. Using parametric lens models and a set of 4 different lenses (only PG 1115+080 is common to all authors) Kochanek (2002) obtain H0=51$`\pm `$5 km.s-1.Mpc-1if lens galaxies have dark matter halos, or H0=73$`\pm `$8 km.s-1.Mpc-1if lens galaxies have constant mass-to-light ratios.

Gravitationally lensed quasars have one drawback over other methods for determining H0: they do require good knowledge of the mass profile of the lens. It has long been a limitation to the effectiveness of the method to produce reliable estimates of H0, but this drawback is becoming easier and easier to overcome, thanks to spectroscopy, to high spatial resolution observations, and to the progresses made on the physics of galaxies. Gravitational lenses have, on the other hand, tremendous advantages over other methods. First, they do not rely on any “standard candle” which would rend the method close to useless if the standard candle turned out to be significantly deviant from the “standard” behaviour. Second, it does not require secondary calibrators of the standard candle, e.g., low redshift objects, in the case of the supernovae method. Third, it probes H0 at cosmological distances, independent of any local effect such as peculiar velocities of nearby galaxies. Finally, lensing is not as sensitive to the other cosmological parameters ($`\mathrm{\Omega }_m`$, $`\mathrm{\Omega }_\mathrm{\Lambda }`$) than the other methods.

We compare in Fig. 12, the value of H0 for lensed quasars and for the Cepheid method. With the present error bars, calculated with only 9 objects, we can say that lensed quasars and Cepheid disagree. Lensing gives lower values for H0 than does the Cepheid method. If our knowledge of the mass distribution of galaxies is any good, i.e., that galaxies have dark matter halos, the lensing value would be even smaller. Recent CMB experiments such as WMAP find high values for H0 (e.g., Spergel 2003), in agreement with the local estimate: H0=71, with impressive error bars of only 4$`\%`$. With the high degree of degeneracy between the cosmological models used to represent the observed CMB power spectrum, H0 is in fact shown to take any value between 54 and 72 (Efstathiou 2003). It spans over an even broader ranger if one does not invoke any prior knowledge on the value of $`\mathrm{\Omega }_m`$ and $`\mathrm{\Omega }_\mathrm{\Lambda }`$ as determined with supernovae.

In fact, no single method has been proved to be good enough that it can surpass the others. There are, however, methods that are better than others as pinning down some of the cosmological parameters and it has been emphasized many times (Bridle et al. 2003) that all methods should be combined in order to break the degeneracies inherent to one specific method. Gravitational lensing is one of these methods. It has advantages and drawbacks, but probably many more advantages than drawbacks given the present observational context.

#### Acknowledgments.

The author wishes to thank Alain Smette and Pierre Magain for useful discussions. Frédéric Courbin is supported by the European Commission through a Marie Curie Individual Fellowship, under grant MCFI-2001-0242. The collaborative grant ECOS/CONICYT C00U05 between Chile and France is also gratefully acknowledged.

## References

Barkana, R. 1997, ApJ, 489, 21

Biggs, A.D., Browne, I.W.A., Helbig, P., et al. 1999, MNRAS, 304, 349

Bridle, S.L., Lahav, O., Ostriker, J.P., et al. 2003, astro-ph/0303180

Burud, I., Hjorth, J., Jausen, A.O., et al. 2000, ApJ, 544, 117

Burud, I., 2000, PhD, Liège University, Belgium

Burud, I., Hjorth, J., Courbin, F., et al. 2002, A&A, 391, 481

Burud, I., Courbin, F., Magain, P., et al. 2002b, A&A, 383, 71

Courbin, F., Magain, P., Keeton, C.S., et al. 1997, A&A, 324, L1

Courbin, F., Saha, P., Schechter, P.L. 2002, in “Gravitational Lensing: An Astrophysical Tool”, LNP topical volume 608, (eds. Courbin, Minniti), p1

Efstathiou, G. 2003, astro-ph/0303127

Falco, E.E., Shapiro, I.I., Moustakas, L.A., et al. 1997, ApJ, 484, 70

Fassnacht, C.D., Xanthopoulos, E., Koopmans, L.V.E., et al. 2002, ApJ, 581, 23

Freedman, W.L., Madore, B.F., Gibson, B.K., et al. 2001, ApJ, 553, 47

Gil-Merino, R., Wisotzki, L., Wambsganss, J. 2002, A&A, 381, 428

Goicoechea, L. J. 2002, MNRAS, 334, 905

Hewitt, J.N., Turner, E.L., Lawrence, C. R., et al. 1992, AJ, 104, 968

Hjorth, J., Burud, I., Jaunsen, A.O., et al. 2002, ApJ, 572, L11

Huchra, J., Gorenstein, M., Kent, S., et al. 1985, AJ, 90, 691

Impey, C.D., Falco, E.E., Kochanek, C.S., et al. 1998, ApJ, 509, 551

Iwamuro, F., Motohara, K., Maihara, T., et al. 2000, PASJ, 52, 25

Jackson, N., Nair, S., Browne, I.W.A., et al. 1998, MNRAS, 296, 483

Jaffe, W. 1983, MNRAS, 202, 995

Keeton, C.R., Falco, E.E., Impey, C.D., et al. 2000, ApJ, 542, 74

Keeton, C.R., Kochanek, C.S. 1997, ApJ, 487, 42

Kneib, J.-P., Cohen, J.G., Hjorth, J. 2000, ApJ, 544, L35

Kochanek, C.S. 2002, ApJ, 578, 25

Kochanek, C.S., Falco, E.E., Impey, C., et al. 2003a, the CASTLE database, http://cfa-www.harvard.edu/glensdata/

Kochanek, C.S. 2003b, ApJ, 583, 49

Koopmans, L.V.E., de Bruyn, A.G., Xanthopoulos, E., et al. 2000, A&A, 356, 391

Kristian, J., Groth, E.J., Shaya, E.J., et al. 1993, AJ, 106, 1330

Kuijken, K. 2003, this volume

Kundic, T., Cohen, J.G., Blandford, R.D., et al. 1997, AJ, 114, 507

Kundic, T., Turner, E.L., Colley, W.N., et al. 1997, ApJ, 482, 75

Langston, G.I., Schneider, D.P., Conner, S., et al. 1989, AJ, 97, 1283

Lawrence, C. R., Bennett, C. L., Hewitt, J. N., et al. 1986 ApJS, 61, 105

Leh r, J., Falco, E.E., Kochanek, C.S., et al. 2000, ApJ, 536, 584

Lidman, C., Courbin, F., Kneib, J.-P., et al. 2000, A&A, 364, L62

Lovell, J.E.J., Jauncey, D.L., Reynolds, J.E., et al. 1998, ApJ, 508, L51

Magain, P., Surdej, J., Swings, J.-P., et al. 1988, Nature, 334, 327

Myers, S.T., Fassnacht, C.D., Djorgovski, S.G., et al. 1995, ApJ, 447, L5

Navarro, J., Frenk, C.S., White, S.D.M. 1997, ApJ, 490, 493

Patnaik, A. R., Browne, I. W. A., Walsh, D., et al. 1992, MNRAS, 259, 1

Press, W.H., Rybicki, G.B., Hewitt, J.N. 1992, ApJ, 385, 404

Refsdal, S. 1964, MNRAS, 128, 307

Rusin, D., Marlow, D.R., Norbury, M., et al. 2001, AJ, 122, 591

Saha, P., Williams, L.L.R. 2001, AJ, 122, 585

Saha, P. 2000, AJ, 120, 1654

Saha, P., Williams, L.L.R. 1997, MNRAS, 292, 148

Schmidt, M. 1963 Nature, 197, 1040

Schechter, P.L., Bailyn, C.D., Barr, R., et al. 1997, ApJ, 475, 85

Schechter, P.L. 2003, this volmune

Schneider, P., Ehlers, J., Falco, E.E. 1992, in Gravitational lenses, Astronomy and Astrophysics Library, Springer-Verlag.

Schneider, D. P., Turner, E. L., Gunn, J. E. 1988, AJ, 95, 1619

Spergel, D.N., Verde, L., Peiris, H.V., et al. 2003, astro-ph/0302209

Sluse, D., et al. 2003, submitted to A&A

Smette, A. 2003, this volume

Surdej, J., Magain, P., Swings, J.-P., et al. 1987, Nature, 329, 695

Tonry, J.L. 1998, AJ, 115, 1

Treu, T., Koopmans, L.V.E. 2002, MNRAS, 337, L6

Turner, E. L. 1980, ApJ, 242, L135

Vanderriest, C., Schneider, J., Herpe, G., et al. 1989, A&A, 215, 1

Walsh, D., Carswell, R. F., Weymann, R. J. 1979, Nature, 279, 381

Wambsganss, J. 2003, this volume

Weymann, R. J., Chaffee, F. H., Carleton, N. P., et al. 1979, ApJ, 233, L43

Weymann, R. J., Latham, D., Roger, J., et al. 1980, Nature, 285, 641

Williams, L.L.R., Saha, P. 2000, AJ, 119, 439

Wisotzki, L., Koehler, T., Kayser, R., et al. 1993, A&A, 278, L15

Wucknitz, O. 2002, MNRAS, 332, 951

Wyithe, J.S., Winn, J.N., Rusin, D. 2003, MNRAS, 583, 58

Young, P., Deverill, R.S., Gunn, J.E. 1981 ApJ, 244, 723


text:
# Relationship Between Cepheid and Tully-Fisher Distance Calculations

## 1 INTRODUCTION

The residual between the Cepheid distance calculation $`D_c`$ for a galaxy and the Tully-Fisher relationship (TF) distance calculation $`D_{tf}`$ for the galaxy varies among galaxies (Shanks, 1997; Shanks et al., 2002). The residual can be small for some galaxies or greater than the sum of the errors of each calculation for other galaxies. The $`D_{tf}`$ to a target galaxy is determined by relating the 21-cm line width at 20 percent of the peak value $`W_{20}`$ corrected for the inclination between our line of sight and the target galaxy’s polar axis $`i`$ with the absolute magnitude $`M`$ in various wavelength bands (Tully et al., 1998). The $`D_c`$ is based on the observation that pulsating Cepheid stars in a galaxy have a $`M`$ related to their pulse period. Cepheids obey very well defined relations and so make excellent standard candles (Binney & Merrifield, 1998)(page 415). This paper uses $`D_c`$ as standard distances. In this Paper, the influence of neighboring galaxies on $`M`$ is investigated for the first time. A remarkably tight correlation is found relating the illumination of neighboring galaxies to ($`D_cD_{tf}`$) for redshift $`z<0.006`$. Since this result was obtained with the assumption that the mass of a galaxy is constant over time, there may be a fundamental physical mechanism regulating the mass of galaxies. Also, the TF assumption that the intrinsic mass to intrinsic luminosity ratio is constant among galaxies (Aaronson, Huchra, & Mould, 1979) is valid for $`z<0.006`$.

The object of this paper is to examine the effect of neighboring galaxies on $`D_{tf}`$. Thereby, the residual between $`D_c`$ and $`D_{tf}`$ distances may be reduced. The approach is to (A) develop an equation from the Principle of the Conservation of Energy describing the influence of neighboring galaxies on $`D_{tf}`$, (B) choose galaxies with published Cepheid distances, and (C) apply the model to the target galaxies.

## 2 MODEL

The light emitted from a galaxy is energy from the galaxy. The Principle of the Conservation of Energy in a galaxy requires,

$$\mathrm{\Delta }𝖬c^\mathit{2}+E_{\mathrm{𝑜𝑢𝑡}}=E_{\mathrm{𝑖𝑛}}+ϵ,$$
(1)
where $`\mathrm{\Delta }𝖬`$ is the rate of change of mass $`𝖬`$ in the target galaxy, $`c`$ is the speed of light, $`E_{out}`$ is the rate energy radiates from the target galaxy, $`E_{in}`$ is the rate of transmittal of energy from another galaxy into the target galaxy, and $`ϵ`$ is the rate of intrinsic energy production from mass conversion processes in the target galaxy.

McLure & Dunlop (2002) found that the mass in the central region of a galaxy is 0.0012 of the mass of the bulge. Ferrarese and Merritt (2002) reported that about 0.1% of a galaxy’s luminous mass is at the center of galaxies and that the density of supermassive black holes (SMB) in the universe agrees with the density inferred from observation of quasars. Merritt & Ferrarese (2001); Ferrarese and Merritt (2002) found similar results in their study of the relationship between the mass $`𝖬_{}`$ of a SMB and dispersion velocity $`\sigma `$ of a galaxy. Ferrarese (2002) found a tight relation between rotation velocity $`v_c`$ and bulge velocity dispersion $`\sigma _c`$ which is strongly supporting a relationship of the center force with total gravitational mass of a galaxy. Either the dynamics of many galaxies are producing the same increase of mass in the center at the same rate or a mechanism exists to evaporate (convert to radiated energy) the mass increase that changes as the rate of inflow changes. The rotation curves imply the dynamics of galaxies differ such that the former is unlikely. Merritt & Ferrarese (2001b) suggested a feedback mechanism must exist in such a way that $`\mathrm{\Delta }\mathrm{log}(𝖬_{}`$$`)4.5\mathrm{\Delta }\mathrm{log}(\sigma )`$. Therefore, $`𝖬`$ is assumed to remain constant, the matter in an incremental cylinder shell of a galaxy is constant, and $`\mathrm{\Delta }𝖬=\mathrm{𝟢}`$. Whatever the source of matter in a galaxy, the energy content of the inflowing matter equals $`ϵ`$. Constant mass in a galaxy and the observation of $`ϵ`$ implies there is inflowing matter.

Another source of energy for a galaxy is from other galaxies as $`E_{in}`$. The energy transfer from other galaxies can be (A) in the form of photons $`E_a`$, (B) in the form of potential energy $`E_p`$ from gravitational forces of other galaxies. The $`E_a`$ component is dependant on the surface area cross section of the target galaxy presented to the other galaxy, the distance between galaxies, and the $`M`$ of the other galaxies. The $`E_p`$ is a conservative field. If the matter in an incremental cylinder shell of the target galaxy is constant, then $`E_p=0`$. The heat change caused by the movement of a galaxy as a whole in a potential field is assumed to be negligible in the B band.

Therefore, conservation of energy implies the only radiated energy observed is from re-radiated energy from neighboring galaxies and from $`ϵ`$,

$$E_{out}10^{\frac{M}{2.5}}=K_aE_a+K_eϵ,$$
(2)
where $`K_a`$ and $`K_ϵ`$ are proportionality constants of $`E_a`$ and $`ϵ`$, respectively \[herein called “Conversion Efficiencies” (CE)\] and $`E_{in}=K_aE_a`$. The CE’s represent the fraction of energy transmitted in the measurement band of $`M`$ relative to the available energy. Hence, $`K_aE_a`$ is the observed luminosity originally from neighbor galaxies re-emitted from a target galaxy and $`K_eϵ`$ is the observed intrinsic luminosity of the target galaxy. Since $`ϵ`$ will vary among galaxies, $`K_eϵ`$ will also vary among galaxies. The $`K_a`$ is a function of the target galaxy’s absorption per unit surface area and the re-emitted light per unit absorption. Since the HI mass to total mass ratio increases systematically from giant galaxies towards dwarf galaxies (Karachentsev, Makarov, & Hutchmeier, 1999), $`K_a`$ may change accordingly. Therefore, it is reasonable to assume that the $`K_a`$ also changes with $`ϵ`$.

Consider the ($`D_cD_{tf}`$) as an error in $`D_{tf}`$. The error rate is defined as the correction factor $`C_f`$,

$$C_f\frac{D_cD_{tf}}{D_{tf}},$$
(3)
or,

$$D_c=D_{tf}(1+C_f).$$
(4)
Consider the attenuation of energy is a constant factor $`F_a`$ of the light from the target galaxy. The term on the left side of equation (2) is the luminosity calculated by the TF relation. If $`D_c`$ is the true distance, the last term on the right side of equation (2) is the intrinsic luminosity that would be calculated using $`D_c`$. Therefore, $`D_{tf}=F_a10^{M/2.5}`$ and $`D_c=F_aK_eϵ`$. Substituting these relations into equation (3)and solving equations (2) and (3) for $`C_f`$ yields,

$$C_f=\frac{K_aE_a}{K_eϵK_aE_a}.$$
(5)
A binomial expansion of the denominator of equation (5) yields,

$$C_f=K_sE_a+K_i,$$
(6)
where $`K_i`$ is the sum of second and higher order terms and is approximately a constant and,

$$K_s=\frac{K_a}{K_eϵ}.$$
(7)
If $`K_aK_eϵ`$ among galaxies, then a plot of $`C_f`$ versus $`E_a`$ will yield a linear relationship. That is, for each $`E_a`$ there corresponds one and only one value of $`C_f`$. Therefore, $`C_f`$ is a functional relationship of $`E_a`$. The function may have discontinuities and gaps but it is still one relationship.

Galaxies with a measured $`D_c`$ can be used as calibration galaxies to calculate $`K_s`$ and $`K_i`$. Then equations (4) and (6) can be used to calculate a distance corresponding to a $`D_c`$.

## 3 DATA AND ANALYSIS

The criteria for choosing galaxies for the analysis are (1) the galaxy has a published Cepheid distance, (2) the distance to the galaxy must be large enough that the Milky Way’s contribution to $`E_a`$ is negligible, (3) the distance to the galaxy must be large enough that the contribution of the peculiar velocity to the redshift $`z`$ measurement is relatively small, and (4) either a published total apparent magnitude in the in the B band $`m_b`$ or a published total apparent corrected I-band magnitude $`m_i`$ must be available for both the target and close galaxies.

The data and references for the 31 target galaxies is presented in Table 1. The morphology type data was obtained from the NED database111The NED database is available at: http://nedwww.ipac.caltech.edu. . The de Vaucouleurs radius $`R_{25}`$, the $`m_b`$ (“btc” in the Leda database), the $`m_i`$ (“itc” in the Leda database), and $`W_{20}`$ data came from the LEDA database 222The LEDA database is available at: http://leda.univ-lyon1.fr. . The value of “btc” for close galaxies was used since I band data is generally unavailable. In 35 of the 310 close galaxies, the “btc” was not available in LEDA. The B band magnitude from NED, which is not corrected, was then used. In 14 galaxies $`m_b`$ was unavailable from either database. These galaxies were deleted from the calculation and the next closest galaxy added to have 10 galaxies for the calculation. The $`m_b`$ for the galaxies which used the NED magnitude have relatively high values. Therefore, their significance was low. The $`D_c`$ was taken from Freedman et al. (2001) distance modulus except as noted in Table 1.

The sample of target galaxies included (A) low surface brightness (LSB), medium surface brightness (MSB), and high surface brightness (HSB) galaxies, (B) galaxies with a range of $`W_{20}`$ values from 61 $`kms^1`$ to 607 $`kms^1`$, (C) LINER, Sy, HII and less active galaxies, (D) galaxies which have excellent and poor agreement between $`D_{tf}`$ and $`D_c`$, (E) a distance range from 2.02 Mpc to 49.7 Mpc, (F) field and cluster galaxies, and (G) galaxies with rising, flat, and declining rotation curves.

For each of the target galaxies, the $`D_{tf}`$ was calculated using the equations from Tully et al. (1998). The $`W_{20}`$ value was corrected for inclination, and used for $`W_R^i`$ in the TF equations. For target galaxies, $`D_{tf}`$ was calculated using total apparent corrected I band magnitude (“itc”) and equations except for the galaxies IC 4182, NGC 1326A, NGC 4496A, and NGC 4571. For these target galaxies, the “btc” and equations were used since “itc” data was unavailable in LEDA.

NGC 3031 and NGC 3319 are HSB galaxies with significant differences between $`D_{tf}`$ and $`D_c`$ measurements. NGC 1365 has a rapidly declining rotation curve with a decline of at least 63% of the peak value (Jörsäter & van Moorsel, 1995). NGC 2841 is a candidate to falsify the MOdified Newtonian Dynamics (MOND) model (Bottema et al., 2002). A distance greater than 19 Mpc, compared to the measured $`D_c`$ of 14.1 Mpc, or a high mass/luminosity ratio is needed for MOND. The $`D_{tf}`$ value of 25.5 Mpc given herein is compatible with MOND. NGC 3031 has significant non-circular motion in its HI gas (Rots & Shane, 1975). NGC 3198 is well suited for testing theories since the data for it has the largest radius and number of surface brightness scale lengths (van Albada et al., 1985). NGC 4321 has a very asymmetric HI rotation curve and is “lopsided”(Knapen et al., 1993) in the disk region of the galaxy.

The NED database was used to assemble a list of galaxies closest to each of the target galaxies. The selection of close galaxies used the Hubble Law with a Hubble constant $`H_o`$ of 70 $`kms^1Mpc^1`$ and galactic z to calculate the distances to galaxies. The angular coordinates were taken from the NED database. For each target galaxy, the distance from each target galaxy to each of the other galaxies was calculated. The neighbor galaxies with the smallest distance were chosen as the close galaxies.

The uncertainty of the value of $`H_o`$ is high. The use of $`H_o`$ herein is restricted to only the selection of the neighbor galaxies. As the relative distances become larger, the distance uncertainty increases if only because of a greater variation in peculiar velocity. Therefore, there is a practical upper limit on the number of galaxies that can be used to evaluate $`E_a`$. If too few close galaxies are used, $`E_a`$ will be underestimated. The number of close galaxies found to produce the highest correlation coefficient was 10.

For each close galaxy, the distance from the Milky Way to the galaxies $`D_{g(jk)}`$ (in $`Mpc`$) was calculated by,

$$D_{g(jk)}=\frac{z_{g(j)}}{z_{c_{(k)}}}D_{c(k)},$$
(8)
where $`z_{g(j)}`$ is the $`z`$ of the $`j^{th}`$ close galaxy, $`z_{c(k)}`$ is the $`z`$ of the $`k^{th}`$ target galaxy, and $`D_{c(k)}`$ is the $`D_c`$ of the $`k^{th}`$ target galaxy. A bold character denotes a vector and the same character without the bold denotes the magnitude of the vector. The sub $`()`$ indicated the letters enclosed are indices identifying the galaxies of the calculation. The vector direction of $`𝑫_{g(jk)}`$ was calculated from coordinates found in the NED database.

The distance $`R_{(jk)}`$ from the $`j^{th}`$ close galaxy to the $`k^{th}`$ target galaxy was calculated as,

$$R_{(jk)}=|𝑹_{(jk)}|=|𝑫_{c(k)}𝑫_{g(jk)}|.$$
(9)
Calculating $`D_{g(jk)}`$ by the method of equation (8) reduces the error of $`R_{(jk)}`$ compared to other methods.

The total absolute magnitude $`M_{(j)}`$ of the $`j^{th}`$ close galaxy was calculated,

$$M_{(j)}=m_b255\mathrm{log}(D_{g(jk)}).$$
(10)
The cross sectional area of the $`k^{th}`$ target galaxy $`A`$ presented to the $`j^{th}`$ close galaxy was calculated by,

$$A_{(jk)}=\pi R_{25}^2\mathrm{sin}I_{(jk)},$$
(11)
where $`I_{(jk)}`$ is the angle between the $`k^{th}`$ target galaxy’s plane and $`𝑹_{(jk)}`$ (see Figure 1) and is calculated from $`i`$ from the LEDA database (“incl”), the position angle “pa” from the LEDA database and the orientation sign as noted in Table 1 in the $`i`$ column. The dependence of $`A_{(jk)}`$ on a target galaxy’s orientation relative to a close galaxy may be significant. The sign indicates whether the galaxy’s polar axis is rotated clockwise or counterclockwise from our line of sight about the major axis when viewed from the easterly side of the major axis. Figure 2 is a diagram depicting a hypothetical example of our view and a close galaxy’s view of the same galaxy. Our view (a and c in Figure 2) is independent of whether the northwest side of the target galaxy is closer or farther than the southeast side. The close galaxy will have one of two possible views depending on the orientation of the target galaxy. In view b of Figure 2 the close galaxy is located in the plane of the target galaxy with a positive $`i`$ and $`A_{(jk)}`$ is minimal. With a negative $`i`$ sign, $`A_{(jk)}`$ as depicted in view d of Figure 2 has a significant value.

The $`E_a`$ was calculated as,

$$E_{a(k)}=\underset{j=1}{\overset{n}{}}10^{\frac{M_{(jk)}}{2.5}}\frac{A_{(jk)}}{4\pi R_{(jk)}^2},$$
(12)
where n is the number of galaxies included in the calculation. In this case, $`n=10`$. The unit of measure of $`E_a`$ is in flux units ($`ergcm^2s^1`$).

The procedure to determine the sign of $`i`$ is as follows. (A) The difference $`\mathrm{\Delta }E_a`$ between the value of $`E_a`$ with a positive $`i`$ and $`E_a`$ with negative $`i`$ was calculated for each target galaxy. (B) Nine target galaxies had a $`\mathrm{\Delta }E_a`$ of less than 5 in the second significant figure, 17 had a $`\mathrm{\Delta }E_a`$ of less than 1 in the first significant figure. The sign of $`i`$ was of minimal significance for these galaxies. (C) Since the relative position of these 17 galaxies on the $`C_f`$ versus $`E_a`$ plot changed little, these 17 target galaxies established the initial $`E_a`$ ranges and the initial constants of equation (6). (D) The sign of $`i`$ of the remaining target galaxies was determined such that their value of $`E_a`$ was within their error limits of one of the initial lines. (E) The sign of $`i`$ of the initial 17 galaxies was re-chosen such that the value was closest to the line. (F) The equations of the lines were recalculated.

The results are presented in Table 1.

A plot of $`C_f`$ versus $`E_a`$ is shown in Figures 3 and 4. The galaxies form into four distinct Conversion Efficiency Type (CET) relations, labeled CET 1, CET 2, CET 3, and CET 4. The characteristics of each CET is tabulated in Table 2. The statistical test of variance of the line and $`E_a`$ of the sample galaxies (F test ) for all CET regions is 0.99. The projections of the lines intersect at ($`E_a`$, $`C_f`$) = (550$`\pm `$50 $`ergcm^2s^1`$,-0.54$`\pm `$.07).

The error $`E_a(D_c)`$ in $`E_a`$ due solely to the error in $`D_c`$ is also listed in Table 1 for each target galaxy. Table 2 shows the range of $`E_a`$ and $`E_a(D_c)`$ for each CET. The choice of sign of $`i`$ could also have been done using the criteria that values of $`E_a`$ and $`E_a(D_c)`$ be within the ranges specified in Table 2.

The large error in NGC 4603 is a result of the unusually large published error in $`D_c`$. NGC 4535 was the only galaxy where the line was outside its error limits. NGC 4535 could fit nearly as well in CET 4 with a positive $`i`$ sign and an out of range $`E_a(D_c)`$. If the sign of $`i`$ of NGC 4535 is positive, NGC 4535 is closer to CET 4, the correlation coefficient of CET 3 increases to 0.94, and the $`E_a(D_c)`$ is in the CET 3 range. Therefore, if CET 4 is selected for NGC 4535, the $`E_a(D_c)`$ and the $`E_a`$ are in different ranges. Hence, NGC 4535 was considered to be in CET 3.

The analysis presented herein depends on the Cepheid distances being secure, standard distances. Freedman et al. (2001) adopted a metallicity PL correction factor of $`0.2\pm 0.2magdex^1`$. Ferrarese et al. (2000) assumed the PL relation was independent of metallicity. If the Cepheid distances used are from the earlier work of Ferrarese et al. (2000), which are higher than Freedman et al. (2001), the correlation coefficients are -0.74, 0.89, 0.85, and 0.98 for the CET 1, CET 2, CET 3, and CET 4 zones, respectively, and the slopes and intercepts of the new equations are within 3 $`\sigma `$ of the slopes and intercepts of the equations of Table 2. Thus, the theory and the result presented herein appear robust relative to systematic variation in the Cepheid distances.

The analysis also depends on the Hubble law. There is considerable uncertainty in the value of $`H_o`$. The attempt to minimize this uncertainty was to consider only galaxies near the target galaxy and to calculate the distances between galaxies using the ratio of $`z`$ values. This assumes that the $`H_o`$ varies little around each target galaxy. The effect of the error in $`H_o`$ is limited to a selection bias. Using $`H_o=80kms^1Mpc^1`$ produced no significant change in the results.

NGC 3621, NGC 3319, and NGC 4535 are outliers in CET 1, CET 2, and CET 3, respectively. These three galaxies have a more negative $`C_f`$ than their respective theoretical lines. The removal of these galaxies from consideration yields the modified correlation coefficient, modified $`K_s`$, and modified $`K_i`$ listed in Table 3.

## 4 DISCUSSION

Shanks et al. (2002) suggested the Cepheid distances may be underestimated due to metallicity and magnitude incompleteness. Also, the sign and value of a possible metallicity correction factor is uncertain (Freedman et al., 2001). As the difference between Ferrarese et al. (2000) and Freedman et al. (2001), the effect will be to change only the slope and intercept of the CET equations.

The existence of four $`E_a`$ zones is unexplained. It should be noted that for each zone $`K_s`$ and $`K_i`$ are constants distinct from other zones. We speculate that since $`K_s`$ has discrete values, equation (7) implies $`K_a`$, $`K_eϵ`$, or both must have discrete values, also. That is, the values are not continuously variable. If $`K_a`$ and $`K_eϵ`$ depend on internal characteristics of a galaxy such as chemical composition, then the gap between CET zones and a discrete value $`K_s`$ implies $`E_a`$ must influence at least two of $`K_a`$, $`K_e`$, or $`ϵ`$. We speculate that other galaxies influence parameters internal to a galaxy including chemical composition. Another unexplained characteristic is the ratio of the slopes. The ratio of the slopes is 4.24 between CET 3 and CET 2 and 3.65 between CET 4 and CET 3 (both approximately 4). Also unexplained is the convergence of the linear equations to ($`E_a`$, $`C_f`$) = (550$`\pm `$50 $`ergcm^2s^1`$,-0.54$`\pm `$.07).

Since the $`C_fE_a`$ relationship has excellent correlation coefficients without NGC 3621, NGC 3319, and NGC 4535, some of the assumptions made in developing the model may be invalid for these galaxies. NGC 3319 is rich in HI (Moore & Gottesman, 1998) and NGC 4535 is poor in HI (Giovanelli & Haynes, 1983). However, if a galaxy has different absorption due to HI, then the $`K_eϵ`$ should also change since HI is a fuel for emission, also. Another intriguing possibility is that there are three more CET zones. The additional zones would consist of (A) NGC 2090 and NGC 3031, (B) NGC 1326A and NGC 3319, and (C) NGC 1365 and NGC 4535. The functional relationship would be maintained. Another method to determine the orientation (sign) of each galaxy, more data, and reduced error are needed.

The choice of sign of the inclination angle is the most subjective part of the data. In some cases such as NGC 0300, the difference in $`E_a`$ causes a change of CET zone which leaves the $`C_f`$ nearly the same. As expected, a sign change has greater effect on the galaxies with one very close neighbor. If all galaxies have their inclination sign reversed, four CET categories are again formed with correlation coefficients of -0.72, 0.98, 0.91, and 0.93. However, several galaxies are outside their error limits of a line. The method is robust. The choice of sign reported herein allows this method to work. However, a better method in determining the sign would place greater confidence in the numbers.

NGC 2841 is close to the calculated line in CET 2 with a measured $`C_f=0.45`$ and a calculated $`C_f=0.41`$. Therefore, the model in this Paper accounts for nearly all the error in ($`D_cD_{tf}`$) and $`D_c`$ is much less than MOND requires. This suggests NGC 2841 is a problem for MOND.

When a galaxy’s fundamental plane parameter is compared to the galaxy’s luminosity, a broader scatter and outliers (see, for example, Gebhardt et al. (2000)) result than if a parameter other than luminosity is compared. This paper suggests this is due to the effect of neighboring galaxies.

Relative to the TF equations, the model must still discover the relationship of $`W_{20}`$ to the $`C_f`$. We speculate that after the adjustment for neighboring galaxies, this correction may explain the scale error found by Shanks et al. (2002) between raw Cepheid and TF distances. The TF assumption that the intrinsic mass to intrinsic luminosity ratio is constant among galaxies (Aaronson, Huchra, & Mould, 1979) is valid for $`z<0.006`$. The TF approach can be an even more powerful tool with $`C_f`$ considered.

## 5 CONCLUSION

$``$ The sample considered 31 spiral galaxies with published Cepheid distances. Predicted linear relationships between a factor expressing the relation between TF and Cepheid distance calculations and a factor expressing the amount of impinging energy from nearby galaxies were found.

$``$ The impinging energy relation was found to have four zones depending on the amount of impinging energy. Each zone had a different linear relationship to the distance correction factor.

$``$ The lines from the four zones projects to a common point at ($`E_a`$, $`C_f`$) = (550$`\pm `$50$`ergcm^2s^1`$,-0.54$`\pm `$.07).

$``$ When considering the luminosity of a galaxy, the effect of its neighbors should be considered.

$``$ The intrinsic mass to intrinsic luminosity ratio is constant among the sample galaxies.

$``$ The mass is constant for each of the target galaxies. Therefore, the intrinsic luminosity equals the rate of energy conversion of the mass being added to the galaxy.

This research has made use of the NASA/IPAC Extragalactic Database (NED), which is operated by the Jet Propulsion Laboratory, California Institute of Technology, under contract with the National Aeronautics and Space Administration. This research has made use of the LEDA database (http://leda.univ-lyon1.fr). We thank W. Osborne and K. Rumstay for comments and suggestions that improved the manuscript. We acknowledge and appreciate the financial support of Cameron Hodge, Stanley, New York, and Maynard Clark, Apollo Beach, Florida, while working on this project.


text:
# How NP Got a New Definition: A Survey of Probabilistically Checkable ProofsSupported by David and Lucile Packard Fellowship, NSF Grant CCR-0098180, and an NSF ITR Grant.

## 1. PCP theorems: an informal introduction

Suppose a mathematician circulates a proof of an important result, say Riemann Hypothesis, fitting several thousand pages. To verify it would take you and your doubting colleagues several years. Can you do it faster? Yes, according to the PCP Theorems. He can rewrite his proof so you can verify it by probabilistically selecting (i.e., using a source of random bits) a constant number of bits —as low as $`3`$ bits—to examine in it. Furthermore, this verification has the following properties: (a) A correct proof will never fail to convince you (that is, no choice of the random bits will make you reject a correct proof) and (b) An incorrect proof will convince you with only negligible probability ($`2^{100}`$ if you examine $`300`$ bits). In fact, a stronger assertion is true: if the Riemann hypothesis is false, then you are guaranteed to reject any string of letters placed before you with high probability after examining a constant number of bits. (c) This proof rewriting is completely mechanical—a computer could do it—and does not greatly increase its size. (Caveat: Before journal editors rush to adopt this new proof verification, we should mention that it currently requires proofs written in a formal axiomatic system —such as Zermelo Fraenkel set theory—since computers do not understand English.)

This result has a strong ring of implausibility. A mathematical proof is invalid if it has even a single error somewhere. How can this error spread itself all over the rewritten proof, so as to be apparent after we have probabilistically examined a few bits in the proof? (Note that the simple idea of just making multiple copies of the erroneous line everywhere does not work: the unknown mathematician could hand you a proof in which this does not happen, yet that does not make the proof correct.) The methods used to achieve this level of redundancy are reminiscent of the theory of error-correcting codes, though they are novel and interesting in their own right, and their full implications are still being felt (see Section 3.).

### 1.1. New definition of NP

The PCP Theorems provide interesting new definitions for the complexity class NP. (Clarification: the singular form “PCP Theorem” will refer to a single result $`\text{NP}=\text{PCP}(\mathrm{log}n,1)`$ proved in , and the plural form “PCP Theorems” refers to a large body of results of a similar ilk, some predating the PCP Theorem.) Classically, NP is defined as the set of decision problems for which a “Yes” answer has a short certificate verifiable in polynomial time (i.e., if the instance size is $`n`$, then the certificate size and the verification time is $`n^c`$ for some fixed constant $`c`$). The following are two examples:

3-SAT $`=`$ satisfiable boolean formulae of the form AND of clauses of size at most $`3`$, e.g., $`(x_1\neg x_2x_3)(\neg x_1x_2x_3)(x_4)`$. (The certificate for satisfiability is simply an assignment to the variables that makes the formula true.)

$`\text{MATH-THEOREM}_{ZFC}`$ $`=`$ set of strings of the form $`(T,1^n)`$ where $`T`$ is a mathematical statement that is a theorem in Zermelo Fraenkel set theory that has a proof $`n`$ bits long. (The “certificate” for theoremhood is just the proof.)

The famous conjecture $`\text{P}\text{NP}`$ —now one of seven Millenium Prize problems in math —says that not every NP problem is solvable in polynomial time. In other words, though the certificate is easy to check, it is not always easy to find.

The PCP Theorem gives a new definition of NP: it is the set of decision problems for which a “Yes” answer has a polynomial-size certificate which can be probabilistically checked using $`O(\mathrm{log}n)`$ random bits and by examing $`O(1)`$ (i.e., constant) number of bits in it.

Our earlier claim about proof verification follows from the PCP Theorem, since $`\text{MATH-THEOREM}_{ZFC}`$ is in NP, and hence there is a way to certify a YES answer (namely, theoremhood) that satisfies properties (a) and (b). (Property (c) follows from the constructive nature of the proof of the PCP Theorem in .)

Motivated by the PCP Theorems, researchers have proved new analogous definitions of other complexity classes such as PSPACE  and PH .

### 1.2. Optimization, approximation, and PCP theorems

The P versus NP question is important because of NP-completeness (also, NP-hardness). Optimization problems in a variety of disciplines are NP-hard , and so if $`\text{P}\text{NP}`$ they cannot be solved in polynomial time. The following is one such optimization problem.

MAX-3SAT: Given a 3-CNF boolean formula $`\phi `$, find an assignment to the variables that maximizes the number of satisfied clauses.

Approximation algorithms represent a way to deal with NP-hardness. An algorithm achieves an approximation ratio $`\alpha `$ for a maximization problem if, for every instance, it produces a solution of value at least $`OPT/\alpha `$, where $`OPT`$ is the value of the optimal solution. (For a minimization problem, achieving a ratio $`\alpha `$ involves finding a solution of cost at most $`\alpha OPT`$.) Note that the approximation ratio is $`1`$ by definition. For MAX-3SAT we now know a polynomial-time algorithm that achieves an approximation ratio $`8/7`$ .

Though approximation algorithms is a well-developed research area (see ), for many problems no good approximation algorithms have been found. The PCP Theorems suggest a reason: for many NP-hard problems, including MAX-CLIQUE, CHROMATIC NUMBER, MAX-3SAT, and SET-COVER, achieving certain reasonable approximation ratios is no easier than computing optimal solutions. In other words, approximation is NP-hard. For instance, achieving a ratio $`8/7ϵ`$ for MAX-3SAT is NP-hard .

Why do the PCP Theorems lead to such results? Details appear in the survey  (and \[Feige 2002\], these proceedings), but we hint at the reason using 3SAT and MAX-3SAT as examples. Cook and Levin  showed how to reduce any NP problem to 3SAT, by constructing, for any nondeterministic machine, a 3CNF formula whose satisfying assignments represent the transcripts of accepting computations. Thus it is difficult to satisfy all clauses. Yet it is easy to find assignmenent satisfying $`1o(1)`$ fraction of the clauses! The reason is that a computation transcript is a very non-robust object: changing even a bit affects its correctness. Thus the Cook-Levin reduction does not prove the inapproximability of MAX-3SAT. By providing a more robust representation of a computation, the PCP Theorems overcome this difficulty. We note that MAX-3SAT is a central problem in the study of inapproximability: once we have proved its inapproximability, other inapproximability results easily follow (see ; the observation in a weaker form is originally from work on MAX-SNP ).

### 1.3. History and context

PCPs evolved from interactive proofs, which were invented by Goldwasser, Micali, and Rackoff  and Babai  as a probabilistic extension of NP and proved useful in cryptography and complexity theory (see Goldreich’s survey ), including some early versions of PCPs . In 1990, Lund, Fortnow, Karloff and Nisan  and Shamir  showed IP=PSPACE, thus giving a new probabilistic definition of PSPACE in terms of interactive proofs. They introduced a revolutionary algebraic way of looking at boolean formulae. In restrospect, this algebraization can also be seen as a “robust” representation of computation. The inspiration to use polynomials came from works on program checking  (see also ). Babai, Fortnow, and Lund  used similar methods to give a new probabilistic definition of NEXPTIME, the exponential analogue of NP. To extend this result to NP, Babai, Fortnow, Levin, and Szegedy  and Feige, Goldwasser, Lovász, Safra, and Szegedy  studied variants of what we now call probabilistically checkable proof systems (Babai et al. called their systems holographic proofs).

Feige et al. also proved the first inapproximability result in the PCP area: if any polynomial-time algorithm can achieve a constant approximation ratio for the MAX-CLIQUE problem, then every NP problem is solvable in $`n^{O(\mathrm{log}\mathrm{log}n)}`$ time. This important result drew everybody’s attention to the (as yet unnamed) area of probabilistically checkable proofs. A year later, Arora and Safra  formalized and named the class PCP and used it to give a new probabilistic definition of NP. (Babai et al. and Feige et al.’s results were precursors of this new definition.) They also showed that approximating MAX-CLIQUE is NP-hard. Soon, Arora, Lund, Motwani, Sudan, and Szegedy  proved the PCP Theorem (see below) and showed that MAX-SNP-hard problems do not have a PTAS if $`\text{P}\text{NP}`$. Since the second paper relied heavily on the still-unpublished first paper, the the PCP theorem is jointly attributed to . For surveys of these developments see .

## 2. Definitions and results

Now we define the class PCP. We will use “language membership” and “decision problem” interchangeably. A $`(r(n),q(n))`$-restricted verifier for a language $`L`$, where $`r,q`$ are integer-valued functions, is a probabilistic turing machine $`M`$ that, given an input of size $`n`$, checks membership certificates for the input in the following way. The certificate is an array of bits to which the verifier has random-access (that is, it can query individual bits of the certificate).

* The verifier reads the input, and uses $`O(r(n))`$ random bits to compute a sequence of $`O(q(n))`$ addresses in the certificate.
* The verifier queries the bits at those addresses, and depending upon what they were, outputs “accept” or “reject”.
* $$xL\text{ certificate }\mathrm{\Pi }\text{ s.t. }\mathrm{Pr}[M^\mathrm{\Pi }\text{accepts}]=1,$$
(2.1)
$$xL\text{ certificate }\mathrm{\Pi }\text{}\mathrm{Pr}[M^\mathrm{\Pi }\text{accepts}]1/2$$
(2.2)
(In both cases the probability is over the choice of the verifier’s random string.)

$`\text{PCP}(r(n),q(n))`$ is the complexity class consisting of every language with an $`(r(n),q(n))`$-restricted verifier. Since NP is the class of languages whose membership certificates can be checked by a deterministic polynomial-time verifier, $`\text{NP}=_{c0}\text{PCP}(0,n^c)`$. The PCP Theorem gives an alternative definition: $`\text{NP}=\text{PCP}(\mathrm{log}n,1)`$. Other PCP-like classes have been defined by using variants of the definition above, and shown to equal NP (when the parameters are appropriately chosen). We mention some variants and the best results known for them; these are the “PCP Theorems” alluded to earlier.

1. The probability $`1`$ in condition (2.1) may be allowed to be $`c<1`$. Such a verifier is said to have imperfect completeness $`c`$.
2. The probability $`1/2`$ in condition (2.2) may be allowed to be $`s<c`$. Such a verifier is said to have soundness $`s`$. Using standard results on random walks on expanders, it can be shown from the PCP theorem that every NP language has verifiers with perfect completeness that use $`O(k)`$ query bits for soundness $`2^k`$ (here $`kO(\mathrm{log}n)`$).
3. The number of query bits, which was $`O(q(n))`$ above, may be specified more precisely together with the leading constant. The constant is important for many inapproximability results. Building upon past results on PCPs and using fourier analysis, Håstad  recently proved that for each $`ϵ>0`$, every NP language has a verifier with completeness $`1ϵ`$, soundness $`1/2`$ and only $`3`$ query bits. He uses this to show the inapproximability of MAX-3SAT upto a factor $`8/7ϵ`$.
4. The free bit parameter may be used instead of query bits . This parameter is defined as follows. Suppose the query bit parameter is $`q`$. After the verifier has picked its random string, and picked a sequence of $`q`$ addresses, there are $`2^q`$ possible sequences of bits that could be contained in those addresses. If the verifier accepts for only $`t`$ of those sequences, then we say that the free bit parameter is $`\mathrm{log}t`$ (note that this number need not be an integer). Samorodnitsky and Trevisan show how to reduce the soundness to $`2^{k^2/4}`$ using $`k`$ free bits .
5. Amortized free bits may be used . This parameter is $`lim_{s0}f_s/\mathrm{log}(1/s)`$, where $`f_s`$ is the number of free bits needed by the verifier to make soundness $`<s`$. Håstad  shows that for each $`ϵ>0`$, every NP language has a verifier that uses $`O(\mathrm{log}n)`$ random bits and $`ϵ`$ amortized free bits. He uses this to show (using a reduction from  and modified by ) that MAX-CLIQUE is inapproximable upto a factor $`n^{1\delta }`$.
6. The certificate may contain not bits but letters from a larger alphabet $`\mathrm{\Sigma }`$. The verifier’s soundness may then depend upon $`\mathrm{\Sigma }`$. In a $`p`$ prover 1-round interactive proof system, the certificate consists of $`p`$ arrays of letters from $`\mathrm{\Sigma }`$. The verifier is only allowed to query $`1`$ letter from each array. Since each letter of $`\mathrm{\Sigma }`$ is represented by $`\mathrm{log}\left|\mathrm{\Sigma }\right|`$ bits, the number of bits queried may be viewed as $`p\mathrm{log}\left|\mathrm{\Sigma }\right|`$. Constructions of such proof systems for NP appeared in . Lund and Yannakakis  used these proof systems to prove inapproximability results for SETCOVER and many subgraph maximization problems. The best construction of such proof systems is due to Raz and Safra . They show that for each $`k\sqrt{\mathrm{log}n}`$, every NP language has a verifier that uses $`O(\mathrm{log}n)`$ random bits, has $`\mathrm{log}\left|\mathrm{\Sigma }\right|=O(k)`$ and soundness $`2^k`$. The parameter $`p`$ is $`O(1)`$.

## 3. Proof of the PCP theorems

A striking feature of the PCP Theorems is that each builds upon the previous ones. However, a few ideas recur. First, note that it suffices to design verifiers for 3SAT since 3SAT is NP-complete and a verifier for any other language can transform the input to a 3SAT instance as a first step. The verifier then expects a certificate for a “yes” answer to be an encoding of a satisfying assignment; we define this next.

For an alphabet $`\mathrm{\Sigma }`$ let $`\mathrm{\Sigma }^m`$ denote the set of $`m`$-letter words. The distance between two words $`x,y\mathrm{\Sigma }^m`$, denoted $`\delta (x,y)`$, is the fraction of indices they differ on. For a set $`𝒞\mathrm{\Sigma }^m`$, let the minimum distance of $`𝒞`$, denoted $`\text{min-dist}(𝒞)`$, refer to $`\mathrm{min}_{x,y𝒞;xy}\left\{\delta (x,y)\right\}`$ and let $`\delta (x,𝒞)`$ stand for $`\mathrm{min}_{y𝒞}\left\{\delta (x,y)\right\}`$. If $`\text{min-dist}(𝒞)=\gamma `$, and $`\delta (x,𝒞)<\gamma /2`$, then triangle inequality implies there is a unique $`y𝒞`$ such that $`\delta (x,y)=\delta (x,𝒞)`$. We will be interested in $`𝒞`$ such that $`\text{min-dist}(𝒞)0.5`$; such sets are examples of error-correcting codes from information theory, where $`𝒞`$ is thought of as a map from strings of $`\mathrm{log}\left|𝒞\right|`$ bits (“messages”) to $`𝒞`$. When encoded this way, messages can be recovered even if transmitted over a noisy channel that corrupts up to $`1/4`$th of the letters.

The probabilistically checkable certificate is required to contain the encoding of a satisfying assignment using some such $`𝒞`$. When presented with such a string, the verifier needs to check, first, that the string is close to some codeword, and second, that the (unique) closest codeword is the encoding of a satisfying assignment. As one would expect, the set $`𝒞`$ is defined using mathematically interesting objects (polynomials, monotone functions, etc.) so the final technique may be seen as a “lifting” of the satisfiability question to some mathematical domain (such as algebra). The important new angle is “local checkability,” namely, the ability to verify global properties by a few random spot-checks. (See below.)

Another important technique introduced in  and used in all subsequent papers is verifier composition, which composes two verifiers to give a new verifier some of whose parameters are lower than those in either verifier. Verifier composition relies on the notion of a probabilistically checkable split-encoding, a notion to which Arora and Safra were led by results in . (Later PCP Theorems use other probabilistically checkable encodings: linear function codes , and long codes .) One final but crucial ingredient in recent PCP Theorems is Raz’s parallel repetition theorem .

### 3.1. Local tests for global properties

The key idea in the PCP Theorems is to design probabilistic local checks that verify global properties of a provided certificate. Designing such local tests involves proving a statement of the following type: if a certain object satisfies some local property “often” (say, in $`90\%`$ of the local neighborhoods) then it satisfies a global property. Such statements are reminiscent of theorems in more classical areas of math, e.g., those establishing properties of solutions to PDEs, but the analogy is not exact because we only require the local property to hold in most neighborhoods, and not all.

We illustrate with some examples. (A research area called Property Testing  now consists of inventing such local tests for different properties.) There is a set $`𝒞\mathrm{\Sigma }^m`$ of interest, with $`\text{min-dist}(𝒞)0.5`$. Presented with $`x\mathrm{\Sigma }^m`$, we wish to read “a few” letters in it to determine whether $`\delta (x,𝒞)`$ is small.

1. Linearity test. Here $`\mathrm{\Sigma }=GF(2)`$ and $`m=2^n`$ for some integer $`n`$. Thus $`\mathrm{\Sigma }^m`$ is the set of all functions from $`GF(2)^n`$ to $`GF(2)`$. Let $`𝒞_1`$ be the set of words that correspond to linear functions, namely, the set of $`f:GF(2)^nGF(2)`$ such that $`a_1,\mathrm{},a_nGF(2)\text{s.t.}f(z_1,z_2,\mathrm{},,z_n)=_ia_iz_i.`$ The test for linearity involves picking $`\overline{z},\overline{u}GF(2)^n`$ randomly and accepting iff $`f(\overline{z})+f(\overline{u})=f(\overline{z}+\overline{u})`$. Let $`\gamma `$ be the probability that this test does not accept. Using elementary fourier analysis one can show $`\gamma \delta (f,𝒞_1)/2`$  (see also earlier weaker results in ).
2. Low Degree Test. Here $`\mathrm{\Sigma }=GF(p)`$ for a prime $`p`$ and $`m=p^n`$ for some $`n`$. Thus $`\mathrm{\Sigma }^m`$ is the set of all functions from $`GF(p)^n`$ to $`GF(p)`$. Let $`𝒞_2`$ be the set of words that correspond to polynomials of total degree $`d`$, namely, the set of $`f:GF(p)^nGF(p)`$ such that there is a $`n`$-variate polynomial $`g`$ of degree $`d`$ and $`f(z_1,z_2,\mathrm{},,z_n)=g(z_1,z_2,\mathrm{},,z_n).`$ We assume $`dnp`$ (hence degree is “low”). Testing for closeness to $`𝒞_2`$ involves picking random lines. A line has the parametric form $`\{(a_1+b_1t,a_2+b_2t,\mathrm{},a_n+b_nt):tGF(p)\}`$ for some $`a_1,a_2,\mathrm{},a_n`$, $`b_1,b_2,\mathrm{},b_nGF(p)`$. (It is a $`1`$-dimensional affine subspace, hence much smaller than $`GF(p)^n`$.) Note that if $`f`$ is described by a degree $`d`$ polynomial, then its restriction to such a line is described by a univariate degree $`d`$ polynomial in the line parameter $`t`$.

* Variant 1: Pick a random line, read its first $`d+1`$ points to construct a degree $`d`$ univariate polynomial, and check if it describes $`f`$ at a randomly chosen point of the line. This test appears in  and is similar to another test in .
    * Variant 2: This test uses the fact that in the PCP setting, it is reasonable to ask that the provided certificate should contain additional useful information to facilitate the test. We require, together with $`f`$, a separate table containing a degree $`d`$ univariate polynomial for the line. We do the test above, except after picking the random line we read the relevant univariate polynomial from the provided table. This has the crucial benefit that we do not have to read $`d+1`$ separate “pieces” of information from the two tables. If $`\gamma `$ is the probability that the test rejects, then $`\gamma \mathrm{min}\{0.1,\delta (f,𝒞_2)/2\}`$ (see ; which uses ).
3. Closeness to a small set of codewords. Above, we wanted to check that $`\delta (f,𝒞)<0.1`$, in which case there is a unique word from $`𝒞`$ in $`\text{Ball}(f,0.1)`$. Proofs of recent PCP Theorems relax this and only require for some $`ϵ`$ that there is a small set of words $`S𝒞`$ such that each $`sS`$ lies in $`\text{Ball}(f,ϵ)`$. (In information theory, such an $`S`$ is called a list decoding of $`f`$.) We mention two important such tests.

For degree $`d`$ polynomials: The test in Variant 2 works with a stronger guarantee: if $`\beta `$ is the probability that the test accepts, then there are $`\text{poly}(1/ϵ)`$ polynomials whose distance to $`f`$ is less than $`1ϵ`$ provided $`p>\text{poly}(nd/\beta ϵ)`$ (see , and also  for an alternative test).

Long Code test. Here $`\mathrm{\Sigma }=GF(2)`$ and $`m=2^n`$ for some integer $`n`$. Thus $`\mathrm{\Sigma }^m`$ is the set of all functions from $`GF(2)^n`$ to $`GF(2)`$. Let $`𝒞_3`$ be the set of words that correspond to coordinate functions, namely,

$$\{f:GF(2)^nGF(2):i\{1,2,\mathrm{},n\}\text{s.t.}f(z_1,z_2,\mathrm{},z_n)=z_i.\}$$

(This encodes $`i[1,n]`$, i.e., $`\mathrm{log}n`$ bits of information, using a string of length $`2^n`$, hence the name “Long Code”.) The following test works , though we do not elaborate on the exact statement, which is technical: Pick $`\overline{z},\overline{w}GF(2)^n`$ and $`\overline{u}GF(2)^n`$ that is a random vector with $`1`$’s in $`ϵ`$ fraction of the entries. Accept iff $`f(\overline{z}+\overline{w})=f(\overline{z})+f(\overline{w}+\overline{u})`$. (Note the similarity to the linearity test above.)

### 3.2. Further applications of PCP techniques

We list some notable applications of PCP techniques. The PCP Theorem is useful in cryptography because many cryptographic primitives involve basic steps that prove Yes/No assertions that are in NP(or even P). The PCP Theorem allows this to be done in a communication-efficient manner. See  for some examples. Some stronger forms of the PCP Theorem (specifically, a version involving encoded inputs) have found uses in giving new definitions for polynomial hierarchy  and PSPACE . Finally, the properties of polynomials and polynomial-based encodings discovered for use in PCP Theorems have influenced new decoding algorithms for error-correcting codes , constructions of pseudorandom graphs called extractors  and derandomization techniques in complexity theory (e.g. ).