text:
# On the cost of participating in a peer-to-peer network This research is supported in part by the National Science Foundation, through grant ANI-0085879.

## 1 Introduction

A key factor in the efficiency of a peer-to-peer overlay network is the level of collaboration provided by each peer. This paper takes a first step towards quantifying the level of collaboration that can be expected from each participant, by proposing a model to evaluate the cost each peer incurs for being a part of the overlay.

Such a cost model has several useful applications, among which, (1) providing a benchmark that can be used to compare between different proposals, complementary to recent works comparing topological properties of various overlays , (2) allowing for predicting disincentives, and designing mechanisms that ensure a protocol is strategyproof , and (3) facilitating the design of load balancing primitives.

This work is not the first attempt to characterize the cost of participating in a network. Jackson and Wolinsky  proposed cost models to analyze formation strategies in social and economic networks. More recent studies  model (overlay) network formation as a non-cooperative game. These studies assume that each node has the freedom to choose which links it maintains, whereas we assume that the overlay topology is constrained by a protocol. Moreover, our approach extends previously proposed cost models , by considering the load imposed on each node in addition to the distance to other nodes and degree of connectivity.

In the remainder of this paper, we introduce our proposed cost model, before applying it to several routing geometries used in recently proposed distributed hash tables (DHT) algorithms . We conclude by discussing some open problems this research has uncovered.

## 2 Proposed cost model

The model we propose applies to any peer-to-peer network where nodes request and serve items, or serve requests between other nodes. This includes peer-to-peer file-sharing systems , ad-hoc networks , peer-to-peer lookup services , peer-to-peer streaming systems , or application-layer multicast overlays , to name a few examples.

To simplify the presentation, we assume a DHT-like structure, defined by quadruplet $`(V,E,K,F)`$, where $`V`$ is the set of vertices in the network, $`E`$ is the set of edges, $`K`$ is the set of keys (items) in the network, and $`F:KV`$ is the hash function that assigns keys to vertices. We denote by $`K_i=\{kK:F(k)=i\}`$ the set of keys stored at node $`iV`$. We have $`K=_iK_i`$, and we assume, without loss of generality, that the sets $`K_i`$ are disjoint.111If a key is stored on several nodes (replication), the replicas can be considered as different keys with the exact same probability of being requested. We characterize each request with two independent random variables, $`XV`$ and $`YK`$, which denote the node $`X`$ making the request, and the key $`Y`$ being requested, respectively.

Consider a given node $`iV`$. Every time a key $`k`$ is requested in the entire network, node $`i`$ is in one of four situations:

1. Node $`i`$ does not hold or request $`k`$, and is not on the routing path of the request. Node $`i`$ is not subject to any cost.
2. Node $`i`$ holds key $`k`$, and pays a price $`s_{i,k}`$ for serving the request. We define the service cost $`S_i`$ incurred by $`i`$, as the expected value of $`s_{i,k}`$ over all possible requests. That is,

$$S_i=\underset{kK_i}{}s_{i,k}\text{Pr}[Y=k].$$
3. Node $`i`$ requests key $`k`$, and pays a price to look up and retrieve $`k`$. We model this price as $`a_{i,k}t_{i,j}`$, where $`t_{i,j}`$ is the number of hops between $`i`$ and the node $`j`$ that holds the key $`k`$, and $`a_{i,k}`$ is a (positive) proportional factor. We define the access cost suffered by node $`i`$, $`A_i`$, as the sum of the individual costs $`a_{i,k}t_{i,j}`$ multiplied by the probability key $`kK_j`$ is requested, that is,

$$A_i=\underset{jV}{}\underset{kK_j}{}a_{i,k}t_{i,j}\text{Pr}[Y=k],$$
(1)
with $`t_{i,j}=\mathrm{}`$ if there is no path from node $`i`$ to node $`j`$, and $`t_{i,i}=0`$ for any $`i`$.
4. $`i`$ does not hold or request $`k`$, but has to forward the request for $`k`$, thereby paying a price $`r_{i,k}`$. The overall routing cost $`R_i`$ experienced by node $`i`$ is the average over all possible keys $`k`$, of the values of $`r_{i,k}`$ such that $`i`$ is on the path of the request. That is, we consider the binary function

$$\chi _{j,l}(i)=\{\begin{array}{cc}1\hfill & \text{if }i\text{ is on the path from }j\text{ to }l\text{,}\hfill \\ & \text{excluding }j\text{ and }l\hfill \\ 0\hfill & \text{otherwise,}\hfill \end{array}$$

and express $`R_i`$ as

$$R_i=\underset{jV}{}\underset{lV}{}\underset{kK_l}{}r_{i,k}\text{Pr}[X=j]\text{Pr}[Y=k]\chi _{j,l}(i).$$
(2)

In addition, each node keeps some state information so that the protocol governing the DHT operates correctly. In most DHT algorithms, each node $`i`$ maintains a neighborhood table, which grows linearly with the out-degree $`\mathrm{deg}(i)`$ of the node, resulting in a maintenance cost $`M_i`$ given by

$$M_i=m_i\mathrm{deg}(i),$$

where $`m_i>0`$ denotes the cost of keeping a single entry in the neighborhood table of node $`i`$.

Last, the total cost $`C_i`$ imposed on node $`i`$ is given by

$$C_i=S_i+A_i+R_i+M_i,$$

which can be used to compute the total cost of the network, $`C=_{iV}C_i`$. The topology that minimizes $`C`$, or “social optimum,” is generally not trivial. In particular, the social optimum is the full mesh only if $`m_i=0`$ for all $`i`$, and the empty set only if $`a_{i,k}=0`$ for all $`(i,k)`$.

## 3 Case studies

We next apply the proposed cost model to a few selected routing geometries. We define a routing geometry as in , that is, as a collection of edges, or topology, associated with a route selection mechanism. Unless otherwise noted, we assume shortest path routing, and distinguish between different topologies. We derive the various costs experienced by a node in each geometry, before illustrating the results with numerical examples.

### 3.1 Analysis

We consider a network of $`N>0`$ nodes, and, for simplicity, assume that, for all $`i`$ and $`k`$, $`s_{i,k}=s`$, $`a_{i,k}=a`$, $`r_{i,k}=r`$, and $`m_i=m`$. For the analysis in this section, we also assume that each node holds the same number of keys, and that all keys have the same popularity. As a result, for all $`i`$,

$$\underset{kK_i}{}\text{Pr}[Y=k]=\frac{1}{N},$$

which implies

$$S_i=\frac{s}{N},$$

regardless of the geometry considered. We also assume that requests are uniformly distributed over the set of nodes, that is, for any node $`i`$,

$$\text{Pr}[X=i]=\frac{1}{N}.$$

Last, we assume that no node is acting maliciously.

#### Star network

The star frequently appears as an equilibrium in network formation studies using cost models based on graph connectivity .

We use $`i=0`$ to denote the center of the star, which routes all traffic between peripheral nodes. That is, $`\chi _{j,l}(0)=1`$ for any $`jl`$ ($`j>0`$, $`l>0`$). Substituting in Eqn. (2), we get

$$R_0=\frac{r(N1)(N2)}{N^2}.$$

The center node is located at a distance of one hop from all $`(N1)`$ other nodes, thus

$$A_0=\frac{a(N1)}{N}.$$

In addition, $`\mathrm{deg}(0)=N1`$, which implies that the cost incurred by the center of the star, $`C_0`$, is

$$C_0=m(N1)+\frac{s}{N}+\frac{a(N1)}{N}+\frac{r(N1)(N2)}{N^2}.$$
(3)
Peripheral nodes do not route any traffic, i.e., $`R_i=0`$ for all $`i>0`$, and are located at a distance of one from the center of the star, and at a distance of two from the $`(N2)`$ other nodes, giving

$$A_i=\frac{a(2N3)}{N}.$$

Furthermore, $`\mathrm{deg}(i)=1`$ for all peripheral nodes. Thus, $`M_i=m`$, and the total cost imposed on nodes $`i>0`$ is

$$C_i=m+\frac{s+a(2N3)}{N}.$$
(4)
The difference $`C_0C_i`$ quantifies the (dis)incentive to be in the center of the star. As expressed in the following two theorems, there is a (dis)incentive to be in the center of the star in a vast majority of cases.

###### Theorem 1.

If the number of nodes $`N`$ ($`N>0`$) is variable, $`C_0C_i`$ unless $`m=r=a=0`$.

###### Proof.

Assume that $`C_0C_i=0`$. Because $`N0`$, $`C_0C_i=0`$ is equivalent to $`N^2(C_0C_i)=0`$. Using the expressions for $`C_0`$ and $`C_i`$ given in Eqs. (3) and (4), and rewriting the condition $`N^2(C_0C_i)=0`$ as a polynomial in $`N`$, we obtain

$$mN^3(2m+ar)N^2+(2a3r)N+2r=0.$$

We can factor the above by $`(N2)`$, and obtain

$$(N2)(mN^2(ar)Nr)=0.$$
(5)
A polynomial in $`N`$ is constantly equal to zero if and only if all of the polynomial coefficients are equal to zero. Thus, Eqn. (5) holds for any value of $`N`$ if and only if:

$$\{\begin{array}{ccc}m\hfill & =\hfill & 0,\hfill \\ ar\hfill & =\hfill & 0,\hfill \\ r\hfill & =\hfill & 0.\hfill \end{array}$$

The solutions of the above system of equations are $`m=r=a=0`$. Hence, $`C_0C_i=0`$ for any $`N`$ only when nodes only pay an (arbitrary) price for serving data, while state maintenance, traffic forwarding, and key lookup and retrieval come for free. ∎

###### Theorem 2.

If the number of nodes $`N`$ ($`N>0`$) is held fixed, and at least one of $`m`$, $`r`$, or $`a`$ is different from zero, $`C_0=C_i`$ only if $`N=2`$ or $`N=N_0`$, where $`N_0`$ is a positive integer that must satisfy:

$$N_0=\{\begin{array}{cc}\frac{r}{ra}\hfill & \text{if }m=0\text{ and }ra,\hfill \\ \frac{ar}{2m}+\sqrt{\left(\frac{ar}{2m}\right)^2+\frac{r}{m}}\hfill & \text{if }m0.\hfill \end{array}$$
(6)
Additionally, $`C_0C_i`$ for any $`N2`$ if $`m=0`$ and $`r=a`$.

###### Proof.

Recall from the proof of Theorem 1, that $`C_0C_i=0`$ is equivalent to Eqn. (5). Clearly, setting $`N=2`$ satisfies Eqn. (5) for all values of $`s`$, $`r`$, and $`m`$. Assuming now that $`N2`$, to have $`C_0C_i=0`$, we need to have

$$mN^2(ar)Nr=0.$$
(7)
Since at least one of $`m`$, $`r`$, or $`a`$ is not equal to zero, Eqn. (7) has at most two real solutions. We distinguish between all possible cases for $`m`$, $`r`$, and $`a`$ such that at least one of $`m`$, $`r`$, and $`a`$ is different from zero.

* If $`m=0`$, and $`a=r`$, Eqn. (7) reduces to $`r=0`$, which implies $`m=r=a=0`$, thereby contradicting the hypothesis that at least one of $`m`$, $`r`$, and $`a`$ is different from zero. Therefore, Eqn. (7) does not admit any solution, i.e., there is a (dis)incentive to be in the center of the star regardless of $`N`$.
* If $`m=0`$ and $`ra`$, the only solution to Eqn. (7) is

$$N_0=\frac{r}{ra}.$$
(8)
Note that if $`r<a`$, $`N_0<0`$ which is not feasible. (The number of nodes has to be positive.)
* If $`m0`$, then Eqn. (7) admits two real roots (or a double root if $`a=r=0`$), given by

$$N_0=\frac{ar}{2m}\pm \sqrt{\left(\frac{ar}{2m}\right)^2+\frac{r}{m}}.$$

However, because $`r0`$, and $`m0`$,

$$\frac{ar}{2m}\sqrt{\left(\frac{ar}{2m}\right)^2+\frac{r}{m}}0,$$

so that the only potentially feasible $`N_0`$ is given by

$$N_0=\frac{ar}{2m}+\sqrt{\left(\frac{ar}{2m}\right)^2+\frac{r}{m}}.$$
(9)

Combining Eqs. (8) and Eqs. (9) yields the expression for $`N_0`$ given in Eqn. (6). Note that the expression given in Eqn. (6) is only a necessary condition. In addition, $`N_0`$ has to be an integer so that we can set the number of nodes $`N`$ to $`N=N_0`$. ∎

#### De Bruijn graphs

De Bruijn graphs are used in algorithms such as Koorde , Distance-Halving , or ODRI , and are extensively discussed in . In a de Bruijn graph, any node $`i`$ is represented by an identifier string $`(i_1,\mathrm{},i_D)`$ of $`D`$ symbols taken from an alphabet of size $`\mathrm{\Delta }`$. The node represented by $`(i_1,\mathrm{},i_D)`$ links to each node represented by $`(i_2,\mathrm{},i_D,x)`$ for all possible values of $`x`$ in the alphabet. The resulting directed graph has a fixed out-degree $`\mathrm{\Delta }`$, and a diameter $`D`$.

Denote by $`V^{}`$ the set of nodes such that the identifier of each node in $`V^{}`$ is of the form $`(h,h,\mathrm{},h)`$. Nodes in $`V^{}`$ link to themselves, so that $`M_i=m(\mathrm{\Delta }1)`$ for $`iV^{}`$. For nodes $`iV^{}`$, the maintenance cost $`M_i`$ is $`M_i=m\mathrm{\Delta }`$. The next two lemmas will allow us to show that the routing cost at each node also depends on the position of the node in the graph.

###### Lemma 1.

With shortest-path routing, nodes $`iV^{}`$ do not route any traffic, and $`R_i=0`$.

###### Proof.

(By contradiction.) Consider a node $`iV^{}`$ with identifier $`(h,h,\mathrm{},h)`$, and suppose $`i`$ routes traffic from a node $`j`$ to a node $`k`$. The nodes linking to $`i`$ are all the nodes with an identifier of the form $`(x,h,\mathrm{},h)`$, for all values of $`x`$ in the alphabet. The nodes linked from $`i`$ are all the nodes of the form $`(h,\mathrm{},h,y)`$ for all values of $`y`$ in the alphabet. Therefore, there exists $`x_0`$ and $`y_0`$ such that traffic from node $`j`$ to node $`k`$ follows a path $`𝒫=(x_0,h,\mathrm{},h)(h,h,\mathrm{},h)(h,h,\mathrm{},y_0)`$. Because, in a de Bruijn graph, there is an edge between $`(x_0,h,\mathrm{},h)`$ and $`(h,h,\mathrm{},y_0)`$, traffic using the path $`𝒫`$ between $`j`$ and $`k`$ does not follows the shortest path. We arrive to a contradiction, which proves that $`i`$ does not route any traffic. ∎

###### Lemma 2.

The number of routes $`L_i`$ passing through a given node $`i`$ is bounded by $`L_iL_{\mathrm{max}}`$ with

$$L_{\mathrm{max}}=\frac{(D1)(\mathrm{\Delta }^{D+2}(\mathrm{\Delta }1)^2)D\mathrm{\Delta }^{D+1}+\mathrm{\Delta }^2}{(\mathrm{\Delta }1)^2}.$$

The bound is tight, since it can be reached when $`\mathrm{\Delta }D`$ for the node $`(0,1,2,\mathrm{},D1)`$.

###### Proof.

The proof follows the spirit of the proof used in  to bound the maximum number of routes passing through a given edge. In a de Bruijn graph, by construction, each node maps to an identifier string of length $`D`$, and each path of length $`k`$ hops maps to a string of length $`D+k`$, where each substring of $`D`$ consecutive symbols corresponds to a different hop . Thus, determining an upper bound on the number of paths of length $`k`$ that pass through a given node $`i`$ is equivalent to computing the maximum number, $`l_k`$, of strings of length $`D+k`$ that include node $`i`$’s identifier, $`\sigma _i=(i_1,\mathrm{},i_D)`$, as a substring. In each string of length $`D+k`$ corresponding to a paths including $`i`$, where $`i`$ is neither the source nor the destination of the path, the substring $`\sigma _i`$ can start at one of $`(k1)`$ positions $`(2,\mathrm{},k)`$. There are $`\mathrm{\Delta }`$ possible choices for each of the $`k`$ symbols in the string of length $`D+k`$ that are not part of the substring $`\sigma _i`$. As a result,

$$l_k(k1)\mathrm{\Delta }^k.$$

With shortest path routing, the set of all paths going through node $`i`$ include all paths of length $`D+k`$ with $`k[1,D]`$. So,

$`L_i`$ $``$ $`{\displaystyle \underset{k=1}{\overset{k=D}{}}}l_k{\displaystyle \underset{k=1}{\overset{k=D}{}}}(k1)\mathrm{\Delta }^k`$ (10)
$``$ $`{\displaystyle \frac{(D1)\mathrm{\Delta }^{D+2}D\mathrm{\Delta }^{D+1}+\mathrm{\Delta }^2}{(\mathrm{\Delta }1)^2}}.`$
We improve the bound given in Eqn. (10) by considering the strings of length $`2D`$ that are of the form $`\sigma ^{}\sigma ^{}`$, where $`\sigma ^{}`$ is a string of length $`D`$. Strings of the form $`\sigma ^{}\sigma ^{}`$ denote a cycle $`\sigma ^{}\sigma ^{}`$, and cannot be a shortest path in a de Bruijn graph. Hence, we can subtract the number of the strings $`\sigma ^{}\sigma ^{}`$ from the bound in Eqn. (10). Because $`\sigma _i=(i_1,\mathrm{},i_D)`$ is a substring of $`\sigma ^{}\sigma ^{}`$ of length $`D`$, $`\sigma ^{}`$ has to be a circular permutation of $`\sigma _i`$, for instance $`(i_{D1},i_D,i_1,\mathrm{},i_{D2})`$. Since $`i`$ does not route any traffic when $`i`$ is the source of traffic, $`\sigma ^{}\sigma _i`$. Thus, there are only $`(D1)`$ possibilities for $`\sigma ^{}`$, and $`(D1)`$ strings $`\sigma ^{}\sigma ^{}`$. Subtracting $`(D1)`$ from the bound in Eqn. (10) yields $`L_{\mathrm{max}}`$.

From Lemmas 1 and 2, we infer that, in a de Bruijn graph, for any $`i`$, $`j`$ and $`k`$, $`0\text{Pr}[\chi _{i,j}(k)=1]L_{\mathrm{max}}/N^2`$. Because $`\chi _{i,j}(k)`$ is a binary function, $`\text{Pr}[\chi _{i,j}(k)=1]=E[\chi _{i,j}]`$, and we finally obtain $`0R_iR_{\mathrm{max}}`$ with

$$R_{\mathrm{max}}=\frac{rL_{\mathrm{max}}}{N^2}.$$

We next compute upper and lower bounds on the access cost. To derive a tight upper bound on $`A_i`$, consider a node $`iV^{}`$. Node $`i`$ links to itself and has only $`(\mathrm{\Delta }1)`$ neighbors. Each neighbor of $`i`$ has itself $`\mathrm{\Delta }`$ neighbors, so that there are $`\mathrm{\Delta }(\mathrm{\Delta }1)`$ nodes $`k`$ such that $`t_{i,k}=2`$. By iteration and substitution in Eqn. (1), we get, after simplification, $`A_iA_{\mathrm{max}}`$, with

$$A_{\mathrm{max}}=a\frac{D\mathrm{\Delta }^{D+1}(D+1)\mathrm{\Delta }^D+1}{N(\mathrm{\Delta }1)},$$

and $`A_i=A_{\mathrm{max}}`$ for nodes in $`V^{}`$.

Now, consider that each node $`i`$ has at most $`\mathrm{\Delta }`$ neighbors. Then, node $`i`$ has at most $`\mathrm{\Delta }^2`$ nodes at distance 2, at most $`\mathrm{\Delta }^3`$ nodes at distance 3, and so forth. Hence, there are at least $`\mathrm{\Delta }^D_{k=0}^{D1}\mathrm{\Delta }^k`$ nodes at the maximum distance of $`D`$ from node $`i`$. We get

$$A_i\frac{a}{N}\left(\underset{k=1}{\overset{D1}{}}k\mathrm{\Delta }^k+D\left(\mathrm{\Delta }^D\underset{k=0}{\overset{D1}{}}\mathrm{\Delta }^k\right)\right),$$

which reduces to $`A_iA_{\mathrm{min}}`$, with

$$A_{\mathrm{min}}=\frac{a}{N}\left(D\mathrm{\Delta }^D+\frac{D}{\mathrm{\Delta }1}\frac{\mathrm{\Delta }(\mathrm{\Delta }^D1)}{(\mathrm{\Delta }1)^2}\right).$$

It can be shown that $`A_i=A_{\mathrm{min}}`$ for the node $`(0,1,\mathrm{},D1)`$ when $`\mathrm{\Delta }D`$.

Note that, the expressions for both $`A_{\mathrm{min}}`$ and $`A_{\mathrm{max}}`$ can be further simplified for $`N=\mathrm{\Delta }^D`$, that is, when the identifier space is fully populated.

#### $`D`$-dimensional tori

We next consider $`D`$-dimensional tori, as in CAN , where each node is represented by $`D`$ Cartesian coordinates, and has $`2D`$ neighbors, for a maintenance cost of $`M_i=2mD`$ for any $`i`$.

Routing at each node is implemented by greedy forwarding to the neighbor with the shortest Euclidean distance to the destination. We assume here that each node is in charge of an equal portion of the $`D`$-dimensional space. From , we know that the average length of a routing path is $`\frac{D}{4}N^{1/D}`$ hops.222Loguinov et al.  refined that result by distinguishing between odd and even values of $`N`$. Because we assume that the $`D`$-dimensional torus is equally partitioned, we conclude by symmetry, that for all $`i`$,

$$A_i=a\frac{D}{4}N^{1/D}.$$

To determine the routing cost $`R_i`$, we compute the number of routes passing through a given node $`i`$, or node loading, as a function $`L_{i,D}`$ of the dimension $`D`$. With our assumption that the $`D`$-torus is equally partitioned, $`L_{i,D}`$ is the same for all $`i`$ by symmetry. We next compute $`L_{i,D}`$ by induction on the dimension $`D`$.

##### Base case $`(D=1)`$.

For $`D=1`$, the $`D`$-torus is a ring, as depicted in Figure 1 for $`N=7`$. Each of the diagrams in the figure corresponds to a case where the source of all requests, represented by a black node, is held fixed. The numbers in each node ($`0,\mathrm{},6`$) represent the node coordinate, the different line styles represent the different routes to all destinations, and the numbers in parentheses denote the number of routes originating from the fixed source that pass through each of the other nodes. As shown in the figure, shifting the source of all requests from 0 to $`1,\mathrm{},6`$ only results in shifting the number of routes that pass through each node. Hence, the node loading $`L_{i,1}`$ at each node $`i`$, is equal to the sum of the number of routes passing through each node when the source is held fixed. In the figure, for $`N=7`$, we have for any $`i`$, $`L_{i,1}=0+1+2+2+1+0=6`$. More generally, for $`N`$ odd, the sum of the number of routes passing through each node is equal to

$`L_{i,1}`$ $`=`$ $`2\left(1+2+\mathrm{}+\left({\displaystyle \frac{N1}{2}}1\right)\right)`$ (11)
$`=`$ $`{\displaystyle \frac{(N1)(N3)}{4}},`$
and for $`N`$ even, is given by

$`L_{i,1}`$ $`=`$ $`\left(1+2+\mathrm{}+\left({\displaystyle \frac{N}{2}}1\right)\right)+\left(1+2+\mathrm{}+\left({\displaystyle \frac{N}{2}}2\right)\right)`$ (12)
$`=`$ $`{\displaystyle \frac{(N2)^2}{4}}.`$
We can express Eqs. (11) and (12) in a more compact form, which holds for any $`N`$,

$$L_{i,1}=\left(\frac{N}{2}1\right)\left(\frac{N}{2}1\right).$$
(13)
##### General case $`(D>1)`$.

The key observation to compute the number of routes $`L_{i,D}`$ passing through each node $`i`$ for $`D>1`$, is that there are several equivalent shortest paths along the Cartesian coordinates, because the coordinates of two consecutive nodes in a path cannot differ in more than one dimension. Consider for instance, for $`D=2`$, going from node (0,0) to node (1,1): both $`𝒫_1=(0,0)(1,0)(1,1)`$ and $`𝒫_2=(0,0)(0,1)(1,1)`$ are equivalent shortest paths. Therefore, we can always pick the path that corrects coordinates successively, starting with the first coordinate, i.e., $`𝒫_1`$ in the above example.

Consider a $`D`$-torus, as represented for $`D=3`$ in Figure 2, where each of the $`N=125`$ nodes is represented by a dot. The figure illustrate how requests are routed by correcting coordinates successively, with the example of three different paths, $`(2,3,2)(3,1,2)`$, $`(2,2,2)(0,4,0)`$, and $`(2,1,3)(4,0,4)`$. For any node $`k`$, we compute the number of routes passing through $`k`$. We denote the source of the route as node $`i`$, and the destination of the route as node $`j`$. We have $`ijk`$. We further denote the coordinates of $`i`$, $`j`$, and $`k`$ by $`(i_1,\mathrm{},i_D)`$, $`(j_1,\mathrm{},j_D)`$, and $`(k_1,\mathrm{},k_D)`$. We distinguish between the only three possibilities for $`k`$ that are allowed by the routing scheme that corrects coordinates one at a time:

1. Node $`k`$ has the same $`D`$-th coordinate as both the source $`i`$ and the destination $`j`$, i.e., $`i_D=j_D=k_D`$. In other words, the route $`𝒫=ij`$ is entirely contained within a $`(D1)`$-torus. This case is illustrated in the figure for the route represented by a solid line going from $`i=(2,3,2)`$ to $`j=(3,1,2)`$ through $`k=(3,2,2)`$. The corresponding $`(D1)`$-torus containing $`i`$, $`j`$ and $`k`$ is denoted by the shaded box. By definition of the node loading, the node loading resulting from all possible paths $`𝒫`$ contained in a $`(D1)`$-torus is equal to $`L_{i,D1}`$. There are $`n`$ different such $`(D1)`$-tori in the $`D`$-torus under consideration, one for each possible value of $`i_D=j_D=k_D`$. So, the total load incurred on each node by all paths which remain contained within a $`(D1)`$-torus is equal to $`nL_{i,D1}`$.
2. Nodes $`i`$, $`j`$ and $`k`$ all differ in their $`D`$-th coordinate, i.e., $`i_Dj_Dk_D`$. Because coordinates are corrected one at a time, for any $`l(1,\mathrm{},D1)`$, we must have $`k_l=j_l`$. This case is illustrated in the figure for the route represented by a dashed line, going from $`i=(2,2,2)`$ to $`j=(0,4,0)`$, through $`k=(0,4,1)`$. Since $`k_l=j_l`$, nodes $`j`$ and $`k`$ belong to the same ring where only the $`D`$-th coordinate varies. Such a ring is represented in the figure by the dotted curve. From node $`k`$’s perspective, routing traffic from $`i`$ to $`j`$ is equivalent to routing traffic between nodes $`i^{}`$ and $`j`$, where node $`i^{}`$ satisfies $`i_l^{}=k_l`$ for any $`l(1,\mathrm{},D1)`$, and $`i_D^{}=i_D`$. (In the figure, the coordinates of node $`i^{}`$ are $`(0,4,2)`$.) From our hypothesis $`k_Di_D`$, we have $`k_Di_D^{}`$, which implies $`ki^{}`$. Therefore, computing the number of routes passing through node $`k`$ coming from $`i`$ is equivalent to computing the number of routes passing through node $`k`$ and originating from node $`i^{}`$. Summing over all possible destination nodes $`j`$, the computation of all routes passing through $`k`$ and originating from all nodes $`i^{}`$ in the same ring as $`j`$ and $`k`$ is identical to the computation of the node loading in the base case $`D=1`$. So, the load imposed on node $`k`$ is equal to $`L_{i,1}`$. Now, summing over all possible nodes $`i`$ is equivalent to summing over all possible rings where only the $`D`$-th coordinate varies. There are are $`n^{D1}`$ such rings in the $`D`$-torus. We conclude that the total load incurred on each node $`k`$ by the paths going from all $`i`$ to all $`j`$ satisfying $`i_Dj_Dk_D`$ is equal to $`n^{D1}L_{i,1}`$.
3. Node $`k`$ has the same $`D`$-th coordinate as node $`i`$, and a $`D`$-th coordinate different from that of the destination $`j`$. In other words, $`i_Dj_D`$, $`i_D=k_D`$. This situation is illustrated in the figure for the route going from $`i=(2,1,3)`$ to $`j=(4,0,4)`$ and passing through $`k=(4,0,3)`$, and represented by a thick dotted line. In this configuration, there are $`(n1)`$ possible choices for the destination node $`j`$ such that $`j_Dk_D`$, and $`j_l=k_l`$ for $`lD1`$. There are $`n^{D1}1`$ possible choices for the source node $`i`$ such that $`i_D=k_D`$ and $`ij`$. Hence, in this configuration, there is a total of $`(n1)(n^{D1}1)`$ routes passing through each node $`k`$.

Summing the node loadings obtained in all three possible cases above, we obtain

$$L_{i,D}=nL_{i,D1}+n^{D1}L_{i,1}+(n1)(n^{D1}1).$$

Replacing $`L_{i,1}`$ by the expression given in Eqn. (13), using $`n=N^{1/D}`$, and removing the recursion in the above relationship, we obtain, for any node $`i`$,

$$L_{i,D}=N^{\frac{D1}{D}}\left(D\left(N^{\frac{1}{D}}1+\left(\frac{N^{\frac{1}{D}}}{2}1\right)\left(\frac{N^{\frac{1}{D}}}{2}1\right)\right)N^{\frac{1}{D}}\right)+1.$$

For all $`i`$, $`R_i`$ immediately follows from $`L_{i,D}`$ with

$$R_i=r\frac{L_{i,D}}{N^2}.$$

#### Plaxton trees

We next consider the variant of Plaxton trees  used in Pastry  or Tapestry . Nodes are represented by a string $`(i_1,\mathrm{},i_D)`$ of $`D`$ digits in base $`\mathrm{\Delta }`$. Each node is connected to $`D(\mathrm{\Delta }1)`$ distinct neighbors of the form $`(i_1,\mathrm{},i_{l1},x,y_{l+1},\mathrm{},y_D)`$, for $`l=1\mathrm{}D`$, and $`xi_l\{0,\mathrm{},\mathrm{\Delta }1\}`$.333For $`\mathrm{\Delta }=2`$, this geometry reduces to a hypercube. The resulting maintenance cost is $`M_i=mD(\mathrm{\Delta }1)`$.

Among the different possibilities for the remaining coordinates $`y_{l+1},\mathrm{},y_D`$, the protocols generally select a node that is nearby according to a spatial proximity metric. We here assume that the spatial distribution of the nodes is uniform, and that the identifier space is fully populated (i.e., $`N=\mathrm{\Delta }^D`$), which enables us to pick $`y_{l+1}=i_{l+1},\mathrm{},y_D=i_D`$. Thus, two nodes $`i`$ and $`j`$ at a distance of $`k`$ hops differ in $`k`$ digits. There are $`\left(\genfrac{}{}{0pt}{}{D}{k}\right)`$ ways of choosing which digits are different, and each such digit can take any of $`(\mathrm{\Delta }1)`$ values. So, for a given node $`i`$, there are $`\left(\genfrac{}{}{0pt}{}{D}{k}\right)(\mathrm{\Delta }1)^k`$ nodes that are at distance $`k`$ from $`i`$. Multiplying by the total number of nodes $`N=\mathrm{\Delta }^D`$, and dividing by the total number of paths $`N^2`$, we infer that, for all $`i`$, $`j`$, and $`k`$, we have

$$\text{Pr}[t_{i,j}=k]=\frac{\left(\genfrac{}{}{0pt}{}{D}{k}\right)(\mathrm{\Delta }1)^k}{N}.$$
(14)
Now, for any $`i`$ and $`j`$ such that $`t_{i,j}=l`$, because routes are unique, there are exactly $`(l1)`$ different nodes on the path between $`i`$ and $`j`$. So, the probability that a node $`k`$ picked at random is on the path from $`i`$ to $`j`$ is

$$\text{Pr}[\chi _{i,j}(k)=1|t_{i,j}=l]=\frac{l1}{N}.$$
(15)
The total probability theorem tells us that

$$\text{Pr}[\chi _{i,j}(k)=1]=\underset{l=1}{\overset{D}{}}\text{Pr}[\chi _{i,j}(k)=1|t_{i,j}=l]\text{Pr}[t_{i,j}=l].$$

Substituting with the expressions obtained for $`\text{Pr}[t_{i,j}=l]`$ and $`\text{Pr}[\chi _{i,j}(k)=1|t_{i,j}=l]`$ in Eqs. (14) and (15) gives:

$$\text{Pr}[\chi _{i,j}(k)=1]=\frac{1}{N^2}\underset{l=1}{\overset{D}{}}(l1)\left(\genfrac{}{}{0pt}{}{D}{l}\right)(\mathrm{\Delta }1)^l,$$
(16)
which can be simplified as follows. We write:

$$\underset{l=1}{\overset{D}{}}\left(\genfrac{}{}{0pt}{}{D}{l}\right)(l1)(\mathrm{\Delta }1)^l=(\mathrm{\Delta }1)^2\underset{l=1}{\overset{D}{}}(l1)\left(\genfrac{}{}{0pt}{}{D}{l}\right)(\mathrm{\Delta }1)^{l2},$$

and rewrite the right-hand term as a function of the derivative of a series,

$$\underset{l=1}{\overset{D}{}}\left(\genfrac{}{}{0pt}{}{D}{l}\right)(l1)(\mathrm{\Delta }1)^l=(\mathrm{\Delta }1)^2\frac{}{\mathrm{\Delta }}\left(\underset{l=1}{\overset{D}{}}\left(\genfrac{}{}{0pt}{}{D}{l}\right)(\mathrm{\Delta }1)^{l1}\right),$$

or, equivalently,

$$\underset{l=1}{\overset{D}{}}\left(\genfrac{}{}{0pt}{}{D}{l}\right)(l1)(\mathrm{\Delta }1)^l=(\mathrm{\Delta }1)^2\frac{}{\mathrm{\Delta }}\left(\frac{1}{\mathrm{\Delta }1}\underset{l=1}{\overset{D}{}}\left(\genfrac{}{}{0pt}{}{D}{l}\right)1^{Dl}(\mathrm{\Delta }1)^l\right).$$

The binomial theorem allows us to simplify the above to:

$$\underset{l=1}{\overset{D}{}}\left(\genfrac{}{}{0pt}{}{D}{l}\right)(l1)(\mathrm{\Delta }1)^l=(\mathrm{\Delta }1)^2\frac{}{\mathrm{\Delta }}\left(\frac{1}{\mathrm{\Delta }1}(1+\mathrm{\Delta }1)^D1\right),$$

which, making the partial derivative explicit, becomes,

$$\underset{l=1}{\overset{D}{}}\left(\genfrac{}{}{0pt}{}{D}{l}\right)(l1)(\mathrm{\Delta }1)^l=(\mathrm{\Delta }1)^2\left(\frac{D\mathrm{\Delta }^{D1}(\mathrm{\Delta }1)\mathrm{\Delta }^D+1}{(\mathrm{\Delta }1)^2}\right),$$

and reduces to

$$\underset{l=1}{\overset{D}{}}\left(\genfrac{}{}{0pt}{}{D}{l}\right)(l1)(\mathrm{\Delta }1)^l=\mathrm{\Delta }^{D1}(D(\mathrm{\Delta }1)\mathrm{\Delta })+1.$$

Substituting in Eqn. (16) gives:

$$\text{Pr}[\chi _{i,j}(k)=1]=\frac{\mathrm{\Delta }^{D1}(D(\mathrm{\Delta }1)\mathrm{\Delta })+1}{N^2},$$

which we multiply by $`r`$ to obtain

$$R_i=r\frac{\mathrm{\Delta }^{D1}(D(\mathrm{\Delta }1)\mathrm{\Delta })+1}{N^2}.$$
(17)
To compute the access cost $`A_i`$, we use the relationship $`A_i=aE[t_{i,j}]`$. We have

$$E[t_{i,j}]=\underset{k=1}{\overset{D}{}}k\text{Pr}[t_{i,j}=k],$$

which, using the expression for $`\text{Pr}[t_{i,j}=k]`$ given in Eqn. (14), implies

$$E[t_{i,j}]=\underset{k=0}{\overset{D}{}}k\frac{\left(\genfrac{}{}{0pt}{}{D}{k}\right)(\mathrm{\Delta }1)^k}{N},$$

and can be expressed in terms of the derivative of a classical series:

$$E[t_{i,j}]=\frac{\mathrm{\Delta }1}{N}\frac{}{\mathrm{\Delta }}\left(\underset{k=0}{\overset{D}{}}\left(\genfrac{}{}{0pt}{}{D}{k}\right)(\mathrm{\Delta }1)^k\right).$$

Using the binomial theorem, the series on the right-hand side collapses to $`\mathrm{\Delta }^D`$, which yields

$$E[t_{i,j}]=\frac{\mathrm{\Delta }1}{N}\frac{(\mathrm{\Delta }^D)}{\mathrm{\Delta }}.$$

We compute the partial derivative, and obtain

$$E[t_{i,j}]=\frac{D\mathrm{\Delta }^{D1}(\mathrm{\Delta }1)}{N}.$$

Multiplying by $`a`$ to obtain $`A_i`$, we eventually get, for all $`i`$,

$$A_i=a\frac{D\mathrm{\Delta }^{D1}(\mathrm{\Delta }1)}{N},$$

which can be simplified, using $`N=\mathrm{\Delta }^D`$:

$$A_i=aD\frac{\mathrm{\Delta }1}{\mathrm{\Delta }}.$$
(18)
#### Chord rings

In a Chord ring , nodes are represented using a binary string (i.e., $`\mathrm{\Delta }=2`$). When the ring is fully populated, each node $`i`$ is connected to a set of $`D`$ neighbors, with identifiers $`((i+2^m)mod2^D)`$ for $`m=0\mathrm{}D1`$. An analysis identical to the above yields $`R_i`$ and $`A_i`$ as in Eqs. (17) and (18) for $`\mathrm{\Delta }=2`$. Note that Eqn. (18) with $`\mathrm{\Delta }=2`$ is confirmed by experimental measurements .

### 3.2 Numerical results

We illustrate our analysis with a few numerical results. In Table 1, we consider five de Bruijn graphs with different values for $`\mathrm{\Delta }`$ and $`D`$, and $`X`$ and $`Y`$ i.i.d. uniform random variables. Table 1 shows that while the access costs of all nodes are comparable, the ratio between $`R_{\mathrm{max}}`$ and the second best case routing cost,444That is, the minimum value for $`R_i`$ over all nodes but the $`\mathrm{\Delta }`$ nodes in $`V^{}`$ for which $`R_i=0`$. $`R_{\mathrm{min}}^{}`$, is in general significant. Thus, if $`ra`$, there can be an incentive for the nodes with $`R_i=R_{\mathrm{max}}`$ to defect. For instance, these nodes may leave the network and immediately come back, hoping to be assigned a different identifier $`i^{}i`$ and incurring a lower cost. Additional mechanisms, such as enforcing a cost of entry to the network, may be required to prevent such defections.

We graph the access and routing costs for the case $`\mathrm{\Delta }=5`$, $`D=4`$ and $`N=625`$ in Figure 3. We plot the access cost of each node in function of the node identifier in Figure 3(a), and the routing cost of each node in function of the node identifier in Figure 3(b). Figure 3 further illustrates the asymmetry in costs evidenced in Table 1, by exhibiting that different nodes have generally different access and routing costs. Therefore, in a de Bruijn graph, there is potentially a large number of nodes that can defect, which, in turn, may result in network instability, if defection is characterized by leaving and immediately rejoining the network.

Next, we provide an illustration by simulation of the costs in the different geometries. We choose $`\mathrm{\Delta }=2`$, for which the results for Plaxton trees and Chord rings are identical. We choose $`D=\{2,6\}`$ for the $`D`$-dimensional tori, and $`D=\mathrm{log}_\mathrm{\Delta }N`$ for the other geometries. We point out that selecting a value for $`D`$ and $`\mathrm{\Delta }`$ common to all geometries may inadvertently bias one geometry against another. We emphasize that we only illustrate a specific example here, without making any general comparison between different DHT geometries.

We vary the number of nodes between $`N=10`$ and $`N=1000`$, and, for each value of $`N`$ run ten differently seeded simulations, consisting of 100,000 requests each, with $`X`$ and $`Y`$ i.i.d. uniform random variables. We plot the access and routing costs averaged over all nodes and all requests in Figure 4. The graphs show that our analysis is validated by simulation, and that the star provides a lower average cost than all the other geometries. In other words, a centralized architecture appears more desirable to the community as a whole than a distributed solution. However, we stress that we do not consider robustness against attack, fault-tolerance, or potential performance bottlenecks, all being factors that pose practical challenges in a centralized approach, nor do we offer a mechanism creating an incentive to be in the center of the star. While the cost model proposed here can be used to quantify the cost incurred by adding links for a higher resiliency to failures, we defer that study to future work.

## 4 Discussion

We proposed a model, based on experienced load and node connectivity, for the cost incurred by each peer to participate in a peer-to-peer network. We argue such a cost model is a useful complement to topological performance metrics , in that it allows to predict disincentives to collaborate (peers refusing to serve requests to reduce their cost), discover possible network instabilities (peers leaving and re-joining in hopes of lowering their cost), identify hot spots (peers with high routing load), and characterize the efficiency of a network as a whole.

We believe however that this paper raises more questions than it provides answers. First, we only analyzed a handful of DHT routing geometries, and even omitted interesting geometries such as the butterfly , or geometries based on the XOR metric . Applying the proposed cost model to deployed peer-to-peer systems such as Gnutella or FastTrack could yield some insight regarding user behavior. Furthermore, for the mathematical analysis, we used strong assumptions such as identical popularity of all items and uniform spatial distribution of all participants. Relaxing these assumptions is necessary to evaluate the performance of a geometry in a realistic setting. Also, obtaining a meaningful set of values for the parameters $`(s,a,r,m)`$ for a given class of applications (e.g., file sharing between PCs, ad-hoc routing between energy-constrained sensor motes) remains an open problem. Finally, identifying the minimal amount of knowledge each node should possess to devise a rational strategy, or studying network formation with the proposed cost model are other promising avenues for further research.


format: text

text:
# Identifying entanglement using quantum “ghost” interference and imaging

Permanent address: \]Department of Physics, Moscow State University, Moscow, Russia.

(January 21, 2004)

## Abstract

We report a quantum interference and imaging experiment which quantitatively demonstrates that Einstein-Podolsky-Rosen (EPR) type entangled two-photon states exhibit both momentum-momentum and position-position correlations, stronger than any classical correlation. The measurements show indeed that the uncertainties in the sum of momenta and in the difference of positions of the entangled two-photon satisfy both EPR inequalities $`\mathrm{\Delta }(k_1+k_2)<min(\mathrm{\Delta }k_1,\mathrm{\Delta }k_2)`$ and $`\mathrm{\Delta }(x_1x_2)<min(\mathrm{\Delta }x_1,\mathrm{\Delta }x_2)`$. These two inequalities, together, represent a non-classicality condition. Our measurements provide a direct way to distinguish between quantum entanglement and classical correlation in continuous variables for two-photons/two photons systems.

The concept of multi-particle quantum entanglement, one of the most surprising consequences of quantum mechanics, was introduced in the very early days of quantum theory schro ; EPR . Since the development of spontaneous parametric down-conversion (SPDC) as an efficient source of two-photon entangled states in late 1980’s Klyshkobook , many experiments have been realized to exhibit and, afterwards, to exploit the very surprising quantum effects of entangled states for secure communication, information processing, and metrology applications applications .

Some of the most intriguing effects of two-photon entanglement in SPDC are quantum ‘ghost’ interference and imaging Ghost\_d ; Ghost\_i . These effects are of great importance in potential applications like quantum metrology and lithography metro ; Dowling ; Milena . Recently, it has been claimed that the two-photon ‘ghost’ image can be achieved using a pair of classically k-vector correlated optical pulses Bob . Ref. Bob , therefore, raises interesting questions about fundamental issues of quantum theory, namely: (i) to what extent can quantum entanglement in continuous variables be simulated with classically correlated systems? and (ii) can we experimentally make a distinction between them?

In this Letter, we report an experiment which sheds light on these two tightly related questions. Our idea is to exploit quantum interference-imaging effects to verify experimentally the EPR-type inequalities, which allow distinguishing quantum entanglement from classical correlation in continuous variables, for two-photon systems. By analyzing the results of a two-photon interference and imaging experiment, we show quantitatively that entangled two-photon pairs exhibit both momentum-momentum and position-position EPR-type correlations, which are stronger than any classical correlation. In contrast, pairs of particles having a perfect classical correlation in momentum (or position), cannot exhibit any correlation in position (or momentum), due to the uncertainty principle. Our experiment, therefore, shows that entanglement in momentum and position variables for two-photon systems can be verified experimentally and suggests that the degree of entanglement can be quantified through the EPR-type non-classicality conditions. This result is of particular interest, since it represent a “Bell’s inequality” for continuous variables, for two-photon systems.

Consider a pair of EPR-correlated particles. As pointed out by EPR, the most peculiar characteristic of EPR-entanglement is its independency on the selected basis: entanglement in momentum automatically implies entanglement in position. In EPR notation EPR , the quantum state of entangled two-particle pairs can indeed be written as

$$\mathrm{\Psi }(x_1,x_2)=u_p(x_1)\psi _p(x_2)𝑑p=v_x(x_1)\varphi _x(x_2)𝑑x,$$

where $`x_1`$ ($`x_2`$) is the variable used to describe particle 1 (particle 2), $`u_p(x_1)`$ ($`\psi _p(x_2)`$) is the momentum eigenfunction for particle 1 (particle 2), and $`v_x(x_1)`$ ($`\varphi _x(x_2)`$) is the corresponding position eigenfunction obtained by Fourier transform of $`u_p(x_1)`$ ($`\psi _p(x_2)`$).

As suggested by EPR, an important consequence of entanglement appears explicitly by considering the case in which $`u_p(x_1)`$ ($`\psi _p(x_2)`$) is a plane wave. In this case the EPR entangled state assumes an interesting form:

$`\mathrm{\Psi }(x_1,x_2)={\displaystyle \delta (p_1+p_2)e^{ip_1x_1/\mathrm{}}e^{ip_2x_2/\mathrm{}}𝑑p_1𝑑p_2}=`$ (1)
$`=h\delta (x_1x_2).`$
A perfectly EPR-correlated particle pair should therefore be characterized by both the values $`\mathrm{\Delta }(p_1+p_2)=0`$ and $`\mathrm{\Delta }(x_1x_2)=0`$. However, even when these uncertainties are different from zero (non-perfect entanglement), they still satisfy the inequalities:

$`\mathrm{\Delta }(p_1+p_2)<min(\mathrm{\Delta }p_1,\mathrm{\Delta }p_2),`$ (2)
$`\mathrm{\Delta }(x_1x_2)<min(\mathrm{\Delta }x_1,\mathrm{\Delta }x_2).`$
The whole entangled system is indeed described in such a way that both the sum of the momenta and difference in the positions are known with a high degree of accuracy even if the momentum and position of each particle are completely undefined EPR . This result comes directly from the coherent superposition of two-particle amplitudes, which cannot be achieved by any classically correlated pairs of particles, as discussed in more details later.

We propose Eq. (2) as a non-classicality condition for continuous variables, for two-photon/two-particle systems. We report an experimental verification of Eq. (2) which exploits quantum ‘ghost’ interference and image effects of entangled two-photon pairs. We measure $`\mathrm{\Delta }(𝐤_1+𝐤_2)`$ from a quantum interference experiment and $`\mathrm{\Delta }(𝐫_1𝐫_2)`$ from a quantum imaging experiment, both realized using the same SPDC source. To the best of our knowledge a direct quantitative verification of Eq. (2) for two-photon system, i.e. for real momentum and position variables, has not been reported in literature squeezing .

Let us first examine whether SPDC two-photon pairs would really exhibit EPR-type entanglement. Under the assumption that the pump beam is a plane wave and the transverse dimensions of the pump beam and the down-conversion crystal are much bigger than the wavelengths of the photons, the quantum state of the SPDC two-photon pairs can be written as Rubin ; Rubin\_tr :

$$|\mathrm{\Psi }=\underset{s,i}{}\delta (\omega _s+\omega _i\omega _p)\delta (𝐤_s+𝐤_i𝐤_p)a_s^{}a_i^{}|0,$$
(3)
where $`\omega _j`$ and $`𝐤_j`$ (with $`j=s,i,p`$) are the frequency and wavevector of the signal (s), idler (i), and pump (p), respectively, and $`a_s^{}`$ ($`a_i^{}`$) is the creation operator for the signal (idler) photon. Since in this Letter we are only interested in the transverse correlation of the entangled two-photon pairs Rubin\_tr , the quantum state used in our experiment is indeed very close to the one of the original EPR-type entangled pairs of particles. Verification of non-classicality using Eq. (2) should then be possible through adequate experiments realized with this source.

A schematic of the experimental setup can be seen in Fig. 1. The $`351.1`$ nm line of an argon ion laser is used to pump a BBO crystal cut for type-II collinear degenerate parametric down conversion. Pairs of orthogonally polarized signal and idler photons at central wavelength $`\lambda _i=\lambda _s=702.2`$ nm, which are entangled in momentum, emerge from the crystal almost collinearly with the pump laser. After the crystal, the pump laser beam is separated from the SPDC beam by a quartz dispersion prism. A polarization beam splitting Thompson prism separates the co-propagating signal and idler into two separate spatial modes. The signal photon propagates through a double-slit toward a detector package ($`D_1`$) consisting of a collection lens ($`500`$ mm focal length) and a single photon detector placed in its focus. The idler photon propagates freely before being collected by the imaging lens ($`f=510`$ mm). A 50-50 beam splitter (BS) is inserted after the lens. The reflected and transmitted photons are then detected by single photon detectors $`D_2`$ and $`D_3`$, respectively. Each of them is mounted on an encoder driver to scan its own transverse plane. A spectral filter centered at $`702.2`$ nm with $`3`$ nm bandwidth precedes each detector. The output pulses of the detectors are sent to a coincidence circuit ($`CC`$). Coincidences are measured between $`D_1`$ and $`D_2`$ and between $`D_1`$ and $`D_3`$.

This setup therefore allows to measure both ‘ghost’ interference-diffraction and ‘ghost’ image patterns of the double-slit Ghost\_d ; Ghost\_i . Indeed, the coherent superposition of biphoton amplitudes allows exploiting the momentum-momentum correlation to obtain an image (position-position correlation) by simply changing the observation plane ($`D_3`$, instead of $`D_2`$) Rubin\_tr ; Rubinnew ; Gatti . The results are shown in Fig. 2. The single counts on both $`D_2`$ and $`D_3`$, which are scanned in the transverse direction, show no features at all. The single counting rate of $`D_1`$, when the detector scans the focal plane of the collection lens, did not show any interference fringes as well: only a wide bell-shaped pattern was observed. This result is due to the fact that biphotons are generated with all possible momenta $`𝐤_i`$ and $`𝐤_s`$ such that $`𝐤_s+𝐤_i=𝐤_p`$ is satisfied. In our experiment, the divergence of the SPDC beam $`\mathrm{\Delta }(\theta )`$, which takes into account the filters bandwidth, the dispersion in the crystal, and the phase matching condition, is such that: $`\mathrm{\Delta }(\theta )2.6\text{ mrad}\lambda /d,`$ where $`d=0.4`$ mm is the distance between the slits and $`\lambda =702.2`$ nm is the central wavelength of the SPDC photons. Under this condition, the first order interference-diffraction pattern on $`D_1`$ is simply washed out.

It is, however, possible to observe a ‘ghost’ interference-diffraction pattern when counting coincidences between $`D_1`$ and $`D_2`$ ($`D_1`$ is fixed and $`D_2`$ is scanned in the focal plane of the imaging lens) and to observe a ‘ghost’ image pattern in coincidences between $`D_1`$ and $`D_3`$ ($`D_1`$ is, again, fixed and $`D_3`$ is scanned in the image plane).

For ‘ghost’ interference-diffraction measurement, the detector package $`D_1`$ plays the role of a point-like detector. As shown in Ref. Ghost\_d , we expect the coincidence counting rate to be:

$$R_c(x_2)\mathrm{sinc}^2[x_2\pi a/(\lambda f)]\mathrm{cos}^2[x_2\pi d/(\lambda f)],$$
(4)
where $`x_2`$ is the transverse position of detector $`D_2`$ in the focal plane of $`L_2`$. Figure 2(a) shows the ‘ghost’ interference measurement. The continuous line in Fig. 2(a) is a fitting of the experimental data, which takes into account both the finite size of the detectors, the divergence of the pump and the less-than-perfect correlation between signal and idler. It is well known that the visibility of the interference pattern ($`1+V\mathrm{cos}[2x_2\pi d/(\lambda f_2)]`$) is related to the degree of transverse coherence of the source. We exploit this effect to evaluate the less-than-perfect transverse correlation between signal and idler photons:

$$\mathrm{\Delta }(k_{x_s}+k_{x_i})=2.5\pm 0.6\text{ mm}^1.$$

From the divergence of the SPDC beam $`\mathrm{\Delta }(\theta )`$ mentioned above we evaluate $`\mathrm{\Delta }k_{x_j}23\text{ mm}^1`$, for $`j=i,s`$. So the ghost interference/diffraction experiment demonstrates that:

$$\mathrm{\Delta }(k_{x_s}+k_{x_i})min(\mathrm{\Delta }k_{x_i},\mathrm{\Delta }k_{x_s}),$$

for our SPDC source.

In a similar way, we obtain $`\mathrm{\Delta }(𝐫_s𝐫_i)`$ by studying the ‘ghost’ image obtained by measuring coincidences between $`D_1`$ and $`D_3`$, see Fig. 2(b). To observe a ‘ghost’ image, the two-photon Gaussian thin lens equation, $`1/s_i+1/s_o=1/f`$, where $`s_i=b`$ and $`s_o=a_1+a_2`$, should be satisfied Ghost\_i . In the ideal situation the detector package $`D_1`$ is a perfect a bucket detector, which detects any signal photon that have not been stopped by the double slit. The role of the double slit is then to measure the localization of the signal with an uncertainty $`\mathrm{\Delta }(x_s)`$, equal to the slit width $`a`$. In the ideal case, counting coincidences between $`D_1`$ and $`D_3`$, we would obtain two rectangles of width $`a^{}=ma`$, and center-to-center distance $`d^{}=md`$, where $`m=s_i/s_o`$ is the magnification. In our case $`m=1.8`$, $`a=0.165`$ mm, $`d=0.4`$ mm and the corresponding ideal result ($`a^{}=0.297`$ mm, $`d^{}=0.72`$ mm) is plotted as dashed line in Fig. 2(b). To take into account a more realistic situation we fit the data with the convolution of the double slit with a Gaussian function that takes into account the finite size of $`D_2`$. The comparison of the resulting fitting curve with the theoretical result, dashed line in Fig. 2(b), allows to evaluate $`\mathrm{\Delta }(x_sx_i)`$, as the difference between the FWHM of the two curves:

$$\mathrm{\Delta }(x_sx_i)=0.11\pm 0.02\text{ mm}\mathrm{\Delta }x_s.$$

Note that the center-to-center distance between the bell-shaped fitting curve and the two rectangles is exactly the same. The imperfect correlation in position is evidently smaller than the distance between the two slits.

The non-classicality conditions introduced in Eq. (2) are then satisfied for the momentum and position variables of entangled two-photon of SPDC. As we mentioned earlier, this result is a direct consequence, if not the definition, of quantum correlation: particles that are entangled in momentum are automatically entangled in position. Only entangled particles can satisfy such inequalities.

An interesting way of understanding this result is the following. The Fourier transform of an entangled state such as the one given in Eq. (1) and (3), can be factorized by introducing the variables $`𝐤_1+𝐤_2`$ and $`𝐤_1𝐤_2`$. The corresponding Fourier transformed variables are $`𝐫_1+𝐫_2`$ and $`𝐫_1𝐫_2`$, respectively. Since $`𝐤_1+𝐤_2`$ and $`𝐫_1𝐫_2`$ are not conjugate variables, Eq.s (2) can definitely be true simultaneously. For this same reason, also the product of the two uncertainties can be smaller than one. Indeed we obtain from the uncertainties evaluated above:

$$\mathrm{\Delta }(k_{x_s}+k_{x_i})\mathrm{\Delta }(x_sx_i)=0.3\pm 0.1<1,$$
(5)
Note however that this last inequality is a necessary but not sufficient condition for entanglement EPR ineq .

Let us now consider the case of two particles or beams classically correlated in momentum. An example of such a source is given by a pair of bounded identical guns which emit (quantum) particles while rotating simultaneously, in such a way that the momenta of the two particles are always equal in modulus but with opposite direction. Each pair of independent but correlated particles, fired at a certain angle at a given time, may be described by:

$$|\mathrm{\Psi }_j_{12}=a_1^{}(𝐤_j)a_2^{}(𝐤_j)|0.$$

If each pair of particles has (non-negative) probability $`P(𝐤_j)`$ of being emitted by the source, the resulting incoherent statistical mixture is described by the following density matrix:

$$\rho _{12}=\underset{𝐤_j}{}P(𝐤_j)|\mathrm{\Psi }_j_{\mathrm{12\hspace{0.25em}12}}\mathrm{\Psi }_j|=\underset{𝐤_j}{}P(𝐤_j)\rho _1^j\rho _2^j$$
(6)
where $`\rho _1^j=|𝐤_j_{\mathrm{1\hspace{0.25em}1}}𝐤_j|`$ and $`\rho _2^j=|𝐤_j_{\mathrm{2\hspace{0.25em}2}}𝐤_j|`$ are the density matrices for particles 1 and 2, respectively, belonging to the $`j^{th}`$ pair. It is well known that for each particle to propagate with such a perfectly well defined momentum, the sources have to be infinite in the transverse direction pointsource ; Popper\_exp . Therefore, pairs of particles with a perfect momentum-momentum correlation do not exhibit any position-position correlation. In the more realistic case of finite transverse dimension of the source, the position-position correlation improves at the expenses of the momentum-momentum correlation: each particle is always diffracted independently. In general, any attempt to improve the classical correlation in one variable inevitably worsens the correlation in the other. Thus the classical statistical inequalities:

$`\mathrm{\Delta }(k_1+k_2)=\sqrt{(\mathrm{\Delta }k_1)^2+(\mathrm{\Delta }k_2)^2}>max(\mathrm{\Delta }k_1,\mathrm{\Delta }k_2),`$ (7)
$`\mathrm{\Delta }(x_1x_2)=\sqrt{(\mathrm{\Delta }x_1)^2+(\mathrm{\Delta }x_2)^2}>max(\mathrm{\Delta }x_1,\mathrm{\Delta }x_2),`$
can never be violated by pairs of classically correlated particles/beams.

In conclusion, any source of classically correlated pairs of particles: i) can never achieve perfect correlation in both momentum and position variables; ii) can never satisfy inequalities Eq. (2).

In summary, we have experimentally demonstrated that SPDC photon pairs satisfy the EPR-type non-classicality condition Eq. (2). In doing so, we have shown that entangled particles exhibit almost perfect $`both`$ momentum-momentum $`and`$ position-position correlations. Classically correlated pairs of particles cannot exhibit such behavior. The measurement described in this Letter thus provides a direct way to distinguish between quantum entanglement and classical correlation in momentum and/or position variables, for two-photon systems. An important practical consequence is that only the non-local correlation implicit in entangled systems allows to ‘overcome’ the usual diffraction limit and to obtain super-resolved images, as proposed and demonstrated in Ref. Dowling ; Milena ; Popper\_exp . Furthermore, our experiment shows that a distinction between classically correlated and quantum entangled systems, in momentum and/or position variables, can be realized experimentally through the study of “ghost” imaging-type experiments explain . This is a quite different approach with respect to Bell’s inequality and may represent an extension of Bell’s inequality, in optics.

The authors thank M.H. Rubin and V. Protopopescu for helpful comments and discussions. This work was supported, in part, by ARDA, NASA-CASPR program, NSF, and ONR. The Oak Ridge National Laboratory is managed by UT-Battelle, LLC, for the U.S. DOE under contract DE-AC05-00OR22725.


text:
# Normal forces in stationary spacetimes

## Abstract

Abstract

For geodesic motion of a particle in a stationary spacetime the $`U_0`$ component of particle 4-velocity is constant and is considered to be a conserved mechanical energy. We show that this concept of a conserved mechanical energy can be extended to particles that move under the influence of a “normal force,” a force that, in the stationary frame, is orthogonal to the motion of the particle. We illustrate the potential usefulness of the concept with a simple example.

For a particle with 4-velocity $`\stackrel{}{U}`$, moving on a geodesic in a spacetime with timelike Killing vector $`\stackrel{}{\xi }`$, it is well known that the quantity

$$E\stackrel{}{U}\stackrel{}{\xi }$$
(1)
is conserved along the geodesic particle world lineWald84 . The quantity $`E`$ can then be taken to be a conserved mechanical energy (per unit particle mass), analogous to the classical mechanical energy that includes gravitational potential energy. In Newtonian mechanics this concept can be extended to particles that move under the influence of normal forces, forces that serve only to constrain the particle motion to a geometric path. Newtonian normal forces are orthogonal to the velocity of the particle, and therefore perform no work on the particle and do not change the mechanical energy. Here we show that this can also be made to apply for relativistic gravitation. We extend the idea of a normal forces to stationary spacetime, and we show that under the influence of such normal forces, the quantity $`E`$ of Eq. (1) is conserved. Though this concept is quite simple, basic, and potentially useful, it does not seem to appear in textbooks.

Our definition of normal force uses the operator $`P_\stackrel{}{\xi }`$ which projects any vector $`\stackrel{}{w}`$ to

$$P_\stackrel{}{\xi }(\stackrel{}{w})=\stackrel{}{w}\left[\frac{\stackrel{}{\xi }\stackrel{}{w}}{\stackrel{}{\xi }\stackrel{}{\xi }}\right]\stackrel{}{\xi },$$
(2)
so that $`P_\stackrel{}{\xi }(\stackrel{}{w})`$ is orthogonal to $`\stackrel{}{\xi }`$. Using this operator, we take $`P_\stackrel{}{\xi }(\stackrel{}{U})`$ and $`P_\stackrel{}{\xi }(\stackrel{}{a})`$ respectively to be the spatial velocity and acceleration of the particle. Our condition that only normal forces are acting on a particle is the condition that the particle’s spatial acceleration is orthogonal to its spatial velocity, or

$$P_\stackrel{}{\xi }(\stackrel{}{U})P_\stackrel{}{\xi }(\stackrel{}{a})=0\text{normal force definition}.$$
(3)
A straightforward substitution of Eq. (2) into (3) gives

$$P_\stackrel{}{\xi }(\stackrel{}{U})P_\stackrel{}{\xi }(\stackrel{}{a})=\stackrel{}{U}\stackrel{}{a}\frac{(\stackrel{}{\xi }\stackrel{}{U})(\stackrel{}{\xi }\stackrel{}{a})}{(\stackrel{}{\xi }\stackrel{}{\xi })}.$$
(4)
Since $`\stackrel{}{U}\stackrel{}{a}`$ must be zero, and $`\stackrel{}{\xi }\stackrel{}{U}`$ cannot be zero, it follows that

$$\stackrel{}{\xi }\stackrel{}{a}=0.$$
(5)
We now take the derivative $`dE/d\tau `$ where $`E`$ is the energy defined in Eq. (1) and $`\tau `$ is proper time along the worldline:

$$\frac{dE}{d\tau }=_\stackrel{}{U}\left(\stackrel{}{U}\stackrel{}{\xi }\right)=\stackrel{}{a}\stackrel{}{\xi }+\stackrel{}{U}_\stackrel{}{U}\xi .$$
(6)
The last term $`U^\alpha \xi _{\alpha ;\beta }U^\beta `$ vanishes if $`\stackrel{}{\xi }`$ is a Killing vector, and the first term vanishes if the particle is acted on only by normal forces. The energy $`E`$ is therefore constant along the worldline.

This extended concept of conserved mechanical energy is most usefully applied in a coordinate system with $`\stackrel{}{\xi }=/x^0`$, and the metric coefficients independent of time $`x^0`$. (We use units in which $`c=G=1`$ and other conventions of Misner et al.MTW .) We suppose that the path to which the normal forces constrain the particle is specified through $`x^j(\lambda )`$, where $`x^j`$ is a spatial coordinate and $`\lambda `$ is some curve parameter. We suppose also that the energy $`E\stackrel{}{U}\stackrel{}{\xi }=U_0`$ is specified. From $`\stackrel{}{U}\stackrel{}{U}=1`$ we have

$$1=g_{00}\left(U^0\right)^2+g_{ij}\frac{dx^i}{d\tau }\frac{dx^j}{d\tau }.$$
(7)
Here and below, summation over spatial indices $`i,j,\mathrm{}`$ is understood. Equation (7) gives us

$$1=g_{00}^1\left(Eg_{0j}\frac{dx^j}{d\lambda }\frac{d\lambda }{d\tau }\right)^2+g_{ij}\frac{dx^i}{d\lambda }\frac{dx^j}{d\lambda }\left(\frac{d\lambda }{d\tau }\right)^2.$$
(8)
In this equation, the metric coefficients $`g_{00}`$,$`g_{0j}`$, and $`g_{ij}`$ are known functions of $`x^j`$, and hence of $`\lambda `$. The only unknown in Eq. (8), then, is $`d\lambda /d\tau `$, and Eq. (8) is an ordinary differential equation for $`\lambda (\tau )`$. Once this is solved, $`x^j(\tau )`$, and hence the dynamics, is completely determined.

As a simple explicit example, for the Schwarzschild spacetime expressed in the usual coordinates,

$$ds^2=\left(12M/r\right)dt^2+\left(12M/r\right)^1dr^2+r^2\left(d\theta ^2+\mathrm{sin}^2\theta d\varphi ^2\right)$$
(9)
we consider the “straight” curve $`r\mathrm{cos}\varphi =b`$ in the $`\theta =\pi /2`$ equatorial plane. From $`\stackrel{}{U}\stackrel{}{U}=1`$ we have

$$1=\frac{E^2}{12M/r}+\left[\frac{r^2b^2}{12M/r}\frac{r^2}{b^2}+r^2\right]\left(\frac{d\varphi }{d\tau }\right)^2.$$
(10)
From this and $`r=b/\mathrm{cos}\varphi `$, we can find $`\varphi (\tau )`$, $`r(\tau )`$, $`\varphi (t)`$, and so forth.

It is particularly interesting to see the effect of the normal force on $`LU_\varphi =r^2d\varphi /d\tau `$. For geodesic motion in an azimuthally symmetric spacetime, $`L`$ is a conserved quantity considered to be particle angular momentum per unit mass. For the nongeodesic motion along $`r\mathrm{cos}\varphi =b`$, we have, from Eq. (10), that

$$L^2=b^2\frac{E^21+2M/r}{12Mb^2/r^3}.$$
(11)
Since $`L`$ is not constant, we can conclude that the normal force applies a torque to the particle.


text:
# Strongly Correlated Superconductivity and Pseudogap Phase near a multi-band Mott Insulator

## Abstract

Near a Mott transition, strong electron correlations may enhance Cooper pairing. This is demonstrated in the Dynamical Mean Field Theory solution of a twofold-orbital degenerate Hubbard model with an inverted on-site Hund rule exchange, favoring local spin-singlet configurations. Close to the Mott insulator, which here is a local version of a valence bond insulator, a pseudogap non-Fermi-liquid metal, a superconductor, and a normal metal appear, in striking similarity with the physics of cuprates. The strongly correlated s-wave superconducting state has a larger Drude weight than the corresponding normal state. The role of the impurity Kondo problem is underscored.

How superconductivity emerges so spectacularly out of a weakly doped Mott insulator is one of the fascinating and still controversial aspects of high Tc cuprate superconductors. A novel strongly correlated superconductivity (SCS) scenario has been recently proposed Capone-Science  which deals with an ultimately related basic issue, namely the conditions under which Cooper pairing can be enhanced, rather than depressed, by strong electron repulsion. The key of the SCS proposal is the presence of pairing interaction term $`J`$, which is weak but is not suppressed by the strong short-range repulsion $`U`$. This is realized for an attraction which involves mainly spin and orbital degrees of freedom, which are not frozen near a Mott metal-insulator transition (MIT). In addition, close to the MIT, correlations slow down electron motion so much that the effective quasiparticle bandwidth becomes extremely small $`W_{qp}W`$, $`W`$ being its uncorrelated value. In these conditions the pairing attraction can eventually equal the quasiparticle bandwidth $`JW_{qp}`$. That drives the system to an intermediate-strong coupling superconducting regime where the maximum superconducting gap $`\mathrm{\Delta }J`$ for given value of $`J`$ is reached, as opposed to the much smaller uncorrelated BCS value $`\mathrm{\Delta }_{BCS}W\mathrm{exp}(W/J)`$. A first theoretical realization of SCS was demonstrated in Ref. CaponePRL ; Capone-Science  by a Dynamical Mean Field Theory (DMFT)DMFT  solution of a three-fold degenerate model for tetravalent fullerides. It was shown that a narrow SCS region arises next the MIT, and is indeed characterized by a superconducting gap three orders of magnitude larger that the value one would obtain for the same attraction in the absence of correlation.

DMFT maps a lattice model onto an Anderson impurity (AI) model subject to a self-consistency condition. Within this mapping SCS emergesCaponePRL  through a competition between Kondo screening of the impurity (leading to a normal Fermi liquid) and an intra-impurity mechanism which forms a local non-degenerate singlet (a kind of local resonating valence bond statePWA ). This requires orbital degeneracy and inversion of Hund’s rules, both ingredients present in the model of Ref. Capone-Science . More recently a simpler AI with only twofold orbital degeneracy was shown by Wilson Numerical Renormalization Group (NRG) to display anomalous propertiesDeLeo , suggesting its lattice generalization as a new candidate for a SCS.

In this Letter we present a detailed DMFT analysis that confirms this expectation, exploiting the lower degeneracy for a wider and more revealing study. We consider an infinite coordination Bethe lattice and solve the AI by exact diagonalization. The model reads DeLeo

$$\widehat{H}=t\underset{<ij>,a,\sigma }{}c_{i,a\sigma }^{}c_{j,a\sigma }^{}+H.c.+\frac{U}{2}\underset{i}{}n_i^2+\widehat{H}_J,$$
(1)
where $`c_{i,a\sigma }^{}`$ creates an electron at site $`i`$ in orbital $`a=1,2`$ with spin $`\sigma `$, while $`n_i=_{a,\sigma }c_{i,a\sigma }^{}c_{i,a\sigma }^{}`$ is the on-site occupation number. The on-site exchange is

$$\widehat{H}_J=2J\underset{i}{}\left(T_{i,x}^2+T_{i,y}^2\right),$$
(2)
where $`T_{i,\alpha }=1/2_{a,b}_\sigma c_{i,a\sigma }^{}\left(\widehat{\tau }^\alpha \right)_{ab}c_{i,b\sigma }^{}`$ are the pseudo-spin 1/2 operators, and $`\widehat{\tau }^\alpha `$ ($`\alpha =x,y,z`$) the Pauli matrices. The electronic states of the isolated site with $`n`$ electrons are labeled by total spin and pseudo-spin, $`S`$ and $`T`$ and their $`z`$-components, and have energies $`E(n,S,S_z,T,T_z)=Un^2/22J[T(T+1)T_z^2]`$. For $`n=2`$ the configurations allowed by Pauli principle are a spin triplet orbital singlet ($`S=1`$ and $`T=0`$) and a spin singlet orbital triplet ($`S=0`$ and $`T=1`$), split by $`\widehat{H}_J`$. If $`J<0`$, standard Hund’s rules, the spin triplet has the lowest energy. Here we consider the less common case of $`J>0`$, where the lowest energy configuration has $`S=0`$, $`T=1`$ and $`T_z=0`$. This inversion of Hund’s rules may for instance mimic a dynamical $`eE`$ Jahn-Teller effectCapone-Science ; CaponePRL . Here it just represents a generic mechanism for on-site spin-singlet pairing. Indeed, for $`U=0`$ and $`JW`$, the ground state of (1) is an $`s`$-wave BCS superconductor with pairs condensed in the $`S=0`$, $`T=1`$ and $`T_z=0`$ channel. The energy gap is $`\mathrm{\Delta }W\mathrm{exp}(1/\lambda )`$, where $`\lambda =2JN_F`$ is the dimensionless superconducting coupling, and $`N_F`$ the density of states (DOS) at the Fermi energy per spin and orbital. In this regime, a finite $`UW`$ introduces a “Coulomb” pseudopotential $`\mu _{}=UN_F`$ that opposes superconductivity, eventually suppressed for $`U>2J`$ in favor of a normal metal ground state. For larger $`UU_cW`$, the model (1) undergoes a MIT for all integer fillings $`n=1,2,3`$. We could generally expect the superconducting gap to decrease monotonically as a function of $`U`$, the superconductor either turning directly into a Mott insulator (for $`\lambda 1`$), or (when $`\lambda 1`$) first into a metal, and then into the insulator. This is indeed what we find for $`n=1`$ (equivalent to $`n=3`$ by particle-hole symmetry) and $`\lambda `$ ranging from 0.1 to 0.6. The picture is however richer in the half-filled $`n=2`$ case, as reported in Fig. 1, where the standard superconductor evolves continuously to the SCS regime If $`\lambda `$ is large (e.g.,$`J/W=0.15`$), $`\mathrm{\Delta }`$ decreases with increasing $`U`$, as in a BCS superconductor, until a weakly first order transition to our local-RVB insulator occursGunnarsson . For smaller $`\lambda `$ however, the dependence of $`\mathrm{\Delta }`$ on $`U`$ is non-monotonic, and the initial drop for small $`U`$ is followed by a rise. Finally, for the smallest values of $`\lambda `$, the weak-$`U`$ superconductor first turns into a metal but, just before the MIT, reverts back to a superconductor, as in SCS of Ref. Capone-Science . Here too the superconducting gap reaches values much larger than those attained for the same pairing attraction $`\lambda `$ but for $`U`$ = 0 (compare the inset and the right-hand side of Fig. 1).

The appearance of SCS in (1) for $`n=2`$ supports the AI analysis DeLeo . Indeed, as $`U`$ increases, the quasiparticle bandwidth, which is the AI effective Kondo temperature $`T_K`$, is gradually suppressed by the dropping quasiparticle residue $`Z1`$, $`T_KZW`$. At the same time, we expect $`J`$ to remain unrenormalized Capone-Science  . $`H_J`$ splits multiplets with same $`n`$, and that can happen without opposing $`U`$, which just freezes charge fluctuations regardless of either spin or orbital degrees of freedom. As $`Z`$ decreases, the AI enters the critical region around its unstable fixed-point DeLeo  at a critical $`T_K^{(c)}J`$. For $`T_K>T_K^{(c)}`$, the AI is in the Kondo screened regime, while for $`T_K<T_K^{(c)}`$ an intra-impurity singlet forms thanks to the inverted exchange $`J`$. At the fixed point the two effects balance exactly, leading to a residual entropy $`\mathrm{ln}\sqrt{2}`$. The remaining impurity degrees of freedom are quenched at a larger temperature $`T_+max(T_K,J)`$. $`T_{}|T_KT_K^{(c)}|^2/T_K^{(c)}`$ measures the deviation from the fixed point behavior. It was argued in Ref. DeLeo  that DMFT self-consistency should turn this AI instability into a true bulk one, most likely implying superconductivity. This is now confirmed by our DMFT analysis. S-wave superconductivity opens up a new screening route which freezes the residual entropy, otherwise quenched only below $`T_{}`$DeLeo . This suggests that (a) the energy scale which controls superconductivity should be related to $`T_+T_{}`$; (b) the onset of superconductivity should be accompanied by a kinetic energy gain at low frequency, as Kondo screening implies. A kinetic energy (or, more accurately, band energy) gain may be regarded as a signal of SCS (as opposed to BCS where kinetic energy rises), and that is reflected by the behavior of the Drude weight. In Fig. 2 we show for $`J=0.05W`$ the Drude weight of the stable superconducting solution for $`0.7U/WU_c`$ (here the Drude weight is the strength of the superfluid peak), in comparison with that of the unstable metallic solution (obtained disallowing superconductivity), taken to represent the normal phase. Fig. 2 shows a large increase of Drude weight with superconductivity, an occurrence also predictedHirsch ; Baskaran  and actually observed in cupratesVanDerMarel . Here the unstable metal Drude weight actually appears to vanish at $`U_{}<U_c`$. As we shall show, this reflects the opening of a pseudogap at the chemical potential before the MIT.

Additional physical insight is gained by analyzing the DOS in the strongly correlated region $`U/W>0.7`$. Within DMFT, the DOS in this region of parameters displays three features: Two high-energy Hubbard bands and a low-energy feature associated to quasiparticles. Fig. 3 displays the evolution of the DOS of the normal state solution in this regime, and shows that a pseudogap opens within the low-energy peak. A similar pseudogap appeared also in the NRG solution of the AI of Ref. DeLeoDOS , where it was argued that the low-energy DOS around the unstable fixed point is well described by

$$\rho (\omega )=\frac{\rho _0}{2}\left(\frac{T_+^2}{\omega ^2+T_+^2}\pm \frac{T_{}^2}{\omega ^2+T_{}^2}\right).$$
(3)
where $`\rho _0`$ is the non-interacting DOS, and plus/minus refers to the Kondo screened/unscreened phase. We find that (3) fits well also the low-frequency behavior of the DMFT resultsnota-semicircolare . Eq. (3) implies that at the chemical potential $`\rho (0)=\rho _0`$ in the Kondo screened regime, compatible with a Fermi-liquid with $`m\mathrm{\Sigma }(\omega )\omega ^2`$. On the contrary, the DOS values at $`T_{}=0`$, $`\rho (0)=\rho _0/2`$, and in the pseudogap phase, $`\rho (0)=0`$, imply a singular behavior of the self-energy, i.e., a non-Fermi liquid.

The best-fit values of $`T^+`$ and $`T^{}`$ for $`J=0.05W`$ are shown in Fig. 4, and compared with the superconducting gap $`\mathrm{\Delta }`$.

The maximum of $`\mathrm{\Delta }`$ almost coincides with the vanishing of $`T_{}`$, which corresponds to the AI unstable fixed point. Fig. 4 suggests a scenario which shares similarities to the quantum critical pointquantum-critical-point  and the gauge theory-slave bosonslave-bosons  pictures of cuprates. For temperatures $`T`$ above $`T_c`$ (presumably of order $`\mathrm{\Delta }`$), but below $`T_{}`$, the normal phase is a Fermi-liquid for $`U<U_{}`$, and a non Fermi-liquid pseudogap phase for $`U_c>U>U_{}`$. For $`T_{}<T<T_+`$, both the narrow Fermi-liquid quasiparticle peak and the pseudogap should be washed out, leaving a broader resonance reflecting the properties of the non Fermi-liquid AI unstable fixed point. The resonance will eventually disappear above $`T_+`$. Close to the MIT, the unstable metallic solution and the stable superconductor have almost the same energy and very similar DOS, but for the presence of a very small superconducting gap. From this point of view, the pseudogapped unstable phase plays a role similar to the staggered flux phase within the SU(2) invariant slave-boson description of the $`t`$-$`J`$ model, and may therefore be thought as a phase with broken symmetry in the particle-hole or in the particle-particle channels, where the full symmetry is restored by fluctuationsslave-bosons . We note here that (a) superconductivity is not an accidental route which the lattice system takes to rid itself of competition among other phases, but is one of the pre-determined instabilities of the AI; (b) attempts to uncover the fixed point by suppressing superconductivity would likely spoil the fixed point or unveil other instabilities of the lattice model.

The analogy with high Tc cuprates becomes even more suggestive when we analyze the phase diagram away from half-filling, and follow the fate of superconductivity upon doping.

SCS extends (Fig. 5) into a superconducting pocket away from $`n=2`$. When we dope the singlet Mott insulator just above the MIT, a pseudogap metallic phase is encountered first, followed by a narrow superconducting region which finally gives way to a normal metal (inset of Fig. 5), in remarkable similarity to the phase diagram of high Tc cuprates. Striking is also the similarity in the Drude weight (inset), which is zero in the Mott insulator at half-filling and increases almost linearly upon doping. The phase diagram of Fig. 5 again agrees with the AI analysisDeLeoDOS , which shows that the unstable fixed point still exists away from half-filling.

In the alkali fulleride models, that provide our prime examples of SCS, the physics which leads to $`J>0`$ and spin pairing is Jahn Teller, i.e. a conventional phonon effect.CaponePRL ; Capone-Science ; Han  Future experiments to test the SCS scenario by comparing Drude weights in presence and in absence of superconductivity should be actively considered in trivalent fullerides such as K3NH3C60.NH3  These materials are of extraordinary importance, for they show a similar “universal” contiguity between superconductivity and Mott insulating behavior as the high Tc cuprates do, albeit with different physical ingredients. When dealing with spectroscopies, one should keep in mind that there are now two low-energy scales, $`T_+`$ and $`T_{}`$. That makes, e.g., photoemission data such as the recent ones on K3C60Goldoni  especially difficult to analyze, even ignoring the heavy vibronic structures. In the SCS region, coherent band-like dispersion should occur with a reduced bandwidth of order $`2T_+`$, a scale which remains finite across the MIT, even though the system is strongly correlated. The true quasiparticle peak will instead become extremely narrow, of order $`T_{}`$, or even disappear in the pseudogap regime. We believe that the dataGoldoni  are actually compatible with the SCS scenario. The underlying Kondo physics offers a new intriguing insight in this superconductivity problem. It seems in fact that the onset of bulk coherence close to a MIT may involve a hierarchy of energy scales, $`T_{}<T_+`$ and $`\mathrm{\Delta }`$. The latter is the most sought-after, as it marks the onset of lattice long-range order. On the contrary, $`T_+`$ and $`T_{}`$ have their clearest meaning in the AI, which displays a two-stage quenching of the impurity entropy.

We are grateful to L. De Leo and to J.E. Han for sharing with us their results prior to publication, and to P. Nozières, E. Cappelluti, G.E. Santoro and M. Lueders for illuminating discussions. This work has been supported by MIUR Cofin 2003, MIUR FIRB RBAU017S8R004, FIRB RBAU01LX5H, and by INFM Progetto Calcolo Parallelo.


text:
# The narrow width of the Θ⁺ - a possible explanation

## Acknowledgements

The research of one of us (M.K.) was supported in part by a grant from the United States-Israel Binational Science Foundation (BSF), Jerusalem and by the Einstein Center for Theoretical Physics at the Weizmann Institute. The research of one of us (H.J.L.) was supported in part by the U.S. Department of Energy, Division of High Energy Physics, Contract W-31-109-ENG-38. We benefited from discussions with A. Auerbach, D. Faiman and G. Karl who called our attention to refs .


text:
# Post-Inflationary Curvature Perturbations

## I Introduction

Standard one-field models of inflation standard1 ; standard2  have the obvious virtue of simplicity, and should be preferred to multi-field models, but only so long as no important effects are missed. It has been argued that such effects might indeed exist lyth ; finelli ; bern ; DGZ1 ; DGZ2 ; Z ; kofman .

An example relevant for this work is the “inhomogeneous reheating” scenario DGZ2 . According to the inhomogeneous reheating model, curvature perturbations are generated by conversion of inflationary entropy fluctuations in the following way. In addition to the inflaton field $`\varphi `$ , there exists another light scalar field $`\chi `$ which has a very small potential energy. This field will fluctuate during inflation. After inflation, $`\chi `$ modulates the reheating rate, thus generating postinflationary curvature perturbations, which can be larger than the curvature perturbations generated during inflation.

This mechanism has obvious generalizations DGZ2 . Postinflationary curvature fluctuations can be generated by inhomogeneous reheating, or freeze-out, or mass domination, etc. The most important question is how these postinflationary curvature perturbations compare to the standard inflationary curvature perturbations.

We show that (i) Effects analogous to inhomogeneous reheating are present in generic multi-field inflation. (ii) “Generically” the postinflationary curvature perturbations are smaller than inflationary. (iii) Yet simple multi-field models with dominant postinflationary perturbations do exist. (iv) The characteristic feature of the postinflationary curvature perturbations is non-Gaussianity $`\pm 1`$.

We describe the basic mechanism for generating curvature perturbation after inflation and estimate the size of the effect in §2. We describe simple models with dominant postinflationary curvature perturbations in §3, where we also estimate the non-Gaussianity of postinflationary curvature perturbations.

## II The mechanism for generating postinflationary curvature perturbations and the estimate of the amplitude.

After the end of inflation the inflaton fields $`\varphi _a`$ will oscillate. Consider the potential energy in the region of oscillations. There can be directions in the $`\varphi _a`$ space along which the potential is nearly quadratic. Oscillations along quadratic directions are equivalent to matter, with the equation of state $`p=0`$. There can be other directions in the $`\varphi _a`$ space along which the potential is nearly quartic. Oscillations in the quartic potential are equivalent to radiation, with the equation of state $`p=\rho /3`$. If different parts of the universe enter the oscillation region along different directions, the difference in equations of state will be translated into curvature perturbations. In a similar way, different oscillatory trajectories can give rise to different reheating rates.

A rough estimate of the resulting superhorizon curvature perturbation $`\zeta _{\mathrm{post}}`$ should be

$$\zeta _{\mathrm{post}}\delta \theta ,$$
(1)
where $`\theta `$ are angles in the $`\varphi `$ space. A rigorous definition of $`\zeta `$ is this: on superhorizon scales, $`e^\zeta `$ is proportional to the local scale factor on uniform energy density hypersurfaces.

Now we need to estimate the superhorizon fluctuations in the directions $`\delta \theta `$ along which the fields enter the oscillation region. The field fluctuations during inflation are $`\delta \varphi H`$, where $`H`$ is the Hubble parameter during inflation. Then the fluctuations in the angle are

$$\delta \theta \frac{H}{\varphi }.$$
(2)
From (1) and (2) we get an estimate for the postinflationary curvature perturbation,

$$\zeta _{\mathrm{post}}\frac{H}{\varphi }.$$
(3)
This should be compared to the standard inflationary curvature perturbation

$$\zeta _{\mathrm{infl}}\frac{H}{ϵ^{1/2}M_{Pl}},$$
(4)
where $`2ϵ(M_{Pl}V^{}/V)^2`$ is the slow-roll parameter. The ratio of postinflationary to inflationary perturbations is then

$$\frac{\zeta _{\mathrm{post}}}{\zeta _{\mathrm{infl}}}\frac{ϵ^{1/2}M_{Pl}}{\varphi }\frac{1}{N},$$
(5)
where $`N1`$ is the number of e-foldings until the end of inflation.

Thus the postinflationary curvature perturbations are “generically” subdominant. It is clear that one can cook up a potential energy which will give rise to a very strong conversion of entropy into curvature perturbations after the end of inflation. Or one can have a potential energy which gives rise to very large entropy perturbations, leading to postinflationary curvature perturbations greater than the standard ones. But, as the next section shows, this can actually occur in very simple two-field models.

There also exists a radical way to ensure that the postinflationary curvature perturbations dominate. One can suppress the perturbations produced during the inflationary stage, by assuming that inflation occurs in a false vacuum state dvali . This assumption also allows for a large level of gravitational waves in postinflationary perturbation models riotto .

## III Large postinflationary curvature perturbations

If all fields give similar contributions to the potential energy, the postinflationary curvature perturbations are subdominant, as we have seen. However, when this condition is violated, and different fields contribute very differently to the potential energy, the postinflationary curvature perturbations can dominate.

We will give several examples of models with large post-inflationary curvature perturbations. For simplicity, we will assume that the parameters of the models are such that the postinflationary perturbations are the much larger than inflationary. We will therefore neglect the curvature perturbations generated during inflation. We want to demonstrate two things: (i) large post-inflationary curvature perturbations are not exotica, some simple models give large post-inflationary perturbations, (ii) the characteristic feature of the postinflationary perturbations is non-Gaussianity $`\pm 1`$.

The non-Gaussianity $`\pm 1`$ is much larger than the standard one-field inflationary non-Gaussianity ($``$ tilt, maldacena ), and it might be observable in future galaxy surveys sco ; note .

### III.1 Inhomogeneous reheating I

In inhomogeneous reheating DGZ2  the two fields play a very different role simply by assumption. It is postulated that there is an iflaton $`\varphi `$ field and another light field $`\chi `$. The field $`\chi `$ has no significant energy density, yet it can modulate the rate of reheating.

Assume that (i) reheating occurs during the time when $`\varphi `$ oscillations behave like matter, (ii) reheating rate $`\mathrm{\Gamma }`$ is proportional to $`\chi ^2`$, because $`\chi `$ is the coupling strength of the inflaton to radiation.

Before reheating, the energy density $`\rho a^3`$, where $`a`$ is the scale factor. The energy density at reheating is

$$\rho H^2\mathrm{\Gamma }^2\chi ^4,$$
(6)
and the scale factor at reheating is

$$a_r\chi ^{4/3},$$
(7)
After reheating the energy density is $`a_ra^4\chi ^{4/3}a^4`$, and the perturbations of the scale factor on uniform energy hypersurfaces are

$$e^\zeta \chi ^{1/3},$$
(8)
or

$$\zeta =\frac{1}{3}\mathrm{ln}\chi const=\frac{1}{3}\left(\delta _\chi \frac{1}{2}\delta _\chi ^2\right),$$
(9)
where $`\delta _\chi \chi /<\chi >1`$ is the approximately Gaussian inflationary fluctuation. The definition of primordial non-Gaussianity $`f_{nl}`$ used by komsper ; maldacena  is

$$\zeta =g(3/5)f_{nl}g^2,$$
(10)
where $`g`$ is Gaussian. We therefore get

$$f_{nl}=\frac{5}{2}$$
(11)
for this version of inhomogeneous reheating.

### III.2 Inhomogeneous reheating II

The version of inhomogeneous reheating presented above requires a non-renormalizable coupling, $`\varphi \chi \overline{\psi }\psi `$, where $`\varphi `$ is the inflaton, $`\chi `$ is the light scalar field modulating the rate of reheating, and $`\psi `$ is the fermion field. The resulting reheating rate is then $`\mathrm{\Gamma }\chi ^2`$.

One can get the same rate of reheating in a different way. Let there be two inflaton fields $`\varphi _1`$ and $`\varphi _2`$ with different masses. Assume that the scalar field $`\chi `$ modulates the rate of $`\varphi _1\varphi _2`$ conversion via a renormalizable coupling $`\chi \varphi _1\varphi _2`$. Further assume that $`\varphi _2`$ reheats much faster than $`\varphi _1`$. For small $`\chi `$, the effective reheating rate will be determined by the admixture of the $`\varphi _2`$ “flavor” in the $`\varphi _1`$ mode. The latter scales as $`\varphi _2\chi \varphi _1`$. The resulting reheating rate is again $`\mathrm{\Gamma }\chi ^2`$, and the results of the previous section apply.

### III.3 “Curvaton”

Consider a two-field model with potential energy

$$V(\varphi ,\chi )=\lambda \varphi ^4+m^2\chi ^2.$$
(12)
Since now the two fields give very different contributions to the potential energy, the postinflationary perturbations can be significant. Indeed, for some values of parameters, the model reduces to the curvaton lyth . We get a curvaton if the initial conditions are such that (i) $`\varphi `$ is the inflaton field, it carries the energy during inflation, (ii) $`\chi `$ is light during inflation, so that it fluctuates.

After the end of inflation, the energy stored in $`\varphi `$ oscillations will redshift away, and only the energy in $`\chi `$ oscillations will remain. This will translate the $`\chi `$ perturbations into the curvature perturbations. The energy density of the $`\chi `$ field will be $`\chi ^2a^3`$, where $`\chi `$ is the value at horizon crossing. This gives the curvature perturbation

$$e^{3\zeta }\chi ^2.$$
(13)
The corresponding non-Gaussianity is

$$f_{nl}=5/4.$$
(14)
### III.4 Inhomogeneous reheating III

Consider inhomogeneous reheating of the iflaton $`\varphi `$. The field $`\chi `$ which modulates the rate of reheating is now assumed to have a small mass. After reheating the field $`\chi `$ will redshift slower than radiation, and therefore it will generate the curvaton-like perturbations, which will add (coherently) to the perturbations due to inhomogeneous reheating. As a result, we can calculate the perturbations by multiplying equations (8, 13)

$$e^{3\zeta }\chi ^2\chi ^1=\chi $$
(15)
and the corresponding non-Gaussianity is

$$f_{nl}=5/2.$$
(16)
The detailed calculation can be done as follows. After the end of inflation, the inflaton oscillations redshift like matter. The Hubble parameter $`H`$ will be given by

$$H^2a^3,$$
(17)
where $`a`$ is the scale factor. Reheating occurs when $`H\mathrm{\Gamma }\chi ^2`$. Thus the scale factor at reheating

$$a_r\chi ^{4/3},$$
(18)
here and in what follows $`\chi `$ denotes the value of the $`\chi `$ field at the moment of horizon crossing. The Hubble parameter at reheating

$$H_r^2a_r^3.$$
(19)
After reheating,

$$H^2H_r^2a_r^4a^4a_ra^4$$
(20)
The $`\chi `$ field will start to oscillate when $`H^2m_\chi ^2`$. This occurs at the scale factor

$$a_\chi a_r^{1/4}.$$
(21)
After that, the energy density of the $`\chi `$ field will scale as

$$\rho _\chi \chi ^2a_\chi ^3a^3.$$
(22)
Since the $`\chi `$ energy will ultimately dominate, the fluctuations of the scale factor on uniform energy hypersurfaces are given by

$$e^{3\zeta }\chi ^2a_\chi ^3\chi ^2a_r^{3/4}\chi ,$$
(23)
as expected.

### III.5 Non-Gaussianity

One can keep on going and invent other models with large postinflationary curvature perturbations. It appears that in all such models, after the conversion of entropy into curvature perturbations, and after the final reheating of the massive fields, the radiation energy density becomes proportional to a certain power of some light scalar field $`\chi `$. Thus, quantum fluctuations of $`\chi `$ which occur during the inflationary stage are translated, after the end of inflation, into curvature perturbations

$$\zeta \mathrm{ln}(1+\delta _\chi ).$$
(24)
If these postinflationary perturbations dominate, the non-Gaussianity is

$$f_{nl}\pm 1.$$
(25)
The previous sections give examples with $`f_{nl}=2.5,1.25,2.5`$.

## IV Conclusion

* Effects analogous to inhomogeneous reheating are present in generic multi-field inflation.
* Generically the postinflationary curvature perturbations are smaller than inflationary.
* Yet simple multi-field models with dominant postinflationary perturbations do exist.
* The characteristic feature of the postinflationary curvature perturbations is the relatively large non-Gaussianity $`\pm 1`$.

###### Acknowledgements.

I thank Gia Dvali and Gregory Gabadadze for useful discussions. This work was supported by the David and Lucile Packard Foundation.