even if all _feasible_ product distributions are confusable. See Remark 14.
The coefficients of the convex combination can be regarded as giving a time-
sharing sequence. We then sample random codes in the following way. All
codewords are chopped up into chunks of lengths proportional to the convex
combination coefficients. Entries of all codewords in a particular chunk are
i.i.d. according the corresponding component distribution of the convex
combination. Effectively it is as if we convexly concatenate multiple
codebooks of shorter lengths sampled from different product distributions.
Again by a Chernoff-union argument, all joint types are tightly concentrated
around the mixture distribution provided that the rates are sufficiently
small. Since the mixture distribution itself is outside the confusability
sets, the code pair attains zero error with high probability. This gives Lemma
23. Such a code construction is known as _coded time-sharing_ (see Remark 14).

Secondly, by carefully analyzing the large deviation exponent, one can in fact
obtain _inner bounds_ on the capacity region. To this end, one could not
simply set the rates to be sufficiently small so as to admit a union bound. A
standard trick is to _remove_ (a.k.a. _expurgate_) one codeword from each
confusable pair. Using Sanov’s theorem (Lemma 3), one can get the exact
exponent of the probability of sampling a confusable pair. One can then set
the rates so as to guarantee that the (expected) number of expurgated
codewords is at most, say, half of the code size. This ensures that the
expurgation process does not hurt the rate. This gives Lemma 24. We remark
that if one wishes to achieve a rate pair with two positive rates, then the
above argument requires one to expurgate codewords that contribute to (at
least one of) jointly confusable pairs, first marginally confusable pairs or
second marginally confusable pairs. We believe that such an expurgation
strategy is pessimistic and higher rates may be obtained using more clever
expurgation strategies. See Item 4 in Section XVI.

###  XII-B Proof techniques for converse

The converse part is considerably more involved. At a high level, it is
inspired by the classical Plotkin bound in coding theory and follows a similar
structure as [WBBJ19]. However, due to the multiuser nature of the channel,
the case analysis is more delicate.

The basic proof strategy is comprised of the following components. Given any
code pair $({\mathcal{C}}_{1},{\mathcal{C}}_{2})$ that attains zero error, we
would like to show that they have zero rate(s) once the conditions in Theorem
20 are satisfied. To this end, we follow the steps below.

  1. 1.

First, we extract a subcode pair
$({\mathcal{C}}_{1}^{\prime},{\mathcal{C}}_{2}^{\prime})$ which has nontrivial
sizes and is “equicoupled”. More specifically, for one thing, the code sizes
are mildly large in the sense that
$|{\mathcal{C}}_{i}^{\prime}|\xrightarrow{|{\mathcal{C}}_{i}|\to\infty}\infty$
for $i=1,2$. In fact $|{\mathcal{C}}_{i}^{\prime}|=f(|{\mathcal{C}}_{i}|)$
where $f(\cdot)$ is the inverse Ramsey number which grows extremely slow.
However, this is enough for our purposes since it will be ultimately proved
that
$\max\left\\{|{\mathcal{C}}_{1}^{\prime}|,|{\mathcal{C}}^{\prime}|\right\\}\leq
C$ for some _constant_ $C>0$ independent of $n$. Then
$\max\left\\{|{\mathcal{C}}_{1}|,|{\mathcal{C}}_{2}|\right\\}\leq f^{-1}(C)$
which is a huge constant. However, this is already more than sufficient to
imply zero rates. For another (more important) thing, the subcode pair we
obtained is highly structured in the sense that the joint type of any codeword
tuple from the subcode pair is approximately the same (hence the subcodes are
at times called _equicoupled_ in this paper). This follows from Ramsey’s
theorem (Theorem 26). At the cost of losing rates (which is actually fine), we
localize some highly regular structures into a tiny subcode pair.

  2. 2.

We then focus on the subcode pair. It is unclear whether or not the
distribution that all joint types are concentrated around is symmetric (as per
Definition 14). However, viewing the codebook as a sequence of random
variables, we can show (in Section XIV-B) that the size of the equicoupled
subcode must be small if the distribution is asymmetric. This, after some
preprocessing of the sequence of random variables, follows from a classical
theorem by Komlós (Theorem 29).

  3. 3.

Now we assume that the equicoupled subcode is equipped with a symmetric
distribution. Since we started with a code pair of zero error, all joint types
are outside the confusability sets. Hence by the equicoupledness property, the
associated distribution is outside the confusability sets as well. By the
assumptions of Theorem 20, this distribution cannot be good (as per Definition
15) since the sets of good distributions are assumed to be subsets of the
confusability sets. By the duality (Theorem 18) between the sets of good and
“co-good” tensors (Definition 16), we can find a _witness_ (which itself is a
co-good tensor) of the non-goodness of the distribution. This finally allows
us to apply a Plotkin-type double counting trick. Specifically, we upper and
lower bound the following crucial quantity (Equation 96): the average inner
product between the witness and the joint types in the subcodes. Careful
calculations give us upper and lower bounds on this quantity. Contrasting
these bounds further gives us an upper bound on the code sizes as promised.

Similar argument can be adapted to the marginal case where exactly one
transmitter suffers from zero capacity.

##  XIII Achievability

We need the following lemma which concentrates the size of the constant
composition component of a random code. The proof follows from the Chernoff
bound (Lemma 2) and can be found in, e.g., [ZBJ20].

######  Lemma 21.

Let ${\mathcal{C}}\subseteq{\mathcal{X}}^{n}$ be a random code that consists
of codewords
${\underline{\mathbf{x}}}_{1},\cdots,{\underline{\mathbf{x}}}_{M}$ i.i.d.
according to $P_{\mathbf{x}}^{\otimes n}$ for some
$P_{\mathbf{x}}\in\Delta({\mathcal{X}})$. Let
${\mathcal{C}}^{\prime}\subseteq{\mathcal{C}}$ be the
$P_{\mathbf{x}}$-constant composition subcode of ${\mathcal{C}}$. Then

$\displaystyle\Pr\left[\left|{\mathcal{C}}^{\prime}\right|\notin(1\pm
1/2)\frac{M}{\nu(P_{\mathbf{x}},n)}\right]\leq$ $\displaystyle
2\exp\left(-\frac{M}{12\nu(P_{\mathbf{x}},n)}\right).$

###  XIII-A Positive achievable rates via product distributions

######  Lemma 22 (Positive achievable rates via product distributions).

Let $(P_{1},P_{2})\in\Gamma_{1}\times\Gamma_{2}$.

  1. 1.

If $P_{1}^{\otimes 2}\otimes P_{2}^{\otimes
2}\notin{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$, $P_{1}^{\otimes
2}\otimes P_{2}\notin{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$ and
$P_{1}\otimes P_{2}^{\otimes
2}\notin{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$, then there exist
achievable rate pairs $(R_{1},R_{2})$ such that $R_{1}>0,R_{2}>0$.

  2. 2.

If $P_{1}^{\otimes 2}\otimes
P_{2}\notin{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$, then there exist
achievable rate pairs $(R_{1},R_{2})$ such that $R_{1}>0,R_{2}=0$.

  3. 3.

If $P_{1}\otimes P_{2}^{\otimes
2}\notin{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$, then there exist
achievable rate pairs $(R_{1},R_{2})$ such that $R_{1}=0,R_{2}>0$.

###### Proof of Item 1 in Lemma 22.

Assume that both $P_{1}$ and $P_{2}$ have no zero atoms. Sample a random code
pair
$\left({\mathcal{C}}_{1},{\mathcal{C}}_{2}\right)\subseteq{\mathcal{X}}_{1}^{n}\times{\mathcal{X}}_{2}^{n}$
of sizes $(M_{1},M_{2})$, where ${\mathcal{C}}_{i}$ consists of codewords
${\underline{\mathbf{x}}}^{i}_{1},\cdots,{\underline{\mathbf{x}}}^{i}_{M_{i}}$
i.i.d. according to $P_{i}^{\otimes n}$ ($i=1,2$). Note that for any $1\leq
i_{1}<i_{2}\leq M_{1}$ and $1\leq j_{1}<j_{2}\leq M_{2}$,

$\displaystyle\mathbb{E}\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}}\right]=$
$\displaystyle P_{1}^{\otimes 2}\otimes P_{2}^{\otimes 2}.$ (57)

To see this, for any
$(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})\in{\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}^{2}$,

$\displaystyle\mathbb{E}\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}}\right](x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})=$
$\displaystyle\frac{1}{n}\sum_{k=1}^{n}\mathbb{E}\left[\mathds{1}{\left\\{{\underline{\mathbf{x}}}^{1}_{i_{1}}(k)=x^{1}_{1},{\underline{\mathbf{x}}}^{1}_{i_{2}}(k)=x^{1}_{2},{\underline{\mathbf{x}}}^{2}_{j_{1}}(k)=x^{2}_{1},{\underline{\mathbf{x}}}^{2}_{j_{2}}(k)=x^{2}_{2}\right\\}}\right]$
$\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{k=1}^{n}\mathbb{E}\left[\mathds{1}{\left\\{{\underline{\mathbf{x}}}^{1}_{i_{1}}(k)=x^{1}_{1}\right\\}}\right]\mathbb{E}\left[\mathds{1}{\left\\{{\underline{\mathbf{x}}}^{1}_{i_{1}}(k)=x^{1}_{2}\right\\}}\right]\mathbb{E}\left[\mathds{1}{\left\\{{\underline{\mathbf{x}}}^{2}_{j_{1}}(k)=x^{2}_{1}\right\\}}\right]\mathbb{E}\left[\mathds{1}{\left\\{{\underline{\mathbf{x}}}^{2}_{j_{2}}(k)=x^{2}_{2}\right\\}}\right]$
(58) $\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{k=1}^{n}\Pr\left[{\underline{\mathbf{x}}}^{1}_{i_{1}}(k)=x^{1}_{1}\right]\Pr\left[{\underline{\mathbf{x}}}^{1}_{i_{2}}(k)=x^{1}_{2}\right]\Pr\left[{\underline{\mathbf{x}}}^{2}_{j_{1}}(k)=x^{2}_{1}\right]\Pr\left[{\underline{\mathbf{x}}}^{2}_{j_{2}}(k)=x^{2}_{2}\right]$
$\displaystyle=$ $\displaystyle
P_{1}(x^{1}_{1})P_{1}(x^{1}_{2})P_{2}(x^{2}_{1})P_{2}(x^{2}_{2}),$ (59)

where Equation 58 follows since each codeword is sampled independent; Equation
59 follows since each component is identically distributed. Similarly,

$\displaystyle\mathbb{E}\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j_{1}}}\right]=$
$\displaystyle P_{1}^{\otimes 2}\otimes
P_{2},\quad\mathbb{E}\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}}\right]=P_{1}\otimes
P_{2}^{\otimes 2}.$

Let ${\mathcal{C}}_{i}^{\prime}$ be the $P_{i}$-constant composition subcode
of ${\mathcal{C}}_{i}$ ($i=1,2$). By Lemma 21, for $i=1,2$,

$\displaystyle\Pr\left[\left|{\mathcal{C}}_{i}^{\prime}\right|\notin(1\pm
1/2)\frac{M_{i}}{\nu(P_{i},n)}\right]\leq$ $\displaystyle
2\exp\left(-\frac{M_{i}}{12\nu(P_{i},n)}\right).$ (60)

Let

$\displaystyle\rho_{1,2}\coloneqq$ $\displaystyle
d_{{\infty}}\left(P_{1}^{\otimes 2}\otimes P_{2}^{\otimes
2},{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\right),$ (61)
$\displaystyle\rho_{1}\coloneqq$ $\displaystyle
d_{{\infty}}\left(P_{1}^{\otimes 2}\otimes
P_{2},{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\right),$
$\displaystyle\rho_{2}\coloneqq$ $\displaystyle d_{{\infty}}\left(P_{1}\otimes
P_{2}^{\otimes 2},{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)\right),$
$\displaystyle\varepsilon\coloneqq$
$\displaystyle\frac{1}{2}\min\left\\{\rho_{1,2},\rho_{1},\rho_{2}\right\\}.$

By the assumptions of Item 1, all the above quantities are _strictly_
positive. Since $\varepsilon<\rho_{1,2}$, for any $1\leq i_{1}<i_{2}\leq
M_{1}$ and $1\leq j_{1}<j_{2}\leq M_{2}$,

$\displaystyle\Pr\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}}\in{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\right]$
$\displaystyle\leq$
$\displaystyle\Pr\left[d_{{\infty}}\left(\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}},P_{1}^{\otimes
2}\otimes P_{2}^{\otimes 2}\right)\geq\varepsilon\right]$ $\displaystyle=$
$\displaystyle\Pr\left[\exists(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})\in{\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}^{2},\;\left|\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})-P_{1}(x^{1}_{1})P_{1}(x^{1}_{2})P_{2}(x^{2}_{1})P_{2}(x^{2}_{2})\right|\geq\varepsilon\right]$
$\displaystyle\leq$
$\displaystyle\sum_{(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})\in{\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}^{2}}\Pr\left[\left|\sum_{k=1}^{n}\mathds{1}{\left\\{{\underline{\mathbf{x}}}^{1}_{i_{1}}(k)=x^{1}_{1},{\underline{\mathbf{x}}}^{1}_{i_{2}}(k)=x^{1}_{2},{\underline{\mathbf{x}}}^{2}_{j_{1}}(k)=x^{2}_{1},{\underline{\mathbf{x}}}^{2}_{j_{2}}(k)=x^{2}_{2}\right\\}}-nP_{1}(x^{1}_{1})P_{1}(x^{1}_{2})P_{2}(x^{2}_{1})P_{2}(x^{2}_{2})\right|\geq
n\varepsilon\right]$ $\displaystyle=$
$\displaystyle\sum_{(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})\in{\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}^{2}}\Pr\left[\sum_{k=1}^{n}\mathds{1}{\left\\{{\underline{\mathbf{x}}}^{1}_{i_{1}}(k)=x^{1}_{1},{\underline{\mathbf{x}}}^{1}_{i_{2}}(k)=x^{1}_{2},{\underline{\mathbf{x}}}^{2}_{j_{1}}(k)=x^{2}_{1},{\underline{\mathbf{x}}}^{2}_{j_{2}}(k)=x^{2}_{2}\right\\}}\notin\left(1\pm\frac{n\varepsilon}{\mu}\right)\mu\right]$
(62) $\displaystyle\leq$
$\displaystyle\sum_{(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})\in{\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}^{2}}2\exp\left(-\frac{1}{3}\left(\frac{n\varepsilon}{\mu}\right)^{2}\mu\right)$
(63) $\displaystyle=$
$\displaystyle\sum_{(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})\in{\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}^{2}}2\exp\left(-\frac{n\varepsilon^{2}}{3P_{1}(x^{1}_{1})P_{1}(x^{1}_{2})P_{2}(x^{2}_{1})P_{2}(x^{2}_{2})}\right)$
(64) $\displaystyle\leq$
$\displaystyle\left|{\mathcal{X}}_{1}\right|^{2}\left|{\mathcal{X}}_{2}\right|^{2}\cdot
2\exp\left(-\frac{n\varepsilon^{2}}{3}\right).$ (65)

In Equation 62, we define

$\displaystyle\mu=\mu(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})\coloneqq\mathbb{E}\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}}\right](x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})=P_{1}(x^{1}_{1})P_{1}(x^{1}_{2})P_{2}(x^{2}_{1})P_{2}(x^{2}_{2})>0.$

Equation 63 is by Lemma 2. In Equation 64, we used Equation 57. In Equation
65, we used the trivial bound: for $i=1,2$, $P_{i}(x)\leq 1$ for
$x\in{\mathcal{X}}_{i}$.

We only need to consider ordered pairs $i_{1}<i_{2}$ and $j_{1}<j_{2}$, since
by the Item 2 of Proposition 15, if
$\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}\in{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$
then
$\tau_{{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{2}_{j_{2}},{\underline{x}}^{2}_{j_{1}}}\in{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$.
By union bound,

$\displaystyle\Pr\left[\exists((i_{1},i_{2}),(j_{1},j_{2}))\in\binom{[|{\mathcal{C}}_{1}^{\prime}|]}{2}\times\binom{[|{\mathcal{C}}_{2}^{\prime}|]}{2},\;\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}}\in{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\right]$
$\displaystyle\leq$
$\displaystyle\binom{M_{1}}{2}\binom{M_{2}}{2}\cdot\left|{\mathcal{X}}_{1}\right|^{2}\left|{\mathcal{X}}_{2}\right|^{2}\cdot
2\exp\left(-\frac{n\varepsilon^{2}}{3}\right)$ $\displaystyle\leq$
$\displaystyle\exp\left(n\left(2R_{1}\ln\left|{\mathcal{X}}_{1}\right|+2R_{2}\ln\left|{\mathcal{X}}_{2}\right|-\varepsilon^{2}/3+o(1)\right)\right).$
(66)

Similar Chernoff-union argument yields

$\displaystyle\Pr\left[\exists((i_{1},i_{2}),j)\in\binom{[|{\mathcal{C}}_{1}^{\prime}|]}{2}\times[|{\mathcal{C}}_{2}^{\prime}|],\;{\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j}}}\in{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\right]\leq$
$\displaystyle\exp\left(n\left(2R_{1}\ln\left|{\mathcal{X}}_{1}\right|+R_{2}\ln\left|{\mathcal{X}}_{2}\right|-\varepsilon^{2}/3+o(1)\right)\right),$
(67)
$\displaystyle\Pr\left[\exists(i,(j_{1},j_{2}))\in[|{\mathcal{C}}_{1}^{\prime}|]\times\binom{[|{\mathcal{C}}_{2}^{\prime}|]}{2},\;{\tau_{{\underline{\mathbf{x}}}^{1}_{i},{\underline{\mathbf{x}}}^{1}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}}}\in{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)\right]\leq$
$\displaystyle\exp\left(n\left(R_{1}\ln\left|{\mathcal{X}}_{1}\right|+2R_{2}\ln\left|{\mathcal{X}}_{2}\right|-\varepsilon^{2}/3+o(1)\right)\right).$
(68)

It suffices to take $(R_{1},R_{2})$ such that
$2R_{1}\ln\left|{\mathcal{X}}_{1}\right|+2R_{2}\ln\left|{\mathcal{X}}_{2}\right|-\varepsilon^{2}/3<0$.
For instance, one can take
$R_{1}=\frac{\varepsilon^{2}}{24\ln\left|{\mathcal{X}}_{1}\right|}$ and
$R_{2}=\frac{\varepsilon^{2}}{24\ln\left|{\mathcal{X}}_{2}\right|}$. Then
Equations 66, 67 and 68 are all $\exp\left(-\Omega(n)\right)$. Finally,
combining Equations 60, 66, 67 and 68, we get that with probability
$1-\exp(-\Omega(n))$,
$({\mathcal{C}}_{1}^{\prime},{\mathcal{C}}_{2}^{\prime})$ is a good code pair
of rates $R({\mathcal{C}}_{1}^{\prime})\asymp R_{1}>0$ and
$R({\mathcal{C}}_{2}^{\prime})\asymp R_{2}>0$. ∎

###### Proof of Items 2 and 3 in Lemma 22.

We only prove Item 2 and Item 3 follows similarly once the roles of user one
and user two are interchanged.

Suppose $P_{1}^{\otimes 2}\otimes
P_{2}\notin{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$. We construct a
codebook pair $({\mathcal{C}}_{1},{\mathcal{C}}_{2})$ as follows. The codebook
${\mathcal{C}}_{2}$ consists of only one (arbitrary) codeword
${\underline{x}}^{2}\in{\mathcal{X}}_{2}^{n}$ of type $P_{2}$. Apparently
$R({\mathcal{C}}_{2})\to 0$ as $n\to 0$. Indeed, user two cannot even transmit
a single bit reliably through the channel. The codebook
${\mathcal{C}}_{1}\in{\mathcal{X}}_{1}^{M\times n}$ consists of $M$ codewords
${\underline{\mathbf{x}}}^{1}_{1},\cdots,{\underline{\mathbf{x}}}^{1}_{M}$
i.i.d. according to $P_{1}^{\otimes n}$. Note that for all $1\leq
i_{1}<i_{2}\leq M$,
$\mathbb{E}\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{x}}^{2}}\right]=P_{1}^{\otimes
2}\otimes P_{2}$. Indeed, for any
$(x^{1}_{1},x^{1}_{2},x^{2})\in{\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}$,

$\displaystyle\mathbb{E}\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{x}}^{2}}\right](x^{1}_{1},x^{1}_{2},x^{2})=$
$\displaystyle\frac{1}{n}\sum_{k=1}^{n}\mathbb{E}\left[\mathds{1}{\left\\{{\underline{\mathbf{x}}}^{1}_{i_{1}}(k)=x^{1}_{1},{\underline{\mathbf{x}}}^{1}_{i_{2}}(k)=x^{1}_{2},{\underline{x}}^{2}(k)=x^{2}\right\\}}\right]$
$\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{k=1}^{n}\mathbb{E}\left[\mathds{1}{\left\\{{\underline{\mathbf{x}}}^{1}_{i_{1}}(k)=x^{1}_{1}\right\\}}\right]\mathbb{E}\left[\mathds{1}{\left\\{{\underline{\mathbf{x}}}^{1}_{i_{2}}(k)=x^{1}_{2}\right\\}}\right]\mathds{1}{\left\\{{\underline{x}}^{2}(k)=x^{2}\right\\}}$
$\displaystyle=$
$\displaystyle\Pr\left[{\underline{\mathbf{x}}}^{1}(1)=x^{1}_{1}\right]\Pr\left[{\underline{\mathbf{x}}}^{1}(1)=x^{1}_{2}\right]\frac{1}{n}\sum_{k=1}^{n}\mathds{1}{\left\\{{\underline{x}}^{2}(k)=x^{2}\right\\}}$
$\displaystyle=$ $\displaystyle
P_{1}(x^{1}_{1})P_{1}(x^{1}_{2})\tau_{{\underline{x}}^{2}}(x^{2})$
$\displaystyle=$ $\displaystyle\left(P_{1}^{\otimes 2}\otimes
P_{2}\right)(x^{1}_{1},x^{1}_{2},x^{2}).$

By Lemma 21, Equation 60 holds for the $P_{1}$-constant composition subcode of
${\mathcal{C}}_{1}$, denoted by ${\mathcal{C}}_{1}^{\prime}$. Therefore,
${\mathcal{C}}_{1}^{\prime}$ has asymptotically the same rate as
$R({\mathcal{C}}_{1})$.

We define the gap $\rho_{1}>0$ between $P_{1}^{\otimes 2}\otimes P_{2}$ and
${\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$ in the same way as in Equation
61. Let $\varepsilon\coloneqq\rho_{1}/2$. Similar Chernoff-union-type argument
as before yields

$\displaystyle\Pr\left[\exists(i_{1},i_{2})\in\binom{[|{\mathcal{C}}_{1}^{\prime}|]}{2},\;\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{x}}^{2}}\in{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\right]\leq$
$\displaystyle\binom{M}{2}\cdot\left|{\mathcal{X}}_{1}\right|^{2}\cdot
2\exp\left(-\frac{n\varepsilon^{2}}{3}\right)$ $\displaystyle\leq$
$\displaystyle\exp\left(n\left(2R_{1}\ln\left|{\mathcal{X}}_{1}\right|-\varepsilon^{2}/3+o(1)\right)\right).$
(69)

Taking $R_{1}=\frac{\varepsilon^{2}}{12\left|{\mathcal{X}}_{1}\right|}$, we
get that with probability $1-2^{-\Omega(n)}$, the codebook pair
$({\mathcal{C}}_{1}^{\prime},{\mathcal{C}}_{2})$ constructed above is good. ∎

###  XIII-B Positive achievable rates via mixtures of product distributions

######  Lemma 23 (Positive achievable rates via mixtures product
distributions).

Fix input distributions $(P_{1},P_{2})\in\Gamma_{1}\times\Gamma_{2}$.

  1. 1.

If ${\mathcal{G}}\left(P_{1},P_{2}\right)\neq\emptyset$, then there exist
achievable rate pairs $(R_{1},R_{2})$ such that $R_{1}>0,R_{2}>0$.

  2. 2.

If
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\neq\emptyset$,
then there exist achievable rate pairs $(R_{1},0)$ such that $R_{1}>0$.

  3. 3.

If
${\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)\neq\emptyset$,
then there exist achievable rate pairs $(0,R_{2})$ such that $R_{2}>0$.

###### Proof of Item 1.

By the condition in Item 1, we are able to find a distribution
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{G}}\left(P_{1},P_{2}\right)$.
Suppose
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}=\sum_{{\ell}=1}^{k}\lambda_{\ell}P_{1,{\ell}}^{\otimes
2}\otimes P_{2,{\ell}}^{\otimes 2}$ for some $k\in{\mathbb{Z}}_{\geq 1}$,
$\left\\{\lambda_{\ell}\right\\}_{{\ell}=1}^{k}\subset(0,1]$ with
$\sum_{{\ell}=1}^{k}\lambda_{\ell}=1$ and distributions
$\left\\{P_{1,{\ell}}\right\\}_{{\ell}=1}^{k}\subset\Delta({\mathcal{X}}_{1}),\left\\{P_{2,{\ell}}\right\\}_{{\ell}=1}^{k}\subset\Delta({\mathcal{X}}_{2})$.
It simultaneously holds that

$\displaystyle
P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in$
$\displaystyle{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right),$
(70) $\displaystyle
P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\coloneqq\sum_{\ell=1}^{k}\lambda_{\ell}P_{1,\ell}^{\otimes
2}\otimes P_{2,\ell}\in$
$\displaystyle{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right),$
$\displaystyle
P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\coloneqq\sum_{\ell=1}^{k}\lambda_{\ell}P_{1,\ell}\otimes
P_{2,\ell}^{\otimes 2}\in$
$\displaystyle{\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right).$

See Figure 3(a) for the geometry of the aforementioned distributions.

Partition $[n]$ into $k$ subsets ${\mathcal{I}}_{1},\cdots,{\mathcal{I}}_{k}$
such that $|{\mathcal{I}}_{\ell}|=\lambda_{\ell}n$ (${\ell}\in[k]$). Now
sample a codebook pair
$({\mathcal{C}}_{1},{\mathcal{C}}_{2})\subseteq{\mathcal{X}}_{1}^{n}\times{\mathcal{X}}_{2}^{n}$
of sizes $(M_{1},M_{2})$ in the following way. For $i=1,2$, ${\ell}\in[k]$,
the entries of each codeword of ${\mathcal{C}}_{i}$ that are in
${\mathcal{I}}_{\ell}$ are i.i.d. according to $P_{i,{\ell}}$. See Figure 3(b)
for a pictorial explanation of the code construction.

The proof is similar to that of Lemma 22 and the geometry of various
distributions is depicted in Figure 3(c).

(a) By the assumption ${\mathcal{G}}\left(P_{1},P_{2}\right)\neq\emptyset$,
there exists a distribution $\sum_{i=1}^{k}\lambda_{i}P_{1,i}^{\otimes
2}\otimes P_{2,i}^{\otimes
2}\notin{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$ such that
$\sum_{i=1}^{k}\lambda_{i}P_{1,i}^{\otimes 2}\otimes
P_{2,i}\notin{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$ and
$\sum_{i=1}^{k}\lambda_{i}P_{1,i}\otimes P_{2,i}^{\otimes
2}\notin{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$ (see Equation 70).

(b) A pictorial explanation of our code construction from
$\sum_{i=1}^{k}\lambda_{i}P_{1,i}^{\otimes 2}\otimes P_{2,i}^{\otimes 2}$. The
construction can be viewed as an application of coded time-sharing where the
time-sharing sequence is given by the convex combination coefficients
$\left\\{\lambda_{i}\right\\}_{i=1}^{k}$. For any fixed value $\ell\in[k]$ of
the time-sharing variable, each symbol of ${\mathcal{C}}_{i}$ is i.i.d.
according to $P_{\ell,i}$.

(c) By the assumption that $\sum_{i=1}^{k}\lambda_{i}P_{1,i}^{\otimes
2}\otimes P_{2,i}^{\otimes 2}$ is $\rho_{1,2}$-far from
${\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$,
$\sum_{i=1}^{k}\lambda_{i}P_{1,i}^{\otimes 2}\otimes P_{2,i}$ is
$\rho_{1}$-far from ${\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$ and
$\sum_{i=1}^{k}\lambda_{i}P_{1,i}\otimes P_{2,i}^{\otimes 2}$ is
$\rho_{2}$-far from ${\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$, one can
show via a Chernoff-union-type argument that all joint types of
$({\mathcal{C}}_{1},{\mathcal{C}}_{2})$ are $\varepsilon$-far from the
confusability sets and hence $({\mathcal{C}}_{1},{\mathcal{C}}_{2})$ attains
positive rates and zero error. The gap factors $\rho_{1,2},\rho_{1},\rho_{2}$
and $\varepsilon$ are defined in Equation 72.

Figure 3: Illustration of the proof of Item 1 of Lemma 23. Under the
assumption ${\mathcal{G}}\left(P_{1},P_{2}\right)\neq\emptyset$, the goal is
to show the existence of zero-error code pairs
$({\mathcal{C}}_{1},{\mathcal{C}}_{2})$ of positive rates.

We can apply similar Chernoff-union argument to the $\ell$-th punctured codes
of $({\mathcal{C}}_{1},{\mathcal{C}}_{2})$ for each $\ell\in[k]$ and then take
a union bound over ${\ell}$. Here by the $\ell$-th punctured codes we mean the
codes obtained by restricting codewords to ${\mathcal{I}}_{\ell}$. We use
${\underline{\mathbf{x}}}_{i,{\ell}}^{1}\in{\mathcal{X}}_{1}^{\lambda_{\ell}n}$
and
${\underline{\mathbf{x}}}_{j,{\ell}}^{2}\in{\mathcal{X}}_{2}^{\lambda_{\ell}n}$
to denote respectively the subsequences of ${\underline{\mathbf{x}}}^{1}_{i}$
and ${\underline{\mathbf{x}}}^{2}_{j}$ whose components are in
${\mathcal{I}}_{\ell}$. Note that for any $1\leq i_{1}<i_{2}\leq M_{1}$ and
$1\leq j_{1}<j_{2}\leq M_{2}$, by 4,

$\displaystyle\mathbb{E}\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}}\right]=$
$\displaystyle\sum_{\ell=1}^{k}\lambda_{\ell}\mathbb{E}\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1},\ell},{\underline{\mathbf{x}}}^{1}_{i_{2},\ell},{\underline{\mathbf{x}}}^{2}_{j_{1},\ell},{\underline{\mathbf{x}}}^{2}_{j_{2},\ell}}\right]=\sum_{\ell=1}^{k}\lambda_{\ell}P_{1,\ell}^{\otimes
2}\otimes P_{2,\ell}^{\otimes
2}=P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},$
$\displaystyle\mathbb{E}\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j_{1}}}\right]=$
$\displaystyle\sum_{\ell=1}^{k}\lambda_{\ell}\mathbb{E}\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1},\ell},{\underline{\mathbf{x}}}^{1}_{i_{2},\ell},{\underline{\mathbf{x}}}^{2}_{j_{1},\ell}}\right]=\sum_{\ell=1}^{k}\lambda_{\ell}P_{1,\ell}^{\otimes
2}\otimes
P_{2,\ell}=P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}},$
$\displaystyle\mathbb{E}\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}}\right]=$
$\displaystyle\sum_{\ell=1}^{k}\lambda_{\ell}\mathbb{E}\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1},\ell},{\underline{\mathbf{x}}}^{2}_{j_{1},\ell},{\underline{\mathbf{x}}}^{2}_{j_{2},\ell}}\right]=\sum_{\ell=1}^{k}\lambda_{\ell}P_{1,\ell}\otimes
P_{2,\ell}^{\otimes
2}=P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}.$

Let ${\mathcal{C}}_{i}^{\prime}$ be the subcode of ${\mathcal{C}}_{i}$ such
that all codewords in ${\mathcal{C}}_{i}^{\prime}$ restricted to
${\mathcal{I}}_{\ell}$ are $P_{i,\ell}$-constant composition
($i=1,2,\ell\in[k]$). The size of ${\mathcal{C}}_{i}^{\prime}$ can be
concentrated similarly as before.

$\displaystyle\mathbb{E}\left[|{\mathcal{C}}_{i}^{\prime}|\right]=$
$\displaystyle\sum_{j=1}^{M_{i}}\Pr\left[\forall\ell\in[k],\;\tau_{{\underline{\mathbf{x}}}^{i}_{j,\ell}}=P_{i,\ell}\right]=\sum_{j=1}^{M_{i}}\prod_{\ell=1}^{k}\Pr\left[\tau_{{\underline{\mathbf{x}}}^{i}_{j,\ell}}=P_{i,\ell}\right]\asymp
M_{i}\prod_{\ell=1}^{k}\nu(P_{i,\ell},\lambda_{\ell}n)^{-1}.$

By Lemma 2,

$\displaystyle\Pr\left[|{\mathcal{C}}_{i}^{\prime}|\notin(1\pm
1/2)\mathbb{E}\left[|{\mathcal{C}}_{i}^{\prime}|\right]\right]\leq$
$\displaystyle
2\exp\left(-\frac{M_{i}}{12\prod_{\ell=1}^{k}\nu(P_{i,\ell},\lambda_{\ell}n)}\right).$
(71)

Let

$\displaystyle\rho_{1,2}\coloneqq$ $\displaystyle
d_{{\infty}}\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\right)>0,$
(72) $\displaystyle\rho_{1}\coloneqq$ $\displaystyle
d_{{\infty}}\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}},{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\right)>0,$
$\displaystyle\rho_{2}\coloneqq$ $\displaystyle
d_{{\infty}}\left(P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)\right)>0,$
$\displaystyle\varepsilon\coloneqq$
$\displaystyle\frac{1}{2}\min\left\\{\rho_{1,2},\rho_{1},\rho_{2}\right\\}>0.$

For any $1\leq i_{1}<i_{2}\leq M_{1}$ and $1\leq j_{1}<j_{2}\leq M_{2}$,

$\displaystyle\Pr\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}}\in{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\right]\leq$
$\displaystyle\Pr\left[\exists\ell\in[k],\;d_{{\infty}}\left(\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1},\ell},{\underline{\mathbf{x}}}^{1}_{i_{2},\ell},{\underline{\mathbf{x}}}^{2}_{j_{1},\ell},{\underline{\mathbf{x}}}^{2}_{j_{2},\ell}},P_{1,\ell}^{\otimes
2}\otimes P_{2,\ell}^{\otimes 2}\right)\geq\varepsilon\right]$ (73)
$\displaystyle\leq$ $\displaystyle
k\cdot\left|{\mathcal{X}}_{1}\right|^{2}\left|{\mathcal{X}}_{2}\right|^{2}\cdot
2\exp\left(-\frac{n\varepsilon^{2}}{3}\right).$ (74)

Equation 73 follows since
$d_{{\infty}}\left(\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1},\ell},{\underline{\mathbf{x}}}^{1}_{i_{2},\ell},{\underline{\mathbf{x}}}^{2}_{j_{1},\ell},{\underline{\mathbf{x}}}^{2}_{j_{2},\ell}},P_{1,\ell}^{\otimes
2}\otimes P_{2,\ell}^{\otimes 2}\right)<\varepsilon$ for all $\ell\in[k]$
implies

$\displaystyle
d_{{\infty}}\left(\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)$
$\displaystyle=$
$\displaystyle\max_{(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})\in{\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}^{2}}\left|\sum_{\ell=1}^{k}\lambda_{\ell}\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1},\ell},{\underline{\mathbf{x}}}^{1}_{i_{2},\ell},{\underline{\mathbf{x}}}^{2}_{j_{1},\ell},{\underline{\mathbf{x}}}^{2}_{j_{2},\ell}}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})-\sum_{\ell=1}^{k}\lambda_{\ell}P_{1,\ell}^{\otimes
2}\otimes P_{2,\ell}^{\otimes
2}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})\right|$ $\displaystyle\leq$
$\displaystyle\sum_{\ell=1}^{k}\lambda_{\ell}\max_{(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})\in{\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}^{2}}\left|\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1},\ell},{\underline{\mathbf{x}}}^{1}_{i_{2},\ell},{\underline{\mathbf{x}}}^{2}_{j_{1},\ell},{\underline{\mathbf{x}}}^{2}_{j_{2},\ell}}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})-P_{1,\ell}^{\otimes
2}\otimes P_{2,\ell}^{\otimes
2}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})\right|$ $\displaystyle=$
$\displaystyle\sum_{\ell=1}^{k}\lambda_{\ell}d_{{\infty}}\left(\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1},\ell},{\underline{\mathbf{x}}}^{1}_{i_{2},\ell},{\underline{\mathbf{x}}}^{2}_{j_{1},\ell},{\underline{\mathbf{x}}}^{2}_{j_{2},\ell}},P_{1,\ell}^{\otimes
2}\otimes P_{2,\ell}^{\otimes 2}\right)<\varepsilon<\rho_{1,2},$

which in turn implies
$\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}}\notin{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$.
In Equation 74, we took a union bound over $\ell\in[k]$ where
$k={\mathcal{O}}(1)$.

Similarly, we have

$\displaystyle\Pr\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j}}\in{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\right]\leq$
$\displaystyle
k\cdot\left|{\mathcal{X}}_{1}\right|^{2}\left|{\mathcal{X}}_{2}\right|\cdot
2\exp\left(-\frac{n\varepsilon^{2}}{3}\right),$ (75)

for all $1\leq i_{1}<i_{2}\leq M_{1}$ and $1\leq j\leq M_{2}$; and

$\displaystyle\Pr\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}}\in{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)\right]\leq$
$\displaystyle
k\cdot\left|{\mathcal{X}}_{1}\right|\left|{\mathcal{X}}_{2}\right|^{2}\cdot
2\exp\left(-\frac{n\varepsilon^{2}}{3}\right),$ (76)

for all $1\leq i\leq M_{1}$ and $1\leq j_{1}<j_{2}\leq M_{2}$. Taking further
union bounds on Equations 74, 75 and 76 over $((i_{1},i_{2}),(j_{1},j_{2}))$,
$((i_{1},i_{2}),j)$ and $(i,(j_{1},j_{2}))$ respectively ensures that
Equations 66, 67 and 68 still hold. The rest of the proof remains the same and
we get a good code pair
$({\mathcal{C}}_{1}^{\prime},{\mathcal{C}}_{2}^{\prime})$ of rate
$R({\mathcal{C}}_{1}^{\prime})>0,R({\mathcal{C}}_{2}^{\prime})>0$. ∎

###### Proof of Items 2 and 3.

We only prove Item 2 since Item 3 is the same once the roles of the first and
second users are swapped.

Suppose
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$
has a decomposition
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}=\sum_{\ell=1}^{k}\lambda_{\ell}P_{1,\ell}^{\otimes
2}\otimes P_{2,\ell}$ for some $k\in{\mathbb{Z}}_{\geq 1}$,
$\left\\{\lambda_{\ell}\right\\}_{\ell=1}^{k}\subset(0,1]$ with
$\sum_{\ell=1}^{k}\lambda_{\ell}=1$ and
$\left\\{P_{1,\ell}\right\\}_{\ell=1}^{k}\subset\Delta({\mathcal{X}}_{1}^{2})$,
$\left\\{P_{2,\ell}\right\\}_{\ell=1}^{k}\subset\Delta({\mathcal{X}}_{2}^{2})$.

Partition $[n]$ into $k$ subsets ${\mathcal{I}}_{1},\cdots,{\mathcal{I}}_{k}$
such that $|{\mathcal{I}}_{\ell}|=\lambda_{\ell}n$ (${\ell}\in[k]$). Construct
a codebook pair $({\mathcal{C}}_{1},{\mathcal{C}}_{2})$ as follows. The second
codebook ${\mathcal{C}}_{2}$ only consists of one (arbitrary) codeword
${\underline{x}}^{2}\in{\mathcal{X}}_{2}^{n}$ satisfying the following
property. Let
${\underline{x}}^{2}_{\ell}\in{\mathcal{X}}_{2}^{\lambda_{\ell}n}$ denote the
subsequence of ${\underline{x}}^{2}$ restricted to ${\mathcal{I}}_{\ell}$. For
each $\ell\in[k]$, $\tau_{{\underline{x}}^{2}_{\ell}}=P_{2,\ell}$. The first
codebook ${\mathcal{C}}_{1}\in{\mathcal{X}}_{1}^{M\times n}$ consists of $M$
codewords
${\underline{\mathbf{x}}}^{1}_{1},\cdots,{\underline{\mathbf{x}}}^{1}_{M}$,
where for each $i\in[M]$ and $\ell\in[k]$,
${\underline{\mathbf{x}}}^{1}_{i,\ell}\overset{\mathrm{i.i.d.}}{\sim}P_{1,\ell}^{\otimes(\lambda_{\ell}n)}$.
Note that for all $1\leq i_{1}<i_{2}\leq M$,
$\mathbb{E}\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{x}}^{2}}\right]=P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}$.
Let ${\mathcal{C}}_{1}^{\prime}$ be the subcode of ${\mathcal{C}}_{1}$ whose
codewords restricted to ${\mathcal{I}}_{\ell}$ are all $P_{1,\ell}$-constant
composition ($\ell\in[k]$). For ${\mathcal{C}}_{1}^{\prime}$, Equation 71
still holds. Therefore, $R({\mathcal{C}}_{1}^{\prime})\asymp
R({\mathcal{C}}_{1})$ ($n\to\infty$). We define $\rho_{1}$ in the same way as
in Equation 72. Let $\varepsilon\coloneqq\rho_{1}/2$. Since

$\displaystyle
d_{{\infty}}\left(\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{x}}^{2}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\right)\leq$
$\displaystyle\sum_{\ell=1}^{k}\lambda_{\ell}d_{{\infty}}\left(\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1},\ell},{\underline{\mathbf{x}}}^{1}_{i_{2},\ell},{\underline{x}}^{2}_{\ell}},P_{1,\ell}^{\otimes
2}\otimes P_{2,\ell}\right),$

a Chernoff-union bound gives

$\displaystyle\Pr\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{x}}^{2}}\in{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\right]\leq$
$\displaystyle\Pr\left[d_{{\infty}}\left(\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{x}}^{2}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\right)\geq\varepsilon\right]$
$\displaystyle\leq$
$\displaystyle\Pr\left[\exists\ell\in[k],\;d_{{\infty}}\left(\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1},\ell},{\underline{\mathbf{x}}}^{1}_{i_{2},\ell},{\underline{x}}^{2}_{\ell}},P_{1,\ell}^{\otimes
2}\otimes P_{2,\ell}\right)\geq\varepsilon\right]$ $\displaystyle\leq$
$\displaystyle k\cdot\left|{\mathcal{X}}_{1}\right|^{2}\cdot
2\exp\left(-\frac{n\varepsilon^{2}}{3}\right).$

Since $k$ is a constant independent of $n$, a union bound over
$(i_{1},i_{2})\in\binom{[|{\mathcal{C}}_{1}^{\prime}|]}{2}$ gives Equation 69.
Under a proper choice of $R_{1}>0$, we get that
$({\mathcal{C}}_{1}^{\prime},{\mathcal{C}}_{2})$ is a good codebook pair with
probability at least $1-2^{-\Omega(n)}$. ∎

######  Remark 14.

In the above proof of Lemma 23, the partition
$\left\\{{\mathcal{I}}_{\ell}\right\\}_{\ell=1}^{k}$ can be thought of as a
_time-sharing_ sequence ${\underline{u}}\in[k]^{n}$ of type $P_{\mathbf{u}}$
given by the coefficients $\left\\{\lambda_{i}\right\\}_{i=1}^{k}$ of the
convex combination. That is, $P_{\mathbf{u}}(u)=\lambda_{u}$ for any
$u\in[k]$. This particular type of time-sharing scheme is known as the _coded_
time-sharing in the literature [PS19]. As explained in [PS19, Remark 6], the
classical _operational_ time-sharing in network information theory does not
work for (oblivious) arbitrarily varying channels with constraints. This is
because the adversary can concentrate his power on coordinates in a single
${\mathcal{I}}_{\ell}$. This effectively increases the noise level in
${\mathcal{I}}_{\ell}$ significantly and the $\ell$-th component codebook in
the time-sharing is not necessarily resilient to this effective level of
noise. The above argument also applies to the omniscient adversarial channel
model. More discussions on the “non-tensorization” of good codes for
adversarial channels and its implications to single-letterization of capacity
expressions can be found in Item 5 of Section XVI. These phenomena suggest
that the capacity region of adversarial channels does not have to be convex in
general (see Section XI-A).

Furthermore, we emphasize the following point in the above achievability
proof. Each component $P_{1,\ell}$ and $P_{2,\ell}$ of the convex combinations
is not necessarily non-confusable, i.e., $P_{1,\ell}^{\otimes 2}\otimes
P_{2,\ell}^{\otimes 2}$, $P_{1,\ell}^{\otimes 2}\otimes P_{2,\ell}$ or
$P_{1,\ell}\otimes P_{2,\ell}^{\otimes 2}$ may be confusable. Nonetheless, it
is only desired that their convex combinations are non-confusable.

######  Remark 15.

In the above proof of Items 2 and 3, the transmitter with zero capacity cannot
even reliably transmit a single bit through the MAC since the codebook
contains only one codeword. Such achievability proofs go through as long as
there exist non-marginally confusable distributions. In contrast, in the AVMAC
setting [PS19], besides non-marginal symmetrizability, non-joint
symmetrizability is a necessary condition for achieving any positive rate even
individually instead of jointly. More discussions on the differences between
our results and Pereg–Steinberg’s [PS19] can be found in Section XI-B.

###  XIII-C Inner bounds via product distributions

######  Lemma 24 (Inner bounds via product distributions).

Fix input distributions $(P_{1},P_{2})\in\Gamma_{1}\times\Gamma_{2}$.

  1. 1.

If $P_{1}^{\otimes 2}\otimes P_{2}^{\otimes
2}\notin{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$,
$P_{1}\notin{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$ and
$P_{2}\notin{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$, then rate pairs
$(R_{1},R_{2})\in{\mathbb{R}}_{\geq 0}^{2}$ satisfying

$\displaystyle R_{1}\leq$ $\displaystyle
D(P_{1},P_{2})-\widehat{D}(P_{1},P_{2})$ (77) $\displaystyle R_{2}\leq$
$\displaystyle D(P_{1},P_{2})-\widehat{D}(P_{1},P_{2})$ $\displaystyle
R_{1}+R_{2}\leq$ $\displaystyle\widehat{D}(P_{1},P_{2})$

are achievable, where

$\displaystyle D(P_{1},P_{2})\coloneqq$
$\displaystyle\min_{P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)}D\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}^{\otimes 2}\right)$
$\displaystyle\widehat{D}(P_{1},P_{2})\coloneqq$
$\displaystyle\min\left\\{\min_{P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)}D\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\middle\|P_{1}^{\otimes
2}\otimes
P_{2}\right),\min_{P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)}D\left(P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\middle\|P_{1}\otimes
P_{2}^{\otimes 2}\right)\right\\}.$

  2. 2.

If $P_{1}^{\otimes 2}\otimes P_{2}^{\otimes
2}\notin{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$, $P_{1}^{\otimes
2}\notin{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$ and $P_{2}^{\otimes
2}\in{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$, then rate pairs $(R_{1},0)$
satisfying

$\displaystyle 0\leq
R_{1}\leq\min_{P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)}D\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}\right)$ (78)

are achievable.

  3. 3.

If $P_{1}^{\otimes 2}\otimes P_{2}^{\otimes
2}\notin{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$, $P_{1}^{\otimes
2}\in{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$ and $P_{2}^{\otimes
2}\notin{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$, then rate pairs
$(0,R_{2})$ satisfying

$\displaystyle 0\leq
R_{2}\leq\min_{P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)}D\left(P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\middle\|P_{1}\otimes
P_{2}^{\otimes 2}\right)$ (79)

are achievable.

######  Corollary 25 (Inner bounds on capacity region).

Let
$\mathsf{MAC}_{2}=\left({\mathcal{X}}_{1},{\mathcal{X}}_{2},{\mathcal{S}},{\mathcal{Y}},\Gamma_{1},\Gamma_{2},\Lambda,W_{{\mathbf{y}}|{\mathbf{x}},{\mathbf{s}}}\right)$
be a two-user omniscient adversarial MAC. The capacity region of
$\mathsf{MAC}_{2}$ contains as a subset the following region

$\displaystyle\bigcup_{\begin{subarray}{c}(P_{1},P_{2})\in\Gamma_{1}\times\Gamma_{2}\\\
\text{conditions in \lx@cref{creftypecap~refnum}{itm:rate-prod-pos-pos} are
satisfied}\end{subarray}}\left\\{(R_{1},R_{2}):(R_{1},R_{2})\text{ satisfies
}\lx@cref{creftypecap~refnum}{eqn:achieve-product-12}\right\\}$
$\displaystyle\cup\bigcup_{\begin{subarray}{c}(P_{1},P_{2})\in\Gamma_{1}\times\Gamma_{2}\\\
\text{conditions in \lx@cref{creftypecap~refnum}{itm:rate-prod-pos-zero} are
satisfied}\end{subarray}}\left\\{(R_{1},0):R_{1}\text{ satisfies
\lx@cref{creftypecap~refnum}{eqn:rate-prod-pos-zero}}\right\\}$
$\displaystyle\cup\bigcup_{\begin{subarray}{c}(P_{1},P_{2})\in\Gamma_{1}\times\Gamma_{2}\\\
\text{conditions in \lx@cref{creftypecap~refnum}{itm:rate-prod-zero-pos} are
satisfied}\end{subarray}}\left\\{(0,R_{2}):R_{2}\text{ satisfies
\lx@cref{creftypecap~refnum}{eqn:rate-prod-zero-pos}}\right\\}.$

###### Proof of Item 1.

Sample a random code pair
$\left({\mathcal{C}}_{1},{\mathcal{C}}_{2}\right)\subseteq{\mathcal{X}}_{1}^{n}\times{\mathcal{X}}_{2}^{n}$
of sizes $(M_{1},M_{2})$, where ${\mathcal{C}}_{i}$ consists of codewords
${\underline{\mathbf{x}}}^{i}_{1},\cdots,{\underline{\mathbf{x}}}^{i}_{M_{i}}$
i.i.d. according to $P_{i}^{\otimes n}$ ($i=1,2$). By Lemma 1, the the
expected number of codewords in ${\mathcal{C}}_{i}$ of type $P_{i}$ is
asymptotically $M_{i}/\nu(P_{i},n)$. For any $1\leq i_{1}<i_{2}\leq M_{1}$ and
$1\leq j_{1}<j_{2}\leq M_{2}$, by Lemma 3,

$\displaystyle\Pr\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}}\in{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\right]\doteq$
$\displaystyle\sup_{P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)}2^{-nD\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}^{\otimes 2}\right)},$
$\displaystyle\Pr\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j_{1}}}\in{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\right]\doteq$
$\displaystyle\sup_{P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)}2^{-nD\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}\right)},$
$\displaystyle\Pr\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}}\in{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)\right]\doteq$
$\displaystyle\sup_{P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)}2^{-nD\left(P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\middle\|P_{1}\otimes
P_{2}^{\otimes 2}\right)}.$

Hence the expected number of confusable tuples
$({\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}})$,
$({\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j})$
and
$({\underline{\mathbf{x}}}^{1}_{i},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}})$
is respectively

$\displaystyle\binom{M_{1}}{2}\binom{M_{2}}{2}2^{-n\inf
D\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}^{\otimes 2}\right)}\leq$ $\displaystyle
M_{1}^{2}M_{2}^{2}2^{-n\inf
D\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}^{\otimes 2}\right)},$
$\displaystyle\binom{M_{1}}{2}M_{2}2^{-n\inf
D\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}\right)}\leq$ $\displaystyle M_{1}^{2}M_{2}2^{-n\inf
D\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}\right)},$ $\displaystyle M_{1}\binom{M_{2}}{2}2^{-n\inf
D\left(P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\middle\|P_{1}\otimes
P_{2}^{\otimes 2}\right)}\leq$ $\displaystyle M_{1}M_{2}^{2}2^{-n\inf
D\left(P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\middle\|P_{1}\otimes
P_{2}^{\otimes 2}\right)}.$

Pick $M_{1},M_{2}$ such that

$\displaystyle M_{1}^{2}M_{2}^{2}2^{-n\inf
D\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}^{\otimes 2}\right)}\leq$
$\displaystyle\min\left\\{\frac{M_{1}}{3\nu(P_{1},n)},\frac{M_{2}}{3\nu(P_{2},n)}\right\\},$
$\displaystyle M_{1}^{2}M_{2}2^{-n\inf
D\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}\right)}\leq$ $\displaystyle\frac{M_{1}}{3\nu(P_{1},n)}$
$\displaystyle M_{1}M_{2}^{2}2^{-n\inf
D\left(P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\middle\|P_{1}\otimes
P_{2}^{\otimes 2}\right)}\leq$ $\displaystyle\frac{M_{2}}{3\nu(P_{2},n)}.$

This can be satisfied if

$\displaystyle 2R_{1}+2R_{2}-\inf
D\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}^{\otimes 2}\right)\leq$
$\displaystyle\min\left\\{R_{1},R_{2}\right\\}-o(1),$ $\displaystyle
2R_{1}+R_{2}-\inf
D\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}\right)\leq$ $\displaystyle R_{1}-o(1),$ $\displaystyle
R_{1}+2R_{2}-\inf
D\left(P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\middle\|P_{1}\otimes
P_{2}^{\otimes 2}\right)\leq$ $\displaystyle R_{2}-o(1),$

i.e.,

$\displaystyle R_{1}+2R_{2}\leq$ $\displaystyle\inf
D\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}^{\otimes 2}\right)-o(1),$ $\displaystyle 2R_{1}+R_{2}\leq$
$\displaystyle\inf
D\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}^{\otimes 2}\right)-o(1),$ $\displaystyle R_{1}+R_{2}\leq$
$\displaystyle\min\left\\{\inf
D\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}\right)-o(1),\inf
D\left(P_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\middle\|P_{1}\otimes
P_{2}^{\otimes 2}\right)-o(1)\right\\}.$

That is, it suffices to take $(R_{1},R_{2})$ satisfying Equation 77 (as
$n\to\infty$).

Now, we remove all codewords from ${\mathcal{C}}_{1}$ and ${\mathcal{C}}_{2}$
whose types are not $P_{1}$ and $P_{2}$ respectively. For all $1\leq
i_{1}<i_{2}\leq M_{1}$ and $1\leq j_{1}<j_{2}\leq M_{2}$, we also remove

  1. 1.

one of
$({\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{j_{2}})$
from ${\mathcal{C}}_{1}$ and one of
$({\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}})$
from ${\mathcal{C}}_{2}$ if
$\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}}\in{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$;

  2. 2.

one of
$({\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}})$
from ${\mathcal{C}}_{1}$ if
$\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{\mathbf{x}}}^{2}_{j_{1}}}\in{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$;

  3. 3.

one of
$({\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}})$
from ${\mathcal{C}}_{2}$ if
$\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{2}_{j_{1}},{\underline{\mathbf{x}}}^{2}_{j_{2}}}\in{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$.

After the removal, $\left({\mathcal{C}}_{1},{\mathcal{C}}_{2}\right)$ becomes
a good code pair. In total, the expected number of codewords we removed from
${\mathcal{C}}_{i}$ is at most

$\displaystyle
M_{i}-\frac{M_{i}}{\nu(P_{i},n)}+\frac{M_{i}}{3\nu(P_{i},n)}+\frac{M_{i}}{3\nu(P_{i},n)}=M_{i}-\frac{M_{i}}{3\nu(P_{i},n)}$

for $i=1,2$. Therefore, $(R_{1},R_{2})$ is preserved after the removal. Noting
that we have exhibited the existence of code pairs that attain zero error for
$\mathsf{MAC}_{2}$ with desired rates, we finish the proof. ∎

###### Proof of Items 2 and 3.

We only prove Item 2. Item 3 will follow verbatim. Let
${\underline{x}}^{2}\in{\mathcal{X}}_{2}^{n}$ be an arbitrary codeword of type
$P_{2}$. The codebook ${\mathcal{C}}_{2}$ only consists of
${\underline{x}}^{2}$. The codebook ${\mathcal{C}}_{1}$ consists of $M$
codewords
${\underline{\mathbf{x}}}^{1}_{1},\cdots,{\underline{\mathbf{x}}}^{1}_{M}$
i.i.d. according to $P_{1}^{\otimes n}$. Again, the expected number of
codewords in ${\mathcal{C}}_{1}$ of type $P_{1}$ is asymptotically
$M/\nu(P_{1},n)$. By Lemma 3, for any $1\leq i_{1}<i_{2}\leq M$,

$\displaystyle\Pr\left[\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{x}}^{2}}\in{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\right]\doteq$
$\displaystyle\sup_{P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)}2^{-nD\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}\right)}.$

Hence the expected number of confusable tuples
$({\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{x}}^{2})$
is

$\displaystyle\binom{M}{2}2^{-n\inf
D\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}\right)}\leq$ $\displaystyle M^{2}2^{-n\inf
D\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}\right)}.$

Pick $M$ such that

$\displaystyle M^{2}2^{-n\inf
D\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}\right)}\leq$ $\displaystyle\frac{M}{2\nu(P_{1},n)}.$

It suffices to take

$\displaystyle 2R_{1}-\inf
D\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\middle\|P_{1}^{\otimes
2}\otimes P_{2}\right)\leq$ $\displaystyle R_{1}-o(1),$

i.e., $R_{1}$ asymptotically satisfies Equation 78.

We then remove all codewords from ${\mathcal{C}}_{1}$ which have type
different from $P_{1}$. We also remove ${\underline{\mathbf{x}}}^{1}_{i_{1}}$
if
$\tau_{{\underline{\mathbf{x}}}^{1}_{i_{1}},{\underline{\mathbf{x}}}^{1}_{i_{2}},{\underline{x}}^{2}}\in{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$
for some $i_{1}<i_{2}\leq M$. After removal we get a constant composition
codebook pair that attains zero error. The expected number of codewords we
removed from ${\mathcal{C}}_{1}$ is at most
$M-M/\nu(P_{1},n)+M/2\nu(P_{1},n)=M-M/2\nu(P_{1},n)$. Therefore, the removal
does not (asymptotically) change the rate. This finishes the proof. ∎

######  Remark 16.

In Lemma 24, we did not obtain a pentagon region defined by three mutual
information terms as is commonly seen in problems regarding MACs. It is
perhaps due to our crude expurgation strategy. We believe that our inner
bounds can be improved by employing more careful expurgation strategies (see
Item 4 in Section XVI).

##  XIV Converse, Item 1 in Theorem 20

In this section, we assume that
${\mathcal{G}}\left(P_{1},P_{2}\right)=\emptyset$. Let
$({\mathcal{C}}_{1},{\mathcal{C}}_{2})\subseteq{\mathcal{X}}_{1}^{n}\times{\mathcal{X}}_{2}^{n}$
be any good codebook pair. Without loss of rate, we assume that
${\mathcal{C}}_{1}$ is $P_{1}$-constant composition and ${\mathcal{C}}_{2}$ is
$P_{2}$-constant composition. Our goal is to show that $R({\mathcal{C}}_{1})$
and $R({\mathcal{C}}_{2})$ cannot be simultaneously positive. In fact, we will
show that at least one of $M_{1}\coloneqq|{\mathcal{C}}_{1}|$ and
$M_{2}\coloneqq|{\mathcal{C}}_{2}|$ is bounded from above by a _constant_
(independent of $n$).

###  XIV-A Subcode pair extraction

######  Definition 18 (Bipartite, uniform, complete hypergraphs).

A hypergraph ${\mathcal{H}}=({\mathcal{V}},{\mathcal{E}})$ is called
_$(N_{1},N_{2})$ -bipartite_ if it is bipartite with
${\mathcal{V}}={\mathcal{V}}_{1}\sqcup{\mathcal{V}}_{2}$ where
$|{\mathcal{V}}_{1}|=N_{1}$ and $|{\mathcal{V}}_{2}|=N_{2}$. It is called
_$(k_{1},k_{2})$ -uniform_ if every hyperedge contains $k_{1}$ vertices in
${\mathcal{V}}_{1}$ and $k_{2}$ vertices in ${\mathcal{V}}_{2}$. It is called
_complete_ if every $k_{1}$-tuple of vertices in ${\mathcal{V}}_{1}$ and every
$k_{2}$-tuple of vertices in ${\mathcal{V}}_{2}$ are connected.

######  Theorem 26 (Bipartite hypergraph Ramsey’s theorem [BLA76]).

Let $N_{1},N_{2},D$ be integers that are at least 2. There exist constants
$K_{1}=K_{2}(N_{1},N_{2},D)$ and $K_{2}=K_{2}(N_{1},N_{2},D)$ such that for
every $(M_{1},M_{2})$-bipartite $(2,2)$-uniform complete hypergraph
${\mathcal{H}}=(({\mathcal{V}}_{1},{\mathcal{V}}_{2}),{\mathcal{E}})$ such
that $|{\mathcal{V}}_{1}|=M_{1}\geq K_{1}$ and $|{\mathcal{V}}_{2}|=M_{2}\geq
K_{2}$, for every $D$-coloring of ${\mathcal{E}}$, there must exist
${\mathcal{V}}_{1}^{\prime}\subseteq{\mathcal{V}}_{1}$ and
${\mathcal{V}}_{2}^{\prime}\subseteq{\mathcal{V}}_{2}$ such that
$|{\mathcal{V}}_{1}^{\prime}|\geq N_{1},|{\mathcal{V}}_{2}^{\prime}|\geq
N_{2}$ and all hyperedges crossing ${\mathcal{V}}_{1}^{\prime}$ and
${\mathcal{V}}_{2}^{\prime}$ have the same color.

######  Lemma 27 (Subcode pair extraction).

For any code pair
$\left({\mathcal{C}}_{1},{\mathcal{C}}_{2}\right)=\left(\left\\{{\underline{x}}^{1}_{k}\right\\}_{k=1}^{M_{1}},\left\\{{\underline{x}}^{2}_{\ell}\right\\}_{\ell=1}^{M_{2}}\right)$
of sizes $M_{1}$ and $M_{2}$, respectively, there exists a subcode pair
$\left({\mathcal{C}}_{1}^{\prime},{\mathcal{C}}_{2}^{\prime}\right)=\left(\left\\{{\underline{x}}^{1}_{i}\right\\}_{i=1}^{M_{1}^{\prime}},\left\\{{\underline{x}}^{2}_{j}\right\\}_{j=1}^{M_{2}^{\prime}}\right)$
of sizes $M_{1}^{\prime}\geq
f_{1}(|{\mathcal{X}}_{1}|,|{\mathcal{X}}_{2}|,\eta,M_{1},M_{2})\xrightarrow{M_{1}\to\infty}\infty$
and $M_{2}^{\prime}\geq
f_{2}(|{\mathcal{X}}_{1}|,|{\mathcal{X}}_{2}|,\eta,M_{1},M_{2})\xrightarrow{M_{2}\to\infty}\infty$,
respectively, and there exists a distribution
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)$
such that, for all $1\leq i_{1}<i_{2}\leq M_{1}^{\prime}$ and $1\leq
j_{1}<j_{2}\leq M_{2}^{\prime}$, it holds that
$d_{{\infty}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)\leq\eta$.

###### Proof.

To apply Theorem 26, we build an $(M_{1},M_{2})$-bipartite $(2,2)$-uniform
complete hypergraph ${\mathcal{H}}$. The left and right vertex sets of
${\mathcal{H}}$ are the codewords in ${\mathcal{C}}_{1}$ and the codewords in
${\mathcal{C}}_{2}$ respectively. Every pair of codewords
$({\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}})\in\binom{{\mathcal{C}}_{1}}{2}$
(where $1\leq i_{1}<i_{2}<M_{1}$) in the left vertex set is connected to all
pairs of codewords
$({\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}})\in\binom{{\mathcal{C}}_{2}}{2}$
(for all $1\leq j_{1}<j_{2}\leq M_{2}$) in the right vertex set.

We now color all hyperedges of ${\mathcal{H}}$ using distributions in
${\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)$. To this end, we first take an
$\eta$-net ${\mathcal{N}}$ of ${\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)$
with respect to $d_{\infty}$. By Lemma 5,
$D\coloneqq\left|{\mathcal{N}}\right|$ can be made no larger than
$\left(\frac{\left|{\mathcal{X}}_{1}\right|^{2}\times\left|{\mathcal{X}}_{2}\right|^{2}}{2\eta}+1\right)^{\left|{\mathcal{X}}_{1}\right|^{2}\times\left|{\mathcal{X}}_{2}\right|^{2}}$.
The hyperedges in ${\mathcal{H}}$ are colored in the following way. If an
hyperedge
$(({\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}}),({\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}))$
(where $1\leq i_{1}<i_{2}<M_{1}$ and $1\leq j_{1}<j_{2}\leq M_{2}$) satisfies
$d_{{\infty}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)\leq\eta$
for some
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{N}}$,
then we color this hyperedge by
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$.
Note that by the covering property of ${\mathcal{N}}$, such a distribution
must exist.

By Theorem 26, there exist subcodes
$({\mathcal{C}}_{1}^{\prime},{\mathcal{C}}_{2}^{\prime})$ of
$({\mathcal{C}}_{1},{\mathcal{C}}_{2})$ satisfying

  1. 1.

$M_{1}^{\prime}\coloneqq|{\mathcal{C}}_{1}^{\prime}|\geq
N_{1},M_{2}^{\prime}\coloneqq|{\mathcal{C}}_{2}^{\prime}|\geq N_{2}$ for
$N_{1}=N_{1}(M_{1},M_{2},D),N_{2}=N_{2}(M_{1},M_{2},D)$ with
$N_{1}\xrightarrow{M_{1}\to\infty}\infty,N_{2}\xrightarrow{M_{2}\to\infty}\infty$;

  2. 2.

all hyperedges between ${\mathcal{C}}_{1}^{\prime}$ and
${\mathcal{C}}_{2}^{\prime}$ are monochromatic.

In other words, according to the way we colored the hyperedges, there is a
distribution
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)$
such that for all $1\leq i_{1}<i_{2}\leq M_{1}^{\prime}$ and $1\leq
j_{1}<j_{2}\leq M_{2}^{\prime}$, we have
$d_{{\infty}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)\leq\eta$.
This completes the proof. ∎

In what follows, we will prove that the “equicoupled” subcode pair
$({\mathcal{C}}_{1}^{\prime},{\mathcal{C}}_{2}^{\prime})$ must have at least
one zero rate. We do so by treating separately the case where
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
is (almost) symmetric and the case where it is (significantly) asymmetric. We
will actually show that131313Hereafter we use the simplified notation
$M_{1}^{\prime}=f(M_{1})$ and $M_{2}^{\prime}=f(M_{2})$ (where $f(\cdot)$ is
an increasing function) to emphasize the respective dependence of
$|{\mathcal{C}}_{1}^{\prime}|$ and $|{\mathcal{C}}_{2}^{\prime}|$ on
$|{\mathcal{C}}_{1}|$ and ${\mathcal{C}}_{2}$, ignoring the dependence on
other parameters. Indeed, noting $M_{1},M_{2}\geq 1$ and treating
$\left|{\mathcal{X}}_{1}\right|,\left|{\mathcal{X}}_{2}\right|,\eta$ as
constants, one can take
$f(\cdot)=\min\left\\{f_{1}(\left|{\mathcal{X}}_{1}\right|,\left|{\mathcal{X}}_{2}\right|,\eta;\cdot,1),f_{2}(\left|{\mathcal{X}}_{1}\right|,\left|{\mathcal{X}}_{2}\right|,\eta;1,\cdot)\right\\}$
where $f_{1}$ and $f_{2}$ are from Lemma 27.  $M_{1}^{\prime}=f(M_{1})\leq
C_{1}$ or $M_{2}^{\prime}=f(M_{2})\leq C_{2}$ for some constants (independent
of $n$) $C_{1}>0$ and $C_{2}>0$. Since $f(\cdot)$ is a (slowly) increasing
function, this implies that the original code pair
$({\mathcal{C}}_{1},{\mathcal{C}}_{2})$ has sizes $M_{1}\leq f^{-1}(C_{1})$
and $M_{2}\leq f^{-1}(C_{2})$ which are still constants (though enormous).
This is a stronger statement than that $({\mathcal{C}}_{1},{\mathcal{C}}_{2})$
have at least one zero rate.

###  XIV-B Asymmetric case

######  Definition 19 (Asymmetry and approximate symmetry).

The _$\left\\{1,2\right\\}$ -asymmetry_, the _$\left\\{1\right\\}$
-asymmetry_, the _$\left\\{2\right\\}$ -asymmetry_ and the _asymmetry_ of a
distribution
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in\Delta({\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}^{2})$
is respectively defined as

$\displaystyle\mathrm{asymm}_{1,2}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})\coloneqq$
$\displaystyle\max_{(x^{1}_{1},x^{1}_{2})\in{{\mathcal{X}}_{1}}^{2}}\max_{(x^{2}_{1},x^{2}_{2})\in{{\mathcal{X}}_{2}}^{2}}\left|P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})-P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{2},x^{1}_{1},x^{2}_{2},x^{2}_{1})\right|,$
$\displaystyle\mathrm{asymm}_{1}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})\coloneqq$
$\displaystyle\max_{(x^{1}_{1},x^{1}_{2})\in{{\mathcal{X}}_{1}}^{2}}\max_{(x^{2}_{1},x^{2}_{2})\in{{\mathcal{X}}_{2}}^{2}}\left|P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})-P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{2},x^{1}_{1},x^{2}_{1},x^{2}_{2})\right|,$
$\displaystyle\mathrm{asymm}_{2}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})\coloneqq$
$\displaystyle\max_{(x^{1}_{1},x^{1}_{2})\in{{\mathcal{X}}_{1}}^{2}}\max_{(x^{2}_{1},x^{2}_{2})\in{{\mathcal{X}}_{2}}^{2}}\left|P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})-P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{1},x^{1}_{2},x^{2}_{2},x^{2}_{1})\right|,$
$\displaystyle\mathrm{asymm}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})\coloneqq$
$\displaystyle\max\left\\{\mathrm{asymm}_{1,2}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}),\mathrm{asymm}_{1}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}),\mathrm{asymm}_{2}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})\right\\}.$

A distribution
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
is called _$\alpha$ -symmetric_ if
$\mathrm{asymm}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})\leq\alpha$.

######  Remark 17.

By definition, a self-coupling
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)$
is in ${\mathcal{S}}_{1,2}\left(P_{1},P_{2}\right)$ if and only if
$\mathrm{asymm}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})=0$.

According to Definition 19, the asymmetry of
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
that was extracted in Lemma 27 can be divided into eight different cases as
shown in Table III below. Case (1) in Table III corresponds to the case where
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
is $\alpha$-symmetric. This case will be treated in Section XIV-C. Other cases
correspond to when
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
is asymmetric with asymmetry larger than $\alpha$. They will be treated in
Sections XIV-B1, XIV-B2 and XIV-B3.

Cases | $\mathrm{asymm}_{1,2}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})\stackrel{{\scriptstyle?}}{{\leq}}\alpha$ | $\mathrm{asymm}_{1}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})\stackrel{{\scriptstyle?}}{{\leq}}\alpha$ | $\mathrm{asymm}_{2}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})\stackrel{{\scriptstyle?}}{{\leq}}\alpha$ | Section
---|---|---|---|---
Case (1) | $\leq$ | $\leq$ | $\leq$ | Section XIV-C
Case (2) | $>$ | $\leq$ | $\leq$ | Section XIV-B3
Case (3) | $\leq$ | $>$ | $\leq$ | Section XIV-B3
Case (4) | $\leq$ | $\leq$ | $>$ | Section XIV-B3
Case (5) | $>$ | $>$ | $\leq$ | Section XIV-B1
Case (6) | $>$ | $\leq$ | $>$ | Section XIV-B1
Case (7) | $\leq$ | $>$ | $>$ | Section XIV-B2
Case (8) | $>$ | $>$ | $>$ | Section XIV-B2
TABLE III: The asymmetric case can be divided into several sub-cases.

For the asymmetric cases (Cases (5)-(8) in Table III), we prove the following
lemma.

######  Lemma 28.

If a code pair
$({\mathcal{C}}_{1}^{\prime},{\mathcal{C}}_{2}^{\prime})\in{\mathcal{X}}_{1}^{M_{1}^{\prime}\times
n}\times{\mathcal{X}}_{2}^{M_{2}^{\prime}\times n}$ satisfies that there
exists a distribution
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)$
such that

  1. 1.

${\mathcal{C}}_{i}$ is $P_{i}$-constant composition for $i=1,2$;

  2. 2.

for all $1\leq i_{1}<i_{2}\leq M_{1}^{\prime}$ and $1\leq j_{1}<j_{2}\leq
M_{2}^{\prime}$,
$d_{{\infty}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)\leq\eta$;

  3. 3.

$\mathrm{asymm}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})\geq\alpha$,

then at least one of $M_{1}^{\prime}$ and $M_{2}^{\prime}$ is at most a
constant $C(\alpha,\eta)>0$.

###### Proof.

The proof is divided into several cases. As we shall see in Sections XIV-B1
and XIV-B2, only Cases (5)-(8) in Table III are asymmetric cases. Cases
(2)-(4), handled in Section XIV-B3, can be reduced to the symmetric case (Case
(1)). The symmetric Case (1) will be treated in the next section (Section
XIV-C). ∎

The following lemma will be crucial in the proceeding subsections.

######  Theorem 29 ([Kom90]).

Let ${\mathbf{v}}_{1},\cdots,{\mathbf{v}}_{M}$ be a sequence of random
variables over a common finite alphabet ${\mathcal{W}}$. If there exist a
distribution
$P_{{\mathbf{w}}_{1},{\mathbf{w}}_{2}}\in\Delta({\mathcal{W}}^{2})$ and a
constant $\eta\geq 0$ such that
$\left\|P_{{\mathbf{v}}_{i},{\mathbf{v}}_{j}}-P_{{\mathbf{w}}_{1},{\mathbf{w}}_{2}}\right\|_{\infty}\leq\eta$
for all $1\leq i<j\leq M$, then
$\mathrm{asymm}(P_{{\mathbf{w}}_{1},{\mathbf{w}}_{2}})\leq{6}/{\sqrt{M}}+4\sqrt{\eta}+2\eta$,
where

$\displaystyle\mathrm{asymm}(P_{{\mathbf{w}}_{1},{\mathbf{w}}_{2}})\coloneqq$
$\displaystyle\max_{(w_{1},w_{2})\in{\mathcal{W}}\times{\mathcal{W}}}\left|P_{{\mathbf{w}}_{1},{\mathbf{w}}_{2}}(w_{1},w_{2})-P_{{\mathbf{w}}_{1},{\mathbf{w}}_{2}}(w_{2},w_{1})\right|.$

####  XIV-B1 Cases (5) & (6) in Table III

We only prove Case (5) since Case (6) is the same up to change of notation. We
will show that $M_{1}^{\prime}\coloneqq|{\mathcal{C}}_{1}^{\prime}|$ is at
most a constant.

We identify
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
with $P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{z}}^{2}}$ where
${\mathbf{z}}^{2}=({\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2})$ is a random
variable over ${\mathcal{Z}}_{2}\coloneqq{\mathcal{X}}_{2}^{2}$. Immediately,
$\alpha<\mathrm{asymm}_{1}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})=\mathrm{asymm}_{1}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{z}}^{2}})$
where
$\mathrm{asymm}_{1}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})$
is naturally defined as

$\displaystyle\mathrm{asymm}_{1}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{z}}^{2}})\coloneqq$
$\displaystyle\max_{(x^{1}_{1},x^{1}_{2})\in{\mathcal{X}}_{1}^{2}}\max_{z^{2}\in{\mathcal{Z}}_{2}}\left|P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{z}}^{2}}(x^{1}_{1},x^{1}_{2},z^{2})-P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{z}}^{2}}(x^{1}_{2},x^{1}_{1},z^{2})\right|.$

We then have the following simple lemma.

######  Lemma 30.

If a distribution
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{z}}^{2}}$ satisfies
$\mathrm{asymm}_{1}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{z}}^{2}})>\alpha$,
then $\mathrm{asymm}(P_{{\mathbf{w}}_{1},{\mathbf{w}}_{2}})>\alpha$, where
${\mathbf{w}}_{i}\coloneqq({\mathbf{x}}^{1}_{i},{\mathbf{z}}^{2})\in{\mathcal{W}}\coloneqq{\mathcal{X}}_{1}\times{\mathcal{Z}}_{2}$
for $i=1,2$.

###### Proof.

The lemma follows from the following simple (in)equalities:

$\displaystyle\left|P_{{\mathbf{w}}_{1},{\mathbf{w}}_{2}}(w_{1},w_{2})-P_{{\mathbf{w}}_{1},{\mathbf{w}}_{2}}(w_{2},w_{1})\right|=$
$\displaystyle\left|P_{({\mathbf{x}}^{1}_{1},{\mathbf{z}}^{2}),({\mathbf{x}}^{1}_{2},{\mathbf{z}}^{2})}((x^{1}_{1},z^{2}),(x^{1}_{2},z^{2}))-P_{({\mathbf{x}}^{1}_{1},{\mathbf{z}}^{2}),({\mathbf{x}}^{1}_{2},{\mathbf{z}}^{2})}((x^{1}_{2},z^{2}),(x^{1}_{1},z^{2}))\right|$
$\displaystyle=$
$\displaystyle\left|P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{z}}^{2}}(x^{1}_{1},x^{1}_{2},z^{2})-P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{z}}^{2}}(x^{1}_{2},x^{1}_{1},z^{2})\right|>\alpha.\qed$
(80)

Recall
$M_{1}^{\prime}\coloneqq\left|{\mathcal{C}}_{1}^{\prime}\right|,M_{2}^{\prime}\coloneqq\left|{\mathcal{C}}_{2}^{\prime}\right|$.
By equicoupledness, for any fixed $1\leq j_{1}<j_{2}<M_{2}^{\prime}$, we have
$d_{{\infty}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)\leq\eta$
for all $1\leq i_{1}<i_{2}\leq M_{1}^{\prime}$. Identify the codewords
${\underline{x}}^{1}_{1},\cdots,{\underline{x}}^{1}_{M_{1}^{\prime}}$ in
${\mathcal{C}}_{1}^{\prime}$ together with
${\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}\in{\mathcal{C}}_{2}^{\prime}$
with a sequence of random variables
${\boldsymbol{\chi}}_{1},\cdots,{\boldsymbol{\chi}}_{M_{1}^{\prime}},{\boldsymbol{\zeta}}^{2}\in{\mathcal{X}}_{1}^{M_{1}^{\prime}}\times{\mathcal{Z}}_{2}$.
That is
$P_{{\boldsymbol{\chi}}_{1},\cdots,{\boldsymbol{\chi}}_{M_{1}^{\prime}},{\boldsymbol{\zeta}}^{2}}\coloneqq\tau_{{\underline{x}}^{1}_{1},\cdots,{\underline{x}}^{1}_{M_{1}^{\prime}},({\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}})}$.
Arrange this sequence in the following way:
${\mathbf{v}}_{1},\cdots,{\mathbf{v}}_{M_{1}^{\prime}}$ where
${\mathbf{v}}_{i}=({\boldsymbol{\chi}}_{i},{\boldsymbol{\zeta}}^{2})\in{\mathcal{W}}\coloneqq{\mathcal{X}}_{1}\times{\mathcal{Z}}_{2}$.
This sequence satisfies
$d_{{\infty}}\left(P_{{\mathbf{v}}_{i_{1}},{\mathbf{v}}_{i_{2}}},P_{{\mathbf{w}}_{1},{\mathbf{w}}_{2}}\right)\leq\eta$
for every $1\leq i_{1}<i_{2}\leq M_{1}^{\prime}$. To see this,

$\displaystyle
d_{{\infty}}\left(P_{{\mathbf{v}}_{i_{1}},{\mathbf{v}}_{i_{2}}},P_{{\mathbf{w}}_{1},{\mathbf{w}}_{2}}\right)=$
$\displaystyle
d_{{\infty}}\left(P_{({\boldsymbol{\chi}}_{i_{1}},{\boldsymbol{\zeta}}^{2}),({\boldsymbol{\chi}}_{i_{2}},{\boldsymbol{\zeta}}^{2})},P_{({\mathbf{x}}^{1}_{1},{\mathbf{z}}^{2}),({\mathbf{x}}^{1}_{2},{\mathbf{z}}^{2})}\right)$
$\displaystyle=$ $\displaystyle
d_{{\infty}}\left(P_{{\boldsymbol{\chi}}_{i_{1}},{\boldsymbol{\chi}}_{i_{2}},{\boldsymbol{\zeta}}^{2}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{z}}^{2}}\right)$
$\displaystyle=$ $\displaystyle
d_{{\infty}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)\leq\eta.$
(81)

Equation 81 is by the second assumption of Lemma 28. Now by Theorem 29 and
Lemma 30, $\alpha<\mathrm{asymm}(P_{{\mathbf{w}}_{1},{\mathbf{w}}_{2}})\leq
6/\sqrt{M_{1}^{\prime}}+4\sqrt{\eta}+2\eta$, i.e.,
$M_{1}^{\prime}<36/(\alpha-4\sqrt{\eta}-2\eta)^{2}$. This finishes the proof
of this case.

####  XIV-B2 Cases (7) & (8) in Table III

In both Cases (7) & (8), it simultaneously holds that
$\mathrm{asymm}_{1}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})>\alpha$
and
$\mathrm{asymm}_{2}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})>\alpha$.
By the analysis of the previous case, we have
$M_{1}^{\prime}<36/(\alpha-4\sqrt{\eta}-2\eta)^{2}$ and
$M_{2}^{\prime}<36/(\alpha-4\sqrt{\eta}-2\eta)^{2}$.

####  XIV-B3 Cases (2)-(4) in Table III

We apply the following lemma to handle Cases (2)-(4).

######  Lemma 31.

The following relations hold.

$\displaystyle\mathrm{asymm}_{1,2}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})\leq$
$\displaystyle\mathrm{asymm}_{1}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})+\mathrm{asymm}_{2}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}),$
(82)
$\displaystyle\mathrm{asymm}_{1}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})\leq$
$\displaystyle\mathrm{asymm}_{1,2}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})+\mathrm{asymm}_{2}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}),$
(83)
$\displaystyle\mathrm{asymm}_{2}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})\leq$
$\displaystyle\mathrm{asymm}_{1,2}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})+\mathrm{asymm}_{1}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}).$
(84)

###### Proof.

The lemma is a simple consequence of the triangle inequality. We only prove
Equation 82. Equations 83 and 84 follow similarly.

$\displaystyle\mathrm{asymm}_{1,2}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})=$
$\displaystyle\max_{(x^{1}_{1},x^{1}_{2})\in{{\mathcal{X}}_{1}}^{2}}\max_{(x^{2}_{1},x^{2}_{2})\in{{\mathcal{X}}_{2}}^{2}}\left|P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})-P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{2},x^{1}_{1},x^{2}_{2},x^{2}_{1})\right|$
$\displaystyle\leq$
$\displaystyle\max_{(x^{1}_{1},x^{1}_{2})\in{{\mathcal{X}}_{1}}^{2}}\max_{(x^{2}_{1},x^{2}_{2})\in{{\mathcal{X}}_{2}}^{2}}\left(\left|P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})-P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{1},x^{1}_{2},x^{2}_{2},x^{2}_{1})\right|\right.$
$\displaystyle+\left.\left|P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{1},x^{1}_{2},x^{2}_{2},x^{2}_{1})-P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{2},x^{1}_{1},x^{2}_{2},x^{2}_{1})\right|\right)$
$\displaystyle\leq$
$\displaystyle\max_{(x^{1}_{1},x^{1}_{2})\in{{\mathcal{X}}_{1}}^{2}}\max_{(x^{2}_{1},x^{2}_{2})\in{{\mathcal{X}}_{2}}^{2}}\left|P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})-P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{1},x^{1}_{2},x^{2}_{2},x^{2}_{1})\right|$
$\displaystyle+\max_{(x^{1}_{1},x^{1}_{2})\in{{\mathcal{X}}_{1}}^{2}}\max_{(x^{2}_{1},x^{2}_{2})\in{{\mathcal{X}}_{2}}^{2}}\left|P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{1},x^{1}_{2},x^{2}_{2},x^{2}_{1})-P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{2},x^{1}_{1},x^{2}_{2},x^{2}_{1})\right|$
$\displaystyle=$
$\displaystyle\mathrm{asymm}_{1}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})+\mathrm{asymm}_{2}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}).\qed$
(85)

By Lemma 31, we can reduce Cases (2)-(4) to the symmetric case (Case (1)) with
$\alpha$ replaced by $2\alpha$. Indeed, in Case (2),

$\displaystyle\alpha<\mathrm{asymm}_{1,2}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})\leq$
$\displaystyle\mathrm{asymm}_{1}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})+\mathrm{asymm}_{2}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})\leq
2\alpha.$

Cases (3) and (4) are similar.

####  XIV-B4 Case (1) in Table III

Case (1) is treated in the next section.

###  XIV-C Symmetric case

In the previous section, we showed that
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
associated to the subcode pair
$({\mathcal{C}}_{1}^{\prime},{\mathcal{C}}_{2}^{\prime})$ must be
approximately symmetric (in the sense of Definition 19) for both
$|{\mathcal{C}}_{1}^{\prime}|$ and $|{\mathcal{C}}_{2}^{\prime}|$ to be large,
regardless of the channel structure. Therefore, in this section we focus on
the case where

$\displaystyle\mathrm{asymm}(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}})\leq\alpha.$
(86)

Though we assume ${\mathcal{G}}\left(P_{1},P_{2}\right)=\emptyset$ in Item 1
of Theorem 20, the set
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$
may or may not be empty (see Figure 5). We treat these two cases separately in
the subsequent two subsections (Sections XIV-C1 and XIV-C2).

####  XIV-C1 The case where
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)=\emptyset$

In this subsection, we show that if
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)=\emptyset$,
then both $M_{1}^{\prime}$ and $M_{2}^{\prime}$ are bounded from above by a
constant. Therefore, any good code pair
$({\mathcal{C}}_{1},{\mathcal{C}}_{2})$ has rates $R_{1}=0$ and $R_{2}=0$. The
geometry of various sets of distributions that are involved in the following
proof is depicted in Figure 4.

Figure 4: The geometry of various sets of distributions in the converse proof
in Section XIV-C1. We assume
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)=\emptyset$
and would like to show that any zero-error code pair has rate $R_{1}=0$ and
$R_{2}=0$. In the above figure, the ambient space is the set
${\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)$ of self-couplings equipped with
$\ell^{1}$ metric. The set ${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$ is
a strict subset of ${\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$ such that
they are $\varepsilon$-separated (see Equation 87). The joint types of the
equicoupled subcode pair
$({\mathcal{C}}_{1}^{\prime},{\mathcal{C}}_{2}^{\prime})$ are in an
$\eta^{\prime}$-ball (see Equation 91) around a distribution
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
which is assumed to be $\alpha$-symmetric (see Equation 86). We then project
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
to obtain a symmetric distribution
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
defined in Equation 88. (Note that
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
may be slight inside ${\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$.) It can
be shown that
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
and
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
are $\alpha^{\prime}$-close (see Equation 89). Since
$({\mathcal{C}}_{1}^{\prime},{\mathcal{C}}_{2}^{\prime})$ attains zero error
and all joint types are outside
${\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$, one can show that
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
is $(\varepsilon-\eta^{\prime}-\alpha^{\prime})$-far from
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$ (see 32). This allows us to
proceed with the double counting argument.

We assume that ${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$ is a _proper_
subset of ${\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$. Specifically, we
assume that there exists a constant $\varepsilon>0$ such that

$\displaystyle
d_{{1}}\left({\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right),{\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\right)\geq\varepsilon.$
(87)

We first project
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
to ${\mathcal{S}}_{1,2}\left(P_{1},P_{2}\right)$ and obtain an _exactly_
symmetric distribution
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$,

$\displaystyle\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\coloneqq\frac{1}{4}\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}+P_{{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}+P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{2},{\mathbf{x}}^{2}_{1}}+P_{{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}_{2},{\mathbf{x}}^{2}_{1}}\right).$
(88)

Since the four summands are all in
${\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)$,
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
is also in ${\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)$. Also, one can easily
check that it is indeed symmetric in the sense of Definition 14. Furthermore,
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
and
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
are close to each other.

$\displaystyle
d_{{1}}\left(\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)=$
$\displaystyle\sum_{(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})\in{\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}^{2}}\left|\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})-P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})\right|$
$\displaystyle\leq$
$\displaystyle\sum_{(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})\in{\mathcal{X}}_{1}^{2}\times{\mathcal{X}}_{2}^{2}}\frac{1}{4}\left(\left|P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})-P_{{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})\right|\right.$
$\displaystyle+\left|P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})-P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{2},{\mathbf{x}}^{2}_{1}}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})\right|$
$\displaystyle+\left.\left|P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})-P_{{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}_{2},{\mathbf{x}}^{2}_{1}}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})\right|\right)$
$\displaystyle\leq$
$\displaystyle\frac{3}{4}|{\mathcal{X}}_{1}|^{2}|{\mathcal{X}}_{2}|^{2}\alpha\eqqcolon\alpha^{\prime}.$
(89)

Equation 89 follows from the assumption given by Equation 86. Though we will
not use it, the above bound can be slightly improved to
$\alpha^{\prime}=\frac{1}{4}\left(3|{\mathcal{X}}_{1}|^{2}|{\mathcal{X}}_{2}|^{2}-|{\mathcal{X}}_{1}||{\mathcal{X}}_{2}|^{2}-|{\mathcal{X}}_{1}|^{2}|{\mathcal{X}}_{2}|-|{\mathcal{X}}_{1}||{\mathcal{X}}_{2}|\right)$
by noting that some terms corresponding to
${\underline{x}}^{1}_{1}={\underline{x}}^{1}_{2}$ or
${\underline{x}}^{2}_{1}={\underline{x}}^{2}_{2}$ do not contributed to the
sum.

######  Claim 32.

Under the assumptions of Section XIV-C1,
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
is not in ${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$:

$\displaystyle
d_{{1}}\left(\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\right)\geq$
$\displaystyle\varepsilon-\eta^{\prime}-\alpha^{\prime},$ (90)

where
$\eta^{\prime}\coloneqq\left|{\mathcal{X}}_{1}\right|^{2}\left|{\mathcal{X}}_{2}\right|^{2}\eta$
and $\alpha^{\prime}$ was defined in Equation 89.

###### Proof.

To prove the claim, first recall that for any $1\leq i_{1}<i_{2}\leq
M_{1}^{\prime}$ and $1\leq j_{1}<j_{2}\leq M_{2}^{\prime}$, we have (by 6)

$\displaystyle
d_{{1}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)\leq$
$\displaystyle\left|{\mathcal{X}}_{1}\right|^{2}\left|{\mathcal{X}}_{2}\right|^{2}d_{{\infty}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)\leq\left|{\mathcal{X}}_{1}\right|^{2}\left|{\mathcal{X}}_{2}\right|^{2}\eta\eqqcolon\eta^{\prime}.$
(91)

Since $({\mathcal{C}}_{1},{\mathcal{C}}_{2})$ is a good code pair,
$({\mathcal{C}}_{1}^{\prime},{\mathcal{C}}_{2}^{\prime})$ is also good. Hence
$\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}$
is not confusable, i.e.,

$\displaystyle\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}\in{\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right).$
(92)

We get that
$\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}$
is strictly bounded away from ${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$.

$\displaystyle
d_{{1}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\right)\geq
d_{{1}}\left({\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right),{\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\right)\geq\varepsilon.$
(93)

The first inequality is by Equation 92 and the second one follows from the
assumption given by Equation 87. Equations 93 and 91 imply that
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
is strictly outside ${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$.

$\displaystyle
d_{{1}}\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\right)\geq$
$\displaystyle
d_{{1}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\right)-d_{{1}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)\geq\varepsilon-\eta^{\prime}.$
(94)

Combining Equations 94 and 89, we further have

$\displaystyle
d_{{1}}\left(\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\right)\geq$
$\displaystyle
d_{{1}}\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\right)-d_{{1}}\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)\geq\varepsilon-\eta^{\prime}-\alpha^{\prime}.$

This finishes the proof of 32. ∎

Since
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\notin{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$
by Equation 90, we can apply Theorem 18. There exists
$Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in\mathrm{co}\text{-}{\mathcal{G}}_{1,2}\left(P_{1},P_{2}\right)$
such that

$\displaystyle\left\langle\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle\leq$
$\displaystyle-\varepsilon^{\prime}<0$ (95)

for some constant $\varepsilon^{\prime}>0$.

To prove upper bounds on $M_{1}^{\prime}$ and $M_{2}^{\prime}$, the trick is
to upper and lower bound the following quantity

$\displaystyle\sum_{(i_{1},i_{2})\in[M_{1}^{\prime}]\times[M_{2}^{\prime}]}\sum_{(j_{1},j_{2})\in[M_{2}^{\prime}]\times[M_{2}^{\prime}]}\left\langle\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle.$
(96)

Contrasting the upper and lower bounds on Equation 96 will give us an upper
bound on $\max\left\\{M_{1}^{\prime},M_{2}^{\prime}\right\\}$. We first prove
an upper bound on Equation 96.

######  Claim 33.

Equation 96 is at most

$\displaystyle\sum_{(i_{1},i_{2})\in[M_{1}^{\prime}]\times[M_{2}^{\prime}]}\sum_{(j_{1},j_{2})\in[M_{2}^{\prime}]\times[M_{2}^{\prime}]}\left\langle\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle$
$\displaystyle\leq$ $\displaystyle
M_{1}^{\prime}(M_{1}^{\prime}-1)M_{2}^{\prime}(M_{2}^{\prime}-1)(\eta^{\prime}+\alpha^{\prime}-\varepsilon^{\prime})+M_{1}^{\prime
2}M_{2}^{\prime}+M_{1}^{\prime}M_{2}^{\prime 2}+M_{1}^{\prime}M_{2}^{\prime}.$
(97)

###### Proof.

Expanding the summation in Equation 96, we have

$\displaystyle\sum_{(i_{1},i_{2})\in[M_{1}^{\prime}]\times[M_{1}^{\prime}]}\sum_{(j_{1},j_{2})\in[M_{2}^{\prime}]\times[M_{2}^{\prime}]}\left\langle\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle$
$\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}(i_{1},i_{2},j_{1},j_{2})\in[M_{1}^{\prime}]^{2}\times[M_{2}^{\prime}]^{2}\\\
i_{1}\neq i_{2},j_{1}\neq
j_{2}\end{subarray}}+\sum_{\begin{subarray}{c}(i_{1},i_{2},j_{1},j_{2})\in[M_{1}^{\prime}]^{2}\times[M_{2}^{\prime}]^{2}\\\
i_{1}=i_{2}\mathrm{\ or\
}j_{1}=j_{2}\end{subarray}}\left\langle\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle$
$\displaystyle=$ $\displaystyle\sum_{i_{1}\neq i_{2},j_{1}\neq
j_{2}}+\sum_{i_{1}\neq i_{2},j_{1}=j_{2}}+\sum_{i_{1}=i_{2},j_{1}\neq
j_{2}}+\sum_{i_{1}=i_{2},j_{1}=j_{2}}\left\langle\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle.$
(98)

Note that

$\displaystyle\left\langle\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle\leq$
$\displaystyle\left\|\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}\right\|_{2}\left\|Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\|_{2}\leq\left\|\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}\right\|_{1}\left\|Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\|_{1}=1.$

The last three terms in Equation 98 is at most

$\displaystyle M_{1}^{\prime 2}M_{2}^{\prime}+M_{1}^{\prime}M_{2}^{\prime
2}+M_{1}^{\prime}M_{2}^{\prime}.$ (99)

The first term in Equation 98 can be bounded as follows.

$\displaystyle\sum_{i_{1}\neq i_{2},j_{1}\neq
j_{2}}\left\langle\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle$
$\displaystyle=$ $\displaystyle\sum_{i_{1}\neq i_{2},j_{1}\neq
j_{2}}\left(\left\langle\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}-\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle+\left\langle\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle\right).$
(100)

For any $i_{1}\neq i_{2}$ and $j_{1}\neq j_{2}$, the first term of the summand
in Equation 100 is at most

$\displaystyle\left\langle\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}-\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle\leq$
$\displaystyle\left\|\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}-\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\|_{1}\left\|Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\|_{\infty}$
(101) $\displaystyle\leq$ $\displaystyle
d_{{1}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)+d_{{1}}\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)$
(102) $\displaystyle\leq$ $\displaystyle\eta^{\prime}+\alpha^{\prime}.$ (103)

In Equation 101, we used the symmetry141414The double counting argument
crucially relies on the symmetry of
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
which is the reason why we treat the symmetric and asymmetric cases
separately.  (as per Definition 14) of
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$.
Specifically, since
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{S}}_{1,2}\left(P_{1},P_{2}\right)$,
we have

$\displaystyle
d_{{1}}\left(\tau_{{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{2}_{j_{2}},{\underline{x}}^{2}_{j_{1}}},\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)=$
$\displaystyle
d_{{1}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},\overline{P}_{{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}_{2},{\mathbf{x}}^{2}_{1}}\right)=d_{{1}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right),$
$\displaystyle
d_{{1}}\left(\tau_{{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)=$
$\displaystyle
d_{{1}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},\overline{P}_{{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)=d_{{1}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right),$
$\displaystyle
d_{{1}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{2}},{\underline{x}}^{2}_{j_{1}}},\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)=$
$\displaystyle
d_{{1}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{2},{\mathbf{x}}^{2}_{1}}\right)=d_{{1}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right).$

Hence, the bound in Equation 103 holds for all $i_{1}\neq i_{2}$ and
$j_{1}\neq j_{2}$ (not only for $i_{1}<i_{2}$ and $j_{1}<j_{2}$). In Equation
102, we used the trivial bound
$\left\|Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\|_{\infty}\leq
1$ since
$Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
is a probability distribution. Equation 103 is by Equations 89 and 91.
Combining Equations 103 and 95, we get that the first term in Equation 98 is
at most

$\displaystyle M_{1}^{\prime 2}M_{2}^{\prime
2}(\eta^{\prime}+\alpha^{\prime}-\varepsilon^{\prime}).$ (104)

Overall, by Equations 99 and 104, we get an upper bound on Equation 96:

$\displaystyle
M_{1}^{\prime}(M_{1}^{\prime}-1)M_{2}^{\prime}(M_{2}^{\prime}-1)(\eta^{\prime}+\alpha^{\prime}-\varepsilon^{\prime})+M_{1}^{\prime
2}M_{2}^{\prime}+M_{1}^{\prime}M_{2}^{\prime 2}+M_{1}^{\prime}M_{2}^{\prime},$

which completes the proof of 33. ∎

On the other hand, a lower bound on Equation 96 follows from a direct
calculation.

######  Claim 34.

Equation 96 is nonnegative, i.e.,

$\displaystyle\sum_{(i_{1},i_{2})\in[M_{1}^{\prime}]\times[M_{2}^{\prime}]}\sum_{(j_{1},j_{2})\in[M_{2}^{\prime}]\times[M_{2}^{\prime}]}\left\langle\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle\geq
0.$ (105)

###### Proof.

We compute Equation 96 from the first principle and interchange the
summations.

$\displaystyle\sum_{(i_{1},i_{2})\in[M_{1}^{\prime}]\times[M_{2}^{\prime}]}\sum_{(j_{1},j_{2})\in[M_{2}^{\prime}]\times[M_{2}^{\prime}]}\left\langle\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle$
$\displaystyle=$
$\displaystyle\sum_{(i_{1},i_{2})\in[M_{1}^{\prime}]^{2}}\sum_{(j_{1},j_{2})\in[M_{2}^{\prime}]^{2}}\sum_{(x^{1}_{1},x^{1}_{2})\in{\mathcal{X}}_{1}^{2}}\sum_{(x^{2}_{1},x^{2}_{2})\in{\mathcal{X}}_{2}^{2}}\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})Q(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})$
$\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}(x^{1}_{1},x^{1}_{2})\in{\mathcal{X}}_{1}^{2}\\\
(x^{2}_{1},x^{2}_{2})\in{\mathcal{X}}_{2}^{2}\end{subarray}}\sum_{\begin{subarray}{c}(i_{1},i_{2})\in[M_{1}^{\prime}]^{2}\\\
(j_{1},j_{2})\in[M_{2}^{\prime}]^{2}\end{subarray}}\frac{1}{n}\sum_{k\in[n]}\mathds{1}{\left\\{{\underline{x}}^{1}_{i_{1}}(k)=x^{1}_{1}\right\\}}\mathds{1}{\left\\{{\underline{x}}^{1}_{i_{2}}(k)=x^{1}_{2}\right\\}}\mathds{1}{\left\\{{\underline{x}}^{2}_{j_{1}}(k)=x^{2}_{1}\right\\}}\mathds{1}{\left\\{{\underline{x}}^{2}_{j_{2}}(k)=x^{2}_{2}\right\\}}Q(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})$
$\displaystyle=$
$\displaystyle\frac{1}{n}\sum_{\begin{subarray}{c}(x^{1}_{1},x^{1}_{2})\in{\mathcal{X}}_{1}^{2}\\\
(x^{2}_{1},x^{2}_{2})\in{\mathcal{X}}_{2}^{2}\end{subarray}}\sum_{k\in[n]}\left(\sum_{i_{1}\in[M_{1}^{\prime}]}\mathds{1}{\left\\{{\underline{x}}^{1}_{i_{1}}(k)=x^{1}_{1}\right\\}}\right)\left(\sum_{i_{2}\in[M_{1}^{\prime}]}\mathds{1}{\left\\{{\underline{x}}^{1}_{i_{2}}(k)=x^{1}_{2}\right\\}}\right)$
$\displaystyle\left(\sum_{j_{1}\in[M_{2}^{\prime}]}\mathds{1}{\left\\{{\underline{x}}^{2}_{j_{1}}(k)=x^{2}_{1}\right\\}}\right)\left(\sum_{j_{2}\in[M_{2}^{\prime}]}\mathds{1}{\left\\{{\underline{x}}^{2}_{j_{2}}(k)=x^{2}_{2}\right\\}}\right)Q(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})$
$\displaystyle=$ $\displaystyle\frac{M_{1}^{\prime 2}M_{2}^{\prime
2}}{n}\sum_{k\in[n]}\sum_{\begin{subarray}{c}(x^{1}_{1},x^{1}_{2})\in{\mathcal{X}}_{1}^{2}\\\
(x^{2}_{1},x^{2}_{2})\in{\mathcal{X}}_{2}^{2}\end{subarray}}P_{1}^{(k)}(x^{1}_{1})P_{1}^{(k)}(x^{1}_{2})P_{2}^{(k)}(x^{2}_{1})P_{2}^{(k)}(x^{2}_{2})Q(x^{1}_{1},x^{1}_{2},x^{2}_{1},x^{2}_{2})$
(106) $\displaystyle=$ $\displaystyle M_{1}^{\prime 2}M_{2}^{\prime
2}\left\langle\frac{1}{n}\sum_{k\in[n]}\left(P_{1}^{(k)}\right)^{\otimes
2}\otimes\left(P_{2}^{(k)}\right)^{\otimes
2},Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right\rangle$
$\displaystyle\geq$ $\displaystyle 0.$ (107)

In Equation 106, $P_{i}^{(k)}$ denotes the empirical distribution of the
$k$-th _column_ of the codebook
${\mathcal{C}}_{i}^{\prime}\in{\mathcal{X}}_{i}^{M_{i}^{\prime}\times n}$,
i.e., for any $x^{i}\in{\mathcal{X}}_{i}$,

$\displaystyle
P_{i}^{(k)}(x^{i})=\frac{1}{M_{i}^{\prime}}\left|\left\\{\ell\in[M_{i}^{\prime}]:{\underline{x}}^{i}_{\ell}(k)=x^{i}\right\\}\right|.$
(108)

Equation 107 follows from Theorem 18 since
$\frac{1}{n}\sum_{k\in[n]}\left(P_{1}^{(k)}\right)^{\otimes
2}\otimes\left(P_{2}^{(k)}\right)^{\otimes
2}\in{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$ and
$Q_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in\mathrm{co}\text{-}{\mathcal{G}}_{1,2}\left(P_{1},P_{2}\right)$.

This finishes the proof of 34. ∎

Finally, Equations 97 and 105 yield

$\displaystyle 0\leq$ $\displaystyle M_{1}^{\prime 2}M_{2}^{\prime
2}(\eta^{\prime}+\alpha^{\prime}-\varepsilon^{\prime})+M_{1}^{\prime
2}M_{2}^{\prime}+M_{1}^{\prime}M_{2}^{\prime 2}+M_{1}^{\prime}M_{2}^{\prime}$
$\displaystyle\implies$ $\displaystyle 0\leq$ $\displaystyle
M_{1}^{\prime}M_{2}^{\prime}(\eta^{\prime}+\alpha^{\prime}-\varepsilon^{\prime})+M_{1}^{\prime}+M_{2}^{\prime}+1$
$\displaystyle\implies$ $\displaystyle 0\leq$ $\displaystyle-\delta M^{\prime
2}+2M^{\prime}+1$ (109) $\displaystyle\implies$ $\displaystyle M^{\prime}\leq$
$\displaystyle\frac{1+\sqrt{1+\delta}}{\delta}$ (110)

In Equation 109, we let
$M^{\prime}\coloneqq\max\left\\{M_{1}^{\prime},M_{2}^{\prime}\right\\}$ and
$\delta\coloneqq\varepsilon^{\prime}-\eta^{\prime}-\alpha^{\prime}>0$.
Equation 110 gives us the desired bound
$\max\left\\{M_{1}^{\prime},M_{2}^{\prime}\right\\}\leq C$ for some constant
$C>0$ independent of $n$.

####  XIV-C2 The case where
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\neq\emptyset$

Intuitively, this case is impossible for the following reasons. In the last
subsection, we have shown that for any of $|{\mathcal{C}}_{1}^{\prime}|$ and
$|{\mathcal{C}}_{2}^{\prime}|$ to be large, the distribution
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
should (approximately) belong to
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$.
For one thing, since
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)$,
by the second property in Proposition 17,
$\left[\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1}}$
(approximately) belongs to ${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)$ and
$\left[\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
(approximately) belongs to ${\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)$. For
another thing, since the code pair
$({\mathcal{C}}_{1}^{\prime},{\mathcal{C}}_{2}^{\prime})$ is assumed to attain
zero error in the first place, we have that
$\left[\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1}}$
which is close to
$\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}}}$
is (approximately) outside ${\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$ and
$\left[\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
which is close to
$\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}$
is (approximately) outside ${\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$. In
summary, we found a distribution
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$
with
$\left[\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1}}\in{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$
and
$\left[\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$.
This, nevertheless, contradicts the assumption
${\mathcal{G}}\left(P_{1},P_{2}\right)=\emptyset$ of Item 1 in Theorem 20.

The above intuition can be formalized by taking a good care of various slack
factors. We flesh out the details below.

In the previous section, we showed that for any constant $\gamma>0$, if the
distribution
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
(which is the symmetrized version of
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$,
as defined in Equation 88) associated to
$({\mathcal{C}}_{1}^{\prime},{\mathcal{C}}_{2}^{\prime})$ is $\gamma$-far (in
$\ell^{1}$ distance) from ${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$,
then both $M_{1}^{\prime}$ and $M_{2}^{\prime}$ are at most a constant
$g(\gamma)$ for some function $g(\gamma)\xrightarrow{\gamma\to 0}0$.151515 In
the previous section, $\gamma=\varepsilon-\eta^{\prime}-\alpha^{\prime}$ as we
got in Equation 90 and
$g(\gamma)=g(\varepsilon,\eta^{\prime},\alpha^{\prime})=\frac{1+\sqrt{1+\varepsilon^{\prime}-\eta^{\prime}-\alpha^{\prime}}}{\varepsilon^{\prime}-\eta^{\prime}-\alpha^{\prime}}$
where $\varepsilon^{\prime}=\varepsilon^{\prime}(\varepsilon)$ as we obtained
in Equation 110.  In other words, for $M_{1}^{\prime}$ or $M_{2}^{\prime}$ to
be sufficiently large,
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
has to be $\gamma$-close (in $\ell^{1}$ distance) to
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$ for an arbitrarily small
constant $\gamma>0$. Note also that unlike
$\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}$,
the distribution
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
can be _slightly_ inside ${\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$.
However, it cannot be _significantly_ inside
${\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$. Specifically, for any $1\leq
i_{1}<i_{2}\leq M_{1}^{\prime}$ and $1\leq j_{1}<j_{2}\leq M_{2}^{\prime}$,

$\displaystyle
d_{{1}}\left(\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},{\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\right)$
$\displaystyle\leq$ $\displaystyle
d_{{1}}\left(\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right)+d_{{1}}\left(P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}}\right)+d_{{1}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j_{1}},{\underline{x}}^{2}_{j_{2}}},{\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\right)$
(111) $\displaystyle\leq$ $\displaystyle\alpha^{\prime}+\eta^{\prime}.$ (112)

In Equation 112, we used Equations 89 and 91. Also, the last term in Equation
111 is zero due to Equation 92. Overall, we have that for any good code pair
$({\mathcal{C}}_{1}^{\prime},{\mathcal{C}}_{1}^{\prime})\in{\mathcal{X}}_{1}^{M_{1}^{\prime}\times
n}\times{\mathcal{X}}_{2}^{M_{2}^{\prime}\times n}$ extracted from Lemma 27,
for either $M_{1}^{\prime}$ or $M_{2}^{\prime}$ to be sufficiently large,
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}$
has to be $(\varepsilon-\eta^{\prime}-\alpha^{\prime})$-close to
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$ and
$(\alpha^{\prime}+\eta^{\prime})$-close to
${\mathcal{J}}_{1,2}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$
for arbitrarily small constants $\varepsilon,\eta^{\prime},\alpha^{\prime}>0$.

Therefore, we can without loss of rigor drop these slack factors and assume
for convenience

$\displaystyle\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right).$
(113)

For this to be possible, in this subsection we consider the case where
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\neq\emptyset$.

Let

$\displaystyle\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\coloneqq$
$\displaystyle\left[\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1}}=\left[\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{2}},$
$\displaystyle\overline{P}_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\coloneqq$
$\displaystyle\left[\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}=\left[\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}.$

Since
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)$,
the equality of the respective marginals above is by the second property of
Proposition 17. Furthermore, by Equation 112 and Lemma 9,

$\displaystyle
d_{{1}}\left(\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}},{\mathcal{J}}_{1}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\right)\leq$
$\displaystyle\alpha^{\prime}+\eta^{\prime},$ (114) $\displaystyle
d_{{1}}\left(\overline{P}_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}},{\mathcal{J}}_{2}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)\right)\leq$
$\displaystyle\alpha^{\prime}+\eta^{\prime}.$ (115)

We further divide the analysis into two cases (as shown in Figure 5).

(a) The case where
$\widetilde{{\mathcal{G}}_{{1}}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)=\emptyset$
where $\widetilde{{\mathcal{G}}_{{1}}}\left(P_{1},P_{2}\right)$ is defined in
Equation 116.

(b) The case where
$\widetilde{{\mathcal{G}}_{{1}}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\neq\emptyset$
while
$\widetilde{{\mathcal{G}}_{{2}}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)=\emptyset$
where $\widetilde{{\mathcal{G}}_{{2}}}\left(P_{1},P_{2}\right)$ is defined in
Equation 126.

Figure 5: Under the assumptions
${\mathcal{G}}\left(P_{1},P_{2}\right)=\emptyset$ and
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\neq\emptyset$,
we further divide the converse analysis into two cases. The goal is to show
that in these cases there do not exist zero-error code pairs of rates
$R_{1}>0$ and $R_{2}>0$. In the above figures, pink sets are confusability
sets and green sets are sets of good distributions. Two-dimensional sets are
sets of joint distributions (e.g.,
${\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right),{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)$)
and one-dimensional sets are sets of marginal distributions (e.g.,
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right),{\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right),{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right),{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$,
etc.).

  1. 1.

Define

$\displaystyle\widetilde{{\mathcal{G}}_{{1}}}\left(P_{1},P_{2}\right)\coloneqq$
$\displaystyle\left\\{\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1}}:P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\right\\}\subseteq{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right).$
(116)

Note that by Equation 113,

$\displaystyle\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in\widetilde{{\mathcal{G}}_{{1}}}\left(P_{1},P_{2}\right).$
(117)

Since we assume ${\mathcal{G}}\left(P_{1},P_{2}\right)=\emptyset$ in Item 1 of
Theorem 20,
$\widetilde{{\mathcal{G}}_{{1}}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$
may or may not be empty. We first handle the case where
$\widetilde{{\mathcal{G}}_{{1}}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)=\emptyset$.
In fact, let us assume

$\displaystyle
d_{{1}}\left(\widetilde{{\mathcal{G}}_{{1}}}\left(P_{1},P_{2}\right),{\mathcal{J}}_{1}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\right)\geq\varepsilon_{1}$
(118)

for some $\varepsilon_{1}>0$. See Figure 5(a). However, Equations 117 and 114
lead to a contradiction if $\alpha^{\prime}$ and $\eta^{\prime}$ and
sufficiently small so that $\alpha^{\prime}+\eta^{\prime}<\varepsilon_{1}$.
Therefore, it is impossible for this case to happen.

  2. 2.

Now we assume

$\displaystyle\widetilde{{\mathcal{G}}_{{1}}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\neq\emptyset.$
(119)

The analysis of the above case shows that
$\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in\widetilde{{\mathcal{G}}_{{1}}}\left(P_{1},P_{2}\right)$
has to be $(\alpha^{\prime}+\eta^{\prime})$-close to
${\mathcal{J}}_{1}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)$
for arbitrarily small $\alpha^{\prime}$ and $\eta^{\prime}$. Similar to the
assumption given by Equation 113, in the present case we may as well assume
for convenience

$\displaystyle\overline{P}_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in\widetilde{{\mathcal{G}}_{{1}}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right).$
(120)

Now define

$\displaystyle\widetilde{{\mathcal{G}}_{{2}}}\left(P_{1},P_{2}\right)\coloneqq$
$\displaystyle\left\\{\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}:\begin{array}[]{rl}P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in&{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\\\
\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1}}\in&{\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\end{array}\right\\}$
(123) $\displaystyle=$
$\displaystyle\left\\{\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}:\begin{array}[]{rl}P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in&{\mathcal{G}}_{{1,2}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1,2}}\left(P_{1},P_{2}\right)\\\
\left[P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\right]_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}_{1}}\in&\widetilde{{\mathcal{G}}_{{1}}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\end{array}\right\\}\subseteq{\mathcal{G}}_{{2}}\left(P_{1},P_{2}\right).$
(126)

Equation 126 is by Equation 116. By the assumption given by Equation 119,
$\widetilde{{\mathcal{G}}_{{2}}}\left(P_{1},P_{2}\right)\neq\emptyset$. Note
that by Equations 113 and 120,

$\displaystyle\overline{P}_{{\mathbf{x}}^{1},{\mathbf{x}}^{2}_{1},{\mathbf{x}}^{2}_{2}}\in\widetilde{{\mathcal{G}}_{{2}}}\left(P_{1},P_{2}\right).$
(127)

On the other hand, by the assumption
${\mathcal{G}}\left(P_{1},P_{2}\right)=\emptyset$ and Equation 119,
$\widetilde{{\mathcal{G}}_{{2}}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)$
must be empty. In fact let us assume

$\displaystyle
d_{{1}}\left(\widetilde{{\mathcal{G}}_{{2}}}\left(P_{1},P_{2}\right),{\mathcal{J}}_{2}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{2}}\left(P_{1},P_{2}\right)\right)\geq\varepsilon_{2}$
(128)

for some $\varepsilon_{2}>0$. See Figure 5(b). Now by Equations 115 and 127,
we again reach a contradiction if $\alpha+\eta^{\prime}<\varepsilon_{2}$.
Therefore, this case is also impossible to happen.

##  XV Converse, Items 2 and 3 in Theorem 20

In this section, we only prove Item 2. Item 3 follows by interchanging
notation. We assume that
${\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)=\emptyset$.
More precisely, we assume

$\displaystyle
d_{{1}}\left({\mathcal{G}}_{{1}}\left(P_{1},P_{2}\right),{\mathcal{J}}_{1}\left(P_{1},P_{2}\right)\setminus{\mathcal{K}}_{{1}}\left(P_{1},P_{2}\right)\right)\geq\varepsilon$
(129)

for some $\varepsilon>0$. Let $({\mathcal{C}}_{1},{\mathcal{C}}_{2})$ be any
good code pair. Suppose $R_{1}>0$. Our goal is to derive a contradiction.

###  XV-A Subcode extraction

######  Theorem 35 (Ramsey’s theorem [Wik21]).

Let ${\mathcal{K}}_{M}$ denote the (undirected) complete graph on $M$
vertices. Let $N\in{\mathbb{Z}}_{\geq 1},D\in{\mathbb{Z}}_{\geq 2}$. Then
there exists a constant $K=K(N,D)$ such that for every $D$-coloring of the
edges of ${\mathcal{K}}_{M}$ with $M\geq K$, there is a monochromatic clique
in ${\mathcal{K}}_{M}$ of size at least $N$.

######  Lemma 36 (Subcode extraction).

Let
$({\mathcal{C}}_{1},{\mathcal{C}}_{2})\subseteq{\mathcal{X}}_{1}^{n}\times{\mathcal{X}}_{2}^{n}$
be any $(P_{1},P_{2})$-constant composition code pair of sizes $M_{1},M_{2}$,
respectively. Let $j\in[M_{2}]$. Then there exists a subcode
${\mathcal{C}}_{1}^{\prime}\subseteq{\mathcal{C}}$ of size $M_{1}^{\prime}\geq
f(\left|{\mathcal{X}}_{1}\right|,\left|{\mathcal{X}}_{2}\right|,\eta,M_{1})\xrightarrow{M_{1}\to\infty}\infty$
and a distribution
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in{\mathcal{J}}_{1}\left(P_{1},P_{2}\right)$
such that for all $1\leq i_{1}<i_{1}\leq M_{1}^{\prime}$, we have
$d_{{\infty}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\right)\leq\eta$.

###### Proof.

The proof is similar to that of Lemma 27 and follows readily from Theorem 35.
We first build a complete graph ${\mathcal{K}}_{M_{1}}$ whose vertex set is
${\mathcal{C}}_{1}$. We then color the edges of ${\mathcal{K}}_{M_{1}}$ using
distributions in ${\mathcal{J}}_{1}\left(P_{1},P_{2}\right)$. Let
${\mathcal{N}}$ be an $\eta$-net of
${\mathcal{J}}_{1}\left(P_{1},P_{2}\right)$ of size at most
$|{\mathcal{N}}|\leq\left(\frac{\left|{\mathcal{X}}_{1}\right|^{2}\times\left|{\mathcal{X}}_{2}\right|}{2\eta}+1\right)^{\left|{\mathcal{X}}_{1}\right|^{2}\times\left|{\mathcal{X}}_{2}\right|}\eqqcolon
D$ (by Lemma 5). An edge
$({\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}})$ ($1\leq
i_{1}<i_{2}\leq M_{1}$) is colored by a distribution
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in{\mathcal{N}}$
if
$d_{{\infty}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\right)\leq\eta$.
Now by Theorem 35, there is a monochromatic subcode
${\mathcal{C}}_{1}^{\prime}\subseteq{\mathcal{C}}_{1}$ of size at least
$M_{1}^{\prime}\geq
f(\left|{\mathcal{X}}_{1}\right|,\left|{\mathcal{X}}_{2}\right|,\eta,M_{1})$,
where
$f(\left|{\mathcal{X}}_{1}\right|,\left|{\mathcal{X}}_{2}\right|,\eta,M_{1})\xrightarrow{M_{1}\to\infty}\infty$.
According to the way we colored the edges, this means that for all $1\leq
i_{1}<i_{2}\leq M_{1}^{\prime}$,
$d_{{\infty}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\right)\leq\eta$.
∎

Fix any $j\in[M_{2}]$. By Lemma 36, there is a subcode
${\mathcal{C}}_{1}^{\prime}\subseteq{\mathcal{C}}_{1}$ of size
$M_{1}^{\prime}\xrightarrow{M_{1}\to\infty}\infty$ such that for some
distribution
$P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\in{\mathcal{J}}_{1}\left(P_{1},P_{2}\right)$,
we have

$\displaystyle
d_{{\infty}}\left(\tau_{{\underline{x}}^{1}_{i_{1}},{\underline{x}}^{1}_{i_{2}},{\underline{x}}^{2}_{j}},P_{{\mathbf{x}}^{1}_{1},{\mathbf{x}}^{1}_{2},{\mathbf{x}}^{2}}\right)\leq\eta$
(130)