# Synthesizing Correlated Randomness using Algebraic Structured Codes

Touheed Anwar Atif1, Arun Padakandla2 and S. Sandeep Pradhan1
Department of Electrical Engineering and Computer Science,
1University of Michigan, Ann Arbor, MI 48109, USA.
2University of Tennessee, Knoxville, USA
Email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this problem, Alice and Bob, are provided $X_{1}^{n}$ and $X_{2}^{n}$ that
are IID $p_{X_{1}X_{2}}$. Alice and Bob can communicate to Charles over
(noiseless) links of rate $R_{1}$ and $R_{2}$, respectively. Their goal is to
enable Charles generate samples $Y^{n}$ such that the triple
$(X_{1}^{n},X_{2}^{n},Y^{n})$ has a PMF that is close, in total variation, to
$\prod p_{X_{1}X_{2}Y}$. In addition, the three parties may posses shared
common randomness at rate $C$. We address the problem of characterizing the
set of rate triples $(R_{1},R_{2},C)$ for which the above goal can be
accomplished. We build on our recent findings and propose a new coding scheme
based on coset codes. We analyze its information-theoretic performance and
derive a new inner bound. We identify examples for which the derived inner
bound is analytically proven to contain rate triples that are not achievable
via any known unstructured code based coding techniques. Our findings build on
a variant of soft-covering which generalizes its applicability to the
algebraic structured code ensembles. This adds to the advancement of the use
structured codes in network information theory.

##  I Introduction

The task of generating correlated randomness at different terminals in a
network finds its applications in several communication and computing
paradigms. This task is also fundamental to several cryptographic protocols.
In this article, we provide a new information-theoretic coding framework for
generating such correlated randomness in network scenarios.

We consider the scenario which was originally studied by authors in [1], as
depicted in Fig 1. Three distributed parties, say Alice, Bob and Charles, have
to generate samples that are independent and identically distributed (IID)
with a target probability mass function (PMF) $p_{X_{1}X_{2}Y}$. Alice and Bob
are provided with samples that are IID according to $p_{X_{1}X_{2}}$ \- the
marginal of the target PMF $p_{X_{1}X_{2}Y}$. They have access to unlimited
private randomness and share noiseless communication links of rates
$R_{1},R_{2}$ with Charles. In addition, the three parties share common
randomness at rate $C$. The authors in [1] provided a set of sufficient
conditions, i.e., an achievable rate region for such a scenario. However, can
this rate-region be improved? This article answers the above question in the
affirmative.

It is well established that traditional coding techniques using unstructured
codes do not achieve optimality for the several multi-terminal scenarios. For
instance, the work by Körner-Marton [2] demonstrated this sub-optimality for a
classical distributed lossless compression problem with symmetric binary
sources using random linear codes. We harness analogous gains for the problem
of generating correlated randomness at distributed parties. Specifically, we
propose a coding scheme based on coset codes, analyze its information-
theoretic performance and thereby derive a new inner bound (see Thm. 1). We
identify an example for which the derived inner bound is analytically proven
to contain rate triples that are not achievable in the earlier known results
[1]. While the derived inner bound does not subsume the one characterized in ,
one can adopt the technique in [3, Sec. VII] \- also demonstrated in a related
context [4] \- to derive an inner bound that subsumes the inner bounds derived
in [1] and Thm. 1.

The problem of generating correlated randomness can be traced back to Wyner
[5], whose work discovered the important technical tool, called the soft
covering. This tool has found its application in diverse fields including
cryptography and quantum information theory. The work in [1] further refined
this tool by introducing a joint-typicality based application. As we
illustrate in the sequel, this work adds another dimension to our current
understanding of soft covering, what we term as the change of measure soft
covering.

A renewed interest in soft covering led Cuff [6], [7] to consider a point-to-
point (PTP) version of the scenario depicted in Fig. 1, wherein Bob (or
$X_{2}$) is absent. A side-information based scenario was subsequently studied
in [8] and a converse provided in [1]. In [1] we studied the above scenario
using unstructured coding techniques. A similar sequence of problems were also
studied in the quantum setting [9, 10, 11].

Figure 1:  Source Coding for Synthesizing Correlated Randomness

While all of the above works leverage the unstructured IID random codes, it
has been proven that algebraic structured codes provide gains in network
communication involving distributed encoders [12, 13, 14, 15, 16, 4, 17].
Motivated by this, we consider the distributed correlation synthesis problem
depicted in Fig. 1 and present a new achievable rate-region using structured
coding techniques. We highlight two main challenges in this endeavour. The
first challenge is to be able to achieve rates corresponding to non-uniform
distributions. In particular, codewords within a random linear code has
uniform empirical distributions. This requires us to enlarge our codes to be
able to identify codeword with the desired single-letter distribution. We
address this challenge by using a random shifts of cosets of a linear code as
our code, henceforth referred to as Unionized Coset Codes (UCCs) [16]. The
second challenge concerns the statistical dependence among codewords of a
coset code. In contrast to IID codes, the codewords of a UCC are only pairwise
independent [18]. This prevents us from using the Chernoff concentration
bound. We therefore develop novel techniques for our information theoretic
study.

##  II Preliminaries and Problem Statement

We supplement standard information theory notation with the following. For a
PMF $p_{X}$, we let $p^{n}_{X}=\prod_{i=1}^{n}p_{X}$. For an integer $n\geq
1$,
$[n]\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\\{1,\cdots,n\\}$.
The total variation between PMFs $p_{X}$ and $q_{X}$ defined over
$\mathcal{X}$ is denoted
$\|p_{X}-q_{X}\|_{1}=\frac{1}{2}\sum_{x\in\mathcal{X}}|p_{X}(x)-q_{X}(x)|$.
$\mathbb{F}_{p}$ is used to denote a finite field of size $p$ with addition
$\oplus.$

Building on this, we address the network scenario (Fig. 1) for which we state
the problem below. In the following, we let
$\underline{X}=(X_{1},X_{2}),\underline{x}^{n}=(x^{n}_{1},x^{n}_{2})$.

######  Definition 1.

Given a PMF $p_{X_{1}X_{2}Y}$ on
$\mathcal{X}_{1}\crossproduct\mathcal{X}_{2}\crossproduct\mathcal{Y}$, a rate
triple $(R_{1},R_{2},C)$ is achievable, if $\forall\epsilon\\!>\\!0$ and
sufficiently large $n$, there exists $2^{nC}$ randomized encoder pairs
$E_{j}^{(\mu)}:\mathcal{X}_{j}^{n}\rightarrow[\Theta_{j}]:j\in[2],\mu\in[2^{nC}]$,
and a corresponding collection of $2^{nC}$ randomized decoders
$D^{(\mu)}:[\Theta_{1}]\times[\Theta_{2}]\rightarrow\mathcal{Y}^{n}$ for
$\mu\in[2^{nC}]$ such that
$\left|p^{n}_{\underline{X}Y}-p_{\underline{X}^{n}Y^{n}}\right|_{1}\leq\epsilon$,
$\frac{1}{n}\log_{2}\Theta_{j}\leq R_{j}+\epsilon:j\in[2]$, where

$\displaystyle
p_{\underline{X}^{n}Y^{n}}(\underline{x}^{n},y^{n})=\\!\\!\\!\\!\sum_{\mu\in[2^{nC}]}\\!\\!\\!2^{-nC}\\!\\!\\!\\!\\!\sum_{\begin{subarray}{c}(m_{1},m_{2})\in\\\
[\Theta_{1}]\times[\Theta_{2}]\end{subarray}}\\!\\!\\!\\!p^{n}_{\underline{X}Y}(\underline{x}^{n},y^{n})$
$\displaystyle
p^{(\mu)}_{M_{1}|X_{1}^{n}}(m_{1}|x_{1}^{n})p^{(\mu)}_{M_{2}|X_{2}^{n}}(m_{2}|x_{2}^{n})p^{(\mu)}_{Y^{n}|M_{1},M_{2}}(y^{n}|m_{1},m_{2})$

$p^{(\mu)}_{M_{j}|X_{j}^{n}}:j\in[2],p^{(\mu)}_{Y^{n}|M_{1},M_{2}}$ are the
PMFs induced by the two randomized encoders and decoder respectively,
corresponding to common randomness message $\mu$. We let
$\mathcal{R}_{d}(p_{\underline{X}Y})$ denote the set of achievable rate
triples.

Theorem 1 provides a new characterization of
$\mathcal{R}_{d}(p_{\underline{X}Y})$ based on coset codes, for the above
described problem statement. This characterization provides a new inner bound
to the achievable rate-region. An essential aspect of our work is the
identification of a PMF $p_{X_{1}X_{2}Y}$ for which the coding scheme
described in [1, 19] is strictly sub-optimal.

##  III Distributed Soft Covering using Algebraic Structured Random Codes

###  III-A Change of Measure Soft Covering

Before presenting the main result of the paper, we develop the necessary tools
and provide a lemma which is crucial for the upcoming results. This lemma
extends the cloud mixing result of [7] with a mismatched codebook generation
process. The lemma is as follows.

######  Lemma 1.

Consider a PMF $p_{XY}$ on $\mathcal{X}\crossproduct\mathcal{Y},$ and let $R$
be a finite non-negative integer. Additionally, assume that there exists some
set $\bar{\mathcal{X}}$ containing the set $\mathcal{X}$, with $p_{XY}(x,y)=0$
for all $x\in\bar{\mathcal{X}}\backslash\mathcal{X}$. Suppose $q_{X}$ is any
PMF on the set $\bar{\mathcal{X}}$ such that the PMF $p_{X}$ is absolutely
continuous with respect to the $q_{X}$. Let a random code
$\mathbb{C}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\\{X^{n}(m):m\in[2^{nR}]\\}$
be defined as a collection of codewords chosen pairwise independently from the
set $\bar{\mathcal{X}}$ according to the PMF $q_{X}^{n}$. Then we have for
$R\geq H_{q}(X)-H_{p}(Y|X)=I_{p}(X;Y)-H_{p}(X)+H_{q}(X)$,

$\displaystyle\lim_{n\rightarrow\infty}\mathbb{E}_{\mathbb{C}}$
$\displaystyle\left[\sum_{y^{n}\in\mathcal{Y}^{n}}\Big{|}p^{n}_{Y}(y^{n})-\frac{1}{M}\sum_{m=1}^{2^{nR}}\frac{p^{n}_{X}(X^{n}(m))}{q^{n}_{X}(X^{n}(m))}p^{n}_{Y|X}(y^{n}|X^{n}(m))\Bigg{|}\right]=0$

###### Proof.

The proof follows similar analysis as the proof of [20, Lemma 19] as hence is
omitted.

∎

###  III-B Main Result

Our main result is the characterization of
$\mathcal{R}_{s}(p_{\underline{X}Y})$ which is the inner bound to
$\mathcal{R}_{d}(p_{\underline{X}Y})$. In the following, we let
$\underline{X}=(X_{1},X_{2}),\underline{W}=(W_{1},W_{2}),\underline{x}=(x_{1},x_{2})$
and $\underline{w}=(w_{1},w_{2})$.

######  Theorem 1.

Given a PMF $p_{X_{1}X_{2}Y}$, let $\mathcal{P}(p_{X_{1}X_{2}Y})$ denote the
collection of all PMFs $p_{QW_{1}W_{2}\underline{X}Y}$ defined on
$\mathcal{Q}\times\mathcal{W}_{1}\times\mathcal{W}_{2}\times\mathcal{\underline{X}}\times\mathcal{Y}$
such that (i)
$p_{\underline{X}Y}(\underline{x},y)=\sum_{(q,\underline{w})\in\mathcal{Q}\times\underline{\mathcal{W}}}p_{Q\underline{W}\underline{X}Y}(q,\underline{w},\underline{x},y)$
for all $(\underline{x},y)\in\underline{\mathcal{X}}\crossproduct\mathcal{Y}$,
(ii) $W_{1}-QX_{1}-QX_{2}-W_{2}$ and $\underline{X}-Q\underline{W}-Y$ are
Markov chains, (iii) $|\mathcal{W}_{1}|\leq|\mathcal{X}_{1}|$,
$|\mathcal{W}_{2}|\leq|\mathcal{X}_{2}|$. Further, let
$\beta(p_{Q\underline{W}\underline{X}Y})$ denote the set of rates and common
randomness triple $(R_{1},R_{2},C)$ that satisfy

$\displaystyle{R}_{1}$ $\displaystyle\geq I(X_{1};W_{1}|W_{2},Q)+I(W_{1}\oplus
W_{2};W_{2}|Q)$ $\displaystyle{R}_{2}$ $\displaystyle\geq
I(X_{2};W_{2}|W_{1},Q)+I(W_{1}\oplus W_{2};W_{1}|Q)$ $\displaystyle{R}_{1}+C$
$\displaystyle\geq
I(\underline{X};W_{1}|W_{2},Q)+I(Y;W_{1}|\underline{X},Q)+I(W_{1}\oplus
W_{2};W_{2}|Q)$ $\displaystyle{R}_{2}+C$ $\displaystyle\geq
I(\underline{X};W_{2}|W_{1},Q)+I(Y;W_{2}|\underline{X},Q)+I(W_{1}\oplus
W_{2};W_{1}|Q)$ $\displaystyle R_{1}+R_{2}+C$ $\displaystyle\geq
I(\underline{X};W_{1}|W_{2},Q)+I(\underline{X};W_{2}|W_{1},Q)+I(W_{1}\oplus
W_{2};W_{1}|Q)+I(W_{1}\oplus W_{2};W_{2}|Q),$ (1)

where the above information theoretic terms are evaluated with respect to the
PMF $p_{QW_{1}W_{2}\underline{X}Y}$. Let

$\displaystyle\mathcal{R}_{s}(p_{\underline{X}Y})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\text{Closure}\left(\bigcup_{p_{Q\underline{W}\underline{X}Y}\in\mathcal{P}(p_{X_{1}X_{2}Y})}\beta(p_{Q\underline{W}\underline{X}Y})\right)$
(2)

We have

$\mathcal{R}_{s}(p_{\underline{X}Y})\subseteq\mathcal{R}_{d}(p_{\underline{X}Y}).$

In other words, the rate triple
$(R_{1},R_{2},C)\in\left(\bigcup_{p_{Q\underline{W}\underline{X}Y}\in\mathcal{P}(p_{X_{1}X_{2}Y})}\beta(p_{Q\underline{W}\underline{X}Y})\right)$
is achievable.

Note that the rate-region obtained in Theorem 2 of [19] contains the
constraint $R_{1}+R_{2}+C\geq I(X_{1}X_{2}Y;W_{1}W_{2}|Q)$. Hence when
$2H(W_{1}\oplus W_{2}|Q)<H(W_{1},W_{2}|Q),$ the above theorem gives a lower
sum rate constraint. As a result, the rate-region above contains points that
are not contained within the rate-region provided in [19]. To illustrate this
fact further, consider the following example.

######  Example 1.

Let $X_{1}$ and $X_{2}$ be a pair of binary symmetric correlated sources with
$P(X_{2}=1|X_{1}=0)=p$, for some $p\in(0,0.5)$. Let $Y=X_{1}\oplus X_{2}\oplus
Q$, where $P(Q=1)=q$, for some $q\in(0,0.5)$. Consider $q=p=0.1$ for a
numerical evaluation. Let us first consider the inner bound
$\mathcal{R}_{u}(p_{\underline{X},Y})$ to the rate region
$\mathcal{R}(p_{\underline{X},Y})$ given in [1], developed using unstructured
code ensemble. Due to symmetry in the example, it turns out that the search
over the auxiliary random variables for minimization reduces to a single-
parameter minimization which can be computed through derivative techniques.
The computation details are not provided for the sake of brevity. In
particular, the minimum value of $R_{1}+R_{2}+C$ can be computed to be
$1.3965$. Next let us consider the new inner bound
$\mathcal{R}_{s}(p_{\underline{X},Y})$ developed using structured code
ensemble (Theorem 1). The minimum value of $R_{1}+R_{2}+C$ can be computed to
be $0.9596$.

The results can also be verified for the special case of $q=0$ which we
provide in the following. Using the arguments given in proof of Proposition 1
of [2], one can show that

$\displaystyle\mathcal{R}_{u}(p_{\underline{X},Y})$
$\displaystyle=\\{(R_{1},R_{2},C):R_{1}\geq h_{b}(p),R_{2}\geq h_{b}(p),$
$\displaystyle R_{1}+R_{2}\geq 1+h_{b}(p),C\geq 0\\}.$

Next let us consider the new inner bound
$\mathcal{R}_{s}(p_{\underline{X},Y})$ developed using structured code
ensemble (Theorem 1). By choosing $W_{1}=X_{1}$ and $W_{2}=X_{2}$, we see that
the following triple of rates is achievable:

$\\{(R_{1},R_{2},C):R_{1}\geq h_{b}(p),R_{2}\geq h_{b}(p),C\geq 0\\}.$

In fact, one can show that this is optimal using the side information
argument. If $X_{2}$ is sent losslessly, then from the converse argument in
the side information case, we see that $R_{1}\geq H(X_{2}|X_{1})=h_{b}(p)$.

##  IV Proof of Distributed Soft Covering using Algebraic Structured Random
Codes

The coding strategy used here is based on Unionized Coset Codes, defined in
Definition (2). The structure in these codes provides a method to exploit the
structure present in the stochastic processing applied by decoder, i.e.,
$P_{Y|W_{1}+W_{2}}$. Using this technique, we aim to strictly reduce the rate
constraints compared to the ones obtained in Theorem 1 of [1].

Let $\mu\in[2^{nC}]$ denote the common randomness shared amidst all terminals.
The first encoder uses a part of the entire common randomness available to it,
say $C_{1}$ bits out of the $C$ bits, which is denoted by
$\mu_{1}\in[2^{nC_{1}}]$. Similarly, let $\mu_{2}\in[2^{nC_{2}}]$ denote the
common randomness used by the second encoder. Our goal is to prove the
existence of PMFs
$p_{M_{1}|X_{1}^{n}}^{(\mu_{1})}(m_{1}|x_{1}^{n}):x_{1}^{n}\in\mathcal{X}_{1}^{n},m_{1}\in[\Theta_{1}],\mu_{1}\in[2^{nC_{1}}],p^{\mu_{2}}_{M_{2}|X_{2}^{n}}(m_{2}|x_{2}^{n}):x_{2}^{n}\in\mathcal{X}_{2}^{n},m_{2}\in[\Theta_{2}],\mu_{2}\in[2^{nC_{2}}]$,
$p_{Y^{n}|M_{1},M_{2}}(y^{n}|m_{1},m_{2}):y^{n}\in\mathcal{Y}^{n},(m_{1},m_{2})\in[\Theta_{1}]\times[\Theta_{2}]$
such that

$\displaystyle\mathscr{Q}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\\!\cfrac{1}{2}$
$\displaystyle\\!\\!\sum_{\underline{x}^{n},y^{n}}\Bigg{|}p^{n}_{\underline{X}Y}(\underline{x}^{n},y^{n})-\\!\\!\\!\\!\sum_{\begin{subarray}{c}\mu\in[2^{nC}]\end{subarray}}\sum_{\begin{subarray}{c}m_{1}\in[\Theta_{1}],\\\
m_{2}\in[\Theta_{2}]\end{subarray}}\\!\\!\\!\\!\frac{p^{n}_{\underline{X}}(\underline{x}^{n})}{2^{nC}}p^{(\mu_{1})}_{M_{1}|X_{1}^{n}}(m_{1}|x_{1}^{n})p^{(\mu_{2})}_{M_{2}|X_{2}^{n}}(m_{2}|x_{2}^{n})p^{(\mu)}_{Y^{n}|\underline{M}}(y^{n}|\underline{m})\Bigg{|}\leq\varepsilon,$
$\displaystyle\frac{\log\Theta_{j}}{n}\leq R_{j}+\epsilon:j\in[2],$ (3)

for sufficiently large $n$. Fix a block length $n>0$, a positive integer $N$
and a finite field $\mathbb{F}_{p}$. Further, let $W_{1}$ and $W_{2}$ be
random variables defined on the alphabets $\mathcal{W}_{1}$ and
$\mathcal{W}_{2}$, respectively, where
$\mathcal{W}_{1}=\mathcal{W}_{2}=\mathbb{F}_{p},$ and let
$Z\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}W_{1}\oplus
W_{2}.$ In building the code, we use the Unionized Coset Codes (UCCs) [16]
defined as below. These codes involve two layers of codes (i) a coarse code
and (ii) a fine code. The coarse code is a coset of the linear code and the
fine code is the union of several cosets of the linear code.

For a fixed $k\times n$ matrix $G\in\mathbb{F}_{p}^{k\times n}$ with $k\leq
n$, and a $1\times n$ vector $B\in\mathbb{F}_{p}^{n}$, define the coset code
as

$\mathbb{C}(G,B)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\\{x^{n}:x^{n}=a^{k}G+B,\mbox{
for some }a^{k}\in\mathbb{F}_{p}^{k}\\}.$

In other words, $\mathbb{C}(G,B)$ is a shift of the row space of the matrix
$G$. The row space of $G$ is a linear code. If the rank of $G$ is $k$, then
there are $p^{k}$ codewords in the coset code.

######  Definition 2.

An $(n,k,l,p)$ UCC is a pair $(G,h)$ consisting of a $k\times n$ matrix
$G\in\mathbb{F}_{p}^{k\times n}$, and a mapping
$h:\mathbb{F}_{p}^{l}\rightarrow\mathbb{F}_{p}^{n}$. In the context of UCC,
define the composite code as
$\mathbb{C}=\bigcup_{i\in\mathbb{F}_{p}^{l}}\mathbb{C}(G,h(i))$.

For every
$\mu\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}(\mu_{1},\mu_{2})$,
consider two UCCs $(G,h_{1}^{(\mu_{1})})$ and $(G,h_{2}^{(\mu_{2})})$, each
with parameters $(n,k,l_{1},p)$ and $(n,k,l_{2},p)$, respectively. Note that,
for every $\mu\in[N],$ the generator matrix $G$ remains the same.

For each $(\mu_{1},\mu_{2})$, the generator matrix $G$ along with the function
$h_{1}^{\mu_{1}}$ and $h_{2}^{\mu_{2}}$ generates $p^{k+l_{1}}$ and
$p^{k+l_{2}}$ codewords, respectively. Each of these codewords are
characterized by a triple $(a_{i},m_{i},\mu_{i})$, where
$a_{i}\in\mathbb{F}^{k}_{p}$ and $m_{i}\in\mathbb{F}^{l_{i}}_{p}$ corresponds
to the coarse code and the fine code indices, respectively, for $i\in[2]$. Let
$\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})$ and
$\mathtt{w}_{2}(a_{2},m_{2},\mu_{2})$ denote the codewords associated with
Alice and Bob, generated using the above procedure, respectively, where
$\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}a_{1}G+h_{1}^{(\mu_{1})}(i),$
and
$\mathtt{w}_{2}(a_{2},m_{2},\mu_{2})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}a_{2}G+h_{2}^{(\mu_{2})}(j).$

Consider the collections $c_{1}=(c_{1}^{(\mu_{1})}:1\leq\mu_{1}\leq
2^{nC_{1}})$ where $c_{1}^{(\mu_{1})}=(\mathtt{w}_{1}(l_{1},\mu_{1}):1\leq
l_{1}\leq 2^{n\tilde{R}_{1}})$ and $c_{2}=(c_{1}^{(\mu_{1})}:1\leq\mu_{1}\leq
2^{nC_{1}})$ where $c_{2}^{(\mu_{2})}=(\mathtt{w}_{2}(l_{2},\mu_{2}):1\leq
l_{2}\leq 2^{n\tilde{R}_{2}})$. For this collection, we let

$\displaystyle E^{(\mu_{1})}_{L_{1}|X_{1}^{n}}(a_{1},\\!m_{1}|x_{1}^{n})$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\begin{subarray}{c}w_{1}^{n}\in
T_{\delta}(W_{1}|x_{1}^{n})\end{subarray}}{p^{n}}\frac{p^{n}_{W_{1}|X_{1}}\\!\\!(w_{1}^{n}|x_{1}^{n})}{2^{nS_{1}}(1+\eta)}\\!\mathbbm{1}_{\\{\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})=w_{1}^{n}\\}},$
$\displaystyle E_{L_{2}|X_{2}^{n}}^{(\mu_{2})}(a_{2},\\!m_{2}|x_{2}^{n})$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\begin{subarray}{c}w_{2}^{n}\in
T_{\delta}(W_{2}|x^{n}_{2})\end{subarray}}{p^{n}}\frac{p^{n}_{W_{2}|X_{2}}\\!(w_{2}^{n}|x_{2}^{n})}{2^{nS_{2}}(1+\eta)}\\!\mathbbm{1}_{\\{\mathtt{w}_{2}(a_{2},m_{2},\mu_{2})=w_{2}^{n}\\}}.$
(4)

The definition of $E^{(\mu_{1})}_{L_{1}|X_{1}^{n}}$ and
$E^{(\mu_{2})}_{L_{2}|X_{2}^{n}}$ can be thought of as encoding rules that do
not exploit the additional rebate obtained by using binning techniques,
specifically in a distributed setup.

###  IV-A Binning of Random Encoders

We next proceed to binning the above constructed collection of random
encoders. Since, UCC is already a union of several cosets, we associate a bin
to each coset, and place all the codewords of a coset in the same bin. For
each $i\in\mathbb{F}_{p}^{l_{1}}$ and $j\in\mathbb{F}_{p}^{l_{2}}$, let
$\mathcal{B}^{(\mu_{1})}_{1}(i)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\mathbb{C}(G,h_{1}^{(\mu_{1})}(i))$
and
$\mathcal{B}^{(\mu_{2})}_{2}(j)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\mathbb{C}(G,h_{2}^{(\mu_{2})}(j))$
denote the $i^{th}$ and the $j^{th}$ bins, respectively. Formally, we define
the following PMFs.

$\displaystyle
p_{M_{1}|X_{1}^{n}}^{(\mu_{1})}(m_{1}|x_{1}^{n})=\begin{cases}\mathbbm{1}_{\\{m_{i}=0\\}}&\mbox{if
}s_{i}^{(\mu_{i})}(x_{i}^{n})>1,\\\ 1-s_{i}^{(\mu_{i})}(x_{i}^{n})&\mbox{if
}m_{i}=0\mbox{ and }s_{i}^{(\mu_{i})}(x_{i}^{n})\\!\in[0,1],\\\
\displaystyle\sum_{a_{i}\in\mathbb{F}_{p}^{k}}E^{(\mu_{i})}_{L_{i}|X_{i}^{n}}(a_{i},\\!m_{i}|x_{i}^{n})&\mbox{if
}m_{i}\neq 0\mbox{ and }s_{i}^{(\mu_{i})}(x_{i}^{n})\\!\in[0,1],\end{cases}$

for all $x_{i}^{n}\in T_{\delta}(X_{i})$, $s_{i}^{(\mu_{i})}(x_{i}^{n})$
defined as
$s_{i}^{(\mu_{i})}(x_{i}^{n})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{a_{i}\in\mathbb{F}_{p}^{k}}\sum_{m_{i}\in\mathbb{F}_{p}^{l_{i}}}E^{(\mu_{i})}_{L_{i}|X_{i}^{n}}(a_{i},m_{i}|x_{i}^{n})$
and $i\in[2]$. For $x_{1}^{n}\notin T_{\delta}(X_{1})$, we let
$p_{M_{1}|X_{1}^{n}}^{(\mu_{1})}(m_{1}|x_{1}^{n})=\mathbbm{1}_{\\{m_{1}=0\\}}.$

With this definition note that,
$\sum_{m_{1}=0}^{2^{nR_{1}}}p_{M_{1}|X_{1}^{n}}^{(\mu_{1})}(m_{1}|x_{1}^{n})=1$
for all $\mu_{1}\in[2^{nC_{1}}]$ and $x^{n}_{1}\in\mathcal{X}_{1}^{n}$ and
similarly,
$\sum_{m_{2}=0}^{2^{nR_{2}}}p_{M_{2}|X_{2}^{n}}^{(\mu_{2})}(m_{2}|x_{2}^{n})=1$
for all $\mu_{2}\in[2^{nC_{2}}]$ and $x^{n}_{2}\in\mathcal{X}_{2}^{n}$.

Also, note that the effect of introducing binning (by defining the above PMFs)
is in reducing the communication rates from $(S_{1},S_{2})$ to
$(R_{1},R_{2})$, where $R_{i}=\frac{l_{i}}{n}\log{p},i\in\\{1,2\\}$. Now, we
move on to describing the decoder.

###  IV-B Decoder mapping

We create a decoder that takes as an input a pair of bin numbers and produces
a sequence $W^{n}\in\mathbb{F}^{n}_{p}$. More precisely, we define a mapping
$f^{(\mu)}$ for
$\mu\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}(\mu_{1},\mu_{2})$,
acting on the messages $(m_{1},m_{2})$ as follows. On observing $\mu$ and the
classical indices
$(m_{1},m_{2})\in\mathbb{F}_{p}^{l_{1}}\times\mathbb{F}_{p}^{l_{2}}$
communicated by the encoder, the decoder constructs
$D^{(\mu)}_{i,j}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\\{\tilde{a}\in\mathbb{F}_{p}^{k}:\tilde{a}G+h_{1}^{(\mu_{1})}(i)+h_{2}^{(\mu_{2})}(j)\in\mathcal{T}_{\hat{\delta}}^{(n)}(Z)\\},$
and $f^{(\mu)}(m_{1},m_{2})$

$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\begin{cases}\tilde{a}G+h_{1}^{(\mu_{1})}(i)+h_{2}^{(\mu_{2})}(j)&\quad\text{
if }D^{(\mu_{1},\mu_{2})}_{i,j}\equiv\\{\tilde{a}\\}\\\ w^{n}_{0}&\quad\text{
otherwise },\end{cases}$ (5)

where $\hat{\delta}=p\delta$ and $w_{0}^{n}$ is an additional sequence added
to $\mathbb{F}_{p}^{n}$. Further, $f^{(\mu)}(m_{1},m_{2})=w_{0}^{n}$ for $i=0$
or $j=0$. The decoder then performs a stochastic processing of the output and
chooses $y^{n}$ according to PMF $p^{n}_{Y|Z}(y^{n}|f^{(\mu)}(m_{1},m_{2}))$.
This implies the PMF $p^{(\mu_{1})}_{Y^{n}|M_{1}M_{2}}(\cdot|\cdot)$ is given
by

$\displaystyle
p^{(\mu)}_{Y^{n}|M_{1}M_{2}}(\cdot|m_{1},m_{2})=p^{n}_{Y|Z}(y^{n}|f^{(\mu)}(m_{1},m_{2})).$
(6)

We now begin our analysis of the total variation term given in (3).

###  IV-C Analysis of Total Variation

Our goal is to prove the existence of a collections $c_{1},c_{2}$ for which
(3) holds. We do this via random coding. Specifically, we prove that
$\mathbb{E}[{K}]\leq\epsilon$, where the expectation is over the ensemble of
codebooks. The PMF induced on the ensemble of codebooks is as specified below.
The codewords of the random codebook
$C_{i}^{(\mu_{i})}=(\mathtt{W}_{i}(a_{i},m_{i},\mu_{i}):a_{i}\in\mathbb{F}_{p}^{k},m_{i}\in\mathbb{F}_{p}^{l_{i}})$
for each $\mu_{i}\in[2^{nC_{i}}]$ are only pairwise independent [16] and
distributed with PMF
$\mathbb{P}(\mathtt{W}_{i}(a_{i},m_{i},\mu_{i})=w_{i}^{n})=\frac{1}{p^{n}}$
for each $i\in[2].$

Step 1: Error caused by not covering
We begin by splitting $K$ into two terms using the triangle inequality as
$K\leq S+\tilde{S}$, where

$\displaystyle
S\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}$
$\displaystyle\sum_{\underline{x}^{n},y^{n}}\Bigg{|}p^{n}_{\underline{X}Y}(\underline{x}^{n},y^{n})-\sum_{\begin{subarray}{c}\mu_{1},\mu_{2}\end{subarray}}\sum_{\begin{subarray}{c}m_{1}>0,\\\
m_{2}>0\end{subarray}}\frac{p^{n}_{\underline{X}}(\underline{x}^{n})p^{(\mu_{1})}_{M_{1}|X_{1}^{n}}(m_{1}|x_{1}^{n})}{2^{n(C_{1}+C_{2})}}p^{(\mu_{2})}_{M_{2}|X_{2}^{n}}(m_{2}|x_{2}^{n})p^{(\mu)}_{Y^{n}|\underline{M}}(y^{n}|\underline{m})\Bigg{|},$
$\displaystyle\tilde{S}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}$
$\displaystyle\sum_{\underline{x}^{n},y^{n}}\Bigg{|}\sum_{\begin{subarray}{c}\mu_{1},\mu_{2}\end{subarray}}\sum_{\begin{subarray}{c}m_{1}=0\mathbin{\scalebox{1.2}{$\cup$}}m_{2}=0\end{subarray}}\frac{p^{n}_{\underline{X}}(\underline{x}^{n})}{2^{n(C_{1}+C_{2})}}p^{(\mu_{1})}_{M_{1}|X_{1}^{n}}(m_{1}|x_{1}^{n})p^{(\mu_{2})}_{M_{2}|X_{2}^{n}}(m_{2}|x_{2}^{n})p^{(\mu)}_{Y^{n}|\underline{M}}(y^{n}|\underline{m})\Bigg{|}.$

Note that $\widetilde{S}$ captures the error induced by not covering
$p^{n}_{\underline{X}Y}$. For the term corresponding to $\widetilde{S}$, we
prove the following result by developing the following lemma below followed by
a proposition.

######  Lemma 2.

For the above defined notations, for $i\in\\{1,2\\}$, if $S_{i}\geq
I(X_{i};W_{i})+\delta_{c_{i}}$, then the following holds true

$\displaystyle\frac{1}{2^{nC_{i}}}\sum_{\begin{subarray}{c}\mu_{i}\end{subarray}}\sum_{{x}_{i}^{n}}{p^{n}_{{X}_{i}}({x}_{i}^{n})}\mathbb{P}\Bigg{(}\bigg{[}\sum_{a_{i}\in\mathbb{F}_{p}^{k}}\sum_{m_{i}\in\mathbb{F}_{p}^{l_{i}}}E^{(\mu_{i})}_{L_{i}|X_{i}^{n}}(a_{i},m_{i}|x_{i}^{n})\bigg{]}>1\Bigg{)}\leq\epsilon_{c_{i}}$
(7)

###### Proof.

The proof is provided in Appendix A-A. ∎

######  Proposition 1.

There exist functions $\epsilon_{\widetilde{S}}(\delta),$ and
$\delta_{\widetilde{S}}(\delta)$, such that for all sufficiently small
$\delta$ and sufficiently large $n$, we have
$\mathbb{E}[\widetilde{S}]\leq\epsilon_{\widetilde{S}}(\delta)$, if
$S_{1}>I(X_{1};W_{1})-H(W_{1})+\log{p}+\delta_{\widetilde{S}}$ and
$S_{2}>I(X_{2};W_{2})-H(W_{2})+\log{p}+\delta_{\widetilde{S}},$ where
$\epsilon_{\widetilde{S}},\delta_{\widetilde{S}}\searrow 0$ as $\delta\searrow
0$.

###### Proof.

The proof is provided in Appendix B-A ∎

Now we move on to removing from $S$ the error that is induced due to binning.

Step 2: Error caused by binning
Note that $S$ can be simplified using the definitions of
$P_{M_{1}|X_{1}^{n}}^{(\mu_{1})}(\cdot|\cdot)$,
$P_{M_{2}|X_{2}^{n}}^{(\mu_{2})}(\cdot|\cdot)$, and
$p^{(\mu)}_{Y^{n}|\underline{M}}(y^{n}|\underline{m})$ as

$\displaystyle
S\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}$
$\displaystyle\sum_{\underline{x}^{n},y^{n}}\Bigg{|}p^{n}_{\underline{X}Y}(\underline{x}^{n},y^{n})-\sum_{\begin{subarray}{c}\mu_{1},\mu_{2}\end{subarray}}\sum_{\begin{subarray}{c}m_{1}>0,\\\
m_{2}>0\end{subarray}}\sum_{\begin{subarray}{c}a_{1}\in\mathbb{F}_{p}^{k}\\\
a_{2}\in\mathbb{F}_{p}^{k}\end{subarray}}\sum_{\begin{subarray}{c}w_{1},w_{2}\in\mathbb{F}_{p}^{n}\end{subarray}}\frac{p^{n}_{\underline{X}}(\underline{x}^{n})}{2^{n(C_{1}+C_{2})}}E^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})E^{(\mu_{2})}_{W^{n}_{2}|X_{2}^{n}}\\!(w^{n}_{2}|x_{2}^{n})$
$\displaystyle\hskip
150.0pt\mathbbm{1}_{\left\\{\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})=w_{1}^{n}\right\\}}\mathbbm{1}_{\left\\{\mathtt{w}_{2}(a_{2},m_{2},\mu_{2})=w_{1}^{n}\right\\}}p_{Y|Z}^{n}(y^{n}|f^{(\mu)}(m_{1},m_{2}))\Bigg{|},$

where $E^{(\mu_{i})}_{W_{i}^{n}|X_{i}^{n}}(w_{i}^{n}|x_{i}^{n})$ is defined as

$\displaystyle E^{(\mu_{i})}_{W_{i}^{n}|X_{i}^{n}}(w_{i}^{n}|x_{i}^{n})$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\frac{p^{n}}{2^{nS_{i}}(1+\eta)}{p_{W_{i}|X_{i}}^{n}(w_{i}^{n}|x_{i}^{n})}\mathbbm{1}_{\left\\{w_{i}^{n}\in
T_{\delta}(W_{i}|x_{i}^{n})\right\\}}\mathbbm{1}_{\\{s_{i}^{(\mu_{i})}(x_{i}^{n})\leq
1\\}},\quad\text{ for i $\in\\{1,2\\}$ }.$

Further by defining $\gamma_{w_{1}^{n}}^{(\mu_{1})}$ and
$\zeta_{w_{2}^{n}}^{(\mu_{2})}$ as

$\displaystyle\gamma_{w_{1}^{n}}^{(\mu_{1})}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}|\\{\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})=w_{1}^{n}\\}|=\sum_{m_{1}>0}\sum_{a_{1}\in\mathbb{F}_{q}^{k}}\mathbbm{1}_{\\{\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})=w_{1}^{n}\\}}\quad\text{
and }$ $\displaystyle\zeta_{w_{2}^{n}}^{(\mu_{2})}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}|\\{\mathtt{w}_{2}(a_{2},m_{2},\mu_{2})=w_{2}^{n}\\}|=\sum_{m_{2}>0}\sum_{a_{2}\in\mathbb{F}_{q}^{k}}\mathbbm{1}_{\\{\mathtt{w}_{2}(a_{2},m_{2},\mu_{2})=w_{2}^{n}\\}}.$
(8)

we bound $S$ using triangle inequality as $S\leq S_{1}+S_{2}$, where

$\displaystyle S_{1}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\underline{x}^{n},y^{n}}\Bigg{|}p^{n}_{\underline{X}Y}(\underline{x}^{n},y^{n})-\sum_{\begin{subarray}{c}\mu_{1},\mu_{2}\end{subarray}}\sum_{\begin{subarray}{c}w_{1}^{n},w_{2}^{n}\in\mathbb{F}_{p}^{n}\end{subarray}}\frac{p^{n}_{\underline{X}}(\underline{x}^{n})}{2^{n(C_{1}+C_{2})}}\gamma_{w_{1}^{n}}^{(\mu_{1})}\zeta_{w_{2}^{n}}^{(\mu_{2})}$
$\displaystyle\hskip
170.0ptE^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})E^{(\mu_{2})}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})p^{n}_{Y|Z}(y^{n}|w_{1}^{n}\oplus
w_{2}^{n})\Bigg{|},$ $\displaystyle S_{2}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\underline{x}^{n},y^{n}}\sum_{\begin{subarray}{c}\mu_{1},\mu_{2}\end{subarray}}\sum_{\begin{subarray}{c}m_{1}>0,\\\
m_{2}>0\end{subarray}}\sum_{\begin{subarray}{c}a_{1}\in\mathbb{F}_{p}^{k}\\\
a_{2}\in\mathbb{F}_{p}^{k}\end{subarray}}\sum_{\begin{subarray}{c}w_{1}^{n},w_{2}^{n}\in\mathbb{F}_{p}^{n}\end{subarray}}\\!\frac{p^{n}_{\underline{X}}(\underline{x}^{n})}{2^{n(C_{1}+C_{2})}}E^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})E^{(\mu_{2})}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})$
$\displaystyle\hskip
80.0pt\mathbbm{1}_{\left\\{\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})=w_{1}^{n}\right\\}}\mathbbm{1}_{\left\\{\mathtt{w}_{2}(a_{2},m_{2},\mu_{2})=w_{1}^{n}\right\\}}\Bigg{|}p^{n}_{Y|Z}(y^{n}|w_{1}^{n}\oplus
w_{2}^{n})\\!-\\!p^{n}_{Y|Z}(y^{n}|f^{(\mu)}(m_{1},\\!m_{2}))\Bigg{|}.$

To bound the term corresponding to $S_{2}$, we provide the following
proposition.

######  Proposition 2 (Mutual Packing).

There exist $\epsilon_{S_{2}}(\delta),$ such that for all sufficiently small
$\delta$ and sufficiently large $n$, we have
$\mathbb{E}\left[{S}_{2}\right]\leq\epsilon_{{S_{2}}}(\delta)$, if
$S_{1}-R_{1}<\log{p}-H(Z)$, or equivalently, $S_{2}-R_{2}<\log{p}-H(Z)$, where
$\epsilon_{{S}_{2}}\searrow 0$ as $\delta\searrow 0$.

###### Proof.

The proof is provided in Appendix B-B. ∎

Now, we move on to analyzing the term corresponding to $S_{1}$.
Step 3: Term concerning Alice’s encoding
In this step, we separately analyze the action of the two encoders in
approximating the product distribution $p_{\underline{X}Y}^{n}(\cdot)$. For
that, we split $S_{1}$ as $S_{1}\leq Q_{1}+Q_{2}$, where

$\displaystyle
Q_{1}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}$
$\displaystyle\sum_{\underline{x}^{n},y^{n}}\Bigg{|}p^{n}_{\underline{X}Y}(\underline{x}^{n},y^{n})-\frac{1}{2^{nC_{1}}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\sum_{\begin{subarray}{c}w_{1}^{n},w_{2}^{n}\in\mathbb{F}_{p}^{n}\end{subarray}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\gamma_{w_{1}^{n}}^{(\mu_{1})}E^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})$
$\displaystyle\hskip
216.81ptp^{n}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})p^{n}_{Y|{Z}}(y^{n}|w_{1}^{n}+w_{2}^{n})\Bigg{|},$
$\displaystyle
Q_{2}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}$
$\displaystyle\\!\\!\sum_{\underline{x}^{n},y^{n}}\Bigg{|}\frac{1}{2^{nC_{1}}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\sum_{\begin{subarray}{c}w_{1}^{n},w_{2}^{n}\in\mathbb{F}_{p}^{n}\end{subarray}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\gamma_{w_{1}^{n}}^{(\mu_{1})}E^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})$
$\displaystyle\hskip
80.0pt\left(p^{n}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})\\!-\zeta_{w_{2}^{n}}^{(\mu_{2})}E^{(\mu_{2})}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})\right)p^{n}_{Y|{Z}}(y^{n}|w_{1}^{n}\\!\\!+\\!\\!w_{2}^{n})\Bigg{|}.$

With this partition, the terms within the trace norm of $Q_{1}$ differ only in
the action of Alice’s encoder. And similarly, the terms within the norm of
$Q_{2}$ differ only in the action of Bob’s encoder. Showing that these two
terms are small forms a major portion of the achievability proof.
Analysis of $Q_{1}$: To prove $Q_{1}$ is small, we characterize the rate
constraints which ensure that an upper bound to $Q_{1}$ can be made to vanish
in an expected sense. In addition, this upper bound becomes useful in
obtaining a single-letter characterization for the rate needed to make the
term corresponding to $Q_{2}$ vanish. For this, we define $J$ as

$\displaystyle
J\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}$
$\displaystyle\sum_{\underline{x}^{n},w_{2}^{n},y^{n}}\Bigg{|}p^{n}_{\underline{X}W_{2}Y}(\underline{x}^{n},y^{n})-\frac{1}{2^{nC_{1}}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\sum_{\begin{subarray}{c}w_{1}^{n}\end{subarray}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\gamma_{w_{1}^{n}}^{(\mu_{1})}E^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})$
$\displaystyle\hskip
216.81ptp^{n}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})p^{n}_{Y|{Z}}(y^{n}|w_{1}^{n}+w_{2}^{n})\Bigg{|}.$

By again using triangle inequality we obtain $J\leq J_{1}+J_{2}$, where

$\displaystyle J_{1}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\underline{x}^{n},w_{2}^{n},y^{n}}\Bigg{|}p^{n}_{\underline{X}W_{2}Y}(\underline{x}^{n},y^{n})-\frac{1}{2^{nC_{1}}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\sum_{\begin{subarray}{c}w_{1}^{n}\end{subarray}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\gamma_{w_{1}^{n}}^{(\mu_{1})}\bar{E}^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})$
$\displaystyle\hskip
216.81ptp^{n}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})p^{n}_{Y|{Z}}(y^{n}|w_{1}^{n}+w_{2}^{n})\Bigg{|}$
$\displaystyle J_{2}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\underline{x}^{n},w_{2}^{n},y^{n}}\Bigg{|}\frac{1}{2^{nC_{1}}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\sum_{\begin{subarray}{c}w_{1}^{n}\end{subarray}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\gamma_{w_{1}^{n}}^{(\mu_{1})}\left(\bar{E}^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})-E^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})\right)$
$\displaystyle\hskip
216.81ptp^{n}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})p^{n}_{Y|{Z}}(y^{n}|w_{1}^{n}+w_{2}^{n})\Bigg{|}$

where $\bar{E}^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(\cdot|\cdot)$ is defined as

$\displaystyle E^{(\mu_{1})}_{W_{1}^{n}|X_{1}^{n}}(w_{1}^{n}|x_{1}^{n})$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\frac{p^{n}}{2^{nS_{1}}(1+\eta)}{p_{W_{1}|X_{1}}^{n}(w_{1}^{n}|x_{1}^{n})}\mathbbm{1}_{\left\\{w_{1}^{n}\in
T_{\delta}(W_{1}|x_{1}^{n})\right\\}}.$ (9)

To prove the term corresponding to $J_{1}$ is small, consider the following
proposition.

######  Proposition 3.

There exist $\epsilon_{J_{1}}(\delta),\delta_{J_{1}}(\delta)$ such that for
all sufficiently small $\delta$ and sufficiently large $n$, we have
$\mathbb{E}\left[J_{1}\right]\leq\epsilon_{J_{1}}$ if $S_{1}+C_{1}\geq
I(W_{1};X_{1}X_{2}ZW_{2})+\log{p}-H(W_{1})+\delta_{J_{1}}$, where
$\epsilon_{{J_{1}}},\delta_{{J_{1}}}\searrow 0$ as $\delta\searrow 0$.

###### Proof.

The proof is provided in Appendix B-C. ∎

Now, consider the term corresponding to $J_{2}$. This can be simplified as

$\displaystyle J_{2}$
$\displaystyle=\frac{1}{2^{nC_{1}}}\sum_{{x}_{1}^{n}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\left(\sum_{\begin{subarray}{c}w_{1}^{n}\end{subarray}}\gamma_{w_{1}^{n}}^{(\mu_{1})}\bar{E}^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})\right)\mathbbm{1}_{\\{s_{1}^{(\mu_{1})}(x^{n}_{1})>1\\}}$
$\displaystyle\leq\frac{1}{2^{nC_{1}}}\sum_{{x}_{1}^{n}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\mathbb{E}\left[\sum_{\begin{subarray}{c}w_{1}^{n}\end{subarray}}\gamma_{w_{1}^{n}}^{(\mu_{1})}\bar{E}^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})\right]\mathbbm{1}_{\\{s_{1}^{(\mu_{1})}(x^{n}_{1})>1\\}}$
$\displaystyle\hskip
10.0pt+\frac{1}{2^{nC_{1}}}\sum_{{x}_{1}^{n}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\left|\sum_{\begin{subarray}{c}w_{1}^{n}\end{subarray}}\gamma_{w_{1}^{n}}^{(\mu_{1})}\bar{E}^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})-\mathbb{E}\left[\sum_{\begin{subarray}{c}w_{1}^{n}\end{subarray}}\gamma_{w_{1}^{n}}^{(\mu_{1})}\bar{E}^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})\right]\right|$
$\displaystyle\leq\frac{1}{2^{nC_{1}}}\sum_{{x}_{1}^{n}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\mathbb{E}\left[\sum_{\begin{subarray}{c}w_{1}^{n}\end{subarray}}\gamma_{w_{1}^{n}}^{(\mu_{1})}\bar{E}^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})\right]\mathbbm{1}_{\\{s_{1}^{(\mu_{1})}(x^{n}_{1})>1\\}}$
$\displaystyle\hskip
10.0pt+\frac{1}{2^{nC_{1}}}\sum_{{x}_{1}^{n}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\left|\sum_{\begin{subarray}{c}w_{1}^{n}\end{subarray}}\gamma_{w_{1}^{n}}^{(\mu_{1})}\bar{E}^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})-\mathbb{E}\left[\sum_{\begin{subarray}{c}w_{1}^{n}\end{subarray}}\gamma_{w_{1}^{n}}^{(\mu_{1})}\bar{E}^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})\right]\right|$
$\displaystyle\leq H_{0}+H_{1}+\epsilon^{\prime\prime},$

for

$\displaystyle H_{0}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\frac{1}{2^{nC_{1}}}\sum_{{x}_{1}^{n}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\mathbbm{1}_{\\{s_{1}^{(\mu_{1})}(x^{n}_{1})>1\\}}$
$\displaystyle H_{1}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\frac{1}{2^{nC_{1}}}\sum_{{x}_{1}^{n}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\left|{p^{n}_{\underline{X}}(\underline{x}^{n})}-\frac{p^{n}}{2^{nS_{1}}(1+\eta)}\sum_{\begin{subarray}{c}w_{1}^{n}\end{subarray}}\sum_{m_{1}>0}\sum_{a_{1}\in\mathbb{F}_{q}^{k}}{p_{X_{1}W_{1}}^{n}(x_{1}^{n},w_{1}^{n})}\mathbbm{1}_{\\{\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})=w_{1}^{n}\\}}\right|$

where we use
$\mathbb{E}\left[\sum_{\begin{subarray}{c}w_{1}^{n}\end{subarray}}\gamma_{w_{1}^{n}}^{(\mu_{1})}\bar{E}^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})\right]\leq
1$ in defining $H_{0}$ and $H_{1}$ is obtained by adding the sequences
$w_{1}^{n}\notin\mathcal{T}_{\delta}^{(n)}(W_{1})$ within the summation. Now,
we can provide an upper bound on $H_{0}$ and $H_{1}$ using the Lemmas 2 and 1,
respectively, as $\mathbb{E}[H_{0}+H_{1}]\leq\epsilon_{H}$ if $S_{1}\geq
I(X_{1};W_{1})+\delta_{H}$. Therefore, since $Q_{1}\leq J$, hence $Q_{1}$, can
be made arbitrarily small for sufficiently large n, if
$S_{1}+C_{1}>I(W_{1};X_{1}X_{2}YW_{2})-H(W_{1})+\log{p}+\delta_{J}$ . Now we
move on to bounding $Q_{2}$.
Step 4: Analysis of Bob’s encoding
Step 3 ensured that the random variables $X_{1}X_{2}YW_{2}$ are close to a
product PMF in total variation. In this step, we approximate the PMF of random
variables $X_{1}X_{2}Y$ using the Bob’s encoding rule and bound the theorem
corresponding to $Q_{2}$. We proceed with the following proposition.

######  Proposition 4.

There exist functions $\epsilon_{Q_{2}}(\delta)$ and
$\delta_{{Q}_{2}}(\delta)$, such that for all sufficiently small $\delta$ and
sufficiently large $n$, we have $\mathbb{E}[{Q}_{2}]\leq\epsilon_{{Q_{2}}}$,
if $S_{1}+C_{1}\geq I(W_{1};X_{1}X_{2}YW_{2})-H(W_{1})+\log{p}+\delta_{Q_{2}}$
and $S_{2}+C_{2}\geq I(W_{2};X_{1}X_{2}Y)-H(W_{2})+\log{p}+\delta_{Q_{2}}$,
where $\epsilon_{Q_{2}},\delta_{{Q}_{2}}\searrow 0$ as $\delta\searrow 0$.

###### Proof.

The proof is provided in Appendix B-D. ∎

Hence, in bounding the terms corresponding to $Q_{1}$ and $Q_{2}$, we have
obtained the following constraints:

$\displaystyle S_{1}+C_{1}$ $\displaystyle\geq
I(W_{1};X_{1}X_{2}YW_{2})-H(W_{1})+\log{p},$ $\displaystyle S_{2}+C_{2}$
$\displaystyle\geq I(W_{2};X_{1}X_{2}Y)-H(W_{2})+\log{p}.$ (10)

By doing an exact symmetric analysis, but by replacing the first encoder by a
product distribution instead of the second encoder in $S_{1}$, we obtain the
following constraints

$\displaystyle S_{1}+C_{1}$ $\displaystyle\geq
I(W_{1};X_{1}X_{2}Y)-H(W_{1})+\log{p},$ $\displaystyle S_{2}+C_{2}$
$\displaystyle\geq I(W_{2};X_{1}X_{2}YW_{1})-H(W_{2})+\log{p}.$ (11)

By time sharing between the above rates (10) and (11), one can obtain the
following rate constraints

$\displaystyle S_{1}\\!+\\!C_{1}$
$\displaystyle\\!\geq\\!I(W_{1};X_{1}X_{2}Y)-H(W_{1})+\log{p},$ $\displaystyle
S_{2}\\!+\\!C_{2}$
$\displaystyle\\!\geq\\!I(W_{2};X_{1}X_{2}Y)-H(W_{2})+\log{p},$ $\displaystyle
S_{1}\\!+\\!S_{2}\\!+\\!C_{1}\\!+\\!C_{2}$
$\displaystyle\\!\geq\\!I(W_{1}W_{2};X_{1}X_{2}Y)\\!-\\!H(W_{1},W_{2})\\!+\\!2\log{p}.$

###  IV-D Rate Constraints

To sum-up, we showed that the (3) holds for sufficiently large $n$ and with
probability sufficiently close to 1, if the following bounds holds while
incorporating the time sharing random variable $Q$ taking values over the
finite set $\mathcal{Q}$111Since $Q$, the time sharing random variable is
employed in the standard way we omit its discussion here.:

$\displaystyle S_{1}$ $\displaystyle\geq I(X_{1};W_{1}|Q)-H(W_{1}|Q)+\log{p},$
$\displaystyle S_{2}$ $\displaystyle\geq I(X_{2};W_{2}|Q)-H(W_{2}|Q)+\log{p},$
$\displaystyle S_{1}+C_{1}$ $\displaystyle\geq
I(X_{1}X_{2}Y;W_{1}|Q)-H(W_{1}|Q)+\log{p},$ $\displaystyle S_{2}+C_{2}$
$\displaystyle\geq I(X_{1}X_{2}Y;W_{2}|Q)-H(W_{2}|Q)\\!+\\!\log{p},$
$\displaystyle S_{1}+S_{2}+C_{1}+C_{2}$ $\displaystyle\geq
I(W_{1}W_{2};X_{1}X_{2}Y|Q)-H(W_{1},\\!W_{2}|Q)+2\log{p},$ $\displaystyle
S_{1}-R_{1}$ $\displaystyle=S_{2}-R_{2}\leq\log{p}-H(W_{1}\oplus W_{2}|Q),$
$\displaystyle 0\leq R_{1}$ $\displaystyle\leq S_{1},\quad 0\leq R_{2}\leq
S_{2},$ $\displaystyle C_{1}+C_{2}$ $\displaystyle\leq C,\quad C\geq 0$ (12)

Lastly, we complete the proof of the theorem using the following lemma.

######  Lemma 3.

Let $\mathcal{R}_{1}$ denote the set of all $(R_{1},R_{2},C)$ for which there
exists $(S_{1},S_{2})$ such that the septuple
$(R_{1},R_{2},C,S_{1},S_{2},{C}_{1},{C}_{2})$ satisfies the inequalities in
(IV-D). Let, $\mathcal{R}_{2}$ denote the set of all triples $(R_{1},R_{2},C)$
that satisfies the inequalities in (1) given in the statement of the theorem.
Then, $\mathcal{R}_{1}=\mathcal{R}_{2}$.

###### Proof.

This follows from Fourier-Motzkin elimination [21]. ∎

##  Appendix A Proof of Lemmas

###  A-A Proof of Lemma 2

Let $K$ denote the left hand side of (7). Further, for the purpose of this
proof, we skip the subscript $i$ Bounding the a-typical sequences of $x^{n}$
from the summation gives $K=K_{1}+\epsilon_{X},$ where

$\displaystyle
K_{1}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\frac{1}{2^{nC}}\sum_{\begin{subarray}{c}\mu\end{subarray}}\sum_{{x}^{n}\in\mathcal{T}_{\delta}^{(n)}(X)}{p^{n}_{{X}}({x}^{n})}\mathbb{P}\Bigg{(}\bigg{[}\sum_{a\in\mathbb{F}_{p}^{k}}\sum_{m\in\mathbb{F}_{p}^{l}}E^{(\mu)}_{L|X^{n}}(a,m|x^{n})\bigg{]}>1\Bigg{)},$

and
$\epsilon_{X}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{x^{n}\notin\mathcal{T}_{\delta}^{(n)}(X)}{p^{n}_{{X}}({x}^{n})}$.
Note that $\epsilon_{X}(\delta)\searrow 0$ as $\delta\searrow 0.$ With that,
it remains to show the $K_{1}$ can be made arbitrarily small in expected
sense. Toward that, define

$\displaystyle Z^{(\mu)}_{x^{n}}(a,m)$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\frac{p^{n}}{(1+\eta)}\\!\sum_{w^{n}}p_{XW}^{n}(x^{n}\\!\\!,w^{n})\mathbbm{1}_{\\{\mathtt{w}^{n}(a,m,\mu)=w^{n}\\}}\mathbbm{1}_{\\{w^{n}\in\mathcal{T}_{\delta}^{(n)}(W|x^{n})\\}},\quad\\!\\!\\!Z^{(\mu)}_{x^{n}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\frac{1}{2^{nS}}\\!\\!\sum_{m>0}\sum_{a\in\mathbb{F}_{q}^{k}}\\!\\!Z^{(\mu)}_{x^{n}}(a,m)$

Observe the following upper and lower bounds on
$\mathbb{E}[Z^{(\mu)}_{x^{n}}]$.

$\displaystyle\mathbb{E}[Z^{(\mu)}_{x^{n}}]$
$\displaystyle=\frac{p^{n}}{(1+\eta)}\sum_{w^{n}\in\mathcal{T}_{\delta}^{(n)}(W|x^{n})}p_{XW}^{n}(x^{n},w^{n})\frac{1}{p^{n}}\leq\frac{p_{X}^{n}(x^{n})}{(1+\eta)}$
(13) $\displaystyle\mathbb{E}[Z^{(\mu)}_{x^{n}}]$
$\displaystyle=\frac{1}{(1+\eta)}\sum_{w^{n}\in\mathcal{T}_{\delta}^{(n)}(W|x^{n})}p_{XW}^{n}(x^{n},w^{n})\geq\frac{p_{X}^{n}(x^{n})2^{n\delta_{w}}}{(1+\eta)},$
(14)

where the inequalities above uses the typicality arguments and
$\delta_{w}(\delta)\searrow 0$ as $\delta\searrow 0.$ Using these bounds, we
perform the following simplification.

$\displaystyle\mathbb{P}\Bigg{(}\bigg{[}\sum_{a\in\mathbb{F}_{p}^{k}}\sum_{m\in\mathbb{F}_{p}^{l}}E^{(\mu)}_{L|X^{n}}(a,m|x^{n})\bigg{]}>1\Bigg{)}$
$\displaystyle=\mathbb{P}\Bigg{(}Z^{(\mu)}_{x^{n}}>p_{X}^{n}(x^{n})\Bigg{)}\leq\mathbb{P}\Bigg{(}Z^{(\mu)}_{x^{n}}>(1+\eta)\mathbb{E}[Z^{(\mu)}_{x^{n}}]\Bigg{)}$
(15)

where the inequality above uses the inequality from (13). Further, we have

$\displaystyle\mathbb{P}\Bigg{(}\bigg{|}Z^{(\mu)}_{x^{n}}-\mathbb{E}[Z^{(\mu)}_{x^{n}}]\bigg{|}>\eta\mathbb{E}[Z^{(\mu)}_{x^{n}}]\Bigg{)}\leq\frac{\mathbb{E}\bigg{|}Z^{(\mu)}_{x^{n}}-\mathbb{E}[Z^{(\mu)}_{x^{n}}]\bigg{|}}{\eta\mathbb{E}[Z^{(\mu)}_{x^{n}}]}\leq\frac{(1+\eta)\sqrt{Var\left(Z^{(\mu)}_{x^{n}}\right)}}{\eta
2^{-n\delta_{w}}p^{n}_{X}(x^{n})}$ (16)

where the first inequality follows from Markov Inequality, and the second uses
(i) the Jensen’s inequality for square-root function and (ii) the bound from
(14). Combining the inequalities (15) and (16) using union bound, we obtain

$\displaystyle\mathbb{P}\Bigg{(}\bigg{[}\sum_{a\in\mathbb{F}_{p}^{k}}\sum_{m\in\mathbb{F}_{p}^{l}}E^{(\mu)}_{L|X^{n}}(a,m|x^{n})\bigg{]}>1\Bigg{)}\leq\frac{\sqrt{Var\left(Z^{(\mu)}_{x^{n}}\right)}}{\eta
2^{-n\delta_{w}}p^{n}_{X}(x^{n})}\leq\frac{(1+\eta)\sqrt{2^{-n(S+H(X|W)+H(W)-\delta^{\prime\prime})}}}{\eta
2^{-n\delta_{w}}p^{n}_{X}(x^{n})}$ (17)

where the last inequality follows by simplifying
$Var\left(Z^{(\mu)}_{x^{n}}\right)$ similar to the one in [20, Lemma 19] to
obtain

$\displaystyle Var\left(Z^{(\mu)}_{x^{n}}\right)\leq
2^{-n(S+H(X|W)+H(W)-\delta^{\prime\prime})}\frac{1}{(1+\eta)^{2}}.$

Substituting the simplification of (17) in $K_{1}$ completes the proof.

##  Appendix B Proof of Propositions

###  B-A Proof of Proposition 1

We bound $\tilde{S}$ as
$\tilde{S}\leq\tilde{S}_{1}+\tilde{S}_{2}+\tilde{S}_{3},$ where

$\displaystyle\tilde{S}_{1}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\underline{x}^{n},y^{n}}\sum_{\begin{subarray}{c}\mu_{1},\mu_{2}\end{subarray}}\sum_{\begin{subarray}{c}m_{2}>0\end{subarray}}\frac{p^{n}_{\underline{X}}(\underline{x}^{n})}{2^{n(C_{1}+C_{2})}}p^{(\mu_{1})}_{M_{1}|X_{1}^{n}}(0|x_{1}^{n})p^{(\mu_{2})}_{M_{2}|X_{2}^{n}}(m_{2}|x_{2}^{n})p^{(\mu)}_{Y^{n}|M_{1}M_{2}}(y^{n}|0,m_{2})$
$\displaystyle\tilde{S}_{2}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\underline{x}^{n},y^{n}}\sum_{\begin{subarray}{c}\mu_{1},\mu_{2}\end{subarray}}\sum_{\begin{subarray}{c}m_{2}>0\end{subarray}}\frac{p^{n}_{\underline{X}}(\underline{x}^{n})}{2^{n(C_{1}+C_{2})}}p^{(\mu_{1})}_{M_{1}|X_{1}^{n}}(m_{1}|x_{1}^{n})p^{(\mu_{2})}_{M_{2}|X_{2}^{n}}(0|x_{2}^{n})p^{(\mu)}_{Y^{n}|M_{1}M_{2}}(y^{n}|m_{1},0)$
$\displaystyle\tilde{S}_{3}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\underline{x}^{n},y^{n}}\sum_{\begin{subarray}{c}\mu_{1},\mu_{2}\end{subarray}}\sum_{\begin{subarray}{c}m_{2}>0\end{subarray}}\frac{p^{n}_{\underline{X}}(\underline{x}^{n})}{2^{n(C_{1}+C_{2})}}p^{(\mu_{1})}_{M_{1}|X_{1}^{n}}(0|x_{1}^{n})p^{(\mu_{2})}_{M_{2}|X_{2}^{n}}(0|x_{2}^{n})p^{(\mu)}_{Y^{n}|M_{1}M_{2}}(y^{n}|0,0)$

Analysis of $\tilde{S}_{1}$:  Consider the following simplification with
regards to $\tilde{S}_{1}.$

$\displaystyle\tilde{S}_{1}$
$\displaystyle=\sum_{\underline{x}^{n}}\sum_{\begin{subarray}{c}\mu_{1},\mu_{2}\end{subarray}}\frac{p^{n}_{\underline{X}}(\underline{x}^{n})p^{(\mu_{1})}_{M_{1}|X_{1}^{n}}(0|x_{1}^{n})}{2^{n(C_{1}+C_{2})}}\left(\sum_{\begin{subarray}{c}m_{2}>0\end{subarray}}p^{(\mu_{2})}_{M_{2}|X_{2}^{n}}(m_{2}|x_{2}^{n})\left(\sum_{y^{n}}p^{(\mu)}_{Y^{n}|M_{1}M_{2}}(y^{n}|0,m_{2})\right)\right)$
$\displaystyle=\sum_{{x}^{n}_{1}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\frac{p^{n}_{{X}_{1}}({x}_{1}^{n})p^{(\mu_{1})}_{M_{1}|X_{1}^{n}}(0|x_{1}^{n})}{2^{nC_{1}}}$
$\displaystyle\leq\sum_{{x}_{1}^{n}\in\mathcal{T}_{\delta}^{(n)}(X_{1})}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\frac{p^{n}_{{X}_{1}}({x}_{1}^{n})p^{(\mu_{1})}_{M_{1}|X_{1}^{n}}(0|x_{1}^{n})}{2^{nC_{1}}}\left(\mathbbm{1}_{\\{s_{1}^{(\mu_{1})}(x^{n}_{1})\leq
1\\}}+\mathbbm{1}_{\\{s_{1}^{(\mu_{1})}(x^{n}_{1})>1\\}}\right)+\epsilon_{X_{1}}$
$\displaystyle=\tilde{S}_{11}+\tilde{S}_{12}+\epsilon_{X_{1}}$

where we define
$\epsilon_{X_{1}}(\delta)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}1-\sum_{x^{n}\in\mathcal{T}_{\delta}^{(n)}(X_{1})}p^{n}_{{X}_{1}}({x}_{1}^{n})$
and

$\displaystyle\tilde{S}_{11}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{{x}_{1}^{n}\in\mathcal{T}_{\delta}^{(n)}(X_{1})}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\frac{p^{n}_{{X}_{1}}({x}_{1}^{n})}{2^{nC_{1}}}(1-s_{1}^{(\mu_{1})}(x^{n}_{1}))\mathbbm{1}_{\\{s_{1}^{(\mu_{1})}(x^{n}_{1})\leq
1\\}},$ $\displaystyle\tilde{S}_{12}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{{x}_{1}^{n}\in\mathcal{T}_{\delta}^{(n)}(X_{1})}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\frac{p^{n}_{{X}_{1}}({x}_{1}^{n})}{2^{nC_{1}}}\mathbbm{1}_{\\{s_{1}^{(\mu_{1})}(x^{n}_{1})>1\\}}.$

Now, we bound each of the above terms. For the term corresponding to
$\tilde{S}_{11}$, consider the following.

$\displaystyle\tilde{S}_{11}$
$\displaystyle\stackrel{{\scriptstyle\textnormal{(a)}}}{{\mathstrut{\leq}}}\sum_{{x}_{1}^{n}\in\mathcal{T}_{\delta}^{(n)}(X_{1})}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\frac{p^{n}_{{X}_{1}}({x}_{1}^{n})}{2^{nC_{1}}}\left|1-\sum_{a_{1}\in\mathbb{F}_{p}^{k}}\sum_{m_{1}\in\mathbb{F}_{p}^{l_{1}}}E^{(\mu_{1})}_{L_{1}|X_{1}^{n}}(a_{1},m_{1}|x_{1}^{n})\right|$
$\displaystyle\stackrel{{\scriptstyle\textnormal{(b)}}}{{\mathstrut{=}}}\sum_{{x}_{1}^{n}\in\mathcal{T}_{\delta}^{(n)}(X_{1})}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\frac{1}{2^{nC_{1}}}\left|p^{n}_{{X}_{1}}({x}_{1}^{n})-\frac{p^{n}}{2^{nS_{1}}}\sum_{a_{1}\in\mathbb{F}_{p}^{k}}\sum_{m_{1}\in\mathbb{F}_{p}^{l_{1}}}\sum_{\begin{subarray}{c}w_{1}^{n}\in
T_{\delta}(W_{1}|x_{1}^{n})\end{subarray}}\frac{p^{n}_{W_{1}X_{1}}\\!\\!(w_{1}^{n},x_{1}^{n})}{(1+\eta)}\\!\mathbbm{1}_{\\{\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})=w_{1}^{n}\\}}\right|$
$\displaystyle\stackrel{{\scriptstyle\textnormal{(c)}}}{{\mathstrut{\leq}}}\sum_{{x}_{1}^{n}\in\mathcal{T}_{\delta}^{(n)}(X_{1})}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\frac{1}{2^{nC_{1}}}\left|p^{n}_{{X}_{1}}({x}_{1}^{n})-\frac{p^{n}}{2^{nS_{1}}}\sum_{a_{1}\in\mathbb{F}_{p}^{k}}\sum_{m_{1}\in\mathbb{F}_{p}^{l_{1}}}\sum_{\begin{subarray}{c}w_{1}^{n}\end{subarray}}\frac{p^{n}_{W_{1}X_{1}}\\!\\!(w_{1}^{n},x_{1}^{n})}{(1+\eta)}\\!\mathbbm{1}_{\\{\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})=w_{1}^{n}\\}}\right|$
$\displaystyle\hskip
30.0pt+\sum_{{x}_{1}^{n}\in\mathcal{T}_{\delta}^{(n)}(X_{1})}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\frac{p^{n}}{2^{n(S_{1}+C_{1})}}\sum_{a_{1}\in\mathbb{F}_{p}^{k}}\sum_{m_{1}\in\mathbb{F}_{p}^{l_{1}}}\sum_{\begin{subarray}{c}w_{1}^{n}\notin
T_{\delta}(W_{1}|x_{1}^{n})\end{subarray}}\frac{p^{n}_{W_{1}X_{1}}\\!\\!(w_{1}^{n},x_{1}^{n})}{(1+\eta)}\\!\mathbbm{1}_{\\{\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})=w_{1}^{n}\\}}$
(18)

where (B-A) follows by bounding the indicator by $1$ and using the definition
of $s_{1}^{(\mu_{1})}(\cdot)$, (B-A) uses the definition of
$E^{(\mu_{1})}_{L_{1}|X_{1}^{n}}(a_{1},\\!m_{1}|x_{1}^{n})$ as defined in
Definition (4), the inequality (B-A) follows from triangle inequality.

Taking expectation on (18) over the first encoders codebook generation, we
obtain

$\displaystyle\mathbb{E}_{\mathbbm{C}_{1}}[\tilde{S}_{11}]$
$\displaystyle\leq\frac{1}{2^{nC_{1}}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\mathbb{E}_{\mathbbm{C}_{1}}\left[\sum_{{x}_{1}^{n}\in\mathcal{T}_{\delta}^{(n)}(X_{1})}\left|p^{n}_{{X}_{1}}({x}_{1}^{n})-\frac{p^{n}}{2^{nS_{1}}}\sum_{a_{1}\in\mathbb{F}_{p}^{k}}\sum_{m_{1}\in\mathbb{F}_{p}^{l_{1}}}\sum_{\begin{subarray}{c}w_{1}^{n}\end{subarray}}\frac{p^{n}_{W_{1}X_{1}}\\!\\!(w_{1}^{n},x_{1}^{n})}{(1+\eta)}\\!\mathbbm{1}_{\\{\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})=w_{1}^{n}\\}}\right|\right]$
$\displaystyle\hskip
30.0pt+\sum_{{x}_{1}^{n}\in\mathcal{T}_{\delta}^{(n)}(X_{1})}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\frac{p^{n}}{2^{n(S_{1}+C_{1})}}\sum_{a_{1}\in\mathbb{F}_{p}^{k}}\sum_{m_{1}\in\mathbb{F}_{p}^{l_{1}}}\sum_{\begin{subarray}{c}w_{1}^{n}\notin
T_{\delta}(W_{1}|x_{1}^{n})\end{subarray}}\frac{p^{n}_{W_{1}X_{1}}\\!\\!(w_{1}^{n},x_{1}^{n})}{(1+\eta)}\frac{1}{p^{n}}$
(19)

For the first term in (19), we use Lemma (1) and obtain
$\mathbb{E}[\tilde{S}_{11}]\leq\epsilon_{\tilde{S}_{11}}$ if $S_{1}\leq
I(X_{1};W_{1})-H(W_{1})+\log{p}+\delta_{\tilde{S}_{11}}$. As for the second
term we can use typicality arguments and bound it as

$\displaystyle\sum_{{x}_{1}^{n}\in\mathcal{T}_{\delta}^{(n)}(X_{1})}$
$\displaystyle\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\frac{p^{n}}{2^{n(S_{1}+C_{1})}}\sum_{a_{1}\in\mathbb{F}_{p}^{k}}\sum_{m_{1}\in\mathbb{F}_{p}^{l_{1}}}\sum_{\begin{subarray}{c}w_{1}^{n}\notin
T_{\delta}(W_{1}|x_{1}^{n})\end{subarray}}\frac{p^{n}_{W_{1}X_{1}}\\!\\!(w_{1}^{n},x_{1}^{n})}{(1+\eta)}\frac{1}{p^{n}}$
$\displaystyle\leq\sum_{{x}_{1}^{n}\in\mathcal{T}_{\delta}^{(n)}(X_{1})}\sum_{\begin{subarray}{c}w_{1}^{n}\notin
T_{\delta}(W_{1}|x_{1}^{n})\end{subarray}}\frac{p^{n}_{W_{1}X_{1}}\\!\\!(w_{1}^{n},x_{1}^{n})}{(1+\eta)}\leq{\epsilon^{\prime}}$
(20)

where
$\epsilon^{\prime}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{{x}_{1}^{n}\in\mathcal{T}_{\delta}^{(n)}(X_{1})}\sum_{\begin{subarray}{c}w_{1}^{n}\notin
T_{\delta}(W_{1}|x_{1}^{n})\end{subarray}}{p^{n}_{W_{1}X_{1}}\\!\\!(w_{1}^{n},x_{1}^{n})}$

Finally, we have the term corresponding to $\tilde{S}_{12}$. For this, we use
Lemma 2 and hence obtain
$\mathbb{E}[\tilde{S}_{12}]\leq\epsilon_{\tilde{S}_{12}}$ if $S_{2}\leq
I(X_{1};W_{1})-H(W_{1})+\log{p}+\delta_{\tilde{S}_{12}}$.

Analysis of $\tilde{S}_{2}$:  Due to the symmetry in $\tilde{S}_{1}$ and
$\tilde{S}_{2},$ the analysis of $\tilde{S}_{2}$ follows very similar
arguments at that of $\tilde{S}_{1}$ and therefore we obtain
$\mathbb{E}[\tilde{S}_{2}]\leq\epsilon_{\tilde{S}_{2}}$ if $S_{2}\geq
I(X_{2};W_{2})-H(W_{2})+\log{p}+\delta_{\tilde{S}_{2}}.$

Analysis of $\tilde{S}_{3}:$ Follows by merging the above analysis of
$\tilde{S}_{1}$ and $\tilde{S}_{2}.$

###  B-B Proof of Proposition 2

Recalling $S_{2}$, we have

$\displaystyle S_{2}$
$\displaystyle=\sum_{\underline{x}^{n}}\sum_{\begin{subarray}{c}\mu_{1},\mu_{2}\end{subarray}}\sum_{\begin{subarray}{c}m_{1}>0,\\\
m_{2}>0\end{subarray}}\sum_{\begin{subarray}{c}a_{1}\in\mathbb{F}_{p}^{k}\\\
a_{2}\in\mathbb{F}_{p}^{k}\end{subarray}}\sum_{\begin{subarray}{c}w_{1}^{n},w_{2}^{n}\in\mathbb{F}_{p}^{n}\end{subarray}}\\!\frac{p^{n}_{\underline{X}}(\underline{x}^{n})}{2^{n(C_{1}+C_{2})}}E^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})E^{(\mu_{2})}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})$
$\displaystyle\hskip
50.0pt\mathbbm{1}_{\left\\{\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})=w_{1}^{n}\right\\}}\mathbbm{1}_{\left\\{\mathtt{w}_{2}(a_{2},m_{2},\mu_{2})=w_{1}^{n}\right\\}}\sum_{y^{n}}\Bigg{|}p^{n}_{Y|Z}(y^{n}|w_{1}^{n}\oplus
w_{2}^{n})\\!-\\!p^{n}_{Y|Z}(y^{n}|f^{(\mu)}(m_{1},\\!m_{2}))\Bigg{|}$
$\displaystyle\leq
2\sum_{\underline{x}^{n}}\sum_{\begin{subarray}{c}\mu_{1},\mu_{2}\end{subarray}}\sum_{\begin{subarray}{c}m_{1}>0,\\\
m_{2}>0\end{subarray}}\sum_{\begin{subarray}{c}a_{1}\in\mathbb{F}_{p}^{k}\\\
a_{2}\in\mathbb{F}_{p}^{k}\end{subarray}}\sum_{\begin{subarray}{c}w_{1}^{n},w_{2}^{n}\in\mathbb{F}_{p}^{n}\end{subarray}}\\!\frac{p^{n}_{\underline{X}}(\underline{x}^{n})}{2^{n(C_{1}+C_{2})}}\frac{p^{n}p^{n}}{2^{n(S_{1}+S_{2})}(1+\eta)^{2}}{p_{W_{1}|X_{1}}^{n}(w_{1}^{n}|x_{1}^{n})}{p_{W_{2}|X_{2}}^{n}(w_{2}^{n}|x_{2}^{n})}$
$\displaystyle\hskip 55.0pt\mathbbm{1}_{\left\\{w_{i}^{n}\in
T_{\delta}(W_{i}|x_{i}^{n})\right\\}}\mathbbm{1}_{\left\\{w_{i}^{n}\in
T_{\delta}(W_{i}|x_{i}^{n})\right\\}}\mathbbm{1}_{\left\\{\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})=w_{1}^{n}\right\\}}\mathbbm{1}_{\left\\{\mathtt{w}_{2}(a_{2},m_{2},\mu_{2})=w_{1}^{n}\right\\}}\mathbbm{1}_{\\{w_{1}^{n}\oplus
w_{2}^{n},m_{1},m_{2}\\}}$

where we define $\mathbbm{1}_{\\{w_{1}^{n}\oplus w_{2}^{n},m_{1},m_{2}\\}}$ as

$\displaystyle\mathbbm{1}_{\\{w^{n},m_{1},m_{2}\\}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\mathbbm{1}\left\\{\exists(\tilde{w}^{n},\tilde{a}):\tilde{w}^{n}G+h_{1}^{(\mu_{1})}(m_{1})+h_{2}^{(\mu_{2})}(m_{2}),\tilde{w}^{n}\in\mathcal{T}_{\delta}^{(n)}(W_{1}\oplus
W_{2}),\tilde{w}^{n}\neq w^{n}\right\\}.$

Using this we obtain,

$\displaystyle\mathbb{E}[{S}_{2}]$ $\displaystyle\leq
2\sum_{\underline{x}^{n}}\sum_{\begin{subarray}{c}\mu_{1},\mu_{2}\end{subarray}}\sum_{\begin{subarray}{c}m_{1}>0,\\\
m_{2}>0\end{subarray}}\sum_{\begin{subarray}{c}a_{1}\in\mathbb{F}_{p}^{k}\\\
a_{2}\in\mathbb{F}_{p}^{k}\end{subarray}}\sum_{\begin{subarray}{c}w_{1}^{n},w_{2}^{n}\in\mathbb{F}_{p}^{n}\end{subarray}}\\!\frac{p^{n}_{\underline{X}}(\underline{x}^{n})}{2^{n(C_{1}+C_{2})}}\frac{p^{n}p^{n}}{2^{n(S_{1}+S_{2})}(1+\eta)^{2}}{p_{W_{1}|X_{1}}^{n}(w_{1}^{n}|x_{1}^{n})}{p_{W_{2}|X_{2}}^{n}(w_{2}^{n}|x_{2}^{n})}$
$\displaystyle\hskip 55.0pt\mathbbm{1}_{\left\\{w_{i}^{n}\in
T_{\delta}(W_{i}|x_{i}^{n})\right\\}}\mathbbm{1}_{\left\\{w_{i}^{n}\in
T_{\delta}(W_{i}|x_{i}^{n})\right\\}}\mathbbm{1}_{\left\\{\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})=w_{1}^{n}\right\\}}\mathbbm{1}_{\left\\{\mathtt{w}_{2}(a_{2},m_{2},\mu_{2})=w_{1}^{n}\right\\}}\mathbbm{1}_{\\{w_{1}^{n}\oplus
w_{2}^{n},m_{1},m_{2}\\}}$

Note that, we have

$\displaystyle\mathbb{E}$ $\displaystyle\left[\mathbbm{1}_{\\{w_{1}^{n}\oplus
w_{2}^{n},m_{1},m_{2}\\}}\mathbbm{1}_{\left\\{\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})=w_{1}^{n}\right\\}}\mathbbm{1}_{\left\\{\mathtt{w}_{2}(a_{2},m_{2},\mu_{2})=w_{1}^{n}\right\\}}\right]$
$\displaystyle\leq\sum_{\tilde{a}\neq
a}\sum_{\begin{subarray}{c}\tilde{w}^{n}\in\mathcal{T}_{\delta}^{(n)}(W_{1}\oplus
W_{2})\\\ \tilde{w}^{n}\neq w_{1}^{n}\oplus
w^{n}_{2}\end{subarray}}\frac{1}{p^{n}}\frac{1}{p^{n}}\frac{1}{p^{n}}\leq
2^{n(H(W_{1}\oplus W_{2})+\delta_{z})}p^{3n-k},$ (21)

where $\delta_{z}(\delta)\searrow 0$ as $\delta\searrow 0.$ This gives

$\displaystyle\mathbb{E}[{S}_{2}]$ $\displaystyle\leq
2\sum_{\underline{x}^{n}}\sum_{\begin{subarray}{c}m_{1}>0,\\\
m_{2}>0\end{subarray}}\sum_{\begin{subarray}{c}a_{1}\in\mathbb{F}_{p}^{k}\\\
a_{2}\in\mathbb{F}_{p}^{k}\end{subarray}}\sum_{\begin{subarray}{c}w_{1}^{n},w_{2}^{n}\in\mathbb{F}_{p}^{n}\end{subarray}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\frac{2^{n(H(W_{1}\oplus
W_{2})+\delta_{z})}p^{n-k}}{2^{n(S_{1}+S_{2})}(1+\eta)^{2}}{p_{W_{1}|X_{1}}^{n}(w_{1}^{n}|x_{1}^{n})}{p_{W_{2}|X_{2}}^{n}(w_{2}^{n}|x_{2}^{n})}$
$\displaystyle\leq 2^{n\left[(S_{1}-R_{1})-(\log{p}H(W_{1}\oplus
W_{2})-\delta_{S_{2}})\right]},$

where $\delta_{S_{2}}(\delta)\searrow 0$ as $\delta\searrow 0.$

###  B-C Proof of Proposition 3

Substituting the definition of
$\bar{E}^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(\cdot|\cdot)$ and
$\gamma_{w_{1}^{n}}^{(\mu_{1})}$ in $J_{1}$, we obtain

$\displaystyle J_{1}$
$\displaystyle=\sum_{\underline{x}^{n},w_{2}^{n},y^{n}}\Bigg{|}p^{n}_{\underline{X}W_{2}Y}(\underline{x}^{n},y^{n})-\frac{1}{2^{nC_{1}}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\sum_{\begin{subarray}{c}w_{1}^{n}\end{subarray}}\sum_{m_{1}>0}\sum_{a_{1}\in\mathbb{F}_{q}^{k}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\frac{p^{n}}{2^{nS_{1}}(1+\eta)}{p_{W_{1}|X_{1}}^{n}(w_{1}^{n}|x_{1}^{n})}$
$\displaystyle\hskip 108.405pt\mathbbm{1}_{\left\\{w_{1}^{n}\in
T_{\delta}(W_{1}|x_{1}^{n})\right\\}}\mathbbm{1}_{\\{\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})=w_{1}^{n}\\}}p^{n}_{W_{2}|X_{2}}(w^{n}_{2}|x_{2}^{n})p^{n}_{Y|{Z}}(y^{n}|w_{1}^{n}+w_{2}^{n})\Bigg{|}$
$\displaystyle=\sum_{\underline{x}^{n},w_{2}^{n},y^{n}}\Bigg{|}p^{n}_{\underline{X}W_{2}Y}(\underline{x}^{n},y^{n})$
$\displaystyle\hskip
36.135pt-\frac{1}{(1+\eta)}\frac{p^{n}}{2^{n(S_{1}+C_{1})}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\sum_{\begin{subarray}{c}w_{1}^{n}\in
T_{\delta}(W_{1}|x_{1}^{n})\end{subarray}}\sum_{m_{1}>0}\sum_{a_{1}\in\mathbb{F}_{q}^{k}}{p^{n}_{\underline{X}\underline{W}Y}(\underline{x}^{n},\underline{w}^{n},y^{n})}\mathbbm{1}_{\\{\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})=w_{1}^{n}\\}}\Bigg{|}$
$\displaystyle\leq J_{11}+J_{12},$

where

$\displaystyle J_{11}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\underline{x}^{n},w_{2}^{n},y^{n}}\Bigg{|}p^{n}_{\underline{X}W_{2}Y}(\underline{x}^{n},y^{n})-\frac{1}{(1+\eta)}\frac{p^{n}}{2^{n(S_{1}+C_{1})}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\sum_{\begin{subarray}{c}w_{1}^{n}\end{subarray}}\sum_{\begin{subarray}{c}m_{1}>0\\\
a_{1}\in\mathbb{F}_{q}^{k}\end{subarray}}{p^{n}_{\underline{X}\underline{W}Y}(\underline{x}^{n},\underline{w}^{n},y^{n})}\mathbbm{1}_{\\{\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})=w_{1}^{n}\\}}\Bigg{|}$
$\displaystyle J_{12}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\underline{x}^{n},w_{2}^{n},y^{n}}\Bigg{|}\frac{1}{(1+\eta)}\frac{p^{n}}{2^{n(S_{1}+C_{1})}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\sum_{\begin{subarray}{c}w_{1}^{n}\notin\mathcal{T}_{\delta}^{(n)}(W_{1})\end{subarray}}\sum_{m_{1}>0}\sum_{a_{1}\in\mathbb{F}_{q}^{k}}{p^{n}_{\underline{X}\underline{W}Y}(\underline{x}^{n},\underline{w}^{n},y^{n})}\mathbbm{1}_{\\{\mathtt{w}_{1}(a_{1},m_{1},\mu_{1})=w_{1}^{n}\\}}\Bigg{|}$

As for the term $J_{11}$, we use Lemma 1 and obtain the following bound on
$\mathbb{E}[J_{11}]$ as, $\mathbb{E}[J_{11}]\leq\epsilon_{J_{11}}$ if
$S_{1}+C_{1}\geq I(W_{1};X_{1}X_{2}ZW_{2})+\log{p}-H(W_{1})+\delta_{J_{11}}.$

For the term $J_{12},$ applying expectation gives

$\displaystyle\mathbb{E}[J_{12}]\leq\frac{1}{(1+\eta)}\sum_{\underline{x}^{n},w_{2}^{n},y^{n}}\sum_{w_{1}^{n}\notin\mathcal{T}_{\delta}^{(n)}(W_{1})}{p^{n}_{\underline{X}\underline{W}Y}(\underline{x}^{n},\underline{w}^{n},y^{n})}\leq\epsilon^{\prime}.$

where $\epsilon^{\prime}(\delta)\searrow 0$ as $\delta\searrow 0.$

###  B-D Proof of Proposition 4

We begin by applying triangle inequality on $Q_{2}$ to obtain $Q_{2}\leq
F_{1}+F_{2}$, where

$\displaystyle F_{1}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\underline{x}^{n},y^{n}}\Bigg{|}\frac{1}{2^{n(C_{1}+C_{2})}}\sum_{\begin{subarray}{c}\mu_{1},\mu_{2}\end{subarray}}\sum_{\begin{subarray}{c}w_{1}^{n},w_{2}^{n}\in\mathbb{F}_{p}^{n}\end{subarray}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\gamma_{w_{1}^{n}}^{(\mu_{1})}E^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})$
$\displaystyle\hskip
80.0pt\left(p^{n}_{W_{2}|X_{2}}(w^{n}_{2}|x_{2}^{n})\\!-\zeta_{w_{2}^{n}}^{(\mu_{2})}\bar{E}^{(\mu_{2})}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})\right)p^{n}_{Y|{Z}}(y^{n}|w_{1}^{n}\oplus
w_{2}^{n})\Bigg{|},$ $\displaystyle F_{2}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\underline{x}^{n},y^{n}}\Bigg{|}\frac{1}{2^{n(C_{1}+C_{2})}}\sum_{\begin{subarray}{c}\mu_{1},\mu_{2}\end{subarray}}\sum_{\begin{subarray}{c}w_{1}^{n},w_{2}^{n}\in\mathbb{F}_{p}^{n}\end{subarray}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\gamma_{w_{1}^{n}}^{(\mu_{1})}E^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})$
$\displaystyle\hskip
70.0pt\zeta_{w_{2}^{n}}^{(\mu_{2})}\left(\bar{E}^{(\mu_{2})}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})-{E}^{(\mu_{2})}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})\right)p^{n}_{Y|{Z}}(y^{n}|w_{1}^{n}\oplus
w_{2}^{n})\Bigg{|},$

where $\bar{E}^{(\mu_{2})}_{W^{n}_{2}|X_{2}^{n}}(\cdot|\cdot)$ is defined as

$\displaystyle\bar{E}^{(\mu_{2})}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\frac{p^{n}}{2^{nS_{2}}(1+\eta)}{p_{W_{2}|X_{2}}^{n}(w_{2}^{n}|x_{2}^{n})}\mathbbm{1}_{\left\\{w_{2}^{n}\in
T_{\delta}(W_{2}|x_{2}^{n})\right\\}}$

Considering the term corresponding to $F_{1}$, we bound it using triangle
inequality applied by adding and subtracting the following terms within its
modulus:

$\displaystyle(i)\;$
$\displaystyle\sum_{w_{1}^{n},w_{2}^{n}\in\mathbb{F}_{p}^{n}}{p^{n}_{\underline{X}}(\underline{x}^{n})}p^{n}_{W_{1}|X_{1}}(w^{n}_{1}|x_{1}^{n})p^{n}_{W_{2}|X_{2}}(w^{n}_{2}|x_{2}^{n})p^{n}_{Y|{Z}}(y^{n}|w_{1}^{n}\oplus
w_{2}^{n})$ $\displaystyle(ii)\;$
$\displaystyle\frac{1}{2^{nC_{2}}}\sum_{\mu_{2}}\sum_{w_{1}^{n},w_{2}^{n}\in\mathbb{F}_{p}^{n}}{p^{n}_{\underline{X}}(\underline{x}^{n})}p^{n}_{W_{1}|X_{1}}(w^{n}_{1}|x_{1}^{n})\frac{p^{n}\zeta_{w_{2}^{n}}^{(\mu_{2})}}{2^{nS_{2}}(1+\eta)}p^{n}_{W_{2}|X_{2}}(w^{n}_{2}|x_{2}^{n})p^{n}_{Y|{Z}}(y^{n}|w_{1}^{n}\oplus
w_{2}^{n})$ $\displaystyle(iii)\;$
$\displaystyle\frac{1}{2^{n(C_{1}+C_{2})}}\sum_{\mu_{1},\mu_{2}}\sum_{w_{1}^{n},w_{2}^{n}\in\mathbb{F}_{p}^{n}}\\!\\!\\!\\!\\!\\!{p^{n}_{\underline{X}}(\underline{x}^{n})}\gamma_{w_{1}^{n}}^{(\mu_{1})}E^{(\mu_{1})}_{W^{n}_{1}|X^{n}_{1}}(w^{n}_{1}|x_{1}^{n})\frac{p^{n}\zeta_{w_{2}^{n}}^{(\mu_{2})}}{2^{nS_{2}}(1+\eta)}\
p^{n}_{W_{2}|X_{2}}(w^{n}_{2}|x_{2}^{n})p^{n}_{Y|{Z}}(y^{n}|w_{1}^{n}\oplus
w_{2}^{n})$

This gives the following bound $F_{1}\leq F_{11}+F_{12}+F_{13}+F_{14},$ where

$\displaystyle F_{11}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\underline{x}^{n},y^{n}}\Bigg{|}\frac{1}{2^{nC_{1}}}\sum_{\begin{subarray}{c}\mu_{1}\end{subarray}}\sum_{\begin{subarray}{c}w_{1}^{n},w_{2}^{n}\in\mathbb{F}_{p}^{n}\end{subarray}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\left(\gamma_{w_{1}^{n}}^{(\mu_{1})}E^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})-p^{n}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})\right)p^{n}_{Y|{Z}}(y^{n}|w_{1}^{n}\oplus
w_{2}^{n})\Bigg{|}$ $\displaystyle F_{12}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\underline{x}^{n},y^{n}}\Bigg{|}\sum_{w_{1}^{n},w_{2}^{n}\in\mathbb{F}_{p}^{n}}{p^{n}_{\underline{X}}(\underline{x}^{n})}p^{n}_{W_{1}|X_{1}}(w^{n}_{1}|x_{1}^{n})\left(p^{n}_{W_{2}|X_{2}}(w^{n}_{2}|x_{2}^{n})\right.$
$\displaystyle\hskip
195.12877pt\left.-\frac{p^{n}\zeta_{w_{2}^{n}}^{(\mu_{2})}}{2^{nS_{2}}(1+\eta)}p^{n}_{W_{2}|X_{2}}(w^{n}_{2}|x_{2}^{n})\right)p^{n}_{Y|{Z}}(y^{n}|w_{1}^{n}\oplus
w_{2}^{n})\Bigg{|}$ $\displaystyle F_{13}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\underline{x}^{n},y^{n}}\Bigg{|}\frac{1}{2^{nC_{2}}}\sum_{\mu_{2}}\sum_{w_{1}^{n},w_{2}^{n}\in\mathbb{F}_{p}^{n}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\left(p^{n}_{W_{1}|X_{1}}(w^{n}_{1}|x_{1}^{n})\right.$
$\displaystyle\hskip
72.26999pt\left.-\frac{1}{2^{nC_{1}}}\sum_{\mu_{1}}\gamma_{w_{1}^{n}}^{(\mu_{1})}E^{(\mu_{1})}_{W^{n}_{1}|X^{n}_{1}}(w^{n}_{1}|x_{1}^{n})\right)\frac{p^{n}\zeta_{w_{2}^{n}}^{(\mu_{2})}}{2^{nS_{2}}(1+\eta)}p^{n}_{W_{2}|X_{2}}(w^{n}_{2}|x_{2}^{n})p^{n}_{Y|{Z}}(y^{n}|w_{1}^{n}\oplus
w_{2}^{n})\Bigg{|}$ $\displaystyle F_{14}$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{\underline{x}^{n},y^{n}}\Bigg{|}\frac{1}{2^{n(C_{1}+C_{2})}}\sum_{\mu_{1},\mu_{2}}\sum_{\begin{subarray}{c}w_{1}^{n}\in\mathbb{F}_{p}^{n}\end{subarray}}\sum_{w_{2}^{n}\notin\mathcal{T}_{\delta}^{(n)}(W_{2})}{p^{n}_{\underline{X}}(\underline{x}^{n})}\gamma_{w_{1}^{n}}^{(\mu_{1})}\bar{E}^{(\mu_{1})}_{W^{n}_{1}|X^{n}_{1}}(w^{n}_{1}|x_{1}^{n})\frac{p^{n}\zeta_{w_{2}^{n}}^{(\mu_{2})}}{2^{nS_{2}}(1+\eta)}$
$\displaystyle\hskip
252.94499ptp^{n}_{W_{2}|X_{2}}(w^{n}_{2}|x_{2}^{n})p^{n}_{Y|{Z}}(y^{n}|w_{1}^{n}\oplus
w_{2}^{n})\Bigg{|}$

We start by analyzing $F_{11}.$ Note that $F_{11}$ is exactly similar to the
term $Q_{1}$ and hence using the same rate constraints as $Q_{1}$, this term
can be bounded. Next consider the term corresponding to $F_{12}.$ Substituting
the definition of $\zeta_{w_{2}^{n}}^{(\mu_{2})}$ gives

$\displaystyle F_{12}$
$\displaystyle=\sum_{\underline{x}^{n},y^{n}}\Bigg{|}{p^{n}_{\underline{X}Y}(\underline{x}^{n},y^{n})}-\frac{p^{n}}{2^{nS_{2}}(1+\eta)}\sum_{w_{2}^{n}\in\mathbb{F}_{p}^{n}}\sum_{\begin{subarray}{c}m_{2}>0\\\
a_{2}\in\mathbb{F}_{q}^{k}\end{subarray}}\mathbbm{1}_{\\{\mathtt{w}_{2}(a_{2},m_{2},\mu_{2})=w_{2}^{n}\\}}p^{n}_{\underline{X}W_{2}Y}(\underline{x}^{n},w_{2}^{n},y^{n})\Bigg{|}$

Lemma 1 gives us functions $\epsilon_{F_{12}}(\delta),\delta_{F_{12}}(\delta)$
such that if

$S_{1}\geq I(W_{2};X_{1}X_{2}Y)-H(W_{2})+\log{p}+\delta_{F_{12}},$

then $\mathbb{E}[F_{12}]\leq\epsilon_{F_{12}}$, where
$\epsilon_{F_{12}}(\delta),\delta_{F_{12}}(\delta)\searrow 0$ as
$\delta\searrow 0.$

Now, we move on to considering in the term corresponding to $F_{13}.$ Taking
expectation with respect to $G,h_{1}^{(\mu_{1})}$ and $h_{2}^{(\mu_{2})}$
gives

$\displaystyle\mathbb{E}[F_{13}]$
$\displaystyle=\mathbb{E}_{G,h_{1}}\left[\sum_{\underline{x}^{n},y^{n}}\Bigg{|}\frac{1}{2^{nC_{2}}}\sum_{\mu_{2}}\sum_{w_{1}^{n},w_{2}^{n}\in\mathbb{F}_{p}^{n}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\bigg{(}p^{n}_{W_{1}|X_{1}}(w^{n}_{1}|x_{1}^{n})\right.$
$\displaystyle\hskip
21.68121pt\left.-\frac{1}{2^{nC_{1}}}\sum_{\mu_{1}}\gamma_{w_{1}^{n}}^{(\mu_{1})}E^{(\mu_{1})}_{W^{n}_{1}|X^{n}_{1}}(w^{n}_{1}|x_{1}^{n})\bigg{)}\mathbb{E}_{h_{2}|G}\left[\frac{p^{n}\zeta_{w_{2}^{n}}^{(\mu_{2})}}{2^{nS_{2}}(1+\eta)}\right]p^{n}_{W_{2}|X_{2}}(w^{n}_{2}|x_{2}^{n})p^{n}_{Y|{Z}}(y^{n}|w_{1}^{n}\oplus
w_{2}^{n})\right]$
$\displaystyle=\frac{1}{(1+\eta)}\mathbb{E}_{G,h_{1}}\left[\sum_{\underline{x}^{n},y^{n}}\Bigg{|}\frac{1}{2^{nC_{2}}}\sum_{\mu_{2}}\sum_{w_{1}^{n},w_{2}^{n}\in\mathbb{F}_{p}^{n}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\bigg{(}p^{n}_{W_{1}|X_{1}}(w^{n}_{1}|x_{1}^{n})\right.$
$\displaystyle\hskip
108.405pt\left.-\frac{1}{2^{nC_{1}}}\sum_{\mu_{1}}\gamma_{w_{1}^{n}}^{(\mu_{1})}E^{(\mu_{1})}_{W^{n}_{1}|X^{n}_{1}}(w^{n}_{1}|x_{1}^{n})\bigg{)}p^{n}_{W_{2}|X_{2}}(w^{n}_{2}|x_{2}^{n})p^{n}_{Y|{Z}}(y^{n}|w_{1}^{n}\oplus
w_{2}^{n})\right]$ $\displaystyle=\mathbb{E}\left[\frac{J}{(1+\eta)}\right],$

where the above equalities follows from the fact that $h_{1}^{(\mu_{1})}$ and
$h_{1}^{(\mu_{1})}$ were generated independently and from using the definition
of $J$ as stated earlier. Therefore, using the same analysis and rate
constraints as $J$, we can bound the term $F_{13}$. Finally, we remain with
the term $F_{14}$. Applying expectation on $F_{14}$ gives

$\displaystyle\mathbb{E}\left[F_{14}\right]$
$\displaystyle\leq\mathbb{E}_{G,h_{2}}\left[\sum_{\underline{x}^{n}}\Bigg{|}\sum_{\mu_{1},\mu_{2}}\\!\\!\\!\\!\\!\sum_{\begin{subarray}{c}w_{1}^{n}\in\mathbb{F}_{p}^{n}\\\
w_{2}^{n}\in\mathcal{T}_{\delta}^{(n)}(W_{2})\end{subarray}}\\!\\!\\!\\!{p^{n}_{\underline{X}}(\underline{x}^{n})}\frac{E_{h_{1}}\left[\gamma_{w_{1}^{n}}^{(\mu_{1})}\right]}{2^{n(C_{1}+C_{2})}}E^{(\mu_{1})}_{W^{n}_{1}|X^{n}_{1}}(w^{n}_{1}|x_{1}^{n})\frac{p^{n}\zeta_{w_{2}^{n}}^{(\mu_{2})}}{2^{nS_{2}}(1+\eta)}p^{n}_{W_{2}|X_{2}}(w^{n}_{2}|x_{2}^{n})\Bigg{|}\right]$
$\displaystyle\leq\sum_{\underline{x}^{n}}\frac{1}{2^{nC_{2}}}\sum_{\mu_{2}}\sum_{\begin{subarray}{c}w_{1}^{n}\in\mathcal{T}_{\delta}^{(n)}(W_{1})\\\
w_{2}^{n}\notin\mathcal{T}_{\delta}^{(n)}(W_{2})\end{subarray}}\\!\\!\\!\\!{p^{n}_{\underline{X}}(\underline{x}^{n})}\frac{p^{n}_{W_{1}|X_{1}}(w^{n}_{1}|x_{1}^{n})}{(1+\eta)}\mathbb{E}\left[\frac{p^{n}\zeta_{w_{2}^{n}}^{(\mu_{2})}}{2^{nS_{2}}(1+\eta)}\right]p^{n}_{W_{2}|X_{2}}(w^{n}_{2}|x_{2}^{n})$
$\displaystyle\leq\frac{1}{(1+\eta)^{2}}\sum_{\underline{x}^{n}}\sum_{\begin{subarray}{c}w_{2}^{n}\notin\mathcal{T}_{\delta}^{(n)}(W_{2})\end{subarray}}\\!\\!\\!\\!{p^{n}_{\underline{X}}(\underline{x}^{n})}p^{n}_{W_{2}|X_{2}}(w^{n}_{2}|x_{2}^{n})\leq\epsilon_{w}^{\prime},$

where $\epsilon_{w}^{\prime}(\delta)\searrow 0$ as $\delta\searrow 0.$ This
completes the analysis for the term corresponding to $F_{1}$. Finally we
remain with the analysis of the term $F_{2}.$ Simplifying $F_{2}$ gives

$\displaystyle F_{2}$
$\displaystyle\leq\frac{1}{2^{n(C_{1}+C_{2})}}\sum_{\begin{subarray}{c}\mu_{1},\mu_{2}\end{subarray}}\sum_{\underline{x}^{n}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\Bigg{(}\sum_{\begin{subarray}{c}w_{1}^{n}\in\mathbb{F}_{p}^{n}\end{subarray}}\gamma_{w_{1}^{n}}^{(\mu_{1})}E^{(\mu_{1})}_{W^{n}_{1}|X_{1}^{n}}(w^{n}_{1}|x_{1}^{n})\Bigg{)}$
$\displaystyle\hskip
70.0pt\Bigg{|}\sum_{\begin{subarray}{c}w_{2}^{n}\in\mathbb{F}_{p}^{n}\end{subarray}}\zeta_{w_{2}^{n}}^{(\mu_{2})}\left(\bar{E}^{(\mu_{2})}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})-{E}^{(\mu_{2})}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})\right)\Bigg{|},$
$\displaystyle=\frac{1}{2^{nC_{2}}}\sum_{\begin{subarray}{c}\mu_{1},\mu_{2}\end{subarray}}\sum_{\underline{x}^{n}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\bigg{(}\sum_{m_{1}>0}p_{M_{1}|X^{n}_{1}}(m_{1}|x_{1}^{n})\bigg{)}$
$\displaystyle\hskip
70.0pt\Bigg{|}\sum_{\begin{subarray}{c}w_{2}^{n}\in\mathbb{F}_{p}^{n}\end{subarray}}\zeta_{w_{2}^{n}}^{(\mu_{2})}\left(\bar{E}^{(\mu_{2})}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})-{E}^{(\mu_{2})}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})\right)\Bigg{|},$
$\displaystyle\leq\frac{1}{2^{nC_{2}}}\sum_{\begin{subarray}{c}\mu_{1},\mu_{2}\end{subarray}}\sum_{\underline{x}^{n}}{p^{n}_{\underline{X}}(\underline{x}^{n})}\Bigg{|}\sum_{\begin{subarray}{c}w_{2}^{n}\in\mathbb{F}_{p}^{n}\end{subarray}}\zeta_{w_{2}^{n}}^{(\mu_{2})}\left(\bar{E}^{(\mu_{2})}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})-{E}^{(\mu_{2})}_{W^{n}_{2}|X_{2}^{n}}(w^{n}_{2}|x_{2}^{n})\right)\Bigg{|},$
$\displaystyle=\tilde{S}_{2},$

where the last inequality above follows by using
$\bigg{(}\sum_{m_{1}>0}p_{M_{1}|X^{n}_{1}}(m_{1}|x_{1}^{n})\bigg{)}\leq 1$ and
the last equality follows by recalling the definition of $\tilde{S}_{2}$.
Therefore, using the constraints obtained in the analysis of $\tilde{S}_{2}$,
we complete the proof of the proposition.

## References

  * [1] T. Anwar Atif, A. Padakandla, and S. Sandeep Pradhan, “Source coding for synthesizing correlated randomness,” in _2020 IEEE International Symposium on Information Theory (ISIT)_ , 2020, pp. 1570–1575.
  * [2] J. Korner and K. Marton, “How to encode the modulo-two sum of binary sources (corresp.),” _IEEE Transactions on Information Theory_ , vol. 25, no. 2, pp. 219–221, 1979.
  * [3] R. Ahlswede and T. Han, “On source coding with side information via a multiple-access channel and related problems in multi-user information theory,” _IEEE Transactions on Information Theory_ , vol. 29, no. 3, pp. 396–412, 1983.
  * [4] A. Padakandla, A. G. Sahebi, and S. S. Pradhan, “An achievable rate region for the three-user interference channel based on coset codes,” _IEEE Transactions on Information Theory_ , vol. 62, no. 3, pp. 1250–1279, 2016.
  * [5] A. Wyner, “Recent results in the shannon theory,” _Information Theory, IEEE Transactions on_ , vol. 20, no. 1, pp. 2 – 10, Jan 1974.
  * [6] P. W. Cuff, “Communication in networks for coordinating behavior,” Ph.D. dissertation, Stanford, CA, USA, 2009.
  * [7] P. Cuff, “Distributed channel synthesis,” _IEEE Transactions on Information Theory_ , vol. 59, no. 11, pp. 7071–7096, Nov 2013.
  * [8] M. H. Yassaee, A. Gohari, and M. R. Aref, “Channel simulation via interactive communications,” _IEEE Transactions on Information Theory_ , vol. 61, no. 6, pp. 2964–2982, 2015.
  * [9] A. Winter, ““Extrinsic”and “Intrinsic” data in quantum measurements: Asymptotic convex decomposition of positive operator valued measures,” _Communications in mathematical physics_ , vol. 244, no. 1, pp. 157–185, 2004.
  * [10] M. M. Wilde, P. Hayden, F. Buscemi, and M.-H. Hsieh, “The information-theoretic costs of simulating quantum measurements,” _Journal of Physics A: Mathematical and Theoretical_ , vol. 45, no. 45, p. 453001, 2012.
  * [11] M. Heidari, T. A. Atif, and S. Sandeep Pradhan, “Faithful simulation of distributed quantum measurements with applications in distributed rate-distortion theory,” in _2019 IEEE International Symposium on Information Theory (ISIT)_ , July 2019, pp. 1162–1166.
  * [12] D. Krithivasan and S. S. Pradhan, “Distributed source coding using abelian group codes: A new achievable rate-distortion region,” _IEEE Transactions on Information Theory_ , vol. 57, no. 3, pp. 1495–1519, 2011.
  * [13] B. Nazer and M. Gastpar, “Computation over multiple-access channels,” _IEEE Trans. on Info. Th._ , vol. 53, no. 10, pp. 3498 –3516, oct. 2007.
  * [14] T. Philosof and R. Zamir, “On the loss of single-letter characterization: The dirty multiple access channel,” _IEEE Trans. on Info. Th._ , vol. 55, pp. 2442–2454, June 2009.
  * [15] A. Jafarian and S. Vishwanath, “Achievable rates for k-user Gaussian interference channels,” submitted to IEEE Trans. of Information theory 2011, available at http://arxiv.org/abs/1109.5336.
  * [16] S. S. Pradhan, A. Padakandla, and F. Shirani, _An Algebraic and Probabilistic Framework for Network Information Theory_. Foundations and Trends in Communications and Information Theory, 2021, vol. 18, no. 2.
  * [17] A. Padakandla and S. S. Pradhan, “Computing sum of sources over an arbitrary multiple access channel,” in _2013 IEEE International Symposium on Information Theory_. IEEE, 2013, pp. 2144–2148.
  * [18] R. G. Gallager, _Information Theory and Reliable Communication_. New York: John Wiley & Sons, 1968.
  * [19] T. A. Atif, A. Padakandla, and S. S. Pradhan, “Source coding for synthesizing correlated randomness,” _arXiv preprint arXiv:2004.03651_ , 2020.
  * [20] P. W. Cuff, _Communication in networks for coordinating behavior_. Stanford University, 2009.
  * [21] G. M. Ziegler, _Lectures on polytopes_. Springer Science & Business Media, 2012, vol. 152.