text:
# The volume and lengths on a three sphere

## 1 Introduction

In this paper we consider the volume, $`Vol(g)`$, of a Riemannian metric $`g`$ on the three sphere. We let $`L(g)`$ represent the length of the shortest nontrivial closed geodesic in $`(S^3,g)`$. By an “antipodal map”, $`A`$, on an $`n`$-sphere we will mean an order 2, fixed point free diffeomorphism. We will let $`D(g,A)=inf_{xS^3}d(x,Ax)`$, and $`D(g)=sup_AD(g,A)`$. The main result of this paper is:

Theorem 1.1. For any Riemannian metric on $`S^3`$ we have:

$$Vol(g)^{\frac{1}{3}}C_1\mathrm{min}\{L(g),2D(g)\}$$

where $`C_1`$ is a universal constant (which can be taken to be $`\frac{1}{3180}`$)

This theorem is an example of a “universal” inequality. This is a term introduced by Berger to describe inequalities on a Riemannian manifold $`(M,g)`$ (usually between minimizing objects in some topological class) which hold for all metrics $`g`$ on $`M`$. With the glaring exception of Gromov’s work \[Gr\] (which we discuss below) most such inequalities are known in 2 dimensions only. Many of these inequalities involve the systole, $`sys(g)`$, which is the length of the shortest closed noncontractible curve in $`M`$. Estimates of the form $`A(g)^{\frac{1}{2}}c(M)sys(g)`$, Where $`A(g)`$ represents the area, have been proved for all surfaces $`M`$. The first of these was proved by Loewner (unpublished) where he finds the sharp value of $`c(T^2)`$ (sharp for the flat regular hexagonal torus). The sharp values of $`c(RP^2)`$ and $`c(K^2)`$ for the projective plane (the round one is best) and Klein bottle (the best one is singular and not flat!) were proven by Pu \[Pu\] and Bavard \[Ba\] respectively. For surfaces of genus $`\gamma `$, nonsharp constants $`c(\gamma )`$ (which unfortunately went to 0 as $`\gamma `$ grew) were first proved independently by Accola \[Ac\] and Blatter \[Bl\]. Gromov greatly improve these constants in \[Gr\] so that they grow correctly with $`\gamma `$. However, the best constants are still unknown. Finding them is likely to be an extremely hard problem.

None of the above says anything about $`S^2`$ since it is simply connected. However there are two inequalities of this type on $`S^2`$. The first, due to Berger \[Be\] says that there is a universal constant $`c_2`$ such that for any antipodal map $`A:S^2S^2`$:

$$Vol(S^2,g)^{\frac{1}{2}}c_2D(g,A).$$
$`1.1`$
The sharp constant is not known, but is conjectured to be that of the round sphere. The other result (see \[Cr2\]) is that

$$Vol(S^2,g)^{\frac{1}{2}}c_3L(g).$$
$`1.2`$
Also in this case the sharp constant is not known. It is conjectured to be that for the singular metric one gets by gluing two flat equilateral triangles along their boundaries.

We now turn to higher dimensions. The most important results in the area are in Gromov’s paper “Filling Riemannian Manifolds” \[Gr\]. Gromov shows that for essential manifolds (which includes $`T^n`$, $`RP^n`$, and all compact $`K(\pi ,1)`$ spaces) we have $`V(g)^{\frac{1}{n}}c(n)sys(g)`$. However, this says nothing directly about $`S^n`$ (or any compact simply connected manifold). For example the natural generalizations of 1.1 and 1.2 above for $`S^2`$ are open questions for $`S^n`$, $`n3`$. Note that for any Riemannian manifold $`(M,g)`$ of injectivity radius $`inj(M)`$ and any $`r\frac{1}{2}inj(M)`$ the metric spheres $`S(x,r)`$ with their induced Riemannian metrics $`\overline{g}`$ satisfy $`D(\overline{g},A)2r`$, so an estimate $`Vol(g)^{\frac{1}{n}}c(S^n)D(g,A)`$ which was sharp for the round spheres would give sharp estimates for the volume of small metric spheres. See \[Cr1\] for nonsharp estimates for the volume of such metric spheres.

In the other direction, Ivanov (see \[I1\] or \[I2\]) has given examples of a sequence of metrics on $`S^3`$ that Gromov-Housdorff converge to the standard metric but whose volumes go to zero.

Although Theorem 1 does not yield either 1.1. or 1.2 for $`S^3`$ it does show that for any given metric one or the other inequality must hold.

For $`A:S^3S^3`$ an antipodal map we let $`L(g,A)`$ be the infimum of the lengths of curves, $`\gamma `$ such that $`\gamma `$ links $`A(\gamma )`$. Here we will say $`\gamma `$ links $`\tau `$ if either $`\gamma `$ intersects $`\tau `$ or the linking number of $`\gamma `$ and $`\tau `$ is nonzero. We consider two cases. If there is no closed curve $`\gamma `$ that links $`A(\gamma )`$ of length less than $`2D(g,A)`$ then $`L(g,A)=2D(g,A)`$ and the minimum length $`\gamma `$ is the union of two minimizing geodesics between $`x`$ and $`A(x)`$ for some $`x`$. Otherwise there is such a closed curve $`\gamma `$. In this case we can apply curve shortening to $`\gamma `$ to get a continuous family $`\gamma _t`$ each of which is shorter than $`\gamma `$ and hence does not intersect $`A(\gamma _t)`$. Thus we see that $`\gamma _t`$ links with $`A(\gamma _t)`$ and hence has length bounded below by $`L(g,A)`$. By looking at limits of such $`\gamma _t`$ we find nontrivial closed geodesics of length less than the length of $`\gamma `$. Since this is true for all such $`\gamma `$ we find that there is a closed geodesic of length $`L(g,A)`$. Thus the invariants $`L(g)`$ and $`D(g,A)`$ are thus related to $`L(g,A)`$ via:

$$L(g,A)min\{L(g),2D(g,A)\}.$$

Theorem 1 thus will follow from:

Theorem 1.2. For any Riemannian metric on $`S^3`$ and any antipodal map $`A`$, we have:

$$Vol(g)^{\frac{1}{3}}C_1L(A,g)$$

where $`C_1`$ is a universal constant (which can be taken to be $`\frac{1}{3180}`$)

The fundamental result in the proof of Gromov’s isosystolic inequality is his filling radius theorem: $`Fillrad(g)c_nVol(g)^{\frac{1}{n}}`$, which holds for all Riemannian $`n`$-manifolds (here $`c_3<265`$). We define the filling radius, $`Fillrad(g)`$, in the next section. We also make fundamental use of it since Theorem 1 will thus follow from

Theorem 1.3. For any Riemannian metric on $`S^3`$ and any antipodal map $`A`$, we have:

$$Fillrad(g)C_4L(g,A)$$

Where $`C_4`$ is a universal constant (which can be taken to be $`\frac{1}{12}`$)

The proof of this theorem is a generalization of an argument that works on $`S^2`$ to yield:

Theorem 1.4. For any Riemannian metric on $`S^2`$ we and any antipodal map $`A`$ we have:

$$Fillrad(g)\frac{1}{4}D(g,A)$$

This theorem along with the Filling radius theorem recovers Berger’s estimate equation 1.1 (although with a worse constant). We present the argument in section 3.

The author would like to thank Herman Gluck for helpful conversations.

## 2 Notation/Preliminaries

The main purpose of this section is to set up notation and remind the reader about the Filling radius (for details see \[Gr\]):

In \[Gr\] Gromov introduced the notion of the filling radius (we use integer coefficients) $`Fillrad(M)`$ of a closed $`n`$-dimensional manifold $`M`$ with a metric $`d`$ (not necessarily Riemannian). We will only consider the case where $`M`$ is homeomorphic to $`S^2`$ or $`S^3`$ and the metric is Riemannian. There is a natural isometric embedding (in the metric space sense!) $`i:ML^{\mathrm{}}(M)`$ defined by $`i(x)()=d_M(x,)`$. The filling radius is the infimum of $`r`$ such that $`i(M)`$ bounds in the tubular neighborhood $`T_r(i(M))`$ in the sense that $`i_{}(H_n(M;))`$ vanishes in $`H_n(T_r(i(M));)`$. We will represent a filling as continuous map $`\sigma :\mathrm{\Sigma }T_r(i(M))`$ from an $`n+1`$-dimensional simplicial complex $`\mathrm{\Sigma }`$ such that $`\sigma |_\mathrm{\Sigma }:\mathrm{\Sigma }i(M)`$ represents a generator in $`H_n(M;)`$.

We note that for any fixed $`ϵ>0`$ by taking Barycentric subdivisions as needed we may assume that the $`\sigma `$-image of any simplex has diameter less than $`ϵ`$ in $`L^{\mathrm{}}(X)`$.

We note that there can be no continuous map $`f:\mathrm{\Sigma }i(X)`$ which agrees with $`\sigma `$ on $`\mathrm{\Sigma }`$ since $`\sigma |_\mathrm{\Sigma }`$ represents a generator of the top homology (so is not a boundary). Our proof of Theorem 1 will be by contradiction. We assume that $`Fillrad(g)`$ is small, take a filling $`\sigma :\mathrm{\Sigma }L^{\mathrm{}}(M)`$ as above, and show that $`\sigma :\mathrm{\Sigma }i(M)`$ extends to a continuous $`f:\mathrm{\Sigma }i(M)`$ giving the desired contradiction. Our proof of Theorem 1 uses a similar contradiction.

We use the notation $`S_i(\mathrm{\Sigma })`$ to denote the $`i`$-skeleton of a simplicial complex $`\mathrm{\Sigma }`$. For each $`i=0,1,2,\mathrm{},n+1`$ We will let $`\{\mathrm{\Delta }_j^i\}`$ denote the set of $`i`$ simplices in the $`n+1`$ dimensional simplicial complex $`\mathrm{\Sigma }`$. For each i-simplex $`\mathrm{\Delta }_j^i`$ we let $`G_j^i`$ be the connected graph (i.e. 1-complex) $`G_j^i=\{S_1(\mathrm{\Delta }_k^{n+1})|\mathrm{\Delta }_j^i`$ is a face of $`\mathrm{\Delta }_k^{n+1}\}`$. By taking Barycentric subdivisions if needed we can assume that any two simplices intersect in a single (possibly empty) common face. Then we see that $`H_1(G_j^i)`$ is generated by the boundaries of the $`2`$-simplices that are faces of the $`n+1`$ simplices in the above union, since Van Kampen’s theorem implies that the two complex $`\{S_2(\mathrm{\Delta }_k^{n+1})|\mathrm{\Delta }_j^i`$ is a face of $`\mathrm{\Delta }_k^{n+1}\}`$ is simply connected.

## 3 Proof of Theorem 1

Proof. (of Theorem 1) Let $`ϵ>0`$ and choose a filling $`\sigma :\mathrm{\Sigma }L^{\mathrm{}}(S^2,g)`$ of $`(S^2,g)`$ in the $`Fillrad(g)+ϵ`$ tubular neighborhood of $`S^2L^{\mathrm{}}(S^2,g)`$ (we will confuse $`S^2`$ with $`i(S^2)`$ since $`i`$ is an isometric embedding). By taking subdivisions we can assume that $`diam(\sigma (\mathrm{\Delta }_k^3))<ϵ`$ for each $`\mathrm{\Delta }_k^3\mathrm{\Sigma }`$. We will prove the theorem as suggested in the previous section by showing that if $`Fillrad(g)<\frac{D(g,A)}{4}`$ then we can find a continuous map $`f:\mathrm{\Sigma }S^2`$ extending the map $`\sigma |_\mathrm{\Sigma }`$. We choose $`ϵ`$ so small that $`2Fillrad(g)+3ϵ\frac{D(g,A)}{2}`$

Step1: The 0 and 1 Skeletons

We define $`f`$ on the 0-skeleton, $`S_0(\mathrm{\Sigma })`$, of $`\mathrm{\Sigma }`$ by mapping each 0 simplex $`v`$ to a point $`f(v)`$ on $`i(S^2)`$ closest to $`\sigma (v)`$, hence

$$d_{L^{\mathrm{}}(S^2)}(f(v),\sigma (v))<Fillrad(g)+ϵ.$$

In particular, $`f`$ takes 0-simplices in the boundary to the same point as $`\sigma `$ does. We note that if two vertices $`v_1`$ and $`v_2`$ are the endpoints of an edge then

$$d_{S^2}(f(v_1),f(v_2))=d_{L^{\mathrm{}}(S^2)}(f(v_1),f(v_2))$$

$$d_{L^{\mathrm{}}(S^2)}(f(v_1),\sigma (v_1))+d_{L^{\mathrm{}}(S^2)}(\sigma (v_1),\sigma (v_2))+d_{L^{\mathrm{}}(S^2)}(\sigma (v_2),f(v_2))<$$

$$<2Fillrad(g)+3ϵ\frac{D(g,A)}{2}.$$

We define $`f`$ to map each nonboundary $`\mathrm{\Delta }_i^1S_1(\mathrm{\Sigma })`$ to a minimizing geodesic between the $`f`$ image of the endpoints, hence the length $`L(\mathrm{\Delta }_i^1)`$ satisfies $`L(\mathrm{\Delta }_i^1)<\frac{D(g,A)}{2}`$. For $`\mathrm{\Delta }_i^1`$ on the boundary, we let $`f|_{\mathrm{\Delta }_i^1}=\sigma |_{\mathrm{\Delta }_i^1}`$ and hence $`Diam(f(\mathrm{\Delta }_i^1))<ϵ`$.

Step 2: The 2 skeleton

We now extend $`f`$ to $`S_2(\mathrm{\Sigma })`$. We note that $`f(\mathrm{\Delta }_j^2)Af(G_j^2)=\mathrm{}`$, for otherwise there would be a point $`xf(G_j^2)`$ such that $`A(x)f(G_j^2)`$ but this cannot happen since step 1 guarantees that the diameter of $`G_j^2`$ is less than $`D(g,A)`$.

We can thus extend $`f`$ to $`S_2(\mathrm{\Sigma })`$ in such a way that we have

$$f:\mathrm{\Delta }_j^2S^2Af(G_j^2).$$

Note that for boundary simplices, $`\mathrm{\Delta }_j^2`$, this will hold when we take $`f|_{\mathrm{\Delta }_j^2}=\sigma |_{\mathrm{\Delta }_j^2}`$ by the triangle inequality.

Step 3: The 3 skeleton

Now for every $`\mathrm{\Delta }_k^3`$ in $`\mathrm{\Sigma }`$ the previous step guarantees that

$$f:\mathrm{\Delta }_k^3S^2Af(S_1(\mathrm{\Delta }_k^3)).$$

Hence, since $`f|_{\mathrm{\Delta }_k^3}`$ misses a point, we can extend $`f`$ to $`\mathrm{\Delta }_k^3`$.

This completes the proof.

## 4 Proof of Theorem 1

Throughout this section $`S^3`$ will be endowed with a fixed Riemannian metric $`g`$ and an antipodal map $`A:S^3S^3`$.

We will proceed analogously to the proof of Theorem 1. However, in this case we will get our contradiction by finding a singular chain in $`S^3`$ whose boundary is $`\sigma `$ restricted to $`\mathrm{\Sigma }`$. We will do this one skeleton at a time, associating to each simplex $`\mathrm{\Delta }_i^j`$ a singular simplicial chain $`c_i^j`$ whose boundary $`c_i^j`$ corresponds to the already defined chain associated to $`\mathrm{\Delta }_i^j`$ (i.e. if $`\mathrm{\Delta }_i^j=\mathrm{\Sigma }_k(1)^{\alpha (i,k)}\mathrm{\Delta }_k^{j1}`$ then $`c_i^j=\mathrm{\Sigma }_k(1)^{\alpha (i,k)}c_k^{j1}`$). We do this while associating simplices $`\mathrm{\Delta }_i^j`$ of $`\mathrm{\Sigma }`$ to the chain consisting only of $`\sigma `$ applied to $`\mathrm{\Delta }_i^j`$.

Let $`ϵ>0`$ and choose a filling $`\sigma `$ of $`(S^3,g)`$ in the $`Fillrad(g)+ϵ`$ tubular neighborhood of $`S^3L^{\mathrm{}}(S^3,g)`$. By taking subdivisions we can assume that $`diam(F(\mathrm{\Delta }_l^4))<ϵ`$ for each $`\mathrm{\Delta }_l^4\mathrm{\Sigma }`$. We will prove the theorem by showing that if $`Fillrad(g)<\frac{L(g,A)}{12}`$ then we find a chain as above extending $`\sigma |_\mathrm{\Sigma }`$. We choose $`ϵ`$ so small that $`2Fillrad(g)+3ϵ<\frac{L(g,A)}{6}`$. During the rest of the argument we will associate boundary simplices to themselves without explicitly mentioning this special case. The arguments for these simplices will always follow from the other arguments along with the fact that the diameters are bounded by $`ϵ`$.

Step1: The 0 and 1 Skeletons

We define the 0-chains and 1-chains, $`c_i^0`$ and $`c_i^1`$, associated to the 0-skeleton, $`S_0(\mathrm{\Sigma })`$, and the 1-skeleton, $`S_1(\mathrm{\Sigma })`$ of $`\mathrm{\Sigma }`$ just as before; i.e. by mapping each 0 simplex to a closest point on $`S^3`$, and mapping each edge in the one skeleton to a minimizing geodesic between the endpoints. Hence the length of the image of a 1 simplex is less than $`2Fillrad(g)+3ϵ<\frac{L(g,A)}{6}`$. We can assume (by small moves) that 0-chains of distinct vertices of $`\mathrm{\Sigma }`$ are distinct and that the geodesic segments only intersect each other at endpoints.

Step 2: The 2 skeleton

Now consider a two simplex $`\mathrm{\Delta }_j^2`$ of $`\mathrm{\Sigma }`$. Let $`\overline{G}_j^2`$ be the embedded geodesic graph in $`S^3`$ which is the union of the geodesic segments that correspond to the edges of $`G_j^2`$. We know that the support of $`c_j^2`$ (i.e. a geodesic triangle) does not intersect $`A((\overline{G}_j^2))`$ since in fact $`\overline{G}_j^2`$ does not intersect $`A((\overline{G}_j^2))`$, for if so there would be an $`x\overline{G}_j^2`$ such that $`A(x)`$ is also in $`\overline{G}_j^2`$. But this can’t happen because the diameter of $`\overline{G}_j^2`$ is $`<\frac{3}{2}\frac{L(g,A)}{6}<L(g,A).`$

We claim that $`c_j^2`$ represents zero in $`H_1(S^3A(\overline{G}_k^2))`$. Alexander duality along with the fact that $`H_1(\overline{G}_j^2)`$ is generated by $`\{c_k^2|\mathrm{\Delta }_k^2`$ and $`\mathrm{\Delta }_j^2`$ lie in a common 4-simplex$`\}`$ says that we need only show that $`(c_j^2,A(c_k^2))=0`$ for each such $`c_k^2`$. So assume that $`(c_j^2,A(c_k^2))0`$. Since $`\mathrm{\Delta }_k^2`$ and $`\mathrm{\Delta }_j^2`$ lie in a common 4-simplex they share at least one vertex and hence we let $`\gamma `$ be the closed simplicial curve (of combinatorial length 6) which is just $`\mathrm{\Delta }_1^2`$ followed by $`\mathrm{\Delta }_k^2`$. We let $`\overline{\gamma }`$ be the corresponding closed piecewise geodesic curve in $`\overline{G}_j^2`$ of length $`<6\frac{L(g,A)}{6}=L(g,A)`$ (which of course does not intersect $`A(\overline{\gamma })`$). By the definition of $`L(g,A)`$ we see that $`(\overline{\gamma },A(\overline{\gamma }))`$ is zero as are $`(c_j^2,A(c_j^2))`$ and $`(c_k^2,A(c_k^2))`$. On the other hand

$$0=(\gamma ,A(\gamma ))=(c_j^2,A(c_j^2))+(c_k^2,A(c_k^2))+(c_j^2,A(c_k^2))+(c_k^2,A(c_j^2))$$

and hence $`(c_j^2,A(c_k^2))=(c_k^2,A(c_j^2))`$. But since $`A^2=id`$ and $`A`$ preserves orientation (since it is fixed point free) we have

$$(c_j^2,A(c_k^2))=(A(c_j^2),A^2(c_k^2))=(A(c_j^2),c_k^2)$$

and the claim follows.

Thus we can define a 2-chain $`c_j^2`$ whose boundary is $`c_j^2`$ and whose support is contained in $`S^3A(\overline{G}_j^2)`$.

Step 3: the 3 and 4 skeleta

Let $`\mathrm{\Delta }_i^3`$ be a 3-simplex in $`\mathrm{\Sigma }`$. For each 2-face $`\mathrm{\Delta }_k^2`$ the support of $`c_k^2`$ lies in $`S^3A(\overline{G}_k^2)S^3A(\overline{G}_i^3)`$ (since $`\overline{G}_i^3\overline{G}_k^2`$). Thus we have already defined the cycle $`c_i^3`$ in such a way that its support is in $`S^3A(\overline{G}_i^3)`$ and since by Alexander duality $`H_3(S^3A(\overline{G}_i^3))=0`$ we can find a chain $`c_i^3`$ with boundary $`c_i^3`$ whose support also lies in $`S^3A(\overline{G}_i^3)`$. Thus we can extend to the 3 skeleton.

Now for $`\mathrm{\Delta }_i^4`$ a 4-simplex of $`\mathrm{\Sigma }`$ we have now defined the cycle $`c_i^4`$ in such a way that its support is in $`S^3A(\overline{G}_i^4)`$. Since the support of $`c_i^4`$ misses a point of $`S^3`$ there is a $`c_i^4`$ whose boundary is $`c_i^4`$.

$`\mathrm{}`$


format: text

text:
# All Teleportation and Dense Coding Schemes

## 1 Introduction

Teleportation and dense coding are two processes, which stood at the beginning of modern Quantum Information Theory. They both demonstrated radically new features of quantum information as opposed to classical information, in that both would be impossible without the assistance of entangled states. Indeed, the attempt of using the properties of a classically correlated system shared by sender and receiver to improve the transmission rate of a classical channel can easily be seen to be hopeless. But this is precisely what happens in teleportation and dense coding, and dramatically so, because without entanglement assistance teleportation, i.e., the transmission of quantum information on a classical channel, would not only be less efficient, but virtually impossible.

In the original papers \[BW, BB\] the new possibilities were demonstrated by giving an explicit example, based on qubits. It was clear early on that extensions to systems with higher dimensional Hilbert spaces were possible, not only to powers of $`2`$, by running the process several times, but to any dimension $`2d<\mathrm{}`$ \[BB\].

The task set in this paper is to do this systematically, and to classify all schemes for teleportation and dense coding. There are several reasons for doing this. The first is, of course, to take these miracle machines apart and to analyze what makes them work: what is the mathematical structure one really needs to set up such a scheme? For the present author one motivation of this kind was to understand the surprising observation that each of the published teleportation schemes also works as a dense coding scheme, and conversely: sender Alice and receiver Bob merely have to swap the equipment they use. An attempt at a direct proof of this failed, and indeed, as discussed below, the statement fails in general, but is true in the special case of “tight” schemes.

The second reason for attempting a complete classification of teleportation schemes is more practical. In spite of amazing progress in recent years, experiments in quantum information processing are still quite difficult. Hence, for realizing a teleportation scheme it is useful to have a systematic overview of the options, before going on to find the one which is the easiest to implement. This also goes for approximate realizations. And in order to find feasible approximate teleportation schemes it is probably once again necessary to understand the manifold of exact realizations.

The aim of determining all schemes is not quite achieved in this paper, in two respects. Firstly, we will only look at the case when dense coding and teleportation are realized optimally with minimal resources, in the sense of Hilbert space dimensions and number of distinguishable classical signals. As in the well-known qubit case, this means that an entangled state between systems of the same dimension $`d`$ as the input systems is used, and the classical channel distinguishes $`d^2`$ signals. That is, the classical capacity of the quantum channel is exactly doubled by dense coding, and teleportation requires twice as much classical channel capacity as the quantum capacity of the channel set up by this scheme. We will call schemes with these dimension parameters tight. As mentioned above, for these dimensions the symmetry between teleportation and dense coding holds perfectly. Classifying all schemes beyond the tight case appears to be more difficult because there is too much freedom, which cannot be parametrized in a simple way (see, however, \[BD\]).

The second respect in which this paper falls short of a complete classification is that we can only reduce it to another “standard” problem, namely the construction of orthonormal bases of unitary operators with respect to the scalar product $`(A,B)d^1tr(A^{}B)`$. In the last section we provide a fairly general construction for such bases. However, even this construction has to rely on other well-known but not completely classified combinatorial designs, namely Latin squares, and complex Hadamard matrices. This suggests that a complete construction procedure for all unitary bases would be at least as difficult as a complete classification of Latin squares or Hadamard matrices, and hence hardly a promising task.

The paper is organized as follows: in Section 2 the Main Theorem is stated: an equivalence in the tight case between teleportation schemes, dense coding schemes, orthonormal unitary bases, bases of maximally entangled vectors, and so-called unitary depolarizers. Basic consequences of the Theorem are discussed. Section 3 contains the proof, divided into subsections, each devoted to some implication in the big equivalence. In writing the proof an attempt was made to include also simple steps explicitly, and to make as transparent as possible why the tightness condition is crucial. Finally, in Section 4 we present the “Shift and Multiply” construction of unitary bases, which are then classified in terms of Latin squares and Hadamard matrices.

## 2 Main result

In order to state our result we use the following notation and terminology: When $``$ is a Hilbert space, we denote by $`()`$ the space of bounded linear operators on $``$. A channel converting quantum systems with Hilbert space $`_{\mathrm{in}}`$ into systems with Hilbert space $`_{\mathrm{out}}`$ is a linear operator $`T:(_{\mathrm{out}})(_{\mathrm{in}})`$, which is completely positive \[Da, Pa\] and normalized as $`T(1\mathrm{I})=1\mathrm{I}`$. A (discrete) observable $`F`$ on $``$ over an output parameter space $`X`$ is a collection of positive operators $`F_x()`$ such that $`_xF_x=1\mathrm{I}`$. A density operator on $``$ is a positive operator with trace $`1`$. The basic probabilistic interpretation of these objects is fixed by the prescription that $`tr(\omega T(F_x))`$ is the probability to get the measuring result “$`x`$” on systems prepared according $`\omega `$, before passing through the channel $`T`$. Finally, we call a vector $`\mathrm{\Psi }`$ maximally entangled, if it is normalized, and its reduced density operator is maximally mixed, i.e., a multiple of $`1\mathrm{I}`$:

$$\mathrm{\Psi }|(A1\mathrm{I})\mathrm{\Psi }=(dim)^1tr(A).$$
(1)
Let us set up the equations describing dense coding and teleportation in this language. In both cases, the beginning of each transmission is to distribute the parts of an entangled state $`\omega `$ between sender Alice and receiver Bob. Only then Alice is given the message she is supposed to send, which is a quantum state in the case of teleportation and a classical value in case of dense coding. She codes this in a suitable way, and Bob reconstructs the original message by evaluating Alice’s signal jointly with his entangled subsystem. For dense coding, assume that $`xX`$ is the message given to Alice. She encodes it by transforming her entangled system by a channel $`T_x`$, and sending the resulting quantum system to Bob, who measures an observable $`F`$ jointly on Alice’s particle and his. The probability for getting $`y`$ as a result is then $`tr\left(\omega (T_x\mathrm{id})(F_y)\right)`$, where the “$`\mathrm{id}`$” expresses the fact that no transformation is done to Bob’s particle while Alice applies $`T_x`$ to hers. If everything works correctly, this expression has to be $`1`$ for $`x=y`$, and $`0`$ otherwise (see eq. (3)).

Let us take a similar look at teleportation. Here three quantum systems are involved: the entangled pair in state $`\omega `$, and the input system given to Alice, in state $`\rho `$. Thus the overall initial state is $`\rho \omega `$. Alice measures an observable $`F`$ on the first two factors, obtaining a result $`x`$ sent to Bob. Bob applies a transformation $`T_x`$ to his particle, and makes a final measurement of an observable $`A`$ of his choice. Thus the probability for Alice measuring $`x`$ and for Bob getting a result “yes” on $`A`$, is $`tr(\rho \omega )(F_xT_x(A))`$. Note that the tensor symbols in this equation refer to different splittings of the system ($`123`$ and $`123`$, respectively). Teleportation is successful, if the overall probability for getting $`A`$, computed by summing over all possibilities $`x`$, is the same as for an ideal channel, i.e., $`tr(\rho A)`$, as in eq. (2).

The only relationship between the Hilbert spaces involved, which this description requires, is that the input and output spaces of the teleportation line are the same, since the whole teleportation process is equivalent to the identity. In some sense the best results (minimal dimension for the Hilbert spaces carrying the entangled state, best ratio of achieved capacity to capacity used) are obtained in the special case, where all Hilbert spaces have the same dimension $`d`$, and exactly $`|X|=d^2`$ signals are distinguished. We call this the tight case, and the main Theorem refers only to this case.

###### Theorem 1

Let $``$ be a $`d`$-dimensional Hilbert space ($`d<\mathrm{}`$), and $`X`$ a set of $`d^2`$ elements. Consider the following types of objects:

1. Teleportation schemes consisting of

* a density operator $`\omega `$ on $``$
    * a collection of channels $`T_x:()()`$, $`xX`$
    * an observable $`F_x`$, $`xX`$ on $``$

such that, for all density operators $`\rho `$ on $``$, and $`A()`$:

$$\underset{xX}{}tr(\rho \omega )(F_xT_x(A))=tr\rho A.$$
(2)
2. Dense coding schemes, consisting of the same objects as a Teleportation Scheme, but satisfying, instead of (2), the equation

$$tr\left(\omega (T_x\mathrm{id})(F_y)\right)=\delta _{xy}.$$
(3)
3. Bases of maximally entangled vectors, i.e. families of maximally entangled vectors $`\mathrm{\Phi }_x`$, $`xX`$ such that

$$\mathrm{\Phi }_x|\mathrm{\Phi }_y=\delta _{xy}$$
(4)
4. Bases of unitary operators, i.e., collections of unitary operators $`U_x()`$, $`xX`$ such that

$$tr(U_x^{}U_y)=d\delta _{xy}.$$
(5)
5. Unitary depolarizers,i.e., collections of unitary operators $`U_x()`$, $`xX`$ such that for any $`A()`$:

$$\underset{x}{}U_x^{}AU_x=dtr(A)\mathrm{\hspace{0.17em}1}\mathrm{I}.$$
(6)

Then, given any object of any one of these types, one can construct an object of each of the types, using the following equations:

$`\omega `$ $`=`$ $`|\mathrm{\Omega }\mathrm{\Omega }|,\text{with }\mathrm{\Omega }\text{ maximally entangled.}`$ (7)
$`F_x`$ $`=`$ $`|\mathrm{\Phi }_x\mathrm{\Phi }_x|`$ (8)
$`T_x(A)`$ $`=`$ $`U_x^{}AU_x`$ (9)
$`\mathrm{\Phi }_x`$ $`=`$ $`(U_x1\mathrm{I})\mathrm{\Omega }.`$ (10)
The logical structure of this result is maybe slightly unusual, so we begin by giving some examples how it is used. We can use it, for example, as a construction procedure: once we are given a unitary basis, we can get from the equations (7) to (10) a teleportation scheme and a dense coding scheme. Moreover, since we could also start with these schemes, ending up with the unitary basis we are assured that every teleportation or dense coding scheme is obtained in this way, i.e., this construction is exhaustive. In particular, we learn that any tight teleportation scheme is necessarily of a very special form: the entangled state $`\omega `$ must be pure and maximally entangled, the channels $`T_x`$ must be unitarily implemented, and the observable $`F`$ must be a complete von Neumann measurement.

Another result contained in this Theorem is the amazing equivalence between (1) and (2): any teleportation scheme works as a dense coding scheme and conversely. Alice and Bob merely have to swap their equipment to convert one into the other. We must emphasize, however, that the tightness condition is absolutely crucial for this equivalence. For simplicity, we will discuss this only in the case that $`|X|=n`$ is not fixed to be $`d^2`$, leaving aside the more difficult question what kind of trade-off between resources becomes possible, when $`\omega `$ lives on $`_1_2`$, with dimensions other than $`dd`$.

The basic difference between teleportation and dense coding is that the parameters $`d`$ and $`n`$ have opposite roles: For teleportation $`d`$ describes the size of the signal to be sent, and $`n`$ describes a resource, so the problem becomes more difficult when we increase $`d`$ and decrease $`n`$. For dense coding, it is exactly the opposite. Therefore, it is easy to show that teleportation (resp. dense coding) schemes exist whenever $`nd^2`$ (resp. $`nd^2`$). In fact, for teleportation one can take $`X`$ to be a continuum, and replace the sum in the teleportation equation by an integral \[BD\], but the dense coding equation would make no sense then. The optimality of these dimension inequalities, i.e., that no teleportation (resp. dense coding) scheme exists with $`n<d^2`$ (resp. $`n>d^2`$), is also a corollary of Theorem 1. To prove it, suppose we had a teleportation scheme with $`n<d^2`$. Then we could add $`(d^2n)`$ irrelevant classical signals happening with probability zero ($`F_x=0`$), and apply the Theorem, which says that all $`F_x`$ must be non-zero after all. The same reasoning works for dense coding with the operation of throwing in a few unused Hilbert space dimensions.

Of course, our Theorem is efficient as a construction procedure for dense coding and teleportation schemes only to the extent that unitary bases can be generated. After giving the proof of the Theorem, we will therefore describe the most general construction for such bases known to us.

## 3 Proof of Theorem 1

### Proof of the Implications “3$``$4”

Implicit in the formulation of the Theorem is the claim that the equation (10) $`\mathrm{\Phi }_x=(U_x1\mathrm{I})\mathrm{\Omega }`$ not only determines $`\mathrm{\Phi }_x`$ in terms of $`U_x`$ but also, conversely, determines $`U_x`$ in terms of $`\mathrm{\Phi }_x`$. This connection is based on a general construction, by which the $`d^2`$ matrix elements of an operator $`A:`$ are identified with the $`d^2`$ components of a vector $`\mathrm{\Psi }`$. This identification depends on the choice of a maximally entangled vector $`\mathrm{\Omega }`$. By choosing appropriate orthonormal bases $`e_k`$, $`k=1,\mathrm{},d`$ in the first and second tensor factor, such a vector can be written in “Schmidt form” as

$$\mathrm{\Omega }=\frac{1}{\sqrt{d}}\underset{k}{}e_ke_k.$$
(11)
Then a one-to-one correspondence between operators $`A()`$ and $`\mathrm{\Psi }`$ is given by the equation $`e_k|Ae_{\mathrm{}}=\sqrt{d}e_ke_{\mathrm{}}|\mathrm{\Psi }`$. We will use this in the form

$$\mathrm{\Psi }=(A1\mathrm{I})\mathrm{\Omega }=(1\mathrm{I}A^T)\mathrm{\Omega },$$
(12)
where the transpose operation $`AA^T`$ is defined in the basis $`e_k`$. Then if $`A`$ and $`\mathrm{\Psi }`$ and, similarly, $`A^{}`$ and $`\mathrm{\Psi }^{}`$ are related in this way,

$$\mathrm{\Psi }|(B1\mathrm{I})\mathrm{\Psi }^{}=\frac{1}{d}tr(A^{}BA^{}),$$
(13)
for arbitrary $`B()`$. Thus $`\mathrm{\Psi }`$ is maximally entangled iff this expression (for $`A=A^{}`$) is equal to $`d^1tr(B)`$, i.e., iff $`A`$ is unitary. Moreover, setting $`B=1\mathrm{I}`$, the scalar product of vectors $`\mathrm{\Psi },\mathrm{\Psi }^{}`$ is translated to $`d^1tr(A^{}A^{})`$ in terms of $`A,A^{}`$. Taking all this together, we get the one-to one correspondence between unitary bases and bases of maximally entangled vectors, as claimed. Note, however, that this correspondence depends on the choice of the reference maximally entangled vector $`\mathrm{\Omega }`$.

### Proof of the Implications “4$``$5”

This proof is relatively straightforward, since we are talking about only one type of objects, collections of $`d^2`$ unitaries $`U_x()`$. It is, however, also a crucial step for the entire proof, since it is here that the consequences of the tightness condition are seen. We will prove this in a form, which is also needed later to establish that the state $`\omega `$ in teleportation and dense coding schemes is necessarily maximally entangled.

The basic observation concerning matching dimensions is the following.

###### Lemma 2

$`D`$ vectors $`\varphi _1,\mathrm{},\varphi _D`$ in a $`D`$-dimensional Hilbert space form an orthonormal basis if and only if

$$\underset{k=1}{\overset{D}{}}|\varphi _k\varphi _k|=1\mathrm{I}.$$
(14)
Of course, this is false when there are more vectors than the dimension of the Hilbert space. Such families of vectors are called “overcomplete”. They exist and are an interesting mathematical structure of their own. On the other hand, fewer vectors than the dimension can never satisfy eq. (14), because the rank (dimension of the range) of the operator on the left hand side is at most the number of vectors.

Proof: It is a well-known fact that eq. (14) holds for any orthonormal basis. Conversely, we find from eq. (14) that, for each $`k`$, $`|\varphi _k\varphi _k|1\mathrm{I}`$, which is the same as $`\varphi _k^21`$. On the other hand, taking the trace of (14), we get $`_k\varphi _k^2=tr(1\mathrm{I})=D`$. This is only possible, when $`\varphi _k^2=1`$ for all $`k`$. Hence the operators $`|\varphi _k\varphi _k|`$ are hermitian projections, and we can invoke the observation that hermitian projections $`p_1,p_2`$ with $`p_1+p_21\mathrm{I}`$ are necessarily orthogonal. (For a quick proof, sandwich the inequality between factors $`p_1`$, finding $`p_1+p_1p_2p_1p_1`$, i.e., $`p_1p_2p_1=(p_2p_1)^{}(p_2p_1)0`$, and hence $`p_2p_1=0`$).

We now apply this Lemma to a collection of $`D=d^2`$ operators in $`()`$, where this space is considered as a Hilbert space with a suitable scalar product.

###### Proposition 3

Consider $`d^2`$ operators $`K_1,\mathrm{},K_{d^2}`$ on a $`d`$-dimensional Hilbert space $``$, and let $`R>0`$ be an invertible operator on $``$.
Then the following conditions are equivalent

1. $`tr(K_x^{}R^1K_y)=\delta _{xy}`$, for $`x,y=1,\mathrm{},d^2`$
2. $`_xK_x^{}CK_x=tr(RC)1\mathrm{I}`$ for all $`C()`$.

Proof: Let us define a scalar product $`|_R`$ on $`()`$ by

$$A|B_R=tr(A^{}R^1B).$$
(15)
Since $`R`$ is positive and invertible, this is indeed a scalar product, satisfying $`A|A_R=0`$ only for $`A=0`$. Condition 1 then simply says that the $`K_x`$ are an orthonormal basis. By the previous Lemma this is equivalent to the completeness relation (14), so all we have to do is to show that this relation, adapted to the special scalar product at hand, is equivalent to Condition 2 of the present Lemma. The completeness relation is that, for any $`A,B()`$,

$$A|B_R=\underset{x}{}A|K_x_RK_x|B_R.$$
($``$)
It suffices to evaluate this on rank one operators $`A,B()`$, since these span the whole space. We take $`A=|\varphi _1\varphi _2|`$ and $`B=|\psi _1\psi _2|`$. Then the left hand side of equation ($``$) becomes

$$\varphi _1|R^1\psi _1\psi _2|\varphi _2,$$
($``$LHS)
whereas the right hand side is

$$\underset{x}{}\varphi _1|R^1K_x\varphi _2\psi _2|K_x^{}R^1\psi _1=\psi _2|M\varphi _2,$$
($``$RHS)
with

$$M=\underset{x}{}K_x^{}R^1|\psi _1\varphi _1|R^1K_x\underset{x}{}K_x^{}CK_x$$

where we have interchanged the two factors in each term, and introduced the abbreviation $`C`$. Since ($``$LHS)=($``$RHS) for every $`\psi _2,\varphi _2`$, we find $`M=\varphi _1|R^1\psi _1\mathrm{\hspace{0.33em}1}\mathrm{I}`$. The factor is readily identified as

$`\varphi _1|R^1\psi _1=tr(RC)`$. Since operators of the form $`C`$ span $`()`$, the completeness relation thus becomes equivalent to $`_xK_x^{}CK_x=tr(RC)1\mathrm{I}`$ for all $`C`$, which completes the proof.

The special case of this Proposition, where each $`K_x`$ is unitary and $`R=\frac{1}{d}1\mathrm{I}`$, is exactly the relationship between items 4 and 5 of Theorem 1. However, there is another consequence needed later on:

###### Corollary 4

Let $`U_1,\mathrm{},U_{d^2}()`$ be unitaries in a $`d`$-dimensional Hilbert space $``$, and $`\rho `$ a density operator such that $`tr(U_x^{}\rho U_y)=\delta _{xy}`$. Then $`\rho =d^11\mathrm{I}`$.

Proof: Since the $`U_x`$ are an orthonormal set whose cardinality is the dimension, there can be no null vectors of this scalar product, i.e., $`tr(A^{}\rho A)=0`$ implies $`A=0`$. Hence $`\rho `$ is invertible, and we can apply the previous Proposition with $`R=\rho ^1`$, finding that $`_xU_x^{}AU_x=tr(\rho ^1A)1\mathrm{I}`$. The trace of this equation is $`d^2tr(A)=dtr(\rho ^1A)`$. This holds for all $`A`$, i.e., $`\rho ^1=d1\mathrm{I}`$.

### Proof of “(3 or 4)$``$(1 and 2)”

Suppose now we are given either a basis of unitary operators or of maximally entangled vectors. Then we can choose a maximally entangled vector $`\mathrm{\Omega }`$ and use equation (10) as in in the proof of “3$``$4” to define the other kind of basis. Equations (8) and (9) then become explicit definitions of the observable $`F_x`$ and the transformations $`T_x`$, respectively, so all the objects needed for a teleportation or dense coding scheme are defined, and we only need to verify that equations (2) and (3) are indeed satisfied.

In the teleportation equation an expectation value is generated between a state on the first and an observable on the third factor of a triple tensor product. This is a consequence of a similar “teleportation equation” on the level of vectors, which we now state. For later use we prove a certain converse at the same time.

###### Lemma 5

Let $`\mathrm{\Omega }^d^d`$ be the maximally entangled vector $`\mathrm{\Omega }=d^{1/2}_ke_ke_k`$, where $`e_k`$, $`k=1,\mathrm{},d`$ is the standard basis of $`^d`$. Let $`M(^d)`$, and $`\mu `$. Then the equation

$$\varphi \mathrm{\Omega }|(1\mathrm{I}M1\mathrm{I})\mathrm{\Omega }\psi =\mu \varphi |\psi $$

holds for all $`\varphi ,\psi ^d`$, if and only if $`M=d\mu 1\mathrm{I}`$.

Proof: Inserting the sum defining $`\mathrm{\Omega }`$ we get

$`\varphi \mathrm{\Omega }|(1\mathrm{I}M1\mathrm{I})\mathrm{\Omega }\psi =`$
$`=`$ $`{\displaystyle \frac{1}{d}}{\displaystyle \underset{k\mathrm{}}{}}\varphi e_ke_k|(1\mathrm{I}M1\mathrm{I})e_{\mathrm{}}e_{\mathrm{}}\psi `$
$`=`$ $`{\displaystyle \frac{1}{d}}{\displaystyle \underset{k\mathrm{}}{}}\varphi |e_{\mathrm{}}e_k|Me_{\mathrm{}}e_k|\psi ={\displaystyle \frac{1}{d}}\varphi |M^T\psi ,`$
which is equal to $`\mu \varphi |\psi `$ for all $`\varphi ,\psi `$ iff $`M^T=d\mu 1\mathrm{I}`$.

Consider now the term with index $`xX`$ in the teleportation equation (2), with $`F_x`$ and $`T_x`$ defined via equations (8), (9), and (10). Without loss of generality we set $`\rho =|\varphi _1\varphi _2|`$, $`A=|\psi _1\psi _2|`$. Then

$$\mathrm{term}_x=\varphi _2\mathrm{\Omega }|\mathrm{\Phi }_xU_x^{}\psi _1\mathrm{\Phi }_xU_x^{}\psi _2|\varphi _1\mathrm{\Omega }.$$

The first scalar product can be rewritten by substituting $`\mathrm{\Phi }_x`$ from equation (10), using equation (12):

$`\varphi _2\mathrm{\Omega }|\mathrm{\Phi }_xU_x^{}\psi _1`$ $`=`$ $`\varphi _2((1\mathrm{I}U_x)\mathrm{\Omega })|((U_x1\mathrm{I})\mathrm{\Omega })\psi _1`$
$`=`$ $`\varphi _2((U_x^T1\mathrm{I})\mathrm{\Omega })|((1\mathrm{I}U_x^T)\mathrm{\Omega })\psi _1`$
$`=`$ $`(1\mathrm{I}U_x^T1\mathrm{I})\varphi _2\mathrm{\Omega }|(1\mathrm{I}U_x^T1\mathrm{I})\mathrm{\Omega }\psi _1`$
$`=`$ $`\varphi _2\mathrm{\Omega }|\mathrm{\Omega }\psi _1={\displaystyle \frac{1}{d}}\varphi _2|\psi _1,`$
where at the last equation we used Lemma 5 with $`\mu =1/d`$. Together with a similar computation for the second scalar product, we get $`\mathrm{term}_x=d^2\varphi _2|\psi _1\psi _2|\varphi _1=d^2tr(\rho A)`$, and equation (2) follows by summing over $`d^2`$ equal terms.

Similarly, for the dense coding equation (3) we get

$$tr\left(\omega (T_x\mathrm{id})(F_y)\right)=\mathrm{\Omega }|(U_x^{}1\mathrm{I})\mathrm{\Phi }_y\mathrm{\Phi }_y|(U_x1\mathrm{I})\mathrm{\Omega },$$

i.e., the absolute square of the scalar product

$$\mathrm{\Omega }|(U_x^{}1\mathrm{I})\mathrm{\Phi }_y=\mathrm{\Omega }|(U_x^{}U_y1\mathrm{I})\mathrm{\Omega }=\frac{1}{d}tr(U_x^{}U_y)=\delta _{xy},$$

where we have used, in turn equation (10), the maximal entangledness of $`\mathrm{\Omega }`$ (see equation (1)), and the orthogonality of the $`U_x`$. This completes the proof of the dense coding property.

### Proof of the Implications “2 $``$ Rest”

Let us now assume that a dense coding scheme is given. We have to conclude that it is of the special form given in equations (710).

Note first that if $`\omega =_\alpha \lambda _\alpha \omega _\alpha `$ ($`\lambda _\alpha >0`$) is a mixture of states satisfying the teleportation equation, then every $`\omega _\alpha `$ also satisfies it. Hence the assumption is also satisfied for each pure component $`\omega _\alpha `$, and we can first analyze the problem assuming $`\omega `$ to be pure. In order to show that $`\omega `$ indeed is pure, we only have to verify that the given $`F,T`$ are consistent only with one pure state. So for the moment we will assume that $`\omega =|\mathrm{\Omega }\mathrm{\Omega }|`$ is pure.

The next step is a simple general observation on the coding of classical information on quantum channels, which we isolate in a Lemma.

###### Lemma 6

Let $`𝒦`$ be a $`D`$-dimensional Hilbert space, and $`\sigma _x,F_x(𝒦)`$, for $`xX`$, a set with $`D`$ elements. Suppose that each $`\sigma _x`$ is a density operator, $`F`$ is an observable, and $`tr(\sigma _xF_y)=\delta _{xy}`$, for $`x,y=1,\mathrm{},D`$.
Then there is an orthonormal basis $`\mathrm{\Phi }_x`$ such that

$$\sigma _x=F_x=|\mathrm{\Phi }_x\mathrm{\Phi }_x|.$$

Proof: Let $`\mathrm{\Phi }_x`$ be one of the normalized eigenvectors of $`\sigma _x`$ with non-zero eigenvalue. Then since $`F_x1\mathrm{I}`$, and $`\mathrm{\Phi }_x|F_x\mathrm{\Phi }_x=1`$, $`\mathrm{\Phi }_x`$ must also be an eigenvector of $`F_x`$ with eigenvalue $`1`$. Similarly, for any $`yx`$ the $`F_x0`$, and the normalization $`_xF_x=1\mathrm{I}`$ forces $`F_y\mathrm{\Phi }_x=0`$. Hence the $`\mathrm{\Phi }_x`$ are orthonormal, and since their number is the dimension of the space, they must be a basis. Consequently we have jointly diagonalized the $`F_x`$ and the $`\sigma _x`$, with eigenvalues either $`0`$ or $`1`$.

We apply this Lemma with $`D=d^2`$ and $`\sigma _x`$ the state after application of $`T_x`$ to the first factor, i.e., $`tr(\sigma _xA)=tr(\omega (T_x\mathrm{id})(A))`$. This proves equation (8), although it remains to be seen that each $`\mathrm{\Phi }_x`$ is maximally entangled.

Since the $`\sigma _x`$ form a maximal set of pure states, there cannot be a non-zero projection $`P`$ such that, for all $`xX`$,

$`0`$ $`=`$ $`tr(\sigma _x(1\mathrm{I}P))=tr(\omega (T_x\mathrm{id})(1\mathrm{I}P))`$
$`=`$ $`tr(\omega (1\mathrm{I}P))=\mathrm{\Omega }|(1\mathrm{I}P)\mathrm{\Omega }.`$
Hence $`\mathrm{\Omega }`$ must have full Schmidt rank. We will need the consequence that the equation $`(A1\mathrm{I})\mathrm{\Omega }=(A^{}1\mathrm{I})\mathrm{\Omega }`$ implies $`A=A^{}`$.

Let $`T_x(A)=_\alpha K_{x,\alpha }^{}AK_{x,\alpha }`$ be the Kraus decomposition of $`T_x`$. Then the teleportation equation is

$$\underset{\alpha }{}|\mathrm{\Omega }|(K_{x,\alpha }^{}1\mathrm{I})\mathrm{\Phi }_y|^2=\delta _{xy}.$$

Therefore, $`(K_{x,\alpha }1\mathrm{I})\mathrm{\Omega }|\mathrm{\Phi }_y=0`$ for all $`yx`$, and for every $`x`$ there must be constants $`c_\alpha `$ such that

$$(K_{x,\alpha }1\mathrm{I})\mathrm{\Omega }=c_\alpha \mathrm{\Phi }_x.$$
(16)
Since $`\mathrm{\Omega }`$ has full Schmidt rank, this implies that all $`K_{x,\alpha }`$ are proportional to each other, i.e., that $`T_x`$ can be written with a single Kraus summand. Of course, the corresponding $`K_xU_x`$ must be unitary, and since both sides are normalized, equation (16) $`\mathrm{\Phi }_x=(U_x1\mathrm{I})\mathrm{\Omega }`$, possibly after fixing suitable phase factors (which influence neither $`T_x`$ nor $`F_x`$).

The orthonormality of the $`\mathrm{\Phi }_x`$ translates into $`tr(\rho U_x^{}U_y)=\delta _{xy}`$, where $`\rho `$ is the reduced density operator of $`\omega `$. But then Corollary 4 shows that $`\rho `$ must be a multiple of the identity, i.e., $`\mathrm{\Omega }`$ and each $`\mathrm{\Phi }_x`$ is maximally entangled.

Finally, we have to complete the argument for the purity of $`\omega `$ by showing that only one pure state is consistent with the other data $`T,F`$, encoded in $`U_x`$. But this is obvious from the explicit expression $`\mathrm{\Omega }=(U_x^{}1\mathrm{I})\mathrm{\Phi }_x`$.

### Proof of the Implications “1 $``$ Rest”

Let us now assume that a teleportation scheme is given. We have to conclude that it is of the special form given in equations (710).

The crucial input for this proof is the principle that in quantum mechanics there is no measurement without perturbation. It enters in the following form, a corollary of the so-called Radon-Nikodym Theorem for completely positive maps. We state it here as a Lemma.

###### Lemma 7

Let $``$ be a finite dimensional Hilbert space, and let $`T_\alpha :()()`$ be completely positive maps such that $`_\alpha T_\alpha =\mathrm{id}`$. Then there are positive numbers $`t_\alpha `$ such that $`T_\alpha =t_\alpha \mathrm{id}`$.

Proof: For readers less familiar with dilation theory of cp-maps we include a quick proof based on the Kraus decomposition $`T(A)=_\beta K_\beta ^{}AK_\beta `$, which exists for every completely positive map. Note that by decomposing each $`T_\alpha `$ in Kraus form, we get a finer decomposition of $`\mathrm{id}`$, so we may as well prove the Lemma for the case that each $`T_\alpha `$ is of the form $`T_\alpha (A)=K_\alpha ^{}AK_\alpha `$. With $`A=|\psi \psi |`$,

$$|K_\alpha ^{}\psi K_\alpha ^{}\psi |\underset{\alpha }{}|K_\alpha ^{}\psi \psi |K_\alpha =|\psi \psi |.$$

Hence $`K_\alpha ^{}\psi =\lambda (\psi )\psi `$, with a factor $`\lambda (\psi )`$. But then every vector $`\psi `$ is an eigenvector of the linear operator $`K_\alpha ^{}`$, which is only possible, if $`K_\alpha ^{}`$ is a multiple of the identity.

A collection of completely positive maps adding up to a normalized one should be understood as an “instrument” in the terminology of Davies \[Da\], i.e., a device which produces classical measurement results “$`k`$”, such that the probability for obtaining this result and a response to a subsequent measurement $`F`$ on an input state $`\rho `$ is $`tr(\rho T_k(F)))`$. The channel $`_kT_k`$ then describes the overall state change, when the measuring results are ignored. In this language the hypothesis of the Lemma says that there is no overall state change through the device, i.e., “no perturbation” of the system. The conclusion is that in that case the output probabilities are $`t_k`$, and independent of the input state, i.e., no information about the system is obtained.

As a first application, we conclude exactly as in the previous subsection that each convex component of the state $`\omega `$ again satisfies the teleportation equation. Hence we can once more assume that $`\omega =|\mathrm{\Omega }\mathrm{\Omega }|`$ is a pure state. The argument that $`\mathrm{\Omega }`$ is then uniquely determined by the other data, and hence that $`\omega `$ is pure is the same as in the dense coding case.

Clearly, this kind of argument is also useful for decompositions of $`T_x`$ or $`F_x`$ into sums of (completely) positive terms. To do this systematically, fix a maximally entangled unit vector $`\mathrm{\Xi }`$, so that vectors in $``$ become expressed as $`\mathrm{\Phi }=(A1\mathrm{I})\mathrm{\Xi }`$ for a uniquely determined operator $`A`$ (see equation (12)). In particular, we can write $`\mathrm{\Omega }=(W1\mathrm{I})\mathrm{\Xi }`$, and the Kraus decomposition and spectral decomposition of each $`F_x`$ in the form

$`T_x(A)`$ $`=`$ $`{\displaystyle \underset{\alpha }{}}K_{x,\alpha }^{}AK_{x,\alpha }`$ (17)
$`F_x`$ $`=`$ $`{\displaystyle \underset{\beta }{}}(A_{x,\beta }1\mathrm{I})|\mathrm{\Xi }\mathrm{\Xi }|(A_{x,\beta }1\mathrm{I})^{}.`$ (18)
Inserting this into the teleportation equation (2) we find a sum over $`x,\alpha ,\beta `$, in which each term represents a completely positive operator, and which sum up to the identity. Hence by Lemma 7, each term has to be multiple of the identity, $`\stackrel{~}{\mu }_{x,\alpha ,\beta }\mathrm{id}`$, say. This can be written in terms of scalar products, if we take $`\rho =|\varphi _1\varphi _2|`$ and $`A=|\psi _1\psi _2|`$:

$`\stackrel{~}{\mu }_{x,\alpha ,\beta }tr(\rho A)`$ $`=`$ $`\stackrel{~}{\mu }_{x,\alpha ,\beta }\varphi _2,\psi _1\psi _2,\varphi _1`$
$`=`$ $`\varphi _2\mathrm{\Omega },(A_{x,\beta }1\mathrm{I}K_{x,\alpha }^{})\mathrm{\Xi }\psi _1`$
$`\mathrm{\Xi }\psi _2,(A_{x,\beta }^{}1\mathrm{I}K_{x,\alpha })\varphi _1\mathrm{\Omega }.`$
Note that the two scalar products on the right hand side are complex conjugates of each other apart from a swapping of the arguments $`(\varphi _2,\psi _1)`$ and $`(\psi _2,\varphi _1)`$, which exactly matches the variable pairing on the left hand side. Since the equation is to hold for arbitrary vectors $`\varphi _1,\varphi _2,\psi _1,\psi _2`$, we can hold one pair fixed and find that

$$\varphi _2\mathrm{\Omega },(A_{x,\beta }1\mathrm{I}K_{x,\alpha }^{})\mathrm{\Xi }\psi _1=\mu _{x,\alpha ,\beta }\varphi _2,\psi _1,$$
(19)
where $`\mu _{x,\alpha ,\beta }`$ is a factor determined in terms of $`\stackrel{~}{\mu }`$, and the scalar products involving $`(\psi _2,\varphi _1)`$. With $`\mathrm{\Omega }=(W1\mathrm{I})\mathrm{\Xi }`$, and equation (12) we get

$`\varphi _2\mathrm{\Omega },(A_{x,\beta }1\mathrm{I}K_{x,\alpha }^{})\mathrm{\Xi }\psi _1`$
$`=`$ $`\varphi _2(1\mathrm{I}K_{x,\alpha })\mathrm{\Xi },(1\mathrm{I}W^{}1\mathrm{I})\left((A_{x,\beta }1\mathrm{I})\mathrm{\Xi }\psi _1\right)`$
$`=`$ $`\varphi _2(K_{x,\alpha }^T1\mathrm{I})\mathrm{\Xi },(1\mathrm{I}W^{}1\mathrm{I})\left((1\mathrm{I}A_{x,\beta }^T)\mathrm{\Xi }\psi _1\right)`$
$`=`$ $`\varphi _2\mathrm{\Xi },(1\mathrm{I}\overline{K_{x,\alpha }}W^{}A_{x,\beta }^T1\mathrm{I})\mathrm{\Xi }\psi _1`$
$``$ $`\mu _{x,\alpha ,\beta }\varphi _2,\psi _1,`$
where we have used the notation $`\overline{K}=(K^{})^T`$ for the matrix element-wise complex conjugation in the Schmidt basis belonging to the maximally entangled state $`\mathrm{\Xi }`$. Since the above equation holds for all $`\varphi _2`$ and $`\psi _1`$, Lemma 5 implies that

$$\overline{K_{x,\alpha }}W^{}A_{x,\beta }^T=d\mu _{x,\alpha ,\beta }1\mathrm{I},$$
(20)
for all $`x,\alpha ,\beta `$.

Let us say that a label $`xX`$ contributes to teleportation, if the corresponding term in the teleportation equation does not vanish for all $`\rho `$ and $`A`$. This is equivalent to saying that for some $`\alpha ,\beta `$ the factor $`\mu _{x,\alpha ,\beta }`$ is non-zero. For such triples $`(x,\alpha ,\beta )`$ all three operators on the left hand side of equation (20) have to be invertible.

Now since there has to be at least one contributing label, $`W`$ has to be non-singular, which means that $`\mathrm{\Omega }`$ has full Schmidt rank. Equivalently, the reduced density operator $`\omega _1`$ for the first factor has no zero eigenvalues. From this we conclude that the non-contributing labels are precisely those for which $`F_x=0`$. Indeed, we may set $`A=\rho =1\mathrm{I}`$, and use the normalization of $`T_x`$ to find

$$0=tr\left((1\mathrm{I}\omega )(F_x1\mathrm{I})\right)=tr\left((1\mathrm{I}\omega _1)F_x\right)$$

Since $`F_x0`$, and $`1\mathrm{I}\omega _1`$ has only strictly positive eigenvalues, this implies $`F_x=0`$.

Now let $`x`$ be a contributing index, and choose some triple $`(x,\alpha ,\beta )`$ with $`\mu _{x,\alpha ,\beta }0`$. If we now look at equation (20) for triples $`(x,\alpha ^{},\beta )`$ with arbitrary $`\alpha ^{}`$, we get $`\overline{K_{x,\alpha ^{}}}=(\mu _{x,\alpha ^{},\beta }/\mu _{x,\alpha ,\beta })\overline{K_{x,\alpha }}`$, i.e., all Kraus operators of $`T_x`$ are proportional, and hence $`T_x`$ can be written with a single Kraus summand, $`T_x(A)=U_x^{}AU_x`$, with a unitary $`U_x`$.

Similarly, we find that all $`A_{x,\beta ^{}}`$ are proportional, which means that $`F_x=|\mathrm{\Phi }_x\mathrm{\Phi }_x|`$ with $`\mathrm{\Phi }_x=(A_x1\mathrm{I})\mathrm{\Xi }`$.

We can now apply Lemma 2 to these vectors $`\mathrm{\Phi }_x`$, setting $`\mathrm{\Phi }_x=0`$ for non-contributing labels. The conclusion is that the $`\mathrm{\Phi }_x`$ are an orthonormal basis. In particular, all indices do contribute after all.

Equation (20) and the unitarity of $`U_x`$ allow us to express $`A_x`$ in terms of $`U_x`$:

$$A_x=d\mu _xU_x\overline{W}^1$$
(21)
Orthonormality of the $`\mathrm{\Phi }_x`$ becomes

$$\delta _{xy}=\frac{1}{d}tr(A_x^{}A_y)=d\overline{\mu _x}\mu _ytr(U_y\overline{W}^1(\overline{W}^1)^{}U_x^{}).$$
(22)
For $`x=y`$ we find that $`|\mu _x|^2`$ is independent of $`x`$, hence the operators $`(\overline{\mu _x}/|\mu _x|)U_x^{}`$ are unitary, and satisfy the hypothesis of Corollary 4 with $`\rho `$ a positive multiple of $`\overline{W}^1(\overline{W}^1)^{}`$. Hence this operator is a multiple of the identity, $`W`$ is unitary up to a factor, and $`\mathrm{\Omega }=(W1\mathrm{I})\mathrm{\Xi }`$ is maximally entangled. Moreover, we see from equation (22) and the $`U_x`$ form a unitary basis.

Since $`\mathrm{\Xi }`$ was an arbitrary maximally entangled vector, we may just as well take $`\mathrm{\Xi }=\mathrm{\Omega }`$, so equation (21) holds with $`W=1\mathrm{I}`$. Hence, $`\mathrm{\Phi }_x=c(U_x1\mathrm{I})\mathrm{\Omega }`$, where $`c`$ is a factor which has to be of modulus $`1`$, because $`\mathrm{\Omega }`$ and $`\mathrm{\Phi }_x`$ are normalized, and $`U_x`$ is unitary, and which can be chosen to be $`1`$ by adjusting the phase of $`\mathrm{\Phi }_x`$. This completes the proof.

## 4 Constructing bases of unitaries

It is not a priori clear that bases of unitary operators should exist in any dimension. Indeed, the system equation (5) of equations is formally overdetermined, according to the following rough dimension count. The variables in this system are the unitaries $`U_x`$, each of which we can take in the $`(d^21)`$-dimensional manifold $`SU_d`$, i.e., with $`det\left(U_x\right)=1`$, by fixing a phase factor. Since the transformations $`U_xV_1U_xV_2`$, for arbitrary $`V_1,V_2SU_d`$ leave the set of solutions invariant, we may fix $`U_1=1\mathrm{I}`$, and take $`U_2`$ diagonal without loss of generality. This reduces the number of variables to $`(d1)+(d^22)(d^21)`$. On the other hand, orthogonality introduces one complex constraint for every pair $`xy`$. None of these is trivially satisfied due to the special choices we made, so we have to take $`d^2(d^21)`$ constraints into account. This leaves, formally,

$$\text{\#variables-\#equations}=(d1)(2d+1)<0.$$

Of course, we know that this count is somehow too crude, because, after all, many inequivalent unitary bases are constructed below. But it is not so easy to spot the dependences among the constraints. Note also that the dimension count is essentially the same for bases orthogonal with respect to a weight $`\rho d^11\mathrm{I}`$, but in that case Corollary 4 shows that there is no solution at all.

In order to describe the best known construction for unitary bases \[VW\], let us introduce some terminology. We say that a (single) unitary matrix is of shift and multiply type, if it is the product of a permutation operator and a diagonal unitary. In other words, every row or column contains $`(d1)`$ zero entries, and one entry of modulus $`1`$. The bases we will construct not only have the property that each element is of this type, but also that the $`d^2`$ values for $`x`$ can be split into $`d`$ options for “shift” and $`d`$ options for “multiply”.

###### Definiton 8

A shift and multiply basis of unitary matrices in $`^d`$ is a collection of $`d^2`$ unitary operators $`U_{ij}`$, $`i,jI_d\{1,\mathrm{},d\}`$, satisfying the orthogonality relation $`tr(U_{ij}^{}U_k\mathrm{})=d\delta _{ik}\delta _j\mathrm{}`$, and acting on the basis vectors $`|k`$ as

$$U_{ij}|k=H_{ik}^j|\lambda (j,k),$$
(23)
where the $`H_{ik}^j`$ are complex numbers, and $`\lambda :I_d\times I_dI_d`$.

###### Proposition 9

The parameters and $`\lambda :I_d\times I_dI_d`$ define a shift and multiply basis of unitary matrices if and only if the following two conditions are satisfied

1. Each $`H^j`$ is a Hadamard matrix, i.e. $`|H_{ik}^j|=1`$ for all $`i,k`$, and $`H^j(H^j)^{}=d\mathrm{\hspace{0.33em}1}\mathrm{I}`$.
2. $`\lambda `$ is a Latin square, i.e., the maps $`k\lambda (k,\mathrm{})`$ and $`k\lambda (\mathrm{},k)`$ are injective for every $`\mathrm{}`$.

Proof: For $`U_{ij}`$ to be unitary, it is necessary and sufficient that the $`H_{ik}^j`$ are phases, and that $`k\lambda (j,k)`$ is injective (hence bijective) for every $`j`$. For the orthogonality we have to evaluate

$$tr(U_{ij}^{}U_{i^{}j^{}})=\underset{k}{}\overline{H_{ik}^j}H_{i^{}k}^j^{}\lambda (j,k)|\lambda (j^{},k).$$

We consider first the case $`j=j^{}`$. Then the scalar products in the sum are all equal to $`1`$, and equating this expression to $`\delta _{ii^{}}`$ we find that $`H^j`$ is Hadamard.

Now let $`jj^{}`$, and consider the “coincidence set” $`C=\{k\lambda (j,k)=\lambda (j^{},k)\}`$. Then orthogonality requires, for every $`i,i^{}`$, that

$$0=\underset{kC}{}\overline{H_{ik}^j}H_{i^{}k}^j^{}=\underset{k=1}{\overset{d}{}}H_{i^{}k}^j^{}\chi _C(k)(H^j)_{ki}=(H^j^{}\chi _CH^j)_{i^{}i},$$
(24)
where $`\chi _C(k)=1`$ for $`kC`$, and zero otherwise, and in the last line $`\chi _C`$ denotes the projection $`\chi _C|k=\chi _C(k)|k`$. But since $`H^j^{}`$ and $`H^j`$ are Hadamard, and in particular invertible, this implies $`\chi _C=0`$. Hence $`C`$ is empty, and the second injectivity of $`\lambda `$ is proved.

In order to construct unitary bases of this form, we must now construct Hadamard matrices and Latin squares of the appropriate dimension. For both of these tasks there is a rich literature, and below we will give a brief summary on what is known for each.

It is useful to note that each of the structures ‘unitary bases’, ‘Hadamard matrices’, and ‘Latin squares’ has a natural notion of equivalence, and to some extent these equivalences are related. We call two unitary bases $`U,U^{}`$ equivalent, if $`U_x^{}=V_1U_x^{}V_2`$, for some unitaries $`V_1,V_2`$, and a re-labelling $`xx^{}`$. Hadamard matrices are called equivalent, if one is obtained from the other by permuting rows or columns, or multiplying rows or columns with phases. Finally, a Latin square $`\lambda :I_d\times I_dI_d`$ is equivalent to any other obtained by applying a permutation on each of the three copies of $`I_d`$ involved. In each case there are also discrete transformations, such as transposition or complex conjugation (where applicable). It should be noted that replacing each $`H^j`$ by an equivalent one, typically only leads to an equivalent unitary basis, if the equivalence operation is the same for each $`j`$. With $`j`$-dependent equivalence transformations it is possible to construct inequivalent unitary bases in $`d=3`$, although in this dimension there is only one Hadamard matrix and only one Latin square – up to equivalence. Of course, in $`d=2`$ all three structures, including the unitary bases are unique up to equivalence \[VW\]. The unique unitary basis is then given by the three Pauli matrices and the identity and, of course generates via the Theorem 1, the usual two qubit examples of teleportation and dense coding.

For each of the three structures we furthermore have an obvious notion of tensor product, allowing the construction of a unitary basis (resp. a Hadamard matrix, or Latin square) in dimension $`d=d_1d_2`$, if counterparts in dimension $`d_1`$ and dimension $`d_2`$ are given.

In order to show that unitary bases exist in any dimension it is easiest to use group theory based constructions: the Latin square can be taken as the multiplication table of any group of order $`d`$, for example the cyclic group. The Hadamard matrix can be taken as the matrix implementing the Fourier transform on an abelian group of order $`d`$, the standard example being given once again by the cyclic group of order $`d`$. Thus $`H_k\mathrm{}=\mathrm{exp}(\frac{2\pi i}{d}k\mathrm{})`$, where $`k`$ and $`\mathrm{}`$ are taken modulo $`d`$. If we combine these data into a unitary basis we get an instance of what we propose to call a unitary basis of group type (“nice error basis” in \[Kn\]). These are orthonormal unitary bases with the additional property that the operator product of any two elements is a third, up to a phase. That is to say, the index set $`X`$ is a group, and

$$U_xU_y=\mu (x,y)U_{xy},$$
(25)
with $`|\mu (x,y)|=1`$. In the special case of an abelian group $`X`$ this is a discrete version of Weyl systems of unitary operators, named after their continuous variable counterpart, well-known from quantum optics and non-relativistic “phase space” quantum mechanics.

Latin squares are not completely classified, nor does there seem to be a realistic hope to do so. A standard work on the subject is \[DK\], a useful net resource is \[Ri\]. Counts of squares are usually done for “normalized squares”, in which the first row and column are in natural order, thus eliminating some trivial freedom. In $`d=5`$ Euler counted $`56`$ of these, but only $`2`$ are inequivalent, because the symbols themselves can also be permuted. Counts of normalized squares have now gone all the way up to $`d=10`$, but are no longer done by hand (there are roughly $`7.5\times 10^{24}`$ \[MR\]). It is also clear from these numbers that group based constructions exhaust only a tiny fraction of the possible unitary bases.

Hadamard matrices are also a standard subject in coding theory. However, usually only the real case (orthogonal matrices with entries $`\pm 1`$) is considered. It is easy to see that real Hadamard matrices exist only in dimension two and multiples of four. Again, the possibilities for such designs by far exceed the group based possibilities (the characters of an abelian group are real only if $`d=2^n`$). A standard reference is \[Ag\].

For complex Hadamard matrices the Fourier matrices show that there is no constraint on dimension. The uniqueness in $`d=3`$ is easy to get. The general form in $`d=4`$ is, up to equivalence

$$\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& 1& 1\\ 1& 1& u& u\\ 1& 1& u& u\end{array}\right),$$
(26)
where $`u`$ is an arbitrary phase. For $`u=1`$ this is equivalent to the Fourier matrix of “Klein’s Four Group”, the product of two copies of the two-element group, and for $`u=i`$ it is equivalent to the Fourier matrix of the cyclic group. The possibility of embedding the cyclic group Fourier matrix into a higher dimensional manifold can be generalized to arbitrary composite numbers $`d=pq`$: whenever $`V_k\mathrm{}`$ is a matrix of phases satisfying the periodicity conditions $`V_{k,\mathrm{}}=V_{k+p,\mathrm{}}=V_{k,\mathrm{}+q}`$, we get a Hadamard matrix as

$$H_k\mathrm{}=V_k\mathrm{}\mathrm{exp}\left(\frac{2\pi i}{d}k\mathrm{}\right).$$
(27)
One might conjecture from this that for prime orders $`d`$ the Hadamard matrix is unique. This problem was discussed by Haagerup \[Ha\] on the basis of a completely different motivation (theory of von Neumann algebras). There it is shown that $`d=5`$ there is uniqueness, but for $`d=7`$ there are at least $`5`$ solutions. For some primes, uncountably many inequivalent Hadamard matrices are known.


text:
# Accretion by Galaxies

## 1. Introduction

The Milky Way is an extremely typical galaxy in the sense that most of the luminosity in the Universe comes from similar systems. Therefore, indications that the Milky Way is accreting at a significant rate would imply that accretion is an important phenomenon within the Universe at large.

Several observations suggest that material is falling into the Milky Way. First and foremost, our nearest large neighbour, M31, is approaching us at $`140\mathrm{km}\mathrm{s}^1`$. Second, the so-called ‘high-velocity clouds’ have, on the average, negative line-of-sight velocities. Third, the Magellanic Clouds are on an orbit that must be decaying through dynamical friction, and I shall argue that the orbit of the Sagittarius Dwarf Galaxy is in a still more advanced state of decay. Fourth, beyond $`R_0`$ the Galactic disk has a complex warped structure, and the most plausible explanation of this phenomenon invokes infall as the driver. Fifth, at a given radius the ISM appears to vary significantly in metallicity from place to place, and this phenomenon is most naturally explained by persistent accretion of low-metallicity material.

In this talk I shall review each of these lines of evidence in turn.

## 2. Collapse of the Local Group

The luminosity of the Local Group is dominated by the Milky Way and M31. Since M31 is approaching us, the Local Group is either virialized or collapsing. The simplest dynamical model in which the Group’s mass is concentrated in point particles coincident with the Milky Way and M31 suffices to show that the age of the Universe, combined with the present distance and Galactocentric velocity of M31, implies that the Local Group is collapsing for the first time (Kahn & Woltjer 1959).

When a cosmological structure collapses for the first time, its constituent parts move on highly elongated orbits towards the barycentre. Some of these orbits must enter the Galactic halo and become trapped. How much matter is the Galaxy likely to be accreting in this way?

The answer depends on two related quantities: how far out the Galactic halo reaches, and what fraction of the Local group lies outside M31 and the Galaxy. The mass of the Local Group has been estimated many times and found to lie in the range111The Local Group’s $`V`$-band luminosity is $`4.2\times 10^{10}\mathrm{L}_{}`$ (e.g., Tables 2.1 and 4.3 of Binney & Merrifield, 1998), while the mean mass-to-light ratio of the Universe is $`400h(\mathrm{\Omega }/0.25)`$ (§10.3.1 of Binney & Tremaine, 1987), so for $`h=0.65`$ one expects the mass of the Local Group to be $`1.1\times 10^{13}`$. $`4`$ to $`8\times 10^{12}\mathrm{M}_{}`$ (e.g., Schmoldt & Saha 1998). If all this matter were in M31 and the Galaxy, with a third of the matter being in the Galaxy, the halo would have to extend at constant $`v_c=220\mathrm{km}\mathrm{s}^1`$ to $`120`$ to $`210\mathrm{kpc}`$. Consequently, material that comes within $`100\mathrm{kpc}`$ of the Galactic centre is likely to be accreted.

Blitz et al. (1999) describe a simulation of the formation of the Local Group in which $`10^6`$ test particles move in the field of two point masses representing M31 and the Galaxy, plus the tidal field generated by external galaxies from Raychaudhury & Lynden-Bell (1989). Particles that come within $`100`$ comoving kpc of either M31 or the Galaxy are captured. In the simulation the Hubble flow currently reverses $`1.5\mathrm{Mpc}`$ from the centre of the Local Group and the Galaxy’s current accretion rate is $`7.5\mathrm{M}_{}\mathrm{yr}^1`$, of which $`0.8\mathrm{M}_{}\mathrm{yr}^1`$ takes the form of neutral hydrogen.

Can we see infalling material? One school of thought has long held that the so-called high-velocity clouds (HVCs) are made of infalling gas (Oort 1966, 1970). HVCs were first identified when Muller, Oort & Raimond (1963) detected 21-cm emission in many directions at velocities that are incompatible with circular rotation. The location of the objects responsible for this emission has been controversial, however. One possibility is that they are small, nearby clouds that have been accelerated to large peculiar velocities by supernovae, stellar winds, and the like. Alternatively, they might be at distances in excess of a Mpc and be tracing the (disturbed) Hubble flow around the Local Group.

It is likely that no single explanation applies to all HVCs. Some of these objects are almost certainly associated with Local-Group galaxies such as M31, the Magellanic Clouds and the Phoenix dwarf spheroidal (St-Germain et al, 1999). Others, such as Complex A (van Woerden et al., 1998) and Complex M (Danly et al., 1993) are small clouds in the Galactic halo. But a powerful case can be mounted that many HVCs are systems over $`10\mathrm{kpc}`$ in diameter that lie at distances $`1\mathrm{Mpc}`$.

Braun & Burton (1999) identified a sample of 66 compact, isolated HVCs, 23 of which had not previously been catalogued. They showed that these objects are distributed fairly uniformly over the sky, define a mean velocity that, within the errors, agrees with the Local Group’s mean velocity (Karachentsev & Makarov, 1966), and with respect to this mean have a velocity dispersion of $`69\mathrm{km}\mathrm{s}^1`$ and an infall velocity $`100\mathrm{km}\mathrm{s}^1`$. They infer that these objects are typically $`15\mathrm{kpc}`$ in diameter and contain $`\mathrm{}>10^7\mathrm{M}_{}`$ of HI.

Blitz et al. (1999) point out first that HVCs are seen within the Galactic plane where local objects would collide at high velocity with gas in circular motion, yet there is no evidence for shock-excited gas. Second, attempts to detect HVCs in absorption against distant stars have been largely fruitless – only two HVCs have been detected in absorption, and there are other reasons for believing that these are two of three HVCs that are unusually nearby. Third, nearby clouds would be illuminated by UV photons from the Galaxy and be brighter H$`\alpha `$ sources than they actually are. Fourth, the velocities of the HVCs make more sense when referred to the barycentre of the Local Group than when referred to either the velocity of the Galactic centre or the Local Standard of Rest. Fifth, the metallicities of HVCs are low, which is inconsistent with their having been ejected from the Galactic ISM.

Blitz et al. use their simulation of the formation of the Local Group to show that the non-uniform distribution of HVCs on the sky arises naturally if HVCs lie at distances $`\mathrm{}>1\mathrm{Mpc}`$. Moreover, at such distances the HVCs would have a distribution over column density which resembles that of Ly$`\alpha `$ clouds, which are now known to be floating in intergalactic space (Theuns & Efstathiou, 1998; Davé et al. 1999). Hence, when the HVCs are interpreted as extragalactic objects, they fit naturally into the picture of intergalactic space that has emerged from a combination of theoretical and observational work in cosmology. Blitz et al. argue that objects lying near the top of the HVC mass spectrum have already been detected in external groups of galaxies, and that less massive objects are detectable with feasibly deep observations. They estimate that a typical cloud contains $`3\times 10^7\mathrm{M}_{}`$ of HI, so the population as a whole contains $`10^{10}\mathrm{M}_{}`$ of HI.

Once one accepts that many HVCs are extragalactic and associated with cosmic infall, it is inevitable that their detected hydrogen is associated with a very much larger mass of dark matter. The estimate of the Galaxy’s accretion rate cited above is based on the assumption that there is 10 times as much dark matter as neutral hydrogen. There could easily be more dark matter by a factor of a few, since $`\mathrm{\Omega }_{\mathrm{baryon}}`$ is thought to be $`\mathrm{}<0.05`$ and only a fraction of a HVC’s hydrogen content will be neutral.

## 3. Warps

Both theoretical and observational developments over the last few years have strengthened the argument that warps such as that of the Galactic disk are a reflection of cosmic infall, and the associated reorientation of galactic angular-momentum vectors. Since the discovery of the Galactic warp by Burke (1957) and Kerr (1957), there has been a debate as to whether warps are self-consistent intrinsic structures, or externally driven. Kahn & Woltjer (1959) suggested that the Galactic warp was driven by an intergalactic wind, while Lynden-Bell (1965) suggested that a warp can be an intrinsic structure. The latter proposal was shot down by Hunter & Toomre (1969). After the discovery of dark matter, Toomre (1983) and Dekel & Shlosman (1983) argued that warps might after all be intrinsic structures, and Sparke & Casertano (1988) developed this proposal to the point that it became very attractive. Recently Nelson & Tremaine (1995) and Binney, Jiang & Dutta (1998) have demonstrated that the Toomre–Dekel proposal, as elaborated by Sparke & Casertano, is not viable. The flaw in the approach of Sparke & Casertano is the treatment of the dark halo as a rigid, unflexing thing. The semi-analytic work of Nelson & Tremaine and the numerical simulations of Binney et al. demonstrate that a dark halo responds rapidly to any warp in an embedded disk in such a manner that warps predicted to endure for ever by Sparke & Casertano actually wind up within a few dynamic times.

Binney et al. did not demonstrate that intrinsic warps are impossible, but only that any long-lived warp would have to be a manifestation of a cooperative distortion of both disk and halo. However, a priori it is not clear that such configurations exist, and extensive numerical experimentation by several groups has failed to find one. Hence, the theoretical case for intrinsic warps must be considered at best doubtful. Moreover, new observations (Shang et al. 1998) of the classic example of an isolated galaxy with an integral-sign warp, NGC 5907, have shattered the observational case for the existence of warps in isolated galaxies: NGC 5907 possesses both a dwarf satellite $`37\mathrm{kpc}`$ from its centre, and an elliptical ring of luminosity that probably contains the debris of another, now shredded, companion.

What is the theoretical status of externally driven warps? The original proposal of Kahn & Woltjer (1959) is not viable because it relies upon a massive, subsonic wind past the Milky Way, for which there is no evidence. Similarly, proposals involving magnetic fields (Battaner, Florido & Sánchez-Saavedra, 1990) are for various reasons not in serious contention. An idea that remains plausible is that warps are a response to the accretion by a galaxy of material laden with angular momentum about an axis that is inclined to the galaxy’s original spin axis (Binney & May, 1986; Ostriker & Binney, 1989). Jiang & Binney (1999) followed the dynamics of a disk embedded in a live halo by decomposing the disk into a series of massive rings that interact gravitationally with one another and with the $`\mathrm{100\hspace{0.17em}000}`$ particles that represent the halo. The disk is exponential out to $`R=3.5R_\mathrm{d}`$ and is then smoothly tapered to zero surface density at $`R=4R_\mathrm{d}`$. The halo initially has ten times the mass of the disk and ensures that the overall rotation curve is very nearly flat out to $`5R_\mathrm{d}`$. The accretion of material by the halo is simulated by injecting particles into a torus of major radius $`8.9R_\mathrm{d}`$ whose spin axis is inclined by $`15^{}`$ to the original spin axis of the disk. In response to the accretion, the disk develops an integral-sign warp that carries the outermost ring $`0.3R_\mathrm{d}`$ above and below the plane of the innermost ring. Hence the warp is very comparable in magnitude to the warp of the Milky Way. This simulation shows very clearly that the warp is essentially a halo phenomenon: accretion causes the outer halo to tip with respect to the inner halo. The disk largely acts as a tracer of the internal dynamics of the halo.

How much infalling matter is needed to generate a warp? In this simulation, the reorientation of the galactic angular momentum is driven by the crude expedient of adding mass to a tilted annulus of fixed radius. This procedure is well defined and easy to describe, but it exaggerates the mass of infalling material that is required to slew a galaxy’s angular momentum by a given amount because neither the angular-momentum per unit mass of the infalling material, nor the angle between its spin axis and the galaxy’s original spin axis increases with time, as they would in a more realistic situation. Indeed, if the simulation were continued for longer, the galaxy’s angular momentum would everywhere become parallel to the symmetry axis of the torus, and the warp would fade away. In the real world, by contrast, the angular momentum vector of infalling material will be constantly shifting its direction, and, moreover, less and less material will be required to import a given quantity of angular momentum. Hence the simulation’s plausibility hinges on whether the rate of angular-momentum slewing in it is plausible, rather than on the likelihood that a galaxy will accrete as much material at $`10R_\mathrm{d}`$ as is crudely assumed.

Several authors have studied how tidal interactions endow protogalactic regions with angular momentum at early times (e.g. Heavens & Peacock 1988) and these studies are generally in good agreement with numerical simulations (Barnes & Efstathiou 1987). Ryden (1988) and Quinn & Binney (1992) investigated the rate at which the direction of infalling angular momentum should slew by studying the angular momenta of individual spherical shells of protogalactic material. Quinn & Binney found that the angular momenta acquired by shells that differ in radius by a factor 2 have a clear tendency to be antiparallel. Moreover, the angular momentum per unit mass of a shell rises strongly with radius, with the consequence that the net angular momentum of a galaxy tends to be aligned with the angular momentum of the most recently accreted shell. These two results together imply that the net spin axis of a halo tends to slew through more than $`90^{}`$ in the time required for the radius of the currently accreting shell to double. This time depends on the cosmology and the initial density profile (e.g. Fillmore & Goldreich 1984). For critical cosmic density, $`\mathrm{\Omega }=1`$, it is typically comparable to the current Hubble time and the halo’s spin axis is likely to slew by $`\mathrm{}>7^{}`$ in the $`0.9\mathrm{Gyr}`$ that the Jiang & Binney simulation lasted.

## 4. Infalling satellites

It has long been recognized that the Magellanic Clouds are spiralling into the Milky Way. Dynamical models of this process (Murai & Fujimoto 1980; Gardiner et al. 1994; Moore & Davis, 1994; Lin et al. 1995) have been successful in predicting the proper motions of the Clouds, which have now been measured to reasonable accuracy (Jones, Klemola & Lin, 1994; Kroupa & Bastian, 1997). These models are based on the assumption that the Magellanic Stream comprises material that has been tidally stripped out of the Clouds. Hence the success of these models implies that as the Clouds sink deeper into the Galactic halo, a polar ring will form. Since there will be more angular momentum in this ring than there is in the Galactic disk, the orbit of the Clouds constitutes direct evidence for the accretion of mis-aligned angular momentum.

Ibata, Gilmore & Irwin (1994) discovered that the Galaxy has a much nearer satellite than the Clouds, namely the Sagittarius Dwarf galaxy, that is almost hidden from us by the Galactic centre even though it is at a Galactocentric distance of only $`16\mathrm{kpc}`$. Like the Clouds, the Sgr Dwarf is in a nearly polar orbit (Ibata et al. 1997), but the poles of the two orbits make an angle of $`90^{}`$ with one another. It seems that the Dwarf’s orbit has a remarkably short period $`1\mathrm{Gyr}`$ (Ibata & Lewis 1998).

On such a short-period orbit the Dwarf is severely tidally limited by the Galaxy, and there is direct observational evidence that the Dwarf is being tidally shredded: an arc of associated material has now been detected that extends over $`\mathrm{}>60^{}`$ on the sky (Mateo, Olszewski & Morrison, 1999). Several authors have concluded that a Dwarf that contained only the observed luminous material could not have survived tidal shredding for a Hubble time on its present orbit. By enveloping the observed dwarf in a rather homogeneous cloud of dark matter, Lewis & Ibata (1998) were able to construct a model of the Dwarf which retained 46% of its original mass after a Hubble time on its present orbit.

Jiang & Binney (this volume) ask how the Dwarf could have got into its present configuration: galaxies are not likely to form in regions where an external tidal field is strong, because the field would shear away protogalactic material and prevent it accumulating locally. Moreover, the configuration proposed by Lewis & Ibata is finely tuned in the sense that the dark halo has to be very homogeneous and sharp-edged. For these reasons it seems likely that the Dwarf was formed at a considerable distance from the Milky Way, and has subsequently moved onto its present tight orbit by one of two mechanisms. Zhao (1998) suggested that the Dwarf was recently scattered onto its orbit by an encounter with the Clouds. The problem with this proposal is the softness of the potentials of the Dwarf and the Clouds relative to the large velocity of any encounter between them: the required scattering is through a substantial angle. Dynamical friction is the other mechanism that could have moved the Dwarf onto a short-period orbit. The problem here is that the present mass of the Dwarf, even including the Lewis & Ibata dark halo, is too small ($`10^9\mathrm{M}_{}`$) for dynamical friction to be effective.

Jiang & Binney combine $`N`$-body simulations, in which both Dwarf and Galaxy are live systems, with a semi-analytic model, that incorporates dynamical friction and tidal limitation, to explore the rather large parameter space of possible Dwarf histories. They identify a one-parameter family of initial configurations in which the Dwarf starts out at ever greater Galactocentric distances. In the most distant initial configuration explored, the Dwarf starts from $`R=250\mathrm{kpc}`$ as an object of mass $`10^{11}\mathrm{M}_{}`$, largely in the form of a dark halo with central velocity dispersion $`50\mathrm{km}\mathrm{s}^1`$ and roughly constant circular speed. At the other extreme, the Dwarf starts from $`R60\mathrm{kpc}`$ with mass $`1.4\times 10^{10}\mathrm{M}_{}`$. The off-axis angular momentum that the Dwarf brings to the Galaxy, which varies by a factor $`30`$ between extreme configurations, would have a pronounced effect of the Galactic warp at the upper end of the range. Hence, it should be possible to constrain the history of the Dwarf by modelling the combined effect of the Dwarf and the Clouds on the outer disk.

## 5. Conclusions

From the kinematics of M31 we know that the Local Group has yet to virialize. Hence, there is an a-priori expectation that out towards the edges of the Local Group there is a reservoir of material from which M31 and the Galaxy are accreting at a significant rate.

There is a real possibility that this reservoir can be traced through high-velocity clouds (HVCs). This proposition is controversial because the HVCs form a heterogeneous group. Some are clearly associated with M31, the Magellanic Clouds, and other, lower-mass systems such as Phoenix (St-Germain et al, 1999). Others are material in the Galactic halo, but one can identify substantial subset of HVCs that are most naturally interpreted as rather massive objects of order $`1\mathrm{Mpc}`$ from the Galaxy that have yet to fall to the centre of the Local Group. These clouds may together contain $`10^{10}\mathrm{M}_{}`$ of HI and enable the Galaxy to accrete HI at a rate of $`0.8\mathrm{M}_{}\mathrm{yr}^1`$ and dark matter at a rate ten times higher.

Currently we know of no viable mechanism by which warps could survive long in an isolated galaxy, and there is no longer observational support for the proposition that warps exist in isolated galaxies. It seems likely that warps are a manifestation of a galaxy accreting material whose net angular momentum is not parallel to that of the galaxy. To generate a typical warp, off-axis angular momentum must be accreted at such a rate that the spin axis of the inner galaxy slewed by $`10^{}`$ per Gyr.

Observations of the Magellanic Stream and the Sgr Dwarf Galaxy tell us that the Milky Way is certainly accreting off-axis angular momentum. Whether this accretion is fast enough to slew the inner Galaxy’s spin axis by $`10^{}`$ per Gyr depends on how much dark-matter is being accreted alongside the observed luminous matter. If there is 10 times as much dark as luminous matter, it should be possible to explain the Galactic warp, although the very peculiar morphology of the Galactic warp has yet to emerge from a model of Galactic accretion.

## References

Battaner E., Florido E., Sánchez-Saavedra M.L., 1990, AA, 236, 1

Binney J.J., May A., 1986 MN, 218, 743

Binney J.J., Merrifield, M.R., 1998, Galactic Astronomy, Princeton University Press

Binney J.J., Jiang I.-G., Dutta S.N., 1998, MN, 297, 1237

Binney J.J., Tremaine, S.D., 1987, Galactic Dynamics, Princeton University Press

Davé R., Hernquist L., Katz N., Weinberg D.H., 1999, ApJ, 511, 521

Dekel A., Shlosman I., 1983, in IAU Symposium 100, ‘Internal Kinematics and Dynamics of Galaxies’, ed. E. Athanassoula, Dordrecht, Reidel, p. 187

Gardiner L.T., Sawa T & Fujimoto M., 1994, MN, 266, 567

Hunter C., Toomre A., 1969, ApJ, 155, 747

Ibata R.A., Gilmore G., Irwin M.J., 1994, Nature 370, 194

Ibata R.A., Lewis G.F., 1998, ApJ, 500, 57

Ibata R.A., Wyse F.G., Gilmore G., Irwin M.J., Suntzeff M.B., 1997, AJ, 113, 634

Jiang I.-G., Binney J.J., 1998, MN, 303, L7

Jones B.F., Klemola A.R., Lin D.N.C., 1994, AJ, 107, 1333

Kahn F.D., Woltjer L., 1959, ApJ, 130, 705

Karachentsev I.D., Makarov D.A., 1966, AJ, 111, 794

Kroupa P., Bastian U., 1997, New Astron, 2, 77

Lin D.N.C., Jones B.F., Klemola A.R., 1995, ApJ, 439, 652

Lynden-Bell D., 1965, MN, 129, 299

Mateo M., Olszewski E.W., Morrison H.L., 1999, astro-ph/9810015

Moore B., Davis M., 1994, MN, 270, 209

Murai T., Fujimoto M., 1980, PASJ 32 581

Nelson R.W., Tremaine S., 1995, MN, 275, 897

Oort J.H., 1966, Bull. Astr. Inst. Netherlands 18, 421

Oort J.H., 1970, AA, 7, 381

Ostriker E.C., Binney J.J, 1989, MN, 237, 785

Quinn T.R., Binney J.J., 1992, MN, 255, 729

Schmoldt I.M., Saha P., 1998, AJ, 115, 2231

Shang Z., et al. 1998, ApJ, 504, L23

Sparke L.S., Casertano S., 1988, MN, 234, 873

St-Germain, J., Carignan, C., Côte, S., Oosterloo, T., 1999, AJ, 118, 1235

Theuns T., Leonard A., Pearce F.R., Thomas P.A., 1998, MN, 301, 478

Toomre, A., 1983, in IAU Symp. 100, ‘Internal Kinematics and Dynamics of Galaxies’, ed. E. Athanassoula, Reidel, Dordrecht, p. 177

Zhao H.-S., 1998, ApJ, 500, L149