\section{Introduction}

In their lauded paper~\cite{Slepian:SW},
David Slepian and Jack~K.~Wolf
characterize the information
rates needed to losslessly communicate two
correlated, memoryless information sources when
these sources are encoded separately.
Their well-known
result states that two discrete sources
$Y_1$ and $Y_2$ can be losslessly reproduced
if
\begin{align*}
R_1 & > H(Y_1|Y_2) \\
R_2 & > H(Y_2|Y_1) \\
R_1 + R_2 & > H(Y_1,Y_2),
\end{align*}
where $R_1$ is the rate of the encoder observing
$Y_1$ and $R_2$ is the rate of the encoder observing
$Y_2$. Conversely, lossless reproduction is not possible
if $(R_1,R_2)$ lies outside the closure
of this region.
See Cover and Thomas~\cite[Section~14.4]{Cover:IT} or
Csisz\'{a}r and K\"{o}rner~\cite[Section~3.1]{CK:IT} for precise
statements of the result and modern proofs.
This result is naturally viewed as
a multi-source generalization of the classical result
of Shannon~\cite{Shannon:IT},
which says that, loosely speaking, a discrete memoryless source
with known law can be losslessly reproduced if and only
if the data rate exceeds the entropy of the source.
Shannon too studied a generalization of this
result, albeit in a different direction.
He studied the problem of reproducing a source
imperfectly, subject to a minimum fidelity constraint, and
showed that the required rate is given by the well-known
rate-distortion formula~\cite{Shannon:IT,Shannon:RD}.
One of the central problems
of Shannon theory is to understand the limits of source
coding for models that combine the two generalizations.
That is, we seek to determine the rates required to
reproduce two correlated sources, each subject to a
fidelity constraint, when the sources are encoded separately
(see Fig.~\ref{MTSC:basic:fig}).
\begin{figure}
\begin{center}
\scalebox{.9}{\input{basic.pstex_t}}
\end{center}
\caption{Separate encoding of correlated sources.}
\label{MTSC:basic:fig}
\end{figure}
Determining the set
of achievable rates and distortions for this
setup is often
called the \emph{multiterminal source-coding problem},
even though this name suggests a more elaborate network
topology. This problem has been unsolved for some time.

The model we consider in this paper is slightly
more general and is depicted in Fig.~\ref{MTSC:fig}.
\begin{figure}
\begin{center}
\scalebox{.9}{\input{mtsc.pstex_t}}
\end{center}
\caption{A general model.}
\label{MTSC:fig}
\end{figure}
Beyond considering an arbitrary number of encoders, $L$,
we also allow for a hidden source, $Y_0$, which is
not directly observed by any encoder or the decoder,
and a ``side information'' source, $Y_{L+1}$, which is observed by the
decoder but not by any encoder. We also permit arbitrary
functions of the sources to be reproduced, in addition to,
or in place of, the sources themselves.
We will therefore use $Z_1, Z_2$, etc., to denote
the instantaneous estimates instead of
$\hat{Y}_1, \hat{Y}_2$, etc., as before.
In this paper, we will refer to this more general problem as
the multiterminal source-coding problem.

One might doubt the wisdom of embellishing the model
when even the basic form shown in Fig.~\ref{MTSC:basic:fig}
is unsolved. But one of the contributions of this paper is
to show that far from obscuring the problem,
the added generality actually illuminates it.
Of course, the more general problem is also unsolved.

Many special cases have been solved, however. For these,
the reader is referred to the classical papers of
Slepian and Wolf~\cite{Slepian:SW}, mentioned earlier;
Wyner~\cite{Wyner:SCSI};
Ahlswede and K\"{o}rner~\cite{Ahlswede:SCSI};
Wyner and Ziv~\cite{Wyner:WZ};
K\"{o}rner and Marton~\cite{Korner:ModTwo}; and
Gel`fand and Pinsker~\cite{Gelfand:CEO};
and to the more recent papers of
Berger and Yeung~\cite{Berger:BY};
Gastpar~\cite{Gastpar:WZ};
Oohama~\cite{Oohama:CEO:Region};
and Prabhakaran, Tse, and Ramchandran~\cite{Prabhakaran:ISIT04}.
While all of these papers contain conclusive results,
these results
are established using coding theorems that are
tailored to the special cases under consideration.

The solutions to these solved special cases suggest a
coding technique
for the general model~\cite{Berger:MTSC,Tung:PHD}.
The idea is this. Each encoder
first quantizes its observation as in single-user
rate-distortion theory. The quantized processes
are then losslessly communicated to the decoder using
the binning scheme of Cover~\cite{Cover:Bin}.
The decoder uses the quantized processes to produce
the desired estimates. The set of rate-distortion
vectors that can be achieved using this scheme is
described in Section~\ref{relation}. This inner
bound to the rate-distortion region is tight in
all of the special cases listed above except
that of K\"{o}rner and Marton~\cite{Korner:ModTwo}.
Indeed, the K\"{o}rner-Marton problem seems to
require a custom coding technique that relies on
the problem's unique structure. This suggests that
the multiterminal source-coding
problem may not have a classical single-letter
solution.

We attack this problem, therefore, by proving single-letter
inner and outer bounds on the rate-distortion
region. The best inner bound in the literature has
just been described.
The best outer bound, which is due to Berger~\cite{Berger:MTSC}
and Tung~\cite{Tung:PHD},
is described in Section~\ref{relation}.
In light of the result of K\"{o}rner and Marton, it is clear
that the two bounds must not coincide in all cases.
This gap cannot be entirely attributed to the
inner bound, however, as
there are instances of the problem that can be
solved from first principles for which the Berger-Tung outer bound
is strictly bigger than the true rate-distortion region (see
Section~\ref{contrived} of this paper).

Our aim is to provide an improved outer bound
for the problem. We prove such a bound
in the next section,
following a precise formulation of the problem. We show that
our bound is contained in (i.e., subsumes)
the Berger-Tung outer bound in
Section~\ref{relation}.  In that section, we also provide several
examples for which the containment is strict.

One example is the binary erasure version of the
``CEO problem,'' the general version of which was
introduced by Berger, Zhang, and
Viswanathan~\cite{Berger:CEO}. The CEO problem is a special
case of the multiterminal source-coding problem in which
the observed processes $Y_1,\ldots,Y_L$ are conditionally
independent given the hidden process $Y_0$ and in which
the decoder (the CEO) is only interested in estimating
the hidden process\footnote{This definition is not as
restrictive as it might seem. Indeed, any instance of
the multiterminal source-coding problem with a single
distortion constraint can be transformed into an instance
of the CEO problem without changing the rate-distortion
region by lumping $Y_1,\ldots,Y_L$ into $Y_0$ and redefining
the distortion measure as needed. Nonetheless, it defines
a useful special case.}. Berger, Zhang,
and Viswanathan characterize the tradeoff
between sum rate and Hamming distortion in the
high-rate and many-encoder
limit. Gel`fand and Pinsker~\cite{Gelfand:CEO}
had earlier found the
rate region in the lossless reproduction case.
We consider the problem in which $Y_0$ is binary and uniform,
and the encoders observe $Y_0$ through independent
binary erasure channels. The decoder reproduces
$Y_0$ subject to a constraint on the ``erasure
distortion'' (see Section~\ref{BECEO:subsection} or
Cover and Thomas~\cite[p.~370]{Cover:IT}). For this
problem, we show that our outer bound is tight in the
sum rate for any number of users. In contrast,
the Berger-Tung outer bound contains points whose
sum rate is strictly smaller than the optimum.

In our view, this result is
of interest in its own right.
The binary erasure CEO problem arises naturally in sensor
networks in which the sensors occasionally ``sleep''
to conserve energy. This application is described
in Section~\ref{BECEO:subsection}.
The result also provides an example for which
the binning-based coding scheme mentioned earlier
is optimum. Finally, this is one of relatively few
conclusive results for the multiterminal source-coding
problem in general, and the CEO problem in particular.
These problems are considered sufficiently difficult
that it is worth reporting solutions to special cases.

One of the few other conclusive results available is
for the Gaussian version of the CEO problem, which was
first studied by Viswanathan and Berger~\cite{Viswanathan:CEO}.
Here the encoders observe a hidden Gaussian source through
independent Gaussian additive-noise channels. The distortion
measure is expected squared error. The rate-distortion
region for this problem was recently found by
Oohama~\cite{Oohama:Africa,Oohama:CEO:Region} and independently by
Prabhakaran, Tse, and Ramchandran~\cite{Prabhakaran:ISIT04}.
We show that the converse result of these four authors
can be recovered from our single-letter outer bound, while the
Berger-Tung outer bound contains points that lie outside the
true rate-distortion region.

The converse results used to solve all of the other special
cases mentioned so far are also consequences of our bound. This is
discussed in Section~\ref{recover}. Our outer bound
therefore serves to unify most of what is known about
the nonexistence of multiuser source codes.
This unification is noteworthy in the case of
Oohama~\cite{Oohama:CEO:Region}
and Prabhakaran, Tse, and Ramchandran~\cite{Prabhakaran:ISIT04}
because the connection between their remarkable converse
result and the classical discrete results in this area
is not immediately apparent.
As we will see, subject to some technical caveats,
most of the key results in multiterminal
source coding can be recovered by combining the general inner
bound described earlier with the outer bound described next.

\section{Formulation and Main Result}

We work exclusively in discrete time.
We use uppercase letters to denote random variables and
vectors, lowercase letters to denote their realizations,
and script letters to denote their ranges. Let
$\{Y^n_0(t), Y_1^n(t),\ldots,Y_L^n(t),Y_{L+1}^n(t)\}_{t = 1}^n$ be a
vector-valued,
finite-alphabet memoryless source. For $A \subset \{1,\ldots,L\}$, we
denote $(Y_\ell^n(t))_{\{\ell \in A\}}$ by $\mathbf{Y}^n_A(t)$. If
$A = \{1,\ldots,L\}$, we write this simply as $\mathbf{Y}^n(t)$.
In this context,
the set $A^c$ should be interpreted as
$\{1,\ldots,L\}\backslash A$
rather than $\{0,\ldots,L+1\}\backslash A$.
When $A = \{\ell\}$, we shall write
$Y_\ell^n(t)$ and $Y_{\ell^c}^n(t)$ in place of
$Y_{\{\ell\}}(t)$ and $Y_{\{\ell\}^c}(t)$, respectively. Also,
we use $Y^n_\ell(t_1:t_2)$ to denote
$\{Y^n_\ell(t)\}_{t = t_1}^{t_2}$,
$Y_\ell^n$ to denote $Y_\ell^n(1:n)$,
and $Y^n_\ell(t^c)$ to denote
\begin{equation*}
(Y^n_\ell(1), \ldots, Y^n_\ell(t-1),Y^n_\ell(t+1), \ldots, Y^n_\ell(n)).
\end{equation*}
Similar notation will be used for other vectors that appear later.

The notation for the
encoding and decoding rules is shown in Fig.~\ref{rules}.
\begin{figure}
\begin{center}
\makebox[3.3in][l]{\scalebox{.9}{\input{rules.pstex_t}}}
\end{center}
\caption{Notation for the encoding and decoding rules.}
\label{rules}
\end{figure}
For each $\ell$ in $\{1,\ldots,L\}$, encoder $\ell$ observes
$Y_\ell^n$,
then employs a mapping
\begin{equation*}
f_\ell^{(n)} : \mathcal{Y}_\ell^n \rightarrow
\left\{1,\ldots,M_\ell^{(n)}\right\}
\end{equation*}
to convey information about it to the decoder.
The decoder observes $Y_{L+1}^n$ and uses it and the received messages to
estimate $K$ functions of the vector-valued source according to the mappings
\begin{equation*}
\varphi_k^{(n)} : \mathcal{Y}_{L+1}^n \times
  \prod_{\ell = 1}^L \left\{1,\ldots,M_\ell^{(n)}\right\}
  \mapsto \mathcal{Z}_k^n \ \text{for $k = 1,\ldots,K$}.
\end{equation*}
We assume that $K$ distortion measures
$d_k : \prod_{\ell = 0}^{L+1} \mathcal{Y}_\ell \times \mathcal{Z}_k \mapsto
\mathbb{R}_+$ are given.

We mention at this point that while the generality of this
setup will be useful later when studying examples, it is not
needed to appreciate the bounding technique itself. The reader
is welcome to focus on the basic model shown in Fig.~\ref{MTSC:basic:fig}
for that purpose.
\begin{defn}
\label{achievable:defn}
The rate-distortion vector
\begin{equation*}
(\mathbf{R},\mathbf{D}) = (R_1,R_2,\ldots,R_L,D_1,D_2,\ldots,D_K)
\end{equation*}
is \emph{achievable} if there exists a block length $n$,
encoders $f_\ell^{(n)}$, and a decoder
\begin{equation*}
\left(\varphi_1^{(n)},\ldots,\varphi_K^{(n)}\right)
\end{equation*}
such that%
\footnote{All logarithms and exponentiations in this paper have
base $e$.}
\begin{equation}
\label{constraints}
\begin{split}
R_\ell & \ge \frac{1}{n} \log M_\ell^{(n)} \ \text{for all $\ell$, and} \\
D_k & \ge E\left[\frac{1}{n} \sum_{t = 1}^n d_k(Y^n_0(t),\mathbf{Y}^n(t),
Y_{L+1}^n(t), Z_k^n(t))\right] \ \text{for all $k$}.
\end{split}
\end{equation}
Let $\mathcal{RD}_\star$ be the
set of achievable rate-distortion vectors. Its
closure, $\overline{\mathcal{RD}_\star}$, is called the
\emph{rate-distortion region}.
\end{defn}
We will sometimes be concerned with projections of the
rate-distortion region. We denote these by, for example,
$\overline{\mathcal{RD}_\star} \cap \{R_1 = 0\}$, meaning
\begin{equation*}
\left\{(R_2,\ldots,R_L,D_1,\ldots,D_K) : (0,R_2,\ldots,R_L,D_1,\ldots,D_K)
  \in \overline{\mathcal{RD}_\star}\right\}.
\end{equation*}

In this paper, we view lossless compression as a limit of
lossy compression with the distortion tending to zero. More
precisely, if we wish to reproduce $Y_1$ losslessly, we will
set, say, $\mathcal{Z}_1 = \mathcal{Y}_1$ with $d_1$ equal
to Hamming distance, and then examine
$\overline{\mathcal{RD}_\star} \cap \{D_1 = 0\}$.
This convention and Definition~\ref{achievable:defn} together
yield a notion of lossless compression that is weaker than the
one traditionally
used. It is common instead to require that for all sufficiently
large block lengths, there exists a code for which the probability
of correctly reproducing the entire vector $Y_1^n$ is arbitrarily
close to 1. But a weaker notion is desirable here since we are
proving an outer bound or ``converse'' result.

To state our result,
let $Y_0,\ldots,Y_{L+1}$ be generic random variables with
the distribution of the source at a single time.
Let $\Gamma_o$ denote
the set of finite-alphabet random variables $\gamma = (U_1,\ldots,U_L,
Z_1,\ldots,Z_K,W,T)$ satisfying
\begin{enumerate}
\item[(\emph{i})]
$(W,T)$ is independent of $(Y_0,\mathbf{Y},Y_{L+1})$,
\item[(\emph{ii})]
$U_\ell \ensuremath{\leftrightarrow} (Y_\ell,W,T) \ensuremath{\leftrightarrow} (Y_0,\mathbf{Y}_{\ell^c},Y_{L+1},
  \mathbf{U}_{\ell^c}$), shorthand for
``$U_\ell$, $(Y_\ell,W,T)$ and
$(Y_0,\mathbf{Y}_{\ell^c},Y_{L+1},\mathbf{U}_{\ell^c})$
form a Markov chain in this order'', for all $\ell$, and
\item[(\emph{iii})]
$(Y_0,\mathbf{Y},W) \ensuremath{\leftrightarrow} (\mathbf{U},Y_{L+1},T) \ensuremath{\leftrightarrow} \mathbf{Z}$.
\end{enumerate}
It is straightforward to verify that $\Gamma_o$ is
precisely the set of finite-alphabet random variables $(U_1,\ldots,U_L,
Z_1,\ldots,Z_K,W,T)$ whose joint distribution with
$(Y_0,\mathbf{Y},Y_{L+1})$ factors as
\begin{equation*}
p(y_0,\mathbf{y},y_{L+1},\mathbf{u},\mathbf{z},w,t) =
p(y_0,\mathbf{y},y_{L+1})p(w,t)\prod_{\ell = 1}^L p(u_\ell|y_\ell,w,t)
  p(\mathbf{z}|\mathbf{u},y_{L+1},t).
\end{equation*}
This description is helpful in that it suggests
a parametrization of the space $\Gamma_o$.

Let $\chi$ denote the set of finite-alphabet random variables $X$ with
the property that $Y_1,\ldots,Y_L$
are conditionally independent given $(X,Y_{L+1})$. Note
that $\chi$ is nonempty since it contains, e.g.,
$X = (Y_1,\ldots,Y_{L-1})$.

There are many ways of coupling a given
$X$ in $\chi$ and $\gamma$ in $\Gamma_o$.
In this paper, we shall only consider the unique coupling for which
$X \ensuremath{\leftrightarrow} (Y_0,\mathbf{Y},Y_{L+1}) \ensuremath{\leftrightarrow} \gamma$, which
we call the \emph{Markov coupling.}
Whenever the joint distribution of
$X$, $(Y_0, \mathbf{Y}, Y_{L+1})$, and
$\gamma$ arises, we assume that this coupling is in effect.

It is evident from the definition of $\chi$ that there is
considerable latitude in choosing how $X$ depends on
$Y_0$. This is because the sole constraint on the choice
of $X$ only depends on the joint distribution of $X$
and $(\mathbf{Y},Y_{L+1})$. But as the following
definition makes clear, this freedom is inconsequential
since our outer bound only depends on the distributions
of $(Y_0,\mathbf{Y},Y_{L+1},\gamma)$ and $(X,\mathbf{Y},Y_{L+1},\gamma)$
separately.

\begin{defn}
\label{Me:defn}
Let
\begin{align*}
\mathcal{RD}_o(X,\gamma) & = \Bigg\{(\mathbf{R},\mathbf{D}) :
\sum_{\ell \in A} R_\ell \ge I(X;\mathbf{U}_A|\mathbf{U}_{A^c},Y_{L+1},T) \\
& \phantom{= \Bigg\{}
  \mbox{} + \sum_{\ell \in A} I(Y_\ell;U_\ell|X,Y_{L+1},W,T)
    \ \text{for all $A \subset \{1,\ldots,L\}$}, \\
& \phantom{= \Bigg\{} \ \text{and} \ D_k
  \ge E[d_k(Y_0,\mathbf{Y},Y_{L+1},Z_k)] \ \text{for all $k$} \Bigg\}.
\end{align*}
Then define
\begin{equation*}
\mathcal{RD}_o = \bigcap_{X \in \chi} \bigcup_{\gamma \in \Gamma_o}
          \mathcal{RD}_o(X,\gamma).
\end{equation*}
\end{defn}
The first theorem is our main result.
\begin{theorem}
\label{main}
The rate-distortion region is contained in $\overline{\mathcal{RD}_o}$.
In fact, $\mathcal{RD}_\star \subset \mathcal{RD}_o.$
\end{theorem}

\emph{Proof.} It suffices to show the second statement.
Suppose $(\mathbf{R},\mathbf{D})$ is
achievable. Let $f_1^{(n)}, \ldots, f_L^{(n)}$ be encoders
and $(\varphi_1^{(n)},\ldots,\varphi_K^{(n)})$ a decoder
satisfying~(\ref{constraints}).
Take any $X$ in $\chi$ and augment the sample space to
include $X^n$ so that
\begin{equation*}
(X^n(t),Y_0^n(t),\mathbf{Y}^n(t),Y_{L+1}^n(t))
\end{equation*}
is independent over
$t$. Next let $T$ be uniformly distributed over $\{1,\ldots,n\}$,
independent of $X^n$, $Y_0^n$, $\mathbf{Y}^n$, and $Y_{L+1}^n$.
Then define
\begin{align*}
X & = X^n(T) \\
Y_\ell & = Y_\ell^n(T) \ \text{for each $\ell$ in $\{0,\ldots,L+1\}$} \\
U_\ell & = \left(f_\ell^{(n)}(Y_\ell^n), X^n(1:T-1),
     Y_{L+1}^n(T^c)\right) \ \text{for each $\ell$} \\
Z_k & = Z_k^n(T) \ \text{for each $k$} \\
W & = (X^n(T^c),Y^n_{L+1}(T^c)).
\end{align*}
It can be verified that $\gamma = (\mathbf{U},\mathbf{Z},W,T)$
is in $\Gamma_o$ and that,
together with $Y_0$, $\mathbf{Y}$, $Y_{L+1}$, and $X$, it satisfies the
Markov coupling. It suffices to show that $(\mathbf{R},\mathbf{D})$
is in $\mathcal{RD}_o(X,\gamma)$.
First, note that~(\ref{constraints}) implies
\begin{equation*}
D_k \ge E[d_k(Y_0^n(T),\mathbf{Y}^n(T),Y_{L+1}^n(T),Z^n_k(T))]
  \ \text{for all $k$},
\end{equation*}
i.e.,
\begin{equation*}
D_k \ge E[d_k(Y_0,\mathbf{Y},Y_{L+1},Z_k)] \ \text{for all $k$}.
\end{equation*}
Second, let $A \subset \{1,\ldots,L\}$. Then
by the cardinality bound on entropy,
\begin{equation*}
n \sum_{\ell \in A} R_\ell \ge
   H\left(\left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A}\right).
\end{equation*}
Since conditioning reduces entropy, this implies
\begin{align}
\nonumber
n \sum_{\ell \in A} R_\ell & \ge
        H\left(\left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A}
   \Big|\left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A^c},Y_{L+1}^n\right) \\
\label{blockchain}
    & = I\left(X^n, \mathbf{Y}_A^n;
      \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A} \Big|
         \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A^c},Y_{L+1}^n\right).
\end{align}
By the chain rule for mutual information,
\begin{multline}
\label{twoterms}
 I\left(X^n, \mathbf{Y}_A^n ;
    \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A} \Big|
        \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A^c},Y_{L+1}^n\right) \\
 = I\left(X^n; \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A} \Big|
         \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A^c},Y_{L+1}^n\right) \\
 + I\left(\mathbf{Y}_A^n; \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A}
  \Big| \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A^c},X^n,Y_{L+1}^n\right).
\end{multline}
Applying the chain rule again gives
\begin{align*}
 & I\left(X^n; \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A}\Big|
        \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A^c},Y_{L+1}^n\right) \\
 & = \sum_{t = 1}^n I\left(X^n(t);
     \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A}\Big|
    \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A^c},
    X^n(1:t-1), Y_{L+1}^n\right).
\end{align*}
Consider next the second term on the right-hand side
of~(\ref{twoterms}). Since $X \in \chi$,
\begin{multline*}
I\left(\mathbf{Y}_A^n; \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A}
  \Big| \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A^c},
         X^n,Y_{L+1}^n\right) \\
  = \sum_{\ell \in A} I\left(Y_\ell^n; f_\ell^{(n)}(Y_\ell^n)
       \Big|X^n,Y_{L+1}^n\right).
\end{multline*}
Applying the chain rule once more gives
\begin{multline*}
I\left(Y_\ell^n; f_\ell^{(n)}(Y_\ell^n)\Big|X^n,Y_{L+1}^n\right) = \\
\sum_{t = 1}^n I\left(Y_\ell^n(t); f_\ell^{(n)}(Y_\ell^n)\Big|X^n,
   Y_\ell^n(1:t-1), Y_{L+1}^n\right).
\end{multline*}
But
\begin{multline*}
I\left(Y_\ell^n(t); f_\ell^{(n)}(Y_\ell^n)\Big|X^n,Y_\ell^n(1:t-1),
    Y_{L+1}^n\right) \\
  \mbox{} + I(Y_\ell^n(t);Y_\ell^n(1:t-1)|X^n,Y_{L+1}^n) \\
 =  I\left(Y_\ell^n(t);f_\ell^{(n)}(Y_\ell^n)\Big| X^n,Y_{L+1}^n\right) \\
  \mbox{} + I\left(Y_\ell^n(t);Y_\ell^n(1:t-1)\Big|f_\ell^{(n)}(Y_\ell^n),
   X^n,Y_{L+1}^n\right),
\end{multline*}
and the second term on the left-hand side is zero. Thus
\begin{multline*}
I\left(Y_\ell^n(t); f_\ell^{(n)}(Y_\ell^n)\Big|X^n,Y_\ell^n(1:t-1),
  Y_{L+1}^n\right) \ge \\
  I\left(Y_\ell^n(t);f_\ell^{(n)}(Y_\ell^n)\Big| X^n,Y_{L+1}^n\right).
\end{multline*}
Substituting the results of these various calculations into~(\ref{blockchain})
gives
\begin{equation}
\begin{split}
\label{substitute}
& \sum_{\ell \in A} R_\ell \ge \\
 & \frac{1}{n} \sum_{t = 1}^n \Bigg[I\left(X^n(t);
           \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A}\Big|
  \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A^c},
         X^n(1:t-1),Y_{L+1}^n\right) \\
 & \phantom{\ge} + \sum_{\ell \in A}
      I\left(Y_\ell^n(t);f_\ell^{(n)}(Y^n_\ell)\Big|
       X^n(t),X^n(t^c),Y_{L+1}^n(t), Y_{L+1}^n(t^c)\right)\Bigg].
\end{split}
\end{equation}
If $A^c$ is nonempty, this can be rewritten as
\begin{align*}
\sum_{\ell \in A} R_\ell
& \ge I(X^n(T);\mathbf{U}_A|\mathbf{U}_{A^c},Y_{L+1}^n(T),T) \\
& \phantom{=} + \sum_{\ell \in A}
  I(Y_\ell^n(T);U_\ell|X^n(T),X^n(T^c),Y_{L+1}^n(T),Y_{L+1}^n(T^c),T) \\
& = I(X;\mathbf{U}_A|\mathbf{U}_{A^c},Y_{L+1},T) + \sum_{\ell \in A}
    I(Y_\ell;U_\ell|X,Y_{L+1},W,T).
\end{align*}
The case $A = \{1,\ldots,L\}$ is handled separately. In this case,
observe that
\begin{align*}
 & I\left(X^n(t); \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A}
     \Big| \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A^c}, X^n(1:t-1),
       Y_{L+1}^n\right) \\
 & = I\left(X^n(t); \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A}
      \Big|  X^n(1:t-1), Y_{L+1}^n\right)  \\
 & = I\left(X^n(t); \left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A}
      \Big|  X^n(1:t-1), Y_{L+1}^n\right) \\
 & \phantom{= I\Bigg(} + I(X^n(t);X^n(1:t-1),Y_{L+1}^n(t^c)|Y_{L+1}^n(t)) \\
 & = I\left(X^n(t);\left(f_\ell^{(n)}(Y_\ell^n)\right)_{\ell \in A},
     X^n(1:t-1),Y_{L+1}^n(t^c)\Big| Y_{L+1}^n(t)\right).
\end{align*}
Substituting this into~(\ref{substitute}) and proceeding as in the
$A^c \ne \emptyset$ case completes the proof. \ensuremath{\hfill \Box}

It is worth noting that the proof uses classical
techniques. Most of the manipulations in the latter part of the
proof can be viewed as versions
of the chain rule
for mutual information. Since this chain rule holds in
abstract spaces~\cite[(3.6.6)]{Pinsker:Stability}, the proof
can be readily extended to more general alphabets.

The key step in the proof is the introduction of
$X^n$ in~(\ref{blockchain}). Unlike the other
auxiliary random variables, $X^n$ does not
represent a component of the code. Rather, it is used to
aid the analysis by inducing conditional independence among
the messages sent by the encoders. This technique of augmenting
the source to induce conditional independence was pioneered
by Ozarow~\cite{Ozarow:MD}, who used it to solve the Gaussian
two-descriptions problem.
Wang and Viswanath~\cite{Wang:MD} used it to determine the
sum rate of the Gaussian vector multiple-descriptions problem with
individual and central decoders. It was also used by Wagner,
Tavildar, and Viswanath~\cite{Wagner:Gaussian:Two} to solve the Gaussian
two-terminal source-coding problem. A step that is similar
to~(\ref{blockchain}) appeared in
Gel`fand and Pinsker~\cite{Gelfand:CEO} and
in later papers on the Gaussian CEO
problem~\cite{Oohama:CEO:Region,Prabhakaran:ISIT04},
although in these works $X^n$ is part of the source,
so no augmentation is involved.

The significance of conditional independence has long
been known in the related field of distributed detection
(e.g.,~\cite{Tsitsiklis:Complexity}). Given the
similarity between distributed detection and the
multiterminal source-coding problem, one expects
conditional independence to play a significant
role here as well. Indeed,
most conclusive results for the
multiterminal source-coding problem require
a conditional independence
assumption~\cite{Gelfand:CEO,Berger:CEO,Gastpar:WZ,
Oohama:CEO:Region,Prabhakaran:ISIT04}. The motivation
for introducing $X^n$ is that it allows one to apply
the approach used in these works to problems that
lack conditional independence.

We do not consider the problem of computing $\mathcal{RD}_o$ in this
paper. Note that we have not specified the
alphabet sizes of the auxiliary random variables $\mathbf{U}$,
$W$, and $T$. As such, the outer bound provided by Theorem~\ref{main}
is not computable~\cite[p.~259]{CK:IT}
in the present form. One might question
the utility of an
outer bound that cannot be computed. The remainder of the paper,
however, will show that the bound is
still useful as a theoretical tool. In addition, cardinality bounds
might be found later, although obtaining such bounds appears to
be more difficult in this case than for related bounds.

It should be mentioned that the time-sharing variable
$T$ is unnecessary; it
can be absorbed into the other variables. We have included it to
ease the comparison with existing inner and outer bounds, to which
we turn next.

\section{Relation to Existing Bounds}
\label{relation}

The coding scheme described in the introduction
gives rise to the following inner bound on the
rate-distortion region.
\begin{defn}
\label{BT:inner:defn}
Let $\Gamma_i^{BT}$ denote the set of finite-alphabet random
variables
\begin{equation*}
\gamma = (U_1,\ldots,U_L, Z_1,\ldots,Z_K,T)
\end{equation*}
satisfying
\begin{enumerate}
\item[(\emph{i})] $T$ is independent of $(Y_0,\mathbf{Y},Y_{L+1})$,
\item[(\emph{ii})] $U_\ell
        \ensuremath{\leftrightarrow} (Y_\ell,T) \ensuremath{\leftrightarrow} (Y_0,\mathbf{Y}_{\ell^c},Y_{L+1},
       \mathbf{U}_{\ell^c})$ for all $\ell$, and
\item[(\emph{iii})] $(Y_0,\mathbf{Y}) \ensuremath{\leftrightarrow} (\mathbf{U},Y_{L+1},T)
             \ensuremath{\leftrightarrow} \mathbf{Z}$.
\end{enumerate}
Then define
\begin{align*}
\mathcal{RD}_i^{BT}(\gamma) & = \Bigg\{ (\mathbf{R},\mathbf{D}) :
\sum_{\ell \in A} R_\ell \ge I(\mathbf{Y}_A;\mathbf{U}_A|%
       \mathbf{U}_{A^c},Y_{L+1},T) \ \text{for all $A$}, \\
  & \phantom{= \Bigg\{} \ \text{and} \
 D_k \ge E[d_k(Y_0,\mathbf{Y},Y_{L+1},Z_k)] \ \text{for all $k$} \Bigg\}.
\end{align*}
Finally, let
\begin{equation*}
\mathcal{RD}_i^{BT} = \bigcup_{\gamma \in \Gamma_i^{BT}}
\mathcal{RD}_i^{BT}(\gamma).
\end{equation*}
\end{defn}
\begin{prop}[\cite{Berger:MTSC,Tung:PHD}]
\label{BT:inner}
$\overline{\mathcal{RD}_i^{BT}} \subset \overline{\mathcal{RD}_\star}$.
\end{prop}
In Appendix~\ref{closed} we show that $\mathcal{RD}_i^{BT}$
is in fact closed. We call $\overline{\mathcal{RD}_i^{BT}}$ the Berger-Tung
\cite{Berger:MTSC,Tung:PHD}
inner bound, since although these authors prove a bound that is less general
than the one given here, their proof can be extended to prove
Proposition~\ref{BT:inner}.
See Chen \emph{et al.}~\cite{Chen:CEO:Bounds} or
Gastpar~\cite{Gastpar:WZ} for recent sketches of the
proof that accommodate some of the generalizations
included here.

To understand the difference between $\mathcal{RD}_i^{BT}$ and
$\mathcal{RD}_o$, suppose that
\begin{equation*}
(\mathbf{U},\mathbf{Z},W,T)
\end{equation*}
is in $\Gamma_o$ and $W$ is deterministic. Then
$(\mathbf{U},\mathbf{Z},T)$ is in $\Gamma_i^{BT}$, and for
all $A \subset \{1,\ldots,L\}$ and all $X \in \chi$,
\begin{align*}
& I(X;\mathbf{U}_A|\mathbf{U}_{A^c},Y_{L+1},T) +
    \sum_{\ell \in A} I(Y_\ell;U_\ell|X,Y_{L+1},W,T) \\
 & = I(X;\mathbf{U}_A|\mathbf{U}_{A^c},Y_{L+1},T) +
     I(\mathbf{Y}_A;\mathbf{U}_A|\mathbf{U}_{A^c},X,Y_{L+1},W,T) \\
 & = I(X;\mathbf{U}_A|\mathbf{U}_{A^c},Y_{L+1},T) +
     I(\mathbf{Y}_A;\mathbf{U}_A|\mathbf{U}_{A^c},X,Y_{L+1},T) \\
 & = I(X,\mathbf{Y}_A;\mathbf{U}_A|\mathbf{U}_{A^c},Y_{L+1},T) \\
 & = I(\mathbf{Y}_A;\mathbf{U}_A|\mathbf{U}_{A^c},Y_{L+1},T).
\end{align*}
Thus
\begin{equation}
\label{tworegions}
\mathcal{RD}_o(X,\mathbf{U},\mathbf{Z},W,T) =
\mathcal{RD}_i^{BT}(\mathbf{U},\mathbf{Z},T).
\end{equation}
Conversely, if $(\mathbf{U},\mathbf{Z},T)$ is in
$\Gamma_i^{BT}$, then for any deterministic $W$,
$(\mathbf{U},\mathbf{Z},W,T)$ is in $\Gamma_o$
and~(\ref{tworegions}) holds for any $X$.
It follows that $\mathcal{RD}_i^{BT}$ is equal to
$\mathcal{RD}_o$
with $W$ restricted to be deterministic in
the definition of $\Gamma_o$.

In particular, to obtain coincident inner
and outer bounds, it suffices to show that restricting $W$ to be
deterministic in the definition of $\Gamma_o$ does not reduce
$\mathcal{RD}_o$. We will see later how this can be accomplished
in several examples. Of course, it is not possible for the problem
solved by K\"{o}rner and Marton~\cite{Korner:ModTwo}, since they show
that the inner bound is not tight in that case.

The best outer bound in the literature
is the following.
\begin{defn}
\label{BT:outer:defn}
Let $\Gamma_o^{BT}$ denote the set of finite-alphabet random
variables $\gamma = (\mathbf{U},\mathbf{Z},T)$ satisfying
\begin{enumerate}
\item[(\emph{i})] $T$ is independent of $(Y_0,\mathbf{Y},Y_{L+1})$,
\item[(\emph{ii})] $U_\ell \ensuremath{\leftrightarrow} (Y_\ell,T)
     \ensuremath{\leftrightarrow} (Y_0,\mathbf{Y}_{\ell^c},Y_{L+1})$ for all $\ell$, and
\item[(\emph{iii})] $(Y_0,\mathbf{Y}) \ensuremath{\leftrightarrow} (\mathbf{U}, Y_{L+1},T)
      \ensuremath{\leftrightarrow} \mathbf{Z}$.
\end{enumerate}
Then let
\begin{align*}
\mathcal{RD}_o^{BT}(\gamma) & = \Bigg\{(\mathbf{R},\mathbf{D}) :
\sum_{\ell \in A} R_\ell \ge I(\mathbf{Y};\mathbf{U}_A|
         \mathbf{U}_{A^c},Y_{L+1},T) \
  \text{for all $A$,} \\
 & \phantom{= \Bigg\{}
   \ \text{and} \ D_k \ge E[d_k(Y_0,\mathbf{Y},Y_{L+1},Z_k)] \
  \text{for all $k$} \Bigg\}.
\end{align*}
Finally, let
\begin{equation*}
\mathcal{RD}_o^{BT} = \bigcup_{\gamma \in \Gamma_o^{BT}}
\mathcal{RD}_o^{BT}(\gamma).
\end{equation*}
\end{defn}
\begin{prop}[\cite{Berger:MTSC,Tung:PHD}]
$\mathcal{RD}_\star \subset \mathcal{RD}_{o}^{BT}$.
\end{prop}
As with the inner bound, Berger~\cite{Berger:MTSC} and
Tung~\cite{Tung:PHD} prove the result for a model
that is more restrictive than the one considered here,
but their proof can be extended
to this setup (c.f.~\cite{Chen:CEO:Bounds,Gastpar:WZ}).
The difference between $\mathcal{RD}_i^{BT}$ and
$\mathcal{RD}_o^{BT}$ is that
condition (\emph{ii}) has been weakened in the latter.
We next show that the Berger-Tung outer bound is subsumed by the
one in the previous section.
\begin{prop}
\label{contain}
$\mathcal{RD}_o \subset \mathcal{RD}_o^{BT}$.
\end{prop}

\emph{Proof.}
First observe that for any $(\mathbf{U},\mathbf{Z},W,T)$ in
$\Gamma_o$,
\begin{equation*}
U_\ell \ensuremath{\leftrightarrow} (Y_\ell,W,T) \ensuremath{\leftrightarrow} (Y_0,\mathbf{Y}_{\ell^c},Y_{L+1})
   \ \text{for each $\ell$}.
\end{equation*}
Since
$(Y_0,\mathbf{Y}_{\ell^c},Y_{L+1}) \ensuremath{\leftrightarrow} (Y_\ell,T) \ensuremath{\leftrightarrow} W$, it holds
\begin{equation*}
U_\ell \ensuremath{\leftrightarrow} (Y_\ell,T) \ensuremath{\leftrightarrow} (Y_0,\mathbf{Y}_{\ell^c},Y_{L+1})
  \ \text{for each $\ell$}.
\end{equation*}
Thus $(\mathbf{U},\mathbf{Z},T)$ is in $\Gamma_o^{BT}$ and in
particular,
\begin{equation*}
\mathcal{RD}_o(\mathbf{Y},\mathbf{U},\mathbf{Z},W,T) =
  \mathcal{RD}_o^{BT}(\mathbf{U},\mathbf{Z},T).
\end{equation*}
It follows that
\begin{equation*}
\mathcal{RD}_o \subset \bigcup_{\gamma \in \Gamma_o} \mathcal{RD}_o(\mathbf{Y},
   \gamma) \subset \bigcup_{\gamma \in \Gamma_o^{BT}}
    \mathcal{RD}_o^{BT}(\gamma) = \mathcal{RD}_o^{BT}.
\end{equation*}
\ensuremath{\hfill \Box}

The proof reveals that
$\mathcal{RD}_o$ improves upon $\mathcal{RD}_o^{BT}$ in
two ways. The first is that $\mathcal{RD}_o$ allows
for optimization over $X$ while $\mathcal{RD}_o^{BT}$
effectively requires the choice $X = \mathbf{Y}$. The
second is that $\Gamma_o$ is ``smaller'' than
$\Gamma_o^{BT}$ in the sense that if
$(\mathbf{U},\mathbf{Z},W,T)$ is in $\Gamma_o$ then
$(\mathbf{U},\mathbf{Z},T)$ is in $\Gamma_o^{BT}$.
The balance of this section is devoted to showing
that these improvements make the containment
in Proposition~\ref{contain} strict in some
cases. As the reader will see, the former
difference is entirely responsible for the gap
that we expose between the two
bounds in our examples. We hasten to add, however,
that the latter improvement is not an empty one in
that Anantharam and Borkar~\cite{Anantharam:Mixtures}
have shown that there can exist a
$(\mathbf{U},\mathbf{Z},T)$ in $\Gamma_o^{BT}$
with the property that there does not exist a $W$
such that $(\mathbf{U},\mathbf{Z},W,T)$ is in $\Gamma_o$.
It is interesting to note that the
Anantharam-Borkar example arose independently
of this work in the context of distributed
stochastic control.

We will exhibit three examples for which $\mathcal{RD}_o^{BT}$
strictly contains $\mathcal{RD}_o$.
The first is rather contrived and can be
solved from first principles. It is included to
illustrate the difference between the two bounds.
\subsection{Toy Example}
\label{contrived}
Let $Y_{11}$, $Y_{12}$, $Y_{21}$, and $Y_{22}$ be independent
and identically distributed (i.i.d.) random variables,
uniformly distributed over $\{0,1\}$. Consider two encoders ($L = 2$) with
$Y_1 = (Y_{11},Y_{12})$ and $Y_2 = (Y_{21},Y_{22})$
(there is no hidden source or side information in this example).
We have a single distortion constraint ($K=1$)
with $\mathcal{Z}_1 = \{0,1\}^2$ and
\begin{equation*}
d_1(\mathbf{Y},Z_1) =
\begin{cases}
0 & \text{if $Z_1 = (Y_{11},Y_{21})$ or $Z_1 = (Y_{12},Y_{22})$} \\
1 & \text{otherwise}.
\end{cases}
\end{equation*}
In words, the decoder attempts to guess either the first or the
second coordinate of both encoders' observations.
It incurs a distortion of zero if it guesses correctly
the same coordinate of the two sources and one otherwise.
Note that the decoder need not declare which coordinate
it is attempting to guess.
\begin{prop}
For this problem,
\begin{equation*}
 \overline{\mathcal{RD}_o} \cap \{D_1 = 0\}
  \subset \{(R_1,R_2) : R_1 \ge \log 2, R_2 \ge \log 2 \}.
\end{equation*}
\end{prop}
\emph{Proof.}
Suppose $(R_1,R_2,\epsilon)$ is in $\mathcal{RD}_o$, and
$\epsilon \le 1/2$. Observe that since $Y_1$ and $Y_2$
are independent, deterministic random variables are in
$\chi$. Thus there exists $\gamma$ in $\Gamma_o$ such that
\begin{align*}
\epsilon & \ge E[d_1(\mathbf{Y},Z_1)] \\
R_1 & \ge I(Y_1;U_1|W,T) \\
R_2 & \ge I(Y_2;U_2|W,T).
\end{align*}
By condition (\emph{ii}) defining $\Gamma_o$,
\begin{equation}
\label{repeatii}
U_1 \ensuremath{\leftrightarrow} (Y_1,W,T) \ensuremath{\leftrightarrow} (Y_2,U_2).
\end{equation}
Since $Y_2$ is independent of $(Y_1,W,T)$ in this
example, $Y_2$ must be
independent of $(Y_1,U_1,W,T)$. Thus
\begin{equation}
\label{toycondition}
I(Y_1;U_1|W,T) = I(Y_1;U_1|W,T,Y_{21} \ne Y_{22}).
\end{equation}
Likewise, $Y_1$ is independent of $(Y_2,U_2,W,T)$ and
hence given $(W,T)$, $Y_1$ is independent of $(Y_2,U_2)$.
This observation combined with~(\ref{repeatii}) implies
$(Y_1,U_1) \ensuremath{\leftrightarrow} (W,T) \ensuremath{\leftrightarrow} (Y_2,U_2)$. In particular,
$Y_1 \ensuremath{\leftrightarrow} (U_1,W,T) \ensuremath{\leftrightarrow} (Y_2,U_2)$. By condition
(\emph{iii}) defining $\Gamma_o$, $Y_1 \ensuremath{\leftrightarrow} (Y_2,U_1,U_2,W,T) \ensuremath{\leftrightarrow}
 (Y_2,Z_1)$. These last two chains imply that
\begin{equation*}
Y_1 \ensuremath{\leftrightarrow} (U_1,W,T) \ensuremath{\leftrightarrow} (Y_2,Z_1).
\end{equation*}
Thus conditioned on $(W,T)$ and the event
$\{Y_{21} \ne Y_{22}\}$, we have $Y_1 \ensuremath{\leftrightarrow} U_1 \ensuremath{\leftrightarrow} (Y_2,Z_1)$.
It follows that
\begin{align*}
& I(Y_1;U_1|W,T,Y_{21} \ne Y_{22}) \\
 & \ge I(Y_1;Y_2,Z_1|W,T,Y_{21} \ne Y_{22}) \\
  & = I(Y_1;Y_2,Z_1,d_1(\mathbf{Y},Z_1)|W,T,Y_{21} \ne Y_{22}) \\
  & \phantom{= I(}
   - I(Y_1;d_1(\mathbf{Y},Z_1)|W,T,Y_2,Z_1,Y_{21} \ne Y_{22}) \\
  & \ge H(Y_1|W,T,Y_{21} \ne Y_{22}) - H(Y_1|Y_2,Z_1,d_1(\mathbf{Y},Z_1),
     W,T,Y_{21} \ne Y_{22}) \\
  & \phantom{= I(}
   - H(d_1(\mathbf{Y},Z_1)|W,T,Y_2,Z_1,Y_{21} \ne Y_{22}),
\end{align*}
since $d_1(\mathbf{Y},Z_1)$ is a function of $\mathbf{Y}$ and $Z_1$. Next,
observe that on the events $\{Y_{21} \ne Y_{22}\}$ and
$\{d_1(\mathbf{Y},Z_1) = 0\}$,
$Y_2$ and $Z_1$ together must reveal one of the two bits of $Y_1$.
Thus
\begin{equation*}
H(Y_1|Y_2,Z_1,d_1(\mathbf{Y},Z_1) = 0,W,T,Y_{21} \ne Y_{22}) \le \log 2.
\end{equation*}
Continuing our chain of inequalities,
\begin{align}
\nonumber
 & I(Y_1;U_1|W,T,Y_{21} \ne Y_{22}) \\
\nonumber
  & \ge 2\log 2 - \log 2 \cdot
       \Pr(d_1(\mathbf{Y},Z_1) = 0|Y_{21} \ne Y_{22}) \\
\nonumber
   & \phantom{= I(}
    - (2 \log 2) \cdot
      \Pr(d_1(\mathbf{Y},Z_1) = 1|Y_{21} \ne Y_{22}) \\
\nonumber
   &  \phantom{= I(}
   - H(d_1(\mathbf{Y},Z_1)|Y_{21} \ne Y_{22}) \\
\label{toyformula}
  & \ge \log 2 - (2\log 2) \cdot
     \Pr(d_1(\mathbf{Y},Z_1) = 1|Y_{21} \ne Y_{22}) \\
\nonumber
   &  \phantom{= I(}
     - H(d_1(\mathbf{Y},Z_1)|Y_{21} \ne Y_{22}).
\end{align}
Now
\begin{multline*}
\frac{1}{2} H(d_1(\mathbf{Y},Z_1)|Y_{21} \ne Y_{22}) +
\frac{1}{2} H(d_1(\mathbf{Y},Z_1)|Y_{21} = Y_{22}) \\
   = H(d_1(\mathbf{Y},Z_1)|1(Y_{21} = Y_{22}))
 \le H(d_1(\mathbf{Y},Z_1)) \le h(\epsilon),
\end{multline*}
where, here and throughout, $h(\cdot)$ is the binary entropy
function with natural logarithms. We conclude that
\begin{equation*}
H(d_1(\mathbf{Y},Z_1)|Y_{21} \ne Y_{22}) \le 2h(\epsilon).
\end{equation*}
Similarly,
\begin{equation*}
\Pr(d_1(\mathbf{Y},Z_1) = 1|Y_{21} \ne Y_{22}) \le 2\epsilon.
\end{equation*}
Substituting these two observations into~(\ref{toyformula}) and
recalling~(\ref{toycondition}) yields
\begin{equation*}
I(Y_1;U_1|W,T) \ge \log 2 - 4\epsilon \log 2 - 2h(\epsilon).
\end{equation*}
By symmetry, $I(Y_2;U_2|W,T)$ must satisfy the same
inequality. This implies the desired conclusion. \ensuremath{\hfill \Box}

It is easy to see that the point $(\log 2, \log 2, 0)$ is achievable.
Using rate $\log 2$,
each encoder can send, say, the first coordinate of
its observation. The decoder can then
realize zero distortion by repeating the two bits it receives.
This fact and the above proposition together imply
\begin{align*}
\overline{\mathcal{RD}_o} \cap \{D_1 = 0\} =
\overline{\mathcal{RD}_\star} \cap \{D_1 = 0\} =
\{(R_1,R_2): R_1  \ge \log 2, R_2 \ge \log 2\}.
\end{align*}
In particular, $\mathcal{RD}_o$ is tight in the zero-distortion limit.
In contrast, we show next that the Berger-Tung outer bound is not.
\begin{prop}
The point $((3/4)\log 2, (3/4)\log 2, 0)$ is contained in $\mathcal{RD}_o^{BT}$.
\end{prop}
\emph{Proof.}
Let the random variable $W$ be uniformly distributed
over $\{1,2\}$, and let $U_1 = Y_{1W}$ and
$U_2 = Y_{2W}$. Let $Z_1 = (U_1,U_2)$. It is straightforward
to verify that $(U_1,U_2,Z_1)$ is in $\Gamma_o^{BT}$ (the
time-sharing random variable $T$ is unneeded
and can be taken to be constant). Next note that
$E[d_1(\mathbf{Y},Z_1)] = 0$. Finally, one can compute
\begin{align*}
I(\mathbf{Y};U_1,U_2) & = \frac{5}{4}\log 2 \\
\intertext{and}
I(\mathbf{Y};U_1) & = \frac{1}{2}\log 2.
\end{align*}
This implies that
\begin{equation*}
I(\mathbf{Y};U_1|U_2) = I(\mathbf{Y};U_2|U_1) = \frac{3}{4} \log 2
 > \frac{5}{8}\log 2.
\end{equation*}
The conclusion follows. \ensuremath{\hfill \Box}

\subsection{Binary Erasure CEO Problem}
\label{BECEO:subsection}

Here $Y_0$ is uniformly distributed
over $\{-1,1\}$, and $Y_\ell = N_\ell \cdot Y_0$ for $\ell$ in
$\{1,\ldots,L\}$, where
$N_1,\ldots,N_L$ are i.i.d.\ with
$0 < \Pr(N_1 = 0) = p < 1$ and
$\Pr(N_1 = 1) = 1 - p$.
Let $\mathcal{Z}_1 = \{-1,0,1\}$. We will assume that
there is no side information and that
the decoder is only interested in reproducing the
hidden process
$Y_0$. We measure the fidelity of its reproduction
using a family of distortion
measures, $\{d^\lambda_1\}_{\lambda > 0}$, where
\begin{equation*}
d^\lambda_1(Y_0,\mathbf{Y},Z_1) =
\begin{cases}
0 & \text{if $Y_0 = Z_1$} \\
1 & \text{if $Z_1 = 0$} \\
\lambda & \text{otherwise}.
\end{cases}
\end{equation*}
We are particularly interested in the large-$\lambda$ limit. In
this regime, $d^\lambda_1$ approximates the ``erasure distortion
measure''~\cite[p.~370]{Cover:IT},
\begin{equation*}
d^\infty_1(Y_0,\mathbf{Y},Z_1) =
\begin{cases}
0 & \text{if $Y_0 = Z_1$} \\
1 & \text{if $Z_1 = 0$} \\
\infty & \text{otherwise}.
\end{cases}
\end{equation*}
We use a finite approximation because an infinite distortion
measure causes difficulties in the proof of the Berger-Tung
inner bound.

This example is motivated by the following problem arising in
energy-limited sensor networks.
We seek to monitor a remote source, $Y_0$.
To this end, we deploy an array of sensors, each of which is
capable of observing the source with negligible probability
of error. To lengthen the lifetime of the network, each sensor
spends a fraction $p$ of the time in a low-power ``sleep''
state. We assume that the sensors cycle between
the awake and sleep states independently of each other and on a faster
time scale than the sampling; at each
discrete time, each sensor sleeps with probability $p$,
independently of the other sensors and the past.
Sensors do not make any observations while
they are asleep, resulting in erasures. We permit the coding
process to introduce additional erasures, but not
errors, yielding the erasure distortion measure.
What sum rate is required in order for the decoder to
reproduce a fraction $1 - D$ of the $Y_0^n$ variables while
almost never making an error?
Of course, $D$ must satisfy $D \ge p^L$.

Define
\begin{equation*}
\mathcal{R}_\star(D,\lambda) = \inf\left\{ \sum_{\ell = 1}^L R_\ell :
 (R_1,\ldots,R_L,D) \in \overline{\mathcal{RD}_\star}(\lambda)\right\},
\end{equation*}
where $\overline{\mathcal{RD}_\star}(\lambda)$ is the rate-distortion
region when the distortion measure is $d_1^\lambda$. We define
$\mathcal{R}_o(D,\lambda)$ and $\mathcal{R}_i^{BT}(D,\lambda)$
analogously.

In Appendix~\ref{BECEO:achieve}, we show that if $p^L \le D \le 1$, then
\begin{equation}
\label{BECEO:sumrate}
\lim_{\lambda \rightarrow \infty} \mathcal{R}_i^{BT}(D,\lambda) \le
     (1-D)\log 2
 + L\left[h\left(D^{1/L}\right) -
(1-p)h\left(\frac{D^{1/L} - p}{1-p}\right)\right].
\end{equation}
In Appendix~\ref{BECEO:converse}, we show that the quantity
on the right-hand side is also a lower bound to
$\lim_{\lambda \rightarrow \infty} \mathcal{R}_o(D,\lambda)$.
Hence it must equal
$\lim_{\lambda \rightarrow \infty} \mathcal{R}_\star(D,\lambda)$.
That is, the improved outer bound and the Berger-Tung inner bound
together
yield a conclusive result for the sum rate of the
binary erasure CEO problem. Evidently this problem was previously
unsolved. In Appendix~\ref{BT:loose:BE}, we show that
$\overline{\mathcal{RD}_o^{BT}}$ contains points with a strictly
smaller sum rate in general. Fig.~\ref{BECEO:figure} shows
the correct sum rate for $p = 0.5$ and several values of $L$.
\begin{figure}
\begin{center}
\scalebox{.5}{\input{infinitesensors.pstex_t}}
\end{center}
\caption{Sum rate for the binary erasure CEO problem with $p = 1/2$.}
\label{BECEO:figure}
\end{figure}

\subsection{Gaussian CEO Problem~\cite{Viswanathan:CEO,Oohama:CEO,
Oohama:CEO:Region,Prabhakaran:ISIT04}}
\label{CEO:Gaussian}

We turn to a continuous example. Here
$Y_0,\ldots,Y_L$ are jointly Gaussian and
$Y_1,\ldots,Y_L$ are conditionally independent given $Y_0$.
For $\ell \ge 1$, let us write $Y_\ell = Y_0 + N_\ell$, where
$Y_0,N_1,\ldots,N_L$ are mutually independent and
\begin{equation*}
E\left[N_\ell^2\right] = \sigma^2_\ell > 0 \ \text{for all $\ell$}.
\end{equation*}
We will denote the variance of $Y_0$ by $\sigma^2$.
Again there is no side information, and the decoder is only
interested in reproducing the hidden process $Y_0$,
\begin{equation*}
d_1(Y_0,\mathbf{Y},Z_1) = (Y_0 - Z_1)^2.
\end{equation*}
The rate-distortion region for this problem was
recently found by Oohama~\cite{Oohama:Africa,Oohama:CEO:Region}
and Prabhakaran, Tse, and
Ramchandran~\cite{Prabhakaran:ISIT04}.
The two proofs are nearly the same, and build on
earlier work of Oohama~\cite{Oohama:CEO}.
The primary contribution is the converse result,
which makes heavy use of the entropy power
inequality~\cite[Theorem~16.6.3]{Cover:IT}.
The Berger-Tung inner bound is used for achievability.

It is straightforward to extend
Theorem~\ref{main} to this continuous
setting. A statement of the continuous
version is given in Appendix~\ref{Gaussian:proof},
where we also use the techniques of Oohama~\cite{Oohama:CEO:Region}
and Prabhakaran, Tse, and
Ramchandran~\cite{Prabhakaran:ISIT04} to prove the following.
\begin{prop}
\label{Gaussian:Prop}
For the Gaussian CEO problem,
\begin{multline}
\label{Gaussian:result}
\mathcal{RD}_o \subset
  \Bigg\{(R_1,\ldots,R_L,D) \in \mathbb{R}^{L+1}_+ : \ \text{there exists} \
  (r_1,\ldots,r_L) \in \mathbb{R}^L_+ : \text{for all $A$},  \\
 \sum_{\ell \in A} R_\ell \ge \frac{1}{2} \log^+ \Bigg[\frac{1}{D}
 \Bigg( \frac{1}{\sigma^2} + \sum_{\ell \in A^c}
   \frac{1 - \exp(-2r_\ell)}{\sigma^2_\ell}\Bigg)^{-1}\Bigg]
   + \sum_{\ell \in A} r_\ell \Bigg\},
\end{multline}
\end{prop}
where $\log^+ x = \max(\log x,0)$.
Since this expression equals
$\overline{\mathcal{RD}_\star}$~\cite{Oohama:CEO:Region}, we conclude
that $\mathcal{RD}_o$ is tight in this example. It also
follows that the converse result of Oohama~\cite{Oohama:CEO:Region}
and Prabhakaran, Tse, and
Ramchandran~\cite{Prabhakaran:ISIT04}
is a consequence of the outer bound provided in this paper. This
does not imply, however, that the task of
proving the converse result is made
any easier by
our bound. In fact, comparing Appendix~\ref{Gaussian:proof} to the
original works shows that proving Proposition~\ref{Gaussian:Prop}
is as formidable a task as proving the converse result unaided. But this
is still an improvement over the Berger-Tung outer bound, the closure
of which
we show in Appendix~\ref{BT:loose:Gaussian} contains points outside
the rate-distortion region.

We end this section by mentioning that Oohama's~\cite{Oohama:CEO:Region}
converse
is actually more general than the result described here,
in that Oohama permits one of the encoders to make noise-free
observations (i.e., $\sigma^2_1 = 0$). Comparing
Oohama's proof to Appendix~\ref{Gaussian:proof} shows that
the outer bound supplied in this paper also recovers this more general result.

\section{Recovery of Discrete Converse Results}
\label{recover}

Having seen that the new outer bound recovers the converse
of
Oohama~\cite{Oohama:CEO:Region} and Prabhakaran, Tse, and
Ramchandran~\cite{Prabhakaran:ISIT04} for the Gaussian CEO
problem, we show in this final section
that it also recovers the converse results for the
discrete problems of
Slepian and Wolf~\cite{Slepian:SW},
Wyner~\cite{Wyner:SCSI},
Ahlswede and K\"{o}rner~\cite{Ahlswede:SCSI},
Wyner and Ziv~\cite{Wyner:WZ},
Gel`fand and Pinsker~\cite{Gelfand:CEO},
Berger and
Yeung~\cite{Berger:BY}, and
Gastpar~\cite{Gastpar:WZ}.
The outer bound also recovers the converse
result for the problem studied by
K\"{o}rner and Marton~\cite{Korner:ModTwo},
although the proof of this fact is not as
interesting. We shall therefore
focus on the others.
To recover these converse results, we shall use the following
conclusive result for a special case of the problem.

Suppose that there exists a function $g : \mathcal{Y}_0 \mapsto
\mathcal{Y}_0$ such that $Y_1,\ldots,Y_L$ are conditionally
independent given $(g(Y_0),Y_{L+1})$. Also let
$\mathcal{Z}_1 = \mathcal{Y}_0$
and \begin{equation*}
d_1(Y_0,\mathbf{Y},Y_{L+1},Z_1) =
\begin{cases}
0 & \text{if $Z_1 = Y_0$} \\
1 & \text{otherwise.}
\end{cases}
\end{equation*}
We make no other assumptions about the problem.
We would like to characterize the set $\overline{\mathcal{RD}_\star}
\cap \{D_1 = 0\}$.
In words, conditioned on the side information and
some function of the hidden variable,
the observations are independent, and the hidden variable must
be reproduced losslessly. Note that $\overline{\mathcal{RD}_\star}
\cap \{D_1 = 0\}$ will be empty unless $H(Y_0|\mathbf{Y},Y_{L+1}) = 0$.
Gel`fand and Pinsker~\cite{Gelfand:CEO} refer to this
condition as ``completeness of observations.''
\begin{prop}
\label{reduction}
For this problem,
\begin{align}
\label{recover:main}
\overline{\mathcal{RD}_o} \cap \{D_1 = 0\} & =
\overline{\mathcal{RD}_i^{BT}} \cap \{D_1 = 0\} =
\overline{\mathcal{RD}_\star} \cap \{D_1 = 0\} \\
\label{recover:region}
  & = \bigcup_{\gamma \in \Gamma_i^{BT}} \mathcal{RD}_i^{BT}(\gamma)
   \cap \{D_1 = 0\}.
\end{align}
\end{prop}

\emph{Proof.}
To show~(\ref{recover:main}),
it suffices to show that $\overline{\mathcal{RD}_o} \cap \{D_1 = 0\}$ is
contained in $\overline{\mathcal{RD}_i^{BT}} \cap \{D_1 = 0\}$.
Suppose $(\mathbf{R},\epsilon,D_2,\ldots,D_K)$ is a point in
$\mathcal{RD}_o$ and $\epsilon \le 1/2$.
By choosing $X = g(Y_0)$ in Definition~\ref{Me:defn},
we see that there exists
$(\mathbf{U},\mathbf{Z},W,\tilde{T})$ in $\Gamma_o$
such that
\begin{align}
\nonumber
\Pr(Z_1 \ne Y_0) & \le \epsilon  \\
\nonumber
E[d_k(Y_0,\mathbf{Y},Y_{L+1},Z_k)] & \le D_k \ \text{for all $k \ge 2$},
\end{align}
and for all $A$,
\begin{equation*}
\sum_{\ell \in A} R_\ell \ge
     I(g(Y_0);\mathbf{U}_A|\mathbf{U}_{A^c},Y_{L+1},\tilde{T}) +
\sum_{\ell \in A} I(Y_\ell;U_\ell|g(Y_0),Y_{L+1},W,\tilde{T}).
\end{equation*}
Now
\begin{align*}
I(g(Y_0);\mathbf{U}_A|\mathbf{U}_{A^c},Y_{L+1},\tilde{T}) & =
    H(g(Y_0)|\mathbf{U}_{A^c},Y_{L+1},\tilde{T}) \\
 &  \phantom{H(g(Y_0)|}
   \mbox{} - H(g(Y_0)|\mathbf{U},Y_{L+1},\tilde{T}) \\
 & \ge H(g(Y_0)|\mathbf{U}_{A^c},Y_{L+1},W,\tilde{T}) - H(g(Y_0)|g(Z_1)),
\end{align*}
where we have used the fact that
\begin{equation*}
g(Y_0) \ensuremath{\leftrightarrow} Y_0 \ensuremath{\leftrightarrow} (\mathbf{U},Y_{L+1},\tilde{T}) \ensuremath{\leftrightarrow} Z_1
  \ensuremath{\leftrightarrow} g(Z_1).
\end{equation*}
By Fano's inequality~\cite[Lemma~1.3.8]{CK:IT},
\begin{equation*}
H(g(Y_0)|g(Z_1)) \le h(\epsilon) + \epsilon \log(|\mathcal{Y}_0|).
\end{equation*}
Thus
\begin{align*}
I(g(Y_0);\mathbf{U}_A|\mathbf{U}_{A^c},Y_{L+1},\tilde{T}) & \ge
H(g(Y_0)|\mathbf{U}_{A^c},Y_{L+1},W,\tilde{T}) -
     h(\epsilon) - \epsilon \log(|\mathcal{Y}_0|) \\
& \ge I(g(Y_0);\mathbf{U}_A|\mathbf{U}_{A^c},Y_{L+1},W,\tilde{T})  \\
   & \phantom{\ge I(g(Y_0);}  - h(\epsilon) - \epsilon \log(|\mathcal{Y}_0|). \\
\end{align*}
It follows that
\begin{align*}
\sum_{\ell \in A} [R_\ell + h(\epsilon) +
\epsilon\log(|\mathcal{Y}_0|) ] & \ge
I(g(Y_0);\mathbf{U}_A|\mathbf{U}_{A^c},Y_{L+1},W,\tilde{T})  \\
 & \phantom{I(Y_0;\mathbf{U}_A)} +
       \sum_{\ell \in A} I(Y_\ell;U_\ell|g(Y_0),Y_{L+1},W,\tilde{T}) \\
 & = I(g(Y_0);\mathbf{U}_A|\mathbf{U}_{A^c},Y_{L+1},W,\tilde{T})  \\
 & \phantom{I(Y_0;\mathbf{U}_A|} +
   I(\mathbf{Y}_A;\mathbf{U}_A|\mathbf{U}_{A^c},g(Y_0),Y_{L+1},W,\tilde{T}) \\
 & = I(g(Y_0),\mathbf{Y}_A;\mathbf{U}_A|\mathbf{U}_{A^c},Y_{L+1},W,\tilde{T}) \\
 & \ge I(\mathbf{Y}_A;\mathbf{U}_A|\mathbf{U}_{A^c},Y_{L+1},W,\tilde{T}) .
\end{align*}
If we now define $T = (W,\tilde{T})$, it is evident that
$(\mathbf{U},\mathbf{Z},T)$ is in $\Gamma_i^{BT}$ and the point
\begin{equation*}
(R_1 + h(\epsilon) + \epsilon\log(|\mathcal{Y}_0|),
 \ldots, R_L + h(\epsilon) + \epsilon\log(|\mathcal{Y}_0|),\epsilon,
D_2,\ldots,D_K)
\end{equation*}
is in $\mathcal{RD}_i^{BT}$. This implies that
\begin{equation*}
\overline{\mathcal{RD}_o} \cap \{D_1 = 0\}
  \subset \overline{\mathcal{RD}_i^{BT}} \cap \{D_1 = 0\},
\end{equation*}
which proves~(\ref{recover:main}). To prove~(\ref{recover:region}),
it suffices to show that $\mathcal{RD}_i^{BT}$ is closed. This
is shown in Appendix~\ref{closed}. \ensuremath{\hfill \Box}

The differences between this result and that of Gel`fand and
Pinsker~\cite{Gelfand:CEO} are numerous but minor.
The most visible differences are that Gel`fand and Pinsker's
model does not allow for side information at the decoder or
distortion constraints beyond the one on $Y_0$.
Indeed, the region given here reduces to theirs
when these extensions are ignored.
Thus this result
seems to be a generalization of theirs, albeit a trivial one
since their proof can be modified to handle these extensions.
A closer comparison,
however, reveals that they define the rate region more
stringently than we do here.
Thus, our result does not recover theirs, strictly speaking,
although it does recover
the converse component of their result since our definitions
are weaker.

The reason for including side information and
additional distortion constraints in the model is that they
enable us to also recover the converse results for
the other problems mentioned earlier.
For instance, Gastpar~\cite{Gastpar:WZ} considers the problem
of reproducing the observations individually, subject to
separate distortion constraints, under the assumption
that the decoder is provided with side information
that makes the observations conditionally independent.
His converse result can be recovered by setting
$Y_0 = Y_{L+1}$. It is easily
verified that, under this condition, our region
coincides with his. The classical Wyner-Ziv
problem~\cite{Wyner:WZ} can be viewed as Gastpar's problem
with a single encoder ($L=1$). So that converse result is
recovered too.

Berger and Yeung~\cite{Berger:BY} solve the two-encoder
problem in which the observations are to be reproduced
individually, with at least one of the two being reproduced
losslessly. In our notation, this corresponds to setting
$L = 2$ and $Y_1 = Y_0$. Note that our
conditional independence assumption necessarily holds
in this case.

To see that under these assumptions, our region reduces
to theirs, suppose $(R_1,R_2,D_2) \in \mathcal{RD}_i^{BT}(\gamma)
\cap \{D_1 = 0\}$ for some $\gamma \in \Gamma_i^{BT}$. Then
\begin{equation}
\label{BY:1}
R_1 \ge I(Y_1;U_1|U_2,T) = H(Y_1|U_2,T).
\end{equation}
Also,
\begin{align}
\nonumber
R_2 \ge I(Y_2;U_2|U_1,T) & \ge I(Y_2;U_2|U_1,Y_1,T) \\
\label{BY:2}
 & = I(Y_2;U_2|Y_1,T),
\end{align}
where we have used the fact that
\begin{equation*}
U_2 \ensuremath{\leftrightarrow} (Y_2,U_1,T) \ensuremath{\leftrightarrow} Y_1
\end{equation*}
(see Cover and Thomas~\cite[p.~33]{Cover:IT}). Finally,
\begin{align}
\nonumber
R_1 + R_2 & \ge I(Y_1,Y_2;U_1,U_2|T) \\
\nonumber
   & \ge I(Y_1;U_1,U_2|T) + I(Y_2;U_1,U_2|Y_1,T) \\
\label{BY:3}
   & \ge H(Y_1) + I(Y_2;U_2|Y_1,T).
\end{align}
It is now evident that the two regions are
identical (c.f.~\cite[p.~230]{Berger:BY}). Thus the
converse result of Berger and Yeung is a consequence of the
outer bound provided here.

The classical problem of source coding with side
information~\cite{Wyner:SCSI,Ahlswede:SCSI} can be viewed as a
special case of the Berger-Yeung problem in which $D_2$ exceeds
the maximum value of $d_2$, the distortion measure for $Y_2$.
Berger and Yeung demonstrate how, under this assumption, the
region described above reduces
to the one given by Wyner~\cite{Wyner:SCSI} and
Ahlswede and K\"{o}rner~\cite{Ahlswede:SCSI}.
\emph{Ipso facto}, the converse result for this problem is also recovered.

This paper ends the way it began, with the result
of Slepian and Wolf~\cite{Slepian:SW}.
Here the aim is to losslessly reproduce all of the observations.
For two encoders ($L = 2$), this can be
viewed as a special case of the problem of Berger and Yeung.
These authors show how the region described in
Eqs.~(\ref{BY:1})--(\ref{BY:3}) reduces to the one
given at the beginning of the paper. The result for
more than two encoders can be viewed as a special case of
Proposition~\ref{reduction} in which $Y_0 = \mathbf{Y}$.
In this case, if $\mathbf{R} \in
\overline{\mathcal{RD}_o} \cap \{D_1 = 0\}$, then
for any $A$,
\begin{align*}
\sum_{\ell \in A} R_\ell & \ge
  I(\mathbf{Y}_A;\mathbf{U}_A|\mathbf{U}_{A^c},T) \\
  & = H(\mathbf{Y}_A|\mathbf{U}_{A^c},T) \\
  & \ge H(\mathbf{Y}_A|\mathbf{Y}_{A^c},T),
\end{align*}
since $\mathbf{Y}_A \ensuremath{\leftrightarrow} (\mathbf{Y}_{A^c},T) \ensuremath{\leftrightarrow} (\mathbf{U}_{A^c},T)$.
Now $\mathbf{Y}$ is independent of $T$, so
\begin{equation*}
\sum_{\ell \in A} R_\ell \ge H(\mathbf{Y}_A|\mathbf{Y}_{A^c}),
\end{equation*}
which is the well-known rate region for this problem.
Thus the converse of Slepian and Wolf is also recovered.
For this result, as with the others, our outer bound
dispenses with the need to prove a custom converse coding
theorem. In fact, Proposition~\ref{reduction} can
be viewed as unifying all of the results
in this discussion,
assuming one is willing to ignore the discrepancies in
the definition of the rate-distortion region
mentioned earlier.


\section{Introduction} It is well known that a magnetic field produces
a frequency splitting of stellar oscillations (Ledoux \& Simon 1957).
This effect has been extensively studied, using a perturbative
approach (e.g.  Goossens 1972; { 1976a,b; 1977; Goossens, Smeyers
\& Dennis 1976;} and more recently by  Gough \& Taylor 1984;
Dziembowski \& Goode 1984, 1985; Gough \& Thompson 1990; Shibahashi \&
Takata 1993).
This method must be handled with care near the surface, where the
magnetic pressure dominates over the gas pressure, and where the
acoustic modes therefore strongly couple with the Alfv\'en modes (e.g.
Biront et al. 1982, Roberts \& Soward 1983, Campbell \& Papaloizou
1986, Dziembowski \& Goode 1996); such regions are better treated
using a non perturbative treatment (Bigot et al. 2000).

In an earlier paper Hasan and Christensen-Dalsgaard (1992) analytically
determined the frequency shift of p and g modes in an isothermal plasma due to
a homogeneous vertical magnetic field.  Using the full MHD equations, they
found that even a weak field (more precisely when $\beta \gg 1$, where $\beta$
is the ratio of gas to magnetic pressure) can produce a significant shift of
g-mode frequencies, while the effect on the p-mode spectrum is comparatively
small.  In principle this means that g-mode frequencies offer a diagnostic to
probe the internal field of stars in which g modes have been observed on the
stellar surface.

Extensive observation campaigns have uncovered the existence of a
class of variable stars known as slowly pulsating B (SPB) stars which
are multiperiodic typically over a time scale of days (Waelkens 1991;
De Cat et al. 2005 and references therein).  These pulsations have
been identified with low degree $l$ (typically $l=1$ and 2) g modes of
high order, that are excited by the $\kappa$ mechanism in the metal
opacity bump at a temperature of about $2\times 10^5$~K (Dziembowski
et al. 1993).  These modes often occur in multiplets with closely
spaced periods (with a typical separation of 1\%). In some cases this
separation can clearly not be due to rotational splitting, which would yield
much larger spacings,  as was pointed out by De Cat and Aerts (2002).
In this letter we propose that such frequency splittings are due to the
presence of a magnetic field. If this hypothesis is correct, then the
{ splitting of frequencies} can be used to estimate the field strength in
the interior of SPB stars.

\section{Magnetic frequency splitting of g modes}
As was established in the early papers quoted above, the frequency
shifts  $\delta \omega$ due to a magnetic field are given by:
\begin{equation}
{\delta \omega \over \omega} =
{1 \over 8 \pi \omega^2} {\int - \left[  (\nabla \times {\bf B'}) \times {\bf B}
+ (\nabla \times  {\bf B}) \times {\bf B'} \right] \cdot \xi^* {\rm d} V \over
\int (\xi_r^2 + l (l+1) \xi_{\rm h}^2) \rho  {\rm d} V } \; ;
\end{equation}
here $\omega$ is the angular frequency,
$\vec \xi$ is the Lagrangian displacement with radial and horizontal
components $\xi_r$ and $\xi_{\rm h}$, respectively, and
${\bf B'}=\nabla\wedge({\vec \xi} \wedge {\bf B})$ is the perturbation
in the equilibrium magnetic field $\bf B$. We shall deal here with fields whose
energy is sufficiently small compared to the gravitational energy, so that we
may neglect the structural changes caused by the Lorentz force.

{ Let us consider a poloidal axisymmetric field of the form:
\begin{equation}
{\bf B} = B_0  \left[2 b(x) \cos \theta,- {1 \over x} \partial_x(x^2 b) \sin \theta,0\right] \; ,
\end{equation}
where $x=r/R$ is the normalized radial coordinate, $R$ is the radius
of the star and $b(x) = {\cal O}(1)$, so that $B_0$ characterizes the field strength.  The displacement
$\vec \xi$ can be expressed as:
\begin{equation}
{\vec \xi}=
\left[\xi_r Y_l^m(\theta, \phi),\xi_{\rm h} \partial_\theta Y_l^m,
                   \xi_{\rm h}\ {i m \over \sin \theta}\, Y_l^m\right]  \exp i \omega t\; ,
\end{equation}
where $Y_l^m$ is the spherical harmonic of degree $l$ and azimuthal
order $m$ (henceforth, denoted as $Y$).
For a poloidal field given by equation (2), the perturbed field ${\bf
B'}$ is:
\begin{eqnarray*}
B'_r & = &
{B_0  \over R} \left[ \left[   l(l+1) \cos\theta\, Y +
  \sin\theta\,\partial_\theta Y \right]  {2 \xi_{\rm h} b \over x}   \right.\\
& & \left. - {1 \over \sin\theta}\,
\partial_\theta (\sin^2 \theta\,  Y ) \, {\xi_r \over x^2} \partial_x(x^2 b)  \right] \; , \\
B'_\theta & = & {B_0  \over R}
 \left[ \cos\theta \, \partial_\theta Y \, {1 \over  x} \partial_x (2 x  \xi_{\rm h} b)
 - \sin\theta\, Y {1 \over  x} \partial_{x} \left( \xi_r  \partial_x (x^{2} b) \right)   \right.\\
 & & \left. \phantom{ {1 \over  x} \partial_x (x^{-2} \xi_r) \sin\theta Y}
 - {m^2 Y\over \sin\theta} \, { \xi_{\rm h} \over x^2} \partial_x(x^2 b)  \right]
\; ,\\
B'_\phi &=& im {B_0  \over R}  \left[ {\cos\theta \over \sin\theta}\,Y \, {1 \over x}  \partial_x (2 x  \xi_{\rm h} b)
-   \partial_\theta\, Y \, { \xi_{\rm h}  \over  x^2} \partial_x (x^2 b)\right] \; .\\
\end{eqnarray*}
For g modes of high radial order $n$, it is straightforward to show that
in equation (1), the dominant term in the integrand of the numerator is the first one:
\begin{eqnarray}
\label{ratio}
& -& \left[(\nabla \times {\bf B'}) \times {\bf B}\right] \cdot \xi^* = \\
&& |{\bf B'}|^2 \simeq \left({B_0 \over R}\right)^2 \left|{2 \over x}
{{\rm d} \over {\rm d} x} (x b \xi_{\rm h})\right|^2
\left[\left|\cos\theta {\partial Y \over \partial \theta}\right|^2 + m^2 \left|
{\cos\theta \over \sin\theta} Y \right|^2 \right] \; , \nonumber
\end{eqnarray}
whereas in the denominator it is $|\xi_{\rm h}|^2$, since $\xi_{\rm h} \gg \xi_r$
for $n \gg 1$.  In integrating by parts, we have neglected the surface
terms; this region anyhow requires a special,
non-adiabatic and non-perturbative treatment
(see for instance Bigot et al.  2000).
From equation (1) it therefore follows that}
\begin{equation}
{\delta \omega \over \omega} = {1 \over 8 \pi \omega^2} {B_0^2 \over
\rho_{\rm c} R^2} C_{l,m}\, {\cal I} \; ,
\label{delsigma}
\end{equation}
where $\rho_{\rm c}$ is the central mass density,
\begin{equation}
{\cal I}\, ={\int \left| {2 \over x} {{\rm d} \over {\rm d} x}
(x b \xi_{\rm h})\right|^2 x^2 {\rm d} x \over
\int  |\xi_{\rm h}|^2 ( \rho/\rho_{\rm c}) x^2 {\rm d} x } \; ,
\label{delsigma1}
\end{equation}
and
\begin{equation}
C_{l,m} =
{\displaystyle \int \left[\left|\cos\theta
{\partial Y \over \partial \theta}\right|^2
+ m^2 \left| {\cos\theta \over \sin\theta} Y \right|^2 \right]
\sin\theta\, {\rm d} \theta \over
l(l+1) \int |Y|^2 \sin\theta \, {\rm d} \theta} \; .
\end{equation}
Obviously these constants do not depend on the sign of $m$: the
magnetic field reduces the $(2l+1)$ degeneracy of the eigenmodes to
only $l+1$, as already pointed out by Ledoux \& Simon (1957).  For $l=1$
and 2, we find:
\begin{equation}
C_{1,0} =  {1 \over 5} \; , \quad C_{1,1} = C_{1,-1} = {2 \over 5} \; ,
\end{equation}
\begin{equation}
C_{2,0} =  {9 \over 21} \; , \quad C_{2,1} =  C_{2,-1} = {8 \over 21} \; ,
\quad C_{2,2} =  C_{2,-2} = {5 \over 21} \; .
\end{equation}
\begin{table}
\caption{Frequency and periods for g modes of different radial orders
and degree $l=1$, for a 4 M$_\odot$ star with an age of 94 Myr.}
\label{table:1}
\centering
\begin{tabular}{c c c c c c c}
   \hline\hline \\
  & \multicolumn{2}{c}{$l=1$}& &\multicolumn{2}{c}{$l=2$}\\
\cline{2-3} \cline{5-6} \\
$n$ &  $\nu$ ($\mu$Hz) & P (d) & $n$ & $\nu$ ($\mu$Hz) & P (d)  \\  \\
   \hline \\
    23  &     6.683 & 1.732 & 40 & 6.761 &1.712   \\
    20  &     7.728 & 1.498 & 35 & 7.730 &1.497  \\
    15  &     9.983 & 1.159 & 30 & 9.035 &1.281  \\
    10  &     14.68 & 0.788 & 25 & 10.86 & 1.066 \\
    5   &     29.31 & 0.395 & 10 & 25.15 & 0.460  \\
       \hline \\
\end{tabular}
\end{table}
It is convenient to express equation (\ref{delsigma}) as:
\begin{equation}
{\delta\omega \over \omega} = S_{\rm c}\, B_0^2, \; {\rm where} \,
S_{\rm c} = {C_{lm}\ {\cal I}\over 8\pi\omega^2\rho_{\rm c} R^2} \; ,
\label{split}
\end{equation}
which we henceforth refer to as the splitting coefficient. This coefficient increases rapidly with period, since
${\cal I}$ increases also.
{ Note that a toroidal field would produce a much lesser splitting,
since the leading term in equation (\ref{ratio}) would then be $|\xi_{\rm h}|^2$
instead of $|\partial_x \xi_{\rm h}|^2$.}

Finally, let us recall that the rotational splitting for g modes of high order is given by
\begin{equation}
{\delta\omega_{\rm rot}} =
- m \left[1 - {1 \over l(l+1)} \right] \bar\Omega \; ,
\label{split-rot}
\end{equation}
where we have again assumed that $|\xi_r| \ll |\xi_{\rm h}|$;
we see that the frequency spacing
is of the order of the average angular velocity $\bar\Omega$.

\section{Model}
Following Dziembowski et al. (1993), we consider a model SPB star with
the following parameters: $M=4M_\odot$, $\log(L/L_\odot)=2.51$, $\log
T_{\rm eff}=4.142$, $X_{\rm c}=0.37$.  An equilibrium model for such a
star was calculated using the Aarhus Stellar Evolution Code (ASTEC)
(e.g. Christensen-Dalsgaard 1982, 1993); this used the Eggleton et al.
(1973) equation of state and OPAL opacities (Iglesias \& Rogers 1996)
and ignored diffusion and settling.  The evolved star had an age of 94
Myr.  We calculated the g modes of the above star using the Aarhus
adiabatic oscillation package (e.g. Christen\-sen-Dalsgaard \&
Berthomieu 1991).  Table 1 lists the cyclic frequencies $\nu$ and
periods $P$ for high-order  g modes corresponding to $l=1$ and $2$.

\begin{figure}
\resizebox{\hsize}{!}{\includegraphics{hg282_f1.eps}}
\caption{Horizontal component of the eigenfunction $\xi_{\rm h}$
(scaled such that $\xi_r = 1$ at the surface)
as a function of  normalized radius ($r/R$) for a $g_{20}^1$ mode
with a period of 1.5 d for a 4 M$_\odot$ SPB star of 94 Myr. The inset
shows an enlargement of the region close to the edge of the convective core,
where the eigenfunction displays strong oscillations due to the presence of
a steep composition gradient.}
\label{fig1}
\end{figure}

We first evaluate the frequency shift due to a magnetic field for the
$g_{20}^1$ mode (i.e. a g mode of radial order 20 and degree $l=1$),
which has a period of 1.5 d (a typical period for a SPB star). The
horizontal eigenfunction ($\xi_{\rm h}$) of this mode is shown in Figure 1:
the radial component $\xi_r$ is normalized to unity on the surface
$r=R$ of the star.

{ We calculated the numerator of equation (\ref{delsigma1})  with different
functional forms $b(x)$ for the magnetic field. When the field is
constant throughout the star, the main contribution to that integral
comes from above $x \approx 0.8$, where $\xi_{\rm h}$ has its largest
amplitude. But when the field is buried below that depth, or when it
tapers off as $b \propto x^{-q}$ with $q>1$, its main contribution
originates from a small region just above the convective core at $x_c
= 0.106$, where there is a steep gradient in the molecular weight in
this evolved star.  When we choose $b(x) = (x / x_c)^{-q}$, the
results depend little on $q$; those presented hereafter were obtained
with $q=3$.}

For this $g_{20}^1$ mode $\omega^2$ = $2.36\times 10^{-9}$ s$^{-2}$.  Using
$C_{1,1}-C_{1,0} = 1/5$, one finds $S_{\rm c} = 2.278 \times 10^{-6}$.  From
equation (\ref{split}), one deduces that in order to produce a 1\%  frequency
shift in $\delta \omega/\omega$, the polar field just above the convective core
has to be $B_{\rm pol} \simeq$ 110 kG.

For comparison, we consider now the effect of the field on a g mode of order 10
and the same degree $l = 1$.
The horizontal component of the eigenfunction for this
mode is shown in Figure 2. In this case, $B_{\rm pol} \simeq$ 1100 kG, which is
an order or magnitude larger than for the $n=20$ mode with the same degree.

Tables 2 and 3 give the splitting coefficient $S_{\rm c}$ for $l=1$
and $l=2$ g modes of various orders, and the corresponding polar
field strength $B_{\rm pol}$ required to produce a 1\% frequency shift.
In Table 3 we separate the contributions due to $C_{20}-C_{22}$ and
$C_{21}-C_{22}$ terms which produce different frequency shifts.  Note
how rapidly $S_{\rm c}$ increases with radial order $n$.

\begin{table}
\caption{Splitting constant ($S_{\rm c}$) and value of the polar field
($B_{\rm pol}$), at the edge of the convective core for $l=1$ g modes that
would produce a frequency splitting of $1\%$, for a 4 M$_\odot$ star with
an age of 94 Myr.}
\label{table:2}
\centering
\begin{tabular}{c c c c}
   \hline\hline \\
Mode & P (day) & $S_{\rm c}$ (Gauss$^{-2}$)& $B_{\rm pol}${\rm (kG)} \\
   \hline \\
$g_{20}^1$ & 1.497 & $2.278\times 10^{-6}$ & 111 \\
$g_{15}^1$ & 1.159 & $3.765\times 10^{-7}$ & 274 \\
$g_{10}^1$ & 0.789 & $2.321\times 10^{-8}$ & 1102 \\
       \hline \\
\end{tabular}
\end{table}
\begin{table}
\caption{Splitting coefficient ($S_{\rm c}$) and value of the polar field
($B_{\rm pol})$, at the edge of the convective core for $l=2$ g modes
corresponding to different transitions that would produce a frequency
splitting of $1\%$, for a 4 M$_\odot$ star with an age of 94 Myr.}
\label{table:3}
\centering
\begin{tabular}{c c c c c c c}
   \hline\hline \\
& &\multicolumn{2}{c}{$C_{2,0}-C_{2, |2|}$}
                           &  &\multicolumn{2}{c}{$C_{2, |1|}-C_{2, |2|}$} \\
\cline{3-4} \cline{6-7} \\
 \hskip-6pt Mode &  P (day) & $S_{\rm c}$ (G$^{-2}$)& \hskip-12pt B$_{\rm pol}${\rm (kG)}  \hskip-6pt  & &  \hskip-6pt $S_{\rm c}$ (G$^{-2}$)& \hskip-18pt  B$_{\rm pol}${\rm (kG)}  \\
   \hline \\
$g_{35}^2$ & 1.497 & $6.435\times 10^{-7}$ &210  & & $4.827\times 10^{-7}$  & 242   \\
$g_{30}^2$ & 1.281 & $3.422\times 10^{-7}$ &288  & & $2.566\times 10^{-7}$  & 332   \\
$g_{10}^2$ & 1.066 & $7.897\times 10^{-9}$ & 1890  & & $5.922\times 10^{-9}$  &2180   \\
       \hline \\
\end{tabular}
\end{table}

\begin{figure}
\resizebox{\hsize}{!}{\includegraphics{hg282_f2.eps}}
\caption{Same as in Fig. 1, but for the $g_{10}^1$ mode. The inset
shows an enlargement of the region close to the convective core.}
\label{fig2}
\end{figure}

\section{Discussion} Our calculations suggest that high-order g modes
can provide a sensitive diagnostic of the internal magnetic field in
SPB stars, at least when these are sufficiently evolved. The main
contribution to the splitting coefficient then comes from a small
region just above the convective core (close to $x=0.106$ in a 4
$M_\odot$ star of 94 Myr), where a steep helium gradient has built up
due to the shrinking of the convective core.  This causes a sharp peak
in the Brunt-V\"ais\"al\"a frequency $N$, which is reflected in a
series of closely spaced nodes in the horizontal eigenfunction.  In
order to examine the impact of such a region, we repeated the
calculation for a ZAMS star with the same chemical composition and
physical parameters as our evolved SPB star, and found indeed that the
frequency splitting was then much less sensitive to the strength of
the magnetic field.

We concentrated on g modes of low degree and high order, which are
typically excited in SPB stars. We found that a polar field of 110 kG
in the vicinity of the convective core causes a splitting of 1\% for a
g$^1_{20}$ mode.  For a simple dipolar configuration of the magnetic
field, this would translate into a 120 G polar field on the surface of
the star; { we quote this figure only for illustration purpose,
since there is no way to deduce the surface field from the deep field.
We have checked that the rest of the star contributes little to the
splitting, provided that the field is buried below the depth of about
$x=0.80$, or that it tapers off at a faster rate than $b \propto 1/x$.
In such a situation we find that high-order g-modes can be be used to
probe the deep interior field. This result  is not sensitive to the
precise field configuration.}

With moderate- to low-order modes, the diagnostic is much less
sensitive.  For a $l=2$, $n=10$ g mode with a period of 1.1~d, a polar
field of about 2 MG would is required to produce a frequency splitting
of 1\%.

So far only one SPB star has been detected with a magnetic field.  Recently,
Neiner et al.  (2003) have reported the discovery of a field on the SPB star
$\zeta$ Cas, in which a non-radial pulsation with a period $P=1.56$~d was
detected. A field strength for the time-averaged line of sight polar component
of $330^{+120}_{-65}$~G was inferred. If this field is the visible part of a
deeply rooted magnetic field, it could also leave a signature in the splitting
of high-order g modes.  {We should emphasize that according to our results,
a field of order 100 kG at the edge of the convective core would be required to
produce  a 1 \% splitting in typical g modes.}

We considered here only a purely poloidal configuration, { similar
to many earlier papers quoted in Sect. 1.} Such a configuration is
known to be unstable. As was shown by Tayler and collaborators (Tayler
1973, Pitts \& Tayler 1985), and as was illustrated recently by the
numerical simulations of Braithwaite and Spruit (2004), the
configurations which are likely to resist non-axisymmetric MHD
instabilities are combinations of large-scale toroidal and poloidal
fields of about equal strength. Taking this into account is unlikely
to alter our conclusions concerning the detectability of the deep
magnetic field, because the frequency splitting would be much more
sensitive { to the poloidal than to the toroidal component in such
a combined field.}

\begin{acknowledgements}
{ We thank the referee for comments clarifying the role of the global
properties of the magnetic field.}
S.S. Hasan and J.-P. Zahn are grateful to the Indo-French Centre
for the Promotion of Advanced Research, New Delhi for supporting this
project through grant number 2504-3.  We thank M. J. Thompson for
useful discussions.  J. Christensen-Dalsgaard acknowledges the
hospitality of the Indian Institute of Astrophysics, Bangalore, and
the High Altitude Observatory, Boulder, CO, U.S.A. during this project.
\end{acknowledgements}