text:
# A family of bijections between 𝐺-parking functions and spanning trees

## 1. Introduction

The classical parking functions are defined in the following way. There are $`n`$ drivers, labeled $`1,\mathrm{},n`$, and $`n`$ parking spots, $`0,\mathrm{},n1`$, arranged linearly in this order. Each driver $`i`$ has a favorite parking spot $`b_i`$. Drivers enter the parking area in the order in which they are labeled. Each driver proceeds to his favorite spot and parks there if it is free, or parks at the next available spot otherwise. The sequence $`(b_1,\mathrm{},b_n)`$ is called a parking function if every driver parks successfully by this rule. The most notable result about parking functions is a bijective correspondence between such functions and trees on $`n+1`$ labeled vertices. The number of such trees is $`(n+1)^{n1}`$ by Cayley’s theorem. For more on parking functions, see for example .

Postnikov and Shapiro  suggested the following generalization of parking functions. Let $`G`$ be a directed graph on $`n+1`$ vertices indexed by integers from $`0`$ to $`n`$. A *$`G`$-parking function* is a sequence $`(b_1,\mathrm{},b_n)`$ of non-negative integers that satisfies the following condition: for each subset $`U\{1,2,\mathrm{},n\}`$ of vertices of $`G`$, there exists a vertex $`jU`$ such that the number of edges from $`j`$ to vertices outside of $`U`$ is greater than $`b_j`$. For the complete graph $`G=K_{n+1}`$, these are the classical parking functions (we view $`K_{n+1}`$ as the digraph with exactly one edge $`(i,j)`$ for all $`ij`$).

A spanning tree of $`G`$ rooted at $`m`$ is a subgraph of $`G`$ such that, for each $`i\{0,1,\mathrm{},n\}`$, there is a unique path from $`i`$ to $`m`$ along the edges of the spanning tree. Note that these are the spanning trees of the graph in the usual sense with each edge oriented towards $`m`$. The number of such trees is given by the Matrix-Tree Theorem; see . In  it is shown that the number of spanning trees of $`G`$ rooted at $`0`$ is equal to the number of $`G`$-parking functions for any digraph $`G`$.

An equivalent fact was originally discovered by Dhar , who studied the sandpile model. The so called recurrent states of the sandpile model are in one-to-one correspondence with $`G`$-parking functions for certain graphs $`G`$, including all symmetric graphs. A bijection between recurrent states and spanning trees for symmetric graphs $`G`$ is mentioned in , and a class of bijections is constructed in . The sandpile model was also studied by Gabrielov in . This paper also contains an extensive list of references on the topic.

In this paper we present a family of bijections between $`G`$-parking functions and rooted spanning trees of $`G`$. Given a spanning tree $`T`$ of $`G`$, we establish a total order on the vertices of $`T`$ satisfying two conditions, and each such order gives rise to a bijection in the family. In  Francon used a similar concept, which he called selection procedures, to construct a family of bijections between parking functions and rooted trees in the classical case $`G=K_{n+1}`$. Thus our result provides a generalization of Francon’s construction.

## 2. A family of bijections

Let $`G`$ be a directed graph on vertices $`\{0,\mathrm{},n\}`$. We allow $`G`$ to have multiple edges but not loops. To distinguish between multiple edges of $`G`$, we fix an order on the set of edges going from $`i`$ to $`j`$ for all $`ij`$.

A *subtree* of $`G`$ rooted at $`m`$ is a subgraph $`T`$ of $`G`$ containing $`m`$ such that for every vertex $`i`$ of $`T`$, there is a unique path in $`T`$ from $`i`$ to $`m`$. A subtree is called a *spanning tree* if it contains all vertices of $`G`$.

Let $`𝕋_G`$ be the set of subtrees of $`G`$ rooted at $`0`$, and let $`𝒯_G`$ be the set of spanning trees of $`G`$ rooted at $`0`$. Unless stated otherwise, all spanning trees in this paper are assumed to be rooted at $`0`$. Let $`𝒫_G`$ be the set of $`G`$-parking functions. In this section we give a bijection between $`𝒯_G`$ and $`𝒫_G`$.

For every $`T𝕋_G`$, let $`\pi (T)`$ be a total order on the vertices of $`T`$, and write $`i<_{\pi (T)}j`$ to denote that $`i`$ is smaller than $`j`$ in this order. We call the set $`\mathrm{\Pi }(G)=\{\pi (T)|T𝕋_G\}`$ a *proper set of tree orders* if the following conditions hold for all $`T𝕋_G`$:

1. if $`(j,i)`$ is an edge of $`T`$, then $`i<_{\pi (T)}j`$;
2. if $`t`$ is a subtree of $`T`$ rooted at $`0`$, then the order $`\pi (t)`$ is consistent with $`\pi (T)`$; in other words, $`i<_{\pi (t)}j`$ if and only if $`i<_{\pi (T)}j`$ for $`i,jt`$.

We give several examples of proper sets of tree orders in Section 3.

For $`T𝕋_G`$ and a vertex $`j`$ of $`G`$, the order $`\pi (T)`$ induces the order on the edges going from $`j`$ to vertices of $`T`$ in which $`(j,i)`$ is smaller than $`(j,i^{})`$ whenever $`i<_{\pi (T)}i^{}`$ and which is consistent with the previously fixed order on multiple edges. We write $`e<_{\pi (T)}e^{}`$ to denote that $`e`$ is smaller than $`e^{}`$ in this order.

Given a proper set of tree orders $`\mathrm{\Pi }(G)`$, define the map $`\mathrm{\Theta }_{\mathrm{\Pi },G}:𝒯_G𝒫_G`$ as follows. For $`T𝒯_G`$ and a vertex $`j\{1,\mathrm{},n\}`$, let $`e_j`$ be the edge of $`T`$ going out of $`j`$. Set $`\mathrm{\Theta }_{\mathrm{\Pi },G}(T)=(b_1,\mathrm{},b_n)`$, where $`b_j`$ is the number of edges $`e`$ going out of $`j`$ such that $`e<_{\pi (T)}e_j`$. For the rest of the section, we write $`\mathrm{\Theta }`$ instead of $`\mathrm{\Theta }_{\mathrm{\Pi },G}`$.

###### Theorem 2.1.

The map $`\mathrm{\Theta }`$ is a bijection between $`𝒯_G`$ and $`𝒫_G`$.

###### Proof.

We begin by checking that $`\mathrm{\Theta }(T)`$ is a $`G`$-parking function.

###### Lemma 2.2.

$`\mathrm{\Theta }(T)𝒫_G`$ for $`T𝒯_G`$.

###### Proof.

For a subset $`U\{1,\mathrm{},n\}`$, let $`j`$ be the smallest vertex of $`U`$ in the order $`\pi (T)`$. Let $`e_j=(j,i)`$ be the edge of $`T`$ coming out of $`j`$. Then $`i<_{\pi (T)}j`$, so $`iU`$ by choice of $`j`$. For each of the $`b_j`$ edges $`e=(j,i^{})`$ such that $`e<_{\pi (T)}e_j`$, we have $`i^{}_{\pi (T)}i<_{\pi (T)}j`$, so $`i^{}U`$. Thus there are at least $`b_j+1`$ edges going from $`j`$ to vertices outside of $`U`$. ∎

Next, we define the inverse map $`\mathrm{\Phi }_{\mathrm{\Pi },G}:𝒫_G𝒯_G`$. Given $`P=(b_1,\mathrm{},b_n)𝒫_G`$, we construct the corresponding tree $`\mathrm{\Phi }_{\mathrm{\Pi },G}(P)`$ one edge at a time. Initially, let $`t_0`$ be the subtree of $`G`$ consisting of the vertex $`0`$ alone, and put $`p_0=0`$. For $`1mn`$, we choose the vertex $`p_m`$ and construct the subtree $`t_m`$ rooted at $`0`$ inductively as follows. Let $`U_m`$ be the set of vertices not in $`t_{m1}`$, and let $`V_m`$ be the set of vertices $`jU_m`$ such that the number of edges from $`j`$ to $`t_{m1}`$ is at least $`b_j+1`$. Note that $`|V_m|1`$ by definition of a $`G`$-parking function. For each $`jV_m`$, let $`e_j`$ be the edge from $`j`$ to $`t_{m1}`$ such that exactly $`b_j`$ edges $`e`$ from $`j`$ to $`t_{m1}`$ satisfy $`e<_{\pi (t_{m1})}e_j`$. Let $`t`$ be the tree obtained by adjoining each vertex $`jV_m`$ to $`t_{m1}`$ by means of the edge $`e_j`$. Set $`p_m`$ to be the smallest vertex of $`V_m`$ in the order $`\pi (t)`$, and set $`t_m`$ to be the tree obtained by adjoining $`p_m`$ to $`t_{m1}`$ by means of the edge $`e_{p_m}`$. Obviously, $`t_m`$ is a subtree of $`G`$. In the end, set $`\mathrm{\Phi }_{\mathrm{\Pi },G}(P)=T=t_n`$. For the rest of the section, we write $`\mathrm{\Phi }`$ instead of $`\mathrm{\Phi }_{\mathrm{\Pi },G}`$.

An example of constructing $`\mathrm{\Phi }(P)`$ is shown in Figure 1. Let $`G`$ be the graph shown in the figure, and let $`P=(0,1,0,1)`$. Let $`\mathrm{\Pi }`$ be the tree order in which vertex $`i`$ is smaller than vertex $`j`$ if $`i`$ is closer to the root than $`j`$, or else if $`i`$ and $`j`$ are equidistant to the root, and $`i<j`$. Initially, $`U_1=\{1,2,3,4\}`$ and $`V_1=\{1\}`$, so vertex $`1`$ is attached to the root to produce the subtree $`t_1`$. Then we have $`V_2=\{3,4\}`$ with $`e_3=(3,1)`$ and $`e_4=(4,1)`$. Adjoining vertices $`3`$ and $`4`$ to $`t_1`$ by means of $`e_3`$ and $`e_4`$ places vertices $`3`$ and $`4`$ the same distance away from the root, making $`p_2=3`$, so vertex $`3`$ is attached by means of the edge $`e_3=(3,1)`$ to produce $`t_2`$. At the next step, we have $`V_3=\{2,4\}`$ with $`e_2=(2,3)`$ and $`e_4=(4,1)`$. Adjoining vertices $`2`$ and $`4`$ to $`t_2`$ by means of $`e_2`$ and $`e_4`$ makes vertex $`4`$ closer to the root than vertex $`2`$, so we select vertex $`4`$ and attach it to vertex $`1`$ to form $`t_3`$. Finally, we attach vertex $`2`$ to vertex $`3`$ to form $`t_4=\mathrm{\Phi }(P)`$.

###### Lemma 2.3.

In the above construction, $`p_0<_{\pi (T)}\mathrm{}<_{\pi (T)}p_n`$.

###### Proof.

Since $`\mathrm{\Pi }(G)`$ is a proper set of tree orders, it follows that the root $`0`$ is the smallest vertex of $`T`$ in the order $`\pi (T)`$. Hence $`p_0<_{\pi (T)}p_1`$. Suppose that $`p_0<_{\pi (T)}\mathrm{}<_{\pi (T)}p_m`$ for some $`1mn1`$. We show that $`p_m<_{\pi (T)}p_{m+1}`$. We consider the following two cases.

Case 1: $`p_{m+1}V_m`$. Then the number of edges from $`p_{m+1}`$ to $`t_{m1}`$ is at most $`b_{p_{m+1}}`$. Since $`p_{m+1}V_{m+1}`$, the number of edges from $`p_{m+1}`$ to $`t_m`$ is at least $`b_{p_{m+1}}+1`$. It follows that there is at least one edge $`(p_{m+1},p_m)`$ in $`G`$ and that $`p_{m+1}`$ is adjoined to $`t_m`$ by means of such an edge. Thus $`p_m<_{\pi (T)}p_{m+1}`$ because $`\mathrm{\Pi }(G)`$ is a proper set of tree orders.

Case 2: $`p_{m+1}V_m`$. Let $`e_{p_{m+1}}`$ be the edge from $`p_{m+1}`$ to $`t_{m1}`$ such that exactly $`b_{p_{m+1}}`$ edges $`e`$ from $`p_{m+1}`$ to $`t_{m1}`$ satisfy $`e<_{\pi (t_{m1})}e_{p_{m+1}}`$. Since $`p_m`$ is the largest vertex of $`t_m`$ in the order $`\pi (T)`$ and hence in the order $`\pi (t_m)`$, and $`e_{p_{m+1}}`$ goes from $`p_{m+1}`$ to $`t_{m1}=t_mp_m`$, it follows that $`e<_{\pi (t_{m1})}e_{p_{m+1}}`$ if and only if $`e<_{\pi (t_m)}e_{p_{m+1}}`$ because the order $`\pi (t_{m1})`$ is consistent with $`\pi (t_m)`$. Therefore, exactly $`b_j`$ edges $`e`$ from $`p_{m+1}`$ to $`t_m`$ satisfy $`e<_{\pi (t_m)}e_{p_{m+1}}`$, hence $`p_{m+1}`$ is adjoined to $`t_m`$ by means of the edge $`e_{p_{m+1}}`$.

Let $`e_{p_m}`$ be the edge of $`T`$ coming out of $`p_m`$, and let $`t`$ be the tree in the construction of $`T`$ obtained by adjoining the vertices of $`V_m`$ to $`t_{m1}`$. Let $`t^{}`$ be the tree obtained from $`t_{m1}`$ by adjoining the vertices $`p_m`$ and $`p_{m+1}`$ by means of the edges $`e_{p_m}`$ and $`e_{p_{m+1}}`$. Then $`t^{}`$ is a subtree of both $`t`$ and $`T`$. By choice of $`p_m`$, we have $`p_m<_{\pi (t)}p_{m+1}`$, so $`p_m<_{\pi (t^{})}p_{m+1}`$ and $`p_m<_{\pi (T)}p_{m+1}`$ because the order $`\pi (t^{})`$ is consistent with both $`\pi (t)`$ and $`\pi (T)`$. ∎

We now check that $`\mathrm{\Theta }`$ and $`\mathrm{\Phi }`$ are inverses of each other.

###### Lemma 2.4.

$`\mathrm{\Theta }(\mathrm{\Phi }(P))=P`$ for $`P𝒫_G`$.

###### Proof.

Put $`P=(b_1,\mathrm{},b_n)`$ and $`T=\mathrm{\Phi }(P)`$. Consider the process of constructing $`T`$. For $`j\{1,\mathrm{},n\}`$, we have $`j=p_m`$ for some $`1mn`$. Let $`e_j`$ be the edge of $`T`$ coming out of $`j`$. The edge $`e_j`$ goes from $`j`$ to $`t_{m1}`$. Since the set of vertices of $`t_{m1}`$ is $`\{p_0,\mathrm{},p_{m1}\}`$, it follows from Lemma 2.3 that if an edge $`e`$ coming out of $`j`$ satisfies $`e<_{\pi (T)}e_j`$, then $`e`$ goes from $`j`$ to $`t_{m1}`$. Thus, $`e<_{\pi (T)}e_j`$ if and only if $`e<_{\pi (t_{m1})}e_j`$ because the order $`\pi (t_{m1})`$ is consistent with $`\pi (T)`$. By construction of $`T`$, the number of edges $`e`$ satisfying $`e<_{\pi (t_{m1})}e_j`$ is $`b_j`$, hence the number of edges $`e`$ satisfying $`e<_{\pi (T)}e_j`$ is also $`b_j`$. We conclude that $`\mathrm{\Theta }(T)=P`$. ∎

###### Lemma 2.5.

$`\mathrm{\Phi }(\mathrm{\Theta }(T^{}))=T^{}`$ for $`T^{}𝒯_G`$.

###### Proof.

Put $`P=\mathrm{\Theta }(T^{})=(b_1,\mathrm{},b_n)`$. Consider the process of constructing $`T=\mathrm{\Phi }(P)`$. We show by induction that for $`0mn`$, the tree $`t_m`$ is a subtree of $`T^{}`$ and that $`p_0,\mathrm{},p_m`$ are the smallest $`m+1`$ vertices in the order $`\pi (T^{})`$. Since the root $`0`$ is the smallest vertex in $`\pi (T^{})`$, the assertion is true for $`m=0`$.

Now, suppose that $`t_{m1}`$ is a subtree of $`T^{}`$ and that $`p_0,\mathrm{},p_{m1}`$ are the smallest $`m`$ vertices in the order $`\pi (T^{})`$. Let $`k`$ be the $`(m+1)`$-th smallest vertex in the order $`\pi (T^{})`$, and let $`e_k^{}=(k,i)`$ be the edge coming out of $`k`$ in $`T^{}`$. Then $`i<_{\pi (T^{})}k`$, so $`i\{p_0,\mathrm{},p_{m1}\}`$ and $`it_{m1}`$. Hence if an edge $`e`$ coming out of $`k`$ satisfies $`e<_{\pi (T^{})}e_k^{}`$, then $`e`$ goes from $`k`$ to $`t_{m1}`$. There are $`b_k`$ edges $`e`$ satisfying $`e<_{\pi (T^{})}e_k^{}`$. These $`b_k`$ edges together with the edge $`e_k^{}`$ give $`b_k+1`$ edges going from $`k`$ to $`t_{m1}`$. It follows that $`kV_m`$.

As before, for every $`jV_m`$, let $`e_j`$ be the edge from $`j`$ to $`t_{m1}`$ such that exactly $`b_j`$ edges $`e`$ from $`j`$ to $`t_{m1}`$ satisfy $`e<_{\pi (t_{m1})}e_j`$. Since the vertices of $`t_{m1}`$ are the smallest $`m`$ vertices in the order $`\pi (T^{})`$, it follows that if an edge $`e`$ coming out of $`j`$ satisfies $`e<_{\pi (T^{})}e_j`$, then $`e`$ goes from $`j`$ to $`t_{m1}`$. Thus, $`e<_{\pi (T^{})}e_j`$ if and only if $`e<_{\pi (t_{m1})}e_j`$ because the order $`\pi (t_{m1})`$ is consistent with $`\pi (T^{})`$. There are $`b_j`$ edges $`e`$ satisfying $`e<_{\pi (t_{m1})}e_j`$, hence there are $`b_j`$ edges $`e`$ satisfying $`e<_{\pi (T^{})}e_j`$. It follows from the choice of $`b_j`$ that $`e_j`$ is an edge of $`T^{}`$. Therefore, the tree $`t`$ obtained by adjoining the vertices $`jV_m`$ by means of the edges $`e_j`$ is a subtree of $`T^{}`$. Consequently, the smallest vertex $`p_m`$ of $`V_m`$ in the order $`\pi (t)`$ is the smallest vertex of $`V_m`$ in the order $`\pi (T^{})`$. Since $`k`$ is the smallest vertex of $`U_m`$ in the order $`\pi (T^{})`$ and $`kV_mU_m`$, it follows that $`p_m=k`$. The induction step is complete.

Finally, we obtain $`T^{}=t_n=T`$. ∎

Theorem 2.1 follows from Lemmas 2.4 and 2.5. ∎

## 3. Examples

In this section we give examples of proper sets of tree orders and the resulting bijections between $`𝒯_G`$ and $`𝒫_G`$ from the family of bijections defined in Section 2.

We begin by introducing the *breadth-first search order* $`\pi _{bf}(T)`$ on the vertices of a tree $`T𝕋_G`$. For a vertex $`iT`$, we define the *height* $`h_T(i)`$ of $`i`$ in $`T`$ to be the number of edges in the unique path from $`i`$ to the root $`0`$. We set $`i<_{\pi _{bf}(T)}j`$, or $`i<_{bf}j`$, if $`h_T(i)<h_T(j)`$ or else if $`h_T(i)=h_T(j)`$ and $`i<j`$. It is easy to check that $`\pi _{bf}(T)`$ is a total order on the vertices of $`T`$ and that $`\mathrm{\Pi }_{bf}(G)=\{\pi _{bf}(T)|T𝕋_G\}`$ is a proper set of tree orders.

The *depth-first search order* $`\pi _{df}(T)`$ on the vertices of a tree $`T𝕋_G`$ is defined as follows. For a vertex $`iT`$, let $`T(i)`$ denote the branch of $`T`$ rooted at $`i`$. In other words, $`T(i)`$ consists of all vertices $`k`$ of $`T`$ such that the unique path from $`k`$ to $`0`$ in $`T`$ contains $`i`$. If $`(i,\mathrm{})`$ is an edge of $`T`$, then we set $`\mathrm{}<_{\pi _{df}(T)}i`$. Furthermore, if $`(j,\mathrm{})`$ is an edge of $`T`$ such that $`i<j`$, then we set $`i^{}<_{\pi _{df}(T)}j^{}`$ for $`i^{}T(i)`$ and $`j^{}T(j)`$. We use the symbol $`<_{df}`$ with the same meaning as $`<_{\pi _{df}(T)}`$. It is not hard to see that $`\mathrm{\Pi }_{df}(G)=\{\pi _{df}(T)|T𝕋_G\}`$ is a proper set of tree orders.

Our third example is the *vertex-adding order* $`\pi _{va}(T)`$ on the vertices of $`T𝕋_G`$. Construct the sequence $`p_0,\mathrm{},p_{|T|1}`$ inductively as follows. Set $`p_0=0`$, and, for $`1m|T|1`$, let $`p_m`$ be the smallest vertex $`j`$ in $`G\{p_0,\mathrm{},p_{m1}\}`$ such that there is an edge in $`G`$ from $`j`$ to $`\{p_0,\mathrm{},p_{m1}\}`$. Note that the sequence $`p_0,\mathrm{},p_{|T|1}`$ contains each vertex of $`T`$ exactly once. Put $`p_0<_{\pi _{va}(T)}\mathrm{}<_{\pi _{va}(T)}p_{|T|1}`$, and let the symbol $`<_{va}`$ have the same meaning as $`<_{\pi _{va}(T)}`$. Clearly, $`<_{va}`$ is a total order on the vertices of $`T`$. Also, $`\mathrm{\Pi }_{va}(G)=\{\pi _{va}(T)|T𝕋_G\}`$ is a proper set of tree orders. Indeed, if $`t`$ is a subtree of $`T`$, then adding or not adding a vertex of $`Tt`$ to $`\{p_0,\mathrm{},p_{m1}\}`$ does not affect the order in which the vertices of $`t`$ are added.

Let $`\mathrm{\Theta }_{bf,G}`$, $`\mathrm{\Theta }_{df,G}`$, and $`\mathrm{\Theta }_{va,G}`$ be the maps $`\mathrm{\Theta }_{\mathrm{\Pi }_{bf},G}`$, $`\mathrm{\Theta }_{\mathrm{\Pi }_{df},G}`$, and $`\mathrm{\Theta }_{\mathrm{\Pi }_{va},G}`$ constructed in Section 2. Figure 2 shows a sample graph $`G`$ and a spanning tree $`T𝒯_G`$. To compute $`\mathrm{\Theta }_{bf,G}(T)`$, $`\mathrm{\Theta }_{df,G}(T)`$, and $`\mathrm{\Theta }_{va,G}(T)`$, we first determine the orders $`\pi _{bf}(T)`$, $`\pi _{df}(T)`$, and $`\pi _{va}(T)`$. We have $`h_T(0)=0`$, $`h_T(2)=h_T(6)=1`$, $`h_T(3)=h_T(4)=2`$, and $`h_T(1)=h_T(5)=3`$, so

$$0<_{bf}2<_{bf}6<_{bf}3<_{bf}4<_{bf}1<_{bf}5.$$

Next, we determine $`\pi _{df}(T)`$. Applying the depth-first search rule with $`\mathrm{}=0`$, we get $`0<_{df}\{1,2,3,4,5\}<_{df}6`$ because $`T(2)`$ contains vertices $`1`$, $`2`$, $`3`$, $`4`$, and $`5`$, and $`T(6)`$ contains a single vertex $`6`$. Taking $`\mathrm{}=2`$ we get $`0<_{df}2<_{df}\{3,5\}<_{df}\{1,4\}<_{df}6`$. Finally, taking $`\mathrm{}=3`$ and $`\mathrm{}=4`$ we get

$$0<_{df}2<_{df}3<_{df}5<_{df}4<_{df}1<_{df}6.$$

Also, the order $`\pi _{va}(T)`$ is the following:

$$0<_{va}2<_{va}3<_{va}4<_{va}1<_{va}5<_{va}6.$$

The edge coming out of vertex $`1`$ in $`T`$ is $`(1,4)`$. The relation $`e<_{bf}(1,4)`$ is satisfied for $`e=(1,0),(1,2),(1,3),(1,6)`$, so the first component of $`\mathrm{\Theta }_{bf,G}(T)`$ is $`4`$. Similarly, $`e<_{df}(1,4)`$ holds for $`e=(1,0),(1,2),(1,3),(1,5)`$, so the first component of $`\mathrm{\Theta }_{df,G}(T)`$ is $`4`$. The relation $`e<_{va}(1,4)`$ holds for $`e=(1,0),(1,2),(1,3)`$, so the first component of $`\mathrm{\Theta }_{va,G}(T)`$ is $`3`$. The other components are computed in the same way. Figure 2 shows the values of $`\mathrm{\Theta }_{bf,G}(T)`$, $`\mathrm{\Theta }_{df,G}(T)`$, and $`\mathrm{\Theta }_{va,G}(T)`$.

Note that for $`G=K_{n+1}`$, the presented construction yields a family of bijections between the classical parking functions and trees on $`n+1`$ labeled vertices. This family includes some of the well-known bijections. For example, using the vertex-adding tree order results in the following simple correspondence defined in terms of drivers and parking spots: given a parking function $`(b_1,\mathrm{},b_n)`$, the corresponding tree is obtained by introducing the edge $`(i,j)`$ whenever driver $`j`$ ended up parking in spot $`b_i1`$, and the edge $`(i,0)`$ whenever $`b_i=0`$.

Another bijection involving labeled Dyck paths as an intermediate object, communicated to us by A. Postnikov, results if the right-to-left depth first search tree order is used (this order is the same as the depth first search order described above except that larger numbers are given priority among the children of the same vertex). Given a parking function $`P`$, we write numbers $`1`$ through $`n`$ in the $`n\times n`$ square so that all numbers $`j`$ such that $`b_j=i`$ appear in the $`i`$-th row in increasing order, and the numbers in a lower row appear to the left of the numbers in a higher row. Such an arrangement defines a Dyck path from the lower-left corner to the upper-right corner of the square, with horizontal steps labeled with integers between $`1`$ and $`n`$; see Figure 3. To get the spanning tree $`T`$ corresponding to $`P`$, start from the upper-right corner of the square and proceed to the lower-left corner along the Dyck path, keeping track of the current vertex, initially set to be $`0`$. At each horizontal step labeled $`i`$, connect the vertex $`i`$ to the current vertex, and at each vertical step, replace the current vertex with its successor in the right-to-left depth first seach order on the tree constructed so far. It is not hard to show that the obtained tree $`T`$ is precisely $`\varphi (P)`$ for the right-to-left depth first search tree order.

The bijection obtained using the breadth first search tree order is discussed in Section 5 in connection with the sandpile model.

## 4. More proper sets of tree orders

We now present a method for constructing proper sets of tree orders. Let $`\sigma _1,\mathrm{},\sigma _{\mathrm{}}`$ denote the path consisting of the edges $`(\sigma _{\mathrm{}},\sigma _\mathrm{}1)`$, $`(\sigma _\mathrm{}1,\sigma _\mathrm{}2)`$, …, $`(\sigma _1,0)`$. Also, let $``$ denote the path consisting of the vertex $`0`$ alone. Define $`𝔸_G`$ to be the set of paths $`\sigma _1,\mathrm{},\sigma _{\mathrm{}}`$ in $`G`$ such that $`\sigma _1,\mathrm{},\sigma _{\mathrm{}}`$ are distinct vertices of $`G\{0\}`$, where $`\mathrm{}0`$. Let $``$ be a partial order on $`𝔸_G`$ satisfying the following conditions:

1. if $`AA^{}𝔸_G`$ for some $`A,A^{}𝔸_G`$, then $`A`$ and $`A^{}`$ are comparable;
2. $`\sigma _1,\mathrm{},\sigma _{\mathrm{}^{}}\sigma _1,\mathrm{},\sigma _{\mathrm{}^{}},\mathrm{},\sigma _{\mathrm{}}`$ for $`\mathrm{}^{}<\mathrm{}`$.

For a tree $`T𝕋_G`$ and a vertex $`iT`$, let $`A_T(i)𝔸_G`$ be the unique path in $`T`$ from $`i`$ to $`0`$. Introduce the order $`\pi _{}(T)`$ on the vertices of $`T`$ in which $`i<_{\pi _{}(T)}j`$ whenever $`A_T(i)A_T(j)`$. Put $`\mathrm{\Pi }_{}(G)=\{\pi _{}(T)|T𝕋_G\}`$.

###### Proposition 4.1.

$`\mathrm{\Pi }_{}(G)`$ is a proper set of tree orders.

###### Proof.

Let $`T𝕋_G`$, and let $`i`$ and $`j`$ be vertices of $`T\{0\}`$. Since $`A_T(i)`$ and $`A_T(j)`$ are the unique paths in $`T`$ from $`i`$ and $`j`$ to $`0`$, it follows that $`A_T(i)A_T(j)𝔸_G`$. Therefore, $`\pi _{}(T)`$ is a total order on the vertices of $`T`$, by property (i) of $``$.

If $`(j,i)`$ is an edge of $`T`$, then $`A_T(i)=\sigma _1,\mathrm{},\sigma _{\mathrm{}},i`$ and $`A_T(j)=\sigma _1,\mathrm{},\sigma _{\mathrm{}},i,j`$, so $`A_T(i)A_T(j)`$, by property (ii) of $``$, so $`i<_{\pi _{}(T)}j`$.

If $`t`$ is a subtree of $`T`$, then $`A_t(i)=A_T(i)`$ for all vertices $`it`$, so the order $`\pi _{}(t)`$ is consistent with the order $`\pi _{}(T)`$.

The proposition follows. ∎

The orders $`\pi _{bf}(T)`$, $`\pi _{df}(T)`$, and $`\pi _{va}(T)`$ described in Section 3 can be obtained as $`\pi _{}(T)`$ via an appropriate choice of $``$. Setting $``$ to be the lexicographic order on the paths $`\sigma _1,\mathrm{},\sigma _{\mathrm{}}`$ viewed as sequences of integers yields the order $`\pi _{df}(T)`$. To obtain $`\pi _{bf}(T)`$, set $`\sigma _1,\mathrm{},\sigma _{\mathrm{}}\sigma _1^{},\mathrm{},\sigma _{\mathrm{}^{}}^{}`$ if $`\mathrm{}<\mathrm{}^{}`$, or else if $`\mathrm{}=\mathrm{}^{}`$ and $`\sigma _{\mathrm{}}<\sigma _{\mathrm{}^{}}^{}`$. Finally, setting $``$ to be the order in which $`AA^{}`$ whenever $`AA^{}𝔸_G`$, and the largest vertex of $`A\backslash A^{}`$ is smaller than the largest vertex of $`A^{}\backslash A`$, yields the order $`\pi _{va}(T)`$.

We can obtain other proper sets of tree orders from partial orders $``$ on $`𝔸_G`$ satisfying the conditions above. For example, we can set $`A=\sigma _1,\mathrm{},\sigma _{\mathrm{}}A^{}=\sigma _1^{},\mathrm{},\sigma _{\mathrm{}^{}}^{}`$ whenever the increasing rearrangement of $`A`$ is smaller than that of $`A^{}`$ in the lexicographic order. Another example is setting $`AA^{}`$ if $`\sigma _k<\sigma _k^{}`$, or else if $`\sigma _k=\sigma _k^{}`$ and $`\sigma _{\mathrm{}}<\sigma _{\mathrm{}^{}}^{}`$.

Similar examples of partial orders on $`𝔸_G`$ yielding proper sets of tree orders can be obtained by using an arbitrary numbering of the edges of $`G`$ instead of vertex labels.

It is worth noting that not all proper sets of tree orders are induced by a partial order on $`𝔸_G`$ satisfying the above conditions. Consider the following simple example. Let $`G`$ be the graph shown in Figure 4. Let $`e_{1,2}`$ be the two edges of $`G`$ going from vertex $`3`$ to vertex $`1`$, and let $`f_{1,2}`$ be the two edges going from vertex $`4`$ to vertex $`2`$. For $`1i,j2`$, let $`T_{ij}`$ be the spanning tree of $`G`$ containing edges $`e_i`$ and $`f_j`$. Let $`\mathrm{\Pi }=\{\pi (T_{ij})|1i,j2\}`$ be the proper set of tree orders defined as follows:

$$0<_{\pi (T_{ij})}1<_{\pi (T_{ij})}2<_{\pi (T_{ij})}3<_{\pi (T_{ij})}4$$

for $`ij`$, and

$$0<_{\pi (T_{ii})}1<_{\pi (T_{ii})}2<_{\pi (T_{ii})}4<_{\pi (T_{ii})}3.$$

Let $`A_{e_i}`$ (resp. $`A_{f_i}`$) be the unique path in $`𝔸_G`$ from vertex $`3`$ (resp. $`4`$) to the root $`0`$ containing the edge $`e_i`$ (resp. $`f_i`$). Then in order for $`\mathrm{\Pi }`$ to be induced by some partial order $``$ on $`𝔸_G`$, we must have $`A_{e_1}A_{f_2}`$ so that relation $`3<_{\pi (T_{12})}4`$ holds. Similarly, to achieve relations $`4<_{\pi (T_{22})}3`$, $`3<_{\pi (T_{21})}4`$, and $`4<_{\pi (T_{11})}3`$, we must have $`A_{f_2}A_{e_2}`$, $`A_{e_2}A_{f_1}`$, and $`A_{f_1}A_{e_1}`$. We obtain a contradiction $`A_{e_1}A_{e_1}`$, hence $`\mathrm{\Pi }`$ is not induced by a partial order on $`𝔸_G`$.

## 5. $`G`$-parking functions and the sandpile model

In , Cori and Le Borgne construct a family of bijections between the rooted spanning trees of a digraph $`G`$ and the recurrent states of the sandpile model defined on $`G`$. It was shown by Gabrielov  that if for all vertices of $`G`$ except the root, the out-degree is greater than or equal to the in-degree, then recurrent states coincide with the so called *allowed configurations* of the model, which correspond to $`G`$-parking functions: if $`d_i`$ is the out-degree of vertex $`i`$, then $`(u_1,\mathrm{},u_n)`$ is an allowed configuration if and only if $`(d_1u_1,\mathrm{},d_nu_n)`$ is a $`G`$-parking function. In particular, this observation is valid for symmetric graphs, in which the number of edges from $`i`$ to $`j`$ is equal to the number of edges from $`j`$ to $`i`$ for all $`ij`$; such graphs can be naturally viewed as undirected graphs. Thus for these graphs the result of Cori and Le Borgne provides a bijective correspondence between rooted spanning trees of $`G`$ and $`G`$-parking functions. For the rest of the section, we assume that $`G`$ is a symmetric graph.

The construction described in  begins by fixing an arbitrary order on the edges of $`G`$. Given a spanning tree $`T`$ of $`G`$, an edge $`e`$ in $`GT`$ is called *externally active* with respect to $`T`$ if in the unique cycle of $`T+e`$, the edge $`e`$ is the smallest in the chosen order. A key property of the obtained bijection is that the sum of the values of a recurrent state is equal to the number of externally active edges with respect to the corresponding spanning tree. It follows that in the resulting bijection between $`G`$-parking functions and spanning trees, $`G`$-parking functions with the same sum of values are mapped to spanning trees with the same number of externally active edges.

To show that the bijections presented in this paper are substantially different from the ones in , consider the case $`G=K_{n+1}`$, and let $`P`$ be the path obtained as follows: start at the root vertex $`0`$, and then append the remaining vertices one by one, so that at each step the appended edge is the smallest, in the chosen edge order, among all edges that can possibly be appended. There are no externally active edges with respect to $`P`$ since every edge $`(i,j)`$ not in $`P`$, where $`j`$ is closer to the root in $`P`$ than $`i`$, is greater than the edge $`(i^{},j)`$, where $`i^{}`$ is the vertex appended after $`j`$ in the construction of $`P`$, by choice of $`i^{}`$. On the other hand, if a path $`P^{}`$ does not include the smallest edge in the chosen edge order, then this edge is externally active with respect to $`P^{}`$. Hence there is a different number of externally active edges with respect to $`P`$ and $`P^{}`$. However, every bijection $`\mathrm{\Theta }_{\mathrm{\Pi },G}`$ maps both $`P`$ and $`P^{}`$ to permutations of $`(0,\mathrm{},n1)`$, so the sum of values of the corresponding $`G`$-parking functions is the same. Hence for $`G=K_{n+1}`$, none of the bijections $`\mathrm{\Theta }_{\mathrm{\Pi },G}`$ coincides with a bijection from the family constructed in .

Dhar defined the burning algorithm for determining whether a given configuration is allowed; see . In our setting this task corresponds to the question whether a function $`P:\{1,\mathrm{},n\}`$ is a $`G`$-parking function, and an equivalent formulation of Dhar’s burning algorithm is the following. We mark vertices of the graph, starting with the root $`0`$. At each iteration of the algorithm, we mark all vertices $`v`$ that have more marked neighbors than the value of the function at $`v`$. If in the end all vertices are marked, then we have a $`G`$-parking function, as it is not hard to see directly from definition. Conversely, for every $`G`$-parking function, this algorithm marks all vertices.

We claim that our bijection corresponding to the breadth first search order $`\pi _{bf}`$ is a natural generalization of Dhar’s algorithm. Given a parking function $`P=(b_1,\mathrm{},b_n)`$, perform the construction of $`T=\mathrm{\Phi }_{\mathrm{\Pi },G}(P)`$ as described above. We know that $`T`$ contains all verices if and only if we started with a $`G`$-parking function. Let us group the vertices of $`T`$ by height, setting $`W_i`$ to be the set of vertices of $`T`$ of height $`i`$.

###### Proposition 5.1.

$`W_i`$ is exactly the set of vertices marked at the $`i`$-th step of the burning algorithm.

###### Proof.

For $`i=0`$ the claim is true because the root $`0`$ is marked at the $`0`$-th step. We prove the claim by induction. Suppose that for $`k<i`$, the vertices in $`W_k`$ are marked at the $`k`$-th step of the Dhar’s algorithm. Let $`e_j=(j,w_j)`$ be the edge going out of $`j`$ in $`T`$. Each vertex $`jW_i`$ has more than $`b_j`$ edges going to vertices not larger than $`w_j`$ in $`\pi _{bf}`$ order. All vertices not larger than $`w_j`$ are in $`_{k<i}W_k`$ since $`w_jW_{i1}`$. Therefore, all vertices in $`W_i`$ are marked at the $`i`$-th step of Dhar’s algorithm. On the other hand, every vertex marked at the $`i`$-th step of the algorithm in our is to be attached in $`T`$ to a vertex from $`_{k<i}W_k`$ since we add vertices to $`T`$ in the order $`\pi _{bf}`$. Thus each such vertex is in $`W_i`$. Hence Dhar’s burning algorithm is realized by our bijection for the breadth first search tree order. ∎

## 6. Acknowledgments

The authors would like to thank Prof. Alexander Postnikov for suggesting this problem and for many helpful discussions. We are also grateful to Prof. Igor Pak and Prof. Richard Stanley for feedback and advice.


format: text

text:
# References

Precise frequency measurements of atomic transitions using a Rb-stabilized resonator

Ayan Banerjee

Dipankar Das

Vasant Natarajan

vasant@physics.iisc.ernet.in

Department of Physics, Indian Institute of Science, Bangalore 560 012, INDIA

## Abstract

We demonstrate a technique for frequency measurements of atomic transitions with a precision of 30 kHz. The frequency is measured using a ring-cavity resonator whose length is calibrated against a reference laser locked to the $`D_2`$ line of 87Rb, the frequency of which is known to 10 kHz. We have used this to measure the hyperfine structure in the $`5P_{3/2}`$ state of 85Rb. We obtain precise values for the hyperfine constants $`A=25.041(6)`$ MHz and $`B=26.013(25)`$ MHz, and a value of 77.992(20) MHz for the isotope shift in the $`D_2`$ line.

OCIS codes: 020.2930,020.3260,120.3940

Precise measurements of atomic energy levels continue to play an important role in the development of physics. The energy levels of alkali atoms are particularly important because of their widespread use in laser-cooling experiments, ultra-cold collision studies, photoassociation spectroscopy, atomic tests of parity violation, and more recently in Bose-Einstein condensation. For example, precise measurement of the $`D_1`$ line in Cs  combined with an atom-interferometric measurement of the photon recoil shift  could lead to a more precise determination of the fine-structure constant $`\alpha `$. In addition, hyperfine-structure and isotope-shift measurements in atomic lines can yield valuable information about the atomic wavefunction and the contribution from nuclear interactions. This is important when comparing theoretical calculations with experimental data in atomic tests of parity violation .

In this Letter, we demonstrate a new technique for precisely measuring the frequencies of atomic transitions. The technique combines the advantages of using tunable diode lasers to access atomic transitions with the fact that the absolute frequency of the $`D_2`$ line in 87Rb has been measured with an accuracy of 10 kHz . A stabilized diode laser locked to this line is used as a frequency reference along with a ring-cavity resonator whose length is locked to the reference laser. For a given cavity length, an unknown laser locked to an atomic transition has a small frequency offset from the nearest cavity resonance. This offset is combined with the cavity mode number to obtain a precise value for the frequency of the unknown laser. We have used this method to make precise measurements of various hyperfine transitions in the $`D_2`$ line of 85Rb. This yields the hyperfine structure in the $`5P_{3/2}`$ state of 85Rb and the isotope shift in the $`D_2`$ line. We demonstrate a precision of 30 kHz, which is more than an order of magnitude improvement over the typical accuracy of other techniques such as level-crossing or optical double-resonance . The only other technique with similar precision is the frequency-comb method using mode-locked lasers . We believe our technique is uniquely suited for measuring hyperfine intervals and isotope shifts since the leading source of systematic errors cancels in such measurements.

Similar measurements have been done previously using a stabilized HeNe laser as the frequency reference and a linear Fabry-Perot resonator . Our use of a Rb-stabilized diode laser as the reference has the primary advantage that there are several known hyperfine transitions that can be used for locking the laser. This enables us to check systematic errors using different reference frequencies. The use of a ring-cavity resonator also has advantages over a linear resonator because the linear design can cause feedback into the diode laser and destabilize it. By contrast, the ring cavity has a traveling wave inside and there is no possibility of feedback destabilization. Furthermore, the mode structure inside the cavity is elliptical, which makes it easier to mode match the elliptical output of the diode laser.

The schematic of the experiment is shown in Fig. 1. The experiment uses two frequency-stabilized diode lasers that are locked to atomic transitions using Doppler-free saturated-absorption spectroscopy. Laser 1 is the reference laser locked on the $`D_2`$ line of 87Rb. Laser 2 is the unknown laser, which in our case is locked on the $`D_2`$ line of 85Rb. The output of the two lasers is fed into the ring-cavity resonator. The cavity length is adjusted using a piezo-mounted mirror to bring it into resonance with the wavelength of Laser 1. The cavity is then locked to this length in a feedback loop. However, Laser 2 will generally be offset from the cavity resonance. This offset is accounted for by shifting the frequency of the laser using an acousto-optic modulator (AOM) before it enters the cavity. The error signal between the shifted frequency of Laser 2 and the cavity resonance is fed back to the AOM driver which locks the frequency of the AOM at the correct offset. The frequency is read using a frequency counter. The absolute frequency of Laser 1 is known with 10 kHz accuracy , therefore, once the cavity length (or mode number) is known, the frequency of Laser 2 is determined very precisely.

The diode lasers are standard external-cavity lasers stabilized using optical feedback from a piezo-mounted grating . They are locked by modulating the injection current and using third-harmonic detection. The ring cavity consists of two plane mirrors and two concave mirrors ($`f=12.5`$ cm) in a bow-tie arrangement. The mirrors are mounted on a copper plate that is temperature controlled to $`\pm 0.01^{}`$C using a thermoelectric cooler. The cavity $`Q`$ is 35 and the free-spectral range (fsr) is 1.3 GHz (corresponding to a cavity length of 226.5 mm). Thus the cavity modes (shown in Fig. 2) have a linewidth of about 37 MHz, which is similar to the linewidth of atomic transitions used in laser stabilization. The low $`Q`$ ensures robust locking that is quite insensitive to perturbations over a wide dynamic range.

The most important aspect of the measurement is to fix the mode number of the cavity uniquely. This is done in two steps: we first measure the cavity fsr and then we use a known frequency for Laser 2. The fsr measurement proceeds as follows. We lock the cavity with the reference laser on the $`F=2F^{}=(2,3)`$ transition, as shown in Fig. 2a, and measure the AOM offset for a given transition of the unknown laser. We then shift the reference laser to the $`F=1F^{}=(1,2)`$ transition, which is exactly 6622.887 MHz higher . This shift causes the cavity mode number to increase by almost exactly 5, as shown in Fig. 2b. The cavity is locked to the new frequency and the AOM offset for the same transition of the unknown laser is measured. The difference in the two AOM offsets along with the change in the reference frequency gives exactly 5 times the cavity fsr. Using this method, the fsr is determined with a precision of 20 kHz. To determine the mode number, we use a diode laser stabilized on the Rb $`D_1`$ line as Laser 2 and determine its AOM offset. The frequency of this laser is already known to an accuracy of 0.4 MHz . Thus, there is a unique mode number that matches the resonance condition and the measured fsr. For example, the next nearest mode satisfying the resonance has an fsr differing by 350 kHz, or 17 times the error in the determination of the fsr. Similarly, if the mode number is changed by 1, the inferred frequency of Laser 2 changes by 30 MHz, which is 75 times larger than the error with which the frequency is known.

We have used the technique to measure hyperfine structure in Rb. To test the reliability of the measurement and our error budget, we first measured hyperfine transitions in the $`D_2`$ line of 87Rb where the frequencies are already known to an accuracy of 10 kHz. For example, for the $`F=2F^{}=(1,3)`$ transition, we measure a frequency of 384 227 903.438(30) MHz while the value from Ref. 4 is 384 227 903.407(10) MHz. With these checks, we have measured hyperfine transitions in 85Rb. The results are listed in Table 1. Each value is an average over 50 individual measurements. The 5 measurements listed are not all independent because there are only 4 hyperfine levels in the $`5P_{3/2}`$ state. Measurements 2 and 4 couple to the same excited level from different ground levels, therefore their difference should be the ground hyperfine splitting of 3035.732 MHz . The measured difference of 3035.682(45) MHz is a further check on our error budget. We have also repeated these measurements with the reference laser on the $`F=1F^{}=(1,2)`$ transition, and verified that the results are consistent within the quoted errors. Finally, the measurements were repeated over a period of several weeks to check for any long-term variation.

The several internal consistency checks discussed above check one class of systematic errors, namely those that are wavelength independent. They could arise because of shifts in the lock point of the lasers, peak pulling from residual Doppler profile, optical pumping effects, etc. In addition, we have verified that systematic errors due to stray magnetic fields or collisional shifts in the Rb vapor cell are negligible. The magnetic field in the vicinity of the cell is less than 0.1 mT, and we have repeated the measurement with the vapor cell at different locations to check that the shift is negligible. Collisional shifts in the vapor cells are estimated to be less than 10 kHz, and we have used different vapor cells to verify that these shifts are also negligible.

There is another class of systematic errors that is wavelength dependent. Since our cavity is comparing the wavelengths of the two lasers, we have to convert these to frequencies using the refractive index of air . Any error in the refractive index would reflect as a systematic shift in the measured frequency. The ratio of refractive indices at two wavelengths from Ref. 8 is expected to be correct only at the $`10^9`$ level, therefore, in future, we plan to use an evacuated cavity to eliminate dispersion effects. Such errors can also arise from wavelength-dependent phase shifts in the cavity mirrors. The dielectric coatings have extremely flat response over $``$200 nm and we do not expect this to affect measurements at the 30 kHz level over a range of 100 nm.

It is important to note that this class of wavelength-dependent systematic errors does not affect the determination of frequency differences of the unknown laser, up to several 10s of GHz. This is the order of magnitude of frequency differences that arise when determining hyperfine structure or isotope shifts. Thus, in the present case, we are confident that such systematic errors are negligible in the determination of the hyperfine intervals in 85Rb. Indeed, the absolute frequencies of the various transitions in Table 1 are also correct because both lasers are at the same wavelength of 780 nm and there is no need to correct for the dispersion of air.

We have used the data in Table 1 to obtain the hyperfine coupling constants in the $`5P_{3/2}`$ state of 85Rb. The measured intervals are fitted to the magnetic-dipole coupling constant $`A`$ and the electric-quadrupole coupling constant $`B`$, to yield values of $`A=25.041(6)`$ MHz and $`B=26.013(25)`$ MHz. In Fig. 3a, we show the good agreement between the measured intervals and the intervals calculated from the fitted constants. The $`A`$ and $`B`$ values are compared to the earlier values of Arimondo et al.  and Barwood et al.  in Fig. 3b. Our value of $`A`$ is consistent with the previous values but has much smaller error. However, the three values of $`B`$ are quite discrepant and have non-overlapping error bars, though our value overlaps with the recommended value of Arimondo et al. at the $`2\sigma `$ level. Finally, the calculated hyperfine shifts can be used to obtain the hyperfine-free $`D_2`$ frequency, which in turn yields the isotope shift in this line to be 77.992(20) MHz.

In conclusion, we have demonstrated a new technique for precisely measuring the frequency of atomic transitions. We have used this technique to measure hyperfine transitions in the $`D_2`$ line of 85Rb with a precision of 30 kHz. Since the reference and unknown lasers are diode lasers locked to atomic transitions using similar techniques, the accuracy and stability of our measurements are both determined by how well we can lock the lasers to the line-center. In future, we plan to use an evacuated cavity where the leading source of systematic error due to dispersion of air will be overcome. This will enable us to measure transitions in other alkali atoms (such as Li, K, and Cs) where the transitions are similarly accessible using diode lasers, but the difference from the reference frequency is much larger. Another improvement is to mix both beams in an optical fiber for better mode-matching into the cavity. We believe the technique can also be extended to UV atomic lines by using a frequency-doubled IR laser. By measuring the IR frequency instead of the UV frequency, we can get similar accuracy for UV lines without the concomitant sources of systematic error.

This work was supported by the Board of Research in Nuclear Sciences (DAE), and the Department of Science and Technology, Government of India.


text:
# Chapter 1 Tau Neutrinos at EeV Energies

## Chapter 1 Tau Neutrinos at EeV Energies

### Abstract

Astrophysical sources of ultrahigh energy neutrinos yield tau neutrino fluxes due to neutrino oscillations. At neutrino energies in the EeV range, radio Cherenkov detection methods show promise for detecting these fluxes. We quantify the tau neutrino contributions to the signal in, for example, a detector like the Radio Ice Cherenkov Experiment (RICE) for a $`Z`$-burst flux prediction. Tau neutrino regeneration in transit through the Earth, including energy loss, is evaluated.

### 1. Introduction

The experimental evidence of $`\nu _\mu \nu _\tau `$ neutrino oscillations  means that astrophysical sources of muon neutrinos become sources of $`\nu _\mu `$ and $`\nu _\tau `$ in equal proportions after oscillations over astronomical distances . Although $`\nu _\mu `$ and $`\nu _\tau `$ have identical interaction cross sections, signals from $`\nu _\tau \tau `$ conversions have the potential to contribute differently from $`\nu _\mu `$ signals. The $`\tau `$ lepton can decay far from the detector, regenerating $`\nu _\tau `$ \[7-9\]. This also occurs with $`\mu `$ decays, but electromagnetic energy loss coupled with the long muon lifetime make the $`\nu _\mu `$ regeneration from muon decays irrelevant for high energies. A second signal of $`\nu _\tau \tau `$ is the tau decay itself .

In this paper, we investigate the effect of $`\nu _\tau `$ regeneration from tau decays in the neutrino energy range between $`10^610^{12}`$ GeV. Attenuation shadows most of the upward-going solid angle for neutrinos. Regeneration comes from interaction and decay, so one is necessarily considering incident neutrinos which are nearly horizontal or slightly upward-going in a discussion of tau neutrino regeneration. The Radio Ice Cherenkov Experiment (RICE)  has put limits on incident isotropic electron neutrino fluxes which produce downward-going electromagnetic showers. Here, we look at the $`\nu _\tau `$ contribution to horizontal or upward-going electromagnetic showers where the shower is produced in 1-4 km of ice. The Antarctic Impulsive Transient Antenna (ANITA) also uses the ice as a neutrino converter . The ANITA balloon missions will monitor the ice sheet for refracted radio frequency signals and require upward-going neutrino interactions.

### 2. Neutrino Attenuation and Regeneration

Tau neutrino attenuation and regeneration is governed by its interaction length and the tau decay length which is shown in Fig. 1. We also plot the effective decay length with tau electromagnetic energy loss . The neutral current neutrino(antineutrino) cross section contribution to the total is about 1/2 of the charged current cross section. As a comparison of the interaction lengths with physical distances we note that the chord (D) of the earth (in water equivalent distance) as a function of the nadir angle is given as $`D=2R_{}\rho _{\mathrm{rock}}\mathrm{cos}\theta =5.9\times 10^7\mathrm{cm}.\mathrm{w}.\mathrm{e}.`$ for $`\theta =89^{}`$. Here $`R_{}=6.4\times 10^8`$ cm, the mean Earth radius and the density of standard rock $`\rho _{\mathrm{rock}}=2.65`$ g/cm3. Neutrino attenuation is clearly an important effect for nearly horizontal neutrinos.

The effective decay length of produced taus does not go above $`10^7`$ cm, even for $`E_\tau =10^{12}`$ GeV. This is because electromagnetic energy loss over that distance reduces the tau energy to about $`10^8`$ GeV, at which point, the tau is more likely to decay than interact electromagnetically .

Attenuation and regeneration is governed by the neutrino transport equations, as in, e.g., Ref. . The coupled differential equations are solved approximately using Euler’s method for the neutrinos, which is modified to include continuous tau decay for the taus. Energy loss of the $`\tau `$ is accounted for by shifting $`E_{\tau ,f}=E_{\tau ,i}\mathrm{exp}(\beta \mathrm{\Delta }X)`$ for column depth step size $`\mathrm{\Delta }X`$ and $`\beta `$ from the average high energy loss formula $`dE_\tau /dX\beta E`$. As a first approximation, we use $`\beta =0.8\times 10^6`$ cm2/g.

### 3. Results

Fig. 2 shows the attenuated/regenerated $`\nu _e`$ and $`\nu _\tau `$ fluxes as well as the $`\tau `$ flux for the $`Z`$-burst  model of Ref. , approximated by

$$\frac{dF_\nu }{dE}[\mathrm{km}^2\mathrm{yr}^1\mathrm{sr}^1\mathrm{GeV}^1]=\{\begin{array}{cc}1/(E/\mathrm{GeV})\hfill & E<2.5\times 10^{12}\text{ GeV}\hfill \\ 6.24\times 10^{24}/(E/\mathrm{GeV})^3\hfill & E2.5\times 10^{12}\text{ GeV}\hfill \end{array}$$
(1)
and we use a nadir angle $`\theta =85^{}`$. We approximate the Earth density over the course of the trajectory to be $`\rho _{\mathrm{rock}}`$ \[$`D=2.9\times 10^8`$ cm.w.e.\]. Little $`\nu _\tau \tau \nu _\tau `$ regeneration occurs, as can be seen by comparing the $`\nu _\tau `$ flux (solid line) with the $`\nu _e`$ flux (dashed line just below solid curve). The dot-dot-dashed line shows the result of simple attenuation with $`\mathrm{exp}(D/_{CC}^\nu (E))`$, which agrees with the $`\nu _e`$ flux for $`E\stackrel{<}{}10^{10}`$ GeV. The uppermost dashed line corresponds to the tau neutrino flux without the energy loss. The tau flux (dot-dash-dashed line) at the end of the neutrino trajectory through the Earth is a factor of $`10^510^3`$ of the attenuated tau neutrino flux for the energy $`E=10^610^{11}`$ GeV.

In Fig. 3, we show the electron fluxes from $`\nu _e`$ charged current (CC) interactions and from $`\tau e`$ for the $`Z`$-burst model, again at $`\theta =85^{}`$, for two different column depths in water: $`D=1`$ km and 4 km. In evaluating the fluxes, we have integrated over energy distributions of the tau decay or the neutrino interaction cross section. The most important contributions of $`\tau e`$ to the electromagnetic signal occur below $`10^8`$ GeV. For taus, electromagnetic energy loss and the falling probability to decay in depth $`D`$ suppress $`\tau e`$ high energy contributions. For $`\nu _e`$, the rising cross section works in the opposite direction.

We conclude that the electron contribution to the electromagnetic signal from $`\tau `$ decay from nearly horizontal incident $`\nu _\tau `$ is a small portion of the $`\nu _ee`$ CC signal, except in the energy range of $`10^610^8`$ GeV, for the $`Z`$-burst flux model. For the RICE experiment, this is in the energy range where their effective detection volume is smallest, making the $`\tau `$ signal from $`Z`$-burst tau neutrinos difficult to extract.

### 4. Acknowledgments

The work of S.I.D. has been supported in part by NSF Grant No. 0070998. The work of I.S. and I.M. has been supported in part by the DOE under contracts No. DE-FG02-95ER40906 and DE-FG02-93ER40792, and NSF Grant No. PHY99-07949. The work of M.H.R. has been supported in part by the DOE under contract number DE-FG02-91ER40664. I.S. and I.M. thank the KITP at UC Santa Barbara for hospitality. We thank J. Jones and J. Sayre for discussions.

### 5. References

1. Ahluwalia D.V., Ortiz C.A., Adunas G.Z. 2000, hep-ph/0006092 (unpublished)

2. Athar H., Jezabek M., Yasuda O. 2000, Phys. Rev. D 62, 1033007

3. Fargion D. 2002, Ap. J. 570, 909

4. Feng J.L., Fisher P., Wilczek F., Yu T.M. 2002, Phys. Rev. Lett. 88, 161102

5. Fukuda Y. et al. \[Super-Kamiokande Collaboration\] 1998, Phys. Rev. Lett., 81, 1562

6. Gorham P. et al. \[ANITA Collaboration\] http://www.ps.uci.edu/$``$barwick/anitaprop.pdf

7. Halzen F., Saltzberg D. 1998, Phys. Rev. Lett. 81, 4305

8. Iyer S., Reno M.H., Sarcevic I. 2000, Phys. Rev. D 61, 053003

9. Iyer Dutta S., Reno M.H., Sarcevic I. 2000, Phys. Rev. D 62, 123001

10. Iyer Dutta S., Reno M.H., Sarcevic I., Seckel D. 2001, Phys. Rev. D 63, 094020

11. Kravchenko I. et al. \[RICE Collaboration\], astro-ph/0206371 (unpublished)

12. Weiler T.J. 1999, Astropart. Phys. 11, 303

13. Yoshida S., Sigl G., Lee S. 1998, Phys. Rev. Lett. 81, 5505


text:
# Weak Gravitational Lensing by Large-Scale Structure

## 1 INTRODUCTION

Gravitational lensing provides a unique method to directly map the distribution of dark matter in the universe. It relies on the measurement of the distortions that lensing induces in the images of background galaxies (for reviews, see Bartelmann & Schneider 1999, Bernardeau 1999, Kaiser 1999, Mellier 1999, Narayan & Bartelmann 1996, Schneider 1995, Wittman 2002). This method is now widely used to map the mass of clusters of galaxies (see Fort & Mellier 1994 for a review) and has been extended to the study of superclusters (Gray et al. 2002, Kaiser et al. 1998) and groups (Hoekstra et al. 2001). Recently, weak lensing was statistically detected for the first time in random patches of the sky (Brown et al. 2003; Bacon et al. 2002; Bacon, Refregier & Ellis 2000; Hamana et al. 2003; Hämmerle et al. 2002; Hoekstra et al. 2002a; Hoekstra, Yee & Gladders 2002a; Jarvis et al. 2002; Kaiser, Wilson & Luppino 2000; Maoli et al. 2001; Refregier, Rhodes, & Groth 2002; Rhodes, Refregier & Groth 2001; van Waerbeke et al. 2000; van Waerbeke et al. 2001a; van Waerbeke et al. 2002; Wittman et al. 2000). These cosmic shear surveys provide direct measurements of large-scale structure in the universe and, therefore, of the distribution of dark matter. Unlike other methods that probe the distribution of light, weak lensing measures the mass and can thus be directly compared to reliable theoretical models of structure formation. Cosmic shear can therefore be used to measure cosmological parameters in the context of these models, thereby opening wide prospects for cosmology (Bernardeau, van Waerbeke & Mellier 1997; Hu & Tegmark 1999; Jain & Seljak 1997; Kaiser 1998).

In the present review, we describe the theoretical and observational status of cosmic shear. Earlier reviews of this fast-evolving field can be found in Hoekstra et al. (2002b), Mellier et al. (2001), van Waerbeke et al. (2002), Wittman (2002). Here, we first describe the principles of weak lensing (Section 2). We then summarize the different statistics used to measure cosmic shear and describe how they are used to constrain cosmological parameters (Section 3). In Section 4, we survey the different methods used to derive the lensing shear from the shapes of background galaxies. We present, in Section 5, the current observations and their cosmological significance. Future cosmic-shear surveys and the prospects they offer for cosmology are described in Section 6. In Section 7, we outline how systematic effects present challenges that must be met for the potential of these future surveys to be fully realized. We summarize our conclusions in Section 8.

## 2 THEORY

The idea of cosmic shear can be traced back to a lecture given by Richard Feynman at Caltech in 1964 (J.E. Gunn, personal communication). Several theorists (e.g., Gunn 1967, Jaroszyńsky et al. 1990, Kristian & Sachs 1966, Lee & Paczyńsky 1990, Schneider & Weiss 1988) then studied the propagation of light in an inhomogeneous universe. Predictions for the statistics of the weak-lensing distortions were then computed in a modern cosmological context by several groups (Babul & Lee 1991, Blandford et al. 1991, Kaiser 1992, Miralda-Escudé 1991, Villumsen 1996). More recently, the power of cosmic shear to measure cosmological parameters was the object of many theoretical studies (Bernardeau, van Waerbeke & Mellier 1997; Jain & Seljak 1997; Hu & Tegmark 1999; Kaiser 1998; Kamionkowski et al. 1997; van Waerbeke, Bernardeau & Mellier 1999). In this section, we briefly describe the principles of weak lensing and show how this technique can be used to map the dark matter in the universe.

As they travel from a background galaxy to the observer, photons get deflected by mass fluctuations along the line of sight (see Figure 1). As a result, the apparent images of background galaxies are subject to a distortion that is characterized by the distortion matrix:

$$\mathrm{\Psi }_{ij}\frac{(\delta \theta _i)}{\theta _j}\left(\begin{array}{cc}\kappa +\gamma _1& \gamma _2\\ \gamma _2& \kappa \gamma _1\end{array}\right),$$
(1)
where $`\delta \theta _i(\theta )`$ is the deflection vector produced by lensing on the sky. The convergence $`\kappa `$ is proportional to the projected mass along the line of sight and describes overall dilations and contractions. The shear $`\gamma _1`$ ($`\gamma _2`$) describes stretches and compressions along (at $`45^{}`$ from) the x-axis. Figure 2 illustrates the geometrical meaning of the two shear components.

The distortion matrix is directly related to the matter density fluctuations along the line of sight by

$$\mathrm{\Psi }_{ij}=_0^{\chi _h}𝑑\chi g(\chi )_i_j\mathrm{\Phi },$$
(2)
where $`\mathrm{\Phi }`$ is the Newtonian potential, $`\chi `$ is the comoving distance, $`\chi _h`$ is the comoving distance to the horizon, and $`_i`$ is the comoving derivative perpendicular to the line of sight. The radial weight function $`g(\chi )`$ is given by

$$g(\chi )=2_\chi ^{\chi _h}𝑑\chi ^{}n(\chi ^{})\frac{r(\chi )r(\chi ^{}\chi )}{r(\chi ^{})},$$
(3)
where $`r=a^1D_A`$, and $`D_A`$ is the angular-diameter distance. The function $`n(\chi )`$ is the distribution of the galaxies as a function of the comoving distance $`\chi `$ from the observer and is assumed to be normalized as $`𝑑\chi n(\chi )=1`$.

As we discuss in Section 4, galaxy shapes can be averaged over a patch of the sky to measure the shear, which is thus an observable. The shear pattern expected in a standard Cold Dark Matter (SCDM) model is shown in Figure 3 for a $`1\times 1`$ deg2 region. Jain, Seljak, & White (2000) derived this map from ray tracing through N-body simulations. Tangential patterns around the overdensities corresponding to clusters and groups of galaxies, along with a more complicated network of shear fluctuations, are apparent. By inverting the lensing equation (Equation 2), the shear map can be converted into a map of the projected mass $`\kappa `$ and, therefore, of the dark matter distribution.

## 3 COSMIC-SHEAR STATISTICS AND COSMOLOGY

The statistical characteristics of the cosmic-shear field can be quantified using a variety of measures, which can then be used to constrain cosmological models. First, we consider the most basic two-point statistic of the shear field, namely the two-dimensional power spectrum (Jain & Seljak 1997, Kaiser 1998, Kamionkowski et al. 1997, Schneider et al. 1998a). The shear power spectrum $`C_𝐥`$ is defined as a function of multipole moment $`l`$ (or inverse angular scale) by $`_{i=1}^2\stackrel{~}{\gamma _i}(𝐥)\stackrel{~}{\gamma _i}(𝐥^{})=(2\pi )^2\delta (𝐥𝐥^{})C_𝐥`$, where tildes denote Fourier transforms (with the conventions of Bacon, Refregier, & Ellis 2000), $`\delta `$ is the two-dimensional Dirac-delta function, and the brackets denote an ensemble average. Applying Limber’s equation in Fourier space (e.g., Kaiser 1998) to Equation 2 and using the Poisson equation, one can easily express the shear power spectrum $`C_l`$ in terms of the three-dimensional power spectrum $`P(k,\chi )`$ of the mass fluctuations $`\delta \rho /\rho `$ and obtain

$$C_l=\frac{9}{16}\left(\frac{H_0}{c}\right)^4\mathrm{\Omega }_m^2_0^{\chi _h}𝑑\chi \left[\frac{g(\chi )}{ar(\chi )}\right]^2P(\frac{l}{r},\chi ),$$
(4)
where $`a`$ is the expansion parameter, and $`H_0`$ and $`\mathrm{\Omega }_m`$ are the present value of the Hubble constant and matter density parameter, respectively. The lensing power spectra for four CDM models are shown in Figure 4 (see color insert) (see Bacon, Refregier & Ellis 2000 for the exact cosmological parameter values of each model). They were derived using the fitting formula for the nonlinear matter power spectrum $`P(k,\chi )`$ of Peacock & Dodds (1996). In Figure 4, the galaxies were assumed to lie on a sheet at a redshift $`z_s=1`$. A more realistic redshift distribution $`n(z)`$ would require corrections of only approximately 10% on these power spectra, as long as the median redshift of the galaxies were kept at $`z_s=1`$.

The three cluster-normalized models ($`\mathrm{\Lambda }`$CDM, OCDM and $`\tau `$CDM) yield power spectra of similar amplitudes but with different shapes. The COBE-normalized SCDM model has more power on a small scale and thus yields a larger normalization. For the $`\mathrm{\Lambda }`$CDM model, the power spectrum corresponding to a linear evolution of structures is also shown in Figure 4 for comparison. For $`l\stackrel{>}{}1000`$ (corresponding to angular scales smaller than approximately 10’), nonlinear corrections dominate the power spectrum (Jain & Seljak 1997), making cosmic-shear sensitive to gravitational instability processes.

The measurement of the lensing power spectrum can thus be used to measure cosmological parameters, such as $`\mathrm{\Omega }_m`$, $`\mathrm{\Omega }_\mathrm{\Lambda }`$, $`\sigma _8`$, and $`\mathrm{\Gamma }`$. (Bernardeau, van Waerbeke & Mellier 1997; Hu & Tegmark 1999; Jain & Seljak 1997; Kaiser 1998; van Waerbeke, Bernardeau & Mellier 1999). A full-sky cosmic-shear survey would yield a precision of these parameters comparable to that for future cosmic microwave background (CMB) missions. More realistically for the short term, a precision on the order of 10% can be achieved with surveys of approximately 10 square degrees. Such cosmic-shear surveys can also be combined with CMB anisotropy measurements to break degeneracies present when the CMB is considered alone (Hu & Tegmark 1999; Contaldi, Hoekstra & Lewis 2003). This would yield improvements in the precision of cosmological parameters by approximately one order of magnitude. In addition, the use of photometric redshifts can provide a tomographic measurement of matter fluctuations and improve the precision of cosmological parameters by up to an order of magnitude (Hu 1999, Hu & Keeton 2002, Taylor 2001).

In practice, it often is more convenient to measure other two-point statistics. In particular, the variance of the shear $`\sigma _\gamma ^2\overline{\gamma }^2`$ in randomly placed cells is widely used. It is related to the shear power spectrum by

$$\sigma _\gamma ^2=\frac{1}{2\pi }_0^{\mathrm{}}𝑑llC_l\left|\stackrel{~}{W}_l\right|^2,$$
(5)
where $`\stackrel{~}{W}_l`$ is the Fourier transform of the cell aperture. The shear two-point correlation functions (eg. Kaiser 1998) are Fourier transforms of the power spectra and have also been measured by various groups (eg. Bacon et al. 2002; van Waerbeke et al. 2001a; Hoekstra et al. 2002a). The $`M_{ap}`$ statistics (Schneider et al. 1998a) is another convenient statistic based on the average of the shear within a compensated filter. Its advantages are that its window function in $`l`$-space is narrow, that adjacent cells are effectively uncorrelated, and that it can be easily related to the statistics of the projected mass $`\kappa `$.

In analogy with electromagnetism, a tensor field like the shear field $`\gamma _i`$ can be decomposed into an electric (E, or gradient) component and a magnetic (B, or curl) component (Crittenden et al. 2001b, Kaiser 1992, Kamionkowski et al. 1997, Stebbins 1996). Because the distortions it induces arise from a scalar field (the gravitational potential), weak lensing only produces E-type fluctuations. On the other hand, systematic effects and intrinsic galaxy alignments are likely to produce both E-type and B-type fluctuations (See Heavens 2001 for a review; also see Section 7.6). The presence of B-modes can thus be used as a measure of contaminants to the cosmic-shear signal. In practice, this decomposition can be performed using the $`M_{ap}`$ statistic (Schneider et al. 1998a, van Waerbeke et al. 2001a) or the power spectrum (Hu & White 2000, Padmanabhan, Seljak & Pen 2002, Pen et al. 2001).

As is apparent in Figure 3, the shear field is not Gaussian but, instead, has apparent coherent structures. Bernardeau, van Waerbeke, & Mellier (1997) have shown that the skewness

$$S_3=\frac{\kappa ^3}{\kappa ^2^2}$$
(6)
of the convergence field $`\kappa `$ can be used to break the degeneracy between $`\sigma _8`$ and $`\mathrm{\Omega }_m`$, which is present when the shear variance alone is considered. The measurement of higher-point statistics is thus of great cosmological interest, but their computation is made difficult by the fact that the angular scales accessible to obervation ($`\theta \stackrel{<}{}10^{}`$) are in the nonlinear regime. Predictions for higher-point correlation functions have been calculated using perturbation theory, the hierarchical ansatz, (Bernardeau & Valageas 2000; Bernardeau, van Waerbeke & Mellier 1997; Hui 1999; Munshi & Coles 2000; Munshi & Jain 2001; van Waerbeke et al. 2001b) and halo models (Cooray & Hu 2001a; Cooray, Hu, & Miralda-Escudé 2000). These techniques have also been used to compute the full probability distribution function of the convergence field (Bernardeau & Valageas 2000, Munshi & Jain 2000, Valageas 2000) and the errors in two-point statistics (Cooray & Hu 2001b; Munshi & Coles 2002; Schneider et al. 2002).

Another possible way to compute the full nonlinear field is to use ray tracing through N-body simulations (Blandford et al. 1991; Hamana, Colombi & Mellier 2000; Jain, Seljak & White 2000; Premadi et al. 2001; Wambsganss, Cen, & Ostriker 1998; White & Hu 2000) to produce simulated shear maps such as those by Jain, Seljak & White (2000) (shown in Figure 3). These can be used to compute and study other proposed measures of non-Gaussianity such as peak statistics (Jain & van Waerbeke 2000), a generalized maximum likelihood (Taylor & Watts 2000), and cluster counts (Bartelmann, King & Schneider 2001). In practice, the complex geometry of surveys makes it difficult to infer a convergence $`\kappa `$ map from the observed shear $`\gamma _i`$. For this reason, a number of researchers have recently proposed the use of high-order statistics of the shear field rather than the skewness $`S_3`$ of the convergence (Bernardeau, van Waerbeke, & Mellier 2003; Schneider & Lombardi 2002; Takada & Jain 2002; Zaldarriaga & Scoccimarro 2002).

## 4 SHEAR MEASUREMENT METHODS

Because the sought-after lensing signal is of only a few percent in amplitude, the data acquisition and analysis must be performed carefully, and systematic effects must be tightly controlled. All the current measurements of cosmic shear were derived from deep optical images taken with charged-coupled devices (CCD). It is advantageous for the exposures to be homogeneous in depth and for the ground to be subject to as small a seeing as possible. The fields are generally chosen to lie far away from each other to ensure that they are statistically independent and to minimize cosmic variance.

The first step in the data analysis is image processing. After flat fielding, the different exposures are co-added to produce the final reduced images. If necessary, any instrumental distortion induced by the telescope optics is corrected for at this stage. This can be done very accurately by measuring the astrometric offsets from several dithered exposures. For a detailed description of the different image-processing steps, see Kaiser et al. (1999). An example of a processed deep image from the cosmic-shear survey of Bacon, Refregier & Ellis (2000) is shown in Figure 5.

The next step consists of deriving an estimator for the shear from the shapes of the galaxies in the co-added images. The point-spread function (PSF), which smears the images of galaxies and is generally not circular, complicates this task. In general, the PSF varies spatially and in time, and it must be measured and modelled for each image individually. This can be done by measuring the shape of the stars in the field, whose number can be optimized by tuning the galactic latitudes of the observations. Figure 6 shows the ellipticity pattern of the PSF from one of the William Hershel telescope (WHT) fields of Bacon, Refregier & Ellis 2000.

Several methods have been developed to tackle this difficult and crucial task. The more rigorous method of Kaiser, Squires & Broadhurst (KSB; 1995), further developed by Luppino & Kaiser (1997) and Hoekstra et al. (1998), replaced the earlier method by Bonnet & Mellier (1995). The KSB method is now widely used for cluster studies, and it has been used by the majority of the groups involved in measuring cosmic shear (see Bartelmann & Schneider 1999 for a detailed review of the KSB method). It is based on the measurement of the quadrupole moment of the galaxy surface brightness $`I(𝐱)`$,

$$Q_{ij}d^2xx_ix_jw(x)I(𝐱),$$
(7)
where $`w(x)`$ is a weight function conveniently taken to be Gaussian. These moments capture the lowest-order shape information of the galaxy and can be combined to form the ellipticity of the galaxy

$$ϵ_1=\frac{Q_{11}Q_{22}}{Q_{11}+Q_{22}},ϵ_2=\frac{2Q_{12}}{Q_{11}+Q_{22}}.$$
(8)
The first (second) component of the ellipticity describes compressions and elongations along (at 45 from) the x and y axes (see Figure 2 for an illustration). The ellipticity vanishes for circular galaxies.

The first step in the KSB method is to correct the observed galaxy ellipticity $`ϵ_i^g`$ for the anisotropy of the PSF. The corrected galaxy ellipticity $`ϵ^g`$ is given by

$$ϵ^g=ϵ^gP_{\mathrm{sm}}^g(P_{\mathrm{sm}}^{})^1ϵ^{},$$
(9)
where $`ϵ^{}`$ is the PSF ellipticity derived from the stars, and $`P_{\mathrm{sm}}^g`$ and $`P_{\mathrm{sm}}^{}`$ are the smear susceptibility tensors for the galaxy and star, respectively, and can be derived from higher moments of the images. The shear in a patch of the sky can then be measured by averaging over the (corrected) ellipticities in the patch of the sky using

$$\gamma =(P_\gamma )^1ϵ^g,$$
(10)
where the tensor $`P_\gamma `$ quantifies the susceptibility to shear acting before isotropic PSF smearing and is given by

$$P_\gamma =P_{\mathrm{sh}}^gP_{\mathrm{sh}}^{}(P_{\mathrm{sm}}^{})^1P_{\mathrm{sm}}^g,$$
(11)
where the shear susceptibility tensors $`P_{\mathrm{sh}}^g`$ and $`P_{\mathrm{sh}}^{}`$ for the galaxies and the stars can also be measured from higher moments of their respective light distribution.

The KSB method was thoroughly tested using realistic simulated images by Erben et al. (2001) and Bacon et al. (2001a). These studies showed that it is accurate to within a few tenths of percent in reconstructing an input shear and is thus sufficient for the current cosmic-shear surveys (see Section 5). However, this accuracy is insufficient for future, more sensitive surveys (see Section 6). Moreover, Kuijken (1999) and Kaiser (2000) have shown that the KSB method is ill-defined mathematically and unstable for PSF’s found in practice.

This inadequacy has led a number of researchers to develop alternative methods. Rhodes, Refregier & Groth (2000) have modified the KSB method to be better suited for HST images. Kuijken (1999) considered a different approach that consisted of fitting the observed galaxy shape with a smeared and sheared circular model. Kaiser (2000) introduced a new method based on a finite resolution shear operator. Refregier & Bacon (2003) and, independently, Bernstein & Jarvis (2001) developed a new method based on the decomposition of the galaxies into shape components or “shapelets”. The gauss-hermite orthogonal basis functions used in this approach allow shears and PSF convolutions to be described as simple matrix operations, using the formalism developped for the quantum harmonic oscillator (Refregier 2003). These new methods are promising but require extensive testing to establish whether they will achieve the required precision.

## 5 OBSERVATIONS

Because the expected distortions are only of a few percent, the measurement of cosmic shear requires large survey areas and excellent image quality. Early searches for cosmic shear signals with photographic plates were unsuccesful (Kristian 1967; Valdes, Jarvis & Tyson 1983). Mould et al. (1994), performed the first attempt to detect a cosmic-shear signal with CCDs, but only derived an upper limit. Using the same data, Villumsen (1995) reported a $`4.5\sigma `$ detection. Schneider et al. (1998b) then reported a detection of cosmic shear in one of three QSO fields, an area too small to draw any constraints on cosmology.

Within a few weeks, four independent groups (Bacon, Refregier & Ellis 2000; Kaiser, Wilson & Luppino 2000; van Waerbeke et al. 2000; Wittman et al. 2000) reported the first firm statistical detections of cosmic shear using three different 4m-class telescopes: the Cerro Tololo Inter-American Observatory (CTIO), the Canada-France-Hawaii Telescope (CFHT), and the William Herschel Telescope (WHT). These were later confirmed by more precise measurements of the cosmic-shear amplitude from the ground (Bacon et al. 2002; Brown et al. 2003; Maoli et al. 2001; Hamana et al. 2003; Hoekstra et al. 2002a; Hoekstra, Yee & Gladders 2002a; Jarvis et al. 2002; van Waerbeke et al. 2001; van Waerbeke et al. 2002a) using 2-m – (MPG/ESO), 4-m– (WHT, CFHT, CTIO) and 8-m– (Very Large Telescope, Keck, Subaru) class ground-based telescopes. Meanwhile, cosmic shear was also detected (Hämmerle et al. 2002; Rhodes, Refregier & Groth 2001) and measured (Refregier, Rhodes & Groth 2002) from space using HST. Space-based surveys are currently limited by the small field of view of HST, but they are deeper and less prone to systematics thanks to the absence of atmospheric seeing.

Table 1 summarizes the existing cosmic-shear surveys and highlights the wide range of telescopes, survey areas, and depths. The shear variance $`\sigma _\gamma ^2`$ (Equation 5) measured recently by several groups is shown in Figure 7 (see color insert) as a function of the radius a circular cell. The results by Hämmerle et al. (2002) and Hamana et al. (2002a) are not displayed. Note that, for the shear variance, the data points at different angular scales are not independent. For comparison, the shear variance predicted for a $`\mathrm{\Lambda }`$CDM model with $`\sigma _8=1`$ is also shown in Figure 7. The model is displayed for median galaxy redshifts of $`z_m`$ from 0.8 to 1.0, corresponding approximately to the range of depths of the top five surveys displayed (van Waerbeke et al. 2002a; Brown et al. 2003; Bacon et al. 2002, WHT and Keck; Refregier et al. 2002). These observations are approximately consistent with each other and with the $`\mathrm{\Lambda }`$CDM model on angular scales from 0.7 to 20 arcmins. This is compelling given that these were performed with different telescopes (and therefore different instrumental systematics) and independent data-analysis pipelines.

The bottom two surveys (Hoekstra et al. 2002b; Jarvis et al. 2002) have a median redshift in the range $`z_m0.6`$$`0.7`$ and yield lower shear variances. As indicated by the theoretical curves in figure 7, this redshift dependence is expected in CDM models and thus confirms the detection of a cosmic shear signal.

Although the shear variance was displayed for the purpose of Figure 7, some of the groups have used instead the shear correlation function or $`M_{ap}`$ statistic to quantify their lensing signal. Recently, several groups used the latter statistic to separate their signal into $`E`$ and $`B`$ components (see Section 3) and thus to estimate and subtract systematic effects (Jarvis et al. 2002; Hamana et al. 2003; Hoekstra, Yee & Gladders 2002; van Waerbeke et al. 2001, 2002a). Pen, van Waerbeke & Mellier (2001) and Brown et al. (2003) chose instead to measure directly the shear power spectrum for each $`E`$ and $`B`$ mode. Figure 8a shows the measurement of the $`E`$ and $`B`$ signals using the $`M_{ap}`$ statistic by Hoekstra, Yee & Gladders (2002a), for several $`R_c`$-magnitude ranges in the Red-Sequence Cluster (RCS) survey. They measure a clear lensing signal apparent as $`E`$ modes. However, the significant $`B`$ modes reveals the presence of residual systematics on small scales ($`\theta \stackrel{<}{}10^{}`$), especially for bright galaxies. In their analysis, these authors use the amplitude of the $`B`$ modes as a measure systematic uncertainties.

Existing cosmic-shear measurements already yield interesting constraints on the amplitude of the matter power spectrum $`\sigma _8`$ on which the lensing signal strongly depends. For instance, Figure 8b shows cosmological constraints for a $`\mathrm{\Lambda }`$CDM model derived by Hoekstra, Yee & Gladders (2002a) from the measurement of the $`M_{ap}`$ statistic for their $`22<R_c<24`$ galaxy sample. The degeneracy between $`\sigma _8`$ and $`\mathrm{\Omega }_m`$ apparent in the figure is typical of cosmic-shear measurements involving only two-point statistics. Hoekstra, Yee & Gladders (2002a) found that the constraints are well described by $`\sigma _8\mathrm{\Omega }_m^{0.52}=0.46_{0.07}^{+0.05}`$ (95% CL), where priors from CMB and galaxy survey data have been used to marginalize over $`\mathrm{\Gamma }`$ and $`\mathrm{\Omega }_\mathrm{\Lambda }`$. Other surveys find constraints of the same form with similar exponents for $`\mathrm{\Omega }_m`$.

Table 1 lists the values of $`\sigma _8`$ found by the different groups. The errors have been converted to 68% confidence level (CL) when necessary, and values of $`\mathrm{\Omega }_m=0.3`$, $`\mathrm{\Omega }_\mathrm{\Lambda }=0.7`$, and $`\mathrm{\Gamma }=0.21`$ have been assumed, when possible. The most recent values are displayed in Figure 9 (see color insert), along with their average $`\sigma _80.83\pm 0.04`$ ($`1\sigma `$). The values derived by the different cosmic shear groups are in the range $`\sigma _80.7`$$`1.0`$, with the most recent measurements (Brown et al. 2003; Hamana et al. 2003; Jarvis et al. 2002) yielding lower values. The $`2`$$`3\sigma `$ mutual inconsistencies between some of the measurements may be symptomatic of a small level of residual systematics. In particular, calibration errors in the shear measurement method would not be detected via the $`E`$-$`B`$ decomposition and are a likely explanation (see Hirata & Seljak 2003). Another source of discrepancy arises from the different fitting functions for the non-linear evolution of the power spectrum (see section 2). Apart from Brown et al. (2003; see also Contaldi et al. 2003) who used the more accurate results of Smith et al. (2003), the other groups used the Peacock & Dodds (1997) fitting function which yields an underprediction of $`\sigma _8`$ by roughly 5–10%. The impact of these systematics will be discussed further in section 7.

Interestingly, an independent measurement of $`\sigma _8`$ is provided by the abundance of X-ray clusters and can be directly compared to this value. Initially, this method yielded normalisations of $`\sigma _80.9`$ (Eke et al. 1998; Pierpaoli, Scott & White 2001; Viana & Liddle 1999), in agreement with the early cosmic shear results (see table 1 and figure 9). This value was subsequently revised downward to $`\sigma _80.7`$$`0.8`$ by the use of the observed, rather than simulated, mass-temperature relation in clusters (Borgani et al. 2001; Reiprich & Böhringer 2001; Seljak 2001; Viana, Nichol & Liddle 2001; Pierpaoli, Scott & White 2002). Recently, Spergel et al. (2003) derived a value of $`\sigma _8=0.84\pm 0.04`$ (68%CL) from a joint analysis of CMB anisotropy measurements from the Wilkinson Microwave Anistropy Probe (WMAP) and other experiments, galaxy clustering and the Lyman $`\alpha `$ forest. For comparison, these results along with a representative value of the revised cluster-abundance normalization (Pierpaoli, Scott & White 2002) are also shown in figure 9. The average of the cosmic shear results is formally in good agreement with the determination of $`\sigma _8`$ using the other techniques. Future surveys are however needed to confirm this, by resolving the discrepancies between the current cosmic shear measurements. Also, a full likelihood analysis would be required to establish the significance of the agreement between the different techniques (see Contaldi et al. 2003). This comparison is important as it provides a strong test of the $`\mathrm{\Lambda }`$CDM model, the gravitational instability paradigm, the physics of clusters, and of the biased formation of galaxies.

As discussed in Section 3, the degeneracy between $`\sigma _8`$ and $`\mathrm{\Omega }_m`$ can be broken by measuring higher-order correlation functions of the lensing field. Bernardeau, Mellier, & van Waerbeke (2002) recently reported the first detection of a non-Gaussian shear signal using the 3-point shear correlation function formalism of Bernardeau, van Waerbeke & Mellier (2003). Another measure of non-gaussianity was recently performed by Miyazaki et al. (2002) using peak statistics in their Subaru survey. Although these results are consistent with that expected from structure formation models, larger survey areas are needed to infer cosmological constraints.

Another approach to probe the dark matter is to measure the bias between the mass and galaxies by cross-correlating the shear map with that of the light from foreground galaxies in the same region of the sky (Cooray 2002, Schneider 1998, van Waerbeke 1998). Hoekstra, Yee & Gladders (2001a), Hoekstra et al. (2002b), and Wilson, Kaiser & Luppino (2001) have recently measured this cross-correlation on large scales.

## 6 FUTURE SURVEYS AND PROSPECTS

The existing measurements described above are primarily limited by statistics. They will therefore be improved upon by ongoing surveys on existing telescopes, such as the Legacy Survey on CFHT (CFHTLS; Mellier et al. 2000), the Deep Lens Survey (Wittman et al. 2002), surveys with the Subaru telescope (Hiroyasu et al. 2001) and the Sloan Digital Sky Survey (Stebbins, McKay & Frieman 1995). Future instruments dedicated to surveys and for which cosmic shear is a primary science driver are being planned, such as Megacam on CFHT (Boulade et al. 2000), the Visible and Infrared Survey Telescope for Astronomy (VISTA; Taylor et al. 2003), the Large aperture Synoptic Survey Telescope (LSST; Tyson et al. 2002a,b), or the novel Panoramic Survey Telescope and Rapid Response System (Pan-STARRS; Kaiser, Tonry & Luppino 2000). From space, the new Advanced Camera for Surveys (ACS) on HST and, much more ambitiously, the future Supernova Acceleration Probe satellite (SNAP; Perlmutter et al. 2003; Rhodes et al. 2003; Massey et al. 2003; Refregier et al. 2003) also offer exciting prospects. Table 2 lists the characteristics of some of these future surveys. Broadly speaking, ground-based measurements will cover large areas, whereas space-based surveys will yield higher-resolution maps and reduced systematics thanks to the absence of atmospheric seeing.

Radio surveys offer another interesting prospect. Ongoing efforts are aimed at detecting cosmic shear with the FIRST radio survey (Chang & Refregier 2002, Kamionkowski et al. 1997, Refregier et al. 1998). The future radio telescopes LOFAR (Low Frequency Array) and SKA (Square Kilometer Array) will yield cosmic-shear measurements of comparable sensitivity to the most ambitious optical surveys (Schneider 1999). The advantages of radio surveys are that they cover large solid angles, that the bright radio sources are at a higher redshift, and that the PSF is fully predictable and reproducible.

These future surveys will provide very accurate measurements of cosmological parameters through the measurement of the lensing power spectrum and higher-order statistics. Figure 10 (see color insert) shows, for instance, the excellent accuracy with which the lensing power spectrum will be measured with the SNAP wide survey. They will also allow us to test some of the foundations of the standard cosmological model. For example, the measurement of the power spectrum on nonlinear scales at different redshift slices, and of the hierarchy of high-order correlation functions, will yield a direct test of the gravitational instability paradigm. The lensing power spectrum can also be used to measure the equation of the state of the dark energy $`w`$ and thus complement supernovae measurements in the constraining of quintessence models (Benabed & Bernardeau 2001; Hui 1999; Huterer 2001; Hu 2001, 2002; Munshi & Wang 2002; Weinberg & Kamionkowski 2002). Figure 10 shows, for instance, that a change of 40% in $`w`$ can easily be measured by SNAP (see Refregier et al. 2003). Cosmic-shear measurements can also be used to test general relativity (Uzan & Bernardeau 2001).

Another promising approach to measure weak lensing is to use the fluctuations of the CMB temperature as the background sources (Bernardeau 1997, 1998; Cooray & Kesden 2002; Hirata & Seljak 2002; Hu 2000; Seljak 1996; Seljak & Zaldarriaga 1999; Zaldarriaga & Seljak 1998). Because these fluctuations are produced at a redshift of approximately 1100, CMB lensing provides a probe of the evolution of mass fluctuations at redshifts larger than those probed by optical galaxies. Lensing indeed produces distinct non-Gaussian signatures that can be used to reconstruct the foreground mass distribution and probe the growth of structures. This approach will become feasible with the advent of future CMB missions such as Planck Surveyor or ground-based instruments with high angular resolutions.

## 7 CHALLENGE: SYSTEMATIC EFFECTS

For the future surveys described above to yield their full potential, a number of challenges must be met. Indeed, these surveys require the measurement of shears on the order of 1% with an accuracy better than 0.1%; thus, they require a very tight control of systematic effects. In the following, we review the main sources of systematics.

### 7.1 PSF Anisotropy

The most serious systematic for ground-based surveys is that produced by the rather large PSF ellipticities ($`10\%`$) observed by the different groups. The KSB method (see Section 4) provides a correction of the PSF anisotropy by, at most, a factor of approximately 10, which is insufficient for a precision of 0.1% in shear. Although new shear measurement methods may improve upon this (see Section 4 and below), the correction is fundamentally limited by the finite surface density and signal-to-noise ratio of the stars used to measure the PSF shape. It is, therefore, necessary for the PSF ellipticity to be reduced in hardware as well as in software. This can be done by using tighter constraints in the tracking and optical systems of the new telescopes and instruments as well as with interactions between telescope designers, engineers, and scientists.

### 7.2 Shear Measurement Method

Even if the PSF ellipticity were guaranteed to be isotropic, future measurements will be limited by the precision of the shear measurement methods. The KSB method is accurate to measure shears of approximately 1% with only a 10% accuracy (Bacon et al. 2001, Erben et al. 2001). This will soon become an important limiting factor (see Hirata & Seljak 2003). Although new methods (see Section 4) promise to improve upon this, more extensive simulations are required to establish that the same accuracy can be reached for shears of 0.1%.

### 7.3 Redshift Distribution

To convert cosmic-shear measurements into constraints on cosmological parameters, the redshift distribution of the background galaxies must be known (see Section 4). The uncertainty in the median galaxy redshift is already one of the dominant contributions to the uncertainty in the amplitude of the matter power spectrum from cosmic shear. The determination of the galaxy redshift distribution is made difficult by the depth of the cosmic-shear surveys. In addition, the sample of galaxies is not simply magnitude limited, but it is subject to complex selection cuts throughout the shear measurement pipeline. Dedicated spectroscopic surveys and photometric redshift studies (such as that by Brown et al. 2003) are thus required to overcome this limitation.

### 7.4 CCD Nonlinearities

All the shear measurement methods rely on the assumption that the instrumental response is linear. It is therefore important to test whether CCD cameras do not have subtle pixel-to-pixel nonlinearities that would induce biases in the shear measurements. The mean shear offset and the shear gradient across the chip found by van Waerbeke et al. (2001) could be due to this effect.

### 7.5 Overlapping Isophotes

Two neighboring galaxies in an image yield ”peanut-shaped” isophotal contours and thus appear to have aligned ellipticities. This overlapping-ellipticities effect may produce a spurious ellipticity correlation signal on small scales. van Waerbeke et al. (2000) suggested that this effect may explain the excess shear signal, which they measured on small scale and which disappeared when close pairs were discarded. Evidence for this effect was also found in the image simulation by Bacon et al. (2001). More extensive and detailed simulations would need to be performed to ascertain and calibrate this effect.

### 7.6 Intrinsic Correlations

The measurement of the lensing shear relies on the assumptions that, in the absence of lensing, the ellipticities of the galaxies are uncorrelated. However, an intrinsic correlation of galaxy shapes could exist owing to the coupling of the galaxy angular momentum or shape to the tidal field or to galaxy interactions (see Heavens 2001 for a review). Theoretical estimation of the size of this effect has been performed using numerical simulations (Croft & Metzler 2000; Heavens, Refregier & Heymans 2000; Jing 2002) and analytical methods (Catalan, Kamionkowski & Blandford 2001; Crittenden et al. 2001a,b; Lee & Pen 2001; Mackey, White & Kamionkowski 2001). Measurements of intrinsic correlations have also been performed (Brown et al. 2000; Pen, Lee & Seljak 2000). Although considerable uncertainty remains regarding the amplitude of this effect, a consensus is arising that intrinsic correlations are likely to be small for the deep current surveys with $`z_m1`$, but may be dominant for shallower surveys with $`z_m\stackrel{<}{}0.2`$ (see however the conflicting results of Jing 2002). Although lensing distortions are coherent over a large redshift range, intrinsic alignments are only significant for small physical separations. Photometric redshifts can thus be used to separate and reduce intrinsic correlations from cosmic-shear signals (Heymans & Heavens 2002; King & Schneider 2002a,b). Another approach is to search for the $`B`$-type correlation signal produced by intrinsic correlations (Crittenden et al. 2001b).

### 7.7 Theoretical Uncertainties

Most of the signal in cosmic-shear surveys arises from small scales ($`\theta \stackrel{<}{}10^{}`$) and thus from nonlinear structures (Jain & Seljak 1997). The existing prescriptions for computing the nonlinear corrections (Peacock & Dodds 1997; Ma 1998) to the matter power spectrum are only accurate to approximately 10% and disagree at that level with one another (see discussion in Huterer 2001). This theoretical uncertainty will soon become one of the dominating errors in the determination of cosmological parameters from cosmic-shear surveys (see discussion in van Waerbeke et al. 2002). New prescriptions based on more recent N-body simulations such as those by Smith et al. (2003) will help improve the accuracy of the predictions. The problem of the prediction of higher-order statistics is even more difficult, but it is not as pressing given the large uncertainties in the the measurements within current surveys (see Bernardeau, Mellier, van Waerbeke 2002). The inclusion of second-order terms in the weak-lensing approximation will eventually also be required (Cooray 2002, Cooray & Hu 2002).

These systematic effects must be controlled to match the statistical accuracy of future surveys. Along with the studies suggested above, further measurements with different colors and comparison of various surveys in overlapping regions would help to control systematics and to test data analysis pipelines. On the theoretical side, larger simulations coupled with advanced analytical techniques will be required.

## 8 CONCLUSIONS

Cosmic shear has emerged as a powerful method to measure the large-scale structure in the universe. It can be thought of as the measurement of background fluctuations in the space-time metric. Although other methods rely on assumptions relating the distribution of light to that of the mass, weak lensing is based on “clean” physics and can be directly compared to theory. The past three years have yielded impressive observational progress, as the first statistical detections and measurements of cosmic shear have been achieved. In analogy with the CMB, cosmic shear has moved from the COBE era to that of the first generation of anisotropy experiments. However, the measurement of cosmic shear differs from that of CMB anisotropies in several respects. First, the fluctuations are on the order of $`10^2`$ as opposed to $`10^5`$, making them easier to measure while retaining the validity of linear calculations. Second, the cosmic-shear field is non-Gaussian and therefore contains more information than that quantified by the power spectrum.

Existing cosmic-shear measurements have started to yield significant constraints on cosmological parameters. The measurement of the amplitude of the matter power spectrum $`\sigma _8\mathrm{\Omega }_m^{0.5}`$ from cosmic shear should soon replace that derived from the local abundance of clusters. This latter technique is indeed limited by the finite number of bright clusters and by systematic uncertainties in the physics of clusters. With better statistics, the angular and redshift dependence of the shear signal as well as with higher-order moments of the convergence field will break the degeneracy between $`\sigma _8`$ and $`\mathrm{\Omega }_m`$ and yield constraints on further parameters such as $`\mathrm{\Omega }_\mathrm{\Lambda }`$ and $`\mathrm{\Gamma }`$.

The current measurements of cosmic shear are now primarily limited by statistics. They will therefore be improved upon by a number of upcoming and future instruments such as Megacam, VST, VISTA, LSST, and Pan-STARRS from the ground, and HST/ACS and SNAP in space. For several of these instruments, a weak-lensing survey has been listed as one of the primary science drivers. These surveys will potentially yield measurements of cosmological parameters that are comparable in precision and complementary to those derived from the CMB. They will also be able to address more far-reaching questions in cosmology by measuring parameters beyond the standard model. For instance, they can be used to provide a test of the gravitational instability paradigm, a measure of the equation of state of the dark energy, and a test of general relativity.

For these instruments to yield the full promise of cosmic shear, a number of challenges have to be met. First, observationally, systematic effects, such as the PSF anisotropy and CCD nonlinearities, must be controlled and corrected for. From the theoretical point of view, calculations of the nonlinear power spectrum, of high-order statistics, and of the associated errors must be improved to meet the precision of future measurements. The observational and theoretical efforts required to overcome these difficulties are worthwhile given the remarkable promise that cosmic shear offers to cosmology.

Acknowledgments The author thanks his collaborators David Bacon, Richard Massey, Tzu-Ching Chang, Jason Rhodes, and Richard Ellis for numerous fruitful discussions. The author thanks Bhuvnesh Jain, David Bacon, and Henk Hoekstra for their permission to reproduce their figure. He also thanks Tony Tyson, Hervé Aussel and Andy Taylor for precisions regarding the parameters of future cosmic shear surveys. He is also grateful to Richard Ellis, Henk Hoekstra, Gary Bernstein, Yannick Mellier, Richard Massey, and Ivan Valtchanov for useful comments on the manuscript.

The Annual Review of Astronomy and Astrophysics is online at

http://astro.annualreviews.org