text:
# Finite Metric Spaces—Combinatorics,Geometry and Algorithms

## 1. Introduction

The constantly intensifying ties between combinatorics and geometry are among the most significant developments in Discrete Mathematics in recent years. These connections are manifold, and it is, perhaps, still too early to fully evaluate this relationship. This article deals only with what might be called the geometrization of combinatorics. Namely, the idea that viewing combinatorial objects from a geometric perspective often yields unexpected insights. Even more concretely, we concentrate on finite metric spaces and their embeddings.

To illustrate the underlying idea, it may be best to begin with a practical problem. There are many disciplines, scientific, technological, economic and others, which crucially depend on the analysis of large bodies of data. Technological advances have made it possible to collect enormous amounts of interesting data, and further progress depends on our ability to organize and classify these data so as to allow meaningful and insightful analysis. A case in point is bioinformatics where huge bodies of data - DNA sequences, protein sequences, information about expression levels etc. all await analysis. Let us consider, for example, the space of all proteins. For the purpose of the current discussion, a protein may be viewed as a word in an alphabet of 20 letters (amino acids). Word lengths vary from under fifty to several thousands, the most typical length being several hundred letters. At this writing, there are about half a million proteins whose sequence is known. Algorithms were developed over the years to evaluate the similarity of different proteins, and there are standard computer programs that calculate distances among proteins very efficiently. This turns the collection of all known proteins into a metric space of about half a million elements. Proper analysis of this space is of great importance for the biological sciences. Thus, this huge body of sequence data takes a geometric form, namely, a finite metric space, and it becomes feasible to use geometric concepts and tools in the analysis of this data.

In the combinatorial realm proper, and in the design and analysis of algorithms, similar ideas have proved very useful as well. A graph is completely characterized by its (shortest path, or geodesic) metric. The analysis of this metric provides a lot of useful information about the graph. Moreover, given a graph $`G`$, one may modify $`G`$’s metric by assigning nonnegative lengths to $`G`$’s edges. By varying these edge lengths, a family of finite metrics is obtained, the properties of which reflect a good deal of structural information about $`G`$. We mention in passing that there are other useful and interesting geometric viewpoints of graphs. Thus, it is useful to geometrically realize a graph by assigning vectors to the vertices and posit that adjacent vertices correspond to orthogonal vectors. Graphs can encode the intersection patterns of geometric objects. These are all interesting instances of our basic paradigm: In the study of combinatorial objects, and especially graphs, it is often beneficial to develop a perspective from which the graph is perceived geometrically.

Aside from what has already been thus accomplished, this approach holds a great promise. Combinatorics as we know it, is still a very young subject. (There is no official date of birth, and Euler was undoubtedly a giant in our field, but I think that the dawn of modern combinatorics can be dated to the 1930’s). Discrete Mathematics stands to gain a lot from interactions with older, better established fields. This geometrization of combinatorics indeed creates clear and tangible connections with various subfields of geometry. So far the study of finite metric spaces has had substantial connections with the theory of finite-dimensional normed spaces, but it seems safe to predict that useful ties with differential geometry will soon emerge. With the possible incorporation of probabilistic tools, now commonplace in combinatorics, we can expect very exciting outcomes.

A good sign for the vitality of this area is the large number of intriguing open problems. We will present here some of those that we particularly like. In a recent meeting (Haifa, March ’02), a list of open problems in this area has been collected, see http://www.kam.mff.cuni.cz/$`\stackrel{~}{}`$matousek/haifaop.ps. More extensive surveys of this area can be found in \[Mat02\] Chapter 15, and \[Ind01\].

In view of this description, it should not come as a surprise to the reader that this theory is characterized as being

* Asymptotic: We are mostly interested in analyzing large, finite metric spaces, graphs and data sets.
* Approximate: While it is possible to postulate that the geometric situation agrees perfectly with the combinatorics, it is much more beneficial to investigate the approximate version. This leads to a richer theory that is quantitative in nature. Rather than a binary question whether perfect mimicking is possible or not, we ask how well a given combinatorial object can be approximated geometrically.
* Algorithmic: Existential results are very important and interesting in this area, but we always prefer it when such a result is accompanied by an efficient algorithm.
* It is mostly comparative: There are certain classes of finite metric spaces that we favor. These may have a particularly simple structure or be very well understood. Other, less well behaved spaces are being compared to, and approximated by, these “nice” metrics.

So, how should we compare between two metrics? Let $`(X,d)`$ and $`(Y,\rho )`$ be two metric spaces and let $`\phi :XY`$ be a mapping between them. We quantify the extent to which $`\phi `$ expands, resp. contracts distances: $`\text{expansion}(\phi )=sup_{x,yX}\frac{\rho (\phi (x),\phi (y))}{d(x,y)}`$ and $`\text{contraction}(\phi )=sup_{x,yX}\frac{d(x,y)}{\rho (\phi (x),\phi (y))}`$.

Finally, the main definition is: $`\text{distortion}(\phi )=\text{expansion}(\phi )\text{contraction}(\phi )`$.

In other words, we consider the tightest constants $`\alpha \beta `$ for which $`\alpha \frac{\rho (\phi (x),\phi (y))}{d(x,y)}\beta `$ always holds, and define $`\text{distortion}(\phi )`$ as $`\frac{\alpha }{\beta }`$. We call $`\phi `$ an isometry when $`\text{distortion}(\phi )=1`$. This deviates somewhat from the conventional definition, and a map that multiplies all distances by a constant (not necessarily $`1`$) is being considered here as an isometry.

The least distortion with which $`(X,d)`$ can be embedded in $`(Y,\rho )`$ is denoted $`c_Y(X)=c_Y(X,d)`$. If $`𝒞`$ is a class of metric spaces, then the infimum of $`c_Y(X)`$ over all $`Y𝒞`$ is denoted by $`c_𝒞(X)`$. When $`𝒞`$ is the class of finite-dimensional $`l_p`$ spaces $`\{l_p^n|n=1,2,\mathrm{}\}`$ we denote $`c_𝒞(X)`$ by $`c_p(X)`$.

One of the major problems in this area is:

###### Problem 1.

Given a finite metric space $`(X,d)`$ and a class of metrics $`𝒞`$, find the (nearly) best approximation for $`X`$ by a metric from $`𝒞`$. In other words, find a metric space $`Y𝒞`$ and a map $`\phi :XY`$ such that $`\text{distortion}(\phi )`$ (nearly) equals $`c_𝒞(X)`$.

The classes of metric spaces $`𝒞`$ for which this problem has so far been studied are: (i) Metrics of normed spaces, especially $`l_p^n`$ for $`\mathrm{}p1`$ and $`n=1,2,\mathrm{}`$. (ii) Metrics of special families of graphs, most notably trees, as well as convex combinations thereof.

One more convention: Speaking of $`l_p`$, either means infinite dimensional $`l_p`$, or, what is often the same, that we do not care about the dimension of the space in which we embed a given metric.

To get a first feeling for this subject, let us consider the smallest nontrivial example. Every $`3`$-point metric embeds isometrically into the plane, but as we show now, the metric of $`K_{1,3}`$, the $`4`$-vertex tree with a root and three leaves, has no isometric embedding into $`l_2`$. Let $`x`$, resp. $`y_i`$ be the image of the root and the leaves of this tree. Since $`d(x,y_i)=1`$ and $`d(y_i,y_j)=2`$ for all $`ij`$, it follows that the three points $`x,y_i,y_j`$ are colinear for every $`ij`$. Thus, all four points are colinear, leading to a contradiction. It can be shown that the least distorted image of this graph in $`l_2`$ is in the plane with $`120^{}`$ degree angle among the edges. Below (Section 2.) we present a polynomial-time algorithm that determines $`c_2(X)`$, the least $`l_2`$ distortion for any finite metric $`(X,d)`$.

Another easy fact which belongs into this warm-up section is that $`c_{\mathrm{}}(X)=1`$ for every finite metric $`(X,d)`$. That is, the space $`l_{\mathrm{}}`$ space contains an isometric copy of every finite metric space.
Acknowledgment: Helpful remarks on this article by R. Krauthgamer, A. Magen, J. Matoušek, and Yu. Rabinovich are gratefully acknowledged.

## 2. Embedding into $`𝒍_\mathrm{𝟐}`$

This is by far the most developed part of the theory. There are several good reasons for this part of the theory to have attracted the most attention so far. Consider the practical context, where a metric space represents some large data set, and where the major driving force is the search for good algorithms for data analysis. If the data set you need to analyze happens to be a large set of points in $`l_2`$, there are many tools at your disposal, from geometry, algebra and analysis. So if your data can be well approximated in $`l_2`$, this is of great practical advantage. There is another reason for the special status of $`l_2`$ in this area. To explain it, we need to introduce some terminology from Banach space theory. The Banach-Mazur distance among two normed spaces $`X`$ and $`Y`$, is said to be $`c`$, if there is a linear map $`\phi :XY`$ with $`\text{distortion}(\phi )c`$. What we are doing here may very well be described as a search for the metric counterpart of this highly developed linear theory. See \[MS86\] for an introduction to this field and \[BL00\] for a comprehensive cover of the nonlinear theory. The grandfather of the linear theory is the celebrated theorem of Dvoretzky \[Dvo61\].

###### Theorem 1 (Dvoretzky).

For every $`n`$ and $`ϵ>0`$, every $`n`$-dimensional normed space contains a $`k=\mathrm{\Omega }(ϵ^2\mathrm{log}n)`$-dimensional space whose Banach-Mazur distance from $`l_2`$ is $`1+ϵ`$.

Thus, among embeddings into normed spaces, embeddings into $`l_2`$ are the hardest to come by.

We begin our story with an important theorem of Bourgain \[Bou85\].

###### Theorem 2.

Every $`n`$-point metric space 111Here and elsewhere, unless otherwise stated, $`n=|X|`$, the cardinality of the metric space in question. embeds in $`l_2`$ with distortion $`O(\mathrm{log}n)`$.

Not only is this a fundamental result, Bourgain’s proof of the theorem readily translates into an efficient randomized algorithm that finds, for any given finite $`(X,d)`$ an embedding in $`l_2`$ of distortion $`O(\mathrm{log}n)`$. The algorithm is so simple that we record it here. Given the metric space $`(X,d)`$, we map every point $`xX`$ to $`\phi (x)`$, an $`O(\mathrm{log}^2n)`$-dimensional vector. Coordinates in $`\phi ()`$ correspond to subsets $`SX`$, and the $`S`$-th coordinate in $`\phi (x)`$ is simply $`d(x,S)`$, the minimum of $`d(x,y)`$ over all $`yS`$. To define the map $`\phi `$, we need to specify, then, the collection of subsets $`S`$ that we utilize. These sets are selected randomly. Namely, you randomly select $`O(\mathrm{log}n)`$ sets of size $`1`$, another $`O(\mathrm{log}n)`$ sets of size $`2`$, of size $`4,8\mathrm{},\frac{n}{2}`$.

In view of Bourgain’s Theorem, several questions suggest themselves naturally:

* Is this bound tight? The answer is positive, see Theorem 3.
* Given that $`\mathrm{max}c_2(X)`$ over all $`n`$-point metrics is $`\mathrm{\Theta }(\mathrm{log}n)`$, what about metrics that are closer to $`l_2`$? Is there a polynomial-time algorithm to compute $`c_2(X,d)`$ (That is, the least distortion in an embedding of $`X`$ into $`l_2`$)? Again the answer is affirmative, see below and Theorem 4.
* Are there interesting families of metric spaces for which $`c_2`$ is substantially smaller than $`\mathrm{log}n`$? Indeed, there are, see, e.g., Theorem 5.

So let us proceed with the answers to these questions. Expanders are graphs which cannot be disconnected into two large subgraphs by removing relatively few edges. Specifically, a graph $`G`$ on $`n`$ vertices is said to be an $`ϵ`$-(edge)-expander if, for every set $`S`$ of $`n/2`$ vertices, there are at least $`ϵ|S|`$ edges between $`S`$ and its complement. It is said to be $`k`$-regular if every vertex has exactly $`k`$ neighbors. The theory of expander graphs is a fascinating chapter in discrete mathematics and theoretical computer science. It is not obvious that arbitrarily large $`k`$-regular graphs exist with expansion $`ϵ`$ bounded away from zero. In fact, in the early days of this area, conjectures to the contrary had been made. It turns out, however, that expanders are rather ubiquitous. For every $`k3`$, the probability that a randomly chosen $`k`$-regular graph has expansion $`ϵ>k/10`$ tends to $`1`$ as the number of vertices $`n`$ tends to $`\mathrm{}`$. It turns out that the metrics of expander graphs are as far from $`l_2`$ as possible. 222We freely interchange between a graph and its (shortest path) metric.

###### Theorem 3 (\[LLR95\], see also \[Mat97, LM00\]).

Let $`G`$ be an $`n`$-vertex $`k`$-regular $`ϵ`$-expander graph ($`k3`$, $`ϵ>0`$). Then $`c_2(G)c\mathrm{log}n`$ where $`c`$ depends only on $`k`$ and $`ϵ`$.

Metric geometry is by no means a new subject, and indeed metrics that embed isometrically into $`l_2`$ were characterized long ago (see e.g. \[Blu70\]). This is a special case of the more recent results. Let $`\phi :Xl_2^n`$ be an embedding. The condition that $`\text{distortion}(\phi )c`$ can be expressed as a system of linear inequalities in the entries of the Gram matrix corresponding to the vectors in $`\phi (X)`$. Therefore, the computation of $`c_2(X)`$ is an instance of semidefinite quadratic programming and can be found in polynomial time. 333This is not quite accurate. Given an $`n`$-point space $`(X,d)`$ and $`ϵ>0`$, the algorithm can determine $`c_2(X,d)`$ with relative error $`<ϵ`$ in time polynomial in $`n`$ and $`\frac{1}{ϵ}`$. This formulation of the problem has, however, other useful consequences. The duality principle of convex programming yields a max-min formula for $`c_2`$.

###### Theorem 4 (\[LLR95\]).

For every finite metric space $`(X,d)`$,

$$c_2(X,d)=\mathrm{max}\sqrt{\frac{_{i,j:q_{i,j}>0}d^2(i,j)q_{i,j}}{_{i,j:q_{i,j}<0}d^2(i,j)|q_{i,j}|}},$$

where the maximum is over all matrices $`Q`$ so that

1. $`Q`$ is positive semidefinite, and
2. The entries in every row in $`Q`$ sum to zero.

Consider the metric of the $`r`$-dimensional cube. As shown by Enflo \[Enf69\], the least distorted embedding of this metric is simply the identity map into $`l_2^r`$, which has distortion $`\sqrt{r}`$. Our first illustration for the power of the quadratic programming method is that we provide a quick elementary proof for this fact, earlier proofs of which required heavier machinery. The rows and columns of the matrix $`Q`$ are indexed by the $`2^r`$ vertices of the $`r`$-dimensional cube. The $`(x,y)`$ entry of $`Q`$ is: (i) $`r1`$ if $`x=y`$, (ii) It is $`1`$ if $`x`$ and $`y`$ are neighbors (they are represented by two $`0,1`$ vectors that differ in exactly one coordinate, and (iii) It is $`1`$ if $`x`$ and $`y`$ are antipodal, i.e., they differ in all $`r`$ coordinates. (iv) All other entries of $`Q`$ are zero. We leave out the details and only indicate how to prove that $`Q`$ is positive semidefinite. It is possible to express $`Q=(r1)IA+P`$, where $`A`$ is the adjacency matrix of the $`r`$-cube and $`P`$ is the (permutation) matrix corresponding to being antipodal. The eigenfunctions of $`A`$ are well known, namely, they are the $`2^r`$ Walsh functions. The same vectors happen to be also the eigenvectors of $`Q`$ and all have nonnegative eigenvalues.

As another application of this method (also from \[LM00\]), here is a quick proof of Theorem 3. It is known \[Alo86\] that if $`G`$ is a $`k`$-regular $`ϵ`$-expander graph and $`A`$ is $`G`$’s adjacency matrix, then the second eigenvalue of $`A`$ is $`<k\delta `$ for some $`\delta `$ that depends on $`k`$ and $`ϵ`$, but not on the size of the graph 444$`A`$’s first eigenvalue is clearly $`k`$. This is the combinatorial analogue of Cheeger’s Theorem \[Che70\] about the spectrum of the Laplacian.. It is not hard to show that the vertices of a graph with bounded degrees can be paired up so that every two paired vertices are at distance $`\mathrm{\Omega }(\mathrm{log}n)`$. Let $`P`$ be the permutation matrix corresponding to such a pairing. It is not hard to establish Theorem 3 using the matrix $`Q=kIA+\frac{\delta }{2}(PI)`$. More sophisticated applications of this method will be described below (Theorem 7).

## 3. Specific families of graph metrics

For various graph families, it is possible find embeddings into $`l_2`$ with distortion asymptotically smaller than $`\mathrm{log}n`$. This often applies as well to graphs with arbitrary nonnegative edge lengths.

### 3.1. Trees

The metrics of trees are quite restricted. They can be characterized through a four-term inequality (e.g. \[DL97\]). It is also not hard to see that every tree metric embeds isometrically into $`l_1`$. They can also be embedded into $`l_2`$ with a relatively low distortion.

###### Theorem 5 (Matoušek \[Mat99\]).

Every tree on $`n`$ vertices can be embedded into $`l_2`$ with distortion $`O(\sqrt{\mathrm{log}\mathrm{log}n})`$.

Bourgain \[Bou86\] had earlier shown that this bound is attained for complete binary trees. (See \[LS\] for an elementary proof of this.)

### 3.2. Planar graphs

It turns out that the metrics of planar graphs have good embedding into $`l_2`$. Rao \[Rao99\] showed:

###### Theorem 6.

Every planar graph embeds in $`l_2`$ with distortion $`O(\sqrt{\mathrm{log}n})`$.

A recent construction of Newman and Rabinovich \[NR02\] shows that this bound is tight.

### 3.3. Graphs of high girth

The girth of a graph is the length of the shortest cycle in the graph. If you restrict your attention (as we do in this section) to graphs in which all vertex degrees are $`3`$, then it is still a major challenge to construct graphs with very high girth, i.e., having no short cycles. The metrics of such graphs seem far from $`l_2`$, so in \[LLR95\] it was conjectured that $`c_2(G)\mathrm{\Omega }(g)`$ for every graph $`G`$ of girth $`g`$ in which all vertex degrees are $`3`$. There are known examples of $`n`$-vertex $`k`$-regular expanders whose girth is $`\mathrm{\Omega }(\mathrm{log}n)`$. In view of Theorem 2, such graphs show that this conjecture, if true, is best possible. Recently, the following was shown:

###### Theorem 7 (\[LMN\]).

Let $`G`$ be a $`k`$-regular graph $`k3`$ with girth $`g`$. Then $`c_2(G)\mathrm{\Omega }(\sqrt{g})`$.

Two proofs of this theorem are given in \[LMN\]. One is based on the notion of Markov Type due to Ball \[Bal92\]. The underlying idea of this proof is that a random walk on a graph with girth $`g`$ and all vertex degree $`3`$ drifts at a constant speed away from its starting point for time $`\mathrm{\Omega }(g)`$. On the other hand, in an appropriately defined class of random walks in Euclidean space, at time $`T`$ the walk is expected to be only $`O(\sqrt{T})`$ away from its origin. If we compare between the graph itself and its image under an embedding in $`l_2`$, this discrepancy must be accounted for by a metrical distortion. The comparison at time $`T=\mathrm{\Theta }(g)`$ yields a distortion of $`\mathrm{\Omega }(\sqrt{g})`$.

The other proof again employs semidefinite programming, using the matrix $`Q=\alpha IA+\beta B`$. Here $`A`$ is the graph’s adjacency matrix, and $`B`$ is a $`0,1`$ matrix where $`B_{xy}=1`$ if $`x`$ and $`y`$ are at distance $`g/2`$ in $`G`$. The parameters $`\alpha `$ and $`\beta `$ have to satisfy the two conditions from Theorem 4. A key observation is that due to the high girth, $`B`$ can be expressed as $`P_{g/2}(A)`$ where $`P_j`$ is the $`j`$-th Geronimus Polynomial, a known family of orthogonal polynomials. The proof depends on the distribution of zeros for these polynomials, and other analytical properties that they have.

Our present state of knowledge leads us to ask:

###### Open Problem 1.

How small can $`c_2(G)`$ be for a a graph $`G`$ of girth $`g`$ in which all vertices have degree $`3`$? The answer lies between $`\mathrm{\Omega }(\sqrt{g})`$ and $`O(g)`$.

An earlier result of Rabinovich and Raz \[RR98\] reveals another connection between high girth and distortion. Let $`\phi `$ be a map from a graph of girth $`g`$ to a graph of smaller Euler characteristic ($`|E||V|+1`$). Then $`\text{distortion}(\phi )\mathrm{\Omega }(g)`$.

## 4. Algorithmic applications

Among the most pleasing aspects of this field, are the many beautiful applications it has to the design of new algorithms.

### 4.1. Multicommodity flow and sparsest cuts

Flows in networks are a classical subject in discrete optimization and a topic of many investigations (see \[Sch02\] for a comprehensive coverage). You are given a network i.e., a graph with two specified vertices: The source $`s`$ and the sink $`t`$. Edges have nonnegative capacities. The objective is to ship as much of a given commodity between $`s`$ and $`t`$, subject to two conditions: (i) In every vertex other than $`s`$ and $`t`$, matter is conserved, (ii) The flow through any edge must not exceed the edge capacity. Let the set $`S`$ separate the vertices $`s`$ and $`t`$, i.e., it contains exactly one of them. Define $`S`$’s capacity as the sum of edge capacities over those edges that connect $`S`$ to its complement. The Max-flow Min-cut Theorem states that the largest possible flow equals the minimum such capacity.

Here we consider the $`k`$-commodity version: Now there are $`k`$ source-sink pairs $`s_i,t_i,i=1,2,\mathrm{},k`$ for the $`i`$-th commodity, and the $`i`$-th demand is $`D_i>0`$. We seek to determine the largest $`\varphi >0`$ for which it is possible to flow $`\varphi D_i`$ of the $`i`$-th commodity between $`s_i`$ and $`t_i`$, simultaneously for all $`ki1`$ subject to conditions (i) and (ii) above where in (ii) the total flow through an edge should not exceed its capacity. With every subset of the vertices $`S`$ we associate $`\gamma (S)=\frac{\text{cap}(S)}{\text{dem}(S)}`$. As before, $`\text{cap}(S)`$ is the sum of the capacities of edges between $`S`$ and its complement. The denominator $`\text{dem}(S)`$ is $`D_i`$ over all indices $`i`$ so that $`S`$ separates $`s_i`$ and $`t_i`$. It is trivially true that $`\varphi \gamma (S)`$, for every flow and every set $`S`$, but unlike the one-commodity case, $`\mathrm{min}\gamma (S)`$ (the sparsest cut) need not equal $`\mathrm{max}\varphi `$. As for the algorithmic perspective, finding $`\mathrm{max}\varphi `$ is a linear program, so it can be computed in polynomial time. However, it is $`NP`$-hard to determine the sparsest cut. Also, it is interesting to find out how far $`\mathrm{max}\varphi `$ and $`\mathrm{min}\gamma (S)`$ can be. Consider the case where the underlying graph is an expander, edges have unit capacities and every pair of vertices form a source-sink pair with a unit demand. It is not hard to see that in this case $`\varphi O(\frac{\mathrm{min}\gamma (S)}{\mathrm{log}n})`$. On the other hand,

###### Theorem 8 (\[LLR95\], see also \[AR98\]).

In the $`k`$-commodity problem

$$\mathrm{max}\varphi \mathrm{\Omega }(\frac{\mathrm{min}\gamma (S)}{\mathrm{log}k}).$$

We will be able to review the proof in Section 5..

### 4.2. Graph bandwidth

In this computational problem, we are presented with an $`n`$-vertex graph $`G`$. It is required to label the vertices with distinct labels from $`\{1,\mathrm{},n\}`$ so that the difference between the labels of any two adjacent vertices is not too big. Namely,

$$\text{bw}(G)=\underset{\psi }{\mathrm{min}}\underset{xyE(G)}{\mathrm{max}}|\psi (x)\psi (y)|,$$

where the minimum is over all $`1:1`$ maps $`\psi :V\{1,\mathrm{},n\}`$.

It is $`NP`$-hard to compute this parameter, and for many years no decent approximation algorithm was known. However, a recent paper by Feige \[Fei00\] provides a polylogarithmic approximation for the bandwidth. The statement of his algorithm is simple enough to be recorded here:

1. Compute (a slight modification of) the embedding $`\phi :Gl_2`$ that appears in the proof of Bourgain’s Theorem 2.
2. Select a random line $`l`$ and project $`\phi (G)`$ onto it.
3. Label the vertices of $`G`$ by the order at which their images appear along the line $`l`$.

Let $`\beta (G):=\mathrm{max}_{x,r}\frac{|B_r(x)|}{r}`$ where $`B_r(x)`$ is the set of those vertices in $`G`$ at distance $`r`$ from $`x`$. It’s easy to see that $`\text{bw}(G)\mathrm{\Omega }(\beta (G))`$ and an interesting feature of Feige’s proof is that it shows that $`\text{bw}(G)O(\beta (G)\mathrm{log}^cn)`$. His paper gives $`c=3.5`$ which was later \[DV99\] improved to $`c=3`$.

###### Open Problem 2.

Is it true that $`\text{bw}(G)O(\beta (G)\mathrm{log}n)`$?

It is not hard to see that this bound would be tight for expanders.

### 4.3. Bartal’s method

The following general structure theorem of Bartal \[Bar98\] has numerous algorithmic applications:

###### Theorem 9.

For every finite metric space $`(X,d)`$ there is a collection of trees $`\{T_i|iI\}`$, each of which has $`X`$ as its set of leaves, and positive weights $`\{p_i|iI\}`$ with $`_Ip_i=1`$. Each of these tree metrics dominates $`d`$, i.e., $`dist_{T_i}(x,y)d(x,y)`$ for every $`i`$ and every $`x,yX`$. On the other hand, for every $`x,yX`$,

$$\underset{i}{}p_idist_{T_i}(x,y)O(\mathrm{log}n\mathrm{log}\mathrm{log}nd(x,y)).$$

Bartal’s algorithmic paradigm is a general principle underlying the numerous algorithmic applications of this theorem: Given an algorithmic problem on input a graph or a general metric space $`(X,d)`$, find a collection of tree metrics $`T_i`$ and weights $`p_i`$ as in Theorem 9. Select one of the trees at random, where $`T_i`$ is selected with probability $`p_i`$. Now solve the problem for input $`T_i`$. (This description assumes, and this is often the case, that the original optimization problem is $`NP`$-hard in general, but feasible for tree metrics.

There are two features of the proof that we’d like to mention:
The trees $`T_i`$ are HST’s. In such trees, edge lengths decrease exponentially as you move from the root toward the leaves. They feature prominently in many recent developments in this area.
The proof makes substantial use of sparse decompositions of graphs. Given a graph, one seeks a probability distribution on all partitions of the vertex set, so that (i) Parts have small diameters (ii) Adjacent vertices are very likely to reside in the same part. Such partitions have proved instrumental in the design of many algorithms. In fact, an important tool in Rao’s Theorem 6 was an earlier result \[KPR93\] about the existence of very sparse partitions for the members of any minor-closed families family of graphs.

## 5. The mysterious $`𝒍_\mathrm{𝟏}`$

We know much less about metric embeddings into $`l_1`$, and the attempts to understand them give rise to many intriguing open problems. We start by defining the cut metric $`d_S`$ on $`X`$ where $`SX`$, as follows: $`d_S(x,y)=1`$ if $`x,y`$ are separated by $`S`$ and is zero otherwise. A simple, but useful observation is that the collection of all $`n`$-point metrics in $`l_1`$ form a cone $`𝒞`$ whose extreme rays are the cut metrics. 555For each $`n`$, the $`n`$-point metrics in $`l_1`$ form a cone $`𝒞_\mathrm{n}`$, but we suppress the index $`n`$. The book \[DL97\] provides a coverage of this area.

We are now able to complete the proof of Theorem 8. We retain the terminology of the discussion around that theorem. Linear programming duality yields the following alternative expression for the maximum $`k`$-commodity flow problem on $`G=(V,E)`$:

$$\mathrm{max}\varphi =\mathrm{min}\frac{_Ed(i,j)c_{ij}}{_1^kD_jd(s_j,t_j)}.$$

Here the minimum is over all graphical metrics $`d`$ on $`G`$. Namely, you assign nonnegative lengths to $`G`$’s edges and $`d`$ is the induced shortest path metric on $`G`$’s vertices. Now let $`d`$ be the graphical metric that minimizes this expression. A slight adaptation of Bourgain’s embedding algorithm yields an $`l_1`$ metric $`\rho `$ so that $`\rho (i,j)d(i,j)`$ for all $`i,j`$ and $`\rho (s_j,t_j)\mathrm{\Omega }(\frac{d(s_j,t_j)}{\mathrm{log}k})`$ for all $`j`$. But the minimum of $`\frac{_E\rho (i,j)c_{ij}}{_1^kD_j\rho (s_j,t_j)}`$ over $`l_1`$ metrics is attained for $`\rho `$ a cut metric, since cut metrics are the extreme rays of the cone of $`l_1`$ metrics $`𝒞`$. This minimum, over cut metrics is simply $`\mathrm{min}\gamma (S)`$, the sparsest cut value of the network. The conclusion follows.

The identification between $`l_1`$ metrics and the cut cone $`𝒞`$ makes it desirable to find an algorithm to solve linear optimization problems whose feasible set is this convex cone. Such an algorithm would solve at one fell swoop a host of interesting (and hard) problems such as max-cut, graph bisection and more. This hope is hard to realize, since the ellipsoid method (e.g. \[Sch02\]) applies only to convex bodies for which we have efficient membership and separation oracles. For the convex cone $`𝒞`$, that would mean that we need to efficiently determine whether a given a real symmetric matrix $`M`$, represents the metric on $`n`$ points in $`l_1`$. Moreover, if not, we ought to find a hyperplane (in $`n^2`$ dimensions) that separates $`M`$ from $`𝒞`$. Unfortunately, these questions are $`NP`$-hard (e.g. \[DL97\]). It becomes, therefore, interesting to approximate the cone $`𝒞`$. So, can we find another cone that is close to $`𝒞`$ and for which computationally efficient membership and separation oracles exist? There is a natural candidate for the job. We say that a matrix $`M`$ is in square-$`l_2`$, if there are points $`x_i`$ in $`l_2`$ such that $`M_{ij}=x_ix_j_2^2`$. Let $`𝒮`$ be the collection of all all square-$`l_2`$ matrices which are also a metric (i.e. the entries in $`M`$ also satisfy the triangle inequality). It is not hard to see that $`𝒞𝒮`$, but we ask:

###### Open Problem 3.

What is the smallest $`\alpha =\alpha (n)`$, such that every $`n\times n`$ matrix $`M𝒮`$ can be embedded in $`l_1`$ with distortion $`\alpha `$ ?

It is not hard to see that every finite $`l_2`$ metric embeds isometrically into $`l_1`$. But what about the opposite direction?

###### Open Problem 4.

Find $`\mathrm{max}c_2(X)`$ over all $`(X,d)`$ that are $`n`$-point metrics in $`l_1`$. As we saw above, for the $`n=2^r`$ vertices of the $`r`$-cube the answer is $`\sqrt{r}=\sqrt{\mathrm{log}n}`$. We suspect that this is the extreme case. No example is known where $`c_2`$ is asymptotically larger that $`\sqrt{\mathrm{log}n}`$.

### 5.1. Dimension reduction

Let us return to the applied aspect of this area. Even when a given metric space can be approximated well in some normed space, the dimension of the host space is quite significant. Data analysis and clustering in $`l_2^N`$ for large $`N`$ is by no means easy. In fact, practitioners in these areas often speak about the curse of dimensionality when they refer to this problem. In $`l_2`$ there is a basic result that answers this problem.

###### Theorem 10 (Johnson Lindenstrauss \[JL84\]).

Every $`n`$-point metric in $`l_2`$ can be embedded into $`l_2^k`$ with distortion $`<1+ϵ`$ where $`kO(\frac{\mathrm{log}n}{ϵ^2})`$.

Here, again, the proof yields an efficient randomized algorithm. Namely, select a random $`k`$-dimensional subspace and project the points to it.

What is the appropriate analogue of this theorem for $`l_1`$ metrics?

###### Open Problem 5.

What is the smallest $`k=k(n,ϵ)`$ so that every $`n`$-point metric in $`l_1`$ can be embedded into $`l_1^k`$ with distortion $`<1+ϵ`$?

We know very little at the moment, namely $`\mathrm{\Omega }(\mathrm{log}n)kO(n\mathrm{log}n)`$ for constant $`ϵ>0`$. The lower bound is trivial and the upper bound is from \[Sch87, Tal90\]. Note that if the truth is at the lower bound, then this provides an affirmative answer to Open Problem 4.

### 5.2. Planar graphs and other minor-closed families

One of the most fascinating problems about $`l_1`$ metrics is:

###### Open Problem 6.

Is there is an absolute constant $`C>0`$ so that every metric of a planar graph embeds into $`l_1`$ with distortion $`<C`$?

Even more daringly, the same can be asked for every minor-closed family of graphs. Some initial success for smaller graph families has been achieved already \[GNRS99\].

### 5.3. Large girth

Is there an analogue of Theorem 7 for embeddings into $`l_1`$?

###### Open Problem 7.

How small can $`c_1(G)`$ be for a a graph $`G`$ of girth $`g`$ in which all vertices have degree $`3`$? Specifically, can $`c_1(G)`$ stay bounded as $`g`$ tends to $`\mathrm{}`$?

## 6. Ramsey-type theorems for metric spaces

The philosophy of modern Ramsey Theory, (as developed e.g. in \[GRS90\]) can be stated as follows: Large systems necessarily contain substantial “islands of order”. Dvoretzky’s Theorem certainly falls into this circle of ideas. But what about the metric analogues?

###### Open Problem 8.

What is the largest $`f(,)`$ so that every $`n`$-point metric $`(X,d)`$ has a subset $`Y`$ of cardinality $`f(n,t)`$ with $`c_2(Y)t`$? (We mean, of course, the metric $`d`$ restricted to the set $`Y`$.)

For $`t`$ close to $`1`$, the answer is known, namely, $`f(n,t)=\mathrm{\Theta }(\mathrm{log}n)`$. For larger $`t`$ the behavior is known to be different \[BLMN\].


format: text

text:
# Positivity and Dense Matter

## I Introduction

Euclidean quantum chromodynamics (QCD) with a non-zero chemical potential has a complex measure, which has made lattice simulation particularly difficult Hands:2001jn . (For recent lattice investigation of the QCD phase boundary at finite density, see Fodor:2001au ; Allton:2002zi ). This problem is often referred to as the sign problem, because by appropriately grouping terms quantities such as the partition function can be written as a sum over real, but potentially negative, terms. (That this grouping can be accomplished is in many systems a consequence of a discrete symmetry such as parity or time-reversal invariance.) Indeterminate signs are enough to preclude use of importance sampling, the main technique for speeding up Monte Carlo integration. It is important to note that while the sign problem often arises in systems of fermions, it is neither inevitable nor inescapable. For example, in QCD at zero chemical potential and in the Hubbard model at half filling one can organize the sum so that terms are real and positive. For recent work on the sign problem, see sign .

Analytical work in color superconductivity csc  has demonstrated a rich phase structure at high density, and stimulated interest in QCD at non-zero baryon density. Several experiments have been proposed to probe matter at density of a few times nuclear matter density exper . Even rudimentary information about the behavior of dense matter would be useful to the experimental program, as well as to the study of compact astrophysical objects such as neutron stars. In an earlier paper Hong:2002nn , we showed that QCD near a Fermi surface has positive, semi-definite measure. In the limit of low energies, the contribution of the remaining modes far from the Fermi surface can be systematically expanded, using a high density effective theory previously introduced by one of us Hong:2000tn ; Hong:2000ru . This effective theory is sufficient to study phenomena like color superconductivity, although quantities like the equation of state may be largely determined by dynamics deep in the Fermi sea.

The expansion about the Fermi surface is in powers of $`1/\mu `$, where $`\mu `$ is the chemical potential. For this expansion to be controlled, the ultraviolet cutoff of our effective theory must be less than $`\mu `$, or equivalently the scale of the physics of interest must be small relative to the chemical potential. In QCD at asymptotic density, the superconducting gap is exponentially small, so this condition is satisfied. However, it is also quite possible that at intermediate densities (e.g., those inside a neutron star) the gap is somewhat smaller than $`\mu `$, providing us with an additional small dimensionless parameter. Even if this is not the case, the power expansion of the effective theory is qualitatively different from the usual perturbation in $`\alpha _s`$, and therefore worth exploring. Finally, we note that models (e.g., of electronic systems) which are not asymptotically free may exhibit strongly coupled quasiparticle excitations even at high density. The results described here still apply to such systems and may be of use in their simulation.

This paper is organized as follows. We begin in section 2 with simple examples in (1+1) and higher dimensions which illustrate how the effective Fermi surface description can have positive measure even if the original model has a sign problem. In section 3 we review the results from our previous paper, and include some discussion of how they apply to electronic systems that may arise in condensed matter. In section 4 we describe how they can be applied to lattice simulations of dense matter. In section 5 we discuss correlator inequalities (also known as QCD inequalities) that result from positivity, and how they restrict the possible ground states of QCD. In section 6 we conclude with a summary and future prospects.

## II Example: (1+1) Dimensions and Beyond

We begin with an example that illustrates the basic ideas in a simple setting. Consider the Euclidean (1+1) action of non-relativistic fermions interacting with a gauge field A

$$S=𝑑\tau 𝑑x\psi _\sigma ^{}\left[(_\tau +i\varphi +ϵ_F)ϵ(i_x+A)\right]\psi _\sigma $$
(1)
where $`ϵ(p)`$ is the energy as a function of momentum (e.g. $`ϵ(p)\frac{p^2}{2m}+\mathrm{}`$). In (1) and below we may consider it as a function of the operator ($`i_x+A`$). The dispersion relation in the presence of the chemical potential $`ϵ_F`$ is: $`E(p)=ϵ(p)ϵ_F`$, and a low energy mode must have momentum close to $`\pm p_F`$, where $`ϵ(\pm p_F)=ϵ_F`$. The Fermi surface in (1+1) dimensions is reduced to the two points $`p=\pm p_F`$. Near these points we have

$$E(p\pm p_F)\pm v_Fp,$$
(2)
where $`v_F=E/p|_{p_F}`$ is the Fermi velocity.

The action (1) is not obviously positive. In fact, the operator in brackets $`\left[\mathrm{}\right]`$ clearly has Hermitian as well as anti-Hermitian components, and hence complex eigenvalues.

Let us assume that the gauge field has small amplitude and is slowly varying relative to the scale $`p_F`$. We will extract the slowly varying component of the fermion field to construct a low energy effective theory involving quasiparticles and gauge fields. This effective theory will have positive, semi-definite determinant.

First, we extract the quasiparticle modes (we suppress the spin index in what follows)

$$\psi (x,\tau )=\psi _Le^{+ip_Fx}+\psi _Re^{ip_Fx},$$
(3)
where the functions $`\psi _{L,R}`$ are slowly varying. To simplify the action, we use the identity

$$e^{\pm ip_Fx}E(i_x+A)e^{ip_Fx}\psi (x)\pm v_F(i_x+A)\psi (x),$$
(4)
to obtain vf

$$S_{\mathrm{eff}}=𝑑\tau 𝑑x\left[\psi _L^{}(_\tau +i\varphi +i_xA)\psi _L+\psi _R^{}(_\tau +i\varphi i_x+A)\psi _R\right].$$
(5)
We can write this in a more familiar form by introducing the Euclidean (1+1) gamma matrices $`\gamma _{0,1,2}`$ , which are Hermitian and can be taken as $`\gamma _i=\sigma _i`$ where $`\stackrel{}{\sigma }`$ are the Pauli matrices. Using $`\psi _{L,R}=\frac{1}{2}(1\pm \gamma _2)\psi `$ we obtain

$$S_{\mathrm{eff}}=𝑑\tau 𝑑x\overline{\psi }\gamma ^\mu (_\mu +iA_\mu )\psi 𝑑\tau 𝑑x\overline{\psi }D/\psi .$$
(6)
Since the gamma matrices are Hermitian, and the operator $`(_\mu +iA_\mu )`$ is anti-Hermitian, the operator $`D/`$ in (6) has purely imaginary eigenvalues. However, because $`\gamma _2`$ anticommutes with $`D/`$, the eigenvalues come in conjugate pairs: given $`D/\varphi =\lambda \varphi `$, we have

$$D/(\gamma _2\varphi )=\gamma _2D/\varphi =\gamma _2\lambda \varphi =\lambda (\gamma _2\varphi _n).$$

Hence the determinant $`detD/=\lambda ^{}\lambda `$ is real and positive semi-definite.

Thus, by considering only the low-energy modes near the Fermi points of the original model (1), we obtain an effective theory with desirable positivity properties. Note that it is necessary that the interactions (in this case, the background gauge field A) not couple strongly the low-energy modes to fast modes which are far from the Fermi points. This is a reasonable approximation in many physical situations, where it is the interactions among quasiparticles that are of primary interest. In what follows, we will apply this basic idea to more complex models such as QCD.

It is straightforward to go beyond (1+1) dimensions. Consider an electron system, described by

$$=\psi ^{}\left[i_tϵ(\stackrel{}{p})\right]\psi +\mu \psi ^{}\psi ,$$
(7)
where $`ϵ(\stackrel{}{p})`$ is the electron energy, a function of momentum $`\stackrel{}{p}`$. It is interesting to note that the non-relativistic system already has a sign problem even at the zero density, $`\mu =0`$, though the free case does not suffer this, thanks to the separation of variables. In fact, it is quite unusual to have a system like vacuum QCD which has no sign problem. In Euclidean space the electron determinant is

$$M=_\tau ϵ(\stackrel{}{p})+\mu .$$
(8)
The first term in operator (8) is anti-Hermitian, while the rest are Hermitian. Since there is no constant matrix $`P`$ in the spin space that satisfies $`M^{}=PMP^1`$, it has a sign problem in general.

Let us decompose the fermion momentum as

$$\stackrel{}{p}=\stackrel{}{p}_F+\stackrel{}{l}.$$
(9)
Again, the Fermi momentum is defined to be a momentum at which the energy equals to the chemical potential at zero temperature: $`\mu =ϵ(p_F)`$, and the Fermi velocity is defined as

$`\stackrel{}{v}_F={\displaystyle \frac{ϵ(p)}{\stackrel{}{p}}}|_{p=p_F}.`$ (10)
If we are interested in low energies, $`\left|\stackrel{}{l}\right|p_F`$, we may integrate out the fast modes to get an effective operator,

$$M_{\mathrm{EFT}}=_\tau \stackrel{}{v}_F\stackrel{}{l},$$
(11)
which has complex eigenvalues. However, when we include the $`\stackrel{}{v}_F`$ sector, we have $`M_{\mathrm{EFT}}(\stackrel{}{v}_F)M_{\mathrm{EFT}}(\stackrel{}{v}_F)0`$ (i.e., has real negative eigenvalues), assuming $`ϵ(\stackrel{}{p})=ϵ(\stackrel{}{p})`$. We again see that the sign problem in the electron system is alleviated in the low-energy effective theory.

## III QCD

Let us recall why the measure of dense QCD is complex in Euclidean space. We use the following analytic continuation of the Dirac Lagrangian to Euclidean space:

$$x_0ix_E^4,x_ix_E^i;\gamma _0\gamma _E^4,\gamma _ii\gamma _E^i.$$
(12)
The Euclidean gamma matrices satisfy

$$\gamma _{E}^{\mu }{}_{}{}^{}=\gamma _E^\mu ,\{\gamma _E^\mu ,\gamma _E^\nu \}=2\delta ^{\mu \nu }.$$
(13)
The Dirac-conjugated field, $`\overline{\psi }=\psi ^{}\gamma ^0`$, is mapped into a field, still denoted as $`\overline{\psi }`$, which is independent of $`\psi `$ and transforms as $`\psi ^{}`$ under $`SO(4)`$. Then, the grand canonical partition function for QCD is

$`Z(\mu )={\displaystyle dA_\mu det\left(M\right)e^{S(A_\mu )}},`$ (14)
where $`S(A_\mu )`$ is the positive semi-definite gauge action, and the Dirac operator

$$M=\gamma _E^\mu D_E^\mu +\mu \gamma _E^4,$$
(15)
where $`D_E=_E+iA_E`$ is the analytic continuation of the covariant derivative. The Hermitian conjugate of the Dirac operator is

$$M^{}=\gamma _E^\mu D_E^\mu +\mu \gamma _E^4.$$
(16)
The first term in (15) is anti-Hermitian, while the second is Hermitian, hence the generally complex eigenvalues. When $`\mu =0`$, the eigenvalues are purely imaginary, but come in conjugate pairs $`(\lambda ,\lambda ^{})`$ ev , so the resulting determinant is real and positive semi-definite:

$$\mathrm{det}\mathrm{M}=\lambda ^{}\lambda 0.$$
(17)
In what follows we investigate the positivity properties of an effective theory describing only modes near the Fermi surface. A system of degenerate quarks with a net baryon number asymmetry is described by the QCD Lagrangian density with a chemical potential $`\mu `$,

$$_{\mathrm{QCD}}=\overline{\psi }iD/\psi \frac{1}{4}F_{\mu \nu }^aF^{a\mu \nu }+\mu \overline{\psi }\gamma _0\psi ,$$
(18)
where the covariant derivative $`D_\mu =_\mu +iA_\mu `$ and we neglect the quark mass for simplicity.

At high density ($`\mu \mathrm{\Lambda }_{\mathrm{QCD}}`$), due to asymptotic freedom the energy spectrum of quarks near the Fermi surface is approximately given by a free Dirac eigenvalue equation,

$$\left(\stackrel{}{\alpha }\stackrel{}{p}\mu \right)\psi _\pm =E_\pm \psi _\pm ,$$
(19)
where $`\stackrel{}{\alpha }=\gamma _0\stackrel{}{\gamma }`$ and $`\psi _\pm `$ denote the energy eigenfunctions with eigenvalues $`E_\pm =\mu \pm \left|\stackrel{}{p}\right|`$, respectively. At low energy $`E<\mu `$, the states $`\psi _+`$ near the Fermi surface, $`|\stackrel{}{p}|\mu `$, are easily excited but $`\psi _{}`$, which correspond to the states in the Dirac sea, are completely decoupled due to the presence of the energy gap $`\mu `$ provided by the Fermi sea. Therefore the appropriate degrees of freedom at low energy consist of gluons and $`\psi _+`$ only.

Now, we wish to construct an effective theory describing the dynamics of $`\psi _+`$ by integrating out modes whose energy is greater than $`\mu `$. Consider a quark near the Fermi surface, whose momentum is close to $`\mu \stackrel{}{v}_F`$. Without loss of generality, we may decompose the momentum of a quark into a Fermi momentum and a residual momentum as

$$p_\mu =\mu v_\mu +l_\mu ,$$
(20)
where $`v^\mu =(0,\stackrel{}{v}_F)`$. Since the quark energy is given as

$$E=\mu +\sqrt{(l_{}+\mu )^2+l_{}^2},$$
(21)
the residual momentum should satisfy $`(l_{}+\mu )^2+l_{}^24\mu ^2`$ with $`\stackrel{}{l}_{}=\stackrel{}{v}_F\stackrel{}{l}\stackrel{}{v}_F`$ and $`\stackrel{}{l}_{}=\stackrel{}{l}\stackrel{}{l}_{}`$.

To describe the small excitations of the quark with Fermi momentum, $`\mu \stackrel{}{v}_F`$, we decompose the quark fields as

$$\psi (x)=e^{i\mu \stackrel{}{v}_F\stackrel{}{x}}\left[\psi _+(\stackrel{}{v}_F,x)+\psi _{}(\stackrel{}{v}_F,x)\right],$$
(22)
where

$$\psi _\pm (\stackrel{}{v}_F,x)=P_\pm (\stackrel{}{v}_F)e^{i\mu \stackrel{}{v}_F\stackrel{}{x}}\psi (x)\mathrm{with}P_\pm (\stackrel{}{v}_F)\frac{1\pm \stackrel{}{\alpha }\stackrel{}{v}_F}{2}.$$
(23)
The quark Lagrangian in Eq. (18) then becomes

$`\overline{\psi }(iD/+\mu \gamma ^0)\psi `$ $`=`$ $`\left[\overline{\psi }_+(\stackrel{}{v}_F,x)i\gamma _{}^\mu D_\mu \psi _+(\stackrel{}{v}_F,x)+\overline{\psi }_{}(\stackrel{}{v}_F,x)\gamma ^0\left(2\mu +i\overline{D}_{}\right)\psi _{}(\stackrel{}{v}_F,x)\right]`$ (24)
$`+[\overline{\psi }_{}(\stackrel{}{v}_F,x)iD/_{}\psi _+(\stackrel{}{v}_F,x)+\mathrm{h}.\mathrm{c}.]`$
where $`\gamma _{}^\mu (\gamma ^0,\stackrel{}{v}_F\stackrel{}{v}_F\stackrel{}{\gamma })`$, $`\gamma _{}^\mu =\gamma ^\mu \gamma _{}^\mu `$, $`\overline{D}_{}=\overline{V}^\mu D_\mu `$ with $`V^\mu =(1,\stackrel{}{v}_F)`$, $`\overline{V}^\mu =(1,\stackrel{}{v}_F)`$, and $`D/_{}=\gamma _{}^\mu D_\mu `$.

At low energy, we integrate out all the “fast” modes $`\psi _{}`$ and derive the low energy effective Lagrangian by matching all the one-light-particle irreducible amplitudes containing gluons and $`\psi _+`$ in loop expansion. The effects of fast modes will appear in the quantum corrections to the couplings of low energy interactions. At tree-level, the matching is equivalent to eliminating $`\psi _{}`$ in terms of equations of motion:

$$\psi _{}(\stackrel{}{v}_F,x)=\frac{i\gamma ^0}{2\mu +iD_{}}D/_{}\psi _+(\stackrel{}{v}_F,x)=\frac{i\gamma ^0}{2\mu }\underset{n=0}{\overset{\mathrm{}}{}}\left(\frac{iD_{}}{2\mu }\right)^nD/_{}\psi _+(\stackrel{}{v}_F,x).$$
(25)
Therefore, the tree-level Lagrangian for $`\psi _+`$ becomes

$$_{\mathrm{eff}}^0=\overline{\psi }_+i\gamma _{}^\mu D_\mu \psi _+\frac{1}{2\mu }\overline{\psi }_+\gamma ^0(D/_{})^2\psi _++\mathrm{},$$
(26)
where the ellipsis denotes terms with higher derivatives.

Consider the first term in our effective Lagrangian, which when continued to Euclidean space yields the operator

$$M_{\mathrm{eft}}=\gamma _{}^ED(A).$$
(27)
$`M_{\mathrm{eft}}`$ is anti-Hermitian and it anti-commutes with $`\gamma _5`$, so it leads to a positive semi-definite determinant. However, note that the Dirac operator is not well defined in the space of $`\psi _+(\stackrel{}{v}_F,x)`$ (for fixed $`v_F`$), since it maps $`\psi _+(\stackrel{}{v}_F,x)`$ into $`\psi _+(\stackrel{}{v}_F,x)`$:

$$iD_{}/P_+\psi =P_{}iD_{}/\psi .$$
(28)
Since $`P_{}(\stackrel{}{v}_F)=P_+(\stackrel{}{v}_F)`$, $`iD/\psi _+(\stackrel{}{v}_F,x)`$ are $`\psi _+(\stackrel{}{v}_F,x)`$ modes, or fluctuations of a quark with momentum $`\mu \stackrel{}{v}_F`$.

We can demonstrate the necessity of including both $`\psi _+(\stackrel{}{v}_F,x)`$ and $`\psi _+(\stackrel{}{v}_F,x)`$ modes in our effective theory by considering charge conservation in a world with only $`+\stackrel{}{v}_F`$ quarks. The divergence of the quark current at one loop is at the leading order in the $`1/\mu `$ expansion

$$_\mu J^{a\mu }(\stackrel{}{v}_F,x)=g_s\frac{\mathrm{d}^4p}{(2\pi )^4}e^{ipx}p^\mu \mathrm{\Pi }_{\mu \nu }^{ab}(p)A_{}^{b\nu }(p),$$
(29)
where $`A_{}=(A_0,\stackrel{}{v}_F\stackrel{}{v}_F\stackrel{}{A})`$ and $`\mathrm{\Pi }_{\mu \nu }^{ab}`$ is the vacuum polarization tensor in the effective theory given as Hong:2000tn

$$\mathrm{\Pi }_{ab}^{\mu \nu }(p)=i\frac{\mu ^2}{2}\delta _{ab}\left(\frac{2\stackrel{}{p}\stackrel{}{v}_FV^\mu V^\nu }{pV+iϵ\stackrel{}{p}\stackrel{}{v}_F}+g_{}^{\mu \nu }\right),$$
(30)
where $`g_{}^{\mu \nu }=g^{\mu \nu }(V^\mu \overline{V}^\nu +\overline{V}^\mu V^\nu )/2`$ is the metric tensor perpendicular to $`V^\mu `$ and $`\overline{V}^\mu `$. The polarization tensor has to be transverse to maintain gauge invariance. We find that if we have both fields $`\psi _+(\stackrel{}{v}_F,x)`$ and $`\psi _+(\stackrel{}{v}_F,x)`$ the current is conserved and the gauge symmetry is not anomalous:

$$_\mu J_a^\mu (\stackrel{}{v}_F,x)+_\mu J_a^\mu (\stackrel{}{v}_F,x)=0.$$
(31)
Therefore, we need to introduce quark fields with opposite momenta. The Dirac operator is well defined on this larger space.

This anomaly can be understood in terms of spectral flow, since the Fermi surface is (in a certain sense) not gauge-invariant. Under a gauge transformation, $`U(x)=e^{i\stackrel{}{q}\stackrel{}{x}}`$, the Hamiltonian changes and the energy spectrum of free modes of residual momentum $`\stackrel{}{l}`$ shifts to $`E=\stackrel{}{l}\stackrel{}{v}_F+\stackrel{}{q}\stackrel{}{v}_F`$. Quarks near the Fermi surface with $`\stackrel{}{v}_F\stackrel{}{q}>0`$ flow out of the Fermi sea, creating charge. This charge creation is compensated by quarks with opposite $`\stackrel{}{v}_F`$; their energy decreases and they flow into the Fermi sea. However, unless modes with opposite velocities (i.e. both sides of the Fermi sphere) are included, charge is not conserved.

Thus far we have considered the quark velocity as a parameter labelling different sectors of the quark field. This is similar to the approach of heavy quark effective theory (HQET) Isgur:vq , in which the velocity of the heavy charm or bottom quark is almost conserved due to the hierarchy of scales between the heavy quark mass and the QCD scale. However, this approach contains an ambiguity often referred to as “reparameterization invariance”, related to the non-uniqueness of the decomposition (20) of quark momenta into a large and residual component. In the dense QCD case, two $`\psi (v_F,x)`$ modes whose values of $`v_F`$ are not very different may actually represent the same degrees of freedom of the original quark field. In what follows we give a different formulation which describes all velocity modes of the quark field, and is suitable for defining the quasiparticle determinant.

First, a more precise definition of the breakup of the quark field into Fermi surface modes. Using the momentum operator in a position eigenstate basis: $`\stackrel{}{p}=i\stackrel{}{}`$, we construct the Fermi velocity operator:

$$\stackrel{}{v}=\frac{i}{\sqrt{^2}}\frac{}{\stackrel{}{x}},$$
(32)
which is Hermitian, and a unit vector.

Using the velocity operator, we define the projection operators $`P_\pm `$ as before and break up the quark field as, $`\psi (x)=\psi _+(x)+\psi _{}(x)`$, with $`\psi _\pm =P_\pm \psi `$. By leaving $`\stackrel{}{v}`$ as an operator we can work in coordinate space without introducing the HQET-inspired velocity Fourier transform which introduces $`v_F`$ as a parameter. If we expand the quark field in the eigenstates of the velocity operators, we recover the previous formalism with all Fermi velocities summed up.

The leading low-energy part of the quark action is given by

$$_+=\overline{\psi }P_{}(v)(i/A/+\mu \gamma _0)P_+(v)\psi .$$
(33)
As before, we define the fields $`\psi _+`$ to absorb the large Fermi momentum:

$$\psi _+(x)=e^{i\mu \stackrel{}{x}\stackrel{}{v}}P_+(v)\psi (x).$$
(34)
Let us denote the eigenvalue $`v`$ obtained by acting on the field $`\psi `$ (which has momentum of order $`\mu `$) as $`v_l`$ (or $`v`$ “large”), whereas eigenvalues obtained by acting on the effective field theory modes $`\psi _+`$ are denoted $`v_r`$ (or $`v`$ “residual”). If the original quark mode had momentum p with $`|p|>\mu `$ (i.e. was a particle), then $`v_l`$ and $`v_r`$ are parallel, whereas if $`|p|<\mu `$ (as for a hole) then $`v_r`$ and $`v_l`$ are anti-parallel. In the first case, we have $`P_+(v_l)=P_+(v_r)`$ whereas in the second case $`P_+(v_l)=P_{}(v_r)`$. Thus, the residual modes $`\psi _+`$ can satisfy either of $`P_\pm (v_r)\psi _+=\psi _+`$, depending on whether the original $`\psi `$ mode from which it was derived was a particle or a hole. In fact, $`\psi _+`$ modes can also satisfy either of $`P_\pm (v_l)\psi _+=\psi _+`$ since they can originate from $`\psi `$ modes with momentum $`+\mu v`$ as well as $`\mu v`$ (both are present in the original measure: $`D\overline{\psi }D\psi `$). So, the functional measure for $`\psi _+`$ modes contains all possible spinor functions – the only restriction is on the momenta: $`|l_0|,|\stackrel{}{l}|<\mathrm{\Lambda }`$, where $`\mathrm{\Lambda }`$ is the cutoff.

In light of the ambiguity between $`v_l`$ and $`v_r`$, the equation $`\psi =e^{+i\mu xv}\psi _+`$ must be modified to

$$\psi =\mathrm{exp}\left(+i\mu xv\alpha v\right)\psi _+=\mathrm{exp}\left(+i\mu xv_r\alpha v_r\right)\psi _+,$$
(35)
where the factor of $`\alpha v_r`$ corrects the sign in the momentum shift if $`v_r`$ and $`v_l`$ are anti-parallel. In general, any expression with two powers of $`v`$ is unaffected by this ambiguity. For notational simplicity we define a local operator

$$X\mu xv\alpha v=\mu \frac{\alpha ^ix^j}{^2}\frac{^2}{x^ix^j}.$$
(36)
Taking this into account, we obtain the following action:

$$_+=\overline{\psi }_+e^{iX}(i/A/+\mu \gamma _0)e^{+iX}\psi _+.$$
(37)
We treat the $`A/`$ term separately from $`i/+\mu \gamma _0`$ since the former does not commute with X, while the latter does. Continuing to Euclidean space, and using the identity $`P_{}\gamma _\mu P_+=\gamma _\mu ^{}P_+`$, we obtain

$$_+=\overline{\psi }_+\gamma _{}^\mu \left(^\mu +iA_+^\mu \right)\psi _+,$$
(38)
where

$$A_+^\mu =e^{iX}A^\mu e^{+iX},$$
(39)
and all $`\gamma `$ matrices are Euclidean. The term containing $`A`$ cannot be fully simplified because $`[v,A]0`$. Physically, this is because the gauge field carries momentum and can deflect the quark velocity. The redefined $`\psi _+`$ modes are functions only of the residual momenta l, and the exponential factors in the A term reflect the fact that the gluon originally couples to the quark field $`\psi `$, not the residual mode $`\psi _+`$.

The kinetic term in (38) can be simplified to

$$\gamma _{}^\mu ^\mu =\gamma ^\mu ^\mu $$
(40)
since $`vv\gamma =\gamma .`$ The action (38) is the most general dimension 4 term with the rotational, gauge invariance gauge  and projection properties appropriate to quark quasiparticles. Therefore, it is a general consequence of any Fermi liquid description of quark-like excitations.

The operator in (38) is anti-Hermitian and leads to a positive, semi-definite determinant since it anti-commutes with $`\gamma _5`$. The corrections given in (26) are all Hermitian, so higher orders in the $`1/\mu `$ expansion may re-introduce complexity. The structure of the leading term plus corrections is anti-Hermitian plus Hermitian, just as in the original QCD Dirac Lagrangian with chemical potential.

By integrating out the fast modes, the Euclidean QCD partition function can be rewritten as

$`Z(\mu )={\displaystyle dA_+detM_{\mathrm{eff}}(A_+)e^{S_{\mathrm{eff}}(A_+)}}.`$ (41)
The leading terms in the effective action for gluons (these terms are generated when we match our effective theory, with energy cutoff $`\mathrm{\Lambda }`$, to QCD) also contribute only real, positive terms to the partition function:

$$S_{\mathrm{eff}}(A)=\mathrm{d}^4x_E\left(\frac{1}{4}F_{\mu \nu }^aF_{\mu \nu }^a+\frac{M^2}{16\pi }\underset{\stackrel{}{v}_F}{}A_\mu ^aA_\mu ^a\right)0,$$
(42)
where $`A_{}=AA_{}`$ and the Debye screening mass is $`M=\sqrt{N_f/(2\pi ^2)}g_s\mu `$ . Note that Landau damping is due to softer quark modes which have not been integrated out, and therefore do not contribute to matching.

Although the HDET only describes low-energy modes, it still contains Cooper pairing interactions. This is because Cooper pairing, in which the quasiparticles have nearly equal and opposite momenta, is induced by gluonic interactions with small energy and momentum transfer. That is, although a gluon exchange (or other interaction) which causes a large angular deflection of a quasiparticle

$$|\stackrel{}{p}|\stackrel{}{p}^{}$$

must involve a large momentum transfer, and hence is not part of the effective theory, a Cooper pairing interaction

$$|\stackrel{}{p},\stackrel{}{p}|\stackrel{}{p}^{},\stackrel{}{p}^{}$$

only involves a small energy and momentum transfer, even if the angle between $`\stackrel{}{p}`$ and $`\stackrel{}{p}^{}`$ is large. Hence, it is described by the leading order interaction between soft gluons and quarks in the effective theory (38).

Matching of hard gluon effects also leads to four-quark operators in the effective theory. The addition of these four-quark operators still leads to a positive action for attractive channels, since they arise from quasiparticle-gluon interactions which are originally positive. A simple way to study the positivity of four-quark operators is to replace them by a vector field with trivial quadratic term $`V_\mu ^2`$ which couples to quarks like the original gluon: $`V_\mu \overline{\psi }\gamma ^\mu \psi `$. Completing the square, we see that the resulting path integral is positive. Note that this argument does not apply to interactions involving six or more quarks, or interactions involving virtual anti-quarks. However, these are always suppressed by additional powers of $`\mu `$.

Finally, some comments on more general models than QCD – in particular electronic systems in condensed matter – which are also affected by a sign problem. We note that as long as the important dynamics of the system involve energies which are small compared to the Fermi energy (or are exhibited at a temperature small compared to the Fermi temperature), the Euclidean description of the system is likely to have a positive effective action after modes far from the Fermi surface are integrated out. Models involving, e.g., attractive four-fermion interactions or long range gauge fields fall into this category. As long as the important interactions are soft interactions between quasiparticle degrees of freedom not too far from the Fermi surface, the model can be simulated without a sign problem, even if it is strongly coupled.

As a specific example, consider the Hamiltonian

$$H=\underset{ab}{}t_{ab}c_a^{}c_b+\underset{abcd}{}v_{abcd}c_a^{}c_bc_c^{}c_d,$$
(43)
where $`\mathrm{abcd}`$ denote lattice site and spin indices. This Hamiltonian includes the Hubbard model as a special case. A constant diagonal part of the kinetic term acts as a chemical potential $`\mu =t_{aa}`$, but $`t`$ may also contain hopping terms such as a nearest-neighbor off-diagonal term in the tight binding approximation. The usual kinetic term, taken by itself, produces a band structure which in momentum space has the form

$$\underset{k}{}E(k)c_k^{}c_k,$$
(44)
for some function $`E(k)`$. A non-zero chemical potential leads to filling of levels up to some momentum $`k_F`$. There is an effective theory description of modes near this surface if the Fourier transform of the interaction term $`v_{abcd}`$ only contains soft interactions (i.e. support for typical momentum transfers less than $`k_F`$.)

To obtain the partition function Z we must extend the fields from the d-dimensional lattice to (d+1)-dimensional Euclidean space, with finite extent $`\beta `$ in the time direction. The action density is given by

$$\frac{}{\tau }$$
(45)
where $``$ is the Hamiltonian density. Using the Hubbard-Stratonovich transformation, we can rewrite the interaction term in terms of a functional integral over a background field U.

$$Z=\frac{1}{N}\underset{ab}{}dU_{ab}e^{_{cdef}U_{cd}v_{cdef}^1U_{ef}}det\left[TU\right],$$
(46)
where $`T=\frac{}{\tau }t`$ contains the time derivative as well as the kinetic term t from the Hamiltonian (43). We assume that the interaction $`v`$ is real and negative definite so that the exponential is real and the integral converges.

The determinant can be expanded about our effective theory. The leading term is positive and has no sign problem. The correction terms are suppressed as long as the background field U has support on momentum scales small compared to $`k_F`$. (See discussion in next section, especially equation (52) with U playing the role of the gauge field). Typical fields U in the integral are determined by the exponential term – if the Fourier transform of $`v`$ has little support at large momenta, then the exponent $`_kU(k)v^1(k)U(k)`$ will be large and negative, and the corresponding modes of $`U`$ suppressed.

Unfortunately, the Hubbard model itself contains the interaction term

$$V\underset{i}{}n_in_i$$
(47)
where $`n_i=c_i^{}c_i`$ is the number operator. This interaction allows all momentum transfers up to $`\pi /a`$, where $`a`$ is the lattice spacing. Because it couples low-energy modes to fast modes far from the Fermi surface, the resulting partition function isn’t well-approximated by the positive EFT part. However, a model with modified (softer) interactions would be approximately positive and might in fact be more physically realistic.

## IV Lattice Simulation

The goal of this section is to give a method for simulating QCD at finite density. We will consider a chemical potential $`\mu `$ much larger than $`\mathrm{\Lambda }_{\mathrm{QCD}}`$ throughout, and divide the functional integral over quark excitations into two parts: (I) modes within a shell of width $`\mathrm{\Lambda }`$ of the Fermi surface, and (II) modes which are further than $`\mathrm{\Lambda }`$ from the Fermi surface. We will assume the hierarchy

$$\mu >>\mathrm{\Lambda }>>\mathrm{\Lambda }_{\mathrm{QCD}}.$$
(48)
The quark determinant in region (I) is well approximated by the determinant of the leading operator in high density effective theory (HDET) as long as the first inequality in (48) is satisfied. As discussed in the previous section, it is positive and real.

Here we will show that the contributions to the effective action for the gauge field from quark modes in region (II) are small and vanish as the $`\mathrm{\Lambda }`$ grows large compared to $`\mathrm{\Lambda }_{\mathrm{QCD}}`$.

First consider the theory in Minkowski space. The Dirac operator is

$$M=iD/+\mu \gamma _0$$
(49)
and the Dirac equation can be written as

$$i_0\psi =H\psi $$
(50)
with

$$H=i\alpha \mu $$
(51)
a Hermitian operator. The break up into regions (I) and (II) proceeds naturally in terms of energy eigenvalues of H (or $`l_0`$ in the HDET notation). The low-lying modes in region (I) are particle states with spatial momenta satisfying $`|\stackrel{}{p}|\mu `$.

The analytic continuation of region (I) to Euclidean space leads to the HDET determinant considered previously.

Modes in region (II) all have large energy eigenvalues, at least as large as $`\mathrm{\Lambda }`$. In considering their effect on physics at the scale $`\mathrm{\Lambda }_{\mathrm{QCD}}`$, we can integrate them out in favor of local operators suppressed by powers of $`\mathrm{\Lambda }_{\mathrm{QCD}}/\mathrm{\Lambda }`$.

To make this concrete, consider the effective action for gauge fields with field strengths $`F_{\mu \nu }`$ of order $`\mathrm{\Lambda }_{\mathrm{QCD}}`$. The quark contribution to this effective action is simply the logarithm of the determinant we wish to compute. It can be expanded diagrammatically in graphs with external gauge field lines connected to a single quark loop. Restricting to region (II), we require that the quark modes in the loop have large H eigenvalues. Evaluating such graphs leads only to operators which are local in the external fields $`A_\mu (x)`$.

The resulting renormalizable (dimension 4) operator is the finite density equivalent of $`F_{\mu \nu }^2`$, except that due to the breaking of Lorentz invariance it contains separate time- and space-like components which represent the contribution of high-energy modes to the renormalization of the coupling constant, and Debye screening. These effects do not introduce a complex component when continued to Euclidean space.

Higher dimension operators, which involve additional powers of $`F_{\mu \nu }`$ or covariant derivatives $`D_\mu `$ are suppressed by the scale $`\mathrm{\Lambda }`$. These are presumably the source of complex terms introduced to the effective action. However, due to the $`1/\mathrm{\Lambda }`$ suppression they are dominated by the contribution from the low-lying modes in region (I), which is necessarily non-local, but real.

The logarithm of the Euclidean quark determinant will have the form:

$$\mathrm{ln}\mathrm{det}M𝒪(\mu ^4)+(\mathrm{non}\mathrm{local},\mathrm{real})+𝒪(\frac{1}{\mathrm{\Lambda }})(\mathrm{local},\mathrm{complex}),$$
(52)
where the first term is the (real, constant) free energy of non-interacting quarks, the second term is from the positive determinant in region (I) and the last term is the suppressed, complex contribution from region (II). Only the last two terms depend on the gauge field $`A_\mu (x)`$

On the lattice, one can use the dominant dependence of $`\mathrm{det}M`$ on the first and second terms to do importance sampling. In order to keep the complex higher dimension operators (last term in (52)) small, it is important that the gauge field strengths are kept smaller than $`\mathrm{\Lambda }^2`$. One can impose this condition by using two different lattice spacings, $`a_g`$ for the gluons and $`a_{det}`$ for the quarks, with $`a_g>a_{det}`$. The determinant is calculated on the finer $`a_{det}`$ lattice, and is a function of plaquettes which are obtained by interpolation from the plaquettes on the coarser $`a_g`$ lattice. Interpolation can be defined in a natural way, since each lattice link variable $`U_{x\mu }`$ is an element of the gauge group, and one can connect any two points $`g_1,g_2`$ on the group manifold in a linear fashion: $`g(t)=g_1+t(g_2g_1),0t1`$.

More explicitly, let $`x`$ and $`x+a_g\mu `$ be two neighboring points on the coarse lattice, and

$$z_n=x+na_{\mathrm{det}}\mu ,n=0,1,\mathrm{}N$$
(53)
be the corresponding points on the fine lattice: $`z_0=x,z_N=x+a_g\mu `$, where $`N=a_g/a_{det}`$. Then a link

$$U_{x,\mu }=\mathrm{exp}\left[ia_gG^mt^m\right]$$

is interpolated to a set of links as

$$\overline{U}_{z_n,z_{n+1}}=\mathrm{exp}\left[ia_{\mathrm{det}}G^mt^m\right],$$
(54)
where the $`t^m`$ are SU(N) generators, and the bar denotes the finer lattice. Equation (54) allows us to compute $`\overline{U}`$ links which are sub-links of original $`a_g`$ link variables, and lie on the outer perimeter of a plaquette. The remaining $`\overline{U}`$ links, which are within an $`a_g`$ plaquette, can be obtained through a similar interpolation starting from opposite sides of the perimeter, yielding an entire set of plaquettes on the $`a_{det}`$ lattice. The field strengths resulting from this interpolation are always of order $`a_g^2`$ and can be kept small compared to the cutoff $`\mathrm{\Lambda }^2`$. To properly include the quasiparticle modes, the spacing of the fermion lattice must be $`a_{det}1/\mu `$, while $`a_g1/\mathrm{\Lambda }_{\mathrm{QCD}}`$ is probably sufficient to capture the effects of non-perturbative gauge configurations.

The fermion determinant is to be computed as a function of the finer plaquettes $`\{\overline{U}_{x\mu }\}`$. The result is (approximately) real and positive and can be used for importance sampling. Further, there is a physical understanding of the complex part of the determinant: it originates in the modes far from the Fermi surface which have been integrated out.

## V Inequalities and Anomaly Matching

Positivity of the measure allows for rigorous QCD inequalities at asymptotic density. For example, inequalities among masses of bound states can be obtained using bounds on bare quasiparticle propagators. One subtlety that arises is that a quark mass term does not lead to a quasiparticle gap (the mass term just shifts the Fermi surface). Hence, for technical reasons the proof of non-breaking of vector symmetries Vafa:1984xg  must be modified. (Naive application of the Vafa-Witten theorem would preclude the breaking of baryon number that is observed in the color-flavor-locked (CFL) phase Alford:1998mk ). A quasiparticle gap can be inserted by hand to regulate the bare propagator, but it will explicitly violate baryon number. However, following the logic of the Vafa-Witten proof, any symmetries which are preserved by the regulator gap cannot be broken spontaneously. One can, for example, still conclude that isospin symmetry is never spontaneously broken (although see below for a related subtlety). In the case of three flavors, one can introduce a regulator $`d`$ with the color and flavor structure of the CFL gap to show rigorously that none of the symmetries of the CFL phase are broken at asymptotic density. On the other hand, by applying anomaly matching conditions anomaly , we can prove that the $`SU(3)_A`$ symmetries are broken. We therefore conclude that the CFL phase is the true ground state for three light flavors at asymptotic density, a result that was first established by explicit calculation Evans:1999at ; Hong:2000ru ; Schafer:1999fe .

To examine the long-distance behavior of the vector current, we note that the correlator of the vector current for a given gauge field $`A`$ can be written as

$`J_\mu ^a(\stackrel{}{v}_F,x)J_\nu ^b(\stackrel{}{v}_F,y)^A=\mathrm{Tr}\gamma _\mu T^aS^A(x,y;d)\gamma _\nu T^bS^A(y,x;d),`$
where the $`SU(N_f)`$ flavor current $`J_\mu ^a(\stackrel{}{v}_F,x)=\overline{\psi }_+(\stackrel{}{v}_F,x)\gamma _\mu T^a\psi _+(\stackrel{}{v}_F,x)`$. The propagator with $`SU(3)_V`$-invariant IR regulator $`d`$ is given as

$`S^A(x,y;d)=x\left|{\displaystyle \frac{1}{M}}\right|y={\displaystyle _0^{\mathrm{}}}d\tau x\left|e^{i\tau (iM)}\right|y`$
where with $`D=+iA`$

$`M`$ $`=`$ $`\gamma _0\left(\begin{array}{cc}DV& d\\ d^{}& D\overline{V}\end{array}\right).`$
Since the eigenvalues of $`M`$ are bounded from below by $`d`$, we have

$`\left|x\left|{\displaystyle \frac{1}{M}}\right|y\right|{\displaystyle _R^{\mathrm{}}}d\tau e^{d\tau }\sqrt{x|x}\sqrt{y|y}={\displaystyle \frac{e^{dR}}{d}}\sqrt{x|x}\sqrt{y|y},`$ (55)
where $`R\left|xy\right|`$. The current correlators fall off rapidly as $`R\mathrm{}`$;

$`|{\displaystyle }\mathrm{d}A_+`$ $`detM_{\mathrm{eff}}(A)e^{S_{\mathrm{eff}}}J_\mu ^A(\stackrel{}{v}_F,x)J_\nu ^B(\stackrel{}{v}_F,y)^{A_+}|`$ (56)
$``$ $`{\displaystyle _{A_+}}\left|J_\mu ^A(\stackrel{}{v}_F,x)J_\nu ^B(\stackrel{}{v}_F,y)^{A_+}\right|{\displaystyle \frac{e^{2dR}}{d^2}}{\displaystyle _{A_+}}\left|x|x\right|\left|y|y\right|,`$
where we used the Schwartz inequality in the first inequality, since the measure of the effective theory is now positive, and equation (55) in the second inequality. The IR regulated vector currents do not create massless modes out of the vacuum or Fermi sea, which implies that there is no Nambu-Goldstone mode in the $`SU(3)_V`$ channel. Therefore, for three massless flavors $`SU(3)_V`$ has to be unbroken as in CFL. The rigorous result provides a non-trivial check on explicit calculations, and applies to any system in which the quasiparticle dynamics have positive measure.

It is important to note the order of limits necessary to obtain the above results. Because there are higher-order corrections to the HDET, suppressed by powers of $`\mathrm{\Lambda }/\mu `$, that spoil its positivity, there may be contributions on the RHS of (56) of the form

$$𝒪\left(\frac{\mathrm{\Lambda }}{\mu }\right)f(R),$$
(57)
where $`f(R)`$ falls off more slowly than the exponential in (56). To obtain the desired result, we must first take the limit $`\mu \mathrm{}`$ at fixed $`\mathrm{\Lambda }`$ before taking $`R\mathrm{}`$. Therefore, our results only apply in the limit of asymptotic density.

Although our result precludes breaking of vector symmetries at asymptotic density in the case of three exactly massless quarks thermo , it does not necessarily apply to the case when the quark masses are allowed to be slightly non-zero. In that case the results depend on precisely how the limits of zero quark masses and asymptotic density are taken, as we discuss below.

In Bedaque:2001je  the authors investigate the effect of quark masses on the CFL phase. These calculations are done in the asymptotic limit, and are reliable for sufficiently small quark masses. When $`m_u=m_dm<<m_s`$ (unbroken $`SU(2)`$ isospin, but explicitly broken $`SU(3)`$), one finds a kaon condensate. The critical value of $`m_s`$ at which the condensate forms is $`m_s^{}m^{1/3}\mathrm{\Delta }_0^{2/3}`$, where $`\mathrm{\Delta }_0`$ is the CFL gap (see, in particular, equation (8) of the first paper). As kaons transform as a doublet under isospin, the vector $`SU(2)`$ symmetry is broken in seeming contradiction with our result.

However, a subtle order of limits is at work here. For simplicity, let us set $`m=0`$. Note that the CFL regulator $`d`$, which was inserted by hand, explicitly breaks $`SU(3)_A`$ through color-flavor locking, leading to small positive mass squared for the pions and kaons, given as

$`m_{\pi ,K}^2\alpha _sd^2\mathrm{ln}\left({\displaystyle \frac{\mu }{d}}\right).`$ (58)
The meson mass is not suppressed by $`1/\mu `$, since, unlike the Dirac mass term, the regulator, being a Majorana mass, does not involve antiquarks Hong:1999ei .

Therefore, even when the light quarks are massless, there is a critical value of $`m_s`$ necessary to drive negative the mass-squared of kaons and cause condensation:

$$m_s^{}\left[g_sd\mu \mathrm{ln}\left(\frac{\mu }{d}\right)\right]^{1/2}>(d\mu )^{1/2},$$
(59)
where $`g_s`$ is the strong coupling constant. Note the product of $`g_s`$ with the logarithm grows as $`\mu `$ gets large. To obtain our inequality we must keep the regulator $`d`$ non-zero until the end of the calculation in order to see the exponential fall off. To find the phase with kaon condensation identified in Bedaque:2001je  we must keep $`m_s`$ larger than $`m_s^{}`$. (Note $`\mu \mathrm{}`$, so to have any chance of finding this phase we must take $`d0`$ keeping $`dR`$ large and $`d\mu `$ small.)

Since the UV cutoff of the HDET must be larger than $`m_s`$, we have

$$1>\left(\frac{m_s^{}}{\mathrm{\Lambda }}\right)^2>\frac{d}{\mathrm{\Lambda }}\frac{\mu }{\mathrm{\Lambda }},$$
(60)
which implies

$$\frac{\mathrm{\Lambda }}{\mu }f(R)>\frac{d}{\mathrm{\Lambda }}f(R).$$
(61)
Note the right hand side of this inequality does not necessarily fall off at large $`R`$, and also does not go to zero for $`\mu \mathrm{}`$ at fixed $`\mathrm{\Lambda }`$ and $`d`$. This is a problem since to apply our inequality the exponential falloff from (56) must dominate the correction term (57), which is just the left hand side of (61). Combining these equations, we see that the exponential falloff of the correlator is bounded below,

$$\frac{e^{2dR}}{d^2}>\frac{d}{\mathrm{\Lambda }}f(R),$$
(62)
in the scaling region with a kaon condensate, $`m_s>m_s^{}`$.

Alternatively, if we had taken $`m_s`$ to be finite for fixed regulator $`d`$ (so that, as $`\mu \mathrm{}`$, eventually $`m_s<m_s^{}`$), the inequality in (56) could be applied to exclude a Nambu-Goldstone boson, but we would find ourselves in the phase without a kaon condensate.

## VI Conclusion

The low-energy physics of dense fermionic matter, ranging from quark matter to electronic systems, is controlled by modes near the Fermi surface. An effective Lagrangian describing the low-energy modes can be given in a systematic expansion in powers of the energy scale over the chemical potential. The leading term in this expansion has a simple form, and we have shown that it leads to a real, positive Euclidean path integral measure.

This observation opens the door to importance sampling in Monte Carlo simulations of dense matter systems. The key requirement is that the interactions do not strongly couple the low-energy modes to modes far from the Fermi surface. QCD at high density satisfies this requirement, as do all asymptotically free models. Electronic system in which the important interactions involve momentum transfer less than the Fermi energy are in this category, although some idealized models such as the Hubbard model are not. We have given some proposals for how the positive effective theory might be simulated numerically. Ultimately, we hope that actual practitioners will develop even more practical methods.

Finally, positivity has analytical applications as well, since it allows the use of rigorous inequalities. In QCD we obtain restrictions on symmetry breaking patterns at high density. Similar restrictions can probably be obtained for electronic systems with suitable interactions.

###### Acknowledgements.

We would like to thank M. Alford, S. Hands, C. Kim, W. Lee, T.-S. Park, K. Rajagopal and M. Stephanov for useful discussions. The work of D.K.H. was supported in part by the academic research fund of Ministry of Education, Republic of Korea, Project No. KRF-2000-015-DP0069. The work of S.H. was supported in part under DOE contract DE-FG06-85ER40224 and by the NSF through through the USA-Korea Cooperative Science Program, 9982164.


text:
# Generalized Parton Distributions and Nucleon Resonances

## 1 Brief introduction to “transition” GPDs

The Generalized Parton Distributions provide one of the most complete information on the structure of the nucleon : they allow to access the longitudinal momentum distributions of the partons in the nucleon as well as the nucleon’s transverse profile, the parton correlations, their orbital momentum contribution to the total nucleon’s spin, quark-antiquark components in the nucleon, etc…

The GPDs can be accessed through the hard (i.e. large photon virtuality $`Q^2`$) exclusive electroproduction of photons (“Deep Virtual Compton Scattering” -DVCS-) and mesons -$`\pi ^{0,\pm }`$, $`\rho ^{0,\pm }`$, $`\omega `$, $`\varphi `$, etc…- on the nucleon.

The formalism introducing the Generalized Parton Distributions can be found in Refs.  and is summarized in the contribution of A. Belitstky to these proceedings. We refer the reader to these articles for the standard definitions and notations used in the following.

The GPD formalism was originally developed for exclusive reactions on the nucleon, both in the initial and final states, but was recently extended to more general baryonic final states , in particular for the simplest non-elastic transition the N-$`\mathrm{\Delta }`$ case. Like “transition” N-$`\mathrm{\Delta }`$ form factors, one can introduce about “transition” N-$`\mathrm{\Delta }`$ GPDs and these are in principle different from the nucleon GPDs.

N-$`\mathrm{\Delta }`$ GPDs contain the same type of information as the nucleon GPDs, i.e. the quarks longitudinal momentum distributions and their transverse positions in the $`\mathrm{\Delta }`$, their spin distribution, etc… and, in the case of $`\mathrm{\Delta }`$-$`\mathrm{\Delta }`$ GPDs, similarly to Ji’s sum rule, the orbital contribution of the quarks to the spin of the $`\mathrm{\Delta }`$.

At leading twist in QCD, the N-$`\mathrm{\Delta }`$ transition can be parametrized in terms of 3 vector N-$`\mathrm{\Delta }`$ GPDs and 4 axial-vector N-$`\mathrm{\Delta }`$ GPDs. Among them, one expects 3 N-$`\mathrm{\Delta }`$ GPDs to dominate at small $`t`$ : the magnetic vector N-$`\mathrm{\Delta }`$ GPD $`H_M`$, whose first moment corresponds to the N-$`\mathrm{\Delta }`$ magnetic transition form factor $`G_M^{}(t)`$, and the axial vector N-$`\mathrm{\Delta }`$ GPDs $`C_1`$ and $`C_2`$ whose first moments correspond to the axial and pseudoscalar N-$`\mathrm{\Delta }`$ form factors respectively.

In order to provide numerical estimates for the N-$`\mathrm{\Delta }`$ amplitudes, these three GPDs have been estimated in Ref.  in the large $`N_c`$ limit. In this limit (valid to about 30%), they can be related to three nucleon GPDs : $`C_1\stackrel{~}{H}^{(3)},C_2\stackrel{~}{E}^{(3)}`$ and $`H_ME^{(3)}`$, where the superscript (3) refers to the isovector nucleon GPDs combination. As various modelizations of the nucleon GPDs are available in the literature, these relations allow to make numerical estimates and calculations for observables (cross sections, asymmetries,…) related to exclusive reactions involving the N-$`\mathrm{\Delta }`$ transition, such as $`epe^{}\mathrm{\Delta }\gamma `$ (usually refered to as $`\mathrm{\Delta }`$VCS by analogy with DVCS -see Fig. 1-), $`epe^{}\mathrm{\Delta }^{++}\pi ^{}`$, etc…

In the case of the $`\mathrm{\Delta }`$VCS process, similarly to the DVCS process, there is an interference with the associated Bethe-Heitler mechanism (where the outgoing photon is emitted by the incoming or scattered electron), and this produces a beam helicity asymmetry, which is shown on Fig. 2.

The large $`N_c`$ relations, although not extremely precise, allow also to interpret the $`\mathrm{\Delta }`$VCS reaction in terms of nucleon GPDs and therefore permits to access a different flavor combination of the nucleon GPDs : for instance, in DVCS, one accesses in general the combination $`\frac{4}{9}\stackrel{~}{H}^u+\frac{1}{9}\stackrel{~}{H}^d`$ whereas, in $`\mathrm{\Delta }`$VCS, one accesses the isovector part $`\stackrel{~}{H}^u\stackrel{~}{H}^d`$. In this way, the $`\mathrm{\Delta }`$VCS process is therefore also useful to carry out a flavor decomposition of the nucleon GPDs.

A new way to study baryon spectroscopy is therefore opening up through these transition $`NN^{},\mathrm{\Delta }^{}`$ GPDs, where not only the $`t`$-dependence, which can currently be determined through transition form factors and which reflects the transverse spatial distribution of the partons in the nucleon, can be accessed but also their $`x`$-dependence, reflecting the longitudinal momentum distributions of the quarks in the $`N^{}`$’s.

## 2 Modelization of the N-$`\mathrm{\Delta }`$ transition form factor

In this part, as a basic illustration of the information contained in the GPDs, we show how the N-$`\mathrm{\Delta }`$ transition form factor can be estimated from the (nucleon) GPDs, relying on very simple assumptions. We start from the model independent sum rules which relate the GPDs to the form factors :

$`F_2^q(t)={\displaystyle _1^{+1}}𝑑xE^q(x,\xi ,t),G_M^{}(t)={\displaystyle _1^{+1}}𝑑xH_M(x,\xi ,t)`$ (1)
where $`F_2`$ is the nucleon Pauli form factor and $`G_M^{}`$ the N-$`\mathrm{\Delta }`$ magnetic transition form factor.

In the large $`N_c`$ limit, the N-$`\mathrm{\Delta }`$ GPDs can be expressed in terms of the isovector combination of nucleon GPDs and one arrives at the following sum rule  :

$`G_M^{}(t)={\displaystyle \frac{G_M^{}(0)}{\kappa _V}}{\displaystyle _1^{+1}}𝑑x\left\{E^u(x,\xi ,t)E^d(x,\xi ,t)\right\}={\displaystyle \frac{G_M^{}(0)}{\kappa _V}}\left\{F_2^p(t)F_2^n(t)\right\}`$ (2)
where $`\kappa _V=\kappa _p\kappa _n=3.70`$. In the large $`N_c`$ limit, the value $`G_M^{}(0)`$ is given by : $`G_M^{}(0)=\kappa _V/\sqrt{3}`$, some 30 % smaller than the experimental number. In calculations, we therefore use the phenomenological value $`G_M^{}(0)3.02`$ .

One can choose $`\xi =0`$ in the previous equations, and by modeling the nucleon GPD $`E(x,0,t)`$, one can therefore estimate the N-$`\mathrm{\Delta }`$ transition form factor. A plausible ansatz at low $`t`$, inspired from a Regge form, for the GPD $`E(x,0,t)`$ could be :

$`E^q(x,0,t)`$ $`=`$ $`\kappa _qq_v(x){\displaystyle \frac{1}{x^{\alpha ^{^{}}t}}},`$ (3)
where $`q_v(x)`$ is the (u,d) valence quark distribution normalized to (2,1) respectively and where $`\kappa _u`$ and $`\kappa _d`$ are given by

$`\kappa _u`$ $`=`$ $`\mathrm{\hspace{0.17em}2}\kappa _p+\kappa _n,`$ (4)
$`\kappa _d`$ $`=`$ $`\kappa _p+\mathrm{\hspace{0.33em}2}\kappa _n.`$ (5)
In equation (3), $`\alpha ^{}(t)`$ is the slope of standard Regge trajectory (to be fitted) around 1 GeV2. It has been shown in Ref.  that such kind of ansatz was able to reproduce rather well the electric and magnetic radii of the nucleon and the Dirac and Pauli form factors at low $`t`$ ($`<`$ 1 GeV2). We show on figure 3 the decent agreement for the N-$`\mathrm{\Delta }`$ transition form factor.

## 3 Experimental aspects

Finally, on the experimental side, first hints of the observation of the $`epe^{}\mathrm{\Delta }\gamma `$ reaction in the CLAS detector at JLab are showing up. The analysis, led by S. Bouchigny from IPN Orsay, has consisted in selecting $`e^{}n\pi ^+`$ final states in data taken with a 4.2 GeV incident electron beam. Selecting events whose missing mass MM($`e^{}n\pi ^+X`$) is around zero 111It should be kept in mind that there is certainly a contamination of the $`\mathrm{\Delta }`$VCS signal by $`\mathrm{\Delta }\pi ^0`$ final states at this preliminary stage of analysis, the current resolution of CLAS not permitting the separation of the two by the missing mass technique., in order to be compatible with a missing photon (see figure 4-a), and imposing a $`W>2`$ GeV cut so that one is above the resonance region, one was able to observe the $`n\pi ^+`$ invariant mass spectra of figure 4-b where one clearly distinguishes, not only $`\mathrm{\Delta }\gamma `$ final states, but also higher $`N^{}\gamma `$ final states, providing evidence for N$``$N DVCS processes.

The statistics in this figure (effectively equivalent to a few days of beam time) are not enough yet to extract a significant beam asymmetry to be compared to the theoretical calculations of figure 2 but the observed signals are certainly very encouraging.

Data have been taken last year in CLAS with a 5.75 GeV beam and are in the process of being analysed (with 5 times more statistics than with the 4.2 GeV run of figure 4) and should allow to have a first glance at a $`\mathrm{\Delta }`$VCS beam asymmetry very soon.

Finally, the forthcoming equipment of CLAS with a fine (angular and energy) resolution and high counting rate capability calorimeter, to be installed and operational mid-2004 (see for instance Ref. ), will also boost tremendously the potential of analysis of this channel. The full detection of the photon(s) of the final state will be possible and will unambiguously allow to distinguish $`e^{}\mathrm{\Delta }\gamma `$ from $`e^{}\mathrm{\Delta }\pi ^0`$ final states.

## 4 Conclusion

We have briefly discussed here a couple of aspects of the relation between (transition) Generalized Parton Distributions and nucleon resonances. The exclusive electroproduction of a photon or of a meson with baryonic resonances opens a brand new way to understand the nucleon excitation spectrum, allowing to access a wealth of information not contained in direct (i.e. $`s`$-channel) resonance excitation. This opens up the perspective to arrive at a 3-dimensional picture of the nucleon and its resonances through the formalism of the GPDs.