text:
# The presence and distribution of HI absorbing gas in sub-galactic sized radio sources

## 1 Introduction

Gigahertz Peaked Spectrum (GPS) and Compact Steep Spectrum (CSS) radio sources have their radio emission confined to a very small region ($`<`$ 10 kpc). Their radio spectra and radio morphology indicate this class of sources are intrinsically small in contrast to the relativistically beamed core-jet sources.

In these two classes of sources the turn-over frequency is anti-correlated with the source size. This has led to the argument that that the turnover could be due to synchrotron self-absorption (Fanti et al. fanti90 (1990); O’Dea & Baum odea97 (1997), Snellen et al. snellen00 (2000)). A turn-over in the 100 MHz regime is characteristic of the CSSs with sizes 1 – 10 kpc, while if the peak flux density instead is seen close to 1 GHz, the sources are smaller ($`<`$ 1 kpc) and are classified as GPSs. The most likely explanation for the small sizes of these objects is that they are young sources which will eventually evolve into larger scale classical doubles like Cygnus A (e.g. Fanti et al. fanti95 (1995); Readhead et al. readhead96 (1996); Owsianik & Conway owsianik98a (1998)). They therefore provide interesting laboratories for studying AGN evolution, and present data is consistent with the idea that the sources expand with constant velocities while their radio power declines as $`LS^{0.5}`$, where $`LS`$ is the linear size (e.g. Fanti et al. fanti95 (1995)). The drop of the radio power as the source grows in size could indicate that the GPS sources may evolve into the lowest luminosity FRII radio galaxies or perhaps into the FRIs (O’Dea & Baum odea97 (1997)).

The probable youth of GPS/CSSs implies the possibility of studying the birth of radio sources; little is known of the mechanisms triggering the radio activity. Mergers could provide a way to transport gas to the centre of the host galaxies and thus be involved in the onset of the nuclear engine. Indeed, optical observations have shown that many of the GPS/CSS sources are in disturbed or interacting systems (de Vries et al. devries00 (2000); O’Dea et al. odea96 (1996)), in which we may expect dense nuclear environments.

A number of studies of gas in GPS/CSS sources have already been made at different wavebands. For instance, optical studies show strong highly excited line emission with large equivalent widths (Gelderman & Whittle gelderman94 (1994)), consistent with interactions between the radio source and the interstellar medium. Radio polarisation observations have shown that some GPS/CSS sources display large rotation measures exceeding $`>`$ 1000 rad m-2 which in turn imply large foreground electron densities and magnetic fields (Kato et al. kato87 (1987); Stanghellini et al. stanghellini98 (1998)). However, the majority of small GPS sources are weakly polarised, making it hard to estimate rotation measures (e.g. Stanghellini et al. stanghellini98 (1998)). The low polarisation suggests strong depolarisation, again consistent with a very large central density. X-ray absorption observations of a few GPS quasars indicate an absorbing column of a few $`10^{22}`$ cm-2 associated with the quasars (Elvis et al. elvis94 (1994)). However, there exist no extensive study of this phenomenon in the GPS/CSS class as a whole. Other evidence for a dense environment comes from free-free absorption observations, for example in OQ208 (Kameno et al. kameno00 (2000)). Marr et al. (marr01 (2001)) found evidence for free-free absorption in the GPS source 0108+388, consistent with a 100 pc radius disk with an electron density of 500 cm-3. In 1946+708 multi-frequency continuum studies also show indications of free-free absorption concentrated towards the core and inner parts of the counter-jet, again suggesting a disk or torus origin (Peck et al. peck99 (1999)). Disk-like distributions of gas have also been found in the optical, and the best example so far is the HST dust disk observed in the GPS source 4C 31.04 (Perlman et al. perlman01 (2001)). Due to the sparse number of observations, a typical molecular gas mass of GPS/CSSs is not yet known, but CO observations of 4C 12.50 have shown a large total gas mass around $`10^{10}`$ M (Evans et al. evans99 (1999); Mirabel et al. mirabel89b (1989)). However this source is unusual in many other of its properties and might not be representative of the GPS/CSS class as a whole.

Another way to study the gas content in these sources is by spectral absorption experiments. Such absorption observations have the advantage over emission that the sensitivity is independent of the distance, depending only on the background flux density. In absorption experiments detection depends on having a significant column density, rather than a large gas mass, so this method is sensitive to dense gas on small scales in AGN. Using the 21 cm line of atomic hydrogen in absorption it is possible to study the neutral gas content of GPS/CSS sources. The Hi is likely to be only a fraction of the total gas present, however such observations provide lower limits to the total gas mass and density. The strength of GPS/CSS sources at cm wavelengths makes them good targets for such experiments. In addition their small sizes indicate that lines of sight to these sources will sample the dense gas confined within the centre of the host galaxy. Similarly the line of sight to a GPS source will trace gas within the narrow-line region (NLR).

Here we discuss the results of Hi absorption studies in such sources, compiled from our own observations presented in Vermeulen et al. (vermeulen03 (2003)), and from the literature.

## 2 The sample and its properties

We are interested in studying the Hi gas content of the AGN host galaxy; both the general interstellar matter (ISM) in addition to circumnuclear gas disks if present. In Table 1 we have compiled a list of sources searched for Hi absorption which belong to the GPS/CSS class and are therefore likely compact with total intrinsic sizes $`<`$ 10 kpc.

In order to achieve a sample of small sources searched for Hi absorption which is as complete and unbiased as possible, we have selected sources from the following major GPS/CSS lists: Spencer et al. (spencer89 (1989)), the Fanti CSS sample (Fanti et al. fanti90 (1990)), O’Dea & Baum (odea97 (1997)), the CSS classified objects from Morganti et al. (morganti97 (1997)), de Vries et al. (1997a ) and the COINS sample (Peck et al. peck00 (2000)). The selection criteria were:
1) The redshift must be $`0.05<z<0.75`$. This ensures a high possibility of the objects having been searched for Hi absorption, given the frequency coverage of the WSRT (which has a UHF system covering the Hi 21 cm line up to $`z=0.75`$). 2) The declination should be larger than $`30^{}`$; the majority of GPS/CSSs are found at redshift between 0.1 and 1, restricting observations to the frequency flexible Northern hemisphere telescope WSRT. 3) The sources should have intrinsic linear sizes $`<10`$ kpc, in order to represent a true GPS/CSS object. We have therefore excluded a few objects (J1110+4817 and J1148+5924) which are known to have a clear one-sided core-jet structure and are therefore likely foreshortened by projection (Peck et al. peck00 (2000)). After the initial publication from which we selected the sources, 4 objects (J0432+4138, J0702+3757, J1227+3635 and J1520+2016) were found to actually have redshifts $`>`$1.0 and thus have been excluded from our analysis.

This gives a sample of 49 genuine GPS/CSS objects, which are listed in Table 1. We find that usable Hi absorption data have been taken for 41 of these, most of which can be found in Vermeulen et al. (vermeulen03 (2003)).

Table 1 lists some properties of the sources included in our analysis: the source J2000 and B1950 name, a possible other name, redshift and the Hi column density with the corresponding reference. All column densities assume a spin temperature of 100 K and a covering factor of unity. Quoted upper limits are given as a 3$`\sigma `$ limit, assuming a line width of 100 km s-1. For the sources where the absorption line is best fitted by multiple Gaussians, the number given is the total integrated column density. The FWHM and peak opacity are listed for the component with the largest column density if multiple lines are present. The projected linear size was (if possible given the source radio morphology) derived from measuring the size between the two hotspots in VLBI continuum images. For J0556-0241 we have only an upper limits of the size, however it is still included in the following analysis. $`S_{\mathrm{cont}}`$ is the observed flux density at the redshifted Hi frequency. A Friedmann cosmology with $`H_0=`$ 75 km s-1 and $`q_0=`$0.5 is used throughout this paper; all numbers taken from the literature are, if necessary, recalculated to this cosmological model.

## 3 Results

### 3.1 Detection rate

Including all 41 targets with usable Hi data listed in Table 1, the Hi absorption detection rate is 54%. We show in Table 2 that 59% of the galaxies have an Hi detection, as opposed to only 42% of the quasars. The latter number is however more uncertain since there are fewer quasars (29%) in our sample than galaxies (71%). Interestingly, we find an even stronger dichotomy when we separate out the GPS from the CSS sources by using a linear size division at 1 kpc. Table 3 shows that the smaller GPS sources have a detection rate of 63% as compared to 36% in the larger CSS sources; again the latter number is more uncertain due to the smaller number of objects. Below, we will discuss at length how this difference could reflect the fact that the more compact sources have a larger part of their continuum emission covered by nuclear gas. This effect has already been suspected on account of the high detection rate of Hi absorption in nearby GPS/CSS objects (Conway conway96 (1996)). First, rather than simply looking at the detection rate in two bins, we show that there may be a more continuous relationship between Hi column density and linear size.

### 3.2 Relation between $`N_{\mathrm{HI}}`$ and linear size

There appears to be an anti-correlation between the source linear size and the largest component of the Hi column density as plotted in Fig. 1 (for the objects with multiple lines we plot the component with the largest column density). A visual inspection suggests that the column densities for sources $`<`$ 0.5 kpc are larger than for those $`>`$ 0.5kpc. The data set contains upper limits both in Hi column density, as well as a few points which have upper limits on their size. We therefore investigated the possible correlation in Fig. 1 using survival analysis, taking into account also the upper limits. We used the software package ASURV Rev 1.2 (Lavalley et al. lavalley92 (1992)), which implements the methods for bivariate problems presented by Isobe et al. (isobe86 (1986)). A Kendall’s Tau test shows that there exists a correlation between the column density and the linear size with a probability $`>`$ 99%.

In order to parameterise the correlation we fit the simplest model of a power law to the data. The cluster of sources with column densities about $`10^{21}`$ cm-2 suggests that other models are possible, perhaps a two component model or a model with different power laws for small and large sources. However, given the uncertainties of the present dataset we cannot differentiate between these models. Linear regression applied with ASURV finds the relationship $`N_{\mathrm{HI}}=7.2\times `$$`10^{19}`$$`LS^{0.43}`$cm-2; where $`LS`$ is the linear size in kpc. This linear fit is plotted with a dotted line in Fig. 1. The solid line represents a least square linear fit taking into account the detections only (parameterised by $`N_{\mathrm{HI}}=1.95\times `$$`10^{20}`$$`LS^{0.45}`$cm-2).

While the majority of the upper limits do not show any dependence with linear size, there are two of the most compact sources which have higher upper limits. This raises the question whether the observed anti-correlation between $`N_{\mathrm{HI}}`$ and $`LS`$ could be an observational effect. Since the sensitivity of the Hi column density depends on the strength of the background continuum, we plot in Fig. 2 the distribution of background continuum strength as a function of linear size. Fig. 2 shows that we are more sensitive to small amounts of Hi absorption for the larger sources. Clearly, there are no reasons why we should not have been able to detect sources in the top right corner of Fig. 1 if they existed, and so we are confident that the top right hand corner on Fig. 1 is really empty. It is however possible that there are additional absorbers amongst the compact sources, with column densities similar to the larger sources ($``$ $`10^{20}`$$`10^{21}`$ cm-2). This would reduce the amplitude of the correlation (however the upper limit data and its possible dependence on size has already been taken account of by ASURV when making its confidence estimate).

An interesting question is whether the population of small sources have larger column densities because the FWHM of the absorption line is wider, or because the line is deeper. Fig. 3 shows the FWHM versus the projected linear size. There is no evidence that there is any correlation between the two (tested by a Kendall’s Tau correlation test). Fig. 4 shows the peak optical depth versus linear size. A Kendall’s Tau test shows that those two variables are correlated with a probability $`>`$ 99%. The solid line represents a least square linear fit to the data points. The slope is $``$0.36, which implies that the slope in Fig. 1 mainly depends on a difference in the observed opacity and is not due to differences in the line width.

### 3.3 A temporal change in the gas mass or a geometric effect?

There are at least two plausible explanations for the observed anti-correlation between source linear size and Hi column density. The first possibility is that we are tracing a temporal change in the total gas mass, and hence in the column density. In the evolutionary models of GPS/CSSs the smallest sources are the youngest, so we may postulate that the younger sources have used less fuel during their lifetime, as compared to the older and larger sources. To see if this is plausible, it is interesting to consider the total gas mass and the rate of use for larger radio sources (e.g. FRIs and FRIIs). The radio loud sources are usually associated with elliptical hosts (e.g. Martel et al. martel99 (1999); Bahcall et al. bahcall97 (1997), Dunlop et al. dunlop03 (2003)), which perhaps is surprising since it might be expected that more luminous sources would reside in more gas rich systems. However, the amount of gas needed to sustain an AGN during its lifetime is not necessarily large. Consider for instance a typical FRI radio galaxy with a bolometric luminosity of the order of $`10^{45}`$ erg s-1. Given that these large sources have expected lifetimes of $``$ $`10^7`$ – $`10^8`$ yrs (Parma et al. parma99 (1999)), and assuming an energy conversion efficiency of 10%, we would expect a fuel usage of less than $`10^7`$ M. Roughly 15% of the nearby normal ellipticals searched for Hi emission display Hi masses $`>`$ $`10^8`$ M (Huchtmeier huchtmeier94 (1994)). Amounts smaller than $`10^7`$ – $`10^8`$ M are below present detection limits, and are thus hard to detect in emission. Specifically in ellipticals which harbour powerful AGN molecular gas masses of around $`10^8`$ – $`10^9`$ M have been found in perhaps 40% of the sources searched during CO emission observations (Leon et al. leon01 (2001)), with detection limits of the order of $`10^8`$ M (Lim et al. lim00 (2000)). We therefore would expect total gas masses of GPS/CSSs to be similar to that of classical FRI/FRII sources, given the above mentioned expected fuel usage of $``$ $`10^7`$ M and that the typical total gas mass of FRI/FRIIs is $``$ $`10^8`$ M. Hence, we reject the possibility of the anti-correlation being due to a temporal change in the total gas mass, since there is no evidence that the radio source would use up a significant fraction of its total gas mass during its first $`10^4`$ years.

Instead we prefer a second explanation, in which the observed anti-correlation is a geometric effect of probing densities which decrease with radial distance from the centre. Here we assume that the sources (which all are $`<10`$ kpc) are fully embedded within the host galaxy, and that the absorbing medium has basically the same distribution in all sources (either a spherical or a disk distribution; for a cartoon see Fig. 5 and Fig. 6). If the radio source is centrally located in such a gas distribution, the lobes of the smaller sources must be embedded in (or in the case of a disk, behind) denser gas. Since most of those objects are lobe-dominated we thus expect to probe larger foreground column densities in the most compact sources. Constraining this density profile is useful for constraining both the feeding mechanism and evolution model of GPS/CSSs, and with this radial density model in mind we will in the following section investigate the Hi absorption characteristics.

## 4 Distribution of the absorbing gas

For some time it has been suspected that GPS/CSS sources have a high Hi absorption detection rate (Conway conway96 (1996)). This seems to be confirmed in our analysis of the available data (see Section 3). Most of those detections are so far done using instruments of modest resolution, which means we cannot easily determine where the Hi absorbing gas is located with respect to the continuum. In the following discussion we will first consider the case of the absorbing gas in our sample being in a spherical distribution, then we discuss the possibility of the Hi absorption instead arising in a disk.

### 4.1 Spherical distribution

The strong radio emission in the GPS/CSS sources is most often concentrated in two lobes, while the core emission (if present) is weak. A cartoon of a GPS/CSS source geometry is shown in Fig. 5. The two lobes do not extend beyond the optical host galaxy, hence the probability of tracing host galaxy ISM should be high, especially if the central environment is enriched due to a merger event. Assuming a spherical, radially declining density distribution of the ISM gas, the larger sources will probe lower density gas. In order to see if such a density distribution could explain the anti-correlation in our data, we calculate the expected integrated absorption $`N_{\mathrm{HI}}=n(r)𝑑l`$ towards the two lobes, where $`dl`$ corresponds to the path of absorption along the line of sight. In this estimate we use a source with an inclination of 45, however, for this symmetric model the resulting Hi column density is only weakly dependent on the inclination.

A first approach is to assume that the density follows a King profile:

$$n=n_0(1+\frac{r^2}{r_\mathrm{c}^2})^\beta $$
(1)
where $`r_\mathrm{c}`$ is the core radius of the gas distribution and $`n_0`$ is is the density at 1 kpc. From X-ray data, which traces the ionised gas component, the core radius for ellipticals is usually derived to be $``$ 1 kpc (Trinchieri et al. trinchieri86 (1986); Forman et al. forman85 (1985)). We consider the simplest case, that the atomic gas component is a constant fraction of the ionised gas and follows a similar profile. The two variable parameters to be constrained are $`n_0`$ and $`\beta `$, and we test the goodness of the fit by calculating the sum of squares for the observed and calculated Hi column densities. The best fit to the data is then achieved for $`n_0=`$ 0.05 cm-3 and $`\beta =`$ 1.06. The resulting absorbed Hi column density as a function of source size is plotted with the dotted line in Fig. 7 (calculated for a core radius of 1 kpc and host ISM outer radius of 50 kpc). In this figure the observed values in our sample are plotted with triangles. The King model has a more or less uniform density in its centre, thus for any value of $`\beta `$ such a density model is unable to reproduce the slope in the data at small linear sizes. The only possibility to reproduce the observed data is to reduce the core radius by several orders of magnitude and, in addition, to increase the core density above 100 cm-3. However, then the density model does not follow a typical King ISM profile any longer.

A King model of the density appears inconsistent with not only our data, but also with what is generally assumed for the medium in which the GPS sources expand. More often a simple, steep power law is used, and such power laws successfully explain the detection rates of sources of different sizes (e.g. Fanti et al. fanti95 (1995); Readhead et al. readhead96 (1996); O’Dea & Baum odea97 (1997)). Therefore we instead assume a power law density profile

$$n=n_0(\frac{r}{r_0})^\beta $$
(2)
where $`n_0`$ is the number density (in cm-3) at $`r_0=`$ 1 kpc. We again construct a sum of squares surface, which gives a best fit to the data for $`\beta `$ 1.40 and $`n_0=`$ 0.009 cm-3(this best fit is plotted in Fig. 7). Assuming a volume filling factor of unity, the integrated Hi mass within a radius of 10 kpc can then be estimated to be 7$`\times 10^7`$ M. We note that if the filling factor is less than 1, the estimated mass will decrease, and our estimated Hi mass is thus an upper limit. Since the host galaxies of GPS/CSSs may preferentially be found in merging/interacting systems (de Vries et al. devries00 (2000); O’Dea et al. odea96 (1996)), it is interesting to compare the mass of Hi with what has been found in the more nearby population of the luminous infra-red galaxies (ULIRGs). Those sources are also associated with interactions (although between gas rich galaxies), and more or less all of them are detected in Hi emission with masses in the range of 5$`\times 10^8`$ to 3$`\times 10^{10}`$ M, with typical values of the order of $`10^9`$ M (Mirabel & Sanders mirabel88 (1988)). Even though our objects may also be merging systems, a spherical distribution indicates that the GPS/CSSs are less gas rich than the ULIRGs.

Given that the host galaxies of radio loud sources are ellipticals, it is also interesting to compare our derived gas mass with what is found in nearby non-AGN ellipticals. Around 15% of those normal ellipticals are detected in Hi emission with masses $`M_{\mathrm{HI}}`$ $`10^9`$ M (Huchtmeier et al. huchtmeier95 (1995); Knapp et al. knapp85 (1985)). Typical upper limits of the remaining 85% are of the order of $`10^8`$ – $`10^9`$ M. Given the sensitivity of the Hi emission experiments, the Hi mass we calculate assuming a spherical power law density profile is consistent with our GPS/CSS sources being hosted by normal ellipticals.

### 4.2 Disk distribution

Instead of spherically distributed gas, another plausible distribution is a disk in a plane roughly perpendicular to the radio source. For most source orientations this means that only the far radio lobe is occulted. It has been shown from VLA and ATCA Hi imaging that early-type E and S0 galaxies often have their Hi in disk systems (e.g. Sadler et al. sadler00 (2000); Oosterloo et al. oosterloo99 (1999)). Many large scale radio sources show Hi absorption that is consistent with circumnuclear gas, extended on scales of a few pc in radio loud FRIs up to scales of a few 100 pc in low luminosity Seyferts (e.g. van Langevelde et al. vanlangevelde00 (2000); Taylor taylor96 (1996); Gallimore et al. gallimore99 (1999); Vermeulen et al. vermeulen02 (2002)). HST imaging has revealed nuclear disks of gas and dust in radio loud AGN (Verdoes Kleijn et al. verdoes99 (1999); de Koff et al. dekoff00 (2000)). In particular recent HST observations of a few GPS/CSS sources have shown them to contain central disks of gas and dust (4C 31.04, 1946+708 and 1146+596; Perlman et al. perlman01 (2001)). Other high resolution absorption studies of nearby GPSs show that the Hi data are consistent with a rotating ring (e.g. in 1946+708; Peck et al. peck99 (1999) and 4C 31.04; Conway conway96 (1996)). Here we consider the case of the absorbing gas in a disk oriented perpendicular to the radio axis.

In this case absorption will only be seen against the far lobe. For a cartoon image of the simple disk see Fig. 6. The maximum radius of the disk, $`r_{\mathrm{disk}}`$, is assumed to be at least 10 kpc and thus for sources of projected linear sizes up to 10 kpc the far lobe is always covered by the disk. When calculating the Hi column densities, we assume the disk has a radial density profile $`n=n_0(r/r_0)^\beta `$, where $`n_0`$ is the density at $`r_0=1`$ kpc. The calculated column densities will be a function of both viewing angle as well as the disk opening angle. In our modelling we limit ourselves to a viewing angle of 45, and uses disk opening angles of 10°, 20° and 30°. We again test the goodness of fit using the sum of squares method. Given the scatter in the data all such opening angles give similar fits, and in Fig. 7 we plot the best fit for a disk full opening angle of 20°, yielding $`n_0=0.11`$ and $`\beta =1.45`$.

A 10kpc radius disk will, assuming there is an inner radius of the disk of 1pc, yield an atomic mass of the order of $`10^8`$ M. This is comparable to the results of the spherical distribution (Sect. 4.1). Following the discussion in Sect. 4.1, we find that also for a disk distribution the GPS/CSSs appear to be less gas rich than the ULIRGs.

## 5 Comparison with GPS/CSS models

Currently the most favoured explanation to the small sizes of most GPS and CSS sources is that they are young, as estimated both from their measured expansion speed as well as from synchrotron ageing (e.g. Owsianik & Conway owsianik98a (1998); Murgia et al. murgia99 (1999)). In this ’youth’ scenario the dense gas interacts with the radio plasma giving a large radio luminosity which then explains the relatively larger number of sources with small size. In order to explain the number density of sources of a given size, the radio jet is assumed to propagate in a medium with decreasing density, approximated with a power law profile $`r^\beta `$ with a slope $`\beta =`$ 1.5 – 2 (Fanti et al. fanti95 (1995); Begelman begelman96 (1996), Readhead et al. readhead96 (1996)). Given our uncertainties, it is interesting that this exponent is comparable with the $`\beta `$ 1.4 we get from our Hi absorption.

Alternatively the GPS/CSSs have been suggested to be old ’frustrated’ sources prevented from growing by a very dense medium (e.g. van Breugel et al. vanbreugel84 (1984); Fanti et al. fanti90 (1990)). In Sect. 1 we mentioned several observations showing the presence of gas in GPS/CSSs. Other evidence for dense environments comes from effects thought to derive from interactions with the surrounding medium, several CSS objects for example display distorted radio morphologies (e.g. van Breugel et al. vanbreugel84 (1984)) and alignment effects between the radio axis and the optical emission (e.g. de Vries et al. 1997b ). Obviously, there is compelling evidence for dense gas in GPS/CSS sources; the question is whether the central density is large enough to give frustration.

While the frustration model is now less popular it is still possible that a minority of the GPS/CSS sources are created in this way. Here we discuss our Hi results in context of those two models.

### 5.1 The frustration scenario

In order to confine a median luminosity CSS, an average number density in the range 1 – 10 cm-3 at $`r=`$ 10 kpc is needed (de Young deyoung93 (1993)). This implies, for a uniform density, gas masses of the order of $`10^{10}`$ M. In our power law density model we derive atomic gas masses of the order of $`10^8`$ M, two orders of magnitude less. Comparison of molecular data with Hi data for elliptical galaxies have indicated a $`M_{\mathrm{H2}}/M_{\mathrm{HI}}`$ ratio of the order of 0.4 (Wiklind et al. wiklind95 (1995)). If such a number is applicable also to the GPS/CSS sources, it implies total gas masses around a few times $`10^8`$ M. This result may change if the ratio $`M_{\mathrm{H2}}/M_{\mathrm{HI}}`$ is very different. For the gas rich ULIRGs however, the total molecular gas mass derived from CO emission, and the atomic gas mass derived from Hi emission are of the same order ($`10^9`$ M; Downes & Solomon downes98 (1998); Mirabel & Sanders mirabel88 (1988)), and will thus change the resulting total gas mass by a small factor. Given those estimates, the Hi absorption data suggests that there is not enough gas to frustrate the radio sources.

### 5.2 The youth model

The young ages estimated from the hotspot advance speeds are strong arguments in favour of the youth model. Using ram pressure arguments, the lobe advance speed $`v_\mathrm{a}`$ is related to the external mass density $`\rho _{\mathrm{ext}}`$ and the hotspot pressure $`p_\mathrm{i}`$ by

$$p_\mathrm{i}=\rho _{\mathrm{ext}}v_\mathrm{a}^2=n_{\mathrm{ext}}m_\mathrm{p}v_\mathrm{a}^2$$
(3)
Thus, for sources with measured expansion velocities, we can estimate the density $`n_{\mathrm{ext}}`$ at the hotspot location. We can further compare $`n_{\mathrm{ext}}`$ with the density expected using the power law density distribution models discussed in Sect. 4.

Published in the literature we find a selection of 7 sources with measured advance speeds and quoted (or sufficient information to calculate) internal hotspot pressures. For those sources, we list in Table 4 the distance between the core and hotspot, the advance speed, hotspot pressure and the corresponding references. We use Eq. (3) to derive external densities $`n_{\mathrm{ext}}`$ (Table 4) at the given hotspot radius.

In order to derive densities using the disk and spherical power law density profile (Eq. (2)), we first note that all sources listed in Table 4 have very small linear sizes. Especially, for sources $`<0.1`$ kpc there are large offsets between the measured Hi column density and the Hi column density as predicted by our simple models (Fig. 7). For the sources with measured Hi column density, we therefore apply a correction factor ($`C_{\mathrm{HI}}=N_{\mathrm{HI},\mathrm{measured}}/N_{\mathrm{HI},\mathrm{predicted}}`$), in order to better estimate the density in the source in question. We also note that the estimated density will depend on the spin temperature; the values for the column density used in Sect. 3 assumes a $`T_{\mathrm{sp}}=100`$K. However, close to an X-ray irradiating AGN the spin temperature is likely to be above 100K, and probably closer to 8000 K if the gas is purely atomic (Maloney et al. maloney96 (1996)).

For the spherical density profile, we use the power law profile (Eq. (2)) and express the density $`n_\mathrm{S}`$ as a function of radius and spin temperature:

$$n_\mathrm{S}=C_{\mathrm{HI}}n_{\mathrm{HI}}(\frac{T_{\mathrm{sp}}}{100\mathrm{K}})=C_{\mathrm{HI}}n_0r_{\mathrm{kpc}}^\beta (\frac{T_{\mathrm{sp}}}{100\mathrm{K}})$$
(4)
Applying the best fitting values of $`n_0`$ and $`\beta `$ from Sect. 4.1, and using a spin temperature of 100K we achieve:

$$n_{\mathrm{S},100\mathrm{K}}C_{\mathrm{HI}}\text{ 0.009}r_{\mathrm{kpc}}^{1.4}$$
(5)
At a given radius Eq. (5) gives the Hi density, and is thus a lower limit to the total density. Using the radius of the sources in Table 4, we calculate the corresponding values of the density $`n_{\mathrm{S},100\mathrm{K}}`$. For this model we have chosen to use $`T_{\mathrm{sp}}=100`$K, since that gives the closest match to the densities $`n_{\mathrm{ext}}`$ estimated from the ram-pressure argument. If the spin temperature is 8000 K, the estimated $`n_\mathrm{S}`$ will be 80 times higher.

If instead the absorbing gas is in a disk distribution, we can estimate the density at the hotspots (which must be in a medium external to the disk, see Fig. 6) by assuming that the disk internal pressure will be similar to the pressure outside the disk. Since we do not have any information on the properties of such a disk, we will first consider the simplest case, assuming the disk to be completely atomic and to have an uniform kinetic temperature $`T_{\mathrm{disk}}=T_{\mathrm{sp}}`$. The external medium is assumed to be ionised with an electron temperature $`T_{\mathrm{ext}}=`$ $`10^4`$ K. Applying the ideal gas law the external density $`n_\mathrm{D}`$ can be written as:

$$n_\mathrm{D}=C_{\mathrm{HI}}n_{\mathrm{HI}}(\frac{T_{\mathrm{sp}}}{100\mathrm{K}})(\frac{T_{\mathrm{sp}}}{T_{\mathrm{ext}}})=C_{\mathrm{HI}}n_0r_{\mathrm{kpc}}^\beta (\frac{T_{\mathrm{sp}}}{100\mathrm{K}})(\frac{T_{\mathrm{sp}}}{T_{\mathrm{ext}}})$$
(6)
For a disk opening angle of 20°, we derived a value of $`n_0=`$ 0.11 cm-3 and $`\beta =`$ 1.45 (Sect. 4.2), and assuming a spin temperature of 1000K we rewrite Eq. (6) into

$$n_{\mathrm{D},1000\mathrm{K}}0.11C_{\mathrm{HI}}r_{\mathrm{kpc}}^{1.45}$$
(7)
Again, this is a lower limit to the total gas density present. In order to get densities which best agree with those estimated via the ram pressure argument, we here use a $`T_{\mathrm{sp}}=1000`$K. The resulting values of $`n_{\mathrm{D},1000\mathrm{K}}`$ are listed in Table 4.

Excluding J0111+3906, for the spherical power law model most $`n_{\mathrm{ext}}`$ and $`n_{\mathrm{S},100\mathrm{K}}`$ values are remarkably similar, and in most cases only differ within an order of a magnitude; which is consistent with the GPSs propagating through a purely atomic spherical gas distribution. The offset can depend on a number of things. Firstly, it is possible that the spin temperature has a very different value. Secondly, and closely linked to the spin temperature, is the expected molecular abundance. If the kinetic temperature is as low as 100K, the molecular abundance is expected to be high (Maloney et al. maloney96 (1996)), and thus our Hi density estimate is only a lower limit to the total gas density. Thirdly, the value of $`\beta `$ and $`n_0`$ could be different, given the sparse amount of data used in the fitting (22 points). Within a 90% confidence region the value of $`\beta `$ may change as much as $`\pm `$0.25 and $`n_0`$ as much as $`\pm `$4e-3, with a corresponding difference of $``$ 1 in the number density at a radius of 0.05 kpc. Finally the individual viewing angles of the sources in Table 4 may affect the assumed radius where the hotspot is located.

The densities derived from the disk profile are equally similar, differing with only a factor of a few from $`n_{\mathrm{ext}}`$ (except for J0111+3906). The offsets are not surprising, given the large number of uncertainties in the calculation of $`n_{\mathrm{D},1000\mathrm{K}}`$. In addition to the reasons already given for the spherical distribution, the ratio $`T_{\mathrm{disk}}/T_{\mathrm{ext}}`$ could for instance be very different from the assumed value.

We conclude that within the scope of the power law profile, we more or less can reproduce the densities expected in the youth model for the GPS sources with measured lobe velocities.

## 6 Orientation effects on the observed HI
column density: galaxies versus quasars

In most cases the spatial resolution of present Hi data is not enough to determine whether the absorption covers both lobes (consistent with ISM gas) or only one lobe (indicating a disk distribution). In the previous sections we showed that, given the limited information we have about the density profiles, both a disk as well as a spherical distribution are consistent with the observed relation between Hi column density and linear size. One possibility to distinguish between those models is to look at any possible orientation effects. Assuming the unified scheme, quasars are supposed to be seen at a smaller viewing angle $`\alpha `$ (more end-on) than the radio galaxies. In fact, we have shown that there appears to be a larger detection rate in galaxies than in quasars (Sect. 3.1).

For a given projected source size of 1 kpc, the amount of expected Hi absorption as a function of viewing angle can be estimated. Given that for a projected size of 1 kpc we have a Hi column density sensitivity of around $`10^{20}`$ cm-2 (Fig. 1), the spherical density profile predicts we would detect equal column densities in galaxies (with say $`\alpha `$ 45°; Barthel barthel89 (1989)) and quasars ($`\alpha `$ 45°). In contrast for the disk profile there will be a range of optimum viewing angles, for which we are likely to detect Hi absorption. This exact range of viewing angles will be extremely dependent on the disk model used. In Sect. 6.1 we discuss if the galaxies and quasars in our sample are consistent with having different viewing angles, as expected from unified schemes. If so, a spherically symmetric distribution could be considered less likely, since objects classified as galaxies appear to have higher Hi column densities than quasars.

### 6.1 Core prominence

Because of relativistic boosting the core strength is considered to be a good indicator of orientation; the more dominant the core is, the smaller the viewing angle. For larger radio sources, this has been investigated by a number of people (e.g. Orr & Browne orr82 (1982)). Since the GPS/CSS objects in general have weak or no core emission, similar studies have been difficult. Stanghellini et al. (stanghellini01 (2001)) reports on VLBA observations of 10 GPS sources. The authors conclude that in the few cases where cores were detected, the core of the GPS galaxies accounted for $`2`$% of the total flux density, while in the GPS quasars the core accounted for $`20`$%. Moreover, Saikia et al. (saikia95 (1995)) studied a sample of CSS sources with detected radio cores, and found that the degree of core prominence were consistent with those for larger radio sources and also consistent with the unified scheme. In the study by Saikia et al. (saikia95 (1995)), there are 7 sources that can also be found in our sample (3 quasars and 4 galaxies). For the galaxies the average fraction of emission from the core is $`\overline{f}_\mathrm{c}=`$ 0.012, while the corresponding number for the quasars is $`\overline{f}_\mathrm{c}=`$ 0.26. In Fig. 8 we plot the Hi column density versus $`f_\mathrm{c}`$ for those objects, and we mark quasars and galaxies with different symbols. Clearly the quasars have larger core prominence. This implies the quasars have a smaller viewing angle.

Only one of these quasars is detected in Hi absorption, while three of the galaxies are Hi absorbers. For the sources in common with the sources of Saikia et al. (saikia95 (1995)), it appears as if the upper limits of the Hi column density for the quasars are smaller than the detections for the radio galaxies. It would be interesting to carry out deeper observations for a larger sample of the CSS quasars with upper limits; if deeper searches showed (for a majority of the sources) lower column densities or upper limits for the quasars than for the radio galaxy detections, this would strongly argue for a disk origin for the Hi absorption.

### 6.2 GPS quasars versus GPS galaxies

It should be noted that it is debated whether the GPS quasars are really intrinsically small sources like the GPS galaxies. Snellen (snellen97 (1997)) proposes that GPS galaxies viewed end-on will have a flat spectra and thus the GPS galaxies and quasars are different types of objects. This has some support in a very different redshift distribution for the GPS galaxies and quasars (Snellen snellen97 (1997); Stanghellini stanghellini98 (1998)), and the fact that many GPS quasars appear to have core-jet morphologies when observed at high angular resolution (Stanghellini stanghellini01 (2001)). If this is the case, the low detection rate in the GPS quasars reported here could be explained by them being large scale radio sources, hence with a lower probability of the line of sight going through the host galaxy.

## 7 Implications for the spectral turn-over mechanism

The integrated radio spectrum turn-over frequency for GPS/CSS sources is known to have a relationship $`\nu _\mathrm{t}LS^{0.65}`$ (O’Dea & Baum odea97 (1997)). Most often this is ascribed to synchrotron selfabsorption (e.g. O’Dea & Baum odea97 (1997)); however an alternative possibility is the one of free-free absorption (e.g. Bicknell et al. bicknell97 (1997)). A few VLBI results indicate the presence of a nuclear disk causing free-free absorption (Marr et al. marr01 (2001); Peck et al. peck99 (1999)).

Since our Hi results show that the column density along the line of sight depends on the source linear size (and thus turnover frequency), it is likely that a similar relationship exists for an ionised gas component. The free-free absorption turn-over frequency is related to the electron density, $`\nu _\mathrm{t}(n_\mathrm{e}^2)^{1/2.1}`$. If we simply assume the gas fraction to be constant ($`n_{\mathrm{HI}}/n_\mathrm{e}=C`$) and $`N_{\mathrm{HI}}=n_\mathrm{e}L`$ where L is the absorbing pathlength, the observed relationship ($`N_{\mathrm{HI}}LS^{0.43}`$) implies a free-free absorption caused turnover relationship $`\nu _\mathrm{t}LS^{0.41}`$. This is much less steep than observed ($`\nu _\mathrm{t}LS^{0.65}`$), implying that free-free absorption can not be the only turn-over mechanism present.

Conversely we could assume that the observed relationship between turnover frequency and linear size is due to free free absorption. Then, $`\nu _\mathrm{t}LS^{0.65}`$ implies that the slope for the ionised gas component necessarily is larger than the slope we observe for Hi. In this case perhaps there is a gradient of the fraction of ionised gas decreasing with radius.

## 8 Conclusions

We have investigated the combined results of Hi absorption in GPS/CSS sources. The most striking result is that the smaller GPS sources ($`<`$ 0.5 kpc) tend to have larger Hi column densities than the larger CSS sources ($`>`$ 0.5 kpc). This anti-correlation between linear size and absorbed Hi column density is mostly an effect from opacity differences rather than line width differences. It is possible to use a simple power law profile of the density to explain the observed Hi column densities, and both a spherically symmetric medium as well as disk can be fitted to the data.

Our modelling cannot distinguish between the spherical and disk density models, and most observations at present do not have enough resolution to determine the location of the absorbing gas. However, to date high resolution Hi data exist for a limited number of sources that in all cases indicate Hi disks (Conway conway96 (1996); Peck et al. peck99 (1999); Peck & Taylor peck98 (1998)). This argues for a disk model, and in addition we notice that most Hi absorbers are found in sources classified as galaxies. By studying our sources in their radio continuum properties we find that the galaxies and quasars in our sample behave similarly to larger scale sources, where orientation effects are known to take place. Therefore, it is easier to argue for a disk model, where sources with very small viewing angles in addition to sources observed edge-on would be less likely to have Hi detectable in absorption against their lobes. The fact that quasars have smaller column densities argues against a spherically symmetric model for the Hi gas.

###### Acknowledgements.

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.


format: text

text:
# Supersymmetric Extension of the Lorentz and CPT-violating Maxwell-Chern-Simons Model

## I  Introduction

Lorentz and CPT invariances are cornerstones in modern Quantum Field Theory, both symmetries being respected by the Standard Model for Particle Physics. Nevertheless, nowadays one faces the possibility that this scenario is only an effective theoretical description of a low-energy regime, an assumption that leads to the idea that these fundamental symmetries could be violated when one deals with energies close to the Planck scale Jackiw . Taking this viewpoint, several approaches to analyze the violation of Lorentz symmetry have been proposed in the literature. Eventually a common feature arises: the violation is implemented by keeping either a four-vector (in a CPT-odd term Jackiw ) or a traceless symmetric tensor (CPT-preserving term Kostelec1 ) unchanged by particle inertial frame transformations Colladay  which is generally called spontaneous violation. Furthermore, the issue of preserving supersymmetry (Susy) while violating Lorentz symmetry is addressed to berger . This breaking of Lorentz symmetry is also phenomenologically motivated as a candidate to explain the patterns observed in the detection of ultra-high energy cosmic rays, concerning the events with energy above the GZK ( $`E_{GZK}4\times 10^{19}eV.T`$) cutoff raios . Moreover, measurements of radio emission from distant galaxies and quasars verify that the polarization vectors of these radiations are not randomly oriented as naturally expected. This peculiar phenomenon suggests that the space-time intervening between the source and observer may be exhibiting some sort of optical activity, the origin of which is not known.

In a Theoretical Field proposal where this breaking of Lorentz invariance is taken into account, an analysis of the unitarity, causality, and vortex-like solutions had been carried out in Ref. Baeta . Another focus of interest points to planar gauge systems, which play a relevant role in Condensed Matter descriptions, as they happen to be related to issues like high-Tc superconductivity and fractionary quantum Hall effect. Possible contributions from Lorentz-violating terms to the appearance of anisotropy in planar systems had been investigated in Refs. Manojr  and beto .

A first proposal of Supersymmetry-Preserving Lorentz Violation was carried out in the work of Ref.berger . The aim of that work was to investigate whether one could maintain desired properties of supersymmetric systems, namely, cancellation of divergences and the patterns of spontaneous breaking schemes, while violating Lorentz symmetry. A Lorentz breaking tensor with constants entries has been adopted following an original suggestion given by Colladay Colladay . Working upon a modified Wess-Zumino model, the authors of Ref. berger  had demonstrated that convenient changes of the Susy-algebra of fermionic charges and of Susy-covariant derivatives expressions were enough to define a Susy-like invariance for the Lorentz violating starting theory. As a matter of fact the modification of the algebra was achieved by adding a particular tensor-dependent central term, of the $`k_{\mu \upsilon }^\nu `$ type, where $`k_{\mu \upsilon }`$ exhibits real symmetric traceless tensor properties.

As a net result, it was shown that a model for a modified-Susy invariant but Lorentz non-invariant matter system can be built. Moved by a different perspective, we now present an analysis on Lorentz and Susy breakings concerning degrees of freedom in the gauge field sector. We start off by establishing the supersymmetric minimal extension for the Chern-Simons-like term Jackiw ,

$$\mathrm{\Sigma }_{CS}=\frac{1}{4}𝑑x^4ϵ^{\mu \nu \alpha \beta }c_\mu A_\nu F_{\alpha \beta },$$
(1)
preserving the usual $`(1+3)`$-dimensional Susy algebra. The breaking of Susy will follow the very same route to Lorentz breaking: the statement that $`c_\mu `$ is a constant (in the active sense) vector triggers both Lorentz and, as we shall comment on, Susy breakings. Handling proper superfield extensions for the background shall prevent the model from displaying higher spin excitations, and interesting self-couplings for the gauge sector as well as background contribution for the gaugino masses come up naturally as a consequence of the (initially) supersymmetric structure.

In the next section, we present the Susy minimal extension for 1. In Section 2, a first generalization, with non-polynomial couplings, shows up. Finally, we comment on conclusions and perspectives in Section 4.

## II The Supersymmetric Extension of the Maxwell-Chern-Simons Model.

Adopting covariant superspace-superfield formulation, we propose the following minimal extension for 1:

$$A=d^4xd^2\theta d^2\overline{\theta }\left\{W^a(D_aV)S+\overline{W}_{\dot{a}}(\overline{D}^{\dot{a}}V)\overline{S}\right\},$$
(2)
where the superfields $`W_a`$, $`V`$, $`S`$ and the Susy-covariant derivatives $`D_a`$, $`\overline{D}_{\dot{a}}`$ hold the definitions:

$`D_a`$ $`=`$ $`{\displaystyle \frac{}{\theta ^a}}+i\sigma _{}^{\mu }{}_{a\dot{a}}{}^{}\overline{\theta }^{\dot{a}}_\mu `$
$`\overline{D}_{\dot{a}}`$ $`=`$ $`{\displaystyle \frac{}{\overline{\theta }^{\dot{a}}}}i\theta ^a\sigma _{}^{\mu }{}_{a\dot{a}}{}^{}_\mu ;`$
from $`\overline{D}_{\dot{b}}W_a(x,\theta ,\overline{\theta })=0`$ and $`D^aW_a(x,\theta ,\overline{\theta })=`$ $`\overline{D}_{\dot{a}}\overline{W}^{\dot{a}}(x,\theta ,\overline{\theta })`$, it follows that

$$W_a(x,\theta ,\overline{\theta })=\frac{1}{4}\overline{D}^2D_aV:$$

Its $`\theta `$-expansion reads as below:

$`W_a(x,\theta ,\overline{\theta })`$ $`=`$ $`\lambda _a\left(x\right)+i\theta ^b\sigma _{}^{\mu }{}_{b\dot{a}}{}^{}\overline{\theta }^{\dot{a}}_\mu \lambda _a\left(x\right){\displaystyle \frac{1}{4}}\overline{\theta }^2\theta ^2\mathrm{}\lambda _a\left(x\right)`$
$`+2\theta _aD\left(x\right)i\theta ^2\overline{\theta }^{\dot{a}}\sigma _{}^{\mu }{}_{a\dot{a}}{}^{}_\mu D\left(x\right)`$
$`+\sigma _{}^{\mu \nu }{}_{a}{}^{}{}_{}{}^{b}\theta _bF_{\mu \nu }\left(x\right){\displaystyle \frac{i}{2}}\sigma _{}^{\mu \nu }{}_{a}{}^{}{}_{}{}^{b}\sigma _{}^{\alpha }{}_{b\dot{a}}{}^{}\theta ^2\overline{\theta }^{\dot{a}}_\alpha F_{\mu \nu }\left(x\right)`$
$`i\sigma _{a\dot{a}}^\mu _\mu \text{ }\overline{\lambda }^{\dot{a}}\left(x\right)\theta ^2`$
and $`V=V^{}`$. The Wess-Zumino gauge choice is taken as usually done:

$$\text{ }V_{WZ}=\theta \sigma ^\mu \overline{\theta }A_\mu (x)+\theta ^2\overline{\theta }\overline{\lambda }\left(x\right)+\overline{\theta }^2\theta \lambda (x)+\theta ^2\overline{\theta }^2D,$$

so the action (2) is gauge-invariant. The background superfield is so chosen to be a chiral one. Such a constraint restricts the maximum spin component of the background to be an $`s`$ $`=`$ $`\frac{1}{2}`$ component-field, showing up as a Susy-partner for a spinless dimensionless scalar field. Also, one should notice that $`S`$ happens to be dimensionless. The superfield expansion for$`S`$ then reads:

$`\overline{D}_{\dot{a}}S\left(x\right)`$ $`=`$ $`0\text{ and }S\left(x\right)\text{ }=s\left(x\right)+i\theta \sigma ^\mu \overline{\theta }_\mu s\left(x\right){\displaystyle \frac{1}{4}}\overline{\theta }^2\theta ^2\mathrm{}s\left(x\right)`$
$`+\sqrt{2}\theta \psi \left(x\right)+{\displaystyle \frac{i}{\sqrt{2}}}\theta ^2\overline{\theta }\overline{\sigma }_\mu _\mu \psi \left(x\right)+\theta ^2F\left(x\right).`$
The component-wise counterpart for the action (2) is as follows:

$`A_{comp.}`$ $`=`$ $`{\displaystyle }d^4x\text{ }\{{\displaystyle \frac{1}{2}}(s+s^{})F_{\mu \nu }F^{\mu \nu }+{\displaystyle \frac{i}{2}}_\mu (ss^{})\epsilon ^{\mu \alpha \beta \nu }F_{\alpha \beta }A_\nu +4D^2(s+s^{})`$ (3)
$``$ $`2is\lambda \sigma ^\mu _\mu \overline{\lambda }2is^{}\overline{\lambda }\overline{\sigma }^\mu _\mu \lambda \sqrt{2}\lambda (\sigma ^{\mu \nu })F_{\mu \nu }\psi +\sqrt{2}\overline{\lambda }(\overline{\sigma }^{\mu \nu })F_{\mu \nu }\overline{\psi }+`$
$`+`$ $`\lambda \lambda F+\overline{\lambda }\overline{\lambda }F^{}2\sqrt{2}\lambda \psi D2\sqrt{2}\overline{\lambda }\overline{\psi }D\}`$
As one can easily recognize, the first line displays the 4D Chern-Simons-like term (1), where the vector $`c_\mu `$ is expressed as the gradient of a real background scalar: $`c_\mu `$ $`=`$ $`_\mu \sigma `$, for $`s`$ $`=`$ $`\xi +i\sigma `$. Such a reduction of the vector into a gradient of a scalar field stems directly from the simultaneous requirements of both gauge111The gauge invariance of action 2 will become clearly manifest in the next section, where we rephrase the supersymmetrization of the 4D Chern-Simons-like term in a formulation restricted to the chiral (anti-chiral for the h.c. counterpart) sector of superspace. and supersymmetry invariances.

Another interesting feature of this model concerns the presence of self-couplings for the gauge sector: the fermionic background field, $`\psi `$, triggers the coupling of the gauge boson (through the field-strength) to the gaugino. Moreover, using the field equation for the gauge auxiliary field $`D`$ one arrives at a quartic fermionic fields coupling - $`\lambda \lambda \psi \psi `$ -, and the background nature of $`\psi `$ indicates a background contribution for the gaugino mass222We shall analyze the propagator structure for the gauge component-fields in a forthcoming communication. We anticipate that a constant $`\psi `$ component-field configuration is compatible with the supersymmetry algebra..

Concerning the breaking of Lorentz symmetry, realized by assuming $`c_\mu `$ $`=`$ $`_\mu \sigma `$ to be constant under the action of particle inertial frame transformations, one should observe that such an assumption implies that the scalar component-field $`\sigma `$ must be linear in the coordinates, $`\sigma =c_\mu x^\mu `$. As a matter of fact, a linear dependence on $`x^\mu `$ cannot be implemented by means of a Susy-covariant constraint (i.e., Susy-covariant derivatives acting on $`S`$), and, in that sense, the choice of a rigid $`_\mu \sigma `$ breaks Susy in exact analogy to the Lorentz breaking scheme adopted. To better establish such a correspondence, one can consider the choice for constant $`_\mu \sigma `$ to be accompanied by a constant $`\psi `$ requirement (and a constant auxiliary field, $`F`$, as well333In fact, a constant auxiliary field $`F`$ is singled out as a susy-invariant parameter, as far as one deals with a constant $`\psi `$.). In this context, a (passive) Susy-transformation keeps the status of all component-fields unchanged.

In the next section, we provide the model with a non-polynomial generalization, which brings about the possibility of understanding the 4D C.S.-like term as a first order correction in a complete exponential scenario.

## III Non-polynomial generalization

Let us note that the integration defined through the Grassmanian measure $`d^2\overline{\theta }`$ (or $`d^2\theta `$ ) can be represented by the action of a squared Susy-covariant derivative (up to a normalization factor), $`\overline{D}^2`$ (or $`D^2`$), on the super-Lagrangian $`W^a(D_aV)S`$ $`+`$ $`h.c.`$, if one neglects boundary terms, and that the only sector of the superfield product $`W(DV)S`$ (or $`\overline{W}(\overline{D}V)\overline{S}`$) that admits a non-null action of $`\overline{D}^2`$ (or $`D^2`$) is the factor $`DV`$ (or $`\overline{D}V`$ ). Such a manipulation leads to the Lagrangian $`d^4x(`$ $`d^2\theta `$ $`W^a(\overline{D}^2D_aV)S`$ $`+`$ $`d^2\overline{\theta }`$ $`\overline{W}_{\dot{a}}(D^2\overline{D}^{\dot{a}}V)\overline{S}`$

$`)`$, and one can rephrase (2) through such a parametrization:

$$A=hd^4x\left\{d^2\theta [W^aW_aS]+d^2\overline{\theta }\left[\overline{W}_{\dot{a}}\overline{W}^{\dot{a}}\overline{S}\right]\right\},$$

where a suitable dimensionless (perturbation) parameter $`h`$ is inserted. We remark that such an inclusion does not spoil any power-counting renormalization property of the model. Moreover, as we aim at a Susy version for a model hosting both regular Maxwell kinetic term and the 4D C.S.-like term Baeta , we end up with the following combination:

$$A_{Max.+C.S.}=\frac{1}{4}d^4x\left\{d^2\theta [W^aW_a]+d^2\overline{\theta }\left[\overline{W}_{\dot{a}}\overline{W}^{\dot{a}}\right]\right\}+\frac{h}{4}d^4x\left\{d^2\theta [W^aW_aS]+d^2\overline{\theta }\left[\overline{W}_{\dot{a}}\overline{W}^{\dot{a}}\overline{S}\right]\right\}.$$

Such an expression induces a straightforward non-polynomial generalization:

$$A_{nonpol.}=\frac{1}{4}d^4x\left\{d^2\theta \left[W^aW_a\mathrm{exp}(hS)\right]+d^2\overline{\theta }\left[\overline{W}_{\dot{a}}\overline{W}^{\dot{a}}\mathrm{exp}(h\overline{S})\right]\right\},$$
(4)
leaving room for a perturbative approach parametrized by orders of $`h`$. In fact, the action (4) includes a zero order supersymmetric Maxwell theory, a first-order Susy-extended 4D C.S.-like term (reproducing the action of the eq. (3)), and higher orders contributions. In component-field parametrization, action (4) reads:

$`A_{nonpol.}`$ $`=`$ $`{\displaystyle \frac{1}{4}}{\displaystyle }d^4x\{\mathrm{exp}(hs)[{\displaystyle \frac{1}{2}}F_{\mu \nu }F^{\mu \nu }{\displaystyle \frac{i}{2}}\stackrel{~}{F}_{\mu \nu }F^{\mu \nu }2i\lambda ^a\sigma _{}^{\mu }{}_{a\dot{a}}{}^{}_\mu \text{ }\overline{\lambda }^{\dot{a}}+4D^2+`$
$`+h(2\sqrt{2}\lambda ^a\psi _aD+\lambda ^a\lambda _aF\sqrt{2}\lambda ^a(\sigma ^{\mu \nu })_{a}^{}{}_{}{}^{b}F_{\mu \nu }\psi _b){\displaystyle \frac{h^2}{2}}\lambda ^a\lambda _a\psi ^b\psi _b]+h.c..\}`$
The exponential version brings about the 4D C.S.-like term in the form $`\frac{i}{8}\mathrm{exp}(hs)\stackrel{~}{F}_{\mu \nu }F^{\mu \nu }+h.c.`$, demanding an integration by parts to reproduce the expression $`i_\mu (ss^{})\epsilon ^{\mu \alpha \beta \nu }F_{\alpha \beta }A_\nu `$. One should also realize that a quartic fermion-fields coupling is already present at order $`h^2`$ , even if the field equation for the auxiliary field $`D`$ is not used to eliminate it. It is also interesting to observe how the background components $`s`$, $`\psi `$ and $`F`$ influence on the gaugino physical mass.

## IV Concluding Comments

Working on the gauge-field sector of a system with a Lorentz breaking 4D-Chern-Simons-like term, we have been able to derive its minimal supersymmetric extension and a peculiar nom-polynomial generalizations has been proposed that is compatible with $`N=1`$-Susy. Focusing on the minimal Susy-extension, one should already realize the presence of new couplings induced by the background (passive-)superfield components. The assumption that the Lorentz breaking is implemented by means of a constant vector, regarded as a background input, finds its as a Susy-counterpart in a set of requirements on the space-time dependence of each component-field of the background superfield, $`S`$. A scalar field, $`s`$, linearly dependent on $`x^\mu `$, as well as a constant spinor field, $`\psi `$, arise as a consequence of gauge invariance, and these results impose that, eventually, coupling terms are to be regarded as mass terms. A complete analysis of the propagator structure for the gauge supermultiplet, both in superspace and in component-fields, is mandatory, including an interesting study of the gaugino (background-)induced mass. We shall very soon report our efforts in this matter elsewhere.

## V Acknowledgments

The authors are grateful to A.P. Baêta Scarpelli for several discussions. One of the authors, J.L.B., would like to thank CCP/CBPF for the hospitality.


text:
# A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover

## 1 Introduction

A $`k`$-uniform hypergraph $`H=(V,E)`$ consists of a set of vertices $`V`$ and a collection $`E`$ of $`k`$-element subsets of $`V`$ called hyperedges. A vertex cover of $`H`$ is a subset $`SV`$ such that every hyperedge in $`E`$ intersects $`S`$, i.e., $`eS\mathrm{}`$ for each $`eE`$. An independent set in $`G`$ is a subset whose complement is a vertex cover, or in other words a subset of vertices that contains no hyperedge entirely within it. The E$`k`$-Vertex-Cover problem is the problem of finding a minimum size vertex cover in a $`k`$-uniform hypergraph. This problem is alternatively called the minimum hitting set problem with sets of size $`k`$ (and is equivalent to the set cover problem where each element of the universe occurs in exactly $`k`$ sets).

The E$`k`$-Vertex-Cover problem is a fundamental NP-hard optimization problem which arises in numerous settings. For $`k=2`$, it is just the famous vertex cover problem on graphs. Owing to its NP-hardness, one is interested in how well it can be approximated in polynomial time. A very simple algorithm that is invariably taught in a typical undergraduate algorithms class is the following: greedily pick a maximal set of pairwise disjoint hyperedges and then include all vertices in the chosen hyperedges in the vertex cover. It is easy to show that this gives a factor $`k`$ approximation algorithm for E$`k`$-Vertex-Cover. State of the art techniques yield only a tiny improvement, achieving a $`ko(1)`$ approximation ratio . This raises the question whether achieving an approximation factor of $`k\epsilon `$ for any constant $`\epsilon >0`$ could be NP-hard.

In this paper, we prove a nearly tight hardness result for E$`k`$-Vertex-Cover. Specifically, we prove that E$`k`$-Vertex-Cover is indeed NP-hard to approximate within factor $`(k1\epsilon )`$ for any $`\epsilon >0`$, thus explaining why no efficient algorithm with performance guarantee much better than $`k`$ has been found.

### Previous Hardness Results

The vertex-cover problem on hypergraphs where the size of the hyperedges is unbounded is nothing but the Set-Cover problem. For this problem there is a $`\mathrm{ln}n`$ approximation algorithm , and a matching $`(1o(1))\mathrm{ln}n`$ hardness result due to Feige . The first explicit hardness result shown for E$`k`$-Vertex-Cover was due to Trevisan  who considered the approximability of bounded degree instances of several combinatorial problems, and specifically showed an inapproximability factor of $`k^{1/19}`$ for E$`k`$-Vertex-Cover. Holmerin  showed that E$`4`$-Vertex-Cover is NP-hard to approximate within $`(2\epsilon )`$. Independently, Goldreich  showed a direct ‘FGLSS’-type  reduction (involving no use of the long-code, a crucial component in most recent PCP constructions) attaining a hardness factor of $`(2\epsilon )`$ for E$`k`$-Vertex-Cover for some constant $`k`$. Later, Holmerin  showed that E$`k`$-Vertex-Cover is NP-hard to approximate within a factor of $`k^{1\epsilon }`$, and also that it is NP-hard to approximate E$`3`$-Vertex-Cover within factor $`(3/2\epsilon )`$.

Somewhat surprisingly, more recently Dinur, Guruswami and Khot gave a fairly simple proof of an $`\alpha k`$ hardness result for E$`k`$-Vertex-Cover, (for some $`\alpha >\frac{1}{3}`$). The proof takes a combinatorial view of Holmerin’s construction and instead of Fourier analysis uses some properties concerning intersecting families of finite sets. The authors also give a more complicated reduction that shows a factor $`(k3\epsilon )`$ hardness for E$`k`$-Vertex-Cover. The crucial impetus for that work came from the recent result of Dinur and Safra  on the hardness of approximating vertex cover (on graphs), and as in  the notion of biased long codes and some extremal combinatorics relating to intersecting families of sets play an important role. In addition to ideas from , the factor $`(k3\epsilon )`$ hardness result also exploits the notion of covering complexity introduced by Guruswami, Håstad and Sudan . Both the $`\alpha k`$ and the $`k3\epsilon `$ results have not been published (an ECCC manuscript exists, ) since they have been subsumed by the work presented herein.

### Our result and techniques

In this paper we improve upon all the above hardness results by proving a factor $`(k1\epsilon )`$ inapproximability result for E$`k`$-Vertex-Cover. Already for $`k=3`$, this is an improvement from $`1.5\epsilon `$ to $`2\epsilon `$. Extending our result from $`k1\epsilon `$ to $`k\epsilon `$ appears highly non-trivial and in particular would imply a factor $`2\epsilon `$ hardness for vertex-cover on graphs, a problem that is notoriously difficult. While our proof shares some of the extremal combinatorics flavor of  and , it draws its strength mainly from a new multilayered outer verifier system for NP languages. This multilayered system is constructed using the Raz verifier  as a building block.

The Raz verifier, which serves as the starting point or “outer verifier” in most if not all recent hardness results, can be described as follows. There are two sets of (non-Boolean) variables $`Y`$ and $`Z`$, and for certain pairs of $`yY`$ and $`zZ`$, a constraint $`\pi _{yz}`$. The constraints are projections, i.e., for each assignment to $`y`$ there exists exactly one assignment to $`z`$ such that the constraint $`\pi _{yz}`$ is satisfied. The goal is to find an assignment $`A`$ to the variables so that a maximum number of constraints $`\pi _{yz}`$ are satisfied, i.e., have the property $`\pi _{yz}(A(y))=A(z)`$. The PCP Theorem  along with the Parallel Repetition Theorem  imply that for any $`\epsilon >0`$ it is NP-hard to distinguish between the case where all the constraints can be satisfied and the case where no more than a fraction $`\epsilon `$ of the constraints can be satisfied.

In , the $`\alpha k`$ hardness result is obtained by replacing every $`Y`$ variable by a block of vertices (representing its Long-Code). Hyperedges connect $`y_1`$-vertices to $`y_2`$-vertices only if there is some $`zZ`$ such that $`\pi _{y_1z},\pi _{y_2z}`$ are constraints in the system. This construction has an inherent symmetry between blocks which deteriorates the projection property of the constraints, limiting the hardness factor one can prove to at most $`k/2`$.

Another way of reducing the Raz verifier to E$`k`$-Vertex-Cover is by maintaining the asymmetry between $`Y`$ and $`Z`$, introducing a block of vertices for each variable in $`Y`$ and in $`Z`$ (representing their Long-Code). Each constraint $`\pi _{yz}`$ can be emulated by a set of hyperedges, where each hyperedge consists of both $`y`$-vertices and $`z`$-vertices. The hyperedges can be chosen so that if the initial PCP instance was satisfiable, then taking a certain $`1/k`$ of the vertices in each block will be a vertex-cover. However, this reduction has a basic ‘bipartiteness’ flaw: the underlying constraint graph, being bipartite with parts $`Y`$ and $`Z`$, has a vertex cover of size at most one half of the number of vertices. Taking all the vertices of, say, the $`Z`$ variables will be a vertex cover for the hypergraph regardless of whether or not the initial PCP instance was satisfiable. This, once again, limits the gap to no more than $`k/2`$.

We remark that this ‘bipartiteness’ flaw naturally arises in other settings as well. One example is approximate hypergraph coloring, where indeed our multilayered PCP construction has been successfully used for showing hardness, see .

The Multilayered PCP.  We overcome the $`k/2`$ limit by presenting a new, multilayered PCP. In this construction we maintain the projection property of the constraints that is a strong feature of the Raz verifier, while overcoming the ‘bipartiteness’ flaw. In the usual Raz verifier we have two ‘layers’, the first containing the $`Y`$ variables and the second containing the $`Z`$ variables. In the multilayered PCP, we have $`l`$ layers containing variables $`X_1,X_2,\mathrm{},X_l`$ respectively. Between every pair of layers $`i_1`$ and $`i_2`$, we have a set of projection constraints that represent an instance of the Raz verifier. In the multilayered PCP, it is NP-hard to distinguish between (i) the case where there exists an assignment that satisfies all the constraints (between every pair of layers), and (ii) the case where for every $`i_1,i_2`$ it is impossible to satisfy more than a fraction $`\epsilon `$ of the constraints between $`X_{i_1}`$ and $`X_{i_2}`$.

In addition, we prove that the underlying constraint graph no longer has the ‘bipartiteness’ obstacle, i.e. it no longer has a small vertex cover and hence a large independent set. Indeed we show that the multilayered PCP has a certain ‘weak-density’ property: for any set containing an $`\epsilon `$ fraction of the variables there are many constraints between variables of the set. This guarantees that “fake” independent sets in the hypergraph (i.e., independent sets that occur because there are no constraints between the variables of the set) contain at most $`\epsilon `$ of the vertices. Hence, the minimum vertex cover must contain vertices in almost all of the blocks.

We mention that the PCP presented by Feige in  has a few structural similarities with ours. Most notably, both have more than two types of variables. However, while in our construction the types are layered with decreasing domain sizes, in Feige’s construction the different types are all symmetric. Furthermore, and more importantly, the constraints tested by the verifier in Feige’s construction are not projections while this is a key feature of our multilayered PCP, crucially exploited in our analysis.

We view the construction of the multilayered PCP as a central contribution of our paper, and believe that it could be a powerful tool to reduce from in other hardness of approximation results as well. In fact, as mentioned above, our multilayered construction has already been used in obtaining strong hardness results for coloring $`3`$-uniform hypergraphs  (namely the hardness of coloring a $`2`$-colorable $`3`$-uniform hypergraph using an arbitrary constant number of colors), a problem for which no non-trivial inapproximability results are known using other techniques. We anticipate that this new outer verifier will also find other applications besides the ones in this paper and in .

### The Biased Long-Code

Our hypergraph construction relies on the Long-Code that was introduced in , and more specifically, on the biased Long-Code defined in . Thus, each PCP variable is represented by a block of vertices, one for each ‘bit’ of the biased Long-Code. More specifically, in $`x`$’s block we have one vertex for each subset of $`R`$, where $`R`$ is the set of assignments for the variable $`x`$. However, rather than taking all vertices in a block with equal weight, we attach weights to the vertices according to the $`p`$-biased Long-Code. The weight of a subset $`F`$ is set to $`p^{\left|F\right|}(1p)^{\left|RF\right|}`$, highlighting subsets of cardinality $`p\left|R\right|`$. Thus we actually construct a weighted hypergraph which can then be easily translated, by appropriate duplication of vertices, to a non-weighted one (see, e.g., ).

The vertex cover in the hypergraph is shown to have relative size of either $`1p`$ in the good case or almost $`1`$ in the bad case. Choosing large $`p=1\frac{1}{k1\epsilon }`$, yields the desired gap of $`\frac{1}{1p}k1\epsilon `$ between the good and bad cases. The reduction uses the following property: a family of subsets of a set $`R`$, where each subset has size $`p\left|R\right|`$, either contains very few subsets, or it contains some $`k1`$ subsets whose common intersection is very small.  We will later show that this property holds for $`p<1\frac{1}{k1}`$ and therefore we obtain a gap of $`k1\epsilon `$. As can be seen, this property does not hold for $`p>1\frac{1}{k1}`$ and therefore one cannot improve the $`k1\epsilon `$ result by simply increasing $`p`$.

### Location of the gap

All our hardness results have the gap between sizes of the vertex cover at the “strongest” location. Specifically, to prove a factor $`(k1\epsilon )`$ hardness we show that it is hard to distinguish between $`k`$-uniform hypergraphs that have a vertex cover of weight $`\frac{1}{k1}+\epsilon `$ from those whose minimum vertex cover has weight at least $`(1\epsilon )`$. This result is stronger than a gap of about $`(k1)`$ achieved, for example, between vertex covers of weight $`\frac{1}{(k1)^2}`$ and $`\frac{1}{k1}`$. In fact, by adding dummy vertices, our result implies that for any $`c<1`$ it is NP-hard to distinguish between hypergraphs whose minimum vertex-cover has weight at least $`c`$ from those which have a vertex-cover of weight at most $`\left(\frac{c}{k1}+\epsilon \right)`$. Put another way, our result shows that for $`k`$-uniform hypergraphs, for $`k3`$, there is a fixed $`\alpha `$ such that for arbitrarily small $`\epsilon >0`$, it is NP-hard to find an independent set consisting of a fraction $`\epsilon `$ of the vertices even if the hypergraph is promised to contain an independent set comprising a fraction $`\alpha `$ of vertices. We remark that such a result is not known for graphs and seems out of reach of current techniques. (The recent $`1.36`$ hardness result for vertex cover on graphs due to Dinur and Safra , for example, shows that it is NP-hard to distinguish between cases when the graph has an independent set of size $`0.38n`$ and when no independent set has more than $`0.16n`$ vertices.)

### Organization

We begin in Section 2 by developing the machinery from extremal combinatorics concerning intersecting families of sets that will play a crucial role in our proof. In Section 3 we present the multilayered PCP construction. In Section 4 we present our reduction to a gap version of E$`k`$-Vertex-Cover which allows us to prove a factor $`(k1\epsilon )`$ inapproximability result for this problem.

## 2 Intersecting Families

In this section we describe certain properties of $`s`$-wise $`t`$-intersecting families. For a comprehensive survey, see . Denote $`[n]=\{0,1,\mathrm{},n1\}`$ and $`2^{[n]}=\left\{F\right|F[n]\}`$.

###### Definition 2.1

A family $`2^{[n]}`$ is called $`s`$-wise $`t`$-intersecting if for every $`s`$ sets $`F_1,\mathrm{},F_s`$, we have

$$|F_1\mathrm{}F_s|t.$$

We are interested in bounding the size of such families, and for this purpose it is useful to introduce the notion of a left-shifted family. Performing an $`(i,j)`$-shift on a family consists of replacing the element $`j`$ with the element $`i`$ in all sets $`F`$ such that $`jF`$, $`iF`$ and $`(F\{j\})\{i\}`$. A left-shifted family is a family which is invariant with respect to $`(i,j)`$-shifts for any $`1i<jn`$. For any family $``$, by iterating the $`(i,j)`$-shift for all $`1i<jn`$ we eventually get a left-shifted family which we denote by $`S()`$. The following simple lemma summarizes the properties of the left-shift operation (see, e.g., , p. 1298, Lemma 4.2):

###### Lemma 2.2

For any family $`2^{[n]}`$, there exists a one-to-one and onto mapping $`\tau `$ from $``$ to $`S()`$ such that $`|F|=|\tau (F)|`$ for every $`F`$. In other words, left-shifting a family maintains its size and the size of the sets in the family. Moreover, if $``$ is an $`s`$-wise $`t`$-intersecting family then so is $`S()`$.

The next lemma states that a subset $`F`$ in a left-shifted $`s`$-wise $`t`$-intersecting family, cannot be ‘sparse’ on all of its prefixes $`F[t+js],j0`$.

###### Lemma 2.3 (, p. 1311, Lemma 8.3)

Let $``$ be a left-shifted $`s`$-wise $`t`$-intersecting family. Then, for every $`F`$, there exists a $`j0`$ with $`|F[t+sj]|t+(s1)j`$.

###### Definition 2.4

For a bias parameter $`0<p<1`$, and a ground set $`R`$, the weight of a set $`FR`$ is

$$\mu _p^R(F)\stackrel{def}{=}p^{|F|}(1p)^{|RF|}$$

When $`R`$ is clear from the context we write $`\mu _p`$ for $`\mu _p^R`$. The weight of a family $`2^R`$ is $`\mu _p()=_F\mu _p(F)`$.

The weight of a subset is precisely the probability of obtaining this subset when one picks every element in $`R`$ independently with probability $`p`$.

The following is the main lemma of this section. It shows that for any $`p<\frac{s1}{s}`$, a family of non-negligible $`\mu _p`$-weight (i.e., $`\mu _p()\epsilon `$) cannot be $`s`$-wise $`t`$-intersecting for sufficiently large $`t`$.

###### Lemma 2.5

For any $`\epsilon ,s,p`$ with $`p<\frac{s1}{s}`$, there exists a $`t=t(\epsilon ,s,p)`$ such that for any $`s`$-wise $`t`$-intersecting family $`2^{[n]}`$, $`\mu _p()<\epsilon `$.

#### Proof:

The proof follows from Lemma 2.3 (see , p. 1311, Theorem 8.4). Let $``$ be an $`s`$-wise $`t`$-intersecting family where $`t`$ will be determined later. According to Lemma 2.2, $`S()`$ is also $`s`$-wise $`t`$-intersecting and $`\mu _p(S())=\mu _p()`$. By Lemma 2.3, for every $`FS()`$, there exists a $`j0`$ such that $`|F[t+sj]|t+(s1)j`$. We can therefore bound $`\mu _p(S())`$ from above by the probability that such a $`j`$ exists for a random set chosen according to the distribution $`\mu _p`$. We now prove an upper bound on this probability, which will give the desired bound on $`\mu _p(S())`$ and hence also on $`\mu _p()`$.

Let $`\delta =\frac{s1}{s}p`$. Then, for any $`j0`$, $`\text{Pr}[|F[t+sj]|t+(s1)j]`$ is at most

$$\text{Pr}[|F[t+sj]|p(t+sj)\delta (t+sj)]e^{2(t+sj)\delta ^2}.$$

by the Chernoff bound . Summing over all $`j0`$ we get:

$$\mu _p(S())\underset{j0}{}e^{2(t+sj)\delta ^2}=e^{2t\delta ^2}/(1e^{2s\delta ^2})$$

which is smaller than $`\epsilon `$ for large enough $`t`$.

## 3 The Multilayered PCP

### 3.1 Starting Point - The PCP Theorem and the Parallel Repetition Theorem

As is the case with many inapproximability results (e.g., , , , ), we begin our reduction from the Raz verifier described next. Let $`\mathrm{\Psi }`$ be a collection of two-variable constraints, where the variables are of two types, denoted $`Y`$ and $`Z`$. Let $`R_Y`$ denote the range of the $`Y`$-variables and $`R_Z`$ the range of the $`Z`$-variables, where $`\left|R_Z\right|\left|R_Y\right|`$333Readers familiar with the Raz verifier may prefer to think concretely of $`R_Y=[7^u]`$ and $`R_Z=[2^u]`$ for some number $`u`$ of repetitions.. Assume each constraint $`\pi \mathrm{\Psi }`$ depends on exactly one $`yY`$ and one $`zZ`$, furthermore, for every value $`a_yR_Y`$ assigned to $`y`$ there is exactly one value $`a_zR_Z`$ to $`z`$ such that the constraint $`\pi `$ is satisfied. Therefore, we can write each constraint $`\pi \mathrm{\Psi }`$ as a function from $`R_Y`$ to $`R_Z`$, and use notation $`\pi _{yz}:R_YR_Z`$. Furthermore, we assume that the underlying constraint graph is bi-regular, i.e., every $`Y`$-variable appears in the same number of constraints in $`\mathrm{\Psi }`$, and every $`Z`$-variable appears in the same number of constraints in $`\mathrm{\Psi }`$.

The following theorem follows by combining the PCP Theorem with Raz’s Parallel Repetition Theorem. The PCP given by this theorem will be called the Raz’s verifier henceforth.

###### Theorem 3.1

(PCP Theorem  \+ Raz’s Parallel Repetition Theorem ) Let $`\mathrm{\Psi }`$ be as above. There exists a universal constant $`\gamma >0`$ such that for every (large enough) constant $`\left|R_Y\right|`$ it is NP-hard to distinguish between the following two cases:

* Yes :  There is an assignment $`A:YR_Y`$, $`A:ZR_Z`$ such that all $`\pi \mathrm{\Psi }`$ are satisfied by $`A`$, i.e., $`\pi _{yz}\mathrm{\Psi },\pi _{yz}(A(y))=A(z)`$.
* No :  No assignment can satisfy more than a fraction $`\frac{1}{\left|R_Y\right|^\gamma }`$ of the constraints in $`\mathrm{\Psi }`$.

As discussed in the introduction, a natural approach to build a hypergraph from the PCP $`\mathrm{\Psi }`$ is to have a block of vertices for every variable $`y`$ or $`z`$ and define hyperedges of the hypergraph so as to enforce the constraints $`\pi _{yz}`$. For every constraint $`\pi _{yz}`$, there will be hyperedges containing vertices from the block of $`y`$ and the block of $`z`$. However, this approach is limited by the fact that the constraint graph underlying the PCP has a small vertex cover. Since each hyperedge contains vertices from both the $`Y`$ and $`Z`$ ‘sides’, the subset of all vertices on the $`Y`$ (resp. $`Z`$) ‘side’, already covers all of the hyperedges regardless of whether the initial PCP system was satisfiable or not.444Adding hyperedges entirely within vertices on the $`Y`$ and $`Z`$ sides cannot help either since we wish to ensure a small vertex cover in the completeness case. Hence picking all vertices on, say, the $`Z`$ side, together with the small vertex cover that hits all edges entirely within the $`Y`$ side (such a small cover must exist due to the completeness case) will again give a vertex cover of weight close to $`1/2`$.

This difficulty motivates our construction of a multilayered PCP where we have many types of variables (rather than only $`Y`$ and $`Z`$) and the resulting hypergraph is multipartite. The multilayered PCP is able to maintain the properties of Theorem 3.1 between every pair of layers. Moreover, the underlying constraint graph has a special ‘weak-density’ property that roughly guarantees it will have only tiny independent sets (thus any vertex cover for it must contain almost all of the vertices).

### 3.2 Layering the Variables

Let $`l,R>0`$. Let us begin by defining an $`l`$-layered PCP. In an $`l`$-layered PCP there are $`l`$ sets of variables denoted by $`X_1,\mathrm{},X_l`$. The range of variables in $`X_i`$ is denoted $`R_i`$, with $`\left|R_i\right|=R^{O(l)}`$. For every $`1i<jl`$ there is a set of constraints $`\mathrm{\Phi }_{ij}`$ where each constraint $`\pi \mathrm{\Phi }_{ij}`$ depends on exactly one $`xX_i`$ and one $`x^{}X_j`$. For any two variables we denote by $`\pi _{xx^{}}`$ the constraint between them if such a constraint exists. Moreover, the constraints in $`\mathrm{\Phi }_{ij}`$ are projections from $`x`$ to $`x^{}`$, that is, for every assignment to $`x`$ there is exactly one assignment to $`x^{}`$ such that the constraint is satisfied.

In addition, as mentioned in the introduction, we would like to show a certain ‘weak-density’ property of our multilayered PCP:

###### Definition 3.2

An $`l`$-layered PCP is said to be weakly-dense if for any $`\delta >0`$, given $`m\frac{2}{\delta }`$ layers $`i_1<\mathrm{}<i_m`$ and given any sets $`S_jX_{i_j}`$ for $`j[m]`$ such that $`S_j\delta |X_{i_j}|`$, there always exist two sets $`S_j`$ and $`S_j^{}`$ such that the number of constraints between them is at least a $`\frac{\delta ^2}{4}`$ fraction of the constraints between the layers $`X_{i_j}`$ and $`X_{i_j^{}}`$.

###### Theorem 3.3

There exists a universal constant $`\gamma >0`$, such that for any parameters $`l,R`$, there is a weakly-dense $`l`$-layered PCP $`\mathrm{\Phi }_{ij}`$ such that it is NP-hard to distinguish between the following two cases:

* Yes :  There exists an assignment that satisfies all the constraints.
* No :  For every $`i<j`$, not more than $`1/R^\gamma `$ of the constraints in $`\mathrm{\Phi }_{ij}`$ can be satisfied by an assignment.

#### Proof:

Let $`\mathrm{\Psi }`$ be a constraint-system as in Theorem 3.1. We construct $`\mathrm{\Phi }=\mathrm{\Phi }_{ij}`$ as follows. The variables $`X_i`$ of layer $`i[l]`$ are the elements of the set $`Z^i\times Y^{li}`$, i.e., all $`l`$-tuples where the first $`i`$ elements are $`Z`$ variables and the last $`li`$ elements are $`Y`$ variables. The variables in layer $`i`$ have assignments from the set $`R_i=(R_Z)^i\times (R_Y)^{li}`$ corresponding to an assignment to each variable of $`\mathrm{\Psi }`$ in the $`l`$-tuple. It is easy to see that $`|R_i|R^{O(l)}`$ for any $`i[l]`$ and that the total number of variables is no more than $`\left|\mathrm{\Psi }\right|^{O(l)}`$. For any $`1i<jl`$ we define the constraints in $`\mathrm{\Phi }_{ij}`$ as follows. A constraint exists between a variable $`x_iX_i`$ and a variable $`x_jX_j`$ if they contain the same $`\mathrm{\Psi }`$ variables in the first $`i`$ and the last $`lj`$ elements of their $`l`$-tuples. Moreover, for any $`i<kj`$ there should be a constraint in $`\mathrm{\Psi }`$ between $`x_{i,k}`$ and $`x_{j,k}`$. More formally, denoting $`x_i=(x_{i,1},\mathrm{},x_{i,l})`$ for $`x_iX_i=Z^i\times Y^{li}`$,

$`\mathrm{\Phi }_{ij}`$ $`=`$ $`\{\pi _{x_i,x_j}x_iX_i,x_jX_j,`$
$`k[l]\{i+1,\mathrm{},j\},x_{i,k}=x_{j,k}`$
$`k\{i+1,\mathrm{},j\},\pi _{x_{i,k}x_{j,k}}\mathrm{\Psi }\}.`$
As promised, the constraints $`\pi _{x_{i,k}x_{j,k}}`$ are projections. Given an assignment $`a=(a_1,..,a_l)R_i`$ to $`x_i`$, we define the consistent assignment $`b=(b_1,..,b_l)R_j`$ to $`x_j`$ as $`b_k=\pi _{x_{i,k}x_{j,k}}(a_k)`$ for $`k\{i+1,\mathrm{},j\}`$ and $`b_k=a_k`$ for all other $`k`$.

The completeness of $`\mathrm{\Phi }`$ follows easily from the completeness of $`\mathrm{\Psi }`$. That is, assume we are given an assignment $`A:YZR_YR_Z`$ that satisfies all the constraints of $`\mathrm{\Psi }`$. Then, the assignment $`B:X_iR_i`$ defined by $`B(x_1\mathrm{}x_l)=(A(x_1)\mathrm{}A(x_l))`$ is a satisfying assignment.

For the soundness part, assume that there exist two layers $`i<j`$ and an assignment $`B`$ that satisfies more than a $`1/R^\gamma `$ fraction of the constraints in $`\mathrm{\Phi }_{ij}`$. We partition $`X_i`$ into classes such that two variables in $`X_i`$ are in the same class iff they are identical except possibly on coordinate $`j`$. The variables in $`X_j`$ are also partitioned according to coordinate $`j`$. Since more than $`1/R^\gamma `$ of the constraints in $`\mathrm{\Phi }_{ij}`$ are satisfied, it must be the case that there exist a class $`x_{i,1},\mathrm{},x_{i,j1},x_{i,j+1},\mathrm{},x_{i,l}`$ in the partition of $`X_i`$ and a class $`x_{j,1},\mathrm{},x_{j,j1},x_{j,j+1},\mathrm{},x_{j,l}`$ in the partition of $`X_j`$ between which there exist constraints and the fraction of satisfied constraints is more than $`1/R^\gamma `$. We define an assignment to $`\mathrm{\Psi }`$ as

$$A(y)=(B(x_{i,1},\mathrm{},x_{i,j1},y,x_{i,j+1},\mathrm{},x_{i,l}))_j$$

for $`yY`$ and as

$$A(z)=(B(x_{j,1},\mathrm{},x_{j,j1},z,x_{j,j+1},\mathrm{},x_{j,l}))_j$$

for $`zZ`$. Notice that there is a one-to-one and onto correspondence between the constraints in $`\mathrm{\Psi }`$ and the constraints between the two chosen classes in $`\mathrm{\Phi }`$. Moreover, if the constraint in $`\mathrm{\Phi }`$ is satisfied, then the constraint in $`\mathrm{\Psi }`$ is also satisfied. Therefore, $`A`$ is an assignment to $`\mathrm{\Psi }`$ that satisfies more than $`1/R^\gamma `$ of the constraints.

To prove that this multilayered PCP is weakly-dense, we recall the bi-regularity property mentioned above, i.e., each variable $`yY`$ appears in the same number of constraints and also each $`zZ`$ appears in the same number of constraints. Therefore, the distribution obtained by uniformly choosing a variable $`yY`$ and then uniformly choosing one of the variables in $`zZ`$ with which it has a constraint is a uniform distribution on $`Z`$.

Take any $`m=\frac{2}{\delta }`$ layers $`i_1<\mathrm{}<i_m`$ and sets $`S_jX_{i_j}`$ for $`j[m]`$ such that $`S_j\delta |X_{i_j}|`$. Consider a random walk beginning from a uniformly chosen variable $`x_1X_1`$ and proceeding to a variable $`x_2X_2`$ chosen uniformly among the variables with which $`x_1`$ has a constraint. The random walk continues in a similar way to a variable $`x_3X_3`$ chosen uniformly among the variables with which $`x_2`$ has a constraint and so on up to a variable in $`X_l`$. Denote by $`E_j`$ the indicator variable of the event that the random walk hits an $`S_j`$ variable when in layer $`X_{i_j}`$. From the uniformity of $`\mathrm{\Psi }`$ it follows that for every $`j`$, $`\text{Pr}[E_j]\delta `$. Moreover, using the inclusion-exclusion principle, we get:

$`1\text{Pr}[{\displaystyle E_j}]{\displaystyle \underset{j}{}}\text{Pr}[E_j]{\displaystyle \underset{j<k}{}}\text{Pr}[E_jE_k]`$
$`{\displaystyle \frac{2}{\delta }}\delta \left({\displaystyle \genfrac{}{}{0pt}{}{m}{2}}\right)\text{max}_{j<k}\text{Pr}[E_jE_k]`$
$`2\left({\displaystyle \genfrac{}{}{0pt}{}{m}{2}}\right)\text{max}_{j<k}\text{Pr}[E_jE_k]`$
which implies

$$\text{max}_{j<k}\text{Pr}[E_jE_k]1/\left(\genfrac{}{}{0pt}{}{m}{2}\right)\frac{\delta ^2}{4}$$

Fix $`j`$ and $`k`$ such that $`\text{Pr}[E_jE_k]\frac{\delta ^2}{4}`$ and consider a shorter random walk beginning from a random variable in $`X_{i_j}`$ and proceeding to the next layer and so on until hitting layer $`i_k`$. Since $`E_j`$ is uniform on $`X_{i_j}`$ we still have that $`\text{Pr}[E_jE_k]\frac{\delta ^2}{4}`$ where the probability is taken over the random walks between $`X_{i_j}`$ and $`X_{i_k}`$. Also, notice that there is a one-to-one and onto mapping from the set of all random walks between $`X_{i_j}`$ and $`X_{i_k}`$ to the set $`\mathrm{\Phi }_{i_j,i_k}`$. Therefore, at least a fraction $`\frac{\delta ^2}{4}`$ of the constraints between $`X_{i_j}`$ and $`X_{i_k}`$ are between $`S_j`$ and $`S_k`$, which completes the proof of the weak-density property.

## 4 The Hypergraph Construction

###### Theorem 4.1 (Main Theorem)

For any $`k3`$ it is NP-hard to approximate the vertex-cover on a $`k`$-uniform hypergraph within any constant factor less than $`k1`$.

#### Proof:

Fix $`k3`$ and arbitrarily small $`\epsilon >0`$. Define $`p=1\frac{1}{k1\epsilon }`$. Let $`\mathrm{\Phi }`$ be a PCP instance with layers $`X_1,\mathrm{},X_l`$, as described in Theorem 3.3, with parameters $`l=32\epsilon ^2`$ and $`R`$ large enough to be chosen later. We present a construction of a $`k`$-uniform hypergraph $`G=(V,E)`$. We use the Long Code introduced by Bellare et al. . A Long Code over domain $`R`$ has one bit for every subset $`vR`$. An encoding of element $`xR`$ assigns bit-value $`1`$ to the sets $`v`$ s.t. $`xv`$ and assigns $`0`$ to the sets which do not contain $`x`$. In the following, the bits in the Long Code will be vertices of the hypergraph. The vertices that correspond to a bit-value $`0`$ are (supposedly) the vertices of a Vertex Cover.

Vertices. For each variable $`x`$ in layer $`X_i`$ we construct a block of vertices $`V[x]`$. This block contains a vertex for each subset of $`R_i`$. Throughout this section we slightly abuse notation by writing a vertex rather than the set it represents. The weight of the vertices inside the block $`V[x]`$ is according to $`\mu _p^{R_i}`$, i.e. the weight of a subset $`vR_i`$ is proportional to $`\mu _p^{R_i}(v)=p^{\left|v\right|}(1p)^{\left|R_iv\right|}`$ as in Definition 2.4. All blocks in the same layer have the same total weight and the total weight of each layer is $`\frac{1}{l}`$. Formally, the weight of a vertex $`vV[x]`$ where $`xX_i`$ is given by

$$\frac{1}{l|X_i|}\mu _p^{R_i}(v).$$

Hyperedges. We construct hyperedges between blocks $`V[x]`$ and $`V[y]`$ such that there exists a constraint $`\pi _{xy}`$. We connect a hyperedge between any $`v_1,\mathrm{},v_{k1}V[x]`$ and $`uV[y]`$ whenever $`\pi _{xy}(_{i=1}^{k1}v_i)u=\varphi `$.

Let $`IS(G)`$ denote the weight of vertices contained in the largest independent set of the hypergraph $`G`$.

###### Lemma 4.2 (Completeness)

If $`\mathrm{\Phi }`$ is satisfiable then $`IS(G)p`$.

#### Proof:

Let $`A`$ be a satisfying assignment for $`\mathrm{\Phi }`$, i.e., $`A`$ maps each $`i[l]`$ and $`xX_i`$ to an assignment in $`R_i`$ such that all the constraints are satisfied. Let $`V`$ contain in the block $`V[x]`$ all the vertices that contain the assignment $`A(x)`$,

$$=\underset{x}{}\left\{vV[x]\right|vA(x)\}.$$

We claim that $``$ is an independent set. Take any $`v_1,\mathrm{},v_{k1}`$ in $`V[x]`$ and a vertex $`u`$ in $`V[y]`$. The vertices $`v_1,\mathrm{},v_{k1}`$ intersect on $`A(x)`$ and therefore the projection of their intersection contains $`\pi _{xy}(A(x))=A(y)`$. Since $`u`$ is in $`V[y]`$ it must contain $`A(y)`$. The proof is completed by noting that inside each block, the weight of the set of all vertices that contain a specific assignment is exactly $`p`$.

We now turn to the soundness of the construction.

###### Lemma 4.3 (Soundness)

If $`IS(G)\epsilon `$ then $`\mathrm{\Phi }`$ is satisfiable.

This lemma completes the proof of our main result since the ratio between the sizes of the vertex cover in the yes and no cases is $`\frac{1\epsilon }{1p}=(1\epsilon )(k1\epsilon )`$ which can be arbitrarily close to $`k1`$.

#### Proof:

Let $``$ be an independent set of weight $`\epsilon `$. We consider the set $`X^{}`$ of all variables $`x`$ for which the weight of $`V[x]`$ in $`V[x]`$ is at least $`\epsilon /2`$. A simple averaging argument shows that the weight of $`_{xX^{}}V[x]`$ is at least $`\frac{\epsilon }{2}`$. Another averaging argument shows that in at least $`\frac{\epsilon }{4}l=\frac{8}{\epsilon }`$ layers, $`X^{}`$ contains at least $`\frac{\epsilon }{4}`$ fraction of the variables. Using the weak-density property of the PCP (see Definition 3.2), we conclude that there exist two layers $`X_i`$ and $`X_j`$ such that $`\frac{\epsilon ^2}{64}`$ fraction of the constraints between them are constraints between variables in $`X^{}`$. Let us denote by $`X`$ the variables in $`X_iX^{}`$ and by $`Y`$ the variables in $`X_jX^{}`$.

For any variable $`xX`$, consider the vertices in $`V[x]`$. According to Lemma 2.5 there exists a $`t=t(\frac{\epsilon }{2},k1,p)`$ and $`k1`$ vertices in $`V[x]`$ that intersect in less than $`t`$ assignments. We denote these vertices by $`v_{x,1},\mathrm{},v_{x,k1}`$ and their intersection by $`B(x)`$.

In the following we define an assignment to the variables in $`X`$ and $`Y`$ such that many of the constraints between them are satisfied. Then Theorem 3.3 would imply that $`\mathrm{\Phi }`$ must be satisfiable (provided $`R`$ is chosen large enough). For a variable $`xX`$ we choose a random assignment from the set $`B(x)`$. For a variable $`yY`$ we choose the assignment

$$A(y)=\text{maxvar}_{aR_Y}|\{xX|a\pi _{xy}(B(x))\}|,$$

i.e., the assignment that is contained in the largest number of projections of $`B(x)`$.

Before continuing, we need the following simple claim:

###### Claim 4.4

Let $`A_1,\mathrm{},A_n`$ be a collection of $`n`$ sets of size at most $`m`$ such that no element is contained in more than $`k`$ sets. Then, there are at least $`\frac{n}{1+(k1)m}\frac{n}{km}`$ disjoint sets in this collection.

#### Proof:

We prove by induction on $`n`$ that there are at least $`\frac{n}{1+(k1)m}`$ disjoint sets in the collection. The claim holds trivially for $`n1+(k1)m`$. Otherwise, consider all the sets that intersect $`A_1`$. Since no element is contained in more than $`k`$ sets, the number of such sets (including $`A_1`$) is at most $`1+(k1)m`$. Removing these sets we get, by using the induction hypothesis, a collection that contains $`\frac{n1(k1)m}{1+(k1)m}=\frac{n}{1+(k1)m}1`$ disjoint sets. We conclude the induction step by adding $`A_1`$ to the disjoint sets.

Consider a variable $`yY`$ and a variable $`x`$ such that the constraint $`\pi _{xy}`$ exists. There are no hyperedges of the form $`(v_{x,1},\mathrm{},v_{x,k1},u)`$ for any vertex $`uV[y]`$. Therefore, every vertex $`uV[y]`$ must intersect $`\pi _{xy}(B(x))`$. Now consider the family of projections $`\pi _{xy}(B(x))`$ for all the variables $`x`$ such that the constraint $`\pi _{xy}`$ exists. Let $`q`$ denote the maximum number of disjoint sets inside this family. Note that every disjoint set reduces the weight of the vertices in $`V[y]`$ by a factor of $`1(1p)^t`$. Because the weight of $`V[y]`$ is at least $`\frac{\epsilon }{4}`$, we obtain that $`q`$ is at most $`\mathrm{log}(\frac{\epsilon }{4})/\mathrm{log}(1(1p)^t)`$. Claim 4.4 implies that there exists an assignment for $`y`$ that is contained in at least a fraction

$$\frac{1}{t\mathrm{log}(\frac{\epsilon }{4})/\mathrm{log}(1(1p)^t)}$$

of the projections $`\pi _{xy}(B(x))`$. Therefore, the expected fraction of constraints satisfied between $`X`$ and $`Y`$ is at least

$$\frac{1}{t^2\mathrm{log}(\frac{\epsilon }{4})/\mathrm{log}(1(1p)^t)}$$

which is a constant that does not depend on $`R`$. We complete the proof by choosing the range $`R`$ of the PCP large enough so that this fraction is larger than $`1/R^\gamma `$ and applying Theorem 3.3. This completes the soundness proof.

## 5 Acknowledgements

We would like to thank Noga Alon for his help with $`s`$-wise $`t`$-intersecting families.