text:
# Projectivities in Simplicial Complexes and Colorings of Simple Polytopes

## 1 Introduction

In  Davis and Januszkiewicz introduce an $`(n+d)`$-dimensional smooth manifold $`𝒵_P`$ built from a $`d`$-dimensional simple convex polytope $`P`$ with $`n`$ facets. These manifolds play a significant role in the study of (quasi-)toric manifolds. We briefly sketch the construction. Let $`P`$ be a simple $`d`$-polytope with $`n`$ facets. Fix an ordering of the facets $`=(F_1,\mathrm{},F_n)`$ and let $`T`$ be the $`n`$-dimensional complex algebraic torus $`(\{0\})^{}`$. On the product $`P\times T`$ define an equivalence relation $``$, where $`(p,s)(q,t)`$ if and only if $`p=q`$ and the $`i`$-th component of the quotient $`st^1`$ in the group $`T`$ is trivial for all facets $`F_i`$ not containing the point $`p=q`$. We obtain a manifold $`𝒵_P`$ as the quotient space $`(P\times T)/`$. For a survey on the subject see Buchstaber and Panov , where the construction of the manifold $`𝒵_P`$ is discussed in Section 3.1. The obvious action of the torus $`T`$ on $`𝒵_P`$ is free over the interior of $`P`$. Points which are contained in the relative interior of a $`k`$-dimensional face have a $`(dk)`$-dimensional isotropy group. In particular, the isotropy group of each vertex has dimension $`d`$. Buchstaber suggested to study quotients of $`𝒵_P`$ by freely acting subgroups of $`T`$, see \[4, Section 4.4\]. In this context he defines $`s(P)`$ as the maximal dimension of a subgroup of $`T`$ which acts freely on $`𝒵_P`$. Izmestiev  defines the chromatic number $`\gamma (P)`$ of $`P`$ as the minimal number of colors required to color the facets of $`P`$ such that any two facets sharing a vertex have distinct colors. He shows that $`s(P)n\gamma (P)`$, see \[4, 4.4.5\], whereas it is clear that $`s(P)nd`$, see \[4, 4.4.2\].

From our main result (Theorem 3.2), which is a statement on combinatorial manifolds, we infer a combinatorial characterization for the simple $`d`$-polytopes with $`\gamma (P)=d`$. The aforementioned results imply that for such polytopes we have $`s(P)=nd`$. This gives a partial answer to Problem 4.4.1 in . The case $`s(P)=nd`$ seems to be the most interesting one in this context. The result for simple $`3`$-polytopes is classical. The result for the special case of simple zonotopes is implicit in \[7, Lemma 4.2.6\] of Davis, Januszkiewicz, and Scott. Moreover, since the original submission of this paper I learned that Edwards  had announced a solution to the coloring problem already in 1977. However, to the best of my knowledge, no proof was published.

The paper is organized as follows. We start by associating a finite group to each facet of a finite-dimensional simplicial complex, the *group of projectivities*. For strongly connected complexes the isomorphism class of the group does not depend on the facet chosen. In the next section we investigate the groups of projectivities of combinatorial manifolds. It turns out that, in order to determine the group of projectivities, it suffices to have combinatorial information about the fundamental group plus local combinatorial data. This result is then specialized to the case of simplicial spheres which arise as boundaries of convex polytopes. A polytope is simple if and only if the boundary of its dual is a simplicial sphere. Hence we can apply our results on combinatorial manifolds to any simple polytope $`P`$. This way we obtain the desired result: $`\gamma (P)=d`$ if and only if each $`2`$-face of $`P`$ has an even number of vertices. We conclude the paper with a few remarks and a short appendix on how our results are related to known results in graph theory.

I am indebted to Ivan Izmestiev and Friederike Körner for stimulating discussions on the subject. Thanks to Carsten Lange, Julian Pfeifle, and Günter M. Ziegler for giving helpful comments on a previous version of this paper. Moreover, I am grateful to the anonymous referee for bringing to my attention the paper of Davis, Januszkiewicz, and Scott .

## 2 Simplicial Complexes

An *(abstract) simplicial complex* on the vertex set $`V`$ is a non-empty collection $`\mathrm{\Delta }`$ of finite subsets of $`V`$, which is closed with respect to forming subsets. If $`\sigma \mathrm{\Delta }`$ with $`\mathrm{\#}\sigma =k+1`$, we say that the *simplex* $`\sigma `$ has *dimension* $`k`$, and we write $`dim\sigma =k`$. Define $`dim\mathrm{\Delta }=sup\left\{dim\sigma \right|\sigma \mathrm{\Delta }\}`$. Throughout the rest of the paper we always assume that $`dim\mathrm{\Delta }<\mathrm{}`$. A simplex of $`\mathrm{\Delta }`$ which is maximal with respect to inclusion is called a *facet*. If a simplex $`\sigma `$ is contained in another simplex $`\tau `$, then $`\sigma `$ is a *face* of $`\tau `$. The complex $`\mathrm{\Delta }`$ is called *pure* if all its facets have the same dimension. The maximal proper faces of the facets are the *ridges*. For a given face $`\sigma \mathrm{\Delta }`$, the *(closed) star* $`\mathrm{st}\sigma `$ is the subcomplex generated by the facets containing $`\sigma `$, whereas the *link* $`\mathrm{lk}\sigma `$ is the subcomplex of $`\mathrm{st}\sigma `$ of faces not containing $`\sigma `$.

By introducing barycentric coordinates on the simplices and extending according to the concept of weak topology, every finite-dimensional simplicial complex $`\mathrm{\Delta }`$ defines a locally compact and metrizable Hausdorff space $`\mathrm{\Delta }`$, which is compact if and only if $`\mathrm{\Delta }`$ is finite; see any topology textbook, e.g. Munkres , for the details. We frequently apply notions from topology to $`\mathrm{\Delta }`$ which, if no confusion can arise, are meant to refer to $`\mathrm{\Delta }`$.

The *dual graph* $`\mathrm{\Gamma }(\mathrm{\Delta })`$ of $`\mathrm{\Delta }`$ is an abstract graph whose nodes are the facets of $`\mathrm{\Delta }`$, and where an edge between two facets corresponds to a common ridge. We call $`\mathrm{\Delta }`$ *strongly connected* if the graph $`\mathrm{\Gamma }(\mathrm{\Delta })`$ is connected. Strong connectedness clearly implies connectedness in the topological sense. Moreover, if $`\mathrm{\Delta }`$ is strongly connected, then $`\mathrm{\Delta }`$ is pure. However, our definition of the dual graph also makes sense for non-pure complexes. In the non-pure case each connected component of the dual graph consists of facets of the same dimension.

For each ridge $`\rho `$ contained in two facets $`\sigma `$, $`\tau `$, there is a unique vertex $`v(\sigma ,\tau )`$ which is contained in $`\sigma `$ but not in $`\tau `$. We define the *perspectivity* $`\sigma ,\tau :\sigma \tau `$ by setting

$$w\{\begin{array}{cc}v(\tau ,\sigma )& \text{if }w=v(\sigma ,\tau ),\hfill \\ w& \text{otherwise.}\hfill \end{array}$$

Let $`g=(\sigma _0,\sigma _1,\mathrm{},\sigma _n)`$ be a *facet path* in $`\mathrm{\Gamma }(\mathrm{\Delta })`$, that is, for each each $`i`$ the facets $`\sigma _i`$ and $`\sigma _{i+1}`$ share a common ridge. The *projectivity* $`g`$ from $`\sigma _1`$ to $`\sigma _n`$ along $`g`$ is the concatenation

$$g=\sigma _0,\sigma _1,\mathrm{},\sigma _n=\sigma _0,\sigma _1\sigma _1,\sigma _2\mathrm{}\sigma _{n1},\sigma _n$$

of perspectivities. The map $`g`$ is a bijection from $`\sigma _0`$ to $`\sigma _n`$. The facet path $`g`$ is *closed* if $`\sigma _0=\sigma _n`$. A closed facet path from $`\sigma _0`$ to $`\sigma _0`$ is called a *facet loop* based at $`\sigma _0`$. We denote the concatenation of two facet paths $`g=(\sigma _0,\sigma _1,\mathrm{},\sigma _n)`$ and $`h=(\sigma _n,\sigma _{n+1},\mathrm{},\sigma _m)`$ by $`gh`$. Clearly, $`gh=gh`$.

For a given facet $`\sigma _0`$ the set of projectivities along facet loops based at $`\sigma _0`$ forms a group $`\mathrm{\Pi }(\mathrm{\Delta },\sigma _0)`$, the *group of projectivities* of $`\mathrm{\Delta }`$ at $`\sigma _0`$. The group of projectivities is a (permutation) subgroup of the symmetric group $`\mathrm{Sym}\sigma _0`$, the group of all bijections on the set of vertices of $`\sigma _0`$. The inverse of the facet path $`g`$ is denoted by $`g^{}`$.

###### Lemma 2.1

Let $`g`$ be a facet path from the facet $`\sigma _0`$ to the facet $`\sigma _1`$. Then $`\mathrm{\Pi }(\mathrm{\Delta },\sigma _0)=g\mathrm{\Pi }(\mathrm{\Delta },\sigma _1)g^{}`$.

This implies that for strongly connected $`\mathrm{\Delta }`$ the isomorphism class of $`\mathrm{\Pi }(\mathrm{\Delta },\sigma )`$ does not depend on the choice of the *base facet* $`\sigma _0`$. We write $`\mathrm{\Pi }(\mathrm{\Delta })`$ and call it the *group of projectivities* of $`\mathrm{\Delta }`$. In this case the group of projectivities is a combinatorial invariant of $`\mathrm{\Delta }`$.

Let $`\mathrm{\Delta }`$ and $`\mathrm{\Delta }^{}`$ be finite-dimensional simplicial complexes and let $`f:\mathrm{\Delta }\mathrm{\Delta }^{}`$ a *simplicial map*, that is, $`f`$ is a map between the vertex sets which preserves the inclusion among the faces. A simplicial map is called *non-degenerate* if it preserves dimension. Consider a non-degenerate simplicial map between simplicial complexes of the same dimension. In this case facet loops are mapped to facet loops and we obtain an induced map

$$f_\mathrm{\#}=\mathrm{\Pi }(f):\mathrm{\Pi }(\mathrm{\Delta },\sigma _0)\mathrm{\Pi }(\mathrm{\Delta }^{},f(\sigma _0)).$$

Consider the category $`𝒞_d`$ of pairs $`(\mathrm{\Delta },\sigma _0)`$, where $`\mathrm{\Delta }`$ is a simplicial complex of fixed dimension $`d`$ and $`\sigma _0`$ is a facet of $`\mathrm{\Delta }`$. As morphisms take the non-degenerate simplicial maps which map base facets to base facets.

###### Proposition 2.2

$`\mathrm{\Pi }()`$ is a covariant functor from the category $`𝒞_d`$ into the category of finite groups.

###### Proposition 2.3

Let $`\mathrm{\Delta }`$ and $`\mathrm{\Delta }^{}`$ be $`d`$-dimensional simplicial complexes, and let $`\sigma _0`$ be a facet of $`\mathrm{\Delta }`$. If $`f:(\mathrm{\Delta },\sigma _0)(\mathrm{\Delta },f(\sigma _0))`$ is a non-degenerate simplicial map which is injective if restricted to the set of facets, then the induced map $`f_\mathrm{\#}`$ is a group monomorphism. In particular, the group of projectivities of a full-dimensional subcomplex of $`\mathrm{\Delta }`$ which contains $`\sigma _0`$ is a subgroup of $`\mathrm{\Pi }(\mathrm{\Delta },\sigma _0)`$.

We want to determine the groups of projectivities for simplicial complexes $`\mathrm{\Delta }`$ of dimension at most $`1`$. Up to an isomorphism there is a unique simplicial complex of dimension $`1`$, namely $`\{\mathrm{}\}`$. It has a unique facet and no ridges, so its dual graph consists of a single node. Its group of projectivities $`\mathrm{\Pi }(\{\mathrm{}\},\mathrm{})`$ is trivial. Similarly, if $`dim\mathrm{\Delta }=0`$ the facets correspond to the vertices, and $`\mathrm{\Pi }(\mathrm{\Delta },\{v\})`$ is trivial for any vertex $`v`$. The $`1`$-dimensional simplicial complexes are precisely the graphs. The edges are the facets (except for possibly existing isolated nodes). Each edge has two nodes, so the group of projectivities is of order at most $`2`$.

###### Proposition 2.4

Let $`\mathrm{\Delta }`$ be a graph and let $`\sigma _0=\{v,w\}`$ be an edge. If the connected component of $`\sigma _0`$ in $`\mathrm{\Delta }`$ contains an odd cycle, then $`\mathrm{\Pi }(\mathrm{\Delta },\sigma _0)`$ is generated by the transposition $`(vw)`$. Otherwise, the connected component of $`\sigma _0`$ is bipartite and $`\mathrm{\Pi }(\mathrm{\Delta },\sigma _0)`$ is trivial.

There are many ways to build new complexes from given ones. We will explore one construction and its impact on the group of projectivities.

Let $`\mathrm{\Delta }`$ and $`\mathrm{\Delta }^{}`$ be finite dimensional simplicial complexes over the vertex sets $`V`$ and $`V^{}`$, respectively, where $`V`$ is disjoint from $`V^{}`$. The *join* of $`\mathrm{\Delta }`$ and $`\mathrm{\Delta }^{}`$ is defined to be

$$\mathrm{\Delta }\mathrm{\Delta }^{}=\left\{\sigma \sigma ^{}\right|\sigma \mathrm{\Delta },\sigma \mathrm{\Delta }^{}\}.$$

Clearly, $`dim\mathrm{\Delta }\mathrm{\Delta }^{}=dim\mathrm{\Delta }+dim\mathrm{\Delta }^{}+1`$. The facets of $`\mathrm{\Delta }\mathrm{\Delta }^{}`$ are unions of facets of $`\mathrm{\Delta }`$ and $`\mathrm{\Delta }^{}`$; the ridges are unions of a facet of one complex with a ridge of the other. Forming the join of two complexes is, in fact, a topological operation: $`\mathrm{\Delta }\mathrm{\Delta }^{}`$ is homeomorphic to the double mapping cylinder of the projections $`\mathrm{\Delta }\times \mathrm{\Delta }^{}\mathrm{\Delta },\mathrm{\Delta }^{}`$.

###### Proposition 2.5

Let $`\mathrm{\Delta }`$ and $`\mathrm{\Delta }^{}`$ both be finite-dimensional simplicial complexes with facets $`\sigma _0`$ and $`\sigma _0^{}`$, respectively. Then $`\mathrm{\Pi }(\mathrm{\Delta }\mathrm{\Delta }^{},\sigma _0\sigma _0^{})=\mathrm{\Pi }(\mathrm{\Delta },\sigma _0)\times \mathrm{\Pi }(\mathrm{\Delta }^{},\sigma _0^{})`$.

Proof. We claim equality instead of the mere existence of an isomorphism because the direct product can be interpreted as an inner direct product as follows. The maps $`f:\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }^{}:\sigma \sigma \sigma _0^{}`$ and $`f^{}:\mathrm{\Delta }^{}\mathrm{\Delta }\mathrm{\Delta }^{}:\sigma ^{}\sigma _0\sigma ^{}`$ both are non-degenerate and injective, which yields monomorphisms $`\mathrm{\Pi }(f)`$ and $`\mathrm{\Pi }(f^{})`$, respectively, by Proposition 2.3.

We have to prove that each projectivity in the join can be written as a product of a projectivity in $`\mathrm{\Delta }`$ with a projectivity in $`\mathrm{\Delta }^{}`$.

The simplices of $`\mathrm{\Delta }\mathrm{\Delta }^{}`$ are written as $`\sigma \sigma ^{}`$, implying that $`\sigma \mathrm{\Delta }`$ and $`\sigma ^{}\mathrm{\Delta }^{}`$. Note that the distinct facets $`\sigma \sigma ^{}`$ and $`\tau \tau ^{}`$ are adjacent if and only if $`\sigma =\tau `$ and $`\sigma ^{}`$ adjacent to $`\tau ^{}`$ in $`\mathrm{\Delta }^{}`$, or $`\sigma `$ adjacent to $`\tau `$ in $`\mathrm{\Delta }`$ and $`\sigma ^{}=\tau ^{}`$.

Moreover, any two facets $`\sigma \sigma ^{}`$ and $`\tau \tau ^{}`$ with $`\sigma `$ adjacent to $`\tau `$ and $`\sigma ^{}`$ adjacent to $`\tau ^{}`$ are contained in the star of the codimension-$`2`$-face $`(\sigma \tau )(\sigma ^{}\tau ^{})`$. There are precisely two more facets contained in this star, namely $`\sigma \tau ^{}`$ and $`\tau \sigma ^{}`$. Applying the Propositions 2.3 and 2.4 to $`\mathrm{st}((\sigma \tau )(\sigma ^{}\tau ^{}))`$ yields

$$\sigma \sigma ^{},\sigma \tau ^{},\tau \tau ^{},\tau \sigma ^{},\sigma \sigma ^{}=1$$

and thus

$$\sigma \sigma ^{},\sigma \tau ^{},\tau \tau ^{}=\sigma \sigma ^{},\tau \sigma ^{},\tau \tau ^{}.$$
(1)
Invoking the identity (1) several times, allows to “sort” a projectivity: Each projectivity $`\pi `$ from $`\sigma _0\sigma _0^{}`$ onto itself can be written as the product

$`\pi `$ $`=`$ $`\sigma _0\sigma _0^{},\sigma _1\sigma _0^{},\mathrm{},(\sigma _m=\sigma _0)\sigma _0^{})`$
$`\sigma _0\sigma _0^{},\sigma _0\sigma _1^{},\mathrm{},\sigma _0(\sigma _n^{}=\sigma _0^{}).`$
$`\mathrm{}`$

Izmestiev  has proved a partial converse of the previous proposition.

The $`d`$-dimensional simplicial complex $`\mathrm{\Delta }`$ on the vertex set $`V`$ is called *balanced* if there is a map $`c:V\{0,\mathrm{},d\}`$ such that whenever $`\{v,w\}`$ is an edge in $`\mathrm{\Delta }`$ then $`c(v)c(w)`$. The map $`c`$ is called a *proper $`d`$-coloring* of $`\mathrm{\Delta }`$. Clearly, a proper $`d`$-coloring of $`\mathrm{\Delta }`$ is the same as a simplicial projection from $`\mathrm{\Delta }`$ onto the standard $`d`$-simplex which is injective on each simplex. Occasionally, this is called a *folding map* of $`\mathrm{\Delta }`$. Important examples for balanced simplicial complexes are provided by Coxeter complexes and Tits buildings, see Stanley \[20, pp 104ff\]. For properties of proper colorings or folding maps in the context of toric manifolds see Davis and Januszkiewicz \[6, Lemma 1.14 and Example 1.15\].

We call a simplicial complex *locally strongly connected* if it is strongly connected and, additionally, the star of each vertex is also strongly connected. There are strongly connected complexes which is not locally strongly connected. For instance, consider a $`2`$-dimensional complex whose dual graph is a path such that the two triangles corresponding to the end points of the path share a unique vertex $`v`$. The star of $`v`$ is not strongly connected.

###### Proposition 2.6

Let $`\mathrm{\Delta }`$ be a locally strongly connected simplicial complex. Then $`\mathrm{\Delta }`$ is balanced if and only if $`\mathrm{\Pi }(\mathrm{\Delta })`$ is trivial.

Proof. Fix an arbitrary facet $`\sigma _0`$ of $`\mathrm{\Delta }`$ and an arbitrary coloring of the vertices of $`\sigma _0`$. For each facet path $`g`$ from $`\sigma _0`$ to some other facet $`\sigma `$ the projectivity $`g`$ induces a coloring of the vertices of $`\sigma `$. Two such colorings induced by facet paths $`g`$ and $`g^{}`$, respectively, coincide if and only if the projectivity $`g^{}g^{}=g^{}g^1`$, which is induced by the facet loop $`g^{}g^{}`$ based at $`\sigma _0`$, is the identity. Observe that, in general, the color of a vertex $`v\sigma `$ does depend on the choice of the facet $`\sigma `$. Since, however, the star of $`v`$ in $`\mathrm{\Delta }`$ is also strongly connected, this color is the same for all facets containing $`v`$.
$`\mathrm{}`$

It is worth mentioning that the property of being balanced is by no means a topological invariant. To the contrary, for arbitrary $`\mathrm{\Delta }`$ the barycentric subdivision $`\mathrm{sd}\mathrm{\Delta }`$ is always balanced.

## 3 Combinatorial Manifolds

We now impose severe topological restrictions on the simplicial complexes studied. A finite $`d`$-dimensional simplicial complex $`\mathrm{\Delta }`$ is a *combinatorial manifold* if the link of each $`k`$-face is a simplicial sphere of dimension $`dk1`$. In particular, the link of each codimension-$`2`$-face is a $`1`$-sphere, that is, the boundary of a polygon on the combinatorial level. Note that our (combinatorial) manifolds are always compact and without boundary. However, the results below can suitably be extended to combinatorial manifolds with boundary.

If $`\mathrm{\Delta }`$ is a combinatorial manifold, then $`\mathrm{\Delta }`$ is a PL-manifold. Conversely, a PL-manifold $`M`$ always admits a triangulation $`\mathrm{\Delta }`$ (compatible with the PL-structure), such that $`\mathrm{\Delta }`$ is a combinatorial manifold. For a general introduction to combinatorial and PL-manifolds see Hudson , Glaser , or \[13, 65 (IX.17)\].

Throughout the following let $`\mathrm{\Delta }`$ be a combinatorial manifold. This implies that the dual graph $`\mathrm{\Gamma }(\mathrm{\Delta })`$ is strongly connected, so the isomorphism class of the group of projectivities does not depend on the facet chosen.

Consider the joint geometric realization $`\mathrm{\Delta }`$ of $`\mathrm{\Delta }`$ and its dual block complex $`\mathrm{\Delta }^{}`$ within a realization of the first barycentric subdivision $`\mathrm{sd}\mathrm{\Delta }`$, see Munkres \[16, §64\] and also Glaser \[10, pp. 83ff\]. This way each facet path canonically yields an edge path in the $`1`$-skeleton of the dual block complex $`\mathrm{\Delta }^{}`$ and vice versa. Often we will not distinguish between a facet path and its corresponding edge path in $`\mathrm{\Delta }^{}`$. As $`\mathrm{\Delta }`$ is a combinatorial manifold the blocks in $`\mathrm{\Delta }^{}`$ are, in fact, cells. In particular, the blocks are simply connected.

It is known that any path in $`\mathrm{\Delta }=\mathrm{\Delta }^{}`$ is homotopic to a path in the $`1`$-skeleton of $`\mathrm{\Delta }^{}`$ which is the same as the dual graph of $`\mathrm{\Delta }`$. In Seifert and Threlfall \[19, §44\] this is proved for simplicial complexes, but the arguments given can directly be extended to arbitrary cell complexes. In particular, the fundamental group $`\pi _1(\mathrm{\Delta },x_0)`$ for $`x_0\mathrm{\Delta }`$ is generated by facet loops based at $`\sigma _0`$ where $`\sigma _0`$ is some facet with $`x_0\sigma _0`$. Usually, in the geometric realization we choose $`x_0`$ to be the barycenter of the facet $`\sigma _0`$, and we write $`\pi _1(\mathrm{\Delta },\sigma _0)`$. Note that, as $`\mathrm{\Delta }`$ is assumed to be finite, the group $`\pi _1(\mathrm{\Delta },\sigma _0)`$ is finitely generated.

Define the *reduced group of projectivities* $`\mathrm{\Pi }_0(\mathrm{\Delta },\sigma _0)`$ to be the subgroup of $`\mathrm{\Pi }(\mathrm{\Delta },\sigma _0)`$ generated by facet loops based at $`\sigma _0`$ which are null-homotopic. Similar to what is expressed in Lemma 2.1 the reduced group of projectivities is a combinatorial invariant of the connected component of $`\sigma _0`$ in $`\mathrm{\Delta }`$.

###### Proposition 3.1

Let $`p_1,\mathrm{},p_m`$ be a set of facet loops based at $`\sigma _0`$ generating the fundamental group $`\pi (\mathrm{\Delta },\sigma _0)`$. Then $`\mathrm{\Pi }(\mathrm{\Delta },\sigma _0)`$ is generated by $`\mathrm{\Pi }_0(\mathrm{\Delta },\sigma _0)`$ together with $`p_1,\mathrm{},p_m`$.

In particular, if $`\pi _1(\mathrm{\Delta },\sigma _0)`$ is trivial then $`\mathrm{\Pi }_0(\mathrm{\Delta },\sigma _0)=\mathrm{\Pi }(\mathrm{\Delta },\sigma _0)`$. The converse does not hold.

The link of each codimension-$`2`$-face $`\kappa `$ is an $`n`$-gon for some $`n3`$; see Figure 1. Due to the obvious bijection between the facets in $`\mathrm{lk}\kappa `$ and the facets in $`\mathrm{st}\kappa `$ we see that $`\mathrm{\Gamma }(\mathrm{st}\kappa )`$ is also an $`n`$-gon. The *parity* of $`\kappa `$, that is, the property of being *even* or *odd*, is the parity of $`n`$.

Let $`\kappa `$ be a codimension-$`2`$-face $`\kappa `$, $`\sigma `$ a facet containing $`\kappa `$, and $`g`$ a path from $`\sigma _0`$ to $`\sigma `$. As $`\mathrm{st}\kappa `$ is simply connected we infer that the path $`glg^{}`$ is null-homotopic for any facet loop $`l`$ in $`\mathrm{st}\kappa `$ based at $`\sigma `$. Thus we have $`glg^{}\mathrm{\Pi }_0(\mathrm{\Delta },\sigma _0)`$.

If $`\kappa `$ is odd, in view of Proposition 2.4, the group $`\mathrm{\Pi }(\mathrm{st}\kappa ,\sigma )`$ is of order $`2`$, generated by some facet loop $`l`$ based at $`\sigma `$. Then $`glg^{}`$ is a transposition on the set $`\sigma _0`$.

###### Theorem 3.2

The reduced group of projectivities $`\mathrm{\Pi }_0(\mathrm{\Delta },\sigma _0)`$ is generated by the set of all projectivities $`glg^{}`$ where $`g`$ is a facet path from $`\sigma _0`$ to some facet $`\sigma `$ which contains an odd codimension-$`2`$-face $`\kappa `$ and $`l`$ is a facet loop based at $`\sigma `$ generating $`\mathrm{\Pi }(\mathrm{st}\kappa ,\sigma )`$. In particular, $`\mathrm{\Pi }_0(\mathrm{\Delta },\sigma _0)`$ is generated by transpositions.

Proof. Let $`r`$ be an arbitrary facet loop based at $`\sigma _0`$ which is null-homotopic. Without loss of generality let $`x_0`$ be the vertex of $`\mathrm{\Delta }^{}`$ corresponding to the barycenter of $`\sigma _0`$. It is known that $`r`$ can be contracted to the constant map $`c_{x_0}`$ at $`x_0`$ within the $`2`$-skeleton of $`\mathrm{\Delta }^{}`$. Discretizing a suitable homotopy from $`r`$ to $`c_{x_0}`$ yields a sequence $`r_1,\mathrm{},r_n`$ of closed paths in the $`1`$-skeleton from $`x_0`$ to $`x_0`$ in the $`1`$-skeleton of $`\mathrm{\Delta }^{}`$ such that $`r_1=r`$, $`r_n=c_{x_0}`$, and $`r_i`$ coincides with $`r_{i+1}`$ outside some $`2`$-face $`F_i`$ of $`\mathrm{\Delta }^{}`$; see Figure 2. The dual of $`F_i`$ in $`\mathrm{\Delta }`$ is a codimension-$`2`$-face $`\kappa _i`$.

Because the facet paths $`r_1`$ and $`r_2`$ are the same outside $`\mathrm{st}\kappa `$ we have that the projectivity $`r_1r_2^1`$ coincides with some projectivity $`glg^{}`$, where $`g`$ is the common initial segment of $`r_1`$ and $`r_2`$ up to some facet $`\sigma \mathrm{st}\kappa `$ and $`l`$ is a facet loop in $`\mathrm{st}\kappa `$ based at $`\sigma `$. In particular, by Proposition 2.4, $`r_1r_2^1`$ is either a transposition or trivial, depending on the parity of $`\kappa `$.

An induction on $`n`$ establishes the theorem. $`\mathrm{}`$

###### Corollary 3.3

The reduced group of projectivities $`\mathrm{\Pi }_0`$ of a combinatorial manifold is isomorphic to a direct product of symmetric groups.

The same result does not hold for the whole group of projectivities $`\mathrm{\Pi }`$. For an example see Figure 3.

###### Corollary 3.4

The reduced group of projectivities $`\mathrm{\Pi }_0(\mathrm{\Delta },\sigma _0)`$ is trivial if and only if each codimension-$`2`$-face of $`\mathrm{\Delta }`$ is even.

###### Corollary 3.5

Suppose that $`\mathrm{\Delta }`$ is simply connected. Then $`\mathrm{\Delta }`$ is balanced if and only if each codimension-$`2`$-face of $`\mathrm{\Delta }`$ is even.

Corollary 3.5 seems to be known: It is announced, without a proof, in Edwards : “The above theorem \[on a reformulation of the Four Color Problem\] developed from a lunch table conversation at I.H.E.S., Bures-sur-Yvette, France, in which P. Deligne-R. MacPherson-J. Morgan observed that a closed, $`1`$-connected, PL triangulated $`n`$-manifold is $`(n+1)`$-colorable $``$ each $`(n2)`$-simplex has even order.”

The group of projectivities is an interesting invariant of a combinatorial manifold. Consider, for example, two different triangulations of the $`2`$-torus $`𝕊^1\times 𝕊^1`$ as depicted in Figure 3. The first triangulation $`T`$ (to the left) is standard. The second triangulation $`A`$ is produced from $`T`$ by flipping the diagonal edges in the three squares of the middle column; in order to give it some name, call it *anti-torus*. Several combinatorial invariants of $`T`$ and $`A`$ coincide: e.g., the $`f`$-vector, the vector of vertex-degrees in the graph, the Altshuler determinant. But the groups of projectivities differ.

This can be seen as follows. Fix the facet $`\sigma _0=\{1,2,4\}`$ in both triangulations. The codimension-$`2`$-faces are the vertices. In both triangulations, the link of each vertex is the boundary of a hexagon. Therefore, by Corollary 3.4, the only potentially non-trivial contributions to $`\mathrm{\Pi }(T,\sigma _0)`$ and $`\mathrm{\Pi }(A,\sigma _0)`$ can come from the fundamental group which is known to be isomorphic to $`\times `$. The facet loops

$$p=(\{1,2,4\},\{2,4,5\},\{4,5,7\},\{5,7,8\},\{1,7,8\},\{1,2,8\},\{1,2,4\})$$

and

$$q=(\{1,2,4\},\{2,4,5\},\{2,3,5\},\{3,5,6\},\{1,3,6\},\{1,4,6\},\{1,2,4\})$$

generate the group $`\pi _1(T,\sigma _0)`$. Verify that both $`p`$ and $`q`$ are equal to the identity. Now $`p`$ and

$$q^{}=(\{1,2,4\},\{2,4,5\},\{2,5,6\},\{2,3,6\},\{1,3,6\},\{1,4,6\},\{1,2,4\})$$

generate $`\pi _1(A,\sigma _0)`$. Again $`p=\mathrm{id}`$, but $`q^{}`$ is the $`3`$-cycle $`(\mathrm{1\; 4\; 2})`$. Therefore, $`\mathrm{\Pi }(A,\sigma _0)/3`$.

## 4 Polytopes

A polytope is *simple* if each of its vertex figures is a simplex, or, equivalently, for any given vertex $`v`$ there is a 1–1 correspondence between the sets of edges through $`v`$ and the faces containing $`v`$. For an introduction to the theory of convex polytopes, see Ziegler . Here we restrict our attention to polytopes which are convex.

There is another way to characterize simple polytopes, which suits our needs: A polytope $`P`$ is simple if and only if its dual $`P^{}`$ is simplicial, that is, each proper face is a simplex. In particular, the boundary complex of a simple polytope is the dual cell complex of a polytopal sphere. Therefore, we can dualize our definition of perspectivity. The results of the previous section apply.

Let $`v`$ be a vertex in the simple $`d`$-polytope $`P`$. Denote the set of facets through $`v`$ by $`(v)`$. If $`w`$ is a vertex adjacent to $`v`$ then there is a unique facet $`F(v,w)`$ contained in $`(v)(w)`$. The *perspectivity* from $`v`$ to $`w`$ is defined as

$$v,w:(v)(w):F\{\begin{array}{cc}F(w,v)& \text{if }F=F(v,w)\text{,}\hfill \\ F& \text{otherwise.}\hfill \end{array}$$

Again *projectivities* are concatenations of perspectivities. As the boundary of a polytope is connected the isomorphism class of the group of projectivities does not depend on the vertex chosen.

Note that each $`2`$-face of $`P`$ corresponds to (the link of) a codimension-$`2`$-face of the dual. Therefore the following corollary follows from our Theorem 3.2.

###### Corollary 4.1

For any vertex $`v`$ the group of projectivities $`\mathrm{\Pi }(P,v)`$ is generated by projectivities with respect to paths around the $`2`$-faces with an odd number of vertices. In particular, if each $`2`$-face has an even number of vertices, then the group of projectivities vanishes.

Proof. The boundary complex of a polytope is homeomorphic to a sphere, and thus the fundamental group is trivial, provided that the dimension of the polytope is at least $`3`$. The group of projectivities coincides with the reduced group of projectivities. For $`2`$-dimensional polytopes the only $`2`$-face is the polytope itself and the result follows from Proposition 2.4. A $`1`$-dimensional polytope does not have any $`2`$-face, its dual graph consists of two isolated points, and hence the group of projectivities is trivial. $`\mathrm{}`$

This directly allows to compute the group of projectivities of many known polytopes, including all regular simple polytopes.

###### Corollary 4.2

The group of projectivities of the $`d`$-simplex is isomorphic to $`S_d`$.

The group of projectivities of the dodecahedron is isomorphic to $`S_3`$.

The group of projectivities of the regular $`120`$-cell is isomorphic to $`S_4`$.

The group of projectivities of the $`d`$-cube is trivial.

Proof. Each $`2`$-face of a simplex is a triangle. Each $`2`$-face of the dodecahedron and the $`120`$-cell is a pentagon. Each $`2`$-face of the $`d`$-cube is a quadrangle. $`\mathrm{}`$

In Proposition 2.5 we discussed the effect of forming joins of simplicial complexes on the group of projectivities. This can be translated into a result about simple polytopes.

###### Corollary 4.3

Let $`P`$ and $`Q`$ be simple polytopes with respective vertices $`v`$ and $`w`$. Then $`\mathrm{\Pi }(P\times Q,(v,w))=\mathrm{\Pi }(P,v)\times \mathrm{\Pi }(Q,w)`$.

Proof. The product $`P\times Q`$ is again a simple polytope. Its boundary complex is dual to the join of the duals of the boundary complexes of $`P`$ and $`Q`$. $`\mathrm{}`$

The example of products of simplices shows that for any *partition* of $`d`$, that is, a sequence $`(d_1,\mathrm{},d_k)`$ of natural numbers with $`d_i1`$ and $`d_i=d`$, there is a simple $`d`$-polytope whose group of projectivities is isomorphic to $`S_{d_1}\times \mathrm{}\times S_{d_k}`$. From Corollary 3.3 we infer that, in fact, this is the only class of groups which occurs as groups of projectivities of simple polytopes. We obtain a combinatorial invariant of a simple polytope.

###### Corollary 4.4

Let $`P`$ be a simple $`d`$-polytope. Then there is a unique partition $`(d_1,\mathrm{},d_k)`$ of $`d`$ with $`d_1d_2\mathrm{}d_k`$ such that $`\mathrm{\Pi }(P)S_{d_1}\times \mathrm{}\times S_{d_k}`$.

The Corollary 4.1 characterizes those simple polytopes whose $`2`$-faces have an even number of vertices. We call such simple polytopes *even*. Note that each simple zonotope is an even simple polytope. But, an easy construction shows that the even simple polytopes form a (much) wider class. For an example see Figure 4.

Let $`P`$ be an arbitrary $`d`$-polytope. Define a graph $`\overline{\mathrm{\Gamma }}(P)`$ whose nodes are the facets of $`P`$; two facets are joined by an edge in $`\overline{\mathrm{\Gamma }}(P)`$ if their intersection is not empty. A *proper (node) coloring* of a graph is an assignment of a color to each node such that any two adjacent nodes have different colors. The *chromatic number* of a graph is the minimal number of colors in a proper coloring. Following Izmestiev , the *chromatic number* $`\gamma (P)`$ of the polytope $`P`$ is now defined as the chromatic number of the graph $`\overline{\mathrm{\Gamma }}(P)`$. As every vertex of $`P`$ is contained in at least $`d`$ facets, it is clear that it requires at least $`d`$ colors to color $`\overline{\mathrm{\Gamma }}(P)`$ properly. Moreover, if $`\gamma (P)=d`$ then $`P`$ is simple.

The $`1`$-skeleton of a polytope also forms an abstract graph, which is more commonly studied in polytope theory. In order to avoid confusion we call this graph the *vertex-edge-graph* of $`P`$.

For simple polytopes the graph $`\overline{\mathrm{\Gamma }}(P)`$ coincides with its dual graph, that is, the vertex-edge-graph of the dual (simplicial) polytope: This follows from the fact that each vertex figure of a simple polytope is a simplex. Hence any two facets which share a vertex already have a common ridge.

###### Theorem 4.5

Let $`P`$ be a simple $`d`$-polytope. Then the following properties are equivalent.

1. The polytope $`P`$ is even.
2. The vertex-edge-graph of $`P`$ is bipartite.
3. The boundary complex $`P^{}`$ of the dual is balanced.
4. $`\gamma (P)=d`$.

Proof. Let $`P`$ be an even simple $`d`$-polytope. Due to Corollary 4.1 we know that this is characterized by the property that the group of projectivities vanishes. A proper coloring of the facets of $`P`$ clearly corresponds to a proper coloring of the vertices of the dual $`P^{}`$. The existence of such a coloring now follows from Proposition 2.6. This proves the equivalence of the first, the third and the fourth statement. The equivalence of the first and the second statement is known. We indicate a short proof in the Appendix. $`\mathrm{}`$

The same result for $`3`$-dimensional polytopes is classical, see Ore \[17, 13.1.1\] and also Izmestiev  for a more recent proof. The proofs employ techniques, for which it seems to be unclear how they can be generalized to higher dimensions. The result for $`4`$-dimensional polytopes follows from work of Goodman and Onishi . Davis, Januszkiewicz, and Scott proved in \[7, Lemma 4.2.6\] that the boundary complex of the dual of a simple zonotope is balanced.

Recall the definition of the manifold $`𝒵_P=(P\times T)/`$ from the introduction. The number $`s(P)`$ is defined as the maximal dimension of a subgroup of the algebraic torus $`T`$ which acts freely on $`𝒵_P`$.

###### Corollary 4.6

If $`P`$ is an even simple $`d`$-polytope, then $`s(P)=nd`$.

Proof. The dimension $`s(P)`$ of a freely acting subgroup is bounded from above by $`nd`$ according to Buchstaber and Panov \[4, 4.4.2\]. The same number is bounded from below by $`n\gamma (P)`$ by a result of Izmestiev , see \[4, 4.4.5\]. But the Theorem 4.5 enforces $`\gamma (P)=d`$. $`\mathrm{}`$

From the fact that the coloring defined in the proof of Proposition 2.6 is indeed a proper coloring we immediately obtain the following corollary.

###### Corollary 4.7

Let $`P`$ be an even simple $`d`$-polytope. Suppose that $`v`$ and $`w`$ are adjacent vertices of $`P`$. Then the two facets $`F(v,w)`$ and $`F(w,v)`$ are disjoint.

## 5 Concluding Remarks

The terms *perspectivity* and *projectivity* are borrowed from incidence geometry, in particular from the theory of projective planes and generalized polygons, see Van Maldeghem \[21, Section 1.5\]. These notions in turn are inspired by concepts from projective geometry. Moreover, some properties of our groups of projectivities suggest that they can also be seen as some combinatorial analogue of holonomy groups.

It is natural to ask what kind of finite groups can arise as the groups of projectivities of interesting simplicial complexes. From Theorem 3.2 we know that the group of projectivities of any simply connected combinatorial manifold is necessarily isomorphic to a, possibly trivial, product of symmetric groups. Izmestiev  shows that for each conjugacy class of a subgroup of the symmetric group $`S_{d+1}`$ of degree $`d+1`$ there is a combinatorial manifold such that the given group arises as the group of projectivities.

A lot is known about the $`f`$-vectors of balanced simplicial complexes. This is particularly true for balanced Cohen-Macaulay complexes which include the boundary complexes of simplicial polytopes. See Stanley \[20, Section III.4\] as well as Billera and Björner \[2, 15.1.3, 15.2.4\].

There is an intriguing question on planar graphs which is open for quite some time now. It might be worthwhile to explore whether the methods developed in this paper can contribute towards a solution.

###### Conjecture 5.1

(Barnette 1970) The vertex-edge-graph of an even simple $`3`$-polytope contains a Hamiltonian cycle.

For one fairly large class of even simple polytopes one can see immediately that this conjecture holds. Start from an arbitrary simple polytope $`P`$. Successively truncate all the faces with increasing dimension to obtain $`P^{}`$. Truncation is dual to stellar subdivision. So the boundary of the polytope $`P^{}`$ is dual to the barycentric subdivision of the boundary of $`P^{}`$. In particular, $`P^{}`$ is even. Now, each spanning tree in the dual graph of $`P`$ yields a Hamiltonian cycle in the vertex-edge-graph of $`P^{}`$.

## 6 Appendix

Let $`\mathrm{\Gamma }`$ be a finite graph with node set $`V`$ and edge set $`E`$. Consider the $`𝔽_2`$-vector space $`𝔽_2^E`$ of mappings of $`E`$ into $`𝔽_2`$. Each subset of $`E`$ corresponds to such a map via the characteristic function. The *cycle space* of $`\mathrm{\Gamma }`$ is the subspace $`C(\mathrm{\Gamma })`$ of $`𝔽_2^E`$ generated by all cycles of $`\mathrm{\Gamma }`$.

A *pure polytopal complex* is a finite collection $`P_1,\mathrm{},P_k^n`$ of convex $`d`$-polytopes such that the intersection of any two polytopes is a face in both. The boundary complex of any polytope is a polytopal complex, for instance. We want to recursively define the *constructibility* of a polytopal complex: A polytope is constructible. A pure polytopal complex $`\mathrm{\Delta }`$ which is the union of pure constructible subcomplexes $`A`$ and $`B`$ is constructible if the intersection $`AB`$ is a pure constructible complex. The notion of constructibility generalizes the concept of *shellability*, see Ziegler \[23, §8\]. From a theorem of Bruggesser and Mani  it is known that the boundary complexes of polytopes are shellable and thus constructible.

The $`1`$-skeleton of a polytopal complex forms an abstract graph $`\mathrm{\Gamma }(\mathrm{\Delta })`$. For $`\mathrm{\Delta }`$ being the boundary of a convex polytope we called $`\mathrm{\Gamma }(\mathrm{\Delta })`$ the *vertex-edge-graph* of the polytope above. The following result is known. A proof follows from a double induction on the dimension of the complex $`\mathrm{\Delta }`$ and the number of the polytopes comprising $`\mathrm{\Delta }`$.

###### Proposition 6.1

Let $`\mathrm{\Delta }`$ be a constructible polytopal complex. Then the cycle space $`C(\mathrm{\Gamma }(\mathrm{\Delta }))`$ is generated by the cycles corresponding to the $`2`$-faces of $`\mathrm{\Delta }`$.

A finite graph is bipartite if and only if all the cycles in a cycle basis have even length. In particular, a simple polytope is even if and only if its graph is bipartite. This proves the equivalence of the first and the third statement in Theorem 4.5.

The vertex-edge-graph of any simple $`d`$-polytope is $`d`$-regular. A bipartite regular graph has an even number of vertices because, by double counting, both color classes are of the same size.

###### Corollary 6.2

An even simple polytope has an even number of vertices.

We want to explore the relationship between proper facet colorings of a simple polytope and proper edge colorings of its vertex-edge-graph. An edge coloring of a graph is *proper* if any two edges which share a vertex have distinct colors.

###### Proposition 6.3

Let $`P`$ be a simple $`d`$-polytope, and let $`c`$ be a proper coloring of $`\overline{\mathrm{\Gamma }}(P)`$ with $`d`$ colors. Then $`c`$ induces a proper edge coloring of the vertex-edge-graph $`\mathrm{\Gamma }(P)`$ with $`d`$ colors.

Proof. Let $`e=\{v,w\}`$ be an edge of $`P`$. If $`\overline{\mathrm{\Gamma }}(P)`$ is properly $`d`$-colored, then the two facets $`F(v,w)`$ and $`F(w,v)`$ have the same color. Assign this color to the edge $`e`$. Evidently, this procedure requires exactly $`d`$ colors. Assume that this edge coloring is not proper, that is, there are vertices $`u`$, $`v`$, $`w`$ such that $`\{u,v\}`$ and $`\{v,w\}`$ are edges of the same color. Then we have $`c(F(v,u))=c(F(v,w))`$, but the facets $`F(v,u)`$ and $`F(v,w)`$ both contain the vertex $`v`$. This contradicts the assumption that $`c`$ is a proper coloring of the facets. $`\mathrm{}`$

As already mentioned, the graph $`\mathrm{\Gamma }(P)`$ of $`P`$ is $`d`$-regular. By a result of Vizing and Gupta, see West \[22, 6.1.7\], the edges of $`\mathrm{\Gamma }(P)`$ can be properly colored with at most $`d+1`$ colors. König proved that a bipartite $`d`$-regular graph is edge $`d`$-colorable, see West \[22, 6.1.5\]. Therefore, in view of Theorem 4.5, Proposition 6.3 can be interpreted as a very special instance of a classical result from graph theory.

Michael Joswig
Technische Universität Berlin
Fakultät II: Mathematik und Naturwissenschaften
Institut für Mathematik, MA 6-2
Straße des 17. Juni 136
D-10623 Berlin, Germany
joswig@math.tu-berlin.de


format: text

text:
# Coulomb blockade of tunneling between disordered conductors

## Abstract

We determine the zero–bias anomaly of the conductance of tunnel junctions by an approach unifying the conventional Coulomb blockade theory for ultrasmall junctions with the diffusive anomalies in disordered conductors. Both, electron–electron interactions within the electrodes and electron–hole interactions between the electrodes are taken into account non–perturbatively. Explicit results are given for one– and two–dimensional junctions and the crossover to ultrasmall junctions is discussed.

Coulomb blockade of tunneling  has been investigated extensively in the last decade. Most of these studies were focussed on ultrasmall tunnel junctions with small capacitance $`C`$. Then, the relevant energy scale is the charging energy $`E_C=e^2/2C`$. In these effectively zero–dimensional junctions the charge of a tunneling electron is distributed over the junction area fast compared to the time scale $`\mathrm{}/eV`$ associated with the applied voltage $`V`$, and Coulomb blockade effects are observable for single junctions only because of the slow charge relaxation via the environmental impedance $`Z(\omega )`$ .

The situation changes for tunnel junctions with large lateral extensions where the time scale of propagation of the electromagnetic field over the system size becomes relevant. Then screening and relaxation processes within the electrodes need to be considered explicitly. Particularly, in junctions with disordered low–dimensional electrodes, the field propagates diffusively, and a suppression of the tunneling conductance arises from the reduction of the electron density of states by electron–electron interactions .

The pioneering papers on the diffusive anomalies in disordered conductors  are based on perturbation theory in the Coulomb interaction and fail at very low energy scales. As is well–known from the conventional theory of Coulomb blockade in effectively zero–dimensional junctions  a non–perturbative approach is needed for a complete treatment of the Zero–Bias Anomaly (ZBA) of the conductance. Furthermore, apart from the interaction within the electrodes, the Coulomb interaction between the electrodes needs to be taken into account. Only in limiting cases, e.g., for a strongly disordered electrode screened by a bulky electrode, can the mutual interaction be incorporated into a screened Coulomb potential.

Here, we present a microscopic approach treating all low energy excitations of the Coulomb field non–perturbatively and obtain explicit results for the current–voltage relation of zero–, one–, and two–dimensional junctions at finite temperature. Specifically, we consider a tunnel junction consisting of two disordered metallic electrodes separated by a thin insulating barrier with a chemical potential difference $`\mu _1\mu _2=eV`$. The tunneling current $`I`$ can be calculated from the tunneling Hamiltonian

$`H_T={\displaystyle \underset{k,q}{}}T_{kq}c_k^{}c_q+\mathrm{h}.\mathrm{c}.,`$ (1)
where $`k`$ and $`q`$ label the momenta of electrons in the right and left electrode, respectively . To leading order in $`H_T`$ the current reads

$`I(V)=2e\mathrm{Im}[X^{\mathrm{ret}}(eV)].`$ (2)
Here $`X^{\mathrm{ret}}(\omega )`$ is the Fourier transform of

$`X^{\mathrm{ret}}(t)=i\theta (t){\displaystyle \underset{k,q}{}}{\displaystyle \underset{k^{},q^{}}{}}T_{kq}T_{k^{}q^{}}^{}[c_k^{}(t)c_q(t),c_q^{}^{}c_k^{}]`$ (3)
where we put $`\mathrm{}=1`$, and the time evolution of the Fermi operators arises from the Hamiltonian in the absence of tunneling, but in the presence of disorder and interactions.

To evaluate the expectation value with four Fermi operators in Eq. (3), we employ the Keldysh $`\sigma `$–model technique  leading to the result in Eq. (17) below. We start from the partition function

$`Z=𝒩{\displaystyle 𝒟\overline{\psi }_1𝒟\psi _1𝒟\overline{\psi }_2𝒟\psi _2𝒟\varphi e^{iS[\overline{\psi }_1,\psi _1,\overline{\psi }_2,\psi _2,\varphi ]}},`$ (4)
where $`𝒩`$ is a normalization constant. The action is given by

$`S[\overline{\psi }_j,\psi _j,\varphi ]`$ $`=`$ $`{\displaystyle \underset{j}{}}{\displaystyle _𝒞}dt{\displaystyle _{V_j}}dr\overline{\psi }_j(r,t)[i{\displaystyle \frac{}{t}}+{\displaystyle \frac{1}{2m}}\mathrm{\Delta }`$ (7)
$`W_j(r)+e\varphi (r,t)]\psi _j(r,t)`$
$`+{\displaystyle \frac{1}{8\pi }}{\displaystyle _𝒞}𝑑t{\displaystyle 𝑑r\left[\varphi (r,t)\right]^2},`$
where $`𝒞`$ is the Keldysh contour, $`W_j(r)`$ are Gaussian distributed disorder potentials, $`\varphi `$ is the electric potential, and $`e`$ is the electric charge. While the fermionic terms are integrated over the volume of the electrodes only, the last term is integrated over entire space, which leads to electrostatic coupling between the electrodes. For simplicity we disregard polarization effects in the tunnel barrier, that may easily be incorporated in the capacitance $`C_0`$ introduced below.

Assuming that the impurity potentials in the two electrodes are statistically independent, the Gaussian integrations over the realizations of $`W_j(r)`$ lead to quartic interactions of the fermion fields within each electrode. Within the $`\sigma `$–model approach these interactions can be decoupled by introducing Hubbard–Stratonovich matrix fields $`\widehat{Q}_j`$ . Subsequently, the fermionic fields can be integrated out in the usual way yielding a representation of the impurity averaged partition function as a functional integral over the electric potential $`\varphi `$ and the matrix fields $`\widehat{Q}_j`$. Since for given field $`\varphi `$ all of these transformations can be done independently for each electrode, the resulting action $`S[\varphi ,\widehat{Q}_1,\widehat{Q}_2]`$ can immediately be inferred from earlier work .

To proceed we follow Kamenev and Andreev  and evaluate the integrals over the matrix fields $`\widehat{Q}_j`$ using the saddle point approximation. The saddle point solution can be obtained analytically for spatially uniform fields $`\varphi (t)`$ only. Provided $`\varphi `$ is essentially constant on scales of the size of the mean free path $`l`$, an effective action was derived in  which incorporates dynamic screening in the random phase approximation (RPA) and the diffuson vertex correction within each electrode.

One is left with a Gaussian integral over the Coulomb field with a purely electromagnetic action which determines the field propagators. Since these depend on the geometry of the electrodes, we first restrict ourselves to the case of thin films. Then, for low energy excitations with wave vectors $`qa^1`$, where $`a`$ is the thickness of the films, we have effectively a two–dimensional problem, where the Coulomb field depends on two spacial coordinates in each electrode (see also the discussion below). Although only the large distance behavior of the Coulomb interaction matters, we have to keep the barrier thickness $`\mathrm{\Delta }`$ finite since dipolar interactions arise . With the sources restricted to two–dimensional films at $`z_j=\pm \mathrm{\Delta }/2`$, the bare Coulomb interactions reads

$`U_{ij}^{(0)}(xx^{},yy^{})={\displaystyle 𝑑z𝑑z^{}\frac{e^2\delta (zz_i)\delta (z^{}z_j)}{|rr^{}|}}.`$ (8)
The resulting equation for the matrix $`U^{\mathrm{ret}}(q,\omega )`$ of the Fourier transformed field propagator then takes the form of the diffusive RPA

$`U^{\mathrm{ret}}(q,\omega )=\left[\left(U^{(0)}(q,\omega )\right)^1+P(q,\omega )\right]^1,`$ (9)
where

$$U^{(0)}(q,\omega )=\left(\begin{array}{cc}u(q)& \hfill v(q)\\ v(q)& \hfill u(q)\end{array}\right).$$
(10)
Here $`u(q)`$ and $`v(q)`$ are the two–dimensional bare Coulomb interactions inside and between the electrodes, respectively. Neglecting polarization effects in the barrier, we obtain $`u(q)=2\pi e^2/q`$ and $`v(q)=2\pi e^2e^{q\mathrm{\Delta }}/q`$. The polarization function

$$P(q,\omega )=\left(\begin{array}{cc}\nu _1\frac{D_1q^2}{D_1q^2i\omega }& 0\\ 0& \nu _2\frac{D_2q^2}{D_2q^2i\omega }\end{array}\right)$$
(11)
contains the bare electron densities $`\nu _j`$ and the electron diffusion constants $`D_j`$ of the two electrodes.

Supplementing the partition function $`Z`$ with source fields that couple to the fermion operators of each electrode, it may be employed as a generating functional to evaluate impurity averaged correlation functions like

$`X^>(t)=i{\displaystyle \underset{k,q}{}}{\displaystyle \underset{k^{},q^{}}{}}T_{kq}T_{k^{}q^{}}^{}\overline{c_k^{}(t)c_q(t)c_q^{}^{}c_k^{}}.`$ (12)
The pre–exponential factors resulting from functional derivatives with respect to the sources are replaced by their saddle point approximation. In terms of an average tunnel matrix element $`T`$, we find

$`X^>(t)`$ $`=`$ $`i\nu _1\nu _2|T|^2{\displaystyle 𝑑ϵ𝑑ϵ^{}e^{i(ϵϵ^{})t}}`$ (14)
$`\times n(ϵ)[1n(ϵ^{})]e^{J(t)},`$
where the interaction effects are incorporated in

$`J(t)=2{\displaystyle \frac{d\omega }{2\pi }\frac{e^{i\omega t}1}{1e^{\beta \omega }}\mathrm{Im}Y(\omega )}.`$ (15)
Here $`\beta `$ is the inverse temperature and

$`Y(\omega )={\displaystyle \underset{i,j}{}}{\displaystyle \underset{q}{}}(2\delta _{ij}1){\displaystyle \frac{U_{ij}(q,\omega )}{(D_iq^2i\omega )(D_jq^2i\omega )}}.`$ (16)
The factors $`(D_jq^2i\omega )^1`$ come from the vertex correction terms in the action and are seen to obey the classical diffusion equation. When the two–dimensional result for $`Y(\omega )`$ is inserted into Eq. (15), the $`\omega `$–integral needs to be cut off at frequencies of order $`|\omega |1/\tau _0a^2/D`$ where the crossover from two– to three–dimensional behavior occurs.

Now, combining Eqs. (2) and (14), the expression for the current is found to read

$`I(V)={\displaystyle \frac{G_0}{e}}{\displaystyle _{\mathrm{}}^{\mathrm{}}}𝑑ϵϵP(eVϵ){\displaystyle \frac{1e^{\beta eV}}{1e^{\beta ϵ}}},`$ (17)
where $`G_0=4\pi e^2\nu _1\nu _2|T|^2`$ is the bare tunneling conductance, and where we have introduced the spectral density

$`P(ϵ)={\displaystyle \frac{1}{\pi }}\mathrm{Re}{\displaystyle _0^{\mathrm{}}}𝑑te^{iϵt}e^{J(t)}.`$ (18)
The expression (17) constitutes the central result of this work. It is formally identical to the conventional expression for the current–voltage relation of ultrasmall tunnel junctions (zero–dimensional case) , and determines the non–perturbative effect of Coulomb interactions on the $`I`$$`V`$–curve of spatially extended disordered tunnel junctions. The very same form can also be derived in the case of effectively one–dimensional wires (see below).

To make contact with previous work, we first consider the (somewhat unrealistic) case where Coulomb interactions between the electrodes are disregarded, i.e., $`U_{12}=U_{21}=0`$. Then $`J(t)=J_1(t)+J_2(t)`$ where $`J_j(t)`$ contains the contribution from $`U_{jj}`$ only. Replacing $`J(t)`$ by $`J_j(t)`$ in Eq. (18), we may define spectral densities $`P_j(ϵ)`$ for each electrode. The current (17) can then be written in the familiar form

$`I`$ $`=`$ $`4\pi e|T|^2{\displaystyle 𝑑ϵ\nu _1(ϵ)\nu _2(ϵeV)\left[n(ϵeV)n(ϵ)\right]}`$ (19)
with the densities of states

$`\nu _j(ϵ)=\nu _j{\displaystyle _{\mathrm{}}^{\mathrm{}}}𝑑ϵ^{}{\displaystyle \frac{1+e^{\beta ϵ}}{1+e^{\beta ϵ^{}}}}P_j(ϵϵ^{}).`$ (20)
This relation gives a non–perturbative result for the effective tunneling density of states of an electrode in presence of Coulomb interactions expressed in terms of the spectral density $`P_j(ϵ)`$ familiar from Coulomb blockade theory. When $`P_j(ϵ)`$ is replaced by its perturbative approximation, the seminal result by Altshuler, Aronov, and Lee  is recovered.

In particular, for a two–dimensional film at zero temperature the density of states (20) reads

$`\nu (ϵ)=\nu \mathrm{exp}\left[{\displaystyle \frac{1}{4\pi g}}\mathrm{ln}|ϵ\tau _0|\mathrm{ln}\left({\displaystyle \frac{|ϵ|}{(D\kappa ^2)^2\tau _0}}\right)\right],`$ (21)
where we have suppressed the index $`j`$. Further, $`g=2\pi \nu D`$ is the conductance in units of $`e^2/2\pi `$ and $`\kappa =2\pi e^2\nu `$ is the inverse screening length in two dimensions. The non–perturbative result (21) has been obtained previously by Kamenev and Andreev .

We now return to the full problem and determine the non–perturbative $`I`$$`V`$–curve for two–dimensional interacting electrodes at zero temperature. Then, the four terms in Eq. (16) cannot be split into contributions of each electrode, and the spectral function $`P(ϵ)`$ characterizes the coupled system. In the parameter range relevant for tunneling experiments $`u(q)v(q)2\pi e^2\mathrm{\Delta }`$, and we obtain from Eq. (16)

$`Y(\omega )={\displaystyle \frac{e^2}{C_0}}{\displaystyle \underset{q}{}}{\displaystyle \underset{j=1}{\overset{2}{}}}{\displaystyle \frac{\lambda _j}{(D^{}q^2i\omega )(D_jq^2i\omega )}}.`$ (22)
Here we have introduced the field diffusion constant $`D^{}=(2\delta _1\delta _2+\delta _1D_2+\delta _2D_1)/(\delta _1+\delta _2)`$, with $`\delta _j=D_j\kappa _j\mathrm{\Delta }`$ and the numerical factors $`\lambda _j=(2\delta _i+D_iD_j)/2(\delta _1+\delta _2)`$ ($`ij`$). While $`D`$ and $`\kappa `$ are properties of the electrodes, $`\mathrm{\Delta }`$ may also be expressed in terms of the capacitance per unit area $`C_0=1/4\pi \mathrm{\Delta }`$ of the junction. With the result (22) we readily obtain from Eq. (17) for the zero temperature differential conductance $`G(V)=I/V`$ at voltages $`VV_0`$

$`{\displaystyle \frac{G(V)}{G_0}}`$ $`=`$ $`{\displaystyle \frac{e^{2\gamma /g}}{\mathrm{\Gamma }(1+2/g)}}\left({\displaystyle \frac{V}{V_0}}\right)^{2/g},`$ (23)
where $`\gamma =0.577\mathrm{}`$ is Euler’s constant, $`g=\frac{8\pi ^2}{e^2}C_0D^{}\left(_j\lambda _j\mathrm{ln}(1/\xi _j)/(1\xi _j)\right)^1`$ with $`\xi _j=D_j/D^{}`$ is a dimensionless parameter, and $`V_0=2\pi /e\tau _02\pi D/ea^2`$.

When $`g1`$ we recover the perturbative result

$`G(V)=G_0[1+2/g\mathrm{ln}(V/V_0)],`$ (24)
Hence in the non–perturbative approach the logarithmic corrections of perturbation theory are exponentiated to a power–law dependence on $`V`$. In the limiting case where one of the electrodes is bulky, i.e. $`\kappa _1\kappa _2`$, this result can be rewritten by means of Eq. (20) in terms of an effective tunneling density of states of the other electrode

$`\nu (ϵ)=\nu _0{\displaystyle \frac{e^{2\gamma /g}}{\mathrm{\Gamma }(1+2/g)}}\left({\displaystyle \frac{ϵ}{eV_0}}\right)^{2/g}`$ (25)
This gives a non-perturbative generalization of the result obtained by Altshuler, Aronov, and Zyuzin .

We now turn to one–dimensional contacts. Then the result (22) for $`Y(\omega )`$ remains valid provided the bare interactions $`u(q)`$ and $`v(q)`$ in Eq. (10) are replaced by $`u(q)=2e^2\mathrm{ln}(1/qa)`$ and $`v(q)=2e^2\mathrm{ln}(1/q\mathrm{\Delta })`$. Further the momentum sum is one–dimensional, and $`C_0=[4\mathrm{ln}(\mathrm{\Delta }/a)]^1`$ becomes the capacitance per unit length. The zero temperature differential conductance now takes the form

$`{\displaystyle \frac{G(V)}{G_0}}=1\text{erf}\sqrt{{\displaystyle \frac{V_0}{V}}}`$ (26)
with $`V_0=\frac{e^3}{8\pi D^{}C_0^2}[_j\lambda _j/(1+\xi _j^{1/2})]^2`$. This result is formally equivalent to the conductance of an ultrasmall junction biased via a RC transmission line  and is in quantitative agreement with a recent experimental study of long tunnel junctions .

If one of the electrodes is bulky, we again may use Eq. (20) to obtain an effective tunneling density of states of a one–dimensional electrode

$`\nu (ϵ)=\nu _0\left(1\text{erf}\sqrt{{\displaystyle \frac{eV_0}{ϵ}}}\right).`$ (27)
While for large energies we recover the perturbative result $`\nu (ϵ)=\nu _0(12\sqrt{eV_0/\pi ϵ})`$, the non–perturbative result (27) does not diverge at low energies but approaches an exponential suppression of the densities of states near the Fermi surface $`\nu (ϵ)=\nu _0\sqrt{ϵ/\pi eV_0}\mathrm{exp}(eV_0/ϵ)`$.

For the realistic case of a system with finite size the diffusive spreading of the transfered charge reaches the boundaries of the electrode for long times, and then the charge relaxes via the external circuit characterized by an impedance $`Z_{\mathrm{ext}}(\omega )`$. This modifies the ZBA at very low voltages. For simplicity we assume that the external charge relaxation, which is the only process relevant for ultrasmall junctions , is slow and couples only to the $`q=0`$ component of the field . Then Eq. (22) is modified to read

$`Y(\omega )`$ $`=`$ $`{\displaystyle \frac{e^2}{C_0}}{\displaystyle \underset{q0}{}}{\displaystyle \underset{j=1}{\overset{2}{}}}{\displaystyle \frac{\lambda _j}{(D^{}q^2i\omega )(D_jq^2i\omega )}}`$ (29)
$`+i{\displaystyle \frac{e^2}{\omega }}{\displaystyle \frac{1}{Z_{\mathrm{ext}}^1(\omega )i\omega C}}.`$
For one–dimensional electrodes of length $`L`$ the discrete $`q`$ values are of the form $`(2\pi /L)n`$, $`n`$ integer, and $`C=C_0L`$ is the total capacitance of the contact, while for two–dimensional quadratic electrodes $`C=C_0L^2`$.

For three–dimensional electrodes of finite size there are several energy scales in $`Y(\omega )`$: The charging energy $`E_C=e^2/2C`$ and for each spatial dimension $`\mathrm{}`$ of the electrodes a Thouless energy $`E_{\mathrm{Th}}=D/\mathrm{}^2`$ as well as a field Thouless energy $`E^{}=D^{}/\mathrm{}^2`$. Here $`\mathrm{}`$ stands for the length $`L`$, width $`w`$, and thickness $`a`$, respectively. The effective dimension of the electrodes is determined by $`E^{}`$. Whenever $`eV`$ exceeds one of the scales $`E_{\mathrm{}}^{}`$ ($`\mathrm{}=L,w,a`$) the effective dimension increases by one.

As an example we consider a symmetric one–dimensional contact of length $`L`$ with an ohmic external impedance $`Z_{\mathrm{ext}}=R`$. Then, from Eq. (29) we obtain

$`\mathrm{Im}Y(\omega )`$ $`=`$ $`\mathrm{Im}Y_{\mathrm{}}(\omega )f\left({\displaystyle \frac{\omega }{E^{}}}\right)+{\displaystyle \frac{\alpha }{1+\alpha ^2(\omega R_\mathrm{K}C)^2}}`$ (30)
where $`\mathrm{Im}Y_{\mathrm{}}(\omega )=e^2/[2\sqrt{2D^{}}C_0(1+\xi ^{1/2})\omega ^{3/2}]`$ describes an infinitely long contact, and the function $`f(z)=(g(z)\xi ^{1/2}g(z/\xi ))/(1\xi ^{1/2})`$ with $`g(z)=\mathrm{Im}\left[\sqrt{2i}\mathrm{cot}\left(\sqrt{iz}/2\right)\right]`$ incorporates all size effects. The last term in Eq. (30) describes the environmental impedance characterized by the dimensionless parameter $`\alpha =R/R_\mathrm{K}`$ with $`R_\mathrm{K}=h/e^2`$.

In Fig. 1 we present results for typical values of metallic quasi one–dimensional tunnel junctions  ($`\xi =4\times 10^4`$, $`E^{}/eV_0=100`$, $`E_C/eV_0=25`$). The full line corresponds to a finite length junction shunted by a rather large environmental impedance ($`\alpha =1`$) to display the crossover between zero–dimensional and one–dimensional behavior clearly. The dotted line gives the conventional environmental Coulomb blockade of a zero–dimensional junction which determines the behavior for voltages below $`E_C/e`$ (see inset). On the other hand, for large voltages above $`E^{}/e`$ the result (26) for a long one–dimensional junction (dashed line) is approached. The chain dotted line results from a perturbative calculation of the diffusive anomaly .

In summary, we have studied tunneling in large junctions with diffusive electron motion. Treating the Coulomb interaction non–perturbatively, the $`I`$$`V`$–curve was written in a form familiar from Coulomb blockade theory for ultrasmall junctions. Interaction effects are again incorporated in a spectral function $`P(ϵ)`$. However, while for ultrasmall junctions $`P(ϵ)`$ depends only on the effective impedance $`[Z_{\mathrm{ext}}^1(\omega )i\omega C]^1`$, for large junctions this quantity is replaced by $`i\omega Y(\omega )/e^2`$ which incorporates also the diffusive anomaly of disordered metals.

We would like to thank the authors of Ref.  and G. Göppert for valuable discussions. One of us (JR) is grateful to the CEA-Saclay for hospitality during a stay where parts of this work were carried out. Financial support was provided by the DAAD.


text:
# The ATESP Radio Survey

## 1 Introduction

Deep radio surveys have clearly indicated that normalized radio counts show a flattening below a few mJy; the first clear indications of such a flattening date back to the pioneering deep ($`S_{1.4\mathrm{GHz}}<1`$ mJy) radio surveys undertaken in the early eighties (see Condon 1984, Kellerman et al. 1987; Windhorst et al. 1990 for reviews on radio counts available at the time), and have been confirmed by deeper and/or larger surveys (mostly at 1.4 GHz) carried out in the last decade. The counts derived from the ATESP survey, which covers an area 8 times larger than the previous surveys (Prandoni et al. 2001, paper III in this series), indicate that the upturn actually occurs at $`S1`$ mJy.

This change of slope has been interpreted as being due to the presence of a new population of radio sources (the so-called sub–mJy population) which does not show up at higher flux densities. Classical radio sources, powered by active galactic nuclei (AGN) and typically hosted by giant ellipticals and quasars are known to dominate at high flux densities ($`99\%`$ above 60 mJy, Windhorst et al. 1990), but their contribution steadily decreases going to fainter fluxes. At $`0.1<S_{1.4\mathrm{GHz}}<1`$ mJy, the median angular size of radio sources shrinks to $`<3\mathrm{}`$ and the sources are predominantly identified with blue galaxies (see e.g. Kron et al. 1985; Windhorst et al. 1985; Windhorst et al. 1990). These systems often appear disturbed, in poor groups, and/or part of merging galaxy systems. This evidence, coupled with the well-known tight far infrared/radio correlation found for many of these objects at lower redshift, as well as optical spectra with HII-like signatures similar to those of star-forming IRAS galaxies (Benn et al. 1993), suggested that the radio emission in these galaxies is the result of active star-formation ($`1100`$ M$``$/yr).

Unfortunately, the optical identification work and subsequent spectroscopy, needed to investigate the nature of the radio sources, are both very demanding in terms of telescope time, since faint radio sources have usually very faint optical counterparts. Typically, no more than $`5060\%`$ of the radio sources in sub–mJy samples have been identified on optical images. Only in the $`\mu `$Jy survey of the Hubble Deep Field, 80$`\%`$ of the 111 radio sources detected have been identified (Richards et al. 1999). On the other hand, the typical fraction of spectra available is only $`20\%`$. Due to the long integration times needed for detection, deeper spectroscopy programmes have been undertaken only for very small sub–mJy radio samples and never went to completion. The best studied sample is the Marano Field ($`0.3`$ sq. degr.), where $`50\%`$ of the sources have spectra (Gruppioni et al. 1999), which allowed to determine spectral type and redshift for 29 galaxies.

When discussing results about the nature and the evolution of faint radio sources, the numbers reported above must be kept in mind. Conclusions are, in fact, limited by the low identification rate and biased by the fact that only the brightest optical counterparts have spectral information. This explains why, despite the large observational efforts, the true nature of the sub–mJy population is not yet well established. Today we know that the sub–mJy population is composed by different classes of objects (AGN, star-forming galaxies, normal elliptical and spiral galaxies), but the relative fractions are still uncertain. Gruppioni et al. (1999) found that $`50\%`$ of the observed sources show the typical absorption spectra of early type galaxies, while late-type galaxies account for 32% of the whole population. This result is in contrast with previous ones, where a predominance of star-forming galaxies was found (e.g. in Benn et al., $`47\%`$ of the sources are associated to late-type galaxies).

Recently the Phoenix survey (Hopkins et al. 1998) has given an important contribution to the knowledge of the faint radio population. Georgakakis et al. (1999) obtained spectroscopic data for 246 objects with $`S_{1.4}>0.15`$ mJy and $`m_R<22.5`$, corresponding to about 40% of the optically identified sample. The large numbers involved allowed the separation, on a reliable statistical basis, the mJy and sub–mJy regimes. According to their spectroscopic classification, they found that most of the emission-line sources are star-forming galaxies (contributing for $`41\%`$ of the sub–mJy population) and that the absorption-line systems, likely to be ellipticals, dominate at flux densities $`>1`$ mJy (46%). However absorption-line systems are also found at sub–mJy levels ($`22\%`$). Unfortunately a significant fraction of objects (almost $`30\%`$) could not be classified due to poor quality of the spectra, making the quoted numbers still quite uncertain.

It is therefore clear that the availability of large faint radio samples with complete (good quality) spectroscopy is critical in order to fully assess the nature and evolution of the mJy and sub–mJy radio sources. A significant advantage for this kind of study is obviously provided by a faint radio survey with deep photometry already available (possibly multicolor). The region we have selected fulfills these requirements at least partially. It consists of the overlap between the ATESP survey (Prandoni et al. 2000a, Paper I) and the EIS patch A photometric survey (Nonino et al. 1999).

This paper is organized as follows: in Sect. 2 we describe the ATESP-EIS sample; in Sect. 3 we define the complete sample for which we have obtained spectroscopy and we report the observations, the reduction of the spectra and the spectral classification criteria used. The ATESP-EIS sample properties are described in Sect. 4. The mJy and sub–mJy population properties as deduced from our analysis are discussed in Sect. 5. Conclusions are given in Sect. 6.

Through this paper we will use $`H_0=100`$ km s-1 Mpc-1 and q$`{}_{0}{}^{}=0.5`$.

## 2 The ATESP–EIS Sample: Optical Identifications

Vettolani et al. (1997) made a deep redshift survey (referred to as ESP) in two strips of $`22^{}\times 1^{}`$ and $`5^{}\times 1^{}`$ at $`\delta 40\mathrm{°}`$. They obtained photometry and spectroscopy for 3342 galaxies down to $`b_J`$ 19.4 (Vettolani et al. 1998). The same region was observed at 1.4 GHz with the Australia Telescope Compact Array. This radio survey (referred to as the ATESP radio survey) consists of 16 radio mosaics with $`8\mathrm{}\times 14\mathrm{}`$ resolution and uniform sensitivity ($`1\sigma `$ noise level $``$79 $`\mu `$Jy) over the region covered by the ESP redshift survey ($`26`$ sq. degrees, see details in paper I). The ATESP survey has produced a catalogue of 2967 radio sources down to a flux limit ($`6\sigma `$) of $``$ 0.5 mJy (see Prandoni et al. 2000b - paper II - and following updates at http://www.ira.bo.cnr.it/atesp).

In a 3.2 sq. degr. subregion of the $`5^{}\times 1^{}`$ strip lies the EIS (ESO Imaging Survey) Patch A, consisting of deep images in the I band out of which an object catalogue has been extracted. Further V band images are available over $``$ 1.5 sq. degr.. In order to identify the radio sources present in this area we used the EIS Patch A I-band filtered catalogue. The filtering is required to eliminate truncated objects (f.i. objects at the border of the images) and objects with a significant number of pixels affected by cosmic rays and/or other artifacts (see the discussion in Nonino et al. 1999, Sect. 5.3). This catalogue covers 3 square degrees. At I $``$ 22.5 the completeness of the EIS catalog is $`95\%`$, while it rapidly drops at fainter magnitudes. We then decided to consider in our analysis only the radio-optical associations found down to $`I=22.5`$. A search circle of $`3\mathrm{}`$ radius, centered at each radio position, was chosen; this turned out to be a good compromise when inspecting Fig. 1, where the distance distribution of the radio-optical associations with $`I<22.5`$ is presented. For double and triple radio sources the distance to the nearest optical counterpart is computed from the radio centroid, while for complex radio sources (e.g. sources which cannot be described by a single or multiple Gaussian fit) the distance is computed from the radio peak position. Since this position does not generally coincide with the position of the source nucleus (where the optical identification is expected to be) we allowed for distances larger than $`3\mathrm{}`$ and checked for the actual existence of optical counterpart by visual inspection of the radio-optical finding charts. As to the radio morphology, among the 386 sources three are triples (none identified), three are complex (one identified), twenty-one are doubles (six identified) and 359 are point-like (212 identified). In summary, 219 of the 386 radio sources present in this region have been identified down to I=22.5

The distribution of radio-optical pairs at distances $`>3\mathrm{}`$ has been used to provide an estimate of the number of spurious identifications expected in the identification sample. The estimated contamination rate is $`2\%`$ (5/219).

Fig. 2 shows the distribution of the identified radio sources as a function of the I-band magnitude. The most interesting feature in this distribution is the strong decrease at magnitudes $`I>20`$. We point out that this is not due to incompleteness effects in the optical catalogue but is a consequence of the physical radio-optical properties of our sources (see discussion in Sect. 5).

## 3 The ATESP-EIS Sample: Spectroscopy

From the list of 219 identified radio sources we have extracted a sample of 70 galaxies complete down to I = 19.0 and we have obtained spectra for all objects except the double radio source ATESP J224750-400143. The spectra were taken in three different runs (October 1998, September and October 1999) with EFOSC2, mounted on the ESO 3.6 meter telescope at La Silla, Chile. In the first run (October 1998) we used Grism number 11, which gives a dispersion of 2.12 Å/pixel. The scale of EFOSC2 is 0.16 arcsec per pixel, corresponding to 13.2 Å/$`1\mathrm{}`$ slit. The wavelength range covered is 3380–7540 Å. In the following runs (September and October 1999) we used Grism number 6, which gives a similar dispersion (2.06 Å/pixel, corresponding to 12.9 Å$`/1\mathrm{}`$). This grism was chosen because it is more efficient in the red part of the wavelength range covered (3860 – 8070 Å) and allows to detect the H$`\alpha `$ line up to larger redshifts. Typical exposure times range from 15 minutes for the brightest galaxies ($`I<16.5`$) to 1 hour for the faintest galaxies ($`I>18.5`$). For 14 objects, spectra were already available. They had been taken with the multi-fiber spectrograph Optopus (also at the ESO 3.6 m telescope) by the ESP team (Vettolani et al. 1998). These spectra have a dispersion of 4.5 Å per pixel over the $`\lambda `$ range 3750–6150 Å.

The reduction of the spectra was done with the IRAF package: we followed the standard procedures of bias subtraction, flat field correction, object extraction from the two-dimensional EFOSC images, sky subtraction and subsequent wavelength and flux calibration. In slightly over one half of the spectra emission lines were present (typically at least \[OII\] or H$`\alpha `$, but often other lines too); the elliptical galaxies are mostly without emission lines and the redshift is based on absorption lines like the Ca H and K lines, the G band, the Mg triplet at $`5180`$ Å, and the Na D doublet. The obtained redshifts are helio-centric. The rms uncertainty in the redshifts (always determined from at least three lines) is of the order of 100 km/s, in accordance with the resolution of the spectra. The high signal-to-noise ratio of these spectra permits an unambiguous spectral classification of the whole sample. Classification of the spectral types is given in the next section.

### 3.1 Spectral Classification

The spectral classification criteria we used are based on visual inspection of the spectra and were followed, when necessary, by measurements of line fluxes (and/or equivalent widths) to be used in diagnostic diagrams as those presented by Baldwin et al. (1981) or Rola et al. (1997). However, the use of diagnostic diagrams is rather limited here due to the low resolution of the spectra (e.g. $`H\alpha `$ and \[NII\] lines cannot be separated) and to the poorer signal-to-noise ratio in faint object spectra. We used the classification scheme originally proposed by Morgan and Mayall (1957) and revised by Kennicutt (1992), which is basically followed also by Georgakakis et al. (1999) and Gruppioni et al. (1999) in the study of faint radio galaxies. However, we have classified the post-starburst galaxies separately. The spectral classes we use are:

Early Type Spectrum (ETS) – Galaxies whose spectra show absorption lines coming from a mixture of late type stars characterizing ellipticals and S0s or bulge dominated spirals. The subtle difference between ellipticals and early spirals (especially an increase of the blue continuum), is not appreciable in our low resolution spectra. Faint \[OII\] or $`H\alpha +[NII]`$ emission lines may be present with equivalent width less than 3 Angstroms.

Starburst (SB) – We classify as starburst those galaxies that show spectra typical of moderate to high excitation HII regions (see McCall et al. 1985 for examples of extra-galactic HII regions) or similar to the spectrum of NGC3310 (Kennicut 1992).

Post–starburst (PSB) – We find two types of post-starburst among our galaxies spectra. a) K+A galaxies which are characterized by strong $`H\delta `$ absorption superposed on a typical ETS spectrum with no emission lines. Higher order Balmer absorptions are often present implying the presence of a significant A star population which comes from a burst 0.1-1 Gyr old. b) Galaxies with spectra showing the simultaneous presence of Balmer absorptions and a moderate OII line (E+A galaxies, see Zabludoff et al. 1996). Other emission lines can be present. This is indicative of a somewhat younger burst or possibly highly reddened still active burst.

Late Type Spectrum (LTS) – Galaxies with spectra similar to those of late spirals (Sb, Sc, Scd, Sd) which are characterized (with respect to ellipticals) by a) bluer stellar continuum, b) less prominent absorption lines. Emission lines are often present (typically \[OII\], \[OIII\], and/or $`H\alpha +[NII]`$) but only in a few cases are prominent. We notice that in a number of cases it is very difficult to assess the prominence of the bulge with respect to the disk. Such objects have been included in the LTS class. As a consequence, this class is probably contaminated by earlier-type spectra, e.g. by objects with intermediate properties between the LTS and the ETS classes.

AGN – We group here objects with evident characteristics of either Seyfert 1 (Sy1) or Seyfert 2 (Sy2) or quasar (Q) spectra.

Liner (L) – There is only one evident liner (as defined in Heckman 1980) characterized by prominent emission lines from low ionization species (e.g. \[OI\]).

Examples of the spectral classes are illustrated in Fig. 3. In Table 1 we present the complete spectroscopic sample: the ATESP name is listed in Col. 1; the total flux for extended radio sources or the peak flux for point-like sources is given in Col. 2. Fluxes (1.4 GHz) are corrected for systematic underestimations due to smearing and clean bias (see Paper II for details); I and V magnitudes from the EIS catalogue are given in Cols. 3 and 4, respectively; the $`b_j`$ magnitude given in Col. 5, was obtained using the ROE/NRL COSMOS UKST Southern Sky Object Catalog (Yentis et al. 1992) at the web site of the US Naval Observatory; redshift is in Col. 6, prominent emission lines111H$`\alpha `$ is always intended as H$`\alpha `$+\[NII\]., whenever present, and the spectral class are given in Cols. 7 and 8, respectively. The last two columns report the Grism information (Col. 9) and some notes about individual spectra (Col. 10).

## 4 The ATESP-EIS Sample: Properties

The faint radio source composition resulting from the ATESP-EIS spectroscopic sample is presented in Table 2, where sub–mJy and mJy regimes have been considered separately. We notice that the good quality of the spectra allowed us to classify all objects. Our data clearly show that the AGN contribution does not significantly change going to fainter fluxes ($`89\%`$). The same is true for late type (LTS) objects (which go from 20% to 25%). This can be due to the fact that this spectral class is probably contaminated by objects with earlier type spectra (see discussion in Sect. 3.1). More meaningful is therefore a direct comparison between the class of early type (ETS) galaxies and the starburst + post-starburst (SB + PSB) one. Early type galaxies largely dominate (60%) the mJy population, while star-formation processes become important in the sub–mJy regime: SB and post-SB galaxies go from 13% at $`S1`$ mJy to 39% at $`S<1`$ mJy. Nevertheless, at sub–mJy fluxes, early type galaxies still constitute a significant fraction (25%) of the whole population.

In Fig. 4 we plot the radio flux densities against the I magnitudes for the whole sample. Superimposed are the lines representing constant values for the radio-to-optical ratios, defined following Condon (1980) as

$$R=S10^{0.4(I12.5)},$$
(1)
where $`S`$ is the 1.4 GHz flux in mJy and $`I`$ is the magnitude. In Fig. 4 the sudden change in the radio source composition going from the mJy to the sub–mJy regime is immediately evident. From a closer inspection, though, it also appears that the fraction of sub–mJy sources with early type spectrum becomes more important going to fainter magnitudes. In fact at sub-mJy fluxes the number ratio of star-forming (filled squares) over early type (empty circles) galaxies is $`2:1`$ for $`I<18`$ (8 SB/PSB galaxies against 4 ETS galaxies), while a reversed ratio is found for $`I>18`$ (2 ETS against 1 SB). The latter result, even though based on a very small number of objects, may indicate that star-forming galaxies actually dominate the sub–mJy population only at bright magnitudes, as also found by Gruppioni et al. (1999) in the radio-optical study of the Marano Field (see discussion in Sect. 5).

The fact that star-forming galaxies dominate our sub–mJy sample only at bright magnitudes is reflected also in the redshift distribution of the different spectral classes (shown in Fig. 5). The median redshift distribution of the whole sample is z=0.20; but starburst and post-starburst galaxies are nearer than early type galaxies. Such a trend was also found in previous studies of sub–mJy (Gruppioni et al. 1999) and mJy (Magliocchetti et al. 2000) samples.

In Fig. 6 we show the radio power distribution of the different spectral classes. These distributions reflect the radio luminosity properties of the different classes. In particular, all starburst and post-starburst galaxies have powers $`P<10^{23.5}`$ W/Hz, while the classes of early type objects and AGNs extend up to $`P10^{25.5}`$ W/Hz. Both results are in very good agreement with the luminosity functions derived from local samples of radio sources: star-forming galaxies mostly contribute at radio powers $`P<10^{23}`$ W/Hz (and become negligible in number at $`P>10^{24}`$ W/Hz), while early type galaxies show a much flatter distribution in radio power, extending up to $`P>10^{26}`$ W/Hz (e.g. Condon 1989). The class of late type objects cover a larger range in radio power than the class of starbursts and post-SBs, supporting the hypothesis that this class can be contaminated by earlier type objects.

Figs. 4 and 6 indicate a possible physical interpretation for the different composition found going from mJy to sub–mJy fluxes, and its possible dependence on the optical magnitude. Star-forming galaxies, characterized by weak intrinsic radio emission, have low radio-to-optical ratios (typically $`10<R<100`$, see Fig. 4), while early type galaxies cover a much larger range in radio power, and hence in R, becoming the dominant population at $`R>100`$. If this behaviour holds going to fainter fluxes and magnitudes, sub–mJy samples with fainter spectroscopic follow-ups should be increasingly sensitive to the population of early type galaxies, while, at a given optical limit, a larger fraction of star-forming galaxies would be expected in $`\mu `$Jy samples, as supported by the study of the $`\mu `$Jy sources in the Hubble Deep Field, the majority of which seem to be associated with star-forming galaxies (Richards et al. 1999).

This hypothesis is also supported by Fig. 7, where we present the distribution in $`R`$ for both the sample of all the radio sources identified down to $`I=22.5`$ (empty histogram) and the 70 objects of the spectroscopic sample ($`I<19.0`$) (shaded histogram). In fact the spectroscopic sample essentially exhausts the objects with low radio-to-optical ratio, while the optically fainter objects mostly have $`R>>100`$. This indicates, even accounting for some evolution, that they are essentially early type galaxies or AGN’s. Deeper spectroscopy for the ATESP-EIS sample will be crucial in order to verify this indication on a reliable statistical basis and to quantify the importance of evolutionary effects in the faint radio population.

As a final remark we notice that the position of the only object with no spectroscopy available in the flux-magnitude diagram (filled circle at $`R4000`$), together with a double-component radio morphology, points toward a nuclear origin for its radio emission.

## 5 The mJy and sub–mJy Population

As already discussed in Sect. 1, the results obtained from the study of faint radio samples are not completely in agreement with each other and therefore the nature of the mJy and sub–mJy radio population is not yet conclusively established. This is due to both the limited size of the faintest radio surveys and to the limited optical follow-up available.

The possibility that selection effects could play an important role in this kind of study, was first recognized by Gruppioni et al. (1999) from the study of the Marano Field. They found a higher fraction of early type galaxies than in previous studies: 50% of the sources identified have colours and spectral features typical of early type galaxies, against e.g., the 9% found by Benn et al. (1993). According to the authors, this discrepancy can very likely be ascribed to the deeper optical magnitude limit reached in the Marano Field, since the fraction of sources identified with early type galaxies abruptly increases at magnitudes $`B>22`$, which is approximately the limit of the sample studied by Benn et al. (1993).

In order to properly compare the results reported in the literature, it is therefore very important to take into account the differences in limiting flux and magnitude of the available radio samples.

If we assume (as suggested in Sect. 4) that a radio-to-optical ratio $`R100`$ separates the locus where the star-forming population dominates ($`R<100`$) from the one dominated by the early-type population ($`R>100`$), we can set a limit on the brightest limiting magnitude required in the spectroscopy follow-up, in order to make the radio-optical sub–mJy studies increasingly sensitive to the early-type population. Inverting Eq. (1), we find

$$I_{100}>17.52.5\mathrm{log}S$$
(2)
where $`I_{100}`$ is defined as the magnitude limit corresponding to $`R>100`$ and depends on the radio flux $`S`$.

In Table 3 (Column 3) we report the different values of $`I_{100}`$ computed assuming $`S=S_{lim}`$ ($`S_{lim}`$ is given in Column 2) of the most recent 1.4 GHz mJy and sub–mJy samples with radio-optical studies available. The samples are sorted on increasing values of the quantity $`I_{lim}I_{100}`$ ($`\mathrm{\Delta }I`$ in Column 5), where $`I_{lim}`$ is the limiting magnitude of spectroscopic follow-up in each sample. To make the comparison among the different samples easier we translated all the limiting magnitudes to I-band values, assuming indicatively $`RI=0.5`$ and $`BI=1.5`$. In the following columns we give the relative fractions for the different classes of objects found in each sample. To allow for the many sub-classes defined by different authors we grouped the objects in three main classes: Early Type galaxies (E), Late Type galaxies (L) and Active Galactic Nuclei (AGN). The Late Type class contains starburst, post-starburst and normal spirals. The fourth class (O) contains any other kind of object which cannot be included in the first three classes. Besides a number of objects classified as stars, they are mostly unclassified objects due to failed and/or poor quality spectra.

Under the hypothesis that the important issue in determining the composition of the faint radio population it is neither the radio flux nor the optical magnitude, but a combination of the two quantities, the relative importance of early type objects should increase with increasing $`\mathrm{\Delta }I`$, that is going through the table, from the B93 sample (the one studied by Benn. et al. 1993) to the Marano Field (MF, Gruppioni et al. 1999). Even if the differences among the quoted fractions in the different samples are not statistically relevant due to the poor number of objects involved, it is interesting to note that this trend is confirmed for both the mJy and the sub–mJy sample. The only exception is represented by the Phoenix Deep Field (PDF, Georgakakis et al. 1999), where a fraction of early type objects smaller than expected is found. It is worth noticing though that the high percentage of unclassified objects makes the PDF result quite uncertain. This uncertainty is probably more severe for the class of the early type galaxies. In fact most of the failed and/or poor quality spectra correspond to objects with very faint magnitudes, where many early type objects are expected. Another bias against early type objects is the fact that pure absorption spectra (typical of early type galaxies) are more difficult to obtain than emission line spectra (typical of late type objects and AGNs). The same uncertainty affects the numbers reported for the Benn et al. sample, where the quoted fractions have to be considered as lower limits. With this caveat, the expected trend for a decreasing fraction of Late-type objects at sub–mJy fluxes with increasing $`\mathrm{\Delta }I`$ is verified.

Very interesting is the fact that the fraction of AGNs is very similar (10-15%) in all the samples and in both flux regimes. This class is also probably the least affected by uncertainties due to poor spectroscopy, because in general AGNs show very strong emission lines. Since these faint radio surveys are mostly sensitive to small radio-to-optical ratios ($`R<1000`$), this result can give a reliable constraint on the number density of low luminosity AGNs.

With this kind of arguments it is also possible to explain the general trend for higher fractions of early type objects at mJy fluxes than at sub–mJy fluxes: at $`S1`$ mJy the $`R<100`$ population is expected at very bright magnitudes ($`I<I_{100}17.5`$), where the existing samples (covering areas from a fraction of a sq. degr. to a few sq. degr.) are severely volume limited.

This analysis seems to be able to reconcile, at least qualitatively, the discrepancies found in the literature about the nature of the faint radio sources. In particular it is very promising that in the two samples where the change of the population with the optical magnitude has been investigated (the ATESP-EIS and the MF) the computed values for $`I_{100}`$ corresponds very well to the magnitude where the change has been found. In the ATESP-EIS we found an increase of early type objects at $`I>18`$ (to be compared with $`I_{100}=18.3`$), while in the MF the same increase is found at $`R>20`$ (see Fig. 4(b) in Gruppioni et al. 1999), roughly corresponding to $`I>19.5`$ (to be compared with $`I_{100}=19.3`$).

As a final remark we notice that the strong decrease at faint magnitudes in the distribution of identified radio sources as a function of I magnitude shown in Fig. 2 can be explained, when we consider that at $`I>20`$ the ATESP-EIS sample is sensitive only to radio sources with $`R>5001000`$ at fluxes of the order of $`0.51`$ mJy. Such values correspond to early type galaxies and/or AGNs, which are not the dominant population in optically selected samples like the EIS. A similar result was found by Georgakakis et al. (1999) in the PDF sample, where the proportion of star-forming galaxies was found to decrease relative to those of early type systems and AGNs at magnitudes $`R>19.5`$. On the other hand, the authors could not draw firm conclusions from this result due to selection effects and incompleteness severely affecting their sample at these magnitudes. From our analysis we can argue that the decrement of star-forming galaxies found in the PDF sample at $`R>19.5`$ is probably mostly real, since we expect this sample to become increasingly insensitive to star-forming galaxies at magnitudes $`I>I_{100}=19.3`$ (or $`R>19.8`$).

## 6 Conclusions

We have studied the radio-optical properties of a magnitude limited sample of 70 radio sources with spectroscopy available ($`I<19.0`$). From our analysis we find that the composition of the faint radio sources abruptly changes going from mJy to sub–mJy fluxes: the early type galaxies largely dominate the mJy population ($`60\%`$), while star forming processes become important in the sub–mJy regime. Starburst and post-starburst galaxies go from 13% at $`S1`$ mJy to 39% at $`S<1`$ mJy. Nevertheless, at sub–mJy fluxes, early type galaxies still constitute a significant fraction (25%) of the whole population.

We argue that the relative fractions found for the two classes of star-forming and early type galaxies mainly depend on the fact that star-forming galaxies dominate at low radio-to-optical ratios ($`R<100`$), while early type objects dominate at $`R>100`$. Under this hypothesis it is possible to reconcile the discrepancies found from the radio-optical analysis of different sub–mJy radio samples, by taking into account the differences in limiting radio flux and optical magnitude.

If this behaviour holds going to $`\mu `$Jy fluxes and to fainter magnitudes than reached by current studies, we expect that faint radio samples with fainter spectroscopic follow-ups will be increasingly sensitive to the population of early type galaxies, with a larger fraction of star-forming galaxies in $`\mu `$Jy samples (given the same optical limiting magnitude). In particular, for a given radio sample, it would be possible to estimate a critical value for the optical magnitude, corresponding to the transition from star-forming to early type galaxy population: at brighter magnitudes the dominant class would be the one of star-forming galaxies, while at fainter magnitudes the early type galaxies would become the main class. This would also correspond to a limit in redshift for the star-forming class that populate a given faint radio sample. In other words, studies based on the star-forming portion of sub–mJy samples (like f.i. the analysis of the evolution of the star formation rate with the cosmic time) can give information up to limited redshifts ($`z<0.5`$), while larger redshift values (up to $`z1`$) can be probed only by $`\mu `$Jy samples.

In order to verify this hypothesis and check whether evolutionary effects could play an important role in changing this scenario, complete optical follow-ups down to very faint magnitudes ($`I>25`$) for statistically relevant faint radio samples are needed. To avoid bias and/or incompleteness effects at the faintest magnitudes it is also very important to obtain good quality spectroscopy.

###### Acknowledgements.

EIS observations have been carried out using the ESO New Technology Telescope (NTT) at the La Silla observatory under Program-ID Nos. 59.A-9005(A) and 60.A-9005(A). I.P. thanks the ESO staff and all the people directly and indirectly involved in the EIS Imaging Survey for their hospitality and support, during the period spent in Garching as a member of the EIS team.
The spectroscopy data were taken at the 3.6 m telescope at ESO La Silla Observatory under the ESO program identifications 62.O-0883, 63.O-0467(A) and 64.O-0258(A). We thank the ESP team, and in particular Elena Zucca and Roberto Merighi, for providing detailed information about the ESP spectra used in this work. Roberto Fanti is acknowledged for many useful comments. We are grateful to the anonymous referee for a number of useful suggestions.
The authors acknowledge the Italian Ministry for University and Scientific Research (MURST) for partial financial support (grant COFIN 99-02-37).