text:
\begin{document}

\title{Outer bounds for exact repair codes}

\author{Iwan M. Duursma}

\date{\today}

\maketitle

\begin{abstract}
We address the open problem of establishing the rate region for exact-repair regenerating codes for given parameters $(n,k,d)$. Tian determined the rate region for a $(4,3,3)$ code and found that it lies strictly within the functional-repair rate region.

Using different methods, Sasidharan, Senthoor and Kumar prove a non-vanishing gap between the functional-repair outer bound and the exact-repair outer bound for codes with $k \geq 3$. Our main results are two improved outer bounds for exact-repair regenerating codes. They capture and then extend essential parts in the proofs by Tian and by Sasidharan, Senthoor and Kumar. We show that the bounds can be combined for further improvements.
\end{abstract}

\section*{Introduction}
Regenerating codes were introduced by Dimakis, Godfrey, Wu, Wainwright and Ramchandran \cite{DGWWR10}. Their main application is in large distributed storage systems where they lead to significant savings by optimizing the trade-off between storage size and repair bandwith. In a distributed storage system (DSS) an encoded file is stored on $n$ servers such that it can be recovered from any combination of $k$ servers. If a server fails it can be rebuilt by retrieving the information needed for its repair from any combination of $d$ other servers. An encoding scheme realizing these parameters is called an $(n,k,d)$ regenerating code. For background and details on distributed storage and regenerating codes we refer to \cite{DRWS11}, \cite{SRKR10}. A common example is the use of a $(4,2,3)$ code to store four bits $x,y,z,t$.
By storing the pairs of bits $(x,z+t), (y,t+x), (z,x+y), (t,y+z)$ on four different servers ($n=4$), the four bits $x,y,z,t$ can be recovered from the combined information on any two servers ($k=2$). And if a server fails it can be rebuilt by retrieving one bit from each of the remaining three servers ($d=3$). In particular, the first server can be rebuilt from the three bits $y, y+x,$ and $y+z+t$.

An $(n,k,d)$ code comes with a secondary set of parameters $(B,\alpha,\beta)$. For a file of size $B$, a part of size at most $\alpha$ is stored on a single server, and bandwith between a server and any of the $d$ servers helping in its repair is limited to $\beta$. For the example, $B=4, \alpha=2, \beta=1$. The gains in a DSS are obtained by using a total repair bandwith $\gamma = d \beta$ that is possibly larger than $\alpha$ but much smaller than the file size $B$.
The challenge is, given $(n,k,d)$, to optimize the trade-off between the storage $\alpha$ per server and the repair bandwith $\beta$ between servers in order to store a file of size $B$. For given parameters $(n,k,d)$, the outer bound refers to the relation among the parameters $(B,\alpha,\beta)$. The outer bound can be interpreted as an upper bound on the file size $B$, for given $\alpha$ and $\beta$, or as a lower bound for $\alpha$ and $\beta$, for a given file size $B$. In the first case it is standard to scale to variables $B/\beta$ and $\alpha/\beta$, and in the second case to variables $\alpha/B$ and $\beta/B$.

In this work, we establish new outer bounds for exact-repair regenerating codes. In the exact-repair scenario it is required that a server be rebuilt to its original form. The weaker requirement, known as functional repair, only requires that a server be rebuilt to a form that preserves the functionality of the DSS. Upper bounds for the file size under functional repair are piece-wise linear and take the form
\begin{equation} \label{Bfr}
B \leq B_q = q\alpha +  \binom{k-q}{2} \beta + (d+1-k)(k-q) \beta, \quad 0 \leq q \leq k.
\end{equation}
Details of the bound and motivation behind the linear functions $B_q$ are recalled in Section \ref{S:1}. For the values $(n,k,d)=(4,2,3)$,
\[
B \leq \min ( B_2, B_1, B_0 ) =  \min ( 2 \alpha, \alpha+ 2\beta, 5 \beta ).
\]
For the four bit example with $(B,\alpha,\beta)=(4,2,1)$ the bound is sharp at both $B \leq B_1$ and $B \leq B_2$.
The vertex with $B = B_k = B_{k-1}$ minimizes $\alpha$ and is called the MSR point (for Minimum Storage Regenerating code). The vertex with $B = B_1 = B_0$ minimizes $\beta$ and is called the MBR point (for Minimum Bandwith Regenerating code).
Both these points are achieved by exact-repair regenerating codes using the general construction in \cite{RSK11}. Using the notion of information flow graph and then applying results from network coding, the main result of \cite{DGWWR10} shows that the bound (\ref{Bfr}) is sharp for regenerating codes under the functional-repair requirement. Clearly, exact-repair implies functional-repair, and the outer bound (\ref{Bfr}) applies to exact-repair regenerating codes

Tian \cite{T14} determined the rate region for a $(4,3,3)$ code and provided the first example of an exact-repair rate region that lies strictly within the functional-repair rate region. For a $(4,3,3)$ code
\begin{equation} \label{B433}
B \leq \min ( B_3, B_2, B_1, B_0 \}
 =  \min ( 3 \alpha, 2 \alpha + \beta, \alpha + 3 \beta, 6 \beta \}.
\end{equation}

The exact-repair region is describeded by adding to (\ref{B433}) the new inequality
\begin{equation} \label{new}
3B ~\leq~ 4 \alpha + 6 \beta~ ( = 2B_1+B_2-\beta ).
\end{equation}

To prove that all points in the new region can be achieved it suffices, using a standard time sharing argument, that the vertices with $\alpha/\beta \in \{ 1,\;3/2,\;3 \}$ can be achieved. The first and the last are the MSR and the MBR point. An example achieving $B=8, \alpha = 3, \beta =2$ is provided in \cite{T14}. A different example is to encode eight bits $x_1, x_2, y_1, y_2, z_1, z_2, t_1, t_2$ as four triples
\[
\begin{array}{ccccc}
x1 & &x2 & &z1+t2 \\
y1  & & (y2) & &(t1+x2) \\
(z1) & &z2 & &(x1+y2) \\
(t1) & &(t2) & &y1+z2
\end{array}
\]
The repair information to rebuilt the first server is given in parentheses.

As part of their results, Sasidharan, Senthoor and Kumar \cite{SSK13} obtain the same inequality (\ref{new}). Their main result however [Ibid., Theorem 1] is a non-vanishing gap between the  functional-repair outer bound and the exact-repair outer bound for all codes with $k \geq 3$.

Our results include the following outer bound (Theorem \ref{thm-rs}).

\begin{quote}
\emph{For given $k,d$, let $q,r,s$ be positive integers with $q+r+s \leq k$. Let $V_1,V_2,\ldots,V_{n-2}$ be subsets of $\{ r+s+1,\ldots,d+1 \}$ of size $q_i = |V_i| \leq k-r-s$ with empty intersection
$V_1 \cap V_2 \cap \cdots \cap V_{n-2} = \emptyset$. Then}
\[
n B \leq B_q + \sum_{i=1}^{n-2} B_{q_i} + B_{r+s} - rs \beta.
\]
\end{quote}

For $k=2p, d=3p$, $q=q_1=q_2=r+s=p$, it follows that $B \leq B_p - (p^2-1) \beta / 16$. This difference is unbounded as $p$ goes to infinity. On the other hand, the non-vanishing gap in \cite{SSK13} remains bounded and is always less than $\beta$.

A second outer bound (Theorem \ref{thm-lm}) is obtained using a similar approach as in \cite{SSK13}. For both outer bounds we give examples that illustrate the improvements over known bounds. We also show that the bounds can be combined for further improvements.

The next section formulates the main problem. Section \ref{S:2} presents the main arguments and how they are used in two different proofs for the rate region of a $(4,3,3)$-code. Section \ref{S:4} proves Theorem \ref{thm-rs}. Section \ref{S:3} builds on the approach used in \cite{SSK13} and proves Theorem \ref{thm-lm}. It also contains a short proof for a non-vanishing gap of $\beta/6$ between the outer bounds for  functional-repair and exact-repair.  Section \ref{S:5} illustrates how the results of the two previous sections can be used in combination.

\section{An optimization problem on random variables} \label{S:1}

By an exact-repair regenerating code of type $(n,k,d)$ with secondary parameters $(B,\alpha,\beta)$ we mean a collection of random variables $M$, $\{ W_j : 1 \leq j \leq n \}$ and $\{ S_i^j : 1 \leq i,j \leq n, i \neq j \}$ that satisfy several  entropy constraints. Let $W_J$ denote the joint distributions $W_J = (W_j : j \in J)$ and, for $j \not \in I$, let $S_I^j$ denote the joint distribution $S_I^j = ( S_i^j : i \in I).$ The entropy constraints are the following
\begin{align}
&H(M) = B. \label{en1} \\
&H(W_j) = \alpha,~~~H(W_j|M) = 0,~~~H(M|W_J) = 0~(|J|\geq k).  \label{en2} \\
&H(S_i^j) = \beta,~~~H(S_i^j|W_i) =0,~~~H(W_j|S_I^j) = 0~(|I| \geq d, j \not \in I). \label{en3}
\end{align}
The interpretation for a distributed storage system is that $M$ is the file to be stored, $W_i$ is the part of the encoded file that is stored on server $i$, and $S_i^j$ is the helper information provided by server $i$ to repair server $j$. Assuming uniform distributions for each of the variables, the conditions $H(M)=B, H(W_i)=\alpha$ and $H(S_i^j)=\beta$ describe the size of the underlying space for $M, W_i$ and $S_i^j$, respectively. The condition $H(W_i|M) = 0$ says that the information stored on server $i$ is completely determined by the file $M$, and similarly $H(S_i^j|W_i) =0$ says that helper information provided by server $i$ is completely determined by information stored on server $i$. Finally, the access condition $H(M|W_J) = 0~(|J|\geq k)$ says that the file can be recovered from information stored on any $k$ servers, and similarly $H(W_j|S_I^j) = 0~(|I| \geq d, j \not \in I)$ says that server $j$ can be rebuilt with helper information received from any $d$ remaining servers.
Clearly, for $|J| =k$,
\[
B = H(M) = H(M|W_J)+H(W_J) \leq 0 + \sum_{j \in J} H(W_j) = k \alpha.
\]
and thus $B \leq k \alpha.$ Moreover, for $0 \leq q \leq k$, let $\{1,2,\ldots,d+1\} = V' \cup V \cup U$ be a partition with $|V'|=q, |V|=k-q$ and $|U|=d+1-k$, and let
$S_V$ denote the joint distribution $S_V = ( S_i^j : i,j \in V, i > j ).$ Then
\[
H(M | W_{V'} S_V S_U^V) = 0
\]
and
\begin{align*}
B = H(M) &\leq~ H(W_{V'} S_V S_U^V) \leq H(W_{V'}) + H(S_V) + H(S_U^V) \\
&\leq~ q \alpha + \binom{k-q}{2} \beta + (d+1-k)(k-q) \beta~~~(=:B_q)
\end{align*}
The upper bound $B \leq \min \{ B_q : 0 \leq q \leq k \}$ applies to both the exact-repair and the functional-repair setting and is sharp for the latter \cite{DGWWR10}.
We will make use of the following.
\begin{align}
&B_{r+1}-B_r = \alpha - (d-r)\beta,  ~~~(0 \leq r \leq k-1)  \label{Br} \\
&B_{r+m}-B_{r+m-1}+B_r-B_{r_1}= (m-1) \beta. ~~~(1 \leq r \leq r+m \leq k) \label{Brm}
\end{align}

\subsection{The case $(n,k,d)=(4,3,3)$}

The single argument that we are aware of to improve the bound
\[
B \leq \min \{ B_q : 0 \leq q \leq k \}
\]
is to sum multiple copies of the bound for different choices of $(V',V,U)$ and to exploit nonzero mutual information among variables in the different copies.
For the $(4,3,3)$-code, one such sum of three copies is
\[
3B ~\leq~ H(W_1 S_3^2 S_4^2 S_4^3) + H(W_4 S_3^2 S_1^1 S_1^3) + H(W_2 W_3 S_1^4),
\]
which corresponds to $(V',V,U)=(\{1\}, \{2,3\},\{4\}),$ $(\{4\},\{2,3\},\{1\}),$ $ (\{2,3\},\{4\},\{1\}).$ After adding a term $H(S_3^2)$, we can regroup the variables (details are provided in Section\ref{S:4}).
\begin{align*}
3B + \beta &\leq~ H(W_1 S_3^2 S_4^2 S_4^3) + H(W_4 S_3^2 S_1^2 S_1^3) + H(W_2 W_3 S_1^4) + H(S_3^2)  \\
                  &\leq~ H(W_1 S_3^2 S_4^2) + H(W_4 S_3^2 S_1^2) + H(W_3 S_1^4) + H(W_2 S_3^2 S_4^3 S_1^3)
\end{align*}
Finally, $H(W_2 S_3^2 S_4^3 S_1^3) = H(W_2 S_4^3 S_1^3)$ leads to a savings of $\beta$ in the sum of the original three copies and thus to (\ref{new}).
The same argument is at the core of the proof in \cite{T14}.

A different choice for the sum of three copies is
\[
3B ~\leq~  H(W_1 S_3^2 S_4^2 S_4^3) + H(W_2 W_3 S_4^1) + H(W_2 W_3 W_4),
\]
which corresponds to $(V',V,U)=(\{1\},\{2,3\},\{4\}),$ $(\{2,3\},\{1\},\{4\}),$ $ (\{2,3,4\},\emptyset,\{1\}).$
First we regroup the variables to obtain (details are provided in Section\ref{S:3})
\[
3B ~\leq~ H(W_1 S_3^2) + H(W_2 W_3 S_4^2) + H(W_2 W_3 S_4^3) + H(S_4^1) + H(W_4).
\]
Using $H(W_2 W_3 S_4^2) = H(W_3 S_4^2) + H( W_2 | W_3 S_4^2) \leq H(W_3 S_4^2) + H(S_1^2)$ and similarly $H(W_2 W_3 S_4^3) \leq H(W_2 S_4^3) + H(S_1^3)$  leads to (\ref{new}). The final reduction follows \cite[Equation (18)]{SSK13}.

A difference between the first choice and the second choice is that the first choice reduces the number of $S_i^j$ while the second choice reduces the number of $W_i$ at a cost of increasing the number of $S_ i^j$.

\subsection{Relation to secret sharing}

We briefly point out the connection between regenerating codes and secret sharing.
In secret sharing a sensitive message is distributed over several parties such that only qualified combinations of parties can reconstruct the message. For the distribution of a message $M$ using shares $W_j$, $j=1,2,\ldots,n,$ let
\begin{align*}
&H(M|W_J) = 0, ~\text{for $|J| \geq r$,} \\
&I(M;W_J) = 0, ~\text{for $|J| \leq t$}.
\end{align*}
The minimal choice for $r$ (resp. the maximal choice for $t$) is called the acceptance threshold (resp. the rejection threshold).
For the distribution of a file $M$ over servers $W_j$, $j=1,2,\ldots,n$ we use the conditions
\begin{align}
H(M|W_J) = 0, \quad \text{if $|J| \geq k$.} \label{eq:t1} \\
I(M;W_J) \leq \alpha, \quad \text{if $|J| \leq 1$.} \label{eq:t2}
\end{align}
For a server $W_j$, let $S^j_1, \ldots, S^j_m$ be helper nodes. We add a second set of conditions
\begin{align}
H(W_j|S^j_I) = 0, \quad \text{if $|I| \geq d$.} \label{eq:b1}\\
I(W_j;S^j_I) \leq\beta, \quad \text{if $|I| \leq 1$}. \label{eq:b2}
\end{align}
These conditions express that a DSS is similar to a two-layer secret sharing scheme where the condition on mutual information is relaxed from zero mutual infirmation to bounded mutual information. The condition of bounded mutual information is enforced to obtain efficient storage in the top-layer and efficient bandwith in the bottom layer (rather than to reduce the information about the secret as in an actual secret sharing scheme). The two-layered secret scheme becomes a regenerating code if we enforce that a share $S^j_i$ is stored not on a dedicated second layer of servers but can be obtained from information on server $W_i$. This is expressed by the conditions
\begin{equation} \label{eq:genb}
H(S^j_i | W_i ) = 0, ~~\text{for all $i,j$}.
\end{equation}
We add as conditions for the top layer
\begin{equation} \label{eq:WM}
H(M) = B, ~~H(W_j| M ) = 0, ~~\text{for all $j$}.
\end{equation}
The entropy conditions (\ref{en1})--(\ref{en3}) imply the conditions (\ref{eq:t1})--(\ref{eq:WM}) and thus the optimization problem for regenerating codes reduces to a problem of share sizes for a special version of a two-layer secret sharing scheme.

\section{Configurations of random variables} \label{S:2}

Let $k$ and $d$ be fixed. We make use of three different configurations of random variables. Minimal configurations appear in the upper bounds $B \leq B_q$, for $0 \leq q \leq k$. For a partition of $\{1,2,\ldots,d+1\}$ into subsets $V$, $M$ and $U$,with $|V|=q,$ $|M|=k-q,$ $|U|=d+1-k,$
\[
B \leq H( W_V, S_M, S_U^M) \leq B_q
\]
With the interpretation of the random variables as edges in an information-flow graph,
\begin{equation} \label{S1}
S = \{ W_V, S_M, S_U^M \}
\end{equation}
corresponds to a min-cut \cite{DGWWR10}.
For a partition of $\{1,2,\ldots,d+1\}$ into susbets $T,$ $L,$ $M$ and $U$, the two configurations
\begin{align}
&S =   \{ W_T, W_L, S_M^L, S_M, S_U^M \} \label{S3} \\
&S =  \{ W_T, W_L, S_M^L, S_U^L \}  \label{S2}
\end{align}
will be used for improvements of the min-cut bounds. For $S$ as in (\ref{S3}),
\begin{equation} \label{R3}
H( S_M^L | W_T W_L S_M S_U^L ) = 0.
\end{equation}
For $S$ as in (\ref{S2}),
\begin{equation} \label{R2}
H(W_i | W_T W_{L \backslash i} S_M^i) \leq H(S_U^i) \qquad (i \in L)
\end{equation}

We illustrate each of the three cases for a partition of $\{ 1, 2, \ldots, 8 \}$.
Putting a mark in position $i,i$ for $W_i \in S$ and a mark in position $i,j$ for $S_i^j \in S$, the
configurations are represented by the diagrams
\[
\begin{array}{ccccc}
\begin{array}{c|cccccc}
  &1 &2 &3 &4 &5 &6 \\ \hline
1 &\xa & & \\
2 & &\xa & \\
3 & & &-  \\
4 & & &\xc &- \\
5 & & &\xc &\xc &- \\
6 & & &\xc &\xc &\xc &- \\
7 & & &\xb &\xb &\xb &\xb \\
8 & & &\xb &\xb &\xb &\xb
\end{array}
&\quad
&\begin{array}{c|ccccc}
  &1 &2 &3 &4 &5 \\ \hline
1 &\xa & & \\
2 & &\xt & \\
3 & & &\xt \\
4 & &\xd &\xd &- \\
5 & &\xd &\xd &\xc &- \\
6 & &    &    &\xb &\xb  \\
7 & &    &    &\xb &\xb  \\
8 & &    &    &\xb &\xb
\end{array}
&\qquad
&\begin{array}{c|ccccc}
  &1 &2 &3 &4  \\ \hline
1 &\xa & & \\
2 & &\xa & & \\
3 & &  &\xt & \\
4 & &  &  &\xt  \\
5 & &  &\xd &\xd \\
6 & &  &\xd &\xd \\
7 & &  &\xb &\xb \\
8 & &  &\xb &\xb
\end{array} \\
{}\\[1.5ex]
(a) & &(b) & &(c)
\end{array}
\]
\[
\begin{array}{cclcl}
(a) &~ &V = \{ 1,2 \}, ~M=\{ 3,4,5,6 \}, ~U=\{ 7,8 \} \\
(b) &~ &T = \{ 1 \}, ~L=\{ 2,3 \}, ~M=\{ 4,5\}, ~U=\{ 6,7,8 \} \\
(c) &~ &T = \{ 1,2 \}, ~L=\{ 3,4 \}, ~M=\{ 5,6 \}, ~U=\{ 7,8 \}
\end{array}
\]
The goal in the next sections is to collect several copies of type (a), to break them into smaller pieces and to regroup them
into a configuration of type (b) (Section \ref{S:4}), or type (c) (Section \ref{S:3}), or a combination of both (Section \ref{S:5}).

The proofs for the improved outer bound (\ref{new}) of a (4,3,3) code in Section \ref{S:2} are special cases. The reduction $H(W_2 S_3^2 S_4^3 S_1^3) = H(W_2 S_4^3 S_1^3)$ uses (\ref{R3}) with
$T = \emptyset, L = \{2\}, M= \{3\}, U = \{1,4\}$.  The reduction $H( W_2 | W_3 S_4^2) \leq H(S_1^2)$ uses (\ref{R2})
with $T = \emptyset, L = \{2, 3\}, M= \{4\}, U = \{1\}$.

\subsection{Parity check matrices}

Assume that $M$ is uniformly distributed on a vector space $V$ of dimension $B$, that the $W_i$ are uniformly distributed on vector spaces $V_i$ of dimension $\alpha$, and that the
$S_i^j$ are uniformly distributed on vector spaces $V_i^j$ of dimension $\beta$. We group the entropy conditions (\ref{en1})-(\ref{en3}) in a different way and give a vector space interpretation.
\begin{align}
&H(M) = B, ~~H(W_i) = \alpha,~~H(W_i|M) = 0 \label{C1} \\
&H(M|W_I) = 0~(|I|\geq k) \label{C2} \\
&H(W_i) = \alpha, ~~H(S_i^j) = \beta, ~~~H(S_i^j|W_i) =0 \label{C3} \\
&H(S_i^j|W_i) =0, ~~H(W_j|S_I^j) = 0~(|I| \geq d, j \not \in I). \label{C4}
\end{align}
Condition (\ref{C1}) implies that there exists a linear map $\phi_i : V \longrightarrow V_i$ of rank $\alpha$ with $phi_i(M) = W_i$. Together the maps define a linear encoder
\[
\phi = (\phi_1,\ldots,\phi_n) : V \longrightarrow \oplus V_i, ~~M \mapsto (W_1,\ldots,W_n).
\]
The image is a linear code of dimension $B$ and length $n \alpha$.
Condition (\ref{C2}) implies that the generator matrix is of full rank $B$ on any submatrix of $k$ out of $n$ blocks of size $\alpha$.
Condition (\ref{C3}) implies that there exists a linear map of rank $\beta$
\[
\phi_i^j :  V_i \longrightarrow V_i^j, ~~~(W_i) \mapsto S_i^j.
\]
Condition (\ref{C4}) implies that there exists a linear map
\begin{equation}
\psi_I^j : \oplus V_i \longrightarrow V_j,~~~(W_i : i \in I) \mapsto W_j,~~~(|I| \geq d)
\end{equation}
and moreover that it factors as
\begin{equation}
\psi_I^j : \oplus V_i \longrightarrow \oplus V_i^j \longrightarrow V_j,~~~(W_i : i \in I) \mapsto (S_i^j : i \in I) \mapsto W_j.
\end{equation}
The factorization allows us to characterize a regenerating code of length $n=d+1$ through the structure of its parity check matrix.

\begin{proposition}
A linear code of dimension $B$ and length $n\alpha$ ($n$ consecutive blocks of length $\alpha$) represents a $(n,k,d)$ regenerating code with secondary
parameters $(B,\alpha,\beta)$ if
\[
\begin{array}{ll}
(1) &\text{Any $k$ blocks of size $\alpha$ have full rank $B$, and} \\
(2) &\text{Any $d+1$ blocks of size $\alpha$ satisfy parity checks of the form $H = H_{1\leq i,j \leq d+1}$, with} \\
      &\text{blocks $H_{i,j}$ of size $\alpha$ and of rank $\alpha$ on the diagional and of rank $\beta$ off the diagonal.}
\end{array}
\]
\end{proposition}

For a code with $n=d+1$, the construction of a regenerating code is equivalent to the construction of a square block matrix $H$ of size $d+1$ with blocks of size $\alpha$ and with rank distribution
\[
\left( \begin{array}{c|c|c|c}
\alpha &\beta  &\cdots &\beta \\ \hline
\beta  &\alpha &           &\beta \\ \hline
\vdots &           &\ddots &\vdots \\ \hline
\beta  &\beta   &\cdots &\alpha
\end{array} \right)
\]
such that columns in any $d-k+1$ blocks are independent (equivalent to (1)). For the special case $n=d+1,$ $k=d,$ the last condition is automatically fulfilled. Maximizing the rank $B$ is equivalent to minimizing the rank of the parity check matrix $H$.

\begin{example}
For a $(4,3,3)$ code with $\alpha=3, \beta=2$ we use
\[
H = \left( \begin{array}{ccc|ccc|ccc|ccc}
1&0&0 &0&1&0 &0&0&1 &0&0&0 \\
0&1&0 &0&0&1 &0&0&0 &1&0&0 \\
0&0&1 &0&0&0 &1&0&0 &0&1&0 \\ \hline
0&0&0 &1&0&0 &0&1&0 &0&0&1 \\
1&0&0 &0&1&0 &0&0&1 &0&0&0 \\
0&1&0 &0&0&1 &0&0&0 &1&0&0 \\ \hline
0&0&1 &0&0&0 &1&0&0 &0&1&0 \\
0&0&0 &1&0&0 &0&1&0 &0&0&1 \\
1&0&0 &0&1&0 &0&0&1 &0&0&0 \\ \hline
0&1&0 &0&0&1 &0&0&0 &1&0&0  \\
0&0&1 &0&0&0 &1&0&0 &0&1&0 \\
0&0&0 &1&0&0 &0&1&0 &0&0&1
\end{array} \right)
\]
The $4 \times 4$ blocks are all equal to the identity matrix and thus the matrix has rank four and its row space is spanned by the first four rows.
The code is the one used inthe introduction.
\end{example}

\begin{proposition}
For any $d \geq 3$, there exists a code with$n=d+1, k=d, d=d$ and $B=(d-1)(d+1), \alpha=d, \beta=(d-1)$. Thus $B=B_{k-1} < B_k, B_{k-2}.$
\end{proposition}

We restrict to the case $n=d+1$. Outer bounds obtained for $(n,k,d)$ codes apply to $(n'>n,k,d)$ codes.

\section{First outer bound} \label{S:4}

Let $S$ be a set of random variables, with each variable $X \in S$ of the form either $X = W_i$ or $X= S_i^j$. In the first case the entropy of $X$ is $H(W_i)=\alpha$ and in the second case it is $H(S_i^j) = \beta.$ The entropies $\alpha$ and $\beta$ serve as weights for the random variables in $S$ and the weight of $S$ is defined as $\sum_{X} H(X)$. By submodularity of the entropy function, the weight of $S$ is an upper bound for the entropy of $S$.

\begin{proposition} \label{chain}
Let $\{ A_i : 1 \leq i \leq n \}$ and $\{ a_i : 1 \leq i \leq n \}$ be two sequences of sets of random variables such that for $1 \leq i < j \leq n$,
\begin{align}
H(M|A_i,a_i) = 0,  \\
H(a_j|A_i) = 0,
\end{align}
Then
\[
n H(M) \leq \sum_{i=1}^n H(A_i) + H(a_1 \ldots a_n).
\]
In particular, for $H(a_n|a_1 \ldots a_{n-1}) = 0$,
\[
n H(M) \leq \sum_{i=1}^n H(A_i) +  \sum_{i=1}^{n-1} H(a_i).
\]
\begin{proof}
For $1 \leq i \leq n$,
\begin{align*}
H(M) &\leq H(A_i,a_i) \\
         &= H(A_i) + H(a_i|A_i) \\
         &\leq H(A_i) + H(a_i|a_{i+1} \cdots a_n) \\
\end{align*}
Finally, sum the $n$ inequalities and apply the chain rule.
\end{proof}
\end{proposition}

\begin{theorem} \label{thm-rs}
For given $k,d$, let $q,\ell,m$ be positive integers with $q+\ell+m \leq k$. Let $V_1,V_2,\ldots,V_{n-2}$ be subsets of $\{ \ell+m+1,\ldots,d+1 \}$ of size $q_i = |V_i| \leq k-\ell-m$ with empty intersection
$V_1 \cap V_2 \cap \cdots \cap V_{n-2} = \emptyset$. Then
\[
n B \leq B_q + \sum_{i=1}^{n-2} B_{q_i} + B_{\ell+m} - \ell m.
\]
\begin{proof}
For $d+1$ nodes $\{1,2,\ldots,d+1\}$, let $L = \{ 1,\ldots,\ell \}$, $M = \{ \ell+1,\ldots, \ell+m \}$, and denote by $U$ the set
 $\{ \ell+m+1,\ldots,d+1 \}$ . Let $U_1 \cup U_2 \cup \cdots \cup U_{n-2}$ be a partition of $U$ such that, for each $i$, $U_i \cap V_i = \emptyset$. The empty intersection of the $V_i$ guarantees that such a partition exists.
We apply the proposition with suitable choices for $\{ A_i : 1 \leq i \leq n \}$ and $\{ a_i : 1 \leq i \leq n \}$. Let
\[
a_i = S_{U_i}^M ~~(1 \leq i \leq n-3)
\]
and let
\[
a_{n-2} = S_{U_{n-2}}^M \cup S_M, ~~a_{n-1} = W_L, ~~a_n = S_M^L.
\]
For each $a_i$ we choose $A_i$ such that $A_i \cup a_i$ is a minimal configuration and in particular $H(M|A_i,a_i)=0$.
Recall from Section \ref{S:2} that a minimal configuration is determined by a partition $V' \cup M' \cup U'$. For $i=1,2,\ldots,n-2$, we choose
\[
V'= V_i, ~~M' \supset L \cup M, ~~U' \supset U_i.
\]
For $i=n-1$, $V'= L \cup M$ and for $i=n$, $M' \supset L, U' \supset M$. With these choices $H(a_j|A_i) = 0$ for
$1 \leq i < j \leq n$.
\end{proof}
\end{theorem}

\begin{corollary}
For $k=2p, d=3p$, $q=q_1=q_2=r+s=p$, it follows that $B \leq B_p - (p^2-1) \beta / 16$. This difference is unbounded as $p$ goes to infinity
\end{corollary}

Interpolation can be used to obtain similar estimates for other choices of parameters.

\begin{example}
The case $(4,3,3)$.
Let $k=3, d=3$. For $q=r=s=1$ and for $V_1 = \{1\}, V_2 = \{4\}$, $4B \leq 3 B_1 + B_2 - \beta$ we list four minimal configurations and their division into $A \cup a.$
\[
\begin{array}{llllllllll}
        V' &M' &U'  &~~ &A &~ &a \\ \hline
   1  &2,3 &4  & &W_1, ~S_3^2,~S_4^2 & &S_4^3  \\
  4  &2,3 &1  & &W_4,  ~S_3^2,~S_1^2 & &S_1^3  \\
   2,3  &4 &1  & &W_3,  ~S_4^1              & &W_2   \\
1  &2,3 &4  & &W_1,  ~S_4^2,~S_4^3 & &S_3^2
\end{array}

\]
The fourth row is used as an upper bound for $H(S_3^2)$ but we can avoid it and use $H(S_3^2) = \beta$. Then the bound becomes  $3B \leq 2 B_1 + B_2 - \beta.$ This improvement applies whenever the theorem is used with $\ell = m = 1.$
\end{example}

\begin{proposition} \label{P1}
For $2 \leq p \leq k-2$,
\[
3B \leq 2 B_p + B_{p\pm1} - \beta
\]
\begin{proof}
For both the plus sign and minus sign we partition $d+1$ nodes into $T \cup \ell \cup m \cup V \cup U$ and we fix an ordering on each of $T$, $V$ and $U$. For the plus sign we choose the sets of size $|T|=p-1$, $|V|=k-p-1 \geq 1$ and $|U|=d+1-k \geq 1$. Let $v \in V$ be the last element in $V$ and let $u \in U$ be the last element in $U$.
We apply Proposition $\ref{chain}$ with three minimal configurations. For each, we list $V'$, $M'$, $U'$ and $a$.
\[
\begin{array}{lclclclc}
V' & &M' & &U'  & &a \\ \hline
T,v  &~ &\ell, m, V \backslash v &~ &U &~~ &S_U^m \\
T,u &~  &\ell, m, V \backslash v &~ &v, U\backslash u &~~ &S_V^m, S_V \\
T,\ell,m &~ &V                           &~ &U &~~ &W_T, W_{\ell}
\end{array}
\]
For the minus sign we choose the sets of size $|T|=p-2$, $|V|=k-p \geq 2$ and $|U|=d+1-k \geq 1$.
Let $v, v' \in V$ be the last elements in $V$ and let $u \in U$ be the last element in $U$.
We apply Proposition $\ref{chain}$ with three minimal configurations. For each, we list $V'$, $M'$, $U'$ and $a_i$.
\[
\begin{array}{lclclclc}
V' & &M' & &U'  & &a \\ \hline
T,v,v'  &~ &\ell, m, V \backslash \{ v,v' \} &~ &U &~~ &S_U^m \\
T,u &~  &\ell, m, V \backslash v' &~ &v', U\backslash u &~~ &S_V^m, S_V \\
T,\ell,m &~ &V                           &~ &U &~~ &W_T, W_{\ell}
\end{array}
\]
\end{proof}
\end{proposition}

\begin{example} \label{E1}
For a $(8,6,7)$ code we apply the theorem with $q=r=s=2$, $V_1 = \{ 5,6 \}, V_2 = \{ 7,8 \}$. Then
\[
4 B \leq 3 B_2 + B_4 - 2 \cdot 2 \beta = 2 B_2 +  2 B_3 - 3 \beta = 10 \alpha + 43 \beta.
\]
This is less than the functional repair outer bound in the range $23 / 6 < \alpha / \beta < 37 / 6$.  The gap reaches a maximum at $\alpha= 5 \beta$  where it lowers the bound $B \leq 24 \beta $ by $3 \beta / 4$. We will compare this with other bounds in the next section.
\end{example}

\section{Second outer bound} \label{S:3}

In graph terms, we consider the complete graph on $d+1$ vertices, with edges $\{ W_i \}$ and $\{ S_i^j \}$. The variable $S_i^j$ connects node $i$ and node $j$. The variable $W_i$ connects node $i$ with node $i$ or, after creating two copies of node $i$, node $i$-in with node $i$-out. The sets $S$ define subgraphs with a block structure on the adjacency matrix. Connections between nodes can be interpreted as channels of bandwith $H(W_i)=\alpha$ or $H(S_i^j)=\beta$.

For a regenerating code with parameters $(n,k,d)$ the repair matrix for $d+1$ nodes is a square matrix of size $d+1$ that indicates which nodes function properly (a nonzero entry in the position $i,i$ for node $i$) and which nodes help other nodes (a nonzero entry in position $i,j$ for node $i$ helping node $j$) \cite{}. A minimal configuration has $q$ diagonal entries and $k-q$ nonzero columns. For $d=7, k=6, q=2,$
\[
\begin{array}{cccccc}
\ast \\
& \ast \\
& &- \\
& &\xb &- \\
& &\xb &\xb &- \\
& &\xb &\xb &\xb &- \\
& &\xb &\xb &\xb &\xb \\
& &\xb &\xb &\xb &\xb
\end{array}
\]
By replacing $\ast$ with $\alpha$ and $\xb$ with $\beta$, the configuration corresponds one-to-one to the adjacency matrix of an acyclic graph on $d+1$ vertices, with loops of weight $\alpha$ and other edges of weight $\beta$. It is common in this setting to think of a loop as an edge between two copies of the same node, an input node and an output node \cite{DGWWR10}. The total weight of the edges, or the weight of the configuration, is given by
\[
B_q = q\alpha +  \binom{k-q}{2} \beta + (d+1-k)(k-q) \beta.
\]
The information stored in node $i$ is modeled by the random variable $W_i$ and the helper information from node $i$ to node $j$ by the random variable $S_i^j$. The entropy of the random variables is bounded by $H(W_i) \leq \alpha$ and $H(S_i^j) \leq \beta$. The entropy of the message that a destination can recover from the configuration of nodes is bounded by the weight of the configuration. The minimal configurations give $H(M) \leq \min_q B_q$, the minimum taken over all $q \in \{0,1,\ldots,k\}$.

\bigskip

As observed in \cite{SRKR12a} and developed in \cite{SSK13}, variables $S_m^\ell$, $\ell \in L$,  in row $m$ of the configuration, all correspond to information from node $m$, i.e to information from a source of bounded entropy $H(W_i) \leq \alpha$. For $L$ large enough, some nonzero mutual information among the $S_m^\ell$, $\ell \in L$, is expected. This is captured by Proposition 2 in \cite{SSK13}. Equation (18) in the next to last line of the proof of Proposition 2 in \cite{SSK13} states that the sum of the entropies $H(W_R|W_m)$, $H(W_R)$ ($\ell-1$ times) and
$H(S^L_m),$ is stricly less than the trivial upper bound $\ell (r \alpha + \beta)$ whenever $\alpha > (d-r) \beta$. We use the claim with the singleton $m$ replaced by a set $M$ and adapt the proof.

\begin{proposition}[Equation (18) in Proposition 2 \cite{SSK13}] \label{P0}
Let $ L \subset R$, $R \cap M = \emptyset$, $|L|=\ell, |M|=m, |R|=r,$ $r+m \leq k$.
\[
H(W_R|W_M) + (\ell-1) H(W_R) + H(S^L_M) \leq \ell ( r \alpha + \beta) + \ell( (d-r)\beta-\alpha )
\]
\begin{proof}
Combine Equations (\ref{p21}) and (\ref{p22}).
\begin{align}
     H(W_R|W_M) + (\ell-1)H(W_R) + H(S^L_M)  \nonumber
\leq~ &H(W_R|S^L_M) + (\ell-1) H(W_R) + H(S^L_M) \nonumber \\
                       =~ &H(S^L_M|W_R) + H(W_R) + (\ell-1) H(W_R) \nonumber \\
                       \leq~ &\sum_{i \in L} ( H(S^i_M|W_R) + H(W_R) ). \label{p21}
\end{align}
For each $i \in L$,
\begin{align} H(S^i_M|W_R) + H(W_R)   \nonumber
                       =~ &H(W_i | W_{R\backslash i} S^i_M ) + H (W_{R\backslash i} S^i_M)   \nonumber \\
                       \leq~ &H(W_i | W_{R\backslash i} S^i_M ) +
                                H (W_{R\backslash i})  + H(S^i_M)   \nonumber \\
                       \leq~ &(d-r+1-m)\beta + (r-1) \alpha  + m \beta  \nonumber \\
                       =~ &(d-r)\beta-\alpha  +  r \alpha + \beta   \label{p22}

\end{align}
\end{proof}
\end{proposition}

Turning the proposition into an improved outer bound follows a standard procedure. In \cite{SSK13}, the improvement is applied, for given $\alpha$ and $\beta$, to the outer bound $B_p$ that is minimal, for the given $\alpha$ and $\beta$, among all $B_q$, $q=0,1,\ldots,k$.
This leaves open the possibility that the best overall outer bound for given $\alpha$ and $\beta$ comes from improving a $B_q$ different from $B_p$. For that reason we change the order and first collect a sequence of improved upper bounds and then address later which upper bound is optimal for which choice of $\alpha$ and $\beta$. Other differences will be pointed out after the statement of the theorem and illustrated by an example.

\bigskip

In the next thereom, the minimal configuration with $q$ intact nodes and $k-q$ nodes being repaired refers to the configuration at the beginning of the section. The region of helper information $S_i^j$ is bounded by
$q+1 \leq j \leq k$, $j < i \leq d+1$.

\begin{theorem} \label{thm-lm}
Let $\cup_{(M,L)} S_M^L$ be a disjoint union of the helper information in a minimal configuration with $q$ intact nodes and $k-q$ nodes being repaired.
For each $(M,L)$, let $\ell=|L|$, $|M|=m$, $r \geq \ell$. Then
\[
B + \sum_{(M,L)} \ell B  \leq B_q + \sum_{(M,L)} ( B_{r+m-1} + (\ell-1)(B_{r+m-2}-\beta) ).

\]

\begin{proof}
Let $\sum_{(M,L)} H(S_M^L)$ be a disjoint sum of the $S$ contributions to $B_q$.

\begin{equation}
B \leq B_q + \sum_{(M,L)} ( H(S_M^L) - \ell m \beta )  \qquad (\ell \leq k-q) \label{eq1}
\end{equation}
Fix a term $(M,L)$  and let $L \subseteq R$, $r = |R|$.
\begin{align}
B &\leq B_s + H(W_R) - r \alpha \qquad (s \geq r) \label{eq2}, \\
B &\leq B_t + H(W_R|W_M) + H(W_M) - (r+m)\alpha \qquad (t \geq r+m) \label{eq3}
\end{align}
\begin{align*}
B + \sum_{(M,L)} \ell B  &\leq
                          B_q + \sum_{(M,L)} ( B_{r+m-1} + (\ell-1)(B_{r+m-2}-\beta) ).
\end{align*}
\end{proof}
\end{theorem}

\begin{example} \label{E544}
For the $(5,4,4)$ code, Theorem \ref{thm-lm} yields the following upper bounds. Each upper bound is obtained as the average of the linear forms above it. Below each upper bound is the range for $\bar \alpha = \alpha / \beta$ where it is minimal among
the given six upper bounds.
\[
\begin{array}{lclcl}
\begin{array}{lll}
{} \\
B_4 &{} \\[1.5ex]
\end{array}
&\quad
&\begin{array}{lll}
{} \\
B_3 &{} \\[1.5ex]
\end{array}
&\quad
&\begin{array}{lll}
B_2 \\
B_3 &B_2^- \\[1.5ex]
\end{array} \\
\bar B \leq 4 \bar \alpha & &\bar B \leq 3 \bar \alpha + 1 & &\bar B \leq (7 \bar \alpha + 6) / 3 \\[1.5ex]
{\bar \alpha \in [0,1]} & &\bar \alpha \in [1,3/2] & &\bar \alpha \in [3/2,2] \\[3ex]
\begin{array}{lll}
B_1 \\
B_3 &B_2^{-} \\
B_3 &B_2^{-} &B_2^{-} \\[1.5ex]
\end{array}
&\quad
&\begin{array}{lll}
B_1 \\
B_2 &B_1^{-} \\
B_3 &B_2^{-} &B_2^{-} \\[1.5ex]
\end{array}
&\quad
&\begin{array}{lll}
B_1 \\
B_2 &B_1^{-} \\
B_2 &B_1^{-} &- \\[1.5ex]
\end{array} \\
\bar B \leq (13 \bar \alpha + 14 ) / 6  & &\bar B \leq (11 \bar \alpha + 19 ) / 6   & &\bar B \leq (7 \bar \alpha + 22 ) / 5 \\[1.5ex]
\bar \alpha \in [2,5/2] & &\bar \alpha \in [5/2,37/13] & &\bar \alpha \in [37/13,4]
\end{array}
\]
\end{example}

 The functional repair outer bound $B \leq \min B_q$ attains its minimum in $B \leq B_p$ on the interval $(d-p)\beta \leq \alpha \leq (d-p+1)\beta$. We give a short proof that the exact repair outer bound is strictly less than the functional repair outer bound for all $(d-k+3/2)\beta < \alpha < d \beta$. Let $\hat B = \min B_q$. We use Theorem \ref{thm-lm} to give a different proof of Proposition \ref{P1}.

\begin{proposition} \label{P2}
For $2 \leq p \leq k-2$,
\[
3B \leq 2 B_p + B_{p\pm1} - \beta
\]
Moreover,
\begin{align*}
&(1)~~2 B_p + B_{p+1} - \beta \leq 3 B_p - \beta/2,    \quad \text{for $(d-p) \leq \alpha \leq (d-p+1/2)\beta.$} \\
&(2)~~2 B_p + B_{p-1} - \beta \leq 3 B_p - \beta/2,  \quad \text{for $(d-p+1/2) \leq \alpha \leq (d-p+1)\beta.$}
\end{align*}
\begin{proof}
For $2 \leq p \leq k-2$, we apply the proposition with $q=p$, $\ell =2, r= p$ :
\[
3B \leq B_p + B_p + B_{p-1} - \beta
\]
or with $q=p$, $\ell =2, r= p+1$ :
\[
3B \leq B_p + B_{p+1} + B_p - \beta
\]
Inequality (1) follows from $B_{p+1}-B_p = \alpha - (d-p)\beta$ and Inequality (2) similarly from
$ B_{p-1}- B_p = (d-p+1)\beta - \alpha$. Together they proof $3B \leq 3 \hat B - \beta/2$ on the interval $(d-p) \leq \alpha \leq (d-p+1)\beta.$
Now take the union of the intervals for $2 \leq p \leq k-2$.
\end{proof}
\end{proposition}

The next Corollary follows from either Proposition \ref{P1} in the previous section or from Proposition \ref{P2} above. Thus, methods in either section can be used to prove a non-vanishing gap between the functional-repair and exact-repair outer bounds.

\begin{corollary}
As a result, the exact repair capacity $B$ of an $(n,k,d;B,\alpha,\beta)$ regenerating code satsfies
$B \leq \hat B- \beta/ 6$ on the interval $(d-k+2) \beta \leq \alpha \leq (d-1) \beta$.
\end{corollary}

\section{Using the bounds in combination} \label{S:5}

Theorem \ref{thm-rs} and Theorem \ref{thm-lm} give two different outer bounds for exact-repair regenerating codes. Both are linear and are valid in the full range of $\alpha / \beta$. Using the bounds with different choices for the parameters and then taking the minimum over all choices will produce a piece-wise linear upper bound for $B$. We provide some details on using the bounds in combination for the cases $(n,k,d)=(8,6,7)$ and $(n,k,d)=(5,4,4)$.

Figure 1 gives outer bounds for a $(8,6,7)$ code. They are presented as a trade-off between $\alpha/B$ and $\beta/B$ and are based on Theorem \ref{thm-lm}. In this case, the graph for the trade-off shows the differences more clearly than the upper bound graph with $B / \beta$ as a function of $\alpha / \beta$.

The lowest of the four outer bounds is the functional-repair outer bound $B \leq \min_q ( B_q : 0 \leq q \leq k ).$ Next we apply the theorem with the choices of \cite[Proposition 2 and Theorem 1]{SSK13}, i.e. $M = \{ m \}$ is a singleton and $\ell$ is fixed.
Next we allow choices with different $\ell$ and finally we allow $M$ of various sizes.

\begin{example}
We illustrate the improvements for $\alpha = 5 \beta.$ This corresponds to the vertex $B_3 = B_2$ in the functional-repair outer bound: $B \leq B_3 = 3 \alpha + 9 \beta$, $B \leq B_2 = 2 \alpha + 14 \beta.$ The various improvements are the following. In each case we use Theorem \ref{thm-lm}.

For $q=3$ and two choices with $\ell=3$, as in \cite[Proposition 2 and Theorem 1]{SSK13} :
\[
7 B \leq B_3 + 2 ( B_3 + B_2 + B_2 - 2\beta) =  4 B_2 + 3B_3 - 4.
\]
For $q=2$ and choices $\ell=2$ ($1 \times$) and $\ell=3$ ($3 \times$):
\[
12 B \leq B_2 + (B_3 + B_2 - \beta) + 3 ( B_3 + B_2 + B_2 - 2 \beta )  = 8 B_2 + 4 B_3 - 7.
\]
For a choice with $m > 1$, let $q=2$ and $\ell=2, m=2$ ($1 \times$) and $\ell=3, m=2$ ($1 \times$):
\[
6 B \leq B_2 + (B_4 + B_2 - 2 \beta) + (B_4 + B_2 + B_2 - 4 \beta) = 2 B_2 + 4 B_3 - 4.
\]
or
\[
6 B \leq B_2 + (B_3 + B_1 - 2\beta) + (B_4 + B_2 + B_2 - 4\beta) = 4 B_2 + 2 B_3 - 4.
\]
At $B_2 = B_3$, the gaps with the fractional-repair upper bound increase as $4/7 < 7/12 < 2/3$. But none reaches the gap of $3/4$ that was found in Example \ref{E1}, using Theorem \ref{thm-rs}:
\[
4 B \leq 2 B_2 +  2 B_3 - 3.
\]
\end{example}

\begin{example}
Example \ref{E544} lists upper bounds for a $(5,4,4)$ code that are obtained with Theorem \ref{thm-lm}. In particular,
\begin{equation} \label{B5}
5B \leq 7  \alpha + 22 \beta = 2 B_2 + 3 B_1 - 2 \beta.
\end{equation}
Here $B \leq B_1 = \alpha + 6 \beta$ and $B \leq B_2 = 2 \alpha + 3 \beta$. Theorem \ref{thm-rs} applied with
$r+s=3$ and $q=q_1=q_2=1$ gives
\[
4 B \leq 3 B_1 + B_3 - 2\beta  = 2 B_1 + 2 B_2 - \beta,
\]
which yields no improvement to the bounds listed in Example \ref{E544}. However, after exploiting nonzero mutual information among the $a_i$, the theorem uses trivial estimates for each of the $H(A_i)$. In this case, together the $A_i$ contain five copies of $S_m^L$, each with $\ell=2$. Using Proposition \ref{P0} we can therefore improve the last bound to
\[
4B + 5 \cdot 2B \leq  2 B_1 + 2 B_2 - \beta + 5 \cdot (B_1 + B_2 - \beta)
\]
0r
\begin{equation} \label{B14}
14 B \leq 7 B_1 + 7 B_2 - 6 \beta.
\end{equation}
Comparing (\ref{B14}) and (\ref{B5}) at $\alpha = 3 \beta$ ($B_1 = B_2$), $B \leq B_1 - 3/7 < B_1 - 2/5.$ And (\ref{B14}) improves on the bounds in Example \ref{E544} for $19/7 < \alpha/\beta < 23/7.$
\end{example}

\newpage

config: arxiv


TITLE: Simplification : $\biggl(\frac{ 1+x^2}{1-x^2}\biggr)^2 = \frac{1}{1-y^2}$
QUESTION [0 upvotes]: I am trying to simplify this expression by as usual the expansion way,
$$\biggl(\frac{ 1+x^2}{1-x^2}\biggr)^2 = \frac{1}{1-y^2}$$
After some steps I am getting:
$$4x^2 - y^2 - 2x^2y^2 - x^4y^2 = 0$$
The answer suggested in my module is $x^2y = 2x - y$
For the answer to be correct I think what I should get is
$$4x^2 - y^2 - 4xy - x^4y^2 = 0$$
What exactly I am doing wrong ? I tried to find an error in my solution, but unable to spot any(yet).
EDIT: For reference I am adding the other options mentioned the question (and now the question too):
if $4\biggl[\frac{x^2}{1} + \frac{x^{6}}{3}+ \frac{x^{10}}{5} + \cdots \biggr] = y^2 + \frac{y^4}{2} + \frac{y^6}{3} + \cdots $, then
$$x^2y = 2x+y \text{ or } x = 2y^2 - 1 \text{ or } x^2y = 2x + y^2$$

REPLY [3 votes]: HINT $\rm\quad\ 0 \ \ = \ \ (y^2-1)\ (1+x^2)^2 + (1 - x^2)^2$
$\rm\quad\quad\quad\quad\quad\quad\quad\ = \ \ y^2\:(1+x^2)^2 - 4\:x^2$
$\rm\quad\quad\quad\quad\quad\quad\quad\ =\ \ (y\:(1+x^2)-2\:x)\ \ (y\:(1+x^2)+2\:x)$


TITLE: What is the force between two charged objects when the space between them is partially filled by a dielectric medium?
QUESTION [21 upvotes]: I am given two charged particles of same charge at a distance of $r$. They initially apply force $F$.
Now an infinite dielectric (of dielectric constant $4$) of width $\frac{r}{2}$ is introduced between the particles. What will be the new force?
I find this problem confusing because I have only been told about forces when its either fully dielectric or fully vaccum given by Coulomb's law. How do we get forces when only partial space is dielectric?

REPLY [5 votes]: Boundary conditions on a dielectric are generally very complicated. While general ideas about how polarization works and affects the overall field can be talked about, the specifics of even simple cases can be too complicated to attempt properly.

So what is the deal with electric field near dielectrics?

Well to begin with I hope you have some general idea about field $\overrightarrow{D}$ (known as electric displacement vector) which is given by:
$$\overrightarrow{D}=\epsilon\epsilon_0\overrightarrow{E} + \overrightarrow{P}$$
Where P is the polarization vector which gives the general idea of dipole moment per unit volume of a dielectric. It has some special properties like its polarization density and relation with Gauss' law which make it useful to define.

Ok that's great, but why is D defined in such an arbitrary manner?

That's because combining the gauss law for P and E gives us a special property for the value
$$\oint(\epsilon\epsilon_0\overrightarrow{E}+\overrightarrow{P})\cdot \mathrm d\textbf{A}=q_\mathrm{free}$$
Where $q_\mathrm{free}$ is the free charges that have not originated due to polarization of the dielectric.Generally it is easier to deal with D and free charges than E and total charge.

How are these concepts important for the problem on hand?

$$\oint{\textbf{E}\cdot \mathrm d\textbf{l}}=0$$
$$\oint{\textbf{D}\cdot \mathrm d\textbf{A}}=q_{free}$$
These equations help us determine the boundary conditions for E and D near the boundaries of dielectrics, here vacuum helps making our calculation easier. This gives us a law reminiscent of Snell's law.
$$\frac{\tan\alpha_2}{\tan\alpha_1}=\frac{\epsilon_2}{\epsilon_1}$$

Solving the problem at hand

Now the more difficult part. Solving these cases would be complicated even with the new tools in our arsenal. We have 2 charges whose effect on the dielectric would vary the overall polarization of the slab. However, if we take an assumption that $q_1>>q_2$ this would help us solve the question without too much complication. This is because it lets us ignore the negligible polarization due to $q_2$ compared to $q_1$. (I couldn't solve the actual problem without this restriction but this may help.)

\begin{align}
\mathrm{O'C} &= \frac{\mathrm{AC}}{\tan \alpha_1} \\
&= \frac{(r-t)\tan \alpha_1 + t\tan \alpha_2}{\tan \alpha_1} \\
&= r - t + kt \\
&= r + (k-1)t \\
\end{align}
This derivation will give you the apparent distance between the 2 charges and hence the electric field of $q_1$ on $q_2$ (Please take care to remember the assumption $q_1 >> q_2$.)
P.S. If you want to learn more about dielectric theory I suggest you check out Basic Laws of Electromagnetism Chapter 3 for a shorter summary or Purcell and Morin Chapter 10 for a more in-depth explanation. I cannot rigorously prove the equations or explain the full topic here since it is a vast thing in its entirety, so it would be a good idea to check these resources out.


text:
\begin{document}

\begin{center}

{\large ON THE TOPOLOGICAL INTERPRETATION OF GRAVITATIONAL ANOMALIES}
\vskip 1cm
{\bf Denis PERROT\footnotemark[1]}
\vskip 0.5cm
Centre de Physique Th\'eorique, CNRS-Luminy,\\ Case 907,
F-13288 Marseille cedex 9, France \\[2mm]
{\tt perrot@cpt.univ-mrs.fr}
\end{center}
\vskip 1cm
\begin{abstract}
We consider the mixed gravitational-Yang-Mills anomaly as the coupling between
the $K$-theory and $K$-homology of a $C^*$-algebra crossed product. The index
theorem of Connes-Moscovici allows to compute the Chern character of the
$K$-cycle by local formulae involving connections and curvatures. It gives a
topological interpretation to the anomaly, in the sense of noncommutative
algebras.
\end{abstract}

\vskip 1cm

\noindent {\bf MSC91:} 19D55, 81T13, 81T50\\

\noindent {\bf Keywords:} $K$-theory, cyclic cohomology, gauge theories.\\

\footnotetext[1]{Allocataire de recherche MENRT.}

\section{Introduction}

In a previous paper \cite{P} we proved a formula computing the topological
anomaly of gauge theories, in the very general framework on noncommutative
geometry \cite{C2}. This formula reduces just to the pairing between the
$K$-theory classes of loops in the gauge group, and some $K$-homology classes
arising from abstract Dirac-type operators. This simple remark allows one to
compare the usual BRS machinery with cyclic cohomology \cite{C2}. Both are
nontrivial as {\it local} cohomologies, but we feel that cyclic cohomology is
more suitable since it can be directly related to the {\it analytic} content of
the Dirac-type operator via the Chern character, whereas BRS cohomology has no
obvious link with index theory in general.\\

In this paper we want to apply the topological anomaly formula in the mixed
gravitational-Yang-Mills case, i.e. when the gauge group is the crossed product
of Yang-Mills transformations on a manifold $X$ with a group of diffeomorphisms
acting on $X$. Here the Chern character of the $K$-cycle involved takes its
values in the cyclic cohomology of an algebra crossed product. The local index
theorem of Connes-Moscovici \cite{CM98} then expresses this Chern character in
terms of Gelfand-Fuchs cohomology. We shall compute it by connections and
curvatures, and see that it gives expressions very similar to the usual ones
encountered in the (BRS) study of gravitational anomalies. However there is an
essential difference here: ordinary BRS methods deal with {\it Lie algebra}
cohomology, whereas the characteristic classes for crossed products involve {\it
group} cohomology. Of course both are related by van Est type theorems, but we
insist on the fact that group considerations can describe gravitational
anomalies topologically, as the pairing of nontrivial cyclic cocycles with the
$K$-theory of a (noncommutative) algebra crossed product.\\

The paper is organized as follows. In section 2 we recall the anomaly formula
in the case of Yang-Mills theories, with particular emphasis on its link with
Bott periodicity, and we improve it by taking the diffeomorphisms into
account.\\
In section 3 we present a relatively self-contained collection of some
classical results of Bott and Haefliger \cite{Bo,H} concerning equivariant
cohomology and Gelfand-Fuchs cohomology, and apply it to the Connes-Moscovici
index theorem for crossed products.\\
In the last section we illustrate these tools by the study of conformal
transformations on a Riemann surface. This gives rise to a nontrivial cyclic
cocycle, corresponding to a conformal anomaly.

\section{The anomaly formula}

\subsection{Yang-Mills anomalies}

Let $X$ be an even-dimensional oriented smooth manifold, $C_0(X)$ the
$C^*$-algebra of continuous complex-valued functions vanishing at infinity. We
consider a $K$-cycle over $X$. For concreteness, let us take the signature
complex: endow $X$ with a Riemannian metric and let $H=H_+\oplus H_-$ be the
Hilbert space of $L^2$ differential forms on $X$, with $\zz_2$-graduation given
by self- and anti-selfduality. The elliptic signature operator ${D}=d+d^*$ acts
on a dense domain of $H$ as an odd unbounded selfadjoint operator. The pair
$(H,{D})$ defines in this way a $K$-homology class $[{D}]\in K^*(C_0(X))$.\\
A typical situation in Qantum Field Theory is the following. Let $N$ be a
positive integer, and consider the group $G=U_N(\cinfc(X))$ of $N\times N$
unitary matrices with entries in the algebra of smooth compactly supported
functions $\cinfc(X)$. It is the group of Yang-Mills transformations, with
structure group $U_N$ (if $X$ is not compact, one should add a unit). $G$ acts
on the tensor product $H\otimes \cc^N$ by even bounded endomorphisms. In general
the elliptic operator comes equipped with a Yang-Mills connection $A$,
\be
{D}_A={D}+A
\ee
which transforms under the gauge group according to the adjoint representation:
\beq
{D}_A&\rightarrow& u^{-1}{D}_Au\qquad\qquad u\in G\non\\
A&\rightarrow& u^{-1}Au+u^{-1}[{D},u]\ .
\eeq
As we work with $\zz_2$-graded spaces we adopt the usual matricial notation
\be
{D}_A=\left(\begin{array}{cc}
  0 & {D}_A^- \\
 {D}_A^+ & 0  \end{array}\right)\qquad
u=\left(\begin{array}{cc}
  u_+ & 0 \\
  0 & u_-  \end{array}\right)\qquad
H=\left(\begin{array}{c}
  H_+  \\
  H_-  \end{array}\right)\ .
\ee
Consider now the chiral action
\be
S(\psi_+,\psi_-,A)=\langle \psi_-,{D}_A^+\psi_+\rangle\qquad \psi_{\pm}\in
H_{\pm}\ .
\ee
If we quantize the fields $\psi_{\pm}$ according to the Fermi statistics, then
the vacuum functional
\be
Z(A)=\int [d\psi]\ e^{-S(\psi_+,\psi_-,A)}
\ee
is simply given by a regularized determinant $\det {D}_A^+$, see \cite{Si} (for
the Bose statistics one takes the inverse determinant). In general it is not
invariant under the gauge group, i.e.
\be
\det {D}_A^+ \neq \det (u^{-1}{D}_Au)^+\ .
\ee
Define the loop group $G^{S^1}$ as the set of smooth maps
\be
g: S^1\rightarrow U_N(\cinfc(X))
\ee
with base-point the identity. The product is pointwise. Let $t\in [0,2\pi)$ be
the coordinate on $S^1$. Given a loop $g\in G^{S^1}$ the determinant $Z(t)=\det
(g^{-1}(t){D}_Ag(t))^+$ is an invertible $\cc$-valued function on $S^1$ and the
topological anomaly is just the winding number
\be
w={1\over{2\pi i}}\int_{S^1} {{d Z(t)}\over{Z(t)}}\quad\in\zz\ .
\ee
The anomaly formula of \cite{P} relates it to the $K$-cycle $[{D}]$ as follows.
First the loop group $G^{S^1}$ may be identified with $U_N(\cinfc(S^1\times
X))$. Then any element $g$ in the loop group determines a class $[g]$ of the
$K$-theory group $K_1(C_0(S^1\times X))$. The operator
\be
Q=\left(\begin{array}{cc}
  i\d_t & {D}_A^- \\
 {D}_A^+ & -i\d_t  \end{array}\right) \label{k}
\ee
acting on sections of the Hilbert bundle $H\times S^1$, represents an odd
$K$-cycle for the $C^*$-algebra $C_0(S^1\times X)$. Let $\ch_*(Q)$ be its Chern
character \cite{C2} in the odd cyclic cohomology of $\cinfc(S^1\times X)$. One
has a well-defined, homotopy-invariant, integral pairing
\be
w=\langle [g], \ch_*(Q)\rangle\ \in\zz\label{aa}
\ee
computing the value of the topological (Yang-Mills) anomaly on the loop $g$
\cite{P}.\\

Observe that in (\ref{aa}) any reference to the connection $A$ disappears. It is
a purely topological formula involving the $K$-homology class of $Q$ and the
$K$-theory element $[g]$. In particular if the first homotopy group of
$U_N(C_0(X))$ is zero, then any loop $g$ is contractible and its image $[g]$
vanishes in $K_1(C_0(X\times S^1))$. By increasing $N$ we may eventually choose
nontrivial loops detected by $Q$, which is really the essence of $K$-theory.\\
In \cite{P} we established the anomaly formula in a more general setting,
allowing for $X$ to be a noncommutative ``space'' described by an associative
algebra $\Ac$ together with an even Fredholm module $(H,D)$ \cite{C2} playing
the role of the previous elliptic operator. Our goal in the following is to
apply these ideas in the case of gravitational theories, where the gauge group
contains the diffeomorphisms $\mbox{Diff}(X)$ of the manifold $X$. The relevant
space is the groupoid $X\cp\mbox{Diff}(X)$, which is highly noncommutative in
nature.\\

\subsection{The gravitational case}

We thus implement the above construction by taking the diffeomorphisms of $X$
into account. The group of mixed Yang-Mills $\cp$ gravitational transformations
is the crossed product $U_N(\cinfc(X))\cp\mbox{Diff}(X)$, which lies in the
matrix algebra of $\Ac=\cinfc(X)\cp\mbox{Diff}(X)$. The associative algebra
$\Ac$ is generated by the symbols
\be
a=f U^*_{\psi}\qquad f\in\cinfc(X)\ ,\quad \psi\in\mbox{Diff}(X)\ ,
\ee
with product rule
\be
(f_1U^*_{\psi_1})(f_2U^*_{\psi_2})=f_1(f_2\circ\psi_1)U^*_{\psi_2\psi_1}\ ,
\ee
where $f_2\circ \psi_1$ is the pullback of $f_2$ by $\psi_1$. Since we are
mostly concerned with $K$-theory, we shall enlarge this group to all invertible
elements $Gl_N(\Ac)$ as well. Thus we are dealing with transformations involving
matrices of diffeomorphisms. The physical interpretation seems obscure at first
sight, but our motivation comes from the fact that the group $\mbox{Diff}(X)$
does not generally contain enough nontrivial loops. We shall see in the
following that provided we consider matrix algebras, in the same philosophy as
in the Yang-Mills case, the anomaly formula detects nontrivial topological
objects related to diffeomorphisms. Let us explain carefully the construction in
this case.\\

Let $\mbox{Diff}(S^1,X)$ denote the subgroup of $\mbox{Diff}(S^1\times X)$
consisting in diffeomorphisms $\psi$ such that
\be
pr\circ \psi =pr\ ,
\ee
where $pr:S^1\times X\rightarrow S^1$ is the projection onto the first factor.
Then $\mbox{Diff}(S^1,X)$ plays the role of the loop group of $\mbox{Diff}(X)$.
Thus we identify the loop group of $Gl_N(\Ac)$ with $Gl_N(\cinfc(S^1\times
X)\cp\mbox{Diff}(S^1,X))$.\\

From now on put $M=S^1\times X$. For the sake of definiteness, let $\Gamma$ be a
discrete countable subgroup of $\mbox{Diff}(S^1,X)$. We choose the loops as
elements of $Gl_N(\cinfc(M)\cp\Gamma)$ and consider their images in the group
$K_1$ of the $C^*$-algebra $C_0(M)\cp\Gamma$. As before we would like to
evaluate these $K$-theory classes on some $K$-cycle $Q$. The previous signature
operator is not suitable in this case because it does not define a $K$-cycle for
$C_0(M)\cp\Gamma$. This problem is solved as in \cite{CM95} by passing to the
bundle $P$ over $M$, whose fiber at $x\in M$ is the set of all euclidian metrics
on the tangent space $T_xM$. $\Gamma$ acts canonically on $P$ and the $K$-theory
of $C_0(M)\cp\Gamma$ lifts through the Thom map of \cite{C1}:
\be
\beta: \ K_*(C_0(M)\cp\Gamma)\rightarrow K_*(C_0(P)\cp\Gamma)\ .
\ee
On this bundle $P$ of metrics one can construct a differential operator $Q$
representing a $K$-cycle for $C_0(P)\cp\Gamma$, playing the role of the
signature class \cite{CM95}. If we let $\ch_*(Q)$ be its Chern character in the
cyclic cohomology of $\cinfc(P)\cp\Gamma$, the anomaly formula amounts to the
computation of
\be
\langle \beta([g]), \ch_*(Q)\rangle\ ,\qquad [g]\in K_1(C_0(M)\cp\Gamma)
\label{ano}
\ee
for any loop $g$. In the following sections we shall use the index theorem of
Connes-Moscovici \cite{CM98} to express $\ch_*(Q)$ as an equivariant cohomology
class. The latter is constructed from connections and curvatures in great
analogy with the usual expressions of gravitational anomalies found in the
literature. This together with the nontriviality of $\ch_*(Q)$ gives an
interesting $K$-theoretical interpretation of these anomalies.\\

\subsection{Remark on Bott periodicity}

Note that in the context of $C^*$-algebras, the pure Yang-Mills anomaly has a
simple interpretation in terms of Bott periodicity (\cite{Bl} \S 9). Indeed the
set of homotopy classes of loops in $U_{\infty}(C_0(X))$ with base-point 1 is
isomorphic to the group $K_1$ of the suspension of $C_0(X)$. Moreover the
product in the loop group of $U_{\infty}(C_0(X))$ can eventually be taken as the
concatenation of loops, so that
\be
\pi_1(U_{\infty}(C_0(X)))\simeq K_1(C_0(X\times \rr))\ ,
\ee
and Bott periodicity stands for the isomorphism
\be
\te : \ K_0(C_0(X))\rightarrow K_1(C_0(X\times\rr))\ .
\ee
Also the Chern character of the differential operator (\ref{k}) is just the cup
product
\be
\ch_*(Q)=\ch_*(D) \# [S^1]
\ee
between $\ch_*({D})$ in the cyclic cohomology of $\cinfc(X)$ and the fundamental
class of the circle. Hence one has an equality (see e.g. \cite{C2} p. 225 prop.
3 c))
\be
\langle [g], \ch_*(Q)\rangle =\langle \te^{-1}([g]),\ch_*({D})\rangle
\ee
for any loop $g\in G^{S^1}$. It follows that the evaluation of the Yang-Mills
anomaly on a loop in the gauge group $U_{\infty}(\cinfc(X))$ is {\it equivalent}
to the coupling between the $K$-theory of $X$ and the $K$-homology class $[D]$.
This interpretation does not hold true for the gravitational anomaly because
$C_0(M)\cp\Gamma$ is not the suspension of a $C^*$-algebra in general.

\section{Characteristic classes for crossed products}

In this section we recall basic facts about equivariant cohomology and
Gelfand-Fuchs cohomology. Most of this material can be found in Bott-Haefliger
\cite{Bo,H}. It allows to compute the characteristic classes of the crossed
product $M\cp\Gamma$ appearing in the Connes-Moscovici index theorem
\cite{CM98}, in terms of connections and curvatures.\\

\subsection{Equivariant cohomology}

Let $M$ be an oriented manifold, and $\Gamma$ a discrete group acting on $M$ by
orientation-preserving diffeomorphisms. In the following we will not distinguish
an element $g$ of $\Gamma$ and the corresponding diffeomorphism.\\
The space of homogeneous cochains of bidegree $n,m$ is zero if $n<0$ or $m<0$,
otherwise it is the space $C^{n,m}(M)$ of maps $u$  from $\Gamma^{n+1}$ to the
differential forms $\Om^m(M)$ of degree $m$ on $M$, subject to the equivariance
condition
\be
u(g_0g,...,g_ng)=u(g_0,...,g_n)\circ g\ ,\qquad g_i,g\in\Gamma\ ,
\ee
where $\circ g$ denotes the pullback by the diffeomorphism $g$. On the complex
$C^{*,*}$ one defines two differentials. The first one $\delta :
C^{n,m}\rightarrow C^{n+1,m}$ is the simplicial differential
\be
(\delta u)(g_o,...,g_{n+1})= (-)^m\sum_{i=0}^{n+1}(-)^i
u(g_0,...,\stackrel{\vee}{g_i},...,g_{n+1})\ ,
\ee
where $^{\vee}$ denotes omission. The second one $d:C^{n,m}\rightarrow
C^{n,m+1}$ is the de Rham coboundary
\be
(du)(g_0,...,g_n)= d(u(g_0,...,g_n))\ .
\ee
The signs are chosen so that $d^2=\delta^2=d\delta+\delta d=0$. Geometrically,
the total complex $(C^{*,*},d+\delta)$ describes the complex of cochains on the
homotopy quotient $M_{\Gamma}=M\times_{\Gamma} E\Gamma$. By definition its
cohomology is the {\it equivariant cohomology} $H^*(M_{\Gamma})$ of $M$.\\

It will be convenient for us to consider the following ring structure on
homogeneous cochains. For $u\in C^{n,m}$ and $v\in C^{p,q}$, the product $uv\in
C^{n+p,m+q}$ is
\be
(uv)(g_0,...,g_{n+p})= (-)^{nq}u(g_0,...,g_n)v(g_n,...,g_{n+p})\ .
\ee
This product is associative and compatible with equivariance. Moreover the
Leibniz rule is satisfied:
\beq
d(uv)&=& du\, v +(-)^{n+m}u\, dv\non\\
\delta(uv)&=& \delta u\, v+(-)^{n+m}u\, \delta v\ ,
\eeq
with $n+m$ the total degree of $u$. Thus $(C^{n,m},d+\delta)$ is a graded
differential algebra.\\

Recall also \cite{H} that the above complex of homogeneous cochains is
isomorphic to the complex of group cochains $C^*(\Gamma, \Om^*(M))$ with
coefficients in the differential forms of $M$. To $u\in C^{n,m}(M)$ corresponds
the group cochain $f\in C^n(\Gamma,\Om^m(M))$:
\be
f(g_1,...,g_n):= u(g_1...g_n,g_2...g_n,...,g_n,1)\ ,\label{b}
\ee
and the associated coboundary operator $\delta: C^n(\Gamma,\Om^m)\rightarrow
C^{n+1}(\Gamma,\Om^m)$ reads
\beq
\delta f (g_1,...,g_{n+1})&=& f(g_2,...,g_{n+1})
+\sum_{i=1}^{n}(-)^if(g_1,...,g_ig_{i+1},...,g_{n+1})\non\\
&& + (-)^{n+1}f(g_1,...,g_n)\circ g_{n+1}\ .
\eeq

\subsection{Jet bundles}

Let $n$ be the dimension of the manifold $M$. Let $J^+_k$ be the space of
$k$-jets of orientation-preserving diffeomorphisms
\be
j: \rr^n\rightarrow M
\ee
from a neighborhood of $0$ in $\rr^n$ to $M$. Given a local coordinate system
$\{x^{\mu}\}_{\mu=1,...,n}$ on $M$, $J^+_k$ has coordinates
$\{x^{\mu},y^{\mu}_i,y^{\mu}_{i_1i_2},...,y^{\mu}_{i_1...i_k}\}$ corresponding
to the jet
\be
j^{\mu}(u)= x^{\mu}+ y^{\mu}_i u^i + {1\over 2}y^{\mu}_{ij}u^iu^j
+\cdot\cdot\cdot + {1\over{k!}}y^{\mu}_{i_1...i_k}u^{i_1}...u^{i_k}\ ,\qquad
u\in\rr^n\ .
\ee
In particular the matrix $(y^{\mu}_i)$ belongs to $Gl^+_n(\rr)$, and the real
numbers $y^{\mu}_{i_1...i_l}$ are symmetric in low indices.\\

$J^+_k$ is a principal bundle over $M$ with structure group $G^k$ consisting in
the set of $k$-jets $h$ fixing $0$: $h^{\mu}(0)=0$. The right action of $G^k$ on
$J^+_k$ is simply the composition of jets:
\be
j\rightarrow j\circ h\ ,\qquad j\in J^+_k\ ,\ h\in G^k\ .
\ee
Since any $(k+1)$-jet yields a $k$-jet, $J^+_{k+1}$ is a principal bundle over
$J^+_k$ with structure group the kernel of the projection $G^{k+1}\rightarrow
G^k$. We get in this way a tower of bundles
\be
\cdot\cdot\cdot \rightarrow J^+_k\rightarrow \cdot\cdot\cdot\rightarrow J^+_1
\rightarrow M\ .
\ee
We write the inverse limit $J^+_{\infty}$. Note that $J^+_1$ is the bundle of
oriented frames on $M$.\\

The action of $\Gamma$ on $M$ lifts on $J^+_k$ by left composition of jets
\be
j\rightarrow g\circ j\ ,\qquad j\in J^+_k\ ,\ g\in\Gamma
\ee
and clearly commutes with $G^k$. In particular the group $SO_n\subset Gl^+_n$
sits in $G^k$ as a maximal compact subgroup and $\Gamma$ still acts on the
quotient $P_k=J^+_k/SO_n$, which is a bundle with contractible fiber over $M$.
The action of an element $a\in SO_n$ is given by the right composition by the
jet
\be
h^i(u)=a^i_j u^j\ ,\qquad u\in \rr^n\ ,
\ee
where $a=(a^i_j)$ is a matrix in $SO_n$. Explicitly the vertical coordinates of
a point in $J^+_k$ change according to the rule
\be
y^{\mu}_{i_1...i_l}\rightarrow y^{\mu}_{j_1...j_l}a^{j_1}_{i_1}...a^{j_l}_{i_l}\
.
\ee
Thus one has a tower of bundles with contractible fiber
\be
\cdot\cdot\cdot \rightarrow P_k\rightarrow \cdot\cdot\cdot\rightarrow P_1
\rightarrow M\ ,
\ee
with inverse limit $P_{\infty}$. Remark that $P_1$ is the bundle of metrics over
$M$. Since $\Gamma$ lifts on each $P_k$, the homotopy quotient
$P_{k,\Gamma}=P_k\times_{\Gamma}E\Gamma$ is a bundle over $M_\Gamma$ with
contractible fiber, which induces an isomorphism in equivariant cohomology,
\be
H^*(P_{k,\Gamma})\simeq H^*(M_{\Gamma})\ ,
\ee
and also for the limit $H^*(P_{\infty,\Gamma})$.\\

\subsection{Gelfand-Fuchs cohomology}

Given a coordinate chart $\{x^{\mu},y^{\mu}_i,...,y^{\mu}_{i_1...i_k},...\}$, we
identify {\it locally} $J^+_{\infty}$ with the pseudogroup of all
diffeomorphisms $\rr^n\rightarrow \rr^n$. Its Lie algebra $\goth{a}$ corresponds
to the formal vector fields of $\rr^n$. Let $\Om_{inv}^*(J^+_{\infty})$ be the
complex of invariant forms under the left action of Diff$(M)$ on jets by
composition
\be
j\rightarrow \varphi\circ j\ ,\qquad \varphi\in \mbox{Diff}(M)\ .
\ee
It is naturally isomorphic to the complex of Lie algebra cochains
$C^*(\goth{a},\rr)$. An algebraic basis of $\mbox{Diff}(M)$-invariant forms on
$J^+_{\infty}$ is provided by expanding the Maurer-Cartan form ``$j^{-1}\circ
dj$'' in powers of $u\in\rr^n$:
\be
(j^{-1}\circ dj)^i(u)= \te^i+\te^i_j u^i+ {1\over 2}\te^i_{jk}u^ju^k
+...+{1\over{k!}}\te^i_{j_1...j_k}u^{j_1}...u^{j_k}+... \ .
\ee
Due to the $\mbox{Diff}(M)$-invariance, the one-forms $\te$ are globally defined
on $J^+_{\infty}$. Actually $\te^i_{j_1...j_k}$ is already defined on
$J^+_{k+1}$. For example
\be
\te^i= (y^{-1})^i_{\mu}dx^{\mu}
\ee
lies on $J^+_1$ (here $((y^{-1})^i_{\mu})$ is the inverse matrix of
$(y_i^{\mu})$),
\be
\te^i_j= (y^{-1})^i_{\mu}dy^{\mu}_j-
y^{\mu}_{jk}(y^{-1})^i_{\mu}(y^{-1})^k_{\nu}dx^{\nu}
\ee
lies on $J^+_2$, and so on. Thus the Gelfand-Fuchs cohomology
$H^*(\goth{a},\rr)$ is naturally isomorphic to the cohomology of invariant forms
$H^*(\Om_{inv}^*(J^+_{\infty}))$. It is computed as follows \cite{G}. The group
$Gl_n(\rr)$ acts on $\rr^n$ be linear diffeomorphisms. Let
$\goth{g}\subset\goth{a}$ be its the Lie algebra. The Weil algebra associated to
$\goth{g}$ is the tensor product
\be
W=\wedge \goth{g}^*\otimes S(\goth{g}^*)
\ee
of the exterior algebra on the dual space $\goth{g}^*$ of $\goth{g}$, by the
symmetric algebra $S(\goth{g}^*)$. $W$ is a graded differential algebra: it is
generated by the elements of degree 1
\be
\om^i_j\in \wedge^1\goth{g}^*
\ee
of the canonical basis of $\goth{g}^*$ and
\be
\Om^i_j\in S^1(\goth{g}^*)
\ee
of degree 2. A differential $d_W$ is uniquely defined by
\beq
d_W\om^i_j&=& \Om^i_j-\om^i_k\om^k_j\ ,\non\\
d_W\Om^i_j&=& \Om^i_k\om^k_j-\om^i_k\Om^k_j\ .
\eeq
Next we consider $\te^i_j$ as the coefficients of a connection 1-form on
$\goth{a}$ with values in $\goth{g}$, and its curvature
\be
R^i_j = d\te^i_j+\te^i_k\te^k_j\ .
\ee
Then from Chern-Weil theory one has a morphism
\be
\psi: W\rightarrow \Om^*_{inv}(J^+_{\infty})
\ee
which sends $\om^i_j$ onto $\te^i_j$ and $\Om^i_j$ onto $R^i_j$. Furthermore the
2-form $R^i_j$ is proportional to $dx^{\mu}$ and hence any polynomial in $R$ of
degree $>n$ vanishes. It follows that $\psi$ factorises through $W_n$, the
quotient of $W$ by the differential ideal generated by the elements in
$S(\goth{g}^*)$ of degree $>2n$. The first result of Gelfand-Fuchs is \cite{G}

\begin{theorem}
The map $\psi: W_n\rightarrow \Om^*_{inv}(J^+_{\infty})$ induces an isomorphism
in cohomology.
\end{theorem}

This theorem also admits a version relative to the action of $SO_n$ on
$\goth{a}$. The complex of $SO_n$-basic cochains $C^*(\goth{a},SO_n)$ is
naturaly isomorphic to the invariant forms on $P_{\infty}=J^+_{\infty}/SO_n$.
Since $SO_n\subset Gl_n$, $W_n$ is a $SO_n$-algebra. Let $WSO_n$ be its
subalgebra of basic elements relative to the action of $SO_n$. Then $\psi$ maps
$WSO_n$ to $\Om^*_{inv}(P_{\infty})$ and one has \cite{G}

\begin{theorem}
The map $\psi$ induces an isomorphism
\be
H^*(WSO_n)\simeq H^*(\Om^*_{inv}(P_{\infty}))\ .
\ee
\end{theorem}

Next we want to send these classes into the equivariant cohomology of $M$.
Remark that there is an injection
\be
i: \Omega^m(P_{\infty})\rightarrow C^{0,m}(P_{\infty})\ ,
\ee
which to any (non necessarily invariant) differential form $\al$ on $P_{\infty}$
associates the homogeneous 0-cochain
\be
\al(g_0):= \al\circ g_0\ ,\qquad \forall g_0\in\Gamma\ .
\ee
It is clear that under this map the image of a closed form in
$\Om^*_{inv}(P_{\infty})$ is both $d$- and $\delta$-closed, and hence defines an
equivariant cohomology class on $P_{\infty,\Gamma}$. Thus one gets a canonical
map
\be
H^*(WSO_n)\rightarrow H^*(P_{\infty,\Gamma})\simeq H^*(M_{\Gamma})\ .
\ee
Note finally that the image of $WSO_n$ by $\psi$ lives in $P_2=J^+_2/SO_n$ since
the forms $\te^i_j$ and $R^i_j=d\te^i_j+\te^i_k\te^k_j$ are defined on $J^+_2$.
It is then sufficient to work on $P_2$ instead of $P_{\infty}$.\\

\subsection{Computation of $H^*(WSO_n)$}

We restrict to the case of a manifold $M$ of {\it odd} dimension $n$. In the
truncated Weil algebra $W_n$, the Chern classes $c_i$, $i=1...n$, correspond to
the terms of degree $2i$ in the determinant of the $n\times n$ matrix $1+\Om$.
In particular:
\be
c_1=\Om^i_i\ ,\qquad c_2={1\over 2}((\Om^i_i)^2-\Om^i_j\Om^j_i)\ ,\qquad
c_n=\det\Om\ .
\ee
For $i$ odd one can choose an element $u_i$ of degree $2i-1$ in $WSO_n$ such
that $d_Wu_i=c_i$. Let $E(u_1,u_3,...,u_n)$ be the exterior algebra in the
$u_i$, $i$ odd $\le n$, and $\rr[c_1,c_2,...,c_n]$ the algebra of polynomials in
all the $c_i$ quotiented by the ideal of elements of degree strictly higher than
$2n$. The tensor product
\be
WU_n= \rr[c_1,...,c_n]\otimes E(u_1,...,u_n)
\ee
is endowed with the differential $d$ such that $du_i=c_i$. Then one has \cite{G}

\begin{theorem}
The inclusion $WU_n\rightarrow WSO_n$ induces an isomorphism in cohomology.
\end{theorem}

In particular if we define the Pontrjagin classes
\be
p_i=c_{2i}\qquad \forall i\le {{n-1}\over 2}\ , \ n\ \mbox{odd}
\ee
then $H^*(WSO_n)$ always contains the polynomial algebra
$\rr[p_1,p_2,...]_{trunc}$ in the $p_i$'s truncated by the elements of degree
$>2n$.\\

\subsection{The Connes-Moscovici index theorem}

Let $P=P_1$ be the bundle of metrics over the odd-dimensional manifold $M$. On
$P$ the hypoelliptic signature operator $Q$ of \cite{CM95} defines a $K$-cycle
for the algebra $C_0(P)\cp\Gamma$. By \cite{C2} $\S$ III.2.$\delta$ one has an
injective map
\be
\Phi: H^*(P\times_{\Gamma}E\Gamma)\hookrightarrow HC^*_{per}(\cinfc(P)\cp\Gamma)
\ee
from equivariant cohomology to the periodic cyclic cohomology of the crossed
product $\cinfc(P)\cp\Gamma$. The index theorem of \cite{CM98} states that the
Chern character $\ch_*(Q)\in HC^*_{per}(\cinfc(P)\cp\Gamma)$ is in the range of
Gelfand-Fuchs cohomology. Actually $\ch_*(Q)$ has a preimage in the Pontrjagin
ring $\rr[p_1,p_2...]_{trunc}$. \\
If we apply this construction to the situation of section 2, where $M=S^1\times
X$ and $\Gamma$ is a loop group of diffeomorphisms on $X$, the complete
computation of the anomaly formula (\ref{ano})
\be
\langle \beta([g]), \ch_*(Q)\rangle\qquad [g]\in K_1(C_0(M)\cp\Gamma)
\ee
yields an expression containing the image of the Pontrjagin classes in
$H^*(M_{\Gamma})$ and other characteristic classes accounting for the Thom
isomorphism $\beta$. In the following section we compute the image of the
Pontrjagin ring in the particular case of Riemann surfaces and conformal
transformations, and see that the result looks like familiar gravitational
anomalies. The same holds clearly true in the general case.

\section{Application to Riemann surfaces}

Let us have a look at the simplest example. We take $M$ as the product of $S^1$
by a Riemann surface $\Si$. We view it as a trivial fiber bundle over $S^1$ with
fiber $\Si$. Let $\Gamma$ be a discrete (pseudo)group of orientation preserving
diffeomorphisms on $M$ fulfiling the two conditions\\

\noindent i) Each fiber $\Si$ over $S^1$ is globally $\Gamma$-invariant,\\
\noindent ii) The restriction of $\Gamma$ to a fiber is a conformal
transformation of $\Si$.\\

Thus according to section 2 an element of $\Gamma$ is a loop of conformal
transformations of $\Si$. Choose a local coordinate system $(z,\zb)$ related to
the complex structure of $\Si$, and let $t\in [0,2\pi)$ be the variable on
$S^1$. For any $g\in\Gamma$ we write
\be
z\circ g= Z_g\ ,\qquad \zb\circ g=\Zb_g\ ,\qquad t\circ g=t\ .
\ee
The jet bundles $J^+_k$ have local coordinates
$(x^{\mu},y^{\mu}_i,...,y^{\mu}_{i_1...i_k})$, where the indices $\mu,i_l...$
can assume any of the three values $(z,\zb,t)$. Of course $x^{\mu}$ are
identified with the coordinates on $M$:
\be
x^z=z\ ,\qquad x^{\zb}=\zb\ ,\qquad x^t=t\ .
\ee
Since the (real) dimension of $M$ is $n=3$ the Pontrjagin ring of the
Gelfand-Fuchs cohomology $H^*(WSO_3)$ only contains the unit 1 and the first
Pontrjagin class $p_1=c_2$. From the last section we know that $p_1$ is
represented by a closed $\Gamma$-invariant 4-form on the bundle
$P_2=J^+_2/SO_3$, explicitly given in terms of the tautological curvature
$R^i_j$, $i,j=(z,\zb,t)$:
\be
p_1={1\over 2}((R^i_i)^2-R^i_jR^j_i)\quad \in\Om^4_{inv}(P_2)\ .\label{a}
\ee
We denote $\hat{p}_1$ its image in $H^4(P_{2,\Gamma})\simeq H^4(M_{\Gamma})$.\\

\subsection{Restriction to a subbundle}

Since $\Gamma$ is a group of conformal transformations of the fibers $\Si$
leaving $t$ invariant, one can restrict the geometry to the subbundle
$\tilde{J}^+_2$ of $J^+_2$ consisting in holomorphic 2-jets
\be
u\in \rr^3\rightarrow j(u)\in M\ ,
\ee
which read in coordinates
\beq
j^z(u)&=&z+y^z_zu^z+y^z_tu^t+ {1\over 2}y^z_{zz}u^zu^z+y^z_{zt}u^zu^t+ {1\over
2}y^z_{tt}u^tu^t\ ,\non\\
j^{\zb}(u)&=&{\zb}+y^{\zb}_{\zb}u^{\zb}+y^{\zb}_tu^t+ {1\over
2}y^{\zb}_{{\zb}{\zb}}u^{\zb}u^{\zb}+y^{\zb}_{{\zb}t}u^{\zb}u^t+ {1\over
2}y^{\zb}_{tt}u^tu^t\ ,\non\\
j^t(u)&=& t+u^t\ .
\eeq
Then the 2-jets of the elements of $\Gamma$ are contained in $\tilde{J}^+_2$.
$\tilde{J}^+_2$ is a principal bundle over $M$, whose structure group contains
$SO_2$ as a maximal compact subgroup. The action of $SO_2$ is obtained by the
right composition
\be
j\in \tilde{J}^+_2\rightarrow j\circ h\in\tilde{J}^+_2\ ,
\ee
where $h$ is the jet of the rotation by an angle $\al$:
\be
h^z(u)=e^{i\al}u^z\ ,\qquad h^{\zb}(u)=e^{-i\al}u^{\zb}\ ,\qquad h^t(u)=u^t\ .
\ee
Thus $\tilde{P}_2=\tilde{J}^+_2/SO_2$ is a $\Gamma$-bundle over $M$ with
contractible fiber so that $H^*(\tilde{P}_{2,\Gamma})=H^*(M_{\Gamma})$. Moreover
$\tilde{P}_2$ is a $\Gamma$-invariant subbundle of $P_2$ and the injection
$\tilde{P}_2\rightarrow P_2$ is a homotopy equivalence. Now $\hat{p}_1\in
H^*(M_{\Gamma})$ may equivalently be represented by a closed invariant form on
$\tilde{P}_2$ corresponding to the pullback of (\ref{a}). One computes that the
pullbacks of the curvature coefficients $R^i_j$ are nonzero only for $R^z_z,
R^z_t, R^{\zb}_{\zb}, R^{\zb}_t$, hence
\be
\hat{p}_1= {1\over 2} ((R^z_z+R^{\zb}_{\zb})^2-(R^z_z)^2-(R^{\zb}_{\zb})^2) =
R^z_z R^{\zb}_{\zb}
\ee
is the pullback of $\hat{p}_1$ on $\tilde{J}^+_2$, and is $SO_2$-basic. In terms
of the tautological connection $\te^i_j$ (eq. (\ref{b})) on $\tilde{J}^+_2$ one
has $R^z_z=d\te^z_z$, with
\be
\te^z_z= (y^{-1})^z_zdy^z_z- y^z_{zz}(y^{-1})^z_z((y^{-1})^z_zdz+(y^{-1})^z_tdt)
- y^z_{zt}(y^{-1})^z_z dt\ ,
\ee
and similarly for $R^{\zb}_{\zb}$. In the following we shall write $R$ (resp.
$\overline{R}$) instead of $R^z_z$ (resp. $R^{\zb}_{\zb}$) and $\te$ (resp.
$\tb$) instead of $\te^z_z$ (resp. $\te^{\zb}_{\zb}$). Remark that the 1-form
$\te+\tb$ is $SO_2$-basic, which implies that the cohomology class of
$R+\overline{R}$ in the $\Gamma$-invariant forms on $\tilde{P}_2$ is zero. Thus
$R\overline{R}$ is cohomologous to $-R^2$ and we shall keep the latter as a
representative of $\hat{p}_1$.\\

It is possible now to express $\hat{p}_1$ as an equivariant cocycle on
$M_{\Gamma}$. Choose a K\"ahler metric $\rho(z,\zb)dz\otimes d\zb$ on $\Si$.
Then the associated connection on $\tilde{J}^+_2$ is the globally defined (not
$\Gamma$-invariant) 1-form
\be
\om = (y^{-1})^z_zdy^z_z + dz\partial_z \ln\rho\ .
\ee
Of course it corresponds to the $^z_z$ component of the connection form
associated with $\rho$ on the frame bundle. We shall regard it as an equivariant
cochain on $\tilde{J}^+_2$ through the inclusion
$\Om^1(\tilde{J}^+_2)\rightarrow C^{0,1}(\tilde{J}^+_2)$. The equivariant
curvature $\Om=(d+\delta)\om$ is an element of $C^{0,2}(\tilde{J}^+_2)\oplus
C^{1,1}(\tilde{J}^+_2)$:
\beq
\Om(g_0,g_1)&=& \delta\om(g_0,g_1)= -\om\circ g_1 +\om\circ g_0\ ,\non\\
\Om(g_0)&=& d\om(g_0)=d\om\circ g_0\ ,\qquad g_i\in\Gamma\ .
\eeq
In fact $\Om$ lives in $M_{\Gamma}$. Indeed, for $g_i\in\Gamma$, let $Z'_i$
denote the function $\partial_z(z\circ g_i)$. One has (with $\d=dz\d_z$)
\be
\om\circ g_i = (y^{-1})^z_zdy^z_z +d\ln Z'_i + (\partial\ln\rho)\circ g_i\ ,
\ee
so that
\beq
\Om(g_0,g_1)&=& d\ln Z'_0 -d\ln Z'_1 + (\partial\ln\rho)\circ g_0
-(\partial\ln\rho)\circ g_1\ ,\non\\
\Om(g_0)&=& -(\partial\db\ln\rho)\circ g_0\ .
\eeq
Here $\d\db\ln\rho$ is the curvature 2-form of the K\"ahler metric. Using the
multiplicative structure on equivariant cohomology (section 3) we consider the
cocycle $-\Om^2$. It is cohomologous to $-R^2$ in $H^4(\tilde{P}_{2,\Gamma})$,
indeed:
\be
\Om^2-R^2 = {1\over 2}(d+\delta)((\om-\te)(\Om+R)+ (\Om+R)(\om-\te))\ ,
\ee
and $\om-\te$ is a $SO_2$-basic equivariant 1-form on $\tilde{J}^+_2$. Thus we
have proved

\begin{theorem}
The equivariant 4-cocycle $-\Om^2$ represents the image of $p_1\in H^*(WSO_3)$
in $H^4(M_{\Gamma})$.
\end{theorem}

\subsection{Link with conformal anomalies}

Using formula (\ref{b}) we can express $\hat{p}_1$ as a group cocycle
$\tilde{p}_1$ in $C^1(\Gamma,\Om^3(M))\oplus C^2(\Gamma,\Om^2(M))$:
\be
\tilde{p}_1(g)=\hat{p}_1(g,1)\ ,\qquad
\tilde{p}_1(g_1,g_2)=\hat{p}_1(g_1g_2,g_2,1)\ .
\ee
The first component $\tilde{p}_1(g)$ is related to conformal anomalies as
follows. Let $g:S^1\rightarrow \mbox{Diff}(\Si)$ be a loop of conformal
transformations of $\Si$, that is, $g\in \mbox{Diff}(S^1,\Si)$ according to the
notations of section 2. Then $\tilde{p}_1(g)$ is a 3-form on $M=S^1\times\Si$:
\beq
\tilde{p}_1(g)&=& -\Om(g,1)\Om(1)-\Om(g)\Om(g,1)\non\\
&=& (d\ln Z'+(\d\ln\rho)\circ g)R_{\rho}+\non\\
&&+R_{\rho}\circ g((d\ln Z')\circ g^{-1}-(\d\ln\rho)\circ g^{-1})\circ g\ ,
\eeq
where $Z=z\circ g$ and $Z'=\d_zZ$. $R_{\rho}=\d\db\ln\rho$ is the curvature
associated to $\rho$. Let us define the $z$-component of the ghost vector field
\be
\xi^z = dt\d_t Z\circ g^{-1}\ .
\ee
It is a one-form on $S^1$ with values in the (conformal) vector fields of $\Si$.
Equivalently it is the pullback of the Maurer-Cartan form on $\mbox{Diff}(\Si)$
by the loop $g$. One computes that
\be
R_{\rho}(d\ln Z'+(\d\ln\rho)\circ g)= R_{\rho}\,(D_z\xi^z)\circ g\ ,
\ee
where $D_z\xi^z=\d_z\xi^z+\xi^z\d_z\ln\rho$ is the covariant derivative. In the
same way define
\be
(\xi^{-1})^z=dt\d_t (z\circ g^{-1})\circ g\ ,
\ee
one has
\be
(R_{\rho}\circ g)((d\ln Z')\circ g^{-1}-(\d\ln\rho)\circ g^{-1})\circ g=
-(R_{\rho}\circ g) D_z(\xi^{-1})^z\ .
\ee
If the loop $g$ is the identity of $\Si$ at $t=0$, then
\be
\tilde{p}_1(g)_{t=0}=2R_{\rho}D_z\xi^z \label{var}
\ee
is the usual expression for the infinitesimal variation, under the ghost vector
field $\xi$, of the vacuum functional of a field theory on $\Si$, i.e. a
gravitational anomaly.\\
Now the Chern character of the signature operator $Q$ (section 2), contains the
image of $\tilde{p}_1$ by the injection
\be
\Phi: H^*(M_{\Gamma})\simeq H^*(P\times_{\Gamma}E\Gamma)\hookrightarrow
HC^*(\cinfc(P)\cp\Gamma)\ ,
\ee
where $P$ is the bundle of all metrics (not necessarily K\"ahler) on the
3-dimensional {\it real} manifold $M$. The topological anomaly formula then
gives an {\it integrated} version of the infinitesimal variation (\ref{var}),
and is in general nonzero, provided we evaluate the anomaly on invertible {\it
matrices} over the algebra $\cinfc(M)\cp\Gamma$.\\

\subsection{Non-triviality of $\tilde{p}_1$}

To show that $\tilde{p}_1$, and consequently its image in
$HC^*(\cinfc(P)\cp\Gamma)$, is in general a non-trivial cohomology class, we
shall construct a cycle $c$ in the equivariant homology with compact support
$H_*(M_{\Gamma})$, whose evaluation on $\tilde{p}_1$ is nonzero. Since it is
sufficient to do this in a particular case, let us take for $\Si$ the Riemann
sphere $\cc\cup \{\infty\}$, and $\rho(z,\zb)=1$. Then the only nonzero
component of $\tilde{p}_1$ lies in $C^2(\Gamma,\Om^2(M))$:
\beq
\tilde{p}_1(g_1,g_2)&=&-\Om^2(g_1g_2,g_2,1)\ =\ \Om(g_1g_2,g_2)\Om(g_2,1)\non\\
&=& (d\ln Z'_1)\circ g_2\, d\ln Z'_2\ .
\eeq
The equivariant homology is computed by the bicomplex $(C_{n,m})_{n,m\ge 0}$,
\be
C_{n,m}= \cc[\Gamma]^{\otimes n}\otimes\Om_m(M)\ ,
\ee
where $\cc[\Gamma]$ is the group ring of $\Gamma$ and $\Om_m(M)$ the space of
$m$-dimensional de Rham currents with compact support on $M$. The first boundary
map $\delta:C_{n,m}\rightarrow C_{n-1,m}$ is
\beq
\delta (g_1\otimes...\otimes g_n\otimes C)&=&g_2\otimes..\otimes g_n\otimes C
+\non\\&&+\sum_{i=1}^n (-)^i g_1\otimes...\otimes g_ig_{i+1}\otimes...\otimes
g_n\otimes C+\non\\
&& + (-)^{n+1}g_1\otimes...\otimes g_{n-1}\otimes g_nC\ ,
\eeq
where $g_nC$ is the left action of $g_n\in\Gamma$ on the current $C\in\Om_m(M)$
by pushforward. The second differential $\d:C_{n,m}\rightarrow C_{n,m-1}$ is the
de Rham boundary (not to be confused with the previous $dz\d_z$ !)
\be
\d(g_1\otimes...\otimes g_n\otimes C)=(-)^n g_1\otimes...\otimes g_n\otimes \d
C\ .
\ee
We shall construct the cycle $c$ as an element of $C_{1,3}\oplus C_{2,2}$. Let
$\Gamma$ be such that $g_1,g_2\in\Gamma$ with
\be
z\circ g_j=Z_j={{e^{itn_j}}\over z}\ ,\qquad t\circ g_j=t\ ,\qquad j=1,2\ ,\quad
 n_j\in\zz\ .
\ee
Choose an orientation on $M=S^1\times \Si$ and let $C\in\Om_3(M)$ be the current
corresponding to the integration of 3-forms over the full cylinder
\be
C=\{(z,\zb,t)\in M | z\zb\le 1\}\ .
\ee
One checks that
\be
g_i\d C=-\d C\ ,\qquad g_1g_2 C=C\ ,
\ee
which implies that
\be
c:= g_1\otimes g_2\otimes \d C + (g_2-g_1-g_1g_2)\otimes C
\ee
represents an homology class in $H_4(M_{\Gamma};\zz)$:
\be
(\d+\delta)c=0\ .
\ee
Therefore the pairing between $\tilde{p}_1$ and $c$ is simply given by
\be
\langle \tilde{p}_1, c\rangle = \int_{\d C}\tilde{p}_1(g_1,g_2)\ ,
\ee
which gives, up to an irrelevant sign depending on the orientation, the
difference $8\pi^2(n_1-n_2)$.

\vskip 1cm

\noindent{\bf Acknowledgments:} The author wishes to thank S. Lazzarini for his
constant support, and S. Majid for comments.


TITLE: Metric space and closed sets (book misprint?)
QUESTION [1 upvotes]: I am not sure if there is a misprint in this corollary or if I am not getting the idea right.
Corollary. Let $X$ be a metric space and let $A\subset X$. Then A is closed in $X$ iff:
$$
(x_n)_{n=1}^{\infty}\subset A \text{ and } x_n \rightarrow x \text{ implies } x_n \in A
$$
Shouldn't it be $x \in A$ instead of $x_n \in A$? If not, why?

REPLY [2 votes]: You are right, there is a misprint.


TITLE: How can I prove the IFF condition for this group of matrices?
QUESTION [1 upvotes]: I'm tasked with showing that matrix $A$ commutes with every $2\times2$ matrix if and only if $A = \begin{bmatrix}a & 0\\0 & a\end{bmatrix}$ for some a.
I was able to prove in the first direction, assuming that $A = \begin{bmatrix}a & 0\\0 & a\end{bmatrix}$, by just multiplying the matrix by $\begin{bmatrix}a & b\\c & d\end{bmatrix}$ in AB = BA format, and showing how AB does equal BA.
$$ (=>)$$
$$\begin{bmatrix}a & 0\\0 & a\end{bmatrix}\begin{bmatrix}a & b\\c & d\end{bmatrix} = \begin{bmatrix}a & b\\c & d\end{bmatrix}\begin{bmatrix}a & 0\\0 & a\end{bmatrix}$$
$$\begin{bmatrix}a^2 & ab\\ac & ad\end{bmatrix} = \begin{bmatrix}a^2 & ab\\ac & ad\end{bmatrix}$$
But now I have to prove in the other direction, assuming that A already does commute with every $2\times 2$ matrix, and I'm not particularly sure how I can do that. Somehow, I have to show that if A commutes with $\begin{bmatrix}a & b\\c & d\end{bmatrix}$, then A will be $\begin{bmatrix}a & 0\\0 & a\end{bmatrix}$, and I don't know how I can carry that out.
Where can I start? Ideas are appreciated.

REPLY [1 votes]: For the opposite direction, it helps to write down the fact that you matrix commutes with particular matrices, which you can choose as simple as you like, so that the computations won't be too hard. With a few good choices you may get to your goal, as you need to establish only $3$ equations in the $4$ unknowns $a,b,c,d$ (namely $a=d$, $b=0$, and $c=0$). You might find a very small set of matrices such that any matrix commuting with them automatically commutes with everyone (because the former condition forces them to be of the form $$
\begin{pmatrix}a&0\\0&a\end{pmatrix}$$). Your particluar matrix should of course not be so simple as to be the null matrix, or more generally a multiple of the identity matrix, since you know that those commute with everyone, so the won't give you any useful equations. But there are some very simple choices left.


TITLE: Proving that operations give equal results given equal inputs
QUESTION [0 upvotes]: I was reading about the 9 or 12 basic properties of 'fields' (if that's what they're called) in a book called Spivak's Calculus, 3rd Edition, and got quite befuddled by dealing with as basic stuff as assuming $1 \neq 0$ (although I get that now).
But I got stuck when I wanted to conclude stuff $ a \cdot c = b \cdot c $ from $ a = b $ where $\cdot$ means addition, multiplication or w/e. There was no property dealing with these cases!
Someone on IRC told me that a property stating that operations give equal results given equal inputs (note: the order of the inputs is preserved; we aren't dealing with commutativity here) was implicitly assumed in the book.
Also, last year in school, we learnt about Euclid's axioms which explicitly stated stuff like this (and in a rather wordy and arbitrary way too, it seemed; unlike the rest of this group and field stuff).

My questions are:

What is this property actually called?
Does it apply to every single operation definable (except stuff like RNGs)?
Why wasn't this mentioned along-side other 'basic' facts in the book?

REPLY [1 votes]: I've seen that property referred to as compatibility or congruence. It's such a low-level fact that I'm not surprised even a detailed book on calculus doesn't make it explicit. If you want to understand it better you should study logic. That rule applies to absolutely anything. It's one of the axioms of predicate calculus with equality in the Hilbert system.
$$ x = y → φ [z := x] → φ [z := y] $$


TITLE: Product of ideal generators
QUESTION [0 upvotes]: Can we in general say that if we have an ideal $(I,J)$ that this is the same as the ideal $(I,J,IJ)$, where $IJ$ is the product of I and J?

REPLY [3 votes]: Yes, they are the same. An ideal is closed under addition (i.e. the sum of two elements of an ideal is also in the ideal) and under multiplication with some element of the ring (i.e. the product of some element of the ideal and some element of the ring is also in the ideal). The product of two ideals is defined by $IJ=\{\sum_{i=1}^na_ib_i\mid n\in\mathbb{N}\land\forall i\in\{1,\ldots,n\}:(a_i\in I\land b_i\in J)\}$. Thus $IJ$ is a subset of $I\cap J$ and in particular a subset if $I$. Thus $(I,J,IJ)$ is contained in $(I,J)$ which again is certainly contained in $(I,J)$.


TITLE: Uniqueness of morphism in definition of category theory product (etc)
QUESTION [9 upvotes]: I'm trying to understand the categorical definition of a product, which describes them in terms of existence of a unique morphism that makes such-and-such a diagram commute. I don't really feel I've totally understood the motivation for this definition: in particular, why must that morphism be unique? What's the consequence of omitting the requirement for uniqueness in, say, Set?

REPLY [8 votes]: This is a question which you will be able to answer yourself after some experience ... anyway:
The cartesian product $X \times Y$ of two sets $X,Y$ has the property: Every element of $X \times Y$ has a representation $(x,y)$ with unique elements $x \in X$ and $y \in Y$. This is the important and characteristic property of ordered pairs. In other words, if $*$ denotes the one-point set: For every two morphisms $x : * \to X$ and $y : * \to Y$ there is a unique morphism $(x,y) : * \to X \times Y$ such that $p_X \circ (x,y) = x$ and $p_Y \circ (x,y) = y$. But since we can do everything pointwise, the same holds for arbitrary sets instead of $*$: For every two morphisms $x : T \to X$ and $y : T \to Y$ (which you may think of families of elements in $X$ resp. $Y$, also called $T$-valued points in the setting of functorial algebraic geometry), there is a unique morphism $(x,y) : T \to X \times Y$ such that $p_X \circ (x,y) = x$ and $p_Y \circ (x,y) = y$. Once you have understood this in detail, this motivates the general definition of a product diagram in a category. After all, these appear everywhere in mathematics (products of groups, vector spaces, $\sigma$-algebras, topological spaces, etc.). Of course, the uniqueness statement is essential. Otherwise, the product won't be unique and in the case of sets you will get many more objects instead of the usual cartesian product. In general, an object $T$ satisfies the universal property of $X \times Y$ without the uniqueness requirement iff there is a retraction $T \to X \times Y$. So for example in the category of sets every set larger than the cartesian product will qualify.